dOvs 2010

The part of the compiler covered by this assignment deals with disambiguation of names, linking of the uses of local variables, fields, methods and constructors to their definitions, finding the types of all expressions, checking that the program is type correct and performing various normalising transformations on the AST. It encompasses the two phases Disambiguation and TypeChecking. You must hand in two files disambiguation.ml and typechecking.ml that extend the skeleton. Throughout this text, the term local variable covers both of the terms local variable and parameter as used in the JLS.

Field and method lookup in these phases is done using the lookup_field and lookup_method functions provided by the Hierarchy phase.

Constructor lookup is done by traversing the list of class members and only looking at constructors.

The rules for method and constructor overloading are very different for Joos 1 and Joos 2.

Joos 1: The declared types of the method or constructor have to match exactly the static types of the argument expressions.
Joos 2: Closest-match overloading as described in Section 15.12.2 of the JLS.

Any strategy in the spectrum between these two is acceptable. That is, anything that accepts all legal Joos 1 programs and rejects any program that is not a legal Joos 2 program is fine.

Disambiguation

The Disambiguation phase performs disambiguation of all ambiguous names and invokes.

Transformations

Transform every EAst.AmbiguousName node into one of the following compounds:
- A local variable access (DAst.Local) enclosed in zero or more non-static field accesses (DAst.NonstaticField).
- A non-static field access (DAst.NonstaticField) with this (DAst.This) as base enclosed in zero or more non-static field accesses (DAst.NonstaticField).
- (Joos 2) A static field access (DAst.StaticField) with the current class as base type enclosed in zero or more non-static field accesses (DAst.NonstaticField).
- A static field access (DAst.StaticField) with a base type resolved from a prefix of the ambiguous name enclosed in zero or more non-static field accesses (DAst.NonstaticField).
Transform every EAst.AmbiguousInvoke node into one of the following compounds:
- A non-static method invocation (DAst.NonstaticInvoke) whose receiver is a local variable access (DAst.Local) enclosed in zero or more non-static field accesses (DAst.NonstaticField).
- A non-static method invocation (DAst.NonstaticInvoke) whose receiver is a non-static field access (DAst.NonstaticField) with this (DAst.This) as base enclosed in zero or more non-static field accesses (DAst.NonstaticField).
- (Joos 2) A non-static method invocation (DAst.NonstaticInvoke) whose receiver is a static field access (DAst.StaticField) with the current class as base type enclosed in zero or more non-static field accesses (DAst.NonstaticField).
- A non-static method invocation (DAst.NonstaticInvoke) whose receiver is a static field access (DAst.StaticField) with a base type resolved from a prefix of the name child of the invoke node enclosed in zero or more non-static field accesses (DAst.NonstaticField).
- A static method invocation (DAst.StaticInvoke) with a base type resolved from the name child of the invoke node.

The disambiguation process is described in Section 6.5.2 of the JLS. The recipe of how this is done in a Joos compiler is described on slides 43, 44 and 45 of the Scopes and Environments lecture.

Checks

Check that all ambiguous names and invokes can be disambiguated properly, i.e.:

If the first identifier of the name disambiguates into a local variable access, then a local variable with that name must be in scope at that point in the program. Beware that a local variable is not in scope before its declaration, even though it might be present in the local variable environment of the current block.
If the first identifier of the name disambiguates into a non-static field access, then a non-static field with that name must be in scope in the class containing the access.
If the first identifier of the name disambiguates into a static field access, then either
(Joos 1) implicit this class for static field access is not allowed (check_joos1_implicit_this_class_static_field)
or (Joos 2) a static field with that name must be in scope in the class containing the access.
If none of the disambiguation rules apply, then an error message must be produced. (Use error_variable_not_found for field accesses and error_variable_or_type_not_found for invocations)

Subsequent fields accesses and method invokes are not checked at this point.

Furthermore, this phase must check for illegal forward references:

The initializer for a non-static field must not refer by simple name to itself or a non-static field declared later in the same class, except as the direct left-hand side of an assignment. (error_illegal_forward_field_reference)
(Joos 2) The initializer for a static field must not refer by simple name to itself or a static field declared later in the same class, except as the direct left-hand side of an assignment. (error_illegal_forward_static_field_reference)

