Allow cycles to be recorded as a TODO

[alexevanczuk]

Summary

This discussion proposes storing cycles as a TODO item to permit more observable and gradual cycle reduction.

When, where, and how should the TODO be recorded?

• When: It seems like this should be recorded during bin/packwerk update-todo. bin/packwerk validate could change to make it clear we're talking about new cycles and that you can store new cycles as TODOs with update.
• Where: No single package is uniquely responsible for the cycle (as can be determined statically), so it doesn't clearly fit into a single pack's TODO file. I wonder if a single file (e.g. /.package_cycles_todo.yml) should hold all of them.
• How: Using the existing output of bin/packwerk validate (slightly modified to be more serializable as YML) seems fine – is there an alternate format of cycles that is more useful?

Advantages

Observability

• makes the dependency graph cycle elimination process generally observable. You’d be able to see and discuss cycles via GitHub links. Right now it’s totally opaque — it only shows up after adding a bad dependency and running validate. There is no forum to see and talk about then.
• It makes it specifically observable. Can see how PRs add new cycles.

Waste Reduction

• Today, when resolving dependency violations, folks sometimes attempt to add the dependency, only to receive a message (usually in CI, sometimes locally if they're using bin/packs add_dependency) that there is a validation (cycle) error. Then they remove the dependency until the next time someone else encounters the same issue. With this, there is much less waste since someone adds it once, uses their usual bin/packwerk validate command, and can then commit the cycle TODO.

More Gradual

• It makes the process more gradual — now you can work through cycles as a systematic process.

Disadvantages

Loss of constraints and meaningfulness of dependencies

The main thing I see now is that cycles in dependencies are possible, which was never possible before. It was kind of an interesting invariant that dependencies formed an acyclic graph, but I'm not sure if it was a useful invariant. This approach loosens this constraint and makes "violations" of that constraint visible. Furthermore, we could enable this via a flag in packwerk.yml so folks can keep the old behavior if they want.

It could even be possible to have cycle detection itself be a checker that can be turned on/off per package, e.g. enforce_acyclicity (defaults to value of enforce_dependencies). If it's on, the package cannot be a part of any cycle. This could be an interesting way to allow a package to prevent this feature from causing entanglement.

Noise from too many cycles

It's possible folks would use the cycle TODO list by just adding to it, as a shift from using the package TODO

I used a small script in Gusto's monolith to add all dependencies necessary to remove all dependency violations to establish an upper bound on cycles and saw there are still fewer cycles than dependency violations, so there should always be less noise by recording cycles (especially since I don't see folks adding all dependencies).

Feedback

Let me know what you think and what I might be missing!

Related discussions:

• Disable the "acyclic dependency graph" check? #313
• Add 'ignored_dependencies' option for package.yml files to incrementally adopt dependency protection #350 (comment)

[mclark]

This idea makes a lot of sense to me. Most (all?) of us are coming from giant ball of mud monoliths, attempting to chunk things down into more manageable portions. As these "chunks" were previously all part of the same big ball of mud, they will naturally have plenty of circular dependencies as boundaries were never a thing until the chunking process began. Circular dependencies of this nature are big problems that we want to fix, but can live with "for now". They are a perfect fit for package_todo.yml files for this reason.

Anecdotally speaking, bringing visibility to circular dependencies will help teams prioritize decomposition work. If these problems are not visible, they aren't prioritized and therefore never done.

Ok so now that I've established my high level agreement, I'll dive into some of the details presented with potentially more contentious opinions.

Where?

If a package participates in a circular dependency chain, then it owns the problem along with all other participating packages. Storing these violations in a global package_cycles_todo.yml file will ensure no one owns the problem and is akin to the current situation of not storing them anywhere.

Loss of acyclic meaning for dependencies

At GitHub, we currently report all actual dependencies and use Packwerk to identify and eliminate those we don't want and to ensure we don't add more that we don't intend. The package dependencies we have look like a mess in a graph, but we prefer to report the actual state of things.

To do this, we actually don't run packwerk validate in CI. So for us, this proposal is a win/win as we'll be able to start using packwerk validate in CI and teams can prioritize this important work due to the increased visibility.

[alexevanczuk]

If a package participates in a circular dependency chain, then it owns the problem along with all other participating packages.

Interesting – so you're saying if there is a chain of 10 packages, we'd want to store that chain 10 times in each package's package_todo.yml? I definitely understand the idea behind this, my only concern is that this has the potential to really blow up the TODO files. I updated my gist with a script that looks at how many TODOs are added each time a sample of dependencies are added if we were to store the cycle N times (once for each package that participates in the cycle). Due to the number of cycles and amount of noise it'd add, it changes the calculus a bit on whether folks would use cycle TODOs often at Gusto, but maybe that's okay.

