Skip to main content

alpha2_eval/edit/
mod.rs

1//! The edit operations `remove_ranges`, `split_at` and `bake`, which apply data to a project once.
2//!
3//! Operations are named for primitives, never for features, and are pure: a project and a
4//! request in, a project and a report out, with no I/O. Clips are split so each part continues its
5//! source and time map, keyframes move with their clip or transition, timeline-anchored data and
6//! caption cues are cut and shifted, transitions whose cut point is removed are removed, and mattes
7//! and `via` bindings follow the part beside them or the edit is refused. Bus curves keep their
8//! shape across a cut. Before editing, `split_at` leaves out cuts it cannot make exactly and
9//! `remove_ranges` refuses them, so a valid request never ends as an invalid result. Kept moments
10//! render as before except for reversed parts off the frame grid and the sound at a loop wrap a cut
11//! turns into a part boundary. The result validates and is canonical.
12
13mod bake;
14#[cfg(test)]
15mod bake_tests;
16#[cfg(test)]
17mod clip_reference_tests;
18#[cfg(test)]
19mod corpus_tests;
20mod json;
21mod plan;
22#[cfg(test)]
23mod plan_tests;
24mod request;
25mod split;
26#[cfg(test)]
27mod surface_corpus_tests;
28#[cfg(test)]
29mod tests;
30
31pub use json::{EditFailure, EditedJson, apply_json};
32pub use request::{
33    BakeTarget, Created, DataRef, EditError, EditReport, EditRequest, Moved, RangeList, Ranges,
34    RawRange, Ripple, SkipReason, Skipped, Target, TimeList, Times,
35};
36
37use alpha2_model::{
38    Animated, Clip, ClipId, ClipReference, DataAnchor, DataValues, Project, TimelineOwner, Track,
39};
40use alpha2_time::{FrameRate, MediaTime, TimeRange};
41use std::collections::{BTreeSet, HashMap, HashSet};
42
43/// Applies `request` to `project`.
44///
45/// # Errors
46/// [`EditError`] for a request that names something the project lacks or does not fit the
47/// operation, and [`EditError::InvalidResult`] if the result fails validation.
48pub fn apply(project: &Project, request: &EditRequest) -> Result<(Project, EditReport), EditError> {
49    let (edited, report) = match request {
50        EditRequest::RemoveRanges {
51            ranges,
52            target,
53            ripple,
54            invert,
55            padding,
56            min_duration,
57        } => remove_ranges(
58            project,
59            ranges,
60            target,
61            *ripple,
62            *invert,
63            *padding,
64            *min_duration,
65        )?,
66        EditRequest::SplitAt { times, target } => split_at(project, times, target)?,
67        EditRequest::Bake { targets } => bake::bake(project, targets)?,
68    };
69    check_counts(&edited)?;
70    edited.validate().map_err(EditError::InvalidResult)?;
71    Ok((edited, report))
72}
73
74/// Refuses a result with more clips or caption cues on a track than a track holds.
75fn check_counts(edited: &Project) -> Result<(), EditError> {
76    let maximum = alpha2_model::MAX_CLIPS_PER_TRACK;
77    for track in &edited.timeline.tracks {
78        if track.clips.len() > maximum {
79            return Err(EditError::TooManyClips {
80                track: track.id.clone(),
81                found: track.clips.len(),
82                maximum,
83            });
84        }
85        if let Some(captions) = &track.captions
86            && captions.cues.len() > maximum
87        {
88            return Err(EditError::TooManyCues {
89                track: track.id.clone(),
90                found: Some(captions.cues.len()),
91                maximum,
92            });
93        }
94    }
95    Ok(())
96}
97
98/// The target clips as `(track position, clip)`, in document order.
99fn target_clips<'a>(
100    project: &'a Project,
101    target: &Target,
102) -> Result<Vec<(usize, &'a Clip)>, EditError> {
103    let clips = match target {
104        Target::Track(id) => {
105            let (position, track) = project
106                .timeline
107                .tracks
108                .iter()
109                .enumerate()
110                .find(|(_, track)| &track.id == id)
111                .ok_or_else(|| EditError::UnknownTarget(format!("track {id}")))?;
112            track
113                .clips
114                .iter()
115                .map(|clip| (position, clip))
116                .collect::<Vec<_>>()
117        }
118        Target::Clips(ids) => {
119            let mut found = Vec::with_capacity(ids.len());
120            for id in ids {
121                let entry = project
122                    .timeline
123                    .tracks
124                    .iter()
125                    .enumerate()
126                    .find_map(|(position, track)| {
127                        track
128                            .clips
129                            .iter()
130                            .find(|clip| &clip.id == id)
131                            .map(|clip| (position, clip))
132                    })
133                    .ok_or_else(|| EditError::UnknownTarget(format!("clip {id}")))?;
134                found.push(entry);
135            }
136            found
137        }
138    };
139    if clips.is_empty() {
140        return Err(EditError::EmptyTarget);
141    }
142    Ok(clips)
143}
144
145/// Intervals on an anchor, from a data set or a list.
146fn read_ranges(
147    project: &Project,
148    ranges: &Ranges,
149) -> Result<(DataAnchor, Vec<(MediaTime, MediaTime)>), EditError> {
150    match ranges {
151        Ranges::Data(DataRef { data }) => {
152            let set = project
153                .data
154                .iter()
155                .find(|set| &set.id == data)
156                .ok_or_else(|| EditError::UnknownData(data.clone()))?;
157            let DataValues::Intervals(intervals) = &set.values else {
158                return Err(EditError::WrongKind {
159                    data: data.clone(),
160                    kind: set.kind(),
161                });
162            };
163            Ok((
164                set.anchor.clone(),
165                intervals
166                    .iter()
167                    .map(|item| (item.start, item.end))
168                    .collect(),
169            ))
170        }
171        Ranges::List(RangeList { list, anchor }) => {
172            let anchor = anchor.clone().ok_or(EditError::MissingAnchor)?;
173            for (index, range) in list.iter().enumerate() {
174                if range.start > range.end {
175                    return Err(EditError::InvalidRange(index));
176                }
177            }
178            Ok((
179                anchor,
180                list.iter().map(|range| (range.start, range.end)).collect(),
181            ))
182        }
183    }
184}
185
186/// Sorted, merged, non-empty timeline ranges.
187fn union(mut ranges: Vec<(i64, i64)>) -> Vec<(i64, i64)> {
188    ranges.retain(|(start, end)| start < end);
189    ranges.sort_unstable();
190    let mut merged: Vec<(i64, i64)> = Vec::with_capacity(ranges.len());
191    for (start, end) in ranges {
192        match merged.last_mut() {
193            Some(last) if start <= last.1 => last.1 = last.1.max(end),
194            _ => merged.push((start, end)),
195        }
196    }
197    merged
198}
199
200/// The nearest project frame start to `tick`, ties to the earlier one.
201fn snap(tick: i64, rate: FrameRate) -> i64 {
202    let Some(frame) = rate.frame_at_or_before(MediaTime(tick)) else {
203        return tick;
204    };
205    let before = rate.frame_start(frame).map_or(tick, MediaTime::ticks);
206    let after = rate.frame_start(frame + 1).map_or(tick, MediaTime::ticks);
207    if after - tick < tick - before {
208        after
209    } else {
210        before
211    }
212}
213
214/// The timeline ranges `intervals` on `anchor` cover through the target clips.
215fn timeline_ranges(
216    project: &Project,
217    anchor: &DataAnchor,
218    intervals: &[(MediaTime, MediaTime)],
219    targets: &[(usize, &Clip)],
220) -> Vec<(i64, i64)> {
221    let mut ranges = Vec::new();
222    match anchor {
223        DataAnchor::Timeline => ranges.extend(
224            intervals
225                .iter()
226                .map(|(start, end)| (start.ticks().max(0), end.ticks())),
227        ),
228        DataAnchor::Source { source_id } => {
229            for (_, clip) in targets
230                .iter()
231                .filter(|(_, clip)| &clip.source_id == source_id)
232            {
233                for (start, end) in intervals {
234                    let mapped = crate::source_range_to_timeline(
235                        clip.timeline_range,
236                        clip.source_range,
237                        clip.time_map,
238                        project.settings.frame_rate,
239                        *start,
240                        *end,
241                    )
242                    .unwrap_or_default();
243                    ranges.extend(
244                        mapped
245                            .into_iter()
246                            .map(|range| (range.start().ticks(), range.end().ticks())),
247                    );
248                }
249            }
250        }
251    }
252    union(ranges)
253}
254
255#[allow(clippy::too_many_arguments, clippy::too_many_lines)]
256fn remove_ranges(
257    project: &Project,
258    ranges: &Ranges,
259    target: &Target,
260    ripple: Ripple,
261    invert: bool,
262    padding: MediaTime,
263    min_duration: MediaTime,
264) -> Result<(Project, EditReport), EditError> {
265    let targets = target_clips(project, target)?;
266    let (anchor, intervals) = read_ranges(project, ranges)?;
267    let rate = project.settings.frame_rate;
268    let mut removal = timeline_ranges(project, &anchor, &intervals, &targets);
269    if invert {
270        let start = targets
271            .iter()
272            .map(|(_, clip)| clip.timeline_range.start().ticks())
273            .min()
274            .unwrap_or(0);
275        let end = targets
276            .iter()
277            .map(|(_, clip)| clip.timeline_range.end().ticks())
278            .max()
279            .unwrap_or(0);
280        let mut complement = Vec::new();
281        let mut cursor = start;
282        for (from, to) in &removal {
283            if *from > cursor {
284                complement.push((cursor, (*from).min(end)));
285            }
286            cursor = cursor.max(*to);
287        }
288        if cursor < end {
289            complement.push((cursor, end));
290        }
291        removal = complement;
292    }
293    // Padding keeps material at each edge (a negative one widens, not before 0); cuts then land on
294    // the project's frame grid.
295    let removal = union(
296        removal
297            .into_iter()
298            .map(|(start, end)| ((start + padding.ticks()).max(0), end - padding.ticks()))
299            .filter(|(start, end)| end - start >= min_duration.ticks().max(1))
300            .map(|(start, end)| (snap(start, rate), snap(end, rate)))
301            .collect(),
302    );
303    let mut edited = project.clone();
304    let mut report = EditReport {
305        removed: removal
306            .iter()
307            .filter_map(|(start, end)| TimeRange::new(MediaTime(*start), MediaTime(*end)).ok())
308            .collect(),
309        ..EditReport::default()
310    };
311    if removal.is_empty() {
312        return Ok((edited, report));
313    }
314    let shifted_tracks: HashSet<usize> = match ripple {
315        Ripple::None => HashSet::new(),
316        Ripple::Track => targets.iter().map(|(position, _)| *position).collect(),
317        Ripple::Timeline => (0..project.timeline.tracks.len()).collect(),
318    };
319    let cut_clips: HashSet<&ClipId> = match ripple {
320        Ripple::None => targets.iter().map(|(_, clip)| &clip.id).collect(),
321        Ripple::Track | Ripple::Timeline => HashSet::new(),
322    };
323    let mut ids = split::IdPool::new(project);
324    let mut renamed = Parts::new();
325    let crossed = crossed_transitions(project, &removal, &shifted_tracks, &cut_clips);
326    let original_tracks = &project.timeline.tracks;
327    for (position, track) in edited.timeline.tracks.iter_mut().enumerate() {
328        let shifts = shifted_tracks.contains(&position);
329        let mut clips = Vec::with_capacity(track.clips.len());
330        for clip in &track.clips {
331            // A clip named by a crossed transition loses its overlap even when not targeted.
332            if !shifts && !cut_clips.contains(&clip.id) && !crossed.contains_key(&clip.id) {
333                clips.push(clip.clone());
334                continue;
335            }
336            let mut own = removal.clone();
337            own.extend(crossed.get(&clip.id).into_iter().flatten().copied());
338            let keep = kept_windows(clip.timeline_range, &union(own));
339            refuse_unsafe_cut(clip, &original_tracks[position], &keep, &removal)?;
340            let parts = split::parts(clip, &keep, &mut ids, &mut report.created);
341            let mut placed = Vec::with_capacity(parts.len());
342            for part in parts {
343                let delta = if shifts {
344                    shift_of(part.timeline_range.start().ticks(), &removal)
345                } else {
346                    0
347                };
348                placed.push((part.timeline_range, split::moved(part, delta)));
349            }
350            renamed.insert(
351                clip.id.clone(),
352                placed
353                    .iter()
354                    .map(|(old, part)| (*old, part.id.clone()))
355                    .collect(),
356            );
357            clips.extend(placed.into_iter().map(|(_, part)| part));
358        }
359        track.clips = clips;
360    }
361    let transition_spans =
362        retarget_transitions(&mut edited, project, &removal, &shifted_tracks, &renamed);
363    // Bus keys of every shifted track, and the master's when every track shifts.
364    edited.for_each_bus_value_mut(&mut |owner, _, value| {
365        let shifts = match owner {
366            TimelineOwner::Track { track, .. } => shifted_tracks.contains(&track),
367            _ => ripple == Ripple::Timeline,
368        };
369        if shifts {
370            shift_keys(value, &removal);
371        }
372    });
373    for (position, track) in edited.timeline.tracks.iter_mut().enumerate() {
374        if let Some(captions) = &mut track.captions
375            && shifted_tracks.contains(&position)
376        {
377            captions.cues = shift_cues(&captions.cues, &removal);
378        }
379    }
380    if ripple == Ripple::Timeline {
381        for set in &mut edited.data {
382            if set.anchor == DataAnchor::Timeline {
383                split::cut_data(set, &removal);
384            }
385        }
386    }
387    retarget_clip_references(&mut edited, project, &renamed, &transition_spans)?;
388    report.moved = moved_stretches(project, &removal, &shifted_tracks);
389    Ok((edited, report))
390}
391
392/// Refuses a removal that cuts `clip` (into the windows `keep`) inside one of its fades, or that
393/// leaves a loop piece boundary inside one of its transitions no removed range crosses.
394fn refuse_unsafe_cut(
395    clip: &Clip,
396    track: &Track,
397    keep: &[(i64, i64)],
398    removal: &[(i64, i64)],
399) -> Result<(), EditError> {
400    let (start, end) = (
401        clip.timeline_range.start().ticks(),
402        clip.timeline_range.end().ticks(),
403    );
404    if keep == [(start, end)] {
405        return Ok(());
406    }
407    let edge = keep
408        .iter()
409        .flat_map(|(from, to)| [*from, *to])
410        .find(|edge| plan::inside_fade(clip, *edge));
411    if let Some(edge) = edge {
412        return Err(EditError::InFade {
413            clip: clip.id.clone(),
414            time: MediaTime(edge),
415        });
416    }
417    let kept = |transition: &alpha2_model::ClipTransition| {
418        let range = transition.timeline_range;
419        !removal
420            .iter()
421            .any(|(from, to)| *from < range.end().ticks() && range.start().ticks() < *to)
422    };
423    match plan::loop_boundary_in_transition(clip, track, keep, kept) {
424        Some((_, boundary)) => Err(EditError::InTransition {
425            clip: clip.id.clone(),
426            time: MediaTime(boundary),
427        }),
428        None => Ok(()),
429    }
430}
431
432/// For each clip of a transition a removed range crosses, what it also loses so the two no longer
433/// overlap. The from-clip loses what follows the first cut inside the transition, and the to-clip
434/// what precedes the last.
435fn crossed_transitions(
436    project: &Project,
437    removal: &[(i64, i64)],
438    shifted: &HashSet<usize>,
439    cut: &HashSet<&ClipId>,
440) -> HashMap<ClipId, Vec<(i64, i64)>> {
441    let mut extra: HashMap<ClipId, Vec<(i64, i64)>> = HashMap::new();
442    for (position, track) in project.timeline.tracks.iter().enumerate() {
443        for transition in &track.transitions {
444            if !shifted.contains(&position)
445                && !cut.contains(&transition.from_clip)
446                && !cut.contains(&transition.to_clip)
447            {
448                continue;
449            }
450            let (start, end) = (
451                transition.timeline_range.start().ticks(),
452                transition.timeline_range.end().ticks(),
453            );
454            let inside = removal
455                .iter()
456                .filter(|(from, to)| *from < end && start < *to)
457                .collect::<Vec<_>>();
458            let (Some(first), Some(last)) = (inside.first(), inside.last()) else {
459                continue;
460            };
461            extra
462                .entry(transition.from_clip.clone())
463                .or_default()
464                .push((first.0.max(start), end));
465            extra
466                .entry(transition.to_clip.clone())
467                .or_default()
468                .push((start, last.1.min(end)));
469        }
470    }
471    extra
472}
473
474/// The windows of `range` outside every removed range.
475fn kept_windows(range: TimeRange, removal: &[(i64, i64)]) -> Vec<(i64, i64)> {
476    kept_windows_ticks(range.start().ticks(), range.end().ticks(), removal)
477}
478
479/// The windows of `start..end` outside every removed range.
480fn kept_windows_ticks(start: i64, end: i64, removal: &[(i64, i64)]) -> Vec<(i64, i64)> {
481    let mut windows = Vec::new();
482    let mut cursor = start;
483    for (from, to) in removal {
484        if *to <= cursor || *from >= end {
485            continue;
486        }
487        if *from > cursor {
488            windows.push((cursor, *from));
489        }
490        cursor = cursor.max(*to);
491    }
492    if cursor < end {
493        windows.push((cursor, end));
494    }
495    windows
496}
497
498/// How far a time at or after `tick` moves left, which is the removed length before it.
499fn shift_of(tick: i64, removal: &[(i64, i64)]) -> i64 {
500    removal
501        .iter()
502        .map(|(from, to)| {
503            if *to <= tick {
504                to - from
505            } else if *from < tick {
506                tick - from
507            } else {
508                0
509            }
510        })
511        .sum()
512}
513
514/// A kept time's new position, or `None` for a removed one.
515fn new_time(tick: i64, removal: &[(i64, i64)]) -> Option<i64> {
516    if removal
517        .iter()
518        .any(|(from, to)| (*from..*to).contains(&tick))
519    {
520        return None;
521    }
522    Some(tick - shift_of(tick, removal))
523}
524
525/// Cues trimmed where they cross a removed range, dropped when wholly inside one, and shifted;
526/// run times stay with the text they time.
527fn shift_cues(
528    cues: &[alpha2_model::CaptionCue],
529    removal: &[(i64, i64)],
530) -> Vec<alpha2_model::CaptionCue> {
531    let mut out = Vec::new();
532    for cue in cues {
533        let windows = kept_windows(cue.timeline_range, removal);
534        let (Some(first), Some(last)) = (windows.first(), windows.last()) else {
535            continue;
536        };
537        let start = first.0 - shift_of(first.0, removal);
538        let end = last.1 - 1 - shift_of(last.1 - 1, removal) + 1;
539        let Ok(range) = TimeRange::new(MediaTime(start), MediaTime(end.max(start))) else {
540            continue;
541        };
542        if range.is_empty() {
543            continue;
544        }
545        let mut cue = cue.clone();
546        let old_start = cue.timeline_range.start().ticks();
547        cue.timeline_range = range;
548        if let alpha2_model::TextContent::Runs(runs) = &mut cue.text {
549            for run in runs.iter_mut() {
550                run.time = run.time.and_then(|time| {
551                    let from = new_time(old_start + time.start.ticks(), removal).or_else(|| {
552                        windows
553                            .iter()
554                            .find(|(lo, _)| *lo > old_start + time.start.ticks())
555                            .map(|(lo, _)| lo - shift_of(*lo, removal))
556                    })?;
557                    let to_old = old_start + time.end.ticks();
558                    let to = new_time(to_old - 1, removal)
559                        .map(|tick| tick + 1)
560                        .or_else(|| {
561                            windows
562                                .iter()
563                                .rev()
564                                .find(|(_, hi)| *hi < to_old)
565                                .map(|(_, hi)| hi - shift_of(hi - 1, removal))
566                        })?;
567                    let (from, to) = (from - start, to - start);
568                    (from < to).then_some(alpha2_model::RunTime {
569                        start: MediaTime(from),
570                        end: MediaTime(to),
571                    })
572                });
573            }
574        }
575        alpha2_model::clip_runs(&mut cue);
576        out.push(cue);
577    }
578    out
579}
580
581/// Keyframes of a bus curve on a rippled timeline. Keys inside removed ranges go and the rest
582/// move; the value at each cut is keyed on both sides, a one-tick hold step across the cut. Every
583/// key takes the part of the old curve up to the next key, so kept moments sample as before.
584fn shift_keys(animation: &mut Animated<f32>, removal: &[(i64, i64)]) {
585    let Animated::Keyframes { keyframes } = animation else {
586        return;
587    };
588    let old = std::mem::take(keyframes);
589    // Each new key at its old time, with the old key it keeps (none for one a cut adds).
590    let mut at = old
591        .iter()
592        .enumerate()
593        .filter(|(_, key)| new_time(key.time.ticks(), removal).is_some())
594        .map(|(index, key)| (key.time.ticks(), Some(index)))
595        .collect::<Vec<_>>();
596    for (from, to) in removal {
597        if from - 1 - shift_of(from - 1, removal) >= 0 {
598            at.push((from - 1, None));
599        }
600        at.push((*to, None));
601    }
602    at.sort_by_key(|(tick, kept)| (*tick, kept.is_none()));
603    at.dedup_by_key(|(tick, _)| *tick);
604    let curve = Animated::Keyframes { keyframes: old };
605    let Animated::Keyframes { keyframes: old } = &curve else {
606        return;
607    };
608    let value =
609        |tick: i64| crate::sample_scalar(&curve, MediaTime(tick), &crate::SampleContext::NONE);
610    let mut keys = Vec::with_capacity(at.len());
611    for (position, (tick, kept)) in at.iter().enumerate() {
612        let next = at.get(position + 1).map(|(tick, _)| *tick);
613        let interpolation = match next {
614            Some(next)
615                if removal
616                    .iter()
617                    .any(|(from, to)| *tick < *from && *to <= next) =>
618            {
619                alpha2_model::Interpolation::Hold
620            }
621            Some(next) => part_of_curve(old, *tick, next).unwrap_or_else(|| {
622                kept.map_or(alpha2_model::Interpolation::Linear, |index| {
623                    old[index].interpolation
624                })
625            }),
626            None => kept.map_or(alpha2_model::Interpolation::Linear, |index| {
627                old[index].interpolation
628            }),
629        };
630        keys.push(alpha2_model::Keyframe {
631            time: MediaTime(tick - shift_of(*tick, removal)),
632            value: kept.map_or_else(|| value(*tick), |index| old[index].value),
633            interpolation,
634        });
635    }
636    *keyframes = keys;
637}
638
639/// The interpolation that shows the old curve from `from` to `to`, which lie in one segment, or
640/// `None` outside every segment, where the curve is constant.
641fn part_of_curve(
642    keys: &[alpha2_model::Keyframe<f32>],
643    from: i64,
644    to: i64,
645) -> Option<alpha2_model::Interpolation> {
646    let next = keys.partition_point(|key| key.time.ticks() <= from);
647    let (start, end) = (keys.get(next.checked_sub(1)?)?, keys.get(next)?);
648    let alpha2_model::Interpolation::CubicBezier(curve) = start.interpolation else {
649        return Some(start.interpolation);
650    };
651    let progress =
652        |tick: i64| crate::animation::interpolation_amount(start.time, end.time, MediaTime(tick));
653    if from == start.time.ticks() && to == end.time.ticks() {
654        return Some(start.interpolation);
655    }
656    // A part whose ends are equal shows a constant; the nearest exact form is a line.
657    Some(curve.between(progress(from), progress(to)).map_or(
658        alpha2_model::Interpolation::Linear,
659        alpha2_model::Interpolation::CubicBezier,
660    ))
661}
662
663/// The parts each processed clip became, as `(old range, new id)`. A clip removed whole has none.
664type Parts = HashMap<ClipId, Vec<(TimeRange, ClipId)>>;
665
666/// Transitions whose cut point is removed go; the rest name the parts that now hold them and
667/// move with their track. Returns each kept transition's old range, per track.
668fn retarget_transitions(
669    edited: &mut Project,
670    original: &Project,
671    removal: &[(i64, i64)],
672    shifted: &HashSet<usize>,
673    renamed: &Parts,
674) -> Vec<Vec<TimeRange>> {
675    let mut spans = Vec::with_capacity(edited.timeline.tracks.len());
676    for (position, track) in edited.timeline.tracks.iter_mut().enumerate() {
677        let before = &original.timeline.tracks[position].transitions;
678        let mut kept = Vec::with_capacity(before.len());
679        let mut old = Vec::with_capacity(before.len());
680        for transition in before {
681            let range = transition.timeline_range;
682            let crosses = removal
683                .iter()
684                .any(|(from, to)| *from < range.end().ticks() && range.start().ticks() < *to);
685            if crosses
686                && (shifted.contains(&position)
687                    || renamed.contains_key(&transition.from_clip)
688                    || renamed.contains_key(&transition.to_clip))
689            {
690                continue;
691            }
692            let owner = |clip: &ClipId| {
693                renamed.get(clip).map_or_else(
694                    || Some(clip.clone()),
695                    |parts| {
696                        parts
697                            .iter()
698                            .find(|(old, _)| {
699                                old.start() <= range.start() && range.end() <= old.end()
700                            })
701                            .map(|(_, id)| id.clone())
702                    },
703                )
704            };
705            let (Some(from), Some(to)) = (owner(&transition.from_clip), owner(&transition.to_clip))
706            else {
707                continue;
708            };
709            let delta = if shifted.contains(&position) {
710                shift_of(range.start().ticks(), removal)
711            } else {
712                0
713            };
714            let mut transition = transition.clone();
715            transition.from_clip = from;
716            transition.to_clip = to;
717            transition.for_each_timeline_value_mut(&mut |_, value| value.shift(-delta));
718            transition.timeline_range = TimeRange::new(
719                MediaTime(range.start().ticks() - delta),
720                MediaTime(range.end().ticks() - delta),
721            )
722            .unwrap_or(range);
723            kept.push(transition);
724            old.push(range);
725        }
726        track.transitions = kept;
727        spans.push(old);
728    }
729    spans
730}
731
732/// The part of `clip` a reference over the old `span` (`None`: the whole timeline) names, or
733/// `None`. One part must overlap the span; a matte over no part stays inactive on the first part.
734fn part_for(
735    clip: &ClipId,
736    span: Option<TimeRange>,
737    matte: bool,
738    renamed: &Parts,
739    old_ranges: &HashMap<&ClipId, TimeRange>,
740) -> Option<ClipId> {
741    let Some(parts) = renamed.get(clip) else {
742        return Some(clip.clone());
743    };
744    if let [(range, id)] = parts.as_slice()
745        && old_ranges.get(clip) == Some(range)
746    {
747        return Some(id.clone());
748    }
749    let mut over = parts.iter().filter(|(range, _)| {
750        span.is_none_or(|span| range.start() < span.end() && span.start() < range.end())
751    });
752    match (over.next(), over.next()) {
753        (Some((_, id)), None) => Some(id.clone()),
754        (None, _) if matte => parts.first().map(|(_, id)| id.clone()),
755        _ => None,
756    }
757}
758
759/// A [`TimelineOwner`] that outlives the walk, for naming it in a refusal.
760enum Owner {
761    Clip(ClipId),
762    Transition(usize, usize),
763    Track(usize),
764    Master,
765}
766
767impl Owner {
768    fn of(owner: TimelineOwner<'_>) -> Self {
769        match owner {
770            TimelineOwner::Clip { id, .. } => Self::Clip(id.clone()),
771            TimelineOwner::Transition { track, index, .. } => Self::Transition(track, index),
772            TimelineOwner::Track { track, .. } => Self::Track(track),
773            TimelineOwner::Master => Self::Master,
774        }
775    }
776
777    fn describe(&self, project: &Project) -> String {
778        match self {
779            Self::Clip(id) => format!("clip {id}"),
780            Self::Transition(track, index) => {
781                let transition = &project.timeline.tracks[*track].transitions[*index];
782                format!(
783                    "transition {} to {}",
784                    transition.from_clip, transition.to_clip
785                )
786            }
787            Self::Track(track) => format!("track {}", project.timeline.tracks[*track].id),
788            Self::Master => "the master bus".to_owned(),
789        }
790    }
791}
792
793/// Points mattes and `via` bindings at the part of a cut clip beside them, and refuses where no
794/// single part fits or where a matte part would be left unnamed, which would draw it.
795fn retarget_clip_references(
796    edited: &mut Project,
797    original: &Project,
798    renamed: &Parts,
799    transition_spans: &[Vec<TimeRange>],
800) -> Result<(), EditError> {
801    let original_clips = || {
802        original
803            .timeline
804            .tracks
805            .iter()
806            .flat_map(|track| &track.clips)
807    };
808    let old_ranges = original_clips()
809        .map(|clip| (&clip.id, clip.timeline_range))
810        .collect::<HashMap<_, _>>();
811    let part_ranges = renamed
812        .values()
813        .flatten()
814        .map(|(range, id)| (id, *range))
815        .collect::<HashMap<_, _>>();
816    let mut refused: Option<(ClipId, ClipReference, Owner)> = None;
817    edited.for_each_clip_reference_mut(&mut |owner, kind, clip| {
818        if refused.is_some() {
819            return;
820        }
821        let (span, own) = match owner {
822            TimelineOwner::Clip { id, range, .. } => (
823                Some(part_ranges.get(id).copied().unwrap_or(range)),
824                Some(id),
825            ),
826            TimelineOwner::Transition { track, index, .. } => {
827                (transition_spans[track].get(index).copied(), None)
828            }
829            TimelineOwner::Track { .. } | TimelineOwner::Master => (None, None),
830        };
831        let matte = match kind {
832            ClipReference::Matte => true,
833            // A binding through its own clip was renamed with the clip's part.
834            ClipReference::Via if own != Some(clip) => false,
835            _ => return,
836        };
837        match part_for(clip, span, matte, renamed, &old_ranges) {
838            Some(part) => *clip = part,
839            None => refused = Some((clip.clone(), kind, Owner::of(owner))),
840        }
841    });
842    match refused {
843        Some((clip, ClipReference::Matte, _)) => return Err(EditError::MatteSource(clip)),
844        Some((clip, _, owner)) => {
845            return Err(EditError::ReadThrough {
846                clip,
847                by: owner.describe(edited),
848            });
849        }
850        None => {}
851    }
852    let sources = original_clips()
853        .filter_map(|clip| clip.matte.as_ref().map(|matte| &matte.source))
854        .collect::<HashSet<_>>();
855    let named = edited
856        .timeline
857        .tracks
858        .iter()
859        .flat_map(|track| &track.clips)
860        .filter_map(|clip| clip.matte.as_ref().map(|matte| &matte.source))
861        .collect::<HashSet<_>>();
862    for clip in original_clips().filter(|clip| sources.contains(&clip.id)) {
863        let unnamed = renamed.get(&clip.id).map_or_else(
864            || !named.contains(&clip.id),
865            |parts| parts.iter().any(|(_, id)| !named.contains(id)),
866        );
867        if unnamed {
868            return Err(EditError::MatteSource(clip.id.clone()));
869        }
870    }
871    Ok(())
872}
873
874/// The kept stretches between removed ranges that moved, over every shifted track's extent.
875fn moved_stretches(
876    project: &Project,
877    removal: &[(i64, i64)],
878    shifted: &HashSet<usize>,
879) -> Vec<Moved> {
880    if shifted.is_empty() {
881        return Vec::new();
882    }
883    let end = project
884        .timeline
885        .tracks
886        .iter()
887        .enumerate()
888        .filter(|(position, _)| shifted.contains(position))
889        .flat_map(|(_, track)| {
890            track
891                .clips
892                .iter()
893                .map(|clip| clip.timeline_range.end().ticks())
894        })
895        .max()
896        .unwrap_or(0);
897    let mut moved = Vec::new();
898    for (index, (_, to)) in removal.iter().enumerate() {
899        let next = removal.get(index + 1).map_or(end, |(from, _)| *from);
900        if *to >= next {
901            continue;
902        }
903        let delta = shift_of(*to, removal);
904        if let (Ok(from), Ok(to)) = (
905            TimeRange::new(MediaTime(*to), MediaTime(next)),
906            TimeRange::new(MediaTime(to - delta), MediaTime(next - delta)),
907        ) {
908            moved.push(Moved { from, to });
909        }
910    }
911    moved
912}
913
914/// The timeline times `times` maps to through the target clips, on the project's frame grid.
915fn split_cuts(
916    project: &Project,
917    times: &Times,
918    targets: &[(usize, &Clip)],
919) -> Result<BTreeSet<i64>, EditError> {
920    let rate = project.settings.frame_rate;
921    let (anchor, instants) = match times {
922        Times::Data(DataRef { data }) => {
923            let set = project
924                .data
925                .iter()
926                .find(|set| &set.id == data)
927                .ok_or_else(|| EditError::UnknownData(data.clone()))?;
928            let DataValues::Intervals(intervals) = &set.values else {
929                return Err(EditError::WrongKind {
930                    data: data.clone(),
931                    kind: set.kind(),
932                });
933            };
934            (
935                set.anchor.clone(),
936                intervals.iter().map(|item| item.start).collect::<Vec<_>>(),
937            )
938        }
939        Times::List(TimeList { list, anchor }) => (
940            anchor.clone().ok_or(EditError::MissingAnchor)?,
941            list.clone(),
942        ),
943    };
944    let mut cuts: BTreeSet<i64> = BTreeSet::new();
945    for (_, clip) in targets {
946        match &anchor {
947            DataAnchor::Timeline => {
948                cuts.extend(instants.iter().map(|time| snap(time.ticks(), rate)));
949            }
950            DataAnchor::Source { source_id } if &clip.source_id == source_id => {
951                for instant in &instants {
952                    let mapped = crate::source_instant_to_timeline(
953                        clip.timeline_range,
954                        clip.source_range,
955                        clip.time_map,
956                        rate,
957                        *instant,
958                    )
959                    .unwrap_or_default();
960                    cuts.extend(mapped.into_iter().map(|time| snap(time.ticks(), rate)));
961                }
962            }
963            DataAnchor::Source { .. } => {}
964        }
965    }
966    Ok(cuts)
967}
968
969fn split_at(
970    project: &Project,
971    times: &Times,
972    target: &Target,
973) -> Result<(Project, EditReport), EditError> {
974    let targets = target_clips(project, target)?;
975    let cuts = split_cuts(project, times, &targets)?;
976    let mut planned = Vec::with_capacity(targets.len());
977    for (track, clip) in &targets {
978        let (start, end) = (
979            clip.timeline_range.start().ticks(),
980            clip.timeline_range.end().ticks(),
981        );
982        let cuts = cuts.range(start + 1..end).copied().collect::<BTreeSet<_>>();
983        if !cuts.is_empty()
984            && !planned
985                .iter()
986                .any(|entry: &plan::Planned<'_>| entry.clip.id == clip.id)
987        {
988            planned.push(plan::Planned {
989                track: *track,
990                clip,
991                cuts,
992            });
993        }
994    }
995    let mut edited = project.clone();
996    let mut report = EditReport::default();
997    let mut skipped = plan::skip_cuts(project, &mut edited, &mut planned);
998    skipped.sort_by_key(|(index, cut, _)| {
999        let entry = &planned[*index];
1000        let order = project.timeline.tracks[entry.track]
1001            .clips
1002            .iter()
1003            .position(|clip| clip.id == entry.clip.id);
1004        (entry.track, order, *cut)
1005    });
1006    report.skipped = skipped
1007        .into_iter()
1008        .map(|(index, cut, reason)| Skipped {
1009            clip: planned[index].clip.id.clone(),
1010            time: MediaTime(cut),
1011            reason,
1012        })
1013        .collect();
1014    let cut_by = planned
1015        .iter()
1016        .filter(|entry| !entry.cuts.is_empty())
1017        .map(|entry| (&entry.clip.id, &entry.cuts))
1018        .collect::<HashMap<_, _>>();
1019    let mut ids = split::IdPool::new(project);
1020    let mut renamed = HashMap::new();
1021    for track in &mut edited.timeline.tracks {
1022        let mut clips = Vec::with_capacity(track.clips.len());
1023        for clip in &track.clips {
1024            let Some(inside) = cut_by.get(&clip.id) else {
1025                clips.push(clip.clone());
1026                continue;
1027            };
1028            let (start, end) = (
1029                clip.timeline_range.start().ticks(),
1030                clip.timeline_range.end().ticks(),
1031            );
1032            let mut windows = Vec::with_capacity(inside.len() + 1);
1033            let mut cursor = start;
1034            for cut in *inside {
1035                windows.push((cursor, *cut));
1036                cursor = *cut;
1037            }
1038            windows.push((cursor, end));
1039            let parts = split::parts(clip, &windows, &mut ids, &mut report.created);
1040            renamed.insert(
1041                clip.id.clone(),
1042                parts
1043                    .iter()
1044                    .map(|part| (part.timeline_range, part.id.clone()))
1045                    .collect::<Vec<_>>(),
1046            );
1047            clips.extend(parts);
1048        }
1049        track.clips = clips;
1050    }
1051    let transition_spans =
1052        retarget_transitions(&mut edited, project, &[], &HashSet::new(), &renamed);
1053    retarget_clip_references(&mut edited, project, &renamed, &transition_spans)?;
1054    Ok((edited, report))
1055}