Name
Abstract | ||
|---|---|---|
We present the problem of class hierarchy complementation: given a partially known hierarchy of classes together with subtyping constraints ("A has to be a transitive subtype of B") complete the hierarchy so that it satisfies all constraints. The problem has immediate practical application to the analysis of partial programs--e.g., it arises in the process of providing a sound handling of "phantom classes" in the Soot program analysis framework. We provide algorithms to solve the hierarchy complementation problem in the single inheritance and multiple inheritance settings. We also show that the problem in a language such as Java, with single inheritance but multiple subtyping and distinguished class vs. interface types, can be decomposed into separate single- and multiple-subtyping instances. We implement our algorithms in a tool, JPhantom, which complements partial Java bytecode programs so that the result is guaranteed to satisfy the Java verifier requirements. JPhantom is highly scalable and runs in mere seconds even for large input applications and complex constraints (with a maximum of 14s for a 19MB binary). |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1145/2509136.2509530 | OOPSLA |
Keywords | Field | DocType |
partial type graph,java verifier requirement,partial program,multiple subtyping,soot program analysis framework,partial java bytecode program,distinguished class,multiple inheritance setting,hierarchy complementation problem,class hierarchy complementation,single inheritance,multiple inheritance,java | Composition over inheritance,Interface (Java),Programming language,Computer science,Theoretical computer science,Class hierarchy,Java bytecode,Program analysis,Hierarchy,Java,Multiple inheritance | Conference |
Volume | Issue | ISSN |
48 | 10 | 0362-1340 |
Citations | PageRank | References |
1 | 0.35 | 8 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| George Balatsouras | 1 | 84 | 4.43 |
| Yannis Smaragdakis | 2 | 2247 | 147.50 |