Not all callers need this information, but I assumed it's relatively cheap to
look up the source path in the target tree compared to diffing.
This could be represented as Regular(_)|Copied(_, _)|Renamed(_, _), but it's
a bit weird if Copied and Renamed were separate variants. Instead, I decided
to wrap copy metadata in Option.
This patch adds accessor methods as I'm going to change the underlying data
types. Since entry values are consumed separately, these methods are implemented
on CopiesTreeDiffEntryPath, not on *TreeDiffEntry.
I plan to provide a richer version of `TreeDiffEntry` with copy info
(and to make `TreeDiffEntry` itself "poorer"). Most callers want to
know about copies/renames, but at least working copy implementations
probably don't. This patch adds separate `diff_stream()` and
`diff_stream_with_copies()` so we can provide the simpler interface
for callers that don't need copy info.
The support for copy tracing is already simply added to the stream
just before yielding the item, so we can easily implement it as a
stream adapter. That ensures that we use the same logic for the
iterator- and stream-based versions. More importantly, it enables
further cleanups and a simpler interface.
MergedTreeVal was roughly equivalent to Merge<Option<Cow<_>>. As we've dropped
support for the legacy trees, it can be simplified to Merge<Option<&_>>.
- force each diff command to explicitly enable copy tracking
- enable copy tracking in diff_summary
- post-process for diff iterator
- post-process for diff stream
- update changelog
I considered making `MergedTree` just a newtype (1-tuple) but I went
with a struct instead because we may want to add copy information in a
separate field in the future.
As we discovered in the `jj fix` tests,
`MergedTreeBuilder::write_tree()` doesn't try to resolve conflicts,
not even trivial ones. This patch fixes that.
I think this is a variant of the problem fixed by 7fda80fc22 "tree: simplify
conflict before resolving at hunk level." We need to simplify() the conflict
before and after extracting file ids because the source conflict values may
contain trees to be cancelled out, and the file values may differ only in exec
bits. Since the legacy tree passes a simplified conflict in to this function,
I made the merged tree do the same.
Fixes#2654
Otherwise an empty subtree would be added to the parent tree.
If the stored tree contained an empty subtree, simplify() wouldn't work
against new "absent" subtree representation. I don't know if there's a
such code path, but I believe it's very rare to encounter the problem.
#2654
This enables cheap str-to-RepoPath cast, which is useful when sorting and
filtering a large Vec<(String, _)> list by using matcher for example. It
will also eliminate temporary allocation by repo_path.parent().
This is a step towards introducing a borrowed RepoPath type. The current
RepoPath type is inefficient as each component String is usually short. We
could apply short-string optimization, but still each inlined component would
consume 24 bytes just for e.g. "src", and increase the chance of random memory
access. If the owned RepoPath type is backed by String, we can implement cheap
cast from &str to borrowed &RepoPath type.
Since the concurrent diff algorithm is significantly slower when using
the Git backend, I think we'll have to use switch between the two
algorithms depending on backend. Even if the concurrent version always
performed as well as the sequential version, exactly how concurrent it
should be probably still depends on the backend. This commit therefore
adds a function to the `Backend` trait, so each backend can say how
much concurrency they deal well with. I then use that number for
choosing between the sequential and concurrent versions in
`MergedTree::diff_stream()`, and also to decide the number of
concurrent reads to do in the concurrent version.
When diffing two trees, we currently start at the root and diff those
trees. Then we diff each subtree, one at a time, recursively. When
using a commit backend that uses remote storage, like our backend at
Google does, diffing the subtrees one at a time gets very slow. We
should be able to diff subtrees concurrently. That way, the number of
roundtrips to a server becomes determined by the depth of the deepest
difference instead of by the number of differing trees (times 2,
even). This patch implements such an algorithm behind a `Stream`
interface. It's not hooked in to `MergedTree::diff_stream()` yet; that
will happen in the next commit.
I timed the new implementation by updating `jj diff -s` to use the new
diff stream and then ran it on the Linux repo with `jj diff
--ignore-working-copy -s --from v5.0 --to v6.0`. That slowed down by
~20%, from ~750 ms to ~900 ms. Maybe we can get some of that
performance back but I think it'll be hard to match
`MergedTree::diff()`. We can decide later if we're okay with the
difference (after hopefully reducing the gap a bit) or if we want to
keep both implementations.
I also timed the new implementation on our cloud-based repo at
Google. As expected, it made some diffs much faster (I'm not sure if
I'm allowed to share figures).
I'm about to add a few more checks for diffing with a matcher. I think
it will help make it readable and reduce the risk of mixing up
variables between each part of the test if we use some nested blocks.
I also removed some unnecessary `.clone()` calls while at it.
I want to fix error propagation before I start using async in this
code. This makes the diff iterator propagate errors from reading tree
objects.
Errors include the path and don't stop the iteration. The idea is that
we should be able to show the user an error inline in diff output if
we failed to read a tree. That's going to be especially useful for
backends that can return `BackendError::AccessDenied`. That error
variant doesn't yet exist, but I plan to add it, and use it in
Google's internal backend.
I'm going to add `MergedTreeValue` as an alias for
`Merge<Option<TreeValue>>`, but we already have a type by that name in
`merged_tree`. This patch renames it away, to make room for the new
alias. I used `MergedTreeVal` for this borrowing version to be a bit
like how `str` is a borrowed version of `String`.
I ran into a bug the other day where `jj status` said there was a
conflict in a file but there were no conflict markers in the working
copy. The commit was created when I squashed a conflict resolution
into the commit's parent. The rebased child commit then ended up in
this state. I.e., it looked something like this before squashing:
```
C (no conflict)
|
| B conflict
|/
A conflict
```
The conflict in B was different from the conflict in A. When I
squashed in C, jj would try to resolve the conflicts by first creating
a 7-way conflict (3 from A, 3 from B, 1 from C). Because of the exact
content-level changes, the 7-way conflict couldn't be automatically
resolved by `files::merge()` (the way it currently works
anyway). However, after simplifying the conflict, it could be
resolved. Because `MergedTree::merge()` does another round of conflict
simplification of the result at the end of the function, it was the
simplifed version that actually got stored in the commit. So when
inspecting the conflict later (e.g. in the working copy, as I did), it
could be automatically resolved.
I think there are at least two ways to solve this. One is to call
`merge_trees()` again after calling `tree.simplify()` in
`MergedTree::merge()`. However, I think it would only matter in the
case of content-level conflicts. Therefore, it seems better to make
the content-level resolution solve this case to start with. I've done
that by simplifying the conflict before passing it into
`files::merge()`. We could even do the fix in `files::merge()`, but
doing it before calling it has the advantage that we can avoid reading
some unchanged content from the backend.
This fixes a bug where we used the parent directory's path when trying
read trees and files for a child entry. Many tests in
`test_merged_tree` fail after switching to the test backend there
without this fix/
