Back to index

texmacs  1.0.7.15
commute.cpp
Go to the documentation of this file.
00001 
00002 /******************************************************************************
00003 * MODULE     : commute.cpp
00004 * DESCRIPTION: Commutation of modifications
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 /******************************************************************************
00015 * Subroutines
00016 ******************************************************************************/
00017 
00018 int
00019 insert_length (tree t) {
00020   if (is_atomic (t)) return N(t->label);
00021   else return N(t);
00022 }
00023 
00024 static tree
00025 insert_range (tree t, int i, int len) {
00026   if (is_atomic (t)) return t->label (i, i+len);
00027   else return t (i, i+len);
00028 }
00029 
00030 static modification
00031 dup (modification m) {
00032   return modification (m->k, copy (m->p), m->t);
00033 }
00034 
00035 /******************************************************************************
00036 * Inversion of modifications
00037 ******************************************************************************/
00038 
00039 modification
00040 invert (modification m, tree t) {
00041   ASSERT (is_applicable (t, m), "modification not applicable");
00042   path rp= root (m);
00043   switch (m->k) {
00044   case MOD_ASSIGN:
00045     return mod_assign (rp, copy (subtree (t, rp)));
00046   case MOD_INSERT:
00047     return mod_remove (rp, index (m), insert_length (m->t));
00048   case MOD_REMOVE:
00049     {
00050       int i= index (m);
00051       int n= argument (m);
00052       return mod_insert (rp, i, copy (insert_range (subtree (t, rp), i, n)));
00053     }
00054   case MOD_SPLIT:
00055     return mod_join (rp, index (m));
00056   case MOD_JOIN:
00057     {
00058       int  i= index (m);
00059       return mod_split (rp, i, insert_length (subtree (t, rp * i)));
00060     }
00061   case MOD_ASSIGN_NODE:
00062     return mod_assign_node (rp, L (subtree (t, rp)));
00063   case MOD_INSERT_NODE:
00064     return mod_remove_node (rp, argument (m));
00065   case MOD_REMOVE_NODE:
00066     {
00067       tree u= subtree (t, rp);
00068       int  i= index (m);
00069       return mod_insert_node (rp, i, copy (u (0, i) * u (i+1, N(u))));
00070     }
00071   case MOD_SET_CURSOR:
00072     return m;
00073   default:
00074     FAILED ("unexpected situation");
00075   }
00076 }
00077 
00078 /******************************************************************************
00079 * Commutation of modifications
00080 ******************************************************************************/
00081 
00082 static bool
00083 swap1 (modification& m1, modification& m2, int i, int d) {
00084   modification r1= dup (m2);
00085   modification r2= dup (m1);
00086   if (m2->p->item >= i)
00087     if (m2->p->item != i || !is_nil (root (m2)) || m2->k != MOD_INSERT)
00088       r1->p->item -= d;
00089   if (is_nil (root (m2)))
00090     switch (m2->k) {
00091     case MOD_INSERT:
00092       {
00093        int b2= m2->p->item;
00094        int e2= b2 + insert_length (m2->t);
00095        if (b2 <= i) r2->p->item += (e2-b2);
00096        break;
00097       }
00098     case MOD_REMOVE:
00099       {
00100        int b2= m2->p->item;
00101        int e2= b2 + m2->p->next->item;
00102        if (b2 <= i && i < e2)
00103          if (b2 != i || m1->k != MOD_REMOVE)
00104            return false;
00105        if (b2 < i) r2->p->item -= (e2-b2);
00106        break;
00107       }
00108     case MOD_SPLIT:
00109       if (m2->p->item < i) r2->p->item++;
00110       break;
00111     case MOD_JOIN:
00112       if (m2->p->item == i-1) return false;
00113       if (m2->p->item < i) r2->p->item--;
00114       break;
00115     case MOD_INSERT_NODE:
00116       {
00117        modification aux= m2;
00118        m2= modification (m1->k, path (m2->p->item, m1->p), m1->t);
00119        m1= aux;
00120        return true;
00121       }
00122     case MOD_REMOVE_NODE:
00123       return false;
00124     case MOD_SET_CURSOR:
00125       return false;
00126     }
00127   m1= r1;
00128   m2= r2;
00129   return true;
00130 }
00131 
00132 static bool
00133 swap2 (modification& m1, modification& m2, int i, int d) {
00134   modification r1= dup (m2);
00135   modification r2= dup (m1);
00136   if (m1->p->item >= i) r2->p->item += d;
00137   m1= r1;
00138   m2= r2;
00139   return true;
00140 }
00141 
00142 bool
00143 swap_basic (modification& m1, modification& m2) {
00144   modification aux= m1;
00145   m1= m2;
00146   m2= aux;
00147   return true;
00148 }
00149 
00150 bool
00151 swap (modification& m1, modification& m2) {
00152   path rp1= root (m1);
00153   path rp2= root (m2);
00154   if (is_nil (rp1))
00155     switch (m1->k) {
00156     case MOD_ASSIGN:
00157       {
00158        if (m1 == m2) return true;
00159        if (!is_nil (rp2) || m2->k != MOD_INSERT_NODE) return false;
00160        modification aux= m2;
00161        m2= modification (m1->k, path (m2->p->item, m1->p), m1->t);
00162        m1= aux;
00163        return true;
00164       }
00165     case MOD_INSERT:
00166       {
00167        if (is_nil (m2->p)) return false;
00168        int b= m1->p->item;
00169        int e= b + insert_length (m1->t);
00170        if (m2->p->item >= b && m2->p->item < e)
00171          if (!is_nil (root (m2)) || m2->p->item != b || m2->k != MOD_INSERT)
00172            if (!is_nil (root (m2)) || m2->k != MOD_INSERT_NODE)
00173              return false;
00174        return swap1 (m1, m2, b, e-b);
00175       }
00176     case MOD_REMOVE:
00177       {
00178        if (is_nil (m2->p)) return false;
00179        int i= m1->p->item;
00180        int d= m1->p->next->item;
00181        return swap1 (m1, m2, i, -d);
00182       }
00183     case MOD_SPLIT:
00184       {
00185        if (is_nil (m2->p)) return false;
00186        int i= m1->p->item;
00187        if (m2->p->item == i || m2->p->item == i+1)
00188          if (!is_nil (root (m2)) || m2->p->item != i || m2->k != MOD_INSERT)
00189            if (!is_nil (root (m2)) || m2->k != MOD_INSERT_NODE)
00190              return false;
00191        return swap1 (m1, m2, i, 1);
00192       }
00193     case MOD_JOIN:
00194       {
00195        if (is_nil (m2->p)) return false;
00196        int i= m1->p->item;
00197        if (m2->p->item == i)
00198          if (!is_nil (root (m2)) || m2->k != MOD_INSERT)
00199            return false;
00200        return swap1 (m1, m2, i, -1);
00201       }
00202     case MOD_ASSIGN_NODE:
00203       {
00204        if (!is_nil (root (m2))) return swap_basic (m1, m2);
00205        if (m1 == m2) return true;
00206        if (!is_nil (rp2) || m2->k != MOD_INSERT_NODE) return false;
00207        modification aux= m2;
00208        m2= modification (m1->k, path (m2->p->item, m1->p), m1->t);
00209        m1= aux;
00210        return true;
00211       }
00212     case MOD_INSERT_NODE:
00213       {
00214        if (is_nil (root (m2))) return false;
00215        if (m2->p->item != m1->p->item) return false;
00216        modification aux= m1;
00217        m1= modification (m2->k, m2->p->next, m2->t);
00218        if (m2->k != MOD_INSERT_NODE || !is_nil (root (m1))) m2= aux;
00219        else m2= modification (aux->k, path (m1->p->item, aux->p), aux->t);
00220        return true;
00221       }
00222     case MOD_REMOVE_NODE:
00223       {
00224        modification aux= m1;
00225        m1= modification (m2->k, path (m1->p->item, m2->p), m2->t);
00226        m2= aux;
00227        return true;
00228       }
00229     case MOD_SET_CURSOR:
00230       {
00231         if (!is_nil (rp2) ||
00232             m2->k == MOD_JOIN ||
00233             m2->k == MOD_SPLIT ||
00234             m2->k == MOD_ASSIGN_NODE)
00235           return swap_basic (m1, m2);
00236         return false;
00237       }
00238     }
00239   else if (is_nil (rp2))
00240     switch (m2->k) {
00241     case MOD_ASSIGN:
00242       return false;
00243     case MOD_INSERT:
00244       {
00245        int b= m2->p->item;
00246        int e= b + insert_length (m2->t);
00247        return swap2 (m1, m2, b, e-b);
00248       }
00249     case MOD_REMOVE:
00250       {
00251        int b= m2->p->item;
00252        int e= b + m2->p->next->item;
00253        if (m1->p->item >= b && m1->p->item < e) return false;
00254        return swap2 (m1, m2, b, b-e);
00255       }
00256     case MOD_SPLIT:
00257       {
00258        int i= m2->p->item;
00259        if (m1->p->item == i) return false;
00260        return swap2 (m1, m2, i, 1);
00261       }
00262     case MOD_JOIN:
00263       {
00264        int i= m2->p->item;
00265        if (m1->p->item == i || m1->p->item == i+1) return false;
00266        return swap2 (m1, m2, i, -1);
00267       }
00268     case MOD_ASSIGN_NODE:
00269       return swap_basic (m1, m2);
00270     case MOD_INSERT_NODE:
00271       {
00272        modification aux= m2;
00273        m2= modification (m1->k, path (m2->p->item, m1->p), m1->t);
00274        m1= aux;
00275        return true;
00276       }
00277     case MOD_REMOVE_NODE:
00278       {
00279        if (m1->p->item != m2->p->item) return false;
00280        modification aux= m2;
00281        m2= modification (m1->k, m1->p->next, m1->t);
00282        m1= aux;
00283        return true;
00284       }
00285     case MOD_SET_CURSOR:
00286       {
00287         if (!is_nil (rp1) ||
00288             m1->k == MOD_JOIN ||
00289             m1->k == MOD_SPLIT ||
00290             m1->k == MOD_ASSIGN_NODE)
00291           return swap_basic (m1, m2);
00292         return false;
00293       }
00294     }
00295   else if (rp1->item == rp2->item) {
00296     path h (rp1->item);
00297     modification s1= m1 / h;
00298     modification s2= m2 / h;
00299     bool r= swap (s1, s2);
00300     m1= h * s1;
00301     m2= h * s2;
00302     return r;
00303   }
00304   else return swap_basic (m1, m2);
00305   FAILED ("unexpected situation");
00306 }
00307 
00308 bool
00309 commute (modification m1, modification m2) {
00310   modification s1= m1;
00311   modification s2= m2;
00312   return swap (s1, s2);
00313 }
00314 
00315 /******************************************************************************
00316 * Joining simple modifications when possible
00317 ******************************************************************************/
00318 
00319 bool
00320 join (modification& m1, modification m2, tree t) {
00321   if (m1->k == MOD_INSERT &&
00322       m2->k == MOD_INSERT &&
00323       is_atomic (m1->t) &&
00324       root (m1) == root (m2) &&
00325       (index (m2) == index (m1) ||
00326        index (m2) == index (m1) + N (m1->t->label)))
00327     {
00328       string s= m1->t->label * m2->t->label;
00329       if (index (m2) == index (m1))
00330        s= m2->t->label * m1->t->label;
00331       m1= mod_insert (root (m1), index (m1), tree (s));
00332       return true;
00333     }
00334   if (m1->k == MOD_REMOVE &&
00335       m2->k == MOD_REMOVE &&
00336       is_atomic (subtree (t, root (m1))) &&
00337       root (m1) == root (m2) &&
00338       (index (m1) == index (m2) ||
00339        index (m1) == index (m2) + argument (m2)))
00340     {
00341       m1= mod_remove (root (m2), index (m2),
00342                     argument (m1) + argument (m2));
00343       return true;
00344     }
00345   return false;
00346 }
00347 
00348 /******************************************************************************
00349 * Test routines
00350 ******************************************************************************/
00351 
00352 #ifdef UNCOMMENTED
00353 
00354 static modification
00355 test_modification (int i) {
00356   switch (i) {
00357   case  0: return mod_assign (path (), "Hi");
00358   case  1: return mod_insert (path (), 0, tree (TUPLE, "a", "b"));
00359   case  2: return mod_remove (path (), 0, 2);
00360   case  3: return mod_split (path (), 0, 1);
00361   case  4: return mod_join (path (), 0);
00362   case  5: return mod_assign_node (path (), TUPLE);
00363   case  6: return mod_insert_node (path (), 1, tree (TUPLE, "a", "b"));
00364   case  7: return mod_remove_node (path (), 0);
00365 
00366   case  8: return mod_insert (path (), 1, tree (TUPLE, "a", "b"));
00367   case  9: return mod_insert (path (), 2, tree (TUPLE, "a", "b"));
00368   case 10: return mod_remove (path (), 1, 2);
00369   case 11: return mod_remove (path (), 2, 2);
00370   case 12: return mod_split (path (), 1, 2);
00371   case 13: return mod_split (path (), 2, 1);
00372   case 14: return mod_join (path (), 1);
00373   case 15: return mod_join (path (), 2);
00374   case 16: return mod_remove_node (path (), 1);
00375   case 17: return mod_remove_node (path (), 2);
00376 
00377   case 18: case 19: case 20: case 21: case 22: case 23: case 24: case 25:
00378     return path (0) * test_modification (i-18);
00379   case 26: case 27: case 28: case 29: case 30: case 31: case 32: case 33:
00380     return path (1) * test_modification (i-26);
00381   case 34: case 35: case 36: case 37: case 38: case 39: case 40: case 41:
00382     return path (2) * test_modification (i-34);
00383   default:
00384     FAILED ("not implemented");
00385     return mod_assign (path (), "");
00386   }
00387 }
00388 
00389 static tree
00390 test_tree (int i= 0, int d= 3) {
00391   // cout << "i= " << i << ", d= " << d << "\n";
00392   if (d == 0) return tree (as_string (i));
00393   else {
00394     int n= 6 + ((int) (2 * sin (1.0 * i * d)));
00395     tree t (TUPLE, n);
00396     for (int j=0; j<n; i++, j++)
00397       t[j]= test_tree (i, d-1);
00398     return t;
00399   }
00400 }
00401 
00402 void
00403 test_commute () {
00404   tree tt= test_tree ();
00405   for (int i=0; i<42; i++)
00406     for (int j=0; j<42; j++) {
00407       modification m1= test_modification (i);
00408       modification m2= test_modification (j);
00409       modification t1= m1;
00410       modification t2= m2;
00411       cout << "m1  = " << m1 << "\n";
00412       cout << "m2  = " << m2 << "\n";
00413       bool r= swap (m1, m2);
00414       modification u1= m1;
00415       modification u2= m2;
00416       if (!r) cout << "  Modifications do not commute\n\n";
00417       else {
00418        cout << "m1' = " << m1 << "\n";
00419        cout << "m2' = " << m2 << "\n";
00420        if (clean_apply (clean_apply (tt, t1), t2) !=
00421            clean_apply (clean_apply (tt, m1), m2)) {
00422          cout << "t1  = " << clean_apply (clean_apply (tt, t1), t2) << "\n";
00423          cout << "t2  = " << clean_apply (clean_apply (tt, m1), m2) << "\n";
00424          FAILED ("inconsistency");
00425        }
00426        r= swap (m1, m2);
00427        if (!r) cout << "r   = " << r << "\n";
00428        else if (m1 != t1 || m2 != t2) {
00429          cout << "m1''= " << m1 << "\n";
00430          cout << "m2''= " << m2 << "\n";
00431          r= swap (m1, m2);
00432          if (!r) cout << "r   = " << r << "\n";
00433          else if (m1 != u1 || m2 != u2) {
00434            cout << "m1* = " << m1 << "\n";
00435            cout << "m2* = " << m2 << "\n";
00436            r= false;
00437          }
00438        }
00439        if (r) cout << "  Consistency check succeeded\n\n";
00440        else {
00441          cout << "  Consistency check failed\n\n";
00442          FAILED ("inconsistency");
00443        }
00444       }
00445     }
00446 }
00447 
00448 void
00449 test_invert () {
00450   tree t1= test_tree ();
00451   for (int i=0; i<42; i++) {
00452     modification m1= test_modification (i);
00453     tree t2= clean_apply (t1, m1);
00454     modification m2= invert (m1, t1);
00455     tree t3= clean_apply (t2, m2);
00456     modification m3= invert (m2, t2);
00457     if (m1 != m3 || t1 != t3) {
00458       cout << "t1= " << t1 << "\n";
00459       cout << "m1= " << m1 << "\n";
00460       cout << "t2= " << t2 << "\n";
00461       cout << "m2= " << m2 << "\n";
00462       cout << "t3= " << t3 << "\n";
00463       FAILED ("inconsistency");
00464     }
00465  }
00466 }
00467 
00468 #endif