| 458 | } |
| 459 | |
| 460 | static void topoSortStructures ( vector<StructurePtr> & structs ) { |
| 461 | if ( structs.size() <= 1 ) return; |
| 462 | // build adjacency: struct -> set of structs it depends on (by value) |
| 463 | das_hash_map<Structure *, das_hash_set<Structure *>> deps; |
| 464 | das_hash_set<Structure *> allSet; |
| 465 | for ( auto & sp : structs ) { |
| 466 | allSet.insert(sp); |
| 467 | } |
| 468 | for ( auto & sp : structs ) { |
| 469 | auto & d = deps[sp]; |
| 470 | for ( auto & field : sp->fields ) { |
| 471 | collectStructDeps(field.type, sp, d); |
| 472 | } |
| 473 | // only keep deps that are in our set |
| 474 | das_hash_set<Structure *> filtered; |
| 475 | for ( auto dep : d ) { |
| 476 | if ( allSet.count(dep) ) filtered.insert(dep); |
| 477 | } |
| 478 | d = das::move(filtered); |
| 479 | } |
| 480 | // Kahn's algorithm using vector as queue |
| 481 | das_hash_map<Structure *, int> inDegree; |
| 482 | for ( auto & [s, dd] : deps ) { |
| 483 | inDegree[s] = (int)dd.size(); |
| 484 | } |
| 485 | vector<Structure *> sorted; |
| 486 | sorted.reserve(structs.size()); |
| 487 | // seed with zero-dependency structs |
| 488 | for ( auto & sp : structs ) { |
| 489 | if ( inDegree[sp] == 0 ) sorted.push_back(sp); |
| 490 | } |
| 491 | // process in FIFO order |
| 492 | for ( size_t qi = 0; qi < sorted.size(); qi++ ) { |
| 493 | auto s = sorted[qi]; |
| 494 | for ( auto & [other, dd] : deps ) { |
| 495 | if ( dd.erase(s) ) { |
| 496 | inDegree[other]--; |
| 497 | if ( inDegree[other] == 0 ) sorted.push_back(other); |
| 498 | } |
| 499 | } |
| 500 | } |
| 501 | if ( sorted.size() != structs.size() ) return; // cycle - keep original order |
| 502 | // reorder structs to match sorted order |
| 503 | das_hash_map<Structure *, StructurePtr> byPtr; |
| 504 | for ( auto & sp : structs ) byPtr[sp] = sp; |
| 505 | for ( size_t i = 0; i < sorted.size(); i++ ) { |
| 506 | structs[i] = byPtr[sorted[i]]; |
| 507 | } |
| 508 | } |
| 509 | |
| 510 | void Program::visitModule(Visitor & vis, Module * thatModule, bool visitGenerics, bool sortStructures) { |
| 511 | vis.preVisitModule(thatModule); |
no test coverage detected