Skip to main content

convert_rs_core/
lib.rs

1//! Pure, deterministic format registration and policy-controlled route planning.
2//!
3//! Routes are loopless and returned in nondecreasing cost order. Equal-cost
4//! ordering is deterministic for a given graph, independent of edge registration
5//! order. Search uses
6//! reverse shortest-path distances to avoid exploring target-unreachable paths.
7//!
8//! This crate only describes formats and routes. It does not inspect files,
9//! execute adapters, validate codec support, or guarantee conversion fidelity.
10//! Conversion classifications and costs are supplied by the graph's registrant.
11//!
12//! # Plan a conversion
13//!
14//! ```rust
15//! use convert_rs_core::{Conversion, ConversionKind, Format, Graph, MediaKind, Policy};
16//!
17//! let mut graph = Graph::new();
18//! graph.add_format(Format::new("note", "Note", MediaKind::Text)
19//!     .with_extensions(&["txt"]))?;
20//! graph.add_format(Format::new("speech", "Speech", MediaKind::Audio))?;
21//! graph.add_conversion(Conversion::new(
22//!     "note", "speech", "reader", "speak", ConversionKind::Bridge, 3,
23//! ))?;
24//! let routes = graph.routes(".TXT", "speech", &Policy::default())?;
25//! assert_eq!(routes[0].cost, 3);
26//! assert_eq!(routes[0].steps[0].operation, "speak");
27//! let strict = Policy { allow_bridges: false, ..Policy::default() };
28//! assert!(graph.routes("note", "speech", &strict).is_err());
29//! # Ok::<(), convert_rs_core::PlanError>(())
30//! ```
31#![warn(missing_docs)]
32
33use std::cmp::Reverse;
34use std::collections::{BTreeMap, BinaryHeap};
35use std::fmt;
36use std::rc::Rc;
37
38/// A format's media category. Categories do not restrict graph connectivity.
39///
40/// Its [`fmt::Display`] representation is the lowercase category name.
41#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
42pub enum MediaKind {
43    /// Unstructured bytes without a more specific category.
44    Binary,
45    /// Human-readable text.
46    Text,
47    /// Structured or tabular data.
48    Data,
49    /// Still images.
50    Image,
51    /// Audio streams.
52    Audio,
53    /// Video streams.
54    Video,
55    /// Documents intended for reading or printing.
56    Document,
57    /// Containers of files or compressed content.
58    Archive,
59    /// Model data, such as three-dimensional geometry.
60    Model,
61    /// Font files.
62    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/// A type of content carried inside or represented by a file.
83///
84/// A [`Format`] names the file representation; a content kind names the streams
85/// the planner can require or match inside it. The optional codec tag
86/// (`h264`, `aac`, `opus`, ...) narrows a category to a specific encoding.
87/// Codecs are normalized to trimmed lowercase at construction.
88///
89/// Equality is exact. Requirement matching uses
90/// [`ContentKind::matches`]: an untagged requirement matches any stream of its
91/// category, while a tagged requirement matches only the same codec tag.
92#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
93pub struct ContentKind {
94    /// Media category of the stream.
95    pub kind: MediaKind,
96    /// Lowercase codec tag, or `None` when no codec is claimed or determined.
97    pub codec: Option<String>,
98}
99
100impl ContentKind {
101    /// Construct an untagged requirement for a media category.
102    #[must_use]
103    pub fn new(kind: MediaKind) -> Self {
104        Self { kind, codec: None }
105    }
106
107    /// Construct a requirement tagged with a codec; see [`Self::codec`].
108    #[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    /// Parse a content kind from its [`std::fmt::Display`] form, `kind` or
117    /// `kind:codec`. The kind must be a known [`MediaKind`] category name and
118    /// the codec (when present) must satisfy the same character rules as a
119    /// format ID after trimming and lowercasing.
120    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    /// Whether an observed stream satisfies this requirement.
149    ///
150    /// The categories must be equal. An untagged requirement matches any
151    /// observed stream in its category; a tagged requirement matches only a
152    /// stream with the same codec tag.
153    #[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/// One observed or declared stream inside a container.
181#[derive(Clone, Debug, PartialEq, Eq)]
182pub struct Stream {
183    /// Stream position within the file, as reported by the inspecting adapter.
184    pub index: usize,
185    /// Content category and codec tag of this stream.
186    pub content: ContentKind,
187    /// Adapter-supplied human-readable detail, such as dimensions or bitrate.
188    pub label: Option<String>,
189}
190
191impl Stream {
192    /// Construct a stream at `index` carrying `content`, without a label.
193    #[must_use]
194    pub fn new(index: usize, content: ContentKind) -> Self {
195        Self {
196            index,
197            content,
198            label: None,
199        }
200    }
201
202    /// Attach a human-readable detail string; see [`Self::label`].
203    #[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/// The content streams a specific file or format representation carries.
211///
212/// A profile built by an engine inspection describes observed streams and keeps
213/// [`Self::format`] as the canonical format ID that was inspected. A profile
214/// assembled from declarations lists every kind the format advertises. The
215/// planner filters edges against profiles supplied through
216/// [`Graph::routes_with_profile`]; it never inspects files itself.
217#[derive(Clone, Debug, Default, PartialEq, Eq)]
218#[non_exhaustive]
219pub struct ContentProfile {
220    /// Canonical format ID this profile describes; empty when unset.
221    pub format: String,
222    /// Streams in adapter-reported order.
223    pub streams: Vec<Stream>,
224}
225
226impl ContentProfile {
227    /// Construct an empty profile for a canonical format ID.
228    #[must_use]
229    pub fn new(format: &str) -> Self {
230        Self {
231            format: format.to_owned(),
232            streams: Vec::new(),
233        }
234    }
235
236    /// Append a stream carrying `content` at the next free index.
237    #[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    /// Append a fully described stream, keeping its own index.
244    pub fn add_stream(&mut self, stream: Stream) -> &mut Self {
245        self.streams.push(stream);
246        self
247    }
248
249    /// Whether any stream satisfies `want` through [`ContentKind::matches`].
250    #[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    /// Whether every requirement in `wants` is satisfied by some stream.
258    #[must_use]
259    pub fn declares_all(&self, wants: &[ContentKind]) -> bool {
260        wants.iter().all(|want| self.declares(want))
261    }
262
263    /// The distinct content kinds carried by this profile's streams, keeping
264    /// first-occurrence order; used by [`Graph::routes_with_profile`].
265    #[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    /// Drop streams whose content duplicates an earlier entry, then renumber
277    /// [`Stream::index`] consecutively. Labels of the kept instance win.
278    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/// A registered format and its lookup metadata.
296///
297/// A format ID describes a file representation, not an encoder configuration.
298/// Registering a format does not imply that any conversion to or from it exists.
299#[derive(Clone, Debug, PartialEq, Eq)]
300#[non_exhaustive]
301pub struct Format {
302    /// Stable format identifier used in plans and conversion requests.
303    pub id: String,
304    /// Human-readable format name.
305    pub name: String,
306    /// Extension aliases, normalized and deduplicated during registration.
307    pub extensions: Vec<String>,
308    /// Broad media category.
309    pub media: MediaKind,
310    /// Mark the format as decode-only for routing purposes.
311    ///
312    /// Unless [`Policy::allow_decode_only`] is set, search skips edges targeting
313    /// this format. It may still be a source or an identity target. This flag
314    /// does not itself check an adapter's encoding capabilities.
315    pub decode_only: bool,
316    /// Registered MIME types, normalized to lowercase during registration.
317    ///
318    /// [`Graph::resolve`] matches trimmed, case-folded values containing `/`
319    /// against these types and against the ID. Adapters declare an empty list
320    /// when a format has no registered media type.
321    pub mime_types: Vec<String>,
322    /// Declared content kinds this format can carry, as a capability ceiling.
323    ///
324    /// A plain `png` declares `[image]`; an `mp4` declares `[image:codec,
325    /// audio:codec, ...]`. This describes what the representation is capable of
326    /// holding, not what a specific file holds. Entries deduplicate by exact
327    /// [`ContentKind`] via [`Graph::add_format`]. The planner uses declared
328    /// payloads to qualify edges that require content on a format that has no
329    /// observed profile; see [`Graph::routes_with_profile`] and
330    /// [`Policy::inspect_content`].
331    pub payloads: Vec<ContentKind>,
332    /// Name of the physical container when this format wraps another.
333    ///
334    /// Set by adapters for nested or wrapper representations, such as `mp3`
335    /// inside `m4a` or a compressed stream inside `tar.gz`. `None` (the default)
336    /// marks a top-level format. The planner never interprets this field; it is
337    /// a metadata label surfaced to callers and reports.
338    pub container: Option<String>,
339}
340
341impl Format {
342    /// Construct a format without extensions and with `decode_only` set to false.
343    ///
344    /// This constructor does not validate the ID; [`Graph::add_format`] does.
345    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    /// Set extension aliases, normalizing case, whitespace, and leading dots.
359    ///
360    /// Replaces previous aliases, sorts and deduplicates them. Invalid aliases
361    /// are rejected later by [`Graph::add_format`], not by this method.
362    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    /// Replace registered MIME types, normalizing case and surrounding whitespace.
370    ///
371    /// [`Graph::add_format`] additionally rejects blank entries and types with
372    /// whitespace. Type matching in [`Graph::resolve`] happens during lookup.
373    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    /// Set the decode-only routing flag; see [`Self::decode_only`].
384    #[must_use]
385    pub fn decode_only(mut self) -> Self {
386        self.decode_only = true;
387        self
388    }
389
390    /// Declare the content kinds this representation can carry.
391    ///
392    /// Replaces previous declarations and deduplicates by exact
393    /// [`ContentKind`]; see [`Self::payloads`].
394    #[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    /// Name the physical container wrapping this representation; see
403    /// [`Self::container`].
404    ///
405    /// The name is trimmed, stripped of leading dots, and lowercased; it must
406    /// satisfy the same character rules as a format ID.
407    #[must_use]
408    pub fn in_container(mut self, container: &str) -> Self {
409        self.container = Some(extension(container));
410        self
411    }
412}
413
414/// An adapter-declared description of a conversion's semantics.
415///
416/// These labels drive policy filtering; they are not verified by the planner.
417/// [`Policy::allow_lossy`] gates [`ConversionKind::Lossy`]; the other kinds have
418/// their own gates or default open.
419#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
420pub enum ConversionKind {
421    /// Preserves the content represented by the operation, as declared by its adapter.
422    Lossless,
423    /// May discard quality, structure, or metadata during conversion.
424    Lossy,
425    /// Expresses content in a different semantic representation.
426    Bridge,
427    /// Interprets input bytes as another format, possibly validating them.
428    Reinterpret,
429    /// Packages files without converting their contents.
430    Package,
431    /// Extracts content from an archive or compressed stream.
432    Extract,
433    /// Re-encodes content within the same format representation.
434    ///
435    /// A Reencode step starts and ends on the same format ID: recompression,
436    /// codec change inside a container, or normalization. It is planned only
437    /// when [`Policy::reencode_same_format`] or the engine's reencode request
438    /// opens same-format searching, and it always declares the properties it
439    /// genuinely keeps.
440    Reencode,
441}
442
443/// A registered conversion's role relative to the content's ordinary purpose.
444///
445/// `Standard` covers conventional format work. `Creative` marks operations that
446/// generate a new representation of the content (sonification, spectrograms,
447/// ASCII art) or otherwise express it in a way the input never had. Planners do
448/// not route through `Creative` edges unless [`Policy::allow_creative`] is set,
449/// so an ordinary conversion failure never silently becomes an artistic one.
450#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
451pub enum ConversionCategory {
452    /// Conventional conversion, extraction, packaging, or reinterpretation.
453    Standard,
454    /// Generated or expressive representation of the content.
455    Creative,
456}
457
458/// A directed conversion edge supplied by an adapter.
459///
460/// Backend and operation IDs are opaque to the planner. They do not select
461/// codecs, quality settings, or other encoder parameters in this crate.
462#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
463#[non_exhaustive]
464pub struct Conversion {
465    /// Source format ID, or `*` for a wildcard accepted by [`Graph::add_conversion`].
466    pub from: String,
467    /// Target format ID.
468    pub to: String,
469    /// Adapter name.
470    pub backend: String,
471    /// Adapter operation ID.
472    pub operation: String,
473    /// Semantic conversion classification.
474    pub kind: ConversionKind,
475    /// Positive relative route cost; lower sums are preferred, not measured runtime.
476    pub cost: u32,
477    /// True when executing this step spawns an out-of-process native tool.
478    pub external: bool,
479    /// Adapter-supplied, human-readable cost or fidelity note.
480    ///
481    /// The planner ignores this value. It exists so [`Graph::routes`] consumers
482    /// (and execution reports) can explain what an edge costs or discards.
483    pub note: Option<String>,
484    /// Whether this edge performs conventional work or generates an expressive
485    /// representation; see [`ConversionCategory`] and [`Policy::allow_creative`].
486    pub category: ConversionCategory,
487    /// Content properties this step preserves, as declared by its adapter.
488    ///
489    /// Entries are normalized property names (see [`Conversion::with_retained`]).
490    /// When [`Policy::retain`] names properties, search only walks edges whose
491    /// retained set covers every requested property. This is an adapter claim,
492    /// not a planner-verified guarantee; see the crate-level fidelity notes.
493    pub retained: Vec<String>,
494    /// Content kinds this step needs inside its source representation.
495    ///
496    /// A subtitle extractor from `mp4` declares `[{ video }, { text }]`-style
497    /// requirements; a plain format edge declares none. Under
498    /// [`Graph::routes_with_profile`], an edge leaving the profiled source
499    /// format is usable only when its requirements are satisfied by the
500    /// observed [`ContentProfile`] (or, with no profile, by the source format's
501    /// declared [`Format::payloads`] when it is empty or [`Policy::require_content`]
502    /// is off). Requirements never block edges that leave another format: only
503    /// the profiled source and the final target are checked against content.
504    pub requires: Vec<ContentKind>,
505    /// Content kinds this step places into its target representation.
506    ///
507    /// The target end of a route is matched against [`Policy::require`], using
508    /// the observed profile when one exists or [`Format::payloads`] otherwise.
509    /// The planner never infers produced kinds from other graph structure.
510    pub produces: Vec<ContentKind>,
511}
512
513impl Conversion {
514    /// Construct an edge with [`Self::external`] set to false and no note.
515    ///
516    /// Values are copied without validation. [`Graph::add_conversion`] checks
517    /// endpoint registration, positive cost, and nonblank backend and operation.
518    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    /// Flag this edge as requiring an out-of-process native tool.
543    #[must_use]
544    pub fn requires_external(mut self) -> Self {
545        self.external = true;
546        self
547    }
548
549    /// Attach an adapter-supplied cost or fidelity note; see [`Self::note`].
550    #[must_use]
551    pub fn with_note(mut self, note: &str) -> Self {
552        self.note = Some(note.to_owned());
553        self
554    }
555
556    /// Override the semantic conversion classification given at construction.
557    #[must_use]
558    pub fn with_kind(mut self, kind: ConversionKind) -> Self {
559        self.kind = kind;
560        self
561    }
562
563    /// Override the relative route cost given at construction.
564    #[must_use]
565    pub fn with_cost(mut self, cost: u32) -> Self {
566        self.cost = cost;
567        self
568    }
569
570    /// Mark this edge as a [`ConversionCategory::Creative`] operation.
571    #[must_use]
572    pub fn creative(mut self) -> Self {
573        self.category = ConversionCategory::Creative;
574        self
575    }
576
577    /// Set the conversion category; see [`Self::category`].
578    #[must_use]
579    pub fn with_category(mut self, category: ConversionCategory) -> Self {
580        self.category = category;
581        self
582    }
583
584    /// Declare the content properties this step preserves; see [`Self::retained`].
585    ///
586    /// Values are trimmed and lowercased, then sorted and deduplicated. An edge
587    /// that declares no properties preserves nothing it is asked to retain.
588    #[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    /// Whether this step preserves every property named in `required`.
600    ///
601    /// An empty or whitespace-only entry in `required` is ignored, matching the
602    /// normalization applied to declared properties.
603    #[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    /// Declare the content kinds this step needs in its source; see
613    /// [`Self::requires`].
614    #[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    /// Declare the content kinds this step places into its target; see
628    /// [`Self::produces`].
629    #[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    /// Whether this edge's source content requirements are satisfied.
643    ///
644    /// Returns true when `requirements` is empty. When a profile is supplied,
645    /// each requirement is matched against its streams; otherwise, each is
646    /// matched against `payloads` (the format's declared contents). An edge
647    /// with requirements is never usable from a format that declares nothing
648    /// and has no observed profile.
649    #[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/// Gates and search budgets used by [`Graph::routes`].
664///
665/// Defaults allow lossless, lossy, bridge, and extraction steps. Reinterpretation,
666/// packaging, external tools, external packaging, and decode-only destinations
667/// are disabled. Default search budgets are 6 steps, 8 routes, and 20,000 forward
668/// edge examinations. These are planning limits, not execution resource limits.
669///
670/// Set [`Policy::allow_lossy`] to require lossless-only routes; the default
671/// permits lossy steps. All fields are public; construct with
672/// `Policy { field: value, ..Policy::default() }` and read them directly.
673#[derive(Clone, Debug, PartialEq, Eq)]
674pub struct Policy {
675    /// Permit semantic bridge conversions; enabled by default.
676    pub allow_bridges: bool,
677    /// Permit lossy steps, including quality-reducing re-encoding; enabled by default.
678    ///
679    /// When disabled, [`Graph::routes`] skips [`ConversionKind::Lossy`] edges and
680    /// [`Policy::allows`] rejects forced plans containing lossy steps.
681    /// Bridge, reinterpret, package, and extract steps are gated separately.
682    pub allow_lossy: bool,
683    /// Permit binary reinterpretation routes; disabled by default.
684    pub allow_reinterpret: bool,
685    /// Permit archive packaging routes; disabled by default. Extraction is independent.
686    pub allow_packaging: bool,
687    /// Permit routes from native external tools. Disabled by default because
688    /// out-of-process tools cannot be sandboxed by this library.
689    pub allow_external: bool,
690    /// Additionally permit external Reinterpret and Package steps; disabled by default.
691    ///
692    /// The corresponding kind gate and [`Self::allow_external`] must also be set.
693    pub allow_external_packaging: bool,
694    /// Permit edges targeting formats marked [`Format::decode_only`].
695    ///
696    /// Disabled by default. Source formats and zero-step identity routes are not
697    /// restricted by this flag. Enabling it does not add encoder support.
698    pub allow_decode_only: bool,
699    /// Permit zero-byte inputs; disabled by default.
700    ///
701    /// The graph does not inspect files. Execution components that identify
702    /// input files (such as `convert_rs::Converter::identify`) enforce this
703    /// gate and treat allowed empty inputs as unknown binary content.
704    pub allow_empty_inputs: bool,
705    /// Maximum conversions per route, capped at 64. Zero allows identity only.
706    pub max_steps: usize,
707    /// Maximum routes returned, capped at 64. Zero is invalid.
708    pub max_routes: usize,
709    /// Maximum candidate edges examined during forward search, capped at 100,000.
710    /// Reverse shortest-path preprocessing is linearithmic in graph size and is
711    /// not charged to this limit. Zero permits no forward edge examinations.
712    pub max_expansions: usize,
713    /// Content properties every planned step must preserve, as declared by
714    /// [`Conversion::retained`].
715    ///
716    /// Empty (the default) places no requirement on routes. Each name is
717    /// trimmed and lowercased during [`Graph::routes`]; an edge preserving a
718    /// listed property must declare it exactly. Values are adapter vocabulary
719    /// such as `alpha`, `animation`, `metadata`, or `pixels`; the planner
720    /// imposes no fixed list. Retention gates apply to edges, not to the
721    /// zero-step identity route, which preserves bytes by definition.
722    pub retain: Vec<String>,
723    /// Restrict search to edges whose backend is named in this set.
724    ///
725    /// Empty (the default) permits any backend. When nonempty, edges using other
726    /// backends are pruned during both reverse distance preprocessing and forward
727    /// search, so filtering happens inside the bounded search instead of
728    /// post-filtering a truncated plan set. Names are matched after trimming.
729    pub backends: Vec<String>,
730    /// Request genuine re-encode routes for same-format conversions.
731    ///
732    /// By default [`Graph::routes`] short-circuits a same-format request to one
733    /// empty identity plan. When this flag is set, the search instead looks for
734    /// nonempty routes that return to the source format (a re-encode such as
735    /// `png→png` recompression or `mp4→mp4` codec change, possibly through an
736    /// intermediate format), allowing exactly one revisit to the target format
737    /// as the route's end. If no such route exists, the search reports
738    /// [`PlanError::NoRoute`]; an execution engine may then decide whether to
739    /// fall back to an identity copy. Disabled by default.
740    pub reencode_same_format: bool,
741    /// Content kinds the final target representation must carry.
742    ///
743    /// A route is admissible only when its target's observed [`ContentProfile`]
744    /// (or, with no profile, its format's declared [`Format::payloads`])
745    /// declares every required kind through [`ContentKind::matches`]. Empty by
746    /// default, which places no content requirement. Enforced by both
747    /// [`Graph::routes_with_profile`] and [`Graph::routes`] after the policy is
748    /// normalized; a route whose final edge cannot deliver the required kinds
749    /// is excluded from the result set.
750    pub require: Vec<ContentKind>,
751    /// Whether the execution engine should ask adapters to inspect file content
752    /// before planning, instead of routing on format metadata alone.
753    ///
754    /// The planner does not inspect files itself; this is a directive consumed
755    /// by engines such as `convert_rs::Converter`, which calls
756    /// [`Graph::routes_with_profile`] with adapter-reported stream profiles when
757    /// the flag is set. The planner ignores it.
758    pub inspect_content: bool,
759    /// Require source-content evidence instead of trusting declared payloads.
760    ///
761    /// With [`Graph::routes_with_profile`] and no observed profile for the
762    /// source format, edges that declare [`Conversion::requires`] content pass
763    /// when this is disabled (the default) if the source format's declared
764    /// [`Format::payloads`] cover them, and fail when enabled unless a real
765    /// profile was supplied. Applies only to edges leaving the profiled source
766    /// format.
767    pub require_content: bool,
768    /// Permit edges in [`ConversionCategory::Creative`]; disabled by default.
769    ///
770    /// Creative operations generate expressive representations of content
771    /// (spectrograms, sonification, ASCII art) rather than conventional
772    /// conversions. Keeping them opt-in means an ordinary request never
773    /// silently produces art and an ordinary no-route error stays a no-route
774    /// error. The zero-step identity route ignores this gate because it has no
775    /// category.
776    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    /// Normalize this policy's content vocabulary for planning.
806    ///
807    /// Codecs and kinds are trimmed and lowercased, empty codec entries become
808    /// `None`, sort keys place untagged kinds before tagged ones, and vectors
809    /// are deduplicated. Returns an error when a codec tag contains characters
810    /// forbidden in format IDs, because comparison is otherwise byte-exact.
811    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    /// Test only the kind gate, without inspecting external tools or formats.
827    ///
828    /// Lossless and extraction steps always pass; lossy steps pass unless
829    /// [`Self::allow_lossy`] is disabled. Use [`Self::allows_edge`]
830    /// to also apply the external-tool gates.
831    #[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    /// Whether the policy permits executing this exact edge, including the
845    /// out-of-process tool, creative-category, and reinterpret/package-from-tools
846    /// gates.
847    ///
848    /// Does not check decode-only destinations, search budgets, graph membership,
849    /// backend availability, [`Self::backends`], or [`Self::retain`].
850    ///
851    /// # Examples
852    ///
853    /// ```rust
854    /// use convert_rs_core::{Conversion, ConversionKind, Policy};
855    /// let edge = Conversion::new("txt", "zip", "archiver", "pack",
856    ///     ConversionKind::Package, 1).requires_external();
857    /// let mut policy = Policy {
858    ///     allow_packaging: true,
859    ///     allow_external: true,
860    ///     ..Policy::default()
861    /// };
862    /// assert!(policy.allows(edge.kind));
863    /// assert!(!policy.allows_edge(&edge));
864    /// policy.allow_external_packaging = true;
865    /// assert!(policy.allows_edge(&edge));
866    /// ```
867    #[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    /// Whether the backend restrict-list admits `backend`.
891    ///
892    /// An empty [`Self::backends`] admits every backend. Otherwise the name must
893    /// match one entry exactly, after trimming the policy-side value.
894    #[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    /// Whether an edge's declared retention covers every property in [`Self::retain`].
904    ///
905    /// Both sides are trimmed and lowercased; empty property names are ignored.
906    /// This trusts the adapter's [`Conversion::retained`] claim.
907    #[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/// An ordered sequence of conversion steps and its declared total cost.
917///
918/// [`Graph::routes`] produces connected, loopless plans. Public fields also allow
919/// callers to construct plans directly; this type does not validate them.
920/// An empty plan represents an identity operation, not a format validation pass.
921#[derive(Clone, Debug, PartialEq, Eq)]
922#[non_exhaustive]
923pub struct Plan {
924    /// Steps in execution order.
925    ///
926    /// Plans returned by [`Graph::routes`] replace wildcard inputs with the
927    /// source format at that step. Manually constructed plans must do the same.
928    pub steps: Vec<Conversion>,
929    /// Sum of edge costs in [`Self::steps`] for planner-generated plans.
930    ///
931    /// The type does not recalculate this field after manual changes.
932    pub cost: u64,
933}
934
935impl Plan {
936    /// Construct a plan and compute [`Self::cost`] from the sum of step costs.
937    ///
938    /// Cost accumulation saturates at `u64::MAX` instead of panicking, although
939    /// saturating requires over four billion steps and is unreachable in practice.
940    #[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    /// The content kinds the final step declares it delivers.
949    ///
950    /// An empty plan (identity) produces nothing it does not already have, so
951    /// this returns an empty list; callers match the observed profile of the
952    /// file directly for identity routes. Intermediate steps' produced kinds
953    /// are not aggregated: a step's declared content refers to what it places
954    /// in its own target representation.
955    #[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    /// The zero-step, zero-cost identity plan.
963    fn default() -> Self {
964        Self {
965            steps: Vec::new(),
966            cost: 0,
967        }
968    }
969}
970
971/// Errors returned while validating or searching the conversion graph.
972#[derive(Clone, Debug, PartialEq, Eq, thiserror::Error)]
973pub enum PlanError {
974    /// Invalid format metadata, edge metadata, or policy, with an explanation.
975    #[error("invalid graph or policy: {0}")]
976    Invalid(
977        /// Human-readable validation failure.
978        String,
979    ),
980    /// An endpoint or lookup value does not resolve to a registered format.
981    #[error("unknown format: {0}")]
982    UnknownFormat(
983        /// Unresolved ID or lookup value.
984        String,
985    ),
986    /// No route satisfies the policy and step budget.
987    #[error("no route from {from} to {to}")]
988    NoRoute {
989        /// Resolved source format ID.
990        from: String,
991        /// Resolved target format ID.
992        to: String,
993    },
994    /// The forward edge budget was exhausted before any route was found.
995    #[error("route search limit reached before finding a route")]
996    SearchLimit,
997}
998
999/// An in-memory registry of formats and directed conversion edges.
1000///
1001/// Registration validates metadata, not adapter availability or file contents.
1002/// Search is read-only; no adapter or external process is executed.
1003#[derive(Clone, Debug, Default)]
1004pub struct Graph {
1005    formats: BTreeMap<String, Format>,
1006    conversions: BTreeMap<String, Vec<Conversion>>,
1007}
1008
1009impl Graph {
1010    /// Create an empty format graph.
1011    pub fn new() -> Self {
1012        Self::default()
1013    }
1014
1015    /// Register a lowercase ASCII ID of 1..=64 bytes using letters, digits,
1016    /// `-`, `_`, `.`, or `+`. Extensions follow the same rules after normalization.
1017    /// Duplicate IDs merge sorted, unique extensions and keep the lexicographically
1018    /// smallest name. Conflicting media categories are rejected without changes.
1019    /// The first registration's `decode_only` flag is retained for duplicate IDs.
1020    ///
1021    /// # Errors
1022    ///
1023    /// Returns [`PlanError::Invalid`] for invalid IDs or aliases, or a conflicting
1024    /// media category. The graph is unchanged on error.
1025    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    /// Register an edge between existing IDs. `*` is allowed only as the input
1092    /// of a Reinterpret or Package edge and matches every registered format.
1093    /// Identical edges are idempotent; distinct parallel edges are retained.
1094    ///
1095    /// Endpoint IDs are exact and case-sensitive, not extension aliases. Content
1096    /// requirements and produced kinds ([`Conversion::requires`],
1097    /// [`Conversion::produces`]) are normalized and must use lowercase codec
1098    /// tags that satisfy the same character rules as format IDs. This method
1099    /// does not verify that the named backend implements the operation.
1100    ///
1101    /// # Errors
1102    ///
1103    /// Returns [`PlanError::Invalid`] for zero cost, blank backend or operation,
1104    /// an unsupported wildcard kind, or an invalid content codec tag. Returns
1105    /// [`PlanError::UnknownFormat`] for unregistered endpoints. The graph is
1106    /// unchanged on error.
1107    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    /// Iterate in ascending format ID order.
1147    pub fn formats(&self) -> impl Iterator<Item = &Format> {
1148        self.formats.values()
1149    }
1150
1151    /// Iterate every registered edge, sorted by source ID then edge order.
1152    pub fn conversions(&self) -> impl Iterator<Item = &Conversion> {
1153        self.conversions.values().flatten()
1154    }
1155
1156    /// Look up an exact, case-sensitive registered ID.
1157    pub fn format(&self, id: &str) -> Option<&Format> {
1158        self.formats.get(id)
1159    }
1160
1161    /// Resolve a trimmed, case-insensitive ID, extension, or MIME type,
1162    /// optionally dot-prefixed.
1163    ///
1164    /// Exact IDs take precedence, then extension aliases, then MIME types that
1165    /// contain a slash. Ambiguous values select the smallest format ID. This
1166    /// does not interpret paths.
1167    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    /// Enumerate cheapest loopless routes using policy-filtered A* search.
1193    /// Inputs are resolved as IDs or extension aliases. Equal formats yield one
1194    /// empty, zero-cost plan unless [`Policy::reencode_same_format`] is set, in
1195    /// which case a nonempty route returning to the source format is searched.
1196    /// Policy limits above their hard caps are clamped.
1197    ///
1198    /// Each path retains its own visited formats, so parallel edges and alternative
1199    /// prefixes remain eligible. At most `max_expansions` candidate edges are examined,
1200    /// with shared prefixes rather than copied plans. Equal estimated costs favor
1201    /// higher spent cost, then deterministic insertion order (specific edges before
1202    /// wildcard edges, each ordered by the fields of Conversion).
1203    ///
1204    /// [`Policy::backends`] and [`Policy::retain`] prune edges inside the search, in
1205    /// both the reverse distance pass and the forward expansion, rather than
1206    /// filtering the returned plans. [`Policy::require`] is enforced through the
1207    /// target format's declared [`Format::payloads`] and each edge's
1208    /// [`Conversion::produces`] claim.
1209    ///
1210    /// Reaching the expansion limit returns routes already found, even if fewer
1211    /// than requested. If none have been found, it returns SearchLimit. Exhausting
1212    /// the search without a route returns NoRoute, including the step-limit case.
1213    /// Identity routes do not apply edge or decode-only gates. A successful plan
1214    /// is a metadata route, not proof that execution will succeed.
1215    ///
1216    /// # Errors
1217    ///
1218    /// Returns [`PlanError::UnknownFormat`] for an unresolved endpoint,
1219    /// [`PlanError::Invalid`] for zero `max_routes`, [`PlanError::NoRoute`] when
1220    /// no permitted route exists within the step budget, or
1221    /// [`PlanError::SearchLimit`] when the edge budget is exhausted before a route
1222    /// is found. Partial results carry no separate truncation indicator.
1223    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    /// Enumerate routes with an observed [`ContentProfile`] for the source file.
1229    ///
1230    /// Behaves exactly like [`Self::routes`], except that edges leaving the
1231    /// profiled source format are also gated on their [`Conversion::requires`]
1232    /// content: each requirement must be satisfied by some stream in `profile`
1233    /// (matched through [`ContentKind::matches`]), instead of trusted against
1234    /// the source format's declared [`Format::payloads`]. An edge whose source
1235    /// is not `profile.format` is unaffected. With no profile available, edges
1236    /// that declare requirements fall back to the source format's payloads
1237    /// unless [`Policy::require_content`] is set, in which case any edge with
1238    /// source content requirements is pruned because its claims are unverified.
1239    /// [`Policy::require`] matches the target's observed profile when
1240    /// `profile.format` equals the resolved target, otherwise the target's
1241    /// declared payloads and edge [`Conversion::produces`] claims.
1242    ///
1243    /// The graph never opens files; callers obtain `profile` from an engine
1244    /// inspection (for example `convert_rs::Converter::profile`) that reads
1245    /// stream metadata through adapters.
1246    ///
1247    /// # Errors
1248    ///
1249    /// As [`Self::routes`].
1250    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            // The byte-preserving identity route answers the content question
1294            // directly: an observed profile of the file is ground truth for it.
1295            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            // With reencode_same_format the root already sits on the target;
1351            // only a nonempty route returning to it counts as a plan.
1352            if path.format == to.id && path.depth > 0 {
1353                let plan = path.plan();
1354                // A wildcard and a specific edge can materialize the same plan.
1355                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                // A wildcard edge's content requirements are judged against the
1385                // format actually leaving this path vertex, not against "*".
1386                if edge.from == "*" && !content_usable(edge, path.format) {
1387                    continue;
1388                }
1389                // Re-entering the target format is allowed only when a same-format
1390                // re-encode was requested. Returning paths are terminal: the pop
1391                // above records the plan without expanding further, so a route can
1392                // close on the target exactly once and never chain through it.
1393                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                // One virtual wildcard vertex avoids materializing V * W edges.
1457                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
1524// References borrow the immutable graph; Rc shares prefixes only within a query.
1525struct 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        // A slash marks a MIME lookup; unknown types never match IDs or aliases.
2094        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            // Interior formats must be distinct; only the target format may
2218            // appear at both the root and the closing step.
2219            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        // The cheap noise routes fill the default max_routes budget entirely.
2319        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        // Identity ignores the category gate entirely.
2372        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        // Declared payloads qualify edges without a profile.
2743        assert_eq!(graph.routes("mp4", "wav", &policy).unwrap().len(), 1);
2744
2745        // A profile is ground truth: this file has no audio stream.
2746        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        // require_content refuses unverified payload claims without a profile.
2763        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        // A tagged requirement is satisfied by an exact produced claim, not by
2826        // an untagged payload declaration.
2827        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        // Identity routes answer from the observed profile only under require.
2846        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}