Introduce rebel-resolve module

It would be nice to reduce the dependencies of the driver on the context
further, so more of rebel-resolve can become private.

7 files changed, 1168 insertions, 0 deletions

diff --git a/crates/rebel-resolve/Cargo.toml b/crates/rebel-resolve/Cargo.toml
new file mode 100644
index 0000000..65eae78
--- /dev/null
+++ b/crates/rebel-resolve/Cargo.toml
@@ -0,0 +1,16 @@
+[package]
+name = "rebel-resolve"
+version = "0.1.0"
+authors = ["Matthias Schiffer <mschiffer@universe-factory.net>"]
+license = "MIT"
+edition = "2021"
+
+# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
+
+[dependencies]
+rebel-common = { path = "../rebel-common" }
+rebel-parse = { path = "../rebel-parse" }
+
+deb-version = "0.1.1"
+enum-kinds = "0.5.1"
+serde = { version = "1", features = ["derive", "rc"] }
diff --git a/crates/rebel-resolve/src/args.rs b/crates/rebel-resolve/src/args.rs
new file mode 100644
index 0000000..805646a
--- /dev/null
+++ b/crates/rebel-resolve/src/args.rs
@@ -0,0 +1,122 @@
+use std::{
+	collections::{hash_map, HashMap},
+	hash,
+	rc::Rc,
+};
+
+use enum_kinds::EnumKind;
+use serde::{Deserialize, Serialize};
+
+#[derive(Debug, Serialize, PartialEq, Eq)]
+pub struct Platform {
+	#[serde(skip)]
+	pub short: String,
+	pub gnu_triplet: String,
+	pub karch: String,
+	pub prefix: String,
+}
+
+#[derive(Debug, Serialize, PartialEq, Eq)]
+pub struct PlatformRelation {
+	pub is_same: bool,
+	pub sysroot: String,
+	pub cross_compile: String,
+}
+
+#[derive(Clone, Debug, Serialize, PartialEq, Eq, EnumKind)]
+#[serde(untagged)]
+#[enum_kind(ArgType, derive(Deserialize), serde(rename_all = "snake_case"))]
+pub enum Arg {
+	String(Rc<String>),
+	Platform(Rc<Platform>),
+	PlatformRelation(Rc<PlatformRelation>),
+}
+
+impl From<&Arg> for Arg {
+	fn from(value: &Arg) -> Self {
+		value.clone()
+	}
+}
+
+impl From<String> for Arg {
+	fn from(value: String) -> Self {
+		Arg::String(Rc::new(value))
+	}
+}
+
+impl From<Platform> for Arg {
+	fn from(value: Platform) -> Self {
+		Arg::Platform(Rc::new(value))
+	}
+}
+
+impl From<PlatformRelation> for Arg {
+	fn from(value: PlatformRelation) -> Self {
+		Arg::PlatformRelation(Rc::new(value))
+	}
+}
+
+#[derive(Clone, Debug, Serialize, PartialEq, Eq, Default)]
+pub struct TaskArgs(HashMap<String, Arg>);
+
+impl TaskArgs {
+	pub fn contains_key(&self, key: &str) -> bool {
+		self.0.contains_key(key)
+	}
+
+	pub fn get(&self, key: &str) -> Option<&Arg> {
+		self.0.get(key)
+	}
+
+	pub fn set<T>(&mut self, key: &str, value: Option<T>)
+	where
+		T: Into<Arg>,
+	{
+		if let Some(v) = value {
+			self.0.insert(key.to_string(), v.into());
+		} else {
+			self.0.remove(key);
+		}
+	}
+
+	pub fn iter(&self) -> hash_map::Iter<String, Arg> {
+		self.into_iter()
+	}
+}
+
+impl FromIterator<(String, Arg)> for TaskArgs {
+	fn from_iter<T: IntoIterator<Item = (String, Arg)>>(iter: T) -> Self {
+		TaskArgs(HashMap::from_iter(iter))
+	}
+}
+
+impl<'a> IntoIterator for &'a TaskArgs {
+	type Item = (&'a String, &'a Arg);
+
+	type IntoIter = hash_map::Iter<'a, String, Arg>;
+
+	fn into_iter(self) -> Self::IntoIter {
+		self.0.iter()
+	}
+}
+
+#[allow(clippy::derived_hash_with_manual_eq)]
+impl hash::Hash for TaskArgs {
+	fn hash<H: hash::Hasher>(&self, _state: &mut H) {
+		// Don't do anything: Properly hashing the task args is likely to cost
+		// much more performance than the hash collisions caused by TaskRefs
+		// that only differ by the args
+	}
+}
+
+pub fn arg<A: Into<Arg>>(key: &str, value: A) -> (String, Arg) {
+	(key.to_string(), value.into())
+}
+
+#[derive(Clone, Debug, Deserialize, Default, PartialEq, Eq)]
+pub struct ArgMapping(pub HashMap<String, String>);
+
+#[allow(clippy::derived_hash_with_manual_eq)]
+impl hash::Hash for ArgMapping {
+	fn hash<H: hash::Hasher>(&self, _state: &mut H) {}
+}
diff --git a/crates/rebel-resolve/src/context.rs b/crates/rebel-resolve/src/context.rs
new file mode 100644
index 0000000..b8090d1
--- /dev/null
+++ b/crates/rebel-resolve/src/context.rs
@@ -0,0 +1,554 @@
+use std::{
+	borrow::Cow,
+	cmp::Ordering,
+	collections::{HashMap, HashSet},
+	fmt::Display,
+	hash::Hash,
+	ops::Index,
+	rc::Rc,
+	result,
+};
+
+use rebel_common::{
+	error::{self, Contextualizable},
+	string_hash::ArchiveHash,
+	types::TaskIDRef,
+};
+use rebel_parse::{self as parse, TaskFlags};
+
+use crate::{
+	args::*,
+	paths,
+	pin::{self, Pins},
+	task::*,
+};
+
+#[derive(Debug, Clone, Copy)]
+pub enum ErrorKind<'a> {
+	TaskNotFound,
+	InvalidArgument(&'a str),
+	InvalidArgRef(&'a str),
+}
+
+#[derive(Debug, Clone, Copy)]
+pub struct Error<'a> {
+	pub task: TaskIDRef<'a>,
+	pub kind: ErrorKind<'a>,
+}
+
+impl<'a> Display for Error<'a> {
+	fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+		let Error { task, kind } = self;
+		match kind {
+			ErrorKind::TaskNotFound => write!(f, "Task '{}' not found", task),
+			ErrorKind::InvalidArgument(arg) => write!(
+				f,
+				"Invalid or missing argument '{}' for task '{}'",
+				arg, task
+			),
+			ErrorKind::InvalidArgRef(arg) => write!(
+				f,
+				"Invalid reference for argument '{}' of task '{}'",
+				arg, task
+			),
+		}
+	}
+}
+
+impl<'a> From<Error<'a>> for error::Error {
+	fn from(err: Error) -> Self {
+		error::Error::new(err)
+	}
+}
+
+pub type Result<'a, T> = result::Result<T, Error<'a>>;
+
+#[derive(Clone, Debug, PartialEq, Eq, Hash)]
+pub struct TaskRef<'ctx> {
+	pub id: TaskIDRef<'ctx>,
+	pub args: Rc<TaskArgs>,
+}
+
+impl<'ctx> Display for TaskRef<'ctx> {
+	fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
+		if !f.alternate() {
+			return self.id.fmt(f);
+		}
+
+		let version_arg = match self.args.get("version") {
+			Some(Arg::String(s)) => Some(s),
+			_ => None,
+		};
+		let host_arg = match self.args.get("host") {
+			Some(Arg::Platform(platform)) => Some(platform),
+			_ => None,
+		};
+		let target_arg = match self.args.get("target") {
+			Some(Arg::Platform(platform)) => Some(platform),
+			_ => None,
+		};
+
+		write!(f, "{}", self.id.recipe)?;
+		if let Some(version) = version_arg {
+			write!(f, "#{}", version)?;
+		}
+		write!(f, "::{}", self.id.task)?;
+
+		if host_arg.is_some() || target_arg.is_some() {
+			write!(f, "@")?;
+		}
+
+		if let Some(host) = host_arg {
+			write!(f, "{}", host.short)?;
+		}
+		if let Some(target) = target_arg {
+			write!(f, ":{}", target.short)?;
+		}
+		Ok(())
+	}
+}
+
+#[derive(Clone, Debug, PartialEq, Eq, Hash)]
+pub struct OutputRef<'ctx> {
+	pub task: TaskRef<'ctx>,
+	pub output: &'ctx str,
+}
+
+fn platform_relation(args: &TaskArgs, from: &str, to: &str) -> Option<PlatformRelation> {
+	let plat_from = match args.get(from)? {
+		Arg::Platform(plat) => plat,
+		_ => return None,
+	};
+	let plat_to = match args.get(to)? {
+		Arg::Platform(plat) => plat,
+		_ => return None,
+	};
+
+	let plat_rel = if plat_from == plat_to {
+		PlatformRelation {
+			is_same: true,
+			sysroot: "".to_string(),
+			cross_compile: "".to_string(),
+		}
+	} else {
+		PlatformRelation {
+			is_same: false,
+			sysroot: paths::TASK_SYSROOT.to_string(),
+			cross_compile: format!("{}/bin/{}-", plat_from.prefix, plat_to.gnu_triplet),
+		}
+	};
+	Some(plat_rel)
+}
+
+#[derive(Debug)]
+pub struct Context {
+	platforms: HashMap<String, Arg>,
+	globals: TaskArgs,
+	tasks: HashMap<String, HashMap<String, Vec<TaskDef>>>,
+	rootfs: (ArchiveHash, String),
+}
+
+impl Context {
+	pub fn new(
+		mut tasks: HashMap<String, HashMap<String, Vec<TaskDef>>>,
+		pins: Pins,
+	) -> error::Result<Self> {
+		let platforms: HashMap<_, _> = [
+			arg(
+				"build",
+				Platform {
+					short: "build".to_string(),
+					gnu_triplet: "x86_64-linux-gnu".to_string(),
+					karch: "x86_64".to_string(),
+					prefix: "/opt/toolchain".to_string(),
+				},
+			),
+			arg(
+				"aarch64",
+				Platform {
+					short: "aarch64".to_string(),
+					gnu_triplet: "aarch64-linux-gnu".to_string(),
+					karch: "arm64".to_string(),
+					prefix: "/usr".to_string(),
+				},
+			),
+		]
+		.into_iter()
+		.collect();
+
+		let globals = TaskArgs::from_iter([
+			("build".to_string(), platforms["build"].clone()),
+			arg("workdir", paths::TASK_WORKDIR.to_string()),
+			arg("dldir", paths::TASK_DLDIR.to_string()),
+			arg("destdir", paths::TASK_DESTDIR.to_string()),
+			arg("sysroot", paths::TASK_SYSROOT.to_string()),
+		]);
+		let (rootfs, rootfs_provides) =
+			Context::handle_pins(pins).context("Failed to process pin list")?;
+
+		Context::add_rootfs_tasks(&mut tasks, rootfs_provides, &globals)
+			.context("Failed to determine rootfs-provided tasks from pin list")?;
+
+		Ok(Context {
+			platforms,
+			globals,
+			tasks,
+			rootfs,
+		})
+	}
+
+	fn handle_pins(pins: Pins) -> error::Result<((ArchiveHash, String), Vec<pin::Provides>)> {
+		let mut ret = None;
+
+		for (name, pin) in pins {
+			if pin.is_rootfs {
+				if ret.is_some() {
+					return Err(error::Error::new("Multiple is-rootfs pins"));
+				}
+				let hash = pin.hash.context("is-rootfs pin without hash")?;
+
+				ret = Some(((hash, name), pin.provides));
+			}
+		}
+
+		ret.context("No is-rootfs pins")
+	}
+
+	fn add_rootfs_tasks(
+		tasks: &mut HashMap<String, HashMap<String, Vec<TaskDef>>>,
+		provides: Vec<pin::Provides>,
+		globals: &TaskArgs,
+	) -> error::Result<()> {
+		let build = globals.get("build").unwrap();
+
+		for pin::Provides {
+			recipe,
+			task,
+			output,
+			args,
+		} in provides
+		{
+			let mut task_def = TaskDef::default();
+
+			if let Some(host) = args.host {
+				if host != "build" {
+					return Err(error::Error::new(format!("Invalid host value '{}'", host)));
+				}
+				task_def.args.insert("host".to_string(), build.into());
+				task_def.arg_match.set("host", Some(build));
+			}
+
+			if let Some(target) = args.target {
+				if target != "build" {
+					return Err(error::Error::new(format!(
+						"Invalid target value '{}'",
+						target
+					)));
+				}
+				task_def.args.insert("target".to_string(), build.into());
+				task_def.arg_match.set("target", Some(build));
+			}
+
+			for output_entry in output {
+				task_def
+					.output
+					.insert(output_entry.to_string(), Output::default());
+			}
+
+			task_def.priority = i32::MAX;
+
+			tasks
+				.entry(recipe)
+				.or_default()
+				.entry(task)
+				.or_default()
+				.push(task_def);
+		}
+
+		Ok(())
+	}
+
+	pub fn get_rootfs(&self) -> &(ArchiveHash, String) {
+		&self.rootfs
+	}
+
+	fn match_task(task: &TaskDef, args: &TaskArgs) -> bool {
+		task.arg_match
+			.iter()
+			.all(|(key, value)| args.get(key) == Some(value))
+	}
+
+	fn compare_tasks(task1: &TaskDef, task2: &TaskDef) -> Ordering {
+		task1
+			.priority
+			.cmp(&task2.priority)
+			.then(deb_version::compare_versions(
+				task1.meta.version.as_deref().unwrap_or_default(),
+				task2.meta.version.as_deref().unwrap_or_default(),
+			))
+	}
+
+	fn select_task<'ctx>(tasks: &'ctx [TaskDef], args: &TaskArgs) -> Option<&'ctx TaskDef> {
+		tasks
+			.iter()
+			.filter(|task| Self::match_task(task, args))
+			.max_by(|task1, task2| Self::compare_tasks(task1, task2))
+	}
+
+	fn get_by_ref(&self, id: TaskIDRef) -> Option<&[TaskDef]> {
+		Some(self.tasks.get(id.recipe)?.get(id.task)?)
+	}
+
+	fn get_with_args<'a>(&self, id: TaskIDRef<'a>, args: &TaskArgs) -> Result<'a, &TaskDef> {
+		self.get_by_ref(id)
+			.and_then(|tasks| Self::select_task(tasks, args))
+			.ok_or(Error {
+				task: id,
+				kind: ErrorKind::TaskNotFound,
+			})
+	}
+
+	pub fn get<'a>(&self, task: &TaskRef<'a>) -> Result<'a, &TaskDef> {
+		self.get_with_args(task.id, task.args.as_ref())
+	}
+
+	fn task_ref<'ctx>(&'ctx self, id: TaskIDRef<'ctx>, args: &TaskArgs) -> Result<TaskRef> {
+		let task_def = self.get_with_args(id, args)?;
+
+		let mut arg_def: HashMap<_, _> = task_def.args.iter().map(|(k, &v)| (k, v)).collect();
+		for (key, arg) in &self.globals {
+			// TODO: Handle conflicts between explicit args and globals
+			arg_def.insert(key, ArgType::from(arg));
+		}
+
+		let mut new_args = TaskArgs::default();
+
+		for (key, typ) in arg_def {
+			if let Some(arg) = args.get(key) {
+				if ArgType::from(arg) == typ {
+					new_args.set(key, Some(arg));
+					continue;
+				}
+			}
+			return Err(Error {
+				task: id,
+				kind: ErrorKind::InvalidArgument(key),
+			});
+		}
+
+		let build_to_host = platform_relation(&new_args, "build", "host");
+		let host_to_target = platform_relation(&new_args, "host", "target");
+		let build_to_target = platform_relation(&new_args, "build", "target");
+
+		let cross_compile = build_to_host
+			.as_ref()
+			.map(|build_to_host| build_to_host.cross_compile.clone());
+
+		new_args.set("build_to_host", build_to_host);
+		new_args.set("host_to_target", host_to_target);
+		new_args.set("build_to_target", build_to_target);
+
+		new_args.set("cross_compile", cross_compile);
+
+		new_args.set("basename", Some(task_def.meta.basename.clone()));
+		new_args.set("recipename", Some(task_def.meta.recipename.clone()));
+		new_args.set("recipe", Some(task_def.meta.recipe.clone()));
+		new_args.set("name", Some(task_def.meta.name.clone()));
+		new_args.set("version", task_def.meta.version.clone());
+
+		Ok(TaskRef {
+			id,
+			args: Rc::new(new_args),
+		})
+	}
+
+	pub fn parse(&self, s: &str) -> error::Result<(TaskRef, TaskFlags)> {
+		let (parsed, flags) = parse::task_with_flags(s)
+			.ok()
+			.context("Invalid task syntax")?;
+
+		let id = TaskIDRef {
+			recipe: parsed.id.recipe,
+			task: parsed.id.task,
+		};
+
+		let (ctx_recipe, recipe_tasks) = self
+			.tasks
+			.get_key_value(id.recipe)
+			.with_context(|| format!("Task {} not found", id))?;
+		let (ctx_task, _) = recipe_tasks
+			.get_key_value(id.task)
+			.with_context(|| format!("Task {} not found", id))?;
+		let ctx_id = TaskIDRef {
+			recipe: ctx_recipe,
+			task: ctx_task,
+		};
+
+		let mut args = self.globals.clone();
+
+		if let Some(host) = parsed.args.host {
+			let plat = self
+				.platforms
+				.get(host)
+				.with_context(|| format!("Platform '{}' not found", host))?;
+			args.set("host", Some(plat));
+			args.set("target", Some(plat));
+		}
+		if let Some(target) = parsed.args.target {
+			let plat = self
+				.platforms
+				.get(target)
+				.with_context(|| format!("Platform '{}' not found", target))?;
+			args.set("target", Some(plat));
+		}
+
+		let task_ref = self
+			.task_ref(ctx_id, &args)
+			.with_context(|| format!("Failed to instantiate task {}", id))?;
+
+		Ok((task_ref, flags))
+	}
+
+	fn map_args<'ctx, 'args>(
+		task: TaskIDRef<'ctx>,
+		mapping: &'ctx ArgMapping,
+		args: &'args TaskArgs,
+		build_dep: bool,
+	) -> Result<'ctx, Cow<'args, TaskArgs>> {
+		if mapping.0.is_empty() && !build_dep {
+			return Ok(Cow::Borrowed(args));
+		}
+
+		let mut ret = args.clone();
+
+		if build_dep {
+			ret.set("host", args.get("build"));
+			ret.set("target", args.get("host"));
+		}
+
+		for (to, from) in &mapping.0 {
+			let value = args.get(from).ok_or(Error {
+				task,
+				kind: ErrorKind::InvalidArgRef(to),
+			})?;
+			ret.set(to, Some(value.clone()));
+		}
+
+		Ok(Cow::Owned(ret))
+	}
+
+	fn parent_ref<'ctx>(
+		&'ctx self,
+		dep_of: TaskIDRef<'ctx>,
+		dep: &'ctx ParentDep,
+		args: &TaskArgs,
+	) -> Result<TaskRef> {
+		let id = dep.dep.id(dep_of.recipe);
+		let mapped_args = Context::map_args(id, &dep.dep.args, args, false)?;
+		self.task_ref(id, mapped_args.as_ref())
+	}
+
+	pub fn output_ref<'ctx>(
+		&'ctx self,
+		dep_of: TaskIDRef<'ctx>,
+		dep: &'ctx OutputDep,
+		args: &TaskArgs,
+		build_dep: bool,
+	) -> Result<OutputRef<'ctx>> {
+		let id = dep.dep.id(dep_of.recipe);
+		let mapped_args = Context::map_args(id, &dep.dep.args, args, build_dep)?;
+		Ok(OutputRef {
+			task: self.task_ref(id, mapped_args.as_ref())?,
+			output: &dep.output,
+		})
+	}
+
+	pub fn get_parent_depend<'ctx>(
+		&'ctx self,
+		task_ref: &TaskRef<'ctx>,
+	) -> Result<Option<TaskRef>> {
+		let task = self.get(task_ref)?;
+		let Some(parent) = &task.parent else {
+			return Ok(None);
+		};
+		Some(self.parent_ref(task_ref.id, parent, &task_ref.args)).transpose()
+	}
+
+	fn ancestor_iter<'ctx>(
+		&'ctx self,
+		task_ref: &TaskRef<'ctx>,
+	) -> impl Iterator<Item = Result<TaskRef>> {
+		struct Iter<'ctx>(&'ctx Context, Option<Result<'ctx, TaskRef<'ctx>>>);
+
+		impl<'ctx> Iterator for Iter<'ctx> {
+			type Item = Result<'ctx, TaskRef<'ctx>>;
+
+			fn next(&mut self) -> Option<Self::Item> {
+				let task_ref = match self.1.take()? {
+					Ok(task_ref) => task_ref,
+					Err(err) => return Some(Err(err)),
+				};
+				self.1 = self.0.get_parent_depend(&task_ref).transpose();
+				Some(Ok(task_ref))
+			}
+		}
+
+		Iter(self, Some(Ok(task_ref.clone())))
+	}
+
+	pub fn get_build_depends<'ctx>(
+		&'ctx self,
+		task_ref: &TaskRef<'ctx>,
+	) -> Result<HashSet<OutputRef>> {
+		let mut ret = HashSet::new();
+		let mut allow_noinherit = true;
+
+		for current in self.ancestor_iter(task_ref) {
+			let current_ref = current?;
+			let task = self.get(&current_ref)?;
+			let entries = task
+				.build_depends
+				.iter()
+				.filter(|dep| allow_noinherit || !dep.noinherit)
+				.map(|dep| self.output_ref(task_ref.id, dep, &current_ref.args, true))
+				.collect::<Result<Vec<_>>>()?;
+			ret.extend(entries);
+
+			allow_noinherit = false;
+		}
+
+		Ok(ret)
+	}
+
+	pub fn get_host_depends<'ctx>(
+		&'ctx self,
+		task_ref: &TaskRef<'ctx>,
+	) -> Result<HashSet<OutputRef>> {
+		let mut ret = HashSet::new();
+		let mut allow_noinherit = true;
+
+		for current in self.ancestor_iter(task_ref) {
+			let current_ref = current?;
+			let task = self.get(&current_ref)?;
+			let entries = task
+				.depends
+				.iter()
+				.filter(|dep| allow_noinherit || !dep.noinherit)
+				.map(|dep| self.output_ref(task_ref.id, dep, &current_ref.args, false))
+				.collect::<Result<Vec<_>>>()?;
+			ret.extend(entries);
+
+			allow_noinherit = false;
+		}
+
+		Ok(ret)
+	}
+}
+
+impl Index<&TaskRef<'_>> for Context {
+	type Output = TaskDef;
+
+	fn index(&self, index: &TaskRef) -> &TaskDef {
+		self.get(index).expect("Invalid TaskRef")
+	}
+}
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()
+	}
+}
diff --git a/crates/rebel-resolve/src/paths.rs b/crates/rebel-resolve/src/paths.rs
new file mode 100644
index 0000000..274dda1
--- /dev/null
+++ b/crates/rebel-resolve/src/paths.rs
@@ -0,0 +1,4 @@
+pub const TASK_DESTDIR: &str = "/build/dest";
+pub const TASK_DLDIR: &str = "/build/downloads";
+pub const TASK_WORKDIR: &str = "/build/work";
+pub const TASK_SYSROOT: &str = "/opt/toolchain/sysroot";
diff --git a/crates/rebel-resolve/src/pin.rs b/crates/rebel-resolve/src/pin.rs
new file mode 100644
index 0000000..bffc940
--- /dev/null
+++ b/crates/rebel-resolve/src/pin.rs
@@ -0,0 +1,31 @@
+use std::collections::HashMap;
+
+use serde::{Deserialize, Serialize};
+
+use rebel_common::string_hash::*;
+
+#[derive(Clone, Debug, Deserialize, Serialize)]
+pub struct Args {
+	pub host: Option<String>,
+	pub target: Option<String>,
+}
+
+#[derive(Clone, Debug, Deserialize, Serialize)]
+pub struct Provides {
+	pub recipe: String,
+	pub task: String,
+	pub output: Vec<String>,
+	pub args: Args,
+}
+
+#[derive(Clone, Debug, Deserialize, Serialize)]
+#[serde(rename_all = "kebab-case")]
+pub struct Pin {
+	pub hash: Option<ArchiveHash>,
+	#[serde(default)]
+	pub provides: Vec<Provides>,
+	#[serde(default)]
+	pub is_rootfs: bool,
+}
+
+pub type Pins = HashMap<String, Pin>;
diff --git a/crates/rebel-resolve/src/task.rs b/crates/rebel-resolve/src/task.rs
new file mode 100644
index 0000000..1220d45
--- /dev/null
+++ b/crates/rebel-resolve/src/task.rs
@@ -0,0 +1,101 @@
+use std::collections::{HashMap, HashSet};
+
+use serde::Deserialize;
+
+use rebel_common::{string_hash::StringHash, types::TaskIDRef};
+
+use crate::args::{ArgMapping, ArgType, TaskArgs};
+
+#[derive(Clone, Debug, Deserialize, PartialEq, Eq, Hash)]
+pub struct TaskDep {
+	pub recipe: Option<String>,
+	pub task: String,
+	#[serde(default)]
+	pub args: ArgMapping,
+}
+
+impl TaskDep {
+	pub fn id<'a>(&'a self, recipe: &'a str) -> TaskIDRef<'a> {
+		let recipe = self.recipe.as_deref().unwrap_or(recipe);
+		let task = &self.task;
+		TaskIDRef { recipe, task }
+	}
+}
+
+#[derive(Clone, Debug, Deserialize, PartialEq, Eq, Hash)]
+pub struct Fetch {
+	pub name: String,
+	pub sha256: StringHash,
+}
+
+fn default_output_name() -> String {
+	"default".to_string()
+}
+
+#[derive(Clone, Debug, Deserialize)]
+pub struct ParentDep {
+	#[serde(flatten)]
+	pub dep: TaskDep,
+}
+
+#[derive(Clone, Debug, Deserialize, PartialEq, Eq, Hash)]
+pub struct OutputDep {
+	#[serde(flatten)]
+	pub dep: TaskDep,
+	#[serde(default)]
+	pub noinherit: bool,
+	#[serde(default = "default_output_name")]
+	pub output: String,
+}
+
+#[derive(Clone, Debug, Deserialize, Default)]
+pub struct Output {
+	pub path: Option<String>,
+	#[serde(default)]
+	pub runtime_depends: HashSet<OutputDep>,
+}
+
+#[derive(Clone, Debug, Deserialize, Default)]
+pub struct Action {
+	#[serde(default)]
+	pub run: String,
+}
+
+impl Action {
+	pub fn is_empty(&self) -> bool {
+		self.run.is_empty()
+	}
+}
+
+#[derive(Clone, Debug, Default)]
+pub struct TaskMeta {
+	pub basename: String,
+	pub recipename: String,
+	pub recipe: String,
+	pub name: String,
+	pub version: Option<String>,
+}
+
+#[derive(Clone, Debug, Deserialize, Default)]
+pub struct TaskDef {
+	#[serde(skip)]
+	pub meta: TaskMeta,
+	#[serde(default)]
+	pub args: HashMap<String, ArgType>,
+	#[serde(default)]
+	pub parent: Option<ParentDep>,
+	#[serde(default)]
+	pub fetch: HashSet<Fetch>,
+	#[serde(default)]
+	pub build_depends: HashSet<OutputDep>,
+	#[serde(default)]
+	pub depends: HashSet<OutputDep>,
+	#[serde(default)]
+	pub output: HashMap<String, Output>,
+	#[serde(flatten)]
+	pub action: Action,
+	#[serde(default)]
+	pub priority: i32,
+	#[serde(skip)]
+	pub arg_match: TaskArgs,
+}