BlueGit

timfa bluegit

Files

bluegit / internal / gitgraph / graph.go

graph.go

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