bazaar 3.5.3

//! Weave storage core algorithms.
//!
//! Port of the pure-logic core of `bzrformats/weave.py` plus the v5 on-disk
//! format reader/writer from `bzrformats/weavefile.py`. A weave is a single
//! flat sequence of [`WeaveEntry`] items: literal lines plus bracketed
//! insertion/deletion instructions. This module implements the annotation
//! walk (`extract`) against that representation, plus [`read_weave_v5`]
//! and [`write_weave_v5`] for the on-disk format. The Python class still
//! owns I/O, parent/name bookkeeping, and the higher-level VersionedFile
//! surface.

/// Magic header for the v5 weave file format.
pub const WEAVE_V5_FORMAT: &[u8] = b"# bzr weave file v5\n";

/// A deserialized weave file: per-version metadata plus the flat weave
/// instruction/line stream.
#[derive(Debug, Default, Clone, PartialEq, Eq)]
pub struct WeaveFile {
    pub parents: Vec<Vec<usize>>,
    pub sha1s: Vec<Vec<u8>>,
    pub names: Vec<Vec<u8>>,
    pub weave: Vec<WeaveEntry>,
}

/// Compute the sha1 hex digest of the concatenation of `lines`. Mirrors
/// `bzrformats.osutils.sha_strings`, which weave uses to checksum each
/// version's content.
pub fn sha_strings<L: AsRef<[u8]>>(lines: &[L]) -> Vec<u8> {
    use sha1::{Digest, Sha1};
    let mut hasher = Sha1::new();
    for line in lines {
        hasher.update(line.as_ref());
    }
    let digest = hasher.finalize();
    let mut hex = vec![0u8; digest.len() * 2];
    for (i, byte) in digest.iter().enumerate() {
        let high = byte >> 4;
        let low = byte & 0x0f;
        hex[i * 2] = if high < 10 {
            b'0' + high
        } else {
            b'a' + high - 10
        };
        hex[i * 2 + 1] = if low < 10 {
            b'0' + low
        } else {
            b'a' + low - 10
        };
    }
    hex
}

impl WeaveFile {
    /// Look up a version index by name. Mirrors `Weave._lookup` (linear
    /// scan of `_names`).
    pub fn lookup(&self, name: &[u8]) -> Option<usize> {
        self.names.iter().position(|n| n == name)
    }

    /// Number of versions in the weave.
    pub fn num_versions(&self) -> usize {
        self.parents.len()
    }

    /// Return the list of version names. Mirrors `Weave.versions`.
    pub fn versions(&self) -> Vec<Vec<u8>> {
        self.names.clone()
    }

    /// Whether `name` is a known version. Mirrors `Weave.has_version`
    /// (and `__contains__`).
    pub fn has_version(&self, name: &[u8]) -> bool {
        self.lookup(name).is_some()
    }

    /// Map version names to their stored sha1s. Unknown names error.
    /// Mirrors `Weave.get_sha1s`.
    pub fn get_sha1s<'a, I>(&self, version_ids: I) -> Result<Vec<(Vec<u8>, Vec<u8>)>, WeaveError>
    where
        I: IntoIterator<Item = &'a [u8]>,
    {
        let mut out = Vec::new();
        for v in version_ids {
            let idx = self
                .lookup(v)
                .ok_or_else(|| WeaveError::RevisionNotPresentByName(v.to_vec()))?;
            out.push((v.to_vec(), self.sha1s[idx].clone()));
        }
        Ok(out)
    }

    /// Return `(version_name, parent_names)` pairs for each known input.
    /// Unknown names are silently skipped, matching `Weave.get_parent_map`.
    pub fn get_parent_map<'a, I>(&self, version_ids: I) -> Vec<(Vec<u8>, Vec<Vec<u8>>)>
    where
        I: IntoIterator<Item = &'a [u8]>,
    {
        let mut out = Vec::new();
        for v in version_ids {
            if let Some(idx) = self.lookup(v) {
                let parents = self.parents[idx]
                    .iter()
                    .map(|&p| self.names[p].clone())
                    .collect();
                out.push((v.to_vec(), parents));
            }
        }
        out
    }

    /// Set of ancestor *names* for `version_ids`, sorted. Unknown names
    /// error. Mirrors `Weave.get_ancestry`.
    pub fn get_ancestry<'a, I>(&self, version_ids: I) -> Result<Vec<Vec<u8>>, WeaveError>
    where
        I: IntoIterator<Item = &'a [u8]>,
    {
        let mut indices = Vec::new();
        for v in version_ids {
            indices.push(
                self.lookup(v)
                    .ok_or_else(|| WeaveError::RevisionNotPresentByName(v.to_vec()))?,
            );
        }
        let included = inclusions(&self.parents, &indices);
        let mut names: Vec<Vec<u8>> = included.iter().map(|&i| self.names[i].clone()).collect();
        names.sort();
        Ok(names)
    }

    /// Subset check used by `_join`. `other_parents` must not contain any
    /// element absent from `my_parents`. Mirrors `Weave._compatible_parents`.
    pub fn compatible_parents(
        my_parents: &std::collections::HashSet<usize>,
        other_parents: &std::collections::HashSet<usize>,
    ) -> bool {
        other_parents.is_subset(my_parents)
    }

    /// Compute the sha1 of the lines making up `version` and verify it
    /// against the stored sha1. Mirrors `Weave.get_lines`.
    pub fn get_lines(&self, version: usize) -> Result<Vec<Vec<u8>>, WeaveError> {
        if version >= self.parents.len() {
            return Err(WeaveError::RevisionNotPresent(version));
        }
        let included = inclusions(&self.parents, &[version]);
        let extracted = extract(&self.weave, &included)?;
        let result: Vec<Vec<u8>> = extracted.iter().map(|e| e.text.to_vec()).collect();
        let measured = sha_strings(&result);
        let expected = &self.sha1s[version];
        if &measured != expected {
            return Err(WeaveError::InvalidChecksum {
                version,
                expected: expected.clone(),
                measured,
            });
        }
        Ok(result)
    }

    /// Return `(originating-version-name, line)` pairs for `version`.
    /// Mirrors `Weave.annotate`.
    pub fn annotate(&self, version: usize) -> Result<Vec<(Vec<u8>, Vec<u8>)>, WeaveError> {
        if version >= self.parents.len() {
            return Err(WeaveError::RevisionNotPresent(version));
        }
        let included = inclusions(&self.parents, &[version]);
        let extracted = extract(&self.weave, &included)?;
        Ok(extracted
            .into_iter()
            .map(|e| (self.names[e.origin].clone(), e.text.to_vec()))
            .collect())
    }

    /// Add a single text on top of the weave.
    ///
    /// Returns the index of the new version. Port of `Weave._add`.
    ///
    /// * `version_id`: symbolic name. If `None`, allocated as `b"sha1:" + sha1`.
    /// * `parents`: direct parent indices.
    /// * `sha1`: precomputed sha1 hex; if `None`, hashed from `lines`.
    /// * `nostore_sha`: if `Some` and equal to the new sha1, returns
    ///   `Err(WeaveError::ExistingContent)` without storing.
    pub fn add(
        &mut self,
        version_id: Option<&[u8]>,
        lines: &[Vec<u8>],
        parents: &[usize],
        sha1: Option<Vec<u8>>,
        nostore_sha: Option<&[u8]>,
    ) -> Result<usize, WeaveError> {
        let sha1 = sha1.unwrap_or_else(|| sha_strings(lines));
        if let Some(no) = nostore_sha {
            if no == sha1.as_slice() {
                return Err(WeaveError::ExistingContent);
            }
        }
        let owned_name: Vec<u8>;
        let version_id: &[u8] = match version_id {
            Some(v) => v,
            None => {
                owned_name = {
                    let mut s = b"sha1:".to_vec();
                    s.extend_from_slice(&sha1);
                    s
                };
                &owned_name
            }
        };

        if let Some(idx) = self.lookup(version_id) {
            return self.check_repeated_add(version_id, parents, &sha1, idx);
        }

        for &p in parents {
            if p >= self.parents.len() {
                return Err(WeaveError::RevisionNotPresent(p));
            }
        }

        let new_version = self.parents.len();
        self.parents.push(parents.to_vec());
        self.sha1s.push(sha1.clone());
        self.names.push(version_id.to_vec());

        if parents.is_empty() {
            // Special case: fresh root. Skip the diff and just append the
            // lines wrapped in a single insertion block.
            if !lines.is_empty() {
                self.weave.push(WeaveEntry::Control {
                    op: Instruction::InsertOpen,
                    version: new_version,
                });
                for line in lines {
                    self.weave.push(WeaveEntry::Line(line.clone()));
                }
                // InsertClose carries no meaningful version — the
                // bracket pairs by stack order, not by index. The on-disk
                // format reflects this (`}\n` with no version), and the
                // reader normalises to 0 here. Keep them aligned so a
                // round-trip via `write_weave_v5`/`read_weave_v5` is a
                // structural identity.
                self.weave.push(WeaveEntry::Control {
                    op: Instruction::InsertClose,
                    version: 0,
                });
            }
            return Ok(new_version);
        }

        if parents.len() == 1 && self.sha1s[parents[0]] == sha1 {
            // Single parent, identical text — no edits to record.
            return Ok(new_version);
        }

        let ancestors = inclusions(&self.parents, parents);
        let extracted = extract(&self.weave, &ancestors)?;

        // basis_lineno[i] = absolute index in self.weave of basis line i.
        // basis_lines[i]  = bytes of basis line i.
        let mut basis_lineno: Vec<usize> = extracted.iter().map(|e| e.lineno).collect();
        let basis_lines: Vec<&[u8]> = extracted.iter().map(|e| e.text).collect();

        // Identical merged text: nothing to record.
        if basis_lines.len() == lines.len()
            && basis_lines
                .iter()
                .zip(lines.iter())
                .all(|(a, b)| *a == b.as_slice())
        {
            return Ok(new_version);
        }

        // Sentinel: a virtual basis line at the end of the weave so the
        // diff can refer to "insert at the end".
        basis_lineno.push(self.weave.len());

        let basis_owned: Vec<Vec<u8>> = basis_lines.iter().map(|s| s.to_vec()).collect();
        let mut sm = patiencediff::SequenceMatcher::new(&basis_owned, lines);
        let opcodes = sm.get_opcodes();

        // `offset` tracks how many entries have been spliced into self.weave
        // since the start of this loop, so the next i1/i2 (which were
        // computed against the *pre-mutation* layout) can be translated to
        // the current layout.
        let mut offset: isize = 0;
        for op in opcodes {
            if matches!(op, patiencediff::Opcode::Equal(_, _, _, _)) {
                continue;
            }
            let i1_basis = op.a_start();
            let i2_basis = op.a_end();
            let j1 = op.b_start();
            let j2 = op.b_end();
            let i1 = basis_lineno[i1_basis];
            let i2 = basis_lineno[i2_basis];

            // Apply deletion bracket first: insert `[` before line i1 and
            // `]` after line i2-1, both in *current* coordinates.
            if i1 != i2 {
                let pos1 = (i1 as isize + offset) as usize;
                self.weave.insert(
                    pos1,
                    WeaveEntry::Control {
                        op: Instruction::DeleteOpen,
                        version: new_version,
                    },
                );
                let pos2 = (i2 as isize + offset + 1) as usize;
                self.weave.insert(
                    pos2,
                    WeaveEntry::Control {
                        op: Instruction::DeleteClose,
                        version: new_version,
                    },
                );
                offset += 2;
            }

            if j1 != j2 {
                // Insert the new lines wrapped in `{`/`}` after the (now
                // bracketed) deletion region.
                let i = (i2 as isize + offset) as usize;
                let mut splice: Vec<WeaveEntry> = Vec::with_capacity(j2 - j1 + 2);
                splice.push(WeaveEntry::Control {
                    op: Instruction::InsertOpen,
                    version: new_version,
                });
                for line in &lines[j1..j2] {
                    splice.push(WeaveEntry::Line(line.clone()));
                }
                splice.push(WeaveEntry::Control {
                    op: Instruction::InsertClose,
                    version: 0,
                });
                let added = splice.len();
                let tail = self.weave.split_off(i);
                self.weave.extend(splice);
                self.weave.extend(tail);
                offset += added as isize;
            }
        }

        Ok(new_version)
    }

