1 use std::fmt; 2 use std::ops::{Index, Range}; 3 4 use crate::algorithms::utils::is_empty_range; 5 use crate::algorithms::DiffHook; 6 use crate::iter::ChangesIter; 7 8 /// An enum representing a diffing algorithm. 9 #[derive(Clone, Copy, Hash, PartialEq, Eq, PartialOrd, Ord, Debug)] 10 pub enum Algorithm { 11 /// Picks the myers algorithm from [`crate::algorithms::myers`] 12 Myers, 13 /// Picks the patience algorithm from [`crate::algorithms::patience`] 14 Patience, 15 /// Picks the LCS algorithm from [`crate::algorithms::lcs`] 16 Lcs, 17 } 18 19 impl Default for Algorithm { 20 /// Returns the default algorithm ([`Algorithm::Myers`]). default() -> Algorithm21 fn default() -> Algorithm { 22 Algorithm::Myers 23 } 24 } 25 26 /// The tag of a change. 27 #[derive(Debug, PartialEq, Eq, Hash, Clone, Copy, Ord, PartialOrd)] 28 pub enum ChangeTag { 29 /// The change indicates equality (not a change) 30 Equal, 31 /// The change indicates deleted text. 32 Delete, 33 /// The change indicates inserted text. 34 Insert, 35 } 36 37 impl fmt::Display for ChangeTag { fmt(&self, f: &mut fmt::Formatter) -> fmt::Result38 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { 39 write!( 40 f, 41 "{}", 42 match &self { 43 ChangeTag::Equal => ' ', 44 ChangeTag::Delete => '-', 45 ChangeTag::Insert => '+', 46 } 47 ) 48 } 49 } 50 51 /// Represents the expanded [`DiffOp`] change. 52 /// 53 /// This type is returned from [`DiffOp::iter_changes`] and 54 /// [`TextDiff::iter_changes`](crate::text::TextDiff::iter_changes). 55 /// 56 /// It exists so that it's more convenient to work with textual differences as 57 /// the underlying [`DiffOp`] encodes a group of changes. 58 /// 59 /// This type has additional methods that are only available for types 60 /// implementing [`DiffableStr`](crate::text::DiffableStr). 61 #[derive(Debug, PartialEq, Eq, Hash, Clone, Copy, Ord, PartialOrd)] 62 pub struct Change<'s, T: ?Sized> { 63 pub(crate) tag: ChangeTag, 64 pub(crate) old_index: Option<usize>, 65 pub(crate) new_index: Option<usize>, 66 pub(crate) value: &'s T, 67 } 68 69 /// These methods are available for all change types. 70 impl<'s, T: ?Sized> Change<'s, T> { 71 /// Returns the change tag. tag(&self) -> ChangeTag72 pub fn tag(&self) -> ChangeTag { 73 self.tag 74 } 75 76 /// Returns the old index if available. old_index(&self) -> Option<usize>77 pub fn old_index(&self) -> Option<usize> { 78 self.old_index 79 } 80 81 /// Returns the new index if available. new_index(&self) -> Option<usize>82 pub fn new_index(&self) -> Option<usize> { 83 self.new_index 84 } 85 86 /// Returns the underlying changed value. 87 /// 88 /// Depending on the type of the underlying [`crate::text::DiffableStr`] 89 /// this value is more or less useful. If you always want to have a utf-8 90 /// string it's best to use the [`Change::as_str`] and 91 /// [`Change::to_string_lossy`] methods. value(&self) -> &'s T92 pub fn value(&self) -> &'s T { 93 self.value 94 } 95 } 96 97 /// Utility enum to capture a diff operation. 98 /// 99 /// This is used by [`Capture`](crate::algorithms::Capture). 100 #[derive(Debug, PartialEq, Eq, Hash, Clone, Copy)] 101 pub enum DiffOp { 102 /// A segment is equal (see [`DiffHook::equal`]) 103 Equal { 104 /// The starting index in the old sequence. 105 old_index: usize, 106 /// The starting index in the new sequence. 107 new_index: usize, 108 /// The length of the segment. 109 len: usize, 110 }, 111 /// A segment was deleted (see [`DiffHook::delete`]) 112 Delete { 113 /// The starting index in the old sequence. 114 old_index: usize, 115 /// The length of the old segment. 116 old_len: usize, 117 /// The starting index in the new sequence. 118 new_index: usize, 119 }, 120 /// A segment was inserted (see [`DiffHook::insert`]) 121 Insert { 122 /// The starting index in the old sequence. 123 old_index: usize, 124 /// The starting index in the new sequence. 125 new_index: usize, 126 /// The length of the new segment. 127 new_len: usize, 128 }, 129 /// A segment was replaced (see [`DiffHook::replace`]) 130 Replace { 131 /// The starting index in the old sequence. 132 old_index: usize, 133 /// The length of the old segment. 134 old_len: usize, 135 /// The starting index in the new sequence. 136 new_index: usize, 137 /// The length of the new segment. 138 new_len: usize, 139 }, 140 } 141 142 /// The tag of a diff operation. 143 #[derive(Debug, PartialEq, Eq, Hash, Clone, Copy, Ord, PartialOrd)] 144 pub enum DiffTag { 145 /// The diff op encodes an equal segment. 146 Equal, 147 /// The diff op encodes a deleted segment. 148 Delete, 149 /// The diff op encodes an inserted segment. 150 Insert, 151 /// The diff op encodes a replaced segment. 152 Replace, 153 } 154 155 impl DiffOp { 156 /// Returns the tag of the operation. tag(self) -> DiffTag157 pub fn tag(self) -> DiffTag { 158 self.as_tag_tuple().0 159 } 160 161 /// Returns the old range. old_range(&self) -> Range<usize>162 pub fn old_range(&self) -> Range<usize> { 163 self.as_tag_tuple().1 164 } 165 166 /// Returns the new range. new_range(&self) -> Range<usize>167 pub fn new_range(&self) -> Range<usize> { 168 self.as_tag_tuple().2 169 } 170 171 /// Transform the op into a tuple of diff tag and ranges. 172 /// 173 /// This is useful when operating on slices. The returned format is 174 /// `(tag, i1..i2, j1..j2)`: 175 /// 176 /// * `Replace`: `a[i1..i2]` should be replaced by `b[j1..j2]` 177 /// * `Delete`: `a[i1..i2]` should be deleted (`j1 == j2` in this case). 178 /// * `Insert`: `b[j1..j2]` should be inserted at `a[i1..i2]` (`i1 == i2` in this case). 179 /// * `Equal`: `a[i1..i2]` is equal to `b[j1..j2]`. as_tag_tuple(&self) -> (DiffTag, Range<usize>, Range<usize>)180 pub fn as_tag_tuple(&self) -> (DiffTag, Range<usize>, Range<usize>) { 181 match *self { 182 DiffOp::Equal { 183 old_index, 184 new_index, 185 len, 186 } => ( 187 DiffTag::Equal, 188 old_index..old_index + len, 189 new_index..new_index + len, 190 ), 191 DiffOp::Delete { 192 old_index, 193 new_index, 194 old_len, 195 } => ( 196 DiffTag::Delete, 197 old_index..old_index + old_len, 198 new_index..new_index, 199 ), 200 DiffOp::Insert { 201 old_index, 202 new_index, 203 new_len, 204 } => ( 205 DiffTag::Insert, 206 old_index..old_index, 207 new_index..new_index + new_len, 208 ), 209 DiffOp::Replace { 210 old_index, 211 old_len, 212 new_index, 213 new_len, 214 } => ( 215 DiffTag::Replace, 216 old_index..old_index + old_len, 217 new_index..new_index + new_len, 218 ), 219 } 220 } 221 222 /// Apply this operation to a diff hook. apply_to_hook<D: DiffHook>(&self, d: &mut D) -> Result<(), D::Error>223 pub fn apply_to_hook<D: DiffHook>(&self, d: &mut D) -> Result<(), D::Error> { 224 match *self { 225 DiffOp::Equal { 226 old_index, 227 new_index, 228 len, 229 } => d.equal(old_index, new_index, len), 230 DiffOp::Delete { 231 old_index, 232 old_len, 233 new_index, 234 } => d.delete(old_index, old_len, new_index), 235 DiffOp::Insert { 236 old_index, 237 new_index, 238 new_len, 239 } => d.insert(old_index, new_index, new_len), 240 DiffOp::Replace { 241 old_index, 242 old_len, 243 new_index, 244 new_len, 245 } => d.replace(old_index, old_len, new_index, new_len), 246 } 247 } 248 249 /// Iterates over all changes encoded in the diff op against old and new 250 /// sequences. 251 /// 252 /// `old` and `new` are two indexable objects like the types you pass to 253 /// the diffing algorithm functions. 254 /// 255 /// ```rust 256 /// use similar::{ChangeTag, Algorithm}; 257 /// use similar::capture_diff_slices; 258 /// let old = vec!["foo", "bar", "baz"]; 259 /// let new = vec!["foo", "bar", "blah"]; 260 /// let ops = capture_diff_slices(Algorithm::Myers, &old, &new); 261 /// let changes: Vec<_> = ops 262 /// .iter() 263 /// .flat_map(|x| x.iter_changes(&old, &new)) 264 /// .map(|x| (x.tag(), x.value())) 265 /// .collect(); 266 /// assert_eq!(changes, vec![ 267 /// (ChangeTag::Equal, "foo"), 268 /// (ChangeTag::Equal, "bar"), 269 /// (ChangeTag::Delete, "baz"), 270 /// (ChangeTag::Insert, "blah"), 271 /// ]); 272 /// ``` iter_changes<'x, 'lookup, Old, New, T>( &self, old: &'lookup Old, new: &'lookup New, ) -> ChangesIter<'lookup, 'x, Old, New, T> where Old: Index<usize, Output = &'x T> + ?Sized, New: Index<usize, Output = &'x T> + ?Sized, T: 'x + ?Sized, 'x: 'lookup,273 pub fn iter_changes<'x, 'lookup, Old, New, T>( 274 &self, 275 old: &'lookup Old, 276 new: &'lookup New, 277 ) -> ChangesIter<'lookup, 'x, Old, New, T> 278 where 279 Old: Index<usize, Output = &'x T> + ?Sized, 280 New: Index<usize, Output = &'x T> + ?Sized, 281 T: 'x + ?Sized, 282 'x: 'lookup, 283 { 284 ChangesIter::new(old, new, *self) 285 } 286 287 /// Given a diffop yields the changes it encodes against the given slices. 288 /// 289 /// This is similar to [`DiffOp::iter_changes`] but instead of yielding the 290 /// individual changes it yields consequitive changed slices. 291 /// 292 /// This will only ever yield a single tuple or two tuples in case a 293 /// [`DiffOp::Replace`] operation is passed. 294 /// 295 /// ```rust 296 /// use similar::{ChangeTag, Algorithm}; 297 /// use similar::capture_diff_slices; 298 /// let old = vec!["foo", "bar", "baz"]; 299 /// let new = vec!["foo", "bar", "blah"]; 300 /// let ops = capture_diff_slices(Algorithm::Myers, &old, &new); 301 /// let changes: Vec<_> = ops.iter().flat_map(|x| x.iter_slices(&old, &new)).collect(); 302 /// assert_eq!(changes, vec![ 303 /// (ChangeTag::Equal, &["foo", "bar"][..]), 304 /// (ChangeTag::Delete, &["baz"][..]), 305 /// (ChangeTag::Insert, &["blah"][..]), 306 /// ]); 307 /// ``` 308 /// 309 /// Due to lifetime restrictions it's currently impossible for the 310 /// returned slices to outlive the lookup. iter_slices<'lookup, Old, New, T>( &self, old: &'lookup Old, new: &'lookup New, ) -> impl Iterator<Item = (ChangeTag, &'lookup T)> where T: 'lookup + ?Sized, Old: Index<Range<usize>, Output = T> + ?Sized, New: Index<Range<usize>, Output = T> + ?Sized,311 pub fn iter_slices<'lookup, Old, New, T>( 312 &self, 313 old: &'lookup Old, 314 new: &'lookup New, 315 ) -> impl Iterator<Item = (ChangeTag, &'lookup T)> 316 where 317 T: 'lookup + ?Sized, 318 Old: Index<Range<usize>, Output = T> + ?Sized, 319 New: Index<Range<usize>, Output = T> + ?Sized, 320 { 321 match *self { 322 DiffOp::Equal { old_index, len, .. } => { 323 Some((ChangeTag::Equal, &old[old_index..old_index + len])) 324 .into_iter() 325 .chain(None.into_iter()) 326 } 327 DiffOp::Insert { 328 new_index, new_len, .. 329 } => Some((ChangeTag::Insert, &new[new_index..new_index + new_len])) 330 .into_iter() 331 .chain(None.into_iter()), 332 DiffOp::Delete { 333 old_index, old_len, .. 334 } => Some((ChangeTag::Delete, &old[old_index..old_index + old_len])) 335 .into_iter() 336 .chain(None.into_iter()), 337 DiffOp::Replace { 338 old_index, 339 old_len, 340 new_index, 341 new_len, 342 } => Some((ChangeTag::Delete, &old[old_index..old_index + old_len])) 343 .into_iter() 344 .chain(Some((ChangeTag::Insert, &new[new_index..new_index + new_len])).into_iter()), 345 } 346 } 347 is_empty(&self) -> bool348 pub(crate) fn is_empty(&self) -> bool { 349 let (_, old, new) = self.as_tag_tuple(); 350 is_empty_range(&old) && is_empty_range(&new) 351 } 352 shift_left(&mut self, adjust: usize)353 pub(crate) fn shift_left(&mut self, adjust: usize) { 354 self.adjust((adjust, true), (0, false)); 355 } 356 shift_right(&mut self, adjust: usize)357 pub(crate) fn shift_right(&mut self, adjust: usize) { 358 self.adjust((adjust, false), (0, false)); 359 } 360 grow_left(&mut self, adjust: usize)361 pub(crate) fn grow_left(&mut self, adjust: usize) { 362 self.adjust((adjust, true), (adjust, false)); 363 } 364 grow_right(&mut self, adjust: usize)365 pub(crate) fn grow_right(&mut self, adjust: usize) { 366 self.adjust((0, false), (adjust, false)); 367 } 368 shrink_left(&mut self, adjust: usize)369 pub(crate) fn shrink_left(&mut self, adjust: usize) { 370 self.adjust((0, false), (adjust, true)); 371 } 372 shrink_right(&mut self, adjust: usize)373 pub(crate) fn shrink_right(&mut self, adjust: usize) { 374 self.adjust((adjust, false), (adjust, true)); 375 } 376 adjust(&mut self, adjust_offset: (usize, bool), adjust_len: (usize, bool))377 fn adjust(&mut self, adjust_offset: (usize, bool), adjust_len: (usize, bool)) { 378 #[inline(always)] 379 fn modify(val: &mut usize, adj: (usize, bool)) { 380 if adj.1 { 381 *val -= adj.0; 382 } else { 383 *val += adj.0; 384 } 385 } 386 387 match self { 388 DiffOp::Equal { 389 old_index, 390 new_index, 391 len, 392 } => { 393 modify(old_index, adjust_offset); 394 modify(new_index, adjust_offset); 395 modify(len, adjust_len); 396 } 397 DiffOp::Delete { 398 old_index, 399 old_len, 400 new_index, 401 } => { 402 modify(old_index, adjust_offset); 403 modify(old_len, adjust_len); 404 modify(new_index, adjust_offset); 405 } 406 DiffOp::Insert { 407 old_index, 408 new_index, 409 new_len, 410 } => { 411 modify(old_index, adjust_offset); 412 modify(new_index, adjust_offset); 413 modify(new_len, adjust_len); 414 } 415 DiffOp::Replace { 416 old_index, 417 old_len, 418 new_index, 419 new_len, 420 } => { 421 modify(old_index, adjust_offset); 422 modify(old_len, adjust_len); 423 modify(new_index, adjust_offset); 424 modify(new_len, adjust_len); 425 } 426 } 427 } 428 } 429 430 #[cfg(feature = "text")] 431 mod text_additions { 432 use super::*; 433 use crate::text::DiffableStr; 434 use std::borrow::Cow; 435 436 /// The text interface can produce changes over [`DiffableStr`] implementing 437 /// values. As those are generic interfaces for different types of strings 438 /// utility methods to make working with standard rust strings more enjoyable. 439 impl<'s, T: DiffableStr + ?Sized> Change<'s, T> { 440 /// Returns the value as string if it is utf-8. as_str(&self) -> Option<&'s str>441 pub fn as_str(&self) -> Option<&'s str> { 442 T::as_str(self.value) 443 } 444 445 /// Returns the value (lossy) decoded as utf-8 string. to_string_lossy(&self) -> Cow<'s, str>446 pub fn to_string_lossy(&self) -> Cow<'s, str> { 447 T::to_string_lossy(self.value) 448 } 449 450 /// Returns `true` if this change does not end in a newline and must be 451 /// followed up by one if line based diffs are used. 452 /// 453 /// The [`std::fmt::Display`] implementation of [`Change`] will automatically 454 /// insert a newline after the value if this is true. missing_newline(&self) -> bool455 pub fn missing_newline(&self) -> bool { 456 !T::ends_with_newline(self.value) 457 } 458 } 459 460 impl<'s, T: DiffableStr + ?Sized> fmt::Display for Change<'s, T> { fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result461 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { 462 write!( 463 f, 464 "{}{}", 465 self.to_string_lossy(), 466 if self.missing_newline() { "\n" } else { "" } 467 ) 468 } 469 } 470 } 471