src/src/Data/History/commute.cpp

   1
   2 /******************************************************************************
   3 * MODULE     : commute.cpp
   4 * DESCRIPTION: Commutation of modifications
   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 "patch.hpp"
  13
  14 /******************************************************************************
  15 * Subroutines
  16 ******************************************************************************/
  17
  18 int
  19 insert_length (tree t) {
  20   if (is_atomic (t)) return N(t->label);
  21   else return N(t);
  22 }
  23
  24 static tree
  25 insert_range (tree t, int i, int len) {
  26   if (is_atomic (t)) return t->label (i, i+len);
  27   else return t (i, i+len);
  28 }
  29
  30 static modification
  31 dup (modification m) {
  32   return modification (m->k, copy (m->p), m->t);
  33 }
  34
  35 /******************************************************************************
  36 * Inversion of modifications
  37 ******************************************************************************/
  38
  39 modification
  40 invert (modification m, tree t) {
  41   ASSERT (is_applicable (t, m), "modification not applicable");
  42   path rp= root (m);
  43   switch (m->k) {
  44   case MOD_ASSIGN:
  45     return mod_assign (rp, subtree (t, rp));
  46   case MOD_INSERT:
  47     return mod_remove (rp, index (m), insert_length (m->t));
  48   case MOD_REMOVE:
  49     {
  50       int i= index (m);
  51       int n= argument (m);
  52       return mod_insert (rp, i, insert_range (subtree (t, rp), i, n));
  53     }
  54   case MOD_SPLIT:
  55     return mod_join (rp, index (m));
  56   case MOD_JOIN:
  57     {
  58       int  i= index (m);
  59       return mod_split (rp, i, insert_length (subtree (t, rp * i)));
  60     }
  61   case MOD_ASSIGN_NODE:
  62     return mod_assign_node (rp, L (subtree (t, rp)));
  63   case MOD_INSERT_NODE:
  64     return mod_remove_node (rp, argument (m));
  65   case MOD_REMOVE_NODE:
  66     {
  67       tree u= subtree (t, rp);
  68       int  i= index (m);
  69       return mod_insert_node (rp, i, u (0, i) * u (i+1, N(u)));
  70     }
  71   default:
  72     FAILED ("unexpected situation");
  73   }
  74 }
  75
  76 /******************************************************************************
  77 * Commutation of modifications
  78 ******************************************************************************/
  79
  80 static bool
  81 swap1 (modification& m1, modification& m2, int i, int d) {
  82   modification r1= dup (m2);
  83   modification r2= dup (m1);
  84   if (m2->p->item >= i)
  85     if (m2->p->item != i || !is_nil (root (m2)) || m2->k != MOD_INSERT)
  86       r1->p->item -= d;
  87   if (is_nil (root (m2)))
  88     switch (m2->k) {
  89     case MOD_INSERT:
  90       {
  91         int b2= m2->p->item;
  92         int e2= b2 + insert_length (m2->t);
  93         if (b2 <= i) r2->p->item += (e2-b2);
  94         break;
  95       }
  96     case MOD_REMOVE:
  97       {
  98         int b2= m2->p->item;
  99         int e2= b2 + m2->p->next->item;
 100         if (b2 <= i && i < e2)
 101           if (b2 != i || m1->k != MOD_REMOVE)
 102             return false;
 103         if (b2 < i) r2->p->item -= (e2-b2);
 104         break;
 105       }
 106     case MOD_SPLIT:
 107       if (m2->p->item < i) r2->p->item++;
 108       break;
 109     case MOD_JOIN:
 110       if (m2->p->item == i-1) return false;
 111       if (m2->p->item < i) r2->p->item--;
 112       break;
 113     case MOD_INSERT_NODE:
 114       {
 115         modification aux= m2;
 116         m2= modification (m1->k, path (m2->p->item, m1->p), m1->t);
 117         m1= aux;
 118         return true;
 119       }
 120     case MOD_REMOVE_NODE:
 121       return false;
 122     }
 123   m1= r1;
 124   m2= r2;
 125   return true;
 126 }
 127
 128 static bool
 129 swap2 (modification& m1, modification& m2, int i, int d) {
 130   modification r1= dup (m2);
 131   modification r2= dup (m1);
 132   if (m1->p->item >= i) r2->p->item += d;
 133   m1= r1;
 134   m2= r2;
 135   return true;
 136 }
 137
 138 bool
 139 swap_basic (modification& m1, modification& m2) {
 140   modification aux= m1;
 141   m1= m2;
 142   m2= aux;
 143   return true;
 144 }
 145
 146 bool
 147 swap (modification& m1, modification& m2) {
 148   path rp1= root (m1);
 149   path rp2= root (m2);
 150   if (is_nil (rp1))
 151     switch (m1->k) {
 152     case MOD_ASSIGN:
 153       {
 154         if (m1 == m2) return true;
 155         if (!is_nil (rp2) || m2->k != MOD_INSERT_NODE) return false;
 156         modification aux= m2;
 157         m2= modification (m1->k, path (m2->p->item, m1->p), m1->t);
 158         m1= aux;
 159         return true;
 160       }
 161     case MOD_INSERT:
 162       {
 163         if (is_nil (m2->p)) return false;
 164         int b= m1->p->item;
 165         int e= b + insert_length (m1->t);
 166         if (m2->p->item >= b && m2->p->item < e)
 167           if (!is_nil (root (m2)) || m2->p->item != b || m2->k != MOD_INSERT)
 168             if (!is_nil (root (m2)) || m2->k != MOD_INSERT_NODE)
 169               return false;
 170         return swap1 (m1, m2, b, e-b);
 171       }
 172     case MOD_REMOVE:
 173       {
 174         if (is_nil (m2->p)) return false;
 175         int i= m1->p->item;
 176         int d= m1->p->next->item;
 177         return swap1 (m1, m2, i, -d);
 178       }
 179     case MOD_SPLIT:
 180       {
 181         if (is_nil (m2->p)) return false;
 182         int i= m1->p->item;
 183         if (m2->p->item == i || m2->p->item == i+1)
 184           if (!is_nil (root (m2)) || m2->p->item != i || m2->k != MOD_INSERT)
 185             if (!is_nil (root (m2)) || m2->k != MOD_INSERT_NODE)
 186               return false;
 187         return swap1 (m1, m2, i, 1);
 188       }
 189     case MOD_JOIN:
 190       {
 191         if (is_nil (m2->p)) return false;
 192         int i= m1->p->item;
 193         if (m2->p->item == i)
 194           if (!is_nil (root (m2)) || m2->k != MOD_INSERT)
 195             return false;
 196         return swap1 (m1, m2, i, -1);
 197       }
 198     case MOD_ASSIGN_NODE:
 199       {
 200         if (!is_nil (root (m2))) return swap_basic (m1, m2);
 201         if (m1 == m2) return true;
 202         if (!is_nil (rp2) || m2->k != MOD_INSERT_NODE) return false;
 203         modification aux= m2;
 204         m2= modification (m1->k, path (m2->p->item, m1->p), m1->t);
 205         m1= aux;
 206         return true;
 207       }
 208     case MOD_INSERT_NODE:
 209       {
 210         if (is_nil (root (m2))) return false;
 211         if (m2->p->item != m1->p->item) return false;
 212         modification aux= m1;
 213         m1= modification (m2->k, m2->p->next, m2->t);
 214         if (m2->k != MOD_INSERT_NODE || !is_nil (root (m1))) m2= aux;
 215         else m2= modification (aux->k, path (m1->p->item, aux->p), aux->t);
 216         return true;
 217       }
 218     case MOD_REMOVE_NODE:
 219       {
 220         modification aux= m1;
 221         m1= modification (m2->k, path (m1->p->item, m2->p), m2->t);
 222         m2= aux;
 223         return true;
 224       }
 225     }
 226   else if (is_nil (rp2))
 227     switch (m2->k) {
 228     case MOD_ASSIGN:
 229       return false;
 230     case MOD_INSERT:
 231       {
 232         int b= m2->p->item;
 233         int e= b + insert_length (m2->t);
 234         return swap2 (m1, m2, b, e-b);
 235       }
 236     case MOD_REMOVE:
 237       {
 238         int b= m2->p->item;
 239         int e= b + m2->p->next->item;
 240         if (m1->p->item >= b && m1->p->item < e) return false;
 241         return swap2 (m1, m2, b, b-e);
 242       }
 243     case MOD_SPLIT:
 244       {
 245         int i= m2->p->item;
 246         if (m1->p->item == i) return false;
 247         return swap2 (m1, m2, i, 1);
 248       }
 249     case MOD_JOIN:
 250       {
 251         int i= m2->p->item;
 252         if (m1->p->item == i || m1->p->item == i+1) return false;
 253         return swap2 (m1, m2, i, -1);
 254       }
 255     case MOD_ASSIGN_NODE:
 256       return swap_basic (m1, m2);
 257     case MOD_INSERT_NODE:
 258       {
 259         modification aux= m2;
 260         m2= modification (m1->k, path (m2->p->item, m1->p), m1->t);
 261         m1= aux;
 262         return true;
 263       }
 264     case MOD_REMOVE_NODE:
 265       {
 266         if (m1->p->item != m2->p->item) return false;
 267         modification aux= m2;
 268         m2= modification (m1->k, m1->p->next, m1->t);
 269         m1= aux;
 270         return true;
 271       }
 272     }
 273   else if (rp1->item == rp2->item) {
 274     path h (rp1->item);
 275     modification s1= m1 / h;
 276     modification s2= m2 / h;
 277     bool r= swap (s1, s2);
 278     m1= h * s1;
 279     m2= h * s2;
 280     return r;
 281   }
 282   else return swap_basic (m1, m2);
 283 }
 284
 285 bool
 286 commute (modification m1, modification m2) {
 287   modification s1= m1;
 288   modification s2= m2;
 289   return swap (s1, s2);
 290 }
 291
 292 /******************************************************************************
 293 * Joining simple modifications when possible
 294 ******************************************************************************/
 295
 296 bool
 297 join (modification& m1, modification m2, tree t) {
 298   if (m1->k == MOD_INSERT &&
 299       m2->k == MOD_INSERT &&
 300       is_atomic (m1->t) &&
 301       root (m1) == root (m2) &&
 302       (index (m2) == index (m1) ||
 303        index (m2) == index (m1) + N (m1->t->label)))
 304     {
 305       string s= m1->t->label * m2->t->label;
 306       if (index (m2) == index (m1))
 307         s= m2->t->label * m1->t->label;
 308       m1= mod_insert (root (m1), index (m1), tree (s));
 309       return true;
 310     }
 311   if (m1->k == MOD_REMOVE &&
 312       m2->k == MOD_REMOVE &&
 313       is_atomic (subtree (t, root (m1))) &&
 314       root (m1) == root (m2) &&
 315       (index (m1) == index (m2) ||
 316        index (m1) == index (m2) + argument (m2)))
 317     {
 318       m1= mod_remove (root (m2), index (m2),
 319                       argument (m1) + argument (m2));
 320       return true;
 321     }
 322   return false;
 323 }
 324
 325 /******************************************************************************
 326 * Test routines
 327 ******************************************************************************/
 328
 329 #ifdef UNCOMMENTED
 330
 331 static modification
 332 test_modification (int i) {
 333   switch (i) {
 334   case  0: return mod_assign (path (), "Hi");
 335   case  1: return mod_insert (path (), 0, tree (TUPLE, "a", "b"));
 336   case  2: return mod_remove (path (), 0, 2);
 337   case  3: return mod_split (path (), 0, 1);
 338   case  4: return mod_join (path (), 0);
 339   case  5: return mod_assign_node (path (), TUPLE);
 340   case  6: return mod_insert_node (path (), 1, tree (TUPLE, "a", "b"));
 341   case  7: return mod_remove_node (path (), 0);
 342
 343   case  8: return mod_insert (path (), 1, tree (TUPLE, "a", "b"));
 344   case  9: return mod_insert (path (), 2, tree (TUPLE, "a", "b"));
 345   case 10: return mod_remove (path (), 1, 2);
 346   case 11: return mod_remove (path (), 2, 2);
 347   case 12: return mod_split (path (), 1, 2);
 348   case 13: return mod_split (path (), 2, 1);
 349   case 14: return mod_join (path (), 1);
 350   case 15: return mod_join (path (), 2);
 351   case 16: return mod_remove_node (path (), 1);
 352   case 17: return mod_remove_node (path (), 2);
 353
 354   case 18: case 19: case 20: case 21: case 22: case 23: case 24: case 25:
 355     return path (0) * test_modification (i-18);
 356   case 26: case 27: case 28: case 29: case 30: case 31: case 32: case 33:
 357     return path (1) * test_modification (i-26);
 358   case 34: case 35: case 36: case 37: case 38: case 39: case 40: case 41:
 359     return path (2) * test_modification (i-34);
 360   default:
 361     FAILED ("not implemented");
 362     return mod_assign (path (), "");
 363   }
 364 }
 365
 366 static tree
 367 test_tree (int i= 0, int d= 3) {
 368   // cout << "i= " << i << ", d= " << d << "\n";
 369   if (d == 0) return tree (as_string (i));
 370   else {
 371     int n= 6 + ((int) (2 * sin (1.0 * i * d)));
 372     tree t (TUPLE, n);
 373     for (int j=0; j<n; i++, j++)
 374       t[j]= test_tree (i, d-1);
 375     return t;
 376   }
 377 }
 378
 379 void
 380 test_commute () {
 381   tree tt= test_tree ();
 382   for (int i=0; i<42; i++)
 383     for (int j=0; j<42; j++) {
 384       modification m1= test_modification (i);
 385       modification m2= test_modification (j);
 386       modification t1= m1;
 387       modification t2= m2;
 388       cout << "m1  = " << m1 << "\n";
 389       cout << "m2  = " << m2 << "\n";
 390       bool r= swap (m1, m2);
 391       modification u1= m1;
 392       modification u2= m2;
 393       if (!r) cout << "  Modifications do not commute\n\n";
 394       else {
 395         cout << "m1' = " << m1 << "\n";
 396         cout << "m2' = " << m2 << "\n";
 397         if (clean_apply (clean_apply (tt, t1), t2) !=
 398             clean_apply (clean_apply (tt, m1), m2)) {
 399           cout << "t1  = " << clean_apply (clean_apply (tt, t1), t2) << "\n";
 400           cout << "t2  = " << clean_apply (clean_apply (tt, m1), m2) << "\n";
 401           FAILED ("inconsistency");
 402         }
 403         r= swap (m1, m2);
 404         if (!r) cout << "r   = " << r << "\n";
 405         else if (m1 != t1 || m2 != t2) {
 406           cout << "m1''= " << m1 << "\n";
 407           cout << "m2''= " << m2 << "\n";
 408           r= swap (m1, m2);
 409           if (!r) cout << "r   = " << r << "\n";
 410           else if (m1 != u1 || m2 != u2) {
 411             cout << "m1* = " << m1 << "\n";
 412             cout << "m2* = " << m2 << "\n";
 413             r= false;
 414           }
 415         }
 416         if (r) cout << "  Consistency check succeeded\n\n";
 417         else {
 418           cout << "  Consistency check failed\n\n";
 419           FAILED ("inconsistency");
 420         }
 421       }
 422     }
 423 }
 424
 425 void
 426 test_invert () {
 427   tree t1= test_tree ();
 428   for (int i=0; i<42; i++) {
 429     modification m1= test_modification (i);
 430     tree t2= clean_apply (t1, m1);
 431     modification m2= invert (m1, t1);
 432     tree t3= clean_apply (t2, m2);
 433     modification m3= invert (m2, t2);
 434     if (m1 != m3 || t1 != t3) {
 435       cout << "t1= " << t1 << "\n";
 436       cout << "m1= " << m1 << "\n";
 437       cout << "t2= " << t2 << "\n";
 438       cout << "m2= " << m2 << "\n";
 439       cout << "t3= " << t3 << "\n";
 440       FAILED ("inconsistency");
 441     }
 442  }
 443 }
 444
 445 #endif