Description of the bug:

While updating to Bazel 7.0.0 from 6.3.2 I observed a large slowdown for our bazel query (from ~1min to ~20min). We use bazel query for finding affected targets (similar to what some open source solutions do like https://github.com/bazel-contrib/target-determinator or https://github.com/Tinder/bazel-diff).

Profiling (see reproduction steps below) yields following:

Which in turn leads us to following call-site

What's causing this regression for us? We implemented our own multiversion support for JVM (java and kotlin) and each multiversion is represented as a separate external repository causing proliferation and O(N * M) behavior here (we have 1000s of versions sadly).

Which category does this issue belong to?

Performance

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

I wrote this quickly to repro from scratch, appologies for quality :-)

repro.sh

mkdir /tmp/dummy_repo
echo 'workspace(name = "dummy_repo")' > /tmp/dummy_repo/WORKSPACE
echo '
genrule(
    name = "hello",
    outs = ["hello.txt"],
    cmd = "echo Hello, world! > $(OUTS)",
)
' > /tmp/dummy_repo/BUILD
# Get the absolute path to the dummy repository
dummy_repo_path=/tmp/dummy_repo

mkdir /tmp/repro_repo

# Create a Bazel workspace with 1000 local_repository rules
echo "" > /tmp/repro_repo/WORKSPACE
for i in $(seq 1 1000); do
    echo "
local_repository(
    name = \"local_repo_$i\",
    path = \"$dummy_repo_path\",
)
" >> /tmp/repro_repo/WORKSPACE
done

# Create a BUILD file with 1000 targets each depending on all of these repositories
echo "" > /tmp/repro_repo/BUILD
for i in $(seq 1 1000); do
    echo "
genrule(
    name = \"target_$i\",
    srcs = [" >> /tmp/repro_repo/BUILD

    for j in $(seq 1 1000); do
        echo "        \"@local_repo_$j//:hello.txt\"," >> /tmp/repro_repo/BUILD
    done

    echo "    ],
    outs = [\"output_$i.txt\"],
    cmd = \"cat \$(SRCS) > \$(OUTS)\",
)
" >> /tmp/repro_repo/BUILD
done

Now we can cd /tmp/repro_repo/ and run bazel query --output streamed_proto "//external:all-targets + deps(//...:all-targets)" --keep_going --enable_bzlmod --experimental_command_profile &> /dev/null

Which operating system are you running Bazel on?

Mac OSX / Linux

What is the output of bazel info release?

release 7.0.0

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

No response

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

No response

Is this a regression? If yes, please try to identify the Bazel commit where the bug was introduced.

This is a regression when enabling bzlmod I think, it's probably not important to find the exact commit.

Have you found anything relevant by searching the web?

No response

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

No response