sha1-name.c 48.2 KB
Newer Older
1
#include "cache.h"
2
#include "config.h"
3
#include "tag.h"
4
#include "commit.h"
5 6
#include "tree.h"
#include "blob.h"
7
#include "tree-walk.h"
8
#include "refs.h"
9
#include "remote.h"
10
#include "dir.h"
11
#include "sha1-array.h"
12
#include "packfile.h"
13
#include "object-store.h"
14
#include "repository.h"
15
#include "submodule.h"
16
#include "midx.h"
17
#include "commit-reach.h"
18

19
static int get_oid_oneline(struct repository *r, const char *, struct object_id *, struct commit_list *);
20

21
typedef int (*disambiguate_hint_fn)(struct repository *, const struct object_id *, void *);
22 23

struct disambiguate_state {
24
	int len; /* length of prefix in hex chars */
25
	char hex_pfx[GIT_MAX_HEXSZ + 1];
26
	struct object_id bin_pfx;
27

28
	struct repository *repo;
29 30
	disambiguate_hint_fn fn;
	void *cb_data;
31
	struct object_id candidate;
32 33 34 35 36
	unsigned candidate_exists:1;
	unsigned candidate_checked:1;
	unsigned candidate_ok:1;
	unsigned disambiguate_fn_used:1;
	unsigned ambiguous:1;
37
	unsigned always_call_fn:1;
38 39
};

40
static void update_candidates(struct disambiguate_state *ds, const struct object_id *current)
41
{
42
	if (ds->always_call_fn) {
43
		ds->ambiguous = ds->fn(ds->repo, current, ds->cb_data) ? 1 : 0;
44 45
		return;
	}
46 47
	if (!ds->candidate_exists) {
		/* this is the first candidate */
48
		oidcpy(&ds->candidate, current);
49 50
		ds->candidate_exists = 1;
		return;
51
	} else if (oideq(&ds->candidate, current)) {
52 53 54 55 56 57 58 59 60 61 62
		/* the same as what we already have seen */
		return;
	}

	if (!ds->fn) {
		/* cannot disambiguate between ds->candidate and current */
		ds->ambiguous = 1;
		return;
	}

	if (!ds->candidate_checked) {
63
		ds->candidate_ok = ds->fn(ds->repo, &ds->candidate, ds->cb_data);
64 65 66 67 68
		ds->disambiguate_fn_used = 1;
		ds->candidate_checked = 1;
	}

	if (!ds->candidate_ok) {
69
		/* discard the candidate; we know it does not satisfy fn */
70
		oidcpy(&ds->candidate, current);
71 72 73 74 75
		ds->candidate_checked = 0;
		return;
	}

	/* if we reach this point, we know ds->candidate satisfies fn */
76
	if (ds->fn(ds->repo, current, ds->cb_data)) {
77 78 79 80 81 82 83 84 85 86 87
		/*
		 * if both current and candidate satisfy fn, we cannot
		 * disambiguate.
		 */
		ds->candidate_ok = 0;
		ds->ambiguous = 1;
	}

	/* otherwise, current can be discarded and candidate is still good */
}

88 89
static int match_sha(unsigned, const unsigned char *, const unsigned char *);

90
static void find_short_object_filename(struct disambiguate_state *ds)
91
{
92
	struct object_directory *odb;
93

94
	for (odb = ds->repo->objects->odb; odb && !ds->ambiguous; odb = odb->next) {
95
		int pos;
96
		struct oid_array *loose_objects;
97

98 99
		loose_objects = odb_loose_cache(odb, &ds->bin_pfx);
		pos = oid_array_lookup(loose_objects, &ds->bin_pfx);
100 101
		if (pos < 0)
			pos = -1 - pos;
102
		while (!ds->ambiguous && pos < loose_objects->nr) {
103
			const struct object_id *oid;
104
			oid = loose_objects->oid + pos;
105 106 107 108
			if (!match_sha(ds->len, ds->bin_pfx.hash, oid->hash))
				break;
			update_candidates(ds, oid);
			pos++;
109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127
		}
	}
}

static int match_sha(unsigned len, const unsigned char *a, const unsigned char *b)
{
	do {
		if (*a != *b)
			return 0;
		a++;
		b++;
		len -= 2;
	} while (len > 1);
	if (len)
		if ((*a ^ *b) & 0xf0)
			return 0;
	return 1;
}

128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153
static void unique_in_midx(struct multi_pack_index *m,
			   struct disambiguate_state *ds)
{
	uint32_t num, i, first = 0;
	const struct object_id *current = NULL;
	num = m->num_objects;

	if (!num)
		return;

	bsearch_midx(&ds->bin_pfx, m, &first);

	/*
	 * At this point, "first" is the location of the lowest object
	 * with an object name that could match "bin_pfx".  See if we have
	 * 0, 1 or more objects that actually match(es).
	 */
	for (i = first; i < num && !ds->ambiguous; i++) {
		struct object_id oid;
		current = nth_midxed_object_oid(&oid, m, i);
		if (!match_sha(ds->len, ds->bin_pfx.hash, current->hash))
			break;
		update_candidates(ds, current);
	}
}

154
static void unique_in_pack(struct packed_git *p,
155
			   struct disambiguate_state *ds)