    fn check_repeated_add(
        &self,
        name: &[u8],
        parents: &[usize],
        sha1: &[u8],
        idx: usize,
    ) -> Result<usize, WeaveError> {
        let mut existing = self.parents[idx].clone();
        existing.sort_unstable();
        let mut requested = parents.to_vec();
        requested.sort_unstable();
        if existing != requested || self.sha1s[idx] != sha1 {
            return Err(WeaveError::RevisionAlreadyPresent(name.to_vec()));
        }
        Ok(idx)
    }

    /// Add a single text addressed by parent *names* rather than indices.
    /// Mirrors the high-level `Weave.add_lines` entry point: looks up each
    /// parent name, errors with `RevisionNotPresentByName` if any parent is
    /// unknown, and otherwise delegates to [`WeaveFile::add`].
    pub fn add_lines(
        &mut self,
        version_id: &[u8],
        parent_names: &[&[u8]],
        lines: &[Vec<u8>],
        sha1: Option<Vec<u8>>,
        nostore_sha: Option<&[u8]>,
    ) -> Result<usize, WeaveError> {
        let mut parent_idxs = Vec::with_capacity(parent_names.len());
        for name in parent_names {
            parent_idxs.push(
                self.lookup(name)
                    .ok_or_else(|| WeaveError::RevisionNotPresentByName(name.to_vec()))?,
            );
        }
        self.add(Some(version_id), lines, &parent_idxs, sha1, nostore_sha)
    }

    /// Yield every line that is inserted by, or present in, the given set of
    /// versions. Lines are returned with a trailing newline appended if they
    /// don't already have one. Mirrors `Weave.iter_lines_added_or_present_in_versions`.
    ///
    /// `version_names` is interpreted as a set; `None` means "all versions".
    /// Each yielded entry is `(line_with_eol, inserted_version_name)`.
    pub fn iter_lines_added_or_present_in_versions<'a, I>(
        &self,
        version_names: Option<I>,
    ) -> Result<impl Iterator<Item = (Vec<u8>, Vec<u8>)> + '_, WeaveError>
    where
        I: IntoIterator<Item = &'a [u8]>,
    {
        // Build the set of insert-version *indices* we care about.
        let included: std::collections::HashSet<usize> = match version_names {
            None => (0..self.parents.len()).collect(),
            Some(iter) => {
                let mut s = std::collections::HashSet::new();
                for name in iter {
                    if let Some(idx) = self.lookup(name) {
                        s.insert(idx);
                    }
                    // Unknown names are silently dropped, matching the Python
                    // contract (the set is filtered against actually-walked
                    // insert versions).
                }
                s
            }
        };

        // walk_internal is a fallible single-pass scan over the whole
        // weave (shared with plan_merge/annotate), so the structural
        // walk happens up front. Line construction — copying the text,
        // appending the trailing newline, cloning the version name — is
        // deferred to iteration, which is the per-item cost callers care
        // about.
        let walked = walk_internal(&self.weave)?;
        Ok(walked.into_iter().filter_map(move |w| {
            if !included.contains(&w.insert) {
                return None;
            }
            let mut line = w.text.to_vec();
            if !line.ends_with(b"\n") {
                line.push(b'\n');
            }
            Some((line, self.names[w.insert].clone()))
        }))
    }

    /// Three-way merge plan between `ver_a` and `ver_b`. Each yielded
    /// entry is one of: `killed-base`, `killed-both`, `killed-a`,
    /// `killed-b`, `unchanged`, `new-a`, `new-b`, `ghost-a`, `ghost-b`,
    /// `irrelevant`. Mirrors `Weave.plan_merge`.
    pub fn plan_merge(
        &self,
        ver_a: &[u8],
        ver_b: &[u8],
    ) -> Result<Vec<(PlanMergeState, Vec<u8>)>, WeaveError> {
        let idx_a = self
            .lookup(ver_a)
            .ok_or_else(|| WeaveError::RevisionNotPresentByName(ver_a.to_vec()))?;
        let idx_b = self
            .lookup(ver_b)
            .ok_or_else(|| WeaveError::RevisionNotPresentByName(ver_b.to_vec()))?;

        let inc_a = inclusions(&self.parents, &[idx_a]);
        let inc_b = inclusions(&self.parents, &[idx_b]);
        let inc_c: std::collections::HashSet<usize> = inc_a.intersection(&inc_b).copied().collect();

        let walked = walk_internal(&self.weave)?;
        let mut out = Vec::new();
        for w in walked {
            let deletes_hit_c = w.deletes.iter().any(|d| inc_c.contains(d));
            let state = if deletes_hit_c {
                PlanMergeState::KilledBase
            } else if inc_c.contains(&w.insert) {
                let killed_a = w.deletes.iter().any(|d| inc_a.contains(d));
                let killed_b = w.deletes.iter().any(|d| inc_b.contains(d));
                match (killed_a, killed_b) {
                    (true, true) => PlanMergeState::KilledBoth,
                    (true, false) => PlanMergeState::KilledA,
                    (false, true) => PlanMergeState::KilledB,
                    (false, false) => PlanMergeState::Unchanged,
                }
            } else if inc_a.contains(&w.insert) {
                if w.deletes.iter().any(|d| inc_a.contains(d)) {
                    PlanMergeState::GhostA
                } else {
                    PlanMergeState::NewA
                }
            } else if inc_b.contains(&w.insert) {
                if w.deletes.iter().any(|d| inc_b.contains(d)) {
                    PlanMergeState::GhostB
                } else {
                    PlanMergeState::NewB
                }
            } else {
                PlanMergeState::Irrelevant
            };
            out.push((state, w.text.to_vec()));
        }
        Ok(out)
    }

    /// Internal consistency check. Verifies parent indices are acyclic
    /// (each parent strictly less than its child), recomputes ancestry
    /// from scratch and compares to `get_ancestry`, then walks the weave
    /// accumulating per-version sha1s and compares to the stored sha1s.
    /// Mirrors `Weave.check`.
    pub fn check(&self) -> Result<(), WeaveError> {
        use sha1::{Digest, Sha1};

        let nv = self.num_versions();
        for v in 0..nv {
            if let Some(&max) = self.parents[v].iter().max() {
                if max >= v {
                    return Err(WeaveError::Acyclic { version: v, max });
                }
            }
        }

        // Per-version inclusion sets (by name) built incrementally.
        let mut inclusions_by_name: std::collections::HashMap<
            Vec<u8>,
            std::collections::HashSet<Vec<u8>>,
        > = std::collections::HashMap::with_capacity(nv);
        let mut hashers: std::collections::HashMap<Vec<u8>, Sha1> =
            std::collections::HashMap::with_capacity(nv);
        for v in 0..nv {
            let name = &self.names[v];
            let mut new_inc: std::collections::HashSet<Vec<u8>> = std::collections::HashSet::new();
            new_inc.insert(name.clone());
            for &p in &self.parents[v] {
                let parent_name = &self.names[p];
                if let Some(parent_inc) = inclusions_by_name.get(parent_name) {
                    new_inc.extend(parent_inc.iter().cloned());
                }
            }
            // Cross-check against get_ancestry, which derives the same set
            // through the inclusions() helper. If they disagree, the
            // parent table is inconsistent in some way we missed.
            let computed = self
                .get_ancestry(std::iter::once(name.as_slice()))?
                .into_iter()
                .collect::<std::collections::HashSet<_>>();
            if computed != new_inc {
                return Err(WeaveError::AncestryMismatch(name.clone()));
            }
            inclusions_by_name.insert(name.clone(), new_inc);
            hashers.insert(name.clone(), Sha1::new());
        }

        for w in walk_internal(&self.weave)? {
            let insert_name = &self.names[w.insert];
            let delete_names: Vec<&[u8]> = w
                .deletes
                .iter()
                .map(|&d| self.names[d].as_slice())
                .collect();
            for v in 0..nv {
                let name = &self.names[v];
                let inc = &inclusions_by_name[name];
                if !inc.contains(insert_name) {
                    continue;
                }
                if delete_names.iter().any(|d| inc.contains(*d)) {
                    continue;
                }
                hashers.get_mut(name).expect("seeded above").update(w.text);
            }
        }

        for v in 0..nv {
            let name = &self.names[v];
            let digest = hashers.remove(name).expect("seeded above").finalize();
            let mut hex = vec![0u8; digest.len() * 2];
            for (i, byte) in digest.iter().enumerate() {
                let high = byte >> 4;
                let low = byte & 0x0f;
                hex[i * 2] = if high < 10 {
                    b'0' + high
                } else {
                    b'a' + high - 10
                };
                hex[i * 2 + 1] = if low < 10 {
                    b'0' + low
                } else {
                    b'a' + low - 10
                };
            }
            if hex != self.sha1s[v] {
                return Err(WeaveError::InvalidChecksum {
                    version: v,
                    expected: self.sha1s[v].clone(),
                    measured: hex,
                });
            }
        }
        Ok(())
    }

    /// Translate parent indices in `other` to parent indices in `self`,
    /// looking up by version name. Errors if any of the parents are
    /// missing from `self`. Mirrors `Weave._imported_parents`.
    pub fn imported_parents(
        &self,
        other: &WeaveFile,
        other_idx: usize,
    ) -> Result<Vec<usize>, WeaveError> {
        let mut new_parents = Vec::with_capacity(other.parents[other_idx].len());
        for &parent_idx in &other.parents[other_idx] {
            let parent_name = &other.names[parent_idx];
            let mapped = self
                .lookup(parent_name)
                .ok_or_else(|| WeaveError::MissingParent {
                    parent: parent_name.clone(),
                    child: other.names[other_idx].clone(),
                })?;
            new_parents.push(mapped);
        }
        Ok(new_parents)
    }

    /// Cross-check that a version `name` shared between `self` and `other`
    /// has matching sha1s and compatible (subset-wise) parent sets.
    /// Returns `Ok(true)` if the version exists in `self` and is
    /// consistent, `Ok(false)` if not present in `self`, or
    /// `Err(TextDiffers | ParentMismatch)` on inconsistency. Mirrors
    /// `Weave._check_version_consistent`.
    pub fn check_version_consistent(
        &self,
        other: &WeaveFile,
        other_idx: usize,
        name: &[u8],
    ) -> Result<bool, WeaveError> {
        let this_idx = match self.lookup(name) {
            None => return Ok(false),
            Some(i) => i,
        };
        if self.sha1s[this_idx] != other.sha1s[other_idx] {
            return Err(WeaveError::TextDiffers(name.to_vec()));
        }
        let self_parents: std::collections::HashSet<Vec<u8>> = self.parents[this_idx]
            .iter()
            .map(|&p| self.names[p].clone())
            .collect();
        let other_parents: std::collections::HashSet<Vec<u8>> = other.parents[other_idx]
            .iter()
            .map(|&p| other.names[p].clone())
            .collect();
        if !other_parents.is_subset(&self_parents) {
            return Err(WeaveError::ParentMismatch {
                version: name.to_vec(),
                a: self_parents.into_iter().collect(),
                b: other_parents.into_iter().collect(),
            });
        }
        Ok(true)
    }
}

/// One state in a [`WeaveFile::plan_merge`] result.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum PlanMergeState {
    KilledBase,
    KilledBoth,
    KilledA,
    KilledB,
    Unchanged,
    NewA,
    NewB,
    GhostA,
    GhostB,
    Irrelevant,
}

impl PlanMergeState {
    /// String tag matching the Python `Weave.plan_merge` yields
    /// (e.g. `b"killed-a"`).
    pub fn tag(self) -> &'static [u8] {
        match self {
            PlanMergeState::KilledBase => b"killed-base",
            PlanMergeState::KilledBoth => b"killed-both",
            PlanMergeState::KilledA => b"killed-a",
            PlanMergeState::KilledB => b"killed-b",
            PlanMergeState::Unchanged => b"unchanged",
            PlanMergeState::NewA => b"new-a",
            PlanMergeState::NewB => b"new-b",
            PlanMergeState::GhostA => b"ghost-a",
            PlanMergeState::GhostB => b"ghost-b",
            PlanMergeState::Irrelevant => b"irrelevant",
        }
    }
}

