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