CocoaPods / CocoaPods/Molinillo

Molinillo cannot find the path of two vertices that there is a circular dependency

Open
#162 1 comment 0 reactions 0 assignees View on GitHub
Dominant language
Ruby
Stars
420
Forks
41
PR merge metrics
No merged PRs in 30d

Description

### Error

```
ArgumentError - There is no path from A to D
/Users/shuzhen/.rvm/gems/ruby-3.0.0/gems/molinillo-0.8.0/lib/molinillo/dependency_graph.rb:259:in `path'
/Users/shuzhen/.rvm/gems/ruby-3.0.0/gems/molinillo-0.8.0/lib/molinillo/dependency_graph.rb:193:in `add_edge'
/Users/shuzhen/.rvm/gems/ruby-3.0.0/gems/molinillo-0.8.0/lib/molinillo/dependency_graph.rb:152:in `block in add_child_vertex'
/Users/shuzhen/.rvm/gems/ruby-3.0.0/gems/molinillo-0.8.0/lib/molinillo/dependency_graph.rb:150:in `each'
/Users/shuzhen/.rvm/gems/ruby-3.0.0/gems/molinillo-0.8.0/lib/molinillo/dependency_graph.rb:150:in `add_child_vertex'
/Users/shuzhen/.rvm/gems/ruby-3.0.0/gems/molinillo-0.8.0/lib/molinillo/resolution.rb:738:in `block in require_nested_dependencies_for'
/Users/shuzhen/.rvm/gems/ruby-3.0.0/gems/molinillo-0.8.0/lib/molinillo/resolution.rb:737:in `each'
/Users/shuzhen/.rvm/gems/ruby-3.0.0/gems/molinillo-0.8.0/lib/molinillo/resolution.rb:737:in `require_nested_dependencies_for'
/Users/shuzhen/.rvm/gems/ruby-3.0.0/gems/molinillo-0.8.0/lib/molinillo/resolution.rb:727:in `activate_new_spec'
/Users/shuzhen/.rvm/gems/ruby-3.0.0/gems/molinillo-0.8.0/lib/molinillo/resolution.rb:684:in `attempt_to_activate'
/Users/shuzhen/.rvm/gems/ruby-3.0.0/gems/molinillo-0.8.0/lib/molinillo/resolution.rb:254:in `process_topmost_state'
/Users/shuzhen/.rvm/gems/ruby-3.0.0/gems/molinillo-0.8.0/lib/molinillo/resolution.rb:182:in `resolve'
/Users/shuzhen/.rvm/gems/ruby-3.0.0/gems/molinillo-0.8.0/lib/molinillo/resolver.rb:43:in `resolve'
/Users/shuzhen/.rvm/gems/ruby-3.0.0/gems/cocoapods-1.11.3/lib/cocoapods/resolver.rb:94:in `resolve'
/Users/shuzhen/.rvm/gems/ruby-3.0.0/gems/cocoapods-1.11.3/lib/cocoapods/installer/analyzer.rb:1078:in `block in resolve_dependencies'
/Users/shuzhen/.rvm/gems/ruby-3.0.0/gems/cocoapods-1.11.3/lib/cocoapods/user_interface.rb:64:in `section'
/Users/shuzhen/.rvm/gems/ruby-3.0.0/gems/cocoapods-1.11.3/lib/cocoapods/installer/analyzer.rb:1076:in `resolve_dependencies'
/Users/shuzhen/.rvm/gems/ruby-3.0.0/gems/cocoapods-1.11.3/lib/cocoapods/installer/analyzer.rb:124:in `analyze'
/Users/shuzhen/.rvm/gems/ruby-3.0.0/gems/cocoapods-1.11.3/lib/cocoapods/installer.rb:416:in `analyze'
/Users/shuzhen/.rvm/gems/ruby-3.0.0/gems/cocoapods-1.11.3/lib/cocoapods/installer.rb:241:in `block in resolve_dependencies'
/Users/shuzhen/.rvm/gems/ruby-3.0.0/gems/cocoapods-1.11.3/lib/cocoapods/user_interface.rb:64:in `section'
/Users/shuzhen/.rvm/gems/ruby-3.0.0/gems/cocoapods-1.11.3/lib/cocoapods/installer.rb:240:in `resolve_dependencies'
/Users/shuzhen/.rvm/gems/ruby-3.0.0/gems/cocoapods-1.11.3/lib/cocoapods/installer.rb:161:in `install!'
/Users/shuzhen/.rvm/gems/ruby-3.0.0/gems/cocoapods-1.11.3/lib/cocoapods/command/install.rb:52:in `run'
/Users/shuzhen/.rvm/gems/ruby-3.0.0/gems/claide-1.1.0/lib/claide/command.rb:334:in `run'
/Users/shuzhen/.rvm/gems/ruby-3.0.0/gems/cocoapods-1.11.3/lib/cocoapods/command.rb:52:in `run'
/Users/shuzhen/.rvm/gems/ruby-3.0.0/gems/cocoapods-1.11.3/bin/pod:55:in `'
/Users/shuzhen/.rvm/gems/ruby-3.0.0/bin/pod:23:in `load'
/Users/shuzhen/.rvm/gems/ruby-3.0.0/bin/pod:23:in `'
/Users/shuzhen/.rvm/gems/ruby-3.0.0/bin/ruby_executable_hooks:22:in `eval'
/Users/shuzhen/.rvm/gems/ruby-3.0.0/bin/ruby_executable_hooks:22:in `'
```

Hi, I found an error that looks like a bug of Molinillo.
I have a demo that contains 4 pod: A, B, C and D.
There is a circular dependency in them, and the path is A -> C -> B -> D -> A.
When pod install, Molinillo raises this error, says there is no path from A to D, but the path is actually existed.
I try to add some debug codes in Molinillo to figure out how the error raised.

### Code
```
# Returns the path between two vertices
# @raise [ArgumentError] if there is no path between the vertices
# @param [Vertex] from
# @param [Vertex] to
# @return [Array] the shortest path from `from` to `to`
def path(from, to)
distances = Hash.new(vertices.size + 1)
distances[from.name] = 0
predecessors = {}
puts "distances : #{distances}"
puts "predecessors : #{predecessors}"
each do |vertex|
puts "\n"
puts "#{vertex.name}(#{distances[vertex.name]})"
vertex.successors.each do |successor|
puts "-- #{successor.name}(#{distances[successor.name]})"
if distances[successor.name] > distances[vertex.name] + 1
distances[successor.name] = distances[vertex.name] + 1
puts "-- update #{successor.name} distance to #{distances[successor.name]}"
predecessors[successor] = vertex
puts "-- log `#{successor.name} -> #{vertex.name}`"
end
end
end

