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 416/* 417 * Determine optimal on-disk fanout for this part of the notes tree 418 * 419 * Given a (sub)tree and the level in the internal tree structure, determine 420 * whether or not the given existing fanout should be expanded for this 421 * (sub)tree. 422 * 423 * Values of the 'fanout' variable: 424 * - 0: No fanout (all notes are stored directly in the root notes tree) 425 * - 1: 2/38 fanout 426 * - 2: 2/2/36 fanout 427 * - 3: 2/2/2/34 fanout 428 * etc. 429 */ 430static unsigned chardetermine_fanout(struct int_node *tree,unsigned char n, 431unsigned char fanout) 432{ 433/* 434 * The following is a simple heuristic that works well in practice: 435 * For each even-numbered 16-tree level (remember that each on-disk 436 * fanout level corresponds to _two_ 16-tree levels), peek at all 16 437 * entries at that tree level. If all of them are either int_nodes or 438 * subtree entries, then there are likely plenty of notes below this 439 * level, so we return an incremented fanout. 440 */ 441unsigned int i; 442if((n %2) || (n >2* fanout)) 443return fanout; 444for(i =0; i <16; i++) { 445switch(GET_PTR_TYPE(tree->a[i])) { 446case PTR_TYPE_SUBTREE: 447case PTR_TYPE_INTERNAL: 448continue; 449default: 450return fanout; 451} 452} 453return fanout +1; 454} 455 456static voidconstruct_path_with_fanout(const unsigned char*sha1, 457unsigned char fanout,char*path) 458{ 459unsigned int i =0, j =0; 460const char*hex_sha1 =sha1_to_hex(sha1); 461assert(fanout <20); 462while(fanout) { 463 path[i++] = hex_sha1[j++]; 464 path[i++] = hex_sha1[j++]; 465 path[i++] ='/'; 466 fanout--; 467} 468strcpy(path + i, hex_sha1 + j); 469} 470 471static intfor_each_note_helper(struct int_node *tree,unsigned char n, 472unsigned char fanout,int flags, each_note_fn fn, 473void*cb_data) 474{ 475unsigned int i; 476void*p; 477int ret =0; 478struct leaf_node *l; 479static char path[40+19+1];/* hex SHA1 + 19 * '/' + NUL */ 480 481 fanout =determine_fanout(tree, n, fanout); 482for(i =0; i <16; i++) { 483redo: 484 p = tree->a[i]; 485switch(GET_PTR_TYPE(p)) { 486case PTR_TYPE_INTERNAL: 487/* recurse into int_node */ 488 ret =for_each_note_helper(CLR_PTR_TYPE(p), n +1, 489 fanout, flags, fn, cb_data); 490break; 491case PTR_TYPE_SUBTREE: 492 l = (struct leaf_node *)CLR_PTR_TYPE(p); 493/* 494 * Subtree entries in the note tree represent parts of 495 * the note tree that have not yet been explored. There 496 * is a direct relationship between subtree entries at 497 * level 'n' in the tree, and the 'fanout' variable: 498 * Subtree entries at level 'n <= 2 * fanout' should be 499 * preserved, since they correspond exactly to a fanout 500 * directory in the on-disk structure. However, subtree 501 * entries at level 'n > 2 * fanout' should NOT be 502 * preserved, but rather consolidated into the above 503 * notes tree level. We achieve this by unconditionally 504 * unpacking subtree entries that exist below the 505 * threshold level at 'n = 2 * fanout'. 506 */ 507if(n <=2* fanout && 508 flags & FOR_EACH_NOTE_YIELD_SUBTREES) { 509/* invoke callback with subtree */ 510unsigned int path_len = 511 l->key_sha1[19] *2+ fanout; 512assert(path_len <40+19); 513construct_path_with_fanout(l->key_sha1, fanout, 514 path); 515/* Create trailing slash, if needed */ 516if(path[path_len -1] !='/') 517 path[path_len++] ='/'; 518 path[path_len] ='\0'; 519 ret =fn(l->key_sha1, l->val_sha1, path, 520 cb_data); 521} 522if(n > fanout *2|| 523!(flags & FOR_EACH_NOTE_DONT_UNPACK_SUBTREES)) { 524/* unpack subtree and resume traversal */ 525 tree->a[i] = NULL; 526load_subtree(l, tree, n); 527free(l); 528goto redo; 529} 530break; 531case PTR_TYPE_NOTE: 532 l = (struct leaf_node *)CLR_PTR_TYPE(p); 533construct_path_with_fanout(l->key_sha1, fanout, path); 534 ret =fn(l->key_sha1, l->val_sha1, path, cb_data); 535break; 536} 537if(ret) 538return ret; 539} 540return0; 541} 542 543voidinit_notes(const char*notes_ref,int flags) 544{ 545unsigned char sha1[20], object_sha1[20]; 546unsigned mode; 547struct leaf_node root_tree; 548 549assert(!initialized); 550 initialized =1; 551 552if(!notes_ref) 553 notes_ref =getenv(GIT_NOTES_REF_ENVIRONMENT); 554if(!notes_ref) 555 notes_ref = notes_ref_name;/* value of core.notesRef config */ 556if(!notes_ref) 557 notes_ref = GIT_NOTES_DEFAULT_REF; 558 559if(flags & NOTES_INIT_EMPTY || !notes_ref || 560read_ref(notes_ref, object_sha1)) 561return; 562if(get_tree_entry(object_sha1,"", sha1, &mode)) 563die("Failed to read notes tree referenced by%s(%s)", 564 notes_ref, object_sha1); 565 566hashclr(root_tree.key_sha1); 567hashcpy(root_tree.val_sha1, sha1); 568load_subtree(&root_tree, &root_node,0); 569} 570 571voidadd_note(const unsigned char*object_sha1,const unsigned char*note_sha1) 572{ 573struct leaf_node *l; 574 575assert(initialized); 576 l = (struct leaf_node *)xmalloc(sizeof(struct leaf_node)); 577hashcpy(l->key_sha1, object_sha1); 578hashcpy(l->val_sha1, note_sha1); 579note_tree_insert(&root_node,0, l, PTR_TYPE_NOTE); 580} 581 582voidremove_note(const unsigned char*object_sha1) 583{ 584struct leaf_node l; 585 586assert(initialized); 587hashcpy(l.key_sha1, object_sha1); 588hashclr(l.val_sha1); 589returnnote_tree_remove(&root_node,0, &l); 590} 591 592const unsigned char*get_note(const unsigned char*object_sha1) 593{ 594struct leaf_node *found; 595 596assert(initialized); 597 found =note_tree_find(&root_node,0, object_sha1); 598return found ? found->val_sha1 : NULL; 599} 600 601intfor_each_note(int flags, each_note_fn fn,void*cb_data) 602{ 603assert(initialized); 604returnfor_each_note_helper(&root_node,0,0, flags, fn, cb_data); 605} 606 607voidfree_notes(void) 608{ 609note_tree_free(&root_node); 610memset(&root_node,0,sizeof(struct int_node)); 611 initialized =0; 612} 613 614voidformat_note(const unsigned char*object_sha1,struct strbuf *sb, 615const char*output_encoding,int flags) 616{ 617static const char utf8[] ="utf-8"; 618const unsigned char*sha1; 619char*msg, *msg_p; 620unsigned long linelen, msglen; 621enum object_type type; 622 623if(!initialized) 624init_notes(NULL,0); 625 626 sha1 =get_note(object_sha1); 627if(!sha1) 628return; 629 630if(!(msg =read_sha1_file(sha1, &type, &msglen)) || !msglen || 631 type != OBJ_BLOB) { 632free(msg); 633return; 634} 635 636if(output_encoding && *output_encoding && 637strcmp(utf8, output_encoding)) { 638char*reencoded =reencode_string(msg, output_encoding, utf8); 639if(reencoded) { 640free(msg); 641 msg = reencoded; 642 msglen =strlen(msg); 643} 644} 645 646/* we will end the annotation by a newline anyway */ 647if(msglen && msg[msglen -1] =='\n') 648 msglen--; 649 650if(flags & NOTES_SHOW_HEADER) 651strbuf_addstr(sb,"\nNotes:\n"); 652 653for(msg_p = msg; msg_p < msg + msglen; msg_p += linelen +1) { 654 linelen =strchrnul(msg_p,'\n') - msg_p; 655 656if(flags & NOTES_INDENT) 657strbuf_addstr(sb," "); 658strbuf_add(sb, msg_p, linelen); 659strbuf_addch(sb,'\n'); 660} 661 662free(msg); 663}