Changeset 0b00df0

Timestamp:

Nov 19, 2018, 5:05:12 PM (6 years ago)

Author:

Aaron Moss <a3moss@…>

Branches:

ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, deferred_resn, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, no_list, persistent-indexer, pthread-emulation, qualifiedEnum

Children:

40290497

Parents:

2fd9f24

Message:

First draft of deferred expression resolution; DOES NOT BUILD

Location:

src

Files:

• GenPoly/Box.cc (modified) (1 diff)
• GenPoly/Specialize.cc (modified) (3 diffs)
• ResolvExpr/AlternativeFinder.cc (modified) (10 diffs)
• ResolvExpr/ResolveAssertions.cc (modified) (12 diffs)
• ResolvExpr/TypeEnvironment.h (modified) (1 diff)
• SynTree/ApplicationExpr.cc (modified) (4 diffs)
• SynTree/Expression.cc (modified) (3 diffs)
• SynTree/Expression.h (modified) (5 diffs)

src/GenPoly/Box.cc

@@ -798 +798 @@
                         for ( Type::ForallList::iterator tyVar = functionType->get_forall().begin(); tyVar != functionType->get_forall().end(); ++tyVar ) {
                                 for ( std::list< DeclarationWithType *>::iterator assert = (*tyVar)->assertions.begin(); assert != (*tyVar)->assertions.end(); ++assert ) {
-                                        InferredParams::const_iterator inferParam = appExpr->get_inferParams().find( (*assert)->get_uniqueId() );
-                                        assertf( inferParam != appExpr->get_inferParams().end(), "addInferredParams missing inferred parameter: %s in: %s", toString( *assert ).c_str(), toString( appExpr ).c_str() );
+                                        InferredParams::const_iterator inferParam = appExpr->inferParams.find( (*assert)->get_uniqueId() );
+                                        assertf( inferParam != appExpr->inferParams.end(), "addInferredParams missing inferred parameter: %s in: %s", toString( *assert ).c_str(), toString( appExpr ).c_str() );
                                         Expression *newExpr = inferParam->second.expr->clone();
                                         addCast( newExpr, (*assert)->get_type(), tyVars );

src/GenPoly/Specialize.cc

@@ -245 +245 @@
                 appExpr->env = TypeSubstitution::newFromExpr( appExpr, env );
                 if ( inferParams ) {
-                        appExpr->get_inferParams() = *inferParams;
+                        appExpr->inferParams = *inferParams;
                 } // if
 
@@ -284 +284 @@
                 std::list< Expression* >::iterator actual;
                 for ( formal = function->get_parameters().begin(), actual = appExpr->get_args().begin(); formal != function->get_parameters().end() && actual != appExpr->get_args().end(); ++formal, ++actual ) {
-                        *actual = doSpecialization( (*formal)->get_type(), *actual, &appExpr->get_inferParams() );
+                        *actual = doSpecialization( (*formal)->get_type(), *actual, &appExpr->inferParams );
                 }
         }
@@ -295 +295 @@
                         // alternatively, if order starts to matter then copy appExpr's inferParams and pass them to handleExplicitParams.
                         handleExplicitParams( appExpr );
-                        for ( InferredParams::iterator inferParam = appExpr->get_inferParams().begin(); inferParam != appExpr->get_inferParams().end(); ++inferParam ) {
-                                inferParam->second.expr = doSpecialization( inferParam->second.formalType, inferParam->second.expr, inferParam->second.inferParams.get() );
+                        for ( InferredParams::iterator inferParam = appExpr->inferParams.begin(); inferParam != appExpr->inferParams.end(); ++inferParam ) {
+                                inferParam->second.expr = doSpecialization( inferParam->second.formalType, inferParam->second.expr, &inferParam->second.expr->inferParams );
                         }
                 }

src/ResolvExpr/AlternativeFinder.cc

@@ -114 +114 @@
                 template<typename OutputIterator>
                 void makeFunctionAlternatives( const Alternative &func, FunctionType *funcType, const ExplodedArgs& args, OutputIterator out );
-                /// Checks if assertion parameters match for a new alternative
+                /// Sets up parameter inference for an output alternative
                 template< typename OutputIterator >
-                void inferParameters( const AssertionSet &need, AssertionSet &have, const Alternative &newAlt, OpenVarSet &openVars, OutputIterator out );
+                void inferParameters( Alternative &newAlt, OutputIterator out );
         private:
                 AlternativeFinder & altFinder;
@@ -486 +486 @@
 
                 // xxx -- replace with new costs in resolver
-                for ( InferredParams::const_iterator assert = appExpr->get_inferParams().begin(); assert != appExpr->get_inferParams().end(); ++assert ) {
+                for ( InferredParams::const_iterator assert = appExpr->inferParams.begin(); assert != appExpr->inferParams.end(); ++assert ) {
                         convCost += computeConversionCost( assert->second.actualType, assert->second.formalType, indexer, alt.env );
                 }
@@ -595 +595 @@
 //                              )
 //                              // follow the current assertion's ID chain to find the correct set of inferred parameters to add the candidate to (i.e. the set of inferred parameters belonging to the entity which requested the assertion parameter).
-//                              InferredParams * inferParameters = &newerAlt.expr->get_inferParams();
+//                              InferredParams * inferParameters = &newerAlt.expr->inferParams;
 //                              for ( UniqueId id : cur->second.idChain ) {
 //                                      inferParameters = (*inferParameters)[ id ].inferParams.get();
@@ -608 +608 @@
 //      }
 
+        /// Unique identifier for matching expression resolutions to their requesting expression
+        UniqueId globalResnSlot = 0;
+
         template< typename OutputIterator >
-        void AlternativeFinder::Finder::inferParameters( const AssertionSet &, AssertionSet &, const Alternative &newAlt, OpenVarSet &, OutputIterator out ) {
+        void AlternativeFinder::Finder::inferParameters( Alternative &newAlt, OutputIterator out ) {
                 // SymTab::Indexer decls( indexer );
                 // addToIndexer( have, decls );
@@ -621 +624 @@
                 // inferRecursive( need.begin(), need.end(), newAlt, openVars, decls, newNeed, 0, indexer, out );
 
-                // add to output list, assertion resolution is defered
+                // Set need bindings for any unbound assertions
+                UniqueId crntResnSlot = 0;  // matching ID for this expression's assertions
+                for ( auto& assn : newAlt.need ) {
+                        // skip already-matched assertions
+                        if ( assn.info.resnSlot != 0 ) continue;
+                        // assign slot for expression if needed
+                        if ( crntResnSlot == 0 ) { crntResnSlot = ++globalResnSlot; }
+                        // fix slot to assertion
+                        assn.info.resnSlot = crntResnSlot;
+                }
+                // pair slot to expression
+                if ( crntResnSlot != 0 ) { newAlt.expr->resnSlots.push_back( crntResnSlot ); }
+
+                // add to output list, assertion resolution is deferred
                 *out++ = newAlt;
         }
@@ -969 +985 @@
                         printAssertionSet( result.need, std::cerr, 8 );
                 )
-                inferParameters( result.need, result.have, newAlt, result.openVars, out );
+                inferParameters( newAlt, out );
         }
 
@@ -1330 +1346 @@
                                         restructureCast( alt.expr->clone(), toType, castExpr->isGenerated ), 
                                         alt.env, openVars, needAssertions, alt.cost, thisCost };
-                                inferParameters( needAssertions, haveAssertions, newAlt, openVars,
-                                        back_inserter( candidates ) );
+                                inferParameters( newAlt, back_inserter( candidates ) );
                         } // if
                 } // for
@@ -1639 +1654 @@
                                                         newExpr, std::move(compositeEnv), std::move(openVars), 
                                                         AssertionList( need.begin(), need.end() ), cost };
-                                                inferParameters( need, have, newAlt, openVars, back_inserter( alternatives ) );
+                                                inferParameters( newAlt, back_inserter( alternatives ) );
                                         } // if
                                 } // for
@@ -1686 +1701 @@
                                                 newExpr, std::move(compositeEnv), std::move(openVars), 
                                                 AssertionList( need.begin(), need.end() ), first.cost + second.cost };
-                                        inferParameters( need, have, newAlt, openVars, back_inserter( alternatives ) );
+                                        inferParameters( newAlt, back_inserter( alternatives ) );
                                 } // if
                         } // for
@@ -1814 +1829 @@
                                                 std::move(newEnv), std::move(openVars), 
                                                 AssertionList( need.begin(), need.end() ), alt.cost, thisCost };
-                                        inferParameters( need, have, newAlt, openVars, back_inserter( candidates ) );
+                                        inferParameters( newAlt, back_inserter( candidates ) );
                                 }
                         }

