#include "../git-compat-util.h"

#include "../hash.h"

#include "../refs.h"

#include "../repository.h"

#include "refs-internal.h"

#include "ref-cache.h"

#include "../iterator.h"

void add_entry_to_dir(struct ref_dir *dir, struct ref_entry *entry)

{

  ALLOC_GROW(dir->entries, dir->nr + 1, dir->alloc);

  dir->entries[dir->nr++] = entry;

  /* optimize for the case that entries are added in order */

  if (dir->nr == 1 ||

      (dir->nr == dir->sorted + 1 &&

       strcmp(dir->entries[dir->nr - 2]->name,

        dir->entries[dir->nr - 1]->name) < 0))

    dir->sorted = dir->nr;

}

struct ref_dir *get_ref_dir(struct ref_entry *entry)

{

  struct ref_dir *dir;

  assert(entry->flag & REF_DIR);

  dir = &entry->u.subdir;

  if (entry->flag & REF_INCOMPLETE) {

    if (!dir->cache->fill_ref_dir)

      BUG("incomplete ref_store without fill_ref_dir function");

    dir->cache->fill_ref_dir(dir->cache->ref_store, dir, entry->name);

    entry->flag &= ~REF_INCOMPLETE;

  }

  return dir;

}

struct ref_entry *create_ref_entry(const char *refname,

           const char *referent,

           const struct object_id *oid, int flag)

{

  struct ref_entry *ref;

  FLEX_ALLOC_STR(ref, name, refname);

  oidcpy(&ref->u.value.oid, oid);

  ref->flag = flag;

  ref->u.value.referent = xstrdup_or_null(referent);

  return ref;

}

struct ref_cache *create_ref_cache(struct ref_store *refs,

           fill_ref_dir_fn *fill_ref_dir)

{

  struct ref_cache *ret = xcalloc(1, sizeof(*ret));

  ret->ref_store = refs;

  ret->fill_ref_dir = fill_ref_dir;

  ret->root = create_dir_entry(ret, "", 0);

  return ret;

}

static void clear_ref_dir(struct ref_dir *dir);

static void free_ref_entry(struct ref_entry *entry)

{

  if (entry->flag & REF_DIR) {

    /*

     * Do not use get_ref_dir() here, as that might

     * trigger the reading of loose refs.

     */

    clear_ref_dir(&entry->u.subdir);

  } else {

    free(entry->u.value.referent);

  }

  free(entry);

}

void free_ref_cache(struct ref_cache *cache)

{

  if (!cache)

    return;

  free_ref_entry(cache->root);

  free(cache);

}

/*

 * Clear and free all entries in dir, recursively.

 */

static void clear_ref_dir(struct ref_dir *dir)

{

  int i;

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

    free_ref_entry(dir->entries[i]);

  FREE_AND_NULL(dir->entries);

  dir->sorted = dir->nr = dir->alloc = 0;

}

struct ref_entry *create_dir_entry(struct ref_cache *cache,

           const char *dirname, size_t len)

{

  struct ref_entry *direntry;

  FLEX_ALLOC_MEM(direntry, name, dirname, len);

  direntry->u.subdir.cache = cache;

  direntry->flag = REF_DIR | REF_INCOMPLETE;

  return direntry;

}

static int ref_entry_cmp(const void *a, const void *b)

{

  struct ref_entry *one = *(struct ref_entry **)a;

  struct ref_entry *two = *(struct ref_entry **)b;

  return strcmp(one->name, two->name);

}

static void sort_ref_dir(struct ref_dir *dir);

struct string_slice {

  size_t len;

  const char *str;

};

static int ref_entry_cmp_sslice(const void *key_, const void *ent_)

{

  const struct string_slice *key = key_;

  const struct ref_entry *ent = *(const struct ref_entry * const *)ent_;

  int cmp = strncmp(key->str, ent->name, key->len);

  if (cmp)

    return cmp;

  return '\0' - (unsigned char)ent->name[key->len];

}

int search_ref_dir(struct ref_dir *dir, const char *refname, size_t len)

{

  struct ref_entry **r;

  struct string_slice key;

  if (refname == NULL || !dir->nr)

    return -1;

  sort_ref_dir(dir);

  key.len = len;

  key.str = refname;

  r = bsearch(&key, dir->entries, dir->nr, sizeof(*dir->entries),

        ref_entry_cmp_sslice);

  if (!r)

    return -1;

  return r - dir->entries;

}

