Changes in / [73edfe9:a2a85658]
- Location:
- src
- Files:
-
- 5 edited
-
AST/porting.md (modified) (1 diff)
-
ResolvExpr/CandidateFinder.cpp (modified) (10 diffs)
-
ResolvExpr/RenameVars.cc (modified) (1 diff)
-
ResolvExpr/RenameVars.h (modified) (1 diff)
-
ResolvExpr/ResolveAssertions.cc (modified) (9 diffs)
Legend:
- Unmodified
- Added
- Removed
-
src/AST/porting.md
r73edfe9 ra2a85658 305 305 * switched order of `env`, `symtab` parameters for better consistency 306 306 307 `findMinCost`308 * pulled out conversion cost promotion into separate `promoteCvtCost` function309 310 307 [1] https://gcc.gnu.org/onlinedocs/gcc-9.1.0/gcc/Type-Attributes.html#Type-Attributes 311 308 -
src/ResolvExpr/CandidateFinder.cpp
r73edfe9 ra2a85658 27 27 #include "Cost.h" 28 28 #include "ExplodedArg.hpp" 29 #include "RenameVars.h" // for renameTyVars30 29 #include "Resolver.h" 31 30 #include "ResolveTypeof.h" … … 558 557 559 558 /// Generate a cast expression from `arg` to `toType` 560 const ast::Expr * restructureCast( 561 ast::ptr< ast::Expr > & arg, const ast::Type * toType, ast::GeneratedFlag isGenerated 562 ) { 563 if ( 564 arg->result->size() > 1 565 && ! toType->isVoid() 566 && ! dynamic_cast< const ast::ReferenceType * >( toType ) 567 ) { 568 // Argument is a tuple and the target type is neither void nor a reference. Cast each 569 // member of the tuple to its corresponding target type, producing the tuple of those 570 // cast expressions. If there are more components of the tuple than components in the 571 // target type, then excess components do not come out in the result expression (but 572 // UniqueExpr ensures that the side effects will still be produced) 573 if ( Tuples::maybeImpureIgnoreUnique( arg ) ) { 574 // expressions which may contain side effects require a single unique instance of 575 // the expression 576 arg = new ast::UniqueExpr{ arg->location, arg }; 577 } 578 std::vector< ast::ptr< ast::Expr > > components; 579 for ( unsigned i = 0; i < toType->size(); ++i ) { 580 // cast each component 581 ast::ptr< ast::Expr > idx = new ast::TupleIndexExpr{ arg->location, arg, i }; 582 components.emplace_back( 583 restructureCast( idx, toType->getComponent( i ), isGenerated ) ); 584 } 585 return new ast::TupleExpr{ arg->location, move( components ) }; 586 } else { 587 // handle normally 588 return new ast::CastExpr{ arg->location, arg, toType, isGenerated }; 589 } 590 } 591 592 /// Gets the name from an untyped member expression (must be NameExpr) 593 const std::string & getMemberName( const ast::UntypedMemberExpr * memberExpr ) { 594 if ( memberExpr->member.as< ast::ConstantExpr >() ) { 595 SemanticError( memberExpr, "Indexed access to struct fields unsupported: " ); 596 } 597 598 return memberExpr->member.strict_as< ast::NameExpr >()->name; 559 const ast::Expr * restructureCast( const ast::Expr * arg, const ast::Type * toType, bool isGenerated ) { 560 #warning unimplemented 561 (void)arg; (void)toType; (void)isGenerated; 562 assert(false); 563 return nullptr; 599 564 } 600 565 … … 799 764 800 765 if ( auto structInst = aggrExpr->result.as< ast::StructInstType >() ) { 801 addAggMembers( structInst, aggrExpr, *cand, Cost::safe, "" );766 addAggMembers( structInst, aggrExpr, cand, Cost::safe, "" ); 802 767 } else if ( auto unionInst = aggrExpr->result.as< ast::UnionInstType >() ) { 803 addAggMembers( unionInst, aggrExpr, *cand, Cost::safe, "" );768 addAggMembers( unionInst, aggrExpr, cand, Cost::safe, "" ); 804 769 } 805 770 } … … 808 773 void addAggMembers( 809 774 const ast::ReferenceToType * aggrInst, const ast::Expr * expr, 810 const Candidate & cand, const Cost & addedCost, const std::string & name775 const CandidateRef & cand, const Cost & addedCost, const std::string & name 811 776 ) { 812 777 for ( const ast::Decl * decl : aggrInst->lookup( name ) ) { 813 778 auto dwt = strict_dynamic_cast< const ast::DeclWithType * >( decl ); 814 779 CandidateRef newCand = std::make_shared<Candidate>( 815 cand, new ast::MemberExpr{ expr->location, dwt, expr }, addedCost );780 *cand, new ast::MemberExpr{ expr->location, dwt, expr }, addedCost ); 816 781 // add anonymous member interpretations whenever an aggregate value type is seen 817 782 // as a member expression 818 783 addAnonConversions( newCand ); 819 784 candidates.emplace_back( move( newCand ) ); 820 }821 }822 823 /// Adds tuple member interpretations824 void addTupleMembers(825 const ast::TupleType * tupleType, const ast::Expr * expr, const Candidate & cand,826 const Cost & addedCost, const ast::Expr * member827 ) {828 if ( auto constantExpr = dynamic_cast< const ast::ConstantExpr * >( member ) ) {829 // get the value of the constant expression as an int, must be between 0 and the830 // length of the tuple to have meaning831 long long val = constantExpr->intValue();832 if ( val >= 0 && (unsigned long long)val < tupleType->size() ) {833 addCandidate(834 cand, new ast::TupleIndexExpr{ expr->location, expr, (unsigned)val },835 addedCost );836 }837 785 } 838 786 } … … 1052 1000 } 1053 1001 1054 // select first on argument cost, then conversion cost 1055 CandidateList minArgCost = findMinCost( matches ); 1056 promoteCvtCost( minArgCost ); 1057 candidates = findMinCost( minArgCost ); 1002 // castExpr->result should be replaced with toType 1003 // candidates => matches 1004 1005 #warning unimplemented 1006 (void)castExpr; 1007 assert(false); 1058 1008 } 1059 1009 … … 1071 1021 1072 1022 void postvisit( const ast::UntypedMemberExpr * memberExpr ) { 1073 CandidateFinder aggFinder{ symtab, tenv }; 1074 aggFinder.find( memberExpr->aggregate, ResolvMode::withAdjustment() ); 1075 for ( CandidateRef & agg : aggFinder.candidates ) { 1076 // it's okay for the aggregate expression to have reference type -- cast it to the 1077 // base type to treat the aggregate as the referenced value 1078 Cost addedCost = Cost::zero; 1079 agg->expr = referenceToRvalueConversion( agg->expr, addedCost ); 1080 1081 // find member of the given type 1082 if ( auto structInst = agg->expr->result.as< ast::StructInstType >() ) { 1083 addAggMembers( 1084 structInst, agg->expr, *agg, addedCost, getMemberName( memberExpr ) ); 1085 } else if ( auto unionInst = agg->expr->result.as< ast::UnionInstType >() ) { 1086 addAggMembers( 1087 unionInst, agg->expr, *agg, addedCost, getMemberName( memberExpr ) ); 1088 } else if ( auto tupleType = agg->expr->result.as< ast::TupleType >() ) { 1089 addTupleMembers( tupleType, agg->expr, *agg, addedCost, memberExpr->member ); 1090 } 1091 } 1023 #warning unimplemented 1024 (void)memberExpr; 1025 assert(false); 1092 1026 } 1093 1027 … … 1096 1030 } 1097 1031 1098 void postvisit( const ast::NameExpr * nameExpr ) { 1099 std::vector< ast::SymbolTable::IdData > declList = symtab.lookupId( nameExpr->name ); 1100 PRINT( std::cerr << "nameExpr is " << nameExpr->name << std::endl; ) 1101 for ( auto & data : declList ) { 1102 Cost cost = Cost::zero; 1103 ast::Expr * newExpr = data.combine( nameExpr->location, cost ); 1104 1105 CandidateRef newCand = std::make_shared<Candidate>( 1106 newExpr, copy( tenv ), ast::OpenVarSet{}, ast::AssertionSet{}, Cost::zero, 1107 cost ); 1108 PRINT( 1109 std::cerr << "decl is "; 1110 ast::print( std::cerr, data.id ); 1111 std::cerr << std::endl; 1112 std::cerr << "newExpr is "; 1113 ast::print( std::cerr, newExpr ); 1114 std::cerr << std::endl; 1115 ) 1116 newCand->expr = ast::mutate_field( 1117 newCand->expr.get(), &ast::Expr::result, 1118 renameTyVars( newCand->expr->result ) ); 1119 // add anonymous member interpretations whenever an aggregate value type is seen 1120 // as a name expression 1121 addAnonConversions( newCand ); 1122 candidates.emplace_back( move( newCand ) ); 1123 } 1032 void postvisit( const ast::NameExpr * variableExpr ) { 1033 #warning unimplemented 1034 (void)variableExpr; 1035 assert(false); 1124 1036 } 1125 1037 … … 1136 1048 1137 1049 void postvisit( const ast::SizeofExpr * sizeofExpr ) { 1138 if ( sizeofExpr->type ) { 1139 addCandidate( 1140 new ast::SizeofExpr{ 1141 sizeofExpr->location, resolveTypeof( sizeofExpr->type, symtab ) }, 1142 tenv ); 1143 } else { 1144 // find all candidates for the argument to sizeof 1145 CandidateFinder finder{ symtab, tenv }; 1146 finder.find( sizeofExpr->expr ); 1147 // find the lowest-cost candidate, otherwise ambiguous 1148 CandidateList winners = findMinCost( finder.candidates ); 1149 if ( winners.size() != 1 ) { 1150 SemanticError( 1151 sizeofExpr->expr.get(), "Ambiguous expression in sizeof operand: " ); 1152 } 1153 // return the lowest-cost candidate 1154 CandidateRef & choice = winners.front(); 1155 choice->expr = referenceToRvalueConversion( choice->expr, choice->cost ); 1156 choice->cost = Cost::zero; 1157 addCandidate( *choice, new ast::SizeofExpr{ sizeofExpr->location, choice->expr } ); 1158 } 1050 #warning unimplemented 1051 (void)sizeofExpr; 1052 assert(false); 1159 1053 } 1160 1054 1161 1055 void postvisit( const ast::AlignofExpr * alignofExpr ) { 1162 if ( alignofExpr->type ) { 1163 addCandidate( 1164 new ast::AlignofExpr{ 1165 alignofExpr->location, resolveTypeof( alignofExpr->type, symtab ) }, 1166 tenv ); 1167 } else { 1168 // find all candidates for the argument to alignof 1169 CandidateFinder finder{ symtab, tenv }; 1170 finder.find( alignofExpr->expr ); 1171 // find the lowest-cost candidate, otherwise ambiguous 1172 CandidateList winners = findMinCost( finder.candidates ); 1173 if ( winners.size() != 1 ) { 1174 SemanticError( 1175 alignofExpr->expr.get(), "Ambiguous expression in alignof operand: " ); 1176 } 1177 // return the lowest-cost candidate 1178 CandidateRef & choice = winners.front(); 1179 choice->expr = referenceToRvalueConversion( choice->expr, choice->cost ); 1180 choice->cost = Cost::zero; 1181 addCandidate( 1182 *choice, new ast::AlignofExpr{ alignofExpr->location, choice->expr } ); 1183 } 1056 #warning unimplemented 1057 (void)alignofExpr; 1058 assert(false); 1184 1059 } 1185 1060 1186 1061 void postvisit( const ast::UntypedOffsetofExpr * offsetofExpr ) { 1187 const ast::ReferenceToType * aggInst; 1188 if (( aggInst = offsetofExpr->type.as< ast::StructInstType >() )) ; 1189 else if (( aggInst = offsetofExpr->type.as< ast::UnionInstType >() )) ; 1190 else return; 1191 1192 for ( const ast::Decl * member : aggInst->lookup( offsetofExpr->member ) ) { 1193 auto dwt = strict_dynamic_cast< const ast::DeclWithType * >( member ); 1194 addCandidate( 1195 new ast::OffsetofExpr{ offsetofExpr->location, aggInst, dwt }, tenv ); 1196 } 1062 #warning unimplemented 1063 (void)offsetofExpr; 1064 assert(false); 1197 1065 } 1198 1066 … … 1271 1139 common ) 1272 1140 ) { 1273 // generate typed expression 1274 ast::ConditionalExpr * newExpr = new ast::ConditionalExpr{ 1275 conditionalExpr->location, r1->expr, r2->expr, r3->expr }; 1276 newExpr->result = common ? common : r2->expr->result; 1277 // convert both options to result type 1278 Cost cost = r1->cost + r2->cost + r3->cost; 1279 newExpr->arg2 = computeExpressionConversionCost( 1280 newExpr->arg2, newExpr->result, symtab, env, cost ); 1281 newExpr->arg3 = computeExpressionConversionCost( 1282 newExpr->arg3, newExpr->result, symtab, env, cost ); 1283 // output candidate 1284 CandidateRef newCand = std::make_shared<Candidate>( 1285 newExpr, move( env ), move( open ), move( need ), cost ); 1286 inferParameters( newCand, candidates ); 1141 #warning unimplemented 1142 assert(false); 1287 1143 } 1288 1144 } … … 1342 1198 common ) 1343 1199 ) { 1344 // generate new expression1345 1200 ast::RangeExpr * newExpr = 1346 1201 new ast::RangeExpr{ rangeExpr->location, r1->expr, r2->expr }; 1347 1202 newExpr->result = common ? common : r1->expr->result; 1348 // add candidate 1349 CandidateRef newCand = std::make_shared<Candidate>( 1350 newExpr, move( env ), move( open ), move( need ), 1351 r1->cost + r2->cost ); 1352 inferParameters( newCand, candidates ); 1203 1204 #warning unimplemented 1205 assert(false); 1353 1206 } 1354 1207 } -
src/ResolvExpr/RenameVars.cc
r73edfe9 ra2a85658 96 96 } 97 97 } // namespace 98 99 const ast::Type * renameTyVars( const ast::Type * t ) {100 #warning unimplemented; make sure resetTyVarRenaming() updated when implemented101 (void)t;102 assert(false);103 return t;104 }105 98 } // namespace ResolvExpr 106 99 -
src/ResolvExpr/RenameVars.h
r73edfe9 ra2a85658 23 23 #include "SynTree/Visitor.h" // for Visitor 24 24 25 namespace ast {26 class Type;27 }28 29 25 namespace ResolvExpr { 30 26 /// Provides a consistent renaming of forall type names in a hierarchy by prefixing them with a unique "level" ID 31 27 void renameTyVars( Type * ); 32 const ast::Type * renameTyVars( const ast::Type * );33 28 34 29 /// resets internal state of renamer to avoid overflow -
src/ResolvExpr/ResolveAssertions.cc
r73edfe9 ra2a85658 186 186 using InferCache = std::unordered_map< UniqueId, InferredParams >; 187 187 188 /// Lexicographically-ordered vector of costs189 using CostVec = std::vector< Cost >;190 191 int compare( const CostVec & a, const CostVec & b ) {192 unsigned i = 0;193 do {194 // lex-compare where shorter one is less195 if ( i == a.size() ) {196 return i == b.size() ? 0 : -1;197 }198 if ( i == b.size() /* && i < a.size() */ ) return 1;199 200 int c = a[i].compare( b[i] );201 if ( c != 0 ) return c;202 } while ( ++i );203 assert(!"unreachable");204 }205 206 bool operator< ( const CostVec & a, const CostVec & b ) { return compare( a, b ) < 0; }207 208 188 /// Flag for state iteration 209 189 enum IterateFlag { IterateState }; … … 216 196 DeferList deferred; ///< Deferred matches 217 197 InferCache inferred; ///< Cache of already-inferred parameters 218 CostVec costs; ///< Costs of recursive assertion satisfaction for disambiguation219 198 SymTab::Indexer& indexer; ///< Name lookup (depends on previous assertions) 220 199 221 200 /// Initial resolution state for an alternative 222 201 ResnState( Alternative& a, SymTab::Indexer& indexer ) 223 : alt(a), need(), newNeed(), deferred(), inferred(), costs{ Cost::zero },indexer(indexer) {202 : alt(a), need(), newNeed(), deferred(), inferred(), indexer(indexer) { 224 203 need.swap( a.need ); 225 204 } … … 228 207 ResnState( ResnState&& o, IterateFlag ) 229 208 : alt(std::move(o.alt)), need(o.newNeed.begin(), o.newNeed.end()), newNeed(), deferred(), 230 inferred(std::move(o.inferred)), costs(o.costs), indexer(o.indexer) { 231 costs.emplace_back( Cost::zero ); 232 } 209 inferred(std::move(o.inferred)), indexer(o.indexer) {} 233 210 }; 234 211 … … 359 336 }; 360 337 361 /// Map of alternative return types to recursive assertion satisfaction costs 362 using PruneMap = std::unordered_map<std::string, CostVec>; 363 364 /// Gets the pruning key for an alternative 365 std::string pruneKey( const Alternative & alt ) { 366 Type* resType = alt.expr->result->clone(); 367 alt.env.apply( resType ); 368 std::string resKey = SymTab::Mangler::mangleType( resType ); 369 delete resType; 370 return std::move( resKey ); 371 } 372 373 /// Replace resnSlots with inferParams and add alternative to output list, if meets pruning 374 /// threshold. 375 void finalizeAssertions( ResnState& resn, PruneMap & pruneThresholds, AltList& out ) { 376 // prune if cheaper alternative for same key has already been generated 377 std::string resKey = pruneKey( resn.alt ); 378 auto it = pruneThresholds.find( resKey ); 379 if ( it != pruneThresholds.end() ) { 380 if ( it->second < resn.costs ) return; 381 } else { 382 pruneThresholds.emplace_hint( it, resKey, resn.costs ); 383 } 384 385 // replace resolution slots with inferred params, add to output 386 PassVisitor<InferMatcher> matcher{ resn.inferred }; 387 resn.alt.expr = resn.alt.expr->acceptMutator( matcher ); 388 out.emplace_back( resn.alt ); 338 void finalizeAssertions( Alternative& alt, InferCache& inferred, AltList& out ) { 339 PassVisitor<InferMatcher> matcher{ inferred }; 340 alt.expr = alt.expr->acceptMutator( matcher ); 341 out.emplace_back( alt ); 389 342 } 390 343 … … 406 359 ResnList resns{ ResnState{ alt, root_indexer } }; 407 360 ResnList new_resns{}; 408 409 // Pruning thresholds by result type of the output alternatives.410 // Alternatives *should* be generated in sorted order, so no need to retroactively prune411 PruneMap thresholds;412 361 413 362 // resolve assertions in breadth-first-order up to a limited number of levels deep … … 415 364 // scan over all mutually-compatible resolutions 416 365 for ( auto& resn : resns ) { 417 // stop this branch if already found a better option418 auto it = thresholds.find( pruneKey( resn.alt ) );419 if ( it != thresholds.end() && it->second < resn.costs ) goto nextResn;420 421 366 // make initial pass at matching assertions 422 367 for ( auto& assn : resn.need ) { … … 438 383 // either add successful match or push back next state 439 384 if ( resn.newNeed.empty() ) { 440 finalizeAssertions( resn , thresholds, out );385 finalizeAssertions( resn.alt, resn.inferred, out ); 441 386 } else { 442 387 new_resns.emplace_back( std::move(resn), IterateState ); … … 475 420 goto nextResn; 476 421 } 477 // sort by cost for overall pruning422 // sort by cost 478 423 CandidateCost coster{ resn.indexer }; 479 424 std::sort( compatible.begin(), compatible.end(), coster ); 480 425 426 // keep map of detected options 427 std::unordered_map<std::string, Cost> found; 481 428 for ( auto& compat : compatible ) { 429 // filter by environment-adjusted result type, keep only cheapest option 430 Type* resType = alt.expr->result->clone(); 431 compat.env.apply( resType ); 432 // skip if cheaper alternative already processed with same result type 433 Cost resCost = coster.get( compat ); 434 auto it = found.emplace( SymTab::Mangler::mangleType( resType ), resCost ); 435 delete resType; 436 if ( it.second == false && it.first->second < resCost ) continue; 437 438 // proceed with resolution step 482 439 ResnState new_resn = resn; 483 440 … … 495 452 new_resn.alt.openVars = std::move(compat.openVars); 496 453 497 // mark cost of this path498 new_resn.costs.back() += compat.cost;499 500 454 // either add sucessful match or push back next state 501 455 if ( new_resn.newNeed.empty() ) { 502 finalizeAssertions( new_resn , thresholds, out );456 finalizeAssertions( new_resn.alt, new_resn.inferred, out ); 503 457 } else { 504 458 new_resns.emplace_back( std::move(new_resn), IterateState );
Note: See TracChangeset
for help on using the changeset viewer.
