source: src/ResolvExpr/CandidateFinder.cpp@ 4b7cce6

ADT arm-eh ast-experimental enum forall-pointer-decay jacob/cs343-translation jenkins-sandbox new-ast new-ast-unique-expr pthread-emulation qualifiedEnum
Last change on this file since 4b7cce6 was 4b7cce6, checked in by Aaron Moss <a3moss@…>, 6 years ago

Fill in CandidateFinder boilerplate in resolver port
  • Property mode set to 100644
File size: 17.0 KB
Line 
1//
2// Cforall Version 1.0.0 Copyright (C) 2015 University of Waterloo
3//
4// The contents of this file are covered under the licence agreement in the
5// file "LICENCE" distributed with Cforall.
6//
7// CandidateFinder.cpp --
8//
9// Author : Aaron B. Moss
10// Created On : Wed Jun 5 14:30:00 2019
11// Last Modified By : Aaron B. Moss
12// Last Modified On : Wed Jun 5 14:30:00 2019
13// Update Count : 1
14//
15
16#include "CandidateFinder.hpp"
17
18#include <iterator> // for back_inserter
19#include <sstream>
20#include <string>
21#include <unordered_map>
22
23#include "Candidate.hpp"
24#include "CompilationState.h"
25#include "Cost.h"
26#include "Resolver.h"
27#include "SatisfyAssertions.hpp"
28#include "typeops.h" // for adjustExprType
29#include "Unify.h"
30#include "AST/Expr.hpp"
31#include "AST/Node.hpp"
32#include "AST/Pass.hpp"
33#include "AST/Print.hpp"
34#include "AST/SymbolTable.hpp"
35#include "SymTab/Mangler.h"
36
37#define PRINT( text ) if ( resolvep ) { text }
38
39namespace ResolvExpr {
40
41namespace {
42
43 /// Actually visits expressions to find their candidate interpretations
44 struct Finder final : public ast::WithShortCircuiting {
45 CandidateFinder & selfFinder;
46 const ast::SymbolTable & symtab;
47 CandidateList & candidates;
48 const ast::TypeEnvironment & tenv;
49 ast::ptr< ast::Type > & targetType;
50
51 Finder( CandidateFinder & f )
52 : selfFinder( f ), symtab( f.symtab ), candidates( f.candidates ), tenv( f.env ),
53 targetType( f.targetType ) {}
54
55 void previsit( const ast::Node * ) { visit_children = false; }
56
57 /// Convenience to add candidate to list
58 template<typename... Args>
59 void addCandidate( Args &&... args ) {
60 candidates.emplace_back( new Candidate{ std::forward<Args>( args )... } );
61 }
62
63 void postvisit( const ast::ApplicationExpr * applicationExpr ) {
64 addCandidate( applicationExpr, tenv );
65 }
66
67 void postvisit( const ast::UntypedExpr * untypedExpr ) {
68 #warning unimplemented
69 (void)untypedExpr;
70 assert(false);
71 }
72
73 /// true if expression is an lvalue
74 static bool isLvalue( const ast::Expr * x ) {
75 return x->result && ( x->result->is_lvalue() || x->result.as< ast::ReferenceType >() );
76 }
77
78 void postvisit( const ast::AddressExpr * addressExpr ) {
79 CandidateFinder finder{ symtab, tenv };
80 finder.find( addressExpr->arg );
81 for ( CandidateRef & r : finder.candidates ) {
82 if ( ! isLvalue( r->expr ) ) continue;
83 addCandidate( *r, new ast::AddressExpr{ addressExpr->location, r->expr } );
84 }
85 }
86
87 void postvisit( const ast::LabelAddressExpr * labelExpr ) {
88 addCandidate( labelExpr, tenv );
89 }
90
91 void postvisit( const ast::CastExpr * castExpr ) {
92 #warning unimplemented
93 (void)castExpr;
94 assert(false);
95 }
96
97 void postvisit( const ast::VirtualCastExpr * castExpr ) {
98 assertf( castExpr->result, "Implicit virtual cast targets not yet supported." );
99 CandidateFinder finder{ symtab, tenv };
100 // don't prune here, all alternatives guaranteed to have same type
101 finder.find( castExpr->arg, ResolvMode::withoutPrune() );
102 for ( CandidateRef & r : finder.candidates ) {
103 addCandidate(
104 *r, new ast::VirtualCastExpr{ castExpr->location, r->expr, castExpr->result } );
105 }
106 }
107
108 void postvisit( const ast::UntypedMemberExpr * memberExpr ) {
109 #warning unimplemented
110 (void)memberExpr;
111 assert(false);
112 }
113
114 void postvisit( const ast::MemberExpr * memberExpr ) {
115 addCandidate( memberExpr, tenv );
116 }
117
118 void postvisit( const ast::NameExpr * variableExpr ) {
119 #warning unimplemented
120 (void)variableExpr;
121 assert(false);
122 }
123
124 void postvisit( const ast::VariableExpr * variableExpr ) {
125 // not sufficient to just pass `variableExpr` here, type might have changed since
126 // creation
127 addCandidate(
128 new ast::VariableExpr{ variableExpr->location, variableExpr->var }, tenv );
129 }
130
131 void postvisit( const ast::ConstantExpr * constantExpr ) {
132 addCandidate( constantExpr, tenv );
133 }
134
135 void postvisit( const ast::SizeofExpr * sizeofExpr ) {
136 #warning unimplemented
137 (void)sizeofExpr;
138 assert(false);
139 }
140
141 void postvisit( const ast::AlignofExpr * alignofExpr ) {
142 #warning unimplemented
143 (void)alignofExpr;
144 assert(false);
145 }
146
147 void postvisit( const ast::UntypedOffsetofExpr * offsetofExpr ) {
148 #warning unimplemented
149 (void)offsetofExpr;
150 assert(false);
151 }
152
153 void postvisit( const ast::OffsetofExpr * offsetofExpr ) {
154 addCandidate( offsetofExpr, tenv );
155 }
156
157 void postvisit( const ast::OffsetPackExpr * offsetPackExpr ) {
158 addCandidate( offsetPackExpr, tenv );
159 }
160
161 void postvisit( const ast::LogicalExpr * logicalExpr ) {
162 CandidateFinder finder1{ symtab, tenv };
163 finder1.find( logicalExpr->arg1, ResolvMode::withAdjustment() );
164 if ( finder1.candidates.empty() ) return;
165
166 CandidateFinder finder2{ symtab, tenv };
167 finder2.find( logicalExpr->arg2, ResolvMode::withAdjustment() );
168 if ( finder2.candidates.empty() ) return;
169
170 for ( const CandidateRef & r1 : finder1.candidates ) {
171 for ( const CandidateRef & r2 : finder2.candidates ) {
172 ast::TypeEnvironment env{ r1->env };
173 env.simpleCombine( r2->env );
174 ast::OpenVarSet open{ r1->open };
175 mergeOpenVars( open, r2->open );
176 ast::AssertionSet need;
177 mergeAssertionSet( need, r1->need );
178 mergeAssertionSet( need, r2->need );
179
180 addCandidate(
181 new ast::LogicalExpr{
182 logicalExpr->location, r1->expr, r2->expr, logicalExpr->isAnd },
183 std::move( env ), std::move( open ), std::move( need ),
184 r1->cost + r2->cost );
185 }
186 }
187 }
188
189 void postvisit( const ast::ConditionalExpr * conditionalExpr ) {
190 // candidates for condition
191 CandidateFinder finder1{ symtab, tenv };
192 finder1.find( conditionalExpr->arg1, ResolvMode::withAdjustment() );
193 if ( finder1.candidates.empty() ) return;
194
195 // candidates for true result
196 CandidateFinder finder2{ symtab, tenv };
197 finder2.find( conditionalExpr->arg2, ResolvMode::withAdjustment() );
198 if ( finder2.candidates.empty() ) return;
199
200 // candidates for false result
201 CandidateFinder finder3{ symtab, tenv };
202 finder3.find( conditionalExpr->arg3, ResolvMode::withAdjustment() );
203 if ( finder3.candidates.empty() ) return;
204
205 for ( const CandidateRef & r1 : finder1.candidates ) {
206 for ( const CandidateRef & r2 : finder2.candidates ) {
207 for ( const CandidateRef & r3 : finder3.candidates ) {
208 ast::TypeEnvironment env{ r1->env };
209 env.simpleCombine( r2->env );
210 env.simpleCombine( r3->env );
211 ast::OpenVarSet open{ r1->open };
212 mergeOpenVars( open, r2->open );
213 mergeOpenVars( open, r3->open );
214 ast::AssertionSet need;
215 mergeAssertionSet( need, r1->need );
216 mergeAssertionSet( need, r2->need );
217 mergeAssertionSet( need, r3->need );
218 ast::AssertionSet have;
219
220 // unify true and false results, then infer parameters to produce new
221 // candidates
222 ast::ptr< ast::Type > common;
223 if (
224 unify(
225 r2->expr->result, r3->expr->result, env, need, have, open, symtab,
226 common )
227 ) {
228 #warning unimplemented
229 assert(false);
230 }
231 }
232 }
233 }
234 }
235
236 void postvisit( const ast::CommaExpr * commaExpr ) {
237 ast::TypeEnvironment env{ tenv };
238 ast::ptr< ast::Expr > arg1 = resolveInVoidContext( commaExpr->arg1, symtab, env );
239
240 CandidateFinder finder2{ symtab, env };
241 finder2.find( commaExpr->arg2, ResolvMode::withAdjustment() );
242
243 for ( const CandidateRef & r2 : finder2.candidates ) {
244 addCandidate( *r2, new ast::CommaExpr{ commaExpr->location, arg1, r2->expr } );
245 }
246 }
247
248 void postvisit( const ast::ImplicitCopyCtorExpr * ctorExpr ) {
249 addCandidate( ctorExpr, tenv );
250 }
251
252 void postvisit( const ast::ConstructorExpr * ctorExpr ) {
253 CandidateFinder finder{ symtab, tenv };
254 finder.find( ctorExpr->callExpr, ResolvMode::withoutPrune() );
255 for ( CandidateRef & r : finder.candidates ) {
256 addCandidate( *r, new ast::ConstructorExpr{ ctorExpr->location, r->expr } );
257 }
258 }
259
260 void postvisit( const ast::RangeExpr * rangeExpr ) {
261 // resolve low and high, accept candidates where low and high types unify
262 CandidateFinder finder1{ symtab, tenv };
263 finder1.find( rangeExpr->low, ResolvMode::withAdjustment() );
264 if ( finder1.candidates.empty() ) return;
265
266 CandidateFinder finder2{ symtab, tenv };
267 finder2.find( rangeExpr->high, ResolvMode::withAdjustment() );
268 if ( finder2.candidates.empty() ) return;
269
270 for ( const CandidateRef & r1 : finder1.candidates ) {
271 for ( const CandidateRef & r2 : finder2.candidates ) {
272 ast::TypeEnvironment env{ r1->env };
273 env.simpleCombine( r2->env );
274 ast::OpenVarSet open{ r1->open };
275 mergeOpenVars( open, r2->open );
276 ast::AssertionSet need;
277 mergeAssertionSet( need, r1->need );
278 mergeAssertionSet( need, r2->need );
279 ast::AssertionSet have;
280
281 ast::ptr< ast::Type > common;
282 if (
283 unify(
284 r1->expr->result, r2->expr->result, env, need, have, open, symtab,
285 common )
286 ) {
287 ast::RangeExpr * newExpr =
288 new ast::RangeExpr{ rangeExpr->location, r1->expr, r2->expr };
289 newExpr->result = common ? common : r1->expr->result;
290
291 #warning unimplemented
292 assert(false);
293 }
294 }
295 }
296 }
297
298 void postvisit( const ast::UntypedTupleExpr * tupleExpr ) {
299 std::vector< CandidateFinder > subCandidates =
300 selfFinder.findSubExprs( tupleExpr->exprs );
301 std::vector< CandidateList > possibilities;
302 combos( subCandidates.begin(), subCandidates.end(), back_inserter( possibilities ) );
303
304 for ( const CandidateList & subs : possibilities ) {
305 std::vector< ast::ptr< ast::Expr > > exprs;
306 exprs.reserve( subs.size() );
307 for ( const CandidateRef & sub : subs ) { exprs.emplace_back( sub->expr ); }
308
309 ast::TypeEnvironment env;
310 ast::OpenVarSet open;
311 ast::AssertionSet need;
312 for ( const CandidateRef & sub : subs ) {
313 env.simpleCombine( sub->env );
314 mergeOpenVars( open, sub->open );
315 mergeAssertionSet( need, sub->need );
316 }
317
318 addCandidate(
319 new ast::TupleExpr{ tupleExpr->location, std::move( exprs ) },
320 std::move( env ), std::move( open ), std::move( need ), sumCost( subs ) );
321 }
322 }
323
324 void postvisit( const ast::TupleExpr * tupleExpr ) {
325 addCandidate( tupleExpr, tenv );
326 }
327
328 void postvisit( const ast::TupleIndexExpr * tupleExpr ) {
329 addCandidate( tupleExpr, tenv );
330 }
331
332 void postvisit( const ast::TupleAssignExpr * tupleExpr ) {
333 addCandidate( tupleExpr, tenv );
334 }
335
336 void postvisit( const ast::UniqueExpr * unqExpr ) {
337 CandidateFinder finder{ symtab, tenv };
338 finder.find( unqExpr->expr, ResolvMode::withAdjustment() );
339 for ( CandidateRef & r : finder.candidates ) {
340 // ensure that the the id is passed on so that the expressions are "linked"
341 addCandidate( *r, new ast::UniqueExpr{ unqExpr->location, r->expr, unqExpr->id } );
342 }
343 }
344
345 void postvisit( const ast::StmtExpr * stmtExpr ) {
346 #warning unimplemented
347 (void)stmtExpr;
348 assert(false);
349 }
350
351 void postvisit( const ast::UntypedInitExpr * initExpr ) {
352 #warning unimplemented
353 (void)initExpr;
354 assert(false);
355 }
356
357 void postvisit( const ast::InitExpr * ) {
358 assertf( false, "CandidateFinder should never see a resolved InitExpr." );
359 }
360
361 void postvisit( const ast::DeletedExpr * ) {
362 assertf( false, "CandidateFinder should never see a DeletedExpr." );
363 }
364
365 void postvisit( const ast::GenericExpr * ) {
366 assertf( false, "_Generic is not yet supported." );
367 }
368 };
369
370 /// Prunes a list of candidates down to those that have the minimum conversion cost for a given
371 /// return type. Skips ambiguous candidates.
372 CandidateList pruneCandidates( CandidateList & candidates ) {
373 struct PruneStruct {
374 CandidateRef candidate;
375 bool ambiguous;
376
377 PruneStruct() = default;
378 PruneStruct( const CandidateRef & c ) : candidate( c ), ambiguous( false ) {}
379 };
380
381 // find lowest-cost candidate for each type
382 std::unordered_map< std::string, PruneStruct > selected;
383 for ( CandidateRef & candidate : candidates ) {
384 std::string mangleName;
385 {
386 ast::ptr< ast::Type > newType = candidate->expr->result;
387 candidate->env.apply( newType );
388 mangleName = Mangle::mangle( newType );
389 }
390
391 auto found = selected.find( mangleName );
392 if ( found != selected.end() ) {
393 if ( candidate->cost < found->second.candidate->cost ) {
394 PRINT(
395 std::cerr << "cost " << candidate->cost << " beats "
396 << found->second.candidate->cost << std::endl;
397 )
398
399 found->second = PruneStruct{ candidate };
400 } else if ( candidate->cost == found->second.candidate->cost ) {
401 // if one of the candidates contains a deleted identifier, can pick the other,
402 // since deleted expressions should not be ambiguous if there is another option
403 // that is at least as good
404 if ( findDeletedExpr( candidate->expr ) ) {
405 // do nothing
406 PRINT( std::cerr << "candidate is deleted" << std::endl; )
407 } else if ( findDeletedExpr( found->second.candidate->expr ) ) {
408 PRINT( std::cerr << "current is deleted" << std::endl; )
409 found->second = PruneStruct{ candidate };
410 } else {
411 PRINT( std::cerr << "marking ambiguous" << std::endl; )
412 found->second.ambiguous = true;
413 }
414 } else {
415 PRINT(
416 std::cerr << "cost " << candidate->cost << " loses to "
417 << found->second.candidate->cost << std::endl;
418 )
419 }
420 } else {
421 selected.emplace_hint( found, mangleName, candidate );
422 }
423 }
424
425 // report unambiguous min-cost candidates
426 CandidateList out;
427 for ( auto & target : selected ) {
428 if ( target.second.ambiguous ) continue;
429
430 CandidateRef cand = target.second.candidate;
431
432 ast::ptr< ast::Type > newResult = cand->expr->result;
433 cand->env.applyFree( newResult );
434 cand->expr = ast::mutate_field(
435 cand->expr.get(), &ast::Expr::result, std::move( newResult ) );
436
437 out.emplace_back( cand );
438 }
439 return out;
440 }
441
442 /// Returns a list of alternatives with the minimum cost in the given list
443 CandidateList findMinCost( const CandidateList & candidates ) {
444 CandidateList out;
445 Cost minCost = Cost::infinity;
446 for ( const CandidateRef & r : candidates ) {
447 if ( r->cost < minCost ) {
448 minCost = r->cost;
449 out.clear();
450 out.emplace_back( r );
451 } else if ( r->cost == minCost ) {
452 out.emplace_back( r );
453 }
454 }
455 return out;
456 }
457
458} // anonymous namespace
459
460void CandidateFinder::find( const ast::Expr * expr, ResolvMode mode ) {
461 // Find alternatives for expression
462 ast::Pass<Finder> finder{ *this };
463 expr->accept( finder );
464
465 if ( mode.failFast && candidates.empty() ) {
466 SemanticError( expr, "No reasonable alternatives for expression " );
467 }
468
469 if ( mode.satisfyAssns || mode.prune ) {
470 // trim candidates to just those where the assertions are satisfiable
471 // - necessary pre-requisite to pruning
472 CandidateList satisfied;
473 std::vector< std::string > errors;
474 for ( auto & candidate : candidates ) {
475 satisfyAssertions( *candidate, symtab, satisfied, errors );
476 }
477
478 // fail early if none such
479 if ( mode.failFast && satisfied.empty() ) {
480 std::ostringstream stream;
481 stream << "No alternatives with satisfiable assertions for " << expr << "\n";
482 for ( const auto& err : errors ) {
483 stream << err;
484 }
485 SemanticError( expr->location, stream.str() );
486 }
487
488 // reset candidates
489 candidates = std::move( satisfied );
490 }
491
492 if ( mode.prune ) {
493 // trim candidates to single best one
494 PRINT(
495 std::cerr << "alternatives before prune:" << std::endl;
496 print( std::cerr, candidates );
497 )
498
499 CandidateList pruned = pruneCandidates( candidates );
500
501 if ( mode.failFast && pruned.empty() ) {
502 std::ostringstream stream;
503 CandidateList winners = findMinCost( candidates );
504 stream << "Cannot choose between " << winners.size() << " alternatives for "
505 "expression\n";
506 ast::print( stream, expr );
507 stream << " Alternatives are:\n";
508 print( stream, winners, 1 );
509 SemanticError( expr->location, stream.str() );
510 }
511
512 auto oldsize = candidates.size();
513 candidates = std::move( pruned );
514
515 PRINT(
516 std::cerr << "there are " << oldsize << " alternatives before elimination" << std::endl;
517 )
518 PRINT(
519 std::cerr << "there are " << candidates.size() << " alternatives after elimination"
520 << std::endl;
521 )
522 }
523
524 // adjust types after pruning so that types substituted by pruneAlternatives are correctly
525 // adjusted
526 if ( mode.adjust ) {
527 for ( CandidateRef & r : candidates ) {
528 r->expr = ast::mutate_field(
529 r->expr.get(), &ast::Expr::result,
530 adjustExprType( r->expr->result, r->env, symtab ) );
531 }
532 }
533
534 // Central location to handle gcc extension keyword, etc. for all expressions
535 for ( CandidateRef & r : candidates ) {
536 if ( r->expr->extension != expr->extension ) {
537 r->expr.get_and_mutate()->extension = expr->extension;
538 }
539 }
540}
541
542std::vector< CandidateFinder > CandidateFinder::findSubExprs(
543 const std::vector< ast::ptr< ast::Expr > > & xs
544) {
545 std::vector< CandidateFinder > out;
546
547 for ( const auto & x : xs ) {
548 out.emplace_back( symtab, env );
549 out.back().find( x, ResolvMode::withAdjustment() );
550
551 PRINT(
552 std::cerr << "findSubExprs" << std::endl;
553 print( std::cerr, out.back().candidates );
554 )
555 }
556
557 return out;
558}
559
560} // namespace ResolvExpr
561
562// Local Variables: //
563// tab-width: 4 //
564// mode: c++ //
565// compile-command: "make install" //
566// End: //
Note: See TracBrowser for help on using the repository browser.