| capture.rs |
|
2788 |
- |
| compact.rs |
Implements basic compacting. This is based on the compaction logic from
diffy by Brandon Williams. |
12067 |
- |
| hook.rs |
|
4809 |
- |
| lcs.rs |
LCS diff algorithm.
* time: `O((NM)D log (M)D)`
* space `O(MN)` |
8554 |
- |
| mod.rs |
Various diff (longest common subsequence) algorithms.
The implementations of the algorithms in this module are relatively low
level and expose the most generic bounds possible for the algorithm. To
use them you would typically use the higher level API if possible but
direct access to these algorithms can be useful in some cases.
All these algorithms provide a `diff` function which takes two indexable
objects (for instance slices) and a [`DiffHook`]. As the
diff is generated the diff hook is invoked. Note that the diff hook does
not get access to the actual values but only the indexes. This is why the
diff hook is not used outside of the raw algorithm implementations as for
most situations access to the values is useful of required.
The algorithms module really is the most low-level module in similar and
generally not the place to start.
# Example
This is a simple example that shows how you can calculate the difference
between two sequences and capture the ops into a vector.
```rust
use similar::algorithms::{Algorithm, Replace, Capture, diff_slices};
let a = vec![1, 2, 3, 4, 5];
let b = vec![1, 2, 3, 4, 7];
let mut d = Replace::new(Capture::new());
diff_slices(Algorithm::Myers, &mut d, &a, &b).unwrap();
let ops = d.into_inner().into_ops();
```
The above example is equivalent to using
[`capture_diff_slices`](crate::capture_diff_slices). |
4294 |
- |
| myers.rs |
Myers' diff algorithm.
* time: `O((N+M)D)`
* space `O(N+M)`
See [the original article by Eugene W. Myers](http://www.xmailserver.org/diff2.pdf)
describing it.
The implementation of this algorithm is based on the implementation by
Brandon Williams.
# Heuristics
At present this implementation of Myers' does not implement any more advanced
heuristics that would solve some pathological cases. For instance passing two
large and completely distinct sequences to the algorithm will make it spin
without making reasonable progress. Currently the only protection in the
library against this is to pass a deadline to the diffing algorithm.
For potential improvements here see [similar#15](https://github.com/mitsuhiko/similar/issues/15). |
13648 |
- |
| patience.rs |
Patience diff algorithm.
* time: `O(N log N + M log M + (N+M)D)`
* space: `O(N+M)`
Tends to give more human-readable outputs. See [Bram Cohen's blog
post](https://bramcohen.livejournal.com/73318.html) describing it.
This is based on the patience implementation of [pijul](https://pijul.org/)
by Pierre-Étienne Meunier. |
5846 |
- |
| replace.rs |
|
6043 |
- |
| snapshots |
|
|
- |
| utils.rs |
|
10300 |
- |