path: root/gsk/gskdiff.c

/*
 * Copyright © 2003 Davide Libenzi
 *             2018 Benjamin Otte
 *
 * 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/>.
 *
 * Authors: Davide Libenzi <davidel@xmailserver.org>
 *          Benjamin Otte <otte@gnome.org>
 */

#include "config.h"

#include "gskdiffprivate.h"


#define XDL_MAX_COST_MIN 256
#define XDL_HEUR_MIN_COST 256
#define XDL_LINE_MAX G_MAXSSIZE
#define XDL_SNAKE_CNT 20
#define XDL_K_HEUR 4
#define MAXCOST 20

struct _GskDiffSettings {
  GCompareDataFunc        compare_func;
  GskKeepFunc             keep_func;
  GskDeleteFunc           delete_func;
  GskInsertFunc           insert_func;

  guint allow_abort : 1;
};

typedef struct _SplitResult {
  long i1, i2;
  int min_lo, min_hi;
} SplitResult;

GskDiffSettings *
gsk_diff_settings_new (GCompareDataFunc compare_func,
                       GskKeepFunc      keep_func,
                       GskDeleteFunc    delete_func,
                       GskInsertFunc    insert_func)
{
  GskDiffSettings *settings;

  settings = g_new0 (GskDiffSettings, 1);

  settings->compare_func = compare_func;
  settings->keep_func = keep_func;
  settings->delete_func = delete_func;
  settings->insert_func = insert_func;

  return settings;
}

void
gsk_diff_settings_set_allow_abort (GskDiffSettings *settings,
                                   gboolean         allow_abort)
{
  settings->allow_abort = allow_abort;
}

void
gsk_diff_settings_free (GskDiffSettings *settings)
{
  g_free (settings);
}

/*
 * See "An O(ND) Difference Algorithm and its Variations", by Eugene Myers.
 * Basically considers a "box" (off1, off2, lim1, lim2) and scan from both
 * the forward diagonal starting from (off1, off2) and the backward diagonal
 * starting from (lim1, lim2). If the K values on the same diagonal crosses
 * returns the furthest point of reach. We might end up having to expensive
 * cases using this algorithm is full, so a little bit of heuristic is needed
 * to cut the search and to return a suboptimal point.
 */
