/rust/registry/src/index.crates.io-1949cf8c6b5b557f/dmp-0.2.3/src/lib.rs

Source
mod diff;
#[cfg(any(test, fuzzing))]
pub mod fuzz;
mod patch;

pub use crate::diff::Diff;
pub use crate::patch::Patch;
use core::char;
use std::collections::HashMap;
use std::iter::FromIterator;
use std::result::Result;
use trice::Instant;
use urlencoding::decode;

pub enum LengthUnit {
  UnicodeScalar,
  UTF16,
}

pub struct Dmp {
  /// Number of seconds to map a diff before giving up (None for infinity).
  pub diff_timeout: Option<f32>,
  /// Cost of an empty edit operation in terms of edit characters.
  pub edit_cost: i32,
  /// How far to search for a match (0 = exact location, 1000+ = broad match).
  /// A match this many characters away from the expected location will add
  /// 1.0 to the score (0.0 is a perfect match).
  pub match_distance: i32,
  /// Chunk size for context length.
  pub patch_margin: i32,
  /// The number of bits in an int.
  /// Python has no maximum, thus to disable patch splitting set to 0.
  /// However to avoid long patches in certain pathological cases, use 32.
  /// Multiple short patches (using native ints) are much faster than long ones.
  pub match_maxbits: i32,
  /// At what point is no match declared (0.0 = perfection, 1.0 = very loose).
  pub match_threshold: f32,
  /// When deleting a large block of text (over ~64 characters), how close do
  /// the contents have to be to match the expected contents. (0.0 = perfection,
  /// 1.0 = very loose). Note that match_threshold controls how closely the
  /// end points of a delete need to match.
  pub patch_delete_threshold: f32,
}

pub fn new() -> Dmp {
  Dmp::default()
}

#[derive(Debug)]
pub enum Error {
  InvalidInput,
  MalformedPatch,
  PatternTooLong,
}

fn min(x: i32, y: i32) -> i32 {
  x.min(y)
}

fn min1(x: f32, y: f32) -> f32 {
  // return minimum element.
  if x > y {
    return y;
  }
  x
}

fn max(x: i32, y: i32) -> i32 {
  x.max(y)
}

/// Returns the first index of a character after a index or return -1 if not found.
fn find_char(cha: char, text: &[char], start: usize) -> i32 {
  for (i, text_item) in text.iter().enumerate().skip(start) {
    if *text_item == cha {
      return i as i32;
    }
  }
  -1
}

impl Default for Dmp {
  fn default() -> Self {
    Dmp {
      diff_timeout: None,
      patch_delete_threshold: 0.5,
      edit_cost: 0,
      match_distance: 1000,
      patch_margin: 4,
      match_maxbits: 32,
      match_threshold: 0.5,
    }
  }
}

impl Dmp {
  /// Find the differences between two chars.  Simplifies the problem by
  /// stripping any common prefix or suffix off the texts before diffing.
  ///
  /// # Args
  /// - text1: Old chars to be diffed.
  /// - text2: New chars to be diffed.
  /// - checklines: Optional speedup flag. If present and false, then don't run
  ///   a line-level diff first to identify the changed areas.
  ///   Defaults to true, which does a faster, slightly less optimal diff.
  ///
  /// # Return
  /// Vector of diffs as changes.
  pub fn diff_main(&self, text1: &str, text2: &str, checklines: bool) -> Vec<Diff> {
    self.diff_main_internal(text1, text2, checklines, Instant::now())
  }

  fn diff_main_internal(
    &self,
    text1: &str,
    text2: &str,
    checklines: bool,
    start_time: Instant,
  ) -> Vec<Diff> {
    // check for empty text
    if text1.is_empty() && text2.is_empty() {
      return vec![];
    } else if text1.is_empty() {
      return vec![Diff::new(1, text2.to_string())];
    } else if text2.is_empty() {
      return vec![Diff::new(-1, text1.to_string())];
    }

    // check for equality
    if text1 == text2 {
      return vec![Diff::new(0, text1.to_string())];
    }

    let mut char1: Vec<char> = text1.chars().collect();
    let mut char2: Vec<char> = text2.chars().collect();
    // Trim off common prefix (speedup).
    let mut commonlength = self.diff_common_prefix(&char1, &char2) as usize;
    let commonprefix = Vec::from_iter(char1[0..commonlength].iter().cloned());
    char1 = Vec::from_iter(char1[commonlength..].iter().cloned());
    char2 = Vec::from_iter(char2[commonlength..].iter().cloned());

    // Trim off common suffix (speedup).
    commonlength = self.diff_common_suffix(&char1, &char2) as usize;
    let commonsuffix =
      Vec::from_iter(char1[(char1.len() - commonlength)..char1.len()].iter().cloned());
    char1 = Vec::from_iter(char1[..(char1.len() - commonlength)].iter().cloned());
    char2 = Vec::from_iter(char2[..(char2.len() - commonlength)].iter().cloned());
    let mut diffs: Vec<Diff> = Vec::new();

    //Restore the prefix
    if !commonprefix.is_empty() {
      diffs.push(Diff::new(0, commonprefix.iter().collect()));
    }

    // Compute the diff on the middle block.
    let temp = self.diff_compute(&char1, &char2, checklines, start_time);
    for z in temp {
      diffs.push(z);
    }

    // Restore the suffix
    if !commonsuffix.is_empty() {
      diffs.push(Diff::new(0, commonsuffix.iter().collect()));
    }
    self.diff_cleanup_merge(&mut diffs);
    diffs
  }

  /// Find the differences between two texts.  Assumes that the texts do not
  /// have any common prefix or suffix.
  ///
  /// # Args
  /// - text1: Old chars to be diffed.
  /// - text2: New chars to be diffed.
  /// - checklines: Speedup flag.  If false, then don't run a line-level diff
  ///   first to identify the changed areas.
  ///   If true, then run a faster, slightly less optimal diff.
  ///
  /// # Return
  /// Vector of diffs as changes.
  fn diff_compute(
    &self,
    text1: &Vec<char>,
    text2: &Vec<char>,
    checklines: bool,
    start_time: Instant,
  ) -> Vec<Diff> {
    let mut diffs: Vec<Diff> = Vec::new();
    if text1.is_empty() {
      // Just add some text (speedup).
      diffs.push(Diff::new(1, text2.iter().collect()));
      return diffs;
    } else if text2.is_empty() {
      // Just delete some text (speedup).
      diffs.push(Diff::new(-1, text1.iter().collect()));
      return diffs;
    }
    {
      let len1 = text1.len();
      let len2 = text2.len();
      let (longtext, shorttext) = if len1 >= len2 {
        (text1, text2)
      } else {
        (text2, text1)
      };
      let i = self.kmp(longtext, shorttext, 0);
      if i != -1 {
        // Shorter text is inside the longer text (speedup).
        if len1 > len2 {
          if i != 0 {
            diffs.push(Diff::new(-1, (text1[0..(i as usize)]).iter().collect()));
          }
          diffs.push(Diff::new(0, text2.iter().collect()));
          if i as usize + text2.len() != text1.len() {
            diffs.push(Diff::new(
              -1,
              text1[((i as usize) + text2.len())..].iter().collect(),
            ));
          }
        } else {
          if i != 0 {
            diffs.push(Diff::new(1, (text2[0..(i as usize)]).iter().collect()));
          }
          diffs.push(Diff::new(0, text1.iter().collect()));
          if (i as usize) + text1.len() != text2.len() {
            diffs.push(Diff::new(
              1,
              text2[((i as usize) + text1.len())..].iter().collect(),
            ));
          }
        }
        return diffs;
      }
      if shorttext.len() == 1 {
        // Single character string.
        // After the previous speedup, the character can't be an equality.
        diffs.push(Diff::new(-1, text1.iter().collect()));
        diffs.push(Diff::new(1, text2.iter().collect()));
        return diffs;
      }
    }
    // Check to see if the problem can be split in two.
    let hm = self.diff_half_match(text1, text2);
    if !hm.is_empty() {
      // A half-match was found, sort out the return data.
      let text1_a = hm[0].clone();
      let text1_b = hm[1].clone();
      let text2_a = hm[2].clone();
      let text2_b = hm[3].clone();
      let mid_common = hm[4].clone();
      // Send both pairs off for separate processing.
      let mut diffs_a =
        self.diff_main_internal(text1_a.as_str(), text2_a.as_str(), checklines, start_time);
      let diffs_b =
        self.diff_main_internal(text1_b.as_str(), text2_b.as_str(), checklines, start_time);
      diffs_a.push(Diff::new(0, mid_common));
      // Merge the result.
      for x in diffs_b {
        diffs_a.push(x);
      }
      return diffs_a;
    }
    if checklines && text1.len() > 100 && text2.len() > 100 {
      return self.diff_linemode_internal(text1, text2, start_time);
    }
    self.diff_bisect_internal(text1, text2, start_time)
  }

  /// Find the first index after a specific index in text1 where patern is present.
  ///
  /// # Args
  /// - text1: Parent chars.
  /// - text2: Patern chars.
  /// - ind: index after which we have to find the patern.
  ///
  /// # Returns
  /// the first index where pattern is found or -1 if not found.
  fn kmp(&self, text1: &[char], text2: &[char], ind: usize) -> i32 {
    if text2.is_empty() {
      return ind as i32;
    }
    if text1.is_empty() {
      return -1;
    }
    let len1 = text1.len();
    let len2 = text2.len();
    let mut patern: Vec<usize> = Vec::new();
    patern.push(0);
    let mut len = 0;
    let mut i = 1;

    // Preprocess the pattern
    while i < len2 {
      if text2[i] == text2[len] {
        len += 1;
        patern.push(len);
        i += 1;
      } else if len == 0 {
        patern.push(0);
        i += 1;
      } else {
        len = patern[len - 1];
      }
    }
    i = ind;
    len = 0;
    while i < len1 {
      if text1[i] == text2[len] {
        len += 1;
        i += 1;
        if len == len2 {
          return (i - len) as i32;
        }
      } else if len == 0 {
        i += 1;
      } else {
        len = patern[len - 1];
      }
    }
    -1
  }

  /// Find the last index before a specific index in text1 where patern is present.
  ///
  /// # Args
  /// - text1: Parent chars.
  /// - text2: Patern chars.
  /// - ind: index just before we have to find the patern.
  ///
  /// # Return
  /// The last index where patern is found or -1 if not found.
  fn rkmp(&self, text1: &[char], text2: &[char], ind: usize) -> i32 {
    if text2.is_empty() {
      return ind as i32;
    }
    if text1.is_empty() {
      return -1;
    }
    let len2 = text2.len();
    let mut patern: Vec<usize> = Vec::new();
    patern.push(0);
    let mut len = 0;
    let mut i = 1;

    // Preprocess the pattern
    while i < len2 {
      if text2[i] == text2[len] {
        len += 1;
        patern.push(len);
        i += 1;
      } else if len == 0 {
        patern.push(0);
        i += 1;
      } else {
        len = patern[len - 1];
      }
    }
    i = 0;
    len = 0;
    let mut ans: i32 = -1;
    while i <= ind {
      if text1[i] == text2[len] {
        len += 1;
        i += 1;
        if len == len2 {
          ans = (i - len) as i32;
          len = patern[len - 1];
        }
      } else if len == 0 {
        i += 1;
      } else {
        len = patern[len - 1];
      }
    }
    ans
  }

