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 43typedef 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. */ 50struct 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 68struct diffstart { 69 LIST_HEAD(, editcmd) dhead; 70}; 71 72static int diff_geteditcmd(struct editcmd *, char *); 73static int diff_copyln(struct editcmd *, lineno_t); 74static int diff_ignoreln(struct editcmd *, lineno_t); 75static void diff_write(struct editcmd *, void *, size_t); 76static int diff_insert_edit(struct diffstart *, struct editcmd *); 77static void diff_free(struct diffstart *); 78 79int 80diff_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 */ 164static int 165diff_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 */ 211static int 212diff_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 238static void 239diff_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 */ 254int 255diff_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. */ 354static int 355diff_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". */ 388static int 389diff_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". */ 405static int 406diff_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. */ 421static void 422diff_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} 438