Avoid different transition output directories when build settings have the same values

[torgil]

Description of the problem / feature request:

To avoid duplicated actions on dependencies when using build-settings it's necessary to reset build-settings to it's default value. This is currently not enough as we still can get conflicts on the "transition directory name fragment" for instance when two subsystems using different build-settings depend on a common library.

Bugs: what's the simplest, easiest way to reproduce this bug? Please provide a minimal example if possible.

The below example shows the issue with two build settings (used by B and C) triggering and action conflict in a common library (ExtDep) which appears in three branches from the top target:

1. A -> B -> ExtDep
2. A -> B -> C -> ExtDep
3. A -> ExtDep (issue also provoked with A -> C )

B sets a non-default value for bs2 in the input transition and resets it to default value in the edge transition to ExtDep.

Rule names below indicate which transitions they perform, eg the name "input_bs1_extdeps_bs2" indicates that it sets "bs1" build setting in the input transition and "bs2" build setting in the edge transition on the "extdeps" attribute.

rules.bzl

"Rules with different transitions to showcase analyze phase configuration conflicts"

def _dummy_rule_impl(ctx):
    return []

def _input_transition_impl(settings, attr):
    build_settings = {setting: settings[setting] for setting in attr._input_settings}
    build_settings.update(attr.input_build_settings)
    return build_settings

def _extdeps_transition_impl(settings, attr):
    build_settings = {setting: settings[setting] for setting in attr._extdeps_settings}
    build_settings.update(attr.extdeps_build_settings)
    return build_settings

def _create_custom_rule(input, extdeps):
    return rule(
        implementation = _dummy_rule_impl,
        cfg = transition(inputs = input, outputs = input, implementation = _input_transition_impl),
        attrs = {
            "deps": attr.label_list(),
            "extdeps": attr.label_list(cfg = transition(
                inputs = extdeps, outputs = extdeps, implementation = _extdeps_transition_impl)),
            "extdeps_build_settings": attr.string_dict(),
            "input_build_settings": attr.string_dict(),
            "_extdeps_settings": attr.string_list(default = extdeps),
            "_input_settings": attr.string_list(default = input),
            "_whitelist_function_transition": attr.label(
                default = "@bazel_tools//tools/whitelists/function_transition_whitelist",
            ),
        },
    )

build_setting = rule(
    implementation = _dummy_rule_impl,
    build_setting = config.string(flag = False),
)

input_outdir = _create_custom_rule(
    ["//command_line_option:output directory name"],
    [],
)

input_outdir_bs1_bs2_extdeps_bs1_bs2 = _create_custom_rule(
    ["//:bs1", "//:bs2", "//command_line_option:output directory name"],
    ["//:bs1", "//:bs2"],
)

BUILD.bazel

load(":rules.bzl", "build_setting", "input_outdir", "input_outdir_bs1_bs2_extdeps_bs1_bs2")
load("@rules_cc//cc:defs.bzl", "cc_library")

build_setting(
    name = "bs1",
    build_setting_default = "bs1_default",
)

build_setting(
    name = "bs2",
    build_setting_default = "bs2_default",
)

input_outdir(
    name = "A",
    input_build_settings = {
        "//command_line_option:output directory name": "any",
    },
    deps = [":B", ":ExtDep"],  # C instead of ExtDep triggers the same issue
)

input_outdir_bs1_bs2_extdeps_bs1_bs2(
    name = "B",
    input_build_settings = {
        "//command_line_option:output directory name": "any",
        "//:bs1": "bs1_default",
        "//:bs2": "bs2_custom",  # Input transition sets custom bs2 value
    },
    deps = [":C"],
    extdeps = [":ExtDep"],  # Edge transition sets default bs2 value
    extdeps_build_settings = {"//:bs1": "bs1_default", "//:bs2": "bs2_default"},
)

input_outdir_bs1_bs2_extdeps_bs1_bs2(
    name = "C",
    input_build_settings = {
        "//command_line_option:output directory name": "any",
        "//:bs1": "bs1_default",
        "//:bs2": "bs2_default",
    },
    extdeps = [":ExtDep"],
    extdeps_build_settings = {"//:bs1": "bs1_default", "//:bs2": "bs2_default"},
)

# Dependency with action to trigger the action conflict (any rule generating actions may apply here)
cc_library(
    name = "ExtDep",
    srcs = ["extdep.c"],
)

Example run:

