1 /* $OpenBSD: undo.c,v 1.58 2016/09/05 08:10:58 lum Exp $ */ 2 /* 3 * This file is in the public domain 4 */ 5 6 #include <sys/queue.h> 7 #include <signal.h> 8 #include <stdio.h> 9 #include <stdlib.h> 10 #include <string.h> 11 12 #include "def.h" 13 #include "kbd.h" 14 15 #define MAX_FREE_RECORDS 32 16 17 /* 18 * Local variables 19 */ 20 static struct undoq undo_free; 21 static int undo_free_num; 22 static int boundary_flag = TRUE; 23 static int undo_enable_flag = TRUE; 24 25 /* 26 * Local functions 27 */ 28 static int find_dot(struct line *, int); 29 static int find_lo(int, struct line **, int *, int *); 30 static struct undo_rec *new_undo_record(void); 31 static int drop_oldest_undo_record(void); 32 33 /* 34 * find_dot, find_lo() 35 * 36 * Find an absolute dot in the buffer from a line/offset pair, and vice-versa. 37 * 38 * Since lines can be deleted while they are referenced by undo record, we 39 * need to have an absolute dot to have something reliable. 40 */ 41 static int 42 find_dot(struct line *lp, int off) 43 { 44 int count = 0; 45 struct line *p; 46 47 for (p = curbp->b_headp; p != lp; p = lforw(p)) { 48 if (count != 0) { 49 if (p == curbp->b_headp) { 50 dobeep(); 51 ewprintf("Error: Undo stuff called with a" 52 "nonexistent line"); 53 return (FALSE); 54 } 55 } 56 count += llength(p) + 1; 57 } 58 count += off; 59 60 return (count); 61 } 62 63 static int 64 find_lo(int pos, struct line **olp, int *offset, int *lnum) 65 { 66 struct line *p; 67 int lineno; 68 69 p = curbp->b_headp; 70 lineno = 0; 71 while (pos > llength(p)) { 72 pos -= llength(p) + 1; 73 if ((p = lforw(p)) == curbp->b_headp) { 74 *olp = NULL; 75 *offset = 0; 76 return (FALSE); 77 } 78 lineno++; 79 } 80 *olp = p; 81 *offset = pos; 82 *lnum = lineno; 83 84 return (TRUE); 85 } 86 87 static struct undo_rec * 88 new_undo_record(void) 89 { 90 struct undo_rec *rec; 91 92 rec = TAILQ_FIRST(&undo_free); 93 if (rec != NULL) { 94 /* Remove it from the free-list */ 95 TAILQ_REMOVE(&undo_free, rec, next); 96 undo_free_num--; 97 } else { 98 if ((rec = malloc(sizeof(*rec))) == NULL) 99 panic("Out of memory in undo code (record)"); 100 } 101 memset(rec, 0, sizeof(struct undo_rec)); 102 103 return (rec); 104 } 105 106 void 107 free_undo_record(struct undo_rec *rec) 108 { 109 static int initialised = 0; 110 111 /* 112 * On the first run, do initialisation of the free list. 113 */ 114 if (initialised == 0) { 115 TAILQ_INIT(&undo_free); 116 initialised = 1; 117 } 118 free(rec->content); 119 rec->content = NULL; 120 if (undo_free_num >= MAX_FREE_RECORDS) { 121 free(rec); 122 return; 123 } 124 undo_free_num++; 125 126 TAILQ_INSERT_HEAD(&undo_free, rec, next); 127 } 128 129 /* 130 * Drop the oldest undo record in our list. Return 1 if we could remove it, 131 * 0 if the undo list was empty. 132 */ 133 static int 134 drop_oldest_undo_record(void) 135 { 136 struct undo_rec *rec; 137 138 rec = TAILQ_LAST(&curbp->b_undo, undoq); 139 if (rec != NULL) { 140 undo_free_num--; 141 TAILQ_REMOVE(&curbp->b_undo, rec, next); 142 free_undo_record(rec); 143 return (1); 144 } 145 return (0); 146 } 147 148 static int 149 lastrectype(void) 150 { 151 struct undo_rec *rec; 152 153 if ((rec = TAILQ_FIRST(&curbp->b_undo)) != NULL) 154 return (rec->type); 155 return (0); 156 } 157 158 /* 159 * Returns TRUE if undo is enabled, FALSE otherwise. 160 */ 161 int 162 undo_enabled(void) 163 { 164 return (undo_enable_flag); 165 } 166 167 /* 168 * undo_enable: toggle undo_enable. 169 * Returns the previous value of the flag. 170 */ 171 int 172 undo_enable(int f, int n) 173 { 174 int pon = undo_enable_flag; 175 176 if (f & (FFARG | FFRAND)) 177 undo_enable_flag = n > 0; 178 else 179 undo_enable_flag = !undo_enable_flag; 180 181 if (!(f & FFRAND)) 182 ewprintf("Undo %sabled", undo_enable_flag ? "en" : "dis"); 183 184 return (pon); 185 } 186 187 /* 188 * If undo is enabled, then: 189 * Toggle undo boundary recording. 190 * If called with an argument, (n > 0) => enable. Otherwise disable. 191 * In either case, add an undo boundary 192 * If undo is disabled, this function has no effect. 193 */ 194 int 195 undo_boundary_enable(int f, int n) 196 { 197 int bon = boundary_flag; 198 199 if (!undo_enable_flag) 200 return (FALSE); 201 202 undo_add_boundary(FFRAND, 1); 203 204 if (f & (FFARG | FFRAND)) 205 boundary_flag = n > 0; 206 else 207 boundary_flag = !boundary_flag; 208 209 if (!(f & FFRAND)) 210 ewprintf("Undo boundaries %sabled", 211 boundary_flag ? "en" : "dis"); 212 213 return (bon); 214 } 215 216 /* 217 * Record an undo boundary, unless boundary_flag == FALSE. 218 * Does nothing if previous undo entry is already a boundary or 'modified' flag. 219 */ 220 int 221 undo_add_boundary(int f, int n) 222 { 223 struct undo_rec *rec; 224 int last; 225 226 if (boundary_flag == FALSE) 227 return (FALSE); 228 229 last = lastrectype(); 230 if (last == BOUNDARY || last == MODIFIED) 231 return (TRUE); 232 233 rec = new_undo_record(); 234 rec->type = BOUNDARY; 235 236 TAILQ_INSERT_HEAD(&curbp->b_undo, rec, next); 237 238 return (TRUE); 239 } 240 241 /* 242 * Record an undo "modified" boundary 243 */ 244 void 245 undo_add_modified(void) 246 { 247 struct undo_rec *rec, *trec; 248 249 TAILQ_FOREACH_SAFE(rec, &curbp->b_undo, next, trec) 250 if (rec->type == MODIFIED) { 251 TAILQ_REMOVE(&curbp->b_undo, rec, next); 252 free_undo_record(rec); 253 } 254 255 rec = new_undo_record(); 256 rec->type = MODIFIED; 257 258 TAILQ_INSERT_HEAD(&curbp->b_undo, rec, next); 259 260 return; 261 } 262 263 int 264 undo_add_insert(struct line *lp, int offset, int size) 265 { 266 struct region reg; 267 struct undo_rec *rec; 268 int pos; 269 270 if (!undo_enable_flag) 271 return (TRUE); 272 273 memset(®, 0, sizeof(reg)); 274 reg.r_linep = lp; 275 reg.r_offset = offset; 276 reg.r_size = size; 277 278 pos = find_dot(lp, offset); 279 280 /* 281 * We try to reuse the last undo record to `compress' things. 282 */ 283 rec = TAILQ_FIRST(&curbp->b_undo); 284 if (rec != NULL && rec->type == INSERT) { 285 if (rec->pos + rec->region.r_size == pos) { 286 rec->region.r_size += reg.r_size; 287 return (TRUE); 288 } 289 } 290 291 /* 292 * We couldn't reuse the last undo record, so prepare a new one. 293 */ 294 rec = new_undo_record(); 295 rec->pos = pos; 296 rec->type = INSERT; 297 memmove(&rec->region, ®, sizeof(struct region)); 298 rec->content = NULL; 299 300 undo_add_boundary(FFRAND, 1); 301 302 TAILQ_INSERT_HEAD(&curbp->b_undo, rec, next); 303 304 return (TRUE); 305 } 306 307 /* 308 * This of course must be done _before_ the actual deletion is done. 309 */ 310 int 311 undo_add_delete(struct line *lp, int offset, int size, int isreg) 312 { 313 struct region reg; 314 struct undo_rec *rec; 315 int pos; 316 317 if (!undo_enable_flag) 318 return (TRUE); 319 320 memset(®, 0, sizeof(reg)); 321 reg.r_linep = lp; 322 reg.r_offset = offset; 323 reg.r_size = size; 324 325 pos = find_dot(lp, offset); 326 327 if (offset == llength(lp)) /* if it's a newline... */ 328 undo_add_boundary(FFRAND, 1); 329 else if ((rec = TAILQ_FIRST(&curbp->b_undo)) != NULL) { 330 /* 331 * Separate this command from the previous one if we're not 332 * just before the previous record... 333 */ 334 if (!isreg && rec->type == DELETE) { 335 if (rec->pos - rec->region.r_size != pos) 336 undo_add_boundary(FFRAND, 1); 337 } 338 } 339 rec = new_undo_record(); 340 rec->pos = pos; 341 if (isreg) 342 rec->type = DELREG; 343 else 344 rec->type = DELETE; 345 memmove(&rec->region, ®, sizeof(struct region)); 346 do { 347 rec->content = malloc(reg.r_size + 1); 348 } while ((rec->content == NULL) && drop_oldest_undo_record()); 349 350 if (rec->content == NULL) 351 panic("Out of memory"); 352 353 region_get_data(®, rec->content, reg.r_size); 354 355 if (isreg || lastrectype() != DELETE) 356 undo_add_boundary(FFRAND, 1); 357 358 TAILQ_INSERT_HEAD(&curbp->b_undo, rec, next); 359 360 return (TRUE); 361 } 362 363 /* 364 * This of course must be called before the change takes place. 365 */ 366 int 367 undo_add_change(struct line *lp, int offset, int size) 368 { 369 if (!undo_enable_flag) 370 return (TRUE); 371 undo_add_boundary(FFRAND, 1); 372 boundary_flag = FALSE; 373 undo_add_delete(lp, offset, size, 0); 374 undo_add_insert(lp, offset, size); 375 boundary_flag = TRUE; 376 undo_add_boundary(FFRAND, 1); 377 378 return (TRUE); 379 } 380 381 /* 382 * Show the undo records for the current buffer in a new buffer. 383 */ 384 /* ARGSUSED */ 385 int 386 undo_dump(int f, int n) 387 { 388 struct undo_rec *rec; 389 struct buffer *bp; 390 struct mgwin *wp; 391 char buf[4096], tmp[1024]; 392 int num; 393 394 /* 395 * Prepare the buffer for insertion. 396 */ 397 if ((bp = bfind("*undo*", TRUE)) == NULL) 398 return (FALSE); 399 bp->b_flag |= BFREADONLY; 400 bclear(bp); 401 if ((wp = popbuf(bp, WNONE)) == NULL) 402 return (FALSE); 403 404 for (wp = wheadp; wp != NULL; wp = wp->w_wndp) { 405 if (wp->w_bufp == bp) { 406 wp->w_dotp = bp->b_headp; 407 wp->w_doto = 0; 408 } 409 } 410 411 num = 0; 412 TAILQ_FOREACH(rec, &curbp->b_undo, next) { 413 num++; 414 snprintf(buf, sizeof(buf), 415 "%d:\t %s at %d ", num, 416 (rec->type == DELETE) ? "DELETE": 417 (rec->type == DELREG) ? "DELREGION": 418 (rec->type == INSERT) ? "INSERT": 419 (rec->type == BOUNDARY) ? "----" : 420 (rec->type == MODIFIED) ? "MODIFIED": "UNKNOWN", 421 rec->pos); 422 423 if (rec->content) { 424 (void)strlcat(buf, "\"", sizeof(buf)); 425 snprintf(tmp, sizeof(tmp), "%.*s", rec->region.r_size, 426 rec->content); 427 (void)strlcat(buf, tmp, sizeof(buf)); 428 (void)strlcat(buf, "\"", sizeof(buf)); 429 } 430 snprintf(tmp, sizeof(tmp), " [%d]", rec->region.r_size); 431 if (strlcat(buf, tmp, sizeof(buf)) >= sizeof(buf)) { 432 dobeep(); 433 ewprintf("Undo record too large. Aborted."); 434 return (FALSE); 435 } 436 addlinef(bp, "%s", buf); 437 } 438 for (wp = wheadp; wp != NULL; wp = wp->w_wndp) { 439 if (wp->w_bufp == bp) { 440 wp->w_dotline = num+1; 441 wp->w_rflag |= WFFULL; 442 } 443 } 444 return (TRUE); 445 } 446 447 /* 448 * After the user did action1, then action2, then action3: 449 * 450 * [action3] <--- Undoptr 451 * [action2] 452 * [action1] 453 * ------ 454 * [undo] 455 * 456 * After undo: 457 * 458 * [undo of action3] 459 * [action2] <--- Undoptr 460 * [action1] 461 * ------ 462 * [undo] 463 * 464 * After another undo: 465 * 466 * 467 * [undo of action2] 468 * [undo of action3] 469 * [action1] <--- Undoptr 470 * ------ 471 * [undo] 472 * 473 * Note that the "undo of actionX" have no special meaning. Only when 474 * we undo a deletion, the insertion will be recorded just as if it 475 * was typed on the keyboard. Resulting in the inverse operation being 476 * saved in the list. 477 * 478 * If undoptr reaches the bottom of the list, or if we moved between 479 * two undo actions, we make it point back at the topmost record. This is 480 * how we handle redoing. 481 */ 482 /* ARGSUSED */ 483 int 484 undo(int f, int n) 485 { 486 struct undo_rec *ptr, *nptr; 487 int done, rval; 488 struct line *lp; 489 int offset, save; 490 static int nulled = FALSE; 491 int lineno; 492 493 if (n < 0) 494 return (FALSE); 495 496 ptr = curbp->b_undoptr; 497 498 /* first invocation, make ptr point back to the top of the list */ 499 if ((ptr == NULL && nulled == TRUE) || rptcount == 0) { 500 ptr = TAILQ_FIRST(&curbp->b_undo); 501 nulled = TRUE; 502 } 503 504 rval = TRUE; 505 while (n--) { 506 /* if we have a spurious boundary, free it and move on.... */ 507 while (ptr && ptr->type == BOUNDARY) { 508 nptr = TAILQ_NEXT(ptr, next); 509 TAILQ_REMOVE(&curbp->b_undo, ptr, next); 510 free_undo_record(ptr); 511 ptr = nptr; 512 } 513 /* 514 * Ptr is NULL, but on the next run, it will point to the 515 * top again, redoing all stuff done in the buffer since 516 * its creation. 517 */ 518 if (ptr == NULL) { 519 dobeep(); 520 ewprintf("No further undo information"); 521 rval = FALSE; 522 nulled = TRUE; 523 break; 524 } 525 nulled = FALSE; 526 527 /* 528 * Loop while we don't get a boundary specifying we've 529 * finished the current action... 530 */ 531 532 undo_add_boundary(FFRAND, 1); 533 534 save = boundary_flag; 535 boundary_flag = FALSE; 536 537 done = 0; 538 do { 539 /* 540 * Move to where this has to apply 541 * 542 * Boundaries (and the modified flag) are put as 543 * position 0 (to save lookup time in find_dot) 544 * so we must not move there... 545 */ 546 if (ptr->type != BOUNDARY && ptr->type != MODIFIED) { 547 if (find_lo(ptr->pos, &lp, 548 &offset, &lineno) == FALSE) { 549 dobeep(); 550 ewprintf("Internal error in Undo!"); 551 rval = FALSE; 552 break; 553 } 554 curwp->w_dotp = lp; 555 curwp->w_doto = offset; 556 curwp->w_markline = curwp->w_dotline; 557 curwp->w_dotline = lineno; 558 } 559 560 /* 561 * Do operation^-1 562 */ 563 switch (ptr->type) { 564 case INSERT: 565 ldelete(ptr->region.r_size, KNONE); 566 break; 567 case DELETE: 568 lp = curwp->w_dotp; 569 offset = curwp->w_doto; 570 region_put_data(ptr->content, 571 ptr->region.r_size); 572 curwp->w_dotp = lp; 573 curwp->w_doto = offset; 574 break; 575 case DELREG: 576 region_put_data(ptr->content, 577 ptr->region.r_size); 578 break; 579 case BOUNDARY: 580 done = 1; 581 break; 582 case MODIFIED: 583 curbp->b_flag &= ~BFCHG; 584 break; 585 default: 586 break; 587 } 588 589 /* And move to next record */ 590 ptr = TAILQ_NEXT(ptr, next); 591 } while (ptr != NULL && !done); 592 593 boundary_flag = save; 594 undo_add_boundary(FFRAND, 1); 595 596 ewprintf("Undo!"); 597 } 598 599 curbp->b_undoptr = ptr; 600 601 return (rval); 602 } 603