aboutsummaryrefslogtreecommitdiffstats
path: root/utils/merkletrie/internal/fsnoder/dir.go
diff options
context:
space:
mode:
Diffstat (limited to 'utils/merkletrie/internal/fsnoder/dir.go')
-rw-r--r--utils/merkletrie/internal/fsnoder/dir.go140
1 files changed, 140 insertions, 0 deletions
diff --git a/utils/merkletrie/internal/fsnoder/dir.go b/utils/merkletrie/internal/fsnoder/dir.go
new file mode 100644
index 0000000..1811de9
--- /dev/null
+++ b/utils/merkletrie/internal/fsnoder/dir.go
@@ -0,0 +1,140 @@
+package fsnoder
+
+import (
+ "bytes"
+ "fmt"
+ "hash/fnv"
+ "sort"
+ "strings"
+
+ "gopkg.in/src-d/go-git.v4/utils/merkletrie/noder"
+)
+
+// Dir values implement directory-like noders.
+type dir struct {
+ name string // relative
+ children []noder.Noder // sorted by name
+ hash []byte // memoized
+}
+
+type byName []noder.Noder
+
+func (a byName) Len() int { return len(a) }
+func (a byName) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
+func (a byName) Less(i, j int) bool {
+ return strings.Compare(a[i].Name(), a[j].Name()) < 0
+}
+
+// copies the children slice, so nobody can modify the order of its
+// elements from the outside.
+func newDir(name string, children []noder.Noder) (*dir, error) {
+ cloned := make([]noder.Noder, len(children))
+ _ = copy(cloned, children)
+ sort.Sort(byName(cloned))
+
+ if hasChildrenWithNoName(cloned) {
+ return nil, fmt.Errorf("non-root inner nodes cannot have empty names")
+ }
+
+ if hasDuplicatedNames(cloned) {
+ return nil, fmt.Errorf("children cannot have duplicated names")
+ }
+
+ return &dir{
+ name: name,
+ children: cloned,
+ }, nil
+}
+
+func hasChildrenWithNoName(children []noder.Noder) bool {
+ for _, c := range children {
+ if c.Name() == "" {
+ return true
+ }
+ }
+
+ return false
+}
+
+func hasDuplicatedNames(children []noder.Noder) bool {
+ if len(children) < 2 {
+ return false
+ }
+
+ for i := 1; i < len(children); i++ {
+ if children[i].Name() == children[i-1].Name() {
+ return true
+ }
+ }
+
+ return false
+}
+
+func (d *dir) Hash() []byte {
+ if d.hash == nil {
+ d.calculateHash()
+ }
+
+ return d.hash
+}
+
+// hash is calculated as the hash of "dir " plus the concatenation, for
+// each child, of its name, a space and its hash. Children are sorted
+// alphabetically before calculating the hash, so the result is unique.
+func (d *dir) calculateHash() {
+ h := fnv.New64a()
+ h.Write([]byte("dir "))
+ for _, c := range d.children {
+ h.Write([]byte(c.Name()))
+ h.Write([]byte(" "))
+ h.Write(c.Hash())
+ }
+ d.hash = h.Sum([]byte{})
+}
+
+func (d *dir) Name() string {
+ return d.name
+}
+
+func (d *dir) IsDir() bool {
+ return true
+}
+
+// returns a copy so nobody can alter the order of its elements from the
+// outside.
+func (d *dir) Children() ([]noder.Noder, error) {
+ clon := make([]noder.Noder, len(d.children))
+ _ = copy(clon, d.children)
+ return clon, nil
+}
+
+func (d *dir) NumChildren() (int, error) {
+ return len(d.children), nil
+}
+
+const (
+ dirStartMark = '('
+ dirEndMark = ')'
+ dirElementSep = ' '
+)
+
+// The string generated by this method is unique for each tree, as the
+// children of each node are sorted alphabetically by name when
+// generating the string.
+func (d *dir) String() string {
+ var buf bytes.Buffer
+
+ buf.WriteString(d.name)
+ buf.WriteRune(dirStartMark)
+
+ for i, c := range d.children {
+ if i != 0 {
+ buf.WriteRune(dirElementSep)
+ }
+ buf.WriteString(c.String())
+ }
+
+ buf.WriteRune(dirEndMark)
+
+ return buf.String()
+}