diff options
Diffstat (limited to 'rredpatch.c')
-rw-r--r-- | rredpatch.c | 772 |
1 files changed, 772 insertions, 0 deletions
diff --git a/rredpatch.c b/rredpatch.c new file mode 100644 index 0000000..a59bc49 --- /dev/null +++ b/rredpatch.c @@ -0,0 +1,772 @@ +/* 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 <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 *modification_dup(const struct modification *p) { + struct modification *first = NULL, *last = NULL; + + for (; p != NULL ; p = p->next) { + struct modification *m = NEW(struct modification); + + if (FAILEDTOALLOC(m)) { + modification_freelist(first); + return NULL; + } + *m = *p; + m->next = NULL; + m->previous = last; + if (last == NULL) + first = m; + else + m->previous->next = m; + last = m; + } + return first; +} + +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 fd; + + fd = open(filename, O_NOCTTY|O_RDONLY); + if (fd < 0) { + int err = errno; + fprintf(stderr, +"Error %d opening '%s' for reading: %s\n", err, filename, strerror(err)); + return RET_ERRNO(err); + } + return patch_loadfd(filename, fd, length, patch_p); + +} + +retvalue patch_loadfd(const char *filename, int fd, 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 = zNEW(struct rred_patch); + if (FAILEDTOALLOC(patch)) { + (void)close(fd); + return RET_ERROR_OOM; + } + patch->fd = fd; + 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 = zNEW(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 = zNEW(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(void *f, const struct modification *m, void write_func(const void *, size_t, void *)) { + const struct modification *p, *q, *r; + char line[30]; + int len; + + 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) + len = snprintf(line, sizeof(line), "%dd\n", + start); + else + len = snprintf(line, sizeof(line), "%d,%dd\n", + start, start + oldcount - 1); + } else { + if (oldcount == 0) + len = snprintf(line, sizeof(line), "%da\n", + start - 1); + else if (oldcount == 1) + len = snprintf(line, sizeof(line), "%dc\n", + start); + else + len = snprintf(line, sizeof(line), "%d,%dc\n", + start, start + oldcount - 1); + } + assert (len < (int)sizeof(line)); + write_func(line, len, f); + if (newcount != 0) { + while (r != p->next) { + if (r->len > 0) + write_func(r->content, r->len, f); + newcount -= r->newlinecount; + r = r->next; + } + assert (newcount == 0); + write_func(".\n", 2, f); + } + p = q; + } +} + +/* make sure a patch is not empty and does not only add lines at the start, + * to work around some problems in apt */ + +retvalue modification_addstuff(const char *source, struct modification **patch_p, char **line_p) { + struct modification **pp, *n, *m = NULL; + char *line = NULL; size_t bufsize = 0; + ssize_t got; + FILE *i; + long lineno = 0; + + pp = patch_p; + /* check if this only adds things at the start and count how many */ + while (*pp != NULL) { + m = *pp; + if (m->oldlinecount > 0 || m->oldlinestart > 1) { + *line_p = NULL; + return RET_OK; + } + lineno += m->newlinecount; + pp = &(*pp)->next; + } + /* not get the next line and claim it was changed */ + 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); + } + do { + got = getline(&line, &bufsize, i); + } while (got >= 0 && lineno-- > 0); + if (got < 0) { + int e = errno; + + /* You should have made sure the old file is not empty */ + fprintf(stderr, "Error %d reading '%s': %s\n", + e, source, strerror(e)); + (void)fclose(i); + return RET_ERRNO(e); + } + (void)fclose(i); + + n = NEW(struct modification); + if (FAILEDTOALLOC(n)) + return RET_ERROR_OOM; + *pp = n; + n->next = NULL; + n->previous = m; + n->oldlinestart = 1; + n->oldlinecount = 1; + n->newlinecount = 1; + n->len = got; + n->content = line; + *line_p = line; + return RET_OK; +} + |