Changeset e5c3811 for src

Timestamp:

Nov 25, 2020, 3:12:17 AM (4 years ago)

Author:

Fangren Yu <f37yu@…>

Branches:

ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr, pthread-emulation, qualifiedEnum

Children:

4702a2c

Parents:

7192145

Message:

create dedicated symbol tables for big 3 operators
note: arbitrary this param type is not supported; it is currently allowed although never used

Location:

src

Files:

• AST/Decl.hpp (modified) (1 diff)
• AST/SymbolTable.cpp (modified) (9 diffs)
• AST/SymbolTable.hpp (modified) (4 diffs)
• AST/Type.cpp (modified) (1 diff)
• AST/Type.hpp (modified) (4 diffs)
• ResolvExpr/CandidateFinder.cpp (modified) (5 diffs)
• ResolvExpr/CandidateFinder.hpp (modified) (1 diff)
• ResolvExpr/SatisfyAssertions.cpp (modified) (1 diff)

src/AST/Decl.hpp

@@ -75 +75 @@
         int scopeLevel = 0;
 
+        /*
+        ForallDecl foralls {
+                list<TypeDecl> params
+                list<ObjectDecl> assns
+        }
+        */
+
         std::vector<ptr<Attribute>> attributes;
         Function::Specs funcSpec;

src/AST/SymbolTable.cpp

@@ -95 +95 @@
 }
 
+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::IdData> SymbolTable::lookupId( const std::string &id ) const {
+        static Stats::Counters::CounterGroup * name_lookup_stats = Stats::Counters::build<Stats::Counters::CounterGroup>("Name Lookup Stats");
+        static std::map<std::string, Stats::Counters::SimpleCounter *> lookups_by_name;
+        static std::map<std::string, Stats::Counters::SimpleCounter *> candidates_by_name;
+
+        SpecialFunctionKind kind = getSpecialFunctionKind(id);
+        if (kind != NUMBER_OF_KINDS) return specialLookupId(kind);
+
         ++*stats().lookup_calls;
         if ( ! idTable ) return {};
@@ -107 +121 @@
                 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::IdData> SymbolTable::specialLookupId( SymbolTable::SpecialFunctionKind kind, const std::string & otypeKey ) const {
+        static Stats::Counters::CounterGroup * special_stats = Stats::Counters::build<Stats::Counters::CounterGroup>("Special Lookups");
+        static Stats::Counters::SimpleCounter * stat_counts[3] = {
+                Stats::Counters::build<Stats::Counters::SimpleCounter>("constructor - count", special_stats),
+                Stats::Counters::build<Stats::Counters::SimpleCounter>("destructor - count", special_stats),
+                Stats::Counters::build<Stats::Counters::SimpleCounter>("assignment - count", special_stats)
+        };
+
+        static Stats::Counters::SimpleCounter * stat_candidates[3] = {
+                Stats::Counters::build<Stats::Counters::SimpleCounter>("constructor - candidates", special_stats),
+                Stats::Counters::build<Stats::Counters::SimpleCounter>("destructor - candidates", special_stats),
+                Stats::Counters::build<Stats::Counters::SimpleCounter>("assignment - candidates", special_stats)
+        };
+
+        static Stats::Counters::SimpleCounter * num_lookup_with_key 
+                = Stats::Counters::build<Stats::Counters::SimpleCounter>("keyed lookups", special_stats);
+        static Stats::Counters::SimpleCounter * num_lookup_without_key 
+                = Stats::Counters::build<Stats::Counters::SimpleCounter>("unkeyed lookups", special_stats);
+
+        assert (kind != NUMBER_OF_KINDS);
+        ++*stats().lookup_calls;
+        if ( ! specialFunctionTable[kind] ) return {};
+
+        std::vector<IdData> 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 +443 @@
 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<const PointerType *>(base)) return Mangle::Encoding::pointer;
+                        return Mangle::mangle( base, Mangle::Type | Mangle::NoGenericParams );
+                }
+                else
+                        return Mangle::mangle( base );  
         }
 
