git

1
#include "builtin.h"
2
#include "environment.h"
3
#include "gettext.h"
4
#include "hex.h"
5
#include "repository.h"
6
#include "config.h"
7
#include "commit.h"
8
#include "tag.h"
9
#include "refs.h"
10
#include "object-name.h"
11
#include "pager.h"
12
#include "parse-options.h"
13
#include "prio-queue.h"
14
#include "hash-lookup.h"
15
#include "commit-slab.h"
16
#include "commit-graph.h"
17
#include "wildmatch.h"
18
#include "mem-pool.h"
19

20
/*
21
 * One day.  See the 'name a rev shortly after epoch' test in t6120 when
22
 * changing this value
23
 */
24
#define CUTOFF_DATE_SLOP 86400
25

26
struct rev_name {
27
	const char *tip_name;
28
	timestamp_t taggerdate;
29
	int generation;
30
	int distance;
31
	int from_tag;
32
};
33

34
define_commit_slab(commit_rev_name, struct rev_name);
35

36
static timestamp_t generation_cutoff = GENERATION_NUMBER_INFINITY;
37
static timestamp_t cutoff = TIME_MAX;
38
static struct commit_rev_name rev_names;
39

40
/* Disable the cutoff checks entirely */
41
static void disable_cutoff(void)
42
{
43
	generation_cutoff = 0;
44
	cutoff = 0;
45
}
46

47
/* Cutoff searching any commits older than this one */
48
static void set_commit_cutoff(struct commit *commit)
49
{
50

51
	if (cutoff > commit->date)
52
		cutoff = commit->date;
53

54
	if (generation_cutoff) {
55
		timestamp_t generation = commit_graph_generation(commit);
56

57
		if (generation_cutoff > generation)
58
			generation_cutoff = generation;
59
	}
60
}
61

62
/* adjust the commit date cutoff with a slop to allow for slightly incorrect
63
 * commit timestamps in case of clock skew.
64
 */
65
static void adjust_cutoff_timestamp_for_slop(void)
66
{
67
	if (cutoff) {
68
		/* check for undeflow */
69
		if (cutoff > TIME_MIN + CUTOFF_DATE_SLOP)
70
			cutoff = cutoff - CUTOFF_DATE_SLOP;
71
		else
72
			cutoff = TIME_MIN;
73
	}
74
}
75

76
/* Check if a commit is before the cutoff. Prioritize generation numbers
77
 * first, but use the commit timestamp if we lack generation data.
78
 */
79
static int commit_is_before_cutoff(struct commit *commit)
80
{
81
	if (generation_cutoff < GENERATION_NUMBER_INFINITY)
82
		return generation_cutoff &&
83
			commit_graph_generation(commit) < generation_cutoff;
84

85
	return commit->date < cutoff;
86
}
87

88
/* How many generations are maximally preferred over _one_ merge traversal? */
89
#define MERGE_TRAVERSAL_WEIGHT 65535
90

91
static int is_valid_rev_name(const struct rev_name *name)
92
{
93
	return name && name->tip_name;
94
}
95

96
static struct rev_name *get_commit_rev_name(const struct commit *commit)
97
{
98
	struct rev_name *name = commit_rev_name_peek(&rev_names, commit);
99

100
	return is_valid_rev_name(name) ? name : NULL;
101
}
102

103
static int effective_distance(int distance, int generation)
104
{
105
	return distance + (generation > 0 ? MERGE_TRAVERSAL_WEIGHT : 0);
106
}
107

108
static int is_better_name(struct rev_name *name,
109
			  timestamp_t taggerdate,
110
			  int generation,
111
			  int distance,
112
			  int from_tag)
