source: translator/Tuples/TupleAssignment.cc @ a32b204

ADTaaron-thesisarm-ehast-experimentalcleanup-dtorsctordeferred_resndemanglerenumforall-pointer-decaygc_noraiijacob/cs343-translationjenkins-sandboxmemorynew-astnew-ast-unique-exprnew-envno_listpersistent-indexerpthread-emulationqualifiedEnumresolv-newstringwith_gc
Last change on this file since a32b204 was a32b204, checked in by Peter A. Buhr <pabuhr@…>, 9 years ago

licencing: second groups of files

  • Property mode set to 100644
File size: 13.9 KB
Line 
1#include "ResolvExpr/AlternativeFinder.h"
2#include "ResolvExpr/Alternative.h"
3#include "ResolvExpr/typeops.h"
4#include "SynTree/Expression.h"
5#include "TupleAssignment.h"
6#include "SemanticError.h"
7
8#include <functional>
9#include <algorithm>
10#include <iterator>
11#include <iostream>
12#include <cassert>
13#include <set>
14
15namespace Tuples {
16  TupleAssignSpotter::TupleAssignSpotter( ResolvExpr::AlternativeFinder *f = 0 )
17    : currentFinder(f), matcher(0), hasMatched( false ) {}
18
19  bool TupleAssignSpotter::pointsToTuple( Expression *expr ) {
20    // also check for function returning tuple of reference types
21    if (AddressExpr *addr = dynamic_cast<AddressExpr *>(expr) )
22      if ( isTuple(addr->get_arg() ) )
23        return true;
24    return false;
25  }
26
27  bool TupleAssignSpotter::isTupleVar( DeclarationWithType *decl ) {
28    if ( dynamic_cast<TupleType *>(decl->get_type()) )
29      return true;
30    return false;
31  }
32
33  bool TupleAssignSpotter::isTuple( Expression *expr, bool isRight ) {
34    // true if `expr' is an expression returning a tuple: tuple, tuple variable or MRV function
35    if ( ! expr ) return false;
36
37    if ( dynamic_cast<TupleExpr *>(expr) )
38      return true;
39    else if ( VariableExpr *var = dynamic_cast<VariableExpr *>(expr) ) {
40      if ( isTupleVar(var->get_var()) )
41        return true;
42    }
43
44    return false;
45  }
46
47  bool TupleAssignSpotter::match() {
48    assert ( matcher != 0 );
49
50    std::list< Expression * > new_assigns;
51    if (! matcher->match(new_assigns) )
52      return false;
53
54    if ( new_assigns.empty() ) return false;
55    /*return */matcher->solve( new_assigns );
56    if ( dynamic_cast<TupleAssignSpotter::MultipleAssignMatcher *>( matcher ) ) {
57      // now resolve new assignments
58      std::list< Expression * > solved_assigns;
59      ResolvExpr::AltList solved_alts;
60      assert( currentFinder != 0 );
61
62      ResolvExpr::AltList current;
63      for ( std::list< Expression * >::iterator i = new_assigns.begin(); i != new_assigns.end(); ++i ) {
64        //try {
65        ResolvExpr::AlternativeFinder finder( currentFinder->get_indexer(), currentFinder->get_environ() );
66        finder.findWithAdjustment(*i);
67        // prune expressions that don't coincide with
68        ResolvExpr::AltList alts = finder.get_alternatives();
69        assert( alts.size() == 1 );
70        assert(alts.front().expr != 0 );
71        current.push_back( finder.get_alternatives().front() );
72        solved_assigns.push_back( alts.front().expr->clone() );
73        //solved_assigns.back()->print(std::cerr);
74        /*} catch( ... ) {
75          continue; // no reasonable alternative found
76          }*/
77      }
78      options.add_option( current );
79
80      return true;
81    } else { // mass assignment
82      //if ( new_assigns.empty() ) return false;
83      std::list< Expression * > solved_assigns;
84      ResolvExpr::AltList solved_alts;
85      assert( currentFinder != 0 );
86
87      ResolvExpr::AltList current;
88      if ( optMass.empty() ) {
89        for ( std::list< Expression * >::size_type i = 0; i != new_assigns.size(); ++i )
90          optMass.push_back( ResolvExpr::AltList() );
91      }
92      int cnt = 0;
93      for ( std::list< Expression * >::iterator i = new_assigns.begin(); i != new_assigns.end(); ++i, cnt++ ) {
94
95        ResolvExpr::AlternativeFinder finder( currentFinder->get_indexer(), currentFinder->get_environ() );
96        finder.findWithAdjustment(*i);
97        ResolvExpr::AltList alts = finder.get_alternatives();
98        assert( alts.size() == 1 );
99        assert(alts.front().expr != 0 );
100        current.push_back( finder.get_alternatives().front() );
101        optMass[cnt].push_back( finder.get_alternatives().front() );
102        solved_assigns.push_back( alts.front().expr->clone() );
103      }
104
105      return true;
106    }
107
108    return false;
109  }
110
111  bool TupleAssignSpotter::isMVR( Expression *expr ) {
112    if ( expr->get_results().size() > 1 ) {
113      // MVR processing
114      return true;
115    }
116    return false;
117  }
118
119  bool TupleAssignSpotter::isTupleAssignment( UntypedExpr * expr, std::list<ResolvExpr::AltList> &possibilities ) {
120    if (  NameExpr *assgnop = dynamic_cast< NameExpr * >(expr->get_function()) ) {
121
122      if ( assgnop->get_name() == std::string("?=?") ) {
123
124        for ( std::list<ResolvExpr::AltList>::iterator ali = possibilities.begin(); ali != possibilities.end(); ++ali ) {
125          assert( ali->size() == 2 );
126          ResolvExpr::AltList::iterator opit = ali->begin();
127          ResolvExpr::Alternative op1 = *opit, op2 = *(++opit);
128
129          if ( pointsToTuple(op1.expr) ) { // also handles tuple vars
130            if ( isTuple( op2.expr, true ) )
131              matcher = new MultipleAssignMatcher(op1.expr, op2.expr);
132            else if ( isMVR( op2.expr ) ) {
133              // handle MVR differently
134            } else
135              // mass assignment
136              matcher = new MassAssignMatcher(op1.expr, op2.expr);
137
138            std::list< ResolvExpr::AltList > options;
139            if ( match() )
140              /*
141              if ( hasMatched ) {
142                // throw SemanticError("Ambiguous tuple assignment");
143              } else {*/
144                // Matched for the first time
145                hasMatched = true;
146                /*} */
147          } /* else if ( isTuple( op2 ) )
148            throw SemanticError("Inapplicable tuple assignment.");
149            */
150        }
151
152        if ( hasMatched ) {
153          if ( dynamic_cast<TupleAssignSpotter::MultipleAssignMatcher *>( matcher ) ) {
154            //options.print( std::cerr );
155            std::list< ResolvExpr::AltList >best = options.get_best();
156            if ( best.size() == 1 ) {
157              std::list<Expression *> solved_assigns;
158              for ( ResolvExpr::AltList::iterator i = best.front().begin(); i != best.front().end(); ++i ){
159                solved_assigns.push_back( i->expr );
160              }
161              /* assigning cost zero? */
162              currentFinder->get_alternatives().push_front( ResolvExpr::Alternative(new SolvedTupleExpr(solved_assigns/*, SolvedTupleExpr::MULTIPLE*/), currentFinder->get_environ(), ResolvExpr::Cost() ) );
163            }
164          } else {
165            assert(! optMass.empty() );
166            ResolvExpr::AltList winners;
167            for ( std::vector< ResolvExpr::AltList >::iterator i = optMass.begin(); i != optMass.end(); ++i )
168              findMinCostAlt( i->begin(), i->end(), back_inserter(winners) );
169
170            std::list< Expression *> solved_assigns;
171            for ( ResolvExpr::AltList::iterator i = winners.begin(); i != winners.end(); ++i )
172              solved_assigns.push_back( i->expr );
173            currentFinder->get_alternatives().push_front( ResolvExpr::Alternative(new SolvedTupleExpr(solved_assigns/*, SolvedTupleExpr::MASS*/), currentFinder->get_environ(), ResolvExpr::Cost() ) );
174          }
175        }
176      }
177    }
178    return hasMatched;
179  }
180
181  void TupleAssignSpotter::Matcher::init( Expression *_lhs, Expression *_rhs ) {
182    lhs.clear();
183    if (AddressExpr *addr = dynamic_cast<AddressExpr *>(_lhs) )
184      if ( TupleExpr *tuple = dynamic_cast<TupleExpr *>(addr->get_arg()) )
185        std::copy( tuple->get_exprs().begin(), tuple->get_exprs().end(), back_inserter(lhs) );
186
187    rhs.clear();
188  }
189
190  TupleAssignSpotter::Matcher::Matcher( /*TupleAssignSpotter &spot,*/ Expression *_lhs, Expression *_rhs ) /*: own_spotter(spot) */{
191    init(_lhs,_rhs);
192  }
193
194  TupleAssignSpotter::MultipleAssignMatcher::MultipleAssignMatcher( Expression *_lhs, Expression *_rhs )/* : own_spotter(spot) */{
195    init(_lhs,_rhs);
196
197    if ( TupleExpr *tuple = dynamic_cast<TupleExpr *>(_rhs) )
198      std::copy( tuple->get_exprs().begin(), tuple->get_exprs().end(), back_inserter(rhs) );
199  }
200
201  UntypedExpr *TupleAssignSpotter::Matcher::createAssgn( Expression *left, Expression *right ) {
202    if ( left && right ) {
203      std::list< Expression * > args;
204      args.push_back(new AddressExpr(left->clone()));  args.push_back(right->clone());
205      return new UntypedExpr(new NameExpr("?=?"), args);
206    } else
207      throw 0; // xxx - diagnose the problem
208  }
209
210  bool TupleAssignSpotter::MassAssignMatcher::match( std::list< Expression * > &out ) {
211    if ( lhs.empty() || (rhs.size() != 1) ) return false;
212
213    for ( std::list< Expression * >::iterator l = lhs.begin(); l != lhs.end(); l++ ) {
214      std::list< Expression * > args;
215      args.push_back( new AddressExpr(*l) );
216      args.push_back( rhs.front() );
217      out.push_back( new UntypedExpr(new NameExpr("?=?"), args) );
218    }
219
220    return true;
221  }
222
223  bool TupleAssignSpotter::MassAssignMatcher::solve( std::list< Expression * > &assigns ) {
224    /*
225    std::list< Expression * > solved_assigns;
226    ResolvExpr::AltList solved_alts;
227    assert( currentFinder != 0 );
228
229    ResolvExpr::AltList current;
230    if ( optMass.empty() ) {
231      for ( std::list< Expression * >::size_type i = 0; i != new_assigns.size(); ++i )
232        optMass.push_back( ResolvExpr::AltList() );
233    }
234    int cnt = 0;
235    for ( std::list< Expression * >::iterator i = new_assigns.begin(); i != new_assigns.end(); ++i, cnt++ ) {
236
237      ResolvExpr::AlternativeFinder finder( currentFinder->get_indexer(), currentFinder->get_environ() );
238      finder.findWithAdjustment(*i);
239      ResolvExpr::AltList alts = finder.get_alternatives();
240      assert( alts.size() == 1 );
241      assert(alts.front().expr != 0 );
242      current.push_back( finder.get_alternatives().front() );
243      optMass[cnt].push_back( finder.get_alternatives().front() );
244      solved_assigns.push_back( alts.front().expr->clone() );
245    }
246    */
247    return true;
248  }
249
250  bool TupleAssignSpotter::MultipleAssignMatcher::match( std::list< Expression * > &out ) {
251    // need more complicated matching
252    if ( lhs.size() == rhs.size() ) {
253      zipWith( lhs.begin(), lhs.end(), rhs.begin(), rhs.end(), back_inserter(out), TupleAssignSpotter::Matcher::createAssgn );
254      return true;
255    } //else
256    //std::cerr << "The length of (left, right) is: (" << lhs.size() << "," << rhs.size() << ")" << std::endl;*/
257    return false;
258  }
259
260  bool TupleAssignSpotter::MultipleAssignMatcher::solve( std::list< Expression * > &assigns ) {
261    /*
262    std::list< Expression * > solved_assigns;
263    ResolvExpr::AltList solved_alts;
264    assert( currentFinder != 0 );
265
266    ResolvExpr::AltList current;
267    for ( std::list< Expression * >::iterator i = new_assigns.begin(); i != new_assigns.end(); ++i ) {
268      //try {
269      ResolvExpr::AlternativeFinder finder( currentFinder->get_indexer(), currentFinder->get_environ() );
270      finder.findWithAdjustment(*i);
271      // prune expressions that don't coincide with
272      ResolvExpr::AltList alts = finder.get_alternatives();
273      assert( alts.size() == 1 );
274      assert(alts.front().expr != 0 );
275      current.push_back( finder.get_alternatives().front() );
276      solved_assigns.push_back( alts.front().expr->clone() );
277      //solved_assigns.back()->print(std::cerr);
278      //} catch( ... ) {
279      //continue; // no reasonable alternative found
280      //}
281    }
282    options.add_option( current );
283    */
284
285    return true;
286  }
287
288  void TupleAssignSpotter::Options::add_option( ResolvExpr::AltList &opt ) {
289    using namespace std;
290
291    options.push_back( opt );
292    /*
293      vector< Cost > costs;
294      costs.reserve( opt.size() );
295      transform( opt.begin(), opt.end(), back_inserter(costs), ptr_fun(extract_cost) );
296    */
297    // transpose matrix
298    if ( costMatrix.empty() )
299      for ( unsigned int i = 0; i< opt.size(); ++i)
300        costMatrix.push_back( vector<ResolvExpr::Cost>() );
301
302    int cnt = 0;
303    for ( ResolvExpr::AltList::iterator i = opt.begin(); i != opt.end(); ++i, cnt++ )
304      costMatrix[cnt].push_back( i->cost );
305
306    return;
307  }
308
309  std::list< ResolvExpr::AltList > TupleAssignSpotter::Options::get_best() {
310    using namespace std;
311    using namespace ResolvExpr;
312    list< ResolvExpr::AltList > ret;
313    list< multiset<int> > solns;
314    for ( vector< vector<Cost> >::iterator i = costMatrix.begin(); i != costMatrix.end(); ++i ) {
315      list<int> current;
316      findMinCost( i->begin(), i->end(), back_inserter(current) );
317      solns.push_back( multiset<int>(current.begin(), current.end()) );
318    }
319    // need to combine
320    multiset<int> result;
321    lift_intersection( solns.begin(), solns.end(), inserter( result, result.begin() ) );
322    if ( result.size() != 1 )
323      throw SemanticError("Ambiguous tuple expression");
324    ret.push_back(get_option( *(result.begin() )));
325    return ret;
326  }
327
328  void TupleAssignSpotter::Options::print( std::ostream &ostr ) {
329    using namespace std;
330
331    for ( vector< vector < ResolvExpr::Cost > >::iterator i = costMatrix.begin(); i != costMatrix.end(); ++i ) {
332      for ( vector < ResolvExpr::Cost >::iterator j = i->begin(); j != i->end(); ++j )
333        ostr << *j << " " ;
334      ostr << std::endl;
335    }
336   
337    return;
338  }
339
340  ResolvExpr::Cost extract_cost( ResolvExpr::Alternative &alt ) {
341    return alt.cost;
342  }
343
344  template< typename InputIterator, typename OutputIterator >
345  void
346  TupleAssignSpotter::Options::findMinCost( InputIterator begin, InputIterator end, OutputIterator out )
347  {
348    using namespace ResolvExpr;
349    std::list<int> alternatives;
350
351    // select the alternatives that have the minimum parameter cost
352    Cost minCost = Cost::infinity;
353    unsigned int index = 0;
354    for ( InputIterator i = begin; i != end; ++i, index++ ) {
355      if ( *i < minCost ) {
356        minCost = *i;
357        alternatives.clear();
358        alternatives.push_back( index );
359      } else if ( *i == minCost ) {
360        alternatives.push_back( index );
361      }
362    }
363    std::copy( alternatives.begin(), alternatives.end(), out );
364  }
365
366  template< class InputIterator, class OutputIterator >
367  void TupleAssignSpotter::Options::lift_intersection( InputIterator begin, InputIterator end, OutputIterator out ){
368    if ( begin == end ) return;
369    InputIterator test = begin;
370
371    if (++test == end)
372      { copy(begin->begin(), begin->end(), out); return; }
373
374
375    std::multiset<int> cur; // InputIterator::value_type::value_type
376    copy( begin->begin(), begin->end(), inserter( cur, cur.begin() ) );
377
378    while ( test != end ) {
379      std::multiset<int> temp;
380      set_intersection( cur.begin(), cur.end(), test->begin(), test->end(), inserter(temp,temp.begin()) );
381      cur.clear();
382      copy( temp.begin(), temp.end(), inserter(cur,cur.begin()));
383      ++test;
384    }
385
386    copy( cur.begin(), cur.end(), out );
387    return;
388  }
389
390
391  ResolvExpr::AltList TupleAssignSpotter::Options::get_option( std::list< ResolvExpr::AltList >::size_type index ) {
392    if ( index >= options.size() )
393      throw 0; // XXX
394    std::list< ResolvExpr::AltList >::iterator it = options.begin();
395    for ( std::list< ResolvExpr::AltList >::size_type i = 0; i < index; ++i, ++it );
396    return *it;
397  }
398
399
400} // namespace Tuples
Note: See TracBrowser for help on using the repository browser.