1#include"cache.h" 2#include"notes.h" 3#include"utf8.h" 4#include"strbuf.h" 5#include"tree-walk.h" 6 7/* 8 * Use a non-balancing simple 16-tree structure with struct int_node as 9 * internal nodes, and struct leaf_node as leaf nodes. Each int_node has a 10 * 16-array of pointers to its children. 11 * The bottom 2 bits of each pointer is used to identify the pointer type 12 * - ptr & 3 == 0 - NULL pointer, assert(ptr == NULL) 13 * - ptr & 3 == 1 - pointer to next internal node - cast to struct int_node * 14 * - ptr & 3 == 2 - pointer to note entry - cast to struct leaf_node * 15 * - ptr & 3 == 3 - pointer to subtree entry - cast to struct leaf_node * 16 * 17 * The root node is a statically allocated struct int_node. 18 */ 19struct int_node { 20void*a[16]; 21}; 22 23/* 24 * Leaf nodes come in two variants, note entries and subtree entries, 25 * distinguished by the LSb of the leaf node pointer (see above). 26 * As a note entry, the key is the SHA1 of the referenced object, and the 27 * value is the SHA1 of the note object. 28 * As a subtree entry, the key is the prefix SHA1 (w/trailing NULs) of the 29 * referenced object, using the last byte of the key to store the length of 30 * the prefix. The value is the SHA1 of the tree object containing the notes 31 * subtree. 32 */ 33struct leaf_node { 34unsigned char key_sha1[20]; 35unsigned char val_sha1[20]; 36}; 37 38#define PTR_TYPE_NULL 0 39#define PTR_TYPE_INTERNAL 1 40#define PTR_TYPE_NOTE 2 41#define PTR_TYPE_SUBTREE 3 42 43#define GET_PTR_TYPE(ptr) ((uintptr_t) (ptr) & 3) 44#define CLR_PTR_TYPE(ptr) ((void *) ((uintptr_t) (ptr) & ~3)) 45#define SET_PTR_TYPE(ptr, type) ((void *) ((uintptr_t) (ptr) | (type))) 46 47#define GET_NIBBLE(n, sha1) (((sha1[(n) >> 1]) >> ((~(n) & 0x01) << 2)) & 0x0f) 48 49#define SUBTREE_SHA1_PREFIXCMP(key_sha1, subtree_sha1) \ 50 (memcmp(key_sha1, subtree_sha1, subtree_sha1[19])) 51 52static struct int_node root_node; 53 54static int initialized; 55 56static voidload_subtree(struct leaf_node *subtree,struct int_node *node, 57unsigned int n); 58 59/* 60 * Search the tree until the appropriate location for the given key is found: 61 * 1. Start at the root node, with n = 0 62 * 2. If a[0] at the current level is a matching subtree entry, unpack that 63 * subtree entry and remove it; restart search at the current level. 64 * 3. Use the nth nibble of the key as an index into a: 65 * - If a[n] is an int_node, recurse from #2 into that node and increment n 66 * - If a matching subtree entry, unpack that subtree entry (and remove it); 67 * restart search at the current level. 68 * - Otherwise, we have found one of the following: 69 * - a subtree entry which does not match the key 70 * - a note entry which may or may not match the key 71 * - an unused leaf node (NULL) 72 * In any case, set *tree and *n, and return pointer to the tree location. 73 */ 74static void**note_tree_search(struct int_node **tree, 75unsigned char*n,const unsigned char*key_sha1) 76{ 77struct leaf_node *l; 78unsigned char i; 79void*p = (*tree)->a[0]; 80 81if(GET_PTR_TYPE(p) == PTR_TYPE_SUBTREE) { 82 l = (struct leaf_node *)CLR_PTR_TYPE(p); 83if(!SUBTREE_SHA1_PREFIXCMP(key_sha1, l->key_sha1)) { 84/* unpack tree and resume search */ 85(*tree)->a[0] = NULL; 86load_subtree(l, *tree, *n); 87free(l); 88returnnote_tree_search(tree, n, key_sha1); 89} 90} 91 92 i =GET_NIBBLE(*n, key_sha1); 93 p = (*tree)->a[i]; 94switch(GET_PTR_TYPE(p)) { 95case PTR_TYPE_INTERNAL: 96*tree =CLR_PTR_TYPE(p); 97(*n)++; 98returnnote_tree_search(tree, n, key_sha1); 99case PTR_TYPE_SUBTREE: 100 l = (struct leaf_node *)CLR_PTR_TYPE(p); 101if(!SUBTREE_SHA1_PREFIXCMP(key_sha1, l->key_sha1)) { 102/* unpack tree and resume search */ 103(*tree)->a[i] = NULL; 104load_subtree(l, *tree, *n); 105free(l); 106returnnote_tree_search(tree, n, key_sha1); 107} 108/* fall through */ 109default: 110return&((*tree)->a[i]); 111} 112} 113 114/* 115 * To find a leaf_node: 116 * Search to the tree location appropriate for the given key: 117 * If a note entry with matching key, return the note entry, else return NULL. 118 */ 119static struct leaf_node *note_tree_find(struct int_node *tree,unsigned char n, 120const unsigned char*key_sha1) 121{ 122void**p =note_tree_search(&tree, &n, key_sha1); 123if(GET_PTR_TYPE(*p) == PTR_TYPE_NOTE) { 124struct leaf_node *l = (struct leaf_node *)CLR_PTR_TYPE(*p); 125if(!hashcmp(key_sha1, l->key_sha1)) 126return l; 127} 128return NULL; 129} 130 131/* Create a new blob object by concatenating the two given blob objects */ 132static intconcatenate_notes(unsigned char*cur_sha1, 133const unsigned char*new_sha1) 134{ 135char*cur_msg, *new_msg, *buf; 136unsigned long cur_len, new_len, buf_len; 137enum object_type cur_type, new_type; 138int ret; 139 140/* read in both note blob objects */ 141 new_msg =read_sha1_file(new_sha1, &new_type, &new_len); 142if(!new_msg || !new_len || new_type != OBJ_BLOB) { 143free(new_msg); 144return0; 145} 146 cur_msg =read_sha1_file(cur_sha1, &cur_type, &cur_len); 147if(!cur_msg || !cur_len || cur_type != OBJ_BLOB) { 148free(cur_msg); 149free(new_msg); 150hashcpy(cur_sha1, new_sha1); 151return0; 152} 153 154/* we will separate the notes by a newline anyway */ 155if(cur_msg[cur_len -1] =='\n') 156 cur_len--; 157 158/* concatenate cur_msg and new_msg into buf */ 159 buf_len = cur_len +1+ new_len; 160 buf = (char*)xmalloc(buf_len); 161memcpy(buf, cur_msg, cur_len); 162 buf[cur_len] ='\n'; 163memcpy(buf + cur_len +1, new_msg, new_len); 164 165free(cur_msg); 166free(new_msg); 167 168/* create a new blob object from buf */ 169 ret =write_sha1_file(buf, buf_len,"blob", cur_sha1); 170free(buf); 171return ret; 172} 173 174/* 175 * To insert a leaf_node: 176 * Search to the tree location appropriate for the given leaf_node's key: 177 * - If location is unused (NULL), store the tweaked pointer directly there 178 * - If location holds a note entry that matches the note-to-be-inserted, then 179 * concatenate the two notes. 180 * - If location holds a note entry that matches the subtree-to-be-inserted, 181 * then unpack the subtree-to-be-inserted into the location. 182 * - If location holds a matching subtree entry, unpack the subtree at that 183 * location, and restart the insert operation from that level. 184 * - Else, create a new int_node, holding both the node-at-location and the 185 * node-to-be-inserted, and store the new int_node into the location. 186 */ 187static voidnote_tree_insert(struct int_node *tree,unsigned char n, 188struct leaf_node *entry,unsigned char type) 189{ 190struct int_node *new_node; 191struct leaf_node *l; 192void**p =note_tree_search(&tree, &n, entry->key_sha1); 193 194assert(GET_PTR_TYPE(entry) ==0);/* no type bits set */ 195 l = (struct leaf_node *)CLR_PTR_TYPE(*p); 196switch(GET_PTR_TYPE(*p)) { 197case PTR_TYPE_NULL: 198assert(!*p); 199*p =SET_PTR_TYPE(entry, type); 200return; 201case PTR_TYPE_NOTE: 202switch(type) { 203case PTR_TYPE_NOTE: 204if(!hashcmp(l->key_sha1, entry->key_sha1)) { 205/* skip concatenation if l == entry */ 206if(!hashcmp(l->val_sha1, entry->val_sha1)) 207return; 208 209if(concatenate_notes(l->val_sha1, 210 entry->val_sha1)) 211die("failed to concatenate note%s" 212"into note%sfor object%s", 213sha1_to_hex(entry->val_sha1), 214sha1_to_hex(l->val_sha1), 215sha1_to_hex(l->key_sha1)); 216free(entry); 217return; 218} 219break; 220case PTR_TYPE_SUBTREE: 221if(!SUBTREE_SHA1_PREFIXCMP(l->key_sha1, 222 entry->key_sha1)) { 223/* unpack 'entry' */ 224load_subtree(entry, tree, n); 225free(entry); 226return; 227} 228break; 229} 230break; 231case PTR_TYPE_SUBTREE: 232if(!SUBTREE_SHA1_PREFIXCMP(entry->key_sha1, l->key_sha1)) { 233/* unpack 'l' and restart insert */ 234*p = NULL; 235load_subtree(l, tree, n); 236free(l); 237note_tree_insert(tree, n, entry, type); 238return; 239} 240break; 241} 242 243/* non-matching leaf_node */ 244assert(GET_PTR_TYPE(*p) == PTR_TYPE_NOTE || 245GET_PTR_TYPE(*p) == PTR_TYPE_SUBTREE); 246 new_node = (struct int_node *)xcalloc(sizeof(struct int_node),1); 247note_tree_insert(new_node, n +1, l,GET_PTR_TYPE(*p)); 248*p =SET_PTR_TYPE(new_node, PTR_TYPE_INTERNAL); 249note_tree_insert(new_node, n +1, entry, type); 250} 251 252/* 253 * How to consolidate an int_node: 254 * If there are > 1 non-NULL entries, give up and return non-zero. 255 * Otherwise replace the int_node at the given index in the given parent node 256 * with the only entry (or a NULL entry if no entries) from the given tree, 257 * and return 0. 258 */ 259static intnote_tree_consolidate(struct int_node *tree, 260struct int_node *parent,unsigned char index) 261{ 262unsigned int i; 263void*p = NULL; 264 265assert(tree && parent); 266assert(CLR_PTR_TYPE(parent->a[index]) == tree); 267 268for(i =0; i <16; i++) { 269if(GET_PTR_TYPE(tree->a[i]) != PTR_TYPE_NULL) { 270if(p)/* more than one entry */ 271return-2; 272 p = tree->a[i]; 273} 274} 275 276/* replace tree with p in parent[index] */ 277 parent->a[index] = p; 278free(tree); 279return0; 280} 281 282/* 283 * To remove a leaf_node: 284 * Search to the tree location appropriate for the given leaf_node's key: 285 * - If location does not hold a matching entry, abort and do nothing. 286 * - Replace the matching leaf_node with a NULL entry (and free the leaf_node). 287 * - Consolidate int_nodes repeatedly, while walking up the tree towards root. 288 */ 289static voidnote_tree_remove(struct int_node *tree,unsigned char n, 290struct leaf_node *entry) 291{ 292struct leaf_node *l; 293struct int_node *parent_stack[20]; 294unsigned char i, j; 295void**p =note_tree_search(&tree, &n, entry->key_sha1); 296 297assert(GET_PTR_TYPE(entry) ==0);/* no type bits set */ 298if(GET_PTR_TYPE(*p) != PTR_TYPE_NOTE) 299return;/* type mismatch, nothing to remove */ 300 l = (struct leaf_node *)CLR_PTR_TYPE(*p); 301if(hashcmp(l->key_sha1, entry->key_sha1)) 302return;/* key mismatch, nothing to remove */ 303 304/* we have found a matching entry */ 305free(l); 306*p =SET_PTR_TYPE(NULL, PTR_TYPE_NULL); 307 308/* consolidate this tree level, and parent levels, if possible */ 309if(!n) 310return;/* cannot consolidate top level */ 311/* first, build stack of ancestors between root and current node */ 312 parent_stack[0] = &root_node; 313for(i =0; i < n; i++) { 314 j =GET_NIBBLE(i, entry->key_sha1); 315 parent_stack[i +1] =CLR_PTR_TYPE(parent_stack[i]->a[j]); 316} 317assert(i == n && parent_stack[i] == tree); 318/* next, unwind stack until note_tree_consolidate() is done */ 319while(i >0&& 320!note_tree_consolidate(parent_stack[i], parent_stack[i -1], 321GET_NIBBLE(i -1, entry->key_sha1))) 322 i--; 323} 324 325/* Free the entire notes data contained in the given tree */ 326static voidnote_tree_free(struct int_node *tree) 327{ 328unsigned int i; 329for(i =0; i <16; i++) { 330void*p = tree->a[i]; 331switch(GET_PTR_TYPE(p)) { 332case PTR_TYPE_INTERNAL: 333note_tree_free(CLR_PTR_TYPE(p)); 334/* fall through */ 335case PTR_TYPE_NOTE: 336case PTR_TYPE_SUBTREE: 337free(CLR_PTR_TYPE(p)); 338} 339} 340} 341 342/* 343 * Convert a partial SHA1 hex string to the corresponding partial SHA1 value. 344 * - hex - Partial SHA1 segment in ASCII hex format 345 * - hex_len - Length of above segment. Must be multiple of 2 between 0 and 40 346 * - sha1 - Partial SHA1 value is written here 347 * - sha1_len - Max #bytes to store in sha1, Must be >= hex_len / 2, and < 20 348 * Returns -1 on error (invalid arguments or invalid SHA1 (not in hex format)). 349 * Otherwise, returns number of bytes written to sha1 (i.e. hex_len / 2). 350 * Pads sha1 with NULs up to sha1_len (not included in returned length). 351 */ 352static intget_sha1_hex_segment(const char*hex,unsigned int hex_len, 353unsigned char*sha1,unsigned int sha1_len) 354{ 355unsigned int i, len = hex_len >>1; 356if(hex_len %2!=0|| len > sha1_len) 357return-1; 358for(i =0; i < len; i++) { 359unsigned int val = (hexval(hex[0]) <<4) |hexval(hex[1]); 360if(val & ~0xff) 361return-1; 362*sha1++ = val; 363 hex +=2; 364} 365for(; i < sha1_len; i++) 366*sha1++ =0; 367return len; 368} 369 370static voidload_subtree(struct leaf_node *subtree,struct int_node *node, 371unsigned int n) 372{ 373unsigned char object_sha1[20]; 374unsigned int prefix_len; 375void*buf; 376struct tree_desc desc; 377struct name_entry entry; 378 379 buf =fill_tree_descriptor(&desc, subtree->val_sha1); 380if(!buf) 381die("Could not read%sfor notes-index", 382sha1_to_hex(subtree->val_sha1)); 383 384 prefix_len = subtree->key_sha1[19]; 385assert(prefix_len *2>= n); 386memcpy(object_sha1, subtree->key_sha1, prefix_len); 387while(tree_entry(&desc, &entry)) { 388int len =get_sha1_hex_segment(entry.path,strlen(entry.path), 389 object_sha1 + prefix_len,20- prefix_len); 390if(len <0) 391continue;/* entry.path is not a SHA1 sum. Skip */ 392 len += prefix_len; 393 394/* 395 * If object SHA1 is complete (len == 20), assume note object 396 * If object SHA1 is incomplete (len < 20), assume note subtree 397 */ 398if(len <=20) { 399unsigned char type = PTR_TYPE_NOTE; 400struct leaf_node *l = (struct leaf_node *) 401xcalloc(sizeof(struct leaf_node),1); 402hashcpy(l->key_sha1, object_sha1); 403hashcpy(l->val_sha1, entry.sha1); 404if(len <20) { 405if(!S_ISDIR(entry.mode)) 406continue;/* entry cannot be subtree */ 407 l->key_sha1[19] = (unsigned char) len; 408 type = PTR_TYPE_SUBTREE; 409} 410note_tree_insert(node, n, l, type); 411} 412} 413free(buf); 414} 415 416voidinit_notes(const char*notes_ref,int flags) 417{ 418unsigned char sha1[20], object_sha1[20]; 419unsigned mode; 420struct leaf_node root_tree; 421 422assert(!initialized); 423 initialized =1; 424 425if(!notes_ref) 426 notes_ref =getenv(GIT_NOTES_REF_ENVIRONMENT); 427if(!notes_ref) 428 notes_ref = notes_ref_name;/* value of core.notesRef config */ 429if(!notes_ref) 430 notes_ref = GIT_NOTES_DEFAULT_REF; 431 432if(flags & NOTES_INIT_EMPTY || !notes_ref || 433read_ref(notes_ref, object_sha1)) 434return; 435if(get_tree_entry(object_sha1,"", sha1, &mode)) 436die("Failed to read notes tree referenced by%s(%s)", 437 notes_ref, object_sha1); 438 439hashclr(root_tree.key_sha1); 440hashcpy(root_tree.val_sha1, sha1); 441load_subtree(&root_tree, &root_node,0); 442} 443 444voidadd_note(const unsigned char*object_sha1,const unsigned char*note_sha1) 445{ 446struct leaf_node *l; 447 448assert(initialized); 449 l = (struct leaf_node *)xmalloc(sizeof(struct leaf_node)); 450hashcpy(l->key_sha1, object_sha1); 451hashcpy(l->val_sha1, note_sha1); 452note_tree_insert(&root_node,0, l, PTR_TYPE_NOTE); 453} 454 455voidremove_note(const unsigned char*object_sha1) 456{ 457struct leaf_node l; 458 459assert(initialized); 460hashcpy(l.key_sha1, object_sha1); 461hashclr(l.val_sha1); 462returnnote_tree_remove(&root_node,0, &l); 463} 464 465const unsigned char*get_note(const unsigned char*object_sha1) 466{ 467struct leaf_node *found; 468 469assert(initialized); 470 found =note_tree_find(&root_node,0, object_sha1); 471return found ? found->val_sha1 : NULL; 472} 473 474voidfree_notes(void) 475{ 476note_tree_free(&root_node); 477memset(&root_node,0,sizeof(struct int_node)); 478 initialized =0; 479} 480 481voidformat_note(const unsigned char*object_sha1,struct strbuf *sb, 482const char*output_encoding,int flags) 483{ 484static const char utf8[] ="utf-8"; 485const unsigned char*sha1; 486char*msg, *msg_p; 487unsigned long linelen, msglen; 488enum object_type type; 489 490if(!initialized) 491init_notes(NULL,0); 492 493 sha1 =get_note(object_sha1); 494if(!sha1) 495return; 496 497if(!(msg =read_sha1_file(sha1, &type, &msglen)) || !msglen || 498 type != OBJ_BLOB) { 499free(msg); 500return; 501} 502 503if(output_encoding && *output_encoding && 504strcmp(utf8, output_encoding)) { 505char*reencoded =reencode_string(msg, output_encoding, utf8); 506if(reencoded) { 507free(msg); 508 msg = reencoded; 509 msglen =strlen(msg); 510} 511} 512 513/* we will end the annotation by a newline anyway */ 514if(msglen && msg[msglen -1] =='\n') 515 msglen--; 516 517if(flags & NOTES_SHOW_HEADER) 518strbuf_addstr(sb,"\nNotes:\n"); 519 520for(msg_p = msg; msg_p < msg + msglen; msg_p += linelen +1) { 521 linelen =strchrnul(msg_p,'\n') - msg_p; 522 523if(flags & NOTES_INDENT) 524strbuf_addstr(sb," "); 525strbuf_add(sb, msg_p, linelen); 526strbuf_addch(sb,'\n'); 527} 528 529free(msg); 530}