[libcpp] Reimplement mkdeps data structures

[Nathan Sidwell <nathan at acm dot org>]

This patch reimplements the header dependency data structures.  We can 
now use a vector class, rather than cut-n-paste 3 sets of bespoke 
C-style array handling.  Sadly, simply using vec.h didn't work, so I do 
have one internal vector class.

The other change is that, rather than apply quoting on adding the 
dependencies, we apply it when writing them out.  This'll permit writing 
the dependencies in different forms (later).  Because we have both -MT 
already-quoted-target and MQ apply-quote-target we need to remember 
which was used.  Fortunately, we record these targets first, so we can 
just record when we stopped adding already-quoted targets.

nathan
--
Nathan Sidwell

2019-05-07  Nathan Sidwell  <nathan@acm.org>

	* include/mkdeps.h (deps_write): Add PHONY arg.
	(deps_phony_targets): Delete.
	* init.c (cpp_finish): Just call deps_write.
	* mkdeps.c (struct mkdeps): Add local vector class.  Reimplement
	vector handling.
	(munge): Munge to static buffer.
	(apply_vpath): Adjust vector handling.
	(deps_init, deps_free): Use new, delete.
	(deps_add_target): Do not munge here.  Record quoting low water mark.
	(deps_add_dep): Do not munge here.
	(deps_add_vpath): Adjust vector handling.
	(make_write_name): New.  Munge on demand here.
	(make_write_vec): New.
	(deps_phony_targets): Delete.
	(make_write): New.
	(deps_write): Forward to deps_Write.
	(deps_save, deps_restore): Adjust vector handling.

