Severance

Inspiration

Every codebase grows dependency cycles, and the standard advice, just break the cycle, skips the only hard question, which is where to cut. I've cut the wrong edge before. It looked like one clean edge on the diagram, so I cut it, and then I spent a sprint untangling the backbone two modules depended on, because that one edge carried five different calls. The smallest cut to draw is almost never the cheapest cut to actually do. I wanted the cheapest one computed for me, with the call counts factored in, instead of squinting at a diagram and guessing.

What it does

Severance finds the dependency cycles in your codebase and tells you the cheapest set of imports to delete to break them. Cheap means the fewest real calls you have to rewrite, not the fewest edges to draw. Then it renders the before and after as a Mermaid diagram right in a GitLab issue: the cycle, and then the same graph with the cut made and visibly acyclic.

On my demo, a rewards package has a cycle. The obvious fix cuts one edge, engine to catalog, but that edge is the backbone and it is called in 5 places. Severance instead cuts two back edges that are called once each, so it is the same result for less than half the refactoring work. The naive cut and the cheap cut point at different edges, and the cheap one is the one you want.

How we built it

This is the one I went deepest on, and it is pure standard library, no graph package.

It reads the call graph from Orbit, weighting each module to module edge by how many distinct functions make the call. Those counts are the whole reason the cheap cut is findable, since an import scanner can tell you an edge exists but not how heavily it is used. It finds the cycles with Tarjan's algorithm, written iteratively so a big repo can't blow the stack. Then for each strongly connected component it solves the weighted minimum feedback arc set, which is the formal name for "cheapest edges to remove to kill all the cycles."

That last part is NP-hard, so how you solve it matters. I reduced it to a minimum-weight hitting set over the elementary cycles, which is exact rather than approximate, because a set of edges breaks every cycle if and only if it hits every cycle. Then I solve that with branch and bound, using a lower bound built from a packing of edge-disjoint cycles. Disjoint cycles need disjoint edges to cut, so the sum of their cheapest edges can never be more than the true optimum, which means the bound is safe to prune with and never throws the real answer away. A greedy bound could overshoot and quietly drop the optimum while still printing the word optimal, and that is the one thing this tool must never do.

To keep it honest, the branch and bound is checked against brute force, an exhaustive subset search, on hundreds of random graphs in the test suite, so optimal is something I prove, not something I claim. For inputs too big to solve exactly, strongly connected components past 18 nodes or 4,000 cycles, it falls back to a clearly labelled heuristic and says so, instead of pretending.

Challenges we ran into

Getting the lower bound right. The first bound I tried was greedy and occasionally optimistic, which meant branch and bound could prune the actual best cut. That is the worst possible bug in a tool whose entire pitch is "provably optimal," and it taught me to prove a bound is admissible before trusting it.

The ImportedSymbol weights. Like my other tools, cross module calls in Orbit go through ImportedSymbol, and here I needed more than whether an edge exists, I needed how many functions use it, since that is the weight. Aggregating that correctly per module took some care.

Tarjan without recursion. Recursive Tarjan is short and clean and will overflow the stack on a large repo, so I rewrote it as an explicit stack machine, which is fiddlier but survives real input.

Proving I was right without hand waving. I did not want to ship "trust me, it's optimal," so the brute force oracle in the tests runs on enough random strongly connected graphs that a wrong answer would show up fast.

Accomplishments that we're proud of

It is exact, and I can show why, not just that it passes tests. The reduction is exact, the bound is admissible, and there is a short proof of both written out.

It is checked against brute force on hundreds of graphs, all in the standard library, and it stays fast on the cycle sizes real codebases actually have, a few modules, solved in well under 10 milliseconds.

The output is a picture. The before and after Mermaid diptych makes the cut obvious to a human, rendered inline in the issue.

It never fakes optimality. Past its budget it switches to a clearly labelled heuristic.

What we learned

The hard part of an optimization tool is not the search, it is the bound, and an inadmissible bound is a silent correctness bug wearing a performance costume.

Edge weights change the answer. The unweighted minimum cut and the weighted minimum cut disagree on this demo, and the weighted one is the one that matters for real refactoring effort.

Orbit's call counts are what make the weighted version possible at all. Text level import parsing can't tell you how heavily an edge is used.

What's next for Severance

Suggesting the actual refactor, not just the edges: which import to invert or which interface to extract so the cut lands. Handling several overlapping cycles in one component with a single combined minimum cut across all of them, which is most of what the hitting set formulation already does. And a small benchmark artifact that shows branch and bound staying flat while brute force blows up, so the "why is this even hard" question answers itself.

Built With

• ai-catalog
• gitlab
• gitlab-ci-cd
• gitlab-duo-agent-platform
• gitlab-knowledge-graph
• glab
• mermaid
• mypy
• orbit
• pytest
• python
• rest-api
• ruff