156
{
157
	uint32_t num, i, first = 0;
158
	const struct object_id *current = NULL;
159

160 161 162
	if (open_pack_index(p) || !p->num_objects)
		return;

163
	num = p->num_objects;
164
	bsearch_pack(&ds->bin_pfx, p, &first);
165 166 167

	/*
	 * At this point, "first" is the location of the lowest object
168
	 * with an object name that could match "bin_pfx".  See if we have
169 170
	 * 0, 1 or more objects that actually match(es).
	 */
171
	for (i = first; i < num && !ds->ambiguous; i++) {
172 173 174
		struct object_id oid;
		current = nth_packed_object_oid(&oid, p, i);
		if (!match_sha(ds->len, ds->bin_pfx.hash, current->hash))
175
			break;
176
		update_candidates(ds, current);
177
	}
178 179
}

180
static void find_short_packed_object(struct disambiguate_state *ds)
181
{
182
	struct multi_pack_index *m;
183 184
	struct packed_git *p;

185
	for (m = get_multi_pack_index(ds->repo); m && !ds->ambiguous;
186 187
	     m = m->next)
		unique_in_midx(m, ds);
188
	for (p = get_packed_git(ds->repo); p && !ds->ambiguous;
189
	     p = p->next)
190
		unique_in_pack(p, ds);
191 192
}

193
static int finish_object_disambiguation(struct disambiguate_state *ds,
194
					struct object_id *oid)
195
{
196 197
	if (ds->ambiguous)
		return SHORT_NAME_AMBIGUOUS;
198

199
	if (!ds->candidate_exists)
200
		return MISSING_OBJECT;
201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217

	if (!ds->candidate_checked)
		/*
		 * If this is the only candidate, there is no point
		 * calling the disambiguation hint callback.
		 *
		 * On the other hand, if the current candidate
		 * replaced an earlier candidate that did _not_ pass
		 * the disambiguation hint callback, then we do have
		 * more than one objects that match the short name
		 * given, so we should make sure this one matches;
		 * otherwise, if we discovered this one and the one
		 * that we previously discarded in the reverse order,
		 * we would end up showing different results in the
		 * same repository!
		 */
		ds->candidate_ok = (!ds->disambiguate_fn_used ||
218
				    ds->fn(ds->repo, &ds->candidate, ds->cb_data));
219 220

	if (!ds->candidate_ok)
221
		return SHORT_NAME_AMBIGUOUS;
222

223
	oidcpy(oid, &ds->candidate);
224 225 226
	return 0;
}

227 228 229
static int disambiguate_commit_only(struct repository *r,
				    const struct object_id *oid,
				    void *cb_data_unused)
230
{
231
	int kind = oid_object_info(r, oid, NULL);
232 233 234
	return kind == OBJ_COMMIT;
}

235 236 237
static int disambiguate_committish_only(struct repository *r,
					const struct object_id *oid,
					void *cb_data_unused)
238 239 240 241
{
	struct object *obj;
	int kind;

242
	kind = oid_object_info(r, oid, NULL);
243 244 245
	if (kind == OBJ_COMMIT)
		return 1;
	if (kind != OBJ_TAG)
246
		return 0;
247 248

	/* We need to do this the hard way... */
249
	obj = deref_tag(r, parse_object(r, oid), NULL, 0);
250 251
	if (obj && obj->type == OBJ_COMMIT)
		return 1;
252 253 254
	return 0;
}

255 256 257
static int disambiguate_tree_only(struct repository *r,
				  const struct object_id *oid,
				  void *cb_data_unused)
258
{
259
	int kind = oid_object_info(r, oid, NULL);
260 261
	return kind == OBJ_TREE;
}
262

263 264 265
static int disambiguate_treeish_only(struct repository *r,
				     const struct object_id *oid,
				     void *cb_data_unused)
266 267 268 269
{
	struct object *obj;
	int kind;

270
	kind = oid_object_info(r, oid, NULL);
271 272 273 274 275 276
	if (kind == OBJ_TREE || kind == OBJ_COMMIT)
		return 1;
	if (kind != OBJ_TAG)
		return 0;

	/* We need to do this the hard way... */
277
	obj = deref_tag(r, parse_object(r, oid), NULL, 0);
278 279 280 281 282
	if (obj && (obj->type == OBJ_TREE || obj->type == OBJ_COMMIT))
		return 1;
	return 0;
}

283 284 285
static int disambiguate_blob_only(struct repository *r,
				  const struct object_id *oid,
				  void *cb_data_unused)
286
{
287
	int kind = oid_object_info(r, oid, NULL);
288 289 290
	return kind == OBJ_BLOB;
}

291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320
static disambiguate_hint_fn default_disambiguate_hint;

int set_disambiguate_hint_config(const char *var, const char *value)
{
	static const struct {
		const char *name;
		disambiguate_hint_fn fn;
	} hints[] = {
		{ "none", NULL },
		{ "commit", disambiguate_commit_only },
		{ "committish", disambiguate_committish_only },
		{ "tree", disambiguate_tree_only },
		{ "treeish", disambiguate_treeish_only },
		{ "blob", disambiguate_blob_only }
	};
	int i;

	if (!value)
		return config_error_nonbool(var);

	for (i = 0; i < ARRAY_SIZE(hints); i++) {
		if (!strcasecmp(value, hints[i].name)) {
			default_disambiguate_hint = hints[i].fn;
			return 0;
		}
	}

	return error("unknown hint type for '%s': %s", var, value);
}