$ bazel build //:A
ERROR: file '_objs/ExtDep/extdep.pic.o' is generated by these conflicting actions:
Label: //:ExtDep
RuleClass: cc_library rule
Configuration: 0ef19c895a80334be3739ffbe96bbd7f6766cbb2944f2a649b67acb81d261d43, 643272508e08a8348ad8387f39b923f0972d5a26bb916ec22e0cc03e63c97511
<...>
$ bazel config 0ef19c895a80334be3739ffbe96bbd7f6766cbb2944f2a649b67acb81d261d43 643272508e08a8348ad8387f39b923f0972d5a26bb916ec22e0cc03e63c97511
INFO: Displaying diff between configs 0ef19c895a80334be3739ffbe96bbd7f6766cbb2944f2a649b67acb81d261d43 and 643272508e08a8348ad8387f39b923f0972d5a26bb916ec22e0cc03e63c97511
Displaying diff between configs 0ef19c895a80334be3739ffbe96bbd7f6766cbb2944f2a649b67acb81d261d43 and 643272508e08a8348ad8387f39b923f0972d5a26bb916ec22e0cc03e63c97511
FragmentOptions com.google.devtools.build.lib.analysis.config.CoreOptions {
  affected by starlark transition: [//:bs2, //command_line_option:output directory name], [//command_line_option:output directory name]
  transition directory name fragment: ST-1e8dc79add0a, ST-a28aa8ec4aa8

Opts passed to transitionDirectoryNameFragment function:

ST-a28aa8ec4aa8: [//command_line_option:output directory name=any]
ST-1e8dc79add0a: [//:bs2=bs2_default, //command_line_option:output directory name=any]

What operating system are you running Bazel on?

Linux

What's the output of bazel info release?

development version

If bazel info release returns "development version" or "(@non-git)", tell us how you built Bazel.

1. git checkout f0da3ecd186a33439b6255521e4d13a0e65ce88f  # current master
2. git revert commit af0e20f9d9808d8fba03b712491ad8851b3d5c26  # revert "Remove outdated "output directory name" option."
3. bazel-4.1.0-linux-x86_64 build //src:bazel-dev

What's the output of git remote get-url origin ; git rev-parse master ; git rev-parse HEAD ?

not applicable

$ git remote get-url bazelbuild; git rev-parse bazelbuild/master ; git rev-parse HEAD ; git rev-parse HEAD~1
https://github.com/bazelbuild/bazel.git
f0da3ecd186a33439b6255521e4d13a0e65ce88f
b7308ccc7d763088c2efe997ac111bd9e09cec6a
f0da3ecd186a33439b6255521e4d13a0e65ce88f

Issue isolated on a custom version of v5.0.0-pre.20210604.6 but originally found in 4.x versions

Have you found anything relevant by searching the web?

Related issues: #12171 #12731

Any other information, logs, or outputs that you want to share?

Prior to #13580 it's possible to trigger the issue with only B -> ExtDeps and B -> C -> ExtDeps given that bs1 is not included in the extdeps edge transition (found with git bisect building //:B above but using input_outdir_bs1_bs2_extdeps_bs2 instead of input_outdir_bs1_bs2_extdeps_bs1_bs2)

#13587 in combination with a custom output directory scheme using transition on "//command_line_option:output directory name" is designed to address all issues leading to conflicting "transition directory name fragment". This transition turns these types of issues into build failures due to action conflicts rather than silently duplicating actions in different output folders.

[sdtwigg]

Ok, I have a somewhat long update to this after spending a few weeks off-and-on contemplating this and related issues:

Core Background
First, as core background, note that ConfiguredTargetFunction (which, when given a BuildConfigurationKey and Label performs analysis for a rule) is highly sensitive. Skyframe memoization is required for performant operation and, in the case of unsharable actions (cc_*, etc.) correctness. New comments in

bazel/src/main/java/com/google/devtools/build/lib/skyframe/ConfiguredTargetKey.java

Line 32 in 33f7648

* In simple form, a ({@link Label}, {@link BuildConfigurationValue}) pair used to trigger immediate

hopes to clarify this.
Summarizing, Bazel has a key correctness constraint that, for every active Target across an entire build, the associated ConfiguredTargetKeys (created with a Label of that Target) must result in different output directories being computed during rule analysis. Note that Skyframe infrastructure is sufficiently intelligent to ensure that, between builds, stale keys do not cause action conflicts if their output directories match active keys.

Interlude on computing the output directory name
As per code in OutputDirectories.java, the output directory path name is a function of a subset of specifically-called-out fragment options (cpu, compilation mode, python version, etc.) and hash of the values of all options listed in "affected by Starlark transition".

Deeper dive on ensuring correctness of build
Transitions and associated infrastructure are currently ensuring the key correctness constraint noted above is followed by either:

• [A] Ensuring that their options changes cause the output directory name to change. For example, most native transitions only affect options in that subset of specifically-called-out fragment options and thus the output directory name naturally changes. As another example, the Starlark transition infrastructure appends all affected options to affected by Starlark transition thus ensuring a (always always unique) hash is appended to the output directory name.
• [B] Relying on the Target never having been built with the pre-transition value. For example, the test trimming transition (triggered on all non-test targets by the now default true --trim_test_configuration option) creates a new BuildOptions with TestOptions removed. This trimming does not affect the output directory name but there is a presumed system-level guarantee that those Targets will never be analyzed with the pre-transition configuration and thus the constraint is still satisfied. (Although, see the interlude below on 'impossible' BuildOptions for how a separate class of Bazel bugs can cause this guarantee to be violated.)

Interlude about "transition directory name fragment leading to violations of A.
Currently, "transition directory name fragment" is part of BuildOptions. It is essentially the hashed value of all values in options referred to by "affected by Starlark transition". Excluding synthetic (i.e. should not happen in real builds) cases where a transition is itself on "transition directory name fragment", "transition directory name fragment" is itself a computed value based on all the other BuildOptions. Failure to update this when other build options change (e.g. it is discovered the exec transition fails to update this when appropriate #13464) can lead to inconsistent BuildOptions. A change is already in motion to move "transition directory name fragment" out of BuildOptions and instead have it be computed as part of constructing the BuildConfigurationValue (formerly called BuildConfiguration), a collection of a BuildOptions and values all computed from that given BuildOptions). So, for the rest of this issue, assume that "transition directory name fragment" is always consistent with the rest of the BuildOptions.

Interlude about 'impossible' BuildOptions leading to violations of B.
Ultimately, due to bugs, Bazel internal infrastructure can potentially create 'impossible' ConfiguredTargets; namely, analysis of a specific target done with BuildOptions that can't seemingly have been attached to a target (e.g. Target has a self-transition or trimming but they failed to apply). Failing to apply a self-transition won't necessarily cause an action conflict; however, it can lead to incorrect actions. Failing to apply trimming can lead to action conflicts because trimmed off fragments often aren't part of computing the output directory name. Avoiding 'impossible' ConfiguredTargets is not directly relevant to this issue and moreso relevant to #7450. Assume for the rest of this issue that the given configuration had all the currently scheduled transitions and trimming operations run on it.

Additional constraints for more performant builds
Now, while that constraint is necessary for correctness, there are additional constraints in order to maximize build performance. For every active Target across an entire BUILD, it should be analyzed as few times as necessary. If the build actions (commandline and input file contents) of two ConfiguredTargets are the same except for their output directories then they are clearly redundant. Fully solving this problem is generally understood to require generic trimming (i.e. not rebuilding a C++ library just because the python version changed) and outside the scope of this issue for now. However, we can look at avoiding redundancy when only affected by Starlark transition is different.

Further, presuming the use of action caching, there is another optimization available: avoid changing the output directory names as much as possible between incremental builds when command-line options change if those command-line options would have no other effect on the generated actions besides changing the output directory name. This leads to the following observations:

• Adding the full hash of the BuildOptions to the output directory name would be potentially catastrophic to incremental action caching. Changing any command-line option would then change all output directory names and thus require those actions be re-run. (Although, as a bonus, going to a previous commandline would likely require no re-runs.)
• The output directory name being sensitive to that specific subset of specifically-called-out fragment options is seemingly a violation of this desire. However, the gamble is that those options are highly likely to have command-line changes (e.g. compilation mode and the platform).

"affected by Starlark transition" is not quite right
It is currently the list of all native or Starlark options changed by any previous Starlark transition. This is sufficient to ensure the output directory name changes enough after any Starlark transition. However, it is overly pessimistic:

• [1] A Starlark transition can change an option in the subset of specifically-called-out fragment options already handled by OutputDirectories.java. This will cause that option to be appended to "affected by Starlark transition" and included in the ST-hash even though the other parts of OutputDirectories.java is already accounting for the difference.
• [2] Platform mappings cause 2+ options of BuildOptions to be dependent on each other (e.g. --cpu and --platform). Two separate Starlark transitions (e.g. one that affects --cpu and another that equivalently affects --platform) could result in, after application of platform mappings, BuildOptions that differ only in "affected by Starlark transition". Unfortunately, they are likely to result in different ST-hash computations and thus redundant analysis and actions.
• [3] Two Starlark transitions could cause the configuration to transition from A -> B -> A* where A and A* differ only in "affected by Starlark transition". In this case, A -> B is from application of a (native or Starlark) transition affecting a previously-untouched-by-Starlark option. Then, B -> A* is a Starlark transition that reverts that option back to the value it had in A. This causes "affected by Starlark transition" to contain that option.

Potential Resolutions and Related work

• Native transitions (except the exec transition; see the appendix below) should to be audited to ensure they all satisfy transition sub-constraint [A]. In practice, it is likely simplest for readability and maintainability if native transitions only touch options in the subset of specifically-called-out fragment options already handled by OutputDirectories.java.
• To address [1], metadata could be added to native options to track whether they already are in that subset of options specially handled by OutputDirectories.java. If so, those options are not added to "affected by Starlark transition" when Starlark transitions touch those options.
• To address [2], platform mappings could be restricted to only involving options already marked as being in the subset of options specially handled by OutputDirectories.java. This would address a slew of corner cases around transitions, output directory names, and platform mappings. Otherwise, this scenario will need to be revisited.

Addressing [3] is potentially more complex and I have two competing solutions at this time:

• Change "affected by Starlark transition" to instead be a map from option name to original (command-line) value. This will require all transitions (especially the native transition) to store the old value when performing the transition. For maintainability, this requirement may be elevated to the general transition infrastructure and could rely on a separate Skyframe call for caching. Then, if at any point the configuration transitions back to the old value, that entry in "affected by Starlark transition" is dropped (causing the value to be removed from the hash). It is important for correctness that the entry is actually dropped (instead of just skipped during hash computation) to ensure the configurations actually properly overlap when ConfiguredTargetFunction is called. (Note that this was historically tried before but failed due to other bugs. It is expected that we understand the context enough this time to get it right. However, there is still an issue that "affected by Starlark transition" is present as pseudo-dependent/redundant state in BuildOptions)
• Similar to the above change; however, do not tracking "affected by Starlark transition" in BuildOptions at all. Instead, during output directory name calculation, manifest the top-level configuration and do a diff right there to effectively calculate what "affected by Starlark transition" should be. (My fear here is making sure the manifesting of top-level configuration does not cause issues with Skyframe invalidation as the top-level configuration will not be part of the BuildConfigurationKey SkyKey.)

Appendix about the exec transmission
Currently, the exec transition changes a lot of values (both those in the subset of those handled by OutputDirectories and those outside of that subset) but makes no explicit changes to the output directory name fragment or "affected by Starlark transition". In practice, it may be best for long-term correctness to treat the exec transition like a Starlark transition and audit the fromOptions and toOptions to ensure "affected by Starlark transition" is updated as appropriate.

In practice, this could be enough to rename "affected by Starlark transition" to something closer to intended like "changed options to hash" and, if doing the diff is cheap enough (or cachable), treat all native transitions like Starlark transitions and also audit their changes.

[sdtwigg]

As a quick update after conversation with the Bazel core team (experts on the underlying Skyframe infrastructure).

Likely to skip the first proposal to address [3] "Change "affected by Starlark transition" to instead be a map from option name to original (command-line) value."

Instead, the second proposal should be technically feasible with similar effort (and better performance). BuildConfigurationFunction will properly request/register a dependency on the top-level configuration via the Skyframe environment (likely going to injected by using the PrecomputedValue Skyframe feature).

In order for this to work correctly (and avoid unnecessary recomputation of ConfiguredTargetFunction), will need to make sure BuildConfigurationValue.equals is sensitive to the OutputDirectories object it holds (as well as the underlying BuildOptions, of course). At the moment, it looks like it relies on reference equality (and thus is overly sensitive to re-computation).

[gregestren]

@fmeum

[gregestren]

Thanks for this update, @sdtwigg .

My notes on the above:

Values:

• An output prefix shouldn't depend on the dependency path that was taken to get there
• transition directory name fragment and affected by starlark transition shouldn't be independently settable build options since they're pure functions of other options
• No two configs should ever differ by just transition directory name fragment and affected by starlark transition (something we observe a lot today)
• ideally all transitions (native, Starlark, exec) should follow the same, consistent logic
• Doing that is hard since they start from very different places So full convergence is unlikely now

Proposal:

• Update native transition logic. Can you concisely summarize what this achieves?
• Define and compute transition directory name fragment where?
• Define and compute affected by Starlark options where? (I think Avoid different transition output directories when build settings have the same values #14023 (comment) covers this?)
• What's the consideration for diffing by top-level (set at command line) values vs. option defaults?
• You want to do phased implementation, right? What are the phases?

[gregestren]

Instead, the second proposal should be technically feasible with similar effort (and better performance). BuildConfigurationFunction will properly request/register a dependency on the top-level configuration via the Skyframe environment (likely going to injected by using the PrecomputedValue Skyframe feature).

Copying some notes I took on the problem a while back: Do these match your plan?

---

There's another place we can set hash values: BuildConfigurationFunction
This may be cleaner, in that it gives BuildConfiguration more decisive ownership over its output paths, like in here.

In other words, we can exclusively say that a BuildConfiguration's output path is determined in BuildConfiguration construction, end of story. Something about that sounds appealing: more clear, focused ownership of a subtle concept.

BuildConfigurationFunction also has the advantage that it can easily access the build's top-level configuration, or defaults, or whatever.

Just follow the precedent of ConfiguredTargetFunction, which does this here. That code instantiates the Function with a BuildViewProvider, which Skyframe fulfills and keeps current with every build.

That includes stuff like here, which provides the top-level host configuration. It's pretty trivial to expand that to provide any other top-level context.

[gregestren]

Can we simply remove affected by starlark transition and replace it with BuildConfigurationFunction logic that creates transition directory name fragment?

[eric-skydio]

Thanks for putting in all the work to write this up, I'm excited to see this is on a path to eliminate the horrible hacks we are currently using in our codebase to make this work.

In the process of implementing a number of "unifying" starlark transitions in our codebase, one realization we've had is that it's often useful to be able to explicitly "delete" a configuration setting, meaning reset it to the command-line value. For now, we can get by with hard-coding those default values into the various transitions that need to access them, but it would eventually be nice to be able to explicitly perform a "reset" operation from a Starlark transition. It sounds like the proposed Skyframe changes would open the path to that, but I'm not familiar enough with that system to know for sure.

[fmeum]

Can we simply remove affected by starlark transition and replace it with BuildConfigurationFunction logic that creates transition directory name fragment?

To answer this question, I quickly prototyped this approach in fmeum@5eefd23. This has the obvious noted deficencies and contains debug prints, but allowed me to get a better understanding of what the computed affected by starlark transition would look like. It does successfully analyze rules_go as well as our codebase at work, printing diffs such as:

Differing options:
//command_line_option:compilation_mode: opt -> fastbuild
//command_line_option:is host configuration: true -> false
//command_line_option:fat_apk_cpu: [] -> [armeabi-v7a]
//command_line_option:copt: [-g0] -> []
//command_line_option:cxxopt: [-g0] -> []
//command_line_option:strip: always -> sometimes
//command_line_option:java_runtime_version: remotejdk_11 -> local_jdk
//command_line_option:jvmopt: [-XX:ErrorFile=/dev/stderr] -> []
//go/config:static: null -> true
//go/private:request_nogo: null -> true
transitionDirectoryFragment = "ST-7ee17c9866ed"

Based on the contents of the typical diffs, I wonder whether getHostConfiguration() is the correct baseline. Is there a way to get the top-level target config rather than the host config? It could be a better fit.

Edit: This seems to be available from PrepareAnalysisPhaseValue, but I don't know the consequences of declaring a dependency on that in Skyframe.

@gregestren @sdtwigg Feel free to use (or ignore) this code under the CLA terms. If you are still worried about licensing issues, I could also submit it as a draft PR.

[gregestren]

Based on the contents of the typical diffs, I wonder whether getHostConfiguration() is the correct baseline. Is there a way to get the top-level target config rather than the host config? It could be a better fit.

Yes, there is a way. And I agree the top-level config makes a better baseline.

Since @sdtwigg has plans along these lines I'd leave it to you two to converge.

[sdtwigg]

As another piece of work (to be done after removal of "affected by Starlark transition" so tjat the results native transitions are also being properly diffed against the top-level configuration), we can then remove the ad hoc output directories distinguishers used by AppleConfiguration and AndroidConfiguration in their configurationDistinguisher option. (Morally, the configurationDistinguisher is very similar to "affected by Starlark transition" and "transition directory name fragment" in that they are wholly functions of the current configuration and its diff to other configurations. Thus, their function should be wholly subsumed by the more generic calculation of ST-hash.)

[fmeum]

@sdtwigg @gregestren Could you provide a brief update on the efforts to make affected by starlark transition a pure function? Do you still expect to implement that this year? If there should be parts that could be done independently, I would be happy to help.

[gregestren]

@sdtwigg has some pending code at https://bazel-review.googlesource.com/c/bazel/+/181730 that I'm not aware of anything blocking it from merging. I don't know his ETA for the necessary followups.

I'm taking a holiday break through the new year but I'll make sure to follow up after Jan 4.