cool language semantic check implementation.

cool-tree.handcode.h

//
// The following include files must come first.

#ifndef COOL_TREE_HANDCODE_H
#define COOL_TREE_HANDCODE_H

#include <iostream>
#include "tree.h"
#include "cool.h"
#include "stringtab.h"
#define yylineno curr_lineno;
extern int yylineno;

inline Boolean copy_Boolean(Boolean b) {return b; }
inline void assert_Boolean(Boolean) {}
inline void dump_Boolean(ostream& stream, int padding, Boolean b)
	{ stream << pad(padding) << (int) b << "\n"; }

void dump_Symbol(ostream& stream, int padding, Symbol b);
void assert_Symbol(Symbol b);
Symbol copy_Symbol(Symbol b);

class Program_class;
typedef Program_class *Program;
class Class__class;
typedef Class__class *Class_;
class Feature_class;
typedef Feature_class *Feature;
class Formal_class;
typedef Formal_class *Formal;
class Expression_class;
typedef Expression_class *Expression;
class Case_class;
typedef Case_class *Case;

typedef list_node<Class_> Classes_class;
typedef Classes_class *Classes;
typedef list_node<Feature> Features_class;
typedef Features_class *Features;
typedef list_node<Formal> Formals_class;
typedef Formals_class *Formals;
typedef list_node<Expression> Expressions_class;
typedef Expressions_class *Expressions;
typedef list_node<Case> Cases_class;
typedef Cases_class *Cases;

#define Program_EXTRAS                          \
virtual void semant() = 0;			\
virtual void dump_with_types(ostream&, int) = 0;  \
virtual void semantic_check(ClassTable &ct) = 0;



#define program_EXTRAS                          \
void semant();     				               \
void dump_with_types(ostream&, int);           \
void semantic_check(ClassTable &ct);

#define Class__EXTRAS                   \
virtual Symbol get_filename() = 0;      \
virtual void dump_with_types(ostream&,int) = 0;  \
virtual Symbol get_name() = 0;                  \
virtual Symbol get_parent() = 0;                 \
virtual void set_parent(Symbol symbol) = 0;      \
virtual Features get_features() = 0;             \
virtual void semantic_check(ClassTable &ct) = 0;


#define class__EXTRAS                                 \
Symbol get_filename() { return filename; }             \
void dump_with_types(ostream&,int);                    \
Symbol get_name();                                      \
Symbol get_parent();                                    \
void set_parent(Symbol symbol);                        \
Features get_features();                                \
void semantic_check(ClassTable &ct);


#define Feature_EXTRAS                                        \
virtual void dump_with_types(ostream&,int) = 0;          \
virtual void semantic_check(ClassTable &ct) = 0;


#define Feature_SHARED_EXTRAS                            \
void dump_with_types(ostream&,int);                      \
void semantic_check(ClassTable &ct);      


#define Formal_EXTRAS                              \
virtual void dump_with_types(ostream&,int) = 0;     \
virtual Symbol get_type_decl() = 0;                 \
virtual void semantic_check(ClassTable &ct) = 0;


#define formal_EXTRAS                           \
void dump_with_types(ostream&,int);             \
Symbol get_type_decl();                         \
void semantic_check(ClassTable &ct);


#define Case_EXTRAS                             \
virtual void dump_with_types(ostream& ,int) = 0; \
virtual void semantic_check(ClassTable &ct) = 0; \
virtual Symbol get_name() = 0;                      \
virtual Symbol get_type_decl() = 0;                 \
virtual Symbol type_check_expr(ClassTable &ct) = 0;


#define branch_EXTRAS                                   \
void dump_with_types(ostream& ,int);                \
void semantic_check(ClassTable &ct);                \
Symbol get_name();                      \
Symbol get_type_decl();                 \
Symbol type_check_expr(ClassTable &ct);

// forward declare ClassTable 
class ClassTable;

#define Expression_EXTRAS                    \
Symbol type;                                 \
Symbol get_type() { return type; }           \
Expression set_type(Symbol s) { type = s; return this; } \
virtual void dump_with_types(ostream&,int) = 0;  \
void dump_type(ostream&, int);               \
Expression_class() { type = (Symbol) NULL; } \
virtual Symbol type_check(ClassTable &ct) = 0;
// FIXME change above one to virtual once all done

#define Expression_SHARED_EXTRAS           \
void dump_with_types(ostream&,int);        \
Symbol type_check(ClassTable &ct);


// additional extras that has no stub provided 
#define method_EXTRAS                        \
Symbol get_name();                          \
Formals get_formals();                       \
Symbol get_return_type();

#define attr_EXTRAS                         \
Symbol get_name();                          \
Symbol get_type_decl();

#endif

semant.cc

#include <stdlib.h>
#include <stdio.h>
#include <stdarg.h>
#include <vector>
#include <algorithm>
#include <set>
#include "semant.h"
#include "utilities.h"

using std::endl;
//using std::set;


extern int semant_debug;
extern char *curr_filename;

