1 Zipper
2 Types: Trail and cursor
A trail represents the content of the memory stack when recursively exploring a tree. Constructing these trails from closure would be easier, but it would make it harder to port the code to C. The type parameters of the trail keep track of the type of each element on the "stack" using a product type.
The constructors are private. Use '_' prefixed functions with runtime invariant checks.
type info = Info.ttype cursor = private | Cursor of trail * Node_type.node * Context.t * infoThe cursor, also known as a zipper combines the information contained in a trail and a subtree to represent an edit point within a tree. This is a functional data structure that represents the program point in a function that modifies a tree. We use an existential type that keeps the .mli sane and enforces the most important: that the hole tags match between the trail and the Node
*)type t = cursor 2 Constructor with invariant checks
val _Top : trailval _Left : (trail * Node_type.node * modified) -> trailval _Right : (Node_type.node * trail * modified) -> trailval _Cursor : (trail * Node_type.node * Context.t * info) -> cursor 2 Creation
2 Accessors
2 Segments
2 View
val view : t -> t * Node_type.viewGet the view of the cursor. Returns also the updated cursor with the view.
2 Zipper functions
3 Simple 1 step cursor movement
This function expects a cursor positionned on a bud and moves it one step below.
Go down an Extender node. The cursor must point to an Extender.
val go_side : Segment.side -> t -> (t, Error.t) Result.tGo down an Internal node. The cursor must point to an Internal.
3 Complex multi step cursor movement
Many of these functions fail when the given cursor does not point to a bud.
val error_access : access_result -> ('a, Error.t) Result.tMake an access result into an error
val access_gen : t -> Segment.t -> (access_result, Error.t) Result.tFollow a segment. t must point to a bud. The function first go below the bud, then follow the segment.
val access_gen' : t -> Segment.t -> (access_result, Error.t) Result.tFollow a segment. t can be any node.
Moves the cursor back to the bud above. Note that this is not like "cd ../".
If the cursor is already at a bud, the cursor will move to its parent bud.
Moves the cursor back to the bud above. Like "cd ../". The cursor must point to a bud otherwise parent fails.
Moves the cursor down a segment, to the root of a sub-tree. Think "cd segment/"
Create a subtree (bud). Think "mkdir segment". The cursor does NOT move from the original position.
Same as subtree but create a subtree if not exists
val get :
t ->
Segment.t ->
(t * [ `Leaf of Node_type.view | `Bud of Node_type.view ], Error.t) Result.tGets a value if present in the current tree at the given segment.
Gets a value or a bud at the given segment.
Inserts a value at the given segment in the current tree. It fails if a value already exists at the segment. The cursor does NOT move from the original position.
Upserts. If a value alrady exists at the segment, it is overwritten. This can still fail if the segment points to a subtree. The cursor does NOT move from the original position.
Update. A value must be bound at the segment.
val set_hashonly : t -> Segment.segment -> Hash.t -> (t, Error.t) Stdlib.resultDelete a leaf or subtree. The cursor does NOT move from the original position.
Delete a node. The cursor does NOT move from the original position.
Remove the empty Bud pointed by the cursor. If the non-root parent becomes empty by the removal, remove_empty_bud recursively removes it, too. If the cursor points non empty bud, it does nothing.
The cursor in the result points to the parent bud of the upmost removed bud.
val alter :
t ->
Segment.segment ->
(Node_type.view option -> (Node_type.node, Error.t) Result.t) ->
(t, Error.t) Result.talter can easily break the invariants.
Folding over the node tree. The function can choose the node traversal from the given cursor: either continuing into its sub-nodes, not traversing its sub-nodes, or quit the entire folding.
If a node is shared at multiple places it is visited MORE THAN ONCE. If you want to avoid visiting a shared node at most once, carry a set of visited nodes by indices and check a node is visited or not.
More generic tree traversal than fold, which has a step-by-step visitor interface: it does not recurse the structure by itself.
If a node is shared at multiple places it is visited MORE THAN ONCE.
2 Cursor hash compuation
Returns the hash of the node pointed by the cursor. It traverses nodes and compute hashes if necessary.
It also returns the updated cursor with the hash information.
val compute_hash' :
(Node_type.t ->
[< `Hashed of Hash.t * Node_type.t | `Not_Hashed of Node_type.view ]) ->
t ->
t * Hash.tCompute the node hash of the node pointed by the given cursor. Tail recursive.
The function argument for short cutting, especially for Disk _. It can do either
* Obtain the node hash of the node somehow from an external source * Retrieve the view of the node to let compute' calculate the node hash of it
2 Statistics
2 Debug
val dot_of_cursor_ref : (t -> string) Stdlib.refPlaceholder of Graphviz rendering of cursors
module Monad : sig ... endmodule Cursor_storage : sig ... endval deep_stat : int32 -> t -> unit Lwt.tdebug