/// Apply one of the documented orderings to a list of version names
/// against `wf`'s parent table, returning the same names re-ordered.
/// Unknown names are appended at the end in their original order, to
/// match `Weave.get_record_stream`'s
/// `set(versions).difference(set(parents))` fallback.
///
/// `ordering` is one of:
///
/// * `"unordered"` — input order, unchanged
/// * `"topological"` — parents before their children
/// * `"groupcompress"` — reverse-topological, grouped by key prefix
///
/// Returns `None` if `ordering` isn't recognised.
pub fn order_record_stream(
    wf: &WeaveFile,
    names: &[Vec<u8>],
    ordering: &str,
) -> Option<Vec<Vec<u8>>> {
    use vcs_graph::tsort::TopoSorter;

    let mut known = Vec::new();
    let mut unknown = Vec::new();
    for name in names {
        if wf.lookup(name).is_some() {
            known.push(name.clone());
        } else {
            unknown.push(name.clone());
        }
    }

    match ordering {
        "unordered" => Some(names.to_vec()),
        "topological" => {
            let pairs: Vec<(Vec<u8>, Vec<Vec<u8>>)> = known
                .iter()
                .map(|name| {
                    let idx = wf.lookup(name).expect("known by construction");
                    let parents = wf.parents[idx]
                        .iter()
                        .map(|&p| wf.names[p].clone())
                        .collect();
                    (name.clone(), parents)
                })
                .collect();
            let mut sorter = TopoSorter::new(pairs.into_iter());
            let mut sorted = sorter.sorted().expect("acyclic by invariant");
            sorted.extend(unknown);
            Some(sorted)
        }
        "groupcompress" => {
            let parent_map: Vec<(Vec<Vec<u8>>, Vec<Vec<Vec<u8>>>)> = known
                .iter()
                .map(|name| {
                    let idx = wf.lookup(name).expect("known by construction");
                    let key = vec![name.clone()];
                    let parents: Vec<Vec<Vec<u8>>> = wf.parents[idx]
                        .iter()
                        .map(|&p| vec![wf.names[p].clone()])
                        .collect();
                    (key, parents)
                })
                .collect();
            let mut out: Vec<Vec<u8>> = crate::groupcompress::sort::sort_gc_optimal(parent_map)
                .into_iter()
                .map(|key| key.into_iter().next().expect("single-segment key"))
                .collect();
            out.extend(unknown);
            Some(out)
        }
        _ => None,
    }
}

/// Combine two weaves into a single weave that contains every version
/// from both inputs, with parent sets that are the union of the parent
/// sets in `wa` and `wb`. Mirrors `bzrformats.weave._reweave`.
///
/// Errors out with `WeaveError::TextDiffers` if any shared version has
/// different content in the two inputs.
pub fn reweave(wa: &WeaveFile, wb: &WeaveFile) -> Result<WeaveFile, WeaveError> {
    use vcs_graph::tsort::TopoSorter;

    // Build combined parent graph: name -> set(parent_names).
    // Iteration order matches the Python implementation: wa first then wb,
    // and within each weave the existing version order.
    let mut combined: std::collections::BTreeMap<Vec<u8>, std::collections::BTreeSet<Vec<u8>>> =
        std::collections::BTreeMap::new();
    for w in [wa, wb] {
        for (idx, name) in w.names.iter().enumerate() {
            let entry = combined.entry(name.clone()).or_default();
            for &p in &w.parents[idx] {
                entry.insert(w.names[p].clone());
            }
        }
    }

    // Topo-sort by parent graph.
    let pairs: Vec<(Vec<u8>, Vec<Vec<u8>>)> = combined
        .iter()
        .map(|(k, v)| (k.clone(), v.iter().cloned().collect()))
        .collect();
    let mut sorter = TopoSorter::new(pairs.into_iter());
    let order = sorter.sorted().map_err(|_| WeaveError::ReweaveCycle)?;

    let mut wr = WeaveFile::default();
    for name in order {
        let lines = if let Some(idx_a) = wa.lookup(&name) {
            let lines_a = wa.get_lines(idx_a)?;
            if let Some(idx_b) = wb.lookup(&name) {
                let lines_b = wb.get_lines(idx_b)?;
                if lines_a != lines_b {
                    return Err(WeaveError::TextDiffers(name.clone()));
                }
            }
            lines_a
        } else {
            // Must be in wb (sorter only emitted versions from `combined`).
            let idx_b = wb.lookup(&name).expect("name from combined map");
            wb.get_lines(idx_b)?
        };
        let parent_names: Vec<Vec<u8>> = combined
            .get(&name)
            .expect("name from combined map")
            .iter()
            .cloned()
            .collect();
        let parent_refs: Vec<&[u8]> = parent_names.iter().map(|p| p.as_slice()).collect();
        wr.add_lines(&name, &parent_refs, &lines, None, None)?;
    }
    Ok(wr)
}

/// Errors from reading a v5 weave file.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum WeaveFileError {
    /// The file was empty or its first line wasn't the magic header.
    BadHeader(Vec<u8>),
    /// The file ended mid-record.
    UnexpectedEof,
    /// A header or body line didn't match any known form.
    UnexpectedLine(Vec<u8>),
    /// A numeric field (parent index, instruction version) couldn't be
    /// parsed as a decimal integer.
    InvalidInteger(Vec<u8>),
}

impl std::fmt::Display for WeaveFileError {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            WeaveFileError::BadHeader(l) => write!(f, "invalid weave file header: {:?}", l),
            WeaveFileError::UnexpectedEof => write!(f, "unexpected end of weave file"),
            WeaveFileError::UnexpectedLine(l) => write!(f, "unexpected line {:?}", l),
            WeaveFileError::InvalidInteger(s) => write!(f, "not a valid integer: {:?}", s),
        }
    }
}

impl std::error::Error for WeaveFileError {}

/// Instruction bracket kind in a weave entry stream.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Instruction {
    /// Open an insertion block introduced by `version`.
    InsertOpen,
    /// Close the most recently opened insertion block. `version` is ignored.
    InsertClose,
    /// Open a deletion block applied by `version`.
    DeleteOpen,
    /// Close a deletion block applied by `version`.
    DeleteClose,
}

/// One entry in a weave: either a literal line or a control instruction.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum WeaveEntry {
    Line(Vec<u8>),
    Control { op: Instruction, version: usize },
}

/// Errors from walking a malformed weave or from higher-level Weave ops.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum WeaveError {
    /// `}` appeared with no matching `{`.
    UnmatchedInsertClose,
    /// `]` appeared for a deletion that wasn't open (in the included set).
    UnmatchedDeleteClose(usize),
    /// Insertion stack non-empty at end of weave.
    UnclosedInsertions(Vec<usize>),
    /// Deletion set non-empty at end of weave.
    UnclosedDeletions(Vec<usize>),
    /// `add` was called with a name that already exists but with parents
    /// or a sha1 that don't match the existing entry.
    RevisionAlreadyPresent(Vec<u8>),
    /// `add` referenced a parent index that doesn't exist.
    RevisionNotPresent(usize),
    /// A read API was given a name that doesn't exist in this weave.
    RevisionNotPresentByName(Vec<u8>),
    /// `add` was called with `nostore_sha` matching the new content's sha1.
    ExistingContent,
    /// On-disk sha1 didn't match the recomputed sha1 for `get_lines`.
    InvalidChecksum {
        version: usize,
        expected: Vec<u8>,
        measured: Vec<u8>,
    },
    /// `check` found a parent index that wasn't strictly less than its child.
    Acyclic { version: usize, max: usize },
    /// `check` found ancestry computed by walking the parent table did not
    /// match `get_ancestry`'s output for the same version.
    AncestryMismatch(Vec<u8>),
    /// `imported_parents` couldn't find a needed parent in `self`.
    MissingParent { parent: Vec<u8>, child: Vec<u8> },
    /// Two weaves disagree on a version's text content.
    TextDiffers(Vec<u8>),
    /// Two weaves disagree on a version's parents (and `other` isn't a
    /// subset of `self`).
    ParentMismatch {
        version: Vec<u8>,
        a: Vec<Vec<u8>>,
        b: Vec<Vec<u8>>,
    },
    /// `reweave` saw a cycle in the combined parent graph.
    ReweaveCycle,
}

impl std::fmt::Display for WeaveError {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            WeaveError::UnmatchedInsertClose => write!(f, "unmatched '}}' in weave"),
            WeaveError::UnmatchedDeleteClose(v) => {
                write!(f, "unmatched ']' for version {} in weave", v)
            }
            WeaveError::UnclosedInsertions(v) => {
                write!(f, "unclosed insertion blocks at end of weave: {:?}", v)
            }
            WeaveError::UnclosedDeletions(v) => {
                write!(f, "unclosed deletion blocks at end of weave: {:?}", v)
            }
            WeaveError::RevisionAlreadyPresent(name) => {
                write!(f, "revision {:?} already present", name)
            }
            WeaveError::RevisionNotPresent(v) => {
                write!(f, "revision index {} not present", v)
            }
            WeaveError::RevisionNotPresentByName(name) => {
                write!(f, "revision {:?} not present", name)
            }
            WeaveError::ExistingContent => write!(f, "content already stored under nostore_sha"),
            WeaveError::InvalidChecksum {
                version,
                expected,
                measured,
            } => write!(
                f,
                "invalid checksum for version {}: expected {:?}, measured {:?}",
                version, expected, measured
            ),
            WeaveError::Acyclic { version, max } => {
                write!(f, "invalid included version {} for index {}", max, version)
            }
            WeaveError::AncestryMismatch(name) => {
                write!(f, "ancestry mismatch for version {:?}", name)
            }
            WeaveError::MissingParent { parent, child } => {
                write!(f, "missing parent {{{:?}}} of {{{:?}}}", parent, child)
            }
            WeaveError::TextDiffers(name) => {
                write!(f, "weaves differ on text content for version {:?}", name)
            }
            WeaveError::ParentMismatch { version, a, b } => write!(
                f,
                "inconsistent parents for version {{{:?}}}: {:?} vs {:?}",
                version, a, b
            ),
            WeaveError::ReweaveCycle => write!(f, "cycle in combined parent graph during reweave"),
        }
    }
}

impl std::error::Error for WeaveError {}

/// One yielded item from [`extract`]: the originating version index, the
/// absolute line number in the weave, and a borrow of the line bytes.
#[derive(Debug, PartialEq, Eq)]
pub struct ExtractLine<'a> {
    pub origin: usize,
    pub lineno: usize,
    pub text: &'a [u8],
}

/// Walk `weave` yielding lines that are active in the given `included`
/// version set. Mirrors `Weave._extract` in `bzrformats/weave.py`.
///
/// `included` should already contain the transitive closure of
/// ancestors for the versions of interest (see `inclusions`, added in a
/// follow-up). The caller passes indices into the weave's version table.
pub fn extract<'a>(
    weave: &'a [WeaveEntry],
    included: &std::collections::HashSet<usize>,
) -> Result<Vec<ExtractLine<'a>>, WeaveError> {
    let mut istack: Vec<usize> = Vec::new();
    let mut dset: std::collections::HashSet<usize> = std::collections::HashSet::new();
    let mut isactive: Option<bool> = None;
    let mut result = Vec::new();

    for (lineno, entry) in weave.iter().enumerate() {
        match entry {
            WeaveEntry::Control { op, version } => {
                isactive = None;
                match op {
                    Instruction::InsertOpen => istack.push(*version),
                    Instruction::InsertClose => {
                        istack.pop().ok_or(WeaveError::UnmatchedInsertClose)?;
                    }
                    Instruction::DeleteOpen => {
                        if included.contains(version) {
                            dset.insert(*version);
                        }
                    }
                    Instruction::DeleteClose => {
                        if included.contains(version) && !dset.remove(version) {
                            return Err(WeaveError::UnmatchedDeleteClose(*version));
                        }
                    }
                }
            }
            WeaveEntry::Line(text) => {
                let active = match isactive {
                    Some(a) => a,
                    None => {
                        let a = dset.is_empty()
                            && istack.last().is_some_and(|top| included.contains(top));
                        isactive = Some(a);
                        a
                    }
                };
                if active {
                    result.push(ExtractLine {
                        origin: *istack.last().expect("active implies non-empty istack"),
                        lineno,
                        text,
                    });
                }
            }
        }
    }

    if !istack.is_empty() {
        return Err(WeaveError::UnclosedInsertions(istack));
    }
    if !dset.is_empty() {
        let mut v: Vec<usize> = dset.iter().copied().collect();
        v.sort_unstable();
        return Err(WeaveError::UnclosedDeletions(v));
    }
    Ok(result)
}

