In this project, you will be finishing the typechecking pass of the Truss compiler.

You do not have to have completed projects 1 or 2 successfully to do this project.

Quick start guide:

  1. You should have received a GitHub invitation link in your email. Click it!
    • Now you should have access to your repo.
  2. git clone it to your computer.
  3. Edit the typechecking pass source as detailed below so that cargo test tests_type succeeds on all tests.
  4. As you work, make use of git commits to keep track of your progress.

    You can also use git push origin main at any time to ensure that there’s a safe copy of your project on the GitHub servers, or to transfer your code between computers (by pushing it from one and pulling it on the other).

  5. When you’re done (or when you’re not done but it’s due):
    1. Update the README.txt to include your name and username and any information you think will be useful to the grader.
    2. Also update this line in Cargo.toml:
      • authors = ["YOUR NAME <YOUR PITT EMAIL>"]
    3. Commit those changes, and…
    4. git push origin main to submit it.
      • the last commit before the late due date is what we will grade.

What you’ve been given

Although you are not required to have completed projects 1 and 2, there are two test programs that you can make use of by copying these files over from those projects into this one (but do not copy any other files as that may cause things to break):

Most of the source code is familiar to you by now, but:


Getting up to speed

Since the last project, I’ve added quite a bit in the src/sem directory for semantic analysis. The semantic analysis in this compiler consists of two passes: symbols and typechecking.

In software engineering there is a long tradition of using “Context” or “Ctx” to name a type that holds a whole bunch of stuff relevant to performing some task.

The symbols pass takes the AST as its input, and does the scope building and name resolution stuff we talked about in class. Its output is a NameCtx (from src/sem/symtable.rs), short for “name context,” which bundles all the resulting naming data structures together. It contains:

This name context is then used by subsequent compiler passes to do things like:

Then comes the typechecking pass, which takes the AST and name context as inputs, and checks that everything in the program plays by the typing system rules. Its output is a TypeCtx (from src/sem/types.rs), which contains:

The latter is filled in by visit_exp in src/sem/pass_typecheck.rs, the method that you’ll be writing. (The original plan for this project was to have you do the entire typechecking pass but, well. “The best-laid plans” and all that.)


Running the tests

Like the previous projects, your goal is to get the tests working.

If you just cargo test, it will run all tests in the whole compiler including the lexer tests from project 1!

Instead, you’ll just be running cargo test tests_type. There are only 10 tests this time.

Reading the tests and their errors

Be sure to actually look at the source of the tests in src/sem/tests_type.rs. Keep it open while you work, so you can compare the test failures to what the test actually says.

Every expression test evaluates its expression in the context of this piece of Truss code (the AST of which is in stmt_ast in src/sem/tests_type.rs):

struct Empty {}

struct Point {
    x: int,
    y: int,

    fn constructor(x: int, y: int) {
    }
}

fn add(x: int, y: int): int {
    return 5;
}

fn test(var_int: int, var_str: string, var_bool: bool, var_point: Point) {
    let _RESULT_ = <the expression being tested>;
}

This means the expression can use Empty, Point, add, var_int, var_str, var_bool, and var_point, so that’s what those mean when you see them in the tests.

Let’s look at this test in exp_literals:

    exp_ok("10", intlit(10),
        Type::new_int());

The first argument ("10" here) is just a representation of what the source code looks like.

But since I can’t rely on you having completed the previous projects, the second argument (intlit(10) here) is the AST that is given to the typechecker. (You can imagine that this AST would be produced from the first argument, if you had a lexer and parser working.)

Last, the second line shows the expected result. Here, it’s saying “the int literal 10 should be of type int.”

Some cases check for specific semantic errors, like this one from exp_ident:

    exp_err("Point", id("Point"),
        NotAValue("Point".into()));

Here, the expected result is that your code gives a “not a value” error for Point, because Point is the name of a struct and cannot be used in an expression.

