/*

 *  LibXDiff by Davide Libenzi ( File Differential Library )

 *  Copyright (C) 2003-2016 Davide Libenzi, Johannes E. Schindelin

 *

 *  This library is free software; you can redistribute it and/or

 *  modify it under the terms of the GNU Lesser General Public

 *  License as published by the Free Software Foundation; either

 *  version 2.1 of the License, or (at your option) any later version.

 *

 *  This library is distributed in the hope that it will be useful,

 *  but WITHOUT ANY WARRANTY; without even the implied warranty of

 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

 *  Lesser General Public License for more details.

 *

 *  You should have received a copy of the GNU Lesser General Public

 *  License along with this library; if not, see

 *  <http://www.gnu.org/licenses/>.

 *

 *  Davide Libenzi <davidel@xmailserver.org>

 *

 */

#include "xinclude.h"

/*

 * The basic idea of patience diff is to find lines that are unique in

 * both files.  These are intuitively the ones that we want to see as

 * common lines.

 *

 * The maximal ordered sequence of such line pairs (where ordered means

 * that the order in the sequence agrees with the order of the lines in

 * both files) naturally defines an initial set of common lines.

 *

 * Now, the algorithm tries to extend the set of common lines by growing

 * the line ranges where the files have identical lines.

 *

 * Between those common lines, the patience diff algorithm is applied

 * recursively, until no unique line pairs can be found; these line ranges

 * are handled by the well-known Myers algorithm.

 */

#define NON_UNIQUE ULONG_MAX

/*

 * This is a hash mapping from line hash to line numbers in the first and

 * second file.

 */

struct hashmap {

  int nr, alloc;

  struct entry {

    unsigned long hash;

    /*

     * 0 = unused entry, 1 = first line, 2 = second, etc.

     * line2 is NON_UNIQUE if the line is not unique

     * in either the first or the second file.

     */

    unsigned long line1, line2;

    /*

     * "next" & "previous" are used for the longest common

     * sequence;

     * initially, "next" reflects only the order in file1.

     */

    struct entry *next, *previous;

    /*

     * If 1, this entry can serve as an anchor. See

     * Documentation/diff-options.txt for more information.

     */

    unsigned anchor : 1;

  } *entries, *first, *last;

  /* were common records found? */

  unsigned long has_matches;

  xdfenv_t *env;

  xpparam_t const *xpp;

};

static int is_anchor(xpparam_t const *xpp, const char *line)

{

  int i;

  for (i = 0; i < xpp->anchors_nr; i++) {

    if (!strncmp(line, xpp->anchors[i], strlen(xpp->anchors[i])))

      return 1;

  }

  return 0;

}

/* The argument "pass" is 1 for the first file, 2 for the second. */

static void insert_record(xpparam_t const *xpp, int line, struct hashmap *map,

        int pass)

{

  xrecord_t **records = pass == 1 ?

    map->env->xdf1.recs : map->env->xdf2.recs;

  xrecord_t *record = records[line - 1];

  /*

   * After xdl_prepare_env() (or more precisely, due to

   * xdl_classify_record()), the "ha" member of the records (AKA lines)

   * is _not_ the hash anymore, but a linearized version of it.  In

   * other words, the "ha" member is guaranteed to start with 0 and

   * the second record's ha can only be 0 or 1, etc.

   *

   * So we multiply ha by 2 in the hope that the hashing was

   * "unique enough".

   */

  int index = (int)((record->ha << 1) % map->alloc);

  while (map->entries[index].line1) {

    if (map->entries[index].hash != record->ha) {

      if (++index >= map->alloc)

        index = 0;

      continue;

    }

    if (pass == 2)

      map->has_matches = 1;

    if (pass == 1 || map->entries[index].line2)

      map->entries[index].line2 = NON_UNIQUE;

    else

      map->entries[index].line2 = line;

    return;

  }

  if (pass == 2)

    return;

  map->entries[index].line1 = line;

  map->entries[index].hash = record->ha;

  map->entries[index].anchor = is_anchor(xpp, map->env->xdf1.recs[line - 1]->ptr);

  if (!map->first)

    map->first = map->entries + index;

  if (map->last) {

    map->last->next = map->entries + index;

    map->entries[index].previous = map->last;

  }

  map->last = map->entries + index;

  map->nr++;

}

/*

 * This function has to be called for each recursion into the inter-hunk

 * parts, as previously non-unique lines can become unique when being

 * restricted to a smaller part of the files.

 *

 * It is assumed that env has been prepared using xdl_prepare().

 */

static int fill_hashmap(xpparam_t const *xpp, xdfenv_t *env,

    struct hashmap *result,

    int line1, int count1, int line2, int count2)

{

  result->xpp = xpp;

  result->env = env;

  /* We know exactly how large we want the hash map */

  result->alloc = count1 * 2;

  if (!XDL_CALLOC_ARRAY(result->entries, result->alloc))

    return -1;

  /* First, fill with entries from the first file */

  while (count1--)

    insert_record(xpp, line1++, result, 1);

  /* Then search for matches in the second file */

  while (count2--)

    insert_record(xpp, line2++, result, 2);

  return 0;

}

/*

 * Find the longest sequence with a smaller last element (meaning a smaller

 * line2, as we construct the sequence with entries ordered by line1).

 */

static int binary_search(struct entry **sequence, int longest,

    struct entry *entry)

{

  int left = -1, right = longest;