321 322
static int init_object_disambiguation(struct repository *r,
				      const char *name, int len,
323
				      struct disambiguate_state *ds)
324
{
325
	int i;
326

327
	if (len < MINIMUM_ABBREV || len > the_hash_algo->hexsz)
328 329 330 331
		return -1;

	memset(ds, 0, sizeof(*ds));

332
	for (i = 0; i < len ;i++) {
333 334 335 336 337 338 339 340 341 342 343 344
		unsigned char c = name[i];
		unsigned char val;
		if (c >= '0' && c <= '9')
			val = c - '0';
		else if (c >= 'a' && c <= 'f')
			val = c - 'a' + 10;
		else if (c >= 'A' && c <='F') {
			val = c - 'A' + 10;
			c -= 'A' - 'a';
		}
		else
			return -1;
345
		ds->hex_pfx[i] = c;
346 347
		if (!(i & 1))
			val <<= 4;
348
		ds->bin_pfx.hash[i >> 1] |= val;
349
	}
350 351

	ds->len = len;
352
	ds->hex_pfx[len] = '\0';
353 354
	ds->repo = r;
	prepare_alt_odb(r);
355 356 357
	return 0;
}

358
static int show_ambiguous_object(const struct object_id *oid, void *data)
359 360 361 362 363
{
	const struct disambiguate_state *ds = data;
	struct strbuf desc = STRBUF_INIT;
	int type;

364
	if (ds->fn && !ds->fn(ds->repo, oid, ds->cb_data))
365 366
		return 0;

367
	type = oid_object_info(ds->repo, oid, NULL);
368
	if (type == OBJ_COMMIT) {
369
		struct commit *commit = lookup_commit(ds->repo, oid);
370 371 372 373 374 375
		if (commit) {
			struct pretty_print_context pp = {0};
			pp.date_mode.type = DATE_SHORT;
			format_commit_message(commit, " %ad - %s", &desc, &pp);
		}
	} else if (type == OBJ_TAG) {
376
		struct tag *tag = lookup_tag(ds->repo, oid);
377 378 379 380 381
		if (!parse_tag(tag) && tag->tag)
			strbuf_addf(&desc, " %s", tag->tag);
	}

	advise("  %s %s%s",
382
	       repo_find_unique_abbrev(ds->repo, oid, DEFAULT_ABBREV),
383
	       type_name(type) ? type_name(type) : "unknown type",
384 385 386 387 388 389
	       desc.buf);

	strbuf_release(&desc);
	return 0;
}

390 391 392 393 394 395
static int collect_ambiguous(const struct object_id *oid, void *data)
{
	oid_array_append(data, oid);
	return 0;
}

396 397 398 399 400 401 402
static int repo_collect_ambiguous(struct repository *r,
				  const struct object_id *oid,
				  void *data)
{
	return collect_ambiguous(oid, data);
}

403
static struct repository *sort_ambiguous_repo;
404 405
static int sort_ambiguous(const void *a, const void *b)
{
406 407
	int a_type = oid_object_info(sort_ambiguous_repo, a, NULL);
	int b_type = oid_object_info(sort_ambiguous_repo, b, NULL);
408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431
	int a_type_sort;
	int b_type_sort;

	/*
	 * Sorts by hash within the same object type, just as
	 * oid_array_for_each_unique() would do.
	 */
	if (a_type == b_type)
		return oidcmp(a, b);

	/*
	 * Between object types show tags, then commits, and finally
	 * trees and blobs.
	 *
	 * The object_type enum is commit, tree, blob, tag, but we
	 * want tag, commit, tree blob. Cleverly (perhaps too
	 * cleverly) do that with modulus, since the enum assigns 1 to
	 * commit, so tag becomes 0.
	 */
	a_type_sort = a_type % 4;
	b_type_sort = b_type % 4;
	return a_type_sort > b_type_sort ? 1 : -1;
}

432 433 434 435 436 437 438 439
static void sort_ambiguous_oid_array(struct repository *r, struct oid_array *a)
{
	/* mutex will be needed if this code is to be made thread safe */
	sort_ambiguous_repo = r;
	QSORT(a->oid, a->nr, sort_ambiguous);
	sort_ambiguous_repo = NULL;
}

440 441
static enum get_oid_result get_short_oid(struct repository *r,
					 const char *name, int len,
442 443
					 struct object_id *oid,
					 unsigned flags)
