[libgit2.git] / src / apply.c

/*
 * Copyright (C) the libgit2 contributors. All rights reserved.
 *
 * This file is part of libgit2, distributed under the GNU GPL v2 with
 * a Linking Exception. For full terms see the included COPYING file.
 */

#include <assert.h>

#include "git2/patch.h"
#include "git2/filter.h"
#include "array.h"
#include "patch.h"
#include "fileops.h"
#include "apply.h"
#include "delta.h"
#include "zstream.h"

#define apply_err(...) \
	( giterr_set(GITERR_PATCH, __VA_ARGS__), -1 )

typedef struct {
	/* The lines that we allocate ourself are allocated out of the pool.
	 * (Lines may have been allocated out of the diff.)
	 */
	git_pool pool;
	git_vector lines;
} patch_image;

static void patch_line_init(
	git_diff_line *out,
	const char *in,
	size_t in_len,
	size_t in_offset)
{
	out->content = in;
	out->content_len = in_len;
	out->content_offset = in_offset;
}

#define PATCH_IMAGE_INIT { {0} }

static int patch_image_init_fromstr(
	patch_image *out, const char *in, size_t in_len)
{
	git_diff_line *line;
	const char *start, *end;

	memset(out, 0x0, sizeof(patch_image));

	git_pool_init(&out->pool, sizeof(git_diff_line));

	for (start = in; start < in + in_len; start = end) {
		end = memchr(start, '\n', in_len);

		if (end == NULL)
			end = in + in_len;

		else if (end < in + in_len)
			end++;

		line = git_pool_mallocz(&out->pool, 1);
		GITERR_CHECK_ALLOC(line);

		if (git_vector_insert(&out->lines, line) < 0)
			return -1;

		patch_line_init(line, start, (end - start), (start - in));
	}

	return 0;
}

static void patch_image_free(patch_image *image)
{
	if (image == NULL)
		return;

	git_pool_clear(&image->pool);
	git_vector_free(&image->lines);
}

static bool match_hunk(
	patch_image *image,
	patch_image *preimage,
	size_t linenum)
{
	bool match = 0;
	size_t i;

	/* Ensure this hunk is within the image boundaries. */
	if (git_vector_length(&preimage->lines) + linenum >
		git_vector_length(&image->lines))
		return 0;

	match = 1;

	/* Check exact match. */
	for (i = 0; i < git_vector_length(&preimage->lines); i++) {
		git_diff_line *preimage_line = git_vector_get(&preimage->lines, i);
		git_diff_line *image_line = git_vector_get(&image->lines, linenum + i);

		if (preimage_line->content_len != image_line->content_len ||
			memcmp(preimage_line->content, image_line->content, image_line->content_len) != 0) {
			match = 0;
			break;
		}
	}

	return match;
}

static bool find_hunk_linenum(
	size_t *out,
	patch_image *image,
	patch_image *preimage,
	size_t linenum)
{
	size_t max = git_vector_length(&image->lines);
	bool match;

	if (linenum > max)
		linenum = max;

	match = match_hunk(image, preimage, linenum);

	*out = linenum;
	return match;
}

static int update_hunk(
	patch_image *image,
	unsigned int linenum,
	patch_image *preimage,
	patch_image *postimage)
{
	size_t postlen = git_vector_length(&postimage->lines);
	size_t prelen = git_vector_length(&preimage->lines);
	size_t i;
	int error = 0;

	if (postlen > prelen)
		error = git_vector_insert_null(
			&image->lines, linenum, (postlen - prelen));
	else if (prelen > postlen)
		error = git_vector_remove_range(
			&image->lines, linenum, (prelen - postlen));

	if (error) {
		giterr_set_oom();
		return -1;
	}

	for (i = 0; i < git_vector_length(&postimage->lines); i++) {
		image->lines.contents[linenum + i] =
			git_vector_get(&postimage->lines, i);
	}

	return 0;
}