  // Do a quick line-level diff on both chars, then rediff the parts for
  // greater accuracy.
  // This speedup can produce non-minimal diffs.
  //
  // # Args
  // - text1: Old chars to be diffed.
  // - text2: New chars to be diffed.
  //
  // # Return
  // Vector of diffs as changes.
  //pub fn diff_linemode(&self, text1: &Vec<char>, text2: &Vec<char>) -> Vec<Diff> {
  //    self.diff_linemode_internal(text1, text2, Instant::now())
  //}

  fn diff_linemode_internal(
    &self,
    text1: &[char],
    text2: &[char],
    start_time: Instant,
  ) -> Vec<Diff> {
    // Scan the text on a line-by-line basis first.
    let (text3, text4, linearray) = self.diff_lines_tochars(text1, text2);

    let dmp = Dmp::default();
    let mut diffs: Vec<Diff> =
      dmp.diff_main_internal(text3.as_str(), text4.as_str(), false, start_time);

    // Convert the diff back to original text.
    self.diff_chars_tolines(&mut diffs, &linearray);
    // Eliminate freak matches (e.g. blank lines)
    self.diff_cleanup_semantic(&mut diffs);

    // Rediff any replacement blocks, this time character-by-character.
    // Add a dummy entry at the end.
    diffs.push(Diff::new(0, "".to_string()));
    let mut count_delete = 0;
    let mut count_insert = 0;
    let mut text_delete: String = "".to_string();
    let mut text_insert: String = "".to_string();
    let mut pointer = 0;
    let mut temp: Vec<Diff> = vec![];
    while pointer < diffs.len() {
      if diffs[pointer].operation == 1 {
        count_insert += 1;
        text_insert += diffs[pointer].text.as_str();
      } else if diffs[pointer].operation == -1 {
        count_delete += 1;
        text_delete += diffs[pointer].text.as_str();
      } else {
        // Upon reaching an equality, check for prior redundancies.
        if count_delete >= 1 && count_insert >= 1 {
          // Delete the offending records and add the merged ones.
          let sub_diff = self.diff_main_internal(
            text_delete.as_str(),
            text_insert.as_str(),
            false,
            start_time,
          );
          for z in sub_diff {
            temp.push(z);
          }
          temp.push(Diff::new(diffs[pointer].operation, diffs[pointer].text.clone()));
        } else {
          if !text_delete.is_empty() {
            temp.push(Diff::new(-1, text_delete));
          }
          if !text_insert.is_empty() {
            temp.push(Diff::new(1, text_insert));
          }
          temp.push(Diff::new(diffs[pointer].operation, diffs[pointer].text.clone()));
        }
        count_delete = 0;
        count_insert = 0;
        text_delete = "".to_string();
        text_insert = "".to_string();
      }
      pointer += 1;
    }
    temp.pop(); //Remove the dummy entry at the end.
    temp
  }

  // Find the 'middle snake' of a diff, split the problem in two
  // and return the recursively constructed diff.
  // See Myers 1986 paper: An O(ND) Difference Algorithm and Its Variations.
  //
  // # Args
  // - text1: Old chars to be diffed.
  // - text2: New chars to be diffed.
  //
  // # Return
  // - Vector of diffs as changes.
  //fn diff_bisect(&self, char1: &Vec<char>, char2: &Vec<char>) -> Vec<Diff> {
  //    self.diff_bisect_internal(char1, char2, Instant::now())
  //}

  fn diff_bisect_internal(
    &self,
    char1: &[char],
    char2: &[char],
    start_time: Instant,
  ) -> Vec<Diff> {
    let text1_length = char1.len() as i32;
    let text2_length = char2.len() as i32;
    let max_d: i32 = (text1_length + text2_length + 1) / 2;
    let v_offset: i32 = max_d;
    let v_length: i32 = 2 * max_d;
    let mut v1: Vec<i32> = vec![-1; v_length as usize];
    let mut v2: Vec<i32> = vec![-1; v_length as usize];
    v1[v_offset as usize + 1] = 0;
    v2[v_offset as usize + 1] = 0;
    let delta: i32 = text1_length - text2_length;
    // If the total number of characters is odd, then the front path will
    // collide with the reverse path.
    let front: i32 = (delta % 2 != 0) as i32;
    // Offsets for start and end of k loop.
    // Prevents mapping of space beyond the grid.
    let mut k1start: i32 = 0;
    let mut k1end: i32 = 0;
    let mut k2start: i32 = 0;
    let mut k2end: i32 = 0;
    for d in 0..max_d {
      if let Some(diff_timeout) = self.diff_timeout {
        if start_time.elapsed().as_secs_f32() >= diff_timeout {
          break;
        }
      }

      let d1 = d;
      let mut k1 = -d1 + k1start;
      let mut x1: i32;
      let mut k1_offset: i32;
      let mut k2_offset;
      let mut x2;
      let mut y1;
      // Walk the front path one step.
      while k1 < d1 + 1 - k1end {
        k1_offset = v_offset + k1;
        if k1 == -d1
          || (k1 != d1 && v1[k1_offset as usize - 1] < v1[k1_offset as usize + 1])
        {
          x1 = v1[k1_offset as usize + 1];
        } else {
          x1 = v1[k1_offset as usize - 1] + 1;
        }
        y1 = x1 - k1;
        while x1 < text1_length && y1 < text2_length {
          let i1 = if x1 < 0 {
            text1_length + x1
          } else {
            x1
          };
          let i2 = if y1 < 0 {
            text2_length + y1
          } else {
            y1
          };
          if char1[i1 as usize] != char2[i2 as usize] {
            break;
          }
          x1 += 1;
          y1 += 1;
        }
        v1[k1_offset as usize] = x1;
        if x1 > text1_length {
          // Ran off the right of the graph.
          k1end += 2;
        } else if y1 > text2_length {
          // Ran off the bottom of the graph.
          k1start += 2;
        } else if front != 0 {
          k2_offset = v_offset + delta - k1;
          if k2_offset >= 0 && k2_offset < v_length && v2[k2_offset as usize] != -1 {
            // Mirror x2 onto top-left coordinate system.
            x2 = text1_length - v2[k2_offset as usize];
            if x1 >= x2 {
              // Overlap detected.
              return self.diff_bisect_split(char1, char2, x1, y1, start_time);
            }
          }
        }
        k1 += 2;
      }
      let mut k2 = -d1 + k2start;
      let mut y2;
      // Walk the reverse path one step.
      while k2 < d1 + 1 - k2end {
        k2_offset = v_offset + k2;
        if k2 == -d1
          || (k2 != d1 && v2[k2_offset as usize - 1] < v2[k2_offset as usize + 1])
        {
          x2 = v2[k2_offset as usize + 1];
        } else {
          x2 = v2[k2_offset as usize - 1] + 1;
        }
        y2 = x2 - k2;
        while x2 < text1_length && y2 < text2_length {
          let i1 = if text1_length - x2 > 0 {
            text1_length - x2 - 1
          } else {
            x2 + 1
          };
          let i2 = if text2_length - y2 > 0 {
            text2_length - y2 - 1
          } else {
            y2 + 1
          };
          if char1[i1 as usize] != char2[i2 as usize] {
            break;
          }
          x2 += 1;
          y2 += 1;
        }
        v2[k2_offset as usize] = x2;
        if x2 > text1_length {
          // Ran off the left of the graph.
          k2end += 2;
        } else if y2 > text2_length {
          // Ran off the top of the graph.
          k2start += 2;
        } else if front == 0 {
          k1_offset = v_offset + delta - k2;
          if k1_offset >= 0 && k1_offset < v_length && v1[k1_offset as usize] != -1 {
            x1 = v1[k1_offset as usize];
            y1 = v_offset + x1 - k1_offset;
            // Mirror x2 onto top-left coordinate system.
            x2 = text1_length - x2;
            if x1 >= x2 {
              // Overlap detected.
              return self.diff_bisect_split(char1, char2, x1, y1, start_time);
            }
          }
        }
        k2 += 2;
      }
    }
    // number of diffs equals number of characters, no commonality at all.
    vec![Diff::new(-1, char1.iter().collect()), Diff::new(1, char2.iter().collect())]
  }

  /// Given the location of the 'middle snake', split the diff in two parts
  /// and recurse.
  ///
  /// # Args
  /// - text1: Old text1 to be diffed.
  /// - text2: New text1 to be diffed.
  /// - x: Index of split point in text1.
  /// - y: Index of split point in text2.
  ///
  /// # Return
  /// Vector of diffs as changes.
  fn diff_bisect_split(
    &self,
    text1: &[char],
    text2: &[char],
    x: i32,
    y: i32,
    start_time: Instant,
  ) -> Vec<Diff> {
    let text1a: String = text1[..(x as usize)].iter().collect();
    let text2a: String = text2[..(y as usize)].iter().collect();
    let text1b: String = text1[(x as usize)..].iter().collect();
    let text2b: String = text2[(y as usize)..].iter().collect();

    // Compute both diffs serially.
    let mut diffs =
      self.diff_main_internal(text1a.as_str(), text2a.as_str(), false, start_time);
    let mut diffsb =
      self.diff_main_internal(text1b.as_str(), text2b.as_str(), false, start_time);
    diffs.append(&mut diffsb);
    diffs
  }

  /*
  /// Split two texts into an array of strings.  Reduce the texts to a string
  /// of hashes where each Unicode character represents one word.
  ///
  /// # Args
  /// - text1: First chars.
  /// - text2: Second chars.
  ///
  /// # Return
  /// Three element tuple, containing the encoded text1, the encoded text2 and
  /// the array of unique strings.  The zeroth element of the array of unique
  /// strings is intentionally blank.
  fn diff_words_tochars(
    &self,
    text1: &String,
    text2: &String,
  ) -> (String, String, Vec<String>) {
    let mut wordarray: Vec<String> = vec!["".to_string()];
    let mut wordhash: HashMap<String, u32> = HashMap::new();
    let chars1 = self.diff_words_tochars_munge(text1, &mut wordarray, &mut wordhash);
    let dmp = Dmp::new();
    let chars2 = dmp.diff_words_tochars_munge(text2, &mut wordarray, &mut wordhash);
    (chars1, chars2, wordarray)
  }
  */

  /*
  /// Split a text into an array of strings.  Reduce the texts to a string
  /// of hashes where each Unicode character represents one word.
  /// Modifies wordarray and wordhash through being a closure.
  ///
  /// # Args
  /// - text: chars to encode.
  ///
  /// # Return
  /// Encoded string.
  fn diff_words_tochars_munge(
    &self,
    text: &String,
    wordarray: &mut Vec<String>,
    wordhash: &mut HashMap<String, u32>,
  ) -> String {
    let mut chars = "".to_string();

    let re = Regex::new(r"[\s\n\r]").unwrap();
    let mut prev_end: usize = 0;
    for part in re.find_iter(&text) {
      if prev_end < part.start() {
        let word = &text[prev_end..part.start()];
        chars += &self.make_token_dict(word, wordarray, wordhash);
      }
      let word = &text[part.start()..part.end()];
      chars += &self.make_token_dict(word, wordarray, wordhash);
      prev_end = part.end();
    }
    if prev_end < text.len() {
      let word = &text[prev_end..text.len()];
      chars += &self.make_token_dict(word, wordarray, wordhash);
    }
    chars
  }
  */

  /*
  fn make_token_dict(
    &self,
    word: &str,
    wordarray: &mut Vec<String>,
    wordhash: &mut HashMap<String, u32>,
  ) -> String {
    if !wordhash.contains_key(word) {
      wordarray.push(word.to_string());
      wordhash.insert(word.to_string(), wordarray.len() as u32 - 1);
    }
    char::from_u32(wordhash[word]).unwrap().to_string()
  }
  */

