/*  This file is part of "reprepro"
 *  Copyright (C) 2009 Bernhard R. Link
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License version 2 as
 *  published by the Free Software Foundation.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program; if not, write to the Free Software
 *  Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02111-1301  USA
 */
#include <config.h>

#include <errno.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <sys/mman.h>
#include <unistd.h>
#include <stdlib.h>
#include <stdio.h>
#include <fcntl.h>
#include <malloc.h>
#include <string.h>
#include <assert.h>
#include "error.h"
#include "rredpatch.h"

struct modification {
	/* next item in the list (sorted by oldlinestart) */
	struct modification *next, *previous;
	/* each modification removes an (possible empty) range from
	 * the file and replaces it with an (possible empty) range
	 * of new lines */
	int oldlinestart, oldlinecount, newlinecount;
	size_t len;
	const char *content;
	/* a entry might be followed by one other with the same
	 * oldlinestart (due to merging or inefficient patches),
	 * but always: next->oldlinestart >= oldlinestart + oldlinecount
	 */
};

struct rred_patch {
	int fd;
	/* content of the file mapped with mmap */
	char *data;
	off_t len;
	struct modification *modifications;
	bool alreadyinuse;
};

void modification_freelist(struct modification *p) {
	while( p != NULL ) {
		struct modification *m = p;
		p = m->next;
		free(m);
	}
}

struct modification *patch_getmodifications(struct rred_patch *p) {
	struct modification *m;

	assert( !p->alreadyinuse );
	m = p->modifications;
	p->modifications = NULL;
	p->alreadyinuse = true;
	return m;
}

const struct modification *patch_getconstmodifications(struct rred_patch *p) {
	assert( !p->alreadyinuse );
	return p->modifications;
}

static struct modification *modification_freehead(/*@only@*/struct modification *p) {
	struct modification *m = p->next;
	free(p);
	return m;
}

void patch_free(/*@only@*/struct rred_patch *p) {
	if( p->data != NULL )
		(void)munmap(p->data, p->len);
	if( p->fd >= 0 )
		(void)close(p->fd);
	modification_freelist(p->modifications);
	free(p);
}

