// The edit engine.
//
// Everything here is exact. Times are big.Rat seconds; the only place a
// rational is ever quantised is when a timestamp is written to a file, and that
// quantisation is applied once, to the exactly-computed value, so it cannot
// accumulate.
//
// The pipeline, in order:
//
//  1. trim   - choose the retained window and rebase it to zero
//  2. cut    - remove a source range, closing the gap
//     speed  - scale a source range by 1/N
//  3. gap    - collapse every remaining dead pause down to --max
//  4. hold   - insert a freeze at a source instant
//
// Steps 1 and 2 are a single piecewise-linear map from source time to raw
// output time. Steps 3 and 4 are two step functions applied on top of it. All
// three are pure functions of the source time, so every event, marker and the
// timeline end are computed through exactly the same arithmetic.
package main

import (
	"fmt"
	"math/big"
	"sort"
)

// segment is one stretch of the source timeline with a constant time scale.
// Output duration of a segment is (End-Start)*Scale. Scale is 0 for a cut.
type segment struct {
	Start *big.Rat
	End   *big.Rat
	Scale *big.Rat
	Kind  string // "keep", "cut", "speed"
}

func (s segment) srcLen() *big.Rat { return rSub(s.End, s.Start) }
func (s segment) outLen() *big.Rat { return rMul(s.srcLen(), s.Scale) }

// gapCut records that everything at or after a raw output time is pulled
// earlier by Shift, because a dead pause was collapsed.
type gapCut struct {
	At    *big.Rat
	Shift *big.Rat
}

// holdMark is a freeze inserted at a source instant.
type holdMark struct {
	At  *big.Rat
	Dur *big.Rat
}

// mark is a region of the edited timeline worth drawing on a ruler.
type mark struct {
	Kind     string
	SrcStart *big.Rat
	SrcEnd   *big.Rat
	OutStart *big.Rat
	OutEnd   *big.Rat
	Factor   *big.Rat
}

type editPlan struct {
	Window   [2]*big.Rat // retained source window, after trim
	Segments []segment
	GapMax   *big.Rat // nil when no gap op
	GapCuts  []gapCut
	Holds    []holdMark
	RawEnd   *big.Rat // mapped end of the window, before gap and hold
	SpanEnd  *big.Rat // final timeline length
	Marks    []mark
	Identity bool // true when the plan changes nothing at all
}

type editResult struct {
	Plan      *editPlan
	Cast      *cast // the edited cast, ready to write
	Removed   int   // events dropped
	Kept      int   // source events retained
	Preludes  int   // synthetic events inserted
	PreludeAt []preludeReport
	SrcDur    *big.Rat
	OutDur    *big.Rat // timestamp of the last event
	OutSpan   *big.Rat // full timeline length
	Exact     bool     // every emitted timestamp is a whole microsecond
}

type preludeReport struct {
	SrcAt  *big.Rat
	OutAt  *big.Rat
	Bytes  []byte
	Before *termState
	After  *termState
}

// ---------------------------------------------------------------------------
// Building the plan
// ---------------------------------------------------------------------------

