#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;
}