Index: src/ResolvExpr/Alternative.cc =================================================================== --- src/ResolvExpr/Alternative.cc (revision 73a5cadbd1f793f9d7fa1cdf290ae5115ec37051) +++ src/ResolvExpr/Alternative.cc (revision bd4f2e9b269f4ba6094575b830cab685e3a1d075) @@ -18,4 +18,5 @@ #include // for operator<<, ostream, basic_o... #include // for operator<<, char_traits, string +#include // for move #include "Common/utility.h" // for maybeClone @@ -81,4 +82,18 @@ os << std::endl; } + + void splice( AltList& dst, AltList& src ) { + dst.reserve( dst.size() + src.size() ); + for ( Alternative& alt : src ) { + dst.push_back( std::move(alt) ); + } + src.clear(); + } + + void spliceBegin( AltList& dst, AltList& src ) { + splice( src, dst ); + dst.swap( src ); + } + } // namespace ResolvExpr Index: src/ResolvExpr/Alternative.h =================================================================== --- src/ResolvExpr/Alternative.h (revision 73a5cadbd1f793f9d7fa1cdf290ae5115ec37051) +++ src/ResolvExpr/Alternative.h (revision bd4f2e9b269f4ba6094575b830cab685e3a1d075) @@ -17,5 +17,5 @@ #include // for ostream -#include // for list +#include // for vector #include "Cost.h" // for Cost @@ -25,8 +25,4 @@ namespace ResolvExpr { - struct Alternative; - - typedef std::list< Alternative > AltList; - struct Alternative { Alternative(); @@ -46,4 +42,12 @@ TypeEnvironment env; }; + + typedef std::vector< Alternative > AltList; + + /// Moves all elements from src to the end of dst + void splice( AltList& dst, AltList& src ); + + /// Moves all elements from src to the beginning of dst + void spliceBegin( AltList& dst, AltList& src ); } // namespace ResolvExpr Index: src/ResolvExpr/AlternativeFinder.cc =================================================================== --- src/ResolvExpr/AlternativeFinder.cc (revision 73a5cadbd1f793f9d7fa1cdf290ae5115ec37051) +++ src/ResolvExpr/AlternativeFinder.cc (revision bd4f2e9b269f4ba6094575b830cab685e3a1d075) @@ -194,7 +194,7 @@ printAlts( alternatives, std::cerr ); ) - AltList::iterator oldBegin = alternatives.begin(); - pruneAlternatives( alternatives.begin(), alternatives.end(), front_inserter( alternatives ) ); - if ( failFast && alternatives.begin() == oldBegin ) { + AltList pruned; + pruneAlternatives( alternatives.begin(), alternatives.end(), back_inserter( pruned ) ); + if ( failFast && pruned.empty() ) { std::ostringstream stream; AltList winners; @@ -206,5 +206,5 @@ throw SemanticError( stream.str() ); } - alternatives.erase( oldBegin, alternatives.end() ); + alternatives = move(pruned); PRINT( std::cerr << "there are " << oldsize << " alternatives before elimination" << std::endl; @@ -1119,9 +1119,9 @@ // compute conversionsion costs - for ( AltList::iterator withFunc = candidates.begin(); withFunc != candidates.end(); ++withFunc ) { - Cost cvtCost = computeApplicationConversionCost( *withFunc, indexer ); + for ( Alternative& withFunc : candidates ) { + Cost cvtCost = computeApplicationConversionCost( withFunc, indexer ); PRINT( - ApplicationExpr *appExpr = strict_dynamic_cast< ApplicationExpr* >( withFunc->expr ); + ApplicationExpr *appExpr = strict_dynamic_cast< ApplicationExpr* >( withFunc.expr ); PointerType *pointer = strict_dynamic_cast< PointerType* >( appExpr->get_function()->get_result() ); FunctionType *function = strict_dynamic_cast< FunctionType* >( pointer->get_base() ); @@ -1132,15 +1132,14 @@ printAll( appExpr->get_args(), std::cerr, 8 ); std::cerr << "bindings are:" << std::endl; - withFunc->env.print( std::cerr, 8 ); + withFunc.env.print( std::cerr, 8 ); std::cerr << "cost of conversion is:" << cvtCost << std::endl; ) if ( cvtCost != Cost::infinity ) { - withFunc->cvtCost = cvtCost; - alternatives.push_back( *withFunc ); + withFunc.cvtCost = cvtCost; + alternatives.push_back( withFunc ); } // if } // for - candidates.clear(); - candidates.splice( candidates.end(), alternatives ); + candidates = move(alternatives); // use a new list so that alternatives are not examined by addAnonConversions twice. @@ -1148,11 +1147,11 @@ findMinCost( candidates.begin(), candidates.end(), std::back_inserter( winners ) ); - // function may return struct or union value, in which case we need to add alternatives for implicit - // conversions to each of the anonymous members, must happen after findMinCost since anon conversions - // are never the cheapest expression + // function may return struct or union value, in which case we need to add alternatives + // for implicitconversions to each of the anonymous members, must happen after findMinCost + // since anon conversions are never the cheapest expression for ( const Alternative & alt : winners ) { addAnonConversions( alt ); } - alternatives.splice( alternatives.begin(), winners ); + spliceBegin( alternatives, winners ); if ( alternatives.empty() && targetType && ! targetType->isVoid() ) { @@ -1178,7 +1177,8 @@ AlternativeFinder finder( indexer, env ); finder.find( addressExpr->get_arg() ); - for ( std::list< Alternative >::iterator i = finder.alternatives.begin(); i != finder.alternatives.end(); ++i ) { - if ( isLvalue( i->expr ) ) { - alternatives.push_back( Alternative( new AddressExpr( i->expr->clone() ), i->env, i->cost ) ); + for ( Alternative& alt : finder.alternatives ) { + if ( isLvalue( alt.expr ) ) { + alternatives.push_back( + Alternative{ new AddressExpr( alt.expr->clone() ), alt.env, alt.cost } ); } // if } // for @@ -1186,5 +1186,5 @@ void AlternativeFinder::visit( LabelAddressExpr * expr ) { - alternatives.push_back( Alternative( expr->clone(), env, Cost::zero) ); + alternatives.push_back( Alternative{ expr->clone(), env, Cost::zero } ); } @@ -1228,5 +1228,5 @@ AltList candidates; - for ( std::list< Alternative >::iterator i = finder.alternatives.begin(); i != finder.alternatives.end(); ++i ) { + for ( Alternative& alt : finder.alternatives ) { AssertionSet needAssertions, haveAssertions; OpenVarSet openVars; @@ -1236,16 +1236,20 @@ // that are cast directly. The candidate is invalid if it has fewer results than there are types to cast // to. - int discardedValues = i->expr->get_result()->size() - castExpr->get_result()->size(); + int discardedValues = alt.expr->get_result()->size() - castExpr->get_result()->size(); if ( discardedValues < 0 ) continue; // xxx - may need to go into tuple types and extract relevant types and use unifyList. Note that currently, this does not // allow casting a tuple to an atomic type (e.g. (int)([1, 2, 3])) // unification run for side-effects - unify( castExpr->get_result(), i->expr->get_result(), i->env, needAssertions, haveAssertions, openVars, indexer ); - Cost thisCost = castCost( i->expr->get_result(), castExpr->get_result(), indexer, i->env ); + unify( castExpr->get_result(), alt.expr->get_result(), alt.env, needAssertions, + haveAssertions, openVars, indexer ); + Cost thisCost = castCost( alt.expr->get_result(), castExpr->get_result(), indexer, + alt.env ); if ( thisCost != Cost::infinity ) { // count one safe conversion for each value that is thrown away thisCost.incSafe( discardedValues ); - Alternative newAlt( restructureCast( i->expr->clone(), toType ), i->env, i->cost, thisCost ); - inferParameters( needAssertions, haveAssertions, newAlt, openVars, back_inserter( candidates ) ); + Alternative newAlt( restructureCast( alt.expr->clone(), toType ), alt.env, + alt.cost, thisCost ); + inferParameters( needAssertions, haveAssertions, newAlt, openVars, + back_inserter( candidates ) ); } // if } // for @@ -1534,15 +1538,18 @@ void AlternativeFinder::visit( UntypedTupleExpr *tupleExpr ) { - std::list< AlternativeFinder > subExprAlternatives; - findSubExprs( tupleExpr->get_exprs().begin(), tupleExpr->get_exprs().end(), back_inserter( subExprAlternatives ) ); - std::list< AltList > possibilities; - combos( subExprAlternatives.begin(), subExprAlternatives.end(), back_inserter( possibilities ) ); - for ( std::list< AltList >::const_iterator i = possibilities.begin(); i != possibilities.end(); ++i ) { + std::vector< AlternativeFinder > subExprAlternatives; + findSubExprs( tupleExpr->get_exprs().begin(), tupleExpr->get_exprs().end(), + back_inserter( subExprAlternatives ) ); + std::vector< AltList > possibilities; + combos( subExprAlternatives.begin(), subExprAlternatives.end(), + back_inserter( possibilities ) ); + for ( const AltList& alts : possibilities ) { std::list< Expression * > exprs; - makeExprList( *i, exprs ); + makeExprList( alts, exprs ); TypeEnvironment compositeEnv; - simpleCombineEnvironments( i->begin(), i->end(), compositeEnv ); - alternatives.push_back( Alternative( new TupleExpr( exprs ) , compositeEnv, sumCost( *i ) ) ); + simpleCombineEnvironments( alts.begin(), alts.end(), compositeEnv ); + alternatives.push_back( + Alternative{ new TupleExpr( exprs ), compositeEnv, sumCost( alts ) } ); } // for } Index: src/ResolvExpr/Resolver.cc =================================================================== --- src/ResolvExpr/Resolver.cc (revision 73a5cadbd1f793f9d7fa1cdf290ae5115ec37051) +++ src/ResolvExpr/Resolver.cc (revision bd4f2e9b269f4ba6094575b830cab685e3a1d075) @@ -18,4 +18,5 @@ #include // for allocator, allocator_traits<... #include // for get +#include #include "Alternative.h" // for Alternative, AltList @@ -411,9 +412,9 @@ // Find all alternatives for all arguments in canonical form - std::list< AlternativeFinder > argAlternatives; + std::vector< AlternativeFinder > argAlternatives; funcFinder.findSubExprs( clause.target.arguments.begin(), clause.target.arguments.end(), back_inserter( argAlternatives ) ); // List all combinations of arguments - std::list< AltList > possibilities; + std::vector< AltList > possibilities; combos( argAlternatives.begin(), argAlternatives.end(), back_inserter( possibilities ) ); Index: src/ResolvExpr/typeops.h =================================================================== --- src/ResolvExpr/typeops.h (revision 73a5cadbd1f793f9d7fa1cdf290ae5115ec37051) +++ src/ResolvExpr/typeops.h (revision bd4f2e9b269f4ba6094575b830cab685e3a1d075) @@ -16,4 +16,6 @@ #pragma once +#include + #include "SynTree/SynTree.h" #include "SynTree/Type.h" @@ -28,5 +30,5 @@ void combos( InputIterator begin, InputIterator end, OutputIterator out ) { typedef typename InputIterator::value_type SetType; - typedef typename std::list< typename SetType::value_type > ListType; + typedef typename std::vector< typename SetType::value_type > ListType; if ( begin == end ) { @@ -38,16 +40,14 @@ begin++; - std::list< ListType > recursiveResult; + std::vector< ListType > recursiveResult; combos( begin, end, back_inserter( recursiveResult ) ); - for ( typename std::list< ListType >::const_iterator i = recursiveResult.begin(); i != recursiveResult.end(); ++i ) { - for ( typename ListType::const_iterator j = current->begin(); j != current->end(); ++j ) { - ListType result; - std::back_insert_iterator< ListType > inserter = back_inserter( result ); - *inserter++ = *j; - std::copy( i->begin(), i->end(), inserter ); - *out++ = result; - } // for - } // for + for ( const auto& i : recursiveResult ) for ( const auto& j : *current ) { + ListType result; + std::back_insert_iterator< ListType > inserter = back_inserter( result ); + *inserter++ = j; + std::copy( i.begin(), i.end(), inserter ); + *out++ = result; + } } Index: src/Tuples/TupleAssignment.cc =================================================================== --- src/Tuples/TupleAssignment.cc (revision 73a5cadbd1f793f9d7fa1cdf290ae5115ec37051) +++ src/Tuples/TupleAssignment.cc (revision bd4f2e9b269f4ba6094575b830cab685e3a1d075) @@ -251,5 +251,6 @@ // combine assignment environments into combined expression environment simpleCombineEnvironments( current.begin(), current.end(), matcher->compositeEnv ); - currentFinder.get_alternatives().push_front( ResolvExpr::Alternative( + // xxx -- was push_front + currentFinder.get_alternatives().push_back( ResolvExpr::Alternative( new TupleAssignExpr(solved_assigns, matcher->tmpDecls), matcher->compositeEnv, ResolvExpr::sumCost( current ) + matcher->baseCost ) );