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