Back to index

texmacs  1.0.7.15
archiver.cpp
Go to the documentation of this file.
00001 
00002 /******************************************************************************
00003 * MODULE     : archiver.cpp
00004 * DESCRIPTION: manage undo/redo history
00005 * COPYRIGHT  : (C) 2009  Joris van der Hoeven
00006 *******************************************************************************
00007 * This software falls under the GNU general public license version 3 or later.
00008 * It comes WITHOUT ANY WARRANTY WHATSOEVER. For details, see the file LICENSE
00009 * in the root directory or <http://www.gnu.org/licenses/gpl-3.0.html>.
00010 ******************************************************************************/
00011 
00012 #include "archiver.hpp"
00013 #include "hashset.hpp"
00014 #include "iterator.hpp"
00015 
00016 extern tree the_et;
00017 array<patch> singleton (patch p);
00018 static patch make_compound (array<patch> a);
00019 static patch make_branches (array<patch> a);
00020 static hashset<double> genuine_authors;
00021 static hashset<pointer> archs;
00022 static hashset<pointer> pending_archs;
00023 
00024 /******************************************************************************
00025 * Constructors, destructors, printing and announcements
00026 ******************************************************************************/
00027 
00028 archiver_rep::archiver_rep (double author, path rp2):
00029   archive (make_branches (0)),
00030   current (make_compound (0)),
00031   depth (0),
00032   last_save (0),
00033   last_autosave (0),
00034   the_author (author),
00035   the_owner (0),
00036   rp (rp2),
00037   undo_obs (undo_observer (this)),
00038   versioning (false)
00039 {
00040   archs->insert ((pointer) this);
00041   attach_observer (subtree (the_et, rp), undo_obs);
00042   genuine_authors->insert (the_author);
00043 }
00044 
00045 archiver_rep::~archiver_rep () {
00046   genuine_authors->remove (the_author);
00047   detach_observer (subtree (the_et, rp), undo_obs);
00048   archs->remove ((pointer) this);
00049   pending_archs->remove ((pointer) this);
00050 }
00051 
00052 archiver::archiver (double author, path rp):
00053   rep (tm_new<archiver_rep> (author, rp)) {}
00054 
00055 void
00056 archiver_rep::clear () {
00057   archive= make_branches (0);
00058   current= make_compound (0);
00059   the_owner= 0;
00060   depth= 0;
00061   last_save= -1;
00062   last_autosave= -1;
00063 }
00064 
00065 void
00066 archiver_rep::show_all () {
00067   cout << HRULE << archive << LF << HRULE << LF;
00068 }
00069 
00071 
00072 void
00073 archive_announce (archiver_rep* arch, modification mod) {
00074   //cout << "Archive " << mod << "\n";
00076   if (DEBUG_HISTORY) cout << "Archive " << mod << "\n";
00077   ASSERT (arch->rp <= mod->p, "invalid modification");
00078   if (!arch->versioning) {
00079     arch->add (mod);
00080     pending_archs->insert ((pointer) arch);
00081   }
00082 }
00083 
00084 void
00085 global_clear_history () {
00086   iterator<pointer> it = iterate (archs);
00087   while (it->busy()) {
00088     archiver_rep* arch= (archiver_rep*) it->next();
00089     arch->clear ();
00090   }
00091 }
00092 
00093 void
00094 global_confirm () {
00095   iterator<pointer> it = iterate (pending_archs);
00096   while (it->busy()) {
00097     archiver_rep* arch= (archiver_rep*) it->next();
00098     arch->confirm ();
00099     arch->simplify ();
00100   }
00101   pending_archs= hashset<pointer> ();
00102 }
00103 
00104 /******************************************************************************
00105 * Useful subroutines
00106 ******************************************************************************/
00107 
00108 static patch
00109 make_compound (array<patch> a) {
00110   if (N(a) == 1) return a[0];
00111   else return patch (false, a);
00112 }
00113 
00114 static patch
00115 make_branches (array<patch> a) {
00116   if (N(a) == 1) return a[0];
00117   else return patch (true, a);
00118 }
00119 
00120 static patch
00121 append_branches (patch p1, patch p2) {
00122   return make_branches (append (branches (p1), branches (p2)));
00123 }
00124 
00125 static patch
00126 make_history (patch undo, patch redo) {
00127   array<patch> a;
00128   a << undo << branches (redo);
00129   return make_branches (a);
00130 }
00131 
00132 static int
00133 nr_undo (patch p) {
00134   if (nr_branches (p) == 0 || nr_children (branch (p, 0)) != 2) return 0;
00135   return 1;
00136 }
00137 
00138 static int
00139 nr_redo (patch p) {
00140   return max (0, nr_branches (p) - 1);
00141 }
00142 
00143 static patch
00144 get_undo (patch p) {
00145   ASSERT (nr_branches (p) > 0, "undo part unavailable");
00146   return branch (p, 0);
00147 }
00148 
00149 static patch
00150 get_redo (patch p) {
00151   if (nr_branches (p) == 0) return make_branches (array<patch> ());
00152   return make_branches (branches (p, 1, nr_branches (p)));
00153 }
00154 
00155 static patch
00156 car (patch p) {
00157   ASSERT (nr_children (branch (p, 0)) == 2, "car unavailable")
00158   return child (p, 0);
00159 }
00160 
00161 static patch
00162 cdr (patch p) {
00163   ASSERT (nr_children (branch (p, 0)) == 2, "cdr unavailable")
00164   return child (p, 1);
00165 }
00166 
00167 /******************************************************************************
00168 * Internal subroutines
00169 ******************************************************************************/
00170 
00171 void
00172 archiver_rep::apply (patch p) {
00173   // apply a patch, while disabling versioning during the modifications
00174   // cout << "Apply " << p << "\n";
00175   ASSERT (is_applicable (p, the_et), "invalid history");
00176   bool old= versioning;
00177   versioning= true;
00178   ::apply (p, the_et);
00179   versioning= old;
00180 }
00181 
00182 void
00183 archiver_rep::split (patch p1, patch p2, patch& re1, patch& re2) {
00184   //cout << "p1= " << p1 << "\n";
00185   //cout << "p2= " << p2 << "\n";
00186   array<patch> a= branches (p2);
00187   array<patch> a1;
00188   array<patch> a2;
00189   for (int i=0; i<N(a); i++) {
00190     patch q1= p1;
00191     patch q2= car (a[i]);
00192     if (get_author (q2) != the_author || !swap (q1, q2)) a1 << a[i];
00193     else a2 << patch (q1, make_future (q2, cdr (a[i])));
00194   }
00195   re1= make_branches (a1);
00196   re2= make_branches (a2);
00197   //cout << "re1= " << re1 << "\n";
00198   //cout << "re2= " << re2 << "\n";
00199 }
00200 
00201 patch
00202 archiver_rep::make_future (patch p1, patch p2) {
00203   if (nr_branches (p2) == 0 || get_author (p1) == the_author)
00204     return patch (p1, p2);
00205   patch re1, re2;
00206   split (p1, p2, re1, re2);
00207   if (nr_branches (re1) != 0) re1= patch (p1, re1);
00208   return append_branches (re1, re2);
00209 }
00210 
00211 patch
00212 archiver_rep::expose (patch archive) {
00213   if (nr_undo (archive) != 0 &&
00214       get_author (car (get_undo (archive))) != the_author &&
00215       nr_undo (cdr (get_undo (archive))) != 0)
00216     {
00217       patch nx1= expose (cdr (get_undo (archive)));
00218       if (get_author (car (get_undo (nx1))) != the_author) return archive;
00219       patch un1= car (get_undo (archive));
00220       patch un2= car (get_undo (nx1));
00221       patch re1= get_redo (archive);
00222       patch re2= get_redo (nx1);
00223       patch nx2= cdr (get_undo (nx1));
00224       patch fut= make_branches (0);
00225       if (nr_branches (re2) != 0) fut= make_future (un1, re2);
00226       if (!swap (un1, un2)) return archive;
00227       patch nx= make_history (patch (un2, nx2), make_branches (0));
00228       patch un= patch (un1, nx);
00229       patch re= append_branches (re1, fut);
00230       last_save= last_autosave= -1;
00231       return make_history (un, re);
00232     }
00233   else return archive;
00234 }
00235 
00236 void
00237 archiver_rep::expose () {
00238   archive= expose (archive);
00239 }
00240 
00241 void
00242 archiver_rep::normalize () {
00243   if (nr_undo (archive) != 0 && nr_redo (cdr (get_undo (archive))) != 0) {
00244     patch un1= get_undo (archive);
00245     patch re1= get_redo (archive);
00246     patch p1 = car (un1);
00247     patch nx1= cdr (un1);
00248     patch un2= get_undo (nx1);
00249     patch re2= get_redo (nx1);
00250     patch Re1, Re2;
00251     if (get_author (p1) == the_author) return;
00252     split (p1, re2, Re1, Re2);
00253     patch ar2= make_history (un2, Re1);
00254     archive= make_history (patch (p1, ar2), append_branches (re1, Re2));
00255     last_save= last_autosave= -1;
00256   }
00257 }
00258 
00259 /******************************************************************************
00260 * Routines concerning the current modifications
00261 ******************************************************************************/
00262 
00263 void
00264 archiver_rep::add (modification m) {
00265   m= copy (m);
00266   if (the_owner != 0 && the_owner != get_author ()) {
00267     //cout << "Change " << the_owner << " -> " << get_author () << "\n";
00268     confirm ();
00269   }
00270   else the_owner= get_author ();
00271   modification i= invert (m, the_et);
00272   patch q (i, m);
00273   //cout << "Add [" << the_owner << "] " << q << "\n";
00274   current= patch (q, current);
00275 }
00276 
00277 void
00278 archiver_rep::start_slave (double a) {
00279   if (the_owner != 0 && the_owner != get_author ()) {
00280     //cout << "Change " << the_owner << " -> " << get_author () << "\n";
00281     confirm ();
00282   }
00283   else the_owner= get_author ();
00284   patch q (a, false);
00285   //cout << "Add [" << the_owner << "] " << q << "\n";
00286   current= patch (q, current);
00287 }
00288 
00289 bool
00290 archiver_rep::active () {
00291   return nr_children (current) != 0;
00292 }
00293 
00294 bool
00295 archiver_rep::has_history () {
00296   return nr_undo (archive) == 1;
00297 }
00298 
00299 void
00300 archiver_rep::cancel () {
00301   if (active ()) {
00302     //cout << "Cancel " << current << "\n";
00303     apply (current);
00304     current= make_compound (0);
00305     the_owner= 0;
00306   }
00307 }
00308 
00309 void
00310 archiver_rep::confirm () {
00311   if (active ()) {
00312     current= patch (the_owner, compactify (current));
00313     if (nr_children (remove_set_cursor (current)) == 0)
00314       current= make_compound (0);
00315     if (active ()) {
00316       //cout << "Confirm " << current << "\n";
00317       archive= patch (current, archive);
00318       current= make_compound (0);
00319       the_owner= 0;
00320       depth++;
00321       if (depth <= last_save) last_save= -1;
00322       if (depth <= last_autosave) last_autosave= -1;
00323       normalize ();
00324       //show_all ();
00325     }
00326   }
00327 }
00328 
00329 bool
00330 archiver_rep::retract () {
00331   if (!has_history ()) return false;
00332   if (the_owner != 0 && the_owner != the_author) return false;
00333   expose ();
00334   patch un= car (get_undo (archive));
00335   if (get_author (un) != the_author) return false;
00336   patch re= get_redo (archive);
00337   patch nx= cdr (get_undo (archive));
00338   //cout << "Retract " << un << "\n";
00339   if (active ()) current= compactify (patch (current, un));
00340   else current= un;
00341   the_owner= the_author;
00342   if (nr_branches (re) != 0) {
00343     patch q= invert (current, the_et);
00344     re= patch (q, re);
00345   }
00346   if (nr_branches (nx) != 0) nx= get_undo (nx);
00347   archive= make_history (nx, append_branches (re, get_redo (nx)));
00348   depth--;
00349   //show_all ();
00350   return true;
00351 }
00352 
00353 bool
00354 archiver_rep::forget () {
00355   cancel ();
00356   bool r= retract ();
00357   if (r) cancel ();
00358   return r;
00359 }
00360 
00361 void
00362 archiver_rep::forget_cursor () {
00363   current= remove_set_cursor (current);
00364 }
00365 
00366 /******************************************************************************
00367 * Simplification of the history
00368 ******************************************************************************/
00369 
00370 void
00371 archiver_rep::simplify () {
00372   if (has_history () &&
00373       nr_undo (cdr (get_undo (archive))) == 1 &&
00374       nr_redo (cdr (get_undo (archive))) == 0 &&
00375       depth != last_save + 1)
00376     {
00377       patch p1= car (get_undo (archive));
00378       patch p2= car (get_undo (cdr (get_undo (archive))));
00381       //cout << "p1= " << p1 << "\n";
00382       //cout << "p2= " << p2 << "\n";
00383       bool r= join (p1, p2, the_et);
00384       //cout << "pr= " << p1 << "\n";
00385       if (r) {
00386        //cout << "\n\nSimplify\n";
00387        //show_all ();
00388        patch un= patch (p1, cdr (get_undo (cdr (get_undo (archive)))));
00389        patch re= get_redo (archive);
00390        archive= make_history (un, re);
00391        //show_all ();
00392        //cout << "\n";
00393        if (depth == last_autosave + 1) last_autosave= -1;
00394        depth--;
00395        simplify ();
00396       }
00397     }
00398 }
00399 
00400 /******************************************************************************
00401 * Undo and redo
00402 ******************************************************************************/
00403 
00404 int
00405 archiver_rep::undo_possibilities () {
00406   return nr_undo (archive);
00407 }
00408 
00409 int
00410 archiver_rep::redo_possibilities () {
00411   return nr_redo (archive);
00412 }
00413 
00414 path
00415 archiver_rep::undo_one (int i) {
00416   if (active ()) return path ();
00417   if (undo_possibilities () != 0) {
00418     ASSERT (i == 0, "index out of range");
00419     patch p= car (get_undo (archive));
00420     ASSERT (is_applicable (p, the_et), "history corrupted");
00421     patch q= invert (p, the_et);
00422     apply (p);
00423     patch re1= patch (q, get_redo (archive));
00424     patch nx = cdr (get_undo (archive));
00425     patch re2= get_redo (nx);
00426     patch re = append_branches (re1, re2);
00427     patch un = (nr_branches (nx) == 0? nx: get_undo (nx));
00428     archive= make_history (un, re);
00429     depth--;
00430     //show_all ();
00431     return cursor_hint (q, the_et);
00432   }
00433   return path ();
00434 }
00435 
00436 path
00437 archiver_rep::redo_one (int i) {
00438   if (active ()) return path ();
00439   int n= redo_possibilities ();
00440   if (n != 0) {
00441     ASSERT (i >= 0 && i < n, "index out of range");
00442     patch un= get_undo (archive);
00443     patch re= get_redo (archive);
00444     patch p= car (branch (re, i));
00445     //cout << "p= " << p << "\n";
00446     ASSERT (is_applicable (p, the_et), "future corrupted");
00447     patch q= invert (p, the_et);
00448     //cout << "q= " << q << "\n";
00449     apply (p);
00450     patch other= make_branches (append (branches (re, 0, i),
00451                                    branches (re, i+1, n)));
00452     //cout << "other= " << other << "\n";
00453     patch nx= make_history (un, other);
00454     archive= make_history (patch (q, nx), cdr (branch (re, i)));
00455     if (depth <= last_save && i != 0) last_save= -1;
00456     if (depth <= last_autosave && i != 0) last_autosave= -1;
00457     depth++;
00458     normalize ();
00459     //show_all ();
00460     return cursor_hint (q, the_et);
00461   }
00462   return path ();
00463 }
00464 
00465 path
00466 archiver_rep::undo (int i) {
00467   if (active ()) return path ();
00468   path r;
00469   while (undo_possibilities () != 0) {
00470     ASSERT (i == 0, "index out of range");
00471     expose ();
00472     if (get_author (car (get_undo (archive))) == the_author)
00473       return undo_one (i);
00474     else {
00475       r= undo_one (i);
00476       i= 0;
00477     }
00478   }
00479   return r;
00480 }
00481 
00482 path
00483 archiver_rep::redo (int i) {
00484   if (active ()) return path ();
00485   path r;
00486   bool first= true;
00487   while (redo_possibilities () != 0) {
00488     ASSERT (i >= 0 && i < redo_possibilities (), "index out of range");
00489     patch re= branch (get_redo (archive), i);
00490     bool done= (get_author (car (re)) == the_author);
00491     r= redo_one (i);
00492     if (done && !first) break;
00493     if (nr_redo (archive) != 1) break;
00494     i= 0;
00495     first= false;
00496     re= branch (get_redo (archive), i);
00497     if (get_author (car (re)) == the_author) break;
00498     if (done && genuine_authors->contains (get_author (car (re)))) break;
00499   }
00500   return r;
00501 }
00502 
00503 /******************************************************************************
00504 * Marking blocks for grouped modifications or canceling
00505 ******************************************************************************/
00506 
00507 static bool
00508 is_marker (patch p, double m, bool birth) {
00509   if (get_type (p) == PATCH_AUTHOR)
00510     return is_marker (p[0], m, birth);
00511   else if (get_type (p) == PATCH_BIRTH)
00512     return get_author (p) == m && get_birth (p) == birth;
00513   else return false;
00514 }
00515 
00516 static patch
00517 remove_marker (patch archive, double m) {
00518   ASSERT (nr_undo (archive) != 0, "marker not found");
00519   if (is_marker (car (get_undo (archive)), m, false)) {
00520     ASSERT (nr_redo (archive) == 0, "cannot remove marker");
00521     return cdr (get_undo (archive));
00522   }
00523   else {
00524     patch un= get_undo (archive);
00525     patch re= get_redo (archive);
00526     return make_history (patch (car (un), remove_marker (cdr (un), m)), re);
00527   }
00528 }
00529 
00530 void
00531 archiver_rep::mark_start (double m) {
00532   //cout << "Mark start " << m << "\n";
00533   confirm ();
00534   start_slave (m);
00535   confirm ();
00536   //show_all ();
00537 }
00538 
00539 void
00540 archiver_rep::mark_end (double m) {
00541   //cout << "Mark end " << m << "\n";
00542   if (active ()) {
00543     //if (does_modify (current))
00544     //  cout << "CONFIRM: " << current << "\n";
00545     confirm ();
00546   }
00547   archive= remove_marker (archive, m);
00548   depth--;
00549   simplify ();
00550   //show_all ();
00551 }
00552 
00553 bool
00554 archiver_rep::mark_cancel (double m) {
00555   //cout << "Mark cancel " << m << "\n";
00556   cancel ();
00557   while (nr_undo (archive) != 0) {
00558     expose ();
00559     if (is_marker (car (get_undo (archive)), m, false)) {
00560       archive= remove_marker (archive, m);
00561       depth--;
00562       simplify ();
00563       return true;
00564     }
00565     if (get_author (car (get_undo (archive))) != the_author) {
00566       archive= remove_marker (archive, m);
00567       depth--;
00568       return false;
00569     }
00570     retract ();
00571     cancel ();
00572   }
00573   return false;
00574 }
00575 
00576 /******************************************************************************
00577 * Check changes since last save/autosave
00578 ******************************************************************************/
00579 
00580 int
00581 archiver_rep::corrected_depth () {
00582   // NOTE : fix depth due to presence of marker
00583   // FIXME: implement a more robust check for conformity with saved state
00584   if (nr_undo (archive) == 0) return depth;
00585   patch p= car (get_undo (archive));
00586   if (get_type (p) == PATCH_AUTHOR) p= p[0];
00587   if (get_type (p) == PATCH_BIRTH && get_birth (p) == false) return depth - 1;
00588   return depth;
00589 }
00590 
00591 void
00592 archiver_rep::require_save () {
00593   last_save= -1;
00594 }
00595 
00596 void
00597 archiver_rep::notify_save () {
00598   last_save= corrected_depth ();
00599 }
00600 
00601 bool
00602 archiver_rep::conform_save () {
00603   return last_save == corrected_depth ();
00604 }
00605 
00606 void
00607 archiver_rep::require_autosave () {
00608   last_autosave= -1;
00609 }
00610 
00611 void
00612 archiver_rep::notify_autosave () {
00613   last_autosave= depth;
00614 }
00615 
00616 bool
00617 archiver_rep::conform_autosave () {
00618   return last_autosave == depth;
00619 }