aboutsummaryrefslogtreecommitdiff
path: root/compiler/symbol_position.go
diff options
context:
space:
mode:
authorRyo Nihei <nihei.dev@gmail.com>2021-12-09 02:38:12 +0900
committerRyo Nihei <nihei.dev@gmail.com>2021-12-10 01:50:32 +0900
commitd595194791483a71c5afaff2aa3f4b575a9d22b7 (patch)
tree65477d9fab1db2b9ded5eeda8a14ce0b235718b5 /compiler/symbol_position.go
parentAdd a new DFA compiler that generates DFA from a set of CPTree (diff)
downloadtre-d595194791483a71c5afaff2aa3f4b575a9d22b7.tar.gz
tre-d595194791483a71c5afaff2aa3f4b575a9d22b7.tar.xz
Use new parser and DFA compiler
Diffstat (limited to '')
-rw-r--r--compiler/symbol_position.go198
1 files changed, 0 insertions, 198 deletions
diff --git a/compiler/symbol_position.go b/compiler/symbol_position.go
deleted file mode 100644
index d35dfde..0000000
--- a/compiler/symbol_position.go
+++ /dev/null
@@ -1,198 +0,0 @@
-package compiler
-
-import (
- "encoding/binary"
- "fmt"
- "strings"
-)
-
-type symbolPosition uint16
-
-const (
- symbolPositionNil = symbolPosition(0x0000) // 0000 0000 0000 0000
-
- symbolPositionMin = uint16(0x0001) // 0000 0000 0000 0001
- symbolPositionMax = uint16(0x7fff) // 0111 1111 1111 1111
-
- symbolPositionMaskSymbol = uint16(0x0000) // 0000 0000 0000 0000
- symbolPositionMaskEndMark = uint16(0x8000) // 1000 0000 0000 0000
-
- symbolPositionMaskValue = uint16(0x7fff) // 0111 1111 1111 1111
-)
-
-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 {
- if uint16(p)&symbolPositionMaskEndMark > 1 {
- return true
- }
- return false
-}
-
-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) intersect(set *symbolPositionSet) *symbolPositionSet {
- in := newSymbolPositionSet()
- for _, p1 := range s.s {
- for _, p2 := range set.s {
- if p1 != p2 {
- continue
- }
- in.add(p1)
- }
- }
- return in
-}
-
-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 = p3, p2
- if p1 > p2 {
- 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)
-}