113
{
114
	int name_distance = effective_distance(name->distance, name->generation);
115
	int new_distance = effective_distance(distance, generation);
116

117
	/* If both are tags, we prefer the nearer one. */
118
	if (from_tag && name->from_tag)
119
		return name_distance > new_distance;
120

121
	/* Favor a tag over a non-tag. */
122
	if (name->from_tag != from_tag)
123
		return from_tag;
124

125
	/*
126
	 * We are now looking at two non-tags.  Tiebreak to favor
127
	 * shorter hops.
128
	 */
129
	if (name_distance != new_distance)
130
		return name_distance > new_distance;
131

132
	/* ... or tiebreak to favor older date */
133
	if (name->taggerdate != taggerdate)
134
		return name->taggerdate > taggerdate;
135

136
	/* keep the current one if we cannot decide */
137
	return 0;
138
}
139

140
static struct rev_name *create_or_update_name(struct commit *commit,
141
					      timestamp_t taggerdate,
142
					      int generation, int distance,
143
					      int from_tag)
144
{
145
	struct rev_name *name = commit_rev_name_at(&rev_names, commit);
146

147
	if (is_valid_rev_name(name) &&
148
	    !is_better_name(name, taggerdate, generation, distance, from_tag))
149
		return NULL;
150

151
	name->taggerdate = taggerdate;
152
	name->generation = generation;
153
	name->distance = distance;
154
	name->from_tag = from_tag;
155

156
	return name;
157
}
158

159
static char *get_parent_name(const struct rev_name *name, int parent_number,
160
			     struct mem_pool *string_pool)
161
{
162
	size_t len;
163

164
	strip_suffix(name->tip_name, "^0", &len);
165
	if (name->generation > 0) {
166
		return mem_pool_strfmt(string_pool, "%.*s~%d^%d",
167
				       (int)len, name->tip_name,
168
				       name->generation, parent_number);
169
	} else {
170
		return mem_pool_strfmt(string_pool, "%.*s^%d",
171
				       (int)len, name->tip_name, parent_number);
172
	}
173
}
174

175
static void name_rev(struct commit *start_commit,
176
		const char *tip_name, timestamp_t taggerdate,
177
		int from_tag, int deref, struct mem_pool *string_pool)
178
{
179
	struct prio_queue queue;
180
	struct commit *commit;
181
	struct commit **parents_to_queue = NULL;
182
	size_t parents_to_queue_nr, parents_to_queue_alloc = 0;
183
	struct rev_name *start_name;
184

185
	repo_parse_commit(the_repository, start_commit);
186
	if (commit_is_before_cutoff(start_commit))
187
		return;
188

189
	start_name = create_or_update_name(start_commit, taggerdate, 0, 0,
190
					   from_tag);
191
	if (!start_name)
192
		return;
193
	if (deref)
194
		start_name->tip_name = mem_pool_strfmt(string_pool, "%s^0",
195
						       tip_name);
196
	else
197
		start_name->tip_name = mem_pool_strdup(string_pool, tip_name);
198

199
	memset(&queue, 0, sizeof(queue)); /* Use the prio_queue as LIFO */
200
	prio_queue_put(&queue, start_commit);
201

202
	while ((commit = prio_queue_get(&queue))) {
203
		struct rev_name *name = get_commit_rev_name(commit);
204
		struct commit_list *parents;
205
		int parent_number = 1;
206

207
		parents_to_queue_nr = 0;
208

209
		for (parents = commit->parents;
210
				parents;
211
				parents = parents->next, parent_number++) {
212
			struct commit *parent = parents->item;
213
			struct rev_name *parent_name;
214
			int generation, distance;
215

216
			repo_parse_commit(the_repository, parent);
217
			if (commit_is_before_cutoff(parent))
218
				continue;
219

220
			if (parent_number > 1) {
221
				generation = 0;
222
				distance = name->distance + MERGE_TRAVERSAL_WEIGHT;
223
			} else {
224
				generation = name->generation + 1;
225
				distance = name->distance + 1;
226
			}
227

228
			parent_name = create_or_update_name(parent, taggerdate,
229
							    generation,
230
							    distance, from_tag);
231
			if (parent_name) {
232
				if (parent_number > 1)
233
					parent_name->tip_name =
234
						get_parent_name(name,
235
								parent_number,
236
								string_pool);
237
				else
238
					parent_name->tip_name = name->tip_name;
239
				ALLOC_GROW(parents_to_queue,
240
					   parents_to_queue_nr + 1,
241
					   parents_to_queue_alloc);
242
				parents_to_queue[parents_to_queue_nr] = parent;
243
				parents_to_queue_nr++;
244
			}
245
		}
246

247
		/* The first parent must come out first from the prio_queue */
248
		while (parents_to_queue_nr)
249
			prio_queue_put(&queue,
250
				       parents_to_queue[--parents_to_queue_nr]);
251
	}
252

253
	clear_prio_queue(&queue);
254
	free(parents_to_queue);
255
}
256