puts "distances : #{distances}"
puts "predecessors : #{predecessors.map { |k,v| [k.name, v.name] }.to_h}"

path = [to]
while before = predecessors[to]
path << before
to = before
break if to == from
end

unless path.last.equal?(from)
raise ArgumentError, "There is no path from #{from.name} to #{to.name}"
end

path.reverse
end
```

### Log
```
distances : {"A"=>0}
predecessors : {}

A(0)
-- C(5)
-- update C distance to 1
-- log `C -> A`

B(5)
-- D(5)

C(1)
-- B(5)
-- update B distance to 2
-- log `B -> C`

D(5)
distances : {"A"=>0, "C"=>1, "B"=>2}
predecessors : {"C"=>"A", "B"=>"C"}
```

It looks like D's distance cannot be updated as expected when enumerate to B, and the predecessors cannot log `D -> B`.
At last it raises the error because the predecessors does not contain D.

I think it will raise this error if the dependency path is not equal to the enumeration order.
So I try to change the dependency path from `A -> C -> B -> D -> A` to `A -> B -> C -> D -> A`, and Molinillo print the circular dependency path as expected.

### Log
```
distances : {"A"=>0}
predecessors : {}

A(0)
-- B(5)
-- update B distance to 1
-- log `B -> A`

B(1)
-- C(5)
-- update C distance to 2
-- log `C -> B`

C(2)
-- D(5)
-- update D distance to 3
-- log `D -> C`

D(3)
distances : {"A"=>0, "B"=>1, "C"=>2, "D"=>3}
predecessors : {"B"=>"A", "C"=>"B", "D"=>"C"}
[!] There is a circular dependency between A and B and C and D
```

Could someone take a look at this please? Is this a bug, or is there some special reason of the enumeration order?
Thanks, and sorry for my poor English.

This is my test demo. [PodDemo.zip](https://github.com/CocoaPods/Molinillo/files/8401794/PodDemo.zip)

Contributor guide

No contributing guide indexed for this repository

Research direction

Start with the path method in lib/molinillo/dependency_graph.rb:259 and reproduce the A → C → B → D → A case from PodDemo.zip with pod install. Compare its enumeration and predecessor tracking with the reported logs; done means the circular dependency is reported instead of raising “There is no path from A to D.”

Written by the indexing model from the issue text.

Assessment

Tech stack
ruby
Domain
tooling
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.