BlueGit

timfa bluegit

Files

bluegit / internal / gitgraph / graph.go

graph.go

graph.go 11.3 KiB Download Raw
1// Package gitgraph legt een commitgrafiek over branches en tags en
2// bewaart die in een begrensde geheugencache.
3package gitgraph
4
5import (
6 "crypto/sha256"
7 "encoding/hex"
8 "fmt"
9 "sort"
10 "strings"
11)
12
13// DefaultLimit is het aantal recente commits dat in de grafiek past.
14const DefaultLimit = 40
15
16// PaletteSize is het aantal kleuren voor niet-hoofdbranches.
17const PaletteSize = 8
18
19// RowH, LaneW en DotR zijn de tekenmaten in pixels.
20const (
21 RowH = 22
22 LaneW = 12
23 DotR = 4.0
24 RefW = 78
25)
26
27// Commit is één commit voor de grafiek, met ouders.
28type Commit struct {
29 SHA, Short, Author, Email, Subject string
30 Unix int64
31 Parents []string
32}
33
34// Ref is een branch of tag die naar een commit wijst.
35type Ref struct {
36 Name string
37 SHA string
38 Kind string // "branch" of "tag"
39}
40
41// Label is een verkorte branch- of tagnaam bij een commit.
42type Label struct {
43 Name, Kind, Color, Class string
44 Default bool
45}
46
47// Row is één regel in de gelegde grafiek.
48type Row struct {
49 Commit
50 Lane int
51 Color string
52 Class string
53 Labels []Label
54 Avatar string
55 Initial string
56 UserURL string
57}
58
59// Edge is een lijn van een kind naar een ouder (of het einde van het venster).
60type Edge struct {
61 FromRow, FromLane, ToRow, ToLane int
62 Color string
63}
64
65// Graph is een gelegde commitgrafiek, klaar om te tekenen.
66type Graph struct {
67 Rows []Row
68 Edges []Edge
69 Lanes int
70 Width int
71 Height int
72}
73
74// Color is de CSS-kleur van een branch. De hoofdbranch is altijd --blue.
75func Color(branch, defaultBranch string) string {
76 if strings.TrimSpace(branch) != "" && branch == defaultBranch {
77 return "var(--blue)"
78 }
79 return fmt.Sprintf("var(--graph-%d)", hashName(branch)%PaletteSize)
80}
81
82// ColorClass is een CSS-klasse voor dezelfde kleur, veilig in templates
83// (html/template weigert var(--…) in een style-attribuut).
84func ColorClass(color string) string {
85 if color == "var(--blue)" {
86 return "is-main"
87 }
88 if strings.HasPrefix(color, "var(--graph-") && strings.HasSuffix(color, ")") {
89 mid := color[len("var(--graph-") : len(color)-1]
90 if len(mid) == 1 && mid[0] >= '0' && mid[0] < '0'+byte(PaletteSize) {
91 return "c" + mid
92 }
93 }
94 return ""
95}
96
97func hashName(name string) int {
98 n := 0
99 for _, r := range strings.ToLower(strings.TrimSpace(name)) {
100 n = n*33 + int(r)
101 }
102 if n < 0 {
103 n = -n
104 }
105 return n
106}
107
108// Key is de cachesleutel: repo plus de stand van alle branch- en tag-tips.
109func Key(repoID int64, tips map[string]string, defaultBranch string, limit int) string {
110 if limit < 1 {
111 limit = DefaultLimit
112 }
113 names := make([]string, 0, len(tips))
114 for n := range tips {
115 names = append(names, n)
116 }
117 sort.Strings(names)
118 var b strings.Builder
119 fmt.Fprintf(&b, "%d\n%d\n%s\n", repoID, limit, defaultBranch)
120 for _, n := range names {
121 b.WriteString(n)
122 b.WriteByte('=')
123 b.WriteString(tips[n])
124 b.WriteByte('\n')
125 }
126 sum := sha256.Sum256([]byte(b.String()))
127 return fmt.Sprintf("%d:%s", repoID, hex.EncodeToString(sum[:16]))
128}
129
130type laneState struct {
131 sha string
132 color string
133}
134
135// Layout wijst lanes toe en legt lijnen voor merges en forks.
136// commits staat nieuwste eerst. Ontbrekende ouders lopen tot de onderkant.
137func Layout(commits []Commit, refs []Ref, defaultBranch string) *Graph {
138 g := &Graph{}
139 if len(commits) == 0 {
140 return g
141 }
142 bySHA := make(map[string]int, len(commits))
143 for i, c := range commits {
144 bySHA[c.SHA] = i
145 if c.Short == "" && len(c.SHA) >= 10 {
146 commits[i].Short = c.SHA[:10]
147 }
148 }
149 labels := labelsBySHA(refs, defaultBranch)
150 mainline := mainlineSHAs(commits, refs, defaultBranch)
151
152 var lanes []laneState
153 // Lane 0 is gereserveerd voor de hoofdbranch, zodat een nieuwere
154 // zijtak die kleur en kolom niet inpikt.
155 if def := defaultTip(refs, defaultBranch); def != "" {
156 lanes = []laneState{{sha: def, color: "var(--blue)"}}
157 }
158 g.Rows = make([]Row, len(commits))
159 occupancy := make([][]laneState, len(commits)+1)
160
161 for i, c := range commits {
162 incoming := findSHA(lanes, c.SHA)
163 if len(incoming) == 0 {
164 col := colorForCommit(c.SHA, labels, defaultBranch, "")
165 if mainline[c.SHA] {
166 col = "var(--blue)"
167 }
168 incoming = []int{allocLane(&lanes, c.SHA, col)}
169 }
170 primary := pickPrimary(incoming, lanes, c.SHA, labels, defaultBranch)
171 if mainline[c.SHA] {
172 // blijf op lane 0 als die op deze commit wacht
173 for _, li := range incoming {
174 if li == 0 {
175 primary = 0
176 break
177 }
178 }
179 }
180 row := Row{Commit: commits[i], Lane: primary, Labels: labels[c.SHA]}
181 if mainline[c.SHA] {
182 row.Color = "var(--blue)"
183 } else {
184 inherit := lanes[primary].color
185 if inherit == "var(--blue)" {
186 inherit = ""
187 }
188 col := colorForCommit(c.SHA, labels, defaultBranch, inherit)
189 if col == "" || col == "var(--blue)" {
190 col = Color(c.SHA, defaultBranch)
191 }
192 row.Color = col
193 }
194 if row.Color == "" {
195 row.Color = "var(--graph-0)"
196 }
197 row.Class = ColorClass(row.Color)
198 lanes[primary].color = row.Color
199 g.Rows[i] = row
200
201 for _, li := range incoming {
202 if li != primary {
203 lanes[li].sha = ""
204 }
205 }
206 if len(c.Parents) == 0 {
207 lanes[primary].sha = ""
208 } else {
209 first := c.Parents[0]
210 if idx := firstLane(lanes, first); idx >= 0 && idx != primary && !mainline[c.SHA] && !mainline[first] {
211 // zijtak: eerste ouder zit al in een andere lane, daarheen mergen
212 lanes[primary].sha = ""
213 } else {
214 lanes[primary].sha = first
215 }
216 for _, p := range c.Parents[1:] {
217 if firstLane(lanes, p) >= 0 {
218 continue
219 }
220 col := colorForCommit(p, labels, defaultBranch, "")
221 if col == "" || col == "var(--blue)" && !mainline[p] {
222 col = Color(p, defaultBranch)
223 }
224 allocLane(&lanes, p, col)
225 }
226 if lanes[primary].sha == "" {
227 if firstLane(lanes, first) < 0 && first != "" {
228 allocLane(&lanes, first, row.Color)
229 }
230 }
231 }
232 occupancy[i+1] = copyLanes(lanes)
233 trimTrailing(&lanes)
234 }
235 occupancy[0] = make([]laneState, len(occupancy[1]))
236 if len(occupancy[0]) > 0 && len(g.Rows) > 0 {
237 // bovenaan: de lane van de nieuwste commit is bezet
238 if g.Rows[0].Lane < len(occupancy[0]) {
239 occupancy[0][g.Rows[0].Lane] = laneState{sha: g.Rows[0].SHA, color: g.Rows[0].Color}
240 }
241 }
242 g.Edges = buildEdges(g.Rows, bySHA, occupancy)
243 g.Lanes = 1
244 for _, r := range g.Rows {
245 if r.Lane+1 > g.Lanes {
246 g.Lanes = r.Lane + 1
247 }
248 }
249 for _, e := range g.Edges {
250 if e.FromLane+1 > g.Lanes {
251 g.Lanes = e.FromLane + 1
252 }
253 if e.ToLane+1 > g.Lanes {
254 g.Lanes = e.ToLane + 1
255 }
256 }
257 g.Width = g.Lanes * LaneW
258 g.Height = len(g.Rows) * RowH
259 return g
260}
261
262func labelsBySHA(refs []Ref, defaultBranch string) map[string][]Label {
263 out := map[string][]Label{}
264 for _, r := range refs {
265 if r.SHA == "" || r.Name == "" {
266 continue
267 }
268 lb := Label{Name: shortName(r.Name), Kind: r.Kind, Color: Color(r.Name, defaultBranch), Default: r.Kind == "branch" && r.Name == defaultBranch}
269 if r.Kind == "tag" {
270 lb.Color = "var(--muted)"
271 lb.Class = "is-tag"
272 } else {
273 lb.Class = ColorClass(lb.Color)
274 }
275 out[r.SHA] = append(out[r.SHA], lb)
276 }
277 for sha, list := range out {
278 sort.Slice(list, func(i, j int) bool {
279 if list[i].Default != list[j].Default {
280 return list[i].Default
281 }
282 if list[i].Kind != list[j].Kind {
283 return list[i].Kind == "branch"
284 }
285 return list[i].Name < list[j].Name
286 })
287 out[sha] = list
288 }
289 return out
290}
291
292func shortName(name string) string {
293 const max = 18
294 if strings.HasPrefix(name, "refs/heads/") {
295 name = strings.TrimPrefix(name, "refs/heads/")
296 }
297 if strings.HasPrefix(name, "refs/tags/") {
298 name = strings.TrimPrefix(name, "refs/tags/")
299 }
300 runes := []rune(name)
301 if len(runes) <= max {
302 return name
303 }
304 return string(runes[:max-1]) + "…"
305}
306
307func colorForCommit(sha string, labels map[string][]Label, defaultBranch, fallback string) string {
308 for _, lb := range labels[sha] {
309 if lb.Default {
310 return "var(--blue)"
311 }
312 }
313 for _, lb := range labels[sha] {
314 if lb.Kind == "branch" {
315 return lb.Color
316 }
317 }
318 if fallback != "" {
319 return fallback
320 }
321 if defaultBranch != "" {
322 return Color(sha, defaultBranch) // stabiel, maar niet --blue
323 }
324 return "var(--graph-0)"
325}
326
327func findSHA(lanes []laneState, sha string) []int {
328 var out []int
329 for i, l := range lanes {
330 if l.sha == sha {
331 out = append(out, i)
332 }
333 }
334 return out
335}
336
337func firstLane(lanes []laneState, sha string) int {
338 for i, l := range lanes {
339 if l.sha == sha {
340 return i
341 }
342 }
343 return -1
344}
345
346func pickPrimary(incoming []int, lanes []laneState, sha string, labels map[string][]Label, defaultBranch string) int {
347 want := colorForCommit(sha, labels, defaultBranch, "")
348 for _, i := range incoming {
349 if lanes[i].color == want || (want == "var(--blue)" && lanes[i].color == "var(--blue)") {
350 return i
351 }
352 }
353 return incoming[0]
354}
355
356func allocLane(lanes *[]laneState, sha, color string) int {
357 for i, l := range *lanes {
358 if l.sha == "" {
359 (*lanes)[i] = laneState{sha: sha, color: color}
360 return i
361 }
362 }
363 *lanes = append(*lanes, laneState{sha: sha, color: color})
364 return len(*lanes) - 1
365}
366
367func copyLanes(lanes []laneState) []laneState {
368 out := make([]laneState, len(lanes))
369 copy(out, lanes)
370 return out
371}
372
373func trimTrailing(lanes *[]laneState) {
374 n := len(*lanes)
375 for n > 0 && (*lanes)[n-1].sha == "" {
376 n--
377 }
378 *lanes = (*lanes)[:n]
379}
380
381func buildEdges(rows []Row, bySHA map[string]int, occ [][]laneState) []Edge {
382 var edges []Edge
383 seen := map[[4]int]bool{}
384 add := func(e Edge) {
385 if e.FromRow < 0 || e.ToRow < e.FromRow {
386 return
387 }
388 k := [4]int{e.FromRow, e.FromLane, e.ToRow, e.ToLane}
389 if seen[k] {
390 return
391 }
392 seen[k] = true
393 edges = append(edges, e)
394 }
395 // Van elke commit naar zijn ouders in het venster, of naar de onderkant.
396 for i, r := range rows {
397 if len(r.Parents) == 0 {
398 continue
399 }
400 for pi, p := range r.Parents {
401 toRow, toLane := len(rows)-1, r.Lane
402 if j, ok := bySHA[p]; ok {
403 toRow = j
404 toLane = rows[j].Lane
405 } else {
406 // ouder buiten het venster: zoek de lane waarin we die sha bewaren
407 toLane = r.Lane
408 if i+1 < len(occ) {
409 if idx := firstLane(occ[i+1], p); idx >= 0 {
410 toLane = idx
411 }
412 }
413 toRow = len(rows) - 1
414 }
415 col := r.Color
416 if pi == 0 && r.Color != "" {
417 col = r.Color
418 }
419 // Tussenliggende verticale stukken volgen de gereserveerde lane.
420 fromLane := r.Lane
421 if pi > 0 && i+1 < len(occ) {
422 if idx := firstLane(occ[i+1], p); idx >= 0 {
423 fromLane = idx
424 // boog vanaf de merge-commit naar de ouder-lane op de volgende rij
425 add(Edge{FromRow: i, FromLane: r.Lane, ToRow: i + 1, ToLane: fromLane, Color: col})
426 if toRow > i+1 {
427 add(Edge{FromRow: i + 1, FromLane: fromLane, ToRow: toRow, ToLane: toLane, Color: col})
428 }
429 continue
430 }
431 }
432 add(Edge{FromRow: i, FromLane: fromLane, ToRow: toRow, ToLane: toLane, Color: col})
433 }
434 }
435 return edges
436}
437
438func defaultTip(refs []Ref, defaultBranch string) string {
439 for _, r := range refs {
440 if r.Kind == "branch" && r.Name == defaultBranch {
441 return r.SHA
442 }
443 }
444 return ""
445}
446
447func mainlineSHAs(commits []Commit, refs []Ref, defaultBranch string) map[string]bool {
448 out := map[string]bool{}
449 tip := defaultTip(refs, defaultBranch)
450 if tip == "" {
451 return out
452 }
453 parents := map[string][]string{}
454 for _, c := range commits {
455 parents[c.SHA] = c.Parents
456 }
457 seen := map[string]bool{}
458 for sha := tip; sha != "" && !seen[sha]; {
459 seen[sha] = true
460 out[sha] = true
461 ps := parents[sha]
462 if len(ps) == 0 {
463 break
464 }
465 sha = ps[0]
466 }
467 return out
468}