Ignoring header dependencies when computing compile order

[jesperes]

Issue #2462 lead me to discover a problem which we don't really know how to tackle within the current bounds of what rebar can do, namely the fact that we have lots of "header dependency cycles", i.e. cycles where two or more applications include header files from each other. These are really harmless, but the problem is that they may cause rebar to discard the more important behavior and parse_transform dependencies. Example:

1. Rebar iterates through the edges of the dependency graph
2. Rebar discovers that A/src/a.erl includes B/include/b.hrl, marking A as having to be built before B.
3. Rebar discovers that B/src/bb.erl implements a behavior A/src/aa.erl. It attempts to add a compile-order dependency B -> A, but this fails because A already depends on B.

Since our use case is an old and large legacy monolith which has suffered from bad include-file discipline for years, we have lots of these cases where people include stuff all over the place, so we have quite a number of these header-file dependency cycles, and they cause Rebar to drop the more vital behavior dependencies when they are the once introducing a cycle.

My current workaround for this is to use a fork of rebar where compile-order only considers dependencies to .erl files, dropping once which refer to .hrl files. This seems to work well for us, but I'm not sure how acceptable this would be to backport upstreams.

[ferd]

The long term clean solution is rather (in my opinion) to extract things that are shared by multiple applications, and extract them into another application which the original users can then rely on to build. The cyclic dependencies across many apps tend to be a consequence of unclear ownership around definitions and business concerns.

Understandably, this is really complex and hard to fix after the fact, which is why Rebar3 always required this behaviour in dependencies. Our original use cases more or less omitted huge monolithic apps, and in my opinion, the proper policy that would fit rebar3's overall design to be most consistent would be to keep these forcing functions into the compiler's DAG handling to have a uniform policy in place: deps obey the same rules as top-level apps.

So the problem I see here is that allowing and absorbing workaround solutions for the sake of easing people's migrations still require adding code to support things in the same manner as if it were a fully-supported feature, which later down the road does limit the amount of things we can do in terms of migrations, optimizations and whatnot. It is code that adds complexity to the rebar3 codebase to allow external users to work-around theirs, but also code that under ideal principles is vowed to be removed as people should intend to clean up their design.

I realize this is a very opinionated stance that is not helpful for your specific case, since it's essentially saying "ideally you fix this yourself and we don't have to care about it here." I think some workarounds may make sense, but I really hate adding more and more features that have to get long-term support for projects we have no visibility into. Whatever we add would need to be minimal enough to have low overheads and to be easy to take out in isolation to be acceptable, so that we can clearly wall it off as a cognitive burden for maintenance.

A small one that could make sense is to look at the extension of some files when we find cross-application dependencies when we build the app sorting order, and process .erl file before .hrl files since the .erl files tend to be hard dependencies (behaviours and parse transforms) and .hrl files are not. The gotcha here is that the compiler does not currently make a distinction (or have information) about the context of what is a source or header file in the sorting function, and that the DAG structure is part of a public API so we can't just start annotating vertices for fun without breaking other compilers (we do have our own bad design and debt to carry; we could add artifact-tracking because we added new callbacks for them and can look at their presence to prevent introducing them when unsupported).

What we do have however is a context mapping that each compiler can carry, which could be passed around at the call-site. This will allow to provide a small heuristic, but will still represent a major edge case for things like LFE (.lfe extensions), whose files may still have a hard dependency on Erlang files (.erl) but won't sort them properly and will therefore see the same problem you're seeing here.

[jesperes]

The long term clean solution is rather (in my opinion) to extract things that are shared by multiple applications, and extract them into another application which the original users can then rely on to build. The cyclic dependencies across many apps tend to be a consequence of unclear ownership around definitions and business concerns.

In our case, yes. But also the fact that our current build system allows them, and what developers are permitted to do, they will do.