/// Compute the set of ancestor version indices of `versions`, inclusive.
///
/// Mirrors `Weave._inclusions`: starts with the input set and, for each
/// version from `max..=1` that is in the set, unions in its immediate
/// parents from `parents_by_version`. Version 0 is treated as a root and
/// its parent list is never expanded — this matches the Python off-by-one
/// (`range(max(versions), 0, -1)`).
pub fn inclusions(
    parents_by_version: &[Vec<usize>],
    versions: &[usize],
) -> std::collections::HashSet<usize> {
    let mut out = std::collections::HashSet::new();
    if versions.is_empty() {
        return out;
    }
    out.extend(versions.iter().copied());
    let max_v = *versions.iter().max().expect("non-empty");
    for v in (1..=max_v).rev() {
        if out.contains(&v) {
            if let Some(ps) = parents_by_version.get(v) {
                out.extend(ps.iter().copied());
            }
        }
    }
    out
}

/// One yielded item from [`walk_internal`]: the absolute line number, the
/// innermost open insertion version, the set of active deletion versions,
/// and a borrow of the line bytes. Matches `Weave._walk_internal` but with
/// indices rather than resolved names.
#[derive(Debug, PartialEq, Eq)]
pub struct WalkLine<'a> {
    pub lineno: usize,
    pub insert: usize,
    pub deletes: Vec<usize>,
    pub text: &'a [u8],
}

/// Walk `weave` yielding every literal line along with its open-insertion
/// version and the current deletion set. Unlike [`extract`], this doesn't
/// filter on an `included` set — callers decide what to do with each line.
pub fn walk_internal(weave: &[WeaveEntry]) -> Result<Vec<WalkLine<'_>>, WeaveError> {
    let mut istack: Vec<usize> = Vec::new();
    let mut dset: std::collections::BTreeSet<usize> = std::collections::BTreeSet::new();
    let mut result = Vec::new();

    for (lineno, entry) in weave.iter().enumerate() {
        match entry {
            WeaveEntry::Control { op, version } => match op {
                Instruction::InsertOpen => istack.push(*version),
                Instruction::InsertClose => {
                    istack.pop().ok_or(WeaveError::UnmatchedInsertClose)?;
                }
                Instruction::DeleteOpen => {
                    dset.insert(*version);
                }
                Instruction::DeleteClose => {
                    if !dset.remove(version) {
                        return Err(WeaveError::UnmatchedDeleteClose(*version));
                    }
                }
            },
            WeaveEntry::Line(text) => {
                let insert = *istack.last().expect("line outside any insertion block");
                result.push(WalkLine {
                    lineno,
                    insert,
                    deletes: dset.iter().copied().collect(),
                    text,
                });
            }
        }
    }

    if !istack.is_empty() {
        return Err(WeaveError::UnclosedInsertions(istack));
    }
    if !dset.is_empty() {
        return Err(WeaveError::UnclosedDeletions(
            dset.iter().copied().collect(),
        ));
    }
    Ok(result)
}

/// Parse a v5 weave file from its raw bytes. Mirrors
/// `bzrformats.weavefile._read_weave_v5`.
pub fn read_weave_v5(data: &[u8]) -> Result<WeaveFile, WeaveFileError> {
    let lines = split_with_newlines(data);
    let mut iter = lines.into_iter();

    let first = iter.next().ok_or(WeaveFileError::UnexpectedEof)?;
    if first != WEAVE_V5_FORMAT {
        return Err(WeaveFileError::BadHeader(first.to_vec()));
    }

    let mut out = WeaveFile::default();

    // Per-version metadata: `i[ parents...]`, `1 sha1`, `n name`, blank.
    loop {
        let line = iter.next().ok_or(WeaveFileError::UnexpectedEof)?;
        if line == b"w\n" {
            break;
        }
        if line.first() == Some(&b'i') {
            // `b"i\n"` is no-parents; `b"i <int>( <int>)*\n"` is a parent list.
            let ps = if line.len() > 2 {
                let trimmed = trim_trailing_newline(&line[2..]);
                let mut result = Vec::new();
                for part in trimmed.split(|&b| b == b' ') {
                    result.push(parse_usize(part)?);
                }
                result
            } else {
                Vec::new()
            };
            out.parents.push(ps);

            let sha1_line = iter.next().ok_or(WeaveFileError::UnexpectedEof)?;
            out.sha1s
                .push(trim_trailing_newline(&sha1_line[2..]).to_vec());

            let name_line = iter.next().ok_or(WeaveFileError::UnexpectedEof)?;
            out.names
                .push(trim_trailing_newline(&name_line[2..]).to_vec());

            // Consume the trailing blank line between records.
            iter.next().ok_or(WeaveFileError::UnexpectedEof)?;
        } else {
            return Err(WeaveFileError::UnexpectedLine(line.to_vec()));
        }
    }

    // Body: weave entries terminated by `W\n`.
    loop {
        let line = iter.next().ok_or(WeaveFileError::UnexpectedEof)?;
        if line == b"W\n" {
            break;
        }
        if line.starts_with(b". ") {
            // Literal line that includes its trailing newline.
            out.weave.push(WeaveEntry::Line(line[2..].to_vec()));
        } else if line.starts_with(b", ") {
            // Literal line that doesn't end in a newline — strip the wrapper.
            out.weave
                .push(WeaveEntry::Line(trim_trailing_newline(&line[2..]).to_vec()));
        } else if line == b"}\n" {
            out.weave.push(WeaveEntry::Control {
                op: Instruction::InsertClose,
                version: 0,
            });
        } else {
            let tag = *line
                .first()
                .ok_or_else(|| WeaveFileError::UnexpectedLine(line.to_vec()))?;
            let op = match tag {
                b'{' => Instruction::InsertOpen,
                b'[' => Instruction::DeleteOpen,
                b']' => Instruction::DeleteClose,
                _ => return Err(WeaveFileError::UnexpectedLine(line.to_vec())),
            };
            // The version number is ASCII digits after `"X "` up to the
            // trailing `\n`.
            if line.len() < 3 || line[1] != b' ' {
                return Err(WeaveFileError::UnexpectedLine(line.to_vec()));
            }
            let version = parse_usize(trim_trailing_newline(&line[2..]))?;
            out.weave.push(WeaveEntry::Control { op, version });
        }
    }

    Ok(out)
}

/// Serialize a [`WeaveFile`] to the v5 on-disk byte format. Mirrors
/// `bzrformats.weavefile.write_weave_v5`.
pub fn write_weave_v5(wf: &WeaveFile) -> Vec<u8> {
    let mut out = Vec::new();
    out.extend_from_slice(WEAVE_V5_FORMAT);

    for version in 0..wf.parents.len() {
        let parents = &wf.parents[version];
        if parents.is_empty() {
            out.extend_from_slice(b"i\n");
        } else {
            out.extend_from_slice(b"i ");
            for (i, &p) in parents.iter().enumerate() {
                if i > 0 {
                    out.push(b' ');
                }
                out.extend_from_slice(p.to_string().as_bytes());
            }
            out.push(b'\n');
        }
        out.extend_from_slice(b"1 ");
        out.extend_from_slice(&wf.sha1s[version]);
        out.push(b'\n');
        out.extend_from_slice(b"n ");
        out.extend_from_slice(&wf.names[version]);
        out.push(b'\n');
        out.push(b'\n');
    }

    out.extend_from_slice(b"w\n");

    for entry in &wf.weave {
        match entry {
            WeaveEntry::Control { op, version } => match op {
                Instruction::InsertClose => out.extend_from_slice(b"}\n"),
                Instruction::InsertOpen => {
                    out.extend_from_slice(b"{ ");
                    out.extend_from_slice(version.to_string().as_bytes());
                    out.push(b'\n');
                }
                Instruction::DeleteOpen => {
                    out.extend_from_slice(b"[ ");
                    out.extend_from_slice(version.to_string().as_bytes());
                    out.push(b'\n');
                }
                Instruction::DeleteClose => {
                    out.extend_from_slice(b"] ");
                    out.extend_from_slice(version.to_string().as_bytes());
                    out.push(b'\n');
                }
            },
            WeaveEntry::Line(line) => {
                if line.is_empty() {
                    out.extend_from_slice(b", \n");
                } else if line.last() == Some(&b'\n') {
                    out.extend_from_slice(b". ");
                    out.extend_from_slice(line);
                } else {
                    out.extend_from_slice(b", ");
                    out.extend_from_slice(line);
                    out.push(b'\n');
                }
            }
        }
    }

    out.extend_from_slice(b"W\n");
    out
}

/// Split `data` on `\n`, keeping the newline at the end of each line except
/// the last. Mirrors Python's `readlines()` semantics.
fn split_with_newlines(data: &[u8]) -> Vec<&[u8]> {
    let mut out = Vec::new();
    let mut start = 0;
    for (i, &b) in data.iter().enumerate() {
        if b == b'\n' {
            out.push(&data[start..=i]);
            start = i + 1;
        }
    }
    if start < data.len() {
        out.push(&data[start..]);
    }
    out
}

fn trim_trailing_newline(line: &[u8]) -> &[u8] {
    if line.last() == Some(&b'\n') {
        &line[..line.len() - 1]
    } else {
        line
    }
}

fn parse_usize(bytes: &[u8]) -> Result<usize, WeaveFileError> {
    std::str::from_utf8(bytes)
        .ok()
        .and_then(|s| s.trim().parse::<usize>().ok())
        .ok_or_else(|| WeaveFileError::InvalidInteger(bytes.to_vec()))
}

#[cfg(test)]
mod tests {
    use super::*;
    use std::collections::HashSet;

    fn line(s: &[u8]) -> WeaveEntry {
        WeaveEntry::Line(s.to_vec())
    }

    fn ctl(op: Instruction, v: usize) -> WeaveEntry {
        WeaveEntry::Control { op, version: v }
    }

    fn set(xs: &[usize]) -> HashSet<usize> {
        xs.iter().copied().collect()
    }

    /// Simplest weave: a single version 0 inserts three lines.
    #[test]
    fn single_version_extract() {
        let weave = vec![
            ctl(Instruction::InsertOpen, 0),
            line(b"a\n"),
            line(b"b\n"),
            line(b"c\n"),
            ctl(Instruction::InsertClose, 0),
        ];
        let got = extract(&weave, &set(&[0])).unwrap();
        let lines: Vec<&[u8]> = got.iter().map(|e| e.text).collect();
        assert_eq!(lines, vec![b"a\n".as_slice(), b"b\n", b"c\n"]);
        assert!(got.iter().all(|e| e.origin == 0));
    }

    /// An excluded version's lines don't appear even though the weave
    /// still contains them.
    #[test]
    fn excluded_version_filtered() {
        let weave = vec![
            ctl(Instruction::InsertOpen, 0),
            line(b"base\n"),
            ctl(Instruction::InsertClose, 0),
            ctl(Instruction::InsertOpen, 1),
            line(b"only-in-1\n"),
            ctl(Instruction::InsertClose, 1),
        ];
        let got = extract(&weave, &set(&[0])).unwrap();
        assert_eq!(got.len(), 1);
        assert_eq!(got[0].text, b"base\n");
        assert_eq!(got[0].origin, 0);
    }

