From 327a89dca11ac78aee711e4ab440d2194b9914f8 Mon Sep 17 00:00:00 2001 From: Johan Herland Date: Tue, 9 Nov 2010 22:49:37 +0100 Subject: notes.c: Hexify SHA1 in die() message from init_notes() Signed-off-by: Johan Herland Signed-off-by: Junio C Hamano --- notes.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'notes.c') diff --git a/notes.c b/notes.c index 1978244398..bb03eb0364 100644 --- a/notes.c +++ b/notes.c @@ -940,7 +940,7 @@ void init_notes(struct notes_tree *t, const char *notes_ref, return; if (get_tree_entry(object_sha1, "", sha1, &mode)) die("Failed to read notes tree referenced by %s (%s)", - notes_ref, object_sha1); + notes_ref, sha1_to_hex(object_sha1)); hashclr(root_tree.key_sha1); hashcpy(root_tree.val_sha1, sha1); -- cgit v1.2.1 From 4a9cf1cefc0fd05e0eb46f862e398f1e4ac1c9a7 Mon Sep 17 00:00:00 2001 From: Johan Herland Date: Tue, 9 Nov 2010 22:49:39 +0100 Subject: notes.h: Make default_notes_ref() available in notes API Signed-off-by: Johan Herland Signed-off-by: Junio C Hamano --- notes.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'notes.c') diff --git a/notes.c b/notes.c index bb03eb0364..d71c0a30bf 100644 --- a/notes.c +++ b/notes.c @@ -898,7 +898,7 @@ static int notes_display_config(const char *k, const char *v, void *cb) return 0; } -static const char *default_notes_ref(void) +const char *default_notes_ref(void) { const char *notes_ref = NULL; if (!notes_ref) -- cgit v1.2.1 From a5cdebea55d53406e117d9a1fd4cc316ef036553 Mon Sep 17 00:00:00 2001 From: Johan Herland Date: Tue, 9 Nov 2010 22:49:40 +0100 Subject: notes.c: Reorder functions in preparation for next commit This patch introduces no functional change. It consists solely of reordering functions in notes.c to avoid use-before-declaration errors after applying the next commit in this series. Signed-off-by: Johan Herland Signed-off-by: Junio C Hamano --- notes.c | 146 ++++++++++++++++++++++++++++++++-------------------------------- 1 file changed, 73 insertions(+), 73 deletions(-) (limited to 'notes.c') diff --git a/notes.c b/notes.c index d71c0a30bf..bfb3ea5b53 100644 --- a/notes.c +++ b/notes.c @@ -149,6 +149,79 @@ static struct leaf_node *note_tree_find(struct notes_tree *t, return NULL; } +/* + * How to consolidate an int_node: + * If there are > 1 non-NULL entries, give up and return non-zero. + * Otherwise replace the int_node at the given index in the given parent node + * with the only entry (or a NULL entry if no entries) from the given tree, + * and return 0. + */ +static int note_tree_consolidate(struct int_node *tree, + struct int_node *parent, unsigned char index) +{ + unsigned int i; + void *p = NULL; + + assert(tree && parent); + assert(CLR_PTR_TYPE(parent->a[index]) == tree); + + for (i = 0; i < 16; i++) { + if (GET_PTR_TYPE(tree->a[i]) != PTR_TYPE_NULL) { + if (p) /* more than one entry */ + return -2; + p = tree->a[i]; + } + } + + /* replace tree with p in parent[index] */ + parent->a[index] = p; + free(tree); + return 0; +} + +/* + * To remove a leaf_node: + * Search to the tree location appropriate for the given leaf_node's key: + * - If location does not hold a matching entry, abort and do nothing. + * - Replace the matching leaf_node with a NULL entry (and free the leaf_node). + * - Consolidate int_nodes repeatedly, while walking up the tree towards root. + */ +static void note_tree_remove(struct notes_tree *t, struct int_node *tree, + unsigned char n, struct leaf_node *entry) +{ + struct leaf_node *l; + struct int_node *parent_stack[20]; + unsigned char i, j; + void **p = note_tree_search(t, &tree, &n, entry->key_sha1); + + assert(GET_PTR_TYPE(entry) == 0); /* no type bits set */ + if (GET_PTR_TYPE(*p) != PTR_TYPE_NOTE) + return; /* type mismatch, nothing to remove */ + l = (struct leaf_node *) CLR_PTR_TYPE(*p); + if (hashcmp(l->key_sha1, entry->key_sha1)) + return; /* key mismatch, nothing to remove */ + + /* we have found a matching entry */ + free(l); + *p = SET_PTR_TYPE(NULL, PTR_TYPE_NULL); + + /* consolidate this tree level, and parent levels, if possible */ + if (!n) + return; /* cannot consolidate top level */ + /* first, build stack of ancestors between root and current node */ + parent_stack[0] = t->root; + for (i = 0; i < n; i++) { + j = GET_NIBBLE(i, entry->key_sha1); + parent_stack[i + 1] = CLR_PTR_TYPE(parent_stack[i]->a[j]); + } + assert(i == n && parent_stack[i] == tree); + /* next, unwind stack until note_tree_consolidate() is done */ + while (i > 0 && + !note_tree_consolidate(parent_stack[i], parent_stack[i - 1], + GET_NIBBLE(i - 1, entry->key_sha1))) + i--; +} + /* * To insert a leaf_node: * Search to the tree location appropriate for the given leaf_node's key: @@ -229,79 +302,6 @@ static void note_tree_insert(struct notes_tree *t, struct int_node *tree, note_tree_insert(t, new_node, n + 1, entry, type, combine_notes); } -/* - * How to consolidate an int_node: - * If there are > 1 non-NULL entries, give up and return non-zero. - * Otherwise replace the int_node at the given index in the given parent node - * with the only entry (or a NULL entry if no entries) from the given tree, - * and return 0. - */ -static int note_tree_consolidate(struct int_node *tree, - struct int_node *parent, unsigned char index) -{ - unsigned int i; - void *p = NULL; - - assert(tree && parent); - assert(CLR_PTR_TYPE(parent->a[index]) == tree); - - for (i = 0; i < 16; i++) { - if (GET_PTR_TYPE(tree->a[i]) != PTR_TYPE_NULL) { - if (p) /* more than one entry */ - return -2; - p = tree->a[i]; - } - } - - /* replace tree with p in parent[index] */ - parent->a[index] = p; - free(tree); - return 0; -} - -/* - * To remove a leaf_node: - * Search to the tree location appropriate for the given leaf_node's key: - * - If location does not hold a matching entry, abort and do nothing. - * - Replace the matching leaf_node with a NULL entry (and free the leaf_node). - * - Consolidate int_nodes repeatedly, while walking up the tree towards root. - */ -static void note_tree_remove(struct notes_tree *t, struct int_node *tree, - unsigned char n, struct leaf_node *entry) -{ - struct leaf_node *l; - struct int_node *parent_stack[20]; - unsigned char i, j; - void **p = note_tree_search(t, &tree, &n, entry->key_sha1); - - assert(GET_PTR_TYPE(entry) == 0); /* no type bits set */ - if (GET_PTR_TYPE(*p) != PTR_TYPE_NOTE) - return; /* type mismatch, nothing to remove */ - l = (struct leaf_node *) CLR_PTR_TYPE(*p); - if (hashcmp(l->key_sha1, entry->key_sha1)) - return; /* key mismatch, nothing to remove */ - - /* we have found a matching entry */ - free(l); - *p = SET_PTR_TYPE(NULL, PTR_TYPE_NULL); - - /* consolidate this tree level, and parent levels, if possible */ - if (!n) - return; /* cannot consolidate top level */ - /* first, build stack of ancestors between root and current node */ - parent_stack[0] = t->root; - for (i = 0; i < n; i++) { - j = GET_NIBBLE(i, entry->key_sha1); - parent_stack[i + 1] = CLR_PTR_TYPE(parent_stack[i]->a[j]); - } - assert(i == n && parent_stack[i] == tree); - /* next, unwind stack until note_tree_consolidate() is done */ - while (i > 0 && - !note_tree_consolidate(parent_stack[i], parent_stack[i - 1], - GET_NIBBLE(i - 1, entry->key_sha1))) - i--; -} - /* Free the entire notes data contained in the given tree */ static void note_tree_free(struct int_node *tree) { -- cgit v1.2.1 From e2656c82fd836a3d410230c98f6a725368f15642 Mon Sep 17 00:00:00 2001 From: Johan Herland Date: Tue, 9 Nov 2010 22:49:41 +0100 Subject: notes.h/c: Allow combine_notes functions to remove notes Allow combine_notes functions to request that a note be removed, by setting the resulting note SHA1 to null_sha1 (0000000...). For consistency, also teach note_tree_insert() to skip insertion of an empty note (a note with entry->val_sha1 equal to null_sha1) when there is no note to combine it with. In general, an empty note (null_sha1) is treated identically to no note at all, but when adding an empty note where there already exists a non-empty note, we allow the combine_notes function to potentially record a new/changed note. Document this behaviour, and clearly specify how combine_notes functions are expected to handle null_sha1 in input. Before this patch, storing null_sha1s in the notes tree were silently allowed, causing an invalid notes tree (referring to blobs with null_sha1) to be produced by write_notes_tree(). Signed-off-by: Johan Herland Signed-off-by: Junio C Hamano --- notes.c | 12 +++++++++++- 1 file changed, 11 insertions(+), 1 deletion(-) (limited to 'notes.c') diff --git a/notes.c b/notes.c index bfb3ea5b53..0c13a36eb7 100644 --- a/notes.c +++ b/notes.c @@ -248,7 +248,10 @@ static void note_tree_insert(struct notes_tree *t, struct int_node *tree, switch (GET_PTR_TYPE(*p)) { case PTR_TYPE_NULL: assert(!*p); - *p = SET_PTR_TYPE(entry, type); + if (is_null_sha1(entry->val_sha1)) + free(entry); + else + *p = SET_PTR_TYPE(entry, type); return; case PTR_TYPE_NOTE: switch (type) { @@ -264,6 +267,9 @@ static void note_tree_insert(struct notes_tree *t, struct int_node *tree, sha1_to_hex(l->val_sha1), sha1_to_hex(entry->val_sha1), sha1_to_hex(l->key_sha1)); + + if (is_null_sha1(l->val_sha1)) + note_tree_remove(t, tree, n, entry); free(entry); return; } @@ -295,6 +301,10 @@ static void note_tree_insert(struct notes_tree *t, struct int_node *tree, /* non-matching leaf_node */ assert(GET_PTR_TYPE(*p) == PTR_TYPE_NOTE || GET_PTR_TYPE(*p) == PTR_TYPE_SUBTREE); + if (is_null_sha1(entry->val_sha1)) { /* skip insertion of empty note */ + free(entry); + return; + } new_node = (struct int_node *) xcalloc(sizeof(struct int_node), 1); note_tree_insert(t, new_node, n + 1, l, GET_PTR_TYPE(*p), combine_notes); -- cgit v1.2.1 From 180619a58572b17de0ebeb96989e0aa832765186 Mon Sep 17 00:00:00 2001 From: Johan Herland Date: Mon, 15 Nov 2010 00:52:26 +0100 Subject: notes.h/c: Propagate combine_notes_fn return value to add_note() and beyond The combine_notes_fn functions uses a non-zero return value to indicate failure. However, this return value was converted to a call to die() in note_tree_insert(). Instead, propagate this return value out to add_note(), and return it from there to enable the caller to handle errors appropriately. Existing add_note() callers are updated to die() upon failure, thus preserving the current behaviour. The only exceptions are copy_note() and notes_cache_put() where we are able to propagate the add_note() return value instead. This patch has been improved by the following contributions: - Jonathan Nieder: Future-proof by always checking add_note() return value - Jonathan Nieder: Improve clarity of final if-condition in note_tree_insert() Thanks-to: Jonathan Nieder Signed-off-by: Johan Herland Signed-off-by: Junio C Hamano --- notes.c | 55 ++++++++++++++++++++++++++++--------------------------- 1 file changed, 28 insertions(+), 27 deletions(-) (limited to 'notes.c') diff --git a/notes.c b/notes.c index 0c13a36eb7..1674391d38 100644 --- a/notes.c +++ b/notes.c @@ -235,13 +235,14 @@ static void note_tree_remove(struct notes_tree *t, struct int_node *tree, * - Else, create a new int_node, holding both the node-at-location and the * node-to-be-inserted, and store the new int_node into the location. */ -static void note_tree_insert(struct notes_tree *t, struct int_node *tree, +static int note_tree_insert(struct notes_tree *t, struct int_node *tree, unsigned char n, struct leaf_node *entry, unsigned char type, combine_notes_fn combine_notes) { struct int_node *new_node; struct leaf_node *l; void **p = note_tree_search(t, &tree, &n, entry->key_sha1); + int ret = 0; assert(GET_PTR_TYPE(entry) == 0); /* no type bits set */ l = (struct leaf_node *) CLR_PTR_TYPE(*p); @@ -252,26 +253,21 @@ static void note_tree_insert(struct notes_tree *t, struct int_node *tree, free(entry); else *p = SET_PTR_TYPE(entry, type); - return; + return 0; case PTR_TYPE_NOTE: switch (type) { case PTR_TYPE_NOTE: if (!hashcmp(l->key_sha1, entry->key_sha1)) { /* skip concatenation if l == entry */ if (!hashcmp(l->val_sha1, entry->val_sha1)) - return; + return 0; - if (combine_notes(l->val_sha1, entry->val_sha1)) - die("failed to combine notes %s and %s" - " for object %s", - sha1_to_hex(l->val_sha1), - sha1_to_hex(entry->val_sha1), - sha1_to_hex(l->key_sha1)); - - if (is_null_sha1(l->val_sha1)) + ret = combine_notes(l->val_sha1, + entry->val_sha1); + if (!ret && is_null_sha1(l->val_sha1)) note_tree_remove(t, tree, n, entry); free(entry); - return; + return ret; } break; case PTR_TYPE_SUBTREE: @@ -280,7 +276,7 @@ static void note_tree_insert(struct notes_tree *t, struct int_node *tree, /* unpack 'entry' */ load_subtree(t, entry, tree, n); free(entry); - return; + return 0; } break; } @@ -291,9 +287,8 @@ static void note_tree_insert(struct notes_tree *t, struct int_node *tree, *p = NULL; load_subtree(t, l, tree, n); free(l); - note_tree_insert(t, tree, n, entry, type, - combine_notes); - return; + return note_tree_insert(t, tree, n, entry, type, + combine_notes); } break; } @@ -303,13 +298,15 @@ static void note_tree_insert(struct notes_tree *t, struct int_node *tree, GET_PTR_TYPE(*p) == PTR_TYPE_SUBTREE); if (is_null_sha1(entry->val_sha1)) { /* skip insertion of empty note */ free(entry); - return; + return 0; } new_node = (struct int_node *) xcalloc(sizeof(struct int_node), 1); - note_tree_insert(t, new_node, n + 1, l, GET_PTR_TYPE(*p), - combine_notes); + ret = note_tree_insert(t, new_node, n + 1, l, GET_PTR_TYPE(*p), + combine_notes); + if (ret) + return ret; *p = SET_PTR_TYPE(new_node, PTR_TYPE_INTERNAL); - note_tree_insert(t, new_node, n + 1, entry, type, combine_notes); + return note_tree_insert(t, new_node, n + 1, entry, type, combine_notes); } /* Free the entire notes data contained in the given tree */ @@ -452,8 +449,12 @@ static void load_subtree(struct notes_tree *t, struct leaf_node *subtree, l->key_sha1[19] = (unsigned char) len; type = PTR_TYPE_SUBTREE; } - note_tree_insert(t, node, n, l, type, - combine_notes_concatenate); + if (note_tree_insert(t, node, n, l, type, + combine_notes_concatenate)) + die("Failed to load %s %s into notes tree " + "from %s", + type == PTR_TYPE_NOTE ? "note" : "subtree", + sha1_to_hex(l->key_sha1), t->ref); } continue; @@ -1014,7 +1015,7 @@ void init_display_notes(struct display_notes_opt *opt) string_list_clear(&display_notes_refs, 0); } -void add_note(struct notes_tree *t, const unsigned char *object_sha1, +int add_note(struct notes_tree *t, const unsigned char *object_sha1, const unsigned char *note_sha1, combine_notes_fn combine_notes) { struct leaf_node *l; @@ -1028,7 +1029,7 @@ void add_note(struct notes_tree *t, const unsigned char *object_sha1, l = (struct leaf_node *) xmalloc(sizeof(struct leaf_node)); hashcpy(l->key_sha1, object_sha1); hashcpy(l->val_sha1, note_sha1); - note_tree_insert(t, t->root, 0, l, PTR_TYPE_NOTE, combine_notes); + return note_tree_insert(t, t->root, 0, l, PTR_TYPE_NOTE, combine_notes); } void remove_note(struct notes_tree *t, const unsigned char *object_sha1) @@ -1204,7 +1205,7 @@ void format_display_notes(const unsigned char *object_sha1, int copy_note(struct notes_tree *t, const unsigned char *from_obj, const unsigned char *to_obj, - int force, combine_notes_fn combine_fn) + int force, combine_notes_fn combine_notes) { const unsigned char *note = get_note(t, from_obj); const unsigned char *existing_note = get_note(t, to_obj); @@ -1213,9 +1214,9 @@ int copy_note(struct notes_tree *t, return 1; if (note) - add_note(t, to_obj, note, combine_fn); + return add_note(t, to_obj, note, combine_notes); else if (existing_note) - add_note(t, to_obj, null_sha1, combine_fn); + return add_note(t, to_obj, null_sha1, combine_notes); return 0; } -- cgit v1.2.1 From d4990c4b2f5f7066853fea4df775b3f506c79431 Mon Sep 17 00:00:00 2001 From: Johan Herland Date: Tue, 9 Nov 2010 22:49:44 +0100 Subject: notes.c: Use two newlines (instead of one) when concatenating notes When using combine_notes_concatenate() to concatenate notes, it currently ensures exactly one newline character between the given notes. However, when using builtin/notes.c:create_note() to concatenate notes (e.g. by 'git notes append'), it adds a newline character to the trailing newline of the preceding notes object, thus resulting in _two_ newlines (aka. a blank line) separating contents of the two notes. This patch brings combine_notes_concatenate() into consistency with builtin/notes.c:create_note(), by ensuring exactly _two_ newline characters between concatenated notes. The patch also changes a few notes-related selftests accordingly. Signed-off-by: Johan Herland Signed-off-by: Junio C Hamano --- notes.c | 7 ++++--- 1 file changed, 4 insertions(+), 3 deletions(-) (limited to 'notes.c') diff --git a/notes.c b/notes.c index 1674391d38..09a93abca1 100644 --- a/notes.c +++ b/notes.c @@ -812,16 +812,17 @@ int combine_notes_concatenate(unsigned char *cur_sha1, return 0; } - /* we will separate the notes by a newline anyway */ + /* we will separate the notes by two newlines anyway */ if (cur_msg[cur_len - 1] == '\n') cur_len--; /* concatenate cur_msg and new_msg into buf */ - buf_len = cur_len + 1 + new_len; + buf_len = cur_len + 2 + new_len; buf = (char *) xmalloc(buf_len); memcpy(buf, cur_msg, cur_len); buf[cur_len] = '\n'; - memcpy(buf + cur_len + 1, new_msg, new_len); + buf[cur_len + 1] = '\n'; + memcpy(buf + cur_len + 2, new_msg, new_len); free(cur_msg); free(new_msg); -- cgit v1.2.1 From a6a09095a08339afc8468d053ff978ed4662a1d5 Mon Sep 17 00:00:00 2001 From: Johan Herland Date: Mon, 15 Nov 2010 00:57:17 +0100 Subject: git notes merge: Add another auto-resolving strategy: "cat_sort_uniq" This new strategy is similar to "concatenate", but in addition to concatenating the two note candidates, this strategy sorts the resulting lines, and removes duplicate lines from the result. This is equivalent to applying the "cat | sort | uniq" shell pipeline to the two note candidates. This strategy is useful if the notes follow a line-based format where one wants to avoid duplicate lines in the merge result. Note that if either of the note candidates contain duplicate lines _prior_ to the merge, these will also be removed by this merge strategy. The patch also contains tests and documentation for the new strategy. Signed-off-by: Johan Herland Signed-off-by: Junio C Hamano --- notes.c | 76 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 76 insertions(+) (limited to 'notes.c') diff --git a/notes.c b/notes.c index 09a93abca1..96cde42134 100644 --- a/notes.c +++ b/notes.c @@ -845,6 +845,82 @@ int combine_notes_ignore(unsigned char *cur_sha1, return 0; } +static int string_list_add_note_lines(struct string_list *sort_uniq_list, + const unsigned char *sha1) +{ + char *data; + unsigned long len; + enum object_type t; + struct strbuf buf = STRBUF_INIT; + struct strbuf **lines = NULL; + int i, list_index; + + if (is_null_sha1(sha1)) + return 0; + + /* read_sha1_file NUL-terminates */ + data = read_sha1_file(sha1, &t, &len); + if (t != OBJ_BLOB || !data || !len) { + free(data); + return t != OBJ_BLOB || !data; + } + + strbuf_attach(&buf, data, len, len + 1); + lines = strbuf_split(&buf, '\n'); + + for (i = 0; lines[i]; i++) { + if (lines[i]->buf[lines[i]->len - 1] == '\n') + strbuf_setlen(lines[i], lines[i]->len - 1); + if (!lines[i]->len) + continue; /* skip empty lines */ + list_index = string_list_find_insert_index(sort_uniq_list, + lines[i]->buf, 0); + if (list_index < 0) + continue; /* skip duplicate lines */ + string_list_insert_at_index(sort_uniq_list, list_index, + lines[i]->buf); + } + + strbuf_list_free(lines); + strbuf_release(&buf); + return 0; +} + +static int string_list_join_lines_helper(struct string_list_item *item, + void *cb_data) +{ + struct strbuf *buf = cb_data; + strbuf_addstr(buf, item->string); + strbuf_addch(buf, '\n'); + return 0; +} + +int combine_notes_cat_sort_uniq(unsigned char *cur_sha1, + const unsigned char *new_sha1) +{ + struct string_list sort_uniq_list = { NULL, 0, 0, 1 }; + struct strbuf buf = STRBUF_INIT; + int ret = 1; + + /* read both note blob objects into unique_lines */ + if (string_list_add_note_lines(&sort_uniq_list, cur_sha1)) + goto out; + if (string_list_add_note_lines(&sort_uniq_list, new_sha1)) + goto out; + + /* create a new blob object from sort_uniq_list */ + if (for_each_string_list(&sort_uniq_list, + string_list_join_lines_helper, &buf)) + goto out; + + ret = write_sha1_file(buf.buf, buf.len, blob_type, cur_sha1); + +out: + strbuf_release(&buf); + string_list_clear(&sort_uniq_list, 0); + return ret; +} + static int string_list_add_one_ref(const char *path, const unsigned char *sha1, int flag, void *cb) { -- cgit v1.2.1