static int apply_hunk(
	patch_image *image,
	git_patch *patch,
	git_patch_hunk *hunk)
{
	patch_image preimage = PATCH_IMAGE_INIT, postimage = PATCH_IMAGE_INIT;
	size_t line_num, i;
	int error = 0;

	for (i = 0; i < hunk->line_count; i++) {
		size_t linenum = hunk->line_start + i;
		git_diff_line *line = git_array_get(patch->lines, linenum);

		if (!line) {
			error = apply_err("Preimage does not contain line %d", linenum);
			goto done;
		}

		if (line->origin == GIT_DIFF_LINE_CONTEXT ||
			line->origin == GIT_DIFF_LINE_DELETION) {
			if ((error = git_vector_insert(&preimage.lines, line)) < 0)
				goto done;
		}

		if (line->origin == GIT_DIFF_LINE_CONTEXT ||
			line->origin == GIT_DIFF_LINE_ADDITION) {
			if ((error = git_vector_insert(&postimage.lines, line)) < 0)
				goto done;
		}
	}

	line_num = hunk->hunk.new_start ? hunk->hunk.new_start - 1 : 0;

	if (!find_hunk_linenum(&line_num, image, &preimage, line_num)) {
		error = apply_err("Hunk at line %d did not apply",
			hunk->hunk.new_start);
		goto done;
	}

	error = update_hunk(image, line_num, &preimage, &postimage);

done:
	patch_image_free(&preimage);
	patch_image_free(&postimage);

	return error;
}

static int apply_hunks(
	git_buf *out,
	const char *source,
	size_t source_len,
	git_patch *patch)
{
	git_patch_hunk *hunk;
	git_diff_line *line;
	patch_image image;
	size_t i;
	int error = 0;

	if ((error = patch_image_init_fromstr(&image, source, source_len)) < 0)
		goto done;

	git_array_foreach(patch->hunks, i, hunk) {
		if ((error = apply_hunk(&image, patch, hunk)) < 0)
			goto done;
	}

	git_vector_foreach(&image.lines, i, line)
		git_buf_put(out, line->content, line->content_len);

done:
	patch_image_free(&image);

	return error;
}

static int apply_binary_delta(
	git_buf *out,
	const char *source,
	size_t source_len,
	git_diff_binary_file *binary_file)
{
	git_buf inflated = GIT_BUF_INIT;
	int error = 0;

	/* no diff means identical contents */
	if (binary_file->datalen == 0)
		return git_buf_put(out, source, source_len);

	error = git_zstream_inflatebuf(&inflated,
		binary_file->data, binary_file->datalen);

	if (!error && inflated.size != binary_file->inflatedlen) {
		error = apply_err("inflated delta does not match expected length");
		git_buf_free(out);
	}

	if (error < 0)
		goto done;

	if (binary_file->type == GIT_DIFF_BINARY_DELTA) {
		void *data;
		size_t data_len;

		error = git_delta_apply(&data, &data_len, (void *)source, source_len,
			(void *)inflated.ptr, inflated.size);

		out->ptr = data;
		out->size = data_len;
		out->asize = data_len;
	}
	else if (binary_file->type == GIT_DIFF_BINARY_LITERAL) {
		git_buf_swap(out, &inflated);
	}
	else {
		error = apply_err("unknown binary delta type");
		goto done;
	}

done:
	git_buf_free(&inflated);
	return error;
}

static int apply_binary(
	git_buf *out,
	const char *source,
	size_t source_len,
	git_patch *patch)
{
	git_buf reverse = GIT_BUF_INIT;
	int error;

	/* first, apply the new_file delta to the given source */
	if ((error = apply_binary_delta(out, source, source_len,
			&patch->binary.new_file)) < 0)
		goto done;

	/* second, apply the old_file delta to sanity check the result */
	if ((error = apply_binary_delta(&reverse, out->ptr, out->size,
			&patch->binary.old_file)) < 0)
		goto done;

	if (source_len != reverse.size ||
		memcmp(source, reverse.ptr, source_len) != 0) {
		error = apply_err("binary patch did not apply cleanly");
		goto done;
	}

done:
	if (error < 0)
		git_buf_free(out);

	git_buf_free(&reverse);
	return error;
}

int git_apply__patch(
	git_buf *contents_out,
	char **filename_out,
	unsigned int *mode_out,
	const char *source,
	size_t source_len,
	git_patch *patch)
{
	char *filename = NULL;
	unsigned int mode = 0;
	int error = 0;

	assert(contents_out && filename_out && mode_out && (source || !source_len) && patch);

	*filename_out = NULL;
	*mode_out = 0;

	if (patch->delta->status != GIT_DELTA_DELETED) {
		const git_diff_file *newfile = &patch->delta->new_file;

		filename = git__strdup(newfile->path);
		mode = newfile->mode ?
			newfile->mode : GIT_FILEMODE_BLOB;
	}

	if (patch->delta->flags & GIT_DIFF_FLAG_BINARY)
		error = apply_binary(contents_out, source, source_len, patch);
	else if (patch->hunks.size)
		error = apply_hunks(contents_out, source, source_len, patch);
	else
		error = git_buf_put(contents_out, source, source_len);

	if (error)
		goto done;

	if (patch->delta->status == GIT_DELTA_DELETED &&
		git_buf_len(contents_out) > 0) {
		error = apply_err("removal patch leaves file contents");
		goto done;
	}

	*filename_out = filename;
	*mode_out = mode;

done:
	if (error < 0)
		git__free(filename);

	return error;
}
Commit	Line	Data
7cb904ba ET	1	/*
	2	* Copyright (C) the libgit2 contributors. All rights reserved.
	3	*
	4	* This file is part of libgit2, distributed under the GNU GPL v2 with
	5	* a Linking Exception. For full terms see the included COPYING file.
	6	*/
	7
	8	#include <assert.h>
	9
	10	#include "git2/patch.h"
	11	#include "git2/filter.h"
	12	#include "array.h"
804d5fe9	13	#include "patch.h"
7cb904ba ET	14	#include "fileops.h"
7cb904ba ET	15	#include "apply.h"
3149ff6f ET	16	#include "delta.h"
3149ff6f ET	17	#include "zstream.h"
7cb904ba ET	18
	19	#define apply_err(...) \
	20	( giterr_set(GITERR_PATCH, __VA_ARGS__), -1 )
	21
	22	typedef struct {
	23	/* The lines that we allocate ourself are allocated out of the pool.
	24	* (Lines may have been allocated out of the diff.)
	25	*/
	26	git_pool pool;
	27	git_vector lines;
	28	} patch_image;
	29
	30	static void patch_line_init(
	31	git_diff_line *out,
	32	const char *in,
	33	size_t in_len,
	34	size_t in_offset)
	35	{
	36	out->content = in;
	37	out->content_len = in_len;
	38	out->content_offset = in_offset;
	39	}
	40
