notes.c 36.2 KB
Newer Older
1
#include "cache.h"
2
#include "config.h"
3
#include "notes.h"
4
#include "object-store.h"
5
#include "blob.h"
6
#include "tree.h"
7 8
#include "utf8.h"
#include "strbuf.h"
9
#include "tree-walk.h"
10 11
#include "string-list.h"
#include "refs.h"
12

13 14 15 16 17 18 19 20 21 22 23 24 25 26
/*
 * Use a non-balancing simple 16-tree structure with struct int_node as
 * internal nodes, and struct leaf_node as leaf nodes. Each int_node has a
 * 16-array of pointers to its children.
 * The bottom 2 bits of each pointer is used to identify the pointer type
 * - ptr & 3 == 0 - NULL pointer, assert(ptr == NULL)
 * - ptr & 3 == 1 - pointer to next internal node - cast to struct int_node *
 * - ptr & 3 == 2 - pointer to note entry - cast to struct leaf_node *
 * - ptr & 3 == 3 - pointer to subtree entry - cast to struct leaf_node *
 *
 * The root node is a statically allocated struct int_node.
 */
struct int_node {
	void *a[16];
27 28
};

29 30 31
/*
 * Leaf nodes come in two variants, note entries and subtree entries,
 * distinguished by the LSb of the leaf node pointer (see above).
32
 * As a note entry, the key is the SHA1 of the referenced object, and the
33 34
 * value is the SHA1 of the note object.
 * As a subtree entry, the key is the prefix SHA1 (w/trailing NULs) of the
35
 * referenced object, using the last byte of the key to store the length of
36 37 38 39
 * the prefix. The value is the SHA1 of the tree object containing the notes
 * subtree.
 */
struct leaf_node {
40 41
	struct object_id key_oid;
	struct object_id val_oid;
42
};
43

44 45 46 47 48 49 50 51 52 53 54 55
/*
 * A notes tree may contain entries that are not notes, and that do not follow
 * the naming conventions of notes. There are typically none/few of these, but
 * we still need to keep track of them. Keep a simple linked list sorted alpha-
 * betically on the non-note path. The list is populated when parsing tree
 * objects in load_subtree(), and the non-notes are correctly written back into
 * the tree objects produced by write_notes_tree().
 */
struct non_note {
	struct non_note *next; /* grounded (last->next == NULL) */
	char *path;
	unsigned int mode;
56
	struct object_id oid;
57 58
};

59 60 61 62
#define PTR_TYPE_NULL     0
#define PTR_TYPE_INTERNAL 1
#define PTR_TYPE_NOTE     2
#define PTR_TYPE_SUBTREE  3
63

64 65 66
#define GET_PTR_TYPE(ptr)       ((uintptr_t) (ptr) & 3)
#define CLR_PTR_TYPE(ptr)       ((void *) ((uintptr_t) (ptr) & ~3))
#define SET_PTR_TYPE(ptr, type) ((void *) ((uintptr_t) (ptr) | (type)))
67

68
#define GET_NIBBLE(n, sha1) ((((sha1)[(n) >> 1]) >> ((~(n) & 0x01) << 2)) & 0x0f)
69

70 71
#define KEY_INDEX (GIT_SHA1_RAWSZ - 1)
#define FANOUT_PATH_SEPARATORS ((GIT_SHA1_HEXSZ / 2) - 1)
72
#define SUBTREE_SHA1_PREFIXCMP(key_sha1, subtree_sha1) \
73
	(memcmp(key_sha1, subtree_sha1, subtree_sha1[KEY_INDEX]))
74

75
struct notes_tree default_notes_tree;
76

77
static struct string_list display_notes_refs = STRING_LIST_INIT_NODUP;
78 79
static struct notes_tree **display_notes_trees;

80 81
static void load_subtree(struct notes_tree *t, struct leaf_node *subtree,
		struct int_node *node, unsigned int n);
82 83

/*
84
 * Search the tree until the appropriate location for the given key is found:
85
 * 1. Start at the root node, with n = 0
86 87 88 89
 * 2. If a[0] at the current level is a matching subtree entry, unpack that
 *    subtree entry and remove it; restart search at the current level.
 * 3. Use the nth nibble of the key as an index into a:
 *    - If a[n] is an int_node, recurse from #2 into that node and increment n
90 91
 *    - If a matching subtree entry, unpack that subtree entry (and remove it);
 *      restart search at the current level.
92 93 94 95 96
 *    - Otherwise, we have found one of the following:
 *      - a subtree entry which does not match the key
 *      - a note entry which may or may not match the key
 *      - an unused leaf node (NULL)
 *      In any case, set *tree and *n, and return pointer to the tree location.
97
 */
98
static void **note_tree_search(struct notes_tree *t, struct int_node **tree,
99
		unsigned char *n, const unsigned char *key_sha1)
100 101
{
	struct leaf_node *l;
102 103
	unsigned char i;
	void *p = (*tree)->a[0];
104

105 106
	if (GET_PTR_TYPE(p) == PTR_TYPE_SUBTREE) {
		l = (struct leaf_node *) CLR_PTR_TYPE(p);
107
		if (!SUBTREE_SHA1_PREFIXCMP(key_sha1, l->key_oid.hash)) {
108 109
			/* unpack tree and resume search */
			(*tree)->a[0] = NULL;
110
			load_subtree(t, l, *tree, *n);
111
			free(l);
112
			return note_tree_search(t, tree, n, key_sha1);
113 114 115 116 117
		}
	}

	i = GET_NIBBLE(*n, key_sha1);
	p = (*tree)->a[i];
118
	switch (GET_PTR_TYPE(p)) {
119
	case PTR_TYPE_INTERNAL:
120 121
		*tree = CLR_PTR_TYPE(p);
		(*n)++;
122
		return note_tree_search(t, tree, n, key_sha1);
123 124
	case PTR_TYPE_SUBTREE:
		l = (struct leaf_node *) CLR_PTR_TYPE(p);
125
		if (!SUBTREE_SHA1_PREFIXCMP(key_sha1, l->key_oid.hash)) {
126
			/* unpack tree and resume search */
127
			(*tree)->a[i] = NULL;
128
			load_subtree(t, l, *tree, *n);
129
			free(l);
130
			return note_tree_search(t, tree, n, key_sha1);
131
		}
132
		/* fall through */
133
	default:
134
		return &((*tree)->a[i]);
135
	}
136
}
137

