// Copyright 2020 The Jujutsu Authors//// Licensed under the Apache License, Version 2.0 (the "License");// you may not use this file except in compliance with the License.// You may obtain a copy of the License at//// https://www.apache.org/licenses/LICENSE-2.0//// Unless required by applicable law or agreed to in writing, software// distributed under the License is distributed on an "AS IS" BASIS,// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.// See the License for the specific language governing permissions and// limitations under the License. #![expect(missing_docs)] use std::borrow::Borrow;use std::collections::VecDeque;use std::iter;use std::mem; use bstr::BStr;use bstr::BString;use either::Either;use itertools::Itertools as _; use crate::diff::ContentDiff;use crate::diff::DiffHunk;use crate::diff::DiffHunkKind;use crate::merge::Merge;use crate::merge::SameChange;use crate::tree_merge::MergeOptions; /// A diff line which may contain small hunks originating from both sides.#[derive(PartialEq, Eq, Clone, Debug)]pub struct DiffLine<'a> {    pub line_number: DiffLineNumber,    pub hunks: Vec<(DiffLineHunkSide, &'a BStr)>,} impl DiffLine<'_> {    pub fn has_left_content(&self) -> bool {        self.hunks            .iter()            .any(|&(side, _)| side != DiffLineHunkSide::Right)    }     pub fn has_right_content(&self) -> bool {        self.hunks            .iter()            .any(|&(side, _)| side != DiffLineHunkSide::Left)    }     pub fn is_unmodified(&self) -> bool {        self.hunks            .iter()            .all(|&(side, _)| side == DiffLineHunkSide::Both)    }     fn take(&mut self) -> Self {        Self {            line_number: self.line_number,            hunks: mem::take(&mut self.hunks),        }    }} #[derive(Clone, Copy, Debug, Eq, PartialEq)]pub struct DiffLineNumber {    pub left: u32,    pub right: u32,} /// Which side a `DiffLine` hunk belongs to?#[derive(Clone, Copy, Debug, Eq, PartialEq)]pub enum DiffLineHunkSide {    Both,    Left,    Right,} pub struct DiffLineIterator<'a, I> {    diff_hunks: iter::Fuse<I>,    current_line: DiffLine<'a>,    queued_lines: VecDeque<DiffLine<'a>>,} impl<'a, I> DiffLineIterator<'a, I>where    I: Iterator,    I::Item: Borrow<DiffHunk<'a>>,{    /// Iterates `diff_hunks` by line. Each hunk should have exactly two inputs.    pub fn new(diff_hunks: I) -> Self {        let line_number = DiffLineNumber { left: 1, right: 1 };        Self::with_line_number(diff_hunks, line_number)    }     /// Iterates `diff_hunks` by line. Each hunk should have exactly two inputs.    /// Hunk's line numbers start from the given `line_number`.    pub fn with_line_number(diff_hunks: I, line_number: DiffLineNumber) -> Self {        let current_line = DiffLine {            line_number,            hunks: vec![],        };        Self {            diff_hunks: diff_hunks.fuse(),            current_line,            queued_lines: VecDeque::new(),        }    }} impl<I> DiffLineIterator<'_, I> {    /// Returns line number of the next hunk. After all hunks are consumed, this    /// returns the next line number if the last hunk ends with newline.    pub fn next_line_number(&self) -> DiffLineNumber {        let next_line = self.queued_lines.front().unwrap_or(&self.current_line);        next_line.line_number    }} impl<'a, I> Iterator for DiffLineIterator<'a, I>where    I: Iterator,    I::Item: Borrow<DiffHunk<'a>>,{    type Item = DiffLine<'a>;     fn next(&mut self) -> Option<Self::Item> {        // TODO: Should we attempt to interpret as utf-8 and otherwise break only at        // newlines?        while self.queued_lines.is_empty() {            let Some(hunk) = self.diff_hunks.next() else {                break;            };            let hunk = hunk.borrow();            match hunk.kind {                DiffHunkKind::Matching => {                    // TODO: add support for unmatched contexts?                    debug_assert!(hunk.contents.iter().all_equal());                    let text = hunk.contents[0];                    let lines = text.split_inclusive(|b| *b == b'\n').map(BStr::new);                    for line in lines {                        self.current_line.hunks.push((DiffLineHunkSide::Both, line));                        if line.ends_with(b"\n") {                            self.queued_lines.push_back(self.current_line.take());                            self.current_line.line_number.left += 1;                            self.current_line.line_number.right += 1;                        }                    }                }                DiffHunkKind::Different => {                    let [left_text, right_text] = hunk.contents[..]                        .try_into()                        .expect("hunk should have exactly two inputs");                    let left_lines = left_text.split_inclusive(|b| *b == b'\n').map(BStr::new);                    for left_line in left_lines {                        self.current_line                            .hunks                            .push((DiffLineHunkSide::Left, left_line));                        if left_line.ends_with(b"\n") {                            self.queued_lines.push_back(self.current_line.take());                            self.current_line.line_number.left += 1;                        }                    }                    let mut right_lines =                        right_text.split_inclusive(|b| *b == b'\n').map(BStr::new);                    // Omit blank right line if matching hunk of the same line                    // number has already been queued. Here we only need to                    // check the first queued line since the other lines should                    // be created in the left_lines loop above.                    if right_text.starts_with(b"\n")                        && self.current_line.hunks.is_empty()                        && self                            .queued_lines                            .front()                            .is_some_and(|queued| queued.has_right_content())                    {                        let blank_line = right_lines.next().unwrap();                        assert_eq!(blank_line, b"\n");                        self.current_line.line_number.right += 1;                    }                    for right_line in right_lines {                        self.current_line                            .hunks                            .push((DiffLineHunkSide::Right, right_line));                        if right_line.ends_with(b"\n") {                            self.queued_lines.push_back(self.current_line.take());                            self.current_line.line_number.right += 1;                        }                    }                }            }        }         if let Some(line) = self.queued_lines.pop_front() {            return Some(line);        }         if !self.current_line.hunks.is_empty() {            return Some(self.current_line.take());        }         None    }} /// Diff hunk that may be unresolved conflicts.#[derive(Clone, Debug, Eq, PartialEq)]pub struct ConflictDiffHunk<'input> {    pub kind: DiffHunkKind,    pub lefts: Merge<&'input BStr>,    pub rights: Merge<&'input BStr>,} /// Iterator adaptor that translates non-conflict hunks to resolved `Merge`.////// Trivial conflicts in the diff inputs should have been resolved by caller.pub fn conflict_diff_hunks<'input, I>(    diff_hunks: I,    num_lefts: usize,) -> impl Iterator<Item = ConflictDiffHunk<'input>>where    I: IntoIterator,    I::Item: Borrow<DiffHunk<'input>>,{    fn to_merge<'input>(contents: &[&'input BStr]) -> Merge<&'input BStr> {        // Not using trivial_merge() so that the original content can be        // reproduced by concatenating hunks.        if contents.iter().all_equal() {            Merge::resolved(contents[0])        } else {            Merge::from_vec(contents)        }    }     diff_hunks.into_iter().map(move |hunk| {        let hunk = hunk.borrow();        let (lefts, rights) = hunk.contents.split_at(num_lefts);        if let ([left], [right]) = (lefts, rights) {            // Non-conflicting diff shouldn't have identical contents            ConflictDiffHunk {                kind: hunk.kind,                lefts: Merge::resolved(left),                rights: Merge::resolved(right),            }        } else {            let lefts = to_merge(lefts);            let rights = to_merge(rights);            let kind = match hunk.kind {                DiffHunkKind::Matching => DiffHunkKind::Matching,                DiffHunkKind::Different if lefts == rights => DiffHunkKind::Matching,                DiffHunkKind::Different => DiffHunkKind::Different,            };            ConflictDiffHunk {                kind,                lefts,                rights,            }        }    })} /// Granularity of hunks when merging files.#[derive(Clone, Copy, Debug, Eq, PartialEq, serde::Deserialize)]#[serde(rename_all = "kebab-case")]pub enum FileMergeHunkLevel {    /// Splits into line hunks.    Line,    /// Splits into word hunks.    Word,} /// Merge result in either fully-resolved or conflicts form, akin to/// `Result<BString, Vec<Merge<BString>>>`.#[derive(PartialEq, Eq, Clone, Debug)]pub enum MergeResult {    /// Resolved content if inputs can be merged successfully.    Resolved(BString),    /// List of partially-resolved hunks if some of them cannot be merged.    Conflict(Vec<Merge<BString>>),} /// Splits `inputs` into hunks, resolves trivial merge conflicts for each.////// Returns either fully-resolved content or list of partially-resolved hunks.pub fn merge_hunks<T: AsRef<[u8]>>(inputs: &Merge<T>, options: &MergeOptions) -> MergeResult {    merge_inner(inputs, options)} /// Splits `inputs` into hunks, resolves trivial merge conflicts for each, then/// concatenates the outcome back to single `Merge` object.////// The returned merge object is either fully resolved or conflict having the/// same number of terms as the `inputs`.pub fn merge<T: AsRef<[u8]>>(inputs: &Merge<T>, options: &MergeOptions) -> Merge<BString> {    merge_inner(inputs, options)} /// Splits `inputs` into hunks, attempts to resolve trivial merge conflicts for/// each.////// If all input hunks can be merged successfully, returns the merged content.pub fn try_merge<T: AsRef<[u8]>>(inputs: &Merge<T>, options: &MergeOptions) -> Option<BString> {    merge_inner(inputs, options)} fn merge_inner<'input, T, B>(inputs: &'input Merge<T>, options: &MergeOptions) -> Bwhere    T: AsRef<[u8]>,    B: FromMergeHunks<'input>,{    // TODO: Using the first remove as base (first in the inputs) is how it's    // usually done for 3-way conflicts. Are there better heuristics when there are    // more than 3 parts?    let num_diffs = inputs.removes().len();    let diff = ContentDiff::by_line(inputs.removes().chain(inputs.adds()));    let hunks = resolve_diff_hunks(&diff, num_diffs, options.same_change);    match options.hunk_level {        FileMergeHunkLevel::Line => B::from_hunks(hunks.map(MergeHunk::Borrowed)),        FileMergeHunkLevel::Word => {            B::from_hunks(hunks.map(|h| merge_hunk_by_word(h, options.same_change)))        }    }} fn merge_hunk_by_word(inputs: Merge<&BStr>, same_change: SameChange) -> MergeHunk<'_> {    if inputs.is_resolved() {        return MergeHunk::Borrowed(inputs);    }    let num_diffs = inputs.removes().len();    let diff = ContentDiff::by_word(inputs.removes().chain(inputs.adds()));    let hunks = resolve_diff_hunks(&diff, num_diffs, same_change);    // We could instead use collect_merged() to return partially-merged hunk.    // This would be more consistent with the line-based merge function, but    // might produce surprising results. Partially-merged conflicts would be    // hard to review because they would have mixed contexts.    if let Some(content) = collect_resolved(hunks.map(MergeHunk::Borrowed)) {        MergeHunk::Owned(Merge::resolved(content))    } else {        drop(diff);        MergeHunk::Borrowed(inputs)    }} /// `Cow`-like type over `Merge<T>`.#[derive(Clone, Debug)]enum MergeHunk<'input> {    Borrowed(Merge<&'input BStr>),    Owned(Merge<BString>),} impl MergeHunk<'_> {    fn len(&self) -> usize {        match self {            MergeHunk::Borrowed(merge) => merge.as_slice().len(),            MergeHunk::Owned(merge) => merge.as_slice().len(),        }    }     fn iter(&self) -> impl Iterator<Item = &BStr> {        match self {            MergeHunk::Borrowed(merge) => Either::Left(merge.iter().copied()),            MergeHunk::Owned(merge) => Either::Right(merge.iter().map(Borrow::borrow)),        }    }     fn as_resolved(&self) -> Option<&BStr> {        match self {            MergeHunk::Borrowed(merge) => merge.as_resolved().copied(),            MergeHunk::Owned(merge) => merge.as_resolved().map(Borrow::borrow),        }    }     fn into_owned(self) -> Merge<BString> {        match self {            MergeHunk::Borrowed(merge) => merge.map(|&s| s.to_owned()),            MergeHunk::Owned(merge) => merge,        }    }} /// `FromIterator` for merge result.trait FromMergeHunks<'input>: Sized {    fn from_hunks<I: IntoIterator<Item = MergeHunk<'input>>>(hunks: I) -> Self;} impl<'input> FromMergeHunks<'input> for MergeResult {    fn from_hunks<I: IntoIterator<Item = MergeHunk<'input>>>(hunks: I) -> Self {        collect_hunks(hunks)    }} impl<'input> FromMergeHunks<'input> for Merge<BString> {    fn from_hunks<I: IntoIterator<Item = MergeHunk<'input>>>(hunks: I) -> Self {        collect_merged(hunks)    }} impl<'input> FromMergeHunks<'input> for Option<BString> {    fn from_hunks<I: IntoIterator<Item = MergeHunk<'input>>>(hunks: I) -> Self {        collect_resolved(hunks)    }} /// Collects merged hunks into either fully-resolved content or list of/// partially-resolved hunks.fn collect_hunks<'input>(hunks: impl IntoIterator<Item = MergeHunk<'input>>) -> MergeResult {    let mut resolved_hunk = BString::new(vec![]);    let mut merge_hunks: Vec<Merge<BString>> = vec![];    for hunk in hunks {        if let Some(content) = hunk.as_resolved() {            resolved_hunk.extend_from_slice(content);        } else {            if !resolved_hunk.is_empty() {                merge_hunks.push(Merge::resolved(resolved_hunk));                resolved_hunk = BString::new(vec![]);            }            merge_hunks.push(hunk.into_owned());        }    }     if merge_hunks.is_empty() {        MergeResult::Resolved(resolved_hunk)    } else {        if !resolved_hunk.is_empty() {            merge_hunks.push(Merge::resolved(resolved_hunk));        }        MergeResult::Conflict(merge_hunks)    }} /// Collects merged hunks back to single `Merge` object, duplicating resolved/// hunks to all positive and negative terms.fn collect_merged<'input>(hunks: impl IntoIterator<Item = MergeHunk<'input>>) -> Merge<BString> {    let mut maybe_resolved = Merge::resolved(BString::default());    for hunk in hunks {        if let Some(content) = hunk.as_resolved() {            for buf in &mut maybe_resolved {                buf.extend_from_slice(content);            }        } else {            maybe_resolved = match maybe_resolved.into_resolved() {                Ok(content) => Merge::from_vec(vec![content; hunk.len()]),                Err(conflict) => conflict,            };            assert_eq!(maybe_resolved.as_slice().len(), hunk.len());            for (buf, s) in iter::zip(&mut maybe_resolved, hunk.iter()) {                buf.extend_from_slice(s);            }        }    }    maybe_resolved} /// Collects resolved merge hunks. Short-circuits on unresolved hunk.fn collect_resolved<'input>(hunks: impl IntoIterator<Item = MergeHunk<'input>>) -> Option<BString> {    let mut resolved_content = BString::default();    for hunk in hunks {        resolved_content.extend_from_slice(hunk.as_resolved()?);    }    Some(resolved_content)} /// Iterator that attempts to resolve trivial merge conflict for each hunk.fn resolve_diff_hunks<'input>(    diff: &ContentDiff<'input>,    num_diffs: usize,    same_change: SameChange,) -> impl Iterator<Item = Merge<&'input BStr>> {    diff.hunks().map(move |diff_hunk| match diff_hunk.kind {        DiffHunkKind::Matching => {            debug_assert!(diff_hunk.contents.iter().all_equal());            Merge::resolved(diff_hunk.contents[0])        }        DiffHunkKind::Different => {            let merge = Merge::from_removes_adds(                diff_hunk.contents[..num_diffs].iter().copied(),                diff_hunk.contents[num_diffs..].iter().copied(),            );            match merge.resolve_trivial(same_change) {                Some(&content) => Merge::resolved(content),                None => merge,            }        }    })} #[cfg(test)]mod tests {    use indoc::indoc;     use super::*;     fn conflict<const N: usize>(values: [&[u8]; N]) -> Merge<BString> {        Merge::from_vec(values.map(hunk).to_vec())    }     fn resolved(value: &[u8]) -> Merge<BString> {

Lines 1–500 of 1109. Load more