/*

 * Helper functions for tree diff generation

 */

#define DISABLE_SIGN_COMPARE_WARNINGS

#include "git-compat-util.h"

#include "diff.h"

#include "diffcore.h"

#include "hash.h"

#include "tree.h"

#include "tree-walk.h"

#include "repository.h"

#include "dir.h"

/*

 * Some mode bits are also used internally for computations.

 *

 * They *must* not overlap with any valid modes, and they *must* not be emitted

 * to outside world - i.e. appear on disk or network. In other words, it's just

 * temporary fields, which we internally use, but they have to stay in-house.

 *

 * ( such approach is valid, as standard S_IF* fits into 16 bits, and in Git

 *   codebase mode is `unsigned int` which is assumed to be at least 32 bits )

 */

#define S_DIFFTREE_IFXMIN_NEQ 0x80000000

/*

 * internal mode marker, saying a tree entry != entry of tp[imin]

 * (see ll_diff_tree_paths for what it means there)

 *

 * we will update/use/emit entry for diff only with it unset.

 */

#define S_IFXMIN_NEQ  S_DIFFTREE_IFXMIN_NEQ

#define FAST_ARRAY_ALLOC(x, nr) do { \

  if ((nr) <= 2) \

    (x) = xalloca((nr) * sizeof(*(x))); \

  else \

    ALLOC_ARRAY((x), nr); \

} while(0)

#define FAST_ARRAY_FREE(x, nr) do { \

  if ((nr) <= 2) \

    xalloca_free((x)); \

  else \

    free((x)); \

} while(0)

/* Returns true if and only if "dir" is a leading directory of "path" */

static int is_dir_prefix(const char *path, const char *dir, int dirlen)

{

  return !strncmp(path, dir, dirlen) &&

    (!path[dirlen] || path[dirlen] == '/');

}

static int check_recursion_depth(const struct strbuf *name,

         const struct pathspec *ps,

         int max_depth)

{

  int i;

  if (!ps->nr)

    return within_depth(name->buf, name->len, 1, max_depth);

  /*

   * We look through the pathspecs in reverse-sorted order, because we

   * want to find the longest match first (e.g., "a/b" is better for

   * checking depth than "a/b/c").

   */

  for (i = ps->nr - 1; i >= 0; i--) {

    const struct pathspec_item *item = ps->items+i;

    /*

     * If the name to match is longer than the pathspec, then we

     * are only interested if the pathspec matches and we are

     * within the allowed depth.

     */

    if (name->len >= item->len) {

      if (!is_dir_prefix(name->buf, item->match, item->len))

        continue;

      return within_depth(name->buf + item->len,

              name->len - item->len,

              1, max_depth);

    }

    /*

     * Otherwise, our name is shorter than the pathspec. We need to

     * check if it is a prefix of the pathspec; if so, we must

     * always recurse in order to process further (the resulting

     * paths we find might or might not match our pathspec, but we

     * cannot know until we recurse).

     */

    if (is_dir_prefix(item->match, name->buf, name->len))

      return 1;

  }

  return 0;

}

static int should_recurse(const struct strbuf *name, struct diff_options *opt)

{

  if (!opt->flags.recursive)

    return 0;

  if (!opt->max_depth_valid)

    return 1;

  /*

   * We catch this during diff_setup_done, but let's double-check

   * against any internal munging.

   */

  if (opt->pathspec.has_wildcard)

    BUG("wildcard pathspecs are incompatible with max-depth");

  return check_recursion_depth(name, &opt->pathspec, opt->max_depth);

}

static void ll_diff_tree_paths(

  struct combine_diff_path ***tail, const struct object_id *oid,

  const struct object_id **parents_oid, int nparent,

  struct strbuf *base, struct diff_options *opt,

  int depth);

static void ll_diff_tree_oid(const struct object_id *old_oid,

           const struct object_id *new_oid,

           struct strbuf *base, struct diff_options *opt);