static GskDiffResult
split (gconstpointer         *elem1,
       gssize                 off1,
       gssize                 lim1,
       gconstpointer         *elem2,
       gssize                 off2,
       gssize                 lim2,
       gssize                *kvdf,
       gssize                *kvdb,
       gboolean               need_min,
       const GskDiffSettings *settings,
       gpointer               data,
       SplitResult           *spl)
{
  gssize dmin = off1 - lim2, dmax = lim1 - off2;
  gssize fmid = off1 - off2, bmid = lim1 - lim2;
  gboolean odd = (fmid - bmid) & 1;
  gssize fmin = fmid, fmax = fmid;
  gssize bmin = bmid, bmax = bmid;
  gssize ec, d, i1, i2, prev1, best, dd, v, k;

  /*
   * Set initial diagonal values for both forward and backward path.
   */
  kvdf[fmid] = off1;
  kvdb[bmid] = lim1;

  for (ec = 1;; ec++)
    {
      gboolean got_snake = FALSE;

      /*
       * We need to extent the diagonal "domain" by one. If the next
       * values exits the box boundaries we need to change it in the
       * opposite direction because (max - min) must be a power of two.
       * Also we initialize the external K value to -1 so that we can
       * avoid extra conditions check inside the core loop.
       */
      if (fmin > dmin)
        kvdf[--fmin - 1] = -1;
      else
        ++fmin;
      if (fmax < dmax)
        kvdf[++fmax + 1] = -1;
      else
        --fmax;

      for (d = fmax; d >= fmin; d -= 2)
        {
          if (kvdf[d - 1] >= kvdf[d + 1])
            i1 = kvdf[d - 1] + 1;
          else
            i1 = kvdf[d + 1];
          prev1 = i1;
          i2 = i1 - d;
          for (; i1 < lim1 && i2 < lim2; i1++, i2++)
            {
              if (settings->compare_func (elem1[i1], elem2[i2], data) != 0)
                break;
            }
          if (i1 - prev1 > XDL_SNAKE_CNT)
            got_snake = TRUE;
          kvdf[d] = i1;
          if (odd && bmin <= d && d <= bmax && kvdb[d] <= i1)
            {
              spl->i1 = i1;
              spl->i2 = i2;
              spl->min_lo = spl->min_hi = 1;
              return GSK_DIFF_OK;
            }
        }

      /*
       * We need to extent the diagonal "domain" by one. If the next
       * values exits the box boundaries we need to change it in the
       * opposite direction because (max - min) must be a power of two.
       * Also we initialize the external K value to -1 so that we can
       * avoid extra conditions check inside the core loop.
       */
      if (bmin > dmin)
        kvdb[--bmin - 1] = XDL_LINE_MAX;
      else
        ++bmin;
      if (bmax < dmax)
        kvdb[++bmax + 1] = XDL_LINE_MAX;
      else
        --bmax;

      for (d = bmax; d >= bmin; d -= 2)
        {
          if (kvdb[d - 1] < kvdb[d + 1])
            i1 = kvdb[d - 1];
          else
            i1 = kvdb[d + 1] - 1;
          prev1 = i1;
          i2 = i1 - d;
          for (; i1 > off1 && i2 > off2; i1--, i2--)
            {
              if (settings->compare_func (elem1[i1 - 1], elem2[i2 - 1], data) != 0)
                break;
            }
          if (prev1 - i1 > XDL_SNAKE_CNT)
            got_snake = TRUE;
          kvdb[d] = i1;
          if (!odd && fmin <= d && d <= fmax && i1 <= kvdf[d])
            {
              spl->i1 = i1;
              spl->i2 = i2;
              spl->min_lo = spl->min_hi = 1;
              return GSK_DIFF_OK;
            }
        }

      if (need_min)
        continue;

      /*
       * If the edit cost is above the heuristic trigger and if
       * we got a good snake, we sample current diagonals to see
       * if some of them have reached an "interesting" path. Our
       * measure is a function of the distance from the diagonal
       * corner (i1 + i2) penalized with the distance from the
       * mid diagonal itself. If this value is above the current
       * edit cost times a magic factor (XDL_K_HEUR) we consider
       * it interesting.
       */
      if (got_snake && ec > XDL_HEUR_MIN_COST)
        {
          for (best = 0, d = fmax; d >= fmin; d -= 2)
            {
              dd = d > fmid ? d - fmid: fmid - d;
              i1 = kvdf[d];
              i2 = i1 - d;
              v = (i1 - off1) + (i2 - off2) - dd;

              if (v > XDL_K_HEUR * ec && v > best &&
                  off1 + XDL_SNAKE_CNT <= i1 && i1 < lim1 &&
                  off2 + XDL_SNAKE_CNT <= i2 && i2 < lim2)
                {
                  for (k = 1; ; k++)
                    {
                      if (settings->compare_func (elem1[i1 - k], elem2[i2 - k], data) != 0)
                        break;
                      if (k == XDL_SNAKE_CNT)
                        {
                          best = v;
                          spl->i1 = i1;
                          spl->i2 = i2;
                          break;
                        }
                    }
                }
            }
          if (best > 0)
            {
              spl->min_lo = 1;
              spl->min_hi = 0;
              return GSK_DIFF_OK;
            }

          for (best = 0, d = bmax; d >= bmin; d -= 2)
            {
              dd = d > bmid ? d - bmid: bmid - d;
              i1 = kvdb[d];
              i2 = i1 - d;
              v = (lim1 - i1) + (lim2 - i2) - dd;

              if (v > XDL_K_HEUR * ec && v > best &&
                  off1 < i1 && i1 <= lim1 - XDL_SNAKE_CNT &&
                  off2 < i2 && i2 <= lim2 - XDL_SNAKE_CNT)
                {
                  for (k = 0; ; k++)
                    {
                      if (settings->compare_func (elem1[i1 + k], elem2[i2 + k], data) != 0)
                        break;

                      if (k == XDL_SNAKE_CNT - 1)
                        {
                          best = v;
                          spl->i1 = i1;
                          spl->i2 = i2;
                          break;
                        }
                    }
                }
            }
          if (best > 0)
            {
              spl->min_lo = 0;
              spl->min_hi = 1;
              return GSK_DIFF_OK;
            }
        }

      /*
       * Enough is enough. We spent too much time here and now we collect
       * the furthest reaching path using the (i1 + i2) measure.
       */
      if (ec >= MAXCOST)
        {
          gssize fbest, fbest1, bbest, bbest1;

          if (settings->allow_abort)
            return GSK_DIFF_ABORTED;

          fbest = fbest1 = -1;
          for (d = fmax; d >= fmin; d -= 2)
            {
              i1 = MIN (kvdf[d], lim1);
              i2 = i1 - d;
              if (lim2 < i2)
                i1 = lim2 + d, i2 = lim2;
              if (fbest < i1 + i2)
                {
                  fbest = i1 + i2;
                  fbest1 = i1;
                }
            }

          bbest = bbest1 = XDL_LINE_MAX;
          for (d = bmax; d >= bmin; d -= 2)
            {
              i1 = MAX (off1, kvdb[d]);
              i2 = i1 - d;
              if (i2 < off2)
                i1 = off2 + d, i2 = off2;
              if (i1 + i2 < bbest)
                {
                  bbest = i1 + i2;
                  bbest1 = i1;
                }
            }

          if ((lim1 + lim2) - bbest < fbest - (off1 + off2))
            {
              spl->i1 = fbest1;
              spl->i2 = fbest - fbest1;
              spl->min_lo = 1;
              spl->min_hi = 0;
            }
          else
            {
              spl->i1 = bbest1;
              spl->i2 = bbest - bbest1;
              spl->min_lo = 0;
              spl->min_hi = 1;
            }

          return GSK_DIFF_OK;
        }
    }
}

