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 44typedef 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. */ 51struct 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 69struct diffstart { 70 LIST_HEAD(, editcmd) dhead; 71}; 72 73static int diff_geteditcmd(struct editcmd *, char *); 74static int diff_copyln(struct editcmd *, lineno_t); 75static int diff_ignoreln(struct editcmd *, lineno_t); 76static void diff_write(struct editcmd *, void *, size_t); 77static int diff_insert_edit(struct diffstart *, struct editcmd *); 78static void diff_free(struct diffstart *); 79 80int 81diff_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 */ 165static int 166diff_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 */ 212static int 213diff_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 239static void 240diff_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 */ 255int 256diff_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. */ 355static int 356diff_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". */ 389static int 390diff_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". */ 406static int 407diff_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. */ 422static void 423diff_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} 439