Index: libcpp/include/mkdeps.h
===================================================================
--- libcpp/include/mkdeps.h	(revision 270940)
+++ libcpp/include/mkdeps.h	(working copy)
@@ -57,7 +57,7 @@ extern void deps_add_dep (struct mkdeps
 
 /* Write out a deps buffer to a specified file.  The third argument
    is the number of columns to word-wrap at (0 means don't wrap).  */
-extern void deps_write (const struct mkdeps *, FILE *, unsigned int);
+extern void deps_write (const struct mkdeps *, FILE *, bool, unsigned int);
 
 /* Write out a deps buffer to a file, in a form that can be read back
    with deps_restore.  Returns nonzero on error, in which case the
@@ -70,10 +70,4 @@ extern int deps_save (struct mkdeps *, F
    in which case that filename is skipped.  */
 extern int deps_restore (struct mkdeps *, FILE *, const char *);
 
-/* For each dependency *except the first*, emit a dummy rule for that
-   file, causing it to depend on nothing.  This is used to work around
-   the intermediate-file deletion misfeature in Make, in some
-   automatic dependency schemes.  */
-extern void deps_phony_targets (const struct mkdeps *, FILE *);
-
 #endif /* ! LIBCPP_MKDEPS_H */
Index: libcpp/init.c
===================================================================
--- libcpp/init.c	(revision 270940)
+++ libcpp/init.c	(working copy)
@@ -764,14 +764,9 @@ cpp_finish (cpp_reader *pfile, FILE *dep
   while (pfile->buffer)
     _cpp_pop_buffer (pfile);
 
-  if (CPP_OPTION (pfile, deps.style) != DEPS_NONE
-      && deps_stream)
-    {
-      deps_write (pfile->deps, deps_stream, 72);
-
-      if (CPP_OPTION (pfile, deps.phony_targets))
-	deps_phony_targets (pfile->deps, deps_stream);
-    }
+  if (CPP_OPTION (pfile, deps.style) != DEPS_NONE && deps_stream)
+    deps_write (pfile->deps, deps_stream,
+		CPP_OPTION (pfile, deps.phony_targets), 72);
 
   /* Report on headers that could use multiple include guards.  */
   if (CPP_OPTION (pfile, print_include_names))
Index: libcpp/mkdeps.c
===================================================================
--- libcpp/mkdeps.c	(revision 270940)
+++ libcpp/mkdeps.c	(working copy)
@@ -24,99 +24,157 @@ along with this program; see the file CO
 #include "system.h"
 #include "mkdeps.h"
 
+/* Not set up to just include std::vector et al, here's a simple
+   implementation.  */
+
 /* Keep this structure local to this file, so clients don't find it
    easy to start making assumptions.  */
 struct mkdeps
 {
-  const char **targetv;
-  unsigned int ntargets;	/* number of slots actually occupied */
-  unsigned int targets_size;	/* amt of allocated space - in words */
-
-  const char **depv;
-  unsigned int ndeps;
-  unsigned int deps_size;
-
-  const char **vpathv;
-  size_t *vpathlv;
-  unsigned int nvpaths;
-  unsigned int vpaths_size;
-};
+public:
+  /* T has trivial cctor & dtor.  */
+  template <typename T>
+  class vec
+  {
+  private:
+    T *ary;
+    unsigned num;
+    unsigned alloc;
+
+  public:
+    vec ()
+      : ary (NULL), num (0), alloc (0)
+      {}
+    ~vec ()
+      {
+	XDELETEVEC (ary);
+      }
+
+  public:
+    unsigned size () const
+    {
+      return num;
+    }
+    const T &operator[] (unsigned ix) const
+    {
+      return ary[ix];
+    }
+    void push (const T &elt)
+    {
+      if (num == alloc)
+	{
+	  alloc = alloc ? alloc * 2 : 16;
+	  ary = XRESIZEVEC (T, ary, alloc);
+	}
+      ary[num++] = elt;
+    }
+  };
+  struct velt
+  {
+    const char *str;
+    size_t len;
+  };
+
+  mkdeps ()
+    : quote_lwm (0)
+  {
+  }
+  ~mkdeps ()
+  {
+    unsigned int i;
+
+    for (i = targets.size (); i--;)
+      free (const_cast <char *> (targets[i]));
+    for (i = deps.size (); i--;)
+      free (const_cast <char *> (deps[i]));
+    for (i = vpath.size (); i--;)
+      XDELETEVEC (vpath[i].str);
+  }
+
+public:
+  vec<const char *> targets;
+  vec<const char *> deps;
+  vec<velt> vpath;
 
-static const char *munge (const char *);
+public:
+  unsigned short quote_lwm;
+};
 
-/* Given a filename, quote characters in that filename which are
-   significant to Make.  Note that it's not possible to quote all such
-   characters - e.g. \n, %, *, ?, [, \ (in some contexts), and ~ are
-   not properly handled.  It isn't possible to get this right in any
-   current version of Make.  (??? Still true?  Old comment referred to
-   3.76.1.)  */
+/* Apply Make quoting to STR, TRAIL etc.  Note that it's not possible
+   to quote all such characters - e.g. \n, %, *, ?, [, \ (in some
+   contexts), and ~ are not properly handled.  It isn't possible to
+   get this right in any current version of Make.  (??? Still true?
+   Old comment referred to 3.76.1.)  */
 
 static const char *
-munge (const char *filename)
+munge (const char *str, const char *trail = NULL, ...)
 {
-  int len;
-  const char *p, *q;
-  char *dst, *buffer;
-
-  for (p = filename, len = 0; *p; p++, len++)
-    {
-      switch (*p)
+  static unsigned alloc;
+  static char *buf;
+  unsigned dst = 0;
+  va_list args;
+  if (trail)
+    va_start (args, trail);
+
+  for (bool first = true; str; first = false)
+    {
+      unsigned slashes = 0;
+      char c;
+      for (const char *probe = str; (c = *probe++);)
 	{
-	case ' ':
-	case '\t':
-	  /* GNU make uses a weird quoting scheme for white space.
-	     A space or tab preceded by 2N+1 backslashes represents
-	     N backslashes followed by space; a space or tab
-	     preceded by 2N backslashes represents N backslashes at
-	     the end of a file name; and backslashes in other
-	     contexts should not be doubled.  */
-	  for (q = p - 1; filename <= q && *q == '\\';  q--)
-	    len++;
-	  len++;
-	  break;
-
-	case '$':
-	  /* '$' is quoted by doubling it.  */
-	  len++;
-	  break;
-
-	case '#':
-	  /* '#' is quoted with a backslash.  */
-	  len++;
-	  break;
-	}
-    }
+	  if (alloc < dst + 4 + slashes)
+	    {
+	      alloc = alloc * 2 + 32;
+	      buf = XRESIZEVEC (char, buf, alloc);
+	    }
 
-  /* Now we know how big to make the buffer.  */
-  buffer = XNEWVEC (char, len + 1);
+	  switch (c)
+	    {
+	    case '\\':
+	      slashes++;
+	      break;
 
-  for (p = filename, dst = buffer; *p; p++, dst++)
-    {
-      switch (*p)
-	{
-	case ' ':
-	case '\t':
-	  for (q = p - 1; filename <= q && *q == '\\';  q--)
-	    *dst++ = '\\';
-	  *dst++ = '\\';
-	  break;
-
-	case '$':
-	  *dst++ = '$';
-	  break;
-
-	case '#':
-	  *dst++ = '\\';
-	  break;
+	    case '$':
+	      buf[dst++] = '$';
+	      goto def;
+
+	    case ' ':
+	    case '\t':
+	      /* GNU make uses a weird quoting scheme for white space.
+		 A space or tab preceded by 2N+1 backslashes
+		 represents N backslashes followed by space; a space
+		 or tab preceded by 2N backslashes represents N
+		 backslashes at the end of a file name; and
+		 backslashes in other contexts should not be
+		 doubled.  */
+	      while (slashes--)
+		buf[dst++] = '\\';
+	      /* FALLTHROUGH  */
+
+	    case '#':
+	    case ':':
+	      buf[dst++] = '\\';
+	      /* FALLTHROUGH  */
+
+	    default:
+	    def:
+	      slashes = 0;
+	      break;
+	    }
 
-	default:
-	  /* nothing */;
+	  buf[dst++] = c;
 	}
-      *dst = *p;
+
+      if (first)
+	str = trail;
+      else
+	str = va_arg (args, const char *);
     }
+  if (trail)
+    va_end (args);
 
-  *dst = '\0';
-  return buffer;
+  buf[dst] = 0;
+  return buf;
 }
 
 /* If T begins with any of the partial pathnames listed in d->vpathv,
@@ -124,29 +182,26 @@ munge (const char *filename)
 static const char *
 apply_vpath (struct mkdeps *d, const char *t)
 {
-  if (d->vpathv)
-    {
-      unsigned int i;
-      for (i = 0; i < d->nvpaths; i++)
-	{
-	  if (!filename_ncmp (d->vpathv[i], t, d->vpathlv[i]))
-	    {
-	      const char *p = t + d->vpathlv[i];
-	      if (!IS_DIR_SEPARATOR (*p))
-		goto not_this_one;
-
-	      /* Do not simplify $(vpath)/../whatever.  ??? Might not
-		 be necessary. */
-	      if (p[1] == '.' && p[2] == '.' && IS_DIR_SEPARATOR (p[3]))
-		goto not_this_one;
-
-	      /* found a match */
-	      t = t + d->vpathlv[i] + 1;
-	      break;
-	    }
-	not_this_one:;
-	}
-    }
+  if (unsigned len = d->vpath.size ())
+    for (unsigned i = len; i--;)
+      {
+	if (!filename_ncmp (d->vpath[i].str, t, d->vpath[i].len))
+	  {
+	    const char *p = t + d->vpath[i].len;
+	    if (!IS_DIR_SEPARATOR (*p))
+	      goto not_this_one;
+
+	    /* Do not simplify $(vpath)/../whatever.  ??? Might not
+	       be necessary. */
+	    if (p[1] == '.' && p[2] == '.' && IS_DIR_SEPARATOR (p[3]))
+	      goto not_this_one;
+
+	    /* found a match */
+	    t = t + d->vpath[i].len + 1;
+	    break;
+	  }
+      not_this_one:;
+      }
 
   /* Remove leading ./ in any case.  */
   while (t[0] == '.' && IS_DIR_SEPARATOR (t[1]))