  /// Split two texts into an array of strings.  Reduce the texts to a string
  /// of hashes where each Unicode character represents one line.
  ///
  /// Args
  /// - text1: First chars.
  /// - text2: Second chars.
  ///
  /// Return
  /// Three element tuple, containing the encoded text1, the encoded text2 and
  /// the array of unique strings.  The zeroth element of the array of unique
  /// strings is intentionally blank.
  fn diff_lines_tochars(&self, text1: &[char], text2: &[char]) -> (String, String, Vec<String>) {
    let mut linearray: Vec<String> = vec!["".to_string()];
    let mut linehash: HashMap<String, i32> = HashMap::new();
    let chars1 = self.diff_lines_tochars_munge(text1, &mut linearray, &mut linehash);
    let dmp = Dmp::default();
    let chars2 = dmp.diff_lines_tochars_munge(text2, &mut linearray, &mut linehash);
    (chars1, chars2, linearray)
  }

  /// Split a text into an array of strings.  Reduce the texts to a string
  /// of hashes where each Unicode character represents one line.
  /// Modifies linearray and linehash through being a closure.
  ///
  /// Args
  /// - text: chars to encode.
  ///
  /// Return
  /// Encoded string.
  fn diff_lines_tochars_munge(
    &self,
    text: &[char],
    linearray: &mut Vec<String>,
    linehash: &mut HashMap<String, i32>,
  ) -> String {
    let mut chars = "".to_string();
    // Walk the text, pulling out a substring for each line.
    // text.split('\n') would would temporarily double our memory footprint.
    // Modifying text would create many large strings to garbage collect.
    let mut line_start = 0;
    let mut line_end = -1;
    let mut line: String;
    while line_end < (text.len() as i32 - 1) {
      line_end = find_char('\n', text, line_start as usize);
      if line_end == -1 {
        line_end = text.len() as i32 - 1;
      }
      line = text[line_start as usize..=line_end as usize].iter().collect();
      if linehash.contains_key(&line) {
        if let Some(char1) = char::from_u32(linehash[&line] as u32) {
          chars.push(char1);
          line_start = line_end + 1;
        }
      } else {
        let mut u32char = linearray.len() as i32;

        // skip reserved range - U+D800 to U+DFFF
        // unicode code points in this range can't be converted to unicode scalars
        if u32char >= 55296 {
          u32char += 2048;
        }

        // 1114111 is the biggest unicode scalar, so stop here
        if u32char == 1114111 {
          line = text[(line_start as usize)..].iter().collect();
          line_end = text.len() as i32 - 1;
        }

        linearray.push(line.clone());
        linehash.insert(line.clone(), u32char);

        chars.push(char::from_u32(u32char as u32).unwrap());
        line_start = line_end + 1;
      }
    }
    chars
  }

  /// Rehydrate the text in a diff from a string of line hashes to real lines
  /// of text.
  ///
  /// Args
  /// - diffs: Vector of diffs as changes.
  /// - lineArray: Vector of unique strings.
  pub fn diff_chars_tolines(&self, diffs: &mut Vec<Diff>, line_array: &[String]) {
    for d in diffs {
      let mut text: String = "".to_string();
      let text1 = d.text.clone();
      let chars: Vec<char> = text1.chars().collect();
      for j in 0..chars.len() {
        text += line_array[chars[j] as usize].as_str();
      }
      d.text = text;
    }
  }

  /// Determine the common prefix of two chars.
  ///
  /// Args:
  /// - text1: First chars.
  /// - text2: Second chars.
  ///
  /// Returns:
  /// The number of characters common to the start of each chars.
  fn diff_common_prefix(&self, text1: &[char], text2: &[char]) -> i32 {
    if text1.is_empty() || text2.is_empty() {
      return 0;
    }
    let pointermax = min(text1.len() as i32, text2.len() as i32);
    let mut pointerstart = 0;
    while pointerstart < pointermax {
      if text1[pointerstart as usize] == text2[pointerstart as usize] {
        pointerstart += 1;
      } else {
        return pointerstart;
      }
    }
    pointermax
  }

  /// Determine the common suffix of two strings.
  ///
  /// # Args
  /// - text1: First chars.
  /// - text2: Second chars.
  ///
  /// # Return
  /// The number of characters common to the end of each chars.
  fn diff_common_suffix(&self, text1: &[char], text2: &[char]) -> i32 {
    if text1.is_empty() || text2.is_empty() {
      return 0;
    }
    let mut pointer_1 = text1.len() as i32 - 1;
    let mut pointer_2 = text2.len() as i32 - 1;
    let mut len = 0;
    while pointer_1 >= 0 && pointer_2 >= 0 {
      if text1[pointer_1 as usize] == text2[pointer_2 as usize] {
        len += 1;
      } else {
        break;
      }
      pointer_1 -= 1;
      pointer_2 -= 1;
    }
    len
  }

  /// Determine if the suffix of one chars is the prefix of another.
  ///
  /// # Args
  /// - text1 First chars.
  /// - text2 Second chars.
  ///
  /// # Return
  /// The number of characters common to the end of the first
  /// chars and the start of the second chars.
  fn diff_common_overlap(&self, text1: &[char], text2: &[char]) -> i32 {
    let text1_length = text1.len();
    let text2_length = text2.len();
    if text1_length == 0 || text2_length == 0 {
      return 0;
    }
    let text1_trunc;
    let text2_trunc;
    let len = min(text1_length as i32, text2_length as i32);

    // Truncate the longer chars.
    if text1.len() > text2.len() {
      text1_trunc = text1[(text1_length - text2_length)..].to_vec();
      text2_trunc = text2[..].to_vec();
    } else {
      text1_trunc = text1[..].to_vec();
      text2_trunc = text2[0..text1_length].to_vec();
    }
    let mut best = 0;
    let mut length = 1;
    // Quick check for the worst case.
    if text1_trunc == text2_trunc {
      return len;
    }
    /*Start by looking for a single character match
    and increase length until no match is found.
    Performance analysis: https://neil.fraser.name/news/2010/11/04/ */
    loop {
      let patern = text1_trunc[(len as usize - length)..(len as usize)].to_vec();
      let found = self.kmp(&text2_trunc, &patern, 0);
      if found == -1 {
        return best;
      }
      length += found as usize;
      if found == 0 {
        best = length as i32;
        length += 1;
      }
    }
  }

  /// split the string accoring to given character
  ///
  /// # Args
  /// - text: string we have to split
  /// - ch: character by which we have to split string
  ///
  /// # Return
  /// Vector of string after spliting according to character.
  fn split_by_char(&self, text: &str, ch: char) -> Vec<String> {
    text.split(ch).map(str::to_owned).collect()
  }

  /// split the string accoring to given characters "@@ ".
  ///
  /// # Args
  /// - text: string we have to split
  ///
  /// # Return
  /// Vector of string after spliting according to characters.
  fn split_by_chars(&self, text: &str) -> Vec<String> {
    text.split("@@ ").map(str::to_owned).collect()
  }

  /// Do the two texts share a substring which is at least half the length of
  /// the longer text?
  /// This speedup can produce non-minimal diffs.
  ///
  /// # Args
  /// - text1: First chars.
  /// - text2: Second chars.
  ///
  /// # Return
  /// Five element Vector, containing the prefix of text1, the suffix of text1,
  /// the prefix of text2, the suffix of text2 and the common middle.  Or empty vector
  /// if there was no match.
  fn diff_half_match(&self, text1: &Vec<char>, text2: &Vec<char>) -> Vec<String> {
    // Don't risk returning a non-optimal diff if we have unlimited time.
    if self.diff_timeout.is_none() {
      return vec![];
    }

    let (long_text, short_text) = if text1.len() > text2.len() {
      (text1, text2)
    } else {
      (text2, text1)
    };
    let len1 = short_text.len();
    let len2 = long_text.len();
    if len2 < 4 || len1 * 2 < len2 {
      return vec![];
    }

    let mut hm: Vec<String>;
    //First check if the second quarter is the seed for a half-match.
    let hm1 = self.diff_half_matchi(long_text, short_text, (len2 as i32 + 3) / 4);
    // Check again based on the third quarter.
    let hm2 = self.diff_half_matchi(long_text, short_text, (len2 as i32 + 1) / 2);

    if hm1.is_empty() && hm2.is_empty() {
      return vec![];
    } else if hm1.is_empty() {
      hm = hm2;
    } else if hm2.is_empty() {
      hm = hm1;
    } else {
      // Both matched.  Select the longest.
      hm = if hm1[4].len() > hm2[4].len() {
        hm1
      } else {
        hm2
      };
    }
    if text1.len() > text2.len() {
      return hm;
    }
    let mut temp2 = hm[0].clone();
    let mut temp3 = hm[2].clone();
    hm[0] = temp3;
    hm[2] = temp2;
    temp2 = hm[1].clone();
    temp3 = hm[3].clone();
    hm[1] = temp3;
    hm[3] = temp2;
    hm
  }

  /// Does a substring of shorttext exist within longtext such that the
  /// substring is at least half the length of longtext?
  /// Closure, but does not reference any external variables.
  ///
  /// # Args
  /// - longtext: Longer chars.
  /// - shorttext: Shorter chars.
  /// - i: Start index of quarter length substring within longtext.
  ///
  /// # Return
  /// Five element vector, containing the prefix of longtext, the suffix of
  /// longtext, the prefix of shorttext, the suffix of shorttext and the
  /// common middle.  Or empty vector if there was no match.
  fn diff_half_matchi(&self, long_text: &[char], short_text: &[char], i: i32) -> Vec<String> {
    let long_len = long_text.len();
    let seed =
      Vec::from_iter(long_text[(i as usize)..(i as usize + long_len / 4)].iter().cloned());
    let mut best_common = "".to_string();
    let mut best_longtext_a = "".to_string();
    let mut best_longtext_b = "".to_string();
    let mut best_shorttext_a = "".to_string();
    let mut best_shorttext_b = "".to_string();
    let mut j: i32 = self.kmp(short_text, &seed, 0);
    while j != -1 {
      let prefix_length =
        self.diff_common_prefix(&long_text[(i as usize)..], &short_text[(j as usize)..]);
      let suffix_length =
        self.diff_common_suffix(&long_text[..(i as usize)], &short_text[..(j as usize)]);
      if best_common.len() < suffix_length as usize + prefix_length as usize {
        best_common = short_text
          [(j as usize - suffix_length as usize)..(j as usize + prefix_length as usize)]
          .iter()
          .collect();
        best_longtext_a = long_text[..((i - suffix_length) as usize)].iter().collect();
        best_longtext_b = long_text[((i + prefix_length) as usize)..].iter().collect();
        best_shorttext_a = short_text[..((j - suffix_length) as usize)].iter().collect();
        best_shorttext_b = short_text[((j + prefix_length) as usize)..].iter().collect();
      }
      j = self.kmp(short_text, &seed, j as usize + 1);
    }
    if best_common.chars().count() * 2 >= long_text.len() {
      return vec![
        best_longtext_a,
        best_longtext_b,
        best_shorttext_a,
        best_shorttext_b,
        best_common,
      ];
    }
    vec![]
  }