retvalue patch_load(const char *filename, off_t length, struct rred_patch **patch_p) {
	int i;
	struct rred_patch *patch;
	const char *p, *e, *d, *l;
	int number, number2, line;
	char type;
	struct modification *n;
	struct stat statbuf;

	patch = calloc(1, sizeof(struct rred_patch));
	if( FAILEDTOALLOC(patch) )
		return RET_ERROR_OOM;
	patch->fd = open(filename, O_NOCTTY|O_RDONLY);
	if( patch->fd < 0 ) {
		int err = errno;
		fprintf(stderr,
"Error %d opening '%s' for reading: %s\n", err, filename, strerror(err));
		patch_free(patch);
		return RET_ERRNO(err);
	}
	i = fstat(patch->fd, &statbuf);
	if( i != 0 ) {
		int err = errno;
		fprintf(stderr,
"Error %d retrieving length of '%s': %s\n", err, filename, strerror(err));
		patch_free(patch);
		return RET_ERRNO(err);
	}
	if( length == -1 )
		length = statbuf.st_size;
	if( statbuf.st_size != length ) {
		int err = errno;
		fprintf(stderr,
"Unexpected size of '%s': expected %lld, got %lld\n", filename,
			(long long)length, (long long)statbuf.st_size);
		patch_free(patch);
		return RET_ERRNO(err);
	}
	if( length == 0 ) {
		/* handle empty patches gracefully */
		close(patch->fd);
		patch->fd = -1;
		patch->data = NULL;
		patch->len = 0;
		patch->modifications = NULL;
		*patch_p = patch;
		return RET_OK;
	}
	patch->len = length;
	patch->data = mmap(NULL, patch->len, PROT_READ, MAP_PRIVATE,
			patch->fd, 0);
	if( patch->data == MAP_FAILED ) {
		int err = errno;
		fprintf(stderr,
"Error %d mapping '%s' into memory: %s\n", err, filename, strerror(err));
		patch_free(patch);
		return RET_ERRNO(err);
	}
	p = patch->data;
	e = p + patch->len;
	line = 1;
	while( p < e ) {
		/* <number>,<number>(c|d)\n or <number>(a|i|c|d) */
		d = p;
		number = 0; number2 = -1;
		while( d < e && *d >= '0' && *d <= '9' ) {
			number = (*d - '0') + 10 * number;
			d++;
		}
		if( d > p && d < e && *d == ',' ) {
			d++;
			number2 = 0;
			while( d < e && *d >= '0' && *d <= '9' ) {
				number2 = (*d - '0') + 10 * number2;
				d++;
			}
			if( number2 < number ) {
				fprintf(stderr,
"Error parsing '%s': malformed range (2nd number smaller than 1s) at line %d\n",
					filename, line);
				patch_free(patch);
				return RET_ERROR;
			}
		}
		if( d >= e || (*d != 'c' && *d != 'i' && *d != 'a' && *d != 'd') ) {
			fprintf(stderr,
"Error parsing '%s': expected rule (c,i,a or d) at line %d\n",
				filename, line);
			patch_free(patch);
			return RET_ERROR;
		}
		type = *d;
		d++;
		while( d < e && *d == '\r' )
			d++;
		if( d >= e || *d != '\n' ) {
			fprintf(stderr,
"Error parsing '%s': expected newline after command at line %d\n",
				filename, line);
			patch_free(patch);
			return RET_ERROR;
		}
		d++;
		line++;

		if( type != 'a' && number == 0 ) {
			fprintf(stderr,
"Error parsing '%s': missing number at line %d\n",
				filename, line);
			patch_free(patch);
			return RET_ERROR;
		}
		if( type != 'c' && type != 'd'  && number2 >= 0 ) {
			fprintf(stderr,
"Error parsing '%s': line range not allowed with %c at line %d\n",
				filename, (char)type, line);
			patch_free(patch);
			return RET_ERROR;
		}
		n = calloc(1, sizeof(struct modification));
		if( FAILEDTOALLOC(n) ) {
			patch_free(patch);
			return RET_ERROR_OOM;
		}
		n->next = patch->modifications;
		if( n->next != NULL )
			n->next->previous = n;
		patch->modifications = n;

		p = d;
		if( type == 'd') {
			n->content = NULL;
			n->len = 0;
			n->newlinecount = 0;
		} else {
			int startline = line;

			l = p;
			while( l < e ) {
				p = l;
				while( l < e && *l != '\n' )
					l++;
				if( l >= e ) {
					if( l == p + 1 && *p == '.' ) {
						/* that is also corrupted,
						 * but we can cure it */
						break;
					}
					fprintf(stderr,
"Error parsing '%s': ends in unterminated line. File most likely corrupted\n",
							filename);
					patch_free(patch);
					return RET_ERROR;
				}
				l++;
				if( p[0] == '.' && (p[1] == '\n' || p[1] == '\r') )
					break;
				line++;
			}
			if( p[0] != '.' || ( l > p + 1 && p[1] != '\n' && p[1] != '\r' )) {
					fprintf(stderr,
"Error parsing '%s': ends waiting for dot. File most likely corrupted\n",
							filename);
					patch_free(patch);
					return RET_ERROR;
			}
			n->content = d;
			n->len = p - d;
			n->newlinecount = line - startline;
			p = l;
			line++;
		}
		if( type == 'a' ) {
			/* appends appends after instead of before something: */
			n->oldlinestart = number + 1;
			n->oldlinecount = 0;
		} else if( type == 'i' ) {
			n->oldlinestart = number;
			n->oldlinecount = 0;
		} else {
			n->oldlinestart = number;
			if( number2 < 0 )
				n->oldlinecount = 1;
			else
				n->oldlinecount = (number2 - number) + 1;
		}
		/* make sure things are in the order diff usually
		 * generates them, which makes line-calculation much easier: */
		if( n->next != NULL ) {
			if( n->oldlinestart + n->oldlinecount
					> n->next->oldlinestart ) {
				struct modification *first, *second;
				retvalue r;

				// TODO: it might be more efficient to
				// first store the different parts as different
				// patchsets and then combine...

				/* unlink and feed into patch merger */
				first = n->next;
				first->previous = NULL;
				second = n;
				n->next = NULL;
				n = NULL;
				r = combine_patches(&n, first, second);
				patch->modifications = n;
				if( RET_WAS_ERROR(r) ) {
					patch_free(patch);
					return r;
				}
			}
		}
	}
	*patch_p = patch;
	return RET_OK;
}

