Repository: mbrt/gmailctl (go)

Issue:
Chunking supported?
I have very long lists of `{from: …}` blocks. The longest one is over 200 entries. While the Gmail API accepts this, clicking on edit in the UI (so that I can apply to existing emails) presents an alert that the rule is too long.

Is there a way to _chunk_ the list? For example, in chunks of 75. 200 entries in chunks of 75 would create three rules with entries:

* 1–75
* 76–150
* 150–200

This would simplify maintenance so that I could keep the one long list, but the software (or configuration) can deal with chunking across multiple rules.

Pull request description:
Split long filters
Close #158 

Patch:
diff --git a/pkg/filter/convert.go b/pkg/filter/convert.go
index 57d71f7..39ca992 100644
--- a/pkg/filter/convert.go
+++ b/pkg/filter/convert.go
@@ -8,11 +8,21 @@ import (
 	"github.com/mbrt/gmailctl/pkg/parser"
 )
 
+// There's no documented limit on filter size on Gmail, but this educated guess
+// is better than nothing.
+const defaultSizeLimit = 20
+
 // FromRules translates rules into entries that map directly into Gmail filters.
 func FromRules(rs []parser.Rule) (Filters, error) {
+	return FromRulesWithLimit(rs, defaultSizeLimit)
+}
+
+// FromRulesWithLimit translates rules into entries that map directly into
+// Gmail, but uses a custom size limit.
+func FromRulesWithLimit(rs []parser.Rule, sizeLimit int) (Filters, error) {
 	res := Filters{}
 	for i, rule := range rs {
-		filters, err := FromRule(rule)
+		filters, err := FromRule(rule, sizeLimit)
 		if err != nil {
 			return res, fmt.Errorf("generating rule #%d: %w", i, err)
 		}
@@ -22,9 +32,9 @@ func FromRules(rs []parser.Rule) (Filters, error) {
 }
 
 // FromRule translates a rule into entries that map directly into Gmail filters.
-func FromRule(rule parser.Rule) ([]Filter, error) {
+func FromRule(rule parser.Rule, sizeLimit int) (Filters, error) {
 	var crits []Criteria
-	for _, c := range splitRootOr(rule.Criteria) {
+	for _, c := range splitCriteria(rule.Criteria, sizeLimit) {
 		criteria, err := GenerateCriteria(c)
 		if err != nil {
 			return nil, fmt.Errorf("generating criteria: %w", err)
@@ -238,6 +248,168 @@ func escape(a string) string {
 	return a
 }
 
+func splitCriteria(tree parser.CriteriaAST, limit int) []parser.CriteriaAST {
+	var res []parser.CriteriaAST
+	for _, c := range splitRootOr(tree) {
+		res = append(res, splitBigCriteria(c, limit)...)
+	}
+	return res
+}
+
+type splitVisitor struct {
+	limit int
+	res   []parser.CriteriaAST
+}
+
+func (v *splitVisitor) VisitNode(n *parser.Node) {
+	rem := n.Children
+	for len(rem) > v.limit {
+		v.res = append(v.res, &parser.Node{
+			Operation: n.Operation,
+			Children:  rem[:v.limit],
+		})
+		rem = rem[v.limit:]
+	}
+	// Add the last chunk.
+	v.res = append(v.res, &parser.Node{
+		Operation: n.Operation,
+		Children:  rem,
+	})
+}
+
+func (v *splitVisitor) VisitLeaf(n *parser.Leaf) {
+	rem := n.Args
+	for len(rem) > v.limit {
+		v.res = append(v.res, &parser.Leaf{
+			Function: n.Function,
+			Grouping: n.Grouping,
+			IsRaw:    n.IsRaw,
+			Args:     rem[:v.limit],
+		})
+		rem = rem[v.limit:]
+	}
+	// Add the last chunk.
+	v.res = append(v.res, &parser.Leaf{
+		Function: n.Function,
+		Grouping: n.Grouping,
+		IsRaw:    n.IsRaw,
+		Args:     rem,
+	})
+}
+
+func splitBigCriteria(tree parser.CriteriaAST, limit int) []parser.CriteriaAST {
+	// Gmail filters have a size limit, after which they will silently
+	// fail to be applied. To counter that we try to split up filters
+	// that are too big.
+	if size := countNodes(tree); size < limit {
+		// We don't bother with small filters.
+		return []parser.CriteriaAST{tree}
+	}
+	if tree.RootOperation() == parser.OperationOr {
+		// If the root operation is OR, we can split.
+		sv := splitVisitor{limit: limit}
+		tree.AcceptVisitor(&sv)
+		return sv.res
+	}
+	if tree.RootOperation() == parser.OperationAnd {
+		// We still have hope to split this and have set of smaller filters.
+		// We just need to find the biggest child with an OR at the root and
+		// split it this way:
+		// ({a, b, c} d) => ({a, b} d), (c d)
+		return splitNestedAnd(tree, limit)
+	}
+
+	// Nothing we can do about this :(
+	return []parser.CriteriaAST{tree}
+}
+
+func splitNestedAnd(root parser.CriteriaAST, limit int) []parser.CriteriaAST {
+	n, ok := root.(*parser.Node)
+	if !ok {
+		// There's no nesting, just a single function, so we can't do anything.
+		return []parser.CriteriaAST{root}
+	}
+
+	// Find the biggest child with the form {a, b, c, d}
+	maxChildren := 0
+	childID := -1
+	for i, c := range n.Children {
+		if count := countNodes(c); count > maxChildren && c.RootOperation() == parser.OperationOr {
+			childID = i
+			maxChildren = count
+		}
+	}
+	if childID < 0 {
+		// We couldn't find any child with an OR as root operation.
+		return []parser.CriteriaAST{root}
+	}
+	bigChild := n.Children[childID]
+
+	// Split it up.
+	// We want to respect the limit for each new split up filter, but not go
+	// over the top and split it completely.
+	siblingsSize := countNodes(root) - maxChildren
+	newLimit := limit - siblingsSize
+	if newLimit < 1 {
+		// We have no hope of respecting the limit, but let's do our best
+		// and split up the biggest child completely
+		newLimit = 1
+	}
+	sv := splitVisitor{limit: newLimit}
+	bigChild.AcceptVisitor(&sv)
+
+	// Combine the split up child with all the rest of the children.
+	//
+	// Take all the children except the one split up.
+	var siblings []parser.CriteriaAST
+	for i, c := range n.Children {
+		if i == childID {
+			continue
+		}
+		siblings = append(siblings, c)
+	}
+	// Combine every element of the split up child with all the siblings.
+	var res []parser.CriteriaAST
+	for _, c := range sv.res {
+		res = append(res, &parser.Node{
+			Operation: parser.OperationAnd,
+			Children: append(
+				[]parser.CriteriaAST{c}, clone(siblings)...,
+			),
+		})
+	}
+
+	return res
+}
+
+func clone(tl []parser.CriteriaAST) []parser.CriteriaAST {
+	var res []parser.CriteriaAST
+	for _, n := range tl {
+		res = append(res, n.Clone())
+	}
+	return res
+}
+
+type countVisitor struct{ res int }
+
+func (v *countVisitor) VisitNode(n *parser.Node) {
+	for _, c := range n.Children {
+		c.AcceptVisitor(v)
+	}
+	v.res++
+}
+func (v *countVisitor) VisitLeaf(n *parser.Leaf) {
+	// Note that in case of l.IsRaw, this number will be imprecise, as
+	// there will be multiple operands in the same expression.
+	v.res += len(n.Args)
+}
+
+func countNodes(tree parser.CriteriaAST) int {
+	cv := countVisitor{}
+	tree.AcceptVisitor(&cv)
+	return cv.res
+}
+
 func splitRootOr(tree parser.CriteriaAST) []parser.CriteriaAST {
 	// Since Gmail filters are all applied when they match, we can reduce
 	// the size of a rule and make it more readable by splitting a single
diff --git a/pkg/parser/ast.go b/pkg/parser/ast.go
index 9d0cd65..5ae0864 100644
--- a/pkg/parser/ast.go
+++ b/pkg/parser/ast.go
@@ -81,6 +81,8 @@ type CriteriaAST interface {
 	IsLeaf() bool
 	// AcceptVisitor implements the visitor pattern.
 	AcceptVisitor(v Visitor)
+	// Clone returns a deep copy of the tree.
+	Clone() CriteriaAST
 }
 
 // Node is an AST node with children nodes. It can only be a logical operator.
@@ -109,6 +111,18 @@ func (n *Node) AcceptVisitor(v Visitor) {
 	v.VisitNode(n)
 }
 
+// Clone returns a deep copy of the tree.
+func (n *Node) Clone() CriteriaAST {
+	var children []CriteriaAST
+	for _, c := range n.Children {
+		children = append(children, c.Clone())
+	}
+	return &Node{
+		Operation: n.Operation,
+		Children:  children,
+	}
+}
+
 // Leaf is an AST node with no children.
 //
 // If the function has multiple arguments, they are grouped together with a
@@ -141,6 +155,16 @@ func (n *Leaf) AcceptVisitor(v Visitor) {
 	v.VisitLeaf(n)
 }
 
+// Clone returns a deep copy of the leaf node.
+func (n *Leaf) Clone() CriteriaAST {
+	return &Leaf{
+		Function: n.Function,
+		Grouping: n.Grouping,
+		Args:     n.Args,
+		IsRaw:    n.IsRaw,
+	}
+}
+
 // Visitor implements the visitor pattern for CriteriaAST.
 type Visitor interface {
 	VisitNode(n *Node)


Test patch:
diff --git a/pkg/filter/convert_test.go b/pkg/filter/convert_test.go
index e95bad4..fc39643 100644
--- a/pkg/filter/convert_test.go
+++ b/pkg/filter/convert_test.go
@@ -161,6 +161,121 @@ func TestQuoting(t *testing.T) {
 	assert.Equal(t, expected, got)
 }
 
+func TestSplitLeaf(t *testing.T) {
+	rule := parser.Rule{
+		Criteria: &parser.Leaf{
+			Function: parser.FunctionFrom,
+			Grouping: parser.OperationOr,
+			Args:     []string{"a", "b", "c"},
+		},
+		Actions: parser.Actions{Archive: true},
+	}
+	expected := Filters{
+		{
+			Criteria: Criteria{From: "{a b}"},
+			Action:   Actions{Archive: true},
+		},
+		{
+			Criteria: Criteria{From: "c"},
+			Action:   Actions{Archive: true},
+		},
+	}
+	got, err := FromRule(rule, 2)
+	assert.Nil(t, err)
+	assert.Equal(t, expected, got)
+}
+
+func TestSplitFail(t *testing.T) {
+	rule := parser.Rule{
+		Criteria: &parser.Node{
+			Operation: parser.OperationAnd,
+			Children: []parser.CriteriaAST{
+				&parser.Leaf{
+					Function: parser.FunctionFrom,
+					Grouping: parser.OperationAnd,
+					Args:     []string{"d", "e"},
+				},
+				&parser.Leaf{
+					Function: parser.FunctionList,
+					Grouping: parser.OperationAnd,
+					Args:     []string{"a", "b"},
+				},
+				&parser.Node{
+					Operation: parser.OperationNot,
+					Children: []parser.CriteriaAST{
+						&parser.Leaf{
+							Function: parser.FunctionTo,
+							Args:     []string{"e"},
+						},
+					},
+				},
+			},
+		},
+		Actions: parser.Actions{Archive: true},
+	}
+	expected := Filters{
+		{
+			Criteria: Criteria{
+				From:  "(d e)",
+				Query: "list:(a b) -to:e",
+			},
+			Action: Actions{Archive: true},
+		},
+	}
+	got, err := FromRule(rule, 3)
+	assert.Nil(t, err)
+	assert.Equal(t, expected, got)
+}
+
+func TestSplitComplex(t *testing.T) {
+	rule := parser.Rule{
+		Criteria: &parser.Node{
+			Operation: parser.OperationAnd,
+			Children: []parser.CriteriaAST{
+				&parser.Leaf{
+					Function: parser.FunctionFrom,
+					Grouping: parser.OperationOr,
+					Args:     []string{"d", "e"},
+				},
+				&parser.Leaf{
+					Function: parser.FunctionList,
+					Grouping: parser.OperationOr,
+					Args:     []string{"a", "b", "c"},
+				},
+				&parser.Node{
+					Operation: parser.OperationNot,
+					Children: []parser.CriteriaAST{
+						&parser.Leaf{
+							Function: parser.FunctionTo,
+							Args:     []string{"e"},
+						},
+					},
+				},
+			},
+		},
+		Actions: parser.Actions{Archive: true},
+	}
+	expected := Filters{
+		{
+			Criteria: Criteria{
+				From:  "{d e}",
+				Query: "list:{a b} -to:e",
+			},
+			Action: Actions{Archive: true},
+		},
+		{
+			Criteria: Criteria{
+				From:  "{d e}",
+				Query: "list:c -to:e",
+			},
+			Action: Actions{Archive: true},
+		},
+	}
+	got, err := FromRule(rule, 7)
+	assert.Nil(t, err)
+	assert.Equal(t, expected, got)
+}
+
 func TestSplitActions(t *testing.T) {
 	rules := []parser.Rule{
 		{
diff --git a/testdata/local.bigsplit.diff b/testdata/local.bigsplit.diff
new file mode 100644
index 0000000..7fb422a
--- /dev/null
+++ b/testdata/local.bigsplit.diff
@@ -0,0 +1,19 @@
+Filters:
+--- Current
++++ TO BE APPLIED
+@@ -1 +1,15 @@
++* Criteria:
++    query: list:{list40 list41 list42 list43 list44 list45 list46 list47 list48 list49 list50}
++  Actions:
++    archive
+ 
++* Criteria:
++    query: list:{list20 list21 list22 list23 list24 list25 list26 list27 list28 list29 list30 list31 list32 list33 list34 list35 list36 list37 list38 list39}
++  Actions:
++    archive
++
++* Criteria:
++    query: list:{list0 list1 list2 list3 list4 list5 list6 list7 list8 list9 list10 list11 list12 list13 list14 list15 list16 list17 list18 list19}
++  Actions:
++    archive
++
diff --git a/testdata/local.bigsplit.jsonnet b/testdata/local.bigsplit.jsonnet
new file mode 100644
index 0000000..5c6c060
--- /dev/null
+++ b/testdata/local.bigsplit.jsonnet
@@ -0,0 +1,78 @@
+local filters = {
+  me: {
+    or: [
+      { to: 'pippo@gmail.com' },
+      { to: 'pippo@hotmail.com' },
+    ],
+  },
+
+  notMe: {
+    not: self.me,
+  },
+
+  lists: {
+    or: [
+      { list: 'list1' },
+      { list: 'list2' },
+      { list: 'list3' },
+    ],
+  },
+
+  spam: {
+    or: [
+      { from: 'spammer1' },
+      { from: 'spammer2' },
+      { subject: 'spam mail' },
+      { to: 'pippo+spammy@gmail.com' },
+      { has: 'buy this thing' },
+      { has: 'very important!!!' },
+    ],
+  },
+};
+
+// The config
+{
+  version: 'v1alpha3',
+  rules: [
+    {
+      filter: {
+        and: [
+          filters.lists,
+          { not: filters.me },
+        ],
+      },
+      actions: {
+        labels: ['maillist', 'onemorelabel'],
+        archive: true,
+      },
+    },
+    {
+      filter: {
+        and: [
+          { to: 'myalias@gmail.com' },
+          filters.lists,
+        ],
+      },
+      actions: {
+        markImportant: true,
+      },
+    },
+    {
+      filter: filters.spam,
+      actions: {
+        delete: true,
+      },
+    },
+    {
+      filter: {
+        or: [
+          { list: 'list%i' % i }
+          for i in std.range(0, 50)
+        ],
+      },
+      actions: {
+        archive: true,
+      },
+    },
+  ],
+}