Changeset b60f9d9

Timestamp:

Jun 13, 2018, 4:14:31 PM (6 years ago)

Author:

Aaron Moss <a3moss@…>

Branches:

new-env

Children:

97397a26

Parents:

6d53e779

Message:

Start on breadth-first assertion resolution

Location:

src/ResolvExpr

Files:

• AlternativeFinder.cc (modified) (9 diffs)
• Resolver.cc (modified) (2 diffs)

src/ResolvExpr/AlternativeFinder.cc

@@ -9 +9 @@
 // Author           : Richard C. Bilson
 // Created On       : Sat May 16 23:52:08 2015
-// Last Modified By : Peter A. Buhr
-// Last Modified On : Sat Feb 17 11:19:39 2018
-// Update Count     : 33
+// Last Modified By : Aaron B. Moss
+// Last Modified On : Mon Jun 11 16:40:00 2018
+// Update Count     : 34
 //
 
@@ -19 +19 @@
 #include <iostream>                // for operator<<, cerr, ostream, endl
 #include <iterator>                // for back_insert_iterator, back_inserter
+#include <limits>                  // for numeric_limits<int>::max()
 #include <list>                    // for _List_iterator, list, _List_const_...
 #include <map>                     // for _Rb_tree_iterator, map, _Rb_tree_c...
 #include <memory>                  // for allocator_traits<>::value_type
+#include <tuple>                   // for tuple
 #include <utility>                 // for pair
 #include <vector>                  // for vector
@@ -444 +446 @@
                 }
 
+                #if 0 // cost of assertions accounted for in function creation
                 for ( InferredParams::const_iterator assert = appExpr->get_inferParams().begin(); assert != appExpr->get_inferParams().end(); ++assert ) {
                         convCost += computeConversionCost( assert->second.actualType, assert->second.formalType, indexer, alt.env );
                 }
+                #endif
 
                 return convCost;
@@ -572 +576 @@
         }
 
