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 } func (d *dir) Skip() bool { return false } 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() }