sha1_name.c

   1 #include "cache.h"
   2 #include "tag.h"
   3 #include "commit.h"
   4 #include "tree.h"
   5 #include "blob.h"
   6 #include "tree-walk.h"
   7 #include "refs.h"
   8 #include "remote.h"
   9
  10 static int get_sha1_oneline(const char *, unsigned char *, struct commit_list *);
  11
  12 static int find_short_object_filename(int len, const char *name, unsigned char *sha1)
  13 {
  14         struct alternate_object_database *alt;
  15         char hex[40];
  16         int found = 0;
  17         static struct alternate_object_database *fakeent;
  18
  19         if (!fakeent) {
  20                 /*
  21                  * Create a "fake" alternate object database that
  22                  * points to our own object database, to make it
  23                  * easier to get a temporary working space in
  24                  * alt->name/alt->base while iterating over the
  25                  * object databases including our own.
  26                  */
  27                 const char *objdir = get_object_directory();
  28                 int objdir_len = strlen(objdir);
  29                 int entlen = objdir_len + 43;
  30                 fakeent = xmalloc(sizeof(*fakeent) + entlen);
  31                 memcpy(fakeent->base, objdir, objdir_len);
  32                 fakeent->name = fakeent->base + objdir_len + 1;
  33                 fakeent->name[-1] = '/';
  34         }
  35         fakeent->next = alt_odb_list;
  36
  37         sprintf(hex, "%.2s", name);
  38         for (alt = fakeent; alt && found < 2; alt = alt->next) {
  39                 struct dirent *de;
  40                 DIR *dir;
  41                 sprintf(alt->name, "%.2s/", name);
  42                 dir = opendir(alt->base);
  43                 if (!dir)
  44                         continue;
  45                 while ((de = readdir(dir)) != NULL) {
  46                         if (strlen(de->d_name) != 38)
  47                                 continue;
  48                         if (memcmp(de->d_name, name + 2, len - 2))
  49                                 continue;
  50                         if (!found) {
  51                                 memcpy(hex + 2, de->d_name, 38);
  52                                 found++;
  53                         }
  54                         else if (memcmp(hex + 2, de->d_name, 38)) {
  55                                 found = 2;
  56                                 break;
  57                         }
  58                 }
  59                 closedir(dir);
  60         }
  61         if (found == 1)
  62                 return get_sha1_hex(hex, sha1) == 0;
  63         return found;
  64 }
  65
  66 static int match_sha(unsigned len, const unsigned char *a, const unsigned char *b)
  67 {
  68         do {
  69                 if (*a != *b)
  70                         return 0;
  71                 a++;
  72                 b++;
  73                 len -= 2;
  74         } while (len > 1);
  75         if (len)
  76                 if ((*a ^ *b) & 0xf0)
  77                         return 0;
  78         return 1;
  79 }
  80
  81 static int unique_in_pack(int len,
  82                           const unsigned char *match,
  83                           struct packed_git *p,
  84                           const unsigned char **found_sha1,
  85                           int seen_so_far)
  86 {
  87         uint32_t num, last, i, first = 0;
  88         const unsigned char *current = NULL;
  89
  90         open_pack_index(p);
  91         num = p->num_objects;
  92         last = num;
  93         while (first < last) {
  94                 uint32_t mid = (first + last) / 2;
  95                 const unsigned char *current;
  96                 int cmp;
  97
  98                 current = nth_packed_object_sha1(p, mid);
  99                 cmp = hashcmp(match, current);
 100                 if (!cmp) {
 101                         first = mid;
 102                         break;
 103                 }
 104                 if (cmp > 0) {
 105                         first = mid+1;
 106                         continue;
 107                 }
 108                 last = mid;
 109         }
 110
 111         /*
 112          * At this point, "first" is the location of the lowest object
 113          * with an object name that could match "match".  See if we have
 114          * 0, 1 or more objects that actually match(es).
 115          */
 116         for (i = first; i < num; i++) {
 117                 current = nth_packed_object_sha1(p, first);
 118                 if (!match_sha(len, match, current))
 119                         break;
 120
 121                 /* current matches */
 122                 if (!seen_so_far) {
 123                         *found_sha1 = current;
 124                         seen_so_far++;
 125                 } else if (seen_so_far) {
 126                         /* is it the same as the one previously found elsewhere? */
 127                         if (hashcmp(*found_sha1, current))
 128                                 return 2; /* definitely not unique */
 129                 }
 130         }
 131         return seen_so_far;
 132 }
 133
 134 static int find_short_packed_object(int len, const unsigned char *match, unsigned char *sha1)
 135 {
 136         struct packed_git *p;
 137         const unsigned char *found_sha1 = NULL;
 138         int found = 0;
 139
 140         prepare_packed_git();
 141         for (p = packed_git; p && found < 2; p = p->next)
 142                 found = unique_in_pack(len, match, p, &found_sha1, found);
 143
 144         if (found == 1)
 145                 hashcpy(sha1, found_sha1);
 146         return found;
 147 }
 148
 149 #define SHORT_NAME_NOT_FOUND (-1)
 150 #define SHORT_NAME_AMBIGUOUS (-2)
 151
 152 static int find_unique_short_object(int len, char *canonical,
 153                                     unsigned char *res, unsigned char *sha1)
 154 {
 155         int has_unpacked, has_packed;
 156         unsigned char unpacked_sha1[20], packed_sha1[20];
 157
 158         prepare_alt_odb();
 159         has_unpacked = find_short_object_filename(len, canonical, unpacked_sha1);
 160         has_packed = find_short_packed_object(len, res, packed_sha1);
 161         if (!has_unpacked && !has_packed)
 162                 return SHORT_NAME_NOT_FOUND;
 163         if (1 < has_unpacked || 1 < has_packed)
 164                 return SHORT_NAME_AMBIGUOUS;
 165         if (has_unpacked != has_packed) {
 166                 hashcpy(sha1, (has_packed ? packed_sha1 : unpacked_sha1));
 167                 return 0;
 168         }
 169         /* Both have unique ones -- do they match? */
 170         if (hashcmp(packed_sha1, unpacked_sha1))
 171                 return SHORT_NAME_AMBIGUOUS;
 172         hashcpy(sha1, packed_sha1);
 173         return 0;
 174 }
 175
 176 static int get_short_sha1(const char *name, int len, unsigned char *sha1,
 177                           int quietly)
 178 {
 179         int i, status;
 180         char canonical[40];
 181         unsigned char res[20];
 182
 183         if (len < MINIMUM_ABBREV || len > 40)
 184                 return -1;
 185         hashclr(res);
 186         memset(canonical, 'x', 40);
 187         for (i = 0; i < len ;i++) {
 188                 unsigned char c = name[i];
 189                 unsigned char val;
 190                 if (c >= '0' && c <= '9')
 191                         val = c - '0';
 192                 else if (c >= 'a' && c <= 'f')
 193                         val = c - 'a' + 10;
 194                 else if (c >= 'A' && c <='F') {
 195                         val = c - 'A' + 10;
 196                         c -= 'A' - 'a';
 197                 }
 198                 else
 199                         return -1;
 200                 canonical[i] = c;
 201                 if (!(i & 1))
 202                         val <<= 4;
 203                 res[i >> 1] |= val;
 204         }
 205
 206         status = find_unique_short_object(i, canonical, res, sha1);
 207         if (!quietly && (status == SHORT_NAME_AMBIGUOUS))
 208                 return error("short SHA1 %.*s is ambiguous.", len, canonical);
 209         return status;
 210 }
 211
 212 const char *find_unique_abbrev(const unsigned char *sha1, int len)
 213 {
 214         int status, exists;
 215         static char hex[41];
 216
 217         exists = has_sha1_file(sha1);
 218         memcpy(hex, sha1_to_hex(sha1), 40);
 219         if (len == 40 || !len)
 220                 return hex;
 221         while (len < 40) {
 222                 unsigned char sha1_ret[20];
 223                 status = get_short_sha1(hex, len, sha1_ret, 1);
 224                 if (exists
 225                     ? !status
 226                     : status == SHORT_NAME_NOT_FOUND) {
 227                         hex[len] = 0;
 228                         return hex;
 229                 }
 230                 len++;
 231         }
 232         return hex;
 233 }
 234
 235 static int ambiguous_path(const char *path, int len)
 236 {
 237         int slash = 1;
 238         int cnt;
 239
 240         for (cnt = 0; cnt < len; cnt++) {
 241                 switch (*path++) {
 242                 case '\0':
 243                         break;
 244                 case '/':
 245                         if (slash)
 246                                 break;
 247                         slash = 1;
 248                         continue;
 249                 case '.':
 250                         continue;
 251                 default:
 252                         slash = 0;
 253                         continue;
 254                 }
 255                 break;
 256         }
 257         return slash;
 258 }
 259
 260 static inline int upstream_mark(const char *string, int len)
 261 {
 262         const char *suffix[] = { "@{upstream}", "@{u}" };
 263         int i;
 264
 265         for (i = 0; i < ARRAY_SIZE(suffix); i++) {
 266                 int suffix_len = strlen(suffix[i]);
 267                 if (suffix_len <= len
 268                     && !memcmp(string, suffix[i], suffix_len))
 269                         return suffix_len;
 270         }
 271         return 0;
 272 }
 273
 274 static int get_sha1_1(const char *name, int len, unsigned char *sha1);
 275
 276 static int get_sha1_basic(const char *str, int len, unsigned char *sha1)
 277 {
 278         static const char *warn_msg = "refname '%.*s' is ambiguous.";
 279         char *real_ref = NULL;
 280         int refs_found = 0;
 281         int at, reflog_len;
 282
 283         if (len == 40 && !get_sha1_hex(str, sha1))
 284                 return 0;
 285
 286         /* basic@{time or number or -number} format to query ref-log */
 287         reflog_len = at = 0;
 288         if (len && str[len-1] == '}') {
 289                 for (at = len-2; at >= 0; at--) {
 290                         if (str[at] == '@' && str[at+1] == '{') {
 291                                 if (!upstream_mark(str + at, len - at)) {
 292                                         reflog_len = (len-1) - (at+2);
 293                                         len = at;
 294                                 }
 295                                 break;
 296                         }
 297                 }
 298         }
 299
 300         /* Accept only unambiguous ref paths. */
 301         if (len && ambiguous_path(str, len))
 302                 return -1;
 303
 304         if (!len && reflog_len) {
 305                 struct strbuf buf = STRBUF_INIT;
 306                 int ret;
 307                 /* try the @{-N} syntax for n-th checkout */
 308                 ret = interpret_branch_name(str+at, &buf);
 309                 if (ret > 0) {
 310                         /* substitute this branch name and restart */
 311                         return get_sha1_1(buf.buf, buf.len, sha1);
 312                 } else if (ret == 0) {
 313                         return -1;
 314                 }
 315                 /* allow "@{...}" to mean the current branch reflog */
 316                 refs_found = dwim_ref("HEAD", 4, sha1, &real_ref);
 317         } else if (reflog_len)
 318                 refs_found = dwim_log(str, len, sha1, &real_ref);
 319         else
 320                 refs_found = dwim_ref(str, len, sha1, &real_ref);
 321
 322         if (!refs_found)
 323                 return -1;
 324
 325         if (warn_ambiguous_refs && refs_found > 1)
 326                 warning(warn_msg, len, str);
 327
 328         if (reflog_len) {
 329                 int nth, i;
 330                 unsigned long at_time;
 331                 unsigned long co_time;
 332                 int co_tz, co_cnt;
 333
 334                 /* a @{-N} placed anywhere except the start is an error */
 335                 if (str[at+2] == '-')
 336                         return -1;
 337
 338                 /* Is it asking for N-th entry, or approxidate? */
 339                 for (i = nth = 0; 0 <= nth && i < reflog_len; i++) {
 340                         char ch = str[at+2+i];
 341                         if ('0' <= ch && ch <= '9')
 342                                 nth = nth * 10 + ch - '0';
 343                         else
 344                                 nth = -1;
 345                 }
 346                 if (100000000 <= nth) {
 347                         at_time = nth;
 348                         nth = -1;
 349                 } else if (0 <= nth)
 350                         at_time = 0;
 351                 else {
 352                         int errors = 0;
 353                         char *tmp = xstrndup(str + at + 2, reflog_len);
 354                         at_time = approxidate_careful(tmp, &errors);
 355                         free(tmp);
 356                         if (errors)
 357                                 return -1;
 358                 }
 359                 if (read_ref_at(real_ref, at_time, nth, sha1, NULL,
 360                                 &co_time, &co_tz, &co_cnt)) {
 361                         if (at_time)
 362                                 warning("Log for '%.*s' only goes "
 363                                         "back to %s.", len, str,
 364                                         show_date(co_time, co_tz, DATE_RFC2822));
 365                         else {
 366                                 free(real_ref);
 367                                 die("Log for '%.*s' only has %d entries.",
 368                                     len, str, co_cnt);
 369                         }
 370                 }
 371         }
 372
 373         free(real_ref);
 374         return 0;
 375 }
 376
 377 static int get_parent(const char *name, int len,
 378                       unsigned char *result, int idx)
 379 {
 380         unsigned char sha1[20];
 381         int ret = get_sha1_1(name, len, sha1);
 382         struct commit *commit;
 383         struct commit_list *p;
 384
 385         if (ret)
 386                 return ret;
 387         commit = lookup_commit_reference(sha1);
 388         if (!commit)
 389                 return -1;
 390         if (parse_commit(commit))
 391                 return -1;
 392         if (!idx) {
 393                 hashcpy(result, commit->object.sha1);
 394                 return 0;
 395         }
 396         p = commit->parents;
 397         while (p) {
 398                 if (!--idx) {
 399                         hashcpy(result, p->item->object.sha1);
 400                         return 0;
 401                 }
 402                 p = p->next;
 403         }
 404         return -1;
 405 }
 406
 407 static int get_nth_ancestor(const char *name, int len,
 408                             unsigned char *result, int generation)
 409 {
 410         unsigned char sha1[20];
 411         struct commit *commit;
 412         int ret;
 413
 414         ret = get_sha1_1(name, len, sha1);
 415         if (ret)
 416                 return ret;
 417         commit = lookup_commit_reference(sha1);
 418         if (!commit)
 419                 return -1;
 420
 421         while (generation--) {
 422                 if (parse_commit(commit) || !commit->parents)
 423                         return -1;
 424                 commit = commit->parents->item;
 425         }
 426         hashcpy(result, commit->object.sha1);
 427         return 0;
 428 }
 429
 430 struct object *peel_to_type(const char *name, int namelen,
 431                             struct object *o, enum object_type expected_type)
 432 {
 433         if (name && !namelen)
 434                 namelen = strlen(name);
 435         while (1) {
 436                 if (!o || (!o->parsed && !parse_object(o->sha1)))
 437                         return NULL;
 438                 if (o->type == expected_type)
 439                         return o;
 440                 if (o->type == OBJ_TAG)
 441                         o = ((struct tag*) o)->tagged;
 442                 else if (o->type == OBJ_COMMIT)
 443                         o = &(((struct commit *) o)->tree->object);
 444                 else {
 445                         if (name)
 446                                 error("%.*s: expected %s type, but the object "
 447                                       "dereferences to %s type",
 448                                       namelen, name, typename(expected_type),
 449                                       typename(o->type));
 450                         return NULL;
 451                 }
 452         }
 453 }
 454
 455 static int peel_onion(const char *name, int len, unsigned char *sha1)
 456 {
 457         unsigned char outer[20];
 458         const char *sp;
 459         unsigned int expected_type = 0;
 460         struct object *o;
 461
 462         /*
 463          * "ref^{type}" dereferences ref repeatedly until you cannot
 464          * dereference anymore, or you get an object of given type,
 465          * whichever comes first.  "ref^{}" means just dereference
 466          * tags until you get a non-tag.  "ref^0" is a shorthand for
 467          * "ref^{commit}".  "commit^{tree}" could be used to find the
 468          * top-level tree of the given commit.
 469          */
 470         if (len < 4 || name[len-1] != '}')
 471                 return -1;
 472
 473         for (sp = name + len - 1; name <= sp; sp--) {
 474                 int ch = *sp;
 475                 if (ch == '{' && name < sp && sp[-1] == '^')
 476                         break;
 477         }
 478         if (sp <= name)
 479                 return -1;
 480
 481         sp++; /* beginning of type name, or closing brace for empty */
 482         if (!strncmp(commit_type, sp, 6) && sp[6] == '}')
 483                 expected_type = OBJ_COMMIT;
 484         else if (!strncmp(tree_type, sp, 4) && sp[4] == '}')
 485                 expected_type = OBJ_TREE;
 486         else if (!strncmp(blob_type, sp, 4) && sp[4] == '}')
 487                 expected_type = OBJ_BLOB;
 488         else if (sp[0] == '}')
 489                 expected_type = OBJ_NONE;
 490         else if (sp[0] == '/')
 491                 expected_type = OBJ_COMMIT;
 492         else
 493                 return -1;
 494
 495         if (get_sha1_1(name, sp - name - 2, outer))
 496                 return -1;
 497
 498         o = parse_object(outer);
 499         if (!o)
 500                 return -1;
 501         if (!expected_type) {
 502                 o = deref_tag(o, name, sp - name - 2);
 503                 if (!o || (!o->parsed && !parse_object(o->sha1)))
 504                         return -1;
 505                 hashcpy(sha1, o->sha1);
 506                 return 0;
 507         }
 508
 509         /*
 510          * At this point, the syntax look correct, so
 511          * if we do not get the needed object, we should
 512          * barf.
 513          */
 514         o = peel_to_type(name, len, o, expected_type);
 515         if (!o)
 516                 return -1;
 517
 518         hashcpy(sha1, o->sha1);
 519         if (sp[0] == '/') {
 520                 /* "$commit^{/foo}" */
 521                 char *prefix;
 522                 int ret;
 523                 struct commit_list *list = NULL;
 524
 525                 /*
 526                  * $commit^{/}. Some regex implementation may reject.
 527                  * We don't need regex anyway. '' pattern always matches.
 528                  */
 529                 if (sp[1] == '}')
 530                         return 0;
 531
 532                 prefix = xstrndup(sp + 1, name + len - 1 - (sp + 1));
 533                 commit_list_insert((struct commit *)o, &list);
 534                 ret = get_sha1_oneline(prefix, sha1, list);
 535                 free(prefix);
 536                 return ret;
 537         }
 538         return 0;
 539 }
 540
 541 static int get_describe_name(const char *name, int len, unsigned char *sha1)
 542 {
 543         const char *cp;
 544
 545         for (cp = name + len - 1; name + 2 <= cp; cp--) {
 546                 char ch = *cp;
 547                 if (hexval(ch) & ~0377) {
 548                         /* We must be looking at g in "SOMETHING-g"
 549                          * for it to be describe output.
 550                          */
 551                         if (ch == 'g' && cp[-1] == '-') {
 552                                 cp++;
 553                                 len -= cp - name;
 554                                 return get_short_sha1(cp, len, sha1, 1);
 555                         }
 556                 }
 557         }
 558         return -1;
 559 }
 560
 561 static int get_sha1_1(const char *name, int len, unsigned char *sha1)
 562 {
 563         int ret, has_suffix;
 564         const char *cp;
 565
 566         /*
 567          * "name~3" is "name^^^", "name~" is "name~1", and "name^" is "name^1".
 568          */
 569         has_suffix = 0;
 570         for (cp = name + len - 1; name <= cp; cp--) {
 571                 int ch = *cp;
 572                 if ('0' <= ch && ch <= '9')
 573                         continue;
 574                 if (ch == '~' || ch == '^')
 575                         has_suffix = ch;
 576                 break;
 577         }
 578
 579         if (has_suffix) {
 580                 int num = 0;
 581                 int len1 = cp - name;
 582                 cp++;
 583                 while (cp < name + len)
 584                         num = num * 10 + *cp++ - '0';
 585                 if (!num && len1 == len - 1)
 586                         num = 1;
 587                 if (has_suffix == '^')
 588                         return get_parent(name, len1, sha1, num);
 589                 /* else if (has_suffix == '~') -- goes without saying */
 590                 return get_nth_ancestor(name, len1, sha1, num);
 591         }
 592
 593         ret = peel_onion(name, len, sha1);
 594         if (!ret)
 595                 return 0;
 596
 597         ret = get_sha1_basic(name, len, sha1);
 598         if (!ret)
 599                 return 0;
 600
 601         /* It could be describe output that is "SOMETHING-gXXXX" */
 602         ret = get_describe_name(name, len, sha1);
 603         if (!ret)
 604                 return 0;
 605
 606         return get_short_sha1(name, len, sha1, 0);
 607 }
 608
 609 /*
 610  * This interprets names like ':/Initial revision of "git"' by searching
 611  * through history and returning the first commit whose message starts
 612  * the given regular expression.
 613  *
 614  * For future extension, ':/!' is reserved. If you want to match a message
 615  * beginning with a '!', you have to repeat the exclamation mark.
 616  */
 617 #define ONELINE_SEEN (1u<<20)
 618
 619 static int handle_one_ref(const char *path,
 620                 const unsigned char *sha1, int flag, void *cb_data)
 621 {
 622         struct commit_list **list = cb_data;
 623         struct object *object = parse_object(sha1);
 624         if (!object)
 625                 return 0;
 626         if (object->type == OBJ_TAG) {
 627                 object = deref_tag(object, path, strlen(path));
 628                 if (!object)
 629                         return 0;
 630         }
 631         if (object->type != OBJ_COMMIT)
 632                 return 0;
 633         commit_list_insert_by_date((struct commit *)object, list);
 634         return 0;
 635 }
 636
 637 static int get_sha1_oneline(const char *prefix, unsigned char *sha1,
 638                             struct commit_list *list)
 639 {
 640         struct commit_list *backup = NULL, *l;
 641         int found = 0;
 642         regex_t regex;
 643
 644         if (prefix[0] == '!') {
 645                 if (prefix[1] != '!')
 646                         die ("Invalid search pattern: %s", prefix);
 647                 prefix++;
 648         }
 649
 650         if (regcomp(&regex, prefix, REG_EXTENDED))
 651                 die("Invalid search pattern: %s", prefix);
 652
 653         for (l = list; l; l = l->next) {
 654                 l->item->object.flags |= ONELINE_SEEN;
 655                 commit_list_insert(l->item, &backup);
 656         }
 657         while (list) {
 658                 char *p, *to_free = NULL;
 659                 struct commit *commit;
 660                 enum object_type type;
 661                 unsigned long size;
 662                 int matches;
 663
 664                 commit = pop_most_recent_commit(&list, ONELINE_SEEN);
 665                 if (!parse_object(commit->object.sha1))
 666                         continue;
 667                 if (commit->buffer)
 668                         p = commit->buffer;
 669                 else {
 670                         p = read_sha1_file(commit->object.sha1, &type, &size);
 671                         if (!p)
 672                                 continue;
 673                         to_free = p;
 674                 }
 675
 676                 p = strstr(p, "\n\n");
 677                 matches = p && !regexec(&regex, p + 2, 0, NULL, 0);
 678                 free(to_free);
 679
 680                 if (matches) {
 681                         hashcpy(sha1, commit->object.sha1);
 682                         found = 1;
 683                         break;
 684                 }
 685         }
 686         regfree(&regex);
 687         free_commit_list(list);
 688         for (l = backup; l; l = l->next)
 689                 clear_commit_marks(l->item, ONELINE_SEEN);
 690         free_commit_list(backup);
 691         return found ? 0 : -1;
 692 }
 693
 694 struct grab_nth_branch_switch_cbdata {
 695         long cnt, alloc;
 696         struct strbuf *buf;
 697 };
 698
 699 static int grab_nth_branch_switch(unsigned char *osha1, unsigned char *nsha1,
 700                                   const char *email, unsigned long timestamp, int tz,
 701                                   const char *message, void *cb_data)
 702 {
 703         struct grab_nth_branch_switch_cbdata *cb = cb_data;
 704         const char *match = NULL, *target = NULL;
 705         size_t len;
 706         int nth;
 707
 708         if (!prefixcmp(message, "checkout: moving from ")) {
 709                 match = message + strlen("checkout: moving from ");
 710                 target = strstr(match, " to ");
 711         }
 712
 713         if (!match || !target)
 714                 return 0;
 715
 716         len = target - match;
 717         nth = cb->cnt++ % cb->alloc;
 718         strbuf_reset(&cb->buf[nth]);
 719         strbuf_add(&cb->buf[nth], match, len);
 720         return 0;
 721 }
 722
 723 /*
 724  * Parse @{-N} syntax, return the number of characters parsed
 725  * if successful; otherwise signal an error with negative value.
 726  */
 727 static int interpret_nth_prior_checkout(const char *name, struct strbuf *buf)
 728 {
 729         long nth;
 730         int i, retval;
 731         struct grab_nth_branch_switch_cbdata cb;
 732         const char *brace;
 733         char *num_end;
 734
 735         if (name[0] != '@' || name[1] != '{' || name[2] != '-')
 736                 return -1;
 737         brace = strchr(name, '}');
 738         if (!brace)
 739                 return -1;
 740         nth = strtol(name+3, &num_end, 10);
 741         if (num_end != brace)
 742                 return -1;
 743         if (nth <= 0)
 744                 return -1;
 745         cb.alloc = nth;
 746         cb.buf = xmalloc(nth * sizeof(struct strbuf));
 747         for (i = 0; i < nth; i++)
 748                 strbuf_init(&cb.buf[i], 20);
 749         cb.cnt = 0;
 750         retval = 0;
 751         for_each_recent_reflog_ent("HEAD", grab_nth_branch_switch, 40960, &cb);
 752         if (cb.cnt < nth) {
 753                 cb.cnt = 0;
 754                 for_each_reflog_ent("HEAD", grab_nth_branch_switch, &cb);
 755         }
 756         if (cb.cnt < nth)
 757                 goto release_return;
 758         i = cb.cnt % nth;
 759         strbuf_reset(buf);
 760         strbuf_add(buf, cb.buf[i].buf, cb.buf[i].len);
 761         retval = brace-name+1;
 762
 763 release_return:
 764         for (i = 0; i < nth; i++)
 765                 strbuf_release(&cb.buf[i]);
 766         free(cb.buf);
 767
 768         return retval;
 769 }
 770
 771 int get_sha1_mb(const char *name, unsigned char *sha1)
 772 {
 773         struct commit *one, *two;
 774         struct commit_list *mbs;
 775         unsigned char sha1_tmp[20];
 776         const char *dots;
 777         int st;
 778
 779         dots = strstr(name, "...");
 780         if (!dots)
 781                 return get_sha1(name, sha1);
 782         if (dots == name)
 783                 st = get_sha1("HEAD", sha1_tmp);
 784         else {
 785                 struct strbuf sb;
 786                 strbuf_init(&sb, dots - name);
 787                 strbuf_add(&sb, name, dots - name);
 788                 st = get_sha1(sb.buf, sha1_tmp);
 789                 strbuf_release(&sb);
 790         }
 791         if (st)
 792                 return st;
 793         one = lookup_commit_reference_gently(sha1_tmp, 0);
 794         if (!one)
 795                 return -1;
 796
 797         if (get_sha1(dots[3] ? (dots + 3) : "HEAD", sha1_tmp))
 798                 return -1;
 799         two = lookup_commit_reference_gently(sha1_tmp, 0);
 800         if (!two)
 801                 return -1;
 802         mbs = get_merge_bases(one, two, 1);
 803         if (!mbs || mbs->next)
 804                 st = -1;
 805         else {
 806                 st = 0;
 807                 hashcpy(sha1, mbs->item->object.sha1);
 808         }
 809         free_commit_list(mbs);
 810         return st;
 811 }
 812
 813 /*
 814  * This reads short-hand syntax that not only evaluates to a commit
 815  * object name, but also can act as if the end user spelled the name
 816  * of the branch from the command line.
 817  *
 818  * - "@{-N}" finds the name of the Nth previous branch we were on, and
 819  *   places the name of the branch in the given buf and returns the
 820  *   number of characters parsed if successful.
 821  *
 822  * - "<branch>@{upstream}" finds the name of the other ref that
 823  *   <branch> is configured to merge with (missing <branch> defaults
 824  *   to the current branch), and places the name of the branch in the
 825  *   given buf and returns the number of characters parsed if
 826  *   successful.
 827  *
 828  * If the input is not of the accepted format, it returns a negative
 829  * number to signal an error.
 830  *
 831  * If the input was ok but there are not N branch switches in the
 832  * reflog, it returns 0.
 833  */
 834 int interpret_branch_name(const char *name, struct strbuf *buf)
 835 {
 836         char *cp;
 837         struct branch *upstream;
 838         int namelen = strlen(name);
 839         int len = interpret_nth_prior_checkout(name, buf);
 840         int tmp_len;
 841
 842         if (!len)
 843                 return len; /* syntax Ok, not enough switches */
 844         if (0 < len && len == namelen)
 845                 return len; /* consumed all */
 846         else if (0 < len) {
 847                 /* we have extra data, which might need further processing */
 848                 struct strbuf tmp = STRBUF_INIT;
 849                 int used = buf->len;
 850                 int ret;
 851
 852                 strbuf_add(buf, name + len, namelen - len);
 853                 ret = interpret_branch_name(buf->buf, &tmp);
 854                 /* that data was not interpreted, remove our cruft */
 855                 if (ret < 0) {
 856                         strbuf_setlen(buf, used);
 857                         return len;
 858                 }
 859                 strbuf_reset(buf);
 860                 strbuf_addbuf(buf, &tmp);
 861                 strbuf_release(&tmp);
 862                 /* tweak for size of {-N} versus expanded ref name */
 863                 return ret - used + len;
 864         }
 865
 866         cp = strchr(name, '@');
 867         if (!cp)
 868                 return -1;
 869         tmp_len = upstream_mark(cp, namelen - (cp - name));
 870         if (!tmp_len)
 871                 return -1;
 872         len = cp + tmp_len - name;
 873         cp = xstrndup(name, cp - name);
 874         upstream = branch_get(*cp ? cp : NULL);
 875         if (!upstream
 876             || !upstream->merge
 877             || !upstream->merge[0]->dst)
 878                 return error("No upstream branch found for '%s'", cp);
 879         free(cp);
 880         cp = shorten_unambiguous_ref(upstream->merge[0]->dst, 0);
 881         strbuf_reset(buf);
 882         strbuf_addstr(buf, cp);
 883         free(cp);
 884         return len;
 885 }
 886
 887 int strbuf_branchname(struct strbuf *sb, const char *name)
 888 {
 889         int len = strlen(name);
 890         if (interpret_branch_name(name, sb) == len)
 891                 return 0;
 892         strbuf_add(sb, name, len);
 893         return len;
 894 }
 895
 896 int strbuf_check_branch_ref(struct strbuf *sb, const char *name)
 897 {
 898         strbuf_branchname(sb, name);
 899         if (name[0] == '-')
 900                 return -1;
 901         strbuf_splice(sb, 0, 0, "refs/heads/", 11);
 902         return check_refname_format(sb->buf, 0);
 903 }
 904
 905 /*
 906  * This is like "get_sha1_basic()", except it allows "sha1 expressions",
 907  * notably "xyz^" for "parent of xyz"
 908  */
 909 int get_sha1(const char *name, unsigned char *sha1)
 910 {
 911         struct object_context unused;
 912         return get_sha1_with_context(name, sha1, &unused);
 913 }
 914
 915 /* Must be called only when object_name:filename doesn't exist. */
 916 static void diagnose_invalid_sha1_path(const char *prefix,
 917                                        const char *filename,
 918                                        const unsigned char *tree_sha1,
 919                                        const char *object_name)
 920 {
 921         struct stat st;
 922         unsigned char sha1[20];
 923         unsigned mode;
 924
 925         if (!prefix)
 926                 prefix = "";
 927
 928         if (!lstat(filename, &st))
 929                 die("Path '%s' exists on disk, but not in '%s'.",
 930                     filename, object_name);
 931         if (errno == ENOENT || errno == ENOTDIR) {
 932                 char *fullname = xmalloc(strlen(filename)
 933                                              + strlen(prefix) + 1);
 934                 strcpy(fullname, prefix);
 935                 strcat(fullname, filename);
 936
 937                 if (!get_tree_entry(tree_sha1, fullname,
 938                                     sha1, &mode)) {
 939                         die("Path '%s' exists, but not '%s'.\n"
 940                             "Did you mean '%s:%s' aka '%s:./%s'?",
 941                             fullname,
 942                             filename,
 943                             object_name,
 944                             fullname,
 945                             object_name,
 946                             filename);
 947                 }
 948                 die("Path '%s' does not exist in '%s'",
 949                     filename, object_name);
 950         }
 951 }
 952
 953 /* Must be called only when :stage:filename doesn't exist. */
 954 static void diagnose_invalid_index_path(int stage,
 955                                         const char *prefix,
 956                                         const char *filename)
 957 {
 958         struct stat st;
 959         struct cache_entry *ce;
 960         int pos;
 961         unsigned namelen = strlen(filename);
 962         unsigned fullnamelen;
 963         char *fullname;
 964
 965         if (!prefix)
 966                 prefix = "";
 967
 968         /* Wrong stage number? */
 969         pos = cache_name_pos(filename, namelen);
 970         if (pos < 0)
 971                 pos = -pos - 1;
 972         if (pos < active_nr) {
 973                 ce = active_cache[pos];
 974                 if (ce_namelen(ce) == namelen &&
 975                     !memcmp(ce->name, filename, namelen))
 976                         die("Path '%s' is in the index, but not at stage %d.\n"
 977                             "Did you mean ':%d:%s'?",
 978                             filename, stage,
 979                             ce_stage(ce), filename);
 980         }
 981
 982         /* Confusion between relative and absolute filenames? */
 983         fullnamelen = namelen + strlen(prefix);
 984         fullname = xmalloc(fullnamelen + 1);
 985         strcpy(fullname, prefix);
 986         strcat(fullname, filename);
 987         pos = cache_name_pos(fullname, fullnamelen);
 988         if (pos < 0)
 989                 pos = -pos - 1;
 990         if (pos < active_nr) {
 991                 ce = active_cache[pos];
 992                 if (ce_namelen(ce) == fullnamelen &&
 993                     !memcmp(ce->name, fullname, fullnamelen))
 994                         die("Path '%s' is in the index, but not '%s'.\n"
 995                             "Did you mean ':%d:%s' aka ':%d:./%s'?",
 996                             fullname, filename,
 997                             ce_stage(ce), fullname,
 998                             ce_stage(ce), filename);
 999         }
1000
1001         if (!lstat(filename, &st))
1002                 die("Path '%s' exists on disk, but not in the index.", filename);
1003         if (errno == ENOENT || errno == ENOTDIR)
1004                 die("Path '%s' does not exist (neither on disk nor in the index).",
1005                     filename);
1006
1007         free(fullname);
1008 }
1009
1010
1011 static char *resolve_relative_path(const char *rel)
1012 {
1013         if (prefixcmp(rel, "./") && prefixcmp(rel, "../"))
1014                 return NULL;
1015
1016         if (!startup_info)
1017                 die("BUG: startup_info struct is not initialized.");
1018
1019         if (!is_inside_work_tree())
1020                 die("relative path syntax can't be used outside working tree.");
1021
1022         /* die() inside prefix_path() if resolved path is outside worktree */
1023         return prefix_path(startup_info->prefix,
1024                            startup_info->prefix ? strlen(startup_info->prefix) : 0,
1025                            rel);
1026 }
1027
1028 static int get_sha1_with_context_1(const char *name, unsigned char *sha1,
1029                                    struct object_context *oc,
1030                                    int only_to_die, const char *prefix)
1031 {
1032         int ret, bracket_depth;
1033         int namelen = strlen(name);
1034         const char *cp;
1035
1036         memset(oc, 0, sizeof(*oc));
1037         oc->mode = S_IFINVALID;
1038         ret = get_sha1_1(name, namelen, sha1);
1039         if (!ret)
1040                 return ret;
1041         /* sha1:path --> object name of path in ent sha1
1042          * :path -> object name of absolute path in index
1043          * :./path -> object name of path relative to cwd in index
1044          * :[0-3]:path -> object name of path in index at stage
1045          * :/foo -> recent commit matching foo
1046          */
1047         if (name[0] == ':') {
1048                 int stage = 0;
1049                 struct cache_entry *ce;
1050                 char *new_path = NULL;
1051                 int pos;
1052                 if (!only_to_die && namelen > 2 && name[1] == '/') {
1053                         struct commit_list *list = NULL;
1054                         for_each_ref(handle_one_ref, &list);
1055                         return get_sha1_oneline(name + 2, sha1, list);
1056                 }
1057                 if (namelen < 3 ||
1058                     name[2] != ':' ||
1059                     name[1] < '0' || '3' < name[1])
1060                         cp = name + 1;
1061                 else {
1062                         stage = name[1] - '0';
1063                         cp = name + 3;
1064                 }
1065                 new_path = resolve_relative_path(cp);
1066                 if (!new_path) {
1067                         namelen = namelen - (cp - name);
1068                 } else {
1069                         cp = new_path;
1070                         namelen = strlen(cp);
1071                 }
1072
1073                 strncpy(oc->path, cp,
1074                         sizeof(oc->path));
1075                 oc->path[sizeof(oc->path)-1] = '\0';
1076
1077                 if (!active_cache)
1078                         read_cache();
1079                 pos = cache_name_pos(cp, namelen);
1080                 if (pos < 0)
1081                         pos = -pos - 1;
1082                 while (pos < active_nr) {
1083                         ce = active_cache[pos];
1084                         if (ce_namelen(ce) != namelen ||
1085                             memcmp(ce->name, cp, namelen))
1086                                 break;
1087                         if (ce_stage(ce) == stage) {
1088                                 hashcpy(sha1, ce->sha1);
1089                                 oc->mode = ce->ce_mode;
1090                                 free(new_path);
1091                                 return 0;
1092                         }
1093                         pos++;
1094                 }
1095                 if (only_to_die && name[1] && name[1] != '/')
1096                         diagnose_invalid_index_path(stage, prefix, cp);
1097                 free(new_path);
1098                 return -1;
1099         }
1100         for (cp = name, bracket_depth = 0; *cp; cp++) {
1101                 if (*cp == '{')
1102                         bracket_depth++;
1103                 else if (bracket_depth && *cp == '}')
1104                         bracket_depth--;
1105                 else if (!bracket_depth && *cp == ':')
1106                         break;
1107         }
1108         if (*cp == ':') {
1109                 unsigned char tree_sha1[20];
1110                 char *object_name = NULL;
1111                 if (only_to_die) {
1112                         object_name = xmalloc(cp-name+1);
1113                         strncpy(object_name, name, cp-name);
1114                         object_name[cp-name] = '\0';
1115                 }
1116                 if (!get_sha1_1(name, cp-name, tree_sha1)) {
1117                         const char *filename = cp+1;
1118                         char *new_filename = NULL;
1119
1120                         new_filename = resolve_relative_path(filename);
1121                         if (new_filename)
1122                                 filename = new_filename;
1123                         ret = get_tree_entry(tree_sha1, filename, sha1, &oc->mode);
1124                         if (only_to_die) {
1125                                 diagnose_invalid_sha1_path(prefix, filename,
1126                                                            tree_sha1, object_name);
1127                                 free(object_name);
1128                         }
1129                         hashcpy(oc->tree, tree_sha1);
1130                         strncpy(oc->path, filename,
1131                                 sizeof(oc->path));
1132                         oc->path[sizeof(oc->path)-1] = '\0';
1133
1134                         free(new_filename);
1135                         return ret;
1136                 } else {
1137                         if (only_to_die)
1138                                 die("Invalid object name '%s'.", object_name);
1139                 }
1140         }
1141         return ret;
1142 }
1143
1144 /*
1145  * Call this function when you know "name" given by the end user must
1146  * name an object but it doesn't; the function _may_ die with a better
1147  * diagnostic message than "no such object 'name'", e.g. "Path 'doc' does not
1148  * exist in 'HEAD'" when given "HEAD:doc", or it may return in which case
1149  * you have a chance to diagnose the error further.
1150  */
1151 void maybe_die_on_misspelt_object_name(const char *name, const char *prefix)
1152 {
1153         struct object_context oc;
1154         unsigned char sha1[20];
1155         get_sha1_with_context_1(name, sha1, &oc, 1, prefix);
1156 }
1157
1158 int get_sha1_with_context(const char *str, unsigned char *sha1, struct object_context *orc)
1159 {
1160         return get_sha1_with_context_1(str, sha1, orc, 0, NULL);
1161 }