Implement storage (revision 2) module (#311)

* [core] apply rustfmt

* [core] fix warnings related to Wasm compilation

* [core] add SpreadLayout impl for DynamicAllocator

* [core] remove unused method on Bits256RefMut

* [core] apply rustfmt

* [core] remove some unneded ToDo comments

The ToDo comments have been moved to the associated PR description.

* [core] transit to new traits for LazyIndexMap

* [core] transit to new traits for storage::Vec

* [core] transit to new traits for storage::Stash

* [core] transit to new traits for storage::Bitvec

* [core] transit to new traits for dynamic storage allocator

* [core] transit to new traits for LazyHashMap

* [core] transit to new traits for storage::HashMap

* [core] apply rustfmt

* [core] remove old storage traits for storage::Pack

* [core] transit to new storage traits for LazyArray

* [core] transit to new storage traits for storage::SmallVec

* [core] transit to new storage traits for the rest of the lazy abstractions

* [core] transit to new storage traits for storage::Box

* [core] fix compile error in Drop impl for storage::Box

* [core] remove old storage trait impls for Bits256

* [core] remove old storage trait impls for dynamic storage allocator

* [core] apply rustfmt

* [core] remove old traits module

* [core] replace KeyPtr2 usage with KeyPtr

* [core] rename traits2 module to traits

* [core] apply rustfmt

* [core] add Drop impl to storage::Vec

* [core] don't clear storage if key is none for storage::Vec

* [core] impl Drop for storage::Stash

* [core] simplify trait bounds for LazyHashMap

* [core] impl Drop for storage::HashMap

* [core] add Drop impl for storage::SmallVec

* [core] add are_trait_objects lint as deny

* [core] fix minor formatting issue

* [core] add storage2::Memory utility

* [core] remove usage of storage::Pack from internals of storage::Bitvec

* [core] remove usage of storage::Pack from internals of storage::Stash

* [core] remove usage of storage::Pack from internals of storage::HashMap

* [core] add better Debug impl for LazyIndexMap

The improved impl shows the cached entries which were hidden in the old impl behind the UnsafeCell.

* [core] apply rustfmt

* [core] improve Debug impl for LazyHashMap

It now displays its internal cached entries.

* [core] improve Debug impl for lazy::Entry

* [core] improve Debug impl for LazyCell

* [core] improve Debug impl for LazyArray

* [core] apply rustfmt

* [core] add REQUIRES_DEEP_CLEAN_UP to SpreadLayout

With this we have a way for types to perform an optimized storage clean-up without having to load them in case they do not require a deep clean-up of their state.

* [core] implement REQUIRES_DEEP_CLEAN_UP for all built-in types

* [core] add non-storage trait impls for storage::HashMap

* [core] simplify traits bounds of SpreadLayout impl for storage::HashMap

* [core] fix bug in Wasm compilation

* [core] add initial unit tests for storage::HashMap

* [core] allow loading without key from LazyHashMap

* [core] merge storage::HashMap insert and insert_get and fix bugs with it

* [core] add new unit test for storage::HashMap

* [core] generally allow lazy loading without keys for lazy abstractions

* [core] apply rustfmt

* [core] remove outdated docs of storage::HashMap::insert

* [core] add unit test for storage::HashMap::contains_key

* [core] apply rustfmt to storage::HashMap unit tests

* [core] add unit test for storage::HashMap::{get, get_mut}

* [core] fix the doc comment of storage::HashMap::remove

* [core] add unit test for storage::HashMap::take

* [core] add unit test for storage::HashMap::insert

* [core] remove storage::HashMap::remove

The API cannot be implemented properly at this point.

* [core] implement Iterator::count efficiently for storage::HashMap iterators

* [core] add prelude trait impls for crypto hashers

* [core] add unit test for storage::HashMap::iter

* [core] remove outdated doc comment line

* [core] add doc comments to fowarding-to-packed utility functions

* [core] add some high-level documentation for some root storage2 modules

* [core] add some more high-level docs

* [core] add return value to storage::Stash::defrag

The returned value tells the caller how many storage cells have actually been freed by the routine.

* [core] add return value to storage::HashMap::defrag

* [core] add unit test for storage::HashMap::{values, values_mut}

Also add tests for Iterator::size_hint impls.

* [core] add tests for Iterator::size_hint impls of storage::Vec

* [core] add unit test for storage::HashMap::keys

* [core] add unit test for storage::HashMap::defrag

* [core] add unit tests for LazyIndexMap

* [core] remove lazy::Entry::take_value

* [core] remove LazyIndexMap::take

* [core] remove Entry::set_state

Uses have been replaced with Entry::replace_state.

* [core] remove Lazy{Array, HashMap}::take method

Replace uses with Lazy{Array, HashMap}::put_get(.., None)

* [core] add unit test for LazyIndexMap::put

* [core] add unit test for LazyIndexMap::swap

* [core] apply rustfmt

* [core] cover Default impl of LazyIndexMap with unit test

* [core] move imports to top for LazyIndexMap .rs file

* [core] refactor lazy::Entry internals a bit

* [core] add unit tests for Index impl of storage::Vec

* [core] add unit tests for Index impl of storage::SmallVec

* [core] add tests for Index impl of StorageStash

* [core] improve panic message for Index{Mut} impl of storage::Stash

* [core] add unit tests for Index{Mut} impl of storage::Stash

* [core] extend unit test for storage::Stash::get

* [core] disable certain tests in --release mode testing

* [core] add unit test for LazyIndexMap::{get, get_mut}

* [core] add some unit tests for LazyArray

* [core] add some more unit tests for LazyArray

* [core] add some more unit tests to LaryArray

* [core] apply rustfmt

* [core] add unit tests for LazyCell

* [core] add unit test for SpreadLayout impl of LazyCell

* [core] extend SpreadLayout test for LazyCell

* [core] extend SpreadLayout test to also cover the clear_spread impl

* [core] rename unit test for LazyCell

* [core] fix clippy warning

* [core] fix some LazyCell cache entry in lazy form

* [core] add new unit test for Debug impl of lazy initialized LazyCell

* [core] add more unit tests for lazily initialized LazyCell

* [core] implement shallow clean-up of storage via LazyCell

* [core] test that a lazily loaded LazyCell preserves its cached value

* [core] apply rustfmt

* [core] add additional check for LazyCell cache preservation

* [core] fix bug in LazyIndexMap::clear_packed_at

* [core] add unit test for SpreadLayout impl of LazyIndexMap

* [core] fix bug in LazyArray::clear_packed_at

* [core] add unit test for SpreadLayout impl of LazyArray

* [core] make LazyArray::capacity and SmallVec::capcity more user friendly

* [core] remove unnecessary trait bounds

* [core] remove more unnecessary trait bounds

* [core] add initial unit test for LazyHashMap

* [core] add unit test for LazyHashMap::key_at

* [core] apply rustfmt

* [core] indent a block in test

* [core] add unit test for LazyHashMap::put_get

* [core] add unit test for LazyHashMap::{get, get_mut}

* [core] add unit test for LazyHashMap::put

* [core] add unit test for LazyHashMap::swap

* [core] make hash builders reset their accumulator upon finalization

* [core] add unit test for SpreadLayout impl of LazyHashMap

* [core] fix unit test for LazyHashMap::key_at

Also add prefix to hash-key calculation.

* [core] add unit tests for SpreadLayout impl of storage::Vec

* [core] add unit tests for SpreadLayout impl of storage::SmallVec

* [core] add unit tests for SpreadLayout impl of storage::Stash

* [core] apply rustfmt

* [core] add unit tests for SpreadLayout impl of storage::HashMap

* [core] add unit test for DynamicAllocation::key

* [core] add unit tests for SpreadLayout impl of storage::Bitvec

* [core] fix LazyCell::get unit test

* [core] remove unused dependencies from Cargo.toml

* [core] add missing docs for storage::{Stash, HashMap}

* [core] deny missing docs of public items

* [core] add Debug impl to storage::Box

* [core] add unit tests for storage::Box

* [core] remove internal Pack::{get, get_mut} methods

* [core] fix bug in storage::Memory::{get, get_mut} API

* [core] add unit tests for storage::Pack

* [core] improve storage::Pack unit tests

* [core] experimental inline(never) for debug_assertions compilation

* [core] apply rustfmt

* [core] remove experimental #[inline(never)]

* [core] add unit test for Default impl of storage::Pack

* [core] add unit tests for storage::Memory

* [core] fix a unit test for storage::Box

The storage::Box tests did not reset the dynamic storage allocator instance in between their runs which caued them to have side effects on to each other if run single threaded.

* [core] fix minor bug in BitRefMut utility of storage::Bitvec

* [core] cover storage::Bitvec::get_mut in get_works unit test

* [core] add unit tests for BitRefMut utility of storage::Bitvec

* [core] apply rustfmt

* [core] improve panic message when encountering a double free

* [core] adjust double free unit test for storage::Box

* [core] improve double free of dynamic storage panic message

* [core] apply rustfmt

* [core] merge Bits256Ref and Bits256RefMut into ChunkRef<T>

* [core] split access.rs into bitref.rs and bitsref.rs

* [core] apply rustfmt

* [core] replace transmute with pointer cast

Thanks clippy!

* [core] add comment to explain repr(C)

* [core] add PartialEq and Eq impls to BitRefMut

* [core] add unit tests for ChunkRef

* [core] add failure unit tests for dynamic storage allocator

* [core] fix bug in SpreadLayout impl of Option<T>

* [core] add unit test for dynamic storage allocator SpreadLayout impl

* [core] fix SpreadLayout impl for Result<T, E>

* [core] fix yet another bug in SpreadLayout impl of Result<T, E>

* [core] move forward_supported_array_lens macro to usage site

* [core] refactor some code duplication with clear_spread_root_opt

* [core] fix doc comment in storage::Pack

* [core] remove some unused unsafe blocks

They are going to be re-introduced once the unsafe_op_in_unsafe_fn lint has been implemented in the Rust compiler.

* fix typo

Co-authored-by: Andrew Jones <ascjones@gmail.com>

* fix typo

Co-authored-by: Andrew Jones <ascjones@gmail.com>

* fix typo

Co-authored-by: Andrew Jones <ascjones@gmail.com>

* fix typo

Co-authored-by: Andrew Jones <ascjones@gmail.com>

* fix typo

Co-authored-by: Andrew Jones <ascjones@gmail.com>

* [core] remove usage of storage::Pack in dynamic storage allocator

* [core] improve panic message in Lazy::{get, get_mut}

* [core] add test for SpreadLayout::clear_spread impl of dynamic storage alloc

* [core] remove code dupe

* [core] refactor clear_spread_root_opt utility function

* [core] implement SpreadLayout::REQUIRES_DEEP_CLEAN_UP for some types

* [core] move from bool to u8 for Option and Result SpreadLayout impls

* [core] fix bug in SpreadLayout impl for Option

* fix typo

Co-authored-by: Andrew Jones <ascjones@gmail.com>

* [core] update LazyCell SAFETY comment

* [core] update Entry docs

* [core] remove unneeded code in lazy::Entry::pull_packed_root

* fix typo

Co-authored-by: Andrew Jones <ascjones@gmail.com>

* fix typo

Co-authored-by: Andrew Jones <ascjones@gmail.com>

* fix typo

Co-authored-by: Andrew Jones <ascjones@gmail.com>

* fix typo

Co-authored-by: Andrew Jones <ascjones@gmail.com>

* [core] remove commented out code

* [core] add new unit test for dynamic storage allocator

* [core] refactor global storage allocator initialization routines

* [core] fix Wasm compilation errors

* [core] apply rustfmt

* [core] surpress bad clippy lint

* [core] remove dead code

* [core] improve call_setup_works test

* [core] fix bug in initialize_for for off-chain env

* [core] initial steps to factor out BitStash from DynamicAllocator

* [core] apply rustfmt

* [core] add Derive impl for BitStash

* [core] make use of storage::BitStash from dynamic storage allocator

* [core] add unit tests for storage::BitStash

* [core] apply rustfmt

* [core] remove invalid TODO comment

* [core] fix some out of bounds panic messages

* [core] remove deliberate memory leak in test suite

* [core] fix build failure for Wasm target

* [core] add unit tests for SpreadLayout & PackedLayout impls of primitives

* [core] add unit tests for packed layout explicitely

* Fix some typos

* Add simple double ended iter test

* typos

* comment typos

* split hashmap to hash map in comments

* fix typo

Co-authored-by: Andrew Jones <ascjones@gmail.com>

* fix typo in unreachable! message

Co-authored-by: Andrew Jones <ascjones@gmail.com>

* fix typo in expects message

Co-authored-by: Andrew Jones <ascjones@gmail.com>

* fix typo

Co-authored-by: Andrew Jones <ascjones@gmail.com>

* fix typo

Co-authored-by: Andrew Jones <ascjones@gmail.com>

* [core] add more comments to storage2::HashMap::defrag

* [core] make early return for storage2::HashMap::defrag for limit = 0

* [core] improve storage2::HashMap::contains_key implementation

* [core] rename new_vec_works test to new_works

* [core] apply Andrew's suggestions (and more)

* [core] fix typo: increase -> decrease

* [core] add panic to Bitvec::push in case it reached its maximum capacity

* [core] update comments for storage bit stash

* [core] add more explanation comments

* [core] some more renamings of test internals

* improve reasoning

Co-authored-by: Andrew Jones <ascjones@gmail.com>

* fix typo

Co-authored-by: Andrew Jones <ascjones@gmail.com>

Co-authored-by: Andrew Jones <ascjones@gmail.com>
16 jobs for master in 8 minutes and 16 seconds (queued for 3 seconds)
Status Job ID Name Coverage
  Check
passed #519368
linux-docker
check-std

00:01:57

passed #519369
linux-docker
check-wasm

00:01:44

 
  Workspace
passed #519370
linux-docker
build-std

00:02:07

passed #519371
linux-docker
build-wasm

00:00:54

passed #519374
linux-docker
clippy-std

00:01:42

passed #519375
linux-docker
clippy-wasm

00:01:41

passed #519373
linux-docker
codecov

00:03:21

passed #519376
linux-docker
fmt

00:00:35

passed #519372
linux-docker
test

00:02:41

 
  Examples
passed #519379
linux-docker
examples-clippy-std

00:00:51

passed #519380
linux-docker
examples-clippy-wasm

00:01:11

passed #519381
linux-docker
examples-contract-build

00:00:52

passed #519378
linux-docker
examples-fmt

00:00:16

passed #519382
linux-docker
examples-generate-metadata

00:01:06

passed #519377
linux-docker
examples-test

00:00:56

 
  Publish
passed #519383
linux-docker
publish-docs

00:01:39