[PATCH 03/12] Introduce sparse prefix

["Nguyễn Thái Ngọc Duy" <pclouds@gmail.com>]

Sparse prefix is actually a list of prefixes separated by colons,
that will limit worktree usage within it.

This patch adds core.sparsecheckout and
"git rev-parse --show-sparse-prefix". This also adds manipulation
functions that will get used later.

Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 builtin-rev-parse.c |    4 +
 cache.h             |   13 +++
 config.c            |    7 ++
 environment.c       |  221 +++++++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 245 insertions(+), 0 deletions(-)

diff --git a/builtin-rev-parse.c b/builtin-rev-parse.c
index aa71f4a..4200f14 100644
--- a/builtin-rev-parse.c
+++ b/builtin-rev-parse.c
@@ -499,6 +499,10 @@ int cmd_rev_parse(int argc, const char **argv, const char *prefix)
 					puts(prefix);
 				continue;
 			}
+			if (!strcmp(arg, "--show-sparse-prefix")) {
+				puts(get_sparse_prefix_str());
+				continue;
+			}
 			if (!strcmp(arg, "--show-cdup")) {
 				const char *pfx = prefix;
 				if (!is_inside_work_tree()) {
diff --git a/cache.h b/cache.h
index 38985aa..4687096 100644
--- a/cache.h
+++ b/cache.h
@@ -319,6 +319,19 @@ extern const char *get_git_work_tree(void);
 extern const char *read_gitfile_gently(const char *path);
 extern void set_git_work_tree(const char *tree);
 
+extern int sparse_checkout_enabled();
+extern char **get_sparse_prefix(void);
+extern const char *get_sparse_prefix_str(void);
+extern char **save_sparse_prefix();
+extern char **restore_sparse_prefix(char **prefix);
+extern int outside_sparse_prefix(const char *prefix);
+extern int index_outside_sparse_prefix(const char *prefix);
+extern void set_sparse_prefix(const char *prefix);
+extern char **split_prefix(const char *env);
+extern char **combine_prefix_list(char **p1, char **p2);
+extern void free_prefix_list(char **prefix_list);
+extern int outside_prefix_list(char **iprefix, const char *prefix);
+
 #define ALTERNATE_DB_ENVIRONMENT "GIT_ALTERNATE_OBJECT_DIRECTORIES"
 
 extern const char **get_pathspec(const char *prefix, const char **pathspec);
diff --git a/config.c b/config.c
index 1e066c7..e7b457b 100644
--- a/config.c
+++ b/config.c
@@ -467,6 +467,13 @@ static int git_default_core_config(const char *var, const char *value)
 		return 0;
 	}
 
+	if (!strcmp(var, "core.sparsecheckout")) {
+		if (!value)
+			return config_error_nonbool(var);
+		set_sparse_prefix(value);
+		return 0;
+	}
+
 	/* Add other config variables here and to Documentation/config.txt. */
 	return 0;
 }
diff --git a/environment.c b/environment.c
index 4a88a17..94e39b8 100644
--- a/environment.c
+++ b/environment.c
@@ -46,9 +46,132 @@ enum rebase_setup_type autorebase = AUTOREBASE_NEVER;
 char *git_work_tree_cfg;
 static char *work_tree;
 
+static char **sparse_prefix;
+
 static const char *git_dir;
 static char *git_object_dir, *git_index_file, *git_refs_dir, *git_graft_file;
 