  /// Reduce the number of edits by eliminating semantically trivial
  /// equalities.
  ///
  /// # Args
  /// - diffs: Vectors of diff object.
  pub fn diff_cleanup_semantic(&self, diffs: &mut Vec<Diff>) {
    let mut changes = false;
    let mut equalities: Vec<i32> = vec![]; // Stack of indices where equalities are found.
    let mut last_equality = "".to_string(); // Always equal to diffs[equalities[-1]][1]
    let mut pointer: i32 = 0; // Index of current position.
              // Number of chars that changed prior to the equality.
    let mut length_insertions1 = 0;
    let mut length_deletions1 = 0;
    // Number of chars that changed after the equality.
    let mut length_insertions2 = 0;
    let mut length_deletions2 = 0;
    while (pointer as usize) < diffs.len() {
      if diffs[pointer as usize].operation == 0 {
        // Equality found.
        equalities.push(pointer);
        length_insertions1 = length_insertions2;
        length_insertions2 = 0;
        length_deletions1 = length_deletions2;
        length_deletions2 = 0;
        last_equality = diffs[pointer as usize].text.clone();
      } else {
        // An insertion or deletion.
        if diffs[pointer as usize].operation == 1 {
          length_insertions2 += diffs[pointer as usize].text.chars().count() as i32;
        } else {
          length_deletions2 += diffs[pointer as usize].text.chars().count() as i32;
          // Eliminate an equality that is smaller or equal to the edits on both
          // sides of it.
        }
        let last_equality_len = last_equality.chars().count() as i32;
        if last_equality_len > 0
          && last_equality_len <= max(length_insertions1, length_deletions1)
          && last_equality_len <= max(length_insertions2, length_deletions2)
        {
          // Duplicate record.
          diffs.insert(
            equalities[equalities.len() - 1] as usize,
            Diff::new(-1, last_equality.clone()),
          );
          // Change second copy to insert.
          diffs[equalities[equalities.len() - 1] as usize + 1] = Diff::new(
            1,
            diffs[equalities[equalities.len() - 1] as usize + 1].text.clone(),
          );
          // Throw away the equality we just deleted.
          equalities.pop();
          // Throw away the previous equality (it needs to be reevaluated).
          if !equalities.is_empty() {
            equalities.pop();
          }
          if !equalities.is_empty() {
            pointer = equalities[equalities.len() - 1];
          } else {
            pointer = -1;
          }
          // Reset the counters.
          length_insertions1 = 0;
          length_deletions1 = 0;
          length_insertions2 = 0;
          length_deletions2 = 0;
          last_equality = "".to_string();
          changes = true;
        }
      }
      pointer += 1;
    }
    // Normalize the diff.
    if changes {
      self.diff_cleanup_merge(diffs);
    }
    self.diff_cleanup_semantic_lossless(diffs);

    let mut overlap_length1: i32;
    let mut overlap_length2: i32;
    pointer = 1;
    while (pointer as usize) < diffs.len() {
      if diffs[pointer as usize - 1].operation == -1 && diffs[pointer as usize].operation == 1
      {
        let deletion_vec: Vec<char> = diffs[pointer as usize - 1].text.chars().collect();
        let insertion_vec: Vec<char> = diffs[pointer as usize].text.chars().collect();
        overlap_length1 = self.diff_common_overlap(&deletion_vec, &insertion_vec);
        overlap_length2 = self.diff_common_overlap(&insertion_vec, &deletion_vec);
        if overlap_length1 >= overlap_length2 {
          if (overlap_length1 as f32) >= (deletion_vec.len() as f32 / 2.0)
            || (overlap_length1 as f32) >= (insertion_vec.len() as f32 / 2.0)
          {
            // Overlap found.  Insert an equality and trim the surrounding edits.
            diffs.insert(
              pointer as usize,
              Diff::new(
                0,
                insertion_vec[..(overlap_length1 as usize)].iter().collect(),
              ),
            );
            diffs[pointer as usize - 1] = Diff::new(
              -1,
              deletion_vec[..(deletion_vec.len() - overlap_length1 as usize)]
                .iter()
                .collect(),
            );
            diffs[pointer as usize + 1] = Diff::new(
              1,
              insertion_vec[(overlap_length1 as usize)..].iter().collect(),
            );
            pointer += 1;
          }
        } else if (overlap_length2 as f32) >= (deletion_vec.len() as f32 / 2.0)
          || (overlap_length2 as f32) >= (insertion_vec.len() as f32 / 2.0)
        {
          // Reverse overlap found.
          // Insert an equality and swap and trim the surrounding edits.
          diffs.insert(
            pointer as usize,
            Diff::new(0, deletion_vec[..(overlap_length2 as usize)].iter().collect()),
          );
          let insertion_vec_len = insertion_vec.len();
          diffs[pointer as usize - 1] = Diff::new(
            1,
            insertion_vec[..(insertion_vec_len - overlap_length2 as usize)]
              .iter()
              .collect(),
          );
          diffs[pointer as usize + 1] =
            Diff::new(-1, deletion_vec[(overlap_length2 as usize)..].iter().collect());
          pointer += 1;
        }
        pointer += 1;
      }
      pointer += 1;
    }
  }

  /// Look for single edits surrounded on both sides by equalities
  /// which can be shifted sideways to align the edit to a word boundary.
  /// e.g: The c<ins>at c</ins>ame. -> The <ins>cat </ins>came.
  ///
  /// Args:
  /// - diffs: Vector of diff object.
  pub fn diff_cleanup_semantic_lossless(&self, diffs: &mut Vec<Diff>) {
    let mut pointer = 1;
    let mut equality1;
    let mut equality2;
    let mut edit: String;
    let mut common_offset;
    let mut common_string: String;
    let mut best_equality1;
    let mut best_edit;
    let mut best_equality2;
    let mut best_score;
    let mut score;

    //Intentionally ignore the first and last element (don't need checking).
    while pointer < diffs.len() as i32 - 1 {
      if diffs[pointer as usize - 1].operation == 0
        && diffs[pointer as usize + 1].operation == 0
      {
        //  This is a single edit surrounded by equalities.
        equality1 = diffs[pointer as usize - 1].text.clone();
        edit = diffs[pointer as usize].text.clone();
        equality2 = diffs[pointer as usize + 1].text.clone();
        let mut edit_vec: Vec<char> = edit.chars().collect();
        let mut equality1_vec: Vec<char> = equality1.chars().collect();
        let mut equality2_vec: Vec<char> = equality2.chars().collect();

        // First, shift the edit as far left as possible.
        common_offset = self.diff_common_suffix(&equality1_vec, &edit_vec);
        if common_offset != 0 {
          common_string =
            edit_vec[(edit_vec.len() - common_offset as usize)..].iter().collect();
          equality1 = equality1_vec[..(equality1_vec.len() - common_offset as usize)]
            .iter()
            .collect();
          let temp7: String =
            edit_vec[..(edit_vec.len() - common_offset as usize)].iter().collect();
          edit = common_string.clone() + temp7.as_str();
          equality2 = common_string + equality2.as_str();
          edit_vec = edit.chars().collect();
          equality2_vec = equality2.chars().collect();
          equality1_vec = equality1.chars().collect();
        }
        // Second, step character by character right, looking for the best fit.
        best_equality1 = equality1.clone();
        best_edit = edit;
        best_equality2 = equality2;
        best_score = self.diff_cleanup_semantic_score(&equality1_vec, &edit_vec)
          + self.diff_cleanup_semantic_score(&edit_vec, &equality2_vec);
        let edit_len = edit_vec.len();
        let mut equality2_len = equality2_vec.len();
        while equality2_len > 0 && edit_len > 0 {
          if edit_vec[0] != equality2_vec[0] {
            break;
          }
          let ch = edit_vec[0];
          equality1_vec.push(ch);
          edit_vec.push(ch);
          edit_vec = edit_vec[1..].to_vec();
          equality2_len -= 1;
          equality2_vec = equality2_vec[1..].to_vec();
          score = self.diff_cleanup_semantic_score(&equality1_vec, &edit_vec)
            + self.diff_cleanup_semantic_score(&edit_vec, &equality2_vec);
          // The >= encourages trailing rather than leading whitespace on edits.
          if score >= best_score {
            best_score = score;
            best_equality1 = equality1_vec[0..].iter().collect();
            best_edit = edit_vec[..].iter().collect();
            best_equality2 = equality2_vec[..].iter().collect();
          }
        }
        if diffs[pointer as usize - 1].text != best_equality1 {
          // We have an improvement, save it back to the diff.
          if !best_equality1.is_empty() {
            diffs[pointer as usize - 1] =
              Diff::new(diffs[pointer as usize - 1].operation, best_equality1);
          } else {
            diffs.remove(pointer as usize - 1);
            pointer -= 1;
          }
          diffs[pointer as usize] =
            Diff::new(diffs[pointer as usize].operation, best_edit);
          if !best_equality2.is_empty() {
            diffs[pointer as usize + 1] =
              Diff::new(diffs[pointer as usize + 1].operation, best_equality2);
          } else {
            diffs.remove(pointer as usize + 1);
            pointer += 1;
          }
        }
      }
      pointer += 1;
    }
  }

  /// Given two strings, compute a score representing whether the
  /// internal boundary falls on logical boundaries.
  /// Scores range from 6 (best) to 0 (worst).
  /// Closure, but does not reference any external variables.
  ///
  /// # Args
  /// - one: First chars.
  /// - two: Second chars.
  ///
  /// # Return
  /// The score.
  fn diff_cleanup_semantic_score(&self, one: &[char], two: &[char]) -> i32 {
    if one.is_empty() || two.is_empty() {
      // Edges are the best.
      return 6;
    }

    // Each port of this function behaves slightly differently due to
    // subtle differences in each language's definition of things like
    // 'whitespace'.  Since this function's purpose is largely cosmetic,
    // the choice has been made to use each language's native features
    // rather than force total conformity.
    let char1 = one[one.len() - 1];
    let char2 = two[0];
    let nonalphanumeric1: bool = !char1.is_alphanumeric();
    let nonalphanumeric2: bool = !char2.is_alphanumeric();
    let whitespace1: bool = nonalphanumeric1 & char1.is_whitespace();
    let whitespace2: bool = nonalphanumeric2 & char2.is_whitespace();
    let linebreak1: bool = whitespace1 & ((char1 == '\r') | (char1 == '\n'));
    let linebreak2: bool = whitespace2 & ((char2 == '\r') | (char2 == '\n'));
    let mut test1: bool = false;
    let mut test2: bool = false;
    if one.len() > 1 && one[one.len() - 1] == '\n' && one[one.len() - 2] == '\n' {
      test1 = true;
    }
    if one.len() > 2
      && one[one.len() - 1] == '\n'
      && one[one.len() - 3] == '\n'
      && one[one.len() - 2] == '\r'
    {
      test1 = true;
    }
    if two.len() > 1 && two[two.len() - 1] == '\n' && two[two.len() - 2] == '\n' {
      test2 = true;
    }
    if two.len() > 2
      && two[two.len() - 1] == '\n'
      && two[two.len() - 3] == '\n'
      && two[two.len() - 2] == '\r'
    {
      test2 = true;
    }
    let blankline1: bool = linebreak1 & test1;
    let blankline2: bool = linebreak2 & test2;
    if blankline1 || blankline2 {
      // Five points for blank lines.
      return 5;
    }
    if linebreak1 || linebreak2 {
      // Four points for line breaks.
      return 4;
    }
    if nonalphanumeric1 && !whitespace1 && whitespace2 {
      // Three points for end of sentences.
      return 3;
    }
    if whitespace1 || whitespace2 {
      // Two points for whitespace.
      return 2;
    }
    if nonalphanumeric1 || nonalphanumeric2 {
      // One point for non-alphanumeric.
      return 1;
    }
    0
  }

