Changeset 3e5dd913 for src/AST


Ignore:
Timestamp:
Dec 16, 2020, 2:43:12 PM (5 years ago)
Author:
Fangren Yu <f37yu@…>
Branches:
ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr, pthread-emulation, qualifiedEnum
Children:
53449a4
Parents:
13fece5
Message:

reimplement function type and eliminate deep copy

Location:
src/AST
Files:
3 deleted
16 edited

Legend:

Unmodified
Added
Removed

  • src/AST/Convert.cpp

    r13fece5 r3e5dd913  
    205205                ftype->parameters = get<DeclarationWithType>().acceptL(node->params);
    206206
    207                 ftype->forall = get<TypeDecl>().acceptL( node->type->forall );
     207                ftype->forall = get<TypeDecl>().acceptL( node->type_params );
     208                if (!node->assertions.empty()) {
     209                        assert(!ftype->forall.empty());
     210                        // find somewhere to place assertions back, for convenience it is the last slot
     211                        ftype->forall.back()->assertions = get<DeclarationWithType>().acceptL(node->assertions);
     212                }
    208213
    209214                visitType(node->type, ftype);
    … …  
    602607
    603608                for (decltype(src->begin()) src_i = src->begin(); src_i != src->end(); src_i++) {
    604                         rslt->add( src_i->first,
     609                        rslt->add( src_i->first.typeString(),
    605610                                   get<Type>().accept1(src_i->second) );
    606                 }
    607 
    608                 for (decltype(src->beginVar()) src_i = src->beginVar(); src_i != src->endVar(); src_i++) {
    609                         rslt->addVar( src_i->first,
    610                                       get<Expression>().accept1(src_i->second) );
    611611                }
    612612
    … …  
    12121212                // ty->returnVals = get<DeclarationWithType>().acceptL( node->returns );
    12131213                // ty->parameters = get<DeclarationWithType>().acceptL( node->params );
    1214                 ty->forall = get<TypeDecl>().acceptL( node->forall );
     1214
     1215                auto types = get<TypeInstType>().acceptL( node->forall );
     1216                for (auto t : types) {
     1217                        auto newT = new TypeDecl(*t->baseType);
     1218                        newT->name = t->name; // converted by typeString()
     1219                        for (auto asst : newT->assertions) delete asst;
     1220                        newT->assertions.clear();
     1221                        ty->forall.push_back(newT);
     1222                }
     1223                auto assts = get<VariableExpr>().acceptL( node->assertions );
     1224                if (!assts.empty()) {
     1225                        assert(!types.empty());
     1226                        for (auto asst : assts) {
     1227                                auto newDecl = new ObjectDecl(*strict_dynamic_cast<ObjectDecl*>(asst->var));
     1228                                delete newDecl->type;
     1229                                newDecl->type = asst->result->clone();
     1230                                newDecl->storageClasses.is_extern = true; // hack
     1231                                ty->forall.back()->assertions.push_back(newDecl);
     1232                        }
     1233                }
     1234
    12151235                return visitType( node, ty );
    12161236        }
    … …  
    12991319                        ty = new TypeInstType{
    13001320                                cv( node ),
    1301                                 node->name,
     1321                                node->typeString(),
    13021322                                get<TypeDecl>().accept1( node->base ),
    13031323                                get<Attribute>().acceptL( node->attributes )
    … …  
    13061326                        ty = new TypeInstType{
    13071327                                cv( node ),
    1308                                 node->name,
     1328                                node->typeString(),
    13091329                                node->kind == ast::TypeDecl::Ftype,
    13101330                                get<Attribute>().acceptL( node->attributes )
    … …  
    14311451        /// at conversion stage, all created nodes are guaranteed to be unique, therefore
    14321452        /// const_casting out of smart pointers is permitted.
    1433         std::unordered_map< const BaseSyntaxNode *, ast::ptr<ast::Node> > cache = {};
     1453        std::unordered_map< const BaseSyntaxNode *, ast::readonly<ast::Node> > cache = {};
    14341454
    14351455        // Local Utilities:
    … …  
    15651585                // can function type have attributes? seems not to be the case.
    15661586                // visitType(old->type, ftype);
     1587
     1588                // collect assertions and put directly in FunctionDecl
     1589                std::vector<ast::ptr<ast::DeclWithType>> assertions;
     1590                for (auto & param: forall) {
     1591                        for (auto & asst: param->assertions) {
     1592                                assertf(asst->unique(), "newly converted decl must be unique");
     1593                                assertions.emplace_back(asst);
     1594                        }
     1595                        auto mut = param.get_and_mutate();
     1596                        assertf(mut == param, "newly converted decl must be unique");
     1597                        mut->assertions.clear();
     1598                }
    15671599
    15681600                auto decl = new ast::FunctionDecl{
    … …  
    15841616                cache.emplace( old, decl );
    15851617
     1618                decl->assertions = std::move(assertions);
    15861619                decl->withExprs = GET_ACCEPT_V(withExprs, Expr);
    15871620                decl->stmts = GET_ACCEPT_1(statements, CompoundStmt);
    … …  
    20662099        }
    20672100
     2101        // TypeSubstitution shouldn't exist yet in old.
    20682102        ast::TypeSubstitution * convertTypeSubstitution(const TypeSubstitution * old) {
    2069 
     2103               
    20702104                if (!old) return nullptr;
    2071 
     2105                if (old->empty()) return nullptr;
     2106                assert(false);
     2107
     2108                /*
    20722109                ast::TypeSubstitution *rslt = new ast::TypeSubstitution();
    20732110
    … …  
    20772114                }
    20782115
    2079                 for (decltype(old->beginVar()) old_i = old->beginVar(); old_i != old->endVar(); old_i++) {
    2080                         rslt->addVar( old_i->first,
    2081                                       getAccept1<ast::Expr>(old_i->second) );
    2082                 }
    2083 
    20842116                return rslt;
     2117                */
    20852118        }
    20862119
    … …  
    26102643                        ty->params.emplace_back(v->get_type());
    26112644                }
    2612                 ty->forall = GET_ACCEPT_V( forall, TypeDecl );
     2645                // xxx - when will this be non-null?
     2646                // will have to create dangling (no-owner) decls to be pointed to
     2647                auto foralls = GET_ACCEPT_V( forall, TypeDecl );
     2648
     2649                for (auto & param : foralls) {
     2650                        ty->forall.emplace_back(new ast::TypeInstType(param->name, param));
     2651                        for (auto asst : param->assertions) {
     2652                                ty->assertions.emplace_back(new ast::VariableExpr({}, asst));
     2653                        }
     2654                }
    26132655                visitType( old, ty );
    26142656        }

  • src/AST/Decl.cpp

    r13fece5 r3e5dd913  
    5050
    5151FunctionDecl::FunctionDecl( const CodeLocation & loc, const std::string & name,
    52                 std::vector<ptr<TypeDecl>>&& forall,
    53                 std::vector<ptr<DeclWithType>>&& params, std::vector<ptr<DeclWithType>>&& returns,
    54                 CompoundStmt * stmts, Storage::Classes storage, Linkage::Spec linkage,
    55                 std::vector<ptr<Attribute>>&& attrs, Function::Specs fs, bool isVarArgs)
    56         : DeclWithType( loc, name, storage, linkage, std::move(attrs), fs ), params(std::move(params)), returns(std::move(returns)),
    57           stmts( stmts ) {
    58                   FunctionType * ftype = new FunctionType(static_cast<ArgumentFlag>(isVarArgs));
    59                   for (auto & param : this->params) {
    60                           ftype->params.emplace_back(param->get_type());
    61                   }
    62                   for (auto & ret : this->returns) {
    63                           ftype->returns.emplace_back(ret->get_type());
    64                   }
    65                   ftype->forall = std::move(forall);
    66                   this->type = ftype;
    67           }
     52        std::vector<ptr<TypeDecl>>&& forall,
     53        std::vector<ptr<DeclWithType>>&& params, std::vector<ptr<DeclWithType>>&& returns,
     54        CompoundStmt * stmts, Storage::Classes storage, Linkage::Spec linkage,
     55        std::vector<ptr<Attribute>>&& attrs, Function::Specs fs, bool isVarArgs)
     56: DeclWithType( loc, name, storage, linkage, std::move(attrs), fs ), params(std::move(params)), returns(std::move(returns)),
     57        type_params(std::move(forall)), stmts( stmts ) {
     58        FunctionType * ftype = new FunctionType(static_cast<ArgumentFlag>(isVarArgs));
     59        for (auto & param : this->params) {
     60                ftype->params.emplace_back(param->get_type());
     61        }
     62        for (auto & ret : this->returns) {
     63                ftype->returns.emplace_back(ret->get_type());
     64        }
     65        for (auto & tp : this->type_params) {
     66                ftype->forall.emplace_back(new TypeInstType(tp->name, tp));
     67        }
     68        this->type = ftype;
     69}
    6870
    6971

  • src/AST/Decl.hpp

    r13fece5 r3e5dd913  
    132132        std::vector< ptr<Expr> > withExprs;
    133133
     134        std::vector<ptr<TypeDecl>> type_params;
     135        std::vector<ptr<DeclWithType>> assertions;
     136
    134137        FunctionDecl( const CodeLocation & loc, const std::string & name, std::vector<ptr<TypeDecl>>&& forall,
    135138                std::vector<ptr<DeclWithType>>&& params, std::vector<ptr<DeclWithType>>&& returns,

  • src/AST/Expr.cpp

    r13fece5 r3e5dd913  
    206206        assert( aggregate->result );
    207207
    208         // Deep copy on result type avoids mutation on transitively multiply referenced object.
    209         //
    210         // Example, adapted from parts of builtins and bootloader:
    211         //
    212         // forall(dtype T)
    213         // struct __Destructor {
    214         //   T * object;
    215         //   void (*dtor)(T *);
    216         // };
    217         //
    218         // forall(dtype S)
    219         // void foo(__Destructor(S) &d) {
    220         //   if (d.dtor) {  // here
    221         //   }
    222         // }
    223         //
    224         // Let e be the "d.dtor" guard espression, which is MemberExpr after resolve.  Let d be the
    225         // declaration of member __Destructor.dtor (an ObjectDecl), as accessed via the top-level
    226         // declaration of __Destructor.  Consider the types e.result and d.type.  In the old AST, one
    227         // is a clone of the other.  Ordinary new-AST use would set them up as a multiply-referenced
    228         // object.
    229         //
    230         // e.result: PointerType
    231         // .base: FunctionType
    232         // .params.front(): ObjectDecl, the anonymous parameter of type T*
    233         // .type: PointerType
    234         // .base: TypeInstType
    235         // let x = that
    236         // let y = similar, except start from d.type
    237         //
    238         // Consider two code lines down, genericSubstitution(...).apply(result).
    239         //
    240         // Applying this chosen-candidate's type substitution means modifying x, substituting
    241         // S for T.  This mutation should affect x and not y.
    242 
    243         result = deepCopy(mem->get_type());
     208        result = mem->get_type();
    244209
    245210        // substitute aggregate generic parameters into member type

  • src/AST/Pass.hpp

    r13fece5 r3e5dd913  
    3434
    3535#include "AST/SymbolTable.hpp"
    36 
    37 #include "AST/ForallSubstitutionTable.hpp"
    3836
    3937// Private prelude header, needed for some of the magic tricks this class pulls off
    … …  
    6664// | WithVisitorRef        - provides an pointer to the templated visitor wrapper
    6765// | WithSymbolTable       - provides symbol table functionality
    68 // | WithForallSubstitutor - maintains links between TypeInstType and TypeDecl under mutation
    6966//
    7067// Other Special Members:
    … …  
    258255        container_t< ptr<node_t> > call_accept( const container_t< ptr<node_t> > & container );
    259256
    260         /// Mutate forall-list, accounting for presence of type substitution map
    261         template<typename node_t>
    262         void mutate_forall( const node_t *& );
    263 
    264257public:
    265258        /// Logic to call the accept and mutate the parent if needed, delegates call to accept
    … …  
    398391};
    399392
    400 /// Use when the templated visitor needs to keep TypeInstType instances properly linked to TypeDecl
    401 struct WithForallSubstitutor {
    402         ForallSubstitutionTable subs;
    403 };
    404 
    405393}
    406394

  • src/AST/Pass.impl.hpp

    r13fece5 r3e5dd913  
    367367        }
    368368
    369 
    370         template< typename core_t >
    371         template< typename node_t >
    372         void ast::Pass< core_t >::mutate_forall( const node_t *& node ) {
    373                 if ( auto subs = __pass::forall::subs( core, 0 ) ) {
    374                         // tracking TypeDecl substitution, full clone
    375                         if ( node->forall.empty() ) return;
    376 
    377                         node_t * mut = __pass::mutate<core_t>( node );
    378                         mut->forall = subs->clone( node->forall, *this );
    379                         node = mut;
    380                 } else {
    381                         // not tracking TypeDecl substitution, just mutate
    382                         maybe_accept( node, &node_t::forall );
    383                 }
    384         }
    385369}
    386370
    … …  
    504488                        __pass::symtab::addId( core, 0, func );
    505489                        VISIT(
    506                                 // parameter declarations are now directly here
     490                                // parameter declarations
    507491                                maybe_accept( node, &FunctionDecl::params );
    508492                                maybe_accept( node, &FunctionDecl::returns );
    509                                 // foralls are still in function type
    510                                 maybe_accept( node, &FunctionDecl::type );
     493                                // type params and assertions
     494                                maybe_accept( node, &FunctionDecl::type_params );
     495                                maybe_accept( node, &FunctionDecl::assertions );
    511496                                // First remember that we are now within a function.
    512497                                ValueGuard< bool > oldInFunction( inFunction );
    … …  
    17581743
    17591744        VISIT({
    1760                 guard_forall_subs forall_guard { *this, node };
    1761                 mutate_forall( node );
     1745                // guard_forall_subs forall_guard { *this, node };
     1746                // mutate_forall( node );
     1747                maybe_accept( node, &FunctionType::assertions );
    17621748                maybe_accept( node, &FunctionType::returns );
    17631749                maybe_accept( node, &FunctionType::params  );
    … …  
    19811967                {
    19821968                        bool mutated = false;
    1983                         std::unordered_map< std::string, ast::ptr< ast::Type > > new_map;
     1969                        std::unordered_map< ast::TypeInstType::TypeEnvKey, ast::ptr< ast::Type > > new_map;
    19841970                        for ( const auto & p : node->typeEnv ) {
    19851971                                guard_symtab guard { *this };
    … …  
    19941980                        }
    19951981                }
    1996 
    1997                 {
    1998                         bool mutated = false;
    1999                         std::unordered_map< std::string, ast::ptr< ast::Expr > > new_map;
    2000                         for ( const auto & p : node->varEnv ) {
    2001                                 guard_symtab guard { *this };
    2002                                 auto new_node = p.second->accept( *this );
    2003                                 if (new_node != p.second) mutated = true;
    2004                                 new_map.insert({ p.first, new_node });
    2005                         }
    2006                         if (mutated) {
    2007                                 auto new_node = __pass::mutate<core_t>( node );
    2008                                 new_node->varEnv.swap( new_map );
    2009                                 node = new_node;
    2010                         }
    2011                 }
    20121982        )
    20131983

  • src/AST/Pass.proto.hpp

    r13fece5 r3e5dd913  
    413413                static inline auto leave( core_t &, long, const ast::FunctionType * ) {}
    414414
    415                 // Get the substitution table, if present
    416                 template<typename core_t>
    417                 static inline auto subs( core_t & core, int ) -> decltype( &core.subs ) {
    418                         return &core.subs;
    419                 }
    420 
    421                 template<typename core_t>
    422                 static inline ast::ForallSubstitutionTable * subs( core_t &, long ) { return nullptr; }
    423 
    424415                // Replaces a TypeInstType's base TypeDecl according to the table
    425416                template<typename core_t>

  • src/AST/Print.cpp

    r13fece5 r3e5dd913  
    155155        }
    156156
     157        void print( const ast::FunctionType::AssertionList & assts ) {
     158                if (assts.empty()) return;
     159                os << "with assertions" << endl;
     160                ++indent;
     161                printAll(assts);
     162                os << indent;
     163                --indent;
     164        }
     165
    157166        void print( const std::vector<ptr<Attribute>> & attrs ) {
    158167                if ( attrs.empty() ) return;
    … …  
    206215        void preprint( const ast::NamedTypeDecl * node ) {
    207216                if ( ! node->name.empty() ) {
    208                         if( deterministic_output && isUnboundType(node->name) ) os << "[unbound]:";
    209                         else os << node->name << ": ";
     217                        os << node->name << ": ";
    210218                }
    211219
    … …  
    261269        void preprint( const ast::FunctionType * node ) {
    262270                print( node->forall );
     271                print( node->assertions );
    263272                print( node->qualifiers );
    264273        }
    … …  
    13751384        virtual const ast::Type * visit( const ast::TypeInstType * node ) override final {
    13761385                preprint( node );
    1377                 const auto & _name = deterministic_output && isUnboundType(node) ? "[unbound]" : node->name;
     1386                const auto & _name = deterministic_output && isUnboundType(node) ? "[unbound]" : node->typeString();
    13781387                os << "instance of type " << _name
    13791388                   << " (" << (node->kind == ast::TypeDecl::Ftype ? "" : "not ") << "function type)";
    … …  
    15021511                os << indent << "Types:" << endl;
    15031512                for ( const auto& i : *node ) {
    1504                         os << indent+1 << i.first << " -> ";
     1513                        os << indent+1 << i.first.typeString() << " -> ";
    15051514                        indent += 2;
    15061515                        safe_print( i.second );
    1507                         indent -= 2;
    1508                         os << endl;
    1509                 }
    1510                 os << indent << "Non-types:" << endl;
    1511                 for ( auto i = node->beginVar(); i != node->endVar(); ++i ) {
    1512                         os << indent+1 << i->first << " -> ";
    1513                         indent += 2;
    1514                         safe_print( i->second );
    15151516                        indent -= 2;
    15161517                        os << endl;

  • src/AST/SymbolTable.cpp

    r13fece5 r3e5dd913  
    414414
    415415void SymbolTable::addFunction( const FunctionDecl * func ) {
    416         addTypes( func->type->forall );
     416        for (auto & td : func->type_params) {
     417                addType(td);
     418        }
     419        for (auto & asst : func->assertions) {
     420                addId(asst);
     421        }
     422        // addTypes( func->type->forall );
    417423        addIds( func->returns );
    418424        addIds( func->params );

  • src/AST/Type.cpp

    r13fece5 r3e5dd913  
    2121
    2222#include "Decl.hpp"
    23 #include "ForallSubstitutor.hpp" // for substituteForall
    2423#include "Init.hpp"
    2524#include "Common/utility.h"      // for copy, move
    … …  
    9291// GENERATED END
    9392
    94 // --- ParameterizedType
    95 
    96 void FunctionType::initWithSub(
    97         const FunctionType & o, Pass< ForallSubstitutor > & sub
    98 ) {
    99         forall = sub.core( o.forall );
    100 }
    101 
    10293// --- FunctionType
    103 
    104 
    105 FunctionType::FunctionType( const FunctionType & o )
    106 : Type( o.qualifiers, copy( o.attributes ) ), returns(), params(),
    107   isVarArgs( o.isVarArgs ) {
    108         Pass< ForallSubstitutor > sub;
    109         initWithSub( o, sub );           // initialize substitution map
    110         returns = sub.core( o.returns ); // apply to return and parameter types
    111         params = sub.core( o.params );
    112 }
    113 
    11494namespace {
    11595        bool containsTtype( const std::vector<ptr<Type>> & l ) {
    … …  
    199179                // TODO: once TypeInstType representation is updated, it should properly check
    200180                // if the context id is filled. this is a temporary hack for now
    201                 return isUnboundType(typeInst->name);
    202         }
    203         return false;
    204 }
    205 
    206 bool isUnboundType(const std::string & tname) {
    207         // xxx - look for a type name produced by renameTyVars.
    208 
    209         // TODO: once TypeInstType representation is updated, it should properly check
    210         // if the context id is filled. this is a temporary hack for now
    211         if (std::count(tname.begin(), tname.end(), '_') >= 3) {
    212                 return true;
     181                return typeInst->formal_usage > 0;
    213182        }
    214183        return false;

  • src/AST/Type.hpp

    r13fece5 r3e5dd913  
    3636
    3737template< typename T > class Pass;
    38 
    39 struct ForallSubstitutor;
    4038
    4139class Type : public Node {
    … …  
    272270/// Type of a function `[R1, R2](*)(P1, P2, P3)`
    273271class FunctionType final : public Type {
    274         protected:
    275         /// initializes forall with substitutor
    276         void initWithSub( const FunctionType & o, Pass< ForallSubstitutor > & sub );
    277 public:
    278         using ForallList = std::vector<ptr<TypeDecl>>;
     272public:
     273        using ForallList = std::vector<ptr<TypeInstType>>;
     274        using AssertionList = std::vector<ptr<VariableExpr>>;
    279275        ForallList forall;
     276        AssertionList assertions;
    280277
    281278        std::vector<ptr<Type>> returns;
    … …  
    292289        : Type(q), returns(), params(), isVarArgs(va) {}
    293290
    294         FunctionType( const FunctionType & o );
     291        FunctionType( const FunctionType & o ) = default;
    295292
    296293        /// true if either the parameters or return values contain a tttype
    … …  
    397394public:
    398395        readonly<TypeDecl> base;
     396        // previously from renameTyVars; now directly use integer fields instead of synthesized strings
     397        // a nonzero value of formal_usage indicates a formal type (only used in function type)
     398        // a zero value of formal_usage indicates an actual type (referenced inside body of parametric structs and functions)
    399399        TypeDecl::Kind kind;
     400        int formal_usage;
     401        int expr_id;
     402
     403        // compact representation used for map lookups.
     404        struct TypeEnvKey {
     405                const TypeDecl * base;
     406                int formal_usage;
     407                int expr_id;
     408
     409                TypeEnvKey() = default;
     410                TypeEnvKey(const TypeDecl * base, int formal_usage = 0, int expr_id = 0): base(base), formal_usage(formal_usage), expr_id(expr_id) {}
     411                TypeEnvKey(const TypeInstType & inst): base(inst.base), formal_usage(inst.formal_usage), expr_id(inst.expr_id) {}
     412                std::string typeString() const { return std::string("_") + std::to_string(formal_usage) + "_" + std::to_string(expr_id) + "_" + base->name; }
     413                bool operator==(const TypeEnvKey & other) const { return base == other.base && formal_usage == other.formal_usage && expr_id == other.expr_id; }
     414
     415        };
     416
     417        bool operator==(const TypeInstType & other) const { return base == other.base && formal_usage == other.formal_usage && expr_id == other.expr_id; }
    400418
    401419        TypeInstType(
    … …  
    409427        TypeInstType( const TypeInstType & o ) = default;
    410428
     429        TypeInstType( const TypeEnvKey & key )
     430        : BaseInstType(key.base->name), base(key.base), kind(key.base->kind), formal_usage(key.formal_usage), expr_id(key.expr_id) {}
     431
    411432        /// sets `base`, updating `kind` correctly
    412433        void set_base( const TypeDecl * );
    … …  
    418439
    419440        const Type * accept( Visitor & v ) const override { return v.visit( this ); }
     441
     442        std::string typeString() const {
     443                if (formal_usage > 0) return std::string("_") + std::to_string(formal_usage) + "_" + std::to_string(expr_id) + "_" + name;
     444                else return name;
     445        }
    420446private:
    421447        TypeInstType * clone() const override { return new TypeInstType{ *this }; }
    … …  
    510536
    511537bool isUnboundType(const Type * type);
    512 bool isUnboundType(const std::string & tname);
    513 
     538
     539}
     540
     541namespace std {
     542        template<>
     543        struct hash<typename ast::TypeInstType::TypeEnvKey> {
     544                size_t operator() (const ast::TypeInstType::TypeEnvKey & x) const {
     545                        const size_t p = 1000007;
     546                        size_t res = reinterpret_cast<size_t>(x.base);
     547                        res = p * res + x.formal_usage;
     548                        res = p * res + x.expr_id;
     549                        return res;
     550                }
     551        };
    514552}
    515553

  • src/AST/TypeEnvironment.cpp

    r13fece5 r3e5dd913  
    5252        for ( const auto & i : open ) {
    5353                if ( first ) { first = false; } else { out << ' '; }
    54                 out << i.first << "(" << i.second << ")";
     54                out << i.first.typeString() << "(" << i.second << ")";
    5555        }
    5656}
    … …  
    6262                if(first) first = false;
    6363                else out << " ";
    64                 if( deterministic_output && isUnboundType(var) ) out << "[unbound]";
    65                 else out << var;
     64
     65                if( deterministic_output ) out << "[unbound]";
     66                else out << "_" << var.formal_usage << "_" << var.expr_id << "_";
     67
     68                out << var.base->name;
    6669        }
    6770        out << ")";
    … …  
    7982}
    8083
    81 const EqvClass * TypeEnvironment::lookup( const std::string & var ) const {
     84const EqvClass * TypeEnvironment::lookup( const TypeInstType::TypeEnvKey & var ) const {
    8285        for ( ClassList::const_iterator i = env.begin(); i != env.end(); ++i ) {
    8386                if ( i->vars.find( var ) != i->vars.end() ) return &*i;
    … …  
    106109
    107110void TypeEnvironment::add( const FunctionType::ForallList & tyDecls ) {
    108         for ( const TypeDecl * tyDecl : tyDecls ) {
     111        for ( auto & tyDecl : tyDecls ) {
    109112                env.emplace_back( tyDecl );
    110113        }
    … …  
    119122void TypeEnvironment::writeToSubstitution( TypeSubstitution & sub ) const {
    120123        for ( const auto & clz : env ) {
    121                 std::string clzRep;
     124                TypeInstType::TypeEnvKey clzRep;
     125                bool first = true;
    122126                for ( const auto & var : clz.vars ) {
    123127                        if ( clz.bound ) {
    124128                                sub.add( var, clz.bound );
    125                         } else if ( clzRep.empty() ) {
     129                        } else if ( first ) {
    126130                                clzRep = var;
     131                                first = false;
    127132                        } else {
    128                                 sub.add( var, new TypeInstType{ clzRep, clz.data.kind } );
     133                                sub.add( var, new TypeInstType{ clzRep } );
    129134                        }
    130135                }
    … …  
    141146        struct Occurs : public ast::WithVisitorRef<Occurs> {
    142147                bool result;
    143                 std::set< std::string > vars;
     148                std::unordered_set< TypeInstType::TypeEnvKey > vars;
    144149                const TypeEnvironment & tenv;
    145150
    146                 Occurs( const std::string & var, const TypeEnvironment & env )
     151                Occurs( const TypeInstType::TypeEnvKey & var, const TypeEnvironment & env )
    147152                : result( false ), vars(), tenv( env ) {
    148153                        if ( const EqvClass * clz = tenv.lookup( var ) ) {
    … …  
    154159
    155160                void previsit( const TypeInstType * typeInst ) {
    156                         if ( vars.count( typeInst->name ) ) {
     161                        if ( vars.count( *typeInst ) ) {
    157162                                result = true;
    158                         } else if ( const EqvClass * clz = tenv.lookup( typeInst->name ) ) {
     163                        } else if ( const EqvClass * clz = tenv.lookup( *typeInst ) ) {
    159164                                if ( clz->bound ) {
    160165                                        clz->bound->accept( *visitor );
    … …  
    165170
    166171        /// true if `var` occurs in `ty` under `env`
    167         bool occurs( const Type * ty, const std::string & var, const TypeEnvironment & env ) {
     172        bool occurs( const Type * ty, const TypeInstType::TypeEnvKey & var, const TypeEnvironment & env ) {
    168173                Pass<Occurs> occur{ var, env };
    169174                maybe_accept( ty, occur );
    … …  
    280285        // remove references from bound type, so that type variables can only bind to value types
    281286        ptr<Type> target = bindTo->stripReferences();
    282         auto tyvar = open.find( typeInst->name );
     287        auto tyvar = open.find( *typeInst );
    283288        assert( tyvar != open.end() );
    284289        if ( ! tyVarCompatible( tyvar->second, target ) ) return false;
    285         if ( occurs( target, typeInst->name, *this ) ) return false;
    286 
    287         auto it = internal_lookup( typeInst->name );
     290        if ( occurs( target, *typeInst, *this ) ) return false;
     291
     292        auto it = internal_lookup( *typeInst );
    288293        if ( it != env.end() ) {
    289294                if ( it->bound ) {
    … …  
    308313        } else {
    309314                env.emplace_back(
    310                         typeInst->name, target, widen.first && widen.second, data );
     315                        *typeInst, target, widen.first && widen.second, data );
    311316        }
    312317        return true;
    … …  
    318323                WidenMode widen, const SymbolTable & symtab
    319324) {
    320         auto c1 = internal_lookup( var1->name );
    321         auto c2 = internal_lookup( var2->name );
     325        auto c1 = internal_lookup( *var1 );
     326        auto c2 = internal_lookup( *var2 );
    322327
    323328        // exit early if variables already bound together
    … …  
    333338        if ( c1 != env.end() ) {
    334339                if ( c1->bound ) {
    335                         if ( occurs( c1->bound, var2->name, *this ) ) return false;
     340                        if ( occurs( c1->bound, *var2, *this ) ) return false;
    336341                        type1 = c1->bound;
    337342                }
    … …  
    340345        if ( c2 != env.end() ) {
    341346                if ( c2->bound ) {
    342                         if ( occurs( c2->bound, var1->name, *this ) ) return false;
     347                        if ( occurs( c2->bound, *var1, *this ) ) return false;
    343348                        type2 = c2->bound;
    344349                }
    … …  
    378383        } else if ( c1 != env.end() ) {
    379384                // var2 unbound, add to env[c1]
    380                 c1->vars.emplace( var2->name );
     385                c1->vars.emplace( *var2 );
    381386                c1->allowWidening = widen1;
    382387                c1->data.isComplete |= data.isComplete;
    383388        } else if ( c2 != env.end() ) {
    384389                // var1 unbound, add to env[c2]
    385                 c2->vars.emplace( var1->name );
     390                c2->vars.emplace( *var1 );
    386391                c2->allowWidening = widen2;
    387392                c2->data.isComplete |= data.isComplete;
    388393        } else {
    389394                // neither var bound, create new class
    390                 env.emplace_back( var1->name, var2->name, widen1 && widen2, data );
     395                env.emplace_back( *var1, *var2, widen1 && widen2, data );
    391396        }
    392397
    … …  
    452457}
    453458
    454 TypeEnvironment::ClassList::iterator TypeEnvironment::internal_lookup( const std::string & var ) {
     459TypeEnvironment::ClassList::iterator TypeEnvironment::internal_lookup( const TypeInstType::TypeEnvKey & var ) {
    455460        for ( ClassList::iterator i = env.begin(); i != env.end(); ++i ) {
    456461                if ( i->vars.count( var ) ) return i;

  • src/AST/TypeEnvironment.hpp

    r13fece5 r3e5dd913  
    5555/// recorded. More investigation is needed.
    5656struct AssertCompare {
    57         bool operator()( const DeclWithType * d1, const DeclWithType * d2 ) const {
    58                 int cmp = d1->name.compare( d2->name );
    59                 return cmp < 0 || ( cmp == 0 && d1->get_type() < d2->get_type() );
     57        bool operator()( const VariableExpr * d1, const VariableExpr * d2 ) const {
     58                int cmp = d1->var->name.compare( d2->var->name );
     59                return cmp < 0 || ( cmp == 0 && d1->result < d2->result );
    6060        }
    6161};
    … …  
    7070
    7171/// Set of assertions pending satisfaction
    72 using AssertionSet = std::map< readonly<DeclWithType>, AssertionSetValue, AssertCompare >;
     72using AssertionSet = std::map< const VariableExpr *, AssertionSetValue, AssertCompare >;
    7373
    7474/// Set of open variables
    75 using OpenVarSet = std::unordered_map< std::string, TypeDecl::Data >;
     75using OpenVarSet = std::unordered_map< TypeInstType::TypeEnvKey, TypeDecl::Data >;
    7676
    7777/// Merges one set of open vars into another
    … …  
    8989/// they bind to.
    9090struct EqvClass {
    91         std::set< std::string > vars;
     91        std::unordered_set< TypeInstType::TypeEnvKey > vars;
    9292        ptr<Type> bound;
    9393        bool allowWidening;
    … …  
    101101
    102102        /// Singleton class constructor from TypeDecl
    103         EqvClass( const TypeDecl * decl )
    104         : vars{ decl->name }, bound(), allowWidening( true ), data( decl ) {}
     103        EqvClass( const TypeInstType * inst )
     104        : vars{ *inst }, bound(), allowWidening( true ), data( inst->base ) {}
    105105
    106106        /// Singleton class constructor from substitution
    107         EqvClass( const std::string & v, const Type * b )
     107        EqvClass( const TypeInstType::TypeEnvKey & v, const Type * b )
    108108        : vars{ v }, bound( b ), allowWidening( false ), data( TypeDecl::Dtype, false ) {}
    109109
    110110        /// Single-var constructor (strips qualifiers from bound type)
    111         EqvClass( const std::string & v, const Type * b, bool w, const TypeDecl::Data & d )
     111        EqvClass( const TypeInstType::TypeEnvKey & v, const Type * b, bool w, const TypeDecl::Data & d )
    112112        : vars{ v }, bound( b ), allowWidening( w ), data( d ) {
    113113                reset_qualifiers( bound );
    … …  
    115115
    116116        /// Double-var constructor
    117         EqvClass( const std::string & v, const std::string & u, bool w, const TypeDecl::Data & d )
     117        EqvClass( const TypeInstType::TypeEnvKey & v, const TypeInstType::TypeEnvKey & u, bool w, const TypeDecl::Data & d )
    118118        : vars{ v, u }, bound(), allowWidening( w ), data( d ) {}
    119119
    … …  
    131131public:
    132132        /// Finds the equivalence class containing a variable; nullptr for none such
    133         const EqvClass * lookup( const std::string & var ) const;
     133        const EqvClass * lookup( const TypeInstType::TypeEnvKey & var ) const;
    134134
    135135        /// Add a new equivalence class for each type variable
    … …  
    207207
    208208        /// Private lookup API; returns array index of string, or env.size() for not found
    209         ClassList::iterator internal_lookup( const std::string & );
     209        ClassList::iterator internal_lookup( const TypeInstType::TypeEnvKey & );
    210210};
    211211

  • src/AST/TypeSubstitution.cpp

    r13fece5 r3e5dd913  
    3939void TypeSubstitution::initialize( const TypeSubstitution &src, TypeSubstitution &dest ) {
    4040        dest.typeEnv.clear();
    41         dest.varEnv.clear();
    4241        dest.add( src );
    4342}
    … …  
    4746                typeEnv[ i->first ] = i->second;
    4847        } // for
    49         for ( VarEnvType::const_iterator i = other.varEnv.begin(); i != other.varEnv.end(); ++i ) {
    50                 varEnv[ i->first ] = i->second;
    51         } // for
    5248}
    5349
    54 void TypeSubstitution::add( std::string formalType, const Type *actualType ) {
    55         typeEnv[ formalType ] = actualType;
     50void TypeSubstitution::add( const TypeInstType * formalType, const Type *actualType ) {
     51        typeEnv[ *formalType ] = actualType;
    5652}
    5753
    58 void TypeSubstitution::addVar( std::string formalExpr, const Expr *actualExpr ) {
    59         varEnv[ formalExpr ] = actualExpr;
     54void TypeSubstitution::add( const TypeInstType::TypeEnvKey & key, const Type * actualType) {
     55        typeEnv[ key ] = actualType;
    6056}
    6157
    62 void TypeSubstitution::remove( std::string formalType ) {
    63         TypeEnvType::iterator i = typeEnv.find( formalType );
     58void TypeSubstitution::remove( const TypeInstType * formalType ) {
     59        TypeEnvType::iterator i = typeEnv.find( *formalType );
    6460        if ( i != typeEnv.end() ) {
    65                 typeEnv.erase( formalType );
     61                typeEnv.erase( *formalType );
    6662        } // if
    6763}
    6864
    69 const Type *TypeSubstitution::lookup( std::string formalType ) const {
    70         TypeEnvType::const_iterator i = typeEnv.find( formalType );
     65const Type *TypeSubstitution::lookup( const TypeInstType * formalType ) const {
     66        TypeEnvType::const_iterator i = typeEnv.find( *formalType );
    7167
    7268        // break on not in substitution set
    … …  
    7571        // attempt to transitively follow TypeInstType links.
    7672        while ( const TypeInstType *actualType = i->second.as<TypeInstType>()) {
    77                 const std::string& typeName = actualType->name;
    78 
    7973                // break cycles in the transitive follow
    80                 if ( formalType == typeName ) break;
     74                if ( *formalType == *actualType ) break;
    8175
    8276                // Look for the type this maps to, returning previous mapping if none-such
    83                 i = typeEnv.find( typeName );
     77                i = typeEnv.find( *actualType );
    8478                if ( i == typeEnv.end() ) return actualType;
    8579        }
    … …  
    9084
    9185bool TypeSubstitution::empty() const {
    92         return typeEnv.empty() && varEnv.empty();
     86        return typeEnv.empty();
    9387}
    9488
    … …  
    9892                TypeSubstitution * newEnv;
    9993                EnvTrimmer( const TypeSubstitution * env, TypeSubstitution * newEnv ) : env( env ), newEnv( newEnv ){}
    100                 void previsit( TypeDecl * tyDecl ) {
     94                void previsit( FunctionType * ftype ) {
    10195                        // transfer known bindings for seen type variables
    102                         if ( const Type * t = env->lookup( tyDecl->name ) ) {
    103                                 newEnv->add( tyDecl->name, t );
     96                        for (auto & formal : ftype->forall) {
     97                                if ( const Type * t = env->lookup( formal ) ) {
     98                                        newEnv->add( formal, t );
     99                                }
    104100                        }
    105101                }
    … …  
    130126
    131127const Type * TypeSubstitution::Substituter::postvisit( const TypeInstType *inst ) {
    132         BoundVarsType::const_iterator bound = boundVars.find( inst->name );
     128        BoundVarsType::const_iterator bound = boundVars.find( *inst );
    133129        if ( bound != boundVars.end() ) return inst;
    134130
    135         TypeEnvType::const_iterator i = sub.typeEnv.find( inst->name );
     131        TypeEnvType::const_iterator i = sub.typeEnv.find( *inst );
    136132        if ( i == sub.typeEnv.end() ) {
    137133                return inst;
    … …  
    141137                // TODO: investigate preventing type variables from being bound to themselves in the first place.
    142138                if ( const TypeInstType * replacement = i->second.as<TypeInstType>() ) {
    143                         if ( inst->name == replacement->name ) {
     139                        if ( *inst == *replacement ) {
    144140                                return inst;
    145141                        }
    … …  
    156152}
    157153
    158 const Expr * TypeSubstitution::Substituter::postvisit( const NameExpr * nameExpr ) {
    159         VarEnvType::const_iterator i = sub.varEnv.find( nameExpr->name );
    160         if ( i == sub.varEnv.end() ) {
    161                 return nameExpr;
    162         } else {
    163                 subCount++;
    164                 return i->second;
    165         } // if
    166 }
    167 
    168154void TypeSubstitution::Substituter::previsit( const FunctionType * ptype ) {
    169155        GuardValue( boundVars );
    170156        // bind type variables from forall-qualifiers
    171157        if ( freeOnly ) {
    172                 for ( const TypeDecl * tyvar : ptype->forall ) {
    173                                 boundVars.insert( tyvar->name );
     158                for ( auto & tyvar : ptype->forall ) {
     159                                boundVars.insert( *tyvar );
    174160                } // for
    175161        } // if
    176162}
    177163
     164/*
    178165void TypeSubstitution::Substituter::handleAggregateType( const BaseInstType * type ) {
    179166        GuardValue( boundVars );
    … …  
    184171                        if ( ! type->params.empty() ) {
    185172                                for ( const TypeDecl * tyvar : decl->params ) {
    186                                         boundVars.insert( tyvar->name );
     173                                        boundVars.insert( *tyvar );
    187174                                } // for
    188175                        } // if
    … …  
    198185        handleAggregateType( aggregateUseType );
    199186}
     187*/
    200188
    201189} // namespace ast

  • src/AST/TypeSubstitution.hpp

    r13fece5 r3e5dd913  
    6969        }
    7070
    71         void add( std::string formalType, const Type *actualType );
     71        void add( const TypeInstType * formalType, const Type *actualType );
     72        void add( const TypeInstType::TypeEnvKey & key, const Type *actualType );
    7273        void add( const TypeSubstitution &other );
    73         void remove( std::string formalType );
    74         const Type *lookup( std::string formalType ) const;
     74        void remove( const TypeInstType * formalType );
     75        const Type *lookup( const TypeInstType * formalType ) const;
    7576        bool empty() const;
    76 
    77         void addVar( std::string formalExpr, const Expr *actualExpr );
    7877
    7978        template< typename FormalIterator, typename ActualIterator >
    … …  
    101100        friend class Pass;
    102101
    103         typedef std::unordered_map< std::string, ptr<Type> > TypeEnvType;
    104         typedef std::unordered_map< std::string, ptr<Expr> > VarEnvType;
     102        typedef std::unordered_map< TypeInstType::TypeEnvKey, ptr<Type> > TypeEnvType;
    105103        TypeEnvType typeEnv;
    106         VarEnvType varEnv;
    107104
    108105  public:
    … …  
    113110        auto   end() const -> decltype( typeEnv.  end() ) { return typeEnv.  end(); }
    114111
    115         auto beginVar()       -> decltype( varEnv.begin() ) { return varEnv.begin(); }
    116         auto   endVar()       -> decltype( varEnv.  end() ) { return varEnv.  end(); }
    117         auto beginVar() const -> decltype( varEnv.begin() ) { return varEnv.begin(); }
    118         auto   endVar() const -> decltype( varEnv.  end() ) { return varEnv.  end(); }
    119112};
    120113
     114// this is the only place where type parameters outside a function formal may be substituted.
    121115template< typename FormalIterator, typename ActualIterator >
    122116void TypeSubstitution::add( FormalIterator formalBegin, FormalIterator formalEnd, ActualIterator actualBegin ) {
    … …  
    129123                        if ( const TypeExpr *actual = actualIt->template as<TypeExpr>() ) {
    130124                                if ( formal->name != "" ) {
    131                                         typeEnv[ formal->name ] = actual->type;
     125                                        typeEnv[ formal ] = actual->type;
    132126                                } // if
    133127                        } else {
    … …  
    135129                        } // if
    136130                } else {
    137                         // TODO: type check the formal and actual parameters
    138                         if ( (*formalIt)->name != "" ) {
    139                                 varEnv[ (*formalIt)->name ] = *actualIt;
    140                         } // if
     131                       
    141132                } // if
    142133        } // for
    143134}
     135
     136
    144137
    145138template< typename FormalIterator, typename ActualIterator >
    … …  
    147140        add( formalBegin, formalEnd, actualBegin );
    148141}
     142
    149143
    150144} // namespace ast
    … …  
    164158
    165159                const Type * postvisit( const TypeInstType * aggregateUseType );
    166                 const Expr * postvisit( const NameExpr * nameExpr );
    167160
    168161                /// Records type variable bindings from forall-statements
    169162                void previsit( const FunctionType * type );
    170163                /// Records type variable bindings from forall-statements and instantiations of generic types
    171                 void handleAggregateType( const BaseInstType * type );
     164                // void handleAggregateType( const BaseInstType * type );
    172165
    173                 void previsit( const StructInstType * aggregateUseType );
    174                 void previsit( const UnionInstType * aggregateUseType );
     166                // void previsit( const StructInstType * aggregateUseType );
     167                // void previsit( const UnionInstType * aggregateUseType );
    175168
    176169                const TypeSubstitution & sub;
    177170                int subCount = 0;
    178171                bool freeOnly;
    179                 typedef std::unordered_set< std::string > BoundVarsType;
     172                typedef std::unordered_set< TypeInstType::TypeEnvKey > BoundVarsType;
    180173                BoundVarsType boundVars;
    181174

  • src/AST/module.mk

    r13fece5 r3e5dd913  
    3333        AST/Expr.cpp \
    3434        AST/Expr.hpp \
    35         AST/ForallSubstitutionTable.cpp \
    36         AST/ForallSubstitutionTable.hpp \
    37         AST/ForallSubstitutor.hpp \
    3835        AST/FunctionSpec.hpp \
    3936        AST/Fwd.hpp \
Note: See TracChangeset for help on using the changeset viewer.