summaryrefslogtreecommitdiff
path: root/builtin/name-rev.c
diff options
context:
space:
mode:
Diffstat (limited to 'builtin/name-rev.c')
-rw-r--r--builtin/name-rev.c192
1 files changed, 123 insertions, 69 deletions
diff --git a/builtin/name-rev.c b/builtin/name-rev.c
index f1cb45c227..6b9e8c850b 100644
--- a/builtin/name-rev.c
+++ b/builtin/name-rev.c
@@ -6,10 +6,15 @@
#include "tag.h"
#include "refs.h"
#include "parse-options.h"
+#include "prio-queue.h"
#include "sha1-lookup.h"
#include "commit-slab.h"
-#define CUTOFF_DATE_SLOP 86400 /* one day */
+/*
+ * One day. See the 'name a rev shortly after epoch' test in t6120 when
+ * changing this value
+ */
+#define CUTOFF_DATE_SLOP 86400
typedef struct rev_name {
const char *tip_name;
@@ -40,9 +45,7 @@ static void set_commit_rev_name(struct commit *commit, struct rev_name *name)
}
static int is_better_name(struct rev_name *name,
- const char *tip_name,
timestamp_t taggerdate,
- int generation,
int distance,
int from_tag)
{
@@ -77,69 +80,116 @@ static int is_better_name(struct rev_name *name,
return 0;
}
-static void name_rev(struct commit *commit,
- const char *tip_name, timestamp_t taggerdate,
- int generation, int distance, int from_tag,
- int deref)
+static struct rev_name *create_or_update_name(struct commit *commit,
+ const char *tip_name,
+ timestamp_t taggerdate,
+ int generation, int distance,
+ int from_tag)
{
struct rev_name *name = get_commit_rev_name(commit);
- struct commit_list *parents;
- int parent_number = 1;
- char *to_free = NULL;
-
- parse_commit(commit);
-
- if (commit->date < cutoff)
- return;
-
- if (deref) {
- tip_name = to_free = xstrfmt("%s^0", tip_name);
-
- if (generation)
- die("generation: %d, but deref?", generation);
- }
if (name == NULL) {
- name = xmalloc(sizeof(rev_name));
+ name = xmalloc(sizeof(*name));
set_commit_rev_name(commit, name);
goto copy_data;
- } else if (is_better_name(name, tip_name, taggerdate,
- generation, distance, from_tag)) {
+ } else if (is_better_name(name, taggerdate, distance, from_tag)) {
copy_data:
name->tip_name = tip_name;
name->taggerdate = taggerdate;
name->generation = generation;
name->distance = distance;
name->from_tag = from_tag;
- } else {
+
+ return name;
+ } else
+ return NULL;
+}
+
+static void name_rev(struct commit *start_commit,
+ const char *tip_name, timestamp_t taggerdate,
+ int from_tag, int deref)
+{
+ struct prio_queue queue;
+ struct commit *commit;
+ struct commit **parents_to_queue = NULL;
+ size_t parents_to_queue_nr, parents_to_queue_alloc = 0;
+ char *to_free = NULL;
+
+ parse_commit(start_commit);
+ if (start_commit->date < cutoff)
+ return;
+
+ if (deref)
+ tip_name = to_free = xstrfmt("%s^0", tip_name);
+
+ if (!create_or_update_name(start_commit, tip_name, taggerdate, 0, 0,
+ from_tag)) {
free(to_free);
return;
}
- for (parents = commit->parents;
- parents;
- parents = parents->next, parent_number++) {
- if (parent_number > 1) {
- size_t len;
- char *new_name;
-
- strip_suffix(tip_name, "^0", &len);
- if (generation > 0)
- new_name = xstrfmt("%.*s~%d^%d", (int)len, tip_name,
- generation, parent_number);
- else
- new_name = xstrfmt("%.*s^%d", (int)len, tip_name,
- parent_number);
-
- name_rev(parents->item, new_name, taggerdate, 0,
- distance + MERGE_TRAVERSAL_WEIGHT,
- from_tag, 0);
- } else {
- name_rev(parents->item, tip_name, taggerdate,
- generation + 1, distance + 1,
- from_tag, 0);
+ memset(&queue, 0, sizeof(queue)); /* Use the prio_queue as LIFO */
+ prio_queue_put(&queue, start_commit);
+
+ while ((commit = prio_queue_get(&queue))) {
+ struct rev_name *name = get_commit_rev_name(commit);
+ struct commit_list *parents;
+ int parent_number = 1;
+
+ parents_to_queue_nr = 0;
+
+ for (parents = commit->parents;
+ parents;
+ parents = parents->next, parent_number++) {
+ struct commit *parent = parents->item;
+ const char *new_name;
+ int generation, distance;
+
+ parse_commit(parent);
+ if (parent->date < cutoff)
+ continue;
+
+ if (parent_number > 1) {
+ size_t len;
+
+ strip_suffix(name->tip_name, "^0", &len);
+ if (name->generation > 0)
+ new_name = xstrfmt("%.*s~%d^%d",
+ (int)len,
+ name->tip_name,
+ name->generation,
+ parent_number);
+ else
+ new_name = xstrfmt("%.*s^%d", (int)len,
+ name->tip_name,
+ parent_number);
+ generation = 0;
+ distance = name->distance + MERGE_TRAVERSAL_WEIGHT;
+ } else {
+ new_name = name->tip_name;
+ generation = name->generation + 1;
+ distance = name->distance + 1;
+ }
+
+ if (create_or_update_name(parent, new_name, taggerdate,
+ generation, distance,
+ from_tag)) {
+ ALLOC_GROW(parents_to_queue,
+ parents_to_queue_nr + 1,
+ parents_to_queue_alloc);
+ parents_to_queue[parents_to_queue_nr] = parent;
+ parents_to_queue_nr++;
+ }
}
+
+ /* The first parent must come out first from the prio_queue */
+ while (parents_to_queue_nr)
+ prio_queue_put(&queue,
+ parents_to_queue[--parents_to_queue_nr]);
}
+
+ clear_prio_queue(&queue);
+ free(parents_to_queue);
}
static int subpath_matches(const char *path, const char *filter)
@@ -160,10 +210,10 @@ static const char *name_ref_abbrev(const char *refname, int shorten_unambiguous)
{
if (shorten_unambiguous)
refname = shorten_unambiguous_ref(refname, 0);
- else if (starts_with(refname, "refs/heads/"))
- refname = refname + 11;
- else if (starts_with(refname, "refs/"))
- refname = refname + 5;
+ else if (skip_prefix(refname, "refs/heads/", &refname))
+ ; /* refname already advanced */
+ else
+ skip_prefix(refname, "refs/", &refname);
return refname;
}
@@ -271,10 +321,9 @@ static int name_ref(const char *path, const struct object_id *oid, int flags, vo
int from_tag = starts_with(path, "refs/tags/");
if (taggerdate == TIME_MAX)
- taggerdate = ((struct commit *)o)->date;
+ taggerdate = commit->date;
path = name_ref_abbrev(path, can_abbreviate_output);
- name_rev(commit, xstrdup(path), taggerdate, 0, 0,
- from_tag, deref);
+ name_rev(commit, xstrdup(path), taggerdate, from_tag, deref);
}
return 0;
}
@@ -320,11 +369,10 @@ static const char *get_rev_name(const struct object *o, struct strbuf *buf)
if (!n->generation)
return n->tip_name;
else {
- int len = strlen(n->tip_name);
- if (len > 2 && !strcmp(n->tip_name + len - 2, "^0"))
- len -= 2;
strbuf_reset(buf);
- strbuf_addf(buf, "%.*s~%d", len, n->tip_name, n->generation);
+ strbuf_addstr(buf, n->tip_name);
+ strbuf_strip_suffix(buf, "^0");
+ strbuf_addf(buf, "~%d", n->generation);
return buf->buf;
}
}
@@ -361,26 +409,27 @@ static char const * const name_rev_usage[] = {
static void name_rev_line(char *p, struct name_ref_data *data)
{
struct strbuf buf = STRBUF_INIT;
- int forty = 0;
+ int counter = 0;
char *p_start;
+ const unsigned hexsz = the_hash_algo->hexsz;
+
for (p_start = p; *p; p++) {
#define ishex(x) (isdigit((x)) || ((x) >= 'a' && (x) <= 'f'))
if (!ishex(*p))
- forty = 0;
- else if (++forty == GIT_SHA1_HEXSZ &&
+ counter = 0;
+ else if (++counter == hexsz &&
!ishex(*(p+1))) {
struct object_id oid;
const char *name = NULL;
char c = *(p+1);
int p_len = p - p_start + 1;
- forty = 0;
+ counter = 0;
*(p+1) = 0;
- if (!get_oid(p - (GIT_SHA1_HEXSZ - 1), &oid)) {
+ if (!get_oid(p - (hexsz - 1), &oid)) {
struct object *o =
- lookup_object(the_repository,
- oid.hash);
+ lookup_object(the_repository, &oid);
if (o)
name = get_rev_name(o, &buf);
}
@@ -390,7 +439,7 @@ static void name_rev_line(char *p, struct name_ref_data *data)
continue;
if (data->name_only)
- printf("%.*s%s", p_len - GIT_SHA1_HEXSZ, p_start, name);
+ printf("%.*s%s", p_len - hexsz, p_start, name);
else
printf("%.*s (%s)", p_len, p_start, name);
p_start = p + 1;
@@ -483,8 +532,13 @@ int cmd_name_rev(int argc, const char **argv, const char *prefix)
add_object_array(object, *argv, &revs);
}
- if (cutoff)
- cutoff = cutoff - CUTOFF_DATE_SLOP;
+ if (cutoff) {
+ /* check for undeflow */
+ if (cutoff > TIME_MIN + CUTOFF_DATE_SLOP)
+ cutoff = cutoff - CUTOFF_DATE_SLOP;
+ else
+ cutoff = TIME_MIN;
+ }
for_each_ref(name_ref, &data);
if (transform_stdin) {
generated by cgit v1.2.3 (git 2.25.1) at 2025-01-05 19:58:26 +0000