#run-time #data-structures #constant-time

cw-wormhole

A CosmWasm map that allows incrementing and decrementing values from the past

5 stable releases

2.4.2 Jul 22, 2024
2.4.0 Jul 21, 2024
2.3.0 Oct 18, 2023
2.2.0 Jul 9, 2023

#58 in #constant-time

Download history 14/week @ 2024-06-24 34/week @ 2024-07-08 159/week @ 2024-07-15 344/week @ 2024-07-22 107/week @ 2024-07-29 123/week @ 2024-08-05 285/week @ 2024-08-12 233/week @ 2024-08-19 21/week @ 2024-08-26 13/week @ 2024-09-02 16/week @ 2024-09-09 14/week @ 2024-09-16 34/week @ 2024-09-23 31/week @ 2024-09-30

97 downloads per month
Used in 5 crates (2 directly)

BSD-3-Clause

16KB
170 lines

🌀⏱️ CW Wormhole ⏱️🌀

A CosmWasm KV store that allows setting values from the past. For example:

use cosmwasm_std::{testing::mock_dependencies, Uint128, Addr};
use cw_wormhole::Wormhole;
let storage = &mut mock_dependencies().storage;
let w: Wormhole<Addr, Uint128> = Wormhole::new("ns");
let key = Addr::unchecked("violet");

// increment the value by one at time 10.
w.increment(storage, key.clone(), 10, Uint128::new(1))
    .unwrap();

// increment the value by two at time 9.
w.increment(storage, key.clone(), 9, Uint128::new(2))
    .unwrap();

// the value at time 10 is now three.
assert_eq!(
    w.load(storage, key, 10).unwrap(),
    Some(Uint128::new(3))
);

Loading a value from the map is always constant time. Updating values in the map is O(# future values). This has the effect of moving the complexity of incrementing a future value into the present.

For a more in-depth analysis of the runtime of this data structure, please see this essay.

Limitations

Reference types may not be used as keys.

Consider the trait bound:

    for<'a> &'a (K, u64): PrimaryKey<'a>

This bound says, for any lifetime 'a a reference to the tuple (K, u64) will be a valid PrimaryKey with lifetime 'a, thus we can store tuples of this type in the map.

In order to allow K to have a lifetime (call it 'k), we'd need to write:

    for<'a where 'a: 'k> &'a (K, u64): PrimaryKey<'a>

As the lifetime of the primary key is 'a + 'k (the minimum of the key's lifetime and the tuple's lifetime).

Unfourtunately, Rust does not support this. There is an RFC to implement it here.

Dependencies

~5–6.5MB
~141K SLoC