Resolution should try the next one if the first satisfied one fails

[CNSeniorious000]

Use case:

haystack-ai==2.2 requires lxml, which don't have a wheel on pyodide. But haystack<2.2 don't requires lxml.

Resolution should try the next one if the first satisfied one fails. In the example above, when resolving lxml raises ValueError, so haystask 2.2 fails, then it should try haystask 2.1.2 instead of bubbling the ValueError.

Reproduction:

from micropip import install
await install("haystack-ai")  # this will fail because lxml
await install("haystack-ai<2.2")  # this will success

[hoodmane]

See #112. I don't think we want to be a backtracking resolver by default because it's an np-hard problem to solve a dep set. Particularly until we start using PEP 658, this could lead to downloading humongous amounts of stuff while looking for the right solve. It's not ideal for people to be using micropip at runtime anyways, so maybe this would be for creating a lock file ahead of time and then deploying the solve. I was hoping to use pip for this, see #107.

[CNSeniorious000]

I understand. This could be discussed after we start using PEP 658.

It's not ideal for people to be using micropip at runtime anyways, so maybe this would be for creating a lock file ahead of time and then deploying the solve.

Yes of course solving the dependency graph ahead of time and only once is better. But there exists cases when runtime resolution is necessary, such as:

• trying if a package is compatible in the playground
• in a 3-party hosted jupyterlite deployment, running %pip install ... some package that not in the lock file
• LLM code interpreter

So I think a backtracking resolver is necessary but it can be defaults to false, like keep_going.

And I think it is easy to implement, by just making the ver a list or an iterator or satisfied versions here can achieve the my ideal result.

[hoodmane]

lxml, which don't have a wheel on pyodide

As an aside, lxml is included in Pyodide: https://github.com/pyodide/pyodide/blob/main/packages/lxml/meta.yaml

[hoodmane]

I suppose you could probably easily implement a heuristic but implementing a proper solver is quite complicated so there will still be depsets with solutions that a very naive algorithm won't find. I figure it's best to keep it to an algorithm that will find a solve if one exists and an algorithm that doesn't backtrack at all. I don't think we need to make our own halfway working solver.

[hoodmane]

I think we should do #112 and then add a backend that uses resolvelib to do a proper solve.
https://pypi.org/project/resolvelib/

[ryanking13]

Yep, I would like to refactor the micropip (#112) before introducing large changes like resolvelib or installer or PEP 658 (FYI, there is a draft PR for PEP 658 #90). It is not my top priority so if anyone is interested, it's okay to work on this.