/*

 * Search for a directory entry directly within dir (without

 * recursing).  Sort dir if necessary.  subdirname must be a directory

 * name (i.e., end in '/'). Returns NULL if the desired

 * directory cannot be found.  dir must already be complete.

 */

static struct ref_dir *search_for_subdir(struct ref_dir *dir,

           const char *subdirname, size_t len)

{

  int entry_index = search_ref_dir(dir, subdirname, len);

  struct ref_entry *entry;

  if (entry_index == -1)

    return NULL;

  entry = dir->entries[entry_index];

  return get_ref_dir(entry);

}

/*

 * If refname is a reference name, find the ref_dir within the dir

 * tree that should hold refname. If refname is a directory name

 * (i.e., it ends in '/'), then return that ref_dir itself. dir must

 * represent the top-level directory and must already be complete.

 * Sort ref_dirs and recurse into subdirectories as necessary. Will

 * return NULL if the desired directory cannot be found.

 */

static struct ref_dir *find_containing_dir(struct ref_dir *dir,

             const char *refname)

{

  const char *slash;

  for (slash = strchr(refname, '/'); slash; slash = strchr(slash + 1, '/')) {

    size_t dirnamelen = slash - refname + 1;

    struct ref_dir *subdir;

    subdir = search_for_subdir(dir, refname, dirnamelen);

    if (!subdir) {

      dir = NULL;

      break;

    }

    dir = subdir;

  }

  return dir;

}

/*

 * Emit a warning and return true iff ref1 and ref2 have the same name

 * and the same oid. Die if they have the same name but different

 * oids.

 */

static int is_dup_ref(const struct ref_entry *ref1, const struct ref_entry *ref2)

{

  if (strcmp(ref1->name, ref2->name))

    return 0;

  /* Duplicate name; make sure that they don't conflict: */

  if ((ref1->flag & REF_DIR) || (ref2->flag & REF_DIR))

    /* This is impossible by construction */

    die("Reference directory conflict: %s", ref1->name);

  if (!oideq(&ref1->u.value.oid, &ref2->u.value.oid))

    die("Duplicated ref, and SHA1s don't match: %s", ref1->name);

  warning("Duplicated ref: %s", ref1->name);

  return 1;

}

/*

 * Sort the entries in dir non-recursively (if they are not already

 * sorted) and remove any duplicate entries.

 */

static void sort_ref_dir(struct ref_dir *dir)

{

  int i, j;

  struct ref_entry *last = NULL;

  /*

   * This check also prevents passing a zero-length array to qsort(),

   * which is a problem on some platforms.

   */

  if (dir->sorted == dir->nr)

    return;

  QSORT(dir->entries, dir->nr, ref_entry_cmp);

  /* Remove any duplicates: */

  for (i = 0, j = 0; j < dir->nr; j++) {

    struct ref_entry *entry = dir->entries[j];

    if (last && is_dup_ref(last, entry))

      free_ref_entry(entry);

    else

      last = dir->entries[i++] = entry;

  }

  dir->sorted = dir->nr = i;

}

enum prefix_state {

  /* All refs within the directory would match prefix: */

  PREFIX_CONTAINS_DIR,

  /* Some, but not all, refs within the directory might match prefix: */

  PREFIX_WITHIN_DIR,

  /* No refs within the directory could possibly match prefix: */

  PREFIX_EXCLUDES_DIR

};

/*

 * Return a `prefix_state` constant describing the relationship

 * between the directory with the specified `dirname` and `prefix`.

 */

static enum prefix_state overlaps_prefix(const char *dirname,

           const char *prefix)

{

  while (*prefix && *dirname == *prefix) {

    dirname++;

    prefix++;

  }

  if (!*prefix)

    return PREFIX_CONTAINS_DIR;

  else if (!*dirname)

    return PREFIX_WITHIN_DIR;

  else

    return PREFIX_EXCLUDES_DIR;

}

/*

 * Load all of the refs from `dir` (recursively) that could possibly

 * contain references matching `prefix` into our in-memory cache. If

 * `prefix` is NULL, prime unconditionally.

 */

static void prime_ref_dir(struct ref_dir *dir, const char *prefix)