src/ResolvExpr/ResolveAssertions.cc

@@ -18 +18 @@
 #include <cassert>                // for assertf
 #include <list>                   // for list
-#include <unordered_map>          // for unordered_map
+#include <unordered_map>          // for unordered_map, unordered_multimap
 #include <utility>                // for move
 #include <vector>                 // for vector
 
-#include "Alternative.h"          // for Alternative, AssertionItem
+#include "Alternative.h"          // for Alternative, AssertionItem, AssertionList
 #include "Common/FilterCombos.h"  // for filterCombos
 #include "Common/utility.h"       // for sort_mins
 #include "SymTab/Indexer.h"       // for Indexer
+#include "SynTree/Expression.h"   // for InferredParams
 #include "TypeEnvironment.h"      // for TypeEnvironment, etc.
 #include "typeops.h"              // for adjustExprType
@@ -39 +40 @@
                 AssertionSet need;              ///< Post-unification need-set
                 OpenVarSet openVars;            ///< Post-unification open-var set
+                UniqueId resnSlot;              ///< Slot for any recursive assertion IDs
 
                 AssnCandidate( const SymTab::Indexer::IdData& cdata, Type* adjType, TypeEnvironment&& env, 
-                        AssertionSet&& have, AssertionSet&& need, OpenVarSet&& openVars ) 
+                        AssertionSet&& have, AssertionSet&& need, OpenVarSet&& openVars, UniqueId resnSlot ) 
                 : cdata(cdata), adjType(adjType), env(std::move(env)), have(std::move(have)), 
-                        need(std::move(need)), openVars(std::move(openVars)) {}
+                        need(std::move(need)), openVars(std::move(openVars)), resnSlot(resnSlot) {}
         };
 
@@ -159 +161 @@
         };
 
+        /// Set of assertion resolutions, grouped by resolution ID
+        using InferCache = std::unordered_map< UniqueId, InferredParams >;
+
         /// Flag for state iteration
         enum IterateFlag { IterateState };
