Index: src/ResolvExpr/AlternativeFinder.cc =================================================================== --- src/ResolvExpr/AlternativeFinder.cc (revision b5a8ef73c79284910b1246f953b8d0bd205dbf65) +++ src/ResolvExpr/AlternativeFinder.cc (revision 4b6ef7029b7327923c4ddf07c1f9b0f8d4d1af9f) @@ -564,18 +564,18 @@ /// State to iteratively build a match of parameter expressions to arguments struct ArgPack { - AltList actuals; ///< Arguments included in this pack - TypeEnvironment env; ///< Environment for this pack - AssertionSet need; ///< Assertions outstanding for this pack - AssertionSet have; ///< Assertions found for this pack - OpenVarSet openVars; ///< Open variables for this pack - unsigned nextArg; ///< Index of next argument in arguments list - - /// Number of elements included in current tuple element (nested appropriately) - std::vector tupleEls; + AltList actuals; ///< Arguments included in this pack + TypeEnvironment env; ///< Environment for this pack + AssertionSet need; ///< Assertions outstanding for this pack + AssertionSet have; ///< Assertions found for this pack + OpenVarSet openVars; ///< Open variables for this pack + unsigned nextArg; ///< Index of next argument in arguments list + std::vector expls; ///< Exploded actuals left over from last match + unsigned nextExpl; ///< Index of next exploded alternative to use + std::vector tupleEls; /// Number of elements in current tuple element(s) ArgPack(const TypeEnvironment& env, const AssertionSet& need, const AssertionSet& have, const OpenVarSet& openVars) : actuals(), env(env), need(need), have(have), openVars(openVars), nextArg(0), - tupleEls() {} + expls(), nextExpl(0), tupleEls() {} ArgPack(const ArgPack& old, Expression* actual, TypeEnvironment&& env, @@ -623,45 +623,12 @@ actuals.emplace_back( new TupleExpr( exprs ), this->env, cost ); } + + /// Clones and adds an actual, returns this + ArgPack& withArg( Expression* expr ) { + actuals.emplace_back( expr->clone(), this->env, Cost::zero ); + if ( ! tupleEls.empty() ) ++tupleEls.back(); + return *this; + } }; - - /// Iterates a result, exploding actuals as needed. - /// add is a function that takes the same parameters as this (with the exception of add) - template - void addExplodedActual( ArgPack& result, Expression* expr, Cost cost, - std::vector& nextResults, F add ) { - Type* res = expr->get_result()->stripReferences(); - if ( TupleType* tupleType = dynamic_cast( res ) ) { - if ( TupleExpr* tupleExpr = dynamic_cast( expr ) ) { - // recursively explode tuple - for ( Expression* sexpr : tupleExpr->get_exprs() ) { - addExplodedActual( result, sexpr, cost, nextResults, add ); - cost = Cost::zero; // reset cost so not duplicated - } - } else { - // tuple type, but not tuple expr - recursively index into components. - // if expr type is reference, convert to value type - Expression* arg = expr->clone(); - if ( Tuples::maybeImpureIgnoreUnique( arg ) ) { - // expressions which may contain side effects require a single unique instance of the expression. - arg = new UniqueExpr( arg ); - } - // cast reference to value type to facilitate further explosion - if ( dynamic_cast( arg->get_result() ) ) { - arg = new CastExpr( arg, tupleType->clone() ); - } - // explode tuple by index - for ( unsigned i = 0; i < tupleType->size(); ++i ) { - TupleIndexExpr* idx = new TupleIndexExpr( arg->clone(), i ); - addExplodedActual( result, idx, cost, nextResults, add ); - cost = Cost::zero; // reset cost so not duplicated - delete idx; - } - delete arg; - } - } else { - // add non-tuple results directly - add( result, expr->clone(), cost, nextResults ); - } - } /// Instantiates an argument to match a formal, returns false if no results left @@ -716,13 +683,18 @@ // add each possible next argument for ( const Alternative& actual : args[result.nextArg] ) { - addExplodedActual( result, actual.expr, actual.cost, nextResults, - [&actual]( ArgPack& result, Expression* expr, Cost cost, - std::vector& nextResults ) { - TypeEnvironment env{ result.env }; - OpenVarSet openVars{ result.openVars }; - env.addActual( actual.env, openVars ); - nextResults.emplace_back( result, expr, std::move(env), - std::move(openVars), cost ); - } ); + ArgPack aResult = result; // copy to clone everything + // add details of actual to result + aResult.env.addActual( actual.env, aResult.openVars ); + + // explode argument + std::vector exploded; + Tuples::explode( actual, indexer, back_inserter( exploded ) ); + + // add exploded argument to tuple + for ( Alternative& aActual : exploded ) { + aResult.withArg( aActual.expr ); + } + ++aResult.nextArg; + nextResults.push_back( std::move(aResult) ); } } @@ -737,17 +709,35 @@ // iterate each current subresult - for ( ArgPack& result : results ) { - if ( result.nextArg >= args.size() ) { - // If run out of actuals, handle default values + for ( unsigned iResult = 0; iResult < results.size(); ++iResult ) { + ArgPack& result = results[iResult]; + + if ( result.nextExpl < result.expls.size() ) { + // use remainder of exploded tuple if present + const Alternative& actual = result.expls[result.nextExpl]; + result.env.addActual( actual.env, result.openVars ); + Type* actualType = actual.expr->get_result(); + + PRINT( + std::cerr << "formal type is "; + formalType->print( std::cerr ); + std::cerr << std::endl << "actual type is "; + actualType->print( std::cerr ); + std::cerr << std::endl; + ) + + if ( unify( formalType, actualType, result.env, result.need, result.have, + result.openVars, indexer ) ) { + ++result.nextExpl; + nextResults.push_back( std::move(result.withArg( actual.expr )) ); + } + + continue; + } else if ( result.nextArg >= args.size() ) { + // use default initializers if out of arguments if ( ConstantExpr* cnstExpr = getDefaultValue( initializer ) ) { if ( Constant* cnst = dynamic_cast( cnstExpr->get_constant() ) ) { - TypeEnvironment resultEnv = result.env; - AssertionSet resultNeed = result.need, resultHave = result.have; - if ( unify( formalType, cnst->get_type(), - resultEnv, resultNeed, resultHave, result.openVars, - indexer ) ) { - nextResults.emplace_back( result, cnstExpr->clone(), - std::move(resultEnv), std::move(resultNeed), - std::move(resultHave), OpenVarSet{ result.openVars } ); + if ( unify( formalType, cnst->get_type(), result.env, result.need, + result.have, result.openVars, indexer ) ) { + nextResults.push_back( std::move(result.withArg( cnstExpr )) ); } } @@ -758,30 +748,44 @@ // Check each possible next argument for ( const Alternative& actual : args[result.nextArg] ) { - addExplodedActual( result, actual.expr, actual.cost, nextResults, - [formalType,&indexer,&actual]( ArgPack& result, Expression* expr, Cost cost, - std::vector& nextResults ) { - // attempt to unify actual with parameter - TypeEnvironment resultEnv = result.env; - AssertionSet resultNeed = result.need, resultHave = result.have; - OpenVarSet resultOpenVars = result.openVars; - resultEnv.addActual( actual.env, resultOpenVars ); - Type* actualType = expr->get_result(); - - - PRINT( - std::cerr << "formal type is "; - formalType->print( std::cerr ); - std::cerr << std::endl << "actual type is "; - actualType->print( std::cerr ); - std::cerr << std::endl; - ) - - if ( unify( formalType, actualType, resultEnv, resultNeed, resultHave, - resultOpenVars, indexer ) ) { - nextResults.emplace_back( result, expr->clone(), - std::move(resultEnv), std::move(resultNeed), std::move(resultHave), - std::move(resultOpenVars), cost ); - } - } ); + ArgPack aResult = result; // copy to clone everything + // add details of actual to result + aResult.env.addActual( actual.env, aResult.openVars ); + + // explode argument + std::vector exploded; + Tuples::explode( actual, indexer, back_inserter( exploded ) ); + if ( exploded.empty() ) { + // skip empty tuple arguments + ++aResult.nextArg; + results.push_back( std::move(aResult) ); + continue; + } + + // consider only first exploded actual + const Alternative& aActual = exploded.front(); + Type* actualType = aActual.expr->get_result(); + + PRINT( + std::cerr << "formal type is "; + formalType->print( std::cerr ); + std::cerr << std::endl << "actual type is "; + actualType->print( std::cerr ); + std::cerr << std::endl; + ) + + // attempt to unify types + if ( unify( formalType, actualType, aResult.env, aResult.need, aResult.have, aResult.openVars, indexer ) ) { + // add argument + aResult.withArg( aActual.expr ); + if ( exploded.size() == 1 ) { + // argument consumed + ++aResult.nextArg; + } else { + // other parts of tuple left over + aResult.expls = std::move( exploded ); + aResult.nextExpl = 1; + } + nextResults.push_back( std::move(aResult) ); + } } } Index: src/Tuples/TupleAssignment.cc =================================================================== --- src/Tuples/TupleAssignment.cc (revision b5a8ef73c79284910b1246f953b8d0bd205dbf65) +++ src/Tuples/TupleAssignment.cc (revision 4b6ef7029b7327923c4ddf07c1f9b0f8d4d1af9f) @@ -20,5 +20,4 @@ #include // for unique_ptr, allocator_trai... #include // for string -#include #include "CodeGen/OperatorTable.h" @@ -43,4 +42,10 @@ #include "SynTree/Visitor.h" // for Visitor +#if 0 +#define PRINT(x) x +#else +#define PRINT(x) +#endif + namespace Tuples { class TupleAssignSpotter { @@ -55,6 +60,5 @@ struct Matcher { public: - Matcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList& lhs, const - ResolvExpr::AltList& rhs ); + Matcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList & alts ); virtual ~Matcher() {} virtual void match( std::list< Expression * > &out ) = 0; @@ -69,6 +73,5 @@ struct MassAssignMatcher : public Matcher { public: - MassAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList& lhs, - const ResolvExpr::AltList& rhs ) : Matcher(spotter, lhs, rhs) {} + MassAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList & alts ); virtual void match( std::list< Expression * > &out ); }; @@ -76,6 +79,5 @@ struct MultipleAssignMatcher : public Matcher { public: - MultipleAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList& lhs, - const ResolvExpr::AltList& rhs ) : Matcher(spotter, lhs, rhs) {} + MultipleAssignMatcher( TupleAssignSpotter &spot, const ResolvExpr::AltList & alts ); virtual void match( std::list< Expression * > &out ); }; @@ -89,5 +91,5 @@ bool isTuple( Expression *expr ) { if ( ! expr ) return false; - assert( expr->has_result() ); + assert( expr->result ); return dynamic_cast< TupleType * >( expr->get_result()->stripReferences() ); } @@ -114,7 +116,7 @@ void handleTupleAssignment( ResolvExpr::AlternativeFinder & currentFinder, UntypedExpr * expr, - std::vector &args ) { - TupleAssignSpotter spotter( currentFinder ); - spotter.spot( expr, args ); + std::vector &args ) { + TupleAssignSpotter spotter( currentFinder ); + spotter.spot( expr, args ); } @@ -122,74 +124,35 @@ : currentFinder(f) {} - void TupleAssignSpotter::spot( UntypedExpr * expr, - std::vector &args ) { + void TupleAssignSpotter::spot( UntypedExpr * expr, std::vector &args ) { + std::list possibilities; + combos( args.begin(), args.end(), back_inserter( possibilities ) ); + if ( NameExpr *op = dynamic_cast< NameExpr * >(expr->get_function()) ) { if ( CodeGen::isCtorDtorAssign( op->get_name() ) ) { - fname = op->get_name(); - - // AlternativeFinder will naturally handle this case case, if it's legal - if ( args.size() == 0 ) return; - - // if an assignment only takes 1 argument, that's odd, but maybe someone wrote - // the function, in which case AlternativeFinder will handle it normally - if ( args.size() == 1 && CodeGen::isAssignment( fname ) ) return; - - // look over all possible left-hand-sides - for ( ResolvExpr::Alternative& lhsAlt : args[0] ) { - // skip non-tuple LHS - if ( ! refToTuple(lhsAlt.expr) ) continue; - - // explode is aware of casts - ensure every LHS expression is sent into explode - // with a reference cast - // xxx - this seems to change the alternatives before the normal - // AlternativeFinder flow; maybe this is desired? - if ( ! dynamic_cast( lhsAlt.expr ) ) { - lhsAlt.expr = new CastExpr( lhsAlt.expr, - new ReferenceType( Type::Qualifiers(), - lhsAlt.expr->get_result()->clone() ) ); + fname = op->get_name(); + PRINT( std::cerr << "TupleAssignment: " << fname << std::endl; ) + for ( std::list::const_iterator ali = possibilities.begin(); ali != possibilities.end(); ++ali ) { + if ( ali->size() == 0 ) continue; // AlternativeFinder will natrually handle this case, if it's legal + if ( ali->size() <= 1 && CodeGen::isAssignment( op->get_name() ) ) { + // what does it mean if an assignment takes 1 argument? maybe someone defined such a function, in which case AlternativeFinder will naturally handle it + continue; } - // explode the LHS so that each field of a tuple-valued-expr is assigned - ResolvExpr::AltList lhs; - explode( lhsAlt, currentFinder.get_indexer(), back_inserter(lhs), true ); - for ( ResolvExpr::Alternative& alt : lhs ) { - // each LHS value must be a reference - some come in with a cast expression, - // if not just cast to reference here - if ( ! dynamic_cast( alt.expr->get_result() ) ) { - alt.expr = new CastExpr( alt.expr, - new ReferenceType( Type::Qualifiers(), - alt.expr->get_result()->clone() ) ); + assert( ! ali->empty() ); + // grab args 2-N and group into a TupleExpr + const ResolvExpr::Alternative & alt1 = ali->front(); + auto begin = std::next(ali->begin(), 1), end = ali->end(); + PRINT( std::cerr << "alt1 is " << alt1.expr << std::endl; ) + if ( refToTuple(alt1.expr) ) { + PRINT( std::cerr << "and is reference to tuple" << std::endl; ) + if ( isMultAssign( begin, end ) ) { + PRINT( std::cerr << "possible multiple assignment" << std::endl; ) + matcher.reset( new MultipleAssignMatcher( *this, *ali ) ); + } else { + // mass assignment + PRINT( std::cerr << "possible mass assignment" << std::endl; ) + matcher.reset( new MassAssignMatcher( *this, *ali ) ); } - } - - if ( args.size() > 2 ) { - // expand all possible RHS possibilities - // TODO build iterative version of this instead of using combos - std::vector< ResolvExpr::AltList > rhsAlts; - combos( std::next(args.begin(), 1), args.end(), - std::back_inserter( rhsAlts ) ); - for ( const ResolvExpr::AltList& rhsAlt : rhsAlts ) { - // multiple assignment - ResolvExpr::AltList rhs; - explode( rhsAlt, currentFinder.get_indexer(), - std::back_inserter(rhs), true ); - matcher.reset( new MultipleAssignMatcher( *this, lhs, rhs ) ); - match(); - } - } else { - for ( const ResolvExpr::Alternative& rhsAlt : args[1] ) { - ResolvExpr::AltList rhs; - if ( isTuple(rhsAlt.expr) ) { - // multiple assignment - explode( rhsAlt, currentFinder.get_indexer(), - std::back_inserter(rhs), true ); - matcher.reset( new MultipleAssignMatcher( *this, lhs, rhs ) ); - } else { - // mass assignment - rhs.push_back( rhsAlt ); - matcher.reset( new MassAssignMatcher( *this, lhs, rhs ) ); - } - match(); - } + match(); } } @@ -212,4 +175,9 @@ // now resolve new assignments for ( std::list< Expression * >::iterator i = new_assigns.begin(); i != new_assigns.end(); ++i ) { + PRINT( + std::cerr << "== resolving tuple assign ==" << std::endl; + std::cerr << *i << std::endl; + ) + ResolvExpr::AlternativeFinder finder( currentFinder.get_indexer(), currentFinder.get_environ() ); try { @@ -236,8 +204,37 @@ } - TupleAssignSpotter::Matcher::Matcher( TupleAssignSpotter &spotter, - const ResolvExpr::AltList &lhs, const ResolvExpr::AltList &rhs ) - : lhs(lhs), rhs(rhs), spotter(spotter), - baseCost( ResolvExpr::sumCost( lhs ) + ResolvExpr::sumCost( rhs ) ) {} + TupleAssignSpotter::Matcher::Matcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList &alts ) : spotter(spotter), baseCost( ResolvExpr::sumCost( alts ) ) { + assert( ! alts.empty() ); + // combine argument environments into combined expression environment + simpleCombineEnvironments( alts.begin(), alts.end(), compositeEnv ); + + ResolvExpr::Alternative lhsAlt = alts.front(); + // explode is aware of casts - ensure every LHS expression is sent into explode with a reference cast + if ( ! dynamic_cast< CastExpr * >( lhsAlt.expr ) ) { + lhsAlt.expr = new CastExpr( lhsAlt.expr, new ReferenceType( Type::Qualifiers(), lhsAlt.expr->get_result()->clone() ) ); + } + + // explode the lhs so that each field of the tuple-valued-expr is assigned. + explode( lhsAlt, spotter.currentFinder.get_indexer(), back_inserter(lhs), true ); + + for ( ResolvExpr::Alternative & alt : lhs ) { + // every LHS value must be a reference - some come in with a cast expression, if it doesn't just cast to reference here. + if ( ! dynamic_cast< ReferenceType * >( alt.expr->get_result() ) ) { + alt.expr = new CastExpr( alt.expr, new ReferenceType( Type::Qualifiers(), alt.expr->get_result()->clone() ) ); + } + } + } + + TupleAssignSpotter::MassAssignMatcher::MassAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList & alts ) : Matcher( spotter, alts ) { + assert( alts.size() == 1 || alts.size() == 2 ); + if ( alts.size() == 2 ) { + rhs.push_back( alts.back() ); + } + } + + TupleAssignSpotter::MultipleAssignMatcher::MultipleAssignMatcher( TupleAssignSpotter &spotter, const ResolvExpr::AltList & alts ) : Matcher( spotter, alts ) { + // explode the rhs so that each field of the tuple-valued-expr is assigned. + explode( std::next(alts.begin(), 1), alts.end(), spotter.currentFinder.get_indexer(), back_inserter(rhs), true ); + } UntypedExpr * createFunc( const std::string &fname, ObjectDecl *left, ObjectDecl *right ) { @@ -262,5 +259,5 @@ ObjectDecl * TupleAssignSpotter::Matcher::newObject( UniqueName & namer, Expression * expr ) { - assert( expr->has_result() && ! expr->get_result()->isVoid() ); + assert( expr->result && ! expr->get_result()->isVoid() ); ObjectDecl * ret = new ObjectDecl( namer.newName(), Type::StorageClasses(), LinkageSpec::Cforall, nullptr, expr->get_result()->clone(), new SingleInit( expr->clone() ) ); // if expression type is a reference, don't need to construct anything, a simple initializer is sufficient. @@ -272,4 +269,5 @@ ctorInit->accept( rm ); } + PRINT( std::cerr << "new object: " << ret << std::endl; ) return ret; }