func buildPlan(c *cast, e *edl) (*editPlan, error) {
	if err := e.validate(); err != nil {
		return nil, err
	}
	srcEnd := c.timelineEnd()

	win := [2]*big.Rat{rZero(), rCopy(srcEnd)}
	for _, op := range e.Ops {
		if op.Kind != opTrim {
			continue
		}
		win[0] = rCopy(op.Start)
		if op.End != nil {
			win[1] = rCopy(op.End)
		}
	}
	if win[1].Cmp(win[0]) < 0 {
		return nil, fmt.Errorf("trim window %s-%s is empty", rString(win[0]), rString(win[1]))
	}

	p := &editPlan{Window: win}

	// Collect the range operations, clipped to the window.
	type clipped struct {
		op   edlOp
		s, e *big.Rat
	}
	var ranges []clipped
	for _, op := range e.Ops {
		switch op.Kind {
		case opCut, opSpeed:
			s := rMax(op.Start, win[0])
			en := rMin(op.End, win[1])
			if s.Cmp(en) >= 0 {
				return nil, fmt.Errorf("EDL %s: %s %s-%s lies outside the trim window %s-%s",
					op.where(), op.Kind, rString(op.Start), rString(op.End), rString(win[0]), rString(win[1]))
			}
			ranges = append(ranges, clipped{op, s, en})
		case opGap:
			p.GapMax = rCopy(op.Max)
		case opHold:
			if op.At.Cmp(win[0]) < 0 || op.At.Cmp(win[1]) > 0 {
				return nil, fmt.Errorf("EDL %s: hold at %s lies outside the trim window %s-%s",
					op.where(), rString(op.At), rString(win[0]), rString(win[1]))
			}
			p.Holds = append(p.Holds, holdMark{At: rCopy(op.At), Dur: rCopy(op.Dur)})
		}
	}
	sort.SliceStable(p.Holds, func(i, j int) bool { return p.Holds[i].At.Cmp(p.Holds[j].At) < 0 })

	// Boundaries: the window edges plus every clipped range edge.
	bounds := []*big.Rat{win[0], win[1]}
	for _, r := range ranges {
		bounds = append(bounds, r.s, r.e)
	}
	sort.Slice(bounds, func(i, j int) bool { return bounds[i].Cmp(bounds[j]) < 0 })

	scaleAt := func(a, b *big.Rat) (*big.Rat, string, *big.Rat) {
		mid := rMul(rAdd(a, b), big.NewRat(1, 2))
		for _, r := range ranges {
			if mid.Cmp(r.s) >= 0 && mid.Cmp(r.e) < 0 {
				if r.op.Kind == opCut {
					return rZero(), "cut", nil
				}
				return new(big.Rat).Inv(r.op.Factor), "speed", rCopy(r.op.Factor)
			}
		}
		return rCopy(ratOne), "keep", nil
	}

	for i := 1; i < len(bounds); i++ {
		a, b := bounds[i-1], bounds[i]
		if a.Cmp(b) >= 0 {
			continue
		}
		sc, kind, _ := scaleAt(a, b)
		p.Segments = append(p.Segments, segment{Start: rCopy(a), End: rCopy(b), Scale: sc, Kind: kind})
	}

	p.RawEnd = rZero()
	for _, s := range p.Segments {
		p.RawEnd = rAdd(p.RawEnd, s.outLen())
	}
	p.Identity = p.isIdentity(srcEnd)
	return p, nil
}

// isIdentity reports whether the plan leaves the timeline exactly as it was.
// An identity edit rewrites nothing at all, not even the footer, so reading a
// cast and writing it back produces the same bytes.
func (p *editPlan) isIdentity(srcEnd *big.Rat) bool {
	if p.GapMax != nil || len(p.Holds) > 0 {
		return false
	}
	if p.Window[0].Sign() != 0 || p.Window[1].Cmp(srcEnd) != 0 {
		return false
	}
	for _, s := range p.Segments {
		if s.Kind != "keep" {
			return false
		}
	}
	return true
}

// mapSrc maps a source time to a raw output time, before gap collapsing and
// hold insertion. Times before the window map to 0, times after it map to the
// end, and times inside a cut map to the cut's start.
func (p *editPlan) mapSrc(t *big.Rat) *big.Rat {
	out := rZero()
	for _, s := range p.Segments {
		if t.Cmp(s.Start) <= 0 {
			break
		}
		end := s.End
		if t.Cmp(end) < 0 {
			end = t
		}
		out = rAdd(out, rMul(rSub(end, s.Start), s.Scale))
	}
	return out
}

// inWindow reports whether a source event survives trim and cut.
func (p *editPlan) retains(t *big.Rat) bool {
	if t.Cmp(p.Window[0]) < 0 || t.Cmp(p.Window[1]) > 0 {
		return false
	}
	for _, s := range p.Segments {
		if s.Kind == "cut" && t.Cmp(s.Start) >= 0 && t.Cmp(s.End) < 0 {
			return false
		}
	}
	return true
}

func (p *editPlan) gapShiftAt(rawOut *big.Rat) *big.Rat {
	shift := rZero()
	for _, g := range p.GapCuts {
		if rawOut.Cmp(g.At) >= 0 {
			shift = g.Shift
		} else {
			break
		}
	}
	return rCopy(shift)
}

// holdShiftAt sums every hold strictly before a source time. A hold at exactly
// t freezes AFTER the frame at t, so the event at t itself is not pushed.
func (p *editPlan) holdShiftAt(src *big.Rat) *big.Rat {
	shift := rZero()
	for _, h := range p.Holds {
		if h.At.Cmp(src) < 0 {
			shift = rAdd(shift, h.Dur)
		}
	}
	return shift
}

