1 /* Part of XPCE --- The SWI-Prolog GUI toolkit
2
3 Author: Jan Wielemaker and Anjo Anjewierden
4 E-mail: jan@swi.psy.uva.nl
5 WWW: http://www.swi.psy.uva.nl/projects/xpce/
6 Copyright (c) 1985-2002, University of Amsterdam
7 All rights reserved.
8
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions
11 are met:
12
13 1. Redistributions of source code must retain the above copyright
14 notice, this list of conditions and the following disclaimer.
15
16 2. Redistributions in binary form must reproduce the above copyright
17 notice, this list of conditions and the following disclaimer in
18 the documentation and/or other materials provided with the
19 distribution.
20
21 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24 FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
25 COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
27 BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
29 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30 LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
31 ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
32 POSSIBILITY OF SUCH DAMAGE.
33 */
34
35 #include <h/kernel.h>
36 #include <h/text.h>
37
38 static void resetUndoBuffer(UndoBuffer ub);
39
40 /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
41 TEXTBUFFER UNDO
42
43 This module implements multi-action undo for textbuffers. Only three
44 basic operations are defined on textbuffers: deleting, inserting and
45 change. For any of these, a record is made that describes the change.
46 For insertions, this just defines the place and the size. For
47 deletions and changes the old text is stored as well. Undo simply
48 implies to walk back this change and perform the inverse operations.
49
50 The records are stored in an `undo buffer'. This buffer operates as a
51 cycle. New records are appended to the end. If the buffer is full,
52 old records are destroyed at the start, just until enough space is
53 available to store the new record. The elements are linked in a
54 double linked chain. The backward links are used to perform the
55 incremental undo's, the forward links are used to destroy old undo
56 records. The head and tail members point to the last inserted, resp.
57 oldest cell in the chain. The free member points ahead of the head
58 and describes where to allocate the next cell. The current describes
59 the cell to be undone on the next ->undo message. While performing
60 undos this pointer goes backwards in the list. On any other operation
61 it is placed at the head of the list.
62
63 Finally, the checkpoint member describes the head cell at the moment
64 ->modified @off was send to the textbuffer the last time. If undoing
65 hits this cell it will again mark the buffer as not modified.
66 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
67
68 typedef struct undo_cell * UndoCell;
69 typedef struct undo_delete * UndoDelete;
70 typedef struct undo_insert * UndoInsert;
71 typedef struct undo_change * UndoChange;
72
73 #define UNDO_DELETE 0 /* action types */
74 #define UNDO_INSERT 1
75 #define UNDO_CHANGE 2
76
77 #define NOCHECKPOINT ((UndoCell) -1)
78
79 #define COMMON_CELL \
80 UndoCell previous; /* previous cell */ \
81 UndoCell next; /* next in chain */ \
82 unsigned int size; /* size in chars */ \
83 char marked; /* marked as interactive cell */ \
84 char type; /* type of action */
85
86 struct undo_cell
87 { COMMON_CELL
88 };
89
90 struct undo_delete
91 { COMMON_CELL
92 int iswide;
93 long where; /* start address of delete */
94 long len; /* number of characters deleted there */
95 union
96 { charA A[1]; /* ISO Latin-1 text */
97 charW W[1]; /* Wide character text */
98 } text;
99 };
100
101 struct undo_insert
102 { COMMON_CELL
103 long where; /* start address of insert */
104 long len; /* number of characters inserted there */
105 };
106
107 struct undo_change
108 { COMMON_CELL
109 int iswide;
110 long where; /* start of change */
111 long len; /* length of change */
112 union
113 { charA A[1]; /* ISO Latin-1 text */
114 charW W[1]; /* Wide character text */
115 } text;
116 };
117
118 struct undo_buffer
119 { TextBuffer client; /* so we know whom to talk to */
120 unsigned size; /* size of buffer in chars */
121 int undone; /* last action was an undo */
122 int aborted; /* sequence was too big, aborted */
123 UndoCell current; /* current undo cell for undos */
124 UndoCell checkpoint; /* non-modified checkpoint */
125 UndoCell lastmark; /* last marked cell */
126 UndoCell head; /* first cell */
127 UndoCell tail; /* last cell */
128 UndoCell free; /* allocate next one here */
129 UndoCell buffer; /* buffer storage */
130 };
131
132 #define istbA(tb) ((tb)->buffer.iswide == 0)
133 #define Round(n, r) (((n)+(r)-1) & (~((r)-1)))
134 #define AllocRound(s) Round(s, sizeof(UndoCell))
135 #define Distance(p1, p2) ((char *)(p1) - (char *)(p2))
136 #define SizeAfter(ub, size) ((size) <= ub->size - \
137 Distance(ub->free, ub->buffer))
138 #define UndoDeleteSize(len) ((unsigned)(uintptr_t) &((UndoDelete)NULL)->text.A[len])
139 #define UndoChangeSize(len) ((unsigned)(uintptr_t) &((UndoChange)NULL)->text.A[len])
140
141
142 static UndoBuffer
createUndoBuffer(long size)143 createUndoBuffer(long size)
144 { UndoBuffer ub = alloc(sizeof(struct undo_buffer));
145
146 ub->size = AllocRound(size);
147 ub->buffer = alloc(ub->size);
148 ub->aborted = FALSE;
149 ub->client = NIL;
150 resetUndoBuffer(ub);
151
152 return ub;
153 }
154
155
156 static void
resetUndoBuffer(UndoBuffer ub)157 resetUndoBuffer(UndoBuffer ub)
158 { ub->current = ub->lastmark = ub->head = ub->tail = NULL;
159 ub->checkpoint = NOCHECKPOINT;
160 ub->free = ub->buffer;
161 }
162
163
164 void
destroyUndoBuffer(UndoBuffer ub)165 destroyUndoBuffer(UndoBuffer ub)
166 { if ( ub->buffer != NULL )
167 { unalloc(ub->size, ub->buffer);
168 ub->buffer = NULL;
169 }
170
171 unalloc(sizeof(struct undo_buffer), ub);
172 }
173
174
175
176 Int
getUndoTextBuffer(TextBuffer tb)177 getUndoTextBuffer(TextBuffer tb)
178 { long caret = -1;
179
180 if ( tb->undo_buffer != NULL )
181 { UndoBuffer ub = tb->undo_buffer;
182 UndoCell cell;
183
184 if ( (cell = ub->current) == NULL ) /* No further undo's */
185 fail;
186
187 while(cell != NULL)
188 { DEBUG(NAME_undo, Cprintf("Undo using cell %d: ",
189 Distance(cell, ub->buffer)));
190 switch( cell->type )
191 { case UNDO_DELETE:
192 { UndoDelete d = (UndoDelete) cell;
193 string s;
194
195 s.s_size = d->len;
196 s.s_iswide = d->iswide;
197 if ( d->iswide )
198 s.s_textA = d->text.A;
199 else
200 s.s_textW = d->text.W;
201
202 DEBUG(NAME_undo, Cprintf("Undo delete at %ld, len=%ld\n",
203 d->where, d->len));
204 insert_textbuffer(tb, d->where, 1, &s);
205 caret = max(caret, d->where + d->len);
206 break;
207 }
208 case UNDO_INSERT:
209 { UndoInsert i = (UndoInsert) cell;
210 DEBUG(NAME_undo, Cprintf("Undo insert at %ld, len=%ld\n",
211 i->where, i->len));
212 delete_textbuffer(tb, i->where, i->len);
213 caret = max(caret, i->where);
214 break;
215 }
216 case UNDO_CHANGE:
217 { UndoChange c = (UndoChange) cell;
218 string s;
219
220 s.s_size = c->len;
221 s.s_iswide = c->iswide;
222 if ( c->iswide )
223 s.s_textA = c->text.A;
224 else
225 s.s_textW = c->text.W;
226
227 DEBUG(NAME_undo, Cprintf("Undo change at %ld, len=%ld\n",
228 c->where, c->len));
229
230 change_textbuffer(tb, c->where, &s);
231 caret = max(caret, c->where + c->len);
232 break;
233 }
234 }
235
236 cell = cell->previous;
237 if ( cell == NULL || cell->marked == TRUE )
238 { ub->current = cell;
239
240 if ( cell == ub->checkpoint ) /* reached non-modified checkpoint */
241 { DEBUG(NAME_undo, Cprintf("Reset modified to @off\n"));
242 CmodifiedTextBuffer(tb, OFF);
243 }
244
245 changedTextBuffer(tb);
246 ub->undone = TRUE;
247
248 answer(toInt(caret));
249 }
250 }
251 }
252
253 fail;
254 }
255
256
257 status
undoTextBuffer(TextBuffer tb)258 undoTextBuffer(TextBuffer tb)
259 { return getUndoTextBuffer(tb) ? SUCCEED : FAIL;
260 }
261
262
263 static UndoBuffer
getUndoBufferTextBuffer(TextBuffer tb)264 getUndoBufferTextBuffer(TextBuffer tb)
265 { if ( tb->undo_buffer != NULL )
266 return tb->undo_buffer;
267
268 if ( isDefault(tb->undo_buffer_size) )
269 assign(tb, undo_buffer_size,
270 getClassVariableValueObject(tb, NAME_undoBufferSize));
271
272 if ( tb->undo_buffer_size != ZERO )
273 { tb->undo_buffer = createUndoBuffer(valInt(tb->undo_buffer_size));
274 tb->undo_buffer->client = tb;
275 }
276
277 return tb->undo_buffer;
278 }
279
280
281 status
undoBufferSizeTextBuffer(TextBuffer tb,Int size)282 undoBufferSizeTextBuffer(TextBuffer tb, Int size)
283 { if ( tb->undo_buffer_size != size )
284 { if ( tb->undo_buffer != NULL )
285 { destroyUndoBuffer(tb->undo_buffer);
286 tb->undo_buffer = NULL;
287 }
288
289 assign(tb, undo_buffer_size, size);
290 }
291
292 succeed;
293 }
294
295
296 status
markUndoTextBuffer(TextBuffer tb)297 markUndoTextBuffer(TextBuffer tb)
298 { UndoBuffer ub;
299
300 if ( (ub = getUndoBufferTextBuffer(tb)) )
301 { DEBUG(NAME_undo, Cprintf("markUndoTextBuffer(%s)\n", pp(tb)));
302
303 if ( ub->head )
304 { ub->head->marked = TRUE;
305 ub->lastmark = ub->head;
306 }
307
308 if ( ub->undone == FALSE )
309 ub->current = ub->head;
310
311 ub->undone = FALSE;
312 ub->aborted = FALSE;
313 }
314
315 succeed;
316 }
317
318
319 status
resetUndoTextBuffer(TextBuffer tb)320 resetUndoTextBuffer(TextBuffer tb)
321 { if ( tb->undo_buffer != NULL )
322 { destroyUndoBuffer(tb->undo_buffer);
323 tb->undo_buffer = NULL;
324 }
325
326 succeed;
327 }
328
329
330 status
checkpointUndoTextBuffer(TextBuffer tb)331 checkpointUndoTextBuffer(TextBuffer tb)
332 { UndoBuffer ub;
333
334 if ( (ub = getUndoBufferTextBuffer(tb)) )
335 ub->checkpoint = ub->head;
336
337 succeed;
338 }
339
340
341 static void
destroy_oldest_undo(UndoBuffer ub)342 destroy_oldest_undo(UndoBuffer ub)
343 { if ( ub->tail != NULL )
344 ub->tail->marked = FALSE;
345
346 while( ub->tail != NULL && ub->tail->marked == FALSE )
347 { if ( ub->tail == ub->current )
348 ub->current = NULL;
349 if ( ub->tail == ub->checkpoint )
350 ub->checkpoint = NOCHECKPOINT;
351 if ( ub->tail == ub->head )
352 { resetUndoBuffer(ub);
353 return;
354 }
355 if ( ub->tail->next )
356 ub->tail->next->previous = NULL;
357 ub->tail = ub->tail->next;
358 }
359
360 if ( ub->tail == NULL )
361 resetUndoBuffer(ub);
362 }
363
364
365 /********************************
366 * ALLOCATION *
367 *********************************/
368
369 static int
Between(UndoBuffer ub,UndoCell new,UndoCell old)370 Between(UndoBuffer ub, UndoCell new, UndoCell old)
371 { if ( new > old )
372 return Distance(new, old);
373
374 return ub->size - Distance(old, new);
375 }
376
377
378 /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
379 Allocate a new undo size with the requested size in bytes
380 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
381
382 static void *
new_undo_cell(UndoBuffer ub,unsigned int size)383 new_undo_cell(UndoBuffer ub, unsigned int size)
384 { UndoCell new;
385
386 if ( ub->aborted )
387 return NULL;
388
389 size = AllocRound(size);
390
391 if ( size > ub->size/2 ) /* Too big: destroy all */
392 { errorPce(ub->client, NAME_undoOverflow);
393
394 ub->aborted = TRUE;
395 resetUndoBuffer(ub);
396 return NULL;
397 }
398
399 for(;;)
400 { if ( ub->head == NULL ) /* Empty: new cell is head & tail */
401 break;
402
403 if ( ub->tail < ub->free )
404 { if ( SizeAfter(ub, size) )
405 break;
406 ub->free = ub->buffer;
407 } else if ( (int)size <= Distance(ub->tail, ub->free) )
408 break;
409
410 destroy_oldest_undo(ub);
411 }
412
413 if ( ub->lastmark && Between(ub, ub->free, ub->lastmark) >= (int)ub->size/2 )
414 { errorPce(ub->client, NAME_undoOverflow);
415
416 ub->aborted = TRUE;
417 resetUndoBuffer(ub);
418 return NULL;
419 }
420
421 new = ub->free;
422 new->size = size;
423 new->marked = FALSE;
424 new->next = NULL;
425 new->previous = ub->head;
426 if ( ub->head == NULL ) /* empty */
427 { ub->tail = new;
428 ub->lastmark = new;
429 } else
430 ub->head->next = new;
431 ub->head = new;
432 ub->free = (UndoCell) ((char *)new + size);
433
434 DEBUG(NAME_undo, Cprintf("Cell at %d size=%d: ",
435 Distance(new, ub->buffer), new->size));
436
437 return new;
438 }
439
440
441 /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
442 Resize the current undo-cell to be at least <size> characters.
443 - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */
444
445 static int
resize_undo_cell(UndoBuffer ub,UndoCell cell,unsigned int size)446 resize_undo_cell(UndoBuffer ub, UndoCell cell, unsigned int size)
447 { size = AllocRound(size);
448 assert(cell == ub->head);
449
450 if ( cell->size == size )
451 return TRUE;
452
453 while( ub->tail > cell && (int)size > Distance(ub->tail, cell) && ub->head )
454 destroy_oldest_undo(ub);
455
456 if ( ub->head &&
457 ((ub->tail > cell && (int)size < Distance(ub->tail, cell)) ||
458 (ub->tail < cell && SizeAfter(ub, size))) )
459 { cell->size = size;
460 ub->free = (UndoCell) ((char *) cell + size);
461
462 DEBUG(NAME_undo, Cprintf("Resized cell at %d size=%d\n",
463 Distance(cell, ub->buffer), cell->size));
464 return TRUE;
465 }
466
467 DEBUG(NAME_undo,
468 if ( !ub->head )
469 Cprintf("**** UNDO buffer overflow ****\n");
470 else
471 Cprintf("**** UNDO buffer circle ****\n"));
472
473 return FALSE;
474 }
475
476
477 void
register_insert_textbuffer(TextBuffer tb,long int where,long int len)478 register_insert_textbuffer(TextBuffer tb, long int where, long int len)
479 { UndoBuffer ub;
480
481 if ( len > 0 && (ub = getUndoBufferTextBuffer(tb)) != NULL )
482 { UndoInsert i = (UndoInsert) ub->head;
483
484 if ( i != NULL && i->type == UNDO_INSERT && i->marked == FALSE )
485 { if ( i->where + i->len == where || where + len == i->where )
486 { i->len += len;
487 DEBUG(NAME_undo, Cprintf("Insert at %ld grown %ld bytes\n",
488 i->where, i->len));
489 return;
490 }
491 }
492
493 if ( (i = new_undo_cell(ub, sizeof(struct undo_insert))) == NULL )
494 return;
495
496 i->type = UNDO_INSERT;
497 i->where = where;
498 i->len = len;
499 DEBUG(NAME_undo, Cprintf("New Insert at %ld, %ld bytes\n",
500 i->where, i->len));
501 }
502 }
503
504
505 static void
copy_undo_del(TextBuffer tb,long from,long len,UndoDelete udc,long offset)506 copy_undo_del(TextBuffer tb, long from, long len, UndoDelete udc, long offset)
507 { if ( udc->iswide )
508 { charW *to = &udc->text.W[offset];
509
510 for( ; len > 0; len--, from++ )
511 *to++ = fetch_textbuffer(tb, from);
512 } else
513 { charA *to = &udc->text.A[offset];
514
515 for( ; len > 0; len--, from++ )
516 *to++ = fetch_textbuffer(tb, from);
517 }
518 }
519
520
521 void
register_delete_textbuffer(TextBuffer tb,long where,long len)522 register_delete_textbuffer(TextBuffer tb, long where, long len)
523 { UndoBuffer ub;
524 long i;
525 int need_wide = FALSE;
526 int cell_size;
527
528 for(i=where; i<where+len; i++)
529 { wint_t c = fetch_textbuffer(tb, i);
530
531 if ( tisendsline(tb->syntax, c) )
532 tb->lines--;
533
534 if ( c > 0xff )
535 need_wide = TRUE;
536 }
537
538 if ( len > 0 && (ub = getUndoBufferTextBuffer(tb)) != NULL )
539 { UndoDelete udc = (UndoDelete) ub->head;
540
541 if ( udc != NULL && udc->type == UNDO_DELETE &&
542 udc->marked == FALSE &&
543 tb->buffer.s_iswide == udc->iswide )
544 { if ( where == udc->where ) /* forward delete */
545 { cell_size = len+udc->len;
546 if ( udc->iswide )
547 cell_size *= sizeof(charW);
548
549 if ( resize_undo_cell(ub, (UndoCell)udc, UndoDeleteSize(cell_size)) )
550 { copy_undo_del(tb, where, len, udc, udc->len);
551 udc->len += len;
552 DEBUG(NAME_undo, Cprintf("Delete at %ld grown forward %ld bytes\n",
553 udc->where, udc->len));
554 }
555
556 return;
557 }
558
559 if ( where + len == udc->where ) /* backward delete */
560 { cell_size = len+udc->len;
561 if ( udc->iswide )
562 cell_size *= sizeof(charW);
563
564 if ( resize_undo_cell(ub, (UndoCell) udc, UndoDeleteSize(cell_size)) )
565 { if ( udc->iswide )
566 { memmove(&udc->text.W[len], &udc->text.W, udc->len*sizeof(charW));
567 } else
568 { memmove(&udc->text.A[len], &udc->text.A, udc->len);
569 }
570
571 copy_undo_del(tb, where, len, udc, 0);
572 udc->len += len;
573 udc->where -= len;
574 DEBUG(NAME_undo, Cprintf("Delete at %ld grown backward %ld bytes\n",
575 udc->where, udc->len));
576 }
577 return;
578 }
579 }
580
581 cell_size = need_wide ? len*(int)sizeof(charW) : len;
582 if ( (udc = new_undo_cell(ub, UndoDeleteSize(cell_size))) == NULL )
583 return;
584 udc->type = UNDO_DELETE;
585 udc->where = where;
586 udc->len = len;
587 udc->iswide = need_wide;
588 copy_undo_del(tb, where, len, udc, 0);
589 DEBUG(NAME_undo, Cprintf("New delete at %ld, %ld bytes\n",
590 udc->where, udc->len));
591 }
592 }
593
594
595 static void
copy_undo_chg(TextBuffer tb,long from,long len,UndoChange uc,long offset)596 copy_undo_chg(TextBuffer tb, long from, long len, UndoChange uc, long offset)
597 { if ( uc->iswide )
598 { charW *to = &uc->text.W[offset];
599
600 for( ; len > 0; len--, from++ )
601 *to++ = fetch_textbuffer(tb, from);
602 } else
603 { charA *to = &uc->text.A[offset];
604
605 for( ; len > 0; len--, from++ )
606 *to++ = fetch_textbuffer(tb, from);
607 }
608 }
609
610
611 void
register_change_textbuffer(TextBuffer tb,long int where,long int len)612 register_change_textbuffer(TextBuffer tb, long int where, long int len)
613 { UndoBuffer ub;
614 int need_wide = FALSE;
615 int cell_size;
616 long i;
617
618 for(i=where; i<where+len; i++)
619 { wint_t c = fetch_textbuffer(tb, i);
620
621 if ( c > 0xff )
622 need_wide = TRUE;
623 }
624
625 if ( len > 0 && (ub = getUndoBufferTextBuffer(tb)) != NULL )
626 { UndoChange uc = (UndoChange) ub->head;
627
628 if ( uc != NULL && uc->type == UNDO_CHANGE &&
629 uc->marked == FALSE &&
630 tb->buffer.s_iswide == uc->iswide )
631 { if ( where == uc->where + uc->len ) /* forward change */
632 { cell_size = len+uc->len;
633 if ( uc->iswide )
634 cell_size *= sizeof(charW);
635
636 if ( resize_undo_cell(ub, (UndoCell)uc,
637 UndoChangeSize(cell_size)) )
638 { copy_undo_chg(tb, where, len, uc, uc->len);
639
640 uc->len += len;
641 DEBUG(NAME_undo,
642 Cprintf("Change at %ld grown forward to %ld bytes\n",
643 uc->where, uc->len));
644 }
645 return;
646 }
647
648 if ( where + len == uc->where ) /* backward change */
649 { cell_size = len+uc->len;
650 if ( uc->iswide )
651 cell_size *= sizeof(charW);
652
653 if ( resize_undo_cell(ub, (UndoCell)uc,
654 UndoChangeSize(cell_size)) )
655 { if ( uc->iswide )
656 { memmove(&uc->text.W[len], &uc->text.W, uc->len*sizeof(charW));
657 } else
658 { memmove(&uc->text.A[len], &uc->text.A, uc->len);
659 }
660
661 copy_undo_chg(tb, where, len, uc, 0);
662 uc->len += len;
663 uc->where -= len;
664 DEBUG(NAME_undo,
665 Cprintf("Change at %ld grown backward to %ld bytes\n",
666 uc->where, uc->len));
667 }
668 return;
669 }
670 }
671
672 cell_size = need_wide ? len*(int)sizeof(charW) : len;
673 if ( (uc = new_undo_cell(ub, UndoChangeSize(cell_size))) == NULL )
674 return;
675 uc->type = UNDO_CHANGE;
676 uc->where = where;
677 uc->len = len;
678 uc->iswide = need_wide;
679 copy_undo_chg(tb, where, len, uc, 0);
680 DEBUG(NAME_undo, Cprintf("New change at %ld, %ld bytes\n",
681 uc->where, uc->len));
682 }
683 }
684