Requirements of children that are swapped out are not removed, adding "phantom constraints" and breaking resolution

[maxvt]

Hi, I'm a Berkshelf user facing an issue where a resolution fails due to a constraint that does not actually exist in the solver input. For the background, please see https://github.com/berkshelf/solve/issues/62. The rest is Molinillo-specific investigation.

This is the solver run, you can see that the first version tried is homebrew-2.1.2, and just before performing the swap the payload has a single dependency, build-essential >= 2.1.2:

Creating possibility state for homebrew (>= 0.0.0) (29 remaining)
Attempting to activate homebrew-2.1.2
Activated homebrew at homebrew-2.1.2
Requiring nested dependencies (build-essential (>= 2.1.2))
Creating possibility state for homebrew (= 1.10.0) (1 remaining)
Attempting to activate homebrew-1.10.0
Found existing spec (homebrew-2.1.2)

      def attempt_to_swap_possibility
        binding.pry if name == 'homebrew'
        activated.tag(:swap)

[3] pry(#<Molinillo::Resolver::Resolution>)> v.name
=> "homebrew"
[4] pry(#<Molinillo::Resolver::Resolution>)> v.payload.version
=> #<Semverse::Version 2.1.2>
[5] pry(#<Molinillo::Resolver::Resolution>)> v.payload.dependencies.size
=> 1
[6] pry(#<Molinillo::Resolver::Resolution>)> v.payload.dependencies.first.name
=> "build-essential"
[7] pry(#<Molinillo::Resolver::Resolution>)> v.payload.dependencies.first.constraint
=> #<Semverse::Constraint >= 2.1.2>

Ok, step into fixup_swapped_children, we see that the successor (build-essential) is not removed, since other cookbooks depend on it:

Fixing up swapped children for (homebrew)
There are 20 predecessors for (build-essential)

    359: def fixup_swapped_children(vertex)
    360:   debug(depth) { "Fixing up swapped children for (#{vertex.name})" }
    361:
    362:   payload = vertex.payload
    363:   dep_names = dependencies_for(payload).map(&method(:name_for))
    364:   vertex.successors.each do |succ|
    365:     debug(depth) { "There are #{succ.predecessors.to_a.size} predecessors for (#{succ.name})" }
 => 366:     binding.pry if name == 'homebrew'
    367:     if !dep_names.include?(succ.name) && !succ.root? && succ.predecessors.to_a == [vertex]
    368:       debug(depth) { "Removing orphaned spec #{succ.name} after swapping #{name}" }
    369:       activated.detach_vertex_named(succ.name)
    370:
    371:       all_successor_names = succ.recursive_successors.map(&:name)
    372:
    373:       requirements.delete_if do |requirement|
    374:         requirement_name = name_for(requirement)
    375:         (requirement_name == succ.name) || all_successor_names.include?(requirement_name)
    376:       end
    377:     end
    378:   end
    379: end

After the swap, you can see the new possibility selected has no dependencies:

[1] pry(#<Molinillo::Resolver::Resolution>)> payload.dependencies
=> []
[2] pry(#<Molinillo::Resolver::Resolution>)> payload.name
=> "homebrew"
[3] pry(#<Molinillo::Resolver::Resolution>)> payload.version
=> #<Semverse::Version 1.10.0>

but the requirement introduced by the possibility that was swapped out is not removed (it was not done in fixup_swapped_children since the successor is not an orphan, and I don't see related logic anywhere else...):

[1] pry(#<Molinillo::Resolver::Resolution>)> r = requirements.find_all { |r| 'build-essential' == name_for(r) };

[5] pry(#<Molinillo::Resolver::Resolution>)> r.to_a.each{|req| print "#{req.constraint}\n"};
>= 0.0.0
>= 0.0.0
>= 0.0.0
>= 0.0.0
>= 0.0.0
>= 0.0.0
>= 0.0.0
>= 0.0.0
>= 0.0.0
>= 0.0.0
>= 0.0.0
>= 0.0.0
>= 0.0.0
>= 0.0.0
>= 0.0.0
>= 0.0.0
>= 0.0.0
>= 0.0.0
>= 0.0.0
>= 2.1.2

resuming, we get:
Activated homebrew at homebrew-1.10.0
Requiring nested dependencies ()

so that (phantom) requirement for build-essential 2.1.2 sticks around, eventually a (real) conflicting requirement is introduced, and resolution fails:

Unwinding for conflict: build-essential (~> 1.4)
Finished dependency resolution
Finished resolution (5929 steps) (Took 1.796806 seconds) (2016-10-07 17:19:33 -0400)
Unable to satisfy the following requirements:

- `build-essential (>= 0.0.0)` required by `some package`
...
- `build-essential (>= 2.1.2)` required by `homebrew-1.10.0` (there is no such constraint in the solver input!)
...
- `build-essential (~> 1.4)` required by `package that actually needs 1.4`

I don't understand the logic of Molinillo enough to understand what's the correct solution. Presumably, requirements that are no longer needed (present in possibility that was swapped out, but absent in the new possibility) need to be removed; but how to find the correct requirements to remove, whether a new state needs to be pushed or rewound as a result of the changing requirements, and so on are unclear to me.

This introduces all kinds of weird behavior up the stack, issues that are resolved by adding version pins, removing pins, all kinds of placebo solutions that do not actually address what seems to be the actual problem at this level. Any help would be greatly appreciated.

[segiddins]

See https://github.com/CocoaPods/Molinillo/pull/45

[maxvt]

@segiddins, thank you for the pointer. I have tried the fix in #45 and it does not completely resolve the issue - now I get a different conflict, with fewer steps until failure compared to the previous code:

- `ohai (= 1.1.12)` required by `user-specified dependency`
- `ohai (>= 0.0.0)` required by `sysctl-0.7.0`
- `ohai (~> 4.0)` required by `sysctl-0.7.0`

The last one is a phantom dependency, it does not exist in the input data. At a first glance this can be verified by going to https://supermarket.chef.io/cookbooks/sysctl/versions/0.7.0#dependencies

[maxvt]

@segiddins, the problem seems to be that the possibility being swapped out has different requirements from the possibility being swapped in, but those requirement lists are simply combined.

If fixup_swapped_children is the correct place to do that processing, it seems to me there are two issues with the current code:

1. ohai is a dependency of both new and old possibilities, so requirements are never considered in fixup_swapped_children
2. even if requirements were considered, the difference is not in the name of the requirement, it is in the semantic versioning constraint, so code that only looks at the name of the constraint cannot be sufficient.

Creating possibility state for sysctl (>= 0.0.0) (24 remaining)
Attempting to activate sysctl-0.8.0
Activated sysctl at sysctl-0.8.0
Requiring nested dependencies (ohai (~> 4.0))
...
Creating possibility state for sysctl (= 0.7.0) (1 remaining)
Attempting to activate sysctl-0.7.0
Found existing spec (sysctl-0.8.0)
Fixing up swapped children for (sysctl)

[maxvt]

@segiddins, what do you think of the following? This fixes my problem, but I'm not sure if there are unintended side effects. Based on your change #45.

      def fixup_swapped_children(vertex)
        payload = vertex.payload
        deps = dependencies_for(payload)
        dep_names = dependencies_for(payload).map(&method(:name_for))
        debug(depth) { "Fixing up swapped children for (#{vertex.name})" }

        vertex.outgoing_edges.each do |outgoing_edge|
          @parent_of[outgoing_edge.requirement] = states.size - 1
          succ = outgoing_edge.destination
          if !deps.include? (outgoing_edge.requirement) && !succ.root? && succ.predecessors.to_a == [vertex]
            debug(depth) { "Removing orphaned spec #{succ.name} after swapping #{name}" }
            succ.requirements.each { |r| @parent_of.delete(r) }
            activated.detach_vertex_named(succ.name)

            all_successor_names = succ.recursive_successors.map(&:name)

            requirements.delete_if do |requirement|
              requirement_name = name_for(requirement)
              (requirement_name == succ.name) || all_successor_names.include?(requirement_name)
            end
          end
        end
      end

Requirements satisfied, combining and pushing state (packagecloud-0.2.5)
Creating possibility state for sysctl (>= 0.0.0) (24 remaining)
Attempting to activate sysctl-0.8.0
Found existing spec (sysctl-0.8.0)
Requirements satisfied, combining and pushing state (sysctl-0.8.0)
Creating possibility state for sysctl (= 0.7.0) (1 remaining)
Attempting to activate sysctl-0.7.0
Found existing spec (sysctl-0.8.0)
Dependencies for current vertex sysctl.0.8.0:
ohai ~> 4.0
Dependencies for possibility sysctl.0.7.0:
ohai >= 0.0.0
Fixing up swapped children for (sysctl)
Removing orphaned spec ohai after swapping sysctl
Activated sysctl at sysctl-0.7.0
Requiring nested dependencies (ohai (>= 0.0.0))

[maxvt]

I found this chunk of debug code to be very helpful in seeing what's going on:

      def attempt_to_swap_possibility
        activated.tag(:swap)
        vertex = activated.vertex_named(name)
        debug(depth) { "Dependencies for current vertex #{name}.#{vertex.payload.version}:"}
        vertex.payload.dependencies.each do |d|
          debug(depth) { "#{d.name} #{d.constraint}"}
        end

        debug(depth) { "Dependencies for possibility #{name}.#{possibility.version}:"}
        possibility.dependencies.each do |d|
          debug(depth) { "#{d.name} #{d.constraint}"}
        end

[segiddins]

@maxvt can you please make a PR with a test case so we can ensure we don't regress? Thanks!

[segiddins]

diff --git a/lib/molinillo/resolution.rb b/lib/molinillo/resolution.rb
index d92b09d..1120cc7 100644
--- a/lib/molinillo/resolution.rb
+++ b/lib/molinillo/resolution.rb
@@ -356,11 +356,12 @@ module Molinillo
       # @return [void]
       def fixup_swapped_children(vertex)
         payload = vertex.payload
-        dep_names = dependencies_for(payload).map(&method(:name_for))
+        deps = dependencies_for(payload).group_by(&method(:name_for))
         vertex.outgoing_edges.each do |outgoing_edge|
           @parent_of[outgoing_edge.requirement] = states.size - 1
           succ = outgoing_edge.destination
-          if !dep_names.include?(succ.name) && !succ.root? && succ.predecessors.to_a == [vertex]
+          matching_deps = Array(deps[succ.name])
+          if matching_deps.empty? && !succ.root? && succ.predecessors.to_a == [vertex]
             debug(depth) { "Removing orphaned spec #{succ.name} after swapping #{name}" }
             succ.requirements.each { |r| @parent_of.delete(r) }
             activated.detach_vertex_named(succ.name)
@@ -371,7 +372,10 @@ module Molinillo
               requirement_name = name_for(requirement)
               (requirement_name == succ.name) || all_successor_names.include?(requirement_name)
             end
+          elsif !matching_deps.include?(outgoing_edge.requirement)
+            outgoing_edge.requirement = matching_deps.first
           end
+          matching_deps.delete(outgoing_edge.requirement)
         end
       end

Ought to fix it, but I'm hesitant to commit without a failing test

[segiddins]

@maxvt ping on a failing Molinillo test case for this?

[maxvt]

@segiddins Sorry, it took me a while to find some free time and learn how Molinillo testing works. I modified an existing test case and added a new package with the same name, that scenario looks like it manages to hit this problem. Here's a log with a bunch of debugging output thrown in:

            Creating possibility state for build-essential (~> 2.0.0) (1 remaining)
              Attempting to activate build-essential (2.4.0)
              Found existing spec (build-essential (3.2.0))
              Dependencies for current vertex build-essential.3.2.0:
              seven_zip (>= 0.0.0)
              some_package (>= 1.0.0)
              Dependencies for possibility build-essential.2.4.0:
              7-zip (>= 0.0.0)
              some_package (~> 0.1.0)
              Fixing up swapped children for (build-essential)
              Removing orphaned spec seven_zip after swapping build-essential
              Deleting requirement seven_zip (>= 0.0.0) from parent_of
              Considering requirement yum-epel (~> 0.3.0)
              Activated build-essential at build-essential (2.4.0)
              Requiring nested dependencies (7-zip (>= 0.0.0), some_package (~> 0.1.0))
              Creating possibility state for some_package (~> 0.1.0) (1 remaining)
                Attempting to activate some_package (0.1.0)
                Found existing spec (some_package (1.0.0))
                Dependencies for current vertex some_package.1.0.0:
                Dependencies for possibility some_package.0.1.0:
                Rewinding
                Unsatisfied by existing spec (some_package (1.0.0))
                Unwinding for conflict: some_package (~> 0.1.0)

[segiddins]

Thanks, I'm looking into it now and I think I understand what's going on. No promise when I can figure it out, though

[segiddins]

diff --git a/spec/spec_helper/index.rb b/spec/spec_helper/index.rb
index 9625e9e..16f807e 100644
--- a/spec/spec_helper/index.rb
+++ b/spec/spec_helper/index.rb
@@ -32,6 +32,7 @@ module Molinillo
             dependency.satisfied_by?(spec.version)
         end
       end
+      @search_for[dependency].dup
     end

     def name_for(dependency)

[maxvt]

Not sure what that change means - was the fixture (TestIndex) bad?

Doesn't look like it picks the optimal version of nginx, definitely not what the test expects to happen. What forces it to 0.2.0?

[segiddins]

The test passed with that diff

[maxvt]

I pulled the latest master and the test is still failing for me. I do not know why it passes for you. I tried switching the test index to ordering specified by BundlerIndex -- is the result any different?

[segiddins]

Please merge the PR that I sent to your fork