BlueGit

timfa bluegit

Files

bluegit / internal / gitgraph / graph.go

graph.go

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