Changeset 0b00df0


Ignore:
Timestamp:
Nov 19, 2018, 5:05:12 PM (3 years ago)
Author:
Aaron Moss <a3moss@…>
Branches:
aaron-thesis, arm-eh, cleanup-dtors, deferred_resn, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, no_list, persistent-indexer
Children:
40290497
Parents:
2fd9f24
Message:

First draft of deferred expression resolution; DOES NOT BUILD

Location:
src
Files:
8 edited

Legend:

Unmodified
Added
Removed
  • src/GenPoly/Box.cc

    r2fd9f24 r0b00df0  
    798798                        for ( Type::ForallList::iterator tyVar = functionType->get_forall().begin(); tyVar != functionType->get_forall().end(); ++tyVar ) {
    799799                                for ( std::list< DeclarationWithType *>::iterator assert = (*tyVar)->assertions.begin(); assert != (*tyVar)->assertions.end(); ++assert ) {
    800                                         InferredParams::const_iterator inferParam = appExpr->get_inferParams().find( (*assert)->get_uniqueId() );
    801                                         assertf( inferParam != appExpr->get_inferParams().end(), "addInferredParams missing inferred parameter: %s in: %s", toString( *assert ).c_str(), toString( appExpr ).c_str() );
     800                                        InferredParams::const_iterator inferParam = appExpr->inferParams.find( (*assert)->get_uniqueId() );
     801                                        assertf( inferParam != appExpr->inferParams.end(), "addInferredParams missing inferred parameter: %s in: %s", toString( *assert ).c_str(), toString( appExpr ).c_str() );
    802802                                        Expression *newExpr = inferParam->second.expr->clone();
    803803                                        addCast( newExpr, (*assert)->get_type(), tyVars );
  • src/GenPoly/Specialize.cc

    r2fd9f24 r0b00df0  
    245245                appExpr->env = TypeSubstitution::newFromExpr( appExpr, env );
    246246                if ( inferParams ) {
    247                         appExpr->get_inferParams() = *inferParams;
     247                        appExpr->inferParams = *inferParams;
    248248                } // if
    249249
     
    284284                std::list< Expression* >::iterator actual;
    285285                for ( formal = function->get_parameters().begin(), actual = appExpr->get_args().begin(); formal != function->get_parameters().end() && actual != appExpr->get_args().end(); ++formal, ++actual ) {
    286                         *actual = doSpecialization( (*formal)->get_type(), *actual, &appExpr->get_inferParams() );
     286                        *actual = doSpecialization( (*formal)->get_type(), *actual, &appExpr->inferParams );
    287287                }
    288288        }
     
    295295                        // alternatively, if order starts to matter then copy appExpr's inferParams and pass them to handleExplicitParams.
    296296                        handleExplicitParams( appExpr );
    297                         for ( InferredParams::iterator inferParam = appExpr->get_inferParams().begin(); inferParam != appExpr->get_inferParams().end(); ++inferParam ) {
    298                                 inferParam->second.expr = doSpecialization( inferParam->second.formalType, inferParam->second.expr, inferParam->second.inferParams.get() );
     297                        for ( InferredParams::iterator inferParam = appExpr->inferParams.begin(); inferParam != appExpr->inferParams.end(); ++inferParam ) {
     298                                inferParam->second.expr = doSpecialization( inferParam->second.formalType, inferParam->second.expr, &inferParam->second.expr->inferParams );
    299299                        }
    300300                }
  • src/ResolvExpr/AlternativeFinder.cc

    r2fd9f24 r0b00df0  
    114114                template<typename OutputIterator>
    115115                void makeFunctionAlternatives( const Alternative &func, FunctionType *funcType, const ExplodedArgs& args, OutputIterator out );
    116                 /// Checks if assertion parameters match for a new alternative
     116                /// Sets up parameter inference for an output alternative
    117117                template< typename OutputIterator >
    118                 void inferParameters( const AssertionSet &need, AssertionSet &have, const Alternative &newAlt, OpenVarSet &openVars, OutputIterator out );
     118                void inferParameters( Alternative &newAlt, OutputIterator out );
    119119        private:
    120120                AlternativeFinder & altFinder;
     
    486486
    487487                // xxx -- replace with new costs in resolver
    488                 for ( InferredParams::const_iterator assert = appExpr->get_inferParams().begin(); assert != appExpr->get_inferParams().end(); ++assert ) {
     488                for ( InferredParams::const_iterator assert = appExpr->inferParams.begin(); assert != appExpr->inferParams.end(); ++assert ) {
    489489                        convCost += computeConversionCost( assert->second.actualType, assert->second.formalType, indexer, alt.env );
    490490                }
     
    595595//                              )
    596596//                              // 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).
    597 //                              InferredParams * inferParameters = &newerAlt.expr->get_inferParams();
     597//                              InferredParams * inferParameters = &newerAlt.expr->inferParams;
    598598//                              for ( UniqueId id : cur->second.idChain ) {
    599599//                                      inferParameters = (*inferParameters)[ id ].inferParams.get();
     
    608608//      }
    609609
     610        /// Unique identifier for matching expression resolutions to their requesting expression
     611        UniqueId globalResnSlot = 0;
     612
    610613        template< typename OutputIterator >
    611         void AlternativeFinder::Finder::inferParameters( const AssertionSet &, AssertionSet &, const Alternative &newAlt, OpenVarSet &, OutputIterator out ) {
     614        void AlternativeFinder::Finder::inferParameters( Alternative &newAlt, OutputIterator out ) {
    612615                // SymTab::Indexer decls( indexer );
    613616                // addToIndexer( have, decls );
     
    621624                // inferRecursive( need.begin(), need.end(), newAlt, openVars, decls, newNeed, 0, indexer, out );
    622625
    623                 // add to output list, assertion resolution is defered
     626                // Set need bindings for any unbound assertions
     627                UniqueId crntResnSlot = 0;  // matching ID for this expression's assertions
     628                for ( auto& assn : newAlt.need ) {
     629                        // skip already-matched assertions
     630                        if ( assn.info.resnSlot != 0 ) continue;
     631                        // assign slot for expression if needed
     632                        if ( crntResnSlot == 0 ) { crntResnSlot = ++globalResnSlot; }
     633                        // fix slot to assertion
     634                        assn.info.resnSlot = crntResnSlot;
     635                }
     636                // pair slot to expression
     637                if ( crntResnSlot != 0 ) { newAlt.expr->resnSlots.push_back( crntResnSlot ); }
     638
     639                // add to output list, assertion resolution is deferred
    624640                *out++ = newAlt;
    625641        }
     
    969985                        printAssertionSet( result.need, std::cerr, 8 );
    970986                )
    971                 inferParameters( result.need, result.have, newAlt, result.openVars, out );
     987                inferParameters( newAlt, out );
    972988        }
    973989
     
    13301346                                        restructureCast( alt.expr->clone(), toType, castExpr->isGenerated ),
    13311347                                        alt.env, openVars, needAssertions, alt.cost, thisCost };
    1332                                 inferParameters( needAssertions, haveAssertions, newAlt, openVars,
    1333                                         back_inserter( candidates ) );
     1348                                inferParameters( newAlt, back_inserter( candidates ) );
    13341349                        } // if
    13351350                } // for
     
    16391654                                                        newExpr, std::move(compositeEnv), std::move(openVars),
    16401655                                                        AssertionList( need.begin(), need.end() ), cost };
    1641                                                 inferParameters( need, have, newAlt, openVars, back_inserter( alternatives ) );
     1656                                                inferParameters( newAlt, back_inserter( alternatives ) );
    16421657                                        } // if
    16431658                                } // for
     
    16861701                                                newExpr, std::move(compositeEnv), std::move(openVars),
    16871702                                                AssertionList( need.begin(), need.end() ), first.cost + second.cost };
    1688                                         inferParameters( need, have, newAlt, openVars, back_inserter( alternatives ) );
     1703                                        inferParameters( newAlt, back_inserter( alternatives ) );
    16891704                                } // if
    16901705                        } // for
     
    18141829                                                std::move(newEnv), std::move(openVars),
    18151830                                                AssertionList( need.begin(), need.end() ), alt.cost, thisCost };
    1816                                         inferParameters( need, have, newAlt, openVars, back_inserter( candidates ) );
     1831                                        inferParameters( newAlt, back_inserter( candidates ) );
    18171832                                }
    18181833                        }
  • src/ResolvExpr/ResolveAssertions.cc

    r2fd9f24 r0b00df0  
    1818#include <cassert>                // for assertf
    1919#include <list>                   // for list
    20 #include <unordered_map>          // for unordered_map
     20#include <unordered_map>          // for unordered_map, unordered_multimap
    2121#include <utility>                // for move
    2222#include <vector>                 // for vector
    2323
    24 #include "Alternative.h"          // for Alternative, AssertionItem
     24#include "Alternative.h"          // for Alternative, AssertionItem, AssertionList
    2525#include "Common/FilterCombos.h"  // for filterCombos
    2626#include "Common/utility.h"       // for sort_mins
    2727#include "SymTab/Indexer.h"       // for Indexer
     28#include "SynTree/Expression.h"   // for InferredParams
    2829#include "TypeEnvironment.h"      // for TypeEnvironment, etc.
    2930#include "typeops.h"              // for adjustExprType
     
    3940                AssertionSet need;              ///< Post-unification need-set
    4041                OpenVarSet openVars;            ///< Post-unification open-var set
     42                UniqueId resnSlot;              ///< Slot for any recursive assertion IDs
    4143
    4244                AssnCandidate( const SymTab::Indexer::IdData& cdata, Type* adjType, TypeEnvironment&& env,
    43                         AssertionSet&& have, AssertionSet&& need, OpenVarSet&& openVars )
     45                        AssertionSet&& have, AssertionSet&& need, OpenVarSet&& openVars, UniqueId resnSlot )
    4446                : cdata(cdata), adjType(adjType), env(std::move(env)), have(std::move(have)),
    45                         need(std::move(need)), openVars(std::move(openVars)) {}
     47                        need(std::move(need)), openVars(std::move(openVars)), resnSlot(resnSlot) {}
    4648        };
    4749
     
    159161        };
    160162
     163        /// Set of assertion resolutions, grouped by resolution ID
     164        using InferCache = std::unordered_map< UniqueId, InferredParams >;
     165
    161166        /// Flag for state iteration
    162167        enum IterateFlag { IterateState };
     
    164169        /// State needed to resolve a set of assertions
    165170        struct ResnState {
    166                 Alternative alt;                  ///< Alternative assertion is rooted on
    167                 std::vector<AssertionItem> need;  ///< Assertions to find
    168                 AssertionSet newNeed;             ///< New assertions for current resolutions
    169                 DeferList deferred;               ///< Deferred matches
    170                 SymTab::Indexer& indexer;         ///< Name lookup (depends on previous assertions)
     171                Alternative alt;           ///< Alternative assertion is rooted on
     172                AssertionList need;        ///< Assertions to find
     173                AssertionSet newNeed;      ///< New assertions for current resolutions
     174                DeferList deferred;        ///< Deferred matches
     175                InferCache inferred;       ///< Cache of already-inferred parameters
     176                SymTab::Indexer& indexer;  ///< Name lookup (depends on previous assertions)
    171177
    172178                /// Initial resolution state for an alternative
    173179                ResnState( Alternative& a, SymTab::Indexer& indexer )
    174                 : alt(a), need(), newNeed(), deferred(), indexer(indexer) {
     180                : alt(a), need(), newNeed(), deferred(), inferred(), indexer(indexer) {
    175181                        need.swap( a.need );
    176182                }
     
    179185                ResnState( ResnState&& o, IterateFlag )
    180186                : alt(std::move(o.alt)), need(o.newNeed.begin(), o.newNeed.end()), newNeed(), deferred(),
    181                   indexer(o.indexer) {}
     187                  inferred(std::move(o.inferred)), indexer(o.indexer) {}
    182188        };
    183189
    184190        /// Binds a single assertion, updating resolution state
    185191        void bindAssertion( const DeclarationWithType* decl, AssertionSetValue info, Alternative& alt,
    186                         AssnCandidate& match ) {
     192                        AssnCandidate& match, InferCache& inferred ) {
    187193               
    188194                DeclarationWithType* candidate = match.cdata.id;
     
    192198                delete varExpr->result;
    193199                varExpr->result = match.adjType->clone();
    194 
    195                 // follow the current assertion's ID chain to find the correct set of inferred parameters
    196                 // to add the candidate o (i.e. the set of inferred parameters belonging to the entity
    197                 // which requested the assertion parameter)
    198                 InferredParams* inferParams = &alt.expr->inferParams;
    199                 for ( UniqueId id : info.idChain ) {
    200                         inferParams = (*inferParams)[ id ].inferParams.get();
    201                 }
    202 
    203                 (*inferParams)[ decl->get_uniqueId() ] = ParamEntry{
     200                if ( match.resnSlot ) { varExpr->resnSlots.push_back( match.resnSlot ); }
     201
     202                // place newly-inferred assertion in proper place in cache
     203                inferred[ info.resnSlot ][ decl->get_uniqueId() ] = ParamEntry{
    204204                                candidate->get_uniqueId(), match.adjType, decl->get_type()->clone(), varExpr };
     205
     206                // // follow the current assertion's ID chain to find the correct set of inferred parameters
     207                // // to add the candidate o (i.e. the set of inferred parameters belonging to the entity
     208                // // which requested the assertion parameter)
     209                // InferredParams* inferParams = &alt.expr->inferParams;
     210                // for ( UniqueId id : info.idChain ) {
     211                //      inferParams = (*inferParams)[ id ].inferParams.get();
     212                // }
     213
     214                // (*inferParams)[ decl->get_uniqueId() ] = ParamEntry{
     215                //              candidate->get_uniqueId(), match.adjType, decl->get_type()->clone(), varExpr };
    205216        }
    206217
     
    214225        }
    215226
     227        // in AlternativeFinder.cc; unique ID for assertion resolutions
     228        extern UniqueId globalResnSlot;
     229
    216230        /// Resolve a single assertion, in context
    217231        bool resolveAssertion( AssertionItem& assn, ResnState& resn ) {
     
    238252                        if ( unify( assn.decl->get_type(), adjType, newEnv, newNeed, have, newOpenVars,
    239253                                        resn.indexer ) ) {
    240                                 // set up idChain on new assertions
    241                                 for ( auto& a : newNeed ) {
    242                                         a.second.idChain = assn.info.idChain;
    243                                         a.second.idChain.push_back( assn.decl->get_uniqueId() );
     254                                // set up binding slot for recursive assertions
     255                                UniqueId crntResnSlot = 0;
     256                                if ( ! newNeed.empty() ) {
     257                                        crntResnSlot = ++globalResnSlot;
     258                                        for ( auto& a : newNeed ) {
     259                                                a.second.resnSlot = crntResnSlot;
     260                                        }
    244261                                }
     262                                // // set up idChain on new assertions
     263                                // for ( auto& a : newNeed ) {
     264                                //      a.second.idChain = assn.info.idChain;
     265                                //      a.second.idChain.push_back( assn.decl->get_uniqueId() );
     266                                // }
    245267
    246268                                matches.emplace_back( cdata, adjType, std::move(newEnv), std::move(have),
    247                                         std::move(newNeed), std::move(newOpenVars) );
     269                                        std::move(newNeed), std::move(newOpenVars), crntResnSlot );
    248270                        } else {
    249271                                delete adjType;
     
    267289                resn.alt.openVars = std::move(match.openVars);
    268290
    269                 bindAssertion( assn.decl, assn.info, resn.alt, match );
     291                bindAssertion( assn.decl, assn.info, resn.alt, match, resn.inferred );
    270292                return true;
    271293        }
    272294
    273         ///< Limit to depth of recursion of assertion satisfaction
     295        /// Associates inferred parameters with an expression
     296        struct InferMatcher {
     297                InferCache& inferred;
     298
     299                InferMatcher( InferCache& inferred ) : inferred( inferred ) {}
     300
     301                Expression* postmutate( Expression* expr ) {
     302                        // place inferred parameters into resolution slots
     303                        for ( UniqueId slot : expr->resnSlots ) {
     304                                // fail if no matching parameters found
     305                                InferredParams& inferParams = inferred.at( slot );
     306                               
     307                                // place inferred parameters into proper place in expression
     308                                for ( auto& entry : inferParams ) {
     309                                        // recurse on inferParams of resolved expressions
     310                                        entry.second.expr = postmutate( entry.second.expr );
     311                                        // xxx - look at entry.second.inferParams?
     312                                        expr->inferParams[ entry.first ] = entry.second;
     313                                }
     314                        }
     315
     316                        // clear resolution slots and return
     317                        expr->resnSlots.clear();
     318                        return expr;
     319                }
     320        };
     321
     322        void finalizeAssertions( Alternative& alt, InferCache& inferred, AltList& out ) {
     323                PassVisitor<InferMatcher> matcher{ inferred };
     324                alt.expr = alt.expr->acceptMutator( matcher );
     325                out.emplace_back( alt );
     326        }
     327
     328        /// Limit to depth of recursion of assertion satisfaction
    274329        static const int recursionLimit = /* 10 */ 4;
    275330
     
    300355                                        // either add successful match or push back next state
    301356                                        if ( resn.newNeed.empty() ) {
    302                                                 out.emplace_back( resn.alt );
     357                                                finalizeAssertions( resn.alt, resn.inferred, out );
    303358                                        } else {
    304359                                                new_resns.emplace_back( std::move(resn), IterateState );
     
    322377                                                        new_resn.newNeed.insert( match.need.begin(), match.need.end() );
    323378
    324                                                         bindAssertion( r.decl, r.info, new_resn.alt, match );
     379                                                        bindAssertion( r.decl, r.info, new_resn.alt, match, new_resn.inferred );
    325380                                                }
    326381
     
    331386                                                // either add sucessful match or push back next state
    332387                                                if ( new_resn.newNeed.empty() ) {
    333                                                         out.emplace_back( new_resn.alt );
     388                                                        finalizeAssertions( new_resn.alt, new_resn.inferred, out );
    334389                                                } else {
    335390                                                        new_resns.emplace_back( std::move(new_resn), IterateState );
  • src/ResolvExpr/TypeEnvironment.h

    r2fd9f24 r0b00df0  
    5959        };
    6060        struct AssertionSetValue {
    61                 bool isUsed;
    62                 // chain of Unique IDs of the assertion declarations. The first ID in the chain is the ID
    63                 // of an assertion on the current type, with each successive ID being the ID of an
    64                 // assertion pulled in by the previous ID. The last ID in the chain is the ID of the
    65                 // assertion that pulled in the current assertion.
    66                 std::list< UniqueId > idChain;
     61                bool isUsed;        ///< True if assertion needs to be resolved
     62                UniqueId resnSlot;  ///< ID of slot assertion belongs to
     63
     64                AssertionSetValue() : isUsed(false), resnSlot(0) {}
    6765        };
    6866        typedef std::map< DeclarationWithType*, AssertionSetValue, AssertCompare > AssertionSet;
  • src/SynTree/ApplicationExpr.cc

    r2fd9f24 r0b00df0  
    2929
    3030ParamEntry::ParamEntry( const ParamEntry &other ) :
    31                 decl( other.decl ), actualType( maybeClone( other.actualType ) ), formalType( maybeClone( other.formalType ) ), expr( maybeClone( other.expr ) ), inferParams( new InferredParams( *other.inferParams ) ) {
     31                decl( other.decl ), actualType( maybeClone( other.actualType ) ), formalType( maybeClone( other.formalType ) ), expr( maybeClone( other.expr ) )/*, inferParams( new InferredParams( *other.inferParams ) )*/ {
    3232}
    3333
     
    3939        formalType = maybeClone( other.formalType );
    4040        expr = maybeClone( other.expr );
    41         *inferParams = *other.inferParams;
     41        // *inferParams = *other.inferParams;
    4242        return *this;
    4343}
     
    5050
    5151ParamEntry::ParamEntry( ParamEntry && other ) :
    52                 decl( other.decl ), actualType( other.actualType ), formalType( other.formalType ), expr( other.expr ), inferParams( std::move( other.inferParams ) ) {
     52                decl( other.decl ), actualType( other.actualType ), formalType( other.formalType ), expr( other.expr )/*, inferParams( std::move( other.inferParams ) )*/ {
    5353        other.actualType = nullptr;
    5454        other.formalType = nullptr;
     
    6868        other.formalType = nullptr;
    6969        other.expr = nullptr;
    70         inferParams = std::move( other.inferParams );
     70        // inferParams = std::move( other.inferParams );
    7171        return *this;
    7272}
  • src/SynTree/Expression.cc

    r2fd9f24 r0b00df0  
    4040                        Declaration::declFromId( i->second.decl )->printShort( os, indent+1 );
    4141                        os << std::endl;
    42                         printInferParams( *i->second.inferParams, os, indent+1, level+1 );
     42                        printInferParams( i->second.expr->inferParams, os, indent+1, level+1 );
    4343                } // for
    4444        } // if
     
    4747Expression::Expression() : result( 0 ), env( 0 ) {}
    4848
    49 Expression::Expression( const Expression &other ) : BaseSyntaxNode( other ), result( maybeClone( other.result ) ), env( maybeClone( other.env ) ), extension( other.extension ), inferParams( other.inferParams ) {
    50 }
     49Expression::Expression( const Expression &other ) : BaseSyntaxNode( other ), result( maybeClone( other.result ) ), env( maybeClone( other.env ) ), extension( other.extension ), inferParams( other.inferParams ), resnSlots( other.resnSlots ) {}
    5150
    5251void Expression::spliceInferParams( Expression * other ) {
     
    5554                inferParams[p.first] = std::move( p.second );
    5655        }
     56        resnSlots.insert( resnSlots.end(), other->resnSlots.begin(), other->resnSlots.end() );
    5757}
    5858
  • src/SynTree/Expression.h

    r2fd9f24 r0b00df0  
    2121#include <memory>                 // for allocator, unique_ptr
    2222#include <string>                 // for string
     23#include <vector>                 // for vector
    2324
    2425#include "BaseSyntaxNode.h"       // for BaseSyntaxNode
     
    3839/// but subject to decay-to-pointer and type parameter renaming
    3940struct ParamEntry {
    40         ParamEntry(): decl( 0 ), actualType( 0 ), formalType( 0 ), expr( 0 ), inferParams( new InferredParams ) {}
    41         ParamEntry( UniqueId decl, Type * actualType, Type * formalType, Expression* expr ): decl( decl ), actualType( actualType ), formalType( formalType ), expr( expr ), inferParams( new InferredParams ) {}
     41        ParamEntry(): decl( 0 ), actualType( 0 ), formalType( 0 ), expr( 0 )/*, inferParams( new InferredParams )*/ {}
     42        ParamEntry( UniqueId decl, Type * actualType, Type * formalType, Expression* expr ): decl( decl ), actualType( actualType ), formalType( formalType ), expr( expr )/*, inferParams( new InferredParams )*/ {}
    4243        ParamEntry( const ParamEntry & other );
    4344        ParamEntry( ParamEntry && other );
     
    5051        Type * formalType;
    5152        Expression * expr;
    52         std::unique_ptr< InferredParams > inferParams;
     53        // std::unique_ptr< InferredParams > inferParams;
    5354};
    5455
     
    5960        TypeSubstitution * env;
    6061        bool extension = false;
    61         InferredParams inferParams;
     62        InferredParams inferParams;       ///< Post-resolution inferred parameter slots
     63        std::vector<UniqueId> resnSlots;  ///< Pre-resolution inferred parameter slots
     64       
     65        // xxx - should turn inferParams+resnSlots into a union to save some memory
    6266
    6367        Expression();
     
    7377        bool get_extension() const { return extension; }
    7478        Expression * set_extension( bool exten ) { extension = exten; return this; }
    75 
    76         InferredParams & get_inferParams() { return inferParams; }
    7779
    7880        // move other's inferParams to this
Note: See TracChangeset for help on using the changeset viewer.