444 445 446
{
	int status;
	struct disambiguate_state ds;
447
	int quietly = !!(flags & GET_OID_QUIETLY);
448

449
	if (init_object_disambiguation(r, name, len, &ds) < 0)
450
		return -1;
451

452
	if (HAS_MULTI_BITS(flags & GET_OID_DISAMBIGUATORS))
453
		BUG("multiple get_short_oid disambiguator flags");
454

455
	if (flags & GET_OID_COMMIT)
456
		ds.fn = disambiguate_commit_only;
457
	else if (flags & GET_OID_COMMITTISH)
458
		ds.fn = disambiguate_committish_only;
459
	else if (flags & GET_OID_TREE)
460
		ds.fn = disambiguate_tree_only;
461
	else if (flags & GET_OID_TREEISH)
462
		ds.fn = disambiguate_treeish_only;
463
	else if (flags & GET_OID_BLOB)
464
		ds.fn = disambiguate_blob_only;
465 466
	else
		ds.fn = default_disambiguate_hint;
467

468 469
	find_short_object_filename(&ds);
	find_short_packed_object(&ds);
470
	status = finish_object_disambiguation(&ds, oid);
471

472 473 474 475 476 477 478 479 480 481 482 483
	/*
	 * If we didn't find it, do the usual reprepare() slow-path,
	 * since the object may have recently been added to the repository
	 * or migrated from loose to packed.
	 */
	if (status == MISSING_OBJECT) {
		reprepare_packed_git(the_repository);
		find_short_object_filename(&ds);
		find_short_packed_object(&ds);
		status = finish_object_disambiguation(&ds, oid);
	}

484
	if (!quietly && (status == SHORT_NAME_AMBIGUOUS)) {
485 486
		struct oid_array collect = OID_ARRAY_INIT;

487 488 489 490 491 492 493 494 495 496 497 498
		error(_("short SHA1 %s is ambiguous"), ds.hex_pfx);

		/*
		 * We may still have ambiguity if we simply saw a series of
		 * candidates that did not satisfy our hint function. In
		 * that case, we still want to show them, so disable the hint
		 * function entirely.
		 */
		if (!ds.ambiguous)
			ds.fn = NULL;

		advise(_("The candidates are:"));
499 500
		repo_for_each_abbrev(r, ds.hex_pfx, collect_ambiguous, &collect);
		sort_ambiguous_oid_array(r, &collect);
501 502 503 504

		if (oid_array_for_each(&collect, show_ambiguous_object, &ds))
			BUG("show_ambiguous_object shouldn't return non-zero");
		oid_array_clear(&collect);
505 506
	}

507 508 509
	return status;
}

510 511
int repo_for_each_abbrev(struct repository *r, const char *prefix,
			 each_abbrev_fn fn, void *cb_data)
512
{
513
	struct oid_array collect = OID_ARRAY_INIT;
514
	struct disambiguate_state ds;
515
	int ret;
516

517
	if (init_object_disambiguation(r, prefix, strlen(prefix), &ds) < 0)
518 519 520
		return -1;

	ds.always_call_fn = 1;
521
	ds.fn = repo_collect_ambiguous;
522
	ds.cb_data = &collect;
523 524
	find_short_object_filename(&ds);
	find_short_packed_object(&ds);
525

526 527
	ret = oid_array_for_each_unique(&collect, fn, cb_data);
	oid_array_clear(&collect);
528
	return ret;
529 530
}

531 532 533 534 535 536 537 538 539 540 541 542 543
/*
 * Return the slot of the most-significant bit set in "val". There are various
 * ways to do this quickly with fls() or __builtin_clzl(), but speed is
 * probably not a big deal here.
 */
static unsigned msb(unsigned long val)
{
	unsigned r = 0;
	while (val >>= 1)
		r++;
	return r;
}

544 545 546 547
struct min_abbrev_data {
	unsigned int init_len;
	unsigned int cur_len;
	char *hex;
548
	struct repository *repo;
549
	const struct object_id *oid;
550 551
};

552 553 554 555 556 557 558 559 560 561 562
static inline char get_hex_char_from_oid(const struct object_id *oid,
					 unsigned int pos)
{
	static const char hex[] = "0123456789abcdef";

	if ((pos & 1) == 0)
		return hex[oid->hash[pos >> 1] >> 4];
	else
		return hex[oid->hash[pos >> 1] & 0xf];
}

563
static int extend_abbrev_len(const struct object_id *oid, void *cb_data)
564
{
565
	struct min_abbrev_data *mad = cb_data;
Junio C Hamano's avatar
Junio C Hamano committed
566

567
	unsigned int i = mad->init_len;
568
	while (mad->hex[i] && mad->hex[i] == get_hex_char_from_oid(oid, i))
569 570 571 572 573 574 575 576
		i++;

	if (i < GIT_MAX_RAWSZ && i >= mad->cur_len)
		mad->cur_len = i + 1;

	return 0;
}

577 578 579 580 581 582 583
static int repo_extend_abbrev_len(struct repository *r,
				  const struct object_id *oid,
				  void *cb_data)
{
	return extend_abbrev_len(oid, cb_data);
}

584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619
static void find_abbrev_len_for_midx(struct multi_pack_index *m,
				     struct min_abbrev_data *mad)
{
	int match = 0;
	uint32_t num, first = 0;
	struct object_id oid;
	const struct object_id *mad_oid;

	if (!m->num_objects)
		return;

	num = m->num_objects;
	mad_oid = mad->oid;
	match = bsearch_midx(mad_oid, m, &first);

	/*
	 * first is now the position in the packfile where we would insert
	 * mad->hash if it does not exist (or the position of mad->hash if
	 * it does exist). Hence, we consider a maximum of two objects
	 * nearby for the abbreviation length.
	 */
	mad->init_len = 0;
	if (!match) {
		if (nth_midxed_object_oid(&oid, m, first))
			extend_abbrev_len(&oid, mad);
	} else if (first < num - 1) {
		if (nth_midxed_object_oid(&oid, m, first + 1))
			extend_abbrev_len(&oid, mad);
	}
	if (first > 0) {
		if (nth_midxed_object_oid(&oid, m, first - 1))
			extend_abbrev_len(&oid, mad);
	}
	mad->init_len = mad->cur_len;
}

