% CS444 Assignment 2,3,4
% Kevin Suwala, Kyle Verhoog
%
Location: src/main/scala/compiler/joos1w/environment
We broke environment building into 7 different classes of environment:
- Generic environment: is the parent class for all environments and includes logic for handling classes, methods and variables. It provides lookup methods for each of these.
- Root environment: is a singleton used to represent the global namespace. This is used for resolving packages.
- Package environment: is used to represent a package. This stores class and interface related information.
- Class environment: is used to represent methods and fields for a given
class. The class environment also does the
contains
,nodecl
,inherit
,super
, etc classes. - Method environment: just holds the method metadata.
- Variable environment: an environment containing a variable along with metadata about the variable.
- Block environment: this represents
{ }
.
For the first pass through the AST we generate package, class and variable environments. These environments are attached to their corresponding AST node so that type checking can be performed later. For example, a variable AST node will have reference to the enclosing environment it is in. In this pass we do checks including the following:
- check duplicate class/method declarations
- duplicate variable declarations
In this pass we check that types exist and all qualified names resolve to a
class or interface. Here the contains
, super
, etc. sets are generated and
used. Essentially all checks are done in this pass. We perform, among others,
the following checks:
- import priorities
- verify return types for methods exist
- no cycles exist in hierarchies
- no collisions in imports
- class doesn't extend a final class
The way we formatted if
statements in our AST turned out to be problematic
when generating environments. They were structured in such a way that if there
was a secondary branch in the if statement, whether it be an else-if
or an
else
branch, the node of the secondary branch would be attached as a child
of the first if
statement. For environment building it would have been much
more ideal if the additional branches were siblings in the tree gathered under
a common parent node.
To fix this we added a really nasty hack to rearrange the AST to have the desired form.
Location: src/main/scala/compiler/joos1w/types
All type-checking is done in a single pass through the AST following the environment building, type-linking and hierarchy building done in A2.
So for each Java type we define, in turn, our own classes representing each of these types. We have the following classes
AbstractType
: parent of all following typesPrimitiveType
: parent class for primitive types likeint
,boolean
,char
, etc.IntType
: represents a Javaint
BooleanType
: represents a Javaboolean
StringType
:java.lang.String
ArrayType
: wraps a givenAbstractType
and represents this type as an arrayCustomType
: represents user-defined classes and interfaces
Special cases like numeric types are defined in AbstractType
and overridden
in child classes like IntType
to specify that they are numeric.
We just followed the rules as described in class for field and method invocations. The rules as defined by the Java Language Specification for these accesses are checked. For example, when a protected field is used it must be checked that the enclosing class is a subclass of the class that declares the field or that the enclosing class is in the same package.
Type checking is done in a single pass through the AST. We use the references
assigned to the AST nodes linking them with their environment to get type
information. A method determineType
is used to evaluate the type of a given
AST node. This method pattern matches and performs, recursively, the type
lookup, while also performing verification on the type. So, for example,
determineType(assignmentAST)
will recursively look up the type of the left
and right hand sides of the assignment and verify that the types are legal to
be assigned. Legal meaning that they obey the type rules for inheritance.
Location: src/main/scala/compiler/joos1w/Joos1WReachability
Relevant methods:
reachableCheck
: recurses down to method bodies to get to statements.statementReachableCheck
: evaluates statement-by-statement the reachability
Reachability is checked in a top-down traversal of the AST. The in
information
is propagated downwards through the recursion. The rules are checked for if
,
if-else
, while
and for
statements.
Since Joos1W does not support finals, constant expression checking is quite straightforward. In fact, here is (most) of the code that performs the evaluation:
def evalGeneralExpression(expr: AST): Any = {
expr match {
case _: ConditionalExpression | _: MethodInvocation | _: Name => None
case expr: literals.IntegerLiteral => Some(expr.integerValue)
case expr: literals.BooleanLiteral => Some(expr.value)
// ...
case expr: UnaryExpression =>
expr.operator match {
case "!" =>
evalGeneralExpression(expr.subExpression) match {
case Some(b: Boolean) => !b
}
}
}
}
def evalConstantExpression(expr: AST): Option[Boolean] = {
expr match {
case expr: ConditionalExpression =>
val l = evalGeneralExpression(expr.firstExpr)
val r = evalGeneralExpression(expr.secondExpr)
(l, expr.operator, r) match {
// == operator
case (Some(i: Int), "==", Some(j: Int)) => Some(i == j)
case (Some(i: Boolean), "==", Some(j: Boolean)) => Some(i == j)
// ...
// != operator
case (Some(i: Int), "!=", Some(j: Int)) => Some(i != j)
case (Some(i: Boolean), "!=", Some(j: Boolean)) => Some(i != j)
// ...
case (Some(i: Boolean), "||", Some(j: Boolean)) => Some(i || j)
case (Some(i: Boolean), "&&", Some(j: Boolean)) => Some(i && j)
// > operator
case (Some(i: Int), ">", Some(j: Int)) => Some(i > j)
case (Some(i: Char), ">", Some(j: Char)) => Some(i > j)
// < operator
case (Some(i: Int), "<", Some(j: Int)) => Some(i < j)
case (Some(i: Char), "<", Some(j: Char)) => Some(i < j)
case _ => None
}
case _: Name | _: MethodInvocation => None
case _ =>
evalGeneralExpression(expr) match {
case Some(b: Boolean) => Some(b)
case None => throw new RuntimeException(s"$expr")
}
}
}
Again, with Joos1W restrictions, definite assignment is rather straightforward. All that needs to be checked is that a variable is initialized when declared, ensuring that the initializer does not include the variable itself. To ensure that an initializer does not include the variable itself, the environment references attached to AST nodes during the environment building phase are used to lookup whether each name that matches the name of the declared variable is previously defined in the environment, else we raise an exception.
We perform this check in the same AST traversal as the reachability checks.
Location: src/test/scala/joos1w
For each phase we attempted to write unit tests but were unable to rigorously test our code due to time limitations and software design choices. The few unit tests we have are in
When pressed for time we resorted to using our own Marmoset test runners
located in src/test/scala/joos1w/MarmosetTestRunner.scala
.
Overall we have struggled with being able to parallelize tasks amongst ourselves. It has been difficult to get a grasp on all the pieces required for an assignment and then divvy them up.
For similar reasons that made work division difficult, it has also been difficult to maintain code quality for the different phases.
We have tried to quickly go back and rewrite pieces of the compiler after better understanding the problems but have been faced with a shortage of time.