Merge branch 'js/skip-dashed-built-ins-from-config-mak'
[git] / ref-filter.c
1 #include "builtin.h"
2 #include "cache.h"
3 #include "parse-options.h"
4 #include "refs.h"
5 #include "wildmatch.h"
6 #include "object-store.h"
7 #include "repository.h"
8 #include "commit.h"
9 #include "remote.h"
10 #include "color.h"
11 #include "tag.h"
12 #include "quote.h"
13 #include "ref-filter.h"
14 #include "revision.h"
15 #include "utf8.h"
16 #include "git-compat-util.h"
17 #include "version.h"
18 #include "trailer.h"
19 #include "wt-status.h"
20 #include "commit-slab.h"
21 #include "commit-graph.h"
22 #include "commit-reach.h"
23 #include "worktree.h"
24 #include "hashmap.h"
25 #include "strvec.h"
26
27 static struct ref_msg {
28         const char *gone;
29         const char *ahead;
30         const char *behind;
31         const char *ahead_behind;
32 } msgs = {
33          /* Untranslated plumbing messages: */
34         "gone",
35         "ahead %d",
36         "behind %d",
37         "ahead %d, behind %d"
38 };
39
40 void setup_ref_filter_porcelain_msg(void)
41 {
42         msgs.gone = _("gone");
43         msgs.ahead = _("ahead %d");
44         msgs.behind = _("behind %d");
45         msgs.ahead_behind = _("ahead %d, behind %d");
46 }
47
48 typedef enum { FIELD_STR, FIELD_ULONG, FIELD_TIME } cmp_type;
49 typedef enum { COMPARE_EQUAL, COMPARE_UNEQUAL, COMPARE_NONE } cmp_status;
50 typedef enum { SOURCE_NONE = 0, SOURCE_OBJ, SOURCE_OTHER } info_source;
51
52 struct align {
53         align_type position;
54         unsigned int width;
55 };
56
57 struct if_then_else {
58         cmp_status cmp_status;
59         const char *str;
60         unsigned int then_atom_seen : 1,
61                 else_atom_seen : 1,
62                 condition_satisfied : 1;
63 };
64
65 struct refname_atom {
66         enum { R_NORMAL, R_SHORT, R_LSTRIP, R_RSTRIP } option;
67         int lstrip, rstrip;
68 };
69
70 static struct expand_data {
71         struct object_id oid;
72         enum object_type type;
73         unsigned long size;
74         off_t disk_size;
75         struct object_id delta_base_oid;
76         void *content;
77
78         struct object_info info;
79 } oi, oi_deref;
80
81 struct ref_to_worktree_entry {
82         struct hashmap_entry ent;
83         struct worktree *wt; /* key is wt->head_ref */
84 };
85
86 static int ref_to_worktree_map_cmpfnc(const void *unused_lookupdata,
87                                       const struct hashmap_entry *eptr,
88                                       const struct hashmap_entry *kptr,
89                                       const void *keydata_aka_refname)
90 {
91         const struct ref_to_worktree_entry *e, *k;
92
93         e = container_of(eptr, const struct ref_to_worktree_entry, ent);
94         k = container_of(kptr, const struct ref_to_worktree_entry, ent);
95
96         return strcmp(e->wt->head_ref,
97                 keydata_aka_refname ? keydata_aka_refname : k->wt->head_ref);
98 }
99
100 static struct ref_to_worktree_map {
101         struct hashmap map;
102         struct worktree **worktrees;
103 } ref_to_worktree_map;
104
105 /*
106  * An atom is a valid field atom listed below, possibly prefixed with
107  * a "*" to denote deref_tag().
108  *
109  * We parse given format string and sort specifiers, and make a list
110  * of properties that we need to extract out of objects.  ref_array_item
111  * structure will hold an array of values extracted that can be
112  * indexed with the "atom number", which is an index into this
113  * array.
114  */
115 static struct used_atom {
116         const char *name;
117         cmp_type type;
118         info_source source;
119         union {
120                 char color[COLOR_MAXLEN];
121                 struct align align;
122                 struct {
123                         enum {
124                                 RR_REF, RR_TRACK, RR_TRACKSHORT, RR_REMOTE_NAME, RR_REMOTE_REF
125                         } option;
126                         struct refname_atom refname;
127                         unsigned int nobracket : 1, push : 1, push_remote : 1;
128                 } remote_ref;
129                 struct {
130                         enum { C_BARE, C_BODY, C_BODY_DEP, C_LENGTH, C_LINES,
131                                C_SIG, C_SUB, C_SUB_SANITIZE, C_TRAILERS } option;
132                         struct process_trailer_options trailer_opts;
133                         unsigned int nlines;
134                 } contents;
135                 struct {
136                         cmp_status cmp_status;
137                         const char *str;
138                 } if_then_else;
139                 struct {
140                         enum { O_FULL, O_LENGTH, O_SHORT } option;
141                         unsigned int length;
142                 } oid;
143                 struct email_option {
144                         enum { EO_RAW, EO_TRIM, EO_LOCALPART } option;
145                 } email_option;
146                 struct refname_atom refname;
147                 char *head;
148         } u;
149 } *used_atom;
150 static int used_atom_cnt, need_tagged, need_symref;
151
152 /*
153  * Expand string, append it to strbuf *sb, then return error code ret.
154  * Allow to save few lines of code.
155  */
156 static int strbuf_addf_ret(struct strbuf *sb, int ret, const char *fmt, ...)
157 {
158         va_list ap;
159         va_start(ap, fmt);
160         strbuf_vaddf(sb, fmt, ap);
161         va_end(ap);
162         return ret;
163 }
164
165 static int color_atom_parser(const struct ref_format *format, struct used_atom *atom,
166                              const char *color_value, struct strbuf *err)
167 {
168         if (!color_value)
169                 return strbuf_addf_ret(err, -1, _("expected format: %%(color:<color>)"));
170         if (color_parse(color_value, atom->u.color) < 0)
171                 return strbuf_addf_ret(err, -1, _("unrecognized color: %%(color:%s)"),
172                                        color_value);
173         /*
174          * We check this after we've parsed the color, which lets us complain
175          * about syntactically bogus color names even if they won't be used.
176          */
177         if (!want_color(format->use_color))
178                 color_parse("", atom->u.color);
179         return 0;
180 }
181
182 static int refname_atom_parser_internal(struct refname_atom *atom, const char *arg,
183                                          const char *name, struct strbuf *err)
184 {
185         if (!arg)
186                 atom->option = R_NORMAL;
187         else if (!strcmp(arg, "short"))
188                 atom->option = R_SHORT;
189         else if (skip_prefix(arg, "lstrip=", &arg) ||
190                  skip_prefix(arg, "strip=", &arg)) {
191                 atom->option = R_LSTRIP;
192                 if (strtol_i(arg, 10, &atom->lstrip))
193                         return strbuf_addf_ret(err, -1, _("Integer value expected refname:lstrip=%s"), arg);
194         } else if (skip_prefix(arg, "rstrip=", &arg)) {
195                 atom->option = R_RSTRIP;
196                 if (strtol_i(arg, 10, &atom->rstrip))
197                         return strbuf_addf_ret(err, -1, _("Integer value expected refname:rstrip=%s"), arg);
198         } else
199                 return strbuf_addf_ret(err, -1, _("unrecognized %%(%s) argument: %s"), name, arg);
200         return 0;
201 }
202
203 static int remote_ref_atom_parser(const struct ref_format *format, struct used_atom *atom,
204                                   const char *arg, struct strbuf *err)
205 {
206         struct string_list params = STRING_LIST_INIT_DUP;
207         int i;
208
209         if (!strcmp(atom->name, "push") || starts_with(atom->name, "push:"))
210                 atom->u.remote_ref.push = 1;
211
212         if (!arg) {
213                 atom->u.remote_ref.option = RR_REF;
214                 return refname_atom_parser_internal(&atom->u.remote_ref.refname,
215                                                     arg, atom->name, err);
216         }
217
218         atom->u.remote_ref.nobracket = 0;
219         string_list_split(&params, arg, ',', -1);
220
221         for (i = 0; i < params.nr; i++) {
222                 const char *s = params.items[i].string;
223
224                 if (!strcmp(s, "track"))
225                         atom->u.remote_ref.option = RR_TRACK;
226                 else if (!strcmp(s, "trackshort"))
227                         atom->u.remote_ref.option = RR_TRACKSHORT;
228                 else if (!strcmp(s, "nobracket"))
229                         atom->u.remote_ref.nobracket = 1;
230                 else if (!strcmp(s, "remotename")) {
231                         atom->u.remote_ref.option = RR_REMOTE_NAME;
232                         atom->u.remote_ref.push_remote = 1;
233                 } else if (!strcmp(s, "remoteref")) {
234                         atom->u.remote_ref.option = RR_REMOTE_REF;
235                         atom->u.remote_ref.push_remote = 1;
236                 } else {
237                         atom->u.remote_ref.option = RR_REF;
238                         if (refname_atom_parser_internal(&atom->u.remote_ref.refname,
239                                                          arg, atom->name, err)) {
240                                 string_list_clear(&params, 0);
241                                 return -1;
242                         }
243                 }
244         }
245
246         string_list_clear(&params, 0);
247         return 0;
248 }
249
250 static int objecttype_atom_parser(const struct ref_format *format, struct used_atom *atom,
251                                   const char *arg, struct strbuf *err)
252 {
253         if (arg)
254                 return strbuf_addf_ret(err, -1, _("%%(objecttype) does not take arguments"));
255         if (*atom->name == '*')
256                 oi_deref.info.typep = &oi_deref.type;
257         else
258                 oi.info.typep = &oi.type;
259         return 0;
260 }
261
262 static int objectsize_atom_parser(const struct ref_format *format, struct used_atom *atom,
263                                   const char *arg, struct strbuf *err)
264 {
265         if (!arg) {
266                 if (*atom->name == '*')
267                         oi_deref.info.sizep = &oi_deref.size;
268                 else
269                         oi.info.sizep = &oi.size;
270         } else if (!strcmp(arg, "disk")) {
271                 if (*atom->name == '*')
272                         oi_deref.info.disk_sizep = &oi_deref.disk_size;
273                 else
274                         oi.info.disk_sizep = &oi.disk_size;
275         } else
276                 return strbuf_addf_ret(err, -1, _("unrecognized %%(objectsize) argument: %s"), arg);
277         return 0;
278 }
279
280 static int deltabase_atom_parser(const struct ref_format *format, struct used_atom *atom,
281                                  const char *arg, struct strbuf *err)
282 {
283         if (arg)
284                 return strbuf_addf_ret(err, -1, _("%%(deltabase) does not take arguments"));
285         if (*atom->name == '*')
286                 oi_deref.info.delta_base_oid = &oi_deref.delta_base_oid;
287         else
288                 oi.info.delta_base_oid = &oi.delta_base_oid;
289         return 0;
290 }
291
292 static int body_atom_parser(const struct ref_format *format, struct used_atom *atom,
293                             const char *arg, struct strbuf *err)
294 {
295         if (arg)
296                 return strbuf_addf_ret(err, -1, _("%%(body) does not take arguments"));
297         atom->u.contents.option = C_BODY_DEP;
298         return 0;
299 }
300
301 static int subject_atom_parser(const struct ref_format *format, struct used_atom *atom,
302                                const char *arg, struct strbuf *err)
303 {
304         if (!arg)
305                 atom->u.contents.option = C_SUB;
306         else if (!strcmp(arg, "sanitize"))
307                 atom->u.contents.option = C_SUB_SANITIZE;
308         else
309                 return strbuf_addf_ret(err, -1, _("unrecognized %%(subject) argument: %s"), arg);
310         return 0;
311 }
312
313 static int trailers_atom_parser(const struct ref_format *format, struct used_atom *atom,
314                                 const char *arg, struct strbuf *err)
315 {
316         struct string_list params = STRING_LIST_INIT_DUP;
317         int i;
318
319         atom->u.contents.trailer_opts.no_divider = 1;
320
321         if (arg) {
322                 string_list_split(&params, arg, ',', -1);
323                 for (i = 0; i < params.nr; i++) {
324                         const char *s = params.items[i].string;
325                         if (!strcmp(s, "unfold"))
326                                 atom->u.contents.trailer_opts.unfold = 1;
327                         else if (!strcmp(s, "only"))
328                                 atom->u.contents.trailer_opts.only_trailers = 1;
329                         else {
330                                 strbuf_addf(err, _("unknown %%(trailers) argument: %s"), s);
331                                 string_list_clear(&params, 0);
332                                 return -1;
333                         }
334                 }
335         }
336         atom->u.contents.option = C_TRAILERS;
337         string_list_clear(&params, 0);
338         return 0;
339 }
340
341 static int contents_atom_parser(const struct ref_format *format, struct used_atom *atom,
342                                 const char *arg, struct strbuf *err)
343 {
344         if (!arg)
345                 atom->u.contents.option = C_BARE;
346         else if (!strcmp(arg, "body"))
347                 atom->u.contents.option = C_BODY;
348         else if (!strcmp(arg, "size"))
349                 atom->u.contents.option = C_LENGTH;
350         else if (!strcmp(arg, "signature"))
351                 atom->u.contents.option = C_SIG;
352         else if (!strcmp(arg, "subject"))
353                 atom->u.contents.option = C_SUB;
354         else if (!strcmp(arg, "trailers")) {
355                 if (trailers_atom_parser(format, atom, NULL, err))
356                         return -1;
357         } else if (skip_prefix(arg, "trailers:", &arg)) {
358                 if (trailers_atom_parser(format, atom, arg, err))
359                         return -1;
360         } else if (skip_prefix(arg, "lines=", &arg)) {
361                 atom->u.contents.option = C_LINES;
362                 if (strtoul_ui(arg, 10, &atom->u.contents.nlines))
363                         return strbuf_addf_ret(err, -1, _("positive value expected contents:lines=%s"), arg);
364         } else
365                 return strbuf_addf_ret(err, -1, _("unrecognized %%(contents) argument: %s"), arg);
366         return 0;
367 }
368
369 static int oid_atom_parser(const struct ref_format *format, struct used_atom *atom,
370                            const char *arg, struct strbuf *err)
371 {
372         if (!arg)
373                 atom->u.oid.option = O_FULL;
374         else if (!strcmp(arg, "short"))
375                 atom->u.oid.option = O_SHORT;
376         else if (skip_prefix(arg, "short=", &arg)) {
377                 atom->u.oid.option = O_LENGTH;
378                 if (strtoul_ui(arg, 10, &atom->u.oid.length) ||
379                     atom->u.oid.length == 0)
380                         return strbuf_addf_ret(err, -1, _("positive value expected '%s' in %%(%s)"), arg, atom->name);
381                 if (atom->u.oid.length < MINIMUM_ABBREV)
382                         atom->u.oid.length = MINIMUM_ABBREV;
383         } else
384                 return strbuf_addf_ret(err, -1, _("unrecognized argument '%s' in %%(%s)"), arg, atom->name);
385         return 0;
386 }
387
388 static int person_email_atom_parser(const struct ref_format *format, struct used_atom *atom,
389                                     const char *arg, struct strbuf *err)
390 {
391         if (!arg)
392                 atom->u.email_option.option = EO_RAW;
393         else if (!strcmp(arg, "trim"))
394                 atom->u.email_option.option = EO_TRIM;
395         else if (!strcmp(arg, "localpart"))
396                 atom->u.email_option.option = EO_LOCALPART;
397         else
398                 return strbuf_addf_ret(err, -1, _("unrecognized email option: %s"), arg);
399         return 0;
400 }
401
402 static int refname_atom_parser(const struct ref_format *format, struct used_atom *atom,
403                                const char *arg, struct strbuf *err)
404 {
405         return refname_atom_parser_internal(&atom->u.refname, arg, atom->name, err);
406 }
407
408 static align_type parse_align_position(const char *s)
409 {
410         if (!strcmp(s, "right"))
411                 return ALIGN_RIGHT;
412         else if (!strcmp(s, "middle"))
413                 return ALIGN_MIDDLE;
414         else if (!strcmp(s, "left"))
415                 return ALIGN_LEFT;
416         return -1;
417 }
418
419 static int align_atom_parser(const struct ref_format *format, struct used_atom *atom,
420                              const char *arg, struct strbuf *err)
421 {
422         struct align *align = &atom->u.align;
423         struct string_list params = STRING_LIST_INIT_DUP;
424         int i;
425         unsigned int width = ~0U;
426
427         if (!arg)
428                 return strbuf_addf_ret(err, -1, _("expected format: %%(align:<width>,<position>)"));
429
430         align->position = ALIGN_LEFT;
431
432         string_list_split(&params, arg, ',', -1);
433         for (i = 0; i < params.nr; i++) {
434                 const char *s = params.items[i].string;
435                 int position;
436
437                 if (skip_prefix(s, "position=", &s)) {
438                         position = parse_align_position(s);
439                         if (position < 0) {
440                                 strbuf_addf(err, _("unrecognized position:%s"), s);
441                                 string_list_clear(&params, 0);
442                                 return -1;
443                         }
444                         align->position = position;
445                 } else if (skip_prefix(s, "width=", &s)) {
446                         if (strtoul_ui(s, 10, &width)) {
447                                 strbuf_addf(err, _("unrecognized width:%s"), s);
448                                 string_list_clear(&params, 0);
449                                 return -1;
450                         }
451                 } else if (!strtoul_ui(s, 10, &width))
452                         ;
453                 else if ((position = parse_align_position(s)) >= 0)
454                         align->position = position;
455                 else {
456                         strbuf_addf(err, _("unrecognized %%(align) argument: %s"), s);
457                         string_list_clear(&params, 0);
458                         return -1;
459                 }
460         }
461
462         if (width == ~0U) {
463                 string_list_clear(&params, 0);
464                 return strbuf_addf_ret(err, -1, _("positive width expected with the %%(align) atom"));
465         }
466         align->width = width;
467         string_list_clear(&params, 0);
468         return 0;
469 }
470
471 static int if_atom_parser(const struct ref_format *format, struct used_atom *atom,
472                           const char *arg, struct strbuf *err)
473 {
474         if (!arg) {
475                 atom->u.if_then_else.cmp_status = COMPARE_NONE;
476                 return 0;
477         } else if (skip_prefix(arg, "equals=", &atom->u.if_then_else.str)) {
478                 atom->u.if_then_else.cmp_status = COMPARE_EQUAL;
479         } else if (skip_prefix(arg, "notequals=", &atom->u.if_then_else.str)) {
480                 atom->u.if_then_else.cmp_status = COMPARE_UNEQUAL;
481         } else
482                 return strbuf_addf_ret(err, -1, _("unrecognized %%(if) argument: %s"), arg);
483         return 0;
484 }
485
486 static int head_atom_parser(const struct ref_format *format, struct used_atom *atom,
487                             const char *arg, struct strbuf *unused_err)
488 {
489         atom->u.head = resolve_refdup("HEAD", RESOLVE_REF_READING, NULL, NULL);
490         return 0;
491 }
492
493 static struct {
494         const char *name;
495         info_source source;
496         cmp_type cmp_type;
497         int (*parser)(const struct ref_format *format, struct used_atom *atom,
498                       const char *arg, struct strbuf *err);
499 } valid_atom[] = {
500         { "refname", SOURCE_NONE, FIELD_STR, refname_atom_parser },
501         { "objecttype", SOURCE_OTHER, FIELD_STR, objecttype_atom_parser },
502         { "objectsize", SOURCE_OTHER, FIELD_ULONG, objectsize_atom_parser },
503         { "objectname", SOURCE_OTHER, FIELD_STR, oid_atom_parser },
504         { "deltabase", SOURCE_OTHER, FIELD_STR, deltabase_atom_parser },
505         { "tree", SOURCE_OBJ, FIELD_STR, oid_atom_parser },
506         { "parent", SOURCE_OBJ, FIELD_STR, oid_atom_parser },
507         { "numparent", SOURCE_OBJ, FIELD_ULONG },
508         { "object", SOURCE_OBJ },
509         { "type", SOURCE_OBJ },
510         { "tag", SOURCE_OBJ },
511         { "author", SOURCE_OBJ },
512         { "authorname", SOURCE_OBJ },
513         { "authoremail", SOURCE_OBJ, FIELD_STR, person_email_atom_parser },
514         { "authordate", SOURCE_OBJ, FIELD_TIME },
515         { "committer", SOURCE_OBJ },
516         { "committername", SOURCE_OBJ },
517         { "committeremail", SOURCE_OBJ, FIELD_STR, person_email_atom_parser },
518         { "committerdate", SOURCE_OBJ, FIELD_TIME },
519         { "tagger", SOURCE_OBJ },
520         { "taggername", SOURCE_OBJ },
521         { "taggeremail", SOURCE_OBJ, FIELD_STR, person_email_atom_parser },
522         { "taggerdate", SOURCE_OBJ, FIELD_TIME },
523         { "creator", SOURCE_OBJ },
524         { "creatordate", SOURCE_OBJ, FIELD_TIME },
525         { "subject", SOURCE_OBJ, FIELD_STR, subject_atom_parser },
526         { "body", SOURCE_OBJ, FIELD_STR, body_atom_parser },
527         { "trailers", SOURCE_OBJ, FIELD_STR, trailers_atom_parser },
528         { "contents", SOURCE_OBJ, FIELD_STR, contents_atom_parser },
529         { "upstream", SOURCE_NONE, FIELD_STR, remote_ref_atom_parser },
530         { "push", SOURCE_NONE, FIELD_STR, remote_ref_atom_parser },
531         { "symref", SOURCE_NONE, FIELD_STR, refname_atom_parser },
532         { "flag", SOURCE_NONE },
533         { "HEAD", SOURCE_NONE, FIELD_STR, head_atom_parser },
534         { "color", SOURCE_NONE, FIELD_STR, color_atom_parser },
535         { "worktreepath", SOURCE_NONE },
536         { "align", SOURCE_NONE, FIELD_STR, align_atom_parser },
537         { "end", SOURCE_NONE },
538         { "if", SOURCE_NONE, FIELD_STR, if_atom_parser },
539         { "then", SOURCE_NONE },
540         { "else", SOURCE_NONE },
541         /*
542          * Please update $__git_ref_fieldlist in git-completion.bash
543          * when you add new atoms
544          */
545 };
546
547 #define REF_FORMATTING_STATE_INIT  { 0, NULL }
548
549 struct ref_formatting_stack {
550         struct ref_formatting_stack *prev;
551         struct strbuf output;
552         void (*at_end)(struct ref_formatting_stack **stack);
553         void *at_end_data;
554 };
555
556 struct ref_formatting_state {
557         int quote_style;
558         struct ref_formatting_stack *stack;
559 };
560
561 struct atom_value {
562         const char *s;
563         int (*handler)(struct atom_value *atomv, struct ref_formatting_state *state,
564                        struct strbuf *err);
565         uintmax_t value; /* used for sorting when not FIELD_STR */
566         struct used_atom *atom;
567 };
568
569 /*
570  * Used to parse format string and sort specifiers
571  */
572 static int parse_ref_filter_atom(const struct ref_format *format,
573                                  const char *atom, const char *ep,
574                                  struct strbuf *err)
575 {
576         const char *sp;
577         const char *arg;
578         int i, at, atom_len;
579
580         sp = atom;
581         if (*sp == '*' && sp < ep)
582                 sp++; /* deref */
583         if (ep <= sp)
584                 return strbuf_addf_ret(err, -1, _("malformed field name: %.*s"),
585                                        (int)(ep-atom), atom);
586
587         /* Do we have the atom already used elsewhere? */
588         for (i = 0; i < used_atom_cnt; i++) {
589                 int len = strlen(used_atom[i].name);
590                 if (len == ep - atom && !memcmp(used_atom[i].name, atom, len))
591                         return i;
592         }
593
594         /*
595          * If the atom name has a colon, strip it and everything after
596          * it off - it specifies the format for this entry, and
597          * shouldn't be used for checking against the valid_atom
598          * table.
599          */
600         arg = memchr(sp, ':', ep - sp);
601         atom_len = (arg ? arg : ep) - sp;
602
603         /* Is the atom a valid one? */
604         for (i = 0; i < ARRAY_SIZE(valid_atom); i++) {
605                 int len = strlen(valid_atom[i].name);
606                 if (len == atom_len && !memcmp(valid_atom[i].name, sp, len))
607                         break;
608         }
609
610         if (ARRAY_SIZE(valid_atom) <= i)
611                 return strbuf_addf_ret(err, -1, _("unknown field name: %.*s"),
612                                        (int)(ep-atom), atom);
613         if (valid_atom[i].source != SOURCE_NONE && !have_git_dir())
614                 return strbuf_addf_ret(err, -1,
615                                        _("not a git repository, but the field '%.*s' requires access to object data"),
616                                        (int)(ep-atom), atom);
617
618         /* Add it in, including the deref prefix */
619         at = used_atom_cnt;
620         used_atom_cnt++;
621         REALLOC_ARRAY(used_atom, used_atom_cnt);
622         used_atom[at].name = xmemdupz(atom, ep - atom);
623         used_atom[at].type = valid_atom[i].cmp_type;
624         used_atom[at].source = valid_atom[i].source;
625         if (used_atom[at].source == SOURCE_OBJ) {
626                 if (*atom == '*')
627                         oi_deref.info.contentp = &oi_deref.content;
628                 else
629                         oi.info.contentp = &oi.content;
630         }
631         if (arg) {
632                 arg = used_atom[at].name + (arg - atom) + 1;
633                 if (!*arg) {
634                         /*
635                          * Treat empty sub-arguments list as NULL (i.e.,
636                          * "%(atom:)" is equivalent to "%(atom)").
637                          */
638                         arg = NULL;
639                 }
640         }
641         memset(&used_atom[at].u, 0, sizeof(used_atom[at].u));
642         if (valid_atom[i].parser && valid_atom[i].parser(format, &used_atom[at], arg, err))
643                 return -1;
644         if (*atom == '*')
645                 need_tagged = 1;
646         if (!strcmp(valid_atom[i].name, "symref"))
647                 need_symref = 1;
648         return at;
649 }
650
651 static void quote_formatting(struct strbuf *s, const char *str, int quote_style)
652 {
653         switch (quote_style) {
654         case QUOTE_NONE:
655                 strbuf_addstr(s, str);
656                 break;
657         case QUOTE_SHELL:
658                 sq_quote_buf(s, str);
659                 break;
660         case QUOTE_PERL:
661                 perl_quote_buf(s, str);
662                 break;
663         case QUOTE_PYTHON:
664                 python_quote_buf(s, str);
665                 break;
666         case QUOTE_TCL:
667                 tcl_quote_buf(s, str);
668                 break;
669         }
670 }
671
672 static int append_atom(struct atom_value *v, struct ref_formatting_state *state,
673                        struct strbuf *unused_err)
674 {
675         /*
676          * Quote formatting is only done when the stack has a single
677          * element. Otherwise quote formatting is done on the
678          * element's entire output strbuf when the %(end) atom is
679          * encountered.
680          */
681         if (!state->stack->prev)
682                 quote_formatting(&state->stack->output, v->s, state->quote_style);
683         else
684                 strbuf_addstr(&state->stack->output, v->s);
685         return 0;
686 }
687
688 static void push_stack_element(struct ref_formatting_stack **stack)
689 {
690         struct ref_formatting_stack *s = xcalloc(1, sizeof(struct ref_formatting_stack));
691
692         strbuf_init(&s->output, 0);
693         s->prev = *stack;
694         *stack = s;
695 }
696
697 static void pop_stack_element(struct ref_formatting_stack **stack)
698 {
699         struct ref_formatting_stack *current = *stack;
700         struct ref_formatting_stack *prev = current->prev;
701
702         if (prev)
703                 strbuf_addbuf(&prev->output, &current->output);
704         strbuf_release(&current->output);
705         free(current);
706         *stack = prev;
707 }
708
709 static void end_align_handler(struct ref_formatting_stack **stack)
710 {
711         struct ref_formatting_stack *cur = *stack;
712         struct align *align = (struct align *)cur->at_end_data;
713         struct strbuf s = STRBUF_INIT;
714
715         strbuf_utf8_align(&s, align->position, align->width, cur->output.buf);
716         strbuf_swap(&cur->output, &s);
717         strbuf_release(&s);
718 }
719
720 static int align_atom_handler(struct atom_value *atomv, struct ref_formatting_state *state,
721                               struct strbuf *unused_err)
722 {
723         struct ref_formatting_stack *new_stack;
724
725         push_stack_element(&state->stack);
726         new_stack = state->stack;
727         new_stack->at_end = end_align_handler;
728         new_stack->at_end_data = &atomv->atom->u.align;
729         return 0;
730 }
731
732 static void if_then_else_handler(struct ref_formatting_stack **stack)
733 {
734         struct ref_formatting_stack *cur = *stack;
735         struct ref_formatting_stack *prev = cur->prev;
736         struct if_then_else *if_then_else = (struct if_then_else *)cur->at_end_data;
737
738         if (!if_then_else->then_atom_seen)
739                 die(_("format: %%(if) atom used without a %%(then) atom"));
740
741         if (if_then_else->else_atom_seen) {
742                 /*
743                  * There is an %(else) atom: we need to drop one state from the
744                  * stack, either the %(else) branch if the condition is satisfied, or
745                  * the %(then) branch if it isn't.
746                  */
747                 if (if_then_else->condition_satisfied) {
748                         strbuf_reset(&cur->output);
749                         pop_stack_element(&cur);
750                 } else {
751                         strbuf_swap(&cur->output, &prev->output);
752                         strbuf_reset(&cur->output);
753                         pop_stack_element(&cur);
754                 }
755         } else if (!if_then_else->condition_satisfied) {
756                 /*
757                  * No %(else) atom: just drop the %(then) branch if the
758                  * condition is not satisfied.
759                  */
760                 strbuf_reset(&cur->output);
761         }
762
763         *stack = cur;
764         free(if_then_else);
765 }
766
767 static int if_atom_handler(struct atom_value *atomv, struct ref_formatting_state *state,
768                            struct strbuf *unused_err)
769 {
770         struct ref_formatting_stack *new_stack;
771         struct if_then_else *if_then_else = xcalloc(sizeof(struct if_then_else), 1);
772
773         if_then_else->str = atomv->atom->u.if_then_else.str;
774         if_then_else->cmp_status = atomv->atom->u.if_then_else.cmp_status;
775
776         push_stack_element(&state->stack);
777         new_stack = state->stack;
778         new_stack->at_end = if_then_else_handler;
779         new_stack->at_end_data = if_then_else;
780         return 0;
781 }
782
783 static int is_empty(const char *s)
784 {
785         while (*s != '\0') {
786                 if (!isspace(*s))
787                         return 0;
788                 s++;
789         }
790         return 1;
791 }
792
793 static int then_atom_handler(struct atom_value *atomv, struct ref_formatting_state *state,
794                              struct strbuf *err)
795 {
796         struct ref_formatting_stack *cur = state->stack;
797         struct if_then_else *if_then_else = NULL;
798
799         if (cur->at_end == if_then_else_handler)
800                 if_then_else = (struct if_then_else *)cur->at_end_data;
801         if (!if_then_else)
802                 return strbuf_addf_ret(err, -1, _("format: %%(then) atom used without an %%(if) atom"));
803         if (if_then_else->then_atom_seen)
804                 return strbuf_addf_ret(err, -1, _("format: %%(then) atom used more than once"));
805         if (if_then_else->else_atom_seen)
806                 return strbuf_addf_ret(err, -1, _("format: %%(then) atom used after %%(else)"));
807         if_then_else->then_atom_seen = 1;
808         /*
809          * If the 'equals' or 'notequals' attribute is used then
810          * perform the required comparison. If not, only non-empty
811          * strings satisfy the 'if' condition.
812          */
813         if (if_then_else->cmp_status == COMPARE_EQUAL) {
814                 if (!strcmp(if_then_else->str, cur->output.buf))
815                         if_then_else->condition_satisfied = 1;
816         } else if (if_then_else->cmp_status == COMPARE_UNEQUAL) {
817                 if (strcmp(if_then_else->str, cur->output.buf))
818                         if_then_else->condition_satisfied = 1;
819         } else if (cur->output.len && !is_empty(cur->output.buf))
820                 if_then_else->condition_satisfied = 1;
821         strbuf_reset(&cur->output);
822         return 0;
823 }
824
825 static int else_atom_handler(struct atom_value *atomv, struct ref_formatting_state *state,
826                              struct strbuf *err)
827 {
828         struct ref_formatting_stack *prev = state->stack;
829         struct if_then_else *if_then_else = NULL;
830
831         if (prev->at_end == if_then_else_handler)
832                 if_then_else = (struct if_then_else *)prev->at_end_data;
833         if (!if_then_else)
834                 return strbuf_addf_ret(err, -1, _("format: %%(else) atom used without an %%(if) atom"));
835         if (!if_then_else->then_atom_seen)
836                 return strbuf_addf_ret(err, -1, _("format: %%(else) atom used without a %%(then) atom"));
837         if (if_then_else->else_atom_seen)
838                 return strbuf_addf_ret(err, -1, _("format: %%(else) atom used more than once"));
839         if_then_else->else_atom_seen = 1;
840         push_stack_element(&state->stack);
841         state->stack->at_end_data = prev->at_end_data;
842         state->stack->at_end = prev->at_end;
843         return 0;
844 }
845
846 static int end_atom_handler(struct atom_value *atomv, struct ref_formatting_state *state,
847                             struct strbuf *err)
848 {
849         struct ref_formatting_stack *current = state->stack;
850         struct strbuf s = STRBUF_INIT;
851
852         if (!current->at_end)
853                 return strbuf_addf_ret(err, -1, _("format: %%(end) atom used without corresponding atom"));
854         current->at_end(&state->stack);
855
856         /*  Stack may have been popped within at_end(), hence reset the current pointer */
857         current = state->stack;
858
859         /*
860          * Perform quote formatting when the stack element is that of
861          * a supporting atom. If nested then perform quote formatting
862          * only on the topmost supporting atom.
863          */
864         if (!current->prev->prev) {
865                 quote_formatting(&s, current->output.buf, state->quote_style);
866                 strbuf_swap(&current->output, &s);
867         }
868         strbuf_release(&s);
869         pop_stack_element(&state->stack);
870         return 0;
871 }
872
873 /*
874  * In a format string, find the next occurrence of %(atom).
875  */
876 static const char *find_next(const char *cp)
877 {
878         while (*cp) {
879                 if (*cp == '%') {
880                         /*
881                          * %( is the start of an atom;
882                          * %% is a quoted per-cent.
883                          */
884                         if (cp[1] == '(')
885                                 return cp;
886                         else if (cp[1] == '%')
887                                 cp++; /* skip over two % */
888                         /* otherwise this is a singleton, literal % */
889                 }
890                 cp++;
891         }
892         return NULL;
893 }
894
895 /*
896  * Make sure the format string is well formed, and parse out
897  * the used atoms.
898  */
899 int verify_ref_format(struct ref_format *format)
900 {
901         const char *cp, *sp;
902
903         format->need_color_reset_at_eol = 0;
904         for (cp = format->format; *cp && (sp = find_next(cp)); ) {
905                 struct strbuf err = STRBUF_INIT;
906                 const char *color, *ep = strchr(sp, ')');
907                 int at;
908
909                 if (!ep)
910                         return error(_("malformed format string %s"), sp);
911                 /* sp points at "%(" and ep points at the closing ")" */
912                 at = parse_ref_filter_atom(format, sp + 2, ep, &err);
913                 if (at < 0)
914                         die("%s", err.buf);
915                 cp = ep + 1;
916
917                 if (skip_prefix(used_atom[at].name, "color:", &color))
918                         format->need_color_reset_at_eol = !!strcmp(color, "reset");
919                 strbuf_release(&err);
920         }
921         if (format->need_color_reset_at_eol && !want_color(format->use_color))
922                 format->need_color_reset_at_eol = 0;
923         return 0;
924 }
925
926 static const char *do_grab_oid(const char *field, const struct object_id *oid,
927                                struct used_atom *atom)
928 {
929         switch (atom->u.oid.option) {
930         case O_FULL:
931                 return oid_to_hex(oid);
932         case O_LENGTH:
933                 return find_unique_abbrev(oid, atom->u.oid.length);
934         case O_SHORT:
935                 return find_unique_abbrev(oid, DEFAULT_ABBREV);
936         default:
937                 BUG("unknown %%(%s) option", field);
938         }
939 }
940
941 static int grab_oid(const char *name, const char *field, const struct object_id *oid,
942                     struct atom_value *v, struct used_atom *atom)
943 {
944         if (starts_with(name, field)) {
945                 v->s = xstrdup(do_grab_oid(field, oid, atom));
946                 return 1;
947         }
948         return 0;
949 }
950
951 /* See grab_values */
952 static void grab_common_values(struct atom_value *val, int deref, struct expand_data *oi)
953 {
954         int i;
955
956         for (i = 0; i < used_atom_cnt; i++) {
957                 const char *name = used_atom[i].name;
958                 struct atom_value *v = &val[i];
959                 if (!!deref != (*name == '*'))
960                         continue;
961                 if (deref)
962                         name++;
963                 if (!strcmp(name, "objecttype"))
964                         v->s = xstrdup(type_name(oi->type));
965                 else if (!strcmp(name, "objectsize:disk")) {
966                         v->value = oi->disk_size;
967                         v->s = xstrfmt("%"PRIuMAX, (uintmax_t)oi->disk_size);
968                 } else if (!strcmp(name, "objectsize")) {
969                         v->value = oi->size;
970                         v->s = xstrfmt("%"PRIuMAX , (uintmax_t)oi->size);
971                 } else if (!strcmp(name, "deltabase"))
972                         v->s = xstrdup(oid_to_hex(&oi->delta_base_oid));
973                 else if (deref)
974                         grab_oid(name, "objectname", &oi->oid, v, &used_atom[i]);
975         }
976 }
977
978 /* See grab_values */
979 static void grab_tag_values(struct atom_value *val, int deref, struct object *obj)
980 {
981         int i;
982         struct tag *tag = (struct tag *) obj;
983
984         for (i = 0; i < used_atom_cnt; i++) {
985                 const char *name = used_atom[i].name;
986                 struct atom_value *v = &val[i];
987                 if (!!deref != (*name == '*'))
988                         continue;
989                 if (deref)
990                         name++;
991                 if (!strcmp(name, "tag"))
992                         v->s = xstrdup(tag->tag);
993                 else if (!strcmp(name, "type") && tag->tagged)
994                         v->s = xstrdup(type_name(tag->tagged->type));
995                 else if (!strcmp(name, "object") && tag->tagged)
996                         v->s = xstrdup(oid_to_hex(&tag->tagged->oid));
997         }
998 }
999
1000 /* See grab_values */
1001 static void grab_commit_values(struct atom_value *val, int deref, struct object *obj)
1002 {
1003         int i;
1004         struct commit *commit = (struct commit *) obj;
1005
1006         for (i = 0; i < used_atom_cnt; i++) {
1007                 const char *name = used_atom[i].name;
1008                 struct atom_value *v = &val[i];
1009                 if (!!deref != (*name == '*'))
1010                         continue;
1011                 if (deref)
1012                         name++;
1013                 if (grab_oid(name, "tree", get_commit_tree_oid(commit), v, &used_atom[i]))
1014                         continue;
1015                 if (!strcmp(name, "numparent")) {
1016                         v->value = commit_list_count(commit->parents);
1017                         v->s = xstrfmt("%lu", (unsigned long)v->value);
1018                 }
1019                 else if (starts_with(name, "parent")) {
1020                         struct commit_list *parents;
1021                         struct strbuf s = STRBUF_INIT;
1022                         for (parents = commit->parents; parents; parents = parents->next) {
1023                                 struct object_id *oid = &parents->item->object.oid;
1024                                 if (parents != commit->parents)
1025                                         strbuf_addch(&s, ' ');
1026                                 strbuf_addstr(&s, do_grab_oid("parent", oid, &used_atom[i]));
1027                         }
1028                         v->s = strbuf_detach(&s, NULL);
1029                 }
1030         }
1031 }
1032
1033 static const char *find_wholine(const char *who, int wholen, const char *buf)
1034 {
1035         const char *eol;
1036         while (*buf) {
1037                 if (!strncmp(buf, who, wholen) &&
1038                     buf[wholen] == ' ')
1039                         return buf + wholen + 1;
1040                 eol = strchr(buf, '\n');
1041                 if (!eol)
1042                         return "";
1043                 eol++;
1044                 if (*eol == '\n')
1045                         return ""; /* end of header */
1046                 buf = eol;
1047         }
1048         return "";
1049 }
1050
1051 static const char *copy_line(const char *buf)
1052 {
1053         const char *eol = strchrnul(buf, '\n');
1054         return xmemdupz(buf, eol - buf);
1055 }
1056
1057 static const char *copy_name(const char *buf)
1058 {
1059         const char *cp;
1060         for (cp = buf; *cp && *cp != '\n'; cp++) {
1061                 if (!strncmp(cp, " <", 2))
1062                         return xmemdupz(buf, cp - buf);
1063         }
1064         return xstrdup("");
1065 }
1066
1067 static const char *copy_email(const char *buf, struct used_atom *atom)
1068 {
1069         const char *email = strchr(buf, '<');
1070         const char *eoemail;
1071         if (!email)
1072                 return xstrdup("");
1073         switch (atom->u.email_option.option) {
1074         case EO_RAW:
1075                 eoemail = strchr(email, '>');
1076                 if (eoemail)
1077                         eoemail++;
1078                 break;
1079         case EO_TRIM:
1080                 email++;
1081                 eoemail = strchr(email, '>');
1082                 break;
1083         case EO_LOCALPART:
1084                 email++;
1085                 eoemail = strchr(email, '@');
1086                 if (!eoemail)
1087                         eoemail = strchr(email, '>');
1088                 break;
1089         default:
1090                 BUG("unknown email option");
1091         }
1092
1093         if (!eoemail)
1094                 return xstrdup("");
1095         return xmemdupz(email, eoemail - email);
1096 }
1097
1098 static char *copy_subject(const char *buf, unsigned long len)
1099 {
1100         struct strbuf sb = STRBUF_INIT;
1101         int i;
1102
1103         for (i = 0; i < len; i++) {
1104                 if (buf[i] == '\r' && i + 1 < len && buf[i + 1] == '\n')
1105                         continue; /* ignore CR in CRLF */
1106
1107                 if (buf[i] == '\n')
1108                         strbuf_addch(&sb, ' ');
1109                 else
1110                         strbuf_addch(&sb, buf[i]);
1111         }
1112         return strbuf_detach(&sb, NULL);
1113 }
1114
1115 static void grab_date(const char *buf, struct atom_value *v, const char *atomname)
1116 {
1117         const char *eoemail = strstr(buf, "> ");
1118         char *zone;
1119         timestamp_t timestamp;
1120         long tz;
1121         struct date_mode date_mode = { DATE_NORMAL };
1122         const char *formatp;
1123
1124         /*
1125          * We got here because atomname ends in "date" or "date<something>";
1126          * it's not possible that <something> is not ":<format>" because
1127          * parse_ref_filter_atom() wouldn't have allowed it, so we can assume that no
1128          * ":" means no format is specified, and use the default.
1129          */
1130         formatp = strchr(atomname, ':');
1131         if (formatp != NULL) {
1132                 formatp++;
1133                 parse_date_format(formatp, &date_mode);
1134         }
1135
1136         if (!eoemail)
1137                 goto bad;
1138         timestamp = parse_timestamp(eoemail + 2, &zone, 10);
1139         if (timestamp == TIME_MAX)
1140                 goto bad;
1141         tz = strtol(zone, NULL, 10);
1142         if ((tz == LONG_MIN || tz == LONG_MAX) && errno == ERANGE)
1143                 goto bad;
1144         v->s = xstrdup(show_date(timestamp, tz, &date_mode));
1145         v->value = timestamp;
1146         return;
1147  bad:
1148         v->s = xstrdup("");
1149         v->value = 0;
1150 }
1151
1152 /* See grab_values */
1153 static void grab_person(const char *who, struct atom_value *val, int deref, void *buf)
1154 {
1155         int i;
1156         int wholen = strlen(who);
1157         const char *wholine = NULL;
1158
1159         for (i = 0; i < used_atom_cnt; i++) {
1160                 const char *name = used_atom[i].name;
1161                 struct atom_value *v = &val[i];
1162                 if (!!deref != (*name == '*'))
1163                         continue;
1164                 if (deref)
1165                         name++;
1166                 if (strncmp(who, name, wholen))
1167                         continue;
1168                 if (name[wholen] != 0 &&
1169                     strcmp(name + wholen, "name") &&
1170                     !starts_with(name + wholen, "email") &&
1171                     !starts_with(name + wholen, "date"))
1172                         continue;
1173                 if (!wholine)
1174                         wholine = find_wholine(who, wholen, buf);
1175                 if (!wholine)
1176                         return; /* no point looking for it */
1177                 if (name[wholen] == 0)
1178                         v->s = copy_line(wholine);
1179                 else if (!strcmp(name + wholen, "name"))
1180                         v->s = copy_name(wholine);
1181                 else if (starts_with(name + wholen, "email"))
1182                         v->s = copy_email(wholine, &used_atom[i]);
1183                 else if (starts_with(name + wholen, "date"))
1184                         grab_date(wholine, v, name);
1185         }
1186
1187         /*
1188          * For a tag or a commit object, if "creator" or "creatordate" is
1189          * requested, do something special.
1190          */
1191         if (strcmp(who, "tagger") && strcmp(who, "committer"))
1192                 return; /* "author" for commit object is not wanted */
1193         if (!wholine)
1194                 wholine = find_wholine(who, wholen, buf);
1195         if (!wholine)
1196                 return;
1197         for (i = 0; i < used_atom_cnt; i++) {
1198                 const char *name = used_atom[i].name;
1199                 struct atom_value *v = &val[i];
1200                 if (!!deref != (*name == '*'))
1201                         continue;
1202                 if (deref)
1203                         name++;
1204
1205                 if (starts_with(name, "creatordate"))
1206                         grab_date(wholine, v, name);
1207                 else if (!strcmp(name, "creator"))
1208                         v->s = copy_line(wholine);
1209         }
1210 }
1211
1212 static void find_subpos(const char *buf,
1213                         const char **sub, unsigned long *sublen,
1214                         const char **body, unsigned long *bodylen,
1215                         unsigned long *nonsiglen,
1216                         const char **sig, unsigned long *siglen)
1217 {
1218         const char *eol;
1219         /* skip past header until we hit empty line */
1220         while (*buf && *buf != '\n') {
1221                 eol = strchrnul(buf, '\n');
1222                 if (*eol)
1223                         eol++;
1224                 buf = eol;
1225         }
1226         /* skip any empty lines */
1227         while (*buf == '\n')
1228                 buf++;
1229
1230         /* parse signature first; we might not even have a subject line */
1231         *sig = buf + parse_signature(buf, strlen(buf));
1232         *siglen = strlen(*sig);
1233
1234         /* subject is first non-empty line */
1235         *sub = buf;
1236         /* subject goes to first empty line before signature begins */
1237         if ((eol = strstr(*sub, "\n\n"))) {
1238                 eol = eol < *sig ? eol : *sig;
1239         /* check if message uses CRLF */
1240         } else if (! (eol = strstr(*sub, "\r\n\r\n"))) {
1241                 /* treat whole message as subject */
1242                 eol = strrchr(*sub, '\0');
1243         }
1244         buf = eol;
1245         *sublen = buf - *sub;
1246         /* drop trailing newline, if present */
1247         while (*sublen && ((*sub)[*sublen - 1] == '\n' ||
1248                            (*sub)[*sublen - 1] == '\r'))
1249                 *sublen -= 1;
1250
1251         /* skip any empty lines */
1252         while (*buf == '\n' || *buf == '\r')
1253                 buf++;
1254         *body = buf;
1255         *bodylen = strlen(buf);
1256         *nonsiglen = *sig - buf;
1257 }
1258
1259 /*
1260  * If 'lines' is greater than 0, append that many lines from the given
1261  * 'buf' of length 'size' to the given strbuf.
1262  */
1263 static void append_lines(struct strbuf *out, const char *buf, unsigned long size, int lines)
1264 {
1265         int i;
1266         const char *sp, *eol;
1267         size_t len;
1268
1269         sp = buf;
1270
1271         for (i = 0; i < lines && sp < buf + size; i++) {
1272                 if (i)
1273                         strbuf_addstr(out, "\n    ");
1274                 eol = memchr(sp, '\n', size - (sp - buf));
1275                 len = eol ? eol - sp : size - (sp - buf);
1276                 strbuf_add(out, sp, len);
1277                 if (!eol)
1278                         break;
1279                 sp = eol + 1;
1280         }
1281 }
1282
1283 /* See grab_values */
1284 static void grab_sub_body_contents(struct atom_value *val, int deref, void *buf)
1285 {
1286         int i;
1287         const char *subpos = NULL, *bodypos = NULL, *sigpos = NULL;
1288         unsigned long sublen = 0, bodylen = 0, nonsiglen = 0, siglen = 0;
1289
1290         for (i = 0; i < used_atom_cnt; i++) {
1291                 struct used_atom *atom = &used_atom[i];
1292                 const char *name = atom->name;
1293                 struct atom_value *v = &val[i];
1294                 if (!!deref != (*name == '*'))
1295                         continue;
1296                 if (deref)
1297                         name++;
1298                 if (strcmp(name, "body") &&
1299                     !starts_with(name, "subject") &&
1300                     !starts_with(name, "trailers") &&
1301                     !starts_with(name, "contents"))
1302                         continue;
1303                 if (!subpos)
1304                         find_subpos(buf,
1305                                     &subpos, &sublen,
1306                                     &bodypos, &bodylen, &nonsiglen,
1307                                     &sigpos, &siglen);
1308
1309                 if (atom->u.contents.option == C_SUB)
1310                         v->s = copy_subject(subpos, sublen);
1311                 else if (atom->u.contents.option == C_SUB_SANITIZE) {
1312                         struct strbuf sb = STRBUF_INIT;
1313                         format_sanitized_subject(&sb, subpos, sublen);
1314                         v->s = strbuf_detach(&sb, NULL);
1315                 } else if (atom->u.contents.option == C_BODY_DEP)
1316                         v->s = xmemdupz(bodypos, bodylen);
1317                 else if (atom->u.contents.option == C_LENGTH)
1318                         v->s = xstrfmt("%"PRIuMAX, (uintmax_t)strlen(subpos));
1319                 else if (atom->u.contents.option == C_BODY)
1320                         v->s = xmemdupz(bodypos, nonsiglen);
1321                 else if (atom->u.contents.option == C_SIG)
1322                         v->s = xmemdupz(sigpos, siglen);
1323                 else if (atom->u.contents.option == C_LINES) {
1324                         struct strbuf s = STRBUF_INIT;
1325                         const char *contents_end = bodylen + bodypos - siglen;
1326
1327                         /*  Size is the length of the message after removing the signature */
1328                         append_lines(&s, subpos, contents_end - subpos, atom->u.contents.nlines);
1329                         v->s = strbuf_detach(&s, NULL);
1330                 } else if (atom->u.contents.option == C_TRAILERS) {
1331                         struct strbuf s = STRBUF_INIT;
1332
1333                         /* Format the trailer info according to the trailer_opts given */
1334                         format_trailers_from_commit(&s, subpos, &atom->u.contents.trailer_opts);
1335
1336                         v->s = strbuf_detach(&s, NULL);
1337                 } else if (atom->u.contents.option == C_BARE)
1338                         v->s = xstrdup(subpos);
1339         }
1340 }
1341
1342 /*
1343  * We want to have empty print-string for field requests
1344  * that do not apply (e.g. "authordate" for a tag object)
1345  */
1346 static void fill_missing_values(struct atom_value *val)
1347 {
1348         int i;
1349         for (i = 0; i < used_atom_cnt; i++) {
1350                 struct atom_value *v = &val[i];
1351                 if (v->s == NULL)
1352                         v->s = xstrdup("");
1353         }
1354 }
1355
1356 /*
1357  * val is a list of atom_value to hold returned values.  Extract
1358  * the values for atoms in used_atom array out of (obj, buf, sz).
1359  * when deref is false, (obj, buf, sz) is the object that is
1360  * pointed at by the ref itself; otherwise it is the object the
1361  * ref (which is a tag) refers to.
1362  */
1363 static void grab_values(struct atom_value *val, int deref, struct object *obj, void *buf)
1364 {
1365         switch (obj->type) {
1366         case OBJ_TAG:
1367                 grab_tag_values(val, deref, obj);
1368                 grab_sub_body_contents(val, deref, buf);
1369                 grab_person("tagger", val, deref, buf);
1370                 break;
1371         case OBJ_COMMIT:
1372                 grab_commit_values(val, deref, obj);
1373                 grab_sub_body_contents(val, deref, buf);
1374                 grab_person("author", val, deref, buf);
1375                 grab_person("committer", val, deref, buf);
1376                 break;
1377         case OBJ_TREE:
1378                 /* grab_tree_values(val, deref, obj, buf, sz); */
1379                 break;
1380         case OBJ_BLOB:
1381                 /* grab_blob_values(val, deref, obj, buf, sz); */
1382                 break;
1383         default:
1384                 die("Eh?  Object of type %d?", obj->type);
1385         }
1386 }
1387
1388 static inline char *copy_advance(char *dst, const char *src)
1389 {
1390         while (*src)
1391                 *dst++ = *src++;
1392         return dst;
1393 }
1394
1395 static const char *lstrip_ref_components(const char *refname, int len)
1396 {
1397         long remaining = len;
1398         const char *start = xstrdup(refname);
1399         const char *to_free = start;
1400
1401         if (len < 0) {
1402                 int i;
1403                 const char *p = refname;
1404
1405                 /* Find total no of '/' separated path-components */
1406                 for (i = 0; p[i]; p[i] == '/' ? i++ : *p++)
1407                         ;
1408                 /*
1409                  * The number of components we need to strip is now
1410                  * the total minus the components to be left (Plus one
1411                  * because we count the number of '/', but the number
1412                  * of components is one more than the no of '/').
1413                  */
1414                 remaining = i + len + 1;
1415         }
1416
1417         while (remaining > 0) {
1418                 switch (*start++) {
1419                 case '\0':
1420                         free((char *)to_free);
1421                         return xstrdup("");
1422                 case '/':
1423                         remaining--;
1424                         break;
1425                 }
1426         }
1427
1428         start = xstrdup(start);
1429         free((char *)to_free);
1430         return start;
1431 }
1432
1433 static const char *rstrip_ref_components(const char *refname, int len)
1434 {
1435         long remaining = len;
1436         const char *start = xstrdup(refname);
1437         const char *to_free = start;
1438
1439         if (len < 0) {
1440                 int i;
1441                 const char *p = refname;
1442
1443                 /* Find total no of '/' separated path-components */
1444                 for (i = 0; p[i]; p[i] == '/' ? i++ : *p++)
1445                         ;
1446                 /*
1447                  * The number of components we need to strip is now
1448                  * the total minus the components to be left (Plus one
1449                  * because we count the number of '/', but the number
1450                  * of components is one more than the no of '/').
1451                  */
1452                 remaining = i + len + 1;
1453         }
1454
1455         while (remaining-- > 0) {
1456                 char *p = strrchr(start, '/');
1457                 if (p == NULL) {
1458                         free((char *)to_free);
1459                         return xstrdup("");
1460                 } else
1461                         p[0] = '\0';
1462         }
1463         return start;
1464 }
1465
1466 static const char *show_ref(struct refname_atom *atom, const char *refname)
1467 {
1468         if (atom->option == R_SHORT)
1469                 return shorten_unambiguous_ref(refname, warn_ambiguous_refs);
1470         else if (atom->option == R_LSTRIP)
1471                 return lstrip_ref_components(refname, atom->lstrip);
1472         else if (atom->option == R_RSTRIP)
1473                 return rstrip_ref_components(refname, atom->rstrip);
1474         else
1475                 return xstrdup(refname);
1476 }
1477
1478 static void fill_remote_ref_details(struct used_atom *atom, const char *refname,
1479                                     struct branch *branch, const char **s)
1480 {
1481         int num_ours, num_theirs;
1482         if (atom->u.remote_ref.option == RR_REF)
1483                 *s = show_ref(&atom->u.remote_ref.refname, refname);
1484         else if (atom->u.remote_ref.option == RR_TRACK) {
1485                 if (stat_tracking_info(branch, &num_ours, &num_theirs,
1486                                        NULL, atom->u.remote_ref.push,
1487                                        AHEAD_BEHIND_FULL) < 0) {
1488                         *s = xstrdup(msgs.gone);
1489                 } else if (!num_ours && !num_theirs)
1490                         *s = xstrdup("");
1491                 else if (!num_ours)
1492                         *s = xstrfmt(msgs.behind, num_theirs);
1493                 else if (!num_theirs)
1494                         *s = xstrfmt(msgs.ahead, num_ours);
1495                 else
1496                         *s = xstrfmt(msgs.ahead_behind,
1497                                      num_ours, num_theirs);
1498                 if (!atom->u.remote_ref.nobracket && *s[0]) {
1499                         const char *to_free = *s;
1500                         *s = xstrfmt("[%s]", *s);
1501                         free((void *)to_free);
1502                 }
1503         } else if (atom->u.remote_ref.option == RR_TRACKSHORT) {
1504                 if (stat_tracking_info(branch, &num_ours, &num_theirs,
1505                                        NULL, atom->u.remote_ref.push,
1506                                        AHEAD_BEHIND_FULL) < 0) {
1507                         *s = xstrdup("");
1508                         return;
1509                 }
1510                 if (!num_ours && !num_theirs)
1511                         *s = xstrdup("=");
1512                 else if (!num_ours)
1513                         *s = xstrdup("<");
1514                 else if (!num_theirs)
1515                         *s = xstrdup(">");
1516                 else
1517                         *s = xstrdup("<>");
1518         } else if (atom->u.remote_ref.option == RR_REMOTE_NAME) {
1519                 int explicit;
1520                 const char *remote = atom->u.remote_ref.push ?
1521                         pushremote_for_branch(branch, &explicit) :
1522                         remote_for_branch(branch, &explicit);
1523                 *s = xstrdup(explicit ? remote : "");
1524         } else if (atom->u.remote_ref.option == RR_REMOTE_REF) {
1525                 const char *merge;
1526
1527                 merge = remote_ref_for_branch(branch, atom->u.remote_ref.push);
1528                 *s = xstrdup(merge ? merge : "");
1529         } else
1530                 BUG("unhandled RR_* enum");
1531 }
1532
1533 char *get_head_description(void)
1534 {
1535         struct strbuf desc = STRBUF_INIT;
1536         struct wt_status_state state;
1537         memset(&state, 0, sizeof(state));
1538         wt_status_get_state(the_repository, &state, 1);
1539         if (state.rebase_in_progress ||
1540             state.rebase_interactive_in_progress) {
1541                 if (state.branch)
1542                         strbuf_addf(&desc, _("(no branch, rebasing %s)"),
1543                                     state.branch);
1544                 else
1545                         strbuf_addf(&desc, _("(no branch, rebasing detached HEAD %s)"),
1546                                     state.detached_from);
1547         } else if (state.bisect_in_progress)
1548                 strbuf_addf(&desc, _("(no branch, bisect started on %s)"),
1549                             state.branch);
1550         else if (state.detached_from) {
1551                 if (state.detached_at)
1552                         strbuf_addf(&desc, _("(HEAD detached at %s)"),
1553                                 state.detached_from);
1554                 else
1555                         strbuf_addf(&desc, _("(HEAD detached from %s)"),
1556                                 state.detached_from);
1557         } else
1558                 strbuf_addstr(&desc, _("(no branch)"));
1559
1560         return strbuf_detach(&desc, NULL);
1561 }
1562
1563 static const char *get_symref(struct used_atom *atom, struct ref_array_item *ref)
1564 {
1565         if (!ref->symref)
1566                 return xstrdup("");
1567         else
1568                 return show_ref(&atom->u.refname, ref->symref);
1569 }
1570
1571 static const char *get_refname(struct used_atom *atom, struct ref_array_item *ref)
1572 {
1573         if (ref->kind & FILTER_REFS_DETACHED_HEAD)
1574                 return get_head_description();
1575         return show_ref(&atom->u.refname, ref->refname);
1576 }
1577
1578 static int get_object(struct ref_array_item *ref, int deref, struct object **obj,
1579                       struct expand_data *oi, struct strbuf *err)
1580 {
1581         /* parse_object_buffer() will set eaten to 0 if free() will be needed */
1582         int eaten = 1;
1583         if (oi->info.contentp) {
1584                 /* We need to know that to use parse_object_buffer properly */
1585                 oi->info.sizep = &oi->size;
1586                 oi->info.typep = &oi->type;
1587         }
1588         if (oid_object_info_extended(the_repository, &oi->oid, &oi->info,
1589                                      OBJECT_INFO_LOOKUP_REPLACE))
1590                 return strbuf_addf_ret(err, -1, _("missing object %s for %s"),
1591                                        oid_to_hex(&oi->oid), ref->refname);
1592         if (oi->info.disk_sizep && oi->disk_size < 0)
1593                 BUG("Object size is less than zero.");
1594
1595         if (oi->info.contentp) {
1596                 *obj = parse_object_buffer(the_repository, &oi->oid, oi->type, oi->size, oi->content, &eaten);
1597                 if (!obj) {
1598                         if (!eaten)
1599                                 free(oi->content);
1600                         return strbuf_addf_ret(err, -1, _("parse_object_buffer failed on %s for %s"),
1601                                                oid_to_hex(&oi->oid), ref->refname);
1602                 }
1603                 grab_values(ref->value, deref, *obj, oi->content);
1604         }
1605
1606         grab_common_values(ref->value, deref, oi);
1607         if (!eaten)
1608                 free(oi->content);
1609         return 0;
1610 }
1611
1612 static void populate_worktree_map(struct hashmap *map, struct worktree **worktrees)
1613 {
1614         int i;
1615
1616         for (i = 0; worktrees[i]; i++) {
1617                 if (worktrees[i]->head_ref) {
1618                         struct ref_to_worktree_entry *entry;
1619                         entry = xmalloc(sizeof(*entry));
1620                         entry->wt = worktrees[i];
1621                         hashmap_entry_init(&entry->ent,
1622                                         strhash(worktrees[i]->head_ref));
1623
1624                         hashmap_add(map, &entry->ent);
1625                 }
1626         }
1627 }
1628
1629 static void lazy_init_worktree_map(void)
1630 {
1631         if (ref_to_worktree_map.worktrees)
1632                 return;
1633
1634         ref_to_worktree_map.worktrees = get_worktrees();
1635         hashmap_init(&(ref_to_worktree_map.map), ref_to_worktree_map_cmpfnc, NULL, 0);
1636         populate_worktree_map(&(ref_to_worktree_map.map), ref_to_worktree_map.worktrees);
1637 }
1638
1639 static char *get_worktree_path(const struct used_atom *atom, const struct ref_array_item *ref)
1640 {
1641         struct hashmap_entry entry, *e;
1642         struct ref_to_worktree_entry *lookup_result;
1643
1644         lazy_init_worktree_map();
1645
1646         hashmap_entry_init(&entry, strhash(ref->refname));
1647         e = hashmap_get(&(ref_to_worktree_map.map), &entry, ref->refname);
1648
1649         if (!e)
1650                 return xstrdup("");
1651
1652         lookup_result = container_of(e, struct ref_to_worktree_entry, ent);
1653
1654         return xstrdup(lookup_result->wt->path);
1655 }
1656
1657 /*
1658  * Parse the object referred by ref, and grab needed value.
1659  */
1660 static int populate_value(struct ref_array_item *ref, struct strbuf *err)
1661 {
1662         struct object *obj;
1663         int i;
1664         struct object_info empty = OBJECT_INFO_INIT;
1665
1666         ref->value = xcalloc(used_atom_cnt, sizeof(struct atom_value));
1667
1668         if (need_symref && (ref->flag & REF_ISSYMREF) && !ref->symref) {
1669                 ref->symref = resolve_refdup(ref->refname, RESOLVE_REF_READING,
1670                                              NULL, NULL);
1671                 if (!ref->symref)
1672                         ref->symref = xstrdup("");
1673         }
1674
1675         /* Fill in specials first */
1676         for (i = 0; i < used_atom_cnt; i++) {
1677                 struct used_atom *atom = &used_atom[i];
1678                 const char *name = used_atom[i].name;
1679                 struct atom_value *v = &ref->value[i];
1680                 int deref = 0;
1681                 const char *refname;
1682                 struct branch *branch = NULL;
1683
1684                 v->handler = append_atom;
1685                 v->atom = atom;
1686
1687                 if (*name == '*') {
1688                         deref = 1;
1689                         name++;
1690                 }
1691
1692                 if (starts_with(name, "refname"))
1693                         refname = get_refname(atom, ref);
1694                 else if (!strcmp(name, "worktreepath")) {
1695                         if (ref->kind == FILTER_REFS_BRANCHES)
1696                                 v->s = get_worktree_path(atom, ref);
1697                         else
1698                                 v->s = xstrdup("");
1699                         continue;
1700                 }
1701                 else if (starts_with(name, "symref"))
1702                         refname = get_symref(atom, ref);
1703                 else if (starts_with(name, "upstream")) {
1704                         const char *branch_name;
1705                         /* only local branches may have an upstream */
1706                         if (!skip_prefix(ref->refname, "refs/heads/",
1707                                          &branch_name)) {
1708                                 v->s = xstrdup("");
1709                                 continue;
1710                         }
1711                         branch = branch_get(branch_name);
1712
1713                         refname = branch_get_upstream(branch, NULL);
1714                         if (refname)
1715                                 fill_remote_ref_details(atom, refname, branch, &v->s);
1716                         else
1717                                 v->s = xstrdup("");
1718                         continue;
1719                 } else if (atom->u.remote_ref.push) {
1720                         const char *branch_name;
1721                         v->s = xstrdup("");
1722                         if (!skip_prefix(ref->refname, "refs/heads/",
1723                                          &branch_name))
1724                                 continue;
1725                         branch = branch_get(branch_name);
1726
1727                         if (atom->u.remote_ref.push_remote)
1728                                 refname = NULL;
1729                         else {
1730                                 refname = branch_get_push(branch, NULL);
1731                                 if (!refname)
1732                                         continue;
1733                         }
1734                         /* We will definitely re-init v->s on the next line. */
1735                         free((char *)v->s);
1736                         fill_remote_ref_details(atom, refname, branch, &v->s);
1737                         continue;
1738                 } else if (starts_with(name, "color:")) {
1739                         v->s = xstrdup(atom->u.color);
1740                         continue;
1741                 } else if (!strcmp(name, "flag")) {
1742                         char buf[256], *cp = buf;
1743                         if (ref->flag & REF_ISSYMREF)
1744                                 cp = copy_advance(cp, ",symref");
1745                         if (ref->flag & REF_ISPACKED)
1746                                 cp = copy_advance(cp, ",packed");
1747                         if (cp == buf)
1748                                 v->s = xstrdup("");
1749                         else {
1750                                 *cp = '\0';
1751                                 v->s = xstrdup(buf + 1);
1752                         }
1753                         continue;
1754                 } else if (!deref && grab_oid(name, "objectname", &ref->objectname, v, atom)) {
1755                         continue;
1756                 } else if (!strcmp(name, "HEAD")) {
1757                         if (atom->u.head && !strcmp(ref->refname, atom->u.head))
1758                                 v->s = xstrdup("*");
1759                         else
1760                                 v->s = xstrdup(" ");
1761                         continue;
1762                 } else if (starts_with(name, "align")) {
1763                         v->handler = align_atom_handler;
1764                         v->s = xstrdup("");
1765                         continue;
1766                 } else if (!strcmp(name, "end")) {
1767                         v->handler = end_atom_handler;
1768                         v->s = xstrdup("");
1769                         continue;
1770                 } else if (starts_with(name, "if")) {
1771                         const char *s;
1772                         if (skip_prefix(name, "if:", &s))
1773                                 v->s = xstrdup(s);
1774                         else
1775                                 v->s = xstrdup("");
1776                         v->handler = if_atom_handler;
1777                         continue;
1778                 } else if (!strcmp(name, "then")) {
1779                         v->handler = then_atom_handler;
1780                         v->s = xstrdup("");
1781                         continue;
1782                 } else if (!strcmp(name, "else")) {
1783                         v->handler = else_atom_handler;
1784                         v->s = xstrdup("");
1785                         continue;
1786                 } else
1787                         continue;
1788
1789                 if (!deref)
1790                         v->s = xstrdup(refname);
1791                 else
1792                         v->s = xstrfmt("%s^{}", refname);
1793                 free((char *)refname);
1794         }
1795
1796         for (i = 0; i < used_atom_cnt; i++) {
1797                 struct atom_value *v = &ref->value[i];
1798                 if (v->s == NULL && used_atom[i].source == SOURCE_NONE)
1799                         return strbuf_addf_ret(err, -1, _("missing object %s for %s"),
1800                                                oid_to_hex(&ref->objectname), ref->refname);
1801         }
1802
1803         if (need_tagged)
1804                 oi.info.contentp = &oi.content;
1805         if (!memcmp(&oi.info, &empty, sizeof(empty)) &&
1806             !memcmp(&oi_deref.info, &empty, sizeof(empty)))
1807                 return 0;
1808
1809
1810         oi.oid = ref->objectname;
1811         if (get_object(ref, 0, &obj, &oi, err))
1812                 return -1;
1813
1814         /*
1815          * If there is no atom that wants to know about tagged
1816          * object, we are done.
1817          */
1818         if (!need_tagged || (obj->type != OBJ_TAG))
1819                 return 0;
1820
1821         /*
1822          * If it is a tag object, see if we use a value that derefs
1823          * the object, and if we do grab the object it refers to.
1824          */
1825         oi_deref.oid = *get_tagged_oid((struct tag *)obj);
1826
1827         /*
1828          * NEEDSWORK: This derefs tag only once, which
1829          * is good to deal with chains of trust, but
1830          * is not consistent with what deref_tag() does
1831          * which peels the onion to the core.
1832          */
1833         return get_object(ref, 1, &obj, &oi_deref, err);
1834 }
1835
1836 /*
1837  * Given a ref, return the value for the atom.  This lazily gets value
1838  * out of the object by calling populate value.
1839  */
1840 static int get_ref_atom_value(struct ref_array_item *ref, int atom,
1841                               struct atom_value **v, struct strbuf *err)
1842 {
1843         if (!ref->value) {
1844                 if (populate_value(ref, err))
1845                         return -1;
1846                 fill_missing_values(ref->value);
1847         }
1848         *v = &ref->value[atom];
1849         return 0;
1850 }
1851
1852 /*
1853  * Return 1 if the refname matches one of the patterns, otherwise 0.
1854  * A pattern can be a literal prefix (e.g. a refname "refs/heads/master"
1855  * matches a pattern "refs/heads/mas") or a wildcard (e.g. the same ref
1856  * matches "refs/heads/mas*", too).
1857  */
1858 static int match_pattern(const struct ref_filter *filter, const char *refname)
1859 {
1860         const char **patterns = filter->name_patterns;
1861         unsigned flags = 0;
1862
1863         if (filter->ignore_case)
1864                 flags |= WM_CASEFOLD;
1865
1866         /*
1867          * When no '--format' option is given we need to skip the prefix
1868          * for matching refs of tags and branches.
1869          */
1870         (void)(skip_prefix(refname, "refs/tags/", &refname) ||
1871                skip_prefix(refname, "refs/heads/", &refname) ||
1872                skip_prefix(refname, "refs/remotes/", &refname) ||
1873                skip_prefix(refname, "refs/", &refname));
1874
1875         for (; *patterns; patterns++) {
1876                 if (!wildmatch(*patterns, refname, flags))
1877                         return 1;
1878         }
1879         return 0;
1880 }
1881
1882 /*
1883  * Return 1 if the refname matches one of the patterns, otherwise 0.
1884  * A pattern can be path prefix (e.g. a refname "refs/heads/master"
1885  * matches a pattern "refs/heads/" but not "refs/heads/m") or a
1886  * wildcard (e.g. the same ref matches "refs/heads/m*", too).
1887  */
1888 static int match_name_as_path(const struct ref_filter *filter, const char *refname)
1889 {
1890         const char **pattern = filter->name_patterns;
1891         int namelen = strlen(refname);
1892         unsigned flags = WM_PATHNAME;
1893
1894         if (filter->ignore_case)
1895                 flags |= WM_CASEFOLD;
1896
1897         for (; *pattern; pattern++) {
1898                 const char *p = *pattern;
1899                 int plen = strlen(p);
1900
1901                 if ((plen <= namelen) &&
1902                     !strncmp(refname, p, plen) &&
1903                     (refname[plen] == '\0' ||
1904                      refname[plen] == '/' ||
1905                      p[plen-1] == '/'))
1906                         return 1;
1907                 if (!wildmatch(p, refname, flags))
1908                         return 1;
1909         }
1910         return 0;
1911 }
1912
1913 /* Return 1 if the refname matches one of the patterns, otherwise 0. */
1914 static int filter_pattern_match(struct ref_filter *filter, const char *refname)
1915 {
1916         if (!*filter->name_patterns)
1917                 return 1; /* No pattern always matches */
1918         if (filter->match_as_path)
1919                 return match_name_as_path(filter, refname);
1920         return match_pattern(filter, refname);
1921 }
1922
1923 static int qsort_strcmp(const void *va, const void *vb)
1924 {
1925         const char *a = *(const char **)va;
1926         const char *b = *(const char **)vb;
1927
1928         return strcmp(a, b);
1929 }
1930
1931 static void find_longest_prefixes_1(struct string_list *out,
1932                                   struct strbuf *prefix,
1933                                   const char **patterns, size_t nr)
1934 {
1935         size_t i;
1936
1937         for (i = 0; i < nr; i++) {
1938                 char c = patterns[i][prefix->len];
1939                 if (!c || is_glob_special(c)) {
1940                         string_list_append(out, prefix->buf);
1941                         return;
1942                 }
1943         }
1944
1945         i = 0;
1946         while (i < nr) {
1947                 size_t end;
1948
1949                 /*
1950                 * Set "end" to the index of the element _after_ the last one
1951                 * in our group.
1952                 */
1953                 for (end = i + 1; end < nr; end++) {
1954                         if (patterns[i][prefix->len] != patterns[end][prefix->len])
1955                                 break;
1956                 }
1957
1958                 strbuf_addch(prefix, patterns[i][prefix->len]);
1959                 find_longest_prefixes_1(out, prefix, patterns + i, end - i);
1960                 strbuf_setlen(prefix, prefix->len - 1);
1961
1962                 i = end;
1963         }
1964 }
1965
1966 static void find_longest_prefixes(struct string_list *out,
1967                                   const char **patterns)
1968 {
1969         struct strvec sorted = STRVEC_INIT;
1970         struct strbuf prefix = STRBUF_INIT;
1971
1972         strvec_pushv(&sorted, patterns);
1973         QSORT(sorted.v, sorted.nr, qsort_strcmp);
1974
1975         find_longest_prefixes_1(out, &prefix, sorted.v, sorted.nr);
1976
1977         strvec_clear(&sorted);
1978         strbuf_release(&prefix);
1979 }
1980
1981 /*
1982  * This is the same as for_each_fullref_in(), but it tries to iterate
1983  * only over the patterns we'll care about. Note that it _doesn't_ do a full
1984  * pattern match, so the callback still has to match each ref individually.
1985  */
1986 static int for_each_fullref_in_pattern(struct ref_filter *filter,
1987                                        each_ref_fn cb,
1988                                        void *cb_data,
1989                                        int broken)
1990 {
1991         struct string_list prefixes = STRING_LIST_INIT_DUP;
1992         struct string_list_item *prefix;
1993         int ret;
1994
1995         if (!filter->match_as_path) {
1996                 /*
1997                  * in this case, the patterns are applied after
1998                  * prefixes like "refs/heads/" etc. are stripped off,
1999                  * so we have to look at everything:
2000                  */
2001                 return for_each_fullref_in("", cb, cb_data, broken);
2002         }
2003
2004         if (filter->ignore_case) {
2005                 /*
2006                  * we can't handle case-insensitive comparisons,
2007                  * so just return everything and let the caller
2008                  * sort it out.
2009                  */
2010                 return for_each_fullref_in("", cb, cb_data, broken);
2011         }
2012
2013         if (!filter->name_patterns[0]) {
2014                 /* no patterns; we have to look at everything */
2015                 return for_each_fullref_in("", cb, cb_data, broken);
2016         }
2017
2018         find_longest_prefixes(&prefixes, filter->name_patterns);
2019
2020         for_each_string_list_item(prefix, &prefixes) {
2021                 ret = for_each_fullref_in(prefix->string, cb, cb_data, broken);
2022                 if (ret)
2023                         break;
2024         }
2025
2026         string_list_clear(&prefixes, 0);
2027         return ret;
2028 }
2029
2030 /*
2031  * Given a ref (oid, refname), check if the ref belongs to the array
2032  * of oids. If the given ref is a tag, check if the given tag points
2033  * at one of the oids in the given oid array.
2034  * NEEDSWORK:
2035  * 1. Only a single level of indirection is obtained, we might want to
2036  * change this to account for multiple levels (e.g. annotated tags
2037  * pointing to annotated tags pointing to a commit.)
2038  * 2. As the refs are cached we might know what refname peels to without
2039  * the need to parse the object via parse_object(). peel_ref() might be a
2040  * more efficient alternative to obtain the pointee.
2041  */
2042 static const struct object_id *match_points_at(struct oid_array *points_at,
2043                                                const struct object_id *oid,
2044                                                const char *refname)
2045 {
2046         const struct object_id *tagged_oid = NULL;
2047         struct object *obj;
2048
2049         if (oid_array_lookup(points_at, oid) >= 0)
2050                 return oid;
2051         obj = parse_object(the_repository, oid);
2052         if (!obj)
2053                 die(_("malformed object at '%s'"), refname);
2054         if (obj->type == OBJ_TAG)
2055                 tagged_oid = get_tagged_oid((struct tag *)obj);
2056         if (tagged_oid && oid_array_lookup(points_at, tagged_oid) >= 0)
2057                 return tagged_oid;
2058         return NULL;
2059 }
2060
2061 /*
2062  * Allocate space for a new ref_array_item and copy the name and oid to it.
2063  *
2064  * Callers can then fill in other struct members at their leisure.
2065  */
2066 static struct ref_array_item *new_ref_array_item(const char *refname,
2067                                                  const struct object_id *oid)
2068 {
2069         struct ref_array_item *ref;
2070
2071         FLEX_ALLOC_STR(ref, refname, refname);
2072         oidcpy(&ref->objectname, oid);
2073
2074         return ref;
2075 }
2076
2077 struct ref_array_item *ref_array_push(struct ref_array *array,
2078                                       const char *refname,
2079                                       const struct object_id *oid)
2080 {
2081         struct ref_array_item *ref = new_ref_array_item(refname, oid);
2082
2083         ALLOC_GROW(array->items, array->nr + 1, array->alloc);
2084         array->items[array->nr++] = ref;
2085
2086         return ref;
2087 }
2088
2089 static int ref_kind_from_refname(const char *refname)
2090 {
2091         unsigned int i;
2092
2093         static struct {
2094                 const char *prefix;
2095                 unsigned int kind;
2096         } ref_kind[] = {
2097                 { "refs/heads/" , FILTER_REFS_BRANCHES },
2098                 { "refs/remotes/" , FILTER_REFS_REMOTES },
2099                 { "refs/tags/", FILTER_REFS_TAGS}
2100         };
2101
2102         if (!strcmp(refname, "HEAD"))
2103                 return FILTER_REFS_DETACHED_HEAD;
2104
2105         for (i = 0; i < ARRAY_SIZE(ref_kind); i++) {
2106                 if (starts_with(refname, ref_kind[i].prefix))
2107                         return ref_kind[i].kind;
2108         }
2109
2110         return FILTER_REFS_OTHERS;
2111 }
2112
2113 static int filter_ref_kind(struct ref_filter *filter, const char *refname)
2114 {
2115         if (filter->kind == FILTER_REFS_BRANCHES ||
2116             filter->kind == FILTER_REFS_REMOTES ||
2117             filter->kind == FILTER_REFS_TAGS)
2118                 return filter->kind;
2119         return ref_kind_from_refname(refname);
2120 }
2121
2122 struct ref_filter_cbdata {
2123         struct ref_array *array;
2124         struct ref_filter *filter;
2125         struct contains_cache contains_cache;
2126         struct contains_cache no_contains_cache;
2127 };
2128
2129 /*
2130  * A call-back given to for_each_ref().  Filter refs and keep them for
2131  * later object processing.
2132  */
2133 static int ref_filter_handler(const char *refname, const struct object_id *oid, int flag, void *cb_data)
2134 {
2135         struct ref_filter_cbdata *ref_cbdata = cb_data;
2136         struct ref_filter *filter = ref_cbdata->filter;
2137         struct ref_array_item *ref;
2138         struct commit *commit = NULL;
2139         unsigned int kind;
2140
2141         if (flag & REF_BAD_NAME) {
2142                 warning(_("ignoring ref with broken name %s"), refname);
2143                 return 0;
2144         }
2145
2146         if (flag & REF_ISBROKEN) {
2147                 warning(_("ignoring broken ref %s"), refname);
2148                 return 0;
2149         }
2150
2151         /* Obtain the current ref kind from filter_ref_kind() and ignore unwanted refs. */
2152         kind = filter_ref_kind(filter, refname);
2153         if (!(kind & filter->kind))
2154                 return 0;
2155
2156         if (!filter_pattern_match(filter, refname))
2157                 return 0;
2158
2159         if (filter->points_at.nr && !match_points_at(&filter->points_at, oid, refname))
2160                 return 0;
2161
2162         /*
2163          * A merge filter is applied on refs pointing to commits. Hence
2164          * obtain the commit using the 'oid' available and discard all
2165          * non-commits early. The actual filtering is done later.
2166          */
2167         if (filter->reachable_from || filter->unreachable_from ||
2168             filter->with_commit || filter->no_commit || filter->verbose) {
2169                 commit = lookup_commit_reference_gently(the_repository, oid, 1);
2170                 if (!commit)
2171                         return 0;
2172                 /* We perform the filtering for the '--contains' option... */
2173                 if (filter->with_commit &&
2174                     !commit_contains(filter, commit, filter->with_commit, &ref_cbdata->contains_cache))
2175                         return 0;
2176                 /* ...or for the `--no-contains' option */
2177                 if (filter->no_commit &&
2178                     commit_contains(filter, commit, filter->no_commit, &ref_cbdata->no_contains_cache))
2179                         return 0;
2180         }
2181
2182         /*
2183          * We do not open the object yet; sort may only need refname
2184          * to do its job and the resulting list may yet to be pruned
2185          * by maxcount logic.
2186          */
2187         ref = ref_array_push(ref_cbdata->array, refname, oid);
2188         ref->commit = commit;
2189         ref->flag = flag;
2190         ref->kind = kind;
2191
2192         return 0;
2193 }
2194
2195 /*  Free memory allocated for a ref_array_item */
2196 static void free_array_item(struct ref_array_item *item)
2197 {
2198         free((char *)item->symref);
2199         if (item->value) {
2200                 int i;
2201                 for (i = 0; i < used_atom_cnt; i++)
2202                         free((char *)item->value[i].s);
2203                 free(item->value);
2204         }
2205         free(item);
2206 }
2207
2208 /* Free all memory allocated for ref_array */
2209 void ref_array_clear(struct ref_array *array)
2210 {
2211         int i;
2212
2213         for (i = 0; i < array->nr; i++)
2214                 free_array_item(array->items[i]);
2215         FREE_AND_NULL(array->items);
2216         array->nr = array->alloc = 0;
2217
2218         for (i = 0; i < used_atom_cnt; i++)
2219                 free((char *)used_atom[i].name);
2220         FREE_AND_NULL(used_atom);
2221         used_atom_cnt = 0;
2222
2223         if (ref_to_worktree_map.worktrees) {
2224                 hashmap_clear_and_free(&(ref_to_worktree_map.map),
2225                                         struct ref_to_worktree_entry, ent);
2226                 free_worktrees(ref_to_worktree_map.worktrees);
2227                 ref_to_worktree_map.worktrees = NULL;
2228         }
2229 }
2230
2231 #define EXCLUDE_REACHED 0
2232 #define INCLUDE_REACHED 1
2233 static void reach_filter(struct ref_array *array,
2234                          struct commit_list *check_reachable,
2235                          int include_reached)
2236 {
2237         struct rev_info revs;
2238         int i, old_nr;
2239         struct commit **to_clear;
2240         struct commit_list *cr;
2241
2242         if (!check_reachable)
2243                 return;
2244
2245         to_clear = xcalloc(sizeof(struct commit *), array->nr);
2246
2247         repo_init_revisions(the_repository, &revs, NULL);
2248
2249         for (i = 0; i < array->nr; i++) {
2250                 struct ref_array_item *item = array->items[i];
2251                 add_pending_object(&revs, &item->commit->object, item->refname);
2252                 to_clear[i] = item->commit;
2253         }
2254
2255         for (cr = check_reachable; cr; cr = cr->next) {
2256                 struct commit *merge_commit = cr->item;
2257                 merge_commit->object.flags |= UNINTERESTING;
2258                 add_pending_object(&revs, &merge_commit->object, "");
2259         }
2260
2261         revs.limited = 1;
2262         if (prepare_revision_walk(&revs))
2263                 die(_("revision walk setup failed"));
2264
2265         old_nr = array->nr;
2266         array->nr = 0;
2267
2268         for (i = 0; i < old_nr; i++) {
2269                 struct ref_array_item *item = array->items[i];
2270                 struct commit *commit = item->commit;
2271
2272                 int is_merged = !!(commit->object.flags & UNINTERESTING);
2273
2274                 if (is_merged == include_reached)
2275                         array->items[array->nr++] = array->items[i];
2276                 else
2277                         free_array_item(item);
2278         }
2279
2280         clear_commit_marks_many(old_nr, to_clear, ALL_REV_FLAGS);
2281
2282         while (check_reachable) {
2283                 struct commit *merge_commit = pop_commit(&check_reachable);
2284                 clear_commit_marks(merge_commit, ALL_REV_FLAGS);
2285         }
2286
2287         free(to_clear);
2288 }
2289
2290 /*
2291  * API for filtering a set of refs. Based on the type of refs the user
2292  * has requested, we iterate through those refs and apply filters
2293  * as per the given ref_filter structure and finally store the
2294  * filtered refs in the ref_array structure.
2295  */
2296 int filter_refs(struct ref_array *array, struct ref_filter *filter, unsigned int type)
2297 {
2298         struct ref_filter_cbdata ref_cbdata;
2299         int ret = 0;
2300         unsigned int broken = 0;
2301
2302         ref_cbdata.array = array;
2303         ref_cbdata.filter = filter;
2304
2305         if (type & FILTER_REFS_INCLUDE_BROKEN)
2306                 broken = 1;
2307         filter->kind = type & FILTER_REFS_KIND_MASK;
2308
2309         init_contains_cache(&ref_cbdata.contains_cache);
2310         init_contains_cache(&ref_cbdata.no_contains_cache);
2311
2312         /*  Simple per-ref filtering */
2313         if (!filter->kind)
2314                 die("filter_refs: invalid type");
2315         else {
2316                 /*
2317                  * For common cases where we need only branches or remotes or tags,
2318                  * we only iterate through those refs. If a mix of refs is needed,
2319                  * we iterate over all refs and filter out required refs with the help
2320                  * of filter_ref_kind().
2321                  */
2322                 if (filter->kind == FILTER_REFS_BRANCHES)
2323                         ret = for_each_fullref_in("refs/heads/", ref_filter_handler, &ref_cbdata, broken);
2324                 else if (filter->kind == FILTER_REFS_REMOTES)
2325                         ret = for_each_fullref_in("refs/remotes/", ref_filter_handler, &ref_cbdata, broken);
2326                 else if (filter->kind == FILTER_REFS_TAGS)
2327                         ret = for_each_fullref_in("refs/tags/", ref_filter_handler, &ref_cbdata, broken);
2328                 else if (filter->kind & FILTER_REFS_ALL)
2329                         ret = for_each_fullref_in_pattern(filter, ref_filter_handler, &ref_cbdata, broken);
2330                 if (!ret && (filter->kind & FILTER_REFS_DETACHED_HEAD))
2331                         head_ref(ref_filter_handler, &ref_cbdata);
2332         }
2333
2334         clear_contains_cache(&ref_cbdata.contains_cache);
2335         clear_contains_cache(&ref_cbdata.no_contains_cache);
2336
2337         /*  Filters that need revision walking */
2338         reach_filter(array, filter->reachable_from, INCLUDE_REACHED);
2339         reach_filter(array, filter->unreachable_from, EXCLUDE_REACHED);
2340
2341         return ret;
2342 }
2343
2344 static int compare_detached_head(struct ref_array_item *a, struct ref_array_item *b)
2345 {
2346         if (!(a->kind ^ b->kind))
2347                 BUG("ref_kind_from_refname() should only mark one ref as HEAD");
2348         if (a->kind & FILTER_REFS_DETACHED_HEAD)
2349                 return -1;
2350         else if (b->kind & FILTER_REFS_DETACHED_HEAD)
2351                 return 1;
2352         BUG("should have died in the xor check above");
2353         return 0;
2354 }
2355
2356 static int cmp_ref_sorting(struct ref_sorting *s, struct ref_array_item *a, struct ref_array_item *b)
2357 {
2358         struct atom_value *va, *vb;
2359         int cmp;
2360         int cmp_detached_head = 0;
2361         cmp_type cmp_type = used_atom[s->atom].type;
2362         struct strbuf err = STRBUF_INIT;
2363
2364         if (get_ref_atom_value(a, s->atom, &va, &err))
2365                 die("%s", err.buf);
2366         if (get_ref_atom_value(b, s->atom, &vb, &err))
2367                 die("%s", err.buf);
2368         strbuf_release(&err);
2369         if (s->sort_flags & REF_SORTING_DETACHED_HEAD_FIRST &&
2370             ((a->kind | b->kind) & FILTER_REFS_DETACHED_HEAD)) {
2371                 cmp = compare_detached_head(a, b);
2372                 cmp_detached_head = 1;
2373         } else if (s->sort_flags & REF_SORTING_VERSION) {
2374                 cmp = versioncmp(va->s, vb->s);
2375         } else if (cmp_type == FIELD_STR) {
2376                 int (*cmp_fn)(const char *, const char *);
2377                 cmp_fn = s->sort_flags & REF_SORTING_ICASE
2378                         ? strcasecmp : strcmp;
2379                 cmp = cmp_fn(va->s, vb->s);
2380         } else {
2381                 if (va->value < vb->value)
2382                         cmp = -1;
2383                 else if (va->value == vb->value)
2384                         cmp = 0;
2385                 else
2386                         cmp = 1;
2387         }
2388
2389         return (s->sort_flags & REF_SORTING_REVERSE && !cmp_detached_head)
2390                 ? -cmp : cmp;
2391 }
2392
2393 static int compare_refs(const void *a_, const void *b_, void *ref_sorting)
2394 {
2395         struct ref_array_item *a = *((struct ref_array_item **)a_);
2396         struct ref_array_item *b = *((struct ref_array_item **)b_);
2397         struct ref_sorting *s;
2398
2399         for (s = ref_sorting; s; s = s->next) {
2400                 int cmp = cmp_ref_sorting(s, a, b);
2401                 if (cmp)
2402                         return cmp;
2403         }
2404         s = ref_sorting;
2405         return s && s->sort_flags & REF_SORTING_ICASE ?
2406                 strcasecmp(a->refname, b->refname) :
2407                 strcmp(a->refname, b->refname);
2408 }
2409
2410 void ref_sorting_set_sort_flags_all(struct ref_sorting *sorting,
2411                                     unsigned int mask, int on)
2412 {
2413         for (; sorting; sorting = sorting->next) {
2414                 if (on)
2415                         sorting->sort_flags |= mask;
2416                 else
2417                         sorting->sort_flags &= ~mask;
2418         }
2419 }
2420
2421 void ref_array_sort(struct ref_sorting *sorting, struct ref_array *array)
2422 {
2423         QSORT_S(array->items, array->nr, compare_refs, sorting);
2424 }
2425
2426 static void append_literal(const char *cp, const char *ep, struct ref_formatting_state *state)
2427 {
2428         struct strbuf *s = &state->stack->output;
2429
2430         while (*cp && (!ep || cp < ep)) {
2431                 if (*cp == '%') {
2432                         if (cp[1] == '%')
2433                                 cp++;
2434                         else {
2435                                 int ch = hex2chr(cp + 1);
2436                                 if (0 <= ch) {
2437                                         strbuf_addch(s, ch);
2438                                         cp += 3;
2439                                         continue;
2440                                 }
2441                         }
2442                 }
2443                 strbuf_addch(s, *cp);
2444                 cp++;
2445         }
2446 }
2447
2448 int format_ref_array_item(struct ref_array_item *info,
2449                            const struct ref_format *format,
2450                            struct strbuf *final_buf,
2451                            struct strbuf *error_buf)
2452 {
2453         const char *cp, *sp, *ep;
2454         struct ref_formatting_state state = REF_FORMATTING_STATE_INIT;
2455
2456         state.quote_style = format->quote_style;
2457         push_stack_element(&state.stack);
2458
2459         for (cp = format->format; *cp && (sp = find_next(cp)); cp = ep + 1) {
2460                 struct atom_value *atomv;
2461                 int pos;
2462
2463                 ep = strchr(sp, ')');
2464                 if (cp < sp)
2465                         append_literal(cp, sp, &state);
2466                 pos = parse_ref_filter_atom(format, sp + 2, ep, error_buf);
2467                 if (pos < 0 || get_ref_atom_value(info, pos, &atomv, error_buf) ||
2468                     atomv->handler(atomv, &state, error_buf)) {
2469                         pop_stack_element(&state.stack);
2470                         return -1;
2471                 }
2472         }
2473         if (*cp) {
2474                 sp = cp + strlen(cp);
2475                 append_literal(cp, sp, &state);
2476         }
2477         if (format->need_color_reset_at_eol) {
2478                 struct atom_value resetv;
2479                 resetv.s = GIT_COLOR_RESET;
2480                 if (append_atom(&resetv, &state, error_buf)) {
2481                         pop_stack_element(&state.stack);
2482                         return -1;
2483                 }
2484         }
2485         if (state.stack->prev) {
2486                 pop_stack_element(&state.stack);
2487                 return strbuf_addf_ret(error_buf, -1, _("format: %%(end) atom missing"));
2488         }
2489         strbuf_addbuf(final_buf, &state.stack->output);
2490         pop_stack_element(&state.stack);
2491         return 0;
2492 }
2493
2494 void show_ref_array_item(struct ref_array_item *info,
2495                          const struct ref_format *format)
2496 {
2497         struct strbuf final_buf = STRBUF_INIT;
2498         struct strbuf error_buf = STRBUF_INIT;
2499
2500         if (format_ref_array_item(info, format, &final_buf, &error_buf))
2501                 die("%s", error_buf.buf);
2502         fwrite(final_buf.buf, 1, final_buf.len, stdout);
2503         strbuf_release(&error_buf);
2504         strbuf_release(&final_buf);
2505         putchar('\n');
2506 }
2507
2508 void pretty_print_ref(const char *name, const struct object_id *oid,
2509                       const struct ref_format *format)
2510 {
2511         struct ref_array_item *ref_item;
2512         ref_item = new_ref_array_item(name, oid);
2513         ref_item->kind = ref_kind_from_refname(name);
2514         show_ref_array_item(ref_item, format);
2515         free_array_item(ref_item);
2516 }
2517
2518 static int parse_sorting_atom(const char *atom)
2519 {
2520         /*
2521          * This parses an atom using a dummy ref_format, since we don't
2522          * actually care about the formatting details.
2523          */
2524         struct ref_format dummy = REF_FORMAT_INIT;
2525         const char *end = atom + strlen(atom);
2526         struct strbuf err = STRBUF_INIT;
2527         int res = parse_ref_filter_atom(&dummy, atom, end, &err);
2528         if (res < 0)
2529                 die("%s", err.buf);
2530         strbuf_release(&err);
2531         return res;
2532 }
2533
2534 /*  If no sorting option is given, use refname to sort as default */
2535 struct ref_sorting *ref_default_sorting(void)
2536 {
2537         static const char cstr_name[] = "refname";
2538
2539         struct ref_sorting *sorting = xcalloc(1, sizeof(*sorting));
2540
2541         sorting->next = NULL;
2542         sorting->atom = parse_sorting_atom(cstr_name);
2543         return sorting;
2544 }
2545
2546 void parse_ref_sorting(struct ref_sorting **sorting_tail, const char *arg)
2547 {
2548         struct ref_sorting *s;
2549
2550         s = xcalloc(1, sizeof(*s));
2551         s->next = *sorting_tail;
2552         *sorting_tail = s;
2553
2554         if (*arg == '-') {
2555                 s->sort_flags |= REF_SORTING_REVERSE;
2556                 arg++;
2557         }
2558         if (skip_prefix(arg, "version:", &arg) ||
2559             skip_prefix(arg, "v:", &arg))
2560                 s->sort_flags |= REF_SORTING_VERSION;
2561         s->atom = parse_sorting_atom(arg);
2562 }
2563
2564 int parse_opt_ref_sorting(const struct option *opt, const char *arg, int unset)
2565 {
2566         /*
2567          * NEEDSWORK: We should probably clear the list in this case, but we've
2568          * already munged the global used_atoms list, which would need to be
2569          * undone.
2570          */
2571         BUG_ON_OPT_NEG(unset);
2572
2573         parse_ref_sorting(opt->value, arg);
2574         return 0;
2575 }
2576
2577 int parse_opt_merge_filter(const struct option *opt, const char *arg, int unset)
2578 {
2579         struct ref_filter *rf = opt->value;
2580         struct object_id oid;
2581         struct commit *merge_commit;
2582
2583         BUG_ON_OPT_NEG(unset);
2584
2585         if (get_oid(arg, &oid))
2586                 die(_("malformed object name %s"), arg);
2587
2588         merge_commit = lookup_commit_reference_gently(the_repository, &oid, 0);
2589
2590         if (!merge_commit)
2591                 return error(_("option `%s' must point to a commit"), opt->long_name);
2592
2593         if (starts_with(opt->long_name, "no"))
2594                 commit_list_insert(merge_commit, &rf->unreachable_from);
2595         else
2596                 commit_list_insert(merge_commit, &rf->reachable_from);
2597
2598         return 0;
2599 }