1#![warn(missing_docs)]
32
33use std::cmp::Reverse;
34use std::collections::{BTreeMap, BinaryHeap};
35use std::fmt;
36use std::rc::Rc;
37
38#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
42pub enum MediaKind {
43 Binary,
45 Text,
47 Data,
49 Image,
51 Audio,
53 Video,
55 Document,
57 Archive,
59 Model,
61 Font,
63}
64
65impl fmt::Display for MediaKind {
66 fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
67 formatter.write_str(match self {
68 Self::Binary => "binary",
69 Self::Text => "text",
70 Self::Data => "data",
71 Self::Image => "image",
72 Self::Audio => "audio",
73 Self::Video => "video",
74 Self::Document => "document",
75 Self::Archive => "archive",
76 Self::Model => "model",
77 Self::Font => "font",
78 })
79 }
80}
81
82#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
93pub struct ContentKind {
94 pub kind: MediaKind,
96 pub codec: Option<String>,
98}
99
100impl ContentKind {
101 #[must_use]
103 pub fn new(kind: MediaKind) -> Self {
104 Self { kind, codec: None }
105 }
106
107 #[must_use]
109 pub fn with_codec(kind: MediaKind, codec: &str) -> Self {
110 Self {
111 kind,
112 codec: Some(codec.trim().to_ascii_lowercase()),
113 }
114 }
115
116 pub fn parse(value: &str) -> Result<Self, PlanError> {
121 let (kind, codec) = match value.split_once(':') {
122 Some((kind, codec)) => (kind, Some(codec)),
123 None => (value, None),
124 };
125 let kind = match kind.trim().to_ascii_lowercase().as_str() {
126 "binary" | "bin" => MediaKind::Binary,
127 "text" => MediaKind::Text,
128 "data" => MediaKind::Data,
129 "image" => MediaKind::Image,
130 "audio" => MediaKind::Audio,
131 "video" => MediaKind::Video,
132 "document" | "doc" => MediaKind::Document,
133 "archive" => MediaKind::Archive,
134 "model" => MediaKind::Model,
135 "font" => MediaKind::Font,
136 _ => {
137 return Err(PlanError::Invalid(format!("unknown content kind: {kind}")));
138 }
139 };
140 let mut parsed = match codec {
141 Some(codec) => Self::with_codec(kind, codec),
142 None => Self::new(kind),
143 };
144 normalize_content(&mut parsed)?;
145 Ok(parsed)
146 }
147
148 #[must_use]
154 pub fn matches(&self, observed: &Self) -> bool {
155 self.kind == observed.kind
156 && match (self.codec.as_deref(), observed.codec.as_deref()) {
157 (None, _) => true,
158 (_, None) => false,
159 (Some(wanted), Some(found)) => wanted == found,
160 }
161 }
162}
163
164impl std::str::FromStr for ContentKind {
165 type Err = PlanError;
166
167 fn from_str(value: &str) -> Result<Self, Self::Err> {
168 Self::parse(value)
169 }
170}
171impl fmt::Display for ContentKind {
172 fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
173 match self.codec.as_deref() {
174 Some(codec) => write!(formatter, "{}:{}", self.kind, codec),
175 None => fmt::Display::fmt(&self.kind, formatter),
176 }
177 }
178}
179
180#[derive(Clone, Debug, PartialEq, Eq)]
182pub struct Stream {
183 pub index: usize,
185 pub content: ContentKind,
187 pub label: Option<String>,
189}
190
191impl Stream {
192 #[must_use]
194 pub fn new(index: usize, content: ContentKind) -> Self {
195 Self {
196 index,
197 content,
198 label: None,
199 }
200 }
201
202 #[must_use]
204 pub fn with_label(mut self, label: &str) -> Self {
205 self.label = Some(label.to_owned());
206 self
207 }
208}
209
210#[derive(Clone, Debug, Default, PartialEq, Eq)]
218#[non_exhaustive]
219pub struct ContentProfile {
220 pub format: String,
222 pub streams: Vec<Stream>,
224}
225
226impl ContentProfile {
227 #[must_use]
229 pub fn new(format: &str) -> Self {
230 Self {
231 format: format.to_owned(),
232 streams: Vec::new(),
233 }
234 }
235
236 #[must_use]
238 pub fn with_stream(mut self, content: ContentKind) -> Self {
239 self.streams.push(Stream::new(self.streams.len(), content));
240 self
241 }
242
243 pub fn add_stream(&mut self, stream: Stream) -> &mut Self {
245 self.streams.push(stream);
246 self
247 }
248
249 #[must_use]
251 pub fn declares(&self, want: &ContentKind) -> bool {
252 self.streams
253 .iter()
254 .any(|stream| want.matches(&stream.content))
255 }
256
257 #[must_use]
259 pub fn declares_all(&self, wants: &[ContentKind]) -> bool {
260 wants.iter().all(|want| self.declares(want))
261 }
262
263 #[must_use]
266 pub fn stream_kinds(&self) -> Vec<ContentKind> {
267 let mut kinds: Vec<ContentKind> = Vec::with_capacity(self.streams.len());
268 for stream in &self.streams {
269 if !kinds.contains(&stream.content) {
270 kinds.push(stream.content.clone());
271 }
272 }
273 kinds
274 }
275
276 pub fn deduplicate(&mut self) {
279 let mut kept: Vec<Stream> = Vec::with_capacity(self.streams.len());
280 for stream in self.streams.drain(..) {
281 if !kept
282 .iter()
283 .any(|previous| previous.content == stream.content)
284 {
285 kept.push(stream);
286 }
287 }
288 for (index, stream) in kept.iter_mut().enumerate() {
289 stream.index = index;
290 }
291 self.streams = kept;
292 }
293}
294
295#[derive(Clone, Debug, PartialEq, Eq)]
300#[non_exhaustive]
301pub struct Format {
302 pub id: String,
304 pub name: String,
306 pub extensions: Vec<String>,
308 pub media: MediaKind,
310 pub decode_only: bool,
316 pub mime_types: Vec<String>,
322 pub payloads: Vec<ContentKind>,
332 pub container: Option<String>,
339}
340
341impl Format {
342 pub fn new(id: &str, name: &str, media: MediaKind) -> Self {
346 Self {
347 id: id.to_owned(),
348 name: name.to_owned(),
349 extensions: Vec::new(),
350 media,
351 decode_only: false,
352 mime_types: Vec::new(),
353 payloads: Vec::new(),
354 container: None,
355 }
356 }
357
358 pub fn with_extensions(mut self, extensions: &[&str]) -> Self {
363 self.extensions = extensions.iter().map(|value| extension(value)).collect();
364 self.extensions.sort();
365 self.extensions.dedup();
366 self
367 }
368
369 pub fn with_mime(mut self, mime_types: &[&str]) -> Self {
374 self.mime_types = mime_types
375 .iter()
376 .map(|value| value.trim().to_ascii_lowercase())
377 .collect();
378 self.mime_types.sort();
379 self.mime_types.dedup();
380 self
381 }
382
383 #[must_use]
385 pub fn decode_only(mut self) -> Self {
386 self.decode_only = true;
387 self
388 }
389
390 #[must_use]
395 pub fn with_payloads(mut self, payloads: &[ContentKind]) -> Self {
396 let mut merged = payloads.to_vec();
397 merged.dedup();
398 self.payloads = merged;
399 self
400 }
401
402 #[must_use]
408 pub fn in_container(mut self, container: &str) -> Self {
409 self.container = Some(extension(container));
410 self
411 }
412}
413
414#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
420pub enum ConversionKind {
421 Lossless,
423 Lossy,
425 Bridge,
427 Reinterpret,
429 Package,
431 Extract,
433 Reencode,
441}
442
443#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
451pub enum ConversionCategory {
452 Standard,
454 Creative,
456}
457
458#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
463#[non_exhaustive]
464pub struct Conversion {
465 pub from: String,
467 pub to: String,
469 pub backend: String,
471 pub operation: String,
473 pub kind: ConversionKind,
475 pub cost: u32,
477 pub external: bool,
479 pub note: Option<String>,
484 pub category: ConversionCategory,
487 pub retained: Vec<String>,
494 pub requires: Vec<ContentKind>,
505 pub produces: Vec<ContentKind>,
511}
512
513impl Conversion {
514 pub fn new(
519 from: &str,
520 to: &str,
521 backend: &str,
522 operation: &str,
523 kind: ConversionKind,
524 cost: u32,
525 ) -> Self {
526 Self {
527 from: from.to_owned(),
528 to: to.to_owned(),
529 backend: backend.to_owned(),
530 operation: operation.to_owned(),
531 kind,
532 cost,
533 external: false,
534 note: None,
535 category: ConversionCategory::Standard,
536 retained: Vec::new(),
537 requires: Vec::new(),
538 produces: Vec::new(),
539 }
540 }
541
542 #[must_use]
544 pub fn requires_external(mut self) -> Self {
545 self.external = true;
546 self
547 }
548
549 #[must_use]
551 pub fn with_note(mut self, note: &str) -> Self {
552 self.note = Some(note.to_owned());
553 self
554 }
555
556 #[must_use]
558 pub fn with_kind(mut self, kind: ConversionKind) -> Self {
559 self.kind = kind;
560 self
561 }
562
563 #[must_use]
565 pub fn with_cost(mut self, cost: u32) -> Self {
566 self.cost = cost;
567 self
568 }
569
570 #[must_use]
572 pub fn creative(mut self) -> Self {
573 self.category = ConversionCategory::Creative;
574 self
575 }
576
577 #[must_use]
579 pub fn with_category(mut self, category: ConversionCategory) -> Self {
580 self.category = category;
581 self
582 }
583
584 #[must_use]
589 pub fn with_retained(mut self, properties: &[&str]) -> Self {
590 self.retained = properties
591 .iter()
592 .map(|value| value.trim().to_ascii_lowercase())
593 .collect();
594 self.retained.sort();
595 self.retained.dedup();
596 self
597 }
598
599 #[must_use]
604 pub fn retains_all(&self, required: &[&str]) -> bool {
605 required
606 .iter()
607 .map(|value| value.trim().to_ascii_lowercase())
608 .filter(|value| !value.is_empty())
609 .all(|value| self.retained.contains(&value))
610 }
611
612 #[must_use]
615 pub fn requiring(mut self, content: &[ContentKind]) -> Self {
616 let mut merged = content.to_vec();
617 merged.sort_by(|left, right| {
618 left.kind
619 .cmp(&right.kind)
620 .then_with(|| left.codec.cmp(&right.codec))
621 });
622 merged.dedup();
623 self.requires = merged;
624 self
625 }
626
627 #[must_use]
630 pub fn producing(mut self, content: &[ContentKind]) -> Self {
631 let mut merged = content.to_vec();
632 merged.sort_by(|left, right| {
633 left.kind
634 .cmp(&right.kind)
635 .then_with(|| left.codec.cmp(&right.codec))
636 });
637 merged.dedup();
638 self.produces = merged;
639 self
640 }
641
642 #[must_use]
650 pub fn content_satisfies(
651 &self,
652 requirements: &[ContentKind],
653 profile: Option<&ContentProfile>,
654 payloads: &[ContentKind],
655 ) -> bool {
656 requirements.iter().all(|wanted| match profile {
657 Some(profile) => profile.declares(wanted),
658 None => payloads.iter().any(|declared| wanted.matches(declared)),
659 })
660 }
661}
662
663#[derive(Clone, Debug, PartialEq, Eq)]
674pub struct Policy {
675 pub allow_bridges: bool,
677 pub allow_lossy: bool,
683 pub allow_reinterpret: bool,
685 pub allow_packaging: bool,
687 pub allow_external: bool,
690 pub allow_external_packaging: bool,
694 pub allow_decode_only: bool,
699 pub allow_empty_inputs: bool,
705 pub max_steps: usize,
707 pub max_routes: usize,
709 pub max_expansions: usize,
713 pub retain: Vec<String>,
723 pub backends: Vec<String>,
730 pub reencode_same_format: bool,
741 pub require: Vec<ContentKind>,
751 pub inspect_content: bool,
759 pub require_content: bool,
768 pub allow_creative: bool,
777}
778
779impl Default for Policy {
780 fn default() -> Self {
781 Self {
782 allow_bridges: true,
783 allow_lossy: true,
784 allow_reinterpret: false,
785 allow_packaging: false,
786 allow_external: false,
787 allow_external_packaging: false,
788 allow_decode_only: false,
789 allow_empty_inputs: false,
790 max_steps: 6,
791 max_routes: 8,
792 max_expansions: 20_000,
793 retain: Vec::new(),
794 backends: Vec::new(),
795 reencode_same_format: false,
796 require: Vec::new(),
797 inspect_content: false,
798 require_content: false,
799 allow_creative: false,
800 }
801 }
802}
803
804impl Policy {
805 pub fn normalized(mut self) -> Result<Self, PlanError> {
812 for entry in &mut self.require {
813 normalize_content(entry)?;
814 }
815 self.require.sort_by(|left, right| {
816 kind_order(&left.kind)
817 .cmp(&kind_order(&right.kind))
818 .then_with(|| {
819 codec_order(left.codec.as_deref()).cmp(&codec_order(right.codec.as_deref()))
820 })
821 });
822 self.require.dedup();
823 Ok(self)
824 }
825
826 #[must_use]
832 pub fn allows(&self, kind: ConversionKind) -> bool {
833 match kind {
834 ConversionKind::Lossless => true,
835 ConversionKind::Lossy => self.allow_lossy,
836 ConversionKind::Reencode => self.allow_lossy,
837 ConversionKind::Extract => true,
838 ConversionKind::Bridge => self.allow_bridges,
839 ConversionKind::Reinterpret => self.allow_reinterpret,
840 ConversionKind::Package => self.allow_packaging,
841 }
842 }
843
844 #[must_use]
868 pub fn allows_edge(&self, conversion: &Conversion) -> bool {
869 if !self.allows(conversion.kind) {
870 return false;
871 }
872 if conversion.category == ConversionCategory::Creative && !self.allow_creative {
873 return false;
874 }
875 if conversion.external {
876 if !self.allow_external {
877 return false;
878 }
879 if matches!(
880 conversion.kind,
881 ConversionKind::Reinterpret | ConversionKind::Package
882 ) && !self.allow_external_packaging
883 {
884 return false;
885 }
886 }
887 true
888 }
889
890 #[must_use]
895 pub fn permits_backend(&self, backend: &str) -> bool {
896 self.backends.is_empty()
897 || self
898 .backends
899 .iter()
900 .any(|allowed| allowed.trim() == backend)
901 }
902
903 #[must_use]
908 pub fn retains(&self, conversion: &Conversion) -> bool {
909 self.retain.iter().all(|required| {
910 let required = required.trim().to_ascii_lowercase();
911 conversion.retained.iter().any(|held| held == &required)
912 })
913 }
914}
915
916#[derive(Clone, Debug, PartialEq, Eq)]
922#[non_exhaustive]
923pub struct Plan {
924 pub steps: Vec<Conversion>,
929 pub cost: u64,
933}
934
935impl Plan {
936 #[must_use]
941 pub fn new(steps: Vec<Conversion>) -> Self {
942 let cost = steps.iter().fold(0_u64, |total, step| {
943 total.saturating_add(u64::from(step.cost))
944 });
945 Self { steps, cost }
946 }
947
948 #[must_use]
956 pub fn produced(&self) -> &[ContentKind] {
957 self.steps.last().map_or(&[], |last| &last.produces)
958 }
959}
960
961impl Default for Plan {
962 fn default() -> Self {
964 Self {
965 steps: Vec::new(),
966 cost: 0,
967 }
968 }
969}
970
971#[derive(Clone, Debug, PartialEq, Eq, thiserror::Error)]
973pub enum PlanError {
974 #[error("invalid graph or policy: {0}")]
976 Invalid(
977 String,
979 ),
980 #[error("unknown format: {0}")]
982 UnknownFormat(
983 String,
985 ),
986 #[error("no route from {from} to {to}")]
988 NoRoute {
989 from: String,
991 to: String,
993 },
994 #[error("route search limit reached before finding a route")]
996 SearchLimit,
997}
998
999#[derive(Clone, Debug, Default)]
1004pub struct Graph {
1005 formats: BTreeMap<String, Format>,
1006 conversions: BTreeMap<String, Vec<Conversion>>,
1007}
1008
1009impl Graph {
1010 pub fn new() -> Self {
1012 Self::default()
1013 }
1014
1015 pub fn add_format(&mut self, mut format: Format) -> Result<(), PlanError> {
1026 if !valid_id(&format.id) {
1027 return Err(PlanError::Invalid(format!(
1028 "invalid format ID: {:?}",
1029 format.id
1030 )));
1031 }
1032 for value in &mut format.extensions {
1033 *value = extension(value);
1034 if !valid_id(value) {
1035 return Err(PlanError::Invalid(format!(
1036 "invalid extension for {}: {value:?}",
1037 format.id
1038 )));
1039 }
1040 }
1041 for value in &format.mime_types {
1042 if value.is_empty() || value.chars().any(char::is_whitespace) {
1043 return Err(PlanError::Invalid(format!(
1044 "invalid MIME type for {}: {value:?}",
1045 format.id
1046 )));
1047 }
1048 }
1049 format.extensions.sort();
1050 format.extensions.dedup();
1051 for entry in &mut format.payloads {
1052 normalize_content(entry)?;
1053 }
1054 format.payloads.dedup();
1055 if let Some(name) = &mut format.container {
1056 *name = name.trim().to_ascii_lowercase();
1057 if !valid_id(name) {
1058 return Err(PlanError::Invalid(format!(
1059 "invalid container name for {}",
1060 format.id
1061 )));
1062 }
1063 }
1064 if let Some(existing) = self.formats.get_mut(&format.id) {
1065 if existing.media != format.media {
1066 return Err(PlanError::Invalid(format!(
1067 "conflicting media categories for {}",
1068 format.id
1069 )));
1070 }
1071 if format.name < existing.name {
1072 existing.name = format.name;
1073 }
1074 existing.extensions.extend(format.extensions);
1075 existing.extensions.sort();
1076 existing.extensions.dedup();
1077 existing.mime_types.extend(format.mime_types);
1078 existing.mime_types.sort();
1079 existing.mime_types.dedup();
1080 existing.payloads.extend(format.payloads);
1081 existing.payloads.dedup();
1082 if existing.container.is_none() {
1083 existing.container = format.container;
1084 }
1085 } else {
1086 self.formats.insert(format.id.clone(), format);
1087 }
1088 Ok(())
1089 }
1090
1091 pub fn add_conversion(&mut self, mut conversion: Conversion) -> Result<(), PlanError> {
1108 if conversion.cost == 0 {
1109 return Err(PlanError::Invalid(
1110 "conversion cost must be positive".into(),
1111 ));
1112 }
1113 for entry in &mut conversion.requires {
1114 normalize_content(entry)?;
1115 }
1116 for entry in &mut conversion.produces {
1117 normalize_content(entry)?;
1118 }
1119 if conversion.backend.trim().is_empty() || conversion.operation.trim().is_empty() {
1120 return Err(PlanError::Invalid(
1121 "conversion backend and operation must be nonempty".into(),
1122 ));
1123 }
1124 if conversion.from == "*" {
1125 if !matches!(
1126 conversion.kind,
1127 ConversionKind::Reinterpret | ConversionKind::Package
1128 ) {
1129 return Err(PlanError::Invalid(
1130 "wildcard input requires Reinterpret or Package".into(),
1131 ));
1132 }
1133 } else if !self.formats.contains_key(&conversion.from) {
1134 return Err(PlanError::UnknownFormat(conversion.from));
1135 }
1136 if !self.formats.contains_key(&conversion.to) {
1137 return Err(PlanError::UnknownFormat(conversion.to));
1138 }
1139 let edges = self.conversions.entry(conversion.from.clone()).or_default();
1140 if let Err(index) = edges.binary_search(&conversion) {
1141 edges.insert(index, conversion);
1142 }
1143 Ok(())
1144 }
1145
1146 pub fn formats(&self) -> impl Iterator<Item = &Format> {
1148 self.formats.values()
1149 }
1150
1151 pub fn conversions(&self) -> impl Iterator<Item = &Conversion> {
1153 self.conversions.values().flatten()
1154 }
1155
1156 pub fn format(&self, id: &str) -> Option<&Format> {
1158 self.formats.get(id)
1159 }
1160
1161 pub fn resolve(&self, value: &str) -> Option<&Format> {
1168 let normalized = value.trim().to_ascii_lowercase();
1169 if let Some(format) = self.formats.get(&normalized) {
1170 return Some(format);
1171 }
1172 let alias = normalized.trim_start_matches('.');
1173 if let Some(format) = self.formats.get(alias) {
1174 return Some(format);
1175 }
1176 let by_alias = self
1177 .formats
1178 .values()
1179 .find(|format| format.extensions.iter().any(|value| value == alias));
1180 by_alias.or_else(|| {
1181 normalized
1182 .contains('/')
1183 .then(|| {
1184 self.formats
1185 .values()
1186 .find(|format| format.mime_types.iter().any(|mime| mime == &normalized))
1187 })
1188 .flatten()
1189 })
1190 }
1191
1192 pub fn routes(&self, from: &str, to: &str, policy: &Policy) -> Result<Vec<Plan>, PlanError> {
1224 let policy = policy.clone().normalized()?;
1225 self.search(from, to, &policy, None)
1226 }
1227
1228 pub fn routes_with_profile(
1251 &self,
1252 from: &str,
1253 to: &str,
1254 policy: &Policy,
1255 profile: Option<&ContentProfile>,
1256 ) -> Result<Vec<Plan>, PlanError> {
1257 let policy = policy.clone().normalized()?;
1258 let profile = profile.filter(|found| self.formats.contains_key(&found.format));
1259 self.search(from, to, &policy, profile)
1260 }
1261
1262 fn search(
1263 &self,
1264 from: &str,
1265 to: &str,
1266 policy: &Policy,
1267 profile: Option<&ContentProfile>,
1268 ) -> Result<Vec<Plan>, PlanError> {
1269 let from = self
1270 .resolve(from)
1271 .ok_or_else(|| PlanError::UnknownFormat(from.to_owned()))?;
1272 let to = self
1273 .resolve(to)
1274 .ok_or_else(|| PlanError::UnknownFormat(to.to_owned()))?;
1275 if policy.max_routes == 0 {
1276 return Err(PlanError::Invalid("max_routes must be positive".into()));
1277 }
1278 let same_format = from.id == to.id;
1279 let target_ok = |plan: &Plan| -> bool {
1280 policy.require.iter().all(|wanted| {
1281 profile
1282 .filter(|found| found.format == to.id)
1283 .is_some_and(|found| found.declares(wanted))
1284 || plan
1285 .produced()
1286 .iter()
1287 .any(|produced| wanted.matches(produced))
1288 || (!policy.require_content
1289 && to.payloads.iter().any(|declared| wanted.matches(declared)))
1290 })
1291 };
1292 if same_format && !policy.reencode_same_format {
1293 let identity = Plan::default();
1296 return if target_ok(&identity) {
1297 Ok(vec![identity])
1298 } else {
1299 Err(PlanError::NoRoute {
1300 from: from.id.clone(),
1301 to: to.id.clone(),
1302 })
1303 };
1304 }
1305 let no_route = || PlanError::NoRoute {
1306 from: from.id.clone(),
1307 to: to.id.clone(),
1308 };
1309 let max_steps = policy.max_steps.min(64);
1310 let max_routes = policy.max_routes.min(64);
1311 let max_expansions = policy.max_expansions.min(100_000);
1312 if max_steps == 0 {
1313 return Err(no_route());
1314 }
1315 let content_usable = |edge: &Conversion, source: &str| -> bool {
1316 edge.requires.is_empty()
1317 || match profile.filter(|found| found.format == source) {
1318 Some(found) => covers(&edge.requires, &found.stream_kinds()),
1319 None if policy.require_content => false,
1320 None => self
1321 .formats
1322 .get(source)
1323 .is_some_and(|format| covers(&edge.requires, &format.payloads)),
1324 }
1325 };
1326 let usable = |edge: &Conversion| {
1327 policy.allows_edge(edge)
1328 && policy.permits_backend(&edge.backend)
1329 && policy.retains(edge)
1330 && (edge.from == "*" || content_usable(edge, &edge.from))
1331 };
1332 let distances = self.distances_to(&to.id, &usable);
1333 let Some(&estimate) = distances.get(from.id.as_str()) else {
1334 return Err(no_route());
1335 };
1336 let mut frontier = BTreeMap::new();
1337 frontier.insert(
1338 (estimate, Reverse(0_u64), 0_usize),
1339 Rc::new(SearchPath {
1340 format: &from.id,
1341 edge: None,
1342 previous: None,
1343 cost: 0,
1344 depth: 0,
1345 }),
1346 );
1347 let mut plans = Vec::new();
1348 let mut expansions = 0;
1349 while let Some((_, path)) = frontier.pop_first() {
1350 if path.format == to.id && path.depth > 0 {
1353 let plan = path.plan();
1354 if target_ok(&plan) && !plans.contains(&plan) {
1356 plans.push(plan);
1357 }
1358 if plans.len() == max_routes {
1359 return Ok(plans);
1360 }
1361 continue;
1362 }
1363 if path.depth == max_steps {
1364 continue;
1365 }
1366 let edges = self
1367 .conversions
1368 .get(path.format)
1369 .into_iter()
1370 .flatten()
1371 .chain(self.conversions.get("*").into_iter().flatten());
1372 for edge in edges {
1373 if expansions == max_expansions {
1374 return if plans.is_empty() {
1375 Err(PlanError::SearchLimit)
1376 } else {
1377 Ok(plans)
1378 };
1379 }
1380 expansions += 1;
1381 if !usable(edge) {
1382 continue;
1383 }
1384 if edge.from == "*" && !content_usable(edge, path.format) {
1387 continue;
1388 }
1389 let revisit = same_format && edge.to == to.id;
1394 if !revisit && path.contains(&edge.to) {
1395 continue;
1396 }
1397 if self
1398 .formats
1399 .get(&edge.to)
1400 .is_some_and(|format| format.decode_only)
1401 && !policy.allow_decode_only
1402 {
1403 continue;
1404 }
1405 let Some(&remaining) = distances.get(edge.to.as_str()) else {
1406 continue;
1407 };
1408 let cost = path.cost + u64::from(edge.cost);
1409 frontier.insert(
1410 (cost.saturating_add(remaining), Reverse(cost), expansions),
1411 Rc::new(SearchPath {
1412 format: &edge.to,
1413 edge: Some(edge),
1414 previous: Some(Rc::clone(&path)),
1415 cost,
1416 depth: path.depth + 1,
1417 }),
1418 );
1419 }
1420 }
1421 if plans.is_empty() {
1422 Err(no_route())
1423 } else {
1424 Ok(plans)
1425 }
1426 }
1427
1428 fn distances_to<'a>(
1429 &'a self,
1430 target: &'a str,
1431 usable: &impl Fn(&Conversion) -> bool,
1432 ) -> BTreeMap<&'a str, u64> {
1433 let mut reverse: BTreeMap<&str, Vec<(&str, u64)>> = BTreeMap::new();
1434 for edge in self.conversions.values().flatten() {
1435 if usable(edge) {
1436 reverse
1437 .entry(&edge.to)
1438 .or_default()
1439 .push((&edge.from, u64::from(edge.cost)));
1440 }
1441 }
1442 let mut distances = BTreeMap::from([(target, 0_u64)]);
1443 let mut queue = BinaryHeap::from([Reverse((0_u64, target))]);
1444 while let Some(Reverse((cost, current))) = queue.pop() {
1445 if distances.get(current) != Some(&cost) {
1446 continue;
1447 }
1448 let mut relax = |source, weight| {
1449 let next = cost.saturating_add(weight);
1450 if distances.get(source).is_none_or(|&known| next < known) {
1451 distances.insert(source, next);
1452 queue.push(Reverse((next, source)));
1453 }
1454 };
1455 if current == "*" {
1456 for source in self.formats.keys() {
1458 relax(source.as_str(), 0);
1459 }
1460 } else if let Some(edges) = reverse.get(current) {
1461 for &(source, weight) in edges {
1462 relax(source, weight);
1463 }
1464 }
1465 }
1466 distances
1467 }
1468}
1469
1470fn valid_id(value: &str) -> bool {
1471 !value.is_empty()
1472 && value.len() <= 64
1473 && value.bytes().all(|byte| {
1474 byte.is_ascii_lowercase()
1475 || byte.is_ascii_digit()
1476 || matches!(byte, b'-' | b'_' | b'.' | b'+')
1477 })
1478}
1479
1480fn extension(value: &str) -> String {
1481 value.trim().trim_start_matches('.').to_ascii_lowercase()
1482}
1483
1484fn normalize_content(entry: &mut ContentKind) -> Result<(), PlanError> {
1485 if let Some(codec) = &mut entry.codec {
1486 *codec = codec.trim().to_ascii_lowercase();
1487 if codec.is_empty() {
1488 entry.codec = None;
1489 } else if !valid_id(codec) {
1490 return Err(PlanError::Invalid(format!("invalid codec tag: {codec:?}")));
1491 }
1492 }
1493 Ok(())
1494}
1495
1496fn kind_order(kind: &MediaKind) -> u8 {
1497 match kind {
1498 MediaKind::Binary => 0,
1499 MediaKind::Text => 1,
1500 MediaKind::Data => 2,
1501 MediaKind::Image => 3,
1502 MediaKind::Audio => 4,
1503 MediaKind::Video => 5,
1504 MediaKind::Document => 6,
1505 MediaKind::Archive => 7,
1506 MediaKind::Model => 8,
1507 MediaKind::Font => 9,
1508 }
1509}
1510
1511fn codec_order(codec: Option<&str>) -> (u8, &str) {
1512 match codec {
1513 None => (0, ""),
1514 Some(value) => (1, value),
1515 }
1516}
1517
1518fn covers(requirements: &[ContentKind], available: &[ContentKind]) -> bool {
1519 requirements
1520 .iter()
1521 .all(|wanted| available.iter().any(|found| wanted.matches(found)))
1522}
1523
1524struct SearchPath<'a> {
1526 format: &'a str,
1527 edge: Option<&'a Conversion>,
1528 previous: Option<Rc<Self>>,
1529 cost: u64,
1530 depth: usize,
1531}
1532
1533impl SearchPath<'_> {
1534 fn contains(&self, format: &str) -> bool {
1535 let mut current = Some(self);
1536 while let Some(path) = current {
1537 if path.format == format {
1538 return true;
1539 }
1540 current = path.previous.as_deref();
1541 }
1542 false
1543 }
1544
1545 fn plan(&self) -> Plan {
1546 let mut steps = Vec::with_capacity(self.depth);
1547 let mut current = self;
1548 while let (Some(edge), Some(previous)) = (current.edge, current.previous.as_deref()) {
1549 let mut step = edge.clone();
1550 step.from = previous.format.to_owned();
1551 steps.push(step);
1552 current = previous;
1553 }
1554 steps.reverse();
1555 Plan {
1556 steps,
1557 cost: self.cost,
1558 }
1559 }
1560}
1561
1562#[cfg(test)]
1563#[allow(clippy::unwrap_used, clippy::expect_used)]
1564mod tests {
1565 use super::*;
1566 use std::collections::BTreeSet;
1567
1568 fn graph(ids: &[&str]) -> Graph {
1569 let mut graph = Graph::new();
1570 for id in ids {
1571 graph
1572 .add_format(Format::new(id, id, MediaKind::Data))
1573 .unwrap();
1574 }
1575 graph
1576 }
1577
1578 fn edge(from: &str, to: &str, backend: &str, cost: u32) -> Conversion {
1579 Conversion::new(from, to, backend, "convert", ConversionKind::Lossless, cost)
1580 }
1581
1582 #[test]
1583 fn registration_validates_ids_and_normalizes_extensions() {
1584 let mut graph = Graph::new();
1585 for id in ["", "UPPER", "*", "a/b", "a b", "a\0b", "a:b"] {
1586 assert!(matches!(
1587 graph.add_format(Format::new(id, "name", MediaKind::Binary)),
1588 Err(PlanError::Invalid(_))
1589 ));
1590 }
1591 assert!(
1592 graph
1593 .add_format(Format::new(&"a".repeat(65), "name", MediaKind::Binary))
1594 .is_err()
1595 );
1596 graph
1597 .add_format(Format::new(&"a".repeat(64), "name", MediaKind::Binary))
1598 .unwrap();
1599 graph
1600 .add_format(
1601 Format::new("a-z_0.9+", "name", MediaKind::Binary)
1602 .with_extensions(&[" .ABC ", "abc", "tar.gz"]),
1603 )
1604 .unwrap();
1605 assert_eq!(
1606 graph.format("a-z_0.9+").unwrap().extensions,
1607 ["abc", "tar.gz"]
1608 );
1609 for alias in ["", ".", "a/b", "*"] {
1610 assert!(
1611 graph
1612 .add_format(
1613 Format::new("bad", "bad", MediaKind::Data).with_extensions(&[alias])
1614 )
1615 .is_err()
1616 );
1617 }
1618 assert!(graph.format("bad").is_none());
1619 }
1620
1621 #[test]
1622 fn duplicate_formats_merge_independently_of_registration_order() {
1623 let first = Format::new("jpeg", "JPEG", MediaKind::Image).with_extensions(&["jpeg", "jpg"]);
1624 let second = Format::new("jpeg", "Joint photographic", MediaKind::Image)
1625 .with_extensions(&["JPG", "jpe"]);
1626 let mut forward = Graph::new();
1627 let mut backward = Graph::new();
1628 for format in [first.clone(), second.clone()] {
1629 forward.add_format(format).unwrap();
1630 }
1631 for format in [second, first] {
1632 backward.add_format(format).unwrap();
1633 }
1634 assert_eq!(forward.formats, backward.formats);
1635 let before = forward.formats.clone();
1636 assert!(
1637 forward
1638 .add_format(Format::new("jpeg", "wrong", MediaKind::Audio))
1639 .is_err()
1640 );
1641 assert_eq!(forward.formats, before);
1642 assert_eq!(
1643 forward.format("jpeg").unwrap().extensions,
1644 ["jpe", "jpeg", "jpg"]
1645 );
1646 }
1647
1648 #[test]
1649 fn resolving_prefers_ids_then_sorted_extension_aliases() {
1650 let mut graph = graph(&["z", "a", "jpg", ".special"]);
1651 graph
1652 .add_format(Format::new("z", "z", MediaKind::Data).with_extensions(&["jpg", "shared"]))
1653 .unwrap();
1654 graph
1655 .add_format(
1656 Format::new("a", "a", MediaKind::Data).with_extensions(&["shared", "tar.gz"]),
1657 )
1658 .unwrap();
1659 assert_eq!(graph.resolve(" .JPG ").unwrap().id, "jpg");
1660 assert_eq!(graph.resolve("SHARED").unwrap().id, "a");
1661 assert_eq!(graph.resolve(".tar.GZ").unwrap().id, "a");
1662 assert_eq!(graph.resolve(".SPECIAL").unwrap().id, ".special");
1663 assert!(graph.format("JPG").is_none());
1664 assert!(graph.resolve("image/jpeg").is_none());
1665 assert!(graph.resolve("file.tar.gz").is_none());
1666 assert!(graph.resolve("").is_none());
1667 assert_eq!(
1668 graph
1669 .formats()
1670 .map(|format| format.id.as_str())
1671 .collect::<Vec<_>>(),
1672 [".special", "a", "jpg", "z"]
1673 );
1674 }
1675
1676 #[test]
1677 fn conversions_require_valid_endpoints_metadata_and_cost() {
1678 let mut graph = graph(&["a", "b"]);
1679 for conversion in [
1680 edge("a", "b", "backend", 0),
1681 edge("a", "b", " ", 1),
1682 Conversion::new("a", "b", "backend", "\n", ConversionKind::Lossless, 1),
1683 edge("*", "b", "backend", 1),
1684 ] {
1685 assert!(matches!(
1686 graph.add_conversion(conversion),
1687 Err(PlanError::Invalid(_))
1688 ));
1689 }
1690 for conversion in [
1691 edge("missing", "b", "backend", 1),
1692 edge("a", "*", "backend", 1),
1693 ] {
1694 assert!(matches!(
1695 graph.add_conversion(conversion),
1696 Err(PlanError::UnknownFormat(_))
1697 ));
1698 }
1699 let conversion = edge("a", "b", "backend", 1);
1700 graph.add_conversion(conversion.clone()).unwrap();
1701 graph.add_conversion(conversion).unwrap();
1702 assert_eq!(graph.routes("a", "b", &Policy::default()).unwrap().len(), 1);
1703 }
1704
1705 #[test]
1706 fn defaults_allow_lossless_lossy_bridge_and_extract_only() {
1707 let policy = Policy::default();
1708 assert_eq!(
1709 (policy.max_steps, policy.max_routes, policy.max_expansions),
1710 (6, 8, 20_000)
1711 );
1712 let mut graph = graph(&["a", "b"]);
1713 for kind in [
1714 ConversionKind::Lossless,
1715 ConversionKind::Lossy,
1716 ConversionKind::Bridge,
1717 ConversionKind::Reinterpret,
1718 ConversionKind::Package,
1719 ConversionKind::Extract,
1720 ] {
1721 graph
1722 .add_conversion(Conversion::new("a", "b", "backend", "convert", kind, 1))
1723 .unwrap();
1724 }
1725 let kinds = |policy: &Policy| {
1726 graph
1727 .routes("a", "b", policy)
1728 .unwrap()
1729 .iter()
1730 .map(|plan| plan.steps[0].kind)
1731 .collect::<BTreeSet<_>>()
1732 };
1733 assert_eq!(
1734 kinds(&policy),
1735 BTreeSet::from([
1736 ConversionKind::Lossless,
1737 ConversionKind::Lossy,
1738 ConversionKind::Bridge,
1739 ConversionKind::Extract,
1740 ])
1741 );
1742 let restricted = Policy {
1743 allow_bridges: false,
1744 ..policy.clone()
1745 };
1746 assert_eq!(kinds(&restricted).len(), 3);
1747 let enabled = Policy {
1748 allow_reinterpret: true,
1749 allow_packaging: true,
1750 ..policy
1751 };
1752 assert_eq!(kinds(&enabled).len(), 6);
1753 }
1754
1755 #[test]
1756 fn weighted_routes_keep_parallel_edges_and_alternative_prefixes() {
1757 let mut graph = graph(&["s", "a", "b", "t"]);
1758 for conversion in [
1759 edge("s", "t", "direct", 20),
1760 edge("s", "a", "first", 1),
1761 edge("s", "a", "second", 2),
1762 edge("s", "b", "third", 2),
1763 edge("b", "a", "merge", 2),
1764 edge("a", "t", "finish", 1),
1765 edge("a", "s", "cycle", 1),
1766 edge("a", "a", "self", 1),
1767 ] {
1768 graph.add_conversion(conversion).unwrap();
1769 }
1770 let plans = graph.routes("s", "t", &Policy::default()).unwrap();
1771 assert_eq!(
1772 plans.iter().map(|plan| plan.cost).collect::<Vec<_>>(),
1773 [2, 3, 5, 20]
1774 );
1775 assert_eq!(plans[0].steps[0].backend, "first");
1776 assert_eq!(plans[1].steps[0].backend, "second");
1777 for plan in plans {
1778 let mut seen = BTreeSet::from(["s"]);
1779 for step in &plan.steps {
1780 assert!(seen.insert(&step.to));
1781 }
1782 }
1783 assert!(matches!(
1784 graph.routes("t", "s", &Policy::default()),
1785 Err(PlanError::NoRoute { .. })
1786 ));
1787 }
1788
1789 #[test]
1790 fn wildcard_edges_are_opt_in_and_materialize_actual_inputs() {
1791 let mut graph = graph(&["source", "binary", "target", "zip"]);
1792 graph
1793 .add_conversion(Conversion::new(
1794 "*",
1795 "binary",
1796 "bytes",
1797 "read",
1798 ConversionKind::Reinterpret,
1799 1,
1800 ))
1801 .unwrap();
1802 graph
1803 .add_conversion(Conversion::new(
1804 "*",
1805 "zip",
1806 "zip",
1807 "pack",
1808 ConversionKind::Package,
1809 2,
1810 ))
1811 .unwrap();
1812 graph
1813 .add_conversion(edge("binary", "target", "decode", 3))
1814 .unwrap();
1815 assert!(matches!(
1816 graph.routes("source", "target", &Policy::default()),
1817 Err(PlanError::NoRoute { .. })
1818 ));
1819 assert!(matches!(
1820 graph.routes("source", "zip", &Policy::default()),
1821 Err(PlanError::NoRoute { .. })
1822 ));
1823 let policy = Policy {
1824 allow_reinterpret: true,
1825 ..Policy::default()
1826 };
1827 let plans = graph.routes("source", "target", &policy).unwrap();
1828 assert_eq!(plans.len(), 1);
1829 assert_eq!(plans[0].cost, 4);
1830 assert_eq!(plans[0].steps[0].from, "source");
1831 assert_eq!(plans[0].steps[1].from, "binary");
1832 let policy = Policy {
1833 allow_packaging: true,
1834 ..Policy::default()
1835 };
1836 let plans = graph.routes("source", "zip", &policy).unwrap();
1837 assert_eq!(plans[0].steps[0].from, "source");
1838 assert_eq!(plans[0].cost, 2);
1839 }
1840
1841 #[test]
1842 fn wildcard_specific_duplicates_do_not_repeat_plans() {
1843 let mut graph = graph(&["a", "b"]);
1844 for from in ["a", "*"] {
1845 graph
1846 .add_conversion(Conversion::new(
1847 from,
1848 "b",
1849 "bytes",
1850 "read",
1851 ConversionKind::Reinterpret,
1852 1,
1853 ))
1854 .unwrap();
1855 }
1856 let policy = Policy {
1857 allow_reinterpret: true,
1858 ..Policy::default()
1859 };
1860 assert_eq!(graph.routes("a", "b", &policy).unwrap().len(), 1);
1861 }
1862
1863 #[test]
1864 fn identity_unknown_and_cross_media_routes() {
1865 let mut graph = Graph::new();
1866 graph
1867 .add_format(Format::new("text", "Text", MediaKind::Text).with_extensions(&["txt"]))
1868 .unwrap();
1869 graph
1870 .add_format(Format::new("speech", "Speech", MediaKind::Audio))
1871 .unwrap();
1872 graph
1873 .add_conversion(Conversion::new(
1874 "text",
1875 "speech",
1876 "tts",
1877 "speak",
1878 ConversionKind::Bridge,
1879 1,
1880 ))
1881 .unwrap();
1882 assert_eq!(
1883 graph.routes(".TXT", "speech", &Policy::default()).unwrap()[0].cost,
1884 1
1885 );
1886 let policy = Policy {
1887 max_steps: 0,
1888 max_expansions: 0,
1889 ..Policy::default()
1890 };
1891 assert_eq!(
1892 graph.routes("text", "TXT", &policy).unwrap(),
1893 [Plan {
1894 steps: vec![],
1895 cost: 0
1896 }]
1897 );
1898 assert!(matches!(
1899 graph.routes("text", "speech", &policy),
1900 Err(PlanError::NoRoute { .. })
1901 ));
1902 assert_eq!(
1903 graph.routes("unknown", "unknown", &policy),
1904 Err(PlanError::UnknownFormat("unknown".into()))
1905 );
1906 assert_eq!(
1907 graph.routes("text", "unknown", &policy),
1908 Err(PlanError::UnknownFormat("unknown".into()))
1909 );
1910 }
1911
1912 #[test]
1913 fn step_limit_and_large_costs_are_respected() {
1914 let mut graph = graph(&["a", "b", "c"]);
1915 graph
1916 .add_conversion(edge("a", "b", "backend", u32::MAX))
1917 .unwrap();
1918 graph
1919 .add_conversion(edge("b", "c", "backend", u32::MAX))
1920 .unwrap();
1921 let policy = Policy {
1922 max_steps: 1,
1923 ..Policy::default()
1924 };
1925 assert!(matches!(
1926 graph.routes("a", "c", &policy),
1927 Err(PlanError::NoRoute { .. })
1928 ));
1929 assert_eq!(
1930 graph.routes("a", "c", &Policy::default()).unwrap()[0].cost,
1931 2 * u64::from(u32::MAX)
1932 );
1933 }
1934
1935 #[test]
1936 fn expansion_bound_distinguishes_failure_from_partial_results() {
1937 let mut graph = graph(&["s", "a", "t"]);
1938 graph.add_conversion(edge("s", "a", "indirect", 5)).unwrap();
1939 graph.add_conversion(edge("s", "t", "direct", 1)).unwrap();
1940 graph.add_conversion(edge("a", "t", "finish", 5)).unwrap();
1941 let policy = Policy {
1942 max_expansions: 0,
1943 ..Policy::default()
1944 };
1945 assert_eq!(graph.routes("s", "t", &policy), Err(PlanError::SearchLimit));
1946 let policy = Policy {
1947 max_expansions: 2,
1948 ..policy
1949 };
1950 let plans = graph.routes("s", "t", &policy).unwrap();
1951 assert_eq!(plans.len(), 1);
1952 assert_eq!(plans[0].cost, 1);
1953 let policy = Policy {
1954 max_routes: 0,
1955 ..policy
1956 };
1957 assert!(matches!(
1958 graph.routes("s", "t", &policy),
1959 Err(PlanError::Invalid(_))
1960 ));
1961 }
1962
1963 #[test]
1964 fn target_heuristic_avoids_combinatorial_dead_ends() {
1965 let mut graph = graph(&["s", "t"]);
1966 for index in 0..10 {
1967 graph
1968 .add_format(Format::new(
1969 &format!("dead{index}"),
1970 "Dead",
1971 MediaKind::Data,
1972 ))
1973 .unwrap();
1974 }
1975 for from in 0..10 {
1976 graph
1977 .add_conversion(edge("s", &format!("dead{from}"), "dead", 1))
1978 .unwrap();
1979 for to in 0..10 {
1980 graph
1981 .add_conversion(edge(
1982 &format!("dead{from}"),
1983 &format!("dead{to}"),
1984 "dead",
1985 1,
1986 ))
1987 .unwrap();
1988 }
1989 }
1990 graph.add_conversion(edge("s", "t", "direct", 100)).unwrap();
1991 let policy = Policy {
1992 max_expansions: 11,
1993 ..Policy::default()
1994 };
1995 let plans = graph.routes("s", "t", &policy).unwrap();
1996 assert_eq!(plans.len(), 1);
1997 assert_eq!(plans[0].cost, 100);
1998 }
1999
2000 #[test]
2001 fn ties_stop_at_requested_routes_without_expanding_all_prefixes() {
2002 let mut graph = graph(&["s", "a", "t"]);
2003 graph.add_conversion(edge("s", "a", "indirect", 1)).unwrap();
2004 graph.add_conversion(edge("s", "t", "direct", 2)).unwrap();
2005 graph.add_conversion(edge("a", "t", "finish", 1)).unwrap();
2006 let policy = Policy {
2007 max_routes: 1,
2008 max_expansions: 2,
2009 ..Policy::default()
2010 };
2011 let plans = graph.routes("s", "t", &policy).unwrap();
2012 assert_eq!(plans.len(), 1);
2013 assert_eq!(plans[0].steps.len(), 1);
2014 }
2015
2016 #[test]
2017 fn allow_lossy_false_prunes_lossy_edges_but_keeps_lossless_bridges() {
2018 let mut graph = graph(&["a", "b", "c"]);
2019 graph
2020 .add_conversion(Conversion::new(
2021 "a",
2022 "b",
2023 "encoder",
2024 "recompress",
2025 ConversionKind::Lossy,
2026 1,
2027 ))
2028 .unwrap();
2029 graph
2030 .add_conversion(Conversion::new(
2031 "b",
2032 "c",
2033 "encoder",
2034 "bridge",
2035 ConversionKind::Bridge,
2036 1,
2037 ))
2038 .unwrap();
2039 graph
2040 .add_conversion(Conversion::new(
2041 "a",
2042 "c",
2043 "encoder",
2044 "extract",
2045 ConversionKind::Extract,
2046 5,
2047 ))
2048 .unwrap();
2049 let strict = Policy {
2050 allow_lossy: false,
2051 ..Policy::default()
2052 };
2053 let mut strict_policy = strict.clone();
2054 strict_policy.allow_bridges = false;
2055 let plans = graph.routes("a", "c", &strict_policy).unwrap();
2056 assert_eq!(plans.len(), 1);
2057 assert_eq!(plans[0].steps.len(), 1);
2058 assert_eq!(plans[0].steps[0].kind, ConversionKind::Extract);
2059 assert!(graph.routes("a", "c", &strict).unwrap().iter().all(|plan| {
2060 plan.steps
2061 .iter()
2062 .all(|step| step.kind != ConversionKind::Lossy)
2063 }));
2064 assert!(Policy::default().allows(ConversionKind::Lossy));
2065 assert!(!strict.allows(ConversionKind::Lossy));
2066 assert!(strict.allows(ConversionKind::Lossless));
2067 }
2068
2069 #[test]
2070 fn mime_types_resolve_after_ids_and_extensions() {
2071 let mut graph = Graph::new();
2072 graph
2073 .add_format(
2074 Format::new("jpeg", "JPEG", MediaKind::Image)
2075 .with_extensions(&["jpg", "jpeg"])
2076 .with_mime(&["IMAGE/JPEG ", "image/jpg"]),
2077 )
2078 .unwrap();
2079 assert_eq!(graph.resolve("image/jpeg").unwrap().id, "jpeg");
2080 assert_eq!(graph.resolve(" Image/JPG\n").unwrap().id, "jpeg");
2081 assert_eq!(graph.resolve("jpeg").unwrap().id, "jpeg");
2082 assert_eq!(graph.resolve("jpg").unwrap().id, "jpeg");
2083 assert_eq!(
2084 graph.format("jpeg").unwrap().mime_types,
2085 ["image/jpeg", "image/jpg"]
2086 );
2087 assert!(
2088 graph
2089 .add_format(Format::new("x", "X", MediaKind::Image).with_mime(&[""]))
2090 .is_err()
2091 );
2092 assert!(graph.format("x").is_none());
2093 assert!(graph.resolve("application/zip").is_none());
2095 }
2096
2097 #[test]
2098 fn plans_compute_cost_and_edges_carry_notes() {
2099 let plan = Plan::new(vec![]);
2100 assert_eq!(
2101 plan,
2102 Plan {
2103 steps: vec![],
2104 cost: 0
2105 }
2106 );
2107 let base = edge("a", "b", "backend", 3);
2108 assert!(base.note.is_none());
2109 let noted = base.clone().with_note("re-encodes: quality loss");
2110 assert_eq!(noted.note.as_deref(), Some("re-encodes: quality loss"));
2111 assert_eq!(noted, base.clone().with_note("re-encodes: quality loss"));
2112 assert_ne!(noted, base);
2113 let plan = Plan::new(vec![noted, edge("b", "c", "backend", 4)]);
2114 assert_eq!(plan.cost, 7);
2115 }
2116
2117 #[test]
2118 fn registration_order_does_not_change_route_order() {
2119 let mut forward = graph(&["s", "a", "b", "t"]);
2120 let mut backward = graph(&["t", "b", "a", "s"]);
2121 let edges = [
2122 edge("s", "a", "z", 1),
2123 edge("s", "a", "a", 1),
2124 edge("s", "b", "b", 1),
2125 edge("a", "t", "end", 1),
2126 edge("b", "t", "end", 1),
2127 edge("s", "t", "direct", 2),
2128 edge("a", "b", "cycle", 1),
2129 edge("b", "a", "cycle", 1),
2130 Conversion::new("*", "t", "zip", "pack", ConversionKind::Package, 2),
2131 ];
2132 for edge in &edges {
2133 forward.add_conversion(edge.clone()).unwrap();
2134 }
2135 for edge in edges.iter().rev() {
2136 backward.add_conversion(edge.clone()).unwrap();
2137 }
2138 let policy = Policy {
2139 allow_packaging: true,
2140 max_routes: 64,
2141 ..Policy::default()
2142 };
2143 assert_eq!(
2144 forward.routes("s", "t", &policy),
2145 backward.routes("s", "t", &policy)
2146 );
2147 }
2148
2149 #[test]
2150 fn route_and_step_limits_have_hard_caps() {
2151 let mut graph = graph(&["s", "t"]);
2152 for index in 0..70 {
2153 graph
2154 .add_conversion(edge("s", "t", &format!("backend{index:02}"), 1))
2155 .unwrap();
2156 }
2157 let policy = Policy {
2158 max_routes: usize::MAX,
2159 max_steps: usize::MAX,
2160 max_expansions: usize::MAX,
2161 ..Policy::default()
2162 };
2163 assert_eq!(graph.routes("s", "t", &policy).unwrap().len(), 64);
2164 for index in 0..66 {
2165 graph
2166 .add_format(Format::new(&format!("f{index}"), "Format", MediaKind::Data))
2167 .unwrap();
2168 if index > 0 {
2169 graph
2170 .add_conversion(edge(
2171 &format!("f{}", index - 1),
2172 &format!("f{index}"),
2173 "chain",
2174 1,
2175 ))
2176 .unwrap();
2177 }
2178 }
2179 assert_eq!(
2180 graph.routes("f0", "f64", &policy).unwrap()[0].steps.len(),
2181 64
2182 );
2183 assert!(matches!(
2184 graph.routes("f0", "f65", &policy),
2185 Err(PlanError::NoRoute { .. })
2186 ));
2187 }
2188
2189 #[test]
2190 fn reencode_requests_same_format_routes_through_intermediates() {
2191 let mut graph = graph(&["t", "a", "b"]);
2192 graph.add_conversion(edge("t", "a", "decode", 1)).unwrap();
2193 graph.add_conversion(edge("a", "t", "encode", 2)).unwrap();
2194 graph.add_conversion(edge("t", "b", "other", 1)).unwrap();
2195 graph.add_conversion(edge("b", "t", "back", 1)).unwrap();
2196 let identity = graph.routes("t", "t", &Policy::default()).unwrap();
2197 assert_eq!(
2198 identity,
2199 vec![Plan {
2200 steps: vec![],
2201 cost: 0
2202 }]
2203 );
2204 let policy = Policy {
2205 reencode_same_format: true,
2206 ..Policy::default()
2207 };
2208 let plans = graph.routes("t", "t", &policy).unwrap();
2209 assert_eq!(
2210 plans.iter().map(|plan| plan.cost).collect::<Vec<_>>(),
2211 [2, 3]
2212 );
2213 assert_eq!(plans[0].steps.len(), 2);
2214 assert_eq!(plans[0].steps[0].from, "t");
2215 assert_eq!(plans[0].steps[1].to, "t");
2216 for plan in &plans {
2217 let intermediates: Vec<&str> = plan.steps.iter().map(|s| s.to.as_str()).collect();
2220 let unique: BTreeSet<&str> = intermediates.iter().copied().collect();
2221 assert_eq!(
2222 intermediates.len(),
2223 unique.len(),
2224 "{plan:?} revisited a format"
2225 );
2226 }
2227 }
2228
2229 #[test]
2230 fn reencode_reports_no_route_when_only_the_identity_copy_exists() {
2231 let graph = graph(&["t"]);
2232 let policy = Policy {
2233 reencode_same_format: true,
2234 ..Policy::default()
2235 };
2236 assert!(matches!(
2237 graph.routes("t", "t", &policy),
2238 Err(PlanError::NoRoute { .. })
2239 ));
2240 }
2241
2242 #[test]
2243 fn reencode_allows_a_single_self_loop_edge() {
2244 let mut graph = graph(&["t"]);
2245 graph
2246 .add_conversion(edge("t", "t", "self-edge", 5))
2247 .unwrap();
2248 let policy = Policy {
2249 reencode_same_format: true,
2250 ..Policy::default()
2251 };
2252 let plans = graph.routes("t", "t", &policy).unwrap();
2253 assert_eq!(plans.len(), 1);
2254 assert_eq!(plans[0].steps[0].backend, "self-edge");
2255 assert_eq!(plans[0].cost, 5);
2256 }
2257
2258 #[test]
2259 fn retention_policy_prunes_edges_lacking_declared_properties() {
2260 let mut graph = graph(&["a", "b", "c"]);
2261 graph
2262 .add_conversion(
2263 Conversion::new("a", "b", "flat", "convert", ConversionKind::Lossy, 1)
2264 .with_retained(&["pixels"]),
2265 )
2266 .unwrap();
2267 graph
2268 .add_conversion(
2269 Conversion::new("a", "c", "faithful", "convert", ConversionKind::Lossless, 4)
2270 .with_retained(&["alpha", "Pixels"]),
2271 )
2272 .unwrap();
2273 graph
2274 .add_conversion(
2275 Conversion::new(
2276 "b",
2277 "c",
2278 "faithful",
2279 "roundtrip",
2280 ConversionKind::Lossless,
2281 1,
2282 )
2283 .with_retained(&["alpha"]),
2284 )
2285 .unwrap();
2286 let open = graph.routes("a", "c", &Policy::default()).unwrap();
2287 assert_eq!(open.len(), 2, "both routes exist without retention gates");
2288 let alpha = Policy {
2289 retain: vec![" ALPHA ".into()],
2290 ..Policy::default()
2291 };
2292 let plans = graph.routes("a", "c", &alpha).unwrap();
2293 assert_eq!(plans.len(), 1);
2294 assert_eq!(plans[0].cost, 4);
2295 assert!(
2296 plans[0]
2297 .steps
2298 .iter()
2299 .all(|step| step.retained.contains(&"alpha".into()))
2300 );
2301 let exact = Conversion::new("a", "b", "x", "op", ConversionKind::Lossless, 1)
2302 .with_retained(&["alpha"]);
2303 assert!(exact.retains_all(&["Alpha ", ""]));
2304 assert!(!exact.retains_all(&["bytes"]));
2305 assert!(!exact.retains_all(&["alpha", "bytes"]));
2306 }
2307
2308 #[test]
2309 fn backend_search_gate_reaches_routes_a_post_filter_would_truncate_away() {
2310 let mut graph = graph(&["a", "b"]);
2311 for index in 0..8 {
2312 graph
2313 .add_conversion(edge("a", "b", &format!("noise{index}"), 1))
2314 .unwrap();
2315 }
2316 graph.add_conversion(edge("a", "b", "wanted", 9)).unwrap();
2317 let plans = graph.routes("a", "b", &Policy::default()).unwrap();
2318 assert_eq!(plans.len(), 8);
2320 assert!(plans.iter().all(|plan| plan.steps[0].backend != "wanted"));
2321 let policy = Policy {
2322 backends: vec!["wanted".into()],
2323 ..Policy::default()
2324 };
2325 assert!(policy.permits_backend("wanted"));
2326 assert!(!policy.permits_backend("noise0"));
2327 assert!(Policy::default().permits_backend("anything"));
2328 let plans = graph.routes("a", "b", &policy).unwrap();
2329 assert_eq!(plans.len(), 1);
2330 assert_eq!(plans[0].steps[0].backend, "wanted");
2331 assert_eq!(plans[0].cost, 9);
2332 }
2333
2334 #[test]
2335 fn creative_edges_are_opt_in_and_never_disguise_a_no_route() {
2336 let mut graph = graph(&["wav", "png"]);
2337 graph
2338 .add_conversion(
2339 Conversion::new(
2340 "wav",
2341 "png",
2342 "media",
2343 "spectrogram",
2344 ConversionKind::Bridge,
2345 40,
2346 )
2347 .creative(),
2348 )
2349 .unwrap();
2350 assert!(matches!(
2351 graph.routes("wav", "png", &Policy::default()),
2352 Err(PlanError::NoRoute { .. })
2353 ));
2354 let policy = Policy {
2355 allow_creative: true,
2356 ..Policy::default()
2357 };
2358 let plans = graph.routes("wav", "png", &policy).unwrap();
2359 assert_eq!(plans[0].steps[0].category, ConversionCategory::Creative);
2360 assert_eq!(plans[0].cost, 40);
2361 let plain = edge("a", "b", "backend", 1);
2362 assert_eq!(plain.category, ConversionCategory::Standard);
2363 assert_eq!(
2364 plain.clone().creative().category,
2365 ConversionCategory::Creative
2366 );
2367 assert_eq!(
2368 plain.with_category(ConversionCategory::Creative).category,
2369 ConversionCategory::Creative
2370 );
2371 assert_eq!(
2373 graph
2374 .routes("wav", "wav", &Policy::default())
2375 .unwrap()
2376 .len(),
2377 1
2378 );
2379 }
2380
2381 #[test]
2382 fn media_kind_displays_lowercase_names() {
2383 let cases = [
2384 (MediaKind::Binary, "binary"),
2385 (MediaKind::Text, "text"),
2386 (MediaKind::Data, "data"),
2387 (MediaKind::Image, "image"),
2388 (MediaKind::Audio, "audio"),
2389 (MediaKind::Video, "video"),
2390 (MediaKind::Document, "document"),
2391 (MediaKind::Archive, "archive"),
2392 (MediaKind::Model, "model"),
2393 (MediaKind::Font, "font"),
2394 ];
2395 for (kind, label) in cases {
2396 assert_eq!(kind.to_string(), label);
2397 }
2398 }
2399
2400 #[test]
2401 fn decode_only_formats_gate_targets_but_not_sources() {
2402 let mut graph = Graph::new();
2403 graph
2404 .add_format(Format::new("raw", "Raw", MediaKind::Image).decode_only())
2405 .unwrap();
2406 assert!(graph.format("raw").unwrap().decode_only);
2407 graph
2408 .add_format(Format::new("png", "PNG", MediaKind::Image))
2409 .unwrap();
2410 graph
2411 .add_conversion(edge("raw", "png", "decode", 1))
2412 .unwrap();
2413 graph
2414 .add_conversion(edge("png", "raw", "encode", 1))
2415 .unwrap();
2416 assert!(matches!(
2417 graph.routes("png", "raw", &Policy::default()),
2418 Err(PlanError::NoRoute { .. })
2419 ));
2420 assert_eq!(
2421 graph.routes("raw", "png", &Policy::default()).unwrap()[0].cost,
2422 1
2423 );
2424 assert_eq!(
2425 graph.routes("raw", "raw", &Policy::default()).unwrap(),
2426 [Plan {
2427 steps: vec![],
2428 cost: 0
2429 }]
2430 );
2431 let open = Policy {
2432 allow_decode_only: true,
2433 ..Policy::default()
2434 };
2435 assert_eq!(graph.routes("png", "raw", &open).unwrap()[0].cost, 1);
2436 }
2437
2438 #[test]
2439 fn external_gates_compose_with_kind_gates() {
2440 for kind in [
2441 ConversionKind::Lossy,
2442 ConversionKind::Bridge,
2443 ConversionKind::Reinterpret,
2444 ConversionKind::Package,
2445 ] {
2446 let conversion = Conversion::new("a", "b", "tool", "run", kind, 1).requires_external();
2447 assert!(conversion.external);
2448 let base = Policy::default();
2449 assert!(!base.allows_edge(&conversion));
2450 let external = Policy {
2451 allow_external: true,
2452 allow_bridges: true,
2453 ..Policy::default()
2454 };
2455 let mut lossless = conversion.clone();
2456 lossless.kind = ConversionKind::Lossless;
2457 assert!(external.allows_edge(&lossless));
2458 let expected = matches!(kind, ConversionKind::Lossy | ConversionKind::Bridge);
2459 assert_eq!(external.allows_edge(&conversion), expected, "{kind:?}");
2460 let full = Policy {
2461 allow_external_packaging: true,
2462 allow_reinterpret: true,
2463 allow_packaging: true,
2464 ..external
2465 };
2466 assert!(full.allows_edge(&conversion));
2467 if matches!(kind, ConversionKind::Reinterpret | ConversionKind::Package) {
2468 let external_kind_only = Policy {
2469 allow_external: true,
2470 allow_reinterpret: true,
2471 allow_packaging: true,
2472 ..Policy::default()
2473 };
2474 assert!(
2475 !external_kind_only.allows_edge(&conversion),
2476 "{kind:?} external edge needs allow_external_packaging"
2477 );
2478 }
2479 }
2480 let extract = Conversion::new("a", "b", "tool", "run", ConversionKind::Extract, 1)
2481 .requires_external();
2482 assert!(!Policy::default().allows_edge(&extract));
2483 assert!(
2484 Policy {
2485 allow_external: true,
2486 ..Policy::default()
2487 }
2488 .allows_edge(&extract)
2489 );
2490 }
2491
2492 #[test]
2493 fn conversion_builder_defaults_and_chains() {
2494 let plain = Conversion::new("a", "b", "backend", "op", ConversionKind::Lossy, 7);
2495 assert!(!plain.external);
2496 assert_eq!(plain.cost, 7);
2497 assert_eq!(plain.from, "a");
2498 assert_eq!(plain.to, "b");
2499 assert_eq!(plain.backend, "backend");
2500 assert_eq!(plain.operation, "op");
2501 let marked = plain.clone().requires_external();
2502 assert!(marked.external);
2503 assert!(!plain.external);
2504
2505 let format = Format::new("img", "Image", MediaKind::Image)
2506 .with_extensions(&["Z", ".y", "y", " x "])
2507 .decode_only();
2508 assert!(format.decode_only);
2509 assert_eq!(format.extensions, ["x", "y", "z"]);
2510 let plain_format = Format::new("other", "Other", MediaKind::Text);
2511 assert!(!plain_format.decode_only);
2512 assert!(plain_format.extensions.is_empty());
2513 }
2514
2515 #[test]
2516 fn astar_matches_exhaustive_loopless_enumeration() {
2517 fn enumerate(
2518 graph: &Graph,
2519 current: &str,
2520 visited: &mut Vec<String>,
2521 steps: &mut Vec<Conversion>,
2522 plans: &mut Vec<Plan>,
2523 policy: &Policy,
2524 ) {
2525 if current == "t" {
2526 plans.push(Plan {
2527 steps: steps.clone(),
2528 cost: steps.iter().map(|step| u64::from(step.cost)).sum(),
2529 });
2530 return;
2531 }
2532 if steps.len() == policy.max_steps {
2533 return;
2534 }
2535 for edge in graph
2536 .conversions
2537 .get(current)
2538 .into_iter()
2539 .flatten()
2540 .chain(graph.conversions.get("*").into_iter().flatten())
2541 {
2542 if policy.allows_edge(edge) && !visited.contains(&edge.to) {
2543 visited.push(edge.to.clone());
2544 let mut step = edge.clone();
2545 step.from = current.to_owned();
2546 steps.push(step);
2547 enumerate(graph, &edge.to, visited, steps, plans, policy);
2548 steps.pop();
2549 visited.pop();
2550 }
2551 }
2552 }
2553 let ids = ["s", "a", "b", "c", "t"];
2554 for seed in 0..24 {
2555 let policy = Policy {
2556 allow_packaging: seed % 2 == 0,
2557 max_steps: seed % 5 + 1,
2558 max_routes: 64,
2559 ..Policy::default()
2560 };
2561 let mut graph = graph(&ids);
2562 for (i, from) in ids.iter().enumerate() {
2563 for (j, to) in ids.iter().enumerate() {
2564 let value = seed * 31 + i * 17 + j * 7;
2565 if value % 4 != 0 {
2566 graph
2567 .add_conversion(edge(from, to, "backend", (value % 11 + 1) as u32))
2568 .unwrap();
2569 }
2570 }
2571 }
2572 for target in ["a", "t"] {
2573 graph
2574 .add_conversion(Conversion::new(
2575 "*",
2576 target,
2577 "wildcard",
2578 "pack",
2579 ConversionKind::Package,
2580 (seed % 3 + 1) as u32,
2581 ))
2582 .unwrap();
2583 }
2584 let mut expected = vec![];
2585 enumerate(
2586 &graph,
2587 "s",
2588 &mut vec!["s".into()],
2589 &mut vec![],
2590 &mut expected,
2591 &policy,
2592 );
2593 if expected.is_empty() {
2594 assert!(matches!(
2595 graph.routes("s", "t", &policy),
2596 Err(PlanError::NoRoute { .. })
2597 ));
2598 continue;
2599 }
2600 let mut actual = graph.routes("s", "t", &policy).unwrap();
2601 assert!(actual.windows(2).all(|pair| pair[0].cost <= pair[1].cost));
2602 expected.sort_by(|a, b| (a.cost, &a.steps).cmp(&(b.cost, &b.steps)));
2603 actual.sort_by(|a, b| (a.cost, &a.steps).cmp(&(b.cost, &b.steps)));
2604 assert_eq!(actual, expected, "seed {seed}");
2605 }
2606 }
2607
2608 #[test]
2609 fn content_kinds_normalize_and_match() {
2610 let raw = ContentKind::with_codec(MediaKind::Audio, " H.264 ");
2611 assert_eq!(raw.codec.as_deref(), Some("h.264"));
2612 assert_eq!(raw, ContentKind::with_codec(MediaKind::Audio, "h.264"));
2613 assert_eq!(raw.to_string(), "audio:h.264");
2614 assert_eq!(ContentKind::new(MediaKind::Video).to_string(), "video");
2615
2616 let loose = ContentKind::new(MediaKind::Audio);
2617 let tight = ContentKind::with_codec(MediaKind::Audio, "aac");
2618 assert!(loose.matches(&tight));
2619 assert!(!tight.matches(&loose));
2620 assert!(!tight.matches(&ContentKind::with_codec(MediaKind::Audio, "opus")));
2621 assert!(!tight.matches(&ContentKind::with_codec(MediaKind::Video, "aac")));
2622
2623 assert_eq!(
2624 ContentKind::parse(" Audio : OPUS ").unwrap(),
2625 ContentKind::with_codec(MediaKind::Audio, "opus")
2626 );
2627 assert_eq!(
2628 "video".parse::<ContentKind>().unwrap(),
2629 ContentKind::new(MediaKind::Video)
2630 );
2631 assert!(matches!(
2632 ContentKind::parse("video:bad codec"),
2633 Err(PlanError::Invalid(_))
2634 ));
2635 assert!(matches!(
2636 ContentKind::parse("stream"),
2637 Err(PlanError::Invalid(_))
2638 ));
2639 }
2640
2641 #[test]
2642 fn profiles_declare_streams_and_deduplicate() {
2643 let mut profile = ContentProfile::new("mp4")
2644 .with_stream(ContentKind::with_codec(MediaKind::Video, "h264"))
2645 .with_stream(ContentKind::new(MediaKind::Text));
2646 profile.add_stream(
2647 Stream::new(5, ContentKind::new(MediaKind::Video)).with_label("second video track"),
2648 );
2649 assert!(profile.declares(&ContentKind::with_codec(MediaKind::Video, "h264")));
2650 assert!(!profile.declares(&ContentKind::with_codec(MediaKind::Video, "hevc")));
2651 assert!(profile.declares_all(&[
2652 ContentKind::new(MediaKind::Video),
2653 ContentKind::new(MediaKind::Text),
2654 ]));
2655 profile.streams[0].content = ContentKind::new(MediaKind::Audio);
2656 profile.deduplicate();
2657 profile.deduplicate();
2658 assert_eq!(
2659 profile.streams.iter().map(|s| s.index).collect::<Vec<_>>(),
2660 vec![0, 1, 2]
2661 );
2662 assert_eq!(profile.stream_kinds().len(), 3);
2663 }
2664
2665 #[test]
2666 fn registration_validates_content_fields() {
2667 let mut graph = Graph::new();
2668 graph
2669 .add_format(Format::new("mp4", "MP4", MediaKind::Video).with_payloads(&[
2670 ContentKind::new(MediaKind::Video),
2671 ContentKind::new(MediaKind::Video),
2672 ContentKind::with_codec(MediaKind::Audio, " AAC "),
2673 ]))
2674 .unwrap();
2675 let mp4 = graph.format("mp4").unwrap();
2676 assert_eq!(mp4.payloads.len(), 2);
2677 assert_eq!(mp4.payloads[1].codec.as_deref(), Some("aac"));
2678
2679 assert!(matches!(
2680 graph.add_format(Format::new("gz", "Gzip", MediaKind::Archive).in_container(" ")),
2681 Err(PlanError::Invalid(message)) if message == "invalid container name for gz"
2682 ));
2683 graph
2684 .add_format(Format::new("gz", "Gzip", MediaKind::Archive).in_container(" .TAR.GZ "))
2685 .unwrap();
2686 assert_eq!(
2687 graph.format("gz").unwrap().container.as_deref(),
2688 Some("tar.gz")
2689 );
2690 assert!(matches!(
2691 graph
2692 .add_format(Format::new("bz", "Bzip", MediaKind::Archive).in_container("bad name")),
2693 Err(PlanError::Invalid(_))
2694 ));
2695
2696 graph
2697 .add_format(Format::new("wav", "WAV", MediaKind::Audio))
2698 .unwrap();
2699 assert!(matches!(
2700 graph.add_conversion(
2701 edge("mp4", "wav", "ffmpeg", 2)
2702 .requiring(&[ContentKind::with_codec(MediaKind::Audio, "bad codec")])
2703 ),
2704 Err(PlanError::Invalid(_))
2705 ));
2706 graph
2707 .add_conversion(
2708 edge("mp4", "wav", "ffmpeg", 2)
2709 .requiring(&[ContentKind::new(MediaKind::Audio)])
2710 .producing(&[ContentKind::with_codec(MediaKind::Audio, "pcm")]),
2711 )
2712 .unwrap();
2713 }
2714
2715 #[test]
2716 fn profile_gate_selects_source_edges() {
2717 let mut graph = Graph::new();
2718 graph
2719 .add_format(Format::new("mp4", "MP4", MediaKind::Video).with_payloads(&[
2720 ContentKind::new(MediaKind::Video),
2721 ContentKind::new(MediaKind::Audio),
2722 ]))
2723 .unwrap();
2724 graph
2725 .add_format(Format::new("srt", "SubRip", MediaKind::Text))
2726 .unwrap();
2727 graph
2728 .add_format(Format::new("wav", "WAV", MediaKind::Audio))
2729 .unwrap();
2730 graph
2731 .add_conversion(
2732 edge("mp4", "srt", "extract", 1).requiring(&[ContentKind::new(MediaKind::Text)]),
2733 )
2734 .unwrap();
2735 graph
2736 .add_conversion(
2737 edge("mp4", "wav", "ffmpeg", 2).requiring(&[ContentKind::new(MediaKind::Audio)]),
2738 )
2739 .unwrap();
2740 let policy = Policy::default();
2741
2742 assert_eq!(graph.routes("mp4", "wav", &policy).unwrap().len(), 1);
2744
2745 let silent = ContentProfile::new("mp4").with_stream(ContentKind::new(MediaKind::Video));
2747 assert!(matches!(
2748 graph.routes_with_profile("mp4", "wav", &policy, Some(&silent)),
2749 Err(PlanError::NoRoute { .. })
2750 ));
2751 let talking = ContentProfile::new("mp4")
2752 .with_stream(ContentKind::new(MediaKind::Video))
2753 .with_stream(ContentKind::new(MediaKind::Audio));
2754 assert_eq!(
2755 graph
2756 .routes_with_profile("mp4", "wav", &policy, Some(&talking))
2757 .unwrap()
2758 .len(),
2759 1
2760 );
2761
2762 let strict = Policy {
2764 require_content: true,
2765 ..Policy::default()
2766 };
2767 assert!(matches!(
2768 graph.routes_with_profile("mp4", "wav", &strict, None),
2769 Err(PlanError::NoRoute { .. })
2770 ));
2771 assert_eq!(
2772 graph
2773 .routes_with_profile("mp4", "wav", &strict, Some(&talking))
2774 .unwrap()
2775 .len(),
2776 1
2777 );
2778 }
2779
2780 #[test]
2781 fn required_content_gates_the_target() {
2782 let mut graph = Graph::new();
2783 graph
2784 .add_format(
2785 Format::new("wav", "WAV", MediaKind::Audio)
2786 .with_payloads(&[ContentKind::new(MediaKind::Audio)]),
2787 )
2788 .unwrap();
2789 graph
2790 .add_format(Format::new("mp4", "MP4", MediaKind::Video).with_payloads(&[
2791 ContentKind::new(MediaKind::Video),
2792 ContentKind::new(MediaKind::Audio),
2793 ]))
2794 .unwrap();
2795 graph
2796 .add_format(
2797 Format::new("gif", "GIF", MediaKind::Image)
2798 .with_payloads(&[ContentKind::new(MediaKind::Image)]),
2799 )
2800 .unwrap();
2801 graph
2802 .add_conversion(
2803 edge("wav", "mp4", "ffmpeg", 2)
2804 .requiring(&[ContentKind::new(MediaKind::Audio)])
2805 .producing(&[ContentKind::new(MediaKind::Audio)]),
2806 )
2807 .unwrap();
2808 graph
2809 .add_conversion(
2810 edge("wav", "gif", "viz", 1).producing(&[ContentKind::new(MediaKind::Image)]),
2811 )
2812 .unwrap();
2813
2814 let want_audio = Policy {
2815 require: vec![ContentKind::new(MediaKind::Audio)],
2816 ..Policy::default()
2817 };
2818 let routes = graph.routes("wav", "mp4", &want_audio).unwrap();
2819 assert_eq!(routes[0].steps[0].to, "mp4");
2820 assert!(matches!(
2821 graph.routes("wav", "gif", &want_audio),
2822 Err(PlanError::NoRoute { .. })
2823 ));
2824
2825 let verified = Policy {
2828 require: vec![ContentKind::with_codec(MediaKind::Audio, "aac")],
2829 ..Policy::default()
2830 };
2831 assert!(matches!(
2832 graph.routes("wav", "mp4", &verified),
2833 Err(PlanError::NoRoute { .. })
2834 ));
2835 graph
2836 .add_conversion(
2837 edge("wav", "mp4", "ffmpeg-hq", 3)
2838 .requiring(&[ContentKind::new(MediaKind::Audio)])
2839 .producing(&[ContentKind::with_codec(MediaKind::Audio, "aac")]),
2840 )
2841 .unwrap();
2842 let routes = graph.routes("wav", "mp4", &verified).unwrap();
2843 assert_eq!(routes[0].steps[0].backend, "ffmpeg-hq");
2844
2845 let same = graph.routes("mp4", "mp4", &want_audio);
2847 assert_eq!(same.unwrap()[0].steps.len(), 0);
2848 let need_h264 = Policy {
2849 require: vec![ContentKind::with_codec(MediaKind::Video, "h264")],
2850 ..Policy::default()
2851 };
2852 assert!(
2853 !graph
2854 .format("mp4")
2855 .unwrap()
2856 .payloads
2857 .iter()
2858 .any(|payload| payload.codec.is_some())
2859 );
2860 assert!(matches!(
2861 graph.routes_with_profile("mp4", "mp4", &need_h264, None),
2862 Err(PlanError::NoRoute { .. })
2863 ));
2864 let tagged = ContentProfile::new("mp4")
2865 .with_stream(ContentKind::with_codec(MediaKind::Video, "h264"));
2866 assert!(
2867 graph
2868 .routes_with_profile("mp4", "mp4", &need_h264, Some(&tagged))
2869 .unwrap()
2870 .iter()
2871 .all(|plan| plan.steps.is_empty())
2872 );
2873 }
2874
2875 #[test]
2876 fn policy_normalization_cleans_required_content() {
2877 let policy = Policy {
2878 require: vec![
2879 ContentKind::new(MediaKind::Video),
2880 ContentKind::with_codec(MediaKind::Video, " H264 "),
2881 ContentKind::new(MediaKind::Video),
2882 ContentKind::with_codec(MediaKind::Audio, " "),
2883 ],
2884 ..Policy::default()
2885 };
2886 let normalized = policy.normalized().unwrap();
2887 assert_eq!(
2888 normalized.require,
2889 vec![
2890 ContentKind::new(MediaKind::Audio),
2891 ContentKind::new(MediaKind::Video),
2892 ContentKind::with_codec(MediaKind::Video, "h264"),
2893 ]
2894 );
2895 let broken = Policy {
2896 require: vec![ContentKind::with_codec(MediaKind::Video, "bad codec")],
2897 ..Policy::default()
2898 };
2899 assert!(matches!(
2900 graph(&["a"]).routes("a", "a", &broken),
2901 Err(PlanError::Invalid(_))
2902 ));
2903 }
2904}