Context Navigation

source: src/ResolvExpr/CandidateFinder.cpp @ 4b7cce6

arm-ehenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprpthread-emulationqualifiedEnum

Last change on this file since 4b7cce6 was 4b7cce6, checked in by Aaron Moss <a3moss@…>, 4 years ago
Fill in CandidateFinder? boilerplate in resolver port
Property mode set to `100644`
File size: 17.0 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 <iterator> // for back_inserter
19	#include <sstream>
20	#include <string>
21	#include <unordered_map>
22
23	#include "Candidate.hpp"
24	#include "CompilationState.h"
25	#include "Cost.h"
26	#include "Resolver.h"
27	#include "SatisfyAssertions.hpp"
28	#include "typeops.h" // for adjustExprType
29	#include "Unify.h"
30	#include "AST/Expr.hpp"
31	#include "AST/Node.hpp"
32	#include "AST/Pass.hpp"
33	#include "AST/Print.hpp"
34	#include "AST/SymbolTable.hpp"
35	#include "SymTab/Mangler.h"
36
37	#define PRINT( text ) if ( resolvep ) { text }
38
39	namespace ResolvExpr {
40
41	namespace {
42
43	/// Actually visits expressions to find their candidate interpretations
44	struct Finder final : public ast::WithShortCircuiting {
45	CandidateFinder & selfFinder;
46	const ast::SymbolTable & symtab;
47	CandidateList & candidates;
48	const ast::TypeEnvironment & tenv;
49	ast::ptr< ast::Type > & targetType;
50
51	Finder( CandidateFinder & f )
52	: selfFinder( f ), symtab( f.symtab ), candidates( f.candidates ), tenv( f.env ),
53	targetType( f.targetType ) {}
54
55	void previsit( const ast::Node * ) { visit_children = false; }
56
57	/// Convenience to add candidate to list
58	template<typename... Args>
59	void addCandidate( Args &&... args ) {
60	candidates.emplace_back( new Candidate{ std::forward<Args>( args )... } );
61	}
62
63	void postvisit( const ast::ApplicationExpr * applicationExpr ) {
64	addCandidate( applicationExpr, tenv );
65	}
66
67	void postvisit( const ast::UntypedExpr * untypedExpr ) {
68	#warning unimplemented
69	(void)untypedExpr;
70	assert(false);
71	}
72
73	/// true if expression is an lvalue
74	static bool isLvalue( const ast::Expr * x ) {
75	return x->result && ( x->result->is_lvalue() \|\| x->result.as< ast::ReferenceType >() );
76	}
77
78	void postvisit( const ast::AddressExpr * addressExpr ) {
79	CandidateFinder finder{ symtab, tenv };
80	finder.find( addressExpr->arg );
81	for ( CandidateRef & r : finder.candidates ) {
82	if ( ! isLvalue( r->expr ) ) continue;
83	addCandidate( *r, new ast::AddressExpr{ addressExpr->location, r->expr } );
84	}
85	}
86
87	void postvisit( const ast::LabelAddressExpr * labelExpr ) {
88	addCandidate( labelExpr, tenv );
89	}
90
91	void postvisit( const ast::CastExpr * castExpr ) {
92	#warning unimplemented
93	(void)castExpr;
94	assert(false);
95	}
96
97	void postvisit( const ast::VirtualCastExpr * castExpr ) {
98	assertf( castExpr->result, "Implicit virtual cast targets not yet supported." );
99	CandidateFinder finder{ symtab, tenv };
100	// don't prune here, all alternatives guaranteed to have same type
101	finder.find( castExpr->arg, ResolvMode::withoutPrune() );
102	for ( CandidateRef & r : finder.candidates ) {
103	addCandidate(
104	*r, new ast::VirtualCastExpr{ castExpr->location, r->expr, castExpr->result } );
105	}
106	}
107
108	void postvisit( const ast::UntypedMemberExpr * memberExpr ) {
109	#warning unimplemented
110	(void)memberExpr;
111	assert(false);
112	}
113
114	void postvisit( const ast::MemberExpr * memberExpr ) {
115	addCandidate( memberExpr, tenv );
116	}
117
118	void postvisit( const ast::NameExpr * variableExpr ) {
119	#warning unimplemented
120	(void)variableExpr;
121	assert(false);
122	}
123
124	void postvisit( const ast::VariableExpr * variableExpr ) {
125	// not sufficient to just pass `variableExpr` here, type might have changed since
126	// creation
127	addCandidate(
128	new ast::VariableExpr{ variableExpr->location, variableExpr->var }, tenv );
129	}
130
131	void postvisit( const ast::ConstantExpr * constantExpr ) {
132	addCandidate( constantExpr, tenv );
133	}
134
135	void postvisit( const ast::SizeofExpr * sizeofExpr ) {
136	#warning unimplemented
137	(void)sizeofExpr;
138	assert(false);
139	}
140
141	void postvisit( const ast::AlignofExpr * alignofExpr ) {
142	#warning unimplemented
143	(void)alignofExpr;
144	assert(false);
145	}
146
147	void postvisit( const ast::UntypedOffsetofExpr * offsetofExpr ) {
148	#warning unimplemented
149	(void)offsetofExpr;
150	assert(false);
151	}
152
153	void postvisit( const ast::OffsetofExpr * offsetofExpr ) {
154	addCandidate( offsetofExpr, tenv );
155	}
156
157	void postvisit( const ast::OffsetPackExpr * offsetPackExpr ) {
158	addCandidate( offsetPackExpr, tenv );
159	}
160
161	void postvisit( const ast::LogicalExpr * logicalExpr ) {
162	CandidateFinder finder1{ symtab, tenv };
163	finder1.find( logicalExpr->arg1, ResolvMode::withAdjustment() );
164	if ( finder1.candidates.empty() ) return;
165
166	CandidateFinder finder2{ symtab, tenv };
167	finder2.find( logicalExpr->arg2, ResolvMode::withAdjustment() );
168	if ( finder2.candidates.empty() ) return;
169
170	for ( const CandidateRef & r1 : finder1.candidates ) {
171	for ( const CandidateRef & r2 : finder2.candidates ) {
172	ast::TypeEnvironment env{ r1->env };
173	env.simpleCombine( r2->env );
174	ast::OpenVarSet open{ r1->open };
175	mergeOpenVars( open, r2->open );
176	ast::AssertionSet need;
177	mergeAssertionSet( need, r1->need );
178	mergeAssertionSet( need, r2->need );
179
180	addCandidate(
181	new ast::LogicalExpr{
182	logicalExpr->location, r1->expr, r2->expr, logicalExpr->isAnd },
183	std::move( env ), std::move( open ), std::move( need ),
184	r1->cost + r2->cost );
185	}
186	}
187	}
188
189	void postvisit( const ast::ConditionalExpr * conditionalExpr ) {
190	// candidates for condition
191	CandidateFinder finder1{ symtab, tenv };
192	finder1.find( conditionalExpr->arg1, ResolvMode::withAdjustment() );
193	if ( finder1.candidates.empty() ) return;
194
195	// candidates for true result
196	CandidateFinder finder2{ symtab, tenv };
197	finder2.find( conditionalExpr->arg2, ResolvMode::withAdjustment() );
198	if ( finder2.candidates.empty() ) return;
199
200	// candidates for false result
201	CandidateFinder finder3{ symtab, tenv };
202	finder3.find( conditionalExpr->arg3, ResolvMode::withAdjustment() );
203	if ( finder3.candidates.empty() ) return;
204
205	for ( const CandidateRef & r1 : finder1.candidates ) {
206	for ( const CandidateRef & r2 : finder2.candidates ) {
207	for ( const CandidateRef & r3 : finder3.candidates ) {
208	ast::TypeEnvironment env{ r1->env };
209	env.simpleCombine( r2->env );
210	env.simpleCombine( r3->env );
211	ast::OpenVarSet open{ r1->open };
212	mergeOpenVars( open, r2->open );
213	mergeOpenVars( open, r3->open );
214	ast::AssertionSet need;
215	mergeAssertionSet( need, r1->need );
216	mergeAssertionSet( need, r2->need );
217	mergeAssertionSet( need, r3->need );
218	ast::AssertionSet have;
219
220	// unify true and false results, then infer parameters to produce new
221	// candidates
222	ast::ptr< ast::Type > common;
223	if (
224	unify(
225	r2->expr->result, r3->expr->result, env, need, have, open, symtab,
226	common )
227	) {
228	#warning unimplemented
229	assert(false);
230	}
231	}
232	}
233	}
234	}
235
236	void postvisit( const ast::CommaExpr * commaExpr ) {
237	ast::TypeEnvironment env{ tenv };
238	ast::ptr< ast::Expr > arg1 = resolveInVoidContext( commaExpr->arg1, symtab, env );
239
240	CandidateFinder finder2{ symtab, env };
241	finder2.find( commaExpr->arg2, ResolvMode::withAdjustment() );
242
243	for ( const CandidateRef & r2 : finder2.candidates ) {
244	addCandidate( *r2, new ast::CommaExpr{ commaExpr->location, arg1, r2->expr } );
245	}
246	}
247
248	void postvisit( const ast::ImplicitCopyCtorExpr * ctorExpr ) {
249	addCandidate( ctorExpr, tenv );
250	}
251
252	void postvisit( const ast::ConstructorExpr * ctorExpr ) {
253	CandidateFinder finder{ symtab, tenv };
254	finder.find( ctorExpr->callExpr, ResolvMode::withoutPrune() );
255	for ( CandidateRef & r : finder.candidates ) {
256	addCandidate( *r, new ast::ConstructorExpr{ ctorExpr->location, r->expr } );
257	}
258	}
259
260	void postvisit( const ast::RangeExpr * rangeExpr ) {
261	// resolve low and high, accept candidates where low and high types unify
262	CandidateFinder finder1{ symtab, tenv };
263	finder1.find( rangeExpr->low, ResolvMode::withAdjustment() );
264	if ( finder1.candidates.empty() ) return;
265
266	CandidateFinder finder2{ symtab, tenv };
267	finder2.find( rangeExpr->high, ResolvMode::withAdjustment() );
268	if ( finder2.candidates.empty() ) return;
269
270	for ( const CandidateRef & r1 : finder1.candidates ) {
271	for ( const CandidateRef & r2 : finder2.candidates ) {
272	ast::TypeEnvironment env{ r1->env };
273	env.simpleCombine( r2->env );
274	ast::OpenVarSet open{ r1->open };
275	mergeOpenVars( open, r2->open );
276	ast::AssertionSet need;
277	mergeAssertionSet( need, r1->need );
278	mergeAssertionSet( need, r2->need );
279	ast::AssertionSet have;
280
281	ast::ptr< ast::Type > common;
282	if (
283	unify(
284	r1->expr->result, r2->expr->result, env, need, have, open, symtab,
285	common )
286	) {
287	ast::RangeExpr * newExpr =
288	new ast::RangeExpr{ rangeExpr->location, r1->expr, r2->expr };
289	newExpr->result = common ? common : r1->expr->result;
290
291	#warning unimplemented
292	assert(false);
293	}
294	}
295	}
296	}
297
298	void postvisit( const ast::UntypedTupleExpr * tupleExpr ) {
299	std::vector< CandidateFinder > subCandidates =
300	selfFinder.findSubExprs( tupleExpr->exprs );
301	std::vector< CandidateList > possibilities;
302	combos( subCandidates.begin(), subCandidates.end(), back_inserter( possibilities ) );
303
304	for ( const CandidateList & subs : possibilities ) {
305	std::vector< ast::ptr< ast::Expr > > exprs;
306	exprs.reserve( subs.size() );
307	for ( const CandidateRef & sub : subs ) { exprs.emplace_back( sub->expr ); }
308
309	ast::TypeEnvironment env;
310	ast::OpenVarSet open;
311	ast::AssertionSet need;
312	for ( const CandidateRef & sub : subs ) {
313	env.simpleCombine( sub->env );
314	mergeOpenVars( open, sub->open );
315	mergeAssertionSet( need, sub->need );
316	}
317
318	addCandidate(
319	new ast::TupleExpr{ tupleExpr->location, std::move( exprs ) },
320	std::move( env ), std::move( open ), std::move( need ), sumCost( subs ) );
321	}
322	}
323
324	void postvisit( const ast::TupleExpr * tupleExpr ) {
325	addCandidate( tupleExpr, tenv );
326	}
327
328	void postvisit( const ast::TupleIndexExpr * tupleExpr ) {
329	addCandidate( tupleExpr, tenv );
330	}
331
332	void postvisit( const ast::TupleAssignExpr * tupleExpr ) {
333	addCandidate( tupleExpr, tenv );
334	}
335
336	void postvisit( const ast::UniqueExpr * unqExpr ) {
337	CandidateFinder finder{ symtab, tenv };
338	finder.find( unqExpr->expr, ResolvMode::withAdjustment() );
339	for ( CandidateRef & r : finder.candidates ) {
340	// ensure that the the id is passed on so that the expressions are "linked"
341	addCandidate( *r, new ast::UniqueExpr{ unqExpr->location, r->expr, unqExpr->id } );
342	}
343	}
344
345	void postvisit( const ast::StmtExpr * stmtExpr ) {
346	#warning unimplemented
347	(void)stmtExpr;
348	assert(false);
349	}
350
351	void postvisit( const ast::UntypedInitExpr * initExpr ) {
352	#warning unimplemented
353	(void)initExpr;
354	assert(false);
355	}
356
357	void postvisit( const ast::InitExpr * ) {
358	assertf( false, "CandidateFinder should never see a resolved InitExpr." );
359	}
360
361	void postvisit( const ast::DeletedExpr * ) {
362	assertf( false, "CandidateFinder should never see a DeletedExpr." );
363	}
364
365	void postvisit( const ast::GenericExpr * ) {
366	assertf( false, "_Generic is not yet supported." );
367	}
368	};
369
370	/// Prunes a list of candidates down to those that have the minimum conversion cost for a given
371	/// return type. Skips ambiguous candidates.
372	CandidateList pruneCandidates( CandidateList & candidates ) {
373	struct PruneStruct {
374	CandidateRef candidate;
375	bool ambiguous;
376
377	PruneStruct() = default;
378	PruneStruct( const CandidateRef & c ) : candidate( c ), ambiguous( false ) {}
379	};
380
381	// find lowest-cost candidate for each type
382	std::unordered_map< std::string, PruneStruct > selected;
383	for ( CandidateRef & candidate : candidates ) {
384	std::string mangleName;
385	{
386	ast::ptr< ast::Type > newType = candidate->expr->result;
387	candidate->env.apply( newType );
388	mangleName = Mangle::mangle( newType );
389	}
390
391	auto found = selected.find( mangleName );
392	if ( found != selected.end() ) {
393	if ( candidate->cost < found->second.candidate->cost ) {
394	PRINT(
395	std::cerr << "cost " << candidate->cost << " beats "
396	<< found->second.candidate->cost << std::endl;
397	)
398
399	found->second = PruneStruct{ candidate };
400	} else if ( candidate->cost == found->second.candidate->cost ) {
401	// if one of the candidates contains a deleted identifier, can pick the other,
402	// since deleted expressions should not be ambiguous if there is another option
403	// that is at least as good
404	if ( findDeletedExpr( candidate->expr ) ) {
405	// do nothing
406	PRINT( std::cerr << "candidate is deleted" << std::endl; )
407	} else if ( findDeletedExpr( found->second.candidate->expr ) ) {
408	PRINT( std::cerr << "current is deleted" << std::endl; )
409	found->second = PruneStruct{ candidate };
410	} else {
411	PRINT( std::cerr << "marking ambiguous" << std::endl; )
412	found->second.ambiguous = true;
413	}
414	} else {
415	PRINT(
416	std::cerr << "cost " << candidate->cost << " loses to "
417	<< found->second.candidate->cost << std::endl;
418	)
419	}
420	} else {
421	selected.emplace_hint( found, mangleName, candidate );
422	}
423	}
424
425	// report unambiguous min-cost candidates
426	CandidateList out;
427	for ( auto & target : selected ) {
428	if ( target.second.ambiguous ) continue;
429
430	CandidateRef cand = target.second.candidate;
431
432	ast::ptr< ast::Type > newResult = cand->expr->result;
433	cand->env.applyFree( newResult );
434	cand->expr = ast::mutate_field(
435	cand->expr.get(), &ast::Expr::result, std::move( newResult ) );
436
437	out.emplace_back( cand );
438	}
439	return out;
440	}
441
442	/// Returns a list of alternatives with the minimum cost in the given list
443	CandidateList findMinCost( const CandidateList & candidates ) {
444	CandidateList out;
445	Cost minCost = Cost::infinity;
446	for ( const CandidateRef & r : candidates ) {
447	if ( r->cost < minCost ) {
448	minCost = r->cost;
449	out.clear();
450	out.emplace_back( r );
451	} else if ( r->cost == minCost ) {
452	out.emplace_back( r );
453	}
454	}
455	return out;
456	}
457
458	} // anonymous namespace
459
460	void CandidateFinder::find( const ast::Expr * expr, ResolvMode mode ) {
461	// Find alternatives for expression
462	ast::Pass<Finder> finder{ *this };
463	expr->accept( finder );
464
465	if ( mode.failFast && candidates.empty() ) {
466	SemanticError( expr, "No reasonable alternatives for expression " );
467	}
468
469	if ( mode.satisfyAssns \|\| mode.prune ) {
470	// trim candidates to just those where the assertions are satisfiable
471	// - necessary pre-requisite to pruning
472	CandidateList satisfied;
473	std::vector< std::string > errors;
474	for ( auto & candidate : candidates ) {
475	satisfyAssertions( *candidate, symtab, satisfied, errors );
476	}
477
478	// fail early if none such
479	if ( mode.failFast && satisfied.empty() ) {
480	std::ostringstream stream;
481	stream << "No alternatives with satisfiable assertions for " << expr << "\n";
482	for ( const auto& err : errors ) {
483	stream << err;
484	}
485	SemanticError( expr->location, stream.str() );
486	}
487
488	// reset candidates
489	candidates = std::move( satisfied );
490	}
491
492	if ( mode.prune ) {
493	// trim candidates to single best one
494	PRINT(
495	std::cerr << "alternatives before prune:" << std::endl;
496	print( std::cerr, candidates );
497	)
498
499	CandidateList pruned = pruneCandidates( candidates );
500
501	if ( mode.failFast && pruned.empty() ) {
502	std::ostringstream stream;
503	CandidateList winners = findMinCost( candidates );
504	stream << "Cannot choose between " << winners.size() << " alternatives for "
505	"expression\n";
506	ast::print( stream, expr );
507	stream << " Alternatives are:\n";
508	print( stream, winners, 1 );
509	SemanticError( expr->location, stream.str() );
510	}
511
512	auto oldsize = candidates.size();
513	candidates = std::move( pruned );
514
515	PRINT(
516	std::cerr << "there are " << oldsize << " alternatives before elimination" << std::endl;
517	)
518	PRINT(
519	std::cerr << "there are " << candidates.size() << " alternatives after elimination"
520	<< std::endl;
521	)
522	}
523
524	// adjust types after pruning so that types substituted by pruneAlternatives are correctly
525	// adjusted
526	if ( mode.adjust ) {
527	for ( CandidateRef & r : candidates ) {
528	r->expr = ast::mutate_field(
529	r->expr.get(), &ast::Expr::result,
530	adjustExprType( r->expr->result, r->env, symtab ) );
531	}
532	}
533
534	// Central location to handle gcc extension keyword, etc. for all expressions
535	for ( CandidateRef & r : candidates ) {
536	if ( r->expr->extension != expr->extension ) {
537	r->expr.get_and_mutate()->extension = expr->extension;
538	}
539	}
540	}
541
542	std::vector< CandidateFinder > CandidateFinder::findSubExprs(
543	const std::vector< ast::ptr< ast::Expr > > & xs
544	) {
545	std::vector< CandidateFinder > out;
546
547	for ( const auto & x : xs ) {
548	out.emplace_back( symtab, env );
549	out.back().find( x, ResolvMode::withAdjustment() );
550
551	PRINT(
552	std::cerr << "findSubExprs" << std::endl;
553	print( std::cerr, out.back().candidates );
554	)
555	}
556
557	return out;
558	}
559
560	} // namespace ResolvExpr
561
562	// Local Variables: //
563	// tab-width: 4 //
564	// mode: c++ //
565	// compile-command: "make install" //
566	// End: //

Note: See TracBrowser for help on using the repository browser.

Download in other formats: