source: src/ResolvExpr/SatisfyAssertions.cpp@ 22f94a4

ADT arm-eh ast-experimental enum forall-pointer-decay jacob/cs343-translation new-ast new-ast-unique-expr pthread-emulation qualifiedEnum
Last change on this file since 22f94a4 was 07d867b, checked in by Fangren Yu <f37yu@…>, 5 years ago

attempt to fix inferparams
  • Property mode set to 100644
File size: 17.8 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// SatisfyAssertions.cpp --
8//
9// Author : Aaron B. Moss
10// Created On : Mon Jun 10 17:45:00 2019
11// Last Modified By : Andrew Beach
12// Last Modified On : Tue Oct 1 13:56:00 2019
13// Update Count : 2
14//
15
16#include "SatisfyAssertions.hpp"
17
18#include <algorithm>
19#include <cassert>
20#include <sstream>
21#include <string>
22#include <unordered_map>
23#include <vector>
24
25#include "Candidate.hpp"
26#include "CandidateFinder.hpp"
27#include "Cost.h"
28#include "RenameVars.h"
29#include "typeops.h"
30#include "Unify.h"
31#include "AST/Decl.hpp"
32#include "AST/Expr.hpp"
33#include "AST/Node.hpp"
34#include "AST/Pass.hpp"
35#include "AST/Print.hpp"
36#include "AST/SymbolTable.hpp"
37#include "AST/TypeEnvironment.hpp"
38#include "Common/FilterCombos.h"
39#include "Common/Indenter.h"
40#include "GenPoly/GenPoly.h"
41#include "SymTab/Mangler.h"
42
43namespace ResolvExpr {
44
45// in CandidateFinder.cpp; unique ID for assertion satisfaction
46extern UniqueId globalResnSlot;
47
48namespace {
49 /// Post-unification assertion satisfaction candidate
50 struct AssnCandidate {
51 ast::SymbolTable::IdData cdata; ///< Satisfying declaration
52 ast::ptr< ast::Type > adjType; ///< Satisfying type
53 ast::TypeEnvironment env; ///< Post-unification environment
54 ast::AssertionSet have; ///< Post-unification have-set
55 ast::AssertionSet need; ///< Post-unification need-set
56 ast::OpenVarSet open; ///< Post-unification open-var-set
57 ast::UniqueId resnSlot; ///< Slot for any recursive assertion IDs
58
59 AssnCandidate(
60 const ast::SymbolTable::IdData c, const ast::Type * at, ast::TypeEnvironment && e,
61 ast::AssertionSet && h, ast::AssertionSet && n, ast::OpenVarSet && o, ast::UniqueId rs )
62 : cdata( c ), adjType( at ), env( std::move( e ) ), have( std::move( h ) ),
63 need( std::move( n ) ), open( std::move( o ) ), resnSlot( rs ) {}
64 };
65
66 /// List of assertion satisfaction candidates
67 using AssnCandidateList = std::vector< AssnCandidate >;
68
69 /// Reference to a single deferred item
70 struct DeferRef {
71 const ast::DeclWithType * decl;
72 const ast::AssertionSetValue & info;
73 const AssnCandidate & match;
74 };
75
76 /// Wrapper for the deferred items from a single assertion satisfaction.
77 /// Acts like an indexed list of DeferRef
78 struct DeferItem {
79 const ast::DeclWithType * decl;
80 const ast::AssertionSetValue & info;
81 AssnCandidateList matches;
82
83 DeferItem(
84 const ast::DeclWithType * d, const ast::AssertionSetValue & i, AssnCandidateList && ms )
85 : decl( d ), info( i ), matches( std::move( ms ) ) {}
86
87 bool empty() const { return matches.empty(); }
88
89 AssnCandidateList::size_type size() const { return matches.size(); }
90
91 DeferRef operator[] ( unsigned i ) const { return { decl, info, matches[i] }; }
92 };
93
94 /// List of deferred satisfaction items
95 using DeferList = std::vector< DeferItem >;
96
97 /// Set of assertion satisfactions, grouped by resolution ID
98 using InferCache = std::unordered_map< ast::UniqueId, ast::InferredParams >;
99
100 /// Lexicographically-ordered vector of costs.
101 /// Lexicographic order comes from default operator< on std::vector.
102 using CostVec = std::vector< Cost >;
103
104 /// Flag for state iteration
105 enum IterateFlag { IterateState };
106
107 /// Intermediate state for satisfying a set of assertions
108 struct SatState {
109 CandidateRef cand; ///< Candidate assertion is rooted on
110 ast::AssertionList need; ///< Assertions to find
111 ast::AssertionSet newNeed; ///< Recursive assertions from current satisfied assertions
112 DeferList deferred; ///< Deferred matches
113 InferCache inferred; ///< Cache of already-inferred assertions
114 CostVec costs; ///< Disambiguating costs of recursive assertion satisfaction
115 ast::SymbolTable symtab; ///< Name lookup (depends on previous assertions)
116
117 /// Initial satisfaction state for a candidate
118 SatState( CandidateRef & c, const ast::SymbolTable & syms )
119 : cand( c ), need(), newNeed(), deferred(), inferred(), costs{ Cost::zero },
120 symtab( syms ) { need.swap( c->need ); }
121
122 /// Update satisfaction state for next step after previous state
123 SatState( SatState && o, IterateFlag )
124 : cand( std::move( o.cand ) ), need( o.newNeed.begin(), o.newNeed.end() ), newNeed(),
125 deferred(), inferred( std::move( o.inferred ) ), costs( std::move( o.costs ) ),
126 symtab( o.symtab ) { costs.emplace_back( Cost::zero ); }
127
128 /// Field-wise next step constructor
129 SatState(
130 CandidateRef && c, ast::AssertionSet && nn, InferCache && i, CostVec && cs,
131 ast::SymbolTable && syms )
132 : cand( std::move( c ) ), need( nn.begin(), nn.end() ), newNeed(), deferred(),
133 inferred( std::move( i ) ), costs( std::move( cs ) ), symtab( std::move( syms ) )
134 { costs.emplace_back( Cost::zero ); }
135 };
136
137 /// Adds a captured assertion to the symbol table
138 void addToSymbolTable( const ast::AssertionSet & have, ast::SymbolTable & symtab ) {
139 for ( auto & i : have ) {
140 if ( i.second.isUsed ) { symtab.addId( i.first ); }
141 }
142 }
143
144 /// Binds a single assertion, updating satisfaction state
145 void bindAssertion(
146 const ast::DeclWithType * decl, const ast::AssertionSetValue & info, CandidateRef & cand,
147 AssnCandidate & match, InferCache & inferred
148 ) {
149 const ast::DeclWithType * candidate = match.cdata.id;
150 assertf( candidate->uniqueId,
151 "Assertion candidate does not have a unique ID: %s", toString( candidate ).c_str() );
152
153 ast::Expr * varExpr = match.cdata.combine( cand->expr->location, cand->cvtCost );
154 varExpr->result = match.adjType;
155 if ( match.resnSlot ) { varExpr->inferred.resnSlots().emplace_back( match.resnSlot ); }
156
157 // place newly-inferred assertion in proper location in cache
158 inferred[ info.resnSlot ][ decl->uniqueId ] = ast::ParamEntry{
159 candidate->uniqueId, candidate, match.adjType, decl->get_type(), varExpr };
160 }
161
162 /// Satisfy a single assertion
163 bool satisfyAssertion( ast::AssertionList::value_type & assn, SatState & sat ) {
164 // skip unused assertions
165 if ( ! assn.second.isUsed ) return true;
166
167 // find candidates that unify with the desired type
168 AssnCandidateList matches;
169 for ( const ast::SymbolTable::IdData & cdata : sat.symtab.lookupId( assn.first->name ) ) {
170 const ast::DeclWithType * candidate = cdata.id;
171
172 // build independent unification context for candidate
173 ast::AssertionSet have, newNeed;
174 ast::TypeEnvironment newEnv{ sat.cand->env };
175 ast::OpenVarSet newOpen{ sat.cand->open };
176 ast::ptr< ast::Type > toType = assn.first->get_type();
177 ast::ptr< ast::Type > adjType =
178 renameTyVars( adjustExprType( candidate->get_type(), newEnv, sat.symtab ) );
179
180 // only keep candidates which unify
181 if ( unify( toType, adjType, newEnv, newNeed, have, newOpen, sat.symtab ) ) {
182 // set up binding slot for recursive assertions
183 ast::UniqueId crntResnSlot = 0;
184 if ( ! newNeed.empty() ) {
185 crntResnSlot = ++globalResnSlot;
186 for ( auto & a : newNeed ) { a.second.resnSlot = crntResnSlot; }
187 }
188
189 matches.emplace_back(
190 cdata, adjType, std::move( newEnv ), std::move( have ), std::move( newNeed ),
191 std::move( newOpen ), crntResnSlot );
192 }
193 }
194
195 // break if no satisfying match
196 if ( matches.empty() ) return false;
197
198 // defer if too many satisfying matches
199 if ( matches.size() > 1 ) {
200 sat.deferred.emplace_back( assn.first, assn.second, std::move( matches ) );
201 return true;
202 }
203
204 // otherwise bind unique match in ongoing scope
205 AssnCandidate & match = matches.front();
206 addToSymbolTable( match.have, sat.symtab );
207 sat.newNeed.insert( match.need.begin(), match.need.end() );
208 sat.cand->env = std::move( match.env );
209 sat.cand->open = std::move( match.open );
210
211 bindAssertion( assn.first, assn.second, sat.cand, match, sat.inferred );
212 return true;
213 }
214
215 /// Map of candidate return types to recursive assertion satisfaction costs
216 using PruneMap = std::unordered_map< std::string, CostVec >;
217
218 /// Gets the pruning key for a candidate (derived from environment-adjusted return type)
219 std::string pruneKey( const Candidate & cand ) {
220 ast::ptr< ast::Type > resType = cand.expr->result;
221 cand.env.apply( resType );
222 return Mangle::mangle( resType, Mangle::typeMode() );
223 }
224
225 /// Associates inferred parameters with an expression
226 struct InferMatcher final {
227 InferCache & inferred;
228
229 InferMatcher( InferCache & inferred ) : inferred( inferred ) {}
230
231 const ast::Expr * postvisit( const ast::Expr * expr ) {
232 // Skip if no slots to find
233 if ( !expr->inferred.hasSlots() ) return expr;
234 // if ( expr->inferred.mode != ast::Expr::InferUnion::Slots ) return expr;
235 std::vector<UniqueId> missingSlots;
236 // find inferred parameters for resolution slots
237 ast::InferredParams * newInferred = new ast::InferredParams();
238 for ( UniqueId slot : expr->inferred.resnSlots() ) {
239 // fail if no matching assertions found
240 auto it = inferred.find( slot );
241 if ( it == inferred.end() ) {
242 std::cerr << "missing assertion " << slot << std::endl;
243 missingSlots.push_back(slot);
244 continue;
245 }
246
247 // place inferred parameters into new map
248 for ( auto & entry : it->second ) {
249 // recurse on inferParams of resolved expressions
250 entry.second.expr = postvisit( entry.second.expr );
251 auto res = newInferred->emplace( entry );
252 assert( res.second && "all assertions newly placed" );
253 }
254 }
255
256 ast::Expr * ret = mutate( expr );
257 ret->inferred.set_inferParams( newInferred );
258 if (!missingSlots.empty()) ret->inferred.resnSlots() = missingSlots;
259 return ret;
260 }
261 };
262
263 /// Replace ResnSlots with InferParams and add alternative to output list, if it meets pruning
264 /// threshold.
265 void finalizeAssertions(
266 CandidateRef & cand, InferCache & inferred, PruneMap & thresholds, CostVec && costs,
267 CandidateList & out
268 ) {
269 // prune if cheaper alternative for same key has already been generated
270 std::string key = pruneKey( *cand );
271 auto it = thresholds.find( key );
272 if ( it != thresholds.end() ) {
273 if ( it->second < costs ) return;
274 } else {
275 thresholds.emplace_hint( it, key, std::move( costs ) );
276 }
277
278 // replace resolution slots with inferred parameters, add to output
279 ast::Pass< InferMatcher > matcher{ inferred };
280 cand->expr = cand->expr->accept( matcher );
281 out.emplace_back( cand );
282 }
283
284 /// Combo iterator that combines candidates into an output list, merging their environments.
285 /// Rejects an appended candidate if environments cannot be merged. See `Common/FilterCombos.h`
286 /// for description of "combo iterator".
287 class CandidateEnvMerger {
288 /// Current list of merged candidates
289 std::vector< DeferRef > crnt;
290 /// Stack of environments to support backtracking
291 std::vector< ast::TypeEnvironment > envs;
292 /// Stack of open variables to support backtracking
293 std::vector< ast::OpenVarSet > opens;
294 /// Symbol table to use for merges
295 const ast::SymbolTable & symtab;
296
297 public:
298 /// The merged environment/open variables and the list of candidates
299 struct OutType {
300 ast::TypeEnvironment env;
301 ast::OpenVarSet open;
302 std::vector< DeferRef > assns;
303 Cost cost;
304
305 OutType(
306 const ast::TypeEnvironment & e, const ast::OpenVarSet & o,
307 const std::vector< DeferRef > & as, const ast::SymbolTable & symtab )
308 : env( e ), open( o ), assns( as ), cost( Cost::zero ) {
309 // compute combined conversion cost
310 for ( const DeferRef & assn : assns ) {
311 // compute conversion cost from satisfying decl to assertion
312 cost += computeConversionCost(
313 assn.match.adjType, assn.decl->get_type(), false, symtab, env );
314
315 // mark vars+specialization on function-type assertions
316 const ast::FunctionType * func =
317 GenPoly::getFunctionType( assn.match.cdata.id->get_type() );
318 if ( ! func ) continue;
319
320 for ( const ast::DeclWithType * param : func->params ) {
321 cost.decSpec( specCost( param->get_type() ) );
322 }
323
324 cost.incVar( func->forall.size() );
325
326 for ( const ast::TypeDecl * td : func->forall ) {
327 cost.decSpec( td->assertions.size() );
328 }
329 }
330 }
331
332 bool operator< ( const OutType & o ) const { return cost < o.cost; }
333 };
334
335 CandidateEnvMerger(
336 const ast::TypeEnvironment & env, const ast::OpenVarSet & open,
337 const ast::SymbolTable & syms )
338 : crnt(), envs{ env }, opens{ open }, symtab( syms ) {}
339
340 bool append( DeferRef i ) {
341 ast::TypeEnvironment env = envs.back();
342 ast::OpenVarSet open = opens.back();
343 mergeOpenVars( open, i.match.open );
344
345 if ( ! env.combine( i.match.env, open, symtab ) ) return false;
346
347 crnt.emplace_back( i );
348 envs.emplace_back( std::move( env ) );
349 opens.emplace_back( std::move( open ) );
350 return true;
351 }
352
353 void backtrack() {
354 crnt.pop_back();
355 envs.pop_back();
356 opens.pop_back();
357 }
358
359 OutType finalize() { return { envs.back(), opens.back(), crnt, symtab }; }
360 };
361
362 /// Limit to depth of recursion of assertion satisfaction
363 static const int recursionLimit = 4;
364 /// Maximum number of simultaneously-deferred assertions to attempt concurrent satisfaction of
365 static const int deferLimit = 10;
366} // anonymous namespace
367
368void satisfyAssertions(
369 CandidateRef & cand, const ast::SymbolTable & symtab, CandidateList & out,
370 std::vector<std::string> & errors
371) {
372 // finish early if no assertions to satisfy
373 if ( cand->need.empty() ) {
374 out.emplace_back( cand );
375 return;
376 }
377
378 // build list of possible combinations of satisfying declarations
379 std::vector< SatState > sats{ SatState{ cand, symtab } };
380 std::vector< SatState > nextSats{};
381
382 // pruning thresholds by result type of output candidates.
383 // Candidates *should* be generated in sorted order, so no need to retroactively prune
384 PruneMap thresholds;
385
386 // satisfy assertions in breadth-first order over the recursion tree of assertion satisfaction.
387 // Stop recursion at a limited number of levels deep to avoid infinite loops.
388 for ( unsigned level = 0; level < recursionLimit; ++level ) {
389 // for each current mutually-compatible set of assertions
390 for ( SatState & sat : sats ) {
391 // stop this branch if a better option is already found
392 auto it = thresholds.find( pruneKey( *sat.cand ) );
393 if ( it != thresholds.end() && it->second < sat.costs ) goto nextSat;
394
395 // make initial pass at matching assertions
396 for ( auto & assn : sat.need ) {
397 // fail early if any assertion is not satisfiable
398 if ( ! satisfyAssertion( assn, sat ) ) {
399 Indenter tabs{ 3 };
400 std::ostringstream ss;
401 ss << tabs << "Unsatisfiable alternative:\n";
402 print( ss, *sat.cand, ++tabs );
403 ss << (tabs-1) << "Could not satisfy assertion:\n";
404 ast::print( ss, assn.first, tabs );
405
406 errors.emplace_back( ss.str() );
407 goto nextSat;
408 }
409 }
410
411 if ( sat.deferred.empty() ) {
412 // either add successful match or push back next state
413 if ( sat.newNeed.empty() ) {
414 finalizeAssertions(
415 sat.cand, sat.inferred, thresholds, std::move( sat.costs ), out );
416 } else {
417 nextSats.emplace_back( std::move( sat ), IterateState );
418 }
419 } else if ( sat.deferred.size() > deferLimit ) {
420 // too many deferred assertions to attempt mutual compatibility
421 Indenter tabs{ 3 };
422 std::ostringstream ss;
423 ss << tabs << "Unsatisfiable alternative:\n";
424 print( ss, *sat.cand, ++tabs );
425 ss << (tabs-1) << "Too many non-unique satisfying assignments for assertions:\n";
426 for ( const auto & d : sat.deferred ) {
427 ast::print( ss, d.decl, tabs );
428 }
429
430 errors.emplace_back( ss.str() );
431 goto nextSat;
432 } else {
433 // combine deferred assertions by mutual compatibility
434 std::vector< CandidateEnvMerger::OutType > compatible = filterCombos(
435 sat.deferred, CandidateEnvMerger{ sat.cand->env, sat.cand->open, sat.symtab } );
436
437 // fail early if no mutually-compatible assertion satisfaction
438 if ( compatible.empty() ) {
439 Indenter tabs{ 3 };
440 std::ostringstream ss;
441 ss << tabs << "Unsatisfiable alternative:\n";
442 print( ss, *sat.cand, ++tabs );
443 ss << (tabs-1) << "No mutually-compatible satisfaction for assertions:\n";
444 for ( const auto& d : sat.deferred ) {
445 ast::print( ss, d.decl, tabs );
446 }
447
448 errors.emplace_back( ss.str() );
449 goto nextSat;
450 }
451
452 // sort by cost (for overall pruning order)
453 std::sort( compatible.begin(), compatible.end() );
454
455 // process mutually-compatible combinations
456 for ( auto & compat : compatible ) {
457 // set up next satisfaction state
458 CandidateRef nextCand = std::make_shared<Candidate>(
459 sat.cand->expr, std::move( compat.env ), std::move( compat.open ),
460 ast::AssertionSet{} /* need moved into satisfaction state */,
461 sat.cand->cost, sat.cand->cvtCost );
462
463 ast::AssertionSet nextNewNeed{ sat.newNeed };
464 InferCache nextInferred{ sat.inferred };
465
466 CostVec nextCosts{ sat.costs };
467 nextCosts.back() += compat.cost;
468
469 ast::SymbolTable nextSymtab{ sat.symtab };
470
471 // add compatible assertions to new satisfaction state
472 for ( DeferRef r : compat.assns ) {
473 AssnCandidate match = r.match;
474 addToSymbolTable( match.have, nextSymtab );
475 nextNewNeed.insert( match.need.begin(), match.need.end() );
476
477 bindAssertion( r.decl, r.info, nextCand, match, nextInferred );
478 }
479
480 // either add successful match or push back next state
481 if ( nextNewNeed.empty() ) {
482 finalizeAssertions(
483 nextCand, nextInferred, thresholds, std::move( nextCosts ), out );
484 } else {
485 nextSats.emplace_back(
486 std::move( nextCand ), std::move( nextNewNeed ),
487 std::move( nextInferred ), std::move( nextCosts ),
488 std::move( nextSymtab ) );
489 }
490 }
491 }
492 nextSat:; }
493
494 // finish or reset for next round
495 if ( nextSats.empty() ) return;
496 sats.swap( nextSats );
497 nextSats.clear();
498 }
499
500 // exceeded recursion limit if reaches here
501 if ( out.empty() ) {
502 SemanticError( cand->expr->location, "Too many recursive assertions" );
503 }
504}
505
506} // namespace ResolvExpr
507
508// Local Variables: //
509// tab-width: 4 //
510// mode: c++ //
511// compile-command: "make install" //
512// End: //
Note: See TracBrowser for help on using the repository browser.