Writing this out because it's too complicated to fit all in my head at once. There are two suggests:
For both commands you are conceptually trying to find the smallest possible audit you could perform that would properly connect up the graph. This is vague/complicated, so let's define some concepts/terms.
Methodology / Terminology
Your audit graph is conceptually a DAG (forest), with nodes containing version numbers and edges containing deltas. This DAG has minimum values and one maximum value.
The minimum values are:
- full audits
- entries in unaudited (may be multiple for one crate)
The maximum value is the current versions in the Cargo.lock (there may be multiple versions of one crate, but we redo the whole algorithm for each version, so we can ignore that... kinda).
A path from either direction conceptually starts with all criteria, and then has its criteria intersected by the edge's criteria.
The goal of the vet resolver is to find every path between the minimums and the maximum. This can be done in either direction -- currently we search from the maximums because there are fewer of them and we can conceptually terminate searches must faster (I think we don't realize this right now, to do so we would need to compare the currently evaluated criteria against validated_criteria and discard that work item if it's a subset, since it can't possibly add more information; right now we only discard paths when the intersection becomes the empty set).
The resolver can fail for two conceptually distinct reasons (although it doesn't distinguish them):
- There exist no paths between the minimums and the maximum
- Although there exists paths, none of them have sufficient criteria, not even their union
The first is easier to think about, so let's start with that. The graph is disconnected, but conceptually we have some set of paths reaching down and some set paths reaching up. In my head this is like two hands outstretched towards eachother. In a simplified model where there is only one criteria, the solution we're interested in is just
delta(max(min_graph), min(max_graph)). That is, the smallest distance between the two outstreched hands' fingers.
The second is harder to think about, and I'm not sure how to properly detect/communicate what edges could be cheaply added to make the graph connected from the perspective of Sufficient Criteria. This is especially brain-melty to think about if you want to try to do a Really Amazing Job and actually take path unioning into account.
Ok now with this established, let's see what these two commands are actually asking.
This is to help you get 'vet' passing. Everything described above is exactly the case. Usually the answer will just be "you need a delta from the maximum to the last audit you did".
This is to help you clean out your unaudited backlog. This is the same as vet suggest except all the minimums from unaudited entries have been removed. Assuming you run this command when vet is passing, the answer will usually just be "you need a full audit for the exact version of the unaudited entry we just removed".
Quick And Dirty
Assume the "usual" case is good enough, and just recommend exactly that.
Real Suggest would just say "make a full audit for that version", which would always be sufficient but potentially overkill if you actually have a decent audit-chain near the unaudited version and can actually just add a small delta.
Vet Suggest would say "make a delta from the largest known version mentioned by an audit that is still <= the current version". This could actually be insufficient if done naively enough, because it might be that this is a random floating delta we got from a foreign auditfile without the context of someone they import. In this cast connecting up to that delta might still result in failure.
Compute The Fingers
Actually run the algorithm forwards and backwards and compare the minimums and maximums. If criteria are uniform (no unioning shenanigans), then this will get you some pretty good results that are hard to complain about. Unfortunately this may still miss some extremely galaxy brain optimal solutions involving doing two small deltas to bridge a floating delta (I don't think anyone can reasonably expect us to find and explain that, right?)
Unfortunately this wouldn't help with situations where a review needs to be made "stricter" or weird situations where you can fix some minor path and make the unioning work out. Maybe that's Too Weird and fine to miss?
??? Magic ???
Somehow figure out how to detect and express places where making a review more strict could fix things. I genuinely can't imagine what kind of algorithm this would be right now.
Get really smart about cargo's dependency resolution and start pointing out places where you could upgrade or downgrade specific packages to repair the delta graph. I am getting a headache just thinking about this.