257
static int subpath_matches(const char *path, const char *filter)
258
{
259
	const char *subpath = path;
260

261
	while (subpath) {
262
		if (!wildmatch(filter, subpath, 0))
263
			return subpath - path;
264
		subpath = strchr(subpath, '/');
265
		if (subpath)
266
			subpath++;
267
	}
268
	return -1;
269
}
270

271
struct name_ref_data {
272
	int tags_only;
273
	int name_only;
274
	struct string_list ref_filters;
275
	struct string_list exclude_filters;
276
};
277

278
static struct tip_table {
279
	struct tip_table_entry {
280
		struct object_id oid;
281
		const char *refname;
282
		struct commit *commit;
283
		timestamp_t taggerdate;
284
		unsigned int from_tag:1;
285
		unsigned int deref:1;
286
	} *table;
287
	int nr;
288
	int alloc;
289
	int sorted;
290
} tip_table;
291

292
static void add_to_tip_table(const struct object_id *oid, const char *refname,
293
			     int shorten_unambiguous, struct commit *commit,
294
			     timestamp_t taggerdate, int from_tag, int deref)
295
{
296
	char *short_refname = NULL;
297

298
	if (shorten_unambiguous)
299
		short_refname = refs_shorten_unambiguous_ref(get_main_ref_store(the_repository),
300
							     refname, 0);
301
	else if (skip_prefix(refname, "refs/heads/", &refname))
302
		; /* refname already advanced */
303
	else
304
		skip_prefix(refname, "refs/", &refname);
305

306
	ALLOC_GROW(tip_table.table, tip_table.nr + 1, tip_table.alloc);
307
	oidcpy(&tip_table.table[tip_table.nr].oid, oid);
308
	tip_table.table[tip_table.nr].refname = short_refname ?
309
		short_refname : xstrdup(refname);
310
	tip_table.table[tip_table.nr].commit = commit;
311
	tip_table.table[tip_table.nr].taggerdate = taggerdate;
312
	tip_table.table[tip_table.nr].from_tag = from_tag;
313
	tip_table.table[tip_table.nr].deref = deref;
314
	tip_table.nr++;
315
	tip_table.sorted = 0;
316
}
317

318
static int tipcmp(const void *a_, const void *b_)
319
{
320
	const struct tip_table_entry *a = a_, *b = b_;
321
	return oidcmp(&a->oid, &b->oid);
322
}
323

324
static int cmp_by_tag_and_age(const void *a_, const void *b_)
325
{
326
	const struct tip_table_entry *a = a_, *b = b_;
327
	int cmp;
328

329
	/* Prefer tags. */
330
	cmp = b->from_tag - a->from_tag;
331
	if (cmp)
332
		return cmp;
333

334
	/* Older is better. */
335
	if (a->taggerdate < b->taggerdate)
336
		return -1;
337
	return a->taggerdate != b->taggerdate;
338
}
339

340
static int name_ref(const char *path, const char *referent UNUSED, const struct object_id *oid,
341
		    int flags UNUSED, void *cb_data)