/*

 * Compare two tree entries, taking into account only path/S_ISDIR(mode),

 * but not their sha1's.

 *

 * NOTE files and directories *always* compare differently, even when having

 *      the same name - thanks to base_name_compare().

 *

 * NOTE empty (=invalid) descriptor(s) take part in comparison as +infty,

 *      so that they sort *after* valid tree entries.

 *

 *      Due to this convention, if trees are scanned in sorted order, all

 *      non-empty descriptors will be processed first.

 */

static int tree_entry_pathcmp(struct tree_desc *t1, struct tree_desc *t2)

{

  struct name_entry *e1, *e2;

  int cmp;

  /* empty descriptors sort after valid tree entries */

  if (!t1->size)

    return t2->size ? 1 : 0;

  else if (!t2->size)

    return -1;

  e1 = &t1->entry;

  e2 = &t2->entry;

  cmp = base_name_compare(e1->path, tree_entry_len(e1), e1->mode,

        e2->path, tree_entry_len(e2), e2->mode);

  return cmp;

}

/*

 * convert path -> opt->diff_*() callbacks

 *

 * emits diff to first parent only, and tells diff tree-walker that we are done

 * with p and it can be freed.

 */

static int emit_diff_first_parent_only(struct diff_options *opt, struct combine_diff_path *p)

{

  struct combine_diff_parent *p0 = &p->parent[0];

  if (p->mode && p0->mode) {

    opt->change(opt, p0->mode, p->mode, &p0->oid, &p->oid,

      1, 1, p->path, 0, 0);

  }

  else {

    const struct object_id *oid;

    unsigned int mode;

    int addremove;

    if (p->mode) {

      addremove = '+';

      oid = &p->oid;

      mode = p->mode;

    } else {

      addremove = '-';

      oid = &p0->oid;

      mode = p0->mode;

    }

    opt->add_remove(opt, addremove, mode, oid, 1, p->path, 0);

  }

  return 0; /* we are done with p */

}

/*

 * new path should be added to combine diff

 *

 * 3 cases on how/when it should be called and behaves:

 *

 *   t, !tp   -> path added, all parents lack it

 *  !t,  tp   -> path removed from all parents

 *   t,  tp   -> path modified/added

 *         (M for tp[i]=tp[imin], A otherwise)

 */

static void emit_path(struct combine_diff_path ***tail,

          struct strbuf *base, struct diff_options *opt,

          int nparent, struct tree_desc *t, struct tree_desc *tp,

          int imin, int depth)

