Index: src/AST/Decl.hpp =================================================================== --- src/AST/Decl.hpp (revision a0ba5e6f4d5ec1474c3c35657b2a854519889206) +++ src/AST/Decl.hpp (revision e5c38112cf0116f0fcdd3e08dd4133429b2ecfbe) @@ -75,4 +75,11 @@ int scopeLevel = 0; + /* + ForallDecl foralls { + list params + list assns + } + */ + std::vector> attributes; Function::Specs funcSpec; Index: src/AST/SymbolTable.cpp =================================================================== --- src/AST/SymbolTable.cpp (revision a0ba5e6f4d5ec1474c3c35657b2a854519889206) +++ src/AST/SymbolTable.cpp (revision e5c38112cf0116f0fcdd3e08dd4133429b2ecfbe) @@ -95,5 +95,19 @@ } +SymbolTable::SpecialFunctionKind SymbolTable::getSpecialFunctionKind(const std::string & name) { + if (name == "?{}") return CTOR; + if (name == "^?{}") return DTOR; + if (name == "?=?") return ASSIGN; + return NUMBER_OF_KINDS; +} + std::vector SymbolTable::lookupId( const std::string &id ) const { + static Stats::Counters::CounterGroup * name_lookup_stats = Stats::Counters::build("Name Lookup Stats"); + static std::map lookups_by_name; + static std::map candidates_by_name; + + SpecialFunctionKind kind = getSpecialFunctionKind(id); + if (kind != NUMBER_OF_KINDS) return specialLookupId(kind); + ++*stats().lookup_calls; if ( ! idTable ) return {}; @@ -107,4 +121,67 @@ out.push_back( decl.second ); } + + if (Stats::Counters::enabled) { + if (! lookups_by_name.count(id)) { + // leaks some strings, but it is because Counters do not hold them + auto lookupCounterName = new std::string(id + "%count"); + auto candidatesCounterName = new std::string(id + "%candidate"); + lookups_by_name.emplace(id, new Stats::Counters::SimpleCounter(lookupCounterName->c_str(), name_lookup_stats)); + candidates_by_name.emplace(id, new Stats::Counters::SimpleCounter(candidatesCounterName->c_str(), name_lookup_stats)); + } + (*lookups_by_name[id]) ++; + *candidates_by_name[id] += out.size(); + } + + return out; +} + +std::vector SymbolTable::specialLookupId( SymbolTable::SpecialFunctionKind kind, const std::string & otypeKey ) const { + static Stats::Counters::CounterGroup * special_stats = Stats::Counters::build("Special Lookups"); + static Stats::Counters::SimpleCounter * stat_counts[3] = { + Stats::Counters::build("constructor - count", special_stats), + Stats::Counters::build("destructor - count", special_stats), + Stats::Counters::build("assignment - count", special_stats) + }; + + static Stats::Counters::SimpleCounter * stat_candidates[3] = { + Stats::Counters::build("constructor - candidates", special_stats), + Stats::Counters::build("destructor - candidates", special_stats), + Stats::Counters::build("assignment - candidates", special_stats) + }; + + static Stats::Counters::SimpleCounter * num_lookup_with_key + = Stats::Counters::build("keyed lookups", special_stats); + static Stats::Counters::SimpleCounter * num_lookup_without_key + = Stats::Counters::build("unkeyed lookups", special_stats); + + assert (kind != NUMBER_OF_KINDS); + ++*stats().lookup_calls; + if ( ! specialFunctionTable[kind] ) return {}; + + std::vector out; + + if (otypeKey.empty()) { // returns everything + ++*num_lookup_without_key; + for (auto & table : *specialFunctionTable[kind]) { + for (auto & decl : *table.second) { + out.push_back(decl.second); + } + } + } + else { + ++*num_lookup_with_key; + ++*stats().map_lookups; + auto decls = specialFunctionTable[kind]->find(otypeKey); + if (decls == specialFunctionTable[kind]->end()) return {}; + + for (auto decl : *(decls->second)) { + out.push_back(decl.second); + } + } + + ++*stat_counts[kind]; + *stat_candidates[kind] += out.size(); + return out; } @@ -366,11 +443,16 @@ 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; + std::string getOtypeKey( const FunctionType * ftype, bool stripParams = true ) { + const auto & params = ftype->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() ); assert( base ); - return Mangle::mangle( base ); + if (stripParams) { + if (dynamic_cast(base)) return Mangle::Encoding::pointer; + return Mangle::mangle( base, Mangle::Type | Mangle::NoGenericParams ); + } + else + return Mangle::mangle( base ); } @@ -380,5 +462,5 @@ const DeclWithType * decl, const std::string & otypeKey ) { auto func = dynamic_cast< const FunctionDecl * >( decl ); - if ( ! func || otypeKey != getOtypeKey( func ) ) return nullptr; + if ( ! func || otypeKey != getOtypeKey( func->type, false ) ) return nullptr; return func; } @@ -405,5 +487,5 @@ bool dataIsUserDefinedFunc = ! function->linkage.is_overrideable; bool dataIsCopyFunc = InitTweak::isCopyFunction( function ); - std::string dataOtypeKey = getOtypeKey( function ); + std::string dataOtypeKey = getOtypeKey( function->type, false ); // requires exact match to override autogen if ( dataIsUserDefinedFunc && dataIsCopyFunc ) { @@ -577,4 +659,26 @@ const DeclWithType * decl, SymbolTable::OnConflict handleConflicts, const Expr * baseExpr, const Decl * deleter ) { + SpecialFunctionKind kind = getSpecialFunctionKind(decl->name); + if (kind == NUMBER_OF_KINDS) { // not a special decl + addId(decl, decl->name, idTable, handleConflicts, baseExpr, deleter); + } + else { + std::string key; + if (auto func = dynamic_cast(decl)) { + key = getOtypeKey(func->type); + } + else if (auto obj = dynamic_cast(decl)) { + key = getOtypeKey(obj->type.strict_as()->base.strict_as()); + } + else { + assertf(false, "special decl with non-function type"); + } + addId(decl, key, specialFunctionTable[kind], handleConflicts, baseExpr, deleter); + } +} + +void SymbolTable::addId( + const DeclWithType * decl, const std::string & lookupKey, IdTable::Ptr & table, SymbolTable::OnConflict handleConflicts, const Expr * baseExpr, + const Decl * deleter ) { ++*stats().add_calls; const std::string &name = decl->name; @@ -607,11 +711,11 @@ // ensure tables exist and add identifier MangleTable::Ptr mangleTable; - if ( ! idTable ) { - idTable = IdTable::new_ptr(); + if ( ! table ) { + table = IdTable::new_ptr(); mangleTable = MangleTable::new_ptr(); } else { ++*stats().map_lookups; - auto decls = idTable->find( name ); - if ( decls == idTable->end() ) { + auto decls = table->find( lookupKey ); + if ( decls == table->end() ) { mangleTable = MangleTable::new_ptr(); } else { @@ -628,6 +732,6 @@ lazyInitScope(); *stats().map_mutations += 2; - idTable = idTable->set( - name, + table = table->set( + lookupKey, mangleTable->set( mangleName, @@ -644,7 +748,9 @@ IdData data{ decl, baseExpr, deleter, scope }; // Ensure that auto-generated ctor/dtor/assignment are deleted if necessary - if ( ! removeSpecialOverrides( data, mangleTable ) ) return; + if (table != idTable) { // adding to special table + if ( ! removeSpecialOverrides( data, mangleTable ) ) return; + } *stats().map_mutations += 2; - idTable = idTable->set( name, mangleTable->set( mangleName, std::move(data) ) ); + table = table->set( lookupKey, mangleTable->set( mangleName, std::move(data) ) ); } Index: src/AST/SymbolTable.hpp =================================================================== --- src/AST/SymbolTable.hpp (revision a0ba5e6f4d5ec1474c3c35657b2a854519889206) +++ src/AST/SymbolTable.hpp (revision e5c38112cf0116f0fcdd3e08dd4133429b2ecfbe) @@ -33,4 +33,8 @@ class SymbolTable final : public std::enable_shared_from_this { public: + /// special functions stored in dedicated tables, with different lookup keys + enum SpecialFunctionKind {CTOR, DTOR, ASSIGN, NUMBER_OF_KINDS}; + static SpecialFunctionKind getSpecialFunctionKind(const std::string & name); + /// Stored information about a declaration struct IdData { @@ -77,4 +81,8 @@ UnionTable::Ptr unionTable; ///< union namespace TraitTable::Ptr traitTable; ///< trait namespace + IdTable::Ptr specialFunctionTable[NUMBER_OF_KINDS]; + + // using SpecialFuncTable = PersistentMap< std::string, IdTable::Ptr >; // fname (ctor/dtor/assign) - otypekey + // SpecialFuncTable::Ptr specialFuncTable; using Ptr = std::shared_ptr; @@ -95,4 +103,6 @@ /// Gets all declarations with the given ID std::vector lookupId( const std::string &id ) const; + /// Gets special functions associated with a type; if no key is given, returns everything + std::vector specialLookupId( SpecialFunctionKind kind, const std::string & otypeKey = "" ) const; /// Gets the top-most type declaration with the given ID const NamedTypeDecl * lookupType( const std::string &id ) const; @@ -186,4 +196,9 @@ const Decl * deleter = nullptr ); + /// common code for addId when special decls are placed into separate tables + void addId( + const DeclWithType * decl, const std::string & lookupKey, IdTable::Ptr & idTable, OnConflict handleConflicts, + const Expr * baseExpr = nullptr, const Decl * deleter = nullptr); + /// adds all of the members of the Aggregate (addWith helper) void addMembers( const AggregateDecl * aggr, const Expr * expr, OnConflict handleConflicts ); Index: src/AST/Type.cpp =================================================================== --- src/AST/Type.cpp (revision a0ba5e6f4d5ec1474c3c35657b2a854519889206) +++ src/AST/Type.cpp (revision e5c38112cf0116f0fcdd3e08dd4133429b2ecfbe) @@ -216,4 +216,17 @@ } +bool isUnboundType(const Type * type) { + if (auto typeInst = dynamic_cast(type)) { + // xxx - look for a type name produced by renameTyVars. + + // TODO: once TypeInstType representation is updated, it should properly check + // if the context id is filled. this is a temporary hack for now + if (std::count(typeInst->name.begin(), typeInst->name.end(), '_') >= 3) { + return true; + } + } + return false; +} + } Index: src/AST/Type.hpp =================================================================== --- src/AST/Type.hpp (revision a0ba5e6f4d5ec1474c3c35657b2a854519889206) +++ src/AST/Type.hpp (revision e5c38112cf0116f0fcdd3e08dd4133429b2ecfbe) @@ -274,6 +274,10 @@ public: using ForallList = std::vector>; - + // using ForallList = std::vector>; + + // using ForallList = std::vector>; ForallList forall; + // using AssertionList = std::vector>; + // AssertionList assertions; ParameterizedType( ForallList&& fs = {}, CV::Qualifiers q = {}, @@ -423,4 +427,5 @@ public: readonly base; + // int context; TypeDecl::Kind kind; @@ -535,5 +540,8 @@ }; +bool isUnboundType(const Type * type); + } + #undef MUTATE_FRIEND @@ -541,4 +549,5 @@ // Local Variables: // // tab-width: 4 // + // mode: c++ // // compile-command: "make install" // Index: src/ResolvExpr/CandidateFinder.cpp =================================================================== --- src/ResolvExpr/CandidateFinder.cpp (revision a0ba5e6f4d5ec1474c3c35657b2a854519889206) +++ src/ResolvExpr/CandidateFinder.cpp (revision e5c38112cf0116f0fcdd3e08dd4133429b2ecfbe) @@ -43,4 +43,7 @@ #include "SymTab/Validate.h" // for validateType #include "Tuples/Tuples.h" // for handleTupleAssignment +#include "InitTweak/InitTweak.h" // for getPointerBase + +#include "Common/Stats/Counter.h" #define PRINT( text ) if ( resolvep ) { text } @@ -864,11 +867,4 @@ void postvisit( const ast::UntypedExpr * untypedExpr ) { - CandidateFinder funcFinder{ symtab, tenv }; - funcFinder.find( untypedExpr->func, ResolvMode::withAdjustment() ); - // short-circuit if no candidates - if ( funcFinder.candidates.empty() ) return; - - reason.code = NoMatch; - std::vector< CandidateFinder > argCandidates = selfFinder.findSubExprs( untypedExpr->args ); @@ -877,4 +873,43 @@ // if not tuple assignment, handled as normal function call Tuples::handleTupleAssignment( selfFinder, untypedExpr, argCandidates ); + + CandidateFinder funcFinder{ symtab, tenv }; + if (auto nameExpr = untypedExpr->func.as()) { + auto kind = ast::SymbolTable::getSpecialFunctionKind(nameExpr->name); + if (kind != ast::SymbolTable::SpecialFunctionKind::NUMBER_OF_KINDS) { + assertf(!argCandidates.empty(), "special function call without argument"); + for (auto & firstArgCand: argCandidates[0]) { + ast::ptr argType = firstArgCand->expr->result; + firstArgCand->env.apply(argType); + // strip references + // xxx - is this correct? + while (argType.as()) argType = argType.as()->base; + + // convert 1-tuple to plain type + if (auto tuple = argType.as()) { + if (tuple->size() == 1) { + argType = tuple->types[0]; + } + } + + // if argType is an unbound type parameter, all special functions need to be searched. + if (isUnboundType(argType)) { + funcFinder.otypeKeys.clear(); + break; + } + + if (argType.as()) funcFinder.otypeKeys.insert(Mangle::Encoding::pointer); + else funcFinder.otypeKeys.insert(Mangle::mangle(argType, Mangle::NoGenericParams | Mangle::Type)); + } + } + } + // if candidates are already produced, do not fail + // xxx - is it possible that handleTupleAssignment and main finder both produce candidates? + // this means there exists ctor/assign functions with a tuple as first parameter. + funcFinder.find( untypedExpr->func, selfFinder.candidates.empty() ? ResolvMode::withAdjustment() : ResolvMode::withoutFailFast() ); + // short-circuit if no candidates + // if ( funcFinder.candidates.empty() ) return; + + reason.code = NoMatch; // find function operators @@ -1187,6 +1222,19 @@ void postvisit( const ast::NameExpr * nameExpr ) { - std::vector< ast::SymbolTable::IdData > declList = symtab.lookupId( nameExpr->name ); + std::vector< ast::SymbolTable::IdData > declList; + if (!selfFinder.otypeKeys.empty()) { + auto kind = ast::SymbolTable::getSpecialFunctionKind(nameExpr->name); + assertf(kind != ast::SymbolTable::SpecialFunctionKind::NUMBER_OF_KINDS, "special lookup with non-special target: %s", nameExpr->name.c_str()); + + for (auto & otypeKey: selfFinder.otypeKeys) { + auto result = symtab.specialLookupId(kind, otypeKey); + declList.insert(declList.end(), std::make_move_iterator(result.begin()), std::make_move_iterator(result.end())); + } + } + else { + declList = symtab.lookupId( nameExpr->name ); + } PRINT( std::cerr << "nameExpr is " << nameExpr->name << std::endl; ) + if( declList.empty() ) return; @@ -1558,4 +1606,5 @@ } } + } Index: src/ResolvExpr/CandidateFinder.hpp =================================================================== --- src/ResolvExpr/CandidateFinder.hpp (revision a0ba5e6f4d5ec1474c3c35657b2a854519889206) +++ src/ResolvExpr/CandidateFinder.hpp (revision e5c38112cf0116f0fcdd3e08dd4133429b2ecfbe) @@ -31,4 +31,5 @@ const ast::TypeEnvironment & env; ///< Substitutions performed in this resolution ast::ptr< ast::Type > targetType; ///< Target type for resolution + std::set< std::string > otypeKeys; /// different type may map to same key CandidateFinder( Index: src/ResolvExpr/SatisfyAssertions.cpp =================================================================== --- src/ResolvExpr/SatisfyAssertions.cpp (revision a0ba5e6f4d5ec1474c3c35657b2a854519889206) +++ src/ResolvExpr/SatisfyAssertions.cpp (revision e5c38112cf0116f0fcdd3e08dd4133429b2ecfbe) @@ -167,5 +167,24 @@ // find candidates that unify with the desired type AssnCandidateList matches; - for ( const ast::SymbolTable::IdData & cdata : sat.symtab.lookupId( assn.first->name ) ) { + + std::vector candidates; + auto kind = ast::SymbolTable::getSpecialFunctionKind(assn.first->name); + if (kind != ast::SymbolTable::SpecialFunctionKind::NUMBER_OF_KINDS) { + // prefilter special decls by argument type, if already known + ast::ptr thisArgType = strict_dynamic_cast(assn.first->get_type())->base + .strict_as()->params[0] + .strict_as()->base; + sat.cand->env.apply(thisArgType); + + std::string otypeKey = ""; + if (thisArgType.as()) otypeKey = Mangle::Encoding::pointer; + else if (!isUnboundType(thisArgType)) otypeKey = Mangle::mangle(thisArgType, Mangle::Type | Mangle::NoGenericParams); + + candidates = sat.symtab.specialLookupId(kind, otypeKey); + } + else { + candidates = sat.symtab.lookupId(assn.first->name); + } + for ( const ast::SymbolTable::IdData & cdata : candidates ) { const ast::DeclWithType * candidate = cdata.id;