    /// A version-1 insertion nested inside version-0 keeps the origin
    /// pointing at version 1 (innermost open insertion).
    #[test]
    fn nested_insertion_origin() {
        let weave = vec![
            ctl(Instruction::InsertOpen, 0),
            line(b"top\n"),
            ctl(Instruction::InsertOpen, 1),
            line(b"nested\n"),
            ctl(Instruction::InsertClose, 1),
            line(b"bottom\n"),
            ctl(Instruction::InsertClose, 0),
        ];
        let got = extract(&weave, &set(&[0, 1])).unwrap();
        let pairs: Vec<(usize, &[u8])> = got.iter().map(|e| (e.origin, e.text)).collect();
        assert_eq!(
            pairs,
            vec![(0, b"top\n".as_slice()), (1, b"nested\n"), (0, b"bottom\n"),]
        );
    }

    /// A deletion applied by version 1 suppresses a version-0 line when
    /// version 1 is in the included set.
    #[test]
    fn deletion_suppresses_line() {
        let weave = vec![
            ctl(Instruction::InsertOpen, 0),
            line(b"keep\n"),
            ctl(Instruction::DeleteOpen, 1),
            line(b"gone\n"),
            ctl(Instruction::DeleteClose, 1),
            line(b"also\n"),
            ctl(Instruction::InsertClose, 0),
        ];
        let got_v0 = extract(&weave, &set(&[0])).unwrap();
        assert_eq!(got_v0.len(), 3, "without version 1, delete is inert");
        let got_v01 = extract(&weave, &set(&[0, 1])).unwrap();
        let lines: Vec<&[u8]> = got_v01.iter().map(|e| e.text).collect();
        assert_eq!(lines, vec![b"keep\n".as_slice(), b"also\n"]);
    }

    #[test]
    fn unclosed_insertion_errors() {
        let weave = vec![ctl(Instruction::InsertOpen, 0), line(b"x\n")];
        assert_eq!(
            extract(&weave, &set(&[0])),
            Err(WeaveError::UnclosedInsertions(vec![0]))
        );
    }

    #[test]
    fn unmatched_close_errors() {
        let weave = vec![ctl(Instruction::InsertClose, 0)];
        assert_eq!(
            extract(&weave, &set(&[0])),
            Err(WeaveError::UnmatchedInsertClose)
        );
    }

    /// An inactive insertion's lines aren't emitted even if a deletion
    /// is also open inside them.
    #[test]
    fn inclusions_empty_input() {
        assert!(inclusions(&[vec![]], &[]).is_empty());
    }

    #[test]
    fn inclusions_linear_chain() {
        // 0 <- 1 <- 2 <- 3
        let parents = vec![vec![], vec![0], vec![1], vec![2]];
        let got = inclusions(&parents, &[3]);
        assert_eq!(got, set(&[0, 1, 2, 3]));
    }

    #[test]
    fn inclusions_version_zero_root_is_not_expanded() {
        // Verify the Python off-by-one: version 0's parents slot is
        // never consulted. Put a nonsense sentinel parent there and
        // make sure it doesn't leak into the result.
        let parents = vec![vec![999], vec![0]];
        let got = inclusions(&parents, &[1]);
        assert_eq!(got, set(&[0, 1]));
    }

    #[test]
    fn inclusions_merges_converge() {
        // 0 -- 1 -- 3
        //  \-- 2 --/
        let parents = vec![vec![], vec![0], vec![0], vec![1, 2]];
        let got = inclusions(&parents, &[3]);
        assert_eq!(got, set(&[0, 1, 2, 3]));
    }

    #[test]
    fn walk_internal_reports_deletes() {
        let weave = vec![
            ctl(Instruction::InsertOpen, 0),
            line(b"a\n"),
            ctl(Instruction::DeleteOpen, 1),
            line(b"b\n"),
            ctl(Instruction::DeleteClose, 1),
            ctl(Instruction::InsertClose, 0),
        ];
        let got = walk_internal(&weave).unwrap();
        assert_eq!(got.len(), 2);
        assert_eq!(got[0].text, b"a\n");
        assert_eq!(got[0].insert, 0);
        assert!(got[0].deletes.is_empty());
        assert_eq!(got[1].text, b"b\n");
        assert_eq!(got[1].insert, 0);
        assert_eq!(got[1].deletes, vec![1]);
    }

    #[test]
    fn three_way_merge_extract() {
        // Mirrors test_weave.test_multi_line_merge. The weave shape is
        // captured from a real `Weave` instance (not hand-crafted) so the
        // test exercises the exact nesting of insertions and deletions
        // that `_add` produces for a three-way merge.
        let weave = vec![
            ctl(Instruction::InsertOpen, 0),
            line(b"header"),
            ctl(Instruction::InsertClose, 0),
            ctl(Instruction::InsertOpen, 1),
            line(b""),
            line(b"line from 1"),
            ctl(Instruction::InsertClose, 1),
            ctl(Instruction::InsertOpen, 2),
            ctl(Instruction::DeleteOpen, 3),
            line(b""),
            ctl(Instruction::DeleteClose, 3),
            ctl(Instruction::InsertOpen, 3),
            line(b"fixup line"),
            ctl(Instruction::InsertClose, 3),
            line(b"line from 2"),
            ctl(Instruction::DeleteOpen, 3),
            line(b"more from 2"),
            ctl(Instruction::InsertClose, 2),
            ctl(Instruction::DeleteClose, 3),
        ];
        let got = extract(&weave, &set(&[0, 1, 2, 3])).unwrap();
        let pairs: Vec<(usize, &[u8])> = got.iter().map(|e| (e.origin, e.text)).collect();
        assert_eq!(
            pairs,
            vec![
                (0, b"header".as_slice()),
                (1, b""),
                (1, b"line from 1"),
                (3, b"fixup line"),
                (2, b"line from 2"),
            ]
        );
    }

    #[test]
    fn read_weave_v5_minimal() {
        // One version, no parents, one literal line.
        let mut data = WEAVE_V5_FORMAT.to_vec();
        data.extend_from_slice(b"i\n1 0000000000000000000000000000000000000000\nn text0\n\n");
        data.extend_from_slice(b"w\n");
        data.extend_from_slice(b"{ 0\n. hello\n}\n");
        data.extend_from_slice(b"W\n");

        let wf = read_weave_v5(&data).unwrap();
        assert_eq!(wf.parents, vec![Vec::<usize>::new()]);
        assert_eq!(
            wf.sha1s,
            vec![b"0000000000000000000000000000000000000000".to_vec()]
        );
        assert_eq!(wf.names, vec![b"text0".to_vec()]);
        assert_eq!(
            wf.weave,
            vec![
                WeaveEntry::Control {
                    op: Instruction::InsertOpen,
                    version: 0,
                },
                WeaveEntry::Line(b"hello\n".to_vec()),
                WeaveEntry::Control {
                    op: Instruction::InsertClose,
                    version: 0,
                },
            ]
        );
    }

    #[test]
    fn read_weave_v5_with_parents_and_no_eol_line() {
        // Two versions: the second has parent 0, and the body contains a
        // `", "` line (no trailing newline) plus a deletion bracket.
        let mut data = WEAVE_V5_FORMAT.to_vec();
        data.extend_from_slice(b"i\n1 aaa\nn text0\n\n");
        data.extend_from_slice(b"i 0\n1 bbb\nn text1\n\n");
        data.extend_from_slice(b"w\n");
        data.extend_from_slice(b"{ 0\n. line\n, noeol\n}\n");
        data.extend_from_slice(b"[ 1\n, gone\n] 1\n");
        data.extend_from_slice(b"W\n");

        let wf = read_weave_v5(&data).unwrap();
        assert_eq!(wf.parents, vec![Vec::<usize>::new(), vec![0]]);
        assert_eq!(wf.sha1s, vec![b"aaa".to_vec(), b"bbb".to_vec()]);
        assert_eq!(wf.names, vec![b"text0".to_vec(), b"text1".to_vec()]);
        assert_eq!(
            wf.weave,
            vec![
                WeaveEntry::Control {
                    op: Instruction::InsertOpen,
                    version: 0,
                },
                WeaveEntry::Line(b"line\n".to_vec()),
                WeaveEntry::Line(b"noeol".to_vec()),
                WeaveEntry::Control {
                    op: Instruction::InsertClose,
                    version: 0,
                },
                WeaveEntry::Control {
                    op: Instruction::DeleteOpen,
                    version: 1,
                },
                WeaveEntry::Line(b"gone".to_vec()),
                WeaveEntry::Control {
                    op: Instruction::DeleteClose,
                    version: 1,
                },
            ]
        );
    }

    #[test]
    fn read_weave_v5_multiple_parents_on_one_version() {
        // Version 2 has parents [0, 1].
        let mut data = WEAVE_V5_FORMAT.to_vec();
        data.extend_from_slice(b"i\n1 a\nn v0\n\n");
        data.extend_from_slice(b"i 0\n1 b\nn v1\n\n");
        data.extend_from_slice(b"i 0 1\n1 c\nn v2\n\n");
        data.extend_from_slice(b"w\nW\n");

        let wf = read_weave_v5(&data).unwrap();
        assert_eq!(wf.parents, vec![vec![], vec![0], vec![0, 1]]);
        assert_eq!(wf.weave, Vec::<WeaveEntry>::new());
    }

    #[test]
    fn read_weave_v5_empty_line_roundtrips_to_empty_bytes() {
        // The `", "` form with an empty payload represents an empty line.
        let mut data = WEAVE_V5_FORMAT.to_vec();
        data.extend_from_slice(b"i\n1 a\nn v0\n\n");
        data.extend_from_slice(b"w\n{ 0\n, \n}\nW\n");

        let wf = read_weave_v5(&data).unwrap();
        assert_eq!(
            wf.weave,
            vec![
                WeaveEntry::Control {
                    op: Instruction::InsertOpen,
                    version: 0,
                },
                WeaveEntry::Line(b"".to_vec()),
                WeaveEntry::Control {
                    op: Instruction::InsertClose,
                    version: 0,
                },
            ]
        );
    }

    #[test]
    fn read_weave_v5_rejects_bad_header() {
        let err = read_weave_v5(b"not-a-weave\n").unwrap_err();
        assert!(matches!(err, WeaveFileError::BadHeader(_)));
    }

    #[test]
    fn read_weave_v5_rejects_empty_input() {
        assert_eq!(read_weave_v5(b""), Err(WeaveFileError::UnexpectedEof));
    }

    #[test]
    fn read_weave_v5_rejects_truncated_after_header() {
        let err = read_weave_v5(WEAVE_V5_FORMAT).unwrap_err();
        assert_eq!(err, WeaveFileError::UnexpectedEof);
    }

    fn sample_weave_file() -> WeaveFile {
        WeaveFile {
            parents: vec![vec![], vec![0], vec![0, 1]],
            sha1s: vec![
                b"1111111111111111111111111111111111111111".to_vec(),
                b"2222222222222222222222222222222222222222".to_vec(),
                b"3333333333333333333333333333333333333333".to_vec(),
            ],
            names: vec![b"text0".to_vec(), b"text1".to_vec(), b"merge".to_vec()],
            weave: vec![
                WeaveEntry::Control {
                    op: Instruction::InsertOpen,
                    version: 0,
                },
                WeaveEntry::Line(b"hello\n".to_vec()),
                WeaveEntry::Line(b"no-eol".to_vec()),
                WeaveEntry::Control {
                    op: Instruction::InsertClose,
                    version: 0,
                },
                WeaveEntry::Control {
                    op: Instruction::DeleteOpen,
                    version: 1,
                },
                WeaveEntry::Line(b"".to_vec()),
                WeaveEntry::Control {
                    op: Instruction::DeleteClose,
                    version: 1,
                },
            ],
        }
    }

