update comment references to sha1_object_info()
[git] / negotiator / skipping.c
1 #include "cache.h"
2 #include "skipping.h"
3 #include "../commit.h"
4 #include "../fetch-negotiator.h"
5 #include "../prio-queue.h"
6 #include "../refs.h"
7 #include "../tag.h"
8
9 /* Remember to update object flag allocation in object.h */
10 /*
11  * Both us and the server know that both parties have this object.
12  */
13 #define COMMON          (1U << 2)
14 /*
15  * The server has told us that it has this object. We still need to tell the
16  * server that we have this object (or one of its descendants), but since we are
17  * going to do that, we do not need to tell the server about its ancestors.
18  */
19 #define ADVERTISED      (1U << 3)
20 /*
21  * This commit has entered the priority queue.
22  */
23 #define SEEN            (1U << 4)
24 /*
25  * This commit has left the priority queue.
26  */
27 #define POPPED          (1U << 5)
28
29 static int marked;
30
31 /*
32  * An entry in the priority queue.
33  */
34 struct entry {
35         struct commit *commit;
36
37         /*
38          * Used only if commit is not COMMON.
39          */
40         uint16_t original_ttl;
41         uint16_t ttl;
42 };
43
44 struct data {
45         struct prio_queue rev_list;
46
47         /*
48          * The number of non-COMMON commits in rev_list.
49          */
50         int non_common_revs;
51 };
52
53 static int compare(const void *a_, const void *b_, void *unused)
54 {
55         const struct entry *a = a_;
56         const struct entry *b = b_;
57         return compare_commits_by_commit_date(a->commit, b->commit, NULL);
58 }
59
60 static struct entry *rev_list_push(struct data *data, struct commit *commit, int mark)
61 {
62         struct entry *entry;
63         commit->object.flags |= mark | SEEN;
64
65         entry = xcalloc(1, sizeof(*entry));
66         entry->commit = commit;
67         prio_queue_put(&data->rev_list, entry);
68
69         if (!(mark & COMMON))
70                 data->non_common_revs++;
71         return entry;
72 }
73
74 static int clear_marks(const char *refname, const struct object_id *oid,
75                        int flag, void *cb_data)
76 {
77         struct object *o = deref_tag(the_repository, parse_object(the_repository, oid), refname, 0);
78
79         if (o && o->type == OBJ_COMMIT)
80                 clear_commit_marks((struct commit *)o,
81                                    COMMON | ADVERTISED | SEEN | POPPED);
82         return 0;
83 }
84
85 /*
86  * Mark this SEEN commit and all its SEEN ancestors as COMMON.
87  */
88 static void mark_common(struct data *data, struct commit *c)
89 {
90         struct commit_list *p;
91
92         if (c->object.flags & COMMON)
93                 return;
94         c->object.flags |= COMMON;
95         if (!(c->object.flags & POPPED))
96                 data->non_common_revs--;
97
98         if (!c->object.parsed)
99                 return;
100         for (p = c->parents; p; p = p->next) {
101                 if (p->item->object.flags & SEEN)
102                         mark_common(data, p->item);
103         }
104 }
105
106 /*
107  * Ensure that the priority queue has an entry for to_push, and ensure that the
108  * entry has the correct flags and ttl.
109  *
110  * This function returns 1 if an entry was found or created, and 0 otherwise
111  * (because the entry for this commit had already been popped).
112  */
113 static int push_parent(struct data *data, struct entry *entry,
114                        struct commit *to_push)
115 {
116         struct entry *parent_entry;
117
118         if (to_push->object.flags & SEEN) {
119                 int i;
120                 if (to_push->object.flags & POPPED)
121                         /*
122                          * The entry for this commit has already been popped,
123                          * due to clock skew. Pretend that this parent does not
124                          * exist.
125                          */
126                         return 0;
127                 /*
128                  * Find the existing entry and use it.
129                  */
130                 for (i = 0; i < data->rev_list.nr; i++) {
131                         parent_entry = data->rev_list.array[i].data;
132                         if (parent_entry->commit == to_push)
133                                 goto parent_found;
134                 }
135                 BUG("missing parent in priority queue");
136 parent_found:
137                 ;
138         } else {
139                 parent_entry = rev_list_push(data, to_push, 0);
140         }
141
142         if (entry->commit->object.flags & (COMMON | ADVERTISED)) {
143                 mark_common(data, to_push);
144         } else {
145                 uint16_t new_original_ttl = entry->ttl
146                         ? entry->original_ttl : entry->original_ttl * 3 / 2 + 1;
147                 uint16_t new_ttl = entry->ttl
148                         ? entry->ttl - 1 : new_original_ttl;
149                 if (parent_entry->original_ttl < new_original_ttl) {
150                         parent_entry->original_ttl = new_original_ttl;
151                         parent_entry->ttl = new_ttl;
152                 }
153         }
154
155         return 1;
156 }
157
158 static const struct object_id *get_rev(struct data *data)
159 {
160         struct commit *to_send = NULL;
161
162         while (to_send == NULL) {
163                 struct entry *entry;
164                 struct commit *commit;
165                 struct commit_list *p;
166                 int parent_pushed = 0;
167
168                 if (data->rev_list.nr == 0 || data->non_common_revs == 0)
169                         return NULL;
170
171                 entry = prio_queue_get(&data->rev_list);
172                 commit = entry->commit;
173                 commit->object.flags |= POPPED;
174                 if (!(commit->object.flags & COMMON))
175                         data->non_common_revs--;
176
177                 if (!(commit->object.flags & COMMON) && !entry->ttl)
178                         to_send = commit;
179
180                 parse_commit(commit);
181                 for (p = commit->parents; p; p = p->next)
182                         parent_pushed |= push_parent(data, entry, p->item);
183
184                 if (!(commit->object.flags & COMMON) && !parent_pushed)
185                         /*
186                          * This commit has no parents, or all of its parents
187                          * have already been popped (due to clock skew), so send
188                          * it anyway.
189                          */
190                         to_send = commit;
191
192                 free(entry);
193         }
194
195         return &to_send->object.oid;
196 }
197
198 static void known_common(struct fetch_negotiator *n, struct commit *c)
199 {
200         if (c->object.flags & SEEN)
201                 return;
202         rev_list_push(n->data, c, ADVERTISED);
203 }
204
205 static void add_tip(struct fetch_negotiator *n, struct commit *c)
206 {
207         n->known_common = NULL;
208         if (c->object.flags & SEEN)
209                 return;
210         rev_list_push(n->data, c, 0);
211 }
212
213 static const struct object_id *next(struct fetch_negotiator *n)
214 {
215         n->known_common = NULL;
216         n->add_tip = NULL;
217         return get_rev(n->data);
218 }
219
220 static int ack(struct fetch_negotiator *n, struct commit *c)
221 {
222         int known_to_be_common = !!(c->object.flags & COMMON);
223         if (!(c->object.flags & SEEN))
224                 die("received ack for commit %s not sent as 'have'\n",
225                     oid_to_hex(&c->object.oid));
226         mark_common(n->data, c);
227         return known_to_be_common;
228 }
229
230 static void release(struct fetch_negotiator *n)
231 {
232         clear_prio_queue(&((struct data *)n->data)->rev_list);
233         FREE_AND_NULL(n->data);
234 }
235
236 void skipping_negotiator_init(struct fetch_negotiator *negotiator)
237 {
238         struct data *data;
239         negotiator->known_common = known_common;
240         negotiator->add_tip = add_tip;
241         negotiator->next = next;
242         negotiator->ack = ack;
243         negotiator->release = release;
244         negotiator->data = data = xcalloc(1, sizeof(*data));
245         data->rev_list.compare = compare;
246
247         if (marked)
248                 for_each_ref(clear_marks, NULL);
249         marked = 1;
250 }