138 139 140 141 142
/*
 * To find a leaf_node:
 * Search to the tree location appropriate for the given key:
 * If a note entry with matching key, return the note entry, else return NULL.
 */
143 144
static struct leaf_node *note_tree_find(struct notes_tree *t,
		struct int_node *tree, unsigned char n,
145 146
		const unsigned char *key_sha1)
{
147
	void **p = note_tree_search(t, &tree, &n, key_sha1);
148 149
	if (GET_PTR_TYPE(*p) == PTR_TYPE_NOTE) {
		struct leaf_node *l = (struct leaf_node *) CLR_PTR_TYPE(*p);
150
		if (hasheq(key_sha1, l->key_oid.hash))
151
			return l;
152 153
	}
	return NULL;
154 155
}

156 157 158 159
/*
 * How to consolidate an int_node:
 * If there are > 1 non-NULL entries, give up and return non-zero.
 * Otherwise replace the int_node at the given index in the given parent node
160 161
 * with the only NOTE entry (or a NULL entry if no entries) from the given
 * tree, and return 0.
162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179
 */
static int note_tree_consolidate(struct int_node *tree,
	struct int_node *parent, unsigned char index)
{
	unsigned int i;
	void *p = NULL;

	assert(tree && parent);
	assert(CLR_PTR_TYPE(parent->a[index]) == tree);

	for (i = 0; i < 16; i++) {
		if (GET_PTR_TYPE(tree->a[i]) != PTR_TYPE_NULL) {
			if (p) /* more than one entry */
				return -2;
			p = tree->a[i];
		}
	}

180 181
	if (p && (GET_PTR_TYPE(p) != PTR_TYPE_NOTE))
		return -2;
182 183 184 185 186 187 188 189 190 191
	/* replace tree with p in parent[index] */
	parent->a[index] = p;
	free(tree);
	return 0;
}

/*
 * To remove a leaf_node:
 * Search to the tree location appropriate for the given leaf_node's key:
 * - If location does not hold a matching entry, abort and do nothing.
192
 * - Copy the matching entry's value into the given entry.
193 194 195
 * - Replace the matching leaf_node with a NULL entry (and free the leaf_node).
 * - Consolidate int_nodes repeatedly, while walking up the tree towards root.
 */
196 197 198
static void note_tree_remove(struct notes_tree *t,
		struct int_node *tree, unsigned char n,
		struct leaf_node *entry)
199 200
{
	struct leaf_node *l;
201
	struct int_node *parent_stack[GIT_SHA1_RAWSZ];
202
	unsigned char i, j;
203
	void **p = note_tree_search(t, &tree, &n, entry->key_oid.hash);
204 205 206 207 208

	assert(GET_PTR_TYPE(entry) == 0); /* no type bits set */
	if (GET_PTR_TYPE(*p) != PTR_TYPE_NOTE)
		return; /* type mismatch, nothing to remove */
	l = (struct leaf_node *) CLR_PTR_TYPE(*p);
209
	if (!oideq(&l->key_oid, &entry->key_oid))
210 211 212
		return; /* key mismatch, nothing to remove */

	/* we have found a matching entry */
213
	oidcpy(&entry->val_oid, &l->val_oid);
214 215 216 217 218 219 220
	free(l);
	*p = SET_PTR_TYPE(NULL, PTR_TYPE_NULL);

	/* consolidate this tree level, and parent levels, if possible */
	if (!n)
		return; /* cannot consolidate top level */
	/* first, build stack of ancestors between root and current node */
221
	parent_stack[0] = t->root;
222
	for (i = 0; i < n; i++) {
223
		j = GET_NIBBLE(i, entry->key_oid.hash);
224 225 226 227 228 229
		parent_stack[i + 1] = CLR_PTR_TYPE(parent_stack[i]->a[j]);
	}
	assert(i == n && parent_stack[i] == tree);
	/* next, unwind stack until note_tree_consolidate() is done */
	while (i > 0 &&
	       !note_tree_consolidate(parent_stack[i], parent_stack[i - 1],
230
				      GET_NIBBLE(i - 1, entry->key_oid.hash)))
231 232 233
		i--;
}

234 235
/*
 * To insert a leaf_node:
236 237 238
 * Search to the tree location appropriate for the given leaf_node's key:
 * - If location is unused (NULL), store the tweaked pointer directly there
 * - If location holds a note entry that matches the note-to-be-inserted, then
239
 *   combine the two notes (by calling the given combine_notes function).
240 241 242 243 244 245
 * - If location holds a note entry that matches the subtree-to-be-inserted,
 *   then unpack the subtree-to-be-inserted into the location.
 * - If location holds a matching subtree entry, unpack the subtree at that
 *   location, and restart the insert operation from that level.
 * - Else, create a new int_node, holding both the node-at-location and the
 *   node-to-be-inserted, and store the new int_node into the location.
246
 */
247
static int note_tree_insert(struct notes_tree *t, struct int_node *tree,
248
		unsigned char n, struct leaf_node *entry, unsigned char type,
249
		combine_notes_fn combine_notes)