{

  /*

   * The hard work of loading loose refs is done by get_ref_dir(), so we

   * just need to recurse through all of the sub-directories. We do not

   * even need to care about sorting, as traversal order does not matter

   * to us.

   */

  int i;

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

    struct ref_entry *entry = dir->entries[i];

    if (!(entry->flag & REF_DIR)) {

      /* Not a directory; no need to recurse. */

    } else if (!prefix) {

      /* Recurse in any case: */

      prime_ref_dir(get_ref_dir(entry), NULL);

    } else {

      switch (overlaps_prefix(entry->name, prefix)) {

      case PREFIX_CONTAINS_DIR:

        /*

         * Recurse, and from here down we

         * don't have to check the prefix

         * anymore:

         */

        prime_ref_dir(get_ref_dir(entry), NULL);

        break;

      case PREFIX_WITHIN_DIR:

        prime_ref_dir(get_ref_dir(entry), prefix);

        break;

      case PREFIX_EXCLUDES_DIR:

        /* No need to prime this directory. */

        break;

      }

    }

  }

}

/*

 * A level in the reference hierarchy that is currently being iterated

 * through.

 */

struct cache_ref_iterator_level {

  /*

   * The ref_dir being iterated over at this level. The ref_dir

   * is sorted before being stored here.

   */

  struct ref_dir *dir;

  enum prefix_state prefix_state;

  /*

   * The index of the current entry within dir (which might

   * itself be a directory). If index == -1, then the iteration

   * hasn't yet begun. If index == dir->nr, then the iteration

   * through this level is over.

   */

  int index;

};

/*

 * Represent an iteration through a ref_dir in the memory cache. The

 * iteration recurses through subdirectories.

 */

struct cache_ref_iterator {

  struct ref_iterator base;

  /*

   * The number of levels currently on the stack.

   */

  size_t levels_nr;

  /* The number of levels that have been allocated on the stack */

  size_t levels_alloc;

  /*

   * Only include references with this prefix in the iteration.

   * The prefix is matched textually, without regard for path

   * component boundaries.

   */

  char *prefix;

  /*

   * A stack of levels. levels[0] is the uppermost level that is

   * being iterated over in this iteration. (This is not

   * necessary the top level in the references hierarchy. If we

   * are iterating through a subtree, then levels[0] will hold

   * the ref_dir for that subtree, and subsequent levels will go

   * on from there.)

   */

  struct cache_ref_iterator_level *levels;

  struct repository *repo;

  struct ref_cache *cache;

  int prime_dir;

};

static int cache_ref_iterator_advance(struct ref_iterator *ref_iterator)

{

  struct cache_ref_iterator *iter =

    (struct cache_ref_iterator *)ref_iterator;

  if (!iter->levels_nr)

    return ITER_DONE;

  while (1) {

    struct cache_ref_iterator_level *level =

      &iter->levels[iter->levels_nr - 1];

    struct ref_dir *dir = level->dir;

    struct ref_entry *entry;

    enum prefix_state entry_prefix_state;

    if (level->index == -1)

      sort_ref_dir(dir);

    if (++level->index == level->dir->nr) {

      /* This level is exhausted; pop up a level */

      if (--iter->levels_nr == 0)

        return ITER_DONE;

      continue;

    }

    entry = dir->entries[level->index];

    if (level->prefix_state == PREFIX_WITHIN_DIR) {

      entry_prefix_state = overlaps_prefix(entry->name, iter->prefix);

      if (entry_prefix_state == PREFIX_EXCLUDES_DIR ||

          (entry_prefix_state == PREFIX_WITHIN_DIR && !(entry->flag & REF_DIR)))

        continue;

    } else {

      entry_prefix_state = level->prefix_state;

    }

    if (entry->flag & REF_DIR) {

      /* push down a level */

      ALLOC_GROW(iter->levels, iter->levels_nr + 1,

           iter->levels_alloc);

      level = &iter->levels[iter->levels_nr++];

      level->dir = get_ref_dir(entry);

      level->prefix_state = entry_prefix_state;

      level->index = -1;

    } else {

      memset(&iter->base.ref, 0, sizeof(iter->base.ref));

      iter->base.ref.name = entry->name;

      iter->base.ref.target = entry->u.value.referent;

      iter->base.ref.oid = &entry->u.value.oid;

      iter->base.ref.flags = entry->flag;

      return ITER_OK;

    }

  }

}

static int cache_ref_iterator_set_prefix(struct cache_ref_iterator *iter,

           const char *prefix)

