Merge branch 'tb/config-default'
[git] / notes.c
1 #include "cache.h"
2 #include "config.h"
3 #include "notes.h"
4 #include "object-store.h"
5 #include "blob.h"
6 #include "tree.h"
7 #include "utf8.h"
8 #include "strbuf.h"
9 #include "tree-walk.h"
10 #include "string-list.h"
11 #include "refs.h"
12
13 /*
14  * Use a non-balancing simple 16-tree structure with struct int_node as
15  * internal nodes, and struct leaf_node as leaf nodes. Each int_node has a
16  * 16-array of pointers to its children.
17  * The bottom 2 bits of each pointer is used to identify the pointer type
18  * - ptr & 3 == 0 - NULL pointer, assert(ptr == NULL)
19  * - ptr & 3 == 1 - pointer to next internal node - cast to struct int_node *
20  * - ptr & 3 == 2 - pointer to note entry - cast to struct leaf_node *
21  * - ptr & 3 == 3 - pointer to subtree entry - cast to struct leaf_node *
22  *
23  * The root node is a statically allocated struct int_node.
24  */
25 struct int_node {
26         void *a[16];
27 };
28
29 /*
30  * Leaf nodes come in two variants, note entries and subtree entries,
31  * distinguished by the LSb of the leaf node pointer (see above).
32  * As a note entry, the key is the SHA1 of the referenced object, and the
33  * value is the SHA1 of the note object.
34  * As a subtree entry, the key is the prefix SHA1 (w/trailing NULs) of the
35  * referenced object, using the last byte of the key to store the length of
36  * the prefix. The value is the SHA1 of the tree object containing the notes
37  * subtree.
38  */
39 struct leaf_node {
40         struct object_id key_oid;
41         struct object_id val_oid;
42 };
43
44 /*
45  * A notes tree may contain entries that are not notes, and that do not follow
46  * the naming conventions of notes. There are typically none/few of these, but
47  * we still need to keep track of them. Keep a simple linked list sorted alpha-
48  * betically on the non-note path. The list is populated when parsing tree
49  * objects in load_subtree(), and the non-notes are correctly written back into
50  * the tree objects produced by write_notes_tree().
51  */
52 struct non_note {
53         struct non_note *next; /* grounded (last->next == NULL) */
54         char *path;
55         unsigned int mode;
56         struct object_id oid;
57 };
58
59 #define PTR_TYPE_NULL     0
60 #define PTR_TYPE_INTERNAL 1
61 #define PTR_TYPE_NOTE     2
62 #define PTR_TYPE_SUBTREE  3
63
64 #define GET_PTR_TYPE(ptr)       ((uintptr_t) (ptr) & 3)
65 #define CLR_PTR_TYPE(ptr)       ((void *) ((uintptr_t) (ptr) & ~3))
66 #define SET_PTR_TYPE(ptr, type) ((void *) ((uintptr_t) (ptr) | (type)))
67
68 #define GET_NIBBLE(n, sha1) ((((sha1)[(n) >> 1]) >> ((~(n) & 0x01) << 2)) & 0x0f)
69
70 #define KEY_INDEX (GIT_SHA1_RAWSZ - 1)
71 #define FANOUT_PATH_SEPARATORS ((GIT_SHA1_HEXSZ / 2) - 1)
72 #define SUBTREE_SHA1_PREFIXCMP(key_sha1, subtree_sha1) \
73         (memcmp(key_sha1, subtree_sha1, subtree_sha1[KEY_INDEX]))
74
75 struct notes_tree default_notes_tree;
76
77 static struct string_list display_notes_refs = STRING_LIST_INIT_NODUP;
78 static struct notes_tree **display_notes_trees;
79
80 static void load_subtree(struct notes_tree *t, struct leaf_node *subtree,
81                 struct int_node *node, unsigned int n);
82
83 /*
84  * Search the tree until the appropriate location for the given key is found:
85  * 1. Start at the root node, with n = 0
86  * 2. If a[0] at the current level is a matching subtree entry, unpack that
87  *    subtree entry and remove it; restart search at the current level.
88  * 3. Use the nth nibble of the key as an index into a:
89  *    - If a[n] is an int_node, recurse from #2 into that node and increment n
90  *    - If a matching subtree entry, unpack that subtree entry (and remove it);
91  *      restart search at the current level.
92  *    - Otherwise, we have found one of the following:
93  *      - a subtree entry which does not match the key
94  *      - a note entry which may or may not match the key
95  *      - an unused leaf node (NULL)
96  *      In any case, set *tree and *n, and return pointer to the tree location.
97  */
98 static void **note_tree_search(struct notes_tree *t, struct int_node **tree,
99                 unsigned char *n, const unsigned char *key_sha1)
100 {
101         struct leaf_node *l;
102         unsigned char i;
103         void *p = (*tree)->a[0];
104
105         if (GET_PTR_TYPE(p) == PTR_TYPE_SUBTREE) {
106                 l = (struct leaf_node *) CLR_PTR_TYPE(p);
107                 if (!SUBTREE_SHA1_PREFIXCMP(key_sha1, l->key_oid.hash)) {
108                         /* unpack tree and resume search */
109                         (*tree)->a[0] = NULL;
110                         load_subtree(t, l, *tree, *n);
111                         free(l);
112                         return note_tree_search(t, tree, n, key_sha1);
113                 }
114         }
115
116         i = GET_NIBBLE(*n, key_sha1);
117         p = (*tree)->a[i];
118         switch (GET_PTR_TYPE(p)) {
119         case PTR_TYPE_INTERNAL:
120                 *tree = CLR_PTR_TYPE(p);
121                 (*n)++;
122                 return note_tree_search(t, tree, n, key_sha1);
123         case PTR_TYPE_SUBTREE:
124                 l = (struct leaf_node *) CLR_PTR_TYPE(p);
125                 if (!SUBTREE_SHA1_PREFIXCMP(key_sha1, l->key_oid.hash)) {
126                         /* unpack tree and resume search */
127                         (*tree)->a[i] = NULL;
128                         load_subtree(t, l, *tree, *n);
129                         free(l);
130                         return note_tree_search(t, tree, n, key_sha1);
131                 }
132                 /* fall through */
133         default:
134                 return &((*tree)->a[i]);
135         }
136 }
137
138 /*
139  * To find a leaf_node:
140  * Search to the tree location appropriate for the given key:
141  * If a note entry with matching key, return the note entry, else return NULL.
142  */
143 static struct leaf_node *note_tree_find(struct notes_tree *t,
144                 struct int_node *tree, unsigned char n,
145                 const unsigned char *key_sha1)
146 {
147         void **p = note_tree_search(t, &tree, &n, key_sha1);
148         if (GET_PTR_TYPE(*p) == PTR_TYPE_NOTE) {
149                 struct leaf_node *l = (struct leaf_node *) CLR_PTR_TYPE(*p);
150                 if (!hashcmp(key_sha1, l->key_oid.hash))
151                         return l;
152         }
153         return NULL;
154 }
155
156 /*
157  * How to consolidate an int_node:
158  * If there are > 1 non-NULL entries, give up and return non-zero.
159  * Otherwise replace the int_node at the given index in the given parent node
160  * with the only NOTE entry (or a NULL entry if no entries) from the given
161  * tree, and return 0.
162  */
163 static int note_tree_consolidate(struct int_node *tree,
164         struct int_node *parent, unsigned char index)
165 {
166         unsigned int i;
167         void *p = NULL;
168
169         assert(tree && parent);
170         assert(CLR_PTR_TYPE(parent->a[index]) == tree);
171
172         for (i = 0; i < 16; i++) {
173                 if (GET_PTR_TYPE(tree->a[i]) != PTR_TYPE_NULL) {
174                         if (p) /* more than one entry */
175                                 return -2;
176                         p = tree->a[i];
177                 }
178         }
179
180         if (p && (GET_PTR_TYPE(p) != PTR_TYPE_NOTE))
181                 return -2;
182         /* replace tree with p in parent[index] */
183         parent->a[index] = p;
184         free(tree);
185         return 0;
186 }
187
188 /*
189  * To remove a leaf_node:
190  * Search to the tree location appropriate for the given leaf_node's key:
191  * - If location does not hold a matching entry, abort and do nothing.
192  * - Copy the matching entry's value into the given entry.
193  * - Replace the matching leaf_node with a NULL entry (and free the leaf_node).
194  * - Consolidate int_nodes repeatedly, while walking up the tree towards root.
195  */
196 static void note_tree_remove(struct notes_tree *t,
197                 struct int_node *tree, unsigned char n,
198                 struct leaf_node *entry)
199 {
200         struct leaf_node *l;
201         struct int_node *parent_stack[GIT_SHA1_RAWSZ];
202         unsigned char i, j;
203         void **p = note_tree_search(t, &tree, &n, entry->key_oid.hash);
204
205         assert(GET_PTR_TYPE(entry) == 0); /* no type bits set */
206         if (GET_PTR_TYPE(*p) != PTR_TYPE_NOTE)
207                 return; /* type mismatch, nothing to remove */
208         l = (struct leaf_node *) CLR_PTR_TYPE(*p);
209         if (oidcmp(&l->key_oid, &entry->key_oid))
210                 return; /* key mismatch, nothing to remove */
211
212         /* we have found a matching entry */
213         oidcpy(&entry->val_oid, &l->val_oid);
214         free(l);
215         *p = SET_PTR_TYPE(NULL, PTR_TYPE_NULL);
216
217         /* consolidate this tree level, and parent levels, if possible */
218         if (!n)
219                 return; /* cannot consolidate top level */
220         /* first, build stack of ancestors between root and current node */
221         parent_stack[0] = t->root;
222         for (i = 0; i < n; i++) {
223                 j = GET_NIBBLE(i, entry->key_oid.hash);
224                 parent_stack[i + 1] = CLR_PTR_TYPE(parent_stack[i]->a[j]);
225         }
226         assert(i == n && parent_stack[i] == tree);
227         /* next, unwind stack until note_tree_consolidate() is done */
228         while (i > 0 &&
229                !note_tree_consolidate(parent_stack[i], parent_stack[i - 1],
230                                       GET_NIBBLE(i - 1, entry->key_oid.hash)))
231                 i--;
232 }
233
234 /*
235  * To insert a leaf_node:
236  * Search to the tree location appropriate for the given leaf_node's key:
237  * - If location is unused (NULL), store the tweaked pointer directly there
238  * - If location holds a note entry that matches the note-to-be-inserted, then
239  *   combine the two notes (by calling the given combine_notes function).
240  * - If location holds a note entry that matches the subtree-to-be-inserted,
241  *   then unpack the subtree-to-be-inserted into the location.
242  * - If location holds a matching subtree entry, unpack the subtree at that
243  *   location, and restart the insert operation from that level.
244  * - Else, create a new int_node, holding both the node-at-location and the
245  *   node-to-be-inserted, and store the new int_node into the location.
246  */
247 static int note_tree_insert(struct notes_tree *t, struct int_node *tree,
248                 unsigned char n, struct leaf_node *entry, unsigned char type,
249                 combine_notes_fn combine_notes)
250 {
251         struct int_node *new_node;
252         struct leaf_node *l;
253         void **p = note_tree_search(t, &tree, &n, entry->key_oid.hash);
254         int ret = 0;
255
256         assert(GET_PTR_TYPE(entry) == 0); /* no type bits set */
257         l = (struct leaf_node *) CLR_PTR_TYPE(*p);
258         switch (GET_PTR_TYPE(*p)) {
259         case PTR_TYPE_NULL:
260                 assert(!*p);
261                 if (is_null_oid(&entry->val_oid))
262                         free(entry);
263                 else
264                         *p = SET_PTR_TYPE(entry, type);
265                 return 0;
266         case PTR_TYPE_NOTE:
267                 switch (type) {
268                 case PTR_TYPE_NOTE:
269                         if (!oidcmp(&l->key_oid, &entry->key_oid)) {
270                                 /* skip concatenation if l == entry */
271                                 if (!oidcmp(&l->val_oid, &entry->val_oid))
272                                         return 0;
273
274                                 ret = combine_notes(&l->val_oid,
275                                                     &entry->val_oid);
276                                 if (!ret && is_null_oid(&l->val_oid))
277                                         note_tree_remove(t, tree, n, entry);
278                                 free(entry);
279                                 return ret;
280                         }
281                         break;
282                 case PTR_TYPE_SUBTREE:
283                         if (!SUBTREE_SHA1_PREFIXCMP(l->key_oid.hash,
284                                                     entry->key_oid.hash)) {
285                                 /* unpack 'entry' */
286                                 load_subtree(t, entry, tree, n);
287                                 free(entry);
288                                 return 0;
289                         }
290                         break;
291                 }
292                 break;
293         case PTR_TYPE_SUBTREE:
294                 if (!SUBTREE_SHA1_PREFIXCMP(entry->key_oid.hash, l->key_oid.hash)) {
295                         /* unpack 'l' and restart insert */
296                         *p = NULL;
297                         load_subtree(t, l, tree, n);
298                         free(l);
299                         return note_tree_insert(t, tree, n, entry, type,
300                                                 combine_notes);
301                 }
302                 break;
303         }
304
305         /* non-matching leaf_node */
306         assert(GET_PTR_TYPE(*p) == PTR_TYPE_NOTE ||
307                GET_PTR_TYPE(*p) == PTR_TYPE_SUBTREE);
308         if (is_null_oid(&entry->val_oid)) { /* skip insertion of empty note */
309                 free(entry);
310                 return 0;
311         }
312         new_node = (struct int_node *) xcalloc(1, sizeof(struct int_node));
313         ret = note_tree_insert(t, new_node, n + 1, l, GET_PTR_TYPE(*p),
314                                combine_notes);
315         if (ret)
316                 return ret;
317         *p = SET_PTR_TYPE(new_node, PTR_TYPE_INTERNAL);
318         return note_tree_insert(t, new_node, n + 1, entry, type, combine_notes);
319 }
320
321 /* Free the entire notes data contained in the given tree */
322 static void note_tree_free(struct int_node *tree)
323 {
324         unsigned int i;
325         for (i = 0; i < 16; i++) {
326                 void *p = tree->a[i];
327                 switch (GET_PTR_TYPE(p)) {
328                 case PTR_TYPE_INTERNAL:
329                         note_tree_free(CLR_PTR_TYPE(p));
330                         /* fall through */
331                 case PTR_TYPE_NOTE:
332                 case PTR_TYPE_SUBTREE:
333                         free(CLR_PTR_TYPE(p));
334                 }
335         }
336 }
337
338 static int non_note_cmp(const struct non_note *a, const struct non_note *b)
339 {
340         return strcmp(a->path, b->path);
341 }
342
343 /* note: takes ownership of path string */
344 static void add_non_note(struct notes_tree *t, char *path,
345                 unsigned int mode, const unsigned char *sha1)
346 {
347         struct non_note *p = t->prev_non_note, *n;
348         n = (struct non_note *) xmalloc(sizeof(struct non_note));
349         n->next = NULL;
350         n->path = path;
351         n->mode = mode;
352         hashcpy(n->oid.hash, sha1);
353         t->prev_non_note = n;
354
355         if (!t->first_non_note) {
356                 t->first_non_note = n;
357                 return;
358         }
359
360         if (non_note_cmp(p, n) < 0)
361                 ; /* do nothing  */
362         else if (non_note_cmp(t->first_non_note, n) <= 0)
363                 p = t->first_non_note;
364         else {
365                 /* n sorts before t->first_non_note */
366                 n->next = t->first_non_note;
367                 t->first_non_note = n;
368                 return;
369         }
370
371         /* n sorts equal or after p */
372         while (p->next && non_note_cmp(p->next, n) <= 0)
373                 p = p->next;
374
375         if (non_note_cmp(p, n) == 0) { /* n ~= p; overwrite p with n */
376                 assert(strcmp(p->path, n->path) == 0);
377                 p->mode = n->mode;
378                 oidcpy(&p->oid, &n->oid);
379                 free(n);
380                 t->prev_non_note = p;
381                 return;
382         }
383
384         /* n sorts between p and p->next */
385         n->next = p->next;
386         p->next = n;
387 }
388
389 static void load_subtree(struct notes_tree *t, struct leaf_node *subtree,
390                 struct int_node *node, unsigned int n)
391 {
392         struct object_id object_oid;
393         size_t prefix_len;
394         void *buf;
395         struct tree_desc desc;
396         struct name_entry entry;
397
398         buf = fill_tree_descriptor(&desc, &subtree->val_oid);
399         if (!buf)
400                 die("Could not read %s for notes-index",
401                      oid_to_hex(&subtree->val_oid));
402
403         prefix_len = subtree->key_oid.hash[KEY_INDEX];
404         if (prefix_len >= GIT_SHA1_RAWSZ)
405                 BUG("prefix_len (%"PRIuMAX") is out of range", (uintmax_t)prefix_len);
406         if (prefix_len * 2 < n)
407                 BUG("prefix_len (%"PRIuMAX") is too small", (uintmax_t)prefix_len);
408         memcpy(object_oid.hash, subtree->key_oid.hash, prefix_len);
409         while (tree_entry(&desc, &entry)) {
410                 unsigned char type;
411                 struct leaf_node *l;
412                 size_t path_len = strlen(entry.path);
413
414                 if (path_len == 2 * (GIT_SHA1_RAWSZ - prefix_len)) {
415                         /* This is potentially the remainder of the SHA-1 */
416
417                         if (!S_ISREG(entry.mode))
418                                 /* notes must be blobs */
419                                 goto handle_non_note;
420
421                         if (hex_to_bytes(object_oid.hash + prefix_len, entry.path,
422                                          GIT_SHA1_RAWSZ - prefix_len))
423                                 goto handle_non_note; /* entry.path is not a SHA1 */
424
425                         type = PTR_TYPE_NOTE;
426                 } else if (path_len == 2) {
427                         /* This is potentially an internal node */
428                         size_t len = prefix_len;
429
430                         if (!S_ISDIR(entry.mode))
431                                 /* internal nodes must be trees */
432                                 goto handle_non_note;
433
434                         if (hex_to_bytes(object_oid.hash + len++, entry.path, 1))
435                                 goto handle_non_note; /* entry.path is not a SHA1 */
436
437                         /*
438                          * Pad the rest of the SHA-1 with zeros,
439                          * except for the last byte, where we write
440                          * the length:
441                          */
442                         memset(object_oid.hash + len, 0, GIT_SHA1_RAWSZ - len - 1);
443                         object_oid.hash[KEY_INDEX] = (unsigned char)len;
444
445                         type = PTR_TYPE_SUBTREE;
446                 } else {
447                         /* This can't be part of a note */
448                         goto handle_non_note;
449                 }
450
451                 l = xcalloc(1, sizeof(*l));
452                 oidcpy(&l->key_oid, &object_oid);
453                 oidcpy(&l->val_oid, entry.oid);
454                 if (note_tree_insert(t, node, n, l, type,
455                                      combine_notes_concatenate))
456                         die("Failed to load %s %s into notes tree "
457                             "from %s",
458                             type == PTR_TYPE_NOTE ? "note" : "subtree",
459                             oid_to_hex(&l->key_oid), t->ref);
460
461                 continue;
462
463 handle_non_note:
464                 /*
465                  * Determine full path for this non-note entry. The
466                  * filename is already found in entry.path, but the
467                  * directory part of the path must be deduced from the
468                  * subtree containing this entry based on our
469                  * knowledge that the overall notes tree follows a
470                  * strict byte-based progressive fanout structure
471                  * (i.e. using 2/38, 2/2/36, etc. fanouts).
472                  */
473                 {
474                         struct strbuf non_note_path = STRBUF_INIT;
475                         const char *q = oid_to_hex(&subtree->key_oid);
476                         size_t i;
477                         for (i = 0; i < prefix_len; i++) {
478                                 strbuf_addch(&non_note_path, *q++);
479                                 strbuf_addch(&non_note_path, *q++);
480                                 strbuf_addch(&non_note_path, '/');
481                         }
482                         strbuf_addstr(&non_note_path, entry.path);
483                         add_non_note(t, strbuf_detach(&non_note_path, NULL),
484                                      entry.mode, entry.oid->hash);
485                 }
486         }
487         free(buf);
488 }
489
490 /*
491  * Determine optimal on-disk fanout for this part of the notes tree
492  *
493  * Given a (sub)tree and the level in the internal tree structure, determine
494  * whether or not the given existing fanout should be expanded for this
495  * (sub)tree.
496  *
497  * Values of the 'fanout' variable:
498  * - 0: No fanout (all notes are stored directly in the root notes tree)
499  * - 1: 2/38 fanout
500  * - 2: 2/2/36 fanout
501  * - 3: 2/2/2/34 fanout
502  * etc.
503  */
504 static unsigned char determine_fanout(struct int_node *tree, unsigned char n,
505                 unsigned char fanout)
506 {
507         /*
508          * The following is a simple heuristic that works well in practice:
509          * For each even-numbered 16-tree level (remember that each on-disk
510          * fanout level corresponds to _two_ 16-tree levels), peek at all 16
511          * entries at that tree level. If all of them are either int_nodes or
512          * subtree entries, then there are likely plenty of notes below this
513          * level, so we return an incremented fanout.
514          */
515         unsigned int i;
516         if ((n % 2) || (n > 2 * fanout))
517                 return fanout;
518         for (i = 0; i < 16; i++) {
519                 switch (GET_PTR_TYPE(tree->a[i])) {
520                 case PTR_TYPE_SUBTREE:
521                 case PTR_TYPE_INTERNAL:
522                         continue;
523                 default:
524                         return fanout;
525                 }
526         }
527         return fanout + 1;
528 }
529
530 /* hex SHA1 + 19 * '/' + NUL */
531 #define FANOUT_PATH_MAX GIT_SHA1_HEXSZ + FANOUT_PATH_SEPARATORS + 1
532
533 static void construct_path_with_fanout(const unsigned char *sha1,
534                 unsigned char fanout, char *path)
535 {
536         unsigned int i = 0, j = 0;
537         const char *hex_sha1 = sha1_to_hex(sha1);
538         assert(fanout < GIT_SHA1_RAWSZ);
539         while (fanout) {
540                 path[i++] = hex_sha1[j++];
541                 path[i++] = hex_sha1[j++];
542                 path[i++] = '/';
543                 fanout--;
544         }
545         xsnprintf(path + i, FANOUT_PATH_MAX - i, "%s", hex_sha1 + j);
546 }
547
548 static int for_each_note_helper(struct notes_tree *t, struct int_node *tree,
549                 unsigned char n, unsigned char fanout, int flags,
550                 each_note_fn fn, void *cb_data)
551 {
552         unsigned int i;
553         void *p;
554         int ret = 0;
555         struct leaf_node *l;
556         static char path[FANOUT_PATH_MAX];
557
558         fanout = determine_fanout(tree, n, fanout);
559         for (i = 0; i < 16; i++) {
560 redo:
561                 p = tree->a[i];
562                 switch (GET_PTR_TYPE(p)) {
563                 case PTR_TYPE_INTERNAL:
564                         /* recurse into int_node */
565                         ret = for_each_note_helper(t, CLR_PTR_TYPE(p), n + 1,
566                                 fanout, flags, fn, cb_data);
567                         break;
568                 case PTR_TYPE_SUBTREE:
569                         l = (struct leaf_node *) CLR_PTR_TYPE(p);
570                         /*
571                          * Subtree entries in the note tree represent parts of
572                          * the note tree that have not yet been explored. There
573                          * is a direct relationship between subtree entries at
574                          * level 'n' in the tree, and the 'fanout' variable:
575                          * Subtree entries at level 'n <= 2 * fanout' should be
576                          * preserved, since they correspond exactly to a fanout
577                          * directory in the on-disk structure. However, subtree
578                          * entries at level 'n > 2 * fanout' should NOT be
579                          * preserved, but rather consolidated into the above
580                          * notes tree level. We achieve this by unconditionally
581                          * unpacking subtree entries that exist below the
582                          * threshold level at 'n = 2 * fanout'.
583                          */
584                         if (n <= 2 * fanout &&
585                             flags & FOR_EACH_NOTE_YIELD_SUBTREES) {
586                                 /* invoke callback with subtree */
587                                 unsigned int path_len =
588                                         l->key_oid.hash[KEY_INDEX] * 2 + fanout;
589                                 assert(path_len < FANOUT_PATH_MAX - 1);
590                                 construct_path_with_fanout(l->key_oid.hash,
591                                                            fanout,
592                                                            path);
593                                 /* Create trailing slash, if needed */
594                                 if (path[path_len - 1] != '/')
595                                         path[path_len++] = '/';
596                                 path[path_len] = '\0';
597                                 ret = fn(&l->key_oid, &l->val_oid,
598                                          path,
599                                          cb_data);
600                         }
601                         if (n > fanout * 2 ||
602                             !(flags & FOR_EACH_NOTE_DONT_UNPACK_SUBTREES)) {
603                                 /* unpack subtree and resume traversal */
604                                 tree->a[i] = NULL;
605                                 load_subtree(t, l, tree, n);
606                                 free(l);
607                                 goto redo;
608                         }
609                         break;
610                 case PTR_TYPE_NOTE:
611                         l = (struct leaf_node *) CLR_PTR_TYPE(p);
612                         construct_path_with_fanout(l->key_oid.hash, fanout,
613                                                    path);
614                         ret = fn(&l->key_oid, &l->val_oid, path,
615                                  cb_data);
616                         break;
617                 }
618                 if (ret)
619                         return ret;
620         }
621         return 0;
622 }
623
624 struct tree_write_stack {
625         struct tree_write_stack *next;
626         struct strbuf buf;
627         char path[2]; /* path to subtree in next, if any */
628 };
629
630 static inline int matches_tree_write_stack(struct tree_write_stack *tws,
631                 const char *full_path)
632 {
633         return  full_path[0] == tws->path[0] &&
634                 full_path[1] == tws->path[1] &&
635                 full_path[2] == '/';
636 }
637
638 static void write_tree_entry(struct strbuf *buf, unsigned int mode,
639                 const char *path, unsigned int path_len, const
640                 unsigned char *sha1)
641 {
642         strbuf_addf(buf, "%o %.*s%c", mode, path_len, path, '\0');
643         strbuf_add(buf, sha1, GIT_SHA1_RAWSZ);
644 }
645
646 static void tree_write_stack_init_subtree(struct tree_write_stack *tws,
647                 const char *path)
648 {
649         struct tree_write_stack *n;
650         assert(!tws->next);
651         assert(tws->path[0] == '\0' && tws->path[1] == '\0');
652         n = (struct tree_write_stack *)
653                 xmalloc(sizeof(struct tree_write_stack));
654         n->next = NULL;
655         strbuf_init(&n->buf, 256 * (32 + GIT_SHA1_HEXSZ)); /* assume 256 entries per tree */
656         n->path[0] = n->path[1] = '\0';
657         tws->next = n;
658         tws->path[0] = path[0];
659         tws->path[1] = path[1];
660 }
661
662 static int tree_write_stack_finish_subtree(struct tree_write_stack *tws)
663 {
664         int ret;
665         struct tree_write_stack *n = tws->next;
666         struct object_id s;
667         if (n) {
668                 ret = tree_write_stack_finish_subtree(n);
669                 if (ret)
670                         return ret;
671                 ret = write_object_file(n->buf.buf, n->buf.len, tree_type, &s);
672                 if (ret)
673                         return ret;
674                 strbuf_release(&n->buf);
675                 free(n);
676                 tws->next = NULL;
677                 write_tree_entry(&tws->buf, 040000, tws->path, 2, s.hash);
678                 tws->path[0] = tws->path[1] = '\0';
679         }
680         return 0;
681 }
682
683 static int write_each_note_helper(struct tree_write_stack *tws,
684                 const char *path, unsigned int mode,
685                 const struct object_id *oid)
686 {
687         size_t path_len = strlen(path);
688         unsigned int n = 0;
689         int ret;
690
691         /* Determine common part of tree write stack */
692         while (tws && 3 * n < path_len &&
693                matches_tree_write_stack(tws, path + 3 * n)) {
694                 n++;
695                 tws = tws->next;
696         }
697
698         /* tws point to last matching tree_write_stack entry */
699         ret = tree_write_stack_finish_subtree(tws);
700         if (ret)
701                 return ret;
702
703         /* Start subtrees needed to satisfy path */
704         while (3 * n + 2 < path_len && path[3 * n + 2] == '/') {
705                 tree_write_stack_init_subtree(tws, path + 3 * n);
706                 n++;
707                 tws = tws->next;
708         }
709
710         /* There should be no more directory components in the given path */
711         assert(memchr(path + 3 * n, '/', path_len - (3 * n)) == NULL);
712
713         /* Finally add given entry to the current tree object */
714         write_tree_entry(&tws->buf, mode, path + 3 * n, path_len - (3 * n),
715                          oid->hash);
716
717         return 0;
718 }
719
720 struct write_each_note_data {
721         struct tree_write_stack *root;
722         struct non_note *next_non_note;
723 };
724
725 static int write_each_non_note_until(const char *note_path,
726                 struct write_each_note_data *d)
727 {
728         struct non_note *n = d->next_non_note;
729         int cmp = 0, ret;
730         while (n && (!note_path || (cmp = strcmp(n->path, note_path)) <= 0)) {
731                 if (note_path && cmp == 0)
732                         ; /* do nothing, prefer note to non-note */
733                 else {
734                         ret = write_each_note_helper(d->root, n->path, n->mode,
735                                                      &n->oid);
736                         if (ret)
737                                 return ret;
738                 }
739                 n = n->next;
740         }
741         d->next_non_note = n;
742         return 0;
743 }
744
745 static int write_each_note(const struct object_id *object_oid,
746                 const struct object_id *note_oid, char *note_path,
747                 void *cb_data)
748 {
749         struct write_each_note_data *d =
750                 (struct write_each_note_data *) cb_data;
751         size_t note_path_len = strlen(note_path);
752         unsigned int mode = 0100644;
753
754         if (note_path[note_path_len - 1] == '/') {
755                 /* subtree entry */
756                 note_path_len--;
757                 note_path[note_path_len] = '\0';
758                 mode = 040000;
759         }
760         assert(note_path_len <= GIT_SHA1_HEXSZ + FANOUT_PATH_SEPARATORS);
761
762         /* Weave non-note entries into note entries */
763         return  write_each_non_note_until(note_path, d) ||
764                 write_each_note_helper(d->root, note_path, mode, note_oid);
765 }
766
767 struct note_delete_list {
768         struct note_delete_list *next;
769         const unsigned char *sha1;
770 };
771
772 static int prune_notes_helper(const struct object_id *object_oid,
773                 const struct object_id *note_oid, char *note_path,
774                 void *cb_data)
775 {
776         struct note_delete_list **l = (struct note_delete_list **) cb_data;
777         struct note_delete_list *n;
778
779         if (has_object_file(object_oid))
780                 return 0; /* nothing to do for this note */
781
782         /* failed to find object => prune this note */
783         n = (struct note_delete_list *) xmalloc(sizeof(*n));
784         n->next = *l;
785         n->sha1 = object_oid->hash;
786         *l = n;
787         return 0;
788 }
789
790 int combine_notes_concatenate(struct object_id *cur_oid,
791                               const struct object_id *new_oid)
792 {
793         char *cur_msg = NULL, *new_msg = NULL, *buf;
794         unsigned long cur_len, new_len, buf_len;
795         enum object_type cur_type, new_type;
796         int ret;
797
798         /* read in both note blob objects */
799         if (!is_null_oid(new_oid))
800                 new_msg = read_object_file(new_oid, &new_type, &new_len);
801         if (!new_msg || !new_len || new_type != OBJ_BLOB) {
802                 free(new_msg);
803                 return 0;
804         }
805         if (!is_null_oid(cur_oid))
806                 cur_msg = read_object_file(cur_oid, &cur_type, &cur_len);
807         if (!cur_msg || !cur_len || cur_type != OBJ_BLOB) {
808                 free(cur_msg);
809                 free(new_msg);
810                 oidcpy(cur_oid, new_oid);
811                 return 0;
812         }
813
814         /* we will separate the notes by two newlines anyway */
815         if (cur_msg[cur_len - 1] == '\n')
816                 cur_len--;
817
818         /* concatenate cur_msg and new_msg into buf */
819         buf_len = cur_len + 2 + new_len;
820         buf = (char *) xmalloc(buf_len);
821         memcpy(buf, cur_msg, cur_len);
822         buf[cur_len] = '\n';
823         buf[cur_len + 1] = '\n';
824         memcpy(buf + cur_len + 2, new_msg, new_len);
825         free(cur_msg);
826         free(new_msg);
827
828         /* create a new blob object from buf */
829         ret = write_object_file(buf, buf_len, blob_type, cur_oid);
830         free(buf);
831         return ret;
832 }
833
834 int combine_notes_overwrite(struct object_id *cur_oid,
835                             const struct object_id *new_oid)
836 {
837         oidcpy(cur_oid, new_oid);
838         return 0;
839 }
840
841 int combine_notes_ignore(struct object_id *cur_oid,
842                          const struct object_id *new_oid)
843 {
844         return 0;
845 }
846
847 /*
848  * Add the lines from the named object to list, with trailing
849  * newlines removed.
850  */
851 static int string_list_add_note_lines(struct string_list *list,
852                                       const struct object_id *oid)
853 {
854         char *data;
855         unsigned long len;
856         enum object_type t;
857
858         if (is_null_oid(oid))
859                 return 0;
860
861         /* read_sha1_file NUL-terminates */
862         data = read_object_file(oid, &t, &len);
863         if (t != OBJ_BLOB || !data || !len) {
864                 free(data);
865                 return t != OBJ_BLOB || !data;
866         }
867
868         /*
869          * If the last line of the file is EOL-terminated, this will
870          * add an empty string to the list.  But it will be removed
871          * later, along with any empty strings that came from empty
872          * lines within the file.
873          */
874         string_list_split(list, data, '\n', -1);
875         free(data);
876         return 0;
877 }
878
879 static int string_list_join_lines_helper(struct string_list_item *item,
880                                          void *cb_data)
881 {
882         struct strbuf *buf = cb_data;
883         strbuf_addstr(buf, item->string);
884         strbuf_addch(buf, '\n');
885         return 0;
886 }
887
888 int combine_notes_cat_sort_uniq(struct object_id *cur_oid,
889                                 const struct object_id *new_oid)
890 {
891         struct string_list sort_uniq_list = STRING_LIST_INIT_DUP;
892         struct strbuf buf = STRBUF_INIT;
893         int ret = 1;
894
895         /* read both note blob objects into unique_lines */
896         if (string_list_add_note_lines(&sort_uniq_list, cur_oid))
897                 goto out;
898         if (string_list_add_note_lines(&sort_uniq_list, new_oid))
899                 goto out;
900         string_list_remove_empty_items(&sort_uniq_list, 0);
901         string_list_sort(&sort_uniq_list);
902         string_list_remove_duplicates(&sort_uniq_list, 0);
903
904         /* create a new blob object from sort_uniq_list */
905         if (for_each_string_list(&sort_uniq_list,
906                                  string_list_join_lines_helper, &buf))
907                 goto out;
908
909         ret = write_object_file(buf.buf, buf.len, blob_type, cur_oid);
910
911 out:
912         strbuf_release(&buf);
913         string_list_clear(&sort_uniq_list, 0);
914         return ret;
915 }
916
917 static int string_list_add_one_ref(const char *refname, const struct object_id *oid,
918                                    int flag, void *cb)
919 {
920         struct string_list *refs = cb;
921         if (!unsorted_string_list_has_string(refs, refname))
922                 string_list_append(refs, refname);
923         return 0;
924 }
925
926 /*
927  * The list argument must have strdup_strings set on it.
928  */
929 void string_list_add_refs_by_glob(struct string_list *list, const char *glob)
930 {
931         assert(list->strdup_strings);
932         if (has_glob_specials(glob)) {
933                 for_each_glob_ref(string_list_add_one_ref, glob, list);
934         } else {
935                 struct object_id oid;
936                 if (get_oid(glob, &oid))
937                         warning("notes ref %s is invalid", glob);
938                 if (!unsorted_string_list_has_string(list, glob))
939                         string_list_append(list, glob);
940         }
941 }
942
943 void string_list_add_refs_from_colon_sep(struct string_list *list,
944                                          const char *globs)
945 {
946         struct string_list split = STRING_LIST_INIT_NODUP;
947         char *globs_copy = xstrdup(globs);
948         int i;
949
950         string_list_split_in_place(&split, globs_copy, ':', -1);
951         string_list_remove_empty_items(&split, 0);
952
953         for (i = 0; i < split.nr; i++)
954                 string_list_add_refs_by_glob(list, split.items[i].string);
955
956         string_list_clear(&split, 0);
957         free(globs_copy);
958 }
959
960 static int notes_display_config(const char *k, const char *v, void *cb)
961 {
962         int *load_refs = cb;
963
964         if (*load_refs && !strcmp(k, "notes.displayref")) {
965                 if (!v)
966                         config_error_nonbool(k);
967                 string_list_add_refs_by_glob(&display_notes_refs, v);
968         }
969
970         return 0;
971 }
972
973 const char *default_notes_ref(void)
974 {
975         const char *notes_ref = NULL;
976         if (!notes_ref)
977                 notes_ref = getenv(GIT_NOTES_REF_ENVIRONMENT);
978         if (!notes_ref)
979                 notes_ref = notes_ref_name; /* value of core.notesRef config */
980         if (!notes_ref)
981                 notes_ref = GIT_NOTES_DEFAULT_REF;
982         return notes_ref;
983 }
984
985 void init_notes(struct notes_tree *t, const char *notes_ref,
986                 combine_notes_fn combine_notes, int flags)
987 {
988         struct object_id oid, object_oid;
989         unsigned mode;
990         struct leaf_node root_tree;
991
992         if (!t)
993                 t = &default_notes_tree;
994         assert(!t->initialized);
995
996         if (!notes_ref)
997                 notes_ref = default_notes_ref();
998
999         if (!combine_notes)
1000                 combine_notes = combine_notes_concatenate;
1001
1002         t->root = (struct int_node *) xcalloc(1, sizeof(struct int_node));
1003         t->first_non_note = NULL;
1004         t->prev_non_note = NULL;
1005         t->ref = xstrdup_or_null(notes_ref);
1006         t->update_ref = (flags & NOTES_INIT_WRITABLE) ? t->ref : NULL;
1007         t->combine_notes = combine_notes;
1008         t->initialized = 1;
1009         t->dirty = 0;
1010
1011         if (flags & NOTES_INIT_EMPTY || !notes_ref ||
1012             get_oid_treeish(notes_ref, &object_oid))
1013                 return;
1014         if (flags & NOTES_INIT_WRITABLE && read_ref(notes_ref, &object_oid))
1015                 die("Cannot use notes ref %s", notes_ref);
1016         if (get_tree_entry(&object_oid, "", &oid, &mode))
1017                 die("Failed to read notes tree referenced by %s (%s)",
1018                     notes_ref, oid_to_hex(&object_oid));
1019
1020         oidclr(&root_tree.key_oid);
1021         oidcpy(&root_tree.val_oid, &oid);
1022         load_subtree(t, &root_tree, t->root, 0);
1023 }
1024
1025 struct notes_tree **load_notes_trees(struct string_list *refs, int flags)
1026 {
1027         struct string_list_item *item;
1028         int counter = 0;
1029         struct notes_tree **trees;
1030         ALLOC_ARRAY(trees, refs->nr + 1);
1031         for_each_string_list_item(item, refs) {
1032                 struct notes_tree *t = xcalloc(1, sizeof(struct notes_tree));
1033                 init_notes(t, item->string, combine_notes_ignore, flags);
1034                 trees[counter++] = t;
1035         }
1036         trees[counter] = NULL;
1037         return trees;
1038 }
1039
1040 void init_display_notes(struct display_notes_opt *opt)
1041 {
1042         char *display_ref_env;
1043         int load_config_refs = 0;
1044         display_notes_refs.strdup_strings = 1;
1045
1046         assert(!display_notes_trees);
1047
1048         if (!opt || opt->use_default_notes > 0 ||
1049             (opt->use_default_notes == -1 && !opt->extra_notes_refs.nr)) {
1050                 string_list_append(&display_notes_refs, default_notes_ref());
1051                 display_ref_env = getenv(GIT_NOTES_DISPLAY_REF_ENVIRONMENT);
1052                 if (display_ref_env) {
1053                         string_list_add_refs_from_colon_sep(&display_notes_refs,
1054                                                             display_ref_env);
1055                         load_config_refs = 0;
1056                 } else
1057                         load_config_refs = 1;
1058         }
1059
1060         git_config(notes_display_config, &load_config_refs);
1061
1062         if (opt) {
1063                 struct string_list_item *item;
1064                 for_each_string_list_item(item, &opt->extra_notes_refs)
1065                         string_list_add_refs_by_glob(&display_notes_refs,
1066                                                      item->string);
1067         }
1068
1069         display_notes_trees = load_notes_trees(&display_notes_refs, 0);
1070         string_list_clear(&display_notes_refs, 0);
1071 }
1072
1073 int add_note(struct notes_tree *t, const struct object_id *object_oid,
1074                 const struct object_id *note_oid, combine_notes_fn combine_notes)
1075 {
1076         struct leaf_node *l;
1077
1078         if (!t)
1079                 t = &default_notes_tree;
1080         assert(t->initialized);
1081         t->dirty = 1;
1082         if (!combine_notes)
1083                 combine_notes = t->combine_notes;
1084         l = (struct leaf_node *) xmalloc(sizeof(struct leaf_node));
1085         oidcpy(&l->key_oid, object_oid);
1086         oidcpy(&l->val_oid, note_oid);
1087         return note_tree_insert(t, t->root, 0, l, PTR_TYPE_NOTE, combine_notes);
1088 }
1089
1090 int remove_note(struct notes_tree *t, const unsigned char *object_sha1)
1091 {
1092         struct leaf_node l;
1093
1094         if (!t)
1095                 t = &default_notes_tree;
1096         assert(t->initialized);
1097         hashcpy(l.key_oid.hash, object_sha1);
1098         oidclr(&l.val_oid);
1099         note_tree_remove(t, t->root, 0, &l);
1100         if (is_null_oid(&l.val_oid)) /* no note was removed */
1101                 return 1;
1102         t->dirty = 1;
1103         return 0;
1104 }
1105
1106 const struct object_id *get_note(struct notes_tree *t,
1107                 const struct object_id *oid)
1108 {
1109         struct leaf_node *found;
1110
1111         if (!t)
1112                 t = &default_notes_tree;
1113         assert(t->initialized);
1114         found = note_tree_find(t, t->root, 0, oid->hash);
1115         return found ? &found->val_oid : NULL;
1116 }
1117
1118 int for_each_note(struct notes_tree *t, int flags, each_note_fn fn,
1119                 void *cb_data)
1120 {
1121         if (!t)
1122                 t = &default_notes_tree;
1123         assert(t->initialized);
1124         return for_each_note_helper(t, t->root, 0, 0, flags, fn, cb_data);
1125 }
1126
1127 int write_notes_tree(struct notes_tree *t, struct object_id *result)
1128 {
1129         struct tree_write_stack root;
1130         struct write_each_note_data cb_data;
1131         int ret;
1132         int flags;
1133
1134         if (!t)
1135                 t = &default_notes_tree;
1136         assert(t->initialized);
1137
1138         /* Prepare for traversal of current notes tree */
1139         root.next = NULL; /* last forward entry in list is grounded */
1140         strbuf_init(&root.buf, 256 * (32 + GIT_SHA1_HEXSZ)); /* assume 256 entries */
1141         root.path[0] = root.path[1] = '\0';
1142         cb_data.root = &root;
1143         cb_data.next_non_note = t->first_non_note;
1144
1145         /* Write tree objects representing current notes tree */
1146         flags = FOR_EACH_NOTE_DONT_UNPACK_SUBTREES |
1147                 FOR_EACH_NOTE_YIELD_SUBTREES;
1148         ret = for_each_note(t, flags, write_each_note, &cb_data) ||
1149               write_each_non_note_until(NULL, &cb_data) ||
1150               tree_write_stack_finish_subtree(&root) ||
1151               write_object_file(root.buf.buf, root.buf.len, tree_type, result);
1152         strbuf_release(&root.buf);
1153         return ret;
1154 }
1155
1156 void prune_notes(struct notes_tree *t, int flags)
1157 {
1158         struct note_delete_list *l = NULL;
1159
1160         if (!t)
1161                 t = &default_notes_tree;
1162         assert(t->initialized);
1163
1164         for_each_note(t, 0, prune_notes_helper, &l);
1165
1166         while (l) {
1167                 if (flags & NOTES_PRUNE_VERBOSE)
1168                         printf("%s\n", sha1_to_hex(l->sha1));
1169                 if (!(flags & NOTES_PRUNE_DRYRUN))
1170                         remove_note(t, l->sha1);
1171                 l = l->next;
1172         }
1173 }
1174
1175 void free_notes(struct notes_tree *t)
1176 {
1177         if (!t)
1178                 t = &default_notes_tree;
1179         if (t->root)
1180                 note_tree_free(t->root);
1181         free(t->root);
1182         while (t->first_non_note) {
1183                 t->prev_non_note = t->first_non_note->next;
1184                 free(t->first_non_note->path);
1185                 free(t->first_non_note);
1186                 t->first_non_note = t->prev_non_note;
1187         }
1188         free(t->ref);
1189         memset(t, 0, sizeof(struct notes_tree));
1190 }
1191
1192 /*
1193  * Fill the given strbuf with the notes associated with the given object.
1194  *
1195  * If the given notes_tree structure is not initialized, it will be auto-
1196  * initialized to the default value (see documentation for init_notes() above).
1197  * If the given notes_tree is NULL, the internal/default notes_tree will be
1198  * used instead.
1199  *
1200  * (raw != 0) gives the %N userformat; otherwise, the note message is given
1201  * for human consumption.
1202  */
1203 static void format_note(struct notes_tree *t, const struct object_id *object_oid,
1204                         struct strbuf *sb, const char *output_encoding, int raw)
1205 {
1206         static const char utf8[] = "utf-8";
1207         const struct object_id *oid;
1208         char *msg, *msg_p;
1209         unsigned long linelen, msglen;
1210         enum object_type type;
1211
1212         if (!t)
1213                 t = &default_notes_tree;
1214         if (!t->initialized)
1215                 init_notes(t, NULL, NULL, 0);
1216
1217         oid = get_note(t, object_oid);
1218         if (!oid)
1219                 return;
1220
1221         if (!(msg = read_object_file(oid, &type, &msglen)) || type != OBJ_BLOB) {
1222                 free(msg);
1223                 return;
1224         }
1225
1226         if (output_encoding && *output_encoding &&
1227             !is_encoding_utf8(output_encoding)) {
1228                 char *reencoded = reencode_string(msg, output_encoding, utf8);
1229                 if (reencoded) {
1230                         free(msg);
1231                         msg = reencoded;
1232                         msglen = strlen(msg);
1233                 }
1234         }
1235
1236         /* we will end the annotation by a newline anyway */
1237         if (msglen && msg[msglen - 1] == '\n')
1238                 msglen--;
1239
1240         if (!raw) {
1241                 const char *ref = t->ref;
1242                 if (!ref || !strcmp(ref, GIT_NOTES_DEFAULT_REF)) {
1243                         strbuf_addstr(sb, "\nNotes:\n");
1244                 } else {
1245                         if (starts_with(ref, "refs/"))
1246                                 ref += 5;
1247                         if (starts_with(ref, "notes/"))
1248                                 ref += 6;
1249                         strbuf_addf(sb, "\nNotes (%s):\n", ref);
1250                 }
1251         }
1252
1253         for (msg_p = msg; msg_p < msg + msglen; msg_p += linelen + 1) {
1254                 linelen = strchrnul(msg_p, '\n') - msg_p;
1255
1256                 if (!raw)
1257                         strbuf_addstr(sb, "    ");
1258                 strbuf_add(sb, msg_p, linelen);
1259                 strbuf_addch(sb, '\n');
1260         }
1261
1262         free(msg);
1263 }
1264
1265 void format_display_notes(const struct object_id *object_oid,
1266                           struct strbuf *sb, const char *output_encoding, int raw)
1267 {
1268         int i;
1269         assert(display_notes_trees);
1270         for (i = 0; display_notes_trees[i]; i++)
1271                 format_note(display_notes_trees[i], object_oid, sb,
1272                             output_encoding, raw);
1273 }
1274
1275 int copy_note(struct notes_tree *t,
1276               const struct object_id *from_obj, const struct object_id *to_obj,
1277               int force, combine_notes_fn combine_notes)
1278 {
1279         const struct object_id *note = get_note(t, from_obj);
1280         const struct object_id *existing_note = get_note(t, to_obj);
1281
1282         if (!force && existing_note)
1283                 return 1;
1284
1285         if (note)
1286                 return add_note(t, to_obj, note, combine_notes);
1287         else if (existing_note)
1288                 return add_note(t, to_obj, &null_oid, combine_notes);
1289
1290         return 0;
1291 }
1292
1293 void expand_notes_ref(struct strbuf *sb)
1294 {
1295         if (starts_with(sb->buf, "refs/notes/"))
1296                 return; /* we're happy */
1297         else if (starts_with(sb->buf, "notes/"))
1298                 strbuf_insert(sb, 0, "refs/", 5);
1299         else
1300                 strbuf_insert(sb, 0, "refs/notes/", 11);
1301 }
1302
1303 void expand_loose_notes_ref(struct strbuf *sb)
1304 {
1305         struct object_id object;
1306
1307         if (get_oid(sb->buf, &object)) {
1308                 /* fallback to expand_notes_ref */
1309                 expand_notes_ref(sb);
1310         }
1311 }