Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Problem: Circular dependencies not a solved problem #153

Closed
clacke opened this issue Aug 11, 2018 · 1 comment · Fixed by #213
Closed

Problem: Circular dependencies not a solved problem #153

clacke opened this issue Aug 11, 2018 · 1 comment · Fixed by #213

Comments

@clacke
Copy link
Member

clacke commented Aug 11, 2018

With fractalide/fractalide#281 , fractalide now has graph as a dependency, and graph depends on racket-doc and its big circular family of dependencies. It seems to be working for fractalide itself, but when I depend on fractalide I get a whole slew of these:

WARNING: This derivation should not have been depended on.
Any derivation depending on this one should have depended on one of these instead:
racket-doc

graph is a monolithic package, there's no graph-lib without the racket-doc dependency that one could depend on instead.

Solution: The real solution, which I have been kicking down the road, is that instead of hoping that everyone happen to encounter the circle through the same "top" package, all the packages in the circle become aliases of the same derivation.
@clacke clacke mentioned this issue Aug 15, 2018
Merged
@clacke
Copy link
Member Author

clacke commented Aug 23, 2018

The real real solution is ripping out the ad-hoc, imperative tree traversal and replace it with probably a datalog ruleset and a relatively simple query.

clacke added a commit to clacke/racket2nix-clacke that referenced this issue Sep 11, 2018
@clacke
Problem: We are not handling circular dependencies well
6a542d5 
The current model is a hack, that only works for directed nix
generation (for a specific package), and only works if you're lucky
(no surprising paths for transitive dependencies into circular
dependencies). It's not good enough for generating a generally useable
racket-packages.nix.

Solution: Implement cycle detection in datalog then reimplement again.

 - The datalog solution worked for small sets of packages, but scaled
   horribly.
 - The new implementation is implemented with lessons learned from
   thinking in datalog. In the future there will be another,
   implemented with lessons learned from writing this one.
 - Turns out the cycle detection is the easy part. The hard work is in
   the nitty gritty of what to do with those cycles.
 - Everything turns out to be a fixed-point problem, or a dynamic
   programming problem, and those turn out to be kind of duals:
   "[Dynamic programming is just a fixed-point application of an
   endofunctor in the domain of graphs, what's the problem?]"

Closes fractalide#153
@clacke clacke mentioned this issue Sep 11, 2018
Merged
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Problem: We are not handling circular dependencies well clacke/racket2nix-clacke
1 participant
@clacke