  /// Reduce the number of edits by eliminating operationally trivial
  /// equalities.
  ///
  /// # Args
  /// - diffs: Vector of diff object.
  pub fn diff_cleanup_efficiency(&self, diffs: &mut Vec<Diff>) {
    if diffs.is_empty() {
      return;
    }
    let mut changes: bool = false;
    let mut equalities: Vec<i32> = vec![]; //Stack of indices where equalities are found.
    let mut last_equality: String = "".to_string(); // Always equal to diffs[equalities[-1]][1]
    let mut pointer: i32 = 0; // Index of current position.
    let mut pre_ins = false; // Is there an insertion operation before the last equality.
    let mut pre_del = false; // Is there a deletion operation before the last equality.
    let mut post_ins = false; // Is there an insertion operation after the last equality.
    let mut post_del = false; // Is there a deletion operation after the last equality.
    while (pointer as usize) < diffs.len() {
      if diffs[pointer as usize].operation == 0 {
        if diffs[pointer as usize].text.chars().count() < self.edit_cost as usize
          && (post_del || post_ins)
        {
          // Candidate found.
          equalities.push(pointer);
          pre_ins = post_ins;
          pre_del = post_del;
          last_equality = diffs[pointer as usize].text.clone();
        } else {
          // Not a candidate, and can never become one.
          equalities = vec![];
          last_equality = "".to_string();
        }
        post_ins = false;
        post_del = false;
      } else {
        // An insertion or deletion.
        if diffs[pointer as usize].operation == -1 {
          post_del = true;
        } else {
          post_ins = true;
        }

        /*
        Five types to be split:
        <ins>A</ins><del>B</del>XY<ins>C</ins><del>D</del>
        <ins>A</ins>X<ins>C</ins><del>D</del>
        <ins>A</ins><del>B</del>X<ins>C</ins>
        <ins>A</del>X<ins>C</ins><del>D</del>
        <ins>A</ins><del>B</del>X<del>C</del>
        */

        if !last_equality.is_empty()
          && ((pre_ins && pre_del && post_del && post_ins)
            || ((last_equality.chars().count() as i32) < self.edit_cost / 2
              && (pre_ins as i32
                + pre_del as i32 + post_del as i32
                + post_ins as i32) == 3))
        {
          // Duplicate record.
          diffs.insert(
            equalities[equalities.len() - 1] as usize,
            Diff::new(-1, last_equality),
          );
          // Change second copy to insert.
          diffs[equalities[equalities.len() - 1] as usize + 1] = Diff::new(
            1,
            diffs[equalities[equalities.len() - 1] as usize + 1].text.clone(),
          );
          equalities.pop(); // Throw away the equality we just deleted.
          last_equality = "".to_string();
          if pre_ins && pre_del {
            // No changes made which could affect previous entry, keep going.
            post_del = true;
            post_ins = true;
            equalities = vec![];
          } else {
            if !equalities.is_empty() {
              equalities.pop(); // Throw away the previous equality.
            }
            if !equalities.is_empty() {
              pointer = equalities[equalities.len() - 1];
            } else {
              pointer = -1;
            }
            post_ins = false;
            post_del = false;
          }
          changes = true;
        }
      }
      pointer += 1;
    }
    if changes {
      self.diff_cleanup_merge(diffs);
    }
  }

  /// Reorder and merge like edit sections. Merge equalities.
  /// Any edit section can move as long as it doesn't cross an equality.
  ///
  /// # Args
  /// - diffs: vectors of diff object.
  pub fn diff_cleanup_merge(&self, diffs: &mut Vec<Diff>) {
    if diffs.is_empty() {
      return;
    }
    diffs.push(Diff::new(0, "".to_string()));
    let mut text_insert: String = "".to_string();
    let mut text_delete: String = "".to_string();
    let mut i: i32 = 0;
    let mut count_insert = 0;
    let mut count_delete = 0;
    while (i as usize) < diffs.len() {
      if diffs[i as usize].operation == -1 {
        text_delete += diffs[i as usize].text.as_str();
        count_delete += 1;
        i += 1;
      } else if diffs[i as usize].operation == 1 {
        text_insert += diffs[i as usize].text.as_str();
        count_insert += 1;
        i += 1;
      } else {
        // Upon reaching an equality, check for prior redundancies.
        if count_delete + count_insert > 1 {
          let mut delete_vec: Vec<char> = text_delete.chars().collect();
          let mut insert_vec: Vec<char> = text_insert.chars().collect();
          if count_delete > 0 && count_insert > 0 {
            // Factor out any common prefixies.
            let mut commonlength = self.diff_common_prefix(&insert_vec, &delete_vec);
            if commonlength != 0 {
              let temp1: String =
                (&insert_vec)[..(commonlength as usize)].iter().collect();
              let x = i - count_delete - count_insert - 1;
              if x >= 0 && diffs[x as usize].operation == 0 {
                diffs[x as usize] = Diff::new(
                  diffs[x as usize].operation,
                  diffs[x as usize].text.clone() + temp1.as_str(),
                );
              } else {
                diffs.insert(0, Diff::new(0, temp1));
                i += 1;
              }
              insert_vec = insert_vec[(commonlength as usize)..].to_vec();
              delete_vec = delete_vec[(commonlength as usize)..].to_vec();
            }

            // Factor out any common suffixies.
            commonlength = self.diff_common_suffix(&insert_vec, &delete_vec);
            if commonlength != 0 {
              let temp1: String = (&insert_vec)
                [(insert_vec.len() - commonlength as usize)..]
                .iter()
                .collect();
              diffs[i as usize] = Diff::new(
                diffs[i as usize].operation,
                temp1 + diffs[i as usize].text.as_str(),
              );
              insert_vec =
                insert_vec[..(insert_vec.len() - commonlength as usize)].to_vec();
              delete_vec =
                delete_vec[..(delete_vec.len() - commonlength as usize)].to_vec();
            }
          }

          // Delete the offending records and add the merged ones.
          i -= count_delete + count_insert;
          for _j in 0..(count_delete + count_insert) as usize {
            diffs.remove(i as usize);
          }
          if !delete_vec.is_empty() {
            diffs.insert(i as usize, Diff::new(-1, delete_vec.iter().collect()));
            i += 1;
          }
          if !insert_vec.is_empty() {
            diffs.insert(i as usize, Diff::new(1, insert_vec.iter().collect()));
            i += 1;
          }
          i += 1;
        } else if i != 0 && diffs[i as usize - 1].operation == 0 {
          // Merge this equality with the previous one.
          diffs[i as usize - 1] = Diff::new(
            diffs[i as usize - 1].operation,
            diffs[i as usize - 1].text.clone() + diffs[i as usize].text.as_str(),
          );
          diffs.remove(i as usize);
        } else {
          i += 1;
        }
        count_delete = 0;
        text_delete = "".to_string();
        text_insert = "".to_string();
        count_insert = 0;
      }
    }
    // Remove the dummy entry at the end.
    if diffs[diffs.len() - 1].text.is_empty() {
      diffs.pop();
    }

    /*
    Second pass: look for single edits surrounded on both sides by equalities
    which can be shifted sideways to eliminate an equality.
    e.g: A<ins>BA</ins>C -> <ins>AB</ins>AC
    */
    let mut changes = false;
    i = 1;
    // Intentionally ignore the first and last element (don't need checking).
    while (i as usize) < diffs.len() - 1 {
      if diffs[i as usize - 1].operation == 0 && diffs[i as usize + 1].operation == 0 {
        // This is a single edit surrounded by equalities.
        let text_vec: Vec<char> = diffs[i as usize].text.chars().collect();
        let text1_vec: Vec<char> = diffs[i as usize - 1].text.chars().collect();
        let text2_vec: Vec<char> = diffs[i as usize + 1].text.chars().collect();
        if self.endswith(&text_vec, &text1_vec) {
          // Shift the edit over the previous equality.
          if !diffs[i as usize - 1].text.is_empty() {
            let temp1: String = diffs[i as usize - 1].text.clone();
            let temp2: String =
              text_vec[..(text_vec.len() - text1_vec.len())].iter().collect();
            diffs[i as usize].text = temp1 + temp2.as_str();
            diffs[i as usize + 1].text = diffs[i as usize - 1].text.clone()
              + diffs[i as usize + 1].text.as_str();
          }
          diffs.remove(i as usize - 1);
          changes = true;
        } else if self.startswith(&text_vec, &text2_vec) {
          // Shift the edit over the next equality.
          diffs[i as usize - 1].text =
            diffs[i as usize - 1].text.clone() + diffs[i as usize + 1].text.as_str();
          let temp1: String = text_vec[text2_vec.len()..].iter().collect();
          diffs[i as usize].text = temp1 + diffs[i as usize + 1].text.as_str();
          diffs.remove(i as usize + 1);
          changes = true;
        }
      }
      i += 1;
    }
    // If shifts were made, the diff needs reordering and another shift sweep.
    if changes {
      self.diff_cleanup_merge(diffs);
    }
  }

  /// It will check if first chars vector is endswith second chars vector or not.
  ///
  /// # Args
  /// - first: First chars,
  /// - second: Second chars.
  ///
  /// # Return
  /// Return true if first chars vector endswith second chars vector, false otherwise.
  fn endswith(&self, first: &[char], second: &[char]) -> bool {
    let mut len1 = first.len();
    let mut len2 = second.len();
    if len1 < len2 {
      return false;
    }
    while len2 > 0 {
      if first[len1 - 1] != second[len2 - 1] {
        return false;
      }
      len1 -= 1;
      len2 -= 1;
    }
    true
  }

  /// It will check if first chars vector is startswith second chars vector or not.
  ///
  /// # Args:
  /// - first: First chars,
  /// - second: Secodn chars.
  ///
  /// # Return
  /// Return true if first chars vector startswith second chars vector, false otherwise.
  fn startswith(&self, first: &[char], second: &[char]) -> bool {
    let len1 = first.len();
    let len2 = second.len();
    if len1 < len2 {
      return false;
    }
    for i in 0..len2 {
      if first[i] != second[i] {
        return false;
      }
    }
    true
  }

  /// loc is a location in text1, compute and return the equivalent location
  /// in text2.  e.g. "The cat" vs "The big cat", 1->1, 5->8
  ///
  /// # Args
  /// - diffs: Vector of diff object.
  /// - loc: Location within text1.
  ///
  /// # Return
  /// Location within text2.
  fn diff_xindex(&self, diffs: &Vec<Diff>, loc: i32) -> i32 {
    let mut chars1 = 0;
    let mut chars2 = 0;
    let mut last_chars1 = 0;
    let mut last_chars2 = 0;
    let mut lastdiff = Diff::new(0, "".to_string());
    let z = 0;
    for diffs_item in diffs {
      if diffs_item.operation != 1 {
        // Equality or deletion.
        chars1 += diffs_item.text.chars().count() as i32;
      }
      if diffs_item.operation != -1 {
        // Equality or insertion.
        chars2 += diffs_item.text.chars().count() as i32;
      }
      if chars1 > loc {
        // Overshot the location.
        lastdiff = Diff::new(diffs_item.operation, diffs_item.text.clone());
        break;
      }
      last_chars1 = chars1;
      last_chars2 = chars2;
    }
    if lastdiff.operation == -1 && diffs.len() != z {
      // The location was deleted.
      return last_chars2;
    }
    // Add the remaining len(character).
    last_chars2 + (loc - last_chars1)
  }

  /// Compute and return the source text (all equalities and deletions).
  ///
  /// # Args
  /// - diffs: Vector of diff object.
  ///
  /// # Return
  /// Source text.
  pub fn diff_text1(&self, diffs: &Vec<Diff>) -> String {
    let mut text: String = "".to_string();
    for adiff in diffs {
      if adiff.operation != 1 {
        text += adiff.text.as_str();
      }
    }
    text
  }

