similar/algorithms/
mod.rs

Help
1//! Various diff (longest common subsequence) algorithms.
2//!
3//! The implementations of the algorithms in this module are relatively low
4//! level and expose the most generic bounds possible for the algorithm.  To
5//! use them you would typically use the higher level API if possible but
6//! direct access to these algorithms can be useful in some cases.
7//!
8//! All these algorithms provide a `diff` function which takes two indexable
9//! objects (for instance slices) and a [`DiffHook`].  As the
10//! diff is generated the diff hook is invoked.  Note that the diff hook does
11//! not get access to the actual values but only the indexes.  This is why the
12//! diff hook is not used outside of the raw algorithm implementations as for
13//! most situations access to the values is useful of required.
14//!
15//! The algorithms module really is the most low-level module in similar and
16//! generally not the place to start.
17//!
18//! # Example
19//!
20//! This is a simple example that shows how you can calculate the difference
21//! between two sequences and capture the ops into a vector.
22//!
23//! ```rust
24//! use similar::algorithms::{Algorithm, Replace, Capture, diff_slices};
25//!
26//! let a = vec![1, 2, 3, 4, 5];
27//! let b = vec![1, 2, 3, 4, 7];
28//! let mut d = Replace::new(Capture::new());
29//! diff_slices(Algorithm::Myers, &mut d, &a, &b).unwrap();
30//! let ops = d.into_inner().into_ops();
31//! ```
32//!
33//! The above example is equivalent to using
34//! [`capture_diff_slices`](crate::capture_diff_slices).
35
36mod capture;
37mod compact;
38mod hook;
39mod replace;
40pub(crate) mod utils;
41
42use std::hash::Hash;
43use std::ops::{Index, Range};
44
45use crate::deadline_support::Instant;
46pub use capture::Capture;
47pub use compact::Compact;
48pub use hook::{DiffHook, NoFinishHook};
49pub use replace::Replace;
50pub use utils::IdentifyDistinct;
51
52#[doc(no_inline)]
53pub use crate::Algorithm;
54
55pub mod lcs;
56pub mod myers;
57pub mod patience;
58
59/// Creates a diff between old and new with the given algorithm.
60///
61/// Diffs `old`, between indices `old_range` and `new` between indices `new_range`.
62pub fn diff<Old, New, D>(
63    alg: Algorithm,
64    d: &mut D,
65    old: &Old,
66    old_range: Range<usize>,
67    new: &New,
68    new_range: Range<usize>,
69) -> Result<(), D::Error>
70where
71    Old: Index<usize> + ?Sized,
72    New: Index<usize> + ?Sized,
73    D: DiffHook,
74    Old::Output: Hash + Eq + Ord,
75    New::Output: PartialEq<Old::Output> + Hash + Eq + Ord,
76{
77    diff_deadline(alg, d, old, old_range, new, new_range, None)
78}
79
80/// Creates a diff between old and new with the given algorithm with deadline.
81///
82/// Diffs `old`, between indices `old_range` and `new` between indices `new_range`.
83///
84/// This diff is done with an optional deadline that defines the maximal
85/// execution time permitted before it bails and falls back to an approximation.
86/// Note that not all algorithms behave well if they reach the deadline (LCS
87/// for instance produces a very simplistic diff when the deadline is reached
88/// in all cases).
89pub fn diff_deadline<Old, New, D>(
90    alg: Algorithm,
91    d: &mut D,
92    old: &Old,
93    old_range: Range<usize>,
94    new: &New,
95    new_range: Range<usize>,
96    deadline: Option<Instant>,
97) -> Result<(), D::Error>
98where
99    Old: Index<usize> + ?Sized,
100    New: Index<usize> + ?Sized,
101    D: DiffHook,
102    Old::Output: Hash + Eq + Ord,
103    New::Output: PartialEq<Old::Output> + Hash + Eq + Ord,
104{
105    match alg {
106        Algorithm::Myers => myers::diff_deadline(d, old, old_range, new, new_range, deadline),
107        Algorithm::Patience => patience::diff_deadline(d, old, old_range, new, new_range, deadline),
108        Algorithm::Lcs => lcs::diff_deadline(d, old, old_range, new, new_range, deadline),
109    }
110}
111
112/// Shortcut for diffing slices with a specific algorithm.
113pub fn diff_slices<D, T>(alg: Algorithm, d: &mut D, old: &[T], new: &[T]) -> Result<(), D::Error>
114where
115    D: DiffHook,
116    T: Eq + Hash + Ord,
117{
118    diff(alg, d, old, 0..old.len(), new, 0..new.len())
119}
120
121/// Shortcut for diffing slices with a specific algorithm.
122pub fn diff_slices_deadline<D, T>(
123    alg: Algorithm,
124    d: &mut D,
125    old: &[T],
126    new: &[T],
127    deadline: Option<Instant>,
128) -> Result<(), D::Error>
129where
130    D: DiffHook,
131    T: Eq + Hash + Ord,
132{
133    diff_deadline(alg, d, old, 0..old.len(), new, 0..new.len(), deadline)
134}
similar/algorithms/mod.rs

similar/algorithms/
mod.rs
