Auto merge of #5542 - bundler:seg-conflict-minimal-dependencies, r=indirect

[Resolver] Only include minimal set of conflicting deps in conflict message

This implements a feature that @indirect thought up last week.
Previously, when a resolver conflict occurred, bundler would print _all_ the "conflicting" dependencies, even if some of them were not an issue! No longer. Now, we'll compute the minimal set of conflicting dependencies and only print out the requirement trees for those, which should hopefully make conflict messages less confusing and more actionable for users.

I have some tests for the `VersionRanges` module that I'll push up in a few minutes, but a test for the feature itself is already included.

5 files changed, 145 insertions, 1 deletions

diff --git a/lib/bundler.rb b/lib/bundler.rb
index 63a9f5784c..1969f36a71 100644
--- a/lib/bundler.rb
+++ b/lib/bundler.rb
@@ -55,6 +55,7 @@ module Bundler
   autoload :StubSpecification,      "bundler/stub_specification"
   autoload :UI,                     "bundler/ui"
   autoload :URICredentialsFilter,   "bundler/uri_credentials_filter"
+  autoload :VersionRanges,          "bundler/version_ranges"
 
   class << self
     attr_writer :bundle_path
diff --git a/lib/bundler/resolver.rb b/lib/bundler/resolver.rb
index b8d044e6ef..db2ae496a4 100644
--- a/lib/bundler/resolver.rb
+++ b/lib/bundler/resolver.rb
@@ -21,7 +21,16 @@ module Bundler
             o << %(\n)
           end
           o << %(  In Gemfile:\n)
-          o << conflict.requirement_trees.sort_by {|t| t.reverse.map(&:name) }.map do |tree|
+          trees = conflict.requirement_trees
+
+          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
+
+          o << trees.sort_by {|t| t.reverse.map(&:name) }.map do |tree|
             t = String.new
             depth = 2
             tree.each do |req|
