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 unsigned char key_sha1
[20];
40 unsigned char val_sha1
[20];
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) */
55 unsigned char sha1
[20];
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 SUBTREE_SHA1_PREFIXCMP(key_sha1, subtree_sha1) \
70 (memcmp(key_sha1, subtree_sha1, subtree_sha1[19]))
72 struct notes_tree default_notes_tree
;
74 static struct string_list display_notes_refs
= STRING_LIST_INIT_NODUP
;
75 static struct notes_tree
**display_notes_trees
;
77 static void load_subtree(struct notes_tree
*t
, struct leaf_node
*subtree
,
78 struct int_node
*node
, unsigned int n
);
81 * Search the tree until the appropriate location for the given key is found:
82 * 1. Start at the root node, with n = 0
83 * 2. If a[0] at the current level is a matching subtree entry, unpack that
84 * subtree entry and remove it; restart search at the current level.
85 * 3. Use the nth nibble of the key as an index into a:
86 * - If a[n] is an int_node, recurse from #2 into that node and increment n
87 * - If a matching subtree entry, unpack that subtree entry (and remove it);
88 * restart search at the current level.
89 * - Otherwise, we have found one of the following:
90 * - a subtree entry which does not match the key
91 * - a note entry which may or may not match the key
92 * - an unused leaf node (NULL)
93 * In any case, set *tree and *n, and return pointer to the tree location.
95 static void **note_tree_search(struct notes_tree
*t
, struct int_node
**tree
,
96 unsigned char *n
, const unsigned char *key_sha1
)
100 void *p
= (*tree
)->a
[0];
102 if (GET_PTR_TYPE(p
) == PTR_TYPE_SUBTREE
) {
103 l
= (struct leaf_node
*) CLR_PTR_TYPE(p
);
104 if (!SUBTREE_SHA1_PREFIXCMP(key_sha1
, l
->key_sha1
)) {
105 /* unpack tree and resume search */
106 (*tree
)->a
[0] = NULL
;
107 load_subtree(t
, l
, *tree
, *n
);
109 return note_tree_search(t
, tree
, n
, key_sha1
);
113 i
= GET_NIBBLE(*n
, key_sha1
);
115 switch (GET_PTR_TYPE(p
)) {
116 case PTR_TYPE_INTERNAL
:
117 *tree
= CLR_PTR_TYPE(p
);
119 return note_tree_search(t
, tree
, n
, key_sha1
);
120 case PTR_TYPE_SUBTREE
:
121 l
= (struct leaf_node
*) CLR_PTR_TYPE(p
);
122 if (!SUBTREE_SHA1_PREFIXCMP(key_sha1
, l
->key_sha1
)) {
123 /* unpack tree and resume search */
124 (*tree
)->a
[i
] = NULL
;
125 load_subtree(t
, l
, *tree
, *n
);
127 return note_tree_search(t
, tree
, n
, key_sha1
);
131 return &((*tree
)->a
[i
]);
136 * To find a leaf_node:
137 * Search to the tree location appropriate for the given key:
138 * If a note entry with matching key, return the note entry, else return NULL.
140 static struct leaf_node
*note_tree_find(struct notes_tree
*t
,
141 struct int_node
*tree
, unsigned char n
,
142 const unsigned char *key_sha1
)
144 void **p
= note_tree_search(t
, &tree
, &n
, key_sha1
);
145 if (GET_PTR_TYPE(*p
) == PTR_TYPE_NOTE
) {
146 struct leaf_node
*l
= (struct leaf_node
*) CLR_PTR_TYPE(*p
);
147 if (!hashcmp(key_sha1
, l
->key_sha1
))
154 * How to consolidate an int_node:
155 * If there are > 1 non-NULL entries, give up and return non-zero.
156 * Otherwise replace the int_node at the given index in the given parent node
157 * with the only NOTE entry (or a NULL entry if no entries) from the given
158 * tree, and return 0.
160 static int note_tree_consolidate(struct int_node
*tree
,
161 struct int_node
*parent
, unsigned char index
)
166 assert(tree
&& parent
);
167 assert(CLR_PTR_TYPE(parent
->a
[index
]) == tree
);
169 for (i
= 0; i
< 16; i
++) {
170 if (GET_PTR_TYPE(tree
->a
[i
]) != PTR_TYPE_NULL
) {
171 if (p
) /* more than one entry */
177 if (p
&& (GET_PTR_TYPE(p
) != PTR_TYPE_NOTE
))
179 /* replace tree with p in parent[index] */
180 parent
->a
[index
] = p
;
186 * To remove a leaf_node:
187 * Search to the tree location appropriate for the given leaf_node's key:
188 * - If location does not hold a matching entry, abort and do nothing.
189 * - Copy the matching entry's value into the given entry.
190 * - Replace the matching leaf_node with a NULL entry (and free the leaf_node).
191 * - Consolidate int_nodes repeatedly, while walking up the tree towards root.
193 static void note_tree_remove(struct notes_tree
*t
,
194 struct int_node
*tree
, unsigned char n
,
195 struct leaf_node
*entry
)
198 struct int_node
*parent_stack
[20];
200 void **p
= note_tree_search(t
, &tree
, &n
, entry
->key_sha1
);
202 assert(GET_PTR_TYPE(entry
) == 0); /* no type bits set */
203 if (GET_PTR_TYPE(*p
) != PTR_TYPE_NOTE
)
204 return; /* type mismatch, nothing to remove */
205 l
= (struct leaf_node
*) CLR_PTR_TYPE(*p
);
206 if (hashcmp(l
->key_sha1
, entry
->key_sha1
))
207 return; /* key mismatch, nothing to remove */
209 /* we have found a matching entry */
210 hashcpy(entry
->val_sha1
, l
->val_sha1
);
212 *p
= SET_PTR_TYPE(NULL
, PTR_TYPE_NULL
);
214 /* consolidate this tree level, and parent levels, if possible */
216 return; /* cannot consolidate top level */
217 /* first, build stack of ancestors between root and current node */
218 parent_stack
[0] = t
->root
;
219 for (i
= 0; i
< n
; i
++) {
220 j
= GET_NIBBLE(i
, entry
->key_sha1
);
221 parent_stack
[i
+ 1] = CLR_PTR_TYPE(parent_stack
[i
]->a
[j
]);
223 assert(i
== n
&& parent_stack
[i
] == tree
);
224 /* next, unwind stack until note_tree_consolidate() is done */
226 !note_tree_consolidate(parent_stack
[i
], parent_stack
[i
- 1],
227 GET_NIBBLE(i
- 1, entry
->key_sha1
)))
232 * To insert a leaf_node:
233 * Search to the tree location appropriate for the given leaf_node's key:
234 * - If location is unused (NULL), store the tweaked pointer directly there
235 * - If location holds a note entry that matches the note-to-be-inserted, then
236 * combine the two notes (by calling the given combine_notes function).
237 * - If location holds a note entry that matches the subtree-to-be-inserted,
238 * then unpack the subtree-to-be-inserted into the location.
239 * - If location holds a matching subtree entry, unpack the subtree at that
240 * location, and restart the insert operation from that level.
241 * - Else, create a new int_node, holding both the node-at-location and the
242 * node-to-be-inserted, and store the new int_node into the location.
244 static int note_tree_insert(struct notes_tree
*t
, struct int_node
*tree
,
245 unsigned char n
, struct leaf_node
*entry
, unsigned char type
,
246 combine_notes_fn combine_notes
)
248 struct int_node
*new_node
;
250 void **p
= note_tree_search(t
, &tree
, &n
, entry
->key_sha1
);
253 assert(GET_PTR_TYPE(entry
) == 0); /* no type bits set */
254 l
= (struct leaf_node
*) CLR_PTR_TYPE(*p
);
255 switch (GET_PTR_TYPE(*p
)) {
258 if (is_null_sha1(entry
->val_sha1
))
261 *p
= SET_PTR_TYPE(entry
, type
);
266 if (!hashcmp(l
->key_sha1
, entry
->key_sha1
)) {
267 /* skip concatenation if l == entry */
268 if (!hashcmp(l
->val_sha1
, entry
->val_sha1
))
271 ret
= combine_notes(l
->val_sha1
,
273 if (!ret
&& is_null_sha1(l
->val_sha1
))
274 note_tree_remove(t
, tree
, n
, entry
);
279 case PTR_TYPE_SUBTREE
:
280 if (!SUBTREE_SHA1_PREFIXCMP(l
->key_sha1
,
283 load_subtree(t
, entry
, tree
, n
);
290 case PTR_TYPE_SUBTREE
:
291 if (!SUBTREE_SHA1_PREFIXCMP(entry
->key_sha1
, l
->key_sha1
)) {
292 /* unpack 'l' and restart insert */
294 load_subtree(t
, l
, tree
, n
);
296 return note_tree_insert(t
, tree
, n
, entry
, type
,
302 /* non-matching leaf_node */
303 assert(GET_PTR_TYPE(*p
) == PTR_TYPE_NOTE
||
304 GET_PTR_TYPE(*p
) == PTR_TYPE_SUBTREE
);
305 if (is_null_sha1(entry
->val_sha1
)) { /* skip insertion of empty note */
309 new_node
= (struct int_node
*) xcalloc(1, sizeof(struct int_node
));
310 ret
= note_tree_insert(t
, new_node
, n
+ 1, l
, GET_PTR_TYPE(*p
),
314 *p
= SET_PTR_TYPE(new_node
, PTR_TYPE_INTERNAL
);
315 return note_tree_insert(t
, new_node
, n
+ 1, entry
, type
, combine_notes
);
318 /* Free the entire notes data contained in the given tree */
319 static void note_tree_free(struct int_node
*tree
)
322 for (i
= 0; i
< 16; i
++) {
323 void *p
= tree
->a
[i
];
324 switch (GET_PTR_TYPE(p
)) {
325 case PTR_TYPE_INTERNAL
:
326 note_tree_free(CLR_PTR_TYPE(p
));
329 case PTR_TYPE_SUBTREE
:
330 free(CLR_PTR_TYPE(p
));
336 * Convert a partial SHA1 hex string to the corresponding partial SHA1 value.
337 * - hex - Partial SHA1 segment in ASCII hex format
338 * - hex_len - Length of above segment. Must be multiple of 2 between 0 and 40
339 * - sha1 - Partial SHA1 value is written here
340 * - sha1_len - Max #bytes to store in sha1, Must be >= hex_len / 2, and < 20
341 * Returns -1 on error (invalid arguments or invalid SHA1 (not in hex format)).
342 * Otherwise, returns number of bytes written to sha1 (i.e. hex_len / 2).
343 * Pads sha1 with NULs up to sha1_len (not included in returned length).
345 static int get_sha1_hex_segment(const char *hex
, unsigned int hex_len
,
346 unsigned char *sha1
, unsigned int sha1_len
)
348 unsigned int i
, len
= hex_len
>> 1;
349 if (hex_len
% 2 != 0 || len
> sha1_len
)
351 for (i
= 0; i
< len
; i
++) {
352 unsigned int val
= (hexval(hex
[0]) << 4) | hexval(hex
[1]);
358 for (; i
< sha1_len
; i
++)
363 static int non_note_cmp(const struct non_note
*a
, const struct non_note
*b
)
365 return strcmp(a
->path
, b
->path
);
368 /* note: takes ownership of path string */
369 static void add_non_note(struct notes_tree
*t
, char *path
,
370 unsigned int mode
, const unsigned char *sha1
)
372 struct non_note
*p
= t
->prev_non_note
, *n
;
373 n
= (struct non_note
*) xmalloc(sizeof(struct non_note
));
377 hashcpy(n
->sha1
, sha1
);
378 t
->prev_non_note
= n
;
380 if (!t
->first_non_note
) {
381 t
->first_non_note
= n
;
385 if (non_note_cmp(p
, n
) < 0)
387 else if (non_note_cmp(t
->first_non_note
, n
) <= 0)
388 p
= t
->first_non_note
;
390 /* n sorts before t->first_non_note */
391 n
->next
= t
->first_non_note
;
392 t
->first_non_note
= n
;
396 /* n sorts equal or after p */
397 while (p
->next
&& non_note_cmp(p
->next
, n
) <= 0)
400 if (non_note_cmp(p
, n
) == 0) { /* n ~= p; overwrite p with n */
401 assert(strcmp(p
->path
, n
->path
) == 0);
403 hashcpy(p
->sha1
, n
->sha1
);
405 t
->prev_non_note
= p
;
409 /* n sorts between p and p->next */
414 static void load_subtree(struct notes_tree
*t
, struct leaf_node
*subtree
,
415 struct int_node
*node
, unsigned int n
)
417 unsigned char object_sha1
[20];
418 unsigned int prefix_len
;
420 struct tree_desc desc
;
421 struct name_entry entry
;
426 buf
= fill_tree_descriptor(&desc
, subtree
->val_sha1
);
428 die("Could not read %s for notes-index",
429 sha1_to_hex(subtree
->val_sha1
));
431 prefix_len
= subtree
->key_sha1
[19];
432 assert(prefix_len
* 2 >= n
);
433 memcpy(object_sha1
, subtree
->key_sha1
, prefix_len
);
434 while (tree_entry(&desc
, &entry
)) {
435 path_len
= strlen(entry
.path
);
436 len
= get_sha1_hex_segment(entry
.path
, path_len
,
437 object_sha1
+ prefix_len
, 20 - prefix_len
);
439 goto handle_non_note
; /* entry.path is not a SHA1 */
443 * If object SHA1 is complete (len == 20), assume note object
444 * If object SHA1 is incomplete (len < 20), and current
445 * component consists of 2 hex chars, assume note subtree
448 type
= PTR_TYPE_NOTE
;
449 l
= (struct leaf_node
*)
450 xcalloc(1, sizeof(struct leaf_node
));
451 hashcpy(l
->key_sha1
, object_sha1
);
452 hashcpy(l
->val_sha1
, entry
.oid
->hash
);
454 if (!S_ISDIR(entry
.mode
) || path_len
!= 2)
455 goto handle_non_note
; /* not subtree */
456 l
->key_sha1
[19] = (unsigned char) len
;
457 type
= PTR_TYPE_SUBTREE
;
459 if (note_tree_insert(t
, node
, n
, l
, type
,
460 combine_notes_concatenate
))
461 die("Failed to load %s %s into notes tree "
463 type
== PTR_TYPE_NOTE
? "note" : "subtree",
464 sha1_to_hex(l
->key_sha1
), t
->ref
);
470 * Determine full path for this non-note entry:
471 * The filename is already found in entry.path, but the
472 * directory part of the path must be deduced from the subtree
473 * containing this entry. We assume here that the overall notes
474 * tree follows a strict byte-based progressive fanout
475 * structure (i.e. using 2/38, 2/2/36, etc. fanouts, and not
476 * e.g. 4/36 fanout). This means that if a non-note is found at
477 * path "dead/beef", the following code will register it as
478 * being found on "de/ad/beef".
479 * On the other hand, if you use such non-obvious non-note
480 * paths in the middle of a notes tree, you deserve what's
481 * coming to you ;). Note that for non-notes that are not
482 * SHA1-like at the top level, there will be no problems.
484 * To conclude, it is strongly advised to make sure non-notes
485 * have at least one non-hex character in the top-level path
489 struct strbuf non_note_path
= STRBUF_INIT
;
490 const char *q
= sha1_to_hex(subtree
->key_sha1
);
492 for (i
= 0; i
< prefix_len
; i
++) {
493 strbuf_addch(&non_note_path
, *q
++);
494 strbuf_addch(&non_note_path
, *q
++);
495 strbuf_addch(&non_note_path
, '/');
497 strbuf_addstr(&non_note_path
, entry
.path
);
498 add_non_note(t
, strbuf_detach(&non_note_path
, NULL
),
499 entry
.mode
, entry
.oid
->hash
);
506 * Determine optimal on-disk fanout for this part of the notes tree
508 * Given a (sub)tree and the level in the internal tree structure, determine
509 * whether or not the given existing fanout should be expanded for this
512 * Values of the 'fanout' variable:
513 * - 0: No fanout (all notes are stored directly in the root notes tree)
516 * - 3: 2/2/2/34 fanout
519 static unsigned char determine_fanout(struct int_node
*tree
, unsigned char n
,
520 unsigned char fanout
)
523 * The following is a simple heuristic that works well in practice:
524 * For each even-numbered 16-tree level (remember that each on-disk
525 * fanout level corresponds to _two_ 16-tree levels), peek at all 16
526 * entries at that tree level. If all of them are either int_nodes or
527 * subtree entries, then there are likely plenty of notes below this
528 * level, so we return an incremented fanout.
531 if ((n
% 2) || (n
> 2 * fanout
))
533 for (i
= 0; i
< 16; i
++) {
534 switch (GET_PTR_TYPE(tree
->a
[i
])) {
535 case PTR_TYPE_SUBTREE
:
536 case PTR_TYPE_INTERNAL
:
545 /* hex SHA1 + 19 * '/' + NUL */
546 #define FANOUT_PATH_MAX 40 + 19 + 1
548 static void construct_path_with_fanout(const unsigned char *sha1
,
549 unsigned char fanout
, char *path
)
551 unsigned int i
= 0, j
= 0;
552 const char *hex_sha1
= sha1_to_hex(sha1
);
555 path
[i
++] = hex_sha1
[j
++];
556 path
[i
++] = hex_sha1
[j
++];
560 xsnprintf(path
+ i
, FANOUT_PATH_MAX
- i
, "%s", hex_sha1
+ j
);
563 static int for_each_note_helper(struct notes_tree
*t
, struct int_node
*tree
,
564 unsigned char n
, unsigned char fanout
, int flags
,
565 each_note_fn fn
, void *cb_data
)
571 static char path
[FANOUT_PATH_MAX
];
573 fanout
= determine_fanout(tree
, n
, fanout
);
574 for (i
= 0; i
< 16; i
++) {
577 switch (GET_PTR_TYPE(p
)) {
578 case PTR_TYPE_INTERNAL
:
579 /* recurse into int_node */
580 ret
= for_each_note_helper(t
, CLR_PTR_TYPE(p
), n
+ 1,
581 fanout
, flags
, fn
, cb_data
);
583 case PTR_TYPE_SUBTREE
:
584 l
= (struct leaf_node
*) CLR_PTR_TYPE(p
);
586 * Subtree entries in the note tree represent parts of
587 * the note tree that have not yet been explored. There
588 * is a direct relationship between subtree entries at
589 * level 'n' in the tree, and the 'fanout' variable:
590 * Subtree entries at level 'n <= 2 * fanout' should be
591 * preserved, since they correspond exactly to a fanout
592 * directory in the on-disk structure. However, subtree
593 * entries at level 'n > 2 * fanout' should NOT be
594 * preserved, but rather consolidated into the above
595 * notes tree level. We achieve this by unconditionally
596 * unpacking subtree entries that exist below the
597 * threshold level at 'n = 2 * fanout'.
599 if (n
<= 2 * fanout
&&
600 flags
& FOR_EACH_NOTE_YIELD_SUBTREES
) {
601 /* invoke callback with subtree */
602 unsigned int path_len
=
603 l
->key_sha1
[19] * 2 + fanout
;
604 assert(path_len
< FANOUT_PATH_MAX
- 1);
605 construct_path_with_fanout(l
->key_sha1
, fanout
,
607 /* Create trailing slash, if needed */
608 if (path
[path_len
- 1] != '/')
609 path
[path_len
++] = '/';
610 path
[path_len
] = '\0';
611 ret
= fn(l
->key_sha1
, l
->val_sha1
, path
,
614 if (n
> fanout
* 2 ||
615 !(flags
& FOR_EACH_NOTE_DONT_UNPACK_SUBTREES
)) {
616 /* unpack subtree and resume traversal */
618 load_subtree(t
, l
, tree
, n
);
624 l
= (struct leaf_node
*) CLR_PTR_TYPE(p
);
625 construct_path_with_fanout(l
->key_sha1
, fanout
, path
);
626 ret
= fn(l
->key_sha1
, l
->val_sha1
, path
, cb_data
);
635 struct tree_write_stack
{
636 struct tree_write_stack
*next
;
638 char path
[2]; /* path to subtree in next, if any */
641 static inline int matches_tree_write_stack(struct tree_write_stack
*tws
,
642 const char *full_path
)
644 return full_path
[0] == tws
->path
[0] &&
645 full_path
[1] == tws
->path
[1] &&
649 static void write_tree_entry(struct strbuf
*buf
, unsigned int mode
,
650 const char *path
, unsigned int path_len
, const
653 strbuf_addf(buf
, "%o %.*s%c", mode
, path_len
, path
, '\0');
654 strbuf_add(buf
, sha1
, 20);
657 static void tree_write_stack_init_subtree(struct tree_write_stack
*tws
,
660 struct tree_write_stack
*n
;
662 assert(tws
->path
[0] == '\0' && tws
->path
[1] == '\0');
663 n
= (struct tree_write_stack
*)
664 xmalloc(sizeof(struct tree_write_stack
));
666 strbuf_init(&n
->buf
, 256 * (32 + 40)); /* assume 256 entries per tree */
667 n
->path
[0] = n
->path
[1] = '\0';
669 tws
->path
[0] = path
[0];
670 tws
->path
[1] = path
[1];
673 static int tree_write_stack_finish_subtree(struct tree_write_stack
*tws
)
676 struct tree_write_stack
*n
= tws
->next
;
679 ret
= tree_write_stack_finish_subtree(n
);
682 ret
= write_sha1_file(n
->buf
.buf
, n
->buf
.len
, tree_type
, s
);
685 strbuf_release(&n
->buf
);
688 write_tree_entry(&tws
->buf
, 040000, tws
->path
, 2, s
);
689 tws
->path
[0] = tws
->path
[1] = '\0';
694 static int write_each_note_helper(struct tree_write_stack
*tws
,
695 const char *path
, unsigned int mode
,
696 const unsigned char *sha1
)
698 size_t path_len
= strlen(path
);
702 /* Determine common part of tree write stack */
703 while (tws
&& 3 * n
< path_len
&&
704 matches_tree_write_stack(tws
, path
+ 3 * n
)) {
709 /* tws point to last matching tree_write_stack entry */
710 ret
= tree_write_stack_finish_subtree(tws
);
714 /* Start subtrees needed to satisfy path */
715 while (3 * n
+ 2 < path_len
&& path
[3 * n
+ 2] == '/') {
716 tree_write_stack_init_subtree(tws
, path
+ 3 * n
);
721 /* There should be no more directory components in the given path */
722 assert(memchr(path
+ 3 * n
, '/', path_len
- (3 * n
)) == NULL
);
724 /* Finally add given entry to the current tree object */
725 write_tree_entry(&tws
->buf
, mode
, path
+ 3 * n
, path_len
- (3 * n
),
731 struct write_each_note_data
{
732 struct tree_write_stack
*root
;
733 struct non_note
*next_non_note
;
736 static int write_each_non_note_until(const char *note_path
,
737 struct write_each_note_data
*d
)
739 struct non_note
*n
= d
->next_non_note
;
741 while (n
&& (!note_path
|| (cmp
= strcmp(n
->path
, note_path
)) <= 0)) {
742 if (note_path
&& cmp
== 0)
743 ; /* do nothing, prefer note to non-note */
745 ret
= write_each_note_helper(d
->root
, n
->path
, n
->mode
,
752 d
->next_non_note
= n
;
756 static int write_each_note(const unsigned char *object_sha1
,
757 const unsigned char *note_sha1
, char *note_path
,
760 struct write_each_note_data
*d
=
761 (struct write_each_note_data
*) cb_data
;
762 size_t note_path_len
= strlen(note_path
);
763 unsigned int mode
= 0100644;
765 if (note_path
[note_path_len
- 1] == '/') {
768 note_path
[note_path_len
] = '\0';
771 assert(note_path_len
<= 40 + 19);
773 /* Weave non-note entries into note entries */
774 return write_each_non_note_until(note_path
, d
) ||
775 write_each_note_helper(d
->root
, note_path
, mode
, note_sha1
);
778 struct note_delete_list
{
779 struct note_delete_list
*next
;
780 const unsigned char *sha1
;
783 static int prune_notes_helper(const unsigned char *object_sha1
,
784 const unsigned char *note_sha1
, char *note_path
,
787 struct note_delete_list
**l
= (struct note_delete_list
**) cb_data
;
788 struct note_delete_list
*n
;
790 if (has_sha1_file(object_sha1
))
791 return 0; /* nothing to do for this note */
793 /* failed to find object => prune this note */
794 n
= (struct note_delete_list
*) xmalloc(sizeof(*n
));
796 n
->sha1
= object_sha1
;
801 int combine_notes_concatenate(unsigned char *cur_sha1
,
802 const unsigned char *new_sha1
)
804 char *cur_msg
= NULL
, *new_msg
= NULL
, *buf
;
805 unsigned long cur_len
, new_len
, buf_len
;
806 enum object_type cur_type
, new_type
;
809 /* read in both note blob objects */
810 if (!is_null_sha1(new_sha1
))
811 new_msg
= read_sha1_file(new_sha1
, &new_type
, &new_len
);
812 if (!new_msg
|| !new_len
|| new_type
!= OBJ_BLOB
) {
816 if (!is_null_sha1(cur_sha1
))
817 cur_msg
= read_sha1_file(cur_sha1
, &cur_type
, &cur_len
);
818 if (!cur_msg
|| !cur_len
|| cur_type
!= OBJ_BLOB
) {
821 hashcpy(cur_sha1
, new_sha1
);
825 /* we will separate the notes by two newlines anyway */
826 if (cur_msg
[cur_len
- 1] == '\n')
829 /* concatenate cur_msg and new_msg into buf */
830 buf_len
= cur_len
+ 2 + new_len
;
831 buf
= (char *) xmalloc(buf_len
);
832 memcpy(buf
, cur_msg
, cur_len
);
834 buf
[cur_len
+ 1] = '\n';
835 memcpy(buf
+ cur_len
+ 2, new_msg
, new_len
);
839 /* create a new blob object from buf */
840 ret
= write_sha1_file(buf
, buf_len
, blob_type
, cur_sha1
);
845 int combine_notes_overwrite(unsigned char *cur_sha1
,
846 const unsigned char *new_sha1
)
848 hashcpy(cur_sha1
, new_sha1
);
852 int combine_notes_ignore(unsigned char *cur_sha1
,
853 const unsigned char *new_sha1
)
859 * Add the lines from the named object to list, with trailing
862 static int string_list_add_note_lines(struct string_list
*list
,
863 const unsigned char *sha1
)
869 if (is_null_sha1(sha1
))
872 /* read_sha1_file NUL-terminates */
873 data
= read_sha1_file(sha1
, &t
, &len
);
874 if (t
!= OBJ_BLOB
|| !data
|| !len
) {
876 return t
!= OBJ_BLOB
|| !data
;
880 * If the last line of the file is EOL-terminated, this will
881 * add an empty string to the list. But it will be removed
882 * later, along with any empty strings that came from empty
883 * lines within the file.
885 string_list_split(list
, data
, '\n', -1);
890 static int string_list_join_lines_helper(struct string_list_item
*item
,
893 struct strbuf
*buf
= cb_data
;
894 strbuf_addstr(buf
, item
->string
);
895 strbuf_addch(buf
, '\n');
899 int combine_notes_cat_sort_uniq(unsigned char *cur_sha1
,
900 const unsigned char *new_sha1
)
902 struct string_list sort_uniq_list
= STRING_LIST_INIT_DUP
;
903 struct strbuf buf
= STRBUF_INIT
;
906 /* read both note blob objects into unique_lines */
907 if (string_list_add_note_lines(&sort_uniq_list
, cur_sha1
))
909 if (string_list_add_note_lines(&sort_uniq_list
, new_sha1
))
911 string_list_remove_empty_items(&sort_uniq_list
, 0);
912 string_list_sort(&sort_uniq_list
);
913 string_list_remove_duplicates(&sort_uniq_list
, 0);
915 /* create a new blob object from sort_uniq_list */
916 if (for_each_string_list(&sort_uniq_list
,
917 string_list_join_lines_helper
, &buf
))
920 ret
= write_sha1_file(buf
.buf
, buf
.len
, blob_type
, cur_sha1
);
923 strbuf_release(&buf
);
924 string_list_clear(&sort_uniq_list
, 0);
928 static int string_list_add_one_ref(const char *refname
, const struct object_id
*oid
,
931 struct string_list
*refs
= cb
;
932 if (!unsorted_string_list_has_string(refs
, refname
))
933 string_list_append(refs
, refname
);
938 * The list argument must have strdup_strings set on it.
940 void string_list_add_refs_by_glob(struct string_list
*list
, const char *glob
)
942 assert(list
->strdup_strings
);
943 if (has_glob_specials(glob
)) {
944 for_each_glob_ref(string_list_add_one_ref
, glob
, list
);
946 unsigned char sha1
[20];
947 if (get_sha1(glob
, sha1
))
948 warning("notes ref %s is invalid", glob
);
949 if (!unsorted_string_list_has_string(list
, glob
))
950 string_list_append(list
, glob
);
954 void string_list_add_refs_from_colon_sep(struct string_list
*list
,
957 struct string_list split
= STRING_LIST_INIT_NODUP
;
958 char *globs_copy
= xstrdup(globs
);
961 string_list_split_in_place(&split
, globs_copy
, ':', -1);
962 string_list_remove_empty_items(&split
, 0);
964 for (i
= 0; i
< split
.nr
; i
++)
965 string_list_add_refs_by_glob(list
, split
.items
[i
].string
);
967 string_list_clear(&split
, 0);
971 static int notes_display_config(const char *k
, const char *v
, void *cb
)
975 if (*load_refs
&& !strcmp(k
, "notes.displayref")) {
977 config_error_nonbool(k
);
978 string_list_add_refs_by_glob(&display_notes_refs
, v
);
984 const char *default_notes_ref(void)
986 const char *notes_ref
= NULL
;
988 notes_ref
= getenv(GIT_NOTES_REF_ENVIRONMENT
);
990 notes_ref
= notes_ref_name
; /* value of core.notesRef config */
992 notes_ref
= GIT_NOTES_DEFAULT_REF
;
996 void init_notes(struct notes_tree
*t
, const char *notes_ref
,
997 combine_notes_fn combine_notes
, int flags
)
999 struct object_id oid
, object_oid
;
1001 struct leaf_node root_tree
;
1004 t
= &default_notes_tree
;
1005 assert(!t
->initialized
);
1008 notes_ref
= default_notes_ref();
1011 combine_notes
= combine_notes_concatenate
;
1013 t
->root
= (struct int_node
*) xcalloc(1, sizeof(struct int_node
));
1014 t
->first_non_note
= NULL
;
1015 t
->prev_non_note
= NULL
;
1016 t
->ref
= xstrdup_or_null(notes_ref
);
1017 t
->update_ref
= (flags
& NOTES_INIT_WRITABLE
) ? t
->ref
: NULL
;
1018 t
->combine_notes
= combine_notes
;
1022 if (flags
& NOTES_INIT_EMPTY
|| !notes_ref
||
1023 get_sha1_treeish(notes_ref
, object_oid
.hash
))
1025 if (flags
& NOTES_INIT_WRITABLE
&& read_ref(notes_ref
, object_oid
.hash
))
1026 die("Cannot use notes ref %s", notes_ref
);
1027 if (get_tree_entry(object_oid
.hash
, "", oid
.hash
, &mode
))
1028 die("Failed to read notes tree referenced by %s (%s)",
1029 notes_ref
, oid_to_hex(&object_oid
));
1031 hashclr(root_tree
.key_sha1
);
1032 hashcpy(root_tree
.val_sha1
, oid
.hash
);
1033 load_subtree(t
, &root_tree
, t
->root
, 0);
1036 struct notes_tree
**load_notes_trees(struct string_list
*refs
, int flags
)
1038 struct string_list_item
*item
;
1040 struct notes_tree
**trees
;
1041 ALLOC_ARRAY(trees
, refs
->nr
+ 1);
1042 for_each_string_list_item(item
, refs
) {
1043 struct notes_tree
*t
= xcalloc(1, sizeof(struct notes_tree
));
1044 init_notes(t
, item
->string
, combine_notes_ignore
, flags
);
1045 trees
[counter
++] = t
;
1047 trees
[counter
] = NULL
;
1051 void init_display_notes(struct display_notes_opt
*opt
)
1053 char *display_ref_env
;
1054 int load_config_refs
= 0;
1055 display_notes_refs
.strdup_strings
= 1;
1057 assert(!display_notes_trees
);
1059 if (!opt
|| opt
->use_default_notes
> 0 ||
1060 (opt
->use_default_notes
== -1 && !opt
->extra_notes_refs
.nr
)) {
1061 string_list_append(&display_notes_refs
, default_notes_ref());
1062 display_ref_env
= getenv(GIT_NOTES_DISPLAY_REF_ENVIRONMENT
);
1063 if (display_ref_env
) {
1064 string_list_add_refs_from_colon_sep(&display_notes_refs
,
1066 load_config_refs
= 0;
1068 load_config_refs
= 1;
1071 git_config(notes_display_config
, &load_config_refs
);
1074 struct string_list_item
*item
;
1075 for_each_string_list_item(item
, &opt
->extra_notes_refs
)
1076 string_list_add_refs_by_glob(&display_notes_refs
,
1080 display_notes_trees
= load_notes_trees(&display_notes_refs
, 0);
1081 string_list_clear(&display_notes_refs
, 0);
1084 int add_note(struct notes_tree
*t
, const unsigned char *object_sha1
,
1085 const unsigned char *note_sha1
, combine_notes_fn combine_notes
)
1087 struct leaf_node
*l
;
1090 t
= &default_notes_tree
;
1091 assert(t
->initialized
);
1094 combine_notes
= t
->combine_notes
;
1095 l
= (struct leaf_node
*) xmalloc(sizeof(struct leaf_node
));
1096 hashcpy(l
->key_sha1
, object_sha1
);
1097 hashcpy(l
->val_sha1
, note_sha1
);
1098 return note_tree_insert(t
, t
->root
, 0, l
, PTR_TYPE_NOTE
, combine_notes
);
1101 int remove_note(struct notes_tree
*t
, const unsigned char *object_sha1
)
1106 t
= &default_notes_tree
;
1107 assert(t
->initialized
);
1108 hashcpy(l
.key_sha1
, object_sha1
);
1109 hashclr(l
.val_sha1
);
1110 note_tree_remove(t
, t
->root
, 0, &l
);
1111 if (is_null_sha1(l
.val_sha1
)) /* no note was removed */
1117 const unsigned char *get_note(struct notes_tree
*t
,
1118 const unsigned char *object_sha1
)
1120 struct leaf_node
*found
;
1123 t
= &default_notes_tree
;
1124 assert(t
->initialized
);
1125 found
= note_tree_find(t
, t
->root
, 0, object_sha1
);
1126 return found
? found
->val_sha1
: NULL
;
1129 int for_each_note(struct notes_tree
*t
, int flags
, each_note_fn fn
,
1133 t
= &default_notes_tree
;
1134 assert(t
->initialized
);
1135 return for_each_note_helper(t
, t
->root
, 0, 0, flags
, fn
, cb_data
);
1138 int write_notes_tree(struct notes_tree
*t
, unsigned char *result
)
1140 struct tree_write_stack root
;
1141 struct write_each_note_data cb_data
;
1145 t
= &default_notes_tree
;
1146 assert(t
->initialized
);
1148 /* Prepare for traversal of current notes tree */
1149 root
.next
= NULL
; /* last forward entry in list is grounded */
1150 strbuf_init(&root
.buf
, 256 * (32 + 40)); /* assume 256 entries */
1151 root
.path
[0] = root
.path
[1] = '\0';
1152 cb_data
.root
= &root
;
1153 cb_data
.next_non_note
= t
->first_non_note
;
1155 /* Write tree objects representing current notes tree */
1156 ret
= for_each_note(t
, FOR_EACH_NOTE_DONT_UNPACK_SUBTREES
|
1157 FOR_EACH_NOTE_YIELD_SUBTREES
,
1158 write_each_note
, &cb_data
) ||
1159 write_each_non_note_until(NULL
, &cb_data
) ||
1160 tree_write_stack_finish_subtree(&root
) ||
1161 write_sha1_file(root
.buf
.buf
, root
.buf
.len
, tree_type
, result
);
1162 strbuf_release(&root
.buf
);
1166 void prune_notes(struct notes_tree
*t
, int flags
)
1168 struct note_delete_list
*l
= NULL
;
1171 t
= &default_notes_tree
;
1172 assert(t
->initialized
);
1174 for_each_note(t
, 0, prune_notes_helper
, &l
);
1177 if (flags
& NOTES_PRUNE_VERBOSE
)
1178 printf("%s\n", sha1_to_hex(l
->sha1
));
1179 if (!(flags
& NOTES_PRUNE_DRYRUN
))
1180 remove_note(t
, l
->sha1
);
1185 void free_notes(struct notes_tree
*t
)
1188 t
= &default_notes_tree
;
1190 note_tree_free(t
->root
);
1192 while (t
->first_non_note
) {
1193 t
->prev_non_note
= t
->first_non_note
->next
;
1194 free(t
->first_non_note
->path
);
1195 free(t
->first_non_note
);
1196 t
->first_non_note
= t
->prev_non_note
;
1199 memset(t
, 0, sizeof(struct notes_tree
));
1203 * Fill the given strbuf with the notes associated with the given object.
1205 * If the given notes_tree structure is not initialized, it will be auto-
1206 * initialized to the default value (see documentation for init_notes() above).
1207 * If the given notes_tree is NULL, the internal/default notes_tree will be
1210 * (raw != 0) gives the %N userformat; otherwise, the note message is given
1211 * for human consumption.
1213 static void format_note(struct notes_tree
*t
, const unsigned char *object_sha1
,
1214 struct strbuf
*sb
, const char *output_encoding
, int raw
)
1216 static const char utf8
[] = "utf-8";
1217 const unsigned char *sha1
;
1219 unsigned long linelen
, msglen
;
1220 enum object_type type
;
1223 t
= &default_notes_tree
;
1224 if (!t
->initialized
)
1225 init_notes(t
, NULL
, NULL
, 0);
1227 sha1
= get_note(t
, object_sha1
);
1231 if (!(msg
= read_sha1_file(sha1
, &type
, &msglen
)) || type
!= OBJ_BLOB
) {
1236 if (output_encoding
&& *output_encoding
&&
1237 !is_encoding_utf8(output_encoding
)) {
1238 char *reencoded
= reencode_string(msg
, output_encoding
, utf8
);
1242 msglen
= strlen(msg
);
1246 /* we will end the annotation by a newline anyway */
1247 if (msglen
&& msg
[msglen
- 1] == '\n')
1251 const char *ref
= t
->ref
;
1252 if (!ref
|| !strcmp(ref
, GIT_NOTES_DEFAULT_REF
)) {
1253 strbuf_addstr(sb
, "\nNotes:\n");
1255 if (starts_with(ref
, "refs/"))
1257 if (starts_with(ref
, "notes/"))
1259 strbuf_addf(sb
, "\nNotes (%s):\n", ref
);
1263 for (msg_p
= msg
; msg_p
< msg
+ msglen
; msg_p
+= linelen
+ 1) {
1264 linelen
= strchrnul(msg_p
, '\n') - msg_p
;
1267 strbuf_addstr(sb
, " ");
1268 strbuf_add(sb
, msg_p
, linelen
);
1269 strbuf_addch(sb
, '\n');
1275 void format_display_notes(const unsigned char *object_sha1
,
1276 struct strbuf
*sb
, const char *output_encoding
, int raw
)
1279 assert(display_notes_trees
);
1280 for (i
= 0; display_notes_trees
[i
]; i
++)
1281 format_note(display_notes_trees
[i
], object_sha1
, sb
,
1282 output_encoding
, raw
);
1285 int copy_note(struct notes_tree
*t
,
1286 const unsigned char *from_obj
, const unsigned char *to_obj
,
1287 int force
, combine_notes_fn combine_notes
)
1289 const unsigned char *note
= get_note(t
, from_obj
);
1290 const unsigned char *existing_note
= get_note(t
, to_obj
);
1292 if (!force
&& existing_note
)
1296 return add_note(t
, to_obj
, note
, combine_notes
);
1297 else if (existing_note
)
1298 return add_note(t
, to_obj
, null_sha1
, combine_notes
);
1303 void expand_notes_ref(struct strbuf
*sb
)
1305 if (starts_with(sb
->buf
, "refs/notes/"))
1306 return; /* we're happy */
1307 else if (starts_with(sb
->buf
, "notes/"))
1308 strbuf_insert(sb
, 0, "refs/", 5);
1310 strbuf_insert(sb
, 0, "refs/notes/", 11);
1313 void expand_loose_notes_ref(struct strbuf
*sb
)
1315 unsigned char object
[20];
1317 if (get_sha1(sb
->buf
, object
)) {
1318 /* fallback to expand_notes_ref */
1319 expand_notes_ref(sb
);