@@ -164 +169 @@
         /// State needed to resolve a set of assertions
         struct ResnState {
-                Alternative alt;                  ///< Alternative assertion is rooted on
-                std::vector<AssertionItem> need;  ///< Assertions to find
-                AssertionSet newNeed;             ///< New assertions for current resolutions
-                DeferList deferred;               ///< Deferred matches
-                SymTab::Indexer& indexer;         ///< Name lookup (depends on previous assertions)
+                Alternative alt;           ///< Alternative assertion is rooted on
+                AssertionList need;        ///< Assertions to find
+                AssertionSet newNeed;      ///< New assertions for current resolutions
+                DeferList deferred;        ///< Deferred matches
+                InferCache inferred;       ///< Cache of already-inferred parameters
+                SymTab::Indexer& indexer;  ///< Name lookup (depends on previous assertions)
 
                 /// Initial resolution state for an alternative
                 ResnState( Alternative& a, SymTab::Indexer& indexer )
-                : alt(a), need(), newNeed(), deferred(), indexer(indexer) {
+                : alt(a), need(), newNeed(), deferred(), inferred(), indexer(indexer) {
                         need.swap( a.need );
                 }
@@ -179 +185 @@
                 ResnState( ResnState&& o, IterateFlag )
                 : alt(std::move(o.alt)), need(o.newNeed.begin(), o.newNeed.end()), newNeed(), deferred(), 
-                  indexer(o.indexer) {}
+                  inferred(std::move(o.inferred)), indexer(o.indexer) {}
         };
 
         /// Binds a single assertion, updating resolution state
         void bindAssertion( const DeclarationWithType* decl, AssertionSetValue info, Alternative& alt, 
-                        AssnCandidate& match ) {
+                        AssnCandidate& match, InferCache& inferred ) {
                 
                 DeclarationWithType* candidate = match.cdata.id;
@@ -192 +198 @@
                 delete varExpr->result;
                 varExpr->result = match.adjType->clone();
-
-                // 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 = &alt.expr->inferParams;
-                for ( UniqueId id : info.idChain ) {
-                        inferParams = (*inferParams)[ id ].inferParams.get();
-                }
-
-                (*inferParams)[ decl->get_uniqueId() ] = ParamEntry{
+                if ( match.resnSlot ) { varExpr->resnSlots.push_back( match.resnSlot ); }
+
+                // place newly-inferred assertion in proper place in cache
+                inferred[ info.resnSlot ][ decl->get_uniqueId() ] = ParamEntry{
                                 candidate->get_uniqueId(), match.adjType, decl->get_type()->clone(), varExpr };
+
+                // // 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 = &alt.expr->inferParams;
+                // for ( UniqueId id : info.idChain ) {
+                //      inferParams = (*inferParams)[ id ].inferParams.get();
+                // }
+
+                // (*inferParams)[ decl->get_uniqueId() ] = ParamEntry{
+                //              candidate->get_uniqueId(), match.adjType, decl->get_type()->clone(), varExpr };
         }
 
@@ -214 +225 @@
         }
 
+        // in AlternativeFinder.cc; unique ID for assertion resolutions
+        extern UniqueId globalResnSlot;
+
         /// Resolve a single assertion, in context
         bool resolveAssertion( AssertionItem& assn, ResnState& resn ) {
@@ -238 +252 @@
                         if ( unify( assn.decl->get_type(), adjType, newEnv, newNeed, have, newOpenVars, 
                                         resn.indexer ) ) {
-                                // set up idChain on new assertions
-                                for ( auto& a : newNeed ) {
-                                        a.second.idChain = assn.info.idChain;
-                                        a.second.idChain.push_back( assn.decl->get_uniqueId() );
+                                // set up binding slot for recursive assertions
+                                UniqueId crntResnSlot = 0;
+                                if ( ! newNeed.empty() ) {
+                                        crntResnSlot = ++globalResnSlot;
+                                        for ( auto& a : newNeed ) {
+                                                a.second.resnSlot = crntResnSlot;
+                                        }
                                 }
+                                // // set up idChain on new assertions
+                                // for ( auto& a : newNeed ) {
+                                //      a.second.idChain = assn.info.idChain;
+                                //      a.second.idChain.push_back( assn.decl->get_uniqueId() );
+                                // }
 
                                 matches.emplace_back( cdata, adjType, std::move(newEnv), std::move(have), 
-                                        std::move(newNeed), std::move(newOpenVars) );
+                                        std::move(newNeed), std::move(newOpenVars), crntResnSlot );
                         } else {
                                 delete adjType;
@@ -267 +289 @@
                 resn.alt.openVars = std::move(match.openVars);
 
-                bindAssertion( assn.decl, assn.info, resn.alt, match );
+                bindAssertion( assn.decl, assn.info, resn.alt, match, resn.inferred );
                 return true;
         }
 
-        ///< Limit to depth of recursion of assertion satisfaction
+        /// Associates inferred parameters with an expression
+        struct InferMatcher {
+                InferCache& inferred;
+
+                InferMatcher( InferCache& inferred ) : inferred( inferred ) {}
+
+                Expression* postmutate( Expression* expr ) {
+                        // place inferred parameters into resolution slots
+                        for ( UniqueId slot : expr->resnSlots ) {
+                                // fail if no matching parameters found
+                                InferredParams& inferParams = inferred.at( slot );
+                                
+                                // place inferred parameters into proper place in expression
+                                for ( auto& entry : inferParams ) {
+                                        // recurse on inferParams of resolved expressions
+                                        entry.second.expr = postmutate( entry.second.expr );
+                                        // xxx - look at entry.second.inferParams?
+                                        expr->inferParams[ entry.first ] = entry.second;
+                                }
+                        }
+
+                        // clear resolution slots and return
+                        expr->resnSlots.clear();
+                        return expr;
+                }
+        };
+
+        void finalizeAssertions( Alternative& alt, InferCache& inferred, AltList& out ) {
+                PassVisitor<InferMatcher> matcher{ inferred };
+                alt.expr = alt.expr->acceptMutator( matcher );
+                out.emplace_back( alt );
+        }
+
+        /// Limit to depth of recursion of assertion satisfaction
         static const int recursionLimit = /* 10 */ 4;
 
@@ -300 +355 @@
                                         // either add successful match or push back next state
                                         if ( resn.newNeed.empty() ) {
-                                                out.emplace_back( resn.alt );
+                                                finalizeAssertions( resn.alt, resn.inferred, out );
                                         } else {
                                                 new_resns.emplace_back( std::move(resn), IterateState );
@@ -322 +377 @@
                                                         new_resn.newNeed.insert( match.need.begin(), match.need.end() );
 
-                                                        bindAssertion( r.decl, r.info, new_resn.alt, match );
+                                                        bindAssertion( r.decl, r.info, new_resn.alt, match, new_resn.inferred );
                                                 }
 
@@ -331 +386 @@
                                                 // either add sucessful match or push back next state
                                                 if ( new_resn.newNeed.empty() ) {
-                                                        out.emplace_back( new_resn.alt );
+                                                        finalizeAssertions( new_resn.alt, new_resn.inferred, out );
                                                 } else {
                                                         new_resns.emplace_back( std::move(new_resn), IterateState );

src/ResolvExpr/TypeEnvironment.h

@@ -59 +59 @@
         };
         struct AssertionSetValue {
-                bool isUsed;
-                // chain of Unique IDs of the assertion declarations. The first ID in the chain is the ID 
-                // of an assertion on the current type, with each successive ID being the ID of an 
-                // assertion pulled in by the previous ID. The last ID in the chain is the ID of the 
-                // assertion that pulled in the current assertion.
-                std::list< UniqueId > idChain;
+                bool isUsed;        ///< True if assertion needs to be resolved
+                UniqueId resnSlot;  ///< ID of slot assertion belongs to
+
+                AssertionSetValue() : isUsed(false), resnSlot(0) {}
         };
         typedef std::map< DeclarationWithType*, AssertionSetValue, AssertCompare > AssertionSet;

src/SynTree/ApplicationExpr.cc

@@ -29 +29 @@
 
 ParamEntry::ParamEntry( const ParamEntry &other ) :
-                decl( other.decl ), actualType( maybeClone( other.actualType ) ), formalType( maybeClone( other.formalType ) ), expr( maybeClone( other.expr ) ), inferParams( new InferredParams( *other.inferParams ) ) {
+                decl( other.decl ), actualType( maybeClone( other.actualType ) ), formalType( maybeClone( other.formalType ) ), expr( maybeClone( other.expr ) )/*, inferParams( new InferredParams( *other.inferParams ) )*/ {
 }
 
@@ -39 +39 @@
         formalType = maybeClone( other.formalType );
         expr = maybeClone( other.expr );
-        *inferParams = *other.inferParams;
+        // *inferParams = *other.inferParams;
         return *this;
 }
@@ -50 +50 @@
 
 ParamEntry::ParamEntry( ParamEntry && other ) :
-                decl( other.decl ), actualType( other.actualType ), formalType( other.formalType ), expr( other.expr ), inferParams( std::move( other.inferParams ) ) {
+                decl( other.decl ), actualType( other.actualType ), formalType( other.formalType ), expr( other.expr )/*, inferParams( std::move( other.inferParams ) )*/ {
         other.actualType = nullptr;
         other.formalType = nullptr;
@@ -68 +68 @@
         other.formalType = nullptr;
         other.expr = nullptr;
-        inferParams = std::move( other.inferParams );
+        // inferParams = std::move( other.inferParams );
         return *this;
 }

src/SynTree/Expression.cc

@@ -40 +40 @@
                         Declaration::declFromId( i->second.decl )->printShort( os, indent+1 );
                         os << std::endl;
-                        printInferParams( *i->second.inferParams, os, indent+1, level+1 );
+                        printInferParams( i->second.expr->inferParams, os, indent+1, level+1 );
                 } // for
         } // if
@@ -47 +47 @@
 Expression::Expression() : result( 0 ), env( 0 ) {}
 
-Expression::Expression( const Expression &other ) : BaseSyntaxNode( other ), result( maybeClone( other.result ) ), env( maybeClone( other.env ) ), extension( other.extension ), inferParams( other.inferParams ) {
-}
+Expression::Expression( const Expression &other ) : BaseSyntaxNode( other ), result( maybeClone( other.result ) ), env( maybeClone( other.env ) ), extension( other.extension ), inferParams( other.inferParams ), resnSlots( other.resnSlots ) {}
 
 void Expression::spliceInferParams( Expression * other ) {
@@ -55 +54 @@
                 inferParams[p.first] = std::move( p.second );
         }
+        resnSlots.insert( resnSlots.end(), other->resnSlots.begin(), other->resnSlots.end() );
 }
 

