package plebeia

You can search for identifiers within the package.

in-package search v0.2.0

package plebeia

plebeia
- LICENSE
- README
- Library plebeia
  - Plebeia
    
    Internal
    
    Error
    
    Utils
    
    Exn
    
    Format
    
    String
    
    Hashtbl
    
    HashedType
    
    S
    
    Make
    
    SeededHashedType
    
    SeededS
    
    MakeSeeded
    
    List
    
    Open
    
    Option
    
    Op
    
    Result
    
    Monad
    
    S1
    
    Op
    
    Make1
    
    Op
    
    S2
    
    Op
    
    Make2
    
    Op
    
    Log
    
    Value
    
    Index
    
    Set
    
    Map
    
    Segment
    
    Context
    
    Node
    
    Node_tools
    
    Cursor
    
    Hash
    
    Node_hash
    
    Cursor_hash
    
    Lock
    
    Storage
    
    Chunk
    
    Node_storage
    
    Cursor_storage
    
    Hashcons
    
    Bud_cache
    
    Deep
    
    Roots
    
    Vc
    
    Stat
    
    Debug
    
    Traverse
    
    Diff
    
    Deep_stat
    
    Merkle_proof
    
    Cursor_tools
    
    GenTraverse
    
    Search
    
    Ediff
    
    Rand
    
    Gen
    
    Op
    
    RS
    
    Test_utils
    
    Exn
    
    Format
    
    String
    
    Hashtbl
    
    HashedType
    
    S
    
    Make
    
    SeededHashedType
    
    SeededS
    
    MakeSeeded
    
    List
    
    Open
    
    RS
    
    Error
    
    Result
    
    Op
    
    Value
    
    Segment
    
    Hash
    
    Hashcons
    
    Vc
    
    Roots
    
    RootHash
    
    Entry
    
    Stat
    
    Merkle_proof
- Sources
  - plebeia
    
    bud_cache.ml
    
    context.ml
    
    cursor.ml
    
    cursorM.ml
    
    cursor_hash.ml
    
    cursor_storage.ml
    
    cursor_tools.ml
    
    debug.ml
    
    deep.ml
    
    deep_stat.ml
    
    diff.ml
    
    ediff.ml
    
    error.ml
    
    gen.ml
    
    hash.ml
    
    hashcons.ml
    
    index.ml
    
    lock.ml
    
    log.ml
    
    merkle_proof.ml
    
    monad.ml
    
    node.ml
    
    node_hash.ml
    
    node_storage.ml
    
    node_tools.ml
    
    option.ml
    
    plebeia.ml
    
    plebeia__.ml
    
    plebeia_intf.ml
    
    rand.ml
    
    result.ml
    
    roots.ml
    
    search.ml
    
    segment.ml
    
    stat.ml
    
    storage.ml
    
    test_utils.ml
    
    traverse.ml
    
    utils.ml
    
    value.ml
    
    vc.ml
    
    xcstruct.ml

Legend:
Page
Library
Module
Module type
Parameter
Class
Class type
Source

Module `Internal.Cursor`Source

1 Zipper

Sourcetype Error.t +=

| Write of string

2 Types: Trail and cursor

Sourcetype modified =

| Modified
| Unmodified of Plebeia__.Node.indexed * Plebeia__.Node.hashed

Sourcetype trail = private

| Top
| Left of trail * Plebeia__.Node.node * modified
| Right of Plebeia__.Node.node * trail * modified
| Budded of trail * modified
| Extended of trail * Segment.t * modified

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.

Sourcetype cursor = private

| Cursor of trail * Plebeia__.Node.node * Plebeia__.Context.t
(*
The 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
*)

Sourcetype t = cursor

2 Constructor with invariant checks

Sourceval _Top : trail

Sourceval _Left : (trail * Plebeia__.Node.node * modified) -> trail

Sourceval _Right : (Plebeia__.Node.node * trail * modified) -> trail

Sourceval _Budded : (trail * modified) -> trail

Sourceval _Extended : (trail * Segment.t * modified) -> trail

Sourceval _Cursor : (trail * Plebeia__.Node.node * Plebeia__.Context.t) -> cursor

2 Creation

Sourceval empty : Plebeia__.Context.t -> t

Creates a cursor to a new, empty tree.

2 Accessors

Sourceval context : t -> Plebeia__.Context.t

Sourceval index : t -> Plebeia__.Index.t option

Get the index of the node pointed by the cursor, if indexed.

2 Segments

Sourceval segs_of_trail : trail -> Segment.t list

Segment side list of the given trail, splitted by buds

Sourceval segs_of_cursor : t -> Segment.t list

Segment side list of the given cursor, splitted by buds

Sourceval local_seg_of_trail : trail -> Segment.t

