4 files changed, 442 insertions, 0 deletions

diff --git a/third_party/git/negotiator/default.c b/third_party/git/negotiator/default.c
new file mode 100644
index 000000000000..4b78f6bf36a0
--- /dev/null
+++ b/third_party/git/negotiator/default.c
@@ -0,0 +1,176 @@
+#include "cache.h"
+#include "default.h"
+#include "../commit.h"
+#include "../fetch-negotiator.h"
+#include "../prio-queue.h"
+#include "../refs.h"
+#include "../tag.h"
+
+/* Remember to update object flag allocation in object.h */
+#define COMMON		(1U << 2)
+#define COMMON_REF	(1U << 3)
+#define SEEN		(1U << 4)
+#define POPPED		(1U << 5)
+
+static int marked;
+
+struct negotiation_state {
+	struct prio_queue rev_list;
+	int non_common_revs;
+};
+
+static void rev_list_push(struct negotiation_state *ns,
+			  struct commit *commit, int mark)
+{
+	if (!(commit->object.flags & mark)) {
+		commit->object.flags |= mark;
+
+		if (parse_commit(commit))
+			return;
+
+		prio_queue_put(&ns->rev_list, commit);
+
+		if (!(commit->object.flags & COMMON))
+			ns->non_common_revs++;
+	}
+}
+
+static int clear_marks(const char *refname, const struct object_id *oid,
+		       int flag, void *cb_data)
+{
+	struct object *o = deref_tag(the_repository, parse_object(the_repository, oid), refname, 0);
+
+	if (o && o->type == OBJ_COMMIT)
+		clear_commit_marks((struct commit *)o,
+				   COMMON | COMMON_REF | SEEN | POPPED);
+	return 0;
+}
+
+/*
+ * This function marks a rev and its ancestors as common.
+ * In some cases, it is desirable to mark only the ancestors (for example
+ * when only the server does not yet know that they are common).
+ */
+static void mark_common(struct negotiation_state *ns, struct commit *commit,
+		int ancestors_only, int dont_parse)
+{
+	if (commit != NULL && !(commit->object.flags & COMMON)) {
+		struct object *o = (struct object *)commit;
+
+		if (!ancestors_only)
+			o->flags |= COMMON;
+
+		if (!(o->flags & SEEN))
+			rev_list_push(ns, commit, SEEN);
+		else {
+			struct commit_list *parents;
+
+			if (!ancestors_only && !(o->flags & POPPED))
+				ns->non_common_revs--;
+			if (!o->parsed && !dont_parse)
+				if (parse_commit(commit))
+					return;
+
+			for (parents = commit->parents;
+					parents;
+					parents = parents->next)
+				mark_common(ns, parents->item, 0,
+					    dont_parse);
+		}
+	}
+}
+
+/*
+ * Get the next rev to send, ignoring the common.
+ */
+static const struct object_id *get_rev(struct negotiation_state *ns)
+{
+	struct commit *commit = NULL;
+
+	while (commit == NULL) {
+		unsigned int mark;
+		struct commit_list *parents;
+
+		if (ns->rev_list.nr == 0 || ns->non_common_revs == 0)
+			return NULL;
+
+		commit = prio_queue_get(&ns->rev_list);
+		parse_commit(commit);
+		parents = commit->parents;
+
+		commit->object.flags |= POPPED;
+		if (!(commit->object.flags & COMMON))
+			ns->non_common_revs--;
+
+		if (commit->object.flags & COMMON) {
+			/* do not send "have", and ignore ancestors */
+			commit = NULL;
+			mark = COMMON | SEEN;
+		} else if (commit->object.flags & COMMON_REF)
+			/* send "have", and ignore ancestors */
+			mark = COMMON | SEEN;
+		else
+			/* send "have", also for its ancestors */
+			mark = SEEN;
+
+		while (parents) {
+			if (!(parents->item->object.flags & SEEN))
+				rev_list_push(ns, parents->item, mark);
+			if (mark & COMMON)
+				mark_common(ns, parents->item, 1, 0);
+			parents = parents->next;
+		}
+	}
+
+	return &commit->object.oid;
+}
+
+static void known_common(struct fetch_negotiator *n, struct commit *c)
+{
+	if (!(c->object.flags & SEEN)) {
+		rev_list_push(n->data, c, COMMON_REF | SEEN);
+		mark_common(n->data, c, 1, 1);
+	}
+}
+
+static void add_tip(struct fetch_negotiator *n, struct commit *c)
+{
+	n->known_common = NULL;
+	rev_list_push(n->data, c, SEEN);
+}
+
+static const struct object_id *next(struct fetch_negotiator *n)
+{
+	n->known_common = NULL;
+	n->add_tip = NULL;
+	return get_rev(n->data);
+}
+
+static int ack(struct fetch_negotiator *n, struct commit *c)
+{
+	int known_to_be_common = !!(c->object.flags & COMMON);
+	mark_common(n->data, c, 0, 1);
+	return known_to_be_common;
+}
+
+static void release(struct fetch_negotiator *n)
+{
+	clear_prio_queue(&((struct negotiation_state *)n->data)->rev_list);
+	FREE_AND_NULL(n->data);
+}
+
+void default_negotiator_init(struct fetch_negotiator *negotiator)
+{
+	struct negotiation_state *ns;
+	negotiator->known_common = known_common;
+	negotiator->add_tip = add_tip;
+	negotiator->next = next;
+	negotiator->ack = ack;
+	negotiator->release = release;
+	negotiator->data = ns = xcalloc(1, sizeof(*ns));
+	ns->rev_list.compare = compare_commits_by_commit_date;
+
+	if (marked)
+		for_each_ref(clear_marks, NULL);
+	marked = 1;
+}
diff --git a/third_party/git/negotiator/default.h b/third_party/git/negotiator/default.h
new file mode 100644
index 000000000000..d23a8f2fb8e0
--- /dev/null
+++ b/third_party/git/negotiator/default.h
@@ -0,0 +1,8 @@
+#ifndef NEGOTIATOR_DEFAULT_H
+#define NEGOTIATOR_DEFAULT_H
+
+struct fetch_negotiator;
+
+void default_negotiator_init(struct fetch_negotiator *negotiator);
+
+#endif
diff --git a/third_party/git/negotiator/skipping.c b/third_party/git/negotiator/skipping.c
new file mode 100644
index 000000000000..dffbc76c49ef
--- /dev/null
+++ b/third_party/git/negotiator/skipping.c
@@ -0,0 +1,250 @@
+#include "cache.h"
+#include "skipping.h"
+#include "../commit.h"
+#include "../fetch-negotiator.h"
+#include "../prio-queue.h"
+#include "../refs.h"
+#include "../tag.h"
+
+/* Remember to update object flag allocation in object.h */
+/*
+ * Both us and the server know that both parties have this object.
+ */
+#define COMMON		(1U << 2)
+/*
+ * The server has told us that it has this object. We still need to tell the
+ * server that we have this object (or one of its descendants), but since we are
+ * going to do that, we do not need to tell the server about its ancestors.
+ */
+#define ADVERTISED	(1U << 3)
+/*
+ * This commit has entered the priority queue.
+ */
+#define SEEN		(1U << 4)
+/*
+ * This commit has left the priority queue.
+ */
+#define POPPED		(1U << 5)
+
+static int marked;
+
+/*
+ * An entry in the priority queue.
+ */
+struct entry {
+	struct commit *commit;
+
+	/*
+	 * Used only if commit is not COMMON.
+	 */
+	uint16_t original_ttl;
+	uint16_t ttl;
+};
+
+struct data {
+	struct prio_queue rev_list;
+
+	/*
+	 * The number of non-COMMON commits in rev_list.
+	 */
+	int non_common_revs;
+};
+
+static int compare(const void *a_, const void *b_, void *unused)
+{
+	const struct entry *a = a_;
+	const struct entry *b = b_;
+	return compare_commits_by_commit_date(a->commit, b->commit, NULL);
+}
+
+static struct entry *rev_list_push(struct data *data, struct commit *commit, int mark)
+{
+	struct entry *entry;
+	commit->object.flags |= mark | SEEN;
+
+	entry = xcalloc(1, sizeof(*entry));
+	entry->commit = commit;
+	prio_queue_put(&data->rev_list, entry);
+
+	if (!(mark & COMMON))
+		data->non_common_revs++;
+	return entry;
+}
+
+static int clear_marks(const char *refname, const struct object_id *oid,
+		       int flag, void *cb_data)
+{
+	struct object *o = deref_tag(the_repository, parse_object(the_repository, oid), refname, 0);
+
+	if (o && o->type == OBJ_COMMIT)
+		clear_commit_marks((struct commit *)o,
+				   COMMON | ADVERTISED | SEEN | POPPED);
+	return 0;
+}
+
+/*
+ * Mark this SEEN commit and all its SEEN ancestors as COMMON.
+ */
+static void mark_common(struct data *data, struct commit *c)
+{
+	struct commit_list *p;
+
+	if (c->object.flags & COMMON)
+		return;
+	c->object.flags |= COMMON;
+	if (!(c->object.flags & POPPED))
+		data->non_common_revs--;
+
+	if (!c->object.parsed)
+		return;
+	for (p = c->parents; p; p = p->next) {
+		if (p->item->object.flags & SEEN)
+			mark_common(data, p->item);
+	}
+}
+
+/*
+ * Ensure that the priority queue has an entry for to_push, and ensure that the
+ * entry has the correct flags and ttl.
+ *
+ * This function returns 1 if an entry was found or created, and 0 otherwise
+ * (because the entry for this commit had already been popped).
+ */
+static int push_parent(struct data *data, struct entry *entry,
+		       struct commit *to_push)
+{
+	struct entry *parent_entry;
+
+	if (to_push->object.flags & SEEN) {
+		int i;
+		if (to_push->object.flags & POPPED)
+			/*
+			 * The entry for this commit has already been popped,
+			 * due to clock skew. Pretend that this parent does not
+			 * exist.
+			 */
+			return 0;
+		/*
+		 * Find the existing entry and use it.
+		 */
+		for (i = 0; i < data->rev_list.nr; i++) {
+			parent_entry = data->rev_list.array[i].data;
+			if (parent_entry->commit == to_push)
+				goto parent_found;
+		}
+		BUG("missing parent in priority queue");
+parent_found:
+		;
+	} else {
+		parent_entry = rev_list_push(data, to_push, 0);
+	}
+
+	if (entry->commit->object.flags & (COMMON | ADVERTISED)) {
+		mark_common(data, to_push);
+	} else {
+		uint16_t new_original_ttl = entry->ttl
+			? entry->original_ttl : entry->original_ttl * 3 / 2 + 1;
+		uint16_t new_ttl = entry->ttl
+			? entry->ttl - 1 : new_original_ttl;
+		if (parent_entry->original_ttl < new_original_ttl) {
+			parent_entry->original_ttl = new_original_ttl;
+			parent_entry->ttl = new_ttl;
+		}
+	}
+
+	return 1;
+}
+
+static const struct object_id *get_rev(struct data *data)
+{
+	struct commit *to_send = NULL;
+
+	while (to_send == NULL) {
+		struct entry *entry;
+		struct commit *commit;
+		struct commit_list *p;
+		int parent_pushed = 0;
+
+		if (data->rev_list.nr == 0 || data->non_common_revs == 0)
+			return NULL;
+
+		entry = prio_queue_get(&data->rev_list);
+		commit = entry->commit;
+		commit->object.flags |= POPPED;
+		if (!(commit->object.flags & COMMON))
+			data->non_common_revs--;
+
+		if (!(commit->object.flags & COMMON) && !entry->ttl)
+			to_send = commit;
+
+		parse_commit(commit);
+		for (p = commit->parents; p; p = p->next)
+			parent_pushed |= push_parent(data, entry, p->item);
+
+		if (!(commit->object.flags & COMMON) && !parent_pushed)
+			/*
+			 * This commit has no parents, or all of its parents
+			 * have already been popped (due to clock skew), so send
+			 * it anyway.
+			 */
+			to_send = commit;
+
+		free(entry);
+	}
+
+	return &to_send->object.oid;
+}
+
+static void known_common(struct fetch_negotiator *n, struct commit *c)
+{
+	if (c->object.flags & SEEN)
+		return;
+	rev_list_push(n->data, c, ADVERTISED);
+}
+
+static void add_tip(struct fetch_negotiator *n, struct commit *c)
+{
+	n->known_common = NULL;
+	if (c->object.flags & SEEN)
+		return;
+	rev_list_push(n->data, c, 0);
+}
+
+static const struct object_id *next(struct fetch_negotiator *n)
+{
+	n->known_common = NULL;
+	n->add_tip = NULL;
+	return get_rev(n->data);
+}
+
+static int ack(struct fetch_negotiator *n, struct commit *c)
+{
+	int known_to_be_common = !!(c->object.flags & COMMON);
+	if (!(c->object.flags & SEEN))
+		die("received ack for commit %s not sent as 'have'\n",
+		    oid_to_hex(&c->object.oid));
+	mark_common(n->data, c);
+	return known_to_be_common;
+}
+
+static void release(struct fetch_negotiator *n)
+{
+	clear_prio_queue(&((struct data *)n->data)->rev_list);
+	FREE_AND_NULL(n->data);
+}
+
+void skipping_negotiator_init(struct fetch_negotiator *negotiator)
+{
+	struct data *data;
+	negotiator->known_common = known_common;
+	negotiator->add_tip = add_tip;
+	negotiator->next = next;
+	negotiator->ack = ack;
+	negotiator->release = release;
+	negotiator->data = data = xcalloc(1, sizeof(*data));
+	data->rev_list.compare = compare;
+
+	if (marked)
+		for_each_ref(clear_marks, NULL);
+	marked = 1;
+}
diff --git a/third_party/git/negotiator/skipping.h b/third_party/git/negotiator/skipping.h
new file mode 100644
index 000000000000..d7dfa6c6e429
--- /dev/null
+++ b/third_party/git/negotiator/skipping.h
@@ -0,0 +1,8 @@
+#ifndef NEGOTIATOR_SKIPPING_H
+#define NEGOTIATOR_SKIPPING_H
+
+struct fetch_negotiator;
+
+void skipping_negotiator_init(struct fetch_negotiator *negotiator);
+
+#endif