aboutsummaryrefslogtreecommitdiffstats
path: root/pkg/query
diff options
context:
space:
mode:
Diffstat (limited to 'pkg/query')
-rw-r--r--pkg/query/compiler.go94
-rw-r--r--pkg/query/optimizer.go38
-rw-r--r--pkg/query/parser.go31
3 files changed, 92 insertions, 71 deletions
diff --git a/pkg/query/compiler.go b/pkg/query/compiler.go
index f0df4b4..e6418d5 100644
--- a/pkg/query/compiler.go
+++ b/pkg/query/compiler.go
@@ -9,77 +9,27 @@ import (
const MAX_CLAUSE_DEPTH int = 16
-func (stmt Statement) Compile(b *strings.Builder) (*string, error) {
- if stmt.Negated {
- b.WriteString("NOT ")
- }
+type CompilationArtifact struct {
+ Query string
+ Args []string
+}
- switch stmt.Category {
- case CAT_TITLE:
- b.WriteString("title ")
- case CAT_AUTHOR:
- b.WriteString("author ")
- case CAT_DATE:
- b.WriteString("date ")
- case CAT_FILETIME:
- b.WriteString("fileTime ")
- case CAT_TAGS:
- b.WriteString("tags ")
- case CAT_LINKS:
- b.WriteString("links ")
- default:
- return nil, &CompileError{
- fmt.Sprint("unknown or invalid category ", stmt.Category.String()),
- }
- }
- switch stmt.Operator {
- case OP_EQ:
- if stmt.Category.IsSet() {
- b.WriteString("IN ")
+func (art CompilationArtifact) String() string {
+ b := strings.Builder{}
+ fmt.Fprintln(&b, art.Query)
+ b.WriteByte('[')
+ for i, arg := range art.Args {
+ if i != len(art.Args)-1 {
+ fmt.Fprintf(&b, "`%s`, ", arg)
} else {
- b.WriteString("= ")
- }
- case OP_AP:
- b.WriteString("LIKE ")
- case OP_NE:
- b.WriteString("!= ")
- case OP_LT:
- b.WriteString("< ")
- case OP_LE:
- b.WriteString("<= ")
- case OP_GE:
- b.WriteString(">= ")
- case OP_GT:
- b.WriteString("> ")
- default:
- return nil, &CompileError{
- fmt.Sprint("unknown or invalid operand ", stmt.Operator.String()),
+ fmt.Fprintf(&b, "`%s`", arg)
}
}
-
- switch stmt.Value.Type() {
- case VAL_STR:
- s, ok := stmt.Value.(StringValue)
- if !ok {
- panic(CompileError{"type corruption in string value"})
- }
- b.WriteString("(?) ")
- return &s.S, nil
- case VAL_DATETIME:
- dt, ok := stmt.Value.(DatetimeValue)
- if !ok {
- panic(CompileError{"type corruption in datetime value"})
- }
- fmt.Fprint(b, dt.D.Unix(), " ")
- default:
- return nil, &CompileError{
- fmt.Sprint("unknown or invalid value type ", stmt.Value.Type()),
- }
- }
- return nil, nil
+ b.WriteByte(']')
+ return b.String()
}
-func (s Statements) Compile(b *strings.Builder, delim string) ([]string, error) {
+func (s Statements) buildCompile(b *strings.Builder, delim string) ([]string, error) {
var args []string
sCount := 0
@@ -185,6 +135,7 @@ func (s Statements) Compile(b *strings.Builder, delim string) ([]string, error)
start, end := util.FuzzDatetime(d.D)
+ b.WriteString("NOT ")
b.WriteString(opStr)
fmt.Fprint(b, start.Unix(), " ")
b.WriteString("AND ")
@@ -199,6 +150,9 @@ func (s Statements) Compile(b *strings.Builder, delim string) ([]string, error)
} else {
idx := 0
for _, stmt := range opStmts {
+ if stmt.Negated {
+ b.WriteString("NOT ")
+ }
b.WriteString(catStr)
b.WriteString(opStr)
arg, ok := stmt.Value.buildCompile(b)
@@ -229,9 +183,9 @@ func (s Statements) Compile(b *strings.Builder, delim string) ([]string, error)
return args, nil
}
-func (root Clause) Compile() (string, []string, error) {
+func (root Clause) Compile() (CompilationArtifact, error) {
if d := root.Depth(); d > MAX_CLAUSE_DEPTH {
- return "", nil, &CompileError{
+ return CompilationArtifact{}, &CompileError{
fmt.Sprintf("exceeded maximum clause depth: %d > %d", d, MAX_CLAUSE_DEPTH),
}
}
@@ -239,9 +193,9 @@ func (root Clause) Compile() (string, []string, error) {
b := strings.Builder{}
args, err := root.buildCompile(&b)
if err != nil {
- return "", nil, err
+ return CompilationArtifact{}, err
}
- return b.String(), args, nil
+ return CompilationArtifact{b.String(), args}, nil
}
func (c Clause) buildCompile(b *strings.Builder) ([]string, error) {
@@ -257,7 +211,7 @@ func (c Clause) buildCompile(b *strings.Builder) ([]string, error) {
return nil, &CompileError{fmt.Sprint("invalid clause operator ", c.Operator)}
}
- args, err := c.Statements.Compile(b, delim)
+ args, err := c.Statements.buildCompile(b, delim)
if err != nil {
return nil, err
}
diff --git a/pkg/query/optimizer.go b/pkg/query/optimizer.go
index c203b9c..cdb2455 100644
--- a/pkg/query/optimizer.go
+++ b/pkg/query/optimizer.go
@@ -47,6 +47,38 @@ func NewOptimizer(root *Clause, workers uint) Optimizer {
}
}
+// Optimize clause according to level.
+// level 0 is automatic and levels < 0 do nothing.
+func (o Optimizer) Optimize(level int) {
+ o.Simplify()
+ if level < 0 {
+ return
+ } else if level == 0 {
+ // TODO: determine smarter level determination strategy
+ level = o.root.Depth()
+ }
+
+ oldDepth := o.root.Depth()
+ for range level {
+ // clause level parallel
+ o.Compact()
+ o.StrictEquality()
+ o.Tighten()
+ o.Contradictions()
+ // parallel + serial
+ o.Tidy()
+ // purely serial
+ o.Flatten()
+
+ depth := o.root.Depth()
+ if depth == oldDepth {
+ break
+ } else {
+ oldDepth = depth
+ }
+ }
+}
+
// Perform optimizations in parallel. They should **NOT** mutate the tree
func (o Optimizer) parallel(optimize func(*Clause)) {
jobs := make(chan *Clause, o.workers)
@@ -131,6 +163,12 @@ func (o *Optimizer) Flatten() {
})
}
+// Remove multiples of equivalent statements within the same clause
+//
+// Examples
+//
+// (and a="Fred Flinstone" a="Fred Flinstone") --> (and a="Fred Flinstone")
+// (or a=Shaggy -a!=Shaggy) --> (or a=Shaggy)
func (o *Optimizer) Compact() {
o.parallel(func(c *Clause) {
c.Statements = slices.CompactFunc(c.Statements, StatementEq)
diff --git a/pkg/query/parser.go b/pkg/query/parser.go
index 178665d..c52530e 100644
--- a/pkg/query/parser.go
+++ b/pkg/query/parser.go
@@ -322,6 +322,35 @@ func (s Statements) OperatorPartition() iter.Seq2[opType, Statements] {
}
}
+// Partition statements by their negated status without copying, similar to
+// CategoryPartition and OperatorPartition
+func (s Statements) NegatedPartition() iter.Seq2[bool, Statements] {
+ if !slices.IsSortedFunc(s, StatementCmp) {
+ slices.SortFunc(s, StatementCmp)
+ }
+
+ return func(yield func(bool, Statements) bool) {
+ firstNegated := -1
+ for i, stmt := range s {
+ if stmt.Negated {
+ firstNegated = i
+ }
+ }
+
+ if firstNegated > 0 {
+ if !yield(false, s[:firstNegated]) {
+ return
+ } else if !yield(true, s[firstNegated:]) {
+ return
+ }
+ } else {
+ if !yield(false, s) {
+ return
+ }
+ }
+ }
+}
+
func (c Clause) String() string {
b := &strings.Builder{}
c.buildString(b, 0)
@@ -459,7 +488,7 @@ func Parse(tokens []Token) (*Clause, error) {
}
clause.Operator = COP_OR
case TOK_OP_NEG:
- if !prevToken.Type.Any(TOK_CLAUSE_OR, TOK_CLAUSE_AND, TOK_VAL_STR, TOK_VAL_DATETIME) {
+ if !prevToken.Type.Any(TOK_CLAUSE_OR, TOK_CLAUSE_AND, TOK_VAL_STR, TOK_VAL_DATETIME, TOK_CLAUSE_END) {
return nil, &TokenError{
got: token,
gotPrev: prevToken,
generated by cgit v1.2.3 (git 2.39.1) at 2025-12-06 10:11:42 +0000