Smarter dependency resolver

[ysbaddaden]

The current dependency resolver is dumb.

It takes the current project shard.yml then clones dependencies, extracts the available versions and takes the shard.yml for the latest version matching the requirement (or HEAD).

It then does the same for the dependencies of each dependency, pushing new dependencies or requirements to a flat list of packages, and so on, recursively.

If any package in the flattened list packages and requirements can't eventually be resolved to at least one version, the resolver will fail by raising a conflict.

This resolver should work for quite some time, until Crystal starts having lots of libraries with lots of dependencies, in which case it will quickly fail.

A smarter resolver will then be appreciable.

[ysbaddaden]

I found some reference on this topic: this is a Boolean Satisfiability Problem which is NP-complete (proof) and can be solved with a SAT solver.

There are some libraries available:

• picosat (C)
• gecode (C++)
• libsolv (C)