usr.bin/csup/diff.c

   1 /*-
   2  * Copyright (c) 2003-2006, Maxime Henrion <mux@FreeBSD.org>
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions
   7  * are met:
   8  * 1. Redistributions of source code must retain the above copyright
   9  *    notice, this list of conditions and the following disclaimer.
  10  * 2. Redistributions in binary form must reproduce the above copyright
  11  *    notice, this list of conditions and the following disclaimer in the
  12  *    documentation and/or other materials provided with the distribution.
  13  *
  14  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  15  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  17  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  18  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  19  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  20  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  21  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  22  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  23  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  24  * SUCH DAMAGE.
  25  *
  26  * $FreeBSD$
  27  */
  28
  29 #include <sys/limits.h>
  30
  31 #include <assert.h>
  32 #include <err.h>
  33 #include <errno.h>
  34 #include <stdio.h>
  35 #include <stdlib.h>
  36 #include <string.h>
  37
  38 #include "diff.h"
  39 #include "keyword.h"
  40 #include "misc.h"
  41 #include "stream.h"
  42 #include "queue.h"
  43
  44 typedef long lineno_t;
  45
  46 #define EC_ADD  0
  47 #define EC_DEL  1
  48 #define MAXKEY  LONG_MAX
  49
  50 /* Editing command and state. */
  51 struct editcmd {
  52         int cmd;
  53         long key;
  54         int havetext;
  55         int offset;
  56         lineno_t where;
  57         lineno_t count;
  58         lineno_t lasta;
  59         lineno_t lastd;
  60         lineno_t editline;
  61         /* For convenience. */
  62         struct keyword *keyword;
  63         struct diffinfo *di;
  64         struct stream *orig;
  65         struct stream *dest;
  66         LIST_ENTRY(editcmd) next;
  67 };
  68
  69 struct diffstart {
  70         LIST_HEAD(, editcmd) dhead;
  71 };
  72
  73 static int      diff_geteditcmd(struct editcmd *, char *);
  74 static int      diff_copyln(struct editcmd *, lineno_t);
  75 static int      diff_ignoreln(struct editcmd *, lineno_t);
  76 static void     diff_write(struct editcmd *, void *, size_t);
  77 static int      diff_insert_edit(struct diffstart *, struct editcmd *);
  78 static void     diff_free(struct diffstart *);
  79
  80 int
  81 diff_apply(struct stream *rd, struct stream *orig, struct stream *dest,
  82     struct keyword *keyword, struct diffinfo *di, int comode)
  83 {
  84         struct editcmd ec;
  85         lineno_t i;
  86         size_t size;
  87         char *line;
  88         int empty, error, noeol;
  89
  90         memset(&ec, 0, sizeof(ec));
  91         empty = 0;
  92         noeol = 0;
  93         ec.di = di;
  94         ec.keyword = keyword;
  95         ec.orig = orig;
  96         ec.dest = dest;
  97         line = stream_getln(rd, NULL);
  98         while (line != NULL && strcmp(line, ".") != 0 &&
  99             strcmp(line, ".+") != 0) {
 100                 /*
 101                  * The server sends an empty line and then terminates
 102                  * with .+ for forced (and thus empty) commits.
 103                  */
 104                 if (*line == '\0') {
 105                         if (empty)
 106                                 return (-1);
 107                         empty = 1;
 108                         line = stream_getln(rd, NULL);
 109                         continue;
 110                 }
 111                 error = diff_geteditcmd(&ec, line);
 112                 if (error)
 113                         return (-1);
 114
 115                 if (ec.cmd == EC_ADD) {
 116                         error = diff_copyln(&ec, ec.where);
 117                         if (error)
 118                                 return (-1);
 119                         for (i = 0; i < ec.count; i++) {
 120                                 line = stream_getln(rd, &size);
 121                                 if (line == NULL)
 122                                         return (-1);
 123                                 if (comode && line[0] == '.') {
 124                                         line++;
 125                                         size--;
 126                                 }
 127                                 diff_write(&ec, line, size);
 128                         }
 129                 } else {
 130                         assert(ec.cmd == EC_DEL);
 131                         error = diff_copyln(&ec, ec.where - 1);
 132                         if (error)
 133                                 return (-1);
 134                         for (i = 0; i < ec.count; i++) {
 135                                 line = stream_getln(orig, NULL);
 136                                 if (line == NULL)
 137                                         return (-1);
 138                                 ec.editline++;
 139                         }
 140                 }
 141                 line = stream_getln(rd, NULL);
 142         }
 143         if (comode && line == NULL)
 144                 return (-1);
 145         /* If we got ".+", there's no ending newline. */
 146         if (comode && strcmp(line, ".+") == 0 && !empty)
 147                 noeol = 1;
 148         ec.where = 0;
 149         while ((line = stream_getln(orig, &size)) != NULL)
 150                 diff_write(&ec, line, size);
 151         stream_flush(dest);
 152         if (noeol) {
 153                 error = stream_truncate_rel(dest, -1);
 154                 if (error) {
 155                         warn("stream_truncate_rel");
 156                         return (-1);
 157                 }
 158         }
 159         return (0);
 160 }
 161
 162 /*
 163  * Reverse a diff using the same algorithm as in cvsup.
 164  */
 165 static int
 166 diff_write_reverse(struct stream *dest, struct diffstart *ds)
 167 {
 168         struct editcmd *ec, *nextec;
 169         long editline, endline, firstoutputlinedeleted;
 170         long num_added, num_deleted, startline;
 171         int num;
 172
 173         nextec = LIST_FIRST(&ds->dhead);
 174         editline = 0;
 175         num = 0;
 176         while (nextec != NULL) {
 177                 ec = nextec;
 178                 nextec = LIST_NEXT(nextec, next);
 179                 if (nextec == NULL)
 180                         break;
 181                 num++;
 182                 num_deleted = 0;
 183                 if (ec->havetext)
 184                         num_deleted = ec->count;
 185                 num_added = num_deleted + nextec->offset - ec->offset;
 186                 if (num_deleted > 0) {
 187                         firstoutputlinedeleted = ec->key - num_deleted + 1;
 188                         stream_printf(dest, "d%ld %ld\n", firstoutputlinedeleted,
 189                             num_deleted);
 190                         if (num_added <= 0)
 191                                 continue;
 192                 }
 193                 if (num_added > 0) {
 194                         stream_printf(dest, "a%ld %ld\n", ec->key, num_added);
 195                         startline = ec->key - num_deleted + 1 + ec->offset;
 196                         endline = startline + num_added - 1;
 197
 198                         /* Copy lines from original file. First ignore some. */
 199                         ec->editline = editline;
 200                         diff_ignoreln(ec,  startline - 1);
 201                         diff_copyln(ec, endline);
 202                         editline = ec->editline;
 203                 }
 204         }
 205         return (0);
 206 }
 207
 208 /*
 209  * Insert a diff into the list sorted on key. Should perhaps use quicker
 210  * algorithms than insertion sort, but do this for now.
 211  */
 212 static int
 213 diff_insert_edit(struct diffstart *ds, struct editcmd *ec)
 214 {
 215         struct editcmd *curec;
 216
 217         if (ec == NULL)
 218                 return (0);
 219
 220         if (LIST_EMPTY(&ds->dhead)) {
 221                 LIST_INSERT_HEAD(&ds->dhead, ec, next);
 222                 return (0);
 223         }
 224
 225         /* Insertion sort based on key. */
 226         LIST_FOREACH(curec, &ds->dhead, next) {
 227                 if (ec->key < curec->key) {
 228                         LIST_INSERT_BEFORE(curec, ec, next);
 229                         return (0);
 230                 }
 231                 if (LIST_NEXT(curec, next) == NULL)
 232                         break;
 233         }
 234         /* Just insert it after. */
 235         LIST_INSERT_AFTER(curec, ec, next);
 236         return (0);
 237 }
 238
 239 static void
 240 diff_free(struct diffstart *ds)
 241 {
 242         struct editcmd *ec;
 243
 244         while(!LIST_EMPTY(&ds->dhead)) {
 245                 ec = LIST_FIRST(&ds->dhead);
 246                 LIST_REMOVE(ec, next);
 247                 free(ec);
 248         }
 249 }
 250
 251 /*
 252  * Write the reverse diff from the diff in rd, and original file into
 253  * destination. This algorithm is the same as used in cvsup.
 254  */
 255 int
 256 diff_reverse(struct stream *rd, struct stream *orig, struct stream *dest,
 257     struct keyword *keyword, struct diffinfo *di)
 258 {
 259         struct diffstart ds;
 260         struct editcmd ec, *addec, *delec;
 261         lineno_t i;
 262         char *line;
 263         int error, offset;
 264
 265         memset(&ec, 0, sizeof(ec));
 266         ec.orig = orig;
 267         ec.dest = dest;
 268         ec.keyword = keyword;
 269         ec.di = di;
 270         addec = NULL;
 271         delec = NULL;
 272         ec.havetext = 0;
 273         offset = 0;
 274         LIST_INIT(&ds.dhead);
 275
 276         /* Start with next since we need it. */
 277         line = stream_getln(rd, NULL);
 278         /* First we build up the list of diffs from input. */
 279         while (line != NULL) {
 280                 error = diff_geteditcmd(&ec, line);
 281                 if (error)
 282                         break;
 283                 if (ec.cmd == EC_ADD) {
 284                         addec = xmalloc(sizeof(struct editcmd));
 285                         *addec = ec;
 286                         addec->havetext = 1;
 287                         /* Ignore the lines we was supposed to add. */
 288                         for (i = 0; i < ec.count; i++) {
 289                                 line = stream_getln(rd, NULL);
 290                                 if (line == NULL)
 291                                         return (-1);
 292                         }
 293
 294                         /* Get the next diff command if we have one. */
 295                         addec->key = addec->where + addec->count - offset;
 296                         if (delec != NULL &&
 297                             delec->key == addec->key - addec->count) {
 298                                 delec->key = addec->key;
 299                                 delec->havetext = addec->havetext;
 300                                 delec->count = addec->count;
 301                                 diff_insert_edit(&ds, delec);
 302                                 free(addec);
 303                                 delec = NULL;
 304                                 addec = NULL;
 305                         } else {
 306                                 if (delec != NULL) {
 307                                         diff_insert_edit(&ds, delec);
 308                                 }
 309                                 delec = NULL;
 310                                 addec->offset = offset;
 311                                 diff_insert_edit(&ds, addec);
 312                                 addec = NULL;
 313                         }
 314                         offset -= ec.count;
 315                 } else if (ec.cmd == EC_DEL) {
 316                         if (delec != NULL) {
 317                                 /* Update offset to our next. */
 318                                 diff_insert_edit(&ds, delec);
 319                                 delec = NULL;
 320                         }
 321                         delec = xmalloc(sizeof(struct editcmd));
 322                         *delec = ec;
 323                         delec->key = delec->where - 1 - offset;
 324                         delec->offset = offset;
 325                         delec->count = 0;
 326                         delec->havetext = 0;
 327                         /* Important to use the count we had before reset.*/
 328                         offset += ec.count;
 329                 }
 330                 line = stream_getln(rd, NULL);
 331         }
 332
 333         while (line != NULL)
 334                 line = stream_getln(rd, NULL);
 335         if (delec != NULL) {
 336                 diff_insert_edit(&ds, delec);
 337                 delec = NULL;
 338         }
 339
 340         addec = xmalloc(sizeof(struct editcmd));
 341         /* Should be filesize, but we set it to max value. */
 342         addec->key = MAXKEY;
 343         addec->offset = offset;
 344         addec->havetext = 0;
 345         addec->count = 0;
 346         diff_insert_edit(&ds, addec);
 347         addec = NULL;
 348         diff_write_reverse(dest, &ds);
 349         diff_free(&ds);
 350         stream_flush(dest);
 351         return (0);
 352 }
 353
 354 /* Get an editing command from the diff. */
 355 static int
 356 diff_geteditcmd(struct editcmd *ec, char *line)
 357 {
 358         char *end;
 359
 360         if (line[0] == 'a')
 361                 ec->cmd = EC_ADD;
 362         else if (line[0] == 'd')
 363                 ec->cmd = EC_DEL;
 364         else
 365                 return (-1);
 366         errno = 0;
 367         ec->where = strtol(line + 1, &end, 10);
 368         if (errno || ec->where < 0 || *end != ' ')
 369                 return (-1);
 370         line = end + 1;
 371         errno = 0;
 372         ec->count = strtol(line, &end, 10);
 373         if (errno || ec->count <= 0 || *end != '\0')
 374                 return (-1);
 375         if (ec->cmd == EC_ADD) {
 376                 if (ec->where < ec->lasta)
 377                         return (-1);
 378                 ec->lasta = ec->where + 1;
 379         } else {
 380                 if (ec->where < ec->lasta || ec->where < ec->lastd)
 381                         return (-1);
 382                 ec->lasta = ec->where;
 383                 ec->lastd = ec->where + ec->count;
 384         }
 385         return (0);
 386 }
 387
 388 /* Copy lines from the original version of the file up to line "to". */
 389 static int
 390 diff_copyln(struct editcmd *ec, lineno_t to)
 391 {
 392         size_t size;
 393         char *line;
 394
 395         while (ec->editline < to) {
 396                 line = stream_getln(ec->orig, &size);
 397                 if (line == NULL)
 398                         return (-1);
 399                 ec->editline++;
 400                 diff_write(ec, line, size);
 401         }
 402         return (0);
 403 }
 404
 405 /* Ignore lines from the original version of the file up to line "to". */
 406 static int
 407 diff_ignoreln(struct editcmd *ec, lineno_t to)
 408 {
 409         size_t size;
 410         char *line;
 411
 412         while (ec->editline < to) {
 413                 line = stream_getln(ec->orig, &size);
 414                 if (line == NULL)
 415                         return (-1);
 416                 ec->editline++;
 417         }
 418         return (0);
 419 }
 420
 421 /* Write a new line to the file, expanding RCS keywords appropriately. */
 422 static void
 423 diff_write(struct editcmd *ec, void *buf, size_t size)
 424 {
 425         size_t newsize;
 426         char *line, *newline;
 427         int ret;
 428
 429         line = buf;
 430         ret = keyword_expand(ec->keyword, ec->di, line, size,
 431             &newline, &newsize);
 432         if (ret) {
 433                 stream_write(ec->dest, newline, newsize);
 434                 free(newline);
 435         } else {
 436                 stream_write(ec->dest, buf, size);
 437         }
 438 }