brew says [email protected] is needed by cairo and graphene, but it's not

[fxcoudert]

brew config output

HOMEBREW_VERSION: 3.5.9-124-gfcb30c1
ORIGIN: https://github.com/Homebrew/brew
HEAD: fcb30c1ead6977f7c880a6770e6d4c11ed5d635a
Last commit: 23 hours ago
Core tap ORIGIN: https://github.com/Homebrew/homebrew-core
Core tap HEAD: 7c64f3c143c0bb0454b747e50af5c6fff0e0e87e
Core tap last commit: 39 minutes ago
Core tap branch: master
HOMEBREW_PREFIX: /opt/homebrew
HOMEBREW_CASK_OPTS: []
HOMEBREW_DISPLAY: /private/tmp/com.apple.launchd.hzx1VHZ6yZ/org.xquartz:0
HOMEBREW_EDITOR: vim
HOMEBREW_GITHUB_API_TOKEN: set
HOMEBREW_MAKE_JOBS: 8
HOMEBREW_NO_AUTO_UPDATE: set
Homebrew Ruby: 2.6.8 => /System/Library/Frameworks/Ruby.framework/Versions/2.6/usr/bin/ruby
CPU: octa-core 64-bit arm_firestorm_icestorm
Clang: 13.1.6 build 1316
Git: 2.32.1 => /Applications/Xcode.app/Contents/Developer/usr/bin/git
Curl: 7.79.1 => /usr/bin/curl
macOS: 12.5-arm64
CLT: 13.4.0.0.1.1651278267
Xcode: 13.4.1
Rosetta 2: false

brew doctor output

Your system is ready to brew.

Verification

• [X] I ran brew update and am still able to reproduce my issue.
• [X] I have resolved all warnings from brew doctor and that did not fix my problem.

What were you trying to do (and why)?

After brew update && brew upgrade, I saw that the migration from Python 3.9 to 3.10 seemed completed, and decided to remove the old version.

What happened (include all command output)?

$ brew rm [email protected]
Error: Refusing to uninstall /opt/homebrew/Cellar/[email protected]/3.9.13_3
because it is required by cairo and graphene, which are currently installed.
You can override this and force removal with:
  brew uninstall --ignore-dependencies [email protected]
$ brew deps --tree graphene                      
graphene
└── glib
    ├── gettext
    ├── libffi
    └── pcre

What did you expect to happen?

Brew should allow me to remove [email protected]

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

brew rm [email protected]

[carlocab]

The [email protected] dependency is recorded in the tab, because it had that dependency when the bottle was poured. It doesn't have that anymore, but brew currently doesn't know how to handle that.

[fxcoudert]

It makes for a very weird user experience, to say the least…

[carlocab]

Yea, it does. A workaround for new is to brew reinstall cairo graphene. But we should handle this properly.

[carlocab]

@MikeMcQuaid I'm not going to make more noise about it if you still disagree, but I genuinely think this is a bug in brew that's worth trying to fix.

[hyuraku]

@carlocab I suggest a new function to return one formula runtime dependencies; how about?

  def all_runtime_dependencies (formula)
    required_deps = formula.deps.select{|dep| dep.required? }
    further_deps = required_deps.map{|r_dep| r_dep.to_formula.deps}.flatten.uniq.select{|dep| dep.required? and !required_deps.include?(dep) }

    while further_deps != [] do
      required_deps.push *further_deps
      further_deps = further_deps.map{|f_dep| f_dep.to_formula.deps}.flatten.uniq.select{|dep| dep.required? and !required_deps.include?(dep) }
    end

    return required_deps
  end

[carlocab]

That's not quite enough. The issue is that there is a difference between the dependencies recorded in the tab and the dependencies declared in the relevant formulae.

We need to work out how to identify these differences arising and what to do about them when they do.

[apainintheneck]

Assuming that the list is correct when a formula is installed from source, how can the dependency list get out-of-date? It seems like this list is only updated/created when a formula is installed. That means that each direct dependency and it's dependencies are recorded in the tab. If a dependency changes it's dependencies in the meantime, then only it's own tab will be updated; all of the formulas that depend on it will have out-of-date dependency lists. The likelihood that a formula will have an out-of-date dependency list goes up with bottles since the tab is recorded when the bottle is built not when the bottle is installed.

