Index: src/Parser/ParseNode.h =================================================================== --- src/Parser/ParseNode.h (revision 8c49c0e874fb58f676d7d0589d6897e2cf4e9581) +++ src/Parser/ParseNode.h (revision aefcc3b4bc74c06dfe70a46ab130a8295ab26c3c) @@ -397,8 +397,8 @@ //############################################################################## -template< typename SynTreeType, typename NodeType > -void buildList( const NodeType * firstNode, std::list< SynTreeType * > &outputList ) { +template< typename SynTreeType, typename NodeType, template< typename, typename...> class Container, typename... Args > +void buildList( const NodeType * firstNode, Container< SynTreeType *, Args... > &outputList ) { SemanticError errors; - std::back_insert_iterator< std::list< SynTreeType * > > out( outputList ); + std::back_insert_iterator< Container< SynTreeType *, Args... > > out( outputList ); const NodeType * cur = firstNode; Index: src/ResolvExpr/Alternative.cc =================================================================== --- src/ResolvExpr/Alternative.cc (revision 8c49c0e874fb58f676d7d0589d6897e2cf4e9581) +++ src/ResolvExpr/Alternative.cc (revision aefcc3b4bc74c06dfe70a46ab130a8295ab26c3c) @@ -38,4 +38,19 @@ } + Alternative::Alternative( Alternative && other ) : cost( other.cost ), cvtCost( other.cvtCost ), expr( other.expr ), env( other.env ) { + other.expr = nullptr; + } + + Alternative & Alternative::operator=( Alternative && other ) { + if ( &other == this ) return *this; + delete expr; + cost = other.cost; + cvtCost = other.cvtCost; + expr = other.expr; + env = other.env; + other.expr = nullptr; + return *this; + } + void Alternative::initialize( const Alternative &src, Alternative &dest ) { dest.cost = src.cost; Index: src/ResolvExpr/Alternative.h =================================================================== --- src/ResolvExpr/Alternative.h (revision 8c49c0e874fb58f676d7d0589d6897e2cf4e9581) +++ src/ResolvExpr/Alternative.h (revision aefcc3b4bc74c06dfe70a46ab130a8295ab26c3c) @@ -32,4 +32,6 @@ Alternative( const Alternative &other ); Alternative &operator=( const Alternative &other ); + Alternative( Alternative && other ); + Alternative &operator=( Alternative && other ); ~Alternative(); @@ -49,9 +51,12 @@ Type * res = expr->get_result(); if ( TupleType * tupleType = dynamic_cast< TupleType * > ( res ) ) { - if ( TupleExpr * tupleExpr = dynamic_cast< TupleExpr * >( alt.expr ) ) { + if ( TupleExpr * tupleExpr = dynamic_cast< TupleExpr * >( expr ) ) { + // can open tuple expr and dump its exploded components for ( Expression * expr : tupleExpr->get_exprs() ) { explodeUnique( expr, alt, out ); } } else { + // tuple type, but not tuple expr - need to refer to single instance of the argument + // expression and index into its components UniqueExpr * unq = new UniqueExpr( expr->clone() ); for ( unsigned int i = 0; i < tupleType->size(); i++ ) { @@ -63,4 +68,5 @@ } } else { + // atomic (non-tuple) type - output a clone of the expression in a new alternative *out++ = Alternative( expr->clone(), alt.env, alt.cost, alt.cvtCost ); } @@ -69,5 +75,5 @@ /// expands a tuple-valued alternative into multiple alternatives, each with a non-tuple-type template< typename OutputIterator > - void explode( Alternative &alt, OutputIterator out ) { + void explode( const Alternative &alt, OutputIterator out ) { explodeUnique( alt.expr, alt, out ); } @@ -75,6 +81,6 @@ // explode list of alternatives template< typename OutputIterator > - void explode( AltList & alts, OutputIterator out ) { - for ( Alternative & alt : alts ) { + void explode( const AltList & alts, OutputIterator out ) { + for ( const Alternative & alt : alts ) { explode( alt, out ); } Index: src/ResolvExpr/AlternativeFinder.cc =================================================================== --- src/ResolvExpr/AlternativeFinder.cc (revision 8c49c0e874fb58f676d7d0589d6897e2cf4e9581) +++ src/ResolvExpr/AlternativeFinder.cc (revision aefcc3b4bc74c06dfe70a46ab130a8295ab26c3c) @@ -371,5 +371,59 @@ } - bool AlternativeFinder::instantiateFunction( std::list< DeclarationWithType* >& formals, /*const*/ AltList &actuals, bool isVarArgs, OpenVarSet& openVars, TypeEnvironment &resultEnv, AssertionSet &resultNeed, AssertionSet &resultHave ) { + /// instantiate a single argument by matching actuals from [actualIt, actualEnd) against formalType, + /// producing expression(s) in out and their total cost in cost. + template< typename AltIterator, typename OutputIterator > + bool instantiateArgument( Type * formalType, Initializer * defaultValue, AltIterator & actualIt, AltIterator actualEnd, OpenVarSet & openVars, TypeEnvironment & resultEnv, AssertionSet & resultNeed, AssertionSet & resultHave, const SymTab::Indexer & indexer, Cost & cost, OutputIterator out ) { + if ( TupleType * tupleType = dynamic_cast< TupleType * >( formalType ) ) { + // formalType is a TupleType - group actuals into a TupleExpr whose type unifies with the TupleType + TupleExpr * tupleExpr = new TupleExpr(); + for ( Type * type : *tupleType ) { + if ( ! instantiateArgument( type, defaultValue, actualIt, actualEnd, openVars, resultEnv, resultNeed, resultHave, indexer, cost, back_inserter( tupleExpr->get_exprs() ) ) ) { + delete tupleExpr; + return false; + } + } + tupleExpr->set_result( Tuples::makeTupleType( tupleExpr->get_exprs() ) ); + *out++ = tupleExpr; + } else if ( actualIt != actualEnd ) { + // both actualType and formalType are atomic (non-tuple) types - if they unify + // then accept actual as an argument, otherwise return false (fail to instantiate argument) + Expression * actual = actualIt->expr; + Type * actualType = actual->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, openVars, indexer ) ) { + return false; + } + // move the expression from the alternative to the output iterator + *out++ = actual; + actualIt->expr = nullptr; + cost += actualIt->cost; + ++actualIt; + } else { + // End of actuals - Handle default values + if ( SingleInit *si = dynamic_cast( defaultValue )) { + // so far, only constant expressions are accepted as default values + if ( ConstantExpr *cnstexpr = dynamic_cast( si->get_value()) ) { + if ( Constant *cnst = dynamic_cast( cnstexpr->get_constant() ) ) { + if ( unify( formalType, cnst->get_type(), resultEnv, resultNeed, resultHave, openVars, indexer ) ) { + // xxx - Don't know if this is right + *out++ = cnstexpr->clone(); + return true; + } // if + } // if + } // if + } // if + return false; + } // if + return true; + } + + bool AlternativeFinder::instantiateFunction( std::list< DeclarationWithType* >& formals, const AltList &actuals, bool isVarArgs, OpenVarSet& openVars, TypeEnvironment &resultEnv, AssertionSet &resultNeed, AssertionSet &resultHave, AltList & out ) { simpleCombineEnvironments( actuals.begin(), actuals.end(), resultEnv ); // make sure we don't widen any existing bindings @@ -379,60 +433,31 @@ resultEnv.extractOpenVars( openVars ); - std::list< DeclarationWithType* >::iterator formal = formals.begin(); - - AltList newActuals; - explode( actuals, back_inserter( newActuals ) ); - - std::list< Type * > formalTypes; - std::list< Type * >::iterator formalType = formalTypes.end(); - - for ( AltList::const_iterator actualExpr = actuals.begin(); actualExpr != actuals.end(); ++actualExpr ) { - std::list< Type * > flatActualTypes; - flatten( actualExpr->expr->get_result(), back_inserter( flatActualTypes ) ); - for ( std::list< Type* >::iterator actualType = flatActualTypes.begin(); actualType != flatActualTypes.end(); ++actualType, ++formalType ) { - if ( formalType == formalTypes.end() ) { - // the type of the formal parameter may be a tuple type. To make this easier to work with, - // flatten the tuple type and traverse the resulting list of types, incrementing the formal - // iterator once its types have been extracted. Once a particular formal parameter's type has - // been exhausted load the next formal parameter's type. - if ( formal == formals.end() ) { - return isVarArgs; - } - formalTypes.clear(); - flatten( (*formal)->get_type(), back_inserter( formalTypes ) ); - formalType = formalTypes.begin(); - ++formal; - } - 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, openVars, indexer ) ) { - return false; - } - } - } - - // xxx - a tuple type was not completely matched - // partially handle the tuple with default arguments?? - if ( formalType != formalTypes.end() ) return false; - - // Handling of default values - while ( formal != formals.end() ) { - if ( ObjectDecl *od = dynamic_cast( *formal ) ) - if ( SingleInit *si = dynamic_cast( od->get_init() )) - // so far, only constant expressions are accepted as default values - if ( ConstantExpr *cnstexpr = dynamic_cast( si->get_value()) ) - if ( Constant *cnst = dynamic_cast( cnstexpr->get_constant() ) ) - if ( unify( (*formal)->get_type(), cnst->get_type(), resultEnv, resultNeed, resultHave, openVars, indexer ) ) { - // XXX Don't know if this is right - actuals.push_back( Alternative( cnstexpr->clone(), env, Cost::zero ) ); - formal++; - if ( formal == formals.end()) break; - } - return false; + // flatten actuals so that each actual has an atomic (non-tuple) type + AltList exploded; + explode( actuals, back_inserter( exploded ) ); + + AltList::iterator actualExpr = exploded.begin(); + AltList::iterator actualEnd = exploded.end(); + for ( DeclarationWithType * formal : formals ) { + // match flattened actuals with formal parameters - actuals will be grouped to match + // with formals as appropriate + Cost cost; + std::list< Expression * > newExprs; + ObjectDecl * obj = safe_dynamic_cast< ObjectDecl * >( formal ); + if ( ! instantiateArgument( obj->get_type(), obj->get_init(), actualExpr, actualEnd, openVars, resultEnv, resultNeed, resultHave, indexer, cost, back_inserter( newExprs ) ) ) { + deleteAll( newExprs ); + return false; + } + // success - produce argument as a new alternative + assert( newExprs.size() == 1 ); + out.push_back( Alternative( newExprs.front(), resultEnv, cost ) ); + } + if ( actualExpr != actualEnd ) { + // there are still actuals remaining, but we've run out of formal parameters to match against + // this is okay only if the function is variadic + if ( ! isVarArgs ) { + return false; + } + out.splice( out.end(), exploded, actualExpr, actualEnd ); } return true; @@ -565,13 +590,14 @@ template< typename OutputIterator > - void AlternativeFinder::makeFunctionAlternatives( const Alternative &func, FunctionType *funcType, AltList &actualAlt, OutputIterator out ) { + void AlternativeFinder::makeFunctionAlternatives( const Alternative &func, FunctionType *funcType, const AltList &actualAlt, OutputIterator out ) { OpenVarSet openVars; AssertionSet resultNeed, resultHave; TypeEnvironment resultEnv; makeUnifiableVars( funcType, openVars, resultNeed ); - if ( instantiateFunction( funcType->get_parameters(), actualAlt, funcType->get_isVarArgs(), openVars, resultEnv, resultNeed, resultHave ) ) { + AltList instantiatedActuals; // filled by instantiate function + if ( instantiateFunction( funcType->get_parameters(), actualAlt, funcType->get_isVarArgs(), openVars, resultEnv, resultNeed, resultHave, instantiatedActuals ) ) { ApplicationExpr *appExpr = new ApplicationExpr( func.expr->clone() ); - Alternative newAlt( appExpr, resultEnv, sumCost( actualAlt ) ); - makeExprList( actualAlt, appExpr->get_args() ); + Alternative newAlt( appExpr, resultEnv, sumCost( instantiatedActuals ) ); + makeExprList( instantiatedActuals, appExpr->get_args() ); PRINT( std::cerr << "need assertions:" << std::endl; Index: src/ResolvExpr/AlternativeFinder.h =================================================================== --- src/ResolvExpr/AlternativeFinder.h (revision 8c49c0e874fb58f676d7d0589d6897e2cf4e9581) +++ src/ResolvExpr/AlternativeFinder.h (revision aefcc3b4bc74c06dfe70a46ab130a8295ab26c3c) @@ -78,7 +78,7 @@ /// Adds alternatives for offsetof expressions, given the base type and name of the member template< typename StructOrUnionType > void addOffsetof( StructOrUnionType *aggInst, const std::string &name ); - bool instantiateFunction( std::list< DeclarationWithType* >& formals, /*const*/ AltList &actuals, bool isVarArgs, OpenVarSet& openVars, TypeEnvironment &resultEnv, AssertionSet &resultNeed, AssertionSet &resultHave ); + bool instantiateFunction( std::list< DeclarationWithType* >& formals, const AltList &actuals, bool isVarArgs, OpenVarSet& openVars, TypeEnvironment &resultEnv, AssertionSet &resultNeed, AssertionSet &resultHave, AltList & out ); template< typename OutputIterator > - void makeFunctionAlternatives( const Alternative &func, FunctionType *funcType, AltList &actualAlt, OutputIterator out ); + void makeFunctionAlternatives( const Alternative &func, FunctionType *funcType, const AltList &actualAlt, OutputIterator out ); template< typename OutputIterator > void inferParameters( const AssertionSet &need, AssertionSet &have, const Alternative &newAlt, OpenVarSet &openVars, OutputIterator out ); Index: src/ResolvExpr/Unify.cc =================================================================== --- src/ResolvExpr/Unify.cc (revision 8c49c0e874fb58f676d7d0589d6897e2cf4e9581) +++ src/ResolvExpr/Unify.cc (revision aefcc3b4bc74c06dfe70a46ab130a8295ab26c3c) @@ -416,5 +416,5 @@ void markAssertions( AssertionSet &assertion1, AssertionSet &assertion2, Type *type ) { - for ( Type::ForallList::const_iterator tyvar = type->get_forall().begin(); tyvar != type->get_forall().end(); ++tyvar ) { + for ( std::list< TypeDecl* >::const_iterator tyvar = type->get_forall().begin(); tyvar != type->get_forall().end(); ++tyvar ) { for ( std::list< DeclarationWithType* >::const_iterator assert = (*tyvar)->get_assertions().begin(); assert != (*tyvar)->get_assertions().end(); ++assert ) { markAssertionSet( assertion1, *assert ); Index: src/Tuples/TupleExpansion.cc =================================================================== --- src/Tuples/TupleExpansion.cc (revision 8c49c0e874fb58f676d7d0589d6897e2cf4e9581) +++ src/Tuples/TupleExpansion.cc (revision aefcc3b4bc74c06dfe70a46ab130a8295ab26c3c) @@ -72,8 +72,10 @@ } - void expandTuples( std::list< Declaration * > & translationUnit ) { + void expandUniqueExpr( std::list< Declaration * > & translationUnit ) { UniqueExprExpander unqExpander; unqExpander.mutateDeclarationList( translationUnit ); + } + void expandTuples( std::list< Declaration * > & translationUnit ) { TupleAssignExpander assnExpander; mutateAll( translationUnit, assnExpander ); Index: src/Tuples/Tuples.h =================================================================== --- src/Tuples/Tuples.h (revision 8c49c0e874fb58f676d7d0589d6897e2cf4e9581) +++ src/Tuples/Tuples.h (revision aefcc3b4bc74c06dfe70a46ab130a8295ab26c3c) @@ -32,4 +32,6 @@ void expandTuples( std::list< Declaration * > & translationUnit ); + void expandUniqueExpr( std::list< Declaration * > & translationUnit ); + TupleType * makeTupleType( const std::list< Expression * > & exprs ); } // namespace Tuples Index: src/main.cc =================================================================== --- src/main.cc (revision 8c49c0e874fb58f676d7d0589d6897e2cf4e9581) +++ src/main.cc (revision aefcc3b4bc74c06dfe70a46ab130a8295ab26c3c) @@ -250,4 +250,7 @@ } // if + OPTPRINT( "expandUniqueExpr" ); // xxx - is this the right place for this? + Tuples::expandUniqueExpr( translationUnit ); + // fix ObjectDecl - replaces ConstructorInit nodes OPTPRINT( "fixInit" )