2 * Copyright (C) the libgit2 contributors. All rights reserved.
4 * This file is part of libgit2, distributed under the GNU GPL v2 with
5 * a Linking Exception. For full terms see the included COPYING file.
7 #include "git2/describe.h"
8 #include "git2/strarray.h"
10 #include "git2/status.h"
14 #include "commit_list.h"
20 #include "repository.h"
24 /* Ported from https://github.com/git/git/blob/89dde7882f71f846ccd0359756d27bebc31108de/builtin/describe.c */
28 unsigned prio
:2; /* annotated tag = 2, tag = 1, head = 0 */
29 unsigned name_checked
:1;
33 /* Khash workaround. They original key has to still be reachable */
37 static void *oidmap_value_bykey(git_oidmap
*map
, const git_oid
*key
)
39 khint_t pos
= git_oidmap_lookup_index(map
, key
);
41 if (!git_oidmap_valid_index(map
, pos
))
44 return git_oidmap_value_at(map
, pos
);
47 static struct commit_name
*find_commit_name(
49 const git_oid
*peeled
)
51 return (struct commit_name
*)(oidmap_value_bykey(names
, peeled
));
54 static int replace_name(
57 struct commit_name
*e
,
61 git_time_t e_time
= 0, t_time
= 0;
63 if (!e
|| e
->prio
< prio
)
66 if (e
->prio
== 2 && prio
== 2) {
67 /* Multiple annotated tags point to the same commit.
68 * Select one to keep based upon their tagger date.
73 if (git_tag_lookup(&t
, repo
, &e
->sha1
) < 0)
78 if (git_tag_lookup(&t
, repo
, sha1
) < 0)
84 e_time
= e
->tag
->tagger
->when
.time
;
87 t_time
= t
->tagger
->when
.time
;
96 static int add_to_known_names(
100 const git_oid
*peeled
,
104 struct commit_name
*e
= find_commit_name(names
, peeled
);
105 bool found
= (e
!= NULL
);
108 if (replace_name(&tag
, repo
, e
, prio
, sha1
)) {
110 e
= git__malloc(sizeof(struct commit_name
));
111 GITERR_CHECK_ALLOC(e
);
118 git_tag_free(e
->tag
);
122 git_oid_cpy(&e
->sha1
, sha1
);
124 e
->path
= git__strdup(path
);
125 git_oid_cpy(&e
->peeled
, peeled
);
130 git_oidmap_insert(names
, &e
->peeled
, e
, ret
);
141 static int retrieve_peeled_tag_or_object_oid(
143 git_oid
*ref_target_out
,
144 git_repository
*repo
,
148 git_object
*peeled
= NULL
;
151 if ((error
= git_reference_lookup_resolved(&ref
, repo
, refname
, -1)) < 0)
154 if ((error
= git_reference_peel(&peeled
, ref
, GIT_OBJ_ANY
)) < 0)
157 git_oid_cpy(ref_target_out
, git_reference_target(ref
));
158 git_oid_cpy(peeled_out
, git_object_id(peeled
));
160 if (git_oid_cmp(ref_target_out
, peeled_out
) != 0)
161 error
= 1; /* The reference was pointing to a annotated tag */
163 error
= 0; /* Any other object */
166 git_reference_free(ref
);
167 git_object_free(peeled
);
171 struct git_describe_result
{
176 git_repository
*repo
;
177 struct commit_name
*name
;
178 struct possible_tag
*tag
;
183 git_describe_options
*opts
;
184 git_repository
*repo
;
186 git_describe_result
*result
;
189 static int commit_name_dup(struct commit_name
**out
, struct commit_name
*in
)
191 struct commit_name
*name
;
193 name
= git__malloc(sizeof(struct commit_name
));
194 GITERR_CHECK_ALLOC(name
);
196 memcpy(name
, in
, sizeof(struct commit_name
));
200 if (in
->tag
&& git_object_dup((git_object
**) &name
->tag
, (git_object
*) in
->tag
) < 0)
203 name
->path
= git__strdup(in
->path
);
204 GITERR_CHECK_ALLOC(name
->path
);
210 static int get_name(const char *refname
, void *payload
)
212 struct get_name_data
*data
;
213 bool is_tag
, is_annotated
, all
;
214 git_oid peeled
, sha1
;
218 data
= (struct get_name_data
*)payload
;
219 is_tag
= !git__prefixcmp(refname
, GIT_REFS_TAGS_DIR
);
220 all
= data
->opts
->describe_strategy
== GIT_DESCRIBE_ALL
;
222 /* Reject anything outside refs/tags/ unless --all */
226 /* Accept only tags that match the pattern, if given */
227 if (data
->opts
->pattern
&& (!is_tag
|| p_fnmatch(data
->opts
->pattern
,
228 refname
+ strlen(GIT_REFS_TAGS_DIR
), 0)))
231 /* Is it annotated? */
232 if ((error
= retrieve_peeled_tag_or_object_oid(
233 &peeled
, &sha1
, data
->repo
, refname
)) < 0)
236 is_annotated
= error
;
239 * By default, we only use annotated tags, but with --tags
240 * we fall back to lightweight ones (even without --tags,
241 * we still remember lightweight ones, only to give hints
242 * in an error message). --all allows any refs to be used.
251 add_to_known_names(data
->repo
, data
->names
,
252 all
? refname
+ strlen(GIT_REFS_DIR
) : refname
+ strlen(GIT_REFS_TAGS_DIR
),
253 &peeled
, prio
, &sha1
);
257 struct possible_tag
{
258 struct commit_name
*name
;
261 unsigned flag_within
;
264 static int possible_tag_dup(struct possible_tag
**out
, struct possible_tag
*in
)
266 struct possible_tag
*tag
;
269 tag
= git__malloc(sizeof(struct possible_tag
));
270 GITERR_CHECK_ALLOC(tag
);
272 memcpy(tag
, in
, sizeof(struct possible_tag
));
275 if ((error
= commit_name_dup(&tag
->name
, in
->name
)) < 0) {
285 static int compare_pt(const void *a_
, const void *b_
)
287 struct possible_tag
*a
= (struct possible_tag
*)a_
;
288 struct possible_tag
*b
= (struct possible_tag
*)b_
;
289 if (a
->depth
!= b
->depth
)
290 return a
->depth
- b
->depth
;
291 if (a
->found_order
!= b
->found_order
)
292 return a
->found_order
- b
->found_order
;
296 #define SEEN (1u << 0)
298 static unsigned long finish_depth_computation(
301 struct possible_tag
*best
)
303 unsigned long seen_commits
= 0;
306 while (git_pqueue_size(list
) > 0) {
307 git_commit_list_node
*c
= git_pqueue_pop(list
);
309 if (c
->flags
& best
->flag_within
) {
311 while (git_pqueue_size(list
) > index
) {
312 git_commit_list_node
*i
= git_pqueue_get(list
, index
);
313 if (!(i
->flags
& best
->flag_within
))
317 if (index
> git_pqueue_size(list
))
321 for (i
= 0; i
< c
->out_degree
; i
++) {
322 git_commit_list_node
*p
= c
->parents
[i
];
323 if ((error
= git_commit_list_parse(walk
, p
)) < 0)
325 if (!(p
->flags
& SEEN
))
326 if ((error
= git_pqueue_insert(list
, p
)) < 0)
328 p
->flags
|= c
->flags
;
334 static int display_name(git_buf
*buf
, git_repository
*repo
, struct commit_name
*n
)
336 if (n
->prio
== 2 && !n
->tag
) {
337 if (git_tag_lookup(&n
->tag
, repo
, &n
->sha1
) < 0) {
338 giterr_set(GITERR_TAG
, "Annotated tag '%s' not available", n
->path
);
343 if (n
->tag
&& !n
->name_checked
) {
344 if (!git_tag_name(n
->tag
)) {
345 giterr_set(GITERR_TAG
, "Annotated tag '%s' has no embedded name", n
->path
);
349 /* TODO: Cope with warnings
350 if (strcmp(n->tag->tag, all ? n->path + 5 : n->path))
351 warning(_("tag '%s' is really '%s' here"), n->tag->tag, n->path);
358 git_buf_printf(buf
, "%s", git_tag_name(n
->tag
));
360 git_buf_printf(buf
, "%s", n
->path
);
365 static int find_unique_abbrev_size(
367 git_repository
*repo
,
368 const git_oid
*oid_in
,
369 int abbreviated_size
)
371 size_t size
= abbreviated_size
;
376 if ((error
= git_repository_odb__weakptr(&odb
, repo
)) < 0)
379 while (size
< GIT_OID_HEXSZ
) {
380 if ((error
= git_odb_exists_prefix(&dummy
, odb
, oid_in
, size
)) == 0) {
385 /* If the error wasn't that it's not unique, then it's a proper error */
386 if (error
!= GIT_EAMBIGUOUS
)
389 /* Try again with a larger size */
393 /* If we didn't find any shorter prefix, we have to do the whole thing */
394 *out
= GIT_OID_HEXSZ
;
399 static int show_suffix(
402 git_repository
*repo
,
408 char hex_oid
[GIT_OID_HEXSZ
];
410 if ((error
= find_unique_abbrev_size(&size
, repo
, id
, abbrev_size
)) < 0)
413 git_oid_fmt(hex_oid
, id
);
415 git_buf_printf(buf
, "-%d-g", depth
);
417 git_buf_put(buf
, hex_oid
, size
);
419 return git_buf_oom(buf
) ? -1 : 0;
422 #define MAX_CANDIDATES_TAGS FLAG_BITS - 1
424 static int describe_not_found(const git_oid
*oid
, const char *message_format
) {
425 char oid_str
[GIT_OID_HEXSZ
+ 1];
426 git_oid_tostr(oid_str
, sizeof(oid_str
), oid
);
428 giterr_set(GITERR_DESCRIBE
, message_format
, oid_str
);
429 return GIT_ENOTFOUND
;
433 struct get_name_data
*data
,
436 struct commit_name
*n
;
437 struct possible_tag
*best
;
439 git_revwalk
*walk
= NULL
;
441 git_commit_list_node
*cmit
, *gave_up_on
= NULL
;
442 git_vector all_matches
= GIT_VECTOR_INIT
;
443 unsigned int match_cnt
= 0, annotated_cnt
= 0, cur_match
;
444 unsigned long seen_commits
= 0; /* TODO: Check long */
445 unsigned int unannotated_cnt
= 0;
448 if (git_vector_init(&all_matches
, MAX_CANDIDATES_TAGS
, compare_pt
) < 0)
451 if ((error
= git_pqueue_init(&list
, 0, 2, git_commit_list_time_cmp
)) < 0)
454 all
= data
->opts
->describe_strategy
== GIT_DESCRIBE_ALL
;
455 tags
= data
->opts
->describe_strategy
== GIT_DESCRIBE_TAGS
;
457 git_oid_cpy(&data
->result
->commit_id
, git_commit_id(commit
));
459 n
= find_commit_name(data
->names
, git_commit_id(commit
));
460 if (n
&& (tags
|| all
|| n
->prio
== 2)) {
462 * Exact match to an existing ref.
464 data
->result
->exact_match
= 1;
465 if ((error
= commit_name_dup(&data
->result
->name
, n
)) < 0)
471 if (!data
->opts
->max_candidates_tags
) {
472 error
= describe_not_found(
473 git_commit_id(commit
),
474 "Cannot describe - no tag exactly matches '%s'");
479 if ((error
= git_revwalk_new(&walk
, git_commit_owner(commit
))) < 0)
482 if ((cmit
= git_revwalk__commit_lookup(walk
, git_commit_id(commit
))) == NULL
)
485 if ((error
= git_commit_list_parse(walk
, cmit
)) < 0)
490 if ((error
= git_pqueue_insert(&list
, cmit
)) < 0)
493 while (git_pqueue_size(&list
) > 0)
497 git_commit_list_node
*c
= (git_commit_list_node
*)git_pqueue_pop(&list
);
500 n
= find_commit_name(data
->names
, &c
->oid
);
503 if (!tags
&& !all
&& n
->prio
< 2) {
505 } else if (match_cnt
< data
->opts
->max_candidates_tags
) {
506 struct possible_tag
*t
= git__malloc(sizeof(struct commit_name
));
507 GITERR_CHECK_ALLOC(t
);
508 if ((error
= git_vector_insert(&all_matches
, t
)) < 0)
514 t
->depth
= seen_commits
- 1;
515 t
->flag_within
= 1u << match_cnt
;
516 t
->found_order
= match_cnt
;
517 c
->flags
|= t
->flag_within
;
527 for (cur_match
= 0; cur_match
< match_cnt
; cur_match
++) {
528 struct possible_tag
*t
= git_vector_get(&all_matches
, cur_match
);
529 if (!(c
->flags
& t
->flag_within
))
533 if (annotated_cnt
&& (git_pqueue_size(&list
) == 0)) {
536 char oid_str[GIT_OID_HEXSZ + 1];
537 git_oid_tostr(oid_str, sizeof(oid_str), &c->oid);
539 fprintf(stderr, "finished search at %s\n", oid_str);
544 for (i
= 0; i
< c
->out_degree
; i
++) {
545 git_commit_list_node
*p
= c
->parents
[i
];
546 if ((error
= git_commit_list_parse(walk
, p
)) < 0)
548 if (!(p
->flags
& SEEN
))
549 if ((error
= git_pqueue_insert(&list
, p
)) < 0)
551 p
->flags
|= c
->flags
;
553 if (data
->opts
->only_follow_first_parent
)
559 if (data
->opts
->show_commit_oid_as_fallback
) {
560 data
->result
->fallback_to_id
= 1;
561 git_oid_cpy(&data
->result
->commit_id
, &cmit
->oid
);
565 if (unannotated_cnt
) {
566 error
= describe_not_found(git_commit_id(commit
),
568 "No annotated tags can describe '%s'."
569 "However, there were unannotated tags.");
573 error
= describe_not_found(git_commit_id(commit
),
575 "No tags can describe '%s'.");
580 git_vector_sort(&all_matches
);
582 best
= (struct possible_tag
*)git_vector_get(&all_matches
, 0);
585 git_pqueue_insert(&list
, gave_up_on
);
588 if ((error
= finish_depth_computation(
589 &list
, walk
, best
)) < 0)
592 seen_commits
+= error
;
593 if ((error
= possible_tag_dup(&data
->result
->tag
, best
)) < 0)
598 static const char *prio_names[] = {
599 "head", "lightweight", "annotated",
602 char oid_str[GIT_OID_HEXSZ + 1];
605 for (cur_match = 0; cur_match < match_cnt; cur_match++) {
606 struct possible_tag *t = (struct possible_tag *)git_vector_get(&all_matches, cur_match);
607 fprintf(stderr, " %-11s %8d %s\n",
608 prio_names[t->name->prio],
609 t->depth, t->name->path);
611 fprintf(stderr, "traversed %lu commits\n", seen_commits);
613 git_oid_tostr(oid_str, sizeof(oid_str), &gave_up_on->oid);
615 "more than %i tags found; listed %i most recent\n"
616 "gave up search at %s\n",
617 data->opts->max_candidates_tags, data->opts->max_candidates_tags,
624 git_oid_cpy(&data
->result
->commit_id
, &cmit
->oid
);
629 struct possible_tag
*match
;
630 git_vector_foreach(&all_matches
, i
, match
) {
634 git_vector_free(&all_matches
);
635 git_pqueue_free(&list
);
636 git_revwalk_free(walk
);
640 static int normalize_options(
641 git_describe_options
*dst
,
642 const git_describe_options
*src
)
644 git_describe_options default_options
= GIT_DESCRIBE_OPTIONS_INIT
;
645 if (!src
) src
= &default_options
;
649 if (dst
->max_candidates_tags
> GIT_DESCRIBE_DEFAULT_MAX_CANDIDATES_TAGS
)
650 dst
->max_candidates_tags
= GIT_DESCRIBE_DEFAULT_MAX_CANDIDATES_TAGS
;
655 int git_describe_commit(
656 git_describe_result
**result
,
657 git_object
*committish
,
658 git_describe_options
*opts
)
660 struct get_name_data data
;
661 struct commit_name
*name
;
664 git_describe_options normalized
;
668 data
.result
= git__calloc(1, sizeof(git_describe_result
));
669 GITERR_CHECK_ALLOC(data
.result
);
670 data
.result
->repo
= git_object_owner(committish
);
672 data
.repo
= git_object_owner(committish
);
674 if ((error
= normalize_options(&normalized
, opts
)) < 0)
677 GITERR_CHECK_VERSION(
679 GIT_DESCRIBE_OPTIONS_VERSION
,
680 "git_describe_options");
681 data
.opts
= &normalized
;
683 data
.names
= git_oidmap_alloc();
684 GITERR_CHECK_ALLOC(data
.names
);
686 /** TODO: contains to be implemented */
688 if ((error
= git_object_peel((git_object
**)(&commit
), committish
, GIT_OBJ_COMMIT
)) < 0)
691 if ((error
= git_reference_foreach_name(
692 git_object_owner(committish
),
693 get_name
, &data
)) < 0)
696 if (git_oidmap_size(data
.names
) == 0 && !opts
->show_commit_oid_as_fallback
) {
697 giterr_set(GITERR_DESCRIBE
, "Cannot describe - "
698 "No reference found, cannot describe anything.");
703 if ((error
= describe(&data
, commit
)) < 0)
707 git_commit_free(commit
);
709 git_oidmap_foreach_value(data
.names
, name
, {
710 git_tag_free(name
->tag
);
711 git__free(name
->path
);
715 git_oidmap_free(data
.names
);
718 git_describe_result_free(data
.result
);
720 *result
= data
.result
;
725 int git_describe_workdir(
726 git_describe_result
**out
,
727 git_repository
*repo
,
728 git_describe_options
*opts
)
732 git_status_list
*status
= NULL
;
733 git_status_options status_opts
= GIT_STATUS_OPTIONS_INIT
;
734 git_describe_result
*result
= NULL
;
737 if ((error
= git_reference_name_to_id(¤t_id
, repo
, GIT_HEAD_FILE
)) < 0)
740 if ((error
= git_object_lookup(&commit
, repo
, ¤t_id
, GIT_OBJ_COMMIT
)) < 0)
743 /* The first step is to perform a describe of HEAD, so we can leverage this */
744 if ((error
= git_describe_commit(&result
, commit
, opts
)) < 0)
747 if ((error
= git_status_list_new(&status
, repo
, &status_opts
)) < 0)
751 if (git_status_list_entrycount(status
) > 0)
755 git_object_free(commit
);
756 git_status_list_free(status
);
759 git_describe_result_free(result
);
766 static int normalize_format_options(
767 git_describe_format_options
*dst
,
768 const git_describe_format_options
*src
)
771 git_describe_init_format_options(dst
, GIT_DESCRIBE_FORMAT_OPTIONS_VERSION
);
775 memcpy(dst
, src
, sizeof(git_describe_format_options
));
779 int git_describe_format(git_buf
*out
, const git_describe_result
*result
, const git_describe_format_options
*given
)
782 git_repository
*repo
;
783 struct commit_name
*name
;
784 git_describe_format_options opts
;
786 assert(out
&& result
);
788 GITERR_CHECK_VERSION(given
, GIT_DESCRIBE_FORMAT_OPTIONS_VERSION
, "git_describe_format_options");
789 normalize_format_options(&opts
, given
);
791 git_buf_sanitize(out
);
794 if (opts
.always_use_long_format
&& opts
.abbreviated_size
== 0) {
795 giterr_set(GITERR_DESCRIBE
, "Cannot describe - "
796 "'always_use_long_format' is incompatible with a zero"
797 "'abbreviated_size'");
804 /* If we did find an exact match, then it's the easier method */
805 if (result
->exact_match
) {
807 if ((error
= display_name(out
, repo
, name
)) < 0)
810 if (opts
.always_use_long_format
) {
811 const git_oid
*id
= name
->tag
? git_tag_target_id(name
->tag
) : &result
->commit_id
;
812 if ((error
= show_suffix(out
, 0, repo
, id
, opts
.abbreviated_size
)) < 0)
816 if (result
->dirty
&& opts
.dirty_suffix
)
817 git_buf_puts(out
, opts
.dirty_suffix
);
819 return git_buf_oom(out
) ? -1 : 0;
822 /* If we didn't find *any* tags, we fall back to the commit's id */
823 if (result
->fallback_to_id
) {
824 char hex_oid
[GIT_OID_HEXSZ
+ 1] = {0};
827 if ((error
= find_unique_abbrev_size(
828 &size
, repo
, &result
->commit_id
, opts
.abbreviated_size
)) < 0)
831 git_oid_fmt(hex_oid
, &result
->commit_id
);
832 git_buf_put(out
, hex_oid
, size
);
834 if (result
->dirty
&& opts
.dirty_suffix
)
835 git_buf_puts(out
, opts
.dirty_suffix
);
837 return git_buf_oom(out
) ? -1 : 0;
840 /* Lastly, if we found a matching tag, we show that */
841 name
= result
->tag
->name
;
843 if ((error
= display_name(out
, repo
, name
)) < 0)
846 if (opts
.abbreviated_size
) {
847 if ((error
= show_suffix(out
, result
->tag
->depth
, repo
,
848 &result
->commit_id
, opts
.abbreviated_size
)) < 0)
852 if (result
->dirty
&& opts
.dirty_suffix
) {
853 git_buf_puts(out
, opts
.dirty_suffix
);
856 return git_buf_oom(out
) ? -1 : 0;
859 void git_describe_result_free(git_describe_result
*result
)
865 git_tag_free(result
->name
->tag
);
866 git__free(result
->name
->path
);
867 git__free(result
->name
);
871 git_tag_free(result
->tag
->name
->tag
);
872 git__free(result
->tag
->name
->path
);
873 git__free(result
->tag
->name
);
874 git__free(result
->tag
);
880 int git_describe_init_options(git_describe_options
*opts
, unsigned int version
)
882 GIT_INIT_STRUCTURE_FROM_TEMPLATE(
883 opts
, version
, git_describe_options
, GIT_DESCRIBE_OPTIONS_INIT
);
887 int git_describe_init_format_options(git_describe_format_options
*opts
, unsigned int version
)
889 GIT_INIT_STRUCTURE_FROM_TEMPLATE(
890 opts
, version
, git_describe_format_options
, GIT_DESCRIBE_FORMAT_OPTIONS_INIT
);