1 files changed, 91 insertions, 0 deletions
diff --git a/src/resolve.rs b/src/resolve.rs
new file mode 100644
index 0000000..0758016
--- /dev/null
+++ b/src/resolve.rs
@@ -0,0 +1,91 @@
+use std::collections::{HashMap, HashSet};
+use std::fmt;
+
+use crate::types::*;
+
+#[derive(Debug)]
+pub enum Error {
+	TaskNotFound(TaskRef),
+	DependencyCycle(TaskRef),
+}
+
+impl fmt::Display for Error {
+	fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+		match self {
+			Error::TaskNotFound(id) => write!(f, "Task not found: {}", id),
+			Error::DependencyCycle(id) => write!(f, "DependencyCycle: {}", id),
+		}
+	}
+}
+
+impl std::error::Error for Error {}
+
+pub type Result<T> = std::result::Result<T, Error>;
+
+#[derive(PartialEq)]
+enum ResolveState {
+	Resolving,
+	Resolved,
+}
+
+pub struct Resolver<'a> {
+	tasks: &'a TaskMap,
+	resolve_state: HashMap<TaskRef, ResolveState>,
+}
+
+impl<'a> Resolver<'a> {
+	pub fn new(tasks: &'a TaskMap) -> Self {
+		Resolver {
+			tasks: tasks,
+			resolve_state: HashMap::new(),
+		}
+	}
+
+	pub fn add_goal(&mut self, task: &TaskRef) -> Result<()> {
+		match self.resolve_state.get(task) {
+			Some(ResolveState::Resolving) => return Err(Error::DependencyCycle(task.clone())),
+			Some(ResolveState::Resolved) => return Ok(()),
+			None => (),
+		}
+
+		let task_def = match self.tasks.get(task) {
+			None => return Err(Error::TaskNotFound(task.clone())),
+			Some(task_def) => task_def,
+		};
+
+		self.resolve_state
+			.insert(task.clone(), ResolveState::Resolving);
+
+		for dep in &task_def.depends {
+			let res = self.add_goal(dep);
+			if res.is_err() {
+				self.resolve_state.remove(task);
+				return res;
+			}
+		}
+
+		*self
+			.resolve_state
+			.get_mut(task)
+			.expect("Missing resolve_state") = ResolveState::Resolved;
+
+		Ok(())
+	}
+
+	pub fn to_taskset(self) -> HashSet<TaskRef> {
+		fn tasks_resolved(this: &Resolver) -> bool {
+			for (_, resolved) in &this.resolve_state {
+				if *resolved != ResolveState::Resolved {
+					return false;
+				}
+			}
+			true
+		}
+		debug_assert!(tasks_resolved(&self));
+
+		self.resolve_state
+			.into_iter()
+			.map(|entry| entry.0)
+			.collect()
+	}
+}