@@ -166,37 +221,13 @@ apply_vpath (struct mkdeps *d, const cha
 struct mkdeps *
 deps_init (void)
 {
-  return XCNEW (struct mkdeps);
+  return new mkdeps ();
 }
 
 void
 deps_free (struct mkdeps *d)
 {
-  unsigned int i;
-
-  if (d->targetv)
-    {
-      for (i = 0; i < d->ntargets; i++)
-	free ((void *) d->targetv[i]);
-      free (d->targetv);
-    }
-
-  if (d->depv)
-    {
-      for (i = 0; i < d->ndeps; i++)
-	free ((void *) d->depv[i]);
-      free (d->depv);
-    }
-
-  if (d->vpathv)
-    {
-      for (i = 0; i < d->nvpaths; i++)
-	free ((void *) d->vpathv[i]);
-      free (d->vpathv);
-      free (d->vpathlv);
-    }
-
-  free (d);
+  delete d;
 }
 
 /* Adds a target T.  We make a copy, so it need not be a permanent
@@ -204,19 +235,14 @@ deps_free (struct mkdeps *d)
 void
 deps_add_target (struct mkdeps *d, const char *t, int quote)
 {
-  if (d->ntargets == d->targets_size)
+  t = apply_vpath (d, t);
+  if (!quote)
     {
-      d->targets_size = d->targets_size * 2 + 4;
-      d->targetv = XRESIZEVEC (const char *, d->targetv, d->targets_size);
+      gcc_assert (d->quote_lwm == d->targets.size ());
+      d->quote_lwm++;
     }
 
-  t = apply_vpath (d, t);
-  if (quote)
-    t = munge (t);  /* Also makes permanent copy.  */
-  else
-    t = xstrdup (t);
-
-  d->targetv[d->ntargets++] = t;
+  d->targets.push (xstrdup (t));
 }
 
 /* Sets the default target if none has been given already.  An empty
@@ -226,7 +252,7 @@ void
 deps_add_default_target (struct mkdeps *d, const char *tgt)
 {
   /* Only if we have no targets.  */
