\documentclass{article}
\usepackage{amsfonts}
\usepackage{graphicx}
%\oddsidemargin=0cm
%\evensidemargin=0cm
%\textwidth=6.5in
%\textheight=9in
%\topmargin=-.5in

\def\Cpp{{\tt C++}}  
\def\ignore#1{\relax}
\def\txt{\tt \small}
\def\baselinestretch{1.2}

\title{NextGen Developer's Guide}
\author
{
	\begin{tabular}{c}
		Eric Allen \\
		eallen@cs.rice.edu \\
		Rice University \\
		6100 S. Main St. \\
		Houston TX 77005 \\
	\end{tabular}
}

\begin{document}
\maketitle

\section{Introduction}
This document describes the high-level architecture and code layout of the {\sc NextGen} prototype compiler, developed at Rice University. The {\sc NextGen} compiler was developed as an extension to the {\sc GJ} compiler under special license from Sun Microsystems. This same compiler was extended independently by Sun Microsystems to form the JSR-14 prototype compiler, scheduled for inclusion in J2SE 1.5. In the process of developing {\sc NextGen}, we have refactored the original {\sc GJ} compiler substantially, and no attempt has been made to maintain compatibility with the JSR-14 source code. Nevertheless, the reader may find that some of the architectural features of {\sc NextGen} described here are helpful when deciphering the JSR-14 code base (modulo class, package, and variable name changes). 

The {\sc GJ} compiler, as well as the {\sc NextGen} and JSR-14 compilers derived from it, are written in Generic Java.\footnote{"Generic Java" is a specification for a family of languages that add generic types to Java. This family includes both {\sc GJ} and {\sc NextGen}.} As a result, we enjoy much more precise type checking in the source code of these compilers than we would have with ordinary Java. But we are also unable to use many of the powerful development tools available for standard Java.\footnote{Two very useful tools that are compatible with Generic Java are the {\sc CodeGuide} and {\sc DrJava} IDEs. All {\sc NextGen} developers are encouraged to leverage both tools. {\sc Drjava} is particularly useful for writing new unit tests; {\sc CodeGuide} provides support for automated refactoring and incremental compilation.}

Throughout this document, it is assumed that the reader is familiar with the {\sc GJ}, {\sc NextGen}, and {\sc MixGen}  language designs, as well as the published descriptions of how these languages can be compiled to the JVM so as to maintain compatibility with existing compiled binaries. Readers not already familiar with this material are referred to \cite{GJ, NextGen, MixGen}. The References section also includes optional background material discussing various extensions of the Java type system, including first-class genericity and non-generic mixins.

It is also assumed that the reader has set up a JavaPLT development environment, is familiar with basic CVS commands, with JUnit, with Ant, and with DrJava. Instructions on setting up a JavaPLT environment are available at
\begin{verbatim}
 http://www.cs.rice.edu/~javaplt/doc/developer.pdf
\end{verbatim} A short tutorial on CVS is available at {\txt http://www.cvshome.org/docs/manual}. A tutorial on JUnit is available at {\txt http://www.junit.org}. A tutorial on Ant is available at {\txt http://www.jakarta.org}. DrJava documentation is available at {\txt http://drjava.sf.net}. 

\section{The {\sc NextGen} CVS Repository}
The {\sc NextGen} source code is maintained under the {\txt javaplt} CVS repository. To checkout the NextGen source code, go to your {\txt javaplt} directory and checkout the module {\txt nextgen}. 
Because {\sc NextGen} is written in JSR-14, you will need to prepend JSR-14 to the bootclasspath when starting Ant. The best way to do that is to set your {\txt ANT\_OPTS} environment variable to the location of the JSR-14 jar. For example, on Unix systems, set it to:
\begin{verbatim}
-Xbootclasspath/p:`javaplt-home`/packages/jsr14_adding_generics-1_3-ea/javac.jar
\end{verbatim}
Of course, on Windows/Cygwin, your path will look different.\footnote{Because we must set this variable before Ant starts, this is one place where Ant's ability to automatically convert path names doesn't save us.}

Once you have checked out a copy of the code, the first thing you should do is {\txt cd} to the new {\txt nextgen} directory and type 
\begin{verbatim}
$ ant all
\end{verbatim}

Doing so will run all Ant targets in the project. An {\it essential} invariant of the {\sc NextGen} project is that {\txt ant all} should succeed when invoked on a clean checkout, on all supported platforms (Linux, Solaris, OS X, and Windows XP/Cygwin) with a proper JavaPLT development environment. If it doesn't, be sure to correct any problems with your environment before continuing.

\section{The {\sc NextGen} Project Directory Structure}
The {\txt nextgen} project directory contains the following files and subdirectories:
\begin{itemize}

\item{\txt build.xml}. This file contains the XML source code for all Ant targets associated with the NextGen project. 

\item {\txt anttools}. This directory contains the Java source code for custom Ant tasks associated with {\sc NextGen}. In particular, the {\txt NextGenCompilerTask} and {\txt NextGenJUnitRunner} source code is contained here. Because all Java source code in the {\sc NextGen} project is placed in various subpackages of {\txt edu.rice.cs.nextgen}, the files in this directory (and all other directories containing Java source code) are all placed in subdirectories of {\txt edu/rice/cs/nextgen}.


{\txt NextGenCompilerTask} is used in the {\txt ant compile} target in {\txt build.xml}. Although the {\sc NextGen} compiler could be invoked within Ant simply as a Java program, the {\txt NextGenCompilerTask} is much more convenient because it allows the compiler to be invoked on Ant filesets and other compound structures instead of just an explicit list of command-line arguments. 

{\txt NextGenJUnitRunner} is used  for {\sc NextGen} acceptance testing. It is called by the {\txt simpletests} target. This task uses the {\sc NextGen} classloader to invoke JUnit on {\txt TestCases} compiled with the {\txt NextGenCompiler}. Note that such {\txt TestCases} can't be invoked by JUnit with the default class loader because some of them may be template classfiles.

\item {\txt benchmarks}. Contains the source code for the {\sc NextGen} benchmark suite. There are three versions of this suite: {\txt edu.rice.cs.nextgen.javabenchmarks}, {\txt edu.rice.cs.nextgen.gjbenchmarks}, {\txt edu.rice.cs.nextgen.nextgenbenchmarks}, corresponding to the three compilers tested in {\sc NextGen} benchmarking. All of these suites are compiled by the Ant target {\txt compile-benchmarks}. A bash script is provided for running the benchmarks in the {\txt bin} subdirectory, discussed below. Note that the benchmarks can't be run (easily) from within Ant because an entire run of the benchmarks involves invoking several different JVMs with different classloaders. Also, to prevent skewing performance results, we don't want to use up resources by running an Ant process during benchmarking.

\item{\txt bin}. Contains various bash scripts useful for performing tasks associated with the {\sc NextGen} project. Ultimately, we'd like to turn all of these scripts into platform-independent Ant targets, but in same cases, we haven't yet found a good way to do that.

\item{\txt doc}. Contains all documentation associated with the {\sc NextGen} project, including the sources for this document. The NextGen documentation available online is a checked out copy of this directory. To make changes to the live webpage, you must have write access to {\txt /home/javaplt}. After committing your changes, go to {\txt /home/javaplt/public\_html} and execute {\txt cvs update}. That command will update both the {\txt public\_html} module and the copy of {\txt nextgen/doc}. To update only the {\sc NextGen} documentation, simply perform a {\txt cvs update} in the {\txt /home/javaplt/public\_html/nextgen} directory.

\item{\txt lib}. Contains all library classes needed by the Ant targets, including JSR-14, JUnit, and all {\txt bootclasses} for Linux, Solaris, OS X, and Windows XP. Note that the bootclasses are included inside this project subdirectory to maintain the invariant that {\txt ant all} always succeeds on a clean checkout. All bootclasses must be accessible not just to Ant, but also to the {\sc NextGen} compiler, to prevent it from signaling errors when compiling sources with references to standard library classes. There is no standardization of the placement of bootclassses across JDKs\footnote{Non-Sun JDKs such as the Mac OS X JDK do not always follow the file layout of the Sun JDKs, and Sun hasn't made JDK file layout part of any standard specification.} and we want to decouple any quirks of the bootclasspath on a platform from the ability of the Ant targets to work. By putting all bootclasses in a well-defined location, we can ensure that we can always find them. 

\item{\txt manifests}. Contains the manifest files used when bundling the {\sc NextGen} compiler and classloader into jar files.

\item{\txt jars}. Contains the jar files for the compiler and classloader, constructed with target {\txt ant jar}.

\item{\txt simpletests}. Contains all acceptance tests for the {\sc NextGen} compiler, in the form of JUnit {\txt TestCases} written in {\sc NextGen}. Running an acceptance test consists of compiling it under the {\sc NextGen} compiler and then invoking JUnit on it with the {\sc NextGen} classloader. By running JUnit on the compiled code, we check that the semantics of that code is as expected, providing a powerful check on {\sc NextGen's} correctness. The acceptance tests can be run by invoking the Ant target {\txt simpletests}.

\item{\txt src}. Contains all source code for the {\sc NextGen} compiler and classloader, in packages {\txt edu.rice.cs.nextgen.compiler} and {\txt edu.rice.cs.nextgen.classloader}, respectively. In the section on {\sc NextGen} package design, we will discuss the various subpackages in this directory.

\item{\txt built}. This directory is empty on a clean checkout. It's used by Ant to store the class files for all Generic Java sources associated with {\sc NextGen}.

\end{itemize}

\section{Ant Targets in the {\sc NextGen} Project}
For a complete list of targets, always refer to the {\txt build.xml} file. Below are some of the most common targets you will invoke.

\begin{itemize}
\item{\txt clean}. Deletes all compiled classfiles.
\item{\txt compile}. Compiles the compiler and classloader.
\item{\txt test}. Runs all unit tests on the compiler and classloader.
\item{\txt simpletests}. Compiles the compiler and classloader and runs all acceptance tests.
\item{\txt testall}. Compiles the compiler and classloader and runs all unit tests and acceptance tests.
\item{\txt compile-tests}. Compiles all acceptance tests with the most recently compiled version of {\sc NextGen}.
\item{\txt update}. Updates this checked out copy of {\sc NextGen} with the CVS repository. 
\item{\txt commit}. Synchronizes with the CVS repository, compiles, ensures that all unit tests and acceptance tests still pass, and, if so, creates new jar files and commits the newly synchronized version to the repository. Run this often! At least once a day, if not once an hour when actively working with the code.  The more often  you run it, the easier it will be to diagnose new bugs.
\item{\txt jar}. Constructs jar files for the most recently compiled versions of the compiler and classloader.
\item{\txt all}. Runs all targets in the project. Useful for making sure that everything still works.
\item{\txt alloffline}. Runs all targets in the project except commit. Useful for making sure that everything testable works when you're not connected to a network.
\end{itemize}

\section{Releasing a New Version of {\sc NextGen}}
The {\sc NextGen} documentation and jar files are available online at {\txt http://www.cs.rice.edu/~javaplt/nextgen}. To release the latest committed version to the live website, simply go to {\txt /home/javaplt/nextgen} on csnet and do a {\txt cvs update}. Concerning the documentation: be sure that the latest committed LaTeX file corresponds to the latest committed pdf file.\footnote{In the long run, the pdf file should be re-generated during {\txt ant commit}.  Doing so would require finding a portable \LaTeX\ to pdf generator, putting it in the {\sc NextGen} lib directory, and calling it in the {\txt commit} target.}

WARNING: If you edit anything in the live directories, be sure to perform a {\txt cvs commit} so your changes are included in the CVS repository. Better yet, never edit the live directories directly. Instead, always make changes to your local copy and update the live directory.

\section{{\sc NextGen} Package Design}
\subsection{Classloader Package Design}
All classes in the {\sc NextGen} classloader are contained in a single package:
{\txt edu.rice.cs.nextgen.classloader}.
There are no subpackages. The main entry point is class {\txt Runner}.

\subsection{Compiler Package Design}
The source code for the {\sc NextGen} compiler is divided into the following packages, found in {\txt src/edu/rice/cs/nextgen/compiler}:

\begin{itemize}
\item{\txt main}. Contains the main entry point for the compiler, in class {\txt Main}, as well as supporting code. In particular, class {\txt JavaCompiler} contains the code for invoking the various phases of the compiler.

\item{\txt parser}. Contains the code for scanning and parsing {\sc NextGen} source files.

\item{\txt tree}. Contains the code defining {\sc NextGen} abstract syntax trees.

\item{\txt comp}. Contains the code for computing most phases of compilation, including symbol table entry, type checking, data flow checking, and bytecode generation. 

\item{\txt code}. Contains code for many of the datastructures utilized by the various phases of compilation. Unfortunately, there is no sharp conceptual distinction between the classes contained in this package and the classes contained in the {\txt code} package. A useful refactoring would be to move the classes in these two packages so as to define the roles of each package more precisely.

\item{\txt flatten}. Contains the visitors and support code that convert type dependent operations into snippet calls. No comparable package exists in the JSR-14 compiler. Parametric types are flattened according to the rules for {\sc NextGen} name mangling. Snippet methods are added to classes as necessary. Template classes are generated. Finally, the jump targets for {\txt break} and {\txt continue} statements are fixed after flattening.\footnote{These targets are broken by flattening because the positions of the targets are changed when snippet methods are added.}

\item{\txt instrument}. Contains the code for pretty-printing all datastructures used by the compiler. No comparable package exists in the JSR-14 compiler. We originally added this code to facilitate diagnosis of errors when modifying the datastructures during {\sc NextGen}-specific phases of compilation. It has been an invaluable tool in retrofitting unit tests over {\txt NextGen}. 

\item{\txt util}. Contains many general-purpose datastructures, including parametric versions of many Java collections classes. These collections classes were written as part of the GJ compiler before the JSR-14 compiler was available. We've modified and rewritten many of them, particularly the {\txt List} classes. Although JSR-14 provides parametric versions of the collections classes, our versions (particularly of {\txt Lists}) have many advantages over those in JSR-14, so in most cases there is little (or negative) incentive to refactor them out of the codebase. One useful feature that is currently missing from our hash tables is an iterator (however, a {\txt map} facility is provided).

\item{\txt hist}. Contains some useful DrJava interactions histories. {\txt ImportAll.hist} imports all {\txt NextGen} source packages. {\txt NextGenTestCase} sets up all variables initialized in class {\txt edu.rice.cs.nextgen.compiler.main.NextGenTestCase}. {\txt JavaCompilerTest.hist} performs the various tasks done in the {\txt imports} and {\txt setUp} method of {\txt JavaCompilerTest}, i.e., it initializes a new {\txt JavaCompiler} on a {\txt NextGen} sourcefile:
\begin{verbatim}
> package edu.rice.cs.nextgen.compiler.main;
> import edu.rice.cs.nextgen.compiler.code.*;
> import edu.rice.cs.nextgen.compiler.comp.*;
> import edu.rice.cs.nextgen.compiler.instrument.*;
> import edu.rice.cs.nextgen.compiler.util.*;
> import edu.rice.cs.nextgen.compiler.tree.*;
> import java.io.IOException;
> import junit.framework.TestCase;
> import junit.framework.TestSuite;
>
> String[] args = new String[] {
    "-classpath",System.getProperty("sun.boot.class.path"),
    "simpletests/edu/rice/cs/nextgen/simpletests/InstanceofParameter.java"
  };
> CompilerOptions options = new CompilerOptions();
> _fileNames = options.processArgs(args);
> _compiler = new JavaCompiler(options);
\end{verbatim}

Be sure to add other useful interactions histories as you build them.

\end{itemize}

\section{Unit Tests in {\sc NextGen}}
In both the compiler code and the classloader code, unit tests are contained in files ending in {\txt Test}. Each such file contains a public class that extends {\txt junit.framework.TestCase}. Although there is a significant set of working unit tests over the source code, not all code is covered directly (yet). Nevertheless, skeleton test cases are provided for all code, making it easier to add new tests. Also, the {\txt PrintableObject} class in package {\txt instrument}, and the {\txt NextGenTestCase} class in package {\txt main} make writing new unit tests easy over any part of the code base. 

\subsection{Class {\tt PrintableObject}}
{\txt PrintableObject} provides a mechanism for pretty-printing complex datastructures. By extending {\txt PrintableObject}, a class inherits all the functionality needed to pretty-print itself. All that is needed is for the extending class to override method {\txt print()} and use the inherited methods to specify how it should be printed. A {\txt PrintableObject} decides which fields of itself to print. It can also tell its constituent fields that are {\txt PrintableObjects} to print themselves selectively, passing a {\txt Filter} object to handle cyclic references.\footnote{See classes {\txt edu.rice.cs.nextgen.compiler.code.Scope} and 
{\txt edu.rice.cs.nextgen.compiler.code.Symbol.ClassSymbol} for two examples of cyclic structures printed with {\txt Filters}.}
Virtually all complex datastructures in {\sc NextGen} extend {\txt PrintableObject}. See their {\txt print} methods for examples of how to call the {\txt PrintableObject} functionality for pretty-printing.

In addition to method {\txt print}, which sends a pretty-printed representation of an object to {\txt System.out}, every {\txt PrintableObject} has a {\txt longString()} method that takes no arguments and returns a (multiline) {\txt String} representation of the object. {\txt longString()} is extremely useful when writing unit tests. Reasonable {\txt toString} methods are also written for most classes, but they contain much less detailed information. The {\txt toString} methods can be useful for quickly checking the identity of an object.

To familiarize yourself with the various datastructures used in {\sc NextGen}, it is recommended that you experiment with printing out instances of them in the DrJava interactions window while reading through their descriptions in this document. Another great way to learn how these datastructures work is by writing new unit tests over them.

\subsection{Class {\tt NextGenTestCase}}
{\txt NextGenTestCase} initializes default values for the most commonly used {\sc NextGen} datastructures, allowing you to quickly build complex datastructures in a test case. It also defines the following convenience methods:

\begin{itemize}
\item{\txt String removeWhiteSpace(String)}. This method takes a {\txt String} and returns a new {\txt String} with all whitespace removed. It's useful for checking that a multiline {\txt String} representation of an {\txt Object} is as expected (without breaking everytime that the whitespace in the representation is changed).

\item{\txt String removeNewlines(String)}. Like {\txt removeWhiteSpace}, with similar motivation, but only {\txt newlines} are removed.

\item{\txt String wrapInQuotes(String)}. Often in a test method, you will want to check that the {\txt String} representation of an object is as expected. To specify what's expected in source code, you have to wrap the {\txt String} representation inside quotes. For multiline {\txt String} representations, this task can be extremely tedious. {\txt wrapInQuotes} is a static method that takes a {\txt String} and returns a new {\txt String} with each line wrapped in quotes. This method can be conveniently called in the DrJava interactions window while constructing new test methods. In the long run, {\txt wrapInQuotes} should become functionality provided by DrJava on selected blocks of text in the editor. Until that functionality is added, this method will save you time.

\item{\txt Parser makeParser(String)}. Takes a {\txt String} representing source code and returns an instance of {\txt edu.rice.cs.nextgen.parser.Parser} to read that source code.

\item{\txt Tree.TopLevel makeClassTree(String)}. Takes a {\txt String} representing the source code  of a complete Java source file, parses it and returns an instance of {\txt Tree.TopLevel}.\footnote{For more information on {\txt Trees}, seee the section``Phases of the NextGen Compiler''.}

\item{\txt Tree.Import makeImport(String)}. Takes a {\txt String} representing an import declaration, parses it and returns an instance of {\txt Tree.Import}. 
\end{itemize}

Other {\txt make} methods should be added to this class as they become useful in the unit tests. It is recommended that all new {\sc NextGen} test case classes extend {\txt NextGenTestCase}.

\section{Phases of The {\sc NextGen} Compiler}
When class {\txt Main} is invoked with a sequence of keyword arguments and files, it stores all keyword arguments in a new {\txt CompilerOptions} object named {\txt options}, creates a new instance of {\txt JavaCompiler} named {\txt compiler}, with a field reference to {\txt options}, and calls {\txt compiler.compile()} on a {\txt List} of all source files to compile. The phases of compilation corresponding precisely to the sequence of method calls in method {\txt JavaCompiler.compile()}. Those phases are as follows.
\begin{verbatim}
      ListBox<Tree> trees = parseFiles(filenames);
      List<Environment<AnalyzerContext>> envs = enterClasses(trees);
      checkTypes(envs);
      envs = flatten(envs);
      patchSnippets();
      eraseTypes(envs);
      flattenGroundedSuperClasses();
      List<ClassSymbol> classSyms = generateByteCode(envs);
\end{verbatim}

We will now provide a high-level overview of the entire compilation process and then delve into the datastructures manipulated during each phase.

During parsing (Stage I), the initial {\txt List<String>} of filenames is converted into a {\txt List<Tree>}. Next, (Stage II), the classes and packages in this tree are entered into a {\txt SymbolTable} object, and {\txt Symbols} for various lexical items are filled into the {\txt Trees}. A {\txt List<Environment<AnalyzerContext>>} (basically the original {\txt List<Tree>} with each {\txt Tree} wrapped in an {\txt Environment}) is returned from this phase. The {\txt List<Environment<AnalyzerContext>>} is named {\txt envs} and is the primary datastructure passed through subsequent phases. 

After symbols are entered, {\txt envs} is type checked (Stage III). The type of each {\txt Tree} is recorded in a field in the {\txt Tree} . After type-checking comes {\sc NextGen}-specific processing. Type names are flattened, snippets are added and template classes and interfaces are generated as static nested classes in the corresponding base class (Stage IV). Afterward, various source-position-specific targets must be patched in the base class (Stage V), since the locations of items will move after adding snippet methods.

After snippets are patched, types are erased, as in GJ (Stage VI).\footnote{Notice that flattened types won't be erased, as they are no longer parametric.} Then the superclasses of grounded types are flattened (Stage VII). \footnote{This part of flattening must be deferred because Stage IV depends on the unflattened representation.  In addition, Stage II as currently written depends on this deferral because it tests whether or not the superclass is  parametric and ground to determine whether the supercall for a constructor must be modified.} Finally, bytecode is generated from {\txt envs} (Stage VIII) and returned as a {\txt List<ClassSymbol>}. These {\txt ClassSymbols} are then written out to disk to form the corresponding classfiles. 

Notice that not all stages take all datastructures they depend on as arguments. In particular, {\txt patchSnippets} and {\txt flattenGroundedSuperClasses} do not take {\txt envs} as an argument. They operate on {\txt envs} via field references set to it. Obviously, this situation is undesirable; an important refactoring is to finish decoupling all field references to {\txt envs} and to always pass it as an argument.\footnote{Originally, there were many other phases that kept field references to {\txt envs}. The remaining phases are the most difficult to refactor.}

Every major phase of compilation after parsing\footnote{Snippet patching is not performed by a visitor because the targets to fix are accumulated during type flattening. Class {\txt SnippetPatcher} simply walks over the accumulated list.} is implemented as a walk over the parsed {\txt Trees}. Consequently, each phase is associated with a subclass of class {\txt Tree.Visitor}. For example, symbol entry is handled by visitor {\txt SymbolEnterer}. Static checking is handled primarily by visitor {\txt StaticAnalyzer}, which is assisted by visitor {\txt TypeChecker}.  Flattening of parametric type references is handled by visitor {\txt TypeFlattener}. Type erasure is handled by visitor {\txt TypeEraser}\footnote{{\txt TypeEraser} is a subtype of {\txt TreeTranslator}, which is a subtype of {\txt Tree.Visitor}.} Code generation is handled by visitor {\txt CodeGenerator}. 
We will now examine the various datastructures manipulated by these phases. We will start with {\txt Trees} because the first internal representation of the source code constructed is a {\txt List<Tree>}, and all other datastructures built depend on them.

\subsection{Trees}
\begin{figure*}[thb]
\begin{verbatim}
 Tree ::= TopLevel | Import | ClassDef | MethodDef | VarDef | Block
        | DoLoop | WhileLoop | ForLoop | Labelled | Switch | Case
        | Synchronized | Try | Catch | Conditional | Exec | Break
        | Continue | Return | Throw | Apply | NewInstance | NewArray
        | Assign | Assignop | Operation | TypeCast | TypeTest
        | Indexed | Select | Ident | Literal | TypeIdent | TypeArray
        | TypeApply | TypeParameter | Erroneous
\end{verbatim}
\label{ast}
\caption{Abstract Syntax Trees}
\end{figure*}

{\txt Trees} in {\sc NextGen} represent abstract syntax trees. {\txt Trees} form a composite class hierarchy rooted at class {\txt edu.rice.cs.nextgen.compiler.tree.Tree}. All subclasses in this composite hierarchy are static nested classes in class {\txt Tree}.  Every syntactic construct in {\sc NextGen} corresponds to a subclass of class {\txt Tree}. For example, source files are parsed to {\txt TopLevels} and class definitions are parsed to {\txt ClassDefs}. The entire composite hierarchy is represented in BNF notation in Figure \ref{ast}.

\subsection{Trees and PrintableObjects}
{\txt Trees} are a subclass of class {\txt edu.rice.cs.nextgen.compiler.instrument.PrintableObject}, allowing them to be pretty-printed easily in the DrJava interactions pane. For example, suppose we want to pretty-print the {\txt Tree} for this simple {\sc NextGen} source file:
\begin{verbatim}
package example;
public class C<T> {}
\end{verbatim}
We can print it in the DrJava interactions window as follows:

\begin{verbatim}
> package edu.rice.cs.nextgen.compiler.main;

> NextGenTestCase.makeClassTree(
     "package example; \n" +
     "public class C<T> { } \n"
   ).longString() 
\end{verbatim}
Resulting in:
\begin{verbatim}
"{TopLevel for null
  packageId: {Ident example} packageSymbol: null
  starImportScope (except for java.lang): null
  namedImportScope: null
  ==========
  {ClassDef C<{TypeParameter T extends null implements null}> extends null implements () 
    flags: 1
    null}}
"
\end{verbatim}
This result is a pretty-printed representation of a {\txt Tree.TopLevel}. The first line indicates the source file corresponding to the {\txt TopLevel}. In this case it is  {\txt null} because this {\txt TopLevel} was parsed directly from a {\txt String} instead of a file.  If the {\txt TopLevel} were constructed from a file {\txt f}, the first line would read {\txt TopLevel for f}. The fields printed represent the package, the imports, and the list of {\txt ClassDefs}. Notice the use of {\txt null} values as defaults for many fields. 

Underneath the horizontal bar are listed the constituent class definitions in the source file. The pretty-printed {\txt ClassDef} follows the structure of the original source code. The {\txt flags} field of a {\txt ClassDef} is an {\txt int} that stores various attributes of the class, such as the included visibility modifiers. Underneath the header of the {\txt ClassDef} is its contained {\txt ClassSymbol}, initialized to {\txt null} and filled in during symbol entry.

If class {\txt C} contained any members, the {\txt Trees} for those members would be printed out underneath the {\txt ClassSymbol}. For example, below is the source for acceptance test {\txt ReturnIntegerTest}:
\begin{verbatim}
package edu.rice.cs.nextgen.simpletests;

class C<T> {
  Object m(Integer i) {
    return i;
  }
}
\end{verbatim}
This source will parse to
\begin{verbatim}
{TopLevel for simpletests/edu/rice/cs/nextgen/simpletests/ReturnIntegerTest.java
  packageId: {Select {Select {Select {Select {Ident edu}.rice}.cs}.nextgen}.simpletests} 
  packageSymbol: null
  starImportScope (except for java.lang): null
  namedImportScope: null
  ==========
  {ClassDef C<{TypeParameter T extends null implements null}> extends null implements () 
    flags: 0
    null
    {MethodDef <> {Ident Object} m({VarDef {Ident Integer} i}) throws  flags: 0
      null
      {Block {Return {Ident i}}}}}}
\end{verbatim}
The headers of method definitions include the type parameters (between angle brackets), the return type, name, parameter types, {\txt throws} clause, and the visibility flags. Beneath the header is a {\txt MethodSymbol} (filled in during symbol entry). Finally, beneath the {\txt MethodSymbol} is the parsed body of the method.

The generated bytecodes of a method are stored in a {\txt MethodSymbol}. After bytecode generation, the printed {\txt MethodSymbol} will display these bytecodes. For example, here is the same {\txt TopLevel} as above after all phases including bytecode generation:
\begin{verbatim}
 {TopLevel for simpletests/edu/rice/cs/nextgen/simpletests/ReturnIntegerTest.java
    packageId: {Select {Select {Select {Select {Ident edu}.rice}.cs}.nextgen}.simpletests} 
    packageSymbol: [PackageSymbol edu.rice.cs.nextgen.simpletests]
    starImportScope (except for java.lang): null
    namedImportScope: 
      [Scope: [ClassSymbol  fullname: edu.rice.cs.nextgen.simpletests.C  
         flatname: edu.rice.cs.nextgen.simpletests.C flags: 1024
         members (cyclic references have been filtered):
               [Scope: [MethodSymbol m
                                  [Code: aload_1; -80; ]]
                              [MethodSymbol <init>
                                  [Code: aload_0; -73; nop; aconst_null; -79; ]]]]]
    ==========
    {ClassDef C<{TypeParameter T extends null implements null}> extends null implements () 
      flags: 0
      [ClassSymbol  fullname: edu.rice.cs.nextgen.simpletests.C  
        flatname: edu.rice.cs.nextgen.simpletests.C flags: 1024
        members (cyclic references have been filtered):
        [Scope: [MethodSymbol m
                         [Code: aload_1; -80; ]]
                       [MethodSymbol <init>
                         [Code: aload_0; -73; nop; aconst_null; -79; ]]]]
       {MethodDef <> null <init>() throws  flags: 0
         [MethodSymbol <init>
           [Code: aload_0; -73; nop; aconst_null; -79; ]]
         {Block {ExpressionStatement {Apply {Ident super}()}}}}
       {MethodDef <> {Ident Object} m({VarDef {Ident Integer} i}) throws  flags: 0
         [MethodSymbol m
           [Code: aload_1; -80; ]]
         {Block {Return {Ident i}}}}}}
\end{verbatim}
{\txt MethodSymbols} inside {\txt ClassSymbols} contain bytecode, as well as the the  {\txt MethodSymbols} attached to {\txt MethodDefs} in {\txt Trees} (which are actually the same as ({\txt ==} to) the {\txt Symbols} contained in the {\txt ClassSymbol}. Incidentally, notice that a default constructor has been added to class {\txt C}. 
\subsection{Environments}

A {\txt List<Environment<AnalyzerContext>>} is returned from Stage II. An {\txt Environment} is a structure associated with a {\txt Tree}; each {\txt Environment} contains its associated {\txt Tree} as a field. The {\txt List} returned from Stage II contains one environment for each {\txt Tree} in the {\txt List<Tree>} passed to it.

In addition to referencing its associated {\txt Tree}, each  {\txt Environment} contains a reference to its enclosing {\txt Environment}. For example, if an {\txt Environment} \(E\) is associated with an immediate subtree \(T\) of a enclosing {\txt Tree} \(T'\), and {\txt Environment} \(E'\) is associated with \(T'\), then \(E\) contains a reference to \(E'\).  Each element of the  {\txt List<Environment<AnalyzerContext>>} resulting from the parsing phase of compilation is associated with a {\txt TopLevel} representing a file in the original list of filenames. Contained {\txt Environments} can be constructed from enclosing {\txt Environments} by method {\txt spawn(Tree)}.

Environments store information relevant to their associated {\txt Tree}.  They are used during two phases of compilation: static analysis and code generation.  The information stored during these two phases is significantly different. In order to decouple the general-purpose functionality of {\txt Environments} from the code for storing the information relevant to a particular usage, {\txt Environments} are parameterized by a type parameter {\txt A}. A field {\txt context} of type {\txt A} contains the information stored at each level of an {\txt Environment}. So, during static analysis, we make use of a {\txt List<Environment<AnalyzerContext>>} where each {\txt Environment<AnalyzerContext>} in the {\txt List} contains a {\txt context} field of type {\txt AnalyzerContext}. 

\subsection{AnalyzerContexts}
{\txt AnalyzerContexts} contain many fields relevant to static analysis, but most importantly they contain the following three fields:

\begin{enumerate}
\item An {\txt expectedType} field of type {\txt Type}. {\txt Types} represent the results of static checking. This field is initialized to {\txt NoType.ONLY} and filled in during static checking.
\item An {\txt expectedKind} field of type {\txt int}. {\txt Kinds} are very high-level descriptions of the expected syntactic structure of a {\txt Tree} that are filled in during static checking. The possible {\txt Kinds} of a {\txt Tree} are as follows: {\txt NO\_KIND}, {\txt PACKAGE\_KIND}, {\txt TYPE\_KIND}, {\txt VAR\_KIND}, {\txt VAL\_OR\_VAR\_KIND}, {\txt METHOD\_KIND}, {\txt ALL\_KINDS}.  Each {\txt Kind} is represented as an {\txt int} in interface {\txt edu.rice.cs.nextgen.compiler.code.Kinds}.\footnote{Representing a dataset of atomic elements as {\txt int} fields in an interface is an common idiom in {\sc NextGen}, inherited from  the {\txt GJ} compiler. This idiom is a workaround for the lack of enumeration types in Java. By ``implementing'' an interface corresponding to a dataset, a class can refer to all of the elements of the dataset directly. Also, a class can iterate over the elements of the dataset with a simple {\txt int} counter in a {\txt for} loop. One serious disadvantage of this idiom is that values of the dataset must be deciphered when they're printed out in an error message. Also, proper data abstraction is not enforced; there is nothing to prevent us from using an element of a dataset in a nonsensical arithmetic operation.}
The {\txt expectedKind} of an {\txt AnalyzerContext} is initialized to {\txt NO\_KIND} and filled in by subsequent analysis.
\item A {\txt Scope}. Conceptually, {\txt Scopes} are lists of identifiers introduced in a lexical context. We now turn our attention to their internal structure.

\end{enumerate}

\subsection{Scopes and Entries}
Each {\txt Scope} is owned by a {\txt Symbol} corresponding to the lexical environment the {\txt Scope} represents. For example, a {\txt Scope} corresponding to fields in a class would be owned by the associated {\txt ClassSymbol}. 
The first identifier appearing in a {\txt Scope} is stored in an {\txt Entry}. Each {\txt Entry} contains a {\txt Symbol} and a reference to a {\txt sibling} in the {\txt Scope}. So, we can iterate over the {\txt Entries} in a {\txt Scope} by starting with the contained {\txt Entry} and following the {\txt sibling} links. The final {\txt Entry} contains {\txt null} as its {\txt sibling}.\footnote{Obviously, {\txt Scopes} and {\txt Entries} are rich with opportunities for refactoring. Because they represent list-like structures, it would be better to make them either subtypes of type {\txt List}, or containers, each with a field of type  {\txt List}.}

Each {\txt Entry} also refers to the {\txt Entry} it shadows in an enclosing {\txt Scope}. The shadowed {\txt Entry} is contained in field {\txt shadowed}. 

New {\txt Symbols} may be destructively added to a {\txt Scope} with method {\txt addSymbol}. {\txt Entries} in a {\txt Scope} may be accessed with method {\txt lookup} that takes a {\txt Name} and returns the {\txt Entry} in that {\txt Scope} corresponding to the given {\txt Name}. {\txt Names} are identifiers; they can be constructed from {\txt Strings} with the static method {\txt Name.fromString(String)}. For more information on {\txt Names}, see their unit tests in package {\txt edu.rice.cs.nextgen.util}.  For convenience, {\txt lookup} is overridden with a method that takes a {\txt String} and converts it to a {\txt Name}.
 
Each {\txt Scope} refes to its enclosing {\txt Scope}, in field {\txt nextScope}. Consequently, {\txt Scopes} mirror the structure of the {\txt Environments} they're associated with.\footnote{This mirrored structure is undesirable because it can result in ``Rogue Data'' where one of the two structures is modified but the other is not. A potential refactoring would be to eliminate the {\txt nextScope} field and replace it with a method that accesses the scope contained in the enclosing {\txt Environment}.}

\subsubsection{Environments and Scopes as PrintableObjects}
Like {\txt Trees}, {\txt Environments} and their constituents can be printed to examine their contents. For example, here is a call on {\txt longString()} of an empty {\txt Scope} (constructed from a default {\txt ClassSymbol} available in {\txt NextGenTestCase}):
\begin{verbatim}
> new Scope(NextGenTestCase.CLASS_SYMBOL).longString()
[Scope: ]
\end{verbatim}
Using {\txt addSymbol} and {\txt lookup}, we can build and examine {\txt Scopes} in the DrJava interactions window:
\begin{verbatim}
> s = new Scope(NextGenTestCase.CLASS_SYMBOL)
edu.rice.cs.nextgen.compiler.code.Scope@7dfcf1
> s.addSymbol(NextGenTestCase.METHOD_SYMBOL);
> s.lookup("METHOD_SYMBOL")
edu.rice.cs.nextgen.compiler.code.Scope$Entry@7abaab
> s.lookup("METHOD_SYMBOL").longString()

"[MethodSymbol METHOD_SYMBOL]
"
\end{verbatim}
We can also build and print {\txt Environments}\footnote{Raw types are used in this example because, at the time of this writing, the DrJava interactions window does not yet support generic types. In some unit tests where the context is unimportant, {\txt Environments} are instantiated as {\txt Environment<VoidContext>}. Class {\txt VoidContext} is never used outside the unit tests.}:
\begin{verbatim}
> new Environment(null, null)
edu.rice.cs.nextgen.compiler.comp.Environment@53be7c
> new Environment(null, null).longString()

"[Environment 
  null
  null]
"
\end{verbatim}
The two arguments to the constructor are the associated {\txt Tree} and the associated context. Likewise, the {\txt longString} representations of {\txt Environments} include the associated context and tree. Here is a more complex example:
\begin{verbatim}
> Tree.TopLevel simpleTree = NextGenTestCase.makeClassTree("public class C {}");
  Environment env = new Environment(simpleTree, null);
> env.longString()

"[Environment 
  null
  {TopLevel for null
    packageId: null packageSymbol: null
    starImportScope (except for java.lang): null
    namedImportScope: null
    ==========
    {ClassDef C<> extends null implements () flags: 1
      null
      }}]
"
\end{verbatim}
{\txt Environments} can be spawned from other {\txt Environments} as follows:
\begin{verbatim}
> e1 = new Environment(null, null);
> e2 = e1.spawn(null);
\end{verbatim}
When printed, spawned {\txt Environments} first print out their own contents, and then print the contents of their enclosing {\txt Environment}:
\begin{verbatim}
> e2.longString()

"[Environment 
  null
  null]
[Environment 
  null
  null]
"
\end{verbatim}
Of course, we can also spawn {\txt Environments} containing non-null {\txt Trees}:
\begin{verbatim}
> Tree.TopLevel innerTree = NextGenTestCase.makeClassTree("public class C {}");
  Environment innerEnv = new Environment(innerTree, null);
  Tree.TopLevel outerTree = NextGenTestCase.makeClassTree("public class D {}");
  Environment outerEnv = innerEnv.spawn(outerTree);
> outerEnv.longString()

"[Environment 
  null
  {TopLevel for null
    packageId: null packageSymbol: null
    starImportScope (except for java.lang): null
    namedImportScope: null
    ==========
    {ClassDef D<> extends null implements () flags: 1
      null
      }}]
[Environment 
  null
  {TopLevel for null
    packageId: null packageSymbol: null
    starImportScope (except for java.lang): null
    namedImportScope: null
    ==========
    {ClassDef C<> extends null implements () flags: 1
      null
      }}]
"
\end{verbatim}
Notice that the original {\txt Environment} is unaffected by the spawn.

\subsection{Symbols}
{\txt Symbols} are containers for identifiers. They also hold relevant information such as the bytecode generated for an identifier. The various types of {\txt Symbols} form a composite class hierarchy rooted at class {\txt Symbol}. All subclasses are static nested classes of class {\txt Symbol}. The composite hierarchy is represented in BNF notation in Figure \ref{symbols}.\footnote{Notice that concrete class {\txt TypeSymbol} forms the root of a composite subhierarchy, and also represents naked type parameters! An important refactoring would be to make {\txt TypeSymbol} abstract and add a new subclass for naked type parameters.}
\begin{figure*}[thb]
\begin{verbatim}
Symbol ::=  TypeSymbol | VarSymbol | MethodSymbol | OperatorSymbol
TypeSymbol ::= (type variable) TypeSymbol | ClassSymbol | PackageSymbol
\end{verbatim}
\label{symbols}
\caption{Symbols}
\end{figure*}
Each {\txt ClassSymbol} contains a {\txt Scope} of its members. Because each method's bytecode is stored in its corresponding {\txt MethodSymbol}, and because the {\txt Scope} of a {\txt ClassSymbol} contains all {\txt Symbols} for methods (and other members) appearing in a class, all of the information needed to write out a classfile for a given class can be accessed in the class's {\txt ClassSymbol} after bytecode generation.

\subsection{SymbolTables and ClassReaders}
During Phase II, a {\txt SymbolTable} is constructed and kept as a field in {\txt JavaCompiler} for use in subsequent phases. A {\txt SymbolTable} contains a field {\txt classReader} (of type {\txt ClassReader}) that stores all constituent symbols. {\txt ClassReaders} store their symbols in two {\txt Hashtables}: one mapping package names to their corresponding {\txt PackageSymbols}, and one mapping class names to their {\txt ClassSymbols}. In addition to all classes explicitly referred to in a program, {\txt SymbolTables} include all classes in {\txt java.lang}. They also contain mappings for all Java infix operators. Because the  {\txt ClassSymbols} in  {\txt java.lang} and the infix operators are the same for all {\txt SymbolTables}, they are omitted from the {\txt longString} representation. To see precisely what is entered during {\txt SymbolTable} initialization, refer to the source file {\txt edu.rice.cs.nextgen.compiler.comp.SymbolTable.java}.

In the DrJava interactions session below, we create a new {\txt SymbolTable} corresponding to  {\txt NextGen} acceptance test {\txt InstanceofParameter.java}. The text of that test is:
\begin{verbatim}
package edu.rice.cs.nextgen.simpletests;
 
public class InstanceOfParameter<T> {
  public boolean is(Object o) {
    boolean ret = o instanceof T;
    return ret;
  }
}
\end{verbatim}
Here is the interactions session:\\
\\
{\tt > {\it load JavaCompilerTestSetup.hist}}
\begin{verbatim}
> trees = _compiler.parseFiles(_fileNames);
> envs = _compiler.enterClasses(trees);
> _compiler.getSymbolTable().longString()

"[SymbolTable
  packages: 
      edu.rice.cs.nextgen => [PackageSymbol edu.rice.cs.nextgen]
      edu.rice => [PackageSymbol edu.rice]
      edu.rice.cs.nextgen.simpletests => 
        [PackageSymbol edu.rice.cs.nextgen.simpletests]
      edu.rice.cs => [PackageSymbol edu.rice.cs]
      edu => [PackageSymbol edu]
            
  classes: edu.rice.cs.nextgen.simpletests.InstanceOfParameter => 
    [ClassSymbol  fullname: edu.rice.cs.nextgen.simpletests.InstanceOfParameter
        flatname: edu.rice.cs.nextgen.simpletests.InstanceOfParameter flags: 4194305
        members (cyclic references have been filtered):
           [Scope: [MethodSymbol is]
                          [MethodSymbol <init>]]]
           ]

"
\end{verbatim}

\subsection{CodeGenerators, GenContexts, and ClassWriters}
Class {\txt JavaCompiler} drives class generation by first using a {\txt CodeGenerator} visitor to write bytecode to a {\txt ClassSymbol}, and then passing that {\txt ClassSymbol} to method
{\txt ClassWriter.writeClassFile()}, on an instance of {\txt ClassWriter} stored in the {\txt SymbolTable}. 

When generating bytecode for a given {\txt Tree}, {\txt CodeGenerators} keep information for each subtree in an {\txt Environment<GenContext>}. Class {\txt GenContext} is a non-public class, written in source file {\txt CodeGenerator.java}, that stores the following information for each subtree:
\begin{enumerate}
\item The {\txt expectedType} of the subtree (a {\txt Type}).
\item All unresolved {\txt exitingJumps} out of the code represented by the subtree, represented as aa {\txt Chain}. {\txt Chains} are described below.
\item All unresolved {\txt continuingJumps} to the code represented by the subtree, also represented as a {\txt Chain}.
\end{enumerate}

Class {\txt Chain} is a static nested class of class {\txt Code} (contained in source file {\txt Code.java}).\footnote{Instances of {\txt Code} represent all information that goes into a code attribute in a classfile.} Conceptually, {\txt Chains} are lists of jumps. Each {\txt Chain} contains three fields:
\begin{enumerate}
\item The {\txt next} {\txt Chain} in the list.
\item {\txt pc} (an {\txt int}). This field represents the position of the jump instruction.
\item {\txt stackSize} (an {\txt int}). The stack size after the jump instruction.\footnote{When the locations of jumps are resolved, the compiler ensures as a sanity check that the {\txt stackSize} non-negative in each block of code. In an old (unreleased) version of the {\txt NextGen} compiler, jump targets were resolved incorrectly because snippet methods moved the locations of all code in a parametric class. As a result, the sanity check on {\txt stackSizes} would fail during compilation of some classes.}
\end{enumerate}
An important invariant of a chain is that all elements of the chain list have the same {\txt stackSize}.

\subsubsection{Writing to Disk}
Once all bytecode has been generated and stored in the {\txt ClassSymbols}, {\txt ClassWriters} are responsible for writing class files to disk. The {\txt ClassSymbols} to be written are not stored in class {\txt ClassWriter}. Instead, each class component is passed as an argument to the appropriate method, and written to a file.

\section{Conclusion}
We have attempted to provide a high-level roadmap of the {\txt NextGen} code base, capturing enough detail that the reader possesses an accurate understanding of the architecture, while keeping the discussion at a level high enough that there is an advantage to reading this document as opposed to simply perusing the code base. Consequently, there are many details of various stages of compilation that have been omitted. The reader is encouraged to bolster his understanding of the code base through interactive exploration in the DrJava interactions window and through adding unit tests. Additionally, an IDE such as CodeGuide that allows one to quickly navigate from uses of identifiers to definitions of identifiers, and that provides support for automated refactoring of code, can be extremely helpful when working with this code base.

The source for this document is contained in the NextGen code repository, in the {\txt doc} directory. Readers are strongly encouraged to update and improve this document while using it to learn the code base. New readers are in a particularly good position to assess the clarity and usefulness of this document. By improving it, you will help future generations of {\sc NextGen} programmers to understand {\sc NextGen} more quickly, just as this document has helped you to do so.

\begin{thebibliography}{bib}

\bibitem{Agesen} O. Agesen, S.. Freund and J. Mitchell.  Adding Type
Parameterization to the Java Language. In OOPLSA'97.

\bibitem{Theory} D. Ancona and E. Zucca. A Theory of Mixin Modules: Basic 
and Derived Operators. Mathematical Structures in Computer Science, 
8(4):401--446, 1998.

\bibitem{MixGen} E. Allen, J. Bannet, R. Cartwright. 
{First-class Genericity for Java}.
Submitted to ECOOP 2003.

\bibitem{SoundMixGen} E. Allen, J. Bannet, R. Cartwright. {Mixins in 
Generic Java are Sound}.
Technical Report, Computer Science Department, Rice University,
December 2002.

\bibitem{EfficientNextGen} E. Allen, R. Cartwright, B. Stoler. {Efficient 
Implementation of Run-time Generic Types for Java}. IFIP WG2.1 Working 
Conference on Generic Programming, July 2002.

\bibitem{CaseForNextGen} E. Allen, R. Cartwright.{The Case for 
Run-time Types in Generic Java}. Principles and Practice of Programming 
in Java, June 2002.

\bibitem{Jam}D. Ancona, G.Lagorio, E.Zucca. {JAM-A Smooth Extension 
of Java with Mixins}. ECOOP 00, LNCS, Spring Verlag, 2000.

\bibitem{Bloch and Gafter}J. Bloch, N. Gafter. Personal communication.

\bibitem{NextGen} 
R. Cartwright, G. Steele. {Compatible Genericity with Run-time Types
for the Java Programming Language}.  In {\it OOPSLA '98\/}, October
1998.

\bibitem{GJ}
G. Bracha, M. Odersky, D. Stoutamire, P. Wadler. {Making the Future
Safe for the Past: Adding Genericity to the Java Programming
Language}. In {\it OOPSLA '98}, October 1998.

\bibitem{MatthiasMixin}
M. Flatt, S. Krishnamurthi, M. Felleisen. {A Programmer's Reduction
Semantics for Classes and Mixins}. Formal Syntax and Semantics of
Java, volume 1523, June 1999.

\bibitem{Pizza} Martin Odersky and Philip Wadler.
{Pizza into Java: Translating Theory into Practice}. In 
{\it POPL 1997}, January 1997, 146--159.

\bibitem{JSR14}
Sun Microsystems, Inc. {JSR 14: Add Generic Types To The Java
Programming Language}.  Available at {\txt
http://www.jcp.org/jsr/detail/14.jsp}.

\end{thebibliography}
\end{document}
