Add method to merge subtrees in a clause tree

Add `Flatten` method to `query.Clause` which merges a parent clause with
its children.
The merge occurs if clauses have the same operator.
The merge transforms the tree similar to the examples below:

(+ (+ (+ (+ a b) c) d) e) -> (+ a b c d e)
(+ (+ a b) c (* d e))      -> (+ a b c (* d e))

2 files changed, 214 insertions, 4 deletions

diff --git a/pkg/query/parser.go b/pkg/query/parser.go
index 2a70819..e8fccfe 100644
--- a/pkg/query/parser.go
+++ b/pkg/query/parser.go
@@ -3,6 +3,7 @@ package query
 import (
 	"fmt"
 	"os"
+	"slices"
 	"strings"
 	"time"
 
@@ -76,7 +77,7 @@ var _ Valuer = StringValue{}
 var _ Valuer = DatetimeValue{}
 
 type StringValue struct {
-	s string
+	S string
 }
 
 func (v StringValue) Type() valuerType {
@@ -89,9 +90,9 @@ func (v StringValue) Compare(other Valuer) int {
 		return 0
 	}
 
-	if v.s < o.s {
+	if v.S < o.S {
 		return -1
-	} else if v.s > o.s {
+	} else if v.S > o.S {
 		return 1
 	} else {
 		return 0
@@ -218,6 +219,43 @@ func (c Clause) String() string {
 	return b.String()
 }
 
+// Merge child clauses with their parents when applicable
+func (root *Clause) Flatten() {
+	stack := make([]*Clause, 0, len(root.Clauses))
+	stack = append(stack, root)
+	for len(stack) != 0 {
+		top := len(stack) - 1
+		node := stack[top]
+		stack = stack[:top]
+
+		hasMerged := false
+		// cannot be "modernized", node.Clauses is modified in loop
+		for i := 0; i < len(node.Clauses); i++ {
+			child := node.Clauses[i]
+
+			// merge because of commutativity
+			if node.Operator == child.Operator {
+				hasMerged = true
+				node.Statements = append(node.Statements, child.Statements...)
+				node.Clauses = append(node.Clauses, child.Clauses...)
+			} else {
+				stack = append(stack, child)
+			}
+		}
+
+		if hasMerged {
+			numChildren := len(stack) - top
+			if numChildren > 0 {
+				node.Clauses = slices.Grow(node.Clauses, numChildren)
+				node.Clauses = node.Clauses[:numChildren]
+				copy(node.Clauses, stack[top:top+numChildren])
+			} else {
+				node.Clauses = nil
+			}
+		}
+	}
+}
+
 func (c Clause) buildString(b *strings.Builder, level int) {
 	writeIndent(b, level)
 	b.WriteByte('(')
@@ -349,7 +387,7 @@ func Parse(tokens []Token) (*Clause, error) {
 		default:
 			fmt.Fprintln(os.Stderr, token)
 			return nil, &TokenError{
-				got: token,
+				got:     token,
 				gotPrev: prevToken,
 			}
 		}
diff --git a/pkg/query/parser_test.go b/pkg/query/parser_test.go
new file mode 100644
index 0000000..7ee4987
--- /dev/null
+++ b/pkg/query/parser_test.go
@@ -0,0 +1,172 @@
+package query_test
+
+import (
+	"slices"
+	"testing"
+
+	"github.com/jpappel/atlas/pkg/query"
+)
+
+func TestClause_Flatten(t *testing.T) {
+	tests := []struct {
+		name     string
+		root     *query.Clause
+		expected query.Clause
+	}{
+		{
+			"empty",
+			&query.Clause{},
+			query.Clause{},
+		},
+		{
+			"already flat",
+			&query.Clause{
+				Operator: query.COP_AND,
+				Statements: []query.Statement{
+					{Category: query.CAT_AUTHOR, Operator: query.OP_AP, Value: query.StringValue{"jp"}},
+					{Category: query.CAT_TAGS, Operator: query.OP_EQ, Value: query.StringValue{"foobar"}},
+					{Category: query.CAT_TITLE, Operator: query.OP_AP, Value: query.StringValue{"a very interesting title"}},
+				},
+			},
+			query.Clause{
+				Operator: query.COP_AND,
+				Statements: []query.Statement{
+					{Category: query.CAT_TITLE, Operator: query.OP_AP, Value: query.StringValue{"a very interesting title"}},
+					{Category: query.CAT_TAGS, Operator: query.OP_EQ, Value: query.StringValue{"foobar"}},
+					{Category: query.CAT_AUTHOR, Operator: query.OP_AP, Value: query.StringValue{"jp"}},
+				},
+			},
+		},
+		{
+			"flatten 1 layer, multiple clauses",
+			&query.Clause{
+				Operator: query.COP_OR,
+				Statements: []query.Statement{
+					{Category: query.CAT_AUTHOR, Operator: query.OP_AP, Value: query.StringValue{"jp"}},
+					{Category: query.CAT_TAGS, Operator: query.OP_EQ, Value: query.StringValue{"foobar"}},
+					{Category: query.CAT_TITLE, Operator: query.OP_AP, Value: query.StringValue{"a very interesting title"}},
+				},
+				Clauses: []*query.Clause{
+					{Operator: query.COP_OR, Statements: []query.Statement{{Category: query.CAT_AUTHOR, Operator: query.OP_NE, Value: query.StringValue{"pj"}}}},
+					{Operator: query.COP_OR, Statements: []query.Statement{{Category: query.CAT_TAGS, Operator: query.OP_EQ, Value: query.StringValue{"barfoo"}}}},
+				},
+			},
+			query.Clause{
+				Operator: query.COP_OR,
+				Statements: []query.Statement{
+					{Category: query.CAT_TITLE, Operator: query.OP_AP, Value: query.StringValue{"a very interesting title"}},
+					{Category: query.CAT_TAGS, Operator: query.OP_EQ, Value: query.StringValue{"foobar"}},
+					{Category: query.CAT_AUTHOR, Operator: query.OP_AP, Value: query.StringValue{"jp"}},
+					{Category: query.CAT_AUTHOR, Operator: query.OP_NE, Value: query.StringValue{"pj"}},
+					{Category: query.CAT_TAGS, Operator: query.OP_EQ, Value: query.StringValue{"barfoo"}},
+				},
+			},
+		},
+		{
+			"flatten 2 layers",
+			&query.Clause{
+				Operator: query.COP_AND,
+				Statements: []query.Statement{
+					{Category: query.CAT_TITLE, Operator: query.OP_AP, Value: query.StringValue{"a very interesting title"}},
+					{Category: query.CAT_TAGS, Operator: query.OP_EQ, Value: query.StringValue{"foobar"}},
+				},
+				Clauses: []*query.Clause{
+					{
+						Operator: query.COP_AND,
+						Statements: []query.Statement{
+							{Category: query.CAT_AUTHOR, Operator: query.OP_AP, Value: query.StringValue{"jp"}},
+							{Category: query.CAT_AUTHOR, Operator: query.OP_NE, Value: query.StringValue{"pj"}},
+						},
+						Clauses: []*query.Clause{
+							{
+								Operator: query.COP_AND,
+								Statements: []query.Statement{
+									{Category: query.CAT_TAGS, Operator: query.OP_EQ, Value: query.StringValue{"barfoo"}},
+								},
+							},
+						},
+					},
+				},
+			},
+			query.Clause{
+				Operator: query.COP_AND,
+				Statements: []query.Statement{
+					{Category: query.CAT_TITLE, Operator: query.OP_AP, Value: query.StringValue{"a very interesting title"}},
+					{Category: query.CAT_TAGS, Operator: query.OP_EQ, Value: query.StringValue{"foobar"}},
+					{Category: query.CAT_AUTHOR, Operator: query.OP_AP, Value: query.StringValue{"jp"}},
+					{Category: query.CAT_AUTHOR, Operator: query.OP_NE, Value: query.StringValue{"pj"}},
+					{Category: query.CAT_TAGS, Operator: query.OP_EQ, Value: query.StringValue{"barfoo"}},
+				},
+			},
+		},
+		{
+			"flatten 1 child keep 1 child",
+			&query.Clause{
+				Operator: query.COP_AND,
+				Statements: []query.Statement{
+					{Category: query.CAT_TAGS, Operator: query.OP_EQ, Value: query.StringValue{"foobar"}},
+					{Category: query.CAT_TITLE, Operator: query.OP_AP, Value: query.StringValue{"a very interesting title"}},
+				},
+				Clauses: []*query.Clause{
+					{
+						Operator: query.COP_OR,
+						Statements: []query.Statement{
+							{Category: query.CAT_AUTHOR, Operator: query.OP_AP, Value: query.StringValue{"jp"}},
+							{Category: query.CAT_AUTHOR, Operator: query.OP_NE, Value: query.StringValue{"pj"}},
+						},
+					},
+					{
+						Operator: query.COP_AND,
+						Statements: []query.Statement{
+							{Category: query.CAT_TAGS, Operator: query.OP_EQ, Value: query.StringValue{"barfoo"}},
+						},
+					},
+				},
+			},
+			query.Clause{
+				Operator: query.COP_AND,
+				Statements: []query.Statement{
+					{Category: query.CAT_TAGS, Operator: query.OP_EQ, Value: query.StringValue{"foobar"}},
+					{Category: query.CAT_TITLE, Operator: query.OP_AP, Value: query.StringValue{"a very interesting title"}},
+					{Category: query.CAT_TAGS, Operator: query.OP_EQ, Value: query.StringValue{"barfoo"}},
+				},
+				Clauses: []*query.Clause{
+					{
+						Operator: query.COP_OR,
+						Statements: []query.Statement{
+							{Category: query.CAT_AUTHOR, Operator: query.OP_AP, Value: query.StringValue{"jp"}},
+							{Category: query.CAT_AUTHOR, Operator: query.OP_NE, Value: query.StringValue{"pj"}},
+						},
+					},
+				},
+			},
+		},
+	}
+	for _, tt := range tests {
+		t.Run(tt.name, func(t *testing.T) {
+			tt.root.Flatten()
+
+			slices.SortFunc(tt.root.Statements, query.StatementCmp)
+			slices.SortFunc(tt.expected.Statements, query.StatementCmp)
+
+			stmtsEq := slices.EqualFunc(tt.root.Statements, tt.expected.Statements,
+				func(a, b query.Statement) bool {
+					return a.Category == b.Category && a.Operator == b.Operator && a.Negated == b.Negated && a.Value.Compare(b.Value) == 0
+				},
+			)
+
+			if !stmtsEq {
+				t.Error("Statments not equal")
+				if gL, wL := len(tt.root.Statements), len(tt.expected.Statements); gL != wL {
+					t.Logf("Different number of statements: got %d want %d\n", gL, wL)
+				}
+			}
+
+			gotL, wantL := len(tt.root.Clauses), len(tt.expected.Clauses)
+
+			if gotL != wantL {
+				t.Errorf("Incorrect number of children clauses: got %d want %d\n", gotL, wantL)
+			}
+		})
+	}
+}