1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
|
package fsnoder
import (
"bytes"
"fmt"
"hash/fnv"
"sort"
"strings"
"github.com/go-git/go-git/v5/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()
}
|