Finally, many tests look like this (from exp_field), for the common “type mismatch” error:

    exp_mismatch("var_int.x", field(id("var_int"), "x"),
        "struct type", // expected type
        "int",         // what you gave
        "var_int");    // context

The comments explain what the three things mean. These correspond to what you pass to self.check_types_match().


Getting Started

Open up these files in your editor, because you’ll probably need to refer to them:

You’ll also need to open this page in your browser. This is the specification of the Truss type system, and immediately after the description of the types is the expression typing rules which you’ll be implementing.

The TypecheckPass object and the methods I’ve given you

Semantic analysis works by doing a recursive visit of the AST. Much of this has been done for you in the various visit_ methods. visit_program recurses into the program’s declarations; visit_func_decl recurses into its code; visit_stmt recurses into each statement’s components, and so on, until visit_exp is called.

Have a look at the visit_stmt method, as its code is the most similar to what you’ll be writing. Take this code from the case for If statements as an example:

let cond_ty = self.visit_exp(&cond)?;
self.check_types_match(cond.id, &cond_ty, &Type::new_bool(), "'if' condition")?;

You can see two important things happening here:

Those last three arguments are what correspond to the exp_mismatch arguments in the tests.

There are more helper methods that will be introduced as you go through the instructions, but this one is common enough to get its own instructions.


Your task

Look at visit_exp at the bottom. Right now it should look like this:

    fn visit_exp(&mut self, e: &Box<Exp>) -> SemResult<Box<Type>> {
        use ExpKind::*;

        let ty = match &e.kind {
            IntLit(..) =>  Type::new_int(),

            // TODO: the rest of the cases.

            // when you implement all the cases, you will remove this line and this comment.
            _ => unimplemented!(),
        };

        self.tc.set_node_type(e.id, ty.clone());
        Ok(ty)
    }

Notice what it does: it matches on what kind of expression e is. The match should evaluate to a type; and that type is set as the node type in the type context, then returned.

You will write the rest of the cases in this method to handle every kind of expression AST node. For reference, it took me about 115 lines of code to do this. If your code is going way past that, maybe you’re making it harder than it needs to be and you should get some help.

Every case will end with the type that should be given to this expression. In the case that has been done for you:

IntLit(..) =>  Type::new_int(),

This assigns the int type to all int literal expressions, like the typing rules say.

Remember that to “give a value”, you just write it as the last thing in a match arm without a semicolon.

Whatever => {
    let some_ty = whatever();
    self.blah_blah();
    some_ty // this is what type will be given from this arm.
}

Literals (exp_literals)

I’ve already done int literals for you. Now, add cases for BoolLit and StrLit (these are the ExpKind enumeration from src/parse/ast.rs). Look in the impl Type in src/sem/types.rs to see how to construct string and bool types.

Just two lines of code! And that test should now pass.


Identifiers (exp_ident)

Make a case like this:

Id(ident) => {

}

Remember, this is declaring a variable named ident which holds the identifier that was inside the Id(..) enum variant.

Name resolution has already been done, so you need to do two things. It’s only a few lines of code, but there’s a lot going on in those few lines:

  1. get the symbol that this identifier refers to.
    • use self.get_referenced_symbol(ident) for that.
    • it returns a reference to a Symbol object, which is defined in src/sem/symtable.rs.
  2. get the symbol’s type, if it has one, and give an error if not.
    • use self.get_sym_type(sym.id), where sym is the symbol you got in the previous step.
    • this returns an Option<Box<Type>>, so you must match on it:
      • in the Some(ty) case, ty is the type you want to give. So, Some(ty) => ty, is all you need.
      • in the None case, you have to return an error.
        • specifically, Err(SemError::not_a_value(&ident)), to indicate this identifier does not refer to a value.

That’s it. If it compiles, the exp_ident test should now work.


Fields (exp_field)

Now to handle the Field { obj, name } => { ... } case. Remember from parsing that obj can be any expression, and name is an identifier.

Because obj is an expression, first you need to recursively visit it to get its type, like:

    let obj_ty = self.visit_exp(obj)?;

