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