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

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(#)> v.name
=> "homebrew"
[4] pry(#)> v.payload.version
=> #
[5] pry(#)> v.payload.dependencies.size
=> 1
[6] pry(#)> v.payload.dependencies.first.name
=> "build-essential"
[7] pry(#)> v.payload.dependencies.first.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(#)> payload.dependencies
=> []
[2] pry(#)> payload.name
=> "homebrew"
[3] pry(#)> payload.version
=> #
```

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(#)> r = requirements.find_all { |r| 'build-essential' == name_for(r) };

[5] pry(#)> 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.

Start with Resolution#attempt_to_swap_possibility and Resolution#fixup_swapped_children, using the supplied pry trace to follow how requirements change when homebrew-2.1.2 is replaced by homebrew-1.10.0. Inspect the requirements bookkeeping around swapped successors. Done means the removed possibility's build-essential constraint is no longer retained and the described resolution can proceed without the phantom constraint.

Written by the indexing model from the issue text.