Re: RCS log gets up to large numbers of revisions then RCS will core dump

From b668481a28bde811ba25fe6d4dee569a736464e3 Mon Sep 17 00:00:00 2001
From: Paul Eggert <[email protected]>
Date: Wed, 26 Oct 2016 12:17:19 -0700
Subject: [PATCH] [int] Fix stack crash for long branches
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

This does not fix all recursive calls, just enough to fix
likely cases, including the bug report by Haoming Chu at:
http://lists.gnu.org/archive/html/bug-rcs/2016-10/msg00002.html
* rlog.c (putadelta): Do not check ‘node->selector’; now the
caller’s responsibility.  Remove arg TRUNK; now inferred from
other args.  All callers changed.
(putadelta, putrunk): Omit ‘register’ as the compiler should
figure this stuff out nowadays.
* rcsgen.c (putree):
* rlog.c (putree, exttree, recentdate, extdate):
Avoid recursion in the common case where !root->branches.
* rlog.c (putree): Avoid recursion when outputting the last tree
in the forest.
(putabranch): Do not check whether arg is null; now the
caller’s responsibility.  Avoid recursion in the common case
where !root->selector.
(putforest): Return last tree in the forest.
(extractdelta): Return bool, not char.
(extdate): Return size_t, not int.  All callers changed.
---
 src/ChangeLog |  24 ++++++++
 src/rcsgen.c  |  25 +++++---
 src/rlog.c    | 187 ++++++++++++++++++++++++++++++++--------------------------
 3 files changed, 143 insertions(+), 93 deletions(-)

diff --git a/src/ChangeLog b/src/ChangeLog
index 7f6a1aa..e047a29 100644
--- a/src/ChangeLog
+++ b/src/ChangeLog
@@ -1,3 +1,27 @@
+2016-10-26  Paul Eggert  <[email protected]>
+
+	[int] Fix stack crash for long branches
+
+	This does not fix all recursive calls, just enough to fix
+	likely cases, including the bug report by Haoming Chu at:
+	http://lists.gnu.org/archive/html/bug-rcs/2016-10/msg00002.html
+	* rlog.c (putadelta): Do not check ‘node->selector’; now the
+	caller’s responsibility.  Remove arg TRUNK; now inferred from
+	other args.  All callers changed.
+	(putadelta, putrunk): Omit ‘register’ as the compiler should
+	figure this stuff out nowadays.
+	* rcsgen.c (putree):
+	* rlog.c (putree, exttree, recentdate, extdate):
+	Avoid recursion in the common case where !root->branches.
+	* rlog.c (putree): Avoid recursion when outputting the last tree
+	in the forest.
+	(putabranch): Do not check whether arg is null; now the
+	caller’s responsibility.  Avoid recursion in the common case
+	where !root->selector.
+	(putforest): Return last tree in the forest.
+	(extractdelta): Return bool, not char.
+	(extdate): Return size_t, not int.  All callers changed.
+
 2016-10-25  Paul Eggert  <[email protected]>
 
 	[int] Fix stack crash and port to non-VLA
diff --git a/src/rcsgen.c b/src/rcsgen.c
index 32222ac..ed827c6 100644
--- a/src/rcsgen.c
+++ b/src/rcsgen.c
@@ -461,16 +461,23 @@ void
 puttree (struct delta const *root, register FILE *fout)
 /* Output the delta tree with base ‘root’ in preorder to ‘fout’.  */
 {
-  if (!root)
-    return;
-
-  if (root->selector)
-    putdelta (root, fout);
-
-  puttree (root->ilk, fout);
+  while (root)
+    {
+      if (root->selector)
+        putdelta (root, fout);
 
-  for (struct wlink *ls = root->branches; ls; ls = ls->next)
-    puttree (ls->entry, fout);
+      struct wlink *ls = root->branches;
+      if (! ls)
+        root = root->ilk;
+      else
+        {
+          /* FIXME: This recurses deeply in the worst case.  */
+          puttree (root->ilk, fout);
+          for (; ls->next; ls = ls->next)
+            puttree (ls->entry, fout);
+          root = ls->entry;
+        }
+    }
 }
 
 bool
diff --git a/src/rlog.c b/src/rlog.c
index d1915bf..f5fa370 100644
--- a/src/rlog.c
+++ b/src/rlog.c
@@ -158,22 +158,16 @@ count_a_d (long *a, long *d, struct atat *edits)
 }
 
 static void
