Repository: celestiaorg/nmt
Pull request #107 (2023-02-17 19:56:24)

chore: add golangci-lint config
While working on a different PR, my editor complained about failed go-staticcheck warnings. For consistency across codebases, I adopted the celestia-app golangci-lint config and fixed the lint errors in the screenshot below. This repo already has a lint workflow that runs [golangci-lint](https://golangci-lint.run/) so CI will run with these linters moving forward (confirmed via verbose logging [here](https://github.com/celestiaorg/nmt/actions/runs/4207167400/jobs/7301618009#step:4:33)).

## Screenshot

<img width="1441" alt="Screenshot 2023-02-17 at 2 48 43 PM" src="https://user-images.githubusercontent.com/3699047/219778350-ebaac63e-c7e9-407e-8f73-7ca1f3d77786.png">

codecov[bot]: # [Codecov](https://codecov.io/gh/celestiaorg/nmt/pull/107?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=celestiaorg) Report
> Merging [#107](https://codecov.io/gh/celestiaorg/nmt/pull/107?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=celestiaorg) (542bc79) into [master](https://codecov.io/gh/celestiaorg/nmt/commit/fa98a59cbf582b3a0880ba0222a49e3bf5032f6d?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=celestiaorg) (fa98a59) will **decrease** coverage by `0.02%`.
> The diff coverage is `100.00%`.

```diff
@@            Coverage Diff             @@
##           master     #107      +/-   ##
==========================================
- Coverage   96.21%   96.19%   -0.02%     
==========================================
  Files           6        6              
  Lines         423      421       -2     
==========================================
- Hits          407      405       -2     
  Misses         10       10              
  Partials        6        6              
```


| [Impacted Files](https://codecov.io/gh/celestiaorg/nmt/pull/107?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=celestiaorg) | Coverage Δ | |
|---|---|---|
| [proof.go](https://codecov.io/gh/celestiaorg/nmt/pull/107?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=celestiaorg#diff-cHJvb2YuZ28=) | `96.73% <ø> (-0.04%)` | :arrow_down: |
| [subrootpaths.go](https://codecov.io/gh/celestiaorg/nmt/pull/107?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=celestiaorg#diff-c3Vicm9vdHBhdGhzLmdv) | `90.47% <100.00%> (-0.12%)` | :arrow_down: |

Help us with your feedback. Take ten seconds to tell us [how you rate us](https://about.codecov.io/nps?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=celestiaorg). Have a feature suggestion? [Share it here.](https://app.codecov.io/gh/feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=celestiaorg)


Patch:
diff --git a/.github/workflows/lint.yml b/.github/workflows/lint.yml
index c35ffcc..7293956 100644
--- a/.github/workflows/lint.yml
+++ b/.github/workflows/lint.yml
@@ -24,4 +24,4 @@ jobs:
         with:
           version: latest
           args: --timeout 10m
-        if: env.GIT_DIFF
\ No newline at end of file
+        if: env.GIT_DIFF
diff --git a/.golangci.yml b/.golangci.yml
new file mode 100644
index 0000000..5ea7614
--- /dev/null
+++ b/.golangci.yml
@@ -0,0 +1,11 @@
+run:
+  timeout: 5m
+  modules-download-mode: readonly
+
+linters:
+  enable:
+    - exportloopref
+    - gofumpt
+    - misspell
+    - revive
+    - prealloc
diff --git a/nmt.go b/nmt.go
index 2a4f8c1..830aeb0 100644
--- a/nmt.go
+++ b/nmt.go
@@ -414,6 +414,16 @@ func (n *NamespacedMerkleTree) Root() []byte {
 	return n.rawRoot
 }
 
+// MinNamespace returns the minimum namespace ID in this Namespaced Merkle Tree.
+func (n *NamespacedMerkleTree) MinNamespace() namespace.ID {
+	return MinNamespace(n.Root(), n.NamespaceSize())
+}
+
+// MaxNamespace returns the maximum namespace ID in this Namespaced Merkle Tree.
+func (n *NamespacedMerkleTree) MaxNamespace() namespace.ID {
+	return MaxNamespace(n.Root(), n.NamespaceSize())
+}
+
 // computeRoot calculates the namespace Merkle root for a tree/sub-tree that
 // encompasses the leaves within the range of [start, end).
 func (n *NamespacedMerkleTree) computeRoot(start, end int) []byte {
diff --git a/proof.go b/proof.go
index a50c0e3..660ae1f 100644
--- a/proof.go
+++ b/proof.go
@@ -120,8 +120,7 @@ func NewAbsenceProof(proofStart, proofEnd int, proofNodes [][]byte, leafHash []b
 //	`end-1` of the tree.
 //
 // `root` is the root of the NMT against which the `proof` is verified.
-func (proof Proof) VerifyNamespace(
-	h hash.Hash, nID namespace.ID, data [][]byte, root []byte) bool {
+func (proof Proof) VerifyNamespace(h hash.Hash, nID namespace.ID, data [][]byte, root []byte) bool {
 	nth := NewNmtHasher(h, nID.Size(), proof.isMaxNamespaceIDIgnored)
 	min := namespace.ID(MinNamespace(root, nID.Size()))
 	max := namespace.ID(MaxNamespace(root, nID.Size()))
diff --git a/subrootpaths.go b/subrootpaths.go
index febeda6..4494f80 100644
--- a/subrootpaths.go
+++ b/subrootpaths.go
@@ -6,10 +6,10 @@ import (
 )
 
 var (
-	srpNotPowerOf2       = errors.New("GetSubrootPaths: Supplied square size is not a power of 2")
-	srpInvalidShareCount = errors.New("GetSubrootPaths: Can't compute path for 0 share count slice")
-	srpPastSquareSize    = errors.New("GetSubrootPaths: Share slice can't be past the square size")
-	srpInvalidIdxEnd     = errors.New("GetSubrootPaths: idxEnd must be larger than idxStart and shareCount")
+	errNotPowerOf2       = errors.New("GetSubrootPaths: Supplied square size is not a power of 2")
+	errInvalidShareCount = errors.New("GetSubrootPaths: Can't compute path for 0 share count slice")
+	errPastSquareSize    = errors.New("GetSubrootPaths: Share slice can't be past the square size")
+	errInvalidIdxEnd     = errors.New("GetSubrootPaths: idxEnd must be larger than idxStart and shareCount")
 )
 
 // merkle path to a node is equivalent to the index's binary representation
@@ -51,9 +51,8 @@ func prune(idxStart uint, idxEnd uint, maxWidth uint) [][]int {
 	if idxStart+1 >= idxEnd {
 		if idxStart%2 == 1 {
 			return [][]int{pathStart, pathEnd}
-		} else {
-			return [][]int{pathStart[:len(pathStart)-1]}
 		}
+		return [][]int{pathStart[:len(pathStart)-1]}
 	}
 
 	var prunedPaths [][]int
@@ -127,24 +126,24 @@ func GetSubrootPaths(squareSize uint, idxStart uint, shareCount uint) ([][][]int
 	// check squareSize is at least 2 and that it's
 	// a power of 2 by checking that only 1 bit is on
 	if squareSize < 2 || bits.OnesCount(squareSize) != 1 {
-		return nil, srpNotPowerOf2
+		return nil, errNotPowerOf2
 	}
 
 	// no path exists for 0 count slice
 	if shareCount == 0 {
-		return nil, srpInvalidShareCount
+		return nil, errInvalidShareCount
 	}
 
 	idxEnd := idxStart + shareCount
 	if idxEnd < idxStart || idxEnd < shareCount {
-		return nil, srpInvalidIdxEnd
+		return nil, errInvalidIdxEnd
 	}
 
 	shares := squareSize * squareSize
 
 	// sanity checking
 	if idxStart >= shares || idxEnd > shares {
-		return nil, srpPastSquareSize
+		return nil, errPastSquareSize
 	}
 
 	startRow := idxStart / squareSize


Test patch:
diff --git a/hasher_test.go b/hasher_test.go
index e7c7325..1574068 100644
--- a/hasher_test.go
+++ b/hasher_test.go
@@ -3,7 +3,6 @@ package nmt
 import (
 	"crypto"
 	"crypto/sha256"
-	_ "crypto/sha256"
 	"reflect"
 	"testing"
 
diff --git a/nmt_test.go b/nmt_test.go
index eeabe4b..8541351 100644
--- a/nmt_test.go
+++ b/nmt_test.go
@@ -14,6 +14,7 @@ import (
 	"testing"
 
 	"github.com/celestiaorg/nmt/namespace"
+	"github.com/stretchr/testify/assert"
 )
 
 type namespaceDataPair struct {
@@ -618,7 +619,8 @@ func TestNMT_forgedNamespaceEmptinessProof(t *testing.T) {
 		append(namespace.ID{1}, []byte("leaf_0")...),
 		append(namespace.ID{1}, []byte("leaf_1")...),
 		append(namespace.ID{2}, []byte("leaf_2")...),
-		append(namespace.ID{2}, []byte("leaf_3")...)}
+		append(namespace.ID{2}, []byte("leaf_3")...),
+	}
 	// Init a tree with the namespace size as well as
 	// the underlying hash function:
 	tree := New(sha256.New(), NamespaceIDSize(1))
@@ -773,3 +775,73 @@ func generateRandNamespacedRawData(total int, nidSize int, leafSize int) [][]byt
 func sortByteArrays(src [][]byte) {
 	sort.Slice(src, func(i, j int) bool { return bytes.Compare(src[i], src[j]) < 0 })
 }
+
+func TestMinMaxNamespace(t *testing.T) {
+	type testCase struct {
+		name    string
+		tree    *NamespacedMerkleTree
+		wantMin namespace.ID
+		wantMax namespace.ID
+	}
+	testCases := []testCase{
+		{
+			name:    "example tree with four leaves",
+			tree:    exampleTreeWithFourLeaves(),
+			wantMin: namespace.ID{0},
+			wantMax: namespace.ID{3},
+		},
+		{
+			name:    "example tree with eight leaves",
+			tree:    exampleTreeWithEightLeaves(),
+			wantMin: namespace.ID{1, 1},
+			wantMax: namespace.ID{8, 8},
+		},
+	}
+
+	for _, tc := range testCases {
+		t.Run(tc.name, func(t *testing.T) {
+			assert.Equal(t, tc.wantMin, tc.tree.MinNamespace())
+			assert.Equal(t, tc.wantMax, tc.tree.MaxNamespace())
+		})
+	}
+}
+
+func exampleTreeWithFourLeaves() *NamespacedMerkleTree {
+	nidSize := 1
+	data := [][]byte{
+		append(namespace.ID{0}, []byte("leaf_0")...),
+		append(namespace.ID{0}, []byte("leaf_1")...),
+		append(namespace.ID{1}, []byte("leaf_2")...),
+		append(namespace.ID{3}, []byte("leaf_3")...),
+	}
+
+	tree := New(sha256.New(), NamespaceIDSize(nidSize))
+	for _, d := range data {
+		if err := tree.Push(d); err != nil {
+			panic(fmt.Sprintf("unexpected error: %v", err))
+		}
+	}
+	return tree
+}
+
+func exampleTreeWithEightLeaves() *NamespacedMerkleTree {
+	nidSize := 2
+	data := [][]byte{
+		append(namespace.ID{1, 1}, []byte("leaf_0")...),
+		append(namespace.ID{2, 2}, []byte("leaf_1")...),
+		append(namespace.ID{3, 3}, []byte("leaf_2")...),
+		append(namespace.ID{4, 4}, []byte("leaf_3")...),
+		append(namespace.ID{5, 5}, []byte("leaf_4")...),
+		append(namespace.ID{6, 6}, []byte("leaf_5")...),
+		append(namespace.ID{7, 7}, []byte("leaf_6")...),
+		append(namespace.ID{8, 8}, []byte("leaf_7")...),
+	}
+
+	tree := New(sha256.New(), NamespaceIDSize(nidSize))
+	for _, d := range data {
+		if err := tree.Push(d); err != nil {
+			panic(fmt.Sprintf("unexpected error: %v", err))
+		}
+	}
+	return tree
+}
diff --git a/subrootpaths_test.go b/subrootpaths_test.go
index e5b1964..d2d2b67 100644
--- a/subrootpaths_test.go
+++ b/subrootpaths_test.go
@@ -20,12 +20,12 @@ func TestArgValidation(t *testing.T) {
 	}
 
 	tests := []test{
-		{input: pathSpan{squareSize: 0, startNode: 0, length: 0}, want: srpNotPowerOf2},
-		{input: pathSpan{squareSize: 1, startNode: 0, length: 1}, want: srpNotPowerOf2},
-		{input: pathSpan{squareSize: 20, startNode: 0, length: 1}, want: srpNotPowerOf2},
-		{input: pathSpan{squareSize: 4, startNode: 0, length: 17}, want: srpPastSquareSize},
-		{input: pathSpan{squareSize: 4, startNode: 0, length: 0}, want: srpInvalidShareCount},
-		{input: pathSpan{squareSize: 128, startNode: 1, length: 18446744073709551615}, want: srpInvalidIdxEnd},
+		{input: pathSpan{squareSize: 0, startNode: 0, length: 0}, want: errNotPowerOf2},
+		{input: pathSpan{squareSize: 1, startNode: 0, length: 1}, want: errNotPowerOf2},
+		{input: pathSpan{squareSize: 20, startNode: 0, length: 1}, want: errNotPowerOf2},
+		{input: pathSpan{squareSize: 4, startNode: 0, length: 17}, want: errPastSquareSize},
+		{input: pathSpan{squareSize: 4, startNode: 0, length: 0}, want: errInvalidShareCount},
+		{input: pathSpan{squareSize: 128, startNode: 1, length: 18446744073709551615}, want: errInvalidIdxEnd},
 	}
 
 	for _, tc := range tests {