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