Update contrib/tools/bison to 3.3.2

6215035f251de2d87363064fb4f07a2b14a3b4c8

11 files changed, 5511 insertions, 0 deletions

diff --git a/contrib/tools/bison/lib/bitset/array.c b/contrib/tools/bison/lib/bitset/array.c
new file mode 100644
index 0000000000..fde9fa24f5
--- /dev/null
+++ b/contrib/tools/bison/lib/bitset/array.c
@@ -0,0 +1,772 @@
+/* Array bitsets.
+
+   Copyright (C) 2002-2003, 2006, 2009-2015, 2018-2019 Free Software
+   Foundation, Inc.
+
+   Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz).
+
+   This program is free software: you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation, either version 3 of the License, or
+   (at your option) any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
+
+#include <config.h>
+
+#include "bitset/array.h"
+#include <stddef.h>
+#include <stdlib.h>
+#include <string.h>
+
+/* This file implements fixed size bitsets stored as an array
+   of words.  Any unused bits in the last word must be zero.  */
+
+#define ABITSET_N_WORDS(N) (((N) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS)
+#define ABITSET_WORDS(X) ((X)->a.words)
+
+
+static bitset_bindex
+abitset_resize (bitset src, bitset_bindex size)
+{
+  /* These bitsets have a fixed size.  */
+  if (BITSET_SIZE_ (src) != size)
+    abort ();
+
+  return size;
+}
+
+/* Find list of up to NUM bits set in BSET starting from and including
+   *NEXT and store in array LIST.  Return with actual number of bits
+   found and with *NEXT indicating where search stopped.  */
+static bitset_bindex
+abitset_small_list (bitset src, bitset_bindex *list,
+                    bitset_bindex num, bitset_bindex *next)
+{
+  bitset_word word = ABITSET_WORDS (src)[0];
+
+  /* Short circuit common case.  */
+  if (!word)
+    return 0;
+
+  bitset_windex size = BITSET_SIZE_ (src);
+  bitset_bindex bitno = *next;
+  if (bitno >= size)
+    return 0;
+
+  word >>= bitno;
+
+  /* If num is 1, we could speed things up with a binary search
+     of the word of interest.  */
+
+  bitset_bindex count;
+  if (num >= BITSET_WORD_BITS)
+    {
+      for (count = 0; word; bitno++)
+        {
+          if (word & 1)
+            list[count++] = bitno;
+          word >>= 1;
+        }
+    }
+  else
+    {
+      for (count = 0; word; bitno++)
+        {
+          if (word & 1)
+            {
+              list[count++] = bitno;
+              if (count >= num)
+                {
+                  bitno++;
+                  break;
+                }
+            }
+          word >>= 1;
+        }
+    }
+
+  *next = bitno;
+  return count;
+}
+
+
+/* Set bit BITNO in bitset DST.  */
+static void
+abitset_set (bitset dst ATTRIBUTE_UNUSED, bitset_bindex bitno ATTRIBUTE_UNUSED)
+{
+  /* This should never occur for abitsets since we should always hit
+     the cache.  It is likely someone is trying to access outside the
+     bounds of the bitset.  */
+  abort ();
+}
+
+
+/* Reset bit BITNO in bitset DST.  */
+static void
+abitset_reset (bitset dst ATTRIBUTE_UNUSED,
+               bitset_bindex bitno ATTRIBUTE_UNUSED)
+{
+  /* This should never occur for abitsets since we should always hit
+     the cache.  It is likely someone is trying to access outside the
+     bounds of the bitset.  Since the bit is zero anyway, let it pass.  */
+}
+
+
+/* Test bit BITNO in bitset SRC.  */
+static bool
+abitset_test (bitset src ATTRIBUTE_UNUSED,
+              bitset_bindex bitno ATTRIBUTE_UNUSED)
+{
+  /* This should never occur for abitsets since we should always
+     hit the cache.  */
+  return false;
+}
+
+
+/* Find list of up to NUM bits set in BSET in reverse order, starting
+   from and including NEXT and store in array LIST.  Return with
+   actual number of bits found and with *NEXT indicating where search
+   stopped.  */
+static bitset_bindex
+abitset_list_reverse (bitset src, bitset_bindex *list,
+                      bitset_bindex num, bitset_bindex *next)
+{
+  bitset_bindex rbitno = *next;
+  bitset_word *srcp = ABITSET_WORDS (src);
+  bitset_bindex n_bits = BITSET_SIZE_ (src);
+
+  /* If num is 1, we could speed things up with a binary search
+     of the word of interest.  */
+
+  if (rbitno >= n_bits)
+    return 0;
+
+  bitset_bindex count = 0;
+
+  bitset_bindex bitno = n_bits - (rbitno + 1);
+
+  bitset_windex windex = bitno / BITSET_WORD_BITS;
+  unsigned bitcnt = bitno % BITSET_WORD_BITS;
+  bitset_bindex bitoff = windex * BITSET_WORD_BITS;
+
+  do
+    {
+      bitset_word word = srcp[windex] << (BITSET_WORD_BITS - 1 - bitcnt);
+      for (; word; bitcnt--)
+        {
+          if (word & BITSET_MSB)
+            {
+              list[count++] = bitoff + bitcnt;
+              if (count >= num)
+                {
+                  *next = n_bits - (bitoff + bitcnt);
+                  return count;
+                }
+            }
+          word <<= 1;
+        }
+      bitoff -= BITSET_WORD_BITS;
+      bitcnt = BITSET_WORD_BITS - 1;
+    }
+  while (windex--);
+
+  *next = n_bits - (bitoff + 1);
+  return count;
+}
+
+
+/* Find list of up to NUM bits set in BSET starting from and including
+   *NEXT and store in array LIST.  Return with actual number of bits
+   found and with *NEXT indicating where search stopped.  */
+static bitset_bindex
+abitset_list (bitset src, bitset_bindex *list,
+              bitset_bindex num, bitset_bindex *next)
+{
+  bitset_windex windex;
+  bitset_bindex bitoff;
+  bitset_windex size = src->b.csize;
+  bitset_word *srcp = ABITSET_WORDS (src);
+
+  bitset_bindex bitno = *next;
+
+  bitset_bindex count = 0;
+  if (!bitno)
+    {
+      /* Many bitsets are zero, so make this common case fast.  */
+      for (windex = 0; windex < size && !srcp[windex]; windex++)
+        continue;
+      if (windex >= size)
+        return 0;
+
+      /* If num is 1, we could speed things up with a binary search
+         of the current word.  */
+
+      bitoff = windex * BITSET_WORD_BITS;
+    }
+  else
+    {
+      if (bitno >= BITSET_SIZE_ (src))
+        return 0;
+
+      windex = bitno / BITSET_WORD_BITS;
+      bitno = bitno % BITSET_WORD_BITS;
+
+      if (bitno)
+        {
+          /* Handle the case where we start within a word.
+             Most often, this is executed with large bitsets
+             with many set bits where we filled the array
+             on the previous call to this function.  */
+
+          bitoff = windex * BITSET_WORD_BITS;
+          bitset_word word = srcp[windex] >> bitno;
+          for (bitno = bitoff + bitno; word; bitno++)
+            {
+              if (word & 1)
+                {
+                  list[count++] = bitno;
+                  if (count >= num)
+                    {
+                      *next = bitno + 1;
+                      return count;
+                    }
+                }
+              word >>= 1;
+            }
+          windex++;
+        }
+      bitoff = windex * BITSET_WORD_BITS;
+    }
+
+  for (; windex < size; windex++, bitoff += BITSET_WORD_BITS)
+    {
+      bitset_word word = srcp[windex];
+      if (!word)
+        continue;
+
+      if ((count + BITSET_WORD_BITS) < num)
+        {
+          for (bitno = bitoff; word; bitno++)
+            {
+              if (word & 1)
+                list[count++] = bitno;
+              word >>= 1;
+            }
+        }
+      else
+        {
+          for (bitno = bitoff; word; bitno++)
+            {
+              if (word & 1)
+                {
+                  list[count++] = bitno;
+                  if (count >= num)
+                    {
+                      *next = bitno + 1;
+                      return count;
+                    }
+                }
+              word >>= 1;
+            }
+        }
+    }
+
+  *next = bitoff;
+  return count;
+}
+
+
+/* Ensure that any unused bits within the last word are clear.  */
+static inline void
+abitset_unused_clear (bitset dst)
+{
+  unsigned last_bit = BITSET_SIZE_ (dst) % BITSET_WORD_BITS;
+  if (last_bit)
+    ABITSET_WORDS (dst)[dst->b.csize - 1] &=
+      ((bitset_word) 1 << last_bit) - 1;
+}
+
+
+static void
+abitset_ones (bitset dst)
+{
+  bitset_word *dstp = ABITSET_WORDS (dst);
+  size_t bytes = sizeof (bitset_word) * dst->b.csize;
+
+  memset (dstp, -1, bytes);
+  abitset_unused_clear (dst);
+}
+
+
+static void
+abitset_zero (bitset dst)
+{
+  bitset_word *dstp = ABITSET_WORDS (dst);
+  size_t bytes = sizeof (bitset_word) * dst->b.csize;
+
+  memset (dstp, 0, bytes);
+}
+
+
+static bool
+abitset_empty_p (bitset dst)
+{
+  bitset_word *dstp = ABITSET_WORDS (dst);
+
+  for (bitset_windex i = 0; i < dst->b.csize; i++)
+    if (dstp[i])
+      return false;
+  return true;
+}
+
+
+static void
+abitset_copy1 (bitset dst, bitset src)
+{
+  bitset_word *srcp = ABITSET_WORDS (src);
+  bitset_word *dstp = ABITSET_WORDS (dst);
+  if (srcp == dstp)
+    return;
+  bitset_windex size = dst->b.csize;
+  memcpy (dstp, srcp, sizeof (bitset_word) * size);
+}
+
+
+static void
+abitset_not (bitset dst, bitset src)
+{
+  bitset_word *srcp = ABITSET_WORDS (src);
+  bitset_word *dstp = ABITSET_WORDS (dst);
+  bitset_windex size = dst->b.csize;
+
+  for (bitset_windex i = 0; i < size; i++)
+    *dstp++ = ~(*srcp++);
+  abitset_unused_clear (dst);
+}
+
+
+static bool
+abitset_equal_p (bitset dst, bitset src)
+{
+  bitset_word *srcp = ABITSET_WORDS (src);
+  bitset_word *dstp = ABITSET_WORDS (dst);
+  bitset_windex size = dst->b.csize;
+
+  for (bitset_windex i = 0; i < size; i++)
+    if (*srcp++ != *dstp++)
+      return false;
+  return true;
+}
+
+
+static bool
+abitset_subset_p (bitset dst, bitset src)
+{
+  bitset_word *srcp = ABITSET_WORDS (src);
+  bitset_word *dstp = ABITSET_WORDS (dst);
+  bitset_windex size = dst->b.csize;
+
+  for (bitset_windex i = 0; i < size; i++, dstp++, srcp++)
+    if (*dstp != (*srcp | *dstp))
+      return false;
+  return true;
+}
+
+
+static bool
+abitset_disjoint_p (bitset dst, bitset src)
+{
+  bitset_word *srcp = ABITSET_WORDS (src);
+  bitset_word *dstp = ABITSET_WORDS (dst);
+  bitset_windex size = dst->b.csize;
+
+  for (bitset_windex i = 0; i < size; i++)
+    if (*srcp++ & *dstp++)
+      return false;
+  return true;
+}
+
+
+static void
+abitset_and (bitset dst, bitset src1, bitset src2)
+{
+  bitset_word *src1p = ABITSET_WORDS (src1);
+  bitset_word *src2p = ABITSET_WORDS (src2);
+  bitset_word *dstp = ABITSET_WORDS (dst);
+  bitset_windex size = dst->b.csize;
+
+  for (bitset_windex i = 0; i < size; i++)
+    *dstp++ = *src1p++ & *src2p++;
+}
+
+
+static bool
+abitset_and_cmp (bitset dst, bitset src1, bitset src2)
+{
+  bool changed = false;
+  bitset_word *src1p = ABITSET_WORDS (src1);
+  bitset_word *src2p = ABITSET_WORDS (src2);
+  bitset_word *dstp = ABITSET_WORDS (dst);
+  bitset_windex size = dst->b.csize;
+
+  for (bitset_windex i = 0; i < size; i++, dstp++)
+    {
+      bitset_word tmp = *src1p++ & *src2p++;
+      if (*dstp != tmp)
+        {
+          changed = true;
+          *dstp = tmp;
+        }
+    }
+  return changed;
+}
+
+
+static void
+abitset_andn (bitset dst, bitset src1, bitset src2)
+{
+  bitset_word *src1p = ABITSET_WORDS (src1);
+  bitset_word *src2p = ABITSET_WORDS (src2);
+  bitset_word *dstp = ABITSET_WORDS (dst);
+  bitset_windex size = dst->b.csize;
+
+  for (bitset_windex i = 0; i < size; i++)
+    *dstp++ = *src1p++ & ~(*src2p++);
+}
+
+
+static bool
+abitset_andn_cmp (bitset dst, bitset src1, bitset src2)
+{
+  bool changed = false;
+  bitset_word *src1p = ABITSET_WORDS (src1);
+  bitset_word *src2p = ABITSET_WORDS (src2);
+  bitset_word *dstp = ABITSET_WORDS (dst);
+  bitset_windex size = dst->b.csize;
+
+  for (bitset_windex i = 0; i < size; i++, dstp++)
+    {
+      bitset_word tmp = *src1p++ & ~(*src2p++);
+      if (*dstp != tmp)
+        {
+          changed = true;
+          *dstp = tmp;
+        }
+    }
+  return changed;
+}
+
+
+static void
+abitset_or (bitset dst, bitset src1, bitset src2)
+{
+  bitset_word *src1p = ABITSET_WORDS (src1);
+  bitset_word *src2p = ABITSET_WORDS (src2);
+  bitset_word *dstp = ABITSET_WORDS (dst);
+  bitset_windex size = dst->b.csize;
+
+  for (bitset_windex i = 0; i < size; i++)
+    *dstp++ = *src1p++ | *src2p++;
+}
+
+
+static bool
+abitset_or_cmp (bitset dst, bitset src1, bitset src2)
+{
+  bool changed = false;
+  bitset_word *src1p = ABITSET_WORDS (src1);
+  bitset_word *src2p = ABITSET_WORDS (src2);
+  bitset_word *dstp = ABITSET_WORDS (dst);
+  bitset_windex size = dst->b.csize;
+
+  for (bitset_windex i = 0; i < size; i++, dstp++)
+    {
+      bitset_word tmp = *src1p++ | *src2p++;
+
+      if (*dstp != tmp)
+        {
+          changed = true;
+          *dstp = tmp;
+        }
+    }
+  return changed;
+}
+
+
+static void
+abitset_xor (bitset dst, bitset src1, bitset src2)
+{
+  bitset_word *src1p = ABITSET_WORDS (src1);
+  bitset_word *src2p = ABITSET_WORDS (src2);
+  bitset_word *dstp = ABITSET_WORDS (dst);
+  bitset_windex size = dst->b.csize;
+
+  for (bitset_windex i = 0; i < size; i++)
+    *dstp++ = *src1p++ ^ *src2p++;
+}
+
+
+static bool
+abitset_xor_cmp (bitset dst, bitset src1, bitset src2)
+{
+  bool changed = false;
+  bitset_word *src1p = ABITSET_WORDS (src1);
+  bitset_word *src2p = ABITSET_WORDS (src2);
+  bitset_word *dstp = ABITSET_WORDS (dst);
+  bitset_windex size = dst->b.csize;
+
+  for (bitset_windex i = 0; i < size; i++, dstp++)
+    {
+      bitset_word tmp = *src1p++ ^ *src2p++;
+
+      if (*dstp != tmp)
+        {
+          changed = true;
+          *dstp = tmp;
+        }
+    }
+  return changed;
+}
+
+
+static void
+abitset_and_or (bitset dst, bitset src1, bitset src2, bitset src3)
+{
+  bitset_word *src1p = ABITSET_WORDS (src1);
+  bitset_word *src2p = ABITSET_WORDS (src2);
+  bitset_word *src3p = ABITSET_WORDS (src3);
+  bitset_word *dstp = ABITSET_WORDS (dst);
+  bitset_windex size = dst->b.csize;
+
+  for (bitset_windex i = 0; i < size; i++)
+    *dstp++ = (*src1p++ & *src2p++) | *src3p++;
+}
+
+
+static bool
+abitset_and_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
+{
+  bool changed = false;
+  bitset_word *src1p = ABITSET_WORDS (src1);
+  bitset_word *src2p = ABITSET_WORDS (src2);
+  bitset_word *src3p = ABITSET_WORDS (src3);
+  bitset_word *dstp = ABITSET_WORDS (dst);
+  bitset_windex size = dst->b.csize;
+
+  for (bitset_windex i = 0; i < size; i++, dstp++)
+    {
+      bitset_word tmp = (*src1p++ & *src2p++) | *src3p++;
+      if (*dstp != tmp)
+        {
+          changed = true;
+          *dstp = tmp;
+        }
+    }
+  return changed;
+}
+
+
+static void
+abitset_andn_or (bitset dst, bitset src1, bitset src2, bitset src3)
+{
+  bitset_word *src1p = ABITSET_WORDS (src1);
+  bitset_word *src2p = ABITSET_WORDS (src2);
+  bitset_word *src3p = ABITSET_WORDS (src3);
+  bitset_word *dstp = ABITSET_WORDS (dst);
+  bitset_windex size = dst->b.csize;
+
+  for (bitset_windex i = 0; i < size; i++)
+    *dstp++ = (*src1p++ & ~(*src2p++)) | *src3p++;
+}
+
+
+static bool
+abitset_andn_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
+{
+  bool changed = false;
+  bitset_word *src1p = ABITSET_WORDS (src1);
+  bitset_word *src2p = ABITSET_WORDS (src2);
+  bitset_word *src3p = ABITSET_WORDS (src3);
+  bitset_word *dstp = ABITSET_WORDS (dst);
+  bitset_windex size = dst->b.csize;
+
+  for (bitset_windex i = 0; i < size; i++, dstp++)
+    {
+      bitset_word tmp = (*src1p++ & ~(*src2p++)) | *src3p++;
+      if (*dstp != tmp)
+        {
+          changed = true;
+          *dstp = tmp;
+        }
+    }
+  return changed;
+}
+
+
+static void
+abitset_or_and (bitset dst, bitset src1, bitset src2, bitset src3)
+{
+  bitset_word *src1p = ABITSET_WORDS (src1);
+  bitset_word *src2p = ABITSET_WORDS (src2);
+  bitset_word *src3p = ABITSET_WORDS (src3);
+  bitset_word *dstp = ABITSET_WORDS (dst);
+  bitset_windex size = dst->b.csize;
+
+  for (bitset_windex i = 0; i < size; i++)
+    *dstp++ = (*src1p++ | *src2p++) & *src3p++;
+}
+
+
+static bool
+abitset_or_and_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
+{
+  bool changed = false;
+  bitset_word *src1p = ABITSET_WORDS (src1);
+  bitset_word *src2p = ABITSET_WORDS (src2);
+  bitset_word *src3p = ABITSET_WORDS (src3);
+  bitset_word *dstp = ABITSET_WORDS (dst);
+  bitset_windex size = dst->b.csize;
+
+  for (bitset_windex i = 0; i < size; i++, dstp++)
+    {
+      bitset_word tmp = (*src1p++ | *src2p++) & *src3p++;
+      if (*dstp != tmp)
+        {
+          changed = true;
+          *dstp = tmp;
+        }
+    }
+  return changed;
+}
+
+
+static void
+abitset_copy (bitset dst, bitset src)
+{
+  if (BITSET_COMPATIBLE_ (dst, src))
+    abitset_copy1 (dst, src);
+  else
+    bitset_copy_ (dst, src);
+}
+
+
+/* Vector of operations for single word bitsets.  */
+struct bitset_vtable abitset_small_vtable = {
+  abitset_set,
+  abitset_reset,
+  bitset_toggle_,
+  abitset_test,
+  abitset_resize,
+  bitset_size_,
+  bitset_count_,
+  abitset_empty_p,
+  abitset_ones,
+  abitset_zero,
+  abitset_copy,
+  abitset_disjoint_p,
+  abitset_equal_p,
+  abitset_not,
+  abitset_subset_p,
+  abitset_and,
+  abitset_and_cmp,
+  abitset_andn,
+  abitset_andn_cmp,
+  abitset_or,
+  abitset_or_cmp,
+  abitset_xor,
+  abitset_xor_cmp,
+  abitset_and_or,
+  abitset_and_or_cmp,
+  abitset_andn_or,
+  abitset_andn_or_cmp,
+  abitset_or_and,
+  abitset_or_and_cmp,
+  abitset_small_list,
+  abitset_list_reverse,
+  NULL,
+  BITSET_ARRAY
+};
+
+
+/* Vector of operations for multiple word bitsets.  */
+struct bitset_vtable abitset_vtable = {
+  abitset_set,
+  abitset_reset,
+  bitset_toggle_,
+  abitset_test,
+  abitset_resize,
+  bitset_size_,
+  bitset_count_,
+  abitset_empty_p,
+  abitset_ones,
+  abitset_zero,
+  abitset_copy,
+  abitset_disjoint_p,
+  abitset_equal_p,
+  abitset_not,
+  abitset_subset_p,
+  abitset_and,
+  abitset_and_cmp,
+  abitset_andn,
+  abitset_andn_cmp,
+  abitset_or,
+  abitset_or_cmp,
+  abitset_xor,
+  abitset_xor_cmp,
+  abitset_and_or,
+  abitset_and_or_cmp,
+  abitset_andn_or,
+  abitset_andn_or_cmp,
+  abitset_or_and,
+  abitset_or_and_cmp,
+  abitset_list,
+  abitset_list_reverse,
+  NULL,
+  BITSET_ARRAY
+};
+
+
+size_t
+abitset_bytes (bitset_bindex n_bits)
+{
+  size_t header_size = offsetof (union bitset_union, a.words);
+  struct bitset_align_struct { char a; union bitset_union b; };
+  size_t bitset_alignment = offsetof (struct bitset_align_struct, b);
+
+  bitset_windex size = ABITSET_N_WORDS (n_bits);
+  size_t bytes = header_size + size * sizeof (bitset_word);
+
+  /* Align the size properly for a vector of abitset objects.  */
+  if (header_size % bitset_alignment != 0
+      || sizeof (bitset_word) % bitset_alignment != 0)
+    {
+      bytes += bitset_alignment - 1;
+      bytes -= bytes % bitset_alignment;
+    }
+
+  return bytes;
+}
+
+
+bitset
+abitset_init (bitset bset, bitset_bindex n_bits)
+{
+  bitset_windex size = ABITSET_N_WORDS (n_bits);
+  BITSET_NBITS_ (bset) = n_bits;
+
+  /* Use optimized routines if bitset fits within a single word.
+     There is probably little merit if using caching since
+     the small bitset will always fit in the cache.  */
+  bset->b.vtable = size == 1 ? &abitset_small_vtable : &abitset_vtable;
+  bset->b.cindex = 0;
+  bset->b.csize = size;
+  bset->b.cdata = ABITSET_WORDS (bset);
+  return bset;
+}
diff --git a/contrib/tools/bison/lib/bitset/array.h b/contrib/tools/bison/lib/bitset/array.h
new file mode 100644
index 0000000000..6f49a2e047
--- /dev/null
+++ b/contrib/tools/bison/lib/bitset/array.h
@@ -0,0 +1,30 @@
+/* Functions to support abitsets.
+
+   Copyright (C) 2002, 2004, 2009-2015, 2018-2019 Free Software Foundation,
+   Inc.
+
+   Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz).
+
+   This program is free software: you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation, either version 3 of the License, or
+   (at your option) any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
+
+#ifndef _BITSET_ARRAY_H
+#define _BITSET_ARRAY_H
+
+#include "bitset.h"
+
+size_t abitset_bytes (bitset_bindex);
+
+bitset abitset_init (bitset, bitset_bindex);
+
+#endif
diff --git a/contrib/tools/bison/lib/bitset/base.h b/contrib/tools/bison/lib/bitset/base.h
new file mode 100644
index 0000000000..4fcafac8b6
--- /dev/null
+++ b/contrib/tools/bison/lib/bitset/base.h
@@ -0,0 +1,312 @@
+/* Base bitset stuff.
+
+   Copyright (C) 2002-2004, 2006, 2009-2015, 2018-2019 Free Software
+   Foundation, Inc.
+
+   Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz).
+
+   This program is free software: you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation, either version 3 of the License, or
+   (at your option) any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
+
+#ifndef _BITSET_BASE_H
+#define _BITSET_BASE_H
+
+#include <limits.h>
+#include <stdbool.h>
+#include <stddef.h>
+
+#include "xalloc.h"
+
+#ifndef __attribute__
+# if __GNUC__ < 2 || (__GNUC__ == 2 && __GNUC_MINOR__ < 8)
+#  define __attribute__(x)
+# endif
+#endif
+
+#define ATTRIBUTE_UNUSED __attribute__ ((__unused__))
+
+/* Currently we support five flavours of bitsets:
+   BITSET_ARRAY:  Array of bits (fixed size, fast for dense bitsets).
+                  Memory for bit array and bitset structure allocated
+                  contiguously.
+   BITSET_LIST:   Linked list of arrays of bits (variable size, least storage
+                  for large very sparse sets).
+   BITSET_TABLE:  Expandable table of pointers to arrays of bits
+                  (variable size, less storage for large sparse sets).
+                  Faster than BITSET_LIST for random access.
+   BITSET_VECTOR: Variable array of bits (variable size, fast for
+                  dense bitsets).
+   BITSET_STATS:  Wrapper bitset for internal use only.  Used for gathering
+                  statistics and/or better run-time checking.
+*/
+enum bitset_type {BITSET_ARRAY, BITSET_LIST, BITSET_TABLE, BITSET_VECTOR,
+                  BITSET_TYPE_NUM, BITSET_STATS};
+#define BITSET_TYPE_NAMES {"abitset", "lbitset", "tbitset", "vbitset"}
+
+extern const char * const bitset_type_names[];
+
+enum bitset_alloc_type {BITSET_MALLOC, BITSET_OBALLOC};
+
+/* Data type used to store a word of bits.  */
+typedef unsigned long bitset_word;
+#define BITSET_WORD_BITS ((unsigned) (CHAR_BIT * sizeof (bitset_word)))
+
+/* Bit index.  In theory we might need a type wider than size_t, but
+   in practice we lose at most a factor of CHAR_BIT by going with
+   size_t, and that is good enough.  If this type is changed to be
+   wider than size_t, the code needs to be modified to check for
+   overflow when converting bit counts to byte or word counts.
+   The bit and word index types must be unsigned.  */
+typedef size_t bitset_bindex;
+
+/* Word index.  */
+typedef size_t bitset_windex;
+
+/* Maximum values for commonly-used unsigned types.  BITSET_SIZE_MAX
+   always equals SIZE_MAX, but some older systems lack SIZE_MAX.  */
+#define BITSET_BINDEX_MAX ((bitset_bindex) -1)
+
+/* Limit max word index to the maximum value of a signed integer
+   to simplify cache disabling.  */
+#define BITSET_WINDEX_MAX (((bitset_windex) -1) >> 1)
+#define BITSET_SIZE_MAX ((size_t) -1)
+
+#define BITSET_MSB ((bitset_word) 1 << (BITSET_WORD_BITS - 1))
+
+#define BITSET_LIST_SIZE 1024
+
+enum bitset_ops {BITSET_OP_ZERO, BITSET_OP_ONES,
+                 BITSET_OP_COPY, BITSET_OP_NOT,
+                 BITSET_OP_EMPTY_P, BITSET_OP_EQUAL_P,
+                 BITSET_OP_SUBSET_P, BITSET_OP_DISJOINT_P,
+                 BITSET_OP_AND, BITSET_OP_OR, BITSET_OP_XOR, BITSET_OP_ANDN,
+                 BITSET_OP_OR_AND, BITSET_OP_AND_OR, BITSET_OP_ANDN_OR};
+
+struct bbitset_struct
+{
+  const struct bitset_vtable *vtable;
+  bitset_windex cindex;         /* Cache word index.  */
+  bitset_windex csize;          /* Cache size in words.  */
+  bitset_word *cdata;           /* Cache data pointer.  */
+  bitset_bindex n_bits;         /* Number of bits.  */
+  /* Perhaps we could sacrifice another word to indicate
+     that the bitset is known to be zero, that a bit has been set
+     in the cache, and that a bit has been cleared in the cache.
+     This would speed up some of the searches but slightly slow down
+     bit set/reset operations of cached bits.  */
+};
+
+
+typedef union bitset_union *bitset;
+
+
+/* Private accessor macros to bitset structure.  */
+#define BITSET_VTABLE_(SRC) (SRC)->b.vtable
+#define BITSET_CINDEX_(SRC) (SRC)->b.cindex
+#define BITSET_CDATA_(SRC) (SRC)->b.cdata
+#define BITSET_CSIZE_(SRC) (SRC)->b.csize
+#define BITSET_NBITS_(SRC) (SRC)->b.n_bits
+
+
+/* The contents of this structure should be considered private.  */
+struct bitset_vtable
+{
+  void (*set) (bitset, bitset_bindex);
+  void (*reset) (bitset, bitset_bindex);
+  bool (*toggle) (bitset, bitset_bindex);
+  bool (*test) (bitset, bitset_bindex);
+  bitset_bindex (*resize) (bitset, bitset_bindex);
+  bitset_bindex (*size) (bitset);
+  bitset_bindex (*count) (bitset);
+
+  bool (*empty_p) (bitset);
+  void (*ones) (bitset);
+  void (*zero) (bitset);
+
+  void (*copy) (bitset, bitset);
+  bool (*disjoint_p) (bitset, bitset);
+  bool (*equal_p) (bitset, bitset);
+  void (*not_) (bitset, bitset);
+  bool (*subset_p) (bitset, bitset);
+
+  void (*and_) (bitset, bitset, bitset);
+  bool (*and_cmp) (bitset, bitset, bitset);
+  void (*andn) (bitset, bitset, bitset);
+  bool (*andn_cmp) (bitset, bitset, bitset);
+  void (*or_) (bitset, bitset, bitset);
+  bool (*or_cmp) (bitset, bitset, bitset);
+  void (*xor_) (bitset, bitset, bitset);
+  bool (*xor_cmp) (bitset, bitset, bitset);
+
+  void (*and_or) (bitset, bitset, bitset, bitset);
+  bool (*and_or_cmp) (bitset, bitset, bitset, bitset);
+  void (*andn_or) (bitset, bitset, bitset, bitset);
+  bool (*andn_or_cmp) (bitset, bitset, bitset, bitset);
+  void (*or_and) (bitset, bitset, bitset, bitset);
+  bool (*or_and_cmp) (bitset, bitset, bitset, bitset);
+
+  bitset_bindex (*list) (bitset, bitset_bindex *, bitset_bindex,
+                         bitset_bindex *);
+  bitset_bindex (*list_reverse) (bitset, bitset_bindex *, bitset_bindex,
+                                 bitset_bindex *);
+  void (*free) (bitset);
+  enum bitset_type type;
+};
+
+#define BITSET_COMPATIBLE_(BSET1, BSET2) \
+((BSET1)->b.vtable == (BSET2)->b.vtable)
+
+#define BITSET_CHECK2_(DST, SRC) \
+if (!BITSET_COMPATIBLE_ (DST, SRC)) abort ();
+
+#define BITSET_CHECK3_(DST, SRC1, SRC2) \
+if (!BITSET_COMPATIBLE_ (DST, SRC1) \
+    || !BITSET_COMPATIBLE_ (DST, SRC2)) abort ();
+
+#define BITSET_CHECK4_(DST, SRC1, SRC2, SRC3) \
+if (!BITSET_COMPATIBLE_ (DST, SRC1) || !BITSET_COMPATIBLE_ (DST, SRC2) \
+    || !BITSET_COMPATIBLE_ (DST, SRC3)) abort ();
+
+
+/* Redefine number of bits in bitset DST.  */
+#define BITSET_RESIZE_(DST, SIZE) (DST)->b.vtable->resize (DST, SIZE)
+
+/* Return size in bits of bitset SRC.  */
+#define BITSET_SIZE_(SRC) (SRC)->b.vtable->size (SRC)
+
+/* Return number of bits set in bitset SRC.  */
+#define BITSET_COUNT_(SRC) (SRC)->b.vtable->count (SRC)
+
+/* Return type of bitset SRC.  */
+#define BITSET_TYPE_(DST) (DST)->b.vtable->type
+
+/* Set bit BITNO in bitset DST.  */
+#define BITSET_SET_(DST, BITNO) (DST)->b.vtable->set (DST, BITNO)
+
+/* Reset bit BITNO in bitset DST.  */
+#define BITSET_RESET_(DST, BITNO) (DST)->b.vtable->reset (DST, BITNO)
+
+/* Toggle bit BITNO in bitset DST.  */
+#define BITSET_TOGGLE_(DST, BITNO) (DST)->b.vtable->toggle (DST, BITNO)
+
+/* Return non-zero if bit BITNO in bitset SRC is set.  */
+#define BITSET_TEST_(SRC, BITNO) (SRC)->b.vtable->test (SRC, BITNO)
+
+/* Free bitset SRC.  */
+#define BITSET_FREE_(SRC)\
+ ((SRC)->b.vtable->free ? (SRC)->b.vtable->free (SRC) :(void)0)
+
+
+/* Return SRC == 0.  */
+#define BITSET_EMPTY_P_(SRC) (SRC)->b.vtable->empty_p (SRC)
+
+/* DST = ~0.  */
+#define BITSET_ONES_(DST) (DST)->b.vtable->ones (DST)
+
+/* DST = 0.  */
+#define BITSET_ZERO_(DST) (DST)->b.vtable->zero (DST)
+
+
+
+/* DST = SRC.  */
+#define BITSET_COPY_(DST, SRC) (SRC)->b.vtable->copy (DST, SRC)
+
+/* Return DST & SRC == 0.  */
+#define BITSET_DISJOINT_P_(DST, SRC) (SRC)->b.vtable->disjoint_p (DST, SRC)
+
+/* Return DST == SRC.  */
+#define BITSET_EQUAL_P_(DST, SRC) (SRC)->b.vtable->equal_p (DST, SRC)
+
+/* DST = ~SRC.  */
+#define BITSET_NOT_(DST, SRC) (SRC)->b.vtable->not_ (DST, SRC)
+
+/* Return DST == DST | SRC.  */
+#define BITSET_SUBSET_P_(DST, SRC) (SRC)->b.vtable->subset_p (DST, SRC)
+
+
+/* DST = SRC1 & SRC2.  */
+#define BITSET_AND_(DST, SRC1, SRC2) (SRC1)->b.vtable->and_ (DST, SRC1, SRC2)
+#define BITSET_AND_CMP_(DST, SRC1, SRC2) (SRC1)->b.vtable->and_cmp (DST, SRC1, SRC2)
+
+/* DST = SRC1 & ~SRC2.  */
+#define BITSET_ANDN_(DST, SRC1, SRC2) (SRC1)->b.vtable->andn (DST, SRC1, SRC2)
+#define BITSET_ANDN_CMP_(DST, SRC1, SRC2) (SRC1)->b.vtable->andn_cmp (DST, SRC1, SRC2)
+
+/* DST = SRC1 | SRC2.  */
+#define BITSET_OR_(DST, SRC1, SRC2) (SRC1)->b.vtable->or_ (DST, SRC1, SRC2)
+#define BITSET_OR_CMP_(DST, SRC1, SRC2) (SRC1)->b.vtable->or_cmp (DST, SRC1, SRC2)
+
+/* DST = SRC1 ^ SRC2.  */
+#define BITSET_XOR_(DST, SRC1, SRC2) (SRC1)->b.vtable->xor_ (DST, SRC1, SRC2)
+#define BITSET_XOR_CMP_(DST, SRC1, SRC2) (SRC1)->b.vtable->xor_cmp (DST, SRC1, SRC2)
+
+
+
+/* DST = (SRC1 & SRC2) | SRC3.  Return non-zero if
+   DST != (SRC1 & SRC2) | SRC3.  */
+#define BITSET_AND_OR_(DST, SRC1, SRC2, SRC3) \
+ (SRC1)->b.vtable->and_or (DST, SRC1, SRC2, SRC3)
+#define BITSET_AND_OR_CMP_(DST, SRC1, SRC2, SRC3) \
+ (SRC1)->b.vtable->and_or_cmp (DST, SRC1, SRC2, SRC3)
+
+/* DST = (SRC1 & ~SRC2) | SRC3.  Return non-zero if
+   DST != (SRC1 & ~SRC2) | SRC3.  */
+#define BITSET_ANDN_OR_(DST, SRC1, SRC2, SRC3) \
+ (SRC1)->b.vtable->andn_or (DST, SRC1, SRC2, SRC3)
+#define BITSET_ANDN_OR_CMP_(DST, SRC1, SRC2, SRC3) \
+ (SRC1)->b.vtable->andn_or_cmp (DST, SRC1, SRC2, SRC3)
+
+/* DST = (SRC1 | SRC2) & SRC3.  Return non-zero if
+   DST != (SRC1 | SRC2) & SRC3.  */
+#define BITSET_OR_AND_(DST, SRC1, SRC2, SRC3) \
+ (SRC1)->b.vtable->or_and (DST, SRC1, SRC2, SRC3)
+#define BITSET_OR_AND_CMP_(DST, SRC1, SRC2, SRC3) \
+ (SRC1)->b.vtable->or_and_cmp (DST, SRC1, SRC2, SRC3)
+
+
+/* Find list of up to NUM bits set in BSET starting from and including
+   *NEXT.  Return with actual number of bits found and with *NEXT
+   indicating where search stopped.  */
+#define BITSET_LIST_(BSET, LIST, NUM, NEXT) \
+ (BSET)->b.vtable->list (BSET, LIST, NUM, NEXT)
+
+/* Find reverse list of up to NUM bits set in BSET starting from and
+   including NEXT.  Return with actual number of bits found and with
+   *NEXT indicating where search stopped.  */
+#define BITSET_LIST_REVERSE_(BSET, LIST, NUM, NEXT) \
+ (BSET)->b.vtable->list_reverse (BSET, LIST, NUM, NEXT)
+
+
+/* Private functions for bitset implementations.  */
+
+bool bitset_toggle_ (bitset, bitset_bindex);
+
+bitset_bindex bitset_count_ (bitset);
+
+bitset_bindex bitset_size_ (bitset);
+
+bool bitset_copy_ (bitset, bitset);
+
+void bitset_and_or_ (bitset, bitset, bitset, bitset);
+
+bool bitset_and_or_cmp_ (bitset, bitset, bitset, bitset);
+
+void bitset_andn_or_ (bitset, bitset, bitset, bitset);
+
+bool bitset_andn_or_cmp_ (bitset, bitset, bitset, bitset);
+
+void bitset_or_and_ (bitset, bitset, bitset, bitset);
+
+bool bitset_or_and_cmp_ (bitset, bitset, bitset, bitset);
+
+#endif /* _BBITSET_H  */
diff --git a/contrib/tools/bison/lib/bitset/list.c b/contrib/tools/bison/lib/bitset/list.c
new file mode 100644
index 0000000000..f42edb8ea3
--- /dev/null
+++ b/contrib/tools/bison/lib/bitset/list.c
@@ -0,0 +1,1327 @@
+/* Functions to support link list bitsets.
+
+   Copyright (C) 2002-2004, 2006, 2009-2015, 2018-2019 Free Software
+   Foundation, Inc.
+
+   Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz).
+
+   This program is free software: you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation, either version 3 of the License, or
+   (at your option) any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
+
+#include <config.h>
+
+#include "bitset/list.h"
+
+#include <stddef.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "obstack.h"
+
+/* This file implements linked-list bitsets.  These bitsets can be of
+   arbitrary length and are more efficient than arrays of bits for
+   large sparse sets.
+
+   Usually if all the bits in an element are zero we remove the element
+   from the list.  However, a side effect of the bit caching is that we
+   do not always notice when an element becomes zero.  Hence the
+   lbitset_weed function which removes zero elements.  */
+
+
+/* Number of words to use for each element.  The larger the value the
+   greater the size of the cache and the shorter the time to find a given bit
+   but the more memory wasted for sparse bitsets and the longer the time
+   to search for set bits.
+
+   The routines that dominate timing profiles are lbitset_elt_find
+   and lbitset_elt_link, especially when accessing the bits randomly.  */
+
+#define LBITSET_ELT_WORDS 2
+
+typedef bitset_word lbitset_word;
+
+#define LBITSET_WORD_BITS BITSET_WORD_BITS
+
+/* Number of bits stored in each element.  */
+#define LBITSET_ELT_BITS \
+  ((unsigned) (LBITSET_ELT_WORDS * LBITSET_WORD_BITS))
+
+/* Lbitset element.   We use an array of bits for each element.
+   These are linked together in a doubly-linked list.  */
+typedef struct lbitset_elt_struct
+{
+  struct lbitset_elt_struct *next;      /* Next element.  */
+  struct lbitset_elt_struct *prev;      /* Previous element.  */
+  bitset_windex index;  /* bitno / BITSET_WORD_BITS.  */
+  bitset_word words[LBITSET_ELT_WORDS]; /* Bits that are set.  */
+}
+lbitset_elt;
+
+
+enum lbitset_find_mode
+  { LBITSET_FIND, LBITSET_CREATE, LBITSET_SUBST };
+
+static lbitset_elt lbitset_zero_elts[3]; /* Elements of all zero bits.  */
+
+/* Obstack to allocate bitset elements from.  */
+static struct obstack lbitset_obstack;
+static bool lbitset_obstack_init = false;
+static lbitset_elt *lbitset_free_list;  /* Free list of bitset elements.  */
+
+extern void debug_lbitset (bitset);
+
+#define LBITSET_CURRENT1(X) \
+  ((lbitset_elt *) (void *) ((char *) (X) - offsetof (lbitset_elt, words)))
+
+#define LBITSET_CURRENT(X) LBITSET_CURRENT1((X)->b.cdata)
+
+#define LBITSET_HEAD(X) ((X)->l.head)
+#define LBITSET_TAIL(X) ((X)->l.tail)
+
+/* Allocate a lbitset element.  The bits are not cleared.  */
+static inline lbitset_elt *
+lbitset_elt_alloc (void)
+{
+  lbitset_elt *elt;
+
+  if (lbitset_free_list != 0)
+    {
+      elt = lbitset_free_list;
+      lbitset_free_list = elt->next;
+    }
+  else
+    {
+      if (!lbitset_obstack_init)
+        {
+          lbitset_obstack_init = true;
+
+          /* Let particular systems override the size of a chunk.  */
+
+#ifndef OBSTACK_CHUNK_SIZE
+# define OBSTACK_CHUNK_SIZE 0
+#endif
+
+          /* Let them override the alloc and free routines too.  */
+
+#ifndef OBSTACK_CHUNK_ALLOC
+# define OBSTACK_CHUNK_ALLOC xmalloc
+#endif
+
+#ifndef OBSTACK_CHUNK_FREE
+# define OBSTACK_CHUNK_FREE free
+#endif
+
+#if ! defined __GNUC__ || __GNUC__ < 2
+# define __alignof__(type) 0
+#endif
+
+          obstack_specify_allocation (&lbitset_obstack, OBSTACK_CHUNK_SIZE,
+                                      __alignof__ (lbitset_elt),
+                                      OBSTACK_CHUNK_ALLOC,
+                                      OBSTACK_CHUNK_FREE);
+        }
+
+      /* Perhaps we should add a number of new elements to the free
+         list.  */
+      elt = (lbitset_elt *) obstack_alloc (&lbitset_obstack,
+                                           sizeof (lbitset_elt));
+    }
+
+  return elt;
+}
+
+
+/* Allocate a lbitset element.  The bits are cleared.  */
+static inline lbitset_elt *
+lbitset_elt_calloc (void)
+{
+  lbitset_elt *elt = lbitset_elt_alloc ();
+  memset (elt->words, 0, sizeof (elt->words));
+  return elt;
+}
+
+
+static inline void
+lbitset_elt_free (lbitset_elt *elt)
+{
+  elt->next = lbitset_free_list;
+  lbitset_free_list = elt;
+}
+
+
+/* Unlink element ELT from bitset BSET.  */
+static inline void
+lbitset_elt_unlink (bitset bset, lbitset_elt *elt)
+{
+  lbitset_elt *next = elt->next;
+  lbitset_elt *prev = elt->prev;
+
+  if (prev)
+    prev->next = next;
+
+  if (next)
+    next->prev = prev;
+
+  if (LBITSET_HEAD (bset) == elt)
+    LBITSET_HEAD (bset) = next;
+  if (LBITSET_TAIL (bset) == elt)
+    LBITSET_TAIL (bset) = prev;
+
+  /* Update cache pointer.  Since the first thing we try is to insert
+     before current, make current the next entry in preference to the
+     previous.  */
+  if (LBITSET_CURRENT (bset) == elt)
+    {
+      if (next)
+        {
+          bset->b.cdata = next->words;
+          bset->b.cindex = next->index;
+        }
+      else if (prev)
+        {
+          bset->b.cdata = prev->words;
+          bset->b.cindex = prev->index;
+        }
+      else
+        {
+          bset->b.csize = 0;
+          bset->b.cdata = 0;
+        }
+    }
+
+  lbitset_elt_free (elt);
+}
+
+
+/* Cut the chain of bitset BSET before element ELT and free the
+   elements.  */
+static inline void
+lbitset_prune (bitset bset, lbitset_elt *elt)
+{
+  if (!elt)
+    return;
+
+  if (elt->prev)
+    {
+      LBITSET_TAIL (bset) = elt->prev;
+      bset->b.cdata = elt->prev->words;
+      bset->b.cindex = elt->prev->index;
+      elt->prev->next = 0;
+    }
+  else
+    {
+      LBITSET_HEAD (bset) = 0;
+      LBITSET_TAIL (bset) = 0;
+      bset->b.cdata = 0;
+      bset->b.csize = 0;
+    }
+
+  lbitset_elt *next;
+  for (; elt; elt = next)
+    {
+      next = elt->next;
+      lbitset_elt_free (elt);
+    }
+}
+
+
+/* Are all bits in an element zero?  */
+static inline bool
+lbitset_elt_zero_p (lbitset_elt *elt)
+{
+  for (int i = 0; i < LBITSET_ELT_WORDS; i++)
+    if (elt->words[i])
+      return false;
+  return true;
+}
+
+
+/* Link the bitset element into the current bitset linked list.  */
+static inline void
+lbitset_elt_link (bitset bset, lbitset_elt *elt)
+{
+  bitset_windex windex = elt->index;
+
+  lbitset_elt *current = bset->b.csize ? LBITSET_CURRENT (bset) : LBITSET_HEAD (bset);
+
+  /* If this is the first and only element, add it in.  */
+  if (LBITSET_HEAD (bset) == 0)
+    {
+      elt->next = elt->prev = 0;
+      LBITSET_HEAD (bset) = elt;
+      LBITSET_TAIL (bset) = elt;
+    }
+
+  /* If this index is less than that of the current element, it goes
+     somewhere before the current element.  */
+  else if (windex < bset->b.cindex)
+    {
+      lbitset_elt *ptr;
+      for (ptr = current;
+           ptr->prev && ptr->prev->index > windex; ptr = ptr->prev)
+        continue;
+
+      if (ptr->prev)
+        ptr->prev->next = elt;
+      else
+        LBITSET_HEAD (bset) = elt;
+
+      elt->prev = ptr->prev;
+      elt->next = ptr;
+      ptr->prev = elt;
+    }
+
+  /* Otherwise, it must go somewhere after the current element.  */
+  else
+    {
+      lbitset_elt *ptr;
+      for (ptr = current;
+           ptr->next && ptr->next->index < windex; ptr = ptr->next)
+        continue;
+
+      if (ptr->next)
+        ptr->next->prev = elt;
+      else
+        LBITSET_TAIL (bset) = elt;
+
+      elt->next = ptr->next;
+      elt->prev = ptr;
+      ptr->next = elt;
+    }
+
+  /* Set up so this is the first element searched.  */
+  bset->b.cindex = windex;
+  bset->b.csize = LBITSET_ELT_WORDS;
+  bset->b.cdata = elt->words;
+}
+
+
+static lbitset_elt *
+lbitset_elt_find (bitset bset, bitset_windex windex,
+                  enum lbitset_find_mode mode)
+{
+  lbitset_elt *current;
+
+  if (bset->b.csize)
+    {
+      current = LBITSET_CURRENT (bset);
+      /* Check if element is the cached element.  */
+      if ((windex - bset->b.cindex) < bset->b.csize)
+        return current;
+    }
+  else
+    {
+      current = LBITSET_HEAD (bset);
+    }
+
+  if (current)
+    {
+      lbitset_elt *elt;
+      if (windex < bset->b.cindex)
+        {
+          for (elt = current;
+               elt->prev && elt->index > windex; elt = elt->prev)
+            continue;
+        }
+      else
+        {
+          for (elt = current;
+               elt->next && (elt->index + LBITSET_ELT_WORDS - 1) < windex;
+               elt = elt->next)
+            continue;
+        }
+
+      /* ELT is the nearest to the one we want.  If it's not the one
+         we want, the one we want does not exist.  */
+      if (windex - elt->index < LBITSET_ELT_WORDS)
+        {
+          bset->b.cindex = elt->index;
+          bset->b.csize = LBITSET_ELT_WORDS;
+          bset->b.cdata = elt->words;
+          return elt;
+        }
+    }
+
+  switch (mode)
+    {
+    default:
+      abort ();
+
+    case LBITSET_FIND:
+      return 0;
+
+    case LBITSET_CREATE:
+      windex -= windex % LBITSET_ELT_WORDS;
+      lbitset_elt *elt = lbitset_elt_calloc ();
+      elt->index = windex;
+      lbitset_elt_link (bset, elt);
+      return elt;
+
+    case LBITSET_SUBST:
+      return &lbitset_zero_elts[0];
+    }
+}
+
+
+/* Weed out the zero elements from the list.  */
+static inline void
+lbitset_weed (bitset bset)
+{
+  lbitset_elt *next;
+  for (lbitset_elt *elt = LBITSET_HEAD (bset); elt; elt = next)
+    {
+      next = elt->next;
+      if (lbitset_elt_zero_p (elt))
+        lbitset_elt_unlink (bset, elt);
+    }
+}
+
+
+/* Set all bits in the bitset to zero.  */
+static void
+lbitset_zero (bitset bset)
+{
+  lbitset_elt *head = LBITSET_HEAD (bset);
+  if (!head)
+    return;
+
+  /* Clear a bitset by freeing the linked list at the head element.  */
+  lbitset_prune (bset, head);
+}
+
+
+/* Is DST == SRC?  */
+static inline bool
+lbitset_equal_p (bitset dst, bitset src)
+{
+  if (src == dst)
+    return true;
+
+  lbitset_weed (src);
+  lbitset_weed (dst);
+  lbitset_elt *selt;
+  lbitset_elt *delt;
+  for (selt = LBITSET_HEAD (src), delt = LBITSET_HEAD (dst);
+       selt && delt; selt = selt->next, delt = delt->next)
+    {
+      if (selt->index != delt->index)
+        return false;
+
+      for (int j = 0; j < LBITSET_ELT_WORDS; j++)
+        if (delt->words[j] != selt->words[j])
+          return false;
+    }
+  return !selt && !delt;
+}
+
+
+/* Copy bits from bitset SRC to bitset DST.  */
+static inline void
+lbitset_copy (bitset dst, bitset src)
+{
+  if (src == dst)
+    return;
+
+  lbitset_zero (dst);
+
+  lbitset_elt *head = LBITSET_HEAD (src);
+  if (!head)
+    return;
+
+  lbitset_elt *prev = 0;
+  lbitset_elt *tmp;
+  for (lbitset_elt *elt = head; elt; elt = elt->next)
+    {
+      tmp = lbitset_elt_alloc ();
+      tmp->index = elt->index;
+      tmp->prev = prev;
+      tmp->next = 0;
+      if (prev)
+        prev->next = tmp;
+      else
+        LBITSET_HEAD (dst) = tmp;
+      prev = tmp;
+
+      memcpy (tmp->words, elt->words, sizeof (elt->words));
+    }
+  LBITSET_TAIL (dst) = tmp;
+
+  dst->b.csize = LBITSET_ELT_WORDS;
+  dst->b.cdata = LBITSET_HEAD (dst)->words;
+  dst->b.cindex = LBITSET_HEAD (dst)->index;
+}
+
+
+/* Copy bits from bitset SRC to bitset DST.  Return true if
+   bitsets different.  */
+static inline bool
+lbitset_copy_cmp (bitset dst, bitset src)
+{
+  if (src == dst)
+    return false;
+
+  if (!LBITSET_HEAD (dst))
+    {
+      lbitset_copy (dst, src);
+      return LBITSET_HEAD (src) != 0;
+    }
+
+  if (lbitset_equal_p (dst, src))
+    return false;
+
+  lbitset_copy (dst, src);
+  return true;
+}
+
+
+static bitset_bindex
+lbitset_resize (bitset src, bitset_bindex size)
+{
+  BITSET_NBITS_ (src) = size;
+
+  /* Need to prune any excess bits.  FIXME.  */
+  return size;
+}
+
+/* Set bit BITNO in bitset DST.  */
+static void
+lbitset_set (bitset dst, bitset_bindex bitno)
+{
+  bitset_windex windex = bitno / BITSET_WORD_BITS;
+
+  lbitset_elt_find (dst, windex, LBITSET_CREATE);
+
+  dst->b.cdata[windex - dst->b.cindex] |=
+    (bitset_word) 1 << (bitno % BITSET_WORD_BITS);
+}
+
+
+/* Reset bit BITNO in bitset DST.  */
+static void
+lbitset_reset (bitset dst, bitset_bindex bitno)
+{
+  bitset_windex windex = bitno / BITSET_WORD_BITS;
+
+  if (!lbitset_elt_find (dst, windex, LBITSET_FIND))
+    return;
+
+  dst->b.cdata[windex - dst->b.cindex] &=
+    ~((bitset_word) 1 << (bitno % BITSET_WORD_BITS));
+
+  /* If all the data is zero, perhaps we should unlink it now...  */
+}
+
+
+/* Test bit BITNO in bitset SRC.  */
+static bool
+lbitset_test (bitset src, bitset_bindex bitno)
+{
+  bitset_windex windex = bitno / BITSET_WORD_BITS;
+
+  return (lbitset_elt_find (src, windex, LBITSET_FIND)
+          && ((src->b.cdata[windex - src->b.cindex]
+               >> (bitno % BITSET_WORD_BITS))
+              & 1));
+}
+
+
+static void
+lbitset_free (bitset bset)
+{
+  lbitset_zero (bset);
+}
+
+
+/* Find list of up to NUM bits set in BSET starting from and including
+ *NEXT and store in array LIST.  Return with actual number of bits
+ found and with *NEXT indicating where search stopped.  */
+static bitset_bindex
+lbitset_list_reverse (bitset bset, bitset_bindex *list,
+                      bitset_bindex num, bitset_bindex *next)
+{
+  lbitset_elt *elt = LBITSET_TAIL (bset);
+  if (!elt)
+    return 0;
+
+  bitset_bindex n_bits = (elt->index + LBITSET_ELT_WORDS) * BITSET_WORD_BITS;
+  bitset_bindex rbitno = *next;
+
+  if (rbitno >= n_bits)
+    return 0;
+
+  bitset_bindex bitno = n_bits - (rbitno + 1);
+
+  bitset_windex windex = bitno / BITSET_WORD_BITS;
+
+  /* Skip back to starting element.  */
+  for (; elt && elt->index > windex; elt = elt->prev)
+    continue;
+
+  if (!elt)
+    return 0;
+
+  unsigned bcount;
+  if (windex >= elt->index + LBITSET_ELT_WORDS)
+    {
+      /* We are trying to start in no-mans land so start
+         at end of current elt.  */
+      bcount = BITSET_WORD_BITS - 1;
+      windex = elt->index + LBITSET_ELT_WORDS - 1;
+    }
+  else
+    {
+      bcount = bitno % BITSET_WORD_BITS;
+    }
+
+  bitset_bindex count = 0;
+  bitset_bindex boffset = windex * BITSET_WORD_BITS;
+
+  /* If num is 1, we could speed things up with a binary search
+     of the word of interest.  */
+
+  while (elt)
+    {
+      bitset_word *srcp = elt->words;
+
+      for (; (windex - elt->index) < LBITSET_ELT_WORDS;
+           windex--, boffset -= BITSET_WORD_BITS,
+             bcount = BITSET_WORD_BITS - 1)
+        {
+          bitset_word word =
+            srcp[windex - elt->index] << (BITSET_WORD_BITS - 1 - bcount);
+
+          for (; word; bcount--)
+            {
+              if (word & BITSET_MSB)
+                {
+                  list[count++] = boffset + bcount;
+                  if (count >= num)
+                    {
+                      *next = n_bits - (boffset + bcount);
+                      return count;
+                    }
+                }
+              word <<= 1;
+            }
+        }
+
+      elt = elt->prev;
+      if (elt)
+        {
+          windex = elt->index + LBITSET_ELT_WORDS - 1;
+          boffset = windex * BITSET_WORD_BITS;
+        }
+    }
+
+  *next = n_bits - (boffset + 1);
+  return count;
+}
+
+
+/* Find list of up to NUM bits set in BSET starting from and including
+   *NEXT and store in array LIST.  Return with actual number of bits
+   found and with *NEXT indicating where search stopped.  */
+static bitset_bindex
+lbitset_list (bitset bset, bitset_bindex *list,
+              bitset_bindex num, bitset_bindex *next)
+{
+  lbitset_elt *head = LBITSET_HEAD (bset);
+  if (!head)
+    return 0;
+
+  bitset_windex windex;
+  lbitset_elt *elt;
+
+  bitset_bindex bitno = *next;
+  bitset_bindex count = 0;
+
+  if (!bitno)
+    {
+      /* This is the most common case.  */
+
+      /* Start with the first element.  */
+      elt = head;
+      windex = elt->index;
+      bitno = windex * BITSET_WORD_BITS;
+    }
+  else
+    {
+      windex = bitno / BITSET_WORD_BITS;
+
+      /* Skip to starting element.  */
+      for (elt = head;
+           elt && (elt->index + LBITSET_ELT_WORDS - 1) < windex;
+           elt = elt->next)
+        continue;
+
+      if (!elt)
+        return 0;
+
+      if (windex < elt->index)
+        {
+          windex = elt->index;
+          bitno = windex * BITSET_WORD_BITS;
+        }
+      else
+        {
+          bitset_word *srcp = elt->words;
+
+          /* We are starting within an element.  */
+
+          for (; (windex - elt->index) < LBITSET_ELT_WORDS; windex++)
+            {
+              bitset_word word = srcp[windex - elt->index] >> (bitno % BITSET_WORD_BITS);
+
+              for (; word; bitno++)
+                {
+                  if (word & 1)
+                    {
+                      list[count++] = bitno;
+                      if (count >= num)
+                        {
+                          *next = bitno + 1;
+                          return count;
+                        }
+                    }
+                  word >>= 1;
+                }
+              bitno = (windex + 1) * BITSET_WORD_BITS;
+            }
+
+          elt = elt->next;
+          if (elt)
+            {
+              windex = elt->index;
+              bitno = windex * BITSET_WORD_BITS;
+            }
+        }
+    }
+
+
+  /* If num is 1, we could speed things up with a binary search
+     of the word of interest.  */
+
+  while (elt)
+    {
+      bitset_word *srcp = elt->words;
+
+      if ((count + LBITSET_ELT_BITS) < num)
+        {
+          /* The coast is clear, plant boot!  */
+
+#if LBITSET_ELT_WORDS == 2
+          bitset_word word = srcp[0];
+          if (word)
+            {
+              if (!(word & 0xffff))
+                {
+                  word >>= 16;
+                  bitno += 16;
+                }
+              if (!(word & 0xff))
+                {
+                  word >>= 8;
+                  bitno += 8;
+                }
+              for (; word; bitno++)
+                {
+                  if (word & 1)
+                    list[count++] = bitno;
+                  word >>= 1;
+                }
+            }
+          windex++;
+          bitno = windex * BITSET_WORD_BITS;
+
+          word = srcp[1];
+          if (word)
+            {
+              if (!(word & 0xffff))
+                {
+                  word >>= 16;
+                  bitno += 16;
+                }
+              for (; word; bitno++)
+                {
+                  if (word & 1)
+                    list[count++] = bitno;
+                  word >>= 1;
+                }
+            }
+          windex++;
+          bitno = windex * BITSET_WORD_BITS;
+#else
+          for (int i = 0; i < LBITSET_ELT_WORDS; i++)
+            {
+              bitset_word word = srcp[i];
+              if (word)
+                {
+                  if (!(word & 0xffff))
+                    {
+                      word >>= 16;
+                      bitno += 16;
+                    }
+                  if (!(word & 0xff))
+                    {
+                      word >>= 8;
+                      bitno += 8;
+                    }
+                  for (; word; bitno++)
+                    {
+                      if (word & 1)
+                        list[count++] = bitno;
+                      word >>= 1;
+                    }
+                }
+              windex++;
+              bitno = windex * BITSET_WORD_BITS;
+            }
+#endif
+        }
+      else
+        {
+          /* Tread more carefully since we need to check
+             if array overflows.  */
+
+          for (int i = 0; i < LBITSET_ELT_WORDS; i++)
+            {
+              for (bitset_word word = srcp[i]; word; bitno++)
+                {
+                  if (word & 1)
+                    {
+                      list[count++] = bitno;
+                      if (count >= num)
+                        {
+                          *next = bitno + 1;
+                          return count;
+                        }
+                    }
+                  word >>= 1;
+                }
+              windex++;
+              bitno = windex * BITSET_WORD_BITS;
+            }
+        }
+
+      elt = elt->next;
+      if (elt)
+        {
+          windex = elt->index;
+          bitno = windex * BITSET_WORD_BITS;
+        }
+    }
+
+  *next = bitno;
+  return count;
+}
+
+
+static bool
+lbitset_empty_p (bitset dst)
+{
+  lbitset_elt *elt;
+  lbitset_elt *next;
+
+  for (elt = LBITSET_HEAD (dst); elt; elt = next)
+    {
+      next = elt->next;
+      if (!lbitset_elt_zero_p (elt))
+        return false;
+      /* Weed as we go.  */
+      lbitset_elt_unlink (dst, elt);
+    }
+
+  return true;
+}
+
+
+/* Ensure that any unused bits within the last element are clear.  */
+static inline void
+lbitset_unused_clear (bitset dst)
+{
+  bitset_bindex n_bits = BITSET_SIZE_ (dst);
+  unsigned last_bit = n_bits % LBITSET_ELT_BITS;
+
+  if (last_bit)
+    {
+      lbitset_elt *elt = LBITSET_TAIL (dst);
+      bitset_word *srcp = elt->words;
+      bitset_windex windex = n_bits / BITSET_WORD_BITS;
+
+      srcp[windex - elt->index] &= ((bitset_word) 1 << last_bit) - 1;
+      windex++;
+
+      for (; (windex - elt->index) < LBITSET_ELT_WORDS; windex++)
+        srcp[windex - elt->index] = 0;
+    }
+}
+
+
+static void
+lbitset_ones (bitset dst)
+{
+  /* This is a decidedly unfriendly operation for a linked list
+     bitset!  It makes a sparse bitset become dense.  An alternative
+     is to have a flag that indicates that the bitset stores the
+     complement of what it indicates.  */
+
+  bitset_windex windex
+    = (BITSET_SIZE_ (dst) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS;
+
+  for (bitset_windex i = 0; i < windex; i += LBITSET_ELT_WORDS)
+    {
+      /* Create new elements if they cannot be found.  */
+      lbitset_elt *elt = lbitset_elt_find (dst, i, LBITSET_CREATE);
+      memset (elt->words, -1, sizeof (elt->words));
+    }
+
+  lbitset_unused_clear (dst);
+}
+
+
+static void
+lbitset_not (bitset dst, bitset src)
+{
+  bitset_windex windex
+    = (BITSET_SIZE_ (dst) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS;
+
+  for (bitset_windex i = 0; i < windex; i += LBITSET_ELT_WORDS)
+    {
+      /* Create new elements for dst if they cannot be found
+         or substitute zero elements if src elements not found.  */
+      lbitset_elt *selt = lbitset_elt_find (src, i, LBITSET_SUBST);
+      lbitset_elt *delt = lbitset_elt_find (dst, i, LBITSET_CREATE);
+
+      for (unsigned j = 0; j < LBITSET_ELT_WORDS; j++)
+        delt->words[j] = ~selt->words[j];
+    }
+  lbitset_unused_clear (dst);
+  lbitset_weed (dst);
+}
+
+
+/* Is DST == DST | SRC?  */
+static bool
+lbitset_subset_p (bitset dst, bitset src)
+{
+  for (lbitset_elt *selt = LBITSET_HEAD (src), *delt = LBITSET_HEAD (dst);
+       selt || delt; selt = selt->next, delt = delt->next)
+    {
+      if (!selt)
+        selt = &lbitset_zero_elts[0];
+      else if (!delt)
+        delt = &lbitset_zero_elts[0];
+      else if (selt->index != delt->index)
+        {
+          if (selt->index < delt->index)
+            {
+              lbitset_zero_elts[2].next = delt;
+              delt = &lbitset_zero_elts[2];
+            }
+          else
+            {
+              lbitset_zero_elts[1].next = selt;
+              selt = &lbitset_zero_elts[1];
+            }
+        }
+
+      for (unsigned j = 0; j < LBITSET_ELT_WORDS; j++)
+        if (delt->words[j] != (selt->words[j] | delt->words[j]))
+          return false;
+    }
+  return true;
+}
+
+
+/* Is DST & SRC == 0?  */
+static bool
+lbitset_disjoint_p (bitset dst, bitset src)
+{
+  for (lbitset_elt *selt = LBITSET_HEAD (src), *delt = LBITSET_HEAD (dst);
+       selt && delt; selt = selt->next, delt = delt->next)
+    {
+      if (selt->index != delt->index)
+        {
+          if (selt->index < delt->index)
+            {
+              lbitset_zero_elts[2].next = delt;
+              delt = &lbitset_zero_elts[2];
+            }
+          else
+            {
+              lbitset_zero_elts[1].next = selt;
+              selt = &lbitset_zero_elts[1];
+            }
+          /* Since the elements are different, there is no
+             intersection of these elements.  */
+          continue;
+        }
+
+      for (unsigned j = 0; j < LBITSET_ELT_WORDS; j++)
+        if (selt->words[j] & delt->words[j])
+          return false;
+    }
+  return true;
+}
+
+
+static bool
+lbitset_op3_cmp (bitset dst, bitset src1, bitset src2, enum bitset_ops op)
+{
+  lbitset_elt *selt1 = LBITSET_HEAD (src1);
+  lbitset_elt *selt2 = LBITSET_HEAD (src2);
+  lbitset_elt *delt = LBITSET_HEAD (dst);
+  bool changed = false;
+
+  LBITSET_HEAD (dst) = 0;
+  dst->b.csize = 0;
+
+  bitset_windex windex1 = (selt1) ? selt1->index : BITSET_WINDEX_MAX;
+  bitset_windex windex2 = (selt2) ? selt2->index : BITSET_WINDEX_MAX;
+
+  while (selt1 || selt2)
+    {
+      bitset_windex windex;
+      lbitset_elt *stmp1;
+      lbitset_elt *stmp2;
+
+      /* Figure out whether we need to substitute zero elements for
+         missing links.  */
+      if (windex1 == windex2)
+        {
+          windex = windex1;
+          stmp1 = selt1;
+          stmp2 = selt2;
+          selt1 = selt1->next;
+          windex1 = (selt1) ? selt1->index : BITSET_WINDEX_MAX;
+          selt2 = selt2->next;
+          windex2 = (selt2) ? selt2->index : BITSET_WINDEX_MAX;
+        }
+      else if (windex1 < windex2)
+        {
+          windex = windex1;
+          stmp1 = selt1;
+          stmp2 = &lbitset_zero_elts[0];
+          selt1 = selt1->next;
+          windex1 = (selt1) ? selt1->index : BITSET_WINDEX_MAX;
+        }
+      else
+        {
+          windex = windex2;
+          stmp1 = &lbitset_zero_elts[0];
+          stmp2 = selt2;
+          selt2 = selt2->next;
+          windex2 = (selt2) ? selt2->index : BITSET_WINDEX_MAX;
+        }
+
+      /* Find the appropriate element from DST.  Begin by discarding
+         elements that we've skipped.  */
+      lbitset_elt *dtmp;
+      while (delt && delt->index < windex)
+        {
+          changed = true;
+          dtmp = delt;
+          delt = delt->next;
+          lbitset_elt_free (dtmp);
+        }
+      if (delt && delt->index == windex)
+        {
+          dtmp = delt;
+          delt = delt->next;
+        }
+      else
+        dtmp = lbitset_elt_calloc ();
+
+      /* Do the operation, and if any bits are set, link it into the
+         linked list.  */
+      bitset_word *srcp1 = stmp1->words;
+      bitset_word *srcp2 = stmp2->words;
+      bitset_word *dstp = dtmp->words;
+      switch (op)
+        {
+        default:
+          abort ();
+
+        case BITSET_OP_OR:
+          for (unsigned i = 0; i < LBITSET_ELT_WORDS; i++, dstp++)
+            {
+              bitset_word tmp = *srcp1++ | *srcp2++;
+
+              if (*dstp != tmp)
+                {
+                  changed = true;
+                  *dstp = tmp;
+                }
+            }
+          break;
+
+        case BITSET_OP_AND:
+          for (unsigned i = 0; i < LBITSET_ELT_WORDS; i++, dstp++)
+            {
+              bitset_word tmp = *srcp1++ & *srcp2++;
+
+              if (*dstp != tmp)
+                {
+                  changed = true;
+                  *dstp = tmp;
+                }
+            }
+          break;
+
+        case BITSET_OP_XOR:
+          for (unsigned i = 0; i < LBITSET_ELT_WORDS; i++, dstp++)
+            {
+              bitset_word tmp = *srcp1++ ^ *srcp2++;
+
+              if (*dstp != tmp)
+                {
+                  changed = true;
+                  *dstp = tmp;
+                }
+            }
+          break;
+
+        case BITSET_OP_ANDN:
+          for (unsigned i = 0; i < LBITSET_ELT_WORDS; i++, dstp++)
+            {
+              bitset_word tmp = *srcp1++ & ~(*srcp2++);
+
+              if (*dstp != tmp)
+                {
+                  changed = true;
+                  *dstp = tmp;
+                }
+            }
+          break;
+        }
+
+      if (!lbitset_elt_zero_p (dtmp))
+        {
+          dtmp->index = windex;
+          /* Perhaps this could be optimised...  */
+          lbitset_elt_link (dst, dtmp);
+        }
+      else
+        {
+          lbitset_elt_free (dtmp);
+        }
+    }
+
+  /* If we have elements of DST left over, free them all.  */
+  if (delt)
+    {
+      changed = true;
+      lbitset_prune (dst, delt);
+    }
+
+  return changed;
+}
+
+
+static bool
+lbitset_and_cmp (bitset dst, bitset src1, bitset src2)
+{
+  lbitset_elt *selt1 = LBITSET_HEAD (src1);
+  lbitset_elt *selt2 = LBITSET_HEAD (src2);
+
+  if (!selt2)
+    {
+      lbitset_weed (dst);
+      bool changed = !LBITSET_HEAD (dst);
+      lbitset_zero (dst);
+      return changed;
+    }
+  else if (!selt1)
+    {
+      lbitset_weed (dst);
+      bool changed = !LBITSET_HEAD (dst);
+      lbitset_zero (dst);
+      return changed;
+    }
+  else
+    return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_AND);
+}
+
+
+static void
+lbitset_and (bitset dst, bitset src1, bitset src2)
+{
+  lbitset_and_cmp (dst, src1, src2);
+}
+
+
+static bool
+lbitset_andn_cmp (bitset dst, bitset src1, bitset src2)
+{
+  lbitset_elt *selt1 = LBITSET_HEAD (src1);
+  lbitset_elt *selt2 = LBITSET_HEAD (src2);
+
+  if (!selt2)
+    {
+      return lbitset_copy_cmp (dst, src1);
+    }
+  else if (!selt1)
+    {
+      lbitset_weed (dst);
+      bool changed = !LBITSET_HEAD (dst);
+      lbitset_zero (dst);
+      return changed;
+    }
+  else
+    return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_ANDN);
+}
+
+
+static void
+lbitset_andn (bitset dst, bitset src1, bitset src2)
+{
+  lbitset_andn_cmp (dst, src1, src2);
+}
+
+
+static bool
+lbitset_or_cmp (bitset dst, bitset src1, bitset src2)
+{
+  lbitset_elt *selt1 = LBITSET_HEAD (src1);
+  lbitset_elt *selt2 = LBITSET_HEAD (src2);
+
+  if (!selt2)
+    return lbitset_copy_cmp (dst, src1);
+  else if (!selt1)
+    return lbitset_copy_cmp (dst, src2);
+  else
+    return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_OR);
+}
+
+
+static void
+lbitset_or (bitset dst, bitset src1, bitset src2)
+{
+  lbitset_or_cmp (dst, src1, src2);
+}
+
+
+static bool
+lbitset_xor_cmp (bitset dst, bitset src1, bitset src2)
+{
+  lbitset_elt *selt1 = LBITSET_HEAD (src1);
+  lbitset_elt *selt2 = LBITSET_HEAD (src2);
+
+  if (!selt2)
+    return lbitset_copy_cmp (dst, src1);
+  else if (!selt1)
+    return lbitset_copy_cmp (dst, src2);
+  else
+    return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_XOR);
+}
+
+
+static void
+lbitset_xor (bitset dst, bitset src1, bitset src2)
+{
+  lbitset_xor_cmp (dst, src1, src2);
+}
+
+
+
+/* Vector of operations for linked-list bitsets.  */
+struct bitset_vtable lbitset_vtable = {
+  lbitset_set,
+  lbitset_reset,
+  bitset_toggle_,
+  lbitset_test,
+  lbitset_resize,
+  bitset_size_,
+  bitset_count_,
+  lbitset_empty_p,
+  lbitset_ones,
+  lbitset_zero,
+  lbitset_copy,
+  lbitset_disjoint_p,
+  lbitset_equal_p,
+  lbitset_not,
+  lbitset_subset_p,
+  lbitset_and,
+  lbitset_and_cmp,
+  lbitset_andn,
+  lbitset_andn_cmp,
+  lbitset_or,
+  lbitset_or_cmp,
+  lbitset_xor,
+  lbitset_xor_cmp,
+  bitset_and_or_,
+  bitset_and_or_cmp_,
+  bitset_andn_or_,
+  bitset_andn_or_cmp_,
+  bitset_or_and_,
+  bitset_or_and_cmp_,
+  lbitset_list,
+  lbitset_list_reverse,
+  lbitset_free,
+  BITSET_LIST
+};
+
+
+/* Return size of initial structure.  */
+size_t
+lbitset_bytes (bitset_bindex n_bits ATTRIBUTE_UNUSED)
+{
+  return sizeof (struct lbitset_struct);
+}
+
+
+/* Initialize a bitset.  */
+bitset
+lbitset_init (bitset bset, bitset_bindex n_bits ATTRIBUTE_UNUSED)
+{
+  BITSET_NBITS_ (bset) = n_bits;
+  bset->b.vtable = &lbitset_vtable;
+  return bset;
+}
+
+
+void
+lbitset_release_memory (void)
+{
+  lbitset_free_list = 0;
+  if (lbitset_obstack_init)
+    {
+      lbitset_obstack_init = false;
+      obstack_free (&lbitset_obstack, NULL);
+    }
+}
+
+
+/* Function to be called from debugger to debug lbitset.  */
+void
+debug_lbitset (bitset bset)
+{
+  if (!bset)
+    return;
+
+  for (lbitset_elt *elt = LBITSET_HEAD (bset); elt; elt = elt->next)
+    {
+      fprintf (stderr, "Elt %lu\n", (unsigned long) elt->index);
+      for (unsigned i = 0; i < LBITSET_ELT_WORDS; i++)
+        {
+          bitset_word word = elt->words[i];
+
+          fprintf (stderr, "  Word %u:", i);
+          for (unsigned j = 0; j < LBITSET_WORD_BITS; j++)
+            if ((word & ((bitset_word) 1 << j)))
+              fprintf (stderr, " %u", j);
+          fprintf (stderr, "\n");
+        }
+    }
+}
diff --git a/contrib/tools/bison/lib/bitset/list.h b/contrib/tools/bison/lib/bitset/list.h
new file mode 100644
index 0000000000..a0fc09f8c6
--- /dev/null
+++ b/contrib/tools/bison/lib/bitset/list.h
@@ -0,0 +1,32 @@
+/* Functions to support lbitsets.
+
+   Copyright (C) 2002, 2004, 2009-2015, 2018-2019 Free Software Foundation,
+   Inc.
+
+   Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz).
+
+   This program is free software: you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation, either version 3 of the License, or
+   (at your option) any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
+
+#ifndef _BITSET_LIST_H
+#define _BITSET_LIST_H
+
+#include "bitset.h"
+
+size_t lbitset_bytes (bitset_bindex);
+
+bitset lbitset_init (bitset, bitset_bindex);
+
+void lbitset_release_memory (void);
+
+#endif
diff --git a/contrib/tools/bison/lib/bitset/stats.c b/contrib/tools/bison/lib/bitset/stats.c
new file mode 100644
index 0000000000..da73cdcac5
--- /dev/null
+++ b/contrib/tools/bison/lib/bitset/stats.c
@@ -0,0 +1,730 @@
+/* Bitset statistics.
+
+   Copyright (C) 2002-2006, 2009-2015, 2018-2019 Free Software Foundation, Inc.
+
+   Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz).
+
+   This program is free software: you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation, either version 3 of the License, or
+   (at your option) any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
+
+/* This file is a wrapper bitset implementation for the other bitset
+   implementations.  It provides bitset compatibility checking and
+   statistics gathering without having to instrument the bitset
+   implementations.  When statistics gathering is enabled, the bitset
+   operations get vectored through here and we then call the appropriate
+   routines.  */
+
+#include <config.h>
+
+#include "bitset/stats.h"
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "gettext.h"
+#define _(Msgid)  gettext (Msgid)
+
+#include "bitset/array.h"
+#include "bitset/base.h"
+#include "bitset/list.h"
+#include "bitset/table.h"
+#include "bitset/vector.h"
+
+/* Configuration macros.  */
+#define BITSET_STATS_FILE "bitset.dat"
+#define BITSET_LOG_COUNT_BINS 10
+#define BITSET_LOG_SIZE_BINS  16
+#define BITSET_DENSITY_BINS  20
+
+
+/* Accessor macros.  */
+#define BITSET_STATS_ALLOCS_INC(TYPE)                   \
+    bitset_stats_info->types[(TYPE)].allocs++
+#define BITSET_STATS_FREES_INC(BSET)                    \
+    bitset_stats_info->types[BITSET_TYPE_ (BSET)].frees++
+#define BITSET_STATS_SETS_INC(BSET)                     \
+    bitset_stats_info->types[BITSET_TYPE_ (BSET)].sets++
+#define BITSET_STATS_CACHE_SETS_INC(BSET)               \
+    bitset_stats_info->types[BITSET_TYPE_ (BSET)].cache_sets++
+#define BITSET_STATS_RESETS_INC(BSET)                   \
+    bitset_stats_info->types[BITSET_TYPE_ (BSET)].resets++
+#define BITSET_STATS_CACHE_RESETS_INC(BSET)             \
+    bitset_stats_info->types[BITSET_TYPE_ (BSET)].cache_resets++
+#define BITSET_STATS_TESTS_INC(BSET)                    \
+    bitset_stats_info->types[BITSET_TYPE_ (BSET)].tests++
+#define BITSET_STATS_CACHE_TESTS_INC(BSET)              \
+    bitset_stats_info->types[BITSET_TYPE_ (BSET)].cache_tests++
+#define BITSET_STATS_LISTS_INC(BSET)                    \
+    bitset_stats_info->types[BITSET_TYPE_ (BSET)].lists++
+#define BITSET_STATS_LIST_COUNTS_INC(BSET, I)           \
+    bitset_stats_info->types[BITSET_TYPE_ (BSET)].list_counts[(I)]++
+#define BITSET_STATS_LIST_SIZES_INC(BSET, I)            \
+    bitset_stats_info->types[BITSET_TYPE_ (BSET)].list_sizes[(I)]++
+#define BITSET_STATS_LIST_DENSITY_INC(BSET, I)          \
+    bitset_stats_info->types[BITSET_TYPE_ (BSET)].list_density[(I)]++
+
+
+struct bitset_type_info_struct
+{
+  unsigned allocs;
+  unsigned frees;
+  unsigned lists;
+  unsigned sets;
+  unsigned cache_sets;
+  unsigned resets;
+  unsigned cache_resets;
+  unsigned tests;
+  unsigned cache_tests;
+  unsigned list_counts[BITSET_LOG_COUNT_BINS];
+  unsigned list_sizes[BITSET_LOG_SIZE_BINS];
+  unsigned list_density[BITSET_DENSITY_BINS];
+};
+
+struct bitset_stats_info_struct
+{
+  unsigned runs;
+  struct bitset_type_info_struct types[BITSET_TYPE_NUM];
+};
+
+
+struct bitset_stats_info_struct bitset_stats_info_data;
+struct bitset_stats_info_struct *bitset_stats_info;
+bool bitset_stats_enabled = false;
+
+
+/* Print a percentage histogram with message MSG to FILE.  */
+static void
+bitset_percent_histogram_print (FILE *file, const char *name, const char *msg,
+                                unsigned n_bins, unsigned *bins)
+{
+  unsigned total = 0;
+  for (unsigned i = 0; i < n_bins; i++)
+    total += bins[i];
+
+  if (!total)
+    return;
+
+  fprintf (file, "%s %s", name, msg);
+  for (unsigned i = 0; i < n_bins; i++)
+    fprintf (file, "%.0f-%.0f%%\t%8u (%5.1f%%)\n",
+             i * 100.0 / n_bins,
+             (i + 1) * 100.0 / n_bins, bins[i],
+             (100.0 * bins[i]) / total);
+}
+
+
+/* Print a log histogram with message MSG to FILE.  */
+static void
+bitset_log_histogram_print (FILE *file, const char *name, const char *msg,
+                            unsigned n_bins, unsigned *bins)
+{
+  unsigned total = 0;
+  for (unsigned i = 0; i < n_bins; i++)
+    total += bins[i];
+
+  if (!total)
+    return;
+
+  /* Determine number of useful bins.  */
+  {
+    unsigned i;
+    for (i = n_bins; i > 3 && ! bins[i - 1]; i--)
+      continue;
+    n_bins = i;
+  }
+
+  /* 2 * ceil (log10 (2) * (N - 1)) + 1.  */
+  unsigned max_width = 2 * (unsigned) (0.30103 * (n_bins - 1) + 0.9999) + 1;
+
+  fprintf (file, "%s %s", name, msg);
+  {
+    unsigned i;
+    for (i = 0; i < 2; i++)
+      fprintf (file, "%*d\t%8u (%5.1f%%)\n",
+               max_width, i, bins[i], 100.0 * bins[i] / total);
+
+    for (; i < n_bins; i++)
+      fprintf (file, "%*lu-%lu\t%8u (%5.1f%%)\n",
+               max_width - ((unsigned) (0.30103 * (i) + 0.9999) + 1),
+               1UL << (i - 1),
+               (1UL << i) - 1,
+               bins[i],
+               (100.0 * bins[i]) / total);
+  }
+}
+
+
+/* Print bitset statistics to FILE.  */
+static void
+bitset_stats_print_1 (FILE *file, const char *name,
+                      struct bitset_type_info_struct *stats)
+{
+  if (!stats)
+    return;
+
+  fprintf (file, "%s:\n", name);
+  fprintf (file, _("%u bitset_allocs, %u freed (%.2f%%).\n"),
+           stats->allocs, stats->frees,
+           stats->allocs ? 100.0 * stats->frees / stats->allocs : 0);
+  fprintf (file, _("%u bitset_sets, %u cached (%.2f%%)\n"),
+           stats->sets, stats->cache_sets,
+           stats->sets ? 100.0 * stats->cache_sets / stats->sets : 0);
+  fprintf (file, _("%u bitset_resets, %u cached (%.2f%%)\n"),
+           stats->resets, stats->cache_resets,
+           stats->resets ? 100.0 * stats->cache_resets / stats->resets : 0);
+  fprintf (file, _("%u bitset_tests, %u cached (%.2f%%)\n"),
+           stats->tests, stats->cache_tests,
+           stats->tests ? 100.0 * stats->cache_tests / stats->tests : 0);
+
+  fprintf (file, _("%u bitset_lists\n"), stats->lists);
+
+  bitset_log_histogram_print (file, name, _("count log histogram\n"),
+                              BITSET_LOG_COUNT_BINS, stats->list_counts);
+
+  bitset_log_histogram_print (file, name, _("size log histogram\n"),
+                              BITSET_LOG_SIZE_BINS, stats->list_sizes);
+
+  bitset_percent_histogram_print (file, name, _("density histogram\n"),
+                                  BITSET_DENSITY_BINS, stats->list_density);
+}
+
+
+/* Print all bitset statistics to FILE.  */
+static void
+bitset_stats_print (FILE *file, bool verbose ATTRIBUTE_UNUSED)
+{
+  if (!bitset_stats_info)
+    return;
+
+  fprintf (file, _("Bitset statistics:\n\n"));
+
+  if (bitset_stats_info->runs > 1)
+    fprintf (file, _("Accumulated runs = %u\n"), bitset_stats_info->runs);
+
+  for (int i = 0; i < BITSET_TYPE_NUM; i++)
+    bitset_stats_print_1 (file, bitset_type_names[i],
+                          &bitset_stats_info->types[i]);
+}
+
+
+/* Initialise bitset statistics logging.  */
+void
+bitset_stats_enable (void)
+{
+  if (!bitset_stats_info)
+    bitset_stats_info = &bitset_stats_info_data;
+  bitset_stats_enabled = true;
+}
+
+
+void
+bitset_stats_disable (void)
+{
+  bitset_stats_enabled = false;
+}
+
+
+/* Read bitset statistics file.  */
+void
+bitset_stats_read (const char *file_name)
+{
+  if (!bitset_stats_info)
+    return;
+
+  if (!file_name)
+    file_name = BITSET_STATS_FILE;
+
+  FILE *file = fopen (file_name, "r");
+  if (file)
+    {
+      if (fread (&bitset_stats_info_data, sizeof (bitset_stats_info_data),
+                 1, file) != 1)
+        {
+          if (ferror (file))
+            perror (_("cannot read stats file"));
+          else
+            fprintf (stderr, _("bad stats file size\n"));
+        }
+      if (fclose (file) != 0)
+        perror (_("cannot read stats file"));
+    }
+  bitset_stats_info_data.runs++;
+}
+
+
+/* Write bitset statistics file.  */
+void
+bitset_stats_write (const char *file_name)
+{
+  if (!bitset_stats_info)
+    return;
+
+  if (!file_name)
+    file_name = BITSET_STATS_FILE;
+
+  FILE *file = fopen (file_name, "w");
+  if (file)
+    {
+      if (fwrite (&bitset_stats_info_data, sizeof (bitset_stats_info_data),
+                  1, file) != 1)
+        perror (_("cannot write stats file"));
+      if (fclose (file) != 0)
+        perror (_("cannot write stats file"));
+    }
+  else
+    perror (_("cannot open stats file for writing"));
+}
+
+
+/* Dump bitset statistics to FILE.  */
+void
+bitset_stats_dump (FILE *file)
+{
+  bitset_stats_print (file, false);
+}
+
+
+/* Function to be called from debugger to print bitset stats.  */
+void
+debug_bitset_stats (void)
+{
+  bitset_stats_print (stderr, true);
+}
+
+
+static void
+bitset_stats_set (bitset dst, bitset_bindex bitno)
+{
+  bitset bset = dst->s.bset;
+  bitset_windex wordno = bitno / BITSET_WORD_BITS;
+  bitset_windex offset = wordno - bset->b.cindex;
+
+  BITSET_STATS_SETS_INC (bset);
+
+  if (offset < bset->b.csize)
+    {
+      bset->b.cdata[offset] |= (bitset_word) 1 << (bitno % BITSET_WORD_BITS);
+      BITSET_STATS_CACHE_SETS_INC (bset);
+    }
+  else
+    BITSET_SET_ (bset, bitno);
+}
+
+
+static void
+bitset_stats_reset (bitset dst, bitset_bindex bitno)
+{
+  bitset bset = dst->s.bset;
+  bitset_windex wordno = bitno / BITSET_WORD_BITS;
+  bitset_windex offset = wordno - bset->b.cindex;
+
+  BITSET_STATS_RESETS_INC (bset);
+
+  if (offset < bset->b.csize)
+    {
+      bset->b.cdata[offset] &=
+        ~((bitset_word) 1 << (bitno % BITSET_WORD_BITS));
+      BITSET_STATS_CACHE_RESETS_INC (bset);
+    }
+  else
+    BITSET_RESET_ (bset, bitno);
+}
+
+
+static bool
+bitset_stats_toggle (bitset src, bitset_bindex bitno)
+{
+  return BITSET_TOGGLE_ (src->s.bset, bitno);
+}
+
+
+static bool
+bitset_stats_test (bitset src, bitset_bindex bitno)
+{
+  bitset bset = src->s.bset;
+  bitset_windex wordno = bitno / BITSET_WORD_BITS;
+  bitset_windex offset = wordno - bset->b.cindex;
+
+  BITSET_STATS_TESTS_INC (bset);
+
+  if (offset < bset->b.csize)
+    {
+      BITSET_STATS_CACHE_TESTS_INC (bset);
+      return (bset->b.cdata[offset] >> (bitno % BITSET_WORD_BITS)) & 1;
+    }
+  else
+    return BITSET_TEST_ (bset, bitno);
+}
+
+
+static bitset_bindex
+bitset_stats_resize (bitset src, bitset_bindex size)
+{
+  return BITSET_RESIZE_ (src->s.bset, size);
+}
+
+
+static bitset_bindex
+bitset_stats_size (bitset src)
+{
+  return BITSET_SIZE_ (src->s.bset);
+}
+
+
+static bitset_bindex
+bitset_stats_count (bitset src)
+{
+  return BITSET_COUNT_ (src->s.bset);
+}
+
+
+static bool
+bitset_stats_empty_p (bitset dst)
+{
+  return BITSET_EMPTY_P_ (dst->s.bset);
+}
+
+
+static void
+bitset_stats_ones (bitset dst)
+{
+  BITSET_ONES_ (dst->s.bset);
+}
+
+
+static void
+bitset_stats_zero (bitset dst)
+{
+  BITSET_ZERO_ (dst->s.bset);
+}
+
+
+static void
+bitset_stats_copy (bitset dst, bitset src)
+{
+  BITSET_CHECK2_ (dst, src);
+  BITSET_COPY_ (dst->s.bset, src->s.bset);
+}
+
+
+static bool
+bitset_stats_disjoint_p (bitset dst, bitset src)
+{
+  BITSET_CHECK2_ (dst, src);
+  return BITSET_DISJOINT_P_ (dst->s.bset, src->s.bset);
+}
+
+
+static bool
+bitset_stats_equal_p (bitset dst, bitset src)
+{
+  BITSET_CHECK2_ (dst, src);
+  return BITSET_EQUAL_P_ (dst->s.bset, src->s.bset);
+}
+
+
+static void
+bitset_stats_not (bitset dst, bitset src)
+{
+  BITSET_CHECK2_ (dst, src);
+  BITSET_NOT_ (dst->s.bset, src->s.bset);
+}
+
+
+static bool
+bitset_stats_subset_p (bitset dst, bitset src)
+{
+  BITSET_CHECK2_ (dst, src);
+  return BITSET_SUBSET_P_ (dst->s.bset, src->s.bset);
+}
+
+
+static void
+bitset_stats_and (bitset dst, bitset src1, bitset src2)
+{
+  BITSET_CHECK3_ (dst, src1, src2);
+  BITSET_AND_ (dst->s.bset, src1->s.bset, src2->s.bset);
+}
+
+
+static bool
+bitset_stats_and_cmp (bitset dst, bitset src1, bitset src2)
+{
+  BITSET_CHECK3_ (dst, src1, src2);
+  return BITSET_AND_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset);
+}
+
+
+static void
+bitset_stats_andn (bitset dst, bitset src1, bitset src2)
+{
+  BITSET_CHECK3_ (dst, src1, src2);
+  BITSET_ANDN_ (dst->s.bset, src1->s.bset, src2->s.bset);
+}
+
+
+static bool
+bitset_stats_andn_cmp (bitset dst, bitset src1, bitset src2)
+{
+  BITSET_CHECK3_ (dst, src1, src2);
+  return BITSET_ANDN_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset);
+}
+
+
+static void
+bitset_stats_or (bitset dst, bitset src1, bitset src2)
+{
+  BITSET_CHECK3_ (dst, src1, src2);
+  BITSET_OR_ (dst->s.bset, src1->s.bset, src2->s.bset);
+}
+
+
+static bool
+bitset_stats_or_cmp (bitset dst, bitset src1, bitset src2)
+{
+  BITSET_CHECK3_ (dst, src1, src2);
+  return BITSET_OR_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset);
+}
+
+
+static void
+bitset_stats_xor (bitset dst, bitset src1, bitset src2)
+{
+  BITSET_CHECK3_ (dst, src1, src2);
+  BITSET_XOR_ (dst->s.bset, src1->s.bset, src2->s.bset);
+}
+
+
+static bool
+bitset_stats_xor_cmp (bitset dst, bitset src1, bitset src2)
+{
+  BITSET_CHECK3_ (dst, src1, src2);
+  return BITSET_XOR_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset);
+}
+
+
+static void
+bitset_stats_and_or (bitset dst, bitset src1, bitset src2, bitset src3)
+{
+  BITSET_CHECK4_ (dst, src1, src2, src3);
+  BITSET_AND_OR_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset);
+}
+
+
+static bool
+bitset_stats_and_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
+{
+  BITSET_CHECK4_ (dst, src1, src2, src3);
+  return BITSET_AND_OR_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset);
+}
+
+
+static void
+bitset_stats_andn_or (bitset dst, bitset src1, bitset src2, bitset src3)
+{
+  BITSET_CHECK4_ (dst, src1, src2, src3);
+  BITSET_ANDN_OR_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset);
+}
+
+
+static bool
+bitset_stats_andn_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
+{
+  BITSET_CHECK4_ (dst, src1, src2, src3);
+  return BITSET_ANDN_OR_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset);
+}
+
+
+static void
+bitset_stats_or_and (bitset dst, bitset src1, bitset src2, bitset src3)
+{
+  BITSET_CHECK4_ (dst, src1, src2, src3);
+  BITSET_OR_AND_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset);
+}
+
+
+static bool
+bitset_stats_or_and_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
+{
+  BITSET_CHECK4_ (dst, src1, src2, src3);
+  return BITSET_OR_AND_CMP_ (dst->s.bset, src1->s.bset, src2->s.bset, src3->s.bset);
+}
+
+
+static bitset_bindex
+bitset_stats_list (bitset bset, bitset_bindex *list,
+                   bitset_bindex num, bitset_bindex *next)
+{
+  bitset_bindex count = BITSET_LIST_ (bset->s.bset, list, num, next);
+
+  BITSET_STATS_LISTS_INC (bset->s.bset);
+
+  /* Log histogram of number of set bits.  */
+  {
+    bitset_bindex i;
+    bitset_bindex tmp;
+    for (i = 0, tmp = count; tmp; tmp >>= 1, i++)
+      continue;
+    if (i >= BITSET_LOG_COUNT_BINS)
+      i = BITSET_LOG_COUNT_BINS - 1;
+    BITSET_STATS_LIST_COUNTS_INC (bset->s.bset, i);
+  }
+
+  /* Log histogram of number of bits in set.  */
+  bitset_bindex size = BITSET_SIZE_ (bset->s.bset);
+  {
+    bitset_bindex i;
+    bitset_bindex tmp;
+    for (i = 0, tmp = size; tmp; tmp >>= 1, i++)
+      continue;
+    if (i >= BITSET_LOG_SIZE_BINS)
+      i = BITSET_LOG_SIZE_BINS - 1;
+    BITSET_STATS_LIST_SIZES_INC (bset->s.bset, i);
+  }
+
+  /* Histogram of fraction of bits set.  */
+  {
+    bitset_bindex i = size ? (count * BITSET_DENSITY_BINS) / size : 0;
+    if (i >= BITSET_DENSITY_BINS)
+      i = BITSET_DENSITY_BINS - 1;
+    BITSET_STATS_LIST_DENSITY_INC (bset->s.bset, i);
+  }
+  return count;
+}
+
+
+static bitset_bindex
+bitset_stats_list_reverse (bitset bset, bitset_bindex *list,
+                           bitset_bindex num, bitset_bindex *next)
+{
+  return BITSET_LIST_REVERSE_ (bset->s.bset, list, num, next);
+}
+
+
+static void
+bitset_stats_free (bitset bset)
+{
+  BITSET_STATS_FREES_INC (bset->s.bset);
+  BITSET_FREE_ (bset->s.bset);
+}
+
+
+struct bitset_vtable bitset_stats_vtable = {
+  bitset_stats_set,
+  bitset_stats_reset,
+  bitset_stats_toggle,
+  bitset_stats_test,
+  bitset_stats_resize,
+  bitset_stats_size,
+  bitset_stats_count,
+  bitset_stats_empty_p,
+  bitset_stats_ones,
+  bitset_stats_zero,
+  bitset_stats_copy,
+  bitset_stats_disjoint_p,
+  bitset_stats_equal_p,
+  bitset_stats_not,
+  bitset_stats_subset_p,
+  bitset_stats_and,
+  bitset_stats_and_cmp,
+  bitset_stats_andn,
+  bitset_stats_andn_cmp,
+  bitset_stats_or,
+  bitset_stats_or_cmp,
+  bitset_stats_xor,
+  bitset_stats_xor_cmp,
+  bitset_stats_and_or,
+  bitset_stats_and_or_cmp,
+  bitset_stats_andn_or,
+  bitset_stats_andn_or_cmp,
+  bitset_stats_or_and,
+  bitset_stats_or_and_cmp,
+  bitset_stats_list,
+  bitset_stats_list_reverse,
+  bitset_stats_free,
+  BITSET_STATS
+};
+
+
+/* Return enclosed bitset type.  */
+enum bitset_type
+bitset_stats_type_get (bitset bset)
+{
+  return BITSET_TYPE_ (bset->s.bset);
+}
+
+
+size_t
+bitset_stats_bytes (void)
+{
+  return sizeof (struct bitset_stats_struct);
+}
+
+
+bitset
+bitset_stats_init (bitset bset, bitset_bindex n_bits, enum bitset_type type)
+{
+  bset->b.vtable = &bitset_stats_vtable;
+
+  /* Disable cache.  */
+  bset->b.cindex = 0;
+  bset->b.csize = 0;
+  bset->b.cdata = 0;
+
+  BITSET_NBITS_ (bset) = n_bits;
+
+  /* Set up the actual bitset implementation that
+     we are a wrapper over.  */
+  switch (type)
+    {
+    default:
+      abort ();
+
+    case BITSET_ARRAY:
+      {
+        size_t bytes = abitset_bytes (n_bits);
+        bset->s.bset = xcalloc (1, bytes);
+        abitset_init (bset->s.bset, n_bits);
+      }
+      break;
+
+    case BITSET_LIST:
+      {
+        size_t bytes = lbitset_bytes (n_bits);
+        bset->s.bset = xcalloc (1, bytes);
+        lbitset_init (bset->s.bset, n_bits);
+      }
+      break;
+
+    case BITSET_TABLE:
+      {
+        size_t bytes = tbitset_bytes (n_bits);
+        bset->s.bset = xcalloc (1, bytes);
+        tbitset_init (bset->s.bset, n_bits);
+      }
+      break;
+
+    case BITSET_VECTOR:
+      {
+        size_t bytes = vbitset_bytes (n_bits);
+        bset->s.bset = xcalloc (1, bytes);
+        vbitset_init (bset->s.bset, n_bits);
+      }
+      break;
+    }
+
+  BITSET_STATS_ALLOCS_INC (type);
+
+  return bset;
+}
diff --git a/contrib/tools/bison/lib/bitset/stats.h b/contrib/tools/bison/lib/bitset/stats.h
new file mode 100644
index 0000000000..95e64dc4e5
--- /dev/null
+++ b/contrib/tools/bison/lib/bitset/stats.h
@@ -0,0 +1,33 @@
+/* Functions to support bitset statistics.
+
+   Copyright (C) 2002-2004, 2009-2015, 2018-2019 Free Software Foundation, Inc.
+
+   Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz).
+
+   This program is free software: you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation, either version 3 of the License, or
+   (at your option) any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
+
+#ifndef _BITSET_STATS_H
+#define _BITSET_STATS_H
+
+#include "bitset/base.h"
+
+extern bool bitset_stats_enabled;
+
+enum bitset_type bitset_stats_type_get (bitset);
+
+size_t bitset_stats_bytes (void);
+
+bitset bitset_stats_init (bitset, bitset_bindex, enum bitset_type);
+
+#endif
diff --git a/contrib/tools/bison/lib/bitset/table.c b/contrib/tools/bison/lib/bitset/table.c
new file mode 100644
index 0000000000..8351cf7848
--- /dev/null
+++ b/contrib/tools/bison/lib/bitset/table.c
@@ -0,0 +1,1228 @@
+/* Functions to support expandable bitsets.
+
+   Copyright (C) 2002-2006, 2009-2015, 2018-2019 Free Software Foundation, Inc.
+
+   Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz).
+
+   This program is free software: you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation, either version 3 of the License, or
+   (at your option) any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
+
+#include <config.h>
+
+#include "bitset/table.h"
+
+#include <stdlib.h>
+#include <string.h>
+
+#include "obstack.h"
+
+/* This file implements expandable bitsets.  These bitsets can be of
+   arbitrary length and are more efficient than arrays of bits for
+   large sparse sets.
+
+   Empty elements are represented by a NULL pointer in the table of
+   element pointers.  An alternative is to point to a special zero
+   element.  Similarly, we could represent an all 1's element with
+   another special ones element pointer.
+
+   Bitsets are commonly empty so we need to ensure that this special
+   case is fast.  A zero bitset is indicated when cdata is 0.  This is
+   conservative since cdata may be non zero and the bitset may still
+   be zero.
+
+   The bitset cache can be disabled either by setting cindex to
+   BITSET_WINDEX_MAX or by setting csize to 0.  Here
+   we use the former approach since cindex needs to be updated whenever
+   cdata is changed.
+*/
+
+
+/* Number of words to use for each element.  */
+#define EBITSET_ELT_WORDS 2
+
+/* Number of bits stored in each element.  */
+#define EBITSET_ELT_BITS \
+  ((unsigned) (EBITSET_ELT_WORDS * BITSET_WORD_BITS))
+
+/* Ebitset element.  We use an array of bits.  */
+typedef struct tbitset_elt_struct
+{
+  union
+  {
+    bitset_word words[EBITSET_ELT_WORDS];       /* Bits that are set.  */
+    struct tbitset_elt_struct *next;
+  }
+  u;
+}
+tbitset_elt;
+
+
+typedef tbitset_elt *tbitset_elts;
+
+
+/* Number of elements to initially allocate.  */
+
+#ifndef EBITSET_INITIAL_SIZE
+# define EBITSET_INITIAL_SIZE 2
+#endif
+
+
+enum tbitset_find_mode
+  { EBITSET_FIND, EBITSET_CREATE, EBITSET_SUBST };
+
+static tbitset_elt tbitset_zero_elts[1]; /* Elements of all zero bits.  */
+
+/* Obstack to allocate bitset elements from.  */
+static struct obstack tbitset_obstack;
+static bool tbitset_obstack_init = false;
+static tbitset_elt *tbitset_free_list;  /* Free list of bitset elements.  */
+
+#define EBITSET_N_ELTS(N) (((N) + EBITSET_ELT_BITS - 1) / EBITSET_ELT_BITS)
+#define EBITSET_ELTS(BSET) ((BSET)->e.elts)
+#define EBITSET_SIZE(BSET) EBITSET_N_ELTS (BITSET_NBITS_ (BSET))
+#define EBITSET_ASIZE(BSET) ((BSET)->e.size)
+
+#define EBITSET_NEXT(ELT) ((ELT)->u.next)
+#define EBITSET_WORDS(ELT) ((ELT)->u.words)
+
+/* Disable bitset cache and mark BSET as being zero.  */
+#define EBITSET_ZERO_SET(BSET) ((BSET)->b.cindex = BITSET_WINDEX_MAX, \
+        (BSET)->b.cdata = 0)
+
+#define EBITSET_CACHE_DISABLE(BSET)  ((BSET)->b.cindex = BITSET_WINDEX_MAX)
+
+/* Disable bitset cache and mark BSET as being possibly non-zero.  */
+#define EBITSET_NONZERO_SET(BSET) \
+ (EBITSET_CACHE_DISABLE (BSET), (BSET)->b.cdata = (bitset_word *)~0)
+
+/* A conservative estimate of whether the bitset is zero.
+   This is non-zero only if we know for sure that the bitset is zero.  */
+#define EBITSET_ZERO_P(BSET) ((BSET)->b.cdata == 0)
+
+/* Enable cache to point to element with table index EINDEX.
+   The element must exist.  */
+#define EBITSET_CACHE_SET(BSET, EINDEX) \
+ ((BSET)->b.cindex = (EINDEX) * EBITSET_ELT_WORDS, \
+  (BSET)->b.cdata = EBITSET_WORDS (EBITSET_ELTS (BSET) [EINDEX]))
+
+#undef min
+#undef max
+#define min(a, b) ((a) > (b) ? (b) : (a))
+#define max(a, b) ((a) > (b) ? (a) : (b))
+
+static bitset_bindex
+tbitset_resize (bitset src, bitset_bindex n_bits)
+{
+  if (n_bits == BITSET_NBITS_ (src))
+    return n_bits;
+
+  bitset_windex oldsize = EBITSET_SIZE (src);
+  bitset_windex newsize = EBITSET_N_ELTS (n_bits);
+
+  if (oldsize < newsize)
+    {
+      /* The bitset needs to grow.  If we already have enough memory
+         allocated, then just zero what we need.  */
+      if (newsize > EBITSET_ASIZE (src))
+        {
+          /* We need to allocate more memory.  When oldsize is
+             non-zero this means that we are changing the size, so
+             grow the bitset 25% larger than requested to reduce
+             number of reallocations.  */
+
+          bitset_windex size = oldsize == 0 ? newsize : newsize + newsize / 4;
+          EBITSET_ELTS (src)
+            = realloc (EBITSET_ELTS (src), size * sizeof (tbitset_elt *));
+          EBITSET_ASIZE (src) = size;
+        }
+
+      memset (EBITSET_ELTS (src) + oldsize, 0,
+              (newsize - oldsize) * sizeof (tbitset_elt *));
+    }
+  else
+    {
+      /* The bitset needs to shrink.  There's no point deallocating
+         the memory unless it is shrinking by a reasonable amount.  */
+      if ((oldsize - newsize) >= oldsize / 2)
+        {
+          EBITSET_ELTS (src)
+            = realloc (EBITSET_ELTS (src), newsize * sizeof (tbitset_elt *));
+          EBITSET_ASIZE (src) = newsize;
+        }
+
+      /* Need to prune any excess bits.  FIXME.  */
+    }
+
+  BITSET_NBITS_ (src) = n_bits;
+  return n_bits;
+}
+
+
+/* Allocate a tbitset element.  The bits are not cleared.  */
+static inline tbitset_elt *
+tbitset_elt_alloc (void)
+{
+  tbitset_elt *elt;
+
+  if (tbitset_free_list != 0)
+    {
+      elt = tbitset_free_list;
+      tbitset_free_list = EBITSET_NEXT (elt);
+    }
+  else
+    {
+      if (!tbitset_obstack_init)
+        {
+          tbitset_obstack_init = true;
+
+          /* Let particular systems override the size of a chunk.  */
+
+#ifndef OBSTACK_CHUNK_SIZE
+#define OBSTACK_CHUNK_SIZE 0
+#endif
+
+          /* Let them override the alloc and free routines too.  */
+
+#ifndef OBSTACK_CHUNK_ALLOC
+#define OBSTACK_CHUNK_ALLOC xmalloc
+#endif
+
+#ifndef OBSTACK_CHUNK_FREE
+#define OBSTACK_CHUNK_FREE free
+#endif
+
+#if ! defined __GNUC__ || __GNUC__ < 2
+#define __alignof__(type) 0
+#endif
+
+          obstack_specify_allocation (&tbitset_obstack, OBSTACK_CHUNK_SIZE,
+                                      __alignof__ (tbitset_elt),
+                                      OBSTACK_CHUNK_ALLOC,
+                                      OBSTACK_CHUNK_FREE);
+        }
+
+      /* Perhaps we should add a number of new elements to the free
+         list.  */
+      elt = (tbitset_elt *) obstack_alloc (&tbitset_obstack,
+                                           sizeof (tbitset_elt));
+    }
+
+  return elt;
+}
+
+
+/* Allocate a tbitset element.  The bits are cleared.  */
+static inline tbitset_elt *
+tbitset_elt_calloc (void)
+{
+  tbitset_elt *elt = tbitset_elt_alloc ();
+  memset (EBITSET_WORDS (elt), 0, sizeof (EBITSET_WORDS (elt)));
+  return elt;
+}
+
+
+static inline void
+tbitset_elt_free (tbitset_elt *elt)
+{
+  EBITSET_NEXT (elt) = tbitset_free_list;
+  tbitset_free_list = elt;
+}
+
+
+/* Remove element with index EINDEX from bitset BSET.  */
+static inline void
+tbitset_elt_remove (bitset bset, bitset_windex eindex)
+{
+  tbitset_elts *elts = EBITSET_ELTS (bset);
+  tbitset_elt *elt = elts[eindex];
+
+  elts[eindex] = 0;
+  tbitset_elt_free (elt);
+}
+
+
+/* Add ELT into elts at index EINDEX of bitset BSET.  */
+static inline void
+tbitset_elt_add (bitset bset, tbitset_elt *elt, bitset_windex eindex)
+{
+  tbitset_elts *elts = EBITSET_ELTS (bset);
+  /* Assume that the elts entry not allocated.  */
+  elts[eindex] = elt;
+}
+
+
+/* Are all bits in an element zero?  */
+static inline bool
+tbitset_elt_zero_p (tbitset_elt *elt)
+{
+  for (int i = 0; i < EBITSET_ELT_WORDS; i++)
+    if (EBITSET_WORDS (elt)[i])
+      return false;
+  return true;
+}
+
+
+static tbitset_elt *
+tbitset_elt_find (bitset bset, bitset_bindex bindex,
+                  enum tbitset_find_mode mode)
+{
+  bitset_windex eindex = bindex / EBITSET_ELT_BITS;
+
+  tbitset_elts *elts = EBITSET_ELTS (bset);
+  bitset_windex size = EBITSET_SIZE (bset);
+
+  if (eindex < size)
+    {
+      tbitset_elt *elt = elts[eindex];
+      if (elt)
+        {
+          if (EBITSET_WORDS (elt) != bset->b.cdata)
+            EBITSET_CACHE_SET (bset, eindex);
+          return elt;
+        }
+    }
+
+  /* The element could not be found.  */
+
+  switch (mode)
+    {
+    default:
+      abort ();
+
+    case EBITSET_FIND:
+      return 0;
+
+    case EBITSET_CREATE:
+      if (eindex >= size)
+        tbitset_resize (bset, bindex);
+
+      /* Create a new element.  */
+      {
+        tbitset_elt *elt = tbitset_elt_calloc ();
+        tbitset_elt_add (bset, elt, eindex);
+        EBITSET_CACHE_SET (bset, eindex);
+        return elt;
+      }
+
+    case EBITSET_SUBST:
+      return &tbitset_zero_elts[0];
+    }
+}
+
+
+/* Weed out the zero elements from the elts.  */
+static inline bitset_windex
+tbitset_weed (bitset bset)
+{
+  if (EBITSET_ZERO_P (bset))
+    return 0;
+
+  tbitset_elts *elts = EBITSET_ELTS (bset);
+  bitset_windex count = 0;
+  bitset_windex j;
+  for (j = 0; j < EBITSET_SIZE (bset); j++)
+    {
+      tbitset_elt *elt = elts[j];
+
+      if (elt)
+        {
+          if (tbitset_elt_zero_p (elt))
+            {
+              tbitset_elt_remove (bset, j);
+              count++;
+            }
+        }
+      else
+        count++;
+    }
+
+  count = j - count;
+  if (!count)
+    {
+      /* All the bits are zero.  We could shrink the elts.
+         For now just mark BSET as known to be zero.  */
+      EBITSET_ZERO_SET (bset);
+    }
+  else
+    EBITSET_NONZERO_SET (bset);
+
+  return count;
+}
+
+
+/* Set all bits in the bitset to zero.  */
+static inline void
+tbitset_zero (bitset bset)
+{
+  if (EBITSET_ZERO_P (bset))
+    return;
+
+  tbitset_elts *elts = EBITSET_ELTS (bset);
+  for (bitset_windex j = 0; j < EBITSET_SIZE (bset); j++)
+    {
+      tbitset_elt *elt = elts[j];
+      if (elt)
+        tbitset_elt_remove (bset, j);
+    }
+
+  /* All the bits are zero.  We could shrink the elts.
+     For now just mark BSET as known to be zero.  */
+  EBITSET_ZERO_SET (bset);
+}
+
+
+static inline bool
+tbitset_equal_p (bitset dst, bitset src)
+{
+  if (src == dst)
+    return true;
+
+  tbitset_weed (dst);
+  tbitset_weed (src);
+
+  if (EBITSET_SIZE (src) != EBITSET_SIZE (dst))
+    return false;
+
+  tbitset_elts *selts = EBITSET_ELTS (src);
+  tbitset_elts *delts = EBITSET_ELTS (dst);
+
+  for (bitset_windex j = 0; j < EBITSET_SIZE (src); j++)
+    {
+      tbitset_elt *selt = selts[j];
+      tbitset_elt *delt = delts[j];
+
+      if (!selt && !delt)
+        continue;
+      if ((selt && !delt) || (!selt && delt))
+        return false;
+
+      for (unsigned i = 0; i < EBITSET_ELT_WORDS; i++)
+        if (EBITSET_WORDS (selt)[i] != EBITSET_WORDS (delt)[i])
+          return false;
+    }
+  return true;
+}
+
+
+/* Copy bits from bitset SRC to bitset DST.  */
+static inline void
+tbitset_copy_ (bitset dst, bitset src)
+{
+  if (src == dst)
+    return;
+
+  tbitset_zero (dst);
+
+  if (BITSET_NBITS_ (dst) != BITSET_NBITS_ (src))
+    tbitset_resize (dst, BITSET_NBITS_ (src));
+
+  tbitset_elts *selts = EBITSET_ELTS (src);
+  tbitset_elts *delts = EBITSET_ELTS (dst);
+  for (bitset_windex j = 0; j < EBITSET_SIZE (src); j++)
+    {
+      tbitset_elt *selt = selts[j];
+      if (selt)
+        {
+          tbitset_elt *tmp = tbitset_elt_alloc ();
+          delts[j] = tmp;
+          memcpy (EBITSET_WORDS (tmp), EBITSET_WORDS (selt),
+                  sizeof (EBITSET_WORDS (selt)));
+        }
+    }
+  EBITSET_NONZERO_SET (dst);
+}
+
+
+/* Copy bits from bitset SRC to bitset DST.  Return true if
+   bitsets different.  */
+static inline bool
+tbitset_copy_cmp (bitset dst, bitset src)
+{
+  if (src == dst)
+    return false;
+
+  if (EBITSET_ZERO_P (dst))
+    {
+      tbitset_copy_ (dst, src);
+      return !EBITSET_ZERO_P (src);
+    }
+
+  if (tbitset_equal_p (dst, src))
+    return false;
+
+  tbitset_copy_ (dst, src);
+  return true;
+}
+
+
+/* Set bit BITNO in bitset DST.  */
+static void
+tbitset_set (bitset dst, bitset_bindex bitno)
+{
+  bitset_windex windex = bitno / BITSET_WORD_BITS;
+
+  tbitset_elt_find (dst, bitno, EBITSET_CREATE);
+
+  dst->b.cdata[windex - dst->b.cindex] |=
+    (bitset_word) 1 << (bitno % BITSET_WORD_BITS);
+}
+
+
+/* Reset bit BITNO in bitset DST.  */
+static void
+tbitset_reset (bitset dst, bitset_bindex bitno)
+{
+  bitset_windex windex = bitno / BITSET_WORD_BITS;
+
+  if (!tbitset_elt_find (dst, bitno, EBITSET_FIND))
+    return;
+
+  dst->b.cdata[windex - dst->b.cindex] &=
+    ~((bitset_word) 1 << (bitno % BITSET_WORD_BITS));
+
+  /* If all the data is zero, perhaps we should remove it now...
+     However, there is a good chance that the element will be needed
+     again soon.  */
+}
+
+
+/* Test bit BITNO in bitset SRC.  */
+static bool
+tbitset_test (bitset src, bitset_bindex bitno)
+{
+  bitset_windex windex = bitno / BITSET_WORD_BITS;
+
+  return (tbitset_elt_find (src, bitno, EBITSET_FIND)
+          && ((src->b.cdata[windex - src->b.cindex]
+               >> (bitno % BITSET_WORD_BITS))
+              & 1));
+}
+
+
+static void
+tbitset_free (bitset bset)
+{
+  tbitset_zero (bset);
+  free (EBITSET_ELTS (bset));
+}
+
+
+/* Find list of up to NUM bits set in BSET starting from and including
+ *NEXT and store in array LIST.  Return with actual number of bits
+ found and with *NEXT indicating where search stopped.  */
+static bitset_bindex
+tbitset_list_reverse (bitset bset, bitset_bindex *list,
+                      bitset_bindex num, bitset_bindex *next)
+{
+  if (EBITSET_ZERO_P (bset))
+    return 0;
+
+  bitset_windex size = EBITSET_SIZE (bset);
+  bitset_bindex n_bits = size * EBITSET_ELT_BITS;
+  bitset_bindex rbitno = *next;
+
+  if (rbitno >= n_bits)
+    return 0;
+
+  tbitset_elts *elts = EBITSET_ELTS (bset);
+
+  bitset_bindex bitno = n_bits - (rbitno + 1);
+
+  bitset_windex windex = bitno / BITSET_WORD_BITS;
+  bitset_windex eindex = bitno / EBITSET_ELT_BITS;
+  bitset_windex woffset = windex - eindex * EBITSET_ELT_WORDS;
+
+  /* If num is 1, we could speed things up with a binary search
+     of the word of interest.  */
+  bitset_bindex count = 0;
+  unsigned bcount = bitno % BITSET_WORD_BITS;
+  bitset_bindex boffset = windex * BITSET_WORD_BITS;
+
+  do
+    {
+      tbitset_elt *elt = elts[eindex];
+      if (elt)
+        {
+          bitset_word *srcp = EBITSET_WORDS (elt);
+
+          do
+            {
+              for (bitset_word word = srcp[woffset] << (BITSET_WORD_BITS - 1 - bcount);
+                   word; bcount--)
+                {
+                  if (word & BITSET_MSB)
+                    {
+                      list[count++] = boffset + bcount;
+                      if (count >= num)
+                        {
+                          *next = n_bits - (boffset + bcount);
+                          return count;
+                        }
+                    }
+                  word <<= 1;
+                }
+              boffset -= BITSET_WORD_BITS;
+              bcount = BITSET_WORD_BITS - 1;
+            }
+          while (woffset--);
+        }
+
+      woffset = EBITSET_ELT_WORDS - 1;
+      boffset = eindex * EBITSET_ELT_BITS - BITSET_WORD_BITS;
+    }
+  while (eindex--);
+
+  *next = n_bits - (boffset + 1);
+  return count;
+}
+
+
+/* Find list of up to NUM bits set in BSET starting from and including
+ *NEXT and store in array LIST.  Return with actual number of bits
+ found and with *NEXT indicating where search stopped.  */
+static bitset_bindex
+tbitset_list (bitset bset, bitset_bindex *list,
+              bitset_bindex num, bitset_bindex *next)
+{
+  if (EBITSET_ZERO_P (bset))
+    return 0;
+
+  bitset_bindex bitno = *next;
+  bitset_bindex count = 0;
+
+  tbitset_elts *elts = EBITSET_ELTS (bset);
+  bitset_windex size = EBITSET_SIZE (bset);
+  bitset_windex eindex = bitno / EBITSET_ELT_BITS;
+
+  if (bitno % EBITSET_ELT_BITS)
+    {
+      /* We need to start within an element.  This is not very common.  */
+
+      tbitset_elt *elt = elts[eindex];
+      if (elt)
+        {
+          bitset_windex woffset;
+          bitset_word *srcp = EBITSET_WORDS (elt);
+
+          bitset_windex windex = bitno / BITSET_WORD_BITS;
+          woffset = eindex * EBITSET_ELT_WORDS;
+
+          for (; (windex - woffset) < EBITSET_ELT_WORDS; windex++)
+            {
+              bitset_word word = srcp[windex - woffset] >> (bitno % BITSET_WORD_BITS);
+
+              for (; word; bitno++)
+                {
+                  if (word & 1)
+                    {
+                      list[count++] = bitno;
+                      if (count >= num)
+                        {
+                          *next = bitno + 1;
+                          return count;
+                        }
+                    }
+                  word >>= 1;
+                }
+              bitno = (windex + 1) * BITSET_WORD_BITS;
+            }
+        }
+
+      /* Skip to next element.  */
+      eindex++;
+    }
+
+  /* If num is 1, we could speed things up with a binary search
+     of the word of interest.  */
+
+  for (; eindex < size; eindex++)
+    {
+      bitset_word *srcp;
+
+      tbitset_elt *elt = elts[eindex];
+      if (!elt)
+        continue;
+
+      srcp = EBITSET_WORDS (elt);
+      bitset_windex windex = eindex * EBITSET_ELT_WORDS;
+
+      if ((count + EBITSET_ELT_BITS) < num)
+        {
+          /* The coast is clear, plant boot!  */
+
+#if EBITSET_ELT_WORDS == 2
+          bitset_word word = srcp[0];
+          if (word)
+            {
+              if (!(word & 0xffff))
+                {
+                  word >>= 16;
+                  bitno += 16;
+                }
+              if (!(word & 0xff))
+                {
+                  word >>= 8;
+                  bitno += 8;
+                }
+              for (; word; bitno++)
+                {
+                  if (word & 1)
+                    list[count++] = bitno;
+                  word >>= 1;
+                }
+            }
+          windex++;
+          bitno = windex * BITSET_WORD_BITS;
+
+          word = srcp[1];
+          if (word)
+            {
+              if (!(word & 0xffff))
+                {
+                  word >>= 16;
+                  bitno += 16;
+                }
+              for (; word; bitno++)
+                {
+                  if (word & 1)
+                    list[count++] = bitno;
+                  word >>= 1;
+                }
+            }
+          windex++;
+          bitno = windex * BITSET_WORD_BITS;
+#else
+          for (int i = 0; i < EBITSET_ELT_WORDS; i++, windex++)
+            {
+              bitno = windex * BITSET_WORD_BITS;
+
+              word = srcp[i];
+              if (word)
+                {
+                  if (!(word & 0xffff))
+                    {
+                      word >>= 16;
+                      bitno += 16;
+                    }
+                  if (!(word & 0xff))
+                    {
+                      word >>= 8;
+                      bitno += 8;
+                    }
+                  for (; word; bitno++)
+                    {
+                      if (word & 1)
+                        list[count++] = bitno;
+                      word >>= 1;
+                    }
+                }
+            }
+#endif
+        }
+      else
+        {
+          /* Tread more carefully since we need to check
+             if array overflows.  */
+
+          for (int i = 0; i < EBITSET_ELT_WORDS; i++, windex++)
+            {
+              bitno = windex * BITSET_WORD_BITS;
+
+              for (bitset_word word = srcp[i]; word; bitno++)
+                {
+                  if (word & 1)
+                    {
+                      list[count++] = bitno;
+                      if (count >= num)
+                        {
+                          *next = bitno + 1;
+                          return count;
+                        }
+                    }
+                  word >>= 1;
+                }
+            }
+        }
+    }
+
+  *next = bitno;
+  return count;
+}
+
+
+/* Ensure that any unused bits within the last element are clear.  */
+static inline void
+tbitset_unused_clear (bitset dst)
+{
+  bitset_bindex n_bits = BITSET_NBITS_ (dst);
+  unsigned last_bit = n_bits % EBITSET_ELT_BITS;
+
+  if (last_bit)
+    {
+      tbitset_elts *elts = EBITSET_ELTS (dst);
+
+      bitset_windex eindex = n_bits / EBITSET_ELT_BITS;
+
+      tbitset_elt *elt = elts[eindex];
+      if (elt)
+        {
+          bitset_word *srcp = EBITSET_WORDS (elt);
+
+          bitset_windex windex = n_bits / BITSET_WORD_BITS;
+          bitset_windex woffset = eindex * EBITSET_ELT_WORDS;
+
+          srcp[windex - woffset] &= ((bitset_word) 1 << last_bit) - 1;
+          windex++;
+          for (; (windex - woffset) < EBITSET_ELT_WORDS; windex++)
+            srcp[windex - woffset] = 0;
+        }
+    }
+}
+
+
+static void
+tbitset_ones (bitset dst)
+{
+  for (bitset_windex j = 0; j < EBITSET_SIZE (dst); j++)
+    {
+      /* Create new elements if they cannot be found.  Perhaps
+         we should just add pointers to a ones element?  */
+      tbitset_elt *elt =
+        tbitset_elt_find (dst, j * EBITSET_ELT_BITS, EBITSET_CREATE);
+      memset (EBITSET_WORDS (elt), -1, sizeof (EBITSET_WORDS (elt)));
+    }
+  EBITSET_NONZERO_SET (dst);
+  tbitset_unused_clear (dst);
+}
+
+
+static bool
+tbitset_empty_p (bitset dst)
+{
+  if (EBITSET_ZERO_P (dst))
+    return true;
+
+  tbitset_elts *elts = EBITSET_ELTS (dst);
+  for (bitset_windex j = 0; j < EBITSET_SIZE (dst); j++)
+    {
+      tbitset_elt *elt = elts[j];
+
+      if (elt)
+        {
+          if (!tbitset_elt_zero_p (elt))
+            return false;
+          /* Do some weeding as we go.  */
+          tbitset_elt_remove (dst, j);
+        }
+    }
+
+  /* All the bits are zero.  We could shrink the elts.
+     For now just mark DST as known to be zero.  */
+  EBITSET_ZERO_SET (dst);
+  return true;
+}
+
+
+static void
+tbitset_not (bitset dst, bitset src)
+{
+  tbitset_resize (dst, BITSET_NBITS_ (src));
+
+  for (bitset_windex j = 0; j < EBITSET_SIZE (src); j++)
+    {
+      /* Create new elements for dst if they cannot be found
+         or substitute zero elements if src elements not found.  */
+      tbitset_elt *selt =
+        tbitset_elt_find (src, j * EBITSET_ELT_BITS, EBITSET_SUBST);
+      tbitset_elt *delt =
+        tbitset_elt_find (dst, j * EBITSET_ELT_BITS, EBITSET_CREATE);
+
+      for (unsigned i = 0; i < EBITSET_ELT_WORDS; i++)
+        EBITSET_WORDS (delt)[i] = ~EBITSET_WORDS (selt)[i];
+    }
+  EBITSET_NONZERO_SET (dst);
+  tbitset_unused_clear (dst);
+}
+
+
+/* Is DST == DST | SRC?  */
+static bool
+tbitset_subset_p (bitset dst, bitset src)
+{
+  tbitset_elts *selts = EBITSET_ELTS (src);
+  tbitset_elts *delts = EBITSET_ELTS (dst);
+
+  bitset_windex ssize = EBITSET_SIZE (src);
+  bitset_windex dsize = EBITSET_SIZE (dst);
+
+  for (bitset_windex j = 0; j < ssize; j++)
+    {
+      tbitset_elt *selt = j < ssize ? selts[j] : 0;
+      tbitset_elt *delt = j < dsize ? delts[j] : 0;
+
+      if (!selt && !delt)
+        continue;
+
+      if (!selt)
+        selt = &tbitset_zero_elts[0];
+      if (!delt)
+        delt = &tbitset_zero_elts[0];
+
+      for (unsigned i = 0; i < EBITSET_ELT_WORDS; i++)
+        if (EBITSET_WORDS (delt)[i]
+            != (EBITSET_WORDS (selt)[i] | EBITSET_WORDS (delt)[i]))
+          return false;
+    }
+  return true;
+}
+
+
+/* Is DST & SRC == 0?  */
+static bool
+tbitset_disjoint_p (bitset dst, bitset src)
+{
+  tbitset_elts *selts = EBITSET_ELTS (src);
+  tbitset_elts *delts = EBITSET_ELTS (dst);
+
+  bitset_windex ssize = EBITSET_SIZE (src);
+  bitset_windex dsize = EBITSET_SIZE (dst);
+
+  for (bitset_windex j = 0; j < ssize; j++)
+    {
+      tbitset_elt *selt = j < ssize ? selts[j] : 0;
+      tbitset_elt *delt = j < dsize ? delts[j] : 0;
+
+      if (!selt || !delt)
+        continue;
+
+      for (unsigned i = 0; i < EBITSET_ELT_WORDS; i++)
+        if ((EBITSET_WORDS (selt)[i] & EBITSET_WORDS (delt)[i]))
+          return false;
+    }
+  return true;
+}
+
+
+
+static bool
+tbitset_op3_cmp (bitset dst, bitset src1, bitset src2, enum bitset_ops op)
+{
+  bool changed = false;
+
+  tbitset_resize (dst, max (BITSET_NBITS_ (src1), BITSET_NBITS_ (src2)));
+
+  bitset_windex ssize1 = EBITSET_SIZE (src1);
+  bitset_windex ssize2 = EBITSET_SIZE (src2);
+  bitset_windex dsize = EBITSET_SIZE (dst);
+  bitset_windex size = ssize1;
+  if (size < ssize2)
+    size = ssize2;
+
+  tbitset_elts *selts1 = EBITSET_ELTS (src1);
+  tbitset_elts *selts2 = EBITSET_ELTS (src2);
+  tbitset_elts *delts = EBITSET_ELTS (dst);
+
+  bitset_windex j = 0;
+  for (j = 0; j < size; j++)
+    {
+      tbitset_elt *selt1 = j < ssize1 ? selts1[j] : 0;
+      tbitset_elt *selt2 = j < ssize2 ? selts2[j] : 0;
+      tbitset_elt *delt = j < dsize ? delts[j] : 0;
+
+      if (!selt1 && !selt2)
+        {
+          if (delt)
+            {
+              changed = true;
+              tbitset_elt_remove (dst, j);
+            }
+          continue;
+        }
+
+      if (!selt1)
+        selt1 = &tbitset_zero_elts[0];
+      if (!selt2)
+        selt2 = &tbitset_zero_elts[0];
+      if (!delt)
+        delt = tbitset_elt_calloc ();
+      else
+        delts[j] = 0;
+
+      bitset_word *srcp1 = EBITSET_WORDS (selt1);
+      bitset_word *srcp2 = EBITSET_WORDS (selt2);
+      bitset_word *dstp = EBITSET_WORDS (delt);
+      switch (op)
+        {
+        default:
+          abort ();
+
+        case BITSET_OP_OR:
+          for (unsigned i = 0; i < EBITSET_ELT_WORDS; i++, dstp++)
+            {
+              bitset_word tmp = *srcp1++ | *srcp2++;
+
+              if (*dstp != tmp)
+                {
+                  changed = true;
+                  *dstp = tmp;
+                }
+            }
+          break;
+
+        case BITSET_OP_AND:
+          for (unsigned i = 0; i < EBITSET_ELT_WORDS; i++, dstp++)
+            {
+              bitset_word tmp = *srcp1++ & *srcp2++;
+
+              if (*dstp != tmp)
+                {
+                  changed = true;
+                  *dstp = tmp;
+                }
+            }
+          break;
+
+        case BITSET_OP_XOR:
+          for (unsigned i = 0; i < EBITSET_ELT_WORDS; i++, dstp++)
+            {
+              bitset_word tmp = *srcp1++ ^ *srcp2++;
+
+              if (*dstp != tmp)
+                {
+                  changed = true;
+                  *dstp = tmp;
+                }
+            }
+          break;
+
+        case BITSET_OP_ANDN:
+          for (unsigned i = 0; i < EBITSET_ELT_WORDS; i++, dstp++)
+            {
+              bitset_word tmp = *srcp1++ & ~(*srcp2++);
+
+              if (*dstp != tmp)
+                {
+                  changed = true;
+                  *dstp = tmp;
+                }
+            }
+          break;
+        }
+
+      if (!tbitset_elt_zero_p (delt))
+        {
+          tbitset_elt_add (dst, delt, j);
+        }
+      else
+        {
+          tbitset_elt_free (delt);
+        }
+    }
+
+  /* If we have elements of DST left over, free them all.  */
+  for (; j < dsize; j++)
+    {
+      changed = true;
+
+      tbitset_elt *delt = delts[j];
+      if (delt)
+        tbitset_elt_remove (dst, j);
+    }
+
+  EBITSET_NONZERO_SET (dst);
+  return changed;
+}
+
+
+static bool
+tbitset_and_cmp (bitset dst, bitset src1, bitset src2)
+{
+  if (EBITSET_ZERO_P (src2))
+    {
+      tbitset_weed (dst);
+      bool changed = EBITSET_ZERO_P (dst);
+      tbitset_zero (dst);
+      return changed;
+    }
+  else if (EBITSET_ZERO_P (src1))
+    {
+      tbitset_weed (dst);
+      bool changed = EBITSET_ZERO_P (dst);
+      tbitset_zero (dst);
+      return changed;
+    }
+  return tbitset_op3_cmp (dst, src1, src2, BITSET_OP_AND);
+}
+
+
+static void
+tbitset_and (bitset dst, bitset src1, bitset src2)
+{
+  tbitset_and_cmp (dst, src1, src2);
+}
+
+
+static bool
+tbitset_andn_cmp (bitset dst, bitset src1, bitset src2)
+{
+  if (EBITSET_ZERO_P (src2))
+    {
+      return tbitset_copy_cmp (dst, src1);
+    }
+  else if (EBITSET_ZERO_P (src1))
+    {
+      tbitset_weed (dst);
+      bool changed = EBITSET_ZERO_P (dst);
+      tbitset_zero (dst);
+      return changed;
+    }
+  return tbitset_op3_cmp (dst, src1, src2, BITSET_OP_ANDN);
+}
+
+
+static void
+tbitset_andn (bitset dst, bitset src1, bitset src2)
+{
+  tbitset_andn_cmp (dst, src1, src2);
+}
+
+
+static bool
+tbitset_or_cmp (bitset dst, bitset src1, bitset src2)
+{
+  if (EBITSET_ZERO_P (src2))
+    {
+      return tbitset_copy_cmp (dst, src1);
+    }
+  else if (EBITSET_ZERO_P (src1))
+    {
+      return tbitset_copy_cmp (dst, src2);
+    }
+  return tbitset_op3_cmp (dst, src1, src2, BITSET_OP_OR);
+}
+
+
+static void
+tbitset_or (bitset dst, bitset src1, bitset src2)
+{
+  tbitset_or_cmp (dst, src1, src2);
+}
+
+
+static bool
+tbitset_xor_cmp (bitset dst, bitset src1, bitset src2)
+{
+  if (EBITSET_ZERO_P (src2))
+    {
+      return tbitset_copy_cmp (dst, src1);
+    }
+  else if (EBITSET_ZERO_P (src1))
+    {
+      return tbitset_copy_cmp (dst, src2);
+    }
+  return tbitset_op3_cmp (dst, src1, src2, BITSET_OP_XOR);
+}
+
+
+static void
+tbitset_xor (bitset dst, bitset src1, bitset src2)
+{
+  tbitset_xor_cmp (dst, src1, src2);
+}
+
+
+static void
+tbitset_copy (bitset dst, bitset src)
+{
+  if (BITSET_COMPATIBLE_ (dst, src))
+    tbitset_copy_ (dst, src);
+  else
+    bitset_copy_ (dst, src);
+}
+
+
+/* Vector of operations for linked-list bitsets.  */
+struct bitset_vtable tbitset_vtable = {
+  tbitset_set,
+  tbitset_reset,
+  bitset_toggle_,
+  tbitset_test,
+  tbitset_resize,
+  bitset_size_,
+  bitset_count_,
+  tbitset_empty_p,
+  tbitset_ones,
+  tbitset_zero,
+  tbitset_copy,
+  tbitset_disjoint_p,
+  tbitset_equal_p,
+  tbitset_not,
+  tbitset_subset_p,
+  tbitset_and,
+  tbitset_and_cmp,
+  tbitset_andn,
+  tbitset_andn_cmp,
+  tbitset_or,
+  tbitset_or_cmp,
+  tbitset_xor,
+  tbitset_xor_cmp,
+  bitset_and_or_,
+  bitset_and_or_cmp_,
+  bitset_andn_or_,
+  bitset_andn_or_cmp_,
+  bitset_or_and_,
+  bitset_or_and_cmp_,
+  tbitset_list,
+  tbitset_list_reverse,
+  tbitset_free,
+  BITSET_TABLE
+};
+
+
+/* Return size of initial structure.  */
+size_t
+tbitset_bytes (bitset_bindex n_bits ATTRIBUTE_UNUSED)
+{
+  return sizeof (struct tbitset_struct);
+}
+
+
+/* Initialize a bitset.  */
+
+bitset
+tbitset_init (bitset bset, bitset_bindex n_bits)
+{
+  bset->b.vtable = &tbitset_vtable;
+
+  bset->b.csize = EBITSET_ELT_WORDS;
+
+  EBITSET_ZERO_SET (bset);
+
+  EBITSET_ASIZE (bset) = 0;
+  EBITSET_ELTS (bset) = 0;
+  tbitset_resize (bset, n_bits);
+
+  return bset;
+}
+
+
+void
+tbitset_release_memory (void)
+{
+  tbitset_free_list = 0;
+  if (tbitset_obstack_init)
+    {
+      tbitset_obstack_init = false;
+      obstack_free (&tbitset_obstack, NULL);
+    }
+}
diff --git a/contrib/tools/bison/lib/bitset/table.h b/contrib/tools/bison/lib/bitset/table.h
new file mode 100644
index 0000000000..6c781adde3
--- /dev/null
+++ b/contrib/tools/bison/lib/bitset/table.h
@@ -0,0 +1,32 @@
+/* Functions to support tbitsets.
+
+   Copyright (C) 2002, 2004, 2009-2015, 2018-2019 Free Software Foundation,
+   Inc.
+
+   Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz).
+
+   This program is free software: you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation, either version 3 of the License, or
+   (at your option) any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
+
+#ifndef _BITSET_TABLE_H
+#define _BITSET_TABLE_H
+
+#include "bitset.h"
+
+size_t tbitset_bytes (bitset_bindex);
+
+bitset tbitset_init (bitset, bitset_bindex);
+
+void tbitset_release_memory (void);
+
+#endif
diff --git a/contrib/tools/bison/lib/bitset/vector.c b/contrib/tools/bison/lib/bitset/vector.c
new file mode 100644
index 0000000000..15d3e99567
--- /dev/null
+++ b/contrib/tools/bison/lib/bitset/vector.c
@@ -0,0 +1,985 @@
+/* Variable array bitsets.
+
+   Copyright (C) 2002-2006, 2009-2015, 2018-2019 Free Software Foundation, Inc.
+
+   Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz).
+
+   This program is free software: you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation, either version 3 of the License, or
+   (at your option) any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
+
+#include <config.h>
+
+#include "bitset/vector.h"
+
+#include <stdlib.h>
+#include <string.h>
+
+/* This file implements variable size bitsets stored as a variable
+   length array of words.  Any unused bits in the last word must be
+   zero.
+
+   Note that binary or ternary operations assume that each bitset operand
+   has the same size.
+*/
+
+static void vbitset_unused_clear (bitset);
+
+static void vbitset_set (bitset, bitset_bindex);
+static void vbitset_reset (bitset, bitset_bindex);
+static bool vbitset_test (bitset, bitset_bindex);
+static bitset_bindex vbitset_list (bitset, bitset_bindex *,
+                                   bitset_bindex, bitset_bindex *);
+static bitset_bindex vbitset_list_reverse (bitset, bitset_bindex *,
+                                           bitset_bindex, bitset_bindex *);
+
+#define VBITSET_N_WORDS(N) (((N) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS)
+#define VBITSET_WORDS(X) ((X)->b.cdata)
+#define VBITSET_SIZE(X) ((X)->b.csize)
+#define VBITSET_ASIZE(X) ((X)->v.size)
+
+#undef min
+#undef max
+#define min(a, b) ((a) > (b) ? (b) : (a))
+#define max(a, b) ((a) > (b) ? (a) : (b))
+
+static bitset_bindex
+vbitset_resize (bitset src, bitset_bindex n_bits)
+{
+  if (n_bits == BITSET_NBITS_ (src))
+    return n_bits;
+
+  bitset_windex oldsize = VBITSET_SIZE (src);
+  bitset_windex newsize = VBITSET_N_WORDS (n_bits);
+
+  if (oldsize < newsize)
+    {
+      /* The bitset needs to grow.  If we already have enough memory
+         allocated, then just zero what we need.  */
+      if (newsize > VBITSET_ASIZE (src))
+        {
+          /* We need to allocate more memory.  When oldsize is
+             non-zero this means that we are changing the size, so
+             grow the bitset 25% larger than requested to reduce
+             number of reallocations.  */
+
+          bitset_windex size = oldsize == 0 ? newsize : newsize + newsize / 4;
+          VBITSET_WORDS (src)
+            = realloc (VBITSET_WORDS (src), size * sizeof (bitset_word));
+          VBITSET_ASIZE (src) = size;
+        }
+
+      memset (VBITSET_WORDS (src) + oldsize, 0,
+              (newsize - oldsize) * sizeof (bitset_word));
+      VBITSET_SIZE (src) = newsize;
+    }
+  else
+    {
+      /* The bitset needs to shrink.  There's no point deallocating
+         the memory unless it is shrinking by a reasonable amount.  */
+      if ((oldsize - newsize) >= oldsize / 2)
+        {
+          VBITSET_WORDS (src)
+            = realloc (VBITSET_WORDS (src), newsize * sizeof (bitset_word));
+          VBITSET_ASIZE (src) = newsize;
+        }
+
+      /* Need to prune any excess bits.  FIXME.  */
+
+      VBITSET_SIZE (src) = newsize;
+    }
+
+  BITSET_NBITS_ (src) = n_bits;
+  return n_bits;
+}
+
+
+/* Set bit BITNO in bitset DST.  */
+static void
+vbitset_set (bitset dst, bitset_bindex bitno)
+{
+  bitset_windex windex = bitno / BITSET_WORD_BITS;
+
+  /* Perhaps we should abort.  The user should explicitly call
+     bitset_resize since this will not catch the case when we set a
+     bit larger than the current size but smaller than the allocated
+     size.  */
+  vbitset_resize (dst, bitno);
+
+  dst->b.cdata[windex - dst->b.cindex] |=
+    (bitset_word) 1 << (bitno % BITSET_WORD_BITS);
+}
+
+
+/* Reset bit BITNO in bitset DST.  */
+static void
+vbitset_reset (bitset dst ATTRIBUTE_UNUSED, bitset_bindex bitno ATTRIBUTE_UNUSED)
+{
+  /* We must be accessing outside the cache so the bit is
+     zero anyway.  */
+}
+
+
+/* Test bit BITNO in bitset SRC.  */
+static bool
+vbitset_test (bitset src ATTRIBUTE_UNUSED,
+              bitset_bindex bitno ATTRIBUTE_UNUSED)
+{
+  /* We must be accessing outside the cache so the bit is
+     zero anyway.  */
+  return false;
+}
+
+
+/* Find list of up to NUM bits set in BSET in reverse order, starting
+   from and including NEXT and store in array LIST.  Return with
+   actual number of bits found and with *NEXT indicating where search
+   stopped.  */
+static bitset_bindex
+vbitset_list_reverse (bitset src, bitset_bindex *list,
+                      bitset_bindex num, bitset_bindex *next)
+{
+  bitset_word *srcp = VBITSET_WORDS (src);
+  bitset_bindex n_bits = BITSET_SIZE_ (src);
+
+  bitset_bindex rbitno = *next;
+
+  /* If num is 1, we could speed things up with a binary search
+     of the word of interest.  */
+
+  if (rbitno >= n_bits)
+    return 0;
+
+  bitset_bindex count = 0;
+
+  bitset_bindex bitno = n_bits - (rbitno + 1);
+
+  bitset_windex windex = bitno / BITSET_WORD_BITS;
+  unsigned bitcnt = bitno % BITSET_WORD_BITS;
+  bitset_bindex bitoff = windex * BITSET_WORD_BITS;
+
+  do
+    {
+      bitset_word word = srcp[windex] << (BITSET_WORD_BITS - 1 - bitcnt);
+      for (; word; bitcnt--)
+        {
+          if (word & BITSET_MSB)
+            {
+              list[count++] = bitoff + bitcnt;
+              if (count >= num)
+                {
+                  *next = n_bits - (bitoff + bitcnt);
+                  return count;
+                }
+            }
+          word <<= 1;
+        }
+      bitoff -= BITSET_WORD_BITS;
+      bitcnt = BITSET_WORD_BITS - 1;
+    }
+  while (windex--);
+
+  *next = n_bits - (bitoff + 1);
+  return count;
+}
+
+
+/* Find list of up to NUM bits set in BSET starting from and including
+   *NEXT and store in array LIST.  Return with actual number of bits
+   found and with *NEXT indicating where search stopped.  */
+static bitset_bindex
+vbitset_list (bitset src, bitset_bindex *list,
+              bitset_bindex num, bitset_bindex *next)
+{
+  bitset_windex size = VBITSET_SIZE (src);
+  bitset_word *srcp = VBITSET_WORDS (src);
+  bitset_bindex bitno = *next;
+  bitset_bindex count = 0;
+
+  bitset_windex windex;
+  bitset_bindex bitoff;
+  bitset_word word;
+
+  if (!bitno)
+    {
+      /* Many bitsets are zero, so make this common case fast.  */
+      for (windex = 0; windex < size && !srcp[windex]; windex++)
+        continue;
+      if (windex >= size)
+        return 0;
+
+      /* If num is 1, we could speed things up with a binary search
+         of the current word.  */
+
+      bitoff = windex * BITSET_WORD_BITS;
+    }
+  else
+    {
+      if (bitno >= BITSET_SIZE_ (src))
+        return 0;
+
+      windex = bitno / BITSET_WORD_BITS;
+      bitno = bitno % BITSET_WORD_BITS;
+
+      if (bitno)
+        {
+          /* Handle the case where we start within a word.
+             Most often, this is executed with large bitsets
+             with many set bits where we filled the array
+             on the previous call to this function.  */
+
+          bitoff = windex * BITSET_WORD_BITS;
+          word = srcp[windex] >> bitno;
+          for (bitno = bitoff + bitno; word; bitno++)
+            {
+              if (word & 1)
+                {
+                  list[count++] = bitno;
+                  if (count >= num)
+                    {
+                      *next = bitno + 1;
+                      return count;
+                    }
+                }
+              word >>= 1;
+            }
+          windex++;
+        }
+      bitoff = windex * BITSET_WORD_BITS;
+    }
+
+  for (; windex < size; windex++, bitoff += BITSET_WORD_BITS)
+    {
+      if (!(word = srcp[windex]))
+        continue;
+
+      if ((count + BITSET_WORD_BITS) < num)
+        {
+          for (bitno = bitoff; word; bitno++)
+            {
+              if (word & 1)
+                list[count++] = bitno;
+              word >>= 1;
+            }
+        }
+      else
+        {
+          for (bitno = bitoff; word; bitno++)
+            {
+              if (word & 1)
+                {
+                  list[count++] = bitno;
+                  if (count >= num)
+                    {
+                      *next = bitno + 1;
+                      return count;
+                    }
+                }
+              word >>= 1;
+            }
+        }
+    }
+
+  *next = bitoff;
+  return count;
+}
+
+
+/* Ensure that any unused bits within the last word are clear.  */
+static inline void
+vbitset_unused_clear (bitset dst)
+{
+  unsigned last_bit = BITSET_SIZE_ (dst) % BITSET_WORD_BITS;
+  if (last_bit)
+    VBITSET_WORDS (dst)[VBITSET_SIZE (dst) - 1] &=
+      ((bitset_word) 1 << last_bit) - 1;
+}
+
+
+static void
+vbitset_ones (bitset dst)
+{
+  bitset_word *dstp = VBITSET_WORDS (dst);
+  unsigned bytes = sizeof (bitset_word) * VBITSET_SIZE (dst);
+
+  memset (dstp, -1, bytes);
+  vbitset_unused_clear (dst);
+}
+
+
+static void
+vbitset_zero (bitset dst)
+{
+  bitset_word *dstp = VBITSET_WORDS (dst);
+  unsigned bytes = sizeof (bitset_word) * VBITSET_SIZE (dst);
+
+  memset (dstp, 0, bytes);
+}
+
+
+static bool
+vbitset_empty_p (bitset dst)
+{
+  bitset_word *dstp = VBITSET_WORDS (dst);
+
+  for (unsigned i = 0; i < VBITSET_SIZE (dst); i++)
+    if (dstp[i])
+      return false;
+  return true;
+}
+
+
+static void
+vbitset_copy1 (bitset dst, bitset src)
+{
+  if (src == dst)
+    return;
+
+  vbitset_resize (dst, BITSET_SIZE_ (src));
+
+  bitset_word *srcp = VBITSET_WORDS (src);
+  bitset_word *dstp = VBITSET_WORDS (dst);
+  bitset_windex ssize = VBITSET_SIZE (src);
+  bitset_windex dsize = VBITSET_SIZE (dst);
+
+  memcpy (dstp, srcp, sizeof (bitset_word) * ssize);
+
+  memset (dstp + sizeof (bitset_word) * ssize, 0,
+          sizeof (bitset_word) * (dsize - ssize));
+}
+
+
+static void
+vbitset_not (bitset dst, bitset src)
+{
+  vbitset_resize (dst, BITSET_SIZE_ (src));
+
+  bitset_word *srcp = VBITSET_WORDS (src);
+  bitset_word *dstp = VBITSET_WORDS (dst);
+  bitset_windex ssize = VBITSET_SIZE (src);
+  bitset_windex dsize = VBITSET_SIZE (dst);
+
+  for (unsigned i = 0; i < ssize; i++)
+    *dstp++ = ~(*srcp++);
+
+  vbitset_unused_clear (dst);
+  memset (dstp + sizeof (bitset_word) * ssize, 0,
+          sizeof (bitset_word) * (dsize - ssize));
+}
+
+
+static bool
+vbitset_equal_p (bitset dst, bitset src)
+{
+  bitset_word *srcp = VBITSET_WORDS (src);
+  bitset_word *dstp = VBITSET_WORDS (dst);
+  bitset_windex ssize = VBITSET_SIZE (src);
+  bitset_windex dsize = VBITSET_SIZE (dst);
+
+  unsigned i;
+  for (i = 0; i < min (ssize, dsize); i++)
+    if (*srcp++ != *dstp++)
+      return false;
+
+  if (ssize > dsize)
+    {
+      for (; i < ssize; i++)
+        if (*srcp++)
+          return false;
+    }
+  else
+    {
+      for (; i < dsize; i++)
+        if (*dstp++)
+          return false;
+    }
+
+  return true;
+}
+
+
+static bool
+vbitset_subset_p (bitset dst, bitset src)
+{
+  bitset_word *srcp = VBITSET_WORDS (src);
+  bitset_word *dstp = VBITSET_WORDS (dst);
+  bitset_windex ssize = VBITSET_SIZE (src);
+  bitset_windex dsize = VBITSET_SIZE (dst);
+
+  unsigned i;
+  for (i = 0; i < min (ssize, dsize); i++, dstp++, srcp++)
+    if (*dstp != (*srcp | *dstp))
+      return false;
+
+  if (ssize > dsize)
+    for (; i < ssize; i++)
+      if (*srcp++)
+        return false;
+
+  return true;
+}
+
+
+static bool
+vbitset_disjoint_p (bitset dst, bitset src)
+{
+  bitset_word *srcp = VBITSET_WORDS (src);
+  bitset_word *dstp = VBITSET_WORDS (dst);
+  bitset_windex ssize = VBITSET_SIZE (src);
+  bitset_windex dsize = VBITSET_SIZE (dst);
+
+  for (unsigned i = 0; i < min (ssize, dsize); i++)
+    if (*srcp++ & *dstp++)
+      return false;
+
+  return true;
+}
+
+
+static void
+vbitset_and (bitset dst, bitset src1, bitset src2)
+{
+  vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2)));
+
+  bitset_windex dsize = VBITSET_SIZE (dst);
+  bitset_windex ssize1 = VBITSET_SIZE (src1);
+  bitset_windex ssize2 = VBITSET_SIZE (src2);
+  bitset_word *dstp = VBITSET_WORDS (dst);
+  bitset_word *src1p = VBITSET_WORDS (src1);
+  bitset_word *src2p = VBITSET_WORDS (src2);
+
+  for (unsigned i = 0; i < min (ssize1, ssize2); i++)
+    *dstp++ = *src1p++ & *src2p++;
+
+  memset (dstp, 0, sizeof (bitset_word) * (dsize - min (ssize1, ssize2)));
+}
+
+
+static bool
+vbitset_and_cmp (bitset dst, bitset src1, bitset src2)
+{
+  bool changed = false;
+  vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2)));
+
+  bitset_windex dsize = VBITSET_SIZE (dst);
+  bitset_windex ssize1 = VBITSET_SIZE (src1);
+  bitset_windex ssize2 = VBITSET_SIZE (src2);
+  bitset_word *dstp = VBITSET_WORDS (dst);
+  bitset_word *src1p = VBITSET_WORDS (src1);
+  bitset_word *src2p = VBITSET_WORDS (src2);
+
+  unsigned i;
+  for (i = 0; i < min (ssize1, ssize2); i++, dstp++)
+    {
+      bitset_word tmp = *src1p++ & *src2p++;
+
+      if (*dstp != tmp)
+        {
+          changed = true;
+          *dstp = tmp;
+        }
+    }
+
+  if (ssize2 > ssize1)
+    {
+      src1p = src2p;
+      ssize1 = ssize2;
+    }
+
+  for (; i < ssize1; i++, dstp++)
+    {
+      if (*dstp != 0)
+        {
+          changed = true;
+          *dstp = 0;
+        }
+    }
+
+  memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1));
+
+  return changed;
+}
+
+
+static void
+vbitset_andn (bitset dst, bitset src1, bitset src2)
+{
+  vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2)));
+
+  bitset_windex dsize = VBITSET_SIZE (dst);
+  bitset_windex ssize1 = VBITSET_SIZE (src1);
+  bitset_windex ssize2 = VBITSET_SIZE (src2);
+  bitset_word *dstp = VBITSET_WORDS (dst);
+  bitset_word *src1p = VBITSET_WORDS (src1);
+  bitset_word *src2p = VBITSET_WORDS (src2);
+
+  unsigned i;
+  for (i = 0; i < min (ssize1, ssize2); i++)
+    *dstp++ = *src1p++ & ~(*src2p++);
+
+  if (ssize2 > ssize1)
+    {
+      for (; i < ssize2; i++)
+        *dstp++ = 0;
+
+      memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize2));
+    }
+  else
+    {
+      for (; i < ssize1; i++)
+        *dstp++ = *src1p++;
+
+      memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1));
+    }
+}
+
+
+static bool
+vbitset_andn_cmp (bitset dst, bitset src1, bitset src2)
+{
+  bool changed = false;
+  vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2)));
+
+  bitset_windex dsize = VBITSET_SIZE (dst);
+  bitset_windex ssize1 = VBITSET_SIZE (src1);
+  bitset_windex ssize2 = VBITSET_SIZE (src2);
+  bitset_word *dstp = VBITSET_WORDS (dst);
+  bitset_word *src1p = VBITSET_WORDS (src1);
+  bitset_word *src2p = VBITSET_WORDS (src2);
+
+  unsigned i;
+  for (i = 0; i < min (ssize1, ssize2); i++, dstp++)
+    {
+      bitset_word tmp = *src1p++ & ~(*src2p++);
+
+      if (*dstp != tmp)
+        {
+          changed = true;
+          *dstp = tmp;
+        }
+    }
+
+  if (ssize2 > ssize1)
+    {
+      for (; i < ssize2; i++, dstp++)
+        {
+          if (*dstp != 0)
+            {
+              changed = true;
+              *dstp = 0;
+            }
+        }
+
+      memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize2));
+    }
+  else
+    {
+      for (; i < ssize1; i++, dstp++)
+        {
+          bitset_word tmp = *src1p++;
+
+          if (*dstp != tmp)
+            {
+              changed = true;
+              *dstp = tmp;
+            }
+        }
+
+      memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1));
+    }
+
+  return changed;
+}
+
+
+static void
+vbitset_or (bitset dst, bitset src1, bitset src2)
+{
+  vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2)));
+
+  bitset_windex dsize = VBITSET_SIZE (dst);
+  bitset_windex ssize1 = VBITSET_SIZE (src1);
+  bitset_windex ssize2 = VBITSET_SIZE (src2);
+  bitset_word *dstp = VBITSET_WORDS (dst);
+  bitset_word *src1p = VBITSET_WORDS (src1);
+  bitset_word *src2p = VBITSET_WORDS (src2);
+
+  unsigned i;
+  for (i = 0; i < min (ssize1, ssize2); i++)
+    *dstp++ = *src1p++ | *src2p++;
+
+  if (ssize2 > ssize1)
+    {
+      src1p = src2p;
+      ssize1 = ssize2;
+    }
+
+  for (; i < ssize1; i++)
+    *dstp++ = *src1p++;
+
+  memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1));
+}
+
+
+static bool
+vbitset_or_cmp (bitset dst, bitset src1, bitset src2)
+{
+  bool changed = false;
+
+  vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2)));
+
+  bitset_windex dsize = VBITSET_SIZE (dst);
+  bitset_windex ssize1 = VBITSET_SIZE (src1);
+  bitset_windex ssize2 = VBITSET_SIZE (src2);
+  bitset_word *dstp = VBITSET_WORDS (dst);
+  bitset_word *src1p = VBITSET_WORDS (src1);
+  bitset_word *src2p = VBITSET_WORDS (src2);
+
+  unsigned i;
+  for (i = 0; i < min (ssize1, ssize2); i++, dstp++)
+    {
+      bitset_word tmp = *src1p++ | *src2p++;
+
+      if (*dstp != tmp)
+        {
+          changed = true;
+          *dstp = tmp;
+        }
+    }
+
+  if (ssize2 > ssize1)
+    {
+      src1p = src2p;
+      ssize1 = ssize2;
+    }
+
+  for (; i < ssize1; i++, dstp++)
+    {
+      bitset_word tmp = *src1p++;
+
+      if (*dstp != tmp)
+        {
+          changed = true;
+          *dstp = tmp;
+        }
+    }
+
+  memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1));
+
+  return changed;
+}
+
+
+static void
+vbitset_xor (bitset dst, bitset src1, bitset src2)
+{
+  vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2)));
+
+  bitset_windex dsize = VBITSET_SIZE (dst);
+  bitset_windex ssize1 = VBITSET_SIZE (src1);
+  bitset_windex ssize2 = VBITSET_SIZE (src2);
+  bitset_word *dstp = VBITSET_WORDS (dst);
+  bitset_word *src1p = VBITSET_WORDS (src1);
+  bitset_word *src2p = VBITSET_WORDS (src2);
+
+  unsigned i;
+  for (i = 0; i < min (ssize1, ssize2); i++)
+    *dstp++ = *src1p++ ^ *src2p++;
+
+  if (ssize2 > ssize1)
+    {
+      src1p = src2p;
+      ssize1 = ssize2;
+    }
+
+  for (; i < ssize1; i++)
+    *dstp++ = *src1p++;
+
+  memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1));
+}
+
+
+static bool
+vbitset_xor_cmp (bitset dst, bitset src1, bitset src2)
+{
+  bool changed = false;
+  vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2)));
+
+  bitset_windex dsize = VBITSET_SIZE (dst);
+  bitset_windex ssize1 = VBITSET_SIZE (src1);
+  bitset_windex ssize2 = VBITSET_SIZE (src2);
+  bitset_word *dstp = VBITSET_WORDS (dst);
+  bitset_word *src1p = VBITSET_WORDS (src1);
+  bitset_word *src2p = VBITSET_WORDS (src2);
+
+  unsigned i;
+  for (i = 0; i < min (ssize1, ssize2); i++, dstp++)
+    {
+      bitset_word tmp = *src1p++ ^ *src2p++;
+
+      if (*dstp != tmp)
+        {
+          changed = true;
+          *dstp = tmp;
+        }
+    }
+
+  if (ssize2 > ssize1)
+    {
+      src1p = src2p;
+      ssize1 = ssize2;
+    }
+
+  for (; i < ssize1; i++, dstp++)
+    {
+      bitset_word tmp = *src1p++;
+
+      if (*dstp != tmp)
+        {
+          changed = true;
+          *dstp = tmp;
+        }
+    }
+
+  memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1));
+
+  return changed;
+}
+
+
+/* FIXME, these operations need fixing for different size
+   bitsets.  */
+
+static void
+vbitset_and_or (bitset dst, bitset src1, bitset src2, bitset src3)
+{
+  if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2)
+      || BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3))
+    {
+      bitset_and_or_ (dst, src1, src2, src3);
+      return;
+    }
+
+  vbitset_resize (dst, BITSET_NBITS_ (src1));
+
+  bitset_word *src1p = VBITSET_WORDS (src1);
+  bitset_word *src2p = VBITSET_WORDS (src2);
+  bitset_word *src3p = VBITSET_WORDS (src3);
+  bitset_word *dstp = VBITSET_WORDS (dst);
+  bitset_windex size = VBITSET_SIZE (dst);
+
+  for (unsigned i = 0; i < size; i++)
+    *dstp++ = (*src1p++ & *src2p++) | *src3p++;
+}
+
+
+static bool
+vbitset_and_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
+{
+  if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2)
+      || BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3))
+    return bitset_and_or_cmp_ (dst, src1, src2, src3);
+
+  vbitset_resize (dst, BITSET_NBITS_ (src1));
+
+  bitset_word *src1p = VBITSET_WORDS (src1);
+  bitset_word *src2p = VBITSET_WORDS (src2);
+  bitset_word *src3p = VBITSET_WORDS (src3);
+  bitset_word *dstp = VBITSET_WORDS (dst);
+  bitset_windex size = VBITSET_SIZE (dst);
+
+  bool changed = false;
+  for (unsigned i = 0; i < size; i++, dstp++)
+    {
+      bitset_word tmp = (*src1p++ & *src2p++) | *src3p++;
+
+      if (*dstp != tmp)
+        {
+          changed = true;
+          *dstp = tmp;
+        }
+    }
+  return changed;
+}
+
+
+static void
+vbitset_andn_or (bitset dst, bitset src1, bitset src2, bitset src3)
+{
+  if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2)
+      || BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3))
+    {
+      bitset_andn_or_ (dst, src1, src2, src3);
+      return;
+    }
+
+  vbitset_resize (dst, BITSET_NBITS_ (src1));
+
+  bitset_word *src1p = VBITSET_WORDS (src1);
+  bitset_word *src2p = VBITSET_WORDS (src2);
+  bitset_word *src3p = VBITSET_WORDS (src3);
+  bitset_word *dstp = VBITSET_WORDS (dst);
+  bitset_windex size = VBITSET_SIZE (dst);
+
+  for (unsigned i = 0; i < size; i++)
+    *dstp++ = (*src1p++ & ~(*src2p++)) | *src3p++;
+}
+
+
+static bool
+vbitset_andn_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
+{
+  if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2)
+      || BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3))
+    return bitset_andn_or_cmp_ (dst, src1, src2, src3);
+
+  vbitset_resize (dst, BITSET_NBITS_ (src1));
+
+  bitset_word *src1p = VBITSET_WORDS (src1);
+  bitset_word *src2p = VBITSET_WORDS (src2);
+  bitset_word *src3p = VBITSET_WORDS (src3);
+  bitset_word *dstp = VBITSET_WORDS (dst);
+  bitset_windex size = VBITSET_SIZE (dst);
+
+  bool changed = false;
+  for (unsigned i = 0; i < size; i++, dstp++)
+    {
+      bitset_word tmp = (*src1p++ & ~(*src2p++)) | *src3p++;
+
+      if (*dstp != tmp)
+        {
+          changed = true;
+          *dstp = tmp;
+        }
+    }
+  return changed;
+}
+
+
+static void
+vbitset_or_and (bitset dst, bitset src1, bitset src2, bitset src3)
+{
+  if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2)
+      || BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3))
+    {
+      bitset_or_and_ (dst, src1, src2, src3);
+      return;
+    }
+
+  vbitset_resize (dst, BITSET_NBITS_ (src1));
+
+  bitset_word *src1p = VBITSET_WORDS (src1);
+  bitset_word *src2p = VBITSET_WORDS (src2);
+  bitset_word *src3p = VBITSET_WORDS (src3);
+  bitset_word *dstp = VBITSET_WORDS (dst);
+  bitset_windex size = VBITSET_SIZE (dst);
+
+  for (unsigned i = 0; i < size; i++)
+    *dstp++ = (*src1p++ | *src2p++) & *src3p++;
+}
+
+
+static bool
+vbitset_or_and_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
+{
+  if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2)
+      || BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3))
+    return bitset_or_and_cmp_ (dst, src1, src2, src3);
+
+  vbitset_resize (dst, BITSET_NBITS_ (src1));
+
+  bitset_word *src1p = VBITSET_WORDS (src1);
+  bitset_word *src2p = VBITSET_WORDS (src2);
+  bitset_word *src3p = VBITSET_WORDS (src3);
+  bitset_word *dstp = VBITSET_WORDS (dst);
+  bitset_windex size = VBITSET_SIZE (dst);
+
+  unsigned i;
+  bool changed = false;
+  for (i = 0; i < size; i++, dstp++)
+    {
+      bitset_word tmp = (*src1p++ | *src2p++) & *src3p++;
+
+      if (*dstp != tmp)
+        {
+          changed = true;
+          *dstp = tmp;
+        }
+    }
+  return changed;
+}
+
+
+static void
+vbitset_copy (bitset dst, bitset src)
+{
+  if (BITSET_COMPATIBLE_ (dst, src))
+    vbitset_copy1 (dst, src);
+  else
+    bitset_copy_ (dst, src);
+}
+
+
+/* Vector of operations for multiple word bitsets.  */
+struct bitset_vtable vbitset_vtable = {
+  vbitset_set,
+  vbitset_reset,
+  bitset_toggle_,
+  vbitset_test,
+  vbitset_resize,
+  bitset_size_,
+  bitset_count_,
+  vbitset_empty_p,
+  vbitset_ones,
+  vbitset_zero,
+  vbitset_copy,
+  vbitset_disjoint_p,
+  vbitset_equal_p,
+  vbitset_not,
+  vbitset_subset_p,
+  vbitset_and,
+  vbitset_and_cmp,
+  vbitset_andn,
+  vbitset_andn_cmp,
+  vbitset_or,
+  vbitset_or_cmp,
+  vbitset_xor,
+  vbitset_xor_cmp,
+  vbitset_and_or,
+  vbitset_and_or_cmp,
+  vbitset_andn_or,
+  vbitset_andn_or_cmp,
+  vbitset_or_and,
+  vbitset_or_and_cmp,
+  vbitset_list,
+  vbitset_list_reverse,
+  NULL,
+  BITSET_VECTOR
+};
+
+
+size_t
+vbitset_bytes (bitset_bindex n_bits ATTRIBUTE_UNUSED)
+{
+  return sizeof (struct vbitset_struct);
+}
+
+
+bitset
+vbitset_init (bitset bset, bitset_bindex n_bits)
+{
+  bset->b.vtable = &vbitset_vtable;
+  bset->b.cindex = 0;
+  VBITSET_SIZE (bset) = 0;
+  vbitset_resize (bset, n_bits);
+  return bset;
+}
diff --git a/contrib/tools/bison/lib/bitset/vector.h b/contrib/tools/bison/lib/bitset/vector.h
new file mode 100644
index 0000000000..1f5b94dea0
--- /dev/null
+++ b/contrib/tools/bison/lib/bitset/vector.h
@@ -0,0 +1,30 @@
+/* Functions to support vbitsets.
+
+   Copyright (C) 2002, 2004, 2009-2015, 2018-2019 Free Software Foundation,
+   Inc.
+
+   Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz).
+
+   This program is free software: you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation, either version 3 of the License, or
+   (at your option) any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
+
+#ifndef _BITSET_VECTOR_H
+#define _BITSET_VECTOR_H
+
+#include "bitset.h"
+
+size_t vbitset_bytes (bitset_bindex);
+
+bitset vbitset_init (bitset, bitset_bindex);
+
+#endif