Re: Row pattern recognition

Hi hackers,

This is the third of the postings that follow the increment. It
covers 2014 through 2021 and changes nothing in them.

The eight fall in two groups. Three are about what the pattern
grammar accepts and what it says when it does not: 2014, 2019 and
2020. The other five are one subject seen at five points --
absorption and the pattern optimizations -- in what the matcher
keeps (2015), in what the planner may rewrite (2016), in how the
passes that rewrite it are written (2017), in what EXPLAIN prints
about the result (2018), and in what the comments claim about all of
it (2021).

2014 Point the RPR quantifier diagnostics at the offending token

A quantifier written as two operator tokens was reported by
concatenating them, spelling out a quantifier nobody typed: "A *? ?"
said invalid quantifier combination: "*??". What follows from
naming the offending token instead:

- the offender is named and the cursor put on it, the way the "*",
"+" and range rules already do. A first token that spells no
quantifier at all is itself the offender, so "A ?+ ?" and
"A ?+ *" agree on "?+";

- the lexer glues a trailing alternation operator onto a
quantifier token, so rpr_invalid_quantifier_token() drops one
bar before quoting and "A **|B" and "A ** |B" both report "**".
With another bar left over there is no quantifier to uncover, so
"A ||B" and "A *||B" are quoted whole;

- the token an offender follows is quoted as typed, bar and all.
"A *| ?" reports

ERROR: invalid token "?" after "*|" quantifier

and not after a "*", because "A* ?" is a pattern the grammar
takes: stripping there would describe a pair that is not an
error;

- a range quantifier had one message for both bounds, so a bad
maximum was reported as the minimum's fault. The bounds are
checked one at a time now, each with the message its
single-bound rule already uses, so A{0} puts the cursor on the 0
and A{0,0} on the maximum;

- a dangling alternation operator pointed at the start of the
pattern, where "A B*|" blames the element it hangs off now;

- the hints listed *?, +? and ?? and then offered "their reluctant
versions", which reads as sanctioning "*??" -- a spelling these
very errors reject. They list the plain quantifiers now and say
a "?" may follow each one.

2015 Stop RPR absorption at a reluctant group's BEGIN

Absorption cannot apply under a reluctant quantifier, and it was
applying. isUnboundedStart() tested the quantifier it was handed
rather than the one that governs the subtree, so the greedy A+ in
PATTERN ((A+ B)+? C) still became a comparison point. The group's
quantifier sits on its BEGIN as well as its END, so returning there
lets one element answer for the whole subtree.

This only withholds flags, so the matcher keeps contexts it used to
discard and never the reverse: nothing a query returns changes, only
the work done to return it. The new rpr_explain pair has the same
body, DEFINE and rows -- the greedy (A+ B)+ C reports the marker on
a+ and a nonzero absorbed count, the reluctant (A+ B)+? C twin
reports neither.

2016 Clear the RPR reluctant flag when min equals max

Reluctance decides nothing once min == max, so optimizeRPRPattern()
clears the flag. The matcher reads it only where the quantifier
still has a choice, and min == max leaves none, so nothing there
changes; what changes is how much the planner can rewrite.
rprPatternEqual() compares reluctance, so a reluctant node was
unequal to its greedy twin and the rewrites that go by equality
declined it. (A{2}? | A{2}) deduplicates to A{2} now, and
(A+ B){2}? is marked absorbable. Each ends up with the plan its
greedy twin already had.

2017 Rewrite RPR pattern list optimizations to compact lists in place

- The five passes that only ever drop elements edit the list they
were handed instead of building a second one. Jian's patch did
that with an insert and a delete per element, and both memmove
the tail of the elements array, so dropping k of n elements
moves the tail k times. This walks the children with a read
cursor and a write cursor and truncates once at the end: the
write cursor never passes the read cursor, and list_truncate()
only lowers the length, moving no cells at all.

- The passes still hand the list back and are marked pg_nodiscard,
since dropping the result loses a pass silently -- the pattern
still matches, only less well.