620 621
static void find_abbrev_len_for_pack(struct packed_git *p,
				     struct min_abbrev_data *mad)
622
{
623
	int match = 0;
624
	uint32_t num, first = 0;
625
	struct object_id oid;
626
	const struct object_id *mad_oid;
627 628 629 630 631

	if (open_pack_index(p) || !p->num_objects)
		return;

	num = p->num_objects;
632 633
	mad_oid = mad->oid;
	match = bsearch_pack(mad_oid, p, &first);
634 635 636 637

	/*
	 * first is now the position in the packfile where we would insert
	 * mad->hash if it does not exist (or the position of mad->hash if
638
	 * it does exist). Hence, we consider a maximum of two objects
639 640 641 642
	 * nearby for the abbreviation length.
	 */
	mad->init_len = 0;
	if (!match) {
643 644
		if (nth_packed_object_oid(&oid, p, first))
			extend_abbrev_len(&oid, mad);
645
	} else if (first < num - 1) {
646 647
		if (nth_packed_object_oid(&oid, p, first + 1))
			extend_abbrev_len(&oid, mad);
648 649
	}
	if (first > 0) {
650 651
		if (nth_packed_object_oid(&oid, p, first - 1))
			extend_abbrev_len(&oid, mad);
652 653 654 655 656 657
	}
	mad->init_len = mad->cur_len;
}

static void find_abbrev_len_packed(struct min_abbrev_data *mad)
{
658
	struct multi_pack_index *m;
659 660
	struct packed_git *p;

661
	for (m = get_multi_pack_index(mad->repo); m; m = m->next)
662
		find_abbrev_len_for_midx(m, mad);
663
	for (p = get_packed_git(mad->repo); p; p = p->next)
664 665 666
		find_abbrev_len_for_pack(p, mad);
}

667 668
int repo_find_unique_abbrev_r(struct repository *r, char *hex,
			      const struct object_id *oid, int len)
669 670 671 672
{
	struct disambiguate_state ds;
	struct min_abbrev_data mad;
	struct object_id oid_ret;
673
	const unsigned hexsz = r->hash_algo->hexsz;
674

675
	if (len < 0) {
676
		unsigned long count = repo_approximate_object_count(r);
677 678 679 680 681 682 683 684 685 686
		/*
		 * Add one because the MSB only tells us the highest bit set,
		 * not including the value of all the _other_ bits (so "15"
		 * is only one off of 2^4, but the MSB is the 3rd bit.
		 */
		len = msb(count) + 1;
		/*
		 * We now know we have on the order of 2^len objects, which
		 * expects a collision at 2^(len/2). But we also care about hex
		 * chars, not bits, and there are 4 bits per hex. So all
René Scharfe's avatar
René Scharfe committed
687
		 * together we need to divide by 2 and round up.
688
		 */
René Scharfe's avatar
René Scharfe committed
689
		len = DIV_ROUND_UP(len, 2);
690 691 692 693 694
		/*
		 * For very small repos, we stick with our regular fallback.
		 */
		if (len < FALLBACK_DEFAULT_ABBREV)
			len = FALLBACK_DEFAULT_ABBREV;
695
	}
696

697
	oid_to_hex_r(hex, oid);
698 699
	if (len == hexsz || !len)
		return hexsz;
700

701
	mad.repo = r;
702 703 704
	mad.init_len = len;
	mad.cur_len = len;
	mad.hex = hex;
705
	mad.oid = oid;
706 707 708

	find_abbrev_len_packed(&mad);

709
	if (init_object_disambiguation(r, hex, mad.cur_len, &ds) < 0)
710
		return -1;
711

712
	ds.fn = repo_extend_abbrev_len;
713 714 715 716 717 718 719 720
	ds.always_call_fn = 1;
	ds.cb_data = (void *)&mad;

	find_short_object_filename(&ds);
	(void)finish_object_disambiguation(&ds, &oid_ret);

	hex[mad.cur_len] = 0;
	return mad.cur_len;
721 722
}

723 724 725
const char *repo_find_unique_abbrev(struct repository *r,
				    const struct object_id *oid,
				    int len)
726
{
727
	static int bufno;
728
	static char hexbuffer[4][GIT_MAX_HEXSZ + 1];
729 730
	char *hex = hexbuffer[bufno];
	bufno = (bufno + 1) % ARRAY_SIZE(hexbuffer);
731
	repo_find_unique_abbrev_r(r, hex, oid, len);
732
	return hex;
733 734
}

735
static int ambiguous_path(const char *path, int len)
736 737
{
	int slash = 1;
738
	int cnt;
739

740
	for (cnt = 0; cnt < len; cnt++) {
741 742 743 744 745 746 747 748 749 750 751 752 753 754
		switch (*path++) {
		case '\0':
			break;
		case '/':
			if (slash)
				break;
			slash = 1;
			continue;
		case '.':
			continue;
		default:
			slash = 0;
			continue;
		}
755
		break;
756
	}
757
	return slash;
758 759
}

