source: src/ResolvExpr/CandidateFinder.cpp@ c8e4d2f8

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

Start porting CastExpr resolution
  • Property mode set to 100644
File size: 50.3 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 <deque>
19#include <iterator> // for back_inserter
20#include <sstream>
21#include <string>
22#include <unordered_map>
23#include <vector>
24
25#include "Candidate.hpp"
26#include "CompilationState.h"
27#include "Cost.h"
28#include "ExplodedArg.hpp"
29#include "Resolver.h"
30#include "ResolveTypeof.h"
31#include "SatisfyAssertions.hpp"
32#include "typeops.h" // for adjustExprType, conversionCost, polyCost, specCost
33#include "Unify.h"
34#include "AST/Expr.hpp"
35#include "AST/Node.hpp"
36#include "AST/Pass.hpp"
37#include "AST/Print.hpp"
38#include "AST/SymbolTable.hpp"
39#include "AST/Type.hpp"
40#include "SymTab/Mangler.h"
41#include "SymTab/Validate.h" // for validateType
42#include "Tuples/Tuples.h" // for handleTupleAssignment
43
44#define PRINT( text ) if ( resolvep ) { text }
45
46namespace ResolvExpr {
47
48using std::move;
49
50/// partner to move that copies any copyable type
51template<typename T>
52T copy( const T & x ) { return x; }
53
54const ast::Expr * referenceToRvalueConversion( const ast::Expr * expr, Cost & cost ) {
55 if ( expr->result.as< ast::ReferenceType >() ) {
56 // cast away reference from expr
57 cost.incReference();
58 return new ast::CastExpr{ expr->location, expr, expr->result->stripReferences() };
59 }
60
61 return expr;
62}
63
64/// Unique identifier for matching expression resolutions to their requesting expression
65UniqueId globalResnSlot = 0;
66
67namespace {
68 /// First index is which argument, second is which alternative, third is which exploded element
69 using ExplodedArgs_new = std::deque< std::vector< ExplodedArg > >;
70
71 /// Returns a list of alternatives with the minimum cost in the given list
72 CandidateList findMinCost( const CandidateList & candidates ) {
73 CandidateList out;
74 Cost minCost = Cost::infinity;
75 for ( const CandidateRef & r : candidates ) {
76 if ( r->cost < minCost ) {
77 minCost = r->cost;
78 out.clear();
79 out.emplace_back( r );
80 } else if ( r->cost == minCost ) {
81 out.emplace_back( r );
82 }
83 }
84 return out;
85 }
86
87 /// Computes conversion cost between two types
88 Cost computeConversionCost(
89 const ast::Type * argType, const ast::Type * paramType, const ast::SymbolTable & symtab,
90 const ast::TypeEnvironment & env
91 ) {
92 PRINT(
93 std::cerr << std::endl << "converting ";
94 ast::print( std::cerr, argType, 2 );
95 std::cerr << std::endl << " to ";
96 ast::print( std::cerr, paramType, 2 );
97 std::cerr << std::endl << "environment is: ";
98 ast::print( std::cerr, env, 2 );
99 std::cerr << std::endl;
100 )
101 Cost convCost = conversionCost( argType, paramType, symtab, env );
102 PRINT(
103 std::cerr << std::endl << "cost is " << convCost << std::endl;
104 )
105 if ( convCost == Cost::infinity ) return convCost;
106 convCost.incPoly( polyCost( paramType, symtab, env ) + polyCost( argType, symtab, env ) );
107 PRINT(
108 std::cerr << "cost with polycost is " << convCost << std::endl;
109 )
110 return convCost;
111 }
112
113 /// Computes conversion cost for a given expression to a given type
114 const ast::Expr * computeExpressionConversionCost(
115 const ast::Expr * arg, const ast::Type * paramType, const ast::SymbolTable & symtab, const ast::TypeEnvironment & env, Cost & outCost
116 ) {
117 Cost convCost = computeConversionCost( arg->result, paramType, symtab, env );
118 outCost += convCost;
119
120 // If there is a non-zero conversion cost, ignoring poly cost, then the expression requires
121 // conversion. Ignore poly cost for now, since this requires resolution of the cast to
122 // infer parameters and this does not currently work for the reason stated below
123 Cost tmpCost = convCost;
124 tmpCost.incPoly( -tmpCost.get_polyCost() );
125 if ( tmpCost != Cost::zero ) {
126 ast::ptr< ast::Type > newType = paramType;
127 env.apply( newType );
128 return new ast::CastExpr{ arg->location, arg, newType };
129
130 // xxx - *should* be able to resolve this cast, but at the moment pointers are not
131 // castable to zero_t, but are implicitly convertible. This is clearly inconsistent,
132 // once this is fixed it should be possible to resolve the cast.
133 // xxx - this isn't working, it appears because type1 (parameter) is seen as widenable,
134 // but it shouldn't be because this makes the conversion from DT* to DT* since
135 // commontype(zero_t, DT*) is DT*, rather than nothing
136
137 // CandidateFinder finder{ symtab, env };
138 // finder.find( arg, ResolvMode::withAdjustment() );
139 // assertf( finder.candidates.size() > 0,
140 // "Somehow castable expression failed to find alternatives." );
141 // assertf( finder.candidates.size() == 1,
142 // "Somehow got multiple alternatives for known cast expression." );
143 // return finder.candidates.front()->expr;
144 }
145
146 return arg;
147 }
148
149 /// Computes conversion cost for a given candidate
150 Cost computeApplicationConversionCost(
151 CandidateRef cand, const ast::SymbolTable & symtab
152 ) {
153 auto appExpr = cand->expr.strict_as< ast::ApplicationExpr >();
154 auto pointer = appExpr->func->result.strict_as< ast::PointerType >();
155 auto function = pointer->base.strict_as< ast::FunctionType >();
156
157 Cost convCost = Cost::zero;
158 const auto & params = function->params;
159 auto param = params.begin();
160 auto & args = appExpr->args;
161
162 for ( unsigned i = 0; i < args.size(); ++i ) {
163 const ast::Type * argType = args[i]->result;
164 PRINT(
165 std::cerr << "arg expression:" << std::endl;
166 ast::print( std::cerr, args[i], 2 );
167 std::cerr << "--- results are" << std::endl;
168 ast::print( std::cerr, argType, 2 );
169 )
170
171 if ( param == params.end() ) {
172 if ( function->isVarArgs ) {
173 convCost.incUnsafe();
174 PRINT( std::cerr << "end of params with varargs function: inc unsafe: "
175 << convCost << std::endl; ; )
176 // convert reference-typed expressions into value-typed expressions
177 cand->expr = ast::mutate_field_index(
178 appExpr, &ast::ApplicationExpr::args, i,
179 referenceToRvalueConversion( args[i], convCost ) );
180 continue;
181 } else return Cost::infinity;
182 }
183
184 if ( auto def = args[i].as< ast::DefaultArgExpr >() ) {
185 // Default arguments should be free - don't include conversion cost.
186 // Unwrap them here because they are not relevant to the rest of the system
187 cand->expr = ast::mutate_field_index(
188 appExpr, &ast::ApplicationExpr::args, i, def->expr );
189 ++param;
190 continue;
191 }
192
193 // mark conversion cost and also specialization cost of param type
194 const ast::Type * paramType = (*param)->get_type();
195 cand->expr = ast::mutate_field_index(
196 appExpr, &ast::ApplicationExpr::args, i,
197 computeExpressionConversionCost(
198 args[i], paramType, symtab, cand->env, convCost ) );
199 convCost.decSpec( specCost( paramType ) );
200 ++param; // can't be in for-loop update because of the continue
201 }
202
203 if ( param != params.end() ) return Cost::infinity;
204
205 // specialization cost of return types can't be accounted for directly, it disables
206 // otherwise-identical calls, like this example based on auto-newline in the I/O lib:
207 //
208 // forall(otype OS) {
209 // void ?|?(OS&, int); // with newline
210 // OS& ?|?(OS&, int); // no newline, always chosen due to more specialization
211 // }
212
213 // mark type variable and specialization cost of forall clause
214 convCost.incVar( function->forall.size() );
215 for ( const ast::TypeDecl * td : function->forall ) {
216 convCost.decSpec( td->assertions.size() );
217 }
218
219 return convCost;
220 }
221
222 void makeUnifiableVars(
223 const ast::ParameterizedType * type, ast::OpenVarSet & unifiableVars,
224 ast::AssertionSet & need
225 ) {
226 for ( const ast::TypeDecl * tyvar : type->forall ) {
227 unifiableVars[ tyvar->name ] = ast::TypeDecl::Data{ tyvar };
228 for ( const ast::DeclWithType * assn : tyvar->assertions ) {
229 need[ assn ].isUsed = true;
230 }
231 }
232 }
233
234 /// Gets a default value from an initializer, nullptr if not present
235 const ast::ConstantExpr * getDefaultValue( const ast::Init * init ) {
236 if ( auto si = dynamic_cast< const ast::SingleInit * >( init ) ) {
237 if ( auto ce = si->value.as< ast::CastExpr >() ) {
238 return ce->arg.as< ast::ConstantExpr >();
239 } else {
240 return si->value.as< ast::ConstantExpr >();
241 }
242 }
243 return nullptr;
244 }
245
246 /// State to iteratively build a match of parameter expressions to arguments
247 struct ArgPack {
248 std::size_t parent; ///< Index of parent pack
249 ast::ptr< ast::Expr > expr; ///< The argument stored here
250 Cost cost; ///< The cost of this argument
251 ast::TypeEnvironment env; ///< Environment for this pack
252 ast::AssertionSet need; ///< Assertions outstanding for this pack
253 ast::AssertionSet have; ///< Assertions found for this pack
254 ast::OpenVarSet open; ///< Open variables for this pack
255 unsigned nextArg; ///< Index of next argument in arguments list
256 unsigned tupleStart; ///< Number of tuples that start at this index
257 unsigned nextExpl; ///< Index of next exploded element
258 unsigned explAlt; ///< Index of alternative for nextExpl > 0
259
260 ArgPack()
261 : parent( 0 ), expr(), cost( Cost::zero ), env(), need(), have(), open(), nextArg( 0 ),
262 tupleStart( 0 ), nextExpl( 0 ), explAlt( 0 ) {}
263
264 ArgPack(
265 const ast::TypeEnvironment & env, const ast::AssertionSet & need,
266 const ast::AssertionSet & have, const ast::OpenVarSet & open )
267 : parent( 0 ), expr(), cost( Cost::zero ), env( env ), need( need ), have( have ),
268 open( open ), nextArg( 0 ), tupleStart( 0 ), nextExpl( 0 ), explAlt( 0 ) {}
269
270 ArgPack(
271 std::size_t parent, const ast::Expr * expr, ast::TypeEnvironment && env,
272 ast::AssertionSet && need, ast::AssertionSet && have, ast::OpenVarSet && open,
273 unsigned nextArg, unsigned tupleStart = 0, Cost cost = Cost::zero,
274 unsigned nextExpl = 0, unsigned explAlt = 0 )
275 : parent(parent), expr( expr ), cost( cost ), env( move( env ) ), need( move( need ) ),
276 have( move( have ) ), open( move( open ) ), nextArg( nextArg ), tupleStart( tupleStart ),
277 nextExpl( nextExpl ), explAlt( explAlt ) {}
278
279 ArgPack(
280 const ArgPack & o, ast::TypeEnvironment && env, ast::AssertionSet && need,
281 ast::AssertionSet && have, ast::OpenVarSet && open, unsigned nextArg, Cost added )
282 : parent( o.parent ), expr( o.expr ), cost( o.cost + added ), env( move( env ) ),
283 need( move( need ) ), have( move( have ) ), open( move( open ) ), nextArg( nextArg ),
284 tupleStart( o.tupleStart ), nextExpl( 0 ), explAlt( 0 ) {}
285
286 /// true if this pack is in the middle of an exploded argument
287 bool hasExpl() const { return nextExpl > 0; }
288
289 /// Gets the list of exploded candidates for this pack
290 const ExplodedArg & getExpl( const ExplodedArgs_new & args ) const {
291 return args[ nextArg-1 ][ explAlt ];
292 }
293
294 /// Ends a tuple expression, consolidating the appropriate args
295 void endTuple( const std::vector< ArgPack > & packs ) {
296 // add all expressions in tuple to list, summing cost
297 std::deque< const ast::Expr * > exprs;
298 const ArgPack * pack = this;
299 if ( expr ) { exprs.emplace_front( expr ); }
300 while ( pack->tupleStart == 0 ) {
301 pack = &packs[pack->parent];
302 exprs.emplace_front( pack->expr );
303 cost += pack->cost;
304 }
305 // reset pack to appropriate tuple
306 std::vector< ast::ptr< ast::Expr > > exprv( exprs.begin(), exprs.end() );
307 expr = new ast::TupleExpr{ expr->location, move( exprv ) };
308 tupleStart = pack->tupleStart - 1;
309 parent = pack->parent;
310 }
311 };
312
313 /// Instantiates an argument to match a parameter, returns false if no matching results left
314 bool instantiateArgument(
315 const ast::Type * paramType, const ast::Init * init, const ExplodedArgs_new & args,
316 std::vector< ArgPack > & results, std::size_t & genStart, const ast::SymbolTable & symtab,
317 unsigned nTuples = 0
318 ) {
319 if ( auto tupleType = dynamic_cast< const ast::TupleType * >( paramType ) ) {
320 // paramType is a TupleType -- group args into a TupleExpr
321 ++nTuples;
322 for ( const ast::Type * type : *tupleType ) {
323 // xxx - dropping initializer changes behaviour from previous, but seems correct
324 // ^^^ need to handle the case where a tuple has a default argument
325 if ( ! instantiateArgument(
326 type, nullptr, args, results, genStart, symtab, nTuples ) ) return false;
327 nTuples = 0;
328 }
329 // re-constitute tuples for final generation
330 for ( auto i = genStart; i < results.size(); ++i ) {
331 results[i].endTuple( results );
332 }
333 return true;
334 } else if ( const ast::TypeInstType * ttype = Tuples::isTtype( paramType ) ) {
335 // paramType is a ttype, consumes all remaining arguments
336
337 // completed tuples; will be spliced to end of results to finish
338 std::vector< ArgPack > finalResults{};
339
340 // iterate until all results completed
341 std::size_t genEnd;
342 ++nTuples;
343 do {
344 genEnd = results.size();
345
346 // add another argument to results
347 for ( std::size_t i = genStart; i < genEnd; ++i ) {
348 unsigned nextArg = results[i].nextArg;
349
350 // use next element of exploded tuple if present
351 if ( results[i].hasExpl() ) {
352 const ExplodedArg & expl = results[i].getExpl( args );
353
354 unsigned nextExpl = results[i].nextExpl + 1;
355 if ( nextExpl == expl.exprs.size() ) { nextExpl = 0; }
356
357 results.emplace_back(
358 i, expl.exprs[ results[i].nextExpl ], copy( results[i].env ),
359 copy( results[i].need ), copy( results[i].have ),
360 copy( results[i].open ), nextArg, nTuples, Cost::zero, nextExpl,
361 results[i].explAlt );
362
363 continue;
364 }
365
366 // finish result when out of arguments
367 if ( nextArg >= args.size() ) {
368 ArgPack newResult{
369 results[i].env, results[i].need, results[i].have, results[i].open };
370 newResult.nextArg = nextArg;
371 const ast::Type * argType = nullptr;
372
373 if ( nTuples > 0 || ! results[i].expr ) {
374 // first iteration or no expression to clone,
375 // push empty tuple expression
376 newResult.parent = i;
377 std::vector< ast::ptr< ast::Expr > > emptyList;
378 newResult.expr =
379 new ast::TupleExpr{ CodeLocation{}, move( emptyList ) };
380 argType = newResult.expr->result;
381 } else {
382 // clone result to collect tuple
383 newResult.parent = results[i].parent;
384 newResult.cost = results[i].cost;
385 newResult.tupleStart = results[i].tupleStart;
386 newResult.expr = results[i].expr;
387 argType = newResult.expr->result;
388
389 if ( results[i].tupleStart > 0 && Tuples::isTtype( argType ) ) {
390 // the case where a ttype value is passed directly is special,
391 // e.g. for argument forwarding purposes
392 // xxx - what if passing multiple arguments, last of which is
393 // ttype?
394 // xxx - what would happen if unify was changed so that unifying
395 // tuple
396 // types flattened both before unifying lists? then pass in
397 // TupleType (ttype) below.
398 --newResult.tupleStart;
399 } else {
400 // collapse leftover arguments into tuple
401 newResult.endTuple( results );
402 argType = newResult.expr->result;
403 }
404 }
405
406 // check unification for ttype before adding to final
407 if (
408 unify(
409 ttype, argType, newResult.env, newResult.need, newResult.have,
410 newResult.open, symtab )
411 ) {
412 finalResults.emplace_back( move( newResult ) );
413 }
414
415 continue;
416 }
417
418 // add each possible next argument
419 for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
420 const ExplodedArg & expl = args[nextArg][j];
421
422 // fresh copies of parent parameters for this iteration
423 ast::TypeEnvironment env = results[i].env;
424 ast::OpenVarSet open = results[i].open;
425
426 env.addActual( expl.env, open );
427
428 // skip empty tuple arguments by (nearly) cloning parent into next gen
429 if ( expl.exprs.empty() ) {
430 results.emplace_back(
431 results[i], move( env ), copy( results[i].need ),
432 copy( results[i].have ), move( open ), nextArg + 1, expl.cost );
433
434 continue;
435 }
436
437 // add new result
438 results.emplace_back(
439 i, expl.exprs.front(), move( env ), copy( results[i].need ),
440 copy( results[i].have ), move( open ), nextArg + 1, nTuples,
441 expl.cost, expl.exprs.size() == 1 ? 0 : 1, j );
442 }
443 }
444
445 // reset for next round
446 genStart = genEnd;
447 nTuples = 0;
448 } while ( genEnd != results.size() );
449
450 // splice final results onto results
451 for ( std::size_t i = 0; i < finalResults.size(); ++i ) {
452 results.emplace_back( move( finalResults[i] ) );
453 }
454 return ! finalResults.empty();
455 }
456
457 // iterate each current subresult
458 std::size_t genEnd = results.size();
459 for ( std::size_t i = genStart; i < genEnd; ++i ) {
460 unsigned nextArg = results[i].nextArg;
461
462 // use remainder of exploded tuple if present
463 if ( results[i].hasExpl() ) {
464 const ExplodedArg & expl = results[i].getExpl( args );
465 const ast::Expr * expr = expl.exprs[ results[i].nextExpl ];
466
467 ast::TypeEnvironment env = results[i].env;
468 ast::AssertionSet need = results[i].need, have = results[i].have;
469 ast::OpenVarSet open = results[i].open;
470
471 const ast::Type * argType = expr->result;
472
473 PRINT(
474 std::cerr << "param type is ";
475 ast::print( std::cerr, paramType );
476 std::cerr << std::endl << "arg type is ";
477 ast::print( std::cerr, argType );
478 std::cerr << std::endl;
479 )
480
481 if ( unify( paramType, argType, env, need, have, open, symtab ) ) {
482 unsigned nextExpl = results[i].nextExpl + 1;
483 if ( nextExpl == expl.exprs.size() ) { nextExpl = 0; }
484
485 results.emplace_back(
486 i, expr, move( env ), move( need ), move( have ), move( open ), nextArg,
487 nTuples, Cost::zero, nextExpl, results[i].explAlt );
488 }
489
490 continue;
491 }
492
493 // use default initializers if out of arguments
494 if ( nextArg >= args.size() ) {
495 if ( const ast::ConstantExpr * cnst = getDefaultValue( init ) ) {
496 ast::TypeEnvironment env = results[i].env;
497 ast::AssertionSet need = results[i].need, have = results[i].have;
498 ast::OpenVarSet open = results[i].open;
499
500 if ( unify( paramType, cnst->result, env, need, have, open, symtab ) ) {
501 results.emplace_back(
502 i, new ast::DefaultArgExpr{ cnst->location, cnst }, move( env ),
503 move( need ), move( have ), move( open ), nextArg, nTuples );
504 }
505 }
506
507 continue;
508 }
509
510 // Check each possible next argument
511 for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
512 const ExplodedArg & expl = args[nextArg][j];
513
514 // fresh copies of parent parameters for this iteration
515 ast::TypeEnvironment env = results[i].env;
516 ast::AssertionSet need = results[i].need, have = results[i].have;
517 ast::OpenVarSet open = results[i].open;
518
519 env.addActual( expl.env, open );
520
521 // skip empty tuple arguments by (nearly) cloning parent into next gen
522 if ( expl.exprs.empty() ) {
523 results.emplace_back(
524 results[i], move( env ), move( need ), move( have ), move( open ),
525 nextArg + 1, expl.cost );
526
527 continue;
528 }
529
530 // consider only first exploded arg
531 const ast::Expr * expr = expl.exprs.front();
532 const ast::Type * argType = expr->result;
533
534 PRINT(
535 std::cerr << "param type is ";
536 ast::print( std::cerr, paramType );
537 std::cerr << std::endl << "arg type is ";
538 ast::print( std::cerr, argType );
539 std::cerr << std::endl;
540 )
541
542 // attempt to unify types
543 if ( unify( paramType, argType, env, need, have, open, symtab ) ) {
544 // add new result
545 results.emplace_back(
546 i, expr, move( env ), move( need ), move( have ), move( open ),
547 nextArg + 1, nTuples, expl.cost, expl.exprs.size() == 1 ? 0 : 1, j );
548 }
549 }
550 }
551
552 // reset for next parameter
553 genStart = genEnd;
554
555 return genEnd != results.size();
556 }
557
558 /// Generate a cast expression from `arg` to `toType`
559 const ast::Expr * restructureCast( const ast::Expr * arg, const ast::Type * toType, bool isGenerated ) {
560 #warning unimplemented
561 (void)arg; (void)toType; (void)isGenerated;
562 assert(false);
563 return nullptr;
564 }
565
566 /// Actually visits expressions to find their candidate interpretations
567 struct Finder final : public ast::WithShortCircuiting {
568 CandidateFinder & selfFinder;
569 const ast::SymbolTable & symtab;
570 CandidateList & candidates;
571 const ast::TypeEnvironment & tenv;
572 ast::ptr< ast::Type > & targetType;
573
574 Finder( CandidateFinder & f )
575 : selfFinder( f ), symtab( f.symtab ), candidates( f.candidates ), tenv( f.env ),
576 targetType( f.targetType ) {}
577
578 void previsit( const ast::Node * ) { visit_children = false; }
579
580 /// Convenience to add candidate to list
581 template<typename... Args>
582 void addCandidate( Args &&... args ) {
583 candidates.emplace_back( new Candidate{ std::forward<Args>( args )... } );
584 }
585
586 void postvisit( const ast::ApplicationExpr * applicationExpr ) {
587 addCandidate( applicationExpr, tenv );
588 }
589
590 /// Set up candidate assertions for inference
591 void inferParameters( CandidateRef & newCand, CandidateList & out ) {
592 // Set need bindings for any unbound assertions
593 UniqueId crntResnSlot = 0; // matching ID for this expression's assertions
594 for ( auto & assn : newCand->need ) {
595 // skip already-matched assertions
596 if ( assn.second.resnSlot != 0 ) continue;
597 // assign slot for expression if needed
598 if ( crntResnSlot == 0 ) { crntResnSlot = ++globalResnSlot; }
599 // fix slot to assertion
600 assn.second.resnSlot = crntResnSlot;
601 }
602 // pair slot to expression
603 if ( crntResnSlot != 0 ) {
604 newCand->expr.get_and_mutate()->inferred.resnSlots().emplace_back( crntResnSlot );
605 }
606
607 // add to output list; assertion satisfaction will occur later
608 out.emplace_back( newCand );
609 }
610
611 /// Completes a function candidate with arguments located
612 void validateFunctionCandidate(
613 const CandidateRef & func, ArgPack & result, const std::vector< ArgPack > & results,
614 CandidateList & out
615 ) {
616 ast::ApplicationExpr * appExpr =
617 new ast::ApplicationExpr{ func->expr->location, func->expr };
618 // sum cost and accumulate arguments
619 std::deque< const ast::Expr * > args;
620 Cost cost = func->cost;
621 const ArgPack * pack = &result;
622 while ( pack->expr ) {
623 args.emplace_front( pack->expr );
624 cost += pack->cost;
625 pack = &results[pack->parent];
626 }
627 std::vector< ast::ptr< ast::Expr > > vargs( args.begin(), args.end() );
628 appExpr->args = move( vargs );
629 // build and validate new candidate
630 auto newCand =
631 std::make_shared<Candidate>( appExpr, result.env, result.open, result.need, cost );
632 PRINT(
633 std::cerr << "instantiate function success: " << appExpr << std::endl;
634 std::cerr << "need assertions:" << std::endl;
635 ast::print( std::cerr, result.need, 2 );
636 )
637 inferParameters( newCand, out );
638 }
639
640 /// Builds a list of candidates for a function, storing them in out
641 void makeFunctionCandidates(
642 const CandidateRef & func, const ast::FunctionType * funcType,
643 const ExplodedArgs_new & args, CandidateList & out
644 ) {
645 ast::OpenVarSet funcOpen;
646 ast::AssertionSet funcNeed, funcHave;
647 ast::TypeEnvironment funcEnv{ func->env };
648 makeUnifiableVars( funcType, funcOpen, funcNeed );
649 // add all type variables as open variables now so that those not used in the parameter
650 // list are still considered open
651 funcEnv.add( funcType->forall );
652
653 if ( targetType && ! targetType->isVoid() && ! funcType->returns.empty() ) {
654 // attempt to narrow based on expected target type
655 const ast::Type * returnType = funcType->returns.front()->get_type();
656 if ( ! unify(
657 returnType, targetType, funcEnv, funcNeed, funcHave, funcOpen, symtab )
658 ) {
659 // unification failed, do not pursue this candidate
660 return;
661 }
662 }
663
664 // iteratively build matches, one parameter at a time
665 std::vector< ArgPack > results;
666 results.emplace_back( funcEnv, funcNeed, funcHave, funcOpen );
667 std::size_t genStart = 0;
668
669 for ( const ast::DeclWithType * param : funcType->params ) {
670 auto obj = strict_dynamic_cast< const ast::ObjectDecl * >( param );
671 // Try adding the arguments corresponding to the current parameter to the existing
672 // matches
673 if ( ! instantiateArgument(
674 obj->type, obj->init, args, results, genStart, symtab ) ) return;
675 }
676
677 if ( funcType->isVarArgs ) {
678 // append any unused arguments to vararg pack
679 std::size_t genEnd;
680 do {
681 genEnd = results.size();
682
683 // iterate results
684 for ( std::size_t i = genStart; i < genEnd; ++i ) {
685 unsigned nextArg = results[i].nextArg;
686
687 // use remainder of exploded tuple if present
688 if ( results[i].hasExpl() ) {
689 const ExplodedArg & expl = results[i].getExpl( args );
690
691 unsigned nextExpl = results[i].nextExpl + 1;
692 if ( nextExpl == expl.exprs.size() ) { nextExpl = 0; }
693
694 results.emplace_back(
695 i, expl.exprs[ results[i].nextExpl ], copy( results[i].env ),
696 copy( results[i].need ), copy( results[i].have ),
697 copy( results[i].open ), nextArg, 0, Cost::zero, nextExpl,
698 results[i].explAlt );
699
700 continue;
701 }
702
703 // finish result when out of arguments
704 if ( nextArg >= args.size() ) {
705 validateFunctionCandidate( func, results[i], results, out );
706
707 continue;
708 }
709
710 // add each possible next argument
711 for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
712 const ExplodedArg & expl = args[nextArg][j];
713
714 // fresh copies of parent parameters for this iteration
715 ast::TypeEnvironment env = results[i].env;
716 ast::OpenVarSet open = results[i].open;
717
718 env.addActual( expl.env, open );
719
720 // skip empty tuple arguments by (nearly) cloning parent into next gen
721 if ( expl.exprs.empty() ) {
722 results.emplace_back(
723 results[i], move( env ), copy( results[i].need ),
724 copy( results[i].have ), move( open ), nextArg + 1,
725 expl.cost );
726
727 continue;
728 }
729
730 // add new result
731 results.emplace_back(
732 i, expl.exprs.front(), move( env ), copy( results[i].need ),
733 copy( results[i].have ), move( open ), nextArg + 1, 0, expl.cost,
734 expl.exprs.size() == 1 ? 0 : 1, j );
735 }
736 }
737
738 genStart = genEnd;
739 } while( genEnd != results.size() );
740 } else {
741 // filter out the results that don't use all the arguments
742 for ( std::size_t i = genStart; i < results.size(); ++i ) {
743 ArgPack & result = results[i];
744 if ( ! result.hasExpl() && result.nextArg >= args.size() ) {
745 validateFunctionCandidate( func, result, results, out );
746 }
747 }
748 }
749 }
750
751 /// Adds implicit struct-conversions to the alternative list
752 void addAnonConversions( const CandidateRef & cand ) {
753 // adds anonymous member interpretations whenever an aggregate value type is seen.
754 // it's okay for the aggregate expression to have reference type -- cast it to the
755 // base type to treat the aggregate as the referenced value
756 ast::ptr< ast::Expr > aggrExpr( cand->expr );
757 ast::ptr< ast::Type > & aggrType = aggrExpr.get_and_mutate()->result;
758 cand->env.apply( aggrType );
759
760 if ( aggrType.as< ast::ReferenceType >() ) {
761 aggrExpr =
762 new ast::CastExpr{ aggrExpr->location, aggrExpr, aggrType->stripReferences() };
763 }
764
765 if ( auto structInst = aggrExpr->result.as< ast::StructInstType >() ) {
766 addAggMembers( structInst, aggrExpr, cand, Cost::safe, "" );
767 } else if ( auto unionInst = aggrExpr->result.as< ast::UnionInstType >() ) {
768 addAggMembers( unionInst, aggrExpr, cand, Cost::safe, "" );
769 }
770 }
771
772 /// Adds aggregate member interpretations
773 void addAggMembers(
774 const ast::ReferenceToType * aggrInst, const ast::Expr * expr,
775 const CandidateRef & cand, const Cost & addedCost, const std::string & name
776 ) {
777 for ( const ast::Decl * decl : aggrInst->lookup( name ) ) {
778 auto dwt = strict_dynamic_cast< const ast::DeclWithType * >( decl );
779 CandidateRef newCand = std::make_shared<Candidate>(
780 *cand, new ast::MemberExpr{ expr->location, dwt, expr }, addedCost );
781 // add anonymous member interpretations whenever an aggregate value type is seen
782 // as a member expression
783 addAnonConversions( newCand );
784 candidates.emplace_back( move( newCand ) );
785 }
786 }
787
788 void postvisit( const ast::UntypedExpr * untypedExpr ) {
789 CandidateFinder funcFinder{ symtab, tenv };
790 funcFinder.find( untypedExpr->func, ResolvMode::withAdjustment() );
791 // short-circuit if no candidates
792 if ( funcFinder.candidates.empty() ) return;
793
794 std::vector< CandidateFinder > argCandidates =
795 selfFinder.findSubExprs( untypedExpr->args );
796
797 // take care of possible tuple assignments
798 // if not tuple assignment, handled as normal function call
799 Tuples::handleTupleAssignment( selfFinder, untypedExpr, argCandidates );
800
801 // find function operators
802 ast::ptr< ast::Expr > opExpr = new ast::NameExpr{ untypedExpr->location, "?()" };
803 CandidateFinder opFinder{ symtab, tenv };
804 // okay if there aren't any function operations
805 opFinder.find( opExpr, ResolvMode::withoutFailFast() );
806 PRINT(
807 std::cerr << "known function ops:" << std::endl;
808 print( std::cerr, opFinder.candidates, 1 );
809 )
810
811 // pre-explode arguments
812 ExplodedArgs_new argExpansions;
813 for ( const CandidateFinder & args : argCandidates ) {
814 argExpansions.emplace_back();
815 auto & argE = argExpansions.back();
816 for ( const CandidateRef & arg : args ) { argE.emplace_back( *arg, symtab ); }
817 }
818
819 // Find function matches
820 CandidateList found;
821 SemanticErrorException errors;
822 for ( CandidateRef & func : funcFinder ) {
823 try {
824 PRINT(
825 std::cerr << "working on alternative:" << std::endl;
826 print( std::cerr, *func, 2 );
827 )
828
829 // check if the type is a pointer to function
830 const ast::Type * funcResult = func->expr->result->stripReferences();
831 if ( auto pointer = dynamic_cast< const ast::PointerType * >( funcResult ) ) {
832 if ( auto function = pointer->base.as< ast::FunctionType >() ) {
833 CandidateRef newFunc{ new Candidate{ *func } };
834 newFunc->expr =
835 referenceToRvalueConversion( newFunc->expr, newFunc->cost );
836 makeFunctionCandidates( newFunc, function, argExpansions, found );
837 }
838 } else if (
839 auto inst = dynamic_cast< const ast::TypeInstType * >( funcResult )
840 ) {
841 if ( const ast::EqvClass * clz = func->env.lookup( inst->name ) ) {
842 if ( auto function = clz->bound.as< ast::FunctionType >() ) {
843 CandidateRef newFunc{ new Candidate{ *func } };
844 newFunc->expr =
845 referenceToRvalueConversion( newFunc->expr, newFunc->cost );
846 makeFunctionCandidates( newFunc, function, argExpansions, found );
847 }
848 }
849 }
850 } catch ( SemanticErrorException & e ) { errors.append( e ); }
851 }
852
853 // Find matches on function operators `?()`
854 if ( ! opFinder.candidates.empty() ) {
855 // add exploded function alternatives to front of argument list
856 std::vector< ExplodedArg > funcE;
857 funcE.reserve( funcFinder.candidates.size() );
858 for ( const CandidateRef & func : funcFinder ) {
859 funcE.emplace_back( *func, symtab );
860 }
861 argExpansions.emplace_front( move( funcE ) );
862
863 for ( const CandidateRef & op : opFinder ) {
864 try {
865 // check if type is pointer-to-function
866 const ast::Type * opResult = op->expr->result->stripReferences();
867 if ( auto pointer = dynamic_cast< const ast::PointerType * >( opResult ) ) {
868 if ( auto function = pointer->base.as< ast::FunctionType >() ) {
869 CandidateRef newOp{ new Candidate{ *op} };
870 newOp->expr =
871 referenceToRvalueConversion( newOp->expr, newOp->cost );
872 makeFunctionCandidates( newOp, function, argExpansions, found );
873 }
874 }
875 } catch ( SemanticErrorException & e ) { errors.append( e ); }
876 }
877 }
878
879 // Implement SFINAE; resolution errors are only errors if there aren't any non-error
880 // candidates
881 if ( found.empty() && ! errors.isEmpty() ) { throw errors; }
882
883 // Compute conversion costs
884 for ( CandidateRef & withFunc : found ) {
885 Cost cvtCost = computeApplicationConversionCost( withFunc, symtab );
886
887 PRINT(
888 auto appExpr = withFunc->expr.strict_as< ast::ApplicationExpr >();
889 auto pointer = appExpr->func->result.strict_as< ast::PointerType >();
890 auto function = pointer->base.strict_as< ast::FunctionType >();
891
892 std::cerr << "Case +++++++++++++ " << appExpr->func << std::endl;
893 std::cerr << "parameters are:" << std::endl;
894 ast::printAll( std::cerr, function->params, 2 );
895 std::cerr << "arguments are:" << std::endl;
896 ast::printAll( std::cerr, appExpr->args, 2 );
897 std::cerr << "bindings are:" << std::endl;
898 ast::print( std::cerr, withFunc->env, 2 );
899 std::cerr << "cost is: " << withFunc->cost << std::endl;
900 std::cerr << "cost of conversion is:" << cvtCost << std::endl;
901 )
902
903 if ( cvtCost != Cost::infinity ) {
904 withFunc->cvtCost = cvtCost;
905 candidates.emplace_back( move( withFunc ) );
906 }
907 }
908 found = move( candidates );
909
910 // use a new list so that candidates are not examined by addAnonConversions twice
911 CandidateList winners = findMinCost( found );
912 promoteCvtCost( winners );
913
914 // function may return a struct/union value, in which case we need to add candidates
915 // for implicit conversions to each of the anonymous members, which must happen after
916 // `findMinCost`, since anon conversions are never the cheapest
917 for ( const CandidateRef & c : winners ) {
918 addAnonConversions( c );
919 }
920 spliceBegin( candidates, winners );
921
922 if ( candidates.empty() && targetType && ! targetType->isVoid() ) {
923 // If resolution is unsuccessful with a target type, try again without, since it
924 // will sometimes succeed when it wouldn't with a target type binding.
925 // For example:
926 // forall( otype T ) T & ?[]( T *, ptrdiff_t );
927 // const char * x = "hello world";
928 // unsigned char ch = x[0];
929 // Fails with simple return type binding (xxx -- check this!) as follows:
930 // * T is bound to unsigned char
931 // * (x: const char *) is unified with unsigned char *, which fails
932 // xxx -- fix this better
933 targetType = nullptr;
934 postvisit( untypedExpr );
935 }
936 }
937
938 /// true if expression is an lvalue
939 static bool isLvalue( const ast::Expr * x ) {
940 return x->result && ( x->result->is_lvalue() || x->result.as< ast::ReferenceType >() );
941 }
942
943 void postvisit( const ast::AddressExpr * addressExpr ) {
944 CandidateFinder finder{ symtab, tenv };
945 finder.find( addressExpr->arg );
946 for ( CandidateRef & r : finder.candidates ) {
947 if ( ! isLvalue( r->expr ) ) continue;
948 addCandidate( *r, new ast::AddressExpr{ addressExpr->location, r->expr } );
949 }
950 }
951
952 void postvisit( const ast::LabelAddressExpr * labelExpr ) {
953 addCandidate( labelExpr, tenv );
954 }
955
956 void postvisit( const ast::CastExpr * castExpr ) {
957 ast::ptr< ast::Type > toType = castExpr->result;
958 assert( toType );
959 toType = resolveTypeof( toType, symtab );
960 toType = SymTab::validateType( toType, symtab );
961 toType = adjustExprType( toType, tenv, symtab );
962
963 CandidateFinder finder{ symtab, tenv, toType };
964 finder.find( castExpr->arg, ResolvMode::withAdjustment() );
965
966 CandidateList matches;
967 for ( CandidateRef & cand : finder.candidates ) {
968 ast::AssertionSet need( cand->need.begin(), cand->need.end() ), have;
969 ast::OpenVarSet open( cand->open );
970
971 cand->env.extractOpenVars( open );
972
973 // It is possible that a cast can throw away some values in a multiply-valued
974 // expression, e.g. cast-to-void, one value to zero. Figure out the prefix of the
975 // subexpression results that are cast directly. The candidate is invalid if it
976 // has fewer results than there are types to cast to.
977 int discardedValues = cand->expr->result->size() - toType->size();
978 if ( discardedValues < 0 ) continue;
979
980 // unification run for side-effects
981 unify( toType, cand->expr->result, cand->env, need, have, open, symtab );
982 Cost thisCost = castCost( cand->expr->result, toType, symtab, cand->env );
983 PRINT(
984 std::cerr << "working on cast with result: " << toType << std::endl;
985 std::cerr << "and expr type: " << cand->expr->result << std::endl;
986 std::cerr << "env: " << cand->env << std::endl;
987 )
988 if ( thisCost != Cost::infinity ) {
989 PRINT(
990 std::cerr << "has finite cost." << std::endl;
991 )
992 // count one safe conversion for each value that is thrown away
993 thisCost.incSafe( discardedValues );
994 CandidateRef newCand = std::make_shared<Candidate>(
995 restructureCast( cand->expr, toType, castExpr->isGenerated ),
996 copy( cand->env ), move( open ), move( need ), cand->cost,
997 cand->cost + thisCost );
998 inferParameters( newCand, matches );
999 }
1000 }
1001
1002 // castExpr->result should be replaced with toType
1003 // candidates => matches
1004
1005 #warning unimplemented
1006 (void)castExpr;
1007 assert(false);
1008 }
1009
1010 void postvisit( const ast::VirtualCastExpr * castExpr ) {
1011 assertf( castExpr->result, "Implicit virtual cast targets not yet supported." );
1012 CandidateFinder finder{ symtab, tenv };
1013 // don't prune here, all alternatives guaranteed to have same type
1014 finder.find( castExpr->arg, ResolvMode::withoutPrune() );
1015 for ( CandidateRef & r : finder.candidates ) {
1016 addCandidate(
1017 *r,
1018 new ast::VirtualCastExpr{ castExpr->location, r->expr, castExpr->result } );
1019 }
1020 }
1021
1022 void postvisit( const ast::UntypedMemberExpr * memberExpr ) {
1023 #warning unimplemented
1024 (void)memberExpr;
1025 assert(false);
1026 }
1027
1028 void postvisit( const ast::MemberExpr * memberExpr ) {
1029 addCandidate( memberExpr, tenv );
1030 }
1031
1032 void postvisit( const ast::NameExpr * variableExpr ) {
1033 #warning unimplemented
1034 (void)variableExpr;
1035 assert(false);
1036 }
1037
1038 void postvisit( const ast::VariableExpr * variableExpr ) {
1039 // not sufficient to just pass `variableExpr` here, type might have changed since
1040 // creation
1041 addCandidate(
1042 new ast::VariableExpr{ variableExpr->location, variableExpr->var }, tenv );
1043 }
1044
1045 void postvisit( const ast::ConstantExpr * constantExpr ) {
1046 addCandidate( constantExpr, tenv );
1047 }
1048
1049 void postvisit( const ast::SizeofExpr * sizeofExpr ) {
1050 #warning unimplemented
1051 (void)sizeofExpr;
1052 assert(false);
1053 }
1054
1055 void postvisit( const ast::AlignofExpr * alignofExpr ) {
1056 #warning unimplemented
1057 (void)alignofExpr;
1058 assert(false);
1059 }
1060
1061 void postvisit( const ast::UntypedOffsetofExpr * offsetofExpr ) {
1062 #warning unimplemented
1063 (void)offsetofExpr;
1064 assert(false);
1065 }
1066
1067 void postvisit( const ast::OffsetofExpr * offsetofExpr ) {
1068 addCandidate( offsetofExpr, tenv );
1069 }
1070
1071 void postvisit( const ast::OffsetPackExpr * offsetPackExpr ) {
1072 addCandidate( offsetPackExpr, tenv );
1073 }
1074
1075 void postvisit( const ast::LogicalExpr * logicalExpr ) {
1076 CandidateFinder finder1{ symtab, tenv };
1077 finder1.find( logicalExpr->arg1, ResolvMode::withAdjustment() );
1078 if ( finder1.candidates.empty() ) return;
1079
1080 CandidateFinder finder2{ symtab, tenv };
1081 finder2.find( logicalExpr->arg2, ResolvMode::withAdjustment() );
1082 if ( finder2.candidates.empty() ) return;
1083
1084 for ( const CandidateRef & r1 : finder1.candidates ) {
1085 for ( const CandidateRef & r2 : finder2.candidates ) {
1086 ast::TypeEnvironment env{ r1->env };
1087 env.simpleCombine( r2->env );
1088 ast::OpenVarSet open{ r1->open };
1089 mergeOpenVars( open, r2->open );
1090 ast::AssertionSet need;
1091 mergeAssertionSet( need, r1->need );
1092 mergeAssertionSet( need, r2->need );
1093
1094 addCandidate(
1095 new ast::LogicalExpr{
1096 logicalExpr->location, r1->expr, r2->expr, logicalExpr->isAnd },
1097 move( env ), move( open ), move( need ), r1->cost + r2->cost );
1098 }
1099 }
1100 }
1101
1102 void postvisit( const ast::ConditionalExpr * conditionalExpr ) {
1103 // candidates for condition
1104 CandidateFinder finder1{ symtab, tenv };
1105 finder1.find( conditionalExpr->arg1, ResolvMode::withAdjustment() );
1106 if ( finder1.candidates.empty() ) return;
1107
1108 // candidates for true result
1109 CandidateFinder finder2{ symtab, tenv };
1110 finder2.find( conditionalExpr->arg2, ResolvMode::withAdjustment() );
1111 if ( finder2.candidates.empty() ) return;
1112
1113 // candidates for false result
1114 CandidateFinder finder3{ symtab, tenv };
1115 finder3.find( conditionalExpr->arg3, ResolvMode::withAdjustment() );
1116 if ( finder3.candidates.empty() ) return;
1117
1118 for ( const CandidateRef & r1 : finder1.candidates ) {
1119 for ( const CandidateRef & r2 : finder2.candidates ) {
1120 for ( const CandidateRef & r3 : finder3.candidates ) {
1121 ast::TypeEnvironment env{ r1->env };
1122 env.simpleCombine( r2->env );
1123 env.simpleCombine( r3->env );
1124 ast::OpenVarSet open{ r1->open };
1125 mergeOpenVars( open, r2->open );
1126 mergeOpenVars( open, r3->open );
1127 ast::AssertionSet need;
1128 mergeAssertionSet( need, r1->need );
1129 mergeAssertionSet( need, r2->need );
1130 mergeAssertionSet( need, r3->need );
1131 ast::AssertionSet have;
1132
1133 // unify true and false results, then infer parameters to produce new
1134 // candidates
1135 ast::ptr< ast::Type > common;
1136 if (
1137 unify(
1138 r2->expr->result, r3->expr->result, env, need, have, open, symtab,
1139 common )
1140 ) {
1141 #warning unimplemented
1142 assert(false);
1143 }
1144 }
1145 }
1146 }
1147 }
1148
1149 void postvisit( const ast::CommaExpr * commaExpr ) {
1150 ast::TypeEnvironment env{ tenv };
1151 ast::ptr< ast::Expr > arg1 = resolveInVoidContext( commaExpr->arg1, symtab, env );
1152
1153 CandidateFinder finder2{ symtab, env };
1154 finder2.find( commaExpr->arg2, ResolvMode::withAdjustment() );
1155
1156 for ( const CandidateRef & r2 : finder2.candidates ) {
1157 addCandidate( *r2, new ast::CommaExpr{ commaExpr->location, arg1, r2->expr } );
1158 }
1159 }
1160
1161 void postvisit( const ast::ImplicitCopyCtorExpr * ctorExpr ) {
1162 addCandidate( ctorExpr, tenv );
1163 }
1164
1165 void postvisit( const ast::ConstructorExpr * ctorExpr ) {
1166 CandidateFinder finder{ symtab, tenv };
1167 finder.find( ctorExpr->callExpr, ResolvMode::withoutPrune() );
1168 for ( CandidateRef & r : finder.candidates ) {
1169 addCandidate( *r, new ast::ConstructorExpr{ ctorExpr->location, r->expr } );
1170 }
1171 }
1172
1173 void postvisit( const ast::RangeExpr * rangeExpr ) {
1174 // resolve low and high, accept candidates where low and high types unify
1175 CandidateFinder finder1{ symtab, tenv };
1176 finder1.find( rangeExpr->low, ResolvMode::withAdjustment() );
1177 if ( finder1.candidates.empty() ) return;
1178
1179 CandidateFinder finder2{ symtab, tenv };
1180 finder2.find( rangeExpr->high, ResolvMode::withAdjustment() );
1181 if ( finder2.candidates.empty() ) return;
1182
1183 for ( const CandidateRef & r1 : finder1.candidates ) {
1184 for ( const CandidateRef & r2 : finder2.candidates ) {
1185 ast::TypeEnvironment env{ r1->env };
1186 env.simpleCombine( r2->env );
1187 ast::OpenVarSet open{ r1->open };
1188 mergeOpenVars( open, r2->open );
1189 ast::AssertionSet need;
1190 mergeAssertionSet( need, r1->need );
1191 mergeAssertionSet( need, r2->need );
1192 ast::AssertionSet have;
1193
1194 ast::ptr< ast::Type > common;
1195 if (
1196 unify(
1197 r1->expr->result, r2->expr->result, env, need, have, open, symtab,
1198 common )
1199 ) {
1200 ast::RangeExpr * newExpr =
1201 new ast::RangeExpr{ rangeExpr->location, r1->expr, r2->expr };
1202 newExpr->result = common ? common : r1->expr->result;
1203
1204 #warning unimplemented
1205 assert(false);
1206 }
1207 }
1208 }
1209 }
1210
1211 void postvisit( const ast::UntypedTupleExpr * tupleExpr ) {
1212 std::vector< CandidateFinder > subCandidates =
1213 selfFinder.findSubExprs( tupleExpr->exprs );
1214 std::vector< CandidateList > possibilities;
1215 combos( subCandidates.begin(), subCandidates.end(), back_inserter( possibilities ) );
1216
1217 for ( const CandidateList & subs : possibilities ) {
1218 std::vector< ast::ptr< ast::Expr > > exprs;
1219 exprs.reserve( subs.size() );
1220 for ( const CandidateRef & sub : subs ) { exprs.emplace_back( sub->expr ); }
1221
1222 ast::TypeEnvironment env;
1223 ast::OpenVarSet open;
1224 ast::AssertionSet need;
1225 for ( const CandidateRef & sub : subs ) {
1226 env.simpleCombine( sub->env );
1227 mergeOpenVars( open, sub->open );
1228 mergeAssertionSet( need, sub->need );
1229 }
1230
1231 addCandidate(
1232 new ast::TupleExpr{ tupleExpr->location, move( exprs ) },
1233 move( env ), move( open ), move( need ), sumCost( subs ) );
1234 }
1235 }
1236
1237 void postvisit( const ast::TupleExpr * tupleExpr ) {
1238 addCandidate( tupleExpr, tenv );
1239 }
1240
1241 void postvisit( const ast::TupleIndexExpr * tupleExpr ) {
1242 addCandidate( tupleExpr, tenv );
1243 }
1244
1245 void postvisit( const ast::TupleAssignExpr * tupleExpr ) {
1246 addCandidate( tupleExpr, tenv );
1247 }
1248
1249 void postvisit( const ast::UniqueExpr * unqExpr ) {
1250 CandidateFinder finder{ symtab, tenv };
1251 finder.find( unqExpr->expr, ResolvMode::withAdjustment() );
1252 for ( CandidateRef & r : finder.candidates ) {
1253 // ensure that the the id is passed on so that the expressions are "linked"
1254 addCandidate( *r, new ast::UniqueExpr{ unqExpr->location, r->expr, unqExpr->id } );
1255 }
1256 }
1257
1258 void postvisit( const ast::StmtExpr * stmtExpr ) {
1259 #warning unimplemented
1260 (void)stmtExpr;
1261 assert(false);
1262 }
1263
1264 void postvisit( const ast::UntypedInitExpr * initExpr ) {
1265 #warning unimplemented
1266 (void)initExpr;
1267 assert(false);
1268 }
1269
1270 void postvisit( const ast::InitExpr * ) {
1271 assertf( false, "CandidateFinder should never see a resolved InitExpr." );
1272 }
1273
1274 void postvisit( const ast::DeletedExpr * ) {
1275 assertf( false, "CandidateFinder should never see a DeletedExpr." );
1276 }
1277
1278 void postvisit( const ast::GenericExpr * ) {
1279 assertf( false, "_Generic is not yet supported." );
1280 }
1281 };
1282
1283 /// Prunes a list of candidates down to those that have the minimum conversion cost for a given
1284 /// return type. Skips ambiguous candidates.
1285 CandidateList pruneCandidates( CandidateList & candidates ) {
1286 struct PruneStruct {
1287 CandidateRef candidate;
1288 bool ambiguous;
1289
1290 PruneStruct() = default;
1291 PruneStruct( const CandidateRef & c ) : candidate( c ), ambiguous( false ) {}
1292 };
1293
1294 // find lowest-cost candidate for each type
1295 std::unordered_map< std::string, PruneStruct > selected;
1296 for ( CandidateRef & candidate : candidates ) {
1297 std::string mangleName;
1298 {
1299 ast::ptr< ast::Type > newType = candidate->expr->result;
1300 candidate->env.apply( newType );
1301 mangleName = Mangle::mangle( newType );
1302 }
1303
1304 auto found = selected.find( mangleName );
1305 if ( found != selected.end() ) {
1306 if ( candidate->cost < found->second.candidate->cost ) {
1307 PRINT(
1308 std::cerr << "cost " << candidate->cost << " beats "
1309 << found->second.candidate->cost << std::endl;
1310 )
1311
1312 found->second = PruneStruct{ candidate };
1313 } else if ( candidate->cost == found->second.candidate->cost ) {
1314 // if one of the candidates contains a deleted identifier, can pick the other,
1315 // since deleted expressions should not be ambiguous if there is another option
1316 // that is at least as good
1317 if ( findDeletedExpr( candidate->expr ) ) {
1318 // do nothing
1319 PRINT( std::cerr << "candidate is deleted" << std::endl; )
1320 } else if ( findDeletedExpr( found->second.candidate->expr ) ) {
1321 PRINT( std::cerr << "current is deleted" << std::endl; )
1322 found->second = PruneStruct{ candidate };
1323 } else {
1324 PRINT( std::cerr << "marking ambiguous" << std::endl; )
1325 found->second.ambiguous = true;
1326 }
1327 } else {
1328 PRINT(
1329 std::cerr << "cost " << candidate->cost << " loses to "
1330 << found->second.candidate->cost << std::endl;
1331 )
1332 }
1333 } else {
1334 selected.emplace_hint( found, mangleName, candidate );
1335 }
1336 }
1337
1338 // report unambiguous min-cost candidates
1339 CandidateList out;
1340 for ( auto & target : selected ) {
1341 if ( target.second.ambiguous ) continue;
1342
1343 CandidateRef cand = target.second.candidate;
1344
1345 ast::ptr< ast::Type > newResult = cand->expr->result;
1346 cand->env.applyFree( newResult );
1347 cand->expr = ast::mutate_field(
1348 cand->expr.get(), &ast::Expr::result, move( newResult ) );
1349
1350 out.emplace_back( cand );
1351 }
1352 return out;
1353 }
1354
1355} // anonymous namespace
1356
1357void CandidateFinder::find( const ast::Expr * expr, ResolvMode mode ) {
1358 // Find alternatives for expression
1359 ast::Pass<Finder> finder{ *this };
1360 expr->accept( finder );
1361
1362 if ( mode.failFast && candidates.empty() ) {
1363 SemanticError( expr, "No reasonable alternatives for expression " );
1364 }
1365
1366 if ( mode.satisfyAssns || mode.prune ) {
1367 // trim candidates to just those where the assertions are satisfiable
1368 // - necessary pre-requisite to pruning
1369 CandidateList satisfied;
1370 std::vector< std::string > errors;
1371 for ( auto & candidate : candidates ) {
1372 satisfyAssertions( *candidate, symtab, satisfied, errors );
1373 }
1374
1375 // fail early if none such
1376 if ( mode.failFast && satisfied.empty() ) {
1377 std::ostringstream stream;
1378 stream << "No alternatives with satisfiable assertions for " << expr << "\n";
1379 for ( const auto& err : errors ) {
1380 stream << err;
1381 }
1382 SemanticError( expr->location, stream.str() );
1383 }
1384
1385 // reset candidates
1386 candidates = move( satisfied );
1387 }
1388
1389 if ( mode.prune ) {
1390 // trim candidates to single best one
1391 PRINT(
1392 std::cerr << "alternatives before prune:" << std::endl;
1393 print( std::cerr, candidates );
1394 )
1395
1396 CandidateList pruned = pruneCandidates( candidates );
1397
1398 if ( mode.failFast && pruned.empty() ) {
1399 std::ostringstream stream;
1400 CandidateList winners = findMinCost( candidates );
1401 stream << "Cannot choose between " << winners.size() << " alternatives for "
1402 "expression\n";
1403 ast::print( stream, expr );
1404 stream << " Alternatives are:\n";
1405 print( stream, winners, 1 );
1406 SemanticError( expr->location, stream.str() );
1407 }
1408
1409 auto oldsize = candidates.size();
1410 candidates = move( pruned );
1411
1412 PRINT(
1413 std::cerr << "there are " << oldsize << " alternatives before elimination" << std::endl;
1414 )
1415 PRINT(
1416 std::cerr << "there are " << candidates.size() << " alternatives after elimination"
1417 << std::endl;
1418 )
1419 }
1420
1421 // adjust types after pruning so that types substituted by pruneAlternatives are correctly
1422 // adjusted
1423 if ( mode.adjust ) {
1424 for ( CandidateRef & r : candidates ) {
1425 r->expr = ast::mutate_field(
1426 r->expr.get(), &ast::Expr::result,
1427 adjustExprType( r->expr->result, r->env, symtab ) );
1428 }
1429 }
1430
1431 // Central location to handle gcc extension keyword, etc. for all expressions
1432 for ( CandidateRef & r : candidates ) {
1433 if ( r->expr->extension != expr->extension ) {
1434 r->expr.get_and_mutate()->extension = expr->extension;
1435 }
1436 }
1437}
1438
1439std::vector< CandidateFinder > CandidateFinder::findSubExprs(
1440 const std::vector< ast::ptr< ast::Expr > > & xs
1441) {
1442 std::vector< CandidateFinder > out;
1443
1444 for ( const auto & x : xs ) {
1445 out.emplace_back( symtab, env );
1446 out.back().find( x, ResolvMode::withAdjustment() );
1447
1448 PRINT(
1449 std::cerr << "findSubExprs" << std::endl;
1450 print( std::cerr, out.back().candidates );
1451 )
1452 }
1453
1454 return out;
1455}
1456
1457} // namespace ResolvExpr
1458
1459// Local Variables: //
1460// tab-width: 4 //
1461// mode: c++ //
1462// compile-command: "make install" //
1463// End: //
Note: See TracBrowser for help on using the repository browser.