ref-filter: introduce ref_formatting_state and ref_formatting_stack
[git/git.git] / ref-filter.c
CommitLineData
c95b7585
KN
1#include "builtin.h"
2#include "cache.h"
3#include "parse-options.h"
4#include "refs.h"
5#include "wildmatch.h"
6#include "commit.h"
7#include "remote.h"
8#include "color.h"
9#include "tag.h"
10#include "quote.h"
11#include "ref-filter.h"
35257aa0 12#include "revision.h"
c95b7585
KN
13
14typedef enum { FIELD_STR, FIELD_ULONG, FIELD_TIME } cmp_type;
15
16static struct {
17 const char *name;
18 cmp_type cmp_type;
19} valid_atom[] = {
20 { "refname" },
21 { "objecttype" },
22 { "objectsize", FIELD_ULONG },
23 { "objectname" },
24 { "tree" },
25 { "parent" },
26 { "numparent", FIELD_ULONG },
27 { "object" },
28 { "type" },
29 { "tag" },
30 { "author" },
31 { "authorname" },
32 { "authoremail" },
33 { "authordate", FIELD_TIME },
34 { "committer" },
35 { "committername" },
36 { "committeremail" },
37 { "committerdate", FIELD_TIME },
38 { "tagger" },
39 { "taggername" },
40 { "taggeremail" },
41 { "taggerdate", FIELD_TIME },
42 { "creator" },
43 { "creatordate", FIELD_TIME },
44 { "subject" },
45 { "body" },
46 { "contents" },
47 { "contents:subject" },
48 { "contents:body" },
49 { "contents:signature" },
50 { "upstream" },
51 { "push" },
52 { "symref" },
53 { "flag" },
54 { "HEAD" },
55 { "color" },
56};
57
574e96a2
KN
58#define REF_FORMATTING_STATE_INIT { 0, NULL }
59
60struct ref_formatting_stack {
61 struct ref_formatting_stack *prev;
62 struct strbuf output;
63};
64
65struct ref_formatting_state {
66 int quote_style;
67 struct ref_formatting_stack *stack;
68};
69
3a25761a
KN
70struct atom_value {
71 const char *s;
72 unsigned long ul; /* used for sorting when not FIELD_STR */
73};
74
c95b7585
KN
75/*
76 * An atom is a valid field atom listed above, possibly prefixed with
77 * a "*" to denote deref_tag().
78 *
79 * We parse given format string and sort specifiers, and make a list
80 * of properties that we need to extract out of objects. ref_array_item
81 * structure will hold an array of values extracted that can be
82 * indexed with the "atom number", which is an index into this
83 * array.
84 */
85static const char **used_atom;
86static cmp_type *used_atom_type;
87static int used_atom_cnt, need_tagged, need_symref;
88static int need_color_reset_at_eol;
89
90/*
91 * Used to parse format string and sort specifiers
92 */
93int parse_ref_filter_atom(const char *atom, const char *ep)
94{
95 const char *sp;
96 int i, at;
97
98 sp = atom;
99 if (*sp == '*' && sp < ep)
100 sp++; /* deref */
101 if (ep <= sp)
102 die("malformed field name: %.*s", (int)(ep-atom), atom);
103
104 /* Do we have the atom already used elsewhere? */
105 for (i = 0; i < used_atom_cnt; i++) {
106 int len = strlen(used_atom[i]);
107 if (len == ep - atom && !memcmp(used_atom[i], atom, len))
108 return i;
109 }
110
111 /* Is the atom a valid one? */
112 for (i = 0; i < ARRAY_SIZE(valid_atom); i++) {
113 int len = strlen(valid_atom[i].name);
114 /*
115 * If the atom name has a colon, strip it and everything after
116 * it off - it specifies the format for this entry, and
117 * shouldn't be used for checking against the valid_atom
118 * table.
119 */
120 const char *formatp = strchr(sp, ':');
121 if (!formatp || ep < formatp)
122 formatp = ep;
123 if (len == formatp - sp && !memcmp(valid_atom[i].name, sp, len))
124 break;
125 }
126
127 if (ARRAY_SIZE(valid_atom) <= i)
128 die("unknown field name: %.*s", (int)(ep-atom), atom);
129
130 /* Add it in, including the deref prefix */
131 at = used_atom_cnt;
132 used_atom_cnt++;
133 REALLOC_ARRAY(used_atom, used_atom_cnt);
134 REALLOC_ARRAY(used_atom_type, used_atom_cnt);
135 used_atom[at] = xmemdupz(atom, ep - atom);
136 used_atom_type[at] = valid_atom[i].cmp_type;
137 if (*atom == '*')
138 need_tagged = 1;
139 if (!strcmp(used_atom[at], "symref"))
140 need_symref = 1;
141 return at;
142}
143
574e96a2
KN
144static void push_stack_element(struct ref_formatting_stack **stack)
145{
146 struct ref_formatting_stack *s = xcalloc(1, sizeof(struct ref_formatting_stack));
147
148 strbuf_init(&s->output, 0);
149 s->prev = *stack;
150 *stack = s;
151}
152
153static void pop_stack_element(struct ref_formatting_stack **stack)
154{
155 struct ref_formatting_stack *current = *stack;
156 struct ref_formatting_stack *prev = current->prev;
157
158 if (prev)
159 strbuf_addbuf(&prev->output, &current->output);
160 strbuf_release(&current->output);
161 free(current);
162 *stack = prev;
163}
164
c95b7585
KN
165/*
166 * In a format string, find the next occurrence of %(atom).
167 */
168static const char *find_next(const char *cp)
169{
170 while (*cp) {
171 if (*cp == '%') {
172 /*
173 * %( is the start of an atom;
174 * %% is a quoted per-cent.
175 */
176 if (cp[1] == '(')
177 return cp;
178 else if (cp[1] == '%')
179 cp++; /* skip over two % */
180 /* otherwise this is a singleton, literal % */
181 }
182 cp++;
183 }
184 return NULL;
185}
186
187/*
188 * Make sure the format string is well formed, and parse out
189 * the used atoms.
190 */
191int verify_ref_format(const char *format)
192{
193 const char *cp, *sp;
194
195 need_color_reset_at_eol = 0;
196 for (cp = format; *cp && (sp = find_next(cp)); ) {
197 const char *color, *ep = strchr(sp, ')');
198 int at;
199
200 if (!ep)
201 return error("malformed format string %s", sp);
202 /* sp points at "%(" and ep points at the closing ")" */
203 at = parse_ref_filter_atom(sp + 2, ep);
204 cp = ep + 1;
205
206 if (skip_prefix(used_atom[at], "color:", &color))
207 need_color_reset_at_eol = !!strcmp(color, "reset");
208 }
209 return 0;
210}
211
212/*
213 * Given an object name, read the object data and size, and return a
214 * "struct object". If the object data we are returning is also borrowed
215 * by the "struct object" representation, set *eaten as well---it is a
216 * signal from parse_object_buffer to us not to free the buffer.
217 */
218static void *get_obj(const unsigned char *sha1, struct object **obj, unsigned long *sz, int *eaten)
219{
220 enum object_type type;
221 void *buf = read_sha1_file(sha1, &type, sz);
222
223 if (buf)
224 *obj = parse_object_buffer(sha1, type, *sz, buf, eaten);
225 else
226 *obj = NULL;
227 return buf;
228}
229
230static int grab_objectname(const char *name, const unsigned char *sha1,
231 struct atom_value *v)
232{
233 if (!strcmp(name, "objectname")) {
234 char *s = xmalloc(41);
235 strcpy(s, sha1_to_hex(sha1));
236 v->s = s;
237 return 1;
238 }
239 if (!strcmp(name, "objectname:short")) {
240 v->s = xstrdup(find_unique_abbrev(sha1, DEFAULT_ABBREV));
241 return 1;
242 }
243 return 0;
244}
245
246/* See grab_values */
247static void grab_common_values(struct atom_value *val, int deref, struct object *obj, void *buf, unsigned long sz)
248{
249 int i;
250
251 for (i = 0; i < used_atom_cnt; i++) {
252 const char *name = used_atom[i];
253 struct atom_value *v = &val[i];
254 if (!!deref != (*name == '*'))
255 continue;
256 if (deref)
257 name++;
258 if (!strcmp(name, "objecttype"))
259 v->s = typename(obj->type);
260 else if (!strcmp(name, "objectsize")) {
261 char *s = xmalloc(40);
262 sprintf(s, "%lu", sz);
263 v->ul = sz;
264 v->s = s;
265 }
266 else if (deref)
267 grab_objectname(name, obj->sha1, v);
268 }
269}
270
271/* See grab_values */
272static void grab_tag_values(struct atom_value *val, int deref, struct object *obj, void *buf, unsigned long sz)
273{
274 int i;
275 struct tag *tag = (struct tag *) obj;
276
277 for (i = 0; i < used_atom_cnt; i++) {
278 const char *name = used_atom[i];
279 struct atom_value *v = &val[i];
280 if (!!deref != (*name == '*'))
281 continue;
282 if (deref)
283 name++;
284 if (!strcmp(name, "tag"))
285 v->s = tag->tag;
286 else if (!strcmp(name, "type") && tag->tagged)
287 v->s = typename(tag->tagged->type);
288 else if (!strcmp(name, "object") && tag->tagged) {
289 char *s = xmalloc(41);
290 strcpy(s, sha1_to_hex(tag->tagged->sha1));
291 v->s = s;
292 }
293 }
294}
295
296/* See grab_values */
297static void grab_commit_values(struct atom_value *val, int deref, struct object *obj, void *buf, unsigned long sz)
298{
299 int i;
300 struct commit *commit = (struct commit *) obj;
301
302 for (i = 0; i < used_atom_cnt; i++) {
303 const char *name = used_atom[i];
304 struct atom_value *v = &val[i];
305 if (!!deref != (*name == '*'))
306 continue;
307 if (deref)
308 name++;
309 if (!strcmp(name, "tree")) {
310 char *s = xmalloc(41);
311 strcpy(s, sha1_to_hex(commit->tree->object.sha1));
312 v->s = s;
313 }
314 if (!strcmp(name, "numparent")) {
315 char *s = xmalloc(40);
316 v->ul = commit_list_count(commit->parents);
317 sprintf(s, "%lu", v->ul);
318 v->s = s;
319 }
320 else if (!strcmp(name, "parent")) {
321 int num = commit_list_count(commit->parents);
322 int i;
323 struct commit_list *parents;
324 char *s = xmalloc(41 * num + 1);
325 v->s = s;
326 for (i = 0, parents = commit->parents;
327 parents;
328 parents = parents->next, i = i + 41) {
329 struct commit *parent = parents->item;
330 strcpy(s+i, sha1_to_hex(parent->object.sha1));
331 if (parents->next)
332 s[i+40] = ' ';
333 }
334 if (!i)
335 *s = '\0';
336 }
337 }
338}
339
340static const char *find_wholine(const char *who, int wholen, const char *buf, unsigned long sz)
341{
342 const char *eol;
343 while (*buf) {
344 if (!strncmp(buf, who, wholen) &&
345 buf[wholen] == ' ')
346 return buf + wholen + 1;
347 eol = strchr(buf, '\n');
348 if (!eol)
349 return "";
350 eol++;
351 if (*eol == '\n')
352 return ""; /* end of header */
353 buf = eol;
354 }
355 return "";
356}
357
358static const char *copy_line(const char *buf)
359{
360 const char *eol = strchrnul(buf, '\n');
361 return xmemdupz(buf, eol - buf);
362}
363
364static const char *copy_name(const char *buf)
365{
366 const char *cp;
367 for (cp = buf; *cp && *cp != '\n'; cp++) {
368 if (!strncmp(cp, " <", 2))
369 return xmemdupz(buf, cp - buf);
370 }
371 return "";
372}
373
374static const char *copy_email(const char *buf)
375{
376 const char *email = strchr(buf, '<');
377 const char *eoemail;
378 if (!email)
379 return "";
380 eoemail = strchr(email, '>');
381 if (!eoemail)
382 return "";
383 return xmemdupz(email, eoemail + 1 - email);
384}
385
386static char *copy_subject(const char *buf, unsigned long len)
387{
388 char *r = xmemdupz(buf, len);
389 int i;
390
391 for (i = 0; i < len; i++)
392 if (r[i] == '\n')
393 r[i] = ' ';
394
395 return r;
396}
397
398static void grab_date(const char *buf, struct atom_value *v, const char *atomname)
399{
400 const char *eoemail = strstr(buf, "> ");
401 char *zone;
402 unsigned long timestamp;
403 long tz;
d939af12 404 struct date_mode date_mode = { DATE_NORMAL };
c95b7585
KN
405 const char *formatp;
406
407 /*
408 * We got here because atomname ends in "date" or "date<something>";
409 * it's not possible that <something> is not ":<format>" because
410 * parse_ref_filter_atom() wouldn't have allowed it, so we can assume that no
411 * ":" means no format is specified, and use the default.
412 */
413 formatp = strchr(atomname, ':');
414 if (formatp != NULL) {
415 formatp++;
d939af12 416 parse_date_format(formatp, &date_mode);
c95b7585
KN
417 }
418
419 if (!eoemail)
420 goto bad;
421 timestamp = strtoul(eoemail + 2, &zone, 10);
422 if (timestamp == ULONG_MAX)
423 goto bad;
424 tz = strtol(zone, NULL, 10);
425 if ((tz == LONG_MIN || tz == LONG_MAX) && errno == ERANGE)
426 goto bad;
d939af12 427 v->s = xstrdup(show_date(timestamp, tz, &date_mode));
c95b7585
KN
428 v->ul = timestamp;
429 return;
430 bad:
431 v->s = "";
432 v->ul = 0;
433}
434
435/* See grab_values */
436static void grab_person(const char *who, struct atom_value *val, int deref, struct object *obj, void *buf, unsigned long sz)
437{
438 int i;
439 int wholen = strlen(who);
440 const char *wholine = NULL;
441
442 for (i = 0; i < used_atom_cnt; i++) {
443 const char *name = used_atom[i];
444 struct atom_value *v = &val[i];
445 if (!!deref != (*name == '*'))
446 continue;
447 if (deref)
448 name++;
449 if (strncmp(who, name, wholen))
450 continue;
451 if (name[wholen] != 0 &&
452 strcmp(name + wholen, "name") &&
453 strcmp(name + wholen, "email") &&
454 !starts_with(name + wholen, "date"))
455 continue;
456 if (!wholine)
457 wholine = find_wholine(who, wholen, buf, sz);
458 if (!wholine)
459 return; /* no point looking for it */
460 if (name[wholen] == 0)
461 v->s = copy_line(wholine);
462 else if (!strcmp(name + wholen, "name"))
463 v->s = copy_name(wholine);
464 else if (!strcmp(name + wholen, "email"))
465 v->s = copy_email(wholine);
466 else if (starts_with(name + wholen, "date"))
467 grab_date(wholine, v, name);
468 }
469
470 /*
471 * For a tag or a commit object, if "creator" or "creatordate" is
472 * requested, do something special.
473 */
474 if (strcmp(who, "tagger") && strcmp(who, "committer"))
475 return; /* "author" for commit object is not wanted */
476 if (!wholine)
477 wholine = find_wholine(who, wholen, buf, sz);
478 if (!wholine)
479 return;
480 for (i = 0; i < used_atom_cnt; i++) {
481 const char *name = used_atom[i];
482 struct atom_value *v = &val[i];
483 if (!!deref != (*name == '*'))
484 continue;
485 if (deref)
486 name++;
487
488 if (starts_with(name, "creatordate"))
489 grab_date(wholine, v, name);
490 else if (!strcmp(name, "creator"))
491 v->s = copy_line(wholine);
492 }
493}
494
495static void find_subpos(const char *buf, unsigned long sz,
496 const char **sub, unsigned long *sublen,
497 const char **body, unsigned long *bodylen,
498 unsigned long *nonsiglen,
499 const char **sig, unsigned long *siglen)
500{
501 const char *eol;
502 /* skip past header until we hit empty line */
503 while (*buf && *buf != '\n') {
504 eol = strchrnul(buf, '\n');
505 if (*eol)
506 eol++;
507 buf = eol;
508 }
509 /* skip any empty lines */
510 while (*buf == '\n')
511 buf++;
512
513 /* parse signature first; we might not even have a subject line */
514 *sig = buf + parse_signature(buf, strlen(buf));
515 *siglen = strlen(*sig);
516
517 /* subject is first non-empty line */
518 *sub = buf;
519 /* subject goes to first empty line */
520 while (buf < *sig && *buf && *buf != '\n') {
521 eol = strchrnul(buf, '\n');
522 if (*eol)
523 eol++;
524 buf = eol;
525 }
526 *sublen = buf - *sub;
527 /* drop trailing newline, if present */
528 if (*sublen && (*sub)[*sublen - 1] == '\n')
529 *sublen -= 1;
530
531 /* skip any empty lines */
532 while (*buf == '\n')
533 buf++;
534 *body = buf;
535 *bodylen = strlen(buf);
536 *nonsiglen = *sig - buf;
537}
538
539/* See grab_values */
540static void grab_sub_body_contents(struct atom_value *val, int deref, struct object *obj, void *buf, unsigned long sz)
541{
542 int i;
543 const char *subpos = NULL, *bodypos = NULL, *sigpos = NULL;
544 unsigned long sublen = 0, bodylen = 0, nonsiglen = 0, siglen = 0;
545
546 for (i = 0; i < used_atom_cnt; i++) {
547 const char *name = used_atom[i];
548 struct atom_value *v = &val[i];
549 if (!!deref != (*name == '*'))
550 continue;
551 if (deref)
552 name++;
553 if (strcmp(name, "subject") &&
554 strcmp(name, "body") &&
555 strcmp(name, "contents") &&
556 strcmp(name, "contents:subject") &&
557 strcmp(name, "contents:body") &&
558 strcmp(name, "contents:signature"))
559 continue;
560 if (!subpos)
561 find_subpos(buf, sz,
562 &subpos, &sublen,
563 &bodypos, &bodylen, &nonsiglen,
564 &sigpos, &siglen);
565
566 if (!strcmp(name, "subject"))
567 v->s = copy_subject(subpos, sublen);
568 else if (!strcmp(name, "contents:subject"))
569 v->s = copy_subject(subpos, sublen);
570 else if (!strcmp(name, "body"))
571 v->s = xmemdupz(bodypos, bodylen);
572 else if (!strcmp(name, "contents:body"))
573 v->s = xmemdupz(bodypos, nonsiglen);
574 else if (!strcmp(name, "contents:signature"))
575 v->s = xmemdupz(sigpos, siglen);
576 else if (!strcmp(name, "contents"))
577 v->s = xstrdup(subpos);
578 }
579}
580
581/*
582 * We want to have empty print-string for field requests
583 * that do not apply (e.g. "authordate" for a tag object)
584 */
585static void fill_missing_values(struct atom_value *val)
586{
587 int i;
588 for (i = 0; i < used_atom_cnt; i++) {
589 struct atom_value *v = &val[i];
590 if (v->s == NULL)
591 v->s = "";
592 }
593}
594
595/*
596 * val is a list of atom_value to hold returned values. Extract
597 * the values for atoms in used_atom array out of (obj, buf, sz).
598 * when deref is false, (obj, buf, sz) is the object that is
599 * pointed at by the ref itself; otherwise it is the object the
600 * ref (which is a tag) refers to.
601 */
602static void grab_values(struct atom_value *val, int deref, struct object *obj, void *buf, unsigned long sz)
603{
604 grab_common_values(val, deref, obj, buf, sz);
605 switch (obj->type) {
606 case OBJ_TAG:
607 grab_tag_values(val, deref, obj, buf, sz);
608 grab_sub_body_contents(val, deref, obj, buf, sz);
609 grab_person("tagger", val, deref, obj, buf, sz);
610 break;
611 case OBJ_COMMIT:
612 grab_commit_values(val, deref, obj, buf, sz);
613 grab_sub_body_contents(val, deref, obj, buf, sz);
614 grab_person("author", val, deref, obj, buf, sz);
615 grab_person("committer", val, deref, obj, buf, sz);
616 break;
617 case OBJ_TREE:
618 /* grab_tree_values(val, deref, obj, buf, sz); */
619 break;
620 case OBJ_BLOB:
621 /* grab_blob_values(val, deref, obj, buf, sz); */
622 break;
623 default:
624 die("Eh? Object of type %d?", obj->type);
625 }
626}
627
628static inline char *copy_advance(char *dst, const char *src)
629{
630 while (*src)
631 *dst++ = *src++;
632 return dst;
633}
634
635/*
636 * Parse the object referred by ref, and grab needed value.
637 */
638static void populate_value(struct ref_array_item *ref)
639{
640 void *buf;
641 struct object *obj;
642 int eaten, i;
643 unsigned long size;
644 const unsigned char *tagged;
645
646 ref->value = xcalloc(used_atom_cnt, sizeof(struct atom_value));
647
648 if (need_symref && (ref->flag & REF_ISSYMREF) && !ref->symref) {
649 unsigned char unused1[20];
650 ref->symref = resolve_refdup(ref->refname, RESOLVE_REF_READING,
651 unused1, NULL);
652 if (!ref->symref)
653 ref->symref = "";
654 }
655
656 /* Fill in specials first */
657 for (i = 0; i < used_atom_cnt; i++) {
658 const char *name = used_atom[i];
659 struct atom_value *v = &ref->value[i];
660 int deref = 0;
661 const char *refname;
662 const char *formatp;
663 struct branch *branch = NULL;
664
665 if (*name == '*') {
666 deref = 1;
667 name++;
668 }
669
670 if (starts_with(name, "refname"))
671 refname = ref->refname;
672 else if (starts_with(name, "symref"))
673 refname = ref->symref ? ref->symref : "";
674 else if (starts_with(name, "upstream")) {
675 const char *branch_name;
676 /* only local branches may have an upstream */
677 if (!skip_prefix(ref->refname, "refs/heads/",
678 &branch_name))
679 continue;
680 branch = branch_get(branch_name);
681
682 refname = branch_get_upstream(branch, NULL);
683 if (!refname)
684 continue;
685 } else if (starts_with(name, "push")) {
686 const char *branch_name;
687 if (!skip_prefix(ref->refname, "refs/heads/",
688 &branch_name))
689 continue;
690 branch = branch_get(branch_name);
691
692 refname = branch_get_push(branch, NULL);
693 if (!refname)
694 continue;
695 } else if (starts_with(name, "color:")) {
696 char color[COLOR_MAXLEN] = "";
697
698 if (color_parse(name + 6, color) < 0)
699 die(_("unable to parse format"));
700 v->s = xstrdup(color);
701 continue;
702 } else if (!strcmp(name, "flag")) {
703 char buf[256], *cp = buf;
704 if (ref->flag & REF_ISSYMREF)
705 cp = copy_advance(cp, ",symref");
706 if (ref->flag & REF_ISPACKED)
707 cp = copy_advance(cp, ",packed");
708 if (cp == buf)
709 v->s = "";
710 else {
711 *cp = '\0';
712 v->s = xstrdup(buf + 1);
713 }
714 continue;
715 } else if (!deref && grab_objectname(name, ref->objectname, v)) {
716 continue;
717 } else if (!strcmp(name, "HEAD")) {
718 const char *head;
719 unsigned char sha1[20];
720
721 head = resolve_ref_unsafe("HEAD", RESOLVE_REF_READING,
722 sha1, NULL);
723 if (!strcmp(ref->refname, head))
724 v->s = "*";
725 else
726 v->s = " ";
727 continue;
728 } else
729 continue;
730
731 formatp = strchr(name, ':');
732 if (formatp) {
733 int num_ours, num_theirs;
734
735 formatp++;
736 if (!strcmp(formatp, "short"))
737 refname = shorten_unambiguous_ref(refname,
738 warn_ambiguous_refs);
739 else if (!strcmp(formatp, "track") &&
740 (starts_with(name, "upstream") ||
741 starts_with(name, "push"))) {
742 char buf[40];
743
744 if (stat_tracking_info(branch, &num_ours,
745 &num_theirs, NULL))
746 continue;
747
748 if (!num_ours && !num_theirs)
749 v->s = "";
750 else if (!num_ours) {
751 sprintf(buf, "[behind %d]", num_theirs);
752 v->s = xstrdup(buf);
753 } else if (!num_theirs) {
754 sprintf(buf, "[ahead %d]", num_ours);
755 v->s = xstrdup(buf);
756 } else {
757 sprintf(buf, "[ahead %d, behind %d]",
758 num_ours, num_theirs);
759 v->s = xstrdup(buf);
760 }
761 continue;
762 } else if (!strcmp(formatp, "trackshort") &&
763 (starts_with(name, "upstream") ||
764 starts_with(name, "push"))) {
765 assert(branch);
766
767 if (stat_tracking_info(branch, &num_ours,
768 &num_theirs, NULL))
769 continue;
770
771 if (!num_ours && !num_theirs)
772 v->s = "=";
773 else if (!num_ours)
774 v->s = "<";
775 else if (!num_theirs)
776 v->s = ">";
777 else
778 v->s = "<>";
779 continue;
780 } else
781 die("unknown %.*s format %s",
782 (int)(formatp - name), name, formatp);
783 }
784
785 if (!deref)
786 v->s = refname;
787 else {
788 int len = strlen(refname);
789 char *s = xmalloc(len + 4);
790 sprintf(s, "%s^{}", refname);
791 v->s = s;
792 }
793 }
794
795 for (i = 0; i < used_atom_cnt; i++) {
796 struct atom_value *v = &ref->value[i];
797 if (v->s == NULL)
798 goto need_obj;
799 }
800 return;
801
802 need_obj:
803 buf = get_obj(ref->objectname, &obj, &size, &eaten);
804 if (!buf)
805 die("missing object %s for %s",
806 sha1_to_hex(ref->objectname), ref->refname);
807 if (!obj)
808 die("parse_object_buffer failed on %s for %s",
809 sha1_to_hex(ref->objectname), ref->refname);
810
811 grab_values(ref->value, 0, obj, buf, size);
812 if (!eaten)
813 free(buf);
814
815 /*
816 * If there is no atom that wants to know about tagged
817 * object, we are done.
818 */
819 if (!need_tagged || (obj->type != OBJ_TAG))
820 return;
821
822 /*
823 * If it is a tag object, see if we use a value that derefs
824 * the object, and if we do grab the object it refers to.
825 */
826 tagged = ((struct tag *)obj)->tagged->sha1;
827
828 /*
829 * NEEDSWORK: This derefs tag only once, which
830 * is good to deal with chains of trust, but
831 * is not consistent with what deref_tag() does
832 * which peels the onion to the core.
833 */
834 buf = get_obj(tagged, &obj, &size, &eaten);
835 if (!buf)
836 die("missing object %s for %s",
837 sha1_to_hex(tagged), ref->refname);
838 if (!obj)
839 die("parse_object_buffer failed on %s for %s",
840 sha1_to_hex(tagged), ref->refname);
841 grab_values(ref->value, 1, obj, buf, size);
842 if (!eaten)
843 free(buf);
844}
845
846/*
847 * Given a ref, return the value for the atom. This lazily gets value
848 * out of the object by calling populate value.
849 */
850static void get_ref_atom_value(struct ref_array_item *ref, int atom, struct atom_value **v)
851{
852 if (!ref->value) {
853 populate_value(ref);
854 fill_missing_values(ref->value);
855 }
856 *v = &ref->value[atom];
857}
858
ee2bd06b
KN
859enum contains_result {
860 CONTAINS_UNKNOWN = -1,
861 CONTAINS_NO = 0,
862 CONTAINS_YES = 1
863};
864
865/*
866 * Mimicking the real stack, this stack lives on the heap, avoiding stack
867 * overflows.
868 *
869 * At each recursion step, the stack items points to the commits whose
870 * ancestors are to be inspected.
871 */
872struct contains_stack {
873 int nr, alloc;
874 struct contains_stack_entry {
875 struct commit *commit;
876 struct commit_list *parents;
877 } *contains_stack;
878};
879
880static int in_commit_list(const struct commit_list *want, struct commit *c)
881{
882 for (; want; want = want->next)
883 if (!hashcmp(want->item->object.sha1, c->object.sha1))
884 return 1;
885 return 0;
886}
887
888/*
889 * Test whether the candidate or one of its parents is contained in the list.
890 * Do not recurse to find out, though, but return -1 if inconclusive.
891 */
892static enum contains_result contains_test(struct commit *candidate,
893 const struct commit_list *want)
894{
895 /* was it previously marked as containing a want commit? */
896 if (candidate->object.flags & TMP_MARK)
897 return 1;
898 /* or marked as not possibly containing a want commit? */
899 if (candidate->object.flags & UNINTERESTING)
900 return 0;
901 /* or are we it? */
902 if (in_commit_list(want, candidate)) {
903 candidate->object.flags |= TMP_MARK;
904 return 1;
905 }
906
907 if (parse_commit(candidate) < 0)
908 return 0;
909
910 return -1;
911}
912
913static void push_to_contains_stack(struct commit *candidate, struct contains_stack *contains_stack)
914{
915 ALLOC_GROW(contains_stack->contains_stack, contains_stack->nr + 1, contains_stack->alloc);
916 contains_stack->contains_stack[contains_stack->nr].commit = candidate;
917 contains_stack->contains_stack[contains_stack->nr++].parents = candidate->parents;
918}
919
920static enum contains_result contains_tag_algo(struct commit *candidate,
921 const struct commit_list *want)
922{
923 struct contains_stack contains_stack = { 0, 0, NULL };
924 int result = contains_test(candidate, want);
925
926 if (result != CONTAINS_UNKNOWN)
927 return result;
928
929 push_to_contains_stack(candidate, &contains_stack);
930 while (contains_stack.nr) {
931 struct contains_stack_entry *entry = &contains_stack.contains_stack[contains_stack.nr - 1];
932 struct commit *commit = entry->commit;
933 struct commit_list *parents = entry->parents;
934
935 if (!parents) {
936 commit->object.flags |= UNINTERESTING;
937 contains_stack.nr--;
938 }
939 /*
940 * If we just popped the stack, parents->item has been marked,
941 * therefore contains_test will return a meaningful 0 or 1.
942 */
943 else switch (contains_test(parents->item, want)) {
944 case CONTAINS_YES:
945 commit->object.flags |= TMP_MARK;
946 contains_stack.nr--;
947 break;
948 case CONTAINS_NO:
949 entry->parents = parents->next;
950 break;
951 case CONTAINS_UNKNOWN:
952 push_to_contains_stack(parents->item, &contains_stack);
953 break;
954 }
955 }
956 free(contains_stack.contains_stack);
957 return contains_test(candidate, want);
958}
959
960static int commit_contains(struct ref_filter *filter, struct commit *commit)
961{
962 if (filter->with_commit_tag_algo)
963 return contains_tag_algo(commit, filter->with_commit);
964 return is_descendant_of(commit, filter->with_commit);
965}
966
c95b7585
KN
967/*
968 * Return 1 if the refname matches one of the patterns, otherwise 0.
969 * A pattern can be path prefix (e.g. a refname "refs/heads/master"
970 * matches a pattern "refs/heads/") or a wildcard (e.g. the same ref
971 * matches "refs/heads/m*",too).
972 */
973static int match_name_as_path(const char **pattern, const char *refname)
974{
975 int namelen = strlen(refname);
976 for (; *pattern; pattern++) {
977 const char *p = *pattern;
978 int plen = strlen(p);
979
980 if ((plen <= namelen) &&
981 !strncmp(refname, p, plen) &&
982 (refname[plen] == '\0' ||
983 refname[plen] == '/' ||
984 p[plen-1] == '/'))
985 return 1;
986 if (!wildmatch(p, refname, WM_PATHNAME, NULL))
987 return 1;
988 }
989 return 0;
990}
991
68411046
KN
992/*
993 * Given a ref (sha1, refname), check if the ref belongs to the array
994 * of sha1s. If the given ref is a tag, check if the given tag points
995 * at one of the sha1s in the given sha1 array.
996 * the given sha1_array.
997 * NEEDSWORK:
998 * 1. Only a single level of inderection is obtained, we might want to
999 * change this to account for multiple levels (e.g. annotated tags
1000 * pointing to annotated tags pointing to a commit.)
1001 * 2. As the refs are cached we might know what refname peels to without
1002 * the need to parse the object via parse_object(). peel_ref() might be a
1003 * more efficient alternative to obtain the pointee.
1004 */
1005static const unsigned char *match_points_at(struct sha1_array *points_at,
1006 const unsigned char *sha1,
1007 const char *refname)
1008{
1009 const unsigned char *tagged_sha1 = NULL;
1010 struct object *obj;
1011
1012 if (sha1_array_lookup(points_at, sha1) >= 0)
1013 return sha1;
1014 obj = parse_object(sha1);
1015 if (!obj)
1016 die(_("malformed object at '%s'"), refname);
1017 if (obj->type == OBJ_TAG)
1018 tagged_sha1 = ((struct tag *)obj)->tagged->sha1;
1019 if (tagged_sha1 && sha1_array_lookup(points_at, tagged_sha1) >= 0)
1020 return tagged_sha1;
1021 return NULL;
1022}
1023
c95b7585
KN
1024/* Allocate space for a new ref_array_item and copy the objectname and flag to it */
1025static struct ref_array_item *new_ref_array_item(const char *refname,
1026 const unsigned char *objectname,
1027 int flag)
1028{
1958a6eb
KN
1029 size_t len = strlen(refname);
1030 struct ref_array_item *ref = xcalloc(1, sizeof(struct ref_array_item) + len + 1);
1031 memcpy(ref->refname, refname, len);
1032 ref->refname[len] = '\0';
c95b7585
KN
1033 hashcpy(ref->objectname, objectname);
1034 ref->flag = flag;
1035
1036 return ref;
1037}
1038
1039/*
1040 * A call-back given to for_each_ref(). Filter refs and keep them for
1041 * later object processing.
1042 */
14de7fba 1043static int ref_filter_handler(const char *refname, const struct object_id *oid, int flag, void *cb_data)
c95b7585
KN
1044{
1045 struct ref_filter_cbdata *ref_cbdata = cb_data;
14de7fba 1046 struct ref_filter *filter = ref_cbdata->filter;
c95b7585 1047 struct ref_array_item *ref;
35257aa0 1048 struct commit *commit = NULL;
c95b7585
KN
1049
1050 if (flag & REF_BAD_NAME) {
1051 warning("ignoring ref with broken name %s", refname);
1052 return 0;
1053 }
1054
7ebc8cbe
JH
1055 if (flag & REF_ISBROKEN) {
1056 warning("ignoring broken ref %s", refname);
1057 return 0;
1058 }
1059
c95b7585
KN
1060 if (*filter->name_patterns && !match_name_as_path(filter->name_patterns, refname))
1061 return 0;
1062
68411046
KN
1063 if (filter->points_at.nr && !match_points_at(&filter->points_at, oid->hash, refname))
1064 return 0;
1065
35257aa0
KN
1066 /*
1067 * A merge filter is applied on refs pointing to commits. Hence
1068 * obtain the commit using the 'oid' available and discard all
1069 * non-commits early. The actual filtering is done later.
1070 */
ee2bd06b 1071 if (filter->merge_commit || filter->with_commit) {
35257aa0
KN
1072 commit = lookup_commit_reference_gently(oid->hash, 1);
1073 if (!commit)
1074 return 0;
ee2bd06b
KN
1075 /* We perform the filtering for the '--contains' option */
1076 if (filter->with_commit &&
1077 !commit_contains(filter, commit))
1078 return 0;
35257aa0
KN
1079 }
1080
c95b7585
KN
1081 /*
1082 * We do not open the object yet; sort may only need refname
1083 * to do its job and the resulting list may yet to be pruned
1084 * by maxcount logic.
1085 */
1086 ref = new_ref_array_item(refname, oid->hash, flag);
35257aa0 1087 ref->commit = commit;
c95b7585 1088
14de7fba
KN
1089 REALLOC_ARRAY(ref_cbdata->array->items, ref_cbdata->array->nr + 1);
1090 ref_cbdata->array->items[ref_cbdata->array->nr++] = ref;
c95b7585
KN
1091 return 0;
1092}
1093
1094/* Free memory allocated for a ref_array_item */
1095static void free_array_item(struct ref_array_item *item)
1096{
1097 free((char *)item->symref);
c95b7585
KN
1098 free(item);
1099}
1100
1101/* Free all memory allocated for ref_array */
1102void ref_array_clear(struct ref_array *array)
1103{
1104 int i;
1105
1106 for (i = 0; i < array->nr; i++)
1107 free_array_item(array->items[i]);
1108 free(array->items);
1109 array->items = NULL;
1110 array->nr = array->alloc = 0;
1111}
1112
35257aa0
KN
1113static void do_merge_filter(struct ref_filter_cbdata *ref_cbdata)
1114{
1115 struct rev_info revs;
1116 int i, old_nr;
1117 struct ref_filter *filter = ref_cbdata->filter;
1118 struct ref_array *array = ref_cbdata->array;
1119 struct commit **to_clear = xcalloc(sizeof(struct commit *), array->nr);
1120
1121 init_revisions(&revs, NULL);
1122
1123 for (i = 0; i < array->nr; i++) {
1124 struct ref_array_item *item = array->items[i];
1125 add_pending_object(&revs, &item->commit->object, item->refname);
1126 to_clear[i] = item->commit;
1127 }
1128
1129 filter->merge_commit->object.flags |= UNINTERESTING;
1130 add_pending_object(&revs, &filter->merge_commit->object, "");
1131
1132 revs.limited = 1;
1133 if (prepare_revision_walk(&revs))
1134 die(_("revision walk setup failed"));
1135
1136 old_nr = array->nr;
1137 array->nr = 0;
1138
1139 for (i = 0; i < old_nr; i++) {
1140 struct ref_array_item *item = array->items[i];
1141 struct commit *commit = item->commit;
1142
1143 int is_merged = !!(commit->object.flags & UNINTERESTING);
1144
1145 if (is_merged == (filter->merge == REF_FILTER_MERGED_INCLUDE))
1146 array->items[array->nr++] = array->items[i];
1147 else
1148 free_array_item(item);
1149 }
1150
1151 for (i = 0; i < old_nr; i++)
1152 clear_commit_marks(to_clear[i], ALL_REV_FLAGS);
1153 clear_commit_marks(filter->merge_commit, ALL_REV_FLAGS);
1154 free(to_clear);
1155}
1156
14de7fba
KN
1157/*
1158 * API for filtering a set of refs. Based on the type of refs the user
1159 * has requested, we iterate through those refs and apply filters
1160 * as per the given ref_filter structure and finally store the
1161 * filtered refs in the ref_array structure.
1162 */
1163int filter_refs(struct ref_array *array, struct ref_filter *filter, unsigned int type)
1164{
1165 struct ref_filter_cbdata ref_cbdata;
35257aa0 1166 int ret = 0;
14de7fba
KN
1167
1168 ref_cbdata.array = array;
1169 ref_cbdata.filter = filter;
1170
35257aa0 1171 /* Simple per-ref filtering */
14de7fba 1172 if (type & (FILTER_REFS_ALL | FILTER_REFS_INCLUDE_BROKEN))
35257aa0 1173 ret = for_each_rawref(ref_filter_handler, &ref_cbdata);
14de7fba 1174 else if (type & FILTER_REFS_ALL)
35257aa0
KN
1175 ret = for_each_ref(ref_filter_handler, &ref_cbdata);
1176 else if (type)
14de7fba 1177 die("filter_refs: invalid type");
35257aa0
KN
1178
1179 /* Filters that need revision walking */
1180 if (filter->merge_commit)
1181 do_merge_filter(&ref_cbdata);
1182
1183 return ret;
14de7fba
KN
1184}
1185
c95b7585
KN
1186static int cmp_ref_sorting(struct ref_sorting *s, struct ref_array_item *a, struct ref_array_item *b)
1187{
1188 struct atom_value *va, *vb;
1189 int cmp;
1190 cmp_type cmp_type = used_atom_type[s->atom];
1191
1192 get_ref_atom_value(a, s->atom, &va);
1193 get_ref_atom_value(b, s->atom, &vb);
1194 switch (cmp_type) {
1195 case FIELD_STR:
1196 cmp = strcmp(va->s, vb->s);
1197 break;
1198 default:
1199 if (va->ul < vb->ul)
1200 cmp = -1;
1201 else if (va->ul == vb->ul)
1202 cmp = 0;
1203 else
1204 cmp = 1;
1205 break;
1206 }
1207 return (s->reverse) ? -cmp : cmp;
1208}
1209
1210static struct ref_sorting *ref_sorting;
1211static int compare_refs(const void *a_, const void *b_)
1212{
1213 struct ref_array_item *a = *((struct ref_array_item **)a_);
1214 struct ref_array_item *b = *((struct ref_array_item **)b_);
1215 struct ref_sorting *s;
1216
1217 for (s = ref_sorting; s; s = s->next) {
1218 int cmp = cmp_ref_sorting(s, a, b);
1219 if (cmp)
1220 return cmp;
1221 }
1222 return 0;
1223}
1224
1225void ref_array_sort(struct ref_sorting *sorting, struct ref_array *array)
1226{
1227 ref_sorting = sorting;
1228 qsort(array->items, array->nr, sizeof(struct ref_array_item *), compare_refs);
1229}
1230
574e96a2 1231static void append_atom(struct atom_value *v, struct ref_formatting_state *state)
c95b7585 1232{
574e96a2
KN
1233 struct strbuf *s = &state->stack->output;
1234
1235 switch (state->quote_style) {
c95b7585 1236 case QUOTE_NONE:
574e96a2 1237 strbuf_addstr(s, v->s);
c95b7585
KN
1238 break;
1239 case QUOTE_SHELL:
574e96a2 1240 sq_quote_buf(s, v->s);
c95b7585
KN
1241 break;
1242 case QUOTE_PERL:
574e96a2 1243 perl_quote_buf(s, v->s);
c95b7585
KN
1244 break;
1245 case QUOTE_PYTHON:
574e96a2 1246 python_quote_buf(s, v->s);
c95b7585
KN
1247 break;
1248 case QUOTE_TCL:
574e96a2 1249 tcl_quote_buf(s, v->s);
c95b7585
KN
1250 break;
1251 }
c95b7585
KN
1252}
1253
1254static int hex1(char ch)
1255{
1256 if ('0' <= ch && ch <= '9')
1257 return ch - '0';
1258 else if ('a' <= ch && ch <= 'f')
1259 return ch - 'a' + 10;
1260 else if ('A' <= ch && ch <= 'F')
1261 return ch - 'A' + 10;
1262 return -1;
1263}
1264static int hex2(const char *cp)
1265{
1266 if (cp[0] && cp[1])
1267 return (hex1(cp[0]) << 4) | hex1(cp[1]);
1268 else
1269 return -1;
1270}
1271
574e96a2 1272static void append_literal(const char *cp, const char *ep, struct ref_formatting_state *state)
c95b7585 1273{
574e96a2
KN
1274 struct strbuf *s = &state->stack->output;
1275
c95b7585
KN
1276 while (*cp && (!ep || cp < ep)) {
1277 if (*cp == '%') {
1278 if (cp[1] == '%')
1279 cp++;
1280 else {
1281 int ch = hex2(cp + 1);
1282 if (0 <= ch) {
574e96a2 1283 strbuf_addch(s, ch);
c95b7585
KN
1284 cp += 3;
1285 continue;
1286 }
1287 }
1288 }
574e96a2 1289 strbuf_addch(s, *cp);
c95b7585
KN
1290 cp++;
1291 }
1292}
1293
1294void show_ref_array_item(struct ref_array_item *info, const char *format, int quote_style)
1295{
1296 const char *cp, *sp, *ep;
574e96a2
KN
1297 struct strbuf *final_buf;
1298 struct ref_formatting_state state = REF_FORMATTING_STATE_INIT;
1299
1300 state.quote_style = quote_style;
1301 push_stack_element(&state.stack);
c95b7585
KN
1302
1303 for (cp = format; *cp && (sp = find_next(cp)); cp = ep + 1) {
1304 struct atom_value *atomv;
1305
1306 ep = strchr(sp, ')');
1307 if (cp < sp)
574e96a2 1308 append_literal(cp, sp, &state);
c95b7585 1309 get_ref_atom_value(info, parse_ref_filter_atom(sp + 2, ep), &atomv);
574e96a2 1310 append_atom(atomv, &state);
c95b7585
KN
1311 }
1312 if (*cp) {
1313 sp = cp + strlen(cp);
574e96a2 1314 append_literal(cp, sp, &state);
c95b7585
KN
1315 }
1316 if (need_color_reset_at_eol) {
1317 struct atom_value resetv;
1318 char color[COLOR_MAXLEN] = "";
1319
1320 if (color_parse("reset", color) < 0)
1321 die("BUG: couldn't parse 'reset' as a color");
1322 resetv.s = color;
574e96a2 1323 append_atom(&resetv, &state);
c95b7585 1324 }
574e96a2
KN
1325 final_buf = &state.stack->output;
1326 fwrite(final_buf->buf, 1, final_buf->len, stdout);
1327 pop_stack_element(&state.stack);
c95b7585
KN
1328 putchar('\n');
1329}
1330
1331/* If no sorting option is given, use refname to sort as default */
1332struct ref_sorting *ref_default_sorting(void)
1333{
1334 static const char cstr_name[] = "refname";
1335
1336 struct ref_sorting *sorting = xcalloc(1, sizeof(*sorting));
1337
1338 sorting->next = NULL;
1339 sorting->atom = parse_ref_filter_atom(cstr_name, cstr_name + strlen(cstr_name));
1340 return sorting;
1341}
1342
1343int parse_opt_ref_sorting(const struct option *opt, const char *arg, int unset)
1344{
1345 struct ref_sorting **sorting_tail = opt->value;
1346 struct ref_sorting *s;
1347 int len;
1348
1349 if (!arg) /* should --no-sort void the list ? */
1350 return -1;
1351
1352 s = xcalloc(1, sizeof(*s));
1353 s->next = *sorting_tail;
1354 *sorting_tail = s;
1355
1356 if (*arg == '-') {
1357 s->reverse = 1;
1358 arg++;
1359 }
1360 len = strlen(arg);
1361 s->atom = parse_ref_filter_atom(arg, arg+len);
1362 return 0;
1363}
5afcb905
KN
1364
1365int parse_opt_merge_filter(const struct option *opt, const char *arg, int unset)
1366{
1367 struct ref_filter *rf = opt->value;
1368 unsigned char sha1[20];
1369
1370 rf->merge = starts_with(opt->long_name, "no")
1371 ? REF_FILTER_MERGED_OMIT
1372 : REF_FILTER_MERGED_INCLUDE;
1373
1374 if (get_sha1(arg, sha1))
1375 die(_("malformed object name %s"), arg);
1376
1377 rf->merge_commit = lookup_commit_reference_gently(sha1, 0);
1378 if (!rf->merge_commit)
1379 return opterror(opt, "must point to a commit", 0);
1380
1381 return 0;
1382}