static void modification_stripendlines(struct modification *m, int r) {
	int lines;
	const char *p;

	m->newlinecount -= r;
	lines = m->newlinecount;
	p = m->content;
	while( lines > 0 ) {
		while( *p != '\n')
			p++;
		p++;
		lines--;
	}
	assert( (size_t)(p - m->content) <= m->len );
	m->len = p - m->content;
}

static void modification_stripstartlines(struct modification *m, int r) {
	const char *p;

	m->newlinecount -= r;
	p = m->content;
	while( r > 0 ) {
		while( *p != '\n')
			p++;
		p++;
		r--;
	}
	assert( (size_t)(p - m->content) <= m->len );
	m->len -= p - m->content;
	m->content = p;
}

static inline void move_queue(struct modification **last_p, struct modification **result_p, struct modification **from_p) {
	struct modification *toadd, *last;

	/* remove from queue: */
	toadd = *from_p;
	*from_p = toadd->next;
	if( toadd->next != NULL ) {
		toadd->next->previous = NULL;
		toadd->next = NULL;
	}

	/* if nothing yet, make it the first */
	if( *last_p == NULL ) {
		*result_p = toadd;
		toadd->previous = NULL;
		*last_p = toadd;
		return;
	}

	last = *last_p;
	if( toadd->oldlinestart == last->oldlinestart + last->oldlinecount ) {
		/* check if something can be combined: */
		if( toadd->newlinecount == 0 ) {
			last->oldlinecount += toadd->oldlinecount;
			free(toadd);
			return;
		}
		if( last->newlinecount == 0 ) {
			toadd->oldlinestart = last->oldlinestart;
			toadd->oldlinecount += last->oldlinecount;
			toadd->previous = last->previous;
			if( toadd->previous == NULL )
				*result_p = toadd;
			else
				toadd->previous->next = toadd;
			*last_p = toadd;
			free(last);
			return;
		}
		if( last->content + last->len == toadd->content ) {
			last->oldlinecount += toadd->oldlinecount;
			last->newlinecount += toadd->newlinecount;
			last->len += toadd->len;
			free(toadd);
			return;
		}
	}
	toadd->previous = last;
	last->next = toadd;
	assert( last->oldlinestart + last->oldlinecount <= toadd->oldlinestart );
	*last_p = toadd;
	return;
}

/* this merges a set of modifications into an already existing stack,
 * modifying line numbers or even cutting away deleted/newly overwritten
 * stuff as necessary */
