mergiraf/mergiraf
mergiraf/mergiraf
9
213
Fork 45
Code Issues 51 Pull requests 7 Releases 19 Activity Actions

No spaces after lifetimes when a structured merge is rendered #170

New issue
Closed
opened 2025-01-27 13:59:01 +01:00 by ada4a · 12 comments
ada4a commented 2025-01-27 13:59:01 +01:00
Owner
Copy link

I've just got this while working on #169. I'll leave a not-quite-minimized example for now, and come back to this later.

// Base.rs
pub(crate) fn other_successors(&self, pcs: &PCS<'a>) -> Vec<&PCS<'a>> {
    self.parents
        .get(&pcs.parent)
        .iter()
        .filter(move |other| {
            other.successor != pcs.successor && other.predecessor == pcs.predecessor
        })
        .collect()
}

// Left.rs
pub(crate) fn other_successors<'s, 'b>(
    &'s self,
    pcs: &'b PCS<'a>,
) -> impl Iterator<Item = &PCS<'a>> + use<'s, 'a, 'b> {
    self.parents.get(&pcs.parent).iter().filter(move |other| {
        other.successor != pcs.successor && other.predecessor == pcs.predecessor
    })
}

// Right.rs
pub(crate) fn other_successors<'s, 'b>(
    &'s self,
    pcs: &'b PCS<'a>,
) -> impl Iterator<Item = &'s PCS<'a>> + use<'s, 'a, 'b> {
    self.parents.get(&pcs.parent).iter().filter(move |other| {
        other.successor != pcs.successor && other.predecessor == pcs.predecessor
    })
}

// Result.rs
pub(crate) fn other_successors<'s, 'b>(
    &'sself,
<<<<<<< Left.rs
    pcs: &'bPCS<'a>,) -> impl Iterator<Item = &PCS<'a>> + use<'s, 'a, 'b> {
||||||| Base.rs
    pcs: &'bPCS<'a>,) -> Vec<&PCS<'a>> {
=======
    pcs: &'bPCS<'a>,) -> impl Iterator<Item = &'s PCS<'a>> + use<'s, 'a, 'b> {
>>>>>>> Right.rs
    self.parents.get(&pcs.parent).iter().filter(move |other| {
        other.successor != pcs.successor && other.predecessor == pcs.predecessor
    })
}

// Expected.rs
pub(crate) fn other_successors<'s, 'b>(
    &'s self,
<<<<<<< Left.rs
    pcs: &'b PCS<'a>,) -> impl Iterator<Item = &PCS<'a>> + use<'s, 'a, 'b> {
||||||| Base.rs
    pcs: &'b PCS<'a>,) -> Vec<&PCS<'a>> {
=======
    pcs: &'b PCS<'a>,) -> impl Iterator<Item = &'s PCS<'a>> + use<'s, 'a, 'b> {
>>>>>>> Right.rs
    self.parents.get(&pcs.parent).iter().filter(move |other| {
        other.successor != pcs.successor && other.predecessor == pcs.predecessor
    })
}

The main differences are as follows:

Result.rs Expected.rs
&'sself &'s self
&'bPCS &'b PCS

Note that --compact has no effect on this -- &'bPCS<'a> just gets pulled out of the conflict, but still formatted incorrectly

