Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Review and improve trie node typing #3704

Closed
scorbajio opened this issue Sep 25, 2024 · 1 comment · Fixed by #3708
Closed

Review and improve trie node typing #3704

scorbajio opened this issue Sep 25, 2024 · 1 comment · Fixed by #3708

Comments

@scorbajio
Copy link
Contributor

scorbajio commented Sep 25, 2024

Currently, the trie Node base type is extended in the extension and leaf node implementations (but unexpectedly, not in the branch node implementation) and it has some typing issues, such as the value() function on different node classes being typed to return a Uint8Array but it can also return null or Uint8Array[]. This issue, and other similar typing issues or class design issues should be considered and fixed if possible or notes/documented for future review. Also see this comment for more context on the problem.

@scorbajio
Copy link
Contributor Author

scorbajio commented Sep 25, 2024

In order to recreate a basic example of the issue, check running npx vitest test/util/log.spec.ts in the trie package. Also navigate to and look at this code section of the onFound function in trie.ts in the src folder of the trie package:

        for (const k of node.key()) {
          console.log('dbg100')
          console.log(node.value())
          this.DEBUG && this.debug(`NextNode: ${node.value()}`, ['find_path', 'extension_node'])
          if (k !== targetKey[progress]) {
            result = { node: null, remaining: targetKey.slice(_progress), stack }
            return
          }
          progress++
        }
        walkController.allChildren(node, keyProgress)

We debug by printing the node.value() of each node being walked.:

...
dbg100
Uint8Array(32) [
  212,  59, 135, 253, 205,  66,  23,   1,
   60, 204, 146, 208,  70,  98, 225,  45,
   54, 228, 204,  37, 220, 105,   0, 119,
  205, 130,  26,  25,  86, 252,  62,  54
]
dbg100
[
  Uint8Array(0) [],
  Uint8Array(0) [],
  Uint8Array(0) [],
  Uint8Array(0) [],
  Uint8Array(0) [],
  Uint8Array(0) [],
  [ Uint8Array(1) [ 53 ], Uint8Array(4) [ 99, 111, 105, 110 ] ],
  Uint8Array(0) [],
  Uint8Array(0) [],
  Uint8Array(0) [],
  Uint8Array(0) [],
  Uint8Array(0) [],
  Uint8Array(0) [],
  Uint8Array(0) [],
  Uint8Array(0) [],
  Uint8Array(0) [],
  Uint8Array(5) [ 112, 117, 112, 112, 121 ]
]
...

As can be seen above, we have Uint8Array as well as Uint8Array[] as the return type of value(), in this instance, we see a branch node that has embedded leaf nodes being represented as an array.

The issue here is that the return type of node.value() is left ambiguous and this causes issues when e.g. passing the value to a conversion function that is strictly expecting a Uint8Array-typed input, such as bytesToHex. It seems like value() should be typed as returning Uint8Array | null | Uint8Array[].

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant