-
Notifications
You must be signed in to change notification settings - Fork 132
/
path_resolver.go
337 lines (292 loc) · 8.76 KB
/
path_resolver.go
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
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
package sizes
import (
"encoding/json"
"fmt"
"sync"
"github.com/github/git-sizer/git"
)
// PathResolver figures out a "reachability path" (i.e., Git
// `rev-parse` input, including commit and/or file path) by which
// specified objects are reachable. It is used as follows:
//
// * Request an object's path using `RequestPath()`. The returned
// `Path` object is a placeholder for the object's path.
//
// * Tell the `PathResolver` about objects that might be along the
// object's reachability path, *in depth-first* order (i.e.,
// referents before referers) by calling `RecordTree()`,
// `RecordCommit()`, `RecordTag()`, and `RecordReference()`,.
//
// * Read the path out of the `Path` object using `Path.Path()`.
//
// Multiple objects can be processed at once.
//
// It is important that interested is registered in an object's path
// via `RequestPath()` *before* any of the objects along its
// reachability path are recorded.
//
// If a caller decides that it is not interested in a path after all,
// it can call `ForgetPath()`. This might free up some resources that
// would otherwise continue consuming memory.
type PathResolver interface {
RequestPath(oid git.OID, objectType string) *Path
ForgetPath(p *Path)
RecordReference(ref git.Reference)
RecordTreeEntry(oid git.OID, name string, childOID git.OID)
RecordCommit(oid, tree git.OID)
RecordTag(oid git.OID, tag *git.Tag)
}
type NullPathResolver struct {
useHash bool
}
func (n NullPathResolver) RequestPath(oid git.OID, objectType string) *Path {
// The caller is the only one retaining a reference to this
// object. When it loses interest, the object will be GCed,
// without our having to do anything to manage its lifetime.
if n.useHash {
return &Path{
OID: oid,
objectType: objectType,
}
} else {
return nil
}
}
func (_ NullPathResolver) ForgetPath(p *Path) {}
func (_ NullPathResolver) RecordReference(ref git.Reference) {}
func (_ NullPathResolver) RecordTreeEntry(oid git.OID, name string, childOID git.OID) {}
func (_ NullPathResolver) RecordCommit(oid, tree git.OID) {}
func (_ NullPathResolver) RecordTag(oid git.OID, tag *git.Tag) {}
type InOrderPathResolver struct {
lock sync.Mutex
soughtPaths map[git.OID]*Path
}
// Structure for keeping track of an object whose path we want to know
// (e.g., the biggest blob, or a tree containing the biggest blob, or
// a commit whose tree contains the biggest blob). Valid states:
//
// * `parent == nil && relativePath == ""`—we have not yet found
// anything that refers to this object.
//
// * `parent != nil && relativePath == ""`—this object is a tree, and
// we have found a commit that refers to it.
//
// * `parent == nil && relativePath != ""`—we have found a reference
// that points directly at this object; `relativePath` is the full
// name of the reference.
//
// * `parent != nil && relativePath != ""`—this object is a blob or
// tree, and we have found another tree that refers to it;
// `relativePath` is the corresponding tree entry name.
type Path struct {
// The OID of the object whose path we seek. This member is always
// set.
git.OID
// The type of the object whose path we seek. This member is
// always set.
objectType string
// The number of seekers that want this object's path, including 1
// for the caller of `RequestPath()` (i.e., it is initialized to
// 1). If this value goes to zero, we can remove the object from
// the PathResolver.
seekerCount uint8
// A path we found of a parent from which this object is
// referenced. This is set when we find a parent then never
// changed again. It is never set if the "parent" we find is a
// reference.
parent *Path
// The relative path from the parent's path to this object; i.e.,
// what has to be appended to the parent path to create the path
// to this object.
relativePath string
}
// Return the path of this object under the assumption that another
// path component will be appended to it.
func (p *Path) TreePrefix() string {
switch p.objectType {
case "blob", "tree":
if p.parent != nil {
if p.relativePath == "" {
// This is a top-level tree or blob.
return p.parent.TreePrefix()
} else {
// The parent is also a tree.
return p.parent.TreePrefix() + p.relativePath + "/"
}
} else {
return "???"
}
case "commit", "tag":
switch {
case p.parent != nil:
// The parent is a tag.
return fmt.Sprintf("%s^{%s}", p.parent.BestPath(), p.objectType)
case p.relativePath != "":
return p.relativePath + ":"
default:
return p.OID.String() + ":"
}
default:
return "???"
}
}
// Return a human-readable path for this object if we can do better
// than its OID; otherwise, return "".
func (p *Path) Path() string {
switch p.objectType {
case "blob", "tree":
if p.parent != nil {
if p.relativePath == "" {
// This is a top-level tree or blob.
return fmt.Sprintf("%s^{%s}", p.parent.BestPath(), p.objectType)
} else {
// The parent is also a tree.
return p.parent.TreePrefix() + p.relativePath
}
} else {
return ""
}
case "commit", "tag":
switch {
case p.parent != nil:
// The parent is a tag.
return fmt.Sprintf("%s^{%s}", p.parent.BestPath(), p.objectType)
case p.relativePath != "":
return p.relativePath
default:
return ""
}
default:
return ""
}
}
// Return some human-readable path for this object, even if it's just
// the OID.
func (p *Path) BestPath() string {
path := p.Path()
if path != "" {
return path
}
return p.OID.String()
}
func (p *Path) String() string {
path := p.Path()
if path == "" {
return p.OID.String()
} else {
return fmt.Sprintf("%s (%s)", p.OID, path)
}
}
func (p *Path) MarshalJSON() ([]byte, error) {
return json.Marshal(p.String())
}
func NewPathResolver(nameStyle NameStyle) PathResolver {
switch nameStyle {
case NameStyleNone:
return NullPathResolver{false}
case NameStyleHash:
return NullPathResolver{true}
case NameStyleFull:
return &InOrderPathResolver{
soughtPaths: make(map[git.OID]*Path),
}
default:
panic("Unexpected NameStyle value")
}
}
// Request that a path to the object named `oid` be computed.
func (pr *InOrderPathResolver) RequestPath(oid git.OID, objectType string) *Path {
pr.lock.Lock()
defer pr.lock.Unlock()
return pr.requestPathLocked(oid, objectType)
}
// Request that a path to the object named `oid` be computed.
func (pr *InOrderPathResolver) requestPathLocked(oid git.OID, objectType string) *Path {
p, ok := pr.soughtPaths[oid]
if ok {
p.seekerCount++
return p
}
p = &Path{
OID: oid,
objectType: objectType,
seekerCount: 1,
}
pr.soughtPaths[oid] = p
return p
}
// Record that the specified path is wanted by one less seeker. If its
// seeker count goes to zero, remove it from `pr.soughtPaths`.
func (pr *InOrderPathResolver) ForgetPath(p *Path) {
pr.lock.Lock()
defer pr.lock.Unlock()
pr.forgetPathLocked(p)
}
func (pr *InOrderPathResolver) forgetPathLocked(p *Path) {
if p.seekerCount == 0 {
panic("forgetPathLocked() called when refcount zero")
}
p.seekerCount--
if p.seekerCount > 0 {
// The path is still wanted (by another seeker).
return
}
if p.parent != nil {
// We already found the object's parent, and the parent's path
// is wanted on account if this object. Decrement its
// seekerCount.
pr.forgetPathLocked(p.parent)
} else if p.relativePath == "" {
// We were still looking for this object's parent. Stop doing
// so.
delete(pr.soughtPaths, p.OID)
}
}
func (pr *InOrderPathResolver) RecordReference(ref git.Reference) {
pr.lock.Lock()
defer pr.lock.Unlock()
p, ok := pr.soughtPaths[ref.OID]
if !ok {
// Nobody is looking for the path to the referent.
return
}
p.relativePath = ref.Refname
delete(pr.soughtPaths, ref.OID)
}
// Record that the tree with OID `oid` has an entry with the specified
// `name` and `childOID`.
func (pr *InOrderPathResolver) RecordTreeEntry(oid git.OID, name string, childOID git.OID) {
pr.lock.Lock()
defer pr.lock.Unlock()
p, ok := pr.soughtPaths[childOID]
if !ok {
// Nobody is looking for the path to the child.
return
}
if p.parent != nil {
panic("tree path parent unexpectedly filled in")
}
p.parent = pr.requestPathLocked(oid, "tree")
p.relativePath = name
// We don't need to keep looking for the child anymore:
delete(pr.soughtPaths, childOID)
}
func (pr *InOrderPathResolver) RecordCommit(oid, tree git.OID) {
pr.lock.Lock()
defer pr.lock.Unlock()
p, ok := pr.soughtPaths[tree]
if !ok {
// Nobody is looking for the path to our tree.
return
}
if p.parent != nil {
panic("commit tree parent unexpectedly filled in")
}
p.parent = pr.requestPathLocked(oid, "commit")
p.relativePath = ""
// We don't need to keep looking for the child anymore:
delete(pr.soughtPaths, tree)
}
func (pr *InOrderPathResolver) RecordTag(oid git.OID, tag *git.Tag) {
// Not implemented.
}