retvalue combine_patches(struct modification **result_p, /*@only@*/struct modification *first, /*@only@*/struct modification *second) {
	struct modification *p, *a, *result, *last;
	long lineofs;

	p = first;
	result = NULL;
	last = NULL;
	a = second;

	lineofs = 0;

	while( a != NULL ) {
		/* modification totally before current one,
		 * so just add it before it */
		if( p == NULL || lineofs + a->oldlinestart + a->oldlinecount
				<= p->oldlinestart ) {
			a->oldlinestart += lineofs;
			move_queue(&last, &result, &a);
			assert( p == NULL || p->oldlinestart >=
					last->oldlinestart + last->oldlinecount );
			continue;
		}
		/* modification to add after current head modification,
		 * so finalize head modification and update lineofs */
		if( lineofs + a->oldlinestart
			  	>= p->oldlinestart + p->newlinecount ) {
			lineofs += p->oldlinecount - p->newlinecount;
			move_queue(&last, &result, &p);
			assert( lineofs + a->oldlinestart >=
					last->oldlinestart + last->oldlinecount );
			continue;
		}
		/* new modification removes everything the old one added: */
		if( lineofs + a->oldlinestart <= p->oldlinestart
			  && lineofs + a->oldlinestart + a->oldlinecount
			  	>= p->oldlinestart + p->newlinecount ) {
			a->oldlinestart -= p->oldlinecount - p->newlinecount;
			a->oldlinecount += p->oldlinecount - p->newlinecount;
			lineofs += p->oldlinecount - p->newlinecount;
			p = modification_freehead(p);
			if( a->oldlinecount == 0 && a->newlinecount == 0 ) {
				/* a exactly cancels p */
				a = modification_freehead(a);
			}
			/* otherwise a is not yet finished, it might modify more */
			continue;
		}
		/* otherwise something overlaps, things get complicated here: */

		/* start of *a removes end of *p, so reduce *p: */
		if( lineofs + a->oldlinestart > p->oldlinestart &&
				lineofs + a->oldlinestart
				< p->oldlinestart + p->newlinecount &&
				lineofs + a->oldlinestart + a->oldlinecount
				>= p->oldlinestart + p->newlinecount ) {
			int removedlines = p->oldlinestart + p->newlinecount
				- (lineofs + a->oldlinestart);

			/* finalize p as before */
			lineofs += p->oldlinecount - p->newlinecount;
			/* just telling a to delete less */
			a->oldlinestart += removedlines;
			a->oldlinecount -= removedlines;
			/* and p to add less */
			modification_stripendlines(p, removedlines);
			move_queue(&last, &result, &p);
			assert( lineofs + a->oldlinestart >=
					last->oldlinestart + last->oldlinecount );
			continue;
		}
		/* end of *a remove start of *p, so finalize *a and reduce *p */
		if( lineofs + a->oldlinestart <= p->oldlinestart &&
				lineofs + a->oldlinestart + a->oldlinecount
				> p->oldlinestart  &&
				lineofs + a->oldlinestart + a->oldlinecount
				< p->oldlinestart + p->newlinecount ) {
			int removedlines =
				lineofs + a->oldlinestart + a->oldlinecount
				- p->oldlinestart;
			/* finalize *a with less lines deleted:*/
			a->oldlinestart += lineofs;
			a->oldlinecount -= removedlines;
			if( a->oldlinecount == 0 && a->newlinecount == 0 ) {
				/* a only removed something and this was hereby
				 * removed from p */
				a = modification_freehead(a);
			} else
				move_queue(&last, &result, &a);
			/* and reduce the number of lines of *p */
			assert( removedlines < p->newlinecount );
			modification_stripstartlines(p, removedlines);
			/* p->newlinecount got smaller, so less will be deleted later */
			lineofs -= removedlines;
			if( last != NULL ) {
			assert( p->oldlinestart >= last->oldlinestart + last->oldlinecount);
			if( a != NULL )
				assert( lineofs + a->oldlinestart >= last->oldlinestart + last->oldlinecount);
			}
			/* note that a->oldlinestart+a->oldlinecount+1
			 *        == p->oldlinestart */
			continue;
		}
		/* the most complex case left, a inside p, this
		 * needs p split in two */
		if( lineofs + a->oldlinestart > p->oldlinestart &&
				lineofs + a->oldlinestart + a->oldlinecount
				< p->oldlinestart + p->newlinecount ) {
			struct modification *n;
			int removedlines = p->oldlinestart + p->newlinecount
				- (lineofs + a->oldlinestart);

			n = calloc(1, sizeof(struct modification));
			if( FAILEDTOALLOC(n) ) {
				modification_freelist(result);
				modification_freelist(p);
				modification_freelist(a);
				return RET_ERROR_OOM;
			}
			*n = *p;
			/* all removing into the later p, so
			 * that later numbers fit */
			n->next = NULL;
			n->oldlinecount = 0;
			assert( removedlines < n->newlinecount );
			modification_stripendlines(n, removedlines);
			lineofs += n->oldlinecount - n->newlinecount;
			assert( lineofs+a->oldlinestart <= p->oldlinestart);
			move_queue(&last, &result, &n);
			assert( n == NULL);
			/* only remove this and let the rest of the
			 * code handle the other changes */
			modification_stripstartlines(p, p->newlinecount - removedlines);
			assert(p->newlinecount == removedlines);
			assert( lineofs + a->oldlinestart >=
					last->oldlinestart + last->oldlinecount );
			continue;
		}
		modification_freelist(result);
		modification_freelist(p);
		modification_freelist(a);
		fputs("Internal error in rred merging!\n", stderr);
		return RET_ERROR;
	}
	while( p != NULL ) {
		move_queue(&last, &result, &p);
	}
	*result_p = result;
	return RET_OK;
}

