source: src/ResolvExpr/CandidateFinder.cpp@ 6e1e2d0

ADT ast-experimental
Last change on this file since 6e1e2d0 was eb8d791, checked in by Andrew Beach <ajbeach@…>, 2 years ago

CandidateFinder fills in the CodeLocation on a generated expression. With that and recent changes, the fills seem to be redundent now, so I removed them.
  • Property mode set to 100644
File size: 71.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 : Andrew Beach
12// Last Modified On : Wed Mar 16 11:58:00 2022
13// Update Count : 3
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 "AdjustExprType.hpp"
26#include "Candidate.hpp"
27#include "CastCost.hpp" // for castCost
28#include "CompilationState.h"
29#include "ConversionCost.h" // for conversionCast
30#include "Cost.h"
31#include "ExplodedArg.hpp"
32#include "PolyCost.hpp"
33#include "RenameVars.h" // for renameTyVars
34#include "Resolver.h"
35#include "ResolveTypeof.h"
36#include "SatisfyAssertions.hpp"
37#include "SpecCost.hpp"
38#include "typeops.h" // for combos
39#include "Unify.h"
40#include "AST/Expr.hpp"
41#include "AST/Node.hpp"
42#include "AST/Pass.hpp"
43#include "AST/Print.hpp"
44#include "AST/SymbolTable.hpp"
45#include "AST/Type.hpp"
46#include "Common/utility.h" // for move, copy
47#include "SymTab/Mangler.h"
48#include "Tuples/Tuples.h" // for handleTupleAssignment
49#include "InitTweak/InitTweak.h" // for getPointerBase
50
51#include "Common/Stats/Counter.h"
52
53#define PRINT( text ) if ( resolvep ) { text }
54
55namespace ResolvExpr {
56
57/// Unique identifier for matching expression resolutions to their requesting expression
58UniqueId globalResnSlot = 0;
59
60namespace {
61 /// First index is which argument, second is which alternative, third is which exploded element
62 using ExplodedArgs_new = std::deque< std::vector< ExplodedArg > >;
63
64 /// Returns a list of alternatives with the minimum cost in the given list
65 CandidateList findMinCost( const CandidateList & candidates ) {
66 CandidateList out;
67 Cost minCost = Cost::infinity;
68 for ( const CandidateRef & r : candidates ) {
69 if ( r->cost < minCost ) {
70 minCost = r->cost;
71 out.clear();
72 out.emplace_back( r );
73 } else if ( r->cost == minCost ) {
74 out.emplace_back( r );
75 }
76 }
77 return out;
78 }
79
80 /// Computes conversion cost for a given expression to a given type
81 const ast::Expr * computeExpressionConversionCost(
82 const ast::Expr * arg, const ast::Type * paramType, const ast::SymbolTable & symtab, const ast::TypeEnvironment & env, Cost & outCost
83 ) {
84 Cost convCost = computeConversionCost(
85 arg->result, paramType, arg->get_lvalue(), symtab, env );
86 outCost += convCost;
87
88 // If there is a non-zero conversion cost, ignoring poly cost, then the expression requires
89 // conversion. Ignore poly cost for now, since this requires resolution of the cast to
90 // infer parameters and this does not currently work for the reason stated below
91 Cost tmpCost = convCost;
92 tmpCost.incPoly( -tmpCost.get_polyCost() );
93 if ( tmpCost != Cost::zero ) {
94 ast::ptr< ast::Type > newType = paramType;
95 env.apply( newType );
96 return new ast::CastExpr{ arg, newType };
97
98 // xxx - *should* be able to resolve this cast, but at the moment pointers are not
99 // castable to zero_t, but are implicitly convertible. This is clearly inconsistent,
100 // once this is fixed it should be possible to resolve the cast.
101 // xxx - this isn't working, it appears because type1 (parameter) is seen as widenable,
102 // but it shouldn't be because this makes the conversion from DT* to DT* since
103 // commontype(zero_t, DT*) is DT*, rather than nothing
104
105 // CandidateFinder finder{ symtab, env };
106 // finder.find( arg, ResolvMode::withAdjustment() );
107 // assertf( finder.candidates.size() > 0,
108 // "Somehow castable expression failed to find alternatives." );
109 // assertf( finder.candidates.size() == 1,
110 // "Somehow got multiple alternatives for known cast expression." );
111 // return finder.candidates.front()->expr;
112 }
113
114 return arg;
115 }
116
117 /// Computes conversion cost for a given candidate
118 Cost computeApplicationConversionCost(
119 CandidateRef cand, const ast::SymbolTable & symtab
120 ) {
121 auto appExpr = cand->expr.strict_as< ast::ApplicationExpr >();
122 auto pointer = appExpr->func->result.strict_as< ast::PointerType >();
123 auto function = pointer->base.strict_as< ast::FunctionType >();
124
125 Cost convCost = Cost::zero;
126 const auto & params = function->params;
127 auto param = params.begin();
128 auto & args = appExpr->args;
129
130 for ( unsigned i = 0; i < args.size(); ++i ) {
131 const ast::Type * argType = args[i]->result;
132 PRINT(
133 std::cerr << "arg expression:" << std::endl;
134 ast::print( std::cerr, args[i], 2 );
135 std::cerr << "--- results are" << std::endl;
136 ast::print( std::cerr, argType, 2 );
137 )
138
139 if ( param == params.end() ) {
140 if ( function->isVarArgs ) {
141 convCost.incUnsafe();
142 PRINT( std::cerr << "end of params with varargs function: inc unsafe: "
143 << convCost << std::endl; ; )
144 // convert reference-typed expressions into value-typed expressions
145 cand->expr = ast::mutate_field_index(
146 appExpr, &ast::ApplicationExpr::args, i,
147 referenceToRvalueConversion( args[i], convCost ) );
148 continue;
149 } else return Cost::infinity;
150 }
151
152 if ( auto def = args[i].as< ast::DefaultArgExpr >() ) {
153 // Default arguments should be free - don't include conversion cost.
154 // Unwrap them here because they are not relevant to the rest of the system
155 cand->expr = ast::mutate_field_index(
156 appExpr, &ast::ApplicationExpr::args, i, def->expr );
157 ++param;
158 continue;
159 }
160
161 // mark conversion cost and also specialization cost of param type
162 // const ast::Type * paramType = (*param)->get_type();
163 cand->expr = ast::mutate_field_index(
164 appExpr, &ast::ApplicationExpr::args, i,
165 computeExpressionConversionCost(
166 args[i], *param, symtab, cand->env, convCost ) );
167 convCost.decSpec( specCost( *param ) );
168 ++param; // can't be in for-loop update because of the continue
169 }
170
171 if ( param != params.end() ) return Cost::infinity;
172
173 // specialization cost of return types can't be accounted for directly, it disables
174 // otherwise-identical calls, like this example based on auto-newline in the I/O lib:
175 //
176 // forall(otype OS) {
177 // void ?|?(OS&, int); // with newline
178 // OS& ?|?(OS&, int); // no newline, always chosen due to more specialization
179 // }
180
181 // mark type variable and specialization cost of forall clause
182 convCost.incVar( function->forall.size() );
183 convCost.decSpec( function->assertions.size() );
184
185 return convCost;
186 }
187
188 void makeUnifiableVars(
189 const ast::FunctionType * type, ast::OpenVarSet & unifiableVars,
190 ast::AssertionSet & need
191 ) {
192 for ( auto & tyvar : type->forall ) {
193 unifiableVars[ *tyvar ] = ast::TypeData{ tyvar->base };
194 }
195 for ( auto & assn : type->assertions ) {
196 need[ assn ].isUsed = true;
197 }
198 }
199
200 /// Gets a default value from an initializer, nullptr if not present
201 const ast::ConstantExpr * getDefaultValue( const ast::Init * init ) {
202 if ( auto si = dynamic_cast< const ast::SingleInit * >( init ) ) {
203 if ( auto ce = si->value.as< ast::CastExpr >() ) {
204 return ce->arg.as< ast::ConstantExpr >();
205 } else {
206 return si->value.as< ast::ConstantExpr >();
207 }
208 }
209 return nullptr;
210 }
211
212 /// State to iteratively build a match of parameter expressions to arguments
213 struct ArgPack {
214 std::size_t parent; ///< Index of parent pack
215 ast::ptr< ast::Expr > expr; ///< The argument stored here
216 Cost cost; ///< The cost of this argument
217 ast::TypeEnvironment env; ///< Environment for this pack
218 ast::AssertionSet need; ///< Assertions outstanding for this pack
219 ast::AssertionSet have; ///< Assertions found for this pack
220 ast::OpenVarSet open; ///< Open variables for this pack
221 unsigned nextArg; ///< Index of next argument in arguments list
222 unsigned tupleStart; ///< Number of tuples that start at this index
223 unsigned nextExpl; ///< Index of next exploded element
224 unsigned explAlt; ///< Index of alternative for nextExpl > 0
225
226 ArgPack()
227 : parent( 0 ), expr(), cost( Cost::zero ), env(), need(), have(), open(), nextArg( 0 ),
228 tupleStart( 0 ), nextExpl( 0 ), explAlt( 0 ) {}
229
230 ArgPack(
231 const ast::TypeEnvironment & env, const ast::AssertionSet & need,
232 const ast::AssertionSet & have, const ast::OpenVarSet & open )
233 : parent( 0 ), expr(), cost( Cost::zero ), env( env ), need( need ), have( have ),
234 open( open ), nextArg( 0 ), tupleStart( 0 ), nextExpl( 0 ), explAlt( 0 ) {}
235
236 ArgPack(
237 std::size_t parent, const ast::Expr * expr, ast::TypeEnvironment && env,
238 ast::AssertionSet && need, ast::AssertionSet && have, ast::OpenVarSet && open,
239 unsigned nextArg, unsigned tupleStart = 0, Cost cost = Cost::zero,
240 unsigned nextExpl = 0, unsigned explAlt = 0 )
241 : parent(parent), expr( expr ), cost( cost ), env( std::move( env ) ), need( std::move( need ) ),
242 have( std::move( have ) ), open( std::move( open ) ), nextArg( nextArg ), tupleStart( tupleStart ),
243 nextExpl( nextExpl ), explAlt( explAlt ) {}
244
245 ArgPack(
246 const ArgPack & o, ast::TypeEnvironment && env, ast::AssertionSet && need,
247 ast::AssertionSet && have, ast::OpenVarSet && open, unsigned nextArg, Cost added )
248 : parent( o.parent ), expr( o.expr ), cost( o.cost + added ), env( std::move( env ) ),
249 need( std::move( need ) ), have( std::move( have ) ), open( std::move( open ) ), nextArg( nextArg ),
250 tupleStart( o.tupleStart ), nextExpl( 0 ), explAlt( 0 ) {}
251
252 /// true if this pack is in the middle of an exploded argument
253 bool hasExpl() const { return nextExpl > 0; }
254
255 /// Gets the list of exploded candidates for this pack
256 const ExplodedArg & getExpl( const ExplodedArgs_new & args ) const {
257 return args[ nextArg-1 ][ explAlt ];
258 }
259
260 /// Ends a tuple expression, consolidating the appropriate args
261 void endTuple( const std::vector< ArgPack > & packs ) {
262 // add all expressions in tuple to list, summing cost
263 std::deque< const ast::Expr * > exprs;
264 const ArgPack * pack = this;
265 if ( expr ) { exprs.emplace_front( expr ); }
266 while ( pack->tupleStart == 0 ) {
267 pack = &packs[pack->parent];
268 exprs.emplace_front( pack->expr );
269 cost += pack->cost;
270 }
271 // reset pack to appropriate tuple
272 std::vector< ast::ptr< ast::Expr > > exprv( exprs.begin(), exprs.end() );
273 expr = new ast::TupleExpr{ expr->location, std::move( exprv ) };
274 tupleStart = pack->tupleStart - 1;
275 parent = pack->parent;
276 }
277 };
278
279 /// Instantiates an argument to match a parameter, returns false if no matching results left
280 bool instantiateArgument(
281 const CodeLocation & location,
282 const ast::Type * paramType, const ast::Init * init, const ExplodedArgs_new & args,
283 std::vector< ArgPack > & results, std::size_t & genStart, const ast::SymbolTable & symtab,
284 unsigned nTuples = 0
285 ) {
286 if ( auto tupleType = dynamic_cast< const ast::TupleType * >( paramType ) ) {
287 // paramType is a TupleType -- group args into a TupleExpr
288 ++nTuples;
289 for ( const ast::Type * type : *tupleType ) {
290 // xxx - dropping initializer changes behaviour from previous, but seems correct
291 // ^^^ need to handle the case where a tuple has a default argument
292 if ( ! instantiateArgument( location,
293 type, nullptr, args, results, genStart, symtab, nTuples ) ) return false;
294 nTuples = 0;
295 }
296 // re-constitute tuples for final generation
297 for ( auto i = genStart; i < results.size(); ++i ) {
298 results[i].endTuple( results );
299 }
300 return true;
301 } else if ( const ast::TypeInstType * ttype = Tuples::isTtype( paramType ) ) {
302 // paramType is a ttype, consumes all remaining arguments
303
304 // completed tuples; will be spliced to end of results to finish
305 std::vector< ArgPack > finalResults{};
306
307 // iterate until all results completed
308 std::size_t genEnd;
309 ++nTuples;
310 do {
311 genEnd = results.size();
312
313 // add another argument to results
314 for ( std::size_t i = genStart; i < genEnd; ++i ) {
315 unsigned nextArg = results[i].nextArg;
316
317 // use next element of exploded tuple if present
318 if ( results[i].hasExpl() ) {
319 const ExplodedArg & expl = results[i].getExpl( args );
320
321 unsigned nextExpl = results[i].nextExpl + 1;
322 if ( nextExpl == expl.exprs.size() ) { nextExpl = 0; }
323
324 results.emplace_back(
325 i, expl.exprs[ results[i].nextExpl ], copy( results[i].env ),
326 copy( results[i].need ), copy( results[i].have ),
327 copy( results[i].open ), nextArg, nTuples, Cost::zero, nextExpl,
328 results[i].explAlt );
329
330 continue;
331 }
332
333 // finish result when out of arguments
334 if ( nextArg >= args.size() ) {
335 ArgPack newResult{
336 results[i].env, results[i].need, results[i].have, results[i].open };
337 newResult.nextArg = nextArg;
338 const ast::Type * argType = nullptr;
339
340 if ( nTuples > 0 || ! results[i].expr ) {
341 // first iteration or no expression to clone,
342 // push empty tuple expression
343 newResult.parent = i;
344 newResult.expr = new ast::TupleExpr( location, {} );
345 argType = newResult.expr->result;
346 } else {
347 // clone result to collect tuple
348 newResult.parent = results[i].parent;
349 newResult.cost = results[i].cost;
350 newResult.tupleStart = results[i].tupleStart;
351 newResult.expr = results[i].expr;
352 argType = newResult.expr->result;
353
354 if ( results[i].tupleStart > 0 && Tuples::isTtype( argType ) ) {
355 // the case where a ttype value is passed directly is special,
356 // e.g. for argument forwarding purposes
357 // xxx - what if passing multiple arguments, last of which is
358 // ttype?
359 // xxx - what would happen if unify was changed so that unifying
360 // tuple
361 // types flattened both before unifying lists? then pass in
362 // TupleType (ttype) below.
363 --newResult.tupleStart;
364 } else {
365 // collapse leftover arguments into tuple
366 newResult.endTuple( results );
367 argType = newResult.expr->result;
368 }
369 }
370
371 // check unification for ttype before adding to final
372 if (
373 unify(
374 ttype, argType, newResult.env, newResult.need, newResult.have,
375 newResult.open, symtab )
376 ) {
377 finalResults.emplace_back( std::move( newResult ) );
378 }
379
380 continue;
381 }
382
383 // add each possible next argument
384 for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
385 const ExplodedArg & expl = args[nextArg][j];
386
387 // fresh copies of parent parameters for this iteration
388 ast::TypeEnvironment env = results[i].env;
389 ast::OpenVarSet open = results[i].open;
390
391 env.addActual( expl.env, open );
392
393 // skip empty tuple arguments by (nearly) cloning parent into next gen
394 if ( expl.exprs.empty() ) {
395 results.emplace_back(
396 results[i], std::move( env ), copy( results[i].need ),
397 copy( results[i].have ), std::move( open ), nextArg + 1, expl.cost );
398
399 continue;
400 }
401
402 // add new result
403 results.emplace_back(
404 i, expl.exprs.front(), std::move( env ), copy( results[i].need ),
405 copy( results[i].have ), std::move( open ), nextArg + 1, nTuples,
406 expl.cost, expl.exprs.size() == 1 ? 0 : 1, j );
407 }
408 }
409
410 // reset for next round
411 genStart = genEnd;
412 nTuples = 0;
413 } while ( genEnd != results.size() );
414
415 // splice final results onto results
416 for ( std::size_t i = 0; i < finalResults.size(); ++i ) {
417 results.emplace_back( std::move( finalResults[i] ) );
418 }
419 return ! finalResults.empty();
420 }
421
422 // iterate each current subresult
423 std::size_t genEnd = results.size();
424 for ( std::size_t i = genStart; i < genEnd; ++i ) {
425 unsigned nextArg = results[i].nextArg;
426
427 // use remainder of exploded tuple if present
428 if ( results[i].hasExpl() ) {
429 const ExplodedArg & expl = results[i].getExpl( args );
430 const ast::Expr * expr = expl.exprs[ results[i].nextExpl ];
431
432 ast::TypeEnvironment env = results[i].env;
433 ast::AssertionSet need = results[i].need, have = results[i].have;
434 ast::OpenVarSet open = results[i].open;
435
436 const ast::Type * argType = expr->result;
437
438 PRINT(
439 std::cerr << "param type is ";
440 ast::print( std::cerr, paramType );
441 std::cerr << std::endl << "arg type is ";
442 ast::print( std::cerr, argType );
443 std::cerr << std::endl;
444 )
445
446 if ( unify( paramType, argType, env, need, have, open, symtab ) ) {
447 unsigned nextExpl = results[i].nextExpl + 1;
448 if ( nextExpl == expl.exprs.size() ) { nextExpl = 0; }
449
450 results.emplace_back(
451 i, expr, std::move( env ), std::move( need ), std::move( have ), std::move( open ), nextArg,
452 nTuples, Cost::zero, nextExpl, results[i].explAlt );
453 }
454
455 continue;
456 }
457
458 // use default initializers if out of arguments
459 if ( nextArg >= args.size() ) {
460 if ( const ast::ConstantExpr * cnst = getDefaultValue( init ) ) {
461 ast::TypeEnvironment env = results[i].env;
462 ast::AssertionSet need = results[i].need, have = results[i].have;
463 ast::OpenVarSet open = results[i].open;
464
465 if ( unify( paramType, cnst->result, env, need, have, open, symtab ) ) {
466 results.emplace_back(
467 i, new ast::DefaultArgExpr{ cnst->location, cnst }, std::move( env ),
468 std::move( need ), std::move( have ), std::move( open ), nextArg, nTuples );
469 }
470 }
471
472 continue;
473 }
474
475 // Check each possible next argument
476 for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
477 const ExplodedArg & expl = args[nextArg][j];
478
479 // fresh copies of parent parameters for this iteration
480 ast::TypeEnvironment env = results[i].env;
481 ast::AssertionSet need = results[i].need, have = results[i].have;
482 ast::OpenVarSet open = results[i].open;
483
484 env.addActual( expl.env, open );
485
486 // skip empty tuple arguments by (nearly) cloning parent into next gen
487 if ( expl.exprs.empty() ) {
488 results.emplace_back(
489 results[i], std::move( env ), std::move( need ), std::move( have ), std::move( open ),
490 nextArg + 1, expl.cost );
491
492 continue;
493 }
494
495 // consider only first exploded arg
496 const ast::Expr * expr = expl.exprs.front();
497 const ast::Type * argType = expr->result;
498
499 PRINT(
500 std::cerr << "param type is ";
501 ast::print( std::cerr, paramType );
502 std::cerr << std::endl << "arg type is ";
503 ast::print( std::cerr, argType );
504 std::cerr << std::endl;
505 )
506
507 // attempt to unify types
508 if ( unify( paramType, argType, env, need, have, open, symtab ) ) {
509 // add new result
510 results.emplace_back(
511 i, expr, std::move( env ), std::move( need ), std::move( have ), std::move( open ),
512 nextArg + 1, nTuples, expl.cost, expl.exprs.size() == 1 ? 0 : 1, j );
513 }
514 }
515 }
516
517 // reset for next parameter
518 genStart = genEnd;
519
520 return genEnd != results.size(); // were any new results added?
521 }
522
523 /// Generate a cast expression from `arg` to `toType`
524 const ast::Expr * restructureCast(
525 ast::ptr< ast::Expr > & arg, const ast::Type * toType, ast::GeneratedFlag isGenerated = ast::GeneratedCast
526 ) {
527 if (
528 arg->result->size() > 1
529 && ! toType->isVoid()
530 && ! dynamic_cast< const ast::ReferenceType * >( toType )
531 ) {
532 // Argument is a tuple and the target type is neither void nor a reference. Cast each
533 // member of the tuple to its corresponding target type, producing the tuple of those
534 // cast expressions. If there are more components of the tuple than components in the
535 // target type, then excess components do not come out in the result expression (but
536 // UniqueExpr ensures that the side effects will still be produced)
537 if ( Tuples::maybeImpureIgnoreUnique( arg ) ) {
538 // expressions which may contain side effects require a single unique instance of
539 // the expression
540 arg = new ast::UniqueExpr{ arg->location, arg };
541 }
542 std::vector< ast::ptr< ast::Expr > > components;
543 for ( unsigned i = 0; i < toType->size(); ++i ) {
544 // cast each component
545 ast::ptr< ast::Expr > idx = new ast::TupleIndexExpr{ arg->location, arg, i };
546 components.emplace_back(
547 restructureCast( idx, toType->getComponent( i ), isGenerated ) );
548 }
549 return new ast::TupleExpr{ arg->location, std::move( components ) };
550 } else {
551 // handle normally
552 return new ast::CastExpr{ arg->location, arg, toType, isGenerated };
553 }
554 }
555
556 /// Gets the name from an untyped member expression (must be NameExpr)
557 const std::string & getMemberName( const ast::UntypedMemberExpr * memberExpr ) {
558 if ( memberExpr->member.as< ast::ConstantExpr >() ) {
559 SemanticError( memberExpr, "Indexed access to struct fields unsupported: " );
560 }
561
562 return memberExpr->member.strict_as< ast::NameExpr >()->name;
563 }
564
565 /// Actually visits expressions to find their candidate interpretations
566 class Finder final : public ast::WithShortCircuiting {
567 const ResolveContext & context;
568 const ast::SymbolTable & symtab;
569 public:
570 // static size_t traceId;
571 CandidateFinder & selfFinder;
572 CandidateList & candidates;
573 const ast::TypeEnvironment & tenv;
574 ast::ptr< ast::Type > & targetType;
575
576 enum Errors {
577 NotFound,
578 NoMatch,
579 ArgsToFew,
580 ArgsToMany,
581 RetsToFew,
582 RetsToMany,
583 NoReason
584 };
585
586 struct {
587 Errors code = NotFound;
588 } reason;
589
590 Finder( CandidateFinder & f )
591 : context( f.context ), symtab( context.symtab ), selfFinder( f ),
592 candidates( f.candidates ), tenv( f.env ), targetType( f.targetType ) {}
593
594 void previsit( const ast::Node * ) { visit_children = false; }
595
596 /// Convenience to add candidate to list
597 template<typename... Args>
598 void addCandidate( Args &&... args ) {
599 candidates.emplace_back( new Candidate{ std::forward<Args>( args )... } );
600 reason.code = NoReason;
601 }
602
603 void postvisit( const ast::ApplicationExpr * applicationExpr ) {
604 addCandidate( applicationExpr, tenv );
605 }
606
607 /// Set up candidate assertions for inference
608 void inferParameters( CandidateRef & newCand, CandidateList & out );
609
610 /// Completes a function candidate with arguments located
611 void validateFunctionCandidate(
612 const CandidateRef & func, ArgPack & result, const std::vector< ArgPack > & results,
613 CandidateList & out );
614
615 /// Builds a list of candidates for a function, storing them in out
616 void makeFunctionCandidates(
617 const CodeLocation & location,
618 const CandidateRef & func, const ast::FunctionType * funcType,
619 const ExplodedArgs_new & args, CandidateList & out );
620
621 /// Adds implicit struct-conversions to the alternative list
622 void addAnonConversions( const CandidateRef & cand );
623
624 /// Adds aggregate member interpretations
625 void addAggMembers(
626 const ast::BaseInstType * aggrInst, const ast::Expr * expr,
627 const Candidate & cand, const Cost & addedCost, const std::string & name
628 );
629
630 /// Adds tuple member interpretations
631 void addTupleMembers(
632 const ast::TupleType * tupleType, const ast::Expr * expr, const Candidate & cand,
633 const Cost & addedCost, const ast::Expr * member
634 );
635
636 /// true if expression is an lvalue
637 static bool isLvalue( const ast::Expr * x ) {
638 return x->result && ( x->get_lvalue() || x->result.as< ast::ReferenceType >() );
639 }
640
641 void postvisit( const ast::UntypedExpr * untypedExpr );
642 void postvisit( const ast::VariableExpr * variableExpr );
643 void postvisit( const ast::ConstantExpr * constantExpr );
644 void postvisit( const ast::SizeofExpr * sizeofExpr );
645 void postvisit( const ast::AlignofExpr * alignofExpr );
646 void postvisit( const ast::AddressExpr * addressExpr );
647 void postvisit( const ast::LabelAddressExpr * labelExpr );
648 void postvisit( const ast::CastExpr * castExpr );
649 void postvisit( const ast::VirtualCastExpr * castExpr );
650 void postvisit( const ast::KeywordCastExpr * castExpr );
651 void postvisit( const ast::UntypedMemberExpr * memberExpr );
652 void postvisit( const ast::MemberExpr * memberExpr );
653 void postvisit( const ast::NameExpr * nameExpr );
654 void postvisit( const ast::UntypedOffsetofExpr * offsetofExpr );
655 void postvisit( const ast::OffsetofExpr * offsetofExpr );
656 void postvisit( const ast::OffsetPackExpr * offsetPackExpr );
657 void postvisit( const ast::LogicalExpr * logicalExpr );
658 void postvisit( const ast::ConditionalExpr * conditionalExpr );
659 void postvisit( const ast::CommaExpr * commaExpr );
660 void postvisit( const ast::ImplicitCopyCtorExpr * ctorExpr );
661 void postvisit( const ast::ConstructorExpr * ctorExpr );
662 void postvisit( const ast::RangeExpr * rangeExpr );
663 void postvisit( const ast::UntypedTupleExpr * tupleExpr );
664 void postvisit( const ast::TupleExpr * tupleExpr );
665 void postvisit( const ast::TupleIndexExpr * tupleExpr );
666 void postvisit( const ast::TupleAssignExpr * tupleExpr );
667 void postvisit( const ast::UniqueExpr * unqExpr );
668 void postvisit( const ast::StmtExpr * stmtExpr );
669 void postvisit( const ast::UntypedInitExpr * initExpr );
670
671 void postvisit( const ast::InitExpr * ) {
672 assertf( false, "CandidateFinder should never see a resolved InitExpr." );
673 }
674
675 void postvisit( const ast::DeletedExpr * ) {
676 assertf( false, "CandidateFinder should never see a DeletedExpr." );
677 }
678
679 void postvisit( const ast::GenericExpr * ) {
680 assertf( false, "_Generic is not yet supported." );
681 }
682 };
683
684 /// Set up candidate assertions for inference
685 void Finder::inferParameters( CandidateRef & newCand, CandidateList & out ) {
686 // Set need bindings for any unbound assertions
687 UniqueId crntResnSlot = 0; // matching ID for this expression's assertions
688 for ( auto & assn : newCand->need ) {
689 // skip already-matched assertions
690 if ( assn.second.resnSlot != 0 ) continue;
691 // assign slot for expression if needed
692 if ( crntResnSlot == 0 ) { crntResnSlot = ++globalResnSlot; }
693 // fix slot to assertion
694 assn.second.resnSlot = crntResnSlot;
695 }
696 // pair slot to expression
697 if ( crntResnSlot != 0 ) {
698 newCand->expr.get_and_mutate()->inferred.resnSlots().emplace_back( crntResnSlot );
699 }
700
701 // add to output list; assertion satisfaction will occur later
702 out.emplace_back( newCand );
703 }
704
705 /// Completes a function candidate with arguments located
706 void Finder::validateFunctionCandidate(
707 const CandidateRef & func, ArgPack & result, const std::vector< ArgPack > & results,
708 CandidateList & out
709 ) {
710 ast::ApplicationExpr * appExpr =
711 new ast::ApplicationExpr{ func->expr->location, func->expr };
712 // sum cost and accumulate arguments
713 std::deque< const ast::Expr * > args;
714 Cost cost = func->cost;
715 const ArgPack * pack = &result;
716 while ( pack->expr ) {
717 args.emplace_front( pack->expr );
718 cost += pack->cost;
719 pack = &results[pack->parent];
720 }
721 std::vector< ast::ptr< ast::Expr > > vargs( args.begin(), args.end() );
722 appExpr->args = std::move( vargs );
723 // build and validate new candidate
724 auto newCand =
725 std::make_shared<Candidate>( appExpr, result.env, result.open, result.need, cost );
726 PRINT(
727 std::cerr << "instantiate function success: " << appExpr << std::endl;
728 std::cerr << "need assertions:" << std::endl;
729 ast::print( std::cerr, result.need, 2 );
730 )
731 inferParameters( newCand, out );
732 }
733
734 /// Builds a list of candidates for a function, storing them in out
735 void Finder::makeFunctionCandidates(
736 const CodeLocation & location,
737 const CandidateRef & func, const ast::FunctionType * funcType,
738 const ExplodedArgs_new & args, CandidateList & out
739 ) {
740 ast::OpenVarSet funcOpen;
741 ast::AssertionSet funcNeed, funcHave;
742 ast::TypeEnvironment funcEnv{ func->env };
743 makeUnifiableVars( funcType, funcOpen, funcNeed );
744 // add all type variables as open variables now so that those not used in the
745 // parameter list are still considered open
746 funcEnv.add( funcType->forall );
747
748 if ( targetType && ! targetType->isVoid() && ! funcType->returns.empty() ) {
749 // attempt to narrow based on expected target type
750 const ast::Type * returnType = funcType->returns.front();
751 if ( ! unify(
752 returnType, targetType, funcEnv, funcNeed, funcHave, funcOpen, symtab )
753 ) {
754 // unification failed, do not pursue this candidate
755 return;
756 }
757 }
758
759 // iteratively build matches, one parameter at a time
760 std::vector< ArgPack > results;
761 results.emplace_back( funcEnv, funcNeed, funcHave, funcOpen );
762 std::size_t genStart = 0;
763
764 // xxx - how to handle default arg after change to ftype representation?
765 if (const ast::VariableExpr * varExpr = func->expr.as<ast::VariableExpr>()) {
766 if (const ast::FunctionDecl * funcDecl = varExpr->var.as<ast::FunctionDecl>()) {
767 // function may have default args only if directly calling by name
768 // must use types on candidate however, due to RenameVars substitution
769 auto nParams = funcType->params.size();
770
771 for (size_t i=0; i<nParams; ++i) {
772 auto obj = funcDecl->params[i].strict_as<ast::ObjectDecl>();
773 if (!instantiateArgument( location,
774 funcType->params[i], obj->init, args, results, genStart, symtab)) return;
775 }
776 goto endMatch;
777 }
778 }
779 for ( const auto & param : funcType->params ) {
780 // Try adding the arguments corresponding to the current parameter to the existing
781 // matches
782 // no default args for indirect calls
783 if ( ! instantiateArgument( location,
784 param, nullptr, args, results, genStart, symtab ) ) return;
785 }
786
787 endMatch:
788 if ( funcType->isVarArgs ) {
789 // append any unused arguments to vararg pack
790 std::size_t genEnd;
791 do {
792 genEnd = results.size();
793
794 // iterate results
795 for ( std::size_t i = genStart; i < genEnd; ++i ) {
796 unsigned nextArg = results[i].nextArg;
797
798 // use remainder of exploded tuple if present
799 if ( results[i].hasExpl() ) {
800 const ExplodedArg & expl = results[i].getExpl( args );
801
802 unsigned nextExpl = results[i].nextExpl + 1;
803 if ( nextExpl == expl.exprs.size() ) { nextExpl = 0; }
804
805 results.emplace_back(
806 i, expl.exprs[ results[i].nextExpl ], copy( results[i].env ),
807 copy( results[i].need ), copy( results[i].have ),
808 copy( results[i].open ), nextArg, 0, Cost::zero, nextExpl,
809 results[i].explAlt );
810
811 continue;
812 }
813
814 // finish result when out of arguments
815 if ( nextArg >= args.size() ) {
816 validateFunctionCandidate( func, results[i], results, out );
817
818 continue;
819 }
820
821 // add each possible next argument
822 for ( std::size_t j = 0; j < args[nextArg].size(); ++j ) {
823 const ExplodedArg & expl = args[nextArg][j];
824
825 // fresh copies of parent parameters for this iteration
826 ast::TypeEnvironment env = results[i].env;
827 ast::OpenVarSet open = results[i].open;
828
829 env.addActual( expl.env, open );
830
831 // skip empty tuple arguments by (nearly) cloning parent into next gen
832 if ( expl.exprs.empty() ) {
833 results.emplace_back(
834 results[i], std::move( env ), copy( results[i].need ),
835 copy( results[i].have ), std::move( open ), nextArg + 1,
836 expl.cost );
837
838 continue;
839 }
840
841 // add new result
842 results.emplace_back(
843 i, expl.exprs.front(), std::move( env ), copy( results[i].need ),
844 copy( results[i].have ), std::move( open ), nextArg + 1, 0, expl.cost,
845 expl.exprs.size() == 1 ? 0 : 1, j );
846 }
847 }
848
849 genStart = genEnd;
850 } while( genEnd != results.size() );
851 } else {
852 // filter out the results that don't use all the arguments
853 for ( std::size_t i = genStart; i < results.size(); ++i ) {
854 ArgPack & result = results[i];
855 if ( ! result.hasExpl() && result.nextArg >= args.size() ) {
856 validateFunctionCandidate( func, result, results, out );
857 }
858 }
859 }
860 }
861
862 /// Adds implicit struct-conversions to the alternative list
863 void Finder::addAnonConversions( const CandidateRef & cand ) {
864 // adds anonymous member interpretations whenever an aggregate value type is seen.
865 // it's okay for the aggregate expression to have reference type -- cast it to the
866 // base type to treat the aggregate as the referenced value
867 ast::ptr< ast::Expr > aggrExpr( cand->expr );
868 ast::ptr< ast::Type > & aggrType = aggrExpr.get_and_mutate()->result;
869 cand->env.apply( aggrType );
870
871 if ( aggrType.as< ast::ReferenceType >() ) {
872 aggrExpr = new ast::CastExpr{ aggrExpr, aggrType->stripReferences() };
873 }
874
875 if ( auto structInst = aggrExpr->result.as< ast::StructInstType >() ) {
876 addAggMembers( structInst, aggrExpr, *cand, Cost::safe, "" );
877 } else if ( auto unionInst = aggrExpr->result.as< ast::UnionInstType >() ) {
878 addAggMembers( unionInst, aggrExpr, *cand, Cost::safe, "" );
879 }
880 }
881
882 /// Adds aggregate member interpretations
883 void Finder::addAggMembers(
884 const ast::BaseInstType * aggrInst, const ast::Expr * expr,
885 const Candidate & cand, const Cost & addedCost, const std::string & name
886 ) {
887 for ( const ast::Decl * decl : aggrInst->lookup( name ) ) {
888 auto dwt = strict_dynamic_cast< const ast::DeclWithType * >( decl );
889 CandidateRef newCand = std::make_shared<Candidate>(
890 cand, new ast::MemberExpr{ expr->location, dwt, expr }, addedCost );
891 // add anonymous member interpretations whenever an aggregate value type is seen
892 // as a member expression
893 addAnonConversions( newCand );
894 candidates.emplace_back( std::move( newCand ) );
895 }
896 }
897
898 /// Adds tuple member interpretations
899 void Finder::addTupleMembers(
900 const ast::TupleType * tupleType, const ast::Expr * expr, const Candidate & cand,
901 const Cost & addedCost, const ast::Expr * member
902 ) {
903 if ( auto constantExpr = dynamic_cast< const ast::ConstantExpr * >( member ) ) {
904 // get the value of the constant expression as an int, must be between 0 and the
905 // length of the tuple to have meaning
906 long long val = constantExpr->intValue();
907 if ( val >= 0 && (unsigned long long)val < tupleType->size() ) {
908 addCandidate(
909 cand, new ast::TupleIndexExpr{ expr->location, expr, (unsigned)val },
910 addedCost );
911 }
912 }
913 }
914
915 void Finder::postvisit( const ast::UntypedExpr * untypedExpr ) {
916 std::vector< CandidateFinder > argCandidates =
917 selfFinder.findSubExprs( untypedExpr->args );
918
919 // take care of possible tuple assignments
920 // if not tuple assignment, handled as normal function call
921 Tuples::handleTupleAssignment( selfFinder, untypedExpr, argCandidates );
922
923 CandidateFinder funcFinder( context, tenv );
924 if (auto nameExpr = untypedExpr->func.as<ast::NameExpr>()) {
925 auto kind = ast::SymbolTable::getSpecialFunctionKind(nameExpr->name);
926 if (kind != ast::SymbolTable::SpecialFunctionKind::NUMBER_OF_KINDS) {
927 assertf(!argCandidates.empty(), "special function call without argument");
928 for (auto & firstArgCand: argCandidates[0]) {
929 ast::ptr<ast::Type> argType = firstArgCand->expr->result;
930 firstArgCand->env.apply(argType);
931 // strip references
932 // xxx - is this correct?
933 while (argType.as<ast::ReferenceType>()) argType = argType.as<ast::ReferenceType>()->base;
934
935 // convert 1-tuple to plain type
936 if (auto tuple = argType.as<ast::TupleType>()) {
937 if (tuple->size() == 1) {
938 argType = tuple->types[0];
939 }
940 }
941
942 // if argType is an unbound type parameter, all special functions need to be searched.
943 if (isUnboundType(argType)) {
944 funcFinder.otypeKeys.clear();
945 break;
946 }
947
948 if (argType.as<ast::PointerType>()) funcFinder.otypeKeys.insert(Mangle::Encoding::pointer);
949 // else if (const ast::EnumInstType * enumInst = argType.as<ast::EnumInstType>()) {
950 // const ast::EnumDecl * enumDecl = enumInst->base; // Here
951 // if ( const ast::Type* enumType = enumDecl->base ) {
952 // // instance of enum (T) is a instance of type (T)
953 // funcFinder.otypeKeys.insert(Mangle::mangle(enumType, Mangle::NoGenericParams | Mangle::Type));
954 // } else {
955 // // instance of an untyped enum is techically int
956 // funcFinder.otypeKeys.insert(Mangle::mangle(enumDecl, Mangle::NoGenericParams | Mangle::Type));
957 // }
958 // }
959 else funcFinder.otypeKeys.insert(Mangle::mangle(argType, Mangle::NoGenericParams | Mangle::Type));
960 }
961 }
962 }
963 // if candidates are already produced, do not fail
964 // xxx - is it possible that handleTupleAssignment and main finder both produce candidates?
965 // this means there exists ctor/assign functions with a tuple as first parameter.
966 ResolvMode mode = {
967 true, // adjust
968 !untypedExpr->func.as<ast::NameExpr>(), // prune if not calling by name
969 selfFinder.candidates.empty() // failfast if other options are not found
970 };
971 funcFinder.find( untypedExpr->func, mode );
972 // short-circuit if no candidates
973 // if ( funcFinder.candidates.empty() ) return;
974
975 reason.code = NoMatch;
976
977 // find function operators
978 ast::ptr< ast::Expr > opExpr = new ast::NameExpr{ untypedExpr->location, "?()" }; // ??? why not ?{}
979 CandidateFinder opFinder( context, tenv );
980 // okay if there aren't any function operations
981 opFinder.find( opExpr, ResolvMode::withoutFailFast() );
982 PRINT(
983 std::cerr << "known function ops:" << std::endl;
984 print( std::cerr, opFinder.candidates, 1 );
985 )
986
987 // pre-explode arguments
988 ExplodedArgs_new argExpansions;
989 for ( const CandidateFinder & args : argCandidates ) {
990 argExpansions.emplace_back();
991 auto & argE = argExpansions.back();
992 for ( const CandidateRef & arg : args ) { argE.emplace_back( *arg, symtab ); }
993 }
994
995 // Find function matches
996 CandidateList found;
997 SemanticErrorException errors;
998 for ( CandidateRef & func : funcFinder ) {
999 try {
1000 PRINT(
1001 std::cerr << "working on alternative:" << std::endl;
1002 print( std::cerr, *func, 2 );
1003 )
1004
1005 // check if the type is a pointer to function
1006 const ast::Type * funcResult = func->expr->result->stripReferences();
1007 if ( auto pointer = dynamic_cast< const ast::PointerType * >( funcResult ) ) {
1008 if ( auto function = pointer->base.as< ast::FunctionType >() ) {
1009 CandidateRef newFunc{ new Candidate{ *func } };
1010 newFunc->expr =
1011 referenceToRvalueConversion( newFunc->expr, newFunc->cost );
1012 makeFunctionCandidates( untypedExpr->location,
1013 newFunc, function, argExpansions, found );
1014 }
1015 } else if (
1016 auto inst = dynamic_cast< const ast::TypeInstType * >( funcResult )
1017 ) {
1018 if ( const ast::EqvClass * clz = func->env.lookup( *inst ) ) {
1019 if ( auto function = clz->bound.as< ast::FunctionType >() ) {
1020 CandidateRef newFunc{ new Candidate{ *func } };
1021 newFunc->expr =
1022 referenceToRvalueConversion( newFunc->expr, newFunc->cost );
1023 makeFunctionCandidates( untypedExpr->location,
1024 newFunc, function, argExpansions, found );
1025 }
1026 }
1027 }
1028 } catch ( SemanticErrorException & e ) { errors.append( e ); }
1029 }
1030
1031 // Find matches on function operators `?()`
1032 if ( ! opFinder.candidates.empty() ) {
1033 // add exploded function alternatives to front of argument list
1034 std::vector< ExplodedArg > funcE;
1035 funcE.reserve( funcFinder.candidates.size() );
1036 for ( const CandidateRef & func : funcFinder ) {
1037 funcE.emplace_back( *func, symtab );
1038 }
1039 argExpansions.emplace_front( std::move( funcE ) );
1040
1041 for ( const CandidateRef & op : opFinder ) {
1042 try {
1043 // check if type is pointer-to-function
1044 const ast::Type * opResult = op->expr->result->stripReferences();
1045 if ( auto pointer = dynamic_cast< const ast::PointerType * >( opResult ) ) {
1046 if ( auto function = pointer->base.as< ast::FunctionType >() ) {
1047 CandidateRef newOp{ new Candidate{ *op} };
1048 newOp->expr =
1049 referenceToRvalueConversion( newOp->expr, newOp->cost );
1050 makeFunctionCandidates( untypedExpr->location,
1051 newOp, function, argExpansions, found );
1052 }
1053 }
1054 } catch ( SemanticErrorException & e ) { errors.append( e ); }
1055 }
1056 }
1057
1058 // Implement SFINAE; resolution errors are only errors if there aren't any non-error
1059 // candidates
1060 if ( found.empty() && ! errors.isEmpty() ) { throw errors; }
1061
1062 // Compute conversion costs
1063 for ( CandidateRef & withFunc : found ) {
1064 Cost cvtCost = computeApplicationConversionCost( withFunc, symtab );
1065
1066 PRINT(
1067 auto appExpr = withFunc->expr.strict_as< ast::ApplicationExpr >();
1068 auto pointer = appExpr->func->result.strict_as< ast::PointerType >();
1069 auto function = pointer->base.strict_as< ast::FunctionType >();
1070
1071 std::cerr << "Case +++++++++++++ " << appExpr->func << std::endl;
1072 std::cerr << "parameters are:" << std::endl;
1073 ast::printAll( std::cerr, function->params, 2 );
1074 std::cerr << "arguments are:" << std::endl;
1075 ast::printAll( std::cerr, appExpr->args, 2 );
1076 std::cerr << "bindings are:" << std::endl;
1077 ast::print( std::cerr, withFunc->env, 2 );
1078 std::cerr << "cost is: " << withFunc->cost << std::endl;
1079 std::cerr << "cost of conversion is:" << cvtCost << std::endl;
1080 )
1081
1082 if ( cvtCost != Cost::infinity ) {
1083 withFunc->cvtCost = cvtCost;
1084 candidates.emplace_back( std::move( withFunc ) );
1085 }
1086 }
1087 found = std::move( candidates );
1088
1089 // use a new list so that candidates are not examined by addAnonConversions twice
1090 CandidateList winners = findMinCost( found );
1091 promoteCvtCost( winners );
1092
1093 // function may return a struct/union value, in which case we need to add candidates
1094 // for implicit conversions to each of the anonymous members, which must happen after
1095 // `findMinCost`, since anon conversions are never the cheapest
1096 for ( const CandidateRef & c : winners ) {
1097 addAnonConversions( c );
1098 }
1099 spliceBegin( candidates, winners );
1100
1101 if ( candidates.empty() && targetType && ! targetType->isVoid() ) {
1102 // If resolution is unsuccessful with a target type, try again without, since it
1103 // will sometimes succeed when it wouldn't with a target type binding.
1104 // For example:
1105 // forall( otype T ) T & ?[]( T *, ptrdiff_t );
1106 // const char * x = "hello world";
1107 // unsigned char ch = x[0];
1108 // Fails with simple return type binding (xxx -- check this!) as follows:
1109 // * T is bound to unsigned char
1110 // * (x: const char *) is unified with unsigned char *, which fails
1111 // xxx -- fix this better
1112 targetType = nullptr;
1113 postvisit( untypedExpr );
1114 }
1115 }
1116
1117 void Finder::postvisit( const ast::AddressExpr * addressExpr ) {
1118 CandidateFinder finder( context, tenv );
1119 finder.find( addressExpr->arg );
1120
1121 if ( finder.candidates.empty() ) return;
1122
1123 reason.code = NoMatch;
1124
1125 for ( CandidateRef & r : finder.candidates ) {
1126 if ( ! isLvalue( r->expr ) ) continue;
1127 addCandidate( *r, new ast::AddressExpr{ addressExpr->location, r->expr } );
1128 }
1129 }
1130
1131 void Finder::postvisit( const ast::LabelAddressExpr * labelExpr ) {
1132 addCandidate( labelExpr, tenv );
1133 }
1134
1135 void Finder::postvisit( const ast::CastExpr * castExpr ) {
1136 ast::ptr< ast::Type > toType = castExpr->result;
1137 assert( toType );
1138 toType = resolveTypeof( toType, context );
1139 toType = adjustExprType( toType, tenv, symtab );
1140
1141 CandidateFinder finder( context, tenv, toType );
1142 finder.find( castExpr->arg, ResolvMode::withAdjustment() );
1143
1144 if ( !finder.candidates.empty() ) reason.code = NoMatch;
1145
1146 CandidateList matches;
1147 for ( CandidateRef & cand : finder.candidates ) {
1148 ast::AssertionSet need( cand->need.begin(), cand->need.end() ), have;
1149 ast::OpenVarSet open( cand->open );
1150
1151 cand->env.extractOpenVars( open );
1152
1153 // It is possible that a cast can throw away some values in a multiply-valued
1154 // expression, e.g. cast-to-void, one value to zero. Figure out the prefix of the
1155 // subexpression results that are cast directly. The candidate is invalid if it
1156 // has fewer results than there are types to cast to.
1157 int discardedValues = cand->expr->result->size() - toType->size();
1158 if ( discardedValues < 0 ) continue;
1159
1160 // unification run for side-effects
1161 unify( toType, cand->expr->result, cand->env, need, have, open, symtab );
1162 Cost thisCost =
1163 (castExpr->isGenerated == ast::GeneratedFlag::GeneratedCast)
1164 ? conversionCost( cand->expr->result, toType, cand->expr->get_lvalue(), symtab, cand->env )
1165 : castCost( cand->expr->result, toType, cand->expr->get_lvalue(), symtab, cand->env );
1166
1167 PRINT(
1168 std::cerr << "working on cast with result: " << toType << std::endl;
1169 std::cerr << "and expr type: " << cand->expr->result << std::endl;
1170 std::cerr << "env: " << cand->env << std::endl;
1171 )
1172 if ( thisCost != Cost::infinity ) {
1173 PRINT(
1174 std::cerr << "has finite cost." << std::endl;
1175 )
1176 // count one safe conversion for each value that is thrown away
1177 thisCost.incSafe( discardedValues );
1178 CandidateRef newCand = std::make_shared<Candidate>(
1179 restructureCast( cand->expr, toType, castExpr->isGenerated ),
1180 copy( cand->env ), std::move( open ), std::move( need ), cand->cost,
1181 cand->cost + thisCost );
1182 inferParameters( newCand, matches );
1183 }
1184 }
1185
1186 // select first on argument cost, then conversion cost
1187 CandidateList minArgCost = findMinCost( matches );
1188 promoteCvtCost( minArgCost );
1189 candidates = findMinCost( minArgCost );
1190 }
1191
1192 void Finder::postvisit( const ast::VirtualCastExpr * castExpr ) {
1193 assertf( castExpr->result, "Implicit virtual cast targets not yet supported." );
1194 CandidateFinder finder( context, tenv );
1195 // don't prune here, all alternatives guaranteed to have same type
1196 finder.find( castExpr->arg, ResolvMode::withoutPrune() );
1197 for ( CandidateRef & r : finder.candidates ) {
1198 addCandidate(
1199 *r,
1200 new ast::VirtualCastExpr{ castExpr->location, r->expr, castExpr->result } );
1201 }
1202 }
1203
1204 void Finder::postvisit( const ast::KeywordCastExpr * castExpr ) {
1205 const auto & loc = castExpr->location;
1206 assertf( castExpr->result, "Cast target should have been set in Validate." );
1207 auto ref = castExpr->result.strict_as<ast::ReferenceType>();
1208 auto inst = ref->base.strict_as<ast::StructInstType>();
1209 auto target = inst->base.get();
1210
1211 CandidateFinder finder( context, tenv );
1212
1213 auto pick_alternatives = [target, this](CandidateList & found, bool expect_ref) {
1214 for (auto & cand : found) {
1215 const ast::Type * expr = cand->expr->result.get();
1216 if (expect_ref) {
1217 auto res = dynamic_cast<const ast::ReferenceType*>(expr);
1218 if (!res) { continue; }
1219 expr = res->base.get();
1220 }
1221
1222 if (auto insttype = dynamic_cast<const ast::TypeInstType*>(expr)) {
1223 auto td = cand->env.lookup(*insttype);
1224 if (!td) { continue; }
1225 expr = td->bound.get();
1226 }
1227
1228 if (auto base = dynamic_cast<const ast::StructInstType*>(expr)) {
1229 if (base->base == target) {
1230 candidates.push_back( std::move(cand) );
1231 reason.code = NoReason;
1232 }
1233 }
1234 }
1235 };
1236
1237 try {
1238 // Attempt 1 : turn (thread&)X into (thread$&)X.__thrd
1239 // Clone is purely for memory management
1240 std::unique_ptr<const ast::Expr> tech1 { new ast::UntypedMemberExpr(loc, new ast::NameExpr(loc, castExpr->concrete_target.field), castExpr->arg) };
1241
1242 // don't prune here, since it's guaranteed all alternatives will have the same type
1243 finder.find( tech1.get(), ResolvMode::withoutPrune() );
1244 pick_alternatives(finder.candidates, false);
1245
1246 return;
1247 } catch(SemanticErrorException & ) {}
1248
1249 // Fallback : turn (thread&)X into (thread$&)get_thread(X)
1250 std::unique_ptr<const ast::Expr> fallback { ast::UntypedExpr::createDeref(loc, new ast::UntypedExpr(loc, new ast::NameExpr(loc, castExpr->concrete_target.getter), { castExpr->arg })) };
1251 // don't prune here, since it's guaranteed all alternatives will have the same type
1252 finder.find( fallback.get(), ResolvMode::withoutPrune() );
1253
1254 pick_alternatives(finder.candidates, true);
1255
1256 // Whatever happens here, we have no more fallbacks
1257 }
1258
1259 void Finder::postvisit( const ast::UntypedMemberExpr * memberExpr ) {
1260 CandidateFinder aggFinder( context, tenv );
1261 aggFinder.find( memberExpr->aggregate, ResolvMode::withAdjustment() );
1262 for ( CandidateRef & agg : aggFinder.candidates ) {
1263 // it's okay for the aggregate expression to have reference type -- cast it to the
1264 // base type to treat the aggregate as the referenced value
1265 Cost addedCost = Cost::zero;
1266 agg->expr = referenceToRvalueConversion( agg->expr, addedCost );
1267
1268 // find member of the given type
1269 if ( auto structInst = agg->expr->result.as< ast::StructInstType >() ) {
1270 addAggMembers(
1271 structInst, agg->expr, *agg, addedCost, getMemberName( memberExpr ) );
1272 } else if ( auto unionInst = agg->expr->result.as< ast::UnionInstType >() ) {
1273 addAggMembers(
1274 unionInst, agg->expr, *agg, addedCost, getMemberName( memberExpr ) );
1275 } else if ( auto tupleType = agg->expr->result.as< ast::TupleType >() ) {
1276 addTupleMembers( tupleType, agg->expr, *agg, addedCost, memberExpr->member );
1277 }
1278 }
1279 }
1280
1281 void Finder::postvisit( const ast::MemberExpr * memberExpr ) {
1282 addCandidate( memberExpr, tenv );
1283 }
1284
1285 void Finder::postvisit( const ast::NameExpr * nameExpr ) {
1286 std::vector< ast::SymbolTable::IdData > declList;
1287 if (!selfFinder.otypeKeys.empty()) {
1288 auto kind = ast::SymbolTable::getSpecialFunctionKind(nameExpr->name);
1289 assertf(kind != ast::SymbolTable::SpecialFunctionKind::NUMBER_OF_KINDS, "special lookup with non-special target: %s", nameExpr->name.c_str());
1290
1291 for (auto & otypeKey: selfFinder.otypeKeys) {
1292 auto result = symtab.specialLookupId(kind, otypeKey);
1293 declList.insert(declList.end(), std::make_move_iterator(result.begin()), std::make_move_iterator(result.end()));
1294 }
1295 } else {
1296 declList = symtab.lookupId( nameExpr->name );
1297 }
1298 PRINT( std::cerr << "nameExpr is " << nameExpr->name << std::endl; )
1299
1300 if ( declList.empty() ) return;
1301
1302 reason.code = NoMatch;
1303
1304 for ( auto & data : declList ) {
1305 Cost cost = Cost::zero;
1306 ast::Expr * newExpr = data.combine( nameExpr->location, cost );
1307
1308 CandidateRef newCand = std::make_shared<Candidate>(
1309 newExpr, copy( tenv ), ast::OpenVarSet{}, ast::AssertionSet{}, Cost::zero,
1310 cost );
1311
1312 if (newCand->expr->env) {
1313 newCand->env.add(*newCand->expr->env);
1314 auto mutExpr = newCand->expr.get_and_mutate();
1315 mutExpr->env = nullptr;
1316 newCand->expr = mutExpr;
1317 }
1318
1319 PRINT(
1320 std::cerr << "decl is ";
1321 ast::print( std::cerr, data.id );
1322 std::cerr << std::endl;
1323 std::cerr << "newExpr is ";
1324 ast::print( std::cerr, newExpr );
1325 std::cerr << std::endl;
1326 )
1327 newCand->expr = ast::mutate_field(
1328 newCand->expr.get(), &ast::Expr::result,
1329 renameTyVars( newCand->expr->result ) );
1330 // add anonymous member interpretations whenever an aggregate value type is seen
1331 // as a name expression
1332 addAnonConversions( newCand );
1333 candidates.emplace_back( std::move( newCand ) );
1334 }
1335 }
1336
1337 void Finder::postvisit( const ast::VariableExpr * variableExpr ) {
1338 // not sufficient to just pass `variableExpr` here, type might have changed since
1339 // creation
1340 addCandidate(
1341 new ast::VariableExpr{ variableExpr->location, variableExpr->var }, tenv );
1342 }
1343
1344 void Finder::postvisit( const ast::ConstantExpr * constantExpr ) {
1345 addCandidate( constantExpr, tenv );
1346 }
1347
1348 void Finder::postvisit( const ast::SizeofExpr * sizeofExpr ) {
1349 if ( sizeofExpr->type ) {
1350 addCandidate(
1351 new ast::SizeofExpr{
1352 sizeofExpr->location, resolveTypeof( sizeofExpr->type, context ) },
1353 tenv );
1354 } else {
1355 // find all candidates for the argument to sizeof
1356 CandidateFinder finder( context, tenv );
1357 finder.find( sizeofExpr->expr );
1358 // find the lowest-cost candidate, otherwise ambiguous
1359 CandidateList winners = findMinCost( finder.candidates );
1360 if ( winners.size() != 1 ) {
1361 SemanticError(
1362 sizeofExpr->expr.get(), "Ambiguous expression in sizeof operand: " );
1363 }
1364 // return the lowest-cost candidate
1365 CandidateRef & choice = winners.front();
1366 choice->expr = referenceToRvalueConversion( choice->expr, choice->cost );
1367 choice->cost = Cost::zero;
1368 addCandidate( *choice, new ast::SizeofExpr{ sizeofExpr->location, choice->expr } );
1369 }
1370 }
1371
1372 void Finder::postvisit( const ast::AlignofExpr * alignofExpr ) {
1373 if ( alignofExpr->type ) {
1374 addCandidate(
1375 new ast::AlignofExpr{
1376 alignofExpr->location, resolveTypeof( alignofExpr->type, context ) },
1377 tenv );
1378 } else {
1379 // find all candidates for the argument to alignof
1380 CandidateFinder finder( context, tenv );
1381 finder.find( alignofExpr->expr );
1382 // find the lowest-cost candidate, otherwise ambiguous
1383 CandidateList winners = findMinCost( finder.candidates );
1384 if ( winners.size() != 1 ) {
1385 SemanticError(
1386 alignofExpr->expr.get(), "Ambiguous expression in alignof operand: " );
1387 }
1388 // return the lowest-cost candidate
1389 CandidateRef & choice = winners.front();
1390 choice->expr = referenceToRvalueConversion( choice->expr, choice->cost );
1391 choice->cost = Cost::zero;
1392 addCandidate(
1393 *choice, new ast::AlignofExpr{ alignofExpr->location, choice->expr } );
1394 }
1395 }
1396
1397 void Finder::postvisit( const ast::UntypedOffsetofExpr * offsetofExpr ) {
1398 const ast::BaseInstType * aggInst;
1399 if (( aggInst = offsetofExpr->type.as< ast::StructInstType >() )) ;
1400 else if (( aggInst = offsetofExpr->type.as< ast::UnionInstType >() )) ;
1401 else return;
1402
1403 for ( const ast::Decl * member : aggInst->lookup( offsetofExpr->member ) ) {
1404 auto dwt = strict_dynamic_cast< const ast::DeclWithType * >( member );
1405 addCandidate(
1406 new ast::OffsetofExpr{ offsetofExpr->location, aggInst, dwt }, tenv );
1407 }
1408 }
1409
1410 void Finder::postvisit( const ast::OffsetofExpr * offsetofExpr ) {
1411 addCandidate( offsetofExpr, tenv );
1412 }
1413
1414 void Finder::postvisit( const ast::OffsetPackExpr * offsetPackExpr ) {
1415 addCandidate( offsetPackExpr, tenv );
1416 }
1417
1418 void Finder::postvisit( const ast::LogicalExpr * logicalExpr ) {
1419 CandidateFinder finder1( context, tenv );
1420 finder1.find( logicalExpr->arg1, ResolvMode::withAdjustment() );
1421 if ( finder1.candidates.empty() ) return;
1422
1423 CandidateFinder finder2( context, tenv );
1424 finder2.find( logicalExpr->arg2, ResolvMode::withAdjustment() );
1425 if ( finder2.candidates.empty() ) return;
1426
1427 reason.code = NoMatch;
1428
1429 for ( const CandidateRef & r1 : finder1.candidates ) {
1430 for ( const CandidateRef & r2 : finder2.candidates ) {
1431 ast::TypeEnvironment env{ r1->env };
1432 env.simpleCombine( r2->env );
1433 ast::OpenVarSet open{ r1->open };
1434 mergeOpenVars( open, r2->open );
1435 ast::AssertionSet need;
1436 mergeAssertionSet( need, r1->need );
1437 mergeAssertionSet( need, r2->need );
1438
1439 addCandidate(
1440 new ast::LogicalExpr{
1441 logicalExpr->location, r1->expr, r2->expr, logicalExpr->isAnd },
1442 std::move( env ), std::move( open ), std::move( need ), r1->cost + r2->cost );
1443 }
1444 }
1445 }
1446
1447 void Finder::postvisit( const ast::ConditionalExpr * conditionalExpr ) {
1448 // candidates for condition
1449 CandidateFinder finder1( context, tenv );
1450 finder1.find( conditionalExpr->arg1, ResolvMode::withAdjustment() );
1451 if ( finder1.candidates.empty() ) return;
1452
1453 // candidates for true result
1454 CandidateFinder finder2( context, tenv );
1455 finder2.find( conditionalExpr->arg2, ResolvMode::withAdjustment() );
1456 if ( finder2.candidates.empty() ) return;
1457
1458 // candidates for false result
1459 CandidateFinder finder3( context, tenv );
1460 finder3.find( conditionalExpr->arg3, ResolvMode::withAdjustment() );
1461 if ( finder3.candidates.empty() ) return;
1462
1463 reason.code = NoMatch;
1464
1465 for ( const CandidateRef & r1 : finder1.candidates ) {
1466 for ( const CandidateRef & r2 : finder2.candidates ) {
1467 for ( const CandidateRef & r3 : finder3.candidates ) {
1468 ast::TypeEnvironment env{ r1->env };
1469 env.simpleCombine( r2->env );
1470 env.simpleCombine( r3->env );
1471 ast::OpenVarSet open{ r1->open };
1472 mergeOpenVars( open, r2->open );
1473 mergeOpenVars( open, r3->open );
1474 ast::AssertionSet need;
1475 mergeAssertionSet( need, r1->need );
1476 mergeAssertionSet( need, r2->need );
1477 mergeAssertionSet( need, r3->need );
1478 ast::AssertionSet have;
1479
1480 // unify true and false results, then infer parameters to produce new
1481 // candidates
1482 ast::ptr< ast::Type > common;
1483 if (
1484 unify(
1485 r2->expr->result, r3->expr->result, env, need, have, open, symtab,
1486 common )
1487 ) {
1488 // generate typed expression
1489 ast::ConditionalExpr * newExpr = new ast::ConditionalExpr{
1490 conditionalExpr->location, r1->expr, r2->expr, r3->expr };
1491 newExpr->result = common ? common : r2->expr->result;
1492 // convert both options to result type
1493 Cost cost = r1->cost + r2->cost + r3->cost;
1494 newExpr->arg2 = computeExpressionConversionCost(
1495 newExpr->arg2, newExpr->result, symtab, env, cost );
1496 newExpr->arg3 = computeExpressionConversionCost(
1497 newExpr->arg3, newExpr->result, symtab, env, cost );
1498 // output candidate
1499 CandidateRef newCand = std::make_shared<Candidate>(
1500 newExpr, std::move( env ), std::move( open ), std::move( need ), cost );
1501 inferParameters( newCand, candidates );
1502 }
1503 }
1504 }
1505 }
1506 }
1507
1508 void Finder::postvisit( const ast::CommaExpr * commaExpr ) {
1509 ast::TypeEnvironment env{ tenv };
1510 ast::ptr< ast::Expr > arg1 = resolveInVoidContext( commaExpr->arg1, context, env );
1511
1512 CandidateFinder finder2( context, env );
1513 finder2.find( commaExpr->arg2, ResolvMode::withAdjustment() );
1514
1515 for ( const CandidateRef & r2 : finder2.candidates ) {
1516 addCandidate( *r2, new ast::CommaExpr{ commaExpr->location, arg1, r2->expr } );
1517 }
1518 }
1519
1520 void Finder::postvisit( const ast::ImplicitCopyCtorExpr * ctorExpr ) {
1521 addCandidate( ctorExpr, tenv );
1522 }
1523
1524 void Finder::postvisit( const ast::ConstructorExpr * ctorExpr ) {
1525 CandidateFinder finder( context, tenv );
1526 finder.find( ctorExpr->callExpr, ResolvMode::withoutPrune() );
1527 for ( CandidateRef & r : finder.candidates ) {
1528 addCandidate( *r, new ast::ConstructorExpr{ ctorExpr->location, r->expr } );
1529 }
1530 }
1531
1532 void Finder::postvisit( const ast::RangeExpr * rangeExpr ) {
1533 // resolve low and high, accept candidates where low and high types unify
1534 CandidateFinder finder1( context, tenv );
1535 finder1.find( rangeExpr->low, ResolvMode::withAdjustment() );
1536 if ( finder1.candidates.empty() ) return;
1537
1538 CandidateFinder finder2( context, tenv );
1539 finder2.find( rangeExpr->high, ResolvMode::withAdjustment() );
1540 if ( finder2.candidates.empty() ) return;
1541
1542 reason.code = NoMatch;
1543
1544 for ( const CandidateRef & r1 : finder1.candidates ) {
1545 for ( const CandidateRef & r2 : finder2.candidates ) {
1546 ast::TypeEnvironment env{ r1->env };
1547 env.simpleCombine( r2->env );
1548 ast::OpenVarSet open{ r1->open };
1549 mergeOpenVars( open, r2->open );
1550 ast::AssertionSet need;
1551 mergeAssertionSet( need, r1->need );
1552 mergeAssertionSet( need, r2->need );
1553 ast::AssertionSet have;
1554
1555 ast::ptr< ast::Type > common;
1556 if (
1557 unify(
1558 r1->expr->result, r2->expr->result, env, need, have, open, symtab,
1559 common )
1560 ) {
1561 // generate new expression
1562 ast::RangeExpr * newExpr =
1563 new ast::RangeExpr{ rangeExpr->location, r1->expr, r2->expr };
1564 newExpr->result = common ? common : r1->expr->result;
1565 // add candidate
1566 CandidateRef newCand = std::make_shared<Candidate>(
1567 newExpr, std::move( env ), std::move( open ), std::move( need ),
1568 r1->cost + r2->cost );
1569 inferParameters( newCand, candidates );
1570 }
1571 }
1572 }
1573 }
1574
1575 void Finder::postvisit( const ast::UntypedTupleExpr * tupleExpr ) {
1576 std::vector< CandidateFinder > subCandidates =
1577 selfFinder.findSubExprs( tupleExpr->exprs );
1578 std::vector< CandidateList > possibilities;
1579 combos( subCandidates.begin(), subCandidates.end(), back_inserter( possibilities ) );
1580
1581 for ( const CandidateList & subs : possibilities ) {
1582 std::vector< ast::ptr< ast::Expr > > exprs;
1583 exprs.reserve( subs.size() );
1584 for ( const CandidateRef & sub : subs ) { exprs.emplace_back( sub->expr ); }
1585
1586 ast::TypeEnvironment env;
1587 ast::OpenVarSet open;
1588 ast::AssertionSet need;
1589 for ( const CandidateRef & sub : subs ) {
1590 env.simpleCombine( sub->env );
1591 mergeOpenVars( open, sub->open );
1592 mergeAssertionSet( need, sub->need );
1593 }
1594
1595 addCandidate(
1596 new ast::TupleExpr{ tupleExpr->location, std::move( exprs ) },
1597 std::move( env ), std::move( open ), std::move( need ), sumCost( subs ) );
1598 }
1599 }
1600
1601 void Finder::postvisit( const ast::TupleExpr * tupleExpr ) {
1602 addCandidate( tupleExpr, tenv );
1603 }
1604
1605 void Finder::postvisit( const ast::TupleIndexExpr * tupleExpr ) {
1606 addCandidate( tupleExpr, tenv );
1607 }
1608
1609 void Finder::postvisit( const ast::TupleAssignExpr * tupleExpr ) {
1610 addCandidate( tupleExpr, tenv );
1611 }
1612
1613 void Finder::postvisit( const ast::UniqueExpr * unqExpr ) {
1614 CandidateFinder finder( context, tenv );
1615 finder.find( unqExpr->expr, ResolvMode::withAdjustment() );
1616 for ( CandidateRef & r : finder.candidates ) {
1617 // ensure that the the id is passed on so that the expressions are "linked"
1618 addCandidate( *r, new ast::UniqueExpr{ unqExpr->location, r->expr, unqExpr->id } );
1619 }
1620 }
1621
1622 void Finder::postvisit( const ast::StmtExpr * stmtExpr ) {
1623 addCandidate( resolveStmtExpr( stmtExpr, context ), tenv );
1624 }
1625
1626 void Finder::postvisit( const ast::UntypedInitExpr * initExpr ) {
1627 // handle each option like a cast
1628 CandidateList matches;
1629 PRINT(
1630 std::cerr << "untyped init expr: " << initExpr << std::endl;
1631 )
1632 // O(n^2) checks of d-types with e-types
1633 for ( const ast::InitAlternative & initAlt : initExpr->initAlts ) {
1634 // calculate target type
1635 const ast::Type * toType = resolveTypeof( initAlt.type, context );
1636 toType = adjustExprType( toType, tenv, symtab );
1637 // The call to find must occur inside this loop, otherwise polymorphic return
1638 // types are not bound to the initialization type, since return type variables are
1639 // only open for the duration of resolving the UntypedExpr.
1640 CandidateFinder finder( context, tenv, toType );
1641 finder.find( initExpr->expr, ResolvMode::withAdjustment() );
1642 for ( CandidateRef & cand : finder.candidates ) {
1643 if (reason.code == NotFound) reason.code = NoMatch;
1644
1645 ast::TypeEnvironment env{ cand->env };
1646 ast::AssertionSet need( cand->need.begin(), cand->need.end() ), have;
1647 ast::OpenVarSet open{ cand->open };
1648
1649 PRINT(
1650 std::cerr << " @ " << toType << " " << initAlt.designation << std::endl;
1651 )
1652
1653 // It is possible that a cast can throw away some values in a multiply-valued
1654 // expression, e.g. cast-to-void, one value to zero. Figure out the prefix of
1655 // the subexpression results that are cast directly. The candidate is invalid
1656 // if it has fewer results than there are types to cast to.
1657 int discardedValues = cand->expr->result->size() - toType->size();
1658 if ( discardedValues < 0 ) continue;
1659
1660 // unification run for side-effects
1661 bool canUnify = unify( toType, cand->expr->result, env, need, have, open, symtab );
1662 (void) canUnify;
1663 Cost thisCost = computeConversionCost( cand->expr->result, toType, cand->expr->get_lvalue(),
1664 symtab, env );
1665 PRINT(
1666 Cost legacyCost = castCost( cand->expr->result, toType, cand->expr->get_lvalue(),
1667 symtab, env );
1668 std::cerr << "Considering initialization:";
1669 std::cerr << std::endl << " FROM: " << cand->expr->result << std::endl;
1670 std::cerr << std::endl << " TO: " << toType << std::endl;
1671 std::cerr << std::endl << " Unification " << (canUnify ? "succeeded" : "failed");
1672 std::cerr << std::endl << " Legacy cost " << legacyCost;
1673 std::cerr << std::endl << " New cost " << thisCost;
1674 std::cerr << std::endl;
1675 )
1676 if ( thisCost != Cost::infinity ) {
1677 // count one safe conversion for each value that is thrown away
1678 thisCost.incSafe( discardedValues );
1679 CandidateRef newCand = std::make_shared<Candidate>(
1680 new ast::InitExpr{
1681 initExpr->location, restructureCast( cand->expr, toType ),
1682 initAlt.designation },
1683 std::move(env), std::move( open ), std::move( need ), cand->cost, thisCost );
1684 inferParameters( newCand, matches );
1685 }
1686 }
1687 }
1688
1689 // select first on argument cost, then conversion cost
1690 CandidateList minArgCost = findMinCost( matches );
1691 promoteCvtCost( minArgCost );
1692 candidates = findMinCost( minArgCost );
1693 }
1694
1695 // size_t Finder::traceId = Stats::Heap::new_stacktrace_id("Finder");
1696 /// Prunes a list of candidates down to those that have the minimum conversion cost for a given
1697 /// return type. Skips ambiguous candidates.
1698
1699} // anonymous namespace
1700
1701bool CandidateFinder::pruneCandidates( CandidateList & candidates, CandidateList & out, std::vector<std::string> & errors ) {
1702 struct PruneStruct {
1703 CandidateRef candidate;
1704 bool ambiguous;
1705
1706 PruneStruct() = default;
1707 PruneStruct( const CandidateRef & c ) : candidate( c ), ambiguous( false ) {}
1708 };
1709
1710 // find lowest-cost candidate for each type
1711 std::unordered_map< std::string, PruneStruct > selected;
1712 // attempt to skip satisfyAssertions on more expensive alternatives if better options have been found
1713 std::sort(candidates.begin(), candidates.end(), [](const CandidateRef & x, const CandidateRef & y){return x->cost < y->cost;});
1714 for ( CandidateRef & candidate : candidates ) {
1715 std::string mangleName;
1716 {
1717 ast::ptr< ast::Type > newType = candidate->expr->result;
1718 assertf(candidate->expr->result, "Result of expression %p for candidate is null", candidate->expr.get());
1719 candidate->env.apply( newType );
1720 mangleName = Mangle::mangle( newType );
1721 }
1722
1723 auto found = selected.find( mangleName );
1724 if (found != selected.end() && found->second.candidate->cost < candidate->cost) {
1725 PRINT(
1726 std::cerr << "cost " << candidate->cost << " loses to "
1727 << found->second.candidate->cost << std::endl;
1728 )
1729 continue;
1730 }
1731
1732 // xxx - when do satisfyAssertions produce more than 1 result?
1733 // this should only happen when initial result type contains
1734 // unbound type parameters, then it should never be pruned by
1735 // the previous step, since renameTyVars guarantees the mangled name
1736 // is unique.
1737 CandidateList satisfied;
1738 bool needRecomputeKey = false;
1739 if (candidate->need.empty()) {
1740 satisfied.emplace_back(candidate);
1741 }
1742 else {
1743 satisfyAssertions(candidate, context.symtab, satisfied, errors);
1744 needRecomputeKey = true;
1745 }
1746
1747 for (auto & newCand : satisfied) {
1748 // recomputes type key, if satisfyAssertions changed it
1749 if (needRecomputeKey)
1750 {
1751 ast::ptr< ast::Type > newType = newCand->expr->result;
1752 assertf(newCand->expr->result, "Result of expression %p for candidate is null", newCand->expr.get());
1753 newCand->env.apply( newType );
1754 mangleName = Mangle::mangle( newType );
1755 }
1756 auto found = selected.find( mangleName );
1757 if ( found != selected.end() ) {
1758 if ( newCand->cost < found->second.candidate->cost ) {
1759 PRINT(
1760 std::cerr << "cost " << newCand->cost << " beats "
1761 << found->second.candidate->cost << std::endl;
1762 )
1763
1764 found->second = PruneStruct{ newCand };
1765 } else if ( newCand->cost == found->second.candidate->cost ) {
1766 // if one of the candidates contains a deleted identifier, can pick the other,
1767 // since deleted expressions should not be ambiguous if there is another option
1768 // that is at least as good
1769 if ( findDeletedExpr( newCand->expr ) ) {
1770 // do nothing
1771 PRINT( std::cerr << "candidate is deleted" << std::endl; )
1772 } else if ( findDeletedExpr( found->second.candidate->expr ) ) {
1773 PRINT( std::cerr << "current is deleted" << std::endl; )
1774 found->second = PruneStruct{ newCand };
1775 } else {
1776 PRINT( std::cerr << "marking ambiguous" << std::endl; )
1777 found->second.ambiguous = true;
1778 }
1779 } else {
1780 // xxx - can satisfyAssertions increase the cost?
1781 PRINT(
1782 std::cerr << "cost " << newCand->cost << " loses to "
1783 << found->second.candidate->cost << std::endl;
1784 )
1785 }
1786 } else {
1787 selected.emplace_hint( found, mangleName, newCand );
1788 }
1789 }
1790 }
1791
1792 // report unambiguous min-cost candidates
1793 // CandidateList out;
1794 for ( auto & target : selected ) {
1795 if ( target.second.ambiguous ) continue;
1796
1797 CandidateRef cand = target.second.candidate;
1798
1799 ast::ptr< ast::Type > newResult = cand->expr->result;
1800 cand->env.applyFree( newResult );
1801 cand->expr = ast::mutate_field(
1802 cand->expr.get(), &ast::Expr::result, std::move( newResult ) );
1803
1804 out.emplace_back( cand );
1805 }
1806 // if everything is lost in satisfyAssertions, report the error
1807 return !selected.empty();
1808}
1809
1810void CandidateFinder::find( const ast::Expr * expr, ResolvMode mode ) {
1811 // Find alternatives for expression
1812 ast::Pass<Finder> finder{ *this };
1813 expr->accept( finder );
1814
1815 if ( mode.failFast && candidates.empty() ) {
1816 switch(finder.core.reason.code) {
1817 case Finder::NotFound:
1818 { SemanticError( expr, "No alternatives for expression " ); break; }
1819 case Finder::NoMatch:
1820 { SemanticError( expr, "Invalid application of existing declaration(s) in expression " ); break; }
1821 case Finder::ArgsToFew:
1822 case Finder::ArgsToMany:
1823 case Finder::RetsToFew:
1824 case Finder::RetsToMany:
1825 case Finder::NoReason:
1826 default:
1827 { SemanticError( expr->location, "No reasonable alternatives for expression : reasons unkown" ); }
1828 }
1829 }
1830
1831 /*
1832 if ( mode.satisfyAssns || mode.prune ) {
1833 // trim candidates to just those where the assertions are satisfiable
1834 // - necessary pre-requisite to pruning
1835 CandidateList satisfied;
1836 std::vector< std::string > errors;
1837 for ( CandidateRef & candidate : candidates ) {
1838 satisfyAssertions( candidate, localSyms, satisfied, errors );
1839 }
1840
1841 // fail early if none such
1842 if ( mode.failFast && satisfied.empty() ) {
1843 std::ostringstream stream;
1844 stream << "No alternatives with satisfiable assertions for " << expr << "\n";
1845 for ( const auto& err : errors ) {
1846 stream << err;
1847 }
1848 SemanticError( expr->location, stream.str() );
1849 }
1850
1851 // reset candidates
1852 candidates = move( satisfied );
1853 }
1854 */
1855
1856 if ( mode.prune ) {
1857 // trim candidates to single best one
1858 PRINT(
1859 std::cerr << "alternatives before prune:" << std::endl;
1860 print( std::cerr, candidates );
1861 )
1862
1863 CandidateList pruned;
1864 std::vector<std::string> errors;
1865 bool found = pruneCandidates( candidates, pruned, errors );
1866
1867 if ( mode.failFast && pruned.empty() ) {
1868 std::ostringstream stream;
1869 if (found) {
1870 CandidateList winners = findMinCost( candidates );
1871 stream << "Cannot choose between " << winners.size() << " alternatives for "
1872 "expression\n";
1873 ast::print( stream, expr );
1874 stream << " Alternatives are:\n";
1875 print( stream, winners, 1 );
1876 SemanticError( expr->location, stream.str() );
1877 }
1878 else {
1879 stream << "No alternatives with satisfiable assertions for " << expr << "\n";
1880 for ( const auto& err : errors ) {
1881 stream << err;
1882 }
1883 SemanticError( expr->location, stream.str() );
1884 }
1885 }
1886
1887 auto oldsize = candidates.size();
1888 candidates = std::move( pruned );
1889
1890 PRINT(
1891 std::cerr << "there are " << oldsize << " alternatives before elimination" << std::endl;
1892 )
1893 PRINT(
1894 std::cerr << "there are " << candidates.size() << " alternatives after elimination"
1895 << std::endl;
1896 )
1897 }
1898
1899 // adjust types after pruning so that types substituted by pruneAlternatives are correctly
1900 // adjusted
1901 if ( mode.adjust ) {
1902 for ( CandidateRef & r : candidates ) {
1903 r->expr = ast::mutate_field(
1904 r->expr.get(), &ast::Expr::result,
1905 adjustExprType( r->expr->result, r->env, context.symtab ) );
1906 }
1907 }
1908
1909 // Central location to handle gcc extension keyword, etc. for all expressions
1910 for ( CandidateRef & r : candidates ) {
1911 if ( r->expr->extension != expr->extension ) {
1912 r->expr.get_and_mutate()->extension = expr->extension;
1913 }
1914 }
1915}
1916
1917std::vector< CandidateFinder > CandidateFinder::findSubExprs(
1918 const std::vector< ast::ptr< ast::Expr > > & xs
1919) {
1920 std::vector< CandidateFinder > out;
1921
1922 for ( const auto & x : xs ) {
1923 out.emplace_back( context, env );
1924 out.back().find( x, ResolvMode::withAdjustment() );
1925
1926 PRINT(
1927 std::cerr << "findSubExprs" << std::endl;
1928 print( std::cerr, out.back().candidates );
1929 )
1930 }
1931
1932 return out;
1933}
1934
1935const ast::Expr * referenceToRvalueConversion( const ast::Expr * expr, Cost & cost ) {
1936 if ( expr->result.as< ast::ReferenceType >() ) {
1937 // cast away reference from expr
1938 cost.incReference();
1939 return new ast::CastExpr{ expr, expr->result->stripReferences() };
1940 }
1941
1942 return expr;
1943}
1944
1945Cost computeConversionCost(
1946 const ast::Type * argType, const ast::Type * paramType, bool argIsLvalue,
1947 const ast::SymbolTable & symtab, const ast::TypeEnvironment & env
1948) {
1949 PRINT(
1950 std::cerr << std::endl << "converting ";
1951 ast::print( std::cerr, argType, 2 );
1952 std::cerr << std::endl << " to ";
1953 ast::print( std::cerr, paramType, 2 );
1954 std::cerr << std::endl << "environment is: ";
1955 ast::print( std::cerr, env, 2 );
1956 std::cerr << std::endl;
1957 )
1958 Cost convCost = conversionCost( argType, paramType, argIsLvalue, symtab, env );
1959 PRINT(
1960 std::cerr << std::endl << "cost is " << convCost << std::endl;
1961 )
1962 if ( convCost == Cost::infinity ) return convCost;
1963 convCost.incPoly( polyCost( paramType, symtab, env ) + polyCost( argType, symtab, env ) );
1964 PRINT(
1965 std::cerr << "cost with polycost is " << convCost << std::endl;
1966 )
1967 return convCost;
1968}
1969
1970} // namespace ResolvExpr
1971
1972// Local Variables: //
1973// tab-width: 4 //
1974// mode: c++ //
1975// compile-command: "make install" //
1976// End: //
Note: See TracBrowser for help on using the repository browser.