// 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. #![allow(missing_docs)] use std::borrow::Borrow;use std::collections::VecDeque;use std::iter;use std::mem; use bstr::BStr;use bstr::BString;use itertools::Itertools as _; use crate::diff::Diff;use crate::diff::DiffHunk;use crate::diff::DiffHunkKind;use crate::merge::Merge; /// 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 {        DiffLine {            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![],        };        DiffLineIterator {            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,            }        }    })} /// 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>) -> MergeResult {    merge_inner(inputs)} /// 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>) -> Merge<BString> {    merge_inner(inputs)} /// 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>) -> Option<BString> {    merge_inner(inputs)} fn merge_inner<'input, T: AsRef<[u8]>, B: FromMergeHunks<'input>>(inputs: &'input Merge<T>) -> B {    // 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 = Diff::by_line(inputs.removes().chain(inputs.adds()));    let hunks = resolve_diff_hunks(&diff, num_diffs);    B::from_hunks(hunks)} /// `FromIterator` for merge result.trait FromMergeHunks<'input>: Sized {    fn from_hunks<I: IntoIterator<Item = Merge<&'input BStr>>>(hunks: I) -> Self;} impl<'input> FromMergeHunks<'input> for MergeResult {    fn from_hunks<I: IntoIterator<Item = Merge<&'input BStr>>>(hunks: I) -> Self {        collect_hunks(hunks)    }} impl<'input> FromMergeHunks<'input> for Merge<BString> {    fn from_hunks<I: IntoIterator<Item = Merge<&'input BStr>>>(hunks: I) -> Self {        collect_merged(hunks)    }} impl<'input> FromMergeHunks<'input> for Option<BString> {    fn from_hunks<I: IntoIterator<Item = Merge<&'input BStr>>>(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 = Merge<&'input BStr>>) -> 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.map(|&s| s.to_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 = Merge<&'input BStr>>) -> Merge<BString> {    let mut maybe_resolved = Merge::resolved(BString::default());    for hunk in hunks {        if let Some(&content) = hunk.as_resolved() {            for buf in maybe_resolved.iter_mut() {                buf.extend_from_slice(content);            }        } else {            maybe_resolved = match maybe_resolved.into_resolved() {                Ok(content) => Merge::from_vec(vec![content; hunk.as_slice().len()]),                Err(conflict) => conflict,            };            assert_eq!(maybe_resolved.as_slice().len(), hunk.as_slice().len());            for (buf, s) in iter::zip(maybe_resolved.iter_mut(), hunk) {                buf.extend_from_slice(s);            }        }    }    maybe_resolved} /// Collects resolved merge hunks. Short-circuits on unresolved hunk.fn collect_resolved<'input>(    hunks: impl IntoIterator<Item = Merge<&'input BStr>>,) -> Option<BString> {    hunks        .into_iter()        .map(|hunk| hunk.into_resolved().ok())        .collect()} /// Iterator that attempts to resolve trivial merge conflict for each hunk.fn resolve_diff_hunks<'a, 'input>(    diff: &'a Diff<'input>,    num_diffs: usize,) -> impl Iterator<Item = Merge<&'input BStr>> + use<'a, 'input> {    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() {                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> {        Merge::resolved(hunk(value))    }     fn hunk(data: &[u8]) -> BString {        data.into()    }     #[test]    fn test_diff_line_iterator_line_numbers() {        let mut line_iter = DiffLineIterator::with_line_number(            [DiffHunk::different(["a\nb", "c\nd\n"])].into_iter(),            DiffLineNumber { left: 1, right: 10 },        );        // Nothing queued        assert_eq!(            line_iter.next_line_number(),            DiffLineNumber { left: 1, right: 10 }        );        assert_eq!(            line_iter.next().unwrap(),            DiffLine {                line_number: DiffLineNumber { left: 1, right: 10 },                hunks: vec![(DiffLineHunkSide::Left, "a\n".as_ref())],            }        );        // Multiple lines queued        assert_eq!(            line_iter.next_line_number(),            DiffLineNumber { left: 2, right: 10 }        );        assert_eq!(            line_iter.next().unwrap(),            DiffLine {                line_number: DiffLineNumber { left: 2, right: 10 },                hunks: vec![                    (DiffLineHunkSide::Left, "b".as_ref()),                    (DiffLineHunkSide::Right, "c\n".as_ref()),                ],            }        );        // Single line queued        assert_eq!(            line_iter.next_line_number(),            DiffLineNumber { left: 2, right: 11 }        );        assert_eq!(            line_iter.next().unwrap(),            DiffLine {                line_number: DiffLineNumber { left: 2, right: 11 },                hunks: vec![(DiffLineHunkSide::Right, "d\n".as_ref())],            }        );        // No more lines: left remains 2 as it lacks newline        assert_eq!(            line_iter.next_line_number(),            DiffLineNumber { left: 2, right: 12 }        );        assert!(line_iter.next().is_none());        assert_eq!(            line_iter.next_line_number(),            DiffLineNumber { left: 2, right: 12 }        );    }     #[test]    fn test_diff_line_iterator_blank_right_line_single_left() {        let mut line_iter = DiffLineIterator::new(            [                DiffHunk::matching(["a"].repeat(2)),                DiffHunk::different(["x\n", "\ny\n"]),            ]            .into_iter(),        );        assert_eq!(            line_iter.next().unwrap(),            DiffLine {                line_number: DiffLineNumber { left: 1, right: 1 },                hunks: vec![

Lines 1–500 of 990. Load more