I've just got this while working on #169. I'll leave a not-quite-minimized example for now, and come back to this later. ```rust // Base.rs pub(crate) fn other_successors(&self, pcs: &PCS<'a>) -> Vec<&PCS<'a>> { self.parents .get(&pcs.parent) .iter() .filter(move |other| { other.successor != pcs.successor && other.predecessor == pcs.predecessor }) .collect() } // Left.rs pub(crate) fn other_successors<'s, 'b>( &'s self, pcs: &'b PCS<'a>, ) -> impl Iterator<Item = &PCS<'a>> + use<'s, 'a, 'b> { self.parents.get(&pcs.parent).iter().filter(move |other| { other.successor != pcs.successor && other.predecessor == pcs.predecessor }) } // Right.rs pub(crate) fn other_successors<'s, 'b>( &'s self, pcs: &'b PCS<'a>, ) -> impl Iterator<Item = &'s PCS<'a>> + use<'s, 'a, 'b> { self.parents.get(&pcs.parent).iter().filter(move |other| { other.successor != pcs.successor && other.predecessor == pcs.predecessor }) } // Result.rs pub(crate) fn other_successors<'s, 'b>( &'sself, <<<<<<< Left.rs pcs: &'bPCS<'a>,) -> impl Iterator<Item = &PCS<'a>> + use<'s, 'a, 'b> { ||||||| Base.rs pcs: &'bPCS<'a>,) -> Vec<&PCS<'a>> { ======= pcs: &'bPCS<'a>,) -> impl Iterator<Item = &'s PCS<'a>> + use<'s, 'a, 'b> { >>>>>>> Right.rs self.parents.get(&pcs.parent).iter().filter(move |other| { other.successor != pcs.successor && other.predecessor == pcs.predecessor }) } // Expected.rs pub(crate) fn other_successors<'s, 'b>( &'s self, <<<<<<< Left.rs pcs: &'b PCS<'a>,) -> impl Iterator<Item = &PCS<'a>> + use<'s, 'a, 'b> { ||||||| Base.rs pcs: &'b PCS<'a>,) -> Vec<&PCS<'a>> { ======= pcs: &'b PCS<'a>,) -> impl Iterator<Item = &'s PCS<'a>> + use<'s, 'a, 'b> { >>>>>>> Right.rs self.parents.get(&pcs.parent).iter().filter(move |other| { other.successor != pcs.successor && other.predecessor == pcs.predecessor }) } ``` The main differences are as follows: | `Result.rs` | `Expected.rs` | |---------|---------| | `&'sself` | `&'s self` | | `&'bPCS` | `&'b PCS` | Note that `--compact` has no effect on this -- `&'bPCS<'a>` just gets pulled out of the conflict, but still formatted incorrectly
ada4a commented 2025-02-02 18:12:39 +01:00
Author
Owner
Copy link

Working on this. Current minified version:

// Base.rs
fn foo(&self) {}

// Left.rs
fn foo(&'s self) {}

// Right.rs
fn foo<'s>(&'s self) {}

// Result.rs
fn foo<'s>(&'sself) {}

// Expected.rs
fn foo<'s>(&'s self) {}

So it looks like it's important to have conflicts in both type parameters and regular parameters of the function -- otherwise, the whole parameters subtree gets printed as is? Ah, no, it's probably just that without the type parameter at Right.rs, the left and right sides become identical, and Mergiraf resolves the conflict trivially

Working on this. Current minified version: ```rust // Base.rs fn foo(&self) {} // Left.rs fn foo(&'s self) {} // Right.rs fn foo<'s>(&'s self) {} // Result.rs fn foo<'s>(&'sself) {} // Expected.rs fn foo<'s>(&'s self) {} ``` ~~So it looks like it's important to have conflicts in both type parameters and regular parameters of the function -- otherwise, the whole parameters subtree gets printed as is?~~ Ah, no, it's probably just that without the type parameter at `Right.rs`, the left and right sides become identical, and Mergiraf resolves the conflict trivially
ada4a commented 2025-02-02 19:41:55 +01:00
Author
Owner
Copy link

Ok so I think this actually uncovered some deeper problems in the logic flow.

The issue manifests itself during pretty-printing. This is how all the calls to MergedTree::pretty_print_recursive look:

[1]: mixed
[1, 1]: mixed
[1, 1, 1]: exact
[src/merged_tree.rs:299:36] tree_at_rev.reindented_source(&new_indentation) = "fn"
[1, 1, 2]: exact
[src/merged_tree.rs:299:36] tree_at_rev.reindented_source(&new_indentation) = "foo"
[1, 1, 3]: exact
[src/merged_tree.rs:299:36] tree_at_rev.reindented_source(&new_indentation) = "<'s>"
[1, 1, 4]: mixed
[1, 1, 4, 1]: exact
[src/merged_tree.rs:299:36] tree_at_rev.reindented_source(&new_indentation) = "("
[1, 1, 4, 2]: mixed
[1, 1, 4, 2, 1]: exact
[src/merged_tree.rs:299:36] tree_at_rev.reindented_source(&new_indentation) = "&"
[1, 1, 4, 2, 2]: conflict
[src/merged_tree.rs:372:21] Self::pretty_print_astnode_list(Revision::Base, base) = ""
[src/merged_tree.rs:373:21] Self::pretty_print_astnode_list(Revision::Left, left) = "'s"
[src/merged_tree.rs:374:21] Self::pretty_print_astnode_list(Revision::Right, right) = "'s"
[1, 1, 4, 2, 3]: exact
[src/merged_tree.rs:299:36] tree_at_rev.reindented_source(&new_indentation) = "self"
[1, 1, 4, 3]: exact
[src/merged_tree.rs:299:36] tree_at_rev.reindented_source(&new_indentation) = ")"
[1, 1, 5]: exact
[src/merged_tree.rs:299:36] tree_at_rev.reindented_source(&new_indentation) = "{}"