760 761
static inline int at_mark(const char *string, int len,
			  const char **suffix, int nr)
762 763 764
{
	int i;

765
	for (i = 0; i < nr; i++) {
766 767
		int suffix_len = strlen(suffix[i]);
		if (suffix_len <= len
768
		    && !strncasecmp(string, suffix[i], suffix_len))
769 770 771 772 773
			return suffix_len;
	}
	return 0;
}

774 775 776 777 778 779
static inline int upstream_mark(const char *string, int len)
{
	const char *suffix[] = { "@{upstream}", "@{u}" };
	return at_mark(string, len, suffix, ARRAY_SIZE(suffix));
}

780 781 782 783 784 785
static inline int push_mark(const char *string, int len)
{
	const char *suffix[] = { "@{push}" };
	return at_mark(string, len, suffix, ARRAY_SIZE(suffix));
}

786
static enum get_oid_result get_oid_1(struct repository *r, const char *name, int len, struct object_id *oid, unsigned lookup_flags);
787
static int interpret_nth_prior_checkout(struct repository *r, const char *name, int namelen, struct strbuf *buf);
788

789 790
static int get_oid_basic(struct repository *r, const char *str, int len,
			 struct object_id *oid, unsigned int flags)
791
{
792
	static const char *warn_msg = "refname '%.*s' is ambiguous.";
793 794 795 796 797
	static const char *object_name_msg = N_(
	"Git normally never creates a ref that ends with 40 hex characters\n"
	"because it will be ignored when you just specify 40-hex. These refs\n"
	"may be created by mistake. For example,\n"
	"\n"
Duy Nguyen's avatar
Duy Nguyen committed
798
	"  git switch -c $br $(git rev-parse ...)\n"
799 800 801
	"\n"
	"where \"$br\" is somehow empty and a 40-hex ref is created. Please\n"
	"examine these refs and maybe delete them. Turn this message off by\n"
802
	"running \"git config advice.objectNameWarning false\"");
803
	struct object_id tmp_oid;
804
	char *real_ref = NULL;
805
	int refs_found = 0;
806
	int at, reflog_len, nth_prior = 0;
807

808
	if (len == r->hash_algo->hexsz && !get_oid_hex(str, oid)) {
809
		if (warn_ambiguous_refs && warn_on_object_refname_ambiguity) {
810
			refs_found = repo_dwim_ref(r, str, len, &tmp_oid, &real_ref);
811
			if (refs_found > 0) {
812 813 814
				warning(warn_msg, len, str);
				if (advice_object_name_warning)
					fprintf(stderr, "%s\n", _(object_name_msg));
815 816
				if (warn_ambiguous_refs > 1)
					die(_("cannot continue with ambiguous refs"));
817 818
			}
			free(real_ref);
819
		}
820
		return 0;
821
	}
822

823
	/* basic@{time or number or -number} format to query ref-log */
824
	reflog_len = at = 0;
825
	if (len && str[len-1] == '}') {
826
		for (at = len-4; at >= 0; at--) {
827
			if (str[at] == '@' && str[at+1] == '{') {
828 829 830 831
				if (str[at+2] == '-') {
					if (at != 0)
						/* @{-N} not at start */
						return -1;
832 833 834
					nth_prior = 1;
					continue;
				}
835 836
				if (!upstream_mark(str + at, len - at) &&
				    !push_mark(str + at, len - at)) {
837 838 839
					reflog_len = (len-1) - (at+2);
					len = at;
				}
840 841
				break;
			}
842 843 844
		}
	}

845
	/* Accept only unambiguous ref paths. */
846
	if (len && ambiguous_path(str, len))
847 848
		return -1;

849
	if (nth_prior) {
850
		struct strbuf buf = STRBUF_INIT;
851 852
		int detached;

853 854
		if (interpret_nth_prior_checkout(r, str, len, &buf) > 0) {
			detached = (buf.len == r->hash_algo->hexsz && !get_oid_hex(buf.buf, oid));
855 856 857
			strbuf_release(&buf);
			if (detached)
				return 0;
858
		}
859 860 861
	}

	if (!len && reflog_len)
862
		/* allow "@{...}" to mean the current branch reflog */
863
		refs_found = repo_dwim_ref(r, "HEAD", 4, oid, &real_ref);
864
	else if (reflog_len)
865
		refs_found = repo_dwim_log(r, str, len, oid, &real_ref);
866
	else
867
		refs_found = repo_dwim_ref(r, str, len, oid, &real_ref);
868 869 870 871

	if (!refs_found)
		return -1;

872
	if (warn_ambiguous_refs && !(flags & GET_OID_QUIETLY) &&
873
	    (refs_found > 1 ||
874
	     !get_short_oid(r, str, len, &tmp_oid, GET_OID_QUIETLY))) {
875 876 877 878 879
		if (warn_ambiguous_refs > 1)
			die(warn_msg, len, str);
		else
			warning(warn_msg, len, str);
	}
880

881 882
	if (reflog_len) {
		int nth, i;
883 884
		timestamp_t at_time;
		timestamp_t co_time;
885 886
		int co_tz, co_cnt;

887
		/* Is it asking for N-th entry, or approxidate? */
888 889 890 891 892 893 894
		for (i = nth = 0; 0 <= nth && i < reflog_len; i++) {
			char ch = str[at+2+i];
			if ('0' <= ch && ch <= '9')
				nth = nth * 10 + ch - '0';
			else
				nth = -1;
		}
895 896 897 898
		if (100000000 <= nth) {
			at_time = nth;
			nth = -1;
		} else if (0 <= nth)
899
			at_time = 0;
900
		else {
901
			int errors = 0;
902
			char *tmp = xstrndup(str + at + 2, reflog_len);
903
			at_time = approxidate_careful(tmp, &errors);
904
			free(tmp);
905 906
			if (errors) {
				free(real_ref);
907
				return -1;
908
			}
909
		}
910
		if (read_ref_at(get_main_ref_store(r),
911
				real_ref, flags, at_time, nth, oid, NULL,
912
				&co_time, &co_tz, &co_cnt)) {
913
			if (!len) {
914
				if (starts_with(real_ref, "refs/heads/")) {
915 916 917 918 919 920 921 922
					str = real_ref + 11;
					len = strlen(real_ref + 11);
				} else {
					/* detached HEAD */
					str = "HEAD";
					len = 4;
				}
			}
923
			if (at_time) {
924
				if (!(flags & GET_OID_QUIETLY)) {
925 926
					warning("Log for '%.*s' only goes "
						"back to %s.", len, str,
927
						show_date(co_time, co_tz, DATE_MODE(RFC2822)));
928 929
				}
			} else {
930
				if (flags & GET_OID_QUIETLY) {
931 932
					exit(128);
				}
933 934 935
				die("Log for '%.*s' only has %d entries.",
				    len, str, co_cnt);
			}
936
		}
937 938
	}

939
	free(real_ref);
940
	return 0;
941 942
}

