1// Copyright 2020 The Gitea Authors. All rights reserved. 2// Use of this source code is governed by a MIT-style 3// license that can be found in the LICENSE file. 4 5package gitgraph 6 7import ( 8 "bytes" 9 "fmt" 10) 11 12// Parser represents a git graph parser. It is stateful containing the previous 13// glyphs, detected flows and color assignments. 14type Parser struct { 15 glyphs []byte 16 oldGlyphs []byte 17 flows []int64 18 oldFlows []int64 19 maxFlow int64 20 colors []int 21 oldColors []int 22 availableColors []int 23 nextAvailable int 24 firstInUse int 25 firstAvailable int 26 maxAllowedColors int 27} 28 29// Reset resets the internal parser state. 30func (parser *Parser) Reset() { 31 parser.glyphs = parser.glyphs[0:0] 32 parser.oldGlyphs = parser.oldGlyphs[0:0] 33 parser.flows = parser.flows[0:0] 34 parser.oldFlows = parser.oldFlows[0:0] 35 parser.maxFlow = 0 36 parser.colors = parser.colors[0:0] 37 parser.oldColors = parser.oldColors[0:0] 38 parser.availableColors = parser.availableColors[0:0] 39 parser.availableColors = append(parser.availableColors, 1, 2) 40 parser.nextAvailable = 0 41 parser.firstInUse = -1 42 parser.firstAvailable = 0 43 parser.maxAllowedColors = 0 44} 45 46// AddLineToGraph adds the line as a row to the graph 47func (parser *Parser) AddLineToGraph(graph *Graph, row int, line []byte) error { 48 idx := bytes.Index(line, []byte("DATA:")) 49 if idx < 0 { 50 parser.ParseGlyphs(line) 51 } else { 52 parser.ParseGlyphs(line[:idx]) 53 } 54 55 var err error 56 commitDone := false 57 58 for column, glyph := range parser.glyphs { 59 if glyph == ' ' { 60 continue 61 } 62 63 flowID := parser.flows[column] 64 65 graph.AddGlyph(row, column, flowID, parser.colors[column], glyph) 66 67 if glyph == '*' { 68 if commitDone { 69 if err != nil { 70 err = fmt.Errorf("double commit on line %d: %s. %w", row, string(line), err) 71 } else { 72 err = fmt.Errorf("double commit on line %d: %s", row, string(line)) 73 } 74 } 75 commitDone = true 76 if idx < 0 { 77 if err != nil { 78 err = fmt.Errorf("missing data section on line %d with commit: %s. %w", row, string(line), err) 79 } else { 80 err = fmt.Errorf("missing data section on line %d with commit: %s", row, string(line)) 81 } 82 continue 83 } 84 err2 := graph.AddCommit(row, column, flowID, line[idx+5:]) 85 if err != nil && err2 != nil { 86 err = fmt.Errorf("%v %w", err2, err) 87 continue 88 } else if err2 != nil { 89 err = err2 90 continue 91 } 92 } 93 } 94 if !commitDone { 95 graph.Commits = append(graph.Commits, RelationCommit) 96 } 97 return err 98} 99 100func (parser *Parser) releaseUnusedColors() { 101 if parser.firstInUse > -1 { 102 // Here we step through the old colors, searching for them in the 103 // "in-use" section of availableColors (that is, the colors between 104 // firstInUse and firstAvailable) 105 // Ensure that the benchmarks are not worsened with proposed changes 106 stepstaken := 0 107 position := parser.firstInUse 108 for _, color := range parser.oldColors { 109 if color == 0 { 110 continue 111 } 112 found := false 113 i := position 114 for j := stepstaken; i != parser.firstAvailable && j < len(parser.availableColors); j++ { 115 colorToCheck := parser.availableColors[i] 116 if colorToCheck == color { 117 found = true 118 break 119 } 120 i = (i + 1) % len(parser.availableColors) 121 } 122 if !found { 123 // Duplicate color 124 continue 125 } 126 // Swap them around 127 parser.availableColors[position], parser.availableColors[i] = parser.availableColors[i], parser.availableColors[position] 128 stepstaken++ 129 position = (parser.firstInUse + stepstaken) % len(parser.availableColors) 130 if position == parser.firstAvailable || stepstaken == len(parser.availableColors) { 131 break 132 } 133 } 134 if stepstaken == len(parser.availableColors) { 135 parser.firstAvailable = -1 136 } else { 137 parser.firstAvailable = position 138 if parser.nextAvailable == -1 { 139 parser.nextAvailable = parser.firstAvailable 140 } 141 } 142 } 143} 144 145// ParseGlyphs parses the provided glyphs and sets the internal state 146func (parser *Parser) ParseGlyphs(glyphs []byte) { 147 148 // Clean state for parsing this row 149 parser.glyphs, parser.oldGlyphs = parser.oldGlyphs, parser.glyphs 150 parser.glyphs = parser.glyphs[0:0] 151 parser.flows, parser.oldFlows = parser.oldFlows, parser.flows 152 parser.flows = parser.flows[0:0] 153 parser.colors, parser.oldColors = parser.oldColors, parser.colors 154 155 // Ensure we have enough flows and colors 156 parser.colors = parser.colors[0:0] 157 for range glyphs { 158 parser.flows = append(parser.flows, 0) 159 parser.colors = append(parser.colors, 0) 160 } 161 162 // Copy the provided glyphs in to state.glyphs for safekeeping 163 parser.glyphs = append(parser.glyphs, glyphs...) 164 165 // release unused colors 166 parser.releaseUnusedColors() 167 168 for i := len(glyphs) - 1; i >= 0; i-- { 169 glyph := glyphs[i] 170 switch glyph { 171 case '|': 172 fallthrough 173 case '*': 174 parser.setUpFlow(i) 175 case '/': 176 parser.setOutFlow(i) 177 case '\\': 178 parser.setInFlow(i) 179 case '_': 180 parser.setRightFlow(i) 181 case '.': 182 fallthrough 183 case '-': 184 parser.setLeftFlow(i) 185 case ' ': 186 // no-op 187 default: 188 parser.newFlow(i) 189 } 190 } 191} 192 193func (parser *Parser) takePreviousFlow(i, j int) { 194 if j < len(parser.oldFlows) && parser.oldFlows[j] > 0 { 195 parser.flows[i] = parser.oldFlows[j] 196 parser.oldFlows[j] = 0 197 parser.colors[i] = parser.oldColors[j] 198 parser.oldColors[j] = 0 199 } else { 200 parser.newFlow(i) 201 } 202} 203 204func (parser *Parser) takeCurrentFlow(i, j int) { 205 if j < len(parser.flows) && parser.flows[j] > 0 { 206 parser.flows[i] = parser.flows[j] 207 parser.colors[i] = parser.colors[j] 208 } else { 209 parser.newFlow(i) 210 } 211} 212 213func (parser *Parser) newFlow(i int) { 214 parser.maxFlow++ 215 parser.flows[i] = parser.maxFlow 216 217 // Now give this flow a color 218 if parser.nextAvailable == -1 { 219 next := len(parser.availableColors) 220 if parser.maxAllowedColors < 1 || next < parser.maxAllowedColors { 221 parser.nextAvailable = next 222 parser.firstAvailable = next 223 parser.availableColors = append(parser.availableColors, next+1) 224 } 225 } 226 parser.colors[i] = parser.availableColors[parser.nextAvailable] 227 if parser.firstInUse == -1 { 228 parser.firstInUse = parser.nextAvailable 229 } 230 parser.availableColors[parser.firstAvailable], parser.availableColors[parser.nextAvailable] = parser.availableColors[parser.nextAvailable], parser.availableColors[parser.firstAvailable] 231 232 parser.nextAvailable = (parser.nextAvailable + 1) % len(parser.availableColors) 233 parser.firstAvailable = (parser.firstAvailable + 1) % len(parser.availableColors) 234 235 if parser.nextAvailable == parser.firstInUse { 236 parser.nextAvailable = parser.firstAvailable 237 } 238 if parser.nextAvailable == parser.firstInUse { 239 parser.nextAvailable = -1 240 parser.firstAvailable = -1 241 } 242} 243 244// setUpFlow handles '|' or '*' 245func (parser *Parser) setUpFlow(i int) { 246 // In preference order: 247 // 248 // Previous Row: '\? ' ' |' ' /' 249 // Current Row: ' | ' ' |' ' | ' 250 if i > 0 && i-1 < len(parser.oldGlyphs) && parser.oldGlyphs[i-1] == '\\' { 251 parser.takePreviousFlow(i, i-1) 252 } else if i < len(parser.oldGlyphs) && (parser.oldGlyphs[i] == '|' || parser.oldGlyphs[i] == '*') { 253 parser.takePreviousFlow(i, i) 254 } else if i+1 < len(parser.oldGlyphs) && parser.oldGlyphs[i+1] == '/' { 255 parser.takePreviousFlow(i, i+1) 256 } else { 257 parser.newFlow(i) 258 } 259} 260 261// setOutFlow handles '/' 262func (parser *Parser) setOutFlow(i int) { 263 // In preference order: 264 // 265 // Previous Row: ' |/' ' |_' ' |' ' /' ' _' '\' 266 // Current Row: '/| ' '/| ' '/ ' '/ ' '/ ' '/' 267 if i+2 < len(parser.oldGlyphs) && 268 (parser.oldGlyphs[i+1] == '|' || parser.oldGlyphs[i+1] == '*') && 269 (parser.oldGlyphs[i+2] == '/' || parser.oldGlyphs[i+2] == '_') && 270 i+1 < len(parser.glyphs) && 271 (parser.glyphs[i+1] == '|' || parser.glyphs[i+1] == '*') { 272 parser.takePreviousFlow(i, i+2) 273 } else if i+1 < len(parser.oldGlyphs) && 274 (parser.oldGlyphs[i+1] == '|' || parser.oldGlyphs[i+1] == '*' || 275 parser.oldGlyphs[i+1] == '/' || parser.oldGlyphs[i+1] == '_') { 276 parser.takePreviousFlow(i, i+1) 277 if parser.oldGlyphs[i+1] == '/' { 278 parser.glyphs[i] = '|' 279 } 280 } else if i < len(parser.oldGlyphs) && parser.oldGlyphs[i] == '\\' { 281 parser.takePreviousFlow(i, i) 282 } else { 283 parser.newFlow(i) 284 } 285} 286 287// setInFlow handles '\' 288func (parser *Parser) setInFlow(i int) { 289 // In preference order: 290 // 291 // Previous Row: '| ' '-. ' '| ' '\ ' '/' '---' 292 // Current Row: '|\' ' \' ' \' ' \' '\' ' \ ' 293 if i > 0 && i-1 < len(parser.oldGlyphs) && 294 (parser.oldGlyphs[i-1] == '|' || parser.oldGlyphs[i-1] == '*') && 295 (parser.glyphs[i-1] == '|' || parser.glyphs[i-1] == '*') { 296 parser.newFlow(i) 297 } else if i > 0 && i-1 < len(parser.oldGlyphs) && 298 (parser.oldGlyphs[i-1] == '|' || parser.oldGlyphs[i-1] == '*' || 299 parser.oldGlyphs[i-1] == '.' || parser.oldGlyphs[i-1] == '\\') { 300 parser.takePreviousFlow(i, i-1) 301 if parser.oldGlyphs[i-1] == '\\' { 302 parser.glyphs[i] = '|' 303 } 304 } else if i < len(parser.oldGlyphs) && parser.oldGlyphs[i] == '/' { 305 parser.takePreviousFlow(i, i) 306 } else { 307 parser.newFlow(i) 308 } 309} 310 311// setRightFlow handles '_' 312func (parser *Parser) setRightFlow(i int) { 313 // In preference order: 314 // 315 // Current Row: '__' '_/' '_|_' '_|/' 316 if i+1 < len(parser.glyphs) && 317 (parser.glyphs[i+1] == '_' || parser.glyphs[i+1] == '/') { 318 parser.takeCurrentFlow(i, i+1) 319 } else if i+2 < len(parser.glyphs) && 320 (parser.glyphs[i+1] == '|' || parser.glyphs[i+1] == '*') && 321 (parser.glyphs[i+2] == '_' || parser.glyphs[i+2] == '/') { 322 parser.takeCurrentFlow(i, i+2) 323 } else { 324 parser.newFlow(i) 325 } 326} 327 328// setLeftFlow handles '----.' 329func (parser *Parser) setLeftFlow(i int) { 330 if parser.glyphs[i] == '.' { 331 parser.newFlow(i) 332 } else if i+1 < len(parser.glyphs) && 333 (parser.glyphs[i+1] == '-' || parser.glyphs[i+1] == '.') { 334 parser.takeCurrentFlow(i, i+1) 335 } else { 336 parser.newFlow(i) 337 } 338} 339