object-name.c

   1 #include "cache.h"
   2 #include "config.h"
   3 #include "tag.h"
   4 #include "commit.h"
   5 #include "tree.h"
   6 #include "blob.h"
   7 #include "tree-walk.h"
   8 #include "refs.h"
   9 #include "remote.h"
  10 #include "dir.h"
  11 #include "oid-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         disambiguate_hint_fn fn;
  30         void *cb_data;
  31         struct object_id candidate;
  32         unsigned candidate_exists:1;
  33         unsigned candidate_checked:1;
  34         unsigned candidate_ok:1;
  35         unsigned disambiguate_fn_used:1;
  36         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                 return;
  45         }
  46         if (!ds->candidate_exists) {
  47                 /* this is the first candidate */
  48                 oidcpy(&ds->candidate, current);
  49                 ds->candidate_exists = 1;
  50                 return;
  51         } else if (oideq(&ds->candidate, current)) {
  52                 /* the same as what we already have seen */
  53                 return;
  54         }
  55
  56         if (!ds->fn) {
  57                 /* cannot disambiguate between ds->candidate and current */
  58                 ds->ambiguous = 1;
  59                 return;
  60         }
  61
  62         if (!ds->candidate_checked) {
  63                 ds->candidate_ok = ds->fn(ds->repo, &ds->candidate, ds->cb_data);
  64                 ds->disambiguate_fn_used = 1;
  65                 ds->candidate_checked = 1;
  66         }
  67
  68         if (!ds->candidate_ok) {
  69                 /* discard the candidate; we know it does not satisfy fn */
  70                 oidcpy(&ds->candidate, current);
  71                 ds->candidate_checked = 0;
  72                 return;
  73         }
  74
  75         /* if we reach this point, we know ds->candidate satisfies fn */
  76         if (ds->fn(ds->repo, current, ds->cb_data)) {
  77                 /*
  78                  * if both current and candidate satisfy fn, we cannot
  79                  * disambiguate.
  80                  */
  81                 ds->candidate_ok = 0;
  82                 ds->ambiguous = 1;
  83         }
  84
  85         /* otherwise, current can be discarded and candidate is still good */
  86 }
  87
  88 static int match_hash(unsigned, const unsigned char *, const unsigned char *);
  89
  90 static enum cb_next match_prefix(const struct object_id *oid, void *arg)
  91 {
  92         struct disambiguate_state *ds = arg;
  93         /* no need to call match_hash, oidtree_each did prefix match */
  94         update_candidates(ds, oid);
  95         return ds->ambiguous ? CB_BREAK : CB_CONTINUE;
  96 }
  97
  98 static void find_short_object_filename(struct disambiguate_state *ds)
  99 {
 100         struct object_directory *odb;
 101
 102         for (odb = ds->repo->objects->odb; odb && !ds->ambiguous; odb = odb->next)
 103                 oidtree_each(odb_loose_cache(odb, &ds->bin_pfx),
 104                                 &ds->bin_pfx, ds->len, match_prefix, ds);
 105 }
 106
 107 static int match_hash(unsigned len, const unsigned char *a, const unsigned char *b)
 108 {
 109         do {
 110                 if (*a != *b)
 111                         return 0;
 112                 a++;
 113                 b++;
 114                 len -= 2;
 115         } while (len > 1);
 116         if (len)
 117                 if ((*a ^ *b) & 0xf0)
 118                         return 0;
 119         return 1;
 120 }
 121
 122 static void unique_in_midx(struct multi_pack_index *m,
 123                            struct disambiguate_state *ds)
 124 {
 125         uint32_t num, i, first = 0;
 126         const struct object_id *current = NULL;
 127         num = m->num_objects;
 128
 129         if (!num)
 130                 return;
 131
 132         bsearch_midx(&ds->bin_pfx, m, &first);
 133
 134         /*
 135          * At this point, "first" is the location of the lowest object
 136          * with an object name that could match "bin_pfx".  See if we have
 137          * 0, 1 or more objects that actually match(es).
 138          */
 139         for (i = first; i < num && !ds->ambiguous; i++) {
 140                 struct object_id oid;
 141                 current = nth_midxed_object_oid(&oid, m, i);
 142                 if (!match_hash(ds->len, ds->bin_pfx.hash, current->hash))
 143                         break;
 144                 update_candidates(ds, current);
 145         }
 146 }
 147
 148 static void unique_in_pack(struct packed_git *p,
 149                            struct disambiguate_state *ds)
 150 {
 151         uint32_t num, i, first = 0;
 152
 153         if (p->multi_pack_index)
 154                 return;
 155
 156         if (open_pack_index(p) || !p->num_objects)
 157                 return;
 158
 159         num = p->num_objects;
 160         bsearch_pack(&ds->bin_pfx, p, &first);
 161
 162         /*
 163          * At this point, "first" is the location of the lowest object
 164          * with an object name that could match "bin_pfx".  See if we have
 165          * 0, 1 or more objects that actually match(es).
 166          */
 167         for (i = first; i < num && !ds->ambiguous; i++) {
 168                 struct object_id oid;
 169                 nth_packed_object_id(&oid, p, i);
 170                 if (!match_hash(ds->len, ds->bin_pfx.hash, oid.hash))
 171                         break;
 172                 update_candidates(ds, &oid);
 173         }
 174 }
 175
 176 static void find_short_packed_object(struct disambiguate_state *ds)
 177 {
 178         struct multi_pack_index *m;
 179         struct packed_git *p;
 180
 181         for (m = get_multi_pack_index(ds->repo); m && !ds->ambiguous;
 182              m = m->next)
 183                 unique_in_midx(m, ds);
 184         for (p = get_packed_git(ds->repo); p && !ds->ambiguous;
 185              p = p->next)
 186                 unique_in_pack(p, ds);
 187 }
 188
 189 static int finish_object_disambiguation(struct disambiguate_state *ds,
 190                                         struct object_id *oid)
 191 {
 192         if (ds->ambiguous)
 193                 return SHORT_NAME_AMBIGUOUS;
 194
 195         if (!ds->candidate_exists)
 196                 return MISSING_OBJECT;
 197
 198         if (!ds->candidate_checked)
 199                 /*
 200                  * If this is the only candidate, there is no point
 201                  * calling the disambiguation hint callback.
 202                  *
 203                  * On the other hand, if the current candidate
 204                  * replaced an earlier candidate that did _not_ pass
 205                  * the disambiguation hint callback, then we do have
 206                  * more than one objects that match the short name
 207                  * given, so we should make sure this one matches;
 208                  * otherwise, if we discovered this one and the one
 209                  * that we previously discarded in the reverse order,
 210                  * we would end up showing different results in the
 211                  * same repository!
 212                  */
 213                 ds->candidate_ok = (!ds->disambiguate_fn_used ||
 214                                     ds->fn(ds->repo, &ds->candidate, ds->cb_data));
 215
 216         if (!ds->candidate_ok)
 217                 return SHORT_NAME_AMBIGUOUS;
 218
 219         oidcpy(oid, &ds->candidate);
 220         return 0;
 221 }
 222
 223 static int disambiguate_commit_only(struct repository *r,
 224                                     const struct object_id *oid,
 225                                     void *cb_data_unused)
 226 {
 227         int kind = oid_object_info(r, oid, NULL);
 228         return kind == OBJ_COMMIT;
 229 }
 230
 231 static int disambiguate_committish_only(struct repository *r,
 232                                         const struct object_id *oid,
 233                                         void *cb_data_unused)
 234 {
 235         struct object *obj;
 236         int kind;
 237
 238         kind = oid_object_info(r, oid, NULL);
 239         if (kind == OBJ_COMMIT)
 240                 return 1;
 241         if (kind != OBJ_TAG)
 242                 return 0;
 243
 244         /* We need to do this the hard way... */
 245         obj = deref_tag(r, parse_object(r, oid), NULL, 0);
 246         if (obj && obj->type == OBJ_COMMIT)
 247                 return 1;
 248         return 0;
 249 }
 250
 251 static int disambiguate_tree_only(struct repository *r,
 252                                   const struct object_id *oid,
 253                                   void *cb_data_unused)
 254 {
 255         int kind = oid_object_info(r, oid, NULL);
 256         return kind == OBJ_TREE;
 257 }
 258
 259 static int disambiguate_treeish_only(struct repository *r,
 260                                      const struct object_id *oid,
 261                                      void *cb_data_unused)
 262 {
 263         struct object *obj;
 264         int kind;
 265
 266         kind = oid_object_info(r, oid, NULL);
 267         if (kind == OBJ_TREE || kind == OBJ_COMMIT)
 268                 return 1;
 269         if (kind != OBJ_TAG)
 270                 return 0;
 271
 272         /* We need to do this the hard way... */
 273         obj = deref_tag(r, parse_object(r, oid), NULL, 0);
 274         if (obj && (obj->type == OBJ_TREE || obj->type == OBJ_COMMIT))
 275                 return 1;
 276         return 0;
 277 }
 278
 279 static int disambiguate_blob_only(struct repository *r,
 280                                   const struct object_id *oid,
 281                                   void *cb_data_unused)
 282 {
 283         int kind = oid_object_info(r, oid, NULL);
 284         return kind == OBJ_BLOB;
 285 }
 286
 287 static disambiguate_hint_fn default_disambiguate_hint;
 288
 289 int set_disambiguate_hint_config(const char *var, const char *value)
 290 {
 291         static const struct {
 292                 const char *name;
 293                 disambiguate_hint_fn fn;
 294         } hints[] = {
 295                 { "none", NULL },
 296                 { "commit", disambiguate_commit_only },
 297                 { "committish", disambiguate_committish_only },
 298                 { "tree", disambiguate_tree_only },
 299                 { "treeish", disambiguate_treeish_only },
 300                 { "blob", disambiguate_blob_only }
 301         };
 302         int i;
 303
 304         if (!value)
 305                 return config_error_nonbool(var);
 306
 307         for (i = 0; i < ARRAY_SIZE(hints); i++) {
 308                 if (!strcasecmp(value, hints[i].name)) {
 309                         default_disambiguate_hint = hints[i].fn;
 310                         return 0;
 311                 }
 312         }
 313
 314         return error("unknown hint type for '%s': %s", var, value);
 315 }
 316
 317 static int init_object_disambiguation(struct repository *r,
 318                                       const char *name, int len,
 319                                       struct disambiguate_state *ds)
 320 {
 321         int i;
 322
 323         if (len < MINIMUM_ABBREV || len > the_hash_algo->hexsz)
 324                 return -1;
 325
 326         memset(ds, 0, sizeof(*ds));
 327
 328         for (i = 0; i < len ;i++) {
 329                 unsigned char c = name[i];
 330                 unsigned char val;
 331                 if (c >= '0' && c <= '9')
 332                         val = c - '0';
 333                 else if (c >= 'a' && c <= 'f')
 334                         val = c - 'a' + 10;
 335                 else if (c >= 'A' && c <='F') {
 336                         val = c - 'A' + 10;
 337                         c -= 'A' - 'a';
 338                 }
 339                 else
 340                         return -1;
 341                 ds->hex_pfx[i] = c;
 342                 if (!(i & 1))
 343                         val <<= 4;
 344                 ds->bin_pfx.hash[i >> 1] |= val;
 345         }
 346
 347         ds->len = len;
 348         ds->hex_pfx[len] = '\0';
 349         ds->repo = r;
 350         prepare_alt_odb(r);
 351         return 0;
 352 }
 353
 354 static int show_ambiguous_object(const struct object_id *oid, void *data)
 355 {
 356         const struct disambiguate_state *ds = data;
 357         struct strbuf desc = STRBUF_INIT;
 358         int type;
 359
 360         if (ds->fn && !ds->fn(ds->repo, oid, ds->cb_data))
 361                 return 0;
 362
 363         type = oid_object_info(ds->repo, oid, NULL);
 364         if (type == OBJ_COMMIT) {
 365                 struct commit *commit = lookup_commit(ds->repo, oid);
 366                 if (commit) {
 367                         struct pretty_print_context pp = {0};
 368                         pp.date_mode.type = DATE_SHORT;
 369                         format_commit_message(commit, " %ad - %s", &desc, &pp);
 370                 }
 371         } else if (type == OBJ_TAG) {
 372                 struct tag *tag = lookup_tag(ds->repo, oid);
 373                 if (!parse_tag(tag) && tag->tag)
 374                         strbuf_addf(&desc, " %s", tag->tag);
 375         }
 376
 377         advise("  %s %s%s",
 378                repo_find_unique_abbrev(ds->repo, oid, DEFAULT_ABBREV),
 379                type_name(type) ? type_name(type) : "unknown type",
 380                desc.buf);
 381
 382         strbuf_release(&desc);
 383         return 0;
 384 }
 385
 386 static int collect_ambiguous(const struct object_id *oid, void *data)
 387 {
 388         oid_array_append(data, oid);
 389         return 0;
 390 }
 391
 392 static int repo_collect_ambiguous(struct repository *r,
 393                                   const struct object_id *oid,
 394                                   void *data)
 395 {
 396         return collect_ambiguous(oid, data);
 397 }
 398
 399 static int sort_ambiguous(const void *a, const void *b, void *ctx)
 400 {
 401         struct repository *sort_ambiguous_repo = ctx;
 402         int a_type = oid_object_info(sort_ambiguous_repo, a, NULL);
 403         int b_type = oid_object_info(sort_ambiguous_repo, b, NULL);
 404         int a_type_sort;
 405         int b_type_sort;
 406
 407         /*
 408          * Sorts by hash within the same object type, just as
 409          * oid_array_for_each_unique() would do.
 410          */
 411         if (a_type == b_type)
 412                 return oidcmp(a, b);
 413
 414         /*
 415          * Between object types show tags, then commits, and finally
 416          * trees and blobs.
 417          *
 418          * The object_type enum is commit, tree, blob, tag, but we
 419          * want tag, commit, tree blob. Cleverly (perhaps too
 420          * cleverly) do that with modulus, since the enum assigns 1 to
 421          * commit, so tag becomes 0.
 422          */
 423         a_type_sort = a_type % 4;
 424         b_type_sort = b_type % 4;
 425         return a_type_sort > b_type_sort ? 1 : -1;
 426 }
 427
 428 static void sort_ambiguous_oid_array(struct repository *r, struct oid_array *a)
 429 {
 430         QSORT_S(a->oid, a->nr, sort_ambiguous, r);
 431 }
 432
 433 static enum get_oid_result get_short_oid(struct repository *r,
 434                                          const char *name, int len,
 435                                          struct object_id *oid,
 436                                          unsigned flags)
 437 {
 438         int status;
 439         struct disambiguate_state ds;
 440         int quietly = !!(flags & GET_OID_QUIETLY);
 441
 442         if (init_object_disambiguation(r, name, len, &ds) < 0)
 443                 return -1;
 444
 445         if (HAS_MULTI_BITS(flags & GET_OID_DISAMBIGUATORS))
 446                 BUG("multiple get_short_oid disambiguator flags");
 447
 448         if (flags & GET_OID_COMMIT)
 449                 ds.fn = disambiguate_commit_only;
 450         else if (flags & GET_OID_COMMITTISH)
 451                 ds.fn = disambiguate_committish_only;
 452         else if (flags & GET_OID_TREE)
 453                 ds.fn = disambiguate_tree_only;
 454         else if (flags & GET_OID_TREEISH)
 455                 ds.fn = disambiguate_treeish_only;
 456         else if (flags & GET_OID_BLOB)
 457                 ds.fn = disambiguate_blob_only;
 458         else
 459                 ds.fn = default_disambiguate_hint;
 460
 461         find_short_object_filename(&ds);
 462         find_short_packed_object(&ds);
 463         status = finish_object_disambiguation(&ds, oid);
 464
 465         /*
 466          * If we didn't find it, do the usual reprepare() slow-path,
 467          * since the object may have recently been added to the repository
 468          * or migrated from loose to packed.
 469          */
 470         if (status == MISSING_OBJECT) {
 471                 reprepare_packed_git(r);
 472                 find_short_object_filename(&ds);
 473                 find_short_packed_object(&ds);
 474                 status = finish_object_disambiguation(&ds, oid);
 475         }
 476
 477         if (!quietly && (status == SHORT_NAME_AMBIGUOUS)) {
 478                 struct oid_array collect = OID_ARRAY_INIT;
 479
 480                 error(_("short object ID %s is ambiguous"), ds.hex_pfx);
 481
 482                 /*
 483                  * We may still have ambiguity if we simply saw a series of
 484                  * candidates that did not satisfy our hint function. In
 485                  * that case, we still want to show them, so disable the hint
 486                  * function entirely.
 487                  */
 488                 if (!ds.ambiguous)
 489                         ds.fn = NULL;
 490
 491                 advise(_("The candidates are:"));
 492                 repo_for_each_abbrev(r, ds.hex_pfx, collect_ambiguous, &collect);
 493                 sort_ambiguous_oid_array(r, &collect);
 494
 495                 if (oid_array_for_each(&collect, show_ambiguous_object, &ds))
 496                         BUG("show_ambiguous_object shouldn't return non-zero");
 497                 oid_array_clear(&collect);
 498         }
 499
 500         return status;
 501 }
 502
 503 int repo_for_each_abbrev(struct repository *r, const char *prefix,
 504                          each_abbrev_fn fn, void *cb_data)
 505 {
 506         struct oid_array collect = OID_ARRAY_INIT;
 507         struct disambiguate_state ds;
 508         int ret;
 509
 510         if (init_object_disambiguation(r, prefix, strlen(prefix), &ds) < 0)
 511                 return -1;
 512
 513         ds.always_call_fn = 1;
 514         ds.fn = repo_collect_ambiguous;
 515         ds.cb_data = &collect;
 516         find_short_object_filename(&ds);
 517         find_short_packed_object(&ds);
 518
 519         ret = oid_array_for_each_unique(&collect, fn, cb_data);
 520         oid_array_clear(&collect);
 521         return ret;
 522 }
 523
 524 /*
 525  * Return the slot of the most-significant bit set in "val". There are various
 526  * ways to do this quickly with fls() or __builtin_clzl(), but speed is
 527  * probably not a big deal here.
 528  */
 529 static unsigned msb(unsigned long val)
 530 {
 531         unsigned r = 0;
 532         while (val >>= 1)
 533                 r++;
 534         return r;
 535 }
 536
 537 struct min_abbrev_data {
 538         unsigned int init_len;
 539         unsigned int cur_len;
 540         char *hex;
 541         struct repository *repo;
 542         const struct object_id *oid;
 543 };
 544
 545 static inline char get_hex_char_from_oid(const struct object_id *oid,
 546                                          unsigned int pos)
 547 {
 548         static const char hex[] = "0123456789abcdef";
 549
 550         if ((pos & 1) == 0)
 551                 return hex[oid->hash[pos >> 1] >> 4];
 552         else
 553                 return hex[oid->hash[pos >> 1] & 0xf];
 554 }
 555
 556 static int extend_abbrev_len(const struct object_id *oid, void *cb_data)
 557 {
 558         struct min_abbrev_data *mad = cb_data;
 559
 560         unsigned int i = mad->init_len;
 561         while (mad->hex[i] && mad->hex[i] == get_hex_char_from_oid(oid, i))
 562                 i++;
 563
 564         if (i < GIT_MAX_RAWSZ && i >= mad->cur_len)
 565                 mad->cur_len = i + 1;
 566
 567         return 0;
 568 }
 569
 570 static int repo_extend_abbrev_len(struct repository *r,
 571                                   const struct object_id *oid,
 572                                   void *cb_data)
 573 {
 574         return extend_abbrev_len(oid, cb_data);
 575 }
 576
 577 static void find_abbrev_len_for_midx(struct multi_pack_index *m,
 578                                      struct min_abbrev_data *mad)
 579 {
 580         int match = 0;
 581         uint32_t num, first = 0;
 582         struct object_id oid;
 583         const struct object_id *mad_oid;
 584
 585         if (!m->num_objects)
 586                 return;
 587
 588         num = m->num_objects;
 589         mad_oid = mad->oid;
 590         match = bsearch_midx(mad_oid, m, &first);
 591
 592         /*
 593          * first is now the position in the packfile where we would insert
 594          * mad->hash if it does not exist (or the position of mad->hash if
 595          * it does exist). Hence, we consider a maximum of two objects
 596          * nearby for the abbreviation length.
 597          */
 598         mad->init_len = 0;
 599         if (!match) {
 600                 if (nth_midxed_object_oid(&oid, m, first))
 601                         extend_abbrev_len(&oid, mad);
 602         } else if (first < num - 1) {
 603                 if (nth_midxed_object_oid(&oid, m, first + 1))
 604                         extend_abbrev_len(&oid, mad);
 605         }
 606         if (first > 0) {
 607                 if (nth_midxed_object_oid(&oid, m, first - 1))
 608                         extend_abbrev_len(&oid, mad);
 609         }
 610         mad->init_len = mad->cur_len;
 611 }
 612
 613 static void find_abbrev_len_for_pack(struct packed_git *p,
 614                                      struct min_abbrev_data *mad)
 615 {
 616         int match = 0;
 617         uint32_t num, first = 0;
 618         struct object_id oid;
 619         const struct object_id *mad_oid;
 620
 621         if (p->multi_pack_index)
 622                 return;
 623
 624         if (open_pack_index(p) || !p->num_objects)
 625                 return;
 626
 627         num = p->num_objects;
 628         mad_oid = mad->oid;
 629         match = bsearch_pack(mad_oid, p, &first);
 630
 631         /*
 632          * first is now the position in the packfile where we would insert
 633          * mad->hash if it does not exist (or the position of mad->hash if
 634          * it does exist). Hence, we consider a maximum of two objects
 635          * nearby for the abbreviation length.
 636          */
 637         mad->init_len = 0;
 638         if (!match) {
 639                 if (!nth_packed_object_id(&oid, p, first))
 640                         extend_abbrev_len(&oid, mad);
 641         } else if (first < num - 1) {
 642                 if (!nth_packed_object_id(&oid, p, first + 1))
 643                         extend_abbrev_len(&oid, mad);
 644         }
 645         if (first > 0) {
 646                 if (!nth_packed_object_id(&oid, p, first - 1))
 647                         extend_abbrev_len(&oid, mad);
 648         }
 649         mad->init_len = mad->cur_len;
 650 }
 651
 652 static void find_abbrev_len_packed(struct min_abbrev_data *mad)
 653 {
 654         struct multi_pack_index *m;
 655         struct packed_git *p;
 656
 657         for (m = get_multi_pack_index(mad->repo); m; m = m->next)
 658                 find_abbrev_len_for_midx(m, mad);
 659         for (p = get_packed_git(mad->repo); p; p = p->next)
 660                 find_abbrev_len_for_pack(p, mad);
 661 }
 662
 663 int repo_find_unique_abbrev_r(struct repository *r, char *hex,
 664                               const struct object_id *oid, int len)
 665 {
 666         struct disambiguate_state ds;
 667         struct min_abbrev_data mad;
 668         struct object_id oid_ret;
 669         const unsigned hexsz = r->hash_algo->hexsz;
 670
 671         if (len < 0) {
 672                 unsigned long count = repo_approximate_object_count(r);
 673                 /*
 674                  * Add one because the MSB only tells us the highest bit set,
 675                  * not including the value of all the _other_ bits (so "15"
 676                  * is only one off of 2^4, but the MSB is the 3rd bit.
 677                  */
 678                 len = msb(count) + 1;
 679                 /*
 680                  * We now know we have on the order of 2^len objects, which
 681                  * expects a collision at 2^(len/2). But we also care about hex
 682                  * chars, not bits, and there are 4 bits per hex. So all
 683                  * together we need to divide by 2 and round up.
 684                  */
 685                 len = DIV_ROUND_UP(len, 2);
 686                 /*
 687                  * For very small repos, we stick with our regular fallback.
 688                  */
 689                 if (len < FALLBACK_DEFAULT_ABBREV)
 690                         len = FALLBACK_DEFAULT_ABBREV;
 691         }
 692
 693         oid_to_hex_r(hex, oid);
 694         if (len == hexsz || !len)
 695                 return hexsz;
 696
 697         mad.repo = r;
 698         mad.init_len = len;
 699         mad.cur_len = len;
 700         mad.hex = hex;
 701         mad.oid = oid;
 702
 703         find_abbrev_len_packed(&mad);
 704
 705         if (init_object_disambiguation(r, hex, mad.cur_len, &ds) < 0)
 706                 return -1;
 707
 708         ds.fn = repo_extend_abbrev_len;
 709         ds.always_call_fn = 1;
 710         ds.cb_data = (void *)&mad;
 711
 712         find_short_object_filename(&ds);
 713         (void)finish_object_disambiguation(&ds, &oid_ret);
 714
 715         hex[mad.cur_len] = 0;
 716         return mad.cur_len;
 717 }
 718
 719 const char *repo_find_unique_abbrev(struct repository *r,
 720                                     const struct object_id *oid,
 721                                     int len)
 722 {
 723         static int bufno;
 724         static char hexbuffer[4][GIT_MAX_HEXSZ + 1];
 725         char *hex = hexbuffer[bufno];
 726         bufno = (bufno + 1) % ARRAY_SIZE(hexbuffer);
 727         repo_find_unique_abbrev_r(r, hex, oid, len);
 728         return hex;
 729 }
 730
 731 static int ambiguous_path(const char *path, int len)
 732 {
 733         int slash = 1;
 734         int cnt;
 735
 736         for (cnt = 0; cnt < len; cnt++) {
 737                 switch (*path++) {
 738                 case '\0':
 739                         break;
 740                 case '/':
 741                         if (slash)
 742                                 break;
 743                         slash = 1;
 744                         continue;
 745                 case '.':
 746                         continue;
 747                 default:
 748                         slash = 0;
 749                         continue;
 750                 }
 751                 break;
 752         }
 753         return slash;
 754 }
 755
 756 static inline int at_mark(const char *string, int len,
 757                           const char **suffix, int nr)
 758 {
 759         int i;
 760
 761         for (i = 0; i < nr; i++) {
 762                 int suffix_len = strlen(suffix[i]);
 763                 if (suffix_len <= len
 764                     && !strncasecmp(string, suffix[i], suffix_len))
 765                         return suffix_len;
 766         }
 767         return 0;
 768 }
 769
 770 static inline int upstream_mark(const char *string, int len)
 771 {
 772         const char *suffix[] = { "@{upstream}", "@{u}" };
 773         return at_mark(string, len, suffix, ARRAY_SIZE(suffix));
 774 }
 775
 776 static inline int push_mark(const char *string, int len)
 777 {
 778         const char *suffix[] = { "@{push}" };
 779         return at_mark(string, len, suffix, ARRAY_SIZE(suffix));
 780 }
 781
 782 static enum get_oid_result get_oid_1(struct repository *r, const char *name, int len, struct object_id *oid, unsigned lookup_flags);
 783 static int interpret_nth_prior_checkout(struct repository *r, const char *name, int namelen, struct strbuf *buf);
 784
 785 static int get_oid_basic(struct repository *r, const char *str, int len,
 786                          struct object_id *oid, unsigned int flags)
 787 {
 788         static const char *warn_msg = "refname '%.*s' is ambiguous.";
 789         static const char *object_name_msg = N_(
 790         "Git normally never creates a ref that ends with 40 hex characters\n"
 791         "because it will be ignored when you just specify 40-hex. These refs\n"
 792         "may be created by mistake. For example,\n"
 793         "\n"
 794         "  git switch -c $br $(git rev-parse ...)\n"
 795         "\n"
 796         "where \"$br\" is somehow empty and a 40-hex ref is created. Please\n"
 797         "examine these refs and maybe delete them. Turn this message off by\n"
 798         "running \"git config advice.objectNameWarning false\"");
 799         struct object_id tmp_oid;
 800         char *real_ref = NULL;
 801         int refs_found = 0;
 802         int at, reflog_len, nth_prior = 0;
 803
 804         if (len == r->hash_algo->hexsz && !get_oid_hex(str, oid)) {
 805                 if (warn_ambiguous_refs && warn_on_object_refname_ambiguity) {
 806                         refs_found = repo_dwim_ref(r, str, len, &tmp_oid, &real_ref, 0);
 807                         if (refs_found > 0) {
 808                                 warning(warn_msg, len, str);
 809                                 if (advice_object_name_warning)
 810                                         fprintf(stderr, "%s\n", _(object_name_msg));
 811                         }
 812                         free(real_ref);
 813                 }
 814                 return 0;
 815         }
 816
 817         /* basic@{time or number or -number} format to query ref-log */
 818         reflog_len = at = 0;
 819         if (len && str[len-1] == '}') {
 820                 for (at = len-4; at >= 0; at--) {
 821                         if (str[at] == '@' && str[at+1] == '{') {
 822                                 if (str[at+2] == '-') {
 823                                         if (at != 0)
 824                                                 /* @{-N} not at start */
 825                                                 return -1;
 826                                         nth_prior = 1;
 827                                         continue;
 828                                 }
 829                                 if (!upstream_mark(str + at, len - at) &&
 830                                     !push_mark(str + at, len - at)) {
 831                                         reflog_len = (len-1) - (at+2);
 832                                         len = at;
 833                                 }
 834                                 break;
 835                         }
 836                 }
 837         }
 838
 839         /* Accept only unambiguous ref paths. */
 840         if (len && ambiguous_path(str, len))
 841                 return -1;
 842
 843         if (nth_prior) {
 844                 struct strbuf buf = STRBUF_INIT;
 845                 int detached;
 846
 847                 if (interpret_nth_prior_checkout(r, str, len, &buf) > 0) {
 848                         detached = (buf.len == r->hash_algo->hexsz && !get_oid_hex(buf.buf, oid));
 849                         strbuf_release(&buf);
 850                         if (detached)
 851                                 return 0;
 852                 }
 853         }
 854
 855         if (!len && reflog_len)
 856                 /* allow "@{...}" to mean the current branch reflog */
 857                 refs_found = repo_dwim_ref(r, "HEAD", 4, oid, &real_ref, 0);
 858         else if (reflog_len)
 859                 refs_found = repo_dwim_log(r, str, len, oid, &real_ref);
 860         else
 861                 refs_found = repo_dwim_ref(r, str, len, oid, &real_ref, 0);
 862
 863         if (!refs_found)
 864                 return -1;
 865
 866         if (warn_ambiguous_refs && !(flags & GET_OID_QUIETLY) &&
 867             (refs_found > 1 ||
 868              !get_short_oid(r, str, len, &tmp_oid, GET_OID_QUIETLY)))
 869                 warning(warn_msg, len, str);
 870
 871         if (reflog_len) {
 872                 int nth, i;
 873                 timestamp_t at_time;
 874                 timestamp_t co_time;
 875                 int co_tz, co_cnt;
 876
 877                 /* Is it asking for N-th entry, or approxidate? */
 878                 for (i = nth = 0; 0 <= nth && i < reflog_len; i++) {
 879                         char ch = str[at+2+i];
 880                         if ('0' <= ch && ch <= '9')
 881                                 nth = nth * 10 + ch - '0';
 882                         else
 883                                 nth = -1;
 884                 }
 885                 if (100000000 <= nth) {
 886                         at_time = nth;
 887                         nth = -1;
 888                 } else if (0 <= nth)
 889                         at_time = 0;
 890                 else {
 891                         int errors = 0;
 892                         char *tmp = xstrndup(str + at + 2, reflog_len);
 893                         at_time = approxidate_careful(tmp, &errors);
 894                         free(tmp);
 895                         if (errors) {
 896                                 free(real_ref);
 897                                 return -1;
 898                         }
 899                 }
 900                 if (read_ref_at(get_main_ref_store(r),
 901                                 real_ref, flags, at_time, nth, oid, NULL,
 902                                 &co_time, &co_tz, &co_cnt)) {
 903                         if (!len) {
 904                                 if (!skip_prefix(real_ref, "refs/heads/", &str))
 905                                         str = "HEAD";
 906                                 len = strlen(str);
 907                         }
 908                         if (at_time) {
 909                                 if (!(flags & GET_OID_QUIETLY)) {
 910                                         warning(_("log for '%.*s' only goes back to %s"),
 911                                                 len, str,
 912                                                 show_date(co_time, co_tz, DATE_MODE(RFC2822)));
 913                                 }
 914                         } else {
 915                                 if (flags & GET_OID_QUIETLY) {
 916                                         exit(128);
 917                                 }
 918                                 die(_("log for '%.*s' only has %d entries"),
 919                                     len, str, co_cnt);
 920                         }
 921                 }
 922         }
 923
 924         free(real_ref);
 925         return 0;
 926 }
 927
 928 static enum get_oid_result get_parent(struct repository *r,
 929                                       const char *name, int len,
 930                                       struct object_id *result, int idx)
 931 {
 932         struct object_id oid;
 933         enum get_oid_result ret = get_oid_1(r, name, len, &oid,
 934                                             GET_OID_COMMITTISH);
 935         struct commit *commit;
 936         struct commit_list *p;
 937
 938         if (ret)
 939                 return ret;
 940         commit = lookup_commit_reference(r, &oid);
 941         if (parse_commit(commit))
 942                 return MISSING_OBJECT;
 943         if (!idx) {
 944                 oidcpy(result, &commit->object.oid);
 945                 return FOUND;
 946         }
 947         p = commit->parents;
 948         while (p) {
 949                 if (!--idx) {
 950                         oidcpy(result, &p->item->object.oid);
 951                         return FOUND;
 952                 }
 953                 p = p->next;
 954         }
 955         return MISSING_OBJECT;
 956 }
 957
 958 static enum get_oid_result get_nth_ancestor(struct repository *r,
 959                                             const char *name, int len,
 960                                             struct object_id *result,
 961                                             int generation)
 962 {
 963         struct object_id oid;
 964         struct commit *commit;
 965         int ret;
 966
 967         ret = get_oid_1(r, name, len, &oid, GET_OID_COMMITTISH);
 968         if (ret)
 969                 return ret;
 970         commit = lookup_commit_reference(r, &oid);
 971         if (!commit)
 972                 return MISSING_OBJECT;
 973
 974         while (generation--) {
 975                 if (parse_commit(commit) || !commit->parents)
 976                         return MISSING_OBJECT;
 977                 commit = commit->parents->item;
 978         }
 979         oidcpy(result, &commit->object.oid);
 980         return FOUND;
 981 }
 982
 983 struct object *repo_peel_to_type(struct repository *r, const char *name, int namelen,
 984                                  struct object *o, enum object_type expected_type)
 985 {
 986         if (name && !namelen)
 987                 namelen = strlen(name);
 988         while (1) {
 989                 if (!o || (!o->parsed && !parse_object(r, &o->oid)))
 990                         return NULL;
 991                 if (expected_type == OBJ_ANY || o->type == expected_type)
 992                         return o;
 993                 if (o->type == OBJ_TAG)
 994                         o = ((struct tag*) o)->tagged;
 995                 else if (o->type == OBJ_COMMIT)
 996                         o = &(repo_get_commit_tree(r, ((struct commit *)o))->object);
 997                 else {
 998                         if (name)
 999                                 error("%.*s: expected %s type, but the object "
1000                                       "dereferences to %s type",
1001                                       namelen, name, type_name(expected_type),
1002                                       type_name(o->type));
1003                         return NULL;
1004                 }
1005         }
1006 }
1007
1008 static int peel_onion(struct repository *r, const char *name, int len,
1009                       struct object_id *oid, unsigned lookup_flags)
1010 {
1011         struct object_id outer;
1012         const char *sp;
1013         unsigned int expected_type = 0;
1014         struct object *o;
1015
1016         /*
1017          * "ref^{type}" dereferences ref repeatedly until you cannot
1018          * dereference anymore, or you get an object of given type,
1019          * whichever comes first.  "ref^{}" means just dereference
1020          * tags until you get a non-tag.  "ref^0" is a shorthand for
1021          * "ref^{commit}".  "commit^{tree}" could be used to find the
1022          * top-level tree of the given commit.
1023          */
1024         if (len < 4 || name[len-1] != '}')
1025                 return -1;
1026
1027         for (sp = name + len - 1; name <= sp; sp--) {
1028                 int ch = *sp;
1029                 if (ch == '{' && name < sp && sp[-1] == '^')
1030                         break;
1031         }
1032         if (sp <= name)
1033                 return -1;
1034
1035         sp++; /* beginning of type name, or closing brace for empty */
1036         if (starts_with(sp, "commit}"))
1037                 expected_type = OBJ_COMMIT;
1038         else if (starts_with(sp, "tag}"))
1039                 expected_type = OBJ_TAG;
1040         else if (starts_with(sp, "tree}"))
1041                 expected_type = OBJ_TREE;
1042         else if (starts_with(sp, "blob}"))
1043                 expected_type = OBJ_BLOB;
1044         else if (starts_with(sp, "object}"))
1045                 expected_type = OBJ_ANY;
1046         else if (sp[0] == '}')
1047                 expected_type = OBJ_NONE;
1048         else if (sp[0] == '/')
1049                 expected_type = OBJ_COMMIT;
1050         else
1051                 return -1;
1052
1053         lookup_flags &= ~GET_OID_DISAMBIGUATORS;
1054         if (expected_type == OBJ_COMMIT)
1055                 lookup_flags |= GET_OID_COMMITTISH;
1056         else if (expected_type == OBJ_TREE)
1057                 lookup_flags |= GET_OID_TREEISH;
1058
1059         if (get_oid_1(r, name, sp - name - 2, &outer, lookup_flags))
1060                 return -1;
1061
1062         o = parse_object(r, &outer);
1063         if (!o)
1064                 return -1;
1065         if (!expected_type) {
1066                 o = deref_tag(r, o, name, sp - name - 2);
1067                 if (!o || (!o->parsed && !parse_object(r, &o->oid)))
1068                         return -1;
1069                 oidcpy(oid, &o->oid);
1070                 return 0;
1071         }
1072
1073         /*
1074          * At this point, the syntax look correct, so
1075          * if we do not get the needed object, we should
1076          * barf.
1077          */
1078         o = repo_peel_to_type(r, name, len, o, expected_type);
1079         if (!o)
1080                 return -1;
1081
1082         oidcpy(oid, &o->oid);
1083         if (sp[0] == '/') {
1084                 /* "$commit^{/foo}" */
1085                 char *prefix;
1086                 int ret;
1087                 struct commit_list *list = NULL;
1088
1089                 /*
1090                  * $commit^{/}. Some regex implementation may reject.
1091                  * We don't need regex anyway. '' pattern always matches.
1092                  */
1093                 if (sp[1] == '}')
1094                         return 0;
1095
1096                 prefix = xstrndup(sp + 1, name + len - 1 - (sp + 1));
1097                 commit_list_insert((struct commit *)o, &list);
1098                 ret = get_oid_oneline(r, prefix, oid, list);
1099                 free(prefix);
1100                 return ret;
1101         }
1102         return 0;
1103 }
1104
1105 static int get_describe_name(struct repository *r,
1106                              const char *name, int len,
1107                              struct object_id *oid)
1108 {
1109         const char *cp;
1110         unsigned flags = GET_OID_QUIETLY | GET_OID_COMMIT;
1111
1112         for (cp = name + len - 1; name + 2 <= cp; cp--) {
1113                 char ch = *cp;
1114                 if (!isxdigit(ch)) {
1115                         /* We must be looking at g in "SOMETHING-g"
1116                          * for it to be describe output.
1117                          */
1118                         if (ch == 'g' && cp[-1] == '-') {
1119                                 cp++;
1120                                 len -= cp - name;
1121                                 return get_short_oid(r,
1122                                                      cp, len, oid, flags);
1123                         }
1124                 }
1125         }
1126         return -1;
1127 }
1128
1129 static enum get_oid_result get_oid_1(struct repository *r,
1130                                      const char *name, int len,
1131                                      struct object_id *oid,
1132                                      unsigned lookup_flags)
1133 {
1134         int ret, has_suffix;
1135         const char *cp;
1136
1137         /*
1138          * "name~3" is "name^^^", "name~" is "name~1", and "name^" is "name^1".
1139          */
1140         has_suffix = 0;
1141         for (cp = name + len - 1; name <= cp; cp--) {
1142                 int ch = *cp;
1143                 if ('0' <= ch && ch <= '9')
1144                         continue;
1145                 if (ch == '~' || ch == '^')
1146                         has_suffix = ch;
1147                 break;
1148         }
1149
1150         if (has_suffix) {
1151                 unsigned int num = 0;
1152                 int len1 = cp - name;
1153                 cp++;
1154                 while (cp < name + len) {
1155                         unsigned int digit = *cp++ - '0';
1156                         if (unsigned_mult_overflows(num, 10))
1157                                 return MISSING_OBJECT;
1158                         num *= 10;
1159                         if (unsigned_add_overflows(num, digit))
1160                                 return MISSING_OBJECT;
1161                         num += digit;
1162                 }
1163                 if (!num && len1 == len - 1)
1164                         num = 1;
1165                 else if (num > INT_MAX)
1166                         return MISSING_OBJECT;
1167                 if (has_suffix == '^')
1168                         return get_parent(r, name, len1, oid, num);
1169                 /* else if (has_suffix == '~') -- goes without saying */
1170                 return get_nth_ancestor(r, name, len1, oid, num);
1171         }
1172
1173         ret = peel_onion(r, name, len, oid, lookup_flags);
1174         if (!ret)
1175                 return FOUND;
1176
1177         ret = get_oid_basic(r, name, len, oid, lookup_flags);
1178         if (!ret)
1179                 return FOUND;
1180
1181         /* It could be describe output that is "SOMETHING-gXXXX" */
1182         ret = get_describe_name(r, name, len, oid);
1183         if (!ret)
1184                 return FOUND;
1185
1186         return get_short_oid(r, name, len, oid, lookup_flags);
1187 }
1188
1189 /*
1190  * This interprets names like ':/Initial revision of "git"' by searching
1191  * through history and returning the first commit whose message starts
1192  * the given regular expression.
1193  *
1194  * For negative-matching, prefix the pattern-part with '!-', like: ':/!-WIP'.
1195  *
1196  * For a literal '!' character at the beginning of a pattern, you have to repeat
1197  * that, like: ':/!!foo'
1198  *
1199  * For future extension, all other sequences beginning with ':/!' are reserved.
1200  */
1201
1202 /* Remember to update object flag allocation in object.h */
1203 #define ONELINE_SEEN (1u<<20)
1204
1205 struct handle_one_ref_cb {
1206         struct repository *repo;
1207         struct commit_list **list;
1208 };
1209
1210 static int handle_one_ref(const char *path, const struct object_id *oid,
1211                           int flag, void *cb_data)
1212 {
1213         struct handle_one_ref_cb *cb = cb_data;
1214         struct commit_list **list = cb->list;
1215         struct object *object = parse_object(cb->repo, oid);
1216         if (!object)
1217                 return 0;
1218         if (object->type == OBJ_TAG) {
1219                 object = deref_tag(cb->repo, object, path,
1220                                    strlen(path));
1221                 if (!object)
1222                         return 0;
1223         }
1224         if (object->type != OBJ_COMMIT)
1225                 return 0;
1226         commit_list_insert((struct commit *)object, list);
1227         return 0;
1228 }
1229
1230 static int get_oid_oneline(struct repository *r,
1231                            const char *prefix, struct object_id *oid,
1232                            struct commit_list *list)
1233 {
1234         struct commit_list *backup = NULL, *l;
1235         int found = 0;
1236         int negative = 0;
1237         regex_t regex;
1238
1239         if (prefix[0] == '!') {
1240                 prefix++;
1241
1242                 if (prefix[0] == '-') {
1243                         prefix++;
1244                         negative = 1;
1245                 } else if (prefix[0] != '!') {
1246                         return -1;
1247                 }
1248         }
1249
1250         if (regcomp(&regex, prefix, REG_EXTENDED))
1251                 return -1;
1252
1253         for (l = list; l; l = l->next) {
1254                 l->item->object.flags |= ONELINE_SEEN;
1255                 commit_list_insert(l->item, &backup);
1256         }
1257         while (list) {
1258                 const char *p, *buf;
1259                 struct commit *commit;
1260                 int matches;
1261
1262                 commit = pop_most_recent_commit(&list, ONELINE_SEEN);
1263                 if (!parse_object(r, &commit->object.oid))
1264                         continue;
1265                 buf = get_commit_buffer(commit, NULL);
1266                 p = strstr(buf, "\n\n");
1267                 matches = negative ^ (p && !regexec(&regex, p + 2, 0, NULL, 0));
1268                 unuse_commit_buffer(commit, buf);
1269
1270                 if (matches) {
1271                         oidcpy(oid, &commit->object.oid);
1272                         found = 1;
1273                         break;
1274                 }
1275         }
1276         regfree(&regex);
1277         free_commit_list(list);
1278         for (l = backup; l; l = l->next)
1279                 clear_commit_marks(l->item, ONELINE_SEEN);
1280         free_commit_list(backup);
1281         return found ? 0 : -1;
1282 }
1283
1284 struct grab_nth_branch_switch_cbdata {
1285         int remaining;
1286         struct strbuf *sb;
1287 };
1288
1289 static int grab_nth_branch_switch(struct object_id *ooid, struct object_id *noid,
1290                                   const char *email, timestamp_t timestamp, int tz,
1291                                   const char *message, void *cb_data)
1292 {
1293         struct grab_nth_branch_switch_cbdata *cb = cb_data;
1294         const char *match = NULL, *target = NULL;
1295         size_t len;
1296
1297         if (skip_prefix(message, "checkout: moving from ", &match))
1298                 target = strstr(match, " to ");
1299
1300         if (!match || !target)
1301                 return 0;
1302         if (--(cb->remaining) == 0) {
1303                 len = target - match;
1304                 strbuf_reset(cb->sb);
1305                 strbuf_add(cb->sb, match, len);
1306                 return 1; /* we are done */
1307         }
1308         return 0;
1309 }
1310
1311 /*
1312  * Parse @{-N} syntax, return the number of characters parsed
1313  * if successful; otherwise signal an error with negative value.
1314  */
1315 static int interpret_nth_prior_checkout(struct repository *r,
1316                                         const char *name, int namelen,
1317                                         struct strbuf *buf)
1318 {
1319         long nth;
1320         int retval;
1321         struct grab_nth_branch_switch_cbdata cb;
1322         const char *brace;
1323         char *num_end;
1324
1325         if (namelen < 4)
1326                 return -1;
1327         if (name[0] != '@' || name[1] != '{' || name[2] != '-')
1328                 return -1;
1329         brace = memchr(name, '}', namelen);
1330         if (!brace)
1331                 return -1;
1332         nth = strtol(name + 3, &num_end, 10);
1333         if (num_end != brace)
1334                 return -1;
1335         if (nth <= 0)
1336                 return -1;
1337         cb.remaining = nth;
1338         cb.sb = buf;
1339
1340         retval = refs_for_each_reflog_ent_reverse(get_main_ref_store(r),
1341                         "HEAD", grab_nth_branch_switch, &cb);
1342         if (0 < retval) {
1343                 retval = brace - name + 1;
1344         } else
1345                 retval = 0;
1346
1347         return retval;
1348 }
1349
1350 int repo_get_oid_mb(struct repository *r,
1351                     const char *name,
1352                     struct object_id *oid)
1353 {
1354         struct commit *one, *two;
1355         struct commit_list *mbs;
1356         struct object_id oid_tmp;
1357         const char *dots;
1358         int st;
1359
1360         dots = strstr(name, "...");
1361         if (!dots)
1362                 return repo_get_oid(r, name, oid);
1363         if (dots == name)
1364                 st = repo_get_oid(r, "HEAD", &oid_tmp);
1365         else {
1366                 struct strbuf sb;
1367                 strbuf_init(&sb, dots - name);
1368                 strbuf_add(&sb, name, dots - name);
1369                 st = repo_get_oid_committish(r, sb.buf, &oid_tmp);
1370                 strbuf_release(&sb);
1371         }
1372         if (st)
1373                 return st;
1374         one = lookup_commit_reference_gently(r, &oid_tmp, 0);
1375         if (!one)
1376                 return -1;
1377
1378         if (repo_get_oid_committish(r, dots[3] ? (dots + 3) : "HEAD", &oid_tmp))
1379                 return -1;
1380         two = lookup_commit_reference_gently(r, &oid_tmp, 0);
1381         if (!two)
1382                 return -1;
1383         mbs = repo_get_merge_bases(r, one, two);
1384         if (!mbs || mbs->next)
1385                 st = -1;
1386         else {
1387                 st = 0;
1388                 oidcpy(oid, &mbs->item->object.oid);
1389         }
1390         free_commit_list(mbs);
1391         return st;
1392 }
1393
1394 /* parse @something syntax, when 'something' is not {.*} */
1395 static int interpret_empty_at(const char *name, int namelen, int len, struct strbuf *buf)
1396 {
1397         const char *next;
1398
1399         if (len || name[1] == '{')
1400                 return -1;
1401
1402         /* make sure it's a single @, or @@{.*}, not @foo */
1403         next = memchr(name + len + 1, '@', namelen - len - 1);
1404         if (next && next[1] != '{')
1405                 return -1;
1406         if (!next)
1407                 next = name + namelen;
1408         if (next != name + 1)
1409                 return -1;
1410
1411         strbuf_reset(buf);
1412         strbuf_add(buf, "HEAD", 4);
1413         return 1;
1414 }
1415
1416 static int reinterpret(struct repository *r,
1417                        const char *name, int namelen, int len,
1418                        struct strbuf *buf, unsigned allowed)
1419 {
1420         /* we have extra data, which might need further processing */
1421         struct strbuf tmp = STRBUF_INIT;
1422         int used = buf->len;
1423         int ret;
1424         struct interpret_branch_name_options options = {
1425                 .allowed = allowed
1426         };
1427
1428         strbuf_add(buf, name + len, namelen - len);
1429         ret = repo_interpret_branch_name(r, buf->buf, buf->len, &tmp, &options);
1430         /* that data was not interpreted, remove our cruft */
1431         if (ret < 0) {
1432                 strbuf_setlen(buf, used);
1433                 return len;
1434         }
1435         strbuf_reset(buf);
1436         strbuf_addbuf(buf, &tmp);
1437         strbuf_release(&tmp);
1438         /* tweak for size of {-N} versus expanded ref name */
1439         return ret - used + len;
1440 }
1441
1442 static void set_shortened_ref(struct repository *r, struct strbuf *buf, const char *ref)
1443 {
1444         char *s = refs_shorten_unambiguous_ref(get_main_ref_store(r), ref, 0);
1445         strbuf_reset(buf);
1446         strbuf_addstr(buf, s);
1447         free(s);
1448 }
1449
1450 static int branch_interpret_allowed(const char *refname, unsigned allowed)
1451 {
1452         if (!allowed)
1453                 return 1;
1454
1455         if ((allowed & INTERPRET_BRANCH_LOCAL) &&
1456             starts_with(refname, "refs/heads/"))
1457                 return 1;
1458         if ((allowed & INTERPRET_BRANCH_REMOTE) &&
1459             starts_with(refname, "refs/remotes/"))
1460                 return 1;
1461
1462         return 0;
1463 }
1464
1465 static int interpret_branch_mark(struct repository *r,
1466                                  const char *name, int namelen,
1467                                  int at, struct strbuf *buf,
1468                                  int (*get_mark)(const char *, int),
1469                                  const char *(*get_data)(struct branch *,
1470                                                          struct strbuf *),
1471                                  const struct interpret_branch_name_options *options)
1472 {
1473         int len;
1474         struct branch *branch;
1475         struct strbuf err = STRBUF_INIT;
1476         const char *value;
1477
1478         len = get_mark(name + at, namelen - at);
1479         if (!len)
1480                 return -1;
1481
1482         if (memchr(name, ':', at))
1483                 return -1;
1484
1485         if (at) {
1486                 char *name_str = xmemdupz(name, at);
1487                 branch = branch_get(name_str);
1488                 free(name_str);
1489         } else
1490                 branch = branch_get(NULL);
1491
1492         value = get_data(branch, &err);
1493         if (!value) {
1494                 if (options->nonfatal_dangling_mark) {
1495                         strbuf_release(&err);
1496                         return -1;
1497                 } else {
1498                         die("%s", err.buf);
1499                 }
1500         }
1501
1502         if (!branch_interpret_allowed(value, options->allowed))
1503                 return -1;
1504
1505         set_shortened_ref(r, buf, value);
1506         return len + at;
1507 }
1508
1509 int repo_interpret_branch_name(struct repository *r,
1510                                const char *name, int namelen,
1511                                struct strbuf *buf,
1512                                const struct interpret_branch_name_options *options)
1513 {
1514         char *at;
1515         const char *start;
1516         int len;
1517
1518         if (!namelen)
1519                 namelen = strlen(name);
1520
1521         if (!options->allowed || (options->allowed & INTERPRET_BRANCH_LOCAL)) {
1522                 len = interpret_nth_prior_checkout(r, name, namelen, buf);
1523                 if (!len) {
1524                         return len; /* syntax Ok, not enough switches */
1525                 } else if (len > 0) {
1526                         if (len == namelen)
1527                                 return len; /* consumed all */
1528                         else
1529                                 return reinterpret(r, name, namelen, len, buf,
1530                                                    options->allowed);
1531                 }
1532         }
1533
1534         for (start = name;
1535              (at = memchr(start, '@', namelen - (start - name)));
1536              start = at + 1) {
1537
1538                 if (!options->allowed || (options->allowed & INTERPRET_BRANCH_HEAD)) {
1539                         len = interpret_empty_at(name, namelen, at - name, buf);
1540                         if (len > 0)
1541                                 return reinterpret(r, name, namelen, len, buf,
1542                                                    options->allowed);
1543                 }
1544
1545                 len = interpret_branch_mark(r, name, namelen, at - name, buf,
1546                                             upstream_mark, branch_get_upstream,
1547                                             options);
1548                 if (len > 0)
1549                         return len;
1550
1551                 len = interpret_branch_mark(r, name, namelen, at - name, buf,
1552                                             push_mark, branch_get_push,
1553                                             options);
1554                 if (len > 0)
1555                         return len;
1556         }
1557
1558         return -1;
1559 }
1560
1561 void strbuf_branchname(struct strbuf *sb, const char *name, unsigned allowed)
1562 {
1563         int len = strlen(name);
1564         struct interpret_branch_name_options options = {
1565                 .allowed = allowed
1566         };
1567         int used = interpret_branch_name(name, len, sb, &options);
1568
1569         if (used < 0)
1570                 used = 0;
1571         strbuf_add(sb, name + used, len - used);
1572 }
1573
1574 int strbuf_check_branch_ref(struct strbuf *sb, const char *name)
1575 {
1576         if (startup_info->have_repository)
1577                 strbuf_branchname(sb, name, INTERPRET_BRANCH_LOCAL);
1578         else
1579                 strbuf_addstr(sb, name);
1580
1581         /*
1582          * This splice must be done even if we end up rejecting the
1583          * name; builtin/branch.c::copy_or_rename_branch() still wants
1584          * to see what the name expanded to so that "branch -m" can be
1585          * used as a tool to correct earlier mistakes.
1586          */
1587         strbuf_splice(sb, 0, 0, "refs/heads/", 11);
1588
1589         if (*name == '-' ||
1590             !strcmp(sb->buf, "refs/heads/HEAD"))
1591                 return -1;
1592
1593         return check_refname_format(sb->buf, 0);
1594 }
1595
1596 /*
1597  * This is like "get_oid_basic()", except it allows "object ID expressions",
1598  * notably "xyz^" for "parent of xyz"
1599  */
1600 int repo_get_oid(struct repository *r, const char *name, struct object_id *oid)
1601 {
1602         struct object_context unused;
1603         return get_oid_with_context(r, name, 0, oid, &unused);
1604 }
1605
1606 /*
1607  * This returns a non-zero value if the string (built using printf
1608  * format and the given arguments) is not a valid object.
1609  */
1610 int get_oidf(struct object_id *oid, const char *fmt, ...)
1611 {
1612         va_list ap;
1613         int ret;
1614         struct strbuf sb = STRBUF_INIT;
1615
1616         va_start(ap, fmt);
1617         strbuf_vaddf(&sb, fmt, ap);
1618         va_end(ap);
1619
1620         ret = get_oid(sb.buf, oid);
1621         strbuf_release(&sb);
1622
1623         return ret;
1624 }
1625
1626 /*
1627  * Many callers know that the user meant to name a commit-ish by
1628  * syntactical positions where the object name appears.  Calling this
1629  * function allows the machinery to disambiguate shorter-than-unique
1630  * abbreviated object names between commit-ish and others.
1631  *
1632  * Note that this does NOT error out when the named object is not a
1633  * commit-ish. It is merely to give a hint to the disambiguation
1634  * machinery.
1635  */
1636 int repo_get_oid_committish(struct repository *r,
1637                             const char *name,
1638                             struct object_id *oid)
1639 {
1640         struct object_context unused;
1641         return get_oid_with_context(r, name, GET_OID_COMMITTISH,
1642                                     oid, &unused);
1643 }
1644
1645 int repo_get_oid_treeish(struct repository *r,
1646                          const char *name,
1647                          struct object_id *oid)
1648 {
1649         struct object_context unused;
1650         return get_oid_with_context(r, name, GET_OID_TREEISH,
1651                                     oid, &unused);
1652 }
1653
1654 int repo_get_oid_commit(struct repository *r,
1655                         const char *name,
1656                         struct object_id *oid)
1657 {
1658         struct object_context unused;
1659         return get_oid_with_context(r, name, GET_OID_COMMIT,
1660                                     oid, &unused);
1661 }
1662
1663 int repo_get_oid_tree(struct repository *r,
1664                       const char *name,
1665                       struct object_id *oid)
1666 {
1667         struct object_context unused;
1668         return get_oid_with_context(r, name, GET_OID_TREE,
1669                                     oid, &unused);
1670 }
1671
1672 int repo_get_oid_blob(struct repository *r,
1673                       const char *name,
1674                       struct object_id *oid)
1675 {
1676         struct object_context unused;
1677         return get_oid_with_context(r, name, GET_OID_BLOB,
1678                                     oid, &unused);
1679 }
1680
1681 /* Must be called only when object_name:filename doesn't exist. */
1682 static void diagnose_invalid_oid_path(struct repository *r,
1683                                       const char *prefix,
1684                                       const char *filename,
1685                                       const struct object_id *tree_oid,
1686                                       const char *object_name,
1687                                       int object_name_len)
1688 {
1689         struct object_id oid;
1690         unsigned short mode;
1691
1692         if (!prefix)
1693                 prefix = "";
1694
1695         if (file_exists(filename))
1696                 die(_("path '%s' exists on disk, but not in '%.*s'"),
1697                     filename, object_name_len, object_name);
1698         if (is_missing_file_error(errno)) {
1699                 char *fullname = xstrfmt("%s%s", prefix, filename);
1700
1701                 if (!get_tree_entry(r, tree_oid, fullname, &oid, &mode)) {
1702                         die(_("path '%s' exists, but not '%s'\n"
1703                             "hint: Did you mean '%.*s:%s' aka '%.*s:./%s'?"),
1704                             fullname,
1705                             filename,
1706                             object_name_len, object_name,
1707                             fullname,
1708                             object_name_len, object_name,
1709                             filename);
1710                 }
1711                 die(_("path '%s' does not exist in '%.*s'"),
1712                     filename, object_name_len, object_name);
1713         }
1714 }
1715
1716 /* Must be called only when :stage:filename doesn't exist. */
1717 static void diagnose_invalid_index_path(struct repository *r,
1718                                         int stage,
1719                                         const char *prefix,
1720                                         const char *filename)
1721 {
1722         struct index_state *istate = r->index;
1723         const struct cache_entry *ce;
1724         int pos;
1725         unsigned namelen = strlen(filename);
1726         struct strbuf fullname = STRBUF_INIT;
1727
1728         if (!prefix)
1729                 prefix = "";
1730
1731         /* Wrong stage number? */
1732         pos = index_name_pos(istate, filename, namelen);
1733         if (pos < 0)
1734                 pos = -pos - 1;
1735         if (pos < istate->cache_nr) {
1736                 ce = istate->cache[pos];
1737                 if (ce_namelen(ce) == namelen &&
1738                     !memcmp(ce->name, filename, namelen))
1739                         die(_("path '%s' is in the index, but not at stage %d\n"
1740                             "hint: Did you mean ':%d:%s'?"),
1741                             filename, stage,
1742                             ce_stage(ce), filename);
1743         }
1744
1745         /* Confusion between relative and absolute filenames? */
1746         strbuf_addstr(&fullname, prefix);
1747         strbuf_addstr(&fullname, filename);
1748         pos = index_name_pos(istate, fullname.buf, fullname.len);
1749         if (pos < 0)
1750                 pos = -pos - 1;
1751         if (pos < istate->cache_nr) {
1752                 ce = istate->cache[pos];
1753                 if (ce_namelen(ce) == fullname.len &&
1754                     !memcmp(ce->name, fullname.buf, fullname.len))
1755                         die(_("path '%s' is in the index, but not '%s'\n"
1756                             "hint: Did you mean ':%d:%s' aka ':%d:./%s'?"),
1757                             fullname.buf, filename,
1758                             ce_stage(ce), fullname.buf,
1759                             ce_stage(ce), filename);
1760         }
1761
1762         if (repo_file_exists(r, filename))
1763                 die(_("path '%s' exists on disk, but not in the index"), filename);
1764         if (is_missing_file_error(errno))
1765                 die(_("path '%s' does not exist (neither on disk nor in the index)"),
1766                     filename);
1767
1768         strbuf_release(&fullname);
1769 }
1770
1771
1772 static char *resolve_relative_path(struct repository *r, const char *rel)
1773 {
1774         if (!starts_with(rel, "./") && !starts_with(rel, "../"))
1775                 return NULL;
1776
1777         if (r != the_repository || !is_inside_work_tree())
1778                 die(_("relative path syntax can't be used outside working tree"));
1779
1780         /* die() inside prefix_path() if resolved path is outside worktree */
1781         return prefix_path(startup_info->prefix,
1782                            startup_info->prefix ? strlen(startup_info->prefix) : 0,
1783                            rel);
1784 }
1785
1786 static enum get_oid_result get_oid_with_context_1(struct repository *repo,
1787                                   const char *name,
1788                                   unsigned flags,
1789                                   const char *prefix,
1790                                   struct object_id *oid,
1791                                   struct object_context *oc)
1792 {
1793         int ret, bracket_depth;
1794         int namelen = strlen(name);
1795         const char *cp;
1796         int only_to_die = flags & GET_OID_ONLY_TO_DIE;
1797
1798         if (only_to_die)
1799                 flags |= GET_OID_QUIETLY;
1800
1801         memset(oc, 0, sizeof(*oc));
1802         oc->mode = S_IFINVALID;
1803         strbuf_init(&oc->symlink_path, 0);
1804         ret = get_oid_1(repo, name, namelen, oid, flags);
1805         if (!ret)
1806                 return ret;
1807         /*
1808          * tree:path --> object name of path in tree
1809          * :path -> object name of absolute path in index
1810          * :./path -> object name of path relative to cwd in index
1811          * :[0-3]:path -> object name of path in index at stage
1812          * :/foo -> recent commit matching foo
1813          */
1814         if (name[0] == ':') {
1815                 int stage = 0;
1816                 const struct cache_entry *ce;
1817                 char *new_path = NULL;
1818                 int pos;
1819                 if (!only_to_die && namelen > 2 && name[1] == '/') {
1820                         struct handle_one_ref_cb cb;
1821                         struct commit_list *list = NULL;
1822
1823                         cb.repo = repo;
1824                         cb.list = &list;
1825                         refs_for_each_ref(get_main_ref_store(repo), handle_one_ref, &cb);
1826                         refs_head_ref(get_main_ref_store(repo), handle_one_ref, &cb);
1827                         commit_list_sort_by_date(&list);
1828                         return get_oid_oneline(repo, name + 2, oid, list);
1829                 }
1830                 if (namelen < 3 ||
1831                     name[2] != ':' ||
1832                     name[1] < '0' || '3' < name[1])
1833                         cp = name + 1;
1834                 else {
1835                         stage = name[1] - '0';
1836                         cp = name + 3;
1837                 }
1838                 new_path = resolve_relative_path(repo, cp);
1839                 if (!new_path) {
1840                         namelen = namelen - (cp - name);
1841                 } else {
1842                         cp = new_path;
1843                         namelen = strlen(cp);
1844                 }
1845
1846                 if (flags & GET_OID_RECORD_PATH)
1847                         oc->path = xstrdup(cp);
1848
1849                 if (!repo->index || !repo->index->cache)
1850                         repo_read_index(repo);
1851                 pos = index_name_pos(repo->index, cp, namelen);
1852                 if (pos < 0)
1853                         pos = -pos - 1;
1854                 while (pos < repo->index->cache_nr) {
1855                         ce = repo->index->cache[pos];
1856                         if (ce_namelen(ce) != namelen ||
1857                             memcmp(ce->name, cp, namelen))
1858                                 break;
1859                         if (ce_stage(ce) == stage) {
1860                                 oidcpy(oid, &ce->oid);
1861                                 oc->mode = ce->ce_mode;
1862                                 free(new_path);
1863                                 return 0;
1864                         }
1865                         pos++;
1866                 }
1867                 if (only_to_die && name[1] && name[1] != '/')
1868                         diagnose_invalid_index_path(repo, stage, prefix, cp);
1869                 free(new_path);
1870                 return -1;
1871         }
1872         for (cp = name, bracket_depth = 0; *cp; cp++) {
1873                 if (*cp == '{')
1874                         bracket_depth++;
1875                 else if (bracket_depth && *cp == '}')
1876                         bracket_depth--;
1877                 else if (!bracket_depth && *cp == ':')
1878                         break;
1879         }
1880         if (*cp == ':') {
1881                 struct object_id tree_oid;
1882                 int len = cp - name;
1883                 unsigned sub_flags = flags;
1884
1885                 sub_flags &= ~GET_OID_DISAMBIGUATORS;
1886                 sub_flags |= GET_OID_TREEISH;
1887
1888                 if (!get_oid_1(repo, name, len, &tree_oid, sub_flags)) {
1889                         const char *filename = cp+1;
1890                         char *new_filename = NULL;
1891
1892                         new_filename = resolve_relative_path(repo, filename);
1893                         if (new_filename)
1894                                 filename = new_filename;
1895                         if (flags & GET_OID_FOLLOW_SYMLINKS) {
1896                                 ret = get_tree_entry_follow_symlinks(repo, &tree_oid,
1897                                         filename, oid, &oc->symlink_path,
1898                                         &oc->mode);
1899                         } else {
1900                                 ret = get_tree_entry(repo, &tree_oid, filename, oid,
1901                                                      &oc->mode);
1902                                 if (ret && only_to_die) {
1903                                         diagnose_invalid_oid_path(repo, prefix,
1904                                                                    filename,
1905                                                                    &tree_oid,
1906                                                                    name, len);
1907                                 }
1908                         }
1909                         if (flags & GET_OID_RECORD_PATH)
1910                                 oc->path = xstrdup(filename);
1911
1912                         free(new_filename);
1913                         return ret;
1914                 } else {
1915                         if (only_to_die)
1916                                 die(_("invalid object name '%.*s'."), len, name);
1917                 }
1918         }
1919         return ret;
1920 }
1921
1922 /*
1923  * Call this function when you know "name" given by the end user must
1924  * name an object but it doesn't; the function _may_ die with a better
1925  * diagnostic message than "no such object 'name'", e.g. "Path 'doc' does not
1926  * exist in 'HEAD'" when given "HEAD:doc", or it may return in which case
1927  * you have a chance to diagnose the error further.
1928  */
1929 void maybe_die_on_misspelt_object_name(struct repository *r,
1930                                        const char *name,
1931                                        const char *prefix)
1932 {
1933         struct object_context oc;
1934         struct object_id oid;
1935         get_oid_with_context_1(r, name, GET_OID_ONLY_TO_DIE,
1936                                prefix, &oid, &oc);
1937 }
1938
1939 enum get_oid_result get_oid_with_context(struct repository *repo,
1940                                          const char *str,
1941                                          unsigned flags,
1942                                          struct object_id *oid,
1943                                          struct object_context *oc)
1944 {
1945         if (flags & GET_OID_FOLLOW_SYMLINKS && flags & GET_OID_ONLY_TO_DIE)
1946                 BUG("incompatible flags for get_oid_with_context");
1947         return get_oid_with_context_1(repo, str, flags, NULL, oid, oc);
1948 }