This requirement is described in Section 8.3.2.3 of the JLS. Note however that this section is confusing in several ways: First, it is not evident that the phrase "before it is used" does not include the declaration containing the initializer that uses the variable. Second, the last sentence "A compile-time error occurs if any of the three requirements above are not met." does not make sense, since the three requirements condition a requirement that must be satisfied for the problem to be valid, and thus if the condition is not fulfilled, the requirement is not in effect.

TypeChecking

The TypeChecking phase determines the types of all expressions, checks that the program is type correct, resolves all non-static field accesses and all method and constructor invocations, and performs some transformations on the AST based on the types.

Implementations

Implement the assignable function that decides whether a value of one type can be assigned to a variable of another.
The assignment rules for Java are given in Section 5.2 of the JLS. The rules for Joos are the same, except that narrowing primitive conversion is never allowed.
A Joos 2 compiler must take all Java types into account in this method, including the non-Joos types float, double and long, in order to perform closest-match method/constructor overloading properly. In a Joos 1 compiler, only the Joos types need to be considered.
Hierarchy relationships between classes and interfaces can be checked using the is_super_type function provided by the Hierarchy module.

Transformations

If one or two of the operands of the + operator have type String, the Ast.Plus node is replaced by an TAst.Concat node. For each of the direct subexpressions of the binary operation, if the expression is not a string constant or a unary or binary operation, the expression is coerced to a string, meaning it is wrapped in an TAst.ByteToString, TAst.ShortToString, TAst.IntToString, TAst.CharToString, TAst.BooleanToString or TAst.ObjectToString unary operation. All this is done in the skeleton, in the DAst.Binop case of tcheck_exp and in the coerce_to_string function.
If a field named length is read from a base expression of array type, it is transformed into an TAst.ArrayLength node.
(Joos 2) If a method named clone with no arguments is invoked on a receiver of array type, it is transformed into an TAst.ArrayClone node.
An DAst.SimpleInvoke node is transformed into an TAst.NonstaticInvoke node using this (TAst.This) as receiver (Joos 2: or an TAst.StaticInvoke node with the current class as base class).
An Ast.Eq or Ast.Ne node whose parent DAst.Binop node compares two expressions of reference type is transformed into an TAst.Aeq or TAst.Ane node, respectively. This is done in the skeleton, in the Binop case of tcheck_exp.

Decorations

For each expression in the program, put the type of the expression into the exp_type field of the TAst.exp record.
For each lvalue in the program, put the type of the lvalue into the lvalue_type field of the TAst.lvalue record.
For each static field access in the program, bind the Types.canonical_name of the type declaring the field with the TAst.StaticField constructor.
For each nonstatic field access in the program, bind the Types.canonical_name of the type declaring the field with the TAst.NonstaticField constructor.
For each invocation of a static method in the program, bind the Types.canonical_name and the Types.method_type of the type declaring the method with the TAst.StaticInvoke constructor.
For each invocation of a non-static method in the program, bind the Types.canonical_name and the Types.method_type of the type declaring the method with the TAst.NonstaticInvoke constructor.
If, after overloading resolution, the invoked method is present in more than one version with identical parameter types in the receiver class or interface (because the receiver class or interface has inherited multiple abstract versions of the same method), link to one of these arbitrarily.
For invocations on array types of methods other than clone either
(Joos 1) report an error (check_joos1_array_method_call)
or (Joos 2) link to the corresponding method in java.lang.Object.
For each class instantiation expression in the program, bind the Types.canonical_name and the Types.constructor_type of the type declaring the constructor with the TAst.New constructor.
For each super constructor invocation statement in the program (whether explicit or implicit), bind the Types.canonical_name and the Types.constructor_type of the type declaring the constructor with the TAst.SuperCall constructor.
(Joos 2) For each explicit this constructor invocation statement in the program, bind the Types.canonical_name and the Types.constructor_type of the type declaring the constructor with the TAst.ThisCall constructor.

Checks

