Diff: -l<num> to limit rename/copy detection.
[git] / sha1_name.c
1 #include "cache.h"
2 #include "commit.h"
3
4 static int find_short_object_filename(int len, const char *name, unsigned char *sha1)
5 {
6         static char dirname[PATH_MAX];
7         char hex[40];
8         DIR *dir;
9         int found;
10
11         snprintf(dirname, sizeof(dirname), "%s/%.2s", get_object_directory(), name);
12         dir = opendir(dirname);
13         sprintf(hex, "%.2s", name);
14         found = 0;
15         if (dir) {
16                 struct dirent *de;
17                 while ((de = readdir(dir)) != NULL) {
18                         if (strlen(de->d_name) != 38)
19                                 continue;
20                         if (memcmp(de->d_name, name + 2, len-2))
21                                 continue;
22                         memcpy(hex + 2, de->d_name, 38);
23                         if (++found > 1)
24                                 break;
25                 }
26                 closedir(dir);
27         }
28         if (found == 1)
29                 return get_sha1_hex(hex, sha1) == 0;
30         return 0;
31 }
32
33 static int match_sha(unsigned len, const unsigned char *a, const unsigned char *b)
34 {
35         do {
36                 if (*a != *b)
37                         return 0;
38                 a++;
39                 b++;
40                 len -= 2;
41         } while (len > 1);
42         if (len)
43                 if ((*a ^ *b) & 0xf0)
44                         return 0;
45         return 1;
46 }
47
48 static int find_short_packed_object(int len, const unsigned char *match, unsigned char *sha1)
49 {
50         struct packed_git *p;
51
52         prepare_packed_git();
53         for (p = packed_git; p; p = p->next) {
54                 unsigned num = num_packed_objects(p);
55                 unsigned first = 0, last = num;
56                 while (first < last) {
57                         unsigned mid = (first + last) / 2;
58                         unsigned char now[20];
59                         int cmp;
60
61                         nth_packed_object_sha1(p, mid, now);
62                         cmp = memcmp(match, now, 20);
63                         if (!cmp) {
64                                 first = mid;
65                                 break;
66                         }
67                         if (cmp > 0) {
68                                 first = mid+1;
69                                 continue;
70                         }
71                         last = mid;
72                 }
73                 if (first < num) {
74                         unsigned char now[20], next[20];
75                         nth_packed_object_sha1(p, first, now);
76                         if (match_sha(len, match, now)) {
77                                 if (nth_packed_object_sha1(p, first+1, next) || !match_sha(len, match, next)) {
78                                         memcpy(sha1, now, 20);
79                                         return 1;
80                                 }
81                         }
82                 }
83         }
84         return 0;
85 }
86
87 static int get_short_sha1(const char *name, int len, unsigned char *sha1)
88 {
89         int i;
90         char canonical[40];
91         unsigned char res[20];
92
93         if (len < 4)
94                 return -1;
95         memset(res, 0, 20);
96         memset(canonical, 'x', 40);
97         for (i = 0; i < len ;i++) {
98                 unsigned char c = name[i];
99                 unsigned char val;
100                 if (c >= '0' && c <= '9')
101                         val = c - '0';
102                 else if (c >= 'a' && c <= 'f')
103                         val = c - 'a' + 10;
104                 else if (c >= 'A' && c <='F') {
105                         val = c - 'A' + 10;
106                         c -= 'A' - 'a';
107                 }
108                 else
109                         return -1;
110                 canonical[i] = c;
111                 if (!(i & 1))
112                         val <<= 4;
113                 res[i >> 1] |= val;
114         }
115         if (find_short_object_filename(i, canonical, sha1))
116                 return 0;
117         if (find_short_packed_object(i, res, sha1))
118                 return 0;
119         return -1;
120 }
121
122 static int get_sha1_file(const char *path, unsigned char *result)
123 {
124         char buffer[60];
125         int fd = open(path, O_RDONLY);
126         int len;
127
128         if (fd < 0)
129                 return -1;
130         len = read(fd, buffer, sizeof(buffer));
131         close(fd);
132         if (len < 40)
133                 return -1;
134         return get_sha1_hex(buffer, result);
135 }
136
137 static int get_sha1_basic(const char *str, int len, unsigned char *sha1)
138 {
139         static const char *prefix[] = {
140                 "",
141                 "refs",
142                 "refs/tags",
143                 "refs/heads",
144                 NULL
145         };
146         const char **p;
147
148         if (len == 40 && !get_sha1_hex(str, sha1))
149                 return 0;
150
151         for (p = prefix; *p; p++) {
152                 char *pathname = git_path("%s/%.*s", *p, len, str);
153                 if (!get_sha1_file(pathname, sha1))
154                         return 0;
155         }
156
157         return -1;
158 }
159
160 static int get_sha1_1(const char *name, int len, unsigned char *sha1);
161
162 static int get_parent(const char *name, int len,
163                       unsigned char *result, int idx)
164 {
165         unsigned char sha1[20];
166         int ret = get_sha1_1(name, len, sha1);
167         struct commit *commit;
168         struct commit_list *p;
169
170         if (ret)
171                 return ret;
172         commit = lookup_commit_reference(sha1);
173         if (!commit)
174                 return -1;
175         if (parse_commit(commit))
176                 return -1;
177         if (!idx) {
178                 memcpy(result, commit->object.sha1, 20);
179                 return 0;
180         }
181         p = commit->parents;
182         while (p) {
183                 if (!--idx) {
184                         memcpy(result, p->item->object.sha1, 20);
185                         return 0;
186                 }
187                 p = p->next;
188         }
189         return -1;
190 }
191
192 static int get_nth_ancestor(const char *name, int len,
193                             unsigned char *result, int generation)
194 {
195         unsigned char sha1[20];
196         int ret = get_sha1_1(name, len, sha1);
197         if (ret)
198                 return ret;
199
200         while (generation--) {
201                 struct commit *commit = lookup_commit_reference(sha1);
202
203                 if (!commit || parse_commit(commit) || !commit->parents)
204                         return -1;
205                 memcpy(sha1, commit->parents->item->object.sha1, 20);
206         }
207         memcpy(result, sha1, 20);
208         return 0;
209 }
210
211 static int get_sha1_1(const char *name, int len, unsigned char *sha1)
212 {
213         int parent, ret;
214         const char *cp;
215
216         /* foo^[0-9] or foo^ (== foo^1); we do not do more than 9 parents. */
217         if (len > 2 && name[len-2] == '^' &&
218             name[len-1] >= '0' && name[len-1] <= '9') {
219                 parent = name[len-1] - '0';
220                 len -= 2;
221         }
222         else if (len > 1 && name[len-1] == '^') {
223                 parent = 1;
224                 len--;
225         } else
226                 parent = -1;
227
228         if (parent >= 0)
229                 return get_parent(name, len, sha1, parent);
230
231         /* "name~3" is "name^^^",
232          * "name~12" is "name^^^^^^^^^^^^", and
233          * "name~" and "name~0" are name -- not "name^0"!
234          */
235         parent = 0;
236         for (cp = name + len - 1; name <= cp; cp--) {
237                 int ch = *cp;
238                 if ('0' <= ch && ch <= '9')
239                         continue;
240                 if (ch != '~')
241                         parent = -1;
242                 break;
243         }
244         if (!parent && *cp == '~') {
245                 int len1 = cp - name;
246                 cp++;
247                 while (cp < name + len)
248                         parent = parent * 10 + *cp++ - '0';
249                 return get_nth_ancestor(name, len1, sha1, parent);
250         }
251
252         ret = get_sha1_basic(name, len, sha1);
253         if (!ret)
254                 return 0;
255         return get_short_sha1(name, len, sha1);
256 }
257
258 /*
259  * This is like "get_sha1_basic()", except it allows "sha1 expressions",
260  * notably "xyz^" for "parent of xyz"
261  */
262 int get_sha1(const char *name, unsigned char *sha1)
263 {
264         return get_sha1_1(name, strlen(name), sha1);
265 }