diff.c revision 186781
1156230Smux/*- 2156230Smux * Copyright (c) 2003-2006, Maxime Henrion <mux@FreeBSD.org> 3156230Smux * All rights reserved. 4156230Smux * 5156230Smux * Redistribution and use in source and binary forms, with or without 6156230Smux * modification, are permitted provided that the following conditions 7156230Smux * are met: 8156230Smux * 1. Redistributions of source code must retain the above copyright 9156230Smux * notice, this list of conditions and the following disclaimer. 10156230Smux * 2. Redistributions in binary form must reproduce the above copyright 11156230Smux * notice, this list of conditions and the following disclaimer in the 12156230Smux * documentation and/or other materials provided with the distribution. 13156230Smux * 14156230Smux * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 15156230Smux * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 16156230Smux * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 17156230Smux * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 18156230Smux * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 19156230Smux * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 20156230Smux * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 21156230Smux * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 22156230Smux * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 23156230Smux * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 24156230Smux * SUCH DAMAGE. 25156230Smux * 26156230Smux * $FreeBSD: head/contrib/csup/diff.c 186781 2009-01-05 15:18:16Z lulf $ 27156230Smux */ 28156230Smux 29186781Slulf#include <sys/limits.h> 30186781Slulf 31156230Smux#include <assert.h> 32156230Smux#include <err.h> 33156230Smux#include <errno.h> 34186781Slulf#include <stdio.h> 35156230Smux#include <stdlib.h> 36156230Smux#include <string.h> 37156230Smux 38156230Smux#include "diff.h" 39156230Smux#include "keyword.h" 40156230Smux#include "misc.h" 41156230Smux#include "stream.h" 42186781Slulf#include "queue.h" 43156230Smux 44156230Smuxtypedef long lineno_t; 45156230Smux 46156230Smux#define EC_ADD 0 47156230Smux#define EC_DEL 1 48186781Slulf#define MAXKEY LONG_MAX 49156230Smux 50156230Smux/* Editing command and state. */ 51156230Smuxstruct editcmd { 52156230Smux int cmd; 53186781Slulf long key; 54186781Slulf int havetext; 55186781Slulf int offset; 56156230Smux lineno_t where; 57156230Smux lineno_t count; 58156230Smux lineno_t lasta; 59156230Smux lineno_t lastd; 60156230Smux lineno_t editline; 61156230Smux /* For convenience. */ 62156230Smux struct keyword *keyword; 63156230Smux struct diffinfo *di; 64156230Smux struct stream *orig; 65156230Smux struct stream *dest; 66186781Slulf LIST_ENTRY(editcmd) next; 67156230Smux}; 68156230Smux 69186781Slulfstruct diffstart { 70186781Slulf LIST_HEAD(, editcmd) dhead; 71186781Slulf}; 72186781Slulf 73156230Smuxstatic int diff_geteditcmd(struct editcmd *, char *); 74156230Smuxstatic int diff_copyln(struct editcmd *, lineno_t); 75186781Slulfstatic int diff_ignoreln(struct editcmd *, lineno_t); 76156230Smuxstatic void diff_write(struct editcmd *, void *, size_t); 77186781Slulfstatic int diff_insert_edit(struct diffstart *, struct editcmd *); 78186781Slulfstatic void diff_free(struct diffstart *); 79156230Smux 80156230Smuxint 81156230Smuxdiff_apply(struct stream *rd, struct stream *orig, struct stream *dest, 82186781Slulf struct keyword *keyword, struct diffinfo *di, int comode) 83156230Smux{ 84156230Smux struct editcmd ec; 85156230Smux lineno_t i; 86186781Slulf size_t size; 87156230Smux char *line; 88156230Smux int empty, error, noeol; 89156230Smux 90156230Smux memset(&ec, 0, sizeof(ec)); 91156230Smux empty = 0; 92156230Smux noeol = 0; 93156230Smux ec.di = di; 94156230Smux ec.keyword = keyword; 95156230Smux ec.orig = orig; 96156230Smux ec.dest = dest; 97156230Smux line = stream_getln(rd, NULL); 98156230Smux while (line != NULL && strcmp(line, ".") != 0 && 99156230Smux strcmp(line, ".+") != 0) { 100156230Smux /* 101156230Smux * The server sends an empty line and then terminates 102156230Smux * with .+ for forced (and thus empty) commits. 103156230Smux */ 104156230Smux if (*line == '\0') { 105156230Smux if (empty) 106156230Smux return (-1); 107156230Smux empty = 1; 108156230Smux line = stream_getln(rd, NULL); 109156230Smux continue; 110156230Smux } 111156230Smux error = diff_geteditcmd(&ec, line); 112156230Smux if (error) 113156230Smux return (-1); 114156230Smux 115156230Smux if (ec.cmd == EC_ADD) { 116156230Smux error = diff_copyln(&ec, ec.where); 117156230Smux if (error) 118156230Smux return (-1); 119156230Smux for (i = 0; i < ec.count; i++) { 120156230Smux line = stream_getln(rd, &size); 121156230Smux if (line == NULL) 122156230Smux return (-1); 123186781Slulf if (comode && line[0] == '.') { 124156230Smux line++; 125156230Smux size--; 126156230Smux } 127156230Smux diff_write(&ec, line, size); 128156230Smux } 129156230Smux } else { 130156230Smux assert(ec.cmd == EC_DEL); 131156230Smux error = diff_copyln(&ec, ec.where - 1); 132156230Smux if (error) 133156230Smux return (-1); 134156230Smux for (i = 0; i < ec.count; i++) { 135156230Smux line = stream_getln(orig, NULL); 136156230Smux if (line == NULL) 137156230Smux return (-1); 138156230Smux ec.editline++; 139156230Smux } 140156230Smux } 141156230Smux line = stream_getln(rd, NULL); 142156230Smux } 143186781Slulf if (comode && line == NULL) 144156230Smux return (-1); 145156230Smux /* If we got ".+", there's no ending newline. */ 146186781Slulf if (comode && strcmp(line, ".+") == 0 && !empty) 147156230Smux noeol = 1; 148156230Smux ec.where = 0; 149156230Smux while ((line = stream_getln(orig, &size)) != NULL) 150156230Smux diff_write(&ec, line, size); 151156230Smux stream_flush(dest); 152156230Smux if (noeol) { 153156230Smux error = stream_truncate_rel(dest, -1); 154156230Smux if (error) { 155156230Smux warn("stream_truncate_rel"); 156156230Smux return (-1); 157156230Smux } 158156230Smux } 159156230Smux return (0); 160156230Smux} 161156230Smux 162186781Slulf/* 163186781Slulf * Reverse a diff using the same algorithm as in cvsup. 164186781Slulf */ 165186781Slulfstatic int 166186781Slulfdiff_write_reverse(struct stream *dest, struct diffstart *ds) 167186781Slulf{ 168186781Slulf struct editcmd *ec, *nextec; 169186781Slulf long editline, endline, firstoutputlinedeleted; 170186781Slulf long num_added, num_deleted, startline; 171186781Slulf int num; 172186781Slulf 173186781Slulf nextec = LIST_FIRST(&ds->dhead); 174186781Slulf editline = 0; 175186781Slulf num = 0; 176186781Slulf while (nextec != NULL) { 177186781Slulf ec = nextec; 178186781Slulf nextec = LIST_NEXT(nextec, next); 179186781Slulf if (nextec == NULL) 180186781Slulf break; 181186781Slulf num++; 182186781Slulf num_deleted = 0; 183186781Slulf if (ec->havetext) 184186781Slulf num_deleted = ec->count; 185186781Slulf num_added = num_deleted + nextec->offset - ec->offset; 186186781Slulf if (num_deleted > 0) { 187186781Slulf firstoutputlinedeleted = ec->key - num_deleted + 1; 188186781Slulf stream_printf(dest, "d%ld %ld\n", firstoutputlinedeleted, 189186781Slulf num_deleted); 190186781Slulf if (num_added <= 0) 191186781Slulf continue; 192186781Slulf } 193186781Slulf if (num_added > 0) { 194186781Slulf stream_printf(dest, "a%ld %ld\n", ec->key, num_added); 195186781Slulf startline = ec->key - num_deleted + 1 + ec->offset; 196186781Slulf endline = startline + num_added - 1; 197186781Slulf 198186781Slulf /* Copy lines from original file. First ignore some. */ 199186781Slulf ec->editline = editline; 200186781Slulf diff_ignoreln(ec, startline - 1); 201186781Slulf diff_copyln(ec, endline); 202186781Slulf editline = ec->editline; 203186781Slulf } 204186781Slulf } 205186781Slulf return (0); 206186781Slulf} 207186781Slulf 208186781Slulf/* 209186781Slulf * Insert a diff into the list sorted on key. Should perhaps use quicker 210186781Slulf * algorithms than insertion sort, but do this for now. 211186781Slulf */ 212186781Slulfstatic int 213186781Slulfdiff_insert_edit(struct diffstart *ds, struct editcmd *ec) 214186781Slulf{ 215186781Slulf struct editcmd *curec; 216186781Slulf 217186781Slulf if (ec == NULL) 218186781Slulf return (0); 219186781Slulf 220186781Slulf if (LIST_EMPTY(&ds->dhead)) { 221186781Slulf LIST_INSERT_HEAD(&ds->dhead, ec, next); 222186781Slulf return (0); 223186781Slulf } 224186781Slulf 225186781Slulf /* Insertion sort based on key. */ 226186781Slulf LIST_FOREACH(curec, &ds->dhead, next) { 227186781Slulf if (ec->key < curec->key) { 228186781Slulf LIST_INSERT_BEFORE(curec, ec, next); 229186781Slulf return (0); 230186781Slulf } 231186781Slulf if (LIST_NEXT(curec, next) == NULL) 232186781Slulf break; 233186781Slulf } 234186781Slulf /* Just insert it after. */ 235186781Slulf LIST_INSERT_AFTER(curec, ec, next); 236186781Slulf return (0); 237186781Slulf} 238186781Slulf 239186781Slulfstatic void 240186781Slulfdiff_free(struct diffstart *ds) 241186781Slulf{ 242186781Slulf struct editcmd *ec; 243186781Slulf 244186781Slulf while(!LIST_EMPTY(&ds->dhead)) { 245186781Slulf ec = LIST_FIRST(&ds->dhead); 246186781Slulf LIST_REMOVE(ec, next); 247186781Slulf free(ec); 248186781Slulf } 249186781Slulf} 250186781Slulf 251186781Slulf/* 252186781Slulf * Write the reverse diff from the diff in rd, and original file into 253186781Slulf * destination. This algorithm is the same as used in cvsup. 254186781Slulf */ 255186781Slulfint 256186781Slulfdiff_reverse(struct stream *rd, struct stream *orig, struct stream *dest, 257186781Slulf struct keyword *keyword, struct diffinfo *di) 258186781Slulf{ 259186781Slulf struct diffstart ds; 260186781Slulf struct editcmd ec, *addec, *delec; 261186781Slulf lineno_t i; 262186781Slulf char *line; 263186781Slulf int error, offset; 264186781Slulf 265186781Slulf memset(&ec, 0, sizeof(ec)); 266186781Slulf ec.orig = orig; 267186781Slulf ec.dest = dest; 268186781Slulf ec.keyword = keyword; 269186781Slulf ec.di = di; 270186781Slulf addec = NULL; 271186781Slulf delec = NULL; 272186781Slulf ec.havetext = 0; 273186781Slulf offset = 0; 274186781Slulf LIST_INIT(&ds.dhead); 275186781Slulf 276186781Slulf /* Start with next since we need it. */ 277186781Slulf line = stream_getln(rd, NULL); 278186781Slulf /* First we build up the list of diffs from input. */ 279186781Slulf while (line != NULL) { 280186781Slulf error = diff_geteditcmd(&ec, line); 281186781Slulf if (error) 282186781Slulf break; 283186781Slulf if (ec.cmd == EC_ADD) { 284186781Slulf addec = xmalloc(sizeof(struct editcmd)); 285186781Slulf *addec = ec; 286186781Slulf addec->havetext = 1; 287186781Slulf /* Ignore the lines we was supposed to add. */ 288186781Slulf for (i = 0; i < ec.count; i++) { 289186781Slulf line = stream_getln(rd, NULL); 290186781Slulf if (line == NULL) 291186781Slulf return (-1); 292186781Slulf } 293186781Slulf 294186781Slulf /* Get the next diff command if we have one. */ 295186781Slulf addec->key = addec->where + addec->count - offset; 296186781Slulf if (delec != NULL && 297186781Slulf delec->key == addec->key - addec->count) { 298186781Slulf delec->key = addec->key; 299186781Slulf delec->havetext = addec->havetext; 300186781Slulf delec->count = addec->count; 301186781Slulf diff_insert_edit(&ds, delec); 302186781Slulf free(addec); 303186781Slulf delec = NULL; 304186781Slulf addec = NULL; 305186781Slulf } else { 306186781Slulf if (delec != NULL) { 307186781Slulf diff_insert_edit(&ds, delec); 308186781Slulf } 309186781Slulf delec = NULL; 310186781Slulf addec->offset = offset; 311186781Slulf diff_insert_edit(&ds, addec); 312186781Slulf addec = NULL; 313186781Slulf } 314186781Slulf offset -= ec.count; 315186781Slulf } else if (ec.cmd == EC_DEL) { 316186781Slulf if (delec != NULL) { 317186781Slulf /* Update offset to our next. */ 318186781Slulf diff_insert_edit(&ds, delec); 319186781Slulf delec = NULL; 320186781Slulf } 321186781Slulf delec = xmalloc(sizeof(struct editcmd)); 322186781Slulf *delec = ec; 323186781Slulf delec->key = delec->where - 1 - offset; 324186781Slulf delec->offset = offset; 325186781Slulf delec->count = 0; 326186781Slulf delec->havetext = 0; 327186781Slulf /* Important to use the count we had before reset.*/ 328186781Slulf offset += ec.count; 329186781Slulf } 330186781Slulf line = stream_getln(rd, NULL); 331186781Slulf } 332186781Slulf 333186781Slulf while (line != NULL) 334186781Slulf line = stream_getln(rd, NULL); 335186781Slulf if (delec != NULL) { 336186781Slulf diff_insert_edit(&ds, delec); 337186781Slulf delec = NULL; 338186781Slulf } 339186781Slulf 340186781Slulf addec = xmalloc(sizeof(struct editcmd)); 341186781Slulf /* Should be filesize, but we set it to max value. */ 342186781Slulf addec->key = MAXKEY; 343186781Slulf addec->offset = offset; 344186781Slulf addec->havetext = 0; 345186781Slulf addec->count = 0; 346186781Slulf diff_insert_edit(&ds, addec); 347186781Slulf addec = NULL; 348186781Slulf diff_write_reverse(dest, &ds); 349186781Slulf diff_free(&ds); 350186781Slulf stream_flush(dest); 351186781Slulf return (0); 352186781Slulf} 353186781Slulf 354156230Smux/* Get an editing command from the diff. */ 355156230Smuxstatic int 356156230Smuxdiff_geteditcmd(struct editcmd *ec, char *line) 357156230Smux{ 358156230Smux char *end; 359156230Smux 360156230Smux if (line[0] == 'a') 361156230Smux ec->cmd = EC_ADD; 362156230Smux else if (line[0] == 'd') 363156230Smux ec->cmd = EC_DEL; 364156230Smux else 365156230Smux return (-1); 366156230Smux errno = 0; 367156230Smux ec->where = strtol(line + 1, &end, 10); 368156230Smux if (errno || ec->where < 0 || *end != ' ') 369156230Smux return (-1); 370156230Smux line = end + 1; 371156230Smux errno = 0; 372156230Smux ec->count = strtol(line, &end, 10); 373156230Smux if (errno || ec->count <= 0 || *end != '\0') 374156230Smux return (-1); 375156230Smux if (ec->cmd == EC_ADD) { 376156230Smux if (ec->where < ec->lasta) 377156230Smux return (-1); 378156230Smux ec->lasta = ec->where + 1; 379156230Smux } else { 380156230Smux if (ec->where < ec->lasta || ec->where < ec->lastd) 381156230Smux return (-1); 382156230Smux ec->lasta = ec->where; 383156230Smux ec->lastd = ec->where + ec->count; 384156230Smux } 385156230Smux return (0); 386156230Smux} 387156230Smux 388156230Smux/* Copy lines from the original version of the file up to line "to". */ 389156230Smuxstatic int 390156230Smuxdiff_copyln(struct editcmd *ec, lineno_t to) 391156230Smux{ 392186781Slulf size_t size; 393156230Smux char *line; 394156230Smux 395156230Smux while (ec->editline < to) { 396156230Smux line = stream_getln(ec->orig, &size); 397156230Smux if (line == NULL) 398156230Smux return (-1); 399156230Smux ec->editline++; 400156230Smux diff_write(ec, line, size); 401156230Smux } 402156230Smux return (0); 403156230Smux} 404156230Smux 405186781Slulf/* Ignore lines from the original version of the file up to line "to". */ 406186781Slulfstatic int 407186781Slulfdiff_ignoreln(struct editcmd *ec, lineno_t to) 408186781Slulf{ 409186781Slulf size_t size; 410186781Slulf char *line; 411186781Slulf 412186781Slulf while (ec->editline < to) { 413186781Slulf line = stream_getln(ec->orig, &size); 414186781Slulf if (line == NULL) 415186781Slulf return (-1); 416186781Slulf ec->editline++; 417186781Slulf } 418186781Slulf return (0); 419186781Slulf} 420186781Slulf 421156230Smux/* Write a new line to the file, expanding RCS keywords appropriately. */ 422156230Smuxstatic void 423156230Smuxdiff_write(struct editcmd *ec, void *buf, size_t size) 424156230Smux{ 425186781Slulf size_t newsize; 426156230Smux char *line, *newline; 427156230Smux int ret; 428156230Smux 429156230Smux line = buf; 430156230Smux ret = keyword_expand(ec->keyword, ec->di, line, size, 431156230Smux &newline, &newsize); 432156230Smux if (ret) { 433156230Smux stream_write(ec->dest, newline, newsize); 434156230Smux free(newline); 435156230Smux } else { 436156230Smux stream_write(ec->dest, buf, size); 437156230Smux } 438156230Smux} 439