source: translator/Tuples/TupleAssignment.cc@ fe3b61b

ADT aaron-thesis arm-eh ast-experimental cleanup-dtors ctor deferred_resn demangler enum forall-pointer-decay gc_noraii jacob/cs343-translation jenkins-sandbox memory new-ast new-ast-unique-expr new-env no_list persistent-indexer pthread-emulation qualifiedEnum resolv-new string with_gc
Last change on this file since fe3b61b was 51b73452, checked in by Peter A. Buhr <pabuhr@…>, 11 years ago

initial commit
  • Property mode set to 100644
File size: 13.8 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.