Is that what's going on here?

[carlocab]

Yes, that sounds correct. brew uninstall is intentionally conservative about uninstalling things, and I think maintaining a level of conservatism for a destructive operation is useful.

I'm just not sure how to balance the existing conservatism against some dependencies sometimes becoming stale. In particular, I'm concerned about the dependency-tree-as-declared-in-the-formula being wrong, and we definitely don't want to do the uninstall in those cases.

[MikeMcQuaid]

Yes, that sounds correct. brew uninstall is intentionally conservative about uninstalling things, and I think maintaining a level of conservatism for a destructive operation is useful.

Agreed 👍🏻

I'm just not sure how to balance the existing conservatism against some dependencies sometimes becoming stale. In particular, I'm concerned about the dependency-tree-as-declared-in-the-formula being wrong, and we definitely don't want to do the uninstall in those cases.

IMO the only issue here is the inconsistency really. If we ensure they are both 👍🏻 or 👎🏻 on the same formula: we're good here.

Ideally, that would result in more shared code between the two commands so they don't drift in future.

[apainintheneck]

I'm just not sure how to balance the existing conservatism against some dependencies sometimes becoming stale. In particular, I'm concerned about the dependency-tree-as-declared-in-the-formula being wrong, and we definitely don't want to do the uninstall in those cases.

I think that we shouldn't be evaluating indirect dependencies when deciding which things can be uninstalled. We should only care if there is a direct dependency that is used by a formula. From what I understand only the indirect dependencies can go out-of-date. I'm pretty sure this is what naturally happens when we evaluate dependencies based on the formula description instead of the install receipt.

Do we care though if the install receipt is up-to-date or is it more important to record the dependencies as they were when they were first installed? It seems like if we update a formula A that we could check for all of the formulas that depend on A and recalculate their dependencies though that sounds expensive. I'm not sure if that's a priority though it would be another way to solve this problem.

To make this a bit clearer I see two possible solutions.

1. Always keep install receipts up-to-date. This will mean extra work when installing or reinstalling packages but means that we wouldn't have to change anything in the uninstall code.
2. Rewrite the algorithm to ignore indirect dependencies. Each indirect dependency should be a direct dependency of another formula so this shouldn't change the outcome but will help us avoid problems with out-of-date indirect dependencies listed in the install receipt.

[apainintheneck]

IMO the only issue here is the inconsistency really. If we ensure they are both 👍🏻 or 👎🏻 on the same formula: we're good here.

Ideally, that would result in more shared code between the two commands so they don't drift in future.

Yeah, it's not great that we have multiple algorithms in the codebase that evaluate whether a formula is an active dependency. Ideally we'd just have one that could be used in multiple circumstances. The problem is that they're not the same algorithm.

Autoremove

• File
  • Library/Homebrew/utils/autoremove.rb
• Algorithm
  • Autoremove.removable_formulae takes an array of formula and casks and recursively removes formula that other explicitly installed formula or casks depend on.

Uninstall

• File
  • Library/Homebrew/installed_dependents.rb
• Algorithm
  • InstalledDependents.find_some_installed_dependents takes a list of kegs and looks for any kegs or casks that depend on it.
  • This is used to throw an error during the uninstall process if the --force option is not passed to brew uninstall. https://github.com/Homebrew/brew/blob/2365c6bed513036d4d1733a42b2a7028c88c7290/Library/Homebrew/uninstall.rb#L110-L120

[MikeMcQuaid]

The problem is that they're not the same algorithm.

@apainintheneck Good catch! Could they somehow use the same algorithm, even if suboptimal for one of the approaches?

[apainintheneck]

I don't see any practical way to combine these algorithms though one of the annoying things is that we run both of them during brew autoremove since the second check is inside the uninstaller.

I'm in favor of just keeping the tab up-to-date at all times. This would mean recalculating the runtime dependencies portion whenever a bottle is installed or a new version of a formula is installed that other formulae depend on.

What worries me most about this approach is that for a few widely used dependencies this would mean recalculating that information for many formulae at once over multiple levels of the dependency tree. That sounds expensive but we should be able to skip it whenever the dependencies don't change.

[MikeMcQuaid]