342
{
343
	struct object *o = parse_object(the_repository, oid);
344
	struct name_ref_data *data = cb_data;
345
	int can_abbreviate_output = data->tags_only && data->name_only;
346
	int deref = 0;
347
	int from_tag = 0;
348
	struct commit *commit = NULL;
349
	timestamp_t taggerdate = TIME_MAX;
350

351
	if (data->tags_only && !starts_with(path, "refs/tags/"))
352
		return 0;
353

354
	if (data->exclude_filters.nr) {
355
		struct string_list_item *item;
356

357
		for_each_string_list_item(item, &data->exclude_filters) {
358
			if (subpath_matches(path, item->string) >= 0)
359
				return 0;
360
		}
361
	}
362

363
	if (data->ref_filters.nr) {
364
		struct string_list_item *item;
365
		int matched = 0;
366

367
		/* See if any of the patterns match. */
368
		for_each_string_list_item(item, &data->ref_filters) {
369
			/*
370
			 * Check all patterns even after finding a match, so
371
			 * that we can see if a match with a subpath exists.
372
			 * When a user asked for 'refs/tags/v*' and 'v1.*',
373
			 * both of which match, the user is showing her
374
			 * willingness to accept a shortened output by having
375
			 * the 'v1.*' in the acceptable refnames, so we
376
			 * shouldn't stop when seeing 'refs/tags/v1.4' matches
377
			 * 'refs/tags/v*'.  We should show it as 'v1.4'.
378
			 */
379
			switch (subpath_matches(path, item->string)) {
380
			case -1: /* did not match */
381
				break;
382
			case 0: /* matched fully */
383
				matched = 1;
384
				break;
385
			default: /* matched subpath */
386
				matched = 1;
387
				can_abbreviate_output = 1;
388
				break;
389
			}
390
		}
391

392
		/* If none of the patterns matched, stop now */
393
		if (!matched)
394
			return 0;
395
	}
396

397
	while (o && o->type == OBJ_TAG) {
398
		struct tag *t = (struct tag *) o;
399
		if (!t->tagged)
400
			break; /* broken repository */
401
		o = parse_object(the_repository, &t->tagged->oid);
402
		deref = 1;
403
		taggerdate = t->date;
404
	}
405
	if (o && o->type == OBJ_COMMIT) {
406
		commit = (struct commit *)o;
407
		from_tag = starts_with(path, "refs/tags/");
408
		if (taggerdate == TIME_MAX)
409
			taggerdate = commit->date;
410
	}
411

412
	add_to_tip_table(oid, path, can_abbreviate_output, commit, taggerdate,
413
			 from_tag, deref);
414
	return 0;
415
}
416

417
static void name_tips(struct mem_pool *string_pool)
418
{
419
	int i;
420

421
	/*
422
	 * Try to set better names first, so that worse ones spread
423
	 * less.
424
	 */
425
	QSORT(tip_table.table, tip_table.nr, cmp_by_tag_and_age);
426
	for (i = 0; i < tip_table.nr; i++) {
427
		struct tip_table_entry *e = &tip_table.table[i];
428
		if (e->commit) {
429
			name_rev(e->commit, e->refname, e->taggerdate,
430
				 e->from_tag, e->deref, string_pool);
431
		}
432
	}
433
}
434

435
static const struct object_id *nth_tip_table_ent(size_t ix, const void *table_)
436
{
437
	const struct tip_table_entry *table = table_;
438
	return &table[ix].oid;
439
}
440

441
static const char *get_exact_ref_match(const struct object *o)
442
{
443
	int found;
444

445
	if (!tip_table.table || !tip_table.nr)
446
		return NULL;
447

448
	if (!tip_table.sorted) {
449
		QSORT(tip_table.table, tip_table.nr, tipcmp);
450
		tip_table.sorted = 1;
451
	}
452

453
	found = oid_pos(&o->oid, tip_table.table, tip_table.nr,
454
			nth_tip_table_ent);
455
	if (0 <= found)
456
		return tip_table.table[found].refname;
457
	return NULL;
458
}
459

460
/* may return a constant string or use "buf" as scratch space */
461
static const char *get_rev_name(const struct object *o, struct strbuf *buf)
462
{
463
	struct rev_name *n;
464
	const struct commit *c;
465

466
	if (o->type != OBJ_COMMIT)
467
		return get_exact_ref_match(o);
468
	c = (const struct commit *) o;
469
	n = get_commit_rev_name(c);
470
	if (!n)
471
		return NULL;
472

473
	if (!n->generation)
474
		return n->tip_name;
475
	else {
476
		strbuf_reset(buf);
477
		strbuf_addstr(buf, n->tip_name);
478
		strbuf_strip_suffix(buf, "^0");
479
		strbuf_addf(buf, "~%d", n->generation);
480
		return buf->buf;
481
	}
482
}
483

