Changeset 5af62f1


Ignore:
Timestamp:
Sep 10, 2016, 12:53:36 PM (8 years ago)
Author:
Rob Schluntz <rschlunt@…>
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:
908cc83
Parents:
add7117
Message:

major refactoring of Rodolfo's tuple assignment code

Location:
src
Files:
4 edited

Legend:

Unmodified
Added
Removed

  • src/ResolvExpr/AlternativeFinder.cc

    radd7117 r5af62f1  
    142142                }
    143143
    144                 template< typename InputIterator, typename OutputIterator >
    145                 void findMinCost( InputIterator begin, InputIterator end, OutputIterator out ) {
    146                         AltList alternatives;
    147 
    148                         // select the alternatives that have the minimum parameter cost
    149                         Cost minCost = Cost::infinity;
    150                         for ( AltList::iterator i = begin; i != end; ++i ) {
    151                                 if ( i->cost < minCost ) {
    152                                         minCost = i->cost;
    153                                         i->cost = i->cvtCost;
    154                                         alternatives.clear();
    155                                         alternatives.push_back( *i );
    156                                 } else if ( i->cost == minCost ) {
    157                                         i->cost = i->cvtCost;
    158                                         alternatives.push_back( *i );
    159                                 }
    160                         }
    161                         std::copy( alternatives.begin(), alternatives.end(), out );
    162                 }
    163 
    164144                template< typename InputIterator >
    165145                void simpleCombineEnvironments( InputIterator begin, InputIterator end, TypeEnvironment &result ) {
    … …  
    254234        template< typename StructOrUnionType >
    255235        void AlternativeFinder::addAggMembers( StructOrUnionType *aggInst, Expression *expr, const Cost &newCost, const TypeEnvironment & env, Expression * member ) {
     236
     237                // // member must be either a tuple expression or a name expr
     238                // if ( NameExpr * nameExpr = dynamic_cast< NameExpr * >( memberExpr->get_member() ) ) {
     239                //  addAggMembers( structInst, agg->expr, agg->cost, nameExpr->get_name() );
     240                // } else {
     241                //  TupleExpr * tupleExpr = safe_dynamic_cast< TupleExpr * >( memberExpr->get_member() );
     242                //  // xxx - ...
     243                //  assert( false );
     244                // }
     245                // if ( TupleExpr * tupleExpr = dynamic_cast< TupleExpr * >( memberExpr->get_member() ) ) {
     246
     247                // }
    256248                NameExpr * nameExpr = safe_dynamic_cast< NameExpr * >( member );
    257249                const std::string & name = nameExpr->get_name();
    … …  
    639631                combos( argAlternatives.begin(), argAlternatives.end(), back_inserter( possibilities ) );
    640632
    641                 Tuples::TupleAssignSpotter tassign( this );
    642                 if ( tassign.isTupleAssignment( untypedExpr, possibilities ) ) {
    643                         // take care of possible tuple assignments, or discard expression
    644                         return;
    645                 } // else ...
     633                // take care of possible tuple assignments
     634                // if not tuple assignment, assignment is taken care of as a normal function call
     635                Tuples::handleTupleAssignment( *this, untypedExpr, possibilities );
    646636
    647637                AltList candidates;

  • src/ResolvExpr/AlternativeFinder.h

    radd7117 r5af62f1  
    6767                virtual void visit( ImplicitCopyCtorExpr * impCpCtorExpr );
    6868                virtual void visit( ConstructorExpr * ctorExpr );
    69           public:  // xxx - temporary hack - should make Tuples::TupleAssignment a friend
    70           /// Runs a new alternative finder on each element in [begin, end)
    71           /// and writes each alternative finder to out.
     69                /// Runs a new alternative finder on each element in [begin, end)
     70                /// and writes each alternative finder to out.
    7271                template< typename InputIterator, typename OutputIterator >
    7372                void findSubExprs( InputIterator begin, InputIterator end, OutputIterator out );
    7473
    75           private:
    7674                /// Adds alternatives for member expressions, given the aggregate, conversion cost for that aggregate, and name of the member
    7775                template< typename StructOrUnionType > void addAggMembers( StructOrUnionType *aggInst, Expression *expr, const Cost &newCost, const TypeEnvironment & env, Expression * member );
    … …  
    9189
    9290        Expression *resolveInVoidContext( Expression *expr, const SymTab::Indexer &indexer, TypeEnvironment &env );
     91
     92        template< typename InputIterator, typename OutputIterator >
     93        void findMinCost( InputIterator begin, InputIterator end, OutputIterator out ) {
     94                AltList alternatives;
     95
     96                // select the alternatives that have the minimum parameter cost
     97                Cost minCost = Cost::infinity;
     98                for ( InputIterator i = begin; i != end; ++i ) {
     99                        if ( i->cost < minCost ) {
     100                                minCost = i->cost;
     101                                i->cost = i->cvtCost;
     102                                alternatives.clear();
     103                                alternatives.push_back( *i );
     104                        } else if ( i->cost == minCost ) {
     105                                i->cost = i->cvtCost;
     106                                alternatives.push_back( *i );
     107                        }
     108                }
     109                std::copy( alternatives.begin(), alternatives.end(), out );
     110        }
    93111} // namespace ResolvExpr
    94112

  • src/Tuples/TupleAssignment.cc

    radd7117 r5af62f1  
    55// file "LICENCE" distributed with Cforall.
    66//
    7 // TupleAssignment.cc -- 
     7// TupleAssignment.cc --
    88//
    99// Author           : Rodolfo G. Esteves
    … …  
    2727#include <cassert>
    2828#include <set>
     29#include <unordered_set>
    2930
    3031namespace Tuples {
    31         TupleAssignSpotter::TupleAssignSpotter( ResolvExpr::AlternativeFinder *f = 0 )
    32                 : currentFinder(f), matcher(0), hasMatched( false ) {}
    33 
    34         bool TupleAssignSpotter::pointsToTuple( Expression *expr ) {
     32        class TupleAssignSpotter {
     33          public:
     34                // dispatcher for Tuple (multiple and mass) assignment operations
     35                TupleAssignSpotter( ResolvExpr::AlternativeFinder & );
     36                void spot( UntypedExpr * expr, std::list<ResolvExpr::AltList> &possibilities );
     37
     38          private:
     39                void match();
     40                // records for assignment generation
     41                struct Options {
     42                        std::list< ResolvExpr::AltList > get_best();
     43                        void print( std::ostream & );
     44                        int size() const { return options.size(); }
     45                        bool empty() const { return options.empty(); }
     46                        typedef std::list< ResolvExpr::AltList >::iterator iterator;
     47                        iterator begin() { return options.begin(); }
     48                        iterator end() { return options.end(); }
     49
     50                        std::list< ResolvExpr::AltList > options;
     51                };
     52
     53                class Matcher {
     54                  public:
     55                        Matcher( TupleAssignSpotter &spotter, Expression *_lhs, Expression *_rhs );
     56                        virtual ~Matcher() {}
     57                        virtual void match( std::list< Expression * > &out ) = 0;
     58                        virtual void solve( std::list< Expression * > &assigns ) = 0;
     59                        static UntypedExpr *createAssgn( Expression *left, Expression *right );
     60                  protected:
     61                        std::list< Expression * > lhs, rhs;
     62                        TupleAssignSpotter &spotter;
     63                };
     64
     65                class MassAssignMatcher : public Matcher {
     66                  public:
     67                        MassAssignMatcher( TupleAssignSpotter &spotter, Expression *lhs, Expression *rhs ) : Matcher( spotter, lhs, rhs ) {
     68                                this->rhs.push_back( rhs );
     69                        }
     70                        virtual void match( std::list< Expression * > &out );
     71                        virtual void solve( std::list< Expression * > &assigns );
     72                };
     73
     74                class MultipleAssignMatcher : public Matcher {
     75                  public:
     76                        MultipleAssignMatcher( TupleAssignSpotter &spot, Expression *lhs, Expression *rhs );
     77                        virtual void match( std::list< Expression * > &out );
     78                        virtual void solve( std::list< Expression * > &assigns );
     79                };
     80
     81                ResolvExpr::AlternativeFinder &currentFinder;
     82                Expression *rhs, *lhs;
     83                Matcher *matcher = nullptr;
     84                Options options;
     85        };
     86
     87        bool isTupleVar( DeclarationWithType *decl ) {
     88                return dynamic_cast< TupleType * >( decl->get_type() );
     89        }
     90
     91        /// true if expr is an expression of tuple type, i.e. a tuple expression, tuple variable, or MRV (multiple-return-value) function
     92        bool isTuple( Expression *expr ) {
     93                if ( ! expr ) return false;
     94
     95                // xxx - used to include cast to varExpr and call to isTupleVar, but this doesn't seem like it should be necessary
     96                return dynamic_cast<TupleExpr *>(expr) || expr->get_results().size() > 1;
     97        }
     98
     99        bool pointsToTuple( Expression *expr ) {
    35100                // also check for function returning tuple of reference types
    36                 if (AddressExpr *addr = dynamic_cast<AddressExpr *>(expr) )
    37                         if ( isTuple(addr->get_arg() ) )
    38                                 return true;
     101                if ( AddressExpr *addr = dynamic_cast< AddressExpr * >( expr) ) {
     102                        return isTuple( addr->get_arg() );
     103                }
    39104                return false;
    40105        }
    41106
    42         bool TupleAssignSpotter::isTupleVar( DeclarationWithType *decl ) {
    43                 if ( dynamic_cast<TupleType *>(decl->get_type()) )
    44                         return true;
    45                 return false;
    46         }
    47 
    48         bool TupleAssignSpotter::isTuple( Expression *expr, bool isRight ) {
    49                 // true if `expr' is an expression returning a tuple: tuple, tuple variable or MRV function
    50                 if ( ! expr ) return false;
    51 
    52                 if ( dynamic_cast<TupleExpr *>(expr) )
    53                         return true;
    54                 else if ( VariableExpr *var = dynamic_cast<VariableExpr *>(expr) ) {
    55                         if ( isTupleVar(var->get_var()) )
    56                                 return true;
    57                 }
    58 
    59                 return false;
    60         }
    61 
    62         bool TupleAssignSpotter::match() {
    63                 assert ( matcher != 0 );
    64 
    65                 std::list< Expression * > new_assigns;
    66                 if ( ! matcher->match(new_assigns) )
    67                         return false;
    68 
    69                 if ( new_assigns.empty() ) return false;
    70                 /*return */matcher->solve( new_assigns );
    71                 if ( dynamic_cast<TupleAssignSpotter::MultipleAssignMatcher *>( matcher ) ) {
    72                         // now resolve new assignments
    73                         std::list< Expression * > solved_assigns;
    74                         ResolvExpr::AltList solved_alts;
    75                         assert( currentFinder != 0 );
    76 
    77                         ResolvExpr::AltList current;
    78                         for ( std::list< Expression * >::iterator i = new_assigns.begin(); i != new_assigns.end(); ++i ) {
    79                                 //try {
    80                                 ResolvExpr::AlternativeFinder finder( currentFinder->get_indexer(), currentFinder->get_environ() );
    81                                 finder.findWithAdjustment(*i);
    82                                 // prune expressions that don't coincide with
    83                                 ResolvExpr::AltList alts = finder.get_alternatives();
    84                                 assert( alts.size() == 1 );
    85                                 assert(alts.front().expr != 0 );
    86                                 current.push_back( finder.get_alternatives().front() );
    87                                 solved_assigns.push_back( alts.front().expr->clone() );
    88                                 //solved_assigns.back()->print(std::cerr);
    89                                 /*} catch( ... ) {
    90                                   continue; // no reasonable alternative found
    91                                   }*/
    92                         }
    93                         options.add_option( current );
    94 
    95                         return true;
    96                 } else { // mass assignment
    97                         //if ( new_assigns.empty() ) return false;
    98                         std::list< Expression * > solved_assigns;
    99                         ResolvExpr::AltList solved_alts;
    100                         assert( currentFinder != 0 );
    101 
    102                         ResolvExpr::AltList current;
    103                         if ( optMass.empty() ) {
    104                                 for ( std::list< Expression * >::size_type i = 0; i != new_assigns.size(); ++i )
    105                                         optMass.push_back( ResolvExpr::AltList() );
    106                         }
    107                         int cnt = 0;
    108                         for ( std::list< Expression * >::iterator i = new_assigns.begin(); i != new_assigns.end(); ++i, cnt++ ) {
    109 
    110                                 ResolvExpr::AlternativeFinder finder( currentFinder->get_indexer(), currentFinder->get_environ() );
    111                                 finder.findWithAdjustment(*i);
    112                                 ResolvExpr::AltList alts = finder.get_alternatives();
    113                                 assert( alts.size() == 1 );
    114                                 assert(alts.front().expr != 0 );
    115                                 current.push_back( finder.get_alternatives().front() );
    116                                 optMass[cnt].push_back( finder.get_alternatives().front() );
    117                                 solved_assigns.push_back( alts.front().expr->clone() );
    118                         }
    119 
    120                         return true;
    121                 }
    122 
    123                 return false;
    124         }
    125 
    126         bool TupleAssignSpotter::isMVR( Expression *expr ) {
    127                 if ( expr->get_results().size() > 1 ) {
    128                         // MVR processing
    129                         return true;
    130                 }
    131                 return false;
    132         }
    133 
    134         bool TupleAssignSpotter::isTupleAssignment( UntypedExpr * expr, std::list<ResolvExpr::AltList> &possibilities ) {
     107        bool isTupleExpr( Expression *expr ) {
     108                return expr->get_results().size() > 1;
     109        }
     110
     111        void handleTupleAssignment( ResolvExpr::AlternativeFinder & currentFinder, UntypedExpr * expr, std::list<ResolvExpr::AltList> &possibilities ) {
     112                TupleAssignSpotter spotter( currentFinder );
     113                spotter.spot( expr, possibilities );
     114        }
     115
     116        TupleAssignSpotter::TupleAssignSpotter( ResolvExpr::AlternativeFinder &f )
     117                : currentFinder(f) {}
     118
     119        void TupleAssignSpotter::spot( UntypedExpr * expr, std::list<ResolvExpr::AltList> &possibilities ) {
    135120                if (  NameExpr *assgnop = dynamic_cast< NameExpr * >(expr->get_function()) ) {
    136 
    137121                        if ( assgnop->get_name() == std::string("?=?") ) {
    138 
    139122                                for ( std::list<ResolvExpr::AltList>::iterator ali = possibilities.begin(); ali != possibilities.end(); ++ali ) {
    140123                                        assert( ali->size() == 2 );
    141                                         ResolvExpr::AltList::iterator opit = ali->begin();
    142                                         ResolvExpr::Alternative op1 = *opit, op2 = *(++opit);
    143 
     124                                        ResolvExpr::Alternative op1 = ali->front(), op2 = ali->back();
     125
     126                                        MultipleAssignMatcher multiMatcher( *this, op1.expr, op2.expr );
     127                                        MassAssignMatcher massMatcher( *this, op1.expr, op2.expr );
    144128                                        if ( pointsToTuple(op1.expr) ) { // also handles tuple vars
    145                                                 if ( isTuple( op2.expr, true ) )
    146                                                         matcher = new MultipleAssignMatcher(op1.expr, op2.expr);
    147                                                 else if ( isMVR( op2.expr ) ) {
    148                                                         // handle MVR differently
    149                                                 } else
     129                                                if ( isTuple( op2.expr ) ) {
     130                                                        matcher = &multiMatcher;
     131                                                } else {
    150132                                                        // mass assignment
    151                                                         matcher = new MassAssignMatcher(op1.expr, op2.expr);
    152 
    153                                                 std::list< ResolvExpr::AltList > options;
    154                                                 if ( match() )
    155                                                         /*
    156                                                           if ( hasMatched ) {
    157                                                           // throw SemanticError("Ambiguous tuple assignment");
    158                                                           } else {*/
    159                                                         // Matched for the first time
    160                                                         hasMatched = true;
    161                                                 /*} */
    162                                         } /* else if ( isTuple( op2 ) )
    163                                                  throw SemanticError("Inapplicable tuple assignment.");
    164                                           */
    165                                 }
    166 
    167                                 if ( hasMatched ) {
    168                                         if ( dynamic_cast<TupleAssignSpotter::MultipleAssignMatcher *>( matcher ) ) {
    169                                                 //options.print( std::cerr );
    170                                                 std::list< ResolvExpr::AltList >best = options.get_best();
    171                                                 if ( best.size() == 1 ) {
    172                                                         std::list<Expression *> solved_assigns;
    173                                                         for ( ResolvExpr::AltList::iterator i = best.front().begin(); i != best.front().end(); ++i ) {
    174                                                                 solved_assigns.push_back( i->expr );
    175                                                         }
    176                                                         /* assigning cost zero? */
    177                                                         currentFinder->get_alternatives().push_front( ResolvExpr::Alternative(new SolvedTupleExpr(solved_assigns/*, SolvedTupleExpr::MULTIPLE*/), currentFinder->get_environ(), ResolvExpr::Cost() ) );
     133                                                        matcher = &massMatcher;
    178134                                                }
    179                                         } else {
    180                                                 assert( ! optMass.empty() );
    181                                                 ResolvExpr::AltList winners;
    182                                                 for ( std::vector< ResolvExpr::AltList >::iterator i = optMass.begin(); i != optMass.end(); ++i )
    183                                                         findMinCostAlt( i->begin(), i->end(), back_inserter(winners) );
    184 
    185                                                 std::list< Expression *> solved_assigns;
    186                                                 for ( ResolvExpr::AltList::iterator i = winners.begin(); i != winners.end(); ++i )
    187                                                         solved_assigns.push_back( i->expr );
    188                                                 currentFinder->get_alternatives().push_front( ResolvExpr::Alternative(new SolvedTupleExpr(solved_assigns/*, SolvedTupleExpr::MASS*/), currentFinder->get_environ(), ResolvExpr::Cost() ) );
     135                                                match();
     136                                        } else if ( isTuple( op2.expr ) ) {
     137                                                throw SemanticError("Cannot assign a tuple value into a non-tuple lvalue.", expr);
    189138                                        }
    190139                                }
    191140                        }
    192141                }
    193                 return hasMatched;
    194         }
    195 
    196         void TupleAssignSpotter::Matcher::init( Expression *_lhs, Expression *_rhs ) {
    197                 lhs.clear();
    198                 if (AddressExpr *addr = dynamic_cast<AddressExpr *>(_lhs) )
     142        }
     143
     144        void TupleAssignSpotter::match() {
     145                assert ( matcher != 0 );
     146
     147                std::list< Expression * > new_assigns;
     148                matcher->match( new_assigns );
     149
     150                if ( new_assigns.empty() ) return;
     151                std::list< Expression * > solved_assigns;
     152                ResolvExpr::AltList solved_alts;
     153                ResolvExpr::AltList current;
     154                // now resolve new assignments
     155                for ( std::list< Expression * >::iterator i = new_assigns.begin(); i != new_assigns.end(); ++i ) {
     156                        ResolvExpr::AlternativeFinder finder( currentFinder.get_indexer(), currentFinder.get_environ() );
     157                        finder.findWithAdjustment(*i);
     158                        // prune expressions that don't coincide with
     159                        ResolvExpr::AltList alts = finder.get_alternatives();
     160                        assert( alts.size() == 1 );
     161                        assert( alts.front().expr != 0 );
     162                        current.push_back( finder.get_alternatives().front() );
     163                        solved_assigns.push_back( alts.front().expr->clone() );
     164                }
     165                options.options.push_back( current );
     166
     167                matcher->solve( new_assigns );
     168        }
     169
     170        TupleAssignSpotter::Matcher::Matcher( TupleAssignSpotter &spotter, Expression *lhs, Expression *rhs ) : spotter(spotter) {
     171                // xxx - shouldn't need to be &<tuple-expr>, just &<lvalue-tuple-type>
     172                if (AddressExpr *addr = dynamic_cast<AddressExpr *>(lhs) )
    199173                        if ( TupleExpr *tuple = dynamic_cast<TupleExpr *>(addr->get_arg()) )
    200                                 std::copy( tuple->get_exprs().begin(), tuple->get_exprs().end(), back_inserter(lhs) );
    201 
    202                 rhs.clear();
    203         }
    204 
    205         TupleAssignSpotter::Matcher::Matcher( /*TupleAssignSpotter &spot,*/ Expression *_lhs, Expression *_rhs ) /*: own_spotter(spot) */{
    206                 init(_lhs,_rhs);
    207         }
    208 
    209         TupleAssignSpotter::MultipleAssignMatcher::MultipleAssignMatcher( Expression *_lhs, Expression *_rhs )/* : own_spotter(spot) */{
    210                 init(_lhs,_rhs);
    211 
    212                 if ( TupleExpr *tuple = dynamic_cast<TupleExpr *>(_rhs) )
    213                         std::copy( tuple->get_exprs().begin(), tuple->get_exprs().end(), back_inserter(rhs) );
     174                                std::copy( tuple->get_exprs().begin(), tuple->get_exprs().end(), back_inserter(this->lhs) );
     175        }
     176
     177        TupleAssignSpotter::MultipleAssignMatcher::MultipleAssignMatcher( TupleAssignSpotter &spotter, Expression *lhs, Expression *rhs ) : Matcher( spotter, lhs, rhs ) {
     178
     179                if ( TupleExpr *tuple = dynamic_cast<TupleExpr *>(rhs) )
     180                        std::copy( tuple->get_exprs().begin(), tuple->get_exprs().end(), back_inserter(this->rhs) );
    214181        }
    215182
    216183        UntypedExpr *TupleAssignSpotter::Matcher::createAssgn( Expression *left, Expression *right ) {
    217                 if ( left && right ) {
    218                         std::list< Expression * > args;
    219                         args.push_back(new AddressExpr(left->clone()));  args.push_back(right->clone());
    220                         return new UntypedExpr(new NameExpr("?=?"), args);
    221                 } else
    222                         throw 0; // xxx - diagnose the problem
    223         }
    224 
    225         bool TupleAssignSpotter::MassAssignMatcher::match( std::list< Expression * > &out ) {
    226                 if ( lhs.empty() || (rhs.size() != 1) ) return false;
    227 
    228                 for ( std::list< Expression * >::iterator l = lhs.begin(); l != lhs.end(); l++ ) {
    229                         std::list< Expression * > args;
    230                         args.push_back( new AddressExpr(*l) );
    231                         args.push_back( rhs.front() );
    232                         out.push_back( new UntypedExpr(new NameExpr("?=?"), args) );
    233                 }
    234 
    235                 return true;
    236         }
    237 
    238         bool TupleAssignSpotter::MassAssignMatcher::solve( std::list< Expression * > &assigns ) {
    239                 /*
    240                   std::list< Expression * > solved_assigns;
    241                   ResolvExpr::AltList solved_alts;
    242                   assert( currentFinder != 0 );
    243 
    244                   ResolvExpr::AltList current;
    245                   if ( optMass.empty() ) {
    246                   for ( std::list< Expression * >::size_type i = 0; i != new_assigns.size(); ++i )
    247                   optMass.push_back( ResolvExpr::AltList() );
    248                   }
    249                   int cnt = 0;
    250                   for ( std::list< Expression * >::iterator i = new_assigns.begin(); i != new_assigns.end(); ++i, cnt++ ) {
    251 
    252                   ResolvExpr::AlternativeFinder finder( currentFinder->get_indexer(), currentFinder->get_environ() );
    253                   finder.findWithAdjustment(*i);
    254                   ResolvExpr::AltList alts = finder.get_alternatives();
    255                   assert( alts.size() == 1 );
    256                   assert(alts.front().expr != 0 );
    257                   current.push_back( finder.get_alternatives().front() );
    258                   optMass[cnt].push_back( finder.get_alternatives().front() );
    259                   solved_assigns.push_back( alts.front().expr->clone() );
    260                   }
    261                 */
    262                 return true;
    263         }
    264 
    265         bool TupleAssignSpotter::MultipleAssignMatcher::match( std::list< Expression * > &out ) {
    266                 // need more complicated matching
     184                assert( left && right );
     185                std::list< Expression * > args;
     186                args.push_back( new AddressExpr( left->clone() ) );
     187                args.push_back( right->clone() );
     188                return new UntypedExpr( new NameExpr( "?=?" ), args );
     189        }
     190
     191        void TupleAssignSpotter::MassAssignMatcher::match( std::list< Expression * > &out ) {
     192                assert ( ! lhs.empty() && rhs.size() == 1);
     193
     194                for ( Expression * l : lhs ) {
     195                        out.push_back( createAssgn( l, rhs.front() ) );
     196                }
     197        }
     198
     199        void TupleAssignSpotter::MassAssignMatcher::solve( std::list< Expression * > &assigns ) {
     200                assert( ! spotter.options.empty() );
     201                ResolvExpr::AltList winners;
     202                for ( std::list< ResolvExpr::AltList >::iterator i = spotter.options.begin(); i != spotter.options.end(); ++i ) {
     203                        findMinCost( i->begin(), i->end(), back_inserter(winners) );
     204                }
     205
     206                std::list< Expression *> solved_assigns;
     207                for ( ResolvExpr::AltList::iterator i = winners.begin(); i != winners.end(); ++i ) {
     208                        solved_assigns.push_back( i->expr );
     209                }
     210                spotter.currentFinder.get_alternatives().push_front( ResolvExpr::Alternative(new SolvedTupleExpr(solved_assigns), spotter.currentFinder.get_environ(), ResolvExpr::Cost() ) );
     211        }
     212
     213        void TupleAssignSpotter::MultipleAssignMatcher::match( std::list< Expression * > &out ) {
     214                // xxx - need more complicated matching?
    267215                if ( lhs.size() == rhs.size() ) {
    268216                        zipWith( lhs.begin(), lhs.end(), rhs.begin(), rhs.end(), back_inserter(out), TupleAssignSpotter::Matcher::createAssgn );
    269                         return true;
    270                 } //else
    271                 //std::cerr << "The length of (left, right) is: (" << lhs.size() << "," << rhs.size() << ")" << std::endl;*/
    272                 return false;
    273         }
    274 
    275         bool TupleAssignSpotter::MultipleAssignMatcher::solve( std::list< Expression * > &assigns ) {
    276                 /*
    277                   std::list< Expression * > solved_assigns;
    278                   ResolvExpr::AltList solved_alts;
    279                   assert( currentFinder != 0 );
    280 
    281                   ResolvExpr::AltList current;
    282                   for ( std::list< Expression * >::iterator i = new_assigns.begin(); i != new_assigns.end(); ++i ) {
    283                   //try {
    284                   ResolvExpr::AlternativeFinder finder( currentFinder->get_indexer(), currentFinder->get_environ() );
    285                   finder.findWithAdjustment(*i);
    286                   // prune expressions that don't coincide with
    287                   ResolvExpr::AltList alts = finder.get_alternatives();
    288                   assert( alts.size() == 1 );
    289                   assert(alts.front().expr != 0 );
    290                   current.push_back( finder.get_alternatives().front() );
    291                   solved_assigns.push_back( alts.front().expr->clone() );
    292                   //solved_assigns.back()->print(std::cerr);
    293                   //} catch( ... ) {
    294                   //continue; // no reasonable alternative found
    295                   //}
    296                   }
    297                   options.add_option( current );
    298                 */
    299 
    300                 return true;
    301         }
    302 
    303         void TupleAssignSpotter::Options::add_option( ResolvExpr::AltList &opt ) {
    304                 using namespace std;
    305 
    306                 options.push_back( opt );
    307                 /*
    308                   vector< Cost > costs;
    309                   costs.reserve( opt.size() );
    310                   transform( opt.begin(), opt.end(), back_inserter(costs), ptr_fun(extract_cost) );
    311                 */
    312                 // transpose matrix
    313                 if ( costMatrix.empty() )
    314                         for ( unsigned int i = 0; i< opt.size(); ++i)
    315                                 costMatrix.push_back( vector<ResolvExpr::Cost>() );
    316 
    317                 int cnt = 0;
    318                 for ( ResolvExpr::AltList::iterator i = opt.begin(); i != opt.end(); ++i, cnt++ )
    319                         costMatrix[cnt].push_back( i->cost );
    320 
    321                 return;
     217                }
     218        }
     219
     220        void TupleAssignSpotter::MultipleAssignMatcher::solve( std::list< Expression * > &assigns ) {
     221                // options.print( std::cerr );
     222                std::list< ResolvExpr::AltList > best = spotter.options.get_best();
     223                if ( best.size() == 1 ) {
     224                        std::list<Expression *> solved_assigns;
     225                        for ( ResolvExpr::AltList::iterator i = best.front().begin(); i != best.front().end(); ++i ) {
     226                                solved_assigns.push_back( i->expr );
     227                        }
     228                        /* assigning cost zero? */
     229                        spotter.currentFinder.get_alternatives().push_front( ResolvExpr::Alternative(new SolvedTupleExpr(solved_assigns), spotter.currentFinder.get_environ(), ResolvExpr::Cost() ) );
     230                }
    322231        }
    323232
    324233        std::list< ResolvExpr::AltList > TupleAssignSpotter::Options::get_best() {
    325                 using namespace std;
    326                 using namespace ResolvExpr;
    327                 list< ResolvExpr::AltList > ret;
    328                 list< multiset<int> > solns;
    329                 for ( vector< vector<Cost> >::iterator i = costMatrix.begin(); i != costMatrix.end(); ++i ) {
    330                         list<int> current;
    331                         findMinCost( i->begin(), i->end(), back_inserter(current) );
    332                         solns.push_back( multiset<int>(current.begin(), current.end()) );
    333                 }
    334                 // need to combine
    335                 multiset<int> result;
    336                 lift_intersection( solns.begin(), solns.end(), inserter( result, result.begin() ) );
    337                 if ( result.size() != 1 )
     234                std::list< ResolvExpr::AltList > ret;
     235                std::list< ResolvExpr::AltList > solns;
     236                for ( ResolvExpr::AltList & i : options ) {
     237                        ResolvExpr::AltList current;
     238                        findMinCost( i.begin(), i.end(), back_inserter(current) );
     239                        solns.push_back( ResolvExpr::AltList(current.begin(), current.end()) );
     240                }
     241                // need to combine -- previously "lift_intersection", which
     242                // did some madness involving, effectively, the intersection of
     243                // a bunch of AltLists
     244                std::list<ResolvExpr::AltList> result = solns;
     245                if ( result.size() != 1 ) {
    338246                        throw SemanticError("Ambiguous tuple expression");
    339                 ret.push_back(get_option( *(result.begin() )));
     247                }
     248                ret.push_back( *result.begin() );
    340249                return ret;
    341250        }
    342251
    343252        void TupleAssignSpotter::Options::print( std::ostream &ostr ) {
    344                 using namespace std;
    345 
    346                 for ( vector< vector < ResolvExpr::Cost > >::iterator i = costMatrix.begin(); i != costMatrix.end(); ++i ) {
    347                         for ( vector < ResolvExpr::Cost >::iterator j = i->begin(); j != i->end(); ++j )
    348                                 ostr << *j << " " ;
     253                for ( ResolvExpr::AltList & l : options ) {
     254                        for ( ResolvExpr::Alternative & alt : l ) {
     255                                alt.print( ostr );
     256                                ostr << " ";
     257                        }
    349258                        ostr << std::endl;
    350259                } // for
    351                 return;
    352         }
    353 
    354         ResolvExpr::Cost extract_cost( ResolvExpr::Alternative &alt ) {
    355                 return alt.cost;
    356         }
    357 
    358         template< typename InputIterator, typename OutputIterator >
    359         void TupleAssignSpotter::Options::findMinCost( InputIterator begin, InputIterator end, OutputIterator out ) {
    360                 using namespace ResolvExpr;
    361                 std::list<int> alternatives;
    362 
    363                 // select the alternatives that have the minimum parameter cost
    364                 Cost minCost = Cost::infinity;
    365                 unsigned int index = 0;
    366                 for ( InputIterator i = begin; i != end; ++i, index++ ) {
    367                         if ( *i < minCost ) {
    368                                 minCost = *i;
    369                                 alternatives.clear();
    370                                 alternatives.push_back( index );
    371                         } else if ( *i == minCost ) {
    372                                 alternatives.push_back( index );
    373                         }
    374                 }
    375                 std::copy( alternatives.begin(), alternatives.end(), out );
    376         }
    377 
    378         template< class InputIterator, class OutputIterator >
    379         void TupleAssignSpotter::Options::lift_intersection( InputIterator begin, InputIterator end, OutputIterator out ) {
    380                 if ( begin == end ) return;
    381                 InputIterator test = begin;
    382 
    383                 if (++test == end)
    384                         { copy(begin->begin(), begin->end(), out); return; }
    385 
    386 
    387                 std::multiset<int> cur; // InputIterator::value_type::value_type
    388                 copy( begin->begin(), begin->end(), inserter( cur, cur.begin() ) );
    389 
    390                 while ( test != end ) {
    391                         std::multiset<int> temp;
    392                         set_intersection( cur.begin(), cur.end(), test->begin(), test->end(), inserter(temp,temp.begin()) );
    393                         cur.clear();
    394                         copy( temp.begin(), temp.end(), inserter(cur,cur.begin()));
    395                         ++test;
    396                 }
    397 
    398                 copy( cur.begin(), cur.end(), out );
    399                 return;
    400         }
    401 
    402         ResolvExpr::AltList TupleAssignSpotter::Options::get_option( std::list< ResolvExpr::AltList >::size_type index ) {
    403                 if ( index >= options.size() )
    404                         throw 0; // XXX
    405                 std::list< ResolvExpr::AltList >::iterator it = options.begin();
    406                 for ( std::list< ResolvExpr::AltList >::size_type i = 0; i < index; ++i, ++it );
    407                 return *it;
    408260        }
    409261} // namespace Tuples

  • src/Tuples/TupleAssignment.h

    radd7117 r5af62f1  
    55// file "LICENCE" distributed with Cforall.
    66//
    7 // TupleAssignment.h -- 
     7// TupleAssignment.h --
    88//
    99// Author           : Rodolfo G. Esteves
    … …  
    2626
    2727namespace Tuples {
    28         class TupleAssignSpotter {
    29           public:
    30                 // dispatcher for Tuple (multiple and mass) assignment operations
    31                 TupleAssignSpotter( ResolvExpr::AlternativeFinder * );
    32                 ~TupleAssignSpotter() { delete matcher; matcher = 0; }
    33 
    34                 bool pointsToTuple( Expression * );
    35                 static bool isTupleVar( DeclarationWithType * );
    36                 bool isTuple( Expression *, bool isRight = false );
    37                 bool isMVR( Expression * );
    38                 bool isTupleAssignment( UntypedExpr *, std::list<ResolvExpr::AltList> & );
    39                 bool match();
    40           private:
    41                 // records for assignment generation
    42                 class Options {
    43                   public:
    44                         void add_option( ResolvExpr::AltList &opt );
    45                         std::list< ResolvExpr::AltList > get_best();
    46                         void print( std::ostream & );
    47                         int size() const { return options.size(); }
    48                         ResolvExpr::AltList get_option( std::list< ResolvExpr::AltList >::size_type index );
    49 
    50                         // should really use the one in ResolvExpr/AlternativeFinder, but it's too coupled with the object
    51                         template< typename InputIterator, typename OutputIterator >
    52                         void findMinCost( InputIterator begin, InputIterator end, OutputIterator out );
    53 
    54                         template< typename InputIterator, typename OutputIterator >
    55                         void lift_intersection( InputIterator begin, InputIterator end, OutputIterator out );
    56                   private:
    57                         std::list< ResolvExpr::AltList > options;
    58                         std::vector< std::vector< ResolvExpr::Cost > > costMatrix;
    59                 };
    60 
    61                 class Matcher {
    62                   public:
    63                         Matcher( /*TupleAssignSpotter &spot, */Expression *_lhs, Expression *_rhs );
    64                         virtual ~Matcher() {}
    65                         virtual bool match( std::list< Expression * > &out ) = 0;
    66                         virtual bool solve( std::list< Expression * > &assigns ) = 0;
    67                         static UntypedExpr *createAssgn( Expression *left, Expression *right );
    68                   protected:
    69                         Matcher() /*: own_spotter( TupleAssignSpotter(0) ) */{}
    70                         void init(/* TupleAssignSpotter &, */Expression *_lhs, Expression *_rhs );
    71                         std::list< Expression * > lhs, rhs;
    72                         //TupleAssignSpotter &own_spotter;
    73                 };
    74 
    75                 class MassAssignMatcher : public Matcher {
    76                   public:
    77                         MassAssignMatcher( Expression *_lhs, Expression *_rhs ) : Matcher( _lhs, _rhs ) {
    78                                 rhs.push_back( _rhs );
    79                         }
    80                         virtual bool match( std::list< Expression * > &out );
    81                         virtual bool solve( std::list< Expression * > &assigns );
    82                   private:
    83                         //std::vector< ResolvExpr::AltList > optMass;
    84                 };
    85 
    86                 class MultipleAssignMatcher : public Matcher {
    87                   public:
    88                         MultipleAssignMatcher( Expression *_lhs, Expression *_rhs );
    89                         virtual bool match( std::list< Expression * > &out );
    90                         virtual bool solve( std::list< Expression * > &assigns );
    91                   private:
    92                         //Options options;
    93                 };
    94 
    95                 friend class Matcher;
    96 
    97                 ResolvExpr::AlternativeFinder *currentFinder;
    98                 //std::list<Expression *> rhs, lhs;
    99                 Expression *rhs, *lhs;
    100                 Matcher *matcher;
    101                 bool hasMatched;
    102                 Options options;
    103                 std::vector< ResolvExpr::AltList > optMass;
    104         };
    105 
    106         ResolvExpr::Cost extract_cost( ResolvExpr::Alternative & );
    107 
    108         template< typename InputIterator, typename OutputIterator >
    109         void findMinCostAlt( InputIterator begin, InputIterator end, OutputIterator out ) {
    110                 using namespace ResolvExpr;
    111                 AltList alternatives;
    112 
    113                 // select the alternatives that have the minimum parameter cost
    114                 Cost minCost = Cost::infinity;
    115                 for ( AltList::iterator i = begin; i != end; ++i ) {
    116                         if ( i->cost < minCost ) {
    117                                 minCost = i->cost;
    118                                 i->cost = i->cvtCost;
    119                                 alternatives.clear();
    120                                 alternatives.push_back( *i );
    121                         } else if ( i->cost == minCost ) {
    122                                 i->cost = i->cvtCost;
    123                                 alternatives.push_back( *i );
    124                         }
    125                 }
    126                 std::copy( alternatives.begin(), alternatives.end(), out );
    127         }
     28        void handleTupleAssignment( ResolvExpr::AlternativeFinder & currentFinder, UntypedExpr * assign, std::list<ResolvExpr::AltList> & possibilities );
    12829} // namespace Tuples
    12930
Note: See TracChangeset for help on using the changeset viewer.