BlueGit

timfa bluegit

Files

bluegit / internal / gitgraph / graph.go

graph.go

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