484
static void show_name(const struct object *obj,
485
		      const char *caller_name,
486
		      int always, int allow_undefined, int name_only)
487
{
488
	const char *name;
489
	const struct object_id *oid = &obj->oid;
490
	struct strbuf buf = STRBUF_INIT;
491

492
	if (!name_only)
493
		printf("%s ", caller_name ? caller_name : oid_to_hex(oid));
494
	name = get_rev_name(obj, &buf);
495
	if (name)
496
		printf("%s\n", name);
497
	else if (allow_undefined)
498
		printf("undefined\n");
499
	else if (always)
500
		printf("%s\n",
501
		       repo_find_unique_abbrev(the_repository, oid, DEFAULT_ABBREV));
502
	else
503
		die("cannot describe '%s'", oid_to_hex(oid));
504
	strbuf_release(&buf);
505
}
506

507
static char const * const name_rev_usage[] = {
508
	N_("git name-rev [<options>] <commit>..."),
509
	N_("git name-rev [<options>] --all"),
510
	N_("git name-rev [<options>] --annotate-stdin"),
511
	NULL
512
};
513

514
static void name_rev_line(char *p, struct name_ref_data *data)
515
{
516
	struct strbuf buf = STRBUF_INIT;
517
	int counter = 0;
518
	char *p_start;
519
	const unsigned hexsz = the_hash_algo->hexsz;
520

521
	for (p_start = p; *p; p++) {
522
#define ishex(x) (isdigit((x)) || ((x) >= 'a' && (x) <= 'f'))
523
		if (!ishex(*p))
524
			counter = 0;
525
		else if (++counter == hexsz &&
526
			 !ishex(*(p+1))) {
527
			struct object_id oid;
528
			const char *name = NULL;
529
			char c = *(p+1);
530
			int p_len = p - p_start + 1;
531

532
			counter = 0;
533

534
			*(p+1) = 0;
535
			if (!repo_get_oid(the_repository, p - (hexsz - 1), &oid)) {
536
				struct object *o =
537
					lookup_object(the_repository, &oid);
538
				if (o)
539
					name = get_rev_name(o, &buf);
540
			}
541
			*(p+1) = c;
542

543
			if (!name)
544
				continue;
545

546
			if (data->name_only)
547
				printf("%.*s%s", p_len - hexsz, p_start, name);
548
			else
549
				printf("%.*s (%s)", p_len, p_start, name);
550
			p_start = p + 1;
551
		}
552
	}
553

554
	/* flush */
555
	if (p_start != p)
556
		fwrite(p_start, p - p_start, 1, stdout);
557

558
	strbuf_release(&buf);
559
}
560

