Modular Concrete Type-Inference for Statically Typed Object-oriented Programming Languages

The problem of 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. We present a new technique called analysis-using-abstract-values which performs modular and demand driven concrete type-inference of a robust subset of Java without threads and exceptions and C++ without exceptions. Our algorithm is provably precise on programs with only single-level types2 and without dynamic dispatch, and has the worst-case complexity of O(n4 ) which is an improvement over the O(n7 ) worst-case bound achievable by applying previous approaches of [RHS95] and [LR91] to this case. For general programs, the algorithm is polynomial-time and computes a safe solution.Technical report DCS-TR-34