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