-putadelta (register struct delta const *node,
-           register struct delta const *editscript,
-           bool trunk, const char *insDelFormat)
-/* Print delta ‘node’ if ‘node->selector’ is set.
-   ‘editscript’ indicates where the editscript is stored;
-   ‘trunk’ !false indicates this node is in trunk.  */
+putadelta (struct delta const *node, struct delta const *editscript,
+           char const *insDelFormat)
+/* Print delta ‘node’.  ‘editscript’ indicates where the editscript is
+   stored; it equals ‘node’ if this node is not in trunk.  */
 {
-  register FILE *out;
+  FILE *out = stdout;
   char datebuf[datesize + zonelenmax];
   bool pre5 = BE (version) < VERSION (5);
   struct atat *log;
 
-  if (!node->selector)
-    return;
-
-  out = stdout;
   aprintf (out, "----------------------------\nrevision %s%s",
            node->num, pre5 ? "        " : "");
   if (node->lockedby)
@@ -184,6 +178,7 @@ putadelta (register struct delta const *node,
 
   if (editscript && editscript != REPO (tip))
     {
+      bool trunk = node != editscript;
       long a, d;
 
       count_a_d (trunk ? &d : &a,
@@ -218,47 +213,60 @@ static void
 putrunk (const char *insDelFormat)
 /* Print revisions chosen, which are in trunk.  */
 {
-  register struct delta const *ptr;
-
-  for (ptr = REPO (tip); ptr; ptr = ptr->ilk)
-    putadelta (ptr, ptr->ilk, true, insDelFormat);
+  for (struct delta const *ptr = REPO (tip); ptr; ptr = ptr->ilk)
+    if (ptr->selector)
+      putadelta (ptr, ptr->ilk, insDelFormat);
 }
 
-static void putforest (struct wlink const *branchroot, const char *insDelFormat);
+static struct delta const *putforest (struct wlink const *, const char *);
 
 static void
 putree (struct delta const *root, const char *insDelFormat)
 /* Print delta tree from ‘root’ (not including trunk)
    in reverse order on each branch.  */
 {
-  if (!root)
-    return;
-  putree (root->ilk, insDelFormat);
-  putforest (root->branches, insDelFormat);
+  while (root)
+    if (! root->branches)
+      root = root->ilk;
+    else
+      {
+        /* FIXME: This recurses deeply in the worst case.  */
+        putree (root->ilk, insDelFormat);
+        root = putforest (root->branches, insDelFormat);
+      }
 }
 
 static void
 putabranch (struct delta const *root, const char *insDelFormat)
 /* Print one branch from ‘root’.  */
 {
-  if (!root)
-    return;
-  putabranch (root->ilk, insDelFormat);
-  putadelta (root, root, false, insDelFormat);
+  while (!root->selector)
+    {
+      root = root->ilk;
+      if (!root)
+        return;
+    }
+
+  /* FIXME: This recurses deeply in the worst case.  */
+  if (root->ilk)
+    putabranch (root->ilk, insDelFormat);
+
+  putadelta (root, root, insDelFormat);
 }
 
-static void
+static struct delta const *
 putforest (struct wlink const *branchroot, const char *insDelFormat)
 /* Print branches that have the same direct ancestor ‘branchroot’.  */
 {
-  if (!branchroot)
-    return;
-  putforest (branchroot->next, insDelFormat);
+  /* FIXME: This recurses deeply in the worst case.  */
+  if (branchroot->next)
+    putforest (branchroot->next, insDelFormat);
+
   putabranch (branchroot->entry, insDelFormat);
-  putree (branchroot->entry, insDelFormat);
+  return branchroot->entry;
 }
 
-static char
+static bool
 extractdelta (struct delta const *pdelta, bool lockflag,
               struct criteria *criteria)
 /* Return true if ‘pdelta’ matches the selection critera.  */
@@ -301,17 +309,23 @@ exttree (struct delta *root, bool lockflag,
          struct criteria *criteria)
 /* Select revisions, starting with ‘root’.  */
 {
-  if (!root)
-    return;
-
-  root->selector = extractdelta (root, lockflag, criteria);
-  root->pretty_log.string = NULL;
-#define RECURSE(x)  exttree (x, lockflag, criteria)
-  RECURSE (root->ilk);
+  while (root)
+    {
+      root->selector = extractdelta (root, lockflag, criteria);
+      root->pretty_log.string = NULL;
 
-  for (struct wlink *ls = root->branches; ls; ls = ls->next)
-    RECURSE (ls->entry);
-#undef RECURSE
+      if (! root->branches)
+        root = root->ilk;
+      else
+        {
+          /* FIXME: This recurses deeply in the worst case.  */
+          struct wlink *ls;
+          exttree (root->ilk, lockflag, criteria);
+          for (ls = root->branches; ls->next; ls = ls->next)
+            exttree (ls->entry, lockflag, criteria);
+          root = ls->entry;
+        }
+    }
 }
 
 static void
@@ -427,73 +441,78 @@ recentdate (struct delta const *root, struct daterange *r)
    interval given by ‘pd’, and set the ‘strtdate’ of ‘pd’ to the date
    of the selected delta.  */
 {
-  if (!root)
-    return;
-  if (root->selector)
+  while (root)
     {
-      if (!DATE_LT (root->date, r->beg)
+      if (root->selector
+          && !DATE_LT (root->date, r->beg)
           && !DATE_GT (root->date, r->end))
         {
           strncpy (r->beg, root->date, datesize);
           r->beg[datesize - 1] = '\0';
         }
-    }
 
-  recentdate (root->ilk, r);
-  for (struct wlink *ls = root->branches; ls; ls = ls->next)
-    recentdate (ls->entry, r);
+      struct wlink *ls = root->branches;
+      if (!ls)
+        root = root->ilk;
+      else
+        {
+          /* FIXME: This recurses deeply in the worst case.  */
+          for (; ls->next; ls = ls->next)
+            recentdate (ls->entry, r);
+          root = ls->entry;
+        }
+    }
 }
 
-static int
+static size_t
 extdate (struct delta *root, struct date_selection *datesel)
 /* Select revisions which are in the date range specified in ‘datesel->by’
    and ‘datesel->in’, starting at ‘root’.  Return number of revisions
    selected, including those already selected.  */
 {
-  int revno;
+  size_t revno = 0;
 
-  if (!root)
-    return 0;
-
-  if (datesel->in || datesel->by)
+  for (; root; root = root->ilk)
     {
-      struct daterange const *r;
-      bool oep, sel = false;
-
-      for (struct link *ls = datesel->in; ls; ls = ls->next)
+      if (datesel->in || datesel->by)
         {
-          r = ls->entry;
-          oep = r->oep;
-          if ((sel = ((!r->beg[0]
-                       || (oep
-                           ? DATE_LT (r->beg, root->date)
-                           : !DATE_GT (r->beg, root->date)))
-                      &&
-                      (!r->end[0]
-                       || (oep
-                           ? DATE_LT (root->date, r->end)
-                           : !DATE_GT (root->date, r->end))))))
-            break;
-        }
-      if (!sel)
-        {
-          for (struct link *ls = datesel->by; ls; ls = ls->next)
+          struct daterange const *r;
+          bool oep, sel = false;
+
+          for (struct link *ls = datesel->in; ls; ls = ls->next)
             {
               r = ls->entry;
-              if ((sel = DATE_EQ (root->date, r->beg)))
+              oep = r->oep;
+              if ((sel = ((!r->beg[0]
+                           || (oep
+                               ? DATE_LT (r->beg, root->date)
+                               : !DATE_GT (r->beg, root->date)))
+                          &&
+                          (!r->end[0]
+                           || (oep
+                               ? DATE_LT (root->date, r->end)
+                               : !DATE_GT (root->date, r->end))))))
                 break;
             }
           if (!sel)
-            root->selector = false;
+            {
+              for (struct link *ls = datesel->by; ls; ls = ls->next)
+                {
+                  r = ls->entry;
+                  if ((sel = DATE_EQ (root->date, r->beg)))
+                    break;
+                }
+              if (!sel)
+                root->selector = false;
+            }
         }
-    }
 
-#define RECURSE(x)  extdate (x, datesel)
-  revno = root->selector + RECURSE (root->ilk);
+      revno += root->selector;
 
-  for (struct wlink *ls = root->branches; ls; ls = ls->next)
-    revno += RECURSE (ls->entry);
-#undef RECURSE
+      /* FIXME: This recurses deeply in the worst case.  */
+      for (struct wlink *ls = root->branches; ls; ls = ls->next)
+        revno += extdate (ls->entry, datesel);
+    }
 
   return revno;
 }
@@ -750,7 +769,7 @@ rlog_main (const char *cmd, int argc, char **argv)
   bool onlyRCSflag;                    /* print only RCS filename */
   bool pre5;
   bool shownames;
-  int revno;
+  size_t revno;
 
   CHECK_HV (cmd);
   gnurcs_init (&program);
@@ -969,7 +988,7 @@ rlog_main (const char *cmd, int argc, char **argv)
 
             revno = extdate (tip, &datesel);
 
-            aprintf (out, ";\tselected revisions: %d", revno);
+            aprintf (out, ";\tselected revisions: %zu", revno);
           }
 
         newline (out);
-- 
2.7.4