func (p *editPlan) holdShiftTotal() *big.Rat {
	shift := rZero()
	for _, h := range p.Holds {
		shift = rAdd(shift, h.Dur)
	}
	return shift
}

// outAt is the final output time of a source instant: the piecewise map, minus
// collapsed dead air, plus inserted freezes.
func (p *editPlan) outAt(src *big.Rat) *big.Rat {
	raw := p.mapSrc(src)
	return rAdd(rSub(raw, p.gapShiftAt(raw)), p.holdShiftAt(src))
}

// integrate is the exact retained-and-scaled length of a source interval,
// computed by summing segment overlaps directly. It is deliberately a second,
// independent implementation of what mapSrc differences produce, and
// verifyTimeline cross-checks the two against each other on every apply.
func (p *editPlan) integrate(a, b *big.Rat) *big.Rat {
	total := rZero()
	for _, s := range p.Segments {
		lo := rMax(a, s.Start)
		hi := rMin(b, s.End)
		if lo.Cmp(hi) >= 0 {
			continue
		}
		total = rAdd(total, rMul(rSub(hi, lo), s.Scale))
	}
	return total
}

// ---------------------------------------------------------------------------
// Applying the plan
// ---------------------------------------------------------------------------

func applyEDL(c *cast, e *edl) (*editResult, error) {
	p, err := buildPlan(c, e)
	if err != nil {
		return nil, err
	}

	// Which source events survive.
	keep := make([]bool, len(c.Events))
	var rawTimes []*big.Rat
	for i, ev := range c.Events {
		keep[i] = p.retains(ev.T)
		if keep[i] {
			rawTimes = append(rawTimes, p.mapSrc(ev.T))
		}
	}

	// Step 3: collapse dead pauses. The virtual final point is the end of the
	// timeline, so trailing dead air is capped too.
	if p.GapMax != nil {
		points := append(append([]*big.Rat{}, rawTimes...), rCopy(p.RawEnd))
		prev := rZero()
		shift := rZero()
		for _, pt := range points {
			g := rSub(pt, prev)
			if g.Cmp(p.GapMax) > 0 {
				shift = rAdd(shift, rSub(g, p.GapMax))
				p.GapCuts = append(p.GapCuts, gapCut{At: rCopy(pt), Shift: rCopy(shift)})
			}
			prev = pt
		}
	}

	p.SpanEnd = rAdd(rSub(p.RawEnd, p.gapShiftAt(p.RawEnd)), p.holdShiftTotal())

	// Step 4 is folded into outAt. Now walk the source events in order,
	// feeding the terminal-state model and emitting preludes at every cut.
	st := newTermState(c.width(), c.height())
	var before *termState
	dropping := false

	out := &cast{
		Path:      c.Path,
		HeaderRaw: append([]byte(nil), c.HeaderRaw...),
		Header:    c.Header,
		FooterRaw: append([]byte(nil), c.FooterRaw...),
	}
	if c.FooterRaw == nil {
		out.FooterRaw = nil
	}
	if c.Footer != nil {
		f := *c.Footer
		out.Footer = &f
	}

	res := &editResult{Plan: p, SrcDur: c.duration()}

	flushPrelude := func(nextIdx int) {
		if !dropping || before == nil {
			return
		}
		dropping = false
		pre := prelude(before, st)
		bef, aft := before, st.clone()
		before = nil
		if pre == nil || nextIdx >= len(c.Events) {
			return
		}
		ev := c.Events[nextIdx]
		out.Events = append(out.Events, castEvent{
			T:      p.outAt(ev.T),
			Stream: "o",
			Data:   pre,
			Synth:  true,
			Src:    rCopy(ev.T),
		})
		res.Preludes++
		res.PreludeAt = append(res.PreludeAt, preludeReport{
			SrcAt: rCopy(ev.T), OutAt: p.outAt(ev.T), Bytes: pre, Before: bef, After: aft,
		})
	}

	for i, ev := range c.Events {
		if keep[i] {
			flushPrelude(i)
			st.feed(ev.Data)
			out.Events = append(out.Events, castEvent{
				T:      p.outAt(ev.T),
				Stream: ev.Stream,
				Data:   ev.Data,
				B64:    ev.B64,
				Src:    rCopy(ev.T),
			})
			res.Kept++
			continue
		}
		if !dropping {
			dropping = true
			before = st.clone()
		}
		st.feed(ev.Data)
		res.Removed++
	}
	// A dropped run at the very end is not given a prelude: there is no
	// surviving event left for it to fix up.

	res.Cast = out
	res.OutSpan = rCopy(p.SpanEnd)
	if n := len(out.Events); n > 0 {
		res.OutDur = rCopy(out.Events[n-1].T)
	} else {
		res.OutDur = rZero()
	}
	res.Exact = true
	for _, ev := range out.Events {
		if !rIsExactMicros(ev.T) {
			res.Exact = false
			break
		}
	}
	if err := verifyTimeline(res); err != nil {
		return nil, err
	}
	if !p.Identity {
		if err := out.setFooterDuration(res.OutSpan); err != nil {
			return nil, fmt.Errorf("cannot rewrite footer: %v", err)
		}
	}
	res.Cast = out
	return res, nil
}