{

  struct cache_ref_iterator_level *level;

  struct ref_dir *dir;

  dir = get_ref_dir(iter->cache->root);

  if (prefix && *prefix)

    dir = find_containing_dir(dir, prefix);

  if (!dir) {

    iter->levels_nr = 0;

    return 0;

  }

  if (iter->prime_dir)

    prime_ref_dir(dir, prefix);

  iter->levels_nr = 1;

  level = &iter->levels[0];

  level->index = -1;

  level->dir = dir;

  if (prefix && *prefix) {

    free(iter->prefix);

    iter->prefix = xstrdup(prefix);

    level->prefix_state = PREFIX_WITHIN_DIR;

  } else {

    FREE_AND_NULL(iter->prefix);

    level->prefix_state = PREFIX_CONTAINS_DIR;

  }

  return 0;

}

static int cache_ref_iterator_seek(struct ref_iterator *ref_iterator,

           const char *refname, unsigned int flags)

{

  struct cache_ref_iterator *iter =

    (struct cache_ref_iterator *)ref_iterator;

  if (flags & REF_ITERATOR_SEEK_SET_PREFIX) {

    return cache_ref_iterator_set_prefix(iter, refname);

  } else if (refname && *refname) {

    struct cache_ref_iterator_level *level;

    const char *slash = refname;

    struct ref_dir *dir;

    dir = get_ref_dir(iter->cache->root);

    if (iter->prime_dir)

      prime_ref_dir(dir, refname);

    iter->levels_nr = 1;

    level = &iter->levels[0];

    level->index = -1;

    level->dir = dir;

    /* Unset any previously set prefix */

    FREE_AND_NULL(iter->prefix);

    /*

     * Breakdown the provided seek path and assign the correct

     * indexing to each level as needed.

     */

    do {

      int idx;

      size_t len;

      int cmp = 0;

      sort_ref_dir(dir);

      slash = strchr(slash, '/');

      len = slash ? (size_t)(slash - refname) : strlen(refname);

      for (idx = 0; idx < dir->nr; idx++) {

        cmp = strncmp(refname, dir->entries[idx]->name, len);

        if (cmp <= 0)

          break;

      }

      /* don't overflow the index */

      idx = idx >= dir->nr ? dir->nr - 1 : idx;

      if (slash)

        slash = slash + 1;

      level->index = idx;

      if (dir->entries[idx]->flag & REF_DIR) {

        /* push down a level */

        dir = get_ref_dir(dir->entries[idx]);

        ALLOC_GROW(iter->levels, iter->levels_nr + 1,

             iter->levels_alloc);

        level = &iter->levels[iter->levels_nr++];

        level->dir = dir;

        level->index = -1;

        level->prefix_state = PREFIX_CONTAINS_DIR;

      } else {

        /* reduce the index so the leaf node is iterated over */

        if (cmp <= 0 && !slash)

          level->index = idx - 1;

        /*

         * while the seek path may not be exhausted, our

         * match is exhausted at a leaf node.

         */

        break;

      }

    } while (slash && dir->nr);

  }

  return 0;

}

static void cache_ref_iterator_release(struct ref_iterator *ref_iterator)

{

  struct cache_ref_iterator *iter =

    (struct cache_ref_iterator *)ref_iterator;

  free(iter->prefix);

  free(iter->levels);

}

static struct ref_iterator_vtable cache_ref_iterator_vtable = {

  .advance = cache_ref_iterator_advance,

  .seek = cache_ref_iterator_seek,

  .release = cache_ref_iterator_release,

};

struct ref_iterator *cache_ref_iterator_begin(struct ref_cache *cache,

                const char *prefix,

                struct repository *repo,

                int prime_dir)

{

  struct cache_ref_iterator *iter;

  struct ref_iterator *ref_iterator;

  CALLOC_ARRAY(iter, 1);

  ref_iterator = &iter->base;

  base_ref_iterator_init(ref_iterator, &cache_ref_iterator_vtable);

  ALLOC_GROW(iter->levels, 10, iter->levels_alloc);

  iter->repo = repo;

  iter->cache = cache;

  iter->prime_dir = prime_dir;

  if (cache_ref_iterator_seek(&iter->base, prefix,

            REF_ITERATOR_SEEK_SET_PREFIX) < 0) {

    ref_iterator_free(&iter->base);

    return NULL;

  }

  return ref_iterator;

}