  /// Compute and return the destination text (all equalities and insertions).
  ///
  /// # Args
  /// - diffs: Vector of diff object.
  ///
  /// # Return
  /// Destination text.
  pub fn diff_text2(&self, diffs: &mut Vec<Diff>) -> String {
    let mut text: String = "".to_string();
    for adiff in diffs {
      if adiff.operation != -1 {
        text += adiff.text.as_str();
      }
    }
    text
  }

  /// Compute the Levenshtein distance; the number of inserted, deleted or
  /// substituted characters.
  ///
  /// # Args
  /// - diffs: Vector of diff object.
  ///
  /// # Return
  /// Number of changes.
  pub fn diff_levenshtein(&self, diffs: &Vec<Diff>) -> i32 {
    let mut levenshtein = 0;
    let mut insertions = 0;
    let mut deletions = 0;
    for adiff in diffs {
      if adiff.operation == 1 {
        insertions += adiff.text.chars().count();
      } else if adiff.operation == -1 {
        deletions += adiff.text.chars().count();
      } else {
        // A deletion and an insertion is one substitution.
        levenshtein += max(insertions as i32, deletions as i32);
        insertions = 0;
        deletions = 0;
      }
    }
    levenshtein += max(insertions as i32, deletions as i32);
    levenshtein
  }

  //fn diff_todelta(&self, diffs: &mut Vec<Diff>) -> String {
  //    self.diff_todelta_unit(diffs, LengthUnit::UnicodeScalar)
  //}

  /*
  /// Crush the diff into an encoded string which describes the operations
  /// required to transform text1 into text2.
  /// E.g. =3\t-2\t+ing  -> Keep 3 chars, delete 2 chars, insert 'ing'.
  /// Operations are tab-separated.  Inserted text is escaped using %xx notation.
  ///
  /// # Args
  /// - diffs: Vector of diff object.
  /// - length_unit: Unit of length.
  ///     For example diff from "🅰🅱" -> "🅱" can have different delta:
  ///      * When operating on unicode scalars delta will be "-1\t=1"
  ///      * For UTF-16 delta will be "-2\t=2"
  ///
  /// # Return
  /// Delta text.
  fn diff_todelta_unit(&self, diffs: &mut Vec<Diff>, length_unit: LengthUnit) -> String {
    let mut text: String = "".to_string();
    let len = diffs.len();
    for (k, diffs_item) in diffs.iter().enumerate() {
      if diffs_item.operation == 1 {
        // High ascii will raise UnicodeDecodeError.  Use Unicode instead.
        let temp5: Vec<char> = vec![
          '!', '~', '*', '(', ')', ';', '/', '?', ':', '@', '&', '=', '+', '$', ',', '#',
          ' ', '\'',
        ];
        let temp4: Vec<char> = diffs_item.text.chars().collect();
        text += "+";
        for temp4_item in &temp4 {
          let mut is = false;
          for temp5_item in &temp5 {
            if *temp5_item == *temp4_item {
              text.push(*temp4_item);
              is = true;
              break;
            }
          }
          if is {
            continue;
          }
          let mut temp6 = "".to_string();
          temp6.push(*temp4_item);
          temp6 = encode(temp6.as_str()).into_owned();
          text += temp6.as_str();
        }
      } else {
        if diffs_item.operation == -1 {
          text += "-";
        } else {
          text += "=";
        }

        let count: usize;
        match length_unit {
          LengthUnit::UnicodeScalar => {
            count = diffs_item.text.chars().count();
          }
          LengthUnit::UTF16 => {
            count = diffs_item.text.encode_utf16().count();
          }
        }
        text += count.to_string().as_str();
      }

      if k < len - 1 {
        text += "\t";
      }
    }
    text
  }
  */

  /// Locate the best instance of 'pattern' in 'text' near 'loc'.
  ///
  /// # Args
  /// - text: The text to search.
  /// - pattern: The pattern to search for.
  /// - loc: The location to search around.
  ///
  /// # Return
  /// Best match index or -1.
  pub fn match_main(&self, text1: &str, patern1: &str, mut loc: i32) -> Result<i32, Error> {
    loc = max(0, min(loc, text1.len() as i32));
    if patern1.is_empty() {
      return Ok(loc);
    }
    if text1.is_empty() {
      return Ok(-1);
    }
    let text: Vec<char> = (text1.to_string()).chars().collect();
    let patern: Vec<char> = (patern1.to_string()).chars().collect();
    if text == patern {
      // Shortcut (potentially not guaranteed by the algorithm)
      return Ok(0);
    } else if loc as usize + patern.len() <= text.len()
      && text[(loc as usize)..(loc as usize + patern.len())].to_vec() == patern
    {
      // Perfect match at the perfect spot!  (Includes case of null pattern)
      return Ok(loc);
    }
    self.match_bitap(&text, &patern, loc)
  }

  /// Locate the best instance of 'pattern' in 'text' near 'loc' using the
  /// Bitap algorithm.
  ///
  /// # Args:
  /// - text: The text to search.
  /// - pattern: The pattern to search for.
  /// - loc: The location to search around.
  ///
  /// # Return
  /// Best match index or -1.
  fn match_bitap(&self, text: &[char], patern: &[char], loc: i32) -> Result<i32, Error> {
    // check for maxbits limit.
    if !(self.match_maxbits == 0 || patern.len() as i32 <= self.match_maxbits) {
      return Err(Error::PatternTooLong);
    }
    // Initialise the alphabet.
    let s: HashMap<char, i32> = self.match_alphabet(patern);

    // Highest score beyond which we give up.
    let mut score_threshold: f32 = self.match_threshold;
    // Is there a nearby exact match? (speedup)
    let mut best_loc = self.kmp(text, patern, loc as usize);
    if best_loc != -1 {
      score_threshold =
        min1(self.match_bitap_score(0, best_loc, loc, patern), score_threshold);
      // What about in the other direction? (speedup)
      best_loc = self.rkmp(text, patern, loc as usize + patern.len());
      if best_loc != -1 {
        score_threshold =
          min1(score_threshold, self.match_bitap_score(0, best_loc, loc, patern));
      }
    }
    // Initialise the bit arrays.
    let matchmask = 1 << (patern.len() - 1); //>
    best_loc = -1;
    let mut bin_min: i32;
    let mut bin_mid: i32;
    let mut bin_max: i32 = (patern.len() + text.len()) as i32;
    // Empty initialization added to appease pychecker.
    let mut last_rd: Vec<i32> = vec![];
    for d in 0..patern.len() {
      /*
      Scan for the best match each iteration allows for one more error.
      Run a binary search to determine how far from 'loc' we can stray at
      this error level.
      */
      let mut rd: Vec<i32> = vec![];
      bin_min = 0;
      bin_mid = bin_max;
      // Use the result from this iteration as the maximum for the next.
      while bin_min < bin_mid {
        if self.match_bitap_score(d as i32, loc + bin_mid, loc, patern) <= score_threshold {
          bin_min = bin_mid;
        } else {
          bin_max = bin_mid;
        }
        bin_mid = bin_min + (bin_max - bin_min) / 2;
      }
      bin_max = bin_mid;
      let mut start = max(1, loc - bin_mid + 1);
      let finish = min(loc + bin_mid, text.len() as i32) + patern.len() as i32;
      rd.resize((finish + 2) as usize, 0);
      rd[(finish + 1) as usize] = (1 << d) - 1; //>
      let mut j = finish;
      while j >= start {
        let char_match: i32;
        if text.len() < j as usize {
          // Out of range.
          char_match = 0;
        } else {
          // Subsequent passes: fuzzy match.
          match s.get(&(text[j as usize - 1])) {
            Some(num) => {
              char_match = *num;
            }
            None => {
              char_match = 0;
            }
          }
        }
        if d == 0 {
          // First pass: exact match.
          rd[j as usize] = ((rd[j as usize + 1] << 1) | 1) & char_match;
        //>>
        } else {
          rd[j as usize] = (((rd[j as usize + 1] << 1) | 1) & char_match)
            | (((last_rd[j as usize + 1] | last_rd[j as usize]) << 1) | 1)
            | last_rd[j as usize + 1]; //>>>>
        }
        if (rd[j as usize] & matchmask) != 0 {
          let score: f32 = self.match_bitap_score(d as i32, j - 1, loc, patern);
          // This match will almost certainly be better than any existing match.
          // But check anyway.
          if score <= score_threshold {
            // Told you so.
            score_threshold = score;
            best_loc = j - 1;
            if best_loc > loc {
              // When passing loc, don't exceed our current distance from loc.
              start = max(1, 2 * loc - best_loc);
            } else {
              // Already passed loc, downhill from here on in.
              break;
            }
          }
        }
        j -= 1;
      }
      // No hope for a (better) match at greater error levels.
      if self.match_bitap_score(d as i32 + 1, loc, loc, patern) > score_threshold {
        break;
      }
      last_rd = rd;
    }
    Ok(best_loc)
  }

  /// Compute and return the score for a match with e errors and x location.
  /// Accesses loc and pattern through being a closure.
  ///
  /// # Args
  /// - e: Number of errors in match.
  /// - x: Location of match.
  ///
  /// # Return
  /// Overall score for match (0.0 = good, 1.0 = bad).
  fn match_bitap_score(&self, e: i32, x: i32, loc: i32, pattern: &[char]) -> f32 {
    let accuracy: f32 = (e as f32) / (pattern.len() as f32);
    let proximity: i32 = (loc - x).abs();
    if self.match_distance == 0 {
      // Dodge divide by zero error.
      if proximity == 0 {
        return accuracy;
      } else {
        return 1.0;
      }
    }
    accuracy + ((proximity as f32) / (self.match_distance as f32))
  }

  /// Initialise the alphabet for the Bitap algorithm.
  ///
  /// # Args:
  /// - pattern: The text to encode.
  ///
  /// # Return
  /// Hash of character locations.
  fn match_alphabet(&self, pattern: &[char]) -> HashMap<char, i32> {
    let mut s: HashMap<char, i32> = HashMap::new();
    for patern_item in pattern {
      s.insert(*patern_item, 0);
    }
    for i in 0..pattern.len() {
      let ch: char = pattern[i];
      let mut temp: i32 = 0;
      if let Some(num) = s.get(&ch) {
        temp = num | (1 << (pattern.len() - i - 1)); //>>
      }
      s.insert(ch, temp);
    }
    s
  }

  /// Increase the context until it is unique,
  /// but don't let the pattern expand beyond Match_MaxBits.
  ///
  /// Args:
  /// - patch: The patch to grow.
  /// - text: Source text.
  fn patch_add_context(&self, patch: &mut Patch, text: &mut [char]) {
    if text.is_empty() {
      return;
    }
    let mut pattern: Vec<char> =
      text[patch.start2 as usize..(patch.length1 as usize + patch.start2 as usize)].to_vec();
    let mut padding: i32 = 0;

    // Look for the first and last matches of pattern in text.  If two different
    // matches are found, increase the pattern length.
    let mut rst = 0;
    while self.kmp(text, &pattern, 0) != self.rkmp(text, &pattern, text.len() - 1)
      && (pattern.len() as i32) < (self.match_maxbits - self.patch_margin * 2)
    {
      padding += self.patch_margin;
      pattern = text[max(0, patch.start2 - padding) as usize
        ..min(text.len() as i32, patch.start2 + patch.length1 + padding) as usize]
        .to_vec();
      rst += 1;
      if rst > 5 {
        break;
      }
    }
    // Add one chunk for good luck.
    padding += self.patch_margin;

    // Add the prefix.
    let prefix: String =
      text[max(0, patch.start2 - padding) as usize..patch.start2 as usize].iter().collect();
    let prefix_length = prefix.chars().count() as i32;
    if !prefix.is_empty() {
      patch.diffs.insert(0, Diff::new(0, prefix.clone()));
    }

    // Add the suffix.
    let suffix: String = text[(patch.start2 + patch.length1) as usize
      ..min(text.len() as i32, patch.start2 + patch.length1 + padding) as usize]
      .iter()
      .collect();
    let suffix_length = suffix.chars().count() as i32;
    if !suffix.is_empty() {
      patch.diffs.push(Diff::new(0, suffix));
    }
    // Roll back the start points.
    patch.start1 -= prefix_length;
    patch.start2 -= prefix_length;
    // Extend lengths.
    patch.length1 += prefix_length + suffix_length;
    patch.length2 += prefix_length + suffix_length;
  }

