[PATCH 1/4] dfa: omit unnecessary allocation

[PATCH 1/4] dfa: omit unnecessary allocation

[Paul Eggert]

* lib/dfa.c (dfaanalyze): Do not allocate follow set, since
an all-zero follow set works just fine.
---
 ChangeLog | 4 ++++
 lib/dfa.c | 2 --
 2 files changed, 4 insertions(+), 2 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index f0cd277..beeefb7 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,9 @@
 2017-01-09  Paul Eggert  <eggert@cs.ucla.edu>
 
+	dfa: omit unnecessary allocation
+	* lib/dfa.c (dfaanalyze): Do not allocate follow set, since
+	an all-zero follow set works just fine.
+
 	dfa: omit unused local
 	* lib/dfa.c (build_state): Fix up recent change.
 
diff --git a/lib/dfa.c b/lib/dfa.c
index e8cb6bb..b27bef4 100644
--- a/lib/dfa.c
+++ b/lib/dfa.c
@@ -2501,8 +2501,6 @@ dfaanalyze (struct dfa *d, bool searchflag)
           firstpos->index = lastpos->index = i;
           firstpos->constraint = lastpos->constraint = NO_CONSTRAINT;
 
-          /* Allocate the follow set for this position.  */
-          alloc_position_set (&d->follows[i], 1);
           break;
         }
 #ifdef DEBUG
-- 
2.9.3

[PATCH 2/4] dfa: omit unnecessary ptrdiff_t check

[Paul Eggert]

* lib/dfa.c (alloc_position_set): Do not worry about ptrdiff_t
overflow, since xnmalloc does that now.
---
 ChangeLog | 4 ++++
 lib/dfa.c | 2 --
 2 files changed, 4 insertions(+), 2 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index beeefb7..91cdc6d 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,9 @@
 2017-01-09  Paul Eggert  <eggert@cs.ucla.edu>
 
+	dfa: omit unnecessary ptrdiff_t check
+	* lib/dfa.c (alloc_position_set): Do not worry about ptrdiff_t
+	overflow, since xnmalloc does that now.
+
 	dfa: omit unnecessary allocation
 	* lib/dfa.c (dfaanalyze): Do not allocate follow set, since
 	an all-zero follow set works just fine.
diff --git a/lib/dfa.c b/lib/dfa.c
index b27bef4..509d6d1 100644
--- a/lib/dfa.c
+++ b/lib/dfa.c
@@ -2007,8 +2007,6 @@ static void
 alloc_position_set (position_set *s, size_t size)
 {
   s->elems = xnmalloc (size, sizeof *s->elems);
-  if (PTRDIFF_MAX < SIZE_MAX / sizeof *s->elems && PTRDIFF_MAX < size)
-    xalloc_die ();
   s->alloc = size;
   s->nelem = 0;
 }
-- 
2.9.3

[PATCH 3/4] dfa: shrink constraints from 4 bits to 3

[Paul Eggert]

* lib/dfa.c (newline_constraint, letter_constraint)
(other_constraint, prev_newline_dependent)
(prev_letter_dependent, NO_CONSTRAINT, BEGLINE_CONSTRAINT)
(ENDLINE_CONSTRAINT, BEGWORD_CONSTRAINT, ENDWORD_CONSTRAINT)
(LIMWORD_CONSTRAINT, NOTLIMWORD_CONSTRAINT):
Constraints need only 3 bits, not 4.  Using smaller integers
shrinks the code a bit and makes grep a tad faster on x86-64.
---
 ChangeLog |  9 +++++++++
 lib/dfa.c | 32 ++++++++++++++++----------------
 2 files changed, 25 insertions(+), 16 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index 91cdc6d..e0b73b5 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,14 @@
 2017-01-09  Paul Eggert  <eggert@cs.ucla.edu>
 
+	dfa: shrink constraints from 4 bits to 3
+	* lib/dfa.c (newline_constraint, letter_constraint)
+	(other_constraint, prev_newline_dependent)
+	(prev_letter_dependent, NO_CONSTRAINT, BEGLINE_CONSTRAINT)
+	(ENDLINE_CONSTRAINT, BEGWORD_CONSTRAINT, ENDWORD_CONSTRAINT)
+	(LIMWORD_CONSTRAINT, NOTLIMWORD_CONSTRAINT):
+	Constraints need only 3 bits, not 4.  Using smaller integers
+	shrinks the code a bit and makes grep a tad faster on x86-64.
+
 	dfa: omit unnecessary ptrdiff_t check
 	* lib/dfa.c (alloc_position_set): Do not worry about ptrdiff_t
 	overflow, since xnmalloc does that now.
