1// SPDX-License-Identifier: MIT
2
3package git
4
5import (
6 "bytes"
7 "errors"
8 "fmt"
9 "strings"
10)
11
12// This file holds the tree comparison used by history walks with a path: a
13// cheap TREESAME test for one path, done by comparing the entry ids
14// component by component. Only the trees on the way to the path are read,
15// and only while the ids differ, so a commit that did not touch the path
16// usually costs the two root trees at most, and nothing when the root trees
17// are identical. Lookups are memoised per (tree, depth), which makes a walk
18// along a chain read each tree once instead of twice.
19
20// ErrInvalidPath reports a path that cannot designate anything in a
21// repository: an absolute path or one that leaves the root with "..".
22var ErrInvalidPath = errors.New("git: invalid path")
23
24// emptyTreeID is the id of the empty tree, which Git knows without storing it.
25var emptyTreeID = ObjectID{
26 0x4b, 0x82, 0x5d, 0xc6, 0x42, 0xcb, 0x6e, 0xb9, 0xa0, 0x60,
27 0xe5, 0x4b, 0xf8, 0xd6, 0x92, 0x88, 0xfb, 0xee, 0x49, 0x04,
28}
29
30// pathSpec is a literal path, normalised as Git does for a pathspec.
31type pathSpec struct {
32 comps []string // no empty, "." or ".." component; none means the root
33 // bloom reports that the path is exactly what Git inserted in the
34 // filters: spelled without a "." or ".." component, an empty one, or
35 // more than one trailing slash. Otherwise the trees are compared.
36 bloom bool
37 // dirOnly is set by a trailing slash: the last component then matches
38 // a directory or a submodule, never a file ("f/" finds nothing when f
39 // is a file).
40 dirOnly bool
41}
42
43// parsePathSpec normalises p: empty and "." components are dropped, ".."
44// removes the previous one, and one trailing slash is ignored. Absolute
45// paths and paths that climb above the root are ErrInvalidPath.
46func parsePathSpec(p string) (pathSpec, error) {
47 if strings.IndexByte(p, 0) >= 0 {
48 return pathSpec{}, fmt.Errorf("%w: NUL byte", ErrInvalidPath)
49 }
50 if strings.HasPrefix(p, "/") {
51 return pathSpec{}, fmt.Errorf("%w: %q is absolute", ErrInvalidPath, p)
52 }
53 s := pathSpec{bloom: true, dirOnly: strings.HasSuffix(p, "/")}
54 t := strings.TrimSuffix(p, "/")
55 if t == "" {
56 s.bloom = false // the root: every commit with a changed tree
57 return s, nil
58 }
59 for _, c := range strings.Split(t, "/") {
60 switch c {
61 case "", ".":
62 s.bloom = false
63 case "..":
64 s.bloom = false
65 if len(s.comps) == 0 {
66 return pathSpec{}, fmt.Errorf("%w: %q is outside the repository", ErrInvalidPath, p)
67 }
68 s.comps = s.comps[:len(s.comps)-1]
69 default:
70 s.comps = append(s.comps, c)
71 }
72 }
73 if len(s.comps) == 0 {
74 s.bloom = false
75 }
76 return s, nil
77}
78
79// String returns the normalised path ("" for the root).
80func (s pathSpec) String() string { return strings.Join(s.comps, "/") }
81
82// pathEntry is what a tree holds at a path.
83type pathEntry struct {
84 id ObjectID
85 mode Mode
86 found bool
87}
88
89type lookupKey struct {
90 tree ObjectID
91 level uint16
92}
93
94// lookupSlots is the size of the direct-mapped cache of lookups. A walk
95// along a chain asks again for the trees it has just read, so a small table
96// is enough, and it never allocates after it is created.
97const lookupSlots = 256
98
99type lookupSlot struct {
100 key lookupKey
101 e pathEntry
102 ok bool
103}
104
105// pathDiffer answers TREESAME questions for one path. It is not safe for
106// concurrent use.
107type pathDiffer struct {
108 r *Repo
109 comps []string
110 dirOnly bool
111 names [][]byte
112 cache []lookupSlot // allocated on first use
113 buf []byte
114}
115
116func newPathDiffer(r *Repo, spec pathSpec) *pathDiffer {
117 comps := spec.comps
118 d := &pathDiffer{r: r, comps: comps, dirOnly: spec.dirOnly}
119 d.names = make([][]byte, len(comps))
120 for i, c := range comps {
121 d.names[i] = []byte(c)
122 }
123 return d
124}
125
126// lookup finds the entry named comps[level] in tree.
127func (d *pathDiffer) lookup(tree ObjectID, level int) (pathEntry, error) {
128 if tree == emptyTreeID {
129 return pathEntry{}, nil
130 }
131 k := lookupKey{tree, uint16(level)}
132 if d.cache == nil {
133 d.cache = make([]lookupSlot, lookupSlots)
134 }
135 slot := &d.cache[(uint(tree[0])|uint(tree[1])<<8+uint(level))%lookupSlots]
136 if slot.ok && slot.key == k {
137 return slot.e, nil
138 }
139 typ, data, err := d.r.ReadObject(tree, d.buf)
140 if err != nil {
141 return pathEntry{}, err
142 }
143 d.buf = data
144 if typ != TypeTree {
145 return pathEntry{}, wrongType(tree, typ, TypeTree)
146 }
147 e, err := findEntry(data, d.names[level])
148 if err != nil {
149 return pathEntry{}, wrapObj(tree, err)
150 }
151 *slot = lookupSlot{key: k, e: e, ok: true}
152 return e, nil
153}
154
155// findEntry scans a tree for name. It validates the entries it walks over
156// like ParseTree and does not allocate.
157func findEntry(data, name []byte) (pathEntry, error) {
158 for len(data) > 0 {
159 sp := bytes.IndexByte(data, ' ')
160 if sp <= 0 || sp > 7 {
161 return pathEntry{}, corrupt("tree: bad mode")
162 }
163 var mode uint32
164 for _, c := range data[:sp] {
165 if c < '0' || c > '7' {
166 return pathEntry{}, corrupt("tree: bad mode")
167 }
168 mode = mode<<3 | uint32(c-'0')
169 }
170 data = data[sp+1:]
171 nul := bytes.IndexByte(data, 0)
172 if nul <= 0 || len(data)-nul-1 < 20 {
173 return pathEntry{}, corrupt("tree: truncated entry")
174 }
175 if bytes.Equal(data[:nul], name) {
176 e := pathEntry{mode: Mode(mode), found: true}
177 copy(e.id[:], data[nul+1:nul+21])
178 return e, nil
179 }
180 data = data[nul+21:]
181 }
182 return pathEntry{}, nil
183}
184
185// final applies the trailing-slash rule to the entry found at the full path.
186func (d *pathDiffer) final(e pathEntry) pathEntry {
187 if d.dirOnly && e.found && !e.mode.IsTree() && !e.mode.IsGitlink() {
188 return pathEntry{}
189 }
190 return e
191}
192
193// resolve returns the entry at the path below the root tree. The root path
194// (no component) resolves to the tree itself.
195func (d *pathDiffer) resolve(root ObjectID) (pathEntry, error) {
196 cur := pathEntry{id: root, mode: ModeTree, found: true}
197 for i := range d.comps {
198 if !cur.mode.IsTree() {
199 return pathEntry{}, nil
200 }
201 e, err := d.lookup(cur.id, i)
202 if err != nil || !e.found {
203 return pathEntry{}, err
204 }
205 cur = e
206 }
207 return d.final(cur), nil
208}
209
210// child returns what the directory entry e holds at comps[level]: absent when
211// e is absent or not a directory.
212func (d *pathDiffer) child(e pathEntry, level int) (pathEntry, error) {
213 if !e.found || !e.mode.IsTree() {
214 return pathEntry{}, nil
215 }
216 return d.lookup(e.id, level)
217}
218
219// same reports whether the path is identical in the root trees a and b: both
220// absent, or the same id and mode. The comparison stops at the first level
221// where the entries are equal.
222func (d *pathDiffer) same(a, b ObjectID) (bool, error) {
223 ea := pathEntry{id: a, mode: ModeTree, found: true}
224 eb := pathEntry{id: b, mode: ModeTree, found: true}
225 for i := 0; ; i++ {
226 if i == len(d.comps) {
227 return d.final(ea) == d.final(eb), nil
228 }
229 if ea == eb {
230 return true, nil
231 }
232 var err error
233 if ea, err = d.child(ea, i); err != nil {
234 return false, err
235 }
236 if eb, err = d.child(eb, i); err != nil {
237 return false, err
238 }
239 }
240}
241
242// exists reports whether the path exists in the root tree, that is whether a
243// root commit changes it.
244func (d *pathDiffer) exists(root ObjectID) (bool, error) {
245 if len(d.comps) == 0 {
246 return root != emptyTreeID, nil
247 }
248 e, err := d.resolve(root)
249 return e.found, err
250}