Re: Better locale-specific-character-class handling for regexps

On 08/23/2016 03:54 AM, Tom Lane wrote:
> ! That's still not quite enough, though, because of locale-dependent
> ! character classes such as [[:alpha:]]. In Unicode locales these classes
> ! may have thousands of entries that are above MAX_SIMPLE_CHR, and we
> ! certainly don't want to be searching large colormaprange arrays at runtime.
> ! Nor do we even want to spend the time to initialize cvec structures that
> ! exhaustively describe all of those characters. Our solution is to compute
> ! exact per-character colors at compile time only up to MAX_SIMPLE_CHR.
> ! For characters above that, we apply the <ctype.h> or <wctype.h> lookup
> ! functions at runtime for each locale-dependent character class used in the
> ! regex pattern, constructing a bitmap that describes which classes the
> ! runtime character belongs to. The per-character-range data structure
> ! mentioned above actually holds, for each range, a separate color entry
> ! for each possible combination of character class properties. That is,
> ! the color map for characters above MAX_SIMPLE_CHR is really a 2-D array,
> ! whose rows correspond to character ranges that are explicitly mentioned
> ! in the input, and whose columns correspond to sets of relevant locale
> ! character classes.

I think that last sentence should say "whose rows correspond to
character ranges that are explicitly mentioned in the *regex pattern*",
rather than "in the input".

An example would be very helpful here. I had to read through this many
times, until I understood it. I can easily come up with examples for
character classes, but not for "high" character-ranges. The best I could
come up with is to check if a characters belongs to some special group
of unicode characters, like U&'[\+01D100-\+01D1FF]' to check for musical
symbol characters. In practice, I guess you will only see single
characters in the colormaprange array, although we must of course cope
with ranges too.

> + /* this relies on WHITE being zero: */
> + memset(cm->locolormap, WHITE,
> + (MAX_SIMPLE_CHR - CHR_MIN + 1) * sizeof(color));
> +
> + memset(cm->classbits, 0, sizeof(cm->classbits));
> + cm->numcmranges = 0;
> + cm->cmranges = NULL;
> + cm->maxarrayrows = 4; /* arbitrary initial allocation */
> + cm->hiarrayrows = 1;
> + cm->hiarraycols = 1;
> + cm->hicolormap = (color *) MALLOC(cm->maxarrayrows * sizeof(color));
> + if (cm->hicolormap == NULL)
> + {
> + CERR(REG_ESPACE);
> + return;
> + }
> + /* initialize the "all other characters" row to WHITE */
> + cm->hicolormap[0] = WHITE;

Is the comment correct? I don't see why this wouldn't work with "WHITE
!= 0".

> ! /* Duplicate existing columns to the right, and increase ref counts */
> ! /* Must work downwards in the array because we realloc'd in place */
> ! for (r = cm->hiarrayrows - 1; r >= 0; r--)
> ! {
> ! color *oldrowptr = &newarray[r * cm->hiarraycols];
> ! color *newrowptr = &newarray[r * cm->hiarraycols * 2];
> ! color *newrowptr2 = newrowptr + cm->hiarraycols;
>
> ! for (c = 0; c < cm->hiarraycols; c++)
> ! {
> ! color co = oldrowptr[c];
> !
> ! newrowptr[c] = newrowptr2[c] = co;
> ! cm->cd[co].nuchrs++;
> ! }
> ! }

Perhaps "backwards" would be clearer than "downwards"? At least in my
mental model, index 0 is the top row of an array, so "downwards" means
0, 1, 2. I guess you meant downwards numerically, rather than visually,
but it took me a moment to process that.

+1 for this patch in general. Some regression test cases would be nice.

- Heikki