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

left and tree in MST nodes are documented as "optional" but implemented as "nullable" #312

Open
str4d opened this issue May 11, 2024 · 1 comment

Comments

@str4d
Copy link

str4d commented May 11, 2024

The documentation:

- `l` ("left", CID link, optional): link to sub-tree Node on a lower level and with all keys sorting before keys at this node
- `e` ("entries", array of objects, required): ordered list of TreeEntry objects
- `p` ("prefixlen", integer, required): count of bytes shared with previous TreeEntry in this Node (if any)
- `k` ("keysuffix", byte array, required): remainder of key for this TreeEntry, after "prefixlen" have been removed
- `v` ("value", CID Link, required): link to the record data (CBOR) for this entry
- `t` ("tree", CID Link, optional): link to a sub-tree Node at a lower level which has keys sorting after this TreeEntry's key (to the "right"), but before the next TreeEntry's key in this Node (if any)

The implementation:
https://github.com/bluesky-social/atproto/blob/4184a652225eaf2de5f4d4702562e84c2fd3fde7/packages/repo/src/mst/mst.ts#L46-L56

const subTreePointer = z.nullable(common.cid)
const treeEntry = z.object({
  p: z.number(), // prefix count of ascii chars that this key shares with the prev key
  k: common.bytes, // the rest of the key outside the shared prefix
  v: common.cid, // value
  t: subTreePointer, // next subtree (to the right of leaf)
})
const nodeData = z.object({
  l: subTreePointer, // left-most subtree
  e: z.array(treeEntry), //entries
})

"nullable" is used elsewhere in the same document, and the corresponding implementation in that case matches (although with different syntax that I haven't yet traced):

- `prev` (CID link, nullable): pointer (by hash) to a previous commit object for this repository. Could be used to create a chain of history, but largely unused (included for v2 backwards compatibility). In version `3` repos, this field must exist in the CBOR object, but is virtually always `null`. NOTE: previously specified as nullable and optional, but this caused interoperability issues.

https://github.com/bluesky-social/atproto/blob/4184a652225eaf2de5f4d4702562e84c2fd3fde7/packages/repo/src/types.ts#L17-L18

  // `prev` added for backwards compatibility with v2, no requirement of keeping around history
  prev: common.cid.nullable(),
@bnewbold
Copy link
Contributor

I think you are probably right and these are nullable, but will double-check next week before updating the specs.

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

No branches or pull requests

2 participants