diff options
| -rw-r--r-- | main/main_test.go | 40 | ||||
| -rw-r--r-- | subex/arithmetic.go | 203 | ||||
| -rw-r--r-- | subex/filter.go | 171 | ||||
| -rw-r--r-- | subex/lex.go | 3 | ||||
| -rw-r--r-- | subex/main.go | 4 | ||||
| -rw-r--r-- | subex/main_test.go | 121 | ||||
| -rw-r--r-- | subex/parse.go | 661 | ||||
| -rw-r--r-- | subex/subexast.go | 311 | ||||
| -rw-r--r-- | subex/subexstate.go | 21 |
9 files changed, 1158 insertions, 377 deletions
diff --git a/main/main_test.go b/main/main_test.go index 076693d..802d248 100644 --- a/main/main_test.go +++ b/main/main_test.go @@ -21,133 +21,133 @@ func TestSpecificCases(t *testing.T) { tests := []test { { name: "Verbose Extract", - program: `s/#(~(people)~$_@(1$_#(~(first_name)~$_.|(..$_){-0})-|(..$_){-0})-|(..$_){-0})-/p`, + program: `s/#(~(people)~>_@(1>_#(~(first_name)~>_.|(..)>_*)-|(..)>_*)-|(..)>_*)-/p`, quiet: true, input: miscInput, expected: `"Tom"`, }, { name: "Extract", - program: `s/#("people"$_ @(1 $_#("first_name"$_ .)-)-)-/p`, + program: `s/#("people">_ @(1>_#("first_name">_ .)-)-)-/p`, quiet: true, input: miscInput, expected: `"Tom"`, }, { name: "Simple Extract", - program: "s/#(\"people\" @(1 #(\"first_name\" (.$a))-)-)-$_ `$a`/p", + program: "s/#(\"people\" @(1 #(\"first_name\" (.>a))-)-)->_ <a/p", quiet: true, input: miscInput, expected: `"Tom"`, }, { name: "Larger Extract", - program: "s/#(\"people\" @(2 (.$a))-)-$_ `$a`/p", + program: "s/#(\"people\" @(2 (.>a))-)->_ `<a`/p", quiet: true, input: miscInput, expected: `{"first_name":"Charlie","last_name":"Chaplin","age":122}`, }, { name: "Extract ages", - program: "s/#(\"people\"$_ :(#(\"age\"$_ .)-):)-/p", + program: "s/#(\"people\">_ :(#(\"age\">_ .)-):)-/p", quiet: true, input: miscInput, expected: `[22,18,122,48]`, }, { name: "Low memory count people", - program: "aX/#(\"people\" :(#()#):)#$_ `1`/o es/#()#/{ xs/.{-0}+/p }", + program: "aX/#(\"people\" :(#()#):)#>_ `1`/o es/#()#/{ xs/.*%+/p }", quiet: true, input: miscInput, expected: "4", }, { name: "Get full names", - program: "s/#(\"people\"$_ .)-/{ s/:():/p as/:(#()#):/{ xdx } s/:(#((\"first_name\" | \"last_name\") .)#)-/X es/@(.#()-)-/{ xs/(#(\"first_name\" \".{-0}$a\")# | #(\"last_name\" \".{-0}$b\")# | .){-0}$_ `\"$a $b\"`/Xxs/-(..)@/p } }", + program: "s/#(\"people\">_ .)-/{ s/:():/p as/:(#()#):/{ xdx } s/:(#((\"first_name\"|\"last_name\") .)#)-/X es/@(.#()-)-/{ xs/(#(\"first_name\"\".*>a\")#|#(\"last_name\"\".*>b\")#|.)*>_`\"<a <b\"`/Xxs/-(..)@/p } }", quiet: true, input: miscInput, expected: `["Charlie Johnson","Tom Johnson","Charlie Chaplin","John Johnson"]`, }, { name: "Get full names 2", - program: "s/#(\"people\"$_ .)-/{ s/:():/p as/:(#()#):/{ xdx } X/:(#((\"first_name\" | \"last_name\") .)#)-/o es/@(.#()-)-/{ xX/(#(\"first_name\" \".{-0}$a\")# | #(\"last_name\" \".{-0}$b\")# | .){-0}$_ `\"$a $b\"`/xs/-(..)@/p } }", + program: "s/#(\"people\">_.)-/{ s/:():/p as/:(#()#):/{ xdx } X/:(#((\"first_name\"|\"last_name\") .)#)-/o es/@(.#()-)-/{ xX/(#(\"first_name\"\".*>a\")#|#(\"last_name\"\".*>b\")#|.)*_`\"<a <b\"`/xs/-(..)@/p } }", quiet: true, input: miscInput, expected: `["Charlie Johnson","Tom Johnson","Charlie Chaplin","John Johnson"]`, }, { name: "Change full names in place", - program: "s/#(\"people\" @(. #(\"first_name\" .)#)@)#/{ Nms/#(\"people\" @(. (#(\"first_name\" \".{-0}$a\" \"last_name\" \".{-0}$b\")#$_) `#(\"name\" \"$a $b\")#`)@)#/ }", + program: "s/#(\"people\"@(.#(\"first_name\".)#)@)#/{ Nms/#(\"people\"@(.(#(\"first_name\"\".*>a\"\"last_name\"\".*>b\")#_)`#(\"name\"\"<a <b\")#`)@)#/ }", input: miscInput, expected: `{"something":{"nested":"Here is my test value"},"array":["Hello","world","these","are","values"],"people":[{"name":"Charlie Johnson","age":22},{"name":"Tom Johnson","age":18},{"name":"Charlie Chaplin","age":122},{"name":"John Johnson","age":48}]}`, }, { name: "Get full names with substitute next command", - program: "s/#( \"people\"$_ :( #( \"first_name\"$_ . )- )- )-/{ N/#( \"people\"$_ :( #( \"last_name\"$_ . )- )- )-/{ s/-( -( ~(.{-0}` `)- ~(.{-0})- )~ ):/p }}", + program: "s/#(\"people\"_:(#(\"first_name\"_.)-)-)-/{ N/#(\"people\"_:(#(\"last_name\"_.)-)-)-/{ s/-(-(~(.*` `)-~(.*)-)~):/p }}", quiet: true, input: miscInput, expected: `["Charlie Johnson","Tom Johnson","Charlie Chaplin","John Johnson"]`, }, { name: "Get full names with merge full command", - program: "s/#(\"people\"$_ :(): )-/p M/#( \"people\" @( . #()# )@ )#/{ s/#( \"people\"$_ @( . #[ \"first_name\" \".{-0}$a\" | \"last_name\" \".{-0}$b\" | .. $_]- `\"$a $b\"` )@ )-/p }", + program: "s/#(\"people\"_:():)-/p M/#(\"people\"@(.#()#)@)#/{ s/#(\"people\"_@(.#[(\"first_name\"\".*>a\"|\"last_name\"\".*>b\"|..)_]-`\"<a <b\"`)@)-/p }", quiet: true, input: miscInput, expected: `["Charlie Johnson","Tom Johnson","Charlie Chaplin","John Johnson"]`, }, { name: "Verbose concat array values", - program: "as/#( \"array\"$_ :(): )-/{ :s N/#( .$_ . )-/{ es/.{-0}:():/be mbs } :em s/:( -( ~(.{-0}` `)-{-0} ~(.{-0})- )~ )-/p }", + program: "as/#(\"array\"_:():)-/{ :s N/#(._.)-/{ es/.*:():/be mbs } :em s/:(-(~(.*` `)-*~(.*)-)~)-/p }", quiet: true, input: miscInput, expected: `"Hello world these are values"`, }, { name: "Short concat array values", - program: "M/#( \"array\" :(): )#/{ s/#( \"array\"$_ :( .{-0} )- )-/ s/-( ~(.{-0}` `)-{-0} ~(.{-0})- )~/p }", + program: "M/#(\"array\":():)#/{ s/#(\"array\"_:(.*)-)-/ s/-(~(.*` `)-*~(.*)-)~/p }", quiet: true, input: miscInput, expected: `"Hello world these are values"`, }, { name: "Drop first element of array", - program: `s/#( "people" @( 0 . )@ )#/d`, + program: `s/#("people"@(0 .)@)#/d`, input: miscInput, expected: `{"something":{"nested":"Here is my test value"},"array":["Hello","world","these","are","values"],"people":[{"first_name":"Tom","last_name":"Johnson","age":18},{"first_name":"Charlie","last_name":"Chaplin","age":122},{"first_name":"John","last_name":"Johnson","age":48}]}`, }, { name: "Drop last element of array", - program: `M/#( "people" @( . , )@ )#/{ Ed }`, + program: `M/#("people"@(.,)@)#/{ Ed }`, input: miscInput, expected: `{"something":{"nested":"Here is my test value"},"array":["Hello","world","these","are","values"],"people":[{"first_name":"Charlie","last_name":"Johnson","age":22},{"first_name":"Tom","last_name":"Johnson","age":18},{"first_name":"Charlie","last_name":"Chaplin","age":122}]}`, }, { name: "Drop last element of simple array", - program: `s/#( "array" @( . . )@ )#/{ Ed }`, + program: `s/#("array"@(..)@)#/{ Ed }`, input: miscInput, expected: `{"something":{"nested":"Here is my test value"},"array":["Hello","world","these","are"],"people":[{"first_name":"Charlie","last_name":"Johnson","age":22},{"first_name":"Tom","last_name":"Johnson","age":18},{"first_name":"Charlie","last_name":"Chaplin","age":122},{"first_name":"John","last_name":"Johnson","age":48}]}`, }, { name: "Drop last element of mixed array", - program: `M/#( "array" @( . , )@ )#/{ Ed }`, + program: `M/#("array"@(.,)@)#/{ Ed }`, input: mixedArray, expected: `{"array":["first",null,3,{"name":"second"}]}`, }, { name: "Drop last element of mixed array 2", - program: `M/#( "array" @( . , )@ )#/{ Ed }`, + program: `M/#("array"@(.,)@)#/{ Ed }`, input: mixedArray2, expected: `{"array":["first",null,3,"second"]}`, }, { name: "Prepend to array", - program: "as/#( \"array\" :( `\"First\"` ): )#/", + program: "as/#(\"array\":(`\"First\"`):)#/", input: miscInput, expected: `{"something":{"nested":"Here is my test value"},"array":["First","Hello","world","these","are","values"],"people":[{"first_name":"Charlie","last_name":"Johnson","age":22},{"first_name":"Tom","last_name":"Johnson","age":18},{"first_name":"Charlie","last_name":"Chaplin","age":122},{"first_name":"John","last_name":"Johnson","age":48}]}`, }, { name: "Append to array", - program: "es/#( \"array\" :( `\"Last\"` ): )#/", + program: "es/#(\"array\":(`\"Last\"`):)#/", input: miscInput, expected: `{"something":{"nested":"Here is my test value"},"array":["Hello","world","these","are","values","Last"],"people":[{"first_name":"Charlie","last_name":"Johnson","age":22},{"first_name":"Tom","last_name":"Johnson","age":18},{"first_name":"Charlie","last_name":"Chaplin","age":122},{"first_name":"John","last_name":"Johnson","age":48}]}`, }, diff --git a/subex/arithmetic.go b/subex/arithmetic.go index 4c87d5f..5e0eb44 100644 --- a/subex/arithmetic.go +++ b/subex/arithmetic.go @@ -3,171 +3,84 @@ package subex import ( "main/walk" "errors" - "strconv" ) -func sumValues(values []walk.Value) ([]walk.Value, error) { - allBools := true - var sum float64 = 0 - var any bool = false - for _, value := range values { - switch v := value.(type) { - case walk.NullValue: - allBools = false - case walk.BoolValue: - if v { - sum += 1 - any = true - } - case walk.NumberValue: - allBools = false - sum += float64(v) - case walk.StringValue: - allBools = false - num, err := strconv.ParseFloat(string(v), 64) - if err == nil { - sum += num - } else { - return nil, errors.New("Tried to sum non-castable string") - } - default: - return nil, errors.New("Tried to sum non-number") - } +func binopAdd(values []walk.Value) ([]walk.Value, error) { + if len(values) != 2 { + return nil, errors.New("Tried to sum a weird number of values") + } + + lhs, lhsIsNumber := values[0].(walk.NumberValue) + if !lhsIsNumber { + return nil, errors.New("Tried to sum a lhs that is not a number") } - if allBools { - return []walk.Value{walk.BoolValue(any)}, nil - } else { - return []walk.Value{walk.NumberValue(sum)}, nil + + rhs, rhsIsNumber := values[1].(walk.NumberValue) + if !rhsIsNumber { + return nil, errors.New("Tried to sum a rhs that is not a number") } + + return []walk.Value{walk.NumberValue(float64(lhs) + float64(rhs))}, nil } -// Compounds atoms into values, if all values are booleans, does AND, if not, tries to cast to numbers and multiply -func multiplyValues(values []walk.Value) ([]walk.Value, error) { - allBools := true - var product float64 = 1 - var all bool = false - for _, value := range values { - switch v := value.(type) { - case walk.NullValue: - allBools = false - product *= 0 - case walk.BoolValue: - if !v { - product *= 0 - all = false - } - case walk.NumberValue: - allBools = false - product *= float64(v) - case walk.StringValue: - allBools = false - num, err := strconv.ParseFloat(string(v), 64) - if err == nil { - product *= num - } else { - return nil, errors.New("Tried to multiply non-castable string") - } - default: - return nil, errors.New("Tried to multiply non-number") - } +func binopMultiply(values []walk.Value) ([]walk.Value, error) { + if len(values) != 2 { + return nil, errors.New("Tried to multiply a weird number of values") } - if allBools { - return []walk.Value{walk.BoolValue(all)}, nil - } else { - return []walk.Value{walk.NumberValue(product)}, nil + + lhs, lhsIsNumber := values[0].(walk.NumberValue) + if !lhsIsNumber { + return nil, errors.New("Tried to multiply a lhs that is not a number") } -} -// Does tries to cast all to numbers and negates them -func negateValues(values []walk.Value) ([]walk.Value, error) { - var negatedNumbers []walk.Value - for _, value := range values { - switch v := value.(type) { - case walk.NullValue: - negatedNumbers = append(negatedNumbers, walk.NumberValue(0)) - case walk.BoolValue: - if v { - negatedNumbers = append(negatedNumbers, walk.NumberValue(-1)) - } else { - negatedNumbers = append(negatedNumbers, walk.NumberValue(0)) - } - case walk.NumberValue: - negatedNumbers = append(negatedNumbers, walk.NumberValue(-float64(v))) - case walk.StringValue: - num, err := strconv.ParseFloat(string(v), 64) - if err == nil { - negatedNumbers = append(negatedNumbers, walk.NumberValue(-num)) - } else { - return nil, errors.New("Tried to negate non-castable string") - } - default: - return nil, errors.New("Tried to negate non-number") - } + rhs, rhsIsNumber := values[1].(walk.NumberValue) + if !rhsIsNumber { + return nil, errors.New("Tried to multiply a rhs that is not a number") } - return negatedNumbers, nil + + return []walk.Value{walk.NumberValue(float64(lhs) * float64(rhs))}, nil } -// If all are castable to numbers, takes reciprocals of all and returns them -// Else errors -func reciprocalValues(values []walk.Value) ([]walk.Value, error) { - var reciprocals []walk.Value - for _, value := range values { - switch v := value.(type) { - case walk.NullValue: - return nil, errors.New("Tried to take reciprocal of null") - case walk.BoolValue: - if v { - reciprocals = append(reciprocals, walk.NumberValue(1)) - } else { - return nil, errors.New("Tried to take reciprocal of false") - } - case walk.NumberValue: - reciprocals = append(reciprocals, walk.NumberValue(1 / float64(v))) - case walk.StringValue: - num, err := strconv.ParseFloat(string(v), 64) - if err == nil { - reciprocals = append(reciprocals, walk.NumberValue(1 / num)) - } else { - return nil, errors.New("Tried to take reciprocal of non-castable string") - } - default: - return nil, errors.New("Tried to take reciprocal of non-number") - } +func binopDivide(values []walk.Value) ([]walk.Value, error) { + if len(values) != 2 { + return nil, errors.New("Tried to divide a weird number of values") + } + + lhs, lhsIsNumber := values[0].(walk.NumberValue) + if !lhsIsNumber { + return nil, errors.New("Tried to divide a lhs that is not a number") + } + + rhs, rhsIsNumber := values[1].(walk.NumberValue) + if !rhsIsNumber { + return nil, errors.New("Tried to divide a rhs that is not a number") } - return reciprocals, nil + + return []walk.Value{walk.NumberValue(float64(lhs) / float64(rhs))}, nil } -// If all are castable to booleans, NOTs all and returns them -// Else errors -func notValues(values []walk.Value) (notted []walk.Value, err error) { +func arithmeticSum(values []walk.Value) ([]walk.Value, error) { + var total float64 = 0 for _, value := range values { - switch v := value.(type) { - case walk.NullValue: - notted = append(notted, walk.BoolValue(true)) - case walk.BoolValue: - notted = append(notted, walk.BoolValue(!bool(v))) - case walk.NumberValue: - notted = append(notted, walk.BoolValue(v == 0)) - case walk.StringValue: - notted = append(notted, walk.BoolValue(len(v) == 0)) - default: - return nil, errors.New("Tried to NOT non-boolean") + n, isNumber := value.(walk.NumberValue) + if !isNumber { + return nil, errors.New("Tried to sum non-number value") } + total += float64(n) } - return notted, nil + + return []walk.Value{walk.NumberValue(total)}, nil } -// Returns true if all values are equal, false if not -func equalValues(values []walk.Value) ([]walk.Value, error) { - if len(values) == 0 { - return []walk.Value{walk.BoolValue(true)}, nil - } - first := values[0] - for _, value := range values[1:] { - // TODO: Refine the equality check - if value != first { - return []walk.Value{walk.BoolValue(false)}, nil +func arithmeticProduct(values []walk.Value) ([]walk.Value, error) { + var product float64 = 0 + for _, value := range values { + n, isNumber := value.(walk.NumberValue) + if !isNumber { + return nil, errors.New("Tried to sum non-number value") } + product *= float64(n) } - return []walk.Value{walk.BoolValue(true)}, nil + + return []walk.Value{walk.NumberValue(product)}, nil } diff --git a/subex/filter.go b/subex/filter.go index 309d6c7..87c83a4 100644 --- a/subex/filter.go +++ b/subex/filter.go @@ -2,6 +2,8 @@ package subex import ( "main/walk" + "math" + "fmt" ) type valueFilter interface { @@ -86,3 +88,172 @@ type selectRuneFilter struct { func (f selectRuneFilter) runeFilter(r rune) bool { return f.r == r } + +type numberFilter interface { + add(m float64) numberFilter + multiply(m float64) numberFilter + numberFilter(n float64) bool +} + +func (_ anyNumberFilter) numberFilter(n float64) bool { + return true +} +func (_ anyNumberFilter) add(m float64) numberFilter { + return anyNumberFilter{} +} +func (_ anyNumberFilter) multiply(m float64) numberFilter { + if m == 0.0 { + return equalNumberFilter {0.0} + } else { + return anyNumberFilter{} + } +} +func (_ anyNumberFilter) String() string { + return "r" +} + +type divisibleNumberFilter struct { + divisor float64 + target float64 +} +func (d divisibleNumberFilter) numberFilter(n float64) bool { + mod := math.Mod(n, d.divisor) + if mod < 0 { + mod += d.divisor + } + return mod == d.target +} +func (d divisibleNumberFilter) add(m float64) numberFilter { + mod := math.Mod(m + d.target, d.divisor) + if mod < 0 { + mod += d.divisor + } + return divisibleNumberFilter { + divisor: d.divisor, + target: mod, + } +} +func (d divisibleNumberFilter) multiply(m float64) numberFilter { + if m == 0.0 { + return equalNumberFilter {0.0} + } + + target := d.target + if m < 0 { + target = d.divisor - target + m = -m + } + + return divisibleNumberFilter { + divisor: d.divisor * m, + target: target * m, + } +} +func (d divisibleNumberFilter) String() string { + return fmt.Sprintf("(x %% %v == %v)", d.divisor, d.target) +} + +type andNumberFilter struct { + lhs, rhs numberFilter +} +func (a andNumberFilter) numberFilter(n float64) bool { + return a.lhs.numberFilter(n) && a.rhs.numberFilter(n) +} +func (a andNumberFilter) add(m float64) numberFilter { + return andNumberFilter { + lhs: a.lhs.add(m), + rhs: a.rhs.add(m), + } +} +func (a andNumberFilter) multiply(m float64) numberFilter { + return andNumberFilter { + lhs: a.lhs.multiply(m), + rhs: a.rhs.multiply(m), + } +} +func (a andNumberFilter) String() string { + return fmt.Sprintf("(%v && %v)", a.lhs, a.rhs) +} + +type orNumberFilter struct { + lhs, rhs numberFilter +} +func (o orNumberFilter) numberFilter(n float64) bool { + return o.lhs.numberFilter(n) || o.rhs.numberFilter(n) +} +func (o orNumberFilter) String() string { + return fmt.Sprintf("(%v || %v)", o.lhs, o.rhs) +} + +type notNumberFilter struct { + operand numberFilter +} +func (no notNumberFilter) numberFilter(n float64) bool { + return !no.operand.numberFilter(n) +} +func (no notNumberFilter) add(m float64) numberFilter { + return notNumberFilter {no.operand.add(m)} +} +func (no notNumberFilter) multiply(m float64) numberFilter { + return notNumberFilter {no.operand.multiply(m)} +} +func (no notNumberFilter) String() string { + return fmt.Sprintf("(!%v)", no.operand) +} + +type lessThanNumberFilter struct { + rhs float64 +} +func (l lessThanNumberFilter) numberFilter(n float64) bool { + return n < l.rhs +} +func (l lessThanNumberFilter) add(m float64) numberFilter { + return lessThanNumberFilter {l.rhs + m} +} +func (l lessThanNumberFilter) multiply(m float64) numberFilter { + if m > 0 { + return lessThanNumberFilter {l.rhs * m} + } else if m < 0 { + return greaterThanNumberFilter {l.rhs * m} + } else { + return equalNumberFilter {0} + } +} +func (l lessThanNumberFilter) String() string { + return fmt.Sprintf("(x < %v)", l.rhs) +} + +type greaterThanNumberFilter struct { + rhs float64 +} +func (g greaterThanNumberFilter) numberFilter(n float64) bool { + return n > g.rhs +} +func (g greaterThanNumberFilter) add(m float64) numberFilter { + return greaterThanNumberFilter {g.rhs + m} +} +func (g greaterThanNumberFilter) multiply(m float64) numberFilter { + if m > 0 { + return greaterThanNumberFilter {g.rhs * m} + } else if m < 0 { + return lessThanNumberFilter {g.rhs * m} + } else { + return equalNumberFilter {0} + } +} +func (g greaterThanNumberFilter) String() string { + return fmt.Sprintf("(x > %v)", g.rhs) +} + +type equalNumberFilter struct { + rhs float64 +} +func (e equalNumberFilter) numberFilter(n float64) bool { + return n == e.rhs +} +func (e equalNumberFilter) add(m float64) numberFilter { + return equalNumberFilter {e.rhs + m} +} +func (e equalNumberFilter) multiply(m float64) numberFilter { + return equalNumberFilter {e.rhs * m} +} diff --git a/subex/lex.go b/subex/lex.go index 0f00a99..dfe89b7 100644 --- a/subex/lex.go +++ b/subex/lex.go @@ -22,6 +22,9 @@ func (l *StringRuneReader) Next() rune { func (l *StringRuneReader) Rewind() { l.pos -= l.width } +func (l *StringRuneReader) RewindRune(r rune) { + l.pos -= utf8.RuneLen(r) +} func NewStringRuneReader(input string) RuneReader { return &StringRuneReader { diff --git a/subex/main.go b/subex/main.go index 32a5cf3..d4cacb9 100644 --- a/subex/main.go +++ b/subex/main.go @@ -88,7 +88,7 @@ func CompileTransducer(transducerAst SubexAST) Transducer { slotMap := SlotMap{ next: NextSlotIds{ values: 0, - runes: 0, + runes: 0, }, ids: make(map[rune]SlotId), } @@ -264,6 +264,8 @@ func addStates(curStates []SubexEatBranch, newStates []SubexBranch, nesting []bo state: s, aux: state.aux, }) + default: + panic("Invalid type of state") } } return curStates diff --git a/subex/main_test.go b/subex/main_test.go index fb6f152..3855dbc 100644 --- a/subex/main_test.go +++ b/subex/main_test.go @@ -36,7 +36,63 @@ func TestSubexMain(t *testing.T) { tests := []test { { - subex: `..+`, + // Keep only 5 + subex: `(5|(.>_))*`, + input: []walk.Value { + walk.NumberValue(0), + walk.NumberValue(1), + walk.NumberValue(2), + walk.NumberValue(3), + walk.NumberValue(4), + walk.NumberValue(5), + walk.NumberValue(9), + walk.NumberValue(10), + walk.NumberValue(11), + walk.NumberValue(2.5), + walk.NumberValue(7.0), + walk.NumberValue(-3), + }, + expected: []walk.Value { + walk.NumberValue(5), + }, + }, + { + // Keep only odd numbers between 0 and 10 + subex: `([c5*2+1]|(.>_))*`, + input: []walk.Value { + walk.NumberValue(0), + walk.NumberValue(1), + walk.NumberValue(2), + walk.NumberValue(3), + walk.NumberValue(4), + walk.NumberValue(5), + walk.NumberValue(9), + walk.NumberValue(10), + walk.NumberValue(11), + walk.NumberValue(2.5), + walk.NumberValue(7.0), + walk.NumberValue(-3), + }, + expected: []walk.Value { + walk.NumberValue(1), + walk.NumberValue(3), + walk.NumberValue(5), + walk.NumberValue(9), + walk.NumberValue(7), + }, + }, + { + subex: "r*([pi*2]%a`<a/2`)|([pi*2+1]%b`<b*3+1`)", + input: []walk.Value { + walk.NumberValue(32), + }, + expected: []walk.Value { + walk.NumberValue(32), + walk.NumberValue(16), + }, + }, + { + subex: `(..)%+`, input: []walk.Value { walk.NumberValue(12), walk.NumberValue(34), @@ -70,7 +126,7 @@ func TestSubexMain(t *testing.T) { }, }, { - subex: `~(.$_(.{-0}))~`, + subex: `~(.>_(.*))~`, input: []walk.Value { walk.StringValue("hello"), }, @@ -79,7 +135,7 @@ func TestSubexMain(t *testing.T) { }, }, { - subex: `#(".".{-0})-`, + subex: `#(".".*)-`, input: []walk.Value { walk.MapValue { { @@ -94,7 +150,7 @@ func TestSubexMain(t *testing.T) { }, }, { - subex: "@(..$a`$a$a`{-0})@", + subex: "@(((..)%a<a)*)@", input: []walk.Value { walk.ArrayValue { walk.ArrayElement { @@ -221,7 +277,7 @@ func TestSubexMain(t *testing.T) { }, }, { - subex: `@(.$_~(.{-0})-{-0})~`, + subex: `@((.>_~(.{-0})-){-0})~`, input: []walk.Value { walk.ArrayValue { { @@ -265,7 +321,7 @@ func TestSubexMain(t *testing.T) { }, }, { - subex: ":(.{-0}+)-", + subex: ":(.{-0}%+)-", input: []walk.Value { walk.ArrayValue { { @@ -287,7 +343,7 @@ func TestSubexMain(t *testing.T) { }, }, { - subex: "~(-(.)~{-0}):", + subex: "~(-(.)~*):", input: []walk.Value { walk.StringValue("abc"), }, @@ -309,7 +365,7 @@ func TestSubexMain(t *testing.T) { }, }, { - subex: "#(.(.$_){-0}):", + subex: "#((..>_)*):", input: []walk.Value { walk.MapValue { { @@ -344,7 +400,7 @@ func TestSubexMain(t *testing.T) { }, }, { - subex: ":(.`null`{-0})#", + subex: ":((.`null`)*)#", input: []walk.Value { walk.ArrayValue { { @@ -379,7 +435,7 @@ func TestSubexMain(t *testing.T) { }, }, { - subex: `#(".$_(.{-0})".{-0})#`, + subex: `#((".>_.*".)*)#`, input: []walk.Value { walk.MapValue { { @@ -406,7 +462,7 @@ func TestSubexMain(t *testing.T) { }, }, { - subex: ".{-0}`\"hello\"`", + subex: ".*`\"hello\"`", input: []walk.Value { walk.NumberValue(1), walk.NumberValue(2), @@ -437,3 +493,46 @@ func TestSubexMain(t *testing.T) { } } } + +func doCollatzTest(t *testing.T, init int) { + input := []walk.Value { + walk.NumberValue(init), + } + last := init + + lexer := NewStringRuneReader("r*([pi*2]%a`<a/2`|[pi*2+1]%b`<b*3+1`)") + ast := Parse(lexer) + transducer := CompileTransducer(ast) + + for last != 1 { + output, err := RunTransducer(transducer, input) + + if err { + t.Errorf("Collatz rejected %v", input) + return + } + + if last % 2 == 0 { + last = last / 2 + } else { + last = last * 3 + 1 + } + + if !reflect.DeepEqual(append(input, walk.NumberValue(last)), output) { + t.Errorf("Collatz took input: %v and produced output %v", input, output) + return + } + + input = output + } + + output, err := RunTransducer(transducer, input) + if !err { + t.Errorf("Collatz accepted input %v. Produced output: %v", input, output) + } +} + +func TestSubexCollatz(t *testing.T) { + doCollatzTest(t, 32) + doCollatzTest(t, 7) +} diff --git a/subex/parse.go b/subex/parse.go index e91008a..179cc01 100644 --- a/subex/parse.go +++ b/subex/parse.go @@ -1,7 +1,6 @@ package subex import ( - "fmt" "main/walk" "strconv" "strings" @@ -64,6 +63,7 @@ const ( type RuneReader interface { Next() rune Rewind() + RewindRune(r rune) } func accept(l RuneReader, chars string) bool { @@ -122,7 +122,6 @@ func parseScalarLiteral(l RuneReader) (walk.Scalar, bool) { panic("Invalid literal") } default: - fmt.Printf("%c\n", r) panic("Invalid literal") } } @@ -145,6 +144,72 @@ func parseInt(l RuneReader) (output int) { return output } +func parseNumberFilter(l RuneReader, minPower int) SubexASTNumberFilter { + var lhs SubexASTNumberFilter + r := l.Next() + switch r { + case eof: + panic("Missing matching ]") + case 'c': + count := parseInt(l) + lhs = SubexASTNumberFilterCount {count} + case 'p': + var subset NumberSubset + if l.Next() == 'i' { + subset = NumberSubsetPositiveInteger + } else { + subset = NumberSubsetPositiveReal + l.Rewind() + } + lhs = SubexASTNumberFilterSubset { + subset: subset, + } + default: + if !isNumericRune(r) { + panic("Invalid character in numeric []") + } + + var builder strings.Builder + builder.WriteRune(r) + for { + r := l.Next() + if !isNumericRune(r) { + l.Rewind() + break + } + builder.WriteRune(r) + } + numberString := builder.String() + number, err := strconv.ParseFloat(numberString, 64) + if err != nil { + panic("Invalid number literal") + } + + lhs = SubexASTNumberFilterLiteral {number} + } + + loop: for { + r := l.Next() + switch { + case r == '+' && minPower <= 10: + lhs = SubexASTNumberFilterAdd { + lhs: lhs, + rhs: parseNumberFilter(l, 11), + } + case r == '*' && minPower <= 20: + lhs = SubexASTNumberFilterMultiply { + lhs: lhs, + rhs: parseNumberFilter(l, 21), + } + default: + l.Rewind() + break loop + } + } + + return lhs +} + // Having just read {, read in and parse the range contents func parseRepeatRange(l RuneReader) (output []ConvexRange) { loop: for { @@ -189,7 +254,7 @@ func parseRepeatRange(l RuneReader) (output []ConvexRange) { return output } -func parseValueReplacement(l RuneReader, end rune) (output SubexAST) { +func parseValueReplacementOLD(l RuneReader, end rune) (output SubexAST) { output = SubexASTEmpty{} // TODO escaping // TODO add arrays, maps and strings @@ -222,7 +287,7 @@ func parseValueReplacement(l RuneReader, end rune) (output SubexAST) { Second: SubexASTDestructure { Destructure: NoneStructure, Structure: MapStructure, - Content: parseValueReplacement(l, ')'), + Content: parseValueReplacementOLD(l, ')'), }, } if !accept(l, "#") { @@ -264,7 +329,7 @@ func parseRuneReplacement(l RuneReader, end rune) (output SubexAST) { panic("Missing closing `") case end: break loop - case '$': + case '<': slot := l.Next() if slot == eof { panic("Missing slot character") @@ -287,6 +352,126 @@ func parseRuneReplacement(l RuneReader, end rune) (output SubexAST) { return output } +func parseValueReplacement(l RuneReader, end rune, minPower int) SubexAST { + // TODO: escaping probably + var lhs SubexAST + r := l.Next() + switch r { + case eof: + panic("Missing closing `") + case end: + l.Rewind() + return SubexASTEmpty{} + case 'n': + if !accept(l, "u") { + panic("Expected null") + } + if !accept(l, "l") { + panic("Expected null") + } + if !accept(l, "l") { + panic("Expected null") + } + lhs = SubexASTOutputValueLiteral { + literal: walk.NullValue{}, + } + // TODO: everything except numbers, strings, maps, and null + case '"': + lhs = SubexASTDestructure { + Destructure: NoneStructure, + Structure: StringStructure, + Content: parseRuneReplacement(l, '"'), + } + case '#': + if !accept(l, "(") { + panic("Missing ( after #") + } + lhs = SubexASTDestructure { + Destructure: NoneStructure, + Structure: MapStructure, + Content: parseValueReplacement(l, ')', 0), + } + if !accept(l, ")") { + panic("Missing closing )") + } + if !accept(l, "#") { + panic("Missing # after )") + } + case '<': + slot := l.Next() + if slot == eof { + panic("Missing slot character") + } + lhs = SubexASTOutputValueLoad { + slot: slot, + } + default: + if !isNumericRune(r) { + panic("Invalid character in numeric") + } + + var builder strings.Builder + builder.WriteRune(r) + for { + r := l.Next() + if !isNumericRune(r) { + l.Rewind() + break + } + builder.WriteRune(r) + } + numberString := builder.String() + number, err := strconv.ParseFloat(numberString, 64) + if err != nil { + panic("Invalid number literal") + } + + lhs = SubexASTOutputValueLiteral { + literal: walk.NumberValue(number), + } + } + + loop: for { + r := l.Next() + switch { + case r == eof: + panic("Missing closing `") + case r == '+' && minPower <= 10: + lhs = SubexASTBinop { + op: binopAdd, + lhs: lhs, + rhs: parseValueReplacement(l, end, 11), + } + case r == '*' && minPower <= 20: + lhs = SubexASTBinop { + op: binopMultiply, + lhs: lhs, + rhs: parseValueReplacement(l, end, 21), + } + case r == '/' && minPower <= 20: + lhs = SubexASTBinop { + op: binopDivide, + lhs: lhs, + rhs: parseValueReplacement(l, end, 21), + } + case r == end: + l.Rewind() + break loop + case minPower <= 2: + l.Rewind() + lhs = SubexASTConcat { + First: lhs, + Second: parseValueReplacement(l, end, 3), + } + default: + l.Rewind() + break loop + } + } + + return lhs +} + // Parse the contents of a range subex [] into a map // func parseRangeSubex(l RuneReader) map[walk.AtomOLD]walk.AtomOLD { // // TODO escaping @@ -471,165 +656,395 @@ func parseSubex(l RuneReader, minPower int, inType Type) (lhs SubexAST, outType start: r := l.Next() switch r { - case eof: - return nil, inType - case '(': - lhs, outType = parseSubex(l, 0, inType) - if !accept(l, ")") { - panic("Missing matching )") - } - case '-': - lhs, outType = parseDestructure(l, NoneStructure, inType) - case '~': - lhs, outType = parseDestructure(l, StringStructure, inType) - case '@': - lhs, outType = parseDestructure(l, ArrayStructure, inType) - case ':': - lhs, outType = parseDestructure(l, ArrayValuesStructure, inType) - case '#': - lhs, outType = parseDestructure(l, MapStructure, inType) - case '"': - if inType == ValueType { - var innerOutType Type - lhs, innerOutType = parseSubex(l, 0, RuneType) - if !accept(l, "\"") { - panic("Missing matching \"") - } - resolveTypes(innerOutType, RuneType) - lhs = SubexASTDestructure { - Destructure: StringStructure, - Structure: StringStructure, - Content: lhs, - } - outType = ValueType - } else { - l.Rewind() - return SubexASTEmpty{}, inType + case eof: + return nil, inType + case '(': + lhs, outType = parseSubex(l, 0, inType) + if !accept(l, ")") { + panic("Missing matching )") + } + case '-': + lhs, outType = parseDestructure(l, NoneStructure, inType) + case '~': + lhs, outType = parseDestructure(l, StringStructure, inType) + case '@': + lhs, outType = parseDestructure(l, ArrayStructure, inType) + case ':': + lhs, outType = parseDestructure(l, ArrayValuesStructure, inType) + case '#': + lhs, outType = parseDestructure(l, MapStructure, inType) + case '"': + switch inType { + case ValueType: + var innerOutType Type + lhs, innerOutType = parseSubex(l, 0, RuneType) + if !accept(l, "\"") { + panic("Missing matching \"") + } + resolveTypes(innerOutType, RuneType) + lhs = SubexASTDestructure { + Destructure: StringStructure, + Structure: StringStructure, + Content: lhs, } - // TODO - // case '[': - // rangeParts := parseRangeSubex(l) - // lhs = SubexASTRange {rangeParts} - case ')', ']', '|', ';', '{', '+', '*', '/', '!', '=', '$': + outType = ValueType + // RuneType + default: l.Rewind() return SubexASTEmpty{}, inType - case '.': - outType = inType - if inType == RuneType { - lhs = SubexASTCopyAnyRune{} - } else { - lhs = SubexASTCopyAnyValue{} - } - case ',': + } + case '<': + slot := l.Next() + switch slot { + case eof: + panic("Missing slot") + case '>': + panic("Parsing error. Tried to parse <> as a subex with nothing before it") + default: switch inType { case ValueType: - outType = inType - lhs = SubexASTCopyAnySimpleValue{} + lhs = SubexASTOutputValueLoad { + slot: slot, + } case RuneType: - outType = inType - lhs = SubexASTCopyRune{','} + lhs = SubexASTOutputRuneLoad { + slot: slot, + } default: panic("Invalid inType") } - case '?': + } + case '[': + switch inType { + case ValueType: + lhs = SubexASTCopyNumberFilter { + filter: parseNumberFilter(l, 0), + } + if !accept(l, "]") { + panic("Missing matching ]") + } + default: + // TODO: other types + panic("[] is only valid for values currently") + } + case ')', ']', '|', '{', '+', '*': + l.Rewind() + return SubexASTEmpty{}, inType + case '.': + outType = inType + if inType == RuneType { + lhs = SubexASTCopyAnyRune{} + } else { + lhs = SubexASTCopyAnyValue{} + } + case ',': + switch inType { + case ValueType: outType = inType - lhs = SubexASTCopyBool{} - case '%': + lhs = SubexASTCopyAnySimpleValue{} + case RuneType: outType = inType - lhs = SubexASTCopyNumber{} - case '`': + lhs = SubexASTCopyRune{','} + default: + panic("Invalid inType") + } + case 'r': + switch inType { + case ValueType: outType = inType - switch inType { - case ValueType: - lhs = parseValueReplacement(l, '`') - case RuneType: - lhs = parseRuneReplacement(l, '`') - default: - panic("Invalid inType") + lhs = SubexASTCopyNumberFilter { + filter: SubexASTNumberFilterSubset { + subset: NumberSubsetReal, + }, } - case ' ': - if inType == RuneType { - outType = RuneType - lhs = SubexASTCopyRune {' '} - } else { - goto start + case RuneType: + outType = inType + lhs = SubexASTCopyRune {'r'} + default: + panic("Invalid inType") + } + case '?': + outType = inType + lhs = SubexASTCopyBool{} + case '`': + outType = inType + switch inType { + case ValueType: + lhs = parseValueReplacement(l, '`', 0) + if !accept(l, "`") { + panic("Missing closing `") } + case RuneType: + lhs = parseRuneReplacement(l, '`') default: - outType = inType - if inType == RuneType { - lhs = SubexASTCopyRune {r} - } else { - l.Rewind() - scalar, ok := parseScalarLiteral(l) - if !ok { - panic("Invalid subex") - } - lhs = SubexASTCopyScalar {scalar} + panic("Invalid inType") + } + case ' ': + switch inType { + case RuneType: + outType = RuneType + lhs = SubexASTCopyRune {' '} + case ValueType: + goto start + } + default: + outType = inType + switch inType { + case RuneType: + lhs = SubexASTCopyRune {r} + // ValueType, NumberType + case ValueType: + l.Rewind() + scalar, ok := parseScalarLiteral(l) + if !ok { + panic("Invalid subex") } + lhs = SubexASTCopyScalar {scalar} + } } loop: for { - if minPower <= 20 { - next, outType2 := parseSubex(l, 21, inType) - // TODO: next might legitimately be SubexASTEmpty, e.g. `` - if next != nil && (next != SubexASTEmpty{}) { - outType = resolveTypes(outType, outType2) - lhs = SubexASTConcat{lhs, next} - continue loop - } - } r := l.Next() switch { - case r == '{' && minPower <= 4: - lhs = SubexASTRepeat { + case r == eof: + break loop + case r == '{' && minPower <= 10: + lhs = SubexASTRepeat { + Content: lhs, + Acceptable: parseRepeatRange(l), + } + case r == '+' && minPower <= 10: + lhs = SubexASTRepeat { + Content: lhs, + Acceptable: []ConvexRange {{ + Start: -1, + End: 1, + }}, + } + case r == '*' && minPower <= 10: + lhs = SubexASTRepeat { + Content: lhs, + Acceptable: []ConvexRange {{ + Start: -1, + End: 0, + }}, + } + case r == '_' && minPower <= 10: + switch inType { + case ValueType: + lhs = SubexASTDiscard { Content: lhs, - Acceptable: parseRepeatRange(l), + InnerOutType: outType, } - case r == '+' && minPower <= 4: - lhs = SubexASTSum {lhs} - resolveTypes(inType, ValueType) - outType = resolveTypes(outType, ValueType) - case r == '*' && minPower <= 4: - lhs = SubexASTProduct {lhs} - resolveTypes(inType, ValueType) - outType = resolveTypes(outType, ValueType) - case r == '!' && minPower <= 4: - lhs = SubexASTNot {lhs} - resolveTypes(inType, ValueType) - outType = resolveTypes(outType, ValueType) - case r == '$' && minPower <= 4: + outType = AnyType + case RuneType: + // Just a concat + lhs = SubexASTConcat { + lhs, + SubexASTCopyRune { + rune: '_', + }, + } + outType = AnyType + default: + panic("Invalid inType") + } + case r == '%' && minPower <= 10: + slot := l.Next() + switch slot { + case eof: + panic("Missing slot character") + case '<', '>': + panic("Invalid character after %") + case '_': + panic("Cannot load from _") + default: + switch inType { + case ValueType: + lhs = SubexASTConcat { + First: SubexASTStoreValues { + Match: lhs, + Slot: slot, + }, + Second: SubexASTOutputValueLoad { + slot: slot, + }, + } + case RuneType: + lhs = SubexASTConcat { + First: SubexASTStoreRunes { + Match: lhs, + Slot: slot, + }, + Second: SubexASTOutputRuneLoad { + slot: slot, + }, + } + default: + panic("Invalid inType") + } + } + case r == '>' && minPower <= 10: + slot := l.Next() + switch slot { + case eof: + panic("Missing slot character") + case '>': slot := l.Next() - if slot == eof { + switch slot { + case eof: panic("Missing slot character") - } - if slot == '_' { + case '_': lhs = SubexASTDiscard { Content: lhs, InnerOutType: outType, } - } else { - if inType == ValueType { - lhs = SubexASTStoreValues { + outType = AnyType + default: + switch inType { + case ValueType: + lhs = SubexASTAppendStoreValues { Match: lhs, Slot: slot, } - } else { - lhs = SubexASTStoreRunes { + case RuneType: + lhs = SubexASTAppendStoreRunes { Match: lhs, Slot: slot, } + default: + panic("Invalid inType") } + outType = AnyType + } + case '<': + slot := l.Next() + switch slot { + case eof: + panic("Missing slot character") + case '_': + panic("Cannot load from _ slot") + default: + switch inType { + case ValueType: + lhs = SubexASTConcat { + First: SubexASTStoreValues { + Match: lhs, + Slot: slot, + }, + Second: SubexASTOutputValueLoad { + slot: slot, + }, + } + case RuneType: + lhs = SubexASTConcat { + First: SubexASTStoreRunes { + Match: lhs, + Slot: slot, + }, + Second: SubexASTOutputRuneLoad { + slot: slot, + }, + } + default: + panic("Invalid inType") + } + outType = inType + } + case '_': + lhs = SubexASTDiscard { + Content: lhs, + InnerOutType: outType, } outType = AnyType - case r == '|' && minPower <= 8: - rhs, outType2 := parseSubex(l, 9, inType) - outType = resolveTypes(outType, outType2) - if rhs == nil { - panic("Missing subex after |") + default: + switch inType { + case ValueType: + lhs = SubexASTStoreValues { + Match: lhs, + Slot: slot, + } + case RuneType: + lhs = SubexASTStoreRunes { + Match: lhs, + Slot: slot, + } + default: + panic("Invalid type") + } + outType = AnyType + } + case r == '<' && minPower <= 6: + slot := l.Next() + switch slot { + case eof: + panic("Missing slot character") + case '_': + panic("Cannot load from _ slot") + case '>': + slot := l.Next() + switch slot { + case eof: + panic("Missing slot character") + case '_': + panic("Cannot load from _ slot") + default: + switch inType { + case ValueType: + lhs = SubexASTConcat { + SubexASTOutputValueLoad { + slot: slot, + }, + SubexASTStoreValues { + Match: lhs, + Slot: slot, + }, + } + case RuneType: + lhs = SubexASTConcat { + SubexASTOutputRuneLoad { + slot: slot, + }, + SubexASTStoreRunes { + Match: lhs, + Slot: slot, + }, + } + default: + panic("Invalid inType") + } } - lhs = SubexASTOr{lhs, rhs} default: + // This is just a concat l.Rewind() + l.RewindRune('<') + next, outType2 := parseSubex(l, 7, inType) + // TODO: next might legitimately be SubexASTEmpty, e.g. `` + if next != nil && (next != SubexASTEmpty{}) { + outType = resolveTypes(outType, outType2) + lhs = SubexASTConcat{lhs, next} + continue loop + } + } + case r == '|' && minPower <= 2: + rhs, outType2 := parseSubex(l, 3, inType) + outType = resolveTypes(outType, outType2) + if rhs == nil { + panic("Missing subex after |") + } + lhs = SubexASTOr{lhs, rhs} + case minPower <= 6: + l.Rewind() + next, outType2 := parseSubex(l, 7, inType) + // TODO: next might legitimately be SubexASTEmpty, e.g. `` + if next != nil && (next != SubexASTEmpty{}) { + outType = resolveTypes(outType, outType2) + lhs = SubexASTConcat{lhs, next} + } else { break loop + } + default: + l.Rewind() + break loop } } return lhs, outType diff --git a/subex/subexast.go b/subex/subexast.go index 655a783..89949ba 100644 --- a/subex/subexast.go +++ b/subex/subexast.go @@ -32,20 +32,60 @@ type SubexASTStoreValues struct { Slot rune } func (ast SubexASTStoreValues) compileWith(next SubexState, slotMap *SlotMap, inType Type, outType Type) SubexState { + if inType != ValueType { + panic("Invalid inType storing to value slot") + } id := slotMap.getId(ast.Slot) - newNext := ast.Match.compileWith(&SubexStoreEndState { + var endState SubexState = &SubexStoreEndState { slot: id, next: next, - }, slotMap, inType, ValueType) + } + switch ast.Slot { + case '+': + endState = &SubexCaptureBeginState { + next: ast.Match.compileWith(&SubexArithmeticEndState { + calculate: arithmeticSum, + next: endState, + }, slotMap, inType, outType), + } + case '*': + endState = &SubexCaptureBeginState { + next: ast.Match.compileWith(&SubexArithmeticEndState { + calculate: arithmeticProduct, + next: endState, + }, slotMap, inType, outType), + } + default: + endState = ast.Match.compileWith(endState, slotMap, inType, outType) + } return &SubexCaptureBeginState { - next: newNext, + next: endState, } } func (ast SubexASTStoreValues) String() string { return fmt.Sprintf("$%c(%v)", ast.Slot, ast.Match) } +type SubexASTAppendStoreValues struct { + Match SubexAST + Slot rune +} +func (ast SubexASTAppendStoreValues) compileWith(next SubexState, slotMap *SlotMap, inType Type, outType Type) SubexState { + id := slotMap.getId(ast.Slot) + newNext := ast.Match.compileWith(&SubexStoreEndState { + slot: id, + next: next, + }, slotMap, inType, ValueType) + + return &SubexOutputValueLoadState { + slot: id, + next: &SubexCaptureBeginState { + next: newNext, + }, + } +} + type SubexASTStoreRunes struct { Match SubexAST Slot rune @@ -66,6 +106,25 @@ func (ast SubexASTStoreRunes) String() string { } // Try to run the first subex, if it fails then backtrack and use the second +type SubexASTAppendStoreRunes struct { + Match SubexAST + Slot rune +} +func (ast SubexASTAppendStoreRunes) compileWith(next SubexState, slotMap *SlotMap, inType Type, outType Type) SubexState { + id := slotMap.getId(ast.Slot) + newNext := ast.Match.compileWith(&SubexStoreEndState { + slot: id, + next: next, + }, slotMap, inType, RuneType) + + return &SubexOutputRuneLoadState { + slot: id, + next: &SubexCaptureBeginState { + next: newNext, + }, + } +} + type SubexASTOr struct { First, Second SubexAST } @@ -238,6 +297,158 @@ func (ast SubexASTCopyNumber) String() string { return "%" } +type SubexASTNumberFilter interface { + compile() numberFilter + computable() bool + compute() float64 +} + +type SubexASTNumberFilterLiteral struct { + value float64 +} +func (ast SubexASTNumberFilterLiteral) compile() numberFilter { + return equalNumberFilter {ast.value} +} +func (ast SubexASTNumberFilterLiteral) computable() bool { + return true +} +func (ast SubexASTNumberFilterLiteral) compute() float64 { + return ast.value +} + +type NumberSubset int +const ( + NumberSubsetReal NumberSubset = iota + NumberSubsetInteger + NumberSubsetPositiveInteger + NumberSubsetZeroToOne + NumberSubsetPositiveReal + NumberSubsetNonNegativeReal +) + +type SubexASTNumberFilterSubset struct { + subset NumberSubset +} +func (ast SubexASTNumberFilterSubset) compile() numberFilter { + switch ast.subset { + case NumberSubsetReal: + return anyNumberFilter{} + case NumberSubsetInteger: + return divisibleNumberFilter { + divisor: 1.0, + target: 0.0, + } + case NumberSubsetPositiveInteger: + return andNumberFilter { + lhs: divisibleNumberFilter { + divisor: 1.0, + target: 0.0, + }, + rhs: greaterThanNumberFilter {0.0}, + } + case NumberSubsetZeroToOne: + return andNumberFilter { + lhs: notNumberFilter { + lessThanNumberFilter {0}, + }, + rhs: notNumberFilter { + greaterThanNumberFilter {1}, + }, + } + case NumberSubsetPositiveReal: + return greaterThanNumberFilter {0} + case NumberSubsetNonNegativeReal: + return notNumberFilter { + lessThanNumberFilter {0}, + } + default: + panic("Invalid NumberSubset") + } +} +func (ast SubexASTNumberFilterSubset) computable() bool { + return false +} +func (ast SubexASTNumberFilterSubset) compute() float64 { + panic("Tried to compute uncomputable") +} + +type SubexASTNumberFilterCount struct { + count int +} +func (ast SubexASTNumberFilterCount) compile() numberFilter { + return andNumberFilter { + lhs: andNumberFilter { + lhs: notNumberFilter { + lessThanNumberFilter {0.0}, + }, + rhs: lessThanNumberFilter {float64(ast.count)}, + }, + rhs: divisibleNumberFilter { + divisor: 1.0, + target: 0.0, + }, + } +} +func (ast SubexASTNumberFilterCount) computable() bool { + return false +} +func (ast SubexASTNumberFilterCount) compute() float64 { + panic("Tried to compute uncomputable") +} + +type SubexASTNumberFilterAdd struct { + lhs, rhs SubexASTNumberFilter +} +func (ast SubexASTNumberFilterAdd) compile() numberFilter { + if ast.lhs.computable() { + return ast.rhs.compile().add(ast.lhs.compute()) + } else { + return ast.lhs.compile().add(ast.rhs.compute()) + } +} +func (ast SubexASTNumberFilterAdd) computable() bool { + return ast.lhs.computable() && ast.rhs.computable() +} +func (ast SubexASTNumberFilterAdd) compute() float64 { + return ast.lhs.compute() + ast.rhs.compute() +} +func (ast SubexASTNumberFilterAdd) String() string { + return fmt.Sprintf("(%v + %v)", ast.lhs, ast.rhs) +} + +type SubexASTNumberFilterMultiply struct { + lhs, rhs SubexASTNumberFilter +} +func (ast SubexASTNumberFilterMultiply) compile() numberFilter { + if ast.lhs.computable() { + return ast.rhs.compile().multiply(ast.lhs.compute()) + } else { + return ast.lhs.compile().multiply(ast.rhs.compute()) + } +} +func (ast SubexASTNumberFilterMultiply) computable() bool { + return ast.lhs.computable() && ast.rhs.computable() +} +func (ast SubexASTNumberFilterMultiply) compute() float64 { + return ast.lhs.compute() * ast.rhs.compute() +} +func (ast SubexASTNumberFilterMultiply) String() string { + return fmt.Sprintf("(%v * %v)", ast.lhs, ast.rhs) +} + +type SubexASTCopyNumberFilter struct { + filter SubexASTNumberFilter +} +func (ast SubexASTCopyNumberFilter) compileWith(next SubexState, slotMap *SlotMap, inType Type, outType Type) SubexState { + if inType != ValueType || outType != ValueType { + panic("Invalid types for SubexASTCopyNumberFilter") + } + return &SubexCopyNumberState { + next: next, + filter: ast.filter.compile(), + } +} + // Read in a null, bool, number, string or empty array or map and output it unchanged type SubexASTCopyAnySimpleValue struct {} func (ast SubexASTCopyAnySimpleValue) compileWith(next SubexState, slotMap *SlotMap, inType Type, outType Type) SubexState { @@ -377,85 +588,31 @@ func (ast SubexASTOutputRuneLoad) compileWith(next SubexState, slotMap *SlotMap, // return fmt.Sprintf("[abc=xyz]") // } -// Run content, if content is a list of booleans, OR them, if all values are castable to numbers, sum them and output the total -// Reject if neither of these cases match -type SubexASTSum struct { - Content SubexAST -} -func (ast SubexASTSum) compileWith(next SubexState, slotMap *SlotMap, inType Type, outType Type) SubexState { - if inType != ValueType || outType != ValueType { - panic("Invalid types for SubexASTSum") - } - return &SubexCaptureBeginState { - next: ast.Content.compileWith(&SubexArithmeticEndState { - next: next, - calculate: sumValues, - }, slotMap, inType, outType), - } +type SubexASTBinop struct { + op func ([]walk.Value) ([]walk.Value, error) + lhs, rhs SubexAST } -func (ast SubexASTSum) String() string { - return fmt.Sprintf("(%v)+", ast.Content) -} - -// Like sum but for AND and product -type SubexASTProduct struct { - Content SubexAST -} -func (ast SubexASTProduct) compileWith(next SubexState, slotMap *SlotMap, inType Type, outType Type) SubexState { - if inType != ValueType || outType != ValueType { - panic("Invalid types for SubexASTProduct") - } - return &SubexCaptureBeginState { - next: ast.Content.compileWith(&SubexArithmeticEndState { - next: next, - calculate: multiplyValues, - }, slotMap, inType, outType), - } -} -func (ast SubexASTProduct) String() string { - return fmt.Sprintf("(%v)*", ast.Content) -} - -// Runs the content Subex, if all outputted atoms can be cast to numbers, outputs them all negated -// Rejects if this fails -type SubexASTNegate struct { - Content SubexAST -} -func (ast SubexASTNegate) compileWith(next SubexState, slotMap *SlotMap, inType Type, outType Type) SubexState { - if inType != ValueType || outType != ValueType { - panic("Invalid types for SubexASTNegate") - } - return &SubexCaptureBeginState { - next: ast.Content.compileWith(&SubexArithmeticEndState { - next: next, - calculate: negateValues, - }, slotMap, inType, outType), - } -} -func (ast SubexASTNegate) String() string { - return fmt.Sprintf("(%v)-", ast.Content) -} - -// Runs the content Subex and collects the output -// Maps over the values in the output, casting each to a boolean, notting each and then outputs them -// Rejects if it cannot cast to boolean -type SubexASTNot struct { - Content SubexAST -} -func (ast SubexASTNot) compileWith(next SubexState, slotMap *SlotMap, inType Type, outType Type) SubexState { - if inType != ValueType || outType != ValueType { - panic("Invalid types for SubexASTNot") +func (ast SubexASTBinop) compileWith(next SubexState, slotMap *SlotMap, inType Type, outType Type) SubexState { + if outType != ValueType { + panic("Invalid types for SubexASTBinop") } return &SubexCaptureBeginState { - next: ast.Content.compileWith(&SubexArithmeticEndState { - next: next, - calculate: notValues, - }, slotMap, ValueType, ValueType), + next: ast.lhs.compileWith( + ast.rhs.compileWith( + &SubexArithmeticEndState { + next: next, + calculate: ast.op, + }, + slotMap, + inType, + outType, + ), + slotMap, + inType, + outType, + ), } } -func (ast SubexASTNot) String() string { - return fmt.Sprintf("(%v)!", ast.Content) -} // Does nothing type SubexASTEmpty struct {} diff --git a/subex/subexstate.go b/subex/subexstate.go index 8f27a10..3bcbdee 100644 --- a/subex/subexstate.go +++ b/subex/subexstate.go @@ -43,6 +43,9 @@ func (state SubexGroupState) epsilon(aux auxiliaryState) []SubexBranch { }, } } +func (state SubexGroupState) String() string { + return fmt.Sprintf("{%T %p, %T %p}", state.first, state.first, state.second, state.second) +} type SubexCopyState struct { next SubexState @@ -83,6 +86,24 @@ func (state SubexCopyRuneState) String() string { return fmt.Sprintf("SubexCopyRuneState[%v]", state.filter) } +type SubexCopyNumberState struct { + next SubexState + filter numberFilter +} +func (state SubexCopyNumberState) eat(aux auxiliaryState, edible walk.Edible) []SubexBranch { + number, isNumber := edible.(walk.NumberValue) + if !isNumber || !state.filter.numberFilter(float64(number)) { + return nil + } + return []SubexBranch {{ + state: state.next, + aux: aux.topAppend([]walk.Value {number}), + }} +} +func (state SubexCopyNumberState) accepting(aux auxiliaryState) []OutputStack { + return nil +} + // Just pushes to the OutputStack and hands over to the next state // Used to capture the output of the state being handed over to type SubexCaptureBeginState struct { |