diff --git a/lib/dfa.c b/lib/dfa.c
index 509d6d1..28678c2 100644
--- a/lib/dfa.c
+++ b/lib/dfa.c
@@ -137,13 +137,13 @@ enum
 /* Sometimes characters can only be matched depending on the surrounding
    context.  Such context decisions depend on what the previous character
    was, and the value of the current (lookahead) character.  Context
-   dependent constraints are encoded as 12-bit integers.  Each bit that
+   dependent constraints are encoded as 9-bit integers.  Each bit that
    is set indicates that the constraint succeeds in the corresponding
    context.
 
-   bit 8-11 - valid contexts when next character is CTX_NEWLINE
-   bit 4-7  - valid contexts when next character is CTX_LETTER
-   bit 0-3  - valid contexts when next character is CTX_NONE
+   bit 6-8  - valid contexts when next character is CTX_NEWLINE
+   bit 3-5  - valid contexts when next character is CTX_LETTER
+   bit 0-2  - valid contexts when next character is CTX_NONE
 
    succeeds_in_context determines whether a given constraint
    succeeds in a particular context.  Prev is a bitmask of possible
@@ -152,17 +152,17 @@ enum
 static int
 newline_constraint (int constraint)
 {
-  return (constraint >> 8) & 0xf;
+  return (constraint >> 6) & 7;
 }
 static int
 letter_constraint (int constraint)
 {
-  return (constraint >> 4) & 0xf;
+  return (constraint >> 3) & 7;
 }
 static int
 other_constraint (int constraint)
 {
-  return constraint & 0xf;
+  return constraint & 7;
 }
 
 static bool
@@ -178,12 +178,12 @@ succeeds_in_context (int constraint, int prev, int curr)
 static bool
 prev_newline_dependent (int constraint)
 {
-  return ((constraint ^ constraint >> 2) & 0x111) != 0;
+  return ((constraint ^ constraint >> 2) & 0111) != 0;
 }
 static bool
 prev_letter_dependent (int constraint)
 {
-  return ((constraint ^ constraint >> 1) & 0x111) != 0;
+  return ((constraint ^ constraint >> 1) & 0111) != 0;
 }
 
 /* Tokens that match the empty string subject to some constraint actually
@@ -192,13 +192,13 @@ prev_letter_dependent (int constraint)
    the constraints corresponding to the special tokens previously defined.  */
 enum
   {
-    NO_CONSTRAINT = 0x777,
-    BEGLINE_CONSTRAINT = 0x444,
-    ENDLINE_CONSTRAINT = 0x700,
-    BEGWORD_CONSTRAINT = 0x050,
-    ENDWORD_CONSTRAINT = 0x202,
-    LIMWORD_CONSTRAINT = 0x252,
-    NOTLIMWORD_CONSTRAINT = 0x525
+    NO_CONSTRAINT = 0777,
+    BEGLINE_CONSTRAINT = 0444,
+    ENDLINE_CONSTRAINT = 0700,
+    BEGWORD_CONSTRAINT = 0050,
+    ENDWORD_CONSTRAINT = 0202,
+    LIMWORD_CONSTRAINT = 0252,
+    NOTLIMWORD_CONSTRAINT = 0525
   };
 
 /* The regexp is parsed into an array of tokens in postfix form.  Some tokens
-- 
2.9.3

[PATCH 4/4] dfa: minor simplification with emptyset

[Paul Eggert]

* lib/dfa.c (build_state): Simplify by using emptyset.
---
 ChangeLog | 5 +++++
 lib/dfa.c | 5 +----
 2 files changed, 6 insertions(+), 4 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index e0b73b5..8fda293 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,8 @@
+2017-01-10  Paul Eggert  <eggert@cs.ucla.edu>
+
+	dfa: minor simplification with emptyset
+	* lib/dfa.c (build_state): Simplify by using emptyset.
+
 2017-01-09  Paul Eggert  <eggert@cs.ucla.edu>
 
 	dfa: shrink constraints from 4 bits to 3
diff --git a/lib/dfa.c b/lib/dfa.c
index 28678c2..5df27ea 100644
--- a/lib/dfa.c
+++ b/lib/dfa.c
@@ -2760,10 +2760,7 @@ build_state (state_num s, struct dfa *d, unsigned char uc)
               matches.w[j] &= d->syntax.letters.w[j] | d->syntax.newline.w[j];
 
           /* If there are no characters left, there's no point in going on.  */
-          size_t j;
-          for (j = 0; j < CHARCLASS_WORDS && !matches.w[j]; j++)
-            continue;
-          if (j == CHARCLASS_WORDS)
+          if (emptyset (&matches))
             continue;
 
           /* If we have reset the bit that made us declare "matched", reset
-- 
2.9.3