//////////////////////////////////////////////////////////////////////
//
// Symbols
//
// For convenience, a large number of symbols are predefined here.
// These symbols include the primitive type and method names, as well
// as fixed names used by the runtime system.
//
//////////////////////////////////////////////////////////////////////
static Symbol 
    arg,
    arg2,
    Bool,
    concat,
    cool_abort,
    copy,
    Int,
    in_int,
    in_string,
    IO,
    length,
    Main,
    main_meth,
    No_class,
    No_type,
    Object,
    out_int,
    out_string,
    prim_slot,
    self,
    SELF_TYPE,
    Str,
    str_field,
    substr,
    type_name,
    val,
    No_expr;
//
// Initializing the predefined symbols.
//
static void initialize_constants(void)
{
    arg         = idtable.add_string("arg");
    arg2        = idtable.add_string("arg2");
    Bool        = idtable.add_string("Bool");
    concat      = idtable.add_string("concat");
    cool_abort  = idtable.add_string("abort");
    copy        = idtable.add_string("copy");
    Int         = idtable.add_string("Int");
    in_int      = idtable.add_string("in_int");
    in_string   = idtable.add_string("in_string");
    IO          = idtable.add_string("IO");
    length      = idtable.add_string("length");
    Main        = idtable.add_string("Main");
    main_meth   = idtable.add_string("main");
    //   _no_class is a symbol that can't be the name of any 
    //   user-defined class.
    No_class    = idtable.add_string("_no_class");
    No_type     = idtable.add_string("_no_type");
    Object      = idtable.add_string("Object");
    out_int     = idtable.add_string("out_int");
    out_string  = idtable.add_string("out_string");
    prim_slot   = idtable.add_string("_prim_slot");
    self        = idtable.add_string("self");
    SELF_TYPE   = idtable.add_string("SELF_TYPE");
    Str         = idtable.add_string("String"); // HACK! as user land uses 'Str' as a type name, must be aligned with it
    str_field   = idtable.add_string("_str_field");
    substr      = idtable.add_string("substr");
    type_name   = idtable.add_string("type_name");
    val         = idtable.add_string("_val");
    No_expr     = idtable.add_string("_no_expr"); // !!!! not used, code generation chokes on this
}



