src/src/Data/History/archiver.cpp

   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
  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
  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
  52 archiver::archiver (double author, path rp):
  53   rep (tm_new<archiver_rep> (author, rp)) {}
  54
  55 void
  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
  66 archiver_rep::show_all () {
  67   cout << HRULE << archive << LF << HRULE << LF;
  68 }
  69
  70 void
  71 archive_announce (archiver_rep* arch, modification mod) {
  72   //cout << "Archive " << mod << "\n";
  73   ASSERT (arch->rp <= mod->p, "invalid modification");
  74   if (!arch->versioning) {
  75     arch->add (mod);
  76     pending_archs->insert ((pointer) arch);
  77   }
  78 }
  79
  80 void
  81 global_clear_history () {
  82   iterator<pointer> it = iterate (archs);
  83   while (it->busy()) {
  84     archiver_rep* arch= (archiver_rep*) it->next();
  85     arch->clear ();
  86   }
  87 }
  88
  89 void
  90 global_confirm () {
  91   iterator<pointer> it = iterate (pending_archs);
  92   while (it->busy()) {
  93     archiver_rep* arch= (archiver_rep*) it->next();
  94     arch->confirm ();
  95     arch->simplify ();
  96   }
  97   pending_archs= hashset<pointer> ();
  98 }
  99
 100 /******************************************************************************
 101 * Useful subroutines
 102 ******************************************************************************/
 103
 104 static patch
 105 make_compound (array<patch> a) {
 106   if (N(a) == 1) return a[0];
 107   else return patch (false, a);
 108 }
 109
 110 static patch
 111 make_branches (array<patch> a) {
 112   if (N(a) == 1) return a[0];
 113   else return patch (true, a);
 114 }
 115
 116 static patch
 117 append_branches (patch p1, patch p2) {
 118   return make_branches (append (branches (p1), branches (p2)));
 119 }
 120
 121 static patch
 122 make_history (patch undo, patch redo) {
 123   array<patch> a;
 124   a << undo << branches (redo);
 125   return make_branches (a);
 126 }
 127
 128 static int
 129 nr_undo (patch p) {
 130   if (nr_branches (p) == 0 || nr_children (branch (p, 0)) != 2) return 0;
 131   return 1;
 132 }
 133
 134 static int
 135 nr_redo (patch p) {
 136   return max (0, nr_branches (p) - 1);
 137 }
 138
 139 static patch
 140 get_undo (patch p) {
 141   ASSERT (nr_branches (p) > 0, "undo part unavailable");
 142   return branch (p, 0);
 143 }
 144
 145 static patch
 146 get_redo (patch p) {
 147   if (nr_branches (p) == 0) return make_branches (array<patch> ());
 148   return make_branches (branches (p, 1, nr_branches (p)));
 149 }
 150
 151 static patch
 152 car (patch p) {
 153   ASSERT (nr_children (branch (p, 0)) == 2, "car unavailable")
 154   return child (p, 0);
 155 }
 156
 157 static patch
 158 cdr (patch p) {
 159   ASSERT (nr_children (branch (p, 0)) == 2, "cdr unavailable")
 160   return child (p, 1);
 161 }
 162
 163 /******************************************************************************
 164 * Internal subroutines
 165 ******************************************************************************/
 166
 167 void
 168 archiver_rep::apply (patch p) {
 169   // apply a patch, while disabling versioning during the modifications
 170   // cout << "Apply " << p << "\n";
 171   ASSERT (is_applicable (p, the_et), "invalid history");
 172   bool old= versioning;
 173   versioning= true;
 174   ::apply (p, the_et);
 175   versioning= old;
 176 }
 177
 178 void
 179 archiver_rep::split (patch p1, patch p2, patch& re1, patch& re2) {
 180   //cout << "p1= " << p1 << "\n";
 181   //cout << "p2= " << p2 << "\n";
 182   array<patch> a= branches (p2);
 183   array<patch> a1;
 184   array<patch> a2;
 185   for (int i=0; i<N(a); i++) {
 186     patch q1= p1;
 187     patch q2= car (a[i]);
 188     if (get_author (q2) != the_author || !swap (q1, q2)) a1 << a[i];
 189     else a2 << patch (q1, make_future (q2, cdr (a[i])));
 190   }
 191   re1= make_branches (a1);
 192   re2= make_branches (a2);
 193   //cout << "re1= " << re1 << "\n";
 194   //cout << "re2= " << re2 << "\n";
 195 }
 196
 197 patch
 198 archiver_rep::make_future (patch p1, patch p2) {
 199   if (nr_branches (p2) == 0 || get_author (p1) == the_author)
 200     return patch (p1, p2);
 201   patch re1, re2;
 202   split (p1, p2, re1, re2);
 203   if (nr_branches (re1) != 0) re1= patch (p1, re1);
 204   return append_branches (re1, re2);
 205 }
 206
 207 patch
 208 archiver_rep::expose (patch archive) {
 209   if (nr_undo (archive) != 0 &&
 210       get_author (car (get_undo (archive))) != the_author &&
 211       nr_undo (cdr (get_undo (archive))) != 0)
 212     {
 213       patch nx1= expose (cdr (get_undo (archive)));
 214       if (get_author (car (get_undo (nx1))) != the_author) return archive;
 215       patch un1= car (get_undo (archive));
 216       patch un2= car (get_undo (nx1));
 217       patch re1= get_redo (archive);
 218       patch re2= get_redo (nx1);
 219       patch nx2= cdr (get_undo (nx1));
 220       patch fut= make_branches (0);
 221       if (nr_branches (re2) != 0) fut= make_future (un1, re2);
 222       if (!swap (un1, un2)) return archive;
 223       patch nx= make_history (patch (un2, nx2), make_branches (0));
 224       patch un= patch (un1, nx);
 225       patch re= append_branches (re1, fut);
 226       last_save= last_autosave= -1;
 227       return make_history (un, re);
 228     }
 229   else return archive;
 230 }
 231
 232 void
 233 archiver_rep::expose () {
 234   archive= expose (archive);
 235 }
 236
 237 void
 238 archiver_rep::normalize () {
 239   if (nr_undo (archive) != 0 && nr_redo (cdr (get_undo (archive))) != 0) {
 240     patch un1= get_undo (archive);
 241     patch re1= get_redo (archive);
 242     patch p1 = car (un1);
 243     patch nx1= cdr (un1);
 244     patch un2= get_undo (nx1);
 245     patch re2= get_redo (nx1);
 246     patch Re1, Re2;
 247     if (get_author (p1) == the_author) return;
 248     split (p1, re2, Re1, Re2);
 249     patch ar2= make_history (un2, Re1);
 250     archive= make_history (patch (p1, ar2), append_branches (re1, Re2));
 251     last_save= last_autosave= -1;
 252   }
 253 }
 254
 255 /******************************************************************************
 256 * Routines concerning the current modifications
 257 ******************************************************************************/
 258
 259 void
 260 archiver_rep::add (modification m) {
 261   if (the_owner != 0 && the_owner != get_author ()) {
 262     //cout << "Change " << the_owner << " -> " << get_author () << "\n";
 263     confirm ();
 264   }
 265   else the_owner= get_author ();
 266   modification i= invert (m, the_et);
 267   patch q (i, m);
 268   //cout << "Add [" << the_owner << "] " << q << "\n";
 269   current= patch (q, current);
 270 }
 271
 272 void
 273 archiver_rep::start_slave (double a) {
 274   if (the_owner != 0 && the_owner != get_author ()) {
 275     //cout << "Change " << the_owner << " -> " << get_author () << "\n";
 276     confirm ();
 277   }
 278   else the_owner= get_author ();
 279   patch q (a, false);
 280   //cout << "Add [" << the_owner << "] " << q << "\n";
 281   current= patch (q, current);
 282 }
 283
 284 bool
 285 archiver_rep::active () {
 286   return nr_children (current) != 0;
 287 }
 288
 289 bool
 290 archiver_rep::has_history () {
 291   return nr_undo (archive) == 1;
 292 }
 293
 294 void
 295 archiver_rep::cancel () {
 296   if (active ()) {
 297     // cout << "Cancel " << current << "\n";
 298     apply (current);
 299     current= make_compound (0);
 300     the_owner= 0;
 301   }
 302 }
 303
 304 void
 305 archiver_rep::confirm () {
 306   if (active ()) {
 307     current= patch (the_owner, compactify (current));
 308     //cout << "Confirm " << current << "\n";
 309     archive= patch (current, archive);
 310     current= make_compound (0);
 311     the_owner= 0;
 312     depth++;
 313     if (depth <= last_save) last_save= -1;
 314     if (depth <= last_autosave) last_autosave= -1;
 315     normalize ();
 316     //show_all ();
 317   }
 318 }
 319
 320 bool
 321 archiver_rep::retract () {
 322   if (!has_history ()) return false;
 323   if (the_owner != 0 && the_owner != the_author) return false;
 324   expose ();
 325   patch un= car (get_undo (archive));
 326   if (get_author (un) != the_author) return false;
 327   patch re= get_redo (archive);
 328   patch nx= cdr (get_undo (archive));
 329   //cout << "Retract " << un << "\n";
 330   if (active ()) current= compactify (patch (current, un));
 331   else current= un;
 332   the_owner= the_author;
 333   if (nr_branches (re) != 0) {
 334     patch q= invert (current, the_et);
 335     re= patch (q, re);
 336   }
 337   if (nr_branches (nx) != 0) nx= get_undo (nx);
 338   archive= make_history (nx, append_branches (re, get_redo (nx)));
 339   depth--;
 340   //show_all ();
 341   return true;
 342 }
 343
 344 bool
 345 archiver_rep::forget () {
 346   cancel ();
 347   bool r= retract ();
 348   if (r) cancel ();
 349   return r;
 350 }
 351
 352 /******************************************************************************
 353 * Simplification of the history
 354 ******************************************************************************/
 355
 356 void
 357 archiver_rep::simplify () {
 358   if (has_history () &&
 359       nr_undo (cdr (get_undo (archive))) == 1 &&
 360       nr_redo (cdr (get_undo (archive))) == 0 &&
 361       depth != last_save + 1)
 362     {
 363       patch p1= car (get_undo (archive));
 364       patch p2= car (get_undo (cdr (get_undo (archive))));
 365       //cout << "p1= " << p1 << "\n";
 366       //cout << "p2= " << p2 << "\n";
 367       bool r= join (p1, p2, the_et);
 368       //cout << "pr= " << p1 << "\n";
 369       if (r) {
 370         //cout << "\n\nSimplify\n";
 371         //show_all ();
 372         patch un= patch (p1, cdr (get_undo (cdr (get_undo (archive)))));
 373         patch re= get_redo (archive);
 374         archive= make_history (un, re);
 375         //show_all ();
 376         //cout << "\n";
 377         if (depth == last_autosave + 1) last_autosave= -1;
 378         depth--;
 379         simplify ();
 380       }
 381     }
 382 }
 383
 384 /******************************************************************************
 385 * Undo and redo
 386 ******************************************************************************/
 387
 388 int
 389 archiver_rep::undo_possibilities () {
 390   return nr_undo (archive);
 391 }
 392
 393 int
 394 archiver_rep::redo_possibilities () {
 395   return nr_redo (archive);
 396 }
 397
 398 path
 399 archiver_rep::undo_one (int i) {
 400   if (active ()) return path ();
 401   if (undo_possibilities () != 0) {
 402     ASSERT (i == 0, "index out of range");
 403     patch p= car (get_undo (archive));
 404     //cout << "p= " << p << "\n";
 405     ASSERT (is_applicable (p, the_et), "history corrupted");
 406     patch q= invert (p, the_et);
 407     //cout << "q= " << q << "\n";
 408     apply (p);
 409     patch re1= patch (q, get_redo (archive));
 410     patch nx = cdr (get_undo (archive));
 411     patch re2= get_redo (nx);
 412     patch re = append_branches (re1, re2);
 413     patch un = (nr_branches (nx) == 0? nx: get_undo (nx));
 414     archive= make_history (un, re);
 415     depth--;
 416     //show_all ();
 417     return cursor_hint (q, the_et);
 418   }
 419   return path ();
 420 }
 421
 422 path
 423 archiver_rep::redo_one (int i) {
 424   if (active ()) return path ();
 425   int n= redo_possibilities ();
 426   if (n != 0) {
 427     ASSERT (i >= 0 && i < n, "index out of range");
 428     patch un= get_undo (archive);
 429     patch re= get_redo (archive);
 430     patch p= car (branch (re, i));
 431     //cout << "p= " << p << "\n";
 432     ASSERT (is_applicable (p, the_et), "future corrupted");
 433     patch q= invert (p, the_et);
 434     //cout << "q= " << q << "\n";
 435     apply (p);
 436     patch other= make_branches (append (branches (re, 0, i),
 437                                         branches (re, i+1, n)));
 438     //cout << "other= " << other << "\n";
 439     patch nx= make_history (un, other);
 440     archive= make_history (patch (q, nx), cdr (branch (re, i)));
 441     if (depth <= last_save && i != 0) last_save= -1;
 442     if (depth <= last_autosave && i != 0) last_autosave= -1;
 443     depth++;
 444     normalize ();
 445     //show_all ();
 446     return cursor_hint (q, the_et);
 447   }
 448   return path ();
 449 }
 450
 451 path
 452 archiver_rep::undo (int i) {
 453   if (active ()) return path ();
 454   path r;
 455   while (undo_possibilities () != 0) {
 456     ASSERT (i == 0, "index out of range");
 457     expose ();
 458     if (get_author (car (get_undo (archive))) == the_author)
 459       return undo_one (i);
 460     else {
 461       r= undo_one (i);
 462       i= 0;
 463     }
 464   }
 465   return r;
 466 }
 467
 468 path
 469 archiver_rep::redo (int i) {
 470   if (active ()) return path ();
 471   path r;
 472   bool first= true;
 473   while (redo_possibilities () != 0) {
 474     ASSERT (i >= 0 && i < redo_possibilities (), "index out of range");
 475     patch re= branch (get_redo (archive), i);
 476     bool done= (get_author (car (re)) == the_author);
 477     r= redo_one (i);
 478     if (done && !first) break;
 479     if (nr_redo (archive) != 1) break;
 480     i= 0;
 481     first= false;
 482     re= branch (get_redo (archive), i);
 483     if (get_author (car (re)) == the_author) break;
 484     if (done && genuine_authors->contains (get_author (car (re)))) break;
 485   }
 486   return r;
 487 }
 488
 489 /******************************************************************************
 490 * Marking blocks for grouped modifications or canceling
 491 ******************************************************************************/
 492
 493 static bool
 494 is_marker (patch p, double m, bool birth) {
 495   if (get_type (p) == PATCH_AUTHOR)
 496     return is_marker (p[0], m, birth);
 497   else if (get_type (p) == PATCH_BIRTH)
 498     return get_author (p) == m && get_birth (p) == birth;
 499   else return false;
 500 }
 501
 502 static patch
 503 remove_marker (patch archive, double m) {
 504   ASSERT (nr_undo (archive) != 0, "marker not found");
 505   if (is_marker (car (get_undo (archive)), m, false)) {
 506     ASSERT (nr_redo (archive) == 0, "cannot remove marker");
 507     return cdr (get_undo (archive));
 508   }
 509   else {
 510     patch un= get_undo (archive);
 511     patch re= get_redo (archive);
 512     return make_history (patch (car (un), remove_marker (cdr (un), m)), re);
 513   }
 514 }
 515
 516 void
 517 archiver_rep::mark_start (double m) {
 518   //cout << "Mark start " << m << "\n";
 519   confirm ();
 520   start_slave (m);
 521   confirm ();
 522   //show_all ();
 523 }
 524
 525 void
 526 archiver_rep::mark_end (double m) {
 527   //cout << "Mark end " << m << "\n";
 528   archive= remove_marker (archive, m);
 529   depth--;
 530   simplify ();
 531   //show_all ();
 532 }
 533
 534 bool
 535 archiver_rep::mark_cancel (double m) {
 536   //cout << "Mark cancel " << m << "\n";
 537   cancel ();
 538   while (nr_undo (archive) != 0) {
 539     expose ();
 540     if (is_marker (car (get_undo (archive)), m, false)) {
 541       archive= remove_marker (archive, m);
 542       depth--;
 543       simplify ();
 544       return true;
 545     }
 546     if (get_author (car (get_undo (archive))) != the_author) {
 547       archive= remove_marker (archive, m);
 548       depth--;
 549       return false;
 550     }
 551     retract ();
 552     cancel ();
 553   }
 554   return false;
 555 }
 556
 557 /******************************************************************************
 558 * Check changes since last save/autosave
 559 ******************************************************************************/
 560
 561 int
 562 archiver_rep::corrected_depth () {
 563   // NOTE : fix depth due to presence of marker
 564   // FIXME: implement a more robust check for conformity with saved state
 565   if (nr_undo (archive) == 0) return depth;
 566   patch p= car (get_undo (archive));
 567   if (get_type (p) == PATCH_AUTHOR) p= p[0];
 568   if (get_type (p) == PATCH_BIRTH && get_birth (p) == false) return depth - 1;
 569   return depth;
 570 }
 571
 572 void
 573 archiver_rep::require_save () {
 574   last_save= -1;
 575 }
 576
 577 void
 578 archiver_rep::notify_save () {
 579   last_save= corrected_depth ();
 580 }
 581
 582 bool
 583 archiver_rep::conform_save () {
 584   return last_save == corrected_depth ();
 585 }
 586
 587 void
 588 archiver_rep::require_autosave () {
 589   last_autosave= -1;
 590 }
 591
 592 void
 593 archiver_rep::notify_autosave () {
 594   last_autosave= depth;
 595 }
 596
 597 bool
 598 archiver_rep::conform_autosave () {
 599   return last_autosave == depth;
 600 }