1// SPDX-License-Identifier: MIT
2
3package git
4
5import (
6 "bytes"
7 "errors"
8 "fmt"
9 "io"
10 "io/fs"
11 "iter"
12 "os"
13 "slices"
14 "strings"
15 "syscall"
16 "time"
17)
18
19const (
20 // maxRefFile bounds a loose ref file or HEAD.
21 maxRefFile = 4096
22 // maxPackedRefs bounds the packed-refs file that is loaded.
23 maxPackedRefs = 1 << 30
24 // maxSymrefDepth is the number of symbolic refs followed, as in Git.
25 maxSymrefDepth = 5
26)
27
28// Ref is a reference.
29type Ref struct {
30 // Name is the full name, such as "refs/heads/main".
31 Name string
32 // ID is the object the ref designates, after following symbolic refs.
33 // It may be an annotated tag; see Repo.PeelRef.
34 ID ObjectID
35 // Symref is the name of the ref this one points to when it is a symbolic
36 // ref, empty otherwise.
37 Symref string
38 // Peeled is the object that ID designates once annotated tags are
39 // followed. It is only set when PeeledKnown, which is the case for refs
40 // read from packed-refs that carry peeled values.
41 Peeled ObjectID
42 PeeledKnown bool
43}
44
45// packedRef is an entry of packed-refs.
46type packedRef struct {
47 name string
48 id ObjectID
49 peeled ObjectID
50 peeledKnown bool
51}
52
53// packedRefs is an immutable parsed packed-refs file, sorted by name.
54type packedRefs struct {
55 sig fileSig
56 raw string // the file content: the names in refs point into it
57 refs []packedRef
58}
59
60func (p *packedRefs) find(name string) (packedRef, bool) {
61 i, ok := slices.BinarySearchFunc(p.refs, name, func(e packedRef, n string) int {
62 return strings.Compare(e.name, n)
63 })
64 if !ok {
65 return packedRef{}, false
66 }
67 return p.refs[i], true
68}
69
70// loadPacked returns the current content of packed-refs, reparsing the file
71// when its stat data changed (or always with force). Concurrent callers share
72// one parse: the check is repeated once pmu is held.
73func (r *Repo) loadPacked(force bool) (*packedRefs, error) {
74 sig, err := r.paths.packedRefs.sig()
75 if err != nil {
76 return nil, err
77 }
78 if cur := r.packed.Load(); !force && cur != nil && cur.sig.same(sig) {
79 return cur, nil
80 }
81 r.pmu.Lock()
82 defer r.pmu.Unlock()
83 cur := r.packed.Load()
84 if !force && cur != nil && (cur.sig.read > sig.read || cur.sig.same(sig)) {
85 // Another caller parsed the file while we waited for the lock. It read
86 // the file after we looked at it, so its result is at least as fresh
87 // as ours would be.
88 return cur, nil
89 }
90 read := time.Now().UnixNano()
91 path := r.dir + "/packed-refs"
92 f, err := os.Open(path)
93 if errors.Is(err, fs.ErrNotExist) {
94 p := &packedRefs{sig: fileSig{read: read}}
95 r.packed.Store(p)
96 return p, nil
97 }
98 if err != nil {
99 return nil, err
100 }
101 defer func() { _ = f.Close() }()
102 st, err := f.Stat()
103 if err != nil {
104 return nil, err
105 }
106 if st.Size() > maxPackedRefs {
107 return nil, unsupported("packed-refs larger than %d bytes", maxPackedRefs)
108 }
109 data := make([]byte, st.Size())
110 if _, err := io.ReadFull(f, data); err != nil {
111 return nil, err
112 }
113 if !force && cur != nil && cur.raw == string(data) {
114 // Racy stat data, same content (Git's racy rule): keep the parse
115 // and record that the file was read now.
116 p := &packedRefs{sig: sigOf(st, read), raw: cur.raw, refs: cur.refs}
117 r.packed.Store(p)
118 return p, nil
119 }
120 p, err := parsePackedRefs(string(data))
121 if err != nil {
122 return nil, err
123 }
124 if i, _ := slices.BinarySearchFunc(p.refs, "refs/replace/", func(e packedRef, n string) int {
125 return strings.Compare(e.name, n)
126 }); i < len(p.refs) && strings.HasPrefix(p.refs[i].name, "refs/replace/") {
127 return nil, unsupported("replace refs (refs/replace in packed-refs)")
128 }
129 p.sig = sigOf(st, read)
130 r.packed.Store(p)
131 return p, nil
132}
133
134// parsePackedRefs parses a packed-refs file. The ref names are substrings of
135// data.
136func parsePackedRefs(data string) (*packedRefs, error) {
137 p := &packedRefs{raw: data}
138 fullyPeeled, peeled := false, false
139 first := true
140 for len(data) > 0 {
141 var line string
142 line, data, _ = strings.Cut(data, "\n")
143 line = strings.TrimSuffix(line, "\r")
144 if line == "" {
145 continue
146 }
147 switch line[0] {
148 case '#':
149 if first && strings.HasPrefix(line, "# pack-refs with:") {
150 for _, tr := range strings.Fields(line[len("# pack-refs with:"):]) {
151 switch tr {
152 case "fully-peeled":
153 fullyPeeled = true
154 case "peeled":
155 peeled = true
156 }
157 }
158 }
159 first = false
160 continue
161 case '^':
162 if len(p.refs) == 0 {
163 return nil, corrupt("packed-refs: peeled line without a ref")
164 }
165 id, ok := parseIDBytes([]byte(line[1:]))
166 if !ok {
167 return nil, corrupt("packed-refs: bad peeled line")
168 }
169 last := &p.refs[len(p.refs)-1]
170 last.peeled, last.peeledKnown = id, true
171 continue
172 }
173 first = false
174 hex, name, ok := strings.Cut(line, " ")
175 if !ok || len(hex) != 40 || name == "" {
176 return nil, corrupt("packed-refs: bad line %q", truncate(line))
177 }
178 id, ok := parseIDBytes([]byte(hex))
179 if !ok {
180 return nil, corrupt("packed-refs: bad id in line %q", truncate(line))
181 }
182 e := packedRef{name: name, id: id}
183 // Without a ^ line, a ref is known not to be a tag when the file
184 // is fully peeled (or, for the old "peeled" trait, outside tags).
185 if fullyPeeled || (peeled && strings.HasPrefix(name, "refs/tags/")) {
186 e.peeled, e.peeledKnown = id, true
187 }
188 p.refs = append(p.refs, e)
189 }
190 cmp := func(a, b packedRef) int { return strings.Compare(a.name, b.name) }
191 if !slices.IsSortedFunc(p.refs, cmp) {
192 slices.SortStableFunc(p.refs, cmp)
193 }
194 return p, nil
195}
196
197// validRefName rejects names that could leave the repository directory or
198// that Git itself refuses. It is a subset of git check-ref-format.
199func validRefName(name string) bool {
200 if !strings.HasPrefix(name, "refs/") {
201 return false
202 }
203 if name == "" || len(name) > 1024 || name[0] == '/' || name[len(name)-1] == '/' || strings.HasSuffix(name, ".lock") {
204 return false
205 }
206 if strings.Contains(name, "..") || strings.Contains(name, "//") || strings.Contains(name, "@{") {
207 return false
208 }
209 for _, c := range []byte(name) {
210 if c < 0x20 || c == 0x7f || c == '\\' || c == ' ' || c == '~' || c == '^' || c == ':' || c == '?' || c == '*' || c == '[' {
211 return false
212 }
213 }
214 for comp := range strings.SplitSeq(name, "/") {
215 if comp == "" || comp[0] == '.' || strings.HasSuffix(comp, ".lock") {
216 return false
217 }
218 }
219 return true
220}
221
222// looseRef is the content of a loose ref file.
223type looseRef struct {
224 id ObjectID
225 symref string
226}
227
228// readLooseRef reads a loose ref. found is false when there is no such file
229// (or it is a directory).
230func (r *Repo) readLooseRef(name string) (lr looseRef, found bool, err error) {
231 // The path goes through a stack buffer and the file is opened with a
232 // plain system call: a ref that does not exist, which is what most
233 // candidates of a revision lookup are, allocates nothing.
234 var arr [256]byte
235 nul := append(arr[:0], r.dir...)
236 nul = append(nul, '/')
237 nul = append(nul, name...)
238 nul = append(nul, 0)
239 file, err := openNul(nul)
240 if err != nil {
241 if isNotExistErrno(err) {
242 return lr, false, nil
243 }
244 return lr, false, openError(nul, err)
245 }
246 defer file.close()
247 pb := getBuf()
248 defer putBuf(pb)
249 pb.b = grow(pb.b, maxRefFile+1)
250 buf := pb.b
251 n, dir, err := file.readFull(buf)
252 if err != nil {
253 return lr, false, &fs.PathError{Op: "read", Path: r.dir + "/" + name, Err: err}
254 }
255 if dir {
256 return lr, false, nil
257 }
258 if n > maxRefFile {
259 return lr, true, corrupt("ref %s is larger than %d bytes", name, maxRefFile)
260 }
261 lr, err = parseRefContent(buf[:n])
262 if err != nil {
263 return lr, true, fmt.Errorf("ref %s: %w", name, err)
264 }
265 return lr, true, nil
266}
267
268func parseRefContent(b []byte) (looseRef, error) {
269 // On bytes: an id ref, the common case, allocates nothing.
270 b = bytes.TrimRight(b, " \t\r\n")
271 if target, ok := bytes.CutPrefix(b, []byte("ref:")); ok {
272 t := string(bytes.TrimSpace(target))
273 if !validRef(t) {
274 return looseRef{}, corrupt("bad symbolic ref target %q", truncate(t))
275 }
276 return looseRef{symref: t}, nil
277 }
278 if len(b) >= 40 {
279 if id, ok := parseIDBytes(b[:40]); ok && (len(b) == 40 || b[40] == ' ' || b[40] == '\t') {
280 return looseRef{id: id}, nil
281 }
282 }
283 return looseRef{}, corrupt("bad ref content %q", truncate(string(b)))
284}
285
286// validRootRef reports whether name is a pseudo-ref of the Git directory such
287// as HEAD or ORIG_HEAD: upper case letters and underscores only.
288func validRootRef(name string) bool {
289 if name == "" || len(name) > 64 {
290 return false
291 }
292 for _, c := range []byte(name) {
293 if (c < 'A' || c > 'Z') && c != '_' {
294 return false
295 }
296 }
297 return true
298}
299
300// validRef accepts the names lookupRef may read.
301func validRef(name string) bool { return validRefName(name) || validRootRef(name) }
302
303// refWalk is a ref lookup that went through the loose files and may still
304// need packed-refs.
305type refWalk struct {
306 ref Ref
307 cur string // the name to look up in packed-refs when !done
308 done bool // the lookup is complete: ok tells whether it found a ref
309 ok bool
310}
311
312// isRootRef reports whether name is a pseudo-ref of the Git directory
313// (HEAD, ORIG_HEAD...) rather than a name under refs/.
314func isRootRef(name string) bool { return !strings.HasPrefix(name, "refs/") }
315
316// lookupLoose follows name through the loose files and symbolic refs. It
317// stops at a loose ref that holds an id, or at the first name that has no
318// loose file: packed-refs decides about that one (see finish).
319func (r *Repo) lookupLoose(name string) (refWalk, error) {
320 if !validRef(name) {
321 return refWalk{done: true}, nil
322 }
323 w := refWalk{ref: Ref{Name: name}, cur: name}
324 for depth := 0; ; depth++ {
325 if depth > maxSymrefDepth {
326 return refWalk{}, corrupt("ref %s: symbolic ref loop", name)
327 }
328 lr, found, err := r.readLooseRef(w.cur)
329 if err != nil {
330 if errors.Is(err, ErrCorrupt) && isRootRef(w.cur) && w.cur != "HEAD" {
331 // A pseudo-ref such as FETCH_HEAD or MERGE_HEAD can hold
332 // anything (FETCH_HEAD has one line per fetched ref), and
333 // a revision like "ABCDEF" may name such a file by
334 // accident: it is not a ref, so not found. A broken HEAD
335 // stays an error.
336 return refWalk{done: true}, nil
337 }
338 return refWalk{}, err
339 }
340 if found && lr.symref != "" {
341 if depth == 0 {
342 w.ref.Symref = lr.symref
343 }
344 if !validRef(lr.symref) {
345 return refWalk{done: true}, nil
346 }
347 w.cur = lr.symref
348 continue
349 }
350 if found {
351 w.ref.ID = lr.id
352 w.done, w.ok = true, true
353 return w, nil
354 }
355 return w, nil
356 }
357}
358
359// finish completes a lookup with the content of packed-refs. The loose files
360// have to be read before packed-refs is loaded: a concurrent pack-refs writes
361// packed-refs first and deletes the loose file after, so it is never missed.
362func (w *refWalk) finish(p *packedRefs) (Ref, bool) {
363 if w.done {
364 return w.ref, w.ok
365 }
366 e, ok := p.find(w.cur)
367 if !ok {
368 return Ref{}, false
369 }
370 w.ref.ID = e.id
371 if w.cur == w.ref.Name {
372 w.ref.Peeled, w.ref.PeeledKnown = e.peeled, e.peeledKnown
373 }
374 return w.ref, true
375}
376
377// lookupRef resolves name through symbolic refs. loose refs win over packed
378// ones.
379func (r *Repo) lookupRef(name string) (Ref, bool, error) {
380 if r.snap.Load() == nil {
381 return Ref{}, false, ErrClosed
382 }
383 w, err := r.lookupLoose(name)
384 if err != nil {
385 return Ref{}, false, err
386 }
387 if w.done {
388 ref, ok := w.finish(nil)
389 return ref, ok, nil
390 }
391 p, err := r.loadPacked(false)
392 if err != nil {
393 return Ref{}, false, err
394 }
395 ref, ok := w.finish(p)
396 return ref, ok, nil
397}
398
399// ResolveRef returns the object the ref with this full name (such as
400// "refs/heads/main", "refs/tags/v1" or "HEAD") designates, following
401// symbolic refs. The result may be an annotated tag; see PeelToCommit. It
402// returns ErrNotFound if the ref does not exist.
403func (r *Repo) ResolveRef(name string) (ObjectID, error) {
404 ref, ok, err := r.lookupRef(name)
405 if err != nil {
406 return ObjectID{}, err
407 }
408 if !ok {
409 return ObjectID{}, notFound("ref %s", name)
410 }
411 return ref.ID, nil
412}
413
414// LookupRefID is like ResolveRef but a ref that does not exist is not an
415// error: ok is false, and nothing is allocated, which makes it the call for
416// trying several candidate names. err is for what went wrong while looking
417// (a closed Repo, an unreadable or corrupt ref).
418func (r *Repo) LookupRefID(name string) (id ObjectID, ok bool, err error) {
419 ref, ok, err := r.lookupRef(name)
420 if err != nil || !ok {
421 return ObjectID{}, false, err
422 }
423 return ref.ID, true, nil
424}
425
426// LookupRef is like ResolveRef but returns the whole Ref.
427func (r *Repo) LookupRef(name string) (Ref, error) {
428 ref, ok, err := r.lookupRef(name)
429 if err != nil {
430 return Ref{}, err
431 }
432 if !ok {
433 return Ref{}, notFound("ref %s", name)
434 }
435 return ref, nil
436}
437
438// Head returns the full name of the ref HEAD points to ("refs/heads/main")
439// and the object it designates. An unborn branch (the target does not exist
440// yet) is not an error: id is then the zero ObjectID. For a detached HEAD
441// target is empty and id is the commit.
442func (r *Repo) Head() (target string, id ObjectID, err error) {
443 if r.snap.Load() == nil {
444 return "", ObjectID{}, ErrClosed
445 }
446 lr, found, err := r.readLooseRef("HEAD")
447 if err != nil {
448 return "", ObjectID{}, err
449 }
450 if !found {
451 return "", ObjectID{}, notFound("HEAD")
452 }
453 if lr.symref == "" {
454 return "", lr.id, nil
455 }
456 ref, ok, err := r.lookupRef(lr.symref)
457 if err != nil {
458 return "", ObjectID{}, err
459 }
460 if !ok {
461 return lr.symref, ObjectID{}, nil
462 }
463 return lr.symref, ref.ID, nil
464}
465
466// Refs iterates over the refs whose full name starts with prefix, such as
467// "refs/heads/" or "refs/tags/" ("" for all of them), sorted by full name.
468// Loose refs override packed ones; the peeled lines of packed-refs are used.
469// Symbolic refs are resolved; a ref that cannot be read is skipped. HEAD is
470// not part of it, see Head. An error ends the iteration.
471func (r *Repo) Refs(prefix string) iter.Seq2[Ref, error] {
472 return func(yield func(Ref, error) bool) {
473 refs, err := r.collectRefs(prefix)
474 if err != nil {
475 yield(Ref{}, err)
476 return
477 }
478 for _, ref := range refs {
479 if !yield(ref, nil) {
480 return
481 }
482 }
483 }
484}
485
486func (r *Repo) collectRefs(prefix string) ([]Ref, error) {
487 if r.snap.Load() == nil {
488 return nil, ErrClosed
489 }
490 var dir string
491 switch {
492 case strings.HasPrefix(prefix, "refs/"):
493 dir = prefix[:strings.LastIndexByte(prefix, '/')]
494 case strings.HasPrefix("refs/", prefix):
495 dir = "refs"
496 default:
497 return nil, nil
498 }
499 // Loose refs first, packed-refs after: see refWalk.finish.
500 var loose []string
501 if err := r.walkLoose(dir, prefix, &loose, 0); err != nil {
502 return nil, err
503 }
504 slices.Sort(loose)
505 loose = slices.Compact(loose)
506 type item struct {
507 name string
508 w refWalk
509 }
510 items := make([]item, 0, len(loose))
511 for _, n := range loose {
512 w, err := r.lookupLoose(n)
513 if err != nil {
514 if errors.Is(err, ErrCorrupt) {
515 continue // Git ignores broken refs when listing
516 }
517 return nil, err
518 }
519 items = append(items, item{name: n, w: w})
520 }
521 // One load of packed-refs serves every name.
522 p, err := r.loadPacked(false)
523 if err != nil {
524 return nil, err
525 }
526 start, _ := slices.BinarySearchFunc(p.refs, prefix, func(e packedRef, pre string) int {
527 if strings.HasPrefix(e.name, pre) {
528 return 0
529 }
530 return strings.Compare(e.name, pre)
531 })
532 // BinarySearchFunc with a prefix comparator may land inside the range:
533 // walk back to its first element.
534 for start > 0 && strings.HasPrefix(p.refs[start-1].name, prefix) {
535 start--
536 }
537 nLoose := len(items)
538 for i := start; i < len(p.refs) && strings.HasPrefix(p.refs[i].name, prefix); i++ {
539 n := p.refs[i].name
540 if _, ok := slices.BinarySearch(loose, n); ok {
541 continue // the loose file wins; its walk is already in items
542 }
543 if !validRef(n) {
544 continue
545 }
546 items = append(items, item{name: n, w: refWalk{ref: Ref{Name: n}, cur: n}})
547 }
548 if len(items) > nLoose {
549 slices.SortFunc(items, func(a, b item) int { return strings.Compare(a.name, b.name) })
550 }
551 out := make([]Ref, 0, len(items))
552 for i := range items {
553 it := &items[i]
554 if ref, ok := it.w.finish(p); ok {
555 ref.Name = it.name
556 out = append(out, ref)
557 }
558 }
559 return out, nil
560}
561
562// maxRefDirDepth bounds the recursion into refs directories.
563const maxRefDirDepth = 64
564
565func (r *Repo) walkLoose(dir, prefix string, out *[]string, depth int) error {
566 if depth > maxRefDirDepth {
567 return nil
568 }
569 entries, err := os.ReadDir(r.dir + "/" + dir)
570 if err != nil {
571 if errors.Is(err, fs.ErrNotExist) || errors.Is(err, syscall.ENOTDIR) {
572 return nil
573 }
574 return err
575 }
576 for _, e := range entries {
577 name := dir + "/" + e.Name()
578 if e.IsDir() {
579 // Descend only where the prefix can match.
580 if strings.HasPrefix(name+"/", prefix) || strings.HasPrefix(prefix, name+"/") {
581 if err := r.walkLoose(name, prefix, out, depth+1); err != nil {
582 return err
583 }
584 }
585 continue
586 }
587 if strings.HasPrefix(name, prefix) && validRefName(name) {
588 *out = append(*out, name)
589 }
590 }
591 return nil
592}
593
594// PeelRef returns the commit a ref designates, following annotated tags. It
595// uses the peeled value of packed-refs when the ref carries one. It returns
596// ErrWrongType if the ref designates something else than a commit.
597func (r *Repo) PeelRef(ref Ref) (ObjectID, error) {
598 if ref.PeeledKnown {
599 typ, _, err := r.ObjectHeader(ref.Peeled)
600 if err != nil {
601 return ObjectID{}, err
602 }
603 if typ != TypeCommit {
604 return ObjectID{}, wrongType(ref.Peeled, typ, TypeCommit)
605 }
606 return ref.Peeled, nil
607 }
608 return r.PeelToCommit(ref.ID)
609}
610
611// Resolve turns a revision name into an object id the way "git rev-parse"
612// does for plain names. The result is not peeled; use PeelToCommit. Revision
613// operators (~, ^, @{}, :path) are not supported.
614//
615// The name is tried in git's order, and the first match wins:
616//
617// 1. a full 40 digit id. It is taken as an id even when a ref has that name
618// (git warns that the ref is ambiguous and ignores it), and it must exist
619// in the repository, which "git rev-parse" does not check;
620// 2. a ref, as "<n>", "refs/<n>", "refs/tags/<n>", "refs/heads/<n>",
621// "refs/remotes/<n>" and "refs/remotes/<n>/HEAD", in that order. A tag
622// therefore wins over a branch of the same name, whereas "git checkout"
623// prefers the branch;
624// 3. an abbreviated id of 4 to 39 digits, which loses against any ref of
625// that name. It matches any object, whatever its type, and fails with
626// ErrAmbiguous if several do; see ResolveCommitPrefix.
627//
628// A caller that wants a branch or a tag, or a commit, should not use Resolve:
629// ResolveRef takes the full ref name and ResolveCommitPrefix only considers
630// commits. Resolve returns an error wrapping ErrNotFound if nothing matches.
631func (r *Repo) Resolve(rev string) (ObjectID, error) {
632 if rev == "" {
633 return ObjectID{}, notFound("empty revision")
634 }
635 if len(rev) == 40 {
636 if id, err := ParseID(rev); err == nil {
637 ok, err := r.HasObject(id)
638 if err != nil {
639 return ObjectID{}, err
640 }
641 if !ok {
642 return ObjectID{}, notFound("object %s", id)
643 }
644 return id, nil
645 }
646 }
647 for _, pat := range [...]string{"%s", "refs/%s", "refs/tags/%s", "refs/heads/%s", "refs/remotes/%s", "refs/remotes/%s/HEAD"} {
648 ref, ok, err := r.lookupRef(fmt.Sprintf(pat, rev))
649 if err != nil {
650 return ObjectID{}, err
651 }
652 if ok {
653 return ref.ID, nil
654 }
655 }
656 if len(rev) >= minPrefix && len(rev) < 40 {
657 id, err := r.ResolvePrefix(rev)
658 if err == nil || !errors.Is(err, ErrInvalidID) {
659 return id, err
660 }
661 }
662 return ObjectID{}, notFound("revision %q", truncate(rev))
663}