Changeset bd4f2e9

Timestamp:

Nov 22, 2017, 1:32:55 PM (7 years ago)

Author:

Aaron Moss <a3moss@…>

Branches:

ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, deferred_resn, demangler, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, pthread-emulation, qualifiedEnum, resolv-new, with_gc

Children:

c2c6177

Parents:

73a5cadb

Message:

Switch AltList? to std::vector from std::list

Location:

src

Files:

• ResolvExpr/Alternative.cc (modified) (2 diffs)
• ResolvExpr/Alternative.h (modified) (3 diffs)
• ResolvExpr/AlternativeFinder.cc (modified) (10 diffs)
• ResolvExpr/Resolver.cc (modified) (2 diffs)
• ResolvExpr/typeops.h (modified) (3 diffs)
• Tuples/TupleAssignment.cc (modified) (1 diff)

src/ResolvExpr/Alternative.cc

@@ -18 +18 @@
 #include <ostream>                       // for operator<<, ostream, basic_o...
 #include <string>                        // for operator<<, char_traits, string
+#include <utility>                       // for move
 
 #include "Common/utility.h"              // for maybeClone
@@ -81 +82 @@
                 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
 

src/ResolvExpr/Alternative.h

@@ -17 +17 @@
 
 #include <iosfwd>             // for ostream
-#include <list>               // for list
+#include <vector>             // for vector
 
 #include "Cost.h"             // for Cost
@@ -25 +25 @@
 
 namespace ResolvExpr {
-        struct Alternative;
-
-        typedef std::list< Alternative > AltList;
-
         struct Alternative {
                 Alternative();
@@ -46 +42 @@
                 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
 

src/ResolvExpr/AlternativeFinder.cc

@@ -194 +194 @@
                                 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 +206 @@
                                 throw SemanticError( stream.str() );
                         }
-                        alternatives.erase( oldBegin, alternatives.end() );
+                        alternatives = move(pruned);
                         PRINT(
                                 std::cerr << "there are " << oldsize << " alternatives before elimination" << std::endl;
@@ -1119 +1119 @@
 
                 // 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 +1132 @@
                                 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 +1147 @@
                 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 +1177 @@
                 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 +1186 @@
 
         void AlternativeFinder::visit( LabelAddressExpr * expr ) {
-                alternatives.push_back( Alternative( expr->clone(), env, Cost::zero) );
+                alternatives.push_back( Alternative{ expr->clone(), env, Cost::zero } );
         }
 
@@ -1228 +1228 @@
 
                 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 +1236 @@
                         // 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 +1538 @@
 
         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
         }

src/ResolvExpr/Resolver.cc

@@ -18 +18 @@
 #include <memory>                        // for allocator, allocator_traits<...
 #include <tuple>                         // for get
+#include <vector>
 
 #include "Alternative.h"                 // for Alternative, AltList
@@ -411 +412 @@
 
                         // 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 ) );
 

src/ResolvExpr/typeops.h

@@ -16 +16 @@
 #pragma once
 
+#include <vector>
+
 #include "SynTree/SynTree.h"
 #include "SynTree/Type.h"
@@ -28 +30 @@
         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 +40 @@
                 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;
+                }
         }
 

src/Tuples/TupleAssignment.cc

@@ -251 +251 @@
                 // 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 ) );