561
int cmd_name_rev(int argc, const char **argv, const char *prefix)
562
{
563
	struct mem_pool string_pool;
564
	struct object_array revs = OBJECT_ARRAY_INIT;
565
	int all = 0, annotate_stdin = 0, transform_stdin = 0, allow_undefined = 1, always = 0, peel_tag = 0;
566
	struct name_ref_data data = { 0, 0, STRING_LIST_INIT_NODUP, STRING_LIST_INIT_NODUP };
567
	struct option opts[] = {
568
		OPT_BOOL(0, "name-only", &data.name_only, N_("print only ref-based names (no object names)")),
569
		OPT_BOOL(0, "tags", &data.tags_only, N_("only use tags to name the commits")),
570
		OPT_STRING_LIST(0, "refs", &data.ref_filters, N_("pattern"),
571
				   N_("only use refs matching <pattern>")),
572
		OPT_STRING_LIST(0, "exclude", &data.exclude_filters, N_("pattern"),
573
				   N_("ignore refs matching <pattern>")),
574
		OPT_GROUP(""),
575
		OPT_BOOL(0, "all", &all, N_("list all commits reachable from all refs")),
576
		OPT_BOOL_F(0,
577
			   "stdin",
578
			   &transform_stdin,
579
			   N_("deprecated: use --annotate-stdin instead"),
580
			   PARSE_OPT_HIDDEN),
581
		OPT_BOOL(0, "annotate-stdin", &annotate_stdin, N_("annotate text from stdin")),
582
		OPT_BOOL(0, "undefined", &allow_undefined, N_("allow to print `undefined` names (default)")),
583
		OPT_BOOL(0, "always",     &always,
584
			   N_("show abbreviated commit object as fallback")),
585
		OPT_HIDDEN_BOOL(0, "peel-tag", &peel_tag,
586
			   N_("dereference tags in the input (internal use)")),
587
		OPT_END(),
588
	};
589

590
	mem_pool_init(&string_pool, 0);
591
	init_commit_rev_name(&rev_names);
592
	git_config(git_default_config, NULL);
593
	argc = parse_options(argc, argv, prefix, opts, name_rev_usage, 0);
594

595
	if (transform_stdin) {
596
		warning("--stdin is deprecated. Please use --annotate-stdin instead, "
597
					"which is functionally equivalent.\n"
598
					"This option will be removed in a future release.");
599
		annotate_stdin = 1;
600
	}
601

602
	if (all + annotate_stdin + !!argc > 1) {
603
		error("Specify either a list, or --all, not both!");
604
		usage_with_options(name_rev_usage, opts);
605
	}
606
	if (all || annotate_stdin)
607
		disable_cutoff();
608

609
	for (; argc; argc--, argv++) {
610
		struct object_id oid;
611
		struct object *object;
612
		struct commit *commit;
613

614
		if (repo_get_oid(the_repository, *argv, &oid)) {
615
			fprintf(stderr, "Could not get sha1 for %s. Skipping.\n",
616
					*argv);
617
			continue;
618
		}
619

620
		commit = NULL;
621
		object = parse_object(the_repository, &oid);
622
		if (object) {
623
			struct object *peeled = deref_tag(the_repository,
624
							  object, *argv, 0);
625
			if (peeled && peeled->type == OBJ_COMMIT)
626
				commit = (struct commit *)peeled;
627
		}
628

629
		if (!object) {
630
			fprintf(stderr, "Could not get object for %s. Skipping.\n",
631
					*argv);
632
			continue;
633
		}
634

635
		if (commit)
636
			set_commit_cutoff(commit);
637

638
		if (peel_tag) {
639
			if (!commit) {
640
				fprintf(stderr, "Could not get commit for %s. Skipping.\n",
641
					*argv);
642
				continue;
643
			}
644
			object = (struct object *)commit;
645
		}
646
		add_object_array(object, *argv, &revs);
647
	}
648

649
	adjust_cutoff_timestamp_for_slop();
650

651
	refs_for_each_ref(get_main_ref_store(the_repository), name_ref, &data);
652
	name_tips(&string_pool);
653

654
	if (annotate_stdin) {
655
		struct strbuf sb = STRBUF_INIT;
656

657
		while (strbuf_getline(&sb, stdin) != EOF) {
658
			strbuf_addch(&sb, '\n');
659
			name_rev_line(sb.buf, &data);
660
		}
661
		strbuf_release(&sb);
662
	} else if (all) {
663
		int i, max;
664

665
		max = get_max_object_index();
666
		for (i = 0; i < max; i++) {
667
			struct object *obj = get_indexed_object(i);
668
			if (!obj || obj->type != OBJ_COMMIT)
669
				continue;
670
			show_name(obj, NULL,
671
				  always, allow_undefined, data.name_only);
672
		}
673
	} else {
674
		int i;
675
		for (i = 0; i < revs.nr; i++)
676
			show_name(revs.objects[i].item, revs.objects[i].name,
677
				  always, allow_undefined, data.name_only);
678
	}
679

680
	string_list_clear(&data.ref_filters, 0);
681
	string_list_clear(&data.exclude_filters, 0);
682
	mem_pool_discard(&string_pool, 0);
683
	object_array_clear(&revs);
684
	return 0;
685
}
686