- Folding a copy away leaves identical GROUPs adjacent with
nothing having put them there, so mergeConsecutiveGroups gets a
second look after mergeGroupPrefixSuffix. (A B)+ A B (A B)+ A B
had been left as (A B){2,} (A B){2,}, and three groups with two
copies between them left three pieces where one belongs. Only
the pattern changes, both forms carrying the same iteration
totals; the gain is in the NFA, where 11 peak states and 5985
total drop to 4 and 2996 on 2000 rows.

- Quantifier arithmetic goes through pg_add_s32_overflow() and
pg_mul_s32_overflow() in place of the subtraction-form guards it
had, with RPR_QUANTITY_INF treated as unbounded rather than as a
count. Without the product check ((A{46341,}){46341,}) wraps to
a negative minimum and walks past the infinity gate. An
overflow declines the rewrite rather than raising an error no
query can reach.

Checked over a 122-shape battery covering every pass. All but the
five the new pass collects deparse as they did before, and those
five were checked for match equivalence over every A and B string of
length 1 through 12. rpr_explain gains four cases, each of which
fails without the second merge.

2018 Use # and ~ for the absorption markers and document EXPLAIN's
RPR output

A pattern variable is printed through quote_identifier(), so the
Pattern line can already contain a double quote -- which was also
one of the two absorption markers. A variable named "select" under
a greedy unbounded quantifier printed as "select"+", where the
marker reads as the start of another quoted name. # and ~ cannot
appear in a bare name, so the marker always lands outside the
quotes. The expected output had no quoted name carrying a marker at
all, so two cases are added.

The plan chapter presented these markers as opportunities the
planner might still take, where they record an analysis already
made. That is corrected, along with the navigation lines and the
counters ANALYZE adds, which it said nothing about.

2019 Reject PERMUTE and keep a pattern variable of that name quoted

PERMUTE (A, B) is not distinguishable from a pattern variable named
permute followed by a group, and without the keyword that is how it
parses -- an undefined variable defaults to TRUE, so the standard
spelling was accepted with a meaning the standard does not give it.
A query written that way today would change its answer on the day
PERMUTE is implemented. So the keyword and a rule that rejects it
go in now, in the parser, and the spelling is diagnosed for what it
is.

That makes permute ambiguous in one position: unquoted and followed
by "(", it is read as the unsupported syntax. quote_identifier()
leaves an unreserved keyword bare, so a pattern variable of that
name would deparse into text the parser rejects;
quote_pattern_variable() quotes it, and the rewriter and the EXPLAIN
printer both use it. A DEFINE entry needs none of that, a name
there always being followed by AS, so the same variable may print
bare in DEFINE and quoted in PATTERN.

2020 Raise the RPR nesting depth limit to the last representable
depth

RPR_DEPTH_MAX was PG_UINT8_MAX - 1, one short of what RPRDepth
holds, so 253 was accepted where 254 fits. It is PG_UINT8_MAX now:
the accepted maximum is 254 and the first rejected depth 255, where
the type runs out. A pattern at the new maximum compiles and
matches, so the top value is exercised rather than reserved.

The boundary tests had inlined two PATTERN literals of about 2000
characters. They are built from repeat('(', N) and
repeat('){3,7}?', N) under \set ECHO none instead, the way the
element-count boundary test in the same file already is.

2021 Refresh stale RPR comments and drop three duplicated blocks

The bulk of the deletion is a design overview at the top of
execRPR.c that repeated README.rpr and the struct headers, plus an
appendix listing functions by name. Most of what is corrected
describes the four patches above:

- the rpr.c helpers did not say which three return a new list and
which four edit cells in place, though a caller must always
assign the return value;

- the absorption eligibility list omitted that no DEFINE variable
may depend on match_start, and the GROUP merge conditions
omitted the fixed-length body;

- the absorption flag enumerations omitted a group's BEGIN, and
the ABSORBABLE_BRANCH description claimed the flag covers the
unbounded start's scope, which is neither what the code marks
nor all of it;

- several worked examples used patterns Phase 1 rewrites into
something else, so they never reach the case they illustrate.

Best regards,
Henson