package main import ( "os" "bufio" "fmt" "strings" "unicode/utf8" ) type PathSegment interface {} type Path []PathSegment type TerminalValue int const ( ArrayBegin TerminalValue = iota ArrayEnd MapBegin MapEnd ) type ValueNull struct {} type ValueBool bool type ValueNumber float64 type ValueString string type WalkValue interface {} type WalkItem struct { value WalkValue path Path } type Program []Command type ProgramState struct { space []WalkItem in chan WalkItem out chan WalkItem program []Command } //const eof rune = -1 type RuneReader struct { input string pos, width int } func (l *RuneReader) next() rune { if l.pos >= len(l.input) { l.width = 0 return eof } var r rune r, l.width = utf8.DecodeRuneInString(l.input[l.pos:]) l.pos += l.width return r } func (l *RuneReader) accept(chars string) bool { r := l.next() for _, char := range chars { if char == r { return true } } l.rewind() return false } func (l *RuneReader) rewind() { l.pos -= l.width } func parseReplacement(l *RuneReader) (output []TransducerOutput) { 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, TransducerReplacementLoad(slot)) default: output = append(output, TransducerReplacementRune(r)) } } return output } func parseRegex(l *RuneReader, minPower int) RegexAST { var lhs RegexAST r := l.next() switch r { case eof: return nil case ')', '*', '-', '|': l.rewind() return nil case '(': lhs = parseRegex(l, 0) if !l.accept(")") { panic("Missing matching )") } case '.': lhs = RegexASTAny{} default: lhs = RegexASTRune(r) } loop: for { if minPower <= 0 { next := parseRegex(l, 1) if next != nil { lhs = RegexASTConcat{lhs, next} continue loop } } r := l.next() switch { case r == '*' && minPower <= 4: lhs = RegexASTMaximise{lhs} case r == '-' && minPower <= 4: lhs = RegexASTMinimise{lhs} case r == '|' && minPower <= 2: rhs := parseRegex(l, 3) if rhs == nil { panic("Missing regex after |") } lhs = RegexASTOr{lhs, rhs} default: l.rewind() break loop } } return lhs } func parseSubex(l *RuneReader, minPower int) TransducerAST { var lhs TransducerAST r := l.next() switch r { case eof: return nil case '(': lhs = parseSubex(l, 0) if !l.accept(")") { panic("Missing matching )") } case ')', '*', '-', '|': l.rewind() return nil case '$': slot := l.next() if slot == eof { panic("Missing slot character") } match := parseRegex(l, 100) if match == nil { panic("Missing regex for store") } lhs = TransducerASTStore{ match: match, slot: slot, } case '"': replacement := parseReplacement(l) lhs = TransducerASTOutput{replacement} case '.': lhs = TransducerASTCopyAny{} default: lhs = TransducerASTCopyRune(r) } loop: for { if minPower <= 0 { next := parseSubex(l, 1) if next != nil { lhs = TransducerASTConcat{lhs, next} continue loop } } r := l.next() switch { case r == '*' && minPower <= 4: lhs = TransducerASTMaximise{lhs} case r == '-' && minPower <= 4: lhs = TransducerASTMinimise{lhs} case r == '|' && minPower <= 2: rhs := parseSubex(l, 3) if rhs == nil { panic("Missing subex after |") } lhs = TransducerASTOr{lhs, rhs} default: l.rewind() break loop } } return lhs } func parse(input string) TransducerAST { l := RuneReader { input: input, pos: 0, width: 0, } return parseSubex(&l, 0) } type TransducerOutput interface { build(Store) string } type TransducerReplacementRune rune func (replacement TransducerReplacementRune) build(store Store) string { return string(replacement) } type TransducerReplacementLoad rune func (replacement TransducerReplacementLoad) build(store Store) string { return store[rune(replacement)] } type RegexState interface { eat(char rune) []RegexState accepting() bool } type RegexNoneState struct {} func (state RegexNoneState) eat(char rune) []RegexState { return nil } func (state RegexNoneState) accepting() bool { return true } type RegexAnyState struct { next RegexState } func (state RegexAnyState) eat(char rune) []RegexState { return []RegexState{state.next} } func (state RegexAnyState) accepting() bool { return false } type RegexRuneState struct { rune rune next RegexState } func (state RegexRuneState) eat(char rune) []RegexState { if char == state.rune { return []RegexState{state.next} } return nil } func (state RegexRuneState) accepting() bool { return false } type RegexGroupState struct { first, second RegexState } func (state RegexGroupState) eat(char rune) []RegexState { return append(state.first.eat(char), state.second.eat(char)...) } func (state RegexGroupState) accepting() bool { return state.first.accepting() || state.second.accepting() } type RegexAST interface { compileWith(next RegexState) RegexState } type RegexASTRune rune func (ast RegexASTRune) compileWith(next RegexState) RegexState { return RegexRuneState{ rune: rune(ast), next: next, } } func (ast RegexASTRune) String() string { return string(rune(ast)) } type RegexASTAny struct {} func (ast RegexASTAny) compileWith(next RegexState) RegexState { return RegexAnyState{next} } func (ast RegexASTAny) String() string { return "." } type RegexASTConcat struct { first, second RegexAST } func (ast RegexASTConcat) compileWith(next RegexState) RegexState { return ast.first.compileWith(ast.second.compileWith(next)) } func (ast RegexASTConcat) String() string { return fmt.Sprintf("Concat{%v, %v}", ast.first, ast.second) } type RegexASTOr struct { first, second RegexAST } func (ast RegexASTOr) compileWith(next RegexState) RegexState { return RegexGroupState{ ast.first.compileWith(next), ast.second.compileWith(next), } } type RegexASTMaximise struct { content RegexAST } func (ast RegexASTMaximise) compileWith(next RegexState) RegexState { state := &RegexGroupState{ nil, next, } state.first = ast.content.compileWith(state) return state } type RegexASTMinimise struct { content RegexAST } func (ast RegexASTMinimise) compileWith(next RegexState) RegexState { state := &RegexGroupState{ next, nil, } state.second = ast.content.compileWith(state) return state } type Store map[rune]string func (store Store) clone() Store { newStore := make(Store) for key, val := range store { newStore[key] = val } return newStore } type TransducerState interface { eat(store Store, char rune) []TransducerStatePair accepting(store Store) []string } type TransducerGroupState struct { first, second TransducerState } func (state TransducerGroupState) eat(store Store, char rune) []TransducerStatePair { otherStore := store.clone() return append(state.first.eat(store, char), state.second.eat(otherStore, char)...) } func (state TransducerGroupState) accepting(store Store) []string { return append(state.first.accepting(store), state.second.accepting(store)...) } type TransducerStoreState struct { match RegexState slot rune next TransducerState input string } func (state TransducerStoreState) eat(store Store, char rune) []TransducerStatePair { var nextStates []TransducerStatePair if state.match.accepting() { store[state.slot] = state.input nextStates = state.next.eat(store, char) } nextRegexStates := state.match.eat(char) for _, regexState := range nextRegexStates { nextStates = append(nextStates, TransducerStatePair { state: TransducerStoreState { match: regexState, slot: state.slot, next: state.next, input: state.input + string(char), }, output: "", store: store.clone(), }) } return nextStates } func (state TransducerStoreState) accepting(store Store) []string { if state.match.accepting() { return state.next.accepting(store) } return nil } type TransducerOutputState struct { content []TransducerOutput next TransducerState } func (state TransducerOutputState) build(store Store) string { var builder strings.Builder for _, part := range state.content { builder.WriteString(part.build(store)) } return builder.String() } func (state TransducerOutputState) eat(store Store, char rune) []TransducerStatePair { content := state.build(store) nextStates := state.next.eat(store, char) for i := range nextStates { nextStates[i].output = content + nextStates[i].output } return nextStates } func (state TransducerOutputState) accepting(store Store) []string { content := state.build(store) outputs := state.next.accepting(store) for i := range outputs { outputs[i] = content + outputs[i] } return outputs } type TransducerNoneState struct {} func (state TransducerNoneState) eat(store Store, char rune) []TransducerStatePair { return nil } func (state TransducerNoneState) accepting(store Store) []string { return []string{""} } type TransducerCopyRuneState struct { rune rune next TransducerState } func (state TransducerCopyRuneState) eat(store Store, char rune) []TransducerStatePair { if char == state.rune { return []TransducerStatePair{{ state: state.next, output: string(char), store: store, }} } return nil } func (state TransducerCopyRuneState) accepting(store Store) []string { return nil } type TransducerCopyAnyState struct { next TransducerState } func (state TransducerCopyAnyState) eat(store Store, char rune) []TransducerStatePair { return []TransducerStatePair{{ state: state.next, output: string(char), store: store, }} } func (state TransducerCopyAnyState) accepting(store Store) []string { return nil } type TransducerAST interface { compileWithNext(next TransducerState) TransducerState } type TransducerASTConcat struct { first, second TransducerAST } func (ast TransducerASTConcat) compileWithNext(next TransducerState) TransducerState { return ast.first.compileWithNext(ast.second.compileWithNext(next)) } func (ast TransducerASTConcat) String() string { return fmt.Sprintf("(%v)(%v)", ast.first, ast.second) } type TransducerASTStore struct { match RegexAST slot rune } func (ast TransducerASTStore) compileWithNext(next TransducerState) TransducerState { return TransducerStoreState { match: ast.match.compileWith(RegexNoneState{}), slot: ast.slot, next: next, } } func (ast TransducerASTStore) String() string { return fmt.Sprintf("$%c(%v)", ast.slot, ast.match) } type TransducerASTOr struct { first, second TransducerAST } func (ast TransducerASTOr) compileWithNext(next TransducerState) TransducerState { return TransducerGroupState { ast.first.compileWithNext(next), ast.second.compileWithNext(next), } } type TransducerASTMaximise struct { content TransducerAST } func (ast TransducerASTMaximise) compileWithNext(next TransducerState) TransducerState { state := &TransducerGroupState { nil, next, } state.first = ast.content.compileWithNext(state) return state } func (ast TransducerASTMaximise) String() string { return fmt.Sprintf("(%v)*", ast.content) } type TransducerASTMinimise struct { content TransducerAST } func (ast TransducerASTMinimise) compileWithNext(next TransducerState) TransducerState { state := &TransducerGroupState { next, nil, } state.second = ast.content.compileWithNext(state) return state } func (ast TransducerASTMinimise) String() string { return fmt.Sprintf("(%v)-", ast.content) } type TransducerASTRepeat struct { content TransducerAST min, max int } func (ast TransducerASTRepeat) compileWithNext(next TransducerState) TransducerState { for i := ast.min; i < ast.max; i += 1 { next = TransducerGroupState { ast.content.compileWithNext(next), next, } } for i := 0; i < ast.min; i += 1 { next = ast.content.compileWithNext(next) } return next } type TransducerASTCopyRune rune func (ast TransducerASTCopyRune) compileWithNext(next TransducerState) TransducerState { return TransducerCopyRuneState{ rune: rune(ast), next: next, } } type TransducerASTCopyAny struct {} func (ast TransducerASTCopyAny) compileWithNext(next TransducerState) TransducerState { return TransducerCopyAnyState{next} } func (ast TransducerASTCopyAny) String() string { return "." } type TransducerASTOutput struct { replacement []TransducerOutput } func (ast TransducerASTOutput) compileWithNext(next TransducerState) TransducerState { return TransducerOutputState{ content: ast.replacement, next: next, } } func compileTransducer(transducerAst TransducerAST) TransducerState { return transducerAst.compileWithNext(TransducerNoneState{}) } type TransducerStatePair struct { store Store state TransducerState output string } func (pair TransducerStatePair) eat(char rune) []TransducerStatePair { states := pair.state.eat(pair.store, char) for i := range states { states[i].output = pair.output + states[i].output } return states } func (pair TransducerStatePair) accepting() []string { return pair.state.accepting(pair.store) } func runTransducer(transducer TransducerState, input string) (output string, err bool) { states := []TransducerStatePair{{ state: transducer, output: "", store: make(Store), }} for _, char := range input { var newStates []TransducerStatePair for _, state := range states { newStates = append(newStates, state.eat(char)...) } states = newStates } for _, state := range states { outputEnds := state.accepting() for _, outputEnd := range outputEnds { return state.output + outputEnd, false } } return "", true } func main() { if len(os.Args) != 3 { panic("Expected: program [input] [subex]") } input := os.Args[1] program := os.Args[2] ast := parse(program) transducer := compileTransducer(ast) output, err := runTransducer(transducer, input) if err { output = input } fmt.Println(output) } func mainISH() { 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 } if !hasInput { panic("Missing program") } tokens := Lex(input) program := Parse(tokens) stdin := bufio.NewReader(os.Stdin) dataStream := Json(stdin) state := ProgramState { in: dataStream, out: make(chan WalkItem), program: program, } go func () { for walkItem := range dataStream { state.space = []WalkItem{walkItem} for _, cmd := range state.program { cmd.exec(&state) } if !quiet { for _, item := range state.space { state.out <- item } } } close(state.out) }() JsonOut(state.out) }