diff options
Diffstat (limited to 'vendor/github.com/cloudwego/iasm/expr')
| -rw-r--r-- | vendor/github.com/cloudwego/iasm/expr/ast.go | 261 | ||||
| -rw-r--r-- | vendor/github.com/cloudwego/iasm/expr/errors.go | 53 | ||||
| -rw-r--r-- | vendor/github.com/cloudwego/iasm/expr/ops.go | 67 | ||||
| -rw-r--r-- | vendor/github.com/cloudwego/iasm/expr/parser.go | 329 | ||||
| -rw-r--r-- | vendor/github.com/cloudwego/iasm/expr/pools.go | 42 | ||||
| -rw-r--r-- | vendor/github.com/cloudwego/iasm/expr/term.go | 23 | ||||
| -rw-r--r-- | vendor/github.com/cloudwego/iasm/expr/utils.go | 77 |
7 files changed, 852 insertions, 0 deletions
diff --git a/vendor/github.com/cloudwego/iasm/expr/ast.go b/vendor/github.com/cloudwego/iasm/expr/ast.go new file mode 100644 index 000000000..a91bb2e25 --- /dev/null +++ b/vendor/github.com/cloudwego/iasm/expr/ast.go @@ -0,0 +1,261 @@ +// +// Copyright 2024 CloudWeGo Authors +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. +// + +package expr + +import ( + `fmt` +) + +// Type is tyep expression type. +type Type int + +const ( + // CONST indicates that the expression is a constant. + CONST Type = iota + + // TERM indicates that the expression is a Term reference. + TERM + + // EXPR indicates that the expression is a unary or binary expression. + EXPR +) + +var typeNames = map[Type]string { + EXPR : "Expr", + TERM : "Term", + CONST : "Const", +} + +// String returns the string representation of a Type. +func (self Type) String() string { + if v, ok := typeNames[self]; ok { + return v + } else { + return fmt.Sprintf("expr.Type(%d)", self) + } +} + +// Operator represents an operation to perform when Type is EXPR. +type Operator uint8 + +const ( + // ADD performs "Add Expr.Left and Expr.Right". + ADD Operator = iota + + // SUB performs "Subtract Expr.Left by Expr.Right". + SUB + + // MUL performs "Multiply Expr.Left by Expr.Right". + MUL + + // DIV performs "Divide Expr.Left by Expr.Right". + DIV + + // MOD performs "Modulo Expr.Left by Expr.Right". + MOD + + // AND performs "Bitwise AND Expr.Left and Expr.Right". + AND + + // OR performs "Bitwise OR Expr.Left and Expr.Right". + OR + + // XOR performs "Bitwise XOR Expr.Left and Expr.Right". + XOR + + // SHL performs "Bitwise Shift Expr.Left to the Left by Expr.Right Bits". + SHL + + // SHR performs "Bitwise Shift Expr.Left to the Right by Expr.Right Bits". + SHR + + // POW performs "Raise Expr.Left to the power of Expr.Right" + POW + + // NOT performs "Bitwise Invert Expr.Left". + NOT + + // NEG performs "Negate Expr.Left". + NEG +) + +var operatorNames = map[Operator]string { + ADD : "Add", + SUB : "Subtract", + MUL : "Multiply", + DIV : "Divide", + MOD : "Modulo", + AND : "And", + OR : "Or", + XOR : "ExclusiveOr", + SHL : "ShiftLeft", + SHR : "ShiftRight", + POW : "Power", + NOT : "Invert", + NEG : "Negate", +} + +// String returns the string representation of a Type. +func (self Operator) String() string { + if v, ok := operatorNames[self]; ok { + return v + } else { + return fmt.Sprintf("expr.Operator(%d)", self) + } +} + +// Expr represents an expression node. +type Expr struct { + Type Type + Term Term + Op Operator + Left *Expr + Right *Expr + Const int64 +} + +// Ref creates an expression from a Term. +func Ref(t Term) (p *Expr) { + p = newExpression() + p.Term = t + p.Type = TERM + return +} + +// Int creates an expression from an integer. +func Int(v int64) (p *Expr) { + p = newExpression() + p.Type = CONST + p.Const = v + return +} + +func (self *Expr) clear() { + if self.Term != nil { self.Term.Free() } + if self.Left != nil { self.Left.Free() } + if self.Right != nil { self.Right.Free() } +} + +// Free returns the Expr into pool. +// Any operation performed after Free is undefined behavior. +func (self *Expr) Free() { + self.clear() + freeExpression(self) +} + +// Evaluate evaluates the expression into an integer. +// It also implements the Term interface. +func (self *Expr) Evaluate() (int64, error) { + switch self.Type { + case EXPR : return self.eval() + case TERM : return self.Term.Evaluate() + case CONST : return self.Const, nil + default : panic("invalid expression type: " + self.Type.String()) + } +} + +/** Expression Combinator **/ + +func combine(a *Expr, op Operator, b *Expr) (r *Expr) { + r = newExpression() + r.Op = op + r.Type = EXPR + r.Left = a + r.Right = b + return +} + +func (self *Expr) Add(v *Expr) *Expr { return combine(self, ADD, v) } +func (self *Expr) Sub(v *Expr) *Expr { return combine(self, SUB, v) } +func (self *Expr) Mul(v *Expr) *Expr { return combine(self, MUL, v) } +func (self *Expr) Div(v *Expr) *Expr { return combine(self, DIV, v) } +func (self *Expr) Mod(v *Expr) *Expr { return combine(self, MOD, v) } +func (self *Expr) And(v *Expr) *Expr { return combine(self, AND, v) } +func (self *Expr) Or (v *Expr) *Expr { return combine(self, OR , v) } +func (self *Expr) Xor(v *Expr) *Expr { return combine(self, XOR, v) } +func (self *Expr) Shl(v *Expr) *Expr { return combine(self, SHL, v) } +func (self *Expr) Shr(v *Expr) *Expr { return combine(self, SHR, v) } +func (self *Expr) Pow(v *Expr) *Expr { return combine(self, POW, v) } +func (self *Expr) Not() *Expr { return combine(self, NOT, nil) } +func (self *Expr) Neg() *Expr { return combine(self, NEG, nil) } + +/** Expression Evaluator **/ + +var binaryEvaluators = [256]func(int64, int64) (int64, error) { + ADD: func(a, b int64) (int64, error) { return a + b, nil }, + SUB: func(a, b int64) (int64, error) { return a - b, nil }, + MUL: func(a, b int64) (int64, error) { return a * b, nil }, + DIV: idiv, + MOD: imod, + AND: func(a, b int64) (int64, error) { return a & b, nil }, + OR: func(a, b int64) (int64, error) { return a | b, nil }, + XOR: func(a, b int64) (int64, error) { return a ^ b, nil }, + SHL: func(a, b int64) (int64, error) { return a << b, nil }, + SHR: func(a, b int64) (int64, error) { return a >> b, nil }, + POW: ipow, +} + +func (self *Expr) eval() (int64, error) { + var lhs int64 + var rhs int64 + var err error + var vfn func(int64, int64) (int64, error) + + /* evaluate LHS */ + if lhs, err = self.Left.Evaluate(); err != nil { + return 0, err + } + + /* check for unary operators */ + switch self.Op { + case NOT: return self.unaryNot(lhs) + case NEG: return self.unaryNeg(lhs) + } + + /* check for operators */ + if vfn = binaryEvaluators[self.Op]; vfn == nil { + panic("invalid operator: " + self.Op.String()) + } + + /* must be a binary expression */ + if self.Right == nil { + panic("operator " + self.Op.String() + " is a binary operator") + } + + /* evaluate RHS, and call the operator */ + if rhs, err = self.Right.Evaluate(); err != nil { + return 0, err + } else { + return vfn(lhs, rhs) + } +} + +func (self *Expr) unaryNot(v int64) (int64, error) { + if self.Right == nil { + return ^v, nil + } else { + panic("operator Invert is an unary operator") + } +} + +func (self *Expr) unaryNeg(v int64) (int64, error) { + if self.Right == nil { + return -v, nil + } else { + panic("operator Negate is an unary operator") + } +} diff --git a/vendor/github.com/cloudwego/iasm/expr/errors.go b/vendor/github.com/cloudwego/iasm/expr/errors.go new file mode 100644 index 000000000..ece4cb8dd --- /dev/null +++ b/vendor/github.com/cloudwego/iasm/expr/errors.go @@ -0,0 +1,53 @@ +// +// Copyright 2024 CloudWeGo Authors +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. +// + +package expr + +import ( + `fmt` +) + +// SyntaxError represents a syntax error in the expression. +type SyntaxError struct { + Pos int + Reason string +} + +func newSyntaxError(pos int, reason string) *SyntaxError { + return &SyntaxError { + Pos : pos, + Reason : reason, + } +} + +func (self *SyntaxError) Error() string { + return fmt.Sprintf("Syntax error at position %d: %s", self.Pos, self.Reason) +} + +// RuntimeError is an error which would occure at run time. +type RuntimeError struct { + Reason string +} + +func newRuntimeError(reason string) *RuntimeError { + return &RuntimeError { + Reason: reason, + } +} + +func (self *RuntimeError) Error() string { + return "Runtime error: " + self.Reason +} diff --git a/vendor/github.com/cloudwego/iasm/expr/ops.go b/vendor/github.com/cloudwego/iasm/expr/ops.go new file mode 100644 index 000000000..7f168b902 --- /dev/null +++ b/vendor/github.com/cloudwego/iasm/expr/ops.go @@ -0,0 +1,67 @@ +// +// Copyright 2024 CloudWeGo Authors +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. +// + +package expr + +import ( + `fmt` +) + +func idiv(v int64, d int64) (int64, error) { + if d != 0 { + return v / d, nil + } else { + return 0, newRuntimeError("division by zero") + } +} + +func imod(v int64, d int64) (int64, error) { + if d != 0 { + return v % d, nil + } else { + return 0, newRuntimeError("division by zero") + } +} + +func ipow(v int64, e int64) (int64, error) { + mul := v + ret := int64(1) + + /* value must be 0 or positive */ + if v < 0 { + return 0, newRuntimeError(fmt.Sprintf("negative base value: %d", v)) + } + + /* exponent must be non-negative */ + if e < 0 { + return 0, newRuntimeError(fmt.Sprintf("negative exponent: %d", e)) + } + + /* fast power first round */ + if (e & 1) != 0 { + ret *= mul + } + + /* fast power remaining rounds */ + for e >>= 1; e != 0; e >>= 1 { + if mul *= mul; (e & 1) != 0 { + ret *= mul + } + } + + /* all done */ + return ret, nil +} diff --git a/vendor/github.com/cloudwego/iasm/expr/parser.go b/vendor/github.com/cloudwego/iasm/expr/parser.go new file mode 100644 index 000000000..1846a58a0 --- /dev/null +++ b/vendor/github.com/cloudwego/iasm/expr/parser.go @@ -0,0 +1,329 @@ +// +// Copyright 2024 CloudWeGo Authors +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. +// + +package expr + +import ( + `strconv` + `unicode` + `unsafe` +) + +type _TokenKind uint8 + +const ( + _T_end _TokenKind = iota + 1 + _T_int + _T_punc + _T_name +) + +const ( + _OP2 = 0x80 + _POW = _OP2 | '*' + _SHL = _OP2 | '<' + _SHR = _OP2 | '>' +) + +type _Slice struct { + p unsafe.Pointer + n int + c int +} + +type _Token struct { + pos int + ptr *rune + u64 uint64 + tag _TokenKind +} + +func (self _Token) str() (v string) { + return string(self.rbuf()) +} + +func (self _Token) rbuf() (v []rune) { + (*_Slice)(unsafe.Pointer(&v)).c = int(self.u64) + (*_Slice)(unsafe.Pointer(&v)).n = int(self.u64) + (*_Slice)(unsafe.Pointer(&v)).p = unsafe.Pointer(self.ptr) + return +} + +func tokenEnd(p int) _Token { + return _Token { + pos: p, + tag: _T_end, + } +} + +func tokenInt(p int, v uint64) _Token { + return _Token { + pos: p, + u64: v, + tag: _T_int, + } +} + +func tokenPunc(p int, v rune) _Token { + return _Token { + pos: p, + tag: _T_punc, + u64: uint64(v), + } +} + +func tokenName(p int, v []rune) _Token { + return _Token { + pos: p, + ptr: &v[0], + tag: _T_name, + u64: uint64(len(v)), + } +} + +// Repository represents a repository of Term's. +type Repository interface { + Get(name string) (Term, error) +} + +// Parser parses an expression string to it's AST representation. +type Parser struct { + pos int + src []rune +} + +var binaryOps = [...]func(*Expr, *Expr) *Expr { + '+' : (*Expr).Add, + '-' : (*Expr).Sub, + '*' : (*Expr).Mul, + '/' : (*Expr).Div, + '%' : (*Expr).Mod, + '&' : (*Expr).And, + '^' : (*Expr).Xor, + '|' : (*Expr).Or, + _SHL : (*Expr).Shl, + _SHR : (*Expr).Shr, + _POW : (*Expr).Pow, +} + +var precedence = [...]map[int]bool { + {_SHL: true, _SHR: true}, + {'|' : true}, + {'^' : true}, + {'&' : true}, + {'+' : true, '-': true}, + {'*' : true, '/': true, '%': true}, + {_POW: true}, +} + +func (self *Parser) ch() rune { + return self.src[self.pos] +} + +func (self *Parser) eof() bool { + return self.pos >= len(self.src) +} + +func (self *Parser) rch() (v rune) { + v, self.pos = self.src[self.pos], self.pos + 1 + return +} + +func (self *Parser) hex(ss []rune) bool { + if len(ss) == 1 && ss[0] == '0' { + return unicode.ToLower(self.ch()) == 'x' + } else if len(ss) <= 1 || unicode.ToLower(ss[1]) != 'x' { + return unicode.IsDigit(self.ch()) + } else { + return ishexdigit(self.ch()) + } +} + +func (self *Parser) int(p int, ss []rune) (_Token, error) { + var err error + var val uint64 + + /* find all the digits */ + for !self.eof() && self.hex(ss) { + ss = append(ss, self.rch()) + } + + /* parse the value */ + if val, err = strconv.ParseUint(string(ss), 0, 64); err != nil { + return _Token{}, err + } else { + return tokenInt(p, val), nil + } +} + +func (self *Parser) name(p int, ss []rune) _Token { + for !self.eof() && isident(self.ch()) { ss = append(ss, self.rch()) } + return tokenName(p, ss) +} + +func (self *Parser) read(p int, ch rune) (_Token, error) { + if isdigit(ch) { + return self.int(p, []rune { ch }) + } else if isident0(ch) { + return self.name(p, []rune { ch }), nil + } else if isop2ch(ch) && !self.eof() && self.ch() == ch { + return tokenPunc(p, _OP2 | self.rch()), nil + } else if isop1ch(ch) { + return tokenPunc(p, ch), nil + } else { + return _Token{}, newSyntaxError(self.pos, "invalid character " + strconv.QuoteRuneToASCII(ch)) + } +} + +func (self *Parser) next() (_Token, error) { + for { + var p int + var c rune + + /* check for EOF */ + if self.eof() { + return tokenEnd(self.pos), nil + } + + /* read the next char */ + p = self.pos + c = self.rch() + + /* parse the token if not a space */ + if !unicode.IsSpace(c) { + return self.read(p, c) + } + } +} + +func (self *Parser) grab(tk _Token, repo Repository) (*Expr, error) { + if repo == nil { + return nil, newSyntaxError(tk.pos, "unresolved symbol: " + tk.str()) + } else if term, err := repo.Get(tk.str()); err != nil { + return nil, err + } else { + return Ref(term), nil + } +} + +func (self *Parser) nest(nest int, repo Repository) (*Expr, error) { + var err error + var ret *Expr + var ntk _Token + + /* evaluate the nested expression */ + if ret, err = self.expr(0, nest + 1, repo); err != nil { + return nil, err + } + + /* must follows with a ')' */ + if ntk, err = self.next(); err != nil { + return nil, err + } else if ntk.tag != _T_punc || ntk.u64 != ')' { + return nil, newSyntaxError(ntk.pos, "')' expected") + } else { + return ret, nil + } +} + +func (self *Parser) unit(nest int, repo Repository) (*Expr, error) { + if tk, err := self.next(); err != nil { + return nil, err + } else if tk.tag == _T_int { + return Int(int64(tk.u64)), nil + } else if tk.tag == _T_name { + return self.grab(tk, repo) + } else if tk.tag == _T_punc && tk.u64 == '(' { + return self.nest(nest, repo) + } else if tk.tag == _T_punc && tk.u64 == '+' { + return self.unit(nest, repo) + } else if tk.tag == _T_punc && tk.u64 == '-' { + return neg2(self.unit(nest, repo)) + } else if tk.tag == _T_punc && tk.u64 == '~' { + return not2(self.unit(nest, repo)) + } else { + return nil, newSyntaxError(tk.pos, "integer, unary operator or nested expression expected") + } +} + +func (self *Parser) term(prec int, nest int, repo Repository) (*Expr, error) { + var err error + var val *Expr + + /* parse the LHS operand */ + if val, err = self.expr(prec + 1, nest, repo); err != nil { + return nil, err + } + + /* parse all the operators of the same precedence */ + for { + var op int + var rv *Expr + var tk _Token + + /* peek the next token */ + pp := self.pos + tk, err = self.next() + + /* check for errors */ + if err != nil { + return nil, err + } + + /* encountered EOF */ + if tk.tag == _T_end { + return val, nil + } + + /* must be an operator */ + if tk.tag != _T_punc { + return nil, newSyntaxError(tk.pos, "operators expected") + } + + /* check for the operator precedence */ + if op = int(tk.u64); !precedence[prec][op] { + self.pos = pp + return val, nil + } + + /* evaluate the RHS operand, and combine the value */ + if rv, err = self.expr(prec + 1, nest, repo); err != nil { + return nil, err + } else { + val = binaryOps[op](val, rv) + } + } +} + +func (self *Parser) expr(prec int, nest int, repo Repository) (*Expr, error) { + if prec >= len(precedence) { + return self.unit(nest, repo) + } else { + return self.term(prec, nest, repo) + } +} + +// Parse parses the expression, and returns it's AST tree. +func (self *Parser) Parse(repo Repository) (*Expr, error) { + return self.expr(0, 0, repo) +} + +// SetSource resets the expression parser and sets the expression source. +func (self *Parser) SetSource(src string) *Parser { + self.pos = 0 + self.src = []rune(src) + return self +} diff --git a/vendor/github.com/cloudwego/iasm/expr/pools.go b/vendor/github.com/cloudwego/iasm/expr/pools.go new file mode 100644 index 000000000..869225242 --- /dev/null +++ b/vendor/github.com/cloudwego/iasm/expr/pools.go @@ -0,0 +1,42 @@ +// +// Copyright 2024 CloudWeGo Authors +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. +// + +package expr + +import ( + `sync` +) + +var ( + expressionPool sync.Pool +) + +func newExpression() *Expr { + if v := expressionPool.Get(); v == nil { + return new(Expr) + } else { + return resetExpression(v.(*Expr)) + } +} + +func freeExpression(p *Expr) { + expressionPool.Put(p) +} + +func resetExpression(p *Expr) *Expr { + *p = Expr{} + return p +} diff --git a/vendor/github.com/cloudwego/iasm/expr/term.go b/vendor/github.com/cloudwego/iasm/expr/term.go new file mode 100644 index 000000000..45042334b --- /dev/null +++ b/vendor/github.com/cloudwego/iasm/expr/term.go @@ -0,0 +1,23 @@ +// +// Copyright 2024 CloudWeGo Authors +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. +// + +package expr + +// Term represents a value that can Evaluate() into an integer. +type Term interface { + Free() + Evaluate() (int64, error) +} diff --git a/vendor/github.com/cloudwego/iasm/expr/utils.go b/vendor/github.com/cloudwego/iasm/expr/utils.go new file mode 100644 index 000000000..780f406e7 --- /dev/null +++ b/vendor/github.com/cloudwego/iasm/expr/utils.go @@ -0,0 +1,77 @@ +// +// Copyright 2024 CloudWeGo Authors +// +// Licensed under the Apache License, Version 2.0 (the "License"); +// you may not use this file except in compliance with the License. +// You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, software +// distributed under the License is distributed on an "AS IS" BASIS, +// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +// See the License for the specific language governing permissions and +// limitations under the License. +// + +package expr + +var op1ch = [...]bool { + '+': true, + '-': true, + '*': true, + '/': true, + '%': true, + '&': true, + '|': true, + '^': true, + '~': true, + '(': true, + ')': true, +} + +var op2ch = [...]bool { + '*': true, + '<': true, + '>': true, +} + +func neg2(v *Expr, err error) (*Expr, error) { + if err != nil { + return nil, err + } else { + return v.Neg(), nil + } +} + +func not2(v *Expr, err error) (*Expr, error) { + if err != nil { + return nil, err + } else { + return v.Not(), nil + } +} + +func isop1ch(ch rune) bool { + return ch >= 0 && int(ch) < len(op1ch) && op1ch[ch] +} + +func isop2ch(ch rune) bool { + return ch >= 0 && int(ch) < len(op2ch) && op2ch[ch] +} + +func isdigit(ch rune) bool { + return ch >= '0' && ch <= '9' +} + +func isident(ch rune) bool { + return isdigit(ch) || isident0(ch) +} + +func isident0(ch rune) bool { + return (ch == '_') || (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') +} + +func ishexdigit(ch rune) bool { + return isdigit(ch) || (ch >= 'a' && ch <= 'f') || (ch >= 'A' && ch <= 'F') +} |