//go:generate re2go $INPUT -o $OUTPUT
package main

import "reflect"

const (
	mtagRoot int = -1
	tagNone int = -1
)

// An m-tag tree is a way to store histories with an O(1) copy operation.
// Histories naturally form a tree, as they have common start and fork at some
// point. The tree is stored as an array of pairs (tag value, link to parent).
// An m-tag is represented with a single link in the tree (array index).
type mtagElem struct {
	elem int
	pred int
}
type mtagTrie = []mtagElem

type Ver = []int // unbounded number of version components

func s2n(s string) int { // convert pre-parsed string to a number
	n := 0
	for _, c := range s { n = n*10 + int(c-'0') }
	return n
}

// Append a single value to an m-tag history.
func add_mtag(trie *mtagTrie, mtag int, value int) int {
	*trie = append(*trie, mtagElem{value, mtag})
	return len(*trie) - 1
}

// Recursively unwind tag histories and collect version components.
func unwind(trie mtagTrie, x int, y int, str string) Ver {
	// Reached the root of the m-tag tree, stop recursion.
	if x == mtagRoot && y == mtagRoot {
		return []int{}
	}

	// Unwind history further.
	ver := unwind(trie, trie[x].pred, trie[y].pred, str)

	// Get tag values. Tag histories must have equal length.
	if x == mtagRoot || y == mtagRoot {
		panic("tag histories have different length")
	}
	ex := trie[x].elem
	ey := trie[y].elem

	if ex != tagNone && ey != tagNone {
		// Both tags are valid string indices, extract component.
		ver = append(ver, s2n(str[ex:ey]))
	} else if !(ex == tagNone && ey == tagNone) {
		panic("both tags should be tagNone")
	}
	return ver
}

func parse(str string) []int {
	var cur, mar int
	trie := make([]mtagElem, 0)

	// User-defined tag variables that are available in semantic action.
	var t1, t2, t3, t4 int

	// Autogenerated tag variables used by the lexer to track tag values.
	/*!stags:re2c format = 'var @@ int'; separator = "\n\t"; */
	/*!mtags:re2c format = "\t@@ := mtagRoot\n"; */

	/*!re2c
		re2c:tags = 1;
		re2c:yyfill:enable = 0;
		re2c:define:YYCTYPE   = byte;
		re2c:define:YYPEEK    = "str[cur]";
		re2c:define:YYSKIP    = "cur += 1";
		re2c:define:YYBACKUP  = "mar = cur";
		re2c:define:YYRESTORE = "cur = mar";
		re2c:define:YYSTAGP   = "@@ = cur";
		re2c:define:YYSTAGN   = "@@ = tagNone";
		re2c:define:YYMTAGP   = "@@ = add_mtag(&trie, @@, cur)";
		re2c:define:YYMTAGN   = "@@ = add_mtag(&trie, @@, tagNone)";

		num = [0-9]+;

		@t1 num @t2 ("." #t3 num #t4)* [\x00] {
			ver := make([]int, 0)
			ver = append(ver, s2n(str[t1:t2]))
			ver = append(ver, unwind(trie, t3, t4, str)...)
			return ver
		}
		* { return nil }
	*/
}

func main() {
	assert_eq := func(x, y []int) {
		if !reflect.DeepEqual(x, y) { panic("error") }
	}
	assert_eq(parse("1\000"), []int{1})
	assert_eq(parse("1.2.3.4.5.6.7\000"), []int{1, 2, 3, 4, 5, 6, 7})
	assert_eq(parse("1.\000"), nil)
}