    #[test]
    fn write_weave_v5_shape() {
        let expected: Vec<u8> = [
            b"# bzr weave file v5\n".as_slice(),
            b"i\n1 1111111111111111111111111111111111111111\nn text0\n\n",
            b"i 0\n1 2222222222222222222222222222222222222222\nn text1\n\n",
            b"i 0 1\n1 3333333333333333333333333333333333333333\nn merge\n\n",
            b"w\n",
            b"{ 0\n. hello\n, no-eol\n}\n",
            b"[ 1\n, \n] 1\n",
            b"W\n",
        ]
        .concat();
        assert_eq!(write_weave_v5(&sample_weave_file()), expected);
    }

    #[test]
    fn weave_file_round_trip() {
        let wf = sample_weave_file();
        let bytes = write_weave_v5(&wf);
        let parsed = read_weave_v5(&bytes).unwrap();
        assert_eq!(parsed, wf);
    }

    #[test]
    fn weave_file_round_trip_minimal() {
        let wf = WeaveFile {
            parents: vec![vec![]],
            sha1s: vec![b"a".to_vec()],
            names: vec![b"v0".to_vec()],
            weave: vec![],
        };
        let bytes = write_weave_v5(&wf);
        assert_eq!(read_weave_v5(&bytes).unwrap(), wf);
    }

    #[test]
    fn weave_file_round_trip_empty_weave_body() {
        // No instructions and no literal lines — just metadata then `w\nW\n`.
        let wf = WeaveFile {
            parents: vec![vec![], vec![0]],
            sha1s: vec![b"x".to_vec(), b"y".to_vec()],
            names: vec![b"a".to_vec(), b"b".to_vec()],
            weave: vec![],
        };
        let bytes = write_weave_v5(&wf);
        assert_eq!(read_weave_v5(&bytes).unwrap(), wf);
    }

    #[test]
    fn walk_internal_unclosed_insertion_errors() {
        let weave = vec![ctl(Instruction::InsertOpen, 0), line(b"x\n")];
        assert_eq!(
            walk_internal(&weave),
            Err(WeaveError::UnclosedInsertions(vec![0]))
        );
    }

    #[test]
    fn inactive_insertion_blocks_lines() {
        let weave = vec![
            ctl(Instruction::InsertOpen, 1),
            line(b"only-in-1\n"),
            ctl(Instruction::InsertClose, 1),
        ];
        let got = extract(&weave, &set(&[0])).unwrap();
        assert!(got.is_empty());
    }

    fn ls(strs: &[&[u8]]) -> Vec<Vec<u8>> {
        strs.iter().map(|s| s.to_vec()).collect()
    }

    /// Mirrors `RepeatedAdd::test_duplicate_add` — adding the same name
    /// twice with matching parents+sha1 returns the same index.
    #[test]
    fn duplicate_add_returns_existing_index() {
        let mut wf = WeaveFile::default();
        let text = ls(&[b"line 1\n", b"line 2\n"]);
        let idx1 = wf.add(Some(b"text0"), &text, &[], None, None).unwrap();
        let idx2 = wf.add(Some(b"text0"), &text, &[], None, None).unwrap();
        assert_eq!(idx1, idx2);
        assert_eq!(wf.parents.len(), 1);
    }

    /// Mirrors `InvalidRepeatedAdd` — same name with different content or
    /// different parents must error.
    #[test]
    fn invalid_repeated_add_errors() {
        let mut wf = WeaveFile::default();
        let text = ls(&[b"line 1\n"]);
        wf.add(Some(b"basis"), &text, &[], None, None).unwrap();
        wf.add(Some(b"text0"), &text, &[], None, None).unwrap();
        // Different content under same name.
        let other = ls(&[b"different\n"]);
        let err = wf.add(Some(b"text0"), &other, &[], None, None).unwrap_err();
        assert_eq!(err, WeaveError::RevisionAlreadyPresent(b"text0".to_vec()));
        // Same content but wrong parents.
        let err = wf.add(Some(b"text0"), &text, &[0], None, None).unwrap_err();
        assert_eq!(err, WeaveError::RevisionAlreadyPresent(b"text0".to_vec()));
    }

    /// Mirrors `InvalidAdd` — referencing a missing parent index errors.
    #[test]
    fn invalid_add_missing_parent_errors() {
        let mut wf = WeaveFile::default();
        let err = wf
            .add(Some(b"text0"), &ls(&[b"new text\n"]), &[69], None, None)
            .unwrap_err();
        assert_eq!(err, WeaveError::RevisionNotPresent(69));
    }

    /// Mirrors `AnnotateOne` — single version annotation reports its own
    /// name as origin for every line.
    #[test]
    fn annotate_one_version() {
        let mut wf = WeaveFile::default();
        let text = ls(&[b"hello\n", b"world\n"]);
        let idx = wf.add(Some(b"text0"), &text, &[], None, None).unwrap();
        let annotated = wf.annotate(idx).unwrap();
        assert_eq!(
            annotated,
            vec![
                (b"text0".to_vec(), b"hello\n".to_vec()),
                (b"text0".to_vec(), b"world\n".to_vec()),
            ]
        );
    }

    /// Mirrors the first half of `InsertLines::runTest` — adding a single
    /// line on top of a parent attributes the new line to the new version
    /// and re-uses the parent's line.
    #[test]
    fn insert_one_line_attribution() {
        let mut wf = WeaveFile::default();
        wf.add(Some(b"text0"), &ls(&[b"line 1\n"]), &[], None, None)
            .unwrap();
        wf.add(
            Some(b"text1"),
            &ls(&[b"line 1\n", b"line 2\n"]),
            &[0],
            None,
            None,
        )
        .unwrap();
        assert_eq!(
            wf.annotate(0).unwrap(),
            vec![(b"text0".to_vec(), b"line 1\n".to_vec())]
        );
        assert_eq!(
            wf.get_lines(1).unwrap(),
            vec![b"line 1\n".to_vec(), b"line 2\n".to_vec()]
        );
        assert_eq!(
            wf.annotate(1).unwrap(),
            vec![
                (b"text0".to_vec(), b"line 1\n".to_vec()),
                (b"text1".to_vec(), b"line 2\n".to_vec()),
            ]
        );
    }

    /// Mirrors the merge half of `InsertLines::runTest` — a 3-way insertion
    /// keeps the parent attributions for shared lines and credits the
    /// new version for the inserted middle line.
    #[test]
    fn insert_lines_merge_attribution() {
        let mut wf = WeaveFile::default();
        wf.add(Some(b"text0"), &ls(&[b"line 1\n"]), &[], None, None)
            .unwrap();
        wf.add(
            Some(b"text1"),
            &ls(&[b"line 1\n", b"line 2\n"]),
            &[0],
            None,
            None,
        )
        .unwrap();
        wf.add(
            Some(b"text3"),
            &ls(&[b"line 1\n", b"middle line\n", b"line 2\n"]),
            &[0, 1],
            None,
            None,
        )
        .unwrap();
        assert_eq!(
            wf.annotate(2).unwrap(),
            vec![
                (b"text0".to_vec(), b"line 1\n".to_vec()),
                (b"text3".to_vec(), b"middle line\n".to_vec()),
                (b"text1".to_vec(), b"line 2\n".to_vec()),
            ]
        );
    }

    /// Mirrors `DeleteLines::runTest` — every derived version round-trips
    /// through `get_lines` after being added with a single parent.
    #[test]
    fn delete_lines_round_trip() {
        let mut wf = WeaveFile::default();
        let base = ls(&[b"one\n", b"two\n", b"three\n", b"four\n"]);
        wf.add(Some(b"text0"), &base, &[], None, None).unwrap();
        let texts: Vec<Vec<Vec<u8>>> = vec![
            ls(&[b"one\n", b"two\n", b"three\n"]),
            ls(&[b"two\n", b"three\n", b"four\n"]),
            ls(&[b"one\n", b"four\n"]),
            ls(&[b"one\n", b"two\n", b"three\n", b"four\n"]),
        ];
        for (i, t) in texts.iter().enumerate() {
            wf.add(
                Some(format!("text{}", i + 1).as_bytes()),
                t,
                &[0],
                None,
                None,
            )
            .unwrap();
        }
        for (i, t) in texts.iter().enumerate() {
            assert_eq!(&wf.get_lines(i + 1).unwrap(), t);
        }
    }

    /// `add` with `nostore_sha` matching the new content errors instead
    /// of inserting.
    #[test]
    fn add_nostore_sha_blocks_storage() {
        let mut wf = WeaveFile::default();
        let text = ls(&[b"line\n"]);
        let sha = sha_strings(&text);
        let err = wf
            .add(Some(b"text0"), &text, &[], None, Some(&sha))
            .unwrap_err();
        assert_eq!(err, WeaveError::ExistingContent);
        assert!(wf.parents.is_empty());
    }

    /// Mirrors `WeaveContains` — a freshly-added name is reported by
    /// `has_version` and absent names are not.
    #[test]
    fn has_version_reports_membership() {
        let mut wf = WeaveFile::default();
        assert!(!wf.has_version(b"foo"));
        wf.add(Some(b"foo"), &ls(&[b"x\n"]), &[], None, None)
            .unwrap();
        assert!(wf.has_version(b"foo"));
        assert!(!wf.has_version(b"bar"));
    }

    /// `versions()` returns names in insertion order.
    #[test]
    fn versions_returns_names_in_order() {
        let mut wf = WeaveFile::default();
        wf.add(Some(b"a"), &ls(&[b"a\n"]), &[], None, None).unwrap();
        wf.add(Some(b"b"), &ls(&[b"a\n", b"b\n"]), &[0], None, None)
            .unwrap();
        assert_eq!(wf.versions(), vec![b"a".to_vec(), b"b".to_vec()]);
        assert_eq!(wf.num_versions(), 2);
    }

    /// `get_sha1s` returns the stored sha1 for each name; unknown names
    /// surface as `RevisionNotPresentByName`.
    #[test]
    fn get_sha1s_for_known_and_unknown() {
        let mut wf = WeaveFile::default();
        let text = ls(&[b"hello\n"]);
        let sha = sha_strings(&text);
        wf.add(Some(b"v0"), &text, &[], None, None).unwrap();
        let known: &[&[u8]] = &[b"v0"];
        assert_eq!(
            wf.get_sha1s(known.iter().copied()).unwrap(),
            vec![(b"v0".to_vec(), sha)]
        );
        let unknown: &[&[u8]] = &[b"nope"];
        let err = wf.get_sha1s(unknown.iter().copied()).unwrap_err();
        assert_eq!(err, WeaveError::RevisionNotPresentByName(b"nope".to_vec()));
    }

    /// `get_parent_map` resolves parent indices to names and silently
    /// drops unknown inputs.
    #[test]
    fn get_parent_map_drops_unknown() {
        let mut wf = WeaveFile::default();
        wf.add(Some(b"a"), &ls(&[b"x\n"]), &[], None, None).unwrap();
        wf.add(Some(b"b"), &ls(&[b"x\n", b"y\n"]), &[0], None, None)
            .unwrap();
        let lookups: &[&[u8]] = &[b"a", b"missing", b"b"];
        let mp = wf.get_parent_map(lookups.iter().copied());
        assert_eq!(
            mp,
            vec![
                (b"a".to_vec(), vec![]),
                (b"b".to_vec(), vec![b"a".to_vec()]),
            ]
        );
    }

    /// `get_ancestry` includes the queried versions and their transitive
    /// parents. Mirrors the `DivergedIncludes` ancestry assertion.
    #[test]
    fn get_ancestry_diverged() {
        let mut wf = WeaveFile::default();
        wf.add(Some(b"0"), &ls(&[b"first line"]), &[], None, None)
            .unwrap();
        wf.add(
            Some(b"1"),
            &ls(&[b"first line", b"second line"]),
            &[0],
            None,
            None,
        )
        .unwrap();
        wf.add(
            Some(b"2"),
            &ls(&[b"first line", b"alternative second line"]),
            &[0],
            None,
            None,
        )
        .unwrap();
        let asked: &[&[u8]] = &[b"2"];
        let anc = wf.get_ancestry(asked.iter().copied()).unwrap();
        assert_eq!(anc, vec![b"0".to_vec(), b"2".to_vec()]);
    }