I don't see any practical way to combine these algorithms though one of the annoying things is that we run both of them during brew autoremove since the second check is inside the uninstaller.

How about if we made InstalledDependents.find_some_installed_dependents:

• take formulae rather than kegs
• output the various dependents

and then Autoremove.removable_formulae could repeatedly call InstalledDependents.find_some_installed_dependents with the installed formulae as inputs to find which formulae cannot be removed (exiting early if/when all formulae have been eliminated).

With a bit of memoization it feels like this approach could be just as efficient. What do you think @apainintheneck?

[carlocab]

I'm a bit wary of recalculating dep trees without also checking linkage information (which I think we don't do because it's slow).

In particular, I am concerned about situations where foo links to bar indirectly through baz but then baz has the bar dependency removed for some reason. We definitely should not uninstall bar here, but I am concerned we might end up doing that if we recalculate dependencies at brew install or brew upgrade. Currently, using the install-time dependency tree prevents uninstalling bar even if baz is changed to not depend on bar.

[apainintheneck]

I'm a bit wary of recalculating dep trees without also checking linkage information (which I think we don't do because it's slow).

If its not feasible to recalculate dependency trees for performance reasons, maybe we should look into changing the algorithm somehow to ignore these situations. It's interesting how the Autoremove.removable_formulae algorithm didn't seem to have this problem in #13729. But yeah, I don't have a specific algorithm change in mind; I'd have to do a lot more research. It seems like there's got to be a better solution that what we currently have.

In particular, I am concerned about situations where foo links to bar indirectly through baz but then baz has the bar dependency removed for some reason. We definitely should not uninstall bar here, but I am concerned we might end up doing that if we recalculate dependencies at brew install or brew upgrade. Currently, using the install-time dependency tree prevents uninstalling bar even if baz is changed to not depend on bar.

Wow, I had not considered that. Do you know how often this happens or have any examples of this problem? And correct me if I'm wrong but this linkage info doesn't seem to be recorded anywhere else in the tab.

[apainintheneck]

I don't see any practical way to combine these algorithms though one of the annoying things is that we run both of them during brew autoremove since the second check is inside the uninstaller.

How about if we made InstalledDependents.find_some_installed_dependents:

• take formulae rather than kegs
• output the various dependents

and then Autoremove.removable_formulae could repeatedly call InstalledDependents.find_some_installed_dependents with the installed formulae as inputs to find which formulae cannot be removed (exiting early if/when all formulae have been eliminated).

With a bit of memoization it feels like this approach could be just as efficient. What do you think @apainintheneck?

That could work as refactor but there are two problems. One, that is the algorithm that is currently not working correctly when the info in the tab is outdated. And, two, we'd still have to find exceptions for things like not autoremoving packages that were built from source which was added recently. But yeah, I'm a big fan of the idea in general.

⚠️ Bikeshedding alert: There is a part of me though that wonders if we could create a general enough algorithm that would be able to replace other not so similar algorithms like those found in #recursive_deps_tree and TopologicalHash. I guess we lack a single generic abstraction for describing the dependency graph and so we end up doing a bunch of similar somewhat overlapping work throughout the codebase.

[MikeMcQuaid]

If its not feasible to recalculate dependency trees for performance reasons, maybe we should look into changing the algorithm somehow to ignore these situations.

I don't think so. We do use the linkage information when initially calculating this so I don't think it's ever appropriate to throw away without recalculating based on linkage which is too slow.

And correct me if I'm wrong but this linkage info doesn't seem to be recorded anywhere else in the tab.

Yeh, it is through the runtime_dependencies.

One, that is the algorithm that is currently not working correctly when the info in the tab is outdated.

I don't think this is a problem really. I think the inconsistency is the actual/main problem.

And, two, we'd still have to find exceptions for things like not autoremoving packages that were built from source which was added recently.

Yeh, that seems doable with what I proposed with an extra "ok InstalledDependents.find_some_installed_dependents said I can remove all these but I checked the tab and have filtered them out based on that" logic. It doesn't matter if autoremove is more conservative than uninstall, it just needs to never be less conservative.

I guess we lack a single generic abstraction for describing the dependency graph and so we end up doing a bunch of similar somewhat overlapping work throughout the codebase.

