Re: Row pattern recognition

Hi Jian,

> I'd like to remove RPRElemCanExit() and RPRElemCanLoop() and compare
> the count with min and max directly.
...
> Similarly, I also want to remove RPRCountIncrement and RPRElemWithinMax.

I'd rather keep all four.

RPRElemCanLoop() and RPRCountIncrement() are not just names for a
comparison. A count saturates at RPR_COUNT_INF, which is the same
value as RPR_QUANTITY_INF, so a saturated count compares as
unbounded (README.rpr). RPRCountIncrement() is the one place that
saturates, and RPRElemCanLoop() checks RPRElemIsUnbounded() first,
so an unbounded quantifier keeps looping after the count has
saturated. (count >= elem->max) as the stop test gets exactly that
case wrong. It is only reached after 2^31 iterations, but spelling
the tests out at each call site would mean repeating the saturation
rule everywhere.

RPRElemCanExit() and RPRElemWithinMax() are simpler, but they pair
with the other two. "Loop" and "exit" are the two ways out of a
quantifier, and a test such as

if (RPRElemCanLoop(elem, count) && RPRElemCanExit(elem, count))

reads as "both are possible", which the expanded form does not.
RPRElemWithinMax() keeps the same unbounded check as
RPRElemCanLoop(), for the Asserts.

> Is there a reason the markers are preferable?

Yes, three.

First, the Pattern line already shows the pattern after the
optimizer has rewritten it, not as the user wrote it. For example,
PATTERN ((A B)+ A B (A B)+ A B) is shown as (a b){4,}, and
absorbability is computed on that rewritten form. So a separate
line would not bring the user's text back either.

Second, the absorbable regions are tied to positions in the
pattern, and there can be more than one. With alternation, each
branch is checked on its own:

PATTERN ((A B)+ | (C D)+)
Pattern: ((a~ b~)+# | (c~ d~)+#)

and the same subpattern can be absorbable in several branches:

PATTERN (A+ | (A+ B+) | (A+ C+))
Pattern: (a+# | a+# b+ | a+# c+)

A single "Absorbable Pattern: a+" line cannot say which branches
are absorbable, and a list such as "a+, a+, a+" cannot say which is
which. Making it say that brings the markers back in words.

Third, the markers are what lets the regression tests check the
analysis itself. computeAbsorbability() sets two flags per element:
"~" for an element inside a region and "#" for the point where
absorption is decided. If a "#" ended up on the wrong element, or
a "~" were missing from part of a region, the inline form would
show it in the expected output, while "Absorbable Pattern: (a b)+"
would look the same. EXPLAIN ANALYZE shows whether contexts were
absorbed, but not where the analysis put the flags.

I agree the markers are not obvious to someone who doesn't know the
absorption design. How about showing them only with VERBOSE, or
with a separate EXPLAIN option?

Best regards,
Henson