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"
7static int find_short_object_filename(int len, const char *name, unsigned char *sha1)
9{
10 struct alternate_object_database *alt;
11 char hex[40];
12 int found = 0;
13 static struct alternate_object_database *fakeent;
14 if (!fakeent) {
16 const char *objdir = get_object_directory();
17 int objdir_len = strlen(objdir);
18 int entlen = objdir_len + 43;
19 fakeent = xmalloc(sizeof(*fakeent) + entlen);
20 memcpy(fakeent->base, objdir, objdir_len);
21 fakeent->name = fakeent->base + objdir_len + 1;
22 fakeent->name[-1] = '/';
23 }
24 fakeent->next = alt_odb_list;
25 sprintf(hex, "%.2s", name);
27 for (alt = fakeent; alt && found < 2; alt = alt->next) {
28 struct dirent *de;
29 DIR *dir;
30 sprintf(alt->name, "%.2s/", name);
31 dir = opendir(alt->base);
32 if (!dir)
33 continue;
34 while ((de = readdir(dir)) != NULL) {
35 if (strlen(de->d_name) != 38)
36 continue;
37 if (memcmp(de->d_name, name + 2, len - 2))
38 continue;
39 if (!found) {
40 memcpy(hex + 2, de->d_name, 38);
41 found++;
42 }
43 else if (memcmp(hex + 2, de->d_name, 38)) {
44 found = 2;
45 break;
46 }
47 }
48 closedir(dir);
49 }
50 if (found == 1)
51 return get_sha1_hex(hex, sha1) == 0;
52 return found;
53}
54static int match_sha(unsigned len, const unsigned char *a, const unsigned char *b)
56{
57 do {
58 if (*a != *b)
59 return 0;
60 a++;
61 b++;
62 len -= 2;
63 } while (len > 1);
64 if (len)
65 if ((*a ^ *b) & 0xf0)
66 return 0;
67 return 1;
68}
69static int find_short_packed_object(int len, const unsigned char *match, unsigned char *sha1)
71{
72 struct packed_git *p;
73 unsigned char found_sha1[20];
74 int found = 0;
75 prepare_packed_git();
77 for (p = packed_git; p && found < 2; p = p->next) {
78 unsigned num = num_packed_objects(p);
79 unsigned first = 0, last = num;
80 while (first < last) {
81 unsigned mid = (first + last) / 2;
82 unsigned char now[20];
83 int cmp;
84 nth_packed_object_sha1(p, mid, now);
86 cmp = memcmp(match, now, 20);
87 if (!cmp) {
88 first = mid;
89 break;
90 }
91 if (cmp > 0) {
92 first = mid+1;
93 continue;
94 }
95 last = mid;
96 }
97 if (first < num) {
98 unsigned char now[20], next[20];
99 nth_packed_object_sha1(p, first, now);
100 if (match_sha(len, match, now)) {
101 if (nth_packed_object_sha1(p, first+1, next) ||
102 !match_sha(len, match, next)) {
103 /* unique within this pack */
104 if (!found) {
105 memcpy(found_sha1, now, 20);
106 found++;
107 }
108 else if (memcmp(found_sha1, now, 20)) {
109 found = 2;
110 break;
111 }
112 }
113 else {
114 /* not even unique within this pack */
115 found = 2;
116 break;
117 }
118 }
119 }
120 }
121 if (found == 1)
122 memcpy(sha1, found_sha1, 20);
123 return found;
124}
125#define SHORT_NAME_NOT_FOUND (-1)
127#define SHORT_NAME_AMBIGUOUS (-2)
128static int find_unique_short_object(int len, char *canonical,
130 unsigned char *res, unsigned char *sha1)
131{
132 int has_unpacked, has_packed;
133 unsigned char unpacked_sha1[20], packed_sha1[20];
134 has_unpacked = find_short_object_filename(len, canonical, unpacked_sha1);
136 has_packed = find_short_packed_object(len, res, packed_sha1);
137 if (!has_unpacked && !has_packed)
138 return SHORT_NAME_NOT_FOUND;
139 if (1 < has_unpacked || 1 < has_packed)
140 return SHORT_NAME_AMBIGUOUS;
141 if (has_unpacked != has_packed) {
142 memcpy(sha1, (has_packed ? packed_sha1 : unpacked_sha1), 20);
143 return 0;
144 }
145 /* Both have unique ones -- do they match? */
146 if (memcmp(packed_sha1, unpacked_sha1, 20))
147 return SHORT_NAME_AMBIGUOUS;
148 memcpy(sha1, packed_sha1, 20);
149 return 0;
150}
151static int get_short_sha1(const char *name, int len, unsigned char *sha1,
153 int quietly)
154{
155 int i, status;
156 char canonical[40];
157 unsigned char res[20];
158 if (len < MINIMUM_ABBREV)
160 return -1;
161 memset(res, 0, 20);
162 memset(canonical, 'x', 40);
163 for (i = 0; i < len ;i++) {
164 unsigned char c = name[i];
165 unsigned char val;
166 if (c >= '0' && c <= '9')
167 val = c - '0';
168 else if (c >= 'a' && c <= 'f')
169 val = c - 'a' + 10;
170 else if (c >= 'A' && c <='F') {
171 val = c - 'A' + 10;
172 c -= 'A' - 'a';
173 }
174 else
175 return -1;
176 canonical[i] = c;
177 if (!(i & 1))
178 val <<= 4;
179 res[i >> 1] |= val;
180 }
181 status = find_unique_short_object(i, canonical, res, sha1);
183 if (!quietly && (status == SHORT_NAME_AMBIGUOUS))
184 return error("short SHA1 %.*s is ambiguous.", len, canonical);
185 return status;
186}
187const char *find_unique_abbrev(const unsigned char *sha1, int len)
189{
190 int status, is_null;
191 static char hex[41];
192 is_null = !memcmp(sha1, null_sha1, 20);
194 memcpy(hex, sha1_to_hex(sha1), 40);
195 if (len == 40)
196 return hex;
197 while (len < 40) {
198 unsigned char sha1_ret[20];
199 status = get_short_sha1(hex, len, sha1_ret, 1);
200 if (!status ||
201 (is_null && status != SHORT_NAME_AMBIGUOUS)) {
202 hex[len] = 0;
203 return hex;
204 }
205 if (status != SHORT_NAME_AMBIGUOUS)
206 return NULL;
207 len++;
208 }
209 return NULL;
210}
211static int ambiguous_path(const char *path, int len)
213{
214 int slash = 1;
215 int cnt;
216 for (cnt = 0; cnt < len; cnt++) {
218 switch (*path++) {
219 case '\0':
220 break;
221 case '/':
222 if (slash)
223 break;
224 slash = 1;
225 continue;
226 case '.':
227 continue;
228 default:
229 slash = 0;
230 continue;
231 }
232 break;
233 }
234 return slash;
235}
236static int get_sha1_basic(const char *str, int len, unsigned char *sha1)
238{
239 static const char *fmt[] = {
240 "%.*s",
241 "refs/%.*s",
242 "refs/tags/%.*s",
243 "refs/heads/%.*s",
244 "refs/remotes/%.*s",
245 "refs/remotes/%.*s/HEAD",
246 NULL
247 };
248 const char **p;
249 const char *warning = "warning: refname '%.*s' is ambiguous.\n";
250 char *pathname;
251 int already_found = 0;
252 unsigned char *this_result;
253 unsigned char sha1_from_ref[20];
254 if (len == 40 && !get_sha1_hex(str, sha1))
256 return 0;
257 /* Accept only unambiguous ref paths. */
259 if (ambiguous_path(str, len))
260 return -1;
261 for (p = fmt; *p; p++) {
263 this_result = already_found ? sha1_from_ref : sha1;
264 pathname = git_path(*p, len, str);
265 if (!read_ref(pathname, this_result)) {
266 if (warn_ambiguous_refs) {
267 if (already_found)
268 fprintf(stderr, warning, len, str);
269 already_found++;
270 }
271 else
272 return 0;
273 }
274 }
275 if (already_found)
276 return 0;
277 return -1;
278}
279static int get_sha1_1(const char *name, int len, unsigned char *sha1);
281static int get_parent(const char *name, int len,
283 unsigned char *result, int idx)
284{
285 unsigned char sha1[20];
286 int ret = get_sha1_1(name, len, sha1);
287 struct commit *commit;
288 struct commit_list *p;
289 if (ret)
291 return ret;
292 commit = lookup_commit_reference(sha1);
293 if (!commit)
294 return -1;
295 if (parse_commit(commit))
296 return -1;
297 if (!idx) {
298 memcpy(result, commit->object.sha1, 20);
299 return 0;
300 }
301 p = commit->parents;
302 while (p) {
303 if (!--idx) {
304 memcpy(result, p->item->object.sha1, 20);
305 return 0;
306 }
307 p = p->next;
308 }
309 return -1;
310}
311static int get_nth_ancestor(const char *name, int len,
313 unsigned char *result, int generation)
314{
315 unsigned char sha1[20];
316 int ret = get_sha1_1(name, len, sha1);
317 if (ret)
318 return ret;
319 while (generation--) {
321 struct commit *commit = lookup_commit_reference(sha1);
322 if (!commit || parse_commit(commit) || !commit->parents)
324 return -1;
325 memcpy(sha1, commit->parents->item->object.sha1, 20);
326 }
327 memcpy(result, sha1, 20);
328 return 0;
329}
330static int peel_onion(const char *name, int len, unsigned char *sha1)
332{
333 unsigned char outer[20];
334 const char *sp;
335 const char *type_string = NULL;
336 struct object *o;
337 /*
339 * "ref^{type}" dereferences ref repeatedly until you cannot
340 * dereference anymore, or you get an object of given type,
341 * whichever comes first. "ref^{}" means just dereference
342 * tags until you get a non-tag. "ref^0" is a shorthand for
343 * "ref^{commit}". "commit^{tree}" could be used to find the
344 * top-level tree of the given commit.
345 */
346 if (len < 4 || name[len-1] != '}')
347 return -1;
348 for (sp = name + len - 1; name <= sp; sp--) {
350 int ch = *sp;
351 if (ch == '{' && name < sp && sp[-1] == '^')
352 break;
353 }
354 if (sp <= name)
355 return -1;
356 sp++; /* beginning of type name, or closing brace for empty */
358 if (!strncmp(commit_type, sp, 6) && sp[6] == '}')
359 type_string = commit_type;
360 else if (!strncmp(tree_type, sp, 4) && sp[4] == '}')
361 type_string = tree_type;
362 else if (!strncmp(blob_type, sp, 4) && sp[4] == '}')
363 type_string = blob_type;
364 else if (sp[0] == '}')
365 type_string = NULL;
366 else
367 return -1;
368 if (get_sha1_1(name, sp - name - 2, outer))
370 return -1;
371 o = parse_object(outer);
373 if (!o)
374 return -1;
375 if (!type_string) {
376 o = deref_tag(o, name, sp - name - 2);
377 if (!o || (!o->parsed && !parse_object(o->sha1)))
378 return -1;
379 memcpy(sha1, o->sha1, 20);
380 }
381 else {
382 /* At this point, the syntax look correct, so
383 * if we do not get the needed object, we should
384 * barf.
385 */
386 while (1) {
388 if (!o || (!o->parsed && !parse_object(o->sha1)))
389 return -1;
390 if (o->type == type_string) {
391 memcpy(sha1, o->sha1, 20);
392 return 0;
393 }
394 if (o->type == tag_type)
395 o = ((struct tag*) o)->tagged;
396 else if (o->type == commit_type)
397 o = &(((struct commit *) o)->tree->object);
398 else
399 return error("%.*s: expected %s type, but the object dereferences to %s type",
400 len, name, type_string,
401 o->type);
402 if (!o->parsed)
403 parse_object(o->sha1);
404 }
405 }
406 return 0;
407}
408static int get_sha1_1(const char *name, int len, unsigned char *sha1)
410{
411 int ret, has_suffix;
412 const char *cp;
413 /* "name~3" is "name^^^",
415 * "name~" and "name~0" are name -- not "name^0"!
416 * "name^" is not "name^0"; it is "name^1".
417 */
418 has_suffix = 0;
419 for (cp = name + len - 1; name <= cp; cp--) {
420 int ch = *cp;
421 if ('0' <= ch && ch <= '9')
422 continue;
423 if (ch == '~' || ch == '^')
424 has_suffix = ch;
425 break;
426 }
427 if (has_suffix) {
429 int num = 0;
430 int len1 = cp - name;
431 cp++;
432 while (cp < name + len)
433 num = num * 10 + *cp++ - '0';
434 if (has_suffix == '^') {
435 if (!num && len1 == len - 1)
436 num = 1;
437 return get_parent(name, len1, sha1, num);
438 }
439 /* else if (has_suffix == '~') -- goes without saying */
440 return get_nth_ancestor(name, len1, sha1, num);
441 }
442 ret = peel_onion(name, len, sha1);
444 if (!ret)
445 return 0;
446 ret = get_sha1_basic(name, len, sha1);
448 if (!ret)
449 return 0;
450 return get_short_sha1(name, len, sha1, 0);
451}
452/*
454 * This is like "get_sha1_basic()", except it allows "sha1 expressions",
455 * notably "xyz^" for "parent of xyz"
456 */
457int get_sha1(const char *name, unsigned char *sha1)
458{
459 int ret;
460 unsigned unused;
461 prepare_alt_odb();
463 ret = get_sha1_1(name, strlen(name), sha1);
464 if (ret < 0) {
465 const char *cp = strchr(name, ':');
466 if (cp) {
467 unsigned char tree_sha1[20];
468 if (!get_sha1_1(name, cp-name, tree_sha1))
469 return get_tree_entry(tree_sha1, cp+1, sha1,
470 &unused);
471 }
472 }
473 return ret;
474}