ClassTable::ClassTable(Classes classes) : semant_errors(0) , error_stream(cerr), class_map(),
                                          method_dmap(), attr_dmap(), scope(), sigmap() {

    /* Fill this in */
    install_basic_classes();
    for(int i = classes->first(); classes->more(i); i = classes->next(i)) {
        add_class(classes->nth(i));
    }

    // SEMANTIC CHECK - all classes shouldn't inherit from SELF_TYPE
    for(int i = classes->first(); classes->more(i); i = classes->next(i)) {
        Class_ c = classes->nth(i);
        if (c->get_parent() == SELF_TYPE) {
            semant_error(c);
            error_stream << "inherit from SELF_TYPE is forbidden." << endl;
            c->set_parent(Object); // try recovery
        }
    }

    // SEMANTIC CHECK - ensure all classes inherit from existing class
    for(int i = classes->first(); classes->more(i); i = classes->next(i)) {
        Class_ c = classes->nth(i);
        if (class_map.find(c->get_parent()) == class_map.end()) {
            semant_error(c);
            error_stream << "inherits from a class not found: " << c->get_parent()->get_string() << endl;
            c->set_parent(Object); // try recovery
        }
    }

    // Fill in method signatures and attrbute map, from now on must iterate through class_map
    for(auto iter = class_map.begin(); iter != class_map.end(); ++iter) {
        Class_ c = iter->second;
        // initialize inner map
        sigmap_type &sigmap = method_dmap[c->get_name()]; 
        attrmap_type &attrmap = attr_dmap[c->get_name()];
        Features features = c->get_features();
        for (int j = features->first(); features->more(j); j = features->next(j)) {
            Feature f = features->nth(j);
            Method method = dynamic_cast<Method>(f);
            if (method != NULL) {
                MethodSignature &sig = sigmap[method->get_name()];
                sig.return_type = method->get_return_type();
                Formals formals = method->get_formals();
                for (int k = formals->first(); formals->more(k); k = formals->next(k)) {
                    Formal formal = formals->nth(k);
                    sig.arg_types.push_back(formal->get_type_decl());
                }
            } else {
                Attr attr = dynamic_cast<Attr>(f); assert(attr);
                attrmap[attr->get_name()] = attr->get_type_decl();
            }
        }
    }

    // SEMANTIC CHECK - ensure subclass method signature are the same as the parent one.
    for (auto iter = class_map.begin(); iter != class_map.end(); ++iter) {
        Class_ class_ = iter->second;
        sigmap_type &class_sigmap = method_dmap[iter->first];
        for (Symbol parent = class_->get_parent(); parent != No_class; parent = class_map[parent]->get_parent()) {
            sigmap_type &parent_sigmap = method_dmap[parent];
            for (auto class_sigiter = class_sigmap.begin(); class_sigiter != class_sigmap.end(); ++class_sigiter) {
                MethodSignature class_sig = class_sigiter->second;
                sigmap_type::iterator parent_sigiter = parent_sigmap.find(class_sigiter->first);
                if (parent_sigiter != parent_sigmap.end()) {
                    MethodSignature parent_sig = parent_sigiter->second;
                    if ((parent_sig.arg_types != class_sig.arg_types) || (class_sig.return_type != parent_sig.return_type)) {
                        semant_error(class_);
                        error_stream << "class has invalid override method signature: " << class_->get_name()->get_string()
                            << " method: " << class_sigiter->first->get_string() << endl;
                        continue;
                    }
                }
            }
        }
    }

    // SEMANTIC CHECK - ensure attributes have types that are in the class map OR SELFTYPE
    for (auto iter = attr_dmap.begin(); iter != attr_dmap.end(); ++iter) {
        //cout << iter->first->get_string() << ":" << endl;
        auto &attrmap = iter->second;
        for (auto jiter = attrmap.begin(); jiter != attrmap.end(); ++jiter) {
            Symbol type_decl = jiter->second;
            // some cases needs to be handled, like Str is using String as class name
            if (type_decl != prim_slot && 
                type_decl != SELF_TYPE && class_map.find(type_decl) == class_map.end()) {
                semant_error(class_map[iter->first]);
                error_stream << "attribute has invalid type: " << type_decl->get_string() << endl;
                continue;
            }
        }
    }

    // error out when have semant error at this stage
    if (semant_errors) {
        cerr << "ABORT: class hierachy types has errors. Refuses to continue." << endl;
        exit(-1);
    }

    ////////////////////// DEBUG and asserts 
#if 0
    for (map<Symbol, Class_>::iterator iter = class_map.begin();
        iter != class_map.end(); ++iter) {
        cout << iter->first->get_string() << endl;
    }

    assert(is_subtype(class_map[Object], class_map[IO]));
    assert(is_subtype(class_map[Object], class_map[Object]));
    assert(!(is_subtype(class_map[Int], class_map[IO])));
    assert(lup(class_map[Object], class_map[Object]) == Object);
    assert(lup(class_map[idtable.lookup_string("D")], class_map[idtable.lookup_string("E")]) == idtable.lookup_string("C"));
    assert(lup(class_map[idtable.lookup_string("D")], class_map[idtable.lookup_string("C")]) == idtable.lookup_string("C"));
    assert(lup(class_map[idtable.lookup_string("F")], class_map[idtable.lookup_string("E")]) == idtable.lookup_string("C"));
    assert(lup(class_map[idtable.lookup_string("Main")], class_map[idtable.lookup_string("E")]) == Object);
    assert(lookup(idtable.lookup_string("F"), idtable.lookup_string("baz")));

    // dump method_dmap content
    cout << "method env dump" << endl;
    for (auto iter = method_dmap.begin(); iter != method_dmap.end(); ++iter) {
        cout << iter->first->get_string() << ":" << endl;
        auto &sigmap = iter->second;
        for (auto jiter = sigmap.begin(); jiter != sigmap.end(); ++jiter) {
            cout << jiter->first->get_string() << " ( ";
            auto &sig = jiter->second;
            for (auto veciter = sig.arg_types.begin(); veciter != sig.arg_types.end(); ++veciter) {
                cout << (*veciter)->get_string() << " ";
            }
            cout << " ) :" << sig.return_type->get_string() << endl;
        }
    }

    // dump attr_dmap content
    cout << "attr env dump" << endl;
    for (auto iter = attr_dmap.begin(); iter != attr_dmap.end(); ++iter) {
        cout << iter->first->get_string() << ":" << endl;
        auto &attrmap = iter->second;
        for (auto jiter = attrmap.begin(); jiter != attrmap.end(); ++jiter) {
            cout << jiter->first->get_string() << " : " << jiter->second->get_string() << endl;
        }
    }

    ////////////////////// END OF DEBUG and asserts 
#endif
}

void ClassTable::add_class(Class_ c) {
    class_map[c->get_name()] = c;
}

bool ClassTable::is_subtype(Symbol parent_sym, Symbol sub_sym) {
    // handle self type using cur_class
    if (parent_sym == No_type || sub_sym == No_type) return false;
    if (parent_sym == sub_sym) return true; 
    if (parent_sym == SELF_TYPE) return false;
    if (sub_sym == SELF_TYPE) {
        return is_subtype(class_map[parent_sym], cur_class);
    }
    
    return is_subtype(class_map[parent_sym], class_map[sub_sym]);
}

bool ClassTable::is_subtype(Class_ parent, Class_ sub) {
    Symbol sub_parent = sub->get_name(); // include sub's type so 'Object is_subtype of Object'
    while (sub_parent != No_class) {
        if (sub_parent == parent->get_name()) {
            return true;
        }
        sub_parent = class_map[sub_parent]->get_parent();
    }
    return false;
}

Symbol ClassTable::lup(Symbol p_sym, Symbol q_sym) {
    // handle self type using cur_class
    if (p_sym == No_type || q_sym == No_type) return No_type;
    if (p_sym == q_sym) return p_sym;
    if (p_sym == SELF_TYPE) {
        return lup(cur_class, class_map[q_sym]);
    } else if (q_sym == SELF_TYPE) {
        return lup(class_map[p_sym], cur_class);
    }
    return lup(class_map[p_sym], class_map[q_sym]);
}