943 944
static enum get_oid_result get_parent(struct repository *r,
				      const char *name, int len,
945
				      struct object_id *result, int idx)
946
{
947
	struct object_id oid;
948
	enum get_oid_result ret = get_oid_1(r, name, len, &oid,
949
					    GET_OID_COMMITTISH);
950 951 952 953 954
	struct commit *commit;
	struct commit_list *p;

	if (ret)
		return ret;
955
	commit = lookup_commit_reference(r, &oid);
956
	if (parse_commit(commit))
957
		return MISSING_OBJECT;
958
	if (!idx) {
959
		oidcpy(result, &commit->object.oid);
960
		return FOUND;
961 962 963 964
	}
	p = commit->parents;
	while (p) {
		if (!--idx) {
965
			oidcpy(result, &p->item->object.oid);
966
			return FOUND;
967 968 969
		}
		p = p->next;
	}
970
	return MISSING_OBJECT;
971 972
}

973 974
static enum get_oid_result get_nth_ancestor(struct repository *r,
					    const char *name, int len,
975 976
					    struct object_id *result,
					    int generation)
977
{
978
	struct object_id oid;
979 980 981
	struct commit *commit;
	int ret;

982
	ret = get_oid_1(r, name, len, &oid, GET_OID_COMMITTISH);
983 984
	if (ret)
		return ret;
985
	commit = lookup_commit_reference(r, &oid);
986
	if (!commit)
987
		return MISSING_OBJECT;
988 989

	while (generation--) {
990
		if (parse_commit(commit) || !commit->parents)
991
			return MISSING_OBJECT;
992
		commit = commit->parents->item;
993
	}
994
	oidcpy(result, &commit->object.oid);
995
	return FOUND;
996 997
}

998 999
struct object *repo_peel_to_type(struct repository *r, const char *name, int namelen,
				 struct object *o, enum object_type expected_type)
1000 1001 1002 1003
{
	if (name && !namelen)
		namelen = strlen(name);
	while (1) {
1004
		if (!o || (!o->parsed && !parse_object(r, &o->oid)))
1005
			return NULL;
1006
		if (expected_type == OBJ_ANY || o->type == expected_type)
1007 1008 1009 1010
			return o;
		if (o->type == OBJ_TAG)
			o = ((struct tag*) o)->tagged;
		else if (o->type == OBJ_COMMIT)
1011
			o = &(repo_get_commit_tree(r, ((struct commit *)o))->object);
1012 1013 1014 1015
		else {
			if (name)
				error("%.*s: expected %s type, but the object "
				      "dereferences to %s type",
1016 1017
				      namelen, name, type_name(expected_type),
				      type_name(o->type));
1018 1019 1020 1021 1022
			return NULL;
		}
	}
}

1023 1024
static int peel_onion(struct repository *r, const char *name, int len,
		      struct object_id *oid, unsigned lookup_flags)
