- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
src/ResolvExpr/ResolveAssertions.cc
re1f7eef raeb8f70 20 20 #include <list> // for list 21 21 #include <memory> // for unique_ptr 22 #include <string>23 22 #include <unordered_map> // for unordered_map, unordered_multimap 24 23 #include <utility> // for move … … 56 55 using CandidateList = std::vector<AssnCandidate>; 57 56 58 /// Unique identifier for a yet-to-be-resolved assertion59 struct AssnId {60 DeclarationWithType* decl; ///< Declaration of assertion61 AssertionSetValue info; ///< Information about assertion62 63 AssnId(DeclarationWithType* decl, const AssertionSetValue& info) : decl(decl), info(info) {}64 };65 66 /// Cached assertion items67 struct AssnCacheItem {68 CandidateList matches; ///< Possible matches for this assertion69 std::vector<AssnId> deferIds; ///< Deferred assertions which resolve to this item70 71 AssnCacheItem( CandidateList&& m ) : matches(std::move(m)), deferIds() {}72 };73 74 /// Cache of resolved assertions75 using AssnCache = std::unordered_map<std::string, AssnCacheItem>;76 77 57 /// Reference to single deferred item 78 58 struct DeferRef { 79 const AssnCacheItem& item; 59 const DeclarationWithType* decl; 60 const AssertionSetValue& info; 80 61 const AssnCandidate& match; 81 62 }; … … 84 65 /// Acts like indexed list of DeferRef 85 66 struct DeferItem { 86 const AssnCache* cache; ///< Cache storing assertion item 87 std::string key; ///< Key into cache 88 89 DeferItem( const AssnCache& cache, const std::string& key ) : cache(&cache), key(key) {} 90 91 bool empty() const { return cache->at(key).matches.empty(); } 92 93 CandidateList::size_type size() const { return cache->at(key).matches.size(); } 94 95 DeferRef operator[] ( unsigned i ) const { 96 const AssnCacheItem& item = cache->at(key); 97 return { item, item.matches[i] }; 98 } 99 100 // sortable by key 101 // TODO look into optimizing combination process with other sort orders (e.g. by number 102 // of matches in candidate) 103 bool operator< ( const DeferItem& o ) const { return key < o.key; } 104 bool operator== ( const DeferItem& o ) const { return key == o.key; } 67 DeclarationWithType* decl; 68 AssertionSetValue info; 69 CandidateList matches; 70 71 DeferItem( DeclarationWithType* decl, const AssertionSetValue& info, 72 CandidateList&& matches ) 73 : decl(decl), info(info), matches(std::move(matches)) {} 74 75 bool empty() const { return matches.empty(); } 76 77 CandidateList::size_type size() const { return matches.size(); } 78 79 DeferRef operator[] ( unsigned i ) const { return { decl, info, matches[i] }; } 105 80 }; 106 81 … … 177 152 for ( const auto& assn : x.assns ) { 178 153 k += computeConversionCost( 179 assn.match.adjType, assn.item.deferIds[0].decl->get_type(), indexer, 180 x.env ); 154 assn.match.adjType, assn.decl->get_type(), indexer, x.env ); 181 155 } 182 156 it = cache.emplace_hint( it, &x, k ); … … 234 208 candidate->get_uniqueId(), match.adjType->clone(), decl->get_type()->clone(), 235 209 varExpr }; 210 211 // // follow the current assertion's ID chain to find the correct set of inferred parameters 212 // // to add the candidate o (i.e. the set of inferred parameters belonging to the entity 213 // // which requested the assertion parameter) 214 // InferredParams* inferParams = &alt.expr->inferParams; 215 // for ( UniqueId id : info.idChain ) { 216 // inferParams = (*inferParams)[ id ].inferParams.get(); 217 // } 218 219 // (*inferParams)[ decl->get_uniqueId() ] = ParamEntry{ 220 // candidate->get_uniqueId(), match.adjType, decl->get_type()->clone(), varExpr }; 236 221 } 237 222 238 223 /// Adds a captured assertion to the symbol table 239 224 void addToIndexer( AssertionSet &assertSet, SymTab::Indexer &indexer ) { 240 for ( auto& i : assertSet) {241 if ( i .second.isUsed ) {242 indexer.addId( i .first );225 for ( AssertionSet::iterator i = assertSet.begin(); i != assertSet.end(); ++i ) { 226 if ( i->second.isUsed ) { 227 indexer.addId( i->first ); 243 228 } 244 229 } … … 249 234 250 235 /// Resolve a single assertion, in context 251 bool resolveAssertion( AssertionItem& assn, ResnState& resn , AssnCache& cache) {236 bool resolveAssertion( AssertionItem& assn, ResnState& resn ) { 252 237 // skip unused assertions 253 238 if ( ! assn.info.isUsed ) return true; 254 239 255 // check cache for this assertion 256 std::string assnKey = SymTab::Mangler::mangleAssnKey( assn.decl, resn.alt.env ); 257 auto it = cache.find( assnKey ); 258 259 // attempt to resolve assertion if this is the first time seen 260 if ( it == cache.end() ) { 261 // lookup candidates for this assertion 262 std::list< SymTab::Indexer::IdData > candidates; 263 resn.indexer.lookupId( assn.decl->name, candidates ); 264 265 // find the candidates that unify with the desired type 266 CandidateList matches; 267 for ( const auto& cdata : candidates ) { 268 DeclarationWithType* candidate = cdata.id; 269 270 // build independent unification context for candidate 271 AssertionSet have, newNeed; 272 TypeEnvironment newEnv{ resn.alt.env }; 273 OpenVarSet newOpenVars{ resn.alt.openVars }; 274 Type* adjType = candidate->get_type()->clone(); 275 adjustExprType( adjType, newEnv, resn.indexer ); 276 renameTyVars( adjType ); 277 278 // keep unifying candidates 279 if ( unify( assn.decl->get_type(), adjType, newEnv, newNeed, have, newOpenVars, 280 resn.indexer ) ) { 281 // set up binding slot for recursive assertions 282 UniqueId crntResnSlot = 0; 283 if ( ! newNeed.empty() ) { 284 crntResnSlot = ++globalResnSlot; 285 for ( auto& a : newNeed ) { 286 a.second.resnSlot = crntResnSlot; 287 } 240 // lookup candidates for this assertion 241 std::list< SymTab::Indexer::IdData > candidates; 242 resn.indexer.lookupId( assn.decl->name, candidates ); 243 244 // find the candidates that unify with the desired type 245 CandidateList matches; 246 for ( const auto& cdata : candidates ) { 247 DeclarationWithType* candidate = cdata.id; 248 249 // build independent unification context for candidate 250 AssertionSet have, newNeed; 251 TypeEnvironment newEnv{ resn.alt.env }; 252 OpenVarSet newOpenVars{ resn.alt.openVars }; 253 Type* adjType = candidate->get_type()->clone(); 254 adjustExprType( adjType, newEnv, resn.indexer ); 255 renameTyVars( adjType ); 256 257 // keep unifying candidates 258 if ( unify( assn.decl->get_type(), adjType, newEnv, newNeed, have, newOpenVars, 259 resn.indexer ) ) { 260 // set up binding slot for recursive assertions 261 UniqueId crntResnSlot = 0; 262 if ( ! newNeed.empty() ) { 263 crntResnSlot = ++globalResnSlot; 264 for ( auto& a : newNeed ) { 265 a.second.resnSlot = crntResnSlot; 288 266 } 289 290 matches.emplace_back( cdata, adjType, std::move(newEnv), std::move(have), 291 std::move(newNeed), std::move(newOpenVars), crntResnSlot ); 292 } else { 293 delete adjType; 294 } 267 } 268 // // set up idChain on new assertions 269 // for ( auto& a : newNeed ) { 270 // a.second.idChain = assn.info.idChain; 271 // a.second.idChain.push_back( assn.decl->get_uniqueId() ); 272 // } 273 274 matches.emplace_back( cdata, adjType, std::move(newEnv), std::move(have), 275 std::move(newNeed), std::move(newOpenVars), crntResnSlot ); 276 } else { 277 delete adjType; 295 278 } 296 297 it = cache.emplace_hint( it, assnKey, AssnCacheItem{ std::move(matches) } ); 298 } 299 300 CandidateList& matches = it->second.matches; 279 } 301 280 302 281 // break if no suitable assertion … … 305 284 // defer if too many suitable assertions 306 285 if ( matches.size() > 1 ) { 307 it->second.deferIds.emplace_back( assn.decl, assn.info ); 308 resn.deferred.emplace_back( cache, assnKey ); 286 resn.deferred.emplace_back( assn.decl, assn.info, std::move(matches) ); 309 287 return true; 310 288 } … … 314 292 addToIndexer( match.have, resn.indexer ); 315 293 resn.newNeed.insert( match.need.begin(), match.need.end() ); 316 resn.alt.env = match.env;317 resn.alt.openVars = match.openVars;294 resn.alt.env = std::move(match.env); 295 resn.alt.openVars = std::move(match.openVars); 318 296 319 297 bindAssertion( assn.decl, assn.info, resn.alt, match, resn.inferred ); … … 376 354 ResnList resns{ ResnState{ alt, root_indexer } }; 377 355 ResnList new_resns{}; 378 AssnCache assnCache;379 356 380 357 // resolve assertions in breadth-first-order up to a limited number of levels deep … … 385 362 for ( auto& assn : resn.need ) { 386 363 // fail early if any assertion is not resolvable 387 if ( ! resolveAssertion( assn, resn , assnCache) ) goto nextResn;364 if ( ! resolveAssertion( assn, resn ) ) goto nextResn; 388 365 } 389 366 … … 396 373 } 397 374 } else { 398 // only resolve each deferred assertion once399 std::sort( resn.deferred.begin(), resn.deferred.end() );400 auto last = std::unique( resn.deferred.begin(), resn.deferred.end() );401 resn.deferred.erase( last, resn.deferred.end() );402 375 // resolve deferred assertions by mutual compatibility 403 376 std::vector<CandidateEnvMerger::OutType> compatible = filterCombos( … … 407 380 CandidateCost coster{ resn.indexer }; 408 381 std::sort( compatible.begin(), compatible.end(), coster ); 382 // // sort by cost if pruning 383 // if ( pruneAssertions ) { 384 // auto lmin = sort_mins( compatible.begin(), compatible.end(), 385 // CandidateCost{resn.indexer} ); 386 // compatible.erase( lmin, compatible.end() ); 387 // } 409 388 410 389 // keep map of detected options … … 429 408 new_resn.newNeed.insert( match.need.begin(), match.need.end() ); 430 409 431 // for each deferred assertion with the same form 432 for ( AssnId id : r.item.deferIds ) { 433 bindAssertion( 434 id.decl, id.info, new_resn.alt, match, new_resn.inferred ); 435 } 410 bindAssertion( r.decl, r.info, new_resn.alt, match, new_resn.inferred ); 436 411 } 437 412
Note: See TracChangeset
for help on using the changeset viewer.