diff options
Diffstat (limited to 'subex')
| -rw-r--r-- | subex/main.go | 49 | ||||
| -rw-r--r-- | subex/parse.go | 18 | ||||
| -rw-r--r-- | subex/subexast.go | 113 | ||||
| -rw-r--r-- | subex/subexstate.go | 4 |
4 files changed, 117 insertions, 67 deletions
diff --git a/subex/main.go b/subex/main.go index 5aedd09..635b1de 100644 --- a/subex/main.go +++ b/subex/main.go @@ -4,26 +4,53 @@ import ( "main/walk" ) +type Transducer struct { + storeSize int + initialState SubexState +} + +type StoreItem struct {} // Where slots are stored -type Store map[rune][]walk.Atom +type Store [][]walk.Atom // Return a new store with all the data from this one func (store Store) clone() Store { - newStore := make(Store) - for key, val := range store { - newStore[key] = val - } + newStore := make([][]walk.Atom, len(store)) + copy(newStore, store) return newStore } // Return a copy of this store but with an additional slot set -func (store Store) withValue(key rune, value []walk.Atom) Store { +func (store Store) withValue(key int, value []walk.Atom) Store { newStore := store.clone() newStore[key] = value return newStore } +type SlotMap struct { + nextId int + ids map[rune]int +} +func (m *SlotMap) getId(slot rune) int { + id, exists := m.ids[slot] + if exists { + return id + } + id = m.nextId + m.nextId++ + m.ids[slot] = id + return id +} + // Compile the SubexAST into a transducer SubexState that can be run -func CompileTransducer(transducerAst SubexAST) SubexState { - return transducerAst.compileWith(&SubexNoneState{}) +func CompileTransducer(transducerAst SubexAST) Transducer { + slotMap := SlotMap { + nextId: 0, + ids: make(map[rune]int), + } + initial := transducerAst.compileWith(&SubexNoneState{}, &slotMap) + return Transducer { + storeSize: slotMap.nextId, + initialState: initial, + } } // An immutable stack for outputting to @@ -93,14 +120,14 @@ func pruneStates(states []SubexBranch) (newStates []SubexBranch) { } // Run the subex transducer -func RunTransducer(transducer SubexState, input []walk.Atom) (output []walk.Atom, err bool) { +func RunTransducer(transducer Transducer, input []walk.Atom) (output []walk.Atom, err bool) { states := []SubexBranch{{ - state: transducer, + state: transducer.initialState, outputStack: OutputStack { head: nil, tail: nil, }, - store: make(Store), + store: make([][]walk.Atom, transducer.storeSize), }} for _, piece := range input { var newStates []SubexBranch diff --git a/subex/parse.go b/subex/parse.go index de53e2a..746217b 100644 --- a/subex/parse.go +++ b/subex/parse.go @@ -159,7 +159,7 @@ func parseRepeatRange(l RuneReader) (output []ConvexRange) { return output } -func parseReplacement(l RuneReader) (output []OutputContent) { +func parseReplacement(l RuneReader) (output []OutputContentAST) { // TODO escaping loop: for { r := l.Next() @@ -173,16 +173,16 @@ func parseReplacement(l RuneReader) (output []OutputContent) { if slot == eof { panic("Missing slot character") } - output = append(output, OutputLoad{slot: slot}) + output = append(output, OutputLoadAST{slot: slot}) case '`': literals := parseNonStringLiteral(l) for _, literal := range literals { - output = append(output, OutputAtomLiteral {literal}) + output = append(output, OutputAtomLiteralAST {literal}) } case '"': - output = append(output, OutputAtomLiteral {walk.NewAtomStringTerminal()}) + output = append(output, OutputAtomLiteralAST {walk.NewAtomStringTerminal()}) default: - output = append(output, OutputAtomLiteral{atom: walk.NewAtomStringRune(r)}) + output = append(output, OutputAtomLiteralAST{atom: walk.NewAtomStringRune(r)}) } } return output @@ -296,12 +296,12 @@ func parseSubex(l RuneReader, minPower int) SubexAST { case '^': replacement := parseReplacement(l) replacement = append( - []OutputContent{OutputAtomLiteral {walk.NewAtomStringTerminal()}}, + []OutputContentAST{OutputAtomLiteralAST {walk.NewAtomStringTerminal()}}, replacement... ) replacement = append( replacement, - OutputAtomLiteral {walk.NewAtomStringTerminal()}, + OutputAtomLiteralAST {walk.NewAtomStringTerminal()}, ) lhs = SubexASTOutput {replacement} case '.': @@ -320,9 +320,9 @@ func parseSubex(l RuneReader, minPower int) SubexAST { lhs = SubexASTCopyAtom {walk.NewAtomStringTerminal()} case '~': literals := parseNonStringLiteral(l) - var replacement []OutputContent + var replacement []OutputContentAST for _, literal := range literals { - replacement = append(replacement, OutputAtomLiteral {literal}) + replacement = append(replacement, OutputAtomLiteralAST {literal}) } lhs = SubexASTOutput {replacement} default: diff --git a/subex/subexast.go b/subex/subexast.go index 92c099a..f5b1178 100644 --- a/subex/subexast.go +++ b/subex/subexast.go @@ -7,15 +7,15 @@ import ( // A node in the AST of a subex type SubexAST interface { - compileWith(next SubexState) SubexState + compileWith(next SubexState, slotMap *SlotMap) 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) SubexState { - return ast.First.compileWith(ast.Second.compileWith(next)) +func (ast SubexASTConcat) compileWith(next SubexState, slotMap *SlotMap) SubexState { + return ast.First.compileWith(ast.Second.compileWith(next, slotMap), slotMap) } func (ast SubexASTConcat) String() string { return fmt.Sprintf("(%v)(%v)", ast.First, ast.Second) @@ -26,12 +26,13 @@ type SubexASTStore struct { Match SubexAST Slot rune } -func (ast SubexASTStore) compileWith(next SubexState) SubexState { +func (ast SubexASTStore) compileWith(next SubexState, slotMap *SlotMap) SubexState { + id := slotMap.getId(ast.Slot) return &SubexCaptureBeginState { next: ast.Match.compileWith(&SubexStoreEndState { - slot: ast.Slot, + slot: id, next: next, - }), + }, slotMap), } } func (ast SubexASTStore) String() string { @@ -42,10 +43,10 @@ func (ast SubexASTStore) String() string { type SubexASTOr struct { First, Second SubexAST } -func (ast SubexASTOr) compileWith(next SubexState) SubexState { +func (ast SubexASTOr) compileWith(next SubexState, slotMap *SlotMap) SubexState { return &SubexGroupState { - ast.First.compileWith(next), - ast.Second.compileWith(next), + ast.First.compileWith(next, slotMap), + ast.Second.compileWith(next, slotMap), } } func (ast SubexASTOr) String() string { @@ -75,19 +76,19 @@ func (cr ConvexRange) decrement() ConvexRange { return ConvexRange{cr.Start - 1, cr.End - 1} } } -func (cr ConvexRange) compile(content SubexAST, next SubexState) SubexState { +func (cr ConvexRange) compile(content SubexAST, next SubexState, slotMap *SlotMap) SubexState { min, _ := cr.minmax() if min != 0 { - return content.compileWith(cr.decrement().compile(content, next)) + return content.compileWith(cr.decrement().compile(content, next, slotMap), slotMap) } if cr.Start == -1 { state := &SubexGroupState {nil, next} - state.first = content.compileWith(state) + state.first = content.compileWith(state, slotMap) return state } if cr.End == -1 { state := &SubexGroupState {next, nil} - state.second = content.compileWith(state) + state.second = content.compileWith(state, slotMap) return state } @@ -95,7 +96,7 @@ func (cr ConvexRange) compile(content SubexAST, next SubexState) SubexState { state := next; for i := 0; i < cr.Start; i += 1 { state = &SubexGroupState { - content.compileWith(state), + content.compileWith(state, slotMap), next, } } @@ -105,7 +106,7 @@ func (cr ConvexRange) compile(content SubexAST, next SubexState) SubexState { for i := 0; i < cr.End; i += 1 { state = &SubexGroupState { next, - content.compileWith(state), + content.compileWith(state, slotMap), } } return state @@ -118,10 +119,10 @@ type SubexASTRepeat struct { Content SubexAST Acceptable []ConvexRange } -func (ast SubexASTRepeat) compileWith(next SubexState) SubexState { +func (ast SubexASTRepeat) compileWith(next SubexState, slotMap *SlotMap) SubexState { var state SubexState = &SubexDeadState{} for _, convex := range ast.Acceptable { - state = &SubexGroupState {state, convex.compile(ast.Content, next)} + state = &SubexGroupState {state, convex.compile(ast.Content, next, slotMap)} } return state } @@ -133,7 +134,7 @@ func (ast SubexASTRepeat) String() string { type SubexASTCopyAtom struct { Atom walk.Atom } -func (ast SubexASTCopyAtom) compileWith(next SubexState) SubexState { +func (ast SubexASTCopyAtom) compileWith(next SubexState, slotMap *SlotMap) SubexState { return &SubexCopyAtomState{ atom: ast.Atom, next: next, @@ -145,7 +146,7 @@ func (ast SubexASTCopyAtom) String() string { // Read in a single atom that must be a boolean and output it unchanged type SubexASTCopyBool struct {} -func (ast SubexASTCopyBool) compileWith(next SubexState) SubexState { +func (ast SubexASTCopyBool) compileWith(next SubexState, slotMap *SlotMap) SubexState { return &SubexCopyBoolState {next} } func (ast SubexASTCopyBool) String() string { @@ -154,7 +155,7 @@ 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) SubexState { +func (ast SubexASTCopyNumber) compileWith(next SubexState, slotMap *SlotMap) SubexState { return &SubexCopyNumberState {next} } func (ast SubexASTCopyNumber) String() string { @@ -163,7 +164,7 @@ func (ast SubexASTCopyNumber) String() string { // Read in a single atom that must be a string atom and output it unchanged type SubexASTCopyStringAtom struct {} -func (ast SubexASTCopyStringAtom) compileWith(next SubexState) SubexState { +func (ast SubexASTCopyStringAtom) compileWith(next SubexState, slotMap *SlotMap) SubexState { return &SubexCopyStringAtomState {next} } func (ast SubexASTCopyStringAtom) String() string { @@ -173,7 +174,7 @@ func (ast SubexASTCopyStringAtom) String() string { // Read in a full string value and copy it out unchanged // # is equivalent to "_{-0}" type SubexASTCopyString struct {} -func (ast SubexASTCopyString) compileWith(next SubexState) SubexState { +func (ast SubexASTCopyString) compileWith(next SubexState, slotMap *SlotMap) SubexState { stringAtomState := &SubexCopyStringAtomState { next: nil, } @@ -197,9 +198,9 @@ func (ast SubexASTCopyString) String() string { // Read in a value and copy it out unchanged // , is equivalent to `null`|?|%|#|[`{}[]`] type SubexASTCopyValue struct {} -func (ast SubexASTCopyValue) compileWith(next SubexState) SubexState { +func (ast SubexASTCopyValue) compileWith(next SubexState, slotMap *SlotMap) SubexState { return &SubexGroupState { - SubexASTCopyString{}.compileWith(next), + SubexASTCopyString{}.compileWith(next, slotMap), &SubexCopyNonStringAtomState {next}, } } @@ -209,20 +210,42 @@ func (ast SubexASTCopyValue) String() string { // Read in any single Atom and output it unchanged type SubexASTCopyAny struct {} -func (ast SubexASTCopyAny) compileWith(next SubexState) SubexState { +func (ast SubexASTCopyAny) compileWith(next SubexState, slotMap *SlotMap) SubexState { return &SubexCopyAnyState{next} } func (ast SubexASTCopyAny) String() string { return "." } +type OutputContentAST interface { + compile(slotMap *SlotMap) OutputContent +} + +type OutputLoadAST struct { + slot rune +} +func (ast OutputLoadAST) compile(slotMap *SlotMap) OutputContent { + return OutputLoad {slotMap.getId(ast.slot)} +} + +type OutputAtomLiteralAST struct { + atom walk.Atom +} +func (ast OutputAtomLiteralAST) compile(slotMap *SlotMap) OutputContent { + return OutputAtomLiteral {ast.atom} +} + // Output a series of Atoms without reading anything from input type SubexASTOutput struct { - Replacement []OutputContent + Replacement []OutputContentAST } -func (ast SubexASTOutput) compileWith(next SubexState) SubexState { +func (ast SubexASTOutput) compileWith(next SubexState, slotMap *SlotMap) SubexState { + var content []OutputContent + for _, el := range ast.Replacement { + content = append(content, el.compile(slotMap)) + } return &SubexOutputState{ - content: ast.Replacement, + content: content, next: next, } } @@ -234,13 +257,13 @@ func (ast SubexASTOutput) String() string { type SubexASTJoin struct { Content, Delimiter SubexAST } -func (ast SubexASTJoin) compileWith(next SubexState) SubexState { +func (ast SubexASTJoin) compileWith(next SubexState, slotMap *SlotMap) SubexState { afterContentState := &SubexGroupState { nil, next, } - manyContentsState := ast.Content.compileWith(afterContentState) - afterContentState.first = ast.Delimiter.compileWith(manyContentsState) + manyContentsState := ast.Content.compileWith(afterContentState, slotMap) + afterContentState.first = ast.Delimiter.compileWith(manyContentsState, slotMap) return &SubexGroupState { manyContentsState, next, @@ -255,7 +278,7 @@ func (ast SubexASTJoin) String() string { type SubexASTRange struct { Parts map[walk.Atom]walk.Atom } -func (ast SubexASTRange) compileWith(next SubexState) SubexState { +func (ast SubexASTRange) compileWith(next SubexState, slotMap *SlotMap) SubexState { return &SubexRangeState { parts: ast.Parts, next: next, @@ -270,12 +293,12 @@ func (ast SubexASTRange) String() string { type SubexASTSum struct { Content SubexAST } -func (ast SubexASTSum) compileWith(next SubexState) SubexState { +func (ast SubexASTSum) compileWith(next SubexState, slotMap *SlotMap) SubexState { return &SubexCaptureBeginState { next: ast.Content.compileWith(&SubexArithmeticEndState { next: next, calculate: sumValues, - }), + }, slotMap), } } func (ast SubexASTSum) String() string { @@ -286,12 +309,12 @@ func (ast SubexASTSum) String() string { type SubexASTProduct struct { Content SubexAST } -func (ast SubexASTProduct) compileWith(next SubexState) SubexState { +func (ast SubexASTProduct) compileWith(next SubexState, slotMap *SlotMap) SubexState { return &SubexCaptureBeginState { next: ast.Content.compileWith(&SubexArithmeticEndState { next: next, calculate: multiplyValues, - }), + }, slotMap), } } func (ast SubexASTProduct) String() string { @@ -303,12 +326,12 @@ func (ast SubexASTProduct) String() string { type SubexASTNegate struct { Content SubexAST } -func (ast SubexASTNegate) compileWith(next SubexState) SubexState { +func (ast SubexASTNegate) compileWith(next SubexState, slotMap *SlotMap) SubexState { return &SubexCaptureBeginState { next: ast.Content.compileWith(&SubexArithmeticEndState { next: next, calculate: negateValues, - }), + }, slotMap), } } func (ast SubexASTNegate) String() string { @@ -321,12 +344,12 @@ func (ast SubexASTNegate) String() string { type SubexASTReciprocal struct { Content SubexAST } -func (ast SubexASTReciprocal) compileWith(next SubexState) SubexState { +func (ast SubexASTReciprocal) compileWith(next SubexState, slotMap *SlotMap) SubexState { return &SubexCaptureBeginState { next: ast.Content.compileWith(&SubexArithmeticEndState { next: next, calculate: reciprocalValues, - }), + }, slotMap), } } func (ast SubexASTReciprocal) String() string { @@ -339,12 +362,12 @@ func (ast SubexASTReciprocal) String() string { type SubexASTNot struct { Content SubexAST } -func (ast SubexASTNot) compileWith(next SubexState) SubexState { +func (ast SubexASTNot) compileWith(next SubexState, slotMap *SlotMap) SubexState { return &SubexCaptureBeginState { next: ast.Content.compileWith(&SubexArithmeticEndState { next: next, calculate: notValues, - }), + }, slotMap), } } func (ast SubexASTNot) String() string { @@ -353,7 +376,7 @@ func (ast SubexASTNot) String() string { // Does nothing type SubexASTEmpty struct {} -func (ast SubexASTEmpty) compileWith(next SubexState) SubexState { +func (ast SubexASTEmpty) compileWith(next SubexState, slotMap *SlotMap) SubexState { return next } func (ast SubexASTEmpty) String() string { @@ -364,9 +387,9 @@ func (ast SubexASTEmpty) String() string { type SubexASTDiscard struct { Content SubexAST } -func (ast SubexASTDiscard) compileWith(next SubexState) SubexState { +func (ast SubexASTDiscard) compileWith(next SubexState, slotMap *SlotMap) SubexState { return &SubexCaptureBeginState { - next: ast.Content.compileWith(&SubexDiscardState {next}), + next: ast.Content.compileWith(&SubexDiscardState {next}, slotMap), } } func (ast SubexASTDiscard) String() string { diff --git a/subex/subexstate.go b/subex/subexstate.go index 56063c0..4655ef9 100644 --- a/subex/subexstate.go +++ b/subex/subexstate.go @@ -52,7 +52,7 @@ func (state SubexDiscardState) accepting(store Store, outputStack OutputStack) [ // Pop the top of the OutputStack which contains the stuff outputted since the start of the store // This outputted data gets stored in a slot type SubexStoreEndState struct { - slot rune + slot int next SubexState } func (state SubexStoreEndState) eat(store Store, outputStack OutputStack, char walk.Atom) []SubexBranch { @@ -80,7 +80,7 @@ func (replacement OutputAtomLiteral) build(store Store) []walk.Atom { // An OutputContent which is a slot that is loaded from type OutputLoad struct { - slot rune + slot int } func (replacement OutputLoad) build(store Store) []walk.Atom { return store[replacement.slot] |