Skip to main content

alpha2_model/
composition.rs

1//! Composition graphs: a clip's picture built from connected nodes.
2//!
3//! A [`Composition`] is an acyclic graph of image operations stored once in the project. A
4//! clip refers to it with a [`ClipComposition`], which also maps the clip's timeline time to
5//! composition time. Every node outputs one image and names the nodes it takes inputs from;
6//! inputs may be left unconnected while a graph is being built.
7//!
8//! A [`NodeOp::Group`] node draws another composition, feeding its [`NodeOp::GroupInput`]
9//! nodes and setting its [`CompositionControl`]s per group node. A
10//! [`crate::MediaKind::Composition`] source shows one on the timeline or in a media node.
11//! Compositions may not use themselves. A composition is inlined wherever it is drawn, so
12//! nesting is bounded by [`MAX_COMPOSITION_DEPTH`] and total drawn nodes by
13//! [`MAX_INLINED_NODES`].
14//!
15//! Saving checks structure: names resolve, nothing depends on itself, values are in range.
16//! Rendering additionally requires every input reachable from the output to be connected.
17//! Nodes that do not reach the output are kept and ignored.
18
19use crate::animation::opaque;
20use crate::{
21    Animated, ClipBlendMode, ClipEffect, CompositionId, EffectValue, Generator, MatteMode, NodeId,
22    ShapeMask, VisualProperties,
23};
24use alpha2_media::SourceId;
25use alpha2_time::MediaTime;
26use serde::{Deserialize, Serialize};
27use std::collections::BTreeMap;
28use std::collections::{HashMap, HashSet};
29
30/// Most compositions in one project.
31pub const MAX_COMPOSITIONS: usize = 10_000;
32/// Most nodes in one composition.
33pub const MAX_COMPOSITION_NODES: usize = 256;
34/// The most named inputs an effect node gives its effect, matching what an effect definition
35/// may declare.
36pub const MAX_EFFECT_INPUTS: usize = 8;
37/// Most layers in one merge node.
38pub const MAX_MERGE_LAYERS: usize = 32;
39/// Most inputs a composition takes as a group.
40pub const MAX_GROUP_INPUTS: usize = 16;
41/// Most controls a composition exposes as a group.
42pub const MAX_COMPOSITION_CONTROLS: usize = 64;
43/// Deepest nesting of compositions. A composition that draws no other has depth one; one
44/// that draws others (via group nodes or composition-source media nodes) is one deeper than
45/// the deepest of them.
46pub const MAX_COMPOSITION_DEPTH: usize = 64;
47/// Most nodes the project's compositions draw in total. Each node counts one, except a group
48/// node or composition-source media node, which counts the nodes of the composition it
49/// draws. This bounds compile cost however uses multiply.
50pub const MAX_INLINED_NODES: usize = 65_536;
51/// Most composition nodes the clips at one instant draw together, each clip counted as
52/// [`MAX_INLINED_NODES`] counts its composition and composition source. This bounds per-frame
53/// work to one composition of the largest allowed size.
54pub const MAX_FRAME_INLINED_NODES: usize = 65_536;
55
56/// An acyclic graph of image operations with one selected output.
57#[derive(Clone, Debug, Deserialize, PartialEq, Serialize)]
58#[cfg_attr(feature = "schema", derive(schemars::JsonSchema))]
59#[serde(deny_unknown_fields)]
60pub struct Composition {
61    /// Stable composition identity.
62    pub id: CompositionId,
63    /// The graph's nodes. Order has no meaning; a node may name a later node as its input.
64    #[serde(default)]
65    #[serde(deserialize_with = "crate::bounded::seq::<_, _, { crate::MAX_COMPOSITION_NODES }>")]
66    #[cfg_attr(feature = "schema", schemars(length(max = crate::MAX_COMPOSITION_NODES)))]
67    pub nodes: Vec<CompositionNode>,
68    /// The node whose image is the composition's picture. A composition without one saves but
69    /// cannot be rendered.
70    #[serde(default)]
71    pub output: Option<NodeId>,
72    /// The images a group node gives it, by name, in port order; its [`NodeOp::GroupInput`]
73    /// nodes read them.
74    #[serde(default, skip_serializing_if = "Vec::is_empty")]
75    #[serde(deserialize_with = "crate::bounded::seq::<_, _, { crate::MAX_GROUP_INPUTS }>")]
76    #[cfg_attr(feature = "schema", schemars(length(max = crate::MAX_GROUP_INPUTS)))]
77    pub inputs: Vec<String>,
78    /// The node settings a group node may set, by name.
79    #[serde(default, skip_serializing_if = "Vec::is_empty")]
80    #[serde(deserialize_with = "crate::bounded::seq::<_, _, { crate::MAX_COMPOSITION_CONTROLS }>")]
81    #[cfg_attr(feature = "schema", schemars(length(max = crate::MAX_COMPOSITION_CONTROLS)))]
82    pub controls: Vec<CompositionControl>,
83}
84
85/// A node setting a composition exposes to group nodes: an effect or transition parameter of
86/// one of its nodes.
87#[derive(Clone, Debug, Deserialize, PartialEq, Eq, Serialize)]
88#[cfg_attr(feature = "schema", derive(schemars::JsonSchema))]
89#[serde(deny_unknown_fields)]
90pub struct CompositionControl {
91    /// The name a group node sets it by; unique in the composition.
92    pub name: String,
93    /// The effect or transition node.
94    pub node: NodeId,
95    /// The parameter of its effect.
96    pub param: String,
97}
98
99impl Composition {
100    /// Creates an empty composition with no output.
101    #[must_use]
102    pub const fn new(id: CompositionId) -> Self {
103        Self {
104            id,
105            nodes: Vec::new(),
106            output: None,
107            inputs: Vec::new(),
108            controls: Vec::new(),
109        }
110    }
111
112    /// The node named `id`.
113    #[must_use]
114    pub fn node(&self, id: &NodeId) -> Option<&CompositionNode> {
115        self.nodes.iter().find(|node| &node.id == id)
116    }
117}
118
119/// One image operation in a [`Composition`].
120#[derive(Clone, Debug, Deserialize, PartialEq, Serialize)]
121#[cfg_attr(feature = "schema", derive(schemars::JsonSchema))]
122#[serde(deny_unknown_fields)]
123pub struct CompositionNode {
124    /// Identity, unique within its composition.
125    pub id: NodeId,
126    /// Whether the node passes its [`NodeOp::bypass_input`] through unchanged. A node without
127    /// inputs cannot be bypassed.
128    #[serde(default)]
129    pub bypass: bool,
130    /// What the node does, with its inputs and settings.
131    pub op: NodeOp,
132}
133
134impl CompositionNode {
135    /// Creates a node that is not bypassed.
136    #[must_use]
137    pub const fn new(id: NodeId, op: NodeOp) -> Self {
138        Self {
139            id,
140            bypass: false,
141            op,
142        }
143    }
144
145    /// The inputs drawing the node reads, in input order: only its [`NodeOp::bypass_input`] when
146    /// bypassed (none for a merge without layers), every input otherwise.
147    #[must_use]
148    pub fn needed_inputs(&self) -> Vec<NodeInput<'_>> {
149        if self.bypass {
150            return self.op.bypass_input().into_iter().collect();
151        }
152        self.op.inputs()
153    }
154}
155
156/// The operation of a [`CompositionNode`].
157///
158/// Animated settings are keyed in composition time (see [`ClipComposition`]).
159#[derive(Clone, Debug, Deserialize, PartialEq, Serialize)]
160#[cfg_attr(feature = "schema", derive(schemars::JsonSchema))]
161#[serde(tag = "type", rename_all = "snake_case", deny_unknown_fields)]
162pub enum NodeOp {
163    /// The picture of the clip showing the composition: its source at the time-mapped source
164    /// time, or what its generated source draws.
165    Clip {},
166    /// Another visual source, read at `start` plus the composition time. Adds no sound to the
167    /// mix.
168    Media {
169        /// The source; a video, image, or generated source.
170        source_id: SourceId,
171        /// Source time shown at composition time zero. Non-negative.
172        #[serde(default)]
173        start: MediaTime,
174    },
175    /// A picture the engine draws.
176    Generator {
177        /// What is drawn.
178        generator: Generator,
179    },
180    /// A registered effect: its input plus any named images it samples.
181    Effect {
182        /// The image the effect processes; a bypassed node passes it through.
183        #[serde(default)]
184        input: Option<NodeId>,
185        /// The images the effect samples besides its input, by the names its definition declares
186        /// (`sample_<name>` in its shader); at most [`MAX_EFFECT_INPUTS`]. An undeclared name, or a
187        /// declared one left out, is invalid for a built-in and fails the frames that draw the
188        /// node otherwise.
189        #[serde(default, skip_serializing_if = "BTreeMap::is_empty")]
190        #[serde(deserialize_with = "crate::bounded::map::<_, _, _, { MAX_EFFECT_INPUTS }>")]
191        #[cfg_attr(feature = "schema", schemars(extend("maxProperties" = MAX_EFFECT_INPUTS)))]
192        inputs: BTreeMap<String, Option<NodeId>>,
193        /// The versioned effect and its parameters.
194        effect: ClipEffect,
195    },
196    /// A registered two-input transition at an explicit progress.
197    Transition {
198        /// The image at progress zero.
199        #[serde(default)]
200        from: Option<NodeId>,
201        /// The image at progress one.
202        #[serde(default)]
203        to: Option<NodeId>,
204        /// The versioned transition and its parameters.
205        effect: ClipEffect,
206        /// Progress through the transition, in `0..=1`.
207        progress: Animated<f32>,
208    },
209    /// The input placed on the canvas by a transform and opacity.
210    Transform {
211        /// The image placed.
212        #[serde(default)]
213        input: Option<NodeId>,
214        /// Position, anchor, scale, rotation, and opacity.
215        #[serde(default)]
216        transform: VisualProperties,
217    },
218    /// Ordered layers composited over transparency.
219    Merge {
220        /// Layers from bottom to top.
221        #[serde(
222            default,
223            deserialize_with = "crate::bounded::seq::<_, _, { MAX_MERGE_LAYERS }>"
224        )]
225        #[cfg_attr(feature = "schema", schemars(length(max = MAX_MERGE_LAYERS)))]
226        layers: Vec<MergeLayer>,
227    },
228    /// The input kept where a second image says.
229    Matte {
230        /// The image kept.
231        #[serde(default)]
232        input: Option<NodeId>,
233        /// The image whose alpha or luminance is coverage.
234        #[serde(default)]
235        matte: Option<NodeId>,
236        /// Which property of the matte image is coverage.
237        mode: MatteMode,
238    },
239    /// The input kept inside shapes.
240    ShapeMask {
241        /// The image masked.
242        #[serde(default)]
243        input: Option<NodeId>,
244        /// The shapes, combined in order; at most [`crate::MAX_CLIP_MASKS`]. Geometry is in the
245        /// input image's normalized space.
246        #[serde(deserialize_with = "crate::bounded::seq::<_, _, { crate::MAX_CLIP_MASKS }>")]
247        #[cfg_attr(feature = "schema", schemars(length(max = crate::MAX_CLIP_MASKS)))]
248        masks: Vec<ShapeMask>,
249    },
250    /// Another composition drawn in this one's time as a group: its output, with group inputs
251    /// fed from `inputs` and controls set from `controls`.
252    Group {
253        /// The composition drawn.
254        composition: CompositionId,
255        /// The image for each of its inputs, in its port order.
256        #[serde(default)]
257        #[serde(deserialize_with = "crate::bounded::seq::<_, _, { crate::MAX_GROUP_INPUTS }>")]
258        #[cfg_attr(feature = "schema", schemars(length(max = crate::MAX_GROUP_INPUTS)))]
259        inputs: Vec<Option<NodeId>>,
260        /// Values for its controls, by name; unset controls keep the composition's own value. Keyed
261        /// in composition time.
262        #[serde(default, skip_serializing_if = "BTreeMap::is_empty")]
263        controls: BTreeMap<String, Animated<EffectValue>>,
264    },
265    /// In a composition used as a group, the image the group node gives its input `index`.
266    GroupInput {
267        /// The input, in the composition's port order.
268        index: u32,
269    },
270}
271
272/// One layer of a [`NodeOp::Merge`].
273#[derive(Clone, Debug, Deserialize, PartialEq, Serialize)]
274#[cfg_attr(feature = "schema", derive(schemars::JsonSchema))]
275#[serde(deny_unknown_fields)]
276pub struct MergeLayer {
277    /// The layer's image.
278    #[serde(default)]
279    pub input: Option<NodeId>,
280    /// How the layer blends with the layers under it.
281    #[serde(default)]
282    pub blend_mode: ClipBlendMode,
283    /// The layer's opacity, in `0..=1`.
284    #[serde(default = "opaque")]
285    pub opacity: Animated<f32>,
286}
287
288impl MergeLayer {
289    /// An opaque, normally blended layer of `input`.
290    #[must_use]
291    pub const fn new(input: Option<NodeId>) -> Self {
292        Self {
293            input,
294            blend_mode: ClipBlendMode::Normal,
295            opacity: Animated::Constant { value: 1.0 },
296        }
297    }
298}
299
300/// What each composition's output reads: the group inputs and clip nodes reachable from its
301/// output, following group nodes into their compositions. A group node needs only the ports
302/// its composition reads, so unread ports may be left unconnected.
303///
304/// Built once per project in dependency order, without recursion. A composition that uses
305/// itself (refused by validation) is taken to read every port and draw the clip.
306#[derive(Clone, Debug, Default)]
307pub struct CompositionReads<'a> {
308    read: HashMap<&'a CompositionId, Reads>,
309}
310
311/// What one composition's output reads.
312#[derive(Clone, Debug)]
313struct Reads {
314    /// By group input index.
315    ports: Vec<bool>,
316    /// Whether it draws the picture of the clip showing it.
317    clip: bool,
318}
319
320impl<'a> CompositionReads<'a> {
321    /// What each of `compositions` reads, resolving group nodes by ID.
322    #[must_use]
323    pub fn new(compositions: &HashMap<&'a CompositionId, &'a Composition>) -> Self {
324        let mut reads = Self::default();
325        let mut walking = HashSet::new();
326        let group = |node: &'a CompositionNode| match &node.op {
327            NodeOp::Group { composition, .. } => compositions.get(composition).copied(),
328            _ => None,
329        };
330        for root in compositions.values() {
331            let mut stack = vec![(*root, false)];
332            while let Some((composition, expanded)) = stack.pop() {
333                if reads.read.contains_key(&composition.id) {
334                    continue;
335                }
336                if !expanded {
337                    if !walking.insert(&composition.id) {
338                        continue;
339                    }
340                    stack.push((composition, true));
341                    stack.extend(
342                        composition
343                            .nodes
344                            .iter()
345                            .filter_map(group)
346                            .filter(|inner| {
347                                !reads.read.contains_key(&inner.id) && !walking.contains(&inner.id)
348                            })
349                            .map(|inner| (inner, false)),
350                    );
351                    continue;
352                }
353                walking.remove(&composition.id);
354                let read = reads.walk(composition);
355                reads.read.insert(&composition.id, read);
356            }
357        }
358        reads
359    }
360
361    /// Whether `composition`'s output reads its group input `port`; true for an unknown
362    /// composition.
363    #[must_use]
364    pub fn reads_port(&self, composition: &CompositionId, port: usize) -> bool {
365        self.read
366            .get(composition)
367            .is_none_or(|read| read.ports.get(port).copied().unwrap_or(false))
368    }
369
370    /// Whether `composition`, shown by a clip, draws the clip's picture (its output reaches a
371    /// clip node, directly or in a group). True for an unknown composition.
372    #[must_use]
373    pub fn draws_clip(&self, composition: &CompositionId) -> bool {
374        self.read.get(composition).is_none_or(|read| read.clip)
375    }
376
377    /// The inputs drawing `node` reads, in input order: its [`CompositionNode::needed_inputs`],
378    /// restricted for a group node to the ports its composition reads.
379    #[must_use]
380    pub fn needed_inputs<'n>(&self, node: &'n CompositionNode) -> Vec<NodeInput<'n>> {
381        let mut needed = node.needed_inputs();
382        if let (false, NodeOp::Group { composition, .. }) = (node.bypass, &node.op) {
383            needed.retain(|input| match input {
384                NodeInput::Port(port, _) => self.reads_port(composition, *port),
385                _ => true,
386            });
387        }
388        needed
389    }
390
391    /// What `composition`'s output reaches, given that its group nodes' compositions are known.
392    fn walk(&self, composition: &'a Composition) -> Reads {
393        let nodes: HashMap<&NodeId, &CompositionNode> = composition
394            .nodes
395            .iter()
396            .map(|node| (&node.id, node))
397            .collect();
398        let mut read = Reads {
399            ports: vec![false; composition.inputs.len()],
400            clip: false,
401        };
402        let mut reached = HashSet::new();
403        let mut pending: Vec<&NodeId> = composition.output.iter().collect();
404        while let Some(id) = pending.pop() {
405            let Some(node) = nodes.get(id).filter(|_| reached.insert(id)) else {
406                continue;
407            };
408            match (node.bypass, &node.op) {
409                (false, NodeOp::GroupInput { index }) => {
410                    if let Some(port) = usize::try_from(*index)
411                        .ok()
412                        .and_then(|index| read.ports.get_mut(index))
413                    {
414                        *port = true;
415                    }
416                }
417                (false, NodeOp::Clip {}) => read.clip = true,
418                (false, NodeOp::Group { composition, .. }) => {
419                    read.clip |= self.draws_clip(composition);
420                }
421                _ => {}
422            }
423            pending.extend(
424                self.needed_inputs(node)
425                    .into_iter()
426                    .filter_map(NodeInput::node),
427            );
428        }
429        read
430    }
431}
432
433/// One named input of a node, as a node's inputs are listed.
434#[derive(Clone, Copy, Debug, Eq, PartialEq)]
435pub enum NodeInput<'a> {
436    /// A named input: `input`, `from`, `to`, or `matte`.
437    Named(&'static str, Option<&'a NodeId>),
438    /// The input of a merge layer, by layer index.
439    Layer(usize, Option<&'a NodeId>),
440    /// An input of a group node, by port index.
441    Port(usize, Option<&'a NodeId>),
442    /// A named input of an effect node.
443    EffectInput(&'a str, Option<&'a NodeId>),
444}
445
446impl<'a> NodeInput<'a> {
447    /// The connected node, if any.
448    #[must_use]
449    pub const fn node(self) -> Option<&'a NodeId> {
450        match self {
451            Self::Named(_, node)
452            | Self::Layer(_, node)
453            | Self::Port(_, node)
454            | Self::EffectInput(_, node) => node,
455        }
456    }
457
458    /// The input's name as a diagnostic shows it: `input`, `from`, `to`, `matte`, `layers[i]`,
459    /// `inputs[i]`, or `inputs.<name>`.
460    #[must_use]
461    pub fn name(self) -> String {
462        match self {
463            Self::Named(name, _) => name.to_owned(),
464            Self::Layer(index, _) => format!("layers[{index}]"),
465            Self::Port(index, _) => format!("inputs[{index}]"),
466            Self::EffectInput(name, _) => format!("inputs.{name}"),
467        }
468    }
469}
470
471impl NodeOp {
472    /// Every input of the operation, connected or not, in a fixed order.
473    #[must_use]
474    pub fn inputs(&self) -> Vec<NodeInput<'_>> {
475        match self {
476            Self::Clip {}
477            | Self::Media { .. }
478            | Self::Generator { .. }
479            | Self::GroupInput { .. } => Vec::new(),
480            Self::Group { inputs, .. } => inputs
481                .iter()
482                .enumerate()
483                .map(|(index, input)| NodeInput::Port(index, input.as_ref()))
484                .collect(),
485            Self::Effect { input, inputs, .. } => {
486                std::iter::once(NodeInput::Named("input", input.as_ref()))
487                    .chain(
488                        inputs
489                            .iter()
490                            .map(|(name, node)| NodeInput::EffectInput(name, node.as_ref())),
491                    )
492                    .collect()
493            }
494            Self::Transform { input, .. } | Self::ShapeMask { input, .. } => {
495                vec![NodeInput::Named("input", input.as_ref())]
496            }
497            Self::Transition { from, to, .. } => vec![
498                NodeInput::Named("from", from.as_ref()),
499                NodeInput::Named("to", to.as_ref()),
500            ],
501            Self::Matte { input, matte, .. } => vec![
502                NodeInput::Named("input", input.as_ref()),
503                NodeInput::Named("matte", matte.as_ref()),
504            ],
505            Self::Merge { layers } => layers
506                .iter()
507                .enumerate()
508                .map(|(index, layer)| NodeInput::Layer(index, layer.input.as_ref()))
509                .collect(),
510        }
511    }
512
513    /// The input a bypassed node passes through: `input` for one-input operations and mattes,
514    /// `from` for a transition, a merge's bottom layer, and a group's first input. `None` for
515    /// operations without inputs and merges without layers.
516    #[must_use]
517    pub fn bypass_input(&self) -> Option<NodeInput<'_>> {
518        match self {
519            Self::Clip {}
520            | Self::Media { .. }
521            | Self::Generator { .. }
522            | Self::GroupInput { .. } => None,
523            Self::Merge { layers } => layers
524                .first()
525                .map(|layer| NodeInput::Layer(0, layer.input.as_ref())),
526            _ => self.inputs().into_iter().next(),
527        }
528    }
529
530    /// Whether the operation takes inputs, and so can be bypassed.
531    #[must_use]
532    pub const fn has_inputs(&self) -> bool {
533        match self {
534            Self::Clip {}
535            | Self::Media { .. }
536            | Self::Generator { .. }
537            | Self::GroupInput { .. } => false,
538            Self::Group { inputs, .. } => !inputs.is_empty(),
539            _ => true,
540        }
541    }
542
543    /// The effect or transition invocation the operation runs, if any.
544    #[must_use]
545    pub const fn effect(&self) -> Option<&ClipEffect> {
546        match self {
547            Self::Effect { effect, .. } | Self::Transition { effect, .. } => Some(effect),
548            _ => None,
549        }
550    }
551}
552
553/// A clip's use of a [`Composition`], and how its time maps onto it.
554///
555/// Composition time is `offset + (t - clip start) * scale` for timeline time `t`, rounded
556/// down to a tick. Moving a clip keeps its offset so the animation moves with it; trimming
557/// its start by `d` adds `d * scale` to the offset so the rest stays in place. A negative
558/// offset holds settings at their first keyframe and media nodes at their first frame.
559#[derive(Clone, Debug, Deserialize, PartialEq, Eq, Serialize)]
560#[cfg_attr(feature = "schema", derive(schemars::JsonSchema))]
561#[serde(deny_unknown_fields)]
562pub struct ClipComposition {
563    /// The composition shown.
564    pub id: CompositionId,
565    /// Composition time at the clip's start.
566    #[serde(default)]
567    pub offset: MediaTime,
568    /// Composition time per timeline time.
569    #[serde(default)]
570    pub scale: TimeScale,
571}
572
573impl ClipComposition {
574    /// Shows `id` from its time zero at the timeline's rate.
575    #[must_use]
576    pub const fn new(id: CompositionId) -> Self {
577        Self {
578            id,
579            offset: MediaTime::ZERO,
580            scale: TimeScale::ONE,
581        }
582    }
583
584    /// The composition time at timeline time `time` of a clip starting at `clip_start`. `None`
585    /// when unrepresentable or the scale has a zero denominator.
586    #[must_use]
587    pub fn local_time(&self, clip_start: MediaTime, time: MediaTime) -> Option<MediaTime> {
588        let elapsed = i128::from(time.ticks()) - i128::from(clip_start.ticks());
589        let scaled = (elapsed * i128::from(self.scale.num))
590            .checked_div_euclid(i128::from(self.scale.den))?;
591        let local = i128::from(self.offset.ticks()).checked_add(scaled)?;
592        i64::try_from(local).ok().map(MediaTime)
593    }
594}
595
596/// A positive rational rate of one time against another.
597#[derive(Clone, Copy, Debug, Deserialize, PartialEq, Eq, Serialize)]
598#[cfg_attr(feature = "schema", derive(schemars::JsonSchema))]
599#[serde(deny_unknown_fields)]
600pub struct TimeScale {
601    /// Numerator; positive.
602    pub num: u32,
603    /// Denominator; positive.
604    pub den: u32,
605}
606
607impl TimeScale {
608    /// The same rate.
609    pub const ONE: Self = Self { num: 1, den: 1 };
610
611    /// Whether both terms are positive.
612    #[must_use]
613    pub const fn is_valid(self) -> bool {
614        self.num > 0 && self.den > 0
615    }
616}
617
618impl Default for TimeScale {
619    fn default() -> Self {
620        Self::ONE
621    }
622}
623
624/// Checks every composition's identity, node settings and connections, and returns the
625/// nodes each draws once inlined. `by_source` maps source IDs for media node lookups.
626pub(crate) fn validate_compositions<'a>(
627    compositions: &'a [Composition],
628    sources: &'a [crate::MediaSource],
629    by_source: &std::collections::HashMap<&SourceId, &crate::MediaSource>,
630    effect_resources: &std::collections::HashSet<&crate::EffectResourceId>,
631    canvas: (u32, u32),
632) -> Result<InlinedNodes<'a>, crate::ModelError> {
633    use crate::ModelError;
634    use std::collections::{HashMap, HashSet};
635
636    if compositions.len() > MAX_COMPOSITIONS {
637        return Err(ModelError::TooManyCompositions {
638            found: compositions.len(),
639            maximum: MAX_COMPOSITIONS,
640        });
641    }
642    let mut ids = HashSet::with_capacity(compositions.len());
643    for composition in compositions {
644        if !ids.insert(&composition.id) {
645            return Err(ModelError::DuplicateCompositionId(composition.id.clone()));
646        }
647    }
648    let by_id: HashMap<&CompositionId, &Composition> = compositions
649        .iter()
650        .map(|composition| (&composition.id, composition))
651        .collect();
652    if let Some(source) = sources.iter().find(|source| {
653        source
654            .composition
655            .as_ref()
656            .is_some_and(|id| !by_id.contains_key(id))
657    }) {
658        return Err(ModelError::InvalidCompositionSource {
659            source: source.id.clone(),
660        });
661    }
662    for composition in compositions {
663        if composition.nodes.len() > MAX_COMPOSITION_NODES {
664            return Err(ModelError::TooManyCompositionNodes {
665                composition: composition.id.clone(),
666                found: composition.nodes.len(),
667                maximum: MAX_COMPOSITION_NODES,
668            });
669        }
670        let mut positions = HashMap::with_capacity(composition.nodes.len());
671        for (position, node) in composition.nodes.iter().enumerate() {
672            if node.id.as_str().contains('/') {
673                return Err(ModelError::InvalidNodeId {
674                    composition: composition.id.clone(),
675                    node: node.id.clone(),
676                });
677            }
678            if positions.insert(&node.id, position).is_some() {
679                return Err(ModelError::DuplicateNodeId {
680                    composition: composition.id.clone(),
681                    node: node.id.clone(),
682                });
683            }
684        }
685        validate_ports(composition, &positions)?;
686        for node in &composition.nodes {
687            validate_node(
688                composition,
689                node,
690                by_source,
691                &by_id,
692                effect_resources,
693                canvas,
694            )?;
695            for input in node.op.inputs() {
696                if let Some(target) = input.node()
697                    && !positions.contains_key(target)
698                {
699                    return Err(ModelError::UnknownNodeInput {
700                        composition: composition.id.clone(),
701                        node: node.id.clone(),
702                        input: input.name(),
703                        target: target.clone(),
704                    });
705                }
706            }
707        }
708        if let Some(output) = &composition.output
709            && !positions.contains_key(output)
710        {
711            return Err(ModelError::UnknownCompositionOutput {
712                composition: composition.id.clone(),
713                node: output.clone(),
714            });
715        }
716        if let Some(node) = cycle_member(composition, &positions) {
717            return Err(ModelError::CompositionCycle {
718                composition: composition.id.clone(),
719                node: node.clone(),
720            });
721        }
722    }
723    if let Some(composition) = reference_cycle_member(compositions, &by_id, by_source) {
724        return Err(ModelError::CompositionUsesItself {
725            composition: composition.clone(),
726        });
727    }
728    validate_expansion(compositions, &by_id, sources)
729}
730
731/// The nodes each composition draws once inlined, as [`MAX_INLINED_NODES`] counts them.
732pub(crate) type InlinedNodes<'a> = std::collections::HashMap<&'a CompositionId, u64>;
733
734/// Checks that compositions nest at most [`MAX_COMPOSITION_DEPTH`] deep and draw at most
735/// [`MAX_INLINED_NODES`] nodes, and returns the nodes each draws. One iterative walk in
736/// dependency order counts each composition once without risking stack exhaustion.
737fn validate_expansion<'a>(
738    compositions: &'a [Composition],
739    by_id: &std::collections::HashMap<&'a CompositionId, &'a Composition>,
740    sources: &'a [crate::MediaSource],
741) -> Result<InlinedNodes<'a>, crate::ModelError> {
742    use std::collections::HashMap;
743    let composition_sources: HashMap<&SourceId, &CompositionId> = sources
744        .iter()
745        .filter_map(|source| Some((&source.id, source.composition.as_ref()?)))
746        .collect();
747    // The composition a node draws in its place, if any.
748    let draws = |node: &'a CompositionNode| -> Option<&'a CompositionId> {
749        match &node.op {
750            NodeOp::Group { composition, .. } => Some(composition),
751            NodeOp::Media { source_id, .. } => composition_sources.get(source_id).copied(),
752            _ => None,
753        }
754        .filter(|id| by_id.contains_key(id))
755    };
756    // Depth and inlined node count of each composition walked.
757    let mut walked: HashMap<&CompositionId, (usize, u64)> = HashMap::new();
758    let mut total = 0_u64;
759    for root in compositions {
760        let mut stack = vec![(root, false)];
761        while let Some((composition, expanded)) = stack.pop() {
762            if walked.contains_key(&composition.id) {
763                continue;
764            }
765            if !expanded {
766                stack.push((composition, true));
767                stack.extend(
768                    composition
769                        .nodes
770                        .iter()
771                        .filter_map(draws)
772                        .filter(|id| !walked.contains_key(id))
773                        .map(|id| (by_id[id], false)),
774                );
775                continue;
776            }
777            let mut depth = 1;
778            let mut nodes = 0_u64;
779            for node in &composition.nodes {
780                let (inner, count) = draws(node).map_or((0, 1), |id| walked[id]);
781                depth = depth.max(inner + 1);
782                nodes = nodes.saturating_add(count);
783            }
784            walked.insert(&composition.id, (depth, nodes));
785        }
786        let (depth, nodes) = walked[&root.id];
787        if depth > MAX_COMPOSITION_DEPTH {
788            return Err(crate::ModelError::CompositionNestedTooDeep {
789                composition: root.id.clone(),
790                maximum: MAX_COMPOSITION_DEPTH,
791            });
792        }
793        total = total.saturating_add(nodes);
794        if total > MAX_INLINED_NODES as u64 {
795            return Err(crate::ModelError::TooManyInlinedNodes {
796                maximum: MAX_INLINED_NODES,
797            });
798        }
799    }
800    Ok(walked
801        .into_iter()
802        .map(|(id, (_, nodes))| (id, nodes))
803        .collect())
804}
805
806/// Checks that a composition's group inputs are named, distinct and few enough, and its
807/// controls name distinct settings of its effect and transition nodes.
808fn validate_ports(
809    composition: &Composition,
810    positions: &std::collections::HashMap<&NodeId, usize>,
811) -> Result<(), crate::ModelError> {
812    use std::collections::HashSet;
813    let invalid = || crate::ModelError::InvalidCompositionPorts {
814        composition: composition.id.clone(),
815    };
816    let mut names = HashSet::new();
817    if composition.inputs.len() > MAX_GROUP_INPUTS
818        || composition
819            .inputs
820            .iter()
821            .any(|name| name.is_empty() || !names.insert(name))
822    {
823        return Err(invalid());
824    }
825    let mut controls = HashSet::new();
826    let mut settings = HashSet::new();
827    if composition.controls.len() > MAX_COMPOSITION_CONTROLS {
828        return Err(invalid());
829    }
830    for control in &composition.controls {
831        let node = positions
832            .get(&control.node)
833            .map(|position| &composition.nodes[*position]);
834        if control.name.is_empty()
835            || control.param.is_empty()
836            || !controls.insert(&control.name)
837            || !settings.insert((&control.node, &control.param))
838            || node.is_none_or(|node| node.op.effect().is_none())
839        {
840            return Err(invalid());
841        }
842        if let Some(effect) = node.and_then(|node| node.op.effect())
843            && let Some(spec) = crate::builtin_effect(&effect.id)
844            && spec.param(&control.param).is_none()
845        {
846            return Err(crate::ModelError::InvalidEffect {
847                owner: Box::new(crate::EffectOwner::Node {
848                    composition: composition.id.clone(),
849                    node: control.node.clone(),
850                }),
851                id: effect.id.clone(),
852                problem: crate::EffectProblem::UnknownParam(control.param.clone()),
853            });
854        }
855    }
856    Ok(())
857}
858
859/// A composition that uses itself through group nodes or composition sources: the first, in
860/// document order, that a depth-first walk finds on its own path.
861fn reference_cycle_member<'a>(
862    compositions: &'a [Composition],
863    by_id: &std::collections::HashMap<&'a CompositionId, &'a Composition>,
864    sources: &std::collections::HashMap<&SourceId, &'a crate::MediaSource>,
865) -> Option<&'a CompositionId> {
866    #[derive(Clone, Copy, PartialEq)]
867    enum Mark {
868        New,
869        Open,
870        Done,
871    }
872    let uses = |composition: &'a Composition| -> Vec<&'a CompositionId> {
873        composition
874            .nodes
875            .iter()
876            .filter_map(|node| match &node.op {
877                NodeOp::Group { composition, .. } => Some(composition),
878                NodeOp::Media { source_id, .. } => sources
879                    .get(source_id)
880                    .and_then(|source| source.composition.as_ref()),
881                _ => None,
882            })
883            .filter(|id| by_id.contains_key(id))
884            .collect()
885    };
886    let mut marks: std::collections::HashMap<&CompositionId, Mark> = compositions
887        .iter()
888        .map(|composition| (&composition.id, Mark::New))
889        .collect();
890    for root in compositions {
891        if marks[&root.id] != Mark::New {
892            continue;
893        }
894        let mut stack = vec![(&root.id, uses(root), 0_usize)];
895        marks.insert(&root.id, Mark::Open);
896        while let Some((current, next, at)) = stack.last_mut() {
897            let Some(target) = next.get(*at).copied() else {
898                marks.insert(current, Mark::Done);
899                stack.pop();
900                continue;
901            };
902            *at += 1;
903            match marks[target] {
904                Mark::Open => return Some(target),
905                Mark::New => {
906                    marks.insert(target, Mark::Open);
907                    stack.push((target, uses(by_id[target]), 0));
908                }
909                Mark::Done => {}
910            }
911        }
912    }
913    None
914}
915
916fn shape_error(
917    composition: &Composition,
918    node: &CompositionNode,
919    issue: crate::ShapeIssue,
920) -> crate::ModelError {
921    crate::ModelError::InvalidShape {
922        owner: crate::ShapeOwner::Node {
923            composition: composition.id.clone(),
924            node: node.id.clone(),
925        },
926        at: issue.at,
927        problem: issue.problem,
928    }
929}
930
931fn layout_error(
932    composition: &Composition,
933    node: &CompositionNode,
934    issue: crate::LayoutIssue,
935) -> crate::ModelError {
936    crate::ModelError::InvalidLayout {
937        owner: crate::ShapeOwner::Node {
938            composition: composition.id.clone(),
939            node: node.id.clone(),
940        },
941        at: issue.at,
942        problem: issue.problem,
943    }
944}
945
946/// Checks a node's built-in effect or transition, and the values a group node sets on its
947/// target's built-in parameters, against their definitions.
948fn check_builtin_effects(
949    composition: &Composition,
950    node: &CompositionNode,
951    compositions: &std::collections::HashMap<&CompositionId, &Composition>,
952) -> Result<(), crate::ModelError> {
953    use crate::effect_spec::{EffectKind, EffectProblem, builtin_effect, check_builtin};
954    let error = |id: &str, problem| crate::ModelError::InvalidEffect {
955        owner: Box::new(crate::EffectOwner::Node {
956            composition: composition.id.clone(),
957            node: node.id.clone(),
958        }),
959        id: id.to_owned(),
960        problem,
961    };
962    match &node.op {
963        NodeOp::Effect { effect, inputs, .. } => {
964            check_builtin(effect, EffectKind::Effect, Some(inputs))
965                .map_err(|problem| error(&effect.id, problem))?;
966        }
967        NodeOp::Transition { effect, .. } => {
968            check_builtin(effect, EffectKind::Transition, None)
969                .map_err(|problem| error(&effect.id, problem))?;
970        }
971        NodeOp::Group {
972            composition: target,
973            controls,
974            ..
975        } => {
976            let Some(target) = compositions.get(target) else {
977                return Ok(());
978            };
979            for (name, value) in controls {
980                let Some(control) = target.controls.iter().find(|control| &control.name == name)
981                else {
982                    continue;
983                };
984                let Some(effect) = target
985                    .nodes
986                    .iter()
987                    .find(|inner| inner.id == control.node)
988                    .and_then(|inner| inner.op.effect())
989                else {
990                    continue;
991                };
992                if let Some(param) =
993                    builtin_effect(&effect.id).and_then(|spec| spec.param(&control.param))
994                    && !param.accepts_animation(value)
995                {
996                    return Err(error(
997                        &effect.id,
998                        EffectProblem::InvalidParam(control.param.clone()),
999                    ));
1000                }
1001            }
1002        }
1003        _ => {}
1004    }
1005    Ok(())
1006}
1007
1008fn validate_node(
1009    composition: &Composition,
1010    node: &CompositionNode,
1011    sources: &std::collections::HashMap<&SourceId, &crate::MediaSource>,
1012    compositions: &std::collections::HashMap<&CompositionId, &Composition>,
1013    effect_resources: &std::collections::HashSet<&crate::EffectResourceId>,
1014    canvas: (u32, u32),
1015) -> Result<(), crate::ModelError> {
1016    use crate::ModelError;
1017
1018    let invalid = || ModelError::InvalidNode {
1019        composition: composition.id.clone(),
1020        node: node.id.clone(),
1021    };
1022    let unit = |animation: &Animated<f32>| {
1023        crate::animation::valid_scalar_values(animation, |value| (0.0..=1.0).contains(&value))
1024    };
1025    let shape_error = |issue| shape_error(composition, node, issue);
1026    if node.bypass && !node.op.has_inputs() {
1027        return Err(invalid());
1028    }
1029    let valid = match &node.op {
1030        NodeOp::Clip {} | NodeOp::Matte { .. } => true,
1031        NodeOp::Media { source_id, start } => {
1032            let visual = sources.get(source_id).is_some_and(|source| {
1033                matches!(
1034                    source.kind,
1035                    crate::MediaKind::Video
1036                        | crate::MediaKind::Image
1037                        | crate::MediaKind::Generated
1038                        | crate::MediaKind::Composition
1039                )
1040            });
1041            if !visual {
1042                return Err(ModelError::InvalidNodeSource {
1043                    composition: composition.id.clone(),
1044                    node: node.id.clone(),
1045                    source: source_id.clone(),
1046                });
1047            }
1048            start.ticks() >= 0
1049        }
1050        NodeOp::Generator { generator } => match generator.validate_on(canvas.0, canvas.1) {
1051            Ok(()) => true,
1052            Err(crate::GeneratorIssue::Shape(issue)) => return Err(shape_error(issue)),
1053            Err(crate::GeneratorIssue::Layout(issue)) => {
1054                return Err(layout_error(composition, node, issue));
1055            }
1056            Err(crate::GeneratorIssue::Invalid) => false,
1057        },
1058        NodeOp::Effect { effect, inputs, .. } => {
1059            effect.is_valid()
1060                && inputs.len() <= MAX_EFFECT_INPUTS
1061                && inputs
1062                    .keys()
1063                    .all(|name| crate::effect::valid_binding_name(name))
1064        }
1065        NodeOp::Transition {
1066            effect, progress, ..
1067        } => effect.is_valid() && unit(progress),
1068        NodeOp::Transform { transform, .. } => transform.validate(),
1069        NodeOp::Merge { layers } => {
1070            layers.len() <= MAX_MERGE_LAYERS && layers.iter().all(|layer| unit(&layer.opacity))
1071        }
1072        NodeOp::ShapeMask { masks, .. } => {
1073            crate::mask::validate_masks(masks).map_err(shape_error)?;
1074            masks.len() <= crate::MAX_CLIP_MASKS
1075        }
1076        NodeOp::Group {
1077            composition: target,
1078            inputs,
1079            controls,
1080        } => {
1081            let Some(target) = compositions.get(target) else {
1082                return Err(ModelError::UnknownGroupComposition {
1083                    composition: composition.id.clone(),
1084                    node: node.id.clone(),
1085                    target: target.clone(),
1086                });
1087            };
1088            inputs.len() == target.inputs.len()
1089                && controls.iter().all(|(name, value)| {
1090                    target.controls.iter().any(|control| &control.name == name)
1091                        && crate::effect::valid_param(value)
1092                })
1093        }
1094        NodeOp::GroupInput { index } => {
1095            usize::try_from(*index).is_ok_and(|index| index < composition.inputs.len())
1096        }
1097    };
1098    if !valid {
1099        return Err(invalid());
1100    }
1101    check_builtin_effects(composition, node, compositions)?;
1102    if let Some(effect) = node.op.effect()
1103        && let Some(resource) = effect
1104            .resources
1105            .values()
1106            .find(|resource| !effect_resources.contains(resource))
1107    {
1108        return Err(ModelError::UnknownNodeResource {
1109            composition: composition.id.clone(),
1110            node: node.id.clone(),
1111            resource: resource.clone(),
1112        });
1113    }
1114    Ok(())
1115}
1116
1117/// A node on a cycle, if any: the first, in document order, that a depth-first walk finds
1118/// on its own path.
1119fn cycle_member<'a>(
1120    composition: &'a Composition,
1121    positions: &std::collections::HashMap<&'a NodeId, usize>,
1122) -> Option<&'a NodeId> {
1123    #[derive(Clone, Copy, PartialEq)]
1124    enum Mark {
1125        New,
1126        Open,
1127        Done,
1128    }
1129    let nodes = &composition.nodes;
1130    let mut marks = vec![Mark::New; nodes.len()];
1131    for root in 0..nodes.len() {
1132        if marks[root] != Mark::New {
1133            continue;
1134        }
1135        // Each entry is a node and how many of its inputs have been walked.
1136        let mut stack = vec![(root, 0_usize)];
1137        marks[root] = Mark::Open;
1138        while let Some((current, next)) = stack.last_mut() {
1139            let inputs = nodes[*current].op.inputs();
1140            let Some(input) = inputs.get(*next) else {
1141                marks[*current] = Mark::Done;
1142                stack.pop();
1143                continue;
1144            };
1145            *next += 1;
1146            let Some(target) = input.node().and_then(|id| positions.get(id)) else {
1147                continue;
1148            };
1149            match marks[*target] {
1150                Mark::Open => return Some(&nodes[*target].id),
1151                Mark::New => {
1152                    marks[*target] = Mark::Open;
1153                    stack.push((*target, 0));
1154                }
1155                Mark::Done => {}
1156            }
1157        }
1158    }
1159    None
1160}
1161
1162#[cfg(test)]
1163#[path = "composition_tests.rs"]
1164mod tests;