browsecache.go RawHistoryFolder

1// SPDX-License-Identifier: AGPL-3.0-or-later
2
3package usecase
4
5import (
6	"container/list"
7	"slices"
8	"sync"
9
10	"bnema.dev/ermite/internal/domain"
11	"bnema.dev/ermite/internal/ports"
12)
13
14// Default bounds of the history cache of Browse.
15const (
16	// DefaultHistoryCacheEntries bounds the cached answers.
17	DefaultHistoryCacheEntries = 256
18	// DefaultHistoryCacheBytes bounds their estimated size.
19	DefaultHistoryCacheBytes = 8 << 20
20)
21
22// historyKey names an answer that depends only on immutable data: a commit
23// designated by its full id, the path inside it, and for a page of history
24// where it starts and how long it is. The repository is part of the key so
25// that an answer is never served across a name, and so is its creation time
26// (in nanoseconds): a repository deleted and created again under the same
27// name is another repository, whose commit ids must not hit the old answers.
28type historyKey struct {
29	repo    domain.RepoName
30	created int64
31	rev     string // full commit id
32	path    string
33	kind    historyKind
34	limit   int
35}
36
37type historyKind uint8
38
39const (
40	kindTreeLast historyKind = iota // a directory with the last commit of its entries
41	kindPage                        // the first page of the history of a path
42)
43
44// historyCache is a small LRU of answers about commits, bounded by entry count
45// and by estimated bytes. The answers are immutable (a commit id fixes its
46// whole history), so there is no invalidation: entries leave by eviction only.
47// It is safe for concurrent use. Values are stored and returned as copies, so
48// a caller cannot alter what another one gets.
49type historyCache struct {
50	maxEntries int
51	maxBytes   int64
52
53	mu    sync.Mutex
54	order *list.List // front is the most recently used
55	items map[historyKey]*list.Element
56	bytes int64
57}
58
59type historyEntry struct {
60	key  historyKey
61	tree domain.Tree
62	page ports.CommitPage
63	size int64
64}
65
66// newHistoryCache returns nil (no cache) unless both bounds are positive.
67func newHistoryCache(maxEntries int, maxBytes int64) *historyCache {
68	if maxEntries <= 0 || maxBytes <= 0 {
69		return nil
70	}
71	return &historyCache{
72		maxEntries: maxEntries, maxBytes: maxBytes,
73		order: list.New(), items: map[historyKey]*list.Element{},
74	}
75}
76
77// get returns the entry of key and marks it recently used.
78func (c *historyCache) get(key historyKey) (*historyEntry, bool) {
79	if c == nil {
80		return nil, false
81	}
82	c.mu.Lock()
83	defer c.mu.Unlock()
84	el, ok := c.items[key]
85	if !ok {
86		return nil, false
87	}
88	c.order.MoveToFront(el)
89	return el.Value.(*historyEntry), true
90}
91
92// put stores e, then evicts the least recently used entries until both bounds
93// hold. An entry larger than the byte bound is not stored.
94func (c *historyCache) put(e *historyEntry) {
95	if c == nil || e.size > c.maxBytes {
96		return
97	}
98	c.mu.Lock()
99	defer c.mu.Unlock()
100	if el, ok := c.items[e.key]; ok {
101		c.bytes -= el.Value.(*historyEntry).size
102		c.order.Remove(el)
103	}
104	c.items[e.key] = c.order.PushFront(e)
105	c.bytes += e.size
106	for c.order.Len() > c.maxEntries || c.bytes > c.maxBytes {
107		oldest := c.order.Back()
108		old := oldest.Value.(*historyEntry)
109		c.order.Remove(oldest)
110		delete(c.items, old.key)
111		c.bytes -= old.size
112	}
113}
114
115// treeEntry builds the entry of a tree; the tree is copied.
116func treeEntry(key historyKey, t domain.Tree) *historyEntry {
117	t = cloneTree(t)
118	size := int64(256 + len(t.Entries)*160)
119	for _, e := range t.Entries {
120		size += int64(len(e.Name) + len(e.Path))
121		if e.LastCommit != nil {
122			size += commitSize(*e.LastCommit)
123		}
124	}
125	return &historyEntry{key: key, tree: t, size: size}
126}
127
128// pageEntry builds the entry of a page of history; the page is copied.
129func pageEntry(key historyKey, p ports.CommitPage) *historyEntry {
130	p = clonePage(p)
131	size := int64(128)
132	for _, c := range p.Commits {
133		size += commitSize(c)
134	}
135	return &historyEntry{key: key, page: p, size: size}
136}
137
138func commitSize(c domain.Commit) int64 {
139	n := 384 + len(c.Parents)*48 + len(c.Summary) + len(c.Message)
140	n += len(c.Author.Name) + len(c.Author.Email) + len(c.Committer.Name) + len(c.Committer.Email)
141	return int64(n)
142}
143
144func cloneCommit(c domain.Commit) domain.Commit {
145	c.Parents = slices.Clone(c.Parents)
146	return c
147}
148
149func cloneTree(t domain.Tree) domain.Tree {
150	t.Entries = slices.Clone(t.Entries)
151	for i := range t.Entries {
152		if lc := t.Entries[i].LastCommit; lc != nil {
153			c := cloneCommit(*lc)
154			t.Entries[i].LastCommit = &c
155		}
156	}
157	return t
158}
159
160func clonePage(p ports.CommitPage) ports.CommitPage {
161	p.Commits = slices.Clone(p.Commits)
162	for i := range p.Commits {
163		p.Commits[i] = cloneCommit(p.Commits[i])
164	}
165	return p
166}