250
{
251
	struct int_node *new_node;
252
	struct leaf_node *l;
253
	void **p = note_tree_search(t, &tree, &n, entry->key_oid.hash);
254
	int ret = 0;
255 256 257

	assert(GET_PTR_TYPE(entry) == 0); /* no type bits set */
	l = (struct leaf_node *) CLR_PTR_TYPE(*p);
258
	switch (GET_PTR_TYPE(*p)) {
259
	case PTR_TYPE_NULL:
260
		assert(!*p);
261
		if (is_null_oid(&entry->val_oid))
262 263 264
			free(entry);
		else
			*p = SET_PTR_TYPE(entry, type);
265
		return 0;
266 267 268
	case PTR_TYPE_NOTE:
		switch (type) {
		case PTR_TYPE_NOTE:
269
			if (oideq(&l->key_oid, &entry->key_oid)) {
270
				/* skip concatenation if l == entry */
271
				if (oideq(&l->val_oid, &entry->val_oid))
272
					return 0;
273

274 275
				ret = combine_notes(&l->val_oid,
						    &entry->val_oid);
276
				if (!ret && is_null_oid(&l->val_oid))
277
					note_tree_remove(t, tree, n, entry);
278
				free(entry);
279
				return ret;
280 281 282
			}
			break;
		case PTR_TYPE_SUBTREE:
283 284
			if (!SUBTREE_SHA1_PREFIXCMP(l->key_oid.hash,
						    entry->key_oid.hash)) {
285
				/* unpack 'entry' */
286
				load_subtree(t, entry, tree, n);
287
				free(entry);
288
				return 0;
289 290 291 292 293
			}
			break;
		}
		break;
	case PTR_TYPE_SUBTREE:
294
		if (!SUBTREE_SHA1_PREFIXCMP(entry->key_oid.hash, l->key_oid.hash)) {
295 296
			/* unpack 'l' and restart insert */
			*p = NULL;
297
			load_subtree(t, l, tree, n);
298
			free(l);
299 300
			return note_tree_insert(t, tree, n, entry, type,
						combine_notes);
301
		}
302
		break;
303
	}
304 305 306 307

	/* non-matching leaf_node */
	assert(GET_PTR_TYPE(*p) == PTR_TYPE_NOTE ||
	       GET_PTR_TYPE(*p) == PTR_TYPE_SUBTREE);
308
	if (is_null_oid(&entry->val_oid)) { /* skip insertion of empty note */
309
		free(entry);
310
		return 0;
311
	}
312
	new_node = (struct int_node *) xcalloc(1, sizeof(struct int_node));
313 314 315 316
	ret = note_tree_insert(t, new_node, n + 1, l, GET_PTR_TYPE(*p),
			       combine_notes);
	if (ret)
		return ret;
317
	*p = SET_PTR_TYPE(new_node, PTR_TYPE_INTERNAL);
318
	return note_tree_insert(t, new_node, n + 1, entry, type, combine_notes);
319
}
320

321 322 323 324 325 326
/* Free the entire notes data contained in the given tree */
static void note_tree_free(struct int_node *tree)
{
	unsigned int i;
	for (i = 0; i < 16; i++) {
		void *p = tree->a[i];
327
		switch (GET_PTR_TYPE(p)) {
328 329 330 331 332 333 334
		case PTR_TYPE_INTERNAL:
			note_tree_free(CLR_PTR_TYPE(p));
			/* fall through */
		case PTR_TYPE_NOTE:
		case PTR_TYPE_SUBTREE:
			free(CLR_PTR_TYPE(p));
		}
335
	}
336
}
337

338 339 340 341 342
static int non_note_cmp(const struct non_note *a, const struct non_note *b)
{
	return strcmp(a->path, b->path);
}

343 344
/* note: takes ownership of path string */
static void add_non_note(struct notes_tree *t, char *path,
345 346 347 348 349
		unsigned int mode, const unsigned char *sha1)
{
	struct non_note *p = t->prev_non_note, *n;
	n = (struct non_note *) xmalloc(sizeof(struct non_note));
	n->next = NULL;
350
	n->path = path;
351
	n->mode = mode;
352
	hashcpy(n->oid.hash, sha1);
353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377
	t->prev_non_note = n;

	if (!t->first_non_note) {
		t->first_non_note = n;
		return;
	}

	if (non_note_cmp(p, n) < 0)
		; /* do nothing  */
	else if (non_note_cmp(t->first_non_note, n) <= 0)
		p = t->first_non_note;
	else {
		/* n sorts before t->first_non_note */
		n->next = t->first_non_note;
		t->first_non_note = n;
		return;
	}

	/* n sorts equal or after p */
	while (p->next && non_note_cmp(p->next, n) <= 0)
		p = p->next;

	if (non_note_cmp(p, n) == 0) { /* n ~= p; overwrite p with n */
		assert(strcmp(p->path, n->path) == 0);
		p->mode = n->mode;
378
		oidcpy(&p->oid, &n->oid);
379 380 381 382 383 384 385 386 387 388 389 390
		free(n);
		t->prev_non_note = p;
		return;
	}

	/* n sorts between p and p->next */
	n->next = p->next;
	p->next = n;
}

static void load_subtree(struct notes_tree *t, struct leaf_node *subtree,
		struct int_node *node, unsigned int n)
391
{
392
	struct object_id object_oid;
393
	size_t prefix_len;
394
	void *buf;
395 396
	struct tree_desc desc;
	struct name_entry entry;
397

398
	buf = fill_tree_descriptor(&desc, &subtree->val_oid);
399 400
	if (!buf)
		die("Could not read %s for notes-index",
401
		     oid_to_hex(&subtree->val_oid));
402

403
	prefix_len = subtree->key_oid.hash[KEY_INDEX];
404 405 406 407
	if (prefix_len >= GIT_SHA1_RAWSZ)
		BUG("prefix_len (%"PRIuMAX") is out of range", (uintmax_t)prefix_len);
	if (prefix_len * 2 < n)
		BUG("prefix_len (%"PRIuMAX") is too small", (uintmax_t)prefix_len);
408
	memcpy(object_oid.hash, subtree->key_oid.hash, prefix_len);
409
	while (tree_entry(&desc, &entry)) {
410 411
		unsigned char type;
		struct leaf_node *l;
412
		size_t path_len = strlen(entry.path);
413 414 415

		if (path_len == 2 * (GIT_SHA1_RAWSZ - prefix_len)) {
			/* This is potentially the remainder of the SHA-1 */
416 417 418 419 420

			if (!S_ISREG(entry.mode))
				/* notes must be blobs */
				goto handle_non_note;

421 422
			if (hex_to_bytes(object_oid.hash + prefix_len, entry.path,
					 GIT_SHA1_RAWSZ - prefix_len))
423
				goto handle_non_note; /* entry.path is not a SHA1 */
424

425
			type = PTR_TYPE_NOTE;
426 427
		} else if (path_len == 2) {
			/* This is potentially an internal node */
428
			size_t len = prefix_len;
429 430 431 432 433

			if (!S_ISDIR(entry.mode))
				/* internal nodes must be trees */
				goto handle_non_note;

434
			if (hex_to_bytes(object_oid.hash + len++, entry.path, 1))
435
				goto handle_non_note; /* entry.path is not a SHA1 */
436

437 438 439 440 441 442 443
			/*
			 * Pad the rest of the SHA-1 with zeros,
			 * except for the last byte, where we write
			 * the length:
			 */
			memset(object_oid.hash + len, 0, GIT_SHA1_RAWSZ - len - 1);
			object_oid.hash[KEY_INDEX] = (unsigned char)len;
444

445
			type = PTR_TYPE_SUBTREE;
446 447 448
		} else {
			/* This can't be part of a note */
			goto handle_non_note;
449
		}
450

451 452
		l = xcalloc(1, sizeof(*l));
		oidcpy(&l->key_oid, &object_oid);
453
		oidcpy(&l->val_oid, &entry.oid);
454 455 456 457 458 459 460
		if (note_tree_insert(t, node, n, l, type,
				     combine_notes_concatenate))
			die("Failed to load %s %s into notes tree "
			    "from %s",
			    type == PTR_TYPE_NOTE ? "note" : "subtree",
			    oid_to_hex(&l->key_oid), t->ref);

461 462 463 464
		continue;

handle_non_note:
		/*
465 466 467 468 469 470 471
		 * Determine full path for this non-note entry. The
		 * filename is already found in entry.path, but the
		 * directory part of the path must be deduced from the
		 * subtree containing this entry based on our
		 * knowledge that the overall notes tree follows a
		 * strict byte-based progressive fanout structure
		 * (i.e. using 2/38, 2/2/36, etc. fanouts).
472 473
		 */
		{
474
			struct strbuf non_note_path = STRBUF_INIT;
475
			const char *q = oid_to_hex(&subtree->key_oid);
476
			size_t i;
477
			for (i = 0; i < prefix_len; i++) {
478 479 480
				strbuf_addch(&non_note_path, *q++);
				strbuf_addch(&non_note_path, *q++);
				strbuf_addch(&non_note_path, '/');
481
			}
482 483
			strbuf_addstr(&non_note_path, entry.path);
			add_non_note(t, strbuf_detach(&non_note_path, NULL),
484
				     entry.mode, entry.oid.hash);
485
		}
486 487 488 489
	}
	free(buf);
}