0267c34c	41	#define PATCH_IMAGE_INIT { {0} }
7cb904ba ET	42
	43	static int patch_image_init_fromstr(
	44	patch_image out, const char in, size_t in_len)
	45	{
	46	git_diff_line *line;
	47	const char start, end;
	48
	49	memset(out, 0x0, sizeof(patch_image));
	50
	51	git_pool_init(&out->pool, sizeof(git_diff_line));
	52
	53	for (start = in; start < in + in_len; start = end) {
	54	end = memchr(start, '\n', in_len);
	55
581a4d39 ET	56	if (end == NULL)
	57	end = in + in_len;
	58
	59	else if (end < in + in_len)
7cb904ba ET	60	end++;
	61
	62	line = git_pool_mallocz(&out->pool, 1);
	63	GITERR_CHECK_ALLOC(line);
	64
	65	if (git_vector_insert(&out->lines, line) < 0)
	66	return -1;
	67
	68	patch_line_init(line, start, (end - start), (start - in));
	69	}
	70
	71	return 0;
	72	}
	73
	74	static void patch_image_free(patch_image *image)
	75	{
	76	if (image == NULL)
	77	return;
	78
	79	git_pool_clear(&image->pool);
	80	git_vector_free(&image->lines);
	81	}
	82
	83	static bool match_hunk(
	84	patch_image *image,
	85	patch_image *preimage,
	86	size_t linenum)
	87	{
	88	bool match = 0;
	89	size_t i;
	90
	91	/* Ensure this hunk is within the image boundaries. */
	92	if (git_vector_length(&preimage->lines) + linenum >
	93	git_vector_length(&image->lines))
	94	return 0;
	95
	96	match = 1;
	97
	98	/* Check exact match. */
	99	for (i = 0; i < git_vector_length(&preimage->lines); i++) {
	100	git_diff_line *preimage_line = git_vector_get(&preimage->lines, i);
	101	git_diff_line *image_line = git_vector_get(&image->lines, linenum + i);
	102
531be3e8	103	if (preimage_line->content_len != image_line->content_len \|\|
7cb904ba ET	104	memcmp(preimage_line->content, image_line->content, image_line->content_len) != 0) {
	105	match = 0;
	106	break;
	107	}
	108	}
	109
	110	return match;
	111	}
	112
	113	static bool find_hunk_linenum(
	114	size_t *out,
	115	patch_image *image,
	116	patch_image *preimage,
	117	size_t linenum)
	118	{
	119	size_t max = git_vector_length(&image->lines);
	120	bool match;
	121
	122	if (linenum > max)
	123	linenum = max;
	124
	125	match = match_hunk(image, preimage, linenum);
	126
	127	*out = linenum;
	128	return match;
	129	}
	130
	131	static int update_hunk(
	132	patch_image *image,
	133	unsigned int linenum,
	134	patch_image *preimage,
	135	patch_image *postimage)
	136	{
	137	size_t postlen = git_vector_length(&postimage->lines);
	138	size_t prelen = git_vector_length(&preimage->lines);
	139	size_t i;
	140	int error = 0;
	141
	142	if (postlen > prelen)
53571f2f	143	error = git_vector_insert_null(
7cb904ba ET	144	&image->lines, linenum, (postlen - prelen));
7cb904ba ET	145	else if (prelen > postlen)
53571f2f	146	error = git_vector_remove_range(
7cb904ba ET	147	&image->lines, linenum, (prelen - postlen));
	148
	149	if (error) {
	150	giterr_set_oom();
	151	return -1;
	152	}
	153
	154	for (i = 0; i < git_vector_length(&postimage->lines); i++) {
	155	image->lines.contents[linenum + i] =
	156	git_vector_get(&postimage->lines, i);
	157	}
	158
	159	return 0;
	160	}
	161
	162	static int apply_hunk(
	163	patch_image *image,
	164	git_patch *patch,
804d5fe9	165	git_patch_hunk *hunk)
7cb904ba	166	{
0267c34c	167	patch_image preimage = PATCH_IMAGE_INIT, postimage = PATCH_IMAGE_INIT;
7cb904ba ET	168	size_t line_num, i;
	169	int error = 0;
	170
7cb904ba ET	171	for (i = 0; i < hunk->line_count; i++) {
	172	size_t linenum = hunk->line_start + i;
	173	git_diff_line *line = git_array_get(patch->lines, linenum);
	174
	175	if (!line) {
	176	error = apply_err("Preimage does not contain line %d", linenum);
	177	goto done;
	178	}
	179
	180	if (line->origin == GIT_DIFF_LINE_CONTEXT \|\|
	181	line->origin == GIT_DIFF_LINE_DELETION) {
	182	if ((error = git_vector_insert(&preimage.lines, line)) < 0)
	183	goto done;
	184	}
	185
	186	if (line->origin == GIT_DIFF_LINE_CONTEXT \|\|
	187	line->origin == GIT_DIFF_LINE_ADDITION) {
	188	if ((error = git_vector_insert(&postimage.lines, line)) < 0)
	189	goto done;
	190	}
	191	}
	192
	193	line_num = hunk->hunk.new_start ? hunk->hunk.new_start - 1 : 0;
	194
	195	if (!find_hunk_linenum(&line_num, image, &preimage, line_num)) {
	196	error = apply_err("Hunk at line %d did not apply",
	197	hunk->hunk.new_start);
	198	goto done;
	199	}
	200
	201	error = update_hunk(image, line_num, &preimage, &postimage);
	202
	203	done:
	204	patch_image_free(&preimage);
	205	patch_image_free(&postimage);
	206
	207	return error;
	208	}
	209
	210	static int apply_hunks(
	211	git_buf *out,
	212	const char *source,
	213	size_t source_len,
	214	git_patch *patch)
	215	{
804d5fe9	216	git_patch_hunk *hunk;
7cb904ba ET	217	git_diff_line *line;
	218	patch_image image;
	219	size_t i;
	220	int error = 0;
	221
	222	if ((error = patch_image_init_fromstr(&image, source, source_len)) < 0)
	223	goto done;
	224
	225	git_array_foreach(patch->hunks, i, hunk) {
	226	if ((error = apply_hunk(&image, patch, hunk)) < 0)
	227	goto done;
	228	}
	229
	230	git_vector_foreach(&image.lines, i, line)
	231	git_buf_put(out, line->content, line->content_len);
	232
	233	done:
	234	patch_image_free(&image);
	235
	236	return error;
	237	}
	238
