source: src/ResolvExpr/CandidateFinder.cpp@ 898ae07

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

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