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