source: src/ResolvExpr/SatisfyAssertions.cpp @ edf3ff1

ADTarm-ehast-experimentalenumforall-pointer-decayjacob/cs343-translationnew-ast-unique-exprpthread-emulationqualifiedEnum
Last change on this file since edf3ff1 was e5c3811, checked in by Fangren Yu <f37yu@…>, 4 years ago

create dedicated symbol tables for big 3 operators
note: arbitrary this param type is not supported; it is currently allowed although never used

  • Property mode set to 100644
File size: 18.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
170                std::vector<ast::SymbolTable::IdData> candidates;
171                auto kind = ast::SymbolTable::getSpecialFunctionKind(assn.first->name);
172                if (kind != ast::SymbolTable::SpecialFunctionKind::NUMBER_OF_KINDS) {
173                        // prefilter special decls by argument type, if already known
174                        ast::ptr<ast::Type> thisArgType = strict_dynamic_cast<const ast::PointerType *>(assn.first->get_type())->base
175                                .strict_as<ast::FunctionType>()->params[0]
176                                .strict_as<ast::ReferenceType>()->base;
177                        sat.cand->env.apply(thisArgType);
178
179                        std::string otypeKey = "";
180                        if (thisArgType.as<ast::PointerType>()) otypeKey = Mangle::Encoding::pointer;
181                        else if (!isUnboundType(thisArgType)) otypeKey = Mangle::mangle(thisArgType, Mangle::Type | Mangle::NoGenericParams);
182
183                        candidates = sat.symtab.specialLookupId(kind, otypeKey);
184                }
185                else {
186                        candidates = sat.symtab.lookupId(assn.first->name);
187                }
188                for ( const ast::SymbolTable::IdData & cdata : candidates ) {
189                        const ast::DeclWithType * candidate = cdata.id;
190
191                        // ignore deleted candidates.
192                        // NOTE: this behavior is different from main resolver.
193                        // further investigations might be needed to determine
194                        // if we should implement the same rule here
195                        // (i.e. error if unique best match is deleted)
196                        if (candidate->isDeleted) continue;
197
198                        // build independent unification context for candidate
199                        ast::AssertionSet have, newNeed;
200                        ast::TypeEnvironment newEnv{ sat.cand->env };
201                        ast::OpenVarSet newOpen{ sat.cand->open };
202                        ast::ptr< ast::Type > toType = assn.first->get_type();
203                        ast::ptr< ast::Type > adjType = 
204                                renameTyVars( adjustExprType( candidate->get_type(), newEnv, sat.symtab ) );
205
206                        // only keep candidates which unify
207                        if ( unify( toType, adjType, newEnv, newNeed, have, newOpen, sat.symtab ) ) {
208                                // set up binding slot for recursive assertions
209                                ast::UniqueId crntResnSlot = 0;
210                                if ( ! newNeed.empty() ) {
211                                        crntResnSlot = ++globalResnSlot;
212                                        for ( auto & a : newNeed ) { a.second.resnSlot = crntResnSlot; }
213                                }
214
215                                matches.emplace_back( 
216                                        cdata, adjType, std::move( newEnv ), std::move( have ), std::move( newNeed ),
217                                        std::move( newOpen ), crntResnSlot );
218                        }
219                }
220
221                // break if no satisfying match
222                if ( matches.empty() ) return false;
223
224                // defer if too many satisfying matches
225                if ( matches.size() > 1 ) {
226                        sat.deferred.emplace_back( assn.first, assn.second, std::move( matches ) );
227                        return true;
228                }
229
230                // otherwise bind unique match in ongoing scope
231                AssnCandidate & match = matches.front();
232                addToSymbolTable( match.have, sat.symtab );
233                sat.newNeed.insert( match.need.begin(), match.need.end() );
234                sat.cand->env = std::move( match.env );
235                sat.cand->open = std::move( match.open );
236
237                bindAssertion( assn.first, assn.second, sat.cand, match, sat.inferred );
238                return true;
239        }
240
241        /// Map of candidate return types to recursive assertion satisfaction costs
242        using PruneMap = std::unordered_map< std::string, CostVec >;
243
244        /// Gets the pruning key for a candidate (derived from environment-adjusted return type)
245        std::string pruneKey( const Candidate & cand ) {
246                ast::ptr< ast::Type > resType = cand.expr->result;
247                cand.env.apply( resType );
248                return Mangle::mangle( resType, Mangle::typeMode() );
249        }
250
251        /// Associates inferred parameters with an expression
252        struct InferMatcher final {
253                InferCache & inferred;
254
255                InferMatcher( InferCache & inferred ) : inferred( inferred ) {}
256
257                const ast::Expr * postvisit( const ast::Expr * expr ) {
258                        // Skip if no slots to find
259                        if ( !expr->inferred.hasSlots() ) return expr;
260                        // if ( expr->inferred.mode != ast::Expr::InferUnion::Slots ) return expr;
261                        std::vector<UniqueId> missingSlots;
262                        // find inferred parameters for resolution slots
263                        ast::InferredParams * newInferred = new ast::InferredParams();
264                        for ( UniqueId slot : expr->inferred.resnSlots() ) {
265                                // fail if no matching assertions found
266                                auto it = inferred.find( slot );
267                                if ( it == inferred.end() ) {
268                                        // std::cerr << "missing assertion " << slot << std::endl;
269                                        missingSlots.push_back(slot);
270                                        continue;
271                                }
272
273                                // place inferred parameters into new map
274                                for ( auto & entry : it->second ) {
275                                        // recurse on inferParams of resolved expressions
276                                        entry.second.expr = postvisit( entry.second.expr );
277                                        auto res = newInferred->emplace( entry );
278                                        assert( res.second && "all assertions newly placed" );
279                                }
280                        }
281
282                        ast::Expr * ret = mutate( expr );
283                        ret->inferred.set_inferParams( newInferred );
284                        if (!missingSlots.empty()) ret->inferred.resnSlots() = missingSlots;
285                        return ret;
286                }
287        };
288
289        /// Replace ResnSlots with InferParams and add alternative to output list, if it meets pruning
290        /// threshold.
291        void finalizeAssertions( 
292                CandidateRef & cand, InferCache & inferred, PruneMap & thresholds, CostVec && costs, 
293                CandidateList & out
294        ) {
295                // prune if cheaper alternative for same key has already been generated
296                std::string key = pruneKey( *cand );
297                auto it = thresholds.find( key );
298                if ( it != thresholds.end() ) {
299                        if ( it->second < costs ) return;
300                } else {
301                        thresholds.emplace_hint( it, key, std::move( costs ) );
302                }
303
304                // replace resolution slots with inferred parameters, add to output
305                ast::Pass< InferMatcher > matcher{ inferred };
306                cand->expr = cand->expr->accept( matcher );
307                out.emplace_back( cand );
308        }
309
310        /// Combo iterator that combines candidates into an output list, merging their environments.
311        /// Rejects an appended candidate if environments cannot be merged. See `Common/FilterCombos.h`
312        /// for description of "combo iterator".
313        class CandidateEnvMerger {
314                /// Current list of merged candidates
315                std::vector< DeferRef > crnt;
316                /// Stack of environments to support backtracking
317                std::vector< ast::TypeEnvironment > envs;
318                /// Stack of open variables to support backtracking
319                std::vector< ast::OpenVarSet > opens;
320                /// Symbol table to use for merges
321                const ast::SymbolTable & symtab;
322
323        public:
324                /// The merged environment/open variables and the list of candidates
325                struct OutType {
326                        ast::TypeEnvironment env;
327                        ast::OpenVarSet open;
328                        std::vector< DeferRef > assns;
329                        Cost cost;
330
331                        OutType(
332                                const ast::TypeEnvironment & e, const ast::OpenVarSet & o,
333                                const std::vector< DeferRef > & as, const ast::SymbolTable & symtab )
334                        : env( e ), open( o ), assns( as ), cost( Cost::zero ) {
335                                // compute combined conversion cost
336                                for ( const DeferRef & assn : assns ) {
337                                        // compute conversion cost from satisfying decl to assertion
338                                        cost += computeConversionCost(
339                                                assn.match.adjType, assn.decl->get_type(), false, symtab, env );
340
341                                        // mark vars+specialization on function-type assertions
342                                        const ast::FunctionType * func =
343                                                GenPoly::getFunctionType( assn.match.cdata.id->get_type() );
344                                        if ( ! func ) continue;
345
346                                        for ( const auto & param : func->params ) {
347                                                cost.decSpec( specCost( param ) );
348                                        }
349
350                                        cost.incVar( func->forall.size() );
351
352                                        for ( const ast::TypeDecl * td : func->forall ) {
353                                                cost.decSpec( td->assertions.size() );
354                                        }
355                                }
356                        }
357
358                        bool operator< ( const OutType & o ) const { return cost < o.cost; }
359                };
360
361                CandidateEnvMerger(
362                        const ast::TypeEnvironment & env, const ast::OpenVarSet & open,
363                        const ast::SymbolTable & syms )
364                : crnt(), envs{ env }, opens{ open }, symtab( syms ) {}
365
366                bool append( DeferRef i ) {
367                        ast::TypeEnvironment env = envs.back();
368                        ast::OpenVarSet open = opens.back();
369                        mergeOpenVars( open, i.match.open );
370
371                        if ( ! env.combine( i.match.env, open, symtab ) ) return false;
372
373                        crnt.emplace_back( i );
374                        envs.emplace_back( std::move( env ) );
375                        opens.emplace_back( std::move( open ) );
376                        return true;
377                }
378
379                void backtrack() {
380                        crnt.pop_back();
381                        envs.pop_back();
382                        opens.pop_back();
383                }
384
385                OutType finalize() { return { envs.back(), opens.back(), crnt, symtab }; }
386        };
387
388        /// Limit to depth of recursion of assertion satisfaction
389        static const int recursionLimit = 4;
390        /// Maximum number of simultaneously-deferred assertions to attempt concurrent satisfaction of
391        static const int deferLimit = 10;
392} // anonymous namespace
393
394void satisfyAssertions( 
395        CandidateRef & cand, const ast::SymbolTable & symtab, CandidateList & out, 
396        std::vector<std::string> & errors
397) {
398        // finish early if no assertions to satisfy
399        if ( cand->need.empty() ) {
400                out.emplace_back( cand );
401                return;
402        }
403
404        // build list of possible combinations of satisfying declarations
405        std::vector< SatState > sats{ SatState{ cand, symtab } };
406        std::vector< SatState > nextSats{};
407
408        // pruning thresholds by result type of output candidates.
409        // Candidates *should* be generated in sorted order, so no need to retroactively prune
410        PruneMap thresholds;
411
412        // satisfy assertions in breadth-first order over the recursion tree of assertion satisfaction.
413        // Stop recursion at a limited number of levels deep to avoid infinite loops.
414        for ( unsigned level = 0; level < recursionLimit; ++level ) {
415                // for each current mutually-compatible set of assertions
416                for ( SatState & sat : sats ) {
417                        // stop this branch if a better option is already found
418                        auto it = thresholds.find( pruneKey( *sat.cand ) );
419                        if ( it != thresholds.end() && it->second < sat.costs ) goto nextSat;
420
421                        // make initial pass at matching assertions
422                        for ( auto & assn : sat.need ) {
423                                // fail early if any assertion is not satisfiable
424                                if ( ! satisfyAssertion( assn, sat ) ) {
425                                        Indenter tabs{ 3 };
426                                        std::ostringstream ss;
427                                        ss << tabs << "Unsatisfiable alternative:\n";
428                                        print( ss, *sat.cand, ++tabs );
429                                        ss << (tabs-1) << "Could not satisfy assertion:\n";
430                                        ast::print( ss, assn.first, tabs );
431
432                                        errors.emplace_back( ss.str() );
433                                        goto nextSat;
434                                }
435                        }
436
437                        if ( sat.deferred.empty() ) {
438                                // either add successful match or push back next state
439                                if ( sat.newNeed.empty() ) {
440                                        finalizeAssertions( 
441                                                sat.cand, sat.inferred, thresholds, std::move( sat.costs ), out );
442                                } else {
443                                        nextSats.emplace_back( std::move( sat ), IterateState );
444                                }
445                        } else if ( sat.deferred.size() > deferLimit ) {
446                                // too many deferred assertions to attempt mutual compatibility
447                                Indenter tabs{ 3 };
448                                std::ostringstream ss;
449                                ss << tabs << "Unsatisfiable alternative:\n";
450                                print( ss, *sat.cand, ++tabs );
451                                ss << (tabs-1) << "Too many non-unique satisfying assignments for assertions:\n";
452                                for ( const auto & d : sat.deferred ) {
453                                        ast::print( ss, d.decl, tabs );
454                                }
455
456                                errors.emplace_back( ss.str() );
457                                goto nextSat;
458                        } else {
459                                // combine deferred assertions by mutual compatibility
460                                std::vector< CandidateEnvMerger::OutType > compatible = filterCombos(
461                                        sat.deferred, CandidateEnvMerger{ sat.cand->env, sat.cand->open, sat.symtab } );
462                               
463                                // fail early if no mutually-compatible assertion satisfaction
464                                if ( compatible.empty() ) {
465                                        Indenter tabs{ 3 };
466                                        std::ostringstream ss;
467                                        ss << tabs << "Unsatisfiable alternative:\n";
468                                        print( ss, *sat.cand, ++tabs );
469                                        ss << (tabs-1) << "No mutually-compatible satisfaction for assertions:\n";
470                                        for ( const auto& d : sat.deferred ) {
471                                                ast::print( ss, d.decl, tabs );
472                                        }
473
474                                        errors.emplace_back( ss.str() );
475                                        goto nextSat;
476                                }
477
478                                // sort by cost (for overall pruning order)
479                                std::sort( compatible.begin(), compatible.end() );
480
481                                // process mutually-compatible combinations
482                                for ( auto & compat : compatible ) {
483                                        // set up next satisfaction state
484                                        CandidateRef nextCand = std::make_shared<Candidate>(
485                                                sat.cand->expr, std::move( compat.env ), std::move( compat.open ), 
486                                                ast::AssertionSet{} /* need moved into satisfaction state */,
487                                                sat.cand->cost, sat.cand->cvtCost );
488
489                                        ast::AssertionSet nextNewNeed{ sat.newNeed };
490                                        InferCache nextInferred{ sat.inferred };
491                                       
492                                        CostVec nextCosts{ sat.costs };
493                                        nextCosts.back() += compat.cost;
494                                                               
495                                        ast::SymbolTable nextSymtab{ sat.symtab };
496
497                                        // add compatible assertions to new satisfaction state
498                                        for ( DeferRef r : compat.assns ) {
499                                                AssnCandidate match = r.match;
500                                                addToSymbolTable( match.have, nextSymtab );
501                                                nextNewNeed.insert( match.need.begin(), match.need.end() );
502
503                                                bindAssertion( r.decl, r.info, nextCand, match, nextInferred );
504                                        }
505
506                                        // either add successful match or push back next state
507                                        if ( nextNewNeed.empty() ) {
508                                                finalizeAssertions( 
509                                                        nextCand, nextInferred, thresholds, std::move( nextCosts ), out );
510                                        } else {
511                                                nextSats.emplace_back( 
512                                                        std::move( nextCand ), std::move( nextNewNeed ), 
513                                                        std::move( nextInferred ), std::move( nextCosts ), 
514                                                        std::move( nextSymtab ) );
515                                        }
516                                }
517                        }
518                nextSat:; }
519
520                // finish or reset for next round
521                if ( nextSats.empty() ) return;
522                sats.swap( nextSats );
523                nextSats.clear();
524        }
525       
526        // exceeded recursion limit if reaches here
527        if ( out.empty() ) {
528                SemanticError( cand->expr->location, "Too many recursive assertions" );
529        }
530}
531
532} // namespace ResolvExpr
533
534// Local Variables: //
535// tab-width: 4 //
536// mode: c++ //
537// compile-command: "make install" //
538// End: //
Note: See TracBrowser for help on using the repository browser.