Struct History

pub struct History<T> { /* private fields */ }

A sequence of operations applied to a shared object.

A history is a sequence of operations that have been applied to a shared object. Each Entry in the history indicates either a call to or response from an operation performed by a specific process. It is possible for operations from different processes to be performed concurrently, which is modeled in a history by interleaving the call and response entries for those operations.

Examples

Consider a history of operations performed on a shared register, where processes can write values and read values that have been written. In the following example process P0 performs a write, after which process P1 performs a read.

use std::matches;
use todc_utils::{History, Action::{Call, Response}};
use todc_utils::linearizability::history::Entry;
use todc_utils::specifications::register::RegisterOperation::{Read, Write};

// P0 |--------|            Write("Hello, World!")
// P1            |--------| Read("Hello, World!")
let actions = vec![
    (0, Call(Write("Hello, World!"))),
    (0, Response(Write("World, World!"))),
    (1, Call(Read(None))),
    (1, Response(Read(Some("Hello, World!")))),
];

let history = History::from_actions(actions);
assert!(matches!(&history[0], Entry::Call(x)));

In the next example processes P0, P1, and P2 each perform a write while P3 performs three reads. Notice that the reads performed by P3 occur concurrently with the writes performed by other processes.

// P0 |--------------------| Write(0)
// P1 |--------------------| Write(1)
// P2 |--------------------| Write(2)
// P3   |--|                 Read(2)
// P3          |--|          Read(1)
// P3                 |--|   Read(0)
let actions = vec![
    (0, Call(Write(0))),
    (1, Call(Write(1))),
    (2, Call(Write(2))),
    (3, Call(Read(None))),
    (3, Response(Read(Some(2)))),
    (3, Call(Read(None))),
    (3, Response(Read(Some(1)))),
    (3, Call(Read(None))),
    (3, Response(Read(Some(0)))),
    (0, Response(Write(0))),
    (1, Response(Write(1))),
    (2, Response(Write(2))),
];

let history = History::from_actions(actions);
assert!(matches!(&history[0], Entry::Call(x)));

Implementations

impl<T> History<T>

pub fn from_actions(actions: Vec<(ProcessId, Action<T>)>) -> Self

Creates a history from a sequence of actions.

Panics

Panics if actions is empty.

Panics if the resulting history would be incomplete. That is, if there is some Call action that does not have a corresponding Response.

let incomplete_actions = vec![
    (0, Call(Write("Hello"))),
    (1, Call(Write("World"))),
    (0, Response(Write("Hello"))),
    // <-- Missing response to the call by process 1!
];

let history = History::from_actions(incomplete_actions);

Trait Implementations

impl<T: Clone> Clone for History<T>

fn clone(&self) -> History<T>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug> Debug for History<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T> Index<usize> for History<T>

type Output = Entry<T>

The returned type after indexing.

fn index(&self, i: usize) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<T> IndexMut<usize> for History<T>

fn index_mut(&mut self, i: usize) -> &mut Self::Output

Performs the mutable indexing (container[index]) operation.

impl<T: PartialEq> PartialEq for History<T>

fn eq(&self, other: &History<T>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T: Eq> Eq for History<T>

impl<T> StructuralPartialEq for History<T>