diff options
| -rw-r--r-- | main/command.go | 37 | ||||
| -rw-r--r-- | main/lex.go | 2 | ||||
| -rw-r--r-- | main/main_test.go | 89 | ||||
| -rw-r--r-- | main/parse.go | 4 | ||||
| -rw-r--r-- | subex/arithmetic.go | 203 | ||||
| -rw-r--r-- | subex/filter.go | 191 | ||||
| -rw-r--r-- | subex/lex.go | 3 | ||||
| -rw-r--r-- | subex/main.go | 4 | ||||
| -rw-r--r-- | subex/main_test.go | 122 | ||||
| -rw-r--r-- | subex/numberexpr.go | 217 | ||||
| -rw-r--r-- | subex/parse.go | 792 | ||||
| -rw-r--r-- | subex/subexast.go | 192 | ||||
| -rw-r--r-- | subex/subexstate.go | 122 |
13 files changed, 1506 insertions, 472 deletions
diff --git a/main/command.go b/main/command.go index 38e1c95..bbbb036 100644 --- a/main/command.go +++ b/main/command.go @@ -138,9 +138,42 @@ func (cmd MergeCommand) String() string { return "m" } -type FullMergeCommand struct {} +type FullMergeCommand struct { + subex subex.Transducer +} func (cmd FullMergeCommand) exec(state *ProgramState) { - panic("Unimplemented") + _, notOk := runSubex(cmd.subex, state.value) + if notOk { + state.pc++ + return + } + if !state.start { + state.pc += 2 + return + } + + for { + item, err := state.Read() + if err != nil { + panic("Missing next value") + } + + _, nonTerminal := runSubex(cmd.subex, []walk.Value{item.Value}) + + state.value = append( + state.value[:len(state.value) - 1], + walk.Merge(state.value[len(state.value) - 1], item.Value)... + ) + + if !nonTerminal && item.End { + state.prevStart = item.PrevStart + state.start = item.Start + state.end = item.End + state.nextEnd = item.NextEnd + state.pc += 2 + return + } + } } func (cmd FullMergeCommand) String() string { return "M" diff --git a/main/lex.go b/main/lex.go index 8e66890..da517cc 100644 --- a/main/lex.go +++ b/main/lex.go @@ -180,7 +180,7 @@ func lexCommand(l *lexer) stateFunc { case '}': l.emit(TokenRBrace) return lexCommand - case 's', 'S': + case 's', 'S', 'M': l.emit(TokenCommand) return lexSubstitution case 'x', 'X', 'y', 'Y', 'z', 'Z', 'n', 'N': diff --git a/main/main_test.go b/main/main_test.go index 1510497..802d248 100644 --- a/main/main_test.go +++ b/main/main_test.go @@ -5,9 +5,11 @@ import ( "testing" ) -var miscInput string = `{"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},{"first_name":"John","last_name":"Johnson","age":48}]}` +const miscInput string = `{"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},{"first_name":"John","last_name":"Johnson","age":48}]}` +const mixedArray string = `{"array":["first",null,3,{"name":"second"},"third"]}` +const mixedArray2 string = `{"array":["first",null,3,"second",{"name":"third"}]}` -func TestMain(t *testing.T) { +func TestSpecificCases(t *testing.T) { type test struct { name string program string @@ -19,73 +21,136 @@ func TestMain(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\"\".*>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/.*:():/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\"_:(.*)-)-/ s/-(~(.*` `)-*~(.*)-)~/p }", + quiet: true, + input: miscInput, + expected: `"Hello world these are values"`, + }, + { + name: "Drop first element of array", + 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 }`, + 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 }`, + 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 }`, + input: mixedArray, + expected: `{"array":["first",null,3,{"name":"second"}]}`, + }, + { + name: "Drop last element of mixed array 2", + program: `M/#("array"@(.,)@)#/{ Ed }`, + input: mixedArray2, + expected: `{"array":["first",null,3,"second"]}`, + }, + { + name: "Prepend to array", + 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\"`):)#/", + 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}]}`, + }, } for _, test := range tests { diff --git a/main/parse.go b/main/parse.go index 36917ac..36bd3ee 100644 --- a/main/parse.go +++ b/main/parse.go @@ -77,6 +77,10 @@ func (p *parser) parseBasicCommand(commands []Command, commandChar rune) []Comma return append(commands, SubstituteAppendNextCommand {subex}, JumpCommand {len(commands) + 3}) case 'm': return append(commands, MergeCommand{}) + case 'M': + ast := p.parseSubex() + subex := subex.CompileTransducer(ast) + return append(commands, FullMergeCommand {subex}, JumpCommand {len(commands) + 3}) case 's': ast := p.parseSubex() subex := subex.CompileTransducer(ast) 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 ae4b8ab..87c83a4 100644 --- a/subex/filter.go +++ b/subex/filter.go @@ -2,6 +2,8 @@ package subex import ( "main/walk" + "math" + "fmt" ) type valueFilter interface { @@ -27,6 +29,26 @@ func (_ anyBoolFilter) valueFilter(value walk.Value) bool { return isBool } +type simpleValueFilter struct {} +func (_ simpleValueFilter) valueFilter(value walk.Value) bool { + switch value := value.(type) { + case walk.NullValue: + return true + case walk.BoolValue: + return true + case walk.NumberValue: + return true + case walk.StringValue: + return true + case walk.ArrayValue: + return len(value) == 0 + case walk.MapValue: + return len(value) == 0 + default: + panic("Invalid value type") + } +} + type anyValueFilter struct {} func (_ anyValueFilter) valueFilter(value walk.Value) bool { return true @@ -66,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..938e5cb 100644 --- a/subex/main_test.go +++ b/subex/main_test.go @@ -36,7 +36,64 @@ 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: `([0<=n&n<=10&n%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), + }, + }, + { + // Collatz + subex: "[1]*[n%2=0:n,n/2]|[n%2=1:n,n*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 +127,7 @@ func TestSubexMain(t *testing.T) { }, }, { - subex: `~(.$_(.{-0}))~`, + subex: `~(.>_(.*))~`, input: []walk.Value { walk.StringValue("hello"), }, @@ -79,7 +136,7 @@ func TestSubexMain(t *testing.T) { }, }, { - subex: `#(".".{-0})-`, + subex: `#(".".*)-`, input: []walk.Value { walk.MapValue { { @@ -94,7 +151,7 @@ func TestSubexMain(t *testing.T) { }, }, { - subex: "@(..$a`$a$a`{-0})@", + subex: "@(((..)%a<a)*)@", input: []walk.Value { walk.ArrayValue { walk.ArrayElement { @@ -221,7 +278,7 @@ func TestSubexMain(t *testing.T) { }, }, { - subex: `@(.$_~(.{-0})-{-0})~`, + subex: `@((.>_~(.{-0})-){-0})~`, input: []walk.Value { walk.ArrayValue { { @@ -265,7 +322,7 @@ func TestSubexMain(t *testing.T) { }, }, { - subex: ":(.{-0}+)-", + subex: ":(.{-0}%+)-", input: []walk.Value { walk.ArrayValue { { @@ -287,7 +344,7 @@ func TestSubexMain(t *testing.T) { }, }, { - subex: "~(-(.)~{-0}):", + subex: "~(-(.)~*):", input: []walk.Value { walk.StringValue("abc"), }, @@ -309,7 +366,7 @@ func TestSubexMain(t *testing.T) { }, }, { - subex: "#(.(.$_){-0}):", + subex: "#((..>_)*):", input: []walk.Value { walk.MapValue { { @@ -344,7 +401,7 @@ func TestSubexMain(t *testing.T) { }, }, { - subex: ":(.`null`{-0})#", + subex: ":((.`null`)*)#", input: []walk.Value { walk.ArrayValue { { @@ -379,7 +436,7 @@ func TestSubexMain(t *testing.T) { }, }, { - subex: `#(".$_(.{-0})".{-0})#`, + subex: `#((".>_.*".)*)#`, input: []walk.Value { walk.MapValue { { @@ -406,7 +463,7 @@ func TestSubexMain(t *testing.T) { }, }, { - subex: ".{-0}`\"hello\"`", + subex: ".*`\"hello\"`", input: []walk.Value { walk.NumberValue(1), walk.NumberValue(2), @@ -437,3 +494,46 @@ func TestSubexMain(t *testing.T) { } } } + +func doCollatzTest(t *testing.T, init int) { + input := []walk.Value { + walk.NumberValue(init), + } + last := init + + lexer := NewStringRuneReader("[1]*([n%2=0:n,n/2]|[n%2=1&n>1:n,n*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/numberexpr.go b/subex/numberexpr.go new file mode 100644 index 0000000..3649305 --- /dev/null +++ b/subex/numberexpr.go @@ -0,0 +1,217 @@ +package subex + +import ( + "fmt" + "math" +) + +type NumberExpr interface { + String() string + Eval(float64) float64 +} + +type NumberExprVariable struct {} +func (ev NumberExprVariable) String() string { + return "n" +} +func (ev NumberExprVariable) Eval(v float64) float64 { + return v +} + +type NumberExprLiteral struct { + Value float64 +} +func (el NumberExprLiteral) String() string { + return fmt.Sprintf("%v", el.Value) +} +func (el NumberExprLiteral) Eval(v float64) float64 { + return el.Value +} + +type NumberExprAnd struct { + Left NumberExpr + Right NumberExpr +} +func (ea NumberExprAnd) String() string { + return fmt.Sprintf("(%v & %v)", ea.Left, ea.Right) +} +func (ea NumberExprAnd) Eval(v float64) float64 { + left := ea.Left.Eval(v) + if left != 0.0 { + return ea.Right.Eval(v) + } else { + return left + } +} + +type NumberExprOr struct { + Left NumberExpr + Right NumberExpr +} +func (eo NumberExprOr) String() string { + return fmt.Sprintf("(%v | %v)", eo.Left, eo.Right) +} +func (eo NumberExprOr) Eval(v float64) float64 { + left := eo.Left.Eval(v) + if left != 0.0 { + return left + } else { + return eo.Right.Eval(v) + } +} + +type NumberExprNot struct { + Right NumberExpr +} +func (en NumberExprNot) String() string { + return fmt.Sprintf("(!%v)", en.Right) +} +func (en NumberExprNot) Eval(v float64) float64 { + inner := en.Right.Eval(v) + if inner == 0.0 { + return 1.0 + } + + return 0.0 +} + +type NumberExprEqual struct { + Left NumberExpr + Right NumberExpr +} +func (ee NumberExprEqual) String() string { + return fmt.Sprintf("(%v = %v)", ee.Left, ee.Right) +} +func (ee NumberExprEqual) Eval(v float64) float64 { + if ee.Left.Eval(v) == ee.Right.Eval(v) { + return 1.0 + } else { + return 0.0 + } +} + +type NumberExprAtMost struct { + Left NumberExpr + Right NumberExpr +} +func (ea NumberExprAtMost) String() string { + return fmt.Sprintf("(%v <= %v)", ea.Left, ea.Right) +} +func (ea NumberExprAtMost) Eval(v float64) float64 { + if ea.Left.Eval(v) <= ea.Right.Eval(v) { + return 1.0 + } else { + return 0.0 + } +} + +type NumberExprLessThan struct { + Left NumberExpr + Right NumberExpr +} +func (el NumberExprLessThan) String() string { + return fmt.Sprintf("(%v < %v)", el.Left, el.Right) +} +func (el NumberExprLessThan) Eval(v float64) float64 { + if el.Left.Eval(v) < el.Right.Eval(v) { + return 1.0 + } else { + return 0.0 + } +} + +type NumberExprGreaterThan struct { + Left NumberExpr + Right NumberExpr +} +func (eg NumberExprGreaterThan) String() string { + return fmt.Sprintf("(%v > %v)", eg.Left, eg.Right) +} +func (eg NumberExprGreaterThan) Eval(v float64) float64 { + if eg.Left.Eval(v) > eg.Right.Eval(v) { + return 1.0 + } else { + return 0.0 + } +} + +type NumberExprAtLeast struct { + Left NumberExpr + Right NumberExpr +} +func (ea NumberExprAtLeast) String() string { + return fmt.Sprintf("(%v >= %v)", ea.Left, ea.Right) +} +func (ea NumberExprAtLeast) Eval(v float64) float64 { + if ea.Left.Eval(v) >= ea.Right.Eval(v) { + return 1.0 + } else { + return 0.0 + } +} + +type NumberExprAdd struct { + Left NumberExpr + Right NumberExpr +} +func (ea NumberExprAdd) String() string { + return fmt.Sprintf("(%v + %v)", ea.Left, ea.Right) +} +func (ea NumberExprAdd) Eval(v float64) float64 { + return ea.Left.Eval(v) + ea.Right.Eval(v) +} + +type NumberExprSubtract struct { + Left NumberExpr + Right NumberExpr +} +func (es NumberExprSubtract) String() string { + return fmt.Sprintf("(%v - %v)", es.Left, es.Right) +} +func (es NumberExprSubtract) Eval(v float64) float64 { + return es.Left.Eval(v) - es.Right.Eval(v) +} + +type NumberExprMultiply struct { + Left NumberExpr + Right NumberExpr +} +func (em NumberExprMultiply) String() string { + return fmt.Sprintf("(%v * %v)", em.Left, em.Right) +} +func (em NumberExprMultiply) Eval(v float64) float64 { + return em.Left.Eval(v) * em.Right.Eval(v) +} + +type NumberExprDivide struct { + Left NumberExpr + Right NumberExpr +} +func (ed NumberExprDivide) String() string { + return fmt.Sprintf("(%v / %v)", ed.Left, ed.Right) +} +func (ed NumberExprDivide) Eval(v float64) float64 { + return ed.Left.Eval(v) / ed.Right.Eval(v) +} + +type NumberExprMod struct { + Left NumberExpr + Right NumberExpr +} +func (em NumberExprMod) String() string { + return fmt.Sprintf("(%v %% %v)", em.Left, em.Right) +} +func (em NumberExprMod) Eval(v float64) float64 { + return math.Mod(em.Left.Eval(v), em.Right.Eval(v)) +} + +type NumberExprExponent struct { + Left NumberExpr + Right NumberExpr +} +func (ee NumberExprExponent) String() string { + return fmt.Sprintf("(%v * %v)", ee.Left, ee.Right) +} +func (ee NumberExprExponent) Eval(v float64) float64 { + return ee.Left.Eval(v) * ee.Right.Eval(v) +} diff --git a/subex/parse.go b/subex/parse.go index b6bf2f6..01a747b 100644 --- a/subex/parse.go +++ b/subex/parse.go @@ -1,7 +1,6 @@ package subex import ( - "fmt" "main/walk" "strconv" "strings" @@ -55,9 +54,16 @@ func (s Structure) String() string { } } +type DestructureMethod int +const ( + Normal DestructureMethod = iota + Iterate +) + type RuneReader interface { Next() rune Rewind() + RewindRune(r rune) } func accept(l RuneReader, chars string) bool { @@ -116,7 +122,6 @@ func parseScalarLiteral(l RuneReader) (walk.Scalar, bool) { panic("Invalid literal") } default: - fmt.Printf("%c\n", r) panic("Invalid literal") } } @@ -139,6 +144,166 @@ func parseInt(l RuneReader) (output int) { return output } +// Parse a number literal in a number expression +func parseNumberLiteral(l RuneReader) NumberExprLiteral { + var builder strings.Builder + 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") + } + return NumberExprLiteral { + Value: number, + } +} + +// Parse a numeric expression +func parseNumberExpression(l RuneReader, minPower int) NumberExpr { + var lhs NumberExpr + switch l.Next() { + case '(': + lhs = parseNumberExpression(l, 0) + if !accept(l, ")") { + panic("Missing closing )") + } + case 'n': + lhs = NumberExprVariable{} + case '-': + lhs = NumberExprLiteral{0} + l.Rewind() + case '!': + lhs = NumberExprNot { + Right: parseNumberExpression(l, 13), + } + default: + l.Rewind() + lhs = parseNumberLiteral(l) + } + + loop: for { + r := l.Next() + switch { + case r == '|' && minPower <= 8: + lhs = NumberExprOr { + Left: lhs, + Right: parseNumberExpression(l, 9), + } + case r == '&' && minPower <= 10: + lhs = NumberExprAnd { + Left: lhs, + Right: parseNumberExpression(l, 11), + } + case r == '<' && minPower <= 20: + if accept(l, "=") { + lhs = NumberExprAtMost { + Left: lhs, + Right: parseNumberExpression(l, 21), + } + } else { + lhs = NumberExprLessThan { + Left: lhs, + Right: parseNumberExpression(l, 21), + } + } + case r == '>' && minPower <= 20: + if accept(l, "=") { + lhs = NumberExprAtLeast { + Left: lhs, + Right: parseNumberExpression(l, 21), + } + } else { + lhs = NumberExprGreaterThan { + Left: lhs, + Right: parseNumberExpression(l, 21), + } + } + case r == '=' && minPower <= 20: + lhs = NumberExprEqual { + Left: lhs, + Right: parseNumberExpression(l, 21), + } + case r == '~' && minPower <= 20: + lhs = NumberExprNot { + Right: NumberExprEqual { + Left: lhs, + Right: parseNumberExpression(l, 21), + }, + } + case r == '+' && minPower <= 30: + lhs = NumberExprAdd { + Left: lhs, + Right: parseNumberExpression(l, 31), + } + case r == '-' && minPower <= 30: + lhs = NumberExprSubtract { + Left: lhs, + Right: parseNumberExpression(l, 31), + } + case r == '*' && minPower <= 36: + lhs = NumberExprMultiply { + Left: lhs, + Right: parseNumberExpression(l, 37), + } + case r == '/' && minPower <= 36: + lhs = NumberExprDivide { + Left: lhs, + Right: parseNumberExpression(l, 37), + } + case r == '%' && minPower <= 36: + lhs = NumberExprMod { + Left: lhs, + Right: parseNumberExpression(l, 37), + } + case r == '^' && minPower <= 40: + lhs = NumberExprExponent { + Left: lhs, + Right: parseNumberExpression(l, 41), + } + default: + l.Rewind() + break loop + } + } + + return lhs +} + +// Having just read a [ in a value subex, parse the number mapping contents up +// to but not including the closing ] +func parseNumberMapping(l RuneReader) SubexAST { + numRange := parseNumberExpression(l, 0) + var numReplace []NumberExpr + if accept(l, ":") { + if !accept(l, "]") { + for { + numReplace = append( + numReplace, + parseNumberExpression(l, 0), + ) + if !accept(l, ",") { + break + } + } + } else { + l.Rewind() + } + } else { + numReplace = []NumberExpr{NumberExprVariable{}} + } + return SubexASTNumberMapping { + Range: numRange, + Replace: numReplace, + } +} + // Having just read {, read in and parse the range contents func parseRepeatRange(l RuneReader) (output []ConvexRange) { loop: for { @@ -183,7 +348,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 @@ -216,7 +381,7 @@ func parseValueReplacement(l RuneReader, end rune) (output SubexAST) { Second: SubexASTDestructure { Destructure: NoneStructure, Structure: MapStructure, - Content: parseValueReplacement(l, ')'), + Content: parseValueReplacementOLD(l, ')'), }, } if !accept(l, "#") { @@ -258,7 +423,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") @@ -281,6 +446,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 @@ -361,8 +646,14 @@ func parseRuneReplacement(l RuneReader, end rune) (output SubexAST) { // } func parseDestructure(l RuneReader, destructure Structure, inType Type) (lhs SubexAST, outType Type) { - if !accept(l, "(") { - panic("Missing ( after destructure start") + var method rune + switch l.Next() { + case '(': + method = ')' + case '[': + method = ']' + default: + panic("Missing ( or [ after destructure start") } var innerInType Type @@ -390,8 +681,22 @@ func parseDestructure(l RuneReader, destructure Structure, inType Type) (lhs Sub resolveTypes(inType, expectedInType) lhs, innerOutType := parseSubex(l, 0, innerInType) - if !accept(l, ")") { - panic("Missing matching )") + if !accept(l, string(method)) { + panic("Missing matching ) or ]") + } + + switch method { + case ')': + case ']': + lhs = SubexASTRepeat { + Content: lhs, + Acceptable: []ConvexRange{{ + Start: -1, + End: 0, + }}, + } + default: + panic("Invalid method") } var structure Structure @@ -445,181 +750,378 @@ 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 \"") } - // TODO - // case '[': - // rangeParts := parseRangeSubex(l) - // lhs = SubexASTRange {rangeParts} - case ')', ']', '|', ';', '{', '+', '*', '/', '!', '=', '$': + resolveTypes(innerOutType, RuneType) + lhs = SubexASTDestructure { + Destructure: StringStructure, + Structure: StringStructure, + Content: lhs, + } + outType = ValueType + // RuneType + default: l.Rewind() return SubexASTEmpty{}, inType - // case '=': - // replacement := parseReplacement(l) - // lhs = SubexASTOutput{replacement} - // case '^': - // replacement := parseReplacement(l) - // replacement = append( - // []OutputContentAST{OutputValueLiteralAST {walk.NewAtomStringTerminal()}}, - // replacement... - // ) - // replacement = append( - // replacement, - // OutputValueLiteralAST {walk.NewAtomStringTerminal()}, - // ) - // lhs = SubexASTOutput {replacement} - case '.': - outType = inType - if inType == RuneType { - lhs = SubexASTCopyAnyRune{} - } else { - lhs = SubexASTCopyAnyValue{} - } - case '?': - outType = inType - lhs = SubexASTCopyBool{} - case '%': - outType = inType - lhs = SubexASTCopyNumber{} - case '`': - outType = inType + } + 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: - lhs = parseValueReplacement(l, '`') + lhs = SubexASTOutputValueLoad { + slot: slot, + } case RuneType: - lhs = parseRuneReplacement(l, '`') + lhs = SubexASTOutputRuneLoad { + slot: slot, + } default: panic("Invalid inType") } - case ' ': - if inType == RuneType { - outType = RuneType - lhs = SubexASTCopyRune {' '} - } else { - goto start + } + case '[': + switch inType { + case ValueType: + lhs = parseNumberMapping(l) + 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 - if inType == RuneType { - lhs = SubexASTCopyRune {r} - } else { - l.Rewind() - scalar, ok := parseScalarLiteral(l) - if !ok { - panic("Invalid subex") - } - lhs = SubexASTCopyScalar {scalar} + lhs = SubexASTCopyAnySimpleValue{} + case RuneType: + outType = inType + lhs = SubexASTCopyRune{','} + 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 `") } - } - 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 + case RuneType: + lhs = parseRuneReplacement(l, '`') + default: + 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 { 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 = SubexASTReciprocal {lhs} - case r == '!' && minPower <= 4: - lhs = SubexASTNot {lhs} - resolveTypes(inType, ValueType) - outType = resolveTypes(outType, ValueType) - // case r == '=' && minPower <= 4: - // lhs = SubexASTEqual {lhs} - 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") } - lhs = SubexASTOr{lhs, rhs} - /*case r == ';' && minPower <= 10: - rhs := parseSubex(l, 11, inType, outType) - if rhs == nil { - panic("Missing subex after ;") + 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 = SubexASTJoin { - Content: lhs, - Delimiter: 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 d08ddac..01a5e0d 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,24 @@ func (ast SubexASTCopyNumber) String() string { return "%" } +type SubexASTNumberFilter interface { + compile() numberFilter + computable() bool + compute() float64 +} + +// 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 { + if inType != ValueType || outType != ValueType { + panic("Invalid types for SubexASTCopyAnySimpleValue") + } + return &SubexCopyState { + next: next, + filter: simpleValueFilter{}, + } +} + // Read in any single Atom and output it unchanged type SubexASTCopyAnyValue struct {} func (ast SubexASTCopyAnyValue) compileWith(next SubexState, slotMap *SlotMap, inType Type, outType Type) SubexState { @@ -298,6 +375,21 @@ func (ast SubexASTOutput) String() string { } */ +type SubexASTNumberMapping struct { + Range NumberExpr + Replace []NumberExpr +} +func (ast SubexASTNumberMapping) compileWith(next SubexState, slotMap *SlotMap, inType Type, outType Type) SubexState { + if inType != ValueType || outType != ValueType { + panic("Invalid in/out type for SubexASTNumberMapping") + } + return &SubexNumberMappingState { + Range: ast.Range, + Replace: ast.Replace, + next: next, + } +} + type SubexASTOutputValueLiteral struct { literal walk.Scalar } @@ -365,85 +457,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), - } -} -func (ast SubexASTSum) String() string { - return fmt.Sprintf("(%v)+", ast.Content) -} - -// Like sum but for AND and product -type SubexASTProduct struct { - Content SubexAST +type SubexASTBinop struct { + op func ([]walk.Value) ([]walk.Value, error) + lhs, rhs 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 1e1e94e..bf5bab9 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,47 @@ 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 +} + +type SubexNumberMappingState struct { + Range NumberExpr + Replace []NumberExpr + next SubexState +} +func (state SubexNumberMappingState) eat(aux auxiliaryState, edible walk.Edible) []SubexBranch { + number, isNumber := edible.(walk.NumberValue) + if !isNumber || state.Range.Eval(float64(number)) == 0.0 { + return nil + } + var res []walk.Value + for _, expr := range state.Replace { + res = append(res, walk.NumberValue(expr.Eval(float64(number)))) + } + return []SubexBranch {{ + state: state.next, + aux: aux.topAppend(res), + }} +} +func (state SubexNumberMappingState) 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 { @@ -146,84 +190,6 @@ func (state SubexStoreRunesEndState) epsilon(aux auxiliaryState) []SubexBranch { }} } -/* -// A part of an output literal, either an Atom or a slot from which to load -type OutputContent interface { - // Given the current store, return the ValueList produced by the TransducerOutput - buildValues(Store) walk.ValueList - // Given the current store, return the RuneList produced by the TransducerOutput - buildRunes(Store) walk.RuneList -} - -// An OutputContent which is just a Value literal -type OutputValueLiteral struct { - value walk.Value -} -func (replacement OutputValueLiteral) buildValues(store Store) walk.ValueList { - return walk.ValueList{replacement.value} -} -func (replacement OutputValueLiteral) buildRunes(store Store) walk.RuneList { - // TODO: serialise to JSON - panic("Unimplemented!") -} - -// An OutputContent which is just a rune literal -type OutputRuneLiteral struct { - rune walk.StringRuneAtom -} -func (replacement OutputRuneLiteral) buildValues(store Store) walk.ValueList { - // TODO: Try to deserialise - panic("Unimplemented!") -} -func (replacement OutputRuneLiteral) buildRunes(store Store) walk.RuneList { - return walk.RuneList {replacement.rune} -} - -// An OutputContent which is a slot that is loaded from -type OutputLoad struct { - slot int -} -func (replacement OutputLoad) buildValues(store Store) walk.ValueList { - values, isValues := store[replacement.slot].(walk.ValueList) - if !isValues { - panic("Tried to output non-values list") - } - return values -} -func (replacement OutputLoad) buildRunes(store Store) walk.RuneList { - runes, isRunes := store[replacement.slot].(walk.RuneList) - if !isRunes { - panic("Tried to output non-runes as runes") - } - return runes -} - -// Don't read in anything, just output the series of data and slots specified -type SubexOutputState struct { - content []OutputContent - next SubexState -} -// Given a store, return what is outputted by an epsilon transition from this state -// TODO: separate into buildValues and buildRunes -func (state SubexOutputState) build(store Store) walk.ValueList { - var result walk.ValueList - for _, part := range state.content { - result = append(result, part.buildValues(store)...) - } - return result -} -func (state SubexOutputState) eat(aux auxiliaryState, char walk.Value) []SubexBranch { - content := state.build(aux.store) - nextStates := state.next.eat(aux.topAppend(content), char) - return nextStates -} -func (state SubexOutputState) accepting(aux auxiliaryState) []OutputStack { - content := state.build(aux.store) - outputStacks := state.next.accepting(aux.topAppend(content)) - return outputStacks -} -*/ - type SubexOutputValueLiteralState struct { literal walk.Scalar next SubexState |