boring.nav — org.replikativ/boring 0.1.9

Read-only navigation over encoded CBOR, without decoding what you did not ask for.

(get-in src ["customer-137" "name"]) walks the wire format, steps over the 199 customer records it does not want, and materialises one string. On a 74 KB blob that measured 27 µs against 181 µs for decode-then-get-in. On a file of 1 MiB bytestrings, handing back a span instead of the payload is ~1000x.

THE ONE SURPRISE. get returns a CURSOR, not a value. That is the whole point -- a cursor costs nothing, so intermediate maps are never built -- but it means get-in here does not behave like get-in on a map. Call value at the end:

(-> src (get-in ["customer-137" "name"]) nav/value)

WHAT IS IMPLEMENTED, AND WHAT IS DELIBERATELY NOT:

ILookup get, and therefore clojure.core/get-in for free Indexed nth -- O(n), see below Counted count -- genuinely O(1), the count is in the head Seqable seq of children IReduceInit reduce over children with no intermediate seq zipper via zipper, read-only: make-node throws

NOT IDeref. @cursor would read as a cheap field access while doing arbitrary decode work, and IDeref means a reference type with changing identity or a caching pending computation -- a cursor is neither. value is a function.

nth is O(n) because a CBOR array carries an ELEMENT count, not byte offsets: reaching index i means stepping over i values. Indexed promises no better, but it is worth knowing before looping over indices.

TWO HARD CONSTRAINTS, both checked rather than documented-and-hoped:

1. :stringref false is required. A stringref is an index into a table built from every preceding string, so a cursor holding only an offset cannot resolve one -- and skipping a subtree would still have to register the strings inside it. Navigating a stringref document is refused, not silently wrong. boring writes stringref BY DEFAULT, so files meant to be navigated must be written with {:stringref false} -- and put that on the WRITER, (boring/writer n {:stringref false}), rather than passing it to every call: resolved per call it costs ~250 heap bytes per item, resolved once it costs nothing.

2. Indefinite-length containers cannot be descended. Their count is not on the wire, so count could not be O(1) and Counted would be a lie. boring never emits them -- Writer.head only writes definite lengths -- so this can only arrive from a foreign streaming encoder. Decode such a document with boring/decode, which handles them fine.

TAGS ARE OPAQUE. get on a tagged value realises it through the normal reader and continues with clojure.core/get on the result. A tag's reader is an arbitrary function, so there is no general relationship between the wire shape and the logical shape of what it returns -- descending structurally could disagree with decoding, silently. The slow path IS the reference implementation, which is what makes the fast path safe to trust.

byte-span clj

(byte-span c)

[start end] of the value at the cursor. end is exclusive. This is what lets a caller hand a subtree somewhere else without decoding it.

children clj

(children c)

A reducible/seqable of child cursors (arrays) or MapEntries of realised key to value cursor (maps). Prefer reduce over seq in a hot loop.

cursor? clj

(cursor? x)

items clj

(items src)

(items src opts)

A reducible/seqable of cursors, one per TOP-LEVEL item, over a CBOR sequence (RFC 8742) -- the shape write-to! in a loop produces, and the natural frame for a log.

Each item is independently decodable, so this streams: nothing before the cursor you are holding stays live, and reduce honours reduced so you can stop early without walking the rest of the file. Reaching item n costs n skips -- a skip being a structural walk, not a decode -- so tailing is cheap and random access to the middle of a large file wants an offset index built alongside the writes.

(transduce (comp (map nav/value) (filter #(= "error" (get % "lvl"))))
           conj [] (nav/items bs opts))

The :stringref false requirement applies per item, as everywhere in this namespace.

raw-bytes clj

(raw-bytes c)

The encoded bytes of the subtree at the cursor, copied out. A re-encodable slice: (boring/decode (raw-bytes c)) equals (value c).

source clj

(source src)

(source src opts)

A navigable view over src -- a byte[], or a ByteSource such as boring.mmap/mmap-source gives. Returns a cursor at the root.

opts are the decode options realisation will use (:registry and friends), and must describe how the document was WRITTEN. :stringref false is forced; see the namespace docstring.

ADDRESSES THE FIRST ITEM ONLY. A log or stream is usually a CBOR sequence (RFC 8742) -- many top-level items concatenated, which is what write-to! in a loop produces -- and a cursor from here would navigate only the first of them and silently ignore the rest. Use items for that. This is not an error case, because a caller may legitimately navigate a value sitting in an oversized scratch buffer.

value clj

(value c)

Realise the subtree at the cursor into a Clojure value, through the ordinary decoder -- same registry, same records, same everything.

value-type clj

(value-type c)

What is at the cursor, without decoding it: :map :array :text :bytes :tag :int :float-or-simple.

zipper clj

(zipper c)

A read-only clojure.zip zipper over the cursor. down, right, node and friends work; anything that edits throws, because a change of length would cascade through every offset after it.