1025
{
1026
	struct object_id outer;
1027
	const char *sp;
1028
	unsigned int expected_type = 0;
1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050
	struct object *o;

	/*
	 * "ref^{type}" dereferences ref repeatedly until you cannot
	 * dereference anymore, or you get an object of given type,
	 * whichever comes first.  "ref^{}" means just dereference
	 * tags until you get a non-tag.  "ref^0" is a shorthand for
	 * "ref^{commit}".  "commit^{tree}" could be used to find the
	 * top-level tree of the given commit.
	 */
	if (len < 4 || name[len-1] != '}')
		return -1;

	for (sp = name + len - 1; name <= sp; sp--) {
		int ch = *sp;
		if (ch == '{' && name < sp && sp[-1] == '^')
			break;
	}
	if (sp <= name)
		return -1;

	sp++; /* beginning of type name, or closing brace for empty */
1051
	if (starts_with(sp, "commit}"))
1052
		expected_type = OBJ_COMMIT;
1053
	else if (starts_with(sp, "tag}"))
1054
		expected_type = OBJ_TAG;
1055
	else if (starts_with(sp, "tree}"))
1056
		expected_type = OBJ_TREE;
1057
	else if (starts_with(sp, "blob}"))
1058
		expected_type = OBJ_BLOB;
1059
	else if (starts_with(sp, "object}"))
1060
		expected_type = OBJ_ANY;
1061
	else if (sp[0] == '}')
1062
		expected_type = OBJ_NONE;
1063 1064
	else if (sp[0] == '/')
		expected_type = OBJ_COMMIT;
1065 1066 1067
	else
		return -1;

1068
	lookup_flags &= ~GET_OID_DISAMBIGUATORS;
1069
	if (expected_type == OBJ_COMMIT)
1070
		lookup_flags |= GET_OID_COMMITTISH;
1071
	else if (expected_type == OBJ_TREE)
1072
		lookup_flags |= GET_OID_TREEISH;
1073

1074
	if (get_oid_1(r, name, sp - name - 2, &outer, lookup_flags))
1075 1076
		return -1;

1077
	o = parse_object(r, &outer);
1078 1079
	if (!o)
		return -1;
1080
	if (!expected_type) {
1081 1082
		o = deref_tag(r, o, name, sp - name - 2);
		if (!o || (!o->parsed && !parse_object(r, &o->oid)))
1083
			return -1;
1084
		oidcpy(oid, &o->oid);
1085
		return 0;
1086
	}
1087 1088 1089 1090 1091 1092

	/*
	 * At this point, the syntax look correct, so
	 * if we do not get the needed object, we should
	 * barf.
	 */
1093
	o = repo_peel_to_type(r, name, len, o, expected_type);
1094
	if (!o)
1095
		return -1;
1096

1097
	oidcpy(oid, &o->oid);
1098 1099 1100 1101 1102 1103
	if (sp[0] == '/') {
		/* "$commit^{/foo}" */
		char *prefix;
		int ret;
		struct commit_list *list = NULL;

1104
		/*
1105 1106
		 * $commit^{/}. Some regex implementation may reject.
		 * We don't need regex anyway. '' pattern always matches.
1107
		 */
1108
		if (sp[1] == '}')
1109
			return 0;
1110

1111 1112
		prefix = xstrndup(sp + 1, name + len - 1 - (sp + 1));
		commit_list_insert((struct commit *)o, &list);
1113
		ret = get_oid_oneline(r, prefix, oid, list);
1114 1115
		free(prefix);
		return ret;
1116 1117 1118 1119
	}
	return 0;
}

1120 1121 1122
static int get_describe_name(struct repository *r,
			     const char *name, int len,
			     struct object_id *oid)
1123 1124
{
	const char *cp;
1125
	unsigned flags = GET_OID_QUIETLY | GET_OID_COMMIT;
1126 1127 1128

	for (cp = name + len - 1; name + 2 <= cp; cp--) {
		char ch = *cp;
1129
		if (!isxdigit(ch)) {
1130 1131 1132 1133 1134 1135
			/* We must be looking at g in "SOMETHING-g"
			 * for it to be describe output.
			 */
			if (ch == 'g' && cp[-1] == '-') {
				cp++;
				len -= cp - name;
1136
				return get_short_oid(r,
1137
						     cp, len, oid, flags);
1138 1139 1140 1141 1142 1143
			}
		}
	}
	return -1;
}

1144 1145
static enum get_oid_result get_oid_1(struct repository *r,
				     const char *name, int len,
1146 1147
				     struct object_id *oid,
				     unsigned lookup_flags)
1148
{
1149
	int ret, has_suffix;
1150
	const char *cp;
1151

1152 1153
	/*
	 * "name~3" is "name^^^", "name~" is "name~1", and "name^" is "name^1".
1154
	 */
1155
	has_suffix = 0;
1156 1157 1158 1159
	for (cp = name + len - 1; name <= cp; cp--) {
		int ch = *cp;
		if ('0' <= ch && ch <= '9')
			continue;
1160 1161
		if (ch == '~' || ch == '^')
			has_suffix = ch;
1162 1163
		break;
	}
1164 1165 1166

	if (has_suffix) {
		int num = 0;
1167 1168 1169
		int len1 = cp - name;
		cp++;
		while (cp < name + len)
1170
			num = num * 10 + *cp++ - '0';
1171 1172 1173
		if (!num && len1 == len - 1)
			num = 1;
		if (has_suffix == '^')
1174
			return get_parent(r, name, len1, oid, num);
1175
		/* else if (has_suffix == '~') -- goes without saying */
1176
		return get_nth_ancestor(r, name, len1, oid, num);
1177 1178
	}

1179
	ret = peel_onion(r, name, len, oid, lookup_flags);
1180
	if (!ret)
1181
		return FOUND;
1182

1183
	ret = get_oid_basic(r, name, len, oid, lookup_flags);
1184
	if (!ret)
1185
		return FOUND;
1186 1187

	/* It could be describe output that is "SOMETHING-gXXXX" */