Dependency resolution error message generator consumes ridiculous amounts of memory for large conflict trees

[halfbyte]

Debugging a failing dependency update for a Depfu client, I found out that if the conflict tree gets to a certain size, the code to display the reduced conflict set consumes way too much memory. I've never let it finish but usually stopped the code when reaching the 4GB mark.

I've identified the following change as the culprit:

5ebc8c1#diff-a068dff3f4ba60cbf2c11bc4e65eed02R27

The code moved a bit since then and is currently at https://github.com/bundler/bundler/blob/f093e405a8e10bafa0b5d4621069a0b7ad86c37f/lib/bundler/resolver.rb#L311

The issue here is the use of Array#combination. The specific conflict trees array had a length of 26. Here's a simple test case to consume a ton of memory on your machine to exemplify the problem:

([1] * 26).combination(12)

(and please note that the bundler code from above would do that for every value from 1 to 26 as input for Array#combination.)

How to fix this?

One thing I noticed is that the unreduced "trees" variable contains a lot of 1:1 dupes. I've removed them with the following (not very elegant) code, inserted before line 310:

trees.uniq! { |tree| [tree.first, tree.last] }

As my knowledge of the resolving process is limited, I am not sure if this will somehow ruin the intended output. It does bring down my 26 trees to 12 after which the reduction still takes a good 10 seconds or so on my machine but consumes way less memory. Not optimal, but better.

As I am afraid that the 26 I encountered are not the theoretical maximum of conflict trees, I think it would be a good idea to add a bailout clause, so that if the deduped trees size is > 10 or so, the reduction is skipped, which would change the full lambda to:

trees.uniq! {|tree| [tree.first, tree.last] }
if trees.size <= 10
  maximal = 1.upto(trees.size).map do |size|
    trees.map(&:last).flatten(1).combination(size).to_a
  end.flatten(1).select do |deps|
    Bundler::VersionRanges.empty?(*Bundler::VersionRanges.for_many(deps.map(&:requirement)))
  end.min_by(&:size)
  trees.reject! {|t| !maximal.include?(t.last) } if maximal

  trees = trees.sort_by {|t| t.flatten.map(&:to_s) }
  trees.uniq! {|t| t.flatten.map {|dep| [dep.name, dep.requirement] } }

  trees = trees.sort_by {|t| t.reverse.map(&:name) }
end
trees

I'm happy to provide a PR if this sounds plausible to y'all. Not sure I am able to provide a non synthetic example (need to check that with our client), though. I'm pretty sure I'll need some guidance in terms of how to properly test this.

Of course this is a special case as the Gemfile is a particularly large one, but the one gem that makes the conflict trees so large is of course ActiveSupport and yeah, maybe it's not such a special case after all. I think it is fair to assume that any significantly large rails application with lots of "rails plugins" might run into similar issues when trying to forcefully update a dependency depending on a higher version of ActiveSupport.

[segiddins]

Thanks for the issue! I think we'd need an example to be able to "fix" it, but in the meantime bailing out after a certain point seems like a good idea

[halfbyte]

@segiddins Ok, let me try to provide a synthetic extraction from my client's Gemfile. Should be doable. But first: Sleep. :)

[halfbyte]

@segiddins Okay, here we go: This Gist contains a Gemfile/Gemfile.lock that will cause the error. Steps to repro:

1. Download gist content into a folder
2. cd into folder
3. run bundle update grape-entity in that folder

What you should see is massive memory usage and almost infinite run time. (Actually I have no idea how long this will run, I never let it finish)

The two fixes outlined above seem to work for me. Again, I'm unsure about the uniq, as I don't know if this will suppress valuable info (my guess is no, since different routes through the dependencies will end up with different instances at the end of the graphs).

As I said, I am willing to prepare a PR, if you could assist and advise me on a testing strategy for this.

[segiddins]

I think at first a PR capping the number of conflict trees and not trying to reduce them after that point would be a good place to start -- we could add a test after merging, and then try to make the algorithm more efficient on larger inputs afterwords.

[indirect]

Fixed by #6145