third-party/triemap/src/main/java/org/opendaylight/yangtools/triemap/INode.java

   1 /*
   2  * (C) Copyright 2016 Pantheon Technologies, s.r.o. and others.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16 package org.opendaylight.yangtools.triemap;
  17
  18 import java.util.Optional;
  19 import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;
  20
  21 final class INode<K, V> extends BasicNode {
  22     static final Object KEY_PRESENT = new Object ();
  23     static final Object KEY_ABSENT = new Object ();
  24
  25     /**
  26      * Virtual result for lookup methods indicating that the lookup needs to be restarted. This is a faster version
  27      * of throwing a checked exception to control the restart.
  28      */
  29     static final Object RESTART = new Object();
  30
  31     @SuppressWarnings("rawtypes")
  32     private static final AtomicReferenceFieldUpdater<INode, MainNode> MAINNODE_UPDATER =
  33             AtomicReferenceFieldUpdater.newUpdater(INode.class, MainNode.class, "mainnode");
  34
  35     private final Gen gen;
  36
  37     private volatile MainNode<K, V> mainnode;
  38
  39     INode(final Gen gen, final MainNode<K, V> mainnode) {
  40         this.gen = gen;
  41         this.mainnode = mainnode;
  42     }
  43
  44     MainNode<K, V> gcasRead(final TrieMap<K, V> ct) {
  45         return GCAS_READ(ct);
  46     }
  47
  48     MainNode<K, V> GCAS_READ(final TrieMap<K, V> ct) {
  49         MainNode<K, V> m = /* READ */ mainnode;
  50         MainNode<K, V> prevval = /* READ */ m.READ_PREV();
  51         if (prevval == null) {
  52             return m;
  53         }
  54
  55         return GCAS_Complete(m, ct);
  56     }
  57
  58     private MainNode<K, V> GCAS_Complete(MainNode<K, V> m, final TrieMap<K, V> ct) {
  59         while (true) {
  60             if (m == null) {
  61                 return null;
  62             }
  63
  64             // complete the GCAS
  65             final MainNode<K, V> prev = /* READ */ m.READ_PREV();
  66             final INode<K, V> ctr = ct.readRoot(true);
  67             if (prev == null) {
  68                 return m;
  69             }
  70
  71             if (prev instanceof FailedNode) {
  72                 // try to commit to previous value
  73                 FailedNode<K, V> fn = (FailedNode<K, V>) prev;
  74                 if (MAINNODE_UPDATER.compareAndSet(this, m, fn.READ_PREV())) {
  75                     return fn.READ_PREV();
  76                 }
  77
  78                 // Tail recursion: return GCAS_Complete (/* READ */ mainnode, ct);
  79                 m = /* READ */ mainnode;
  80                 continue;
  81             }
  82
  83             // Assume that you've read the root from the generation G.
  84             // Assume that the snapshot algorithm is correct.
  85             // ==> you can only reach nodes in generations <= G.
  86             // ==> `gen` is <= G.
  87             // We know that `ctr.gen` is >= G.
  88             // ==> if `ctr.gen` = `gen` then they are both equal to G.
  89             // ==> otherwise, we know that either `ctr.gen` > G, `gen` < G,
  90             // or both
  91             if (ctr.gen == gen && !ct.isReadOnly()) {
  92                 // try to commit
  93                 if (m.CAS_PREV(prev, null)) {
  94                     return m;
  95                 }
  96
  97                 // Tail recursion: return GCAS_Complete (m, ct);
  98                 continue;
  99             }
 100
 101             // try to abort
 102             m.CAS_PREV(prev, new FailedNode<>(prev));
 103
 104             // Tail recursion: return GCAS_Complete(/* READ */ mainnode, ct);
 105             m = /* READ */ mainnode;
 106         }
 107     }
 108
 109     private boolean GCAS(final MainNode<K, V> old, final MainNode<K, V> n, final TrieMap<K, V> ct) {
 110         n.WRITE_PREV(old);
 111         if (MAINNODE_UPDATER.compareAndSet(this, old, n)) {
 112             GCAS_Complete(n, ct);
 113             return /* READ */ n.READ_PREV() == null;
 114         }
 115
 116         return false;
 117     }
 118
 119     private INode<K, V> inode(final MainNode<K, V> cn) {
 120         return new INode<>(gen, cn);
 121     }
 122
 123     INode<K, V> copyToGen(final Gen ngen, final TrieMap<K, V> ct) {
 124         return new INode<>(ngen, GCAS_READ(ct));
 125     }
 126
 127     /**
 128      * Inserts a key value pair, overwriting the old pair if the keys match.
 129      *
 130      * @return true if successful, false otherwise
 131      */
 132     boolean rec_insert(final K k, final V v, final int hc, final int lev, final INode<K, V> parent,
 133             final TrieMap<K, V> ct) {
 134         return rec_insert(k, v, hc, lev, parent, gen, ct);
 135     }
 136
 137     private boolean rec_insert(final K k, final V v, final int hc, final int lev, final INode<K, V> parent,
 138             final Gen startgen, final TrieMap<K, V> ct) {
 139         while (true) {
 140             final MainNode<K, V> m = GCAS_READ (ct); // use -Yinline!
 141
 142             if (m instanceof CNode) {
 143                 // 1) a multiway node
 144                 final CNode<K, V> cn = (CNode<K, V>) m;
 145                 final int idx = (hc >>> lev) & 0x1f;
 146                 final int flag = 1 << idx;
 147                 final int bmp = cn.bitmap;
 148                 final int mask = flag - 1;
 149                 final int pos = Integer.bitCount(bmp & mask);
 150                 if ((bmp & flag) != 0) {
 151                     // 1a) insert below
 152                     final BasicNode cnAtPos = cn.array[pos];
 153                     if (cnAtPos instanceof INode) {
 154                         final INode<K, V> in = (INode<K, V>) cnAtPos;
 155                         if (startgen == in.gen) {
 156                             return in.rec_insert(k, v, hc, lev + 5, this, startgen, ct);
 157                         }
 158                         if (GCAS(cn, cn.renewed(startgen, ct), ct)) {
 159                             // Tail recursion: return rec_insert (k, v, hc, lev, parent, startgen, ct);
 160                             continue;
 161                         }
 162
 163                         return false;
 164                     } else if (cnAtPos instanceof SNode) {
 165                         final SNode<K, V> sn = (SNode<K, V>) cnAtPos;
 166                         if (sn.hc == hc && ct.equal(sn.k, k)) {
 167                             return GCAS(cn, cn.updatedAt(pos, new SNode<>(k, v, hc), gen), ct);
 168                         }
 169
 170                         final CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
 171                         final MainNode<K, V> nn = rn.updatedAt(pos, inode(CNode.dual(sn, sn.hc, new SNode<>(k, v, hc),
 172                                 hc, lev + 5, gen)), gen);
 173                         return GCAS (cn, nn, ct);
 174                     }
 175                 } else {
 176                     CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
 177                     MainNode<K, V> ncnode = rn.insertedAt(pos, flag, new SNode<> (k, v, hc), gen);
 178                     return GCAS (cn, ncnode, ct);
 179                 }
 180             } else if (m instanceof TNode) {
 181                 clean(parent, ct, lev - 5);
 182                 return false;
 183             } else if (m instanceof LNode) {
 184                 LNode<K, V> ln = (LNode<K, V>) m;
 185                 MainNode<K, V> nn = ln.inserted(k, v);
 186                 return GCAS(ln, nn, ct);
 187             } else {
 188                 throw new IllegalStateException("Unhandled node " + m);
 189             }
 190
 191             throw new RuntimeException ("Should not happen");
 192         }
 193     }
 194
 195     /**
 196      * Inserts a new key value pair, given that a specific condition is met.
 197      *
 198      * @param cond
 199      *            null - don't care if the key was there
 200      *            KEY_ABSENT - key wasn't there
 201      *            KEY_PRESENT - key was there
 202      *            other value `v` - key must be bound to `v`
 203      * @return null if unsuccessful, Option[V] otherwise (indicating
 204      *         previous value bound to the key)
 205      */
 206     Optional<V> rec_insertif(final K k, final V v, final int hc, final Object cond, final int lev,
 207             final INode<K, V> parent, final TrieMap<K, V> ct) {
 208         return rec_insertif(k, v, hc, cond, lev, parent, gen, ct);
 209     }
 210
 211     private Optional<V> rec_insertif(final K k, final V v, final int hc, final Object cond, final int lev,
 212             final INode<K, V> parent, final Gen startgen, final TrieMap<K, V> ct) {
 213         while (true) {
 214             final MainNode<K, V> m = GCAS_READ(ct); // use -Yinline!
 215
 216             if (m instanceof CNode) {
 217                 // 1) a multiway node
 218                 final CNode<K, V> cn = (CNode<K, V>) m;
 219                 final int idx = (hc >>> lev) & 0x1f;
 220                 final int flag = 1 << idx;
 221                 final int bmp = cn.bitmap;
 222                 final int mask = flag - 1;
 223                 final int pos = Integer.bitCount(bmp & mask);
 224
 225                 if ((bmp & flag) != 0) {
 226                     // 1a) insert below
 227                     final BasicNode cnAtPos = cn.array[pos];
 228                     if (cnAtPos instanceof INode) {
 229                         final INode<K, V> in = (INode<K, V>) cnAtPos;
 230                         if (startgen == in.gen) {
 231                             return in.rec_insertif(k, v, hc, cond, lev + 5, this, startgen, ct);
 232                         }
 233
 234                         if (GCAS(cn, cn.renewed(startgen, ct), ct)) {
 235                             // Tail recursion: return rec_insertif (k, v, hc, cond, lev, parent, startgen, ct);
 236                             continue;
 237                         }
 238
 239                         return null;
 240                     } else if (cnAtPos instanceof SNode) {
 241                         final SNode<K, V> sn = (SNode<K, V>) cnAtPos;
 242                         if (cond == null) {
 243                             if (sn.hc == hc && ct.equal(sn.k, k)) {
 244                                 if (GCAS(cn, cn.updatedAt(pos, new SNode<>(k, v, hc), gen), ct)) {
 245                                     return Optional.of(sn.v);
 246                                 }
 247
 248                                 return null;
 249                             }
 250
 251                             final CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
 252                             final MainNode<K, V> nn = rn.updatedAt(pos, inode (CNode.dual(sn, sn.hc,
 253                                     new SNode<>(k, v, hc), hc, lev + 5, gen)), gen);
 254                             if (GCAS(cn, nn, ct)) {
 255                                 return Optional.empty();
 256                             }
 257
 258                             return null;
 259                         } else if (cond == INode.KEY_ABSENT) {
 260                             if (sn.hc == hc && ct.equal(sn.k, k)) {
 261                                 return Optional.of(sn.v);
 262                             }
 263
 264                             final CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
 265                             final MainNode<K, V> nn = rn.updatedAt(pos, inode (CNode.dual(sn, sn.hc,
 266                                 new SNode<>(k, v, hc), hc, lev + 5, gen)), gen);
 267                             if (GCAS(cn, nn, ct)) {
 268                                 return Optional.empty();
 269                             }
 270
 271                             return null;
 272                         } else if (cond == INode.KEY_PRESENT) {
 273                             if (sn.hc == hc && ct.equal(sn.k, k)) {
 274                                 if (GCAS(cn, cn.updatedAt(pos, new SNode<>(k, v, hc), gen), ct)) {
 275                                     return Optional.of(sn.v);
 276                                 }
 277                                 return null;
 278                             }
 279
 280                             return Optional.empty();
 281                         } else {
 282                             if (sn.hc == hc && ct.equal(sn.k, k) && cond.equals(sn.v)) {
 283                                 if (GCAS(cn, cn.updatedAt(pos, new SNode<>(k, v, hc), gen), ct)) {
 284                                     return Optional.of(sn.v);
 285                                 }
 286
 287                                 return null;
 288                             }
 289
 290                             return Optional.empty();
 291                         }
 292                     }
 293                 } else if (cond == null || cond == INode.KEY_ABSENT) {
 294                     final CNode<K, V> rn = (cn.gen == gen) ? cn : cn.renewed(gen, ct);
 295                     final CNode<K, V> ncnode = rn.insertedAt (pos, flag, new SNode<>(k, v, hc), gen);
 296                     if (GCAS(cn, ncnode, ct)) {
 297                         return Optional.empty();
 298                     }
 299
 300                     return null;
 301                 } else if (cond == INode.KEY_PRESENT) {
 302                     return Optional.empty();
 303                 } else {
 304                     return Optional.empty();
 305                 }
 306             } else if (m instanceof TNode) {
 307                 clean(parent, ct, lev - 5);
 308                 return null;
 309             } else if (m instanceof LNode) {
 310                 // 3) an l-node
 311                 final LNode<K, V> ln = (LNode<K, V>) m;
 312                 if (cond == null) {
 313                     final Optional<V> optv = ln.get(k);
 314                     if (insertln(ln, k, v, ct)) {
 315                         return optv;
 316                     }
 317                     return null;
 318                 } else if (cond == INode.KEY_ABSENT) {
 319                     final Optional<V> t = ln.get(k);
 320                     if (t.isPresent()) {
 321                         return t;
 322                     }
 323                     if (insertln(ln, k, v, ct)) {
 324                         return Optional.empty();
 325                     }
 326                     return null;
 327                 } else if (cond == INode.KEY_PRESENT) {
 328                     final Optional<V> t = ln.get(k);
 329                     if (!t.isPresent()) {
 330                         return t;
 331                     }
 332                     if (insertln(ln, k, v, ct)) {
 333                         return t;
 334                     }
 335                     return null;
 336                 } else {
 337                     final Optional<V> t = ln.get(k);
 338                     if (t.isPresent()) {
 339                         if (cond.equals(t.get())) {
 340                             if (insertln(ln, k, v, ct)) {
 341                                 // Difference from Scala: we choose to reuse the object returned from LNode,
 342                                 // as the identity of the value does not matter in this call graph.
 343                                 return t;
 344                             }
 345
 346                             return null;
 347                         }
 348                     }
 349
 350                     return Optional.empty();
 351                 }
 352             } else {
 353                 throw new IllegalStateException("Unhandled node " + m);
 354             }
 355
 356             throw new RuntimeException("Should never happen");
 357         }
 358     }
 359
 360     boolean insertln(final LNode<K, V> ln, final K k, final V v, final TrieMap<K, V> ct) {
 361         final LNode<K, V> nn = ln.inserted (k, v);
 362         return GCAS(ln, nn, ct);
 363     }
 364
 365     /**
 366      * Looks up the value associated with the key.
 367      *
 368      * @return null if no value has been found, RESTART if the operation
 369      *         wasn't successful, or any other value otherwise
 370      */
 371     Object rec_lookup(final K k, final int hc, final int lev, final INode<K, V> parent, final TrieMap<K, V> ct) {
 372         return rec_lookup(k, hc, lev, parent, gen, ct);
 373     }
 374
 375     private Object rec_lookup(final K k, final int hc, final int lev, final INode<K, V> parent, final Gen startgen,
 376             final TrieMap<K, V> ct) {
 377         while (true) {
 378             final MainNode<K, V> m = GCAS_READ(ct); // use -Yinline!
 379
 380             if (m instanceof CNode) {
 381                 // 1) a multinode
 382                 final CNode<K, V> cn = (CNode<K, V>) m;
 383                 final int idx = (hc >>> lev) & 0x1f;
 384                 final int flag = 1 << idx;
 385                 final int bmp = cn.bitmap;
 386                 if ((bmp & flag) == 0) {
 387                     // 1a) bitmap shows no binding
 388                     return null;
 389                 }
 390
 391                 // 1b) bitmap contains a value - descend
 392                 final int pos = (bmp == 0xffffffff) ? idx : Integer.bitCount(bmp & (flag - 1));
 393                 final BasicNode sub = cn.array[pos];
 394                 if (sub instanceof INode) {
 395                     final INode<K, V> in = (INode<K, V>) sub;
 396                     if (ct.isReadOnly() || (startgen == in.gen)) {
 397                         return in.rec_lookup(k, hc, lev + 5, this, startgen, ct);
 398                     }
 399
 400                     if (GCAS(cn, cn.renewed(startgen, ct), ct)) {
 401                         // Tail recursion: return rec_lookup(k, hc, lev, parent, startgen, ct);
 402                         continue;
 403                     }
 404
 405                     // used to be throw RestartException
 406                     return RESTART;
 407                 } else if (sub instanceof SNode) {
 408                     // 2) singleton node
 409                     final SNode<K, V> sn = (SNode<K, V>) sub;
 410                     if (sn.hc == hc && ct.equal(sn.k, k)) {
 411                         return sn.v;
 412                     }
 413
 414                     return null;
 415                 }
 416             } else if (m instanceof TNode) {
 417                 // 3) non-live node
 418                 return cleanReadOnly((TNode<K, V>) m, lev, parent, ct, k, hc);
 419             } else if (m instanceof LNode) {
 420                 // 5) an l-node
 421                 return ((LNode<K, V>) m).get(k).orElse(null);
 422             } else {
 423                 throw new IllegalStateException("Unhandled node " + m);
 424             }
 425
 426             throw new RuntimeException ("Should not happen");
 427         }
 428     }
 429
 430     private Object cleanReadOnly(final TNode<K, V> tn, final int lev, final INode<K, V> parent,
 431             final TrieMap<K, V> ct, final K k, final int hc) {
 432         if (ct.isReadOnly()) {
 433             if (tn.hc == hc && ct.equal(tn.k, k)) {
 434                 return tn.v;
 435             }
 436
 437             return null;
 438         }
 439
 440         // used to be throw RestartException
 441         clean(parent, ct, lev - 5);
 442         return RESTART;
 443     }
 444
 445     /**
 446      * Removes the key associated with the given value.
 447      *
 448      * @param v
 449      *            if null, will remove the key regardless of the value;
 450      *            otherwise removes only if binding contains that exact key
 451      *            and value
 452      * @return null if not successful, an Option[V] indicating the previous
 453      *         value otherwise
 454      */
 455     Optional<V> rec_remove(final K k, final V v, final int hc, final int lev, final INode<K, V> parent,
 456             final TrieMap<K, V> ct) {
 457         return rec_remove(k, v, hc, lev, parent, gen, ct);
 458     }
 459
 460     private Optional<V> rec_remove(final K k, final V v, final int hc, final int lev, final INode<K, V> parent,
 461             final Gen startgen, final TrieMap<K, V> ct) {
 462         final MainNode<K, V> m = GCAS_READ(ct); // use -Yinline!
 463
 464         if (m instanceof CNode) {
 465             final CNode<K, V> cn = (CNode<K, V>) m;
 466             final int idx = (hc >>> lev) & 0x1f;
 467             final int bmp = cn.bitmap;
 468             final int flag = 1 << idx;
 469             if ((bmp & flag) == 0) {
 470                 return Optional.empty();
 471             }
 472
 473             final int pos = Integer.bitCount(bmp & (flag - 1));
 474             final BasicNode sub = cn.array[pos];
 475             Optional<V> res = null;
 476             if (sub instanceof INode) {
 477                 final INode<K, V> in = (INode<K, V>) sub;
 478                 if (startgen == in.gen) {
 479                     res = in.rec_remove(k, v, hc, lev + 5, this, startgen, ct);
 480                 } else {
 481                     if (GCAS(cn, cn.renewed (startgen, ct), ct)) {
 482                         res = rec_remove(k, v, hc, lev, parent, startgen, ct);
 483                     } else {
 484                         res = null;
 485                     }
 486                 }
 487
 488             } else if (sub instanceof SNode) {
 489                 final SNode<K, V> sn = (SNode<K, V>) sub;
 490                 if (sn.hc == hc && ct.equal(sn.k, k) && (v == null || v.equals(sn.v))) {
 491                     final MainNode<K, V> ncn = cn.removedAt(pos, flag, gen).toContracted(lev);
 492                     if (GCAS(cn, ncn, ct)) {
 493                         res = Optional.of(sn.v);
 494                     } else {
 495                         res = null;
 496                     }
 497                 } else {
 498                     res = Optional.empty();
 499                 }
 500             }
 501
 502             if (res == null || !res.isPresent()) {
 503                 return res;
 504             }
 505
 506             if (parent != null) {
 507                 // never tomb at root
 508                 final MainNode<K, V> n = GCAS_READ(ct);
 509                 if (n instanceof TNode) {
 510                     cleanParent(n, parent, ct, hc, lev, startgen);
 511                 }
 512             }
 513
 514             return res;
 515         } else if (m instanceof TNode) {
 516             clean(parent, ct, lev - 5);
 517             return null;
 518         } else if (m instanceof LNode) {
 519             final LNode<K, V> ln = (LNode<K, V>) m;
 520             if (v == null) {
 521                 final Optional<V> optv = ln.get(k);
 522                 final MainNode<K, V> nn = ln.removed(k, ct);
 523                 if (GCAS(ln, nn, ct)) {
 524                     return optv;
 525                 }
 526
 527                 return null;
 528             }
 529
 530             final Optional<V> tmp = ln.get(k);
 531             if (tmp.isPresent() && v.equals(tmp.get())) {
 532                 final MainNode<K, V> nn = ln.removed(k, ct);
 533                 if (GCAS(ln, nn, ct)) {
 534                     return tmp;
 535                 }
 536
 537                 return null;
 538             }
 539
 540             // Key not found or value does not match: we have not removed anything
 541             return Optional.empty();
 542         } else {
 543             throw new IllegalStateException("Unhandled node " + m);
 544         }
 545     }
 546
 547     private void cleanParent(final Object nonlive, final INode<K, V> parent, final TrieMap<K, V> ct, final int hc,
 548             final int lev, final Gen startgen) {
 549         while (true) {
 550             final MainNode<K, V> pm = parent.GCAS_READ(ct);
 551             if ((!(pm instanceof CNode))) {
 552                 // parent is no longer a cnode, we're done
 553                 return;
 554             }
 555
 556             final CNode<K, V> cn = (CNode<K, V>) pm;
 557             final int idx = (hc >>> (lev - 5)) & 0x1f;
 558             final int bmp = cn.bitmap;
 559             final int flag = 1 << idx;
 560             if ((bmp & flag) == 0) {
 561                 // somebody already removed this i-node, we're done
 562                 return;
 563             }
 564
 565             final int pos = Integer.bitCount(bmp & (flag - 1));
 566             final BasicNode sub = cn.array[pos];
 567             if (sub == this) {
 568                 if (nonlive instanceof TNode) {
 569                     final TNode<K, V> tn = (TNode<K, V>) nonlive;
 570                     MainNode<K, V> ncn = cn.updatedAt(pos, tn.copyUntombed(), gen).toContracted(lev - 5);
 571                     if (!parent.GCAS(cn, ncn, ct)) {
 572                         if (ct.readRoot().gen == startgen) {
 573                             // Tail recursion: cleanParent(nonlive, parent, ct, hc, lev, startgen);
 574                             continue;
 575                         }
 576                     }
 577                 }
 578             }
 579             break;
 580         }
 581     }
 582
 583     private void clean(final INode<K, V> nd, final TrieMap<K, V> ct, final int lev) {
 584         final MainNode<K, V> m = nd.GCAS_READ(ct);
 585         if (m instanceof CNode) {
 586             final CNode<K, V> cn = (CNode<K, V>) m;
 587             nd.GCAS(cn, cn.toCompressed(ct, lev, gen), ct);
 588         }
 589     }
 590
 591     int cachedSize(final TrieMap<K, V> ct) {
 592         MainNode<K, V> m = GCAS_READ(ct);
 593         return m.cachedSize(ct);
 594     }
 595
 596     // /* this is a quiescent method! */
 597     // def string(lev: Int) = "%sINode -> %s".format("  " * lev, mainnode
 598     // match {
 599     // case null => "<null>"
 600     // case tn: TNode[_, _] => "TNode(%s, %s, %d, !)".format(tn.k, tn.v,
 601     // tn.hc)
 602     // case cn: CNode[_, _] => cn.string(lev)
 603     // case ln: LNode[_, _] => ln.string(lev)
 604     // case x => "<elem: %s>".format(x)
 605     // })
 606
 607     @Override
 608     String string(final int lev) {
 609         return "INode";
 610     }
 611 }