| 1 | // Package gitgraph legt een commitgrafiek over branches en tags en |
| 2 | // bewaart die in een begrensde geheugencache. |
| 3 | package gitgraph |
| 4 | |
| 5 | import ( |
| 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. |
| 14 | const DefaultLimit = 40 |
| 15 | |
| 16 | // PaletteSize is het aantal kleuren voor niet-hoofdbranches. |
| 17 | const 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. |
| 24 | const ( |
| 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. |
| 35 | type 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. |
| 42 | type 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). |
| 50 | type Label struct { |
| 51 | Name, Ref, Kind, Color, Class string |
| 52 | Default bool |
| 53 | } |
| 54 | |
| 55 | // Row is één regel in de gelegde grafiek. |
| 56 | type 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). |
| 69 | type Edge struct { |
| 70 | FromRow, FromLane, ToRow, ToLane int |
| 71 | Color, Branch string |
| 72 | } |
| 73 | |
| 74 | // Graph is een gelegde commitgrafiek, klaar om te tekenen. |
| 75 | type 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. |
| 86 | func 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). |
| 95 | func 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 | |
| 108 | func 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. |
| 120 | func 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 | |
| 141 | type 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. |
| 147 | func 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 | |
| 277 | func 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 | |
| 307 | func 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 | |
| 322 | func 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 | |
| 342 | func 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 | |
| 352 | func 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 | |
| 361 | func 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 | |
| 371 | func 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 | |
| 382 | func 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 | |
| 405 | func copyLanes(lanes []laneState) []laneState { |
| 406 | out := make([]laneState, len(lanes)) |
| 407 | copy(out, lanes) |
| 408 | return out |
| 409 | } |
| 410 | |
| 411 | func trimTrailing(lanes *[]laneState) { |
| 412 | n := len(*lanes) |
| 413 | for n > 0 && (*lanes)[n-1].sha == "" { |
| 414 | n-- |
| 415 | } |
| 416 | *lanes = (*lanes)[:n] |
| 417 | } |
| 418 | |
| 419 | func 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 | |
| 483 | func 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 | |
| 492 | func 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 | } |