-
-
Notifications
You must be signed in to change notification settings - Fork 636
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Tolerate build graph cycles #10059
Comments
@benjyw , @Eric-Arellano: I've sketched out some of the open questions here: https://docs.google.com/document/d/1-n-TG8_iBhhzmnZPUi4lGcl5Q2eF9FYScGnmxZmk2-c/edit# |
### Problem As covered in #10059: in order to support fine-grained dependency inference on real world graphs (which very frequently involve file-level dependency cycles), we'd like to very carefully introduce a form of cycle-tolerance. ### Solution Introduce the concept of "weak" `Get`s (exposed via `await Get(.., weak=True)`) which can return `None` if a cycle would be formed that would cause a `@rule` to depend on its own result. A weak `Get` is intended to be similar in practice to a [weak reference](https://en.wikipedia.org/wiki/Weak_reference), and correspondingly non-weak edges are referred to as "strong" edges. A few changes were made to the `Graph` to support this, but the most fundamental was that we now allow cycles in the `Graph`, as long as they don't involve any running `Node`s. As described in the docstring for `graph::Graph`, we record dependencies for two reasons: 1) invalidation, and 2) deadlock detection. Invalidation is not concerned by cycles, and a deadlock can only occur in running code and thus does not need to walk non-live edges. ### Result Tests demonstrate that `@rules` are able to successfully consume "weak-weak" cycles, where a graph like: ``` digraph { A -> B [label=weak, style=dashed]; B -> A [label=weak, style=dashed]; } ``` ... produces the set `{A, B}` when entered from either direction. Followup work will additionally allow for "strong-weak" cycles, which "mostly" work right now, but which currently have behavior that depends on where the cycle is entered. See #10229 and the ignored test in this change.
After examining options, weak-Gets looks like the right way to go for now. #10230 has landed, and @Eric-Arellano will follow up to incorporate it into |
Closes #10059. It's common in many languages, including Python, to sometimes have import cycles. When using generated subtargets—meaning either dependency inference or explicit file dependencies—Pants will tolerate these cycles. For now, there is no other way to express that a cycle should be tolerated. In the future, we may consider adding a syntax to BUILD files to allow indicating that cycles should be tolerated; it's easier to loosen than it is to tighten. [ci skip-rust-tests]
Via discussion: it doesn't sound like this is blocking the alpha, because the |
…in file-addresses. (#10409) ### Problem After more deeply investigating the issues with #10230 (demonstrated in #10393 and its revert), it doesn't seem like the right idea to rely on the engine's cycle detection (which the implementation of #10230 showed should primarily be used for deadlock detection) to expose high level cycle tolerance for the build graph. ### Solution Move to iterative transitive target expansion (à la #10046), and cycle detect afterward using DFS with a stack of visited entries. ### Result Fixes #10059, and closes #10229. A followup will back out portions of #10230 (but not all of it, as there were a number of other improvements mixed in). [ci skip-rust-tests]
Unfortunately these exist in the real world, and we should still work with them when possible. For example, unless some goal has to operate recursively (e.g., JVM compile), it can usually work with cycles.
The text was updated successfully, but these errors were encountered: