Got Mirror

Blob

Date:: Wed Nov 29 16:11:11 2017 UTC
Message:: add and test basic blob diffing functionality
Actions:: History | Blame | Raw File
1 /*
2  * Copyright (c) 2017 Stefan Sperling <stsp@openbsd.org>
3  *
4  * Permission to use, copy, modify, and distribute this software for any
5  * purpose with or without fee is hereby granted, provided that the above
6  * copyright notice and this permission notice appear in all copies.
7  *
8  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
9  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
10  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
11  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
12  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
13  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
14  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
15  */
16 
17 #include <sys/stat.h>
18 #include <sys/queue.h>
19 
20 #include <stdio.h>
21 #include <stdlib.h>
22 #include <string.h>
23 #include <sha1.h>
24 #include <zlib.h>
25 #include <ctype.h>
26 #include <limits.h>
27 
28 #include "got_error.h"
29 #include "got_object.h"
30 #include "got_repository.h"
31 #include "got_sha1.h"
32 
33 #ifndef MIN
34 #define	MIN(_a,_b) ((_a) < (_b) ? (_a) : (_b))
35 #endif
36 
37 #ifndef nitems
38 #define nitems(_a) (sizeof(_a) / sizeof((_a)[0]))
39 #endif
40 
41 #define GOT_OBJ_TAG_COMMIT	"commit"
42 #define GOT_OBJ_TAG_TREE	"tree"
43 #define GOT_OBJ_TAG_BLOB	"blob"
44 
45 #define GOT_COMMIT_TAG_TREE		"tree "
46 #define GOT_COMMIT_TAG_PARENT		"parent "
47 #define GOT_COMMIT_TAG_AUTHOR		"author "
48 #define GOT_COMMIT_TAG_COMMITTER	"committer "
49 
50 const char *
51 got_object_id_str(struct got_object_id *id, char *buf, size_t size)
52 {
53 	char *p = buf;
54 	char hex[3];
55 	int i;
56 
57 	if (size < SHA1_DIGEST_STRING_LENGTH)
58 		return NULL;
59 
60 	for (i = 0; i < SHA1_DIGEST_LENGTH; i++) {
61 		snprintf(hex, sizeof(hex), "%.2x", id->sha1[i]);
62 		p[0] = hex[0];
63 		p[1] = hex[1];
64 		p += 2;
65 	}
66 	p[0] = '\0';
67 
68 	return buf;
69 }
70 
71 static void
72 inflate_end(struct got_zstream_buf *zb)
73 {
74 	free(zb->inbuf);
75 	free(zb->outbuf);
76 	inflateEnd(&zb->z);
77 }
78 
79 static const struct got_error *
80 inflate_init(struct got_zstream_buf *zb, size_t bufsize)
81 {
82 	const struct got_error *err = NULL;
83 
84 	memset(zb, 0, sizeof(*zb));
85 
86 	zb->z.zalloc = Z_NULL;
87 	zb->z.zfree = Z_NULL;
88 	if (inflateInit(&zb->z) != Z_OK) {
89 		err = got_error(GOT_ERR_IO);
90 		goto done;
91 	}
92 
93 	zb->inlen = zb->outlen = bufsize;
94 
95 	zb->inbuf = calloc(1, zb->inlen);
96 	if (zb->inbuf == NULL) {
97 		err = got_error(GOT_ERR_NO_MEM);
98 		goto done;
99 	}
100 
101 	zb->outbuf = calloc(1, zb->outlen);
102 	if (zb->outbuf == NULL) {
103 		err = got_error(GOT_ERR_NO_MEM);
104 		goto done;
105 	}
106 
107 done:
108 	if (err)
109 		inflate_end(zb);
110 	return err;
111 }
112 
113 static const struct got_error *
114 inflate_read(struct got_zstream_buf *zb, FILE *f, size_t *outlenp)
115 {
116 	size_t last_total_out = zb->z.total_out;
117 	z_stream *z = &zb->z;
118 	int n, ret;
119 
120 	z->next_out = zb->outbuf;
121 	z->avail_out = zb->outlen;
122 
123 	if (z->avail_in == 0 && (zb->flags & GOT_ZSTREAM_F_HAVE_MORE) == 0) {
124 		int i;
125 		n = fread(zb->inbuf, 1, zb->inlen, f);
126 		if (n == 0) {
127 			if (ferror(f))
128 				return got_error(GOT_ERR_IO);
129 			*outlenp = 0;
130 			return NULL;
131 		}
132 		z->next_in = zb->inbuf;
133 		z->avail_in = n;
134 	}
135 
136 	ret = inflate(z, Z_SYNC_FLUSH);
137 	if (ret == Z_OK) {
138 		if (z->avail_out == 0)
139 			zb->flags |= GOT_ZSTREAM_F_HAVE_MORE;
140 		else
141 			zb->flags &= ~GOT_ZSTREAM_F_HAVE_MORE;
142 	} else if (ret != Z_STREAM_END)
143 		return got_error(GOT_ERR_DECOMPRESSION);
144 
145 	*outlenp = z->total_out - last_total_out;
146 	return NULL;
147 }
148 
149 static const struct got_error *
150 parse_object_header(struct got_object **obj, char *buf, size_t len)
151 {
152 	const char *obj_tags[] = {
153 		GOT_OBJ_TAG_COMMIT,
154 		GOT_OBJ_TAG_TREE,
155 		GOT_OBJ_TAG_BLOB
156 	};
157 	const int obj_types[] = {
158 		GOT_OBJ_TYPE_COMMIT,
159 		GOT_OBJ_TYPE_TREE,
160 		GOT_OBJ_TYPE_BLOB,
161 	};
162 	int type = 0;
163 	size_t size = 0, hdrlen = 0;
164 	int i;
165 	char *p = strchr(buf, '\0');
166 
167 	if (p == NULL)
168 		return got_error(GOT_ERR_BAD_OBJ_HDR);
169 
170 	hdrlen = strlen(buf) + 1 /* '\0' */;
171 
172 	for (i = 0; i < nitems(obj_tags); i++) {
173 		const char *tag = obj_tags[i];
174 		size_t tlen = strlen(tag);
175 		const char *errstr;
176 
177 		if (strncmp(buf, tag, tlen) != 0)
178 			continue;
179 
180 		type = obj_types[i];
181 		if (len <= tlen)
182 			return got_error(GOT_ERR_BAD_OBJ_HDR);
183 		size = strtonum(buf + tlen, 0, LONG_MAX, &errstr);
184 		if (errstr != NULL)
185 			return got_error(GOT_ERR_BAD_OBJ_HDR);
186 		break;
187 	}
188 
189 	if (type == 0)
190 		return got_error(GOT_ERR_BAD_OBJ_HDR);
191 
192 	*obj = calloc(1, sizeof(**obj));
193 	(*obj)->type = type;
194 	(*obj)->hdrlen = hdrlen;
195 	(*obj)->size = size;
196 	return NULL;
197 }
198 
199 static const struct got_error *
200 read_object_header(struct got_object **obj, struct got_repository *repo,
201     const char *path)
202 {
203 	const struct got_error *err;
204 	FILE *f;
205 	struct got_zstream_buf zb;
206 	size_t outlen;
207 	int i, ret;
208 
209 	f = fopen(path, "rb");
210 	if (f == NULL)
211 		return got_error(GOT_ERR_BAD_PATH);
212 
213 	err = inflate_init(&zb, 64);
214 	if (err) {
215 		fclose(f);
216 		return err;
217 	}
218 
219 	err = inflate_read(&zb, f, &outlen);
220 	if (err)
221 		goto done;
222 
223 	err = parse_object_header(obj, zb.outbuf, outlen);
224 done:
225 	inflate_end(&zb);
226 	fclose(f);
227 	return err;
228 }
229 
230 static const struct got_error *
231 object_path(char **path, struct got_object_id *id,
232     struct got_repository *repo)
233 {
234 	const struct got_error *err = NULL;
235 	char hex[SHA1_DIGEST_STRING_LENGTH];
236 	char *path_objects = got_repo_get_path_objects(repo);
237 
238 	if (path_objects == NULL)
239 		return got_error(GOT_ERR_NO_MEM);
240 
241 	got_object_id_str(id, hex, sizeof(hex));
242 
243 	if (asprintf(path, "%s/%.2x/%s", path_objects,
244 	    id->sha1[0], hex + 2) == -1)
245 		err = got_error(GOT_ERR_NO_MEM);
246 
247 	free(path_objects);
248 	return err;
249 }
250 
251 const struct got_error *
252 got_object_open(struct got_object **obj, struct got_repository *repo,
253     struct got_object_id *id)
254 {
255 	const struct got_error *err = NULL;
256 	char *path = NULL;
257 
258 	err = object_path(&path, id, repo);
259 	if (err)
260 		return err;
261 
262 	err = read_object_header(obj, repo, path);
263 	if (err == NULL)
264 		memcpy((*obj)->id.sha1, id->sha1, SHA1_DIGEST_LENGTH);
265 done:
266 	free(path);
267 	return err;
268 }
269 
270 void
271 got_object_close(struct got_object *obj)
272 {
273 	free(obj);
274 }
275 
276 static int
277 commit_object_valid(struct got_commit_object *commit)
278 {
279 	int i;
280 	int n;
281 
282 	if (commit == NULL)
283 		return 0;
284 
285 	n = 0;
286 	for (i = 0; i < SHA1_DIGEST_LENGTH; i++) {
287 		if (commit->tree_id.sha1[i] == 0)
288 			n++;
289 	}
290 	if (n == SHA1_DIGEST_LENGTH)
291 		return 0;
292 
293 	return 1;
294 }
295 
296 static const struct got_error *
297 parse_commit_object(struct got_commit_object **commit, char *buf, size_t len)
298 {
299 	const struct got_error *err = NULL;
300 	char *s = buf;
301 	size_t tlen;
302 	ssize_t remain = (ssize_t)len;
303  
304 	*commit = calloc(1, sizeof(**commit));
305 	if (*commit == NULL)
306 		return got_error(GOT_ERR_NO_MEM);
307 
308 	SIMPLEQ_INIT(&(*commit)->parent_ids);
309 
310 	tlen = strlen(GOT_COMMIT_TAG_TREE);
311 	if (strncmp(s, GOT_COMMIT_TAG_TREE, tlen) == 0) {
312 		remain -= tlen;
313 		if (remain < SHA1_DIGEST_STRING_LENGTH) {
314 			err = got_error(GOT_ERR_BAD_OBJ_DATA);
315 			goto done;
316 		}
317 		s += tlen;
318 		if (!got_parse_sha1_digest((*commit)->tree_id.sha1, s)) {
319 			err = got_error(GOT_ERR_BAD_OBJ_DATA);
320 			goto done;
321 		}
322 		remain -= SHA1_DIGEST_STRING_LENGTH;
323 		s += SHA1_DIGEST_STRING_LENGTH;
324 	} else {
325 		err = got_error(GOT_ERR_BAD_OBJ_DATA);
326 		goto done;
327 	}
328 
329 	tlen = strlen(GOT_COMMIT_TAG_PARENT);
330 	while (strncmp(s, GOT_COMMIT_TAG_PARENT, tlen) == 0) {
331 		struct got_parent_id *pid;
332 
333 		remain -= tlen;
334 		if (remain < SHA1_DIGEST_STRING_LENGTH) {
335 			err = got_error(GOT_ERR_BAD_OBJ_DATA);
336 			goto done;
337 		}	
338 
339 		pid = calloc(1, sizeof(*pid));
340 		if (pid == NULL) {
341 			err = got_error(GOT_ERR_NO_MEM);
342 			goto done;
343 		}
344 		s += tlen;
345 		if (!got_parse_sha1_digest(pid->id.sha1, s)) {
346 			err = got_error(GOT_ERR_BAD_OBJ_DATA);
347 			goto done;
348 		}
349 		SIMPLEQ_INSERT_TAIL(&(*commit)->parent_ids, pid, entry);
350 		(*commit)->nparents++;
351 
352 		s += SHA1_DIGEST_STRING_LENGTH;
353 	}
354 
355 	tlen = strlen(GOT_COMMIT_TAG_AUTHOR);
356 	if (strncmp(s, GOT_COMMIT_TAG_AUTHOR, tlen) == 0) {
357 		char *p;
358 
359 		remain -= tlen;
360 		if (remain <= 0) {
361 			err = got_error(GOT_ERR_BAD_OBJ_DATA);
362 			goto done;
363 		}
364 		s += tlen;
365 		p = strchr(s, '\n');
366 		if (p == NULL) {
367 			err = got_error(GOT_ERR_BAD_OBJ_DATA);
368 			goto done;
369 		}
370 		*p = '\0';
371 		(*commit)->author = strdup(s);
372 		if ((*commit)->author == NULL) {
373 			err = got_error(GOT_ERR_NO_MEM);
374 			goto done;
375 		}
376 		s += strlen((*commit)->author) + 1;
377 	}
378 
379 	tlen = strlen(GOT_COMMIT_TAG_COMMITTER);
380 	if (strncmp(s, GOT_COMMIT_TAG_COMMITTER, tlen) == 0) {
381 		char *p;
382 
383 		remain -= tlen;
384 		if (remain <= 0) {
385 			err = got_error(GOT_ERR_BAD_OBJ_DATA);
386 			goto done;
387 		}
388 		s += tlen;
389 		p = strchr(s, '\n');
390 		if (p == NULL) {
391 			err = got_error(GOT_ERR_BAD_OBJ_DATA);
392 			goto done;
393 		}
394 		*p = '\0';
395 		(*commit)->committer = strdup(s);
396 		if ((*commit)->committer == NULL) {
397 			err = got_error(GOT_ERR_NO_MEM);
398 			goto done;
399 		}
400 		s += strlen((*commit)->committer) + 1;
401 	}
402 
403 	(*commit)->logmsg = strdup(s);
404 done:
405 	if (err)
406 		got_object_commit_close(*commit);
407 	return err;
408 }
409 
410 static void
411 tree_entry_close(struct got_tree_entry *te)
412 {
413 	free(te->name);
414 	free(te);
415 }
416 
417 static const char *
418 mode_trailer(mode_t mode)
419 {
420 	if (S_ISDIR(mode))
421 		return "/";
422 
423 	return "";
424 }
425 
426 static const struct got_error *
427 parse_tree_entry(struct got_tree_entry **te, size_t *elen, char *buf,
428     size_t maxlen)
429 {
430 	char *p = buf, *space;
431 	const struct got_error *err = NULL;
432 	char hex[SHA1_DIGEST_STRING_LENGTH];
433 
434 	*te = calloc(1, sizeof(**te));
435 	if (*te == NULL)
436 		return got_error(GOT_ERR_NO_MEM);
437 
438 	*elen = strlen(buf) + 1;
439 	if (*elen > maxlen) {
440 		free(*te);
441 		return got_error(GOT_ERR_BAD_OBJ_DATA);
442 	}
443 
444 	space = strchr(buf, ' ');
445 	if (space == NULL) {
446 		free(*te);
447 		return got_error(GOT_ERR_BAD_OBJ_DATA);
448 	}
449 	while (*p != ' ') {
450 		if (*p < '0' && *p > '7') {
451 			err = got_error(GOT_ERR_BAD_OBJ_DATA);
452 			goto done;
453 		}
454 		(*te)->mode <<= 3;
455 		(*te)->mode |= *p - '0';
456 		p++;
457 	}
458 
459 	(*te)->name = strdup(space + 1);
460 	if (*elen > maxlen || maxlen - *elen < SHA1_DIGEST_LENGTH) {
461 		err = got_error(GOT_ERR_BAD_OBJ_DATA);
462 		goto done;
463 	}
464 	buf += strlen(buf) + 1;
465 	memcpy((*te)->id.sha1, buf, SHA1_DIGEST_LENGTH);
466 	*elen += SHA1_DIGEST_LENGTH;
467 done:
468 	if (err)
469 		tree_entry_close(*te);
470 	return err;
471 }
472 
473 static const struct got_error *
474 parse_tree_object(struct got_tree_object **tree, struct got_repository *repo,
475     char *buf, size_t len)
476 {
477 	size_t remain = len;
478 	int nentries;
479 
480 	*tree = calloc(1, sizeof(**tree));
481 	if (*tree == NULL)
482 		return got_error(GOT_ERR_NO_MEM);
483 
484 	SIMPLEQ_INIT(&(*tree)->entries);
485 
486 	while (remain > 0) {
487 		struct got_tree_entry *te;
488 		size_t elen;
489 
490 		parse_tree_entry(&te, &elen, buf, remain);
491 		(*tree)->nentries++;
492 		SIMPLEQ_INSERT_TAIL(&(*tree)->entries, te, entry);
493 		buf += elen;
494 		remain -= elen;
495 	}
496 
497 	if (remain != 0) {
498 		got_object_tree_close(*tree);
499 		return got_error(GOT_ERR_BAD_OBJ_DATA);
500 	}
501 
502 	return NULL;
503 }
504 
505 static const struct got_error *
506 read_commit_object(struct got_commit_object **commit,
507     struct got_repository *repo, struct got_object *obj, const char *path)
508 {
509 	const struct got_error *err = NULL;
510 	FILE *f;
511 	struct got_zstream_buf zb;
512 	size_t len;
513 	char *p;
514 	int i, ret;
515 
516 	f = fopen(path, "rb");
517 	if (f == NULL)
518 		return got_error(GOT_ERR_BAD_PATH);
519 
520 	err = inflate_init(&zb, 8192);
521 	if (err) {
522 		fclose(f);
523 		return err;
524 	}
525 
526 	do {
527 		err = inflate_read(&zb, f, &len);
528 		if (err || len == 0)
529 			break;
530 	} while (len < obj->hdrlen + obj->size);
531 
532 	if (len < obj->hdrlen + obj->size) {
533 		err = got_error(GOT_ERR_BAD_OBJ_DATA);
534 		goto done;
535 	}
536 
537 	/* Skip object header. */
538 	len -= obj->hdrlen;
539 	err = parse_commit_object(commit, zb.outbuf + obj->hdrlen, len);
540 done:
541 	inflate_end(&zb);
542 	fclose(f);
543 	return err;
544 }
545 
546 const struct got_error *
547 got_object_commit_open(struct got_commit_object **commit,
548     struct got_repository *repo, struct got_object *obj)
549 {
550 	const struct got_error *err = NULL;
551 	char *path = NULL;
552 
553 	if (obj->type != GOT_OBJ_TYPE_COMMIT)
554 		return got_error(GOT_ERR_OBJ_TYPE);
555 
556 	err = object_path(&path, &obj->id, repo);
557 	if (err)
558 		return err;
559 
560 	err = read_commit_object(commit, repo, obj, path);
561 	free(path);
562 	return err;
563 }
564 
565 void
566 got_object_commit_close(struct got_commit_object *commit)
567 {
568 	struct got_parent_id *pid;
569 
570 	while (!SIMPLEQ_EMPTY(&commit->parent_ids)) {
571 		pid = SIMPLEQ_FIRST(&commit->parent_ids);
572 		SIMPLEQ_REMOVE_HEAD(&commit->parent_ids, entry);
573 		free(pid);
574 	}
575 
576 	free(commit->author);
577 	free(commit->committer);
578 	free(commit->logmsg);
579 	free(commit);
580 }
581 
582 static const struct got_error *
583 read_tree_object(struct got_tree_object **tree,
584     struct got_repository *repo, struct got_object *obj, const char *path)
585 {
586 	const struct got_error *err = NULL;
587 	FILE *f;
588 	struct got_zstream_buf zb;
589 	size_t len;
590 	char *p;
591 	int i, ret;
592 
593 	f = fopen(path, "rb");
594 	if (f == NULL)
595 		return got_error(GOT_ERR_BAD_PATH);
596 
597 	err = inflate_init(&zb, 8192);
598 	if (err) {
599 		fclose(f);
600 		return err;
601 	}
602 
603 	do {
604 		err = inflate_read(&zb, f, &len);
605 		if (err || len == 0)
606 			break;
607 	} while (len < obj->hdrlen + obj->size);
608 
609 	if (len < obj->hdrlen + obj->size) {
610 		err = got_error(GOT_ERR_BAD_OBJ_DATA);
611 		goto done;
612 	}
613 
614 	/* Skip object header. */
615 	len -= obj->hdrlen;
616 	err = parse_tree_object(tree, repo, zb.outbuf + obj->hdrlen, len);
617 done:
618 	inflate_end(&zb);
619 	fclose(f);
620 	return err;
621 }
622 
623 const struct got_error *
624 got_object_tree_open(struct got_tree_object **tree,
625     struct got_repository *repo, struct got_object *obj)
626 {
627 	const struct got_error *err = NULL;
628 	char *path = NULL;
629 
630 	if (obj->type != GOT_OBJ_TYPE_TREE)
631 		return got_error(GOT_ERR_OBJ_TYPE);
632 
633 	err = object_path(&path, &obj->id, repo);
634 	if (err)
635 		return err;
636 
637 	err = read_tree_object(tree, repo, obj, path);
638 	free(path);
639 	return err;
640 }
641 
642 void
643 got_object_tree_close(struct got_tree_object *tree)
644 {
645 	struct got_tree_entry *te;
646 
647 	while (!SIMPLEQ_EMPTY(&tree->entries)) {
648 		te = SIMPLEQ_FIRST(&tree->entries);
649 		SIMPLEQ_REMOVE_HEAD(&tree->entries, entry);
650 		tree_entry_close(te);
651 	}
652 
653 	free(tree);
654 }
655 
656 const struct got_error *
657 got_object_blob_open(struct got_blob_object **blob,
658     struct got_repository *repo, struct got_object *obj, size_t blocksize)
659 {
660 	const struct got_error *err = NULL;
661 	char *path;
662 
663 	if (obj->type != GOT_OBJ_TYPE_BLOB)
664 		return got_error(GOT_ERR_OBJ_TYPE);
665 
666 	if (blocksize < obj->hdrlen)
667 		return got_error(GOT_ERR_NO_SPACE);
668 
669 	err = object_path(&path, &obj->id, repo);
670 	if (err)
671 		return err;
672 
673 	*blob = calloc(1, sizeof(**blob));
674 	if (*blob == NULL) {
675 		free(path);
676 		return got_error(GOT_ERR_NO_MEM);
677 	}
678 
679 	(*blob)->f = fopen(path, "rb");
680 	if ((*blob)->f == NULL) {
681 		free(*blob);
682 		free(path);
683 		return got_error(GOT_ERR_BAD_PATH);
684 	}
685 
686 	err = inflate_init(&(*blob)->zb, blocksize);
687 	if (err != NULL) {
688 		fclose((*blob)->f);
689 		free(*blob);
690 		free(path);
691 		return err;
692 	}
693 
694 	(*blob)->hdrlen = obj->hdrlen;
695 
696 	free(path);
697 	return err;
698 }
699 
700 void
701 got_object_blob_close(struct got_blob_object *blob)
702 {
703 	inflate_end(&blob->zb);
704 	fclose(blob->f);
705 	free(blob);
706 }
707 
708 const struct got_error *
709 got_object_blob_read_block(struct got_blob_object *blob, size_t *outlenp)
710 {
711 	return inflate_read(&blob->zb, blob->f, outlenp);
712 }
713