// the resulting `output`
MergedText { sections: [Merged(""), Merged(""), Merged(""), Merged("fn"), Merged(" "), Merged("foo"), Merged(""), Merged("<'s>"), Merged(""), Merged(""), Merged("("), Merged(""), Merged(""), Merged("&"), Merged(""), Merged("'s"), Merged(""), Merged("self"), Merged(""), Merged(")"), Merged(" "), Merged("{}"), Merged("\n")] }

(the [1,1,1] is an improvised call-stack, and after that comes the MergedTree kind)

The interesting step is 1.1.4.2.2: since the three sides were determined to nominally conflict, we have a MergedTree::Conflict. Because of that, when we then go to 1.1.4.2.3, previous_sibling is set to None. We call MergedTree::add_preceding_whitespace with that, therefore resort to looking up what the whitespace before self was in the conflict sides. That turns out to be "" (the whitespace between & and self in BASE I guess?). So that's what we push to output.

The interesting thing is that when we push_conflict during 1.1.4.2.2, the method is smart enough to realize that this is not a real conflict at all, and turns it into MergedText::Merged. But it would be nice if this realization was made earlier. That way, we would've passed Some(PreviousSibling("'s")) to MergedTree::add_preceding_whitespace, and (I'm guessing here), the method would've returned the correct whitespace of " ". The problem is that I'm not really sure where that would need to happen.

PS: This actually causes another problem elsewhere -- after we construct the merge, we proceed to calculate its conflict_{mass,count}. And the fake conflict becomes the sole reason why the merge gets marked as non-perfect, which means that we go on to do the (now pure) structured merge all over again, just to get the same exact result. Avoiding this waste would be one more reason for us to tackle this.