However, if at GitHub, you store all of the actual dependencies, you might find that the amount of new stored TODOs you see is a bit untenable given that suggested format – might be worth calculating that number.

[shageman]

I have a hunch we are more interested in recording strongly connected components rather then (all) cycles.

I am torn on package-local recording vs a global cycle / strongly connected component recording. If we could go with the latter, package-local feels possible. And I would like it better: Imagine adding to a 50 package strongly connected component vs 3 or 4... In one case your PR changes 50 files and packages, in the other only three. I.e., the pain of the PR is correlated to the size of the pain you are creating.

Side note: Packwerk's cycle detection is currently not correct / exhaustive (all except one 3 node subcycles are missing):

    test "#cycles returns cycles in a graph with disjoint subgraphs" do
      graph = Graph.new([
        [1, 2], [1, 3], [1, 4],
        [2, 1], [2, 3], [2, 4],
        [3, 1], [3, 2], [3, 4],
        [4, 1], [4, 2], [4, 3],
      ])

      assert_equal graph.cycles, []
    end

[exterm]

At GitHub, we currently report all actual dependencies and use Packwerk to identify and eliminate those we don't want

@mclark You mean you have put all actual dependencies into the package.yml files? How do you then use packwerk to identify those you don't want?

[mclark]

How do you then use packwerk to identify those you don't want?

When we have identified a dependency we want to remove, we remove it from the package.yml file, which of course causes all the violations to be recorded in package_todo.yml.

[exterm]

ah. Looks like there ought to be three categories:

• intended dependencies
• unintended dependencies we want to ignore for now
• unintended dependencies we want to work on removing right now

In that case, I think Alex' now closed PR is a better solution than this proposal, and I added a comment to that effect.

[exterm]

While I agree it would be nice to have some kind of TODO list for cycles that exist in actual dependencies, I don't think we should have TODO list entries for the dependencies specified in package.yml files. The dependencies in those files are intended to express a desired end state.

It makes no sense whatsoever to me to have a desired end state that contains cycles.

makes "violations" of that constraint visible

We could still do that by highlighting cycles in actual dependencies somewhere. That doesn't require any changes to the acyclicity check on desired dependencies.

I really think it is important to preserve a clean separation between current state and desired end state. Changing the desired end state changes what actual dependencies are listed in the package todo files. It makes no sense to me to derive that information from something that is closer to an actual state. To illustrate: If we listed all actual dependencies in package.yml files there would be no dependency violations left at all.

[exterm]

Added a comment to the PR with Alex' previous proposal - TL;DR: I think that one is a better solution.

[mclark]

TIL we have been using Packwerk dependencies incorrectly 🙈

There appear to be a couple different perspectives of looking at this. At GitHub we have been recording all the actual dependencies, meaning there are no dependency violations at all until you decide to start work on removing one. This means generated dependency graphs show the complete mess of dependencies in our monolith. This is also why we just skip the validation check as it's full of circular dependency errors.

I can now see why this notion of "ignored dependencies" has been tossed around for so long. If you have "aspirational dependencies" indicating the desired dependencies and "ignored dependencies" indicating the dependencies you don't want to deal with now, you are left with the dependency violations you wish to burn down in the near term future. Sort of like how we just remove a dependency from our dependency list.

Instead of needing "ignored dependencies", GitHub just foregoes having a list of "aspirational dependencies" at all. But I believe it would be nice to have. So to flip this around, instead of adding ignored_dependencies, we could instead add target_dependencies and tweak the meaning of dependencies to mean "actual dependencies". circular dependency validations could then just ensure the target dependencies aren't circular.

In the end this doesn't actually buy us anything over the proposal here. It's just another way of naming things. Regardless, thanks for the context @exterm!

[exterm]

I always thought packwerk would over time evolve to support more of a full fledged architecture definition language, allowing you to define a more detailed set of rules around the dependency graph, and then help you move towards that.

There would be concrete rules like "code in package A is allowed to depend on code in package B", and meta rules like "packages in this layer are only allowed to depend on packages in layers below".

You express a target architecture and packwerk helps you move towards that.

That strategy is already possible with packwerk, albeit with limitations (no meta rules), and it seems that it isn't very clear that that's the intended use.

BTW - I don't think there is "using it wrong", there is just "using it in unexpected ways" 😉

[exterm]

Actually - there is one meta-rule, and it is hardcoded - the cyclic dependency check.

[exterm]

Meta rules a la Gusto: https://github.com/rubyatscale/packwerk-extensions#architecture-checker

Pretty cool.