+        namespace {
+                /// Information required to defer resolution of an expression
+                struct AssertionPack {
+                        SymTab::Indexer::IdData cdata;  ///< Satisfying declaration
+                        Type* adjType;                  ///< Satisfying type
+                        TypeEnvironment env;            ///< Post-unification environment
+                        AssertionSet have;              ///< Post-unification have-set
+                        AssertionSet need;              ///< Post-unification need-set
+                        OpenVarSet openVars;            ///< Post-unification open-var set
+
+                        AssertionPack( const SymTab::Indexer::IdData& cdata, Type* adjType, 
+                                        TypeEnvironment&& env, AssertionSet&& have, AssertionSet&& need, 
+                                        OpenVarSet&& openVars ) 
+                                : cdata(cdata), adjType(adjType), env(std::move(env)), have(std::move(have)), 
+                                  need(std::move(need)), openVars(std::move(openVars)) {}
+                };
+
+                /// List of deferred assertion resolutions for the same type
+                using DeferList = std::vector<AssertionPack>;
+
+                /// Intermediate state for assertion resolution
+                struct AssertionResnState {
+                        using DeferItem = std::tuple<DeclarationWithType*, AssertionSetValue, DeferList>;
+
+                        const Alternative& alt;           ///< Alternative being built from
+                        AssertionSet newNeed;             ///< New assertions found from current assertions
+                        OpenVarSet openVars;              ///< Open variables in current context
+                        std::vector<DeferItem> deferred;  ///< Possible deferred assertion resolutions
+                        const SymTab::Indexer& indexer;   ///< Name lookup
+
+                        AssertionResnState(const Alternative& alt, const OpenVarSet& openVars, 
+                                const SymTab::Indexer& indexer ) 
+                                : alt{alt}, have{}, newNeed{}, openVars{openVars}, indexer{indexer} {}
+                };
+
+                /// Binds a single assertion from a compatible AssertionPack, updating resolution state 
+                /// as appropriate.
+                void bindAssertion( DeclarationWithType* curDecl, AssertionSetValue& assnInfo, 
+                                AssertionResnState& resn, AssertionPack&& match ) {
+                        DeclarationWithType* candidate = match.cdata.id;
+                        
+                        addToIndexer( match.have, resn.indexer );
+                        resn.newNeed.insert( match.need.begin(), match.need.end() );
+                        resn.openVars = std::move(match.openVars);
+                        resn.alt.env = std::move(match.env);
+
+                        assertf( candidate->get_uniqueId(), "Assertion candidate does not have a unique ID: %s", toString( candidate ).c_str() );
+                        for ( auto& a : match.need ) {
+                                if ( a.second.idChain.empty() ) {
+                                        a.second.idChain = assnInfo.idChain;
+                                        a.second.idChain.push_back( curDecl->get_uniqueId() );
+                                }
+                        }
+
+                        Expression* varExpr = match.cdata.combine( resn.alt.cvtCost );
+                        varExpr->result = match.adjType;
+
+                        // follow the current assertion's ID chain to find the correct set of inferred 
+                        // parameters to add the candidate o (i.e. the set of inferred parameters belonging 
+                        // to the entity which requested the assertion parameter)
+                        InferredParams* inferParams = &resn.alt.expr->inferParams;
+                        for ( UniqueId id : assnInfo.idChain ) {
+                                inferParams = (*inferParams)[ id ].inferParams.get();
+                        }
+
+                        (*inferParams)[ curDecl->get_uniqueId() ] = ParamEntry{
+                                candidate->get_uniqueId(), match.adjType, curDecl->get_type(), varExpr };
+                }
+
+                /// Resolves a single assertion, returning false if no satisfying assertion, binding it 
+                /// if there is exactly one satisfying assertion, or adding to the defer-list if there 
+                /// is more than one
+                bool resolveAssertion( DeclarationWithType* curDecl, AssertionSetValue& assnInfo, 
+                                AssertionResnState& resn ) {
+                        // skip unused assertions
+                        if ( ! assnInfo.isUsed ) return true;
+
+                        // lookup candidates for this assertion
+                        std::list< SymTab::Indexer::IdData > candidates;
+                        decls.lookupId( curDecl->name, candidates );
+
+                        // find the ones that unify with the desired type
+                        DeferList matches;
+                        for ( const auto& cdata : candidates ) {
+                                DeclarationWithType* candidate = cdata.id;
+
+                                // build independent unification context for candidate
+                                AssertionSet have, newNeed;
+                                TypeEnvironment newEnv{ resn.alt.env };
+                                OpenVarSet newOpenVars{ resn.openVars };
+                                Type* adjType = candidate->get_type()->clone();
+                                adjustExprType( adjType, newEnv, resn.indexer );
+                                renameTyVars( adjType );
+
+                                if ( unify( curDecl->get_type(), adjType, newEnv, 
+                                                newNeed, have, newOpenVars, resn.indexer ) ) {
+                                        matches.emplace_back( cdata, adjType, std::move(newEnv), std::move(have), 
+                                                std::move(newNeed), std::move(newOpenVars) );
+                                }
+                        }
+
+                        // Break if no suitable assertion
+                        if ( matches.empty() ) return false;
+
+                        // Defer if too many suitable assertions
+                        if ( matches.size() > 1 ) {
+                                resn.deferred.emplace_back( curDecl, assnInfo, std::move(matches) );
+                                return true;
+                        }
+
+                        // otherwise bind current match in ongoing scope
+                        bindAssertion( curDecl, assnInfo, resn, std::move(matches.front()) );
+
+                        return true;
+                }
+        }
+
         template< typename OutputIterator >
         void AlternativeFinder::Finder::inferParameters( const AssertionSet &need, AssertionSet &have, const Alternative &newAlt, OpenVarSet &openVars, OutputIterator out ) {
@@ -586 +707 @@
                 // )
                 addToIndexer( have, decls );
+
+                AssertionResnState resn{ newAlt, openVars, indexer };
+
+                // resolve assertions in breadth-first-order up to a limited number of levels deep
+                int level;
+                for ( level = 0; level < recursionLimit; ++level ) {
+                        // make initial pass at matching assertions
+                        for ( auto& assn : need ) {
+                                if ( ! resolveAssertion( assn.first, assn.second, resn ) ) {
+                                        // fail early if any assertion fails to resolve
+                                        return;
+                                }
+                        }
+
+                        // resolve deferred assertions by mutual compatibility and min-cost
+                        if ( ! resn.deferred.empty() ) {
+                                // TODO
+                                assert(false && "TODO: deferred assertions unimplemented");
+
+                                // reset for next round
+                                resn.deferred.clear();
+                        }
+
+                        // quit resolving assertions if done
+                        if ( resn.newNeed.empty() ) break;
+
+                        // otherwise start on next group of recursive assertions
+                        need.swap( resn.newNeed );
+                        resn.newNeed.clear();
+                }
+                if ( level >= recursionLimit ) {
+                        SemanticError( newAlt.expr->location, "Too many recursive assertions" );
+                }
+                
+                // add completed assertion to output
+                *out++ = newAlt;
+
+#if 0           
                 AssertionSet newNeed;
                 PRINT(
@@ -599 +758 @@
 //          *out++ = newAlt;
 //          )
+#endif
         }
 
@@ -630 +790 @@
 
                 ArgPack(const TypeEnvironment& env, const AssertionSet& need, const AssertionSet& have,
-                                const OpenVarSet& openVars)
-                        : parent(0), expr(nullptr), cost(Cost::zero), env(env), need(need), have(have),
+                                const OpenVarSet& openVars, Cost initCost = Cost::zero)
+                        : parent(0), expr(nullptr), cost(initCost), env(env), need(need), have(have),
                           openVars(openVars), nextArg(0), tupleStart(0), nextExpl(0), explAlt(0) {}
 
