rust_analyzer: don't build a tree of RustAnalyzerInfos (#3028)

This patch adds an `id` to RustAnalyzerInfo, and replace all the
recursive RustAnalyzerInfos with the respective crate `id`s.
This fixes RustAnalyzerInfos becoming exponentially expensive to build
in the presence of aliases.

---

Before this patch, `RustAnalyzerInfo.deps` contains the RustAnalyzerInfo
of the target crate's deps, and so on recursively.
This forms a graph of Infos where there is one Info per target, but
multiple paths from one target to another.
e.g. these could all point to `bar`: `foo.deps[0] == foo.deps[1].deps[0]
== foo.aliases[0]`.

If we walk `foo` as a tree, we will see `bar` multiple times. Two
operations that do this are `print(info)` and `{info: 42}` which hashes
the object. As the graph grows, the number of paths grows
combinatorically.

`RustAnalyzerInfo.aliases` is defined as a dict from `RustAnalyzerInfo
=> string`, so building this triggers the slowdown.

It would be possible to fix this by e.g. replacing this dict with a list
of pairs.
However the work `rust_analyzer_aspect` does is fundamentally local and
does not need a recursive data structure. Eliminating it means we can
freely use these values as keys, print them, etc.

---

Timings for `ra_ap_rust-analyzer` (which heavily aliases its deps):

```
blaze build //third_party/bazel_rules/rules_rust/tools/rust_analyzer:gen_rust_project; \
time blaze run //third_party/bazel_rules/rules_rust/tools/rust_analyzer:gen_rust_project -- //third_party/rust/ra_ap_rust_analyzer/...

===Before===
Executed in  211.06 secs    fish           external
   usr time    0.24 secs    0.00 micros    0.24 secs
   sys time    1.24 secs  604.00 micros    1.24 sec

===After===
Executed in    3.24 secs    fish           external
   usr time    0.15 secs  389.00 micros    0.15 secs
   sys time    1.18 secs  125.00 micros    1.18 secs
```
3 files changed
tree: 971a5468bd073dc2f97da4f56fe344b63a9218da
  1. .bazelci/
  2. .bcr/
  3. .github/
  4. cargo/
  5. crate_universe/
  6. docs/
  7. examples/
  8. extensions/
  9. ffi/
  10. nix/
  11. rust/
  12. test/
  13. tools/
  14. util/
  15. .bazelignore
  16. .bazelrc
  17. .bazelversion
  18. .clang-format
  19. .clippy.toml
  20. .envrc
  21. .gitattributes
  22. .gitignore
  23. .prettierrc.toml
  24. .rustfmt.toml
  25. ARCHITECTURE.md
  26. AUTHORS
  27. BUILD.bazel
  28. CODEOWNERS
  29. COMPATIBILITY.md
  30. CONTRIBUTING.md
  31. CONTRIBUTORS
  32. LICENSE.txt
  33. MODULE.bazel
  34. README.md
  35. version.bzl
  36. WORKSPACE.bazel
  37. WORKSPACE.bzlmod
README.md

Rust Rules

  • Postsubmit Build status

Overview

This repository provides rules for building Rust projects with Bazel.

Community

General discussions and announcements take place in the GitHub Discussions, but there are additional places where community members gather to discuss rules_rust.

Documentation

Please refer to the full documentation.