in src/rust/engine/src/rule_graph.rs [390:563]
fn construct_dependencies(
&self,
rule_dependency_edges: &mut RuleDependencyEdges,
all_simplified_entries: &mut HashMap<EntryWithDeps, Vec<EntryWithDeps>>,
unfulfillable_rules: &mut UnfulfillableRuleMap,
entry: EntryWithDeps,
) -> Result<ConstructGraphResult, ()> {
let mut fulfillable_candidates_by_key = HashMap::new();
let mut cycled_on = HashSet::new();
let mut unfulfillable_diagnostics = Vec::new();
let dependency_keys = entry.dependency_keys();
for select_key in dependency_keys {
let (params, product, provided_param) = match &select_key {
&SelectKey::JustSelect(ref s) => (entry.params().clone(), s.product, None),
&SelectKey::JustGet(ref g) => {
// Unlike Selects, Gets introduce new parameter values into a subgraph.
let get_params = {
let mut p = entry.params().clone();
p.insert(g.subject);
p
};
(get_params, g.product, Some(g.subject))
}
};
// Collect fulfillable candidates, used parameters, and cyclic deps.
let mut cycled = false;
let fulfillable_candidates = fulfillable_candidates_by_key
.entry(select_key.clone())
.or_insert_with(Vec::new);
for candidate in rhs(&self.tasks, ¶ms, product) {
match candidate {
Entry::WithDeps(c) => match self.construct_graph_helper(
rule_dependency_edges,
all_simplified_entries,
unfulfillable_rules,
c,
) {
ConstructGraphResult::Unfulfillable => {}
ConstructGraphResult::Fulfilled(simplified_entries) => {
fulfillable_candidates.push(
simplified_entries
.into_iter()
.filter(|e| {
// Only entries that actually consume a provided (Get) parameter are eligible
// for consideration.
if let Some(pp) = provided_param {
e.params().contains(&pp)
} else {
true
}
})
.map(Entry::WithDeps)
.collect::<Vec<_>>(),
);
}
ConstructGraphResult::CycledOn {
cyclic_deps,
partial_simplified_entries,
} => {
cycled = true;
cycled_on.extend(cyclic_deps);
fulfillable_candidates.push(
partial_simplified_entries
.into_iter()
.map(Entry::WithDeps)
.collect::<Vec<_>>(),
);
}
},
p @ Entry::Param(_) => {
fulfillable_candidates.push(vec![p]);
}
};
}
if cycled {
// If any candidate triggered a cycle on a rule that has not yet completed, then we are not
// yet fulfillable, and should finish gathering any other cyclic rule dependencies.
continue;
}
if fulfillable_candidates.is_empty() {
// If no candidates were fulfillable, this rule is not fulfillable.
unfulfillable_diagnostics.push(Diagnostic {
params: params.clone(),
reason: if params.is_empty() {
format!(
"No rule was available to compute {}. Maybe declare it as a RootRule({})?",
product, product,
)
} else {
format!(
"No rule was available to compute {} with parameter type{} {}",
product,
if params.len() > 1 { "s" } else { "" },
params_str(¶ms),
)
},
details: vec![],
});
}
}
// If any dependencies were completely unfulfillable, then whether or not there were cyclic
// dependencies isn't relevant.
if !unfulfillable_diagnostics.is_empty() {
// Was not fulfillable. Remove the placeholder: the unfulfillable entries we stored will
// prevent us from attempting to expand this node again.
unfulfillable_rules
.entry(entry.clone())
.or_insert_with(Vec::new)
.extend(unfulfillable_diagnostics);
rule_dependency_edges.remove(&entry);
return Ok(ConstructGraphResult::Unfulfillable);
}
// No dependencies were completely unfulfillable (although some may have been cyclic).
let flattened_fulfillable_candidates_by_key = fulfillable_candidates_by_key
.into_iter()
.map(|(k, candidate_group)| (k, Itertools::flatten(candidate_group.into_iter()).collect()))
.collect::<Vec<_>>();
// Generate one Entry per legal combination of parameters.
let simplified_entries =
match Self::monomorphize(&entry, &flattened_fulfillable_candidates_by_key) {
Ok(se) => se,
Err(ambiguous_diagnostics) => {
// At least one combination of the dependencies was ambiguous.
unfulfillable_rules
.entry(entry.clone())
.or_insert_with(Vec::new)
.extend(ambiguous_diagnostics);
rule_dependency_edges.remove(&entry);
return Ok(ConstructGraphResult::Unfulfillable);
}
};
let simplified_entries_only: Vec<_> = simplified_entries.keys().cloned().collect();
if cycled_on.is_empty() {
// All dependencies were fulfillable and none were blocked on cycles. Remove the
// placeholder and store the simplified entries.
rule_dependency_edges.remove(&entry);
rule_dependency_edges.extend(simplified_entries);
all_simplified_entries.insert(entry, simplified_entries_only.clone());
Ok(ConstructGraphResult::Fulfilled(simplified_entries_only))
} else {
// The set of cycled dependencies can only contain call stack "parents" of the dependency: we
// remove this entry from the set (if we're in it), until the top-most cyclic parent
// (represented by an empty set) is the one that re-starts recursion.
cycled_on.remove(&entry);
if cycled_on.is_empty() {
// If we were the only member of the set of cyclic dependencies, then we are the top-most
// cyclic parent in the call stack, and we should complete. This represents the case where
// a rule recursively depends on itself, and thus "cannot complete without completing".
//
// Store our simplified equivalence and then re-execute our dependency discovery. In this
// second attempt our cyclic dependencies will use the simplified representation(s) to succeed.
all_simplified_entries.insert(entry, simplified_entries_only);
Err(())
} else {
// This rule may be fulfillable, but we can't compute its complete set of dependencies until
// parent rule entries complete. Remove our placeholder edges before returning.
rule_dependency_edges.remove(&entry);
Ok(ConstructGraphResult::CycledOn {
cyclic_deps: cycled_on,
partial_simplified_entries: simplified_entries_only,
})
}
}
}