1 /* $OpenBSD: undo.c,v 1.59 2023/03/08 04:43:11 guenther 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
find_dot(struct line * lp,int off)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
find_lo(int pos,struct line ** olp,int * offset,int * lnum)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 *
new_undo_record(void)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
free_undo_record(struct undo_rec * rec)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
drop_oldest_undo_record(void)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
lastrectype(void)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
undo_enabled(void)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
undo_enable(int f,int n)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
undo_boundary_enable(int f,int n)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
undo_add_boundary(int f,int n)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
undo_add_modified(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
undo_add_insert(struct line * lp,int offset,int size)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
undo_add_delete(struct line * lp,int offset,int size,int isreg)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
undo_add_change(struct line * lp,int offset,int size)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 int
undo_dump(int f,int n)385 undo_dump(int f, int n)
386 {
387 struct undo_rec *rec;
388 struct buffer *bp;
389 struct mgwin *wp;
390 char buf[4096], tmp[1024];
391 int num;
392
393 /*
394 * Prepare the buffer for insertion.
395 */
396 if ((bp = bfind("*undo*", TRUE)) == NULL)
397 return (FALSE);
398 bp->b_flag |= BFREADONLY;
399 bclear(bp);
400 if ((wp = popbuf(bp, WNONE)) == NULL)
401 return (FALSE);
402
403 for (wp = wheadp; wp != NULL; wp = wp->w_wndp) {
404 if (wp->w_bufp == bp) {
405 wp->w_dotp = bp->b_headp;
406 wp->w_doto = 0;
407 }
408 }
409
410 num = 0;
411 TAILQ_FOREACH(rec, &curbp->b_undo, next) {
412 num++;
413 snprintf(buf, sizeof(buf),
414 "%d:\t %s at %d ", num,
415 (rec->type == DELETE) ? "DELETE":
416 (rec->type == DELREG) ? "DELREGION":
417 (rec->type == INSERT) ? "INSERT":
418 (rec->type == BOUNDARY) ? "----" :
419 (rec->type == MODIFIED) ? "MODIFIED": "UNKNOWN",
420 rec->pos);
421
422 if (rec->content) {
423 (void)strlcat(buf, "\"", sizeof(buf));
424 snprintf(tmp, sizeof(tmp), "%.*s", rec->region.r_size,
425 rec->content);
426 (void)strlcat(buf, tmp, sizeof(buf));
427 (void)strlcat(buf, "\"", sizeof(buf));
428 }
429 snprintf(tmp, sizeof(tmp), " [%d]", rec->region.r_size);
430 if (strlcat(buf, tmp, sizeof(buf)) >= sizeof(buf)) {
431 dobeep();
432 ewprintf("Undo record too large. Aborted.");
433 return (FALSE);
434 }
435 addlinef(bp, "%s", buf);
436 }
437 for (wp = wheadp; wp != NULL; wp = wp->w_wndp) {
438 if (wp->w_bufp == bp) {
439 wp->w_dotline = num+1;
440 wp->w_rflag |= WFFULL;
441 }
442 }
443 return (TRUE);
444 }
445
446 /*
447 * After the user did action1, then action2, then action3:
448 *
449 * [action3] <--- Undoptr
450 * [action2]
451 * [action1]
452 * ------
453 * [undo]
454 *
455 * After undo:
456 *
457 * [undo of action3]
458 * [action2] <--- Undoptr
459 * [action1]
460 * ------
461 * [undo]
462 *
463 * After another undo:
464 *
465 *
466 * [undo of action2]
467 * [undo of action3]
468 * [action1] <--- Undoptr
469 * ------
470 * [undo]
471 *
472 * Note that the "undo of actionX" have no special meaning. Only when
473 * we undo a deletion, the insertion will be recorded just as if it
474 * was typed on the keyboard. Resulting in the inverse operation being
475 * saved in the list.
476 *
477 * If undoptr reaches the bottom of the list, or if we moved between
478 * two undo actions, we make it point back at the topmost record. This is
479 * how we handle redoing.
480 */
481 int
undo(int f,int n)482 undo(int f, int n)
483 {
484 struct undo_rec *ptr, *nptr;
485 int done, rval;
486 struct line *lp;
487 int offset, save;
488 static int nulled = FALSE;
489 int lineno;
490
491 if (n < 0)
492 return (FALSE);
493
494 ptr = curbp->b_undoptr;
495
496 /* first invocation, make ptr point back to the top of the list */
497 if ((ptr == NULL && nulled == TRUE) || rptcount == 0) {
498 ptr = TAILQ_FIRST(&curbp->b_undo);
499 nulled = TRUE;
500 }
501
502 rval = TRUE;
503 while (n--) {
504 /* if we have a spurious boundary, free it and move on.... */
505 while (ptr && ptr->type == BOUNDARY) {
506 nptr = TAILQ_NEXT(ptr, next);
507 TAILQ_REMOVE(&curbp->b_undo, ptr, next);
508 free_undo_record(ptr);
509 ptr = nptr;
510 }
511 /*
512 * Ptr is NULL, but on the next run, it will point to the
513 * top again, redoing all stuff done in the buffer since
514 * its creation.
515 */
516 if (ptr == NULL) {
517 dobeep();
518 ewprintf("No further undo information");
519 rval = FALSE;
520 nulled = TRUE;
521 break;
522 }
523 nulled = FALSE;
524
525 /*
526 * Loop while we don't get a boundary specifying we've
527 * finished the current action...
528 */
529
530 undo_add_boundary(FFRAND, 1);
531
532 save = boundary_flag;
533 boundary_flag = FALSE;
534
535 done = 0;
536 do {
537 /*
538 * Move to where this has to apply
539 *
540 * Boundaries (and the modified flag) are put as
541 * position 0 (to save lookup time in find_dot)
542 * so we must not move there...
543 */
544 if (ptr->type != BOUNDARY && ptr->type != MODIFIED) {
545 if (find_lo(ptr->pos, &lp,
546 &offset, &lineno) == FALSE) {
547 dobeep();
548 ewprintf("Internal error in Undo!");
549 rval = FALSE;
550 break;
551 }
552 curwp->w_dotp = lp;
553 curwp->w_doto = offset;
554 curwp->w_markline = curwp->w_dotline;
555 curwp->w_dotline = lineno;
556 }
557
558 /*
559 * Do operation^-1
560 */
561 switch (ptr->type) {
562 case INSERT:
563 ldelete(ptr->region.r_size, KNONE);
564 break;
565 case DELETE:
566 lp = curwp->w_dotp;
567 offset = curwp->w_doto;
568 region_put_data(ptr->content,
569 ptr->region.r_size);
570 curwp->w_dotp = lp;
571 curwp->w_doto = offset;
572 break;
573 case DELREG:
574 region_put_data(ptr->content,
575 ptr->region.r_size);
576 break;
577 case BOUNDARY:
578 done = 1;
579 break;
580 case MODIFIED:
581 curbp->b_flag &= ~BFCHG;
582 break;
583 default:
584 break;
585 }
586
587 /* And move to next record */
588 ptr = TAILQ_NEXT(ptr, next);
589 } while (ptr != NULL && !done);
590
591 boundary_flag = save;
592 undo_add_boundary(FFRAND, 1);
593
594 ewprintf("Undo!");
595 }
596
597 curbp->b_undoptr = ptr;
598
599 return (rval);
600 }
601