Check that all statements and expressions are type correct according to the type rules given on the slides. If it is not possible to construct a type proof, give a compile-time error. Note that the type rule to apply to a given syntactic construction follows uniquely from the syntax and properties of its subparts.
For error reporting use the appropriate method among error_assign_type, error_binop_type, error_invalid_cast, error_invalid_instanceof, error_non_array_type_array_base, error_non_boolean_condition, error_non_numeric_array_index, error_non_numeric_array_size, error_non_numeric_inc_dec, error_unop_type and error_void_return_in_non_void_method.
The type rules for reference casts and instanceof expressions differ from those given in the JLS. The Joos rules for these expressions are that the types must be assignment compatible in either direction, whereas the Java rules are much more complicated (5.5). For primitive casts, the type rules are as in the JLS.
Check that all fields, methods and constructors that are to be linked as described in the decoration rules are actually present in the corresponding class or interface. (Use the appropriate method among error_field_on_array, error_field_on_non_reference, error_field_not_found, error_non_reference_receiver, error_no_matching_method_found, and error_no_matching_constructor_found).
(Joos 2) Check that any method or constructor invocation resolves to a uniquely closest matching method or constructor (15.12.2) (error_ambiguous_overloading). Use check_joos1_closest_match_overloading to report the use of closest match overloading in Joos 1.
Check that the return type of any called method is a valid Joos type (can be checked using the is_joos_type function). (error_non_joos_return_type)
Check that the field type of any accessed field is a valid Joos type. (error_non_joos_field_type)
(Joos 2) Check that all parameter types of any called method are valid Joos types. (error_non_joos_parameter_type)
Check that fields and methods linked as static are actually static, and that those linked as non-static are actually non-static. (Use the appropriate method among error_nonstatic_field_linked_as_static, error_static_field_linked_as_nonstatic, error_nonstatic_method_linked_as_static and error_static_method_linked_as_nonstatic)
Check that all accesses to protected fields, methods and constructors occur from within the same package as, or from within a subtype of, the class or interface declaring the accessed entity. A class instance creation expression invoking a protected constructor must be in the same package as the created class. (error_protected_member_access or error_protected_constructor_invocation)
(Joos 2) Check that constructors are not invoking each other circularly using explicit this constructor invocation statements. (error_circular_constructor_invocation)
A final field must not be assigned to. (error_assign_to_array_length or error_assign_to_final_field)
Either (Joos 1): No bitwise operations are allowed (check_joos1_bitwise_operations)
or (Joos 2) check the use of bitwise operation is type correct according to the type rules.
The types in the throws clause of a method or constructor must be subtypes of java.lang.Throwable. (error_non_throwable_in_throws)
The type in a class instance creation expression must be a non-abstract class. (error_instantiate_abstract_class or error_instantiate_interface)
A this reference (DAst.This) must not occur, explicitly or implicitly, in a static method, an initializer for a static field, or an argument to a super or this constructor invocation. (error_this_before_super_call or error_this_in_static_context)
(Joos 2) If the static type of the expression in a throw statement is a checked exception E2, then the current method or constructor must declare an exception E1 in its throws clause such that E2 is a subclass of E1. (error_illegal_throws)
For every method invocation expression, class instance creation expression, implicit or explicit super constructor invocation statement or explicit this constructor invocation statement in the program, check that for every checked exception E2 declared in the throws clause of the invoked method or constructor, the current method or constructor declares an exception E1 in its throws clause such that E2 is a subclass of E1. (error_illegal_throws) (See also slide 34 of Type Checking)
For this purpose, field initializers should be treated as declaring no checked exceptions, i.e., a method or constructor that declares any checked exceptions must not be called from a field initializer.
If, after overloading resolution, the invoked method is present in more than one version with identical parameter types in the receiver class or interface (because the receiver class or interface has inherited multiple abstract versions of the same method), this should be treated as one method declaring the intersection of exceptions declared by the present versions of the method. That is, the called method should be treated as declaring any exception E2 for which every present version of the method declares some exception E1 such that E2 is a subclass of E1. This is equivalent to assuming that the invoked method declares all exceptions that could be legally declared by a method that overrides all present versions of the method.

Documentation

You must post an entry in your group blog that explains how your code works and which problems you have encountered and solved in the process.

Furthermore for the documentation:

Explain why local variable accesses are preferred to field accesses in the disambiguation process.
Give a reason why we need a forward field reference check.
Explain the difference between the static type of an expression (the type bound by the exp_type field) and the dynamic type of an expression (the type of the expression at run time).
Explain why we do not check whether an invoked method is abstract or not.

You may also consider the following:

Give a reason why the forward field reference check makes sense when for instance public int foo = this.foo; is still allowed.
Explain the difference between the check of thrown exceptions for error_illegal_throws done in TypeChecking and the check of thrown exceptions for error_illegal_throws_in_replace done in Hierarchy.