Converting Java Classes to Use Generics∗Daniel von DincklageDepartment of Computer ScienceUniversity of [email protected] DiwanDepartment of Computer ScienceUniversity of [email protected] offer significant software engineering benefits sincethey provide code reuse without compromising type safety.Thus generics will be added to the Java language in the nextrelease. While this extension to Java will help programmerswhen they are writing new code, it will not help legacy codeunless it is rewritten to use generics. In our experience, man-ually modifying existing programs to use generics is complexand can be error prone and labor intensive.We describe a system, Ilwith, that (i) converts non-genericclasses to generic classes and (ii) rewrites their clients to usethe newly generified classes. Our experiments with a numberof Java container classes show that our system is effective inmo difying legacy code to use generics.Categories and Subject DescriptorsD.2.7 [Software Engineering]: Distribution, Maintenance,and EnhancementGeneral TermsLanguagesKeywordsGenerics, Parametric Polymorphism, Type Inference1. INTRODUCTIONGenerics, a special case of bounded parametric polymor-phism [3], are useful for writing data-structures that arereusable without compromising static type checking. For ex-ample, a generic list package, parameterized by its element∗This work was supported by NSF ITR grant CCR-0085792,an NSF Career Award CCR-0133457, and an IBM facultypartnership award. Any opinions, findings and conclusionsor recommendations expressed in this material are the au-thors’ and do not necessarily reflect those of the sponsors.Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies arenot made or distributed for profit or commercial advantage and that copiesbear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.OOPSLA’04, Oct. 24-28, 2004, Vancouver, British Columbia, Canada.Copyright 2004 ACM 1-58113-831-8/04/0010 ...$5.00.type, is not only reusable, but also preserves type informa-tion via the type parameter. In contrast, a non-generic listpackage, as distributed with Java [8], is reusable but oper-ations on a list return or take parameters of type Object.Thus clients of the list must explicitly apply narrowing con-versions, compromising static checking and readability ofco de. In addition to the software engineering benefits, gener-ics can also provide performance benefits. For example, theincreased type information provided by generics can givecompilers more freedom in reordering computations [4, 13].It is therefore no surprise that many modern languages suchas Eiffel [10], Modula-3 [12], and SML [11] support generics.Java does not yet support generics but will do so with thenext major release.In order to get the most benefit from the addition ofgenerics to Java, programmers will need to modify existingclasses. We show that even for simple classes this process iscomplex and thus can be error prone. To help programmersin rewriting existing classes to use generics we describe andevaluate a system, Ilwith, that performs two functions: (i) itanalyzes existing Java classes and discovers opportunities forconverting them into generic classes; (ii) it analyzes clients ofnon-generic classes and discovers how to modify the clientsto use generic versions of the classes. Programmers may usethe output of Ilwith as a guideline for manually rewritingclasses to use generics or may feed the output into a toolthat performs the rewriting automatically.Ilwith analyzes the classes it should generify, deriving con-straints on the types of all variables (instance variables, localvariables, parameters, etc.). These constraints are subsetbased [7] and capture all uses and definitions of variables inthe analyzed classes. They determine the range of types onecan use for each variable without violating the type safety ofthe analyzed classes. Ilwith uses these constraints to iden-tify and bound type parameters for the generic classes andto instantiate any generic classes used by the classes beinganalyzed.While the constraint-based analysis described above pro-duces Java programs that use generics and are correct withrespect to the Java type system, it is too aggressive: it re-sults in generic classes with a large number of type parame-ters even for simple classes. In the worst case, the approachab ove can result in generic classes with type parameters foreach variable, method parameter, return type, etc. Whilethese parameters are all correct, they are not what a pro-grammer would have chosen: programmers tend to pick oneor a few typ e parameters for each generic class, not tens orhundreds of parameters. Thus, to reduce the number of type1Listing 1: Dependency between the two tasksc l a s s ListWrapper {void s e t ( Obj ec t arg ) {data . add ( arg ) ;}Ob je ct get ( ) {return data . g e t ( 0 ) ;}L i s t d ata ;}parameters, Ilwith employs a number of coarsening heuris-tics. We designed our initial set of heuristics based on ourstudy of how Eiffel programs use generics. However, the setof heuristics is extensible and we expect to revise them aswe gain experience with our system.Ilwith is modular: it does not need whole program analy-sis. For best results, Ilwith needs to analyze a class after allclasses that it depends on have already been converted touse generics. In the case of cyclic dependencies, Ilwith cananalyze multiple classes at once.Our experience with Ilwith indicates that it often pro-duces the same output as an expert programmer. WhenIlwith was unable to produce the same output as our man-ual effort, we found the cause to be type problems in theJava class that were masked by weak type checking due toa lack of generics.The remainder of this paper is organized as follows: Sec-tion 2 describ e s our approach intuitively. Section 3 givesthe language that Ilwith operates upon and its type sys-tem. Section 4 presents the basic algorithm used in Ilwith.Section 5 refines our basic algorithm to handle Java-specificfeatures. Section 6 presents and motivates heuristics for im-proving the quality of results produced by Ilwith. Section7 presents our results. Section 8 presents related work andSection 9 concludes.2. INTUITION BEHIND OUR APPROACHIn order