/*
 * Copyright 2008 Google Inc. All Rights Reserved.
 * Author: fraser@google.com (Neil Fraser)
 * Author: mikeslemmer@gmail.com (Mike Slemmer)
 * Author: snhere@gmail.com (Sergey Nozhenko)
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *
 * Diff Match and Patch
 * http://code.google.com/p/google-diff-match-patch/
 */

#ifndef DIFF_MATCH_PATCH_H
#define DIFF_MATCH_PATCH_H

#include <limits>
#include <list>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <cwchar>
#include <time.h>

#include "llvm/Support/ErrorHandling.h"

/*
 * Functions for diff, match and patch.
 * Computes the difference between two texts to create a patch.
 * Applies the patch onto another text, allowing for errors.
 *
 * @author fraser@google.com (Neil Fraser)
 *
 * Qt/C++ port by mikeslemmer@gmail.com (Mike Slemmer)
 *
 * STL-only port by snhere@gmail.com (Sergey Nozhenko)
 * and some tweaks for std::string by leutloff@sundancer.oche.de (Christian Leutloff)
 *
 * Here is a trivial sample program:
 *

 #include "diff_match_patch.h"
 #include <string>
 using namespace std;
 int main(int argc, char **argv) {
   diff_match_patch<wstring> dmp;
   wstring str1 = L"First string in diff";
   wstring str2 = L"Second string in diff";

   wstring strPatch = dmp.patch_toText(dmp.patch_make(str1, str2));
   pair<wstring, vector<bool> > out
       = dmp.patch_apply(dmp.patch_fromText(strPatch), str1);
   wstring strResult = out.first;

   // here, strResult will equal str2 above.
   return 0;
 }

 */

// Character type dependencies
template <class char_t> struct diff_match_patch_traits {};

/**
 * Class containing the diff, match and patch methods.
 * Also contains the behaviour settings.
 */
template <class stringT, class traits = diff_match_patch_traits<typename stringT::value_type> >
class diff_match_patch {
 public:
  /**
  * String and character types
  */
  typedef stringT string_t;
  typedef typename string_t::value_type char_t;

  /**-
  * The data structure representing a diff is a Linked list of Diff objects:
  * {Diff(Operation.DELETE, "Hello"), Diff(Operation.INSERT, "Goodbye"),
  *  Diff(Operation.EQUAL, " world.")}
  * which means: delete "Hello", add "Goodbye" and keep " world."
  */
  enum Operation {
    DELETE, INSERT, EQUAL
  };

  /**
  * Class representing one diff operation.
  */
  class Diff {
   public:
    Operation operation;
    // One of: INSERT, DELETE or EQUAL.

    string_t text;
    // The text associated with this diff operation.

    /**
     * Constructor.  Initializes the diff with the provided values.
     * @param _operation One of INSERT, DELETE or EQUAL.
     * @param _text The text being applied.
     */
    Diff(Operation _operation, const string_t &_text) : operation(_operation), text(_text) {}
    Diff() {}

    /**
     * Display a human-readable version of this Diff.
     * @return text version.
     */
    string_t toString() const {
      string_t prettyText = text;
      // Replace linebreaks with Pilcrow signs.
      for (typename string_t::iterator i = prettyText.begin(); i != prettyText.end(); ++i)
        if (traits::to_wchar(*i) == L'\n') *i = traits::from_wchar(L'\u00b6');
      return traits::cs(L"Diff(") + strOperation(operation) + traits::cs(L",\"") + prettyText + traits::cs(L"\")");
    }

    /**
     * Is this Diff equivalent to another Diff?
     * @param d Another Diff to compare against
     * @return true or false
     */
    bool operator==(const Diff &d) const {
      return (d.operation == this->operation) && (d.text == this->text);
    }
    bool operator!=(const Diff &d) const { return !(operator == (d)); }

    static string_t strOperation(Operation op) {
      switch (op) {
        case INSERT:
          return traits::cs(L"INSERT");
        case DELETE:
          return traits::cs(L"DELETE");
        case EQUAL:
          return traits::cs(L"EQUAL");
      }
      llvm_unreachable("Invalid operation.");
    }
  };

  typedef std::list<Diff> Diffs;


  /**
  * Class representing one patch operation.
  */
  class Patch {
   public:
    Diffs diffs;
    int start1;
    int start2;
    int length1;
    int length2;

    /**
     * Constructor.  Initializes with an empty list of diffs.
     */
    Patch() : start1(0), start2(0), length1(0), length2(0) {}

    bool isNull() const {
      return start1 == 0 && start2 == 0 && length1 == 0 && length2 == 0 && diffs.empty();
    }

    /**
     * Emulate GNU diff's format.
     * Header: @@ -382,8 +481,9 @@
     * Indices are printed as 1-based, not 0-based.
     * @return The GNU diff string
     */
    string_t toString() const {
      string_t coords1, coords2;
      if (length1 == 0) {
        coords1 = to_string(start1) + traits::cs(L",0");
      } else if (length1 == 1) {
        coords1 = to_string(start1 + 1);
      } else {
        coords1 = to_string(start1 + 1) + traits::from_wchar(L',') + to_string(length1);
      }
      if (length2 == 0) {
        coords2 = to_string(start2) + traits::cs(L",0");
      } else if (length2 == 1) {
        coords2 = to_string(start2 + 1);
      } else {
        coords2 = to_string(start2 + 1) + traits::from_wchar(L',') + to_string(length2);
      }
      string_t text(traits::cs(L"@@ -") + coords1 + traits::cs(L" +") + coords2 + traits::cs(L" @@\n"));
      // Escape the body of the patch with %xx notation.
      for (typename Diffs::const_iterator cur_diff = diffs.begin(); cur_diff != diffs.end(); ++cur_diff) {
        switch ((*cur_diff).operation) {
          case INSERT:
            text += traits::from_wchar(L'+');
            break;
          case DELETE:
            text += traits::from_wchar(L'-');
            break;
          case EQUAL:
            text += traits::from_wchar(L' ');
            break;
        }
        append_percent_encoded(text, (*cur_diff).text);
        text += traits::from_wchar(L'\n');
      }

      return text;
    }
  };

  typedef std::list<Patch> Patches;

  friend class diff_match_patch_test;

 public:
  // Defaults.
  // Set these on your diff_match_patch instance to override the defaults.

  // Number of seconds to map a diff before giving up (0 for infinity).
  float Diff_Timeout;
  // Cost of an empty edit operation in terms of edit characters.
  short Diff_EditCost;
  // At what point is no match declared (0.0 = perfection, 1.0 = very loose).
  float Match_Threshold;
  // 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).
  int Match_Distance;
  // When deleting a large block of text (over ~64 characters), how close does
  // the contents have 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.
  float Patch_DeleteThreshold;
  // Chunk size for context length.
  short Patch_Margin;

  // The number of bits in an int.
  short Match_MaxBits;


 public:

  diff_match_patch() :
    Diff_Timeout(1.0f),
    Diff_EditCost(4),
    Match_Threshold(0.5f),
    Match_Distance(1000),
    Patch_DeleteThreshold(0.5f),
    Patch_Margin(4),
    Match_MaxBits(32) {
  }

  //  DIFF FUNCTIONS

  /**
   * Find the differences between two texts.
   * @param text1 Old string to be diffed.
   * @param text2 New string to be diffed.
   * @param 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.
   *     Most of the time checklines is wanted, so default to true.
   * @return Linked List of Diff objects.
   */
  Diffs diff_main(const string_t &text1, const string_t &text2, bool checklines = true) const {
    // Set a deadline by which time the diff must be complete.
    clock_t deadline;
    if (Diff_Timeout <= 0) {
      deadline = std::numeric_limits<clock_t>::max();
    } else {
      deadline = clock() + (clock_t)(Diff_Timeout * CLOCKS_PER_SEC);
    }
    Diffs diffs;
    diff_main(text1, text2, checklines, deadline, diffs);
    return diffs;
  }

  /**
   * Find the differences between two texts.  Simplifies the problem by
   * stripping any common prefix or suffix off the texts before diffing.
   * @param text1 Old string to be diffed.
   * @param text2 New string to be diffed.
   * @param 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.
   * @param deadline Time when the diff should be complete by.  Used
   *     internally for recursive calls.  Users should set DiffTimeout instead.
   * @param diffs Linked List of Diff objects.
   */
 private:
  static void diff_main(const string_t &text1, const string_t &text2, bool checklines, clock_t deadline, Diffs& diffs) {
    diffs.clear();

    // Check for equality (speedup).
    if (text1 == text2) {
      if (!text1.empty()) {
        diffs.push_back(Diff(EQUAL, text1));
      }
    }
    else {
      // Trim off common prefix (speedup).
      int commonlength = diff_commonPrefix(text1, text2);
      const string_t &commonprefix = text1.substr(0, commonlength);
      string_t textChopped1 = text1.substr(commonlength);
      string_t textChopped2 = text2.substr(commonlength);

      // Trim off common suffix (speedup).
      commonlength = diff_commonSuffix(textChopped1, textChopped2);
      const string_t &commonsuffix = right(textChopped1, commonlength);
      textChopped1 = textChopped1.substr(0, textChopped1.length() - commonlength);
      textChopped2 = textChopped2.substr(0, textChopped2.length() - commonlength);

      // Compute the diff on the middle block.
      diff_compute(textChopped1, textChopped2, checklines, deadline, diffs);

      // Restore the prefix and suffix.
      if (!commonprefix.empty()) {
        diffs.push_front(Diff(EQUAL, commonprefix));
      }
      if (!commonsuffix.empty()) {
        diffs.push_back(Diff(EQUAL, commonsuffix));
      }

      diff_cleanupMerge(diffs);
    }
  }

  /**
   * Find the differences between two texts.  Assumes that the texts do not
   * have any common prefix or suffix.
   * @param text1 Old string to be diffed.
   * @param text2 New string to be diffed.
   * @param 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.
   * @param deadline Time when the diff should be complete by.
   * @param diffs Linked List of Diff objects.
   */
 private:
  static void diff_compute(string_t text1, string_t text2, bool checklines, clock_t deadline, Diffs& diffs) {
    if (text1.empty()) {
      // Just add some text (speedup).
      diffs.push_back(Diff(INSERT, text2));
      return;
    }

    if (text2.empty()) {
      // Just delete some text (speedup).
      diffs.push_back(Diff(DELETE, text1));
      return;
    }

    {
      const string_t& longtext = text1.length() > text2.length() ? text1 : text2;
      const string_t& shorttext = text1.length() > text2.length() ? text2 : text1;
      const size_t i = longtext.find(shorttext);
      if (i != string_t::npos) {
        // Shorter text is inside the longer text (speedup).
        const Operation op = (text1.length() > text2.length()) ? DELETE : INSERT;
        diffs.push_back(Diff(op, longtext.substr(0, i)));
        diffs.push_back(Diff(EQUAL, shorttext));
        diffs.push_back(Diff(op, safeMid(longtext, i + shorttext.length())));
        return;
      }

      if (shorttext.length() == 1) {
        // Single character string.
        // After the previous speedup, the character can't be an equality.
        diffs.push_back(Diff(DELETE, text1));
        diffs.push_back(Diff(INSERT, text2));
        return;
      }
      // Garbage collect longtext and shorttext by scoping out.
    }

    // Don't risk returning a non-optimal diff if we have unlimited time.
    if (deadline != std::numeric_limits<clock_t>::max()) {
      // Check to see if the problem can be split in two.
      HalfMatchResult hm;
      if (diff_halfMatch(text1, text2, hm)) {
        // A half-match was found, sort out the return data.
        // Send both pairs off for separate processing.
        diff_main(hm.text1_a, hm.text2_a, checklines, deadline, diffs);
        diffs.push_back(Diff(EQUAL, hm.mid_common));
        Diffs diffs_b;
        diff_main(hm.text1_b, hm.text2_b, checklines, deadline, diffs_b);
        diffs.splice(diffs.end(), diffs_b);
        return;
      }
    }

    // Perform a real diff.
    if (checklines && text1.length() > 100 && text2.length() > 100) {
      diff_lineMode(text1, text2, deadline, diffs);
      return;
    }

    diff_bisect(text1, text2, deadline, diffs);
  }