Ok so I think this actually uncovered some deeper problems in the logic flow. The issue manifests itself during pretty-printing. This is how all the calls to `MergedTree::pretty_print_recursive` look: ``` [1]: mixed [1, 1]: mixed [1, 1, 1]: exact [src/merged_tree.rs:299:36] tree_at_rev.reindented_source(&new_indentation) = "fn" [1, 1, 2]: exact [src/merged_tree.rs:299:36] tree_at_rev.reindented_source(&new_indentation) = "foo" [1, 1, 3]: exact [src/merged_tree.rs:299:36] tree_at_rev.reindented_source(&new_indentation) = "<'s>" [1, 1, 4]: mixed [1, 1, 4, 1]: exact [src/merged_tree.rs:299:36] tree_at_rev.reindented_source(&new_indentation) = "(" [1, 1, 4, 2]: mixed [1, 1, 4, 2, 1]: exact [src/merged_tree.rs:299:36] tree_at_rev.reindented_source(&new_indentation) = "&" [1, 1, 4, 2, 2]: conflict [src/merged_tree.rs:372:21] Self::pretty_print_astnode_list(Revision::Base, base) = "" [src/merged_tree.rs:373:21] Self::pretty_print_astnode_list(Revision::Left, left) = "'s" [src/merged_tree.rs:374:21] Self::pretty_print_astnode_list(Revision::Right, right) = "'s" [1, 1, 4, 2, 3]: exact [src/merged_tree.rs:299:36] tree_at_rev.reindented_source(&new_indentation) = "self" [1, 1, 4, 3]: exact [src/merged_tree.rs:299:36] tree_at_rev.reindented_source(&new_indentation) = ")" [1, 1, 5]: exact [src/merged_tree.rs:299:36] tree_at_rev.reindented_source(&new_indentation) = "{}" // the resulting `output` MergedText { sections: [Merged(""), Merged(""), Merged(""), Merged("fn"), Merged(" "), Merged("foo"), Merged(""), Merged("<'s>"), Merged(""), Merged(""), Merged("("), Merged(""), Merged(""), Merged("&"), Merged(""), Merged("'s"), Merged(""), Merged("self"), Merged(""), Merged(")"), Merged(" "), Merged("{}"), Merged("\n")] } ``` (the `[1,1,1]` is an improvised call-stack, and after that comes the `MergedTree` kind) The interesting step is 1.1.4.2.2: since the three sides were determined to nominally conflict, we have a `MergedTree::Conflict`. Because of that, when we then go to 1.1.4.2.3, `previous_sibling` is set to `None`. We call `MergedTree::add_preceding_whitespace` with that, therefore resort to looking up what the whitespace before `self` was in the conflict sides. That turns out to be `""` (the whitespace between `&` and `self` in BASE I guess?). So that's what we push to `output`. The interesting thing is that when we `push_conflict` during 1.1.4.2.2, the method is smart enough to realize that this is not a real conflict at all, and turns it into `MergedText::Merged`. But it would be nice if this realization was made earlier. That way, we would've passed `Some(PreviousSibling("'s"))` to `MergedTree::add_preceding_whitespace`, and (I'm guessing here), the method would've returned the correct whitespace of `" "`. The problem is that I'm not really sure where that would need to happen. PS: This actually causes another problem elsewhere -- after we construct the merge, we proceed to calculate its `conflict_{mass,count}`. And the fake conflict becomes the sole reason why the merge gets marked as non-perfect, which means that we go on to do the (now pure) structured merge all over again, just to get the same exact result. Avoiding this waste would be one more reason for us to tackle this.
ada4a commented 2025-02-02 20:24:31 +01:00
Author
Owner
Copy link

TreeBuilder::build_conflict looks like a good place for the not-really-a-conflict detection (this part in particular)? It would look something like this, though I'm once again not knowledgeable enough about all the nodes and revs and stuff to fully work this out... @wetneb would you be able to help?

--- a/src/tree_builder.rs
+++ b/src/tree_builder.rs
@@ -434,12 +434,22 @@ impl<'a, 'b> TreeBuilder<'a, 'b> {
             Err(format!(
                 "ends don't match: {}, {}, {}",
                 fmt_set(end_base),
                 fmt_set(end_left),
                 fmt_set(end_right)
             ))
+        } else if list_left == list_right {
+            // well that's not really a conflict
+            Ok((
+                end_base,
+                MergedTree::ExactTree {
+                    node: todo!(),
+                    revisions: RevisionNESet::singleton(Revision::Left).with(Revision::Right),
+                    hash: todo!(),
+                },
+            ))
         } else {
             Ok((
                 end_base,
                 MergedTree::Conflict {
                     base: list_base,
                     left: list_left,
`TreeBuilder::build_conflict` looks like a good place for the not-really-a-conflict detection ([this part](https://codeberg.org/mergiraf/mergiraf/src/commit/80d84aefda446e459d3ff802bd79050b00c638a7/src/tree_builder.rs#L440) in particular)? It would look something like this, though I'm once again not knowledgeable enough about all the nodes and revs and stuff to fully work this out... @wetneb would you be able to help? ```patch --- a/src/tree_builder.rs +++ b/src/tree_builder.rs @@ -434,12 +434,22 @@ impl<'a, 'b> TreeBuilder<'a, 'b> { Err(format!( "ends don't match: {}, {}, {}", fmt_set(end_base), fmt_set(end_left), fmt_set(end_right) )) + } else if list_left == list_right { + // well that's not really a conflict + Ok(( + end_base, + MergedTree::ExactTree { + node: todo!(), + revisions: RevisionNESet::singleton(Revision::Left).with(Revision::Right), + hash: todo!(), + }, + )) } else { Ok(( end_base, MergedTree::Conflict { base: list_base, left: list_left, ```
ada4a commented 2025-02-03 13:46:42 +01:00
Author
Owner
Copy link

I think I got it?

--- a/src/tree_builder.rs
+++ b/src/tree_builder.rs
@@ -440,6 +440,20 @@ impl<'a, 'b> TreeBuilder<'a, 'b> {
                 fmt_set(end_left),
                 fmt_set(end_right)
             ))
+        } else if list_left.len() == list_right.len()
+            && core::iter::zip(&list_left, &list_right)
+                .all(|(tree_left, tree_right)| tree_left.isomorphic_to(tree_right))
+        {
+            // well that's not really a conflict
+            Ok((
+                end_base,
+                MergedTree::new_exact(
+                    self.class_mapping
+                        .map_to_leader(RevNode::new(Revision::Left, list_left[0])),
+                    RevisionNESet::singleton(Revision::Left).with(Revision::Right),
+                    self.class_mapping,
+                ),
+            ))
         } else {
             Ok((
                 end_base,
I think I got it? ```diff --- a/src/tree_builder.rs +++ b/src/tree_builder.rs @@ -440,6 +440,20 @@ impl<'a, 'b> TreeBuilder<'a, 'b> { fmt_set(end_left), fmt_set(end_right) )) + } else if list_left.len() == list_right.len() + && core::iter::zip(&list_left, &list_right) + .all(|(tree_left, tree_right)| tree_left.isomorphic_to(tree_right)) + { + // well that's not really a conflict + Ok(( + end_base, + MergedTree::new_exact( + self.class_mapping + .map_to_leader(RevNode::new(Revision::Left, list_left[0])), + RevisionNESet::singleton(Revision::Left).with(Revision::Right), + self.class_mapping, + ), + )) } else { Ok(( end_base, ```
wetneb commented 2025-02-03 15:37:51 +01:00
Owner
Copy link

Thanks for the in-depth investigation! The last version looks like it would be a very safe addition, and it sounds like it would fix this particular case. I am not clear on whether we could also intervene on other parts of the algorithm with this example in mind. The part of the algorithm that adds whitespace between merged tokens has always felt very brittle to me - it really feels like a best-effort heuristic rather than a reliable algorithm, sadly.

One thing I have been considering for a while is to add a safety check by re-parsing the merged output with the tree-sitter parser and checking that the resulting tree matches what we expect. If it's not, we throw the result away and fall back on textual merging. It's a pretty fuzzy idea of course, but it feels like it could be a useful safety net to catch similar problems. Quite some of the bad merges that have been reported are related to incorrect whitespace/newlines between merged items resulting in different semantics, which feels like a really bad kind of failure. I am also not sure if we could run the tree-sitter parser on an output with conflicts in a meaningful way, but doing it on conflict-free merges could already be interesting since they are the ones that can most easily slip through review.

Of course, the scope of such an improvement feels a lot broader than this issue, so I think the fix you have above is definitively worth integrating regardless.

Thanks for the in-depth investigation! The last version looks like it would be a very safe addition, and it sounds like it would fix this particular case. I am not clear on whether we could also intervene on other parts of the algorithm with this example in mind. The part of the algorithm that adds whitespace between merged tokens has always felt very brittle to me - it really feels like a best-effort heuristic rather than a reliable algorithm, sadly. One thing I have been considering for a while is to add a safety check by re-parsing the merged output with the tree-sitter parser and checking that the resulting tree matches what we expect. If it's not, we throw the result away and fall back on textual merging. It's a pretty fuzzy idea of course, but it feels like it could be a useful safety net to catch similar problems. Quite some of the bad merges that have been reported are related to incorrect whitespace/newlines between merged items resulting in different semantics, which feels like a really bad kind of failure. I am also not sure if we could run the tree-sitter parser on an output with conflicts in a meaningful way, but doing it on conflict-free merges could already be interesting since they are the ones that can most easily slip through review. Of course, the scope of such an improvement feels a lot broader than this issue, so I think the fix you have above is definitively worth integrating regardless.
ada4a commented 2025-02-03 16:53:05 +01:00
Author
Owner
Copy link

The last version looks like it would be a very safe addition, and it sounds like it would fix this particular case. I am not clear on whether we could also intervene on other parts of the algorithm with this example in mind.

The MergedText::add_conflict method (and I think there was another one like that, though I can't find it right now) kind of reminds me of shotgun parsing -- in that, instead of eliminating the not-really-conflicts right when they're created, we seem to propagate (some of) them, and therefore end up needing to deal with them at a later point (or, probably, multiple ones) in the pipeline. I think a possible solution would be to experiment with erroring out at MergedText::add_conflict when the left and right sides are identical, and from there trace back the source of this not-really-a-conflict.

Quite some of the bad merges that have been reported are related to incorrect whitespace/newlines between merged items resulting in different semantics, which feels like a really bad kind of failure.

I very much agree.

One thing I have been considering for a while is to add a safety check by re-parsing the merged output with the tree-sitter parser and checking that the resulting tree matches what we expect. If it's not, we throw the result away and fall back on textual merging. It's a pretty fuzzy idea of course, but it feels like it could be a useful safety net to catch similar problems.

The idea actually sounds pretty good!

I am also not sure if we could run the tree-sitter parser on an output with conflicts in a meaningful way

I think we could do something similar to ParsedMerge::reconstruct_revision? We'd basically MergedTree::pretty_print, but only take one of the sides when we encounter a MergedTree::Conflict

I think the fix you have above is definitively worth integrating regardless.

Glad to hear that! The only thing that worries me is the possibly-panicking [0], but I think it really shouldn't fail given the context... I'd add an expect there, but I'm really afraid my understanding of the whole situation is too shaky for that... I'll think about it some more, but do let me know if you come up with something!

> The last version looks like it would be a very safe addition, and it sounds like it would fix this particular case. I am not clear on whether we could also intervene on other parts of the algorithm with this example in mind. The `MergedText::add_conflict` method (and I think there was another one like that, though I can't find it right now) kind of reminds me of [shotgun parsing](https://stackoverflow.com/questions/50852226/what-does-shotgun-parser-mean) -- in that, instead of eliminating the not-really-conflicts right when they're created, we seem to propagate (some of) them, and therefore end up needing to deal with them at a later point (or, probably, multiple ones) in the pipeline. I think a possible solution would be to experiment with erroring out at `MergedText::add_conflict` when the left and right sides are identical, and from there trace back the source of this not-really-a-conflict. > Quite some of the bad merges that have been reported are related to incorrect whitespace/newlines between merged items resulting in different semantics, which feels like a really bad kind of failure. I very much agree. > One thing I have been considering for a while is to add a safety check by re-parsing the merged output with the tree-sitter parser and checking that the resulting tree matches what we expect. If it's not, we throw the result away and fall back on textual merging. It's a pretty fuzzy idea of course, but it feels like it could be a useful safety net to catch similar problems. The idea actually sounds pretty good! > I am also not sure if we could run the tree-sitter parser on an output with conflicts in a meaningful way I think we could do something similar to `ParsedMerge::reconstruct_revision`? We'd basically `MergedTree::pretty_print`, but only take one of the sides when we encounter a `MergedTree::Conflict` > I think the fix you have above is definitively worth integrating regardless. Glad to hear that! The only thing that worries me is the possibly-panicking `[0]`, but I _think_ it really shouldn't fail given the context... I'd add an `expect` there, but I'm really afraid my understanding of the whole situation is too shaky for that... I'll think about it some more, but do let me know if you come up with something!
👍 1
wetneb commented 2025-02-03 16:58:26 +01:00
Owner
Copy link

Ah yeah I didn't catch the [0] - it does seem possible for it to panic, no? If both sides remove things and both lists are empty, we could potentially still end up in this case, I guess. But I see that it's annoying to handle because we do have to return something, given the typing constraints…

At least returning an error would be better than panicking, and perhaps not so difficult since we are already returning a Result.

Ah yeah I didn't catch the `[0]` - it does seem possible for it to panic, no? If both sides remove things and both lists are empty, we could potentially still end up in this case, I guess. But I see that it's annoying to handle because we do have to return something, given the typing constraints… At least returning an error would be better than panicking, and perhaps not so difficult since we are already returning a `Result`.
ada4a commented 2025-02-03 17:16:29 +01:00
Author
Owner
Copy link

Ah yeah I didn't catch the [0] - it does seem possible for it to panic, no? If both sides remove things and both lists are empty, we could potentially still end up in this case, I guess.

Right! Totally missed that possibility

At least returning an error would be better than panicking

The only reason I wanted to go with a panic is because I thought the error case really is unreachable... but it in fact is, so erroring out could be an option indeed

But I see that it's annoying to handle because we do have to return something, given the typing constraints…

Yeah. I'll see what I can come up with!

> Ah yeah I didn't catch the [0] - it does seem possible for it to panic, no? If both sides remove things and both lists are empty, we could potentially still end up in this case, I guess. Right! Totally missed that possibility > At least returning an error would be better than panicking The only reason I wanted to go with a panic is because I thought the error case really is unreachable... but it in fact is, so erroring out could be an option indeed > But I see that it's annoying to handle because we do have to return something, given the typing constraints… Yeah. I'll see what I can come up with!
ada4a commented 2025-02-03 18:03:46 +01:00
Author
Owner
Copy link

I mean an obvious solution would be to return an Option<MergedTree> in the happy case. But the return type of build_conflict warrants us a type complexity warning already. So I'll first deal with that, and come back to this right after

I mean an obvious solution would be to return an `Option<MergedTree>` in the happy case. But the return type of `build_conflict` warrants us a type complexity warning already. So I'll first deal with that, and come back to this right after
❤️ 1
ada4a commented 2025-02-04 11:50:08 +01:00
Author
Owner
Copy link

Wait. Shouldn't TreeBuilder::resolve_commutative_conflict have handled this? It's called on the result of build_conflict, and itself calls TreeBuilder::commutative_or_line_based_fallback, which in turn has checks for- oh, I think I've got it. This is what the last function looks like:

Lines 135 to 173 in e40525b
pub(crate) fn line_based_local_fallback_for_revnode(
node: Leader<'a>,
class_mapping: &ClassMapping<'a>,
) -> MergedTree<'a> {
let base_src = class_mapping.node_at_rev(node, Revision::Base);
let left_src = class_mapping.node_at_rev(node, Revision::Left);
let right_src = class_mapping.node_at_rev(node, Revision::Right);
match (base_src, left_src, right_src) {
(None, None, None) => {
unreachable!("A node that does not belong to any revision, how curious!")
}
(_, Some(_), None) => MergedTree::new_exact(
node,
RevisionNESet::singleton(Revision::Left),
class_mapping,
),
(_, None, Some(_)) => MergedTree::new_exact(
node,
RevisionNESet::singleton(Revision::Right),
class_mapping,
),
(Some(_), None, None) => MergedTree::new_exact(
node,
RevisionNESet::singleton(Revision::Base),
class_mapping,
),
(base, Some(left), Some(right)) => {
let base_src = base.map_or(Cow::from(""), |base| base.unindented_source());
let left_src = left.unindented_source();
let right_src = right.unindented_source();
let line_based_merge = line_based_merge(&base_src, &left_src, &right_src, None);
MergedTree::LineBasedMerge {
node,
contents: line_based_merge.contents,
conflict_mass: line_based_merge.conflict_mass,
}
}
}
}

I think what's missing is a check in the last branch to see if left and right are isomorphic, no? And it looks like that should be it. Let me check real quick.

Wait. Shouldn't `TreeBuilder::resolve_commutative_conflict` have handled this? It's called on the result of `build_conflict`, and itself calls `TreeBuilder::commutative_or_line_based_fallback`, which in turn has checks for- oh, I think I've got it. This is what the last function looks like: https://codeberg.org/mergiraf/mergiraf/src/commit/e40525b5ff4565d4bbe3e5efb188efea0b5ddaeb/src/merged_tree.rs#L135-L173 I think what's missing is a check in the last branch to see if `left` and `right` are isomorphic, no? And it looks like that should be it. Let me check real quick.
ada4a commented 2025-02-04 12:07:07 +01:00
Author
Owner
Copy link

Oh, I was too quick... the first function is actually called TreeBuilder::resolve_commutative_conflict, and is, as the name suggests, only used in case the conflict has a commutative parent. But there shouldn't be anything stopping us from calling TreeBuilder::commutative_or_line_based_fallback (well, without the "commutative" part), ourselves. I'll look at that later (I have an exam in an hour, so maybe it's time to prepare for that or something :p)

Oh, I was too quick... the first function is actually called `TreeBuilder::resolve_commutative_conflict`, and is, as the name suggests, only used in case the conflict has a commutative parent. But there shouldn't be anything stopping us from calling `TreeBuilder::commutative_or_line_based_fallback` (well, without the "commutative" part), ourselves. I'll look at that later (I have an exam in an hour, so maybe it's time to prepare for that or something :p)
ada4a commented 2025-02-05 22:28:35 +01:00
Author
Owner
Copy link

So I thought about this some more.

it does seem possible for it to panic, no? If both sides remove things and both lists are empty, we could potentially still end up in this case, I guess

Wouldn't that actually be impossible inside build_conflict? We only call the method when we have, well, a conflict -- in particular, when two sides diverge. But if they do, then it can't possibly be that one of two lists is empty, no?

For this same reason I think it doesn't make sense to integrate the entire range of possibilities covered by MergedTree::line_based_local_fallback_for_revnode -- the latter mostly deals with cases where one of sides is empty, which we don't need for the reason explained above.

But I think we could actually add the case of isomorphic left and right sides to MergedTree::line_based_local_fallback_for_revnode, and handle it the same way as in build_conflict. This is how that'd look like:

diff --git a/src/merged_tree.rs b/src/merged_tree.rs
index 1935eab..17e3338 100644
--- a/src/merged_tree.rs
+++ b/src/merged_tree.rs
@@ -158,6 +158,11 @@ impl<'a> MergedTree<'a> {
                 RevisionNESet::singleton(Revision::Base),
                 class_mapping,
             ),
+            (_, Some(left), Some(right)) if left.isomorphic_to(right) => MergedTree::new_exact(
+                node,
+                RevisionNESet::singleton(Revision::Left).with(Revision::Right),
+                class_mapping,
+            ),
             (base, Some(left), Some(right)) => {
                 let base_src = base.map_or(Cow::from(""), |base| base.unindented_source());
                 let left_src = left.unindented_source();
So I thought about this some more. > it does seem possible for it to panic, no? If both sides remove things and both lists are empty, we could potentially still end up in this case, I guess Wouldn't that actually be impossible inside `build_conflict`? We only call the method when we have, well, a conflict -- in particular, when two sides diverge. But if they do, then it can't possibly be that one of two lists is empty, no? For this same reason I think it doesn't make sense to integrate the entire range of possibilities covered by `MergedTree::line_based_local_fallback_for_revnode` -- the latter mostly deals with cases where one of sides is empty, which we don't need for the reason explained above. But I think we could actually add the case of isomorphic left and right sides to `MergedTree::line_based_local_fallback_for_revnode`, and handle it the same way as in `build_conflict`. This is how that'd look like: ```diff diff --git a/src/merged_tree.rs b/src/merged_tree.rs index 1935eab..17e3338 100644 --- a/src/merged_tree.rs +++ b/src/merged_tree.rs @@ -158,6 +158,11 @@ impl<'a> MergedTree<'a> { RevisionNESet::singleton(Revision::Base), class_mapping, ), + (_, Some(left), Some(right)) if left.isomorphic_to(right) => MergedTree::new_exact( + node, + RevisionNESet::singleton(Revision::Left).with(Revision::Right), + class_mapping, + ), (base, Some(left), Some(right)) => { let base_src = base.map_or(Cow::from(""), |base| base.unindented_source()); let left_src = left.unindented_source(); ```
ada4a closed this issue 2025-02-15 11:25:00 +01:00
Sign in to join this conversation.
No Branch/Tag specified
Branches Tags
main
marker_length_detection
comm-parents-check-have-all-sigs
benchmark_utils
v0.15.0
v0.14.0
v0.13.0
v0.12.1
v0.12.0
v0.11.0
v0.10.0
v0.9.0
v0.8.1
v0.8.0
v0.7.0
v0.6.0
v0.5.1
v0.5.0
v0.4.0
preview-v0.4.0-alpha1
v0.3.1
v0.3.0
v0.2.0
v0.1.0
Labels
Clear labels   
Compat/Breaking

Breaking change that won't be backward compatible

  
Kind
Bad merge
Examples where the merging algorithm doesn't work as well as it should

  
Kind
Bug
Something is not working

  
Kind
Documentation
Documentation changes

  
Kind
Enhancement
Improve existing functionality

  
Kind
Feature
New functionality

  
Kind
New language

  
Kind
Security
This is security issue

  
Kind
Testing
Issue or pull request related to testing

  
Priority
Critical
The priority is critical

  
Priority
High
The priority is high

  
Priority
Low
The priority is low

  
Priority
Medium
The priority is medium

  
Reviewed
Confirmed
Issue has been confirmed

  
Reviewed
Duplicate
This issue or pull request already exists

  
Reviewed
Invalid
Invalid issue

  
Reviewed
Won't Fix
This issue won't be fixed

  
Status
Abandoned
Somebody has started to work on this but abandoned work

  
Status
Blocked
Something is blocking this issue or pull request

  
Status
Need More Info
Feedback is required to reproduce issue or to continue work

No labels
Compat/Breaking
Kind
Bad merge
Kind
Bug
Kind
Documentation
Kind
Enhancement
Kind
Feature
Kind
New language
Kind
Security
Kind
Testing
Priority
Critical
Priority
High
Priority
Low
Priority
Medium
Reviewed
Confirmed
Reviewed
Duplicate
Reviewed
Invalid
Reviewed
Won't Fix
Status
Abandoned
Status
Blocked
Status
Need More Info
Milestone
Clear milestone
No items
No milestone
Projects
Clear projects
No items
No project
Assignees
Clear assignees
No assignees
2 participants
Notifications
Due date
The due date is invalid or out of range. Please use the format "yyyy-mm-dd".

No due date set.

Dependencies

No dependencies set.

Reference: mergiraf/mergiraf#170
No description provided.
Delete branch "%!s()"

Deleting a branch is permanent. Although the deleted branch may continue to exist for a short time before it actually gets removed, it CANNOT be undone in most cases. Continue?