Cyclic Resolutions should be Sortable.

[yfeldblum]

The resolver must produce a DAG. When the resolver allows cycles, we cannot topologically sort the resolution. Topological sorting of the resolution is a requirement. In part because we need to do it, and in part because cyclic dependencies between packages are an odd concept and should be rejected in principle.

The resolver algorithm should detect cycles immediately as they occur in the incremental resolution process and reject that increment early. A proposed manifest which would result in a cycle should be treated like a proposed manifest which would result in a conflict: it would be rejected.

---

Update.

In some situations, cyclic dependencies are nonsensical. In other situations, there may be some mysterious sense to them. Therefore, the environment may specify whether the resolver is required to produce an acyclic graph or whether the resolver may produce a cyclic graph.

To handle this, the sorter will topologically sort a version of the graph with an approximately minimal feedback arc set (empty, if the graph is acyclic) removed.

An algorithm for finding an approximately minimal feedback arc set is given in Combinatorial Algorithms for Feedback Problems in Directed Graphs §3.1. The algorithm returns the empty set when the input graph is acyclic, so that Librarian's behavior will be extended to new cases, not changed for existing cases.

[marcellodesales]

I will be waiting for a resolution! Thanks!

[mwhooker]

here are a few solutions for removing cycles from a graph

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.1.9435&rep=rep1&type=pdf https://en.wikipedia.org/wiki/Feedback_arc_set

it's how compilers deal with headers/libraries that include each other I think

[mwhooker]

here's a reference to the same issue reported to opscode https://tickets.opscode.com/browse/COOK-4142

[emiellohr]

Is there some kind of workaround for this? I'm also facing the problem of Windows/Powershell on adding the rbenv cookbook. The thing is that I can't even find where the dependency on windows or powershell is set.

[iDub79]

Any update on this issue? My Cheffile contains the following and will only work if I comment out the PHP cookbook:

site 'http://community.opscode.com/api/v1'

cookbook "apt" cookbook "apache2" cookbook "mysql"

cookbook "php"

[emiellohr]

php depends on the windows cookbook and the windows cookbook depends on the powershell cookbook. And the powershell cookbook depends on the windows cookbook. And there is the cyclic dependency. But no resolution yet.

[iDub79]

So has this issue come about due to an Chef/Librarian update?

So is it not currently possible to use a Cheffile to download all of the required cookbooks in order to use Vagrant? Would you suggest that I manually download the required cookbooks until this issue is resolved?

Sorry if these questions have previously been answered somewhere else. I'm quite new to Chef / Vagrant / Librarian...

[mwhooker]

btw, we're hosting a fork of the windows cookbook from when it used to work. feel free to use it here https://github.com/SimpleFinance/chef-windows

cookbook 'windows', :git => 'https://github.com/SimpleFinance/chef-windows.git'

edit: @Ian-Wright1979 try plugging the above line into your cheffile.

[iDub79]

Thanks @mwhooker that did the trick!

[marcellodesales]

I also updated my Cheffile with what @mwhooker suggested and "librarian-chef update" works now...

[yfeldblum]

I am currently out for the holidays.

However you can explicitly specify versions of powershell and windows in your Cheffile which do not have a circular dependency. That should solve the problem temporarily.

[mwhooker]

The problem is the windows cookbook is required by a great many other cookbooks that have nothing to do with windows

[iDub79]

@marcellodesales , @mwhooker , the only issue that I've come across using this solution is if you update the Cheffile and then run librarian-chef install again. As the windows cookbook is a git repository, I get an error every time I try to run librarian-chef install again to update any added/updated cookbooks. The only thing I can do is to restart my Windows computer in order to manually remove the windows cookbook so that I can rerun librarian-chef install. Usual windows rubbish!

[bitgangsta]

This is becoming a major issue as Chef 11.8 includes the newest windows and powershell cookbooks and have a cyclic dependency out of the box. Super gross, especially for those of us not even deploying to Windows. See the cyclic dependency in windows metadata.rb and powershell metadata.rb.

Other than using @mwhooker's fork, what's the plan for fixing this? How does Berkshelf handle this?

[yfeldblum]

@mwhooker Thanks for the links. Discovering and dropping a small feedback arc set will allow us to sort a resolution efficiently as well. The approximation algorithm in Combinatorial Algorithms for Feedback Problems in Directed Graphs §3.1 seems straightforward.

[mwhooker]

@yfeldblum awesome! Please reach out if I can help in any way