vendor/imara-diff/src/histogram/lcs.rs

   1 use crate::histogram::{Histogram, MAX_CHAIN_LEN};
   2 use crate::intern::Token;
   3
   4 pub(super) fn find_lcs(
   5     before: &[Token],
   6     after: &[Token],
   7     histogram: &mut Histogram,
   8 ) -> Option<Lcs> {
   9     let mut search =
  10         LcsSearch { lcs: Lcs::default(), min_occurances: MAX_CHAIN_LEN + 1, found_cs: false };
  11     search.run(before, after, histogram);
  12     if search.success() {
  13         Some(search.lcs)
  14     } else {
  15         None
  16     }
  17 }
  18
  19 #[derive(Default, Debug)]
  20 pub struct Lcs {
  21     pub before_start: u32,
  22     pub after_start: u32,
  23     pub len: u32,
  24 }
  25
  26 pub struct LcsSearch {
  27     lcs: Lcs,
  28     min_occurances: u32,
  29     found_cs: bool,
  30 }
  31
  32 impl LcsSearch {
  33     fn run(&mut self, before: &[Token], after: &[Token], histogram: &mut Histogram) {
  34         let mut pos = 0;
  35         while let Some(&token) = after.get(pos as usize) {
  36             if histogram.num_token_occurances(token) != 0 {
  37                 self.found_cs = true;
  38                 if histogram.num_token_occurances(token) <= self.min_occurances {
  39                     pos = self.update_lcs(pos, token, histogram, before, after);
  40                     continue;
  41                 }
  42             }
  43
  44             pos += 1;
  45         }
  46
  47         histogram.clear();
  48     }
  49
  50     fn success(&mut self) -> bool {
  51         !self.found_cs || self.min_occurances <= MAX_CHAIN_LEN
  52     }
  53
  54     fn update_lcs(
  55         &mut self,
  56         after_pos: u32,
  57         token: Token,
  58         histogram: &Histogram,
  59         before: &[Token],
  60         after: &[Token],
  61     ) -> u32 {
  62         let mut next_token_idx2 = after_pos + 1;
  63         let mut occurances_iter = histogram.token_occurances(token).iter().copied();
  64         let mut token_idx1 = occurances_iter.next().unwrap();
  65
  66         'occurances_iter: loop {
  67             let mut occurances = histogram.num_token_occurances(token);
  68             let mut start1 = token_idx1;
  69             let mut start2 = after_pos;
  70             loop {
  71                 if start1 == 0 || start2 == 0 {
  72                     break;
  73                 }
  74                 let token1 = before.get(start1 as usize - 1);
  75                 let token2 = after.get(start2 as usize - 1);
  76                 if matches!((token1, token2), (Some(token1), Some(token2)) if token1 == token2) {
  77                     start1 -= 1;
  78                     start2 -= 1;
  79                     let new_occurances = histogram.num_token_occurances(before[start1 as usize]);
  80                     occurances = occurances.min(new_occurances);
  81                 } else {
  82                     break;
  83                 }
  84             }
  85
  86             let mut end1 = token_idx1 + 1;
  87             let mut end2 = after_pos + 1;
  88
  89             loop {
  90                 let token1 = before.get(end1 as usize);
  91                 let token2 = after.get(end2 as usize);
  92                 if matches!((token1, token2), (Some(token1), Some(token2)) if token1 == token2) {
  93                     let new_occurances = histogram.num_token_occurances(before[end1 as usize]);
  94                     occurances = occurances.min(new_occurances);
  95                     end1 += 1;
  96                     end2 += 1;
  97                 } else {
  98                     break;
  99                 }
 100             }
 101
 102             if next_token_idx2 < end2 {
 103                 next_token_idx2 = end2;
 104             }
 105
 106             let len = end2 - start2;
 107             debug_assert_eq!(len, end1 - start1);
 108             if self.lcs.len < len || self.min_occurances > occurances {
 109                 self.min_occurances = occurances;
 110                 self.lcs = Lcs { before_start: start1, after_start: start2, len };
 111             }
 112
 113             loop {
 114                 if let Some(next_token_idx) = occurances_iter.next() {
 115                     if next_token_idx > end2 {
 116                         token_idx1 = next_token_idx;
 117                         break;
 118                     }
 119                 } else {
 120                     break 'occurances_iter;
 121                 }
 122             }
 123         }
 124
 125         next_token_idx2
 126     }
 127 }