Back to index

texmacs  1.0.7.15
patch.cpp
Go to the documentation of this file.
00001 
00002 /******************************************************************************
00003 * MODULE     : patch.cpp
00004 * DESCRIPTION: Routines on patches
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 "patch.hpp"
00013 
00014 int insert_length (tree t);
00015 
00016 /******************************************************************************
00017 * Concrete patches
00018 ******************************************************************************/
00019 
00020 class modification_patch_rep: public patch_rep {
00021   modification mod;
00022   modification inv;
00023 public:
00024   modification_patch_rep (modification mod2, modification inv2):
00025     mod (mod2), inv (inv2) {}
00026   int get_type () { return PATCH_MODIFICATION; }
00027   modification get_modification () { return mod; }
00028   modification get_inverse () { return inv; }
00029 };
00030 
00031 class compound_patch_rep: public patch_rep {
00032   array<patch> a;
00033 public:
00034   compound_patch_rep (array<patch> a2): a (a2) {}
00035   int get_type () { return PATCH_COMPOUND; }
00036   int get_arity () { return N(a); }
00037   patch get_child (int i) { return a[i]; }
00038 };
00039 
00040 class branch_patch_rep: public patch_rep {
00041   array<patch> a;
00042 public:
00043   branch_patch_rep (array<patch> a2): a (a2) {}
00044   int get_type () { return PATCH_BRANCH; }
00045   int get_arity () { return N(a); }
00046   patch get_child (int i) { return a[i]; }
00047 };
00048 
00049 class birth_patch_rep: public patch_rep {
00050   double author;
00051   bool birth;
00052 public:
00053   birth_patch_rep (double a2, bool b2): author (a2), birth (b2) {}
00054   int get_type () { return PATCH_BIRTH; }
00055   double get_author () { return author; }
00056   bool get_birth () { return birth; }
00057 };
00058 
00059 class author_patch_rep: public patch_rep {
00060   double author;
00061   patch p;
00062 public:
00063   author_patch_rep (double a2, patch p2): author (a2), p (p2) {}
00064   int get_type () { return PATCH_AUTHOR; }
00065   int get_arity () { return 1; }
00066   patch get_child (int i) {
00067     ASSERT (i == 0, "out of range");
00068     return p; }
00069   double get_author () { return author; }
00070 };
00071 
00072 patch::patch (modification mod, modification inv):
00073   rep (tm_new<modification_patch_rep> (mod, inv)) { rep->ref_count= 1; }
00074 patch::patch (array<patch> a):
00075   rep (tm_new<compound_patch_rep> (a)) { rep->ref_count= 1; }
00076 patch::patch (bool branch, array<patch> a):
00077   rep (branch?
00078        ((patch_rep*) tm_new<branch_patch_rep> (a)):
00079        ((patch_rep*) tm_new<compound_patch_rep> (a))) { rep->ref_count= 1; }
00080 patch::patch (patch p1, patch p2):
00081   rep (tm_new<compound_patch_rep> (array<patch>(p1,p2))) { rep->ref_count= 1; }
00082 patch::patch (double author, bool create):
00083   rep (tm_new<birth_patch_rep> (author, create)) { rep->ref_count= 1; }
00084 patch::patch (double author, patch p):
00085   rep (tm_new<author_patch_rep> (author, p)) { rep->ref_count= 1; }
00086 
00087 /******************************************************************************
00088 * Internal subroutines
00089 ******************************************************************************/
00090 
00091 array<patch>
00092 singleton (patch p) {
00093   array<patch> a (1);
00094   a[0]= p;
00095   return a;
00096 }
00097 
00098 static array<patch>
00099 get_array (patch p) {
00100   int i, n= N(p);
00101   array<patch> a (n);
00102   for (i=0; i<N(p); i++) a[i]= p[i];
00103   return a;
00104 }
00105 
00106 int
00107 nr_children (patch p) {
00108   if (get_type (p) != PATCH_COMPOUND) return 1;
00109   else return N(p);
00110 }
00111 
00112 patch
00113 child (patch p, int i) {
00114   ASSERT (0 <= i && i < nr_children (p), "index out of range");
00115   if (get_type (p) != PATCH_COMPOUND) return p;
00116   else return p[i];
00117 }
00118 
00119 array<patch>
00120 children (patch p) {
00121   if (get_type (p) != PATCH_COMPOUND) return singleton (p);
00122   else return get_array (p);
00123 }
00124 
00125 array<patch>
00126 children (patch p, int i, int j) {
00127   ASSERT (0 <= i && i <= nr_children (p), "index out of range");
00128   ASSERT (i <= j && j <= nr_children (p), "index out of range");
00129   return range (children (p), i, j);
00130 }
00131 
00132 int
00133 nr_branches (patch p) {
00134   if (get_type (p) != PATCH_BRANCH) return 1;
00135   else return N(p);
00136 }
00137 
00138 patch
00139 branch (patch p, int i) {
00140   ASSERT (0 <= i && i < nr_branches (p), "index out of range");
00141   if (get_type (p) != PATCH_BRANCH) return p;
00142   else return p[i];
00143 }
00144 
00145 array<patch>
00146 branches (patch p) {
00147   if (get_type (p) != PATCH_BRANCH) return singleton (p);
00148   else return get_array (p);
00149 }
00150 
00151 array<patch>
00152 branches (patch p, int i, int j) {
00153   ASSERT (0 <= i && i <= nr_branches (p), "index out of range");
00154   ASSERT (i <= j && j <= nr_branches (p), "index out of range");
00155   return range (branches (p), i, j);
00156 }
00157 
00158 /******************************************************************************
00159 * Author management
00160 ******************************************************************************/
00161 
00162 static double current_author= 0.0;
00163 
00164 double
00165 new_author () {
00166   static double next_author= 0.0;
00167   next_author += 1.0;
00168   return next_author;
00169 }
00170 
00171 double
00172 new_marker () {
00173   static double next_marker= 0.5;
00174   next_marker += 1.0;
00175   return next_marker;
00176 }
00177 
00178 void
00179 set_author (double a) {
00180   current_author= a;
00181 }
00182 
00183 double
00184 get_author () {
00185   return current_author;
00186 }
00187 
00188 /******************************************************************************
00189 * Common routines
00190 ******************************************************************************/
00191 
00192 tm_ostream&
00193 operator << (tm_ostream& out, patch p) {
00194   switch (get_type (p)) {
00195   case PATCH_MODIFICATION:
00196     out << get_modification (p) << " -- " << get_inverse (p);
00197     break;
00198   case PATCH_COMPOUND:
00199     if (N(p) == 0) out << "No children";
00200     else {
00201       out << "Composite" << INDENT;
00202       for (int i=0; i<N(p); i++)
00203        out << LF << p[i];
00204       out << UNINDENT;
00205     }
00206     break;
00207   case PATCH_BRANCH:
00208     if (N(p) == 0) out << "No branches";
00209     else for (int i=0; i<N(p); i++) {
00210       if (i != 0) out << LF;
00211       out << "Branch " << i << INDENT << LF << p[i] << UNINDENT;
00212     }
00213     break;
00214   case PATCH_BIRTH:
00215     if (get_birth (p)) out << "Birth ";
00216     else out << "Death ";
00217     out << get_author (p);
00218     break;
00219   case PATCH_AUTHOR:
00220     out << "Author " << get_author (p) << INDENT << LF;
00221     out << p[0];
00222     out << UNINDENT;
00223     break;
00224   default:
00225     FAILED ("unsupported patch type");
00226   }
00227   return out;
00228 }
00229 
00230 patch
00231 copy (patch p) {
00232   switch (get_type (p)) {
00233   case PATCH_MODIFICATION:
00234     return patch (copy (get_modification (p)), copy (get_inverse (p)));
00235   case PATCH_COMPOUND:
00236   case PATCH_BRANCH:
00237     {
00238       int i, n= N(p);
00239       array<patch> r (n);
00240       for (i=0; i<N(p); i++) r[i]= copy (p[i]);
00241       return patch (get_type (p) == PATCH_BRANCH, r);
00242     }
00243   case PATCH_BIRTH:
00244     return p;
00245   case PATCH_AUTHOR:
00246     return patch (get_author (p), copy (p[0]));
00247   default:
00248     FAILED ("unsupported patch type");
00249   }
00250   return p;
00251 }
00252 
00253 /******************************************************************************
00254 * Patch application
00255 ******************************************************************************/
00256 
00257 bool
00258 is_applicable (patch p, tree t) {
00259   switch (get_type (p)) {
00260   case PATCH_MODIFICATION:
00261     return is_applicable (t, get_modification (p));
00262   case PATCH_COMPOUND:
00263     for (int i=0; i<N(p); i++) {
00264       if (!is_applicable (p[i], t)) return false;
00265       t= clean_apply (p[i], t);
00266     }
00267     return true;
00268   case PATCH_BRANCH:
00269   case PATCH_AUTHOR:
00270     for (int i=0; i<N(p); i++)
00271       if (!is_applicable (p[i], t))
00272        return false;
00273     return true;
00274   case PATCH_BIRTH:
00275     return true;
00276   default:
00277     FAILED ("unsupported patch type");
00278     return false;
00279   }
00280 }
00281 
00282 tree
00283 clean_apply (patch p, tree t) {
00284   switch (get_type (p)) {
00285   case PATCH_MODIFICATION:
00286     return clean_apply (t, get_modification (p));
00287   case PATCH_BRANCH:
00288     ASSERT (N(p) <= 1, "ambiguous application");
00289   case PATCH_COMPOUND:
00290   case PATCH_AUTHOR:
00291     for (int i=0; i<N(p); i++)
00292       t= clean_apply (p[i], t);
00293     return t;
00294   case PATCH_BIRTH:
00295     return t;
00296   default:
00297     FAILED ("unsupported patch type");
00298     return t;
00299   }
00300 }
00301 
00302 void
00303 apply (patch p, tree& t) {
00304   switch (get_type (p)) {
00305   case PATCH_MODIFICATION:
00306     apply (t, get_modification (p));
00307     break;
00308   case PATCH_BRANCH:
00309     ASSERT (N(p) <= 1, "ambiguous application");
00310   case PATCH_COMPOUND:
00311   case PATCH_AUTHOR:
00312     for (int i=0; i<N(p); i++)
00313       apply (p[i], t);
00314     break;
00315   case PATCH_BIRTH:
00316     break;
00317   default:
00318     FAILED ("unsupported patch type");
00319   }
00320 }
00321 
00322 /******************************************************************************
00323 * Patch inversion
00324 ******************************************************************************/
00325 
00326 patch
00327 invert (patch p, tree t) {
00328   switch (get_type (p)) {
00329   case PATCH_MODIFICATION:
00330     return patch (get_inverse (p), get_modification (p));
00331   case PATCH_BRANCH:
00332     ASSERT (N(p) <= 1, "ambiguous application");
00333   case PATCH_COMPOUND:
00334     {
00335       int i, n=N(p);
00336       array<patch> r(n);
00337       for (i=0; i<n; i++) {
00338        r[n-1-i]= invert (p[i], t);
00339        t= clean_apply (p[i], t);
00340       }
00341       return patch (get_type (p) == PATCH_BRANCH, r);
00342     }
00343   case PATCH_BIRTH:
00344     return patch (get_author (p), !get_birth (p));
00345   case PATCH_AUTHOR:
00346     return patch (get_author (p), invert (p[0], t));
00347   default:
00348     FAILED ("unsupported patch type");
00349     return patch ();
00350   }
00351 }
00352 
00353 bool
00354 possible_inverse (modification m1, modification m2) {
00355   if (root (m1) != root (m2)) return false;
00356   switch (m1->k) {
00357   case MOD_ASSIGN:
00358     return m2->k == MOD_ASSIGN;
00359   case MOD_INSERT:
00360     return m2->k == MOD_REMOVE && 
00361            argument (m2) == insert_length (m1->t);
00362   case MOD_REMOVE:
00363     return m2->k == MOD_INSERT && 
00364            insert_length (m2->t) == argument (m1);
00365   case MOD_SPLIT:
00366     return m2->k == MOD_JOIN && 
00367            index (m2) == index (m1);
00368   case MOD_JOIN:
00369     return m2->k == MOD_SPLIT && 
00370            index (m2) == index (m1);
00371   case MOD_ASSIGN_NODE:
00372     return m2->k == MOD_ASSIGN_NODE;
00373   case MOD_INSERT_NODE:
00374     return m2->k == MOD_REMOVE_NODE && 
00375            index (m2) == argument (m1);
00376   case MOD_REMOVE_NODE:
00377     return m2->k == MOD_INSERT_NODE && 
00378            argument (m2) == index (m1);
00379   case MOD_SET_CURSOR:
00380     return m1 == m2;
00381   default:
00382     FAILED ("invalid situation");
00383     return false;
00384   }
00385 }
00386 
00387 /******************************************************************************
00388 * Commutation of patches
00389 ******************************************************************************/
00390 
00391 static bool
00392 swap_basic (patch& p1, patch& p2) {
00393   patch aux= p1;
00394   p1= p2;
00395   p2= aux;
00396   return true;
00397 }
00398 
00399 bool
00400 swap (patch& p1, patch& p2, double a1, double a2) {
00401   if (is_nil (p1) || is_nil (p2)) return false;
00402   if (get_type (p1) == PATCH_BRANCH)
00403     return false;
00404   if (get_type (p2) == PATCH_BRANCH)
00405     return false;
00406   if (get_type (p1) == PATCH_COMPOUND) {
00407     int n= N(p1);
00408     array<patch> a (n);
00409     for (int i=0; i<n; i++) a[i]= p1[i];
00410     for (int i=n-1; i>=0; i--) {
00411       if (!swap (a[i], p2, a1, a2)) return false;
00412       swap_basic (a[i], p2);
00413     }
00414     p1= p2;
00415     p2= patch (a);
00416     return true;
00417   }
00418   if (get_type (p2) == PATCH_COMPOUND) {
00419     int n= N(p2);
00420     array<patch> a (n);
00421     for (int i=0; i<n; i++) a[i]= p2[i];
00422     for (int i=0; i<n; i++) {
00423       if (!swap (p1, a[i], a1, a2)) return false;
00424       swap_basic (p1, a[i]);
00425     }
00426     p2= p1;
00427     p1= patch (a);
00428     return true;
00429   }
00430   if (get_type (p1) == PATCH_AUTHOR) {
00431     patch s= p1[0];
00432     bool r= swap (s, p2, get_author (p1), a2);
00433     p2= patch (get_author (p1), p2);
00434     p1= s;
00435     return r;
00436   }
00437   if (get_type (p2) == PATCH_AUTHOR) {
00438     patch s= p2[0];
00439     bool r= swap (p1, s, a1, get_author (p2));
00440     p1= patch (get_author (p2), p1);
00441     p2= s;
00442     return r;
00443   }
00444   if (get_type (p1) == PATCH_BIRTH) {
00445     if (get_author (p1) == a2) return false;
00446     return swap_basic (p1, p2);
00447   }
00448   if (get_type (p2) == PATCH_BIRTH) {
00449     if (get_author (p2) == a1) return false;
00450     return swap_basic (p1, p2);
00451   }
00452   if (get_type (p1) == PATCH_MODIFICATION &&
00453       get_type (p2) == PATCH_MODIFICATION)
00454     {
00455       modification m1= get_modification (p1);
00456       modification m2= get_modification (p2);
00457       modification i1= get_inverse (p1);
00458       modification i2= get_inverse (p2);
00459       bool r= swap (m1, m2);
00460       bool v= swap (i2, i1);
00461       p1= patch (m1, i1);
00462       p2= patch (m2, i2);
00463       return r && v && possible_inverse (m1, i1) && possible_inverse (m2, i2);
00464     }
00465   FAILED ("invalid situation");
00466   return false;
00467 }
00468 
00469 bool
00470 swap (patch& p1, patch& p2) {
00471   return swap (p1, p2, 0, 0);
00472 }
00473 
00474 bool
00475 commute (patch p1, patch p2) {
00476   patch s1= p1;
00477   patch s2= p2;
00478   return swap (s1, s2);
00479 }
00480 
00481 /******************************************************************************
00482 * Joining simple patches if possible
00483 ******************************************************************************/
00484 
00485 bool
00486 join (patch& p1, patch p2, tree t) {
00487   //cout << "Join " << p1 << LF << "with " << p2 << LF;
00488   if (get_type (p1) == PATCH_AUTHOR &&
00489       get_type (p2) == PATCH_AUTHOR &&
00490       get_author (p1) == get_author (p2))
00491     {
00492       double author= get_author (p1);
00493       patch q1= p1[0];
00494       patch q2= p2[0];
00495       bool r= join (q1, q2, t);
00496       if (r) p1= patch (author, q1);
00497       return r;
00498     }
00499   if (get_type (p1) == PATCH_MODIFICATION &&
00500       get_type (p2) == PATCH_MODIFICATION)
00501     {
00502       modification m1= get_modification (p1);
00503       modification m2= get_modification (p2);
00504       modification i2= get_inverse (p2);
00505       modification i1= get_inverse (p1);
00506       bool r= join (m1, m2, t);
00507       bool v= join (i2, i1, clean_apply (p2, clean_apply (p1, t)));
00508       if (r && v) p1= patch (m1, i2);
00509       return r && v;
00510     }
00511   if (get_type (p1) == PATCH_COMPOUND &&
00512       nr_children (p1) > 0 &&
00513       nr_children (remove_set_cursor (p1)) == 1 &&
00514       nr_children (p1[0]) == 1)
00515     {
00516       patch q= p1[0];
00517       bool rf= join (q, p2, t);
00518       if (rf) p1= q;
00519       return rf;
00520     }
00521   if (get_type (p2) == PATCH_COMPOUND &&
00522       nr_children (p2) > 0 &&
00523       nr_children (remove_set_cursor (p2)) == 1 &&
00524       nr_children (p2[0]) == 1)
00525     {
00526       patch q= p2[0];
00527       bool rf= join (p1, q, t);
00528       if (rf) {
00529         array<patch> a= children (p1);
00530         array<patch> b= children (p2);
00531         p1= patch (append (a, range (b, 1, N(b))));
00532       }
00533       return rf;
00534     }
00535   return false;
00536 }
00537 
00538 /******************************************************************************
00539 * Other routines
00540 ******************************************************************************/
00541 
00542 void
00543 insert (array<patch>& a, patch p) {
00544   if (get_type (p) == PATCH_COMPOUND) {
00545     int i, n= N(p);
00546     for (i=0; i<n; i++)
00547       insert (a, p[i]);
00548   }
00549   else if (get_type (p) == PATCH_MODIFICATION &&
00550           N(a) > 0 &&
00551           get_type (a[N(a)-1]) == PATCH_MODIFICATION &&
00552           (get_inverse (a[N(a)-1]) == get_modification (p) &&
00553            get_modification (a[N(a)-1]) == get_inverse (p)))
00554     {
00555       // cout << "Cancel " << a[N(a)-1] << " against " << p << "\n";
00556       a->resize (N(a) - 1);
00557     }
00558   else a << p;
00559 }
00560 
00561 patch
00562 compactify (patch p) {
00563   switch (get_type (p)) {
00564   case PATCH_COMPOUND:
00565     {
00566       double a= 0;
00567       for (int i=0; i<N(p); i++)
00568        if (get_type (p[i]) != PATCH_AUTHOR) a= -1;
00569        else if (a == 0) a= get_author (p[i]);
00570        else if (a != get_author (p[i])) a= -1;
00571       if (a <= 0) {
00572        array<patch> r;
00573        insert (r, p);
00574        if (N(r) == 1) return r[0];
00575        return patch (r);
00576       }
00577       else {
00578        array<patch> r;
00579        for (int i=0; i<N(p); i++) insert (r, p[i][0]);
00580        if (N(r) == 1) return patch (a, r[0]);
00581        return patch (a, patch (r));
00582       }
00583     }
00584   case PATCH_BRANCH:
00585     if (N(p) == 1) return p[0];
00586     else {
00587       int i, n= N(p);
00588       array<patch> r (n);
00589       for (i=0; i<n; i++) r[i]= compactify (p[i]);
00590       return patch (true, r);
00591     }
00592   case PATCH_AUTHOR:
00593     return patch (get_author (p), compactify (p[0]));
00594   }
00595   return p;
00596 }
00597 
00598 path
00599 cursor_hint (modification m, tree t) {
00600   ASSERT (is_applicable (t, m), "modification not applicable");
00601   path rp= root (m);
00602   tree st= subtree (t, rp);
00603   switch (m->k) {
00604   case MOD_ASSIGN:
00605     return end (t, rp);
00606   case MOD_INSERT:
00607     if (is_atomic (st)) return rp * index (m);
00608     else if (index (m) == N (st)) return end (t, rp);
00609     else return start (t, rp * index (m));
00610   case MOD_REMOVE:
00611     if (is_atomic (st)) return rp * (index (m) + argument (m));
00612     else if (index (m) == N (st)) return end (t, rp);
00613     else if (argument (m) == 0) return start (t, rp * index (m));
00614     else return end (t, rp * (index (m) + argument (m) - 1));
00615   case MOD_SPLIT:
00616     if (is_atomic (st [index (m)])) return m->p;
00617     else if (argument (m) == N (st [index (m)])) return end (t, rp * index(m));
00618     else return start (t, m->p);
00619   case MOD_JOIN:
00620     return end (t, m->p);
00621   case MOD_ASSIGN_NODE:
00622     return end (t, rp);
00623   case MOD_INSERT_NODE:
00624     return end (t, rp);
00625   case MOD_REMOVE_NODE:
00626     return end (t, rp * index (m));
00627   case MOD_SET_CURSOR:
00628     return path ();
00629   default:
00630     FAILED ("unexpected situation");
00631     return path ();
00632   }
00633 }
00634 
00635 path
00636 cursor_hint (patch p, tree t) {
00637   switch (get_type (p)) {
00638   case PATCH_MODIFICATION:
00639     return cursor_hint (get_modification (p), t);
00640   case PATCH_COMPOUND:
00641     for (int i=0; i<N(p); i++) {
00642       path r= cursor_hint (p[i], t);
00643       if (!is_nil (r)) return r;
00644     }
00645     return path ();
00646   case PATCH_BRANCH:
00647     if (N(p) == 0) return path ();
00648   case PATCH_AUTHOR:
00649     return cursor_hint (p[0], t);
00650   case PATCH_BIRTH:
00651     return path ();
00652   default:
00653     FAILED ("unsupported patch type");
00654   }
00655   return path ();
00656 }
00657 
00658 patch
00659 remove_set_cursor (patch p) {
00660   switch (get_type (p)) {
00661   case PATCH_MODIFICATION:
00662     if (get_modification (p)->k != MOD_SET_CURSOR) return copy (p);
00663     return patch (array<patch> ());
00664   case PATCH_COMPOUND:
00665     {
00666       array<patch> r;
00667       for (int i=0; i<N(p); i++) {
00668         patch q= remove_set_cursor (p[i]);
00669         r << children (q);
00670       }
00671       if (N(r) == 1) return r[0];
00672       return patch (r);
00673     }
00674   case PATCH_BRANCH:
00675   case PATCH_BIRTH:
00676     return copy (p);
00677   case PATCH_AUTHOR:
00678     {
00679       patch q= remove_set_cursor (p[0]);
00680       if (nr_children (q) == 0) return q;
00681       else return patch (get_author (p), q);
00682     }
00683   default:
00684     FAILED ("unsupported patch type");
00685   }
00686   return p;
00687 }
00688 
00689 bool
00690 does_modify (patch p) {
00691   switch (get_type (p)) {
00692   case PATCH_MODIFICATION:
00693     return get_modification (p)->k != MOD_SET_CURSOR;
00694   case PATCH_COMPOUND:
00695   case PATCH_BRANCH:
00696     for (int i=0; i<N(p); i++)
00697       if (does_modify (p[i]))
00698         return true;
00699     return false;
00700   case PATCH_BIRTH:
00701   case PATCH_AUTHOR:
00702     return false;
00703   default:
00704     return true;
00705   }
00706 }