@@ -923 +1083 @@
         }
 
+        namespace {
+
+                struct CountSpecs : public WithVisitorRef<CountSpecs>, WithShortCircuiting {
+
+                        void postvisit(PointerType*) {
+                                // mark specialization of base type
+                                if ( count >= 0 ) ++count;
+                        }
+
+                        void postvisit(ArrayType*) {
+                                // mark specialization of base type
+                                if ( count >= 0 ) ++count;
+                        }
+
+                        void postvisit(ReferenceType*) {
+                                // mark specialization of base type -- xxx maybe not?
+                                if ( count >= 0 ) ++count;
+                        }
+
+                private:
+                        // takes minimum non-negative count over parameter/return list
+                        void takeminover( int& mincount, std::list<DeclarationWithType*>& dwts ) {
+                                for ( DeclarationWithType* dwt : dwts ) {
+                                        count = -1;
+                                        maybeAccept( dwt->get_type(), *visitor );
+                                        if ( count != -1 && count < mincount ) mincount = count;
+                                }
+                        }
+
+                public:
+                        void previsit(FunctionType*) {
+                                // override default child visiting behaviour
+                                visit_children = false;
+                        }
+
+                        void postvisit(FunctionType* fty) {
+                                // take minimal set value of count over ->returnVals and ->parameters
+                                int mincount = std::numeric_limits<int>::max();
+                                takeminover( mincount, fty->parameters );
+                                takeminover( mincount, fty->returnVals );
+                                // add another level to mincount if set
+                                count = mincount < std::numeric_limits<int>::max() ? mincount + 1 : -1;
+                        }
+
+                private:
+                        // returns minimum non-negative count + 1 over type parameters (-1 if none such)
+                        int minover( std::list<Expression*>& parms ) {
+                                int mincount = std::numeric_limits<int>::max();
+                                for ( Expression* parm : parms ) {
+                                        count = -1;
+                                        maybeAccept( parm->get_result(), *visitor );
+                                        if ( count != -1 && count < mincount ) mincount = count;
+                                }
+                                return mincount < std::numeric_limits<int>::max() ? mincount + 1 : -1;
+                        }
+                        
+                public:
+                        void previsit(StructInstType*) {
+                                // override default child behaviour
+                                visit_children = false;
+                        }
+
+                        void postvisit(StructInstType* sity) {
+                                // look for polymorphic parameters
+                                count = minover( sity->parameters );
+                        }
+
+                        void previsit(UnionInstType*) {
+                                // override default child behaviour
+                                visit_children = false;
+                        }
+
+                        void postvisit(UnionInstType* uity) {
+                                // look for polymorphic parameters
+                                count = minover( uity->parameters );
+                        }
+
+                        void postvisit(TypeInstType*) {
+                                // note polymorphic type (which may be specialized)
+                                // xxx - maybe account for open/closed type variables
+                                count = 0;
+                        }
+
+                        void previsit(TupleType*) {
+                                // override default child behaviour
+                                visit_children = false;
+                        }
+
+                        void postvisit(TupleType* tty) {
+                                // take minimum non-negative count
+                                int mincount = std::numeric_limits<int>::max();
+                                for ( Type* ty : tty->types ) {
+                                        count = -1;
+                                        maybeAccept( ty, *visitor );
+                                        if ( count != -1 && count < mincount ) mincount = count;
+                                }
+                                // xxx - maybe don't increment, tuple flattening doesn't necessarily specialize
+                                count = mincount < std::numeric_limits<int>::max() ? mincount + 1: -1;
+                        }
+
+                        int get_count() const { return count >= 0 ? count : 0; }
+                private:
+                        int count = -1;
+                };
+
+                /// Counts the specializations in the types in a function parameter or return list
+                int countSpecs( std::list<DeclarationWithType*>& dwts ) {
+                        int k = 0;
+                        for ( DeclarationWithType* dwt : dwts ) {
+                                PassVisitor<CountSpecs> counter;
+                                maybeAccept( dwt->get_type(), *counter.pass.visitor );
+                                k += counter.pass.get_count();
+                        }
+                        return k;
+                }
+
+                /// Calculates the inherent costs in a function declaration; varCost for the number of 
+                /// type variables and specCost for type assertions, as well as PolyType specializations 
+                /// in the parameter and return lists.
+                Cost declCost( FunctionType* funcType ) {
+                        Cost k = Cost::zero;
+
+                        // add cost of type variables
+                        k.incVar( funcType->forall.size() );
+
+                        // subtract cost of type assertions
+                        for ( TypeDecl* td : funcType->forall ) {
+                                k.decSpec( td->assertions.size() );
+                        }
+
+                        // count specialized polymorphic types in parameter/return lists
+                        k.decSpec( countSpecs( funcType->parameters ) );
+                        k.decSpec( countSpecs( funcType->returnVals ) );
+
+                        return k;
+                }
+        }
+
         template<typename OutputIterator>
         void AlternativeFinder::Finder::validateFunctionAlternative( const Alternative &func, 
@@ -967 +1265 @@
                 }
 
