ref: c37728bbad8f57288b68559da52ad57abb0141ff
dir: /obj_tree.go/
package furgit
import (
"bytes"
"errors"
"fmt"
"sort"
"strconv"
)
// Tree represents a Git tree object.
type Tree struct {
// Entries represents the entries in the tree.
Entries []TreeEntry
}
// StoredTree represents a tree stored in the object database.
type StoredTree struct {
Tree
hash Hash
}
// Hash returns the hash of the stored tree.
func (sTree *StoredTree) Hash() Hash {
return sTree.hash
}
// FileMode represents the mode of a file in a Git tree.
type FileMode uint32
const (
// FileModeDir represents a directory (tree) in a Git tree.
FileModeDir FileMode = 0o40000
// FileModeRegular represents a regular file (blob) in a Git tree.
FileModeRegular FileMode = 0o100644
// FileModeExecutable represents an executable file (blob) in a Git tree.
FileModeExecutable FileMode = 0o100755
// FileModeSymlink represents a symbolic link (blob) in a Git tree.
FileModeSymlink FileMode = 0o120000
// FileModeGitlink represents a Git link (submodule) in a Git tree.
FileModeGitlink FileMode = 0o160000
)
// TreeEntry represents a single entry in a Git tree.
type TreeEntry struct {
// Mode represents the file mode of the entry.
Mode FileMode
// Name represents the name of the entry.
Name []byte
// ID represents the hash of the entry. This is typically
// either a blob or a tree.
ID Hash
}
// ObjectType returns the object type of the tree.
//
// It always returns ObjectTypeTree.
func (tree *Tree) ObjectType() ObjectType {
_ = tree
return ObjectTypeTree
}
// parseTree decodes a tree body.
func parseTree(id Hash, body []byte, repo *Repository) (*StoredTree, error) {
var entries []TreeEntry
i := 0
for i < len(body) {
space := bytes.IndexByte(body[i:], ' ')
if space < 0 {
return nil, errors.New("furgit: tree: missing mode terminator")
}
modeBytes := body[i : i+space]
i += space + 1
nul := bytes.IndexByte(body[i:], 0)
if nul < 0 {
return nil, errors.New("furgit: tree: missing name terminator")
}
nameBytes := body[i : i+nul]
i += nul + 1
if i+repo.hashAlgo.Size() > len(body) {
return nil, errors.New("furgit: tree: truncated child hash")
}
var child Hash
copy(child.data[:], body[i:i+repo.hashAlgo.Size()])
child.algo = repo.hashAlgo
i += repo.hashAlgo.Size()
mode, err := strconv.ParseUint(string(modeBytes), 8, 32)
if err != nil {
return nil, fmt.Errorf("furgit: tree: parse mode: %w", err)
}
entry := TreeEntry{
Mode: FileMode(mode),
Name: append([]byte(nil), nameBytes...),
ID: child,
}
entries = append(entries, entry)
}
return &StoredTree{
hash: id,
Tree: Tree{
Entries: entries,
},
}, nil
}
// treeBody builds the entry list for a tree without the Git header.
func (tree *Tree) serialize() []byte {
var bodyLen int
for _, e := range tree.Entries {
mode := strconv.FormatUint(uint64(e.Mode), 8)
bodyLen += len(mode) + 1 + len(e.Name) + 1 + e.ID.Size()
}
body := make([]byte, bodyLen)
pos := 0
for _, e := range tree.Entries {
mode := strconv.FormatUint(uint64(e.Mode), 8)
pos += copy(body[pos:], []byte(mode))
body[pos] = ' '
pos++
pos += copy(body[pos:], e.Name)
body[pos] = 0
pos++
size := e.ID.Size()
pos += copy(body[pos:], e.ID.data[:size])
}
return body
}
// Serialize renders the tree into its raw byte representation,
// including the header (i.e., "type size\0").
func (tree *Tree) Serialize() ([]byte, error) {
body := tree.serialize()
header, err := headerForType(ObjectTypeTree, body)
if err != nil {
return nil, err
}
raw := make([]byte, len(header)+len(body))
copy(raw, header)
copy(raw[len(header):], body)
return raw, nil
}
// Entry looks up a tree entry by name.
//
// Lookups are not recursive.
// It returns nil if no such entry exists.
func (tree *Tree) Entry(name []byte) *TreeEntry {
if len(tree.Entries) == 0 {
return nil
}
if e := tree.entry(name, true); e != nil {
return e
}
return tree.entry(name, false)
}
// EntryRecursive looks up a tree entry by path.
//
// Lookups are recursive.
func (sTree *StoredTree) EntryRecursive(repo *Repository, path [][]byte) (*TreeEntry, error) {
if len(path) == 0 {
return nil, errors.New("furgit: tree: empty path")
}
currentTree := sTree
for i, part := range path {
entry := currentTree.Entry(part)
if entry == nil {
return nil, ErrNotFound
}
if i == len(path)-1 {
return entry, nil
}
obj, err := repo.ReadObject(entry.ID)
if err != nil {
return nil, err
}
nextTree, ok := obj.(*StoredTree)
if !ok {
return nil, fmt.Errorf("furgit: tree: expected tree object at %s, got %T", part, obj)
// TODO: It may be useful to check the mode instead of reporting
// an object type error.
}
currentTree = nextTree
}
return nil, ErrNotFound
}
func (tree *Tree) entry(name []byte, searchIsTree bool) *TreeEntry {
low, high := 0, len(tree.Entries)-1
for low <= high {
mid := low + (high-low)/2
entry := &tree.Entries[mid]
cmp := TreeEntryNameCompare(entry.Name, entry.Mode, name, searchIsTree)
if cmp == 0 {
if bytes.Equal(entry.Name, name) {
return entry
}
return nil
}
if cmp < 0 {
low = mid + 1
} else {
high = mid - 1
}
}
return nil
}
// InsertEntry inserts a tree entry while preserving Git's name ordering.
// It returns an error if an entry with the same name already exists.
func (tree *Tree) InsertEntry(newEntry TreeEntry) error {
if tree == nil {
return ErrInvalidObject
}
for _, entry := range tree.Entries {
if bytes.Equal(entry.Name, newEntry.Name) {
return fmt.Errorf("furgit: tree: entry %q already exists", newEntry.Name)
}
}
newIsTree := newEntry.Mode == FileModeDir
insertAt := sort.Search(len(tree.Entries), func(i int) bool {
return TreeEntryNameCompare(tree.Entries[i].Name, tree.Entries[i].Mode, newEntry.Name, newIsTree) >= 0
})
tree.Entries = append(tree.Entries, TreeEntry{})
copy(tree.Entries[insertAt+1:], tree.Entries[insertAt:])
tree.Entries[insertAt] = newEntry
return nil
}
// RemoveEntry removes a tree entry by name.
// It returns ErrNotFound if no matching entry exists.
func (tree *Tree) RemoveEntry(name []byte) error {
if tree == nil {
return ErrInvalidObject
}
if len(tree.Entries) == 0 {
return ErrNotFound
}
for i := range tree.Entries {
if bytes.Equal(tree.Entries[i].Name, name) {
copy(tree.Entries[i:], tree.Entries[i+1:])
tree.Entries = tree.Entries[:len(tree.Entries)-1]
return nil
}
}
return ErrNotFound
}
// TreeEntryNameCompare compares names using Git's tree ordering rules.
func TreeEntryNameCompare(entryName []byte, entryMode FileMode, searchName []byte, searchIsTree bool) int {
isEntryTree := entryMode == FileModeDir
entryLen := len(entryName)
if isEntryTree {
entryLen++
}
searchLen := len(searchName)
if searchIsTree {
searchLen++
}
n := entryLen
if searchLen < n {
n = searchLen
}
for i := 0; i < n; i++ {
var ec, sc byte
if i < len(entryName) {
ec = entryName[i]
} else {
ec = '/'
}
if i < len(searchName) {
sc = searchName[i]
} else {
sc = '/'
}
if ec < sc {
return -1
}
if ec > sc {
return 1
}
}
if entryLen < searchLen {
return -1
}
if entryLen > searchLen {
return 1
}
return 0
}