paircomp_core/search.rs
1use crate::Error;
2
3/// A prefix comparison requested by [`LineSearch`], or its completed result.
4#[derive(Clone, Copy, Debug, Eq, PartialEq)]
5pub enum LineSearchStep {
6 /// Compare file prefixes through this line, including its LF if present.
7 ///
8 /// Use [`crate::fingerprint_through_line`] on each copy. A request beyond
9 /// the local EOF hashes the whole local file.
10 CompareThroughLine {
11 /// The 1-based line position.
12 line: u64,
13 },
14 /// The first differing line; it may be beyond the local EOF.
15 DifferenceAtLine {
16 /// The 1-based line position.
17 line: u64,
18 },
19}
20
21/// A deterministic search for the first differing line using file prefixes.
22///
23/// Construct this only after the whole-file fingerprints have been reported
24/// as different. Supply the local line count and the count reported by the
25/// other instance to [`Self::new`]. Drive the search with [`Self::current_step`]
26/// and [`Self::record_result`]; the search itself performs no file I/O.
27///
28/// Line counts and comparison results must describe the same unchanged pair of
29/// files throughout the search. See the [file stability requirements](crate#file-stability).
30#[derive(Clone, Copy, Debug, Eq, PartialEq)]
31pub struct LineSearch {
32 bounds: SearchBounds,
33}
34
35impl LineSearch {
36 /// Creates a line search using both copies' counts.
37 ///
38 /// Construct only after comparing the whole-file fingerprints and establishing
39 /// a mismatch. Supply the local line count and the count reported by the other
40 /// copy; either count may be zero. Both files must stay unchanged, and both
41 /// instances must use accurate counts and the same comparison answers.
42 ///
43 /// The larger count determines the shared upper bound. The constructor does
44 /// not read either file or verify the reported mismatch.
45 ///
46 /// # Errors
47 ///
48 /// Returns [`Error::EmptyFilesCannotDiffer`] when both counts are zero.
49 ///
50 /// # Examples
51 ///
52 /// ```
53 /// use paircomp_core::{LineSearch, LineSearchStep};
54 ///
55 /// // The whole-file fingerprints differ; the copies have 3 and 4 lines.
56 /// let mut search = LineSearch::new(3, 4)?;
57 /// assert_eq!(search.current_step(), LineSearchStep::CompareThroughLine { line: 2 });
58 /// search.record_result(true)?; // The prefixes through line 2 match.
59 /// assert_eq!(search.current_step(), LineSearchStep::CompareThroughLine { line: 3 });
60 /// search.record_result(false)?; // The prefixes through line 3 differ.
61 /// assert_eq!(search.current_step(), LineSearchStep::DifferenceAtLine { line: 3 });
62 /// # Ok::<(), paircomp_core::Error>(())
63 /// ```
64 pub fn new(local_line_count: u64, other_line_count: u64) -> Result<Self, Error> {
65 let bounds = SearchBounds::new(local_line_count.max(other_line_count))
66 .ok_or(Error::EmptyFilesCannotDiffer)?;
67 Ok(Self { bounds })
68 }
69
70 /// Returns the next prefix comparison or the completed line result.
71 ///
72 /// Repeated calls leave the state unchanged. Positions are 1-based; a final
73 /// result can refer to a line absent from the shorter copy. When only one
74 /// candidate remains, returns [`LineSearchStep::DifferenceAtLine`] without
75 /// requesting another comparison.
76 pub fn current_step(&self) -> LineSearchStep {
77 match self.bounds.midpoint() {
78 Some(line) => LineSearchStep::CompareThroughLine { line },
79 None => LineSearchStep::DifferenceAtLine {
80 line: self.bounds.low,
81 },
82 }
83 }
84
85 /// Applies the answer to the comparison returned by [`Self::current_step`].
86 ///
87 /// Pass `true` when the two fingerprints from [`crate::fingerprint_through_line`]
88 /// match, or `false` when they differ. A match excludes the prefix through the
89 /// requested line; a mismatch retains that position as a candidate. The
90 /// caller must supply the answer for the current comparison on both copies.
91 ///
92 /// # Errors
93 ///
94 /// Returns [`Error::SearchAlreadyComplete`] if the result is already known.
95 /// An error leaves the search unchanged.
96 pub fn record_result(&mut self, matched: bool) -> Result<(), Error> {
97 self.bounds.record_result(matched)
98 }
99}
100
101/// A requested line-local prefix comparison, or the first differing byte.
102///
103/// Byte positions are 1-based and can denote a byte absent from the shorter copy.
104#[derive(Clone, Copy, Debug, Eq, PartialEq)]
105pub enum ByteSearchStep {
106 /// Compare prefixes from the selected line's beginning through this byte.
107 ///
108 /// Use [`crate::fingerprint_line_prefix`] on each copy. Requests past the
109 /// local line's end hash the whole line; an absent line hashes no bytes.
110 CompareThroughByte {
111 /// The 1-based byte position.
112 byte: u64,
113 },
114 /// The first differing byte; it may be absent from the shorter line.
115 DifferenceAtByte {
116 /// The 1-based byte position.
117 byte: u64,
118 },
119}
120
121/// A deterministic search for the first differing byte within a differing line.
122///
123/// Supply both copies' byte lengths, including any LF, to [`Self::new`]. An
124/// absent line has length zero. Drive the search with [`Self::current_step`] and
125/// [`Self::record_result`]; the caller keeps track of the selected line, and the
126/// search itself performs no file I/O.
127///
128/// Counts and comparison results must describe the same unchanged pair of lines
129/// throughout the search. See the [file stability requirements](crate#file-stability).
130#[derive(Clone, Copy, Debug, Eq, PartialEq)]
131pub struct ByteSearch {
132 bounds: SearchBounds,
133}
134
135impl ByteSearch {
136 /// Creates a byte search using both copies' counts.
137 ///
138 /// Construct only after the line search has established that the selected
139 /// line differs and all preceding lines match. Supply each copy's byte length
140 /// for that line, including any CR/LF; use zero for an absent line. Both files
141 /// must stay unchanged, and both instances must use accurate lengths and the
142 /// same comparison answers.
143 ///
144 /// The larger count determines the shared upper bound. The constructor does
145 /// not read either file or verify the reported mismatch.
146 ///
147 /// # Errors
148 ///
149 /// Returns [`Error::EmptyLinesCannotDiffer`] when both counts are zero.
150 ///
151 /// # Examples
152 ///
153 /// ```
154 /// use paircomp_core::{ByteSearch, ByteSearchStep};
155 ///
156 /// // The differing lines are UTF-8 "café" and "cafè", each 5 bytes long.
157 /// let mut search = ByteSearch::new(5, 5)?;
158 /// assert_eq!(search.current_step(), ByteSearchStep::CompareThroughByte { byte: 3 });
159 /// search.record_result(true)?; // "caf" matches.
160 /// assert_eq!(search.current_step(), ByteSearchStep::CompareThroughByte { byte: 4 });
161 /// search.record_result(true)?; // The first byte of the final code point matches.
162 /// assert_eq!(search.current_step(), ByteSearchStep::DifferenceAtByte { byte: 5 });
163 /// # Ok::<(), paircomp_core::Error>(())
164 /// ```
165 pub fn new(local_byte_len: u64, other_byte_len: u64) -> Result<Self, Error> {
166 let bounds = SearchBounds::new(local_byte_len.max(other_byte_len))
167 .ok_or(Error::EmptyLinesCannotDiffer)?;
168 Ok(Self { bounds })
169 }
170
171 /// Returns the next prefix comparison or the completed byte result.
172 ///
173 /// Repeated calls leave the state unchanged. Positions are 1-based; a final
174 /// result can refer to a byte absent from the shorter copy. When only one
175 /// candidate remains, returns [`ByteSearchStep::DifferenceAtByte`] without
176 /// requesting another comparison.
177 pub fn current_step(&self) -> ByteSearchStep {
178 match self.bounds.midpoint() {
179 Some(byte) => ByteSearchStep::CompareThroughByte { byte },
180 None => ByteSearchStep::DifferenceAtByte {
181 byte: self.bounds.low,
182 },
183 }
184 }
185
186 /// Applies the answer to the comparison returned by [`Self::current_step`].
187 ///
188 /// Pass `true` when the two fingerprints from [`crate::fingerprint_line_prefix`]
189 /// match, or `false` when they differ. A match excludes the prefix through the
190 /// requested byte; a mismatch retains that position as a candidate. The
191 /// caller must supply the answer for the current comparison on both copies.
192 ///
193 /// # Errors
194 ///
195 /// Returns [`Error::SearchAlreadyComplete`] if the result is already known.
196 /// An error leaves the search unchanged.
197 pub fn record_result(&mut self, matched: bool) -> Result<(), Error> {
198 self.bounds.record_result(matched)
199 }
200}
201
202/// Inclusive candidate bounds for prefix bisection.
203///
204/// Maintains `1 <= low <= high`. Given an initial mismatch and consistent
205/// answers, prefixes before `low` match and the prefix through `high` differs.
206/// This lets the search finish at `low == high` without another comparison.
207#[derive(Clone, Copy, Debug, Eq, PartialEq)]
208struct SearchBounds {
209 low: u64,
210 high: u64,
211}
212
213impl SearchBounds {
214 fn new(high: u64) -> Option<Self> {
215 (high > 0).then_some(Self { low: 1, high })
216 }
217
218 /// A completed search has no midpoint; `low` is its result.
219 fn midpoint(&self) -> Option<u64> {
220 (self.low < self.high).then(|| self.low + (self.high - self.low) / 2)
221 }
222
223 fn record_result(&mut self, matched: bool) -> Result<(), Error> {
224 let midpoint = self.midpoint().ok_or(Error::SearchAlreadyComplete)?;
225 if matched {
226 self.low = midpoint + 1;
227 } else {
228 self.high = midpoint;
229 }
230 Ok(())
231 }
232}