1 files changed, 340 insertions, 0 deletions
diff --git a/crates/rebel-resolve/src/lib.rs b/crates/rebel-resolve/src/lib.rs
new file mode 100644
index 0000000..cc44de8
--- /dev/null
+++ b/crates/rebel-resolve/src/lib.rs
@@ -0,0 +1,340 @@
+pub mod args;
+pub mod context;
+pub mod paths;
+pub mod pin;
+pub mod task;
+
+use std::collections::{HashMap, HashSet};
+use std::fmt;
+use std::rc::Rc;
+
+use rebel_common::types::TaskIDRef;
+
+use args::TaskArgs;
+use context::{Context, OutputRef, TaskRef};
+
+#[derive(Debug, Default)]
+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<TaskIDRef<'ctx>> for DepChain<'ctx> {
+	fn from(id: TaskIDRef<'ctx>) -> Self {
+		TaskRef {
+			id,
+			args: Rc::new(TaskArgs::default()),
+		}
+		.into()
+	}
+}
+
+const MAX_ERRORS: usize = 100;
+
+#[derive(Debug)]
+pub enum ErrorKind<'ctx> {
+	Context(context::Error<'ctx>),
+	OutputNotFound(&'ctx str),
+	DependencyCycle,
+	TooManyErrors,
+}
+
+#[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 too_many_errors() -> Self {
+		Error {
+			dep_chain: DepChain::default(),
+			kind: ErrorKind::TooManyErrors,
+		}
+	}
+
+	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: ")?;
+			}
+			ErrorKind::TooManyErrors => {
+				write!(f, "Too many errors, stopping.")?;
+			}
+		}
+		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) {
+			return Vec::new();
+		}
+
+		let task = &dep.task;
+		let task_def = match ctx.get(task) {
+			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(task.id, 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()])?,
+		)
+		.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_parent_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) {
+			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>>| -> Result<(), ()> {
+			for mut error in errors {
+				error.extend(task);
+				ret.push(error);
+
+				if ret.len() > MAX_ERRORS {
+					ret.push(Error::too_many_errors());
+					return Err(());
+				}
+			}
+			Ok(())
+		};
+
+		let _ = (|| -> Result<(), ()> {
+			match self.ctx.get_parent_depend(task) {
+				Ok(Some(parent)) => {
+					handle_errors(self.add_task(&parent, 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)?;
+				}
+			}
+
+			Ok(())
+		})();
+
+		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()
+	}
+}