/*
 * Rule: "Divide et Impera". Recursively split the box in sub-boxes by calling
 * the box splitting function. Note that the real job (marking changed lines)
 * is done in the two boundary reaching checks.
 */
static GskDiffResult
compare (gconstpointer             *elem1,
         gssize                     off1,
         gssize                     lim1,
         gconstpointer             *elem2,
         gssize                     off2,
         gssize                     lim2,
         gssize                    *kvdf,
         gssize                    *kvdb,
         gboolean                   need_min,
         const GskDiffSettings     *settings,
         gpointer                   data)
{
  GskDiffResult res;

  /*
   * Shrink the box by walking through each diagonal snake (SW and NE).
   */
  for (; off1 < lim1 && off2 < lim2; off1++, off2++)
    {
      if (settings->compare_func (elem1[off1], elem2[off2], data) != 0)
        break;

      res = settings->keep_func (elem1[off1], elem2[off2], data);
      if (res != GSK_DIFF_OK)
        return res;
    }

  for (; off1 < lim1 && off2 < lim2; lim1--, lim2--)
    {
      if (settings->compare_func (elem1[lim1 - 1], elem2[lim2 - 1], data) != 0)
        break;

      res = settings->keep_func (elem1[lim1 - 1], elem2[lim2 - 1], data);
      if (res != GSK_DIFF_OK)
        return res;
    }

  /*
   * If one dimension is empty, then all records on the other one must
   * be obviously changed.
   */
  if (off1 == lim1)
    {
      for (; off2 < lim2; off2++)
        {
          res = settings->insert_func (elem2[off2], off2, data);
          if (res != GSK_DIFF_OK)
            return res;
        }
    }
  else if (off2 == lim2)
    {
      for (; off1 < lim1; off1++)
        {
          res = settings->delete_func (elem1[off1], off1, data);
          if (res != GSK_DIFF_OK)
            return res;
        }
    }
  else
    {
      SplitResult spl = { 0, };

      /*
       * Divide ...
       */
      res = split (elem1, off1, lim1,
                   elem2, off2, lim2,
                   kvdf, kvdb, need_min,
                   settings, data,
                   &spl);
      if (res != GSK_DIFF_OK)
        return res;

      /*
       * ... et Impera.
       */
      res = compare (elem1, off1, spl.i1,
                     elem2, off2, spl.i2,
                     kvdf, kvdb, spl.min_lo,
                     settings, data);
      if (res != GSK_DIFF_OK)
        return res;
      res = compare (elem1, spl.i1, lim1,
                     elem2, spl.i2, lim2,
                     kvdf, kvdb, spl.min_hi,
                     settings, data);
      if (res != GSK_DIFF_OK)
        return res;
    }

  return GSK_DIFF_OK;
}

#if 0
  ndiags = xe->xdf1.nreff + xe->xdf2.nreff + 3;
  if (!(kvd = (long *) xdl_malloc((2 * ndiags + 2) * sizeof(long)))) {

    xdl_free_env(xe);
    return -1;
  }
  kvdf = kvd;
  kvdb = kvdf + ndiags;
  kvdf += xe->xdf2.nreff + 1;
  kvdb += xe->xdf2.nreff + 1;

  xenv.mxcost = xdl_bogosqrt(ndiags);
  if (xenv.mxcost < XDL_MAX_COST_MIN)
    xenv.mxcost = XDL_MAX_COST_MIN;
  xenv.snake_cnt = XDL_SNAKE_CNT;
  xenv.heur_min = XDL_HEUR_MIN_COST;

  dd1.nrec = xe->xdf1.nreff;
  dd1.ha = xe->xdf1.ha;
  dd1.rchg = xe->xdf1.rchg;
  dd1.rindex = xe->xdf1.rindex;
  dd2.nrec = xe->xdf2.nreff;
  dd2.ha = xe->xdf2.ha;
  dd2.rchg = xe->xdf2.rchg;
  dd2.rindex = xe->xdf2.rindex;
#endif

GskDiffResult
gsk_diff (gconstpointer             *elem1,
          gsize                      n1,
          gconstpointer             *elem2,
          gsize                      n2,
          const GskDiffSettings     *settings,
          gpointer                   data)
{
  gsize ndiags;
  gssize *kvd, *kvdf, *kvdb;
  GskDiffResult res;

  ndiags = n1 + n2 + 3;

  kvd = g_new (gssize, 2 * ndiags + 2);
  kvdf = kvd;
  kvdb = kvd + ndiags;
  kvdf += n2 + 1;
  kvdb += n2 + 1;

  res = compare (elem1, 0, n1,
                 elem2, 0, n2,
                 kvdf, kvdb, FALSE,
                 settings, data);

  g_free (kvd);

  return res;
}