retvalue patch_file(FILE *o, const char *source, const struct modification *patch) {
	FILE *i;
	int currentline, ignore, c;

	i = fopen(source, "r");
	if( i == NULL ) {
		int e = errno;
		fprintf(stderr, "Error %d opening %s: %s\n",
				e, source, strerror(e));
		return RET_ERRNO(e);
	}
	assert( patch == NULL || patch->oldlinestart > 0 );
	currentline = 1;
	do {
		while( patch != NULL && patch->oldlinestart == currentline ) {
			fwrite(patch->content, patch->len, 1, o);
			ignore = patch->oldlinecount;
			patch = patch->next;
			while( ignore > 0 ) {
				do {
					c = getc(i);
				} while( c != '\n' && c != EOF);
				ignore--;
				currentline++;
			}
		}
		assert( patch == NULL || patch->oldlinestart >= currentline );
		while( (c = getc(i)) != '\n' ) {
			if( c == EOF ) {
				if( patch != NULL ) {
					fprintf(stderr,
"Error patching '%s', file shorter than expected by patches!\n",
						source);
					(void)fclose(i);
					return RET_ERROR;
				}
				break;
			}
			putc(c, o);
		}
		if( c == EOF )
			break;
		putc(c, o);
		currentline++;
	} while (1);
	if( ferror(i) != 0 ) {
		int e = errno;
		fprintf(stderr, "Error %d reading %s: %s\n",
				e, source, strerror(e));
		(void)fclose(i);
		return RET_ERRNO(e);
	}
	if( fclose(i) != 0 ) {
		int e = errno;
		fprintf(stderr, "Error %d reading %s: %s\n",
				e, source, strerror(e));
		return RET_ERRNO(e);
	}
	return RET_OK;
}

void modification_printaspatch(FILE *f, const struct modification *m) {
	const struct modification *p, *q, *r;

	if( m == NULL )
		return;
	assert( m->previous == NULL );
	/* go to the end, as we have to print it backwards */
	p = m;
	while( p->next != NULL ) {
		assert( p->next->previous == p );
		p = p->next;
	}
	/* then print, possibly merging things */
	while( p != NULL ) {
		int start, oldcount, newcount;
		start = p->oldlinestart;
		oldcount = p->oldlinecount;
		newcount = p->newlinecount;

		if( p->next != NULL )
			assert( start + oldcount <= p->next->oldlinestart );

		r = p;
		for( q = p->previous ;
		     q != NULL && q->oldlinestart + q->oldlinecount == start ;
		     q = q->previous ) {
			oldcount += q->oldlinecount;
			start = q->oldlinestart;
			newcount += q->newlinecount;
			r = q;
		}
		if( newcount == 0 ) {
			assert( oldcount > 0 );
			if( oldcount == 1 )
				fprintf(f, "%dd\n", start);
			else
				fprintf(f, "%d,%dd\n", start, start + oldcount - 1);
		} else {
			if( oldcount == 0 )
				fprintf(f, "%da\n", start-1);
			else if( oldcount == 1 )
				fprintf(f, "%dc\n", start);
			else
				fprintf(f, "%d,%dc\n", start, start + oldcount - 1);
			while( r != p->next ) {
				if( r->len > 0 )
					fwrite(r->content, r->len, 1, f);
				newcount -= r->newlinecount;
				r = r->next;
			}
			assert( newcount == 0 );
			fputs(".\n", f);
		}
		p = q;
	}
}