source: src/ResolvExpr/CandidateFinder.cpp@ 1379c96e

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