Skip to content

TLog[A: Comparable[A] val, optional T: (Integer[T] val & Unsigned), optional B: (BiasGreater val | BiasLesser val)]

[Source]

A sorted list of ordered log entries, each with a value and logical timestamp. (U64 by default, though it may be any unsigned integer type). The list of entries is sorted in descending timestamp order (with the most recent entries appearing first in the list).

If the logical timestamp is equal for two compared entries, the sort order be determined by the bias type parameter. BiasGreater implies that the greater of the two compared values will appear as more recent, while BiasLesser implies the opposite. The default bias is BiasGreater. If both the timestamp and value properties of the log entries under comparison are equal, they are considered duplicates of each other, and all but one will be discarded.

A cutoff timestamp is also specified, and all entries whose timestamp is less than the cutoff will be discarded. Entries whose timestamps are greater than or equal to the cutoff will be retained until the cutoff is updated. Using a cutoff timestamp of zero is allowed, and indicates that all entries should be retained, allowing the size of the data structure to grow without bound.

The cutoff timestamp can only ever be increased (always moving forward in time, never backward). When reconciling concurrent changes to the cutoff timestamp, the higher of the values is retained, preserving this property.

Because there is a deterministic total order for all entries, conflicts can be resolved in a commutative way. Because duplicate entries are discarded, updates are idempotent. Because the cutoff timestamp can only ever increase, those conflicts can also be resolved in a commutative, idempotent way. Thus, the resulting list of entries is eventually consistent in all replicas. The same bias must be used on all replicas for tie results to be consistent.

All mutator methods accept and return a convergent delta-state.

class ref TLog[A: Comparable[A] val, optional T: (Integer[T] val & Unsigned), optional B: (BiasGreater val | BiasLesser val)] is
  Equatable[TLog[A, T, B] ref] ref,
  Convergent[TLog[A, T, B] ref] ref,
  Replicated ref

Implements

Constructors

create

[Source]

new ref create()
: TLog[A, T, B] ref^

Returns

  • TLog[A, T, B] ref^

Public Functions

is_empty

[Source]

Return true if the data structure contains no information (bottom state).

fun box is_empty()
: Bool val

Returns

apply

[Source]

Return the timestamp and value of the log entry at the given index.

fun box apply(
  index: USize val)
: (A , T) ?

Parameters

Returns

  • (A , T) ?

size

[Source]

Return the number of entries currently stored in the log.

fun box size()
: USize val

Returns

entries

[Source]

Return an iterator over the timestamp/value entries in the log.

fun box entries()
: Iterator[(A , T)] ref^

Returns

cutoff

[Source]

Return the current cutoff timestamp.

fun box cutoff()
: T

Returns

  • T

write[optional D: TLog[A, T, B] ref]

[Source]

Write the value and timestamp to the log, preserving sort order, ignoring the write if its timestamp is earlier than the cutoff timestamp.

fun ref write[optional D: TLog[A, T, B] ref](
  value': A,
  timestamp': T,
  delta': D = D)
: D^

Parameters

  • value': A
  • timestamp': T
  • delta': D = D

Returns

  • D^

raise_cutoff[optional D: TLog[A, T, B] ref]

[Source]

Set the cutoff timestamp (only if it higher than the current value). All entries earlier than the new cutoff timestamp will be discarded.

fun ref raise_cutoff[optional D: TLog[A, T, B] ref](
  cutoff': T,
  delta': D = D)
: D^

Parameters

  • cutoff': T
  • delta': D = D

Returns

  • D^

trim[optional D: TLog[A, T, B] ref]

[Source]

Set the cutoff timestamp to the timestamp of the nth element, so that at least n' entries will be retained locally, but discarding all entries of an earlier timestamp than that of the nth entry. If fewer than n' entries are present, the cutoff timestamp will remain unchanged. If n' is zero, the effect is the same as calling the clear method.

fun ref trim[optional D: TLog[A, T, B] ref](
  n': USize val,
  delta': D = D)
: D^

Parameters

  • n': USize val
  • delta': D = D

Returns

  • D^

clear[optional D: TLog[A, T, B] ref]

[Source]

Raise the cutoff timestamp to be the timestamp of the latest entry plus one, such that all local entries in the log will be discarded due to having timestamps earlier than the cutoff timestamp. If there are no entries in the local log, this method will have no effect.

fun ref clear[optional D: TLog[A, T, B] ref](
  delta': D = D)
: D^

Parameters

  • delta': D = D

Returns

  • D^

converge

[Source]

Converge from the given TLog into this one, inserting any new entries, ignoring any duplicate entries, and respecting the cutoff timestamp. Returns true if the convergence added new information to the data structure.

fun ref converge(
  that: TLog[A, T, B] box)
: Bool val

Parameters

  • that: TLog[A, T, B] box

Returns

string

[Source]

Return a best effort at printing the log. If A and T are Stringable, use the string representation of them; otherwise print as question marks.

fun box string()
: String iso^

Returns

ne

[Source]

fun box ne(
  that: TLog[A, T, B] box)
: Bool val

Parameters

  • that: TLog[A, T, B] box

Returns

eq

[Source]

fun box eq(
  that: TLog[A, T, B] box)
: Bool val

Parameters

  • that: TLog[A, T, B] box

Returns

from_tokens

[Source]

Deserialize an instance of this data structure from a stream of tokens.

fun ref from_tokens(
  that: TokensIterator ref)
: None val ?

Parameters

Returns

each_token

[Source]

Serialize the data structure, capturing each token into the given Tokens.

fun ref each_token(
  tokens: Tokens ref)
: None val

Parameters

Returns