1
2 /******************************************************************************
3 * MODULE : archiver.cpp
4 * DESCRIPTION: manage undo/redo history
5 * COPYRIGHT : (C) 2009 Joris van der Hoeven
6 *******************************************************************************
7 * This software falls under the GNU general public license version 3 or later.
8 * It comes WITHOUT ANY WARRANTY WHATSOEVER. For details, see the file LICENSE
9 * in the root directory or <http://www.gnu.org/licenses/gpl-3.0.html>.
10 ******************************************************************************/
11
12 #include "archiver.hpp"
13 #include "hashset.hpp"
14 #include "iterator.hpp"
15
16 extern tree the_et;
17 array<patch> singleton (patch p);
18 static patch make_compound (array<patch> a);
19 static patch make_branches (array<patch> a);
20 static hashset<double> genuine_authors;
21 static hashset<pointer> archs;
22 static hashset<pointer> pending_archs;
23
24 /******************************************************************************
25 * Constructors, destructors, printing and announcements
26 ******************************************************************************/
27
archiver_rep(double author,path rp2)28 archiver_rep::archiver_rep (double author, path rp2):
29 archive (make_branches (0)),
30 current (make_compound (0)),
31 depth (0),
32 last_save (0),
33 last_autosave (0),
34 the_author (author),
35 the_owner (0),
36 rp (rp2),
37 undo_obs (undo_observer (this)),
38 versioning (false)
39 {
40 archs->insert ((pointer) this);
41 attach_observer (subtree (the_et, rp), undo_obs);
42 genuine_authors->insert (the_author);
43 }
44
~archiver_rep()45 archiver_rep::~archiver_rep () {
46 genuine_authors->remove (the_author);
47 detach_observer (subtree (the_et, rp), undo_obs);
48 archs->remove ((pointer) this);
49 pending_archs->remove ((pointer) this);
50 }
51
archiver(double author,path rp)52 archiver::archiver (double author, path rp):
53 rep (tm_new<archiver_rep> (author, rp)) {}
54
55 void
clear()56 archiver_rep::clear () {
57 archive= make_branches (0);
58 current= make_compound (0);
59 the_owner= 0;
60 depth= 0;
61 last_save= -1;
62 last_autosave= -1;
63 }
64
65 void
show_all()66 archiver_rep::show_all () {
67 cout << HRULE << archive << LF << HRULE << LF;
68 }
69
70 ////extern tree the_et;
71
72 void
archive_announce(archiver_rep * arch,modification mod)73 archive_announce (archiver_rep* arch, modification mod) {
74 //cout << "Archive " << mod << "\n";
75 ////stretched_print (the_et, true);
76 if (DEBUG_HISTORY) debug_history << "Archive " << mod << "\n";
77 ASSERT (arch->rp <= mod->p, "invalid modification");
78 if (!arch->versioning) {
79 arch->add (mod);
80 pending_archs->insert ((pointer) arch);
81 }
82 }
83
84 void
global_clear_history()85 global_clear_history () {
86 iterator<pointer> it = iterate (archs);
87 while (it->busy()) {
88 archiver_rep* arch= (archiver_rep*) it->next();
89 arch->clear ();
90 }
91 }
92
93 void
global_confirm()94 global_confirm () {
95 iterator<pointer> it = iterate (pending_archs);
96 while (it->busy()) {
97 archiver_rep* arch= (archiver_rep*) it->next();
98 arch->confirm ();
99 arch->simplify ();
100 }
101 pending_archs= hashset<pointer> ();
102 }
103
104 void
global_cancel()105 global_cancel () {
106 iterator<pointer> it = iterate (pending_archs);
107 while (it->busy()) {
108 archiver_rep* arch= (archiver_rep*) it->next();
109 arch->cancel ();
110 arch->simplify ();
111 }
112 pending_archs= hashset<pointer> ();
113 }
114
115 /******************************************************************************
116 * Useful subroutines
117 ******************************************************************************/
118
119 static patch
make_compound(array<patch> a)120 make_compound (array<patch> a) {
121 if (N(a) == 1) return a[0];
122 else return patch (false, a);
123 }
124
125 static patch
make_branches(array<patch> a)126 make_branches (array<patch> a) {
127 if (N(a) == 1) return a[0];
128 else return patch (true, a);
129 }
130
131 static patch
append_branches(patch p1,patch p2)132 append_branches (patch p1, patch p2) {
133 return make_branches (append (branches (p1), branches (p2)));
134 }
135
136 static patch
make_history(patch undo,patch redo)137 make_history (patch undo, patch redo) {
138 array<patch> a;
139 a << undo << branches (redo);
140 return make_branches (a);
141 }
142
143 static int
nr_undo(patch p)144 nr_undo (patch p) {
145 if (nr_branches (p) == 0 || nr_children (branch (p, 0)) != 2) return 0;
146 return 1;
147 }
148
149 static int
nr_redo(patch p)150 nr_redo (patch p) {
151 return max (0, nr_branches (p) - 1);
152 }
153
154 static patch
get_undo(patch p)155 get_undo (patch p) {
156 ASSERT (nr_branches (p) > 0, "undo part unavailable");
157 return branch (p, 0);
158 }
159
160 static patch
get_redo(patch p)161 get_redo (patch p) {
162 if (nr_branches (p) == 0) return make_branches (array<patch> ());
163 return make_branches (branches (p, 1, nr_branches (p)));
164 }
165
166 static patch
car(patch p)167 car (patch p) {
168 ASSERT (nr_children (branch (p, 0)) == 2, "car unavailable")
169 return child (p, 0);
170 }
171
172 static patch
cdr(patch p)173 cdr (patch p) {
174 ASSERT (nr_children (branch (p, 0)) == 2, "cdr unavailable")
175 return child (p, 1);
176 }
177
178 /******************************************************************************
179 * Internal subroutines
180 ******************************************************************************/
181
182 void
apply(patch p)183 archiver_rep::apply (patch p) {
184 // apply a patch, while disabling versioning during the modifications
185 // cout << "Apply " << p << "\n";
186 ASSERT (is_applicable (p, the_et), "invalid history");
187 bool old= versioning;
188 bool global_old= busy_versioning;
189 versioning= true;
190 busy_versioning= true;
191 ::apply (p, the_et);
192 versioning= old;
193 busy_versioning= global_old;
194 }
195
196 void
split(patch p1,patch p2,patch & re1,patch & re2)197 archiver_rep::split (patch p1, patch p2, patch& re1, patch& re2) {
198 //cout << "p1= " << p1 << "\n";
199 //cout << "p2= " << p2 << "\n";
200 array<patch> a= branches (p2);
201 array<patch> a1;
202 array<patch> a2;
203 for (int i=0; i<N(a); i++) {
204 patch q1= p1;
205 patch q2= car (a[i]);
206 if (get_author (q2) != the_author || !swap (q1, q2)) a1 << a[i];
207 else a2 << patch (q1, make_future (q2, cdr (a[i])));
208 }
209 re1= make_branches (a1);
210 re2= make_branches (a2);
211 //cout << "re1= " << re1 << "\n";
212 //cout << "re2= " << re2 << "\n";
213 }
214
215 patch
make_future(patch p1,patch p2)216 archiver_rep::make_future (patch p1, patch p2) {
217 if (nr_branches (p2) == 0 || get_author (p1) == the_author)
218 return patch (p1, p2);
219 patch re1, re2;
220 split (p1, p2, re1, re2);
221 if (nr_branches (re1) != 0) re1= patch (p1, re1);
222 return append_branches (re1, re2);
223 }
224
225 patch
expose(patch archive)226 archiver_rep::expose (patch archive) {
227 if (nr_undo (archive) != 0 &&
228 get_author (car (get_undo (archive))) != the_author &&
229 nr_undo (cdr (get_undo (archive))) != 0)
230 {
231 patch nx1= expose (cdr (get_undo (archive)));
232 if (get_author (car (get_undo (nx1))) != the_author) return archive;
233 patch un1= car (get_undo (archive));
234 patch un2= car (get_undo (nx1));
235 patch re1= get_redo (archive);
236 patch re2= get_redo (nx1);
237 patch nx2= cdr (get_undo (nx1));
238 patch fut= make_branches (0);
239 if (nr_branches (re2) != 0) fut= make_future (un1, re2);
240 if (!swap (un1, un2)) return archive;
241 patch nx= make_history (patch (un2, nx2), make_branches (0));
242 patch un= patch (un1, nx);
243 patch re= append_branches (re1, fut);
244 last_save= last_autosave= -1;
245 return make_history (un, re);
246 }
247 else return archive;
248 }
249
250 void
expose()251 archiver_rep::expose () {
252 archive= expose (archive);
253 }
254
255 void
normalize()256 archiver_rep::normalize () {
257 if (nr_undo (archive) != 0 && nr_redo (cdr (get_undo (archive))) != 0) {
258 patch un1= get_undo (archive);
259 patch re1= get_redo (archive);
260 patch p1 = car (un1);
261 patch nx1= cdr (un1);
262 patch un2= get_undo (nx1);
263 patch re2= get_redo (nx1);
264 patch Re1, Re2;
265 if (get_author (p1) == the_author) return;
266 split (p1, re2, Re1, Re2);
267 patch ar2= make_history (un2, Re1);
268 archive= make_history (patch (p1, ar2), append_branches (re1, Re2));
269 last_save= last_autosave= -1;
270 }
271 }
272
273 /******************************************************************************
274 * Routines concerning the current modifications
275 ******************************************************************************/
276
277 void
add(modification m)278 archiver_rep::add (modification m) {
279 m= copy (m);
280 if (the_owner != 0 && the_owner != get_author ()) {
281 //cout << "Change " << the_owner << " -> " << get_author () << "\n";
282 confirm ();
283 }
284 else the_owner= get_author ();
285 modification i= invert (m, the_et);
286 patch q (i, m);
287 //cout << "Add [" << the_owner << "] " << q << "\n";
288 current= patch (q, current);
289 }
290
291 void
start_slave(double a)292 archiver_rep::start_slave (double a) {
293 if (the_owner != 0 && the_owner != get_author ()) {
294 //cout << "Change " << the_owner << " -> " << get_author () << "\n";
295 confirm ();
296 }
297 else the_owner= get_author ();
298 patch q (a, false);
299 //cout << "Add [" << the_owner << "] " << q << "\n";
300 current= patch (q, current);
301 }
302
303 bool
active()304 archiver_rep::active () {
305 return nr_children (current) != 0;
306 }
307
308 bool
has_history()309 archiver_rep::has_history () {
310 return nr_undo (archive) == 1;
311 }
312
313 void
cancel()314 archiver_rep::cancel () {
315 if (active ()) {
316 //cout << "Cancel " << current << "\n";
317 apply (current);
318 current= make_compound (0);
319 the_owner= 0;
320 }
321 }
322
323 void
confirm()324 archiver_rep::confirm () {
325 if (active ()) {
326 current= patch (the_owner, compactify (current));
327 if (nr_children (remove_set_cursor (current)) == 0)
328 current= make_compound (0);
329 if (active ()) {
330 //cout << "Confirm " << current << "\n";
331 archive= patch (current, archive);
332 current= make_compound (0);
333 the_owner= 0;
334 depth++;
335 if (depth <= last_save) last_save= -1;
336 if (depth <= last_autosave) last_autosave= -1;
337 normalize ();
338 //show_all ();
339 }
340 }
341 }
342
343 bool
retract()344 archiver_rep::retract () {
345 if (!has_history ()) return false;
346 if (the_owner != 0 && the_owner != the_author) return false;
347 expose ();
348 patch un= car (get_undo (archive));
349 if (get_author (un) != the_author) return false;
350 patch re= get_redo (archive);
351 patch nx= cdr (get_undo (archive));
352 //cout << "Retract " << un << "\n";
353 if (active ()) current= compactify (patch (current, un));
354 else current= un;
355 the_owner= the_author;
356 if (nr_branches (re) != 0) {
357 patch q= invert (current, the_et);
358 re= patch (q, re);
359 }
360 if (nr_branches (nx) != 0) nx= get_undo (nx);
361 archive= make_history (nx, append_branches (re, get_redo (nx)));
362 depth--;
363 //show_all ();
364 return true;
365 }
366
367 bool
forget()368 archiver_rep::forget () {
369 cancel ();
370 bool r= retract ();
371 if (r) cancel ();
372 return r;
373 }
374
375 void
forget_cursor()376 archiver_rep::forget_cursor () {
377 current= remove_set_cursor (current);
378 }
379
380 /******************************************************************************
381 * Simplification of the history
382 ******************************************************************************/
383
384 void
simplify()385 archiver_rep::simplify () {
386 if (has_history () &&
387 nr_undo (cdr (get_undo (archive))) == 1 &&
388 nr_redo (cdr (get_undo (archive))) == 0 &&
389 depth != last_save + 1)
390 {
391 patch p1= car (get_undo (archive));
392 patch p2= car (get_undo (cdr (get_undo (archive))));
393 ////show_all ();
394 ////stretched_print (the_et, true);
395 //cout << "p1= " << p1 << "\n";
396 //cout << "p2= " << p2 << "\n";
397 bool r= join (p1, p2, the_et);
398 //cout << "pr= " << p1 << "\n";
399 if (r) {
400 //cout << "\n\nSimplify\n";
401 //show_all ();
402 patch un= patch (p1, cdr (get_undo (cdr (get_undo (archive)))));
403 patch re= get_redo (archive);
404 archive= make_history (un, re);
405 //show_all ();
406 //cout << "\n";
407 if (depth == last_autosave + 1) last_autosave= -1;
408 depth--;
409 simplify ();
410 }
411 }
412 }
413
414 /******************************************************************************
415 * Undo and redo
416 ******************************************************************************/
417
418 int
undo_possibilities()419 archiver_rep::undo_possibilities () {
420 return nr_undo (archive);
421 }
422
423 int
redo_possibilities()424 archiver_rep::redo_possibilities () {
425 return nr_redo (archive);
426 }
427
428 path
undo_one(int i)429 archiver_rep::undo_one (int i) {
430 if (active ()) return path ();
431 if (undo_possibilities () != 0) {
432 ASSERT (i == 0, "index out of range");
433 patch p= car (get_undo (archive));
434 ASSERT (is_applicable (p, the_et), "history corrupted");
435 patch q= invert (p, the_et);
436 apply (p);
437 patch re1= patch (q, get_redo (archive));
438 patch nx = cdr (get_undo (archive));
439 patch re2= get_redo (nx);
440 patch re = append_branches (re1, re2);
441 patch un = (nr_branches (nx) == 0? nx: get_undo (nx));
442 archive= make_history (un, re);
443 depth--;
444 //show_all ();
445 return cursor_hint (q, the_et);
446 }
447 return path ();
448 }
449
450 path
redo_one(int i)451 archiver_rep::redo_one (int i) {
452 if (active ()) return path ();
453 int n= redo_possibilities ();
454 if (n != 0) {
455 ASSERT (i >= 0 && i < n, "index out of range");
456 patch un= get_undo (archive);
457 patch re= get_redo (archive);
458 patch p= car (branch (re, i));
459 //cout << "p= " << p << "\n";
460 ASSERT (is_applicable (p, the_et), "future corrupted");
461 patch q= invert (p, the_et);
462 //cout << "q= " << q << "\n";
463 apply (p);
464 patch other= make_branches (append (branches (re, 0, i),
465 branches (re, i+1, n)));
466 //cout << "other= " << other << "\n";
467 patch nx= make_history (un, other);
468 archive= make_history (patch (q, nx), cdr (branch (re, i)));
469 if (depth <= last_save && i != 0) last_save= -1;
470 if (depth <= last_autosave && i != 0) last_autosave= -1;
471 depth++;
472 normalize ();
473 //show_all ();
474 return cursor_hint (q, the_et);
475 }
476 return path ();
477 }
478
479 path
undo(int i)480 archiver_rep::undo (int i) {
481 if (active ()) return path ();
482 path r;
483 while (undo_possibilities () != 0) {
484 ASSERT (i == 0, "index out of range");
485 expose ();
486 if (get_author (car (get_undo (archive))) == the_author)
487 return undo_one (i);
488 else {
489 r= undo_one (i);
490 i= 0;
491 }
492 }
493 return r;
494 }
495
496 path
redo(int i)497 archiver_rep::redo (int i) {
498 if (active ()) return path ();
499 path r;
500 bool first= true;
501 while (redo_possibilities () != 0) {
502 ASSERT (i >= 0 && i < redo_possibilities (), "index out of range");
503 patch re= branch (get_redo (archive), i);
504 bool done= (get_author (car (re)) == the_author);
505 r= redo_one (i);
506 if (done && !first) break;
507 if (nr_redo (archive) != 1) break;
508 i= 0;
509 first= false;
510 re= branch (get_redo (archive), i);
511 if (get_author (car (re)) == the_author) break;
512 if (done && genuine_authors->contains (get_author (car (re)))) break;
513 }
514 return r;
515 }
516
517 /******************************************************************************
518 * Marking blocks for grouped modifications or canceling
519 ******************************************************************************/
520
521 static bool
is_marker(patch p,double m,bool birth)522 is_marker (patch p, double m, bool birth) {
523 if (get_type (p) == PATCH_AUTHOR)
524 return is_marker (p[0], m, birth);
525 else if (get_type (p) == PATCH_BIRTH)
526 return get_author (p) == m && get_birth (p) == birth;
527 else return false;
528 }
529
530 static patch
compress(patch archive1)531 compress (patch archive1) {
532 if (nr_undo (archive1) == 0) return archive1;
533 patch un1= get_undo (archive1);
534 patch re1= get_redo (archive1);
535 if (!is_author (car (un1))) return archive1;
536 if (is_birth (car (un1) [0])) return archive1;
537 if (!is_branch (re1) || N(re1) != 0) return archive1;
538 patch archive2= compress (cdr (un1));
539 if (nr_undo (archive2) == 0) return archive1;
540 patch un2= get_undo (archive2);
541 patch re2= get_redo (archive2);
542 if (!is_author (car (un2))) return archive1;
543 if (is_birth (car (un2) [0])) return archive1;
544 if (!is_branch (re2) || N(re2) != 0) return archive1;
545 if (get_author (car (un1)) != get_author (car (un2))) return archive1;
546 //cout << "cun1= " << car (un1) << LF;
547 //cout << "cun2= " << car (un2) << LF;
548 patch cun= compactify (patch (car (un1), car (un2)));
549 //cout << "cun = " << cun << LF;
550 //return archive1;
551 return make_history (patch (cun, cdr (un2)), re2);
552 }
553
554 static patch
remove_marker_bis(patch archive,double m)555 remove_marker_bis (patch archive, double m) {
556 ASSERT (nr_undo (archive) != 0, "marker not found");
557 if (is_marker (car (get_undo (archive)), m, false)) {
558 ASSERT (nr_redo (archive) == 0, "cannot remove marker");
559 return cdr (get_undo (archive));
560 }
561 else {
562 patch un= get_undo (archive);
563 patch re= get_redo (archive);
564 patch rem= remove_marker_bis (cdr (un), m);
565 return make_history (patch (car (un), rem), re);
566 }
567 }
568
569 static patch
remove_marker(patch archive,double m)570 remove_marker (patch archive, double m) {
571 return remove_marker_bis (compress (archive), m);
572 }
573
574 void
mark_start(double m)575 archiver_rep::mark_start (double m) {
576 //cout << "Mark start " << m << "\n";
577 confirm ();
578 start_slave (m);
579 confirm ();
580 //show_all ();
581 }
582
583 void
mark_end(double m)584 archiver_rep::mark_end (double m) {
585 //cout << "Mark end " << m << "\n";
586 if (active ()) {
587 //if (does_modify (current))
588 // cout << "CONFIRM: " << current << "\n";
589 confirm ();
590 }
591 archive= remove_marker (archive, m);
592 depth--;
593 simplify ();
594 //show_all ();
595 }
596
597 bool
mark_cancel(double m)598 archiver_rep::mark_cancel (double m) {
599 //cout << "Mark cancel " << m << "\n";
600 cancel ();
601 while (nr_undo (archive) != 0) {
602 expose ();
603 if (is_marker (car (get_undo (archive)), m, false)) {
604 archive= remove_marker (archive, m);
605 depth--;
606 simplify ();
607 return true;
608 }
609 if (get_author (car (get_undo (archive))) != the_author) {
610 archive= remove_marker (archive, m);
611 depth--;
612 return false;
613 }
614 retract ();
615 cancel ();
616 }
617 return false;
618 }
619
620 /******************************************************************************
621 * Check changes since last save/autosave
622 ******************************************************************************/
623
624 int
corrected_depth()625 archiver_rep::corrected_depth () {
626 // NOTE : fix depth due to presence of marker
627 // FIXME: implement a more robust check for conformity with saved state
628 if (nr_undo (archive) == 0) return depth;
629 patch p= car (get_undo (archive));
630 if (get_type (p) == PATCH_AUTHOR) p= p[0];
631 if (get_type (p) == PATCH_BIRTH && get_birth (p) == false) return depth - 1;
632 return depth;
633 }
634
635 void
require_save()636 archiver_rep::require_save () {
637 last_save= -1;
638 }
639
640 void
notify_save()641 archiver_rep::notify_save () {
642 last_save= corrected_depth ();
643 }
644
645 bool
conform_save()646 archiver_rep::conform_save () {
647 return last_save == corrected_depth ();
648 }
649
650 void
require_autosave()651 archiver_rep::require_autosave () {
652 last_autosave= -1;
653 }
654
655 void
notify_autosave()656 archiver_rep::notify_autosave () {
657 last_autosave= depth;
658 }
659
660 bool
conform_autosave()661 archiver_rep::conform_autosave () {
662 return last_autosave == depth;
663 }
664