-  if (d->ntargets)
+  if (d->targets.size ())
     return;
 
   if (tgt[0] == '\0')
@@ -255,110 +281,106 @@ deps_add_default_target (struct mkdeps *
 void
 deps_add_dep (struct mkdeps *d, const char *t)
 {
-  t = munge (apply_vpath (d, t));  /* Also makes permanent copy.  */
+  t = apply_vpath (d, t);
 
-  if (d->ndeps == d->deps_size)
-    {
-      d->deps_size = d->deps_size * 2 + 8;
-      d->depv = XRESIZEVEC (const char *, d->depv, d->deps_size);
-    }
-  d->depv[d->ndeps++] = t;
+  d->deps.push (xstrdup (t));
 }
 
 void
 deps_add_vpath (struct mkdeps *d, const char *vpath)
 {
   const char *elem, *p;
-  char *copy;
-  size_t len;
 
   for (elem = vpath; *elem; elem = p)
     {
-      for (p = elem; *p && *p != ':'; p++);
-      len = p - elem;
-      copy = XNEWVEC (char, len + 1);
-      memcpy (copy, elem, len);
-      copy[len] = '\0';
+      for (p = elem; *p && *p != ':'; p++)
+	continue;
+      mkdeps::velt elt;
+      elt.len = p - elem;
+      char *str = XNEWVEC (char, elt.len + 1);
+      elt.str = str;
+      memcpy (str, elem, elt.len);
+      str[elt.len] = '\0';
       if (*p == ':')
 	p++;
 
-      if (d->nvpaths == d->vpaths_size)
-	{
-	  d->vpaths_size = d->vpaths_size * 2 + 8;
-	  d->vpathv = XRESIZEVEC (const char *, d->vpathv, d->vpaths_size);
-	  d->vpathlv = XRESIZEVEC (size_t, d->vpathlv, d->vpaths_size);
-	}
-      d->vpathv[d->nvpaths] = copy;
-      d->vpathlv[d->nvpaths] = len;
-      d->nvpaths++;
+      d->vpath.push (elt);
     }
 }
 
-void
-deps_write (const struct mkdeps *d, FILE *fp, unsigned int colmax)
-{
-  unsigned int size, i, column;
+/* Write NAME, with a leading space to FP, a Makefile.  Advance COL as
+   appropriate, wrap at COLMAX, returning new column number.  Iff
+   QUOTE apply quoting.  Append TRAIL.  */
 
-  column = 0;
-  if (colmax && colmax < 34)
-    colmax = 34;
+static unsigned
+make_write_name (const char *name, FILE *fp, unsigned col, unsigned colmax,
+		 bool quote = true, const char *trail = NULL)
+{
+  if (quote)
+    name = munge (name, trail, NULL);
+  unsigned size = strlen (name);
 
-  for (i = 0; i < d->ntargets; i++)
+  if (col)
     {
-      size = strlen (d->targetv[i]);
-      column += size;
-      if (i)
+      if (colmax && col + size> colmax)
 	{
-	  if (colmax && column > colmax)
-	    {
-	      fputs (" \\\n ", fp);
-	      column = 1 + size;
-	    }
-	  else
-	    {
-	      putc (' ', fp);
-	      column++;
-	    }
+	  fputs (" \\\n", fp);
+	  col = 0;
 	}
-      fputs (d->targetv[i], fp);
+      col++;
+      fputs (" ", fp);
     }
 
-  putc (':', fp);
-  column++;
+  col += size;
+  fputs (name, fp);
 
-  for (i = 0; i < d->ndeps; i++)
-    {
-      size = strlen (d->depv[i]);
-      column += size;
-      if (colmax && column > colmax)
-	{
-	  fputs (" \\\n ", fp);
-	  column = 1 + size;
-	}
-      else
-	{
-	  putc (' ', fp);
-	  column++;
-	}
-      fputs (d->depv[i], fp);
-    }
-  putc ('\n', fp);
+  return col;
 }
 
-void
-deps_phony_targets (const struct mkdeps *d, FILE *fp)
+/* Write all the names in VEC via make_write_name.  */
+
+static unsigned
+make_write_vec (const mkdeps::vec<const char *> &vec, FILE *fp,
+		unsigned col, unsigned colmax, unsigned quote_lwm = 0,
+		const char *trail = NULL)
 {
-  unsigned int i;
+  for (unsigned ix = 0; ix != vec.size (); ix++)
+    col = make_write_name (vec[ix], fp, col, colmax, ix >= quote_lwm, trail);
+  return col;
+}
+
+/* Write the dependencies to a Makefile.  If PHONY is true, add
+   .PHONY targets for all the dependencies too.  */
 
-  for (i = 1; i < d->ndeps; i++)
+static void
+make_write (const struct mkdeps *d, FILE *fp, bool phony, unsigned int colmax)
+{
+  unsigned column = 0;
+  if (colmax && colmax < 34)
+    colmax = 34;
+
+  if (d->deps.size ())
     {
-      putc ('\n', fp);
-      fputs (d->depv[i], fp);
-      putc (':', fp);
-      putc ('\n', fp);
+      column = make_write_vec (d->targets, fp, 0, colmax, d->quote_lwm);
+      fputs (":", fp);
+      column++;
+      column = make_write_vec (d->deps, fp, column, colmax);
+      fputs ("\n", fp);
+      if (phony)
+	for (unsigned i = 1; i < d->deps.size (); i++)
+	  fprintf (fp, "%s:\n", munge (d->deps[i]));
     }
 }
 
+/* Write out dependencies according to the selected format (which is
+   only Make at the moment).  */
+
+void
+deps_write (const struct mkdeps *d, FILE *fp, bool phony, unsigned int colmax)
+{
+  make_write (d, fp, phony, colmax);
+}
+
 /* Write out a deps buffer to a file, in a form that can be read back
    with deps_restore.  Returns nonzero on error, in which case the
    error number will be in errno.  */
@@ -367,71 +389,69 @@ int
 deps_save (struct mkdeps *deps, FILE *f)
 {
   unsigned int i;
+  size_t size;
 
   /* The cppreader structure contains makefile dependences.  Write out this
      structure.  */
 
   /* The number of dependences.  */
-  if (fwrite (&deps->ndeps, sizeof (deps->ndeps), 1, f) != 1)
-      return -1;
+  size = deps->deps.size ();
+  if (fwrite (&size, sizeof (size), 1, f) != 1)
+    return -1;
+
   /* The length of each dependence followed by the string.  */
-  for (i = 0; i < deps->ndeps; i++)
+  for (i = 0; i < deps->deps.size (); i++)
     {
-      size_t num_to_write = strlen (deps->depv[i]);
-      if (fwrite (&num_to_write, sizeof (size_t), 1, f) != 1)
-          return -1;
-      if (fwrite (deps->depv[i], num_to_write, 1, f) != 1)
-          return -1;
+      size = strlen (deps->deps[i]);
+      if (fwrite (&size, sizeof (size), 1, f) != 1)
+	return -1;
+      if (fwrite (deps->deps[i], size, 1, f) != 1)
+	return -1;
     }
 
   return 0;
 }
 
 /* Read back dependency information written with deps_save into
-   the deps buffer.  The third argument may be NULL, in which case
+   the deps sizefer.  The third argument may be NULL, in which case
    the dependency information is just skipped, or it may be a filename,
    in which case that filename is skipped.  */
 
 int
 deps_restore (struct mkdeps *deps, FILE *fd, const char *self)
 {
-  unsigned int i, count;
-  size_t num_to_read;
-  size_t buf_size = 512;
-  char *buf;
+  size_t size;
+  char *buf = NULL;
+  size_t buf_size = 0;
 
   /* Number of dependences.  */
-  if (fread (&count, 1, sizeof (count), fd) != sizeof (count))
+  if (fread (&size, sizeof (size), 1, fd) != 1)
     return -1;
 
-  buf = XNEWVEC (char, buf_size);
-
   /* The length of each dependence string, followed by the string.  */
-  for (i = 0; i < count; i++)
+  for (unsigned i = size; i--;)
     {
       /* Read in # bytes in string.  */
-      if (fread (&num_to_read, 1, sizeof (size_t), fd) != sizeof (size_t))
-	{
-	  free (buf);
-	  return -1;
-	}
-      if (buf_size < num_to_read + 1)
+      if (fread (&size, sizeof (size), 1, fd) != 1)
+	return -1;
+
+      if (size >= buf_size)
 	{
-	  buf_size = num_to_read + 1 + 127;
+	  buf_size = size + 512;
 	  buf = XRESIZEVEC (char, buf, buf_size);
 	}
-      if (fread (buf, 1, num_to_read, fd) != num_to_read)
+      if (fread (buf, 1, size, fd) != size)
 	{
-	  free (buf);
+	  XDELETEVEC (buf);
 	  return -1;
 	}
-      buf[num_to_read] = '\0';
+      buf[size] = 0;
 
       /* Generate makefile dependencies from .pch if -nopch-deps.  */
       if (self != NULL && filename_cmp (buf, self) != 0)
         deps_add_dep (deps, buf);
     }
 
-  free (buf);
+  XDELETEVEC (buf);
   return 0;
 }