  /**
   * Do a quick line-level diff on both strings, then rediff the parts for
   * greater accuracy.
   * This speedup can produce non-minimal diffs.
   * @param text1 Old string to be diffed.
   * @param text2 New string to be diffed.
   * @param deadline Time when the diff should be complete by.
   * @param diffs Linked List of Diff objects.
   */
 private:
  static void diff_lineMode(string_t text1, string_t text2, clock_t deadline, Diffs& diffs) {
    // Scan the text on a line-by-line basis first.
    Lines linearray;
    diff_linesToChars(text1, text2, linearray);

    diff_main(text1, text2, false, deadline, diffs);

    // Convert the diff back to original text.
    diff_charsToLines(diffs, linearray);
    // Eliminate freak matches (e.g. blank lines)
    diff_cleanupSemantic(diffs);

    // Rediff any replacement blocks, this time character-by-character.
    // Add a dummy entry at the end.
    diffs.push_back(Diff(EQUAL, string_t()));
    int count_delete = 0;
    int count_insert = 0;
    string_t text_delete;
    string_t text_insert;

    for (typename Diffs::iterator cur_diff = diffs.begin(); cur_diff != diffs.end(); ++cur_diff) {
      switch ((*cur_diff).operation) {
        case INSERT:
          count_insert++;
          text_insert += (*cur_diff).text;
          break;
        case DELETE:
          count_delete++;
          text_delete += (*cur_diff).text;
          break;
        case EQUAL:
          // Upon reaching an equality, check for prior redundancies.
          if (count_delete >= 1 && count_insert >= 1) {
            // Delete the offending records and add the merged ones.
            typename Diffs::iterator last = cur_diff;
            std::advance(cur_diff, -(count_delete + count_insert));
            cur_diff = diffs.erase(cur_diff, last);

            Diffs new_diffs;
            diff_main(text_delete, text_insert, false, deadline, new_diffs);
            diffs.splice(cur_diff++, new_diffs);
            --cur_diff;
          }
          count_insert = 0;
          count_delete = 0;
          text_delete.clear();
          text_insert.clear();
          break;
      }
    }
    diffs.pop_back();  // Remove the dummy entry at the end.
  }