diff --git a/lib/bundler/version_ranges.rb b/lib/bundler/version_ranges.rb
new file mode 100644
index 0000000000..1ee8440edd
--- /dev/null
+++ b/lib/bundler/version_ranges.rb
@@ -0,0 +1,75 @@
+# frozen_string_literal: true
+module Bundler
+  module VersionRanges
+    NEq = Struct.new(:version)
+    ReqR = Struct.new(:left, :right)
+    class ReqR
+      Endpoint = Struct.new(:version, :inclusive)
+      def to_s
+        "#{left.inclusive ? "[" : "("}#{left.version}, #{right.version}#{right.inclusive ? "]" : ")"}"
+      end
+      INFINITY = Object.new.freeze
+      ZERO = Gem::Version.new("0.a")
+
+      def cover?(v)
+        return false if left.inclusive && left.version > v
+        return false if !left.inclusive && left.version >= v
+
+        if right.version != INFINITY
+          return false if right.inclusive && right.version < v
+          return false if !right.inclusive && right.version <= v
+        end
+
+        true
+      end
+
+      def empty?
+        left.version == right.version && !(left.inclusive && right.inclusive)
+      end
+
+      def single?
+        left.version == right.version
+      end
+
+      UNIVERSAL = ReqR.new(ReqR::Endpoint.new(Gem::Version.new("0.a"), true), ReqR::Endpoint.new(ReqR::INFINITY, false)).freeze
+    end
+
+    def self.for_many(requirements)
+      requirements = requirements.map(&:requirements).flatten(1).map {|r| r.join(" ") }
+      requirements << ">= 0.a" if requirements.empty?
+      requirement = Gem::Requirement.new(requirements)
+      self.for(requirement)
+    end
+
+    def self.for(requirement)
+      ranges = requirement.requirements.map do |op, v|
+        case op
+        when "=" then ReqR.new(ReqR::Endpoint.new(v, true), ReqR::Endpoint.new(v, true))
+        when "!=" then NEq.new(v)
+        when ">=" then ReqR.new(ReqR::Endpoint.new(v, true), ReqR::Endpoint.new(ReqR::INFINITY, false))
+        when ">" then ReqR.new(ReqR::Endpoint.new(v, false), ReqR::Endpoint.new(ReqR::INFINITY, false))
+        when "<" then ReqR.new(ReqR::Endpoint.new(ReqR::ZERO, true), ReqR::Endpoint.new(v, false))
+        when "<=" then ReqR.new(ReqR::Endpoint.new(ReqR::ZERO, true), ReqR::Endpoint.new(v, true))
+        when "~>" then ReqR.new(ReqR::Endpoint.new(v, true), ReqR::Endpoint.new(v.bump, false))
+        else raise "unknown version op #{op} in requirement #{requirement}"
+        end
+      end.uniq
+      ranges, neqs = ranges.partition {|r| !r.is_a?(NEq) }
+
+      [ranges.sort_by {|range| [range.left.version, range.left.inclusive ? 0 : 1] }, neqs.map(&:version)]
+    end
+
+    def self.empty?(ranges, neqs)
+      !ranges.reduce(ReqR::UNIVERSAL) do |last_range, curr_range|
+        next false unless last_range
+        next false if curr_range.single? && neqs.include?(curr_range.left.version)
+        next curr_range if last_range.right.version == ReqR::INFINITY
+        case last_range.right.version <=> curr_range.left.version
+        when 1 then next curr_range
+        when 0 then next(last_range.right.inclusive && curr_range.left.inclusive && !neqs.include?(curr_range.left.version) && curr_range)
+        when -1 then next false
+        end
+      end
+    end
+  end
+end
diff --git a/spec/bundler/version_ranges_spec.rb b/spec/bundler/version_ranges_spec.rb
new file mode 100644
index 0000000000..f746aa88ad
--- /dev/null
+++ b/spec/bundler/version_ranges_spec.rb
@@ -0,0 +1,37 @@
+# frozen_string_literal: true
+require "spec_helper"
+require "bundler/version_ranges"
+
+RSpec.describe Bundler::VersionRanges do
+  describe ".empty?" do
+    shared_examples_for "empty?" do |exp, *req|
+      it "returns #{exp} for #{req}" do
+        r = Gem::Requirement.new(*req)
+        ranges = described_class.for(r)
+        expect(described_class.empty?(*ranges)).to eq(exp), "expected `#{r}` #{exp ? "" : "not "}to be empty"
+      end
+    end
+
+    include_examples "empty?", false
+    include_examples "empty?", false, "!= 1"
+    include_examples "empty?", false, "!= 1", "= 2"
+    include_examples "empty?", false, "!= 1", "> 1"
+    include_examples "empty?", false, "!= 1", ">= 1"
+    include_examples "empty?", false, "= 1", ">= 0.1", "<= 1.1"
+    include_examples "empty?", false, "= 1", ">= 1", "<= 1"
+    include_examples "empty?", false, "= 1", "~> 1"
+    include_examples "empty?", false, ">= 0.z", "= 0"
+    include_examples "empty?", false, ">= 0"
+    include_examples "empty?", false, ">= 1.0.0", "< 2.0.0"
+    include_examples "empty?", false, "~> 1"
+    include_examples "empty?", false, "~> 2.0", "~> 2.1"
+    include_examples "empty?", true, "!= 1", "< 2", "> 2"
+    include_examples "empty?", true, "!= 1", "<= 1", ">= 1"
+    include_examples "empty?", true, "< 2", "> 2"
+    include_examples "empty?", true, "= 1", "!= 1"
+    include_examples "empty?", true, "= 1", "= 2"
+    include_examples "empty?", true, "= 1", "~> 2"
+    include_examples "empty?", true, ">= 0", "<= 0.a"
+    include_examples "empty?", true, "~> 2.0", "~> 3"
+  end
+end
diff --git a/spec/resolver/basic_spec.rb b/spec/resolver/basic_spec.rb
index 69881d1019..9e93847ab5 100644
--- a/spec/resolver/basic_spec.rb
+++ b/spec/resolver/basic_spec.rb
@@ -53,6 +53,28 @@ RSpec.describe "Resolving" do
     end.to raise_error(Bundler::VersionConflict)
   end
 
+  it "raises an exception with the minimal set of conflicting dependencies" do
+    @index = build_index do
+      %w(0.9 1.0 2.0).each {|v| gem("a", v) }
+      gem("b", "1.0") { dep "a", ">= 2" }
+      gem("c", "1.0") { dep "a", "< 1" }
+    end
+    dep "a"
+    dep "b"
+    dep "c"
+    expect do
+      resolve
+    end.to raise_error(Bundler::VersionConflict, <<-E.strip)
+Bundler could not find compatible versions for gem "a":
+  In Gemfile:
+    b was resolved to 1.0, which depends on
+      a (>= 2)
+
+    c was resolved to 1.0, which depends on
+      a (< 1)
+    E
+  end
+
   it "should throw error in case of circular dependencies" do
     @index = a_circular_index
     dep "circular_app"