Coverage Summary for Class: Trie (co.rsk.trie)

Class Method, % Line, %
Trie 68.2% (45/66) 58% (260/448)
Trie$InOrderIterator 0% (0/4) 0% (0/20)
Trie$IterationElement 0% (0/4) 0% (0/10)
Trie$PostOrderIterator 0% (0/4) 0% (0/29)
Trie$PreOrderIterator 0% (0/3) 0% (0/18)
Trie$SharedPathSerializer 100% (7/7) 86.8% (33/38)
Total 59.1% (52/88) 52% (293/563)


1 /* 2  * This file is part of RskJ 3  * Copyright (C) 2017 RSK Labs Ltd. 4  * 5  * This program is free software: you can redistribute it and/or modify 6  * it under the terms of the GNU Lesser General Public License as published by 7  * the Free Software Foundation, either version 3 of the License, or 8  * (at your option) any later version. 9  * 10  * This program is distributed in the hope that it will be useful, 11  * but WITHOUT ANY WARRANTY; without even the implied warranty of 12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13  * GNU Lesser General Public License for more details. 14  * 15  * You should have received a copy of the GNU Lesser General Public License 16  * along with this program. If not, see <http://www.gnu.org/licenses/>. 17  */ 18  19 package co.rsk.trie; 20  21 import co.rsk.bitcoinj.core.VarInt; 22 import co.rsk.core.types.ints.Uint16; 23 import co.rsk.core.types.ints.Uint24; 24 import co.rsk.core.types.ints.Uint8; 25 import co.rsk.crypto.Keccak256; 26 import co.rsk.metrics.profilers.Metric; 27 import co.rsk.metrics.profilers.Profiler; 28 import co.rsk.metrics.profilers.ProfilerFactory; 29 import org.ethereum.crypto.Keccak256Helper; 30 import org.ethereum.db.ByteArrayWrapper; 31 import org.ethereum.util.ByteUtil; 32 import org.ethereum.util.RLP; 33  34 import javax.annotation.Nullable; 35 import java.nio.ByteBuffer; 36 import java.nio.charset.StandardCharsets; 37 import java.util.*; 38  39 import static org.ethereum.util.ByteUtil.EMPTY_BYTE_ARRAY; 40  41 /** 42  * A binary trie node. 43  * 44  * Each node has an optional associated value (a byte array) 45  * 46  * A node is referenced via a key (a byte array) 47  * 48  * A node can be serialized to/from a message (a byte array) 49  * 50  * A node has a hash (keccak256 of its serialization) 51  * 52  * A node is immutable: to add/change a value or key, a new node is created 53  * 54  * An empty node has no subnodes and a null value 55  */ 56 public class Trie { 57  private static final int ARITY = 2; 58  private static final int MAX_EMBEDDED_NODE_SIZE_IN_BYTES = 44; 59  60  private static final Profiler profiler = ProfilerFactory.getInstance(); 61  private static final String INVALID_ARITY = "Invalid arity"; 62  63  private static final int MESSAGE_HEADER_LENGTH = 2 + Short.BYTES * 2; 64  private static final String INVALID_VALUE_LENGTH = "Invalid value length"; 65  66  // all zeroed, default hash for empty nodes 67  private static Keccak256 emptyHash = makeEmptyHash(); 68  69  // this node associated value, if any 70  private byte[] value; 71  72  private final NodeReference left; 73  74  private final NodeReference right; 75  76  // this node hash value 77  private Keccak256 hash; 78  79  // this node hash value as calculated before RSKIP 107 80  // we need to cache it, otherwise TrieConverter is prohibitively slow. 81  private Keccak256 hashOrchid; 82  83  // temporary storage of encoding. Removed after save() 84  private byte[] encoded; 85  86  // valueLength enables lazy long value retrieval. 87  // The length of the data is now stored. This allows EXTCODESIZE to 88  // execute much faster without the need to actually retrieve the data. 89  // if valueLength>32 and value==null this means the value has not been retrieved yet. 90  // if valueLength==0, then there is no value AND no node. 91  // This trie structure does not distinguish between empty arrays 92  // and nulls. Storing an empty byte array has the same effect as removing the node. 93  // 94  private final Uint24 valueLength; 95  96  // For lazy retrieval and also for cache. 97  private Keccak256 valueHash; 98  99  // the size of this node along with its children (in bytes) 100  // note that we use a long because an int would allow only up to 4GB of state to be stored. 101  private VarInt childrenSize; 102  103  // associated store, to store or retrieve nodes in the trie 104  private TrieStore store; 105  106  // shared Path 107  private final TrieKeySlice sharedPath; 108  109  110  // default constructor, no secure 111  public Trie() { 112  this(null); 113  } 114  115  public Trie(TrieStore store) { 116  this(store, TrieKeySlice.empty(), null); 117  } 118  119  private Trie(TrieStore store, TrieKeySlice sharedPath, byte[] value) { 120  this(store, sharedPath, value, NodeReference.empty(), NodeReference.empty(), getDataLength(value), null); 121  } 122  123  public Trie(TrieStore store, TrieKeySlice sharedPath, byte[] value, NodeReference left, NodeReference right, Uint24 valueLength, Keccak256 valueHash) { 124  this(store, sharedPath, value, left, right, valueLength, valueHash, null); 125  } 126  127  // full constructor 128  private Trie(TrieStore store, TrieKeySlice sharedPath, byte[] value, NodeReference left, NodeReference right, Uint24 valueLength, Keccak256 valueHash, VarInt childrenSize) { 129  this.value = value; 130  this.left = left; 131  this.right = right; 132  this.store = store; 133  this.sharedPath = sharedPath; 134  this.valueLength = valueLength; 135  this.valueHash = valueHash; 136  this.childrenSize = childrenSize; 137  checkValueLength(); 138  } 139  140  /** 141  * Deserialize a Trie, either using the original format or RSKIP 107 format, based on version flags. 142  * The original trie wasted the first byte by encoding the arity, which was always 2. We use this marker to 143  * recognize the old serialization format. 144  */ 145  public static Trie fromMessage(byte[] message, TrieStore store) { 146  Trie trie; 147  Metric metric = profiler.start(Profiler.PROFILING_TYPE.BUILD_TRIE_FROM_MSG); 148  if (message[0] == ARITY) { 149  trie = fromMessageOrchid(message, store); 150  } else { 151  trie = fromMessageRskip107(ByteBuffer.wrap(message), store); 152  } 153  154  profiler.stop(metric); 155  return trie; 156  } 157  158  private static Trie fromMessageOrchid(byte[] message, TrieStore store) { 159  int current = 0; 160  int arity = message[current]; 161  current += Byte.BYTES; 162  163  if (arity != ARITY) { 164  throw new IllegalArgumentException(INVALID_ARITY); 165  } 166  167  int flags = message[current]; 168  current += Byte.BYTES; 169  170  boolean hasLongVal = (flags & 0x02) == 2; 171  int bhashes = Uint16.decodeToInt(message, current); 172  current += Uint16.BYTES; 173  int lshared = Uint16.decodeToInt(message, current); 174  current += Uint16.BYTES; 175  176  TrieKeySlice sharedPath = TrieKeySlice.empty(); 177  int lencoded = PathEncoder.calculateEncodedLength(lshared); 178  if (lencoded > 0) { 179  if (message.length - current < lencoded) { 180  throw new IllegalArgumentException(String.format( 181  "Left message is too short for encoded shared path expected:%d actual:%d total:%d", 182  lencoded, message.length - current, message.length)); 183  } 184  sharedPath = TrieKeySlice.fromEncoded(message, current, lshared, lencoded); 185  current += lencoded; 186  } 187  188  int keccakSize = Keccak256Helper.DEFAULT_SIZE_BYTES; 189  NodeReference left = NodeReference.empty(); 190  NodeReference right = NodeReference.empty(); 191  192  int nhashes = 0; 193  if ((bhashes & 0b01) != 0) { 194  Keccak256 nodeHash = readHash(message, current); 195  left = new NodeReference(store, null, nodeHash); 196  current += keccakSize; 197  nhashes++; 198  } 199  if ((bhashes & 0b10) != 0) { 200  Keccak256 nodeHash = readHash(message, current); 201  right = new NodeReference(store, null, nodeHash); 202  current += keccakSize; 203  nhashes++; 204  } 205  206  int offset = MESSAGE_HEADER_LENGTH + lencoded + nhashes * keccakSize; 207  byte[] value; 208  Uint24 lvalue; 209  Keccak256 valueHash; 210  211  if (hasLongVal) { 212  valueHash = readHash(message, current); 213  value = store.retrieveValue(valueHash.getBytes()); 214  lvalue = new Uint24(value.length); 215  } else { 216  int remaining = message.length - offset; 217  if (remaining > 0) { 218  if (message.length - current < remaining) { 219  throw new IllegalArgumentException(String.format( 220  "Left message is too short for value expected:%d actual:%d total:%d", 221  remaining, message.length - current, message.length)); 222  } 223  224  value = Arrays.copyOfRange(message, current, current + remaining); 225  valueHash = null; 226  lvalue = new Uint24(remaining); 227  } else { 228  value = null; 229  valueHash = null; 230  lvalue = Uint24.ZERO; 231  } 232  } 233  234  // it doesn't need to clone value since it's retrieved from store or created from message 235  return new Trie(store, sharedPath, value, left, right, lvalue, valueHash); 236  } 237  238  private static Trie fromMessageRskip107(ByteBuffer message, TrieStore store) { 239  byte flags = message.get(); 240  // if we reached here, we don't need to check the version flag 241  boolean hasLongVal = (flags & 0b00100000) == 0b00100000; 242  boolean sharedPrefixPresent = (flags & 0b00010000) == 0b00010000; 243  boolean leftNodePresent = (flags & 0b00001000) == 0b00001000; 244  boolean rightNodePresent = (flags & 0b00000100) == 0b00000100; 245  boolean leftNodeEmbedded = (flags & 0b00000010) == 0b00000010; 246  boolean rightNodeEmbedded = (flags & 0b00000001) == 0b00000001; 247  248  TrieKeySlice sharedPath = SharedPathSerializer.deserialize(message, sharedPrefixPresent); 249  250  NodeReference left = NodeReference.empty(); 251  NodeReference right = NodeReference.empty(); 252  if (leftNodePresent) { 253  if (leftNodeEmbedded) { 254  byte[] lengthBytes = new byte[Uint8.BYTES]; 255  message.get(lengthBytes); 256  Uint8 length = Uint8.decode(lengthBytes, 0); 257  258  byte[] serializedNode = new byte[length.intValue()]; 259  message.get(serializedNode); 260  Trie node = fromMessageRskip107(ByteBuffer.wrap(serializedNode), store); 261  left = new NodeReference(store, node, null); 262  } else { 263  byte[] valueHash = new byte[Keccak256Helper.DEFAULT_SIZE_BYTES]; 264  message.get(valueHash); 265  Keccak256 nodeHash = new Keccak256(valueHash); 266  left = new NodeReference(store, null, nodeHash); 267  } 268  } 269  270  if (rightNodePresent) { 271  if (rightNodeEmbedded) { 272  byte[] lengthBytes = new byte[Uint8.BYTES]; 273  message.get(lengthBytes); 274  Uint8 length = Uint8.decode(lengthBytes, 0); 275  276  byte[] serializedNode = new byte[length.intValue()]; 277  message.get(serializedNode); 278  Trie node = fromMessageRskip107(ByteBuffer.wrap(serializedNode), store); 279  right = new NodeReference(store, node, null); 280  } else { 281  byte[] valueHash = new byte[Keccak256Helper.DEFAULT_SIZE_BYTES]; 282  message.get(valueHash); 283  Keccak256 nodeHash = new Keccak256(valueHash); 284  right = new NodeReference(store, null, nodeHash); 285  } 286  } 287  288  VarInt childrenSize = new VarInt(0); 289  if (leftNodePresent || rightNodePresent) { 290  childrenSize = readVarInt(message); 291  } 292  293  byte[] value; 294  Uint24 lvalue; 295  Keccak256 valueHash; 296  297  if (hasLongVal) { 298  value = null; 299  byte[] valueHashBytes = new byte[Keccak256Helper.DEFAULT_SIZE_BYTES]; 300  message.get(valueHashBytes); 301  valueHash = new Keccak256(valueHashBytes); 302  byte[] lvalueBytes = new byte[Uint24.BYTES]; 303  message.get(lvalueBytes); 304  lvalue = Uint24.decode(lvalueBytes, 0); 305  } else { 306  int remaining = message.remaining(); 307  if (remaining != 0) { 308  value = new byte[remaining]; 309  message.get(value); 310  valueHash = new Keccak256(Keccak256Helper.keccak256(value)); 311  lvalue = new Uint24(remaining); 312  } else { 313  value = null; 314  valueHash = null; 315  lvalue = Uint24.ZERO; 316  } 317  } 318  319  if (message.hasRemaining()) { 320  throw new IllegalArgumentException("The message had more data than expected"); 321  } 322  323  return new Trie(store, sharedPath, value, left, right, lvalue, valueHash, childrenSize); 324  } 325  326  /** 327  * getHash calculates and/or returns the hash associated with this node content 328  * 329  * the internal variable hash could contains the cached hash. 330  * 331  * This method is not synchronized because the result of it's execution 332  * 333  * disregarding the lazy initialization is idempotent. It's better to keep 334  * 335  * it out of synchronized. 336  * 337  * @return a byte array with the node serialized to bytes 338  */ 339  public Keccak256 getHash() { 340  if (this.hash != null) { 341  return this.hash.copy(); 342  } 343  344  if (isEmptyTrie()) { 345  return emptyHash.copy(); 346  } 347  348  byte[] message = this.toMessage(); 349  350  this.hash = new Keccak256(Keccak256Helper.keccak256(message)); 351  352  return this.hash.copy(); 353  } 354  355  /** 356  * The hash based on pre-RSKIP 107 serialization 357  */ 358  public Keccak256 getHashOrchid(boolean isSecure) { 359  if (this.hashOrchid != null) { 360  return this.hashOrchid.copy(); 361  } 362  363  if (isEmptyTrie()) { 364  return emptyHash.copy(); 365  } 366  367  byte[] message = this.toMessageOrchid(isSecure); 368  369  this.hashOrchid = new Keccak256(Keccak256Helper.keccak256(message)); 370  371  return this.hashOrchid.copy(); 372  } 373  374  /** 375  * get returns the value associated with a key 376  * 377  * @param key the key associated with the value, a byte array (variable length) 378  * 379  * @return the associated value, a byte array, or null if there is no associated value to the key 380  */ 381  @Nullable 382  public byte[] get(byte[] key) { 383  Metric metric = profiler.start(Profiler.PROFILING_TYPE.TRIE_GET_VALUE_FROM_KEY); 384  Trie node = find(key); 385  if (node == null) { 386  profiler.stop(metric); 387  return null; 388  } 389  390  byte[] result = node.getValue(); 391  profiler.stop(metric); 392  return result; 393  } 394  395  /** 396  * get by string, utility method used from test methods 397  * 398  * @param key a string, that is converted to a byte array 399  * @return a byte array with the associated value 400  */ 401  public byte[] get(String key) { 402  return this.get(key.getBytes(StandardCharsets.UTF_8)); 403  } 404  405  /** 406  * put key value association, returning a new NewTrie 407  * 408  * @param key key to be updated or created, a byte array 409  * @param value value to associated to the key, a byte array 410  * 411  * @return a new NewTrie node, the top node of the new tree having the 412  * key-value association. The original node is immutable, a new tree 413  * is build, adding some new nodes 414  */ 415  public Trie put(byte[] key, byte[] value) { 416  TrieKeySlice keySlice = TrieKeySlice.fromKey(key); 417  Trie trie = put(keySlice, value, false); 418  419  return trie == null ? new Trie(this.store) : trie; 420  } 421  422  public Trie put(ByteArrayWrapper key, byte[] value) { 423  return put(key.getData(), value); 424  } 425  /** 426  * put string key to value, the key is converted to byte array 427  * utility method to be used from testing 428  * 429  * @param key a string 430  * @param value an associated value, a byte array 431  * 432  * @return a new NewTrie, the top node of a new trie having the key 433  * value association 434  */ 435  public Trie put(String key, byte[] value) { 436  return put(key.getBytes(StandardCharsets.UTF_8), value); 437  } 438  439  /** 440  * delete update the key to null value 441  * 442  * @param key a byte array 443  * 444  * @return the new top node of the trie with the association removed 445  * 446  */ 447  public Trie delete(byte[] key) { 448  return put(key, null); 449  } 450  451  // This is O(1). The node with exact key "key" MUST exists. 452  public Trie deleteRecursive(byte[] key) { 453  TrieKeySlice keySlice = TrieKeySlice.fromKey(key); 454  Trie trie = put(keySlice, null, true); 455  456  return trie == null ? new Trie(this.store) : trie; 457  } 458  459  /** 460  * delete string key, utility method to be used for testing 461  * 462  * @param key a string 463  * 464  * @return the new top node of the trie with the key removed 465  */ 466  public Trie delete(String key) { 467  return delete(key.getBytes(StandardCharsets.UTF_8)); 468  } 469  470  /** 471  * toMessage serialize the node to bytes. Used to persist the node in a key-value store 472  * like levelDB or redis. 473  * 474  * The serialization includes: 475  * - arity: byte 476  * - bits with present hashes: two bytes (example: 0x0203 says that the node has 477  * hashes at index 0, 1, 9 (the other subnodes are null) 478  * - present hashes: 32 bytes each 479  * - associated value: remainder bytes (no bytes if null) 480  * 481  * @return a byte array with the serialized info 482  */ 483  public byte[] toMessage() { 484  if (encoded == null) { 485  internalToMessage(); 486  } 487  488  return cloneArray(encoded); 489  } 490  491  public int getMessageLength() { 492  if (encoded == null) { 493  internalToMessage(); 494  } 495  496  return encoded.length; 497  } 498  499  /** 500  * Serialize the node to bytes with the pre-RSKIP 107 format 501  */ 502  public byte[] toMessageOrchid(boolean isSecure) { 503  Uint24 lvalue = this.valueLength; 504  int lshared = this.sharedPath.length(); 505  int lencoded = PathEncoder.calculateEncodedLength(lshared); 506  boolean hasLongVal = this.hasLongValue(); 507  Optional<Keccak256> leftHashOpt = this.left.getHashOrchid(isSecure); 508  Optional<Keccak256> rightHashOpt = this.right.getHashOrchid(isSecure); 509  510  int nnodes = 0; 511  int bits = 0; 512  if (leftHashOpt.isPresent()) { 513  bits |= 0b01; 514  nnodes++; 515  } 516  517  if (rightHashOpt.isPresent()) { 518  bits |= 0b10; 519  nnodes++; 520  } 521  522  ByteBuffer buffer = ByteBuffer.allocate(MESSAGE_HEADER_LENGTH + (lshared > 0 ? lencoded: 0) 523  + nnodes * Keccak256Helper.DEFAULT_SIZE_BYTES 524  + (hasLongVal ? Keccak256Helper.DEFAULT_SIZE_BYTES : lvalue.intValue())); 525  526  buffer.put((byte) ARITY); 527  528  byte flags = 0; 529  530  if (isSecure) { 531  flags |= 1; 532  } 533  534  if (hasLongVal) { 535  flags |= 2; 536  } 537  538  buffer.put(flags); 539  buffer.putShort((short) bits); 540  buffer.putShort((short) lshared); 541  542  if (lshared > 0) { 543  buffer.put(this.sharedPath.encode()); 544  } 545  546  leftHashOpt.ifPresent(h -> buffer.put(h.getBytes())); 547  548  rightHashOpt.ifPresent(h -> buffer.put(h.getBytes())); 549  550  if (lvalue.compareTo(Uint24.ZERO) > 0) { 551  if (hasLongVal) { 552  buffer.put(this.getValueHash().getBytes()); 553  } 554  else { 555  buffer.put(this.getValue()); 556  } 557  } 558  559  return buffer.array(); 560  } 561  562  // This method should only be called DURING save(). It should not be called in other places 563  // because it will expand the node encoding in a memory cache that is ONLY removed after save() 564  public boolean isEmbeddable() { 565  return isTerminal() && getMessageLength() <= MAX_EMBEDDED_NODE_SIZE_IN_BYTES; 566  } 567  568  // key is the key with exactly collectKeyLen bytes. 569  // in non-expanded form (binary) 570  // special value Integer.MAX_VALUE means collect them all. 571  private void collectKeys(Set<ByteArrayWrapper> set, TrieKeySlice key, int collectKeyLen) { 572  if (collectKeyLen != Integer.MAX_VALUE && key.length() > collectKeyLen) { 573  return; 574  } 575  576  boolean shouldCollect = collectKeyLen == Integer.MAX_VALUE || key.length() == collectKeyLen; 577  if (valueLength.compareTo(Uint24.ZERO) > 0 && shouldCollect) { 578  // convert bit string into byte[] 579  set.add(new ByteArrayWrapper(key.encode())); 580  } 581  582  for (byte k = 0; k < ARITY; k++) { 583  Trie node = this.retrieveNode(k); 584  585  if (node == null) { 586  continue; 587  } 588  589  TrieKeySlice nodeKey = key.rebuildSharedPath(k, node.getSharedPath()); 590  node.collectKeys(set, nodeKey, collectKeyLen); 591  } 592  } 593  594  // Special value Integer.MAX_VALUE means collect them all. 595  public Set<ByteArrayWrapper> collectKeys(int byteSize) { 596  Set<ByteArrayWrapper> set = new HashSet<>(); 597  598  int bitSize; 599  if (byteSize == Integer.MAX_VALUE) { 600  bitSize = Integer.MAX_VALUE; 601  } else { 602  bitSize = byteSize * 8; 603  } 604  605  collectKeys(set, getSharedPath(), bitSize); 606  return set; 607  } 608  609  /** 610  * trieSize returns the number of nodes in trie 611  * 612  * @return the number of tries nodes, includes the current one 613  */ 614  public int trieSize() { 615  return 1 + this.left.getNode().map(Trie::trieSize).orElse(0) 616  + this.right.getNode().map(Trie::trieSize).orElse(0); 617  } 618  619  /** 620  * get retrieves the associated value given the key 621  * 622  * @param key full key 623  * @return the associated value, null if the key is not found 624  * 625  */ 626  @Nullable 627  public Trie find(byte[] key) { 628  return find(TrieKeySlice.fromKey(key)); 629  } 630  631  @Nullable 632  private Trie find(TrieKeySlice key) { 633  if (sharedPath.length() > key.length()) { 634  return null; 635  } 636  637  int commonPathLength = key.commonPath(sharedPath).length(); 638  if (commonPathLength < sharedPath.length()) { 639  return null; 640  } 641  642  if (commonPathLength == key.length()) { 643  return this; 644  } 645  646  Trie node = this.retrieveNode(key.get(commonPathLength)); 647  if (node == null) { 648  return null; 649  } 650  651  return node.find(key.slice(commonPathLength + 1, key.length())); 652  } 653  654  private void internalToMessage() { 655  Uint24 lvalue = this.valueLength; 656  boolean hasLongVal = this.hasLongValue(); 657  658  SharedPathSerializer sharedPathSerializer = new SharedPathSerializer(this.sharedPath); 659  VarInt childrenSize = getChildrenSize(); 660  661  ByteBuffer buffer = ByteBuffer.allocate( 662  1 + // flags 663  sharedPathSerializer.serializedLength() + 664  this.left.serializedLength() + 665  this.right.serializedLength() + 666  (this.isTerminal() ? 0 : childrenSize.getSizeInBytes()) + 667  (hasLongVal ? Keccak256Helper.DEFAULT_SIZE_BYTES + Uint24.BYTES : lvalue.intValue()) 668  ); 669  670  // current serialization version: 01 671  byte flags = 0b01000000; 672  if (hasLongVal) { 673  flags = (byte) (flags | 0b00100000); 674  } 675  676  if (sharedPathSerializer.isPresent()) { 677  flags = (byte) (flags | 0b00010000); 678  } 679  680  if (!this.left.isEmpty()) { 681  flags = (byte) (flags | 0b00001000); 682  } 683  684  if (!this.right.isEmpty()) { 685  flags = (byte) (flags | 0b00000100); 686  } 687  688  if (this.left.isEmbeddable()) { 689  flags = (byte) (flags | 0b00000010); 690  } 691  692  if (this.right.isEmbeddable()) { 693  flags = (byte) (flags | 0b00000001); 694  } 695  696  buffer.put(flags); 697  698  sharedPathSerializer.serializeInto(buffer); 699  700  this.left.serializeInto(buffer); 701  702  this.right.serializeInto(buffer); 703  704  if (!this.isTerminal()) { 705  buffer.put(childrenSize.encode()); 706  } 707  708  if (hasLongVal) { 709  buffer.put(this.getValueHash().getBytes()); 710  buffer.put(lvalue.encode()); 711  } else if (lvalue.compareTo(Uint24.ZERO) > 0) { 712  buffer.put(this.getValue()); 713  } 714  715  encoded = buffer.array(); 716  } 717  718  private Trie retrieveNode(byte implicitByte) { 719  return getNodeReference(implicitByte).getNode().orElse(null); 720  } 721  722  public NodeReference getNodeReference(byte implicitByte) { 723  return implicitByte == 0 ? this.left : this.right; 724  } 725  726  public NodeReference getLeft() { 727  return left; 728  } 729  730  public NodeReference getRight() { 731  return right; 732  } 733  734  /** 735  * put key with associated value, returning a new NewTrie 736  * 737  * @param key key to be updated 738  * @param value associated value 739  * 740  * @return the new NewTrie containing the tree with the new key value association 741  * 742  */ 743  private Trie put(TrieKeySlice key, byte[] value, boolean isRecursiveDelete) { 744  // First of all, setting the value as an empty byte array is equivalent 745  // to removing the key/value. This is because other parts of the trie make 746  // this equivalent. Use always null to mark a node for deletion. 747  if (value != null && value.length == 0) { 748  value = null; 749  } 750  751  Trie trie = this.internalPut(key, value, isRecursiveDelete); 752  753  // the following code coalesces nodes if needed for delete operation 754  755  // it's null or it is not a delete operation 756  if (trie == null || value != null) { 757  return trie; 758  } 759  760  if (trie.isEmptyTrie()) { 761  return null; 762  } 763  764  // only coalesce if node has only one child and no value 765  if (trie.valueLength.compareTo(Uint24.ZERO) > 0) { 766  return trie; 767  } 768  769  Optional<Trie> leftOpt = trie.left.getNode(); 770  Optional<Trie> rightOpt = trie.right.getNode(); 771  if (leftOpt.isPresent() && rightOpt.isPresent()) { 772  return trie; 773  } 774  775  if (!leftOpt.isPresent() && !rightOpt.isPresent()) { 776  return trie; 777  } 778  779  Trie child; 780  byte childImplicitByte; 781  if (leftOpt.isPresent()) { 782  child = leftOpt.get(); 783  childImplicitByte = (byte) 0; 784  } else { // has right node 785  child = rightOpt.get(); 786  childImplicitByte = (byte) 1; 787  } 788  789  TrieKeySlice newSharedPath = trie.sharedPath.rebuildSharedPath(childImplicitByte, child.sharedPath); 790  return new Trie(child.store, newSharedPath, child.value, child.left, child.right, child.valueLength, child.valueHash); 791  } 792  793  private static Uint24 getDataLength(byte[] value) { 794  if (value == null) { 795  return Uint24.ZERO; 796  } 797  798  return new Uint24(value.length); 799  } 800  801  private Trie internalPut(TrieKeySlice key, byte[] value, boolean isRecursiveDelete) { 802  TrieKeySlice commonPath = key.commonPath(sharedPath); 803  if (commonPath.length() < sharedPath.length()) { 804  // when we are removing a key we know splitting is not necessary. the key wasn't found at this point. 805  if (value == null) { 806  return this; 807  } 808  809  return this.split(commonPath).put(key, value, isRecursiveDelete); 810  } 811  812  if (sharedPath.length() >= key.length()) { 813  // To compare values we need to retrieve the previous value 814  // if not already done so. We could also compare by hash, to avoid retrieval 815  // We do a small optimization here: if sizes are not equal, then values 816  // obviously are not. 817  if (this.valueLength.equals(getDataLength(value)) && Arrays.equals(this.getValue(), value)) { 818  return this; 819  } 820  821  if (isRecursiveDelete) { 822  return new Trie(this.store, this.sharedPath, null); 823  } 824  825  if (isEmptyTrie(getDataLength(value), this.left, this.right)) { 826  return null; 827  } 828  829  return new Trie( 830  this.store, 831  this.sharedPath, 832  cloneArray(value), 833  this.left, 834  this.right, 835  getDataLength(value), 836  null 837  ); 838  } 839  840  if (isEmptyTrie()) { 841  return new Trie(this.store, key, cloneArray(value)); 842  } 843  844  // this bit will be implicit and not present in a shared path 845  byte pos = key.get(sharedPath.length()); 846  847  Trie node = retrieveNode(pos); 848  if (node == null) { 849  node = new Trie(this.store); 850  } 851  852  TrieKeySlice subKey = key.slice(sharedPath.length() + 1, key.length()); 853  Trie newNode = node.put(subKey, value, isRecursiveDelete); 854  855  // reference equality 856  if (newNode == node) { 857  return this; 858  } 859  860  NodeReference newNodeReference = new NodeReference(this.store, newNode, null); 861  NodeReference newLeft; 862  NodeReference newRight; 863  if (pos == 0) { 864  newLeft = newNodeReference; 865  newRight = this.right; 866  } else { 867  newLeft = this.left; 868  newRight = newNodeReference; 869  } 870  871  if (isEmptyTrie(this.valueLength, newLeft, newRight)) { 872  return null; 873  } 874  875  return new Trie(this.store, this.sharedPath, this.value, newLeft, newRight, this.valueLength, this.valueHash); 876  } 877  878  private Trie split(TrieKeySlice commonPath) { 879  int commonPathLength = commonPath.length(); 880  TrieKeySlice newChildSharedPath = sharedPath.slice(commonPathLength + 1, sharedPath.length()); 881  Trie newChildTrie = new Trie(this.store, newChildSharedPath, this.value, this.left, this.right, this.valueLength, this.valueHash); 882  NodeReference newChildReference = new NodeReference(this.store, newChildTrie, null); 883  884  // this bit will be implicit and not present in a shared path 885  byte pos = sharedPath.get(commonPathLength); 886  887  NodeReference newLeft; 888  NodeReference newRight; 889  if (pos == 0) { 890  newLeft = newChildReference; 891  newRight = NodeReference.empty(); 892  } else { 893  newLeft = NodeReference.empty(); 894  newRight = newChildReference; 895  } 896  897  return new Trie(this.store, commonPath, null, newLeft, newRight, Uint24.ZERO, null); 898  } 899  900  public boolean isTerminal() { 901  return this.left.isEmpty() && this.right.isEmpty(); 902  } 903  904  public boolean isEmptyTrie() { 905  return isEmptyTrie(this.valueLength, this.left, this.right); 906  } 907  908  /** 909  * isEmptyTrie checks the existence of subnodes, subnodes hashes or value 910  * 911  * @param valueLength length of current value 912  * @param left a reference to the left node 913  * @param right a reference to the right node 914  * 915  * @return true if no data 916  */ 917  private static boolean isEmptyTrie(Uint24 valueLength, NodeReference left, NodeReference right) { 918  if (valueLength.compareTo(Uint24.ZERO) > 0) { 919  return false; 920  } 921  922  return left.isEmpty() && right.isEmpty(); 923  } 924  925  public boolean hasLongValue() { 926  return this.valueLength.compareTo(new Uint24(32)) > 0; 927  } 928  929  public Uint24 getValueLength() { 930  return this.valueLength; 931  } 932  933  public Keccak256 getValueHash() { 934  // For empty values (valueLength==0) we return the null hash because 935  // in this trie empty arrays cannot be stored. 936  if (valueHash == null && valueLength.compareTo(Uint24.ZERO) > 0) { 937  valueHash = new Keccak256(Keccak256Helper.keccak256(getValue())); 938  } 939  940  return valueHash; 941  } 942  943  public byte[] getValue() { 944  if (value == null && valueLength.compareTo(Uint24.ZERO) > 0) { 945  value = retrieveLongValue(); 946  checkValueLengthAfterRetrieve(); 947  } 948  949  return cloneArray(value); 950  } 951  952  /** 953  * @return the tree size in bytes as specified in RSKIP107 954  * 955  * This method will EXPAND internal encoding caches without removing them afterwards. 956  * It shouldn't be called from outside. It's still public for NodeReference call 957  * 958  */ 959  public VarInt getChildrenSize() { 960  if (childrenSize == null) { 961  if (isTerminal()) { 962  childrenSize = new VarInt(0); 963  } else { 964  childrenSize = new VarInt(this.left.referenceSize() + this.right.referenceSize()); 965  } 966  } 967  968  return childrenSize; 969  } 970  971  private byte[] retrieveLongValue() { 972  return store.retrieveValue(getValueHash().getBytes()); 973  } 974  975  private void checkValueLengthAfterRetrieve() { 976  // At this time value==null and value.length!=null is really bad. 977  if (value == null && valueLength.compareTo(Uint24.ZERO) > 0) { 978  // Serious DB inconsistency here 979  throw new IllegalArgumentException(INVALID_VALUE_LENGTH); 980  } 981  982  checkValueLength(); 983  } 984  985  private void checkValueLength() { 986  if (value != null && value.length != valueLength.intValue()) { 987  // Serious DB inconsistency here 988  throw new IllegalArgumentException(INVALID_VALUE_LENGTH); 989  } 990  991  if (value == null && valueLength.compareTo(Uint24.ZERO) > 0 && valueHash == null) { 992  // Serious DB inconsistency here 993  throw new IllegalArgumentException(INVALID_VALUE_LENGTH); 994  } 995  } 996  997  public TrieKeySlice getSharedPath() { 998  return sharedPath; 999  } 1000  1001  public Iterator<IterationElement> getInOrderIterator() { 1002  return new InOrderIterator(this); 1003  } 1004  1005  public Iterator<IterationElement> getPreOrderIterator() { 1006  return new PreOrderIterator(this); 1007  } 1008  1009  private static byte[] cloneArray(byte[] array) { 1010  return array == null ? null : Arrays.copyOf(array, array.length); 1011  } 1012  1013  public Iterator<IterationElement> getPostOrderIterator() { 1014  return new PostOrderIterator(this); 1015  } 1016  1017  /** 1018  * makeEmpyHash creates the hash associated to empty nodes 1019  * 1020  * @return a hash with zeroed bytes 1021  */ 1022  private static Keccak256 makeEmptyHash() { 1023  return new Keccak256(Keccak256Helper.keccak256(RLP.encodeElement(EMPTY_BYTE_ARRAY))); 1024  } 1025  1026  private static Keccak256 readHash(byte[] bytes, int position) { 1027  int keccakSize = Keccak256Helper.DEFAULT_SIZE_BYTES; 1028  if (bytes.length - position < keccakSize) { 1029  throw new IllegalArgumentException(String.format( 1030  "Left message is too short for hash expected:%d actual:%d total:%d", 1031  keccakSize, bytes.length - position, bytes.length 1032  )); 1033  } 1034  1035  return new Keccak256(Arrays.copyOfRange(bytes, position, position + keccakSize)); 1036  } 1037  1038  @Override 1039  public int hashCode() { 1040  return Objects.hashCode(getHash()); 1041  } 1042  1043  @Override 1044  public boolean equals(Object other) { 1045  if (this == other) { 1046  return true; 1047  } 1048  1049  if (other == null || this.getClass() != other.getClass()) { 1050  return false; 1051  } 1052  1053  Trie otherTrie = (Trie) other; 1054  return getHash().equals(otherTrie.getHash()); 1055  } 1056  1057  @Override 1058  public String toString() { 1059  String s = printParam("TRIE: ", "value", getValue()); 1060  s = printParam(s, "hash0", left.getHash().orElse(null)); 1061  s = printParam(s, "hash1", right.getHash().orElse(null)); 1062  s = printParam(s, "hash", getHash()); 1063  s = printParam(s, "valueHash", getValueHash()); 1064  s = printParam(s, "encodedSharedPath", sharedPath.encode()); 1065  s += "sharedPathLength: " + sharedPath.length() + "\n"; 1066  return s; 1067  } 1068  1069  private String printParam(String s, String name, byte[] param) { 1070  if (param != null) { 1071  s += name + ": " + ByteUtil.toHexString(param) + "\n"; 1072  } 1073  return s; 1074  } 1075  1076  private String printParam(String s, String name, Keccak256 param) { 1077  if (param != null) { 1078  s += name + ": " + param.toHexString() + "\n"; 1079  } 1080  return s; 1081  } 1082  1083  private static VarInt readVarInt(ByteBuffer message) { 1084  // read without touching the buffer position so when we read into bytes it contains the header 1085  int first = Byte.toUnsignedInt(message.get(message.position())); 1086  byte[] bytes; 1087  if (first < 253) { 1088  bytes = new byte[1]; 1089  } else if (first == 253) { 1090  bytes = new byte[3]; 1091  } else if (first == 254) { 1092  bytes = new byte[5]; 1093  } else { 1094  bytes = new byte[9]; 1095  } 1096  1097  message.get(bytes); 1098  return new VarInt(bytes, 0); 1099  } 1100  1101  /** 1102  * Returns the leftmost node that has not yet been visited that node is normally on top of the stack 1103  */ 1104  private static class InOrderIterator implements Iterator<IterationElement> { 1105  1106  private final Deque<IterationElement> visiting; 1107  1108  public InOrderIterator(Trie root) { 1109  Objects.requireNonNull(root); 1110  TrieKeySlice traversedPath = root.getSharedPath(); 1111  this.visiting = new LinkedList<>(); 1112  // find the leftmost node, pushing all the intermediate nodes onto the visiting stack 1113  visiting.push(new IterationElement(traversedPath, root)); 1114  pushLeftmostNode(traversedPath, root); 1115  // now the leftmost unvisited node is on top of the visiting stack 1116  } 1117  1118  /** 1119  * return the leftmost node that has not yet been visited that node is normally on top of the stack 1120  */ 1121  @Override 1122  @SuppressWarnings("squid:S2272") // NoSuchElementException is thrown by {@link Deque#pop()} when it's empty 1123  public IterationElement next() { 1124  IterationElement visitingElement = visiting.pop(); 1125  Trie node = visitingElement.getNode(); 1126  // if the node has a right child, its leftmost node is next 1127  Trie rightNode = node.retrieveNode((byte) 0x01); 1128  if (rightNode != null) { 1129  TrieKeySlice rightNodeKey = visitingElement.getNodeKey().rebuildSharedPath((byte) 0x01, rightNode.getSharedPath()); 1130  visiting.push(new IterationElement(rightNodeKey, rightNode)); // push the right node 1131  // find the leftmost node of the right child 1132  pushLeftmostNode(rightNodeKey, rightNode); 1133  // note "node" has been replaced on the stack by its right child 1134  } // else: no right subtree, go back up the stack 1135  // next node on stack will be next returned 1136  return visitingElement; 1137  } 1138  1139  @Override 1140  public boolean hasNext() { 1141  return !visiting.isEmpty(); // no next node left 1142  } 1143  1144  /** 1145  * Find the leftmost node from this root, pushing all the intermediate nodes onto the visiting stack 1146  * 1147  * @param nodeKey 1148  * @param node the root of the subtree for which we are trying to reach the leftmost node 1149  */ 1150  private void pushLeftmostNode(TrieKeySlice nodeKey, Trie node) { 1151  // find the leftmost node 1152  Trie leftNode = node.retrieveNode((byte) 0x00); 1153  if (leftNode != null) { 1154  TrieKeySlice leftNodeKey = nodeKey.rebuildSharedPath((byte) 0x00, leftNode.getSharedPath()); 1155  visiting.push(new IterationElement(leftNodeKey, leftNode)); // push the left node 1156  pushLeftmostNode(leftNodeKey, leftNode); // recurse on next left node 1157  } 1158  } 1159  } 1160  1161  private class PreOrderIterator implements Iterator<IterationElement> { 1162  1163  private final Deque<IterationElement> visiting; 1164  1165  public PreOrderIterator(Trie root) { 1166  Objects.requireNonNull(root); 1167  TrieKeySlice traversedPath = root.getSharedPath(); 1168  this.visiting = new LinkedList<>(); 1169  this.visiting.push(new IterationElement(traversedPath, root)); 1170  } 1171  1172  @Override 1173  @SuppressWarnings("squid:S2272") // NoSuchElementException is thrown by {@link Deque#pop()} when it's empty 1174  public IterationElement next() { 1175  IterationElement visitingElement = visiting.pop(); 1176  Trie node = visitingElement.getNode(); 1177  TrieKeySlice nodeKey = visitingElement.getNodeKey(); 1178  // need to visit the left subtree first, then the right since a stack is a LIFO, push the right subtree first, 1179  // then the left 1180  Trie rightNode = node.retrieveNode((byte) 0x01); 1181  if (rightNode != null) { 1182  TrieKeySlice rightNodeKey = nodeKey.rebuildSharedPath((byte) 0x01, rightNode.getSharedPath()); 1183  visiting.push(new IterationElement(rightNodeKey, rightNode)); 1184  } 1185  Trie leftNode = node.retrieveNode((byte) 0x00); 1186  if (leftNode != null) { 1187  TrieKeySlice leftNodeKey = nodeKey.rebuildSharedPath((byte) 0x00, leftNode.getSharedPath()); 1188  visiting.push(new IterationElement(leftNodeKey, leftNode)); 1189  } 1190  // may not have pushed anything. If so, we are at the end 1191  return visitingElement; 1192  } 1193  1194  @Override 1195  public boolean hasNext() { 1196  return !visiting.isEmpty(); // no next node left 1197  } 1198  } 1199  1200  private class PostOrderIterator implements Iterator<IterationElement> { 1201  1202  private final Deque<IterationElement> visiting; 1203  private final Deque<Boolean> visitingRightChild; 1204  1205  public PostOrderIterator(Trie root) { 1206  Objects.requireNonNull(root); 1207  TrieKeySlice traversedPath = root.getSharedPath(); 1208  this.visiting = new LinkedList<>(); 1209  this.visitingRightChild = new LinkedList<>(); 1210  // find the leftmost node, pushing all the intermediate nodes onto the visiting stack 1211  visiting.push(new IterationElement(traversedPath, root)); 1212  visitingRightChild.push(Boolean.FALSE); 1213  pushLeftmostNodeRecord(traversedPath, root); 1214  // the node on top of the visiting stack is the next one to be visited, unless it has a right subtree 1215  } 1216  1217  @Override 1218  public boolean hasNext() { 1219  return !visiting.isEmpty(); // no next node left 1220  } 1221  1222  @Override 1223  @SuppressWarnings("squid:S2272") // NoSuchElementException is thrown by {@link Deque#element()} when it's empty 1224  public IterationElement next() { 1225  IterationElement visitingElement = visiting.element(); 1226  Trie node = visitingElement.getNode(); 1227  Trie rightNode = node.retrieveNode((byte) 0x01); 1228  if (rightNode == null || visitingRightChild.peek()) { // no right subtree, or right subtree already visited 1229  // already visited right child, time to visit the node on top 1230  visiting.removeFirst(); // it was already picked 1231  visitingRightChild.removeFirst(); // it was already picked 1232  return visitingElement; 1233  } else { // now visit this node's right subtree 1234  // mark that we're visiting this element's right subtree 1235  visitingRightChild.removeFirst(); 1236  visitingRightChild.push(Boolean.TRUE); 1237  1238  TrieKeySlice rightNodeKey = visitingElement.getNodeKey().rebuildSharedPath((byte) 0x01, rightNode.getSharedPath()); 1239  visiting.push(new IterationElement(rightNodeKey, rightNode)); // push the right node 1240  visitingRightChild.push(Boolean.FALSE); // we're visiting the left subtree of the right node 1241  1242  // now push everything down to the leftmost node in the right subtree 1243  pushLeftmostNodeRecord(rightNodeKey, rightNode); 1244  return next(); // use recursive call to visit that node 1245  } 1246  } 1247  1248  /** 1249  * Find the leftmost node from this root, pushing all the intermediate nodes onto the visiting stack 1250  * and also stating that each is a left child of its parent 1251  * @param nodeKey 1252  * @param node the root of the subtree for which we are trying to reach the leftmost node 1253  */ 1254  private void pushLeftmostNodeRecord(TrieKeySlice nodeKey, Trie node) { 1255  // find the leftmost node 1256  Trie leftNode = node.retrieveNode((byte) 0x00); 1257  if (leftNode != null) { 1258  TrieKeySlice leftNodeKey = nodeKey.rebuildSharedPath((byte) 0x00, leftNode.getSharedPath()); 1259  visiting.push(new IterationElement(leftNodeKey, leftNode)); // push the left node 1260  visitingRightChild.push(Boolean.FALSE); // record that it is on the left 1261  pushLeftmostNodeRecord(leftNodeKey, leftNode); // continue looping 1262  } 1263  } 1264  } 1265  1266  public static class IterationElement { 1267  private final TrieKeySlice nodeKey; 1268  private final Trie node; 1269  1270  public IterationElement(final TrieKeySlice nodeKey, final Trie node) { 1271  this.nodeKey = nodeKey; 1272  this.node = node; 1273  } 1274  1275  public Trie getNode() { 1276  return node; 1277  } 1278  1279  public final TrieKeySlice getNodeKey() { 1280  return nodeKey; 1281  } 1282  1283  public String toString() { 1284  byte[] encodedFullKey = nodeKey.encode(); 1285  StringBuilder ouput = new StringBuilder(); 1286  for (byte b : encodedFullKey) { 1287  ouput.append( b == 0 ? '0': '1'); 1288  } 1289  return ouput.toString(); 1290  } 1291  } 1292  1293  private static class SharedPathSerializer { 1294  private final TrieKeySlice sharedPath; 1295  private final int lshared; 1296  1297  private SharedPathSerializer(TrieKeySlice sharedPath) { 1298  this.sharedPath = sharedPath; 1299  this.lshared = this.sharedPath.length(); 1300  } 1301  1302  private int serializedLength() { 1303  if (!isPresent()) { 1304  return 0; 1305  } 1306  1307  return lsharedSize() + PathEncoder.calculateEncodedLength(lshared); 1308  } 1309  1310  public boolean isPresent() { 1311  return lshared > 0; 1312  } 1313  1314  private void serializeInto(ByteBuffer buffer) { 1315  if (!isPresent()) { 1316  return; 1317  } 1318  1319  if (1 <= lshared && lshared <= 32) { 1320  // first byte in [0..31] 1321  buffer.put((byte) (lshared - 1)); 1322  } else if (160 <= lshared && lshared <= 382) { 1323  // first byte in [32..254] 1324  buffer.put((byte) (lshared - 128)); 1325  } else { 1326  buffer.put((byte) 255); 1327  buffer.put(new VarInt(lshared).encode()); 1328  } 1329  1330  buffer.put(this.sharedPath.encode()); 1331  } 1332  1333  private int lsharedSize() { 1334  if (!isPresent()) { 1335  return 0; 1336  } 1337  1338  if (1 <= lshared && lshared <= 32) { 1339  return 1; 1340  } 1341  1342  if (160 <= lshared && lshared <= 382) { 1343  return 1; 1344  } 1345  1346  return 1 + VarInt.sizeOf(lshared); 1347  } 1348  1349  private static TrieKeySlice deserialize(ByteBuffer message, boolean sharedPrefixPresent) { 1350  if (!sharedPrefixPresent) { 1351  return TrieKeySlice.empty(); 1352  } 1353  1354  int lshared; 1355  // upgrade to int so we can compare positive values 1356  int lsharedFirstByte = Byte.toUnsignedInt(message.get()); 1357  if (0 <= lsharedFirstByte && lsharedFirstByte <= 31) { 1358  // lshared in [1..32] 1359  lshared = lsharedFirstByte + 1; 1360  } else if (32 <= lsharedFirstByte && lsharedFirstByte <= 254) { 1361  // lshared in [160..382] 1362  lshared = lsharedFirstByte + 128; 1363  } else { 1364  lshared = (int) readVarInt(message).value; 1365  } 1366  1367  int lencoded = PathEncoder.calculateEncodedLength(lshared); 1368  byte[] encodedKey = new byte[lencoded]; 1369  message.get(encodedKey); 1370  return TrieKeySlice.fromEncoded(encodedKey, 0, lshared, lencoded); 1371  } 1372  } 1373  1374  // Additional auxiliary methods for Merkle Proof 1375  1376  @Nullable 1377  public List<Trie> getNodes(byte[] key) { 1378  return findNodes(key); 1379  } 1380  1381  @Nullable 1382  public List<Trie> getNodes(String key) { 1383  return this.getNodes(key.getBytes(StandardCharsets.UTF_8)); 1384  } 1385  1386  @Nullable 1387  private List<Trie> findNodes(byte[] key) { 1388  return findNodes(TrieKeySlice.fromKey(key)); 1389  } 1390  1391  @Nullable 1392  private List<Trie> findNodes(TrieKeySlice key) { 1393  if (sharedPath.length() > key.length()) { 1394  return null; 1395  } 1396  1397  int commonPathLength = key.commonPath(sharedPath).length(); 1398  1399  if (commonPathLength < sharedPath.length()) { 1400  return null; 1401  } 1402  1403  if (commonPathLength == key.length()) { 1404  List<Trie> nodes = new ArrayList<>(); 1405  nodes.add(this); 1406  return nodes; 1407  } 1408  1409  Trie node = this.retrieveNode(key.get(commonPathLength)); 1410  1411  if (node == null) { 1412  return null; 1413  } 1414  1415  List<Trie> subnodes = node.findNodes(key.slice(commonPathLength + 1, key.length())); 1416  1417  if (subnodes == null) { 1418  return null; 1419  } 1420  1421  subnodes.add(this); 1422  1423  return subnodes; 1424  } 1425 }