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"
8static int find_short_object_filename(int len, const char *name, unsigned char *sha1)
10{
11 struct alternate_object_database *alt;
12 char hex[40];
13 int found = 0;
14 static struct alternate_object_database *fakeent;
15 static const char *last_objdir;
16 const char *objdir = get_object_directory();
17 if (!last_objdir || strcmp(last_objdir, objdir)) {
19 int objdir_len = strlen(objdir);
20 int entlen = objdir_len + 43;
21 if (fakeent)
22 free(fakeent);
23 fakeent = xmalloc(sizeof(*fakeent) + entlen);
24 memcpy(fakeent->base, objdir, objdir_len);
25 fakeent->name = fakeent->base + objdir_len + 1;
26 fakeent->name[-1] = '/';
27 if (last_objdir)
28 free((char *) last_objdir);
29 last_objdir = strdup(objdir);
30 }
31 fakeent->next = alt_odb_list;
32 sprintf(hex, "%.2s", name);
34 for (alt = fakeent; alt && found < 2; alt = alt->next) {
35 struct dirent *de;
36 DIR *dir;
37 sprintf(alt->name, "%.2s/", name);
38 dir = opendir(alt->base);
39 if (!dir)
40 continue;
41 while ((de = readdir(dir)) != NULL) {
42 if (strlen(de->d_name) != 38)
43 continue;
44 if (memcmp(de->d_name, name + 2, len - 2))
45 continue;
46 if (!found) {
47 memcpy(hex + 2, de->d_name, 38);
48 found++;
49 }
50 else if (memcmp(hex + 2, de->d_name, 38)) {
51 found = 2;
52 break;
53 }
54 }
55 closedir(dir);
56 }
57 if (found == 1)
58 return get_sha1_hex(hex, sha1) == 0;
59 return found;
60}
61static int match_sha(unsigned len, const unsigned char *a, const unsigned char *b)
63{
64 do {
65 if (*a != *b)
66 return 0;
67 a++;
68 b++;
69 len -= 2;
70 } while (len > 1);
71 if (len)
72 if ((*a ^ *b) & 0xf0)
73 return 0;
74 return 1;
75}
76static int find_short_packed_object(int len, const unsigned char *match, unsigned char *sha1)
78{
79 struct packed_git *p;
80 unsigned char found_sha1[20];
81 int found = 0;
82 prepare_packed_git();
84 for (p = packed_git; p && found < 2; p = p->next) {
85 unsigned num = num_packed_objects(p);
86 unsigned first = 0, last = num;
87 while (first < last) {
88 unsigned mid = (first + last) / 2;
89 unsigned char now[20];
90 int cmp;
91 nth_packed_object_sha1(p, mid, now);
93 cmp = memcmp(match, now, 20);
94 if (!cmp) {
95 first = mid;
96 break;
97 }
98 if (cmp > 0) {
99 first = mid+1;
100 continue;
101 }
102 last = mid;
103 }
104 if (first < num) {
105 unsigned char now[20], next[20];
106 nth_packed_object_sha1(p, first, now);
107 if (match_sha(len, match, now)) {
108 if (nth_packed_object_sha1(p, first+1, next) ||
109 !match_sha(len, match, next)) {
110 /* unique within this pack */
111 if (!found) {
112 memcpy(found_sha1, now, 20);
113 found++;
114 }
115 else if (memcmp(found_sha1, now, 20)) {
116 found = 2;
117 break;
118 }
119 }
120 else {
121 /* not even unique within this pack */
122 found = 2;
123 break;
124 }
125 }
126 }
127 }
128 if (found == 1)
129 memcpy(sha1, found_sha1, 20);
130 return found;
131}
132#define SHORT_NAME_NOT_FOUND (-1)
134#define SHORT_NAME_AMBIGUOUS (-2)
135static int find_unique_short_object(int len, char *canonical,
137 unsigned char *res, unsigned char *sha1)
138{
139 int has_unpacked, has_packed;
140 unsigned char unpacked_sha1[20], packed_sha1[20];
141 has_unpacked = find_short_object_filename(len, canonical, unpacked_sha1);
143 has_packed = find_short_packed_object(len, res, packed_sha1);
144 if (!has_unpacked && !has_packed)
145 return SHORT_NAME_NOT_FOUND;
146 if (1 < has_unpacked || 1 < has_packed)
147 return SHORT_NAME_AMBIGUOUS;
148 if (has_unpacked != has_packed) {
149 memcpy(sha1, (has_packed ? packed_sha1 : unpacked_sha1), 20);
150 return 0;
151 }
152 /* Both have unique ones -- do they match? */
153 if (memcmp(packed_sha1, unpacked_sha1, 20))
154 return SHORT_NAME_AMBIGUOUS;
155 memcpy(sha1, packed_sha1, 20);
156 return 0;
157}
158static int get_short_sha1(const char *name, int len, unsigned char *sha1,
160 int quietly)
161{
162 int i, status;
163 char canonical[40];
164 unsigned char res[20];
165 if (len < MINIMUM_ABBREV)
167 return -1;
168 memset(res, 0, 20);
169 memset(canonical, 'x', 40);
170 for (i = 0; i < len ;i++) {
171 unsigned char c = name[i];
172 unsigned char val;
173 if (c >= '0' && c <= '9')
174 val = c - '0';
175 else if (c >= 'a' && c <= 'f')
176 val = c - 'a' + 10;
177 else if (c >= 'A' && c <='F') {
178 val = c - 'A' + 10;
179 c -= 'A' - 'a';
180 }
181 else
182 return -1;
183 canonical[i] = c;
184 if (!(i & 1))
185 val <<= 4;
186 res[i >> 1] |= val;
187 }
188 status = find_unique_short_object(i, canonical, res, sha1);
190 if (!quietly && (status == SHORT_NAME_AMBIGUOUS))
191 return error("short SHA1 %.*s is ambiguous.", len, canonical);
192 return status;
193}
194const char *find_unique_abbrev(const unsigned char *sha1, int len)
196{
197 int status, is_null;
198 static char hex[41];
199 is_null = !memcmp(sha1, null_sha1, 20);
201 memcpy(hex, sha1_to_hex(sha1), 40);
202 if (len == 40)
203 return hex;
204 while (len < 40) {
205 unsigned char sha1_ret[20];
206 status = get_short_sha1(hex, len, sha1_ret, 1);
207 if (!status ||
208 (is_null && status != SHORT_NAME_AMBIGUOUS)) {
209 hex[len] = 0;
210 return hex;
211 }
212 if (status != SHORT_NAME_AMBIGUOUS)
213 return NULL;
214 len++;
215 }
216 return NULL;
217}
218static int ambiguous_path(const char *path, int len)
220{
221 int slash = 1;
222 int cnt;
223 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}
243static int get_sha1_basic(const char *str, int len, unsigned char *sha1)
245{
246 static const char *fmt[] = {
247 "%.*s",
248 "refs/%.*s",
249 "refs/tags/%.*s",
250 "refs/heads/%.*s",
251 "refs/remotes/%.*s",
252 "refs/remotes/%.*s/HEAD",
253 NULL
254 };
255 static const char *warning = "warning: refname '%.*s' is ambiguous.\n";
256 const char **p, *pathname;
257 char *real_path = NULL;
258 int refs_found = 0, am;
259 unsigned long at_time = (unsigned long)-1;
260 unsigned char *this_result;
261 unsigned char sha1_from_ref[20];
262 if (len == 40 && !get_sha1_hex(str, sha1))
264 return 0;
265 /* At a given period of time? "@{2 hours ago}" */
267 for (am = 1; am < len - 1; am++) {
268 if (str[am] == '@' && str[am+1] == '{' && str[len-1] == '}') {
269 int date_len = len - am - 3;
270 char *date_spec = xmalloc(date_len + 1);
271 strlcpy(date_spec, str + am + 2, date_len + 1);
272 at_time = approxidate(date_spec);
273 free(date_spec);
274 len = am;
275 break;
276 }
277 }
278 /* Accept only unambiguous ref paths. */
280 if (ambiguous_path(str, len))
281 return -1;
282 for (p = fmt; *p; p++) {
284 this_result = refs_found ? sha1_from_ref : sha1;
285 pathname = resolve_ref(git_path(*p, len, str), this_result, 1);
286 if (pathname) {
287 if (!refs_found++)
288 real_path = strdup(pathname);
289 if (!warn_ambiguous_refs)
290 break;
291 }
292 }
293 if (!refs_found)
295 return -1;
296 if (warn_ambiguous_refs && refs_found > 1)
298 fprintf(stderr, warning, len, str);
299 if (at_time != (unsigned long)-1) {
301 read_ref_at(
302 real_path + strlen(git_path(".")) - 1,
303 at_time,
304 sha1);
305 }
306 free(real_path);
308 return 0;
309}
310static int get_sha1_1(const char *name, int len, unsigned char *sha1);
312static int get_parent(const char *name, int len,
314 unsigned char *result, int idx)
315{
316 unsigned char sha1[20];
317 int ret = get_sha1_1(name, len, sha1);
318 struct commit *commit;
319 struct commit_list *p;
320 if (ret)
322 return ret;
323 commit = lookup_commit_reference(sha1);
324 if (!commit)
325 return -1;
326 if (parse_commit(commit))
327 return -1;
328 if (!idx) {
329 memcpy(result, commit->object.sha1, 20);
330 return 0;
331 }
332 p = commit->parents;
333 while (p) {
334 if (!--idx) {
335 memcpy(result, p->item->object.sha1, 20);
336 return 0;
337 }
338 p = p->next;
339 }
340 return -1;
341}
342static int get_nth_ancestor(const char *name, int len,
344 unsigned char *result, int generation)
345{
346 unsigned char sha1[20];
347 int ret = get_sha1_1(name, len, sha1);
348 if (ret)
349 return ret;
350 while (generation--) {
352 struct commit *commit = lookup_commit_reference(sha1);
353 if (!commit || parse_commit(commit) || !commit->parents)
355 return -1;
356 memcpy(sha1, commit->parents->item->object.sha1, 20);
357 }
358 memcpy(result, sha1, 20);
359 return 0;
360}
361static int peel_onion(const char *name, int len, unsigned char *sha1)
363{
364 unsigned char outer[20];
365 const char *sp;
366 unsigned int expected_type = 0;
367 struct object *o;
368 /*
370 * "ref^{type}" dereferences ref repeatedly until you cannot
371 * dereference anymore, or you get an object of given type,
372 * whichever comes first. "ref^{}" means just dereference
373 * tags until you get a non-tag. "ref^0" is a shorthand for
374 * "ref^{commit}". "commit^{tree}" could be used to find the
375 * top-level tree of the given commit.
376 */
377 if (len < 4 || name[len-1] != '}')
378 return -1;
379 for (sp = name + len - 1; name <= sp; sp--) {
381 int ch = *sp;
382 if (ch == '{' && name < sp && sp[-1] == '^')
383 break;
384 }
385 if (sp <= name)
386 return -1;
387 sp++; /* beginning of type name, or closing brace for empty */
389 if (!strncmp(commit_type, sp, 6) && sp[6] == '}')
390 expected_type = TYPE_COMMIT;
391 else if (!strncmp(tree_type, sp, 4) && sp[4] == '}')
392 expected_type = TYPE_TREE;
393 else if (!strncmp(blob_type, sp, 4) && sp[4] == '}')
394 expected_type = TYPE_BLOB;
395 else if (sp[0] == '}')
396 expected_type = TYPE_NONE;
397 else
398 return -1;
399 if (get_sha1_1(name, sp - name - 2, outer))
401 return -1;
402 o = parse_object(outer);
404 if (!o)
405 return -1;
406 if (!expected_type) {
407 o = deref_tag(o, name, sp - name - 2);
408 if (!o || (!o->parsed && !parse_object(o->sha1)))
409 return -1;
410 memcpy(sha1, o->sha1, 20);
411 }
412 else {
413 /* At this point, the syntax look correct, so
414 * if we do not get the needed object, we should
415 * barf.
416 */
417 while (1) {
419 if (!o || (!o->parsed && !parse_object(o->sha1)))
420 return -1;
421 if (o->type == expected_type) {
422 memcpy(sha1, o->sha1, 20);
423 return 0;
424 }
425 if (o->type == TYPE_TAG)
426 o = ((struct tag*) o)->tagged;
427 else if (o->type == TYPE_COMMIT)
428 o = &(((struct commit *) o)->tree->object);
429 else
430 return error("%.*s: expected %s type, but the object dereferences to %s type",
431 len, name, typename(expected_type),
432 typename(o->type));
433 if (!o->parsed)
434 parse_object(o->sha1);
435 }
436 }
437 return 0;
438}
439static int get_sha1_1(const char *name, int len, unsigned char *sha1)
441{
442 int ret, has_suffix;
443 const char *cp;
444 /* "name~3" is "name^^^",
446 * "name~" and "name~0" are name -- not "name^0"!
447 * "name^" is not "name^0"; it is "name^1".
448 */
449 has_suffix = 0;
450 for (cp = name + len - 1; name <= cp; cp--) {
451 int ch = *cp;
452 if ('0' <= ch && ch <= '9')
453 continue;
454 if (ch == '~' || ch == '^')
455 has_suffix = ch;
456 break;
457 }
458 if (has_suffix) {
460 int num = 0;
461 int len1 = cp - name;
462 cp++;
463 while (cp < name + len)
464 num = num * 10 + *cp++ - '0';
465 if (has_suffix == '^') {
466 if (!num && len1 == len - 1)
467 num = 1;
468 return get_parent(name, len1, sha1, num);
469 }
470 /* else if (has_suffix == '~') -- goes without saying */
471 return get_nth_ancestor(name, len1, sha1, num);
472 }
473 ret = peel_onion(name, len, sha1);
475 if (!ret)
476 return 0;
477 ret = get_sha1_basic(name, len, sha1);
479 if (!ret)
480 return 0;
481 return get_short_sha1(name, len, sha1, 0);
482}
483/*
485 * This is like "get_sha1_basic()", except it allows "sha1 expressions",
486 * notably "xyz^" for "parent of xyz"
487 */
488int get_sha1(const char *name, unsigned char *sha1)
489{
490 int ret, bracket_depth;
491 unsigned unused;
492 int namelen = strlen(name);
493 const char *cp;
494 prepare_alt_odb();
496 ret = get_sha1_1(name, namelen, sha1);
497 if (!ret)
498 return ret;
499 /* sha1:path --> object name of path in ent sha1
500 * :path -> object name of path in index
501 * :[0-3]:path -> object name of path in index at stage
502 */
503 if (name[0] == ':') {
504 int stage = 0;
505 struct cache_entry *ce;
506 int pos;
507 if (namelen < 3 ||
508 name[2] != ':' ||
509 name[1] < '0' || '3' < name[1])
510 cp = name + 1;
511 else {
512 stage = name[1] - '0';
513 cp = name + 3;
514 }
515 namelen = namelen - (cp - name);
516 if (!active_cache)
517 read_cache();
518 if (active_nr < 0)
519 return -1;
520 pos = cache_name_pos(cp, namelen);
521 if (pos < 0)
522 pos = -pos - 1;
523 while (pos < active_nr) {
524 ce = active_cache[pos];
525 if (ce_namelen(ce) != namelen ||
526 memcmp(ce->name, cp, namelen))
527 break;
528 if (ce_stage(ce) == stage) {
529 memcpy(sha1, ce->sha1, 20);
530 return 0;
531 }
532 pos++;
533 }
534 return -1;
535 }
536 for (cp = name, bracket_depth = 0; *cp; cp++) {
537 if (*cp == '{')
538 bracket_depth++;
539 else if (bracket_depth && *cp == '}')
540 bracket_depth--;
541 else if (!bracket_depth && *cp == ':')
542 break;
543 }
544 if (*cp == ':') {
545 unsigned char tree_sha1[20];
546 if (!get_sha1_1(name, cp-name, tree_sha1))
547 return get_tree_entry(tree_sha1, cp+1, sha1,
548 &unused);
549 }
550 return ret;
551}