  /// Compute a list of patches to turn text1 into text2.
  /// compute diffs.
  ///
  /// # Args
  /// - text1: First string.
  /// - text2: Second string.
  ///
  /// # Return
  /// Vector of Patch objects.
  pub fn patch_make1(&self, text1: &str, text2: &str) -> Vec<Patch> {
    let mut diffs: Vec<Diff> = self.diff_main(text1, text2, true);
    if diffs.len() > 2 {
      self.diff_cleanup_semantic(&mut diffs);
      self.diff_cleanup_efficiency(&mut diffs);
    }
    self.patch_make4(text1, &diffs)
  }

  /// Compute a list of patches to turn text1 into text2.
  /// Use diffs to compute first text.
  ///
  /// # Args
  /// - diffs: Vector of diff object.
  ///
  /// # Return
  /// Vector of Patch objects.
  pub fn patch_make2(&self, diffs: &Vec<Diff>) -> Vec<Patch> {
    let text1 = self.diff_text1(diffs);
    self.patch_make4(text1.as_str(), diffs)
  }

  /// Compute a list of patches to turn text1 into text2.
  ///
  /// # Args
  /// - text1: First string.
  /// - text2: Second string.
  /// - diffs: Vector of diff.
  ///
  /// # Return
  /// Vector of Patch objects.
  pub fn patch_make3(&self, text1: &str, _text2: &str, diffs: &[Diff]) -> Vec<Patch> {
    self.patch_make4(text1, diffs)
  }

  /// Compute a list of patches to turn text1 into text2.
  ///
  /// # Args
  /// - text1: First string.
  /// - diffs: Vector of diff object.
  ///
  /// # Return
  /// Array of Patch objects.
  pub fn patch_make4(&self, text1: &str, diffs: &[Diff]) -> Vec<Patch> {
    let mut patches: Vec<Patch> = vec![];
    if diffs.is_empty() {
      return patches; // Get rid of the None case.
    }
    let mut patch: Patch = Patch::new(vec![], 0, 0, 0, 0);
    let mut char_count1 = 0; // Number of characters into the text1 string.
    let mut char_count2 = 0; // Number of characters into the text2 string.
    let mut prepatch: Vec<char> = (text1.to_string()).chars().collect(); // Recreate the patches to determine context info.
    let mut postpatch: Vec<char> = (text1.to_string()).chars().collect();
    for i in 0..diffs.len() {
      let temp1: &Vec<char> = &(diffs[i].text.chars().collect());
      if patch.diffs.is_empty() && diffs[i].operation != 0 {
        // A new patch starts here.
        patch.start1 = char_count1;
        patch.start2 = char_count2;
      }
      if diffs[i].operation == 1 {
        // Insertion
        patch.diffs.push(Diff::new(diffs[i].operation, diffs[i].text.clone()));
        let temp: Vec<char> = postpatch[char_count2 as usize..].to_vec();
        postpatch = postpatch[..char_count2 as usize].to_vec();
        patch.length2 += temp1.len() as i32;
        for ch in temp1 {
          postpatch.push(*ch);
        }
        for ch in temp {
          postpatch.push(ch);
        }
      } else if diffs[i].operation == -1 {
        // Deletion.
        patch.diffs.push(Diff::new(diffs[i].operation, diffs[i].text.clone()));
        let temp: Vec<char> = postpatch[(temp1.len() + char_count2 as usize)..].to_vec();
        postpatch = postpatch[..char_count2 as usize].to_vec();
        patch.length1 += temp1.len() as i32;
        for ch in &temp {
          postpatch.push(*ch);
        }
      } else {
        if temp1.len() as i32 <= self.patch_margin * 2
          && !patch.diffs.is_empty()
          && i != diffs.len() - 1
        {
          // Small equality inside a patch.
          patch.diffs.push(Diff::new(diffs[i].operation, diffs[i].text.clone()));
          patch.length1 += temp1.len() as i32;
          patch.length2 += temp1.len() as i32;
        }

        // Time for a new patch.
        if temp1.len() as i32 >= 2 * self.patch_margin && !patch.diffs.is_empty() {
          self.patch_add_context(&mut patch, &mut prepatch);
          patches.push(patch);
          patch = Patch::new(vec![], 0, 0, 0, 0);
          prepatch = postpatch.clone();
          char_count1 = char_count2;
        }
      }

      // Update the current character count.
      if diffs[i].operation != 1 {
        char_count1 += temp1.len() as i32;
      }
      if diffs[i].operation != -1 {
        char_count2 += temp1.len() as i32;
      }
    }

    // Pick up the leftover patch if not empty.
    if !patch.diffs.is_empty() {
      self.patch_add_context(&mut patch, &mut prepatch);
      // println!("{:?}", prepatch);
      patches.push(patch);
    }
    patches
  }

  /// Given an Vector of patches, return another Vector that is identical.
  ///
  /// Args:
  /// - patches: Vector of Patch objects.
  ///
  /// Returns:
  /// Vector of Patch objects.
  fn patch_deep_copy(&self, patches: &[Patch]) -> Vec<Patch> {
    patches.to_vec()
  }

  /// Merge a set of patches onto the text.  Return a patched text, as well
  /// as a list of true/false values indicating which patches were applied.
  ///
  /// # Args
  /// - patches: Vector of Patch objects.
  /// - text: Old text.
  ///
  /// # Return
  /// Two element Vector, containing the new chars and an Vector of boolean values.
  pub fn patch_apply(
    &self,
    patches: &[Patch],
    source_text: &str,
  ) -> Result<(Vec<char>, Vec<bool>), Error> {
    if patches.is_empty() {
      return Ok((source_text.chars().collect(), vec![]));
    }

    // Deep copy the patches so that no changes are made to originals.
    let mut patches_copy: Vec<Patch> = self.patch_deep_copy(patches);

    let null_padding: Vec<char> = self.patch_add_padding(&mut patches_copy)?;

    let mut text = null_padding.clone();
    text.extend(source_text.chars());
    text.extend(&null_padding);

    self.patch_splitmax(&mut patches_copy);

    // delta keeps track of the offset between the expected and actual location
    // of the previous patch.  If there are patches expected at positions 10 and
    // 20, but the first patch was found at 12, delta is 2 and the second patch
    // has an effective expected position of 22.
    let mut delta: i32 = 0;
    let mut results: Vec<bool> = vec![false; patches_copy.len()];
    for x in 0..patches_copy.len() {
      let expected_loc: i32 = patches_copy[x].start2 + delta;
      let text1: Vec<char> = self.diff_text1(&patches_copy[x].diffs).chars().collect();
      let mut start_loc: i32;
      let mut end_loc = -1;
      if text1.len() as i32 > self.match_maxbits {
        // patch_splitMax will only provide an oversized pattern in the case of
        // a monster delete.
        let first: String = (text[..]).iter().collect();
        let second: String = text1[..self.match_maxbits as usize].iter().collect();
        let second1: String =
          text1[text1.len() - self.match_maxbits as usize..].iter().collect();
        start_loc = self.match_main(first.as_str(), second.as_str(), expected_loc)?;
        if start_loc != -1 {
          end_loc = self.match_main(
            first.as_str(),
            second1.as_str(),
            expected_loc + text1.len() as i32 - self.match_maxbits,
          )?;
          if end_loc == -1 || start_loc >= end_loc {
            // Can't find valid trailing context.  Drop this patch.
            start_loc = -1;
          }
        }
      } else {
        let first: String = text[..].iter().collect();
        let second: String = text1[..].iter().collect();
        start_loc = self.match_main(first.as_str(), second.as_str(), expected_loc)?;
      }
      if start_loc == -1 {
        // No match found.  :(
        results[x] = false;
        // Subtract the delta for this failed patch from subsequent patches.
        delta -= patches_copy[x].length2 - patches_copy[x].length1;
      } else {
        // Found a match.  :)
        results[x] = true;
        delta = start_loc - expected_loc;

        let mut end_index: usize;
        if end_loc == -1 {
          end_index = start_loc as usize + text1.len();
        } else {
          end_index = (end_loc + self.match_maxbits) as usize;
        }
        end_index = std::cmp::min(text.len(), end_index);

        let text2: Vec<char> = text[start_loc as usize..end_index].to_vec();

        if text1 == text2 {
          // Perfect match, just shove the replacement text in.
          let temp3: String = text[..start_loc as usize].iter().collect();
          let temp4 = self.diff_text2(&mut patches_copy[x].diffs);
          let temp5: String = text[(start_loc as usize + text1.len())..].iter().collect();
          let temp6 = temp3 + temp4.as_str() + temp5.as_str();
          text = temp6.chars().collect();
        } else {
          // Imperfect match.
          // Run a diff to get a framework of equivalent indices.
          let temp3: String = text1[..].iter().collect();
          let temp4: String = text2[..].iter().collect();
          let mut diffs: Vec<Diff> =
            self.diff_main(temp3.as_str(), temp4.as_str(), false);
          if text1.len() as i32 > self.match_maxbits
            && (self.diff_levenshtein(&diffs) as f32 / (text1.len() as f32)
              > self.patch_delete_threshold)
          {
            // The end points match, but the content is unacceptably bad.
            results[x] = false;
          } else {
            self.diff_cleanup_semantic_lossless(&mut diffs);
            let mut index1: i32 = 0;
            for y in 0..patches_copy[x].diffs.len() {
              let mod1 = patches_copy[x].diffs[y].clone();
              if mod1.operation != 0 {
                let index2: i32 = self.diff_xindex(&diffs, index1);
                if mod1.operation == 1 {
                  // Insertion
                  let temp3: String =
                    text[..(start_loc + index2) as usize].iter().collect();
                  let temp4: String =
                    text[(start_loc + index2) as usize..].iter().collect();
                  let temp5 = temp3 + mod1.text.as_str() + temp4.as_str();
                  text = temp5.chars().collect();
                } else if mod1.operation == -1 {
                  // Deletion
                  let temp3: String =
                    text[..(start_loc + index2) as usize].iter().collect();
                  let diffs_text_len = mod1.text.chars().count();
                  let temp4: String = text
                    .get(
                      (start_loc
                        + self.diff_xindex(
                          &diffs,
                          index1 + diffs_text_len as i32,
                        )) as usize..,
                    )
                    .ok_or(Error::MalformedPatch)?
                    .iter()
                    .collect();
                  let temp5 = temp3 + temp4.as_str();
                  text = temp5.chars().collect();
                }
              }
              if mod1.operation != -1 {
                index1 += mod1.text.chars().count() as i32;
              }
            }
          }
        }
      }
    }
    // Strip the padding off.
    text = text
      .get(null_padding.len()..(text.len() - null_padding.len()))
      .ok_or(Error::MalformedPatch)?
      .to_vec();
    Ok((text, results))
  }

