This week you will add name analysis to your Tool compiler. This will considerably ease the task of type checking that you will start next week or the week after. The name analyzer will be due Tuesday, Nov. 25th, 11.59pm (23h59). Note that the type checker will be due the following week, so make sure you start working on it as early as possible.

The description of this assignment is rather long. Don't panic :) Most of it is to help you avoid forgetting important points, and we give you a substantial amount of code.

The goal of name analysis is twofold: we want to reject programs which contain certain types of errors, and we want to associate symbols to all identifiers.

Symbols are values which uniquely identify all class, method and variable names in a program, by mapping their (multiple) occurrences to their (unique) definition. Identifiers are already present in the AST and contain names as well, but these are not sufficient to distinguish between a class member and a local variable with the same name, for instance. This week we will –among other things– add this missing information to the ASTs.

In the process of mapping occurrences to definitions, we will be able to detect the following kinds or errors:

• a class is defined more than once
• a class uses the same name as the main object
• a variable is defined more than once
• a class member is overloaded (forbidden in Tool)
• a method is overloaded (forbidden in Tool)
• a method argument is shadowed by a local variable declaration (forbidden in Java, and we follow this convention)
• two method arguments have the same name
• a class name is used as a symbol (as parent class or type, for instance) but is not declared
• an identifier is used as a variable but not is declared
• the inheritance graph has a cycle (eg. “class A extends B {} class B extends A {}”)
• (Note that we don't check that method calls correspond to methods defined in the proper class. We will need type-checking for this.)

Additionally, we want you to emit a warning to the user when a declared variable is never accessed (read or written). This should really be a warning, not an error (ie. it should not prevent the compiler from proceeding to execute).

In order to attach symbols to trees, we define a new trait, Symbolic, and a new set of classes for the symbols. The Symbolic trait is parametrized by a class name which allows us to define the kind of symbols which can be attached to each kind of AST node (see Symbols.scala and Trees.scala later for examples).

You need to write your analyzer such that two nodes referencing the same symbol have the same symbol class instance attached to them (that is, reference equality, structural equality is not enough). We defined the Symbol class such that symbols automatically get a unique identifier attached to them at creation. This will allow you to check that you are attaching symbols correctly: you will add an option to your pretty-printer to be able to print these unique numbers along with the identifiers where they occur.

Note that Symbols are also Positional objects, which means you have to set them a correct position. The position of the symbol should be its declaration position. This is necessary to produce meaningful error messages such as “error: class Cl is defined twice. First definition here: …”.

When your compiler encounters an internal error (for example, a scope is not initialized as you expected, a symbol is null, etc.), you should not use the methods from the reporter trait. This will be counted as a mistake. You must use sys.error instead, which will throw an exception and show you the stack trace. The reason is that you shouldn't blame the user for internal errors. In fact, the user should never encounter an internal error. Of course, writing bug-free programs is hard…

We will take advantage of the fact that scopes in Tool are only of three kinds:

1. the global scope (the set of declared classes)
2. the class scopes (all members and methods within a class, plus the global scope)
3. the method scopes (the parameters and local variables, plus the corresponding class scope)

This in fact defines a hierarchy among symbols:

• all class symbols are defined in the global scope
• all methods are defined in a class scope
• variables are defined either in a method scope, as arguments or locals, or in a class scope

We encoded this hierarchy in the symbol classes. Therefore, if we have access to a class symbol, for instance, and all symbols were correctly set, we can access from there all method symbols and member variable symbols. This will allow us to easily check if a variable was declared, for instance.

For declarations such as MethodDecl, you will notice that not only the declaration itself extends Symbolic, but also its Identifier field. Generally, you must set the (same) symbol both on declarations and their identifiers. Note that since the MethodDecl extends Symbolic[MethodSymbol], you have the guarantee that setting/getting a symbol here will always be a method symbol.

It should be sufficient to only modify your printer to print symbols of Identifiers.

Here is how we recommend you proceed for the implementation:

1. First, collect all symbols: create the symbol class instances, and attach them to object fields types, method members types, formals types and method return types.
2. Make the appropriate changes to your pretty-printer and make sure you see the unique IDs next to the identifiers at the definition points.
3. Implement the second phase of your analyzer which consists in attaching the proper symbol to the occurrences of the identifiers. To simplify your task, start by writing lookup* methods in the symbol classes: they will allow you to easily check whether an identifier was declared and to recover its symbol if it was. Make sure you properly encode the scope rules (including shadowing) in your lookup* methods.
4. You can use your pretty-printer to make sure you attached symbols correctly.
5. Make sure that you throw errors and warnings when appropriate.

When analyzing the following file:

object Example {
  def main() : Unit = {
    println(new B().foo());
  }
}
 
class B extends A {
  def foo() : Int = {
    value = 42;
    return value;
  }
}
 
class A {
  var value : Int;
  def foo() : Int = {
    var value : Bool;
    value = false;
    return 41;
  }
}

The (updated) pretty-printer would output something like:

object Example#0 {
  def main() : Unit = {
    println(new B#1().foo#??());
  }
}
 
class B#1 extends A#2 {
  def foo#6() : Int = {
    value#3 = 42;
    return value#3;
  }
}
 
class A#2 {
  var value#3 : Int;
  def foo#4() : Int = {
    var value#5 : Bool;
    value#5 = false;
    return 41;
  }
}

Note that:

• Overriding methods have a different symbol than their overridden counterparts.
• Method names in method calls are unresolved symbols.

Here are all the constraints that your analyzer should enforce:¹⁾

• No two variables can have the same name in the same scope, unless one of the two cases of shadowing occurs.
• All variables used must be declared.

Shadowing can occur in two different situations:

1. a local variable in a method can shadow a class member
2. a method parameter can shadow a class member

All other types of shadowing are not allowed in Tool.

• Classes must be defined only once.
• When a class is declared as extending another one, the other class must be declared and cannot be the main object.
• The transitive closure of the “extends” relation must be irreflexive (no cycles in the inheritance graph).
• When a class name is used as a type, the class must be declared. The main object cannot be used as a type.

• Overloading is not permitted:
  • In a given class, no two methods can have the same name.
  • In a given class, no method can have the same name as another method defined in a super class, unless overriding applies.

• A method in a given class overrides another one in a super class if they have the same name and the same number of arguments.²⁾
• Fields can not be overridden.

You can download the stubs from our main repository by following the instructions. It should merge the following files in your project. If you get conflicts, don't panic, they should be relatively easy to resolve.

• analyzer/Symbols.scala contains the definition of symbols, GlobalScope and the Symbolic trait. You only have to write the body of the lookup methods.
• analyzer/NameAnalysis.scala contains a stub for the name analyzer.
• parser/Trees.scala contains an updated version of trees with symbols.
• Main.scala contains code to run the analyzer after the parser.

toolc
  ├── Main.scala               (updated this week)
  │
  ├── analyzer
  │    ├── NameAnalysis.scala  (stubs provided this week)
  │    └── Symbols.scala       (stubs provided this week)
  │
  ├── lexer
  │    ├── Lexer.scala      
  │    └── Tokens.scala     
  │
  ├── eval                     
  │    └── Evaluator.scala 
  │ 
  ├── ast
  │    ├── Parser.scala
  │    ├── Printer.scala    
  │    └── Trees.scala         (updated this week)
  │
  └── utils
       ├── Context.scala
       ├── Positioned.scala
       ├── Reporter.scala
       └── Pipeline.scala

Please choose a commit from your git repository as a deliverable on our server before Sunday, Nov. 25th, 11.59pm (23h59).