Agreed. Not bikeshedding, would love to see this sort of improvement. Just want to be sure that we don't let "perfect be the enemy of good" in trying to get to a slightly better solution to this specific problem first.

[apainintheneck]

Ideally, I'd like to shoot for correctness but working to make the code consistent in the meantime makes sense especially since this would likely become a performance issue with what I've already proposed. I also have no idea what the scale of this problem is. We have one report of a failed uninstall here and then two cases of brew autoremove and brew uninstall disagreeing with each other (am I missing anything else?). Since we haven't heard more complaints, it makes me think that we are just being conservative which, while not ideal, is not the end of the world. It'd be a bigger issue if this was causing installed packages to fail because we accidentally removed runtime dependencies.

Yeh, that seems doable with what I proposed with an extra "ok InstalledDependents.find_some_installed_dependents said I can remove all these but I checked the tab and have filtered them out based on that" logic. It doesn't matter if autoremove is more conservative than uninstall, it just needs to never be less conservative.

Agreed, I'm fine with any solution that makes these two commands consistent even if autoremove ends up being more conservative. I'm also curious to see what that algorithm refactor would look like.

Agreed. Not bikeshedding, would love to see this sort of improvement. Just want to be sure that we don't let "perfect be the enemy of good" in trying to get to a slightly better solution to this specific problem first.

Maybe bikeshedding wasn't the right word there but either way it's obviously outside of the scope of this issue and I wanted to make that clear. IMO that would require a major rethink of the codebase. Should I open another issue to discuss this further?

[MikeMcQuaid]

Ideally, I'd like to shoot for correctness but working to make the code consistent in the meantime makes sense especially since this would likely become a performance issue with what I've already proposed.

I'm still unconvinced the current e.g. tab behaviour is not correct. I'm also dubious that this would be a significant performance issue here without profiling indicating this.

It'd be a bigger issue if this was causing installed packages to fail because we accidentally removed runtime dependencies.

Strongly agree 👍🏻

Should I open another issue to discuss this further?

Probably not 😁. This is the best thing to discuss via e.g. WIP PRs rather than issues, IMO.

[apainintheneck]

I'm still unconvinced the current e.g. tab behaviour is not correct. I'm also dubious that this would be a significant performance issue here without profiling indicating this.

Isn't that what we've been discussing this whole time? I'm very confused. We're all in agreement that the runtime dependencies of a tab can go out-of-date causing discrepancies between brew uninstall and brew autoremove and stopping people from being able to remove unused dependencies without also passing the --force flag. That is a correctness issue whether or not we want to prioritize it. Am I missing something?

In terms of the potential performance issue, I was going on what was said in this thread about how slow the linkage checks are which is mentioned in multiple places. You are right that I haven't actually benchmarked anything. That's not a part of the codebase I'm familiar with so I'd have to go look at it.

Probably not 😁. This is the best thing to discuss via e.g. WIP PRs rather than issues, IMO.

Sounds good. 👍

[apainintheneck]

Is #14121 related at all to what we've been talking about here?

[MikeMcQuaid]

Isn't that what we've been discussing this whole time? I'm very confused. We're all in agreement that the runtime dependencies of a tab can go out-of-date causing discrepancies between brew uninstall and brew autoremove and stopping people from being able to remove unused dependencies without also passing the --force flag. That is a correctness issue whether or not we want to prioritize it. Am I missing something?

No, sorry, but I was 😁

Is #14121 related at all to what we've been talking about here?

Yeh, I think somewhat although that may fit into the "runtime_dependencies is actually correct and the formula is wrong for you due to opportunistic linking" case.

[ericbn]

Yea, it does. A workaround for new is to brew reinstall cairo graphene. But we should handle this properly.

I replaced doing:

$ brew upgrade --formula --ignore-pinned

by:

$ brew update && comm -23 <(brew outdated --formula) <(brew list --formula --pinned) | xargs brew reinstall --formula

Would this be the correct "generic" workaround?

EDIT: The possible drawback here is that reinstalled formulae with be marked as "installed-on-request" instead of "installed-as-dependency"...

[MikeMcQuaid]

This is a long-running issue enough I'm not sure leaving it open is terrible actionable. Will review PRs to improve things but given the best part of a year with no movement here: closing it out.