Segment side list of the given trail, splitted by buds

Sourceval local_seg_of_cursor : t -> Segment.t

Segment side list of the given cursor, splitted by buds

2 View

Sourceval view : t -> t * Plebeia__.Node.view

Get the view of the cursor. Returns also the updated cursor with the view.

Sourceval may_forget : t -> t option

If the node pointed by the cursor is indexed, forget the details

2 Zipper functions

Sourcetype access_result =

| Empty_bud
| Collide of cursor * Plebeia__.Node.view
| Middle_of_extender of cursor * Segment.t * Segment.t * Segment.t
| Reached of cursor * Plebeia__.Node.view

Result of access_gen

Sourcetype Error.t +=

| Access of access_result
| Move of string

Sourceval error_access : access_result -> ('a, Error.t) Result.t

Make an access result into an error

3 Simple 1 step cursor movement

Sourceval go_below_bud : t -> (t option, Error.t) Result.t

This function expects a cursor positionned on a bud and moves it one step below.

Sourceval go_down_extender : t -> (t, Error.t) Result.t

Go down an Extender node. The cursor must point to an Extender.

Sourceval go_side : Segment.side -> t -> (t, Error.t) Result.t

Go down an Internal node. The cursor must point to an Internal.

Sourceval go_up : t -> (t, Error.t) Result.t

Go up one level

3 Complex multi step cursor movement

Many of these functions fail when the given cursor does not point to a bud.

Sourceval access_gen : t -> Segment.t -> (access_result, Error.t) Result.t

Follow a segment. t must point to a bud. The function first go below the bud, then follow the segment.

Sourceval access_gen' : t -> Segment.t -> (access_result, Error.t) Result.t

Follow a segment. t can be any node.

Sourceval go_top : t -> (t, Error.t) Result.t

Move up to the top

Sourceval go_up_to_a_bud : t -> (t, Error.t) Result.t

Moves the cursor back to the bud above. Note that this is not like "cd ../".

If the cursor is already at a bud, it does not move it. This is super confusing. Do not use this function.

deprecated Use go_up_to_bud, which has better semantics

Sourceval go_up_to_bud : t -> (t, Error.t) Result.t

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.

Sourceval parent : t -> (t, Error.t) Result.t

Moves the cursor back to the bud above. Like "cd ../". The cursor must point to a bud otherwise parent fails.

Sourceval subtree : t -> Segment.t -> (t, Error.t) Result.t

Moves the cursor down a segment, to the root of a sub-tree. Think "cd segment/"

Sourceval create_subtree : t -> Segment.t -> (t, Error.t) Result.t

Create a subtree (bud). Think "mkdir segment". The cursor does NOT move from the original position.

Sourceval subtree_or_create : t -> Segment.t -> (t, Error.t) Result.t

Same as subtree but create a subtree if not exists

Source

val get : 
  t ->
  Segment.t ->
  (t * [ `Leaf of Plebeia__.Node.view | `Bud of Plebeia__.Node.view ], Error.t)
    Result.t

Gets a value if present in the current tree at the given segment.

Sourceval get_value : t -> Segment.t -> (t * Value.t, Error.t) Result.t

Gets a value or a bud at the given segment.

Sourceval insert : t -> Segment.t -> Value.t -> (t, Error.t) Result.t

Inserts a value at the given segment in the current tree. The cursor does NOT move from the original position.

Sourceval upsert : t -> Segment.t -> Value.t -> (t, Error.t) Result.t

Upserts. This can still fail if the segment leads to a subtree. The cursor does NOT move from the original position.

Sourceval update : t -> Segment.t -> Value.t -> (t, Error.t) Result.t

Update. A value must be bound at the segment.

Sourceval delete : t -> Segment.t -> (t, Error.t) Result.t

Delete a leaf or subtree. The cursor does NOT move from the original position.

Sourceval remove_empty_bud : t -> (t, Error.t) Result.t

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.

Source

val alter : 
  t ->
  Segment.segment ->
  (Plebeia__.Node.view option -> (Plebeia__.Node.node, Error.t) Result.t) ->
  (t, Error.t) Result.t

alter can easily break the invariants.

Source

val fold : 
  init:'acc ->
  t ->
  ('acc -> t -> [< `Continue | `Exit | `Up ] * 'acc) ->
  'acc

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.

Source

val traverse : 
  'a ->
  t list ->
  ('a -> t -> [< `Exit | `Up | `Continue ] * 'a) ->
  'a * t list

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 Statistics

Sourceval stat : t -> Stat.t

2 Debug

Sourceval dot_of_cursor_ref : (t -> string) ref

Placeholder of Graphviz rendering of cursors

package plebeia

Module Internal.CursorSource

Module `Internal.Cursor`Source