diff options
| -rw-r--r-- | json/read.go | 2 | ||||
| -rw-r--r-- | json/write.go | 4 | ||||
| -rw-r--r-- | json/write_test.go | 57 | ||||
| -rw-r--r-- | main/command.go | 316 | ||||
| -rw-r--r-- | main/lex.go | 35 | ||||
| -rw-r--r-- | main/main.go | 111 | ||||
| -rw-r--r-- | main/main_test.go | 171 | ||||
| -rw-r--r-- | main/parse.go | 103 | ||||
| -rw-r--r-- | subex/arithmetic.go | 94 | ||||
| -rw-r--r-- | subex/filter.go | 42 | ||||
| -rw-r--r-- | subex/main.go | 315 | ||||
| -rw-r--r-- | subex/main_test.go | 783 | ||||
| -rw-r--r-- | subex/parse.go | 454 | ||||
| -rw-r--r-- | subex/subexast.go | 468 | ||||
| -rw-r--r-- | subex/subexast_test.go | 19 | ||||
| -rw-r--r-- | subex/subexstate.go | 351 | ||||
| -rw-r--r-- | subex/subexstate_test.go | 4 | ||||
| -rw-r--r-- | walk/read.go | 4 | ||||
| -rw-r--r-- | walk/walk.go | 134 | ||||
| -rw-r--r-- | walk/walk_test.go | 45 |
20 files changed, 2324 insertions, 1188 deletions
diff --git a/json/read.go b/json/read.go index f3a0a65..91589cf 100644 --- a/json/read.go +++ b/json/read.go @@ -29,7 +29,9 @@ const ( type JSONReaderState int const ( + // Immediately before a value JSONReaderStateValue JSONReaderState = iota + // Immediate after a value JSONReaderStateValueEnd ) diff --git a/json/write.go b/json/write.go index c2a220e..3a5a621 100644 --- a/json/write.go +++ b/json/write.go @@ -209,7 +209,7 @@ func (writer *JSONWriter) navigateTo(keepLen int, path []walk.PathSegment, state } func (writer *JSONWriter) inMapAt(keepLen int, path []walk.PathSegment) bool { - if keepLen < len(path) { + if len(path) != 0 { return false } @@ -222,7 +222,7 @@ func (writer *JSONWriter) inMapAt(keepLen int, path []walk.PathSegment) bool { } func (writer *JSONWriter) inArrayAt(keepLen int, path []walk.PathSegment) bool { - if keepLen < len(path) { + if len(path) != 0 { return false } diff --git a/json/write_test.go b/json/write_test.go index 05b228e..b495d94 100644 --- a/json/write_test.go +++ b/json/write_test.go @@ -222,6 +222,63 @@ func TestWrite(t *testing.T) { }, expected: `[[100],[],null,[200]]`, }, + { + values: []walk.Value { + walk.MapValue {{ + Key: "a", + Value: walk.MapValue {{ + Key: "b", + Value: walk.StringValue("map"), + }}, + }}, + walk.MapValue {{ + Key: "a", + Value: walk.ArrayValue {{ + Index: 0, + Value: walk.StringValue("array"), + }}, + }}, + }, + expected: `{"a":{"b":"map"},"a":["array"]}`, + }, + { + values: []walk.Value { + walk.ArrayValue {{ + Index: 0, + Value: walk.ArrayValue {{ + Index: 0, + Value: walk.ArrayValue {{ + Index: 1, + Value: walk.StringValue("a"), + }}, + }}, + }}, + walk.ArrayValue {{ + Index: 0, + Value: walk.ArrayValue {{ + Index: 1, + Value: walk.ArrayValue{}, + }}, + }}, + }, + expected: `[[["a"],[]]]`, + }, + { + values: []walk.Value { + walk.ArrayValue {{ + Index: 0, + Value: walk.MapValue {{ + Key: "a", + Value: walk.StringValue("a"), + }}, + }}, + walk.ArrayValue {{ + Index: 0, + Value: walk.MapValue{}, + }}, + }, + expected: `[{"a":"a"}]`, + }, } for i, test := range tests { diff --git a/main/command.go b/main/command.go index 5a898e2..bbbb036 100644 --- a/main/command.go +++ b/main/command.go @@ -13,12 +13,11 @@ type Command interface { type PrintValueCommand struct {} func (cmd PrintValueCommand) exec(state *ProgramState) { - err := state.out.Write(walk.WalkItem { - Path: state.path, - Value: state.value, - }) - if err != nil { - panic("Error while outputting") + for _, value := range state.value { + err := state.out.Write(value) + if err != nil { + panic("Error while outputting") + } } state.pc++ } @@ -28,12 +27,18 @@ func (cmd PrintValueCommand) String() string { type NextCommand struct {} func (cmd NextCommand) exec(state *ProgramState) { - nextItem, err := state.in.Read() + nextItem, err := state.Read() if err != nil { panic("Missing next value") } - state.value = nextItem.Value - state.path = nextItem.Path + + state.prevStart = nextItem.PrevStart + state.start = nextItem.Start + state.end = nextItem.End + state.nextEnd = nextItem.NextEnd + + state.value = []walk.Value{nextItem.Value} + state.pc++ } func (cmd NextCommand) String() string { @@ -42,18 +47,138 @@ func (cmd NextCommand) String() string { type AppendNextCommand struct {} func (cmd AppendNextCommand) exec(state *ProgramState) { - nextItem, err := state.in.Read() + nextItem, err := state.Read() if err != nil { panic("Missing next value") } - state.value = append(state.value, nextItem.Value...) - state.path = nextItem.Path + + state.prevStart = nextItem.PrevStart + state.start = nextItem.Start + state.end = nextItem.End + state.nextEnd = nextItem.NextEnd + + state.value = append(state.value, nextItem.Value) + state.pc++ } func (cmd AppendNextCommand) String() string { return "N" } +type SubstituteNextCommand struct { + subex subex.Transducer +} +func (cmd SubstituteNextCommand) exec(state *ProgramState) { + item, err := state.Peek() + if err != nil { + panic("Missing next value") + } + + newValue, notOk := runSubex(cmd.subex, []walk.Value{item.Value}) + + if notOk { + state.pc++ + } else { + state.Read() + state.prevStart = item.PrevStart + state.start = item.Start + state.end = item.End + state.nextEnd = item.NextEnd + state.pc += 2 + state.value = newValue + } +} +func (cmd SubstituteNextCommand) String() string { + return "n/.../" +} + +type SubstituteAppendNextCommand struct { + subex subex.Transducer +} +func (cmd SubstituteAppendNextCommand) exec(state *ProgramState) { + item, err := state.Peek() + if err != nil { + panic("Missing next value") + } + + newValue, notOk := runSubex(cmd.subex, []walk.Value{item.Value}) + + if notOk { + state.pc++ + } else { + state.Read() + state.prevStart = item.PrevStart + state.start = item.Start + state.end = item.End + state.nextEnd = item.NextEnd + state.pc += 2 + state.value = append(state.value, newValue...) + } +} +func (cmd SubstituteAppendNextCommand) String() string { + return "N/.../" +} + +type MergeCommand struct {} +func (cmd MergeCommand) exec(state *ProgramState) { + if len(state.value) <= 1 { + state.pc++ + return + } + + newVals := walk.Merge(state.value[len(state.value) - 2], state.value[len(state.value) - 1]) + state.value = append( + state.value[:len(state.value) - 2], + newVals... + ) + + state.pc++ +} +func (cmd MergeCommand) String() string { + return "m" +} + +type FullMergeCommand struct { + subex subex.Transducer +} +func (cmd FullMergeCommand) exec(state *ProgramState) { + _, 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" +} + type DeleteValueCommand struct {} func (cmd DeleteValueCommand) exec(state *ProgramState) { state.value = nil @@ -63,16 +188,7 @@ func (cmd DeleteValueCommand) String() string { return "d" } -type DeletePathCommand struct {} -func (cmd DeletePathCommand) exec(state *ProgramState) { - state.path = nil - state.pc++ -} -func (cmd DeletePathCommand) String() string { - return "D" -} - -func runSubex(state subex.Transducer, in walk.ValueList) (walk.ValueList, bool) { +func runSubex(state subex.Transducer, in []walk.Value) ([]walk.Value, bool) { out, error := subex.RunTransducer(state, in) if error { return nil, true @@ -96,20 +212,52 @@ func (cmd SubstituteValueCommand) String() string { return "s/.../" } -type SubstitutePathCommand struct { - subex subex.Transducer +type IsStartCommand struct {} +func (cmd IsStartCommand) exec(state *ProgramState) { + if state.start { + state.pc += 2 + } else { + state.pc += 1 + } } -func (cmd SubstitutePathCommand) exec(state *ProgramState) { - newPath, err := runSubex(cmd.subex, state.path) - if err { - state.pc++ +func (cmd IsStartCommand) String() string { + return "a" +} + +type IsPrevStartCommand struct {} +func (cmd IsPrevStartCommand) exec(state *ProgramState) { + if state.prevStart { + state.pc += 2 + } else { + state.pc += 1 + } +} +func (cmd IsPrevStartCommand) String() string { + return "A" +} + +type IsEndCommand struct {} +func (cmd IsEndCommand) exec(state *ProgramState) { + if state.end { + state.pc += 2 } else { + state.pc += 1 + } +} +func (cmd IsEndCommand) String() string { + return "e" +} + +type IsNextEndCommand struct {} +func (cmd IsNextEndCommand) exec(state *ProgramState) { + if state.nextEnd { state.pc += 2 - state.path = newPath + } else { + state.pc += 1 } } -func (cmd SubstitutePathCommand) String() string { - return "S/.../" +func (cmd IsNextEndCommand) String() string { + return "E" } type NoopCommand struct {} @@ -140,6 +288,38 @@ func (cmd AppendXRegCommand) String() string { return "X" } +type SubstituteToXRegCommand struct { + subex subex.Transducer +} +func (cmd SubstituteToXRegCommand) exec(state *ProgramState) { + newValue, err := runSubex(cmd.subex, state.value) + if err { + state.pc++ + } else { + state.pc += 2 + state.xreg = newValue + } +} +func (cmd SubstituteToXRegCommand) String() string { + return "x/.../" +} + +type SubstituteAppendXRegCommand struct { + subex subex.Transducer +} +func (cmd SubstituteAppendXRegCommand) exec(state *ProgramState) { + newValue, err := runSubex(cmd.subex, state.value) + if err { + state.pc++ + } else { + state.pc += 2 + state.xreg = append(state.xreg, newValue...) + } +} +func (cmd SubstituteAppendXRegCommand) String() string { + return "X/.../" +} + type SwapYRegCommand struct {} func (cmd SwapYRegCommand) exec(state *ProgramState) { v := state.value @@ -160,6 +340,38 @@ func (cmd AppendYRegCommand) String() string { return "Y" } +type SubstituteToYRegCommand struct { + subex subex.Transducer +} +func (cmd SubstituteToYRegCommand) exec(state *ProgramState) { + newValue, err := runSubex(cmd.subex, state.value) + if err { + state.pc++ + } else { + state.pc += 2 + state.yreg = newValue + } +} +func (cmd SubstituteToYRegCommand) String() string { + return "y/.../" +} + +type SubstituteAppendYRegCommand struct { + subex subex.Transducer +} +func (cmd SubstituteAppendYRegCommand) exec(state *ProgramState) { + newValue, err := runSubex(cmd.subex, state.value) + if err { + state.pc++ + } else { + state.pc += 2 + state.yreg = append(state.xreg, newValue...) + } +} +func (cmd SubstituteAppendYRegCommand) String() string { + return "Y/.../" +} + type SwapZRegCommand struct {} func (cmd SwapZRegCommand) exec(state *ProgramState) { v := state.value @@ -180,24 +392,36 @@ func (cmd AppendZRegCommand) String() string { return "Z" } -type SwapPathCommand struct {} -func (cmd SwapPathCommand) exec(state *ProgramState) { - v := state.value - state.value = state.path - state.path = v - state.pc++ +type SubstituteToZRegCommand struct { + subex subex.Transducer } -func (cmd SwapPathCommand) String() string { - return "k" +func (cmd SubstituteToZRegCommand) exec(state *ProgramState) { + newValue, err := runSubex(cmd.subex, state.value) + if err { + state.pc++ + } else { + state.pc += 2 + state.zreg = newValue + } +} +func (cmd SubstituteToZRegCommand) String() string { + return "z/.../" } -type AppendPathCommand struct {} -func (cmd AppendPathCommand) exec(state *ProgramState) { - state.path = append(state.path, state.value...) - state.pc++ +type SubstituteAppendZRegCommand struct { + subex subex.Transducer } -func (cmd AppendPathCommand) String() string { - return "K" +func (cmd SubstituteAppendZRegCommand) exec(state *ProgramState) { + newValue, err := runSubex(cmd.subex, state.value) + if err { + state.pc++ + } else { + state.pc += 2 + state.zreg = append(state.xreg, newValue...) + } +} +func (cmd SubstituteAppendZRegCommand) String() string { + return "Z/.../" } type JumpCommand struct { @@ -220,4 +444,4 @@ func (cmd BranchPlaceholderCommand) exec(state *ProgramState) { } func (cmd BranchPlaceholderCommand) String() string { return fmt.Sprintf("b%c", cmd.label) -}
\ No newline at end of file +} diff --git a/main/lex.go b/main/lex.go index 496abd0..da517cc 100644 --- a/main/lex.go +++ b/main/lex.go @@ -171,21 +171,28 @@ func lexCommand(l *lexer) stateFunc { l.ignore() r := l.next() switch r { - case eof: - l.emit(TokenEOF) - return nil - case '{': - l.emit(TokenLBrace) - return lexCommand - case '}': - l.emit(TokenRBrace) - return lexCommand - case 's', 'S': - l.emit(TokenCommand) + case eof: + l.emit(TokenEOF) + return nil + case '{': + l.emit(TokenLBrace) + return lexCommand + case '}': + l.emit(TokenRBrace) + return lexCommand + case 's', 'S', 'M': + l.emit(TokenCommand) + return lexSubstitution + case 'x', 'X', 'y', 'Y', 'z', 'Z', 'n', 'N': + l.emit(TokenCommand) + if l.peek() == '/' { return lexSubstitution - case ':', 'b': - l.emit(TokenCommand) - return lexLabel + } else { + return lexCommand + } + case ':', 'b': + l.emit(TokenCommand) + return lexLabel } if isAlpha(r) { l.emit(TokenCommand) diff --git a/main/main.go b/main/main.go index 8e8c369..bfa1afe 100644 --- a/main/main.go +++ b/main/main.go @@ -1,48 +1,53 @@ package main import ( - "os" "bufio" - "main/walk" + "io" "main/json" + "main/walk" + "os" ) -type Program []Command - type ProgramState struct { - path, value, xreg, yreg, zreg walk.ValueList + value, xreg, yreg, zreg []walk.Value + start, prevStart, end, nextEnd bool + // TODO: This will only ever have 0 or 1 values, it is a slice out of laziness + peekStack []walk.WalkItem in walk.StredReader out walk.StredWriter program []Command pc int } - -func main() { - quiet := false - var input string - hasInput := false - - for i := 1; i < len(os.Args); i += 1 { - switch os.Args[i] { - case "-n": - quiet = true - continue - } - if i < len(os.Args) - 1 { - panic("Unexpected arguments after program") - } - input = os.Args[i] - hasInput = true +func (state *ProgramState) Read() (walk.WalkItem, error) { + if len(state.peekStack) > 0 { + item := state.peekStack[len(state.peekStack) - 1] + state.peekStack = state.peekStack[:len(state.peekStack) - 1] + return item, nil } - if !hasInput { - panic("Missing program") + return state.in.Read() +} +func (state *ProgramState) Peek() (walk.WalkItem, error) { + item, err := state.Read() + if err != nil { + return walk.WalkItem{}, err } + state.peekStack = append(state.peekStack, item) + return item, nil +} + +type config struct { + quiet bool + program string + in io.Reader + out io.Writer +} - tokens := Lex(input) +func run(config config) { + tokens := Lex(config.program) program := Parse(tokens) - stdin := bufio.NewReader(os.Stdin) - stdout := bufio.NewWriter(os.Stdout) + stdin := bufio.NewReader(config.in) + stdout := bufio.NewWriter(config.out) state := ProgramState { in: json.NewJSONReader(stdin), @@ -51,27 +56,57 @@ func main() { } for { - walkItem, err := state.in.Read() + walkItem, err := state.Read() if err != nil { break } - state.value = walkItem.Value - state.path = walkItem.Path + state.value = []walk.Value{walkItem.Value} + state.start = walkItem.Start + state.prevStart = walkItem.PrevStart + state.end = walkItem.End + state.nextEnd = walkItem.NextEnd state.pc = 0 for state.pc < len(state.program) { state.program[state.pc].exec(&state) } - if !quiet { - err := state.out.Write(walk.WalkItem { - Path: state.path, - Value: state.value, - }) - if err != nil { - panic("Error while outputting") + if !config.quiet { + for _, value := range state.value { + err := state.out.Write(value) + if err != nil { + panic("Error while outputting") + } } } } state.in.AssertDone() state.out.AssertDone() -}
\ No newline at end of file +} + +func main() { + config := config { + quiet: false, + in: os.Stdin, + out: os.Stdout, + } + hasInput := false + + for i := 1; i < len(os.Args); i += 1 { + switch os.Args[i] { + case "-n": + config.quiet = true + continue + } + if i < len(os.Args) - 1 { + panic("Unexpected arguments after program") + } + config.program = os.Args[i] + hasInput = true + } + if !hasInput { + panic("Missing program") + } + + run(config) + +} diff --git a/main/main_test.go b/main/main_test.go new file mode 100644 index 0000000..076693d --- /dev/null +++ b/main/main_test.go @@ -0,0 +1,171 @@ +package main + +import ( + "strings" + "testing" +) + +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 TestSpecificCases(t *testing.T) { + type test struct { + name string + program string + quiet bool + input string + expected string + } + + tests := []test { + { + name: "Verbose Extract", + program: `s/#(~(people)~$_@(1$_#(~(first_name)~$_.|(..$_){-0})-|(..$_){-0})-|(..$_){-0})-/p`, + quiet: true, + input: miscInput, + expected: `"Tom"`, + }, + { + name: "Extract", + 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", + quiet: true, + input: miscInput, + expected: `"Tom"`, + }, + { + name: "Larger Extract", + 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", + quiet: true, + input: miscInput, + expected: `[22,18,122,48]`, + }, + { + name: "Low memory count people", + program: "aX/#(\"people\" :(#()#):)#$_ `1`/o es/#()#/{ xs/.{-0}+/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 } }", + 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 } }", + 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\")#`)@)#/ }", + 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 }}", + 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 }", + 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 }", + 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 }", + 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 { + t.Logf("Running test: %s", test.name) + + var output strings.Builder + run(config { + quiet: test.quiet, + program: test.program, + in: strings.NewReader(test.input), + out: &output, + }) + + if output.String() != test.expected { + t.Errorf("Ran '%s' and expected %s but got %s", test.program, test.expected, output.String()) + } + } +} diff --git a/main/parse.go b/main/parse.go index 141ae7e..36bd3ee 100644 --- a/main/parse.go +++ b/main/parse.go @@ -44,13 +44,7 @@ func (p *parser) parseSubex() subex.SubexAST { if subexProgramToken.typ != TokenSubex { panic("Missing subex from substitution") } - var subexProgram string - if delim.val == "=" || delim.val == "~" || delim.val == "\"" || delim.val == "`" || delim.val == "^" { - subexProgram = delim.val + subexProgramToken.val + delim.val - } else { - subexProgram = subexProgramToken.val - } - reader := subex.NewStringRuneReader(subexProgram) + reader := subex.NewStringRuneReader(subexProgramToken.val) subexAST := subex.Parse(reader) delim = p.next() if delim.typ != TokenSubstituteDelimiter { @@ -65,41 +59,90 @@ func (p *parser) parseBasicCommand(commands []Command, commandChar rune) []Comma return append(commands, PrintValueCommand{}) case 'd': return append(commands, DeleteValueCommand{}) - case 'D': - return append(commands, DeletePathCommand{}) case 'n': - return append(commands, NextCommand{}) - case 'N': - return append(commands, AppendNextCommand{}) - case 's', 'S': + delim := p.peek() + if delim.typ != TokenSubstituteDelimiter { + return append(commands, NextCommand{}) + } ast := p.parseSubex() subex := subex.CompileTransducer(ast) - switch commandChar { - case 's': - return append(commands, SubstituteValueCommand {subex}, JumpCommand {len(commands) + 3}) - case 'S': - return append(commands, SubstitutePathCommand {subex}, JumpCommand {len(commands) + 3}) - default: - panic("Unreachable!?!?") + return append(commands, SubstituteNextCommand {subex}, JumpCommand {len(commands) + 3}) + case 'N': + delim := p.peek() + if delim.typ != TokenSubstituteDelimiter { + return append(commands, AppendNextCommand{}) } + ast := p.parseSubex() + subex := subex.CompileTransducer(ast) + 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) + return append(commands, SubstituteValueCommand {subex}, JumpCommand {len(commands) + 3}) case 'o': return append(commands, NoopCommand{}) case 'x': - return append(commands, SwapXRegCommand{}) + delim := p.peek() + if delim.typ != TokenSubstituteDelimiter { + return append(commands, SwapXRegCommand{}) + } + ast := p.parseSubex() + subex := subex.CompileTransducer(ast) + return append(commands, SubstituteToXRegCommand {subex}, JumpCommand {len(commands) + 3}) case 'X': - return append(commands, AppendXRegCommand{}) + delim := p.peek() + if delim.typ != TokenSubstituteDelimiter { + return append(commands, AppendXRegCommand{}) + } + ast := p.parseSubex() + subex := subex.CompileTransducer(ast) + return append(commands, SubstituteAppendXRegCommand {subex}, JumpCommand {len(commands) + 3}) case 'y': - return append(commands, SwapYRegCommand{}) + delim := p.peek() + if delim.typ != TokenSubstituteDelimiter { + return append(commands, SwapYRegCommand{}) + } + ast := p.parseSubex() + subex := subex.CompileTransducer(ast) + return append(commands, SubstituteToYRegCommand {subex}, JumpCommand {len(commands) + 3}) case 'Y': - return append(commands, AppendYRegCommand{}) + delim := p.peek() + if delim.typ != TokenSubstituteDelimiter { + return append(commands, AppendYRegCommand{}) + } + ast := p.parseSubex() + subex := subex.CompileTransducer(ast) + return append(commands, SubstituteAppendYRegCommand {subex}, JumpCommand {len(commands) + 3}) case 'z': - return append(commands, SwapZRegCommand{}) + delim := p.peek() + if delim.typ != TokenSubstituteDelimiter { + return append(commands, SwapZRegCommand{}) + } + ast := p.parseSubex() + subex := subex.CompileTransducer(ast) + return append(commands, SubstituteToZRegCommand {subex}, JumpCommand {len(commands) + 3}) case 'Z': - return append(commands, AppendZRegCommand{}) - case 'k': - return append(commands, SwapPathCommand{}) - case 'K': - return append(commands, AppendPathCommand{}) + delim := p.peek() + if delim.typ != TokenSubstituteDelimiter { + return append(commands, AppendZRegCommand{}) + } + ast := p.parseSubex() + subex := subex.CompileTransducer(ast) + return append(commands, SubstituteAppendZRegCommand {subex}, JumpCommand {len(commands) + 3}) + case 'a': + return append(commands, IsStartCommand{}, JumpCommand {len(commands) + 3}) + case 'A': + return append(commands, IsPrevStartCommand{}, JumpCommand {len(commands) + 3}) + case 'e': + return append(commands, IsEndCommand{}, JumpCommand {len(commands) + 3}) + case 'E': + return append(commands, IsNextEndCommand{}, JumpCommand {len(commands) + 3}) case ':': labelToken := p.next() if labelToken.typ != TokenLabel { diff --git a/subex/arithmetic.go b/subex/arithmetic.go index 4cbc9db..4c87d5f 100644 --- a/subex/arithmetic.go +++ b/subex/arithmetic.go @@ -6,23 +6,23 @@ import ( "strconv" ) -func sumValues(values walk.ValueList) (walk.ValueList, error) { +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.NullScalar: + case walk.NullValue: allBools = false - case walk.BoolScalar: + case walk.BoolValue: if v { sum += 1 any = true } - case walk.NumberScalar: + case walk.NumberValue: allBools = false sum += float64(v) - case walk.StringStructure: + case walk.StringValue: allBools = false num, err := strconv.ParseFloat(string(v), 64) if err == nil { @@ -35,31 +35,31 @@ func sumValues(values walk.ValueList) (walk.ValueList, error) { } } if allBools { - return walk.ValueList{walk.BoolScalar(any)}, nil + return []walk.Value{walk.BoolValue(any)}, nil } else { - return walk.ValueList{walk.NumberScalar(sum)}, nil + return []walk.Value{walk.NumberValue(sum)}, 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.ValueList) (walk.ValueList, error) { +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.NullScalar: + case walk.NullValue: allBools = false product *= 0 - case walk.BoolScalar: + case walk.BoolValue: if !v { product *= 0 all = false } - case walk.NumberScalar: + case walk.NumberValue: allBools = false product *= float64(v) - case walk.StringStructure: + case walk.StringValue: allBools = false num, err := strconv.ParseFloat(string(v), 64) if err == nil { @@ -72,31 +72,31 @@ func multiplyValues(values walk.ValueList) (walk.ValueList, error) { } } if allBools { - return walk.ValueList{walk.BoolScalar(all)}, nil + return []walk.Value{walk.BoolValue(all)}, nil } else { - return walk.ValueList{walk.NumberScalar(product)}, nil + return []walk.Value{walk.NumberValue(product)}, nil } } // Does tries to cast all to numbers and negates them -func negateValues(values walk.ValueList) (walk.ValueList, error) { - var negatedNumbers walk.ValueList +func negateValues(values []walk.Value) ([]walk.Value, error) { + var negatedNumbers []walk.Value for _, value := range values { switch v := value.(type) { - case walk.NullScalar: - negatedNumbers = append(negatedNumbers, walk.NumberScalar(0)) - case walk.BoolScalar: + case walk.NullValue: + negatedNumbers = append(negatedNumbers, walk.NumberValue(0)) + case walk.BoolValue: if v { - negatedNumbers = append(negatedNumbers, walk.NumberScalar(-1)) + negatedNumbers = append(negatedNumbers, walk.NumberValue(-1)) } else { - negatedNumbers = append(negatedNumbers, walk.NumberScalar(0)) + negatedNumbers = append(negatedNumbers, walk.NumberValue(0)) } - case walk.NumberScalar: - negatedNumbers = append(negatedNumbers, walk.NumberScalar(-float64(v))) - case walk.StringStructure: + 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.NumberScalar(-num)) + negatedNumbers = append(negatedNumbers, walk.NumberValue(-num)) } else { return nil, errors.New("Tried to negate non-castable string") } @@ -109,24 +109,24 @@ func negateValues(values walk.ValueList) (walk.ValueList, error) { // If all are castable to numbers, takes reciprocals of all and returns them // Else errors -func reciprocalValues(values walk.ValueList) (walk.ValueList, error) { - var reciprocals walk.ValueList +func reciprocalValues(values []walk.Value) ([]walk.Value, error) { + var reciprocals []walk.Value for _, value := range values { switch v := value.(type) { - case walk.NullScalar: + case walk.NullValue: return nil, errors.New("Tried to take reciprocal of null") - case walk.BoolScalar: + case walk.BoolValue: if v { - reciprocals = append(reciprocals, walk.NumberScalar(1)) + reciprocals = append(reciprocals, walk.NumberValue(1)) } else { return nil, errors.New("Tried to take reciprocal of false") } - case walk.NumberScalar: - reciprocals = append(reciprocals, walk.NumberScalar(1 / float64(v))) - case walk.StringStructure: + 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.NumberScalar(1 / num)) + reciprocals = append(reciprocals, walk.NumberValue(1 / num)) } else { return nil, errors.New("Tried to take reciprocal of non-castable string") } @@ -139,17 +139,17 @@ func reciprocalValues(values walk.ValueList) (walk.ValueList, error) { // If all are castable to booleans, NOTs all and returns them // Else errors -func notValues(values walk.ValueList) (notted walk.ValueList, err error) { +func notValues(values []walk.Value) (notted []walk.Value, err error) { for _, value := range values { switch v := value.(type) { - case walk.NullScalar: - notted = append(notted, walk.BoolScalar(true)) - case walk.BoolScalar: - notted = append(notted, walk.BoolScalar(!bool(v))) - case walk.NumberScalar: - notted = append(notted, walk.BoolScalar(v == 0)) - case walk.StringStructure: - notted = append(notted, walk.BoolScalar(len(v) == 0)) + 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") } @@ -158,16 +158,16 @@ func notValues(values walk.ValueList) (notted walk.ValueList, err error) { } // Returns true if all values are equal, false if not -func equalValues(values walk.ValueList) (walk.ValueList, error) { +func equalValues(values []walk.Value) ([]walk.Value, error) { if len(values) == 0 { - return walk.ValueList{walk.BoolScalar(true)}, nil + 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.ValueList{walk.BoolScalar(false)}, nil + return []walk.Value{walk.BoolValue(false)}, nil } } - return walk.ValueList{walk.BoolScalar(true)}, nil + return []walk.Value{walk.BoolValue(true)}, nil } diff --git a/subex/filter.go b/subex/filter.go index 1a1b6db..309d6c7 100644 --- a/subex/filter.go +++ b/subex/filter.go @@ -17,16 +17,36 @@ func (scalar selectScalarFilter) valueFilter(value walk.Value) bool { type anyNumberFilter struct {} func (_ anyNumberFilter) valueFilter(value walk.Value) bool { - _, isNumber := value.(walk.NumberScalar) + _, isNumber := value.(walk.NumberValue) return isNumber } type anyBoolFilter struct {} func (_ anyBoolFilter) valueFilter(value walk.Value) bool { - _, isBool := value.(walk.BoolScalar) + _, isBool := value.(walk.BoolValue) 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 @@ -34,29 +54,35 @@ func (_ anyValueFilter) valueFilter(value walk.Value) bool { type anyArrayFilter struct {} func (_ anyArrayFilter) valueFilter(value walk.Value) bool { - _, isArray := value.(walk.ArrayStructure) + _, isArray := value.(walk.ArrayValue) return isArray } +type anyMapFilter struct {} +func (_ anyMapFilter) valueFilter(value walk.Value) bool { + _, isMap := value.(walk.MapValue) + return isMap +} + type anyStringFilter struct {} func (_ anyStringFilter) valueFilter(value walk.Value) bool { - _, isString := value.(walk.StringStructure) + _, isString := value.(walk.StringValue) return isString } type runeFilter interface { - runeFilter(r walk.StringRuneAtom) bool + runeFilter(r rune) bool } type anyRuneFilter struct {} -func (_ anyRuneFilter) runeFilter(r walk.StringRuneAtom) bool { +func (_ anyRuneFilter) runeFilter(r rune) bool { return true } type selectRuneFilter struct { r rune } -func (f selectRuneFilter) runeFilter(r walk.StringRuneAtom) bool { - return f.r == rune(r) +func (f selectRuneFilter) runeFilter(r rune) bool { + return f.r == r } diff --git a/subex/main.go b/subex/main.go index e2cec0b..32a5cf3 100644 --- a/subex/main.go +++ b/subex/main.go @@ -5,50 +5,96 @@ import ( ) type Transducer struct { - storeSize int + storeSize NextSlotIds initialState SubexState } -type StoreItem struct {} // Where slots are stored -type Store []walk.OutputList +type Store struct { + values [][]walk.Value + runes [][]rune +} + // Return a new store with all the data from this one func (store Store) clone() Store { - newStore := make([]walk.OutputList, len(store)) - copy(newStore, store) + newStore := Store{ + values: make([][]walk.Value, len(store.values)), + runes: make([][]rune, len(store.runes)), + } + copy(newStore.values, store.values) + copy(newStore.runes, store.runes) return newStore } + // Return a copy of this store but with an additional slot set -func (store Store) withValue(key int, value walk.OutputList) Store { +func (store Store) withValue(key int, value []walk.Value) Store { newStore := store.clone() - newStore[key] = value + newStore.values[key] = value return newStore } +func (store Store) withRunes(key int, runes []rune) Store { + newStore := store.clone() + newStore.runes[key] = runes + return newStore +} + +type SlotId struct { + id int + typ Type +} + +type NextSlotIds struct { + values int + runes int +} + type SlotMap struct { - nextId int - ids map[rune]int + next NextSlotIds + ids map[rune]SlotId } + func (m *SlotMap) getId(slot rune) int { id, exists := m.ids[slot] if exists { - return id + if id.typ != ValueType { + panic("Slot with wrong type used") + } + return id.id + } + id.id = m.next.values + id.typ = ValueType + m.next.values++ + m.ids[slot] = id + return id.id +} +func (m *SlotMap) getRuneId(slot rune) int { + id, exists := m.ids[slot] + if exists { + if id.typ != RuneType { + panic("Slot with wrong type used") + } + return id.id } - id = m.nextId - m.nextId++ + id.id = m.next.runes + id.typ = RuneType + m.next.runes++ m.ids[slot] = id - return id + return id.id } // Compile the SubexAST into a transducer SubexState that can be run func CompileTransducer(transducerAst SubexAST) Transducer { - slotMap := SlotMap { - nextId: 0, - ids: make(map[rune]int), + slotMap := SlotMap{ + next: NextSlotIds{ + values: 0, + runes: 0, + }, + ids: make(map[rune]SlotId), } - initial := transducerAst.compileWith(&SubexNoneState{}, &slotMap, false) - return Transducer { - storeSize: slotMap.nextId, + initial := transducerAst.compileWith(&SubexNoneState{}, &slotMap, ValueType, ValueType) + return Transducer{ + storeSize: slotMap.next, initialState: initial, } } @@ -58,46 +104,44 @@ type OutputStack struct { head walk.OutputList tail *OutputStack } -func (stack OutputStack) pop() (walk.OutputList, OutputStack) { - return stack.head, *stack.tail + +func (stack OutputStack) pop() ([]walk.Value, OutputStack) { + return stack.head.(walk.OutputValueList), *stack.tail } -func (stack OutputStack) push(atoms walk.OutputList) OutputStack { - return OutputStack { - head: atoms, +func (stack OutputStack) push(atoms []walk.Value) OutputStack { + return OutputStack{ + head: walk.OutputValueList(atoms), tail: &stack, } } -func (stack OutputStack) replace(atoms walk.OutputList) OutputStack { - return OutputStack { - head: atoms, +func (stack OutputStack) replace(atoms []walk.Value) OutputStack { + return OutputStack{ + head: walk.OutputValueList(atoms), tail: stack.tail, } } -func (stack OutputStack) peek() walk.OutputList { - return stack.head +func (stack OutputStack) peek() []walk.Value { + return stack.head.(walk.OutputValueList) } func topAppend(outputStack OutputStack, values []walk.Value) OutputStack { - head, isValues := outputStack.peek().(walk.ValueList) - if !isValues { - panic("Tried to append a value to an output of non-values") - } - head = append(walk.ValueList{}, head...) + head := outputStack.peek() + head = append([]walk.Value{}, head...) head = append(head, values...) return outputStack.replace(head) } -func topAppendRunes(outputStack OutputStack, runes walk.RuneList) OutputStack { - head, isRunes := outputStack.peek().(walk.RuneList) - if !isRunes { - panic("Tried to append runes to a non-rune list") - } - head = append(walk.RuneList{}, head...) +func topAppendRune(outputStack OutputStack, runes []rune) OutputStack { + head := outputStack.head.(walk.OutputRuneList) + head = append([]rune{}, head...) head = append(head, runes...) - return outputStack.replace(head) + return OutputStack{ + head: head, + tail: outputStack.tail, + } } -// Addition state that goes along with a subex state in an execution branch +// Additional state that goes along with a subex state in an execution branch type auxiliaryState struct { // Content of slots in this branch store Store @@ -106,7 +150,7 @@ type auxiliaryState struct { outputStack OutputStack // How deeply nested the current execution is inside of the overall value // i.e. starts at zero, is incremented to one when entering an array - nesting int + nesting []bool } func (aux auxiliaryState) cloneStore() auxiliaryState { @@ -114,67 +158,91 @@ func (aux auxiliaryState) cloneStore() auxiliaryState { return aux } -func (aux auxiliaryState) withValue(slot int, value walk.OutputList) auxiliaryState { +func (aux auxiliaryState) withValue(slot int, value []walk.Value) auxiliaryState { aux.store = aux.store.withValue(slot, value) return aux } -func (aux auxiliaryState) pushOutput(data walk.OutputList) auxiliaryState { +func (aux auxiliaryState) pushOutput(data []walk.Value) auxiliaryState { aux.outputStack = aux.outputStack.push(data) return aux } -func (aux auxiliaryState) popOutput() (walk.OutputList, auxiliaryState) { +func (aux auxiliaryState) pushOutputRunes(runes []rune) auxiliaryState { + tail := aux.outputStack + aux.outputStack = OutputStack{ + head: walk.OutputRuneList(runes), + tail: &tail, + } + return aux +} + +func (aux auxiliaryState) popDiscardOutput() auxiliaryState { + aux.outputStack = *aux.outputStack.tail + return aux +} + +func (aux auxiliaryState) popOutput() ([]walk.Value, auxiliaryState) { data, output := aux.outputStack.pop() aux.outputStack = output return data, aux } -func (aux auxiliaryState) topAppend(values walk.OutputList) auxiliaryState { - switch output := values.(type) { - case walk.ValueList: - aux.outputStack = topAppend(aux.outputStack, output) - case walk.RuneList: - aux.outputStack = topAppendRunes(aux.outputStack, output) - } - return aux +func (aux auxiliaryState) popOutputRunes() ([]rune, auxiliaryState) { + runes := aux.outputStack.head.(walk.OutputRuneList) + aux.outputStack = *aux.outputStack.tail + return runes, aux } -func (aux auxiliaryState) incNest() auxiliaryState { - aux.nesting++ +func (aux auxiliaryState) topAppend(values []walk.Value) auxiliaryState { + aux.outputStack = topAppend(aux.outputStack, values) return aux } -func (aux auxiliaryState) decNest() auxiliaryState { - aux.nesting-- +func (aux auxiliaryState) topAppendRune(runes []rune) auxiliaryState { + aux.outputStack = topAppendRune(aux.outputStack, runes) return aux } -// One branch of subex execution type SubexBranch struct { - // State in this branch state SubexState + aux auxiliaryState +} + +// One branch of subex execution +type SubexEatBranch struct { + // State in this branch + state SubexEatState // Axiliary state aux auxiliaryState } + // Read a single character and return all the branches resulting from this branch consuming it -func (pair SubexBranch) eat(char walk.Edible) []SubexBranch { - return pair.state.eat(pair.aux, char) +func (pair SubexEatBranch) eat(edible walk.Edible) []SubexBranch { + return pair.state.eat(pair.aux, edible) } -func (pair SubexBranch) accepting() []OutputStack { +func (pair SubexEatBranch) accepting() []OutputStack { return pair.state.accepting(pair.aux) } -func equalStates(left SubexBranch, right SubexBranch) bool { - // Only care about if they are the same pointer - return left.state == right.state && left.aux.nesting == right.aux.nesting +func equalStates(left SubexEatBranch, right SubexEatBranch) bool { + if left.state != right.state || len(left.aux.nesting) != len(right.aux.nesting) { + return false + } + for i, l := range left.aux.nesting { + if l != right.aux.nesting[i] { + return false + } + } + return true } // If two branches have the same state, only the first has a chance of being successful // This function removes all of the pointless execution branches to save execution time -func pruneStates(states []SubexBranch) []SubexBranch { +func pruneStates(states []SubexEatBranch) []SubexEatBranch { uniqueStates := 0 - outer: for _, state := range states { +outer: + for _, state := range states { for i := 0; i < uniqueStates; i++ { if equalStates(state, states[i]) { continue outer @@ -186,68 +254,95 @@ func pruneStates(states []SubexBranch) []SubexBranch { return states[:uniqueStates] } -func processInput(states []SubexBranch, input walk.StructureIter, nesting int) []SubexBranch { - if len(states) == 0 { - return states - } - var tmp []SubexBranch - newStates := make([]SubexBranch, 0, 2) - for { - piece := input.Next() - if piece == nil { - break +func addStates(curStates []SubexEatBranch, newStates []SubexBranch, nesting []bool) []SubexEatBranch { + for _, state := range newStates { + switch s := state.state.(type) { + case SubexEpsilonState: + curStates = addStates(curStates, s.epsilon(state.aux), nesting) + case SubexEatState: + curStates = append(curStates, SubexEatBranch{ + state: s, + aux: state.aux, + }) } + } + return curStates +} - // TODO: break if there are no states at this nesting level left - // TODO: What to do if there are remaining nested states after all pieces have been used? - for _, state := range states { - if state.aux.nesting == nesting { - newStates = append(newStates, state.eat(piece)...) - } else { - newStates = append(newStates, state) - } +func processInput(states []SubexEatBranch, input walk.Edible, nesting []bool) []SubexEatBranch { + newStates := make([]SubexEatBranch, 0, 2) + + for _, state := range states { + if len(state.aux.nesting) > len(nesting) { + continue } - structure, isStructure := piece.(walk.Structure) - if isStructure { - iter := structure.Iter() - newStates = processInput(newStates, iter, nesting + 1) + if (len(state.aux.nesting) == len(nesting) && + (len(state.aux.nesting) == 0 || len(nesting) == 0 || + state.aux.nesting[len(nesting) - 1] || nesting[len(nesting) - 1])) { + newStates = addStates(newStates, state.eat(input), nesting) + } else { + newStates = append(newStates, state) } + } - tmp = states - states = pruneStates(newStates) - newStates = tmp[:0] - if len(states) == 0 { - return states + switch input := input.(type) { + case walk.StringValue: + for _, r := range input { + newStates = processInput(newStates, walk.RuneEdible(r), append(nesting, true)) } + newStates = processInput(newStates, walk.StringEnd, append(nesting, true)) + case walk.ArrayValue: + for _, el := range input { + newStates = processInput(newStates, walk.NumberValue(el.Index), append(nesting, false)) + newStates = processInput(newStates, el.Value, append(nesting, true)) + } + newStates = processInput(newStates, walk.ArrayEnd, append(nesting, true)) + case walk.MapValue: + for _, el := range input { + newStates = processInput(newStates, walk.StringValue(el.Key), append(nesting, false)) + newStates = processInput(newStates, el.Value, append(nesting, true)) + } + newStates = processInput(newStates, walk.MapEnd, append(nesting, true)) } - return states + + newStates = pruneStates(newStates) + + return newStates } // Run the subex transducer -func RunTransducer(transducer Transducer, input walk.ValueList) (output []walk.Value, err bool) { - states := []SubexBranch{{ +func RunTransducer(transducer Transducer, input []walk.Value) (output []walk.Value, err bool) { + states := addStates(nil, []SubexBranch{{ state: transducer.initialState, - aux: auxiliaryState { - outputStack: OutputStack { - head: walk.ValueList{}, + aux: auxiliaryState{ + outputStack: OutputStack{ + head: walk.OutputValueList(nil), tail: nil, }, - store: make([]walk.OutputList, transducer.storeSize), - nesting: 0, + store: Store{ + values: make([][]walk.Value, transducer.storeSize.values), + runes: make([][]rune, transducer.storeSize.runes), + }, + nesting: nil, }, - }} + }}, nil) + + for _, value := range input { + if len(states) == 0 { + break + } - states = processInput(states, walk.NewValueIter(input), 0) + states = processInput(states, value, nil) + } for _, state := range states { + if len(state.aux.nesting) > 0 { + continue + } acceptingStacks := state.accepting() for _, stack := range acceptingStacks { - output, isValues := stack.head.(walk.ValueList) - if !isValues { - panic("Tried to output a non-values list") - } - return output, false + return stack.head.(walk.OutputValueList), false } } return nil, true diff --git a/subex/main_test.go b/subex/main_test.go index f0350d2..fb6f152 100644 --- a/subex/main_test.go +++ b/subex/main_test.go @@ -1,10 +1,10 @@ package subex import ( - "testing" "main/walk" - "fmt" + "reflect" "strings" + "testing" ) func buildTransducer(subex string) Transducer { @@ -14,429 +14,426 @@ func buildTransducer(subex string) Transducer { return transducer } -func fatalMismatch(t *testing.T, path walk.ValueList, message string) { - var sep string +func fmtValueList(values []walk.Value) string { var builder strings.Builder - for _, segment := range path { - builder.WriteString(sep) - builder.WriteString(segment.Debug()) - sep = "." - } - builder.WriteString(": ") - builder.WriteString(message) - t.Fatal(builder.String()) -} - -func expectEqual(t *testing.T, path walk.ValueList, output walk.Value, expected walk.Value) { - switch expected := expected.(type) { - case walk.NullScalar: - _, isNull := output.(walk.NullScalar) - if !isNull { - fatalMismatch(t, path, fmt.Sprintf("expected null, found %s", output.Debug())) - } - case walk.BoolScalar: - b, isBool := output.(walk.BoolScalar) - if !isBool { - fatalMismatch(t, path, fmt.Sprintf("expected boolean, found %s", output.Debug())) - } - if expected != b { - fatalMismatch(t, path, fmt.Sprintf("expected %s, found %s", expected.Debug(), b.Debug())) - } - case walk.NumberScalar: - n, isNumber := output.(walk.NumberScalar) - if !isNumber { - fatalMismatch(t, path, fmt.Sprintf("expected number, found %s", output.Debug())) - } - if expected != n { - fatalMismatch(t, path, fmt.Sprintf("expected %s, found %s", expected.Debug(), n.Debug())) - } - case walk.StringStructure: - s, isString := output.(walk.StringStructure) - if !isString { - fatalMismatch(t, path, fmt.Sprintf("expected string, found %s", output.Debug())) - } - if s != expected { - fatalMismatch(t, path, fmt.Sprintf("expected %s, found %s", expected.Debug(), s.Debug())) - } - case walk.ArrayStructure: - array, isArray := output.(walk.ArrayStructure) - if !isArray { - fatalMismatch(t, path, fmt.Sprintf("expected array, found %s", output.Debug())) - } - if len(array) != len(expected) { - fatalMismatch(t, path, fmt.Sprintf("Expected array length %d, found %d", len(expected), len(array))) - } - for i, value := range expected { - expectEqual(t, append(path, walk.NumberScalar(i)), array[i], value) - } - case walk.MapStructure: - m, isMap := output.(walk.MapStructure) - if !isMap { - fatalMismatch(t, path, fmt.Sprintf("expected map, found %s", output.Debug())) - } - for key, expected := range expected { - value, hasValue := m[key] - if !hasValue { - fatalMismatch(t, path, fmt.Sprintf("expected map to have key %s, but it doesn't", key)) - } - expectEqual(t, append(path, walk.StringStructure(key)), value, expected) + builder.WriteRune('[') + for i, value := range values { + if i != 0 { + builder.WriteString(", ") } - for key := range m { - _, hasValue := expected[key] - if !hasValue { - fatalMismatch(t, path, fmt.Sprintf("Didn't expect map to have key %s, but it does", key)) - } - } - default: - panic("Expected contains an invalid value") + builder.WriteString(value.Debug()) } + builder.WriteRune(']') + return builder.String() } -func expectOutput(t *testing.T, transducer Transducer, input walk.ValueList, expected walk.ValueList) { - output, err := RunTransducer(transducer, input) - - if err { - t.Fatalf("Error") - } - - if len(output) != len(expected) { - t.Fatalf("Output has incorrect length. Expected %d, got %d", len(expected), len(output)) +func TestSubexMain(t *testing.T) { + type test struct { + subex string + input []walk.Value + expected []walk.Value } - for i, value := range output { - expectEqual(t, walk.ValueList{walk.NumberScalar(i)}, value, expected[i]) - } -} - -func expectReject(t *testing.T, transducer Transducer, input walk.ValueList) { - _, err := RunTransducer(transducer, input) - - if !err { - t.Fatalf("Expected transducer to error, but it accepted input: %v", input) - } -} - -func TestSimpleProcessInput(t *testing.T) { - states := []SubexBranch{{ - state: SubexCopyState { - next: SubexNoneState{}, - filter: anyValueFilter{}, - }, - aux: auxiliaryState { - outputStack: OutputStack { - head: walk.ValueList{}, - tail: nil, + tests := []test { + { + subex: `..+`, + input: []walk.Value { + walk.NumberValue(12), + walk.NumberValue(34), }, - store: nil, - nesting: 0, - }, - }} - - input := walk.ValueList{ - walk.NumberScalar(2), - } - - states = processInput(states, walk.NewValueIter(input), 0) - - if len(states) != 1 { - t.Fatalf("States has wrong length") - } - - accepting := states[0].accepting() - - if len(accepting) != 1 { - t.Fatalf("Wrong number of accepting branches") - } - - values, isValues := accepting[0].head.(walk.ValueList) - - if !isValues { - t.Fatalf("Output is not a value list") - } - - if len(values) != 1 { - t.Fatalf("Output has wrong length") - } - - if values[0] != walk.NumberScalar(2) { - t.Fatalf("Outputted the wrong value") - } -} - -func TestTopAppendFromEmpty(t *testing.T) { - output := OutputStack { - head: walk.ValueList{}, - tail: nil, - } - - output = topAppend(output, []walk.Value{walk.NumberScalar(1), walk.NumberScalar(2)}) - - values, isValues := output.head.(walk.ValueList) - - if !isValues { - t.Fatalf("head is not values") - } - - if len(values) != 2 { - t.Fatalf("values has the wrong length") - } - - if values[0] != walk.NumberScalar(1) || values[1] != walk.NumberScalar(2) { - t.Fatalf("output has the wrong values") - } -} - -func TestArrayPriority1(t *testing.T) { - expectOutput( - t, - buildTransducer(":[.$_]|."), - walk.ValueList{ - walk.ArrayStructure{ - walk.NumberScalar(5), + expected: []walk.Value { + walk.NumberValue(46), }, }, - walk.ValueList{ - walk.ArrayStructure{}, - }, - ) -} - -func TestArrayPriority2(t *testing.T) { - expectOutput( - t, - buildTransducer(".|:[.$_]"), - walk.ValueList{ - walk.ArrayStructure{ - walk.NumberScalar(5), + { + subex: `.`, + input: []walk.Value { + walk.MapValue {{ + Key: "a", + Value: walk.StringValue("b"), + }}, }, - }, - walk.ValueList{ - walk.ArrayStructure{ - walk.NumberScalar(5), + expected: []walk.Value { + walk.MapValue {{ + Key: "a", + Value: walk.StringValue("b"), + }}, }, }, - ) -} - -func TestDropSecondArrayElement(t *testing.T) { - expectOutput( - t, - buildTransducer(":[.(.$_)(.{-0})]"), - walk.ValueList{ - walk.ArrayStructure{ - walk.NumberScalar(1), - walk.NumberScalar(2), - walk.NumberScalar(3), - walk.NumberScalar(4), + { + subex: `~(.)~`, + input: []walk.Value { + walk.StringValue("a"), }, - }, - walk.ValueList{ - walk.ArrayStructure{ - walk.NumberScalar(1), - walk.NumberScalar(3), - walk.NumberScalar(4), + expected: []walk.Value { + walk.StringValue("a"), }, }, - ) -} - -func TestDropSecondElement(t *testing.T) { - expectOutput( - t, - buildTransducer(".(.$_)(.{-0})"), - walk.ValueList{ - walk.NumberScalar(1), - walk.NumberScalar(2), - walk.NumberScalar(3), - walk.NumberScalar(4), - }, - walk.ValueList{ - walk.NumberScalar(1), - walk.NumberScalar(3), - walk.NumberScalar(4), - }, - ) -} - -func TestCopyManyValues(t *testing.T) { - expectOutput( - t, - buildTransducer(".{-0}"), - walk.ValueList{ - walk.NumberScalar(1), - walk.NumberScalar(2), - walk.NumberScalar(3), - walk.NumberScalar(4), - }, - walk.ValueList{ - walk.NumberScalar(1), - walk.NumberScalar(2), - walk.NumberScalar(3), - walk.NumberScalar(4), - }, - ) -} - -func TestCopyTwoValues(t *testing.T) { - expectOutput( - t, - buildTransducer(".."), - walk.ValueList{ - walk.NumberScalar(1), - walk.NumberScalar(2), - }, - walk.ValueList{ - walk.NumberScalar(1), - walk.NumberScalar(2), - }, - ) -} - -func TestCopyValue(t *testing.T) { - expectOutput( - t, - buildTransducer("."), - walk.ValueList{ - walk.NumberScalar(1), - }, - walk.ValueList{ - walk.NumberScalar(1), - }, - ) -} - -func TestSimpleArrayEntry(t *testing.T) { - expectOutput( - t, - buildTransducer(":[..]"), - walk.ValueList{ - walk.ArrayStructure{ - walk.NumberScalar(1), - walk.NumberScalar(2), + { + subex: `~(.$_(.{-0}))~`, + input: []walk.Value { + walk.StringValue("hello"), + }, + expected: []walk.Value { + walk.StringValue("ello"), }, }, - walk.ValueList{ - walk.ArrayStructure{ - walk.NumberScalar(1), - walk.NumberScalar(2), + { + subex: `#(".".{-0})-`, + input: []walk.Value { + walk.MapValue { + { + Key: "a", + Value: walk.NullValue{}, + }, + }, + }, + expected: []walk.Value { + walk.StringValue("a"), + walk.NullValue{}, }, }, - ) -} - -func TestArrayEntrySum(t *testing.T) { - expectOutput( - t, - buildTransducer(":[%{-0}+]"), - walk.ValueList{ - walk.ArrayStructure{ - walk.NumberScalar(1), - walk.NumberScalar(7), - walk.NumberScalar(8), - walk.NumberScalar(3), + { + subex: "@(..$a`$a$a`{-0})@", + input: []walk.Value { + walk.ArrayValue { + walk.ArrayElement { + Index: 0, + Value: walk.NullValue{}, + }, + walk.ArrayElement { + Index: 0, + Value: walk.BoolValue(true), + }, + walk.ArrayElement { + Index: 0, + Value: walk.NumberValue(5.4), + }, + walk.ArrayElement { + Index: 5, + Value: walk.StringValue("hello"), + }, + walk.ArrayElement { + Index: 3, + Value: walk.ArrayValue { + walk.ArrayElement { + Index: 0, + Value: walk.NullValue{}, + }, + }, + }, + walk.ArrayElement { + Index: 1, + Value: walk.MapValue { + walk.MapElement { + Key: "key", + Value: walk.StringValue("value"), + }, + }, + }, + }, + }, + expected: []walk.Value { + walk.ArrayValue { + walk.ArrayElement { + Index: 0, + Value: walk.NullValue{}, + }, + walk.ArrayElement { + Index: 0, + Value: walk.NullValue{}, + }, + walk.ArrayElement { + Index: 0, + Value: walk.BoolValue(true), + }, + walk.ArrayElement { + Index: 0, + Value: walk.BoolValue(true), + }, + walk.ArrayElement { + Index: 0, + Value: walk.NumberValue(5.4), + }, + walk.ArrayElement { + Index: 0, + Value: walk.NumberValue(5.4), + }, + walk.ArrayElement { + Index: 5, + Value: walk.StringValue("hello"), + }, + walk.ArrayElement { + Index: 5, + Value: walk.StringValue("hello"), + }, + walk.ArrayElement { + Index: 3, + Value: walk.ArrayValue { + walk.ArrayElement { + Index: 0, + Value: walk.NullValue{}, + }, + }, + }, + walk.ArrayElement { + Index: 3, + Value: walk.ArrayValue { + walk.ArrayElement { + Index: 0, + Value: walk.NullValue{}, + }, + }, + }, + walk.ArrayElement { + Index: 1, + Value: walk.MapValue { + walk.MapElement { + Key: "key", + Value: walk.StringValue("value"), + }, + }, + }, + walk.ArrayElement { + Index: 1, + Value: walk.MapValue { + walk.MapElement { + Key: "key", + Value: walk.StringValue("value"), + }, + }, + }, + }, }, }, - walk.ValueList{ - walk.ArrayStructure{ - walk.NumberScalar(19), + { + subex: "-(`0`.)@", + input: []walk.Value { + walk.NumberValue(4), + }, + expected: []walk.Value { + walk.ArrayValue { + { + Index: 0, + Value: walk.NumberValue(4), + }, + }, }, }, - ) -} - -func TestStringEmptyMatch(t *testing.T) { - expectOutput( - t, - buildTransducer("~\"\""), - walk.ValueList{ - walk.StringStructure(""), + { + subex: `@(.$_~(.{-0})-{-0})~`, + input: []walk.Value { + walk.ArrayValue { + { + Index: 0, + Value: walk.StringValue("ab"), + }, + { + Index: 1, + Value: walk.StringValue("cd"), + }, + { + Index: 2, + Value: walk.StringValue("efg"), + }, + { + Index: 3, + Value: walk.StringValue(""), + }, + { + Index: 4, + Value: walk.StringValue("hijklm"), + }, + }, + }, + expected: []walk.Value { + walk.StringValue("abcdefghijklm"), + }, }, - walk.ValueList{ - walk.StringStructure(""), + { + subex: ":(.)-", + input: []walk.Value { + walk.ArrayValue { + { + Index: 0, + Value: walk.NullValue{}, + }, + }, + }, + expected: []walk.Value { + walk.NullValue{}, + }, }, - ) -} - -func TestStringSimpleMatch(t *testing.T) { - expectOutput( - t, - buildTransducer("~\"hello\""), - walk.ValueList{ - walk.StringStructure("hello"), + { + subex: ":(.{-0}+)-", + input: []walk.Value { + walk.ArrayValue { + { + Index: 0, + Value: walk.NumberValue(4), + }, + { + Index: 1, + Value: walk.NumberValue(-123), + }, + { + Index: 2, + Value: walk.NumberValue(124), + }, + }, + }, + expected: []walk.Value { + walk.NumberValue(5), + }, }, - walk.ValueList{ - walk.StringStructure("hello"), + { + subex: "~(-(.)~{-0}):", + input: []walk.Value { + walk.StringValue("abc"), + }, + expected: []walk.Value { + walk.ArrayValue { + { + Index: 0, + Value: walk.StringValue("a"), + }, + { + Index: 0, + Value: walk.StringValue("b"), + }, + { + Index: 0, + Value: walk.StringValue("c"), + }, + }, + }, }, - ) -} - -func TestDiscardString(t *testing.T) { - expectOutput( - t, - buildTransducer("~\"test\"$_."), - walk.ValueList{ - walk.StringStructure("test"), - walk.NumberScalar(2), + { + subex: "#(.(.$_){-0}):", + input: []walk.Value { + walk.MapValue { + { + Key: "a", + Value: walk.NullValue{}, + }, + { + Key: "b", + Value: walk.NumberValue(4), + }, + { + Key: "c", + Value: walk.StringValue("hello"), + }, + }, + }, + expected: []walk.Value { + walk.ArrayValue { + { + Index: 0, + Value: walk.StringValue("a"), + }, + { + Index: 0, + Value: walk.StringValue("b"), + }, + { + Index: 0, + Value: walk.StringValue("c"), + }, + }, + }, }, - walk.ValueList{ - walk.NumberScalar(2), + { + subex: ":(.`null`{-0})#", + input: []walk.Value { + walk.ArrayValue { + { + Index: 0, + Value: walk.StringValue("a"), + }, + { + Index: 1, + Value: walk.StringValue("b"), + }, + { + Index: 2, + Value: walk.StringValue("c"), + }, + }, + }, + expected: []walk.Value { + walk.MapValue { + { + Key: "a", + Value: walk.NullValue{}, + }, + { + Key: "b", + Value: walk.NullValue{}, + }, + { + Key: "c", + Value: walk.NullValue{}, + }, + }, + }, }, - ) -} - -func TestStringThenValue(t *testing.T) { - expectOutput( - t, - buildTransducer("~\"test\"."), - walk.ValueList{ - walk.StringStructure("test"), - walk.NumberScalar(2), + { + subex: `#(".$_(.{-0})".{-0})#`, + input: []walk.Value { + walk.MapValue { + { + Key: "hello", + Value: walk.NullValue{}, + }, + { + Key: "world", + Value: walk.NullValue{}, + }, + }, + }, + expected: []walk.Value { + walk.MapValue { + { + Key: "ello", + Value: walk.NullValue{}, + }, + { + Key: "orld", + Value: walk.NullValue{}, + }, + }, + }, }, - walk.ValueList{ - walk.StringStructure("test"), - walk.NumberScalar(2), + { + subex: ".{-0}`\"hello\"`", + input: []walk.Value { + walk.NumberValue(1), + walk.NumberValue(2), + }, + expected: []walk.Value { + walk.NumberValue(1), + walk.NumberValue(2), + walk.StringValue("hello"), + }, }, - ) -} + } -func TestCutStringFromStart(t *testing.T) { - //transducer := buildTransducer("~\"test\"$_(.{-0})") - lexer := NewStringRuneReader("~\"test\"$_(.{-0})") - ast := Parse(lexer) - t.Log(ast) - transducer := CompileTransducer(ast) + for i, test := range tests { + t.Logf("Running test: %d", i) + lexer := NewStringRuneReader(test.subex) + ast := Parse(lexer) + transducer := CompileTransducer(ast) + output, err := RunTransducer(transducer, test.input) + + if err { + t.Errorf("Subex %q rejected input %v", test.subex, fmtValueList(test.input)) + t.Logf("AST: %v", ast) + continue + } - expectOutput( - t, - transducer, - walk.ValueList{ - walk.StringStructure("test"), - walk.NumberScalar(2), - walk.StringStructure("test"), - }, - walk.ValueList{ - walk.NumberScalar(2), - walk.StringStructure("test"), - }, - ) - expectOutput( - t, - transducer, - walk.ValueList{ - walk.StringStructure("test"), - }, - walk.ValueList{}, - ) - expectReject( - t, - transducer, - walk.ValueList{ - walk.StringStructure("yeet"), - }, - ) - expectReject( - t, - transducer, - walk.ValueList{}, - ) + if !reflect.DeepEqual(output, test.expected) { + t.Errorf("Subex %q transformed input %s to output %s", test.subex, fmtValueList(test.input), fmtValueList(output)) + } + } } diff --git a/subex/parse.go b/subex/parse.go index 35baaa2..e91008a 100644 --- a/subex/parse.go +++ b/subex/parse.go @@ -1,11 +1,66 @@ package subex import ( + "fmt" "main/walk" "strconv" "strings" ) +type Type int +const ( + AnyType Type = iota + ValueType + RuneType +) + +func resolveTypes(t1 Type, t2 Type) Type { + if t1 == AnyType { + return t2 + } + + if t2 == AnyType { + return t1 + } + + if t1 == t2 { + return t1 + } + + panic("Types don't match in parser") +} + +type Structure int +const ( + NoneStructure Structure = iota + StringStructure + ArrayStructure + ArrayValuesStructure + MapStructure +) +func (s Structure) String() string { + switch s { + case NoneStructure: + return "-" + case StringStructure: + return "~" + case ArrayStructure: + return "@" + case ArrayValuesStructure: + return ":" + case MapStructure: + return "#" + default: + panic("Invalid structure") + } +} + +type DestructureMethod int +const ( + Normal DestructureMethod = iota + Iterate +) + type RuneReader interface { Next() rune Rewind() @@ -45,28 +100,29 @@ func parseScalarLiteral(l RuneReader) (walk.Scalar, bool) { if err != nil { panic("Invalid number literal") } - return walk.NumberScalar(number), true + return walk.NumberValue(number), true } switch r { case 'n': if accept(l, "u") && accept(l, "l") && accept(l, "l") { - return walk.NullScalar{}, true + return walk.NullValue{}, true } else { panic("Invalid literal") } case 't': if accept(l, "r") && accept(l, "u") && accept(l, "e") { - return walk.BoolScalar(true), true + return walk.BoolValue(true), true } else { panic("Invalid literal") } case 'f': if accept(l, "a") && accept(l, "l") && accept(l, "s") && accept(l, "e") { - return walk.BoolScalar(false), true + return walk.BoolValue(false), true } else { panic("Invalid literal") } default: + fmt.Printf("%c\n", r) panic("Invalid literal") } } @@ -133,34 +189,99 @@ func parseRepeatRange(l RuneReader) (output []ConvexRange) { return output } -// TODO: Consider if it's worth making better use of the go type system to enforce output being all runes or all values -func parseReplacement(l RuneReader, runic bool) (output []OutputContentAST) { +func parseValueReplacement(l RuneReader, end rune) (output SubexAST) { + output = SubexASTEmpty{} // TODO escaping // TODO add arrays, maps and strings loop: for { r := l.Next() switch r { - case eof: - panic("Missing closing `") - case '`': - break loop - case '$': - slot := l.Next() - if slot == eof { - panic("Missing slot character") - } - output = append(output, OutputLoadAST{slot: slot}) - default: - if runic { - output = append(output, OutputRuneLiteralAST {walk.StringRuneAtom(r)}) - } else { - l.Rewind() - scalar, ok := parseScalarLiteral(l) - if !ok { - panic("Invalid scalar literal") - } - output = append(output, OutputValueLiteralAST {scalar}) - } + case eof: + panic("Missing closing `") + case ' ': + case end: + break loop + case '$': + slot := l.Next() + if slot == eof { + panic("Missing slot character") + } + output = SubexASTConcat { + First: output, + Second: SubexASTOutputValueLoad { + slot: slot, + }, + } + // TODO: destructures + case '#': + if !accept(l, "(") { + panic("Missing ( after #") + } + output = SubexASTConcat { + First: output, + Second: SubexASTDestructure { + Destructure: NoneStructure, + Structure: MapStructure, + Content: parseValueReplacement(l, ')'), + }, + } + if !accept(l, "#") { + panic("Missing # after )") + } + case '"': + output = SubexASTConcat { + First: output, + Second: SubexASTDestructure { + Destructure: NoneStructure, + Structure: StringStructure, + Content: parseRuneReplacement(l, '"'), + }, + } + default: + l.Rewind() + scalar, ok := parseScalarLiteral(l) + if !ok { + panic("Invalid scalar literal") + } + output = SubexASTConcat { + First: output, + Second: SubexASTOutputValueLiteral { + literal: scalar, + }, + } + } + } + return output +} + +func parseRuneReplacement(l RuneReader, end rune) (output SubexAST) { + output = SubexASTEmpty{} + // TODO escaping + loop: for { + r := l.Next() + switch r { + case eof: + panic("Missing closing `") + case end: + break loop + case '$': + slot := l.Next() + if slot == eof { + panic("Missing slot character") + } + output = SubexASTConcat { + First: output, + Second: SubexASTOutputRuneLoad { + slot: slot, + }, + } + default: + output = SubexASTConcat { + First: output, + Second: SubexASTOutputRuneLiteral { + literal: r, + }, + } } } return output @@ -245,92 +366,197 @@ func parseReplacement(l RuneReader, runic bool) (output []OutputContentAST) { // return parts // } -func parseSubex(l RuneReader, minPower int, runic bool) SubexAST { - var lhs SubexAST +func parseDestructure(l RuneReader, destructure Structure, inType Type) (lhs SubexAST, outType Type) { + var method rune + switch l.Next() { + case '(': + method = ')' + case '[': + method = ']' + default: + panic("Missing ( or [ after destructure start") + } + + var innerInType Type + var expectedInType Type + switch destructure { + case NoneStructure: + innerInType = inType + expectedInType = inType + case StringStructure: + innerInType = RuneType + expectedInType = ValueType + case ArrayStructure: + innerInType = ValueType + expectedInType = ValueType + case ArrayValuesStructure: + innerInType = ValueType + expectedInType = ValueType + case MapStructure: + innerInType = ValueType + expectedInType = ValueType + default: + panic("Invalid structure") + } + + resolveTypes(inType, expectedInType) + + lhs, innerOutType := parseSubex(l, 0, innerInType) + 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 + var expectedInnerOutType Type + r := l.Next() + switch r { + case '-': + structure = NoneStructure + expectedInnerOutType = innerOutType + case '~': + structure = StringStructure + expectedInnerOutType = RuneType + case '@': + structure = ArrayStructure + expectedInnerOutType = ValueType + case ':': + structure = ArrayValuesStructure + expectedInnerOutType = ValueType + case '#': + structure = MapStructure + expectedInnerOutType = ValueType + default: + panic("Missing matching destructure") + } + + innerOutType = resolveTypes(innerOutType, expectedInnerOutType) + + switch structure { + case NoneStructure: + outType = innerOutType + case StringStructure: + outType = ValueType + case ArrayStructure: + outType = ValueType + case ArrayValuesStructure: + outType = ValueType + case MapStructure: + outType = ValueType + } + + lhs = SubexASTDestructure { + Destructure: destructure, + Structure: structure, + Content: lhs, + } + + return lhs, outType +} + +func parseSubex(l RuneReader, minPower int, inType Type) (lhs SubexAST, outType Type) { + start: r := l.Next() switch r { case eof: - return nil + return nil, inType case '(': - lhs = parseSubex(l, 0, runic) + 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 + } // TODO // case '[': // rangeParts := parseRangeSubex(l) // lhs = SubexASTRange {rangeParts} - case ')', ']', '"', '|', ';', '{', '+', '-', '*', '/', '!', '=', '$': + case ')', ']', '|', ';', '{', '+', '*', '/', '!', '=', '$': l.Rewind() - return SubexASTEmpty{} - // 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} + return SubexASTEmpty{}, inType case '.': - if runic { + outType = inType + if inType == RuneType { lhs = SubexASTCopyAnyRune{} } else { lhs = SubexASTCopyAnyValue{} } + case ',': + switch inType { + case ValueType: + outType = inType + lhs = SubexASTCopyAnySimpleValue{} + case RuneType: + outType = inType + lhs = SubexASTCopyRune{','} + default: + panic("Invalid inType") + } case '?': + outType = inType lhs = SubexASTCopyBool{} case '%': + outType = inType lhs = SubexASTCopyNumber{} - case ':': - if runic { - lhs = SubexASTCopyRune {':'} - } else { - if !accept(l, "[") { - panic("Missing [ after :") - } - lhs = SubexASTEnterArray {parseSubex(l, 0, runic)} - if !accept(l, "]") { - panic("Missing matching ]") - } - } case '`': - lhs = SubexASTOutput {parseReplacement(l, runic)} - case '~': - if runic { - lhs = SubexASTCopyRune {'~'} + outType = inType + switch inType { + case ValueType: + lhs = parseValueReplacement(l, '`') + case RuneType: + lhs = parseRuneReplacement(l, '`') + default: + panic("Invalid inType") + } + case ' ': + if inType == RuneType { + outType = RuneType + lhs = SubexASTCopyRune {' '} } else { - if !accept(l, "\"") { - panic("Missing \" after ~") - } - lhs = SubexASTEnterString {parseSubex(l, 0, true)} - if !accept(l, "\"") { - panic("Missing matching \"") - } + goto start } - // TODO - // case '_': - // lhs = SubexASTCopyStringAtom{} - // case '#': - // lhs = SubexASTCopyString{} - // case ',': - // lhs = SubexASTCopyValue{} - // case '"': - // lhs = SubexASTCopyScalar {walk.NewAtomStringTerminal()} - // case '~': - // literals := parseNonStringLiteral(l) - // var replacement []OutputContentAST - // for _, literal := range literals { - // replacement = append(replacement, OutputValueLiteralAST {literal}) - // } - // lhs = SubexASTOutput {replacement} default: - if runic { + outType = inType + if inType == RuneType { lhs = SubexASTCopyRune {r} } else { l.Rewind() @@ -343,8 +569,10 @@ func parseSubex(l RuneReader, minPower int, runic bool) SubexAST { } loop: for { if minPower <= 20 { - next := parseSubex(l, 21, runic) + 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 } @@ -358,54 +586,58 @@ func parseSubex(l RuneReader, minPower int, runic bool) SubexAST { } case r == '+' && minPower <= 4: lhs = SubexASTSum {lhs} + resolveTypes(inType, ValueType) + outType = resolveTypes(outType, ValueType) case r == '*' && minPower <= 4: lhs = SubexASTProduct {lhs} - case r == '-' && minPower <= 4: - lhs = SubexASTNegate {lhs} - case r == '/' && minPower <= 4: - lhs = SubexASTReciprocal {lhs} + resolveTypes(inType, ValueType) + outType = resolveTypes(outType, ValueType) case r == '!' && minPower <= 4: lhs = SubexASTNot {lhs} - case r == '=' && minPower <= 4: - lhs = SubexASTEqual {lhs} + resolveTypes(inType, ValueType) + outType = resolveTypes(outType, ValueType) case r == '$' && minPower <= 4: slot := l.Next() if slot == eof { panic("Missing slot character") } if slot == '_' { - lhs = SubexASTDiscard {lhs} + lhs = SubexASTDiscard { + Content: lhs, + InnerOutType: outType, + } } else { - lhs = SubexASTStore{ - Match: lhs, - Slot: slot, + if inType == ValueType { + lhs = SubexASTStoreValues { + Match: lhs, + Slot: slot, + } + } else { + lhs = SubexASTStoreRunes { + Match: lhs, + Slot: slot, + } } } + outType = AnyType case r == '|' && minPower <= 8: - rhs := parseSubex(l, 9, runic) + rhs, outType2 := parseSubex(l, 9, inType) + outType = resolveTypes(outType, outType2) if rhs == nil { panic("Missing subex after |") } lhs = SubexASTOr{lhs, rhs} - case r == ';' && minPower <= 10: - rhs := parseSubex(l, 11, runic) - if rhs == nil { - panic("Missing subex after ;") - } - lhs = SubexASTJoin{ - Content: lhs, - Delimiter: rhs, - } default: l.Rewind() break loop } } - return lhs + return lhs, outType } func Parse(l RuneReader) SubexAST { - ast := parseSubex(l, 0, false) + ast, outType := parseSubex(l, 0, ValueType) + outType = resolveTypes(outType, ValueType) if ast == nil { return SubexASTEmpty{} } diff --git a/subex/subexast.go b/subex/subexast.go index e02091d..655a783 100644 --- a/subex/subexast.go +++ b/subex/subexast.go @@ -7,54 +7,72 @@ import ( // A node in the AST of a subex type SubexAST interface { - compileWith(next SubexState, slotMap *SlotMap, runic bool) SubexState + compileWith(next SubexState, slotMap *SlotMap, inType Type, outType Type) SubexState } // Process the first subex, then the second, splitting the input text in two type SubexASTConcat struct { First, Second SubexAST } -func (ast SubexASTConcat) compileWith(next SubexState, slotMap *SlotMap, runic bool) SubexState { - return ast.First.compileWith(ast.Second.compileWith(next, slotMap, runic), slotMap, runic) +func (ast SubexASTConcat) compileWith(next SubexState, slotMap *SlotMap, inType Type, outType Type) SubexState { + return ast.First.compileWith( + ast.Second.compileWith(next, slotMap, inType, outType), + slotMap, + inType, + outType, + ) } func (ast SubexASTConcat) String() string { return fmt.Sprintf("(%v)(%v)", ast.First, ast.Second) } // Processing a subex and storing the output in a slot instead of outputting it -type SubexASTStore struct { +type SubexASTStoreValues struct { Match SubexAST Slot rune } -func (ast SubexASTStore) compileWith(next SubexState, slotMap *SlotMap, runic bool) SubexState { +func (ast SubexASTStoreValues) 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, runic) + }, slotMap, inType, ValueType) - if !runic { - return &SubexCaptureBeginState { - next: newNext, - } - } else { - return &SubexCaptureRunesBeginState { - next: newNext, - } + return &SubexCaptureBeginState { + next: newNext, } } -func (ast SubexASTStore) String() string { +func (ast SubexASTStoreValues) String() string { return fmt.Sprintf("$%c(%v)", ast.Slot, ast.Match) } +type SubexASTStoreRunes struct { + Match SubexAST + Slot rune +} +func (ast SubexASTStoreRunes) compileWith(next SubexState, slotMap *SlotMap, inType Type, outType Type) SubexState { + id := slotMap.getRuneId(ast.Slot) + newNext := ast.Match.compileWith(&SubexStoreRunesEndState { + slot: id, + next: next, + }, slotMap, inType, RuneType) + + return &SubexCaptureRunesBeginState { + next: newNext, + } +} +func (ast SubexASTStoreRunes) String() string { + return fmt.Sprintf("(%v)$%c", ast.Match, ast.Slot) +} + // Try to run the first subex, if it fails then backtrack and use the second type SubexASTOr struct { First, Second SubexAST } -func (ast SubexASTOr) compileWith(next SubexState, slotMap *SlotMap, runic bool) SubexState { +func (ast SubexASTOr) compileWith(next SubexState, slotMap *SlotMap, inType Type, outType Type) SubexState { return &SubexGroupState { - ast.First.compileWith(next, slotMap, runic), - ast.Second.compileWith(next, slotMap, runic), + ast.First.compileWith(next, slotMap, inType, outType), + ast.Second.compileWith(next, slotMap, inType, outType), } } func (ast SubexASTOr) String() string { @@ -84,19 +102,24 @@ func (cr ConvexRange) decrement() ConvexRange { return ConvexRange{cr.Start - 1, cr.End - 1} } } -func (cr ConvexRange) compile(content SubexAST, next SubexState, slotMap *SlotMap, runic bool) SubexState { +func (cr ConvexRange) compile(content SubexAST, next SubexState, slotMap *SlotMap, inType Type, outType Type) SubexState { min, _ := cr.minmax() if min != 0 { - return content.compileWith(cr.decrement().compile(content, next, slotMap, runic), slotMap, runic) + return content.compileWith( + cr.decrement().compile(content, next, slotMap, inType, outType), + slotMap, + inType, + outType, + ) } if cr.Start == -1 { state := &SubexGroupState {nil, next} - state.first = content.compileWith(state, slotMap, runic) + state.first = content.compileWith(state, slotMap, inType, outType) return state } if cr.End == -1 { state := &SubexGroupState {next, nil} - state.second = content.compileWith(state, slotMap, runic) + state.second = content.compileWith(state, slotMap, inType, outType) return state } @@ -104,7 +127,7 @@ func (cr ConvexRange) compile(content SubexAST, next SubexState, slotMap *SlotMa state := next; for i := 0; i < cr.Start; i += 1 { state = &SubexGroupState { - content.compileWith(state, slotMap, runic), + content.compileWith(state, slotMap, inType, outType), next, } } @@ -114,7 +137,7 @@ func (cr ConvexRange) compile(content SubexAST, next SubexState, slotMap *SlotMa for i := 0; i < cr.End; i += 1 { state = &SubexGroupState { next, - content.compileWith(state, slotMap, runic), + content.compileWith(state, slotMap, inType, outType), } } return state @@ -127,10 +150,10 @@ type SubexASTRepeat struct { Content SubexAST Acceptable []ConvexRange } -func (ast SubexASTRepeat) compileWith(next SubexState, slotMap *SlotMap, runic bool) SubexState { +func (ast SubexASTRepeat) compileWith(next SubexState, slotMap *SlotMap, inType Type, outType Type) SubexState { var state SubexState = &SubexDeadState{} for _, convex := range ast.Acceptable { - state = &SubexGroupState {state, convex.compile(ast.Content, next, slotMap, runic)} + state = &SubexGroupState {state, convex.compile(ast.Content, next, slotMap, inType, outType)} } return state } @@ -142,7 +165,10 @@ func (ast SubexASTRepeat) String() string { type SubexASTCopyScalar struct { Scalar walk.Scalar } -func (ast SubexASTCopyScalar) compileWith(next SubexState, slotMap *SlotMap, runic bool) SubexState { +func (ast SubexASTCopyScalar) compileWith(next SubexState, slotMap *SlotMap, inType Type, outType Type) SubexState { + if inType != ValueType || outType != ValueType { + panic("Invalid types for SubexASTCopyScalar") + } return &SubexCopyState{ filter: selectScalarFilter {ast.Scalar}, next: next, @@ -153,26 +179,41 @@ func (ast SubexASTCopyScalar) String() string { } type SubexASTCopyAnyRune struct {} -func (ast SubexASTCopyAnyRune) compileWith(next SubexState, slotMap *SlotMap, runic bool) SubexState { +func (ast SubexASTCopyAnyRune) compileWith(next SubexState, slotMap *SlotMap, inType Type, outType Type) SubexState { + if inType != RuneType || outType != RuneType { + panic("Invalid types for SubexASTCopyAnyRune") + } return &SubexCopyRuneState { next: next, filter: anyRuneFilter{}, } } +func (ast SubexASTCopyAnyRune) String() string { + return ".RUNE" +} type SubexASTCopyRune struct { rune rune } -func (ast SubexASTCopyRune) compileWith(next SubexState, slotMap *SlotMap, runic bool) SubexState { +func (ast SubexASTCopyRune) compileWith(next SubexState, slotMap *SlotMap, inType Type, outType Type) SubexState { + if inType != RuneType || outType != RuneType { + panic("Invalid types for SubexASTCopyRune") + } return &SubexCopyRuneState { next: next, filter: selectRuneFilter {ast.rune}, } } +func (ast SubexASTCopyRune) String() string { + return string(ast.rune) +} // Read in a single atom that must be a boolean and output it unchanged type SubexASTCopyBool struct {} -func (ast SubexASTCopyBool) compileWith(next SubexState, slotMap *SlotMap, runic bool) SubexState { +func (ast SubexASTCopyBool) compileWith(next SubexState, slotMap *SlotMap, inType Type, outType Type) SubexState { + if inType != ValueType || outType != ValueType { + panic("Invalid types for SubexASTCopyBool") + } return &SubexCopyState { next: next, filter: anyBoolFilter{}, @@ -184,7 +225,10 @@ func (ast SubexASTCopyBool) String() string { // Read in a single atom that must be a number and output it unchanged type SubexASTCopyNumber struct {} -func (ast SubexASTCopyNumber) compileWith(next SubexState, slotMap *SlotMap, runic bool) SubexState { +func (ast SubexASTCopyNumber) compileWith(next SubexState, slotMap *SlotMap, inType Type, outType Type) SubexState { + if inType != ValueType || outType != ValueType { + panic("Invalid types for SubexASTCopyNumber") + } return &SubexCopyState { next: next, filter: anyNumberFilter{}, @@ -194,34 +238,24 @@ func (ast SubexASTCopyNumber) String() string { return "%" } -// Read in a full string value and copy it out unchanged -// # is equivalent to "_{-0}" -// TODO -// type SubexASTCopyString struct {} -// func (ast SubexASTCopyString) compileWith(next SubexState, slotMap *SlotMap) SubexState { -// stringAtomState := &SubexCopyStringAtomState { -// next: nil, -// } -// stringContentState := &SubexGroupState { -// &SubexCopyScalarState { -// scalar: walk.NewAtomStringTerminal(), -// next: next, -// }, -// stringAtomState, -// } -// stringAtomState.next = stringContentState -// return &SubexCopyScalarState { -// scalar: walk.NewAtomStringTerminal(), -// next: stringContentState, -// } -// } -// func (ast SubexASTCopyString) String() string { -// return "#" -// } +// 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, runic bool) SubexState { +func (ast SubexASTCopyAnyValue) compileWith(next SubexState, slotMap *SlotMap, inType Type, outType Type) SubexState { + if inType != ValueType || outType != ValueType { + panic("Invalid types for SubexASTCopyAnyValue") + } return &SubexCopyState { next: next, filter: anyValueFilter{}, @@ -231,6 +265,7 @@ func (ast SubexASTCopyAnyValue) String() string { return "." } +/* type OutputContentAST interface { compile(slotMap *SlotMap) OutputContent } @@ -273,25 +308,58 @@ func (ast SubexASTOutput) compileWith(next SubexState, slotMap *SlotMap, runic b func (ast SubexASTOutput) String() string { return "=...=" } +*/ -// Read in a repeated subex separated by a delimiter. Greedy -type SubexASTJoin struct { - Content, Delimiter SubexAST +type SubexASTOutputValueLiteral struct { + literal walk.Scalar } -func (ast SubexASTJoin) compileWith(next SubexState, slotMap *SlotMap, runic bool) SubexState { - afterContentState := &SubexGroupState { - nil, - next, +func (ast SubexASTOutputValueLiteral) compileWith(next SubexState, slotMap *SlotMap, inType Type, outType Type) SubexState { + if outType != ValueType { + panic("Invalid outType for SubexASTOutputValueLiteral") } - manyContentsState := ast.Content.compileWith(afterContentState, slotMap, runic) - afterContentState.first = ast.Delimiter.compileWith(manyContentsState, slotMap, runic) - return &SubexGroupState { - manyContentsState, - next, + return &SubexOutputValueLiteralState { + literal: ast.literal, + next: next, + } +} + +type SubexASTOutputValueLoad struct { + slot rune +} +func (ast SubexASTOutputValueLoad) compileWith(next SubexState, slotMap *SlotMap, inType Type, outType Type) SubexState { + if outType != ValueType { + panic("Invalid outType for SubexASTOutputValueLoad") + } + return &SubexOutputValueLoadState { + slot: slotMap.getId(ast.slot), + next: next, + } +} + +type SubexASTOutputRuneLiteral struct { + literal rune +} +func (ast SubexASTOutputRuneLiteral) compileWith(next SubexState, slotMap *SlotMap, inType Type, outType Type) SubexState { + if outType != RuneType { + panic("Invalid outType for SubexASTOutputRuneLiteral") + } + return &SubexOutputRuneLiteralState { + literal: ast.literal, + next: next, } } -func (ast SubexASTJoin) String() string { - return fmt.Sprintf("(%v);(%v)", ast.Content, ast.Delimiter) + +type SubexASTOutputRuneLoad struct { + slot rune +} +func (ast SubexASTOutputRuneLoad) compileWith(next SubexState, slotMap *SlotMap, inType Type, outType Type) SubexState { + if outType != RuneType { + panic("Invalid outType for SubexASTOutputRuneLoad") + } + return &SubexOutputRuneLoadState { + slot: slotMap.getRuneId(ast.slot), + next: next, + } } // Run each input Atom through a map to produce an output Atom @@ -314,12 +382,15 @@ func (ast SubexASTJoin) String() string { type SubexASTSum struct { Content SubexAST } -func (ast SubexASTSum) compileWith(next SubexState, slotMap *SlotMap, runic bool) SubexState { +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, runic), + }, slotMap, inType, outType), } } func (ast SubexASTSum) String() string { @@ -330,12 +401,15 @@ func (ast SubexASTSum) String() string { type SubexASTProduct struct { Content SubexAST } -func (ast SubexASTProduct) compileWith(next SubexState, slotMap *SlotMap, runic bool) SubexState { +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, runic), + }, slotMap, inType, outType), } } func (ast SubexASTProduct) String() string { @@ -347,12 +421,15 @@ func (ast SubexASTProduct) String() string { type SubexASTNegate struct { Content SubexAST } -func (ast SubexASTNegate) compileWith(next SubexState, slotMap *SlotMap, runic bool) SubexState { +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, runic), + }, slotMap, inType, outType), } } func (ast SubexASTNegate) String() string { @@ -360,58 +437,29 @@ func (ast SubexASTNegate) String() string { } // Runs the content Subex and collects the output -// If it is a list of atoms castable to numbers, it takes the reciprocal of them all and outputs them -// Else it rejects -type SubexASTReciprocal struct { - Content SubexAST -} -func (ast SubexASTReciprocal) compileWith(next SubexState, slotMap *SlotMap, runic bool) SubexState { - return &SubexCaptureBeginState { - next: ast.Content.compileWith(&SubexArithmeticEndState { - next: next, - calculate: reciprocalValues, - }, slotMap, runic), - } -} -func (ast SubexASTReciprocal) 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, runic bool) SubexState { +func (ast SubexASTNot) compileWith(next SubexState, slotMap *SlotMap, inType Type, outType Type) SubexState { + if inType != ValueType || outType != ValueType { + panic("Invalid types for SubexASTNot") + } return &SubexCaptureBeginState { next: ast.Content.compileWith(&SubexArithmeticEndState { next: next, calculate: notValues, - }, slotMap, runic), + }, slotMap, ValueType, ValueType), } } func (ast SubexASTNot) String() string { return fmt.Sprintf("(%v)!", ast.Content) } -// Runs the content Subex and collects the output -// Replaces it with true if all output values are equal and false otherwise -type SubexASTEqual struct { - Content SubexAST -} -func (ast SubexASTEqual) compileWith(next SubexState, slotMap *SlotMap, runic bool) SubexState { - return &SubexCaptureBeginState { - next: ast.Content.compileWith(&SubexArithmeticEndState { - next: next, - calculate: equalValues, - }, slotMap, runic), - } -} - // Does nothing type SubexASTEmpty struct {} -func (ast SubexASTEmpty) compileWith(next SubexState, slotMap *SlotMap, runic bool) SubexState { +func (ast SubexASTEmpty) compileWith(next SubexState, slotMap *SlotMap, inType Type, outType Type) SubexState { return next } func (ast SubexASTEmpty) String() string { @@ -421,10 +469,11 @@ func (ast SubexASTEmpty) String() string { // Discards the output from the content subex type SubexASTDiscard struct { Content SubexAST + InnerOutType Type } -func (ast SubexASTDiscard) compileWith(next SubexState, slotMap *SlotMap, runic bool) SubexState { - newNext := ast.Content.compileWith(&SubexDiscardState {next}, slotMap, runic) - if !runic { +func (ast SubexASTDiscard) compileWith(next SubexState, slotMap *SlotMap, inType Type, outType Type) SubexState { + newNext := ast.Content.compileWith(&SubexDiscardState {next}, slotMap, inType, ast.InnerOutType) + if inType == ValueType { return &SubexCaptureBeginState { next: newNext, } @@ -438,57 +487,170 @@ func (ast SubexASTDiscard) String() string { return fmt.Sprintf("(%v)$_", ast.Content) } -// Go into an array, pass the content each of the values in the array to eat and then leave the array -type SubexASTEnterArray struct { +type SubexASTDestructure struct { + Destructure Structure + Structure Structure Content SubexAST } -func (ast SubexASTEnterArray) compileWith(next SubexState, slotMap *SlotMap, runic bool) SubexState { - return &SubexCaptureBeginState { - next: &SubexIncrementNestState { +func (ast SubexASTDestructure) compileWith(next SubexState, slotMap *SlotMap, inType Type, outType Type) SubexState { + var innerOutType Type + var construct SubexState + switch ast.Structure { + case NoneStructure: + innerOutType = outType + construct = next + case StringStructure: + innerOutType = RuneType + construct = &SubexConstructStringState { + next: next, + } + case ArrayStructure: + innerOutType = ValueType + construct = &SubexConstructArrayState { + next: next, + } + case ArrayValuesStructure: + innerOutType = ValueType + construct = &SubexConstructArrayValuesState { + next: next, + } + case MapStructure: + innerOutType = ValueType + construct = &SubexConstructMapState { + next: next, + } + default: + panic("Invalid ast structure") + } + + var innerInType Type + var destructFooter SubexState + switch ast.Destructure { + case NoneStructure: + innerInType = inType + destructFooter = construct + case StringStructure: + innerInType = RuneType + destructFooter = &SubexDiscardTerminalState { + terminal: walk.StringEnd, + next: &SubexDecrementNestState { + next: construct, + }, + } + case ArrayStructure: + innerInType = ValueType + destructFooter = &SubexDiscardTerminalState { + terminal: walk.ArrayEnd, + next: &SubexDecrementNestState { + next: construct, + }, + } + case ArrayValuesStructure: + innerInType = ValueType + destructFooter = &SubexDiscardTerminalState { + terminal: walk.ArrayEnd, + next: &SubexDecrementNestState { + next: construct, + }, + } + case MapStructure: + innerInType = ValueType + destructFooter = &SubexDiscardTerminalState { + terminal: walk.MapEnd, + next: &SubexDecrementNestState { + next: construct, + }, + } + default: + panic("Invalid ast destructure") + } + + inner := ast.Content.compileWith( + destructFooter, + slotMap, + innerInType, + innerOutType, + ) + + var beginConstruct SubexState + switch ast.Structure { + case NoneStructure: + beginConstruct = inner + case StringStructure: + beginConstruct = &SubexCaptureRunesBeginState { + next: inner, + } + case ArrayStructure: + beginConstruct = &SubexCaptureBeginState { + next: inner, + } + case ArrayValuesStructure: + beginConstruct = &SubexCaptureBeginState { + next: inner, + } + case MapStructure: + beginConstruct = &SubexCaptureBeginState { + next: inner, + } + default: + panic("Invalid ast structure") + } + + switch ast.Destructure { + case NoneStructure: + return beginConstruct + case StringStructure: + return &SubexCaptureBeginState { + next: &SubexCopyState { + filter: anyStringFilter{}, + next: &SubexDiscardState { + next: &SubexIncrementNestState { + keys: true, + next: beginConstruct, + }, + }, + }, + } + case ArrayStructure: + return &SubexCaptureBeginState { next: &SubexCopyState { filter: anyArrayFilter{}, next: &SubexDiscardState { - next: &SubexCaptureBeginState { - next: ast.Content.compileWith( - &SubexDiscardTerminalState { - terminal: walk.ArrayEndTerminal{}, - next: &SubexDecrementNestState { - next: &SubexConstructArrayState {next: next}, - }, - }, - slotMap, - runic, - ), + next: &SubexIncrementNestState { + keys: true, + next: beginConstruct, }, }, }, - }, - } -} - -type SubexASTEnterString struct { - Content SubexAST -} -func (ast SubexASTEnterString) compileWith(next SubexState, slotMap *SlotMap, runic bool) SubexState { - return &SubexCaptureBeginState { - next: &SubexIncrementNestState { + } + case ArrayValuesStructure: + return &SubexCaptureBeginState { next: &SubexCopyState { - filter: anyStringFilter{}, + filter: anyArrayFilter{}, + next: &SubexDiscardState { + next: &SubexIncrementNestState { + keys: false, + next: beginConstruct, + }, + }, + }, + } + case MapStructure: + return &SubexCaptureBeginState { + next: &SubexCopyState { + filter: anyMapFilter{}, next: &SubexDiscardState { - next: &SubexCaptureRunesBeginState { - next: ast.Content.compileWith( - &SubexDecrementNestState { - next: &SubexDiscardTerminalState { - terminal: walk.StringEndTerminal{}, - next: &SubexConstructStringState {next: next}, - }, - }, - slotMap, - true, - ), + next: &SubexIncrementNestState { + keys: true, + next: beginConstruct, }, }, }, - }, + } + default: + panic("Invalid destructure in ast") } } +func (ast SubexASTDestructure) String() string { + return fmt.Sprintf("%v(%v)%v", ast.Destructure, ast.Content, ast.Structure) +} diff --git a/subex/subexast_test.go b/subex/subexast_test.go deleted file mode 100644 index 156162e..0000000 --- a/subex/subexast_test.go +++ /dev/null @@ -1,19 +0,0 @@ -package subex - -import ( - "testing" -) - -func expectASTEqual(t *testing.T, ast SubexAST, expected SubexAST) { - if ast == expected { - return - } - - t.Fatalf("Expected %v, found %v", expected, ast) -} - -func expectAST(t *testing.T, subex string, expected SubexAST) { - lexer := NewStringRuneReader(subex) - ast := Parse(lexer) - expectASTEqual(t, ast, expected) -} diff --git a/subex/subexstate.go b/subex/subexstate.go index 0b21c93..8f27a10 100644 --- a/subex/subexstate.go +++ b/subex/subexstate.go @@ -4,13 +4,24 @@ package subex // e.g. Combine all of the copy states into a single type that has a filter function import ( + "fmt" "main/walk" + "strings" ) -// A state of execution for the transducer type SubexState interface { +} + +type SubexEpsilonState interface { + SubexState + epsilon(aux auxiliaryState) []SubexBranch +} + +// A state of execution for the transducer +type SubexEatState interface { + SubexState // Eat a Atom and transition to any number of new states - eat(aux auxiliaryState, char walk.Edible) []SubexBranch + eat(aux auxiliaryState, edible walk.Edible) []SubexBranch // Find accepting states reachable through epsilon transitions and return their outputs accepting(aux auxiliaryState) []OutputStack } @@ -19,13 +30,18 @@ type SubexState interface { type SubexGroupState struct { first, second SubexState } -func (state SubexGroupState) eat(aux auxiliaryState, char walk.Edible) []SubexBranch { +func (state SubexGroupState) epsilon(aux auxiliaryState) []SubexBranch { otherAux := aux.cloneStore() - return append(state.first.eat(aux, char), state.second.eat(otherAux, char)...) -} -func (state SubexGroupState) accepting(aux auxiliaryState) []OutputStack { - otherAux := aux.cloneStore() - return append(state.first.accepting(aux), state.second.accepting(otherAux)...) + return []SubexBranch { + { + state: state.first, + aux: aux, + }, + { + state: state.second, + aux: otherAux, + }, + } } type SubexCopyState struct { @@ -39,7 +55,7 @@ func (state SubexCopyState) eat(aux auxiliaryState, edible walk.Edible) []SubexB } return []SubexBranch{{ state: state.next, - aux: aux.topAppend(walk.ValueList{value}), + aux: aux.topAppend([]walk.Value{value}), }} } func (state SubexCopyState) accepting(aux auxiliaryState) []OutputStack { @@ -51,29 +67,32 @@ type SubexCopyRuneState struct { filter runeFilter } func (state SubexCopyRuneState) eat(aux auxiliaryState, edible walk.Edible) []SubexBranch { - r, isRune := edible.(walk.StringRuneAtom) - if !isRune || !state.filter.runeFilter(r) { + r, isRune := edible.(walk.RuneEdible) + if !isRune || !state.filter.runeFilter(rune(r)) { return nil } return []SubexBranch{{ state: state.next, - aux: aux.topAppend(walk.RuneList{r}), + aux: aux.topAppendRune([]rune{rune(r)}), }} } func (state SubexCopyRuneState) accepting(aux auxiliaryState) []OutputStack { return nil } +func (state SubexCopyRuneState) String() string { + return fmt.Sprintf("SubexCopyRuneState[%v]", state.filter) +} // 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 { next SubexState } -func (state SubexCaptureBeginState) eat(aux auxiliaryState, char walk.Edible) []SubexBranch { - return state.next.eat(aux.pushOutput(walk.ValueList{}), char) -} -func (state SubexCaptureBeginState) accepting(aux auxiliaryState) []OutputStack { - return state.next.accepting(aux.pushOutput(walk.ValueList{})) +func (state SubexCaptureBeginState) epsilon(aux auxiliaryState) []SubexBranch { + return []SubexBranch {{ + state: state.next, + aux: aux.pushOutput(nil), + }} } func (state SubexCaptureBeginState) String() string { return "CaptureBeginState" @@ -82,24 +101,22 @@ func (state SubexCaptureBeginState) String() string { type SubexCaptureRunesBeginState struct { next SubexState } -func (state SubexCaptureRunesBeginState) eat(aux auxiliaryState, char walk.Edible) []SubexBranch { - return state.next.eat(aux.pushOutput(walk.RuneList{}), char) -} -func (state SubexCaptureRunesBeginState) accepting(aux auxiliaryState) []OutputStack { - return state.next.accepting(aux.pushOutput(walk.RuneList{})) +func (state SubexCaptureRunesBeginState) epsilon(aux auxiliaryState) []SubexBranch { + return []SubexBranch {{ + state: state.next, + aux: aux.pushOutputRunes(nil), + }} } // Discard the top of the OutputStack type SubexDiscardState struct { next SubexState } -func (state SubexDiscardState) eat(aux auxiliaryState, char walk.Edible) []SubexBranch { - _, newAux := aux.popOutput() - return state.next.eat(newAux, char) -} -func (state SubexDiscardState) accepting(aux auxiliaryState) []OutputStack { - _, newAux := aux.popOutput() - return state.next.accepting(newAux) +func (state SubexDiscardState) epsilon(aux auxiliaryState) []SubexBranch { + return []SubexBranch {{ + state: state.next, + aux: aux.popDiscardOutput(), + }} } // Pop the top of the OutputStack which contains the stuff outputted since the start of the store @@ -108,96 +125,74 @@ type SubexStoreEndState struct { slot int next SubexState } -func (state SubexStoreEndState) eat(aux auxiliaryState, char walk.Edible) []SubexBranch { +func (state SubexStoreEndState) epsilon(aux auxiliaryState) []SubexBranch { toStore, aux := aux.popOutput() - aux = aux.withValue(state.slot, toStore) - return state.next.eat(aux, char) -} -func (state SubexStoreEndState) accepting(aux auxiliaryState) []OutputStack { - toStore, aux := aux.popOutput() - aux = aux.withValue(state.slot, toStore) - return state.next.accepting(aux) -} - -// 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 + return []SubexBranch {{ + state: state.next, + aux: aux.withValue(state.slot, toStore), + }} } -// 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} +type SubexStoreRunesEndState struct { + slot int + next SubexState } -func (replacement OutputValueLiteral) buildRunes(store Store) walk.RuneList { - // TODO: serialise to JSON - panic("Unimplemented!") +func (state SubexStoreRunesEndState) epsilon(aux auxiliaryState) []SubexBranch { + toStore, aux := aux.popOutputRunes() + aux.store = aux.store.withRunes(state.slot, toStore) + return []SubexBranch {{ + state: state.next, + aux: aux, + }} } -// 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!") +type SubexOutputValueLiteralState struct { + literal walk.Scalar + next SubexState } -func (replacement OutputRuneLiteral) buildRunes(store Store) walk.RuneList { - return walk.RuneList {replacement.rune} +func (state SubexOutputValueLiteralState) epsilon(aux auxiliaryState) []SubexBranch { + return []SubexBranch {{ + state: state.next, + aux: aux.topAppend([]walk.Value {state.literal}), + }} } -// An OutputContent which is a slot that is loaded from -type OutputLoad struct { +type SubexOutputValueLoadState struct { slot int + next SubexState } -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 +func (state SubexOutputValueLoadState) epsilon(aux auxiliaryState) []SubexBranch { + return []SubexBranch {{ + state: state.next, + aux: aux.topAppend(aux.store.values[state.slot]), + }} } -// Don't read in anything, just output the series of data and slots specified -type SubexOutputState struct { - content []OutputContent +type SubexOutputRuneLiteralState struct { + literal rune 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 SubexOutputRuneLiteralState) epsilon(aux auxiliaryState) []SubexBranch { + return []SubexBranch {{ + state: state.next, + aux: aux.topAppendRune([]rune {state.literal}), + }} } -func (state SubexOutputState) eat(aux auxiliaryState, char walk.Edible) []SubexBranch { - content := state.build(aux.store) - nextStates := state.next.eat(aux.topAppend(content), char) - return nextStates + +type SubexOutputRuneLoadState struct { + slot int + next SubexState } -func (state SubexOutputState) accepting(aux auxiliaryState) []OutputStack { - content := state.build(aux.store) - outputStacks := state.next.accepting(aux.topAppend(content)) - return outputStacks +func (state SubexOutputRuneLoadState) epsilon(aux auxiliaryState) []SubexBranch { + return []SubexBranch {{ + state: state.next, + aux: aux.topAppendRune(aux.store.runes[state.slot]), + }} } // A final state, transitions to nothing but is accepting type SubexNoneState struct {} -func (state SubexNoneState) eat(aux auxiliaryState, char walk.Edible) []SubexBranch { +func (state SubexNoneState) eat(aux auxiliaryState, edible walk.Edible) []SubexBranch { return nil } func (state SubexNoneState) accepting(aux auxiliaryState) []OutputStack { @@ -206,7 +201,7 @@ func (state SubexNoneState) accepting(aux auxiliaryState) []OutputStack { // A dead end state, handy for making internals work nicer but technically redundant type SubexDeadState struct {} -func (state SubexDeadState) eat(aux auxiliaryState, char walk.Edible) []SubexBranch { +func (state SubexDeadState) eat(aux auxiliaryState, edible walk.Edible) []SubexBranch { return nil } func (state SubexDeadState) accepting (aux auxiliaryState) []OutputStack { @@ -239,31 +234,18 @@ func (state SubexDeadState) accepting (aux auxiliaryState) []OutputStack { type SubexArithmeticEndState struct { next SubexState - calculate func(walk.ValueList) (walk.ValueList, error) -} -func (state SubexArithmeticEndState) eat(aux auxiliaryState, char walk.Edible) []SubexBranch { - toCompute, aux := aux.popOutput() - values, isValues := toCompute.(walk.ValueList) - if !isValues { - panic("Tried to do arithmetic on non-values") - } - result, err := state.calculate(values) - if err != nil { - return nil - } - return state.next.eat(aux.topAppend(result), char) + calculate func([]walk.Value) ([]walk.Value, error) } -func (state SubexArithmeticEndState) accepting(aux auxiliaryState) []OutputStack { - toCompute, aux := aux.popOutput() - values, isValues := toCompute.(walk.ValueList) - if !isValues { - panic("Tried to do arithmetic on non-values") - } +func (state SubexArithmeticEndState) epsilon(aux auxiliaryState) []SubexBranch { + values, aux := aux.popOutput() result, err := state.calculate(values) if err != nil { return nil } - return state.next.accepting(aux.topAppend(result)) + return []SubexBranch {{ + state: state.next, + aux: aux.topAppend(result), + }} } type SubexDiscardTerminalState struct { @@ -286,55 +268,102 @@ func (state SubexDiscardTerminalState) accepting(aux auxiliaryState) []OutputSta type SubexConstructArrayState struct { next SubexState } -func (state SubexConstructArrayState) eat(aux auxiliaryState, edible walk.Edible) []SubexBranch { - outputs, aux := aux.popOutput() - values, isValues := outputs.(walk.ValueList) - if !isValues { - panic("Tried to create an array from non-values") +func (state SubexConstructArrayState) epsilon(aux auxiliaryState) []SubexBranch { + values, aux := aux.popOutput() + var array walk.ArrayValue + if len(values) % 2 != 0 { + panic("Tried to construct array with odd length input") } - array := walk.ArrayStructure(values) - return state.next.eat(aux.topAppend(walk.ValueList{array}), edible) -} -func (state SubexConstructArrayState) accepting(aux auxiliaryState) []OutputStack { - outputs, aux := aux.popOutput() - values, isValues := outputs.(walk.ValueList) - if !isValues { - panic("Tried to create an array from non-values") + for i := 0; i < len(values); i += 2 { + index, isNum := values[i].(walk.NumberValue) + if !isNum { + panic("Tried to construct array with non-numeric index") + } + array = append(array, walk.ArrayElement { + Index: int(index), + Value: values[i + 1], + }) } - array := walk.ArrayStructure(values) - return state.next.accepting(aux.topAppend(walk.ValueList{array})) + return []SubexBranch {{ + state: state.next, + aux: aux.topAppend([]walk.Value {array}), + }} } -type SubexConstructStringState struct { +type SubexConstructArrayValuesState struct { + next SubexState +} +func (state SubexConstructArrayValuesState) epsilon(aux auxiliaryState) []SubexBranch { + values, aux := aux.popOutput() + var array walk.ArrayValue + for _, v := range values { + array = append(array, walk.ArrayElement { + Index: 0, + Value: v, + }) + } + return []SubexBranch {{ + state: state.next, + aux: aux.topAppend([]walk.Value {array}), + }} +} + +type SubexConstructMapState struct { next SubexState } -func (state SubexConstructStringState) eat(aux auxiliaryState, edible walk.Edible) []SubexBranch { - outputs, aux := aux.popOutput() - runes, isRunes := outputs.(walk.RuneList) - if !isRunes { - panic("Tried to create a string from non-runes") +func (state SubexConstructMapState) epsilon(aux auxiliaryState) []SubexBranch { + values, aux := aux.popOutput() + var m walk.MapValue + if len(values) % 2 != 0 { + panic("Tried to construct array with odd length input") } - s := walk.StringStructure(runes) - return state.next.eat(aux.topAppend(walk.ValueList{s}), edible) -} -func (state SubexConstructStringState) accepting(aux auxiliaryState) []OutputStack { - outputs, aux := aux.popOutput() - runes, isRunes := outputs.(walk.RuneList) - if !isRunes { - panic("Tried to create a string from non-runes") + for i := 0; i < len(values); i += 2 { + key, isNum := values[i].(walk.StringValue) + if !isNum { + panic("Tried to construct array with non-numeric index") + } + m = append(m, walk.MapElement { + Key: string(key), + Value: values[i + 1], + }) } - s := walk.StringStructure(runes) - return state.next.accepting(aux.topAppend(walk.ValueList{s})) + return []SubexBranch {{ + state: state.next, + aux: aux.topAppend([]walk.Value {m}), + }} } -type SubexIncrementNestState struct { +type SubexConstructStringState struct { next SubexState } -func (state SubexIncrementNestState) eat(aux auxiliaryState, edible walk.Edible) []SubexBranch { - return state.next.eat(aux.incNest(), edible) +func (state SubexConstructStringState) construct(runes []rune) []walk.Value { + var builder strings.Builder + for _, r := range runes { + builder.WriteRune(r) + } + return []walk.Value{walk.StringValue(builder.String())} +} +func (state SubexConstructStringState) epsilon(aux auxiliaryState) []SubexBranch { + runes, aux := aux.popOutputRunes() + return []SubexBranch {{ + state: state.next, + aux: aux.topAppend(state.construct(runes)), + }} +} +func (state SubexConstructStringState) String() string { + return "SubexConstructStringState" } -func (state SubexIncrementNestState) accepting(aux auxiliaryState) []OutputStack { - return state.next.accepting(aux.incNest()) + +type SubexIncrementNestState struct { + keys bool + next SubexState +} +func (state SubexIncrementNestState) epsilon(aux auxiliaryState) []SubexBranch { + aux.nesting = append(aux.nesting, state.keys) + return []SubexBranch {{ + state: state.next, + aux: aux, + }} } func (state SubexIncrementNestState) String() string { return "IncrementNestState" @@ -343,9 +372,11 @@ func (state SubexIncrementNestState) String() string { type SubexDecrementNestState struct { next SubexState } -func (state SubexDecrementNestState) eat(aux auxiliaryState, edible walk.Edible) []SubexBranch { - return state.next.eat(aux.decNest(), edible) -} -func (state SubexDecrementNestState) accepting(aux auxiliaryState) []OutputStack { - return state.next.accepting(aux.decNest()) +func (state SubexDecrementNestState) epsilon(aux auxiliaryState) []SubexBranch { + aux.nesting = aux.nesting[:len(aux.nesting) - 1] + // aux.nestingValue will be set in addStates + return []SubexBranch {{ + state: state.next, + aux: aux, + }} } diff --git a/subex/subexstate_test.go b/subex/subexstate_test.go deleted file mode 100644 index 4eb8969..0000000 --- a/subex/subexstate_test.go +++ /dev/null @@ -1,4 +0,0 @@ -package subex - -import ( -) diff --git a/walk/read.go b/walk/read.go index f25109c..5aedafb 100644 --- a/walk/read.go +++ b/walk/read.go @@ -6,6 +6,6 @@ type StredReader interface { } type StredWriter interface { - Write(WalkItem) error + Write(Value) error AssertDone() -}
\ No newline at end of file +} diff --git a/walk/walk.go b/walk/walk.go index fc9e9de..e66feff 100644 --- a/walk/walk.go +++ b/walk/walk.go @@ -7,7 +7,41 @@ import ( type PathSegment interface {} +type OutputList interface { + outputList() +} + +type OutputValueList []Value +func (_ OutputValueList) outputList() {} + +type OutputRuneList []rune +func (_ OutputRuneList) outputList() {} + +// Can be passed to .eat on a state +type Edible interface { + edible() +} + +type RuneEdible rune +func (_ RuneEdible) edible() {} + +type Terminal int +const ( + ArrayEnd Terminal = iota + MapEnd + StringEnd +) +func (_ Terminal) edible() {} + +// Simple value +// Has a literal +type Scalar interface { + Value + scalar() +} + type Value interface { + Edible value() Debug() string } @@ -17,6 +51,8 @@ func (_ NullValue) value() {} func (_ NullValue) Debug() string { return "null" } +func (_ NullValue) edible() {} +func (_ NullValue) scalar() {} type BoolValue bool func (_ BoolValue) value() {} @@ -26,24 +62,23 @@ func (b BoolValue) Debug() string { } return "false" } +func (_ BoolValue) edible() {} +func (_ BoolValue) scalar() {} type NumberValue float64 func (_ NumberValue) value() {} func (n NumberValue) Debug() string { return fmt.Sprintf("%v", float64(n)) } - -type RuneValue rune -func (_ RuneValue) value() {} -func (r RuneValue) Debug() string { - return string(r) -} +func (_ NumberValue) edible() {} +func (_ NumberValue) scalar() {} type StringValue string func (_ StringValue) value() {} func (s StringValue) Debug() string { return fmt.Sprintf("%q", string(s)) } +func (_ StringValue) edible() {} type ArrayElement struct { Index int @@ -66,6 +101,7 @@ func (array ArrayValue) Debug() string { builder.WriteRune(']') return builder.String() } +func (_ ArrayValue) edible() {} type MapElement struct { Key string @@ -88,6 +124,7 @@ func (m MapValue) Debug() string { builder.WriteRune('}') return builder.String() } +func (_ MapValue) edible() {} type WalkItem struct { Value Value @@ -111,3 +148,88 @@ func (item WalkItem) Debug() string { builder.WriteString(item.Value.Debug()) return builder.String() } + +func Merge(first Value, second Value) []Value { + switch first := first.(type) { + case NullValue: + return []Value {first, second} + case BoolValue: + return []Value {first, second} + case NumberValue: + return []Value {first, second} + case StringValue: + return []Value {first, second} + case ArrayValue: + secondArr, isArr := second.(ArrayValue) + if !isArr { + return []Value {first, second} + } + + if len(first) == 0 { + return []Value {second} + } + + if len(secondArr) == 0 { + return []Value {first} + } + + var res ArrayValue + for _, el := range first[:len(first) - 1] { + res = append(res, el) + } + midFirst := first[len(first) - 1] + midSecond := secondArr[0] + if midFirst.Index == midSecond.Index { + for _, el := range Merge(midFirst.Value, midSecond.Value) { + res = append(res, ArrayElement { + Index: midFirst.Index, + Value: el, + }) + } + } else { + res = append(res, midFirst, midSecond) + } + for _, el := range secondArr[1:] { + res = append(res, el) + } + + return []Value {res} + case MapValue: + secondMap, isMap := second.(MapValue) + if !isMap { + return []Value {first, second} + } + + if len(first) == 0 { + return []Value {second} + } + + if len(secondMap) == 0 { + return []Value {first} + } + + var res MapValue + for _, el := range first[:len(first) - 1] { + res = append(res, el) + } + midFirst := first[len(first) - 1] + midSecond := secondMap[0] + if midFirst.Key == midSecond.Key { + for _, el := range Merge(midFirst.Value, midSecond.Value) { + res = append(res, MapElement { + Key: midFirst.Key, + Value: el, + }) + } + } else { + res = append(res, midFirst, midSecond) + } + for _, el := range secondMap[1:] { + res = append(res, el) + } + + return []Value {res} + default: + panic("first is invalid value type") + } +} diff --git a/walk/walk_test.go b/walk/walk_test.go deleted file mode 100644 index 759c501..0000000 --- a/walk/walk_test.go +++ /dev/null @@ -1,45 +0,0 @@ -package walk - -import ( - "testing" - "log" -) - -func TestValueIter(t *testing.T) { - values := ValueList{ - NumberValue(1), - NumberValue(2), - NumberValue(3), - } - - valuesCopy := ValueList{} - - iter := NewValueIter(values) - - for { - edible := iter.Next() - if edible == nil { - break - } - - log.Println(edible) - - value, isValue := edible.(Value) - - if !isValue { - t.Fatalf("Iterator produced a non-value") - } - - valuesCopy = append(valuesCopy, value) - } - - if len(values) != len(valuesCopy) { - t.Fatalf("iter gave the wrong number of values") - } - - for i, value := range values { - if value != valuesCopy[i] { - t.Fatalf("iter produced an incorrect value") - } - } -} |