Index: src/AST/Convert.cpp =================================================================== --- src/AST/Convert.cpp (revision 2c04369a0b21c0ce78ea35835ad1f3d320c8813a) +++ src/AST/Convert.cpp (revision d76c588058daa6269114595a571223a110ced0ab) @@ -63,5 +63,5 @@ std::list< T * > acceptL( const U & container ) { std::list< T * > ret; - for (auto ptr : container ) { + for ( auto ptr : container ) { ret.emplace_back( accept1( ptr ) ); } @@ -1432,4 +1432,5 @@ }; cache.emplace( old, decl ); + decl->withExprs = GET_ACCEPT_V(withExprs, Expr); decl->scopeLevel = old->scopeLevel; decl->mangleName = old->mangleName; Index: src/AST/Decl.cpp =================================================================== --- src/AST/Decl.cpp (revision 2c04369a0b21c0ce78ea35835ad1f3d320c8813a) +++ src/AST/Decl.cpp (revision d76c588058daa6269114595a571223a110ced0ab) @@ -17,4 +17,5 @@ #include // for assert, strict_dynamic_cast +#include #include #include @@ -70,4 +71,8 @@ } +std::ostream & operator<< ( std::ostream & out, const TypeDecl::Data & data ) { + return out << data.kind << ", " << data.isComplete; +} + // --- EnumDecl Index: src/AST/Decl.hpp =================================================================== --- src/AST/Decl.hpp (revision 2c04369a0b21c0ce78ea35835ad1f3d320c8813a) +++ src/AST/Decl.hpp (revision d76c588058daa6269114595a571223a110ced0ab) @@ -16,4 +16,5 @@ #pragma once +#include #include // for string, to_string #include @@ -121,5 +122,5 @@ ptr type; ptr stmts; - std::list< ptr > withExprs; + std::vector< ptr > withExprs; FunctionDecl( const CodeLocation & loc, const std::string &name, FunctionType * type, @@ -172,13 +173,13 @@ Data() : kind( (TypeVar::Kind)-1 ), isComplete( false ) {} - Data( TypeDecl* d ) : kind( d->kind ), isComplete( d->sized ) {} + Data( const TypeDecl * d ) : kind( d->kind ), isComplete( d->sized ) {} Data( TypeVar::Kind k, bool c ) : kind( k ), isComplete( c ) {} - Data( const Data& d1, const Data& d2 ) + Data( const Data & d1, const Data & d2 ) : kind( d1.kind ), isComplete( d1.isComplete || d2.isComplete ) {} - bool operator== ( const Data& o ) const { + bool operator== ( const Data & o ) const { return kind == o.kind && isComplete == o.isComplete; } - bool operator!= ( const Data& o ) const { return !(*this == o); } + bool operator!= ( const Data & o ) const { return !(*this == o); } }; @@ -200,4 +201,6 @@ MUTATE_FRIEND }; + +std::ostream & operator<< ( std::ostream &, const TypeDecl::Data & ); /// C-style typedef `typedef Foo Bar` Index: src/AST/Expr.cpp =================================================================== --- src/AST/Expr.cpp (revision 2c04369a0b21c0ce78ea35835ad1f3d320c8813a) +++ src/AST/Expr.cpp (revision d76c588058daa6269114595a571223a110ced0ab) @@ -64,5 +64,6 @@ // references have been removed, in which case dereference returns an lvalue of the // base type - ret->result.set_and_mutate( base )->set_lvalue( true ); + ret->result = base; + add_lvalue( ret->result ); } } @@ -173,5 +174,6 @@ assert( var ); assert( var->get_type() ); - result.set_and_mutate( var->get_type() )->set_lvalue( true ); + result = var->get_type(); + add_lvalue( result ); } @@ -306,5 +308,6 @@ : Expr( loc ), init( i ) { assert( t && i ); - result.set_and_mutate( t )->set_lvalue( true ); + result = t; + add_lvalue( result ); } @@ -322,5 +325,6 @@ "index %d in expr %s", type->size(), index, toString( tuple ).c_str() ); // like MemberExpr, TupleIndexExpr is always an lvalue - result.set_and_mutate( type->types[ index ] )->set_lvalue( true ); + result = type->types[ index ]; + add_lvalue( result ); } Index: src/AST/Node.hpp =================================================================== --- src/AST/Node.hpp (revision 2c04369a0b21c0ce78ea35835ad1f3d320c8813a) +++ src/AST/Node.hpp (revision d76c588058daa6269114595a571223a110ced0ab) @@ -113,7 +113,5 @@ } - ptr_base( ptr_base && o ) : node(o.node) { - if( node ) _inc(node); - } + ptr_base( ptr_base && o ) : node(o.node) { o.node = nullptr; } template< enum Node::ref_type o_ref_t > @@ -139,5 +137,8 @@ ptr_base & operator=( ptr_base && o ) { - assign(o.node); + if ( node == o.node ) return *this; + if ( node ) _dec(node); + node = o.node; + o.node = nullptr; return *this; } Index: src/AST/Pass.hpp =================================================================== --- src/AST/Pass.hpp (revision 2c04369a0b21c0ce78ea35835ad1f3d320c8813a) +++ src/AST/Pass.hpp (revision d76c588058daa6269114595a571223a110ced0ab) @@ -179,5 +179,5 @@ template - friend void acceptAll( std::list< ptr > & decls, Pass& visitor ); + friend void accept_all( std::list< ptr > & decls, Pass& visitor ); private: Index: src/AST/Pass.proto.hpp =================================================================== --- src/AST/Pass.proto.hpp (revision 2c04369a0b21c0ce78ea35835ad1f3d320c8813a) +++ src/AST/Pass.proto.hpp (revision d76c588058daa6269114595a571223a110ced0ab) @@ -312,5 +312,4 @@ INDEXER_FUNC1( addTrait , const TraitDecl * ); INDEXER_FUNC2( addWith , const std::vector< ptr > &, const Node * ); - INDEXER_FUNC2( addWith , const std::list < ptr > &, const Node * ); // A few extra functions have more complicated behaviour, they are hand written Index: src/AST/Print.hpp =================================================================== --- src/AST/Print.hpp (revision 2c04369a0b21c0ce78ea35835ad1f3d320c8813a) +++ src/AST/Print.hpp (revision d76c588058daa6269114595a571223a110ced0ab) @@ -17,4 +17,5 @@ #include +#include // for forward #include "AST/Node.hpp" @@ -28,6 +29,8 @@ void print( std::ostream & os, const ast::Node * node, Indenter indent = {} ); -inline void print( std::ostream & os, const ast::Node * node, unsigned int indent ) { - print( os, node, Indenter{ Indenter::tabsize, indent }); +/// Wrap any standard format printer (matching above) with integer Indenter constructor +template +inline void print( std::ostream & os, T && x, unsigned int indent ) { + print( os, std::forward(x), Indenter{ Indenter::tabsize, indent }); } Index: src/AST/SymbolTable.cpp =================================================================== --- src/AST/SymbolTable.cpp (revision d76c588058daa6269114595a571223a110ced0ab) +++ src/AST/SymbolTable.cpp (revision d76c588058daa6269114595a571223a110ced0ab) @@ -0,0 +1,709 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// SymbolTable.cpp -- +// +// Author : Aaron B. Moss +// Created On : Wed May 29 11:00:00 2019 +// Last Modified By : Aaron B. Moss +// Last Modified On : Wed May 29 11:00:00 2019 +// Update Count : 1 +// + +#include "SymbolTable.hpp" + +#include + +#include "Decl.hpp" +#include "Expr.hpp" +#include "Type.hpp" +#include "CodeGen/OperatorTable.h" // for isCtorDtorAssign +#include "Common/SemanticError.h" +#include "Common/Stats/Counter.h" +#include "GenPoly/GenPoly.h" +#include "InitTweak/InitTweak.h" +#include "ResolvExpr/Cost.h" +#include "ResolvExpr/typeops.h" +#include "SymTab/Mangler.h" + +namespace ast { + +// Statistics block +namespace { + static inline auto stats() { + using namespace Stats::Counters; + static auto group = build("Indexers"); + static struct { + SimpleCounter * count; + AverageCounter * size; + SimpleCounter * new_scopes; + SimpleCounter * lazy_scopes; + AverageCounter * avg_scope_depth; + MaxCounter * max_scope_depth; + SimpleCounter * add_calls; + SimpleCounter * lookup_calls; + SimpleCounter * map_lookups; + SimpleCounter * map_mutations; + } ret = { + .count = build("Count", group), + .size = build>("Average Size", group), + .new_scopes = build("Scopes", group), + .lazy_scopes = build("Lazy Scopes", group), + .avg_scope_depth = build>("Average Scope", group), + .max_scope_depth = build>("Max Scope", group), + .add_calls = build("Add Calls", group), + .lookup_calls = build("Lookup Calls", group), + .map_lookups = build("Map Lookups", group), + .map_mutations = build("Map Mutations", group) + }; + return ret; + } +} + +Expr * SymbolTable::IdData::combine( const CodeLocation & loc, ResolvExpr::Cost & cost ) const { + Expr * ret = ( baseExpr ) ? + (Expr *)new MemberExpr{ loc, id, referenceToRvalueConversion( baseExpr, cost ) } : + (Expr *)new VariableExpr{ loc, id }; + if ( deleter ) { ret = new DeletedExpr{ loc, ret, deleter }; } + return ret; +} + +SymbolTable::SymbolTable() +: idTable(), typeTable(), structTable(), enumTable(), unionTable(), traitTable(), + prevScope(), scope( 0 ), repScope( 0 ) { ++*stats().count; } + +SymbolTable::~SymbolTable() { stats().size->push( idTable ? idTable->size() : 0 ); } + +void SymbolTable::enterScope() { + ++scope; + + ++*stats().new_scopes; + stats().avg_scope_depth->push( scope ); + stats().max_scope_depth->push( scope ); +} + +void SymbolTable::leaveScope() { + if ( repScope == scope ) { + Ptr prev = prevScope; // make sure prevScope stays live + *this = std::move(*prevScope); // replace with previous scope + } + + --scope; +} + +std::vector SymbolTable::lookupId( const std::string &id ) const { + ++*stats().lookup_calls; + if ( ! idTable ) return {}; + + ++*stats().map_lookups; + auto decls = idTable->find( id ); + if ( decls == idTable->end() ) return {}; + + std::vector out; + for ( auto decl : *(decls->second) ) { + out.push_back( decl.second ); + } + return out; +} + +const NamedTypeDecl * SymbolTable::lookupType( const std::string &id ) const { + ++*stats().lookup_calls; + if ( ! typeTable ) return nullptr; + ++*stats().map_lookups; + auto it = typeTable->find( id ); + return it == typeTable->end() ? nullptr : it->second.decl; +} + +const StructDecl * SymbolTable::lookupStruct( const std::string &id ) const { + ++*stats().lookup_calls; + if ( ! structTable ) return nullptr; + ++*stats().map_lookups; + auto it = structTable->find( id ); + return it == structTable->end() ? nullptr : it->second.decl; +} + +const EnumDecl * SymbolTable::lookupEnum( const std::string &id ) const { + ++*stats().lookup_calls; + if ( ! enumTable ) return nullptr; + ++*stats().map_lookups; + auto it = enumTable->find( id ); + return it == enumTable->end() ? nullptr : it->second.decl; +} + +const UnionDecl * SymbolTable::lookupUnion( const std::string &id ) const { + ++*stats().lookup_calls; + if ( ! unionTable ) return nullptr; + ++*stats().map_lookups; + auto it = unionTable->find( id ); + return it == unionTable->end() ? nullptr : it->second.decl; +} + +const TraitDecl * SymbolTable::lookupTrait( const std::string &id ) const { + ++*stats().lookup_calls; + if ( ! traitTable ) return nullptr; + ++*stats().map_lookups; + auto it = traitTable->find( id ); + return it == traitTable->end() ? nullptr : it->second.decl; +} + +const NamedTypeDecl * SymbolTable::globalLookupType( const std::string &id ) const { + return atScope( 0 )->lookupType( id ); +} + +const StructDecl * SymbolTable::globalLookupStruct( const std::string &id ) const { + return atScope( 0 )->lookupStruct( id ); +} + +const UnionDecl * SymbolTable::globalLookupUnion( const std::string &id ) const { + return atScope( 0 )->lookupUnion( id ); +} + +const EnumDecl * SymbolTable::globalLookupEnum( const std::string &id ) const { + return atScope( 0 )->lookupEnum( id ); +} + +void SymbolTable::addId( const DeclWithType * decl, const Expr * baseExpr ) { + // default handling of conflicts is to raise an error + addId( decl, OnConflict::error(), baseExpr, decl->isDeleted ? decl : nullptr ); +} + +void SymbolTable::addDeletedId( const DeclWithType * decl, const Node * deleter ) { + // default handling of conflicts is to raise an error + addId( decl, OnConflict::error(), nullptr, deleter ); +} + +namespace { + /// true if redeclaration conflict between two types + bool addedTypeConflicts( const NamedTypeDecl * existing, const NamedTypeDecl * added ) { + if ( existing->base == nullptr ) { + return false; + } else if ( added->base == nullptr ) { + return true; + } else { + // typedef redeclarations are errors only if types are different + if ( ! ResolvExpr::typesCompatible( existing->base, added->base, SymbolTable{} ) ) { + SemanticError( added->location, "redeclaration of " + added->name ); + } + } + // does not need to be added to the table if both existing and added have a base that are + // the same + return true; + } + + /// true if redeclaration conflict between two aggregate declarations + bool addedDeclConflicts( const AggregateDecl * existing, const AggregateDecl * added ) { + if ( ! existing->body ) { + return false; + } else if ( added->body ) { + SemanticError( added, "redeclaration of " ); + } + return true; + } +} + +void SymbolTable::addType( const NamedTypeDecl * decl ) { + ++*stats().add_calls; + const std::string &id = decl->name; + + if ( ! typeTable ) { + typeTable = TypeTable::new_ptr(); + } else { + ++*stats().map_lookups; + auto existing = typeTable->find( id ); + if ( existing != typeTable->end() + && existing->second.scope == scope + && addedTypeConflicts( existing->second.decl, decl ) ) return; + } + + lazyInitScope(); + ++*stats().map_mutations; + typeTable = typeTable->set( id, scoped{ decl, scope } ); +} + +void SymbolTable::addStruct( const std::string &id ) { + addStruct( new StructDecl( CodeLocation{}, id ) ); +} + +void SymbolTable::addStruct( const StructDecl * decl ) { + ++*stats().add_calls; + const std::string &id = decl->name; + + if ( ! structTable ) { + structTable = StructTable::new_ptr(); + } else { + ++*stats().map_lookups; + auto existing = structTable->find( id ); + if ( existing != structTable->end() + && existing->second.scope == scope + && addedDeclConflicts( existing->second.decl, decl ) ) return; + } + + lazyInitScope(); + ++*stats().map_mutations; + structTable = structTable->set( id, scoped{ decl, scope } ); +} + +void SymbolTable::addEnum( const EnumDecl *decl ) { + ++*stats().add_calls; + const std::string &id = decl->name; + + if ( ! enumTable ) { + enumTable = EnumTable::new_ptr(); + } else { + ++*stats().map_lookups; + auto existing = enumTable->find( id ); + if ( existing != enumTable->end() + && existing->second.scope == scope + && addedDeclConflicts( existing->second.decl, decl ) ) return; + } + + lazyInitScope(); + ++*stats().map_mutations; + enumTable = enumTable->set( id, scoped{ decl, scope } ); +} + +void SymbolTable::addUnion( const std::string &id ) { + addUnion( new UnionDecl( CodeLocation{}, id ) ); +} + +void SymbolTable::addUnion( const UnionDecl * decl ) { + ++*stats().add_calls; + const std::string &id = decl->name; + + if ( ! unionTable ) { + unionTable = UnionTable::new_ptr(); + } else { + ++*stats().map_lookups; + auto existing = unionTable->find( id ); + if ( existing != unionTable->end() + && existing->second.scope == scope + && addedDeclConflicts( existing->second.decl, decl ) ) return; + } + + lazyInitScope(); + ++*stats().map_mutations; + unionTable = unionTable->set( id, scoped{ decl, scope } ); +} + +void SymbolTable::addTrait( const TraitDecl * decl ) { + ++*stats().add_calls; + const std::string &id = decl->name; + + if ( ! traitTable ) { + traitTable = TraitTable::new_ptr(); + } else { + ++*stats().map_lookups; + auto existing = traitTable->find( id ); + if ( existing != traitTable->end() + && existing->second.scope == scope + && addedDeclConflicts( existing->second.decl, decl ) ) return; + } + + lazyInitScope(); + ++*stats().map_mutations; + traitTable = traitTable->set( id, scoped{ decl, scope } ); +} + + +void SymbolTable::addWith( const std::vector< ptr > & withExprs, const Node * withStmt ) { + for ( const Expr * expr : withExprs ) { + if ( ! expr->result ) continue; + const Type * resTy = expr->result->stripReferences(); + auto aggrType = dynamic_cast< const ReferenceToType * >( resTy ); + assertf( aggrType, "WithStmt expr has non-aggregate type: %s", + toString( expr->result ).c_str() ); + const AggregateDecl * aggr = aggrType->aggr(); + assertf( aggr, "WithStmt has null aggregate from type: %s", + toString( expr->result ).c_str() ); + + addMembers( aggr, expr, OnConflict::deleteWith( withStmt ) ); + } +} + +void SymbolTable::addIds( const std::vector< ptr > & decls ) { + for ( const DeclWithType * decl : decls ) { addId( decl ); } +} + +void SymbolTable::addTypes( const std::vector< ptr > & tds ) { + for ( const TypeDecl * td : tds ) { + addType( td ); + addIds( td->assertions ); + } +} + +void SymbolTable::addFunctionType( const FunctionType * ftype ) { + addTypes( ftype->forall ); + addIds( ftype->returns ); + addIds( ftype->params ); +} + +void SymbolTable::lazyInitScope() { + // do nothing if already in represented scope + if ( repScope == scope ) return; + + ++*stats().lazy_scopes; + // create rollback + prevScope = std::make_shared( *this ); + // update repScope + repScope = scope; +} + +const ast::SymbolTable * SymbolTable::atScope( unsigned long target ) const { + // by lazy construction, final symtab in list has repScope 0, cannot be > target + // otherwise, will find first scope representing the target + const SymbolTable * symtab = this; + while ( symtab->repScope > target ) { + symtab = symtab->prevScope.get(); + } + return symtab; +} + +namespace { + /// gets the base type of the first parameter; decl must be a ctor/dtor/assignment function + std::string getOtypeKey( const FunctionDecl * function ) { + const auto & params = function->type->params; + assert( ! params.empty() ); + // use base type of pointer, so that qualifiers on the pointer type aren't considered. + const Type * base = InitTweak::getPointerBase( params.front()->get_type() ); + assert( base ); + return Mangle::mangle( base ); + } + + /// gets the declaration for the function acting on a type specified by otype key, + /// nullptr if none such + const FunctionDecl * getFunctionForOtype( + const DeclWithType * decl, const std::string & otypeKey ) { + auto func = dynamic_cast< const FunctionDecl * >( decl ); + if ( ! func || otypeKey != getOtypeKey( func ) ) return nullptr; + return func; + } +} + +bool SymbolTable::removeSpecialOverrides( + SymbolTable::IdData & data, SymbolTable::MangleTable::Ptr & mangleTable ) { + // if a type contains user defined ctor/dtor/assign, then special rules trigger, which + // determine the set of ctor/dtor/assign that can be used by the requester. In particular, + // if the user defines a default ctor, then the generated default ctor is unavailable, + // likewise for copy ctor and dtor. If the user defines any ctor/dtor, then no generated + // field ctors are available. If the user defines any ctor then the generated default ctor + // is unavailable (intrinsic default ctor must be overridden exactly). If the user defines + // anything that looks like a copy constructor, then the generated copy constructor is + // unavailable, and likewise for the assignment operator. + + // only relevant on function declarations + const FunctionDecl * function = data.id.as< FunctionDecl >(); + if ( ! function ) return true; + // only need to perform this check for constructors, destructors, and assignment functions + if ( ! CodeGen::isCtorDtorAssign( data.id->name ) ) return true; + + // set up information for this type + bool dataIsUserDefinedFunc = ! function->linkage.is_overrideable; + bool dataIsCopyFunc = InitTweak::isCopyFunction( function ); + std::string dataOtypeKey = getOtypeKey( function ); + + if ( dataIsUserDefinedFunc && dataIsCopyFunc ) { + // this is a user-defined copy function + // if this is the first such, delete/remove non-user-defined overloads as needed + std::vector< std::string > removed; + std::vector< MangleTable::value_type > deleted; + bool alreadyUserDefinedFunc = false; + + for ( const auto& entry : *mangleTable ) { + // skip decls that aren't functions or are for the wrong type + const FunctionDecl * decl = getFunctionForOtype( entry.second.id, dataOtypeKey ); + if ( ! decl ) continue; + + bool isCopyFunc = InitTweak::isCopyFunction( decl ); + if ( ! decl->linkage.is_overrideable ) { + // matching user-defined function + if ( isCopyFunc ) { + // mutation already performed, return early + return true; + } else { + // note that non-copy deletions already performed + alreadyUserDefinedFunc = true; + } + } else { + // non-user-defined function; mark for deletion/removal as appropriate + if ( isCopyFunc ) { + removed.push_back( entry.first ); + } else if ( ! alreadyUserDefinedFunc ) { + deleted.push_back( entry ); + } + } + } + + // perform removals from mangle table, and deletions if necessary + for ( const auto& key : removed ) { + ++*stats().map_mutations; + mangleTable = mangleTable->erase( key ); + } + if ( ! alreadyUserDefinedFunc ) for ( const auto& entry : deleted ) { + ++*stats().map_mutations; + mangleTable = mangleTable->set( entry.first, IdData{ entry.second, function } ); + } + } else if ( dataIsUserDefinedFunc ) { + // this is a user-defined non-copy function + // if this is the first user-defined function, delete non-user-defined overloads + std::vector< MangleTable::value_type > deleted; + + for ( const auto& entry : *mangleTable ) { + // skip decls that aren't functions or are for the wrong type + const FunctionDecl * decl = getFunctionForOtype( entry.second.id, dataOtypeKey ); + if ( ! decl ) continue; + + // exit early if already a matching user-defined function; + // earlier function will have mutated table + if ( ! decl->linkage.is_overrideable ) return true; + + // skip mutating intrinsic functions + if ( decl->linkage == Linkage::Intrinsic ) continue; + + // user-defined non-copy functions do not override copy functions + if ( InitTweak::isCopyFunction( decl ) ) continue; + + // this function to be deleted after mangleTable iteration is complete + deleted.push_back( entry ); + } + + // mark deletions to update mangle table + // this needs to be a separate loop because of iterator invalidation + for ( const auto& entry : deleted ) { + ++*stats().map_mutations; + mangleTable = mangleTable->set( entry.first, IdData{ entry.second, function } ); + } + } else if ( function->linkage != Linkage::Intrinsic ) { + // this is an overridable generated function + // if there already exists a matching user-defined function, delete this appropriately + for ( const auto& entry : *mangleTable ) { + // skip decls that aren't functions or are for the wrong type + const FunctionDecl * decl = getFunctionForOtype( entry.second.id, dataOtypeKey ); + if ( ! decl ) continue; + + // skip non-user-defined functions + if ( decl->linkage.is_overrideable ) continue; + + if ( dataIsCopyFunc ) { + // remove current function if exists a user-defined copy function + // since the signatures for copy functions don't need to match exactly, using + // a delete statement is the wrong approach + if ( InitTweak::isCopyFunction( decl ) ) return false; + } else { + // mark current function deleted by first user-defined function found + data.deleter = decl; + return true; + } + } + } + + // nothing (more) to fix, return true + return true; +} + +namespace { + /// true iff the declaration represents a function + bool isFunction( const DeclWithType * decl ) { + return GenPoly::getFunctionType( decl->get_type() ); + } + + bool isObject( const DeclWithType * decl ) { return ! isFunction( decl ); } + + /// true if the declaration represents a definition instead of a forward decl + bool isDefinition( const DeclWithType * decl ) { + if ( auto func = dynamic_cast< const FunctionDecl * >( decl ) ) { + // a function is a definition if it has a body + return func->stmts; + } else { + // an object is a definition if it is not marked extern + return ! decl->storage.is_extern; + } + } +} + +bool SymbolTable::addedIdConflicts( + const SymbolTable::IdData & existing, const DeclWithType * added, + SymbolTable::OnConflict handleConflicts, const Node * deleter ) { + // if we're giving the same name mangling to things of different types then there is something + // wrong + assert( (isObject( added ) && isObject( existing.id ) ) + || ( isFunction( added ) && isFunction( existing.id ) ) ); + + if ( existing.id->linkage.is_overrideable ) { + // new definition shadows the autogenerated one, even at the same scope + return false; + } else if ( existing.id->linkage.is_mangled + || ResolvExpr::typesCompatible( + added->get_type(), existing.id->get_type(), SymbolTable{} ) ) { + + // it is a conflict if one declaration is deleted and the other is not + if ( deleter && ! existing.deleter ) { + if ( handleConflicts.mode == OnConflict::Error ) { + SemanticError( added, "deletion of defined identifier " ); + } + return true; + } else if ( ! deleter && existing.deleter ) { + if ( handleConflicts.mode == OnConflict::Error ) { + SemanticError( added, "definition of deleted identifier " ); + } + return true; + } + + // it is a conflict if both declarations are definitions + if ( isDefinition( added ) && isDefinition( existing.id ) ) { + if ( handleConflicts.mode == OnConflict::Error ) { + SemanticError( added, + isFunction( added ) ? + "duplicate function definition for " : + "duplicate object definition for " ); + } + return true; + } + } else { + if ( handleConflicts.mode == OnConflict::Error ) { + SemanticError( added, "duplicate definition for " ); + } + return true; + } + + return true; +} + +void SymbolTable::addId( + const DeclWithType * decl, SymbolTable::OnConflict handleConflicts, const Expr * baseExpr, + const Node * deleter ) { + ++*stats().add_calls; + const std::string &name = decl->name; + if ( name == "" ) return; + + std::string mangleName; + if ( decl->linkage.is_overrideable ) { + // mangle the name without including the appropriate suffix, so overridable routines + // are placed into the same "bucket" as their user defined versions. + mangleName = Mangle::mangle( decl, Mangle::Mode{ Mangle::NoOverrideable } ); + } else { + mangleName = Mangle::mangle( decl ); + } + + // this ensures that no two declarations with the same unmangled name at the same scope + // both have C linkage + if ( decl->linkage.is_mangled ) { + // Check that a Cforall declaration doesn't override any C declaration + if ( hasCompatibleCDecl( name, mangleName ) ) { + SemanticError( decl, "Cforall declaration hides C function " ); + } + } else { + // NOTE: only correct if name mangling is completely isomorphic to C + // type-compatibility, which it may not be. + if ( hasIncompatibleCDecl( name, mangleName ) ) { + SemanticError( decl, "conflicting overload of C function " ); + } + } + + // ensure tables exist and add identifier + MangleTable::Ptr mangleTable; + if ( ! idTable ) { + idTable = IdTable::new_ptr(); + mangleTable = MangleTable::new_ptr(); + } else { + ++*stats().map_lookups; + auto decls = idTable->find( name ); + if ( decls == idTable->end() ) { + mangleTable = MangleTable::new_ptr(); + } else { + mangleTable = decls->second; + // skip in-scope repeat declarations of same identifier + ++*stats().map_lookups; + auto existing = mangleTable->find( mangleName ); + if ( existing != mangleTable->end() + && existing->second.scope == scope + && existing->second.id ) { + if ( addedIdConflicts( existing->second, decl, handleConflicts, deleter ) ) { + if ( handleConflicts.mode == OnConflict::Delete ) { + // set delete expression for conflicting identifier + lazyInitScope(); + *stats().map_mutations += 2; + idTable = idTable->set( + name, + mangleTable->set( + mangleName, + IdData{ existing->second, handleConflicts.deleter } ) ); + } + return; + } + } + } + } + + // add/overwrite with new identifier + lazyInitScope(); + IdData data{ decl, baseExpr, deleter, scope }; + // Ensure that auto-generated ctor/dtor/assignment are deleted if necessary + if ( ! removeSpecialOverrides( data, mangleTable ) ) return; + *stats().map_mutations += 2; + idTable = idTable->set( name, mangleTable->set( mangleName, std::move(data) ) ); +} + +void SymbolTable::addMembers( + const AggregateDecl * aggr, const Expr * expr, SymbolTable::OnConflict handleConflicts ) { + for ( const Decl * decl : aggr->members ) { + if ( auto dwt = dynamic_cast< const DeclWithType * >( decl ) ) { + addId( dwt, handleConflicts, expr ); + if ( dwt->name == "" ) { + const Type * t = dwt->get_type()->stripReferences(); + if ( auto rty = dynamic_cast( t ) ) { + if ( ! dynamic_cast(rty) + && ! dynamic_cast(rty) ) continue; + ResolvExpr::Cost cost = ResolvExpr::Cost::zero; + const Expr * base = ResolvExpr::referenceToRvalueConversion( expr, cost ); + addMembers( + rty->aggr(), new MemberExpr{ base->location, dwt, base }, handleConflicts ); + } + } + } + } +} + +bool SymbolTable::hasCompatibleCDecl( const std::string &id, const std::string &mangleName ) const { + if ( ! idTable ) return false; + + ++*stats().map_lookups; + auto decls = idTable->find( id ); + if ( decls == idTable->end() ) return false; + + for ( auto decl : *(decls->second) ) { + // skip other scopes (hidden by this decl) + if ( decl.second.scope != scope ) continue; + // check for C decl with compatible type (by mangleName) + if ( ! decl.second.id->linkage.is_mangled && decl.first == mangleName ) return true; + } + + return false; +} + +bool SymbolTable::hasIncompatibleCDecl( const std::string &id, const std::string &mangleName ) const { + if ( ! idTable ) return false; + + ++*stats().map_lookups; + auto decls = idTable->find( id ); + if ( decls == idTable->end() ) return false; + + for ( auto decl : *(decls->second) ) { + // skip other scopes (hidden by this decl) + if ( decl.second.scope != scope ) continue; + // check for C decl with incompatible type (by manglename) + if ( ! decl.second.id->linkage.is_mangled && decl.first != mangleName ) return true; + } + + return false; +} + +} + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/AST/SymbolTable.hpp =================================================================== --- src/AST/SymbolTable.hpp (revision d76c588058daa6269114595a571223a110ced0ab) +++ src/AST/SymbolTable.hpp (revision d76c588058daa6269114595a571223a110ced0ab) @@ -0,0 +1,203 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// SymbolTable.hpp -- +// +// Author : Aaron B. Moss +// Created On : Wed May 29 11:00:00 2019 +// Last Modified By : Aaron B. Moss +// Last Modified On : Wed May 29 11:00:00 2019 +// Update Count : 1 +// + +#pragma once + +#include // for shared_ptr, enable_shared_from_this +#include + +#include "Fwd.hpp" +#include "Node.hpp" // for ptr, readonly +#include "Common/CodeLocation.h" +#include "Common/PersistentMap.h" + +namespace ResolvExpr { + class Cost; +} + +namespace ast { + +/// Builds and stores the symbol table, mapping identifiers to declarations. +class SymbolTable final : public std::enable_shared_from_this { +public: + /// Stored information about a declaration + struct IdData { + readonly id = nullptr; ///< Identifier of declaration + readonly baseExpr = nullptr; ///< Implied containing aggregate (from WithExpr) + readonly deleter = nullptr; ///< Node deleting this declaration (if non-null) + unsigned long scope = 0; ///< Scope of identifier + + IdData() = default; + IdData( const DeclWithType * i, const Expr * base, const Node * del, unsigned long s ) + : id( i ), baseExpr( base ), deleter( del ), scope( s ) {} + + /// Modify an existing node with a new deleter + IdData( const IdData & o, const Node * del ) + : id( o.id ), baseExpr( o.baseExpr ), deleter( del ), scope( o.scope ) {} + + /// Constructs an expression referring to this identifier. + /// Increments `cost` by cost of reference conversion + Expr * combine( const CodeLocation & loc, ResolvExpr::Cost & cost ) const; + }; + +private: + /// wraps a reference to D with a scope + template + struct scoped { + readonly decl; ///< wrapped declaration + unsigned long scope; ///< scope of this declaration + + scoped(const D * d, unsigned long s) : decl(d), scope(s) {} + }; + + using MangleTable = PersistentMap< std::string, IdData >; + using IdTable = PersistentMap< std::string, MangleTable::Ptr >; + using TypeTable = PersistentMap< std::string, scoped >; + using StructTable = PersistentMap< std::string, scoped >; + using EnumTable = PersistentMap< std::string, scoped >; + using UnionTable = PersistentMap< std::string, scoped >; + using TraitTable = PersistentMap< std::string, scoped >; + + IdTable::Ptr idTable; ///< identifier namespace + TypeTable::Ptr typeTable; ///< type namespace + StructTable::Ptr structTable; ///< struct namespace + EnumTable::Ptr enumTable; ///< enum namespace + UnionTable::Ptr unionTable; ///< union namespace + TraitTable::Ptr traitTable; ///< trait namespace + + using Ptr = std::shared_ptr; + + Ptr prevScope; ///< Indexer for parent scope + unsigned long scope; ///< Scope index of this indexer + unsigned long repScope; ///< Scope index of currently represented scope + +public: + explicit SymbolTable(); + ~SymbolTable(); + + // when using an indexer manually (e.g., within a mutator traversal), it is necessary to + // tell the indexer explicitly when scopes begin and end + void enterScope(); + void leaveScope(); + + /// Gets all declarations with the given ID + std::vector lookupId( const std::string &id ) const; + /// Gets the top-most type declaration with the given ID + const NamedTypeDecl * lookupType( const std::string &id ) const; + /// Gets the top-most struct declaration with the given ID + const StructDecl * lookupStruct( const std::string &id ) const; + /// Gets the top-most enum declaration with the given ID + const EnumDecl * lookupEnum( const std::string &id ) const; + /// Gets the top-most union declaration with the given ID + const UnionDecl * lookupUnion( const std::string &id ) const; + /// Gets the top-most trait declaration with the given ID + const TraitDecl * lookupTrait( const std::string &id ) const; + + /// Gets the type declaration with the given ID at global scope + const NamedTypeDecl * globalLookupType( const std::string &id ) const; + /// Gets the struct declaration with the given ID at global scope + const StructDecl * globalLookupStruct( const std::string &id ) const; + /// Gets the union declaration with the given ID at global scope + const UnionDecl * globalLookupUnion( const std::string &id ) const; + /// Gets the enum declaration with the given ID at global scope + const EnumDecl * globalLookupEnum( const std::string &id ) const; + + /// Adds an identifier declaration to the symbol table + void addId( const DeclWithType * decl, const Expr * baseExpr = nullptr ); + /// Adds a deleted identifier declaration to the symbol table + void addDeletedId( const DeclWithType * decl, const Node * deleter ); + + /// Adds a type to the symbol table + void addType( const NamedTypeDecl * decl ); + /// Adds a struct declaration to the symbol table by name + void addStruct( const std::string &id ); + /// Adds a struct declaration to the symbol table + void addStruct( const StructDecl * decl ); + /// Adds an enum declaration to the symbol table + void addEnum( const EnumDecl *decl ); + /// Adds a union declaration to the symbol table by name + void addUnion( const std::string &id ); + /// Adds a union declaration to the symbol table + void addUnion( const UnionDecl * decl ); + /// Adds a trait declaration to the symbol table + void addTrait( const TraitDecl * decl ); + + /// adds all of the IDs from WithStmt exprs + void addWith( const std::vector< ptr > & withExprs, const Node * withStmt ); + + /// convenience function for adding a list of Ids to the indexer + void addIds( const std::vector< ptr > & decls ); + + /// convenience function for adding a list of forall parameters to the indexer + void addTypes( const std::vector< ptr > & tds ); + + /// convenience function for adding all of the declarations in a function type to the indexer + void addFunctionType( const FunctionType * ftype ); + +private: + /// Ensures that a proper backtracking scope exists before a mutation + void lazyInitScope(); + + /// Gets the symbol table at a given scope + const SymbolTable * atScope( unsigned long i ) const; + + /// Removes matching autogenerated constructors and destructors so that they will not be + /// selected. If returns false, passed decl should not be added. + bool removeSpecialOverrides( IdData & decl, MangleTable::Ptr & mangleTable ); + + /// Options for handling identifier conflicts + struct OnConflict { + enum { + Error, ///< Throw a semantic error + Delete ///< Delete the earlier version with the delete statement + } mode; + const Node * deleter; ///< Statement that deletes this expression + + private: + OnConflict() : mode(Error), deleter(nullptr) {} + OnConflict( const Node * d ) : mode(Delete), deleter(d) {} + public: + OnConflict( const OnConflict& ) = default; + + static OnConflict error() { return {}; } + static OnConflict deleteWith( const Node * d ) { return { d }; } + }; + + /// true if the existing identifier conflicts with the added identifier + bool addedIdConflicts( + const IdData & existing, const DeclWithType * added, OnConflict handleConflicts, + const Node * deleter ); + + /// common code for addId, addDeletedId, etc. + void addId( + const DeclWithType * decl, OnConflict handleConflicts, const Expr * baseExpr = nullptr, + const Node * deleter = nullptr ); + + /// adds all of the members of the Aggregate (addWith helper) + void addMembers( const AggregateDecl * aggr, const Expr * expr, OnConflict handleConflicts ); + + /// returns true if there exists a declaration with C linkage and the given name with the same mangled name + bool hasCompatibleCDecl( const std::string &id, const std::string &mangleName ) const; + /// returns true if there exists a declaration with C linkage and the given name with a different mangled name + bool hasIncompatibleCDecl( const std::string &id, const std::string &mangleName ) const; +}; + +} + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/AST/Type.cpp =================================================================== --- src/AST/Type.cpp (revision 2c04369a0b21c0ce78ea35835ad1f3d320c8813a) +++ src/AST/Type.cpp (revision d76c588058daa6269114595a571223a110ced0ab) @@ -27,10 +27,10 @@ namespace ast { -const Type * Type::getComponent( unsigned i ) { +const Type * Type::getComponent( unsigned i ) const { assertf( size() == 1 && i == 0, "Type::getComponent was called with size %d and index %d\n", size(), i ); return this; } -const Type * Type::stripDeclarator() { +const Type * Type::stripDeclarator() const { const Type * t; const Type * a; @@ -39,5 +39,5 @@ } -const Type * Type::stripReferences() { +const Type * Type::stripReferences() const { const Type * t; const ReferenceType * r; Index: src/AST/Type.hpp =================================================================== --- src/AST/Type.hpp (revision 2c04369a0b21c0ce78ea35835ad1f3d320c8813a) +++ src/AST/Type.hpp (revision d76c588058daa6269114595a571223a110ced0ab) @@ -25,5 +25,5 @@ #include "Decl.hpp" // for AggregateDecl subclasses #include "Fwd.hpp" -#include "Node.hpp" // for Node, ptr +#include "Node.hpp" // for Node, ptr, ptr_base #include "TypeVar.hpp" #include "Visitor.hpp" @@ -58,10 +58,10 @@ virtual bool isVoid() const { return size() == 0; } /// Get the i'th component of this type - virtual const Type * getComponent( unsigned i ); + virtual const Type * getComponent( unsigned i ) const; /// type without outer pointers and arrays - const Type * stripDeclarator(); + const Type * stripDeclarator() const; /// type without outer references - const Type * stripReferences(); + const Type * stripReferences() const; /// number of reference occuring consecutively on the outermost layer of this type /// (i.e. do not count references nested within other types) @@ -75,4 +75,16 @@ MUTATE_FRIEND }; + +/// Set the `is_lvalue` qualifier on this type, cloning only if necessary +template< enum Node::ref_type ref_t > +void add_lvalue( ptr_base< Type, ref_t > & p ) { + if ( ! p->qualifiers.is_lvalue ) p.get_and_mutate()->qualifiers.is_lvalue = true; +} + +/// Clear the qualifiers on this type, cloning only if necessary +template< enum Node::ref_type ref_t > +void clear_qualifiers( ptr_base< Type, ref_t > & p ) { + if ( p->qualifiers != CV::Qualifiers{} ) p.get_and_mutate()->qualifiers = CV::Qualifiers{}; +} /// `void` @@ -437,5 +449,5 @@ unsigned size() const override { return types.size(); } - const Type * getComponent( unsigned i ) override { + const Type * getComponent( unsigned i ) const override { assertf( i < size(), "TupleType::getComponent: index %d must be less than size %d", i, size() ); Index: src/AST/TypeEnvironment.cpp =================================================================== --- src/AST/TypeEnvironment.cpp (revision d76c588058daa6269114595a571223a110ced0ab) +++ src/AST/TypeEnvironment.cpp (revision d76c588058daa6269114595a571223a110ced0ab) @@ -0,0 +1,469 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// TypeEnvironment.cpp -- +// +// Author : Aaron B. Moss +// Created On : Wed May 29 11:00:00 2019 +// Last Modified By : Aaron B. Moss +// Last Modified On : Wed May 29 11:00:00 2019 +// Update Count : 1 +// + +#include "TypeEnvironment.hpp" + +#include // for copy +#include +#include // for ostream_iterator +#include +#include +#include // for move +#include + +#include "Decl.hpp" +#include "Node.hpp" +#include "Pass.hpp" +#include "Print.hpp" +#include "Type.hpp" +#include "Common/Indenter.h" +#include "ResolvExpr/typeops.h" // for occurs +#include "ResolvExpr/WidenMode.h" +#include "ResolvExpr/Unify.h" // for unifyInexact +#include "Tuples/Tuples.h" // for isTtype + +using ResolvExpr::WidenMode; + +namespace ast { + +void print( std::ostream & out, const AssertionSet & assns, Indenter indent ) { + for ( const auto & i : assns ) { + print( out, i.first, indent ); + out << ( i.second.isUsed ? " (used)" : " (not used)" ); + } +} + +void print( std::ostream & out, const OpenVarSet & openVars, Indenter indent ) { + out << indent; + bool first = true; + for ( const auto & i : openVars ) { + if ( first ) { first = false; } else { out << ' '; } + out << i.first << "(" << i.second << ")"; + } +} + +void print( std::ostream & out, const EqvClass & clz, Indenter indent ) { + out << "( "; + std::copy( clz.vars.begin(), clz.vars.end(), std::ostream_iterator< std::string >( out, " " ) ); + out << ")"; + + if ( clz.bound ) { + out << " -> "; + print( out, clz.bound, indent+1 ); + } + + if ( ! clz.allowWidening ) { + out << " (no widening)"; + } + + out << std::endl; +} + +const EqvClass * TypeEnvironment::lookup( const std::string & var ) const { + for ( ClassList::const_iterator i = env.begin(); i != env.end(); ++i ) { + if ( i->vars.find( var ) != i->vars.end() ) return &*i; + } + return nullptr; +} + +namespace { + /// Removes any class from env that intersects eqvClass + void filterOverlappingClasses( std::list & env, const EqvClass & eqvClass ) { + auto i = env.begin(); + while ( i != env.end() ) { + auto next = i; ++next; // save next node in case of erasure + + for ( const auto & v : eqvClass.vars ) { + if ( i->vars.count( v ) ) { + env.erase( i ); // remove overlapping class + break; // done with this class + } + } + + i = next; // go to next node even if this removed + } + } +} + +void TypeEnvironment::add( const ParameterizedType::ForallList & tyDecls ) { + for ( const TypeDecl * tyDecl : tyDecls ) { + env.emplace_back( tyDecl ); + } +} + +void TypeEnvironment::add( const TypeSubstitution & sub ) { + for ( const auto p : sub ) { + add( EqvClass{ p.first, p.second } ); + } +} + +void TypeEnvironment::writeToSubstitution( TypeSubstitution & sub ) const { + for ( const auto & clz : env ) { + std::string clzRep; + for ( const auto & var : clz.vars ) { + if ( clz.bound ) { + sub.add( var, clz.bound ); + } else if ( clzRep.empty() ) { + clzRep = var; + } else { + sub.add( var, new TypeInstType{ clzRep, clz.data.kind } ); + } + } + } + sub.normalize(); +} + +void TypeEnvironment::simpleCombine( const TypeEnvironment & o ) { + env.insert( env.end(), o.env.begin(), o.env.end() ); +} + +namespace { + /// Implements occurs check by traversing type + struct Occurs : public ast::WithVisitorRef { + bool result; + std::set< std::string > vars; + const TypeEnvironment & tenv; + + Occurs( const std::string & var, const TypeEnvironment & env ) + : result( false ), vars(), tenv( env ) { + if ( const EqvClass * clz = tenv.lookup( var ) ) { + vars = clz->vars; + } else { + vars.emplace( var ); + } + } + + void previsit( const TypeInstType * typeInst ) { + if ( vars.count( typeInst->name ) ) { + result = true; + } else if ( const EqvClass * clz = tenv.lookup( typeInst->name ) ) { + if ( clz->bound ) { + clz->bound->accept( *visitor ); + } + } + } + }; + + /// true if `var` occurs in `ty` under `env` + bool occurs( const Type * ty, const std::string & var, const TypeEnvironment & env ) { + Pass occur{ var, env }; + maybe_accept( ty, occur ); + return occur.pass.result; + } +} + +bool TypeEnvironment::combine( + const TypeEnvironment & o, OpenVarSet & openVars, const SymbolTable & symtab ) { + // short-circuit easy cases + if ( o.empty() ) return true; + if ( empty() ) { + simpleCombine( o ); + return true; + } + + // merge classes + for ( const EqvClass & c : o.env ) { + // index of typeclass in local environment bound to c + auto rt = env.end(); + + // look for first existing bound variable + auto vt = c.vars.begin(); + for ( ; vt != c.vars.end(); ++vt ) { + rt = internal_lookup( *vt ); + if ( rt != env.end() ) break; + } + + if ( rt != env.end() ) { // c needs to be merged into *rt + EqvClass & r = *rt; + // merge bindings + if ( ! mergeBound( r, c, openVars, symtab ) ) return false; + // merge previous unbound variables into this class, checking occurs if needed + if ( r.bound ) for ( const auto & u : c.vars ) { + if ( occurs( r.bound, u, *this ) ) return false; + r.vars.emplace( u ); + } else { r.vars.insert( c.vars.begin(), vt ); } + // merge subsequent variables into this class (skipping *vt, already there) + while ( ++vt != c.vars.end() ) { + auto st = internal_lookup( *vt ); + if ( st == env.end() ) { + // unbound, safe to add if occurs + if ( r.bound && occurs( r.bound, *vt, *this ) ) return false; + r.vars.emplace( *vt ); + } else if ( st != rt ) { + // bound, but not to the same class + if ( ! mergeClasses( rt, st, openVars, symtab ) ) return false; + } // ignore bound into the same class + } + } else { // no variables in c bound; just copy up + env.emplace_back( c ); + } + } + + // merged all classes + return true; +} + +void TypeEnvironment::extractOpenVars( OpenVarSet & openVars ) const { + for ( const auto & clz : env ) { + for ( const auto & var : clz.vars ) { + openVars[ var ] = clz.data; + } + } +} + +void TypeEnvironment::addActual( const TypeEnvironment & actualEnv, OpenVarSet & openVars ) { + for ( const auto & clz : actualEnv ) { + EqvClass c = clz; + c.allowWidening = false; + for ( const auto & var : c.vars ) { + openVars[ var ] = c.data; + } + env.emplace_back( std::move(c) ); + } +} + +namespace { + /// true if a type is a function type + bool isFtype( const Type * type ) { + if ( dynamic_cast< const FunctionType * >( type ) ) { + return true; + } else if ( auto typeInst = dynamic_cast< const TypeInstType * >( type ) ) { + return typeInst->kind == TypeVar::Ftype; + } else return false; + } + + /// true if the given type can be bound to the given type variable + bool tyVarCompatible( const TypeDecl::Data & data, const Type * type ) { + switch ( data.kind ) { + case TypeVar::Dtype: + // to bind to an object type variable, the type must not be a function type. + // if the type variable is specified to be a complete type then the incoming + // type must also be complete + // xxx - should this also check that type is not a tuple type and that it's not a ttype? + return ! isFtype( type ) && ( ! data.isComplete || type->isComplete() ); + case TypeVar::Ftype: + return isFtype( type ); + case TypeVar::Ttype: + // ttype unifies with any tuple type + return dynamic_cast< const TupleType * >( type ) || Tuples::isTtype( type ); + default: + assertf(false, "Unhandled tyvar kind: %d", data.kind); + return false; + } + } +} + +bool TypeEnvironment::bindVar( + const TypeInstType * typeInst, const Type * bindTo, const TypeDecl::Data & data, + AssertionSet & need, AssertionSet & have, const OpenVarSet & openVars, + WidenMode widenMode, const SymbolTable & symtab ) { + // remove references from bound type, so that type variables can only bind to value types + bindTo = bindTo->stripReferences(); + auto tyvar = openVars.find( typeInst->name ); + assert( tyvar != openVars.end() ); + if ( ! tyVarCompatible( tyvar->second, bindTo ) ) return false; + if ( occurs( bindTo, typeInst->name, *this ) ) return false; + + auto it = internal_lookup( typeInst->name ); + if ( it != env.end() ) { + if ( it->bound ) { + // attempt to unify equivalence class type with type to bind to. + // equivalence class type has stripped qualifiers which must be restored + const Type * common = nullptr; + ptr newType = it->bound; + newType.get_and_mutate()->qualifiers = typeInst->qualifiers; + if ( unifyInexact( + newType, bindTo, *this, need, have, openVars, + widenMode & WidenMode{ it->allowWidening, true }, symtab, common ) ) { + if ( common ) { + it->bound = common; + clear_qualifiers( it->bound ); + } + } else return false; + } else { + it->bound = bindTo; + clear_qualifiers( it->bound ); + it->allowWidening = widenMode.widenFirst && widenMode.widenSecond; + } + } else { + env.emplace_back( + typeInst->name, bindTo, widenMode.widenFirst && widenMode.widenSecond, data ); + } + return true; +} + +bool TypeEnvironment::bindVarToVar( + const TypeInstType * var1, const TypeInstType * var2, TypeDecl::Data && data, + AssertionSet & need, AssertionSet & have, const OpenVarSet & openVars, + WidenMode widenMode, const SymbolTable & symtab ) { + auto c1 = internal_lookup( var1->name ); + auto c2 = internal_lookup( var2->name ); + + // exit early if variables already bound together + if ( c1 != env.end() && c1 == c2 ) { + c1->allowWidening &= widenMode; + return true; + } + + bool widen1 = false, widen2 = false; + const Type * type1 = nullptr, * type2 = nullptr; + + // check for existing bindings, perform occurs check + if ( c1 != env.end() ) { + if ( c1->bound ) { + if ( occurs( c1->bound, var2->name, *this ) ) return false; + type1 = c1->bound; + } + widen1 = widenMode.widenFirst && c1->allowWidening; + } + if ( c2 != env.end() ) { + if ( c2->bound ) { + if ( occurs( c2->bound, var1->name, *this ) ) return false; + type2 = c2->bound; + } + widen2 = widenMode.widenSecond && c2->allowWidening; + } + + if ( type1 && type2 ) { + // both classes bound, merge if bound types can be unified + ptr newType1{ type1 }, newType2{ type2 }; + WidenMode newWidenMode{ widen1, widen2 }; + const Type * common = nullptr; + + if ( unifyInexact( + newType1, newType2, *this, need, have, openVars, newWidenMode, symtab, common ) ) { + c1->vars.insert( c2->vars.begin(), c2->vars.end() ); + c1->allowWidening = widen1 && widen2; + if ( common ) { + c1->bound = common; + clear_qualifiers( c1->bound ); + } + c1->data.isComplete |= data.isComplete; + env.erase( c2 ); + } else return false; + } else if ( c1 != env.end() && c2 != env.end() ) { + // both classes exist, at least one unbound, merge unconditionally + if ( type1 ) { + c1->vars.insert( c2->vars.begin(), c2->vars.end() ); + c1->allowWidening = widen1; + c1->data.isComplete |= data.isComplete; + env.erase( c2 ); + } else { + c2->vars.insert( c1->vars.begin(), c1->vars.end() ); + c2->allowWidening = widen2; + c2->data.isComplete |= data.isComplete; + env.erase( c1 ); + } + } else if ( c1 != env.end() ) { + // var2 unbound, add to env[c1] + c1->vars.emplace( var2->name ); + c1->allowWidening = widen1; + c1->data.isComplete |= data.isComplete; + } else if ( c2 != env.end() ) { + // var1 unbound, add to env[c2] + c2->vars.emplace( var1->name ); + c2->allowWidening = widen2; + c2->data.isComplete |= data.isComplete; + } else { + // neither var bound, create new class + env.emplace_back( var1->name, var2->name, widen1 && widen2, data ); + } + + return true; +} + +void TypeEnvironment::forbidWidening() { + for ( EqvClass& c : env ) c.allowWidening = false; +} + +void TypeEnvironment::add( EqvClass && eqvClass ) { + filterOverlappingClasses( env, eqvClass ); + env.emplace_back( std::move(eqvClass) ); +} + +bool TypeEnvironment::mergeBound( + EqvClass & to, const EqvClass & from, OpenVarSet & openVars, const SymbolTable & symtab ) { + if ( from.bound ) { + if ( to.bound ) { + // attempt to unify bound types + ptr toType{ to.bound }, fromType{ from.bound }; + WidenMode widenMode{ to.allowWidening, from.allowWidening }; + const Type * common = nullptr; + AssertionSet need, have; + + if ( unifyInexact( + toType, fromType, *this, need, have, openVars, widenMode, symtab, common ) ) { + // unifies, set common type if necessary + if ( common ) { + to.bound = common; + clear_qualifiers( to.bound ); + } + } else return false; // cannot unify + } else { + to.bound = from.bound; + } + } + + // unify widening if matches + to.allowWidening &= from.allowWidening; + return true; +} + +bool TypeEnvironment::mergeClasses( + ClassList::iterator to, ClassList::iterator from, OpenVarSet & openVars, + const SymbolTable & symtab ) { + EqvClass & r = *to, & s = *from; + + // ensure bounds match + if ( ! mergeBound( r, s, openVars, symtab ) ) return false; + + // check safely bindable + if ( r.bound ) { + for ( const auto & v : s.vars ) if ( occurs( r.bound, v, *this ) ) return false; + } + + // merge classes + r.vars.insert( s.vars.begin(), s.vars.end() ); + r.allowWidening &= s.allowWidening; + env.erase( from ); + + return true; +} + +TypeEnvironment::ClassList::iterator TypeEnvironment::internal_lookup( const std::string & var ) { + for ( ClassList::iterator i = env.begin(); i != env.end(); ++i ) { + if ( i->vars.count( var ) ) return i; + } + return env.end(); +} + +void print( std::ostream & out, const TypeEnvironment & env, Indenter indent ) { + for ( const auto & clz : env ) { + print( out, clz, indent ); + } +} + +std::ostream & operator<<( std::ostream & out, const TypeEnvironment & env ) { + print( out, env ); + return out; +} + +} + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/AST/TypeEnvironment.hpp =================================================================== --- src/AST/TypeEnvironment.hpp (revision d76c588058daa6269114595a571223a110ced0ab) +++ src/AST/TypeEnvironment.hpp (revision d76c588058daa6269114595a571223a110ced0ab) @@ -0,0 +1,223 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// TypeEnvironment.hpp -- +// +// Author : Aaron B. Moss +// Created On : Wed May 29 11:00:00 2019 +// Last Modified By : Aaron B. Moss +// Last Modified On : Wed May 29 11:00:00 2019 +// Update Count : 1 +// + +#pragma once + +#include +#include +#include +#include +#include +#include + +#include "Decl.hpp" +#include "Node.hpp" // for ptr_base, ptr, readonly +#include "SymbolTable.hpp" +#include "Type.hpp" +#include "TypeSubstitution.hpp" +#include "TypeVar.hpp" +#include "Common/Indenter.h" +#include "ResolvExpr/WidenMode.h" + +namespace ast { + +/// Comparator/uniqueness operator for assertion sets. +/// +/// Adding this comparison operator significantly improves assertion satisfaction run time for +/// some cases. The current satisfaction algorithm's speed partially depends on the order of +/// assertions. Assertions which have fewer possible matches should appear before assertions +/// which have more possible matches. This seems to imply that this could be further improved +/// by providing an indexer as an additional argument and ordering based on the number of +/// matches of the same kind (object, function) for the names of the declarations. +/// +/// I've seen a TU go from 54 minutes to 1 minute 34 seconds with the addition of this +/// comparator. +/// +/// Note: since this compares pointers for position, minor changes in the source file that +/// affect memory layout can alter compilation time in unpredictable ways. For example, the +/// placement of a line directive can reorder type pointers with respect to each other so that +/// assertions are seen in different orders, causing a potentially different number of +/// unification calls when resolving assertions. I've seen a TU go from 36 seconds to 27 +/// seconds by reordering line directives alone, so it would be nice to fix this comparison so +/// that assertions compare more consistently. I've tried to modify this to compare on mangle +/// name instead of type as the second comparator, but this causes some assertions to never be +/// recorded. More investigation is needed. +struct AssertCompare { + bool operator()( const DeclWithType * d1, const DeclWithType * d2 ) const { + int cmp = d1->name.compare( d2->name ); + return cmp < 0 || ( cmp == 0 && d1->get_type() < d2->get_type() ); + } +}; + +/// Data for pending assertion satisfaction +struct AssertionSetValue { + bool isUsed; ///< True if assertion needs to be satisfied + UniqueId resnSlot; ///< ID of slot assertion belongs to + + AssertionSetValue() : isUsed(false), resnSlot(0) {} +}; + +/// Set of assertions pending satisfaction +using AssertionSet = std::map< readonly, AssertionSetValue, AssertCompare >; + +/// Set of open variables +using OpenVarSet = std::unordered_map< std::string, TypeDecl::Data >; + +/// Merges one set of open vars into another +/// merges one set of open vars into another +static inline void mergeOpenVars( OpenVarSet& dst, const OpenVarSet& src ) { + for ( const auto& entry : src ) { dst[ entry.first ] = entry.second; } +} + +/// Print an assertion set +void print( std::ostream &, const AssertionSet &, Indenter indent = {} ); +/// Print an open variable set +void print( std::ostream &, const OpenVarSet &, Indenter indent = {} ); + +/// Represents an equivalence class of bound type variables, optionally with the concrete type +/// they bind to. +struct EqvClass { + std::set< std::string > vars; + ptr bound; + bool allowWidening; + TypeDecl::Data data; + + EqvClass() : vars(), bound(), allowWidening( true ), data() {} + + /// Copy-with-bound constructor + EqvClass( const EqvClass & o, const Type * b ) + : vars( o.vars ), bound( b ), allowWidening( o.allowWidening ), data( o.data ) {} + + /// Singleton class constructor from TypeDecl + EqvClass( const TypeDecl * decl ) + : vars{ decl->name }, bound(), allowWidening( true ), data( decl ) {} + + /// Singleton class constructor from substitution + EqvClass( const std::string & v, const Type * b ) + : vars{ v }, bound( b ), allowWidening( false ), data( TypeVar::Dtype, false ) {} + + /// Single-var constructor (strips qualifiers from bound type) + EqvClass( const std::string & v, const Type * b, bool w, const TypeDecl::Data & d ) + : vars{ v }, bound( b ), allowWidening( w ), data( d ) { + clear_qualifiers( bound ); + } + + /// Double-var constructor + EqvClass( const std::string & v, const std::string & u, bool w, const TypeDecl::Data & d ) + : vars{ v, u }, bound(), allowWidening( w ), data( d ) {} + +}; + +void print( std::ostream & out, const EqvClass & clz, Indenter indent = {} ); + +/// A partitioning of type variables into equivalence classes +class TypeEnvironment { + /// The underlying list of equivalence classes + using ClassList = std::list< EqvClass >; + + ClassList env; + +public: + /// Finds the equivalence class containing a variable; nullptr for none such + const EqvClass * lookup( const std::string & var ) const; + + /// Add a new equivalence class for each type variable + void add( const ParameterizedType::ForallList & tyDecls ); + + /// Add a new equivalence class for each branch of the substitution, checking for conflicts + void add( const TypeSubstitution & sub ); + + /// Writes all the substitutions in this environment into a substitution + void writeToSubstitution( TypeSubstitution & sub ) const; + + template< typename node_t, enum Node::ref_type ref_t > + int apply( ptr_base< node_t, ref_t > & type ) const { + TypeSubstitution sub; + writeToSubstitution( sub ); + return sub.apply( type ); + } + + template< typename node_t, enum Node::ref_type ref_t > + int applyFree( ptr_base< node_t, ref_t > & type ) const { + TypeSubstitution sub; + writeToSubstitution( sub ); + return sub.applyFree( type ); + } + + bool empty() const { return env.empty(); } + + /// Concatenate environment onto this one; no safety checks performed + void simpleCombine( const TypeEnvironment & o ); + + /// Merge environment with this one, checking compatibility. + /// Returns false if fails, but does NOT roll back partial changes. + bool combine( const TypeEnvironment & o, OpenVarSet & openVars, const SymbolTable & symtab ); + + /// Add all type variables in environment to open var list + void extractOpenVars( OpenVarSet & openVars ) const; + + /// Iteratively adds the environment of a new actual (with allowWidening = false), + /// and extracts open variables. + void addActual( const TypeEnvironment & actualEnv, OpenVarSet & openVars ); + + /// Binds the type class represented by `typeInst` to the type `bindTo`; will add the class if + /// needed. Returns false on failure. + bool bindVar( + const TypeInstType * typeInst, const Type * bindTo, const TypeDecl::Data & data, + AssertionSet & need, AssertionSet & have, const OpenVarSet & openVars, + ResolvExpr::WidenMode widenMode, const SymbolTable & symtab ); + + /// Binds the type classes represented by `var1` and `var2` together; will add one or both + /// classes if needed. Returns false on failure. + bool bindVarToVar( + const TypeInstType * var1, const TypeInstType * var2, TypeDecl::Data && data, + AssertionSet & need, AssertionSet & have, const OpenVarSet & openVars, + ResolvExpr::WidenMode widenMode, const SymbolTable & symtab ); + + /// Disallows widening for all bindings in the environment + void forbidWidening(); + + using iterator = ClassList::const_iterator; + iterator begin() const { return env.begin(); } + iterator end() const { return env.end(); } + +private: + /// Add an equivalence class to the environment, checking for existing conflicting classes + void add( EqvClass && eqvClass ); + + /// Unifies the type bound of `to` with the type bound of `from`, returning false if fails + bool mergeBound( + EqvClass & to, const EqvClass & from, OpenVarSet & openVars, const SymbolTable & symtab ); + + /// Merges two type classes from local environment, returning false if fails + bool mergeClasses( + ClassList::iterator to, ClassList::iterator from, OpenVarSet & openVars, + const SymbolTable & symtab ); + + /// Private lookup API; returns array index of string, or env.size() for not found + ClassList::iterator internal_lookup( const std::string & ); +}; + +void print( std::ostream & out, const TypeEnvironment & env, Indenter indent = {} ); + +std::ostream & operator<<( std::ostream & out, const TypeEnvironment & env ); + +} + +// Local Variables: // +// tab-width: 4 // +// mode: c++ // +// compile-command: "make install" // +// End: // Index: src/AST/module.mk =================================================================== --- src/AST/module.mk (revision 2c04369a0b21c0ce78ea35835ad1f3d320c8813a) +++ src/AST/module.mk (revision d76c588058daa6269114595a571223a110ced0ab) @@ -28,5 +28,7 @@ AST/Print.cpp \ AST/Stmt.cpp \ + AST/SymbolTable.cpp \ AST/Type.cpp \ + AST/TypeEnvironment.cpp \ AST/TypeSubstitution.cpp Index: src/AST/porting.md =================================================================== --- src/AST/porting.md (revision 2c04369a0b21c0ce78ea35835ad1f3d320c8813a) +++ src/AST/porting.md (revision d76c588058daa6269114595a571223a110ced0ab) @@ -104,4 +104,17 @@ * `LinkageSpec::isMangled(Spec)` etc. => `Spec.is_mangled` etc. * `LinkageSpec::Intrinsic` etc. => `ast::Linkage::Intrinsic` etc. + * Boolean flags to `SymTab::Mangler::mangle` are now a `SymTab::Mangle::Mode` struct + * uses `bitfield` + * Because `Indexer` isn't a terribly evocative name: + * `SymTab::Indexer` => `ast::SymbolTable` + * `SymTab/Indexer.{h,cc}` => `AST/SymbolTable.{hpp,cpp}` + * **TODO** `WithIndexer` => `WithSymbolTable` + * `indexer` => `symTab` + * `IdData::deleteStmt` => `IdData::deleter` + * `lookupId()` now returns a vector rather than an out-param list + * To avoid name collisions: + * `SymTab::Mangler` => `Mangle` + * `ResolvExpr::TypeEnvironment` => `ast::TypeEnvironment` + * in `AST/TypeEnvironment.hpp` * Boolean constructor parameters get replaced with a dedicated flag enum: * e.g. `bool isVarLen;` => `enum LengthFlag { FixedLen, VariableLen };` `LengthFlag isVarLen;` @@ -261,4 +274,21 @@ * feature is `type@thing` e.g. `int@MAX` +`referenceToRvalueConversion` +* now returns `const Expr *` rather than mutating argument + +`printAssertionSet`, `printOpenVarSet` +* `ostream &` now first argument, for consistency + +`EqvClass` +* `type` => `bound` + +`TypeEnvironment` +* `makeSubstitution()` => `writeToSubstitution()` +* `isEmpty()` => `empty()` +* removed `clone()` in favour of explicit copies + +`occurs` +* moved to be helper function in `TypeEnvironment.cpp` (its only use) + [1] https://gcc.gnu.org/onlinedocs/gcc-9.1.0/gcc/Type-Attributes.html#Type-Attributes