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