On This Page
Legend:
Library
Module
Module type
Parameter
Class
Class type
Library
Module
Module type
Parameter
Class
Class type
package store
Store: a versioned mutable store
This library offers an imperative interface to manipulate a 'store', a bag of mutable objects (in particular, references), with the capability to save a snapshot of the current state of the store at any point and restore it later zero, one or several times.
This is useful to implement imperative data structures that support backtracking. For example one can implement a union-find data structure (or a graph, a skip list, etc.), using our store references instead of OCaml's native mutable state. Using a store lets you save the state of the union-find at any point, rollback changes on error, etc.
In addition we provide a transactional API that is slightly more efficient than the general snapshot mechanism for transactional and backtracking workloads that never need to restore a given state more than once.
Stores
type store = tval create : unit -> storeStore references
module Ref : sig ... endMutable references inside a given store.
Snapshots
Restore a snapshot: all mutable data in the store reverts to its state at the time the snapshot was captured.
A snapshot may be restored zero, one or several times.
A snapshot may be invalidated if semi-persistent operations are mixed incorrectly with persistent operations. See the documentation of the transaction type below.
The time complexity of restore is linear in the number of references that have been modified since the snapshot was taken.
Transactions
A transaction represents an interval in the program execution where an ephemeral copy of the store is preserved. The transaction is created by calling transaction, and terminated by calling rollback or commit.
Terminating a transaction invalidates it: trying to terminate it again is a programming error and fails with an Invalid_argument exception.
Transactions can be nested: one can create a transaction within an ongoing transaction. We say that the inner transaction is a "child" of the outer transaction. This nesting must be well-parenthesized: terminating a transaction invalidates all descendant transactions.
The time complexity of terminating a transaction is linear in the number of references that have been modified since the transaction began.
Snapshots and transactions may be mixed, but a (persistent) snapshot created inside a transaction is invalidated when the transaction terminates. For example:
- Using snapshots locally within a given transaction works as expected.
- Using transactions locally on a store that also has snapshots outside the transactions works as expected.
- On the other hand, it would be incorrect to create a transaction T, create a snapshot S within the transaction, terminate T, and then try to restore the snapshot S.
val transaction : store -> transactionBegins a new transaction.
val rollback : store -> transaction -> unitrollback store transaction rolls back store to its state when transaction started.
This invalidates transaction and any child transaction or snapshot created after transaction started.
val commit : store -> transaction -> unitcommit store transaction terminates transaction, keeping store in its current state.
This invalidates transaction and any child transaction or snapshot created after transaction started.
High-level wrappers
val temporarily : store -> (unit -> 'a) -> 'atemporarily store f executes f () inside a local transaction, and rolls back any store change once f () returns a value or fails with an exception.
val tentatively : store -> (unit -> 'a) -> 'atentatively store f executes f () inside a local transaction. If f () returns a value, then the changes are kept; they are rolled back if f () fails with an exception.
On This Page