  while (left + 1 < right) {

    int middle = left + (right - left) / 2;

    /* by construction, no two entries can be equal */

    if (sequence[middle]->line2 > entry->line2)

      right = middle;

    else

      left = middle;

  }

  /* return the index in "sequence", _not_ the sequence length */

  return left;

}

/*

 * The idea is to start with the list of common unique lines sorted by

 * the order in file1.  For each of these pairs, the longest (partial)

 * sequence whose last element's line2 is smaller is determined.

 *

 * For efficiency, the sequences are kept in a list containing exactly one

 * item per sequence length: the sequence with the smallest last

 * element (in terms of line2).

 */

static int find_longest_common_sequence(struct hashmap *map, struct entry **res)

{

  struct entry **sequence;

  int longest = 0, i;

  struct entry *entry;

  /*

   * If not -1, this entry in sequence must never be overridden.

   * Therefore, overriding entries before this has no effect, so

   * do not do that either.

   */

  int anchor_i = -1;

  if (!XDL_ALLOC_ARRAY(sequence, map->nr))

    return -1;

  for (entry = map->first; entry; entry = entry->next) {

    if (!entry->line2 || entry->line2 == NON_UNIQUE)

      continue;

    i = binary_search(sequence, longest, entry);

    entry->previous = i < 0 ? NULL : sequence[i];

    ++i;

    if (i <= anchor_i)

      continue;

    sequence[i] = entry;

    if (entry->anchor) {

      anchor_i = i;

      longest = anchor_i + 1;

    } else if (i == longest) {

      longest++;

    }

  }

  /* No common unique lines were found */

  if (!longest) {

    *res = NULL;

    xdl_free(sequence);

    return 0;

  }

  /* Iterate starting at the last element, adjusting the "next" members */

  entry = sequence[longest - 1];

  entry->next = NULL;

  while (entry->previous) {

    entry->previous->next = entry;

    entry = entry->previous;

  }

  *res = entry;

  xdl_free(sequence);

  return 0;

}

static int match(struct hashmap *map, int line1, int line2)

{

  xrecord_t *record1 = map->env->xdf1.recs[line1 - 1];

  xrecord_t *record2 = map->env->xdf2.recs[line2 - 1];

  return record1->ha == record2->ha;

}

static int patience_diff(xpparam_t const *xpp, xdfenv_t *env,

    int line1, int count1, int line2, int count2);

static int walk_common_sequence(struct hashmap *map, struct entry *first,

    int line1, int count1, int line2, int count2)

{

  int end1 = line1 + count1, end2 = line2 + count2;

  int next1, next2;

  for (;;) {

    /* Try to grow the line ranges of common lines */

    if (first) {

      next1 = first->line1;

      next2 = first->line2;

      while (next1 > line1 && next2 > line2 &&

          match(map, next1 - 1, next2 - 1)) {

        next1--;

        next2--;

      }

    } else {

      next1 = end1;

      next2 = end2;

    }

    while (line1 < next1 && line2 < next2 &&

        match(map, line1, line2)) {

      line1++;

      line2++;

    }

    /* Recurse */

    if (next1 > line1 || next2 > line2) {

      if (patience_diff(map->xpp, map->env,

          line1, next1 - line1,

          line2, next2 - line2))

        return -1;

    }

    if (!first)

      return 0;

    while (first->next &&

        first->next->line1 == first->line1 + 1 &&

        first->next->line2 == first->line2 + 1)

      first = first->next;

    line1 = first->line1 + 1;

    line2 = first->line2 + 1;

    first = first->next;

  }

}

static int fall_back_to_classic_diff(struct hashmap *map,

    int line1, int count1, int line2, int count2)

{

  xpparam_t xpp;

  memset(&xpp, 0, sizeof(xpp));

  xpp.flags = map->xpp->flags & ~XDF_DIFF_ALGORITHM_MASK;

  return xdl_fall_back_diff(map->env, &xpp,

          line1, count1, line2, count2);

}

/*

 * Recursively find the longest common sequence of unique lines,

 * and if none was found, ask xdl_do_diff() to do the job.

 *

 * This function assumes that env was prepared with xdl_prepare_env().

 */

static int patience_diff(xpparam_t const *xpp, xdfenv_t *env,

    int line1, int count1, int line2, int count2)

{

  struct hashmap map;

  struct entry *first;

  int result = 0;

  /* trivial case: one side is empty */

  if (!count1) {

    while(count2--)

      env->xdf2.rchg[line2++ - 1] = 1;

    return 0;

  } else if (!count2) {

    while(count1--)

      env->xdf1.rchg[line1++ - 1] = 1;

    return 0;

  }

  memset(&map, 0, sizeof(map));

  if (fill_hashmap(xpp, env, &map,

      line1, count1, line2, count2))

    return -1;

  /* are there any matching lines at all? */

  if (!map.has_matches) {

    while(count1--)

      env->xdf1.rchg[line1++ - 1] = 1;

    while(count2--)

      env->xdf2.rchg[line2++ - 1] = 1;

    xdl_free(map.entries);

    return 0;

  }

  result = find_longest_common_sequence(&map, &first);

  if (result)

    goto out;

  if (first)

    result = walk_common_sequence(&map, first,

      line1, count1, line2, count2);

  else

    result = fall_back_to_classic_diff(&map,

      line1, count1, line2, count2);

 out:

  xdl_free(map.entries);

  return result;

}

int xdl_do_patience_diff(xpparam_t const *xpp, xdfenv_t *env)

{

  return patience_diff(xpp, env, 1, env->xdf1.nrec, 1, env->xdf2.nrec);

}