{

  unsigned short mode;

  const char *path;

  const struct object_id *oid;

  int pathlen;

  int old_baselen = base->len;

  int i, isdir, recurse = 0, emitthis = 1;

  /* at least something has to be valid */

  assert(t || tp);

  if (t) {

    /* path present in resulting tree */

    oid = tree_entry_extract(t, &path, &mode);

    pathlen = tree_entry_len(&t->entry);

    isdir = S_ISDIR(mode);

  } else {

    /*

     * a path was removed - take path from imin parent. Also take

     * mode from that parent, to decide on recursion(1).

     *

     * 1) all modes for tp[i]=tp[imin] should be the same wrt

     *    S_ISDIR, thanks to base_name_compare().

     */

    tree_entry_extract(&tp[imin], &path, &mode);

    pathlen = tree_entry_len(&tp[imin].entry);

    isdir = S_ISDIR(mode);

    oid = NULL;

    mode = 0;

  }

  if (isdir) {

    strbuf_add(base, path, pathlen);

    if (should_recurse(base, opt)) {

      recurse = 1;

      emitthis = opt->flags.tree_in_recursive;

    }

    strbuf_setlen(base, old_baselen);

  }

  if (emitthis) {

    int keep;

    struct combine_diff_path *p;

    strbuf_add(base, path, pathlen);

    p = combine_diff_path_new(base->buf, base->len, mode,

            oid ? oid : null_oid(opt->repo->hash_algo),

            nparent);

    strbuf_setlen(base, old_baselen);

    for (i = 0; i < nparent; ++i) {

      /*

       * tp[i] is valid, if present and if tp[i]==tp[imin] -

       * otherwise, we should ignore it.

       */

      int tpi_valid = tp && !(tp[i].entry.mode & S_IFXMIN_NEQ);

      const struct object_id *oid_i;

      unsigned mode_i;

      p->parent[i].status =

        !t ? DIFF_STATUS_DELETED :

          tpi_valid ?

            DIFF_STATUS_MODIFIED :

            DIFF_STATUS_ADDED;

      if (tpi_valid) {

        oid_i = &tp[i].entry.oid;

        mode_i = tp[i].entry.mode;

      }

      else {

        oid_i = null_oid(opt->repo->hash_algo);

        mode_i = 0;

      }

      p->parent[i].mode = mode_i;

      oidcpy(&p->parent[i].oid, oid_i);

    }

    keep = 1;

    if (opt->pathchange)

      keep = opt->pathchange(opt, p);

    if (keep) {

      **tail = p;

      *tail = &p->next;

    } else {

      free(p);

    }

  }

  if (recurse) {

    const struct object_id **parents_oid;

    FAST_ARRAY_ALLOC(parents_oid, nparent);

    for (i = 0; i < nparent; ++i) {

      /* same rule as in emitthis */

      int tpi_valid = tp && !(tp[i].entry.mode & S_IFXMIN_NEQ);

      parents_oid[i] = tpi_valid ? &tp[i].entry.oid : NULL;

    }

    strbuf_add(base, path, pathlen);

    strbuf_addch(base, '/');

    ll_diff_tree_paths(tail, oid, parents_oid, nparent, base, opt,

           depth + 1);

    FAST_ARRAY_FREE(parents_oid, nparent);

  }

  strbuf_setlen(base, old_baselen);

}

static void skip_uninteresting(struct tree_desc *t, struct strbuf *base,

             struct diff_options *opt)

{

  enum interesting match;

  while (t->size) {

    match = tree_entry_interesting(opt->repo->index, &t->entry,

                 base, &opt->pathspec);

    if (match) {

      if (match == all_entries_not_interesting)

        t->size = 0;

      break;

    }

    update_tree_entry(t);

  }

}

/*

 * generate paths for combined diff D(sha1,parents_oid[])

 *

 * Resulting paths are appended to combine_diff_path linked list, and also, are

 * emitted on the go via opt->pathchange() callback, so it is possible to

 * process the result as batch or incrementally.

 *

 * The paths are generated scanning new tree and all parents trees

 * simultaneously, similarly to what diff_tree() was doing for 2 trees.

 * The theory behind such scan is as follows:

 *

 *

 * D(T,P1...Pn) calculation scheme

 * -------------------------------

 *

 * D(T,P1...Pn) = D(T,P1) ^ ... ^ D(T,Pn) (regarding resulting paths set)

 *

 *  D(T,Pj)   - diff between T..Pj

 *  D(T,P1...Pn)  - combined diff from T to parents P1,...,Pn

 *

 *

 * We start from all trees, which are sorted, and compare their entries in

 * lock-step:

 *

 *   T     P1       Pn

 *   -     -        -

 *  |t|   |p1|     |pn|

 *  |-|   |--| ... |--|      imin = argmin(p1...pn)

 *  | |   |  |     |  |

 *  |-|   |--|     |--|

 *  |.|   |. |     |. |

 *   .     .        .

 *   .     .        .

 *

 * at any time there could be 3 cases:

 *

 *  1)  t < p[imin];

 *  2)  t > p[imin];

 *  3)  t = p[imin].

 *

 * Schematic deduction of what every case means, and what to do, follows:

 *

 * 1)  t < p[imin]  ->  ∀j t ∉ Pj  ->  "+t" ∈ D(T,Pj)  ->  D += "+t";  t↓

 *

 * 2)  t > p[imin]

 *

 *     2.1) ∃j: pj > p[imin]  ->  "-p[imin]" ∉ D(T,Pj)  ->  D += ø;  ∀ pi=p[imin]  pi↓

 *     2.2) ∀i  pi = p[imin]  ->  pi ∉ T  ->  "-pi" ∈ D(T,Pi)  ->  D += "-p[imin]";  ∀i pi↓

 *

 * 3)  t = p[imin]

 *

 *     3.1) ∃j: pj > p[imin]  ->  "+t" ∈ D(T,Pj)  ->  only pi=p[imin] remains to investigate

 *     3.2) pi = p[imin]  ->  investigate δ(t,pi)

 *      |

 *      |

 *      v

 *

 *     3.1+3.2) looking at δ(t,pi) ∀i: pi=p[imin] - if all != ø  ->

 *

 *                       ⎧δ(t,pi)  - if pi=p[imin]

 *              ->  D += ⎨

 *                       ⎩"+t"     - if pi>p[imin]

 *

 *

 *     in any case t↓  ∀ pi=p[imin]  pi↓

 *

 *

 * ~~~~~~~~

 *

 * NOTE

 *

 *  Usual diff D(A,B) is by definition the same as combined diff D(A,[B]),

 *  so this diff paths generator can, and is used, for plain diffs

 *  generation too.

 *

 *  Please keep attention to the common D(A,[B]) case when working on the

 *  code, in order not to slow it down.

 *

 * NOTE

 *  nparent must be > 0.

 */

