Add convenience feature for word diff

[pascalkuthe]

Performing a word diff over a full file can be fairly slow on large files.
A better approach is to perform a line diff first and and then perform the word diff on the found changes.
While this is already possible with imara-diff is requires quite a bit of legwork and can be tricky to get right.
It would be nice if this could be included in the library directly.
This has multiple steps for an implementation:

• Determine the output format. A different trait or force collecting into a Vec?
• Implement a TokenSource for words
• Implement a Sink that automatically computes a word diff
• Potentially implement a heuristic to detect and ignore

The diff algorithm in git only operates on lines. It is worth looking into what exactly they use to produce a colored word diff from the line diff.
Perhaps a different algorithm is a better fit?

[jlama]

FYI git does word diffing by feeding the same algorithm with one word per line.

[KnorpelSenf]

I am coming from denoland/deno#30644 and I am interested in working on this. I think the git way of

1. splitting each line into its characters
2. running the same algorithm on the output

seems like a straightforward approach.

I also looked at dissimilar which seems not to perform any tokenisation at all (at least https://github.com/dtolnay/dissimilar/blob/fc55e18efe61997361c849c1c8ef8dedb517751b/src/lib.rs#L128 looks like that to me). That is obviously incredibly slow, but it means that dissimilar can provide word diffing out of the box. I expect that splitting each line into its characters would give similar results with imara.

I believe this feature should be opt-in. I don't think it is reasonable to change the behaviour of current library usage.

Currently, the API exposes diffs between tokens, which results in a maximum granularity of line diffs. If we want to support word diffs, we need to extend the API somehow.

The way dissimilar does it looks good to me, and I would take inspiration from it to implement something here. If anyone has an opinion about how this should be designed, please comment below. I'd be happy about some input.

[Byron]

I am not very knowledgeable about this but to me it looked like it should always be possible to implement a sink like UnifiedDiff to also implement word diffing. The problem here should be more of the sort of "how to actually visualise this without a terminal".

In the v0.2 API everything is already collected into a Vec so it should feel a bit more native now from that point of view.

[KnorpelSenf]

I am not very knowledgeable about this but to me it looked like it should always be possible to implement a sink like UnifiedDiff to also implement word diffing.

Doesn't that behaviour essentially require string diffing again?

The problem here should be more of the sort of "how to actually visualise this without a terminal".

I can't follow. I'm interesting in finding the word diff between two strings. Building a pretty UI with a visualisation that isn't inside a terminal doesn't really have anything to do with this, does it?

In the v0.2 API everything is already collected into a Vec so it should feel a bit more native now from that point of view.

The tokens are in a vec, sure, but a word diff needs to surface information that spans several tokens and with sub-token accuracy. Can you explain what you mean by native?

[Byron]

Doesn't that behaviour essentially require string diffing again?

The UnifiedDiff utility is a Sink, but in theory it could trigger another diff itself. It might just feel strange, or needs a user-controlled second step to work, but it doesn't seem impossible.

The problem here should be more of the sort of "how to actually visualise this without a terminal".

I can't follow. I'm interesting in finding the word diff between two strings. Building a pretty UI with a visualisation that isn't inside a terminal doesn't really have anything to do with this, does it?

Right, I was thinking too strongly in terms of UnifiedDiffs and their visualisation. But I am also lacking the 'vision' on how a word-diff would look like in abstract terms, so that any visualisation could be built with that data.

In the v0.2 API everything is already collected into a Vec so it should feel a bit more native now from that point of view.

The tokens are in a vec, sure, but a word diff needs to surface information that spans several tokens and with sub-token accuracy. Can you explain what you mean by native?

native should probably be natural. The V2 API should be easier to use for this, but I'd think it can also be done with V1, but less conveniently.

[KnorpelSenf]

Doesn't that behaviour essentially require string diffing again?

The UnifiedDiff utility is a Sink, but in theory it could trigger another diff itself. It might just feel strange, or needs a user-controlled second step to work, but it doesn't seem impossible.

Gotcha, that makes sense. So … should imara simply export a new type of sink that can be used by library consumers in order to add word diffing? Or would you rather have an internal sink implementation directly?

The problem here should be more of the sort of "how to actually visualise this without a terminal".

I can't follow. I'm interesting in finding the word diff between two strings. Building a pretty UI with a visualisation that isn't inside a terminal doesn't really have anything to do with this, does it?

Right, I was thinking too strongly in terms of UnifiedDiffs and their visualisation. But I am also lacking the 'vision' on how a word-diff would look like in abstract terms, so that any visualisation could be built with that data.

Have you seen how dissimilar does diffs? I think that API makes perfect sense for this use case. Each chunk would effectively contain

• a type (inserted/deleted/unchanged)
• an index of the first inserted/deleted token
• a start position inside the first token
• an index of the last inserted/deleted token
• an end position inside the last token

I can simply write the code for this, it's easier to see that in Rust than in English.

We might want to compress this down. For example, it's probably enough to store a vec of (token, index) pairs for each type. That would be far less convenient to process, but it would also use far fewer bytes and be compatible with the internal data structures that use hunks.

In the v0.2 API everything is already collected into a Vec so it should feel a bit more native now from that point of view.

The tokens are in a vec, sure, but a word diff needs to surface information that spans several tokens and with sub-token accuracy. Can you explain what you mean by native?

native should probably be natural. The V2 API should be easier to use for this, but I'd think it can also be done with V1, but less conveniently.

I'm still not 100 % sure what you meant, but perhaps my suggestion for the API aligns with it?

[Byron]

Let's have a PoC implementation then if you think it's easy enough to do for you. You'd probably do this against the API in master, and due to a lack of oversight/understanding I'd also think you will figure out where to put it with the only constraint that it should strictly be opt-in, or something that can be 'plugged in' on top of existing diff runs.
Maybe the simplest thing is a function that takes the input it needs to produce the output you''d want to further process the word diff, like it's needed for visualisation.

[KnorpelSenf]

Sounds good, I'll drop a comment here once I got something worth reviewing

[pascalkuthe]

I was thinking for the word (or char) diff to be built on top of a normal line diff. You only need to run it on line hunks that are modified (if a line is entirely inserted/removed then all the words in it will be too and that can save quite a bit of performance).

One way to do that would be to add a inner_diff function to the Hunk struct which would take a &mut Diff (to reuse the allocation) and then intern and diff the words.

For word diff you always want to use a Meyers diff (I doubt histogram heuristics are well suited to it but haven't looked into it too much). You want to postprocess but withkut indent heuristic. Longterm I would like to explore alternative algorithms like in delta which uses a different slgorith based on edit distance for word/char difd and not a traditional diff

[KnorpelSenf]

@pascalkuthe @Byron please check out #33.

[Byron]

Thanks so much for pushing this forward!

I'd be unable to review this though, I guess ultimately I need a more visual representation of the diff or spend more time than I have to understand the data.
For Pascal reviewing this should be more possible though, particularly from a 'does this fit' perspective.

[KnorpelSenf]

@Byron I tried adding tests that illustrate usage. Does that enable you to review it? If not, that's alright :)