#![warn(missing_docs)]
use std::cmp::Reverse;
use std::collections::{BTreeMap, BinaryHeap};
use std::fmt;
use std::rc::Rc;
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum MediaKind {
Binary,
Text,
Data,
Image,
Audio,
Video,
Document,
Archive,
Model,
Font,
}
impl fmt::Display for MediaKind {
fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
formatter.write_str(match self {
Self::Binary => "binary",
Self::Text => "text",
Self::Data => "data",
Self::Image => "image",
Self::Audio => "audio",
Self::Video => "video",
Self::Document => "document",
Self::Archive => "archive",
Self::Model => "model",
Self::Font => "font",
})
}
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Format {
pub id: String,
pub name: String,
pub extensions: Vec<String>,
pub media: MediaKind,
pub decode_only: bool,
}
impl Format {
pub fn new(id: &str, name: &str, media: MediaKind) -> Self {
Self {
id: id.to_owned(),
name: name.to_owned(),
extensions: Vec::new(),
media,
decode_only: false,
}
}
pub fn with_extensions(mut self, extensions: &[&str]) -> Self {
self.extensions = extensions.iter().map(|value| extension(value)).collect();
self.extensions.sort();
self.extensions.dedup();
self
}
#[must_use]
pub fn decode_only(mut self) -> Self {
self.decode_only = true;
self
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
pub enum ConversionKind {
Lossless,
Lossy,
Bridge,
Reinterpret,
Package,
Extract,
}
#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
pub struct Conversion {
pub from: String,
pub to: String,
pub backend: String,
pub operation: String,
pub kind: ConversionKind,
pub cost: u32,
pub external: bool,
}
impl Conversion {
pub fn new(
from: &str,
to: &str,
backend: &str,
operation: &str,
kind: ConversionKind,
cost: u32,
) -> Self {
Self {
from: from.to_owned(),
to: to.to_owned(),
backend: backend.to_owned(),
operation: operation.to_owned(),
kind,
cost,
external: false,
}
}
#[must_use]
pub fn requires_external(mut self) -> Self {
self.external = true;
self
}
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Policy {
pub allow_bridges: bool,
pub allow_reinterpret: bool,
pub allow_packaging: bool,
pub allow_external: bool,
pub allow_external_packaging: bool,
pub allow_decode_only: bool,
pub max_steps: usize,
pub max_routes: usize,
pub max_expansions: usize,
}
impl Default for Policy {
fn default() -> Self {
Self {
allow_bridges: true,
allow_reinterpret: false,
allow_packaging: false,
allow_external: false,
allow_external_packaging: false,
allow_decode_only: false,
max_steps: 6,
max_routes: 8,
max_expansions: 20_000,
}
}
}
impl Policy {
#[must_use]
pub fn allows(&self, kind: ConversionKind) -> bool {
match kind {
ConversionKind::Lossless | ConversionKind::Lossy | ConversionKind::Extract => true,
ConversionKind::Bridge => self.allow_bridges,
ConversionKind::Reinterpret => self.allow_reinterpret,
ConversionKind::Package => self.allow_packaging,
}
}
#[must_use]
pub fn allows_edge(&self, conversion: &Conversion) -> bool {
if !self.allows(conversion.kind) {
return false;
}
if conversion.external {
if !self.allow_external {
return false;
}
if matches!(
conversion.kind,
ConversionKind::Reinterpret | ConversionKind::Package
) && !self.allow_external_packaging
{
return false;
}
}
true
}
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Plan {
pub steps: Vec<Conversion>,
pub cost: u64,
}
#[derive(Clone, Debug, PartialEq, Eq, thiserror::Error)]
pub enum PlanError {
#[error("invalid graph or policy: {0}")]
Invalid(
String,
),
#[error("unknown format: {0}")]
UnknownFormat(
String,
),
#[error("no route from {from} to {to}")]
NoRoute {
from: String,
to: String,
},
#[error("route search limit reached before finding a route")]
SearchLimit,
}
#[derive(Clone, Debug, Default)]
pub struct Graph {
formats: BTreeMap<String, Format>,
conversions: BTreeMap<String, Vec<Conversion>>,
}
impl Graph {
pub fn new() -> Self {
Self::default()
}
pub fn add_format(&mut self, mut format: Format) -> Result<(), PlanError> {
if !valid_id(&format.id) {
return Err(PlanError::Invalid(format!(
"invalid format ID: {:?}",
format.id
)));
}
for value in &mut format.extensions {
*value = extension(value);
if !valid_id(value) {
return Err(PlanError::Invalid(format!(
"invalid extension for {}: {value:?}",
format.id
)));
}
}
format.extensions.sort();
format.extensions.dedup();
if let Some(existing) = self.formats.get_mut(&format.id) {
if existing.media != format.media {
return Err(PlanError::Invalid(format!(
"conflicting media categories for {}",
format.id
)));
}
if format.name < existing.name {
existing.name = format.name;
}
existing.extensions.extend(format.extensions);
existing.extensions.sort();
existing.extensions.dedup();
} else {
self.formats.insert(format.id.clone(), format);
}
Ok(())
}
pub fn add_conversion(&mut self, conversion: Conversion) -> Result<(), PlanError> {
if conversion.cost == 0 {
return Err(PlanError::Invalid(
"conversion cost must be positive".into(),
));
}
if conversion.backend.trim().is_empty() || conversion.operation.trim().is_empty() {
return Err(PlanError::Invalid(
"conversion backend and operation must be nonempty".into(),
));
}
if conversion.from == "*" {
if !matches!(
conversion.kind,
ConversionKind::Reinterpret | ConversionKind::Package
) {
return Err(PlanError::Invalid(
"wildcard input requires Reinterpret or Package".into(),
));
}
} else if !self.formats.contains_key(&conversion.from) {
return Err(PlanError::UnknownFormat(conversion.from));
}
if !self.formats.contains_key(&conversion.to) {
return Err(PlanError::UnknownFormat(conversion.to));
}
let edges = self.conversions.entry(conversion.from.clone()).or_default();
if let Err(index) = edges.binary_search(&conversion) {
edges.insert(index, conversion);
}
Ok(())
}
pub fn formats(&self) -> impl Iterator<Item = &Format> {
self.formats.values()
}
pub fn format(&self, id: &str) -> Option<&Format> {
self.formats.get(id)
}
pub fn resolve(&self, value: &str) -> Option<&Format> {
let normalized = value.trim().to_ascii_lowercase();
if let Some(format) = self.formats.get(&normalized) {
return Some(format);
}
let alias = normalized.trim_start_matches('.');
self.formats.get(alias).or_else(|| {
self.formats
.values()
.find(|format| format.extensions.iter().any(|value| value == alias))
})
}
pub fn routes(&self, from: &str, to: &str, policy: &Policy) -> Result<Vec<Plan>, PlanError> {
let from = self
.resolve(from)
.ok_or_else(|| PlanError::UnknownFormat(from.to_owned()))?;
let to = self
.resolve(to)
.ok_or_else(|| PlanError::UnknownFormat(to.to_owned()))?;
if policy.max_routes == 0 {
return Err(PlanError::Invalid("max_routes must be positive".into()));
}
if from.id == to.id {
return Ok(vec![Plan {
steps: Vec::new(),
cost: 0,
}]);
}
let no_route = || PlanError::NoRoute {
from: from.id.clone(),
to: to.id.clone(),
};
let max_steps = policy.max_steps.min(64);
let max_routes = policy.max_routes.min(64);
let max_expansions = policy.max_expansions.min(100_000);
if max_steps == 0 {
return Err(no_route());
}
let distances = self.distances_to(&to.id, policy);
let Some(&estimate) = distances.get(from.id.as_str()) else {
return Err(no_route());
};
let mut frontier = BTreeMap::new();
frontier.insert(
(estimate, Reverse(0_u64), 0_usize),
Rc::new(SearchPath {
format: &from.id,
edge: None,
previous: None,
cost: 0,
depth: 0,
}),
);
let mut plans = Vec::new();
let mut expansions = 0;
while let Some((_, path)) = frontier.pop_first() {
if path.format == to.id {
let plan = path.plan();
if !plans.contains(&plan) {
plans.push(plan);
}
if plans.len() == max_routes {
return Ok(plans);
}
continue;
}
if path.depth == max_steps {
continue;
}
let edges = self
.conversions
.get(path.format)
.into_iter()
.flatten()
.chain(self.conversions.get("*").into_iter().flatten());
for edge in edges {
if expansions == max_expansions {
return if plans.is_empty() {
Err(PlanError::SearchLimit)
} else {
Ok(plans)
};
}
expansions += 1;
if !policy.allows_edge(edge) || path.contains(&edge.to) {
continue;
}
if self
.formats
.get(&edge.to)
.is_some_and(|format| format.decode_only)
&& !policy.allow_decode_only
{
continue;
}
let Some(&remaining) = distances.get(edge.to.as_str()) else {
continue;
};
let cost = path.cost + u64::from(edge.cost);
frontier.insert(
(cost.saturating_add(remaining), Reverse(cost), expansions),
Rc::new(SearchPath {
format: &edge.to,
edge: Some(edge),
previous: Some(Rc::clone(&path)),
cost,
depth: path.depth + 1,
}),
);
}
}
if plans.is_empty() {
Err(no_route())
} else {
Ok(plans)
}
}
fn distances_to<'a>(&'a self, target: &'a str, policy: &Policy) -> BTreeMap<&'a str, u64> {
let mut reverse: BTreeMap<&str, Vec<(&str, u64)>> = BTreeMap::new();
for edge in self.conversions.values().flatten() {
if policy.allows_edge(edge) {
reverse
.entry(&edge.to)
.or_default()
.push((&edge.from, u64::from(edge.cost)));
}
}
let mut distances = BTreeMap::from([(target, 0_u64)]);
let mut queue = BinaryHeap::from([Reverse((0_u64, target))]);
while let Some(Reverse((cost, current))) = queue.pop() {
if distances.get(current) != Some(&cost) {
continue;
}
let mut relax = |source, weight| {
let next = cost.saturating_add(weight);
if distances.get(source).is_none_or(|&known| next < known) {
distances.insert(source, next);
queue.push(Reverse((next, source)));
}
};
if current == "*" {
for source in self.formats.keys() {
relax(source.as_str(), 0);
}
} else if let Some(edges) = reverse.get(current) {
for &(source, weight) in edges {
relax(source, weight);
}
}
}
distances
}
}
fn valid_id(value: &str) -> bool {
!value.is_empty()
&& value.len() <= 64
&& value.bytes().all(|byte| {
byte.is_ascii_lowercase()
|| byte.is_ascii_digit()
|| matches!(byte, b'-' | b'_' | b'.' | b'+')
})
}
fn extension(value: &str) -> String {
value.trim().trim_start_matches('.').to_ascii_lowercase()
}
struct SearchPath<'a> {
format: &'a str,
edge: Option<&'a Conversion>,
previous: Option<Rc<Self>>,
cost: u64,
depth: usize,
}
impl SearchPath<'_> {
fn contains(&self, format: &str) -> bool {
let mut current = Some(self);
while let Some(path) = current {
if path.format == format {
return true;
}
current = path.previous.as_deref();
}
false
}
fn plan(&self) -> Plan {
let mut steps = Vec::with_capacity(self.depth);
let mut current = self;
while let (Some(edge), Some(previous)) = (current.edge, current.previous.as_deref()) {
let mut step = edge.clone();
step.from = previous.format.to_owned();
steps.push(step);
current = previous;
}
steps.reverse();
Plan {
steps,
cost: self.cost,
}
}
}
#[cfg(test)]
#[allow(clippy::unwrap_used, clippy::expect_used)]
mod tests {
use super::*;
use std::collections::BTreeSet;
fn graph(ids: &[&str]) -> Graph {
let mut graph = Graph::new();
for id in ids {
graph
.add_format(Format::new(id, id, MediaKind::Data))
.unwrap();
}
graph
}
fn edge(from: &str, to: &str, backend: &str, cost: u32) -> Conversion {
Conversion::new(from, to, backend, "convert", ConversionKind::Lossless, cost)
}
#[test]
fn registration_validates_ids_and_normalizes_extensions() {
let mut graph = Graph::new();
for id in ["", "UPPER", "*", "a/b", "a b", "a\0b", "a:b"] {
assert!(matches!(
graph.add_format(Format::new(id, "name", MediaKind::Binary)),
Err(PlanError::Invalid(_))
));
}
assert!(
graph
.add_format(Format::new(&"a".repeat(65), "name", MediaKind::Binary))
.is_err()
);
graph
.add_format(Format::new(&"a".repeat(64), "name", MediaKind::Binary))
.unwrap();
graph
.add_format(
Format::new("a-z_0.9+", "name", MediaKind::Binary)
.with_extensions(&[" .ABC ", "abc", "tar.gz"]),
)
.unwrap();
assert_eq!(
graph.format("a-z_0.9+").unwrap().extensions,
["abc", "tar.gz"]
);
for alias in ["", ".", "a/b", "*"] {
assert!(
graph
.add_format(
Format::new("bad", "bad", MediaKind::Data).with_extensions(&[alias])
)
.is_err()
);
}
assert!(graph.format("bad").is_none());
}
#[test]
fn duplicate_formats_merge_independently_of_registration_order() {
let first = Format::new("jpeg", "JPEG", MediaKind::Image).with_extensions(&["jpeg", "jpg"]);
let second = Format::new("jpeg", "Joint photographic", MediaKind::Image)
.with_extensions(&["JPG", "jpe"]);
let mut forward = Graph::new();
let mut backward = Graph::new();
for format in [first.clone(), second.clone()] {
forward.add_format(format).unwrap();
}
for format in [second, first] {
backward.add_format(format).unwrap();
}
assert_eq!(forward.formats, backward.formats);
let before = forward.formats.clone();
assert!(
forward
.add_format(Format::new("jpeg", "wrong", MediaKind::Audio))
.is_err()
);
assert_eq!(forward.formats, before);
assert_eq!(
forward.format("jpeg").unwrap().extensions,
["jpe", "jpeg", "jpg"]
);
}
#[test]
fn resolving_prefers_ids_then_sorted_extension_aliases() {
let mut graph = graph(&["z", "a", "jpg", ".special"]);
graph
.add_format(Format::new("z", "z", MediaKind::Data).with_extensions(&["jpg", "shared"]))
.unwrap();
graph
.add_format(
Format::new("a", "a", MediaKind::Data).with_extensions(&["shared", "tar.gz"]),
)
.unwrap();
assert_eq!(graph.resolve(" .JPG ").unwrap().id, "jpg");
assert_eq!(graph.resolve("SHARED").unwrap().id, "a");
assert_eq!(graph.resolve(".tar.GZ").unwrap().id, "a");
assert_eq!(graph.resolve(".SPECIAL").unwrap().id, ".special");
assert!(graph.format("JPG").is_none());
assert!(graph.resolve("image/jpeg").is_none());
assert!(graph.resolve("file.tar.gz").is_none());
assert!(graph.resolve("").is_none());
assert_eq!(
graph
.formats()
.map(|format| format.id.as_str())
.collect::<Vec<_>>(),
[".special", "a", "jpg", "z"]
);
}
#[test]
fn conversions_require_valid_endpoints_metadata_and_cost() {
let mut graph = graph(&["a", "b"]);
for conversion in [
edge("a", "b", "backend", 0),
edge("a", "b", " ", 1),
Conversion::new("a", "b", "backend", "\n", ConversionKind::Lossless, 1),
edge("*", "b", "backend", 1),
] {
assert!(matches!(
graph.add_conversion(conversion),
Err(PlanError::Invalid(_))
));
}
for conversion in [
edge("missing", "b", "backend", 1),
edge("a", "*", "backend", 1),
] {
assert!(matches!(
graph.add_conversion(conversion),
Err(PlanError::UnknownFormat(_))
));
}
let conversion = edge("a", "b", "backend", 1);
graph.add_conversion(conversion.clone()).unwrap();
graph.add_conversion(conversion).unwrap();
assert_eq!(graph.routes("a", "b", &Policy::default()).unwrap().len(), 1);
}
#[test]
fn defaults_allow_lossless_lossy_bridge_and_extract_only() {
let policy = Policy::default();
assert_eq!(
(policy.max_steps, policy.max_routes, policy.max_expansions),
(6, 8, 20_000)
);
let mut graph = graph(&["a", "b"]);
for kind in [
ConversionKind::Lossless,
ConversionKind::Lossy,
ConversionKind::Bridge,
ConversionKind::Reinterpret,
ConversionKind::Package,
ConversionKind::Extract,
] {
graph
.add_conversion(Conversion::new("a", "b", "backend", "convert", kind, 1))
.unwrap();
}
let kinds = |policy: &Policy| {
graph
.routes("a", "b", policy)
.unwrap()
.iter()
.map(|plan| plan.steps[0].kind)
.collect::<BTreeSet<_>>()
};
assert_eq!(
kinds(&policy),
BTreeSet::from([
ConversionKind::Lossless,
ConversionKind::Lossy,
ConversionKind::Bridge,
ConversionKind::Extract,
])
);
let restricted = Policy {
allow_bridges: false,
..policy.clone()
};
assert_eq!(kinds(&restricted).len(), 3);
let enabled = Policy {
allow_reinterpret: true,
allow_packaging: true,
..policy
};
assert_eq!(kinds(&enabled).len(), 6);
}
#[test]
fn weighted_routes_keep_parallel_edges_and_alternative_prefixes() {
let mut graph = graph(&["s", "a", "b", "t"]);
for conversion in [
edge("s", "t", "direct", 20),
edge("s", "a", "first", 1),
edge("s", "a", "second", 2),
edge("s", "b", "third", 2),
edge("b", "a", "merge", 2),
edge("a", "t", "finish", 1),
edge("a", "s", "cycle", 1),
edge("a", "a", "self", 1),
] {
graph.add_conversion(conversion).unwrap();
}
let plans = graph.routes("s", "t", &Policy::default()).unwrap();
assert_eq!(
plans.iter().map(|plan| plan.cost).collect::<Vec<_>>(),
[2, 3, 5, 20]
);
assert_eq!(plans[0].steps[0].backend, "first");
assert_eq!(plans[1].steps[0].backend, "second");
for plan in plans {
let mut seen = BTreeSet::from(["s"]);
for step in &plan.steps {
assert!(seen.insert(&step.to));
}
}
assert!(matches!(
graph.routes("t", "s", &Policy::default()),
Err(PlanError::NoRoute { .. })
));
}
#[test]
fn wildcard_edges_are_opt_in_and_materialize_actual_inputs() {
let mut graph = graph(&["source", "binary", "target", "zip"]);
graph
.add_conversion(Conversion::new(
"*",
"binary",
"bytes",
"read",
ConversionKind::Reinterpret,
1,
))
.unwrap();
graph
.add_conversion(Conversion::new(
"*",
"zip",
"zip",
"pack",
ConversionKind::Package,
2,
))
.unwrap();
graph
.add_conversion(edge("binary", "target", "decode", 3))
.unwrap();
assert!(matches!(
graph.routes("source", "target", &Policy::default()),
Err(PlanError::NoRoute { .. })
));
assert!(matches!(
graph.routes("source", "zip", &Policy::default()),
Err(PlanError::NoRoute { .. })
));
let policy = Policy {
allow_reinterpret: true,
..Policy::default()
};
let plans = graph.routes("source", "target", &policy).unwrap();
assert_eq!(plans.len(), 1);
assert_eq!(plans[0].cost, 4);
assert_eq!(plans[0].steps[0].from, "source");
assert_eq!(plans[0].steps[1].from, "binary");
let policy = Policy {
allow_packaging: true,
..Policy::default()
};
let plans = graph.routes("source", "zip", &policy).unwrap();
assert_eq!(plans[0].steps[0].from, "source");
assert_eq!(plans[0].cost, 2);
}
#[test]
fn wildcard_specific_duplicates_do_not_repeat_plans() {
let mut graph = graph(&["a", "b"]);
for from in ["a", "*"] {
graph
.add_conversion(Conversion::new(
from,
"b",
"bytes",
"read",
ConversionKind::Reinterpret,
1,
))
.unwrap();
}
let policy = Policy {
allow_reinterpret: true,
..Policy::default()
};
assert_eq!(graph.routes("a", "b", &policy).unwrap().len(), 1);
}
#[test]
fn identity_unknown_and_cross_media_routes() {
let mut graph = Graph::new();
graph
.add_format(Format::new("text", "Text", MediaKind::Text).with_extensions(&["txt"]))
.unwrap();
graph
.add_format(Format::new("speech", "Speech", MediaKind::Audio))
.unwrap();
graph
.add_conversion(Conversion::new(
"text",
"speech",
"tts",
"speak",
ConversionKind::Bridge,
1,
))
.unwrap();
assert_eq!(
graph.routes(".TXT", "speech", &Policy::default()).unwrap()[0].cost,
1
);
let policy = Policy {
max_steps: 0,
max_expansions: 0,
..Policy::default()
};
assert_eq!(
graph.routes("text", "TXT", &policy).unwrap(),
[Plan {
steps: vec![],
cost: 0
}]
);
assert!(matches!(
graph.routes("text", "speech", &policy),
Err(PlanError::NoRoute { .. })
));
assert_eq!(
graph.routes("unknown", "unknown", &policy),
Err(PlanError::UnknownFormat("unknown".into()))
);
assert_eq!(
graph.routes("text", "unknown", &policy),
Err(PlanError::UnknownFormat("unknown".into()))
);
}
#[test]
fn step_limit_and_large_costs_are_respected() {
let mut graph = graph(&["a", "b", "c"]);
graph
.add_conversion(edge("a", "b", "backend", u32::MAX))
.unwrap();
graph
.add_conversion(edge("b", "c", "backend", u32::MAX))
.unwrap();
let policy = Policy {
max_steps: 1,
..Policy::default()
};
assert!(matches!(
graph.routes("a", "c", &policy),
Err(PlanError::NoRoute { .. })
));
assert_eq!(
graph.routes("a", "c", &Policy::default()).unwrap()[0].cost,
2 * u64::from(u32::MAX)
);
}
#[test]
fn expansion_bound_distinguishes_failure_from_partial_results() {
let mut graph = graph(&["s", "a", "t"]);
graph.add_conversion(edge("s", "a", "indirect", 5)).unwrap();
graph.add_conversion(edge("s", "t", "direct", 1)).unwrap();
graph.add_conversion(edge("a", "t", "finish", 5)).unwrap();
let policy = Policy {
max_expansions: 0,
..Policy::default()
};
assert_eq!(graph.routes("s", "t", &policy), Err(PlanError::SearchLimit));
let policy = Policy {
max_expansions: 2,
..policy
};
let plans = graph.routes("s", "t", &policy).unwrap();
assert_eq!(plans.len(), 1);
assert_eq!(plans[0].cost, 1);
let policy = Policy {
max_routes: 0,
..policy
};
assert!(matches!(
graph.routes("s", "t", &policy),
Err(PlanError::Invalid(_))
));
}
#[test]
fn target_heuristic_avoids_combinatorial_dead_ends() {
let mut graph = graph(&["s", "t"]);
for index in 0..10 {
graph
.add_format(Format::new(
&format!("dead{index}"),
"Dead",
MediaKind::Data,
))
.unwrap();
}
for from in 0..10 {
graph
.add_conversion(edge("s", &format!("dead{from}"), "dead", 1))
.unwrap();
for to in 0..10 {
graph
.add_conversion(edge(
&format!("dead{from}"),
&format!("dead{to}"),
"dead",
1,
))
.unwrap();
}
}
graph.add_conversion(edge("s", "t", "direct", 100)).unwrap();
let policy = Policy {
max_expansions: 11,
..Policy::default()
};
let plans = graph.routes("s", "t", &policy).unwrap();
assert_eq!(plans.len(), 1);
assert_eq!(plans[0].cost, 100);
}
#[test]
fn ties_stop_at_requested_routes_without_expanding_all_prefixes() {
let mut graph = graph(&["s", "a", "t"]);
graph.add_conversion(edge("s", "a", "indirect", 1)).unwrap();
graph.add_conversion(edge("s", "t", "direct", 2)).unwrap();
graph.add_conversion(edge("a", "t", "finish", 1)).unwrap();
let policy = Policy {
max_routes: 1,
max_expansions: 2,
..Policy::default()
};
let plans = graph.routes("s", "t", &policy).unwrap();
assert_eq!(plans.len(), 1);
assert_eq!(plans[0].steps.len(), 1);
}
#[test]
fn registration_order_does_not_change_route_order() {
let mut forward = graph(&["s", "a", "b", "t"]);
let mut backward = graph(&["t", "b", "a", "s"]);
let edges = [
edge("s", "a", "z", 1),
edge("s", "a", "a", 1),
edge("s", "b", "b", 1),
edge("a", "t", "end", 1),
edge("b", "t", "end", 1),
edge("s", "t", "direct", 2),
edge("a", "b", "cycle", 1),
edge("b", "a", "cycle", 1),
Conversion::new("*", "t", "zip", "pack", ConversionKind::Package, 2),
];
for edge in &edges {
forward.add_conversion(edge.clone()).unwrap();
}
for edge in edges.iter().rev() {
backward.add_conversion(edge.clone()).unwrap();
}
let policy = Policy {
allow_packaging: true,
max_routes: 64,
..Policy::default()
};
assert_eq!(
forward.routes("s", "t", &policy),
backward.routes("s", "t", &policy)
);
}
#[test]
fn route_and_step_limits_have_hard_caps() {
let mut graph = graph(&["s", "t"]);
for index in 0..70 {
graph
.add_conversion(edge("s", "t", &format!("backend{index:02}"), 1))
.unwrap();
}
let policy = Policy {
max_routes: usize::MAX,
max_steps: usize::MAX,
max_expansions: usize::MAX,
..Policy::default()
};
assert_eq!(graph.routes("s", "t", &policy).unwrap().len(), 64);
for index in 0..66 {
graph
.add_format(Format::new(&format!("f{index}"), "Format", MediaKind::Data))
.unwrap();
if index > 0 {
graph
.add_conversion(edge(
&format!("f{}", index - 1),
&format!("f{index}"),
"chain",
1,
))
.unwrap();
}
}
assert_eq!(
graph.routes("f0", "f64", &policy).unwrap()[0].steps.len(),
64
);
assert!(matches!(
graph.routes("f0", "f65", &policy),
Err(PlanError::NoRoute { .. })
));
}
#[test]
fn astar_matches_exhaustive_loopless_enumeration() {
fn enumerate(
graph: &Graph,
current: &str,
visited: &mut Vec<String>,
steps: &mut Vec<Conversion>,
plans: &mut Vec<Plan>,
policy: &Policy,
) {
if current == "t" {
plans.push(Plan {
steps: steps.clone(),
cost: steps.iter().map(|step| u64::from(step.cost)).sum(),
});
return;
}
if steps.len() == policy.max_steps {
return;
}
for edge in graph
.conversions
.get(current)
.into_iter()
.flatten()
.chain(graph.conversions.get("*").into_iter().flatten())
{
if policy.allows_edge(edge) && !visited.contains(&edge.to) {
visited.push(edge.to.clone());
let mut step = edge.clone();
step.from = current.to_owned();
steps.push(step);
enumerate(graph, &edge.to, visited, steps, plans, policy);
steps.pop();
visited.pop();
}
}
}
let ids = ["s", "a", "b", "c", "t"];
for seed in 0..24 {
let policy = Policy {
allow_packaging: seed % 2 == 0,
max_steps: seed % 5 + 1,
max_routes: 64,
..Policy::default()
};
let mut graph = graph(&ids);
for (i, from) in ids.iter().enumerate() {
for (j, to) in ids.iter().enumerate() {
let value = seed * 31 + i * 17 + j * 7;
if value % 4 != 0 {
graph
.add_conversion(edge(from, to, "backend", (value % 11 + 1) as u32))
.unwrap();
}
}
}
for target in ["a", "t"] {
graph
.add_conversion(Conversion::new(
"*",
target,
"wildcard",
"pack",
ConversionKind::Package,
(seed % 3 + 1) as u32,
))
.unwrap();
}
let mut expected = vec![];
enumerate(
&graph,
"s",
&mut vec!["s".into()],
&mut vec![],
&mut expected,
&policy,
);
if expected.is_empty() {
assert!(matches!(
graph.routes("s", "t", &policy),
Err(PlanError::NoRoute { .. })
));
continue;
}
let mut actual = graph.routes("s", "t", &policy).unwrap();
assert!(actual.windows(2).all(|pair| pair[0].cost <= pair[1].cost));
expected.sort_by(|a, b| (a.cost, &a.steps).cmp(&(b.cost, &b.steps)));
actual.sort_by(|a, b| (a.cost, &a.steps).cmp(&(b.cost, &b.steps)));
assert_eq!(actual, expected, "seed {seed}");
}
}
}