davidlu1001
16 days ago
Author here. A few implementation notes:
1. We use NetworkX for the graph operations. Tarjan's SCC detection is O(V+E), so it scales well even for large accounts.
2. The trickiest part isn't the algorithm — it's mapping AWS API responses to graph edges. AWS APIs are... inconsistent. Some resources return IDs, some ARNs, some Names. Security Groups can reference themselves, reference by ID or by name, and have rules scattered across inline blocks and separate resources. Normalizing this soup into a clean adjacency matrix is where 80% of the engineering work lives.
3. For those wondering about the "Shell & Fill" naming: it's essentially forcing Terraform's create_before_destroy lifecycle behavior manually, by decoupling the resource identity from its configuration.
Would love to hear if others have hit similar graph problems with other IaC tools (Pulumi, CDK, CloudFormation).
talolard
16 days ago
Not IAC, but I’ve been doing a similar trick to sequence adding type annotations to python code,
Eg take the module graph, break the SCCs in a similar manner , then take a reverese topological sort of the imports (now a dag by construction).
davidlu1001
16 days ago
That's a spot-on parallel! Python circular imports (especially for type hinting) are basically the software equivalent of this infrastructure deadlock.
Do you use string-based forward references ("ClassName") to break the cycles? That's essentially our "empty shell" trick — decoupling the resource identity from its configuration to satisfy the graph.
Did you stick with Tarjan's for the SCC detection on the module graph?
talolard
15 days ago
I haven’t had major issues with sccs yet. The linter enforces forward references so the cycle pain we do have is with dynamic/deffered imports, and it’s usually solved by splitting a module.
If you look at the pyrefly repo (metas new type checker), there are some deep thoughts about sccs, but I didn’t fully grok them.
davidlu1001
15 days ago
Thanks for the Pyrefly pointer — I hadn't tracked Meta's Rust rewrite yet. Will dig into their SCC handling.
Your "splitting a module" framing is exactly right. In the IaC world, a Security Group with inline rules is like a Python module with circular imports — it couples identity with logic. The fix is the same: extract the logic into separate resources (or modules), keep the original as a pure identity/interface.
Interesting that the same pattern shows up in both compiler design and infrastructure tooling.