Changeset 4b6ef70


Ignore:
Timestamp:
Oct 20, 2017, 11:45:53 AM (4 years ago)
Author:
Aaron Moss <a3moss@…>
Branches:
aaron-thesis, arm-eh, cleanup-dtors, deferred_resn, demangler, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, resolv-new, with_gc
Children:
1fdfc23
Parents:
b5a8ef7
Message:

Fix one tuple bug in resolver refactor

Location:
src
Files:
2 edited

Legend:

Unmodified
Added
Removed
  • src/ResolvExpr/AlternativeFinder.cc

    rb5a8ef7 r4b6ef70  
    564564        /// State to iteratively build a match of parameter expressions to arguments
    565565        struct ArgPack {
    566                 AltList actuals;      ///< Arguments included in this pack
    567                 TypeEnvironment env;  ///< Environment for this pack
    568                 AssertionSet need;    ///< Assertions outstanding for this pack
    569                 AssertionSet have;    ///< Assertions found for this pack
    570                 OpenVarSet openVars;  ///< Open variables for this pack
    571                 unsigned nextArg;     ///< Index of next argument in arguments list
    572                
    573                 /// Number of elements included in current tuple element (nested appropriately)
    574                 std::vector<unsigned> tupleEls;
     566                AltList actuals;                 ///< Arguments included in this pack
     567                TypeEnvironment env;             ///< Environment for this pack
     568                AssertionSet need;               ///< Assertions outstanding for this pack
     569                AssertionSet have;               ///< Assertions found for this pack
     570                OpenVarSet openVars;             ///< Open variables for this pack
     571                unsigned nextArg;                ///< Index of next argument in arguments list
     572                std::vector<Alternative> expls;  ///< Exploded actuals left over from last match
     573                unsigned nextExpl;               ///< Index of next exploded alternative to use
     574                std::vector<unsigned> tupleEls;  /// Number of elements in current tuple element(s)
    575575
    576576                ArgPack(const TypeEnvironment& env, const AssertionSet& need, const AssertionSet& have,
    577577                                const OpenVarSet& openVars)
    578578                        : actuals(), env(env), need(need), have(have), openVars(openVars), nextArg(0),
    579                           tupleEls() {}
     579                          expls(), nextExpl(0), tupleEls() {}
    580580               
    581581                ArgPack(const ArgPack& old, Expression* actual, TypeEnvironment&& env,
     
    623623                        actuals.emplace_back( new TupleExpr( exprs ), this->env, cost );
    624624                }
     625
     626                /// Clones and adds an actual, returns this
     627                ArgPack& withArg( Expression* expr ) {
     628                        actuals.emplace_back( expr->clone(), this->env, Cost::zero );
     629                        if ( ! tupleEls.empty() ) ++tupleEls.back();
     630                        return *this;
     631                }
    625632        };
    626 
    627         /// Iterates a result, exploding actuals as needed.
    628         /// add is a function that takes the same parameters as this (with the exception of add)
    629         template<typename F>
    630         void addExplodedActual( ArgPack& result, Expression* expr, Cost cost,
    631                         std::vector<ArgPack>& nextResults, F add ) {
    632                 Type* res = expr->get_result()->stripReferences();
    633                 if ( TupleType* tupleType = dynamic_cast<TupleType*>( res ) ) {
    634                         if ( TupleExpr* tupleExpr = dynamic_cast<TupleExpr*>( expr ) ) {
    635                                 // recursively explode tuple
    636                                 for ( Expression* sexpr : tupleExpr->get_exprs() ) {
    637                                         addExplodedActual( result, sexpr, cost, nextResults, add );
    638                                         cost = Cost::zero; // reset cost so not duplicated
    639                                 }
    640                         } else {
    641                                 // tuple type, but not tuple expr - recursively index into components.
    642                                 // if expr type is reference, convert to value type
    643                                 Expression* arg = expr->clone();
    644                                 if ( Tuples::maybeImpureIgnoreUnique( arg ) ) {
    645                                         // expressions which may contain side effects require a single unique instance of the expression.
    646                                         arg = new UniqueExpr( arg );
    647                                 }
    648                                 // cast reference to value type to facilitate further explosion
    649                                 if ( dynamic_cast<ReferenceType*>( arg->get_result() ) ) {
    650                                         arg = new CastExpr( arg, tupleType->clone() );
    651                                 }
    652                                 // explode tuple by index
    653                                 for ( unsigned i = 0; i < tupleType->size(); ++i ) {
    654                                         TupleIndexExpr* idx = new TupleIndexExpr( arg->clone(), i );
    655                                         addExplodedActual( result, idx, cost, nextResults, add );
    656                                         cost = Cost::zero; // reset cost so not duplicated
    657                                         delete idx;
    658                                 }
    659                                 delete arg;
    660                         }
    661                 } else {
    662                         // add non-tuple results directly
    663                         add( result, expr->clone(), cost, nextResults );
    664                 }
    665         }
    666633
    667634        /// Instantiates an argument to match a formal, returns false if no results left
     
    716683                                        // add each possible next argument
    717684                                        for ( const Alternative& actual : args[result.nextArg] ) {
    718                                                 addExplodedActual( result, actual.expr, actual.cost, nextResults,
    719                                                         [&actual]( ArgPack& result, Expression* expr, Cost cost,
    720                                                                         std::vector<ArgPack>& nextResults ) {
    721                                                                 TypeEnvironment env{ result.env };
    722                                                                 OpenVarSet openVars{ result.openVars };
    723                                                                 env.addActual( actual.env, openVars );
    724                                                                 nextResults.emplace_back( result, expr, std::move(env),
    725                                                                         std::move(openVars), cost );
    726                                                         } );
     685                                                ArgPack aResult = result;  // copy to clone everything
     686                                                // add details of actual to result
     687                                                aResult.env.addActual( actual.env, aResult.openVars );
     688               
     689                                                // explode argument
     690                                                std::vector<Alternative> exploded;
     691                                                Tuples::explode( actual, indexer, back_inserter( exploded ) );
     692                                               
     693                                                // add exploded argument to tuple
     694                                                for ( Alternative& aActual : exploded ) {
     695                                                        aResult.withArg( aActual.expr );
     696                                                }
     697                                                ++aResult.nextArg;
     698                                                nextResults.push_back( std::move(aResult) );
    727699                                        }
    728700                                }
     
    737709               
    738710                // iterate each current subresult
    739                 for ( ArgPack& result : results ) {
    740                         if ( result.nextArg >= args.size() ) {
    741                                 // If run out of actuals, handle default values
     711                for ( unsigned iResult = 0; iResult < results.size(); ++iResult ) {
     712                        ArgPack& result = results[iResult];
     713
     714                        if ( result.nextExpl < result.expls.size() ) {
     715                                // use remainder of exploded tuple if present
     716                                const Alternative& actual = result.expls[result.nextExpl];
     717                                result.env.addActual( actual.env, result.openVars );
     718                                Type* actualType = actual.expr->get_result();
     719
     720                                PRINT(
     721                                        std::cerr << "formal type is ";
     722                                        formalType->print( std::cerr );
     723                                        std::cerr << std::endl << "actual type is ";
     724                                        actualType->print( std::cerr );
     725                                        std::cerr << std::endl;
     726                                )
     727                               
     728                                if ( unify( formalType, actualType, result.env, result.need, result.have,
     729                                                result.openVars, indexer ) ) {
     730                                        ++result.nextExpl;
     731                                        nextResults.push_back( std::move(result.withArg( actual.expr )) );
     732                                }
     733
     734                                continue;
     735                        } else if ( result.nextArg >= args.size() ) {
     736                                // use default initializers if out of arguments
    742737                                if ( ConstantExpr* cnstExpr = getDefaultValue( initializer ) ) {
    743738                                        if ( Constant* cnst = dynamic_cast<Constant*>( cnstExpr->get_constant() ) ) {
    744                                                 TypeEnvironment resultEnv = result.env;
    745                                                 AssertionSet resultNeed = result.need, resultHave = result.have;
    746                                                 if ( unify( formalType, cnst->get_type(),
    747                                                                 resultEnv, resultNeed, resultHave, result.openVars,
    748                                                                 indexer ) ) {
    749                                                         nextResults.emplace_back( result, cnstExpr->clone(),
    750                                                                 std::move(resultEnv), std::move(resultNeed),
    751                                                                 std::move(resultHave), OpenVarSet{ result.openVars } );
     739                                                if ( unify( formalType, cnst->get_type(), result.env, result.need,
     740                                                                result.have, result.openVars, indexer ) ) {
     741                                                        nextResults.push_back( std::move(result.withArg( cnstExpr )) );
    752742                                                }
    753743                                        }
     
    758748                        // Check each possible next argument
    759749                        for ( const Alternative& actual : args[result.nextArg] ) {
    760                                 addExplodedActual( result, actual.expr, actual.cost, nextResults,
    761                                         [formalType,&indexer,&actual]( ArgPack& result, Expression* expr, Cost cost,
    762                                                         std::vector<ArgPack>& nextResults ) {
    763                                                 // attempt to unify actual with parameter
    764                                                 TypeEnvironment resultEnv = result.env;
    765                                                 AssertionSet resultNeed = result.need, resultHave = result.have;
    766                                                 OpenVarSet resultOpenVars = result.openVars;
    767                                                 resultEnv.addActual( actual.env, resultOpenVars );
    768                                                 Type* actualType = expr->get_result();
    769 
    770 
    771                                                 PRINT(
    772                                                         std::cerr << "formal type is ";
    773                                                         formalType->print( std::cerr );
    774                                                         std::cerr << std::endl << "actual type is ";
    775                                                         actualType->print( std::cerr );
    776                                                         std::cerr << std::endl;
    777                                                 )
    778 
    779                                                 if ( unify( formalType, actualType, resultEnv, resultNeed, resultHave,
    780                                                                 resultOpenVars, indexer ) ) {
    781                                                         nextResults.emplace_back( result, expr->clone(),
    782                                                                 std::move(resultEnv), std::move(resultNeed), std::move(resultHave),
    783                                                                 std::move(resultOpenVars), cost );
    784                                                 }
    785                                         } );
     750                                ArgPack aResult = result;  // copy to clone everything
     751                                // add details of actual to result
     752                                aResult.env.addActual( actual.env, aResult.openVars );
     753
     754                                // explode argument
     755                                std::vector<Alternative> exploded;
     756                                Tuples::explode( actual, indexer, back_inserter( exploded ) );
     757                                if ( exploded.empty() ) {
     758                                        // skip empty tuple arguments
     759                                        ++aResult.nextArg;
     760                                        results.push_back( std::move(aResult) );
     761                                        continue;
     762                                }
     763
     764                                // consider only first exploded actual
     765                                const Alternative& aActual = exploded.front();
     766                                Type* actualType = aActual.expr->get_result();
     767
     768                                PRINT(
     769                                        std::cerr << "formal type is ";
     770                                        formalType->print( std::cerr );
     771                                        std::cerr << std::endl << "actual type is ";
     772                                        actualType->print( std::cerr );
     773                                        std::cerr << std::endl;
     774                                )
     775
     776                                // attempt to unify types
     777                                if ( unify( formalType, actualType, aResult.env, aResult.need, aResult.have, aResult.openVars, indexer ) ) {
     778                                        // add argument
     779                                        aResult.withArg( aActual.expr );
     780                                        if ( exploded.size() == 1 ) {
     781                                                // argument consumed
     782                                                ++aResult.nextArg;
     783                                        } else {
     784                                                // other parts of tuple left over
     785                                                aResult.expls = std::move( exploded );
     786                                                aResult.nextExpl = 1;
     787                                        }
     788                                        nextResults.push_back( std::move(aResult) );
     789                                }
    786790                        }
    787791                }
  • src/Tuples/TupleAssignment.cc

    rb5a8ef7 r4b6ef70  
    2020#include <memory>                          // for unique_ptr, allocator_trai...
    2121#include <string>                          // for string
    22 #include <vector>
    2322
    2423#include "CodeGen/OperatorTable.h"
     
    4342#include "SynTree/Visitor.h"               // for Visitor
    4443
     44#if 0
     45#define PRINT(x) x
     46#else
     47#define PRINT(x)
     48#endif
     49
    4550namespace Tuples {
    4651        class TupleAssignSpotter {
     
    5560                struct Matcher {
    5661                  public:
    57                         Matcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList& lhs, const
    58                                 ResolvExpr::AltList& rhs );
     62                        Matcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList & alts );
    5963                        virtual ~Matcher() {}
    6064                        virtual void match( std::list< Expression * > &out ) = 0;
     
    6973                struct MassAssignMatcher : public Matcher {
    7074                  public:
    71                         MassAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList& lhs,
    72                                 const ResolvExpr::AltList& rhs ) : Matcher(spotter, lhs, rhs) {}
     75                        MassAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList & alts );
    7376                        virtual void match( std::list< Expression * > &out );
    7477                };
     
    7679                struct MultipleAssignMatcher : public Matcher {
    7780                  public:
    78                         MultipleAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList& lhs,
    79                                 const ResolvExpr::AltList& rhs ) : Matcher(spotter, lhs, rhs) {}
     81                        MultipleAssignMatcher( TupleAssignSpotter &spot, const ResolvExpr::AltList & alts );
    8082                        virtual void match( std::list< Expression * > &out );
    8183                };
     
    8991        bool isTuple( Expression *expr ) {
    9092                if ( ! expr ) return false;
    91                 assert( expr->has_result() );
     93                assert( expr->result );
    9294                return dynamic_cast< TupleType * >( expr->get_result()->stripReferences() );
    9395        }
     
    114116
    115117        void handleTupleAssignment( ResolvExpr::AlternativeFinder & currentFinder, UntypedExpr * expr,
    116                                 std::vector<ResolvExpr::AlternativeFinder> &args ) {
    117                 TupleAssignSpotter spotter( currentFinder );
    118                 spotter.spot( expr, args );
     118                std::vector<ResolvExpr::AlternativeFinder> &args ) {
     119        TupleAssignSpotter spotter( currentFinder );
     120        spotter.spot( expr, args );
    119121        }
    120122
     
    122124                : currentFinder(f) {}
    123125
    124         void TupleAssignSpotter::spot( UntypedExpr * expr,
    125                         std::vector<ResolvExpr::AlternativeFinder> &args ) {
     126        void TupleAssignSpotter::spot( UntypedExpr * expr, std::vector<ResolvExpr::AlternativeFinder> &args ) {
     127                std::list<ResolvExpr::AltList> possibilities;
     128                combos( args.begin(), args.end(), back_inserter( possibilities ) );
     129
    126130                if (  NameExpr *op = dynamic_cast< NameExpr * >(expr->get_function()) ) {
    127131                        if ( CodeGen::isCtorDtorAssign( op->get_name() ) ) {
    128                                 fname = op->get_name();
    129 
    130                                 // AlternativeFinder will naturally handle this case case, if it's legal
    131                                 if ( args.size() == 0 ) return;
    132 
    133                                 // if an assignment only takes 1 argument, that's odd, but maybe someone wrote
    134                                 // the function, in which case AlternativeFinder will handle it normally
    135                                 if ( args.size() == 1 && CodeGen::isAssignment( fname ) ) return;
    136 
    137                                 // look over all possible left-hand-sides
    138                                 for ( ResolvExpr::Alternative& lhsAlt : args[0] ) {
    139                                         // skip non-tuple LHS
    140                                         if ( ! refToTuple(lhsAlt.expr) ) continue;
    141 
    142                                         // explode is aware of casts - ensure every LHS expression is sent into explode
    143                                         // with a reference cast
    144                                         // xxx - this seems to change the alternatives before the normal
    145                                         //  AlternativeFinder flow; maybe this is desired?
    146                                         if ( ! dynamic_cast<CastExpr*>( lhsAlt.expr ) ) {
    147                                                 lhsAlt.expr = new CastExpr( lhsAlt.expr,
    148                                                                 new ReferenceType( Type::Qualifiers(),
    149                                                                         lhsAlt.expr->get_result()->clone() ) );
     132                               fname = op->get_name();
     133                                PRINT( std::cerr << "TupleAssignment: " << fname << std::endl; )
     134                                for ( std::list<ResolvExpr::AltList>::const_iterator ali = possibilities.begin(); ali != possibilities.end(); ++ali ) {
     135                                        if ( ali->size() == 0 ) continue; // AlternativeFinder will natrually handle this case, if it's legal
     136                                        if ( ali->size() <= 1 && CodeGen::isAssignment( op->get_name() ) ) {
     137                                                // what does it mean if an assignment takes 1 argument? maybe someone defined such a function, in which case AlternativeFinder will naturally handle it
     138                                                continue;
    150139                                        }
    151140
    152                                         // explode the LHS so that each field of a tuple-valued-expr is assigned
    153                                         ResolvExpr::AltList lhs;
    154                                         explode( lhsAlt, currentFinder.get_indexer(), back_inserter(lhs), true );
    155                                         for ( ResolvExpr::Alternative& alt : lhs ) {
    156                                                 // each LHS value must be a reference - some come in with a cast expression,
    157                                                 // if not just cast to reference here
    158                                                 if ( ! dynamic_cast<ReferenceType*>( alt.expr->get_result() ) ) {
    159                                                         alt.expr = new CastExpr( alt.expr,
    160                                                                 new ReferenceType( Type::Qualifiers(),
    161                                                                         alt.expr->get_result()->clone() ) );
     141                                        assert( ! ali->empty() );
     142                                        // grab args 2-N and group into a TupleExpr
     143                                        const ResolvExpr::Alternative & alt1 = ali->front();
     144                                        auto begin = std::next(ali->begin(), 1), end = ali->end();
     145                                        PRINT( std::cerr << "alt1 is " << alt1.expr << std::endl; )
     146                                        if ( refToTuple(alt1.expr) ) {
     147                                                PRINT( std::cerr << "and is reference to tuple" << std::endl; )
     148                                                if ( isMultAssign( begin, end ) ) {
     149                                                        PRINT( std::cerr << "possible multiple assignment" << std::endl; )
     150                                                        matcher.reset( new MultipleAssignMatcher( *this, *ali ) );
     151                                                } else {
     152                                                        // mass assignment
     153                                                        PRINT( std::cerr << "possible mass assignment" << std::endl; )
     154                                                        matcher.reset( new MassAssignMatcher( *this,  *ali ) );
    162155                                                }
    163                                         }
    164 
    165                                         if ( args.size() > 2 ) {
    166                                                 // expand all possible RHS possibilities
    167                                                 // TODO build iterative version of this instead of using combos
    168                                                 std::vector< ResolvExpr::AltList > rhsAlts;
    169                                                 combos( std::next(args.begin(), 1), args.end(),
    170                                                         std::back_inserter( rhsAlts ) );
    171                                                 for ( const ResolvExpr::AltList& rhsAlt : rhsAlts ) {
    172                                                         // multiple assignment
    173                                                         ResolvExpr::AltList rhs;
    174                                                         explode( rhsAlt, currentFinder.get_indexer(),
    175                                                                 std::back_inserter(rhs), true );
    176                                                         matcher.reset( new MultipleAssignMatcher( *this, lhs, rhs ) );
    177                                                         match();
    178                                                 }
    179                                         } else {
    180                                                 for ( const ResolvExpr::Alternative& rhsAlt : args[1] ) {
    181                                                         ResolvExpr::AltList rhs;
    182                                                         if ( isTuple(rhsAlt.expr) ) {
    183                                                                 // multiple assignment
    184                                                                 explode( rhsAlt, currentFinder.get_indexer(), 
    185                                                                         std::back_inserter(rhs), true );
    186                                                                 matcher.reset( new MultipleAssignMatcher( *this, lhs, rhs ) );
    187                                                         } else {
    188                                                                 // mass assignment
    189                                                                 rhs.push_back( rhsAlt );
    190                                                                 matcher.reset( new MassAssignMatcher( *this, lhs, rhs ) );
    191                                                         }
    192                                                         match();
    193                                                 }
     156                                                match();
    194157                                        }
    195158                                }
     
    212175                // now resolve new assignments
    213176                for ( std::list< Expression * >::iterator i = new_assigns.begin(); i != new_assigns.end(); ++i ) {
     177                        PRINT(
     178                                std::cerr << "== resolving tuple assign ==" << std::endl;
     179                                std::cerr << *i << std::endl;
     180                        )
     181
    214182                        ResolvExpr::AlternativeFinder finder( currentFinder.get_indexer(), currentFinder.get_environ() );
    215183                        try {
     
    236204        }
    237205
    238         TupleAssignSpotter::Matcher::Matcher( TupleAssignSpotter &spotter,
    239                 const ResolvExpr::AltList &lhs, const ResolvExpr::AltList &rhs )
    240         : lhs(lhs), rhs(rhs), spotter(spotter),
    241           baseCost( ResolvExpr::sumCost( lhs ) + ResolvExpr::sumCost( rhs ) ) {}
     206        TupleAssignSpotter::Matcher::Matcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList &alts ) : spotter(spotter), baseCost( ResolvExpr::sumCost( alts ) ) {
     207                assert( ! alts.empty() );
     208                // combine argument environments into combined expression environment
     209                simpleCombineEnvironments( alts.begin(), alts.end(), compositeEnv );
     210
     211                ResolvExpr::Alternative lhsAlt = alts.front();
     212                // explode is aware of casts - ensure every LHS expression is sent into explode with a reference cast
     213                if ( ! dynamic_cast< CastExpr * >( lhsAlt.expr ) ) {
     214                        lhsAlt.expr = new CastExpr( lhsAlt.expr, new ReferenceType( Type::Qualifiers(), lhsAlt.expr->get_result()->clone() ) );
     215                }
     216
     217                // explode the lhs so that each field of the tuple-valued-expr is assigned.
     218                explode( lhsAlt, spotter.currentFinder.get_indexer(), back_inserter(lhs), true );
     219
     220                for ( ResolvExpr::Alternative & alt : lhs ) {
     221                        // every LHS value must be a reference - some come in with a cast expression, if it doesn't just cast to reference here.
     222                        if ( ! dynamic_cast< ReferenceType * >( alt.expr->get_result() ) ) {
     223                                alt.expr = new CastExpr( alt.expr, new ReferenceType( Type::Qualifiers(), alt.expr->get_result()->clone() ) );
     224                        }
     225                }
     226        }
     227
     228        TupleAssignSpotter::MassAssignMatcher::MassAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList & alts ) : Matcher( spotter, alts ) {
     229                assert( alts.size() == 1 || alts.size() == 2 );
     230                if ( alts.size() == 2 ) {
     231                        rhs.push_back( alts.back() );
     232                }
     233        }
     234
     235        TupleAssignSpotter::MultipleAssignMatcher::MultipleAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList & alts ) : Matcher( spotter, alts ) {
     236                // explode the rhs so that each field of the tuple-valued-expr is assigned.
     237                explode( std::next(alts.begin(), 1), alts.end(), spotter.currentFinder.get_indexer(), back_inserter(rhs), true );
     238        }
    242239
    243240        UntypedExpr * createFunc( const std::string &fname, ObjectDecl *left, ObjectDecl *right ) {
     
    262259
    263260        ObjectDecl * TupleAssignSpotter::Matcher::newObject( UniqueName & namer, Expression * expr ) {
    264                 assert( expr->has_result() && ! expr->get_result()->isVoid() );
     261                assert( expr->result && ! expr->get_result()->isVoid() );
    265262                ObjectDecl * ret = new ObjectDecl( namer.newName(), Type::StorageClasses(), LinkageSpec::Cforall, nullptr, expr->get_result()->clone(), new SingleInit( expr->clone() ) );
    266263                // if expression type is a reference, don't need to construct anything, a simple initializer is sufficient.
     
    272269                        ctorInit->accept( rm );
    273270                }
     271                PRINT( std::cerr << "new object: " << ret << std::endl; )
    274272                return ret;
    275273        }
Note: See TracChangeset for help on using the changeset viewer.