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