Repository: NethermindEth/juno
Pull request #143 (2022-04-30 15:21:46)

Block Specific Database
## Changes:
- Create the new database type `BlockSpecificDatabase` inside the `db` package, to store (key, value) pairs that need to have a history of changes in the blockchain, using the block number as the marker.
- The main way to interact with the database is using the methods `Get` and `Put`.
- The database store the keys and values as `[]byte`, but `Get` and `Put` interacts with the keys and values as interfaces (`Key`, `Value`) like this:

```go
// Key is an interface to represent a key in the database.
// A database key must be able to marshal itself to an array of bytes.
type Key interface {
	Marshal() ([]byte, error)
}

// Value is an interface to represent a value in the database.
// A database value must be able to marshal and unmarshal itself from an array of bytes.
type Value interface {
	Marshal() ([]byte, error)
	Unmarshal([]byte) error
}
```

> To store keys and values in the database, the types must implement the `Key` and `Value` interfaces respectively.

## Types of changes

What types of changes does your code introduce?
_Put an `x` in the boxes that apply_

- [ ] Bugfix (non-breaking change which fixes an issue)
- [x] New feature (non-breaking change which adds functionality)
- [ ] Breaking change (fix or feature that would cause existing functionality to not work as expected)
- [ ] Documentation Update
- [ ] Code style update (formatting, renaming)
- [ ] Refactoring (no functional changes, no api changes)
- [ ] Build related changes
- [ ] Other (please describe): 

## Testing
**Requires testing**

- [x] Yes
- [ ] No

**In case you checked yes, did you write tests??**

- [x] Yes
- [ ] No

