Transitive specialised dependencies are not queued to be built

[marcuscaisey]

When a target //:target requires lang and one of its dependencies //:dep provides a specialised dependency //:provided_dep for lang, then //:target depends on //:provided_dep instead of //:dep. However, if //:dep instead depends on //:transitive_dep which provides //:provided_dep for lang and //:target requires transitive dependencies, then building //:target fails.

This is an edge case, but it did actually occur in the wild in please-build/python-rules#308.

Reproduction

root=$(mktemp -d /tmp/please-XXXXXX)
plz init --dir $root >/dev/null
cat << EOF > $root/BUILD
genrule(
    name = "target",
    outs = ["target"],
    cmd = "find . > $OUT",
    needs_transitive_deps = True,
    requires = ["lang"],
    deps = [
        ":dep",
    ],
)

filegroup(
    name = "dep",
    deps = [":transitive_dep"],
)

filegroup(
    name = "transitive_dep",
    provides = {
        "lang": ":provided_dep",
    },
)

text_file(
    name = "provided_dep",
    content = "",
)
EOF
plz build --repo_root $root //:target

Build stopped after 10ms. 1 target failed:
    //:target
cannot calculate hash for plz-out/gen/provided_dep: file does not exist

Cause

From what I can tell, there is a mismatch between the artefacts that are included the build sandbox for //:target and the targets which gets queued to be built.

• When preparing the build sandbox, core.IterInputs calls recursivelyProvideFor to recursively resolve the outputs of transitive specialised dependencies.
• When parsing the build graph, core.BuildState.ActivateTarget calls core.BuildState.DependentTargets to resolve the specialised dependencies, but doesn't do it recursively. So //:provided_dep never gets queued to be built.

Expected Behaviour

Not sure tbh. The behaviour of core.IterInputs including specialised dependencies from transitive dependencies isn't mentioned by Require & Provide and isn't reflected in the output of plz query deps, so this feels like the more incorrect bit. I think it makes reasoning about the build graph a bit harder as well but maybe this is being relied on by someone somewhere and just working (if //:transitive_dep depended on //:provided_dep like how proto_library works, then //:target would build fine).