runxiyu.tngl.sh
Fast implementation of Git in pure Go
1package object
2
3import (
4 "bytes"
5 "fmt"
6 "sort"
7
8 "codeberg.org/lindenii/furgit/objectid"
9 "codeberg.org/lindenii/furgit/objecttype"
10)
11
12// FileMode represents the mode of a file in a Git tree.
13type FileMode uint32
14
15const (
16 FileModeDir FileMode = 0o40000
17 FileModeRegular FileMode = 0o100644
18 FileModeExecutable FileMode = 0o100755
19 FileModeSymlink FileMode = 0o120000
20 FileModeGitlink FileMode = 0o160000
21)
22
23// TreeEntry represents a single entry in a tree.
24type TreeEntry struct {
25 Mode FileMode
26 Name []byte
27 ID objectid.ObjectID
28}
29
30// Tree represents a Git tree object.
31type Tree struct {
32 Entries []TreeEntry
33}
34
35// ObjectType returns TypeTree.
36func (tree *Tree) ObjectType() objecttype.Type {
37 _ = tree
38
39 return objecttype.TypeTree
40}
41
42// Entry looks up a tree entry by name.
43func (tree *Tree) Entry(name []byte) *TreeEntry {
44 if len(tree.Entries) == 0 {
45 return nil
46 }
47
48 if e := tree.entry(name, true); e != nil {
49 return e
50 }
51
52 return tree.entry(name, false)
53}
54
55// InsertEntry inserts a tree entry while preserving Git ordering.
56func (tree *Tree) InsertEntry(newEntry TreeEntry) error {
57 if tree.entry(newEntry.Name, true) != nil || tree.entry(newEntry.Name, false) != nil {
58 return fmt.Errorf("object: tree: entry %q already exists", newEntry.Name)
59 }
60
61 newIsTree := newEntry.Mode == FileModeDir
62 insertAt := sort.Search(len(tree.Entries), func(i int) bool {
63 return TreeEntryNameCompare(tree.Entries[i].Name, tree.Entries[i].Mode, newEntry.Name, newIsTree) >= 0
64 })
65 tree.Entries = append(tree.Entries, TreeEntry{})
66 copy(tree.Entries[insertAt+1:], tree.Entries[insertAt:])
67 tree.Entries[insertAt] = newEntry
68
69 return nil
70}
71
72// RemoveEntry removes a tree entry by name.
73func (tree *Tree) RemoveEntry(name []byte) error {
74 if len(tree.Entries) == 0 {
75 return fmt.Errorf("object: tree: entry %q not found", name)
76 }
77
78 for i := range tree.Entries {
79 if bytes.Equal(tree.Entries[i].Name, name) {
80 copy(tree.Entries[i:], tree.Entries[i+1:])
81 tree.Entries = tree.Entries[:len(tree.Entries)-1]
82
83 return nil
84 }
85 }
86
87 return fmt.Errorf("object: tree: entry %q not found", name)
88}
89
90func (tree *Tree) entry(name []byte, searchIsTree bool) *TreeEntry {
91 low, high := 0, len(tree.Entries)-1
92 for low <= high {
93 mid := low + (high-low)/2
94 entry := &tree.Entries[mid]
95
96 cmp := TreeEntryNameCompare(entry.Name, entry.Mode, name, searchIsTree)
97 if cmp == 0 {
98 if bytes.Equal(entry.Name, name) {
99 return entry
100 }
101
102 return nil
103 }
104
105 if cmp < 0 {
106 low = mid + 1
107 } else {
108 high = mid - 1
109 }
110 }
111
112 return nil
113}
114
115// TreeEntryNameCompare compares names using Git tree ordering rules.
116func TreeEntryNameCompare(entryName []byte, entryMode FileMode, searchName []byte, searchIsTree bool) int {
117 isEntryTree := entryMode == FileModeDir
118
119 entryLen := len(entryName)
120 if isEntryTree {
121 entryLen++
122 }
123
124 searchLen := len(searchName)
125 if searchIsTree {
126 searchLen++
127 }
128
129 n := min(searchLen, entryLen)
130
131 for i := range n {
132 var ec, sc byte
133 if i < len(entryName) {
134 ec = entryName[i]
135 } else {
136 ec = '/'
137 }
138
139 if i < len(searchName) {
140 sc = searchName[i]
141 } else {
142 sc = '/'
143 }
144
145 if ec < sc {
146 return -1
147 }
148
149 if ec > sc {
150 return 1
151 }
152 }
153
154 if entryLen < searchLen {
155 return -1
156 }
157
158 if entryLen > searchLen {
159 return 1
160 }
161
162 return 0
163}