/* ∀ pi=p[imin]  pi↓ */

static inline void update_tp_entries(struct tree_desc *tp, int nparent)

{

  int i;

  for (i = 0; i < nparent; ++i)

    if (!(tp[i].entry.mode & S_IFXMIN_NEQ))

      update_tree_entry(&tp[i]);

}

static void ll_diff_tree_paths(

  struct combine_diff_path ***tail, const struct object_id *oid,

  const struct object_id **parents_oid, int nparent,

  struct strbuf *base, struct diff_options *opt,

  int depth)

{

  struct tree_desc t, *tp;

  void *ttree, **tptree;

  int i;

  if (depth > opt->repo->settings.max_allowed_tree_depth)

    die("exceeded maximum allowed tree depth");

  FAST_ARRAY_ALLOC(tp, nparent);

  FAST_ARRAY_ALLOC(tptree, nparent);

  /*

   * load parents first, as they are probably already cached.

   *

   * ( log_tree_diff() parses commit->parent before calling here via

   *   diff_tree_oid(parent, commit) )

   */

  for (i = 0; i < nparent; ++i)

    tptree[i] = fill_tree_descriptor(opt->repo, &tp[i], parents_oid[i]);

  ttree = fill_tree_descriptor(opt->repo, &t, oid);

  /* Enable recursion indefinitely */

  opt->pathspec.recursive = opt->flags.recursive;

  for (;;) {

    int imin, cmp;

    if (diff_can_quit_early(opt))

      break;

    if (opt->max_changes && diff_queued_diff.nr > opt->max_changes)

      break;

    if (opt->pathspec.nr) {

      skip_uninteresting(&t, base, opt);

      for (i = 0; i < nparent; i++)

        skip_uninteresting(&tp[i], base, opt);

    }

    /* comparing is finished when all trees are done */

    if (!t.size) {

      int done = 1;

      for (i = 0; i < nparent; ++i)

        if (tp[i].size) {

          done = 0;

          break;

        }

      if (done)

        break;

    }

    /*

     * lookup imin = argmin(p1...pn),

     * mark entries whether they =p[imin] along the way

     */

    imin = 0;

    tp[0].entry.mode &= ~S_IFXMIN_NEQ;

    for (i = 1; i < nparent; ++i) {

      cmp = tree_entry_pathcmp(&tp[i], &tp[imin]);

      if (cmp < 0) {

        imin = i;

        tp[i].entry.mode &= ~S_IFXMIN_NEQ;

      }

      else if (cmp == 0) {

        tp[i].entry.mode &= ~S_IFXMIN_NEQ;

      }

      else {

        tp[i].entry.mode |= S_IFXMIN_NEQ;

      }

    }

    /* fixup markings for entries before imin */

    for (i = 0; i < imin; ++i)

      tp[i].entry.mode |= S_IFXMIN_NEQ; /* pi > p[imin] */

    /* compare t vs p[imin] */

    cmp = tree_entry_pathcmp(&t, &tp[imin]);

    /* t = p[imin] */

    if (cmp == 0) {

      /* are either pi > p[imin] or diff(t,pi) != ø ? */

      if (!opt->flags.find_copies_harder) {

        for (i = 0; i < nparent; ++i) {

          /* p[i] > p[imin] */

          if (tp[i].entry.mode & S_IFXMIN_NEQ)

            continue;

          /* diff(t,pi) != ø */

          if (!oideq(&t.entry.oid, &tp[i].entry.oid) ||

              (t.entry.mode != tp[i].entry.mode))

            continue;

          goto skip_emit_t_tp;

        }

      }

      /* D += {δ(t,pi) if pi=p[imin];  "+a" if pi > p[imin]} */

      emit_path(tail, base, opt, nparent,

          &t, tp, imin, depth);

    skip_emit_t_tp:

      /* t↓,  ∀ pi=p[imin]  pi↓ */

      update_tree_entry(&t);

      update_tp_entries(tp, nparent);

    }

    /* t < p[imin] */

    else if (cmp < 0) {

      /* D += "+t" */

      emit_path(tail, base, opt, nparent,

          &t, /*tp=*/NULL, -1, depth);

      /* t↓ */

      update_tree_entry(&t);

    }

    /* t > p[imin] */

    else {

      /* ∀i pi=p[imin] -> D += "-p[imin]" */

      if (!opt->flags.find_copies_harder) {

        for (i = 0; i < nparent; ++i)

          if (tp[i].entry.mode & S_IFXMIN_NEQ)

            goto skip_emit_tp;

      }

      emit_path(tail, base, opt, nparent,

          /*t=*/NULL, tp, imin, depth);

    skip_emit_tp:

      /* ∀ pi=p[imin]  pi↓ */

      update_tp_entries(tp, nparent);

    }

  }

  free(ttree);

  for (i = nparent-1; i >= 0; i--)

    free(tptree[i]);

  FAST_ARRAY_FREE(tptree, nparent);

  FAST_ARRAY_FREE(tp, nparent);

}

