[PATCH] Fix regex bug with empty alternatives

[Jakub Jelinek <jakub at redhat dot com>]

Hi!

(xx|yy||zz) style regex was parsed incorrectly as if it was
(xx|yy|yy|zz) and the node representing xx was shared, leading to double free.
(|xx|yy|zz) or (xx||yy|zz) worked right though, in the second case because
branch was still NULL in parse_reg_exp.

BTW: Why is free_bin_tree implemented using recursion when it could just
walk over the tree (each node has left, right and parent)?

2002-08-08  Jakub Jelinek  <jakub@redhat.com>

	* posix/regcomp.c (parse_reg_exp): If '|' is immediately followed
	by another '|', end of regex or enclosing ')', clear branch.
	* posix/bug-regex9.c: New test.
	* posix/Makefile (tests): Add bug-regex9.

--- libc/posix/regcomp.c.jj	2002-07-29 15:14:54.000000000 +0200
+++ libc/posix/regcomp.c	2002-08-08 21:44:40.000000000 +0200
@@ -1807,6 +1807,8 @@ parse_reg_exp (regexp, preg, token, synt
               return NULL;
             }
         }
+      else
+	branch = NULL;
       tree = create_tree (tree, branch, 0, new_idx);
       if (BE (new_idx == -1 || tree == NULL, 0))
         return *err = REG_ESPACE, NULL;
--- libc/posix/bug-regex9.c.jj	2002-08-08 21:52:47.000000000 +0200
+++ libc/posix/bug-regex9.c	2002-08-08 22:04:14.000000000 +0200
@@ -0,0 +1,67 @@
+/* Test for memory handling in regex.
+   Copyright (C) 2002 Free Software Foundation, Inc.
+   This file is part of the GNU C Library.
+   Contributed by Ulrich Drepper <drepper@redhat.com>, 2001.
+
+   The GNU C Library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 2.1 of the License, or (at your option) any later version.
+
+   The GNU C Library is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with the GNU C Library; if not, write to the Free
+   Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
+   02111-1307 USA.  */
+
+#include <sys/types.h>
+#include <mcheck.h>
+#include <regex.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+
+static const char text[] = "#! /bin/sh";
+
+int
+main (void)
+{
+  regex_t re;
+  regmatch_t rm[2];
+  int n;
+
+  mtrace ();
+
+  n = regcomp (&re, "^#! */.*/(k|ba||pdk|z)sh", REG_EXTENDED);
+  if (n != 0)
+    {
+      char buf[500];
+      regerror (n, &re, buf, sizeof (buf));
+      printf ("regcomp failed: %s\n", buf);
+      exit (1);
+    }
+
+  for (n = 0; n < 20; ++n)
+    {
+      if (regexec (&re, text, 2, rm, 0))
+	{
+	  puts ("regexec failed");
+	  exit (2);
+	}
+      if (rm[0].rm_so != 0 || rm[0].rm_eo != 10
+	  || rm[1].rm_so != 8 || rm[1].rm_eo != 8)
+	{
+	  printf ("regexec match failure: %d %d %d %d\n",
+		  rm[0].rm_so, rm[0].rm_eo, rm[1].rm_so, rm[1].rm_eo);
+	  exit (3);
+	}
+    }
+
+  regfree (&re);
+
+  return 0;
+}
--- libc/posix/Makefile.jj	2002-08-08 10:39:19.000000000 +0200
+++ libc/posix/Makefile	2002-08-08 22:11:50.000000000 +0200
@@ -72,7 +72,7 @@ tests		:= tstgetopt testfnm runtests run
 		   tst-truncate64 tst-fork tst-fnmatch tst-regexloc tst-dir \
 		   tst-chmod bug-regex1 bug-regex2 bug-regex3 bug-regex4 \
 		   tst-gnuglob tst-regex bug-regex5 bug-regex6 bug-regex7 \
-		   bug-regex8
+		   bug-regex8 bug-regex9
 ifeq (yes,$(build-shared))
 test-srcs	:= globtest
 tests           += wordexp-test tst-exec tst-spawn

	Jakub