Symbol ClassTable::lup(Class_ p, Class_ q) {
    // find the way up to Object and count how far from tail it can go
    vector<Symbol> p_supers, q_supers;
    Symbol p_symbol = p->get_name(),
           q_symbol = q->get_name();
    while (p_symbol != No_class) {
        p_supers.push_back(p_symbol);
        p_symbol = class_map[p_symbol]->get_parent();
    }
    while (q_symbol != No_class) {
        q_supers.push_back(q_symbol);
        q_symbol = class_map[q_symbol]->get_parent();
    }
    
    auto p_riter = p_supers.rbegin(), q_riter = q_supers.rbegin();
    while(*p_riter == *q_riter) {
        if (   (p_riter + 1 == p_supers.rend())
            || (q_riter + 1 == q_supers.rend())
            || (*(p_riter + 1) != *(q_riter + 1))
        ) {
            return *p_riter;
        } else {
            ++p_riter;
            ++q_riter;
        }
    }

    return No_type;
}

MethodSignature* ClassTable::lookup(Symbol class_sym, Symbol name) {
    // when looking up for SELF_TYPE, just use the current class
    if (class_sym == SELF_TYPE) {
        class_sym = cur_class->get_name();
    }

    if (class_map.find(class_sym) == class_map.end()) {
        return NULL;
    }

    for (Symbol class_ = class_sym; class_ != No_class; class_ = class_map[class_]->get_parent()) {
        sigmap_type &sigmap = method_dmap[class_];
        if (sigmap.find(name) != sigmap.end()) {
            return &sigmap[name];
        }
    }

    return NULL;
}

void ClassTable::install_basic_classes() {

    // The tree package uses these globals to annotate the classes built below.
   // curr_lineno  = 0;
    Symbol filename = stringtable.add_string("<basic class>");
    
    // The following demonstrates how to create dummy parse trees to
    // refer to basic Cool classes.  There's no need for method
    // bodies -- these are already built into the runtime system.
    
    // IMPORTANT: The results of the following expressions are
    // stored in local variables.  You will want to do something
    // with those variables at the end of this method to make this
    // code meaningful.

    // 
    // The Object class has no parent class. Its methods are
    //        abort() : Object    aborts the program
    //        type_name() : Str   returns a string representation of class name
    //        copy() : SELF_TYPE  returns a copy of the object
    //
    // There is no need for method bodies in the basic classes---these
    // are already built in to the runtime system.

    Class_ Object_class =
	class_(Object, 
	       No_class,
	       append_Features(
			       append_Features(
					       single_Features(method(cool_abort, nil_Formals(), Object, no_expr())),
					       single_Features(method(type_name, nil_Formals(), Str, no_expr()))),
			       single_Features(method(copy, nil_Formals(), SELF_TYPE, no_expr()))),
	       filename);

    // 
    // The IO class inherits from Object. Its methods are
    //        out_string(Str) : SELF_TYPE       writes a string to the output
    //        out_int(Int) : SELF_TYPE            "    an int    "  "     "
    //        in_string() : Str                 reads a string from the input
    //        in_int() : Int                      "   an int     "  "     "
    //
    Class_ IO_class = 
	class_(IO, 
	       Object,
	       append_Features(
			       append_Features(
					       append_Features(
							       single_Features(method(out_string, single_Formals(formal(arg, Str)),
										      SELF_TYPE, no_expr())),
							       single_Features(method(out_int, single_Formals(formal(arg, Int)),
										      SELF_TYPE, no_expr()))),
					       single_Features(method(in_string, nil_Formals(), Str, no_expr()))),
			       single_Features(method(in_int, nil_Formals(), Int, no_expr()))),
	       filename);  

    //
    // The Int class has no methods and only a single attribute, the
    // "val" for the integer. 
    //
    Class_ Int_class =
	class_(Int, 
	       Object,
	       single_Features(attr(val, prim_slot, no_expr())),
	       filename);

    //
    // Bool also has only the "val" slot.
    //
    Class_ Bool_class =
	class_(Bool, Object, single_Features(attr(val, prim_slot, no_expr())),filename);

    //
    // The class Str has a number of slots and operations:
    //       val                                  the length of the string
    //       str_field                            the string itself
    //       length() : Int                       returns length of the string
    //       concat(arg: Str) : Str               performs string concatenation
    //       substr(arg: Int, arg2: Int): Str     substring selection
    //       
    Class_ Str_class =
	class_(Str, 
	       Object,
	       append_Features(
			       append_Features(
					       append_Features(
							       append_Features(
									       single_Features(attr(val, Int, no_expr())),
									       single_Features(attr(str_field, prim_slot, no_expr()))),
							       single_Features(method(length, nil_Formals(), Int, no_expr()))),
					       single_Features(method(concat, 
								      single_Formals(formal(arg, Str)),
								      Str, 
								      no_expr()))),
			       single_Features(method(substr, 
						      append_Formals(single_Formals(formal(arg, Int)), 
								     single_Formals(formal(arg2, Int))),
						      Str, 
						      no_expr()))),
	       filename);

    // add builtin classes
    add_class(Object_class);
    add_class(IO_class);
    add_class(Int_class);
    add_class(Bool_class);
    add_class(Str_class);
}