490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529
/*
 * Determine optimal on-disk fanout for this part of the notes tree
 *
 * Given a (sub)tree and the level in the internal tree structure, determine
 * whether or not the given existing fanout should be expanded for this
 * (sub)tree.
 *
 * Values of the 'fanout' variable:
 * - 0: No fanout (all notes are stored directly in the root notes tree)
 * - 1: 2/38 fanout
 * - 2: 2/2/36 fanout
 * - 3: 2/2/2/34 fanout
 * etc.
 */
static unsigned char determine_fanout(struct int_node *tree, unsigned char n,
		unsigned char fanout)
{
	/*
	 * The following is a simple heuristic that works well in practice:
	 * For each even-numbered 16-tree level (remember that each on-disk
	 * fanout level corresponds to _two_ 16-tree levels), peek at all 16
	 * entries at that tree level. If all of them are either int_nodes or
	 * subtree entries, then there are likely plenty of notes below this
	 * level, so we return an incremented fanout.
	 */
	unsigned int i;
	if ((n % 2) || (n > 2 * fanout))
		return fanout;
	for (i = 0; i < 16; i++) {
		switch (GET_PTR_TYPE(tree->a[i])) {
		case PTR_TYPE_SUBTREE:
		case PTR_TYPE_INTERNAL:
			continue;
		default:
			return fanout;
		}
	}
	return fanout + 1;
}

530
/* hex SHA1 + 19 * '/' + NUL */
531
#define FANOUT_PATH_MAX GIT_SHA1_HEXSZ + FANOUT_PATH_SEPARATORS + 1
532

533 534 535 536 537
static void construct_path_with_fanout(const unsigned char *sha1,
		unsigned char fanout, char *path)
{
	unsigned int i = 0, j = 0;
	const char *hex_sha1 = sha1_to_hex(sha1);
538
	assert(fanout < GIT_SHA1_RAWSZ);
539 540 541 542 543 544
	while (fanout) {
		path[i++] = hex_sha1[j++];
		path[i++] = hex_sha1[j++];
		path[i++] = '/';
		fanout--;
	}
545
	xsnprintf(path + i, FANOUT_PATH_MAX - i, "%s", hex_sha1 + j);
546 547
}

548 549 550
static int for_each_note_helper(struct notes_tree *t, struct int_node *tree,
		unsigned char n, unsigned char fanout, int flags,
		each_note_fn fn, void *cb_data)
551 552 553 554 555
{
	unsigned int i;
	void *p;
	int ret = 0;
	struct leaf_node *l;
556
	static char path[FANOUT_PATH_MAX];
557 558 559 560 561 562 563 564

	fanout = determine_fanout(tree, n, fanout);
	for (i = 0; i < 16; i++) {
redo:
		p = tree->a[i];
		switch (GET_PTR_TYPE(p)) {
		case PTR_TYPE_INTERNAL:
			/* recurse into int_node */
565
			ret = for_each_note_helper(t, CLR_PTR_TYPE(p), n + 1,
566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587
				fanout, flags, fn, cb_data);
			break;
		case PTR_TYPE_SUBTREE:
			l = (struct leaf_node *) CLR_PTR_TYPE(p);
			/*
			 * Subtree entries in the note tree represent parts of
			 * the note tree that have not yet been explored. There
			 * is a direct relationship between subtree entries at
			 * level 'n' in the tree, and the 'fanout' variable:
			 * Subtree entries at level 'n <= 2 * fanout' should be
			 * preserved, since they correspond exactly to a fanout
			 * directory in the on-disk structure. However, subtree
			 * entries at level 'n > 2 * fanout' should NOT be
			 * preserved, but rather consolidated into the above
			 * notes tree level. We achieve this by unconditionally
			 * unpacking subtree entries that exist below the
			 * threshold level at 'n = 2 * fanout'.
			 */
			if (n <= 2 * fanout &&
			    flags & FOR_EACH_NOTE_YIELD_SUBTREES) {
				/* invoke callback with subtree */
				unsigned int path_len =
588
					l->key_oid.hash[KEY_INDEX] * 2 + fanout;
589
				assert(path_len < FANOUT_PATH_MAX - 1);
590 591
				construct_path_with_fanout(l->key_oid.hash,
							   fanout,
592 593 594 595 596
							   path);
				/* Create trailing slash, if needed */
				if (path[path_len - 1] != '/')
					path[path_len++] = '/';
				path[path_len] = '\0';
597
				ret = fn(&l->key_oid, &l->val_oid,
598
					 path,
599 600 601 602 603 604
					 cb_data);
			}
			if (n > fanout * 2 ||
			    !(flags & FOR_EACH_NOTE_DONT_UNPACK_SUBTREES)) {
				/* unpack subtree and resume traversal */
				tree->a[i] = NULL;
605
				load_subtree(t, l, tree, n);
606 607 608 609 610 611
				free(l);
				goto redo;
			}
			break;
		case PTR_TYPE_NOTE:
			l = (struct leaf_node *) CLR_PTR_TYPE(p);
612 613
			construct_path_with_fanout(l->key_oid.hash, fanout,
						   path);
614
			ret = fn(&l->key_oid, &l->val_oid, path,
615
				 cb_data);
616 617 618 619 620 621 622 623
			break;
		}
		if (ret)
			return ret;
	}
	return 0;
}

624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641
struct tree_write_stack {
	struct tree_write_stack *next;
	struct strbuf buf;
	char path[2]; /* path to subtree in next, if any */
};

static inline int matches_tree_write_stack(struct tree_write_stack *tws,
		const char *full_path)
{
	return  full_path[0] == tws->path[0] &&
		full_path[1] == tws->path[1] &&
		full_path[2] == '/';
}

static void write_tree_entry(struct strbuf *buf, unsigned int mode,
		const char *path, unsigned int path_len, const
		unsigned char *sha1)
{
642
	strbuf_addf(buf, "%o %.*s%c", mode, path_len, path, '\0');
643
	strbuf_add(buf, sha1, GIT_SHA1_RAWSZ);
644 645 646 647 648 649 650 651 652 653 654
}

static void tree_write_stack_init_subtree(struct tree_write_stack *tws,
		const char *path)
{
	struct tree_write_stack *n;
	assert(!tws->next);
	assert(tws->path[0] == '\0' && tws->path[1] == '\0');
	n = (struct tree_write_stack *)
		xmalloc(sizeof(struct tree_write_stack));
	n->next = NULL;
655
	strbuf_init(&n->buf, 256 * (32 + GIT_SHA1_HEXSZ)); /* assume 256 entries per tree */
656 657 658 659 660 661 662 663 664 665
	n->path[0] = n->path[1] = '\0';
	tws->next = n;
	tws->path[0] = path[0];
	tws->path[1] = path[1];
}

static int tree_write_stack_finish_subtree(struct tree_write_stack *tws)
{
	int ret;
	struct tree_write_stack *n = tws->next;
666
	struct object_id s;
667 668 669 670
	if (n) {
		ret = tree_write_stack_finish_subtree(n);
		if (ret)
			return ret;
671
		ret = write_object_file(n->buf.buf, n->buf.len, tree_type, &s);
672 673 674 675 676
		if (ret)
			return ret;
		strbuf_release(&n->buf);
		free(n);
		tws->next = NULL;
677
		write_tree_entry(&tws->buf, 040000, tws->path, 2, s.hash);
678 679 680 681 682 683 684
		tws->path[0] = tws->path[1] = '\0';
	}
	return 0;
}

static int write_each_note_helper(struct tree_write_stack *tws,
		const char *path, unsigned int mode,
685
		const struct object_id *oid)
686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714
{
	size_t path_len = strlen(path);
	unsigned int n = 0;
	int ret;

	/* Determine common part of tree write stack */
	while (tws && 3 * n < path_len &&
	       matches_tree_write_stack(tws, path + 3 * n)) {
		n++;
		tws = tws->next;
	}

	/* tws point to last matching tree_write_stack entry */
	ret = tree_write_stack_finish_subtree(tws);
	if (ret)
		return ret;

	/* Start subtrees needed to satisfy path */
	while (3 * n + 2 < path_len && path[3 * n + 2] == '/') {
		tree_write_stack_init_subtree(tws, path + 3 * n);
		n++;
		tws = tws->next;
	}

	/* There should be no more directory components in the given path */
	assert(memchr(path + 3 * n, '/', path_len - (3 * n)) == NULL);

	/* Finally add given entry to the current tree object */
	write_tree_entry(&tws->buf, mode, path + 3 * n, path_len - (3 * n),
715
			 oid->hash);
716 717 718 719 720 721

	return 0;
}

struct write_each_note_data {
	struct tree_write_stack *root;
722
	struct non_note *next_non_note;
723 724
};

725 726 727 728
static int write_each_non_note_until(const char *note_path,
		struct write_each_note_data *d)
{
	struct non_note *n = d->next_non_note;
729
	int cmp = 0, ret;
730 731 732 733 734
	while (n && (!note_path || (cmp = strcmp(n->path, note_path)) <= 0)) {
		if (note_path && cmp == 0)
			; /* do nothing, prefer note to non-note */
		else {
			ret = write_each_note_helper(d->root, n->path, n->mode,
735
						     &n->oid);
736 737 738 739 740 741 742 743 744
			if (ret)
				return ret;
		}
		n = n->next;
	}
	d->next_non_note = n;
	return 0;
}

745 746
static int write_each_note(const struct object_id *object_oid,
		const struct object_id *note_oid, char *note_path,
747 748 749 750 751 752 753 754 755 756 757 758 759
		void *cb_data)
{
	struct write_each_note_data *d =
		(struct write_each_note_data *) cb_data;
	size_t note_path_len = strlen(note_path);
	unsigned int mode = 0100644;

	if (note_path[note_path_len - 1] == '/') {
		/* subtree entry */
		note_path_len--;
		note_path[note_path_len] = '\0';
		mode = 040000;
	}
760
	assert(note_path_len <= GIT_SHA1_HEXSZ + FANOUT_PATH_SEPARATORS);
761

762 763
	/* Weave non-note entries into note entries */
	return  write_each_non_note_until(note_path, d) ||
764
		write_each_note_helper(d->root, note_path, mode, note_oid);
765 766
}

767 768 769 770 771
struct note_delete_list {
	struct note_delete_list *next;
	const unsigned char *sha1;
};

772 773
static int prune_notes_helper(const struct object_id *object_oid,
		const struct object_id *note_oid, char *note_path,
774 775 776 777 778
		void *cb_data)
{
	struct note_delete_list **l = (struct note_delete_list **) cb_data;
	struct note_delete_list *n;

779
	if (has_object_file(object_oid))
780 781 782 783 784
		return 0; /* nothing to do for this note */

	/* failed to find object => prune this note */
	n = (struct note_delete_list *) xmalloc(sizeof(*n));
	n->next = *l;
785
	n->sha1 = object_oid->hash;
786 787 788 789
	*l = n;
	return 0;
}

790 791
int combine_notes_concatenate(struct object_id *cur_oid,
			      const struct object_id *new_oid)
792 793 794 795 796 797 798
{
	char *cur_msg = NULL, *new_msg = NULL, *buf;
	unsigned long cur_len, new_len, buf_len;
	enum object_type cur_type, new_type;
	int ret;

	/* read in both note blob objects */
799
	if (!is_null_oid(new_oid))
800
		new_msg = read_object_file(new_oid, &new_type, &new_len);
801 802 803 804
	if (!new_msg || !new_len || new_type != OBJ_BLOB) {
		free(new_msg);
		return 0;
	}
805
	if (!is_null_oid(cur_oid))
806
		cur_msg = read_object_file(cur_oid, &cur_type, &cur_len);
807 808 809
	if (!cur_msg || !cur_len || cur_type != OBJ_BLOB) {
		free(cur_msg);
		free(new_msg);
810
		oidcpy(cur_oid, new_oid);
811 812 813
		return 0;
	}

814
	/* we will separate the notes by two newlines anyway */
815 816 817 818
	if (cur_msg[cur_len - 1] == '\n')
		cur_len--;

	/* concatenate cur_msg and new_msg into buf */
819
	buf_len = cur_len + 2 + new_len;
820 821 822
	buf = (char *) xmalloc(buf_len);
	memcpy(buf, cur_msg, cur_len);
	buf[cur_len] = '\n';
823 824
	buf[cur_len + 1] = '\n';
	memcpy(buf + cur_len + 2, new_msg, new_len);
825 826 827 828
	free(cur_msg);
	free(new_msg);

	/* create a new blob object from buf */
829
	ret = write_object_file(buf, buf_len, blob_type, cur_oid);
830 831 832 833
	free(buf);
	return ret;
}

834 835
int combine_notes_overwrite(struct object_id *cur_oid,
			    const struct object_id *new_oid)
836
{
837
	oidcpy(cur_oid, new_oid);
838 839 840
	return 0;
}

841 842
int combine_notes_ignore(struct object_id *cur_oid,
			 const struct object_id *new_oid)
843 844 845 846
{
	return 0;
}

847 848 849 850 851
/*
 * Add the lines from the named object to list, with trailing
 * newlines removed.
 */
static int string_list_add_note_lines(struct string_list *list,
852
				      const struct object_id *oid)
853 854 855 856 857
{
	char *data;
	unsigned long len;
	enum object_type t;

858
	if (is_null_oid(oid))
859 860 861
		return 0;

	/* read_sha1_file NUL-terminates */
862
	data = read_object_file(oid, &t, &len);
863 864 865 866 867
	if (t != OBJ_BLOB || !data || !len) {
		free(data);
		return t != OBJ_BLOB || !data;
	}

868 869 870 871 872 873 874 875
	/*
	 * If the last line of the file is EOL-terminated, this will
	 * add an empty string to the list.  But it will be removed
	 * later, along with any empty strings that came from empty
	 * lines within the file.
	 */
	string_list_split(list, data, '\n', -1);
	free(data);
876 877 878 879 880 881 882 883 884 885 886 887
	return 0;
}

static int string_list_join_lines_helper(struct string_list_item *item,
					 void *cb_data)
{
	struct strbuf *buf = cb_data;
	strbuf_addstr(buf, item->string);
	strbuf_addch(buf, '\n');
	return 0;
}

888 889
int combine_notes_cat_sort_uniq(struct object_id *cur_oid,
				const struct object_id *new_oid)
890
{
891
	struct string_list sort_uniq_list = STRING_LIST_INIT_DUP;
892 893 894 895
	struct strbuf buf = STRBUF_INIT;
	int ret = 1;

	/* read both note blob objects into unique_lines */
896
	if (string_list_add_note_lines(&sort_uniq_list, cur_oid))
897
		goto out;
898
	if (string_list_add_note_lines(&sort_uniq_list, new_oid))
899
		goto out;
900
	string_list_remove_empty_items(&sort_uniq_list, 0);
901
	string_list_sort(&sort_uniq_list);
902
	string_list_remove_duplicates(&sort_uniq_list, 0);
903 904 905 906 907 908

	/* create a new blob object from sort_uniq_list */
	if (for_each_string_list(&sort_uniq_list,
				 string_list_join_lines_helper, &buf))
		goto out;

909
	ret = write_object_file(buf.buf, buf.len, blob_type, cur_oid);
910 911 912 913 914 915 916

out:
	strbuf_release(&buf);
	string_list_clear(&sort_uniq_list, 0);
	return ret;
}

917
static int string_list_add_one_ref(const char *refname, const struct object_id *oid,
918 919 920
				   int flag, void *cb)
{
	struct string_list *refs = cb;
921 922
	if (!unsorted_string_list_has_string(refs, refname))
		string_list_append(refs, refname);
923 924 925
	return 0;
}

926 927 928
/*
 * The list argument must have strdup_strings set on it.
 */
929 930
void string_list_add_refs_by_glob(struct string_list *list, const char *glob)
{
931
	assert(list->strdup_strings);
932
	if (has_glob_specials(glob)) {
933
		for_each_glob_ref(string_list_add_one_ref, glob, list);
934
	} else {
935 936
		struct object_id oid;
		if (get_oid(glob, &oid))
937 938
			warning("notes ref %s is invalid", glob);
		if (!unsorted_string_list_has_string(list, glob))
939
			string_list_append(list, glob);
940 941 942 943 944 945
	}
}

void string_list_add_refs_from_colon_sep(struct string_list *list,
					 const char *globs)
{
946 947
	struct string_list split = STRING_LIST_INIT_NODUP;
	char *globs_copy = xstrdup(globs);
948 949
	int i;

950 951
	string_list_split_in_place(&split, globs_copy, ':', -1);
	string_list_remove_empty_items(&split, 0);
952

953 954
	for (i = 0; i < split.nr; i++)
		string_list_add_refs_by_glob(list, split.items[i].string);
955

956 957
	string_list_clear(&split, 0);
	free(globs_copy);
958 959 960 961 962 963 964 965 966 967 968 969 970 971 972
}

static int notes_display_config(const char *k, const char *v, void *cb)
{
	int *load_refs = cb;

	if (*load_refs && !strcmp(k, "notes.displayref")) {
		if (!v)
			config_error_nonbool(k);
		string_list_add_refs_by_glob(&display_notes_refs, v);
	}

	return 0;
}

973
const char *default_notes_ref(void)
974 975 976 977 978 979 980 981 982 983 984
{
	const char *notes_ref = NULL;
	if (!notes_ref)
		notes_ref = getenv(GIT_NOTES_REF_ENVIRONMENT);
	if (!notes_ref)
		notes_ref = notes_ref_name; /* value of core.notesRef config */
	if (!notes_ref)
		notes_ref = GIT_NOTES_DEFAULT_REF;
	return notes_ref;
}

985 986
void init_notes(struct notes_tree *t, const char *notes_ref,
		combine_notes_fn combine_notes, int flags)
987
{
988
	struct object_id oid, object_oid;
989 990
	unsigned mode;
	struct leaf_node root_tree;
991

992 993 994
	if (!t)
		t = &default_notes_tree;
	assert(!t->initialized);
995 996

	if (!notes_ref)
997
		notes_ref = default_notes_ref();
998

999 1000 1001
	if (!combine_notes)
		combine_notes = combine_notes_concatenate;

1002
	t->root = (struct int_node *) xcalloc(1, sizeof(struct int_node));
1003 1004
	t->first_non_note = NULL;
	t->prev_non_note = NULL;
1005
	t->ref = xstrdup_or_null(notes_ref);
1006
	t->update_ref = (flags & NOTES_INIT_WRITABLE) ? t->ref : NULL;
1007
	t->combine_notes = combine_notes;
1008
	t->initialized = 1;
1009
	t->dirty = 0;
1010

1011
	if (flags & NOTES_INIT_EMPTY || !notes_ref ||
1012
	    get_oid_treeish(notes_ref, &object_oid))
1013
		return;
1014
	if (flags & NOTES_INIT_WRITABLE && read_ref(notes_ref, &object_oid))
1015
		die("Cannot use notes ref %s", notes_ref);
1016
	if (get_tree_entry(&object_oid, "", &oid, &mode))
1017
		die("Failed to read notes tree referenced by %s (%s)",
1018
		    notes_ref, oid_to_hex(&object_oid));
1019

1020 1021
	oidclr(&root_tree.key_oid);
	oidcpy(&root_tree.val_oid, &oid);
1022
	load_subtree(t, &root_tree, t->root, 0);
1023 1024
}

1025
struct notes_tree **load_notes_trees(struct string_list *refs, int flags)
1026
{
1027 1028
	struct string_list_item *item;
	int counter = 0;
1029
	struct notes_tree **trees;
1030
	ALLOC_ARRAY(trees, refs->nr + 1);
1031 1032
	for_each_string_list_item(item, refs) {
		struct notes_tree *t = xcalloc(1, sizeof(struct notes_tree));
1033
		init_notes(t, item->string, combine_notes_ignore, flags);
1034 1035 1036
		trees[counter++] = t;
	}
	trees[counter] = NULL;
1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047
	return trees;
}

void init_display_notes(struct display_notes_opt *opt)
{
	char *display_ref_env;
	int load_config_refs = 0;
	display_notes_refs.strdup_strings = 1;

	assert(!display_notes_trees);

1048 1049
	if (!opt || opt->use_default_notes > 0 ||
	    (opt->use_default_notes == -1 && !opt->extra_notes_refs.nr)) {
1050
		string_list_append(&display_notes_refs, default_notes_ref());
1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061
		display_ref_env = getenv(GIT_NOTES_DISPLAY_REF_ENVIRONMENT);
		if (display_ref_env) {
			string_list_add_refs_from_colon_sep(&display_notes_refs,
							    display_ref_env);
			load_config_refs = 0;
		} else
			load_config_refs = 1;
	}

	git_config(notes_display_config, &load_config_refs);

1062
	if (opt) {
1063
		struct string_list_item *item;
1064
		for_each_string_list_item(item, &opt->extra_notes_refs)
1065 1066 1067
			string_list_add_refs_by_glob(&display_notes_refs,
						     item->string);
	}
1068

1069
	display_notes_trees = load_notes_trees(&display_notes_refs, 0);
1070 1071 1072
	string_list_clear(&display_notes_refs, 0);
}

1073 1074
int add_note(struct notes_tree *t, const struct object_id *object_oid,
		const struct object_id *note_oid, combine_notes_fn combine_notes)
1075 1076 1077
{
	struct leaf_node *l;

1078 1079 1080
	if (!t)
		t = &default_notes_tree;
	assert(t->initialized);
1081
	t->dirty = 1;
1082 1083
	if (!combine_notes)
		combine_notes = t->combine_notes;
1084
	l = (struct leaf_node *) xmalloc(sizeof(struct leaf_node));
1085 1086
	oidcpy(&l->key_oid, object_oid);
	oidcpy(&l->val_oid, note_oid);
1087
	return note_tree_insert(t, t->root, 0, l, PTR_TYPE_NOTE, combine_notes);
1088 1089
}

1090
int remove_note(struct notes_tree *t, const unsigned char *object_sha1)
1091 1092 1093
{
	struct leaf_node l;

1094 1095 1096
	if (!t)
		t = &default_notes_tree;
	assert(t->initialized);
1097 1098
	hashcpy(l.key_oid.hash, object_sha1);
	oidclr(&l.val_oid);
1099
	note_tree_remove(t, t->root, 0, &l);
1100
	if (is_null_oid(&l.val_oid)) /* no note was removed */
1101 1102 1103
		return 1;
	t->dirty = 1;
	return 0;
1104 1105
}

1106
const struct object_id *get_note(struct notes_tree *t,
1107
		const struct object_id *oid)
1108
{
1109 1110
	struct leaf_node *found;

1111 1112 1113
	if (!t)
		t = &default_notes_tree;
	assert(t->initialized);
1114
	found = note_tree_find(t, t->root, 0, oid->hash);
1115
	return found ? &found->val_oid : NULL;
1116
}
1117

1118 1119
int for_each_note(struct notes_tree *t, int flags, each_note_fn fn,
		void *cb_data)
1120
{
1121 1122 1123
	if (!t)
		t = &default_notes_tree;
	assert(t->initialized);
1124
	return for_each_note_helper(t, t->root, 0, 0, flags, fn, cb_data);
1125 1126
}

1127
int write_notes_tree(struct notes_tree *t, struct object_id *result)
1128 1129 1130 1131
{
	struct tree_write_stack root;
	struct write_each_note_data cb_data;
	int ret;
1132
	int flags;
1133

1134 1135 1136
	if (!t)
		t = &default_notes_tree;
	assert(t->initialized);
1137 1138 1139

	/* Prepare for traversal of current notes tree */
	root.next = NULL; /* last forward entry in list is grounded */
1140
	strbuf_init(&root.buf, 256 * (32 + GIT_SHA1_HEXSZ)); /* assume 256 entries */
1141 1142
	root.path[0] = root.path[1] = '\0';
	cb_data.root = &root;
1143
	cb_data.next_non_note = t->first_non_note;
1144 1145

	/* Write tree objects representing current notes tree */
1146 1147 1148 1149 1150
	flags = FOR_EACH_NOTE_DONT_UNPACK_SUBTREES |
		FOR_EACH_NOTE_YIELD_SUBTREES;
	ret = for_each_note(t, flags, write_each_note, &cb_data) ||
	      write_each_non_note_until(NULL, &cb_data) ||
	      tree_write_stack_finish_subtree(&root) ||
1151
	      write_object_file(root.buf.buf, root.buf.len, tree_type, result);
1152 1153 1154 1155
	strbuf_release(&root.buf);
	return ret;
}

1156
void prune_notes(struct notes_tree *t, int flags)
1157 1158 1159 1160 1161 1162 1163 1164 1165 1166
{
	struct note_delete_list *l = NULL;

	if (!t)
		t = &default_notes_tree;
	assert(t->initialized);

	for_each_note(t, 0, prune_notes_helper, &l);

	while (l) {
1167 1168 1169 1170
		if (flags & NOTES_PRUNE_VERBOSE)
			printf("%s\n", sha1_to_hex(l->sha1));
		if (!(flags & NOTES_PRUNE_DRYRUN))
			remove_note(t, l->sha1);
1171 1172 1173 1174
		l = l->next;
	}
}

1175
void free_notes(struct notes_tree *t)
1176
{
1177 1178 1179 1180 1181
	if (!t)
		t = &default_notes_tree;
	if (t->root)
		note_tree_free(t->root);
	free(t->root);
1182 1183 1184 1185 1186 1187
	while (t->first_non_note) {
		t->prev_non_note = t->first_non_note->next;
		free(t->first_non_note->path);
		free(t->first_non_note);
		t->first_non_note = t->prev_non_note;
	}
1188 1189
	free(t->ref);
	memset(t, 0, sizeof(struct notes_tree));
1190 1191
}

1192 1193 1194 1195 1196 1197 1198 1199
/*
 * Fill the given strbuf with the notes associated with the given object.
 *
 * If the given notes_tree structure is not initialized, it will be auto-
 * initialized to the default value (see documentation for init_notes() above).
 * If the given notes_tree is NULL, the internal/default notes_tree will be
 * used instead.
 *
1200 1201
 * (raw != 0) gives the %N userformat; otherwise, the note message is given
 * for human consumption.
1202
 */
1203
static void format_note(struct notes_tree *t, const struct object_id *object_oid,
1204
			struct strbuf *sb, const char *output_encoding, int raw)
1205 1206
{
	static const char utf8[] = "utf-8";
1207
	const struct object_id *oid;
1208 1209 1210 1211
	char *msg, *msg_p;
	unsigned long linelen, msglen;
	enum object_type type;

1212 1213 1214
	if (!t)
		t = &default_notes_tree;
	if (!t->initialized)
1215
		init_notes(t, NULL, NULL, 0);
1216

1217
	oid = get_note(t, object_oid);
1218
	if (!oid)
1219 1220
		return;

1221
	if (!(msg = read_object_file(oid, &type, &msglen)) || type != OBJ_BLOB) {
1222 1223 1224 1225 1226
		free(msg);
		return;
	}

	if (output_encoding && *output_encoding &&
1227
	    !is_encoding_utf8(output_encoding)) {
1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239
		char *reencoded = reencode_string(msg, output_encoding, utf8);
		if (reencoded) {
			free(msg);
			msg = reencoded;
			msglen = strlen(msg);
		}
	}

	/* we will end the annotation by a newline anyway */
	if (msglen && msg[msglen - 1] == '\n')
		msglen--;

1240
	if (!raw) {
1241 1242 1243 1244
		const char *ref = t->ref;
		if (!ref || !strcmp(ref, GIT_NOTES_DEFAULT_REF)) {
			strbuf_addstr(sb, "\nNotes:\n");
		} else {
1245
			if (starts_with(ref, "refs/"))
1246
				ref += 5;
1247
			if (starts_with(ref, "notes/"))
1248 1249 1250 1251
				ref += 6;
			strbuf_addf(sb, "\nNotes (%s):\n", ref);
		}
	}
1252 1253 1254 1255

	for (msg_p = msg; msg_p < msg + msglen; msg_p += linelen + 1) {
		linelen = strchrnul(msg_p, '\n') - msg_p;

1256
		if (!raw)
1257
			strbuf_addstr(sb, "    ");
1258 1259 1260 1261 1262 1263
		strbuf_add(sb, msg_p, linelen);
		strbuf_addch(sb, '\n');
	}

	free(msg);
}
1264

1265
void format_display_notes(const struct object_id *object_oid,
1266
			  struct strbuf *sb, const char *output_encoding, int raw)
1267 1268 1269 1270
{
	int i;
	assert(display_notes_trees);
	for (i = 0; display_notes_trees[i]; i++)
1271
		format_note(display_notes_trees[i], object_oid, sb,
1272