Annotation of src/usr.bin/mg/undo.c, Revision 1.14
1.14 ! vincent 1: /* $OpenBSD: undo.c,v 1.13 2002/08/22 23:28:19 deraadt Exp $ */
1.1 vincent 2: /*
1.10 vincent 3: * Copyright (c) 2002 Vincent Labrecque
4: * All rights reserved.
1.1 vincent 5: *
6: * Redistribution and use in source and binary forms, with or without
7: * modification, are permitted provided that the following conditions
8: * are met:
9: * 1. Redistributions of source code must retain the above copyright
10: * notice, this list of conditions and the following disclaimer.
11: * 2. Redistributions in binary form must reproduce the above copyright
12: * notice, this list of conditions and the following disclaimer in the
13: * documentation and/or other materials provided with the distribution.
14: *
15: * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
16: * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
17: * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
18: * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
19: * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
20: * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
21: * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
22: * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23: * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
24: * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25: */
26:
27: #include "def.h"
28: #include "kbd.h"
29:
30: #include <sys/queue.h>
31:
32: #define MAX_FREE_RECORDS 32
33:
34: /*
35: * Local variables
36: */
1.7 vincent 37: static LIST_HEAD(, undo_rec) undo_free;
38: static int undo_free_num;
1.12 vincent 39: static int nobound;
1.1 vincent 40:
41: /*
42: * Global variables
43: */
44: /*
1.9 vincent 45: * undo_disable_flag: Stop doing undo (useful when we know are
46: * going to deal with huge deletion/insertions
47: * that we don't plan to undo)
1.1 vincent 48: */
49: int undo_disable_flag;
50:
51: /*
52: * Local functions
53: */
1.9 vincent 54: static int find_absolute_dot(LINE *, int);
55: static int find_line_offset(int, LINE **, int *);
1.1 vincent 56: static struct undo_rec *new_undo_record(void);
57: static int drop_oldest_undo_record(void);
58:
1.9 vincent 59: /*
60: * find_{absolute_dot,line_offset}()
61: *
62: * Find an absolute dot in the buffer from a line/offset pair, and vice-versa.
63: *
1.13 deraadt 64: * Since lines can be deleted while they are referenced by undo record, we
1.9 vincent 65: * need to have an absolute dot to have something reliable.
66: */
67:
1.1 vincent 68: static int
1.9 vincent 69: find_absolute_dot(LINE *lp, int off)
1.1 vincent 70: {
71: int count = 0;
72: LINE *p;
73:
74: for (p = curwp->w_linep; p != lp; p = lforw(p)) {
75: if (count != 0) {
1.3 vincent 76: if (p == curwp->w_linep) {
1.1 vincent 77: ewprintf("Error: Undo stuff called with a"
1.9 vincent 78: "nonexistent line");
1.11 vincent 79: return (FALSE);
1.1 vincent 80: }
81: }
82: count += llength(p) + 1;
83: }
84: count += off;
85:
1.11 vincent 86: return (count);
1.1 vincent 87: }
88:
89: static int
1.9 vincent 90: find_line_offset(int pos, LINE **olp, int *offset)
1.1 vincent 91: {
92: LINE *p;
93:
94: p = curwp->w_linep;
1.9 vincent 95: while (pos > llength(p)) {
1.1 vincent 96: pos -= llength(p) + 1;
1.2 vincent 97: if ((p = lforw(p)) == curwp->w_linep) {
1.1 vincent 98: *olp = NULL;
99: *offset = 0;
1.11 vincent 100: return (FALSE);
1.1 vincent 101: }
102: }
103: *olp = p;
104: *offset = pos;
105:
1.11 vincent 106: return (TRUE);
1.1 vincent 107: }
108:
109: static struct undo_rec *
110: new_undo_record(void)
111: {
112: struct undo_rec *rec;
113:
114: rec = LIST_FIRST(&undo_free);
1.9 vincent 115: if (rec != NULL) {
1.1 vincent 116: LIST_REMOVE(rec, next); /* Remove it from the free-list */
1.9 vincent 117: undo_free_num--;
118: } else {
1.1 vincent 119: if ((rec = malloc(sizeof *rec)) == NULL)
120: panic("Out of memory in undo code (record)");
121: }
122: memset(rec, 0, sizeof(struct undo_rec));
1.9 vincent 123:
1.11 vincent 124: return (rec);
1.1 vincent 125: }
126:
1.7 vincent 127: void
1.1 vincent 128: free_undo_record(struct undo_rec *rec)
129: {
1.9 vincent 130: static int initialised = 0;
131:
132: /*
133: * On the first run, do initialisation of the free list.
134: */
135: if (initialised == 0) {
136: LIST_INIT(&undo_free);
137: initialised = 1;
138: }
1.1 vincent 139: if (rec->content != NULL) {
140: free(rec->content);
141: rec->content = NULL;
142: }
143: if (undo_free_num >= MAX_FREE_RECORDS) {
144: free(rec);
145: return;
146: }
147: undo_free_num++;
1.9 vincent 148:
1.1 vincent 149: LIST_INSERT_HEAD(&undo_free, rec, next);
150: }
151:
152: /*
153: * Drop the oldest undo record in our list. Return 1 if we could remove it,
154: * 0 if the undo list was empty
155: */
156: static int
157: drop_oldest_undo_record(void)
158: {
159: struct undo_rec *rec;
160:
1.9 vincent 161: rec = LIST_END(&curbp->b_undo);
1.1 vincent 162: if (rec != NULL) {
163: undo_free_num--;
1.9 vincent 164: LIST_REMOVE(rec, next);
1.1 vincent 165: free_undo_record(rec);
1.11 vincent 166: return (1);
1.1 vincent 167: }
1.11 vincent 168: return (0);
1.1 vincent 169: }
1.9 vincent 170:
171: static __inline__ int
172: last_was_boundary()
1.1 vincent 173: {
1.9 vincent 174: struct undo_rec *rec;
175:
176: if ((rec = LIST_FIRST(&curbp->b_undo)) != NULL &&
177: (rec->type == BOUNDARY))
1.11 vincent 178: return (1);
179: return (0);
1.1 vincent 180: }
181:
182: int
183: undo_enable(int on)
184: {
1.14 ! vincent 185: int pon = undo_disable_flag;
! 186: undo_disable_flag = (on == TRUE) ? 0 : 1;
! 187: return (pon ? FALSE : TRUE);
1.5 vincent 188: }
189:
190: int
1.9 vincent 191: undo_add_boundary(void)
1.5 vincent 192: {
193: struct undo_rec *rec;
194:
1.12 vincent 195: if (nobound)
196: return (TRUE);
197:
1.5 vincent 198: rec = new_undo_record();
1.9 vincent 199: rec->type = BOUNDARY;
1.5 vincent 200:
1.7 vincent 201: LIST_INSERT_HEAD(&curbp->b_undo, rec, next);
1.9 vincent 202:
1.11 vincent 203: return (TRUE);
1.1 vincent 204: }
205:
1.13 deraadt 206: /*
1.9 vincent 207: * If asocial is true, we arrange for this record to be let alone. forever.
208: * Yes, this is a bit of a hack...
209: */
1.1 vincent 210: int
1.9 vincent 211: undo_add_custom(int asocial,
212: int type, LINE *lp, int offset, void *content, int size)
1.1 vincent 213: {
214: struct undo_rec *rec;
215:
216: if (undo_disable_flag)
1.11 vincent 217: return (TRUE);
1.1 vincent 218: rec = new_undo_record();
1.9 vincent 219: if (lp != NULL)
220: rec->pos = find_absolute_dot(lp, offset);
221: else
222: rec->pos = 0;
223: rec->type = type;
224: rec->content = content;
225: rec->region.r_linep = lp;
226: rec->region.r_offset = offset;
227: rec->region.r_size = size;
1.1 vincent 228:
1.9 vincent 229: if (!last_was_boundary())
230: undo_add_boundary();
1.7 vincent 231: LIST_INSERT_HEAD(&curbp->b_undo, rec, next);
1.9 vincent 232: undo_add_boundary();
233: if (asocial) /* Add a second one */
234: undo_add_boundary();
235:
1.11 vincent 236: return (TRUE);
1.1 vincent 237: }
238:
239: int
240: undo_add_insert(LINE *lp, int offset, int size)
241: {
242: REGION reg;
243: struct undo_rec *rec;
1.9 vincent 244: int pos;
245:
1.1 vincent 246: if (undo_disable_flag)
1.11 vincent 247: return (TRUE);
1.1 vincent 248: reg.r_linep = lp;
249: reg.r_offset = offset;
250: reg.r_size = size;
1.9 vincent 251:
252: pos = find_absolute_dot(lp, offset);
253:
1.1 vincent 254: /*
255: * We try to reuse the last undo record to `compress' things.
1.13 deraadt 256: */
1.7 vincent 257: rec = LIST_FIRST(&curbp->b_undo);
1.10 vincent 258: if (rec != NULL) {
259: /* this will be hit like, 80% of the time... */
260: if (rec->type == BOUNDARY)
261: rec = LIST_NEXT(rec, next);
1.11 vincent 262: if (rec->type == INSERT) {
1.10 vincent 263: if (rec->pos + rec->region.r_size == pos) {
264: rec->region.r_size += reg.r_size;
1.11 vincent 265: return (TRUE);
1.10 vincent 266: }
1.1 vincent 267: }
268: }
1.9 vincent 269:
1.1 vincent 270: /*
271: * We couldn't reuse the last undo record, so prepare a new one
272: */
273: rec = new_undo_record();
1.9 vincent 274: rec->pos = pos;
1.1 vincent 275: rec->type = INSERT;
276: memmove(&rec->region, ®, sizeof(REGION));
277: rec->content = NULL;
1.9 vincent 278:
279: if (!last_was_boundary())
280: undo_add_boundary();
281:
1.7 vincent 282: LIST_INSERT_HEAD(&curbp->b_undo, rec, next);
1.9 vincent 283: undo_add_boundary();
1.1 vincent 284:
1.11 vincent 285: return (TRUE);
1.1 vincent 286: }
287:
288: /*
289: * This of course must be done _before_ the actual deletion is done
290: */
291: int
292: undo_add_delete(LINE *lp, int offset, int size)
293: {
294: REGION reg;
295: struct undo_rec *rec;
1.9 vincent 296: int pos;
1.1 vincent 297:
298: if (undo_disable_flag)
1.11 vincent 299: return (TRUE);
1.1 vincent 300:
301: reg.r_linep = lp;
302: reg.r_offset = offset;
303: reg.r_size = size;
304:
1.9 vincent 305: pos = find_absolute_dot(lp, offset);
1.3 vincent 306:
1.10 vincent 307: if (offset == llength(lp)) /* if it's a newline... */
1.9 vincent 308: undo_add_boundary();
309: else if ((rec = LIST_FIRST(&curbp->b_undo)) != NULL) {
310: /*
311: * Separate this command from the previous one if we're not
312: * just before the previous record...
313: */
1.10 vincent 314: if (rec->type == DELETE) {
1.9 vincent 315: if (rec->pos - rec->region.r_size != pos)
316: undo_add_boundary();
317: } else if (rec->type != BOUNDARY)
318: undo_add_boundary();
1.3 vincent 319: }
1.1 vincent 320: rec = new_undo_record();
321: rec->pos = pos;
322:
323: rec->type = DELETE;
324: memmove(&rec->region, ®, sizeof(REGION));
325: do {
326: rec->content = malloc(reg.r_size + 1);
327: } while ((rec->content == NULL) && drop_oldest_undo_record());
1.9 vincent 328:
1.1 vincent 329: if (rec->content == NULL)
330: panic("Out of memory");
1.9 vincent 331:
1.1 vincent 332: region_get_data(®, rec->content, reg.r_size);
333:
1.7 vincent 334: LIST_INSERT_HEAD(&curbp->b_undo, rec, next);
1.9 vincent 335: undo_add_boundary();
1.1 vincent 336:
1.11 vincent 337: return (TRUE);
1.1 vincent 338: }
339:
340: /*
341: * This of course must be called before the change takes place
342: */
343: int
344: undo_add_change(LINE *lp, int offset, int size)
345: {
346: if (undo_disable_flag)
1.11 vincent 347: return (TRUE);
1.12 vincent 348: undo_add_boundary();
349: nobound = 1;
350: undo_add_delete(lp, offset, size);
351: undo_add_insert(lp, offset, size);
352: nobound = 0;
1.9 vincent 353: undo_add_boundary();
354:
1.11 vincent 355: return (TRUE);
1.8 vincent 356: }
357:
358: /*
359: * Show the undo records for the current buffer in a new buffer.
360: */
361: int
362: undo_dump(void)
363: {
364: struct undo_rec *rec;
365: BUFFER *bp;
366: MGWIN *wp;
367: char buf[4096], tmp[1024];
368: int num;
369:
370: /*
371: * Prepare the buffer for insertion.
372: */
373: if ((bp = bfind("*undo*", TRUE)) == NULL)
1.11 vincent 374: return (FALSE);
1.9 vincent 375: bp->b_flag |= BFREADONLY;
1.8 vincent 376: bclear(bp);
377: popbuf(bp);
378:
1.10 vincent 379: for (wp = wheadp; wp != NULL; wp = wp->w_wndp) {
1.8 vincent 380: if (wp->w_bufp == bp) {
381: wp->w_dotp = bp->b_linep;
382: wp->w_doto = 0;
383: }
1.10 vincent 384: }
1.8 vincent 385:
386: num = 0;
387: for (rec = LIST_FIRST(&curbp->b_undo); rec != NULL;
1.13 deraadt 388: rec = LIST_NEXT(rec, next)) {
1.8 vincent 389: num++;
390: snprintf(buf, sizeof buf,
391: "Record %d =>\t %s at %d ", num,
392: (rec->type == DELETE) ? "DELETE":
393: (rec->type == INSERT) ? "INSERT":
394: (rec->type == BOUNDARY) ? "----" : "UNKNOWN",
395: rec->pos);
1.10 vincent 396:
1.12 vincent 397: if (rec->content) {
1.8 vincent 398: strlcat(buf, "\"", sizeof buf);
399: snprintf(tmp, sizeof tmp, "%.*s", rec->region.r_size,
400: rec->content);
401: strlcat(buf, tmp, sizeof buf);
402: strlcat(buf, "\"", sizeof buf);
403: }
404: snprintf(tmp, sizeof buf, " [%d]", rec->region.r_size);
405: strlcat(buf, tmp, sizeof buf);
406: addlinef(bp, buf);
407: }
1.11 vincent 408: return (TRUE);
1.1 vincent 409: }
410:
1.9 vincent 411: /*
412: * After the user did action1, then action2, then action3 :
413: *
414: * [action3] <--- Undoptr
415: * [action2]
416: * [action1]
417: * ------
418: * [undo]
419: *
420: * After undo:
421: *
422: * [undo of action3]
423: * [action2] <--- Undoptr
424: * [action1]
425: * ------
426: * [undo]
1.13 deraadt 427: *
1.9 vincent 428: * After another undo:
429: *
430: *
431: * [undo of action2]
432: * [undo of action3]
433: * [action1] <--- Undoptr
434: * ------
435: * [undo]
1.13 deraadt 436: *
1.9 vincent 437: * Note that the "undo of actionX" have no special meaning. Only when,
438: * say, we undo a deletion, the insertion will be recorded just as if it
1.10 vincent 439: * was typed on the keyboard. Resulting in the inverse operation being
1.9 vincent 440: * saved in the list.
441: *
442: * If undoptr reaches the bottom of the list, or if we moved between
443: * two undo actions, we make it point back at the topmost record. This is
444: * how we handle redoing.
445: */
1.1 vincent 446: int
1.4 vincent 447: undo(int f, int n)
1.1 vincent 448: {
1.9 vincent 449: struct undo_rec *ptr, *nptr;
450: int done, rval;
451: LINE *lp;
452: int offset;
453:
454: ptr = curbp->b_undoptr;
455:
456: /* if we moved, make ptr point back to the top of the list */
457: if ((curbp->b_undopos.r_linep != curwp->w_dotp) ||
458: (curbp->b_undopos.r_offset != curwp->w_doto) ||
459: (ptr == NULL))
460: ptr = LIST_FIRST(&curbp->b_undo);
1.1 vincent 461:
1.9 vincent 462: rval = TRUE;
1.10 vincent 463: while (n--) {
1.9 vincent 464: /* if we have a spurious boundary, free it and move on.... */
465: while (ptr && ptr->type == BOUNDARY) {
466: nptr = LIST_NEXT(ptr, next);
467: LIST_REMOVE(ptr, next);
468: free_undo_record(ptr);
469: ptr = nptr;
1.4 vincent 470: }
471: /*
1.9 vincent 472: * Ptr is NULL, but on the next run, it will point to the
473: * top again, redoing all stuff done in the buffer since
474: * its creation.
1.4 vincent 475: */
1.9 vincent 476: if (ptr == NULL) {
1.11 vincent 477: ewprintf("No further undo information");
1.9 vincent 478: rval = FALSE;
1.4 vincent 479: break;
480: }
1.6 vincent 481:
1.13 deraadt 482: /*
1.9 vincent 483: * Loop while we don't get a boundary specifying we've
484: * finished the current action...
485: */
486: done = 0;
487: do {
488: /* Unlink the current node from the list */
489: nptr = LIST_NEXT(ptr, next);
490: LIST_REMOVE(ptr, next);
491:
492: /*
493: * Move to where this has to apply
494: *
495: * Boundaries are put as position 0 (to save
496: * lookup time in find_absolute_dot) so we must
497: * not move there...
498: */
499: if (ptr->type != BOUNDARY) {
1.10 vincent 500: if (find_line_offset(ptr->pos, &lp,
501: &offset) == FALSE) {
1.9 vincent 502: ewprintf("Internal error in Undo!");
503: rval = FALSE;
504: break;
505: }
506: curwp->w_dotp = lp;
507: curwp->w_doto = offset;
508: }
509:
510: /*
511: * Do operation^-1
512: */
513: switch (ptr->type) {
514: case INSERT:
515: ldelete(ptr->region.r_size, KFORW);
516: break;
517: case DELETE:
1.13 deraadt 518: region_put_data(ptr->content,
1.9 vincent 519: ptr->region.r_size);
520: break;
521: case BOUNDARY:
522: done = 1;
523: break;
524: default:
525: break;
526: }
527: free_undo_record(ptr);
528:
529: /* And move to next record */
530: ptr = nptr;
531: } while (ptr != NULL && !done);
532:
533: ewprintf("Undo!");
1.1 vincent 534: }
1.9 vincent 535: /*
536: * Record where we are. (we have to save our new position at the end
537: * since we change the dot when undoing....)
538: */
539: curbp->b_undoptr = ptr;
540: curbp->b_undopos.r_linep = curwp->w_dotp;
541: curbp->b_undopos.r_offset = curwp->w_doto;
542:
1.13 deraadt 543: return (rval);
1.1 vincent 544: }