////////////////////////////////////////////////////////////////////
//
// semant_error is an overloaded function for reporting errors
// during semantic analysis.  There are three versions:
//
//    ostream& ClassTable::semant_error()                
//
//    ostream& ClassTable::semant_error(Class_ c)
//       print line number and filename for `c'
//
//    ostream& ClassTable::semant_error(Symbol filename, tree_node *t)  
//       print a line number and filename
//
///////////////////////////////////////////////////////////////////

ostream& ClassTable::semant_error(Class_ c)
{                                                             
    return semant_error(c->get_filename(),c);
}    

ostream& ClassTable::semant_error(Symbol filename, tree_node *t)
{
    error_stream << filename << ":" << t->get_line_number() << ": ";
    return semant_error();
}

ostream& ClassTable::semant_error()                  
{                                                 
    semant_errors++;                            
    return error_stream;
} 


// easy err for easier calling
ostream& ClassTable::err(tree_node *t)
{
    semant_error(cur_class->get_filename(), t);
    return error_stream;
}

///////////////////////////////////////////////////////////////////
//
//  additional node class methods
//
///////////////////////////////////////////////////////////////////
// additional getter/setters to construct type environment
Symbol class__class::get_name() {
    return name;
}

Symbol class__class::get_parent() {
    return parent;
}

void class__class::set_parent(Symbol symbol) {
    parent = symbol;
}

Features class__class::get_features() {
    return features;
}

Symbol method_class::get_name() {
    return name;
}

Formals method_class::get_formals() {
    return formals;
}

Symbol method_class::get_return_type() {
    return return_type;
}

Symbol formal_class::get_type_decl() {
    return type_decl;
}

Symbol attr_class::get_name() {
    return name;
}

Symbol attr_class::get_type_decl() {
    return type_decl;
}

Symbol branch_class::get_name() {
    return name;
}

Symbol branch_class::get_type_decl() {
    return type_decl;
}

Symbol branch_class::type_check_expr(ClassTable &ct) {
    return expr->type_check(ct);
}

// non expression semantic_checks for entry point to expression type_checks
void program_class::semantic_check(ClassTable &ct) {
    for(int i = classes->first(); classes->more(i); i = classes->next(i)) {
        // add all attributes and methods from the top of the hierachy down to class
        Class_ class_ = classes->nth(i);
        vector<Symbol> parents;
        parents.push_back(class_->get_name());
        for (Symbol p = class_->get_parent(); p != No_class; p = ct.class_map[p]->get_parent()) {
            parents.push_back(p);
        }
        for (auto iter = parents.rbegin(); iter != parents.rend(); ++iter) {
            attrmap_type &attrmap = ct.attr_dmap[*iter];
            ct.scope.enterscope();
            for (auto jiter = attrmap.begin(); jiter != attrmap.end(); ++jiter) {
                ct.scope.addid(jiter->first, &(jiter->second));
            }

            // construct a flat sigmap to for type checking.
            sigmap_type &class_sigmap = ct.method_dmap[*iter];
            for (auto kiter = class_sigmap.begin(); kiter != class_sigmap.end(); ++kiter) {
                if (ct.sigmap.find(kiter->first) == ct.sigmap.end()) {
                    ct.sigmap[kiter->first] = kiter->second;
                }
            }
        }
 
        // check with proper scope
        ct.cur_class = class_;
        class_->semantic_check(ct);

        // pop all all scopes and ready for the next one.
        for (size_t ix = 0u; ix != parents.size(); ++ix) {
            ct.scope.exitscope();
        }
        ct.sigmap.clear();
    }
}

void class__class::semantic_check(ClassTable &ct) {
    for(int i = features->first(); features->more(i); i = features->next(i)) {
        features->nth(i)->semantic_check(ct);
    }
}

void method_class::semantic_check(ClassTable &ct) {
    // add all formals into scope then check the return value
    ct.scope.enterscope(); // ! enter scope for each method
    for(int i = formals->first(); formals->more(i); i = formals->next(i)) {
        formals->nth(i)->semantic_check(ct);
    }
    ct.scope.addid(self, &SELF_TYPE);

    Symbol expr_type = expr->type_check(ct);
    // SEMANTIC CHECK - expr_type <= return declare type
    if (!ct.is_subtype(return_type, expr_type)) {
        ct.err(this) << "return type declared as " << return_type->get_string()
         << " but expr type infered as " << expr_type->get_string() << "." << endl;
        expr->set_type(return_type); // try correction
    }


    ct.scope.exitscope(); // clean up upon exiting
}

void formal_class::semantic_check(ClassTable &ct) {
    // SEMANTIC CHECK - formal types needs to be valid.
    if (type_decl == SELF_TYPE) {
        ct.err(this) << "can't have SELF_TYPE in formal." << endl;
        type_decl = ct.cur_class->get_name();
    } else if (ct.class_map.find(type_decl) == ct.class_map.end()) {
        ct.err(this) << "can't have SELF_TYPE in formal." << endl;
        type_decl = Object;
    }

    ct.scope.addid(name, &type_decl);
}