    /// Mirrors `TestNeedsReweave::test_compatible_parents`.
    #[test]
    fn compatible_parents_subset_check() {
        let my: HashSet<usize> = [1, 2, 3].iter().copied().collect();
        assert!(WeaveFile::compatible_parents(
            &my,
            &[3].iter().copied().collect()
        ));
        assert!(WeaveFile::compatible_parents(&my, &my));
        assert!(WeaveFile::compatible_parents(
            &HashSet::new(),
            &HashSet::new()
        ));
        assert!(!WeaveFile::compatible_parents(
            &HashSet::new(),
            &[1].iter().copied().collect()
        ));
        assert!(!WeaveFile::compatible_parents(
            &my,
            &[1, 2, 3, 4].iter().copied().collect()
        ));
        assert!(!WeaveFile::compatible_parents(
            &my,
            &[4].iter().copied().collect()
        ));
    }

    /// `add` without an explicit name allocates `b"sha1:" + sha1`.
    #[test]
    fn add_anonymous_uses_sha_name() {
        let mut wf = WeaveFile::default();
        let text = ls(&[b"hi\n"]);
        let sha = sha_strings(&text);
        let idx = wf.add(None, &text, &[], None, None).unwrap();
        assert_eq!(wf.names[idx], {
            let mut n = b"sha1:".to_vec();
            n.extend_from_slice(&sha);
            n
        });
    }

    /// `add_lines` resolves parent names via `lookup` and surfaces
    /// `RevisionNotPresentByName` for missing parents — matching what the
    /// Python `Weave.add_lines` -> `_add` flow does for invalid parent
    /// names (test_weave.InvalidAdd).
    #[test]
    fn add_lines_by_name_unknown_parent_errors() {
        let mut wf = WeaveFile::default();
        let lines = ls(&[b"x\n"]);
        let parents: &[&[u8]] = &[b"69"];
        let err = wf
            .add_lines(b"text0", parents, &lines, None, None)
            .unwrap_err();
        assert_eq!(err, WeaveError::RevisionNotPresentByName(b"69".to_vec()));
    }

    /// `add_lines` happy path: resolves parent name to its index and
    /// records the new version on top of the existing weave.
    #[test]
    fn add_lines_by_name_resolves_parent() {
        let mut wf = WeaveFile::default();
        wf.add_lines(b"v0", &[], &ls(&[b"a\n"]), None, None)
            .unwrap();
        let p: &[&[u8]] = &[b"v0"];
        let idx = wf
            .add_lines(b"v1", p, &ls(&[b"a\n", b"b\n"]), None, None)
            .unwrap();
        assert_eq!(idx, 1);
        assert_eq!(wf.get_lines(1).unwrap(), ls(&[b"a\n", b"b\n"]));
    }

    /// Lines with no trailing newline get one appended on iteration.
    /// Mirrors the trailing-`\n` handling in
    /// `Weave.iter_lines_added_or_present_in_versions`.
    #[test]
    fn iter_lines_appends_missing_newline() {
        let mut wf = WeaveFile::default();
        wf.add(Some(b"v0"), &[b"no-eol".to_vec()], &[], None, None)
            .unwrap();
        let names: Vec<&[u8]> = vec![b"v0"];
        let got = wf
            .iter_lines_added_or_present_in_versions(Some(names))
            .unwrap()
            .collect::<Vec<_>>();
        assert_eq!(got, vec![(b"no-eol\n".to_vec(), b"v0".to_vec())]);
    }

    /// Filtering by a subset of versions only yields lines inserted by
    /// those versions.
    #[test]
    fn iter_lines_filters_by_version() {
        let mut wf = WeaveFile::default();
        wf.add(Some(b"v0"), &ls(&[b"a\n", b"b\n"]), &[], None, None)
            .unwrap();
        wf.add(
            Some(b"v1"),
            &ls(&[b"a\n", b"b\n", b"c\n"]),
            &[0],
            None,
            None,
        )
        .unwrap();
        let names: Vec<&[u8]> = vec![b"v1"];
        let got = wf
            .iter_lines_added_or_present_in_versions(Some(names))
            .unwrap()
            .collect::<Vec<_>>();
        assert_eq!(got, vec![(b"c\n".to_vec(), b"v1".to_vec())]);
    }

    /// `None` for `version_names` means "all versions".
    #[test]
    fn iter_lines_all_versions() {
        let mut wf = WeaveFile::default();
        wf.add(Some(b"v0"), &ls(&[b"a\n"]), &[], None, None)
            .unwrap();
        wf.add(Some(b"v1"), &ls(&[b"a\n", b"b\n"]), &[0], None, None)
            .unwrap();
        let got = wf
            .iter_lines_added_or_present_in_versions::<std::iter::Empty<&[u8]>>(None)
            .unwrap()
            .collect::<Vec<_>>();
        assert_eq!(
            got,
            vec![
                (b"a\n".to_vec(), b"v0".to_vec()),
                (b"b\n".to_vec(), b"v1".to_vec()),
            ]
        );
    }

