Query output with deps order is wrong for proto output format

[xzxzzxzxzca]

Description of the bug:

Bazel's protobuf output is not ordered the same way as the one in label format, even if --order_output=deps is set explicitly in both cases. "Label" output goes "top-down", listing dependencies last. So for example one could iterate the output in reverse order and see the source files first before seeing the rules consuming them. In proto output this is not the case, and source files seem to be output in no particular order (yet, consistent from run to run). Rules still seem to be ordered by dependencies though.
This is critical for any use-case where the output is supposed to be consumed and processed by another program, as building the workspace model from such output essentially can't rely on the ordering and would have to perform additional sorting on its own.

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

Clone the examples repo
Go to e.g. cpp-tutorial/stage3 subdirectory
Query workspace first with outputs as labels: bazel query '//...:*' --order_output=deps --output label
Observe the output order:

//main:hello-world.stripped
//main:BUILD
//main:hello-world.dwp
//main:hello-world
//main:hello-world.cc
//main:hello-greet
//main:hello-greet.cc
//lib:BUILD
//:BUILD
//lib:hello-time
//lib:hello-time.h
//lib:hello-time.cc
//main:hello-greet.h

Now do the same query with protobuf output: bazel query '//...:*' --order_output=deps --output proto and compare the order of items to the previous output.
Although, proto is not very human-readable, it's still visible that the ordering is different. What's critical is that sources and generated files are absolutely out of place.

Which operating system are you running Bazel on?

MacOS

What is the output of bazel info release?

release 5.3.2-homebrew

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 ?

https://github.com/bazelbuild/examples
f53d6699dc0fdfbf288b92345980ea8708e2db0a
f53d6699dc0fdfbf288b92345980ea8708e2db0a

Have you found anything relevant by searching the web?

Here's another somewhat relevant bug report I found: #12320

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

No response

[xzxzzxzxzca]

It looks like this is only fixed in Bazel 7. Will this be ported into 6?

[fmeum]

@bazel-io flag

[keertk]

@bazel-io fork 6.3.0