source: src/ResolvExpr/CandidateFinder.cpp@ 462a7c7

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 462a7c7 was 432ce7a, checked in by Aaron Moss <a3moss@…>, 6 years ago

Port CandidateFinder::postvisit for UntypedExpr, stub dependencies
  • Property mode set to 100644
File size: 23.8 KB
RevLine 
[99d4584]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
[432ce7a]18#include <deque>
[4b7cce6]19#include <iterator> // for back_inserter
[396037d]20#include <sstream>
[d57e349]21#include <string>
22#include <unordered_map>
[432ce7a]23#include <vector>
[396037d]24
25#include "Candidate.hpp"
26#include "CompilationState.h"
[d57e349]27#include "Cost.h"
[432ce7a]28#include "ExplodedArg.hpp"
[d57e349]29#include "Resolver.h"
[396037d]30#include "SatisfyAssertions.hpp"
[d57e349]31#include "typeops.h" // for adjustExprType
[4b7cce6]32#include "Unify.h"
[99d4584]33#include "AST/Expr.hpp"
[396037d]34#include "AST/Node.hpp"
35#include "AST/Pass.hpp"
[d57e349]36#include "AST/Print.hpp"
[4b7cce6]37#include "AST/SymbolTable.hpp"
[432ce7a]38#include "AST/Type.hpp"
[d57e349]39#include "SymTab/Mangler.h"
[432ce7a]40#include "Tuples/Tuples.h" // for handleTupleAssignment
[396037d]41
42#define PRINT( text ) if ( resolvep ) { text }
[99d4584]43
44namespace ResolvExpr {
45
[396037d]46namespace {
47
[432ce7a]48 /// First index is which argument, second is which alternative, third is which exploded element
49 using ExplodedArgs_new = std::deque< std::vector< ExplodedArg > >;
50
51 /// Returns a list of alternatives with the minimum cost in the given list
52 CandidateList findMinCost( const CandidateList & candidates ) {
53 CandidateList out;
54 Cost minCost = Cost::infinity;
55 for ( const CandidateRef & r : candidates ) {
56 if ( r->cost < minCost ) {
57 minCost = r->cost;
58 out.clear();
59 out.emplace_back( r );
60 } else if ( r->cost == minCost ) {
61 out.emplace_back( r );
62 }
63 }
64 return out;
65 }
66
67 /// Computes conversion cost for a given candidate
68 Cost computeApplicationConversionCost(
69 const CandidateRef & cand, const ast::SymbolTable & symtab
70 ) {
71 #warning unimplemented
72 (void)cand; (void)symtab;
73 assert(false);
74 return Cost::infinity;
75 }
76
[396037d]77 /// Actually visits expressions to find their candidate interpretations
[4b7cce6]78 struct Finder final : public ast::WithShortCircuiting {
79 CandidateFinder & selfFinder;
[396037d]80 const ast::SymbolTable & symtab;
81 CandidateList & candidates;
82 const ast::TypeEnvironment & tenv;
83 ast::ptr< ast::Type > & targetType;
84
85 Finder( CandidateFinder & f )
[4b7cce6]86 : selfFinder( f ), symtab( f.symtab ), candidates( f.candidates ), tenv( f.env ),
[396037d]87 targetType( f.targetType ) {}
88
[4b7cce6]89 void previsit( const ast::Node * ) { visit_children = false; }
90
91 /// Convenience to add candidate to list
92 template<typename... Args>
93 void addCandidate( Args &&... args ) {
94 candidates.emplace_back( new Candidate{ std::forward<Args>( args )... } );
95 }
96
97 void postvisit( const ast::ApplicationExpr * applicationExpr ) {
98 addCandidate( applicationExpr, tenv );
99 }
100
[432ce7a]101 /// Builds a list of candidates for a function, storing them in out
102 void makeFunctionCandidates(
103 const CandidateRef & func, const ast::FunctionType * funcType,
104 const ExplodedArgs_new & args, CandidateList & out
105 ) {
[4b7cce6]106 #warning unimplemented
[432ce7a]107 (void)func; (void)funcType; (void)args; (void)out;
[4b7cce6]108 assert(false);
109 }
110
[432ce7a]111 /// Adds implicit struct-conversions to the alternative list
112 void addAnonConversions( const CandidateRef & cand ) {
113 #warning unimplemented
114 (void)cand;
115 assert(false);
116 }
117
118 void postvisit( const ast::UntypedExpr * untypedExpr ) {
119 CandidateFinder funcFinder{ symtab, tenv };
120 funcFinder.find( untypedExpr->func, ResolvMode::withAdjustment() );
121 // short-circuit if no candidates
122 if ( funcFinder.candidates.empty() ) return;
123
124 std::vector< CandidateFinder > argCandidates =
125 selfFinder.findSubExprs( untypedExpr->args );
126
127 // take care of possible tuple assignments
128 // if not tuple assignment, handled as normal function call
129 Tuples::handleTupleAssignment( selfFinder, untypedExpr, argCandidates );
130
131 // find function operators
132 ast::ptr< ast::Expr > opExpr = new ast::NameExpr{ untypedExpr->location, "?()" };
133 CandidateFinder opFinder{ symtab, tenv };
134 // okay if there aren't any function operations
135 opFinder.find( opExpr, ResolvMode::withoutFailFast() );
136 PRINT(
137 std::cerr << "known function ops:" << std::endl;
138 print( std::cerr, opFinder.candidates, 1 );
139 )
140
141 // pre-explode arguments
142 ExplodedArgs_new argExpansions;
143 for ( const CandidateFinder & args : argCandidates ) {
144 argExpansions.emplace_back();
145 auto & argE = argExpansions.back();
146 for ( const CandidateRef & arg : args ) { argE.emplace_back( *arg, symtab ); }
147 }
148
149 // Find function matches
150 CandidateList found;
151 SemanticErrorException errors;
152 for ( CandidateRef & func : funcFinder ) {
153 try {
154 PRINT(
155 std::cerr << "working on alternative:" << std::endl;
156 print( std::cerr, *func, 2 );
157 )
158
159 // check if the type is a pointer to function
160 const ast::Type * funcResult = func->expr->result->stripReferences();
161 if ( auto pointer = dynamic_cast< const ast::PointerType * >( funcResult ) ) {
162 if ( auto function = pointer->base.as< ast::FunctionType >() ) {
163 CandidateRef newFunc{ new Candidate{ *func } };
164 newFunc->expr =
165 referenceToRvalueConversion( newFunc->expr, newFunc->cost );
166 makeFunctionCandidates( newFunc, function, argExpansions, found );
167 }
168 } else if (
169 auto inst = dynamic_cast< const ast::TypeInstType * >( funcResult )
170 ) {
171 if ( const ast::EqvClass * clz = func->env.lookup( inst->name ) ) {
172 if ( auto function = clz->bound.as< ast::FunctionType >() ) {
173 CandidateRef newFunc{ new Candidate{ *func } };
174 newFunc->expr =
175 referenceToRvalueConversion( newFunc->expr, newFunc->cost );
176 makeFunctionCandidates( newFunc, function, argExpansions, found );
177 }
178 }
179 }
180 } catch ( SemanticErrorException & e ) { errors.append( e ); }
181 }
182
183 // Find matches on function operators `?()`
184 if ( ! opFinder.candidates.empty() ) {
185 // add exploded function alternatives to front of argument list
186 std::vector< ExplodedArg > funcE;
187 funcE.reserve( funcFinder.candidates.size() );
188 for ( const CandidateRef & func : funcFinder ) {
189 funcE.emplace_back( *func, symtab );
190 }
191 argExpansions.emplace_front( std::move( funcE ) );
192
193 for ( const CandidateRef & op : opFinder ) {
194 try {
195 // check if type is pointer-to-function
196 const ast::Type * opResult = op->expr->result->stripReferences();
197 if ( auto pointer = dynamic_cast< const ast::PointerType * >( opResult ) ) {
198 if ( auto function = pointer->base.as< ast::FunctionType >() ) {
199 CandidateRef newOp{ new Candidate{ *op} };
200 newOp->expr =
201 referenceToRvalueConversion( newOp->expr, newOp->cost );
202 makeFunctionCandidates( newOp, function, argExpansions, found );
203 }
204 }
205 } catch ( SemanticErrorException & e ) { errors.append( e ); }
206 }
207 }
208
209 // Implement SFINAE; resolution errors are only errors if there aren't any non-error
210 // candidates
211 if ( found.empty() && ! errors.isEmpty() ) { throw errors; }
212
213 // Compute conversion costs
214 for ( CandidateRef & withFunc : found ) {
215 Cost cvtCost = computeApplicationConversionCost( withFunc, symtab );
216
217 PRINT(
218 auto appExpr = withFunc->expr.strict_as< ast::ApplicationExpr >();
219 auto pointer = appExpr->func->result.strict_as< ast::PointerType >();
220 auto function = pointer->base.strict_as< ast::FunctionType >();
221
222 std::cerr << "Case +++++++++++++ " << appExpr->func << std::endl;
223 std::cerr << "parameters are:" << std::endl;
224 ast::printAll( std::cerr, function->params, 2 );
225 std::cerr << "arguments are:" << std::endl;
226 ast::printAll( std::cerr, appExpr->args, 2 );
227 std::cerr << "bindings are:" << std::endl;
228 ast::print( std::cerr, withFunc->env, 2 );
229 std::cerr << "cost is: " << withFunc->cost << std::endl;
230 std::cerr << "cost of conversion is:" << cvtCost << std::endl;
231 )
232
233 if ( cvtCost != Cost::infinity ) {
234 withFunc->cvtCost = cvtCost;
235 candidates.emplace_back( std::move( withFunc ) );
236 }
237 }
238 found = std::move( candidates );
239
240 // use a new list so that candidates are not examined by addAnonConversions twice
241 CandidateList winners = findMinCost( found );
242 promoteCvtCost( winners );
243
244 // function may return a struct/union value, in which case we need to add candidates
245 // for implicit conversions to each of the anonymous members, which must happen after
246 // `findMinCost`, since anon conversions are never the cheapest
247 for ( const CandidateRef & c : winners ) {
248 addAnonConversions( c );
249 }
250 spliceBegin( candidates, winners );
251
252 if ( candidates.empty() && targetType && ! targetType->isVoid() ) {
253 // If resolution is unsuccessful with a target type, try again without, since it
254 // will sometimes succeed when it wouldn't with a target type binding.
255 // For example:
256 // forall( otype T ) T & ?[]( T *, ptrdiff_t );
257 // const char * x = "hello world";
258 // unsigned char ch = x[0];
259 // Fails with simple return type binding (xxx -- check this!) as follows:
260 // * T is bound to unsigned char
261 // * (x: const char *) is unified with unsigned char *, which fails
262 // xxx -- fix this better
263 targetType = nullptr;
264 postvisit( untypedExpr );
265 }
266 }
267
[4b7cce6]268 /// true if expression is an lvalue
269 static bool isLvalue( const ast::Expr * x ) {
270 return x->result && ( x->result->is_lvalue() || x->result.as< ast::ReferenceType >() );
271 }
272
273 void postvisit( const ast::AddressExpr * addressExpr ) {
274 CandidateFinder finder{ symtab, tenv };
275 finder.find( addressExpr->arg );
276 for ( CandidateRef & r : finder.candidates ) {
277 if ( ! isLvalue( r->expr ) ) continue;
278 addCandidate( *r, new ast::AddressExpr{ addressExpr->location, r->expr } );
279 }
280 }
281
282 void postvisit( const ast::LabelAddressExpr * labelExpr ) {
283 addCandidate( labelExpr, tenv );
284 }
285
286 void postvisit( const ast::CastExpr * castExpr ) {
287 #warning unimplemented
288 (void)castExpr;
289 assert(false);
290 }
291
292 void postvisit( const ast::VirtualCastExpr * castExpr ) {
293 assertf( castExpr->result, "Implicit virtual cast targets not yet supported." );
294 CandidateFinder finder{ symtab, tenv };
295 // don't prune here, all alternatives guaranteed to have same type
296 finder.find( castExpr->arg, ResolvMode::withoutPrune() );
297 for ( CandidateRef & r : finder.candidates ) {
298 addCandidate(
299 *r, new ast::VirtualCastExpr{ castExpr->location, r->expr, castExpr->result } );
300 }
301 }
302
303 void postvisit( const ast::UntypedMemberExpr * memberExpr ) {
304 #warning unimplemented
305 (void)memberExpr;
306 assert(false);
307 }
308
309 void postvisit( const ast::MemberExpr * memberExpr ) {
310 addCandidate( memberExpr, tenv );
311 }
312
313 void postvisit( const ast::NameExpr * variableExpr ) {
314 #warning unimplemented
315 (void)variableExpr;
316 assert(false);
317 }
318
319 void postvisit( const ast::VariableExpr * variableExpr ) {
320 // not sufficient to just pass `variableExpr` here, type might have changed since
321 // creation
322 addCandidate(
323 new ast::VariableExpr{ variableExpr->location, variableExpr->var }, tenv );
324 }
325
326 void postvisit( const ast::ConstantExpr * constantExpr ) {
327 addCandidate( constantExpr, tenv );
328 }
329
330 void postvisit( const ast::SizeofExpr * sizeofExpr ) {
331 #warning unimplemented
332 (void)sizeofExpr;
333 assert(false);
334 }
335
336 void postvisit( const ast::AlignofExpr * alignofExpr ) {
337 #warning unimplemented
338 (void)alignofExpr;
339 assert(false);
340 }
341
342 void postvisit( const ast::UntypedOffsetofExpr * offsetofExpr ) {
343 #warning unimplemented
344 (void)offsetofExpr;
345 assert(false);
346 }
347
348 void postvisit( const ast::OffsetofExpr * offsetofExpr ) {
349 addCandidate( offsetofExpr, tenv );
350 }
351
352 void postvisit( const ast::OffsetPackExpr * offsetPackExpr ) {
353 addCandidate( offsetPackExpr, tenv );
354 }
355
356 void postvisit( const ast::LogicalExpr * logicalExpr ) {
357 CandidateFinder finder1{ symtab, tenv };
358 finder1.find( logicalExpr->arg1, ResolvMode::withAdjustment() );
359 if ( finder1.candidates.empty() ) return;
360
361 CandidateFinder finder2{ symtab, tenv };
362 finder2.find( logicalExpr->arg2, ResolvMode::withAdjustment() );
363 if ( finder2.candidates.empty() ) return;
364
365 for ( const CandidateRef & r1 : finder1.candidates ) {
366 for ( const CandidateRef & r2 : finder2.candidates ) {
367 ast::TypeEnvironment env{ r1->env };
368 env.simpleCombine( r2->env );
369 ast::OpenVarSet open{ r1->open };
370 mergeOpenVars( open, r2->open );
371 ast::AssertionSet need;
372 mergeAssertionSet( need, r1->need );
373 mergeAssertionSet( need, r2->need );
374
375 addCandidate(
376 new ast::LogicalExpr{
377 logicalExpr->location, r1->expr, r2->expr, logicalExpr->isAnd },
378 std::move( env ), std::move( open ), std::move( need ),
379 r1->cost + r2->cost );
380 }
381 }
382 }
383
384 void postvisit( const ast::ConditionalExpr * conditionalExpr ) {
385 // candidates for condition
386 CandidateFinder finder1{ symtab, tenv };
387 finder1.find( conditionalExpr->arg1, ResolvMode::withAdjustment() );
388 if ( finder1.candidates.empty() ) return;
389
390 // candidates for true result
391 CandidateFinder finder2{ symtab, tenv };
392 finder2.find( conditionalExpr->arg2, ResolvMode::withAdjustment() );
393 if ( finder2.candidates.empty() ) return;
394
395 // candidates for false result
396 CandidateFinder finder3{ symtab, tenv };
397 finder3.find( conditionalExpr->arg3, ResolvMode::withAdjustment() );
398 if ( finder3.candidates.empty() ) return;
399
400 for ( const CandidateRef & r1 : finder1.candidates ) {
401 for ( const CandidateRef & r2 : finder2.candidates ) {
402 for ( const CandidateRef & r3 : finder3.candidates ) {
403 ast::TypeEnvironment env{ r1->env };
404 env.simpleCombine( r2->env );
405 env.simpleCombine( r3->env );
406 ast::OpenVarSet open{ r1->open };
407 mergeOpenVars( open, r2->open );
408 mergeOpenVars( open, r3->open );
409 ast::AssertionSet need;
410 mergeAssertionSet( need, r1->need );
411 mergeAssertionSet( need, r2->need );
412 mergeAssertionSet( need, r3->need );
413 ast::AssertionSet have;
414
415 // unify true and false results, then infer parameters to produce new
416 // candidates
417 ast::ptr< ast::Type > common;
418 if (
419 unify(
420 r2->expr->result, r3->expr->result, env, need, have, open, symtab,
421 common )
422 ) {
423 #warning unimplemented
424 assert(false);
425 }
426 }
427 }
428 }
429 }
430
431 void postvisit( const ast::CommaExpr * commaExpr ) {
432 ast::TypeEnvironment env{ tenv };
433 ast::ptr< ast::Expr > arg1 = resolveInVoidContext( commaExpr->arg1, symtab, env );
434
435 CandidateFinder finder2{ symtab, env };
436 finder2.find( commaExpr->arg2, ResolvMode::withAdjustment() );
437
438 for ( const CandidateRef & r2 : finder2.candidates ) {
439 addCandidate( *r2, new ast::CommaExpr{ commaExpr->location, arg1, r2->expr } );
440 }
441 }
442
443 void postvisit( const ast::ImplicitCopyCtorExpr * ctorExpr ) {
444 addCandidate( ctorExpr, tenv );
445 }
446
447 void postvisit( const ast::ConstructorExpr * ctorExpr ) {
448 CandidateFinder finder{ symtab, tenv };
449 finder.find( ctorExpr->callExpr, ResolvMode::withoutPrune() );
450 for ( CandidateRef & r : finder.candidates ) {
451 addCandidate( *r, new ast::ConstructorExpr{ ctorExpr->location, r->expr } );
452 }
453 }
454
455 void postvisit( const ast::RangeExpr * rangeExpr ) {
456 // resolve low and high, accept candidates where low and high types unify
457 CandidateFinder finder1{ symtab, tenv };
458 finder1.find( rangeExpr->low, ResolvMode::withAdjustment() );
459 if ( finder1.candidates.empty() ) return;
460
461 CandidateFinder finder2{ symtab, tenv };
462 finder2.find( rangeExpr->high, ResolvMode::withAdjustment() );
463 if ( finder2.candidates.empty() ) return;
464
465 for ( const CandidateRef & r1 : finder1.candidates ) {
466 for ( const CandidateRef & r2 : finder2.candidates ) {
467 ast::TypeEnvironment env{ r1->env };
468 env.simpleCombine( r2->env );
469 ast::OpenVarSet open{ r1->open };
470 mergeOpenVars( open, r2->open );
471 ast::AssertionSet need;
472 mergeAssertionSet( need, r1->need );
473 mergeAssertionSet( need, r2->need );
474 ast::AssertionSet have;
475
476 ast::ptr< ast::Type > common;
477 if (
478 unify(
479 r1->expr->result, r2->expr->result, env, need, have, open, symtab,
480 common )
481 ) {
482 ast::RangeExpr * newExpr =
483 new ast::RangeExpr{ rangeExpr->location, r1->expr, r2->expr };
484 newExpr->result = common ? common : r1->expr->result;
485
486 #warning unimplemented
487 assert(false);
488 }
489 }
490 }
491 }
492
493 void postvisit( const ast::UntypedTupleExpr * tupleExpr ) {
494 std::vector< CandidateFinder > subCandidates =
495 selfFinder.findSubExprs( tupleExpr->exprs );
496 std::vector< CandidateList > possibilities;
497 combos( subCandidates.begin(), subCandidates.end(), back_inserter( possibilities ) );
498
499 for ( const CandidateList & subs : possibilities ) {
500 std::vector< ast::ptr< ast::Expr > > exprs;
501 exprs.reserve( subs.size() );
502 for ( const CandidateRef & sub : subs ) { exprs.emplace_back( sub->expr ); }
503
504 ast::TypeEnvironment env;
505 ast::OpenVarSet open;
506 ast::AssertionSet need;
507 for ( const CandidateRef & sub : subs ) {
508 env.simpleCombine( sub->env );
509 mergeOpenVars( open, sub->open );
510 mergeAssertionSet( need, sub->need );
511 }
512
513 addCandidate(
514 new ast::TupleExpr{ tupleExpr->location, std::move( exprs ) },
515 std::move( env ), std::move( open ), std::move( need ), sumCost( subs ) );
516 }
517 }
518
519 void postvisit( const ast::TupleExpr * tupleExpr ) {
520 addCandidate( tupleExpr, tenv );
521 }
522
523 void postvisit( const ast::TupleIndexExpr * tupleExpr ) {
524 addCandidate( tupleExpr, tenv );
525 }
526
527 void postvisit( const ast::TupleAssignExpr * tupleExpr ) {
528 addCandidate( tupleExpr, tenv );
529 }
530
531 void postvisit( const ast::UniqueExpr * unqExpr ) {
532 CandidateFinder finder{ symtab, tenv };
533 finder.find( unqExpr->expr, ResolvMode::withAdjustment() );
534 for ( CandidateRef & r : finder.candidates ) {
535 // ensure that the the id is passed on so that the expressions are "linked"
536 addCandidate( *r, new ast::UniqueExpr{ unqExpr->location, r->expr, unqExpr->id } );
537 }
538 }
539
540 void postvisit( const ast::StmtExpr * stmtExpr ) {
541 #warning unimplemented
542 (void)stmtExpr;
543 assert(false);
544 }
545
546 void postvisit( const ast::UntypedInitExpr * initExpr ) {
547 #warning unimplemented
548 (void)initExpr;
549 assert(false);
550 }
551
552 void postvisit( const ast::InitExpr * ) {
553 assertf( false, "CandidateFinder should never see a resolved InitExpr." );
554 }
555
556 void postvisit( const ast::DeletedExpr * ) {
557 assertf( false, "CandidateFinder should never see a DeletedExpr." );
558 }
559
560 void postvisit( const ast::GenericExpr * ) {
561 assertf( false, "_Generic is not yet supported." );
562 }
[396037d]563 };
564
565 /// Prunes a list of candidates down to those that have the minimum conversion cost for a given
566 /// return type. Skips ambiguous candidates.
567 CandidateList pruneCandidates( CandidateList & candidates ) {
[d57e349]568 struct PruneStruct {
569 CandidateRef candidate;
570 bool ambiguous;
571
572 PruneStruct() = default;
573 PruneStruct( const CandidateRef & c ) : candidate( c ), ambiguous( false ) {}
574 };
575
576 // find lowest-cost candidate for each type
577 std::unordered_map< std::string, PruneStruct > selected;
578 for ( CandidateRef & candidate : candidates ) {
579 std::string mangleName;
580 {
581 ast::ptr< ast::Type > newType = candidate->expr->result;
582 candidate->env.apply( newType );
583 mangleName = Mangle::mangle( newType );
584 }
585
586 auto found = selected.find( mangleName );
587 if ( found != selected.end() ) {
588 if ( candidate->cost < found->second.candidate->cost ) {
589 PRINT(
590 std::cerr << "cost " << candidate->cost << " beats "
591 << found->second.candidate->cost << std::endl;
592 )
593
594 found->second = PruneStruct{ candidate };
595 } else if ( candidate->cost == found->second.candidate->cost ) {
596 // if one of the candidates contains a deleted identifier, can pick the other,
597 // since deleted expressions should not be ambiguous if there is another option
598 // that is at least as good
599 if ( findDeletedExpr( candidate->expr ) ) {
600 // do nothing
601 PRINT( std::cerr << "candidate is deleted" << std::endl; )
602 } else if ( findDeletedExpr( found->second.candidate->expr ) ) {
603 PRINT( std::cerr << "current is deleted" << std::endl; )
604 found->second = PruneStruct{ candidate };
605 } else {
606 PRINT( std::cerr << "marking ambiguous" << std::endl; )
607 found->second.ambiguous = true;
608 }
609 } else {
610 PRINT(
611 std::cerr << "cost " << candidate->cost << " loses to "
612 << found->second.candidate->cost << std::endl;
613 )
614 }
615 } else {
616 selected.emplace_hint( found, mangleName, candidate );
617 }
618 }
619
620 // report unambiguous min-cost candidates
621 CandidateList out;
622 for ( auto & target : selected ) {
623 if ( target.second.ambiguous ) continue;
624
625 CandidateRef cand = target.second.candidate;
626
627 ast::ptr< ast::Type > newResult = cand->expr->result;
628 cand->env.applyFree( newResult );
629 cand->expr = ast::mutate_field(
630 cand->expr.get(), &ast::Expr::result, std::move( newResult ) );
631
632 out.emplace_back( cand );
633 }
634 return out;
635 }
636
[396037d]637} // anonymous namespace
638
[99d4584]639void CandidateFinder::find( const ast::Expr * expr, ResolvMode mode ) {
[396037d]640 // Find alternatives for expression
641 ast::Pass<Finder> finder{ *this };
642 expr->accept( finder );
643
644 if ( mode.failFast && candidates.empty() ) {
645 SemanticError( expr, "No reasonable alternatives for expression " );
646 }
647
648 if ( mode.satisfyAssns || mode.prune ) {
649 // trim candidates to just those where the assertions are satisfiable
650 // - necessary pre-requisite to pruning
651 CandidateList satisfied;
652 std::vector< std::string > errors;
653 for ( auto & candidate : candidates ) {
654 satisfyAssertions( *candidate, symtab, satisfied, errors );
655 }
656
657 // fail early if none such
658 if ( mode.failFast && satisfied.empty() ) {
659 std::ostringstream stream;
660 stream << "No alternatives with satisfiable assertions for " << expr << "\n";
661 for ( const auto& err : errors ) {
662 stream << err;
663 }
664 SemanticError( expr->location, stream.str() );
665 }
666
667 // reset candidates
668 candidates = std::move( satisfied );
669 }
670
671 if ( mode.prune ) {
672 // trim candidates to single best one
673 PRINT(
674 std::cerr << "alternatives before prune:" << std::endl;
675 print( std::cerr, candidates );
676 )
677
678 CandidateList pruned = pruneCandidates( candidates );
[d57e349]679
[396037d]680 if ( mode.failFast && pruned.empty() ) {
681 std::ostringstream stream;
[d57e349]682 CandidateList winners = findMinCost( candidates );
683 stream << "Cannot choose between " << winners.size() << " alternatives for "
684 "expression\n";
685 ast::print( stream, expr );
686 stream << " Alternatives are:\n";
687 print( stream, winners, 1 );
688 SemanticError( expr->location, stream.str() );
[396037d]689 }
[d57e349]690
691 auto oldsize = candidates.size();
692 candidates = std::move( pruned );
693
694 PRINT(
695 std::cerr << "there are " << oldsize << " alternatives before elimination" << std::endl;
696 )
697 PRINT(
698 std::cerr << "there are " << candidates.size() << " alternatives after elimination"
699 << std::endl;
700 )
[396037d]701 }
702
[d57e349]703 // adjust types after pruning so that types substituted by pruneAlternatives are correctly
704 // adjusted
705 if ( mode.adjust ) {
706 for ( CandidateRef & r : candidates ) {
707 r->expr = ast::mutate_field(
708 r->expr.get(), &ast::Expr::result,
709 adjustExprType( r->expr->result, r->env, symtab ) );
710 }
711 }
712
713 // Central location to handle gcc extension keyword, etc. for all expressions
714 for ( CandidateRef & r : candidates ) {
715 if ( r->expr->extension != expr->extension ) {
716 r->expr.get_and_mutate()->extension = expr->extension;
717 }
718 }
[99d4584]719}
720
[2773ab8]721std::vector< CandidateFinder > CandidateFinder::findSubExprs(
722 const std::vector< ast::ptr< ast::Expr > > & xs
723) {
724 std::vector< CandidateFinder > out;
725
[396037d]726 for ( const auto & x : xs ) {
727 out.emplace_back( symtab, env );
728 out.back().find( x, ResolvMode::withAdjustment() );
729
730 PRINT(
731 std::cerr << "findSubExprs" << std::endl;
732 print( std::cerr, out.back().candidates );
733 )
734 }
[2773ab8]735
736 return out;
737}
738
[99d4584]739} // namespace ResolvExpr
740
741// Local Variables: //
742// tab-width: 4 //
743// mode: c++ //
744// compile-command: "make install" //
745// End: //
Note: See TracBrowser for help on using the repository browser.