void attr_class::semantic_check(ClassTable &ct) {
    ct.scope.enterscope();
    ct.scope.addid(self, &SELF_TYPE);

    if (dynamic_cast<no_expr_class*>(init) == NULL) {
        Symbol init_type = init->type_check(ct);
        // SEMANTIC CHECK - check init_type <= type_decl, self type is implicitly handled
        if (!ct.is_subtype(type_decl, init_type)) {
            ct.err(this) << "invalid init expr type on attr:" << name->get_string() << endl;
        }
    }

    ct.scope.exitscope();
}

void branch_class::semantic_check(ClassTable &ct) {
    // branch checks nothing. provide getters for typcase to check
}

// expression type_checks 
// simple expressions that can get type quite easily
// defined in the sequence of cool-tree.aps
Symbol assign_class::type_check(ClassTable &ct) {
    Symbol *lhs_type_ptr = ct.scope.lookup(name);
    if (lhs_type_ptr == NULL) {
        ct.err(this) << "assigning to non existent object: " << name->get_string() << endl;
        return type = Object;
    }

    Symbol expr_type = expr->type_check(ct);
    if (!ct.is_subtype(*lhs_type_ptr, expr_type)) {
        ct.err(this) << "assigning type violation: " << (*lhs_type_ptr)->get_string()
                     << " assigned with type " << expr_type->get_string() << endl;
    }

    return type = expr_type;
}

// FIXME how to easily share code between classes...
Symbol static_dispatch_class::type_check(ClassTable &ct) {
    Symbol expr_type = expr->type_check(ct);

    size_t arg_cnt = actual->len();
    vector<Symbol> arg_types(arg_cnt);
    for(int i = actual->first(); actual->more(i); i = actual->next(i)) {
        arg_types[i] = actual->nth(i)->type_check(ct);
    }

    // only difference against normal dispatch is to test for explicity given type
    if (!ct.is_subtype(type_name, expr_type)) {
        ct.err(this) << "invalid static dispatch: " << expr_type->get_string()
                     << " trying to dispatch on " << type_name->get_string() << endl;
        return type = Object;
    }
    
    // check argument types
    MethodSignature *sig_ptr = ct.lookup(expr_type, name);
    if (sig_ptr == NULL) {
        ct.err(this) << "method look up failed: " << expr_type->get_string()
                     << " looking for " << name->get_string() << endl;
        return type = Object;
    }

    if (sig_ptr->arg_types.size() != arg_cnt) {
        ct.err(this) << "argument count doesn't match: " << name->get_string()
                     << " expects " << sig_ptr->arg_types.size() << " get " << arg_cnt << endl;
        return type = Object;
    }

    // check on each argument type
    for (size_t i = 0; i != arg_cnt; ++i) {
        if (!ct.is_subtype(sig_ptr->arg_types[i], arg_types[i])) {
            ct.err(this) << "argument type does not match: " << arg_types[i]->get_string()
                         << " is not inherited from " << sig_ptr->arg_types[i] << endl;
        }
    }

    if (sig_ptr->return_type == SELF_TYPE) {
        return type = expr_type;
    } else {
        return type = sig_ptr->return_type;
    }
}

Symbol dispatch_class::type_check(ClassTable &ct) {
    Symbol expr_type = expr->type_check(ct);

    size_t arg_cnt = actual->len();
    vector<Symbol> arg_types(arg_cnt);
    for(int i = actual->first(); actual->more(i); i = actual->next(i)) {
        arg_types[i] = actual->nth(i)->type_check(ct);
    }
    
    // check argument types
    MethodSignature *sig_ptr = ct.lookup(expr_type, name);
    if (sig_ptr == NULL) {
        ct.err(this) << "method look up failed: " << expr_type->get_string()
                     << " looking for " << name->get_string() << endl;
        return type = Object;
    }

    if (sig_ptr->arg_types.size() != arg_cnt) {
        ct.err(this) << "argument count doesn't match: " << name->get_string()
                     << " expects " << sig_ptr->arg_types.size() << " get " << arg_cnt << endl;
        return type = Object;
    }

    // check on each argument type
    for (size_t i = 0; i != arg_cnt; ++i) {
        if (!ct.is_subtype(sig_ptr->arg_types[i], arg_types[i])) {
            ct.err(this) << "argument type does not match: " << arg_types[i]->get_string()
                         << " is not inherited from " << sig_ptr->arg_types[i] << endl;
        }
    }

    if (sig_ptr->return_type == SELF_TYPE) {
        return type = expr_type;
    } else {
        return type = sig_ptr->return_type;
    }
}

Symbol cond_class::type_check(ClassTable &ct) {
    Symbol pred_type = pred->type_check(ct);
    if (pred_type != Bool) {
        ct.err(this) << "predicate in if has type: " << pred_type->get_string() << endl;
        return type = Object;
    }

    Symbol then_type = then_exp->type_check(ct),
           else_type = else_exp->type_check(ct);
    Symbol lup = ct.lup(then_type, else_type);
    if (lup == No_type) {
        ct.err(this) << "then and else has no lup: " << then_type->get_string()
                     << " ," << else_type->get_string() << endl;
        return type = Object;
    }

    return type = lup;
}

