git

1
#define USE_THE_REPOSITORY_VARIABLE
2

3
#include "git-compat-util.h"
4
#include "config.h"
5
#include "environment.h"
6
#include "hex.h"
7
#include "notes.h"
8
#include "object-name.h"
9
#include "object-store-ll.h"
10
#include "utf8.h"
11
#include "strbuf.h"
12
#include "tree-walk.h"
13
#include "string-list.h"
14
#include "refs.h"
15

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

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

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

62
#define PTR_TYPE_NULL     0
63
#define PTR_TYPE_INTERNAL 1
64
#define PTR_TYPE_NOTE     2
65
#define PTR_TYPE_SUBTREE  3
66

67
#define GET_PTR_TYPE(ptr)       ((uintptr_t) (ptr) & 3)
68
#define CLR_PTR_TYPE(ptr)       ((void *) ((uintptr_t) (ptr) & ~3))
69
#define SET_PTR_TYPE(ptr, type) ((void *) ((uintptr_t) (ptr) | (type)))
70

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

73
#define KEY_INDEX (the_hash_algo->rawsz - 1)
74
#define FANOUT_PATH_SEPARATORS (the_hash_algo->rawsz - 1)
75
#define FANOUT_PATH_SEPARATORS_MAX ((GIT_MAX_HEXSZ / 2) - 1)
76
#define SUBTREE_SHA1_PREFIXCMP(key_sha1, subtree_sha1) \
77
	(memcmp(key_sha1, subtree_sha1, subtree_sha1[KEY_INDEX]))
78

79
struct notes_tree default_notes_tree;
80

81
static struct string_list display_notes_refs = STRING_LIST_INIT_NODUP;
82
static struct notes_tree **display_notes_trees;
83

84
static void load_subtree(struct notes_tree *t, struct leaf_node *subtree,
85
		struct int_node *node, unsigned int n);
86

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

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

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

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

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

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

176
	for (i = 0; i < 16; i++) {
177
		if (GET_PTR_TYPE(tree->a[i]) != PTR_TYPE_NULL) {
178
			if (p) /* more than one entry */
179
				return -2;
180
			p = tree->a[i];
181
		}
182
	}
183

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

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

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

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

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

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

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

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

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

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

344
static int non_note_cmp(const struct non_note *a, const struct non_note *b)
345
{
346
	return strcmp(a->path, b->path);
347
}
348

349
/* note: takes ownership of path string */
350
static void add_non_note(struct notes_tree *t, 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 = path;
357
	n->mode = mode;
358
	oidread(&n->oid, sha1, the_repository->hash_algo);
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
		oidcpy(&p->oid, &n->oid);
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

395
static void load_subtree(struct notes_tree *t, struct leaf_node *subtree,
396
		struct int_node *node, unsigned int n)
397
{
398
	struct object_id object_oid;
399
	size_t prefix_len;
400
	void *buf;
401
	struct tree_desc desc;
402
	struct name_entry entry;
403
	const unsigned hashsz = the_hash_algo->rawsz;
404

405
	buf = fill_tree_descriptor(the_repository, &desc, &subtree->val_oid);
406
	if (!buf)
407
		die("Could not read %s for notes-index",
408
		     oid_to_hex(&subtree->val_oid));
409

410
	prefix_len = subtree->key_oid.hash[KEY_INDEX];
411
	if (prefix_len >= hashsz)
412
		BUG("prefix_len (%"PRIuMAX") is out of range", (uintmax_t)prefix_len);
413
	if (prefix_len * 2 < n)
414
		BUG("prefix_len (%"PRIuMAX") is too small", (uintmax_t)prefix_len);
415
	memcpy(object_oid.hash, subtree->key_oid.hash, prefix_len);
416
	while (tree_entry(&desc, &entry)) {
417
		unsigned char type;
418
		struct leaf_node *l;
419
		size_t path_len = strlen(entry.path);
420

421
		if (path_len == 2 * (hashsz - prefix_len)) {
422
			/* This is potentially the remainder of the SHA-1 */
423

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

428
			if (hex_to_bytes(object_oid.hash + prefix_len, entry.path,
429
					 hashsz - prefix_len))
430
				goto handle_non_note; /* entry.path is not a SHA1 */
431

432
			memset(object_oid.hash + hashsz, 0, GIT_MAX_RAWSZ - hashsz);
433

434
			type = PTR_TYPE_NOTE;
435
		} else if (path_len == 2) {
436
			/* This is potentially an internal node */
437
			size_t len = prefix_len;
438

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

443
			if (hex_to_bytes(object_oid.hash + len++, entry.path, 1))
444
				goto handle_non_note; /* entry.path is not a SHA1 */
445

446
			/*
447
			 * Pad the rest of the SHA-1 with zeros,
448
			 * except for the last byte, where we write
449
			 * the length:
450
			 */
451
			memset(object_oid.hash + len, 0, hashsz - len - 1);
452
			object_oid.hash[KEY_INDEX] = (unsigned char)len;
453

454
			type = PTR_TYPE_SUBTREE;
455
		} else {
456
			/* This can't be part of a note */
457
			goto handle_non_note;
458
		}
459

460
		CALLOC_ARRAY(l, 1);
461
		oidcpy(&l->key_oid, &object_oid);
462
		oidcpy(&l->val_oid, &entry.oid);
463
		oid_set_algo(&l->key_oid, the_hash_algo);
464
		oid_set_algo(&l->val_oid, the_hash_algo);
465
		if (note_tree_insert(t, node, n, l, type,
466
				     combine_notes_concatenate))
467
			die("Failed to load %s %s into notes tree "
468
			    "from %s",
469
			    type == PTR_TYPE_NOTE ? "note" : "subtree",
470
			    oid_to_hex(&object_oid), t->ref);
471

472
		continue;
473

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

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

542
/* hex oid + '/' between each pair of hex digits + NUL */
543
#define FANOUT_PATH_MAX GIT_MAX_HEXSZ + FANOUT_PATH_SEPARATORS_MAX + 1
544

545
static void construct_path_with_fanout(const unsigned char *hash,
546
		unsigned char fanout, char *path)
547
{
548
	unsigned int i = 0, j = 0;
549
	const char *hex_hash = hash_to_hex(hash);
550
	assert(fanout < the_hash_algo->rawsz);
551
	while (fanout) {
552
		path[i++] = hex_hash[j++];
553
		path[i++] = hex_hash[j++];
554
		path[i++] = '/';
555
		fanout--;
556
	}
557
	xsnprintf(path + i, FANOUT_PATH_MAX - i, "%s", hex_hash + j);
558
}
559

560
static int for_each_note_helper(struct notes_tree *t, struct int_node *tree,
561
		unsigned char n, unsigned char fanout, int flags,
562
		each_note_fn fn, void *cb_data)
563
{
564
	unsigned int i;
565
	void *p;
566
	int ret = 0;
567
	struct leaf_node *l;
568
	static char path[FANOUT_PATH_MAX];
569

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

636
struct tree_write_stack {
637
	struct tree_write_stack *next;
638
	struct strbuf buf;
639
	char path[2]; /* path to subtree in next, if any */
640
};
641

642
static inline int matches_tree_write_stack(struct tree_write_stack *tws,
643
		const char *full_path)
644
{
645
	return  full_path[0] == tws->path[0] &&
646
		full_path[1] == tws->path[1] &&
647
		full_path[2] == '/';
648
}
649

650
static void write_tree_entry(struct strbuf *buf, unsigned int mode,
651
		const char *path, unsigned int path_len, const
652
		unsigned char *hash)
653
{
654
	strbuf_addf(buf, "%o %.*s%c", mode, path_len, path, '\0');
655
	strbuf_add(buf, hash, the_hash_algo->rawsz);
656
}
657

658
static void tree_write_stack_init_subtree(struct tree_write_stack *tws,
659
		const char *path)
660
{
661
	struct tree_write_stack *n;
662
	assert(!tws->next);
663
	assert(tws->path[0] == '\0' && tws->path[1] == '\0');
664
	n = (struct tree_write_stack *)
665
		xmalloc(sizeof(struct tree_write_stack));
666
	n->next = NULL;
667
	strbuf_init(&n->buf, 256 * (32 + the_hash_algo->hexsz)); /* assume 256 entries per tree */
668
	n->path[0] = n->path[1] = '\0';
669
	tws->next = n;
670
	tws->path[0] = path[0];
671
	tws->path[1] = path[1];
672
}
673

674
static int tree_write_stack_finish_subtree(struct tree_write_stack *tws)
675
{
676
	int ret;
677
	struct tree_write_stack *n = tws->next;
678
	struct object_id s;
679
	if (n) {
680
		ret = tree_write_stack_finish_subtree(n);
681
		if (ret)
682
			return ret;
683
		ret = write_object_file(n->buf.buf, n->buf.len, OBJ_TREE, &s);
684
		if (ret)
685
			return ret;
686
		strbuf_release(&n->buf);
687
		free(n);
688
		tws->next = NULL;
689
		write_tree_entry(&tws->buf, 040000, tws->path, 2, s.hash);
690
		tws->path[0] = tws->path[1] = '\0';
691
	}
692
	return 0;
693
}
694

695
static int write_each_note_helper(struct tree_write_stack *tws,
696
		const char *path, unsigned int mode,
697
		const struct object_id *oid)
698
{
699
	size_t path_len = strlen(path);
700
	unsigned int n = 0;
701
	int ret;
702

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

710
	/* tws point to last matching tree_write_stack entry */
711
	ret = tree_write_stack_finish_subtree(tws);
712
	if (ret)
713
		return ret;
714

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

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

725
	/* Finally add given entry to the current tree object */
726
	write_tree_entry(&tws->buf, mode, path + 3 * n, path_len - (3 * n),
727
			 oid->hash);
728

729
	return 0;
730
}
731

732
struct write_each_note_data {
733
	struct tree_write_stack *root;
734
	struct non_note **nn_list;
735
	struct non_note *nn_prev;
736
};
737

738
static int write_each_non_note_until(const char *note_path,
739
		struct write_each_note_data *d)
740
{
741
	struct non_note *p = d->nn_prev;
742
	struct non_note *n = p ? p->next : *d->nn_list;
743
	int cmp = 0, ret;
744
	while (n && (!note_path || (cmp = strcmp(n->path, note_path)) <= 0)) {
745
		if (note_path && cmp == 0)
746
			; /* do nothing, prefer note to non-note */
747
		else {
748
			ret = write_each_note_helper(d->root, n->path, n->mode,
749
						     &n->oid);
750
			if (ret)
751
				return ret;
752
		}
753
		p = n;
754
		n = n->next;
755
	}
756
	d->nn_prev = p;
757
	return 0;
758
}
759

760
static int write_each_note(const struct object_id *object_oid UNUSED,
761
		const struct object_id *note_oid, char *note_path,
762
		void *cb_data)
763
{
764
	struct write_each_note_data *d =
765
		(struct write_each_note_data *) cb_data;
766
	size_t note_path_len = strlen(note_path);
767
	unsigned int mode = 0100644;
768

769
	if (note_path[note_path_len - 1] == '/') {
770
		/* subtree entry */
771
		note_path_len--;
772
		note_path[note_path_len] = '\0';
773
		mode = 040000;
774
	}
775
	assert(note_path_len <= GIT_MAX_HEXSZ + FANOUT_PATH_SEPARATORS);
776

777
	/* Weave non-note entries into note entries */
778
	return  write_each_non_note_until(note_path, d) ||
779
		write_each_note_helper(d->root, note_path, mode, note_oid);
780
}
781

782
struct note_delete_list {
783
	struct note_delete_list *next;
784
	const unsigned char *sha1;
785
};
786

787
static int prune_notes_helper(const struct object_id *object_oid,
788
			      const struct object_id *note_oid UNUSED,
789
			      char *note_path UNUSED,
790
			      void *cb_data)
791
{
792
	struct note_delete_list **l = (struct note_delete_list **) cb_data;
793
	struct note_delete_list *n;
794

795
	if (repo_has_object_file(the_repository, object_oid))
796
		return 0; /* nothing to do for this note */
797

798
	/* failed to find object => prune this note */
799
	n = (struct note_delete_list *) xmalloc(sizeof(*n));
800
	n->next = *l;
801
	n->sha1 = object_oid->hash;
802
	*l = n;
803
	return 0;
804
}
805

806
int combine_notes_concatenate(struct object_id *cur_oid,
807
			      const struct object_id *new_oid)
808
{
809
	char *cur_msg = NULL, *new_msg = NULL, *buf;
810
	unsigned long cur_len, new_len, buf_len;
811
	enum object_type cur_type, new_type;
812
	int ret;
813

814
	/* read in both note blob objects */
815
	if (!is_null_oid(new_oid))
816
		new_msg = repo_read_object_file(the_repository, new_oid,
817
						&new_type, &new_len);
818
	if (!new_msg || !new_len || new_type != OBJ_BLOB) {
819
		free(new_msg);
820
		return 0;
821
	}
822
	if (!is_null_oid(cur_oid))
823
		cur_msg = repo_read_object_file(the_repository, cur_oid,
824
						&cur_type, &cur_len);
825
	if (!cur_msg || !cur_len || cur_type != OBJ_BLOB) {
826
		free(cur_msg);
827
		free(new_msg);
828
		oidcpy(cur_oid, new_oid);
829
		return 0;
830
	}
831

832
	/* we will separate the notes by two newlines anyway */
833
	if (cur_msg[cur_len - 1] == '\n')
834
		cur_len--;
835

836
	/* concatenate cur_msg and new_msg into buf */
837
	buf_len = cur_len + 2 + new_len;
838
	buf = (char *) xmalloc(buf_len);
839
	memcpy(buf, cur_msg, cur_len);
840
	buf[cur_len] = '\n';
841
	buf[cur_len + 1] = '\n';
842
	memcpy(buf + cur_len + 2, new_msg, new_len);
843
	free(cur_msg);
844
	free(new_msg);
845

846
	/* create a new blob object from buf */
847
	ret = write_object_file(buf, buf_len, OBJ_BLOB, cur_oid);
848
	free(buf);
849
	return ret;
850
}
851

852
int combine_notes_overwrite(struct object_id *cur_oid,
853
			    const struct object_id *new_oid)
854
{
855
	oidcpy(cur_oid, new_oid);
856
	return 0;
857
}
858

859
int combine_notes_ignore(struct object_id *cur_oid UNUSED,
860
			 const struct object_id *new_oid UNUSED)
861
{
862
	return 0;
863
}
864

865
/*
866
 * Add the lines from the named object to list, with trailing
867
 * newlines removed.
868
 */
869
static int string_list_add_note_lines(struct string_list *list,
870
				      const struct object_id *oid)
871
{
872
	char *data;
873
	unsigned long len;
874
	enum object_type t;
875

876
	if (is_null_oid(oid))
877
		return 0;
878

879
	/* read_sha1_file NUL-terminates */
880
	data = repo_read_object_file(the_repository, oid, &t, &len);
881
	if (t != OBJ_BLOB || !data || !len) {
882
		free(data);
883
		return t != OBJ_BLOB || !data;
884
	}
885

886
	/*
887
	 * If the last line of the file is EOL-terminated, this will
888
	 * add an empty string to the list.  But it will be removed
889
	 * later, along with any empty strings that came from empty
890
	 * lines within the file.
891
	 */
892
	string_list_split(list, data, '\n', -1);
893
	free(data);
894
	return 0;
895
}
896

897
static int string_list_join_lines_helper(struct string_list_item *item,
898
					 void *cb_data)
899
{
900
	struct strbuf *buf = cb_data;
901
	strbuf_addstr(buf, item->string);
902
	strbuf_addch(buf, '\n');
903
	return 0;
904
}
905

906
int combine_notes_cat_sort_uniq(struct object_id *cur_oid,
907
				const struct object_id *new_oid)
908
{
909
	struct string_list sort_uniq_list = STRING_LIST_INIT_DUP;
910
	struct strbuf buf = STRBUF_INIT;
911
	int ret = 1;
912

913
	/* read both note blob objects into unique_lines */
914
	if (string_list_add_note_lines(&sort_uniq_list, cur_oid))
915
		goto out;
916
	if (string_list_add_note_lines(&sort_uniq_list, new_oid))
917
		goto out;
918
	string_list_remove_empty_items(&sort_uniq_list, 0);
919
	string_list_sort(&sort_uniq_list);
920
	string_list_remove_duplicates(&sort_uniq_list, 0);
921

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

927
	ret = write_object_file(buf.buf, buf.len, OBJ_BLOB, cur_oid);
928

929
out:
930
	strbuf_release(&buf);
931
	string_list_clear(&sort_uniq_list, 0);
932
	return ret;
933
}
934

935
static int string_list_add_one_ref(const char *refname, const char *referent UNUSED,
936
				   const struct object_id *oid UNUSED,
937
				   int flag UNUSED, void *cb)
938
{
939
	struct string_list *refs = cb;
940
	if (!unsorted_string_list_has_string(refs, refname))
941
		string_list_append(refs, refname);
942
	return 0;
943
}
944

945
/*
946
 * The list argument must have strdup_strings set on it.
947
 */
948
void string_list_add_refs_by_glob(struct string_list *list, const char *glob)
949
{
950
	assert(list->strdup_strings);
951
	if (has_glob_specials(glob)) {
952
		refs_for_each_glob_ref(get_main_ref_store(the_repository),
953
				       string_list_add_one_ref, glob, list);
954
	} else {
955
		struct object_id oid;
956
		if (repo_get_oid(the_repository, glob, &oid))
957
			warning("notes ref %s is invalid", glob);
958
		if (!unsorted_string_list_has_string(list, glob))
959
			string_list_append(list, glob);
960
	}
961
}
962

963
void string_list_add_refs_from_colon_sep(struct string_list *list,
964
					 const char *globs)
965
{
966
	struct string_list split = STRING_LIST_INIT_NODUP;
967
	char *globs_copy = xstrdup(globs);
968
	int i;
969

970
	string_list_split_in_place(&split, globs_copy, ":", -1);
971
	string_list_remove_empty_items(&split, 0);
972

973
	for (i = 0; i < split.nr; i++)
974
		string_list_add_refs_by_glob(list, split.items[i].string);
975

976
	string_list_clear(&split, 0);
977
	free(globs_copy);
978
}
979

980
static int notes_display_config(const char *k, const char *v,
981
				const struct config_context *ctx UNUSED,
982
				void *cb)
983
{
984
	int *load_refs = cb;
985

986
	if (*load_refs && !strcmp(k, "notes.displayref")) {
987
		if (!v)
988
			return config_error_nonbool(k);
989
		string_list_add_refs_by_glob(&display_notes_refs, v);
990
	}
991

992
	return 0;
993
}
994

995
const char *default_notes_ref(void)
996
{
997
	const char *notes_ref = NULL;
998
	if (!notes_ref)
999
		notes_ref = getenv(GIT_NOTES_REF_ENVIRONMENT);
1000
	if (!notes_ref)
1001
		notes_ref = notes_ref_name; /* value of core.notesRef config */
1002
	if (!notes_ref)
1003
		notes_ref = GIT_NOTES_DEFAULT_REF;
1004
	return notes_ref;
1005
}
1006

1007
void init_notes(struct notes_tree *t, const char *notes_ref,
1008
		combine_notes_fn combine_notes, int flags)
1009
{
1010
	struct object_id oid, object_oid;
1011
	unsigned short mode;
1012
	struct leaf_node root_tree;
1013

1014
	if (!t)
1015
		t = &default_notes_tree;
1016
	assert(!t->initialized);
1017

1018
	if (!notes_ref)
1019
		notes_ref = default_notes_ref();
1020
	update_ref_namespace(NAMESPACE_NOTES, xstrdup(notes_ref));
1021

1022
	if (!combine_notes)
1023
		combine_notes = combine_notes_concatenate;
1024

1025
	t->root = (struct int_node *) xcalloc(1, sizeof(struct int_node));
1026
	t->first_non_note = NULL;
1027
	t->prev_non_note = NULL;
1028
	t->ref = xstrdup(notes_ref);
1029
	t->update_ref = (flags & NOTES_INIT_WRITABLE) ? t->ref : NULL;
1030
	t->combine_notes = combine_notes;
1031
	t->initialized = 1;
1032
	t->dirty = 0;
1033

1034
	if (flags & NOTES_INIT_EMPTY ||
1035
	    repo_get_oid_treeish(the_repository, notes_ref, &object_oid))
1036
		return;
1037
	if (flags & NOTES_INIT_WRITABLE && refs_read_ref(get_main_ref_store(the_repository), notes_ref, &object_oid))
1038
		die("Cannot use notes ref %s", notes_ref);
1039
	if (get_tree_entry(the_repository, &object_oid, "", &oid, &mode))
1040
		die("Failed to read notes tree referenced by %s (%s)",
1041
		    notes_ref, oid_to_hex(&object_oid));
1042

1043
	oidclr(&root_tree.key_oid, the_repository->hash_algo);
1044
	oidcpy(&root_tree.val_oid, &oid);
1045
	load_subtree(t, &root_tree, t->root, 0);
1046
}
1047

1048
struct notes_tree **load_notes_trees(struct string_list *refs, int flags)
1049
{
1050
	struct string_list_item *item;
1051
	int counter = 0;
1052
	struct notes_tree **trees;
1053
	ALLOC_ARRAY(trees, refs->nr + 1);
1054
	for_each_string_list_item(item, refs) {
1055
		struct notes_tree *t = xcalloc(1, sizeof(struct notes_tree));
1056
		init_notes(t, item->string, combine_notes_ignore, flags);
1057
		trees[counter++] = t;
1058
	}
1059
	trees[counter] = NULL;
1060
	return trees;
1061
}
1062

1063
void init_display_notes(struct display_notes_opt *opt)
1064
{
1065
	memset(opt, 0, sizeof(*opt));
1066
	opt->use_default_notes = -1;
1067
	string_list_init_dup(&opt->extra_notes_refs);
1068
}
1069

1070
void release_display_notes(struct display_notes_opt *opt)
1071
{
1072
	string_list_clear(&opt->extra_notes_refs, 0);
1073
}
1074

1075
void enable_default_display_notes(struct display_notes_opt *opt, int *show_notes)
1076
{
1077
	opt->use_default_notes = 1;
1078
	*show_notes = 1;
1079
}
1080

1081
void enable_ref_display_notes(struct display_notes_opt *opt, int *show_notes,
1082
		const char *ref) {
1083
	struct strbuf buf = STRBUF_INIT;
1084
	strbuf_addstr(&buf, ref);
1085
	expand_notes_ref(&buf);
1086
	string_list_append_nodup(&opt->extra_notes_refs,
1087
				 strbuf_detach(&buf, NULL));
1088
	*show_notes = 1;
1089
}
1090

1091
void disable_display_notes(struct display_notes_opt *opt, int *show_notes)
1092
{
1093
	opt->use_default_notes = -1;
1094
	string_list_clear(&opt->extra_notes_refs, 0);
1095
	*show_notes = 0;
1096
}
1097

1098
void load_display_notes(struct display_notes_opt *opt)
1099
{
1100
	char *display_ref_env;
1101
	int load_config_refs = 0;
1102
	display_notes_refs.strdup_strings = 1;
1103

1104
	assert(!display_notes_trees);
1105

1106
	if (!opt || opt->use_default_notes > 0 ||
1107
	    (opt->use_default_notes == -1 && !opt->extra_notes_refs.nr)) {
1108
		string_list_append(&display_notes_refs, default_notes_ref());
1109
		display_ref_env = getenv(GIT_NOTES_DISPLAY_REF_ENVIRONMENT);
1110
		if (display_ref_env) {
1111
			string_list_add_refs_from_colon_sep(&display_notes_refs,
1112
							    display_ref_env);
1113
			load_config_refs = 0;
1114
		} else
1115
			load_config_refs = 1;
1116
	}
1117

1118
	git_config(notes_display_config, &load_config_refs);
1119

1120
	if (opt) {
1121
		struct string_list_item *item;
1122
		for_each_string_list_item(item, &opt->extra_notes_refs)
1123
			string_list_add_refs_by_glob(&display_notes_refs,
1124
						     item->string);
1125
	}
1126

1127
	display_notes_trees = load_notes_trees(&display_notes_refs, 0);
1128
	string_list_clear(&display_notes_refs, 0);
1129
}
1130

1131
int add_note(struct notes_tree *t, const struct object_id *object_oid,
1132
		const struct object_id *note_oid, combine_notes_fn combine_notes)
1133
{
1134
	struct leaf_node *l;
1135

1136
	if (!t)
1137
		t = &default_notes_tree;
1138
	assert(t->initialized);
1139
	t->dirty = 1;
1140
	if (!combine_notes)
1141
		combine_notes = t->combine_notes;
1142
	l = (struct leaf_node *) xmalloc(sizeof(struct leaf_node));
1143
	oidcpy(&l->key_oid, object_oid);
1144
	oidcpy(&l->val_oid, note_oid);
1145
	return note_tree_insert(t, t->root, 0, l, PTR_TYPE_NOTE, combine_notes);
1146
}
1147

1148
int remove_note(struct notes_tree *t, const unsigned char *object_sha1)
1149
{
1150
	struct leaf_node l;
1151

1152
	if (!t)
1153
		t = &default_notes_tree;
1154
	assert(t->initialized);
1155
	oidread(&l.key_oid, object_sha1, the_repository->hash_algo);
1156
	oidclr(&l.val_oid, the_repository->hash_algo);
1157
	note_tree_remove(t, t->root, 0, &l);
1158
	if (is_null_oid(&l.val_oid)) /* no note was removed */
1159
		return 1;
1160
	t->dirty = 1;
1161
	return 0;
1162
}
1163

1164
const struct object_id *get_note(struct notes_tree *t,
1165
		const struct object_id *oid)
1166
{
1167
	struct leaf_node *found;
1168

1169
	if (!t)
1170
		t = &default_notes_tree;
1171
	assert(t->initialized);
1172
	found = note_tree_find(t, t->root, 0, oid->hash);
1173
	return found ? &found->val_oid : NULL;
1174
}
1175

1176
int for_each_note(struct notes_tree *t, int flags, each_note_fn fn,
1177
		void *cb_data)
1178
{
1179
	if (!t)
1180
		t = &default_notes_tree;
1181
	assert(t->initialized);
1182
	return for_each_note_helper(t, t->root, 0, 0, flags, fn, cb_data);
1183
}
1184

1185
int write_notes_tree(struct notes_tree *t, struct object_id *result)
1186
{
1187
	struct tree_write_stack root;
1188
	struct write_each_note_data cb_data;
1189
	int ret;
1190
	int flags;
1191

1192
	if (!t)
1193
		t = &default_notes_tree;
1194
	assert(t->initialized);
1195

1196
	/* Prepare for traversal of current notes tree */
1197
	root.next = NULL; /* last forward entry in list is grounded */
1198
	strbuf_init(&root.buf, 256 * (32 + the_hash_algo->hexsz)); /* assume 256 entries */
1199
	root.path[0] = root.path[1] = '\0';
1200
	cb_data.root = &root;
1201
	cb_data.nn_list = &(t->first_non_note);
1202
	cb_data.nn_prev = NULL;
1203

1204
	/* Write tree objects representing current notes tree */
1205
	flags = FOR_EACH_NOTE_DONT_UNPACK_SUBTREES |
1206
		FOR_EACH_NOTE_YIELD_SUBTREES;
1207
	ret = for_each_note(t, flags, write_each_note, &cb_data) ||
1208
	      write_each_non_note_until(NULL, &cb_data) ||
1209
	      tree_write_stack_finish_subtree(&root) ||
1210
	      write_object_file(root.buf.buf, root.buf.len, OBJ_TREE, result);
1211
	strbuf_release(&root.buf);
1212
	return ret;
1213
}
1214

1215
void prune_notes(struct notes_tree *t, int flags)
1216
{
1217
	struct note_delete_list *l = NULL;
1218

1219
	if (!t)
1220
		t = &default_notes_tree;
1221
	assert(t->initialized);
1222

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

1225
	while (l) {
1226
		struct note_delete_list *next;
1227

1228
		if (flags & NOTES_PRUNE_VERBOSE)
1229
			printf("%s\n", hash_to_hex(l->sha1));
1230
		if (!(flags & NOTES_PRUNE_DRYRUN))
1231
			remove_note(t, l->sha1);
1232

1233
		next = l->next;
1234
		free(l);
1235
		l = next;
1236
	}
1237
}
1238

1239
void free_notes(struct notes_tree *t)
1240
{
1241
	if (!t)
1242
		t = &default_notes_tree;
1243
	if (t->root)
1244
		note_tree_free(t->root);
1245
	free(t->root);
1246
	while (t->first_non_note) {
1247
		t->prev_non_note = t->first_non_note->next;
1248
		free(t->first_non_note->path);
1249
		free(t->first_non_note);
1250
		t->first_non_note = t->prev_non_note;
1251
	}
1252
	free(t->ref);
1253
	memset(t, 0, sizeof(struct notes_tree));
1254
}
1255

1256
/*
1257
 * Fill the given strbuf with the notes associated with the given object.
1258
 *
1259
 * If the given notes_tree structure is not initialized, it will be auto-
1260
 * initialized to the default value (see documentation for init_notes() above).
1261
 * If the given notes_tree is NULL, the internal/default notes_tree will be
1262
 * used instead.
1263
 *
1264
 * (raw != 0) gives the %N userformat; otherwise, the note message is given
1265
 * for human consumption.
1266
 */
1267
static void format_note(struct notes_tree *t, const struct object_id *object_oid,
1268
			struct strbuf *sb, const char *output_encoding, int raw)
1269
{
1270
	static const char utf8[] = "utf-8";
1271
	const struct object_id *oid;
1272
	char *msg, *msg_p;
1273
	unsigned long linelen, msglen;
1274
	enum object_type type;
1275

1276
	if (!t)
1277
		t = &default_notes_tree;
1278
	if (!t->initialized)
1279
		init_notes(t, NULL, NULL, 0);
1280

1281
	oid = get_note(t, object_oid);
1282
	if (!oid)
1283
		return;
1284

1285
	if (!(msg = repo_read_object_file(the_repository, oid, &type, &msglen)) || type != OBJ_BLOB) {
1286
		free(msg);
1287
		return;
1288
	}
1289

1290
	if (output_encoding && *output_encoding &&
1291
	    !is_encoding_utf8(output_encoding)) {
1292
		char *reencoded = reencode_string(msg, output_encoding, utf8);
1293
		if (reencoded) {
1294
			free(msg);
1295
			msg = reencoded;
1296
			msglen = strlen(msg);
1297
		}
1298
	}
1299

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

1304
	if (!raw) {
1305
		const char *ref = t->ref;
1306
		if (!ref || !strcmp(ref, GIT_NOTES_DEFAULT_REF)) {
1307
			strbuf_addstr(sb, "\nNotes:\n");
1308
		} else {
1309
			skip_prefix(ref, "refs/", &ref);
1310
			skip_prefix(ref, "notes/", &ref);
1311
			strbuf_addf(sb, "\nNotes (%s):\n", ref);
1312
		}
1313
	}
1314

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

1318
		if (!raw)
1319
			strbuf_addstr(sb, "    ");
1320
		strbuf_add(sb, msg_p, linelen);
1321
		strbuf_addch(sb, '\n');
1322
	}
1323

1324
	free(msg);
1325
}
1326

1327
void format_display_notes(const struct object_id *object_oid,
1328
			  struct strbuf *sb, const char *output_encoding, int raw)
1329
{
1330
	int i;
1331
	assert(display_notes_trees);
1332
	for (i = 0; display_notes_trees[i]; i++)
1333
		format_note(display_notes_trees[i], object_oid, sb,
1334
			    output_encoding, raw);
1335
}
1336

1337
int copy_note(struct notes_tree *t,
1338
	      const struct object_id *from_obj, const struct object_id *to_obj,
1339
	      int force, combine_notes_fn combine_notes)
1340
{
1341
	const struct object_id *note = get_note(t, from_obj);
1342
	const struct object_id *existing_note = get_note(t, to_obj);
1343

1344
	if (!force && existing_note)
1345
		return 1;
1346

1347
	if (note)
1348
		return add_note(t, to_obj, note, combine_notes);
1349
	else if (existing_note)
1350
		return add_note(t, to_obj, null_oid(), combine_notes);
1351

1352
	return 0;
1353
}
1354

1355
void expand_notes_ref(struct strbuf *sb)
1356
{
1357
	if (starts_with(sb->buf, "refs/notes/"))
1358
		return; /* we're happy */
1359
	else if (starts_with(sb->buf, "notes/"))
1360
		strbuf_insertstr(sb, 0, "refs/");
1361
	else
1362
		strbuf_insertstr(sb, 0, "refs/notes/");
1363
}
1364

1365
void expand_loose_notes_ref(struct strbuf *sb)
1366
{
1367
	struct object_id object;
1368

1369
	if (repo_get_oid(the_repository, sb->buf, &object)) {
1370
		/* fallback to expand_notes_ref */
1371
		expand_notes_ref(sb);
1372
	}
1373
}
1374