YT-19430: Add arrow writer

Add arrow writer

3 files changed, 2118 insertions, 0 deletions

diff --git a/contrib/libs/backtrace/macho.c b/contrib/libs/backtrace/macho.c
new file mode 100644
index 0000000000..d00aea9bc8
--- /dev/null
+++ b/contrib/libs/backtrace/macho.c
@@ -0,0 +1,1355 @@
+/* elf.c -- Get debug data from a Mach-O file for backtraces.
+   Copyright (C) 2020-2021 Free Software Foundation, Inc.
+   Written by Ian Lance Taylor, Google.
+
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are
+met:
+
+    (1) Redistributions of source code must retain the above copyright
+    notice, this list of conditions and the following disclaimer.
+
+    (2) Redistributions in binary form must reproduce the above copyright
+    notice, this list of conditions and the following disclaimer in
+    the documentation and/or other materials provided with the
+    distribution.
+
+    (3) The name of the author may not be used to
+    endorse or promote products derived from this software without
+    specific prior written permission.
+
+THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
+WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT,
+INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
+(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
+HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
+IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
+POSSIBILITY OF SUCH DAMAGE.  */
+
+#include "config.h"
+
+#include <sys/types.h>
+#include <dirent.h>
+#include <stdlib.h>
+#include <string.h>
+
+#ifdef HAVE_MACH_O_DYLD_H
+#include <mach-o/dyld.h>
+#endif
+
+#include "backtrace.h"
+#include "internal.h"
+
+/* Mach-O file header for a 32-bit executable.  */
+
+struct macho_header_32
+{
+  uint32_t magic;	/* Magic number (MACH_O_MAGIC_32) */
+  uint32_t cputype;	/* CPU type */
+  uint32_t cpusubtype;	/* CPU subtype */
+  uint32_t filetype;	/* Type of file (object, executable) */
+  uint32_t ncmds;	/* Number of load commands */
+  uint32_t sizeofcmds;	/* Total size of load commands */
+  uint32_t flags;	/* Flags for special features */
+};
+
+/* Mach-O file header for a 64-bit executable.  */
+
+struct macho_header_64
+{
+  uint32_t magic;	/* Magic number (MACH_O_MAGIC_64) */
+  uint32_t cputype;	/* CPU type */
+  uint32_t cpusubtype;	/* CPU subtype */
+  uint32_t filetype;	/* Type of file (object, executable) */
+  uint32_t ncmds;	/* Number of load commands */
+  uint32_t sizeofcmds;	/* Total size of load commands */
+  uint32_t flags;	/* Flags for special features */
+  uint32_t reserved;	/* Reserved */
+};
+
+/* Mach-O file header for a fat executable.  */
+
+struct macho_header_fat
+{
+  uint32_t magic;	/* Magic number (MACH_O_MH_(MAGIC|CIGAM)_FAT(_64)?) */
+  uint32_t nfat_arch;   /* Number of components */
+};
+
+/* Values for the header magic field.  */
+
+#define MACH_O_MH_MAGIC_32	0xfeedface
+#define MACH_O_MH_MAGIC_64	0xfeedfacf
+#define MACH_O_MH_MAGIC_FAT	0xcafebabe
+#define MACH_O_MH_CIGAM_FAT	0xbebafeca
+#define MACH_O_MH_MAGIC_FAT_64	0xcafebabf
+#define MACH_O_MH_CIGAM_FAT_64	0xbfbafeca
+
+/* Value for the header filetype field.  */
+
+#define MACH_O_MH_EXECUTE	0x02
+#define MACH_O_MH_DYLIB		0x06
+#define MACH_O_MH_DSYM		0x0a
+
+/* A component of a fat file.  A fat file starts with a
+   macho_header_fat followed by nfat_arch instances of this
+   struct.  */
+
+struct macho_fat_arch
+{
+  uint32_t cputype;	/* CPU type */
+  uint32_t cpusubtype;	/* CPU subtype */
+  uint32_t offset;	/* File offset of this entry */
+  uint32_t size;	/* Size of this entry */
+  uint32_t align;	/* Alignment of this entry */
+};
+
+/* A component of a 64-bit fat file.  This is used if the magic field
+   is MAGIC_FAT_64.  This is only used when some file size or file
+   offset is too large to represent in the 32-bit format.  */
+
+struct macho_fat_arch_64
+{
+  uint32_t cputype;	/* CPU type */
+  uint32_t cpusubtype;	/* CPU subtype */
+  uint64_t offset;	/* File offset of this entry */
+  uint64_t size;	/* Size of this entry */
+  uint32_t align;	/* Alignment of this entry */
+  uint32_t reserved;	/* Reserved */
+};
+
+/* Values for the fat_arch cputype field (and the header cputype
+   field).  */
+
+#define MACH_O_CPU_ARCH_ABI64 0x01000000
+
+#define MACH_O_CPU_TYPE_X86 7
+#define MACH_O_CPU_TYPE_ARM 12
+#define MACH_O_CPU_TYPE_PPC 18
+
+#define MACH_O_CPU_TYPE_X86_64 (MACH_O_CPU_TYPE_X86 | MACH_O_CPU_ARCH_ABI64)
+#define MACH_O_CPU_TYPE_ARM64  (MACH_O_CPU_TYPE_ARM | MACH_O_CPU_ARCH_ABI64)
+#define MACH_O_CPU_TYPE_PPC64  (MACH_O_CPU_TYPE_PPC | MACH_O_CPU_ARCH_ABI64)
+
+/* The header of a load command.  */
+
+struct macho_load_command
+{
+  uint32_t cmd;		/* The type of load command */
+  uint32_t cmdsize;	/* Size in bytes of the entire command */
+};
+
+/* Values for the load_command cmd field.  */
+
+#define MACH_O_LC_SEGMENT	0x01
+#define MACH_O_LC_SYMTAB	0x02
+#define MACH_O_LC_SEGMENT_64	0x19
+#define MACH_O_LC_UUID		0x1b
+
+/* The length of a section of segment name.  */
+
+#define MACH_O_NAMELEN (16)
+
+/* LC_SEGMENT load command.  */
+
+struct macho_segment_command
+{
+  uint32_t cmd;			/* The type of load command (LC_SEGMENT) */
+  uint32_t cmdsize;		/* Size in bytes of the entire command */
+  char segname[MACH_O_NAMELEN];	/* Segment name */
+  uint32_t vmaddr;		/* Virtual memory address */
+  uint32_t vmsize;		/* Virtual memory size */
+  uint32_t fileoff;		/* Offset of data to be mapped */
+  uint32_t filesize;		/* Size of data in file */
+  uint32_t maxprot;		/* Maximum permitted virtual protection */
+  uint32_t initprot;		/* Initial virtual memory protection */
+  uint32_t nsects;		/* Number of sections in this segment */
+  uint32_t flags;		/* Flags */
+};
+
+/* LC_SEGMENT_64 load command.  */
+
+struct macho_segment_64_command
+{
+  uint32_t cmd;			/* The type of load command (LC_SEGMENT) */
+  uint32_t cmdsize;		/* Size in bytes of the entire command */
+  char segname[MACH_O_NAMELEN];	/* Segment name */
+  uint64_t vmaddr;		/* Virtual memory address */
+  uint64_t vmsize;		/* Virtual memory size */
+  uint64_t fileoff;		/* Offset of data to be mapped */
+  uint64_t filesize;		/* Size of data in file */
+  uint32_t maxprot;		/* Maximum permitted virtual protection */
+  uint32_t initprot;		/* Initial virtual memory protection */
+  uint32_t nsects;		/* Number of sections in this segment */
+  uint32_t flags;		/* Flags */
+};
+
+/* LC_SYMTAB load command.  */
+
+struct macho_symtab_command
+{
+  uint32_t cmd;		/* The type of load command (LC_SEGMENT) */
+  uint32_t cmdsize;	/* Size in bytes of the entire command */
+  uint32_t symoff;	/* File offset of symbol table */
+  uint32_t nsyms;	/* Number of symbols */
+  uint32_t stroff;	/* File offset of string table */
+  uint32_t strsize;	/* String table size */
+};
+
+/* The length of a Mach-O uuid.  */
+
+#define MACH_O_UUID_LEN (16)
+
+/* LC_UUID load command.  */
+
+struct macho_uuid_command
+{
+  uint32_t cmd;				/* Type of load command (LC_UUID) */
+  uint32_t cmdsize;			/* Size in bytes of command */
+  unsigned char uuid[MACH_O_UUID_LEN];	/* UUID */
+};
+
+/* 32-bit section header within a LC_SEGMENT segment.  */
+
+struct macho_section
+{
+  char sectname[MACH_O_NAMELEN];	/* Section name */
+  char segment[MACH_O_NAMELEN];		/* Segment of this section */
+  uint32_t addr;			/* Address in memory */
+  uint32_t size;			/* Section size */
+  uint32_t offset;			/* File offset */
+  uint32_t align;			/* Log2 of section alignment */
+  uint32_t reloff;			/* File offset of relocations */
+  uint32_t nreloc;			/* Number of relocs for this section */
+  uint32_t flags;			/* Flags */
+  uint32_t reserved1;
+  uint32_t reserved2;
+};
+
+/* 64-bit section header within a LC_SEGMENT_64 segment.   */
+
+struct macho_section_64
+{
+  char sectname[MACH_O_NAMELEN];	/* Section name */
+  char segment[MACH_O_NAMELEN];		/* Segment of this section */
+  uint64_t addr;			/* Address in memory */
+  uint64_t size;			/* Section size */
+  uint32_t offset;			/* File offset */
+  uint32_t align;			/* Log2 of section alignment */
+  uint32_t reloff;			/* File offset of section relocations */
+  uint32_t nreloc;			/* Number of relocs for this section */
+  uint32_t flags;			/* Flags */
+  uint32_t reserved1;
+  uint32_t reserved2;
+  uint32_t reserved3;
+};
+
+/* 32-bit symbol data.  */
+
+struct macho_nlist
+{
+  uint32_t n_strx;	/* Index of name in string table */
+  uint8_t n_type;	/* Type flag */
+  uint8_t n_sect;	/* Section number */
+  uint16_t n_desc;	/* Stabs description field */
+  uint32_t n_value;	/* Value */
+};
+
+/* 64-bit symbol data.  */
+
+struct macho_nlist_64
+{
+  uint32_t n_strx;	/* Index of name in string table */
+  uint8_t n_type;	/* Type flag */
+  uint8_t n_sect;	/* Section number */
+  uint16_t n_desc;	/* Stabs description field */
+  uint64_t n_value;	/* Value */
+};
+
+/* Value found in nlist n_type field.  */
+
+#define MACH_O_N_EXT	0x01	/* Extern symbol */
+#define MACH_O_N_ABS	0x02	/* Absolute symbol */
+#define MACH_O_N_SECT	0x0e	/* Defined in section */
+
+#define MACH_O_N_TYPE	0x0e	/* Mask for type bits */
+#define MACH_O_N_STAB	0xe0	/* Stabs debugging symbol */
+
+/* Information we keep for a Mach-O symbol.  */
+
+struct macho_symbol
+{
+  const char *name;	/* Symbol name */
+  uintptr_t address;	/* Symbol address */
+};
+
+/* Information to pass to macho_syminfo.  */
+
+struct macho_syminfo_data
+{
+  struct macho_syminfo_data *next;	/* Next module */
+  struct macho_symbol *symbols;		/* Symbols sorted by address */
+  size_t count;				/* Number of symbols */
+};
+
+/* Names of sections, indexed by enum dwarf_section in internal.h.  */
+
+static const char * const dwarf_section_names[DEBUG_MAX] =
+{
+  "__debug_info",
+  "__debug_line",
+  "__debug_abbrev",
+  "__debug_ranges",
+  "__debug_str",
+  "", /* DEBUG_ADDR */
+  "__debug_str_offs",
+  "", /* DEBUG_LINE_STR */
+  "__debug_rnglists"
+};
+
+/* Forward declaration.  */
+
+static int macho_add (struct backtrace_state *, const char *, int, off_t,
+		      const unsigned char *, uintptr_t, int,
+		      backtrace_error_callback, void *, fileline *, int *);
+
+/* A dummy callback function used when we can't find any debug info.  */
+
+static int
+macho_nodebug (struct backtrace_state *state ATTRIBUTE_UNUSED,
+	       uintptr_t pc ATTRIBUTE_UNUSED,
+	       backtrace_full_callback callback ATTRIBUTE_UNUSED,
+	       backtrace_error_callback error_callback, void *data)
+{
+  error_callback (data, "no debug info in Mach-O executable", -1);
+  return 0;
+}
+
+/* A dummy callback function used when we can't find a symbol
+   table.  */
+
+static void
+macho_nosyms (struct backtrace_state *state ATTRIBUTE_UNUSED,
+	      uintptr_t addr ATTRIBUTE_UNUSED,
+	      backtrace_syminfo_callback callback ATTRIBUTE_UNUSED,
+	      backtrace_error_callback error_callback, void *data)
+{
+  error_callback (data, "no symbol table in Mach-O executable", -1);
+}
+
+/* Add a single DWARF section to DWARF_SECTIONS, if we need the
+   section.  Returns 1 on success, 0 on failure.  */
+
+static int
+macho_add_dwarf_section (struct backtrace_state *state, int descriptor,
+			 const char *sectname, uint32_t offset, uint64_t size,
+			 backtrace_error_callback error_callback, void *data,
+			 struct dwarf_sections *dwarf_sections)
+{
+  int i;
+
+  for (i = 0; i < (int) DEBUG_MAX; ++i)
+    {
+      if (dwarf_section_names[i][0] != '\0'
+	  && strncmp (sectname, dwarf_section_names[i], MACH_O_NAMELEN) == 0)
+	{
+	  struct backtrace_view section_view;
+
+	  /* FIXME: Perhaps it would be better to try to use a single
+	     view to read all the DWARF data, as we try to do for
+	     ELF.  */
+
+	  if (!backtrace_get_view (state, descriptor, offset, size,
+				   error_callback, data, &section_view))
+	    return 0;
+	  dwarf_sections->data[i] = (const unsigned char *) section_view.data;
+	  dwarf_sections->size[i] = size;
+	  break;
+	}
+    }
+  return 1;
+}
+
+/* Collect DWARF sections from a DWARF segment.  Returns 1 on success,
+   0 on failure.  */
+
+static int
+macho_add_dwarf_segment (struct backtrace_state *state, int descriptor,
+			 off_t offset, unsigned int cmd, const char *psecs,
+			 size_t sizesecs, unsigned int nsects,
+			 backtrace_error_callback error_callback, void *data,
+			 struct dwarf_sections *dwarf_sections)
+{
+  size_t sec_header_size;
+  size_t secoffset;
+  unsigned int i;
+
+  switch (cmd)
+    {
+    case MACH_O_LC_SEGMENT:
+      sec_header_size = sizeof (struct macho_section);
+      break;
+    case MACH_O_LC_SEGMENT_64:
+      sec_header_size = sizeof (struct macho_section_64);
+      break;
+    default:
+      abort ();
+    }
+
+  secoffset = 0;
+  for (i = 0; i < nsects; ++i)
+    {
+      if (secoffset + sec_header_size > sizesecs)
+	{
+	  error_callback (data, "section overflow withing segment", 0);
+	  return 0;
+	}
+
+      switch (cmd)
+	{
+	case MACH_O_LC_SEGMENT:
+	  {
+	    struct macho_section section;
+
+	    memcpy (&section, psecs + secoffset, sizeof section);
+	    macho_add_dwarf_section (state, descriptor, section.sectname,
+				     offset + section.offset, section.size,
+				     error_callback, data, dwarf_sections);
+	  }
+	  break;
+
+	case MACH_O_LC_SEGMENT_64:
+	  {
+	    struct macho_section_64 section;
+
+	    memcpy (&section, psecs + secoffset, sizeof section);
+	    macho_add_dwarf_section (state, descriptor, section.sectname,
+				     offset + section.offset, section.size,
+				     error_callback, data, dwarf_sections);
+	  }
+	  break;
+
+	default:
+	  abort ();
+	}
+
+      secoffset += sec_header_size;
+    }
+
+  return 1;
+}
+
+/* Compare struct macho_symbol for qsort.  */
+
+static int
+macho_symbol_compare (const void *v1, const void *v2)
+{
+  const struct macho_symbol *m1 = (const struct macho_symbol *) v1;
+  const struct macho_symbol *m2 = (const struct macho_symbol *) v2;
+
+  if (m1->address < m2->address)
+    return -1;
+  else if (m1->address > m2->address)
+    return 1;
+  else
+    return 0;
+}
+
+/* Compare an address against a macho_symbol for bsearch.  We allocate
+   one extra entry in the array so that this can safely look at the
+   next entry.  */
+
+static int
+macho_symbol_search (const void *vkey, const void *ventry)
+{
+  const uintptr_t *key = (const uintptr_t *) vkey;
+  const struct macho_symbol *entry = (const struct macho_symbol *) ventry;
+  uintptr_t addr;
+
+  addr = *key;
+  if (addr < entry->address)
+    return -1;
+  else if (entry->name[0] == '\0'
+	   && entry->address == ~(uintptr_t) 0)
+    return -1;
+  else if ((entry + 1)->name[0] == '\0'
+	   && (entry + 1)->address == ~(uintptr_t) 0)
+    return -1;
+  else if (addr >= (entry + 1)->address)
+    return 1;
+  else
+    return 0;
+}
+
+/* Return whether the symbol type field indicates a symbol table entry
+   that we care about: a function or data symbol.  */
+
+static int
+macho_defined_symbol (uint8_t type)
+{
+  if ((type & MACH_O_N_STAB) != 0)
+    return 0;
+  if ((type & MACH_O_N_EXT) != 0)
+    return 0;
+  switch (type & MACH_O_N_TYPE)
+    {
+    case MACH_O_N_ABS:
+      return 1;
+    case MACH_O_N_SECT:
+      return 1;
+    default:
+      return 0;
+    }
+}
+
+/* Add symbol table information for a Mach-O file.  */
+
+static int
+macho_add_symtab (struct backtrace_state *state, int descriptor,
+		  uintptr_t base_address, int is_64,
+		  off_t symoff, unsigned int nsyms, off_t stroff,
+		  unsigned int strsize,
+		  backtrace_error_callback error_callback, void *data)
+{
+  size_t symsize;
+  struct backtrace_view sym_view;
+  int sym_view_valid;
+  struct backtrace_view str_view;
+  int str_view_valid;
+  size_t ndefs;
+  size_t symtaboff;
+  unsigned int i;
+  size_t macho_symbol_size;
+  struct macho_symbol *macho_symbols;
+  unsigned int j;
+  struct macho_syminfo_data *sdata;
+
+  sym_view_valid = 0;
+  str_view_valid = 0;
+  macho_symbol_size = 0;
+  macho_symbols = NULL;
+
+  if (is_64)
+    symsize = sizeof (struct macho_nlist_64);
+  else
+    symsize = sizeof (struct macho_nlist);
+
+  if (!backtrace_get_view (state, descriptor, symoff, nsyms * symsize,
+			   error_callback, data, &sym_view))
+    goto fail;
+  sym_view_valid = 1;
+
+  if (!backtrace_get_view (state, descriptor, stroff, strsize,
+			   error_callback, data, &str_view))
+    return 0;
+  str_view_valid = 1;
+
+  ndefs = 0;
+  symtaboff = 0;
+  for (i = 0; i < nsyms; ++i, symtaboff += symsize)
+    {
+      if (is_64)
+	{
+	  struct macho_nlist_64 nlist;
+
+	  memcpy (&nlist, (const char *) sym_view.data + symtaboff,
+		  sizeof nlist);
+	  if (macho_defined_symbol (nlist.n_type))
+	    ++ndefs;
+	}
+      else
+	{
+	  struct macho_nlist nlist;
+
+	  memcpy (&nlist, (const char *) sym_view.data + symtaboff,
+		  sizeof nlist);
+	  if (macho_defined_symbol (nlist.n_type))
+	    ++ndefs;
+	}
+    }
+
+  /* Add 1 to ndefs to make room for a sentinel.  */
+  macho_symbol_size = (ndefs + 1) * sizeof (struct macho_symbol);
+  macho_symbols = ((struct macho_symbol *)
+		   backtrace_alloc (state, macho_symbol_size, error_callback,
+				    data));
+  if (macho_symbols == NULL)
+    goto fail;
+
+  j = 0;
+  symtaboff = 0;
+  for (i = 0; i < nsyms; ++i, symtaboff += symsize)
+    {
+      uint32_t strx;
+      uint64_t value;
+      const char *name;
+
+      strx = 0;
+      value = 0;
+      if (is_64)
+	{
+	  struct macho_nlist_64 nlist;
+
+	  memcpy (&nlist, (const char *) sym_view.data + symtaboff,
+		  sizeof nlist);
+	  if (!macho_defined_symbol (nlist.n_type))
+	    continue;
+
+	  strx = nlist.n_strx;
+	  value = nlist.n_value;
+	}
+      else
+	{
+	  struct macho_nlist nlist;
+
+	  memcpy (&nlist, (const char *) sym_view.data + symtaboff,
+		  sizeof nlist);
+	  if (!macho_defined_symbol (nlist.n_type))
+	    continue;
+
+	  strx = nlist.n_strx;
+	  value = nlist.n_value;
+	}
+
+      if (strx >= strsize)
+	{
+	  error_callback (data, "symbol string index out of range", 0);
+	  goto fail;
+	}
+
+      name = (const char *) str_view.data + strx;
+      if (name[0] == '_')
+	++name;
+      macho_symbols[j].name = name;
+      macho_symbols[j].address = value + base_address;
+      ++j;
+    }
+
+  sdata = ((struct macho_syminfo_data *)
+	   backtrace_alloc (state, sizeof *sdata, error_callback, data));
+  if (sdata == NULL)
+    goto fail;
+
+  /* We need to keep the string table since it holds the names, but we
+     can release the symbol table.  */
+
+  backtrace_release_view (state, &sym_view, error_callback, data);
+  sym_view_valid = 0;
+  str_view_valid = 0;
+
+  /* Add a trailing sentinel symbol.  */
+  macho_symbols[j].name = "";
+  macho_symbols[j].address = ~(uintptr_t) 0;
+
+  backtrace_qsort (macho_symbols, ndefs + 1, sizeof (struct macho_symbol),
+		   macho_symbol_compare);
+
+  sdata->next = NULL;
+  sdata->symbols = macho_symbols;
+  sdata->count = ndefs;
+
+  if (!state->threaded)
+    {
+      struct macho_syminfo_data **pp;
+
+      for (pp = (struct macho_syminfo_data **) (void *) &state->syminfo_data;
+	   *pp != NULL;
+	   pp = &(*pp)->next)
+	;
+      *pp = sdata;
+    }
+  else
+    {
+      while (1)
+	{
+	  struct macho_syminfo_data **pp;
+
+	  pp = (struct macho_syminfo_data **) (void *) &state->syminfo_data;
+
+	  while (1)
+	    {
+	      struct macho_syminfo_data *p;
+
+	      p = backtrace_atomic_load_pointer (pp);
+	      
+	      if (p == NULL)
+		break;
+
+	      pp = &p->next;
+	    }
+
+	  if (__sync_bool_compare_and_swap (pp, NULL, sdata))
+	    break;
+	}
+    }
+
+  return 1;
+
+ fail:
+  if (macho_symbols != NULL)
+    backtrace_free (state, macho_symbols, macho_symbol_size,
+		    error_callback, data);
+  if (sym_view_valid)
+    backtrace_release_view (state, &sym_view, error_callback, data);
+  if (str_view_valid)
+    backtrace_release_view (state, &str_view, error_callback, data);
+  return 0;
+}
+
+/* Return the symbol name and value for an ADDR.  */
+
+static void
+macho_syminfo (struct backtrace_state *state, uintptr_t addr,
+	       backtrace_syminfo_callback callback,
+	       backtrace_error_callback error_callback ATTRIBUTE_UNUSED,
+	       void *data)
+{
+  struct macho_syminfo_data *sdata;
+  struct macho_symbol *sym;
+
+  sym = NULL;
+  if (!state->threaded)
+    {
+      for (sdata = (struct macho_syminfo_data *) state->syminfo_data;
+	   sdata != NULL;
+	   sdata = sdata->next)
+	{
+	  sym = ((struct macho_symbol *)
+		 bsearch (&addr, sdata->symbols, sdata->count,
+			  sizeof (struct macho_symbol), macho_symbol_search));
+	  if (sym != NULL)
+	    break;
+	}
+    }
+  else
+    {
+      struct macho_syminfo_data **pp;
+
+      pp = (struct macho_syminfo_data **) (void *) &state->syminfo_data;
+      while (1)
+	{
+	  sdata = backtrace_atomic_load_pointer (pp);
+	  if (sdata == NULL)
+	    break;
+
+	  sym = ((struct macho_symbol *)
+		 bsearch (&addr, sdata->symbols, sdata->count,
+			  sizeof (struct macho_symbol), macho_symbol_search));
+	  if (sym != NULL)
+	    break;
+
+	  pp = &sdata->next;
+	}
+    }
+
+  if (sym == NULL)
+    callback (data, addr, NULL, 0, 0);
+  else
+    callback (data, addr, sym->name, sym->address, 0);
+}
+
+/* Look through a fat file to find the relevant executable.  Returns 1
+   on success, 0 on failure (in both cases descriptor is closed).  */
+
+static int
+macho_add_fat (struct backtrace_state *state, const char *filename,
+	       int descriptor, int swapped, off_t offset,
+	       const unsigned char *match_uuid, uintptr_t base_address,
+	       int skip_symtab, uint32_t nfat_arch, int is_64,
+	       backtrace_error_callback error_callback, void *data,
+	       fileline *fileline_fn, int *found_sym)
+{
+  int arch_view_valid;
+  unsigned int cputype;
+  size_t arch_size;
+  struct backtrace_view arch_view;
+  unsigned int i;
+
+  arch_view_valid = 0;
+
+#if defined (__x86_64__)
+  cputype = MACH_O_CPU_TYPE_X86_64;
+#elif defined (__i386__)
+  cputype = MACH_O_CPU_TYPE_X86;
+#elif defined (__aarch64__)
+  cputype = MACH_O_CPU_TYPE_ARM64;
+#elif defined (__arm__)
+  cputype = MACH_O_CPU_TYPE_ARM;
+#elif defined (__ppc__)
+  cputype = MACH_O_CPU_TYPE_PPC;
+#elif defined (__ppc64__)
+  cputype = MACH_O_CPU_TYPE_PPC64;
+#else
+  error_callback (data, "unknown Mach-O architecture", 0);
+  goto fail;
+#endif
+
+  if (is_64)
+    arch_size = sizeof (struct macho_fat_arch_64);
+  else
+    arch_size = sizeof (struct macho_fat_arch);
+
+  if (!backtrace_get_view (state, descriptor, offset,
+			   nfat_arch * arch_size,
+			   error_callback, data, &arch_view))
+    goto fail;
+
+  for (i = 0; i < nfat_arch; ++i)
+    {
+      uint32_t fcputype;
+      uint64_t foffset;
+
+      if (is_64)
+	{
+	  struct macho_fat_arch_64 fat_arch_64;
+
+	  memcpy (&fat_arch_64,
+		  (const char *) arch_view.data + i * arch_size,
+		  arch_size);
+	  fcputype = fat_arch_64.cputype;
+	  foffset = fat_arch_64.offset;
+	  if (swapped)
+	    {
+	      fcputype = __builtin_bswap32 (fcputype);
+	      foffset = __builtin_bswap64 (foffset);
+	    }
+	}
+      else
+	{
+	  struct macho_fat_arch fat_arch_32;
+
+	  memcpy (&fat_arch_32,
+		  (const char *) arch_view.data + i * arch_size,
+		  arch_size);
+	  fcputype = fat_arch_32.cputype;
+	  foffset = (uint64_t) fat_arch_32.offset;
+	  if (swapped)
+	    {
+	      fcputype = __builtin_bswap32 (fcputype);
+	      foffset = (uint64_t) __builtin_bswap32 ((uint32_t) foffset);
+	    }
+	}
+
+      if (fcputype == cputype)
+	{
+	  /* FIXME: What about cpusubtype?  */
+	  backtrace_release_view (state, &arch_view, error_callback, data);
+	  return macho_add (state, filename, descriptor, foffset, match_uuid,
+			    base_address, skip_symtab, error_callback, data,
+			    fileline_fn, found_sym);
+	}
+    }
+
+  error_callback (data, "could not find executable in fat file", 0);
+
+ fail:
+  if (arch_view_valid)
+    backtrace_release_view (state, &arch_view, error_callback, data);
+  if (descriptor != -1)
+    backtrace_close (descriptor, error_callback, data);
+  return 0;
+}
+
+/* Look for the dsym file for FILENAME.  This is called if FILENAME
+   does not have debug info or a symbol table.  Returns 1 on success,
+   0 on failure.  */
+
+static int
+macho_add_dsym (struct backtrace_state *state, const char *filename,
+		uintptr_t base_address, const unsigned char *uuid,
+		backtrace_error_callback error_callback, void *data,
+		fileline* fileline_fn)
+{
+  const char *p;
+  const char *dirname;
+  char *diralc;
+  size_t dirnamelen;
+  const char *basename;
+  size_t basenamelen;
+  const char *dsymsuffixdir;
+  size_t dsymsuffixdirlen;
+  size_t dsymlen;
+  char *dsym;
+  char *ps;
+  int d;
+  int does_not_exist;
+  int dummy_found_sym;
+
+  diralc = NULL;
+  dirnamelen = 0;
+  dsym = NULL;
+  dsymlen = 0;
+
+  p = strrchr (filename, '/');
+  if (p == NULL)
+    {
+      dirname = ".";
+      dirnamelen = 1;
+      basename = filename;
+      basenamelen = strlen (basename);
+      diralc = NULL;
+    }
+  else
+    {
+      dirnamelen = p - filename;
+      diralc = backtrace_alloc (state, dirnamelen + 1, error_callback, data);
+      if (diralc == NULL)
+	goto fail;
+      memcpy (diralc, filename, dirnamelen);
+      diralc[dirnamelen] = '\0';
+      dirname = diralc;
+      basename = p + 1;
+      basenamelen = strlen (basename);
+    }
+
+  dsymsuffixdir = ".dSYM/Contents/Resources/DWARF/";
+  dsymsuffixdirlen = strlen (dsymsuffixdir);
+
+  dsymlen = (dirnamelen
+	     + 1
+	     + basenamelen
+	     + dsymsuffixdirlen
+	     + basenamelen
+	     + 1);
+  dsym = backtrace_alloc (state, dsymlen, error_callback, data);
+  if (dsym == NULL)
+    goto fail;
+
+  ps = dsym;
+  memcpy (ps, dirname, dirnamelen);
+  ps += dirnamelen;
+  *ps++ = '/';
+  memcpy (ps, basename, basenamelen);
+  ps += basenamelen;
+  memcpy (ps, dsymsuffixdir, dsymsuffixdirlen);
+  ps += dsymsuffixdirlen;
+  memcpy (ps, basename, basenamelen);
+  ps += basenamelen;
+  *ps = '\0';
+
+  if (diralc != NULL)
+    {
+      backtrace_free (state, diralc, dirnamelen + 1, error_callback, data);
+      diralc = NULL;
+    }
+
+  d = backtrace_open (dsym, error_callback, data, &does_not_exist);
+  if (d < 0)
+    {
+      /* The file does not exist, so we can't read the debug info.
+	 Just return success.  */
+      backtrace_free (state, dsym, dsymlen, error_callback, data);
+      return 1;
+    }
+
+  if (!macho_add (state, dsym, d, 0, uuid, base_address, 1,
+		  error_callback, data, fileline_fn, &dummy_found_sym))
+    goto fail;
+
+  backtrace_free (state, dsym, dsymlen, error_callback, data);
+
+  return 1;
+
+ fail:
+  if (dsym != NULL)
+    backtrace_free (state, dsym, dsymlen, error_callback, data);
+  if (diralc != NULL)
+    backtrace_free (state, diralc, dirnamelen, error_callback, data);
+  return 0;
+}
+
+/* Add the backtrace data for a Macho-O file.  Returns 1 on success, 0
+   on failure (in both cases descriptor is closed).
+
+   FILENAME: the name of the executable.
+   DESCRIPTOR: an open descriptor for the executable, closed here.
+   OFFSET: the offset within the file of this executable, for fat files.
+   MATCH_UUID: if not NULL, UUID that must match.
+   BASE_ADDRESS: the load address of the executable.
+   SKIP_SYMTAB: if non-zero, ignore the symbol table; used for dSYM files.
+   FILELINE_FN: set to the fileline function, by backtrace_dwarf_add.
+   FOUND_SYM: set to non-zero if we found the symbol table.
+*/
+
+static int
+macho_add (struct backtrace_state *state, const char *filename, int descriptor,
+	   off_t offset, const unsigned char *match_uuid,
+	   uintptr_t base_address, int skip_symtab,
+	   backtrace_error_callback error_callback, void *data,
+	   fileline *fileline_fn, int *found_sym)
+{
+  struct backtrace_view header_view;
+  struct macho_header_32 header;
+  off_t hdroffset;
+  int is_64;
+  struct backtrace_view cmds_view;
+  int cmds_view_valid;
+  struct dwarf_sections dwarf_sections;
+  int have_dwarf;
+  unsigned char uuid[MACH_O_UUID_LEN];
+  int have_uuid;
+  size_t cmdoffset;
+  unsigned int i;
+
+  *found_sym = 0;
+
+  cmds_view_valid = 0;
+
+  /* The 32-bit and 64-bit file headers start out the same, so we can
+     just always read the 32-bit version.  A fat header is shorter but
+     it will always be followed by data, so it's OK to read extra.  */
+
+  if (!backtrace_get_view (state, descriptor, offset,
+			   sizeof (struct macho_header_32),
+			   error_callback, data, &header_view))
+    goto fail;
+
+  memcpy (&header, header_view.data, sizeof header);
+
+  backtrace_release_view (state, &header_view, error_callback, data);
+
+  switch (header.magic)
+    {
+    case MACH_O_MH_MAGIC_32:
+      is_64 = 0;
+      hdroffset = offset + sizeof (struct macho_header_32);
+      break;
+    case MACH_O_MH_MAGIC_64:
+      is_64 = 1;
+      hdroffset = offset + sizeof (struct macho_header_64);
+      break;
+    case MACH_O_MH_MAGIC_FAT:
+    case MACH_O_MH_MAGIC_FAT_64:
+      {
+	struct macho_header_fat fat_header;
+
+	hdroffset = offset + sizeof (struct macho_header_fat);
+	memcpy (&fat_header, &header, sizeof fat_header);
+	return macho_add_fat (state, filename, descriptor, 0, hdroffset,
+			      match_uuid, base_address, skip_symtab,
+			      fat_header.nfat_arch,
+			      header.magic == MACH_O_MH_MAGIC_FAT_64,
+			      error_callback, data, fileline_fn, found_sym);
+      }
+    case MACH_O_MH_CIGAM_FAT:
+    case MACH_O_MH_CIGAM_FAT_64:
+      {
+	struct macho_header_fat fat_header;
+	uint32_t nfat_arch;
+
+	hdroffset = offset + sizeof (struct macho_header_fat);
+	memcpy (&fat_header, &header, sizeof fat_header);
+	nfat_arch = __builtin_bswap32 (fat_header.nfat_arch);
+	return macho_add_fat (state, filename, descriptor, 1, hdroffset,
+			      match_uuid, base_address, skip_symtab,
+			      nfat_arch,
+			      header.magic == MACH_O_MH_CIGAM_FAT_64,
+			      error_callback, data, fileline_fn, found_sym);
+      }
+    default:
+      error_callback (data, "executable file is not in Mach-O format", 0);
+      goto fail;
+    }
+
+  switch (header.filetype)
+    {
+    case MACH_O_MH_EXECUTE:
+    case MACH_O_MH_DYLIB:
+    case MACH_O_MH_DSYM:
+      break;
+    default:
+      error_callback (data, "executable file is not an executable", 0);
+      goto fail;
+    }
+
+  if (!backtrace_get_view (state, descriptor, hdroffset, header.sizeofcmds,
+			   error_callback, data, &cmds_view))
+    goto fail;
+  cmds_view_valid = 1;
+
+  memset (&dwarf_sections, 0, sizeof dwarf_sections);
+  have_dwarf = 0;
+  memset (&uuid, 0, sizeof uuid);
+  have_uuid = 0;
+
+  cmdoffset = 0;
+  for (i = 0; i < header.ncmds; ++i)
+    {
+      const char *pcmd;
+      struct macho_load_command load_command;
+
+      if (cmdoffset + sizeof load_command > header.sizeofcmds)
+	break;
+
+      pcmd = (const char *) cmds_view.data + cmdoffset;
+      memcpy (&load_command, pcmd, sizeof load_command);
+
+      switch (load_command.cmd)
+	{
+	case MACH_O_LC_SEGMENT:
+	  {
+	    struct macho_segment_command segcmd;
+
+	    memcpy (&segcmd, pcmd, sizeof segcmd);
+	    if (memcmp (segcmd.segname,
+			"__DWARF\0\0\0\0\0\0\0\0\0",
+			MACH_O_NAMELEN) == 0)
+	      {
+		if (!macho_add_dwarf_segment (state, descriptor, offset,
+					      load_command.cmd,
+					      pcmd + sizeof segcmd,
+					      (load_command.cmdsize
+					       - sizeof segcmd),
+					      segcmd.nsects, error_callback,
+					      data, &dwarf_sections))
+		  goto fail;
+		have_dwarf = 1;
+	      }
+	  }
+	  break;
+
+	case MACH_O_LC_SEGMENT_64:
+	  {
+	    struct macho_segment_64_command segcmd;
+
+	    memcpy (&segcmd, pcmd, sizeof segcmd);
+	    if (memcmp (segcmd.segname,
+			"__DWARF\0\0\0\0\0\0\0\0\0",
+			MACH_O_NAMELEN) == 0)
+	      {
+		if (!macho_add_dwarf_segment (state, descriptor, offset,
+					      load_command.cmd,
+					      pcmd + sizeof segcmd,
+					      (load_command.cmdsize
+					       - sizeof segcmd),
+					      segcmd.nsects, error_callback,
+					      data, &dwarf_sections))
+		  goto fail;
+		have_dwarf = 1;
+	      }
+	  }
+	  break;
+
+	case MACH_O_LC_SYMTAB:
+	  if (!skip_symtab)
+	    {
+	      struct macho_symtab_command symcmd;
+
+	      memcpy (&symcmd, pcmd, sizeof symcmd);
+	      if (!macho_add_symtab (state, descriptor, base_address, is_64,
+				     offset + symcmd.symoff, symcmd.nsyms,
+				     offset + symcmd.stroff, symcmd.strsize,
+				     error_callback, data))
+		goto fail;
+
+	      *found_sym = 1;
+	    }
+	  break;
+
+	case MACH_O_LC_UUID:
+	  {
+	    struct macho_uuid_command uuidcmd;
+
+	    memcpy (&uuidcmd, pcmd, sizeof uuidcmd);
+	    memcpy (&uuid[0], &uuidcmd.uuid[0], MACH_O_UUID_LEN);
+	    have_uuid = 1;
+	  }
+	  break;
+
+	default:
+	  break;
+	}
+
+      cmdoffset += load_command.cmdsize;
+    }
+
+  if (!backtrace_close (descriptor, error_callback, data))
+    goto fail;
+  descriptor = -1;
+
+  backtrace_release_view (state, &cmds_view, error_callback, data);
+  cmds_view_valid = 0;
+
+  if (match_uuid != NULL)
+    {
+      /* If we don't have a UUID, or it doesn't match, just ignore
+	 this file.  */
+      if (!have_uuid
+	  || memcmp (match_uuid, &uuid[0], MACH_O_UUID_LEN) != 0)
+	return 1;
+    }
+
+  if (have_dwarf)
+    {
+      int is_big_endian;
+
+      is_big_endian = 0;
+#if defined(__BYTE_ORDER__) && defined(__ORDER_BIG_ENDIAN__)
+#if __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
+      is_big_endian = 1;
+#endif
+#endif
+
+      if (!backtrace_dwarf_add (state, base_address, &dwarf_sections,
+				is_big_endian, NULL, error_callback, data,
+				fileline_fn, NULL))
+	goto fail;
+    }
+
+  if (!have_dwarf && have_uuid)
+    {
+      if (!macho_add_dsym (state, filename, base_address, &uuid[0],
+			   error_callback, data, fileline_fn))
+	goto fail;
+    }
+
+  return 1;
+
+ fail:
+  if (cmds_view_valid)
+    backtrace_release_view (state, &cmds_view, error_callback, data);
+  if (descriptor != -1)
+    backtrace_close (descriptor, error_callback, data);
+  return 0;
+}
+
+#ifdef HAVE_MACH_O_DYLD_H
+
+/* Initialize the backtrace data we need from a Mach-O executable
+   using the dyld support functions.  This closes descriptor.  */
+
+int
+backtrace_initialize (struct backtrace_state *state, const char *filename,
+		      int descriptor, backtrace_error_callback error_callback,
+		      void *data, fileline *fileline_fn)
+{
+  uint32_t c;
+  uint32_t i;
+  int closed_descriptor;
+  int found_sym;
+  fileline macho_fileline_fn;
+
+  closed_descriptor = 0;
+  found_sym = 0;
+  macho_fileline_fn = macho_nodebug;
+
+  c = _dyld_image_count ();
+  for (i = 0; i < c; ++i)
+    {
+      uintptr_t base_address;
+      const char *name;
+      int d;
+      fileline mff;
+      int mfs;
+
+      name = _dyld_get_image_name (i);
+      if (name == NULL)
+	continue;
+
+      if (strcmp (name, filename) == 0 && !closed_descriptor)
+	{
+	  d = descriptor;
+	  closed_descriptor = 1;
+	}
+      else
+	{
+	  int does_not_exist;
+
+	  d = backtrace_open (name, error_callback, data, &does_not_exist);
+	  if (d < 0)
+	    continue;
+	}
+
+      base_address = _dyld_get_image_vmaddr_slide (i);
+
+      mff = macho_nodebug;
+      if (!macho_add (state, name, d, 0, NULL, base_address, 0,
+		      error_callback, data, &mff, &mfs))
+	continue;
+
+      if (mff != macho_nodebug)
+	macho_fileline_fn = mff;
+      if (mfs)
+	found_sym = 1;
+    }
+
+  if (!closed_descriptor)
+    backtrace_close (descriptor, error_callback, data);
+
+  if (!state->threaded)
+    {
+      if (found_sym)
+	state->syminfo_fn = macho_syminfo;
+      else if (state->syminfo_fn == NULL)
+	state->syminfo_fn = macho_nosyms;
+    }
+  else
+    {
+      if (found_sym)
+	backtrace_atomic_store_pointer (&state->syminfo_fn, macho_syminfo);
+      else
+	(void) __sync_bool_compare_and_swap (&state->syminfo_fn, NULL,
+					     macho_nosyms);
+    }
+
+  if (!state->threaded)
+    *fileline_fn = state->fileline_fn;
+  else
+    *fileline_fn = backtrace_atomic_load_pointer (&state->fileline_fn);
+
+  if (*fileline_fn == NULL || *fileline_fn == macho_nodebug)
+    *fileline_fn = macho_fileline_fn;
+
+  return 1;
+}
+
+#else /* !defined (HAVE_MACH_O_DYLD_H) */
+
+/* Initialize the backtrace data we need from a Mach-O executable
+   without using the dyld support functions.  This closes
+   descriptor.  */
+
+int
+backtrace_initialize (struct backtrace_state *state, const char *filename,
+		      int descriptor, backtrace_error_callback error_callback,
+		      void *data, fileline *fileline_fn)
+{
+  fileline macho_fileline_fn;
+  int found_sym;
+
+  macho_fileline_fn = macho_nodebug;
+  if (!macho_add (state, filename, descriptor, 0, NULL, 0, 0,
+		  error_callback, data, &macho_fileline_fn, &found_sym))
+    return 0;
+
+  if (!state->threaded)
+    {
+      if (found_sym)
+	state->syminfo_fn = macho_syminfo;
+      else if (state->syminfo_fn == NULL)
+	state->syminfo_fn = macho_nosyms;
+    }
+  else
+    {
+      if (found_sym)
+	backtrace_atomic_store_pointer (&state->syminfo_fn, macho_syminfo);
+      else
+	(void) __sync_bool_compare_and_swap (&state->syminfo_fn, NULL,
+					     macho_nosyms);
+    }
+
+  if (!state->threaded)
+    *fileline_fn = state->fileline_fn;
+  else
+    *fileline_fn = backtrace_atomic_load_pointer (&state->fileline_fn);
+
+  if (*fileline_fn == NULL || *fileline_fn == macho_nodebug)
+    *fileline_fn = macho_fileline_fn;
+
+  return 1;
+}
+
+#endif /* !defined (HAVE_MACH_O_DYLD_H) */
diff --git a/contrib/libs/cxxsupp/libcxx/include/experimental/functional b/contrib/libs/cxxsupp/libcxx/include/experimental/functional
new file mode 100644
index 0000000000..1291894aa0
--- /dev/null
+++ b/contrib/libs/cxxsupp/libcxx/include/experimental/functional
@@ -0,0 +1,425 @@
+// -*- C++ -*-
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef _LIBCPP_EXPERIMENTAL_FUNCTIONAL
+#define _LIBCPP_EXPERIMENTAL_FUNCTIONAL
+
+/*
+   experimental/functional synopsis
+
+#include <algorithm>
+
+namespace std {
+namespace experimental {
+inline namespace fundamentals_v1 {
+    // 4.3, Searchers
+    template<class ForwardIterator, class BinaryPredicate = equal_to<>>
+      class default_searcher;
+
+    template<class RandomAccessIterator,
+             class Hash = hash<typename iterator_traits<RandomAccessIterator>::value_type>,
+             class BinaryPredicate = equal_to<>>
+      class boyer_moore_searcher;
+
+    template<class RandomAccessIterator,
+             class Hash = hash<typename iterator_traits<RandomAccessIterator>::value_type>,
+             class BinaryPredicate = equal_to<>>
+      class boyer_moore_horspool_searcher;
+
+    template<class ForwardIterator, class BinaryPredicate = equal_to<>>
+    default_searcher<ForwardIterator, BinaryPredicate>
+    make_default_searcher(ForwardIterator pat_first, ForwardIterator pat_last,
+                          BinaryPredicate pred = BinaryPredicate());
+
+    template<class RandomAccessIterator,
+             class Hash = hash<typename iterator_traits<RandomAccessIterator>::value_type>,
+             class BinaryPredicate = equal_to<>>
+    boyer_moore_searcher<RandomAccessIterator, Hash, BinaryPredicate>
+    make_boyer_moore_searcher(
+        RandomAccessIterator pat_first, RandomAccessIterator pat_last,
+        Hash hf = Hash(), BinaryPredicate pred = BinaryPredicate());
+
+    template<class RandomAccessIterator,
+             class Hash = hash<typename iterator_traits<RandomAccessIterator>::value_type>,
+             class BinaryPredicate = equal_to<>>
+    boyer_moore_horspool_searcher<RandomAccessIterator, Hash, BinaryPredicate>
+    make_boyer_moore_horspool_searcher(
+        RandomAccessIterator pat_first, RandomAccessIterator pat_last,
+        Hash hf = Hash(), BinaryPredicate pred = BinaryPredicate());
+
+  } // namespace fundamentals_v1
+  } // namespace experimental
+
+} // namespace std
+
+*/
+
+#include <__debug>
+#include <__memory/uses_allocator.h>
+#include <array>
+#include <experimental/__config>
+#include <functional>
+#include <type_traits>
+#include <unordered_map>
+#include <vector>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+_LIBCPP_PUSH_MACROS
+#include <__undef_macros>
+
+_LIBCPP_BEGIN_NAMESPACE_LFTS
+
+#if _LIBCPP_STD_VER > 11
+// default searcher
+template<class _ForwardIterator, class _BinaryPredicate = equal_to<>>
+class _LIBCPP_TEMPLATE_VIS default_searcher {
+public:
+    _LIBCPP_INLINE_VISIBILITY
+    default_searcher(_ForwardIterator __f, _ForwardIterator __l,
+                       _BinaryPredicate __p = _BinaryPredicate())
+        : __first_(__f), __last_(__l), __pred_(__p) {}
+
+    template <typename _ForwardIterator2>
+    _LIBCPP_INLINE_VISIBILITY
+    pair<_ForwardIterator2, _ForwardIterator2>
+    operator () (_ForwardIterator2 __f, _ForwardIterator2 __l) const
+    {
+        return _VSTD::__search(__f, __l, __first_, __last_, __pred_,
+            typename iterator_traits<_ForwardIterator>::iterator_category(),
+            typename iterator_traits<_ForwardIterator2>::iterator_category());
+    }
+
+private:
+    _ForwardIterator __first_;
+    _ForwardIterator __last_;
+    _BinaryPredicate __pred_;
+    };
+
+template<class _ForwardIterator, class _BinaryPredicate = equal_to<>>
+_LIBCPP_INLINE_VISIBILITY
+default_searcher<_ForwardIterator, _BinaryPredicate>
+make_default_searcher( _ForwardIterator __f, _ForwardIterator __l, _BinaryPredicate __p = _BinaryPredicate ())
+{
+    return default_searcher<_ForwardIterator, _BinaryPredicate>(__f, __l, __p);
+}
+
+template<class _Key, class _Value, class _Hash, class _BinaryPredicate, bool /*useArray*/> class _BMSkipTable;
+
+//  General case for BM data searching; use a map
+template<class _Key, typename _Value, class _Hash, class _BinaryPredicate>
+class _BMSkipTable<_Key, _Value, _Hash, _BinaryPredicate, false> {
+    typedef _Value value_type;
+    typedef _Key   key_type;
+
+    const _Value __default_value_;
+    std::unordered_map<_Key, _Value, _Hash, _BinaryPredicate> __table;
+
+public:
+    _LIBCPP_INLINE_VISIBILITY
+    _BMSkipTable(size_t __sz, _Value __default, _Hash __hf, _BinaryPredicate __pred)
+        : __default_value_(__default), __table(__sz, __hf, __pred) {}
+
+    _LIBCPP_INLINE_VISIBILITY
+    void insert(const key_type &__key, value_type __val)
+    {
+        __table [__key] = __val;    // Would skip_.insert (val) be better here?
+    }
+
+    _LIBCPP_INLINE_VISIBILITY
+    value_type operator [](const key_type & __key) const
+    {
+        auto __it = __table.find (__key);
+        return __it == __table.end() ? __default_value_ : __it->second;
+    }
+};
+
+
+//  Special case small numeric values; use an array
+template<class _Key, typename _Value, class _Hash, class _BinaryPredicate>
+class _BMSkipTable<_Key, _Value, _Hash, _BinaryPredicate, true> {
+private:
+    typedef _Value value_type;
+    typedef _Key   key_type;
+
+    typedef typename make_unsigned<key_type>::type unsigned_key_type;
+    typedef std::array<value_type, numeric_limits<unsigned_key_type>::max()> skip_map;
+    skip_map __table;
+
+public:
+    _LIBCPP_INLINE_VISIBILITY
+    _BMSkipTable(size_t /*__sz*/, _Value __default, _Hash /*__hf*/, _BinaryPredicate /*__pred*/)
+    {
+        std::fill_n(__table.begin(), __table.size(), __default);
+    }
+
+    _LIBCPP_INLINE_VISIBILITY
+    void insert(key_type __key, value_type __val)
+    {
+        __table[static_cast<unsigned_key_type>(__key)] = __val;
+    }
+
+    _LIBCPP_INLINE_VISIBILITY
+    value_type operator [](key_type __key) const
+    {
+        return __table[static_cast<unsigned_key_type>(__key)];
+    }
+};
+
+
+template <class _RandomAccessIterator1,
+          class _Hash = hash<typename iterator_traits<_RandomAccessIterator1>::value_type>,
+          class _BinaryPredicate = equal_to<>>
+class _LIBCPP_TEMPLATE_VIS boyer_moore_searcher {
+private:
+    typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type difference_type;
+    typedef typename std::iterator_traits<_RandomAccessIterator1>::value_type      value_type;
+    typedef _BMSkipTable<value_type, difference_type, _Hash, _BinaryPredicate,
+                    is_integral<value_type>::value && // what about enums?
+                    sizeof(value_type) == 1 &&
+                    is_same<_Hash, hash<value_type>>::value &&
+                    is_same<_BinaryPredicate, equal_to<>>::value
+            > skip_table_type;
+
+public:
+    boyer_moore_searcher(_RandomAccessIterator1 __f, _RandomAccessIterator1 __l,
+                _Hash __hf = _Hash(), _BinaryPredicate __pred = _BinaryPredicate())
+            : __first_(__f), __last_(__l), __pred_(__pred),
+              __pattern_length_(_VSTD::distance(__first_, __last_)),
+              __skip_{make_shared<skip_table_type>(__pattern_length_, -1, __hf, __pred_)},
+              __suffix_{make_shared<vector<difference_type>>(__pattern_length_ + 1)}
+        {
+    //  build the skip table
+        for ( difference_type __i = 0; __f != __l; ++__f, (void) ++__i )
+            __skip_->insert(*__f, __i);
+
+        this->__build_suffix_table ( __first_, __last_, __pred_ );
+        }
+
+    template <typename _RandomAccessIterator2>
+    pair<_RandomAccessIterator2, _RandomAccessIterator2>
+    operator ()(_RandomAccessIterator2 __f, _RandomAccessIterator2 __l) const
+    {
+        static_assert(__is_same_uncvref<typename iterator_traits<_RandomAccessIterator1>::value_type,
+                                        typename iterator_traits<_RandomAccessIterator2>::value_type>::value,
+                      "Corpus and Pattern iterators must point to the same type");
+
+        if (__f      == __l )    return make_pair(__l, __l); // empty corpus
+        if (__first_ == __last_) return make_pair(__f, __f); // empty pattern
+
+    //  If the pattern is larger than the corpus, we can't find it!
+        if ( __pattern_length_ > _VSTD::distance(__f, __l))
+            return make_pair(__l, __l);
+
+    //  Do the search
+        return this->__search(__f, __l);
+    }
+
+private:
+    _RandomAccessIterator1               __first_;
+    _RandomAccessIterator1               __last_;
+    _BinaryPredicate                     __pred_;
+    difference_type                      __pattern_length_;
+    shared_ptr<skip_table_type>          __skip_;
+    shared_ptr<vector<difference_type>>  __suffix_;
+
+    template <typename _RandomAccessIterator2>
+    pair<_RandomAccessIterator2, _RandomAccessIterator2>
+    __search(_RandomAccessIterator2 __f, _RandomAccessIterator2 __l) const
+    {
+        _RandomAccessIterator2 __cur = __f;
+        const _RandomAccessIterator2 __last = __l - __pattern_length_;
+        const skip_table_type &         __skip   = *__skip_.get();
+        const vector<difference_type> & __suffix = *__suffix_.get();
+
+        while (__cur <= __last)
+        {
+
+        //  Do we match right where we are?
+            difference_type __j = __pattern_length_;
+            while (__pred_(__first_ [__j-1], __cur [__j-1])) {
+                __j--;
+            //  We matched - we're done!
+                if ( __j == 0 )
+                    return make_pair(__cur, __cur + __pattern_length_);
+                }
+
+        //  Since we didn't match, figure out how far to skip forward
+            difference_type __k = __skip[__cur [ __j - 1 ]];
+            difference_type __m = __j - __k - 1;
+            if (__k < __j && __m > __suffix[ __j ])
+                __cur += __m;
+            else
+                __cur += __suffix[ __j ];
+        }
+
+        return make_pair(__l, __l);     // We didn't find anything
+    }
+
+
+    template<typename _Iterator, typename _Container>
+    void __compute_bm_prefix ( _Iterator __f, _Iterator __l, _BinaryPredicate __pred, _Container &__prefix )
+    {
+        const size_t __count = _VSTD::distance(__f, __l);
+
+        __prefix[0] = 0;
+        size_t __k = 0;
+        for ( size_t __i = 1; __i < __count; ++__i )
+        {
+            while ( __k > 0 && !__pred ( __f[__k], __f[__i] ))
+                __k = __prefix [ __k - 1 ];
+
+            if ( __pred ( __f[__k], __f[__i] ))
+                __k++;
+            __prefix [ __i ] = __k;
+        }
+    }
+
+    void __build_suffix_table(_RandomAccessIterator1 __f, _RandomAccessIterator1 __l,
+                                                    _BinaryPredicate __pred)
+    {
+        const size_t __count = _VSTD::distance(__f, __l);
+        vector<difference_type> & __suffix = *__suffix_.get();
+        if (__count > 0)
+        {
+            vector<value_type> __scratch(__count);
+
+            __compute_bm_prefix(__f, __l, __pred, __scratch);
+            for ( size_t __i = 0; __i <= __count; __i++ )
+                __suffix[__i] = __count - __scratch[__count-1];
+
+            typedef reverse_iterator<_RandomAccessIterator1> _RevIter;
+            __compute_bm_prefix(_RevIter(__l), _RevIter(__f), __pred, __scratch);
+
+            for ( size_t __i = 0; __i < __count; __i++ )
+            {
+                const size_t     __j = __count - __scratch[__i];
+                const difference_type __k = __i     - __scratch[__i] + 1;
+
+                if (__suffix[__j] > __k)
+                    __suffix[__j] = __k;
+            }
+        }
+    }
+
+};
+
+template<class _RandomAccessIterator,
+         class _Hash = hash<typename iterator_traits<_RandomAccessIterator>::value_type>,
+         class _BinaryPredicate = equal_to<>>
+_LIBCPP_INLINE_VISIBILITY
+boyer_moore_searcher<_RandomAccessIterator, _Hash, _BinaryPredicate>
+make_boyer_moore_searcher( _RandomAccessIterator __f, _RandomAccessIterator __l,
+                    _Hash __hf = _Hash(), _BinaryPredicate __p = _BinaryPredicate ())
+{
+    return boyer_moore_searcher<_RandomAccessIterator, _Hash, _BinaryPredicate>(__f, __l, __hf, __p);
+}
+
+// boyer-moore-horspool
+template <class _RandomAccessIterator1,
+          class _Hash = hash<typename iterator_traits<_RandomAccessIterator1>::value_type>,
+          class _BinaryPredicate = equal_to<>>
+class _LIBCPP_TEMPLATE_VIS boyer_moore_horspool_searcher {
+private:
+    typedef typename std::iterator_traits<_RandomAccessIterator1>::difference_type difference_type;
+    typedef typename std::iterator_traits<_RandomAccessIterator1>::value_type      value_type;
+    typedef _BMSkipTable<value_type, difference_type, _Hash, _BinaryPredicate,
+                    is_integral<value_type>::value && // what about enums?
+                    sizeof(value_type) == 1 &&
+                    is_same<_Hash, hash<value_type>>::value &&
+                    is_same<_BinaryPredicate, equal_to<>>::value
+            > skip_table_type;
+
+public:
+    boyer_moore_horspool_searcher(_RandomAccessIterator1 __f, _RandomAccessIterator1 __l,
+                _Hash __hf = _Hash(), _BinaryPredicate __pred = _BinaryPredicate())
+            : __first_(__f), __last_(__l), __pred_(__pred),
+              __pattern_length_(_VSTD::distance(__first_, __last_)),
+              __skip_{_VSTD::make_shared<skip_table_type>(__pattern_length_, __pattern_length_, __hf, __pred_)}
+        {
+    //  build the skip table
+            if ( __f != __l )
+            {
+                __l = __l - 1;
+                for ( difference_type __i = 0; __f != __l; ++__f, (void) ++__i )
+                    __skip_->insert(*__f, __pattern_length_ - 1 - __i);
+            }
+        }
+
+    template <typename _RandomAccessIterator2>
+    pair<_RandomAccessIterator2, _RandomAccessIterator2>
+    operator ()(_RandomAccessIterator2 __f, _RandomAccessIterator2 __l) const
+    {
+        static_assert(__is_same_uncvref<typename std::iterator_traits<_RandomAccessIterator1>::value_type,
+                                        typename std::iterator_traits<_RandomAccessIterator2>::value_type>::value,
+                      "Corpus and Pattern iterators must point to the same type");
+
+        if (__f      == __l )    return make_pair(__l, __l); // empty corpus
+        if (__first_ == __last_) return make_pair(__f, __f); // empty pattern
+
+    //  If the pattern is larger than the corpus, we can't find it!
+        if ( __pattern_length_ > _VSTD::distance(__f, __l))
+            return make_pair(__l, __l);
+
+    //  Do the search
+        return this->__search(__f, __l);
+    }
+
+private:
+    _RandomAccessIterator1      __first_;
+    _RandomAccessIterator1      __last_;
+    _BinaryPredicate            __pred_;
+    difference_type             __pattern_length_;
+    shared_ptr<skip_table_type> __skip_;
+
+    template <typename _RandomAccessIterator2>
+    pair<_RandomAccessIterator2, _RandomAccessIterator2>
+    __search ( _RandomAccessIterator2 __f, _RandomAccessIterator2 __l ) const {
+        _RandomAccessIterator2 __cur = __f;
+        const _RandomAccessIterator2 __last = __l - __pattern_length_;
+        const skip_table_type & __skip = *__skip_.get();
+
+        while (__cur <= __last)
+        {
+        //  Do we match right where we are?
+            difference_type __j = __pattern_length_;
+            while (__pred_(__first_[__j-1], __cur[__j-1]))
+            {
+                __j--;
+            //  We matched - we're done!
+                if ( __j == 0 )
+                    return make_pair(__cur, __cur + __pattern_length_);
+            }
+            __cur += __skip[__cur[__pattern_length_-1]];
+        }
+
+        return make_pair(__l, __l);
+    }
+};
+
+template<class _RandomAccessIterator,
+         class _Hash = hash<typename iterator_traits<_RandomAccessIterator>::value_type>,
+         class _BinaryPredicate = equal_to<>>
+_LIBCPP_INLINE_VISIBILITY
+boyer_moore_horspool_searcher<_RandomAccessIterator, _Hash, _BinaryPredicate>
+make_boyer_moore_horspool_searcher( _RandomAccessIterator __f, _RandomAccessIterator __l,
+                    _Hash __hf = _Hash(), _BinaryPredicate __p = _BinaryPredicate ())
+{
+    return boyer_moore_horspool_searcher<_RandomAccessIterator, _Hash, _BinaryPredicate>(__f, __l, __hf, __p);
+}
+
+#endif // _LIBCPP_STD_VER > 11
+
+_LIBCPP_END_NAMESPACE_LFTS
+
+_LIBCPP_POP_MACROS
+
+#endif /* _LIBCPP_EXPERIMENTAL_FUNCTIONAL */
diff --git a/contrib/libs/sparsehash/src/sparsehash/dense_hash_set b/contrib/libs/sparsehash/src/sparsehash/dense_hash_set
new file mode 100644
index 0000000000..050b15d1d5
--- /dev/null
+++ b/contrib/libs/sparsehash/src/sparsehash/dense_hash_set
@@ -0,0 +1,338 @@
+// Copyright (c) 2005, Google Inc.
+// All rights reserved.
+//
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are
+// met:
+//
+//     * Redistributions of source code must retain the above copyright
+// notice, this list of conditions and the following disclaimer.
+//     * Redistributions in binary form must reproduce the above
+// copyright notice, this list of conditions and the following disclaimer
+// in the documentation and/or other materials provided with the
+// distribution.
+//     * Neither the name of Google Inc. nor the names of its
+// contributors may be used to endorse or promote products derived from
+// this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+// ---
+//
+// This is just a very thin wrapper over densehashtable.h, just
+// like sgi stl's stl_hash_set is a very thin wrapper over
+// stl_hashtable.  The major thing we define is operator[], because
+// we have a concept of a data_type which stl_hashtable doesn't
+// (it only has a key and a value).
+//
+// This is more different from dense_hash_map than you might think,
+// because all iterators for sets are const (you obviously can't
+// change the key, and for sets there is no value).
+//
+// NOTE: this is exactly like sparse_hash_set.h, with the word
+// "sparse" replaced by "dense", except for the addition of
+// set_empty_key().
+//
+//   YOU MUST CALL SET_EMPTY_KEY() IMMEDIATELY AFTER CONSTRUCTION.
+//
+// Otherwise your program will die in mysterious ways.  (Note if you
+// use the constructor that takes an InputIterator range, you pass in
+// the empty key in the constructor, rather than after.  As a result,
+// this constructor differs from the standard STL version.)
+//
+// In other respects, we adhere mostly to the STL semantics for
+// hash-map.  One important exception is that insert() may invalidate
+// iterators entirely -- STL semantics are that insert() may reorder
+// iterators, but they all still refer to something valid in the
+// hashtable.  Not so for us.  Likewise, insert() may invalidate
+// pointers into the hashtable.  (Whether insert invalidates iterators
+// and pointers depends on whether it results in a hashtable resize).
+// On the plus side, delete() doesn't invalidate iterators or pointers
+// at all, or even change the ordering of elements.
+//
+// Here are a few "power user" tips:
+//
+//    1) set_deleted_key():
+//         If you want to use erase() you must call set_deleted_key(),
+//         in addition to set_empty_key(), after construction.
+//         The deleted and empty keys must differ.
+//
+//    2) resize(0):
+//         When an item is deleted, its memory isn't freed right
+//         away.  This allows you to iterate over a hashtable,
+//         and call erase(), without invalidating the iterator.
+//         To force the memory to be freed, call resize(0).
+//         For tr1 compatibility, this can also be called as rehash(0).
+//
+//    3) min_load_factor(0.0)
+//         Setting the minimum load factor to 0.0 guarantees that
+//         the hash table will never shrink.
+//
+// Roughly speaking:
+//   (1) dense_hash_set: fastest, uses the most memory unless entries are small
+//   (2) sparse_hash_set: slowest, uses the least memory
+//   (3) hash_set / unordered_set (STL): in the middle
+//
+// Typically I use sparse_hash_set when I care about space and/or when
+// I need to save the hashtable on disk.  I use hash_set otherwise.  I
+// don't personally use dense_hash_set ever; some people use it for
+// small sets with lots of lookups.
+//
+// - dense_hash_set has, typically, about 78% memory overhead (if your
+//   data takes up X bytes, the hash_set uses .78X more bytes in overhead).
+// - sparse_hash_set has about 4 bits overhead per entry.
+// - sparse_hash_set can be 3-7 times slower than the others for lookup and,
+//   especially, inserts.  See time_hash_map.cc for details.
+//
+// See /usr/(local/)?doc/sparsehash-*/dense_hash_set.html
+// for information about how to use this class.
+
+#ifndef _DENSE_HASH_SET_H_
+#define _DENSE_HASH_SET_H_
+
+#include <sparsehash/internal/sparseconfig.h>
+#include <algorithm>                        // needed by stl_alloc
+#include <functional>                       // for equal_to<>, select1st<>, etc
+#include <memory>                           // for alloc
+#include <utility>                          // for pair<>
+#include <sparsehash/internal/densehashtable.h>        // IWYU pragma: export
+#include <sparsehash/internal/libc_allocator_with_realloc.h>
+#include HASH_FUN_H                 // for hash<>
+_START_GOOGLE_NAMESPACE_
+
+template <class Value,
+          class HashFcn = SPARSEHASH_HASH<Value>,   // defined in sparseconfig.h
+          class EqualKey = std::equal_to<Value>,
+          class Alloc = libc_allocator_with_realloc<Value> >
+class dense_hash_set {
+ private:
+  // Apparently identity is not stl-standard, so we define our own
+  struct Identity {
+    typedef const Value& result_type;
+    const Value& operator()(const Value& v) const { return v; }
+  };
+  struct SetKey {
+    void operator()(Value* value, const Value& new_key) const {
+      *value = new_key;
+    }
+  };
+
+  // The actual data
+  typedef dense_hashtable<Value, Value, HashFcn, Identity, SetKey,
+                          EqualKey, Alloc> ht;
+  ht rep;
+
+ public:
+  typedef typename ht::key_type key_type;
+  typedef typename ht::value_type value_type;
+  typedef typename ht::hasher hasher;
+  typedef typename ht::key_equal key_equal;
+  typedef Alloc allocator_type;
+
+  typedef typename ht::size_type size_type;
+  typedef typename ht::difference_type difference_type;
+  typedef typename ht::const_pointer pointer;
+  typedef typename ht::const_pointer const_pointer;
+  typedef typename ht::const_reference reference;
+  typedef typename ht::const_reference const_reference;
+
+  typedef typename ht::const_iterator iterator;
+  typedef typename ht::const_iterator const_iterator;
+  typedef typename ht::const_local_iterator local_iterator;
+  typedef typename ht::const_local_iterator const_local_iterator;
+
+
+  // Iterator functions -- recall all iterators are const
+  iterator begin() const                  { return rep.begin(); }
+  iterator end() const                    { return rep.end(); }
+
+  // These come from tr1's unordered_set. For us, a bucket has 0 or 1 elements.
+  local_iterator begin(size_type i) const { return rep.begin(i); }
+  local_iterator end(size_type i) const   { return rep.end(i); }
+
+
+  // Accessor functions
+  allocator_type get_allocator() const    { return rep.get_allocator(); }
+  hasher hash_funct() const               { return rep.hash_funct(); }
+  hasher hash_function() const            { return hash_funct(); }  // tr1 name
+  key_equal key_eq() const                { return rep.key_eq(); }
+
+
+  // Constructors
+  explicit dense_hash_set(size_type expected_max_items_in_table = 0,
+                          const hasher& hf = hasher(),
+                          const key_equal& eql = key_equal(),
+                          const allocator_type& alloc = allocator_type())
+      : rep(expected_max_items_in_table, hf, eql, Identity(), SetKey(), alloc) {
+  }
+
+  template <class InputIterator>
+  dense_hash_set(InputIterator f, InputIterator l,
+                 const key_type& empty_key_val,
+                 size_type expected_max_items_in_table = 0,
+                 const hasher& hf = hasher(),
+                 const key_equal& eql = key_equal(),
+                 const allocator_type& alloc = allocator_type())
+      : rep(expected_max_items_in_table, hf, eql, Identity(), SetKey(), alloc) {
+    set_empty_key(empty_key_val);
+    rep.insert(f, l);
+  }
+  // We use the default copy constructor
+  // We use the default operator=()
+  // We use the default destructor
+
+  void clear()                        { rep.clear(); }
+  // This clears the hash set without resizing it down to the minimum
+  // bucket count, but rather keeps the number of buckets constant
+  void clear_no_resize()              { rep.clear_no_resize(); }
+  void swap(dense_hash_set& hs)       { rep.swap(hs.rep); }
+
+
+  // Functions concerning size
+  size_type size() const              { return rep.size(); }
+  size_type max_size() const          { return rep.max_size(); }
+  bool empty() const                  { return rep.empty(); }
+  size_type bucket_count() const      { return rep.bucket_count(); }
+  size_type max_bucket_count() const  { return rep.max_bucket_count(); }
+
+  // These are tr1 methods.  bucket() is the bucket the key is or would be in.
+  size_type bucket_size(size_type i) const    { return rep.bucket_size(i); }
+  size_type bucket(const key_type& key) const { return rep.bucket(key); }
+  float load_factor() const {
+    return size() * 1.0f / bucket_count();
+  }
+  float max_load_factor() const {
+    float shrink, grow;
+    rep.get_resizing_parameters(&shrink, &grow);
+    return grow;
+  }
+  void max_load_factor(float new_grow) {
+    float shrink, grow;
+    rep.get_resizing_parameters(&shrink, &grow);
+    rep.set_resizing_parameters(shrink, new_grow);
+  }
+  // These aren't tr1 methods but perhaps ought to be.
+  float min_load_factor() const {
+    float shrink, grow;
+    rep.get_resizing_parameters(&shrink, &grow);
+    return shrink;
+  }
+  void min_load_factor(float new_shrink) {
+    float shrink, grow;
+    rep.get_resizing_parameters(&shrink, &grow);
+    rep.set_resizing_parameters(new_shrink, grow);
+  }
+  // Deprecated; use min_load_factor() or max_load_factor() instead.
+  void set_resizing_parameters(float shrink, float grow) {
+    rep.set_resizing_parameters(shrink, grow);
+  }
+
+  void resize(size_type hint)         { rep.resize(hint); }
+  void rehash(size_type hint)         { resize(hint); }     // the tr1 name
+
+  // Lookup routines
+  iterator find(const key_type& key) const           { return rep.find(key); }
+
+  size_type count(const key_type& key) const         { return rep.count(key); }
+
+  std::pair<iterator, iterator> equal_range(const key_type& key) const {
+    return rep.equal_range(key);
+  }
+
+
+  // Insertion routines
+  std::pair<iterator, bool> insert(const value_type& obj) {
+    std::pair<typename ht::iterator, bool> p = rep.insert(obj);
+    return std::pair<iterator, bool>(p.first, p.second);   // const to non-const
+  }
+  template <class InputIterator> void insert(InputIterator f, InputIterator l) {
+    rep.insert(f, l);
+  }
+  void insert(const_iterator f, const_iterator l) {
+    rep.insert(f, l);
+  }
+  // Required for std::insert_iterator; the passed-in iterator is ignored.
+  iterator insert(iterator, const value_type& obj)   {
+    return insert(obj).first;
+  }
+
+  // Deletion and empty routines
+  // THESE ARE NON-STANDARD!  I make you specify an "impossible" key
+  // value to identify deleted and empty buckets.  You can change the
+  // deleted key as time goes on, or get rid of it entirely to be insert-only.
+  void set_empty_key(const key_type& key)     { rep.set_empty_key(key); }
+  key_type empty_key() const                  { return rep.empty_key(); }
+
+  void set_deleted_key(const key_type& key)   { rep.set_deleted_key(key); }
+  void clear_deleted_key()                    { rep.clear_deleted_key(); }
+  key_type deleted_key() const                { return rep.deleted_key(); }
+
+  // These are standard
+  size_type erase(const key_type& key)               { return rep.erase(key); }
+  void erase(iterator it)                            { rep.erase(it); }
+  void erase(iterator f, iterator l)                 { rep.erase(f, l); }
+
+
+  // Comparison
+  bool operator==(const dense_hash_set& hs) const    { return rep == hs.rep; }
+  bool operator!=(const dense_hash_set& hs) const    { return rep != hs.rep; }
+
+
+  // I/O -- this is an add-on for writing metainformation to disk
+  //
+  // For maximum flexibility, this does not assume a particular
+  // file type (though it will probably be a FILE *).  We just pass
+  // the fp through to rep.
+
+  // If your keys and values are simple enough, you can pass this
+  // serializer to serialize()/unserialize().  "Simple enough" means
+  // value_type is a POD type that contains no pointers.  Note,
+  // however, we don't try to normalize endianness.
+  typedef typename ht::NopointerSerializer NopointerSerializer;
+
+  // serializer: a class providing operator()(OUTPUT*, const value_type&)
+  //    (writing value_type to OUTPUT).  You can specify a
+  //    NopointerSerializer object if appropriate (see above).
+  // fp: either a FILE*, OR an ostream*/subclass_of_ostream*, OR a
+  //    pointer to a class providing size_t Write(const void*, size_t),
+  //    which writes a buffer into a stream (which fp presumably
+  //    owns) and returns the number of bytes successfully written.
+  //    Note basic_ostream<not_char> is not currently supported.
+  template <typename ValueSerializer, typename OUTPUT>
+  bool serialize(ValueSerializer serializer, OUTPUT* fp) {
+    return rep.serialize(serializer, fp);
+  }
+
+  // serializer: a functor providing operator()(INPUT*, value_type*)
+  //    (reading from INPUT and into value_type).  You can specify a
+  //    NopointerSerializer object if appropriate (see above).
+  // fp: either a FILE*, OR an istream*/subclass_of_istream*, OR a
+  //    pointer to a class providing size_t Read(void*, size_t),
+  //    which reads into a buffer from a stream (which fp presumably
+  //    owns) and returns the number of bytes successfully read.
+  //    Note basic_istream<not_char> is not currently supported.
+  template <typename ValueSerializer, typename INPUT>
+  bool unserialize(ValueSerializer serializer, INPUT* fp) {
+    return rep.unserialize(serializer, fp);
+  }
+};
+
+template <class Val, class HashFcn, class EqualKey, class Alloc>
+inline void swap(dense_hash_set<Val, HashFcn, EqualKey, Alloc>& hs1,
+                 dense_hash_set<Val, HashFcn, EqualKey, Alloc>& hs2) {
+  hs1.swap(hs2);
+}
+
+_END_GOOGLE_NAMESPACE_
+
+#endif /* _DENSE_HASH_SET_H_ */