Skip to main content

alpha2_eval/
index.rs

1//! The per-snapshot interval index that frame and audio evaluation query.
2//!
3//! The evaluator has no GPU, decoder, filesystem, clock or global state. A host builds an
4//! [`ActiveIndex`] once per immutable [`Project`] and may evaluate any timestamp on any thread.
5
6use crate::{EvalError, IndexedCaptions, IndexedClip, IndexedTransition, IntervalNode, build_tree};
7use alpha2_media::SourceId;
8use alpha2_model::{CompositionId, Project, ProjectId};
9use alpha2_time::TimeRange;
10
11/// A precomputed interval index for a validated project snapshot.
12#[derive(Clone, Debug)]
13pub struct ActiveIndex {
14    pub(crate) project_id: ProjectId,
15    pub(crate) nodes: Vec<IntervalNode>,
16    pub(crate) root: Option<usize>,
17    pub(crate) transitions: Vec<IndexedTransition>,
18    /// Caption tracks in track order.
19    pub(crate) captions: Vec<IndexedCaptions>,
20    /// The most clips active at any one instant.
21    pub(crate) max_active: usize,
22    /// The project's data sets and clips by id, for data bindings.
23    pub(crate) data: crate::DataIndex,
24    /// Whether the compositions together exceed [`crate::MAX_PLAN_BYTES`], so none draws.
25    pub(crate) plans_too_large: bool,
26}
27
28impl ActiveIndex {
29    /// The data index for sampling `project`'s timeline-time values; `project` must be the one
30    /// this index was built from.
31    #[must_use]
32    pub fn sample_context<'a>(
33        &'a self,
34        project: &'a alpha2_model::Project,
35    ) -> crate::SampleContext<'a> {
36        crate::SampleContext::timeline(project, &self.data)
37    }
38
39    /// The project's data sets and clips by id.
40    #[must_use]
41    pub const fn data(&self) -> &crate::DataIndex {
42        &self.data
43    }
44
45    /// Builds an immutable interval tree from a structurally valid project.
46    ///
47    /// # Errors
48    ///
49    /// Returns [`EvalError::InvalidProject`] when the model is invalid.
50    #[allow(clippy::too_many_lines)]
51    pub fn build(project: &Project) -> Result<Self, EvalError> {
52        project.validate().map_err(EvalError::InvalidProject)?;
53        let mut entries = Vec::new();
54        let mut transitions = Vec::new();
55        let matte_sources = project.timeline.matte_sources();
56        let lookup = crate::composition::Lookup::new(
57            &project.compositions,
58            &project.sources,
59            (project.settings.width, project.settings.height),
60        );
61        let (plans, source_plans, plans_too_large) = compile_plans(project, &lookup);
62        let sources = project
63            .sources
64            .iter()
65            .map(|source| (&source.id, source))
66            .collect::<std::collections::HashMap<_, _>>();
67        let generators = generator_plans(project);
68        for (track_order, track) in project.timeline.tracks.iter().enumerate() {
69            for (clip_order, clip) in track.clips.iter().enumerate() {
70                // Validation guarantees the source exists.
71                let source = sources.get(&clip.source_id).copied();
72                let source_is_audible = source.is_some_and(alpha2_model::MediaSource::is_audible);
73                let generator = source.and_then(|source| source.generator.clone());
74                // A composition source is planned only if the clip's own composition draws the clip.
75                let drawn = clip
76                    .composition
77                    .as_ref()
78                    .is_none_or(|reference| lookup.reads().draws_clip(&reference.id));
79                let source_composition = source
80                    .filter(|_| drawn)
81                    .and_then(|source| source_composition_of(source, &source_plans));
82                entries.push(IndexedClip {
83                    clip_id: clip.id.clone(),
84                    source_id: clip.source_id.clone(),
85                    track_id: track.id.clone(),
86                    track_kind: track.kind,
87                    timeline_range: clip.timeline_range,
88                    source_range: clip.source_range,
89                    time_map: clip.time_map,
90                    visual: clip.visual.clone(),
91                    // Validation guarantees the composition exists.
92                    composition: clip.composition.as_ref().and_then(|reference| {
93                        plans
94                            .get(&reference.id)
95                            .map(|plan| crate::IndexedComposition {
96                                plan: std::sync::Arc::clone(plan),
97                                reference: reference.clone(),
98                            })
99                    }),
100                    blend_mode: clip.blend_mode,
101                    cache: clip.cache,
102                    masks: clip.masks.clone(),
103                    matte: clip.matte.clone(),
104                    is_matte: matte_sources.contains(&clip.id),
105                    audio: clip.audio.clone(),
106                    source_is_audible,
107                    generator,
108                    plan: generators.get(&clip.source_id).cloned(),
109                    source_composition,
110                    track_order,
111                    clip_order,
112                });
113            }
114            transitions.extend(track.transitions.iter().enumerate().map(
115                |(list_order, transition)| IndexedTransition {
116                    from_clip: transition.from_clip.clone(),
117                    to_clip: transition.to_clip.clone(),
118                    timeline_range: transition.timeline_range,
119                    easing: transition.easing,
120                    effect: transition.effect.clone(),
121                    track_order,
122                    list_order,
123                },
124            ));
125        }
126        let captions = project
127            .timeline
128            .tracks
129            .iter()
130            .enumerate()
131            .filter_map(|(track_order, track)| {
132                track.captions.as_ref().map(|captions| {
133                    let mut shown = captions.clone();
134                    if shown.from_words.is_some() {
135                        shown.cues = crate::caption_cues(project, &track.id, captions)
136                            .map_err(EvalError::InvalidProject)?;
137                    }
138                    Ok(IndexedCaptions::new(track.id.clone(), track_order, shown))
139                })
140            })
141            .collect::<Result<_, EvalError>>()?;
142        entries.sort_unstable_by_key(|entry| {
143            (
144                entry.timeline_range.start(),
145                entry.track_order,
146                entry.clip_order,
147            )
148        });
149        let max_active = deepest_overlap(&entries);
150        let (nodes, root) = build_tree(entries);
151        transitions.sort_unstable_by_key(|transition| {
152            (
153                transition.timeline_range.start(),
154                transition.track_order,
155                transition.list_order,
156            )
157        });
158        Ok(Self {
159            project_id: project.id.clone(),
160            nodes,
161            root,
162            transitions,
163            captions,
164            max_active,
165            data: crate::DataIndex::new(project),
166            plans_too_large,
167        })
168    }
169
170    /// The errors [`crate::evaluate`] would return in `range` because a clip shows a composition
171    /// that cannot draw, one per clip, in the order the clips start. An export checks its range
172    /// with this before its first frame instead of failing at the frame that shows the clip. When
173    /// the compositions together exceed [`crate::MAX_PLAN_BYTES`] (see [`Self::plans_too_large`])
174    /// only the first is listed, since the cause is the whole document.
175    #[must_use]
176    pub fn plan_errors(&self, range: TimeRange) -> Vec<EvalError> {
177        let mut found = Vec::new();
178        for entry in self.nodes.iter().map(IntervalNode::entry) {
179            if entry.track_kind != alpha2_model::TrackKind::Video
180                || entry.timeline_range.intersection(range).is_none()
181            {
182                continue;
183            }
184            let own = entry
185                .composition
186                .as_ref()
187                .map(|indexed| (&indexed.reference.id, &indexed.plan));
188            let shown = entry
189                .source_composition
190                .as_ref()
191                .map(|(id, plan)| (id, plan));
192            if let Some((composition, Err(reason))) = own
193                .into_iter()
194                .chain(shown)
195                .map(|(id, plan)| (id, plan.as_ref().as_ref()))
196                .find(|(_, plan)| plan.is_err())
197            {
198                found.push((
199                    entry.timeline_range.start(),
200                    entry.track_order,
201                    EvalError::IncompleteComposition {
202                        clip: entry.clip_id.clone(),
203                        composition: composition.clone(),
204                        reason: reason.clone(),
205                    },
206                ));
207            }
208        }
209        found.sort_by_key(|(start, track, _)| (*start, *track));
210        if self.plans_too_large {
211            found.truncate(1);
212        }
213        found.into_iter().map(|(_, _, error)| error).collect()
214    }
215
216    /// Whether the project's compositions together exceed [`crate::MAX_PLAN_BYTES`], so none draws.
217    #[must_use]
218    pub const fn plans_too_large(&self) -> bool {
219        self.plans_too_large
220    }
221
222    /// Returns the project identity used to build this index.
223    #[must_use]
224    pub fn project_id(&self) -> &ProjectId {
225        &self.project_id
226    }
227
228    /// Returns the number of clips indexed.
229    #[must_use]
230    pub fn len(&self) -> usize {
231        self.nodes.len()
232    }
233
234    /// Returns whether the index has no clips.
235    #[must_use]
236    pub fn is_empty(&self) -> bool {
237        self.nodes.is_empty()
238    }
239
240    /// Every effect invocation the project can draw: steps of each compiled composition (once
241    /// each, in order of first use) and each transition.
242    pub fn effects(&self) -> impl Iterator<Item = &alpha2_model::ClipEffect> {
243        let mut seen = std::collections::HashSet::new();
244        let plans = self
245            .nodes
246            .iter()
247            .flat_map(|node| clip_plans(node.entry()))
248            .flatten()
249            .filter(|slot| seen.insert(std::sync::Arc::as_ptr(slot)))
250            .filter_map(|slot| slot.as_ref().as_ref().ok())
251            .collect::<Vec<_>>();
252        plans
253            .into_iter()
254            .flat_map(crate::CompositionPlan::effects)
255            .chain(self.transitions.iter().map(|transition| &transition.effect))
256    }
257
258    /// Peak number of concurrent host-source reads selected by `counted` in `range`, or 0.
259    ///
260    /// Each read (a clip's own source per [`crate::ActiveClip::needs_source`], or a media step of
261    /// its compositions) gets its own decoder cursor in [`crate::frame_needs`], so this is the
262    /// number of decoders active at once.
263    #[must_use]
264    pub fn peak_source_reads(
265        &self,
266        range: TimeRange,
267        mut counted: impl FnMut(&SourceId) -> bool,
268    ) -> usize {
269        // Keyed by the shared plan allocation so each composition is counted once.
270        let mut plan_reads = std::collections::HashMap::new();
271        let mut events = Vec::new();
272        for entry in self.nodes.iter().map(IntervalNode::entry) {
273            let Some(span) = entry.timeline_range.intersection(range) else {
274                continue;
275            };
276            let [composition, source_composition] = clip_plans(entry);
277            let mut reads = usize::from(draws_own_source(entry) && counted(&entry.source_id));
278            for slot in [composition, source_composition].into_iter().flatten() {
279                reads += *plan_reads
280                    .entry(std::sync::Arc::as_ptr(slot))
281                    .or_insert_with(|| {
282                        slot.as_ref().as_ref().map_or(0, |plan| {
283                            plan.steps
284                                .iter()
285                                .filter(|step| match &step.op {
286                                    crate::StepOp::Media { source_id, .. } => counted(source_id),
287                                    _ => false,
288                                })
289                                .count()
290                        })
291                    });
292            }
293            if reads > 0 {
294                let delta = isize::try_from(reads).unwrap_or(isize::MAX);
295                events.extend([(span.start(), delta), (span.end(), -delta)]);
296            }
297        }
298        // Half-open ranges: ends sort before starts at the same instant.
299        events.sort_unstable_by_key(|&(time, delta)| (time, delta.signum()));
300        let mut active = 0_usize;
301        let mut peak = 0;
302        for (_, delta) in events {
303            active = active.saturating_add_signed(delta);
304            peak = peak.max(active);
305        }
306        peak
307    }
308
309    /// Every host-source read selected by `counted` over `range`, in index order, with readers
310    /// named as in [`crate::frame_needs`]. These are the reads [`Self::peak_source_reads`] counts.
311    ///
312    /// A reader reads only inside its span, so a host can close its decoder once the span ends.
313    /// Within the span it may still skip frames (deduplicated needs, unused mattes).
314    #[must_use]
315    pub fn source_reads(
316        &self,
317        range: TimeRange,
318        mut counted: impl FnMut(&SourceId) -> bool,
319    ) -> Vec<SourceRead> {
320        let mut reads = Vec::new();
321        for entry in self.nodes.iter().map(IntervalNode::entry) {
322            let Some(span) = entry.timeline_range.intersection(range) else {
323                continue;
324            };
325            let read = |source_id: &SourceId, reader| SourceRead {
326                source_id: source_id.clone(),
327                clip_id: entry.clip_id.clone(),
328                reader,
329                span,
330            };
331            if draws_own_source(entry) && counted(&entry.source_id) {
332                reads.push(read(&entry.source_id, None));
333            }
334            let [composition, source_composition] = clip_plans(entry);
335            for (slot, of_source) in [(composition, false), (source_composition, true)] {
336                let Some(Ok(plan)) = slot.map(|slot| slot.as_ref().as_ref()) else {
337                    continue;
338                };
339                for step in &plan.steps {
340                    let crate::StepOp::Media { source_id, .. } = &step.op else {
341                        continue;
342                    };
343                    if !counted(source_id) {
344                        continue;
345                    }
346                    let reader = if of_source {
347                        alpha2_model::NodeId::new(format!("/{}", step.node)).ok()
348                    } else {
349                        Some(step.node.clone())
350                    };
351                    reads.push(read(source_id, reader));
352                }
353            }
354        }
355        reads
356    }
357}
358
359/// One reader of a source over an export range ([`ActiveIndex::source_reads`]).
360#[derive(Clone, Debug, Eq, PartialEq)]
361pub struct SourceRead {
362    /// The source read.
363    pub source_id: SourceId,
364    /// The clip that reads it or shows the reading composition.
365    pub clip_id: alpha2_model::ClipId,
366    /// The reading composition step as in [`crate::FrameNeed::reader`]; `None` for the clip.
367    pub reader: Option<alpha2_model::NodeId>,
368    /// Where on the timeline it may read.
369    pub span: TimeRange,
370}
371
372fn draws_own_source(entry: &IndexedClip) -> bool {
373    let [composition, source_composition] = clip_plans(entry);
374    entry.generator.is_none()
375        && source_composition.is_none()
376        && composition.is_none_or(|slot| {
377            slot.as_ref()
378                .as_ref()
379                .is_ok_and(crate::CompositionPlan::uses_clip)
380        })
381}
382
383/// The compiled compositions `entry` draws: its own, then its composition source's.
384fn clip_plans(entry: &IndexedClip) -> [Option<&PlanSlot>; 2] {
385    [
386        entry
387            .composition
388            .as_ref()
389            .map(|composition| &composition.plan),
390        entry.source_composition.as_ref().map(|(_, plan)| plan),
391    ]
392}
393
394type Plans<'a> = std::collections::HashMap<&'a CompositionId, PlanSlot>;
395
396/// Compiles each used composition once. Together they hold at most [`crate::MAX_PLAN_BYTES`];
397/// past that none draws, so the outcome does not depend on compile order.
398fn compile_plans<'a>(
399    project: &'a Project,
400    lookup: &crate::composition::Lookup<'a>,
401) -> (Plans<'a>, Plans<'a>, bool) {
402    let shown = project
403        .timeline
404        .tracks
405        .iter()
406        .flat_map(|track| &track.clips)
407        .filter_map(|clip| clip.composition.as_ref().map(|reference| &reference.id))
408        .collect::<std::collections::HashSet<_>>();
409    // The composition sources a clip draws, or a media node may read.
410    let sourced = project
411        .sources
412        .iter()
413        .filter_map(|source| source.composition.as_ref())
414        .collect::<std::collections::HashSet<_>>();
415    let mut budget = crate::composition::PlanBudget::new(crate::MAX_PLAN_BYTES);
416    let mut plans = Plans::new();
417    let mut source_plans = Plans::new();
418    let refused = std::sync::Arc::new(Err(crate::PlanError::TooLarge));
419    for composition in &project.compositions {
420        // Past the budget nothing draws, so nothing more is compiled.
421        if budget.exceeded() {
422            if shown.contains(&composition.id) {
423                plans.insert(&composition.id, std::sync::Arc::clone(&refused));
424            }
425            if sourced.contains(&composition.id) {
426                source_plans.insert(&composition.id, std::sync::Arc::clone(&refused));
427            }
428            continue;
429        }
430        if shown.contains(&composition.id) {
431            let plan =
432                crate::composition::plan_composition_within(composition, lookup, &mut budget);
433            plans.insert(&composition.id, std::sync::Arc::new(plan));
434        }
435        if sourced.contains(&composition.id) {
436            let plan = crate::composition::plan_source_composition_within(
437                composition,
438                lookup,
439                &mut budget,
440            );
441            source_plans.insert(&composition.id, std::sync::Arc::new(plan));
442        }
443    }
444    if budget.exceeded() {
445        for plan in plans.values_mut().chain(source_plans.values_mut()) {
446            *plan = std::sync::Arc::clone(&refused);
447        }
448    }
449    (plans, source_plans, budget.exceeded())
450}
451
452fn source_composition_of(
453    source: &alpha2_model::MediaSource,
454    plans: &Plans<'_>,
455) -> Option<(CompositionId, PlanSlot)> {
456    let id = source.composition.as_ref()?;
457    Some((id.clone(), std::sync::Arc::clone(plans.get(id)?)))
458}
459
460/// A compiled plan shared by every clip showing its composition, or the reason it cannot draw.
461pub(crate) type PlanSlot = std::sync::Arc<Result<crate::CompositionPlan, crate::PlanError>>;
462
463fn deepest_overlap(entries: &[IndexedClip]) -> usize {
464    // Half-open intervals: ends (-1) sort before starts (+1) at the same instant.
465    let mut edges: Vec<_> = entries
466        .iter()
467        .flat_map(|entry| {
468            [
469                (entry.timeline_range.start(), 1_i8),
470                (entry.timeline_range.end(), -1),
471            ]
472        })
473        .collect();
474    edges.sort_unstable();
475    let mut depth = 0_usize;
476    let mut deepest = 0;
477    for (_, step) in edges {
478        depth = depth.saturating_add_signed(isize::from(step));
479        deepest = deepest.max(depth);
480    }
481    deepest
482}
483
484/// Plans each shapes or layout source once, however many clips show it.
485fn generator_plans(
486    project: &Project,
487) -> std::collections::HashMap<&SourceId, std::sync::Arc<crate::GeneratorPlan>> {
488    project
489        .sources
490        .iter()
491        .filter_map(|source| {
492            let plan = crate::GeneratorPlan::new(
493                source.generator.as_ref()?,
494                (project.settings.width, project.settings.height),
495            )?;
496            Some((&source.id, std::sync::Arc::new(plan)))
497        })
498        .collect()
499}