Symbol loop_class::type_check(ClassTable &ct) {
    Symbol pred_type = pred->type_check(ct);
    if (pred_type != Bool) {
        ct.err(this) << "predicate in while has type: " << pred_type->get_string() << endl;
        return type = Object;
    }
    body->type_check(ct); // discard body's type
    return type = Object; // use this meaning less type to avoid user use it
}

Symbol typcase_class::type_check(ClassTable &ct) {
    // typecheck all the branches and
    // 1. calculate the lup of all
    // 2. ensure cases have different types
 
    // discard the type of expr
    expr->type_check(ct);

    if (cases->len() == 0) {
        ct.err(this) << "case contains no branches" << endl;
        return Object;
    }

    Symbol final_type = NULL;
    // !!! here's an interesting problem, can't use bare 'set', must use std::set
    // or parse will fail. need to figure this out later
    std::set<Symbol> case_type_set;
    for(int i = cases->first(); cases->more(i); i = cases->next(i)) {
        Case case_ = cases->nth(i);
        Symbol case_type = case_->get_type_decl();
        if (case_type_set.find(case_type) != case_type_set.end()) {
            ct.err(this) << "case branch has duplicated type: " << case_type->get_string() << endl;
        } else {
            case_type_set.insert(case_type);
        }
       
        // add branch name to scope 
        ct.scope.enterscope();
        ct.scope.addid(case_->get_name(), &case_type);
        Symbol case_expr_type = case_->type_check_expr(ct);
        ct.scope.exitscope();

        if (final_type == NULL) {
            final_type = case_expr_type;
        } else {
            final_type = ct.lup(final_type, case_expr_type);
            if (final_type == No_type) {
                ct.err(this) << "case body can't find a common lup: " << final_type->get_string()
                             << " with " << case_expr_type->get_string() << endl;
                return type = Object;
            }
        }
    }

    return type = final_type;
}

Symbol block_class::type_check(ClassTable &ct) {
    Symbol last;
    for(int i = body->first(); body->more(i); i = body->next(i)) {
        last = body->nth(i)->type_check(ct);
    }
    return type = last;
}

// notice that this part differs from the manual, as no multiple lets is allowed in
// this cool implementation.
Symbol let_class::type_check(ClassTable &ct) {
    // evaluate init before enterscope
    Symbol init_type = init->type_check(ct);
    // handle no init
    if (init_type != No_type) {
        if (!ct.is_subtype(type_decl, init_type)) {
            ct.err(this) << "init in let has incompatible type: " << init_type->get_string()
                         << " initing " <<  type_decl << endl;
            return type = Object;
        }
    }

    Symbol body_type;
    ct.scope.enterscope();
    ct.scope.addid(identifier, &type_decl);
    body_type = body->type_check(ct);
    ct.scope.exitscope();

    return type = body_type;
}

Symbol plus_class::type_check(ClassTable &ct) {
    if (e1->type_check(ct) != Int) {
        ct.err(this) << "lhs of plus is not int" << endl;
    }
    if (e2->type_check(ct) != Int) {
        ct.err(this) << "rhs of plus is not int" << endl;
    }

    return type = Int;
}

Symbol sub_class::type_check(ClassTable &ct) {
    if (e1->type_check(ct) != Int) {
        ct.err(this) << "lhs of substract is not int" << endl;
    }
    if (e2->type_check(ct) != Int) {
        ct.err(this) << "rhs of substract is not int" << endl;
    }

    return type = Int;
}

Symbol mul_class::type_check(ClassTable &ct) {
    if (e1->type_check(ct) != Int) {
        ct.err(this) << "lhs of mul is not int" << endl;
    }
    if (e2->type_check(ct) != Int) {
        ct.err(this) << "rhs of mul is not int" << endl;
    }

    return type = Int;
}

Symbol divide_class::type_check(ClassTable &ct) {
    if (e1->type_check(ct) != Int) {
        ct.err(this) << "lhs of divide is not int" << endl;
    }
    if (e2->type_check(ct) != Int) {
        ct.err(this) << "rhs of divide is not int" << endl;
    }

    return type = Int;
}

Symbol neg_class::type_check(ClassTable &ct) {
    if (e1->type_check(ct) != Int) {
        ct.err(this) << "neg on non Int type." << endl;
    }

    return type = Int;
}

Symbol lt_class::type_check(ClassTable &ct) {
    if (e1->type_check(ct) != Int) {
        ct.err(this) << "lhs of less than is not int" << endl;
    }
    if (e2->type_check(ct) != Int) {
        ct.err(this) << "rhs of less than is not int" << endl;
    }

    return type = Bool;
}