3149ff6f ET	239	static int apply_binary_delta(
	240	git_buf *out,
	241	const char *source,
	242	size_t source_len,
	243	git_diff_binary_file *binary_file)
	244	{
	245	git_buf inflated = GIT_BUF_INIT;
	246	int error = 0;
	247
	248	/* no diff means identical contents */
	249	if (binary_file->datalen == 0)
	250	return git_buf_put(out, source, source_len);
	251
	252	error = git_zstream_inflatebuf(&inflated,
	253	binary_file->data, binary_file->datalen);
	254
	255	if (!error && inflated.size != binary_file->inflatedlen) {
	256	error = apply_err("inflated delta does not match expected length");
	257	git_buf_free(out);
	258	}
	259
	260	if (error < 0)
	261	goto done;
	262
	263	if (binary_file->type == GIT_DIFF_BINARY_DELTA) {
	264	void *data;
	265	size_t data_len;
	266
	267	error = git_delta_apply(&data, &data_len, (void *)source, source_len,
	268	(void *)inflated.ptr, inflated.size);
	269
	270	out->ptr = data;
	271	out->size = data_len;
	272	out->asize = data_len;
	273	}
	274	else if (binary_file->type == GIT_DIFF_BINARY_LITERAL) {
	275	git_buf_swap(out, &inflated);
	276	}
	277	else {
	278	error = apply_err("unknown binary delta type");
	279	goto done;
	280	}
	281
	282	done:
	283	git_buf_free(&inflated);
	284	return error;
	285	}
	286
	287	static int apply_binary(
	288	git_buf *out,
	289	const char *source,
	290	size_t source_len,
	291	git_patch *patch)
	292	{
	293	git_buf reverse = GIT_BUF_INIT;
	294	int error;
	295
	296	/* first, apply the new_file delta to the given source */
	297	if ((error = apply_binary_delta(out, source, source_len,
	298	&patch->binary.new_file)) < 0)
	299	goto done;
	300
	301	/* second, apply the old_file delta to sanity check the result */
	302	if ((error = apply_binary_delta(&reverse, out->ptr, out->size,
303	&patch->binary.old_file)) < 0)
304	goto done;
305
306	if (source_len != reverse.size \|\|
307	memcmp(source, reverse.ptr, source_len) != 0) {
308	error = apply_err("binary patch did not apply cleanly");
309	goto done;
310	}
311
312	done:
313	if (error < 0)
314	git_buf_free(out);
315
316	git_buf_free(&reverse);
317	return error;
318	}
319
7cb904ba ET	320	int git_apply__patch(
	321	git_buf *contents_out,
	322	char **filename_out,
	323	unsigned int *mode_out,
	324	const char *source,
	325	size_t source_len,
	326	git_patch *patch)
	327	{
	328	char *filename = NULL;
	329	unsigned int mode = 0;
	330	int error = 0;
	331
	332	assert(contents_out && filename_out && mode_out && (source \|\| !source_len) && patch);
	333
	334	*filename_out = NULL;
	335	*mode_out = 0;
	336
	337	if (patch->delta->status != GIT_DELTA_DELETED) {
b85bd8ce	338	const git_diff_file *newfile = &patch->delta->new_file;
804d5fe9 ET	339
	340	filename = git__strdup(newfile->path);
	341	mode = newfile->mode ?
	342	newfile->mode : GIT_FILEMODE_BLOB;
7cb904ba ET	343	}
7cb904ba ET	344
3149ff6f ET	345	if (patch->delta->flags & GIT_DIFF_FLAG_BINARY)
	346	error = apply_binary(contents_out, source, source_len, patch);
	347	else if (patch->hunks.size)
	348	error = apply_hunks(contents_out, source, source_len, patch);
	349	else
	350	error = git_buf_put(contents_out, source, source_len);
	351
	352	if (error)
7cb904ba ET	353	goto done;
	354
	355	if (patch->delta->status == GIT_DELTA_DELETED &&
	356	git_buf_len(contents_out) > 0) {
	357	error = apply_err("removal patch leaves file contents");
	358	goto done;
	359	}
	360
	361	*filename_out = filename;
	362	*mode_out = mode;
	363
	364	done:
	365	if (error < 0)
	366	git__free(filename);
	367
	368	return error;
	369	}