BlueGit

timfa bluegit

Files

bluegit / internal / gitgraph / graph.go

graph.go

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