1 files changed, 97 insertions, 0 deletions
diff --git a/src/main.rs b/src/main.rs
new file mode 100644
index 0000000..98d1b8d
--- /dev/null
+++ b/src/main.rs
@@ -0,0 +1,97 @@
+use std::collections::{HashMap, HashSet};
+// use std::io::{self, Write};
+use std::io;
+// use std::process::Command;
+
+struct Task {
+	// action: String,
+	deps: Vec<String>,
+}
+
+// impl Task {
+// 	fn run(&self) -> io::Result<()> {
+// 		let output = Command::new("sh").arg("-c").arg(&self.action).output()?;
+
+// 		let stdout = io::stdout();
+// 		let mut handle = stdout.lock();
+// 		handle.write_all(&output.stdout)?;
+
+// 		Ok(())
+// 	}
+// }
+
+fn collect_subtasks<'a>(
+	queued: &HashSet<&'a str>,
+	tasks: &'a HashMap<String, Task>,
+	id: &str,
+) -> io::Result<HashSet<&'a str>> {
+	let (task_id, task) = match tasks.get_key_value(id) {
+		Some(t) => t,
+		None => {
+			return Err(io::Error::new(io::ErrorKind::NotFound, "Task not found"));
+		}
+	};
+
+	if queued.contains(id) {
+		return Err(io::Error::new(
+			io::ErrorKind::InvalidData,
+			"Dependency cycle",
+		));
+	}
+
+	let mut queued_sub = queued.clone();
+	queued_sub.insert(task_id);
+
+	let mut subtasks: HashSet<&'a str> = HashSet::new();
+	subtasks.insert(task_id);
+
+	for dep in &task.deps {
+		let deptasks = collect_subtasks(&queued_sub, tasks, dep)?;
+		subtasks = subtasks.union(&deptasks).copied().collect();
+	}
+
+	Ok(subtasks)
+}
+
+fn collect_tasks<'a>(tasks: &'a HashMap<String, Task>, id: &str) -> io::Result<HashSet<&'a str>> {
+	collect_subtasks(&HashSet::new(), tasks, id)
+}
+
+fn main() -> io::Result<()> {
+	let mut tasks = HashMap::new();
+	tasks.insert(
+		String::from("ls"),
+		Task {
+			// action: String::from("ls"),
+			deps: vec!["foo".to_owned(), "bar".to_owned()],
+		},
+	);
+	tasks.insert(
+		String::from("foo"),
+		Task {
+			// action: String::from("echo foo"),
+			deps: vec!["bar".to_owned()],
+		},
+	);
+	tasks.insert(
+		String::from("bar"),
+		Task {
+			// action: String::from("echo bar"),
+			deps: vec![],
+		},
+	);
+
+	let queue = collect_tasks(&tasks, "ls")?;
+	let (runnable, queued) = queue
+		.into_iter()
+		.partition::<HashSet<_>, _>(|id| tasks.get(*id).unwrap().deps.is_empty());
+
+	for t in &runnable {
+		println!("Runnable: {}", t);
+	}
+	for t in &queued {
+		println!("Queued: {}", t);
+	}
+
+	Ok(())
+}