  /**
   * 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.
   * @param text1 Old string to be diffed.
   * @param text2 New string to be diffed.
   * @return Linked List of Diff objects.
   */
 protected:
  static Diffs diff_bisect(const string_t &text1, const string_t &text2, clock_t deadline) {
    Diffs diffs;
    diff_bisect(text1, text2, deadline, diffs);
    return diffs;
  }
 private:
  static void diff_bisect(const string_t &text1, const string_t &text2, clock_t deadline, Diffs& diffs) {
    // Cache the text lengths to prevent multiple calls.
    const int text1_length = text1.length();
    const int text2_length = text2.length();
    const int max_d = (text1_length + text2_length + 1) / 2;
    const int v_offset = max_d;
    const int v_length = 2 * max_d;
    std::vector<int> v1(v_length, -1), 
                     v2(v_length, -1);
    v1[v_offset + 1] = 0;
    v2[v_offset + 1] = 0;
    const int delta = text1_length - text2_length;
    // If the total number of characters is odd, then the front path will
    // collide with the reverse path.
    const bool front = (delta % 2 != 0);
    // Offsets for start and end of k loop.
    // Prevents mapping of space beyond the grid.
    int k1start = 0;
    int k1end = 0;
    int k2start = 0;
    int k2end = 0;
    for (int d = 0; d < max_d; d++) {
      // Bail out if deadline is reached.
      if (clock() > deadline) {
        break;
      }

      // Walk the front path one step.
      for (int k1 = -d + k1start; k1 <= d - k1end; k1 += 2) {
        const int k1_offset = v_offset + k1;
        int x1;
        if (k1 == -d || (k1 != d && v1[k1_offset - 1] < v1[k1_offset + 1])) {
          x1 = v1[k1_offset + 1];
        } else {
          x1 = v1[k1_offset - 1] + 1;
        }
        int y1 = x1 - k1;
        while (x1 < text1_length && y1 < text2_length
            && text1[x1] == text2[y1]) {
          x1++;
          y1++;
        }
        v1[k1_offset] = 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) {
          int k2_offset = v_offset + delta - k1;
          if (k2_offset >= 0 && k2_offset < v_length && v2[k2_offset] != -1) {
            // Mirror x2 onto top-left coordinate system.
            int x2 = text1_length - v2[k2_offset];
            if (x1 >= x2) {
              // Overlap detected.
              diff_bisectSplit(text1, text2, x1, y1, deadline, diffs);
              return;
            }
          }
        }
      }

      // Walk the reverse path one step.
      for (int k2 = -d + k2start; k2 <= d - k2end; k2 += 2) {
        const int k2_offset = v_offset + k2;
        int x2;
        if (k2 == -d || (k2 != d && v2[k2_offset - 1] < v2[k2_offset + 1])) {
          x2 = v2[k2_offset + 1];
        } else {
          x2 = v2[k2_offset - 1] + 1;
        }
        int y2 = x2 - k2;
        while (x2 < text1_length && y2 < text2_length
            && text1[text1_length - x2 - 1] == text2[text2_length - y2 - 1]) {
          x2++;
          y2++;
        }
        v2[k2_offset] = 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) {
          int k1_offset = v_offset + delta - k2;
          if (k1_offset >= 0 && k1_offset < v_length && v1[k1_offset] != -1) {
            int x1 = v1[k1_offset];
            int y1 = v_offset + x1 - k1_offset;
            // Mirror x2 onto top-left coordinate system.
            x2 = text1_length - x2;
            if (x1 >= x2) {
              // Overlap detected.
              diff_bisectSplit(text1, text2, x1, y1, deadline, diffs);
              return;
            }
          }
        }
      }
    }
    // Diff took too long and hit the deadline or
    // number of diffs equals number of characters, no commonality at all.
    diffs.clear();
    diffs.push_back(Diff(DELETE, text1));
    diffs.push_back(Diff(INSERT, text2));
  }

  /**
   * Given the location of the 'middle snake', split the diff in two parts
   * and recurse.
   * @param text1 Old string to be diffed.
   * @param text2 New string to be diffed.
   * @param x Index of split point in text1.
   * @param y Index of split point in text2.
   * @param deadline Time at which to bail if not yet complete.
   * @param diffs LinkedList of Diff objects.
   */
 private:
  static void diff_bisectSplit(const string_t &text1, const string_t &text2, int x, int y, clock_t deadline, Diffs& diffs) {
    string_t text1a = text1.substr(0, x);
    string_t text2a = text2.substr(0, y);
    string_t text1b = safeMid(text1, x);
    string_t text2b = safeMid(text2, y);

    // Compute both diffs serially.
    diff_main(text1a, text2a, false, deadline, diffs);
    Diffs diffs_b;
    diff_main(text1b, text2b, false, deadline, diffs_b);
    diffs.splice(diffs.end(), diffs_b);
  }

 protected:
  struct LinePtr : std::pair<typename string_t::const_pointer, size_t> {
    LinePtr() {}
    LinePtr(typename string_t::const_pointer p, size_t n) : std::pair<typename string_t::const_pointer, size_t>(p, n) {}
    bool operator<(const LinePtr& p) const
      { return this->second < p.second? true : this->second > p.second? false : string_t::traits_type::compare(this->first, p.first, this->second) < 0; }
  };
  struct Lines : std::vector<LinePtr> { string_t text1, text2; };

  /**
   * Split two texts into a list of strings.  Reduce the texts to a string of
   * hashes where each Unicode character represents one line.
   * @param text1 First string.
   * @param text2 Second string.
   * @param lineArray Lines object, containing the encoded text1, the
   *     encoded text2 and the List of pointers to unique strings.  The zeroth element
   *     of the List of unique strings is intentionally blank.
   */
  static void diff_linesToChars(string_t &text1, string_t &text2, Lines& lineArray) {
    std::map<LinePtr, size_t> lineHash;
    lineArray.text1.swap(text1), lineArray.text2.swap(text2);
    // e.g. linearray[4] == "Hello\n"
    // e.g. linehash.get("Hello\n") == 4

    // "\x00" is a valid character, but various debuggers don't like it.
    // So we'll insert a junk entry to avoid generating a null character.

    text1 = diff_linesToCharsMunge(lineArray.text1, lineHash);
    text2 = diff_linesToCharsMunge(lineArray.text2, lineHash);

    lineArray.resize(lineHash.size() + 1);
    for (typename std::map<LinePtr, size_t>::const_iterator i = lineHash.begin(); i != lineHash.end(); ++i)
      lineArray[(*i).second] = (*i).first;
  }

  /**
   * Split a text into a list of pointers to strings.  Reduce the texts to a string of
   * hashes where each Unicode character represents one line.
   * @param text String to encode.
   * @param lineHash Map of string pointers to indices.
   * @return Encoded string.
   */
 private:
  static string_t diff_linesToCharsMunge(const string_t &text, std::map<LinePtr, size_t> &lineHash) {
    string_t chars;
    // 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.
    typename string_t::size_type lineLen;
    for (typename string_t::const_pointer lineStart = text.c_str(), textEnd = lineStart + text.size(); lineStart < textEnd; lineStart += lineLen + 1) {
      lineLen = next_token(text, traits::from_wchar(L'\n'), lineStart);
      if (lineStart + lineLen == textEnd) --lineLen;
      chars += (char_t)(*lineHash.insert(std::make_pair(LinePtr(lineStart, lineLen + 1), lineHash.size() + 1)).first).second;
    }
    return chars;
  }

  /**
   * Rehydrate the text in a diff from a string of line hashes to real lines of
   * text.
   * @param diffs LinkedList of Diff objects.
   * @param lineArray List of pointers to unique strings.
   */
 private:
  static void diff_charsToLines(Diffs &diffs, const Lines& lineArray) {
    for (typename Diffs::iterator cur_diff = diffs.begin(); cur_diff != diffs.end(); ++cur_diff) {
      string_t text;
      for (int y = 0; y < (int)(*cur_diff).text.length(); y++) {
        const LinePtr& lp = lineArray[static_cast<size_t>((*cur_diff).text[y])];
        text.append(lp.first, lp.second);
      }
      (*cur_diff).text.swap(text);
    }
  }

  /**
   * Determine the common prefix of two strings.
   * @param text1 First string.
   * @param text2 Second string.
   * @return The number of characters common to the start of each string.
   */
 public:
  static int diff_commonPrefix(const string_t &text1, const string_t &text2) {
    // Performance analysis: http://neil.fraser.name/news/2007/10/09/
    const int n = std::min(text1.length(), text2.length());
    for (int i = 0; i < n; i++) {
      if (text1[i] != text2[i]) {
        return i;
      }
    }
    return n;
  }

  /**
   * Determine the common suffix of two strings.
   * @param text1 First string.
   * @param text2 Second string.
   * @return The number of characters common to the end of each string.
   */
 public:
  static int diff_commonSuffix(const string_t &text1, const string_t &text2) {
    // Performance analysis: http://neil.fraser.name/news/2007/10/09/
    const int text1_length = text1.length();
    const int text2_length = text2.length();
    const int n = std::min(text1_length, text2_length);
    for (int i = 1; i <= n; i++) {
      if (text1[text1_length - i] != text2[text2_length - i]) {
        return i - 1;
      }
    }
    return n;
  }

  /**
   * Determine if the suffix of one string is the prefix of another.
   * @param text1 First string.
   * @param text2 Second string.
   * @return The number of characters common to the end of the first
   *     string and the start of the second string.
   */
 protected:
  static int diff_commonOverlap(const string_t &text1, const string_t &text2) {
    // Cache the text lengths to prevent multiple calls.
    const int text1_length = text1.length();
    const int text2_length = text2.length();
    // Eliminate the null case.
    if (text1_length == 0 || text2_length == 0) {
      return 0;
    }
    // Truncate the longer string.
    string_t text1_trunc = text1;
    string_t text2_trunc = text2;
    if (text1_length > text2_length) {
      text1_trunc = right(text1, text2_length);
    } else if (text1_length < text2_length) {
      text2_trunc = text2.substr(0, text1_length);
    }
    const int text_length = std::min(text1_length, text2_length);
    // Quick check for the worst case.
    if (text1_trunc == text2_trunc) {
      return text_length;
    }

    // Start by looking for a single character match
    // and increase length until no match is found.
    // Performance analysis: http://neil.fraser.name/news/2010/11/04/
    int best = 0;
    int length = 1;
    while (true) {
      string_t pattern = right(text1_trunc, length);
      size_t found = text2_trunc.find(pattern);
      if (found == string_t::npos) {
        return best;
      }
      length += found;
      if (found == 0 || right(text1_trunc, length) == text2_trunc.substr(0, length)) {
        best = length;
        length++;
      }
    }
  }

 protected:
  struct HalfMatchResult {
    string_t text1_a, text1_b, text2_a, text2_b, mid_common;
    void swap(HalfMatchResult& hm) {
      text1_a.swap(hm.text1_a), text1_b.swap(hm.text1_b), text2_a.swap(hm.text2_a), text2_b.swap(hm.text2_b), mid_common.swap(hm.mid_common);
    }
  };

  /**
   * 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.
   * @param text1 First string.
   * @param text2 Second string.
   * @param hm HalfMatchResult object, containing the prefix of text1, the
   *     suffix of text1, the prefix of text2, the suffix of text2 and the
   *     common middle.
   * @return Boolean true if there was a match, false otherwise.
   */
  static bool diff_halfMatch(const string_t &text1, const string_t &text2, HalfMatchResult& hm) {
    const string_t longtext = text1.length() > text2.length() ? text1 : text2;
    const string_t shorttext = text1.length() > text2.length() ? text2 : text1;
    if (longtext.length() < 4 || shorttext.length() * 2 < longtext.length()) {
      return false;  // Pointless.
    }

    HalfMatchResult res1, res2;
    // First check if the second quarter is the seed for a half-match.
    bool hm1 = diff_halfMatchI(longtext, shorttext,
        (longtext.length() + 3) / 4, res1);
    // Check again based on the third quarter.
    bool hm2 = diff_halfMatchI(longtext, shorttext,
        (longtext.length() + 1) / 2, res2);
    if (!hm1 && !hm2) {
      return false;
    } else if (!hm2) {
      hm.swap(res1);
    } else if (!hm1) {
      hm.swap(res2);
    } else {
      // Both matched.  Select the longest.
      hm.swap(res1.mid_common.length() > res2.mid_common.length() ? res1 : res2);
    }

    // A half-match was found, sort out the return data.
    if (text1.length() <= text2.length()) {
      hm.text1_a.swap(hm.text2_a);
      hm.text1_b.swap(hm.text2_b);
    }
    return true;
  }

  /**
   * Does a substring of shorttext exist within longtext such that the
   * substring is at least half the length of longtext?
   * @param longtext Longer string.
   * @param shorttext Shorter string.
   * @param i Start index of quarter length substring within longtext.
   * @param best HalfMatchResult object, containing the prefix of longtext, the
   *     suffix of longtext, the prefix of shorttext, the suffix of shorttext
   *     and the common middle.
   * @return Boolean true if there was a match, false otherwise.
   */
 private:
  static bool diff_halfMatchI(const string_t &longtext, const string_t &shorttext, int i, HalfMatchResult& best) {
    // Start with a 1/4 length substring at position i as a seed.
    const string_t seed = safeMid(longtext, i, longtext.length() / 4);
    size_t j = string_t::npos;
    while ((j = shorttext.find(seed, j + 1)) != string_t::npos) {
      const int prefixLength = diff_commonPrefix(safeMid(longtext, i),
          safeMid(shorttext, j));
      const int suffixLength = diff_commonSuffix(longtext.substr(0, i),
          shorttext.substr(0, j));
      if ((int)best.mid_common.length() < suffixLength + prefixLength) {
        best.mid_common = safeMid(shorttext, j - suffixLength, suffixLength)
            + safeMid(shorttext, j, prefixLength);
        best.text1_a = longtext.substr(0, i - suffixLength);
        best.text1_b = safeMid(longtext, i + prefixLength);
        best.text2_a = shorttext.substr(0, j - suffixLength);
        best.text2_b = safeMid(shorttext, j + prefixLength);
      }
    }
    return best.mid_common.length() * 2 >= longtext.length();
  }

  /**
   * Reduce the number of edits by eliminating semantically trivial equalities.
   * @param diffs LinkedList of Diff objects.
   */
 public:
  static void diff_cleanupSemantic(Diffs &diffs) {
    if (diffs.empty()) {
      return;
    }
    bool changes = false;
    std::vector<typename Diffs::iterator> equalities;  // Stack of equalities.
    string_t lastequality;  // Always equal to equalities.lastElement().text
    typename Diffs::iterator cur_diff;
    // Number of characters that changed prior to the equality.
    int length_insertions1 = 0;
    int length_deletions1 = 0;
    // Number of characters that changed after the equality.
    int length_insertions2 = 0;
    int length_deletions2 = 0;
    for (cur_diff = diffs.begin(); cur_diff != diffs.end();) {
      if ((*cur_diff).operation == EQUAL) {
        // Equality found.
        equalities.push_back(cur_diff);
        length_insertions1 = length_insertions2;
        length_deletions1 = length_deletions2;
        length_insertions2 = 0;
        length_deletions2 = 0;
        lastequality = (*cur_diff).text;
      } else {
        // An insertion or deletion.
        if ((*cur_diff).operation == INSERT) {
          length_insertions2 += (*cur_diff).text.length();
        } else {
          length_deletions2 += (*cur_diff).text.length();
        }
        // Eliminate an equality that is smaller or equal to the edits on both
        // sides of it.
        if (!lastequality.empty()
            && ((int)lastequality.length()
                <= std::max(length_insertions1, length_deletions1))
            && ((int)lastequality.length()
                <= std::max(length_insertions2, length_deletions2))) {
          // printf("Splitting: '%s'\n", qPrintable(lastequality));
          // Walk back to offending equality.
          // Change second copy to insert.
          (*(cur_diff = equalities.back())).operation = INSERT;
          // Duplicate record.
          diffs.insert(cur_diff, Diff(DELETE, lastequality));
          equalities.pop_back();  // Throw away the equality we just deleted.
          if (!equalities.empty()) {
            // Throw away the previous equality (it needs to be reevaluated).
            equalities.pop_back();
          }
          length_insertions1 = 0;  // Reset the counters.
          length_deletions1 = 0;
          length_insertions2 = 0;
          length_deletions2 = 0;
          lastequality = string_t();
          changes = true;

          if (!equalities.empty())
            // There is a safe equality we can fall back to.
            cur_diff = equalities.back();
          else
          {
            // There are no previous equalities, walk back to the start.
            cur_diff = diffs.begin();
            continue;
          }
        }
      }
      ++cur_diff;
    }

    // Normalize the diff.
    if (changes) {
      diff_cleanupMerge(diffs);
    }
    diff_cleanupSemanticLossless(diffs);

    // Find any overlaps between deletions and insertions.
    // e.g: <del>abcxxx</del><ins>xxxdef</ins>
    //   -> <del>abc</del>xxx<ins>def</ins>
    // e.g: <del>xxxabc</del><ins>defxxx</ins>
    //   -> <ins>def</ins>xxx<del>abc</del>
    // Only extract an overlap if it is as big as the edit ahead or behind it.
    if ((cur_diff = diffs.begin()) != diffs.end()) {
      for (typename Diffs::iterator prev_diff = cur_diff; ++cur_diff != diffs.end(); prev_diff = cur_diff) {
        if ((*prev_diff).operation == DELETE &&
            (*cur_diff).operation == INSERT) {
          string_t deletion = (*prev_diff).text;
          string_t insertion = (*cur_diff).text;
          int overlap_length1 = diff_commonOverlap(deletion, insertion);
          int overlap_length2 = diff_commonOverlap(insertion, deletion);
          if (overlap_length1 >= overlap_length2) {
            if (overlap_length1 >= deletion.size() / 2.0 ||
                overlap_length1 >= insertion.size() / 2.0) {
              // Overlap found.  Insert an equality and trim the surrounding edits.
              diffs.insert(cur_diff, Diff(EQUAL, insertion.substr(0, overlap_length1)));
              prev_diff->text =
                  deletion.substr(0, deletion.length() - overlap_length1);
              cur_diff->text = safeMid(insertion, overlap_length1);
              // diffs.insert inserts the element before the cursor, so there is
              // no need to step past the new element.
            }
          } else {
            if (overlap_length2 >= deletion.length() / 2.0 ||
                overlap_length2 >= insertion.length() / 2.0) {
              // Reverse overlap found.
              // Insert an equality and swap and trim the surrounding edits.
              diffs.insert(cur_diff, Diff(EQUAL, deletion.substr(0, overlap_length2)));
              prev_diff->operation = INSERT;
              prev_diff->text =
                  insertion.substr(0, insertion.length() - overlap_length2);
              cur_diff->operation = DELETE;
              cur_diff->text = safeMid(deletion, overlap_length2);
              // diffs.insert inserts the element before the cursor, so there is
              // no need to step past the new element.
            }
          }
          if (++cur_diff == diffs.end()) break;
        }
      }
    }
  }

  /**
   * 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.
   * @param diffs LinkedList of Diff objects.
   */
 public:
  static void diff_cleanupSemanticLossless(Diffs &diffs) {
    string_t equality1, edit, equality2;
    string_t commonString;
    int commonOffset;
    int score, bestScore;
    string_t bestEquality1, bestEdit, bestEquality2;
    // Create a new iterator at the start.
    typename Diffs::iterator prev_diff = diffs.begin(), cur_diff = prev_diff;
    if (prev_diff == diffs.end() || ++cur_diff == diffs.end()) return;

    // Intentionally ignore the first and last element (don't need checking).
    for (typename Diffs::iterator next_diff = cur_diff; ++next_diff != diffs.end(); prev_diff = cur_diff, cur_diff = next_diff) {
      if ((*prev_diff).operation == EQUAL &&
        (*next_diff).operation == EQUAL) {
          // This is a single edit surrounded by equalities.
          equality1 = (*prev_diff).text;
          edit = (*cur_diff).text;
          equality2 = (*next_diff).text;

          // First, shift the edit as far left as possible.
          commonOffset = diff_commonSuffix(equality1, edit);
          if (commonOffset != 0) {
            commonString = safeMid(edit, edit.length() - commonOffset);
            equality1 = equality1.substr(0, equality1.length() - commonOffset);
            edit = commonString + edit.substr(0, edit.length() - commonOffset);
            equality2 = commonString + equality2;
          }

          // Second, step character by character right, looking for the best fit.
          bestEquality1 = equality1;
          bestEdit = edit;
          bestEquality2 = equality2;
          bestScore = diff_cleanupSemanticScore(equality1, edit)
              + diff_cleanupSemanticScore(edit, equality2);
          while (!edit.empty() && !equality2.empty()
              && edit[0] == equality2[0]) {
            equality1 += edit[0];
            edit = safeMid(edit, 1) + equality2[0];
            equality2 = safeMid(equality2, 1);
            score = diff_cleanupSemanticScore(equality1, edit)
                + diff_cleanupSemanticScore(edit, equality2);
            // The >= encourages trailing rather than leading whitespace on edits.
            if (score >= bestScore) {
              bestScore = score;
              bestEquality1 = equality1;
              bestEdit = edit;
              bestEquality2 = equality2;
            }
          }

          if ((*prev_diff).text != bestEquality1) {
            // We have an improvement, save it back to the diff.
            if (!bestEquality1.empty()) {
              (*prev_diff).text = bestEquality1;
            } else {
              diffs.erase(prev_diff);
            }
            (*cur_diff).text = bestEdit;
            if (!bestEquality2.empty()) {
              (*next_diff).text = bestEquality2;
            } else {
              diffs.erase(next_diff); // Delete nextDiff.
              next_diff = cur_diff;
              cur_diff = prev_diff;
            }
          }
      }
    }
  }

  /**
   * Given two strings, compute a score representing whether the internal
   * boundary falls on logical boundaries.
   * Scores range from 6 (best) to 0 (worst).
   * @param one First string.
   * @param two Second string.
   * @return The score.
   */
 private:
  static int diff_cleanupSemanticScore(const string_t &one, const string_t &two) {
    if (one.empty() || two.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.
    char_t char1 = one[one.length() - 1];
    char_t char2 = two[0];
    bool nonAlphaNumeric1 = !traits::is_alnum(char1);
    bool nonAlphaNumeric2 = !traits::is_alnum(char2);
    bool whitespace1 = nonAlphaNumeric1 && traits::is_space(char1);
    bool whitespace2 = nonAlphaNumeric2 && traits::is_space(char2);
    bool lineBreak1 = whitespace1 && is_control(char1);
    bool lineBreak2 = whitespace2 && is_control(char2);
    bool blankLine1 = false;
    if (lineBreak1) {
      typename string_t::const_reverse_iterator p1 = one.rbegin(), p2 = one.rend();
      if (traits::to_wchar(*p1) == L'\n' && ++p1 != p2) {
        if (traits::to_wchar(*p1) == L'\r')
          ++p1;
        blankLine1 = p1 != p2 && traits::to_wchar(*p1) == L'\n';
      }
    }
    bool blankLine2 = false;
    if (lineBreak2) {
      typename string_t::const_iterator p1 = two.end(), p2 = two.begin();
      if (traits::to_wchar(*p2) == L'\r')
        ++p2;
      if (p2 != p1 && traits::to_wchar(*p2) == L'\n') {
        if (++p2 != p1 && traits::to_wchar(*p2) == L'\r')
          ++p2;
        if (p2 != p1 && traits::to_wchar(*p2) == L'\n')
          blankLine2 = true;
      }
    }
  
    if (blankLine1 || blankLine2) {
      // Five points for blank lines.
      return 5;
    } else if (lineBreak1 || lineBreak2) {
      // Four points for line breaks.
      return 4;
    } else if (nonAlphaNumeric1 && !whitespace1 && whitespace2) {
      // Three points for end of sentences.
      return 3;
    } else if (whitespace1 || whitespace2) {
      // Two points for whitespace.
      return 2;
    } else if (nonAlphaNumeric1 || nonAlphaNumeric2) {
      // One point for non-alphanumeric.
      return 1;
    }
    return 0;
  }
  /**
   * Reduce the number of edits by eliminating operationally trivial equalities.
   * @param diffs LinkedList of Diff objects.
   */
 public:
  void diff_cleanupEfficiency(Diffs &diffs) const {
    if (diffs.empty()) {
      return;
    }
    bool changes = false;
    std::vector<typename Diffs::iterator> equalities;  // Stack of equalities.
    string_t lastequality;  // Always equal to equalities.lastElement().text
    // Is there an insertion operation before the last equality.
    bool pre_ins = false;
    // Is there a deletion operation before the last equality.
    bool pre_del = false;
    // Is there an insertion operation after the last equality.
    bool post_ins = false;
    // Is there a deletion operation after the last equality.
    bool post_del = false;

    for (typename Diffs::iterator cur_diff = diffs.begin(); cur_diff != diffs.end();) {
      if ((*cur_diff).operation == EQUAL) {
        // Equality found.
        if ((int)(*cur_diff).text.length() < Diff_EditCost && (post_ins || post_del)) {
          // Candidate found.
          equalities.push_back(cur_diff);
          pre_ins = post_ins;
          pre_del = post_del;
          lastequality = (*cur_diff).text;
        } else {
          // Not a candidate, and can never become one.
          equalities.clear();
          lastequality.clear();
        }
        post_ins = post_del = false;
      } else {
        // An insertion or deletion.
        if ((*cur_diff).operation == DELETE) {
          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 (!lastequality.empty()
            && ((pre_ins && pre_del && post_ins && post_del)
            || (((int)lastequality.length() < Diff_EditCost / 2)
            && ((pre_ins ? 1 : 0) + (pre_del ? 1 : 0)
            + (post_ins ? 1 : 0) + (post_del ? 1 : 0)) == 3))) {
          // printf("Splitting: '%s'\n", qPrintable(lastequality));
          // Walk back to offending equality.
          // Change second copy to insert.
          (*(cur_diff = equalities.back())).operation = INSERT;
          // Duplicate record.
          diffs.insert(cur_diff, Diff(DELETE, lastequality));
          equalities.pop_back();  // Throw away the equality we just deleted.
          lastequality.clear();
          changes = true;
          if (pre_ins && pre_del) {
            // No changes made which could affect previous entry, keep going.
            post_ins = post_del = true;
            equalities.clear();
          } else {
            if (!equalities.empty()) {
              // Throw away the previous equality (it needs to be reevaluated).
              equalities.pop_back();
            }
            post_ins = post_del = false;
            if (!equalities.empty())
              // There is a safe equality we can fall back to.
              cur_diff = equalities.back();
            else
            {
              // There are no previous equalities, walk back to the start.
              cur_diff = diffs.begin();
              continue;
            }
          }
        }
      }
      ++cur_diff;
    }

    if (changes) {
      diff_cleanupMerge(diffs);
    }
  }

  /**
   * Reorder and merge like edit sections.  Merge equalities.
   * Any edit section can move as long as it doesn't cross an equality.
   * @param diffs LinkedList of Diff objects.
   */
 public:
  static void diff_cleanupMerge(Diffs &diffs) {
    diffs.push_back(Diff(EQUAL, string_t()));  // Add a dummy entry at the end.
    typename Diffs::iterator prev_diff, cur_diff;
    int count_delete = 0;
    int count_insert = 0;
    string_t text_delete;
    string_t text_insert;
    Diff *prevEqual = NULL;
    int commonlength;
    for (cur_diff = diffs.begin(); cur_diff != diffs.end(); ++cur_diff) {
      switch ((*cur_diff).operation) {
        case INSERT:
          count_insert++;
          text_insert += (*cur_diff).text;
          prevEqual = NULL;
          break;
        case DELETE:
          count_delete++;
          text_delete += (*cur_diff).text;
          prevEqual = NULL;
          break;
        case EQUAL:
          if (count_delete + count_insert > 1) {
            // Delete the offending records.
            prev_diff = cur_diff;
            std::advance(prev_diff, -(count_delete + count_insert));
            diffs.erase(prev_diff, cur_diff);
            if (count_delete != 0 && count_insert != 0) {
              // Factor out any common prefixes.
              commonlength = diff_commonPrefix(text_insert, text_delete);
              if (commonlength != 0) {
                if (cur_diff != diffs.begin()) {
                  prev_diff = cur_diff;
                  if ((*--prev_diff).operation != EQUAL) {
                    llvm_unreachable("Previous diff should have been an equality.");
                  }
                  (*prev_diff).text += text_insert.substr(0, commonlength);
                } else {
                  diffs.insert(cur_diff, Diff(EQUAL, text_insert.substr(0, commonlength)));
                }
                text_insert = safeMid(text_insert, commonlength);
                text_delete = safeMid(text_delete, commonlength);
              }
              // Factor out any common suffixes.
              commonlength = diff_commonSuffix(text_insert, text_delete);
              if (commonlength != 0) {
                (*cur_diff).text = safeMid(text_insert, text_insert.length()
                    - commonlength) + (*cur_diff).text;
                text_insert = text_insert.substr(0, text_insert.length()
                    - commonlength);
                text_delete = text_delete.substr(0, text_delete.length()
                    - commonlength);
              }
            }
            // Insert the merged records.
            if (!text_delete.empty()) {
              diffs.insert(cur_diff, Diff(DELETE, text_delete));
            }
            if (!text_insert.empty()) {
              diffs.insert(cur_diff, Diff(INSERT, text_insert));
            }
          } else if (prevEqual != NULL) {
            // Merge this equality with the previous one.
            prevEqual->text += (*cur_diff).text;
            diffs.erase(cur_diff--);
          }
          
          count_insert = 0;
          count_delete = 0;
          text_delete.clear();
          text_insert.clear();
          prevEqual = &*cur_diff;
          break;
        }

    }
    if (diffs.back().text.empty()) {
      diffs.pop_back();  // Remove the dummy entry at the end.
    }

    /*
    * 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
    */
    bool changes = false;
    // Create a new iterator at the start.
    // (As opposed to walking the current one back.)
    prev_diff = cur_diff = diffs.begin();
    if (prev_diff != diffs.end() && ++cur_diff != diffs.end()) {
      // Intentionally ignore the first and last element (don't need checking).
      for (typename Diffs::iterator next_diff = cur_diff; ++next_diff != diffs.end(); prev_diff = cur_diff, cur_diff = next_diff) {
        if ((*prev_diff).operation == EQUAL &&
          (*next_diff).operation == EQUAL) {
            // This is a single edit surrounded by equalities.
            if ((*cur_diff).text.size() >= (*prev_diff).text.size() &&
                (*cur_diff).text.compare((*cur_diff).text.size() - (*prev_diff).text.size(), (*prev_diff).text.size(), (*prev_diff).text) == 0) {
              // Shift the edit over the previous equality.
              (*cur_diff).text = (*prev_diff).text
                  + (*cur_diff).text.substr(0, (*cur_diff).text.length()
                  - (*prev_diff).text.length());
              (*next_diff).text = (*prev_diff).text + (*next_diff).text;
              diffs.erase(prev_diff);
              cur_diff = next_diff;
              changes = true;
              if (++next_diff == diffs.end()) break;
            } else if ((*cur_diff).text.size() >= (*next_diff).text.size() && (*cur_diff).text.compare(0, (*next_diff).text.size(), (*next_diff).text) == 0) {
              // Shift the edit over the next equality.
              (*prev_diff).text += (*next_diff).text;
              (*cur_diff).text = safeMid((*cur_diff).text, (*next_diff).text.length())
                  + (*next_diff).text;
              next_diff = diffs.erase(next_diff); // Delete nextDiff.
              changes = true;
              if (next_diff == diffs.end()) break;
            }
        }
      }
    }
    // If shifts were made, the diff needs reordering and another shift sweep.
    if (changes) {
      diff_cleanupMerge(diffs);
    }
  }

  /**
   * 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
   * @param diffs LinkedList of Diff objects.
   * @param loc Location within text1.
   * @return Location within text2.
   */
 public:
  static int diff_xIndex(const Diffs &diffs, int loc) {
    int chars1 = 0;
    int chars2 = 0;
    int last_chars1 = 0;
    int last_chars2 = 0;
    typename Diffs::const_iterator last_diff = diffs.end(), cur_diff;
    for (cur_diff = diffs.begin(); cur_diff != diffs.end(); ++cur_diff) {
      if ((*cur_diff).operation != INSERT) {
        // Equality or deletion.
        chars1 += (*cur_diff).text.length();
      }
      if ((*cur_diff).operation != DELETE) {
        // Equality or insertion.
        chars2 += (*cur_diff).text.length();
      }
      if (chars1 > loc) {
        // Overshot the location.
        last_diff = cur_diff;
        break;
      }
      last_chars1 = chars1;
      last_chars2 = chars2;
    }
    if (last_diff != diffs.end() && (*last_diff).operation == DELETE) {
      // The location was deleted.
      return last_chars2;
    }
    // Add the remaining character length.
    return last_chars2 + (loc - last_chars1);
  }

  /**
   * Convert a Diff list into a pretty HTML report.
   * @param diffs LinkedList of Diff objects.
   * @return HTML representation.
   */
 public:
  static string_t diff_prettyHtml(const Diffs &diffs) {
    string_t html;
    string_t text;
    for (typename Diffs::const_iterator cur_diff = diffs.begin(); cur_diff != diffs.end(); ++cur_diff) {
      typename string_t::size_type n = (*cur_diff).text.size();
      typename string_t::const_pointer p, end;
      for (p = (*cur_diff).text.c_str(), end = p + n; p != end; ++p)
        switch (traits::to_wchar(*p)) {
          case L'&': n += 4; break;
          case L'<':
          case L'>': n += 3; break;
          case L'\n': n += 9; break;
        }
      if (n == (*cur_diff).text.size())
        text = (*cur_diff).text;
      else {
        text.clear();
        text.reserve(n);
        for (p = (*cur_diff).text.c_str(); p != end; ++p)
          switch (traits::to_wchar(*p)) {
            case L'&': text += traits::cs(L"&amp;"); break;
            case L'<': text += traits::cs(L"&lt;"); break;
            case L'>': text += traits::cs(L"&gt;"); break;
            case L'\n': text += traits::cs(L"&para;<br>"); break;
            default: text += *p;
          }
      }
      switch ((*cur_diff).operation) {
        case INSERT:
          html += traits::cs(L"<ins style=\"background:#e6ffe6;\">") + text + traits::cs(L"</ins>");
          break;
        case DELETE:
          html += traits::cs(L"<del style=\"background:#ffe6e6;\">") + text + traits::cs(L"</del>");
          break;
        case EQUAL:
          html += traits::cs(L"<span>") + text + traits::cs(L"</span>");
          break;
      }
    }
    return html;
  }

  /**
   * Compute and return the source text (all equalities and deletions).
   * @param diffs LinkedList of Diff objects.
   * @return Source text.
   */
 public:
  static string_t diff_text1(const Diffs &diffs) {
    string_t text;
    for (typename Diffs::const_iterator cur_diff = diffs.begin(); cur_diff != diffs.end(); ++cur_diff) {
      if ((*cur_diff).operation != INSERT) {
        text += (*cur_diff).text;
      }
    }
    return text;
  }

  /**
   * Compute and return the destination text (all equalities and insertions).
   * @param diffs LinkedList of Diff objects.
   * @return Destination text.
   */
 public:
  static string_t diff_text2(const Diffs &diffs) {
    string_t text;
    for (typename Diffs::const_iterator cur_diff = diffs.begin(); cur_diff != diffs.end(); ++cur_diff) {
      if ((*cur_diff).operation != DELETE) {
        text += (*cur_diff).text;
      }
    }
    return text;
  }

  /**
   * Compute the Levenshtein distance; the number of inserted, deleted or
   * substituted characters.
   * @param diffs LinkedList of Diff objects.
   * @return Number of changes.
   */
 public:
  static int diff_levenshtein(const Diffs &diffs) {
    int levenshtein = 0;
    int insertions = 0;
    int deletions = 0;
    for (typename Diffs::const_iterator cur_diff = diffs.begin(); cur_diff != diffs.end(); ++cur_diff) {
      switch ((*cur_diff).operation) {
        case INSERT:
          insertions += (*cur_diff).text.length();
          break;
        case DELETE:
          deletions += (*cur_diff).text.length();
          break;
        case EQUAL:
          // A deletion and an insertion is one substitution.
          levenshtein += std::max(insertions, deletions);
          insertions = 0;
          deletions = 0;
          break;
      }
    }
    levenshtein += std::max(insertions, deletions);
    return levenshtein;
  }

  /**
   * 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.
   * @param diffs Array of diff tuples.
   * @return Delta text.
   */
 public:
  static string_t diff_toDelta(const Diffs &diffs) {
    string_t text;
    for (typename Diffs::const_iterator cur_diff = diffs.begin(); cur_diff != diffs.end(); ++cur_diff) {
      switch ((*cur_diff).operation) {
        case INSERT: {
          text += traits::from_wchar(L'+');
          append_percent_encoded(text, (*cur_diff).text);
          text += traits::from_wchar(L'\t');
          break;
        }
        case DELETE:
          text += traits::from_wchar(L'-') + to_string((*cur_diff).text.length()) + traits::from_wchar(L'\t');
          break;
        case EQUAL:
          text += traits::from_wchar(L'=') + to_string((*cur_diff).text.length()) + traits::from_wchar(L'\t');
          break;
      }
    }
    if (!text.empty()) {
      // Strip off trailing tab character.
      text = text.substr(0, text.length() - 1);
    }
    return text;
  }

  /**
   * Given the original text1, and an encoded string which describes the
   * operations required to transform text1 into text2, compute the full diff.
   * @param text1 Source string for the diff.
   * @param delta Delta text.
   * @return Array of diff tuples or null if invalid.
   * @throws string_t If invalid input.
   */
 public:
  static Diffs diff_fromDelta(const string_t &text1, const string_t &delta) {
    Diffs diffs;
    int pointer = 0;  // Cursor in text1
    typename string_t::size_type token_len;
    for (typename string_t::const_pointer token = delta.c_str(); token - delta.c_str() < (int)delta.length(); token += token_len + 1) {
      token_len = next_token(delta, traits::from_wchar(L'\t'), token);
      if (token_len == 0) {
        // Blank tokens are ok (from a trailing \t).
        continue;
      }
      // Each token begins with a one character parameter which specifies the
      // operation of this token (delete, insert, equality).
      string_t param(token + 1, token_len - 1);
      switch (traits::to_wchar(*token)) {
        case L'+':
          percent_decode(param);
          diffs.push_back(Diff(INSERT, param));
          break;
        case L'-':
          // Fall through.
        case L'=': {
          int n;
          n = to_int(param);
          if (n < 0) {
            llvm_unreachable("Negative number in diff_fromDelta: " + param);
          }
          string_t text;
          text = safeMid(text1, pointer, n);
          pointer += n;
          if (traits::to_wchar(*token) == L'=') {
            diffs.push_back(Diff(EQUAL, text));
          } else {
            diffs.push_back(Diff(DELETE, text));
          }
          break;
        }
        default:
          llvm_unreachable(traits::cs(L"Invalid diff operation in diff_fromDelta: " + *token));
      }
    }
    if (pointer != text1.length()) {
      llvm_unreachable(traits::cs(L"Delta length (") + to_string(pointer)
                     + traits::cs(L") smaller than source text length (")
                     + to_string(text1.length()) + traits::from_wchar(L')'));
    }
    return diffs;
  }


  //  MATCH FUNCTIONS


  /**
   * Locate the best instance of 'pattern' in 'text' near 'loc'.
   * Returns -1 if no match found.
   * @param text The text to search.
   * @param pattern The pattern to search for.
   * @param loc The location to search around.
   * @return Best match index or -1.
   */
 public:
  int match_main(const string_t &text, const string_t &pattern, int loc) const {
    loc = std::max(0, std::min(loc, (int)text.length()));
    if (text == pattern) {
      // Shortcut (potentially not guaranteed by the algorithm)
      return 0;
    } else if (text.empty()) {
      // Nothing to match.
      return -1;
    } else if (loc + pattern.length() <= text.length()
        && safeMid(text, loc, pattern.length()) == pattern) {
      // Perfect match at the perfect spot!  (Includes case of null pattern)
      return loc;
    } else {
      // Do a fuzzy compare.
      return match_bitap(text, pattern, loc);
    }
  }

  /**
   * Locate the best instance of 'pattern' in 'text' near 'loc' using the
   * Bitap algorithm.  Returns -1 if no match found.
   * @param text The text to search.
   * @param pattern The pattern to search for.
   * @param loc The location to search around.
   * @return Best match index or -1.
   */
 protected:
  int match_bitap(const string_t &text, const string_t &pattern, int loc) const {
    if (!(Match_MaxBits == 0 || (int)pattern.length() <= Match_MaxBits)) {
      llvm_unreachable("Pattern too long for this application.");
    }

    // Initialise the alphabet.
    std::map<char_t, int> s; 
    match_alphabet(pattern, s);

    // Highest score beyond which we give up.
    double score_threshold = Match_Threshold;
    // Is there a nearby exact match? (speedup)
    size_t best_loc = text.find(pattern, loc);
    if (best_loc != string_t::npos) {
      score_threshold = std::min(match_bitapScore(0, best_loc, loc, pattern),
          score_threshold);
      // What about in the other direction? (speedup)
      best_loc = text.rfind(pattern, loc + pattern.length());
      if (best_loc != string_t::npos) {
        score_threshold = std::min(match_bitapScore(0, best_loc, loc, pattern),
            score_threshold);
      }
    }

    // Initialise the bit arrays.
    int matchmask = 1 << (pattern.length() - 1);
    best_loc = -1;

    int bin_min, bin_mid;
    int bin_max = pattern.length() + text.length();
    int *rd;
    int *last_rd = NULL;
    for (int d = 0; d < (int)pattern.length(); d++) {
      // 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.
      bin_min = 0;
      bin_mid = bin_max;
      while (bin_min < bin_mid) {
        if (match_bitapScore(d, loc + bin_mid, loc, pattern)
            <= score_threshold) {
          bin_min = bin_mid;
        } else {
          bin_max = bin_mid;
        }
        bin_mid = (bin_max - bin_min) / 2 + bin_min;
      }
      // Use the result from this iteration as the maximum for the next.
      bin_max = bin_mid;
      int start = std::max(1, loc - bin_mid + 1);
      int finish = std::min(loc + bin_mid, (int)text.length()) + pattern.length();

      rd = new int[finish + 2];
      rd[finish + 1] = (1 << d) - 1;
      for (int j = finish; j >= start; j--) {
        int charMatch;
        if ((int)text.length() <= j - 1) {
          // Out of range.
          charMatch = 0;
        } else {
          charMatch = s[text[j - 1]];
        }
        if (d == 0) {
          // First pass: exact match.
          rd[j] = ((rd[j + 1] << 1) | 1) & charMatch;
        } else {
          // Subsequent passes: fuzzy match.
          rd[j] = (((rd[j + 1] << 1) | 1) & charMatch)
              | (((last_rd[j + 1] | last_rd[j]) << 1) | 1)
              | last_rd[j + 1];
        }
        if ((rd[j] & matchmask) != 0) {
          double score = match_bitapScore(d, j - 1, loc, pattern);
          // 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 = std::max(1, 2 * loc - (int)best_loc);
            } else {
              // Already passed loc, downhill from here on in.
              break;
            }
          }
        }
      }
      if (match_bitapScore(d + 1, loc, loc, pattern) > score_threshold) {
        // No hope for a (better) match at greater error levels.
        break;
      }
      delete [] last_rd;
      last_rd = rd;
    }
    delete [] last_rd;
    delete [] rd;
    return best_loc;
  }

  /**
   * Compute and return the score for a match with e errors and x location.
   * @param e Number of errors in match.
   * @param x Location of match.
   * @param loc Expected location of match.
   * @param pattern Pattern being sought.
   * @return Overall score for match (0.0 = good, 1.0 = bad).
   */
 private:
  double match_bitapScore(int e, int x, int loc, const string_t &pattern) const {
    const float accuracy = static_cast<float> (e) / pattern.length();
    const int proximity = (loc - x < 0)? (x - loc) : (loc - x);
    if (Match_Distance == 0) {
      // Dodge divide by zero error.
      return proximity == 0 ? accuracy : 1.0;
    }
    return accuracy + (proximity / static_cast<float> (Match_Distance));
  }

  /**
   * Initialise the alphabet for the Bitap algorithm.
   * @param pattern The text to encode.
   * @param s Hash of character locations.
   */
 protected:
  static void match_alphabet(const string_t &pattern, std::map<char_t, int>& s) {
    // There is no need to initialize map values, since they are zero-initialized by default
    for (size_t i = 0; i < pattern.length(); i++)
      s[pattern[i]] |= (1 << (pattern.length() - i - 1));
  }


 //  PATCH FUNCTIONS


  /**
   * Increase the context until it is unique,
   * but don't let the pattern expand beyond Match_MaxBits.
   * @param patch The patch to grow.
   * @param text Source text.
   */
 protected:
  void patch_addContext(Patch &patch, const string_t &text) const {
    if (text.empty()) {
      return;
    }
    string_t pattern = safeMid(text, patch.start2, patch.length1);
    int padding = 0;

    // Look for the first and last matches of pattern in text.  If two different
    // matches are found, increase the pattern length.
    while (text.find(pattern) != text.rfind(pattern)
        && (int)pattern.length() < Match_MaxBits - Patch_Margin - Patch_Margin) {
      padding += Patch_Margin;
      pattern = safeMid(text, std::max(0, patch.start2 - padding),
          std::min((int)text.length(), patch.start2 + patch.length1 + padding)
          - std::max(0, patch.start2 - padding));
    }
    // Add one chunk for good luck.
    padding += Patch_Margin;

    // Add the prefix.
    string_t prefix = safeMid(text, std::max(0, patch.start2 - padding),
        patch.start2 - std::max(0, patch.start2 - padding));
    if (!prefix.empty()) {
      patch.diffs.push_front(Diff(EQUAL, prefix));
    }
    // Add the suffix.
    string_t suffix = safeMid(text, patch.start2 + patch.length1,
        std::min((int)text.length(), patch.start2 + patch.length1 + padding)
        - (patch.start2 + patch.length1));
    if (!suffix.empty()) {
      patch.diffs.push_back(Diff(EQUAL, suffix));
    }

    // Roll back the start points.
    patch.start1 -= prefix.length();
    patch.start2 -= prefix.length();
    // Extend the lengths.
    patch.length1 += prefix.length() + suffix.length();
    patch.length2 += prefix.length() + suffix.length();
  }

  /**
   * Compute a list of patches to turn text1 into text2.
   * A set of diffs will be computed.
   * @param text1 Old text.
   * @param text2 New text.
   * @return LinkedList of Patch objects.
   */
 public:
  Patches patch_make(const string_t &text1, const string_t &text2) const {
    // No diffs provided, compute our own.
    Diffs diffs = diff_main(text1, text2, true);
    if (diffs.size() > 2) {
      diff_cleanupSemantic(diffs);
      diff_cleanupEfficiency(diffs);
    }

    return patch_make(text1, diffs);
  }

  /**
   * Compute a list of patches to turn text1 into text2.
   * text1 will be derived from the provided diffs.
   * @param diffs Array of diff tuples for text1 to text2.
   * @return LinkedList of Patch objects.
   */
 public:
  Patches patch_make(const Diffs &diffs) const {
    // No origin string provided, compute our own.
    return patch_make(diff_text1(diffs), diffs);
  }

  /**
   * Compute a list of patches to turn text1 into text2.
   * text2 is ignored, diffs are the delta between text1 and text2.
   * @param text1 Old text.
   * @param text2 Ignored.
   * @param diffs Array of diff tuples for text1 to text2.
   * @return LinkedList of Patch objects.
   * @note Prefer patch_make(const string_t &text1, const Diffs &diffs).
   */
 public:
  Patches patch_make(const string_t &text1, const string_t &text2, const Diffs &diffs) const {
    return patch_make(text1, diffs); // text2 is entirely unused.
  }

  /**
   * Compute a list of patches to turn text1 into text2.
   * text2 is not provided, diffs are the delta between text1 and text2.
   * @param text1 Old text.
   * @param diffs Array of diff tuples for text1 to text2.
   * @return LinkedList of Patch objects.
   */
 public:
  Patches patch_make(const string_t &text1, const Diffs &diffs) const {
    Patches patches;
    if (!diffs.empty()) { // Get rid of the null case.
      Patch patch;
      int char_count1 = 0;  // Number of characters into the text1 string.
      int char_count2 = 0;  // Number of characters into the text2 string.
      // Start with text1 (prepatch_text) and apply the diffs until we arrive at
      // text2 (postpatch_text).  We recreate the patches one by one to determine
      // context info.
      string_t prepatch_text = text1;
      string_t postpatch_text = text1;
      for (typename Diffs::const_iterator cur_diff = diffs.begin(); cur_diff != diffs.end(); ++cur_diff) {
        if (patch.diffs.empty() && (*cur_diff).operation != EQUAL) {
          // A new patch starts here.
          patch.start1 = char_count1;
          patch.start2 = char_count2;
        }

        switch ((*cur_diff).operation) {
          case INSERT:
            patch.diffs.push_back(*cur_diff);
            patch.length2 += (*cur_diff).text.length();
            postpatch_text = postpatch_text.substr(0, char_count2)
                + (*cur_diff).text + safeMid(postpatch_text, char_count2);
            break;
          case DELETE:
            patch.length1 += (*cur_diff).text.length();
            patch.diffs.push_back(*cur_diff);
            postpatch_text = postpatch_text.substr(0, char_count2)
                + safeMid(postpatch_text, char_count2 + (*cur_diff).text.length());
            break;
          case EQUAL:
            if ((int)(*cur_diff).text.length() <= 2 * Patch_Margin
                && !patch.diffs.empty() && !(*cur_diff == diffs.back())) {
              // Small equality inside a patch.
              patch.diffs.push_back(*cur_diff);
              patch.length1 += (*cur_diff).text.length();
              patch.length2 += (*cur_diff).text.length();
            }

            if ((int)(*cur_diff).text.length() >= 2 * Patch_Margin) {
              // Time for a new patch.
              if (!patch.diffs.empty()) {
                patch_addContext(patch, prepatch_text);
                patches.push_back(patch);
                patch = Patch();
                // Unlike Unidiff, our patch lists have a rolling context.
                // http://code.google.com/p/google-diff-match-patch/wiki/Unidiff
                // Update prepatch text & pos to reflect the application of the
                // just completed patch.
                prepatch_text = postpatch_text;
                char_count1 = char_count2;
              }
            }
            break;
        }

        // Update the current character count.
        if ((*cur_diff).operation != INSERT) {
          char_count1 += (*cur_diff).text.length();
        }
        if ((*cur_diff).operation != DELETE) {
          char_count2 += (*cur_diff).text.length();
        }
      }
      // Pick up the leftover patch if not empty.
      if (!patch.diffs.empty()) {
        patch_addContext(patch, prepatch_text);
        patches.push_back(patch);
      }
    }
    return patches;
  }

  /**
   * Given an array of patches, return another array that is identical.
   * @param patches Array of patch objects.
   * @return Array of patch objects.
   */
 public:
  Patches patch_deepCopy(const Patches &patches) const { return patches; }

  /**
   * Merge a set of patches onto the text.  Return a patched text, as well
   * as an array of true/false values indicating which patches were applied.
   * @param patches Array of patch objects.
   * @param text Old text.
   * @return Two element Object array, containing the new text and an array of
   *      boolean values.
   */
 public:
  std::pair<string_t, std::vector<bool> > patch_apply(const Patches &patches, const string_t &text) const
    { std::pair<string_t, std::vector<bool> > res; patch_apply(patches, text, res); return res; }
  void patch_apply(const Patches &patches, const string_t &sourceText, std::pair<string_t, std::vector<bool> >& res) const {
    if (patches.empty()) {
      res.first = sourceText;
      res.second.clear();
      return;
    }
    string_t text = sourceText;  // Copy to preserve original.

    // Deep copy the patches so that no changes are made to originals.
  //  Patches patchesCopy = patch_deepCopy(patches);
    Patches patchesCopy(patches); // Default copy constructor will do it just fine

    string_t nullPadding = patch_addPadding(patchesCopy);
    text = nullPadding + text + nullPadding;
    patch_splitMax(patchesCopy);

    int x = 0;
    // 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.
    int delta = 0;
    std::vector<bool>& results = res.second;
    results.resize(patchesCopy.size());
    string_t text1, text2;
    for (typename Patches::const_iterator cur_patch = patchesCopy.begin(); cur_patch != patchesCopy.end(); ++cur_patch) {
      int expected_loc = (*cur_patch).start2 + delta;
      text1 = diff_text1((*cur_patch).diffs);
      int start_loc;
      int end_loc = -1;
      if ((int)text1.length() > Match_MaxBits) {
        // patch_splitMax will only provide an oversized pattern in the case of
        // a monster delete.
        start_loc = match_main(text, text1.substr(0, Match_MaxBits), expected_loc);
        if (start_loc != -1) {
          end_loc = match_main(text, right(text1, Match_MaxBits),
              expected_loc + text1.length() - Match_MaxBits);
          if (end_loc == -1 || start_loc >= end_loc) {
            // Can't find valid trailing context.  Drop this patch.
            start_loc = -1;
          }
        }
      } else {
        start_loc = match_main(text, text1, expected_loc);
      }
      if (start_loc == -1) {
        // No match found.  :(
        results[x] = false;
        // Subtract the delta for this failed patch from subsequent patches.
        delta -= (*cur_patch).length2 - (*cur_patch).length1;
      } else {
        // Found a match.  :)
        results[x] = true;
        delta = start_loc - expected_loc;
        if (end_loc == -1) {
          text2 = safeMid(text, start_loc, text1.length());
        } else {
          text2 = safeMid(text, start_loc, end_loc + Match_MaxBits - start_loc);
        }
        if (text1 == text2) {
          // Perfect match, just shove the replacement text in.
          text = text.substr(0, start_loc) + diff_text2((*cur_patch).diffs) + safeMid(text, start_loc + text1.length());
        } else {
          // Imperfect match.  Run a diff to get a framework of equivalent
          // indices.
          Diffs diffs = diff_main(text1, text2, false);
          if ((int)text1.length() > Match_MaxBits
              && diff_levenshtein(diffs) / static_cast<float> (text1.length())
              > Patch_DeleteThreshold) {
            // The end points match, but the content is unacceptably bad.
            results[x] = false;
          } else {
            diff_cleanupSemanticLossless(diffs);
            int index1 = 0;
            for (typename Diffs::const_iterator cur_diff = (*cur_patch).diffs.begin(); cur_diff != (*cur_patch).diffs.end(); ++cur_diff) {
              if ((*cur_diff).operation != EQUAL) {
                int index2 = diff_xIndex(diffs, index1);
                if ((*cur_diff).operation == INSERT) {
                  // Insertion
                  text = text.substr(0, start_loc + index2) + (*cur_diff).text
                      + safeMid(text, start_loc + index2);
                } else if ((*cur_diff).operation == DELETE) {
                  // Deletion
                  text = text.substr(0, start_loc + index2)
                      + safeMid(text, start_loc + diff_xIndex(diffs,
                      index1 + (*cur_diff).text.length()));
                }
              }
              if ((*cur_diff).operation != DELETE) {
                index1 += (*cur_diff).text.length();
              }
            }
          }
        }
      }
      x++;
    }
    // Strip the padding off.
    res.first = safeMid(text, nullPadding.length(), text.length() - 2 * nullPadding.length());
  }

  /**
   * Add some padding on text start and end so that edges can match something.
   * Intended to be called only from within patch_apply.
   * @param patches Array of patch objects.
   * @return The padding string added to each side.
   */
 public:
  string_t patch_addPadding(Patches &patches) const {
    short paddingLength = Patch_Margin;
    string_t nullPadding;
    for (short x = 1; x <= paddingLength; x++) {
      nullPadding += (char_t)x;
    }

    // Bump all the patches forward.
    for (typename Patches::iterator cur_patch = patches.begin(); cur_patch != patches.end(); ++cur_patch) {
      (*cur_patch).start1 += paddingLength;
      (*cur_patch).start2 += paddingLength;
    }

    // Add some padding on start of first diff.
    Patch &firstPatch = patches.front();
    Diffs &firstPatchDiffs = firstPatch.diffs;
    if (firstPatchDiffs.empty() || firstPatchDiffs.front().operation != EQUAL) {
      // Add nullPadding equality.
      firstPatchDiffs.push_front(Diff(EQUAL, nullPadding));
      firstPatch.start1 -= paddingLength;  // Should be 0.
      firstPatch.start2 -= paddingLength;  // Should be 0.
      firstPatch.length1 += paddingLength;
      firstPatch.length2 += paddingLength;
    } else if (paddingLength > (int)firstPatchDiffs.front().text.length()) {
      // Grow first equality.
      Diff &firstDiff = firstPatchDiffs.front();
      int extraLength = paddingLength - firstDiff.text.length();
      firstDiff.text = safeMid(nullPadding, firstDiff.text.length(),
          paddingLength - firstDiff.text.length()) + firstDiff.text;
      firstPatch.start1 -= extraLength;
      firstPatch.start2 -= extraLength;
      firstPatch.length1 += extraLength;
      firstPatch.length2 += extraLength;
    }

    // Add some padding on end of last diff.
    Patch &lastPatch = patches.front();
    Diffs &lastPatchDiffs = lastPatch.diffs;
    if (lastPatchDiffs.empty() || lastPatchDiffs.back().operation != EQUAL) {
      // Add nullPadding equality.
      lastPatchDiffs.push_back(Diff(EQUAL, nullPadding));
      lastPatch.length1 += paddingLength;
      lastPatch.length2 += paddingLength;
    } else if (paddingLength > (int)lastPatchDiffs.back().text.length()) {
      // Grow last equality.
      Diff &lastDiff = lastPatchDiffs.back();
      int extraLength = paddingLength - lastDiff.text.length();
      lastDiff.text += nullPadding.substr(0, extraLength);
      lastPatch.length1 += extraLength;
      lastPatch.length2 += extraLength;
    }

    return 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.
   * @param patches LinkedList of Patch objects.
   */
 public:
  void patch_splitMax(Patches &patches) const {
    short patch_size = Match_MaxBits;
    string_t precontext, postcontext;
    Patch patch;
    int start1, start2;
    bool empty;
    Operation diff_type;
    string_t diff_text;
    Patch bigpatch;

    for (typename Patches::iterator cur_patch = patches.begin(); cur_patch != patches.end();) {
      if ((*cur_patch).length1 <= patch_size) { ++cur_patch; continue; }
      bigpatch = *cur_patch;
      // Remove the big old patch.
      cur_patch = patches.erase(cur_patch);
      start1 = bigpatch.start1;
      start2 = bigpatch.start2;
      precontext.clear();
      while (!bigpatch.diffs.empty()) {
        // Create one of several smaller patches.
        patch = Patch();
        empty = true;
        patch.start1 = start1 - precontext.length();
        patch.start2 = start2 - precontext.length();
        if (!precontext.empty()) {
          patch.length1 = patch.length2 = precontext.length();
          patch.diffs.push_back(Diff(EQUAL, precontext));
        }
        while (!bigpatch.diffs.empty()
            && patch.length1 < patch_size - Patch_Margin) {
          diff_type = bigpatch.diffs.front().operation;
          diff_text = bigpatch.diffs.front().text;
          if (diff_type == INSERT) {
            // Insertions are harmless.
            patch.length2 += diff_text.length();
            start2 += diff_text.length();
            patch.diffs.push_back(bigpatch.diffs.front());
            bigpatch.diffs.pop_front();
            empty = false;
          } else if (diff_type == DELETE && patch.diffs.size() == 1
              && patch.diffs.front().operation == EQUAL
              && (int)diff_text.length() > 2 * patch_size) {
            // This is a large deletion.  Let it pass in one chunk.
            patch.length1 += diff_text.length();
            start1 += diff_text.length();
            empty = false;
            patch.diffs.push_back(Diff(diff_type, diff_text));
            bigpatch.diffs.pop_front();
          } else {
            // Deletion or equality.  Only take as much as we can stomach.
            diff_text = diff_text.substr(0, std::min((int)diff_text.length(),
                patch_size - patch.length1 - Patch_Margin));
            patch.length1 += diff_text.length();
            start1 += diff_text.length();
            if (diff_type == EQUAL) {
              patch.length2 += diff_text.length();
              start2 += diff_text.length();
            } else {
              empty = false;
            }
            patch.diffs.push_back(Diff(diff_type, diff_text));
            if (diff_text == bigpatch.diffs.front().text) {
              bigpatch.diffs.pop_front();
            } else {
              bigpatch.diffs.front().text = safeMid(bigpatch.diffs.front().text, diff_text.length());
            }
          }
        }
        // Compute the head context for the next patch.
        precontext = safeMid(diff_text2(patch.diffs), std::max(0, (int)precontext.length() - Patch_Margin));
        // Append the end context for this patch.
        postcontext = diff_text1(bigpatch.diffs);
        if ((int)postcontext.length() > Patch_Margin) {
          postcontext = postcontext.substr(0, Patch_Margin);
        }
        if (!postcontext.empty()) {
          patch.length1 += postcontext.length();
          patch.length2 += postcontext.length();
          if (!patch.diffs.empty()
              && patch.diffs.back().operation == EQUAL) {
            patch.diffs.back().text += postcontext;
          } else {
            patch.diffs.push_back(Diff(EQUAL, postcontext));
          }
        }
        if (!empty) {
          patches.insert(cur_patch, patch);
        }
      }
    }
  }

  /**
   * Take a list of patches and return a textual representation.
   * @param patches List of Patch objects.
   * @return Text representation of patches.
   */
 public:
  static string_t patch_toText(const Patches &patches) {
    string_t text;
    for (typename Patches::const_iterator cur_patch = patches.begin(); cur_patch != patches.end(); ++cur_patch) {
      text += (*cur_patch).toString();
    }
    return text;
  }

  /**
   * Parse a textual representation of patches and return a List of Patch
   * objects.
   * @param textline Text representation of patches.
   * @return List of Patch objects.
   * @throws string_t If invalid input.
   */
 public:
  Patches patch_fromText(const string_t &textline) const {
    Patches patches;
    if (!textline.empty()) {
      char_t sign;
      string_t line;
      typename string_t::const_pointer text = textline.c_str();
      typename string_t::size_type text_len, l;
      while (text - textline.c_str() < (int)textline.length()) {
        if ((text_len = next_token(textline, traits::from_wchar(L'\n'), text)) == 0) { ++text; continue; }

        // A replacement for the regexp "^@@ -(\\d+),?(\\d*) \\+(\\d+),?(\\d*) @@$" exact match
        string_t start1, length1, start2, length2;
        do {
          typename string_t::const_pointer t = text;
          l = text_len;
          if ((l -= 9) > 0 && traits::to_wchar(*t) == L'@' && traits::to_wchar(*++t) == L'@'
               && traits::to_wchar(*++t) == L' ' && traits::to_wchar(*++t) == L'-' && traits::is_digit(*++t)) {
            do { start1 += *t; } while (--l > 0 && traits::is_digit(*++t));
            if (l > 0 && traits::to_wchar(*t) == L',') ++t, --l;
            while (l > 0 && traits::is_digit(*t)) --l, length1 += *t++;
            if (l > 0 && traits::to_wchar(*t++) == L' ' && traits::to_wchar(*t++) == L'+' && traits::is_digit(*t)) {
              do { start2 += *t; --l; } while (traits::is_digit(*++t));
              if (l > 0 && traits::to_wchar(*t) == L',') ++t, --l;
              while (l > 0 && traits::is_digit(*t)) --l, length2 += *t++;
              if (l == 0 && traits::to_wchar(*t++) == L' ' && traits::to_wchar(*t++) == L'@' && traits::to_wchar(*t) == L'@') break; // Success
            }
          }
          llvm_unreachable(traits::cs(L"Invalid patch string: ") + string_t(text, text_len));
        } while (false);

        Patch patch;
        patch.start1 = to_int(start1);
        if (length1.empty()) {
          patch.start1--;
          patch.length1 = 1;
        } else if (length1.size() == 1 && traits::to_wchar(length1[0]) == L'0') {
          patch.length1 = 0;
        } else {
          patch.start1--;
          patch.length1 = to_int(length1);
        }

        patch.start2 = to_int(start2);
        if (length2.empty()) {
          patch.start2--;
          patch.length2 = 1;
        } else if (length2.size() == 1 && traits::to_wchar(length2[0]) == L'0') {
          patch.length2 = 0;
        } else {
          patch.start2--;
          patch.length2 = to_int(length2);
        }

        for (text += text_len + 1; text - textline.c_str() < (int)textline.length(); text += text_len + 1) {
          if ((text_len = next_token(textline, traits::from_wchar(L'\n'), text)) == 0) continue;

          sign = *text;
          line.assign(text + 1, text_len - 1);
          percent_decode(line);
          switch (traits::to_wchar(sign)) {
            case L'-':
              // Deletion.
              patch.diffs.push_back(Diff(DELETE, line));
              continue;
            case L'+':
              // Insertion.
              patch.diffs.push_back(Diff(INSERT, line));
              continue;
            case L' ':
              // Minor equality.
              patch.diffs.push_back(Diff(EQUAL, line));
              continue;
            case L'@':
              // Start of next patch.
              break;
            default:
              // WTF?
              llvm_unreachable(traits::cs(L"Invalid patch mode '") + (sign + (traits::cs(L"' in: ") + line)));
          }
          break;
        }

        patches.push_back(patch);
      }
    }
    return patches;
  }

  /**
   * A safer version of string_t.mid(pos).  This one returns "" instead of
   * null when the position equals the string length.
   * @param str String to take a substring from.
   * @param pos Position to start the substring from.
   * @return Substring.
   */
 private:
  static inline string_t safeMid(const string_t &str, size_t pos) {
    return (pos == str.length()) ? string_t() : str.substr(pos);
  }

  /**
   * A safer version of string_t.mid(pos, len).  This one returns "" instead of
   * null when the position equals the string length.
   * @param str String to take a substring from.
   * @param pos Position to start the substring from.
   * @param len Length of substring.
   * @return Substring.
   */
 private:
  static inline string_t safeMid(const string_t &str, size_t pos, size_t len) {
    return (pos == str.length()) ? string_t() : str.substr(pos, len);
  }

  /**
   * Utility functions
   */
 private:
  static string_t to_string(int n) {
    string_t str;
    bool negative = false;
    size_t l = 0;
    if (n < 0) n = -n, ++l, negative = true;
    int n_ = n; do { ++l; } while ((n_ /= 10) > 0);
    str.resize(l);
    typename string_t::iterator s = str.end();
    const wchar_t digits[] = L"0123456789";
    do { *--s = traits::from_wchar(digits[n % 10]); } while ((n /= 10) > 0);
    if (negative) *--s = traits::from_wchar(L'-');
    return str;
  }

  static int to_int(const string_t& str) { return traits::to_int(str.c_str()); }

  static bool is_control(char_t c) { switch (traits::to_wchar(c)) { case L'\n': case L'\r': return true; } return false; }

  static typename string_t::size_type next_token(const string_t& str, char_t delim, typename string_t::const_pointer off) {
    typename string_t::const_pointer p = off, end = str.c_str() + str.length();
    for (; p != end; ++p) if (*p == delim) break;
    return p - off;
  }

  static void append_percent_encoded(string_t& s1, const string_t& s2) {
    const wchar_t safe_chars[] = L"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz-_.~ !*'();/?:@&=+$,#";

    size_t safe[0x100], i;
    for (i = 0; i < 0x100; ++i) safe[i] = 0;
    for (i = 0; i < sizeof(safe_chars) / sizeof(wchar_t); ++i) safe[safe_chars[i]] = i + 1;

    int n = 0;
    typename traits::utf32_t u;
    typename string_t::const_pointer c = s2.c_str(), end = c + s2.length();
    while (c != end) {
      c = traits::to_utf32(c, end, u);
      n += u >= 0x10000? 12 : u >= 0x800? 9 : u >= 0x80? 6 : safe[static_cast<unsigned char>(u)]? 1 : 3;
    }
    if (n == int(s2.length()))
      s1.append(s2);
    else {
      s1.reserve(s1.size() + n);
      // Encode as UTF-8, then escape unsafe characters
      unsigned char utf8[4];
      for (c = s2.c_str(); c != end;) {
        c = traits::to_utf32(c, end, u);
        unsigned char* pt = utf8;
        if (u < 0x80)
          *pt++ = (unsigned char)u;  
        else if (u < 0x800) {
          *pt++ = (unsigned char)((u >> 6) | 0xC0);
          *pt++ = (unsigned char)((u & 0x3F) | 0x80);
        }
        else if (u < 0x10000) {
          *pt++ = (unsigned char)((u >> 12) | 0xE0);
          *pt++ = (unsigned char)(((u >> 6) & 0x3F) | 0x80);
          *pt++ = (unsigned char)((u & 0x3F) | 0x80);
        }
        else {
          *pt++ = (unsigned char)((u >> 18) | 0xF0);
          *pt++ = (unsigned char)(((u >> 12) & 0x3F) | 0x80);
          *pt++ = (unsigned char)(((u >> 6) & 0x3F) | 0x80);
          *pt++ = (unsigned char)((u & 0x3F) | 0x80);
        }

        for (const unsigned char* p = utf8; p < pt; ++p)
          if (safe[*p])
            s1 += traits::from_wchar(safe_chars[safe[*p] - 1]);
          else {
            s1 += traits::from_wchar(L'%');
            s1 += traits::from_wchar(safe_chars[(*p & 0xF0) >> 4]);
            s1 += traits::from_wchar(safe_chars[*p & 0xF]);
          }
      }
    }
  }

  static unsigned hex_digit_value(char_t c) {
    switch (traits::to_wchar(c))
    {
      case L'0': return 0;
      case L'1': return 1;
      case L'2': return 2;
      case L'3': return 3;
      case L'4': return 4;
      case L'5': return 5;
      case L'6': return 6;
      case L'7': return 7;
      case L'8': return 8;
      case L'9': return 9;
      case L'A': case L'a': return 0xA;
      case L'B': case L'b': return 0xB;
      case L'C': case L'c': return 0xC;
      case L'D': case L'd': return 0xD;
      case L'E': case L'e': return 0xE;
      case L'F': case L'f': return 0xF;
    }
    llvm_unreachable(string_t(traits::cs(L"Invalid character: ")) + c);
  }

  static void percent_decode(string_t& str) {
    typename string_t::iterator s2 = str.begin(), s3 = s2, s4 = s2;
    for (typename string_t::const_pointer s1 = str.c_str(), end = s1 + str.size(); s1 != end; ++s1, ++s2)
      if (traits::to_wchar(*s1) != L'%')
        *s2 = *s1;
      else {
        char_t d1 = *++s1;
        *s2 = char_t((hex_digit_value(d1) << 4) + hex_digit_value(*++s1));
      }
    // Decode UTF-8 string in-place
    while (s3 != s2) {
      unsigned u = *s3;
      if (u < 0x80)
        ;
      else if ((u >> 5) == 6) {
        if (++s3 == s2 || (*s3 & 0xC0) != 0x80) continue;
        u = ((u & 0x1F) << 6) + (*s3 & 0x3F);
      }
      else if ((u >> 4) == 0xE) {
        if (++s3 == s2 || (*s3 & 0xC0) != 0x80) continue;
        u = ((u & 0xF) << 12) + ((*s3 & 0x3F) << 6);
        if (++s3 == s2 || (*s3 & 0xC0) != 0x80) continue;
        u += *s3 & 0x3F;
      }
      else if ((u >> 3) == 0x1E) {
        if (++s3 == s2 || (*s3 & 0xC0) != 0x80) continue;
        u = ((u & 7) << 18) + ((*s3 & 0x3F) << 12);
        if (++s3 == s2 || (*s3 & 0xC0) != 0x80) continue;
        u += (*s3 & 0x3F) << 6;
        if (++s3 == s2 || (*s3 & 0xC0) != 0x80) continue;
        u += *s3 & 0x3F; 
      }
      else {
        ++s3;
        continue;
      }
      s4 = traits::from_utf32(u, s4);
      ++s3;
    }
    if (s4 != str.end()) str.resize(s4 - str.begin());
  }

  static string_t right(const string_t& str, typename string_t::size_type n) { return str.substr(str.size() - n); }
};