struct combine_diff_path *diff_tree_paths(

  const struct object_id *oid,

  const struct object_id **parents_oid, int nparent,

  struct strbuf *base, struct diff_options *opt)

{

  struct combine_diff_path *head = NULL, **tail = &head;

  ll_diff_tree_paths(&tail, oid, parents_oid, nparent, base, opt, 0);

  return head;

}

/*

 * Does it look like the resulting diff might be due to a rename?

 *  - single entry

 *  - not a valid previous file

 */

static inline int diff_might_be_rename(void)

{

  return diff_queued_diff.nr == 1 &&

    !DIFF_FILE_VALID(diff_queued_diff.queue[0]->one);

}

static void try_to_follow_renames(const struct object_id *old_oid,

          const struct object_id *new_oid,

          struct strbuf *base, struct diff_options *opt)

{

  struct diff_options diff_opts;

  struct diff_queue_struct *q = &diff_queued_diff;

  struct diff_filepair *choice;

  int i;

  /*

   * follow-rename code is very specific, we need exactly one

   * path. Magic that matches more than one path is not

   * supported.

   */

  GUARD_PATHSPEC(&opt->pathspec, PATHSPEC_FROMTOP | PATHSPEC_LITERAL);

#if 0

  /*

   * We should reject wildcards as well. Unfortunately we

   * haven't got a reliable way to detect that 'foo\*bar' in

   * fact has no wildcards. nowildcard_len is merely a hint for

   * optimization. Let it slip for now until wildmatch is taught

   * about dry-run mode and returns wildcard info.

   */