@@ -380 +462 @@
                         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 +487 @@
         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 +659 @@
                 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<const FunctionDecl *>(decl)) {
+                        key = getOtypeKey(func->type);
+                }
+                else if (auto obj = dynamic_cast<const ObjectDecl *>(decl)) {
+                        key = getOtypeKey(obj->type.strict_as<PointerType>()->base.strict_as<FunctionType>());
+                }
+                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 +711 @@
         // 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 +732 @@
                                                 lazyInitScope();
                                                 *stats().map_mutations += 2;
-                                                idTable = idTable->set(
-                                                        name,
+                                                table = table->set(
+                                                        lookupKey,
                                                         mangleTable->set(
                                                                 mangleName,
@@ -644 +748 @@
         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) ) );
 }
 

src/AST/SymbolTable.hpp

@@ -33 +33 @@
 class SymbolTable final : public std::enable_shared_from_this<ast::SymbolTable> {
 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 +81 @@
         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<const SymbolTable>;
@@ -95 +103 @@
         /// Gets all declarations with the given ID
         std::vector<IdData> lookupId( const std::string &id ) const;
+        /// Gets special functions associated with a type; if no key is given, returns everything
+        std::vector<IdData> 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 +196 @@
                 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 );

src/AST/Type.cpp

@@ -216 +216 @@
 }
 
+bool isUnboundType(const Type * type) {
+        if (auto typeInst = dynamic_cast<const TypeInstType *>(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;
+}
+
 }
 

src/AST/Type.hpp

@@ -274 +274 @@
 public:
         using ForallList = std::vector<ptr<TypeDecl>>;
-
+        // using ForallList = std::vector<readonly<TypeDecl>>;
+
+        // using ForallList = std::vector<ptr<TypeInstType>>;
         ForallList forall;
+        // using AssertionList = std::vector<ptr<VariableExpr>>;
+        // AssertionList assertions;
 
         ParameterizedType( ForallList&& fs = {}, CV::Qualifiers q = {},
@@ -423 +427 @@
 public:
         readonly<TypeDecl> base;
+        // int context;
         TypeDecl::Kind kind;
 
@@ -535 +540 @@
 };
 
+bool isUnboundType(const Type * type);
+
 }
+
 
 #undef MUTATE_FRIEND
@@ -541 +549 @@
 // Local Variables: //
 // tab-width: 4 //
+
 // mode: c++ //
 // compile-command: "make install" //

src/ResolvExpr/CandidateFinder.cpp

@@ -43 +43 @@
 #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 +867 @@
 
                 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 +873 @@
                         // if not tuple assignment, handled as normal function call
                         Tuples::handleTupleAssignment( selfFinder, untypedExpr, argCandidates );
+
+                        CandidateFinder funcFinder{ symtab, tenv };
+                        if (auto nameExpr = untypedExpr->func.as<ast::NameExpr>()) {
+                                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<ast::Type> argType = firstArgCand->expr->result;
+                                                firstArgCand->env.apply(argType);
+                                                // strip references
+                                                // xxx - is this correct?
+                                                while (argType.as<ast::ReferenceType>()) argType = argType.as<ast::ReferenceType>()->base;
+
+                                                // convert 1-tuple to plain type
+                                                if (auto tuple = argType.as<ast::TupleType>()) {
+                                                        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<ast::PointerType>()) 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 +1222 @@
 
                 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 +1606 @@
                                         }
                                 }
+
                         }
 

src/ResolvExpr/CandidateFinder.hpp

@@ -31 +31 @@
         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(

src/ResolvExpr/SatisfyAssertions.cpp

@@ -167 +167 @@
                 // find candidates that unify with the desired type
                 AssnCandidateList matches;
-                for ( const ast::SymbolTable::IdData & cdata : sat.symtab.lookupId( assn.first->name ) ) {
+
+                std::vector<ast::SymbolTable::IdData> 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<ast::Type> thisArgType = strict_dynamic_cast<const ast::PointerType *>(assn.first->get_type())->base
+                                .strict_as<ast::FunctionType>()->params[0]
+                                .strict_as<ast::ReferenceType>()->base;
+                        sat.cand->env.apply(thisArgType);
+
+                        std::string otypeKey = "";
+                        if (thisArgType.as<ast::PointerType>()) 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;