/**
 * Functions dependent on character type
 */

// Unicode helpers
template <class char_t, class utf32_type = unsigned>
struct diff_match_patch_utf32_direct {
  typedef utf32_type utf32_t;
  template <class iterator> static iterator to_utf32(iterator i, iterator /*end*/, utf32_t& u)
  {
    u = *i++;
    return i;
  }
  template <class iterator> static iterator from_utf32(utf32_t u, iterator o)
  {
    *o++ = static_cast<char_t>(u);
    return o;
  }
};

template <class char_t, class utf32_type = unsigned>
struct diff_match_patch_utf32_from_utf16 {
  typedef utf32_type utf32_t;
  static const unsigned UTF16_SURROGATE_MIN = 0xD800u;
  static const unsigned UTF16_SURROGATE_MAX = 0xDFFFu;
  static const unsigned UTF16_HIGH_SURROGATE_MAX = 0xDBFFu;
  static const unsigned UTF16_LOW_SURROGATE_MIN = 0xDC00u;
  static const unsigned UTF16_SURROGATE_OFFSET = (UTF16_SURROGATE_MIN << 10) + UTF16_HIGH_SURROGATE_MAX - 0xFFFFu;
  template <class iterator> static iterator to_utf32(iterator i, iterator end, utf32_t& u)
  {
    u = *i++;
    if (UTF16_SURROGATE_MIN <= u && u <= UTF16_HIGH_SURROGATE_MAX && i != end)
      u = (u << 10) + *i++ - UTF16_SURROGATE_OFFSET; // Assume it is a UTF-16 surrogate pair
    return i;
  }
  template <class iterator> static iterator from_utf32(utf32_t u, iterator o)
  {
    if (u > 0xFFFF) { // Encode code points that do not fit in char_t as UTF-16 surrogate pairs
      *o++ = static_cast<char_t>((u >> 10) + UTF16_SURROGATE_MIN - (0x10000 >> 10));
      *o++ = static_cast<char_t>((u & 0x3FF) + UTF16_LOW_SURROGATE_MIN);
    }
    else
      *o++ = static_cast<char_t>(u);
    return o;
  }
};

