Index: src/AST/Convert.cpp =================================================================== --- src/AST/Convert.cpp (revision 7564e10d60badc52604ddc7491f9465ec58795f3) +++ src/AST/Convert.cpp (revision 67130fe7c6ae00bc7c6da280f8b700e5bc850a3c) @@ -47,7 +47,9 @@ namespace { -// This is to preserve the SymTab::dereferenceOperator hack. It does not (and perhaps should not) +// This is to preserve the FindSpecialDecls hack. It does not (and perhaps should not) // allow us to use the same stratagy in the new ast. ast::FunctionDecl * dereferenceOperator = nullptr; +ast::StructDecl * dtorStruct = nullptr; +ast::FunctionDecl * dtorStructDestroy = nullptr; } @@ -75,5 +77,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 ) ); } @@ -176,4 +178,7 @@ Validate::dereferenceOperator = decl; } + if ( dtorStructDestroy == node ) { + Validate::dtorStructDestroy = decl; + } return declWithTypePostamble( decl, node ); } @@ -231,4 +236,9 @@ LinkageSpec::Spec( node->linkage.val ) ); + + if ( dtorStruct == node ) { + Validate::dtorStruct = decl; + } + return aggregatePostamble( decl, node ); } @@ -1445,4 +1455,5 @@ }; cache.emplace( old, decl ); + decl->withExprs = GET_ACCEPT_V(withExprs, Expr); decl->stmts = GET_ACCEPT_1(statements, CompoundStmt); decl->scopeLevel = old->scopeLevel; @@ -1456,4 +1467,8 @@ if ( Validate::dereferenceOperator == old ) { dereferenceOperator = decl; + } + + if ( Validate::dtorStructDestroy == old ) { + dtorStructDestroy = decl; } } @@ -1478,4 +1493,8 @@ this->node = decl; + + if ( Validate::dtorStruct == old ) { + dtorStruct = decl; + } } Index: src/AST/Decl.cpp =================================================================== --- src/AST/Decl.cpp (revision 7564e10d60badc52604ddc7491f9465ec58795f3) +++ src/AST/Decl.cpp (revision 67130fe7c6ae00bc7c6da280f8b700e5bc850a3c) @@ -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 7564e10d60badc52604ddc7491f9465ec58795f3) +++ src/AST/Decl.hpp (revision 67130fe7c6ae00bc7c6da280f8b700e5bc850a3c) @@ -16,4 +16,5 @@ #pragma once +#include #include // for string, to_string #include @@ -101,7 +102,8 @@ ptr bitfieldWidth; - ObjectDecl( const CodeLocation & loc, const std::string & name, const Type * type, Init * init = nullptr, - Storage::Classes storage = {}, Linkage::Spec linkage = Linkage::C, Expr * bitWd = nullptr, - std::vector< ptr > && attrs = {}, Function::Specs fs = {}) + ObjectDecl( const CodeLocation & loc, const std::string & name, const Type * type, + Init * init = nullptr, Storage::Classes storage = {}, Linkage::Spec linkage = Linkage::C, + Expr * bitWd = nullptr, std::vector< ptr > && attrs = {}, + Function::Specs fs = {} ) : DeclWithType( loc, name, storage, linkage, std::move(attrs), fs ), type( type ), init( init ), bitfieldWidth( bitWd ) {} @@ -121,5 +123,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 +174,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 +202,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 7564e10d60badc52604ddc7491f9465ec58795f3) +++ src/AST/Expr.cpp (revision 67130fe7c6ae00bc7c6da280f8b700e5bc850a3c) @@ -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_qualifiers( ret->result, CV::Lvalue ); } } @@ -164,5 +165,5 @@ genericSubsitution( aggregate->result ).apply( result ); // ensure lvalue and appropriate restrictions from aggregate type - result.get_and_mutate()->qualifiers |= aggregate->result->qualifiers | CV::Lvalue; + add_qualifiers( result, aggregate->result->qualifiers | CV::Lvalue ); } @@ -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_qualifiers( result, CV::Lvalue ); } @@ -306,5 +308,6 @@ : Expr( loc ), init( i ) { assert( t && i ); - result.set_and_mutate( t )->set_lvalue( true ); + result = t; + add_qualifiers( result, CV::Lvalue ); } @@ -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_qualifiers( result, CV::Lvalue ); } Index: src/AST/Node.hpp =================================================================== --- src/AST/Node.hpp (revision 7564e10d60badc52604ddc7491f9465ec58795f3) +++ src/AST/Node.hpp (revision 67130fe7c6ae00bc7c6da280f8b700e5bc850a3c) @@ -10,6 +10,6 @@ // Created On : Wed May 8 10:27:04 2019 // Last Modified By : Andrew Beach -// Last Modified On : Thu May 23 16:00:00 2019 -// Update Count : 4 +// Last Modified On : Mon Jun 3 13:26:00 2019 +// Update Count : 5 // @@ -18,4 +18,6 @@ #include #include + +#include "Common/ErrorObjects.h" // for SemanticErrorException namespace ast { @@ -100,4 +102,22 @@ } +/// Call a visitor on a collection of nodes, throwing any exceptions when completed +template< typename Container > +void accept_each( const Container & c, Visitor & v ) { + SemanticErrorException errors; + for ( const auto & i : c ) { + try { + if ( i ) { + i->accept( v ); + } + } catch ( SemanticErrorException & e ) { + errors.append( e ); + } + } + if ( ! errors.isEmpty() ) { + throw errors; + } +} + /// Base class for the smart pointer types /// should never really be used. @@ -107,5 +127,5 @@ ptr_base() : node(nullptr) {} ptr_base( const node_t * n ) : node(n) { if( node ) _inc(node); } - ~ptr_base() { if( node ) _dec(node); } + ~ptr_base() { if( node ) { auto tmp = node; node = nullptr; _dec(tmp); } } ptr_base( const ptr_base & o ) : node(o.node) { @@ -113,7 +133,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 > @@ -129,5 +147,5 @@ template ptr_base & operator=( const o_node_t * node ) { - assign( node ? strict_dynamic_cast(node) : nullptr ); + assign( strict_dynamic_cast(node) ); return *this; } @@ -139,5 +157,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; } @@ -165,4 +186,8 @@ const o_node_t * as() const { return dynamic_cast(node); } + /// wrapper for convenient access to strict_dynamic_cast + template + const o_node_t * strict_as() const { return strict_dynamic_cast(node); } + /// Returns a mutable version of the pointer in this node. node_t * get_and_mutate(); Index: src/AST/Pass.hpp =================================================================== --- src/AST/Pass.hpp (revision 7564e10d60badc52604ddc7491f9465ec58795f3) +++ src/AST/Pass.hpp (revision 67130fe7c6ae00bc7c6da280f8b700e5bc850a3c) @@ -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 7564e10d60badc52604ddc7491f9465ec58795f3) +++ src/AST/Pass.proto.hpp (revision 67130fe7c6ae00bc7c6da280f8b700e5bc850a3c) @@ -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 7564e10d60badc52604ddc7491f9465ec58795f3) +++ src/AST/Print.hpp (revision 67130fe7c6ae00bc7c6da280f8b700e5bc850a3c) @@ -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 67130fe7c6ae00bc7c6da280f8b700e5bc850a3c) +++ src/AST/SymbolTable.cpp (revision 67130fe7c6ae00bc7c6da280f8b700e5bc850a3c) @@ -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 67130fe7c6ae00bc7c6da280f8b700e5bc850a3c) +++ src/AST/SymbolTable.hpp (revision 67130fe7c6ae00bc7c6da280f8b700e5bc850a3c) @@ -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 7564e10d60badc52604ddc7491f9465ec58795f3) +++ src/AST/Type.cpp (revision 67130fe7c6ae00bc7c6da280f8b700e5bc850a3c) @@ -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 7564e10d60badc52604ddc7491f9465ec58795f3) +++ src/AST/Type.hpp (revision 67130fe7c6ae00bc7c6da280f8b700e5bc850a3c) @@ -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" @@ -48,4 +48,5 @@ Type * set_const( bool v ) { qualifiers.is_const = v; return this; } + Type * set_volatile( bool v ) { qualifiers.is_volatile = v; return this; } Type * set_restrict( bool v ) { qualifiers.is_restrict = v; return this; } Type * set_lvalue( bool v ) { qualifiers.is_lvalue = v; return this; } @@ -58,10 +59,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 +76,22 @@ MUTATE_FRIEND }; + +/// Clear/reset the qualifiers on this type, cloning only if necessary +template< enum Node::ref_type ref_t > +void reset_qualifiers( ptr_base< Type, ref_t > & p, CV::Qualifiers q = {} ) { + if ( p->qualifiers.val != q.val ) p.get_and_mutate()->qualifiers = q; +} + +/// Add the specified qualifiers to this type, cloning only if necessary +template< enum Node::ref_type ref_t > +void add_qualifiers( ptr_base< Type, ref_t > & p, CV::Qualifiers q ) { + if ( ( p->qualifiers.val & q.val ) != q.val ) p.get_and_mutate()->qualifiers |= q; +} + +/// Remove the specified qualifiers from this type, cloning only if necessary +template< enum Node::ref_type ref_t > +void remove_qualifiers( ptr_base< Type, ref_t > & p, CV::Qualifiers q ) { + if ( ( p->qualifiers.val & q.val ) != 0 ) p.get_and_mutate()->qualifiers -= q; +} /// `void` @@ -437,5 +456,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 67130fe7c6ae00bc7c6da280f8b700e5bc850a3c) +++ src/AST/TypeEnvironment.cpp (revision 67130fe7c6ae00bc7c6da280f8b700e5bc850a3c) @@ -0,0 +1,471 @@ +// +// 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 & open, Indenter indent ) { + out << indent; + bool first = true; + for ( const auto & i : open ) { + 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 & open, 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, open, 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, open, 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 & open ) const { + for ( const auto & clz : env ) { + for ( const auto & var : clz.vars ) { + open[ var ] = clz.data; + } + } +} + +void TypeEnvironment::addActual( const TypeEnvironment & actualEnv, OpenVarSet & open ) { + for ( const auto & clz : actualEnv ) { + EqvClass c = clz; + c.allowWidening = false; + for ( const auto & var : c.vars ) { + open[ var ] = c.data; + } + env.emplace_back( std::move(c) ); + } +} + +/// 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; +} + +namespace { + /// 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 & open, WidenMode widen, + const SymbolTable & symtab +) { + // remove references from bound type, so that type variables can only bind to value types + ptr target = bindTo->stripReferences(); + auto tyvar = open.find( typeInst->name ); + assert( tyvar != open.end() ); + if ( ! tyVarCompatible( tyvar->second, target ) ) return false; + if ( occurs( target, 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 + ptr common; + ptr newType = it->bound; + reset_qualifiers( newType, typeInst->qualifiers ); + if ( unifyInexact( + newType, target, *this, need, have, open, + widen & WidenMode{ it->allowWidening, true }, symtab, common ) ) { + if ( common ) { + it->bound = std::move(common); + reset_qualifiers( it->bound ); + } + } else return false; + } else { + it->bound = std::move(target); + reset_qualifiers( it->bound ); + it->allowWidening = widen.first && widen.second; + } + } else { + env.emplace_back( + typeInst->name, target, widen.first && widen.second, data ); + } + return true; +} + +bool TypeEnvironment::bindVarToVar( + const TypeInstType * var1, const TypeInstType * var2, TypeDecl::Data && data, + AssertionSet & need, AssertionSet & have, const OpenVarSet & open, + WidenMode widen, 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 &= widen; + 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 = widen.first && c1->allowWidening; + } + if ( c2 != env.end() ) { + if ( c2->bound ) { + if ( occurs( c2->bound, var1->name, *this ) ) return false; + type2 = c2->bound; + } + widen2 = widen.second && c2->allowWidening; + } + + if ( type1 && type2 ) { + // both classes bound, merge if bound types can be unified + ptr newType1{ type1 }, newType2{ type2 }; + WidenMode newWidenMode{ widen1, widen2 }; + ptr common; + + if ( unifyInexact( + newType1, newType2, *this, need, have, open, newWidenMode, symtab, common ) ) { + c1->vars.insert( c2->vars.begin(), c2->vars.end() ); + c1->allowWidening = widen1 && widen2; + if ( common ) { + c1->bound = std::move(common); + reset_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 & open, const SymbolTable & symtab ) { + if ( from.bound ) { + if ( to.bound ) { + // attempt to unify bound types + ptr toType{ to.bound }, fromType{ from.bound }; + WidenMode widen{ to.allowWidening, from.allowWidening }; + ptr common; + AssertionSet need, have; + + if ( unifyInexact( + toType, fromType, *this, need, have, open, widen, symtab, common ) ) { + // unifies, set common type if necessary + if ( common ) { + to.bound = std::move(common); + reset_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 & open, const SymbolTable & symtab +) { + EqvClass & r = *to, & s = *from; + + // ensure bounds match + if ( ! mergeBound( r, s, open, 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 67130fe7c6ae00bc7c6da280f8b700e5bc850a3c) +++ src/AST/TypeEnvironment.hpp (revision 67130fe7c6ae00bc7c6da280f8b700e5bc850a3c) @@ -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 ) { + reset_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 widen, 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 widen, 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/TypeSubstitution.cpp =================================================================== --- src/AST/TypeSubstitution.cpp (revision 7564e10d60badc52604ddc7491f9465ec58795f3) +++ src/AST/TypeSubstitution.cpp (revision 67130fe7c6ae00bc7c6da280f8b700e5bc850a3c) @@ -9,7 +9,7 @@ // Author : Richard C. Bilson // Created On : Mon May 18 07:44:20 2015 -// Last Modified By : Peter A. Buhr -// Last Modified On : Thu Mar 16 15:54:35 2017 -// Update Count : 4 +// Last Modified By : Andrew Beach +// Last Modified On : Mon Jun 3 13:26:00 2017 +// Update Count : 5 // @@ -26,12 +26,5 @@ } -TypeSubstitution::~TypeSubstitution() { - for ( TypeEnvType::iterator i = typeEnv.begin(); i != typeEnv.end(); ++i ) { - delete( i->second ); - } - for ( VarEnvType::iterator i = varEnv.begin(); i != varEnv.end(); ++i ) { - delete( i->second ); - } -} +TypeSubstitution::~TypeSubstitution() {} TypeSubstitution &TypeSubstitution::operator=( const TypeSubstitution &other ) { Index: src/AST/module.mk =================================================================== --- src/AST/module.mk (revision 7564e10d60badc52604ddc7491f9465ec58795f3) +++ src/AST/module.mk (revision 67130fe7c6ae00bc7c6da280f8b700e5bc850a3c) @@ -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 7564e10d60badc52604ddc7491f9465ec58795f3) +++ src/AST/porting.md (revision 67130fe7c6ae00bc7c6da280f8b700e5bc850a3c) @@ -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,25 @@ * 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) + +`WidenMode` +* changed `widenFirst`, `widenSecond` => `first`, `second` +* changed `WidenMode widenMode` => `WidenMode widen` + [1] https://gcc.gnu.org/onlinedocs/gcc-9.1.0/gcc/Type-Attributes.html#Type-Attributes Index: src/GenPoly/GenPoly.cc =================================================================== --- src/GenPoly/GenPoly.cc (revision 7564e10d60badc52604ddc7491f9465ec58795f3) +++ src/GenPoly/GenPoly.cc (revision 67130fe7c6ae00bc7c6da280f8b700e5bc850a3c) @@ -24,4 +24,5 @@ #include // for vector +#include "AST/Type.hpp" #include "GenPoly/ErasableScopedMap.h" // for ErasableScopedMap<>::const_it... #include "ResolvExpr/typeops.h" // for flatten @@ -262,4 +263,12 @@ } else { return dynamic_cast< FunctionType* >( ty ); // pointer if FunctionType, NULL otherwise + } + } + + const ast::FunctionType * getFunctionType( const ast::Type * ty ) { + if ( auto pty = dynamic_cast< const ast::PointerType * >( ty ) ) { + return pty->base.as< ast::FunctionType >(); + } else { + return dynamic_cast< const ast::FunctionType * >( ty ); } } Index: src/GenPoly/GenPoly.h =================================================================== --- src/GenPoly/GenPoly.h (revision 7564e10d60badc52604ddc7491f9465ec58795f3) +++ src/GenPoly/GenPoly.h (revision 67130fe7c6ae00bc7c6da280f8b700e5bc850a3c) @@ -20,4 +20,5 @@ #include "ErasableScopedMap.h" // for ErasableScopedMap +#include "AST/Fwd.hpp" #include "SymTab/Mangler.h" // for Mangler #include "SynTree/Declaration.h" // for TypeDecl::Data, AggregateDecl, Type... @@ -72,4 +73,5 @@ /// Returns a pointer to the base FunctionType if ty is the type of a function (or pointer to one), NULL otherwise FunctionType *getFunctionType( Type *ty ); + const ast::FunctionType * getFunctionType( const ast::Type * ty ); /// If expr (after dereferencing N >= 0 pointers) is a variable expression, returns the variable expression, NULL otherwise; Index: src/InitTweak/FixInit.cc =================================================================== --- src/InitTweak/FixInit.cc (revision 7564e10d60badc52604ddc7491f9465ec58795f3) +++ src/InitTweak/FixInit.cc (revision 67130fe7c6ae00bc7c6da280f8b700e5bc850a3c) @@ -72,4 +72,10 @@ }; + struct StmtExprResult { + static void link( std::list< Declaration * > & translationUnit ); + + void previsit( StmtExpr * stmtExpr ); + }; + struct InsertImplicitCalls : public WithConstTypeSubstitution { /// wrap function application expressions as ImplicitCopyCtorExpr nodes so that it is easy to identify which @@ -226,4 +232,7 @@ acceptAll( translationUnit, checker ); + // fixes StmtExpr to properly link to their resulting expression + StmtExprResult::link( translationUnit ); + // fixes ConstructorInit for global variables. should happen before fixInitializers. InitTweak::fixGlobalInit( translationUnit, inLibrary ); @@ -299,4 +308,9 @@ return dtorFunc; + } + + void StmtExprResult::link( std::list< Declaration * > & translationUnit ) { + PassVisitor linker; + acceptAll( translationUnit, linker ); } @@ -349,4 +363,15 @@ PassVisitor fixer; mutateAll( translationUnit, fixer ); + } + + void StmtExprResult::previsit( StmtExpr * stmtExpr ) { + // we might loose the result expression here so add a pointer to trace back + assert( stmtExpr->result ); + Type * result = stmtExpr->result; + if ( ! result->isVoid() ) { + CompoundStmt * body = stmtExpr->statements; + assert( ! body->kids.empty() ); + stmtExpr->resultExpr = strict_dynamic_cast< ExprStmt * >( body->kids.back() ); + } } @@ -655,7 +680,7 @@ // function call temporaries should be placed at statement-level, rather than nested inside of a new statement expression, // since temporaries can be shared across sub-expressions, e.g. - // [A, A] f(); - // g([A] x, [A] y); - // g(f()); + // [A, A] f(); // decl + // g([A] x, [A] y); // decl + // g(f()); // call // f is executed once, so the return temporary is shared across the tuple constructors for x and y. // Explicitly mutating children instead of mutating the inner compound statement forces the temporaries to be added @@ -665,4 +690,5 @@ assert( env ); + indexer.enterScope(); // visit all statements std::list< Statement * > & stmts = stmtExpr->statements->get_kids(); @@ -670,4 +696,5 @@ stmt = stmt->acceptMutator( *visitor ); } // for + indexer.leaveScope(); assert( stmtExpr->result ); @@ -688,10 +715,19 @@ stmtsToAddBefore.push_back( new DeclStmt( ret ) ); - // must have a non-empty body, otherwise it wouldn't have a result - CompoundStmt * body = stmtExpr->statements; - assert( ! body->kids.empty() ); - // must be an ExprStmt, otherwise it wouldn't have a result - ExprStmt * last = strict_dynamic_cast< ExprStmt * >( body->kids.back() ); - last->expr = makeCtorDtor( "?{}", ret, last->expr ); + if(!stmtExpr->resultExpr) { + SemanticError(stmtExpr, "Statment-Expression should have a resulting expression"); + } + ExprStmt * last = stmtExpr->resultExpr; + try { + last->expr = makeCtorDtor( "?{}", ret, last->expr ); + } catch(...) { + std::cerr << "=======================" << std::endl; + std::cerr << "ERROR, can't resolve" << std::endl; + ret->print(std::cerr); + std::cerr << std::endl << "---" << std::endl; + last->expr->print(std::cerr); + + abort(); + } // add destructors after current statement Index: src/InitTweak/InitTweak.cc =================================================================== --- src/InitTweak/InitTweak.cc (revision 7564e10d60badc52604ddc7491f9465ec58795f3) +++ src/InitTweak/InitTweak.cc (revision 67130fe7c6ae00bc7c6da280f8b700e5bc850a3c) @@ -756,4 +756,15 @@ } + bool isCopyFunction( const ast::FunctionDecl * decl ) { + const ast::FunctionType * ftype = decl->type; + if ( ftype->params.size() != 2 ) return false; + + const ast::Type * t1 = getPointerBase( ftype->params.front()->get_type() ); + if ( ! t1 ) return false; + const ast::Type * t2 = ftype->params.back()->get_type(); + + return ResolvExpr::typesCompatibleIgnoreQualifiers( t1, t2, ast::SymbolTable{} ); + } + FunctionDecl * isAssignment( Declaration * decl ) { return isCopyFunction( decl, "?=?" ); Index: src/InitTweak/InitTweak.h =================================================================== --- src/InitTweak/InitTweak.h (revision 7564e10d60badc52604ddc7491f9465ec58795f3) +++ src/InitTweak/InitTweak.h (revision 67130fe7c6ae00bc7c6da280f8b700e5bc850a3c) @@ -30,4 +30,5 @@ FunctionDecl * isCopyConstructor( Declaration * decl ); FunctionDecl * isCopyFunction( Declaration * decl, const std::string & fname ); + bool isCopyFunction( const ast::FunctionDecl * decl ); /// returns the base type of the first parameter to a constructor/destructor/assignment function Index: src/Makefile.in =================================================================== --- src/Makefile.in (revision 7564e10d60badc52604ddc7491f9465ec58795f3) +++ src/Makefile.in (revision 67130fe7c6ae00bc7c6da280f8b700e5bc850a3c) @@ -170,5 +170,6 @@ AST/Init.$(OBJEXT) AST/LinkageSpec.$(OBJEXT) \ AST/Node.$(OBJEXT) AST/Pass.$(OBJEXT) AST/Print.$(OBJEXT) \ - AST/Stmt.$(OBJEXT) AST/Type.$(OBJEXT) \ + AST/Stmt.$(OBJEXT) AST/SymbolTable.$(OBJEXT) \ + AST/Type.$(OBJEXT) AST/TypeEnvironment.$(OBJEXT) \ AST/TypeSubstitution.$(OBJEXT) am__objects_2 = CodeGen/CodeGenerator.$(OBJEXT) \ @@ -586,5 +587,7 @@ AST/Print.cpp \ AST/Stmt.cpp \ + AST/SymbolTable.cpp \ AST/Type.cpp \ + AST/TypeEnvironment.cpp \ AST/TypeSubstitution.cpp @@ -754,5 +757,9 @@ AST/Print.$(OBJEXT): AST/$(am__dirstamp) AST/$(DEPDIR)/$(am__dirstamp) AST/Stmt.$(OBJEXT): AST/$(am__dirstamp) AST/$(DEPDIR)/$(am__dirstamp) +AST/SymbolTable.$(OBJEXT): AST/$(am__dirstamp) \ + AST/$(DEPDIR)/$(am__dirstamp) AST/Type.$(OBJEXT): AST/$(am__dirstamp) AST/$(DEPDIR)/$(am__dirstamp) +AST/TypeEnvironment.$(OBJEXT): AST/$(am__dirstamp) \ + AST/$(DEPDIR)/$(am__dirstamp) AST/TypeSubstitution.$(OBJEXT): AST/$(am__dirstamp) \ AST/$(DEPDIR)/$(am__dirstamp) @@ -1190,5 +1197,7 @@ @AMDEP_TRUE@@am__include@ @am__quote@AST/$(DEPDIR)/Print.Po@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@AST/$(DEPDIR)/Stmt.Po@am__quote@ +@AMDEP_TRUE@@am__include@ @am__quote@AST/$(DEPDIR)/SymbolTable.Po@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@AST/$(DEPDIR)/Type.Po@am__quote@ +@AMDEP_TRUE@@am__include@ @am__quote@AST/$(DEPDIR)/TypeEnvironment.Po@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@AST/$(DEPDIR)/TypeSubstitution.Po@am__quote@ @AMDEP_TRUE@@am__include@ @am__quote@CodeGen/$(DEPDIR)/CodeGenerator.Po@am__quote@ Index: src/ResolvExpr/AlternativeFinder.cc =================================================================== --- src/ResolvExpr/AlternativeFinder.cc (revision 7564e10d60badc52604ddc7491f9465ec58795f3) +++ src/ResolvExpr/AlternativeFinder.cc (revision 67130fe7c6ae00bc7c6da280f8b700e5bc850a3c) @@ -28,4 +28,6 @@ #include "Alternative.h" // for AltList, Alternative #include "AlternativeFinder.h" +#include "AST/Expr.hpp" +#include "AST/Type.hpp" #include "Common/SemanticError.h" // for SemanticError #include "Common/utility.h" // for deleteAll, printAll, CodeLocation @@ -222,4 +224,14 @@ cost.incReference(); } + } + + const ast::Expr * referenceToRvalueConversion( const ast::Expr * expr, Cost & cost ) { + if ( expr->result.as< ast::ReferenceType >() ) { + // cast away reference from expr + cost.incReference(); + return new ast::CastExpr{ expr->location, expr, expr->result->stripReferences() }; + } + + return expr; } Index: src/ResolvExpr/CommonType.cc =================================================================== --- src/ResolvExpr/CommonType.cc (revision 7564e10d60badc52604ddc7491f9465ec58795f3) +++ src/ResolvExpr/CommonType.cc (revision 67130fe7c6ae00bc7c6da280f8b700e5bc850a3c) @@ -18,4 +18,6 @@ #include // for pair +#include "AST/Decl.hpp" +#include "AST/Type.hpp" #include "Common/PassVisitor.h" #include "ResolvExpr/TypeEnvironment.h" // for OpenVarSet, AssertionSet @@ -35,6 +37,6 @@ namespace ResolvExpr { - struct CommonType : public WithShortCircuiting { - CommonType( Type *type2, bool widenFirst, bool widenSecond, const SymTab::Indexer &indexer, TypeEnvironment &env, const OpenVarSet &openVars ); + struct CommonType_old : public WithShortCircuiting { + CommonType_old( Type *type2, bool widenFirst, bool widenSecond, const SymTab::Indexer &indexer, TypeEnvironment &env, const OpenVarSet &openVars ); Type *get_result() const { return result; } @@ -94,5 +96,5 @@ Type *commonType( Type *type1, Type *type2, bool widenFirst, bool widenSecond, const SymTab::Indexer &indexer, TypeEnvironment &env, const OpenVarSet &openVars ) { - PassVisitor visitor( type2, widenFirst, widenSecond, indexer, env, openVars ); + PassVisitor visitor( type2, widenFirst, widenSecond, indexer, env, openVars ); int depth1 = type1->referenceDepth(); @@ -483,11 +485,11 @@ ); - CommonType::CommonType( Type *type2, bool widenFirst, bool widenSecond, const SymTab::Indexer &indexer, TypeEnvironment &env, const OpenVarSet &openVars ) + CommonType_old::CommonType_old( Type *type2, bool widenFirst, bool widenSecond, const SymTab::Indexer &indexer, TypeEnvironment &env, const OpenVarSet &openVars ) : result( 0 ), type2( type2 ), widenFirst( widenFirst ), widenSecond( widenSecond ), indexer( indexer ), env( env ), openVars( openVars ) { } - void CommonType::postvisit( VoidType * ) {} - - void CommonType::postvisit( BasicType *basicType ) { + void CommonType_old::postvisit( VoidType * ) {} + + void CommonType_old::postvisit( BasicType *basicType ) { if ( BasicType *otherBasic = dynamic_cast< BasicType* >( type2 ) ) { BasicType::Kind newType = commonTypes[ basicType->get_kind() ][ otherBasic->get_kind() ]; @@ -505,5 +507,5 @@ template< typename Pointer > - void CommonType::getCommonWithVoidPointer( Pointer* voidPointer, Pointer* otherPointer ) { + void CommonType_old::getCommonWithVoidPointer( Pointer* voidPointer, Pointer* otherPointer ) { if ( TypeInstType* var = dynamic_cast< TypeInstType* >( otherPointer->get_base() ) ) { OpenVarSet::const_iterator entry = openVars.find( var->get_name() ); @@ -518,5 +520,5 @@ } - void CommonType::postvisit( PointerType *pointerType ) { + void CommonType_old::postvisit( PointerType *pointerType ) { if ( PointerType *otherPointer = dynamic_cast< PointerType* >( type2 ) ) { // std::cerr << "commonType: two pointers: " << pointerType << " / " << otherPointer << std::endl; @@ -553,7 +555,7 @@ } - void CommonType::postvisit( ArrayType * ) {} - - void CommonType::postvisit( ReferenceType *refType ) { + void CommonType_old::postvisit( ArrayType * ) {} + + void CommonType_old::postvisit( ReferenceType *refType ) { if ( ReferenceType *otherRef = dynamic_cast< ReferenceType* >( type2 ) ) { // std::cerr << "commonType: both references: " << refType << " / " << otherRef << std::endl; @@ -590,9 +592,9 @@ } - void CommonType::postvisit( FunctionType * ) {} - void CommonType::postvisit( StructInstType * ) {} - void CommonType::postvisit( UnionInstType * ) {} - - void CommonType::postvisit( EnumInstType *enumInstType ) { + void CommonType_old::postvisit( FunctionType * ) {} + void CommonType_old::postvisit( StructInstType * ) {} + void CommonType_old::postvisit( UnionInstType * ) {} + + void CommonType_old::postvisit( EnumInstType *enumInstType ) { if ( dynamic_cast< BasicType * >( type2 ) || dynamic_cast< ZeroType* >( type2 ) || dynamic_cast< OneType* >( type2 ) ) { // reuse BasicType, EnumInstType code by swapping type2 with enumInstType @@ -601,8 +603,8 @@ } - void CommonType::postvisit( TraitInstType * ) { - } - - void CommonType::postvisit( TypeInstType *inst ) { + void CommonType_old::postvisit( TraitInstType * ) { + } + + void CommonType_old::postvisit( TypeInstType *inst ) { if ( widenFirst ) { NamedTypeDecl *nt = indexer.lookupType( inst->get_name() ); @@ -626,8 +628,8 @@ } - void CommonType::postvisit( TupleType * ) {} - void CommonType::postvisit( VarArgsType * ) {} - - void CommonType::postvisit( ZeroType *zeroType ) { + void CommonType_old::postvisit( TupleType * ) {} + void CommonType_old::postvisit( VarArgsType * ) {} + + void CommonType_old::postvisit( ZeroType *zeroType ) { if ( widenFirst ) { if ( dynamic_cast< BasicType* >( type2 ) || dynamic_cast< PointerType* >( type2 ) || dynamic_cast< EnumInstType* >( type2 ) ) { @@ -643,5 +645,5 @@ } - void CommonType::postvisit( OneType *oneType ) { + void CommonType_old::postvisit( OneType *oneType ) { if ( widenFirst ) { if ( dynamic_cast< BasicType* >( type2 ) || dynamic_cast< EnumInstType* >( type2 ) ) { @@ -656,4 +658,343 @@ } } + + class CommonType_new final : public ast::WithShortCircuiting { + const ast::Type * type2; + WidenMode widen; + const ast::SymbolTable & symtab; + ast::TypeEnvironment & tenv; + const ast::OpenVarSet & open; + public: + ast::ptr< ast::Type > result; + + CommonType_new( + const ast::Type * t2, WidenMode w, const ast::SymbolTable & st, + ast::TypeEnvironment & env, const ast::OpenVarSet & o ) + : type2( t2 ), widen( w ), symtab( st ), tenv( env ), open( o ), result() {} + + void previsit( const ast::Node * ) { visit_children = false; } + + void postvisit( const ast::VoidType * ) {} + + void postvisit( const ast::BasicType * basic ) { + if ( auto basic2 = dynamic_cast< const ast::BasicType * >( type2 ) ) { + #warning remove casts when `commonTypes` moved to new AST + ast::BasicType::Kind kind = (ast::BasicType::Kind)(int)commonTypes[ (BasicType::Kind)(int)basic->kind ][ (BasicType::Kind)(int)basic2->kind ]; + if ( + ( ( kind == basic->kind && basic->qualifiers >= basic2->qualifiers ) + || widen.first ) + && ( ( kind == basic2->kind && basic->qualifiers <= basic2->qualifiers ) + || widen.second ) + ) { + result = new ast::BasicType{ kind, basic->qualifiers | basic2->qualifiers }; + } + } else if ( + dynamic_cast< const ast::EnumInstType * >( type2 ) + || dynamic_cast< const ast::ZeroType * >( type2 ) + || dynamic_cast< const ast::OneType * >( type2 ) + ) { + #warning remove casts when `commonTypes` moved to new AST + ast::BasicType::Kind kind = (ast::BasicType::Kind)(int)commonTypes[ (BasicType::Kind)(int)basic->kind ][ (BasicType::Kind)(int)ast::BasicType::SignedInt ]; + if ( + ( ( kind == basic->kind && basic->qualifiers >= type2->qualifiers ) + || widen.first ) + && ( ( kind != basic->kind && basic->qualifiers <= type2->qualifiers ) + || widen.second ) + ) { + result = new ast::BasicType{ kind, basic->qualifiers | type2->qualifiers }; + } + } + } + + private: + template< typename Pointer > + void getCommonWithVoidPointer( const Pointer * voidPtr, const Pointer * oPtr ) { + const ast::Type * base = oPtr->base; + if ( auto var = dynamic_cast< const ast::TypeInstType * >( base ) ) { + auto entry = open.find( var->name ); + if ( entry != open.end() ) { + ast::AssertionSet need, have; + if ( ! tenv.bindVar( + var, voidPtr->base, entry->second, need, have, open, widen, symtab ) + ) return; + } + } + result = voidPtr; + add_qualifiers( result, oPtr->qualifiers ); + } + + public: + void postvisit( const ast::PointerType * pointer ) { + if ( auto pointer2 = dynamic_cast< const ast::PointerType * >( type2 ) ) { + if ( + widen.first + && pointer2->base.as< ast::VoidType >() + && ! ast::isFtype( pointer->base ) + ) { + getCommonWithVoidPointer( pointer2, pointer ); + } else if ( + widen.second + && pointer->base.as< ast::VoidType >() + && ! ast::isFtype( pointer2->base ) + ) { + getCommonWithVoidPointer( pointer, pointer2 ); + } else if ( + ( pointer->base->qualifiers >= pointer2->base->qualifiers || widen.first ) + && ( pointer->base->qualifiers <= pointer2->base->qualifiers || widen.second ) + ) { + ast::CV::Qualifiers q1 = pointer->base->qualifiers; + ast::CV::Qualifiers q2 = pointer2->base->qualifiers; + + // force t{1,2} to be cloned if their qualifiers must be stripped, so that + // pointer{,2}->base are unchanged + ast::ptr< ast::Type > t1{ pointer->base }, t2{ pointer2->base }; + reset_qualifiers( t1 ); + reset_qualifiers( t2 ); + + ast::AssertionSet have, need; + ast::OpenVarSet newOpen{ open }; + if ( unifyExact( t1, t2, tenv, have, need, newOpen, noWiden(), symtab ) ) { + result = pointer; + if ( q1.val != q2.val ) { + // reset result->base->qualifiers to be union of two base qualifiers + strict_dynamic_cast< ast::PointerType * >( + result.get_and_mutate() + )->base.get_and_mutate()->qualifiers = q1 | q2; + } + } + } + } else if ( widen.second && dynamic_cast< const ast::ZeroType * >( type2 ) ) { + result = pointer; + add_qualifiers( result, type2->qualifiers ); + } + } + + void postvisit( const ast::ArrayType * ) {} + + void postvisit( const ast::ReferenceType * ref ) { + if ( auto ref2 = dynamic_cast< const ast::ReferenceType * >( type2 ) ) { + if ( + widen.first && ref2->base.as< ast::VoidType >() && ! ast::isFtype( ref->base ) + ) { + getCommonWithVoidPointer( ref2, ref ); + } else if ( + widen.second && ref->base.as< ast::VoidType>() && ! ast::isFtype( ref2->base ) + ) { + getCommonWithVoidPointer( ref, ref2 ); + } else if ( + ( ref->base->qualifiers >= ref2->base->qualifiers || widen.first ) + && ( ref->base->qualifiers <= ref2->base->qualifiers || widen.second ) + ) { + ast::CV::Qualifiers q1 = ref->base->qualifiers, q2 = ref2->base->qualifiers; + + // force t{1,2} to be cloned if their qualifiers must be stripped, so that + // ref{,2}->base are unchanged + ast::ptr< ast::Type > t1{ ref->base }, t2{ ref2->base }; + reset_qualifiers( t1 ); + reset_qualifiers( t2 ); + + ast::AssertionSet have, need; + ast::OpenVarSet newOpen{ open }; + if ( unifyExact( t1, t2, tenv, have, need, newOpen, noWiden(), symtab ) ) { + result = ref; + if ( q1.val != q2.val ) { + // reset result->base->qualifiers to be union of two base qualifiers + strict_dynamic_cast< ast::ReferenceType * >( + result.get_and_mutate() + )->base.get_and_mutate()->qualifiers = q1 | q2; + } + } + } + } else if ( widen.second && dynamic_cast< const ast::ZeroType * >( type2 ) ) { + result = ref; + add_qualifiers( result, type2->qualifiers ); + } + } + + void postvisit( const ast::FunctionType * ) {} + + void postvisit( const ast::StructInstType * ) {} + + void postvisit( const ast::UnionInstType * ) {} + + void postvisit( const ast::EnumInstType * enumInst ) { + if ( + dynamic_cast< const ast::BasicType * >( type2 ) + || dynamic_cast< const ast::ZeroType * >( type2 ) + || dynamic_cast< const ast::OneType * >( type2 ) + ) { + // reuse BasicType/EnumInstType common type by swapping + result = commonType( type2, enumInst, widen, symtab, tenv, open ); + } + } + + void postvisit( const ast::TraitInstType * ) {} + + void postvisit( const ast::TypeInstType * inst ) { + if ( ! widen.first ) return; + if ( const ast::NamedTypeDecl * nt = symtab.lookupType( inst->name ) ) { + if ( const ast::Type * base = + strict_dynamic_cast< const ast::TypeDecl * >( nt )->base + ) { + ast::CV::Qualifiers q1 = inst->qualifiers, q2 = type2->qualifiers; + + // force t{1,2} to be cloned if their qualifiers must be mutated + ast::ptr< ast::Type > t1{ base }, t2{ type2 }; + reset_qualifiers( t1, q1 ); + reset_qualifiers( t2 ); + + ast::AssertionSet have, need; + ast::OpenVarSet newOpen{ open }; + if ( unifyExact( t1, t2, tenv, have, need, newOpen, noWiden(), symtab ) ) { + result = type2; + reset_qualifiers( result, q1 | q2 ); + } + } + } + } + + void postvisit( const ast::TupleType * ) {} + + void postvisit( const ast::VarArgsType * ) {} + + void postvisit( const ast::ZeroType * zero ) { + if ( ! widen.first ) return; + if ( + dynamic_cast< const ast::BasicType * >( type2 ) + || dynamic_cast< const ast::PointerType * >( type2 ) + || dynamic_cast< const ast::EnumInstType * >( type2 ) + ) { + if ( widen.second || zero->qualifiers <= type2->qualifiers ) { + result = type2; + add_qualifiers( result, zero->qualifiers ); + } + } else if ( widen.second && dynamic_cast< const ast::OneType * >( type2 ) ) { + result = new ast::BasicType{ + ast::BasicType::SignedInt, zero->qualifiers | type2->qualifiers }; + } + } + + void postvisit( const ast::OneType * one ) { + if ( ! widen.first ) return; + if ( + dynamic_cast< const ast::BasicType * >( type2 ) + || dynamic_cast< const ast::EnumInstType * >( type2 ) + ) { + if ( widen.second || one->qualifiers <= type2->qualifiers ) { + result = type2; + add_qualifiers( result, one->qualifiers ); + } + } else if ( widen.second && dynamic_cast< const ast::ZeroType * >( type2 ) ) { + result = new ast::BasicType{ + ast::BasicType::SignedInt, one->qualifiers | type2->qualifiers }; + } + } + + }; + + namespace { + ast::ptr< ast::Type > handleReference( + const ast::ptr< ast::Type > & t1, const ast::ptr< ast::Type > & t2, WidenMode widen, + const ast::SymbolTable & symtab, ast::TypeEnvironment & env, + const ast::OpenVarSet & open + ) { + ast::ptr common; + ast::AssertionSet have, need; + ast::OpenVarSet newOpen{ open }; + + // need unify to bind type variables + if ( unify( t1, t2, env, have, need, newOpen, symtab, common ) ) { + ast::CV::Qualifiers q1 = t1->qualifiers, q2 = t2->qualifiers; + PRINT( + std::cerr << "unify success: " << widenFirst << " " << widenSecond << std::endl; + ) + if ( ( widen.first || q2 <= q1 ) && ( widen.second || q1 <= q2 ) ) { + PRINT( + std::cerr << "widen okay" << std::endl; + ) + add_qualifiers( common, q1 | q2 ); + return common; + } + } + + PRINT( + std::cerr << "exact unify failed: " << t1 << " " << t2 << std::endl; + ) + return { nullptr }; + } + } + + ast::ptr< ast::Type > commonType( + const ast::ptr< ast::Type > & type1, const ast::ptr< ast::Type > & type2, + WidenMode widen, const ast::SymbolTable & symtab, ast::TypeEnvironment & env, + const ast::OpenVarSet & open + ) { + unsigned depth1 = type1->referenceDepth(); + unsigned depth2 = type2->referenceDepth(); + + if ( depth1 != depth2 ) { // implies depth1 > 0 || depth2 > 0 + PRINT( + std::cerr << "reference depth diff: " << (depth1-depth2) << std::endl; + ) + ast::ptr< ast::Type > result; + const ast::ReferenceType * ref1 = type1.as< ast::ReferenceType >(); + const ast::ReferenceType * ref2 = type1.as< ast::ReferenceType >(); + + if ( depth1 > depth2 ) { + assert( ref1 ); + result = handleReference( ref1->base, type2, widen, symtab, env, open ); + } else { // implies depth1 < depth2 + assert( ref2 ); + result = handleReference( type1, ref2->base, widen, symtab, env, open ); + } + + if ( result && ref1 ) { + // formal is reference, so result should be reference + PRINT( + std::cerr << "formal is reference; result should be reference" << std::endl; + ) + result = new ast::ReferenceType{ result, ref1->qualifiers }; + } + + PRINT( + std::cerr << "common type of reference [" << type1 << "] and [" << type2 << "] is " + "[" << result << "]" << std::endl; + ) + return result; + } + // otherwise both are reference types of the same depth and this is handled by the visitor + ast::Pass visitor{ type2, widen, symtab, env, open }; + type1->accept( visitor ); + ast::ptr< ast::Type > result = visitor.pass.result; + + // handling for opaque type declarations (?) + if ( ! result && widen.second ) { + if ( const ast::TypeInstType * inst = type2.as< ast::TypeInstType >() ) { + if ( const ast::NamedTypeDecl * nt = symtab.lookupType( inst->name ) ) { + auto type = strict_dynamic_cast< const ast::TypeDecl * >( nt ); + if ( type->base ) { + ast::CV::Qualifiers q1 = type1->qualifiers, q2 = type2->qualifiers; + ast::AssertionSet have, need; + ast::OpenVarSet newOpen{ open }; + + // force t{1,2} to be cloned if its qualifiers must be stripped, so that + // type1 and type->base are left unchanged; calling convention forces + // {type1,type->base}->strong_ref >= 1 + ast::ptr t1{ type1 }, t2{ type->base }; + reset_qualifiers( t1 ); + reset_qualifiers( t2, q1 ); + + if ( unifyExact( t1, t2, env, have, need, newOpen, noWiden(), symtab ) ) { + result = t1; + reset_qualifiers( result, q1 | q2 ); + } + } + } + } + } + + return result; + } + } // namespace ResolvExpr Index: src/ResolvExpr/FindOpenVars.cc =================================================================== --- src/ResolvExpr/FindOpenVars.cc (revision 7564e10d60badc52604ddc7491f9465ec58795f3) +++ src/ResolvExpr/FindOpenVars.cc (revision 67130fe7c6ae00bc7c6da280f8b700e5bc850a3c) @@ -19,4 +19,6 @@ #include // for map<>::mapped_type +#include "AST/Pass.hpp" +#include "AST/Type.hpp" #include "Common/PassVisitor.h" #include "SynTree/Declaration.h" // for TypeDecl, DeclarationWithType (ptr ... @@ -24,6 +26,6 @@ namespace ResolvExpr { - struct FindOpenVars : public WithGuards { - FindOpenVars( OpenVarSet &openVars, OpenVarSet &closedVars, AssertionSet &needAssertions, AssertionSet &haveAssertions, bool firstIsOpen ); + struct FindOpenVars_old : public WithGuards { + FindOpenVars_old( OpenVarSet &openVars, OpenVarSet &closedVars, AssertionSet &needAssertions, AssertionSet &haveAssertions, bool firstIsOpen ); void previsit( PointerType * pointerType ); @@ -40,13 +42,13 @@ void findOpenVars( Type *type, OpenVarSet &openVars, OpenVarSet &closedVars, AssertionSet &needAssertions, AssertionSet &haveAssertions, bool firstIsOpen ) { - PassVisitor finder( openVars, closedVars, needAssertions, haveAssertions, firstIsOpen ); + PassVisitor finder( openVars, closedVars, needAssertions, haveAssertions, firstIsOpen ); type->accept( finder ); } - FindOpenVars::FindOpenVars( OpenVarSet &openVars, OpenVarSet &closedVars, AssertionSet &needAssertions, AssertionSet &haveAssertions, bool firstIsOpen ) + FindOpenVars_old::FindOpenVars_old( OpenVarSet &openVars, OpenVarSet &closedVars, AssertionSet &needAssertions, AssertionSet &haveAssertions, bool firstIsOpen ) : openVars( openVars ), closedVars( closedVars ), needAssertions( needAssertions ), haveAssertions( haveAssertions ), nextIsOpen( firstIsOpen ) { } - void FindOpenVars::common_action( Type *type ) { + void FindOpenVars_old::common_action( Type *type ) { if ( nextIsOpen ) { for ( Type::ForallList::const_iterator i = type->get_forall().begin(); i != type->get_forall().end(); ++i ) { @@ -76,13 +78,13 @@ } - void FindOpenVars::previsit(PointerType *pointerType) { + void FindOpenVars_old::previsit(PointerType *pointerType) { common_action( pointerType ); } - void FindOpenVars::previsit(ArrayType *arrayType) { + void FindOpenVars_old::previsit(ArrayType *arrayType) { common_action( arrayType ); } - void FindOpenVars::previsit(FunctionType *functionType) { + void FindOpenVars_old::previsit(FunctionType *functionType) { common_action( functionType ); nextIsOpen = ! nextIsOpen; @@ -90,6 +92,52 @@ } - void FindOpenVars::previsit(TupleType *tupleType) { + void FindOpenVars_old::previsit(TupleType *tupleType) { common_action( tupleType ); + } + + namespace { + struct FindOpenVars_new final : public ast::WithGuards { + ast::OpenVarSet & open; + ast::OpenVarSet & closed; + ast::AssertionSet & need; + ast::AssertionSet & have; + bool nextIsOpen; + + FindOpenVars_new( + ast::OpenVarSet & o, ast::OpenVarSet & c, ast::AssertionSet & n, + ast::AssertionSet & h, FirstMode firstIsOpen ) + : open( o ), closed( c ), need( n ), have( h ), nextIsOpen( firstIsOpen ) {} + + void previsit( const ast::FunctionType * type ) { + // mark open/closed variables + if ( nextIsOpen ) { + for ( const ast::TypeDecl * decl : type->forall ) { + open[ decl->name ] = ast::TypeDecl::Data{ decl }; + for ( const ast::DeclWithType * assert : decl->assertions ) { + need[ assert ].isUsed = false; + } + } + } else { + for ( const ast::TypeDecl * decl : type->forall ) { + closed[ decl->name ] = ast::TypeDecl::Data{ decl }; + for ( const ast::DeclWithType * assert : decl->assertions ) { + have[ assert ].isUsed = false; + } + } + } + + // flip open variables for contained function types + nextIsOpen = ! nextIsOpen; + GuardAction( [this](){ nextIsOpen = ! nextIsOpen; } ); + } + + }; + } + + void findOpenVars( + const ast::Type * type, ast::OpenVarSet & open, ast::OpenVarSet & closed, + ast::AssertionSet & need, ast::AssertionSet & have, FirstMode firstIsOpen ) { + ast::Pass< FindOpenVars_new > finder{ open, closed, need, have, firstIsOpen }; + type->accept( finder ); } } // namespace ResolvExpr Index: src/ResolvExpr/FindOpenVars.h =================================================================== --- src/ResolvExpr/FindOpenVars.h (revision 7564e10d60badc52604ddc7491f9465ec58795f3) +++ src/ResolvExpr/FindOpenVars.h (revision 67130fe7c6ae00bc7c6da280f8b700e5bc850a3c) @@ -16,11 +16,22 @@ #pragma once +#include "AST/TypeEnvironment.hpp" // for AssertionSet, OpenVarSet #include "ResolvExpr/TypeEnvironment.h" // for AssertionSet, OpenVarSet class Type; +namespace ast { + class Type; +} namespace ResolvExpr { // Updates open and closed variables and their associated assertions void findOpenVars( Type *type, OpenVarSet &openVars, OpenVarSet &closedVars, AssertionSet &needAssertions, AssertionSet &haveAssertions, bool firstIsOpen ); + + enum FirstMode { FirstClosed, FirstOpen }; + + // Updates open and closed variables and their associated assertions + void findOpenVars( + const ast::Type * type, ast::OpenVarSet & open, ast::OpenVarSet & closed, + ast::AssertionSet & need, ast::AssertionSet & have, FirstMode firstIsOpen ); } // namespace ResolvExpr Index: src/ResolvExpr/ResolveAssertions.cc =================================================================== --- src/ResolvExpr/ResolveAssertions.cc (revision 7564e10d60badc52604ddc7491f9465ec58795f3) +++ src/ResolvExpr/ResolveAssertions.cc (revision 67130fe7c6ae00bc7c6da280f8b700e5bc850a3c) @@ -30,4 +30,5 @@ #include "Common/Indenter.h" // for Indenter #include "Common/utility.h" // for sort_mins +#include "GenPoly/GenPoly.h" // for getFunctionType #include "ResolvExpr/RenameVars.h" // for renameTyVars #include "SymTab/Indexer.h" // for Indexer @@ -154,15 +155,10 @@ Cost k = Cost::zero; for ( const auto& assn : x.assns ) { + // compute conversion cost from satisfying decl to assertion k += computeConversionCost( assn.match.adjType, assn.decl->get_type(), indexer, x.env ); // mark vars+specialization cost on function-type assertions - Type* assnType = assn.match.cdata.id->get_type(); - FunctionType* func; - if ( PointerType* ptr = dynamic_cast< PointerType* >( assnType ) ) { - func = dynamic_cast< FunctionType* >( ptr->base ); - } else { - func = dynamic_cast< FunctionType* >( assnType ); - } + FunctionType* func = GenPoly::getFunctionType( assn.match.cdata.id->get_type() ); if ( ! func ) continue; Index: src/ResolvExpr/Resolver.cc =================================================================== --- src/ResolvExpr/Resolver.cc (revision 7564e10d60badc52604ddc7491f9465ec58795f3) +++ src/ResolvExpr/Resolver.cc (revision 67130fe7c6ae00bc7c6da280f8b700e5bc850a3c) @@ -7,9 +7,9 @@ // Resolver.cc -- // -// Author : Richard C. Bilson +// Author : Aaron B. Moss // Created On : Sun May 17 12:17:01 2015 -// Last Modified By : Peter A. Buhr -// Last Modified On : Tue Feb 19 18:09:56 2019 -// Update Count : 240 +// Last Modified By : Aaron B. Moss +// Last Modified On : Wed May 29 11:00:00 2019 +// Update Count : 241 // @@ -21,14 +21,18 @@ #include "Alternative.h" // for Alternative, AltList #include "AlternativeFinder.h" // for AlternativeFinder, resolveIn... +#include "CurrentObject.h" // for CurrentObject +#include "RenameVars.h" // for RenameVars, global_renamer +#include "Resolver.h" +#include "ResolvMode.h" // for ResolvMode +#include "typeops.h" // for extractResultType +#include "Unify.h" // for unify +#include "AST/Pass.hpp" +#include "AST/SymbolTable.hpp" #include "Common/PassVisitor.h" // for PassVisitor #include "Common/SemanticError.h" // for SemanticError #include "Common/utility.h" // for ValueGuard, group_iterate -#include "CurrentObject.h" // for CurrentObject #include "InitTweak/GenInit.h" #include "InitTweak/InitTweak.h" // for isIntrinsicSingleArgCallStmt -#include "RenameVars.h" // for RenameVars, global_renamer #include "ResolvExpr/TypeEnvironment.h" // for TypeEnvironment -#include "Resolver.h" -#include "ResolvMode.h" // for ResolvMode #include "SymTab/Autogen.h" // for SizeType #include "SymTab/Indexer.h" // for Indexer @@ -41,6 +45,4 @@ #include "SynTree/Visitor.h" // for acceptAll, maybeAccept #include "Tuples/Tuples.h" -#include "typeops.h" // for extractResultType -#include "Unify.h" // for unify #include "Validate/FindSpecialDecls.h" // for SizeType @@ -48,7 +50,7 @@ namespace ResolvExpr { - struct Resolver final : public WithIndexer, public WithGuards, public WithVisitorRef, public WithShortCircuiting, public WithStmtsToAdd { - Resolver() {} - Resolver( const SymTab::Indexer & other ) { + struct Resolver_old final : public WithIndexer, public WithGuards, public WithVisitorRef, public WithShortCircuiting, public WithStmtsToAdd { + Resolver_old() {} + Resolver_old( const SymTab::Indexer & other ) { indexer = other; } @@ -101,10 +103,10 @@ void resolve( std::list< Declaration * > translationUnit ) { - PassVisitor resolver; + PassVisitor resolver; acceptAll( translationUnit, resolver ); } void resolveDecl( Declaration * decl, const SymTab::Indexer & indexer ) { - PassVisitor resolver( indexer ); + PassVisitor resolver( indexer ); maybeAccept( decl, resolver ); } @@ -402,9 +404,9 @@ } - void Resolver::previsit( ObjectDecl * objectDecl ) { - // To handle initialization of routine pointers, e.g., int (*fp)(int) = foo(), means that - // class-variable initContext is changed multiple time because the LHS is analysed twice. - // The second analysis changes initContext because of a function type can contain object - // declarations in the return and parameter types. So each value of initContext is + void Resolver_old::previsit( ObjectDecl * objectDecl ) { + // To handle initialization of routine pointers, e.g., int (*fp)(int) = foo(), means that + // class-variable initContext is changed multiple time because the LHS is analysed twice. + // The second analysis changes initContext because of a function type can contain object + // declarations in the return and parameter types. So each value of initContext is // retained, so the type on the first analysis is preserved and used for selecting the RHS. GuardValue( currentObject ); @@ -418,5 +420,5 @@ template< typename PtrType > - void Resolver::handlePtrType( PtrType * type ) { + void Resolver_old::handlePtrType( PtrType * type ) { if ( type->get_dimension() ) { findSingleExpression( type->dimension, Validate::SizeType->clone(), indexer ); @@ -424,13 +426,13 @@ } - void Resolver::previsit( ArrayType * at ) { + void Resolver_old::previsit( ArrayType * at ) { handlePtrType( at ); } - void Resolver::previsit( PointerType * pt ) { + void Resolver_old::previsit( PointerType * pt ) { handlePtrType( pt ); } - void Resolver::previsit( FunctionDecl * functionDecl ) { + void Resolver_old::previsit( FunctionDecl * functionDecl ) { #if 0 std::cerr << "resolver visiting functiondecl "; @@ -442,6 +444,6 @@ } - void Resolver::postvisit( FunctionDecl * functionDecl ) { - // default value expressions have an environment which shouldn't be there and trips up + void Resolver_old::postvisit( FunctionDecl * functionDecl ) { + // default value expressions have an environment which shouldn't be there and trips up // later passes. // xxx - it might be necessary to somehow keep the information from this environment, but I @@ -457,5 +459,5 @@ } - void Resolver::previsit( EnumDecl * ) { + void Resolver_old::previsit( EnumDecl * ) { // in case we decide to allow nested enums GuardValue( inEnumDecl ); @@ -463,9 +465,9 @@ } - void Resolver::previsit( StaticAssertDecl * assertDecl ) { + void Resolver_old::previsit( StaticAssertDecl * assertDecl ) { findIntegralExpression( assertDecl->condition, indexer ); } - void Resolver::previsit( ExprStmt * exprStmt ) { + void Resolver_old::previsit( ExprStmt * exprStmt ) { visit_children = false; assertf( exprStmt->expr, "ExprStmt has null Expression in resolver" ); @@ -473,5 +475,5 @@ } - void Resolver::previsit( AsmExpr * asmExpr ) { + void Resolver_old::previsit( AsmExpr * asmExpr ) { visit_children = false; findVoidExpression( asmExpr->operand, indexer ); @@ -481,5 +483,5 @@ } - void Resolver::previsit( AsmStmt * asmStmt ) { + void Resolver_old::previsit( AsmStmt * asmStmt ) { visit_children = false; acceptAll( asmStmt->get_input(), *visitor ); @@ -487,13 +489,13 @@ } - void Resolver::previsit( IfStmt * ifStmt ) { + void Resolver_old::previsit( IfStmt * ifStmt ) { findIntegralExpression( ifStmt->condition, indexer ); } - void Resolver::previsit( WhileStmt * whileStmt ) { + void Resolver_old::previsit( WhileStmt * whileStmt ) { findIntegralExpression( whileStmt->condition, indexer ); } - void Resolver::previsit( ForStmt * forStmt ) { + void Resolver_old::previsit( ForStmt * forStmt ) { if ( forStmt->condition ) { findIntegralExpression( forStmt->condition, indexer ); @@ -505,5 +507,5 @@ } - void Resolver::previsit( SwitchStmt * switchStmt ) { + void Resolver_old::previsit( SwitchStmt * switchStmt ) { GuardValue( currentObject ); findIntegralExpression( switchStmt->condition, indexer ); @@ -512,5 +514,5 @@ } - void Resolver::previsit( CaseStmt * caseStmt ) { + void Resolver_old::previsit( CaseStmt * caseStmt ) { if ( caseStmt->condition ) { std::list< InitAlternative > initAlts = currentObject.getOptions(); @@ -531,5 +533,5 @@ } - void Resolver::previsit( BranchStmt * branchStmt ) { + void Resolver_old::previsit( BranchStmt * branchStmt ) { visit_children = false; // must resolve the argument for a computed goto @@ -542,5 +544,5 @@ } - void Resolver::previsit( ReturnStmt * returnStmt ) { + void Resolver_old::previsit( ReturnStmt * returnStmt ) { visit_children = false; if ( returnStmt->expr ) { @@ -549,5 +551,5 @@ } - void Resolver::previsit( ThrowStmt * throwStmt ) { + void Resolver_old::previsit( ThrowStmt * throwStmt ) { visit_children = false; // TODO: Replace *exception type with &exception type. @@ -561,5 +563,5 @@ } - void Resolver::previsit( CatchStmt * catchStmt ) { + void Resolver_old::previsit( CatchStmt * catchStmt ) { if ( catchStmt->cond ) { findSingleExpression( catchStmt->cond, new BasicType( noQualifiers, BasicType::Bool ), indexer ); @@ -576,5 +578,5 @@ } - void Resolver::previsit( WaitForStmt * stmt ) { + void Resolver_old::previsit( WaitForStmt * stmt ) { visit_children = false; @@ -782,5 +784,5 @@ } - void Resolver::previsit( SingleInit * singleInit ) { + void Resolver_old::previsit( SingleInit * singleInit ) { visit_children = false; // resolve initialization using the possibilities as determined by the currentObject cursor @@ -834,5 +836,5 @@ } - void Resolver::previsit( ListInit * listInit ) { + void Resolver_old::previsit( ListInit * listInit ) { visit_children = false; // move cursor into brace-enclosed initializer-list @@ -869,5 +871,5 @@ // ConstructorInit - fall back on C-style initializer - void Resolver::fallbackInit( ConstructorInit * ctorInit ) { + void Resolver_old::fallbackInit( ConstructorInit * ctorInit ) { // could not find valid constructor, or found an intrinsic constructor // fall back on C-style initializer @@ -882,5 +884,5 @@ void resolveCtorInit( ConstructorInit * ctorInit, const SymTab::Indexer & indexer ) { assert( ctorInit ); - PassVisitor resolver( indexer ); + PassVisitor resolver( indexer ); ctorInit->accept( resolver ); } @@ -888,5 +890,5 @@ void resolveStmtExpr( StmtExpr * stmtExpr, const SymTab::Indexer & indexer ) { assert( stmtExpr ); - PassVisitor resolver( indexer ); + PassVisitor resolver( indexer ); stmtExpr->accept( resolver ); stmtExpr->computeResult(); @@ -894,5 +896,5 @@ } - void Resolver::previsit( ConstructorInit * ctorInit ) { + void Resolver_old::previsit( ConstructorInit * ctorInit ) { visit_children = false; // xxx - fallback init has been removed => remove fallbackInit function and remove complexity from FixInit and remove C-init from ConstructorInit @@ -928,4 +930,191 @@ // } } + + /////////////////////////////////////////////////////////////////////////// + // + // *** NEW RESOLVER *** + // + /////////////////////////////////////////////////////////////////////////// + + class Resolver_new final + : public ast::WithIndexer, public ast::WithGuards, public ast::WithVisitorRef, + public ast::WithShortCircuiting, public ast::WithStmtsToAdd<> { + + public: + Resolver_new() = default; + Resolver_new( const ast::SymbolTable & syms ) { /*symtab = syms;*/ } + + void previsit( ast::FunctionDecl * functionDecl ); + ast::DeclWithType * postvisit( ast::FunctionDecl * functionDecl ); + void previsit( ast::ObjectDecl * objectDecl ); + void previsit( ast::EnumDecl * enumDecl ); + void previsit( ast::StaticAssertDecl * assertDecl ); + + void previsit( ast::ArrayType * at ); + void previsit( ast::PointerType * pt ); + + void previsit( ast::ExprStmt * exprStmt ); + void previsit( ast::AsmExpr * asmExpr ); + void previsit( ast::AsmStmt * asmStmt ); + void previsit( ast::IfStmt * ifStmt ); + void previsit( ast::WhileStmt * whileStmt ); + void previsit( ast::ForStmt * forStmt ); + void previsit( ast::SwitchStmt * switchStmt ); + void previsit( ast::CaseStmt * caseStmt ); + void previsit( ast::BranchStmt * branchStmt ); + void previsit( ast::ReturnStmt * returnStmt ); + void previsit( ast::ThrowStmt * throwStmt ); + void previsit( ast::CatchStmt * catchStmt ); + void previsit( ast::WaitForStmt * stmt ); + + void previsit( ast::SingleInit * singleInit ); + void previsit( ast::ListInit * listInit ); + void previsit( ast::ConstructorInit * ctorInit ); + }; + + void resolve( std::list< ast::ptr >& translationUnit ) { + ast::Pass resolver; + accept_all( translationUnit, resolver ); + } + + void previsit( ast::FunctionDecl * functionDecl ) { + #warning unimplemented; Resolver port in progress + (void)functionDecl; + assert(false); + } + + ast::DeclWithType * postvisit( ast::FunctionDecl * functionDecl ) { + #warning unimplemented; Resolver port in progress + (void)functionDecl; + assert(false); + return nullptr; + } + + void previsit( ast::ObjectDecl * objectDecl ) { + #warning unimplemented; Resolver port in progress + (void)objectDecl; + assert(false); + } + + void previsit( ast::EnumDecl * enumDecl ) { + #warning unimplemented; Resolver port in progress + (void)enumDecl; + assert(false); + } + + void previsit( ast::StaticAssertDecl * assertDecl ) { + #warning unimplemented; Resolver port in progress + (void)assertDecl; + assert(false); + } + + void previsit( ast::ArrayType * at ) { + #warning unimplemented; Resolver port in progress + (void)at; + assert(false); + } + + void previsit( ast::PointerType * pt ) { + #warning unimplemented; Resolver port in progress + (void)pt; + assert(false); + } + + void previsit( ast::ExprStmt * exprStmt ) { + #warning unimplemented; Resolver port in progress + (void)exprStmt; + assert(false); + } + + void previsit( ast::AsmExpr * asmExpr ) { + #warning unimplemented; Resolver port in progress + (void)asmExpr; + assert(false); + } + + void previsit( ast::AsmStmt * asmStmt ) { + #warning unimplemented; Resolver port in progress + (void)asmStmt; + assert(false); + } + + void previsit( ast::IfStmt * ifStmt ) { + #warning unimplemented; Resolver port in progress + (void)ifStmt; + assert(false); + } + + void previsit( ast::WhileStmt * whileStmt ) { + #warning unimplemented; Resolver port in progress + (void)whileStmt; + assert(false); + } + + void previsit( ast::ForStmt * forStmt ) { + #warning unimplemented; Resolver port in progress + (void)forStmt; + assert(false); + } + + void previsit( ast::SwitchStmt * switchStmt ) { + #warning unimplemented; Resolver port in progress + (void)switchStmt; + assert(false); + } + + void previsit( ast::CaseStmt * caseStmt ) { + #warning unimplemented; Resolver port in progress + (void)caseStmt; + assert(false); + } + + void previsit( ast::BranchStmt * branchStmt ) { + #warning unimplemented; Resolver port in progress + (void)branchStmt; + assert(false); + } + + void previsit( ast::ReturnStmt * returnStmt ) { + #warning unimplemented; Resolver port in progress + (void)returnStmt; + assert(false); + } + + void previsit( ast::ThrowStmt * throwStmt ) { + #warning unimplemented; Resolver port in progress + (void)throwStmt; + assert(false); + } + + void previsit( ast::CatchStmt * catchStmt ) { + #warning unimplemented; Resolver port in progress + (void)catchStmt; + assert(false); + } + + void previsit( ast::WaitForStmt * stmt ) { + #warning unimplemented; Resolver port in progress + (void)stmt; + assert(false); + } + + void previsit( ast::SingleInit * singleInit ) { + #warning unimplemented; Resolver port in progress + (void)singleInit; + assert(false); + } + + void previsit( ast::ListInit * listInit ) { + #warning unimplemented; Resolver port in progress + (void)listInit; + assert(false); + } + + void previsit( ast::ConstructorInit * ctorInit ) { + #warning unimplemented; Resolver port in progress + (void)ctorInit; + assert(false); + } + } // namespace ResolvExpr Index: src/ResolvExpr/Resolver.h =================================================================== --- src/ResolvExpr/Resolver.h (revision 7564e10d60badc52604ddc7491f9465ec58795f3) +++ src/ResolvExpr/Resolver.h (revision 67130fe7c6ae00bc7c6da280f8b700e5bc850a3c) @@ -16,5 +16,6 @@ #pragma once -#include // for list +#include // for list +#include // for ptr class ConstructorInit; @@ -23,6 +24,10 @@ class StmtExpr; namespace SymTab { -class Indexer; -} // namespace SymTab + class Indexer; +} // namespace SymTab + +namespace ast { + class Decl; +} // namespace ast namespace ResolvExpr { @@ -40,4 +45,7 @@ /// Resolves with-stmts and with-clauses on functions void resolveWithExprs( std::list< Declaration * > & translationUnit ); + + /// Checks types and binds syntactic constructs to typed representations + void resolve( std::list< ast::ptr >& translationUnit ); } // namespace ResolvExpr Index: src/ResolvExpr/TypeEnvironment.cc =================================================================== --- src/ResolvExpr/TypeEnvironment.cc (revision 7564e10d60badc52604ddc7491f9465ec58795f3) +++ src/ResolvExpr/TypeEnvironment.cc (revision 67130fe7c6ae00bc7c6da280f8b700e5bc850a3c) @@ -205,8 +205,8 @@ // attempt to unify bound types std::unique_ptr toType{ to.type->clone() }, fromType{ from.type->clone() }; - WidenMode widenMode{ to.allowWidening, from.allowWidening }; + WidenMode widen{ to.allowWidening, from.allowWidening }; Type* common = nullptr; AssertionSet need, have; - if ( unifyInexact( toType.get(), fromType.get(), *this, need, have, openVars, widenMode, indexer, common ) ) { + if ( unifyInexact( toType.get(), fromType.get(), *this, need, have, openVars, widen, indexer, common ) ) { // unifies, set common type if necessary if ( common ) { @@ -343,5 +343,5 @@ } - bool TypeEnvironment::bindVar( TypeInstType *typeInst, Type *bindTo, const TypeDecl::Data & data, AssertionSet &need, AssertionSet &have, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer ) { + bool TypeEnvironment::bindVar( TypeInstType *typeInst, Type *bindTo, const TypeDecl::Data & data, AssertionSet &need, AssertionSet &have, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer ) { // remove references from other, so that type variables can only bind to value types @@ -362,5 +362,5 @@ std::unique_ptr< Type > newType( curClass->type->clone() ); newType->get_qualifiers() = typeInst->get_qualifiers(); - if ( unifyInexact( newType.get(), bindTo, *this, need, have, openVars, widenMode & WidenMode( curClass->allowWidening, true ), indexer, common ) ) { + if ( unifyInexact( newType.get(), bindTo, *this, need, have, openVars, widen & WidenMode( curClass->allowWidening, true ), indexer, common ) ) { if ( common ) { common->get_qualifiers() = Type::Qualifiers{}; @@ -372,5 +372,5 @@ newType->get_qualifiers() = Type::Qualifiers{}; curClass->set_type( newType ); - curClass->allowWidening = widenMode.widenFirst && widenMode.widenSecond; + curClass->allowWidening = widen.first && widen.second; } // if } else { @@ -379,5 +379,5 @@ newClass.type = bindTo->clone(); newClass.type->get_qualifiers() = Type::Qualifiers(); - newClass.allowWidening = widenMode.widenFirst && widenMode.widenSecond; + newClass.allowWidening = widen.first && widen.second; newClass.data = data; env.push_back( std::move(newClass) ); @@ -388,5 +388,5 @@ bool TypeEnvironment::bindVarToVar( TypeInstType *var1, TypeInstType *var2, TypeDecl::Data && data, AssertionSet &need, AssertionSet &have, - const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer ) { + const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer ) { auto class1 = internal_lookup( var1->get_name() ); @@ -395,5 +395,5 @@ // exit early if variables already bound together if ( class1 != env.end() && class1 == class2 ) { - class1->allowWidening &= widenMode; + class1->allowWidening &= widen; return true; } @@ -408,5 +408,5 @@ type1 = class1->type; } // if - widen1 = widenMode.widenFirst && class1->allowWidening; + widen1 = widen.first && class1->allowWidening; } // if if ( class2 != env.end() ) { @@ -415,5 +415,5 @@ type2 = class2->type; } // if - widen2 = widenMode.widenSecond && class2->allowWidening; + widen2 = widen.second && class2->allowWidening; } // if Index: src/ResolvExpr/TypeEnvironment.h =================================================================== --- src/ResolvExpr/TypeEnvironment.h (revision 7564e10d60badc52604ddc7491f9465ec58795f3) +++ src/ResolvExpr/TypeEnvironment.h (revision 67130fe7c6ae00bc7c6da280f8b700e5bc850a3c) @@ -136,9 +136,9 @@ /// Binds the type class represented by `typeInst` to the type `bindTo`; will add /// the class if needed. Returns false on failure. - bool bindVar( TypeInstType *typeInst, Type *bindTo, const TypeDecl::Data & data, AssertionSet &need, AssertionSet &have, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer ); + bool bindVar( TypeInstType *typeInst, Type *bindTo, const TypeDecl::Data & data, AssertionSet &need, AssertionSet &have, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer ); /// Binds the type classes represented by `var1` and `var2` together; will add /// one or both classes if needed. Returns false on failure. - bool bindVarToVar( TypeInstType *var1, TypeInstType *var2, TypeDecl::Data && data, AssertionSet &need, AssertionSet &have, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer ); + bool bindVarToVar( TypeInstType *var1, TypeInstType *var2, TypeDecl::Data && data, AssertionSet &need, AssertionSet &have, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer ); /// Disallows widening for all bindings in the environment Index: src/ResolvExpr/Unify.cc =================================================================== --- src/ResolvExpr/Unify.cc (revision 7564e10d60badc52604ddc7491f9465ec58795f3) +++ src/ResolvExpr/Unify.cc (revision 67130fe7c6ae00bc7c6da280f8b700e5bc850a3c) @@ -14,28 +14,36 @@ // -#include // for assertf, assert -#include // for back_insert_iterator, back_inserter -#include // for _Rb_tree_const_iterator, _Rb_tree_i... -#include // for unique_ptr -#include // for set -#include // for string, operator==, operator!=, bas... -#include // for pair, move +#include "Unify.h" + +#include // for assertf, assert +#include // for back_insert_iterator, back_inserter +#include // for _Rb_tree_const_iterator, _Rb_tree_i... +#include // for unique_ptr +#include // for set +#include // for string, operator==, operator!=, bas... +#include // for pair, move #include +#include "AST/Decl.hpp" #include "AST/Node.hpp" +#include "AST/Pass.hpp" #include "AST/Type.hpp" -#include "Common/PassVisitor.h" // for PassVisitor -#include "FindOpenVars.h" // for findOpenVars -#include "Parser/LinkageSpec.h" // for C -#include "SynTree/Constant.h" // for Constant -#include "SynTree/Declaration.h" // for TypeDecl, TypeDecl::Data, Declarati... -#include "SynTree/Expression.h" // for TypeExpr, Expression, ConstantExpr -#include "SynTree/Mutator.h" // for Mutator -#include "SynTree/Type.h" // for Type, TypeInstType, FunctionType -#include "SynTree/Visitor.h" // for Visitor -#include "Tuples/Tuples.h" // for isTtype -#include "TypeEnvironment.h" // for EqvClass, AssertionSet, OpenVarSet -#include "Unify.h" -#include "typeops.h" // for flatten, occurs, commonType +#include "AST/TypeEnvironment.hpp" +#include "Common/PassVisitor.h" // for PassVisitor +#include "FindOpenVars.h" // for findOpenVars +#include "Parser/LinkageSpec.h" // for C +#include "SynTree/Constant.h" // for Constant +#include "SynTree/Declaration.h" // for TypeDecl, TypeDecl::Data, Declarati... +#include "SynTree/Expression.h" // for TypeExpr, Expression, ConstantExpr +#include "SynTree/Mutator.h" // for Mutator +#include "SynTree/Type.h" // for Type, TypeInstType, FunctionType +#include "SynTree/Visitor.h" // for Visitor +#include "Tuples/Tuples.h" // for isTtype +#include "TypeEnvironment.h" // for EqvClass, AssertionSet, OpenVarSet +#include "typeops.h" // for flatten, occurs, commonType + +namespace ast { + class SymbolTable; +} namespace SymTab { @@ -47,6 +55,6 @@ namespace ResolvExpr { - struct Unify : public WithShortCircuiting { - Unify( Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer ); + struct Unify_old : public WithShortCircuiting { + Unify_old( Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer ); bool get_result() const { return result; } @@ -80,5 +88,5 @@ AssertionSet &haveAssertions; const OpenVarSet &openVars; - WidenMode widenMode; + WidenMode widen; const SymTab::Indexer &indexer; }; @@ -86,6 +94,11 @@ /// Attempts an inexact unification of type1 and type2. /// Returns false if no such unification; if the types can be unified, sets common (unless they unify exactly and have identical type qualifiers) - bool unifyInexact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer, Type *&common ); - bool unifyExact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer ); + bool unifyInexact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer, Type *&common ); + bool unifyExact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer ); + + bool unifyExact( + const ast::Type * type1, const ast::Type * type2, ast::TypeEnvironment & env, + ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open, + WidenMode widen, const ast::SymbolTable & symtab ); bool typesCompatible( Type *first, Type *second, const SymTab::Indexer &indexer, const TypeEnvironment &env ) { @@ -106,4 +119,22 @@ delete newSecond; return result; + } + + bool typesCompatible( + const ast::Type * first, const ast::Type * second, const ast::SymbolTable & symtab, + const ast::TypeEnvironment & env ) { + ast::TypeEnvironment newEnv; + ast::OpenVarSet open, closed; + ast::AssertionSet need, have; + + ast::ptr newFirst{ first }, newSecond{ second }; + env.apply( newFirst ); + env.apply( newSecond ); + + findOpenVars( newFirst, open, closed, need, have, FirstClosed ); + findOpenVars( newSecond, open, closed, need, have, FirstOpen ); + + return unifyExact( + newFirst, newSecond, newEnv, need, have, open, noWiden(), symtab ); } @@ -132,4 +163,21 @@ } + bool typesCompatibleIgnoreQualifiers( + const ast::Type * first, const ast::Type * second, const ast::SymbolTable & symtab, + const ast::TypeEnvironment & env ) { + ast::TypeEnvironment newEnv; + ast::OpenVarSet open; + ast::AssertionSet need, have; + + ast::ptr newFirst{ first }, newSecond{ second }; + env.apply( newFirst ); + env.apply( newSecond ); + reset_qualifiers( newFirst ); + reset_qualifiers( newSecond ); + + return unifyExact( + newFirst, newSecond, newEnv, need, have, open, noWiden(), symtab ); + } + bool unify( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, OpenVarSet &openVars, const SymTab::Indexer &indexer ) { OpenVarSet closedVars; @@ -154,5 +202,5 @@ } - bool unifyExact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer ) { + bool unifyExact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer ) { #ifdef DEBUG TypeEnvironment debugEnv( env ); @@ -181,12 +229,12 @@ result = env.bindVarToVar( var1, var2, TypeDecl::Data{ entry1->second, entry2->second }, needAssertions, - haveAssertions, openVars, widenMode, indexer ); + haveAssertions, openVars, widen, indexer ); } } else if ( isopen1 ) { - result = env.bindVar( var1, type2, entry1->second, needAssertions, haveAssertions, openVars, widenMode, indexer ); - } else if ( isopen2 ) { // TODO: swap widenMode values in call, since type positions are flipped? - result = env.bindVar( var2, type1, entry2->second, needAssertions, haveAssertions, openVars, widenMode, indexer ); + result = env.bindVar( var1, type2, entry1->second, needAssertions, haveAssertions, openVars, widen, indexer ); + } else if ( isopen2 ) { // TODO: swap widen values in call, since type positions are flipped? + result = env.bindVar( var2, type1, entry2->second, needAssertions, haveAssertions, openVars, widen, indexer ); } else { - PassVisitor comparator( type2, env, needAssertions, haveAssertions, openVars, widenMode, indexer ); + PassVisitor comparator( type2, env, needAssertions, haveAssertions, openVars, widen, indexer ); type1->accept( comparator ); result = comparator.pass.get_result(); @@ -213,5 +261,5 @@ } - bool unifyInexact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer, Type *&common ) { + bool unifyInexact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer, Type *&common ) { Type::Qualifiers tq1 = type1->get_qualifiers(), tq2 = type2->get_qualifiers(); type1->get_qualifiers() = Type::Qualifiers(); @@ -225,9 +273,9 @@ std::cerr << std::endl; #endif - if ( ! unifyExact( type1, type2, env, needAssertions, haveAssertions, openVars, widenMode, indexer ) ) { + if ( ! unifyExact( type1, type2, env, needAssertions, haveAssertions, openVars, widen, indexer ) ) { #ifdef DEBUG std::cerr << "unifyInexact: no exact unification found" << std::endl; #endif - if ( ( common = commonType( type1, type2, widenMode.widenFirst, widenMode.widenSecond, indexer, env, openVars ) ) ) { + if ( ( common = commonType( type1, type2, widen.first, widen.second, indexer, env, openVars ) ) ) { common->get_qualifiers() = tq1 | tq2; #ifdef DEBUG @@ -245,5 +293,5 @@ } else { if ( tq1 != tq2 ) { - if ( ( tq1 > tq2 || widenMode.widenFirst ) && ( tq2 > tq1 || widenMode.widenSecond ) ) { + if ( ( tq1 > tq2 || widen.first ) && ( tq2 > tq1 || widen.second ) ) { common = type1->clone(); common->get_qualifiers() = tq1 | tq2; @@ -263,13 +311,13 @@ } - Unify::Unify( Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer ) - : result( false ), type2( type2 ), env( env ), needAssertions( needAssertions ), haveAssertions( haveAssertions ), openVars( openVars ), widenMode( widenMode ), indexer( indexer ) { - } - - void Unify::postvisit( __attribute__((unused)) VoidType *voidType) { + Unify_old::Unify_old( Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer ) + : result( false ), type2( type2 ), env( env ), needAssertions( needAssertions ), haveAssertions( haveAssertions ), openVars( openVars ), widen( widen ), indexer( indexer ) { + } + + void Unify_old::postvisit( __attribute__((unused)) VoidType *voidType) { result = dynamic_cast< VoidType* >( type2 ); } - void Unify::postvisit(BasicType *basicType) { + void Unify_old::postvisit(BasicType *basicType) { if ( BasicType *otherBasic = dynamic_cast< BasicType* >( type2 ) ) { result = basicType->get_kind() == otherBasic->get_kind(); @@ -299,5 +347,5 @@ } - void Unify::postvisit(PointerType *pointerType) { + void Unify_old::postvisit(PointerType *pointerType) { if ( PointerType *otherPointer = dynamic_cast< PointerType* >( type2 ) ) { result = unifyExact( pointerType->get_base(), otherPointer->get_base(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer ); @@ -307,5 +355,5 @@ } - void Unify::postvisit(ReferenceType *refType) { + void Unify_old::postvisit(ReferenceType *refType) { if ( ReferenceType *otherRef = dynamic_cast< ReferenceType* >( type2 ) ) { result = unifyExact( refType->get_base(), otherRef->get_base(), env, needAssertions, haveAssertions, openVars, WidenMode( false, false ), indexer ); @@ -315,5 +363,5 @@ } - void Unify::postvisit(ArrayType *arrayType) { + void Unify_old::postvisit(ArrayType *arrayType) { ArrayType *otherArray = dynamic_cast< ArrayType* >( type2 ); // to unify, array types must both be VLA or both not VLA @@ -395,7 +443,7 @@ /// If this isn't done then argument lists can have wildly different /// size and structure, when they should be compatible. - struct TtypeExpander : public WithShortCircuiting { + struct TtypeExpander_old : public WithShortCircuiting { TypeEnvironment & tenv; - TtypeExpander( TypeEnvironment & tenv ) : tenv( tenv ) {} + TtypeExpander_old( TypeEnvironment & tenv ) : tenv( tenv ) {} void premutate( TypeInstType * ) { visit_children = false; } Type * postmutate( TypeInstType * typeInst ) { @@ -416,5 +464,5 @@ dst.clear(); for ( DeclarationWithType * dcl : src ) { - PassVisitor expander( env ); + PassVisitor expander( env ); dcl->acceptMutator( expander ); std::list< Type * > types; @@ -431,5 +479,5 @@ } - void Unify::postvisit(FunctionType *functionType) { + void Unify_old::postvisit(FunctionType *functionType) { FunctionType *otherFunction = dynamic_cast< FunctionType* >( type2 ); if ( otherFunction && functionType->get_isVarArgs() == otherFunction->get_isVarArgs() ) { @@ -442,5 +490,10 @@ // sizes don't have to match if ttypes are involved; need to be more precise wrt where the ttype is to prevent errors - if ( (flatFunc->parameters.size() == flatOther->parameters.size() && flatFunc->returnVals.size() == flatOther->returnVals.size()) || flatFunc->isTtype() || flatOther->isTtype() ) { + if ( + (flatFunc->parameters.size() == flatOther->parameters.size() && + flatFunc->returnVals.size() == flatOther->returnVals.size()) + || flatFunc->isTtype() + || flatOther->isTtype() + ) { if ( unifyDeclList( flatFunc->parameters.begin(), flatFunc->parameters.end(), flatOther->parameters.begin(), flatOther->parameters.end(), env, needAssertions, haveAssertions, openVars, indexer ) ) { if ( unifyDeclList( flatFunc->returnVals.begin(), flatFunc->returnVals.end(), flatOther->returnVals.begin(), flatOther->returnVals.end(), env, needAssertions, haveAssertions, openVars, indexer ) ) { @@ -458,5 +511,5 @@ template< typename RefType > - void Unify::handleRefType( RefType *inst, Type *other ) { + void Unify_old::handleRefType( RefType *inst, Type *other ) { // check that other type is compatible and named the same RefType *otherStruct = dynamic_cast< RefType* >( other ); @@ -465,5 +518,5 @@ template< typename RefType > - void Unify::handleGenericRefType( RefType *inst, Type *other ) { + void Unify_old::handleGenericRefType( RefType *inst, Type *other ) { // Check that other type is compatible and named the same handleRefType( inst, other ); @@ -533,21 +586,21 @@ } - void Unify::postvisit(StructInstType *structInst) { + void Unify_old::postvisit(StructInstType *structInst) { handleGenericRefType( structInst, type2 ); } - void Unify::postvisit(UnionInstType *unionInst) { + void Unify_old::postvisit(UnionInstType *unionInst) { handleGenericRefType( unionInst, type2 ); } - void Unify::postvisit(EnumInstType *enumInst) { + void Unify_old::postvisit(EnumInstType *enumInst) { handleRefType( enumInst, type2 ); } - void Unify::postvisit(TraitInstType *contextInst) { + void Unify_old::postvisit(TraitInstType *contextInst) { handleRefType( contextInst, type2 ); } - void Unify::postvisit(TypeInstType *typeInst) { + void Unify_old::postvisit(TypeInstType *typeInst) { assert( openVars.find( typeInst->get_name() ) == openVars.end() ); TypeInstType *otherInst = dynamic_cast< TypeInstType* >( type2 ); @@ -604,5 +657,5 @@ } - void Unify::postvisit(TupleType *tupleType) { + void Unify_old::postvisit(TupleType *tupleType) { if ( TupleType *otherTuple = dynamic_cast< TupleType* >( type2 ) ) { std::unique_ptr flat1( tupleType->clone() ); @@ -610,5 +663,5 @@ std::list types1, types2; - PassVisitor expander( env ); + PassVisitor expander( env ); flat1->acceptMutator( expander ); flat2->acceptMutator( expander ); @@ -621,13 +674,13 @@ } - void Unify::postvisit( __attribute__((unused)) VarArgsType *varArgsType ) { + void Unify_old::postvisit( __attribute__((unused)) VarArgsType *varArgsType ) { result = dynamic_cast< VarArgsType* >( type2 ); } - void Unify::postvisit( __attribute__((unused)) ZeroType *zeroType ) { + void Unify_old::postvisit( __attribute__((unused)) ZeroType *zeroType ) { result = dynamic_cast< ZeroType* >( type2 ); } - void Unify::postvisit( __attribute__((unused)) OneType *oneType ) { + void Unify_old::postvisit( __attribute__((unused)) OneType *oneType ) { result = dynamic_cast< OneType* >( type2 ); } @@ -647,4 +700,524 @@ } + class Unify_new final : public ast::WithShortCircuiting { + const ast::Type * type2; + ast::TypeEnvironment & tenv; + ast::AssertionSet & need; + ast::AssertionSet & have; + const ast::OpenVarSet & open; + WidenMode widen; + const ast::SymbolTable & symtab; + public: + bool result; + + Unify_new( + const ast::Type * type2, ast::TypeEnvironment & env, ast::AssertionSet & need, + ast::AssertionSet & have, const ast::OpenVarSet & open, WidenMode widen, + const ast::SymbolTable & symtab ) + : type2(type2), tenv(env), need(need), have(have), open(open), widen(widen), + symtab(symtab), result(false) {} + + void previsit( const ast::Node * ) { visit_children = false; } + + void postvisit( const ast::VoidType * ) { + result = dynamic_cast< const ast::VoidType * >( type2 ); + } + + void postvisit( const ast::BasicType * basic ) { + if ( auto basic2 = dynamic_cast< const ast::BasicType * >( type2 ) ) { + result = basic->kind == basic2->kind; + } + } + + void postvisit( const ast::PointerType * pointer ) { + if ( auto pointer2 = dynamic_cast< const ast::PointerType * >( type2 ) ) { + result = unifyExact( + pointer->base, pointer2->base, tenv, need, have, open, + noWiden(), symtab ); + } + } + + void postvisit( const ast::ArrayType * array ) { + auto array2 = dynamic_cast< const ast::ArrayType * >( type2 ); + if ( ! array2 ) return; + + // to unify, array types must both be VLA or both not VLA and both must have a + // dimension expression or not have a dimension + if ( array->isVarLen != array2->isVarLen ) return; + if ( ! array->isVarLen && ! array2->isVarLen + && array->dimension && array2->dimension ) { + auto ce1 = array->dimension.as< ast::ConstantExpr >(); + auto ce2 = array2->dimension.as< ast::ConstantExpr >(); + + // see C11 Reference Manual 6.7.6.2.6 + // two array types with size specifiers that are integer constant expressions are + // compatible if both size specifiers have the same constant value + if ( ce1 && ce2 && ce1->intValue() != ce2->intValue() ) return; + } + + result = unifyExact( + array->base, array2->base, tenv, need, have, open, noWiden(), + symtab ); + } + + void postvisit( const ast::ReferenceType * ref ) { + if ( auto ref2 = dynamic_cast< const ast::ReferenceType * >( type2 ) ) { + result = unifyExact( + ref->base, ref2->base, tenv, need, have, open, noWiden(), + symtab ); + } + } + + private: + /// Replaces ttype variables with their bound types. + /// If this isn't done when satifying ttype assertions, then argument lists can have + /// different size and structure when they should be compatible. + struct TtypeExpander_new : public ast::WithShortCircuiting { + ast::TypeEnvironment & tenv; + + TtypeExpander_new( ast::TypeEnvironment & env ) : tenv( env ) {} + + const ast::Type * postvisit( const ast::TypeInstType * typeInst ) { + if ( const ast::EqvClass * clz = tenv.lookup( typeInst->name ) ) { + // expand ttype parameter into its actual type + if ( clz->data.kind == ast::TypeVar::Ttype && clz->bound ) { + return clz->bound; + } + } + return typeInst; + } + }; + + /// returns flattened version of `src` + static std::vector< ast::ptr< ast::DeclWithType > > flattenList( + const std::vector< ast::ptr< ast::DeclWithType > > & src, ast::TypeEnvironment & env + ) { + std::vector< ast::ptr< ast::DeclWithType > > dst; + dst.reserve( src.size() ); + for ( const ast::DeclWithType * d : src ) { + ast::Pass expander{ env }; + d = d->accept( expander ); + auto types = flatten( d->get_type() ); + for ( ast::ptr< ast::Type > & t : types ) { + // outermost const, volatile, _Atomic qualifiers in parameters should not play + // a role in the unification of function types, since they do not determine + // whether a function is callable. + // NOTE: **must** consider at least mutex qualifier, since functions can be + // overloaded on outermost mutex and a mutex function has different + // requirements than a non-mutex function + remove_qualifiers( t, ast::CV::Const | ast::CV::Volatile | ast::CV::Atomic ); + dst.emplace_back( new ast::ObjectDecl{ d->location, "", t } ); + } + } + return dst; + } + + /// Creates a tuple type based on a list of DeclWithType + template< typename Iter > + static ast::ptr< ast::Type > tupleFromDecls( Iter crnt, Iter end ) { + std::vector< ast::ptr< ast::Type > > types; + while ( crnt != end ) { + // it is guaranteed that a ttype variable will be bound to a flat tuple, so ensure + // that this results in a flat tuple + flatten( (*crnt)->get_type(), types ); + + ++crnt; + } + + return { new ast::TupleType{ std::move(types) } }; + } + + template< typename Iter > + static bool unifyDeclList( + Iter crnt1, Iter end1, Iter crnt2, Iter end2, ast::TypeEnvironment & env, + ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open, + const ast::SymbolTable & symtab + ) { + while ( crnt1 != end1 && crnt2 != end2 ) { + const ast::Type * t1 = (*crnt1)->get_type(); + const ast::Type * t2 = (*crnt2)->get_type(); + bool isTuple1 = Tuples::isTtype( t1 ); + bool isTuple2 = Tuples::isTtype( t2 ); + + // assumes here that ttype *must* be last parameter + if ( isTuple1 && ! isTuple2 ) { + // combine remainder of list2, then unify + return unifyExact( + t1, tupleFromDecls( crnt2, end2 ), env, need, have, open, + noWiden(), symtab ); + } else if ( ! isTuple1 && isTuple2 ) { + // combine remainder of list1, then unify + return unifyExact( + tupleFromDecls( crnt1, end1 ), t2, env, need, have, open, + noWiden(), symtab ); + } + + if ( ! unifyExact( + t1, t2, env, need, have, open, noWiden(), symtab ) + ) return false; + + ++crnt1; ++crnt2; + } + + // May get to the end of one argument list before the other. This is only okay if the + // other is a ttype + if ( crnt1 != end1 ) { + // try unifying empty tuple with ttype + const ast::Type * t1 = (*crnt1)->get_type(); + if ( ! Tuples::isTtype( t1 ) ) return false; + return unifyExact( + t1, tupleFromDecls( crnt2, end2 ), env, need, have, open, + noWiden(), symtab ); + } else if ( crnt2 != end2 ) { + // try unifying empty tuple with ttype + const ast::Type * t2 = (*crnt2)->get_type(); + if ( ! Tuples::isTtype( t2 ) ) return false; + return unifyExact( + tupleFromDecls( crnt1, end1 ), t2, env, need, have, open, + noWiden(), symtab ); + } + + return true; + } + + static bool unifyDeclList( + const std::vector< ast::ptr< ast::DeclWithType > > & list1, + const std::vector< ast::ptr< ast::DeclWithType > > & list2, + ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have, + const ast::OpenVarSet & open, const ast::SymbolTable & symtab + ) { + return unifyDeclList( + list1.begin(), list1.end(), list2.begin(), list2.end(), env, need, have, open, + symtab ); + } + + static void markAssertionSet( ast::AssertionSet & assns, const ast::DeclWithType * assn ) { + auto i = assns.find( assn ); + if ( i != assns.end() ) { + i->second.isUsed = true; + } + } + + /// mark all assertions in `type` used in both `assn1` and `assn2` + static void markAssertions( + ast::AssertionSet & assn1, ast::AssertionSet & assn2, + const ast::ParameterizedType * type + ) { + for ( const auto & tyvar : type->forall ) { + for ( const ast::DeclWithType * assert : tyvar->assertions ) { + markAssertionSet( assn1, assert ); + markAssertionSet( assn2, assert ); + } + } + } + + public: + void postvisit( const ast::FunctionType * func ) { + auto func2 = dynamic_cast< const ast::FunctionType * >( type2 ); + if ( ! func2 ) return; + + if ( func->isVarArgs != func2->isVarArgs ) return; + + // Flatten the parameter lists for both functions so that tuple structure does not + // affect unification. Does not actually mutate function parameters. + auto params = flattenList( func->params, tenv ); + auto params2 = flattenList( func2->params, tenv ); + + // sizes don't have to match if ttypes are involved; need to be more precise w.r.t. + // where the ttype is to prevent errors + if ( + ( params.size() != params2.size() || func->returns.size() != func2->returns.size() ) + && ! func->isTtype() + && ! func2->isTtype() + ) return; + + if ( ! unifyDeclList( params, params2, tenv, need, have, open, symtab ) ) return; + if ( ! unifyDeclList( + func->returns, func2->returns, tenv, need, have, open, symtab ) ) return; + + markAssertions( have, need, func ); + markAssertions( have, need, func2 ); + + result = true; + } + + private: + template< typename RefType > + const RefType * handleRefType( const RefType * inst, const ast::Type * other ) { + // check that the other type is compatible and named the same + auto otherInst = dynamic_cast< const RefType * >( other ); + result = otherInst && inst->name == otherInst->name; + return otherInst; + } + + /// Creates a tuple type based on a list of TypeExpr + template< typename Iter > + static const ast::Type * tupleFromExprs( + const ast::TypeExpr * param, Iter & crnt, Iter end, ast::CV::Qualifiers qs + ) { + std::vector< ast::ptr< ast::Type > > types; + do { + types.emplace_back( param->type ); + + ++crnt; + if ( crnt == end ) break; + param = strict_dynamic_cast< const ast::TypeExpr * >( crnt->get() ); + } while(true); + + return new ast::TupleType{ std::move(types), qs }; + } + + template< typename RefType > + void handleGenericRefType( const RefType * inst, const ast::Type * other ) { + // check that other type is compatible and named the same + const RefType * inst2 = handleRefType( inst, other ); + if ( ! inst2 ) return; + + // check that parameters of types unify, if any + const std::vector< ast::ptr< ast::Expr > > & params = inst->params; + const std::vector< ast::ptr< ast::Expr > > & params2 = inst2->params; + + auto it = params.begin(); + auto jt = params2.begin(); + for ( ; it != params.end() && jt != params2.end(); ++it, ++jt ) { + auto param = strict_dynamic_cast< const ast::TypeExpr * >( it->get() ); + auto param2 = strict_dynamic_cast< const ast::TypeExpr * >( jt->get() ); + + ast::ptr< ast::Type > pty = param->type; + ast::ptr< ast::Type > pty2 = param2->type; + + bool isTuple = Tuples::isTtype( pty ); + bool isTuple2 = Tuples::isTtype( pty2 ); + + if ( isTuple && isTuple2 ) { + ++it; ++jt; // skip ttype parameters before break + } else if ( isTuple ) { + // bundle remaining params into tuple + pty2 = tupleFromExprs( param2, jt, params2.end(), pty->qualifiers ); + ++it; // skip ttype parameter for break + } else if ( isTuple2 ) { + // bundle remaining params into tuple + pty = tupleFromExprs( param, it, params.end(), pty2->qualifiers ); + ++jt; // skip ttype parameter for break + } + + if ( ! unifyExact( + pty, pty2, tenv, need, have, open, noWiden(), symtab ) ) { + result = false; + return; + } + + // ttype parameter should be last + if ( isTuple || isTuple2 ) break; + } + result = it == params.end() && jt == params2.end(); + } + + public: + void postvisit( const ast::StructInstType * aggrType ) { + handleGenericRefType( aggrType, type2 ); + } + + void postvisit( const ast::UnionInstType * aggrType ) { + handleGenericRefType( aggrType, type2 ); + } + + void postvisit( const ast::EnumInstType * aggrType ) { + handleRefType( aggrType, type2 ); + } + + void postvisit( const ast::TraitInstType * aggrType ) { + handleRefType( aggrType, type2 ); + } + + void postvisit( const ast::TypeInstType * typeInst ) { + assert( open.find( typeInst->name ) == open.end() ); + handleRefType( typeInst, type2 ); + } + + private: + /// Creates a tuple type based on a list of Type + static ast::ptr< ast::Type > tupleFromTypes( + const std::vector< ast::ptr< ast::Type > > & tys + ) { + std::vector< ast::ptr< ast::Type > > out; + for ( const ast::Type * ty : tys ) { + // it is guaranteed that a ttype variable will be bound to a flat tuple, so ensure + // that this results in a flat tuple + flatten( ty, out ); + } + + return { new ast::TupleType{ std::move(out) } }; + } + + static bool unifyList( + const std::vector< ast::ptr< ast::Type > > & list1, + const std::vector< ast::ptr< ast::Type > > & list2, ast::TypeEnvironment & env, + ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open, + const ast::SymbolTable & symtab + ) { + auto crnt1 = list1.begin(); + auto crnt2 = list2.begin(); + while ( crnt1 != list1.end() && crnt2 != list2.end() ) { + const ast::Type * t1 = *crnt1; + const ast::Type * t2 = *crnt2; + bool isTuple1 = Tuples::isTtype( t1 ); + bool isTuple2 = Tuples::isTtype( t2 ); + + // assumes ttype must be last parameter + if ( isTuple1 && ! isTuple2 ) { + // combine entirety of list2, then unify + return unifyExact( + t1, tupleFromTypes( list2 ), env, need, have, open, + noWiden(), symtab ); + } else if ( ! isTuple1 && isTuple2 ) { + // combine entirety of list1, then unify + return unifyExact( + tupleFromTypes( list1 ), t2, env, need, have, open, + noWiden(), symtab ); + } + + if ( ! unifyExact( + t1, t2, env, need, have, open, noWiden(), symtab ) + ) return false; + + ++crnt1; ++crnt2; + } + + if ( crnt1 != list1.end() ) { + // try unifying empty tuple type with ttype + const ast::Type * t1 = *crnt1; + if ( ! Tuples::isTtype( t1 ) ) return false; + // xxx - this doesn't generate an empty tuple, contrary to comment; both ported + // from Rob's code + return unifyExact( + t1, tupleFromTypes( list2 ), env, need, have, open, + noWiden(), symtab ); + } else if ( crnt2 != list2.end() ) { + // try unifying empty tuple with ttype + const ast::Type * t2 = *crnt2; + if ( ! Tuples::isTtype( t2 ) ) return false; + // xxx - this doesn't generate an empty tuple, contrary to comment; both ported + // from Rob's code + return unifyExact( + tupleFromTypes( list1 ), t2, env, need, have, open, + noWiden(), symtab ); + } + + return true; + } + + public: + void postvisit( const ast::TupleType * tuple ) { + auto tuple2 = dynamic_cast< const ast::TupleType * >( type2 ); + if ( ! tuple2 ) return; + + ast::Pass expander{ tenv }; + const ast::Type * flat = tuple->accept( expander ); + const ast::Type * flat2 = tuple2->accept( expander ); + + auto types = flatten( flat ); + auto types2 = flatten( flat2 ); + + result = unifyList( types, types2, tenv, need, have, open, symtab ); + } + + void postvisit( const ast::VarArgsType * ) { + result = dynamic_cast< const ast::VarArgsType * >( type2 ); + } + + void postvisit( const ast::ZeroType * ) { + result = dynamic_cast< const ast::ZeroType * >( type2 ); + } + + void postvisit( const ast::OneType * ) { + result = dynamic_cast< const ast::OneType * >( type2 ); + } + + private: + template< typename RefType > void handleRefType( RefType *inst, Type *other ); + template< typename RefType > void handleGenericRefType( RefType *inst, Type *other ); + }; + + bool unify( + const ast::ptr & type1, const ast::ptr & type2, + ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have, + ast::OpenVarSet & open, const ast::SymbolTable & symtab, ast::ptr & common + ) { + ast::OpenVarSet closed; + findOpenVars( type1, open, closed, need, have, FirstClosed ); + findOpenVars( type2, open, closed, need, have, FirstOpen ); + return unifyInexact( + type1, type2, env, need, have, open, WidenMode{ true, true }, symtab, common ); + } + + bool unifyExact( + const ast::Type * type1, const ast::Type * type2, ast::TypeEnvironment & env, + ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open, + WidenMode widen, const ast::SymbolTable & symtab + ) { + if ( type1->qualifiers != type2->qualifiers ) return false; + + auto var1 = dynamic_cast< const ast::TypeInstType * >( type1 ); + auto var2 = dynamic_cast< const ast::TypeInstType * >( type2 ); + ast::OpenVarSet::const_iterator + entry1 = var1 ? open.find( var1->name ) : open.end(), + entry2 = var2 ? open.find( var2->name ) : open.end(); + bool isopen1 = entry1 != open.end(); + bool isopen2 = entry2 != open.end(); + + if ( isopen1 && isopen2 ) { + if ( entry1->second.kind != entry2->second.kind ) return false; + return env.bindVarToVar( + var1, var2, ast::TypeDecl::Data{ entry1->second, entry2->second }, need, have, + open, widen, symtab ); + } else if ( isopen1 ) { + return env.bindVar( var1, type2, entry1->second, need, have, open, widen, symtab ); + } else if ( isopen2 ) { + return env.bindVar( var2, type1, entry2->second, need, have, open, widen, symtab ); + } else { + ast::Pass comparator{ type2, env, need, have, open, widen, symtab }; + type1->accept( comparator ); + return comparator.pass.result; + } + } + + bool unifyInexact( + const ast::ptr & type1, const ast::ptr & type2, + ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have, + const ast::OpenVarSet & open, WidenMode widen, const ast::SymbolTable & symtab, + ast::ptr & common + ) { + ast::CV::Qualifiers q1 = type1->qualifiers, q2 = type2->qualifiers; + + // force t1 and t2 to be cloned if their qualifiers must be stripped, so that type1 and + // type2 are left unchanged; calling convention forces type{1,2}->strong_ref >= 1 + ast::ptr t1{ type1 }, t2{ type2 }; + reset_qualifiers( t1 ); + reset_qualifiers( t2 ); + + if ( unifyExact( t1, t2, env, need, have, open, widen, symtab ) ) { + t1 = nullptr; t2 = nullptr; // release t1, t2 to avoid spurious clones + + // if exact unification on unqualified types, try to merge qualifiers + if ( q1 == q2 || ( ( q1 > q2 || widen.first ) && ( q2 > q1 || widen.second ) ) ) { + common = type1; + reset_qualifiers( common, q1 | q2 ); + return true; + } else { + return false; + } + + } else if (( common = commonType( t1, t2, widen, symtab, env, open ) )) { + t1 = nullptr; t2 = nullptr; // release t1, t2 to avoid spurious clones + + // no exact unification, but common type + reset_qualifiers( common, q1 | q2 ); + return true; + } else { + return false; + } + } + ast::ptr extractResultType( const ast::FunctionType * func ) { if ( func->returns.empty() ) return new ast::VoidType{}; Index: src/ResolvExpr/Unify.h =================================================================== --- src/ResolvExpr/Unify.h (revision 7564e10d60badc52604ddc7491f9465ec58795f3) +++ src/ResolvExpr/Unify.h (revision 67130fe7c6ae00bc7c6da280f8b700e5bc850a3c) @@ -18,14 +18,21 @@ #include // for list +#include "AST/Node.hpp" // for ptr +#include "AST/TypeEnvironment.hpp" // for TypeEnvironment, AssertionSet, OpenVarSet #include "Common/utility.h" // for deleteAll #include "SynTree/Declaration.h" // for TypeDecl, TypeDecl::Data #include "TypeEnvironment.h" // for AssertionSet, OpenVarSet -#include "WidenMode.h" // for WidenMode +#include "WidenMode.h" // for WidenMode class Type; class TypeInstType; namespace SymTab { -class Indexer; -} // namespace SymTab + class Indexer; +} + +namespace ast { + class SymbolTable; + class Type; +} namespace ResolvExpr { @@ -33,5 +40,5 @@ bool unify( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, OpenVarSet &openVars, const SymTab::Indexer &indexer, Type *&commonType ); bool unifyExact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, OpenVarSet &openVars, const SymTab::Indexer &indexer ); - bool unifyInexact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widenMode, const SymTab::Indexer &indexer, Type *&common ); + bool unifyInexact( Type *type1, Type *type2, TypeEnvironment &env, AssertionSet &needAssertions, AssertionSet &haveAssertions, const OpenVarSet &openVars, WidenMode widen, const SymTab::Indexer &indexer, Type *&common ); template< typename Iterator1, typename Iterator2 > @@ -62,4 +69,20 @@ } + bool unify( + const ast::ptr & type1, const ast::ptr & type2, + ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have, + ast::OpenVarSet & open, const ast::SymbolTable & symtab, ast::ptr & common ); + + bool unifyExact( + const ast::Type * type1, const ast::Type * type2, ast::TypeEnvironment & env, + ast::AssertionSet & need, ast::AssertionSet & have, const ast::OpenVarSet & open, + WidenMode widen, const ast::SymbolTable & symtab ); + + bool unifyInexact( + const ast::ptr & type1, const ast::ptr & type2, + ast::TypeEnvironment & env, ast::AssertionSet & need, ast::AssertionSet & have, + const ast::OpenVarSet & open, WidenMode widen, const ast::SymbolTable & symtab, + ast::ptr & common ); + } // namespace ResolvExpr Index: src/ResolvExpr/WidenMode.h =================================================================== --- src/ResolvExpr/WidenMode.h (revision 7564e10d60badc52604ddc7491f9465ec58795f3) +++ src/ResolvExpr/WidenMode.h (revision 67130fe7c6ae00bc7c6da280f8b700e5bc850a3c) @@ -18,13 +18,28 @@ namespace ResolvExpr { struct WidenMode { - WidenMode( bool widenFirst, bool widenSecond ): widenFirst( widenFirst ), widenSecond( widenSecond ) {} - WidenMode &operator|=( const WidenMode &other ) { widenFirst |= other.widenFirst; widenSecond |= other.widenSecond; return *this; } - WidenMode &operator&=( const WidenMode &other ) { widenFirst &= other.widenFirst; widenSecond &= other.widenSecond; return *this; } - WidenMode operator|( const WidenMode &other ) { WidenMode newWM( *this ); newWM |= other; return newWM; } - WidenMode operator&( const WidenMode &other ) { WidenMode newWM( *this ); newWM &= other; return newWM; } - operator bool() { return widenFirst && widenSecond; } + WidenMode( bool first, bool second ): first( first ), second( second ) {} + + WidenMode &operator|=( const WidenMode &other ) { + first |= other.first; second |= other.second; return *this; + } - bool widenFirst : 1, widenSecond : 1; + WidenMode &operator&=( const WidenMode &other ) { + first &= other.first; second &= other.second; return *this; + } + + WidenMode operator|( const WidenMode &other ) { + WidenMode newWM( *this ); newWM |= other; return newWM; + } + + WidenMode operator&( const WidenMode &other ) { + WidenMode newWM( *this ); newWM &= other; return newWM; + } + + operator bool() { return first && second; } + + bool first : 1, second : 1; }; + + static inline WidenMode noWiden() { return { false, false }; } } // namespace ResolvExpr Index: src/ResolvExpr/typeops.h =================================================================== --- src/ResolvExpr/typeops.h (revision 7564e10d60badc52604ddc7491f9465ec58795f3) +++ src/ResolvExpr/typeops.h (revision 67130fe7c6ae00bc7c6da280f8b700e5bc850a3c) @@ -18,11 +18,15 @@ #include +#include "Cost.h" +#include "TypeEnvironment.h" +#include "WidenMode.h" +#include "AST/Fwd.hpp" #include "AST/Node.hpp" +#include "AST/SymbolTable.hpp" #include "AST/Type.hpp" +#include "AST/TypeEnvironment.hpp" #include "SynTree/SynTree.h" #include "SynTree/Type.h" #include "SymTab/Indexer.h" -#include "Cost.h" -#include "TypeEnvironment.h" namespace ResolvExpr { @@ -85,5 +89,4 @@ // in Unify.cc - bool isFtype( Type *type ); bool typesCompatible( Type *, Type *, const SymTab::Indexer &indexer, const TypeEnvironment &env ); bool typesCompatibleIgnoreQualifiers( Type *, Type *, const SymTab::Indexer &indexer, const TypeEnvironment &env ); @@ -99,4 +102,12 @@ } + bool typesCompatible( + const ast::Type *, const ast::Type *, const ast::SymbolTable &, + const ast::TypeEnvironment & env = {} ); + + bool typesCompatibleIgnoreQualifiers( + const ast::Type *, const ast::Type *, const ast::SymbolTable &, + const ast::TypeEnvironment & env = {} ); + /// creates the type represented by the list of returnVals in a FunctionType. The caller owns the return value. Type * extractResultType( FunctionType * functionType ); @@ -106,4 +117,7 @@ // in CommonType.cc Type * commonType( Type *type1, Type *type2, bool widenFirst, bool widenSecond, const SymTab::Indexer &indexer, TypeEnvironment &env, const OpenVarSet &openVars ); + ast::ptr< ast::Type > commonType( + const ast::ptr< ast::Type > & type1, const ast::ptr< ast::Type > & type2, WidenMode widen, + const ast::SymbolTable & symtab, ast::TypeEnvironment & env, const ast::OpenVarSet & open ); // in PolyCost.cc @@ -115,4 +129,5 @@ // in Occurs.cc bool occurs( Type *type, std::string varName, const TypeEnvironment &env ); + // new AST version in TypeEnvironment.cpp (only place it was used in old AST) template @@ -127,6 +142,7 @@ // in AlternativeFinder.cc void referenceToRvalueConversion( Expression *& expr, Cost & cost ); + const ast::Expr * referenceToRvalueConversion( const ast::Expr * expr, Cost & cost ); - // flatten tuple type into list of types + /// flatten tuple type into list of types template< typename OutputIterator > void flatten( Type * type, OutputIterator out ) { @@ -139,5 +155,34 @@ } } + + /// flatten tuple type into existing list of types + static inline void flatten( + const ast::Type * type, std::vector< ast::ptr< ast::Type > > & out + ) { + if ( auto tupleType = dynamic_cast< const ast::TupleType * >( type ) ) { + for ( const ast::Type * t : tupleType->types ) { + flatten( t, out ); + } + } else { + out.emplace_back( type ); + } + } + + /// flatten tuple type into list of types + static inline std::vector< ast::ptr< ast::Type > > flatten( const ast::Type * type ) { + std::vector< ast::ptr< ast::Type > > out; + out.reserve( type->size() ); + flatten( type, out ); + return out; + } + + // in TypeEnvironment.cc + bool isFtype( Type *type ); } // namespace ResolvExpr + +namespace ast { + // in TypeEnvironment.cpp + bool isFtype( const ast::Type * type ); +} // namespace ast // Local Variables: // Index: src/SymTab/Mangler.cc =================================================================== --- src/SymTab/Mangler.cc (revision 7564e10d60badc52604ddc7491f9465ec58795f3) +++ src/SymTab/Mangler.cc (revision 67130fe7c6ae00bc7c6da280f8b700e5bc850a3c) @@ -32,11 +32,13 @@ #include "SynTree/Type.h" // for Type, ReferenceToType, Type::Fora... +#include "AST/Pass.hpp" + namespace SymTab { namespace Mangler { namespace { /// Mangles names to a unique C identifier - struct Mangler : public WithShortCircuiting, public WithVisitorRef, public WithGuards { - Mangler( bool mangleOverridable, bool typeMode, bool mangleGenericParams ); - Mangler( const Mangler & ) = delete; + struct Mangler_old : public WithShortCircuiting, public WithVisitorRef, public WithGuards { + Mangler_old( bool mangleOverridable, bool typeMode, bool mangleGenericParams ); + Mangler_old( const Mangler_old & ) = delete; void previsit( BaseSyntaxNode * ) { visit_children = false; } @@ -77,5 +79,5 @@ public: - Mangler( bool mangleOverridable, bool typeMode, bool mangleGenericParams, + Mangler_old( bool mangleOverridable, bool typeMode, bool mangleGenericParams, int nextVarNum, const VarMapType& varNums ); @@ -85,9 +87,9 @@ void printQualifiers( Type *type ); - }; // Mangler + }; // Mangler_old } // namespace std::string mangle( BaseSyntaxNode * decl, bool mangleOverridable, bool typeMode, bool mangleGenericParams ) { - PassVisitor mangler( mangleOverridable, typeMode, mangleGenericParams ); + PassVisitor mangler( mangleOverridable, typeMode, mangleGenericParams ); maybeAccept( decl, mangler ); return mangler.pass.get_mangleName(); @@ -95,5 +97,5 @@ std::string mangleType( Type * ty ) { - PassVisitor mangler( false, true, true ); + PassVisitor mangler( false, true, true ); maybeAccept( ty, mangler ); return mangler.pass.get_mangleName(); @@ -101,5 +103,5 @@ std::string mangleConcrete( Type * ty ) { - PassVisitor mangler( false, false, false ); + PassVisitor mangler( false, false, false ); maybeAccept( ty, mangler ); return mangler.pass.get_mangleName(); @@ -107,10 +109,10 @@ namespace { - Mangler::Mangler( bool mangleOverridable, bool typeMode, bool mangleGenericParams ) + Mangler_old::Mangler_old( bool mangleOverridable, bool typeMode, bool mangleGenericParams ) : nextVarNum( 0 ), isTopLevel( true ), mangleOverridable( mangleOverridable ), typeMode( typeMode ), mangleGenericParams( mangleGenericParams ) {} - Mangler::Mangler( bool mangleOverridable, bool typeMode, bool mangleGenericParams, + Mangler_old::Mangler_old( bool mangleOverridable, bool typeMode, bool mangleGenericParams, int nextVarNum, const VarMapType& varNums ) : varNums( varNums ), nextVarNum( nextVarNum ), isTopLevel( false ), @@ -118,5 +120,5 @@ mangleGenericParams( mangleGenericParams ) {} - void Mangler::mangleDecl( DeclarationWithType * declaration ) { + void Mangler_old::mangleDecl( DeclarationWithType * declaration ) { bool wasTopLevel = isTopLevel; if ( isTopLevel ) { @@ -148,18 +150,18 @@ } - void Mangler::postvisit( ObjectDecl * declaration ) { + void Mangler_old::postvisit( ObjectDecl * declaration ) { mangleDecl( declaration ); } - void Mangler::postvisit( FunctionDecl * declaration ) { + void Mangler_old::postvisit( FunctionDecl * declaration ) { mangleDecl( declaration ); } - void Mangler::postvisit( VoidType * voidType ) { + void Mangler_old::postvisit( VoidType * voidType ) { printQualifiers( voidType ); mangleName << Encoding::void_t; } - void Mangler::postvisit( BasicType * basicType ) { + void Mangler_old::postvisit( BasicType * basicType ) { printQualifiers( basicType ); assertf( basicType->get_kind() < BasicType::NUMBER_OF_BASIC_TYPES, "Unhandled basic type: %d", basicType->get_kind() ); @@ -167,5 +169,5 @@ } - void Mangler::postvisit( PointerType * pointerType ) { + void Mangler_old::postvisit( PointerType * pointerType ) { printQualifiers( pointerType ); // mangle void (*f)() and void f() to the same name to prevent overloading on functions and function pointers @@ -174,5 +176,5 @@ } - void Mangler::postvisit( ArrayType * arrayType ) { + void Mangler_old::postvisit( ArrayType * arrayType ) { // TODO: encode dimension printQualifiers( arrayType ); @@ -181,5 +183,5 @@ } - void Mangler::postvisit( ReferenceType * refType ) { + void Mangler_old::postvisit( ReferenceType * refType ) { // don't print prefix (e.g. 'R') for reference types so that references and non-references do not overload. // Further, do not print the qualifiers for a reference type (but do run printQualifers because of TypeDecls, etc.), @@ -200,5 +202,5 @@ } - void Mangler::postvisit( FunctionType * functionType ) { + void Mangler_old::postvisit( FunctionType * functionType ) { printQualifiers( functionType ); mangleName << Encoding::function; @@ -217,5 +219,5 @@ } - void Mangler::mangleRef( ReferenceToType * refType, std::string prefix ) { + void Mangler_old::mangleRef( ReferenceToType * refType, std::string prefix ) { printQualifiers( refType ); @@ -236,17 +238,17 @@ } - void Mangler::postvisit( StructInstType * aggregateUseType ) { + void Mangler_old::postvisit( StructInstType * aggregateUseType ) { mangleRef( aggregateUseType, Encoding::struct_t ); } - void Mangler::postvisit( UnionInstType * aggregateUseType ) { + void Mangler_old::postvisit( UnionInstType * aggregateUseType ) { mangleRef( aggregateUseType, Encoding::union_t ); } - void Mangler::postvisit( EnumInstType * aggregateUseType ) { + void Mangler_old::postvisit( EnumInstType * aggregateUseType ) { mangleRef( aggregateUseType, Encoding::enum_t ); } - void Mangler::postvisit( TypeInstType * typeInst ) { + void Mangler_old::postvisit( TypeInstType * typeInst ) { VarMapType::iterator varNum = varNums.find( typeInst->get_name() ); if ( varNum == varNums.end() ) { @@ -264,10 +266,10 @@ } - void Mangler::postvisit( TraitInstType * inst ) { + void Mangler_old::postvisit( TraitInstType * inst ) { printQualifiers( inst ); mangleName << inst->name.size() << inst->name; } - void Mangler::postvisit( TupleType * tupleType ) { + void Mangler_old::postvisit( TupleType * tupleType ) { printQualifiers( tupleType ); mangleName << Encoding::tuple << tupleType->types.size(); @@ -275,5 +277,5 @@ } - void Mangler::postvisit( VarArgsType * varArgsType ) { + void Mangler_old::postvisit( VarArgsType * varArgsType ) { printQualifiers( varArgsType ); static const std::string vargs = "__builtin_va_list"; @@ -281,13 +283,13 @@ } - void Mangler::postvisit( ZeroType * ) { + void Mangler_old::postvisit( ZeroType * ) { mangleName << Encoding::zero; } - void Mangler::postvisit( OneType * ) { + void Mangler_old::postvisit( OneType * ) { mangleName << Encoding::one; } - void Mangler::postvisit( QualifiedType * qualType ) { + void Mangler_old::postvisit( QualifiedType * qualType ) { bool inqual = inQualifiedType; if (! inqual ) { @@ -305,5 +307,5 @@ } - void Mangler::postvisit( TypeDecl * decl ) { + void Mangler_old::postvisit( TypeDecl * decl ) { // TODO: is there any case where mangling a TypeDecl makes sense? If so, this code needs to be // fixed to ensure that two TypeDecls mangle to the same name when they are the same type and vice versa. @@ -311,5 +313,5 @@ // and the case has not yet come up in practice. Alternatively, if not then this code can be removed // aside from the assert false. - assertf(false, "Mangler should not visit typedecl: %s", toCString(decl)); + assertf(false, "Mangler_old should not visit typedecl: %s", toCString(decl)); assertf( decl->get_kind() < TypeDecl::NUMBER_OF_KINDS, "Unhandled type variable kind: %d", decl->get_kind() ); mangleName << Encoding::typeVariables[ decl->get_kind() ] << ( decl->name.length() ) << decl->name; @@ -322,5 +324,5 @@ } - void Mangler::printQualifiers( Type * type ) { + void Mangler_old::printQualifiers( Type * type ) { // skip if not including qualifiers if ( typeMode ) return; @@ -345,5 +347,5 @@ varNums[ (*i)->name ] = std::make_pair( nextVarNum, (int)(*i)->get_kind() ); for ( std::list< DeclarationWithType* >::iterator assert = (*i)->assertions.begin(); assert != (*i)->assertions.end(); ++assert ) { - PassVisitor sub_mangler( + PassVisitor sub_mangler( mangleOverridable, typeMode, mangleGenericParams, nextVarNum, varNums ); (*assert)->accept( sub_mangler ); @@ -390,4 +392,350 @@ } // namespace SymTab +namespace Mangle { + namespace { + /// Mangles names to a unique C identifier + struct Mangler_new : public ast::WithShortCircuiting, public ast::WithVisitorRef, public ast::WithGuards { + Mangler_new( Mangle::Mode mode ); + Mangler_new( const Mangler_new & ) = delete; + + void previsit( const ast::Node * ) { visit_children = false; } + + void postvisit( const ast::ObjectDecl * declaration ); + void postvisit( const ast::FunctionDecl * declaration ); + void postvisit( const ast::TypeDecl * declaration ); + + void postvisit( const ast::VoidType * voidType ); + void postvisit( const ast::BasicType * basicType ); + void postvisit( const ast::PointerType * pointerType ); + void postvisit( const ast::ArrayType * arrayType ); + void postvisit( const ast::ReferenceType * refType ); + void postvisit( const ast::FunctionType * functionType ); + void postvisit( const ast::StructInstType * aggregateUseType ); + void postvisit( const ast::UnionInstType * aggregateUseType ); + void postvisit( const ast::EnumInstType * aggregateUseType ); + void postvisit( const ast::TypeInstType * aggregateUseType ); + void postvisit( const ast::TraitInstType * inst ); + void postvisit( const ast::TupleType * tupleType ); + void postvisit( const ast::VarArgsType * varArgsType ); + void postvisit( const ast::ZeroType * zeroType ); + void postvisit( const ast::OneType * oneType ); + void postvisit( const ast::QualifiedType * qualType ); + + std::string get_mangleName() { return mangleName.str(); } + private: + std::ostringstream mangleName; ///< Mangled name being constructed + typedef std::map< std::string, std::pair< int, int > > VarMapType; + VarMapType varNums; ///< Map of type variables to indices + int nextVarNum; ///< Next type variable index + bool isTopLevel; ///< Is the Mangler at the top level + bool mangleOverridable; ///< Specially mangle overridable built-in methods + bool typeMode; ///< Produce a unique mangled name for a type + bool mangleGenericParams; ///< Include generic parameters in name mangling if true + bool inFunctionType = false; ///< Include type qualifiers if false. + bool inQualifiedType = false; ///< Add start/end delimiters around qualified type + + private: + Mangler_new( bool mangleOverridable, bool typeMode, bool mangleGenericParams, + int nextVarNum, const VarMapType& varNums ); + friend class ast::Pass; + + private: + void mangleDecl( const ast::DeclWithType *declaration ); + void mangleRef( const ast::ReferenceToType *refType, std::string prefix ); + + void printQualifiers( const ast::Type *type ); + }; // Mangler_new + } // namespace + + + std::string mangle( const ast::Node * decl, Mangle::Mode mode ) { + ast::Pass mangler( mode ); + maybeAccept( decl, mangler ); + return mangler.pass.get_mangleName(); + } + + namespace { + Mangler_new::Mangler_new( Mangle::Mode mode ) + : nextVarNum( 0 ), isTopLevel( true ), + mangleOverridable ( ! mode.no_overrideable ), + typeMode ( mode.type ), + mangleGenericParams( ! mode.no_generic_params ) {} + + Mangler_new::Mangler_new( bool mangleOverridable, bool typeMode, bool mangleGenericParams, + int nextVarNum, const VarMapType& varNums ) + : varNums( varNums ), nextVarNum( nextVarNum ), isTopLevel( false ), + mangleOverridable( mangleOverridable ), typeMode( typeMode ), + mangleGenericParams( mangleGenericParams ) {} + + void Mangler_new::mangleDecl( const ast::DeclWithType * decl ) { + bool wasTopLevel = isTopLevel; + if ( isTopLevel ) { + varNums.clear(); + nextVarNum = 0; + isTopLevel = false; + } // if + mangleName << Encoding::manglePrefix; + CodeGen::OperatorInfo opInfo; + if ( operatorLookup( decl->name, opInfo ) ) { + mangleName << opInfo.outputName.size() << opInfo.outputName; + } else { + mangleName << decl->name.size() << decl->name; + } // if + maybeAccept( decl->get_type(), *visitor ); + if ( mangleOverridable && decl->linkage.is_overrideable ) { + // want to be able to override autogenerated and intrinsic routines, + // so they need a different name mangling + if ( decl->linkage == ast::Linkage::AutoGen ) { + mangleName << Encoding::autogen; + } else if ( decl->linkage == ast::Linkage::Intrinsic ) { + mangleName << Encoding::intrinsic; + } else { + // if we add another kind of overridable function, this has to change + assert( false && "unknown overrideable linkage" ); + } // if + } + isTopLevel = wasTopLevel; + } + + void Mangler_new::postvisit( const ast::ObjectDecl * decl ) { + mangleDecl( decl ); + } + + void Mangler_new::postvisit( const ast::FunctionDecl * decl ) { + mangleDecl( decl ); + } + + void Mangler_new::postvisit( const ast::VoidType * voidType ) { + printQualifiers( voidType ); + mangleName << Encoding::void_t; + } + + void Mangler_new::postvisit( const ast::BasicType * basicType ) { + printQualifiers( basicType ); + assertf( basicType->kind < ast::BasicType::NUMBER_OF_BASIC_TYPES, "Unhandled basic type: %d", basicType->kind ); + mangleName << Encoding::basicTypes[ basicType->kind ]; + } + + void Mangler_new::postvisit( const ast::PointerType * pointerType ) { + printQualifiers( pointerType ); + // mangle void (*f)() and void f() to the same name to prevent overloading on functions and function pointers + if ( ! pointerType->base.as() ) mangleName << Encoding::pointer; + maybe_accept( pointerType->base.get(), *visitor ); + } + + void Mangler_new::postvisit( const ast::ArrayType * arrayType ) { + // TODO: encode dimension + printQualifiers( arrayType ); + mangleName << Encoding::array << "0"; + maybeAccept( arrayType->base.get(), *visitor ); + } + + void Mangler_new::postvisit( const ast::ReferenceType * refType ) { + // don't print prefix (e.g. 'R') for reference types so that references and non-references do not overload. + // Further, do not print the qualifiers for a reference type (but do run printQualifers because of TypeDecls, etc.), + // by pretending every reference type is a function parameter. + GuardValue( inFunctionType ); + inFunctionType = true; + printQualifiers( refType ); + maybeAccept( refType->base.get(), *visitor ); + } + + inline std::vector< ast::ptr< ast::Type > > getTypes( const std::vector< ast::ptr< ast::DeclWithType > > & decls ) { + std::vector< ast::ptr< ast::Type > > ret; + std::transform( decls.begin(), decls.end(), std::back_inserter( ret ), + std::mem_fun( &ast::DeclWithType::get_type ) ); + return ret; + } + + void Mangler_new::postvisit( const ast::FunctionType * functionType ) { + printQualifiers( functionType ); + mangleName << Encoding::function; + // turn on inFunctionType so that printQualifiers does not print most qualifiers for function parameters, + // since qualifiers on outermost parameter type do not differentiate function types, e.g., + // void (*)(const int) and void (*)(int) are the same type, but void (*)(const int *) and void (*)(int *) are different + GuardValue( inFunctionType ); + inFunctionType = true; + std::vector< ast::ptr< ast::Type > > returnTypes = getTypes( functionType->returns ); + if (returnTypes.empty()) mangleName << Encoding::void_t; + else accept_each( returnTypes, *visitor ); + mangleName << "_"; + std::vector< ast::ptr< ast::Type > > paramTypes = getTypes( functionType->params ); + accept_each( paramTypes, *visitor ); + mangleName << "_"; + } + + void Mangler_new::mangleRef( const ast::ReferenceToType * refType, std::string prefix ) { + printQualifiers( refType ); + + mangleName << prefix << refType->name.length() << refType->name; + + if ( mangleGenericParams ) { + if ( ! refType->params.empty() ) { + mangleName << "_"; + for ( const ast::Expr * param : refType->params ) { + auto paramType = dynamic_cast< const ast::TypeExpr * >( param ); + assertf(paramType, "Aggregate parameters should be type expressions: %s", toCString(param)); + maybeAccept( paramType->type.get(), *visitor ); + } + mangleName << "_"; + } + } + } + + void Mangler_new::postvisit( const ast::StructInstType * aggregateUseType ) { + mangleRef( aggregateUseType, Encoding::struct_t ); + } + + void Mangler_new::postvisit( const ast::UnionInstType * aggregateUseType ) { + mangleRef( aggregateUseType, Encoding::union_t ); + } + + void Mangler_new::postvisit( const ast::EnumInstType * aggregateUseType ) { + mangleRef( aggregateUseType, Encoding::enum_t ); + } + + void Mangler_new::postvisit( const ast::TypeInstType * typeInst ) { + VarMapType::iterator varNum = varNums.find( typeInst->name ); + if ( varNum == varNums.end() ) { + mangleRef( typeInst, Encoding::type ); + } else { + printQualifiers( typeInst ); + // Note: Can't use name here, since type variable names do not actually disambiguate a function, e.g. + // forall(dtype T) void f(T); + // forall(dtype S) void f(S); + // are equivalent and should mangle the same way. This is accomplished by numbering the type variables when they + // are first found and prefixing with the appropriate encoding for the type class. + assertf( varNum->second.second < TypeDecl::NUMBER_OF_KINDS, "Unhandled type variable kind: %d", varNum->second.second ); + mangleName << Encoding::typeVariables[varNum->second.second] << varNum->second.first; + } // if + } + + void Mangler_new::postvisit( const ast::TraitInstType * inst ) { + printQualifiers( inst ); + mangleName << inst->name.size() << inst->name; + } + + void Mangler_new::postvisit( const ast::TupleType * tupleType ) { + printQualifiers( tupleType ); + mangleName << Encoding::tuple << tupleType->types.size(); + accept_each( tupleType->types, *visitor ); + } + + void Mangler_new::postvisit( const ast::VarArgsType * varArgsType ) { + printQualifiers( varArgsType ); + static const std::string vargs = "__builtin_va_list"; + mangleName << Encoding::type << vargs.size() << vargs; + } + + void Mangler_new::postvisit( const ast::ZeroType * ) { + mangleName << Encoding::zero; + } + + void Mangler_new::postvisit( const ast::OneType * ) { + mangleName << Encoding::one; + } + + void Mangler_new::postvisit( const ast::QualifiedType * qualType ) { + bool inqual = inQualifiedType; + if (! inqual ) { + // N marks the start of a qualified type + inQualifiedType = true; + mangleName << Encoding::qualifiedTypeStart; + } + maybeAccept( qualType->parent.get(), *visitor ); + maybeAccept( qualType->child.get(), *visitor ); + if ( ! inqual ) { + // E marks the end of a qualified type + inQualifiedType = false; + mangleName << Encoding::qualifiedTypeEnd; + } + } + + void Mangler_new::postvisit( const ast::TypeDecl * decl ) { + // TODO: is there any case where mangling a TypeDecl makes sense? If so, this code needs to be + // fixed to ensure that two TypeDecls mangle to the same name when they are the same type and vice versa. + // Note: The current scheme may already work correctly for this case, I have not thought about this deeply + // and the case has not yet come up in practice. Alternatively, if not then this code can be removed + // aside from the assert false. + assertf(false, "Mangler_new should not visit typedecl: %s", toCString(decl)); + assertf( decl->kind < ast::TypeVar::Kind::NUMBER_OF_KINDS, "Unhandled type variable kind: %d", decl->kind ); + mangleName << Encoding::typeVariables[ decl->kind ] << ( decl->name.length() ) << decl->name; + } + + __attribute__((unused)) void printVarMap( const std::map< std::string, std::pair< int, int > > &varMap, std::ostream &os ) { + for ( std::map< std::string, std::pair< int, int > >::const_iterator i = varMap.begin(); i != varMap.end(); ++i ) { + os << i->first << "(" << i->second.first << "/" << i->second.second << ")" << std::endl; + } // for + } + + void Mangler_new::printQualifiers( const ast::Type * type ) { + // skip if not including qualifiers + if ( typeMode ) return; + if ( auto ptype = dynamic_cast< const ast::ParameterizedType * >(type) ) { + if ( ! ptype->forall.empty() ) { + std::list< std::string > assertionNames; + int dcount = 0, fcount = 0, vcount = 0, acount = 0; + mangleName << Encoding::forall; + for ( const ast::TypeDecl * decl : ptype->forall ) { + switch ( decl->kind ) { + case ast::TypeVar::Kind::Dtype: + dcount++; + break; + case ast::TypeVar::Kind::Ftype: + fcount++; + break; + case ast::TypeVar::Kind::Ttype: + vcount++; + break; + default: + assert( false ); + } // switch + varNums[ decl->name ] = std::make_pair( nextVarNum, (int)decl->kind ); + for ( const ast::DeclWithType * assert : decl->assertions ) { + ast::Pass sub_mangler( + mangleOverridable, typeMode, mangleGenericParams, nextVarNum, varNums ); + assert->accept( sub_mangler ); + assertionNames.push_back( sub_mangler.pass.get_mangleName() ); + acount++; + } // for + } // for + mangleName << dcount << "_" << fcount << "_" << vcount << "_" << acount << "_"; + std::copy( assertionNames.begin(), assertionNames.end(), std::ostream_iterator< std::string >( mangleName, "" ) ); + mangleName << "_"; + } // if + } // if + if ( ! inFunctionType ) { + // these qualifiers do not distinguish the outermost type of a function parameter + if ( type->is_const() ) { + mangleName << Encoding::qualifiers.at(Type::Const); + } // if + if ( type->is_volatile() ) { + mangleName << Encoding::qualifiers.at(Type::Volatile); + } // if + // Removed due to restrict not affecting function compatibility in GCC + // if ( type->get_isRestrict() ) { + // mangleName << "E"; + // } // if + if ( type->is_atomic() ) { + mangleName << Encoding::qualifiers.at(Type::Atomic); + } // if + } + if ( type->is_mutex() ) { + mangleName << Encoding::qualifiers.at(Type::Mutex); + } // if + if ( type->is_lvalue() ) { + // mangle based on whether the type is lvalue, so that the resolver can differentiate lvalues and rvalues + mangleName << Encoding::qualifiers.at(Type::Lvalue); + } + + if ( inFunctionType ) { + // turn off inFunctionType so that types can be differentiated for nested qualifiers + GuardValue( inFunctionType ); + inFunctionType = false; + } + } + } // namespace +} // namespace Mangle + // Local Variables: // // tab-width: 4 // Index: src/SymTab/Mangler.h =================================================================== --- src/SymTab/Mangler.h (revision 7564e10d60badc52604ddc7491f9465ec58795f3) +++ src/SymTab/Mangler.h (revision 67130fe7c6ae00bc7c6da280f8b700e5bc850a3c) @@ -21,4 +21,6 @@ #include // for pair +#include "AST/Bitfield.hpp" +#include "AST/Fwd.hpp" #include "SynTree/SynTree.h" // for Types #include "SynTree/Visitor.h" // for Visitor, maybeAccept @@ -75,4 +77,36 @@ } // SymTab +namespace Mangle { + /// Bitflags for mangle modes + enum { + NoOverrideable = 1 << 0, + Type = 1 << 1, + NoGenericParams = 1 << 2 + }; + + /// Bitflag type for mangler modes + struct mangle_flags { + union { + unsigned int val; + struct { + bool no_overrideable : 1; + bool type : 1; + bool no_generic_params : 1; + }; + }; + + constexpr mangle_flags( unsigned int val ) : val(val) {} + }; + + using Mode = bitfield; + + /// Mangle declaration name + std::string mangle( const ast::Node * decl, Mode mode = {} ); + + namespace Encoding { + using namespace SymTab::Mangler::Encoding; + }; +} + extern "C" { char * cforall_demangle(const char *, int); Index: src/SynTree/Expression.cc =================================================================== --- src/SynTree/Expression.cc (revision 7564e10d60badc52604ddc7491f9465ec58795f3) +++ src/SynTree/Expression.cc (revision 67130fe7c6ae00bc7c6da280f8b700e5bc850a3c) @@ -610,5 +610,5 @@ computeResult(); } -StmtExpr::StmtExpr( const StmtExpr & other ) : Expression( other ), statements( other.statements->clone() ) { +StmtExpr::StmtExpr( const StmtExpr & other ) : Expression( other ), statements( other.statements->clone() ), resultExpr( other.resultExpr ) { cloneAll( other.returnDecls, returnDecls ); cloneAll( other.dtors, dtors ); Index: src/SynTree/Expression.h =================================================================== --- src/SynTree/Expression.h (revision 7564e10d60badc52604ddc7491f9465ec58795f3) +++ src/SynTree/Expression.h (revision 67130fe7c6ae00bc7c6da280f8b700e5bc850a3c) @@ -62,5 +62,5 @@ InferredParams inferParams; ///< Post-resolution inferred parameter slots std::vector resnSlots; ///< Pre-resolution inferred parameter slots - + // xxx - should turn inferParams+resnSlots into a union to save some memory @@ -744,4 +744,7 @@ std::list< Expression * > dtors; // destructor(s) for return variable(s) + // readonly + ExprStmt * resultExpr = nullptr; + StmtExpr( CompoundStmt * statements ); StmtExpr( const StmtExpr & other ); Index: src/Validate/FindSpecialDecls.cc =================================================================== --- src/Validate/FindSpecialDecls.cc (revision 7564e10d60badc52604ddc7491f9465ec58795f3) +++ src/Validate/FindSpecialDecls.cc (revision 67130fe7c6ae00bc7c6da280f8b700e5bc850a3c) @@ -26,7 +26,7 @@ namespace Validate { Type * SizeType = nullptr; - FunctionDecl * dereferenceOperator = nullptr; - StructDecl * dtorStruct = nullptr; - FunctionDecl * dtorStructDestroy = nullptr; + FunctionDecl * dereferenceOperator = nullptr; + StructDecl * dtorStruct = nullptr; + FunctionDecl * dtorStructDestroy = nullptr; namespace { Index: src/include/cassert =================================================================== --- src/include/cassert (revision 7564e10d60badc52604ddc7491f9465ec58795f3) +++ src/include/cassert (revision 67130fe7c6ae00bc7c6da280f8b700e5bc850a3c) @@ -10,6 +10,6 @@ // Created On : Thu Aug 18 13:19:26 2016 // Last Modified By : Andrew Beach -// Last Modified On : Thu May 23 15:30:00 2017 -// Update Count : 17 +// Last Modified On : Mon Jun 3 13:11:00 2017 +// Update Count : 18 // @@ -43,15 +43,15 @@ #endif -enum StrictAllowNull {NonNull, AllowNull}; - -template +template static inline T strict_dynamic_cast( const U & src ) { - if (nullable == AllowNull && src == nullptr) { - return nullptr; - } assert(src); T ret = dynamic_cast(src); assertf(ret, "%s", toString(src).c_str()); return ret; +} + +template +static inline T strict_dynamic_cast( const U & src ) { + return src ? strict_dynamic_cast( src ) : nullptr; }