3 #include "repository.h"
8 #include "parse-options.h"
9 #include "prio-queue.h"
10 #include "hash-lookup.h"
11 #include "commit-slab.h"
12 #include "commit-graph.h"
15 * One day. See the 'name a rev shortly after epoch' test in t6120 when
18 #define CUTOFF_DATE_SLOP 86400
22 timestamp_t taggerdate
;
28 define_commit_slab(commit_rev_name
, struct rev_name
);
30 static timestamp_t generation_cutoff
= GENERATION_NUMBER_INFINITY
;
31 static timestamp_t cutoff
= TIME_MAX
;
32 static struct commit_rev_name rev_names
;
34 /* Disable the cutoff checks entirely */
35 static void disable_cutoff(void)
37 generation_cutoff
= 0;
41 /* Cutoff searching any commits older than this one */
42 static void set_commit_cutoff(struct commit
*commit
)
45 if (cutoff
> commit
->date
)
46 cutoff
= commit
->date
;
48 if (generation_cutoff
) {
49 timestamp_t generation
= commit_graph_generation(commit
);
51 if (generation_cutoff
> generation
)
52 generation_cutoff
= generation
;
56 /* adjust the commit date cutoff with a slop to allow for slightly incorrect
57 * commit timestamps in case of clock skew.
59 static void adjust_cutoff_timestamp_for_slop(void)
62 /* check for undeflow */
63 if (cutoff
> TIME_MIN
+ CUTOFF_DATE_SLOP
)
64 cutoff
= cutoff
- CUTOFF_DATE_SLOP
;
70 /* Check if a commit is before the cutoff. Prioritize generation numbers
71 * first, but use the commit timestamp if we lack generation data.
73 static int commit_is_before_cutoff(struct commit
*commit
)
75 if (generation_cutoff
< GENERATION_NUMBER_INFINITY
)
76 return generation_cutoff
&&
77 commit_graph_generation(commit
) < generation_cutoff
;
79 return commit
->date
< cutoff
;
82 /* How many generations are maximally preferred over _one_ merge traversal? */
83 #define MERGE_TRAVERSAL_WEIGHT 65535
85 static int is_valid_rev_name(const struct rev_name
*name
)
87 return name
&& (name
->generation
|| name
->tip_name
);
90 static struct rev_name
*get_commit_rev_name(const struct commit
*commit
)
92 struct rev_name
*name
= commit_rev_name_peek(&rev_names
, commit
);
94 return is_valid_rev_name(name
) ? name
: NULL
;
97 static int effective_distance(int distance
, int generation
)
99 return distance
+ (generation
> 0 ? MERGE_TRAVERSAL_WEIGHT
: 0);
102 static int is_better_name(struct rev_name
*name
,
103 timestamp_t taggerdate
,
108 int name_distance
= effective_distance(name
->distance
, name
->generation
);
109 int new_distance
= effective_distance(distance
, generation
);
112 * When comparing names based on tags, prefer names
113 * based on the older tag, even if it is farther away.
115 if (from_tag
&& name
->from_tag
)
116 return (name
->taggerdate
> taggerdate
||
117 (name
->taggerdate
== taggerdate
&&
118 name_distance
> new_distance
));
121 * We know that at least one of them is a non-tag at this point.
122 * favor a tag over a non-tag.
124 if (name
->from_tag
!= from_tag
)
128 * We are now looking at two non-tags. Tiebreak to favor
131 if (name_distance
!= new_distance
)
132 return name_distance
> new_distance
;
134 /* ... or tiebreak to favor older date */
135 if (name
->taggerdate
!= taggerdate
)
136 return name
->taggerdate
> taggerdate
;
138 /* keep the current one if we cannot decide */
142 static struct rev_name
*create_or_update_name(struct commit
*commit
,
143 timestamp_t taggerdate
,
144 int generation
, int distance
,
147 struct rev_name
*name
= commit_rev_name_at(&rev_names
, commit
);
149 if (is_valid_rev_name(name
)) {
150 if (!is_better_name(name
, taggerdate
, generation
, distance
, from_tag
))
154 * This string might still be shared with ancestors
155 * (generation > 0). We can release it here regardless,
156 * because the new name that has just won will be better
157 * for them as well, so name_rev() will replace these
158 * stale pointers when it processes the parents.
160 if (!name
->generation
)
161 free(name
->tip_name
);
164 name
->taggerdate
= taggerdate
;
165 name
->generation
= generation
;
166 name
->distance
= distance
;
167 name
->from_tag
= from_tag
;
172 static char *get_parent_name(const struct rev_name
*name
, int parent_number
)
174 struct strbuf sb
= STRBUF_INIT
;
177 strip_suffix(name
->tip_name
, "^0", &len
);
178 if (name
->generation
> 0) {
179 strbuf_grow(&sb
, len
+
180 1 + decimal_width(name
->generation
) +
181 1 + decimal_width(parent_number
));
182 strbuf_addf(&sb
, "%.*s~%d^%d", (int)len
, name
->tip_name
,
183 name
->generation
, parent_number
);
185 strbuf_grow(&sb
, len
+
186 1 + decimal_width(parent_number
));
187 strbuf_addf(&sb
, "%.*s^%d", (int)len
, name
->tip_name
,
190 return strbuf_detach(&sb
, NULL
);
193 static void name_rev(struct commit
*start_commit
,
194 const char *tip_name
, timestamp_t taggerdate
,
195 int from_tag
, int deref
)
197 struct prio_queue queue
;
198 struct commit
*commit
;
199 struct commit
**parents_to_queue
= NULL
;
200 size_t parents_to_queue_nr
, parents_to_queue_alloc
= 0;
201 struct rev_name
*start_name
;
203 parse_commit(start_commit
);
204 if (commit_is_before_cutoff(start_commit
))
207 start_name
= create_or_update_name(start_commit
, taggerdate
, 0, 0,
212 start_name
->tip_name
= xstrfmt("%s^0", tip_name
);
214 start_name
->tip_name
= xstrdup(tip_name
);
216 memset(&queue
, 0, sizeof(queue
)); /* Use the prio_queue as LIFO */
217 prio_queue_put(&queue
, start_commit
);
219 while ((commit
= prio_queue_get(&queue
))) {
220 struct rev_name
*name
= get_commit_rev_name(commit
);
221 struct commit_list
*parents
;
222 int parent_number
= 1;
224 parents_to_queue_nr
= 0;
226 for (parents
= commit
->parents
;
228 parents
= parents
->next
, parent_number
++) {
229 struct commit
*parent
= parents
->item
;
230 struct rev_name
*parent_name
;
231 int generation
, distance
;
233 parse_commit(parent
);
234 if (commit_is_before_cutoff(parent
))
237 if (parent_number
> 1) {
239 distance
= name
->distance
+ MERGE_TRAVERSAL_WEIGHT
;
241 generation
= name
->generation
+ 1;
242 distance
= name
->distance
+ 1;
245 parent_name
= create_or_update_name(parent
, taggerdate
,
249 if (parent_number
> 1)
250 parent_name
->tip_name
=
251 get_parent_name(name
,
254 parent_name
->tip_name
= name
->tip_name
;
255 ALLOC_GROW(parents_to_queue
,
256 parents_to_queue_nr
+ 1,
257 parents_to_queue_alloc
);
258 parents_to_queue
[parents_to_queue_nr
] = parent
;
259 parents_to_queue_nr
++;
263 /* The first parent must come out first from the prio_queue */
264 while (parents_to_queue_nr
)
265 prio_queue_put(&queue
,
266 parents_to_queue
[--parents_to_queue_nr
]);
269 clear_prio_queue(&queue
);
270 free(parents_to_queue
);
273 static int subpath_matches(const char *path
, const char *filter
)
275 const char *subpath
= path
;
278 if (!wildmatch(filter
, subpath
, 0))
279 return subpath
- path
;
280 subpath
= strchr(subpath
, '/');
287 static const char *name_ref_abbrev(const char *refname
, int shorten_unambiguous
)
289 if (shorten_unambiguous
)
290 refname
= shorten_unambiguous_ref(refname
, 0);
291 else if (skip_prefix(refname
, "refs/heads/", &refname
))
292 ; /* refname already advanced */
294 skip_prefix(refname
, "refs/", &refname
);
298 struct name_ref_data
{
301 struct string_list ref_filters
;
302 struct string_list exclude_filters
;
305 static struct tip_table
{
306 struct tip_table_entry
{
307 struct object_id oid
;
309 struct commit
*commit
;
310 timestamp_t taggerdate
;
311 unsigned int from_tag
:1;
312 unsigned int deref
:1;
319 static void add_to_tip_table(const struct object_id
*oid
, const char *refname
,
320 int shorten_unambiguous
, struct commit
*commit
,
321 timestamp_t taggerdate
, int from_tag
, int deref
)
323 refname
= name_ref_abbrev(refname
, shorten_unambiguous
);
325 ALLOC_GROW(tip_table
.table
, tip_table
.nr
+ 1, tip_table
.alloc
);
326 oidcpy(&tip_table
.table
[tip_table
.nr
].oid
, oid
);
327 tip_table
.table
[tip_table
.nr
].refname
= xstrdup(refname
);
328 tip_table
.table
[tip_table
.nr
].commit
= commit
;
329 tip_table
.table
[tip_table
.nr
].taggerdate
= taggerdate
;
330 tip_table
.table
[tip_table
.nr
].from_tag
= from_tag
;
331 tip_table
.table
[tip_table
.nr
].deref
= deref
;
333 tip_table
.sorted
= 0;
336 static int tipcmp(const void *a_
, const void *b_
)
338 const struct tip_table_entry
*a
= a_
, *b
= b_
;
339 return oidcmp(&a
->oid
, &b
->oid
);
342 static int cmp_by_tag_and_age(const void *a_
, const void *b_
)
344 const struct tip_table_entry
*a
= a_
, *b
= b_
;
348 cmp
= b
->from_tag
- a
->from_tag
;
352 /* Older is better. */
353 if (a
->taggerdate
< b
->taggerdate
)
355 return a
->taggerdate
!= b
->taggerdate
;
358 static int name_ref(const char *path
, const struct object_id
*oid
, int flags
, void *cb_data
)
360 struct object
*o
= parse_object(the_repository
, oid
);
361 struct name_ref_data
*data
= cb_data
;
362 int can_abbreviate_output
= data
->tags_only
&& data
->name_only
;
365 struct commit
*commit
= NULL
;
366 timestamp_t taggerdate
= TIME_MAX
;
368 if (data
->tags_only
&& !starts_with(path
, "refs/tags/"))
371 if (data
->exclude_filters
.nr
) {
372 struct string_list_item
*item
;
374 for_each_string_list_item(item
, &data
->exclude_filters
) {
375 if (subpath_matches(path
, item
->string
) >= 0)
380 if (data
->ref_filters
.nr
) {
381 struct string_list_item
*item
;
384 /* See if any of the patterns match. */
385 for_each_string_list_item(item
, &data
->ref_filters
) {
387 * Check all patterns even after finding a match, so
388 * that we can see if a match with a subpath exists.
389 * When a user asked for 'refs/tags/v*' and 'v1.*',
390 * both of which match, the user is showing her
391 * willingness to accept a shortened output by having
392 * the 'v1.*' in the acceptable refnames, so we
393 * shouldn't stop when seeing 'refs/tags/v1.4' matches
394 * 'refs/tags/v*'. We should show it as 'v1.4'.
396 switch (subpath_matches(path
, item
->string
)) {
397 case -1: /* did not match */
399 case 0: /* matched fully */
402 default: /* matched subpath */
404 can_abbreviate_output
= 1;
409 /* If none of the patterns matched, stop now */
414 while (o
&& o
->type
== OBJ_TAG
) {
415 struct tag
*t
= (struct tag
*) o
;
417 break; /* broken repository */
418 o
= parse_object(the_repository
, &t
->tagged
->oid
);
420 taggerdate
= t
->date
;
422 if (o
&& o
->type
== OBJ_COMMIT
) {
423 commit
= (struct commit
*)o
;
424 from_tag
= starts_with(path
, "refs/tags/");
425 if (taggerdate
== TIME_MAX
)
426 taggerdate
= commit
->date
;
429 add_to_tip_table(oid
, path
, can_abbreviate_output
, commit
, taggerdate
,
434 static void name_tips(void)
439 * Try to set better names first, so that worse ones spread
442 QSORT(tip_table
.table
, tip_table
.nr
, cmp_by_tag_and_age
);
443 for (i
= 0; i
< tip_table
.nr
; i
++) {
444 struct tip_table_entry
*e
= &tip_table
.table
[i
];
446 name_rev(e
->commit
, e
->refname
, e
->taggerdate
,
447 e
->from_tag
, e
->deref
);
452 static const struct object_id
*nth_tip_table_ent(size_t ix
, const void *table_
)
454 const struct tip_table_entry
*table
= table_
;
455 return &table
[ix
].oid
;
458 static const char *get_exact_ref_match(const struct object
*o
)
462 if (!tip_table
.table
|| !tip_table
.nr
)
465 if (!tip_table
.sorted
) {
466 QSORT(tip_table
.table
, tip_table
.nr
, tipcmp
);
467 tip_table
.sorted
= 1;
470 found
= oid_pos(&o
->oid
, tip_table
.table
, tip_table
.nr
,
473 return tip_table
.table
[found
].refname
;
477 /* may return a constant string or use "buf" as scratch space */
478 static const char *get_rev_name(const struct object
*o
, struct strbuf
*buf
)
481 const struct commit
*c
;
483 if (o
->type
!= OBJ_COMMIT
)
484 return get_exact_ref_match(o
);
485 c
= (const struct commit
*) o
;
486 n
= get_commit_rev_name(c
);
494 strbuf_addstr(buf
, n
->tip_name
);
495 strbuf_strip_suffix(buf
, "^0");
496 strbuf_addf(buf
, "~%d", n
->generation
);
501 static void show_name(const struct object
*obj
,
502 const char *caller_name
,
503 int always
, int allow_undefined
, int name_only
)
506 const struct object_id
*oid
= &obj
->oid
;
507 struct strbuf buf
= STRBUF_INIT
;
510 printf("%s ", caller_name
? caller_name
: oid_to_hex(oid
));
511 name
= get_rev_name(obj
, &buf
);
513 printf("%s\n", name
);
514 else if (allow_undefined
)
515 printf("undefined\n");
517 printf("%s\n", find_unique_abbrev(oid
, DEFAULT_ABBREV
));
519 die("cannot describe '%s'", oid_to_hex(oid
));
520 strbuf_release(&buf
);
523 static char const * const name_rev_usage
[] = {
524 N_("git name-rev [<options>] <commit>..."),
525 N_("git name-rev [<options>] --all"),
526 N_("git name-rev [<options>] --annotate-stdin"),
530 static void name_rev_line(char *p
, struct name_ref_data
*data
)
532 struct strbuf buf
= STRBUF_INIT
;
535 const unsigned hexsz
= the_hash_algo
->hexsz
;
537 for (p_start
= p
; *p
; p
++) {
538 #define ishex(x) (isdigit((x)) || ((x) >= 'a' && (x) <= 'f'))
541 else if (++counter
== hexsz
&&
543 struct object_id oid
;
544 const char *name
= NULL
;
546 int p_len
= p
- p_start
+ 1;
551 if (!get_oid(p
- (hexsz
- 1), &oid
)) {
553 lookup_object(the_repository
, &oid
);
555 name
= get_rev_name(o
, &buf
);
563 printf("%.*s%s", p_len
- hexsz
, p_start
, name
);
565 printf("%.*s (%s)", p_len
, p_start
, name
);
572 fwrite(p_start
, p
- p_start
, 1, stdout
);
574 strbuf_release(&buf
);
577 int cmd_name_rev(int argc
, const char **argv
, const char *prefix
)
579 struct object_array revs
= OBJECT_ARRAY_INIT
;
580 int all
= 0, annotate_stdin
= 0, transform_stdin
= 0, allow_undefined
= 1, always
= 0, peel_tag
= 0;
581 struct name_ref_data data
= { 0, 0, STRING_LIST_INIT_NODUP
, STRING_LIST_INIT_NODUP
};
582 struct option opts
[] = {
583 OPT_BOOL(0, "name-only", &data
.name_only
, N_("print only ref-based names (no object names)")),
584 OPT_BOOL(0, "tags", &data
.tags_only
, N_("only use tags to name the commits")),
585 OPT_STRING_LIST(0, "refs", &data
.ref_filters
, N_("pattern"),
586 N_("only use refs matching <pattern>")),
587 OPT_STRING_LIST(0, "exclude", &data
.exclude_filters
, N_("pattern"),
588 N_("ignore refs matching <pattern>")),
590 OPT_BOOL(0, "all", &all
, N_("list all commits reachable from all refs")),
591 OPT_BOOL(0, "stdin", &transform_stdin
, N_("deprecated: use annotate-stdin instead")),
592 OPT_BOOL(0, "annotate-stdin", &annotate_stdin
, N_("annotate text from stdin")),
593 OPT_BOOL(0, "undefined", &allow_undefined
, N_("allow to print `undefined` names (default)")),
594 OPT_BOOL(0, "always", &always
,
595 N_("show abbreviated commit object as fallback")),
597 /* A Hidden OPT_BOOL */
598 OPTION_SET_INT
, 0, "peel-tag", &peel_tag
, NULL
,
599 N_("dereference tags in the input (internal use)"),
600 PARSE_OPT_NOARG
| PARSE_OPT_HIDDEN
, NULL
, 1,
605 init_commit_rev_name(&rev_names
);
606 git_config(git_default_config
, NULL
);
607 argc
= parse_options(argc
, argv
, prefix
, opts
, name_rev_usage
, 0);
609 if (transform_stdin
) {
610 warning("--stdin is deprecated. Please use --annotate-stdin instead, "
611 "which is functionally equivalent.\n"
612 "This option will be removed in a future release.");
616 if (all
+ annotate_stdin
+ !!argc
> 1) {
617 error("Specify either a list, or --all, not both!");
618 usage_with_options(name_rev_usage
, opts
);
620 if (all
|| annotate_stdin
)
623 for (; argc
; argc
--, argv
++) {
624 struct object_id oid
;
625 struct object
*object
;
626 struct commit
*commit
;
628 if (get_oid(*argv
, &oid
)) {
629 fprintf(stderr
, "Could not get sha1 for %s. Skipping.\n",
635 object
= parse_object(the_repository
, &oid
);
637 struct object
*peeled
= deref_tag(the_repository
,
639 if (peeled
&& peeled
->type
== OBJ_COMMIT
)
640 commit
= (struct commit
*)peeled
;
644 fprintf(stderr
, "Could not get object for %s. Skipping.\n",
650 set_commit_cutoff(commit
);
654 fprintf(stderr
, "Could not get commit for %s. Skipping.\n",
658 object
= (struct object
*)commit
;
660 add_object_array(object
, *argv
, &revs
);
663 adjust_cutoff_timestamp_for_slop();
665 for_each_ref(name_ref
, &data
);
668 if (annotate_stdin
) {
669 struct strbuf sb
= STRBUF_INIT
;
671 while (strbuf_getline(&sb
, stdin
) != EOF
) {
672 strbuf_addch(&sb
, '\n');
673 name_rev_line(sb
.buf
, &data
);
679 max
= get_max_object_index();
680 for (i
= 0; i
< max
; i
++) {
681 struct object
*obj
= get_indexed_object(i
);
682 if (!obj
|| obj
->type
!= OBJ_COMMIT
)
685 always
, allow_undefined
, data
.name_only
);
689 for (i
= 0; i
< revs
.nr
; i
++)
690 show_name(revs
.objects
[i
].item
, revs
.objects
[i
].name
,
691 always
, allow_undefined
, data
.name_only
);