Once you have the type of the object, there are three steps. Look at the type signatures of these helper methods and see if you can figure out how to call them to get your work done:

  1. use self.check_struct_type()? to ensure that obj_ty really is a struct type.
    • use &obj as the first argument (used for error messages).
  2. use self.lookup_struct_field()? to look up name in the struct type that check_struct_type gave.
  3. use self.get_sym_type() to get the type of the field that lookup_struct_field returned.
    • you will have to use .unwrap() on the Option it returns.
    • this “unwraps” the Option giving you the Some value, and will crash if it’s None.
    • however in this case, we know the field has a type, so it’s safe to unwrap it.

If your exp_field test is failing, things to check:


Unary expressions (exp_unary)

Time for Unary { op, lhs } => { ... }.


Function calls (exp_call)

Call { callee, args } => { ... }.

This one is a little different. Start with this:

let callee_ty = self.visit_exp(callee)?;

match *callee_ty {
    Type::Func { args: arg_types, ret: ret_type } => {
        // it's a function; arg_types and ret_type are the argument and return types
    }
    _ => {
        // it's NOT a function, uh oh
    }
}

Struct constructors (ctors) (exp_ctor)

Ctor { ty, args } => { ... }. (Remember parsing these? This is like when the user types new Cat().)

Read the typing rules about new S(), new S(x, y, z). A struct may have a constructor (like Point does in the tests) or may not (like Empty). Essentially, if it has no constructor, it behaves as if it takes 0 arguments.

Some guiding notes:


Binary Expressions (exp_equality, exp_relational, exp_logical, exp_arithmetic)

Binary { op, lhs, rhs } => { ... }.

These last four tests are broken up based on similarity of implementation, because there are many binary operators in this language.

It’s gonna start off like unary operators - visit lhs and rhs to get their types, then match on op (which is BinOp). Then every operator’s code looks something like:

  1. check if the LHS is a valid type for this operator.
  2. check if the RHS’s type matches the LHS’s type.
    • self.check_types_match(rhs.id, &rhs_ty, &lhs_ty, &format!("rhs of '{}'", op))?;
  3. give the appropriate result type for this operator.

Each set of operators has slightly different details for steps 1 and 3 here.

Start with the equality operators like this:

match op {
	// you can match on multiple possibilities with |
    BinOp::Eq | BinOp::NotEq => {
    	...
    }
    _ => unimplemented!(), // remove this when done
}

Equality can be performed on any non-void types. Types have an .is_void() method you can use to test for that. If the LHS’s type is void, you’ll have to return an error like:

SemError::type_mismatch(lhs.id, "non-void type", &lhs_ty.to_string(), &format!("lhs of '{}'", op))

Then do the relational operators (BinOp::Less | BinOp::Greater | BinOp::LessEq | BinOp::GreaterEq). These only work on ints, so you can use self.check_types_match to see if the LHS’s type matches &Type::new_int(). Be sure to pass the types in the right order: LHS’s actual type first, &Type::new_int() second.

Third are the logical operators (BinOp::And | BinOp::Or). This is almost like relational, but with bool instead of int.

Finally are the arithmetic operators, where we have one complication: the BinOp::Add operation is overloaded for both addition and string concatenation. So, the LHS’s type must be int or string - use the .is_int() and .is_string() methods to check for those. Then, you can check that the RHS has the same type as the LHS as usual, and give the type of the LHS if it succeeds.

All the other operators (BinOp::Sub | BinOp::Mul | BinOp::Div | BinOp::Mod | BinOp::Shl | BinOp::Shr) expect an int on the LHS and give an int.


Submission and Grading

Project submissions will only be accepted through GitHub. If you are having trouble using git, please get in touch sooner rather than at 11:58 PM on the due date.

The project is due at midnight on the due date, but there is some wiggle room there. (We can see the time that you pushed to GitHub.)

You can turn it in for late credit until midnight on the day after the due date. You’ll get 10% off your grade.

Grading rubric: