9 #include "string-list.h"
13 * Use a non-balancing simple 16-tree structure with struct int_node as
14 * internal nodes, and struct leaf_node as leaf nodes. Each int_node has a
15 * 16-array of pointers to its children.
16 * The bottom 2 bits of each pointer is used to identify the pointer type
17 * - ptr & 3 == 0 - NULL pointer, assert(ptr == NULL)
18 * - ptr & 3 == 1 - pointer to next internal node - cast to struct int_node *
19 * - ptr & 3 == 2 - pointer to note entry - cast to struct leaf_node *
20 * - ptr & 3 == 3 - pointer to subtree entry - cast to struct leaf_node *
22 * The root node is a statically allocated struct int_node.
29 * Leaf nodes come in two variants, note entries and subtree entries,
30 * distinguished by the LSb of the leaf node pointer (see above).
31 * As a note entry, the key is the SHA1 of the referenced object, and the
32 * value is the SHA1 of the note object.
33 * As a subtree entry, the key is the prefix SHA1 (w/trailing NULs) of the
34 * referenced object, using the last byte of the key to store the length of
35 * the prefix. The value is the SHA1 of the tree object containing the notes
39 struct object_id key_oid
;
40 struct object_id val_oid
;
44 * A notes tree may contain entries that are not notes, and that do not follow
45 * the naming conventions of notes. There are typically none/few of these, but
46 * we still need to keep track of them. Keep a simple linked list sorted alpha-
47 * betically on the non-note path. The list is populated when parsing tree
48 * objects in load_subtree(), and the non-notes are correctly written back into
49 * the tree objects produced by write_notes_tree().
52 struct non_note
*next
; /* grounded (last->next == NULL) */
58 #define PTR_TYPE_NULL 0
59 #define PTR_TYPE_INTERNAL 1
60 #define PTR_TYPE_NOTE 2
61 #define PTR_TYPE_SUBTREE 3
63 #define GET_PTR_TYPE(ptr) ((uintptr_t) (ptr) & 3)
64 #define CLR_PTR_TYPE(ptr) ((void *) ((uintptr_t) (ptr) & ~3))
65 #define SET_PTR_TYPE(ptr, type) ((void *) ((uintptr_t) (ptr) | (type)))
67 #define GET_NIBBLE(n, sha1) ((((sha1)[(n) >> 1]) >> ((~(n) & 0x01) << 2)) & 0x0f)
69 #define KEY_INDEX (GIT_SHA1_RAWSZ - 1)
70 #define FANOUT_PATH_SEPARATORS ((GIT_SHA1_HEXSZ / 2) - 1)
71 #define SUBTREE_SHA1_PREFIXCMP(key_sha1, subtree_sha1) \
72 (memcmp(key_sha1, subtree_sha1, subtree_sha1[KEY_INDEX]))
74 struct notes_tree default_notes_tree
;
76 static struct string_list display_notes_refs
= STRING_LIST_INIT_NODUP
;
77 static struct notes_tree
**display_notes_trees
;
79 static void load_subtree(struct notes_tree
*t
, struct leaf_node
*subtree
,
80 struct int_node
*node
, unsigned int n
);
83 * Search the tree until the appropriate location for the given key is found:
84 * 1. Start at the root node, with n = 0
85 * 2. If a[0] at the current level is a matching subtree entry, unpack that
86 * subtree entry and remove it; restart search at the current level.
87 * 3. Use the nth nibble of the key as an index into a:
88 * - If a[n] is an int_node, recurse from #2 into that node and increment n
89 * - If a matching subtree entry, unpack that subtree entry (and remove it);
90 * restart search at the current level.
91 * - Otherwise, we have found one of the following:
92 * - a subtree entry which does not match the key
93 * - a note entry which may or may not match the key
94 * - an unused leaf node (NULL)
95 * In any case, set *tree and *n, and return pointer to the tree location.
97 static void **note_tree_search(struct notes_tree
*t
, struct int_node
**tree
,
98 unsigned char *n
, const unsigned char *key_sha1
)
102 void *p
= (*tree
)->a
[0];
104 if (GET_PTR_TYPE(p
) == PTR_TYPE_SUBTREE
) {
105 l
= (struct leaf_node
*) CLR_PTR_TYPE(p
);
106 if (!SUBTREE_SHA1_PREFIXCMP(key_sha1
, l
->key_oid
.hash
)) {
107 /* unpack tree and resume search */
108 (*tree
)->a
[0] = NULL
;
109 load_subtree(t
, l
, *tree
, *n
);
111 return note_tree_search(t
, tree
, n
, key_sha1
);
115 i
= GET_NIBBLE(*n
, key_sha1
);
117 switch (GET_PTR_TYPE(p
)) {
118 case PTR_TYPE_INTERNAL
:
119 *tree
= CLR_PTR_TYPE(p
);
121 return note_tree_search(t
, tree
, n
, key_sha1
);
122 case PTR_TYPE_SUBTREE
:
123 l
= (struct leaf_node
*) CLR_PTR_TYPE(p
);
124 if (!SUBTREE_SHA1_PREFIXCMP(key_sha1
, l
->key_oid
.hash
)) {
125 /* unpack tree and resume search */
126 (*tree
)->a
[i
] = NULL
;
127 load_subtree(t
, l
, *tree
, *n
);
129 return note_tree_search(t
, tree
, n
, key_sha1
);
133 return &((*tree
)->a
[i
]);
138 * To find a leaf_node:
139 * Search to the tree location appropriate for the given key:
140 * If a note entry with matching key, return the note entry, else return NULL.
142 static struct leaf_node
*note_tree_find(struct notes_tree
*t
,
143 struct int_node
*tree
, unsigned char n
,
144 const unsigned char *key_sha1
)
146 void **p
= note_tree_search(t
, &tree
, &n
, key_sha1
);
147 if (GET_PTR_TYPE(*p
) == PTR_TYPE_NOTE
) {
148 struct leaf_node
*l
= (struct leaf_node
*) CLR_PTR_TYPE(*p
);
149 if (!hashcmp(key_sha1
, l
->key_oid
.hash
))
156 * How to consolidate an int_node:
157 * If there are > 1 non-NULL entries, give up and return non-zero.
158 * Otherwise replace the int_node at the given index in the given parent node
159 * with the only NOTE entry (or a NULL entry if no entries) from the given
160 * tree, and return 0.
162 static int note_tree_consolidate(struct int_node
*tree
,
163 struct int_node
*parent
, unsigned char index
)
168 assert(tree
&& parent
);
169 assert(CLR_PTR_TYPE(parent
->a
[index
]) == tree
);
171 for (i
= 0; i
< 16; i
++) {
172 if (GET_PTR_TYPE(tree
->a
[i
]) != PTR_TYPE_NULL
) {
173 if (p
) /* more than one entry */
179 if (p
&& (GET_PTR_TYPE(p
) != PTR_TYPE_NOTE
))
181 /* replace tree with p in parent[index] */
182 parent
->a
[index
] = p
;
188 * To remove a leaf_node:
189 * Search to the tree location appropriate for the given leaf_node's key:
190 * - If location does not hold a matching entry, abort and do nothing.
191 * - Copy the matching entry's value into the given entry.
192 * - Replace the matching leaf_node with a NULL entry (and free the leaf_node).
193 * - Consolidate int_nodes repeatedly, while walking up the tree towards root.
195 static void note_tree_remove(struct notes_tree
*t
,
196 struct int_node
*tree
, unsigned char n
,
197 struct leaf_node
*entry
)
200 struct int_node
*parent_stack
[GIT_SHA1_RAWSZ
];
202 void **p
= note_tree_search(t
, &tree
, &n
, entry
->key_oid
.hash
);
204 assert(GET_PTR_TYPE(entry
) == 0); /* no type bits set */
205 if (GET_PTR_TYPE(*p
) != PTR_TYPE_NOTE
)
206 return; /* type mismatch, nothing to remove */
207 l
= (struct leaf_node
*) CLR_PTR_TYPE(*p
);
208 if (oidcmp(&l
->key_oid
, &entry
->key_oid
))
209 return; /* key mismatch, nothing to remove */
211 /* we have found a matching entry */
212 oidcpy(&entry
->val_oid
, &l
->val_oid
);
214 *p
= SET_PTR_TYPE(NULL
, PTR_TYPE_NULL
);
216 /* consolidate this tree level, and parent levels, if possible */
218 return; /* cannot consolidate top level */
219 /* first, build stack of ancestors between root and current node */
220 parent_stack
[0] = t
->root
;
221 for (i
= 0; i
< n
; i
++) {
222 j
= GET_NIBBLE(i
, entry
->key_oid
.hash
);
223 parent_stack
[i
+ 1] = CLR_PTR_TYPE(parent_stack
[i
]->a
[j
]);
225 assert(i
== n
&& parent_stack
[i
] == tree
);
226 /* next, unwind stack until note_tree_consolidate() is done */
228 !note_tree_consolidate(parent_stack
[i
], parent_stack
[i
- 1],
229 GET_NIBBLE(i
- 1, entry
->key_oid
.hash
)))
234 * To insert a leaf_node:
235 * Search to the tree location appropriate for the given leaf_node's key:
236 * - If location is unused (NULL), store the tweaked pointer directly there
237 * - If location holds a note entry that matches the note-to-be-inserted, then
238 * combine the two notes (by calling the given combine_notes function).
239 * - If location holds a note entry that matches the subtree-to-be-inserted,
240 * then unpack the subtree-to-be-inserted into the location.
241 * - If location holds a matching subtree entry, unpack the subtree at that
242 * location, and restart the insert operation from that level.
243 * - Else, create a new int_node, holding both the node-at-location and the
244 * node-to-be-inserted, and store the new int_node into the location.
246 static int note_tree_insert(struct notes_tree
*t
, struct int_node
*tree
,
247 unsigned char n
, struct leaf_node
*entry
, unsigned char type
,
248 combine_notes_fn combine_notes
)
250 struct int_node
*new_node
;
252 void **p
= note_tree_search(t
, &tree
, &n
, entry
->key_oid
.hash
);
255 assert(GET_PTR_TYPE(entry
) == 0); /* no type bits set */
256 l
= (struct leaf_node
*) CLR_PTR_TYPE(*p
);
257 switch (GET_PTR_TYPE(*p
)) {
260 if (is_null_oid(&entry
->val_oid
))
263 *p
= SET_PTR_TYPE(entry
, type
);
268 if (!oidcmp(&l
->key_oid
, &entry
->key_oid
)) {
269 /* skip concatenation if l == entry */
270 if (!oidcmp(&l
->val_oid
, &entry
->val_oid
))
273 ret
= combine_notes(l
->val_oid
.hash
,
274 entry
->val_oid
.hash
);
275 if (!ret
&& is_null_oid(&l
->val_oid
))
276 note_tree_remove(t
, tree
, n
, entry
);
281 case PTR_TYPE_SUBTREE
:
282 if (!SUBTREE_SHA1_PREFIXCMP(l
->key_oid
.hash
,
283 entry
->key_oid
.hash
)) {
285 load_subtree(t
, entry
, tree
, n
);
292 case PTR_TYPE_SUBTREE
:
293 if (!SUBTREE_SHA1_PREFIXCMP(entry
->key_oid
.hash
, l
->key_oid
.hash
)) {
294 /* unpack 'l' and restart insert */
296 load_subtree(t
, l
, tree
, n
);
298 return note_tree_insert(t
, tree
, n
, entry
, type
,
304 /* non-matching leaf_node */
305 assert(GET_PTR_TYPE(*p
) == PTR_TYPE_NOTE
||
306 GET_PTR_TYPE(*p
) == PTR_TYPE_SUBTREE
);
307 if (is_null_oid(&entry
->val_oid
)) { /* skip insertion of empty note */
311 new_node
= (struct int_node
*) xcalloc(1, sizeof(struct int_node
));
312 ret
= note_tree_insert(t
, new_node
, n
+ 1, l
, GET_PTR_TYPE(*p
),
316 *p
= SET_PTR_TYPE(new_node
, PTR_TYPE_INTERNAL
);
317 return note_tree_insert(t
, new_node
, n
+ 1, entry
, type
, combine_notes
);
320 /* Free the entire notes data contained in the given tree */
321 static void note_tree_free(struct int_node
*tree
)
324 for (i
= 0; i
< 16; i
++) {
325 void *p
= tree
->a
[i
];
326 switch (GET_PTR_TYPE(p
)) {
327 case PTR_TYPE_INTERNAL
:
328 note_tree_free(CLR_PTR_TYPE(p
));
331 case PTR_TYPE_SUBTREE
:
332 free(CLR_PTR_TYPE(p
));
338 * Convert a partial SHA1 hex string to the corresponding partial SHA1 value.
339 * - hex - Partial SHA1 segment in ASCII hex format
340 * - hex_len - Length of above segment. Must be multiple of 2 between 0 and 40
341 * - sha1 - Partial SHA1 value is written here
342 * - sha1_len - Max #bytes to store in sha1, Must be >= hex_len / 2, and < 20
343 * Returns -1 on error (invalid arguments or invalid SHA1 (not in hex format)).
344 * Otherwise, returns number of bytes written to sha1 (i.e. hex_len / 2).
345 * Pads sha1 with NULs up to sha1_len (not included in returned length).
347 static int get_oid_hex_segment(const char *hex
, unsigned int hex_len
,
348 unsigned char *oid
, unsigned int oid_len
)
350 unsigned int i
, len
= hex_len
>> 1;
351 if (hex_len
% 2 != 0 || len
> oid_len
)
353 for (i
= 0; i
< len
; i
++) {
354 unsigned int val
= (hexval(hex
[0]) << 4) | hexval(hex
[1]);
360 for (; i
< oid_len
; i
++)
365 static int non_note_cmp(const struct non_note
*a
, const struct non_note
*b
)
367 return strcmp(a
->path
, b
->path
);
370 /* note: takes ownership of path string */
371 static void add_non_note(struct notes_tree
*t
, char *path
,
372 unsigned int mode
, const unsigned char *sha1
)
374 struct non_note
*p
= t
->prev_non_note
, *n
;
375 n
= (struct non_note
*) xmalloc(sizeof(struct non_note
));
379 hashcpy(n
->oid
.hash
, sha1
);
380 t
->prev_non_note
= n
;
382 if (!t
->first_non_note
) {
383 t
->first_non_note
= n
;
387 if (non_note_cmp(p
, n
) < 0)
389 else if (non_note_cmp(t
->first_non_note
, n
) <= 0)
390 p
= t
->first_non_note
;
392 /* n sorts before t->first_non_note */
393 n
->next
= t
->first_non_note
;
394 t
->first_non_note
= n
;
398 /* n sorts equal or after p */
399 while (p
->next
&& non_note_cmp(p
->next
, n
) <= 0)
402 if (non_note_cmp(p
, n
) == 0) { /* n ~= p; overwrite p with n */
403 assert(strcmp(p
->path
, n
->path
) == 0);
405 oidcpy(&p
->oid
, &n
->oid
);
407 t
->prev_non_note
= p
;
411 /* n sorts between p and p->next */
416 static void load_subtree(struct notes_tree
*t
, struct leaf_node
*subtree
,
417 struct int_node
*node
, unsigned int n
)
419 struct object_id object_oid
;
420 unsigned int prefix_len
;
422 struct tree_desc desc
;
423 struct name_entry entry
;
425 buf
= fill_tree_descriptor(&desc
, subtree
->val_oid
.hash
);
427 die("Could not read %s for notes-index",
428 oid_to_hex(&subtree
->val_oid
));
430 prefix_len
= subtree
->key_oid
.hash
[KEY_INDEX
];
431 assert(prefix_len
* 2 >= n
);
432 memcpy(object_oid
.hash
, subtree
->key_oid
.hash
, prefix_len
);
433 while (tree_entry(&desc
, &entry
)) {
436 int path_len
= strlen(entry
.path
);
438 if (path_len
== 2 * (GIT_SHA1_RAWSZ
- prefix_len
)) {
439 /* This is potentially the remainder of the SHA-1 */
440 if (get_oid_hex_segment(entry
.path
, path_len
,
441 object_oid
.hash
+ prefix_len
,
442 GIT_SHA1_RAWSZ
- prefix_len
) < 0)
443 goto handle_non_note
; /* entry.path is not a SHA1 */
445 type
= PTR_TYPE_NOTE
;
446 l
= (struct leaf_node
*)
447 xcalloc(1, sizeof(struct leaf_node
));
448 oidcpy(&l
->key_oid
, &object_oid
);
449 oidcpy(&l
->val_oid
, entry
.oid
);
450 } else if (path_len
== 2) {
451 /* This is potentially an internal node */
453 if (!S_ISDIR(entry
.mode
))
454 /* internal nodes must be trees */
455 goto handle_non_note
;
457 if (get_oid_hex_segment(entry
.path
, 2,
458 object_oid
.hash
+ prefix_len
,
459 GIT_SHA1_RAWSZ
- prefix_len
) < 0)
460 goto handle_non_note
; /* entry.path is not a SHA1 */
462 type
= PTR_TYPE_SUBTREE
;
463 l
= (struct leaf_node
*)
464 xcalloc(1, sizeof(struct leaf_node
));
465 oidcpy(&l
->key_oid
, &object_oid
);
466 oidcpy(&l
->val_oid
, entry
.oid
);
467 l
->key_oid
.hash
[KEY_INDEX
] = (unsigned char) (prefix_len
+ 1);
469 /* This can't be part of a note */
470 goto handle_non_note
;
473 if (note_tree_insert(t
, node
, n
, l
, type
,
474 combine_notes_concatenate
))
475 die("Failed to load %s %s into notes tree "
477 type
== PTR_TYPE_NOTE
? "note" : "subtree",
478 oid_to_hex(&l
->key_oid
), t
->ref
);
484 * Determine full path for this non-note entry. The
485 * filename is already found in entry.path, but the
486 * directory part of the path must be deduced from the
487 * subtree containing this entry based on our
488 * knowledge that the overall notes tree follows a
489 * strict byte-based progressive fanout structure
490 * (i.e. using 2/38, 2/2/36, etc. fanouts).
493 struct strbuf non_note_path
= STRBUF_INIT
;
494 const char *q
= oid_to_hex(&subtree
->key_oid
);
496 for (i
= 0; i
< prefix_len
; i
++) {
497 strbuf_addch(&non_note_path
, *q
++);
498 strbuf_addch(&non_note_path
, *q
++);
499 strbuf_addch(&non_note_path
, '/');
501 strbuf_addstr(&non_note_path
, entry
.path
);
502 add_non_note(t
, strbuf_detach(&non_note_path
, NULL
),
503 entry
.mode
, entry
.oid
->hash
);
510 * Determine optimal on-disk fanout for this part of the notes tree
512 * Given a (sub)tree and the level in the internal tree structure, determine
513 * whether or not the given existing fanout should be expanded for this
516 * Values of the 'fanout' variable:
517 * - 0: No fanout (all notes are stored directly in the root notes tree)
520 * - 3: 2/2/2/34 fanout
523 static unsigned char determine_fanout(struct int_node
*tree
, unsigned char n
,
524 unsigned char fanout
)
527 * The following is a simple heuristic that works well in practice:
528 * For each even-numbered 16-tree level (remember that each on-disk
529 * fanout level corresponds to _two_ 16-tree levels), peek at all 16
530 * entries at that tree level. If all of them are either int_nodes or
531 * subtree entries, then there are likely plenty of notes below this
532 * level, so we return an incremented fanout.
535 if ((n
% 2) || (n
> 2 * fanout
))
537 for (i
= 0; i
< 16; i
++) {
538 switch (GET_PTR_TYPE(tree
->a
[i
])) {
539 case PTR_TYPE_SUBTREE
:
540 case PTR_TYPE_INTERNAL
:
549 /* hex SHA1 + 19 * '/' + NUL */
550 #define FANOUT_PATH_MAX GIT_SHA1_HEXSZ + FANOUT_PATH_SEPARATORS + 1
552 static void construct_path_with_fanout(const unsigned char *sha1
,
553 unsigned char fanout
, char *path
)
555 unsigned int i
= 0, j
= 0;
556 const char *hex_sha1
= sha1_to_hex(sha1
);
557 assert(fanout
< GIT_SHA1_RAWSZ
);
559 path
[i
++] = hex_sha1
[j
++];
560 path
[i
++] = hex_sha1
[j
++];
564 xsnprintf(path
+ i
, FANOUT_PATH_MAX
- i
, "%s", hex_sha1
+ j
);
567 static int for_each_note_helper(struct notes_tree
*t
, struct int_node
*tree
,
568 unsigned char n
, unsigned char fanout
, int flags
,
569 each_note_fn fn
, void *cb_data
)
575 static char path
[FANOUT_PATH_MAX
];
577 fanout
= determine_fanout(tree
, n
, fanout
);
578 for (i
= 0; i
< 16; i
++) {
581 switch (GET_PTR_TYPE(p
)) {
582 case PTR_TYPE_INTERNAL
:
583 /* recurse into int_node */
584 ret
= for_each_note_helper(t
, CLR_PTR_TYPE(p
), n
+ 1,
585 fanout
, flags
, fn
, cb_data
);
587 case PTR_TYPE_SUBTREE
:
588 l
= (struct leaf_node
*) CLR_PTR_TYPE(p
);
590 * Subtree entries in the note tree represent parts of
591 * the note tree that have not yet been explored. There
592 * is a direct relationship between subtree entries at
593 * level 'n' in the tree, and the 'fanout' variable:
594 * Subtree entries at level 'n <= 2 * fanout' should be
595 * preserved, since they correspond exactly to a fanout
596 * directory in the on-disk structure. However, subtree
597 * entries at level 'n > 2 * fanout' should NOT be
598 * preserved, but rather consolidated into the above
599 * notes tree level. We achieve this by unconditionally
600 * unpacking subtree entries that exist below the
601 * threshold level at 'n = 2 * fanout'.
603 if (n
<= 2 * fanout
&&
604 flags
& FOR_EACH_NOTE_YIELD_SUBTREES
) {
605 /* invoke callback with subtree */
606 unsigned int path_len
=
607 l
->key_oid
.hash
[KEY_INDEX
] * 2 + fanout
;
608 assert(path_len
< FANOUT_PATH_MAX
- 1);
609 construct_path_with_fanout(l
->key_oid
.hash
,
612 /* Create trailing slash, if needed */
613 if (path
[path_len
- 1] != '/')
614 path
[path_len
++] = '/';
615 path
[path_len
] = '\0';
616 ret
= fn(&l
->key_oid
, &l
->val_oid
,
620 if (n
> fanout
* 2 ||
621 !(flags
& FOR_EACH_NOTE_DONT_UNPACK_SUBTREES
)) {
622 /* unpack subtree and resume traversal */
624 load_subtree(t
, l
, tree
, n
);
630 l
= (struct leaf_node
*) CLR_PTR_TYPE(p
);
631 construct_path_with_fanout(l
->key_oid
.hash
, fanout
,
633 ret
= fn(&l
->key_oid
, &l
->val_oid
, path
,
643 struct tree_write_stack
{
644 struct tree_write_stack
*next
;
646 char path
[2]; /* path to subtree in next, if any */
649 static inline int matches_tree_write_stack(struct tree_write_stack
*tws
,
650 const char *full_path
)
652 return full_path
[0] == tws
->path
[0] &&
653 full_path
[1] == tws
->path
[1] &&
657 static void write_tree_entry(struct strbuf
*buf
, unsigned int mode
,
658 const char *path
, unsigned int path_len
, const
661 strbuf_addf(buf
, "%o %.*s%c", mode
, path_len
, path
, '\0');
662 strbuf_add(buf
, sha1
, GIT_SHA1_RAWSZ
);
665 static void tree_write_stack_init_subtree(struct tree_write_stack
*tws
,
668 struct tree_write_stack
*n
;
670 assert(tws
->path
[0] == '\0' && tws
->path
[1] == '\0');
671 n
= (struct tree_write_stack
*)
672 xmalloc(sizeof(struct tree_write_stack
));
674 strbuf_init(&n
->buf
, 256 * (32 + GIT_SHA1_HEXSZ
)); /* assume 256 entries per tree */
675 n
->path
[0] = n
->path
[1] = '\0';
677 tws
->path
[0] = path
[0];
678 tws
->path
[1] = path
[1];
681 static int tree_write_stack_finish_subtree(struct tree_write_stack
*tws
)
684 struct tree_write_stack
*n
= tws
->next
;
687 ret
= tree_write_stack_finish_subtree(n
);
690 ret
= write_sha1_file(n
->buf
.buf
, n
->buf
.len
, tree_type
, s
.hash
);
693 strbuf_release(&n
->buf
);
696 write_tree_entry(&tws
->buf
, 040000, tws
->path
, 2, s
.hash
);
697 tws
->path
[0] = tws
->path
[1] = '\0';
702 static int write_each_note_helper(struct tree_write_stack
*tws
,
703 const char *path
, unsigned int mode
,
704 const struct object_id
*oid
)
706 size_t path_len
= strlen(path
);
710 /* Determine common part of tree write stack */
711 while (tws
&& 3 * n
< path_len
&&
712 matches_tree_write_stack(tws
, path
+ 3 * n
)) {
717 /* tws point to last matching tree_write_stack entry */
718 ret
= tree_write_stack_finish_subtree(tws
);
722 /* Start subtrees needed to satisfy path */
723 while (3 * n
+ 2 < path_len
&& path
[3 * n
+ 2] == '/') {
724 tree_write_stack_init_subtree(tws
, path
+ 3 * n
);
729 /* There should be no more directory components in the given path */
730 assert(memchr(path
+ 3 * n
, '/', path_len
- (3 * n
)) == NULL
);
732 /* Finally add given entry to the current tree object */
733 write_tree_entry(&tws
->buf
, mode
, path
+ 3 * n
, path_len
- (3 * n
),
739 struct write_each_note_data
{
740 struct tree_write_stack
*root
;
741 struct non_note
*next_non_note
;
744 static int write_each_non_note_until(const char *note_path
,
745 struct write_each_note_data
*d
)
747 struct non_note
*n
= d
->next_non_note
;
749 while (n
&& (!note_path
|| (cmp
= strcmp(n
->path
, note_path
)) <= 0)) {
750 if (note_path
&& cmp
== 0)
751 ; /* do nothing, prefer note to non-note */
753 ret
= write_each_note_helper(d
->root
, n
->path
, n
->mode
,
760 d
->next_non_note
= n
;
764 static int write_each_note(const struct object_id
*object_oid
,
765 const struct object_id
*note_oid
, char *note_path
,
768 struct write_each_note_data
*d
=
769 (struct write_each_note_data
*) cb_data
;
770 size_t note_path_len
= strlen(note_path
);
771 unsigned int mode
= 0100644;
773 if (note_path
[note_path_len
- 1] == '/') {
776 note_path
[note_path_len
] = '\0';
779 assert(note_path_len
<= GIT_SHA1_HEXSZ
+ FANOUT_PATH_SEPARATORS
);
781 /* Weave non-note entries into note entries */
782 return write_each_non_note_until(note_path
, d
) ||
783 write_each_note_helper(d
->root
, note_path
, mode
, note_oid
);
786 struct note_delete_list
{
787 struct note_delete_list
*next
;
788 const unsigned char *sha1
;
791 static int prune_notes_helper(const struct object_id
*object_oid
,
792 const struct object_id
*note_oid
, char *note_path
,
795 struct note_delete_list
**l
= (struct note_delete_list
**) cb_data
;
796 struct note_delete_list
*n
;
798 if (has_object_file(object_oid
))
799 return 0; /* nothing to do for this note */
801 /* failed to find object => prune this note */
802 n
= (struct note_delete_list
*) xmalloc(sizeof(*n
));
804 n
->sha1
= object_oid
->hash
;
809 int combine_notes_concatenate(unsigned char *cur_sha1
,
810 const unsigned char *new_sha1
)
812 char *cur_msg
= NULL
, *new_msg
= NULL
, *buf
;
813 unsigned long cur_len
, new_len
, buf_len
;
814 enum object_type cur_type
, new_type
;
817 /* read in both note blob objects */
818 if (!is_null_sha1(new_sha1
))
819 new_msg
= read_sha1_file(new_sha1
, &new_type
, &new_len
);
820 if (!new_msg
|| !new_len
|| new_type
!= OBJ_BLOB
) {
824 if (!is_null_sha1(cur_sha1
))
825 cur_msg
= read_sha1_file(cur_sha1
, &cur_type
, &cur_len
);
826 if (!cur_msg
|| !cur_len
|| cur_type
!= OBJ_BLOB
) {
829 hashcpy(cur_sha1
, new_sha1
);
833 /* we will separate the notes by two newlines anyway */
834 if (cur_msg
[cur_len
- 1] == '\n')
837 /* concatenate cur_msg and new_msg into buf */
838 buf_len
= cur_len
+ 2 + new_len
;
839 buf
= (char *) xmalloc(buf_len
);
840 memcpy(buf
, cur_msg
, cur_len
);
842 buf
[cur_len
+ 1] = '\n';
843 memcpy(buf
+ cur_len
+ 2, new_msg
, new_len
);
847 /* create a new blob object from buf */
848 ret
= write_sha1_file(buf
, buf_len
, blob_type
, cur_sha1
);
853 int combine_notes_overwrite(unsigned char *cur_sha1
,
854 const unsigned char *new_sha1
)
856 hashcpy(cur_sha1
, new_sha1
);
860 int combine_notes_ignore(unsigned char *cur_sha1
,
861 const unsigned char *new_sha1
)
867 * Add the lines from the named object to list, with trailing
870 static int string_list_add_note_lines(struct string_list
*list
,
871 const unsigned char *sha1
)
877 if (is_null_sha1(sha1
))
880 /* read_sha1_file NUL-terminates */
881 data
= read_sha1_file(sha1
, &t
, &len
);
882 if (t
!= OBJ_BLOB
|| !data
|| !len
) {
884 return t
!= OBJ_BLOB
|| !data
;
888 * If the last line of the file is EOL-terminated, this will
889 * add an empty string to the list. But it will be removed
890 * later, along with any empty strings that came from empty
891 * lines within the file.
893 string_list_split(list
, data
, '\n', -1);
898 static int string_list_join_lines_helper(struct string_list_item
*item
,
901 struct strbuf
*buf
= cb_data
;
902 strbuf_addstr(buf
, item
->string
);
903 strbuf_addch(buf
, '\n');
907 int combine_notes_cat_sort_uniq(unsigned char *cur_sha1
,
908 const unsigned char *new_sha1
)
910 struct string_list sort_uniq_list
= STRING_LIST_INIT_DUP
;
911 struct strbuf buf
= STRBUF_INIT
;
914 /* read both note blob objects into unique_lines */
915 if (string_list_add_note_lines(&sort_uniq_list
, cur_sha1
))
917 if (string_list_add_note_lines(&sort_uniq_list
, new_sha1
))
919 string_list_remove_empty_items(&sort_uniq_list
, 0);
920 string_list_sort(&sort_uniq_list
);
921 string_list_remove_duplicates(&sort_uniq_list
, 0);
923 /* create a new blob object from sort_uniq_list */
924 if (for_each_string_list(&sort_uniq_list
,
925 string_list_join_lines_helper
, &buf
))
928 ret
= write_sha1_file(buf
.buf
, buf
.len
, blob_type
, cur_sha1
);
931 strbuf_release(&buf
);
932 string_list_clear(&sort_uniq_list
, 0);
936 static int string_list_add_one_ref(const char *refname
, const struct object_id
*oid
,
939 struct string_list
*refs
= cb
;
940 if (!unsorted_string_list_has_string(refs
, refname
))
941 string_list_append(refs
, refname
);
946 * The list argument must have strdup_strings set on it.
948 void string_list_add_refs_by_glob(struct string_list
*list
, const char *glob
)
950 assert(list
->strdup_strings
);
951 if (has_glob_specials(glob
)) {
952 for_each_glob_ref(string_list_add_one_ref
, glob
, list
);
954 struct object_id oid
;
955 if (get_oid(glob
, &oid
))
956 warning("notes ref %s is invalid", glob
);
957 if (!unsorted_string_list_has_string(list
, glob
))
958 string_list_append(list
, glob
);
962 void string_list_add_refs_from_colon_sep(struct string_list
*list
,
965 struct string_list split
= STRING_LIST_INIT_NODUP
;
966 char *globs_copy
= xstrdup(globs
);
969 string_list_split_in_place(&split
, globs_copy
, ':', -1);
970 string_list_remove_empty_items(&split
, 0);
972 for (i
= 0; i
< split
.nr
; i
++)
973 string_list_add_refs_by_glob(list
, split
.items
[i
].string
);
975 string_list_clear(&split
, 0);
979 static int notes_display_config(const char *k
, const char *v
, void *cb
)
983 if (*load_refs
&& !strcmp(k
, "notes.displayref")) {
985 config_error_nonbool(k
);
986 string_list_add_refs_by_glob(&display_notes_refs
, v
);
992 const char *default_notes_ref(void)
994 const char *notes_ref
= NULL
;
996 notes_ref
= getenv(GIT_NOTES_REF_ENVIRONMENT
);
998 notes_ref
= notes_ref_name
; /* value of core.notesRef config */
1000 notes_ref
= GIT_NOTES_DEFAULT_REF
;
1004 void init_notes(struct notes_tree
*t
, const char *notes_ref
,
1005 combine_notes_fn combine_notes
, int flags
)
1007 struct object_id oid
, object_oid
;
1009 struct leaf_node root_tree
;
1012 t
= &default_notes_tree
;
1013 assert(!t
->initialized
);
1016 notes_ref
= default_notes_ref();
1019 combine_notes
= combine_notes_concatenate
;
1021 t
->root
= (struct int_node
*) xcalloc(1, sizeof(struct int_node
));
1022 t
->first_non_note
= NULL
;
1023 t
->prev_non_note
= NULL
;
1024 t
->ref
= xstrdup_or_null(notes_ref
);
1025 t
->update_ref
= (flags
& NOTES_INIT_WRITABLE
) ? t
->ref
: NULL
;
1026 t
->combine_notes
= combine_notes
;
1030 if (flags
& NOTES_INIT_EMPTY
|| !notes_ref
||
1031 get_sha1_treeish(notes_ref
, object_oid
.hash
))
1033 if (flags
& NOTES_INIT_WRITABLE
&& read_ref(notes_ref
, object_oid
.hash
))
1034 die("Cannot use notes ref %s", notes_ref
);
1035 if (get_tree_entry(object_oid
.hash
, "", oid
.hash
, &mode
))
1036 die("Failed to read notes tree referenced by %s (%s)",
1037 notes_ref
, oid_to_hex(&object_oid
));
1039 oidclr(&root_tree
.key_oid
);
1040 oidcpy(&root_tree
.val_oid
, &oid
);
1041 load_subtree(t
, &root_tree
, t
->root
, 0);
1044 struct notes_tree
**load_notes_trees(struct string_list
*refs
, int flags
)
1046 struct string_list_item
*item
;
1048 struct notes_tree
**trees
;
1049 ALLOC_ARRAY(trees
, refs
->nr
+ 1);
1050 for_each_string_list_item(item
, refs
) {
1051 struct notes_tree
*t
= xcalloc(1, sizeof(struct notes_tree
));
1052 init_notes(t
, item
->string
, combine_notes_ignore
, flags
);
1053 trees
[counter
++] = t
;
1055 trees
[counter
] = NULL
;
1059 void init_display_notes(struct display_notes_opt
*opt
)
1061 char *display_ref_env
;
1062 int load_config_refs
= 0;
1063 display_notes_refs
.strdup_strings
= 1;
1065 assert(!display_notes_trees
);
1067 if (!opt
|| opt
->use_default_notes
> 0 ||
1068 (opt
->use_default_notes
== -1 && !opt
->extra_notes_refs
.nr
)) {
1069 string_list_append(&display_notes_refs
, default_notes_ref());
1070 display_ref_env
= getenv(GIT_NOTES_DISPLAY_REF_ENVIRONMENT
);
1071 if (display_ref_env
) {
1072 string_list_add_refs_from_colon_sep(&display_notes_refs
,
1074 load_config_refs
= 0;
1076 load_config_refs
= 1;
1079 git_config(notes_display_config
, &load_config_refs
);
1082 struct string_list_item
*item
;
1083 for_each_string_list_item(item
, &opt
->extra_notes_refs
)
1084 string_list_add_refs_by_glob(&display_notes_refs
,
1088 display_notes_trees
= load_notes_trees(&display_notes_refs
, 0);
1089 string_list_clear(&display_notes_refs
, 0);
1092 int add_note(struct notes_tree
*t
, const struct object_id
*object_oid
,
1093 const struct object_id
*note_oid
, combine_notes_fn combine_notes
)
1095 struct leaf_node
*l
;
1098 t
= &default_notes_tree
;
1099 assert(t
->initialized
);
1102 combine_notes
= t
->combine_notes
;
1103 l
= (struct leaf_node
*) xmalloc(sizeof(struct leaf_node
));
1104 oidcpy(&l
->key_oid
, object_oid
);
1105 oidcpy(&l
->val_oid
, note_oid
);
1106 return note_tree_insert(t
, t
->root
, 0, l
, PTR_TYPE_NOTE
, combine_notes
);
1109 int remove_note(struct notes_tree
*t
, const unsigned char *object_sha1
)
1114 t
= &default_notes_tree
;
1115 assert(t
->initialized
);
1116 hashcpy(l
.key_oid
.hash
, object_sha1
);
1118 note_tree_remove(t
, t
->root
, 0, &l
);
1119 if (is_null_oid(&l
.val_oid
)) /* no note was removed */
1125 const struct object_id
*get_note(struct notes_tree
*t
,
1126 const struct object_id
*oid
)
1128 struct leaf_node
*found
;
1131 t
= &default_notes_tree
;
1132 assert(t
->initialized
);
1133 found
= note_tree_find(t
, t
->root
, 0, oid
->hash
);
1134 return found
? &found
->val_oid
: NULL
;
1137 int for_each_note(struct notes_tree
*t
, int flags
, each_note_fn fn
,
1141 t
= &default_notes_tree
;
1142 assert(t
->initialized
);
1143 return for_each_note_helper(t
, t
->root
, 0, 0, flags
, fn
, cb_data
);
1146 int write_notes_tree(struct notes_tree
*t
, unsigned char *result
)
1148 struct tree_write_stack root
;
1149 struct write_each_note_data cb_data
;
1153 t
= &default_notes_tree
;
1154 assert(t
->initialized
);
1156 /* Prepare for traversal of current notes tree */
1157 root
.next
= NULL
; /* last forward entry in list is grounded */
1158 strbuf_init(&root
.buf
, 256 * (32 + GIT_SHA1_HEXSZ
)); /* assume 256 entries */
1159 root
.path
[0] = root
.path
[1] = '\0';
1160 cb_data
.root
= &root
;
1161 cb_data
.next_non_note
= t
->first_non_note
;
1163 /* Write tree objects representing current notes tree */
1164 ret
= for_each_note(t
, FOR_EACH_NOTE_DONT_UNPACK_SUBTREES
|
1165 FOR_EACH_NOTE_YIELD_SUBTREES
,
1166 write_each_note
, &cb_data
) ||
1167 write_each_non_note_until(NULL
, &cb_data
) ||
1168 tree_write_stack_finish_subtree(&root
) ||
1169 write_sha1_file(root
.buf
.buf
, root
.buf
.len
, tree_type
, result
);
1170 strbuf_release(&root
.buf
);
1174 void prune_notes(struct notes_tree
*t
, int flags
)
1176 struct note_delete_list
*l
= NULL
;
1179 t
= &default_notes_tree
;
1180 assert(t
->initialized
);
1182 for_each_note(t
, 0, prune_notes_helper
, &l
);
1185 if (flags
& NOTES_PRUNE_VERBOSE
)
1186 printf("%s\n", sha1_to_hex(l
->sha1
));
1187 if (!(flags
& NOTES_PRUNE_DRYRUN
))
1188 remove_note(t
, l
->sha1
);
1193 void free_notes(struct notes_tree
*t
)
1196 t
= &default_notes_tree
;
1198 note_tree_free(t
->root
);
1200 while (t
->first_non_note
) {
1201 t
->prev_non_note
= t
->first_non_note
->next
;
1202 free(t
->first_non_note
->path
);
1203 free(t
->first_non_note
);
1204 t
->first_non_note
= t
->prev_non_note
;
1207 memset(t
, 0, sizeof(struct notes_tree
));
1211 * Fill the given strbuf with the notes associated with the given object.
1213 * If the given notes_tree structure is not initialized, it will be auto-
1214 * initialized to the default value (see documentation for init_notes() above).
1215 * If the given notes_tree is NULL, the internal/default notes_tree will be
1218 * (raw != 0) gives the %N userformat; otherwise, the note message is given
1219 * for human consumption.
1221 static void format_note(struct notes_tree
*t
, const struct object_id
*object_oid
,
1222 struct strbuf
*sb
, const char *output_encoding
, int raw
)
1224 static const char utf8
[] = "utf-8";
1225 const struct object_id
*oid
;
1227 unsigned long linelen
, msglen
;
1228 enum object_type type
;
1231 t
= &default_notes_tree
;
1232 if (!t
->initialized
)
1233 init_notes(t
, NULL
, NULL
, 0);
1235 oid
= get_note(t
, object_oid
);
1239 if (!(msg
= read_sha1_file(oid
->hash
, &type
, &msglen
)) || type
!= OBJ_BLOB
) {
1244 if (output_encoding
&& *output_encoding
&&
1245 !is_encoding_utf8(output_encoding
)) {
1246 char *reencoded
= reencode_string(msg
, output_encoding
, utf8
);
1250 msglen
= strlen(msg
);
1254 /* we will end the annotation by a newline anyway */
1255 if (msglen
&& msg
[msglen
- 1] == '\n')
1259 const char *ref
= t
->ref
;
1260 if (!ref
|| !strcmp(ref
, GIT_NOTES_DEFAULT_REF
)) {
1261 strbuf_addstr(sb
, "\nNotes:\n");
1263 if (starts_with(ref
, "refs/"))
1265 if (starts_with(ref
, "notes/"))
1267 strbuf_addf(sb
, "\nNotes (%s):\n", ref
);
1271 for (msg_p
= msg
; msg_p
< msg
+ msglen
; msg_p
+= linelen
+ 1) {
1272 linelen
= strchrnul(msg_p
, '\n') - msg_p
;
1275 strbuf_addstr(sb
, " ");
1276 strbuf_add(sb
, msg_p
, linelen
);
1277 strbuf_addch(sb
, '\n');
1283 void format_display_notes(const struct object_id
*object_oid
,
1284 struct strbuf
*sb
, const char *output_encoding
, int raw
)
1287 assert(display_notes_trees
);
1288 for (i
= 0; display_notes_trees
[i
]; i
++)
1289 format_note(display_notes_trees
[i
], object_oid
, sb
,
1290 output_encoding
, raw
);
1293 int copy_note(struct notes_tree
*t
,
1294 const struct object_id
*from_obj
, const struct object_id
*to_obj
,
1295 int force
, combine_notes_fn combine_notes
)
1297 const struct object_id
*note
= get_note(t
, from_obj
);
1298 const struct object_id
*existing_note
= get_note(t
, to_obj
);
1300 if (!force
&& existing_note
)
1304 return add_note(t
, to_obj
, note
, combine_notes
);
1305 else if (existing_note
)
1306 return add_note(t
, to_obj
, &null_oid
, combine_notes
);
1311 void expand_notes_ref(struct strbuf
*sb
)
1313 if (starts_with(sb
->buf
, "refs/notes/"))
1314 return; /* we're happy */
1315 else if (starts_with(sb
->buf
, "notes/"))
1316 strbuf_insert(sb
, 0, "refs/", 5);
1318 strbuf_insert(sb
, 0, "refs/notes/", 11);
1321 void expand_loose_notes_ref(struct strbuf
*sb
)
1323 struct object_id object
;
1325 if (get_oid(sb
->buf
, &object
)) {
1326 /* fallback to expand_notes_ref */
1327 expand_notes_ref(sb
);