diff options
Diffstat (limited to 'crates/driver/src/resolve.rs')
-rw-r--r-- | crates/driver/src/resolve.rs | 312 |
1 files changed, 312 insertions, 0 deletions
diff --git a/crates/driver/src/resolve.rs b/crates/driver/src/resolve.rs new file mode 100644 index 0000000..338ce3f --- /dev/null +++ b/crates/driver/src/resolve.rs @@ -0,0 +1,312 @@ +use std::collections::{HashMap, HashSet}; +use std::fmt; +use std::rc::Rc; + +use common::types::TaskID; + +use crate::args::TaskArgs; +use crate::context::{self, Context, OutputRef, TaskRef}; + +#[derive(Debug)] +pub struct DepChain<'ctx>(pub Vec<TaskRef<'ctx>>); + +impl<'ctx> fmt::Display for DepChain<'ctx> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + let mut first = true; + for task in self.0.iter().rev() { + if !first { + write!(f, " -> ")?; + } + write!(f, "{}", task)?; + + first = false; + } + + Ok(()) + } +} + +impl<'ctx> From<TaskRef<'ctx>> for DepChain<'ctx> { + fn from(task: TaskRef<'ctx>) -> Self { + DepChain(vec![task]) + } +} + +impl<'ctx> From<&TaskRef<'ctx>> for DepChain<'ctx> { + fn from(task: &TaskRef<'ctx>) -> Self { + task.clone().into() + } +} + +impl<'ctx> From<&'ctx TaskID> for DepChain<'ctx> { + fn from(id: &'ctx TaskID) -> Self { + TaskRef { + id, + args: Rc::new(TaskArgs::default()), + } + .into() + } +} + +#[derive(Debug)] +pub enum ErrorKind<'ctx> { + Context(context::Error<'ctx>), + OutputNotFound(&'ctx str), + DependencyCycle, +} + +#[derive(Debug)] +pub struct Error<'ctx> { + pub dep_chain: DepChain<'ctx>, + pub kind: ErrorKind<'ctx>, +} + +impl<'ctx> Error<'ctx> { + fn output_not_found(task: &TaskRef<'ctx>, output: &'ctx str) -> Self { + Error { + dep_chain: task.into(), + kind: ErrorKind::OutputNotFound(output), + } + } + + fn dependency_cycle(task: &TaskRef<'ctx>) -> Self { + Error { + dep_chain: task.into(), + kind: ErrorKind::DependencyCycle, + } + } + + fn extend(&mut self, task: &TaskRef<'ctx>) { + self.dep_chain.0.push(task.clone()); + } +} + +impl<'ctx> fmt::Display for Error<'ctx> { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + let Error { dep_chain, kind } = self; + match kind { + ErrorKind::Context(err) => { + write!(f, "{}: ", err)?; + } + ErrorKind::OutputNotFound(output) => { + write!(f, "Output '{}' not found: ", output)?; + } + ErrorKind::DependencyCycle => { + write!(f, "Dependency Cycle: ")?; + } + } + dep_chain.fmt(f) + } +} + +impl<'ctx> From<context::Error<'ctx>> for Error<'ctx> { + fn from(err: context::Error<'ctx>) -> Self { + Error { + dep_chain: err.task.into(), + kind: ErrorKind::Context(err), + } + } +} + +impl<'ctx> std::error::Error for Error<'ctx> {} + +#[derive(Debug, PartialEq)] +enum ResolveState { + Resolving, + Resolved, +} + +pub fn runtime_depends<'ctx, I>( + ctx: &'ctx Context, + deps: I, +) -> Result<HashSet<OutputRef>, Vec<Error>> +where + I: IntoIterator<Item = OutputRef<'ctx>>, +{ + fn add_dep<'ctx>( + ret: &mut HashSet<OutputRef<'ctx>>, + ctx: &'ctx Context, + dep: OutputRef<'ctx>, + ) -> Vec<Error<'ctx>> { + if ret.contains(&dep) || ctx.in_rootfs(&dep) { + return Vec::new(); + } + + let task = &dep.task; + let task_def = match ctx.get(task.id) { + Ok(task) => task, + Err(err) => return vec![err.into()], + }; + + let output = match task_def.output.get(dep.output) { + Some(output) => output, + None => { + return vec![Error::output_not_found(task, dep.output)]; + } + }; + + ret.insert(dep.clone()); + + let mut errors = Vec::new(); + for runtime_dep in &output.runtime_depends { + match ctx.output_ref(runtime_dep, &task.args, false) { + Ok(output_ref) => { + for mut error in add_dep(ret, ctx, output_ref) { + error.extend(task); + errors.push(error); + } + } + Err(err) => { + let mut err: Error = err.into(); + err.extend(task); + errors.push(err); + } + }; + } + errors + } + + let mut ret = HashSet::new(); + let mut errors = Vec::new(); + + for dep in deps { + errors.extend(add_dep(&mut ret, ctx, dep)); + } + + if !errors.is_empty() { + return Err(errors); + } + + Ok(ret) +} + +pub fn get_dependent_outputs<'ctx>( + ctx: &'ctx Context, + task_ref: &TaskRef<'ctx>, +) -> Result<HashSet<OutputRef<'ctx>>, Vec<Error<'ctx>>> { + let deps: HashSet<_> = ctx + .get_build_depends(task_ref) + .map_err(|err| vec![err.into()])? + .into_iter() + .chain( + ctx.get_host_depends(task_ref) + .map_err(|err| vec![err.into()])? + .into_iter(), + ) + .collect(); + runtime_depends(ctx, deps) +} + +pub fn get_dependent_tasks<'ctx>( + ctx: &'ctx Context, + task_ref: &TaskRef<'ctx>, +) -> Result<HashSet<TaskRef<'ctx>>, Vec<Error<'ctx>>> { + Ok(ctx + .get_inherit_depend(task_ref) + .map_err(|err| vec![err.into()])? + .into_iter() + .chain( + get_dependent_outputs(ctx, task_ref)? + .into_iter() + .map(|dep| dep.task), + ) + .collect()) +} + +#[derive(Debug)] +pub struct Resolver<'ctx> { + ctx: &'ctx Context, + resolve_state: HashMap<TaskRef<'ctx>, ResolveState>, +} + +impl<'ctx> Resolver<'ctx> { + pub fn new(ctx: &'ctx Context) -> Self { + Resolver { + ctx, + resolve_state: HashMap::new(), + } + } + + fn tasks_resolved(&self) -> bool { + self.resolve_state + .values() + .all(|resolved| *resolved == ResolveState::Resolved) + } + + fn add_task(&mut self, task: &TaskRef<'ctx>, output: Option<&'ctx str>) -> Vec<Error<'ctx>> { + match self.resolve_state.get(task) { + Some(ResolveState::Resolving) => return vec![Error::dependency_cycle(task)], + Some(ResolveState::Resolved) => return vec![], + None => (), + } + + let task_def = match self.ctx.get(task.id) { + Ok(task_def) => task_def, + Err(err) => return vec![err.into()], + }; + + if let Some(task_output) = output { + if !task_def.output.contains_key(task_output) { + return vec![Error::output_not_found(task, task_output)]; + } + } + + self.resolve_state + .insert(task.clone(), ResolveState::Resolving); + + let mut ret = Vec::new(); + let mut handle_errors = |errors: Vec<Error<'ctx>>| { + for mut error in errors { + error.extend(task); + ret.push(error); + } + }; + + match self.ctx.get_inherit_depend(task) { + Ok(Some(inherit)) => { + handle_errors(self.add_task(&inherit, None)); + } + Ok(None) => {} + Err(err) => { + handle_errors(vec![err.into()]); + } + } + + match get_dependent_outputs(self.ctx, task) { + Ok(rdeps) => { + for rdep in rdeps { + handle_errors(self.add_task(&rdep.task, Some(rdep.output))); + } + } + Err(errors) => { + handle_errors(errors); + } + } + + if ret.is_empty() { + *self + .resolve_state + .get_mut(task) + .expect("Missing resolve_state") = ResolveState::Resolved; + } else { + self.resolve_state.remove(task); + } + + ret + } + + pub fn add_goal(&mut self, task: &TaskRef<'ctx>) -> Vec<Error<'ctx>> { + let ret = self.add_task(task, None); + debug_assert!(self.tasks_resolved()); + ret + } + + pub fn into_taskset(self) -> HashSet<TaskRef<'ctx>> { + debug_assert!(self.tasks_resolved()); + + self.resolve_state + .into_iter() + .map(|entry| entry.0) + .collect() + } +} |