Symbol eq_class::type_check(ClassTable &ct) {
    Symbol lhs_type = e1->type_check(ct);
    Symbol rhs_type = e2->type_check(ct);
    if (lhs_type == Int || lhs_type == Str || lhs_type == Bool) {
        if (lhs_type != rhs_type) {
            ct.err(this) << "primitive types only can do equal check on same type: "
                         << lhs_type->get_string() << " with " << rhs_type->get_string() << endl;
        }
    }
    return type = Bool;
}

Symbol leq_class::type_check(ClassTable &ct) {
    if (e1->type_check(ct) != Int) {
        ct.err(this) << "lhs of less equal than is not int" << endl;
    }
    if (e2->type_check(ct) != Int) {
        ct.err(this) << "rhs of less equal than is not int" << endl;
    }

    return type = Bool;
}

Symbol comp_class::type_check(ClassTable &ct) {
    if (e1->type_check(ct) != Bool) {
        ct.err(this) << "not on non bool type." << endl;
    }

    return type = Bool;
}

Symbol int_const_class::type_check(ClassTable &ct) {
    return type = Int;
}

Symbol bool_const_class::type_check(ClassTable &ct) {
    return type = Bool;
}

Symbol string_const_class::type_check(ClassTable &ct) {
    return type = Str;
}

Symbol new__class::type_check(ClassTable &ct) {
    // notice that actually we don't have pure SELF_TYPE,
    // only have SELF_TYPEc, so directly returning this is correct.
    return type = type_name;
}

Symbol isvoid_class::type_check(ClassTable &ct) {
    return type = Bool;
}

Symbol no_expr_class::type_check(ClassTable &ct) {
    //return type = No_expr; // notice that this is one returns a special symbol just to indicate no_expr
    return type = No_type; // notice that this is one returns a special symbol just to indicate no_expr
}

Symbol object_class::type_check(ClassTable &ct) {
    Symbol *type_ptr = ct.scope.lookup(name);
    if (type_ptr == NULL) {
        ct.err(this) << "referencing a object that is not in any scope: "
                     << name->get_string() << endl;
        return type = Object;
    }
    return type = *type_ptr;
}

/*   This is the entry point to the semantic checker.

     Your checker should do the following two things:

     1) Check that the program is semantically correct
     2) Decorate the abstract syntax tree with type information
        by setting the `type' field in each Expression node.
        (see `tree.h')

     You are free to first do 1), make sure you catch all semantic
     errors. Part 2) can be done in a second stage, when you want
     to build mycoolc.
 */
void program_class::semant()
{
    initialize_constants();

    /* ClassTable constructor may do some semantic analysis */
    ClassTable *classtable = new ClassTable(classes);
    semantic_check(*classtable);

    /* some semantic analysis code may go here */

    if (classtable->errors()) {
	cerr << "Compilation halted due to static semantic errors." << endl;
	exit(1);
    }
}

semant.h

#ifndef SEMANT_H_
#define SEMANT_H_

#include <assert.h>
#include <iostream>  
#include <map>
#include "cool-tree.h"
#include "stringtab.h"
#include "symtab.h"
#include "list.h"

#define TRUE 1
#define FALSE 0

using std::vector;
using std::map;

// additional node typedefs, as originally phylum has class typedefs
typedef method_class *Method;
typedef attr_class *Attr;

class ClassTable;
typedef ClassTable *ClassTableP;

// This is a structure that may be used to contain the semantic
// information such as the inheritance graph.  You may use it or not as
// you like: it is only here to provide a container for the supplied
// methods.
struct MethodSignature {
  vector<Symbol> arg_types;
  Symbol return_type;
};

typedef map<Symbol, MethodSignature> sigmap_type;
typedef map<Symbol, Symbol> attrmap_type;
typedef SymbolTable<Symbol, Symbol> scope_type;

// to keep the code compact, ClassTable itself is used also as the environment.
class ClassTable {
private:
  int semant_errors;
  void install_basic_classes();
  ostream& error_stream;

public:
  ClassTable(Classes);
  int errors() { return semant_errors; }
  ostream& semant_error();
  ostream& semant_error(Class_ c);
  ostream& semant_error(Symbol filename, tree_node *t);
  ostream& err(tree_node *t);

  // Class environment related methods
  // add new class to class_map
  void add_class(Class_ c);
  // is sub a subtype of parent
  bool is_subtype(Symbol parent_sym, Symbol sub_sym);
  bool is_subtype(Class_ parent, Class_ sub);
  // least upper parent
  Symbol lup(Symbol p_sym, Symbol q_sym);
  Symbol lup(Class_ p, Class_ q);

  // look up method signature
  MethodSignature* lookup(Symbol class_sym, Symbol name);

  // class map, no need for a real tree as parent symbol is stored in Class_
  // as idtable stores only single copy of strings, using char* as map key should
  // be fine.
  map<Symbol, Class_> class_map;

  // class-> (method_name -> MethodSignature) double map, as Method environment
  map< Symbol, sigmap_type > method_dmap;

  // class-> (attr_name -> symbol) double map, as static Attr environment
  map< Symbol, attrmap_type > attr_dmap;

  // scope map object
  scope_type scope;

  // static method signature map
  sigmap_type sigmap;

  // current class
  Class_ cur_class;
};

#endif