On 12/12/19 12:50 AM, Bruno Haible wrote:
Several programming languages have range types:
Pascal is where I first saw them.
I would distinguish the range type [0 .. PTRDIFF_MAX] (which is an abstract
concept) from the actual implementation (through the typedef). It could
be represented by a signed type or an unsigned type; either is fine.
Part of the motivation for this change is that unsigned types are not
"fine": they can't be checked for overflow via -fsanitize=undefined, and
they are not optimized as well for index calculations and the like due
to their wraparound overflow semantics.
Also, where would we put these new typedefs? dfa.h doesn't seem like the
right place.
That's up to you. It could well be a separate .h file that is a module of
its own (like verify.h and intprops.h are).
For now I was more conservative installed the attached, which limits the
scope of the new type (which I dubbed "idx_t", by analogy from Idx in
the regex code) to dfa.c. If we want to make this type visible we have
more work to do, including publishing its maximum value (IDX_MAX in
dfa.c), and making it easy to printf (I used "%td" in dfa.c, which is
quite convenient but it assumes idx_t is ptrdiff_t).
From my use of idx_t in dfa.c I'm not entirely sold on the distinction
between it and ptrdiff_t. The type is not separate from ptrdiff_t; it
means "ptrdiff_t but nonnegative" and the code relies on that. There
were iffy places where it kinda doesn't matter whether one uses
ptrdiff_t or idx_t and where I expect other developers won't bother
about the difference (as no tools check for it).
>From 73de34d3b440d5d3d9786b954cedab96dbbdfecf Mon Sep 17 00:00:00 2001
From: Paul Eggert <egg...@cs.ucla.edu>
Date: Thu, 12 Dec 2019 14:11:06 -0800
Subject: [PATCH] dfa: prefer ptrdiff_t for API, too
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
Also, use ‘idx_t’ for ptrdiff_t values that must be nonnegative,
but do this only for internal use for now.
* NEWS: Mention the API change.
* lib/dfa.c (idx_t, IDX_MAX): New type and max value, for internal
use for now. Use them instead of ptrdiff_t and PTRDIFF_MAX for
values known to be nonnegative.
(dfaparse, dfaexec_mb, dfaexec_sb, dfaexec_noop, dfaexec):
Prefer idx_t or ptrdiff_t to size_t for API.
* lib/dfa.h (dfaparse, dfacomp, dfaexec):
Prefer ptrdiff_t to size_t for API.
---
ChangeLog | 12 +++
NEWS | 2 +
lib/dfa.c | 250 ++++++++++++++++++++++++++++--------------------------
lib/dfa.h | 6 +-
4 files changed, 145 insertions(+), 125 deletions(-)
diff --git a/ChangeLog b/ChangeLog
index a22fa7229..aa25cfde0 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,17 @@
2019-12-12 Paul Eggert <egg...@cs.ucla.edu>
+ dfa: prefer ptrdiff_t for API, too
+ Also, use ‘idx_t’ for ptrdiff_t values that must be nonnegative,
+ but do this only for internal use for now.
+ * NEWS: Mention the API change.
+ * lib/dfa.c (idx_t, IDX_MAX): New type and max value, for internal
+ use for now. Use them instead of ptrdiff_t and PTRDIFF_MAX for
+ values known to be nonnegative.
+ (dfaparse, dfaexec_mb, dfaexec_sb, dfaexec_noop, dfaexec):
+ Prefer idx_t or ptrdiff_t to size_t for API.
+ * lib/dfa.h (dfaparse, dfacomp, dfaexec):
+ Prefer ptrdiff_t to size_t for API.
+
stdalign: port to xlclang 16.01
Problem reportd by Bruno Haible in:
https://lists.gnu.org/r/bug-gnulib/2019-12/msg00064.html
diff --git a/NEWS b/NEWS
index b73c9088a..b3a1fd630 100644
--- a/NEWS
+++ b/NEWS
@@ -58,6 +58,8 @@ User visible incompatible changes
Date Modules Changes
+2019-12-12 dfa Its API now uses ptrdiff_t instead of size_t.
+
2019-12-11 dfa To call dfamust, one must now call dfaparse
without yet calling dfacomp. This fixes a bug
introduced on 2018-10-22 that broke dfamust.
diff --git a/lib/dfa.c b/lib/dfa.c
index 26158d16f..8c88c9d36 100644
--- a/lib/dfa.c
+++ b/lib/dfa.c
@@ -33,6 +33,12 @@
#include <string.h>
#include <locale.h>
+/* Another name for ptrdiff_t, for sizes of objects and nonnegative
+ indexes into objects. It is signed to help catch integer overflow.
+ It has its own name because it is for nonnegative values only. */
+typedef ptrdiff_t idx_t;
+static idx_t const IDX_MAX = PTRDIFF_MAX;
+
static bool
streq (char const *a, char const *b)
{
@@ -214,7 +220,7 @@ enum
codes are returned by the lexical analyzer. */
typedef ptrdiff_t token;
-static ptrdiff_t const TOKEN_MAX = PTRDIFF_MAX;
+static token const TOKEN_MAX = PTRDIFF_MAX;
/* States are indexed by state_num values. These are normally
nonnegative but -1 is used as a special value. */
@@ -325,7 +331,7 @@ enum
a constraint. */
typedef struct
{
- ptrdiff_t index; /* Index into the parse array. */
+ idx_t index; /* Index into the parse array. */
unsigned int constraint; /* Constraint for matching this position. */
} position;
@@ -333,8 +339,8 @@ typedef struct
typedef struct
{
position *elems; /* Elements of this position set. */
- ptrdiff_t nelem; /* Number of elements in this set. */
- ptrdiff_t alloc; /* Number of elements allocated in ELEMS. */
+ idx_t nelem; /* Number of elements in this set. */
+ idx_t alloc; /* Number of elements allocated in ELEMS. */
} position_set;
/* A state of the dfa consists of a set of positions, some flags,
@@ -366,8 +372,8 @@ struct mb_char_classes
ptrdiff_t cset;
bool invert;
wchar_t *chars; /* Normal characters. */
- ptrdiff_t nchars;
- ptrdiff_t nchars_alloc;
+ idx_t nchars;
+ idx_t nchars_alloc;
};
struct regex_syntax
@@ -407,9 +413,9 @@ struct regex_syntax
struct lexer_state
{
char const *ptr; /* Pointer to next input character. */
- ptrdiff_t left; /* Number of characters remaining. */
+ idx_t left; /* Number of characters remaining. */
token lasttok; /* Previous token returned; initially END. */
- ptrdiff_t parens; /* Count of outstanding left parens. */
+ idx_t parens; /* Count of outstanding left parens. */
int minrep, maxrep; /* Repeat counts for {m,n}. */
/* Wide character representation of the current multibyte character,
@@ -432,7 +438,7 @@ struct lexer_state
struct parser_state
{
token tok; /* Lookahead token. */
- ptrdiff_t depth; /* Current depth of a hypothetical stack
+ idx_t depth; /* Current depth of a hypothetical stack
holding deferred productions. This is
used to determine the depth that will be
required of the real stack later on in
@@ -447,8 +453,8 @@ struct dfa
/* Fields filled by the scanner. */
charclass *charclasses; /* Array of character sets for CSET tokens. */
- ptrdiff_t cindex; /* Index for adding new charclasses. */
- ptrdiff_t calloc; /* Number of charclasses allocated. */
+ idx_t cindex; /* Index for adding new charclasses. */
+ idx_t calloc; /* Number of charclasses allocated. */
ptrdiff_t canychar; /* Index of anychar class, or -1. */
/* Scanner state */
@@ -459,13 +465,13 @@ struct dfa
/* Fields filled by the parser. */
token *tokens; /* Postfix parse array. */
- ptrdiff_t tindex; /* Index for adding new tokens. */
- ptrdiff_t talloc; /* Number of tokens currently allocated. */
- ptrdiff_t depth; /* Depth required of an evaluation stack
+ idx_t tindex; /* Index for adding new tokens. */
+ idx_t talloc; /* Number of tokens currently allocated. */
+ idx_t depth; /* Depth required of an evaluation stack
used for depth-first traversal of the
parse tree. */
- ptrdiff_t nleaves; /* Number of leaves on the parse tree. */
- ptrdiff_t nregexps; /* Count of parallel regexps being built
+ idx_t nleaves; /* Number of leaves on the parse tree. */
+ idx_t nregexps; /* Count of parallel regexps being built
with dfaparse. */
bool fast; /* The DFA is fast. */
token utf8_anychar_classes[5]; /* To lower ANYCHAR in UTF-8 locales. */
@@ -495,7 +501,7 @@ struct dfa
/* Fields filled by the state builder. */
dfa_state *states; /* States of the dfa. */
state_num sindex; /* Index for adding new states. */
- ptrdiff_t salloc; /* Number of states currently allocated. */
+ idx_t salloc; /* Number of states currently allocated. */
/* Fields filled by the parse tree->NFA conversion. */
position_set *follows; /* Array of follow sets, indexed by position
@@ -565,7 +571,7 @@ struct dfa
/* dfaexec implementation. */
char *(*dfaexec) (struct dfa *, char const *, char *,
- bool, size_t *, bool *);
+ bool, ptrdiff_t *, bool *);
/* The locale is simple, like the C locale. These locales can be
processed more efficiently, as they are single-byte, their native
@@ -791,10 +797,10 @@ emptyset (charclass const *s)
{ free (A); A = xpalloc (NULL, &AITEMS, ...); }. */
static void *
-xpalloc (void *pa, ptrdiff_t *nitems, ptrdiff_t nitems_incr_min,
- ptrdiff_t nitems_max, ptrdiff_t item_size)
+xpalloc (void *pa, idx_t *nitems, idx_t nitems_incr_min,
+ ptrdiff_t nitems_max, idx_t item_size)
{
- ptrdiff_t n0 = *nitems;
+ idx_t n0 = *nitems;
/* The approximate size to use for initial small allocation
requests. This is the largest "small" request for the GNU C
@@ -806,15 +812,15 @@ xpalloc (void *pa, ptrdiff_t *nitems, ptrdiff_t nitems_incr_min,
Adjust the growth according to three constraints: NITEMS_INCR_MIN,
NITEMS_MAX, and what the C language can represent safely. */
- ptrdiff_t n, nbytes;
+ idx_t n, nbytes;
if (INT_ADD_WRAPV (n0, n0 >> 1, &n))
- n = PTRDIFF_MAX;
+ n = IDX_MAX;
if (0 <= nitems_max && nitems_max < n)
n = nitems_max;
- ptrdiff_t adjusted_nbytes
+ idx_t adjusted_nbytes
= ((INT_MULTIPLY_WRAPV (n, item_size, &nbytes) || SIZE_MAX < nbytes)
- ? MIN (PTRDIFF_MAX, SIZE_MAX)
+ ? MIN (IDX_MAX, SIZE_MAX)
: nbytes < DEFAULT_MXFAST ? DEFAULT_MXFAST : 0);
if (adjusted_nbytes)
{
@@ -844,8 +850,8 @@ xpalloc (void *pa, ptrdiff_t *nitems, ptrdiff_t nitems_incr_min,
ITEM_SIZE is the size of one item; it must be positive.
Avoid O(N**2) behavior on arrays growing linearly. */
static void *
-maybe_realloc (void *pa, ptrdiff_t i, ptrdiff_t *nitems,
- ptrdiff_t nitems_max, ptrdiff_t item_size)
+maybe_realloc (void *pa, idx_t i, idx_t *nitems,
+ ptrdiff_t nitems_max, idx_t item_size)
{
if (i < *nitems)
return pa;
@@ -853,10 +859,10 @@ maybe_realloc (void *pa, ptrdiff_t i, ptrdiff_t *nitems,
}
/* In DFA D, find the index of charclass S, or allocate a new one. */
-static ptrdiff_t
+static idx_t
charclass_index (struct dfa *d, charclass *s)
{
- ptrdiff_t i;
+ idx_t i;
for (i = 0; i < d->cindex; ++i)
if (equal (s, &d->charclasses[i]))
@@ -1239,7 +1245,7 @@ parse_bracket_exp (struct dfa *dfa)
struct lexptr
{
char const *ptr;
- ptrdiff_t left;
+ idx_t left;
};
static void
@@ -1659,7 +1665,7 @@ addtok (struct dfa *dfa, token t)
/* Extract wide characters into alternations for better performance.
This does not require UTF-8. */
- for (ptrdiff_t i = 0; i < dfa->lex.brack.nchars; i++)
+ for (idx_t i = 0; i < dfa->lex.brack.nchars; i++)
{
addtok_wc (dfa, dfa->lex.brack.chars[i]);
if (need_or)
@@ -1867,8 +1873,8 @@ atom (struct dfa *dfa)
}
/* Return the number of tokens in the given subexpression. */
-static ptrdiff_t _GL_ATTRIBUTE_PURE
-nsubtoks (struct dfa const *dfa, ptrdiff_t tindex)
+static idx_t _GL_ATTRIBUTE_PURE
+nsubtoks (struct dfa const *dfa, idx_t tindex)
{
switch (dfa->tokens[tindex - 1])
{
@@ -1881,7 +1887,7 @@ nsubtoks (struct dfa const *dfa, ptrdiff_t tindex)
case CAT:
case OR:
{
- ptrdiff_t ntoks1 = nsubtoks (dfa, tindex - 1);
+ idx_t ntoks1 = nsubtoks (dfa, tindex - 1);
return 1 + ntoks1 + nsubtoks (dfa, tindex - 1 - ntoks1);
}
}
@@ -1889,14 +1895,14 @@ nsubtoks (struct dfa const *dfa, ptrdiff_t tindex)
/* Copy the given subexpression to the top of the tree. */
static void
-copytoks (struct dfa *dfa, ptrdiff_t tindex, ptrdiff_t ntokens)
+copytoks (struct dfa *dfa, idx_t tindex, idx_t ntokens)
{
if (dfa->localeinfo.multibyte)
- for (ptrdiff_t i = 0; i < ntokens; ++i)
+ for (idx_t i = 0; i < ntokens; i++)
addtok_mb (dfa, dfa->tokens[tindex + i],
dfa->multibyte_prop[tindex + i]);
else
- for (ptrdiff_t i = 0; i < ntokens; ++i)
+ for (idx_t i = 0; i < ntokens; i++)
addtok_mb (dfa, dfa->tokens[tindex + i], 3);
}
@@ -1908,8 +1914,8 @@ closure (struct dfa *dfa)
|| dfa->parse.tok == PLUS || dfa->parse.tok == REPMN)
if (dfa->parse.tok == REPMN && (dfa->lex.minrep || dfa->lex.maxrep))
{
- ptrdiff_t ntokens = nsubtoks (dfa, dfa->tindex);
- ptrdiff_t tindex = dfa->tindex - ntokens;
+ idx_t ntokens = nsubtoks (dfa, dfa->tindex);
+ idx_t tindex = dfa->tindex - ntokens;
if (dfa->lex.maxrep < 0)
addtok (dfa, PLUS);
if (dfa->lex.minrep == 0)
@@ -1968,7 +1974,7 @@ regexp (struct dfa *dfa)
/* Parse a string S of length LEN into D. S can include NUL characters.
This is the main entry point for the parser. */
void
-dfaparse (char const *s, size_t len, struct dfa *d)
+dfaparse (char const *s, idx_t len, struct dfa *d)
{
d->lex.ptr = s;
d->lex.left = len;
@@ -2016,7 +2022,7 @@ copy (position_set const *src, position_set *dst)
}
static void
-alloc_position_set (position_set *s, ptrdiff_t size)
+alloc_position_set (position_set *s, idx_t size)
{
s->elems = xnmalloc (size, sizeof *s->elems);
s->alloc = size;
@@ -2030,11 +2036,11 @@ alloc_position_set (position_set *s, ptrdiff_t size)
static void
insert (position p, position_set *s)
{
- ptrdiff_t count = s->nelem;
- ptrdiff_t lo = 0, hi = count;
+ idx_t count = s->nelem;
+ idx_t lo = 0, hi = count;
while (lo < hi)
{
- ptrdiff_t mid = (lo + hi) >> 1;
+ idx_t mid = (lo + hi) >> 1;
if (s->elems[mid].index < p.index)
lo = mid + 1;
else if (s->elems[mid].index == p.index)
@@ -2047,7 +2053,7 @@ insert (position p, position_set *s)
}
s->elems = maybe_realloc (s->elems, count, &s->alloc, -1, sizeof *s->elems);
- for (ptrdiff_t i = count; i > lo; i--)
+ for (idx_t i = count; i > lo; i--)
s->elems[i] = s->elems[i - 1];
s->elems[lo] = p;
++s->nelem;
@@ -2056,7 +2062,7 @@ insert (position p, position_set *s)
static void
append (position p, position_set *s)
{
- ptrdiff_t count = s->nelem;
+ idx_t count = s->nelem;
s->elems = maybe_realloc (s->elems, count, &s->alloc, -1, sizeof *s->elems);
s->elems[s->nelem++] = p;
}
@@ -2068,7 +2074,7 @@ static void
merge_constrained (position_set const *s1, position_set const *s2,
unsigned int c2, position_set *m)
{
- ptrdiff_t i = 0, j = 0;
+ idx_t i = 0, j = 0;
if (m->alloc - s1->nelem < s2->nelem)
{
@@ -2112,7 +2118,7 @@ merge2 (position_set *dst, position_set const *src, position_set *m)
{
if (src->nelem < 4)
{
- for (ptrdiff_t i = 0; i < src->nelem; ++i)
+ for (idx_t i = 0; i < src->nelem; i++)
insert (src->elems[i], dst);
}
else
@@ -2125,19 +2131,19 @@ merge2 (position_set *dst, position_set const *src, position_set *m)
/* Delete a position from a set. Return the nonzero constraint of the
deleted position, or zero if there was no such position. */
static unsigned int
-delete (ptrdiff_t del, position_set *s)
+delete (idx_t del, position_set *s)
{
- ptrdiff_t count = s->nelem;
- ptrdiff_t lo = 0, hi = count;
+ idx_t count = s->nelem;
+ idx_t lo = 0, hi = count;
while (lo < hi)
{
- ptrdiff_t mid = (lo + hi) >> 1;
+ idx_t mid = (lo + hi) >> 1;
if (s->elems[mid].index < del)
lo = mid + 1;
else if (s->elems[mid].index == del)
{
unsigned int c = s->elems[mid].constraint;
- ptrdiff_t i;
+ idx_t i;
for (i = mid; i + 1 < count; i++)
s->elems[i] = s->elems[i + 1];
s->nelem = i;
@@ -2151,7 +2157,7 @@ delete (ptrdiff_t del, position_set *s)
/* Replace a position with the followed set. */
static void
-replace (position_set *dst, ptrdiff_t del, position_set *add,
+replace (position_set *dst, idx_t del, position_set *add,
unsigned int constraint, position_set *tmp)
{
unsigned int c = delete (del, dst) & constraint;
@@ -2261,7 +2267,7 @@ epsclosure (struct dfa const *d)
{
position_set tmp;
alloc_position_set (&tmp, d->nleaves);
- for (ptrdiff_t i = 0; i < d->tindex; ++i)
+ for (idx_t i = 0; i < d->tindex; i++)
if (d->follows[i].nelem > 0 && d->tokens[i] >= NOTCHAR
&& d->tokens[i] != BACKREF && d->tokens[i] != ANYCHAR
&& d->tokens[i] != MBCSET && d->tokens[i] < CSET)
@@ -2294,7 +2300,7 @@ epsclosure (struct dfa const *d)
delete (i, &d->follows[i]);
- for (ptrdiff_t j = 0; j < d->tindex; j++)
+ for (idx_t j = 0; j < d->tindex; j++)
if (i != j && d->follows[j].nelem > 0)
replace (&d->follows[j], i, &d->follows[i], constraint, &tmp);
}
@@ -2333,7 +2339,7 @@ state_separate_contexts (struct dfa *d, position_set const *s)
{
int separate_contexts = 0;
- for (ptrdiff_t j = 0; j < s->nelem; j++)
+ for (idx_t j = 0; j < s->nelem; j++)
separate_contexts |= d->separates[s->elems[j].index];
return separate_contexts;
@@ -2360,17 +2366,17 @@ enum
};
static void
-merge_nfa_state (struct dfa *d, ptrdiff_t tindex, char *flags,
+merge_nfa_state (struct dfa *d, idx_t tindex, char *flags,
position_set *merged)
{
position_set *follows = d->follows;
- ptrdiff_t nelem = 0;
+ idx_t nelem = 0;
d->constraints[tindex] = 0;
- for (ptrdiff_t i = 0; i < follows[tindex].nelem; i++)
+ for (idx_t i = 0; i < follows[tindex].nelem; i++)
{
- ptrdiff_t sindex = follows[tindex].elems[i].index;
+ idx_t sindex = follows[tindex].elems[i].index;
/* Skip the node as pruned in future. */
unsigned int iconstraint = follows[tindex].elems[i].constraint;
@@ -2385,11 +2391,11 @@ merge_nfa_state (struct dfa *d, ptrdiff_t tindex, char *flags,
if (!(flags[sindex] & (OPT_LPAREN | OPT_RPAREN)))
{
- ptrdiff_t j;
+ idx_t j;
for (j = 0; j < nelem; j++)
{
- ptrdiff_t dindex = follows[tindex].elems[j].index;
+ idx_t dindex = follows[tindex].elems[j].index;
if (follows[tindex].elems[j].constraint != iconstraint)
continue;
@@ -2432,7 +2438,7 @@ compare (const void *a, const void *b)
static void
reorder_tokens (struct dfa *d)
{
- ptrdiff_t nleaves;
+ idx_t nleaves;
ptrdiff_t *map;
token *tokens;
position_set *follows;
@@ -2445,7 +2451,7 @@ reorder_tokens (struct dfa *d)
map[0] = nleaves++;
- for (ptrdiff_t i = 1; i < d->tindex; i++)
+ for (idx_t i = 1; i < d->tindex; i++)
map[i] = -1;
tokens = xnmalloc (d->nleaves, sizeof *tokens);
@@ -2457,7 +2463,7 @@ reorder_tokens (struct dfa *d)
else
multibyte_prop = NULL;
- for (ptrdiff_t i = 0; i < d->tindex; i++)
+ for (idx_t i = 0; i < d->tindex; i++)
{
if (map[i] == -1)
{
@@ -2474,7 +2480,7 @@ reorder_tokens (struct dfa *d)
if (multibyte_prop != NULL)
multibyte_prop[map[i]] = d->multibyte_prop[i];
- for (ptrdiff_t j = 0; j < d->follows[i].nelem; j++)
+ for (idx_t j = 0; j < d->follows[i].nelem; j++)
{
if (map[d->follows[i].elems[j].index] == -1)
map[d->follows[i].elems[j].index] = nleaves++;
@@ -2486,7 +2492,7 @@ reorder_tokens (struct dfa *d)
sizeof *d->follows[i].elems, compare);
}
- for (ptrdiff_t i = 0; i < nleaves; i++)
+ for (idx_t i = 0; i < nleaves; i++)
{
d->tokens[i] = tokens[i];
d->follows[i] = follows[i];
@@ -2515,9 +2521,9 @@ dfaoptimize (struct dfa *d)
flags = xmalloc (d->tindex * sizeof *flags);
memset (flags, 0, d->tindex * sizeof *flags);
- for (ptrdiff_t i = 0; i < d->tindex; i++)
+ for (idx_t i = 0; i < d->tindex; i++)
{
- for (ptrdiff_t j = 0; j < d->follows[i].nelem; j++)
+ for (idx_t j = 0; j < d->follows[i].nelem; j++)
{
if (d->follows[i].elems[j].index == i)
flags[d->follows[i].elems[j].index] |= OPT_REPEAT;
@@ -2537,7 +2543,7 @@ dfaoptimize (struct dfa *d)
d->constraints = xnmalloc (d->tindex, sizeof *d->constraints);
- for (ptrdiff_t i = 0; i < d->tindex; i++)
+ for (idx_t i = 0; i < d->tindex; i++)
if (flags[i] & OPT_QUEUED)
merge_nfa_state (d, i, flags, merged);
@@ -2617,8 +2623,8 @@ dfaanalyze (struct dfa *d, bool searchflag)
bool nullable;
/* Counts of firstpos and lastpos sets. */
- ptrdiff_t nfirstpos;
- ptrdiff_t nlastpos;
+ idx_t nfirstpos;
+ idx_t nlastpos;
} *stkalloc = xnmalloc (d->depth, sizeof *stkalloc), *stk = stkalloc;
position_set merged; /* Result of merging sets. */
@@ -2627,7 +2633,7 @@ dfaanalyze (struct dfa *d, bool searchflag)
#ifdef DEBUG
fprintf (stderr, "dfaanalyze:\n");
- for (ptrdiff_t i = 0; i < d->tindex; ++i)
+ for (idx_t i = 0; i < d->tindex; i++)
{
fprintf (stderr, " %td:", i);
prtok (d->tokens[i]);
@@ -2639,7 +2645,7 @@ dfaanalyze (struct dfa *d, bool searchflag)
alloc_position_set (&merged, d->nleaves);
d->follows = xcalloc (d->tindex, sizeof *d->follows);
- for (ptrdiff_t i = 0; i < d->tindex; ++i)
+ for (idx_t i = 0; i < d->tindex; i++)
{
switch (d->tokens[i])
{
@@ -2660,7 +2666,7 @@ dfaanalyze (struct dfa *d, bool searchflag)
tmp.elems = firstpos - stk[-1].nfirstpos;
tmp.nelem = stk[-1].nfirstpos;
position *p = lastpos - stk[-1].nlastpos;
- for (ptrdiff_t j = 0; j < stk[-1].nlastpos; j++)
+ for (idx_t j = 0; j < stk[-1].nlastpos; j++)
{
merge (&tmp, &d->follows[p[j].index], &merged);
copy (&merged, &d->follows[p[j].index]);
@@ -2680,7 +2686,7 @@ dfaanalyze (struct dfa *d, bool searchflag)
tmp.nelem = stk[-1].nfirstpos;
tmp.elems = firstpos - stk[-1].nfirstpos;
position *p = lastpos - stk[-1].nlastpos - stk[-2].nlastpos;
- for (ptrdiff_t j = 0; j < stk[-2].nlastpos; j++)
+ for (idx_t j = 0; j < stk[-2].nlastpos; j++)
{
merge (&tmp, &d->follows[p[j].index], &merged);
copy (&merged, &d->follows[p[j].index]);
@@ -2701,7 +2707,7 @@ dfaanalyze (struct dfa *d, bool searchflag)
else
{
position *p = lastpos - stk[-1].nlastpos - stk[-2].nlastpos;
- for (ptrdiff_t j = 0; j < stk[-1].nlastpos; j++)
+ for (idx_t j = 0; j < stk[-1].nlastpos; j++)
p[j] = p[j + stk[-2].nlastpos];
lastpos -= stk[-2].nlastpos;
stk[-2].nlastpos = stk[-1].nlastpos;
@@ -2750,13 +2756,13 @@ dfaanalyze (struct dfa *d, bool searchflag)
fprintf (stderr,
stk[-1].nullable ? " nullable: yes\n" : " nullable: no\n");
fprintf (stderr, " firstpos:");
- for (ptrdiff_t j = 0; j < stk[-1].nfirstpos; j++)
+ for (idx_t j = 0; j < stk[-1].nfirstpos; j++)
{
fprintf (stderr, " %td:", firstpos[j - stk[-1].nfirstpos].index);
prtok (d->tokens[firstpos[j - stk[-1].nfirstpos].index]);
}
fprintf (stderr, "\n lastpos:");
- for (ptrdiff_t j = 0; j < stk[-1].nlastpos; j++)
+ for (idx_t j = 0; j < stk[-1].nlastpos; j++)
{
fprintf (stderr, " %td:", lastpos[j - stk[-1].nlastpos].index);
prtok (d->tokens[lastpos[j - stk[-1].nlastpos].index]);
@@ -2772,7 +2778,7 @@ dfaanalyze (struct dfa *d, bool searchflag)
dfaoptimize (d);
#ifdef DEBUG
- for (ptrdiff_t i = 0; i < d->tindex; ++i)
+ for (idx_t i = 0; i < d->tindex; i++)
if (d->tokens[i] == BEG || d->tokens[i] < NOTCHAR
|| d->tokens[i] == BACKREF || d->tokens[i] == ANYCHAR
|| d->tokens[i] == MBCSET || d->tokens[i] >= CSET)
@@ -2780,7 +2786,7 @@ dfaanalyze (struct dfa *d, bool searchflag)
fprintf (stderr, "follows(%td:", i);
prtok (d->tokens[i]);
fprintf (stderr, "):");
- for (ptrdiff_t j = 0; j < d->follows[i].nelem; j++)
+ for (idx_t j = 0; j < d->follows[i].nelem; j++)
{
fprintf (stderr, " %td:", d->follows[i].elems[j].index);
prtok (d->tokens[d->follows[i].elems[j].index]);
@@ -2798,7 +2804,7 @@ dfaanalyze (struct dfa *d, bool searchflag)
d->separates = xnmalloc (d->tindex, sizeof *d->separates);
- for (ptrdiff_t i = 0; i < d->tindex; i++)
+ for (idx_t i = 0; i < d->tindex; i++)
{
d->separates[i] = 0;
@@ -2807,7 +2813,7 @@ dfaanalyze (struct dfa *d, bool searchflag)
if (prev_letter_dependent (d->constraints[i]))
d->separates[i] |= CTX_LETTER;
- for (ptrdiff_t j = 0; j < d->follows[i].nelem; j++)
+ for (idx_t j = 0; j < d->follows[i].nelem; j++)
{
if (prev_newline_dependent (d->follows[i].elems[j].constraint))
d->separates[i] |= CTX_NEWLINE;
@@ -2843,12 +2849,12 @@ realloc_trans_if_necessary (struct dfa *d)
if (oldalloc < d->sindex)
{
state_num **realtrans = d->trans ? d->trans - 2 : NULL;
- ptrdiff_t newalloc1 = realtrans ? d->tralloc + 2 : 0;
+ idx_t newalloc1 = realtrans ? d->tralloc + 2 : 0;
realtrans = xpalloc (realtrans, &newalloc1, d->sindex - oldalloc,
-1, sizeof *realtrans);
realtrans[0] = realtrans[1] = NULL;
d->trans = realtrans + 2;
- ptrdiff_t newalloc = d->tralloc = newalloc1 - 2;
+ idx_t newalloc = d->tralloc = newalloc1 - 2;
d->fails = xnrealloc (d->fails, newalloc, sizeof *d->fails);
d->success = xnrealloc (d->success, newalloc, sizeof *d->success);
d->newlines = xnrealloc (d->newlines, newalloc, sizeof *d->newlines);
@@ -2961,8 +2967,8 @@ build_state (state_num s, struct dfa *d, unsigned char uc)
/* Find the union of the follows of the positions of the group.
This is a hideously inefficient loop. Fix it someday. */
- for (ptrdiff_t j = 0; j < d->states[s].elems.nelem; j++)
- for (ptrdiff_t k = 0;
+ for (idx_t j = 0; j < d->states[s].elems.nelem; j++)
+ for (idx_t k = 0;
k < d->follows[d->states[s].elems.elems[j].index].nelem; ++k)
insert (d->follows[d->states[s].elems.elems[j].index].elems[k],
&follows);
@@ -2974,7 +2980,7 @@ build_state (state_num s, struct dfa *d, unsigned char uc)
charclass label;
fillset (&label);
- for (ptrdiff_t i = 0; i < follows.nelem; ++i)
+ for (idx_t i = 0; i < follows.nelem; i++)
{
charclass matches; /* Set of matching characters. */
position pos = follows.elems[i];
@@ -3095,7 +3101,7 @@ build_state (state_num s, struct dfa *d, unsigned char uc)
if (!mergeit)
{
mergeit = true;
- for (ptrdiff_t j = 0; mergeit && j < group.nelem; j++)
+ for (idx_t j = 0; mergeit && j < group.nelem; j++)
mergeit &= d->multibyte_prop[group.elems[j].index];
}
if (mergeit)
@@ -3346,7 +3352,7 @@ skip_remains_mb (struct dfa *d, unsigned char const *p,
static inline char *
dfaexec_main (struct dfa *d, char const *begin, char *end, bool allow_nl,
- size_t *count, bool multibyte)
+ ptrdiff_t *count, bool multibyte)
{
if (MAX_TRCOUNT <= d->sindex)
{
@@ -3404,7 +3410,7 @@ dfaexec_main (struct dfa *d, char const *begin, char *end, bool allow_nl,
alloc_position_set (&d->mb_follows, d->nleaves);
}
- ptrdiff_t nlcount = 0;
+ idx_t nlcount = 0;
for (;;)
{
state_num *t;
@@ -3529,14 +3535,14 @@ dfaexec_main (struct dfa *d, char const *begin, char *end, bool allow_nl,
static char *
dfaexec_mb (struct dfa *d, char const *begin, char *end,
- bool allow_nl, size_t *count, bool *backref)
+ bool allow_nl, ptrdiff_t *count, bool *backref)
{
return dfaexec_main (d, begin, end, allow_nl, count, true);
}
static char *
dfaexec_sb (struct dfa *d, char const *begin, char *end,
- bool allow_nl, size_t *count, bool *backref)
+ bool allow_nl, ptrdiff_t *count, bool *backref)
{
return dfaexec_main (d, begin, end, allow_nl, count, false);
}
@@ -3545,7 +3551,7 @@ dfaexec_sb (struct dfa *d, char const *begin, char *end,
any regexp that uses a construct not supported by this code. */
static char *
dfaexec_noop (struct dfa *d, char const *begin, char *end,
- bool allow_nl, size_t *count, bool *backref)
+ bool allow_nl, ptrdiff_t *count, bool *backref)
{
*backref = true;
return (char *) begin;
@@ -3557,7 +3563,7 @@ dfaexec_noop (struct dfa *d, char const *begin, char *end,
char *
dfaexec (struct dfa *d, char const *begin, char *end,
- bool allow_nl, size_t *count, bool *backref)
+ bool allow_nl, ptrdiff_t *count, bool *backref)
{
return d->dfaexec (d, begin, end, allow_nl, count, backref);
}
@@ -3594,7 +3600,7 @@ free_mbdata (struct dfa *d)
static bool _GL_ATTRIBUTE_PURE
dfa_supported (struct dfa const *d)
{
- for (ptrdiff_t i = 0; i < d->tindex; i++)
+ for (idx_t i = 0; i < d->tindex; i++)
{
switch (d->tokens[i])
{
@@ -3622,7 +3628,7 @@ maybe_disable_superset_dfa (struct dfa *d)
return;
bool have_backref = false;
- for (ptrdiff_t i = 0; i < d->tindex; ++i)
+ for (idx_t i = 0; i < d->tindex; i++)
{
switch (d->tokens[i])
{
@@ -3687,8 +3693,8 @@ dfassbuild (struct dfa *d)
bool have_achar = false;
bool have_nchar = false;
- ptrdiff_t j;
- for (ptrdiff_t i = j = 0; i < d->tindex; i++)
+ idx_t j;
+ for (idx_t i = j = 0; i < d->tindex; i++)
{
switch (d->tokens[i])
{
@@ -3741,7 +3747,7 @@ dfassbuild (struct dfa *d)
Then analyze D and build a matcher for it.
SEARCHFLAG says whether to build a searching or an exact matcher. */
void
-dfacomp (char const *s, size_t len, struct dfa *d, bool searchflag)
+dfacomp (char const *s, idx_t len, struct dfa *d, bool searchflag)
{
if (s != NULL)
dfaparse (s, len, d);
@@ -3778,7 +3784,7 @@ dfafree (struct dfa *d)
free (d->constraints);
free (d->separates);
- for (ptrdiff_t i = 0; i < d->sindex; ++i)
+ for (idx_t i = 0; i < d->sindex; i++)
{
free (d->states[i].elems.elems);
free (d->states[i].mbps.elems);
@@ -3787,14 +3793,14 @@ dfafree (struct dfa *d)
if (d->follows)
{
- for (ptrdiff_t i = 0; i < d->tindex; ++i)
+ for (idx_t i = 0; i < d->tindex; i++)
free (d->follows[i].elems);
free (d->follows);
}
if (d->trans)
{
- for (ptrdiff_t i = 0; i < d->tralloc; ++i)
+ for (idx_t i = 0; i < d->tralloc; i++)
{
free (d->trans[i]);
free (d->fails[i]);
@@ -3898,10 +3904,10 @@ dfafree (struct dfa *d)
static char *
icatalloc (char *old, char const *new)
{
- ptrdiff_t newsize = strlen (new);
+ idx_t newsize = strlen (new);
if (newsize == 0)
return old;
- ptrdiff_t oldsize = strlen (old);
+ idx_t oldsize = strlen (old);
char *result = xrealloc (old, oldsize + newsize + 1);
memcpy (result + oldsize, new, newsize + 1);
return result;
@@ -3915,12 +3921,12 @@ freelist (char **cpp)
}
static char **
-enlist (char **cpp, char *new, ptrdiff_t len)
+enlist (char **cpp, char *new, idx_t len)
{
new = memcpy (xmalloc (len + 1), new, len);
new[len] = '\0';
/* Is there already something in the list that's new (or longer)? */
- ptrdiff_t i;
+ idx_t i;
for (i = 0; cpp[i] != NULL; i++)
if (strstr (cpp[i], new) != NULL)
{
@@ -3928,7 +3934,7 @@ enlist (char **cpp, char *new, ptrdiff_t len)
return cpp;
}
/* Eliminate any obsoleted strings. */
- for (ptrdiff_t j = 0; cpp[j] != NULL; )
+ for (idx_t j = 0; cpp[j] != NULL; )
if (strstr (new, cpp[j]) == NULL)
++j;
else
@@ -3955,11 +3961,11 @@ comsubs (char *left, char const *right)
for (char *lcp = left; *lcp != '\0'; lcp++)
{
- ptrdiff_t len = 0;
+ idx_t len = 0;
char *rcp = strchr (right, *lcp);
while (rcp != NULL)
{
- ptrdiff_t i;
+ idx_t i;
for (i = 1; lcp[i] != '\0' && lcp[i] == rcp[i]; ++i)
continue;
if (i > len)
@@ -3987,9 +3993,9 @@ inboth (char **left, char **right)
{
char **both = xzalloc (sizeof *both);
- for (ptrdiff_t lnum = 0; left[lnum] != NULL; lnum++)
+ for (idx_t lnum = 0; left[lnum] != NULL; lnum++)
{
- for (ptrdiff_t rnum = 0; right[rnum] != NULL; rnum++)
+ for (idx_t rnum = 0; right[rnum] != NULL; rnum++)
{
char **temp = comsubs (left[lnum], right[rnum]);
both = addlists (both, temp);
@@ -4014,7 +4020,7 @@ struct must
};
static must *
-allocmust (must *mp, ptrdiff_t size)
+allocmust (must *mp, idx_t size)
{
must *new_mp = xmalloc (sizeof *new_mp);
new_mp->in = xzalloc (sizeof *new_mp->in);
@@ -4060,7 +4066,7 @@ dfamust (struct dfa const *d)
bool need_endline = false;
bool case_fold_unibyte = d->syntax.case_fold && MB_CUR_MAX == 1;
- for (ptrdiff_t ri = 1; ri + 1 < d->tindex; ri++)
+ for (idx_t ri = 1; ri + 1 < d->tindex; ri++)
{
token t = d->tokens[ri];
switch (t)
@@ -4100,7 +4106,7 @@ dfamust (struct dfa const *d)
char **new;
must *rmp = mp;
must *lmp = mp = mp->prev;
- ptrdiff_t j, ln, rn, n;
+ idx_t j, ln, rn, n;
/* Guaranteed to be. Unlikely, but ... */
if (streq (lmp->is, rmp->is))
@@ -4115,7 +4121,7 @@ dfamust (struct dfa const *d)
lmp->endline = false;
}
/* Left side--easy */
- ptrdiff_t i = 0;
+ idx_t i = 0;
while (lmp->left[i] != '\0' && lmp->left[i] == rmp->left[i])
++i;
lmp->left[i] = '\0';
@@ -4145,7 +4151,7 @@ dfamust (struct dfa const *d)
case END:
assert (!mp->prev);
- for (ptrdiff_t i = 0; mp->in[i] != NULL; i++)
+ for (idx_t i = 0; mp->in[i] != NULL; i++)
if (strlen (mp->in[i]) > strlen (result))
result = mp->in[i];
if (streq (result, mp->is))
@@ -4169,8 +4175,8 @@ dfamust (struct dfa const *d)
lmp->in = addlists (lmp->in, rmp->in);
if (lmp->right[0] != '\0' && rmp->left[0] != '\0')
{
- ptrdiff_t lrlen = strlen (lmp->right);
- ptrdiff_t rllen = strlen (rmp->left);
+ idx_t lrlen = strlen (lmp->right);
+ idx_t rllen = strlen (rmp->left);
char *tp = xmalloc (lrlen + rllen);
memcpy (tp, lmp->right, lrlen);
memcpy (tp + lrlen, rmp->left, rllen);
@@ -4235,7 +4241,7 @@ dfamust (struct dfa const *d)
}
}
- ptrdiff_t rj = ri + 2;
+ idx_t rj = ri + 2;
if (d->tokens[ri + 1] == CAT)
{
for (; rj < d->tindex - 1; rj += 2)
@@ -4250,7 +4256,7 @@ dfamust (struct dfa const *d)
mp->is[0] = mp->left[0] = mp->right[0]
= case_fold_unibyte ? toupper (t) : t;
- ptrdiff_t i;
+ idx_t i;
for (i = 1; ri + 2 < rj; i++)
{
ri += 2;
diff --git a/lib/dfa.h b/lib/dfa.h
index bf87703e8..96c3bf1f1 100644
--- a/lib/dfa.h
+++ b/lib/dfa.h
@@ -66,7 +66,7 @@ extern void dfasyntax (struct dfa *, struct localeinfo const *,
reg_syntax_t, int);
/* Parse the given string of given length into the given struct dfa. */
-extern void dfaparse (char const *, size_t, struct dfa *);
+extern void dfaparse (char const *, ptrdiff_t, struct dfa *);
/* Allocate and return a struct dfamust from a struct dfa that was
initialized by dfaparse and not yet given to dfacomp. */
@@ -79,7 +79,7 @@ extern void dfamustfree (struct dfamust *);
The last argument says whether to build a searching or an exact matcher.
A null first argument means the struct dfa has already been
initialized by dfaparse; the second argument is ignored. */
-extern void dfacomp (char const *, size_t, struct dfa *, bool);
+extern void dfacomp (char const *, ptrdiff_t, struct dfa *, bool);
/* Search through a buffer looking for a match to the given struct dfa.
Find the first occurrence of a string matching the regexp in the
@@ -94,7 +94,7 @@ extern void dfacomp (char const *, size_t, struct dfa *, bool);
encountered a back-reference. The caller can use this to decide
whether to fall back on a backtracking matcher. */
extern char *dfaexec (struct dfa *d, char const *begin, char *end,
- bool allow_nl, size_t *count, bool *backref);
+ bool allow_nl, ptrdiff_t *count, bool *backref);
/* Return a superset for D. The superset matches everything that D
matches, along with some other strings (though the latter should be
--
2.23.0