We even have some weird behavior-dependency cycles where it is impossible for rebar to compute a compile order. Our current build system (using Richard Carlssons stdapp.mk) builds everything in src/ first (across all applications), then proceeds to build everything under test/. So we've ended up with cases where B/test/b.erl uses behavior A/src/a.erl and A/test/aa.erl uses behavior B/src/bb.erl, causing a hard loop where neither A nor B can be built in its entirety, but needs to be split in two phases, src and test. Not sure if there is a way to make rebar behave like this; building all code in src/ first, then proceed to build test/? My guess is "no", but maybe there are some hidden capabilities in rebar I am not aware of.

I suspect that it is not worth the effort to bend rebar3 to do things it wasn't designed to do, so the behavior cycles across the src/test boundary will need to be refactored away.

So the problem I see here is that allowing and absorbing workaround solutions for the sake of easing people's migrations still require adding code to support things in the same manner as if it were a fully-supported feature, which later down the road does limit the amount of things we can do in terms of migrations, optimizations and whatnot. It is code that adds complexity to the rebar3 codebase to allow external users to work-around theirs, but also code that under ideal principles is vowed to be removed as people should intend to clean up their design.

I agree completely here.

I realize this is a very opinionated stance that is not helpful for your specific case, since it's essentially saying "ideally you fix this yourself and we don't have to care about it here." I think some workarounds may make sense, but I really hate adding more and more features that have to get long-term support for projects we have no visibility into. Whatever we add would need to be minimal enough to have low overheads and to be easy to take out in isolation to be acceptable, so that we can clearly wall it off as a cognitive burden for maintenance.

I think we can manage with a slightly patched rebar3 for the time being, mostly to be able to proceed working on other aspects of the migration to rebar3 and not being stuck on this particular issue.

Thanks!

[pergu]

I was looking in to this as well, and one solution that I came up with which is in a similar vein to what Jesper suggested is to treat dependencies on .hrl files differently from other files, instead of saying that app A has to be compiled after app B if a file V1 in A depends on .hrl file V2 in B we instead expand the dependencies for V2 to create the correct compile order.

The main reason I looked at this is that the compile order calculation is quite slow (especially for incremental compilation, about 40% of the time spent compiling our system when there has been no changes is spent in this calculation) By expanding the .hrls separately this goes down to < 5% . I can write a PR for it if you think it is ok.

[ferd]

I'm not sure I get what would be different there from say parse transforms or anything? Do you get an improvement running .hrls separately because you have more .hrls and that's just repo-specific?

[pergu]

The speedup results from having much fewer dependencies between apps (which matter for compilation order) when a dependency on an .hrl does not matter unless it has a transitive dependency on something which is not an .hrl.

What is slow in the current implementation is when there are lots of dependencies from files to files in other apps then lots of edges are added to the app dag (Most of them duplicates), and since the graph is acyclic the digraph module must check this on every insert, which makes it even slower (especially if there are cycles in the dependency graph)

The change described above fixes this by stopping most edges from being put in the graph (and also for removing most cycles)

[ferd]

Okay maybe there's something odd in what we're saying here. Do you mean expanding the dependencies when building the base DAG or when defining the compilation sorting order? Because these are two distinct steps and I'm not 100% sure what you mean there.

[pergu]

The one when you build the compile order

…

On Fri, 29 Jan 2021, 13:37 Fred Hebert, ***@***.***> wrote: Okay maybe there's something odd in what we're saying here. Do you mean expanding the dependencies when building the base DAG or when defining the compilation sorting order? Because these are two distinct steps and I'm not 100% sure what you mean there. — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#2465 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AABJAFO6P3BJW27TAFC2EYTS4K2YZANCNFSM4V5VQOXA> .

[ferd]

So that might work. The thing I'm worried about is similar handling for other languages that also have a concept of header files but whose headers do have an impact. That's arguably a smaller subset of them. If you've got the fix around already in a patch set I'm fine reviewing it.

[pergu]

I'll make a PR

[ferd]

the PR was at #2480 and has been merged.