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