brew install/upgrade on Linux: formula re-loaded per dependency edge during resolution (no memoization); severe when bubblewrap implicit dep is unsatisfied [6.0.5]

[adam-eickhoff-hrd]

brew doctor output

❯ brew doctor
Your system is ready to brew.

Verification

• I ran brew update twice and am still able to reproduce my issue.
• My "brew doctor output" above says Your system is ready to brew or a definitely unrelated Tier message.
• This issue's title and/or description do not reference a single formula e.g. brew install wget. If they do, open an issue at https://github.com/Homebrew/homebrew-core/issues/new/choose instead.

brew config output

HOMEBREW_VERSION: 6.0.5
ORIGIN: https://github.com/Homebrew/brew
HEAD: fd9b97148a778b9b34fb743ef066af110ae7bff6
Last commit: 25 hours ago
Branch: stable
Core tap: N/A
HOMEBREW_PREFIX: /home/linuxbrew/.linuxbrew
HOMEBREW_CASK_OPTS: []
HOMEBREW_DOWNLOAD_CONCURRENCY: 48
HOMEBREW_FORBID_PACKAGES_FROM_PATHS: set
HOMEBREW_MAKE_JOBS: 24
HOMEBREW_REQUIRE_TAP_TRUST: set
Homebrew Ruby: 4.0.5 => /home/linuxbrew/.linuxbrew/Homebrew/Library/Homebrew/vendor/portable-ruby/4.0.5_1/bin/ruby
CPU: 24-core 64-bit zen5
Clang: N/A
Git: 2.43.0 => /bin/git
Curl: 8.5.0 => /bin/curl
Kernel: Linux 6.18.33.2-microsoft-standard-WSL2 x86_64 GNU/Linux
OS: Ubuntu 24.04.4 LTS (noble)
WSL: 2 (Microsoft Store)
Windows: Windows 11 Enterprise (25H2) [26200.8390]
Host glibc: 2.39
Host libstdc++: 6.0.33
/usr/bin/gcc-13: 13.3.0
/usr/bin/ruby: N/A
glibc: N/A
gcc@13: N/A
gcc: 16.1.0
xorg: N/A

What were you trying to do (and why)?

Initially, attempting to brew upgrade 19 packages, because best practice.
Total run time; exceeding 20min

What happened (include all command output)?

Summary
On Linux, dependency resolution re-parses formulae from the JSON API once per dependency edge rather than once per unique formula, with no memoization across the graph walk. With a large/diamond-shaped dependency graph this becomes drastically slow. The effect is hugely amplified when no usable bwrap is installed, because bubblewrap is then injected as an implicit dependency on every node and re-loaded between every other load.

Initially, attempting to brew upgrade 19 packages
Total run time; exceeding 20min (I interrupted the process because it was taking too long)

Installing bubblewrap solo brew install bubblewrap --debug --verbose (logs attached below)
Total run time: 7m7s

Running brew upgrade after bwrap install
Total run time: 1m9s

bubble-wrap-install-debug-logs.txt

What did you expect to happen?

Expected
Each formula loaded/parsed once per resolution pass (memoized across the graph walk), so resolution time scales with the count of unique formulae, not dependency edges.

Step-by-step reproduction instructions (running brew commands)

Minimal repro
brew install bubblewrap --debug
With --debug, bubblewrap plus shared deps (xorgproto, libx11, xz, lz4, ncurses, openssl@3, etc.) are each logged as Formulary::FromAPILoader: loading <formula> hundreds of times during resolution of this single formula — before any download. bubblewrap is re-loaded between essentially every other formula load.
Larger repro
brew upgrade of 19 outdated packages including an X11/media-heavy set (ffmpeg, sdl2, sdl2-compat, alsa-lib). Same per-edge re-loading; xorgproto re-loads ~9×, libx11 ~7×, in a short excerpt.
Resolution / smoking gun (timing)
Installing bubblewrap standalone so a usable bwrap exists eliminated the implicit-dependency injection and produced a dramatic speedup:

Before (bwrap absent): brew upgrade stalled in resolution long enough to appear hung.
After (brew install bubblewrap, then re-run): the same 19-package upgrade, split into two brew upgrade commands, completed in ~1 minute total.

This isolates two compounding factors:

Primary amplifier (user-fixable): missing bwrap → bubblewrap injected on every node → re-loaded per edge. Installing bubblewrap removes this.
Underlying issue (not user-fixable): even the minimal brew install bubblewrap repro re-parses shared deps hundreds of times, so the per-edge re-loading exists independently of the bubblewrap injection — just far less visible once the injection is gone.