1 files changed, 182 insertions, 0 deletions
diff --git a/grammar/lexical/dfa/symbol_position.go b/grammar/lexical/dfa/symbol_position.go
new file mode 100644
index 0000000..f154251
--- /dev/null
+++ b/grammar/lexical/dfa/symbol_position.go
@@ -0,0 +1,182 @@
+package dfa
+
+import (
+	"encoding/binary"
+	"fmt"
+	"strings"
+)
+
+type symbolPosition uint16
+
+const (
+	symbolPositionNil symbolPosition = 0x0000
+
+	symbolPositionMin uint16 = 0x0001
+	symbolPositionMax uint16 = 0x7fff
+
+	symbolPositionMaskSymbol  uint16 = 0x0000
+	symbolPositionMaskEndMark uint16 = 0x8000
+
+	symbolPositionMaskValue uint16 = 0x7fff
+)
+
+func newSymbolPosition(n uint16, endMark bool) (symbolPosition, error) {
+	if n < symbolPositionMin || n > symbolPositionMax {
+		return symbolPositionNil, fmt.Errorf("symbol position must be within %v to %v: n: %v, endMark: %v", symbolPositionMin, symbolPositionMax, n, endMark)
+	}
+	if endMark {
+		return symbolPosition(n | symbolPositionMaskEndMark), nil
+	}
+	return symbolPosition(n | symbolPositionMaskSymbol), nil
+}
+
+func (p symbolPosition) String() string {
+	if p.isEndMark() {
+		return fmt.Sprintf("end#%v", uint16(p)&symbolPositionMaskValue)
+	}
+	return fmt.Sprintf("sym#%v", uint16(p)&symbolPositionMaskValue)
+}
+
+func (p symbolPosition) isEndMark() bool {
+	return uint16(p)&symbolPositionMaskEndMark > 1
+}
+
+func (p symbolPosition) describe() (uint16, bool) {
+	v := uint16(p) & symbolPositionMaskValue
+	if p.isEndMark() {
+		return v, true
+	}
+	return v, false
+}
+
+type symbolPositionSet struct {
+	// `s` represents a set of symbol positions.
+	// However, immediately after adding a symbol position, the elements may be duplicated.
+	// When you need an aligned set with no duplicates, you can get such value via the set function.
+	s      []symbolPosition
+	sorted bool
+}
+
+func newSymbolPositionSet() *symbolPositionSet {
+	return &symbolPositionSet{
+		s:      []symbolPosition{},
+		sorted: false,
+	}
+}
+
+func (s *symbolPositionSet) String() string {
+	if len(s.s) <= 0 {
+		return "{}"
+	}
+	ps := s.sortAndRemoveDuplicates()
+	var b strings.Builder
+	fmt.Fprintf(&b, "{")
+	for i, p := range ps {
+		if i <= 0 {
+			fmt.Fprintf(&b, "%v", p)
+			continue
+		}
+		fmt.Fprintf(&b, ", %v", p)
+	}
+	fmt.Fprintf(&b, "}")
+	return b.String()
+}
+
+func (s *symbolPositionSet) set() []symbolPosition {
+	s.sortAndRemoveDuplicates()
+	return s.s
+}
+
+func (s *symbolPositionSet) add(pos symbolPosition) *symbolPositionSet {
+	s.s = append(s.s, pos)
+	s.sorted = false
+	return s
+}
+
+func (s *symbolPositionSet) merge(t *symbolPositionSet) *symbolPositionSet {
+	s.s = append(s.s, t.s...)
+	s.sorted = false
+	return s
+}
+
+func (s *symbolPositionSet) hash() string {
+	if len(s.s) <= 0 {
+		return ""
+	}
+	sorted := s.sortAndRemoveDuplicates()
+	var buf []byte
+	for _, p := range sorted {
+		b := make([]byte, 8)
+		binary.PutUvarint(b, uint64(p))
+		buf = append(buf, b...)
+	}
+	// Convert to a string to be able to use it as a key of a map.
+	// But note this byte sequence is made from values of symbol positions,
+	// so this is not a well-formed UTF-8 sequence.
+	return string(buf)
+}
+
+func (s *symbolPositionSet) sortAndRemoveDuplicates() []symbolPosition {
+	if s.sorted {
+		return s.s
+	}
+
+	sortSymbolPositions(s.s, 0, len(s.s)-1)
+
+	// Remove duplicates.
+	lastV := s.s[0]
+	nextIdx := 1
+	for _, v := range s.s[1:] {
+		if v == lastV {
+			continue
+		}
+		s.s[nextIdx] = v
+		nextIdx++
+		lastV = v
+	}
+	s.s = s.s[:nextIdx]
+	s.sorted = true
+
+	return s.s
+}
+
+// sortSymbolPositions sorts a slice of symbol positions as it uses quick sort.
+func sortSymbolPositions(ps []symbolPosition, left, right int) {
+	if left >= right {
+		return
+	}
+	var pivot symbolPosition
+	{
+		// Use a median as a pivot.
+		p1 := ps[left]
+		p2 := ps[(left+right)/2]
+		p3 := ps[right]
+		if p1 > p2 {
+			p1, p2 = p2, p1
+		}
+		if p2 > p3 {
+			p2 = p3
+			if p1 > p2 {
+				p2 = p1
+			}
+		}
+		pivot = p2
+	}
+	i := left
+	j := right
+	for i <= j {
+		for ps[i] < pivot {
+			i++
+		}
+		for ps[j] > pivot {
+			j--
+		}
+		if i <= j {
+			ps[i], ps[j] = ps[j], ps[i]
+			i++
+			j--
+		}
+	}
+	sortSymbolPositions(ps, left, j)
+	sortSymbolPositions(ps, i, right)
+}