Complexity of Concrete Type-inference in the Presence of Exceptions

Concrete type-inference for statically typed object-oriented programming languages (e.g., Java, C++) determines at each program point, those objects to which a reference may refer or a pointer may point during execution. A precise compile-time solution for this problem requires a ow-sensitive analysis. Our new complexity results for concrete type-inference distinguish the diculty of the intraprocedural and interprocedural problem for languages with combinations of single-level types3 , exceptions with or without subtyping, and dynamic dispatch. Our results include: { The rst polynomial-time algorithm for concrete type-inference in the presence of exceptions, which handles Java without threads, and C++ ; { Proofs that the above algorithm is always safe and provably precise on programs with single-level types, exceptions without subtyping, and without dynamic dispatch; { Proof that interprocedural concrete type-inference problem with single-level types and exceptions with subtyping, and without dynamic dispatch is PSPACE-hard, while the intraprocedural problem is PSPACE-complete. Other complexity characterizations of concrete type-inference for programs without exceptions are also presented.Technical report DCS-TR-34