test-lib: unset GIT_NOTES_REF to stop it from influencing tests
[git/git.git] / notes.c
CommitLineData
a97a7468 1#include "cache.h"
a97a7468 2#include "notes.h"
73f464b5 3#include "blob.h"
61a7cca0 4#include "tree.h"
a97a7468
JS
5#include "utf8.h"
6#include "strbuf.h"
fd53c9eb
JS
7#include "tree-walk.h"
8
23123aec
JH
9/*
10 * Use a non-balancing simple 16-tree structure with struct int_node as
11 * internal nodes, and struct leaf_node as leaf nodes. Each int_node has a
12 * 16-array of pointers to its children.
13 * The bottom 2 bits of each pointer is used to identify the pointer type
14 * - ptr & 3 == 0 - NULL pointer, assert(ptr == NULL)
15 * - ptr & 3 == 1 - pointer to next internal node - cast to struct int_node *
16 * - ptr & 3 == 2 - pointer to note entry - cast to struct leaf_node *
17 * - ptr & 3 == 3 - pointer to subtree entry - cast to struct leaf_node *
18 *
19 * The root node is a statically allocated struct int_node.
20 */
21struct int_node {
22 void *a[16];
fd53c9eb
JS
23};
24
23123aec
JH
25/*
26 * Leaf nodes come in two variants, note entries and subtree entries,
27 * distinguished by the LSb of the leaf node pointer (see above).
a7e7eff6 28 * As a note entry, the key is the SHA1 of the referenced object, and the
23123aec
JH
29 * value is the SHA1 of the note object.
30 * As a subtree entry, the key is the prefix SHA1 (w/trailing NULs) of the
a7e7eff6 31 * referenced object, using the last byte of the key to store the length of
23123aec
JH
32 * the prefix. The value is the SHA1 of the tree object containing the notes
33 * subtree.
34 */
35struct leaf_node {
36 unsigned char key_sha1[20];
37 unsigned char val_sha1[20];
fd53c9eb 38};
a97a7468 39
851c2b37
JH
40/*
41 * A notes tree may contain entries that are not notes, and that do not follow
42 * the naming conventions of notes. There are typically none/few of these, but
43 * we still need to keep track of them. Keep a simple linked list sorted alpha-
44 * betically on the non-note path. The list is populated when parsing tree
45 * objects in load_subtree(), and the non-notes are correctly written back into
46 * the tree objects produced by write_notes_tree().
47 */
48struct non_note {
49 struct non_note *next; /* grounded (last->next == NULL) */
50 char *path;
51 unsigned int mode;
52 unsigned char sha1[20];
53};
54
23123aec
JH
55#define PTR_TYPE_NULL 0
56#define PTR_TYPE_INTERNAL 1
57#define PTR_TYPE_NOTE 2
58#define PTR_TYPE_SUBTREE 3
fd53c9eb 59
23123aec
JH
60#define GET_PTR_TYPE(ptr) ((uintptr_t) (ptr) & 3)
61#define CLR_PTR_TYPE(ptr) ((void *) ((uintptr_t) (ptr) & ~3))
62#define SET_PTR_TYPE(ptr, type) ((void *) ((uintptr_t) (ptr) | (type)))
fd53c9eb 63
1ec666b0 64#define GET_NIBBLE(n, sha1) (((sha1[(n) >> 1]) >> ((~(n) & 0x01) << 2)) & 0x0f)
fd53c9eb 65
23123aec
JH
66#define SUBTREE_SHA1_PREFIXCMP(key_sha1, subtree_sha1) \
67 (memcmp(key_sha1, subtree_sha1, subtree_sha1[19]))
fd53c9eb 68
cd305392 69struct notes_tree default_notes_tree;
23123aec 70
851c2b37
JH
71static void load_subtree(struct notes_tree *t, struct leaf_node *subtree,
72 struct int_node *node, unsigned int n);
23123aec
JH
73
74/*
ef8db638 75 * Search the tree until the appropriate location for the given key is found:
23123aec 76 * 1. Start at the root node, with n = 0
ef8db638
JH
77 * 2. If a[0] at the current level is a matching subtree entry, unpack that
78 * subtree entry and remove it; restart search at the current level.
79 * 3. Use the nth nibble of the key as an index into a:
80 * - If a[n] is an int_node, recurse from #2 into that node and increment n
23123aec
JH
81 * - If a matching subtree entry, unpack that subtree entry (and remove it);
82 * restart search at the current level.
ef8db638
JH
83 * - Otherwise, we have found one of the following:
84 * - a subtree entry which does not match the key
85 * - a note entry which may or may not match the key
86 * - an unused leaf node (NULL)
87 * In any case, set *tree and *n, and return pointer to the tree location.
23123aec 88 */
851c2b37 89static void **note_tree_search(struct notes_tree *t, struct int_node **tree,
ef8db638 90 unsigned char *n, const unsigned char *key_sha1)
23123aec
JH
91{
92 struct leaf_node *l;
ef8db638
JH
93 unsigned char i;
94 void *p = (*tree)->a[0];
23123aec 95
ef8db638
JH
96 if (GET_PTR_TYPE(p) == PTR_TYPE_SUBTREE) {
97 l = (struct leaf_node *) CLR_PTR_TYPE(p);
98 if (!SUBTREE_SHA1_PREFIXCMP(key_sha1, l->key_sha1)) {
99 /* unpack tree and resume search */
100 (*tree)->a[0] = NULL;
851c2b37 101 load_subtree(t, l, *tree, *n);
ef8db638 102 free(l);
851c2b37 103 return note_tree_search(t, tree, n, key_sha1);
ef8db638
JH
104 }
105 }
106
107 i = GET_NIBBLE(*n, key_sha1);
108 p = (*tree)->a[i];
0ab1faae 109 switch (GET_PTR_TYPE(p)) {
23123aec 110 case PTR_TYPE_INTERNAL:
ef8db638
JH
111 *tree = CLR_PTR_TYPE(p);
112 (*n)++;
851c2b37 113 return note_tree_search(t, tree, n, key_sha1);
23123aec
JH
114 case PTR_TYPE_SUBTREE:
115 l = (struct leaf_node *) CLR_PTR_TYPE(p);
116 if (!SUBTREE_SHA1_PREFIXCMP(key_sha1, l->key_sha1)) {
117 /* unpack tree and resume search */
ef8db638 118 (*tree)->a[i] = NULL;
851c2b37 119 load_subtree(t, l, *tree, *n);
23123aec 120 free(l);
851c2b37 121 return note_tree_search(t, tree, n, key_sha1);
23123aec 122 }
ef8db638 123 /* fall through */
23123aec 124 default:
ef8db638 125 return &((*tree)->a[i]);
fd53c9eb 126 }
ef8db638 127}
23123aec 128
ef8db638
JH
129/*
130 * To find a leaf_node:
131 * Search to the tree location appropriate for the given key:
132 * If a note entry with matching key, return the note entry, else return NULL.
133 */
851c2b37
JH
134static struct leaf_node *note_tree_find(struct notes_tree *t,
135 struct int_node *tree, unsigned char n,
ef8db638
JH
136 const unsigned char *key_sha1)
137{
851c2b37 138 void **p = note_tree_search(t, &tree, &n, key_sha1);
ef8db638
JH
139 if (GET_PTR_TYPE(*p) == PTR_TYPE_NOTE) {
140 struct leaf_node *l = (struct leaf_node *) CLR_PTR_TYPE(*p);
141 if (!hashcmp(key_sha1, l->key_sha1))
142 return l;
23123aec
JH
143 }
144 return NULL;
fd53c9eb
JS
145}
146
23123aec
JH
147/*
148 * To insert a leaf_node:
ef8db638
JH
149 * Search to the tree location appropriate for the given leaf_node's key:
150 * - If location is unused (NULL), store the tweaked pointer directly there
151 * - If location holds a note entry that matches the note-to-be-inserted, then
73f464b5 152 * combine the two notes (by calling the given combine_notes function).
ef8db638
JH
153 * - If location holds a note entry that matches the subtree-to-be-inserted,
154 * then unpack the subtree-to-be-inserted into the location.
155 * - If location holds a matching subtree entry, unpack the subtree at that
156 * location, and restart the insert operation from that level.
157 * - Else, create a new int_node, holding both the node-at-location and the
158 * node-to-be-inserted, and store the new int_node into the location.
23123aec 159 */
851c2b37
JH
160static void note_tree_insert(struct notes_tree *t, struct int_node *tree,
161 unsigned char n, struct leaf_node *entry, unsigned char type,
73f464b5 162 combine_notes_fn combine_notes)
fd53c9eb 163{
23123aec 164 struct int_node *new_node;
ef8db638 165 struct leaf_node *l;
851c2b37 166 void **p = note_tree_search(t, &tree, &n, entry->key_sha1);
ef8db638
JH
167
168 assert(GET_PTR_TYPE(entry) == 0); /* no type bits set */
169 l = (struct leaf_node *) CLR_PTR_TYPE(*p);
0ab1faae 170 switch (GET_PTR_TYPE(*p)) {
23123aec 171 case PTR_TYPE_NULL:
ef8db638
JH
172 assert(!*p);
173 *p = SET_PTR_TYPE(entry, type);
174 return;
175 case PTR_TYPE_NOTE:
176 switch (type) {
177 case PTR_TYPE_NOTE:
178 if (!hashcmp(l->key_sha1, entry->key_sha1)) {
179 /* skip concatenation if l == entry */
180 if (!hashcmp(l->val_sha1, entry->val_sha1))
181 return;
182
73f464b5
JH
183 if (combine_notes(l->val_sha1, entry->val_sha1))
184 die("failed to combine notes %s and %s"
185 " for object %s",
ef8db638 186 sha1_to_hex(l->val_sha1),
73f464b5 187 sha1_to_hex(entry->val_sha1),
ef8db638
JH
188 sha1_to_hex(l->key_sha1));
189 free(entry);
190 return;
191 }
192 break;
193 case PTR_TYPE_SUBTREE:
194 if (!SUBTREE_SHA1_PREFIXCMP(l->key_sha1,
195 entry->key_sha1)) {
196 /* unpack 'entry' */
851c2b37 197 load_subtree(t, entry, tree, n);
ef8db638
JH
198 free(entry);
199 return;
200 }
201 break;
202 }
203 break;
204 case PTR_TYPE_SUBTREE:
205 if (!SUBTREE_SHA1_PREFIXCMP(entry->key_sha1, l->key_sha1)) {
206 /* unpack 'l' and restart insert */
207 *p = NULL;
851c2b37 208 load_subtree(t, l, tree, n);
ef8db638 209 free(l);
851c2b37
JH
210 note_tree_insert(t, tree, n, entry, type,
211 combine_notes);
ef8db638 212 return;
23123aec 213 }
ef8db638 214 break;
fd53c9eb 215 }
ef8db638
JH
216
217 /* non-matching leaf_node */
218 assert(GET_PTR_TYPE(*p) == PTR_TYPE_NOTE ||
219 GET_PTR_TYPE(*p) == PTR_TYPE_SUBTREE);
220 new_node = (struct int_node *) xcalloc(sizeof(struct int_node), 1);
851c2b37
JH
221 note_tree_insert(t, new_node, n + 1, l, GET_PTR_TYPE(*p),
222 combine_notes);
ef8db638 223 *p = SET_PTR_TYPE(new_node, PTR_TYPE_INTERNAL);
851c2b37 224 note_tree_insert(t, new_node, n + 1, entry, type, combine_notes);
23123aec 225}
fd53c9eb 226
1ec666b0
JH
227/*
228 * How to consolidate an int_node:
229 * If there are > 1 non-NULL entries, give up and return non-zero.
230 * Otherwise replace the int_node at the given index in the given parent node
231 * with the only entry (or a NULL entry if no entries) from the given tree,
232 * and return 0.
233 */
234static int note_tree_consolidate(struct int_node *tree,
235 struct int_node *parent, unsigned char index)
236{
237 unsigned int i;
238 void *p = NULL;
239
240 assert(tree && parent);
241 assert(CLR_PTR_TYPE(parent->a[index]) == tree);
242
243 for (i = 0; i < 16; i++) {
244 if (GET_PTR_TYPE(tree->a[i]) != PTR_TYPE_NULL) {
245 if (p) /* more than one entry */
246 return -2;
247 p = tree->a[i];
248 }
249 }
250
251 /* replace tree with p in parent[index] */
252 parent->a[index] = p;
253 free(tree);
254 return 0;
255}
256
257/*
258 * To remove a leaf_node:
259 * Search to the tree location appropriate for the given leaf_node's key:
260 * - If location does not hold a matching entry, abort and do nothing.
261 * - Replace the matching leaf_node with a NULL entry (and free the leaf_node).
262 * - Consolidate int_nodes repeatedly, while walking up the tree towards root.
263 */
cd305392
JH
264static void note_tree_remove(struct notes_tree *t, struct int_node *tree,
265 unsigned char n, struct leaf_node *entry)
1ec666b0
JH
266{
267 struct leaf_node *l;
268 struct int_node *parent_stack[20];
269 unsigned char i, j;
851c2b37 270 void **p = note_tree_search(t, &tree, &n, entry->key_sha1);
1ec666b0
JH
271
272 assert(GET_PTR_TYPE(entry) == 0); /* no type bits set */
273 if (GET_PTR_TYPE(*p) != PTR_TYPE_NOTE)
274 return; /* type mismatch, nothing to remove */
275 l = (struct leaf_node *) CLR_PTR_TYPE(*p);
276 if (hashcmp(l->key_sha1, entry->key_sha1))
277 return; /* key mismatch, nothing to remove */
278
279 /* we have found a matching entry */
280 free(l);
281 *p = SET_PTR_TYPE(NULL, PTR_TYPE_NULL);
282
283 /* consolidate this tree level, and parent levels, if possible */
284 if (!n)
285 return; /* cannot consolidate top level */
286 /* first, build stack of ancestors between root and current node */
cd305392 287 parent_stack[0] = t->root;
1ec666b0
JH
288 for (i = 0; i < n; i++) {
289 j = GET_NIBBLE(i, entry->key_sha1);
290 parent_stack[i + 1] = CLR_PTR_TYPE(parent_stack[i]->a[j]);
291 }
292 assert(i == n && parent_stack[i] == tree);
293 /* next, unwind stack until note_tree_consolidate() is done */
294 while (i > 0 &&
295 !note_tree_consolidate(parent_stack[i], parent_stack[i - 1],
296 GET_NIBBLE(i - 1, entry->key_sha1)))
297 i--;
298}
299
23123aec
JH
300/* Free the entire notes data contained in the given tree */
301static void note_tree_free(struct int_node *tree)
302{
303 unsigned int i;
304 for (i = 0; i < 16; i++) {
305 void *p = tree->a[i];
0ab1faae 306 switch (GET_PTR_TYPE(p)) {
23123aec
JH
307 case PTR_TYPE_INTERNAL:
308 note_tree_free(CLR_PTR_TYPE(p));
309 /* fall through */
310 case PTR_TYPE_NOTE:
311 case PTR_TYPE_SUBTREE:
312 free(CLR_PTR_TYPE(p));
313 }
fd53c9eb 314 }
23123aec 315}
fd53c9eb 316
23123aec
JH
317/*
318 * Convert a partial SHA1 hex string to the corresponding partial SHA1 value.
319 * - hex - Partial SHA1 segment in ASCII hex format
320 * - hex_len - Length of above segment. Must be multiple of 2 between 0 and 40
321 * - sha1 - Partial SHA1 value is written here
322 * - sha1_len - Max #bytes to store in sha1, Must be >= hex_len / 2, and < 20
0ab1faae 323 * Returns -1 on error (invalid arguments or invalid SHA1 (not in hex format)).
23123aec
JH
324 * Otherwise, returns number of bytes written to sha1 (i.e. hex_len / 2).
325 * Pads sha1 with NULs up to sha1_len (not included in returned length).
326 */
327static int get_sha1_hex_segment(const char *hex, unsigned int hex_len,
328 unsigned char *sha1, unsigned int sha1_len)
329{
330 unsigned int i, len = hex_len >> 1;
331 if (hex_len % 2 != 0 || len > sha1_len)
332 return -1;
333 for (i = 0; i < len; i++) {
334 unsigned int val = (hexval(hex[0]) << 4) | hexval(hex[1]);
335 if (val & ~0xff)
336 return -1;
337 *sha1++ = val;
338 hex += 2;
339 }
340 for (; i < sha1_len; i++)
341 *sha1++ = 0;
342 return len;
fd53c9eb
JS
343}
344
851c2b37
JH
345static int non_note_cmp(const struct non_note *a, const struct non_note *b)
346{
347 return strcmp(a->path, b->path);
348}
349
350static void add_non_note(struct notes_tree *t, const char *path,
351 unsigned int mode, const unsigned char *sha1)
352{
353 struct non_note *p = t->prev_non_note, *n;
354 n = (struct non_note *) xmalloc(sizeof(struct non_note));
355 n->next = NULL;
356 n->path = xstrdup(path);
357 n->mode = mode;
358 hashcpy(n->sha1, sha1);
359 t->prev_non_note = n;
360
361 if (!t->first_non_note) {
362 t->first_non_note = n;
363 return;
364 }
365
366 if (non_note_cmp(p, n) < 0)
367 ; /* do nothing */
368 else if (non_note_cmp(t->first_non_note, n) <= 0)
369 p = t->first_non_note;
370 else {
371 /* n sorts before t->first_non_note */
372 n->next = t->first_non_note;
373 t->first_non_note = n;
374 return;
375 }
376
377 /* n sorts equal or after p */
378 while (p->next && non_note_cmp(p->next, n) <= 0)
379 p = p->next;
380
381 if (non_note_cmp(p, n) == 0) { /* n ~= p; overwrite p with n */
382 assert(strcmp(p->path, n->path) == 0);
383 p->mode = n->mode;
384 hashcpy(p->sha1, n->sha1);
385 free(n);
386 t->prev_non_note = p;
387 return;
388 }
389
390 /* n sorts between p and p->next */
391 n->next = p->next;
392 p->next = n;
393}
394
395static void load_subtree(struct notes_tree *t, struct leaf_node *subtree,
396 struct int_node *node, unsigned int n)
fd53c9eb 397{
a7e7eff6 398 unsigned char object_sha1[20];
23123aec 399 unsigned int prefix_len;
23123aec 400 void *buf;
fd53c9eb
JS
401 struct tree_desc desc;
402 struct name_entry entry;
851c2b37
JH
403 int len, path_len;
404 unsigned char type;
405 struct leaf_node *l;
23123aec
JH
406
407 buf = fill_tree_descriptor(&desc, subtree->val_sha1);
408 if (!buf)
409 die("Could not read %s for notes-index",
410 sha1_to_hex(subtree->val_sha1));
411
412 prefix_len = subtree->key_sha1[19];
413 assert(prefix_len * 2 >= n);
a7e7eff6 414 memcpy(object_sha1, subtree->key_sha1, prefix_len);
23123aec 415 while (tree_entry(&desc, &entry)) {
851c2b37
JH
416 path_len = strlen(entry.path);
417 len = get_sha1_hex_segment(entry.path, path_len,
a7e7eff6 418 object_sha1 + prefix_len, 20 - prefix_len);
23123aec 419 if (len < 0)
851c2b37 420 goto handle_non_note; /* entry.path is not a SHA1 */
23123aec
JH
421 len += prefix_len;
422
423 /*
a7e7eff6 424 * If object SHA1 is complete (len == 20), assume note object
851c2b37
JH
425 * If object SHA1 is incomplete (len < 20), and current
426 * component consists of 2 hex chars, assume note subtree
23123aec
JH
427 */
428 if (len <= 20) {
851c2b37
JH
429 type = PTR_TYPE_NOTE;
430 l = (struct leaf_node *)
23123aec 431 xcalloc(sizeof(struct leaf_node), 1);
a7e7eff6 432 hashcpy(l->key_sha1, object_sha1);
23123aec
JH
433 hashcpy(l->val_sha1, entry.sha1);
434 if (len < 20) {
851c2b37
JH
435 if (!S_ISDIR(entry.mode) || path_len != 2)
436 goto handle_non_note; /* not subtree */
23123aec
JH
437 l->key_sha1[19] = (unsigned char) len;
438 type = PTR_TYPE_SUBTREE;
439 }
851c2b37 440 note_tree_insert(t, node, n, l, type,
73f464b5 441 combine_notes_concatenate);
23123aec 442 }
851c2b37
JH
443 continue;
444
445handle_non_note:
446 /*
447 * Determine full path for this non-note entry:
448 * The filename is already found in entry.path, but the
449 * directory part of the path must be deduced from the subtree
450 * containing this entry. We assume here that the overall notes
451 * tree follows a strict byte-based progressive fanout
452 * structure (i.e. using 2/38, 2/2/36, etc. fanouts, and not
453 * e.g. 4/36 fanout). This means that if a non-note is found at
454 * path "dead/beef", the following code will register it as
455 * being found on "de/ad/beef".
456 * On the other hand, if you use such non-obvious non-note
457 * paths in the middle of a notes tree, you deserve what's
458 * coming to you ;). Note that for non-notes that are not
459 * SHA1-like at the top level, there will be no problems.
460 *
461 * To conclude, it is strongly advised to make sure non-notes
462 * have at least one non-hex character in the top-level path
463 * component.
464 */
465 {
466 char non_note_path[PATH_MAX];
467 char *p = non_note_path;
468 const char *q = sha1_to_hex(subtree->key_sha1);
469 int i;
470 for (i = 0; i < prefix_len; i++) {
471 *p++ = *q++;
472 *p++ = *q++;
473 *p++ = '/';
474 }
475 strcpy(p, entry.path);
476 add_non_note(t, non_note_path, entry.mode, entry.sha1);
477 }
23123aec
JH
478 }
479 free(buf);
480}
481
73f77b90
JH
482/*
483 * Determine optimal on-disk fanout for this part of the notes tree
484 *
485 * Given a (sub)tree and the level in the internal tree structure, determine
486 * whether or not the given existing fanout should be expanded for this
487 * (sub)tree.
488 *
489 * Values of the 'fanout' variable:
490 * - 0: No fanout (all notes are stored directly in the root notes tree)
491 * - 1: 2/38 fanout
492 * - 2: 2/2/36 fanout
493 * - 3: 2/2/2/34 fanout
494 * etc.
495 */
496static unsigned char determine_fanout(struct int_node *tree, unsigned char n,
497 unsigned char fanout)
498{
499 /*
500 * The following is a simple heuristic that works well in practice:
501 * For each even-numbered 16-tree level (remember that each on-disk
502 * fanout level corresponds to _two_ 16-tree levels), peek at all 16
503 * entries at that tree level. If all of them are either int_nodes or
504 * subtree entries, then there are likely plenty of notes below this
505 * level, so we return an incremented fanout.
506 */
507 unsigned int i;
508 if ((n % 2) || (n > 2 * fanout))
509 return fanout;
510 for (i = 0; i < 16; i++) {
511 switch (GET_PTR_TYPE(tree->a[i])) {
512 case PTR_TYPE_SUBTREE:
513 case PTR_TYPE_INTERNAL:
514 continue;
515 default:
516 return fanout;
517 }
518 }
519 return fanout + 1;
520}
521
522static void construct_path_with_fanout(const unsigned char *sha1,
523 unsigned char fanout, char *path)
524{
525 unsigned int i = 0, j = 0;
526 const char *hex_sha1 = sha1_to_hex(sha1);
527 assert(fanout < 20);
528 while (fanout) {
529 path[i++] = hex_sha1[j++];
530 path[i++] = hex_sha1[j++];
531 path[i++] = '/';
532 fanout--;
533 }
534 strcpy(path + i, hex_sha1 + j);
535}
536
851c2b37
JH
537static int for_each_note_helper(struct notes_tree *t, struct int_node *tree,
538 unsigned char n, unsigned char fanout, int flags,
539 each_note_fn fn, void *cb_data)
73f77b90
JH
540{
541 unsigned int i;
542 void *p;
543 int ret = 0;
544 struct leaf_node *l;
545 static char path[40 + 19 + 1]; /* hex SHA1 + 19 * '/' + NUL */
546
547 fanout = determine_fanout(tree, n, fanout);
548 for (i = 0; i < 16; i++) {
549redo:
550 p = tree->a[i];
551 switch (GET_PTR_TYPE(p)) {
552 case PTR_TYPE_INTERNAL:
553 /* recurse into int_node */
851c2b37 554 ret = for_each_note_helper(t, CLR_PTR_TYPE(p), n + 1,
73f77b90
JH
555 fanout, flags, fn, cb_data);
556 break;
557 case PTR_TYPE_SUBTREE:
558 l = (struct leaf_node *) CLR_PTR_TYPE(p);
559 /*
560 * Subtree entries in the note tree represent parts of
561 * the note tree that have not yet been explored. There
562 * is a direct relationship between subtree entries at
563 * level 'n' in the tree, and the 'fanout' variable:
564 * Subtree entries at level 'n <= 2 * fanout' should be
565 * preserved, since they correspond exactly to a fanout
566 * directory in the on-disk structure. However, subtree
567 * entries at level 'n > 2 * fanout' should NOT be
568 * preserved, but rather consolidated into the above
569 * notes tree level. We achieve this by unconditionally
570 * unpacking subtree entries that exist below the
571 * threshold level at 'n = 2 * fanout'.
572 */
573 if (n <= 2 * fanout &&
574 flags & FOR_EACH_NOTE_YIELD_SUBTREES) {
575 /* invoke callback with subtree */
576 unsigned int path_len =
577 l->key_sha1[19] * 2 + fanout;
578 assert(path_len < 40 + 19);
579 construct_path_with_fanout(l->key_sha1, fanout,
580 path);
581 /* Create trailing slash, if needed */
582 if (path[path_len - 1] != '/')
583 path[path_len++] = '/';
584 path[path_len] = '\0';
585 ret = fn(l->key_sha1, l->val_sha1, path,
586 cb_data);
587 }
588 if (n > fanout * 2 ||
589 !(flags & FOR_EACH_NOTE_DONT_UNPACK_SUBTREES)) {
590 /* unpack subtree and resume traversal */
591 tree->a[i] = NULL;
851c2b37 592 load_subtree(t, l, tree, n);
73f77b90
JH
593 free(l);
594 goto redo;
595 }
596 break;
597 case PTR_TYPE_NOTE:
598 l = (struct leaf_node *) CLR_PTR_TYPE(p);
599 construct_path_with_fanout(l->key_sha1, fanout, path);
600 ret = fn(l->key_sha1, l->val_sha1, path, cb_data);
601 break;
602 }
603 if (ret)
604 return ret;
605 }
606 return 0;
607}
608
61a7cca0
JH
609struct tree_write_stack {
610 struct tree_write_stack *next;
611 struct strbuf buf;
612 char path[2]; /* path to subtree in next, if any */
613};
614
615static inline int matches_tree_write_stack(struct tree_write_stack *tws,
616 const char *full_path)
617{
618 return full_path[0] == tws->path[0] &&
619 full_path[1] == tws->path[1] &&
620 full_path[2] == '/';
621}
622
623static void write_tree_entry(struct strbuf *buf, unsigned int mode,
624 const char *path, unsigned int path_len, const
625 unsigned char *sha1)
626{
627 strbuf_addf(buf, "%06o %.*s%c", mode, path_len, path, '\0');
628 strbuf_add(buf, sha1, 20);
629}
630
631static void tree_write_stack_init_subtree(struct tree_write_stack *tws,
632 const char *path)
633{
634 struct tree_write_stack *n;
635 assert(!tws->next);
636 assert(tws->path[0] == '\0' && tws->path[1] == '\0');
637 n = (struct tree_write_stack *)
638 xmalloc(sizeof(struct tree_write_stack));
639 n->next = NULL;
640 strbuf_init(&n->buf, 256 * (32 + 40)); /* assume 256 entries per tree */
641 n->path[0] = n->path[1] = '\0';
642 tws->next = n;
643 tws->path[0] = path[0];
644 tws->path[1] = path[1];
645}
646
647static int tree_write_stack_finish_subtree(struct tree_write_stack *tws)
648{
649 int ret;
650 struct tree_write_stack *n = tws->next;
651 unsigned char s[20];
652 if (n) {
653 ret = tree_write_stack_finish_subtree(n);
654 if (ret)
655 return ret;
656 ret = write_sha1_file(n->buf.buf, n->buf.len, tree_type, s);
657 if (ret)
658 return ret;
659 strbuf_release(&n->buf);
660 free(n);
661 tws->next = NULL;
662 write_tree_entry(&tws->buf, 040000, tws->path, 2, s);
663 tws->path[0] = tws->path[1] = '\0';
664 }
665 return 0;
666}
667
668static int write_each_note_helper(struct tree_write_stack *tws,
669 const char *path, unsigned int mode,
670 const unsigned char *sha1)
671{
672 size_t path_len = strlen(path);
673 unsigned int n = 0;
674 int ret;
675
676 /* Determine common part of tree write stack */
677 while (tws && 3 * n < path_len &&
678 matches_tree_write_stack(tws, path + 3 * n)) {
679 n++;
680 tws = tws->next;
681 }
682
683 /* tws point to last matching tree_write_stack entry */
684 ret = tree_write_stack_finish_subtree(tws);
685 if (ret)
686 return ret;
687
688 /* Start subtrees needed to satisfy path */
689 while (3 * n + 2 < path_len && path[3 * n + 2] == '/') {
690 tree_write_stack_init_subtree(tws, path + 3 * n);
691 n++;
692 tws = tws->next;
693 }
694
695 /* There should be no more directory components in the given path */
696 assert(memchr(path + 3 * n, '/', path_len - (3 * n)) == NULL);
697
698 /* Finally add given entry to the current tree object */
699 write_tree_entry(&tws->buf, mode, path + 3 * n, path_len - (3 * n),
700 sha1);
701
702 return 0;
703}
704
705struct write_each_note_data {
706 struct tree_write_stack *root;
851c2b37 707 struct non_note *next_non_note;
61a7cca0
JH
708};
709
851c2b37
JH
710static int write_each_non_note_until(const char *note_path,
711 struct write_each_note_data *d)
712{
713 struct non_note *n = d->next_non_note;
714 int cmp, ret;
715 while (n && (!note_path || (cmp = strcmp(n->path, note_path)) <= 0)) {
716 if (note_path && cmp == 0)
717 ; /* do nothing, prefer note to non-note */
718 else {
719 ret = write_each_note_helper(d->root, n->path, n->mode,
720 n->sha1);
721 if (ret)
722 return ret;
723 }
724 n = n->next;
725 }
726 d->next_non_note = n;
727 return 0;
728}
729
61a7cca0
JH
730static int write_each_note(const unsigned char *object_sha1,
731 const unsigned char *note_sha1, char *note_path,
732 void *cb_data)
733{
734 struct write_each_note_data *d =
735 (struct write_each_note_data *) cb_data;
736 size_t note_path_len = strlen(note_path);
737 unsigned int mode = 0100644;
738
739 if (note_path[note_path_len - 1] == '/') {
740 /* subtree entry */
741 note_path_len--;
742 note_path[note_path_len] = '\0';
743 mode = 040000;
744 }
745 assert(note_path_len <= 40 + 19);
746
851c2b37
JH
747 /* Weave non-note entries into note entries */
748 return write_each_non_note_until(note_path, d) ||
749 write_each_note_helper(d->root, note_path, mode, note_sha1);
61a7cca0
JH
750}
751
00fbe636
JH
752struct note_delete_list {
753 struct note_delete_list *next;
754 const unsigned char *sha1;
755};
756
757static int prune_notes_helper(const unsigned char *object_sha1,
758 const unsigned char *note_sha1, char *note_path,
759 void *cb_data)
760{
761 struct note_delete_list **l = (struct note_delete_list **) cb_data;
762 struct note_delete_list *n;
763
764 if (has_sha1_file(object_sha1))
765 return 0; /* nothing to do for this note */
766
767 /* failed to find object => prune this note */
768 n = (struct note_delete_list *) xmalloc(sizeof(*n));
769 n->next = *l;
770 n->sha1 = object_sha1;
771 *l = n;
772 return 0;
773}
774
73f464b5
JH
775int combine_notes_concatenate(unsigned char *cur_sha1,
776 const unsigned char *new_sha1)
777{
778 char *cur_msg = NULL, *new_msg = NULL, *buf;
779 unsigned long cur_len, new_len, buf_len;
780 enum object_type cur_type, new_type;
781 int ret;
782
783 /* read in both note blob objects */
784 if (!is_null_sha1(new_sha1))
785 new_msg = read_sha1_file(new_sha1, &new_type, &new_len);
786 if (!new_msg || !new_len || new_type != OBJ_BLOB) {
787 free(new_msg);
788 return 0;
789 }
790 if (!is_null_sha1(cur_sha1))
791 cur_msg = read_sha1_file(cur_sha1, &cur_type, &cur_len);
792 if (!cur_msg || !cur_len || cur_type != OBJ_BLOB) {
793 free(cur_msg);
794 free(new_msg);
795 hashcpy(cur_sha1, new_sha1);
796 return 0;
797 }
798
799 /* we will separate the notes by a newline anyway */
800 if (cur_msg[cur_len - 1] == '\n')
801 cur_len--;
802
803 /* concatenate cur_msg and new_msg into buf */
804 buf_len = cur_len + 1 + new_len;
805 buf = (char *) xmalloc(buf_len);
806 memcpy(buf, cur_msg, cur_len);
807 buf[cur_len] = '\n';
808 memcpy(buf + cur_len + 1, new_msg, new_len);
809 free(cur_msg);
810 free(new_msg);
811
812 /* create a new blob object from buf */
813 ret = write_sha1_file(buf, buf_len, blob_type, cur_sha1);
814 free(buf);
815 return ret;
816}
817
818int combine_notes_overwrite(unsigned char *cur_sha1,
819 const unsigned char *new_sha1)
820{
821 hashcpy(cur_sha1, new_sha1);
822 return 0;
823}
824
825int combine_notes_ignore(unsigned char *cur_sha1,
826 const unsigned char *new_sha1)
827{
828 return 0;
829}
830
831void init_notes(struct notes_tree *t, const char *notes_ref,
832 combine_notes_fn combine_notes, int flags)
23123aec 833{
a7e7eff6 834 unsigned char sha1[20], object_sha1[20];
23123aec
JH
835 unsigned mode;
836 struct leaf_node root_tree;
fd53c9eb 837
cd305392
JH
838 if (!t)
839 t = &default_notes_tree;
840 assert(!t->initialized);
709f79b0
JH
841
842 if (!notes_ref)
843 notes_ref = getenv(GIT_NOTES_REF_ENVIRONMENT);
844 if (!notes_ref)
845 notes_ref = notes_ref_name; /* value of core.notesRef config */
846 if (!notes_ref)
847 notes_ref = GIT_NOTES_DEFAULT_REF;
848
73f464b5
JH
849 if (!combine_notes)
850 combine_notes = combine_notes_concatenate;
851
cd305392 852 t->root = (struct int_node *) xcalloc(sizeof(struct int_node), 1);
851c2b37
JH
853 t->first_non_note = NULL;
854 t->prev_non_note = NULL;
cd305392 855 t->ref = notes_ref ? xstrdup(notes_ref) : NULL;
73f464b5 856 t->combine_notes = combine_notes;
cd305392
JH
857 t->initialized = 1;
858
709f79b0
JH
859 if (flags & NOTES_INIT_EMPTY || !notes_ref ||
860 read_ref(notes_ref, object_sha1))
fd53c9eb 861 return;
709f79b0
JH
862 if (get_tree_entry(object_sha1, "", sha1, &mode))
863 die("Failed to read notes tree referenced by %s (%s)",
864 notes_ref, object_sha1);
fd53c9eb 865
23123aec
JH
866 hashclr(root_tree.key_sha1);
867 hashcpy(root_tree.val_sha1, sha1);
851c2b37 868 load_subtree(t, &root_tree, t->root, 0);
fd53c9eb
JS
869}
870
cd305392 871void add_note(struct notes_tree *t, const unsigned char *object_sha1,
73f464b5 872 const unsigned char *note_sha1, combine_notes_fn combine_notes)
2626b536
JH
873{
874 struct leaf_node *l;
875
cd305392
JH
876 if (!t)
877 t = &default_notes_tree;
878 assert(t->initialized);
73f464b5
JH
879 if (!combine_notes)
880 combine_notes = t->combine_notes;
2626b536
JH
881 l = (struct leaf_node *) xmalloc(sizeof(struct leaf_node));
882 hashcpy(l->key_sha1, object_sha1);
883 hashcpy(l->val_sha1, note_sha1);
851c2b37 884 note_tree_insert(t, t->root, 0, l, PTR_TYPE_NOTE, combine_notes);
2626b536
JH
885}
886
cd305392 887void remove_note(struct notes_tree *t, const unsigned char *object_sha1)
1ec666b0
JH
888{
889 struct leaf_node l;
890
cd305392
JH
891 if (!t)
892 t = &default_notes_tree;
893 assert(t->initialized);
1ec666b0
JH
894 hashcpy(l.key_sha1, object_sha1);
895 hashclr(l.val_sha1);
cd305392 896 return note_tree_remove(t, t->root, 0, &l);
1ec666b0
JH
897}
898
cd305392
JH
899const unsigned char *get_note(struct notes_tree *t,
900 const unsigned char *object_sha1)
fd53c9eb 901{
9b391f21
JH
902 struct leaf_node *found;
903
cd305392
JH
904 if (!t)
905 t = &default_notes_tree;
906 assert(t->initialized);
851c2b37 907 found = note_tree_find(t, t->root, 0, object_sha1);
9b391f21 908 return found ? found->val_sha1 : NULL;
fd53c9eb 909}
a97a7468 910
cd305392
JH
911int for_each_note(struct notes_tree *t, int flags, each_note_fn fn,
912 void *cb_data)
73f77b90 913{
cd305392
JH
914 if (!t)
915 t = &default_notes_tree;
916 assert(t->initialized);
851c2b37 917 return for_each_note_helper(t, t->root, 0, 0, flags, fn, cb_data);
73f77b90
JH
918}
919
cd305392 920int write_notes_tree(struct notes_tree *t, unsigned char *result)
61a7cca0
JH
921{
922 struct tree_write_stack root;
923 struct write_each_note_data cb_data;
924 int ret;
925
cd305392
JH
926 if (!t)
927 t = &default_notes_tree;
928 assert(t->initialized);
61a7cca0
JH
929
930 /* Prepare for traversal of current notes tree */
931 root.next = NULL; /* last forward entry in list is grounded */
932 strbuf_init(&root.buf, 256 * (32 + 40)); /* assume 256 entries */
933 root.path[0] = root.path[1] = '\0';
934 cb_data.root = &root;
851c2b37 935 cb_data.next_non_note = t->first_non_note;
61a7cca0
JH
936
937 /* Write tree objects representing current notes tree */
cd305392 938 ret = for_each_note(t, FOR_EACH_NOTE_DONT_UNPACK_SUBTREES |
61a7cca0
JH
939 FOR_EACH_NOTE_YIELD_SUBTREES,
940 write_each_note, &cb_data) ||
851c2b37 941 write_each_non_note_until(NULL, &cb_data) ||
61a7cca0
JH
942 tree_write_stack_finish_subtree(&root) ||
943 write_sha1_file(root.buf.buf, root.buf.len, tree_type, result);
944 strbuf_release(&root.buf);
945 return ret;
946}
947
00fbe636
JH
948void prune_notes(struct notes_tree *t)
949{
950 struct note_delete_list *l = NULL;
951
952 if (!t)
953 t = &default_notes_tree;
954 assert(t->initialized);
955
956 for_each_note(t, 0, prune_notes_helper, &l);
957
958 while (l) {
959 remove_note(t, l->sha1);
960 l = l->next;
961 }
962}
963
cd305392 964void free_notes(struct notes_tree *t)
27d57564 965{
cd305392
JH
966 if (!t)
967 t = &default_notes_tree;
968 if (t->root)
969 note_tree_free(t->root);
970 free(t->root);
851c2b37
JH
971 while (t->first_non_note) {
972 t->prev_non_note = t->first_non_note->next;
973 free(t->first_non_note->path);
974 free(t->first_non_note);
975 t->first_non_note = t->prev_non_note;
976 }
cd305392
JH
977 free(t->ref);
978 memset(t, 0, sizeof(struct notes_tree));
27d57564
JH
979}
980
cd305392
JH
981void format_note(struct notes_tree *t, const unsigned char *object_sha1,
982 struct strbuf *sb, const char *output_encoding, int flags)
a97a7468
JS
983{
984 static const char utf8[] = "utf-8";
9b391f21 985 const unsigned char *sha1;
a97a7468
JS
986 char *msg, *msg_p;
987 unsigned long linelen, msglen;
988 enum object_type type;
989
cd305392
JH
990 if (!t)
991 t = &default_notes_tree;
992 if (!t->initialized)
73f464b5 993 init_notes(t, NULL, NULL, 0);
a97a7468 994
cd305392 995 sha1 = get_note(t, object_sha1);
fd53c9eb 996 if (!sha1)
a97a7468
JS
997 return;
998
999 if (!(msg = read_sha1_file(sha1, &type, &msglen)) || !msglen ||
1000 type != OBJ_BLOB) {
1001 free(msg);
1002 return;
1003 }
1004
1005 if (output_encoding && *output_encoding &&
1006 strcmp(utf8, output_encoding)) {
1007 char *reencoded = reencode_string(msg, output_encoding, utf8);
1008 if (reencoded) {
1009 free(msg);
1010 msg = reencoded;
1011 msglen = strlen(msg);
1012 }
1013 }
1014
1015 /* we will end the annotation by a newline anyway */
1016 if (msglen && msg[msglen - 1] == '\n')
1017 msglen--;
1018
c56fcc89
JH
1019 if (flags & NOTES_SHOW_HEADER)
1020 strbuf_addstr(sb, "\nNotes:\n");
a97a7468
JS
1021
1022 for (msg_p = msg; msg_p < msg + msglen; msg_p += linelen + 1) {
1023 linelen = strchrnul(msg_p, '\n') - msg_p;
1024
c56fcc89
JH
1025 if (flags & NOTES_INDENT)
1026 strbuf_addstr(sb, " ");
a97a7468
JS
1027 strbuf_add(sb, msg_p, linelen);
1028 strbuf_addch(sb, '\n');
1029 }
1030
1031 free(msg);
1032}