codecov[bot]: # [Codecov](https://codecov.io/gh/NethermindEth/juno/pull/143?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=NethermindEth) Report
> Merging [#143](https://codecov.io/gh/NethermindEth/juno/pull/143?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=NethermindEth) (432bc73) into [main](https://codecov.io/gh/NethermindEth/juno/commit/9e8144a9fbc4dc88d3c671cea1a9d1205ef0a0ff?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=NethermindEth) (9e8144a) will **decrease** coverage by `2.76%`.
> The diff coverage is `64.70%`.

```diff
@@             Coverage Diff             @@
##              main     #143      +/-   ##
===========================================
- Coverage   100.00%   97.23%   -2.77%     
===========================================
  Files           19       21       +2     
  Lines         1202     1304     +102     
===========================================
+ Hits          1202     1268      +66     
- Misses           0       24      +24     
- Partials         0       12      +12     
```

| Flag | Coverage Δ | |
|---|---|---|
| unittests | `97.23% <64.70%> (-2.77%)` | :arrow_down: |

Flags with carried forward coverage won't be shown. [Click here](https://docs.codecov.io/docs/carryforward-flags?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=NethermindEth#carryforward-flags-in-the-pull-request-comment) to find out more.

| [Impacted Files](https://codecov.io/gh/NethermindEth/juno/pull/143?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=NethermindEth) | Coverage Δ | |
|---|---|---|
| [pkg/db/blockSpecific.go](https://codecov.io/gh/NethermindEth/juno/pull/143/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=NethermindEth#diff-cGtnL2RiL2Jsb2NrU3BlY2lmaWMuZ28=) | `49.29% <49.29%> (ø)` | |
| [pkg/db/sortedList.go](https://codecov.io/gh/NethermindEth/juno/pull/143/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=NethermindEth#diff-cGtnL2RiL3NvcnRlZExpc3QuZ28=) | `100.00% <100.00%> (ø)` | |

------

[Continue to review full report at Codecov](https://codecov.io/gh/NethermindEth/juno/pull/143?src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=NethermindEth).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=NethermindEth)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/NethermindEth/juno/pull/143?src=pr&el=footer&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=NethermindEth). Last update [9e8144a...432bc73](https://codecov.io/gh/NethermindEth/juno/pull/143?src=pr&el=lastupdated&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=NethermindEth). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=NethermindEth).


Patch:
diff --git a/pkg/db/blockSpecific.go b/pkg/db/blockSpecific.go
new file mode 100644
index 00000000..764b3eaf
--- /dev/null
+++ b/pkg/db/blockSpecific.go
@@ -0,0 +1,134 @@
+package db
+
+import (
+	"encoding/binary"
+	"encoding/json"
+	"fmt"
+	"github.com/NethermindEth/juno/internal/log"
+)
+
+// BlockSpecificDatabase is a database to store values that must have a history of versions on the blockchain.
+// To get and put objects in the database is needed the key and a block number.
+type BlockSpecificDatabase struct {
+	database Databaser
+}
+
+// Key is an interface to represent a key in the database.
+// A database key must be able to marshal itself to an array of bytes.
+type Key interface {
+	Marshal() ([]byte, error)
+}
+
+// Value is an interface to represent a value in the database.
+// A database value must be able to marshal and unmarshal itself from an array of bytes.
+type Value interface {
+	Marshal() ([]byte, error)
+	Unmarshal([]byte) error
+}
+
+// NewBlockSpecificDatabase creates a new instance of BlockSpecificDatabase
+func NewBlockSpecificDatabase(database Databaser) *BlockSpecificDatabase {
+	return &BlockSpecificDatabase{database: database}
+}
+
+// Get sets to `value` (must be a pointer), the value associated with the given key, and block number.
+// If the database does not have a value in the requested block, it sets to `value` the value in the closest
+// block less than the blockNumber. Returns true if the value is found and false if not.
+func (db *BlockSpecificDatabase) Get(key Key, blockNumber uint64, value Value) bool {
+	// Get the sortedList of block versions
+	keyRaw, err := key.Marshal()
+	if err != nil {
+		// notest
+		panicWithError(err)
+	}
+	data := db.get(keyRaw)
+	if data == nil {
+		return false
+	}
+	// Decode the data as a sortedList
+	var list sortedList
+	if err := json.Unmarshal(data, &list); err != nil {
+		// notest
+		panicWithError(err)
+	}
+	// Get the best fit
+	bestFit, ok := list.Search(blockNumber)
+	if !ok {
+		return false
+	}
+	// Build the compound key
+	keyRaw = newCompoundedKey(keyRaw, bestFit)
+	// Get the element
+	data = db.get(keyRaw)
+	if data == nil {
+		// notest
+		panicWithError(fmt.Errorf("unexpected not found for key %s at block %d", string(keyRaw), blockNumber))
+	}
+	if err := value.Unmarshal(data); err != nil {
+		// notest
+		panicWithError(err)
+	}
+	return true
+}
+
+// Put stores the given value at the tuple (key,blockNumber).
+func (db *BlockSpecificDatabase) Put(key Key, blockNumber uint64, value Value) {
+	// Create/Update the sortedList
+	rawKey, err := key.Marshal()
+	if err != nil {
+		// notest
+		panicWithError(err)
+	}
+	rawList := db.get(rawKey)
+	var list sortedList
+	if rawList != nil {
+		if err := json.Unmarshal(rawList, &list); err != nil {
+			// notest
+			panicWithError(err)
+		}
+	}
+	list.Add(blockNumber)
+	newRawList, err := json.Marshal(&list)
+	if err != nil {
+		// notest
+		panicWithError(err)
+	}
+	db.put(rawKey, newRawList)
+
+	rawKey = newCompoundedKey(rawKey, blockNumber)
+	rawValue, err := value.Marshal()
+	if err != nil {
+		// notest
+		panicWithError(err)
+	}
+	db.put(rawKey, rawValue)
+}
+
+func (db *BlockSpecificDatabase) get(key []byte) []byte {
+	data, err := db.database.Get(key)
+	if err != nil {
+		// notest
+		panicWithError(err)
+	}
+	return data
+}
+
+func (db *BlockSpecificDatabase) put(key []byte, value []byte) {
+	err := db.database.Put(key, value)
+	if err != nil {
+		// notest
+		panicWithError(err)
+	}
+}
+
+func newCompoundedKey(key []byte, blockNumber uint64) []byte {
+	key = append(key, '.')
+	bn := make([]byte, 8)
+	binary.LittleEndian.PutUint64(bn, blockNumber)
+	return append(key, bn...)
+}
+
+func panicWithError(err error) {
+	log.Default.With("error", err).Error("unexpected error")
+	panic(any(err))
+}
diff --git a/pkg/db/sortedList.go b/pkg/db/sortedList.go
new file mode 100644
index 00000000..491db4be
--- /dev/null
+++ b/pkg/db/sortedList.go
@@ -0,0 +1,42 @@
+package db
+
+import "sort"
+
+type sortedList []uint64
+
+func (s sortedList) searchIndex(x uint64) int {
+	return sort.Search(len(s), func(i int) bool {
+		return x < s[i]
+	})
+}
+
+func (s sortedList) Search(x uint64) (uint64, bool) {
+	if len(s) == 0 {
+		return 0, false
+	}
+	i := s.searchIndex(x)
+	if i == len(s) {
+		return s[len(s)-1], true
+	}
+	if i == 0 {
+		return 0, false
+	}
+	return s[i-1], true
+}
+
+func (s *sortedList) Add(x uint64) {
+	i := s.searchIndex(x)
+	if i == 0 {
+		*s = append([]uint64{x}, *s...)
+		return
+	}
+	if (*s)[i-1] == x {
+		return
+	}
+	if i == len(*s) {
+		*s = append(*s, x)
+		return
+	}
+	*s = append((*s)[:i+1], (*s)[i:]...)
+	(*s)[i] = x
+}


Test patch:
diff --git a/pkg/db/blockSpecific_test.go b/pkg/db/blockSpecific_test.go
new file mode 100644
index 00000000..f96162b7
--- /dev/null
+++ b/pkg/db/blockSpecific_test.go
@@ -0,0 +1,171 @@
+package db
+
+import (
+	"bytes"
+	"testing"
+)
+
+type TestKey []byte
+
+func (x *TestKey) Marshal() ([]byte, error) {
+	return *x, nil
+}
+
+type TestValue []byte
+
+func (x *TestValue) Marshal() ([]byte, error) {
+	return *x, nil
+}
+
+func (x *TestValue) Unmarshal(data []byte) error {
+	*x = data
+	return nil
+}
+
+func TestBlockSpecificDatabase_Put(t *testing.T) {
+	tests := [...]struct {
+		Key         TestKey
+		Value       TestValue
+		BlockNumber uint64
+	}{
+		{
+			Key:         []byte("Key1"),
+			Value:       []byte("Value1"),
+			BlockNumber: 0,
+		},
+		{
+			Key:         []byte("Key1"),
+			Value:       []byte("Value2"),
+			BlockNumber: 2,
+		},
+		{
+			Key:         []byte("Key1"),
+			Value:       []byte("Value3"),
+			BlockNumber: 5,
+		},
+		{
+			Key:         []byte("Key2"),
+			Value:       []byte("Value1"),
+			BlockNumber: 1,
+		},
+		{
+			Key:         []byte("Key2"),
+			Value:       []byte("Value2"),
+			BlockNumber: 3,
+		},
+		{
+			Key:         []byte("Key2"),
+			Value:       []byte("Value3"),
+			BlockNumber: 4,
+		},
+	}
+
+	database := New(t.TempDir(), 0)
+	db := NewBlockSpecificDatabase(database)
+
+	for _, test := range tests {
+		db.Put(&test.Key, test.BlockNumber, &test.Value)
+	}
+}
+
+func TestBlockSpecificDatabase_Get(t *testing.T) {
+	data := [...]struct {
+		Key         TestKey
+		Value       TestValue
+		BlockNumber uint64
+	}{
+		{
+			Key:         []byte("Key1"),
+			Value:       []byte("Value1"),
+			BlockNumber: 0,
+		},
+		{
+			Key:         []byte("Key1"),
+			Value:       []byte("Value2"),
+			BlockNumber: 2,
+		},
+		{
+			Key:         []byte("Key2"),
+			Value:       []byte("Value1"),
+			BlockNumber: 3,
+		},
+		{
+			Key:         []byte("Key1"),
+			Value:       []byte("Value3"),
+			BlockNumber: 5,
+		},
+	}
+
+	database := New(t.TempDir(), 0)
+	db := NewBlockSpecificDatabase(database)
+
+	for _, d := range data {
+		db.Put(&d.Key, d.BlockNumber, &d.Value)
+	}
+
+	tests := [...]struct {
+		Key         TestKey
+		BlockNumber uint64
+		Want        TestValue
+		Ok          bool
+	}{
+		{
+			Key:         []byte("Key1"),
+			Want:        []byte("Value1"),
+			BlockNumber: 0,
+			Ok:          true,
+		},
+		{
+			Key:         []byte("Key1"),
+			Want:        []byte("Value1"),
+			BlockNumber: 1,
+			Ok:          true,
+		},
+		{
+			Key:         []byte("Key1"),
+			Want:        []byte("Value2"),
+			BlockNumber: 2,
+			Ok:          true,
+		},
+		{
+			Key:         []byte("Key1"),
+			Want:        []byte("Value2"),
+			BlockNumber: 3,
+			Ok:          true,
+		},
+		{
+			Key:         []byte("Key1"),
+			Want:        []byte("Value3"),
+			BlockNumber: 5,
+			Ok:          true,
+		},
+		{
+			Key:         []byte("Key1"),
+			Want:        []byte("Value3"),
+			BlockNumber: 50000,
+			Ok:          true,
+		},
+		{
+			Key:         []byte("Key2"),
+			Want:        []byte{},
+			BlockNumber: 1,
+			Ok:          false,
+		},
+		{
+			Key:         []byte("Key3"),
+			Want:        []byte{},
+			BlockNumber: 50000,
+			Ok:          false,
+		},
+	}
+	for _, test := range tests {
+		var result TestValue
+		ok := db.Get(&test.Key, test.BlockNumber, &result)
+		if ok != test.Ok {
+			t.Errorf("unexpected OK result for Get(%s,%d)", string(test.Key), test.BlockNumber)
+		}
+		if ok && bytes.Compare(result, test.Want) != 0 {
+			t.Errorf("db.Get(%s, %d) = %s, want: %s", string(test.Key), test.BlockNumber, string(result), test.Want)
+		}
+	}
+}
diff --git a/pkg/db/sortedList_test.go b/pkg/db/sortedList_test.go
new file mode 100644
index 00000000..c9d331ad
--- /dev/null
+++ b/pkg/db/sortedList_test.go
@@ -0,0 +1,118 @@
+package db
+
+import (
+	"testing"
+)
+
+func TestSortedList_Search(t *testing.T) {
+	tests := []struct {
+		SortedList   sortedList
+		Search, Want uint64
+		Ok           bool
+	}{
+		{
+			SortedList: []uint64{1, 2, 3, 4, 5},
+			Search:     3,
+			Want:       3,
+			Ok:         true,
+		},
+		{
+			SortedList: []uint64{1, 2, 3, 4, 5},
+			Search:     1,
+			Want:       1,
+			Ok:         true,
+		},
+		{
+			SortedList: []uint64{1, 2, 3, 4, 5},
+			Search:     5,
+			Want:       5,
+			Ok:         true,
+		},
+		{
+			SortedList: []uint64{1, 2, 4, 5},
+			Search:     3,
+			Want:       2,
+			Ok:         true,
+		},
+		{
+			SortedList: []uint64{2, 4, 5},
+			Search:     1,
+			Want:       0,
+			Ok:         false,
+		},
+		{
+			SortedList: []uint64{2, 4, 5},
+			Search:     100,
+			Want:       5,
+			Ok:         true,
+		},
+		{
+			SortedList: []uint64{},
+			Search:     100,
+			Want:       0,
+			Ok:         false,
+		},
+	}
+	for _, test := range tests {
+		result, ok := test.SortedList.Search(test.Search)
+		if result != test.Want || ok != test.Ok {
+			t.Errorf("%+v.Search(%d) = %d, %t, want: %d, %t", test.SortedList, test.Search, result, ok, test.Want, test.Ok)
+		}
+	}
+}
+
+func TestSortedList_Add(t *testing.T) {
+	tests := []struct {
+		SortedList sortedList
+		Value      uint64
+		Want       sortedList
+	}{
+		{
+			SortedList: []uint64{1, 2, 3, 4, 5},
+			Value:      3,
+			Want:       []uint64{1, 2, 3, 4, 5},
+		},
+		{
+			SortedList: []uint64{1, 2, 4, 5},
+			Value:      3,
+			Want:       []uint64{1, 2, 3, 4, 5},
+		},
+		{
+			SortedList: []uint64{1, 2, 4, 5},
+			Value:      0,
+			Want:       []uint64{0, 1, 2, 4, 5},
+		},
+		{
+			SortedList: []uint64{1, 2, 4, 5},
+			Value:      6,
+			Want:       []uint64{1, 2, 4, 5, 6},
+		},
+		{
+			SortedList: []uint64{},
+			Value:      3,
+			Want:       []uint64{3},
+		},
+	}
+	for _, test := range tests {
+		l := make([]uint64, len(test.SortedList))
+		copy(l, test.SortedList)
+		sl := sortedList(l)
+
+		sl.Add(test.Value)
+		if !equals(sl, test.Want) {
+			t.Errorf("%+v.Add(%d) = %+v, want %+v", test.SortedList, test.Value, sl, test.Want)
+		}
+	}
+}
+
+func equals(x, y sortedList) bool {
+	if len(x) != len(y) {
+		return false
+	}
+	for i := 0; i < len(x); i++ {
+		if x[i] != y[i] {
+			return false
+		}
+	}
+	return true
+}