  if (opt->pathspec.has_wildcard)

    BUG("wildcards are not supported");

#endif

  /* Remove the file creation entry from the diff queue, and remember it */

  choice = q->queue[0];

  q->nr = 0;

  repo_diff_setup(opt->repo, &diff_opts);

  diff_opts.flags.recursive = 1;

  diff_opts.flags.find_copies_harder = 1;

  diff_opts.output_format = DIFF_FORMAT_NO_OUTPUT;

  diff_opts.single_follow = opt->pathspec.items[0].match;

  diff_opts.break_opt = opt->break_opt;

  diff_opts.rename_score = opt->rename_score;

  diff_setup_done(&diff_opts);

  ll_diff_tree_oid(old_oid, new_oid, base, &diff_opts);

  diffcore_std(&diff_opts);

  clear_pathspec(&diff_opts.pathspec);

  /* Go through the new set of filepairing, and see if we find a more interesting one */

  opt->found_follow = 0;

  for (i = 0; i < q->nr; i++) {

    struct diff_filepair *p = q->queue[i];

    /*

     * Found a source? Not only do we use that for the new

     * diff_queued_diff, we will also use that as the path in

     * the future!

     */

    if ((p->status == 'R' || p->status == 'C') &&

        !strcmp(p->two->path, opt->pathspec.items[0].match)) {

      const char *path[2];

      /* Switch the file-pairs around */

      q->queue[i] = choice;

      choice = p;

      /* Update the path we use from now on.. */

      path[0] = p->one->path;

      path[1] = NULL;

      clear_pathspec(&opt->pathspec);

      parse_pathspec(&opt->pathspec,

               PATHSPEC_ALL_MAGIC & ~PATHSPEC_LITERAL,

               PATHSPEC_LITERAL_PATH, "", path);

      /*

       * The caller expects us to return a set of vanilla

       * filepairs to let a later call to diffcore_std()

       * it makes to sort the renames out (among other

       * things), but we already have found renames

       * ourselves; signal diffcore_std() not to muck with

       * rename information.

       */

      opt->found_follow = 1;

      break;

    }

  }

  /*

   * Then, discard all the non-relevant file pairs...

   */

  for (i = 0; i < q->nr; i++) {

    struct diff_filepair *p = q->queue[i];

    diff_free_filepair(p);

  }

  /*

   * .. and re-instate the one we want (which might be either the

   * original one, or the rename/copy we found)

   */

  q->queue[0] = choice;

  q->nr = 1;

}

static void ll_diff_tree_oid(const struct object_id *old_oid,

           const struct object_id *new_oid,

           struct strbuf *base, struct diff_options *opt)

{

  struct combine_diff_path *paths, *p;

  pathchange_fn_t pathchange_old = opt->pathchange;

  opt->pathchange = emit_diff_first_parent_only;

  paths = diff_tree_paths(new_oid, &old_oid, 1, base, opt);

  for (p = paths; p;) {

    struct combine_diff_path *pprev = p;

    p = p->next;

    free(pprev);

  }

  opt->pathchange = pathchange_old;

}

void diff_tree_oid(const struct object_id *old_oid,

       const struct object_id *new_oid,

       const char *base_str, struct diff_options *opt)

{

  struct strbuf base;

  strbuf_init(&base, PATH_MAX);

  strbuf_addstr(&base, base_str);

  ll_diff_tree_oid(old_oid, new_oid, &base, opt);

  if (!*base_str && opt->flags.follow_renames && diff_might_be_rename())

    try_to_follow_renames(old_oid, new_oid, &base, opt);

  strbuf_release(&base);

}

void diff_root_tree_oid(const struct object_id *new_oid,

      const char *base,

      struct diff_options *opt)

{

  diff_tree_oid(NULL, new_oid, base, opt);

}