+static char *append_slash(const char *prefix, int len)
+{
+	char *new_prefix;
+
+	if (!*prefix)
+		return NULL;
+
+	if (prefix[len-1] == '/')
+		return xstrndup(prefix, len);
+
+	new_prefix = xmalloc(len+2);
+	memcpy(new_prefix, prefix, len);
+	new_prefix[len] = '/';
+	new_prefix[len+1] = '\0';
+	return new_prefix;
+}
+
+/* this should be sorted as same order as index */
+static int prefix_compare(const void *prefix1_, const void *prefix2_)
+{
+	const char *prefix1 = *(const char**)prefix1_;
+	const char *prefix2 = *(const char**)prefix2_;
+	int len1 = strlen(prefix1);
+	int len2 = strlen(prefix2);
+	int len = len1 < len2 ? len1 : len2;
+	int cmp = memcmp(prefix1, prefix2, len);
+	if (cmp)
+		return cmp;
+	if (len1 < len2)
+		return -1;
+	if (len1 > len2)
+		return 1;
+	return 0;
+}
+
+void free_prefix_list(char **prefix_list)
+{
+	char **prefix = prefix_list;
+
+	if (!prefix)
+		return;
+
+	while (*prefix) {
+		free(*prefix);
+		prefix++;
+	}
+	free(prefix_list);
+}
+
+char **split_prefix(const char *env)
+{
+	int prefix_nr = 0;
+	int prefix_alloc = 0;
+	char **prefix_list = NULL;
+
+	if (!env)
+		return NULL;
+
+	do {
+		const char *sep = strchr(env, ':');
+		int len = sep ? sep - env : strlen(env);
+		if (prefix_alloc <= prefix_nr+1) {
+			prefix_alloc = alloc_nr(prefix_alloc);
+			prefix_list = xrealloc(prefix_list,
+						prefix_alloc * sizeof(*prefix_list));
+		}
+		prefix_list[prefix_nr++] = append_slash(env, len);
+		env += sep ? len+1 : len;
+	} while (*env);
+	prefix_list[prefix_nr] = NULL;
+	qsort(prefix_list, prefix_nr, sizeof(*prefix_list), prefix_compare);
+	return prefix_list;
+}
+
+char **combine_prefix_list(char **p1, char **p2)
+{
+	int len1 = 0, len2 = 0;
+	char **p, **p12, *last_prefix;
+	char **result, **result_p;
+
+	/*
+	 * if either of them is null, full access,
+	 * combining them would give full access as well
+	 */
+	if (!p1 || !p2)
+		return NULL;
+
+	for (p = p1; *p; p++)
+		len1++;
+	for (p = p2; *p; p++)
+		len2++;
+
+	p12 = xmalloc((len1+len2+1)*sizeof(*p12));
+	result = xmalloc((len1+len2+1)*sizeof(*result));
+	memcpy(p12, p1, len1*sizeof(*p12));
+	memcpy(p12+len1, p2, (len2+1)*sizeof(*p12));
+	qsort(p12, len1+len2, sizeof(*p12), prefix_compare);
+
+	p = p12;
+	last_prefix = *p;
+	p++;
+	result_p = result;
+	*result_p = xstrdup(last_prefix);
+	result_p++;
+	while (*p) {
+		if (!strcmp(*p, last_prefix)) {
+			p++;
+			continue;
+		}
+		if (!prefixcmp(*p, last_prefix)) {
+			p++;
+			continue;
+		}
+		*result_p = xstrdup(*p);
+		result_p++;
+		p++;
+	}
+	*result_p = NULL;
+	return result;
+}
+
 static void setup_git_env(void)
 {
 	git_dir = getenv(GIT_DIR_ENVIRONMENT);
@@ -122,6 +245,104 @@ const char *get_git_work_tree(void)
 	return work_tree;
 }
 
+void set_sparse_prefix(const char *flat_sparse_prefix)
+{
+	free_prefix_list(sparse_prefix);
+	sparse_prefix = split_prefix(flat_sparse_prefix);
+}
+
+char **get_sparse_prefix()
+{
+	return sparse_prefix;
+}
+
+const char *get_sparse_prefix_str()
+{
+	static char **sparse_prefix = NULL;
+	static char *sparse_prefix_str = NULL;
+	int len;
+	char **prefix;
+
+	if (sparse_prefix == get_sparse_prefix())
+		return sparse_prefix ? sparse_prefix_str : "";
+
+	sparse_prefix = get_sparse_prefix();
+
+	if (!sparse_prefix)
+		return "";
+
+	len = 0;
+	for (prefix = sparse_prefix; *prefix; prefix++)
+		len += strlen(*prefix)+1;
+	if (sparse_prefix_str)
+		free(sparse_prefix_str);
+	sparse_prefix_str = xmalloc(len);
+
+	prefix = sparse_prefix;
+	len = strlen(*prefix);
+	if ((*prefix)[len-1] == '/')
+		len--;
+	memcpy(sparse_prefix_str, *prefix, len);
+	prefix++;
+	while (*prefix) {
+		int len2 = strlen(*prefix);
+		sparse_prefix_str[len++] = ':';
+		if ((*prefix)[len2-1] == '/')
+			len2--;
+		memcpy(sparse_prefix_str+len, *prefix, len2);
+		len += len2;
+		prefix++;
+	}
+	sparse_prefix_str[len] = 0;
+	return sparse_prefix_str;
+}
+
+char **save_sparse_prefix()
+{
+	char **prefix = sparse_prefix;
+	sparse_prefix = NULL;
+	return prefix;
+}
+
+char **restore_sparse_prefix(char **prefix)
+{
+	char **old_prefix = sparse_prefix;
+	sparse_prefix = prefix;
+	return old_prefix;
+}
+
+int outside_prefix_list(char **iprefix, const char *prefix)
+{
+	if (!iprefix)
+		return 0;
+
+	while (*iprefix) {
+		if (!prefixcmp(prefix, *iprefix))
+			return 0;
+		iprefix++;
+	}
+	return 1;
+}
+
+int sparse_checkout_enabled()
+{
+	static int disable_sparse_checkout = -1;
+	if (disable_sparse_checkout == -1)
+		disable_sparse_checkout = getenv("GIT_SPARSE_CHECKOUT_INDEX_ONLY") != NULL;
+	return !disable_sparse_checkout && get_sparse_prefix();
+}
+
+
+int outside_sparse_prefix(const char *prefix)
+{
+	return sparse_checkout_enabled() && outside_prefix_list(sparse_prefix, prefix);
+}
+
+int index_outside_sparse_prefix(const char *prefix)
+{
+	return outside_prefix_list(sparse_prefix, prefix);
+}
+
 char *get_object_directory(void)
 {
 	if (!git_object_dir)
-- 
1.5.5.GIT