    /// `plan_merge` between two siblings of the same base reports
    /// each new line as `new-a` or `new-b`.
    #[test]
    fn plan_merge_disjoint_additions() {
        let mut wf = WeaveFile::default();
        wf.add(Some(b"base"), &ls(&[b"shared\n"]), &[], None, None)
            .unwrap();
        wf.add(
            Some(b"a"),
            &ls(&[b"shared\n", b"from-a\n"]),
            &[0],
            None,
            None,
        )
        .unwrap();
        wf.add(
            Some(b"b"),
            &ls(&[b"shared\n", b"from-b\n"]),
            &[0],
            None,
            None,
        )
        .unwrap();
        let plan = wf.plan_merge(b"a", b"b").unwrap();
        let by_state: Vec<(&'static [u8], &[u8])> =
            plan.iter().map(|(s, l)| (s.tag(), l.as_slice())).collect();
        assert!(by_state.contains(&(b"unchanged", b"shared\n".as_slice())));
        assert!(by_state.contains(&(b"new-a", b"from-a\n".as_slice())));
        assert!(by_state.contains(&(b"new-b", b"from-b\n".as_slice())));
    }

    /// `plan_merge` reports a base-killed line when both branches have
    /// dropped the same content.
    #[test]
    fn plan_merge_killed_both() {
        let mut wf = WeaveFile::default();
        wf.add(Some(b"base"), &ls(&[b"keep\n", b"drop\n"]), &[], None, None)
            .unwrap();
        wf.add(Some(b"a"), &ls(&[b"keep\n"]), &[0], None, None)
            .unwrap();
        wf.add(Some(b"b"), &ls(&[b"keep\n"]), &[0], None, None)
            .unwrap();
        let plan = wf.plan_merge(b"a", b"b").unwrap();
        let drops: Vec<&'static [u8]> = plan
            .iter()
            .filter(|(_, l)| l == b"drop\n")
            .map(|(s, _)| s.tag())
            .collect();
        // The dropped line is reported once with state killed-both.
        assert_eq!(drops, vec![b"killed-both"]);
    }

    /// `check` accepts a freshly-built weave that round-trips correctly.
    #[test]
    fn check_passes_on_clean_weave() {
        let mut wf = WeaveFile::default();
        wf.add(Some(b"v0"), &ls(&[b"a\n"]), &[], None, None)
            .unwrap();
        wf.add(Some(b"v1"), &ls(&[b"a\n", b"b\n"]), &[0], None, None)
            .unwrap();
        wf.check().unwrap();
    }

    /// `check` rejects a weave whose stored sha1 doesn't match the text
    /// it would actually produce. Mirrors `JoinWeavesTests.test_written_detection`.
    #[test]
    fn check_rejects_corrupt_sha1() {
        let mut wf = WeaveFile::default();
        wf.add(Some(b"v0"), &ls(&[b"a\n"]), &[], None, None)
            .unwrap();
        // Tamper with the stored sha1 for v0.
        wf.sha1s[0] = b"deadbeefdeadbeefdeadbeefdeadbeefdeadbeef".to_vec();
        let err = wf.check().unwrap_err();
        assert!(matches!(
            err,
            WeaveError::InvalidChecksum { version: 0, .. }
        ));
    }

    /// `check` rejects a parents table where any parent index isn't strictly
    /// less than its child.
    #[test]
    fn check_rejects_acyclic_violation() {
        let mut wf = WeaveFile::default();
        wf.add(Some(b"v0"), &ls(&[b"a\n"]), &[], None, None)
            .unwrap();
        wf.add(Some(b"v1"), &ls(&[b"a\n"]), &[0], None, None)
            .unwrap();
        // Now manually introduce an invalid self-parent.
        wf.parents[1] = vec![1];
        let err = wf.check().unwrap_err();
        assert_eq!(err, WeaveError::Acyclic { version: 1, max: 1 });
    }

    /// `imported_parents` maps `other`'s parent indices to `self`'s, by
    /// version name.
    #[test]
    fn imported_parents_translates_indices() {
        let mut wa = WeaveFile::default();
        wa.add(Some(b"v0"), &ls(&[b"a\n"]), &[], None, None)
            .unwrap();
        wa.add(Some(b"v1"), &ls(&[b"a\n", b"b\n"]), &[0], None, None)
            .unwrap();
        let mut wb = WeaveFile::default();
        // Different ordering in wb.
        wb.add(Some(b"v1"), &ls(&[b"x\n"]), &[], None, None)
            .unwrap();
        wb.add(Some(b"v0"), &ls(&[b"a\n"]), &[], None, None)
            .unwrap();

        // wa.imported_parents(wb, 0) — wb[0]'s parents in wb are [], so
        // the result is also empty.
        let got = wa.imported_parents(&wb, 0).unwrap();
        assert!(got.is_empty());
    }

    /// `imported_parents` errors if a parent in `other` is missing from `self`.
    #[test]
    fn imported_parents_missing_parent_errors() {
        let mut wa = WeaveFile::default();
        wa.add(Some(b"v0"), &ls(&[b"a\n"]), &[], None, None)
            .unwrap();

        let mut wb = WeaveFile::default();
        wb.add(Some(b"orphan"), &ls(&[b"x\n"]), &[], None, None)
            .unwrap();
        wb.add(Some(b"v0"), &ls(&[b"a\n"]), &[0], None, None)
            .unwrap();
        // wb's v0 has parent "orphan" which doesn't exist in wa.
        let err = wa.imported_parents(&wb, 1).unwrap_err();
        assert!(matches!(err, WeaveError::MissingParent { .. }));
    }

    /// `check_version_consistent` returns Ok(false) for versions absent
    /// from `self`, Ok(true) when names match and parents are subset-OK,
    /// and errors when sha1s differ.
    #[test]
    fn check_version_consistent_states() {
        let mut wa = WeaveFile::default();
        wa.add(Some(b"v0"), &ls(&[b"a\n"]), &[], None, None)
            .unwrap();
        let mut wb = WeaveFile::default();
        wb.add(Some(b"v0"), &ls(&[b"a\n"]), &[], None, None)
            .unwrap();
        wb.add(Some(b"v1"), &ls(&[b"a\n", b"b\n"]), &[0], None, None)
            .unwrap();

        // wb has v1 that wa doesn't — wa.check_version_consistent(wb, 1, "v1") -> Ok(false).
        assert_eq!(wa.check_version_consistent(&wb, 1, b"v1").unwrap(), false);

        // Both have v0 with identical content — Ok(true).
        assert_eq!(wa.check_version_consistent(&wb, 0, b"v0").unwrap(), true);

        // Tamper with wb's v0 sha to force a TextDiffers.
        wb.sha1s[0] = b"deadbeefdeadbeefdeadbeefdeadbeefdeadbeef".to_vec();
        let err = wa.check_version_consistent(&wb, 0, b"v0").unwrap_err();
        assert_eq!(err, WeaveError::TextDiffers(b"v0".to_vec()));
    }

    /// `reweave` of two weaves sharing a common base produces a weave
    /// that contains every version from both inputs.
    #[test]
    fn reweave_merges_disjoint_branches() {
        let mut wa = WeaveFile::default();
        wa.add(Some(b"v0"), &ls(&[b"a\n"]), &[], None, None)
            .unwrap();
        wa.add(
            Some(b"a-only"),
            &ls(&[b"a\n", b"alpha\n"]),
            &[0],
            None,
            None,
        )
        .unwrap();

        let mut wb = WeaveFile::default();
        wb.add(Some(b"v0"), &ls(&[b"a\n"]), &[], None, None)
            .unwrap();
        wb.add(Some(b"b-only"), &ls(&[b"a\n", b"beta\n"]), &[0], None, None)
            .unwrap();

        let result = reweave(&wa, &wb).unwrap();
        let mut names = result.versions();
        names.sort();
        assert_eq!(
            names,
            vec![b"a-only".to_vec(), b"b-only".to_vec(), b"v0".to_vec()]
        );
        // Round-trip text from both branches.
        let i = result.lookup(b"a-only").unwrap();
        assert_eq!(result.get_lines(i).unwrap(), ls(&[b"a\n", b"alpha\n"]));
        let j = result.lookup(b"b-only").unwrap();
        assert_eq!(result.get_lines(j).unwrap(), ls(&[b"a\n", b"beta\n"]));
    }

    /// `order_record_stream` topological: parents come before children;
    /// unknown names land at the end in input order.
    #[test]
    fn order_record_stream_topological() {
        let mut wf = WeaveFile::default();
        wf.add(Some(b"a"), &ls(&[b"a\n"]), &[], None, None).unwrap();
        wf.add(Some(b"b"), &ls(&[b"a\n", b"b\n"]), &[0], None, None)
            .unwrap();
        wf.add(Some(b"c"), &ls(&[b"a\n", b"b\n", b"c\n"]), &[1], None, None)
            .unwrap();
        // Input order is leaf-first, plus an unknown.
        let names: Vec<Vec<u8>> = vec![
            b"c".to_vec(),
            b"a".to_vec(),
            b"missing".to_vec(),
            b"b".to_vec(),
        ];
        let got = order_record_stream(&wf, &names, "topological").unwrap();
        // Topological subset is [a, b, c] (parents before children);
        // unknowns appended preserving order.
        assert_eq!(
            got,
            vec![
                b"a".to_vec(),
                b"b".to_vec(),
                b"c".to_vec(),
                b"missing".to_vec(),
            ]
        );
    }

    /// `order_record_stream` unordered preserves input order verbatim.
    #[test]
    fn order_record_stream_unordered() {
        let mut wf = WeaveFile::default();
        wf.add(Some(b"a"), &ls(&[b"a\n"]), &[], None, None).unwrap();
        wf.add(Some(b"b"), &ls(&[b"a\n", b"b\n"]), &[0], None, None)
            .unwrap();
        let names: Vec<Vec<u8>> = vec![b"b".to_vec(), b"a".to_vec()];
        assert_eq!(
            order_record_stream(&wf, &names, "unordered").unwrap(),
            vec![b"b".to_vec(), b"a".to_vec()]
        );
    }

    /// `order_record_stream` rejects unknown ordering names.
    #[test]
    fn order_record_stream_rejects_unknown_ordering() {
        let wf = WeaveFile::default();
        assert!(order_record_stream(&wf, &[], "bogus").is_none());
    }

    /// `reweave` errors out if the two inputs disagree on the text of a
    /// shared version. Mirrors the Python `WeaveTextDiffers` raise.
    #[test]
    fn reweave_text_diffs_error() {
        let mut wa = WeaveFile::default();
        wa.add(Some(b"v0"), &ls(&[b"hello\n"]), &[], None, None)
            .unwrap();
        let mut wb = WeaveFile::default();
        wb.add(Some(b"v0"), &ls(&[b"goodbye\n"]), &[], None, None)
            .unwrap();
        let err = reweave(&wa, &wb).unwrap_err();
        assert_eq!(err, WeaveError::TextDiffers(b"v0".to_vec()));
    }

    // ----------------------------------------------------------------
    // Tests below were ported from `bzrformats/tests/test_weave.py` —
    // they assemble `WeaveFile` literals directly to verify reading
    // behavior on shapes that aren't reachable through the normal
    // `add`/`add_lines` flow. The Python originals poked at private
    // attributes (`_weave`, `_parents`, `_sha1s`); they live here now
    // because the pyclass exposes those fields read-only.
    // ----------------------------------------------------------------

    /// Round-trip equality regression: a weave built with `add` and the
    /// same weave parsed from its v5 serialization must compare equal.
    /// Mirrors what the `Weave` Python `__eq__` is supposed to do.
    #[test]
    fn round_trip_equality() {
        let mut w1 = WeaveFile::default();
        w1.add(Some(b"text0"), &[b"header".to_vec()], &[], None, None)
            .unwrap();
        w1.add(
            Some(b"text1"),
            &[b"header".to_vec(), b"".to_vec(), b"line from 1".to_vec()],
            &[0],
            None,
            None,
        )
        .unwrap();
        let bytes = write_weave_v5(&w1);
        let w2 = read_weave_v5(&bytes).unwrap();
        assert_eq!(w1.parents, w2.parents);
        assert_eq!(w1.sha1s, w2.sha1s);
        assert_eq!(w1.names, w2.names);
        assert_eq!(w1.weave, w2.weave);
        assert_eq!(w1, w2);
    }

    /// Mirrors `test_weave.CannedDelete`: a weave with a delete bracket
    /// produces the deleted line for v0 and skips it for v1.
    #[test]
    fn canned_delete_round_trip() {
        let lines_v0 = ls(&[b"first line", b"line to be deleted", b"last line"]);
        let lines_v1 = ls(&[b"first line", b"last line"]);
        let weave_body = vec![
            ctl(Instruction::InsertOpen, 0),
            line(b"first line"),
            ctl(Instruction::DeleteOpen, 1),
            line(b"line to be deleted"),
            ctl(Instruction::DeleteClose, 1),
            line(b"last line"),
            ctl(Instruction::InsertClose, 0),
        ];
        let wf = WeaveFile {
            parents: vec![vec![], vec![0]],
            sha1s: vec![sha_strings(&lines_v0), sha_strings(&lines_v1)],
            names: vec![b"v0".to_vec(), b"v1".to_vec()],
            weave: weave_body,
        };
        assert_eq!(wf.get_lines(0).unwrap(), lines_v0);
        assert_eq!(wf.get_lines(1).unwrap(), lines_v1);
    }

    /// Mirrors `test_weave.CannedReplacement`: deletion plus a
    /// fresh insertion under the same version replaces the line.
    #[test]
    fn canned_replacement_round_trip() {
        let lines_v0 = ls(&[b"first line", b"line to be deleted", b"last line"]);
        let lines_v1 = ls(&[b"first line", b"replacement line", b"last line"]);
        let weave_body = vec![
            ctl(Instruction::InsertOpen, 0),
            line(b"first line"),
            ctl(Instruction::DeleteOpen, 1),
            line(b"line to be deleted"),
            ctl(Instruction::DeleteClose, 1),
            ctl(Instruction::InsertOpen, 1),
            line(b"replacement line"),
            ctl(Instruction::InsertClose, 1),
            line(b"last line"),
            ctl(Instruction::InsertClose, 0),
        ];
        let wf = WeaveFile {
            parents: vec![vec![], vec![0]],
            sha1s: vec![sha_strings(&lines_v0), sha_strings(&lines_v1)],
            names: vec![b"v0".to_vec(), b"v1".to_vec()],
            weave: weave_body,
        };
        assert_eq!(wf.get_lines(0).unwrap(), lines_v0);
        assert_eq!(wf.get_lines(1).unwrap(), lines_v1);
    }

    /// Mirrors `test_weave.InsertNested`: insertions can nest and each
    /// version's reconstructed text only includes the blocks whose
    /// open-instruction is in its ancestry.
    #[test]
    fn insert_nested_round_trip() {
        let v0 = ls(&[b"foo {", b"}"]);
        let v1 = ls(&[b"foo {", b"  added in version 1", b"  also from v1", b"}"]);
        let v2 = ls(&[b"foo {", b"  added in v2", b"}"]);
        let v3 = ls(&[
            b"foo {",
            b"  added in version 1",
            b"  added in v2",
            b"  also from v1",
            b"}",
        ]);
        let weave_body = vec![
            ctl(Instruction::InsertOpen, 0),
            line(b"foo {"),
            ctl(Instruction::InsertOpen, 1),
            line(b"  added in version 1"),
            ctl(Instruction::InsertOpen, 2),
            line(b"  added in v2"),
            ctl(Instruction::InsertClose, 2),
            line(b"  also from v1"),
            ctl(Instruction::InsertClose, 1),
            line(b"}"),
            ctl(Instruction::InsertClose, 0),
        ];
        let wf = WeaveFile {
            parents: vec![vec![], vec![0], vec![0], vec![0, 1, 2]],
            sha1s: vec![
                sha_strings(&v0),
                sha_strings(&v1),
                sha_strings(&v2),
                sha_strings(&v3),
            ],
            names: vec![
                b"v0".to_vec(),
                b"v1".to_vec(),
                b"v2".to_vec(),
                b"v3".to_vec(),
            ],
            weave: weave_body,
        };
        assert_eq!(wf.get_lines(0).unwrap(), v0);
        assert_eq!(wf.get_lines(1).unwrap(), v1);
        assert_eq!(wf.get_lines(2).unwrap(), v2);
        assert_eq!(wf.get_lines(3).unwrap(), v3);
    }

    /// Mirrors `test_weave.IncludeVersions`: a v1 insertion outside the
    /// v0 insertion still attaches to the right version when extracted.
    #[test]
    fn include_versions_round_trip() {
        let v0 = ls(&[b"first line"]);
        let v01 = ls(&[b"first line", b"second line"]);
        let weave_body = vec![
            ctl(Instruction::InsertOpen, 0),
            line(b"first line"),
            ctl(Instruction::InsertClose, 0),
            ctl(Instruction::InsertOpen, 1),
            line(b"second line"),
            ctl(Instruction::InsertClose, 1),
        ];
        let wf = WeaveFile {
            parents: vec![vec![], vec![0]],
            sha1s: vec![sha_strings(&v0), sha_strings(&v01)],
            names: vec![b"v0".to_vec(), b"v1".to_vec()],
            weave: weave_body,
        };
        assert_eq!(wf.get_lines(0).unwrap(), v0);
        assert_eq!(wf.get_lines(1).unwrap(), v01);
    }

    /// Mirrors `test_weave.DivergedIncludes`: two siblings of the same
    /// base each get their own additional line when extracted, and
    /// `get_ancestry` reports the right ancestor name set.
    #[test]
    fn diverged_includes_round_trip() {
        let v0 = ls(&[b"first line"]);
        let v01 = ls(&[b"first line", b"second line"]);
        let v02 = ls(&[b"first line", b"alternative second line"]);
        let weave_body = vec![
            ctl(Instruction::InsertOpen, 0),
            line(b"first line"),
            ctl(Instruction::InsertClose, 0),
            ctl(Instruction::InsertOpen, 1),
            line(b"second line"),
            ctl(Instruction::InsertClose, 1),
            ctl(Instruction::InsertOpen, 2),
            line(b"alternative second line"),
            ctl(Instruction::InsertClose, 2),
        ];
        let wf = WeaveFile {
            parents: vec![vec![], vec![0], vec![0]],
            sha1s: vec![sha_strings(&v0), sha_strings(&v01), sha_strings(&v02)],
            names: vec![b"0".to_vec(), b"1".to_vec(), b"2".to_vec()],
            weave: weave_body,
        };
        assert_eq!(wf.get_lines(0).unwrap(), v0);
        assert_eq!(wf.get_lines(1).unwrap(), v01);
        assert_eq!(wf.get_lines(2).unwrap(), v02);
        let ancestry: Vec<&[u8]> = vec![b"2"];
        let mut got = wf.get_ancestry(ancestry).unwrap();
        got.sort();
        assert_eq!(got, vec![b"0".to_vec(), b"2".to_vec()]);
    }
}