// Specialization of the traits for wchar_t
#include <cwctype>
template <> struct diff_match_patch_traits<wchar_t> : diff_match_patch_utf32_from_utf16<wchar_t> {
  static bool is_alnum(wchar_t c) { return std::iswalnum(c)? true : false; }
  static bool is_digit(wchar_t c) { return std::iswdigit(c)? true : false; }
  static bool is_space(wchar_t c) { return std::iswspace(c)? true : false; }
  static int to_int(const wchar_t* s) { return static_cast<int>(std::wcstol(s, NULL, 10)); }
  static wchar_t from_wchar(wchar_t c) { return c; }
  static wchar_t to_wchar(wchar_t c) { return c; }
  static const wchar_t* cs(const wchar_t* s) { return s; }
  static const wchar_t eol = L'\n';
  static const wchar_t tab = L'\t';
};

// Possible specialization of the traits for char
#include <cctype>
template <> struct diff_match_patch_traits<char> : diff_match_patch_utf32_direct<char>
{
  static bool is_alnum(char c) { return std::isalnum(c)? true : false; }
  static bool is_digit(char c) { return std::isdigit(c)? true : false; }
  static bool is_space(char c) { return std::isspace(c)? true : false; }
  static int to_int(const char* s) { return std::atoi(s); }
  static char from_wchar(wchar_t c) { return static_cast<char>(c); }
  static wchar_t to_wchar(char c) { return static_cast<wchar_t>(c); }
  static std::string cs(const wchar_t* s) { return std::string(s, s + wcslen(s)); }
  static const char eol = '\n';
  static const char tab = '\t';
};


#endif // DIFF_MATCH_PATCH_H