Back to shtanton's homepage
aboutsummaryrefslogtreecommitdiff
path: root/subex
diff options
context:
space:
mode:
Diffstat (limited to 'subex')
-rw-r--r--subex/main_test.go7
-rw-r--r--subex/numberexpr.go217
-rw-r--r--subex/parse.go203
-rw-r--r--subex/subexast.go161
-rw-r--r--subex/subexstate.go23
5 files changed, 399 insertions, 212 deletions
diff --git a/subex/main_test.go b/subex/main_test.go
index 3855dbc..938e5cb 100644
--- a/subex/main_test.go
+++ b/subex/main_test.go
@@ -58,7 +58,7 @@ func TestSubexMain(t *testing.T) {
},
{
// Keep only odd numbers between 0 and 10
- subex: `([c5*2+1]|(.>_))*`,
+ subex: `([0<=n&n<=10&n%2=1]|(.>_))*`,
input: []walk.Value {
walk.NumberValue(0),
walk.NumberValue(1),
@@ -82,7 +82,8 @@ func TestSubexMain(t *testing.T) {
},
},
{
- subex: "r*([pi*2]%a`<a/2`)|([pi*2+1]%b`<b*3+1`)",
+ // Collatz
+ subex: "[1]*[n%2=0:n,n/2]|[n%2=1:n,n*3+1]",
input: []walk.Value {
walk.NumberValue(32),
},
@@ -500,7 +501,7 @@ func doCollatzTest(t *testing.T, init int) {
}
last := init
- lexer := NewStringRuneReader("r*([pi*2]%a`<a/2`|[pi*2+1]%b`<b*3+1`)")
+ lexer := NewStringRuneReader("[1]*([n%2=0:n,n/2]|[n%2=1&n>1:n,n*3+1])")
ast := Parse(lexer)
transducer := CompileTransducer(ast)
diff --git a/subex/numberexpr.go b/subex/numberexpr.go
new file mode 100644
index 0000000..3649305
--- /dev/null
+++ b/subex/numberexpr.go
@@ -0,0 +1,217 @@
+package subex
+
+import (
+ "fmt"
+ "math"
+)
+
+type NumberExpr interface {
+ String() string
+ Eval(float64) float64
+}
+
+type NumberExprVariable struct {}
+func (ev NumberExprVariable) String() string {
+ return "n"
+}
+func (ev NumberExprVariable) Eval(v float64) float64 {
+ return v
+}
+
+type NumberExprLiteral struct {
+ Value float64
+}
+func (el NumberExprLiteral) String() string {
+ return fmt.Sprintf("%v", el.Value)
+}
+func (el NumberExprLiteral) Eval(v float64) float64 {
+ return el.Value
+}
+
+type NumberExprAnd struct {
+ Left NumberExpr
+ Right NumberExpr
+}
+func (ea NumberExprAnd) String() string {
+ return fmt.Sprintf("(%v & %v)", ea.Left, ea.Right)
+}
+func (ea NumberExprAnd) Eval(v float64) float64 {
+ left := ea.Left.Eval(v)
+ if left != 0.0 {
+ return ea.Right.Eval(v)
+ } else {
+ return left
+ }
+}
+
+type NumberExprOr struct {
+ Left NumberExpr
+ Right NumberExpr
+}
+func (eo NumberExprOr) String() string {
+ return fmt.Sprintf("(%v | %v)", eo.Left, eo.Right)
+}
+func (eo NumberExprOr) Eval(v float64) float64 {
+ left := eo.Left.Eval(v)
+ if left != 0.0 {
+ return left
+ } else {
+ return eo.Right.Eval(v)
+ }
+}
+
+type NumberExprNot struct {
+ Right NumberExpr
+}
+func (en NumberExprNot) String() string {
+ return fmt.Sprintf("(!%v)", en.Right)
+}
+func (en NumberExprNot) Eval(v float64) float64 {
+ inner := en.Right.Eval(v)
+ if inner == 0.0 {
+ return 1.0
+ }
+
+ return 0.0
+}
+
+type NumberExprEqual struct {
+ Left NumberExpr
+ Right NumberExpr
+}
+func (ee NumberExprEqual) String() string {
+ return fmt.Sprintf("(%v = %v)", ee.Left, ee.Right)
+}
+func (ee NumberExprEqual) Eval(v float64) float64 {
+ if ee.Left.Eval(v) == ee.Right.Eval(v) {
+ return 1.0
+ } else {
+ return 0.0
+ }
+}
+
+type NumberExprAtMost struct {
+ Left NumberExpr
+ Right NumberExpr
+}
+func (ea NumberExprAtMost) String() string {
+ return fmt.Sprintf("(%v <= %v)", ea.Left, ea.Right)
+}
+func (ea NumberExprAtMost) Eval(v float64) float64 {
+ if ea.Left.Eval(v) <= ea.Right.Eval(v) {
+ return 1.0
+ } else {
+ return 0.0
+ }
+}
+
+type NumberExprLessThan struct {
+ Left NumberExpr
+ Right NumberExpr
+}
+func (el NumberExprLessThan) String() string {
+ return fmt.Sprintf("(%v < %v)", el.Left, el.Right)
+}
+func (el NumberExprLessThan) Eval(v float64) float64 {
+ if el.Left.Eval(v) < el.Right.Eval(v) {
+ return 1.0
+ } else {
+ return 0.0
+ }
+}
+
+type NumberExprGreaterThan struct {
+ Left NumberExpr
+ Right NumberExpr
+}
+func (eg NumberExprGreaterThan) String() string {
+ return fmt.Sprintf("(%v > %v)", eg.Left, eg.Right)
+}
+func (eg NumberExprGreaterThan) Eval(v float64) float64 {
+ if eg.Left.Eval(v) > eg.Right.Eval(v) {
+ return 1.0
+ } else {
+ return 0.0
+ }
+}
+
+type NumberExprAtLeast struct {
+ Left NumberExpr
+ Right NumberExpr
+}
+func (ea NumberExprAtLeast) String() string {
+ return fmt.Sprintf("(%v >= %v)", ea.Left, ea.Right)
+}
+func (ea NumberExprAtLeast) Eval(v float64) float64 {
+ if ea.Left.Eval(v) >= ea.Right.Eval(v) {
+ return 1.0
+ } else {
+ return 0.0
+ }
+}
+
+type NumberExprAdd struct {
+ Left NumberExpr
+ Right NumberExpr
+}
+func (ea NumberExprAdd) String() string {
+ return fmt.Sprintf("(%v + %v)", ea.Left, ea.Right)
+}
+func (ea NumberExprAdd) Eval(v float64) float64 {
+ return ea.Left.Eval(v) + ea.Right.Eval(v)
+}
+
+type NumberExprSubtract struct {
+ Left NumberExpr
+ Right NumberExpr
+}
+func (es NumberExprSubtract) String() string {
+ return fmt.Sprintf("(%v - %v)", es.Left, es.Right)
+}
+func (es NumberExprSubtract) Eval(v float64) float64 {
+ return es.Left.Eval(v) - es.Right.Eval(v)
+}
+
+type NumberExprMultiply struct {
+ Left NumberExpr
+ Right NumberExpr
+}
+func (em NumberExprMultiply) String() string {
+ return fmt.Sprintf("(%v * %v)", em.Left, em.Right)
+}
+func (em NumberExprMultiply) Eval(v float64) float64 {
+ return em.Left.Eval(v) * em.Right.Eval(v)
+}
+
+type NumberExprDivide struct {
+ Left NumberExpr
+ Right NumberExpr
+}
+func (ed NumberExprDivide) String() string {
+ return fmt.Sprintf("(%v / %v)", ed.Left, ed.Right)
+}
+func (ed NumberExprDivide) Eval(v float64) float64 {
+ return ed.Left.Eval(v) / ed.Right.Eval(v)
+}
+
+type NumberExprMod struct {
+ Left NumberExpr
+ Right NumberExpr
+}
+func (em NumberExprMod) String() string {
+ return fmt.Sprintf("(%v %% %v)", em.Left, em.Right)
+}
+func (em NumberExprMod) Eval(v float64) float64 {
+ return math.Mod(em.Left.Eval(v), em.Right.Eval(v))
+}
+
+type NumberExprExponent struct {
+ Left NumberExpr
+ Right NumberExpr
+}
+func (ee NumberExprExponent) String() string {
+ return fmt.Sprintf("(%v * %v)", ee.Left, ee.Right)
+}
+func (ee NumberExprExponent) Eval(v float64) float64 {
+ return ee.Left.Eval(v) * ee.Right.Eval(v)
+}
diff --git a/subex/parse.go b/subex/parse.go
index 179cc01..01a747b 100644
--- a/subex/parse.go
+++ b/subex/parse.go
@@ -144,62 +144,128 @@ func parseInt(l RuneReader) (output int) {
return output
}
-func parseNumberFilter(l RuneReader, minPower int) SubexASTNumberFilter {
- var lhs SubexASTNumberFilter
- r := l.Next()
- switch r {
- case eof:
- panic("Missing matching ]")
- case 'c':
- count := parseInt(l)
- lhs = SubexASTNumberFilterCount {count}
- case 'p':
- var subset NumberSubset
- if l.Next() == 'i' {
- subset = NumberSubsetPositiveInteger
- } else {
- subset = NumberSubsetPositiveReal
- l.Rewind()
- }
- lhs = SubexASTNumberFilterSubset {
- subset: subset,
- }
- default:
+// Parse a number literal in a number expression
+func parseNumberLiteral(l RuneReader) NumberExprLiteral {
+ var builder strings.Builder
+ for {
+ r := l.Next()
if !isNumericRune(r) {
- panic("Invalid character in numeric []")
+ l.Rewind()
+ break
}
-
- var builder strings.Builder
builder.WriteRune(r)
- for {
- r := l.Next()
- if !isNumericRune(r) {
- l.Rewind()
- break
- }
- builder.WriteRune(r)
+ }
+ numberString := builder.String()
+ number, err := strconv.ParseFloat(numberString, 64)
+ if err != nil {
+ panic("Invalid number literal")
+ }
+ return NumberExprLiteral {
+ Value: number,
+ }
+}
+
+// Parse a numeric expression
+func parseNumberExpression(l RuneReader, minPower int) NumberExpr {
+ var lhs NumberExpr
+ switch l.Next() {
+ case '(':
+ lhs = parseNumberExpression(l, 0)
+ if !accept(l, ")") {
+ panic("Missing closing )")
}
- numberString := builder.String()
- number, err := strconv.ParseFloat(numberString, 64)
- if err != nil {
- panic("Invalid number literal")
+ case 'n':
+ lhs = NumberExprVariable{}
+ case '-':
+ lhs = NumberExprLiteral{0}
+ l.Rewind()
+ case '!':
+ lhs = NumberExprNot {
+ Right: parseNumberExpression(l, 13),
}
-
- lhs = SubexASTNumberFilterLiteral {number}
+ default:
+ l.Rewind()
+ lhs = parseNumberLiteral(l)
}
loop: for {
r := l.Next()
switch {
- case r == '+' && minPower <= 10:
- lhs = SubexASTNumberFilterAdd {
- lhs: lhs,
- rhs: parseNumberFilter(l, 11),
+ case r == '|' && minPower <= 8:
+ lhs = NumberExprOr {
+ Left: lhs,
+ Right: parseNumberExpression(l, 9),
}
- case r == '*' && minPower <= 20:
- lhs = SubexASTNumberFilterMultiply {
- lhs: lhs,
- rhs: parseNumberFilter(l, 21),
+ case r == '&' && minPower <= 10:
+ lhs = NumberExprAnd {
+ Left: lhs,
+ Right: parseNumberExpression(l, 11),
+ }
+ case r == '<' && minPower <= 20:
+ if accept(l, "=") {
+ lhs = NumberExprAtMost {
+ Left: lhs,
+ Right: parseNumberExpression(l, 21),
+ }
+ } else {
+ lhs = NumberExprLessThan {
+ Left: lhs,
+ Right: parseNumberExpression(l, 21),
+ }
+ }
+ case r == '>' && minPower <= 20:
+ if accept(l, "=") {
+ lhs = NumberExprAtLeast {
+ Left: lhs,
+ Right: parseNumberExpression(l, 21),
+ }
+ } else {
+ lhs = NumberExprGreaterThan {
+ Left: lhs,
+ Right: parseNumberExpression(l, 21),
+ }
+ }
+ case r == '=' && minPower <= 20:
+ lhs = NumberExprEqual {
+ Left: lhs,
+ Right: parseNumberExpression(l, 21),
+ }
+ case r == '~' && minPower <= 20:
+ lhs = NumberExprNot {
+ Right: NumberExprEqual {
+ Left: lhs,
+ Right: parseNumberExpression(l, 21),
+ },
+ }
+ case r == '+' && minPower <= 30:
+ lhs = NumberExprAdd {
+ Left: lhs,
+ Right: parseNumberExpression(l, 31),
+ }
+ case r == '-' && minPower <= 30:
+ lhs = NumberExprSubtract {
+ Left: lhs,
+ Right: parseNumberExpression(l, 31),
+ }
+ case r == '*' && minPower <= 36:
+ lhs = NumberExprMultiply {
+ Left: lhs,
+ Right: parseNumberExpression(l, 37),
+ }
+ case r == '/' && minPower <= 36:
+ lhs = NumberExprDivide {
+ Left: lhs,
+ Right: parseNumberExpression(l, 37),
+ }
+ case r == '%' && minPower <= 36:
+ lhs = NumberExprMod {
+ Left: lhs,
+ Right: parseNumberExpression(l, 37),
+ }
+ case r == '^' && minPower <= 40:
+ lhs = NumberExprExponent {
+ Left: lhs,
+ Right: parseNumberExpression(l, 41),
}
default:
l.Rewind()
@@ -210,6 +276,34 @@ func parseNumberFilter(l RuneReader, minPower int) SubexASTNumberFilter {
return lhs
}
+// Having just read a [ in a value subex, parse the number mapping contents up
+// to but not including the closing ]
+func parseNumberMapping(l RuneReader) SubexAST {
+ numRange := parseNumberExpression(l, 0)
+ var numReplace []NumberExpr
+ if accept(l, ":") {
+ if !accept(l, "]") {
+ for {
+ numReplace = append(
+ numReplace,
+ parseNumberExpression(l, 0),
+ )
+ if !accept(l, ",") {
+ break
+ }
+ }
+ } else {
+ l.Rewind()
+ }
+ } else {
+ numReplace = []NumberExpr{NumberExprVariable{}}
+ }
+ return SubexASTNumberMapping {
+ Range: numRange,
+ Replace: numReplace,
+ }
+}
+
// Having just read {, read in and parse the range contents
func parseRepeatRange(l RuneReader) (output []ConvexRange) {
loop: for {
@@ -717,9 +811,7 @@ func parseSubex(l RuneReader, minPower int, inType Type) (lhs SubexAST, outType
case '[':
switch inType {
case ValueType:
- lhs = SubexASTCopyNumberFilter {
- filter: parseNumberFilter(l, 0),
- }
+ lhs = parseNumberMapping(l)
if !accept(l, "]") {
panic("Missing matching ]")
}
@@ -748,21 +840,6 @@ func parseSubex(l RuneReader, minPower int, inType Type) (lhs SubexAST, outType
default:
panic("Invalid inType")
}
- case 'r':
- switch inType {
- case ValueType:
- outType = inType
- lhs = SubexASTCopyNumberFilter {
- filter: SubexASTNumberFilterSubset {
- subset: NumberSubsetReal,
- },
- }
- case RuneType:
- outType = inType
- lhs = SubexASTCopyRune {'r'}
- default:
- panic("Invalid inType")
- }
case '?':
outType = inType
lhs = SubexASTCopyBool{}
diff --git a/subex/subexast.go b/subex/subexast.go
index 89949ba..01a5e0d 100644
--- a/subex/subexast.go
+++ b/subex/subexast.go
@@ -303,152 +303,6 @@ type SubexASTNumberFilter interface {
compute() float64
}
-type SubexASTNumberFilterLiteral struct {
- value float64
-}
-func (ast SubexASTNumberFilterLiteral) compile() numberFilter {
- return equalNumberFilter {ast.value}
-}
-func (ast SubexASTNumberFilterLiteral) computable() bool {
- return true
-}
-func (ast SubexASTNumberFilterLiteral) compute() float64 {
- return ast.value
-}
-
-type NumberSubset int
-const (
- NumberSubsetReal NumberSubset = iota
- NumberSubsetInteger
- NumberSubsetPositiveInteger
- NumberSubsetZeroToOne
- NumberSubsetPositiveReal
- NumberSubsetNonNegativeReal
-)
-
-type SubexASTNumberFilterSubset struct {
- subset NumberSubset
-}
-func (ast SubexASTNumberFilterSubset) compile() numberFilter {
- switch ast.subset {
- case NumberSubsetReal:
- return anyNumberFilter{}
- case NumberSubsetInteger:
- return divisibleNumberFilter {
- divisor: 1.0,
- target: 0.0,
- }
- case NumberSubsetPositiveInteger:
- return andNumberFilter {
- lhs: divisibleNumberFilter {
- divisor: 1.0,
- target: 0.0,
- },
- rhs: greaterThanNumberFilter {0.0},
- }
- case NumberSubsetZeroToOne:
- return andNumberFilter {
- lhs: notNumberFilter {
- lessThanNumberFilter {0},
- },
- rhs: notNumberFilter {
- greaterThanNumberFilter {1},
- },
- }
- case NumberSubsetPositiveReal:
- return greaterThanNumberFilter {0}
- case NumberSubsetNonNegativeReal:
- return notNumberFilter {
- lessThanNumberFilter {0},
- }
- default:
- panic("Invalid NumberSubset")
- }
-}
-func (ast SubexASTNumberFilterSubset) computable() bool {
- return false
-}
-func (ast SubexASTNumberFilterSubset) compute() float64 {
- panic("Tried to compute uncomputable")
-}
-
-type SubexASTNumberFilterCount struct {
- count int
-}
-func (ast SubexASTNumberFilterCount) compile() numberFilter {
- return andNumberFilter {
- lhs: andNumberFilter {
- lhs: notNumberFilter {
- lessThanNumberFilter {0.0},
- },
- rhs: lessThanNumberFilter {float64(ast.count)},
- },
- rhs: divisibleNumberFilter {
- divisor: 1.0,
- target: 0.0,
- },
- }
-}
-func (ast SubexASTNumberFilterCount) computable() bool {
- return false
-}
-func (ast SubexASTNumberFilterCount) compute() float64 {
- panic("Tried to compute uncomputable")
-}
-
-type SubexASTNumberFilterAdd struct {
- lhs, rhs SubexASTNumberFilter
-}
-func (ast SubexASTNumberFilterAdd) compile() numberFilter {
- if ast.lhs.computable() {
- return ast.rhs.compile().add(ast.lhs.compute())
- } else {
- return ast.lhs.compile().add(ast.rhs.compute())
- }
-}
-func (ast SubexASTNumberFilterAdd) computable() bool {
- return ast.lhs.computable() && ast.rhs.computable()
-}
-func (ast SubexASTNumberFilterAdd) compute() float64 {
- return ast.lhs.compute() + ast.rhs.compute()
-}
-func (ast SubexASTNumberFilterAdd) String() string {
- return fmt.Sprintf("(%v + %v)", ast.lhs, ast.rhs)
-}
-
-type SubexASTNumberFilterMultiply struct {
- lhs, rhs SubexASTNumberFilter
-}
-func (ast SubexASTNumberFilterMultiply) compile() numberFilter {
- if ast.lhs.computable() {
- return ast.rhs.compile().multiply(ast.lhs.compute())
- } else {
- return ast.lhs.compile().multiply(ast.rhs.compute())
- }
-}
-func (ast SubexASTNumberFilterMultiply) computable() bool {
- return ast.lhs.computable() && ast.rhs.computable()
-}
-func (ast SubexASTNumberFilterMultiply) compute() float64 {
- return ast.lhs.compute() * ast.rhs.compute()
-}
-func (ast SubexASTNumberFilterMultiply) String() string {
- return fmt.Sprintf("(%v * %v)", ast.lhs, ast.rhs)
-}
-
-type SubexASTCopyNumberFilter struct {
- filter SubexASTNumberFilter
-}
-func (ast SubexASTCopyNumberFilter) compileWith(next SubexState, slotMap *SlotMap, inType Type, outType Type) SubexState {
- if inType != ValueType || outType != ValueType {
- panic("Invalid types for SubexASTCopyNumberFilter")
- }
- return &SubexCopyNumberState {
- next: next,
- filter: ast.filter.compile(),
- }
-}
-
// Read in a null, bool, number, string or empty array or map and output it unchanged
type SubexASTCopyAnySimpleValue struct {}
func (ast SubexASTCopyAnySimpleValue) compileWith(next SubexState, slotMap *SlotMap, inType Type, outType Type) SubexState {
@@ -521,6 +375,21 @@ func (ast SubexASTOutput) String() string {
}
*/
+type SubexASTNumberMapping struct {
+ Range NumberExpr
+ Replace []NumberExpr
+}
+func (ast SubexASTNumberMapping) compileWith(next SubexState, slotMap *SlotMap, inType Type, outType Type) SubexState {
+ if inType != ValueType || outType != ValueType {
+ panic("Invalid in/out type for SubexASTNumberMapping")
+ }
+ return &SubexNumberMappingState {
+ Range: ast.Range,
+ Replace: ast.Replace,
+ next: next,
+ }
+}
+
type SubexASTOutputValueLiteral struct {
literal walk.Scalar
}
diff --git a/subex/subexstate.go b/subex/subexstate.go
index 3bcbdee..bf5bab9 100644
--- a/subex/subexstate.go
+++ b/subex/subexstate.go
@@ -104,6 +104,29 @@ func (state SubexCopyNumberState) accepting(aux auxiliaryState) []OutputStack {
return nil
}
+type SubexNumberMappingState struct {
+ Range NumberExpr
+ Replace []NumberExpr
+ next SubexState
+}
+func (state SubexNumberMappingState) eat(aux auxiliaryState, edible walk.Edible) []SubexBranch {
+ number, isNumber := edible.(walk.NumberValue)
+ if !isNumber || state.Range.Eval(float64(number)) == 0.0 {
+ return nil
+ }
+ var res []walk.Value
+ for _, expr := range state.Replace {
+ res = append(res, walk.NumberValue(expr.Eval(float64(number))))
+ }
+ return []SubexBranch {{
+ state: state.next,
+ aux: aux.topAppend(res),
+ }}
+}
+func (state SubexNumberMappingState) accepting(aux auxiliaryState) []OutputStack {
+ return nil
+}
+
// Just pushes to the OutputStack and hands over to the next state
// Used to capture the output of the state being handed over to
type SubexCaptureBeginState struct {
generated by cgit v1.2.3 (git 2.25.1) at 2025-10-19 17:26:38 +0000