// ---------------------------------------------------------------------------
// Invariants
// ---------------------------------------------------------------------------

// verifyTimeline asserts, exactly and with no epsilon, that
//
//   - no timestamp is negative,
//   - timestamps never go backwards,
//   - the duration equals the sum of the retained-and-scaled intervals,
//   - no event lands after the end of the timeline.
//
// It runs on every apply, not only in tests. A failure here is a bug in the
// engine and the edit is refused rather than written out.
func verifyTimeline(res *editResult) error {
	evs := res.Cast.Events
	sum := rZero()
	prev := rZero()
	for i, ev := range evs {
		if ev.T.Sign() < 0 {
			return fmt.Errorf("internal error: event %d has negative time %s", i, rString(ev.T))
		}
		d := rSub(ev.T, prev)
		if d.Sign() < 0 {
			return fmt.Errorf("internal error: event %d at %s goes backwards from %s", i, rString(ev.T), rString(prev))
		}
		sum = rAdd(sum, d)
		prev = ev.T
	}
	if sum.Cmp(res.OutDur) != 0 {
		return fmt.Errorf("internal error: duration %s does not equal the sum of intervals %s",
			res.OutDur.RatString(), sum.RatString())
	}
	if res.OutDur.Cmp(res.OutSpan) > 0 {
		return fmt.Errorf("internal error: last event at %s is past the end of the timeline %s",
			res.OutDur.RatString(), res.OutSpan.RatString())
	}

	// Cross-check every inter-event interval against an independent
	// integration of the scale function over the source interval.
	p := res.Plan
	prevSrc := rCopy(p.Window[0])
	prevOut := rZero()
	for i, ev := range evs {
		want := rSub(p.integrate(prevSrc, ev.Src), rSub(p.gapShiftAt(p.mapSrc(ev.Src)), p.gapShiftAt(p.mapSrc(prevSrc))))
		want = rAdd(want, rSub(p.holdShiftAt(ev.Src), p.holdShiftAt(prevSrc)))
		got := rSub(ev.T, prevOut)
		if want.Cmp(got) != 0 {
			return fmt.Errorf("internal error: interval before event %d is %s, but the retained-and-scaled source interval is %s",
				i, got.RatString(), want.RatString())
		}
		prevSrc, prevOut = ev.Src, ev.T
	}
	return nil
}

// ---------------------------------------------------------------------------
// Marks, for preview
// ---------------------------------------------------------------------------

func (p *editPlan) buildMarks() []mark {
	var out []mark
	for _, s := range p.Segments {
		switch s.Kind {
		case "cut":
			out = append(out, mark{
				Kind: "cut", SrcStart: s.Start, SrcEnd: s.End,
				OutStart: p.outAt(s.Start), OutEnd: p.outAt(s.Start),
			})
		case "speed":
			f := new(big.Rat).Inv(s.Scale)
			out = append(out, mark{
				Kind: "speed", SrcStart: s.Start, SrcEnd: s.End,
				OutStart: p.outAt(s.Start), OutEnd: p.outAt(s.End), Factor: f,
			})
		}
	}
	for _, h := range p.Holds {
		start := rAdd(rSub(p.mapSrc(h.At), p.gapShiftAt(p.mapSrc(h.At))), p.holdShiftAt(h.At))
		out = append(out, mark{
			Kind: "hold", SrcStart: h.At, SrcEnd: h.At,
			OutStart: start, OutEnd: rAdd(start, h.Dur),
		})
	}
	sort.SliceStable(out, func(i, j int) bool { return out[i].SrcStart.Cmp(out[j].SrcStart) < 0 })
	return out
}