3 #include "repository.h"
8 #include "parse-options.h"
9 #include "prio-queue.h"
10 #include "sha1-lookup.h"
11 #include "commit-slab.h"
14 * One day. See the 'name a rev shortly after epoch' test in t6120 when
17 #define CUTOFF_DATE_SLOP 86400
21 timestamp_t taggerdate
;
27 define_commit_slab(commit_rev_name
, struct rev_name
*);
29 static timestamp_t cutoff
= TIME_MAX
;
30 static struct commit_rev_name rev_names
;
32 /* How many generations are maximally preferred over _one_ merge traversal? */
33 #define MERGE_TRAVERSAL_WEIGHT 65535
35 static struct rev_name
*get_commit_rev_name(const struct commit
*commit
)
37 struct rev_name
**slot
= commit_rev_name_peek(&rev_names
, commit
);
39 return slot
? *slot
: NULL
;
42 static void set_commit_rev_name(struct commit
*commit
, struct rev_name
*name
)
44 *commit_rev_name_at(&rev_names
, commit
) = name
;
47 static int is_better_name(struct rev_name
*name
,
48 timestamp_t taggerdate
,
53 * When comparing names based on tags, prefer names
54 * based on the older tag, even if it is farther away.
56 if (from_tag
&& name
->from_tag
)
57 return (name
->taggerdate
> taggerdate
||
58 (name
->taggerdate
== taggerdate
&&
59 name
->distance
> distance
));
62 * We know that at least one of them is a non-tag at this point.
63 * favor a tag over a non-tag.
65 if (name
->from_tag
!= from_tag
)
69 * We are now looking at two non-tags. Tiebreak to favor
72 if (name
->distance
!= distance
)
73 return name
->distance
> distance
;
75 /* ... or tiebreak to favor older date */
76 if (name
->taggerdate
!= taggerdate
)
77 return name
->taggerdate
> taggerdate
;
79 /* keep the current one if we cannot decide */
83 static struct rev_name
*create_or_update_name(struct commit
*commit
,
85 timestamp_t taggerdate
,
86 int generation
, int distance
,
89 struct rev_name
*name
= get_commit_rev_name(commit
);
91 if (name
&& !is_better_name(name
, taggerdate
, distance
, from_tag
))
95 name
= xmalloc(sizeof(*name
));
96 set_commit_rev_name(commit
, name
);
99 name
->tip_name
= tip_name
;
100 name
->taggerdate
= taggerdate
;
101 name
->generation
= generation
;
102 name
->distance
= distance
;
103 name
->from_tag
= from_tag
;
108 static void name_rev(struct commit
*start_commit
,
109 const char *tip_name
, timestamp_t taggerdate
,
110 int from_tag
, int deref
)
112 struct prio_queue queue
;
113 struct commit
*commit
;
114 struct commit
**parents_to_queue
= NULL
;
115 size_t parents_to_queue_nr
, parents_to_queue_alloc
= 0;
116 char *to_free
= NULL
;
118 parse_commit(start_commit
);
119 if (start_commit
->date
< cutoff
)
123 tip_name
= to_free
= xstrfmt("%s^0", tip_name
);
125 tip_name
= to_free
= xstrdup(tip_name
);
127 if (!create_or_update_name(start_commit
, tip_name
, taggerdate
, 0, 0,
133 memset(&queue
, 0, sizeof(queue
)); /* Use the prio_queue as LIFO */
134 prio_queue_put(&queue
, start_commit
);
136 while ((commit
= prio_queue_get(&queue
))) {
137 struct rev_name
*name
= get_commit_rev_name(commit
);
138 struct commit_list
*parents
;
139 int parent_number
= 1;
141 parents_to_queue_nr
= 0;
143 for (parents
= commit
->parents
;
145 parents
= parents
->next
, parent_number
++) {
146 struct commit
*parent
= parents
->item
;
147 const char *new_name
;
148 int generation
, distance
;
150 parse_commit(parent
);
151 if (parent
->date
< cutoff
)
154 if (parent_number
> 1) {
157 strip_suffix(name
->tip_name
, "^0", &len
);
158 if (name
->generation
> 0)
159 new_name
= xstrfmt("%.*s~%d^%d",
165 new_name
= xstrfmt("%.*s^%d", (int)len
,
169 distance
= name
->distance
+ MERGE_TRAVERSAL_WEIGHT
;
171 new_name
= name
->tip_name
;
172 generation
= name
->generation
+ 1;
173 distance
= name
->distance
+ 1;
176 if (create_or_update_name(parent
, new_name
, taggerdate
,
177 generation
, distance
,
179 ALLOC_GROW(parents_to_queue
,
180 parents_to_queue_nr
+ 1,
181 parents_to_queue_alloc
);
182 parents_to_queue
[parents_to_queue_nr
] = parent
;
183 parents_to_queue_nr
++;
187 /* The first parent must come out first from the prio_queue */
188 while (parents_to_queue_nr
)
189 prio_queue_put(&queue
,
190 parents_to_queue
[--parents_to_queue_nr
]);
193 clear_prio_queue(&queue
);
194 free(parents_to_queue
);
197 static int subpath_matches(const char *path
, const char *filter
)
199 const char *subpath
= path
;
202 if (!wildmatch(filter
, subpath
, 0))
203 return subpath
- path
;
204 subpath
= strchr(subpath
, '/');
211 static const char *name_ref_abbrev(const char *refname
, int shorten_unambiguous
)
213 if (shorten_unambiguous
)
214 refname
= shorten_unambiguous_ref(refname
, 0);
215 else if (skip_prefix(refname
, "refs/heads/", &refname
))
216 ; /* refname already advanced */
218 skip_prefix(refname
, "refs/", &refname
);
222 struct name_ref_data
{
225 struct string_list ref_filters
;
226 struct string_list exclude_filters
;
229 static struct tip_table
{
230 struct tip_table_entry
{
231 struct object_id oid
;
239 static void add_to_tip_table(const struct object_id
*oid
, const char *refname
,
240 int shorten_unambiguous
)
242 refname
= name_ref_abbrev(refname
, shorten_unambiguous
);
244 ALLOC_GROW(tip_table
.table
, tip_table
.nr
+ 1, tip_table
.alloc
);
245 oidcpy(&tip_table
.table
[tip_table
.nr
].oid
, oid
);
246 tip_table
.table
[tip_table
.nr
].refname
= xstrdup(refname
);
248 tip_table
.sorted
= 0;
251 static int tipcmp(const void *a_
, const void *b_
)
253 const struct tip_table_entry
*a
= a_
, *b
= b_
;
254 return oidcmp(&a
->oid
, &b
->oid
);
257 static int name_ref(const char *path
, const struct object_id
*oid
, int flags
, void *cb_data
)
259 struct object
*o
= parse_object(the_repository
, oid
);
260 struct name_ref_data
*data
= cb_data
;
261 int can_abbreviate_output
= data
->tags_only
&& data
->name_only
;
263 timestamp_t taggerdate
= TIME_MAX
;
265 if (data
->tags_only
&& !starts_with(path
, "refs/tags/"))
268 if (data
->exclude_filters
.nr
) {
269 struct string_list_item
*item
;
271 for_each_string_list_item(item
, &data
->exclude_filters
) {
272 if (subpath_matches(path
, item
->string
) >= 0)
277 if (data
->ref_filters
.nr
) {
278 struct string_list_item
*item
;
281 /* See if any of the patterns match. */
282 for_each_string_list_item(item
, &data
->ref_filters
) {
284 * Check all patterns even after finding a match, so
285 * that we can see if a match with a subpath exists.
286 * When a user asked for 'refs/tags/v*' and 'v1.*',
287 * both of which match, the user is showing her
288 * willingness to accept a shortened output by having
289 * the 'v1.*' in the acceptable refnames, so we
290 * shouldn't stop when seeing 'refs/tags/v1.4' matches
291 * 'refs/tags/v*'. We should show it as 'v1.4'.
293 switch (subpath_matches(path
, item
->string
)) {
294 case -1: /* did not match */
296 case 0: /* matched fully */
299 default: /* matched subpath */
301 can_abbreviate_output
= 1;
306 /* If none of the patterns matched, stop now */
311 add_to_tip_table(oid
, path
, can_abbreviate_output
);
313 while (o
&& o
->type
== OBJ_TAG
) {
314 struct tag
*t
= (struct tag
*) o
;
316 break; /* broken repository */
317 o
= parse_object(the_repository
, &t
->tagged
->oid
);
319 taggerdate
= t
->date
;
321 if (o
&& o
->type
== OBJ_COMMIT
) {
322 struct commit
*commit
= (struct commit
*)o
;
323 int from_tag
= starts_with(path
, "refs/tags/");
325 if (taggerdate
== TIME_MAX
)
326 taggerdate
= commit
->date
;
327 path
= name_ref_abbrev(path
, can_abbreviate_output
);
328 name_rev(commit
, path
, taggerdate
, from_tag
, deref
);
333 static const unsigned char *nth_tip_table_ent(size_t ix
, void *table_
)
335 struct tip_table_entry
*table
= table_
;
336 return table
[ix
].oid
.hash
;
339 static const char *get_exact_ref_match(const struct object
*o
)
343 if (!tip_table
.table
|| !tip_table
.nr
)
346 if (!tip_table
.sorted
) {
347 QSORT(tip_table
.table
, tip_table
.nr
, tipcmp
);
348 tip_table
.sorted
= 1;
351 found
= sha1_pos(o
->oid
.hash
, tip_table
.table
, tip_table
.nr
,
354 return tip_table
.table
[found
].refname
;
358 /* may return a constant string or use "buf" as scratch space */
359 static const char *get_rev_name(const struct object
*o
, struct strbuf
*buf
)
362 const struct commit
*c
;
364 if (o
->type
!= OBJ_COMMIT
)
365 return get_exact_ref_match(o
);
366 c
= (const struct commit
*) o
;
367 n
= get_commit_rev_name(c
);
375 strbuf_addstr(buf
, n
->tip_name
);
376 strbuf_strip_suffix(buf
, "^0");
377 strbuf_addf(buf
, "~%d", n
->generation
);
382 static void show_name(const struct object
*obj
,
383 const char *caller_name
,
384 int always
, int allow_undefined
, int name_only
)
387 const struct object_id
*oid
= &obj
->oid
;
388 struct strbuf buf
= STRBUF_INIT
;
391 printf("%s ", caller_name
? caller_name
: oid_to_hex(oid
));
392 name
= get_rev_name(obj
, &buf
);
394 printf("%s\n", name
);
395 else if (allow_undefined
)
396 printf("undefined\n");
398 printf("%s\n", find_unique_abbrev(oid
, DEFAULT_ABBREV
));
400 die("cannot describe '%s'", oid_to_hex(oid
));
401 strbuf_release(&buf
);
404 static char const * const name_rev_usage
[] = {
405 N_("git name-rev [<options>] <commit>..."),
406 N_("git name-rev [<options>] --all"),
407 N_("git name-rev [<options>] --stdin"),
411 static void name_rev_line(char *p
, struct name_ref_data
*data
)
413 struct strbuf buf
= STRBUF_INIT
;
416 const unsigned hexsz
= the_hash_algo
->hexsz
;
418 for (p_start
= p
; *p
; p
++) {
419 #define ishex(x) (isdigit((x)) || ((x) >= 'a' && (x) <= 'f'))
422 else if (++counter
== hexsz
&&
424 struct object_id oid
;
425 const char *name
= NULL
;
427 int p_len
= p
- p_start
+ 1;
432 if (!get_oid(p
- (hexsz
- 1), &oid
)) {
434 lookup_object(the_repository
, &oid
);
436 name
= get_rev_name(o
, &buf
);
444 printf("%.*s%s", p_len
- hexsz
, p_start
, name
);
446 printf("%.*s (%s)", p_len
, p_start
, name
);
453 fwrite(p_start
, p
- p_start
, 1, stdout
);
455 strbuf_release(&buf
);
458 int cmd_name_rev(int argc
, const char **argv
, const char *prefix
)
460 struct object_array revs
= OBJECT_ARRAY_INIT
;
461 int all
= 0, transform_stdin
= 0, allow_undefined
= 1, always
= 0, peel_tag
= 0;
462 struct name_ref_data data
= { 0, 0, STRING_LIST_INIT_NODUP
, STRING_LIST_INIT_NODUP
};
463 struct option opts
[] = {
464 OPT_BOOL(0, "name-only", &data
.name_only
, N_("print only names (no SHA-1)")),
465 OPT_BOOL(0, "tags", &data
.tags_only
, N_("only use tags to name the commits")),
466 OPT_STRING_LIST(0, "refs", &data
.ref_filters
, N_("pattern"),
467 N_("only use refs matching <pattern>")),
468 OPT_STRING_LIST(0, "exclude", &data
.exclude_filters
, N_("pattern"),
469 N_("ignore refs matching <pattern>")),
471 OPT_BOOL(0, "all", &all
, N_("list all commits reachable from all refs")),
472 OPT_BOOL(0, "stdin", &transform_stdin
, N_("read from stdin")),
473 OPT_BOOL(0, "undefined", &allow_undefined
, N_("allow to print `undefined` names (default)")),
474 OPT_BOOL(0, "always", &always
,
475 N_("show abbreviated commit object as fallback")),
477 /* A Hidden OPT_BOOL */
478 OPTION_SET_INT
, 0, "peel-tag", &peel_tag
, NULL
,
479 N_("dereference tags in the input (internal use)"),
480 PARSE_OPT_NOARG
| PARSE_OPT_HIDDEN
, NULL
, 1,
485 init_commit_rev_name(&rev_names
);
486 git_config(git_default_config
, NULL
);
487 argc
= parse_options(argc
, argv
, prefix
, opts
, name_rev_usage
, 0);
488 if (all
+ transform_stdin
+ !!argc
> 1) {
489 error("Specify either a list, or --all, not both!");
490 usage_with_options(name_rev_usage
, opts
);
492 if (all
|| transform_stdin
)
495 for (; argc
; argc
--, argv
++) {
496 struct object_id oid
;
497 struct object
*object
;
498 struct commit
*commit
;
500 if (get_oid(*argv
, &oid
)) {
501 fprintf(stderr
, "Could not get sha1 for %s. Skipping.\n",
507 object
= parse_object(the_repository
, &oid
);
509 struct object
*peeled
= deref_tag(the_repository
,
511 if (peeled
&& peeled
->type
== OBJ_COMMIT
)
512 commit
= (struct commit
*)peeled
;
516 fprintf(stderr
, "Could not get object for %s. Skipping.\n",
522 if (cutoff
> commit
->date
)
523 cutoff
= commit
->date
;
528 fprintf(stderr
, "Could not get commit for %s. Skipping.\n",
532 object
= (struct object
*)commit
;
534 add_object_array(object
, *argv
, &revs
);
538 /* check for undeflow */
539 if (cutoff
> TIME_MIN
+ CUTOFF_DATE_SLOP
)
540 cutoff
= cutoff
- CUTOFF_DATE_SLOP
;
544 for_each_ref(name_ref
, &data
);
546 if (transform_stdin
) {
549 while (!feof(stdin
)) {
550 char *p
= fgets(buffer
, sizeof(buffer
), stdin
);
553 name_rev_line(p
, &data
);
558 max
= get_max_object_index();
559 for (i
= 0; i
< max
; i
++) {
560 struct object
*obj
= get_indexed_object(i
);
561 if (!obj
|| obj
->type
!= OBJ_COMMIT
)
564 always
, allow_undefined
, data
.name_only
);
568 for (i
= 0; i
< revs
.nr
; i
++)
569 show_name(revs
.objects
[i
].item
, revs
.objects
[i
].name
,
570 always
, allow_undefined
, data
.name_only
);