in src/resolver.rs [1458:1666]
fn search_for_path(
audit_graph: &DirectedAuditGraph<'_>,
criteria_idx: usize,
from_version: Option<&VetVersion>,
to_version: Option<&VetVersion>,
mode: SearchMode,
) -> Result<Vec<DeltaEdgeOrigin>, SortedSet<Option<VetVersion>>> {
assert!(
mode != SearchMode::RegenerateExemptions || to_version.is_none(),
"RegenerateExemptions requires searching towards root"
);
// Search for any path through the graph with edges that satisfy criteria.
// Finding any path validates that we satisfy that criteria.
//
// All full-audits and exemptions have been "desugarred" to a delta from
// None, meaning our graph now has exactly one source and one sink,
// significantly simplifying the start and end conditions.
//
// Some edges have caveats which we want to avoid requiring, so we defer
// edges with caveats to be checked later, after all edges without caveats
// have been visited. This is done by storing work to do in a BinaryHeap,
// sorted by the caveats which apply to each node. This means that if we
// find a patch without using a node with caveats, it's unambiguous proof we
// don't need edges with caveats.
#[derive(Debug, Copy, Clone, Eq, PartialEq, Ord, PartialOrd)]
enum CaveatLevel {
None,
NonImportableAudit,
PreferredExemption,
PreferredUnpublished,
FreshPublisher,
FreshImport,
Exemption,
Unpublished,
FreshExemption,
}
#[derive(Debug)]
struct Node<'a> {
version: Option<&'a VetVersion>,
origin_version: Option<&'a VetVersion>,
path: Vec<DeltaEdgeOrigin>,
caveat_level: CaveatLevel,
}
impl Node<'_> {
fn key(&self) -> impl Ord + '_ {
// Nodes are compared by caveat level. A lower caveat level makes
// the node sort higher, as it will be stored in a max heap.
//
// Once we've sorted by all caveats, we sort by the version
// (preferring lower versions), exemption origin version (preferring
// smaller exemptions), the length of the path (preferring short
// paths), and then the most recently added DeltaEdgeOrigin
// (preferring more-local audits).
//
// NOTE: This ordering logic priorities assume `to_version == None`,
// as we will only be searched in the other direction if the search
// is guaranteed to fail, in which case ordering doesn't matter (as
// we're going to visit every node).
Reverse((
self.caveat_level,
self.version,
self.exemption_origin_version(),
self.path.len(),
self.path.last(),
))
}
// To make better decisions when selecting exemptions, exemption edges
// with lower origin versions are preferred over those with higher
// origin versions. This is checked before path length, as a longer path
// which uses a smaller exemption is generally preferred to a short one
// which uses a full-exemption. This is ignored for other edge types.
fn exemption_origin_version(&self) -> Option<&VetVersion> {
if matches!(
self.caveat_level,
CaveatLevel::PreferredExemption
| CaveatLevel::Exemption
| CaveatLevel::FreshExemption
) {
self.origin_version
} else {
None
}
}
}
impl PartialEq for Node<'_> {
fn eq(&self, other: &Self) -> bool {
self.key() == other.key()
}
}
impl Eq for Node<'_> {}
impl PartialOrd for Node<'_> {
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
Some(self.cmp(other))
}
}
impl Ord for Node<'_> {
fn cmp(&self, other: &Self) -> std::cmp::Ordering {
self.key().cmp(&other.key())
}
}
let mut queue = BinaryHeap::new();
queue.push(Node {
version: from_version,
origin_version: from_version,
path: Vec::new(),
caveat_level: CaveatLevel::None,
});
let mut visited = SortedSet::new();
while let Some(Node {
version,
origin_version: _,
path,
caveat_level,
}) = queue.pop()
{
// If We've been to a version before, We're not going to get a better
// result revisiting it, as we visit the "best" edges first.
if !visited.insert(version) {
continue;
}
// We found a path! Return a search result reflecting what we
// discovered.
if version == to_version {
return Ok(path);
}
// Apply deltas to move along to the next layer of the search, adding it
// to our queue.
let edges = audit_graph.get(&version).map(|v| &v[..]).unwrap_or(&[]);
for edge in edges {
// We'll allow any criteria if we're regenerating exemption edges.
let allow_any_criteria = mode == SearchMode::RegenerateExemptions
&& matches!(edge.origin, DeltaEdgeOrigin::Exemption { .. });
if !allow_any_criteria && !edge.criteria.has_criteria(criteria_idx) {
// This edge never would have been useful to us.
continue;
}
if visited.contains(&edge.version) {
// We've been to the target of this edge already.
continue;
}
// Compute the level of caveats which are being added by the current edge
let edge_caveat_level = match &edge.origin {
DeltaEdgeOrigin::StoredLocalAudit { importable, .. } if !importable => {
CaveatLevel::NonImportableAudit
}
DeltaEdgeOrigin::Exemption { .. } if mode == SearchMode::PreferExemptions => {
CaveatLevel::PreferredExemption
}
DeltaEdgeOrigin::Exemption { .. } => CaveatLevel::Exemption,
DeltaEdgeOrigin::FreshExemption { .. } => unreachable!(),
DeltaEdgeOrigin::Unpublished { .. } => match mode {
// When preferring exemptions, prefer existing unpublished
// entries to avoid imports.lock churn.
SearchMode::PreferExemptions if !edge.freshness.is_fresh() => {
CaveatLevel::PreferredUnpublished
}
SearchMode::PreferExemptions => CaveatLevel::Unpublished,
// Otherwise, prefer fresh to avoid outdated versions.
_ if edge.freshness.is_fresh() => CaveatLevel::PreferredUnpublished,
_ => CaveatLevel::Unpublished,
},
_ => match edge.freshness {
DeltaEdgeFreshness::Stale => CaveatLevel::None,
DeltaEdgeFreshness::FreshPublisher => CaveatLevel::FreshPublisher,
DeltaEdgeFreshness::Fresh => CaveatLevel::FreshImport,
},
};
queue.push(Node {
version: edge.version,
origin_version: version,
path: path.iter().cloned().chain([edge.origin.clone()]).collect(),
caveat_level: caveat_level.max(edge_caveat_level),
});
}
// If we're regenerating exemptions, add a fresh exemption edge which
// directly leads to the root version.
if mode == SearchMode::RegenerateExemptions {
queue.push(Node {
version: None,
origin_version: version,
path: path
.iter()
.cloned()
.chain([DeltaEdgeOrigin::FreshExemption {
version: version
.expect("RegenerateExemptions requires searching towards None")
.clone(),
}])
.collect(),
caveat_level: caveat_level.max(CaveatLevel::FreshExemption),
})
}
}
// Complete failure, we need more audits for this package, so all that
// matters is what nodes were reachable.
Err(visited.into_iter().map(|v| v.cloned()).collect())
}