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$ 27156230Smux */ 28156230Smux 29156230Smux#include <assert.h> 30156230Smux#include <err.h> 31156230Smux#include <errno.h> 32225844Screes#include <limits.h> 33186781Slulf#include <stdio.h> 34156230Smux#include <stdlib.h> 35156230Smux#include <string.h> 36156230Smux 37156230Smux#include "diff.h" 38156230Smux#include "keyword.h" 39156230Smux#include "misc.h" 40156230Smux#include "stream.h" 41186781Slulf#include "queue.h" 42156230Smux 43156230Smuxtypedef long lineno_t; 44156230Smux 45156230Smux#define EC_ADD 0 46156230Smux#define EC_DEL 1 47186781Slulf#define MAXKEY LONG_MAX 48156230Smux 49156230Smux/* Editing command and state. */ 50156230Smuxstruct editcmd { 51156230Smux int cmd; 52186781Slulf long key; 53186781Slulf int havetext; 54186781Slulf int offset; 55156230Smux lineno_t where; 56156230Smux lineno_t count; 57156230Smux lineno_t lasta; 58156230Smux lineno_t lastd; 59156230Smux lineno_t editline; 60156230Smux /* For convenience. */ 61156230Smux struct keyword *keyword; 62156230Smux struct diffinfo *di; 63156230Smux struct stream *orig; 64156230Smux struct stream *dest; 65186781Slulf LIST_ENTRY(editcmd) next; 66156230Smux}; 67156230Smux 68186781Slulfstruct diffstart { 69186781Slulf LIST_HEAD(, editcmd) dhead; 70186781Slulf}; 71186781Slulf 72156230Smuxstatic int diff_geteditcmd(struct editcmd *, char *); 73156230Smuxstatic int diff_copyln(struct editcmd *, lineno_t); 74186781Slulfstatic int diff_ignoreln(struct editcmd *, lineno_t); 75156230Smuxstatic void diff_write(struct editcmd *, void *, size_t); 76186781Slulfstatic int diff_insert_edit(struct diffstart *, struct editcmd *); 77186781Slulfstatic void diff_free(struct diffstart *); 78156230Smux 79156230Smuxint 80156230Smuxdiff_apply(struct stream *rd, struct stream *orig, struct stream *dest, 81186781Slulf struct keyword *keyword, struct diffinfo *di, int comode) 82156230Smux{ 83156230Smux struct editcmd ec; 84156230Smux lineno_t i; 85186781Slulf size_t size; 86156230Smux char *line; 87156230Smux int empty, error, noeol; 88156230Smux 89156230Smux memset(&ec, 0, sizeof(ec)); 90156230Smux empty = 0; 91156230Smux noeol = 0; 92156230Smux ec.di = di; 93156230Smux ec.keyword = keyword; 94156230Smux ec.orig = orig; 95156230Smux ec.dest = dest; 96156230Smux line = stream_getln(rd, NULL); 97156230Smux while (line != NULL && strcmp(line, ".") != 0 && 98156230Smux strcmp(line, ".+") != 0) { 99156230Smux /* 100156230Smux * The server sends an empty line and then terminates 101156230Smux * with .+ for forced (and thus empty) commits. 102156230Smux */ 103156230Smux if (*line == '\0') { 104156230Smux if (empty) 105156230Smux return (-1); 106156230Smux empty = 1; 107156230Smux line = stream_getln(rd, NULL); 108156230Smux continue; 109156230Smux } 110156230Smux error = diff_geteditcmd(&ec, line); 111156230Smux if (error) 112156230Smux return (-1); 113156230Smux 114156230Smux if (ec.cmd == EC_ADD) { 115156230Smux error = diff_copyln(&ec, ec.where); 116156230Smux if (error) 117156230Smux return (-1); 118156230Smux for (i = 0; i < ec.count; i++) { 119156230Smux line = stream_getln(rd, &size); 120156230Smux if (line == NULL) 121156230Smux return (-1); 122186781Slulf if (comode && line[0] == '.') { 123156230Smux line++; 124156230Smux size--; 125156230Smux } 126156230Smux diff_write(&ec, line, size); 127156230Smux } 128156230Smux } else { 129156230Smux assert(ec.cmd == EC_DEL); 130156230Smux error = diff_copyln(&ec, ec.where - 1); 131156230Smux if (error) 132156230Smux return (-1); 133156230Smux for (i = 0; i < ec.count; i++) { 134156230Smux line = stream_getln(orig, NULL); 135156230Smux if (line == NULL) 136156230Smux return (-1); 137156230Smux ec.editline++; 138156230Smux } 139156230Smux } 140156230Smux line = stream_getln(rd, NULL); 141156230Smux } 142186781Slulf if (comode && line == NULL) 143156230Smux return (-1); 144156230Smux /* If we got ".+", there's no ending newline. */ 145186781Slulf if (comode && strcmp(line, ".+") == 0 && !empty) 146156230Smux noeol = 1; 147156230Smux ec.where = 0; 148156230Smux while ((line = stream_getln(orig, &size)) != NULL) 149156230Smux diff_write(&ec, line, size); 150156230Smux stream_flush(dest); 151156230Smux if (noeol) { 152156230Smux error = stream_truncate_rel(dest, -1); 153156230Smux if (error) { 154156230Smux warn("stream_truncate_rel"); 155156230Smux return (-1); 156156230Smux } 157156230Smux } 158156230Smux return (0); 159156230Smux} 160156230Smux 161186781Slulf/* 162186781Slulf * Reverse a diff using the same algorithm as in cvsup. 163186781Slulf */ 164186781Slulfstatic int 165186781Slulfdiff_write_reverse(struct stream *dest, struct diffstart *ds) 166186781Slulf{ 167186781Slulf struct editcmd *ec, *nextec; 168186781Slulf long editline, endline, firstoutputlinedeleted; 169186781Slulf long num_added, num_deleted, startline; 170186781Slulf int num; 171186781Slulf 172186781Slulf nextec = LIST_FIRST(&ds->dhead); 173186781Slulf editline = 0; 174186781Slulf num = 0; 175186781Slulf while (nextec != NULL) { 176186781Slulf ec = nextec; 177186781Slulf nextec = LIST_NEXT(nextec, next); 178186781Slulf if (nextec == NULL) 179186781Slulf break; 180186781Slulf num++; 181186781Slulf num_deleted = 0; 182186781Slulf if (ec->havetext) 183186781Slulf num_deleted = ec->count; 184186781Slulf num_added = num_deleted + nextec->offset - ec->offset; 185186781Slulf if (num_deleted > 0) { 186186781Slulf firstoutputlinedeleted = ec->key - num_deleted + 1; 187186781Slulf stream_printf(dest, "d%ld %ld\n", firstoutputlinedeleted, 188186781Slulf num_deleted); 189186781Slulf if (num_added <= 0) 190186781Slulf continue; 191186781Slulf } 192186781Slulf if (num_added > 0) { 193186781Slulf stream_printf(dest, "a%ld %ld\n", ec->key, num_added); 194186781Slulf startline = ec->key - num_deleted + 1 + ec->offset; 195186781Slulf endline = startline + num_added - 1; 196186781Slulf 197186781Slulf /* Copy lines from original file. First ignore some. */ 198186781Slulf ec->editline = editline; 199186781Slulf diff_ignoreln(ec, startline - 1); 200186781Slulf diff_copyln(ec, endline); 201186781Slulf editline = ec->editline; 202186781Slulf } 203186781Slulf } 204186781Slulf return (0); 205186781Slulf} 206186781Slulf 207186781Slulf/* 208186781Slulf * Insert a diff into the list sorted on key. Should perhaps use quicker 209186781Slulf * algorithms than insertion sort, but do this for now. 210186781Slulf */ 211186781Slulfstatic int 212186781Slulfdiff_insert_edit(struct diffstart *ds, struct editcmd *ec) 213186781Slulf{ 214186781Slulf struct editcmd *curec; 215186781Slulf 216186781Slulf if (ec == NULL) 217186781Slulf return (0); 218186781Slulf 219186781Slulf if (LIST_EMPTY(&ds->dhead)) { 220186781Slulf LIST_INSERT_HEAD(&ds->dhead, ec, next); 221186781Slulf return (0); 222186781Slulf } 223186781Slulf 224186781Slulf /* Insertion sort based on key. */ 225186781Slulf LIST_FOREACH(curec, &ds->dhead, next) { 226186781Slulf if (ec->key < curec->key) { 227186781Slulf LIST_INSERT_BEFORE(curec, ec, next); 228186781Slulf return (0); 229186781Slulf } 230186781Slulf if (LIST_NEXT(curec, next) == NULL) 231186781Slulf break; 232186781Slulf } 233186781Slulf /* Just insert it after. */ 234186781Slulf LIST_INSERT_AFTER(curec, ec, next); 235186781Slulf return (0); 236186781Slulf} 237186781Slulf 238186781Slulfstatic void 239186781Slulfdiff_free(struct diffstart *ds) 240186781Slulf{ 241186781Slulf struct editcmd *ec; 242186781Slulf 243186781Slulf while(!LIST_EMPTY(&ds->dhead)) { 244186781Slulf ec = LIST_FIRST(&ds->dhead); 245186781Slulf LIST_REMOVE(ec, next); 246186781Slulf free(ec); 247186781Slulf } 248186781Slulf} 249186781Slulf 250186781Slulf/* 251186781Slulf * Write the reverse diff from the diff in rd, and original file into 252186781Slulf * destination. This algorithm is the same as used in cvsup. 253186781Slulf */ 254186781Slulfint 255186781Slulfdiff_reverse(struct stream *rd, struct stream *orig, struct stream *dest, 256186781Slulf struct keyword *keyword, struct diffinfo *di) 257186781Slulf{ 258186781Slulf struct diffstart ds; 259186781Slulf struct editcmd ec, *addec, *delec; 260186781Slulf lineno_t i; 261186781Slulf char *line; 262186781Slulf int error, offset; 263186781Slulf 264186781Slulf memset(&ec, 0, sizeof(ec)); 265186781Slulf ec.orig = orig; 266186781Slulf ec.dest = dest; 267186781Slulf ec.keyword = keyword; 268186781Slulf ec.di = di; 269186781Slulf addec = NULL; 270186781Slulf delec = NULL; 271186781Slulf ec.havetext = 0; 272186781Slulf offset = 0; 273186781Slulf LIST_INIT(&ds.dhead); 274186781Slulf 275186781Slulf /* Start with next since we need it. */ 276186781Slulf line = stream_getln(rd, NULL); 277186781Slulf /* First we build up the list of diffs from input. */ 278186781Slulf while (line != NULL) { 279186781Slulf error = diff_geteditcmd(&ec, line); 280186781Slulf if (error) 281186781Slulf break; 282186781Slulf if (ec.cmd == EC_ADD) { 283186781Slulf addec = xmalloc(sizeof(struct editcmd)); 284186781Slulf *addec = ec; 285186781Slulf addec->havetext = 1; 286186781Slulf /* Ignore the lines we was supposed to add. */ 287186781Slulf for (i = 0; i < ec.count; i++) { 288186781Slulf line = stream_getln(rd, NULL); 289186781Slulf if (line == NULL) 290186781Slulf return (-1); 291186781Slulf } 292186781Slulf 293186781Slulf /* Get the next diff command if we have one. */ 294186781Slulf addec->key = addec->where + addec->count - offset; 295186781Slulf if (delec != NULL && 296186781Slulf delec->key == addec->key - addec->count) { 297186781Slulf delec->key = addec->key; 298186781Slulf delec->havetext = addec->havetext; 299186781Slulf delec->count = addec->count; 300186781Slulf diff_insert_edit(&ds, delec); 301186781Slulf free(addec); 302186781Slulf delec = NULL; 303186781Slulf addec = NULL; 304186781Slulf } else { 305186781Slulf if (delec != NULL) { 306186781Slulf diff_insert_edit(&ds, delec); 307186781Slulf } 308186781Slulf delec = NULL; 309186781Slulf addec->offset = offset; 310186781Slulf diff_insert_edit(&ds, addec); 311186781Slulf addec = NULL; 312186781Slulf } 313186781Slulf offset -= ec.count; 314186781Slulf } else if (ec.cmd == EC_DEL) { 315186781Slulf if (delec != NULL) { 316186781Slulf /* Update offset to our next. */ 317186781Slulf diff_insert_edit(&ds, delec); 318186781Slulf delec = NULL; 319186781Slulf } 320186781Slulf delec = xmalloc(sizeof(struct editcmd)); 321186781Slulf *delec = ec; 322186781Slulf delec->key = delec->where - 1 - offset; 323186781Slulf delec->offset = offset; 324186781Slulf delec->count = 0; 325186781Slulf delec->havetext = 0; 326186781Slulf /* Important to use the count we had before reset.*/ 327186781Slulf offset += ec.count; 328186781Slulf } 329186781Slulf line = stream_getln(rd, NULL); 330186781Slulf } 331186781Slulf 332186781Slulf while (line != NULL) 333186781Slulf line = stream_getln(rd, NULL); 334186781Slulf if (delec != NULL) { 335186781Slulf diff_insert_edit(&ds, delec); 336186781Slulf delec = NULL; 337186781Slulf } 338186781Slulf 339186781Slulf addec = xmalloc(sizeof(struct editcmd)); 340186781Slulf /* Should be filesize, but we set it to max value. */ 341186781Slulf addec->key = MAXKEY; 342186781Slulf addec->offset = offset; 343186781Slulf addec->havetext = 0; 344186781Slulf addec->count = 0; 345186781Slulf diff_insert_edit(&ds, addec); 346186781Slulf addec = NULL; 347186781Slulf diff_write_reverse(dest, &ds); 348186781Slulf diff_free(&ds); 349186781Slulf stream_flush(dest); 350186781Slulf return (0); 351186781Slulf} 352186781Slulf 353156230Smux/* Get an editing command from the diff. */ 354156230Smuxstatic int 355156230Smuxdiff_geteditcmd(struct editcmd *ec, char *line) 356156230Smux{ 357156230Smux char *end; 358156230Smux 359156230Smux if (line[0] == 'a') 360156230Smux ec->cmd = EC_ADD; 361156230Smux else if (line[0] == 'd') 362156230Smux ec->cmd = EC_DEL; 363156230Smux else 364156230Smux return (-1); 365156230Smux errno = 0; 366156230Smux ec->where = strtol(line + 1, &end, 10); 367156230Smux if (errno || ec->where < 0 || *end != ' ') 368156230Smux return (-1); 369156230Smux line = end + 1; 370156230Smux errno = 0; 371156230Smux ec->count = strtol(line, &end, 10); 372156230Smux if (errno || ec->count <= 0 || *end != '\0') 373156230Smux return (-1); 374156230Smux if (ec->cmd == EC_ADD) { 375156230Smux if (ec->where < ec->lasta) 376156230Smux return (-1); 377156230Smux ec->lasta = ec->where + 1; 378156230Smux } else { 379156230Smux if (ec->where < ec->lasta || ec->where < ec->lastd) 380156230Smux return (-1); 381156230Smux ec->lasta = ec->where; 382156230Smux ec->lastd = ec->where + ec->count; 383156230Smux } 384156230Smux return (0); 385156230Smux} 386156230Smux 387156230Smux/* Copy lines from the original version of the file up to line "to". */ 388156230Smuxstatic int 389156230Smuxdiff_copyln(struct editcmd *ec, lineno_t to) 390156230Smux{ 391186781Slulf size_t size; 392156230Smux char *line; 393156230Smux 394156230Smux while (ec->editline < to) { 395156230Smux line = stream_getln(ec->orig, &size); 396156230Smux if (line == NULL) 397156230Smux return (-1); 398156230Smux ec->editline++; 399156230Smux diff_write(ec, line, size); 400156230Smux } 401156230Smux return (0); 402156230Smux} 403156230Smux 404186781Slulf/* Ignore lines from the original version of the file up to line "to". */ 405186781Slulfstatic int 406186781Slulfdiff_ignoreln(struct editcmd *ec, lineno_t to) 407186781Slulf{ 408186781Slulf size_t size; 409186781Slulf char *line; 410186781Slulf 411186781Slulf while (ec->editline < to) { 412186781Slulf line = stream_getln(ec->orig, &size); 413186781Slulf if (line == NULL) 414186781Slulf return (-1); 415186781Slulf ec->editline++; 416186781Slulf } 417186781Slulf return (0); 418186781Slulf} 419186781Slulf 420156230Smux/* Write a new line to the file, expanding RCS keywords appropriately. */ 421156230Smuxstatic void 422156230Smuxdiff_write(struct editcmd *ec, void *buf, size_t size) 423156230Smux{ 424186781Slulf size_t newsize; 425156230Smux char *line, *newline; 426156230Smux int ret; 427156230Smux 428156230Smux line = buf; 429156230Smux ret = keyword_expand(ec->keyword, ec->di, line, size, 430156230Smux &newline, &newsize); 431156230Smux if (ret) { 432156230Smux stream_write(ec->dest, newline, newsize); 433156230Smux free(newline); 434156230Smux } else { 435156230Smux stream_write(ec->dest, buf, size); 436156230Smux } 437156230Smux} 438