src/SynTree/Expression.h

@@ -21 +21 @@
 #include <memory>                 // for allocator, unique_ptr
 #include <string>                 // for string
+#include <vector>                 // for vector
 
 #include "BaseSyntaxNode.h"       // for BaseSyntaxNode
@@ -38 +39 @@
 /// but subject to decay-to-pointer and type parameter renaming
 struct ParamEntry {
-        ParamEntry(): decl( 0 ), actualType( 0 ), formalType( 0 ), expr( 0 ), inferParams( new InferredParams ) {}
-        ParamEntry( UniqueId decl, Type * actualType, Type * formalType, Expression* expr ): decl( decl ), actualType( actualType ), formalType( formalType ), expr( expr ), inferParams( new InferredParams ) {}
+        ParamEntry(): decl( 0 ), actualType( 0 ), formalType( 0 ), expr( 0 )/*, inferParams( new InferredParams )*/ {}
+        ParamEntry( UniqueId decl, Type * actualType, Type * formalType, Expression* expr ): decl( decl ), actualType( actualType ), formalType( formalType ), expr( expr )/*, inferParams( new InferredParams )*/ {}
         ParamEntry( const ParamEntry & other );
         ParamEntry( ParamEntry && other );
@@ -50 +51 @@
         Type * formalType;
         Expression * expr;
-        std::unique_ptr< InferredParams > inferParams;
+        // std::unique_ptr< InferredParams > inferParams;
 };
 
@@ -59 +60 @@
         TypeSubstitution * env;
         bool extension = false;
-        InferredParams inferParams;
+        InferredParams inferParams;       ///< Post-resolution inferred parameter slots
+        std::vector<UniqueId> resnSlots;  ///< Pre-resolution inferred parameter slots
+        
+        // xxx - should turn inferParams+resnSlots into a union to save some memory
 
         Expression();
@@ -73 +77 @@
         bool get_extension() const { return extension; }
         Expression * set_extension( bool exten ) { extension = exten; return this; }
-
-        InferredParams & get_inferParams() { return inferParams; }
 
         // move other's inferParams to this