Convert regex engine's subre tree from binary to N-ary style.

Instead of having left and right child links in subre structs,
have a single child link plus a sibling link.  Multiple children
of a tree node are now reached by chasing the sibling chain.

The beneficiary of this is alternation tree nodes.  A regular
expression with N (>1) branches is now represented by one alternation
node with N children, rather than a tree that includes N alternation
nodes as well as N children.  While the old representation didn't
really cost anything extra at execution time, it was pretty horrid
for compilation purposes, because each of the alternation nodes had
its own NFA, which we were too stupid not to separately optimize.
(To make matters worse, all of those NFAs described the entire
alternation pattern, not just the portion of it that one might
expect from the tree structure.)

We continue to require concatenation nodes to have exactly two
children.  This data structure is now prepared to support more,
but the executor's logic would need some careful redesign, and
it's not clear that a lot of benefit could be had.

This is part of a patch series that in total reduces the regex engine's
runtime by about a factor of four on a large corpus of real-world regexes.

Patch by me, reviewed by Joel Jacobson

Discussion: https://postgr.es/m/[email protected]

1 files changed, 11 insertions, 9 deletions

diff --git a/src/include/regex/regguts.h b/src/include/regex/regguts.h
index 82e761bfe57..90ee16957ac 100644
--- a/src/include/regex/regguts.h
+++ b/src/include/regex/regguts.h
@@ -423,15 +423,17 @@ struct cnfa
  *		'='  plain regex without interesting substructure (implemented as DFA)
  *		'b'  back-reference (has no substructure either)
  *		'('  capture node: captures the match of its single child
- *		'.'  concatenation: matches a match for left, then a match for right
- *		'|'  alternation: matches a match for left or a match for right
+ *		'.'  concatenation: matches a match for first child, then second child
+ *		'|'  alternation: matches a match for any of its children
  *		'*'  iteration: matches some number of matches of its single child
  *
- * Note: the right child of an alternation must be another alternation or
- * NULL; hence, an N-way branch requires N alternation nodes, not N-1 as you
- * might expect.  This could stand to be changed.  Actually I'd rather see
- * a single alternation node with N children, but that will take revising
- * the representation of struct subre.
+ * An alternation node can have any number of children (but at least two),
+ * linked through their sibling fields.
+ *
+ * A concatenation node must have exactly two children.  It might be useful
+ * to support more, but that would complicate the executor.  Note that it is
+ * the first child's greediness that determines the node's preference for
+ * where to split a match.
  *
  * Note: when a backref is directly quantified, we stick the min/max counts
  * into the backref rather than plastering an iteration node on top.  This is
@@ -460,8 +462,8 @@ struct subre
 								 * LATYPE code for lookaround constraint */
 	short		min;			/* min repetitions for iteration or backref */
 	short		max;			/* max repetitions for iteration or backref */
-	struct subre *left;			/* left child, if any (also freelist chain) */
-	struct subre *right;		/* right child, if any */
+	struct subre *child;		/* first child, if any (also freelist chain) */
+	struct subre *sibling;		/* next child of same parent, if any */
 	struct state *begin;		/* outarcs from here... */
 	struct state *end;			/* ...ending in inarcs here */
 	struct cnfa cnfa;			/* compacted NFA, if any */