  /// Add some padding on text start and end so that edges can match
  /// something.  Intended to be called only from within patch_apply.
  ///
  /// # Args
  /// - patches: Array of Patch objects.
  ///
  /// # Return
  /// The padding chars added to each side.
  fn patch_add_padding(&self, patches: &mut Vec<Patch>) -> Result<Vec<char>, Error> {
    let padding_length = self.patch_margin;
    let mut nullpadding: Vec<char> = vec![];
    for i in 0..padding_length {
      if let Some(ch) = char::from_u32(1 + i as u32) {
        nullpadding.push(ch);
      }
    }

    // Bump all the patches forward.
    for p in &mut *patches {
      p.start1 += padding_length;
      p.start2 += padding_length;
    }
    let mut patch = patches[0].clone();
    let mut diffs = patch.diffs;
    if diffs.is_empty() {
      return Err(Error::InvalidInput);
    }
    let mut text_len = diffs[0].text.chars().count() as i32;
    if diffs.is_empty() || diffs[0].operation != 0 {
      // Add nullPadding equality.
      diffs.insert(0, Diff::new(0, nullpadding.clone().iter().collect()));
      patch.start1 -= padding_length; // Should be 0.
      patch.start2 -= padding_length; // Should be 0.
      patch.length1 += padding_length;
      patch.length2 += padding_length;
    } else if padding_length > text_len {
      // Grow first equality.
      let extra_length = padding_length - text_len;
      let mut new_text: String = nullpadding[text_len as usize..].iter().collect();
      new_text += diffs[0].text.as_str();
      diffs[0] = Diff::new(diffs[0].operation, new_text);
      patch.start1 -= extra_length;
      patch.start2 -= extra_length;
      patch.length1 += extra_length;
      patch.length2 += extra_length;
    }

    // Add some padding on end of last diff.
    patch.diffs = diffs;
    patches[0] = patch;
    patch = patches[patches.len() - 1].clone();
    diffs = patch.diffs;
    if diffs.is_empty() {
      return Err(Error::InvalidInput);
    }
    text_len = diffs[diffs.len() - 1].text.chars().count() as i32;
    if diffs.is_empty() || diffs[diffs.len() - 1].operation != 0 {
      // Add nullPadding equality.
      diffs.push(Diff::new(0, nullpadding.clone().iter().collect()));
      patch.length1 += padding_length;
      patch.length2 += padding_length;
    } else if padding_length > text_len {
      // Grow last equality.
      let extra_length = padding_length - text_len;
      let mut new_text: String = nullpadding[..extra_length as usize].iter().collect();
      let diffs_len = diffs.len();
      new_text = diffs[diffs_len - 1].text.clone() + new_text.as_str();
      diffs[diffs_len - 1] = Diff::new(diffs[diffs_len - 1].operation, new_text);
      patch.length1 += extra_length;
      patch.length2 += extra_length;
    }
    patch.diffs = diffs;
    let patches_len = patches.len();
    patches[patches_len - 1] = patch;
    Ok(nullpadding)
  }

  /// Look through the patches and break up any which are longer than the
  /// maximum limit of the match algorithm.
  /// Intended to be called only from within patch_apply.
  ///
  /// # Args
  /// - patches: Array of Patch objects.
  fn patch_splitmax(&self, patches: &mut Vec<Patch>) {
    let patch_size = self.match_maxbits;
    if patch_size == 0 {
      return;
    }
    let mut x: i32 = 0;
    while (x as usize) < patches.len() {
      if patches[x as usize].length1 <= patch_size {
        x += 1;
        continue;
      }
      // Remove the big old patch.
      let mut bigpatch = patches.remove(x as usize);
      x -= 1;
      let mut start1 = bigpatch.start1;
      let mut start2 = bigpatch.start2;
      let mut precontext: Vec<char> = vec![];
      while !bigpatch.diffs.is_empty() {
        // Create one of several smaller patches.
        let mut patch = Patch::new(vec![], 0, 0, 0, 0);
        let mut empty = true;
        patch.start1 = start1 - precontext.len() as i32;
        patch.start2 = start2 - precontext.len() as i32;
        if !precontext.is_empty() {
          patch.length1 = precontext.len() as i32;
          patch.length2 = precontext.len() as i32;
          patch.diffs.push(Diff::new(0, precontext.clone().iter().collect()));
        }
        while !bigpatch.diffs.is_empty() && patch.length1 < patch_size - self.patch_margin {
          let diff_type = bigpatch.diffs[0].operation;
          let mut diff_text: Vec<char> = bigpatch.diffs[0].text.chars().collect();
          if diff_type == 1 {
            // Insertions are harmless.
            patch.length2 += diff_text.len() as i32;
            start2 += diff_text.len() as i32;
            patch.diffs.push(bigpatch.diffs[0].clone());
            bigpatch.diffs.remove(0);
            empty = false;
          } else if diff_type == -1
            && patch.diffs.len() == 1
            && patch.diffs[0].operation == 0
            && (diff_text.len() as i32) > 2 * patch_size
          {
            // This is a large deletion.  Let it pass in one chunk.
            patch.length1 += diff_text.len() as i32;
            start1 += diff_text.len() as i32;
            empty = false;
            patch.diffs.push(Diff::new(diff_type, diff_text.iter().collect()));
            bigpatch.diffs.remove(0);
          } else {
            // Deletion or equality.  Only take as much as we can stomach.
            let diff_text_len: i32 = diff_text.len() as i32;
            diff_text = diff_text[..min(
              diff_text_len,
              patch_size - patch.length1 - self.patch_margin,
            ) as usize]
              .to_vec();
            patch.length1 += diff_text.len() as i32;
            start1 += diff_text.len() as i32;
            if diff_type == 0 {
              patch.length2 += diff_text.len() as i32;
              start2 += diff_text.len() as i32;
            } else {
              empty = false;
            }
            patch.diffs.push(Diff::new(diff_type, diff_text.clone().iter().collect()));
            let temp: String = diff_text[..].iter().collect();
            if temp == bigpatch.diffs[0].text.clone() {
              bigpatch.diffs.remove(0);
            } else {
              let temp1: Vec<char> = bigpatch.diffs[0].text.chars().collect();
              bigpatch.diffs[0].text = temp1[diff_text.len()..].iter().collect();
            }
          }
        }
        // Compute the head context for the next patch.
        precontext = self.diff_text2(&mut patch.diffs).chars().collect();
        precontext = precontext[(precontext.len()
          - min(self.patch_margin, precontext.len() as i32) as usize)..]
          .to_vec();
        // Append the end context for this patch.
        let postcontext = if self.diff_text1(&bigpatch.diffs).chars().count() as i32
          > self.patch_margin
        {
          let temp: Vec<char> = self.diff_text1(&bigpatch.diffs).chars().collect();
          temp[..self.patch_margin as usize].iter().collect()
        } else {
          self.diff_text1(&bigpatch.diffs)
        };
        let postcontext_len = postcontext.chars().count() as i32;
        if !postcontext.is_empty() {
          patch.length1 += postcontext_len;
          patch.length2 += postcontext_len;
          if !patch.diffs.is_empty() && patch.diffs[patch.diffs.len() - 1].operation == 0
          {
            let len = patch.diffs.len();
            patch.diffs[len - 1].text += postcontext.as_str();
          } else {
            patch.diffs.push(Diff::new(0, postcontext));
          }
        }
        if !empty {
          x += 1;
          patches.insert(x as usize, patch);
        }
      }
      x += 1;
    }
  }

  /// Take a list of patches and return a textual representation.
  ///
  /// # Args
  /// - patches: Vector of Patch objects.
  ///
  /// # Return
  /// Text representation of patches.
  pub fn patch_to_text(&self, patches: &[Patch]) -> String {
    let mut text: String = String::new();
    for patches_item in patches {
      text += (patches_item.to_string()).as_str();
    }
    text
  }

  /// Parse a textual representation of patches and return a list of patch
  /// objects.
  ///
  /// # Args
  /// - textline: Text representation of patches.
  ///
  /// # Return
  /// Vector of Patch objects or error in case of invalid input.
  pub fn patch_from_text(&self, textline: String) -> Result<Vec<Patch>, Error> {
    let text: Vec<String> = self.split_by_chars(textline.as_str());
    let mut patches: Vec<Patch> = vec![];
    for (i, text_item) in text.iter().enumerate() {
      if text_item.is_empty() {
        if i == 0 {
          continue;
        }
        return Err(Error::InvalidInput);
      }
      patches.push(self.patch1_from_text(text_item.clone())?);
    }
    Ok(patches)
  }

  pub fn patch1_from_text(&self, textline: String) -> Result<Patch, Error> {
    let text: Vec<String> = self.split_by_char(textline.as_str(), '\n');
    let mut text_vec: Vec<char> = text[0].chars().collect();
    if text_vec.len() < 8
      || text_vec[text_vec.len() - 1] != '@'
      || text_vec[text_vec.len() - 2] != '@'
    {
      return Err(Error::InvalidInput);
    }
    let mut patch = Patch::new(vec![], 0, 0, 0, 0);
    let mut i = 0;
    let mut temp: i32 = 0;
    while i < text_vec.len() {
      if text_vec[i] < '0' || text_vec[i] > '9' {
        i += 1;
        continue;
      }
      if (temp == 1 || temp == 3) && text_vec[i - 1] != ',' {
        temp += 1;
      }
      let mut s = "".to_string();
      while i < text_vec.len() && text_vec[i] >= '0' && text_vec[i] <= '9' {
        s.push(text_vec[i]);
        i += 1;
      }
      if temp == 0 {
        patch.start1 = s.parse::<i32>().map_err(|_| Error::InvalidInput)? - 1;
        temp += 1;
      } else if temp == 1 {
        patch.length1 = s.parse::<i32>().map_err(|_| Error::InvalidInput)?;
        temp += 1;
      } else if temp == 2 {
        patch.start2 = s.parse::<i32>().map_err(|_| Error::InvalidInput)? - 1;
        temp += 1;
      } else if temp == 3 {
        patch.length2 = s.parse::<i32>().map_err(|_| Error::InvalidInput)?;
        temp += 1;
      } else {
        return Err(Error::InvalidInput);
      }
      i += 1;
    }
    patch.length1 = 0;
    patch.length2 = 0;
    for text_item in text.iter().take(text.len() - 1).skip(1) {
      text_vec = text_item.chars().collect();
      match text_vec.first().ok_or(Error::InvalidInput)? {
        '+' => {
          // Insertion.
          let mut temp6: String = text_vec[1..].iter().collect();
          temp6 = decode(temp6.as_str()).map_err(|_| Error::InvalidInput)?.into_owned();
          patch.length2 += temp6.chars().count() as i32;
          patch.diffs.push(Diff::new(1, temp6));
        }
        '-' => {
          // Deletion.
          let mut temp6: String = text_vec[1..].iter().collect();
          temp6 = decode(temp6.as_str()).map_err(|_| Error::InvalidInput)?.into_owned();
          patch.length1 += temp6.chars().count() as i32;
          patch.diffs.push(Diff::new(-1, temp6));
        }
        ' ' => {
          // Minor equality.
          let mut temp6: String = text_vec[1..].iter().collect();
          temp6 = decode(temp6.as_str()).map_err(|_| Error::InvalidInput)?.into_owned();
          patch.length1 += temp6.chars().count() as i32;
          patch.length2 += temp6.chars().count() as i32;
          patch.diffs.push(Diff::new(0, temp6));
        }
        _ => {
          return Err(Error::InvalidInput);
        }
      }
    }
    Ok(patch)
  }
}

Coverage Report

Created: 2026-03-11 07:34