Changeset 052cd71 for src/ResolvExpr
- Timestamp:
- Apr 26, 2019, 4:15:00 PM (5 years ago)
- Branches:
- ADT, arm-eh, ast-experimental, cleanup-dtors, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, pthread-emulation, qualifiedEnum
- Children:
- 9795142
- Parents:
- bd405fa
- git-author:
- Aaron Moss <a3moss@…> (04/26/19 15:44:58)
- git-committer:
- Aaron Moss <a3moss@…> (04/26/19 16:15:00)
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/ResolvExpr/ResolveAssertions.cc
rbd405fa r052cd71 35 35 #include "SynTree/Expression.h" // for InferredParams 36 36 #include "TypeEnvironment.h" // for TypeEnvironment, etc. 37 #include "typeops.h" // for adjustExprType 37 #include "typeops.h" // for adjustExprType, specCost 38 38 #include "Unify.h" // for unify 39 39 … … 58 58 using CandidateList = std::vector<AssnCandidate>; 59 59 60 /// Unique identifier for a yet-to-be-resolved assertion61 struct AssnId {62 DeclarationWithType* decl; ///< Declaration of assertion63 AssertionSetValue info; ///< Information about assertion64 65 AssnId(DeclarationWithType* decl, const AssertionSetValue& info) : decl(decl), info(info) {}66 };67 68 /// Cached assertion items69 struct AssnCacheItem {70 CandidateList matches; ///< Possible matches for this assertion71 std::vector<AssnId> deferIds; ///< Deferred assertions which resolve to this item72 73 AssnCacheItem( CandidateList&& m ) : matches(std::move(m)), deferIds() {}74 };75 76 /// Cache of resolved assertions77 using AssnCache = std::unordered_map<std::string, AssnCacheItem>;78 79 60 /// Reference to single deferred item 80 61 struct DeferRef { 81 const AssnCacheItem& item; 62 const DeclarationWithType* decl; 63 const AssertionSetValue& info; 82 64 const AssnCandidate& match; 83 65 }; … … 86 68 /// Acts like indexed list of DeferRef 87 69 struct DeferItem { 88 const AssnCache* cache; ///< Cache storing assertion item 89 std::string key; ///< Key into cache 90 91 DeferItem( const AssnCache& cache, const std::string& key ) : cache(&cache), key(key) {} 92 93 bool empty() const { return cache->at(key).matches.empty(); } 94 95 CandidateList::size_type size() const { return cache->at(key).matches.size(); } 96 97 DeferRef operator[] ( unsigned i ) const { 98 const AssnCacheItem& item = cache->at(key); 99 return { item, item.matches[i] }; 100 } 101 102 const DeclarationWithType* get_decl() const { return cache->at(key).deferIds[0].decl; } 103 104 // sortable by key 105 // TODO look into optimizing combination process with other sort orders (e.g. by number 106 // of matches in candidate) 107 bool operator< ( const DeferItem& o ) const { return key < o.key; } 108 bool operator== ( const DeferItem& o ) const { return key == o.key; } 70 const DeclarationWithType* decl; 71 const AssertionSetValue& info; 72 CandidateList matches; 73 74 DeferItem( DeclarationWithType* decl, const AssertionSetValue& info, CandidateList&& matches ) 75 : decl(decl), info(info), matches(std::move(matches)) {} 76 77 bool empty() const { return matches.empty(); } 78 79 CandidateList::size_type size() const { return matches.size(); } 80 81 DeferRef operator[] ( unsigned i ) const { return { decl, info, matches[i] }; } 109 82 }; 110 83 … … 181 154 for ( const auto& assn : x.assns ) { 182 155 k += computeConversionCost( 183 assn.match.adjType, assn.item.deferIds[0].decl->get_type(), indexer, 184 x.env ); 156 assn.match.adjType, assn.decl->get_type(), indexer, x.env ); 185 157 } 186 158 it = cache.emplace_hint( it, &x, k ); … … 253 225 254 226 /// Resolve a single assertion, in context 255 bool resolveAssertion( AssertionItem& assn, ResnState& resn , AssnCache& cache) {227 bool resolveAssertion( AssertionItem& assn, ResnState& resn ) { 256 228 // skip unused assertions 257 229 if ( ! assn.info.isUsed ) return true; 258 230 259 // check cache for this assertion 260 std::string assnKey = SymTab::Mangler::mangleAssnKey( assn.decl, resn.alt.env ); 261 auto it = cache.find( assnKey ); 262 263 // attempt to resolve assertion if this is the first time seen 264 if ( it == cache.end() ) { 265 // lookup candidates for this assertion 266 std::list< SymTab::Indexer::IdData > candidates; 267 resn.indexer.lookupId( assn.decl->name, candidates ); 268 269 // find the candidates that unify with the desired type 270 CandidateList matches; 271 for ( const auto& cdata : candidates ) { 272 DeclarationWithType* candidate = cdata.id; 273 274 // build independent unification context for candidate 275 AssertionSet have, newNeed; 276 TypeEnvironment newEnv{ resn.alt.env }; 277 OpenVarSet newOpenVars{ resn.alt.openVars }; 278 Type* adjType = candidate->get_type()->clone(); 279 adjustExprType( adjType, newEnv, resn.indexer ); 280 renameTyVars( adjType ); 281 282 // keep unifying candidates 283 if ( unify( assn.decl->get_type(), adjType, newEnv, newNeed, have, newOpenVars, 284 resn.indexer ) ) { 285 // set up binding slot for recursive assertions 286 UniqueId crntResnSlot = 0; 287 if ( ! newNeed.empty() ) { 288 crntResnSlot = ++globalResnSlot; 289 for ( auto& a : newNeed ) { 290 a.second.resnSlot = crntResnSlot; 291 } 231 // lookup candidates for this assertion 232 std::list< SymTab::Indexer::IdData > candidates; 233 resn.indexer.lookupId( assn.decl->name, candidates ); 234 235 // find the candidates that unify with the desired type 236 CandidateList matches; 237 for ( const auto& cdata : candidates ) { 238 DeclarationWithType* candidate = cdata.id; 239 240 // build independent unification context for candidate 241 AssertionSet have, newNeed; 242 TypeEnvironment newEnv{ resn.alt.env }; 243 OpenVarSet newOpenVars{ resn.alt.openVars }; 244 Type* adjType = candidate->get_type()->clone(); 245 adjustExprType( adjType, newEnv, resn.indexer ); 246 renameTyVars( adjType ); 247 248 // keep unifying candidates 249 if ( unify( assn.decl->get_type(), adjType, newEnv, newNeed, have, newOpenVars, 250 resn.indexer ) ) { 251 // set up binding slot for recursive assertions 252 UniqueId crntResnSlot = 0; 253 if ( ! newNeed.empty() ) { 254 crntResnSlot = ++globalResnSlot; 255 for ( auto& a : newNeed ) { 256 a.second.resnSlot = crntResnSlot; 292 257 } 293 294 matches.emplace_back( cdata, adjType, std::move(newEnv), std::move(have), 295 std::move(newNeed), std::move(newOpenVars), crntResnSlot );296 } else {297 delete adjType;298 }258 } 259 260 matches.emplace_back( cdata, adjType, std::move(newEnv), std::move(have), 261 std::move(newNeed), std::move(newOpenVars), crntResnSlot ); 262 } else { 263 delete adjType; 299 264 } 300 301 it = cache.emplace_hint( it, assnKey, AssnCacheItem{ std::move(matches) } ); 302 } 303 304 CandidateList& matches = it->second.matches; 265 } 305 266 306 267 // break if no suitable assertion … … 309 270 // defer if too many suitable assertions 310 271 if ( matches.size() > 1 ) { 311 it->second.deferIds.emplace_back( assn.decl, assn.info ); 312 resn.deferred.emplace_back( cache, assnKey ); 272 resn.deferred.emplace_back( assn.decl, assn.info, std::move(matches) ); 313 273 return true; 314 274 } … … 318 278 addToIndexer( match.have, resn.indexer ); 319 279 resn.newNeed.insert( match.need.begin(), match.need.end() ); 320 resn.alt.env = match.env;321 resn.alt.openVars = match.openVars;280 resn.alt.env = std::move(match.env); 281 resn.alt.openVars = std::move(match.openVars); 322 282 323 283 bindAssertion( assn.decl, assn.info, resn.alt, match, resn.inferred ); … … 380 340 ResnList resns{ ResnState{ alt, root_indexer } }; 381 341 ResnList new_resns{}; 382 AssnCache assnCache;383 342 384 343 // resolve assertions in breadth-first-order up to a limited number of levels deep … … 389 348 for ( auto& assn : resn.need ) { 390 349 // fail early if any assertion is not resolvable 391 if ( ! resolveAssertion( assn, resn , assnCache) ) {350 if ( ! resolveAssertion( assn, resn ) ) { 392 351 Indenter tabs{ Indenter::tabsize, 3 }; 393 352 std::ostringstream ss; … … 410 369 } 411 370 } else { 412 // only resolve each deferred assertion once413 std::sort( resn.deferred.begin(), resn.deferred.end() );414 auto last = std::unique( resn.deferred.begin(), resn.deferred.end() );415 resn.deferred.erase( last, resn.deferred.end() );416 371 // resolve deferred assertions by mutual compatibility 417 372 std::vector<CandidateEnvMerger::OutType> compatible = filterCombos( … … 427 382 ++tabs; 428 383 for ( const auto& d : resn.deferred ) { 429 d. get_decl()->print( ss, tabs );384 d.decl->print( ss, tabs ); 430 385 } 431 386 … … 458 413 new_resn.newNeed.insert( match.need.begin(), match.need.end() ); 459 414 460 // for each deferred assertion with the same form 461 for ( AssnId id : r.item.deferIds ) { 462 bindAssertion( 463 id.decl, id.info, new_resn.alt, match, new_resn.inferred ); 464 } 415 bindAssertion( r.decl, r.info, new_resn.alt, match, new_resn.inferred ); 465 416 } 466 417
Note: See TracChangeset
for help on using the changeset viewer.