+                // calculate declaration cost of function (+vars-spec)
+                Cost funcCost = declCost( funcType );
+
                 // iteratively build matches, one parameter at a time
                 std::vector<ArgPack> results;
-                results.push_back( ArgPack{ funcEnv, funcNeed, funcHave, funcOpenVars } );
+                results.push_back( ArgPack{ funcEnv, funcNeed, funcHave, funcOpenVars, funcCost } );
                 std::size_t genStart = 0;
 

src/ResolvExpr/Resolver.cc

@@ -51 +51 @@
 namespace ResolvExpr {
         struct Resolver final : public WithIndexer, public WithGuards, public WithVisitorRef<Resolver>, public WithShortCircuiting, public WithStmtsToAdd {
+        
+        friend void resolve( std::list<Declaration*> );
+
                 Resolver() {}
                 Resolver( const SymTab::Indexer & other ) {
@@ -96 +99 @@
                 CurrentObject currentObject = nullptr;
                 bool inEnumDecl = false;
+                bool atTopLevel = false;  ///< Was this resolver set up at the top level of resolution
         };
 
         void resolve( std::list< Declaration * > translationUnit ) {
                 PassVisitor<Resolver> resolver;
+                resolver.pass.atTopLevel = true;  // mark resolver as top-level
                 acceptAll( translationUnit, resolver );
         }