write the specification of regex implemented

[hirooih]

I've been expecting to update regex engine as #1861. It was because I just wanted to use \s, \S, \w, and \W which I was familiar with via Perl.
Today I found they were already supported the GNU regex which is being used by ctags.

I've been referring man page of e?grep(1), regex(7), and manual of the GNU libc. But they don't describe about the feature.
I searched on the Web, https://www.gnu.org/software/grep/manual/grep.html#Regular-Expressions is the only document I could find.

@masatake -san, if you agree with me, I'd like to update examples in ctags-optlib.7.rst and optlib.rst to use them. It will improve readability of patterns. Some of them do not handle white-spaces correctly, i.e. ...private) +)?func (...

[masatake]

Before starting this task, could you add a case testing \s, \S, \w, and \W to Tmain or Units?
@leleliu008 has added many platforms where our test runs. We can know whether we can expect \s, \S, \w, and \W are available on all the platforms or not.

[hirooih]

Before starting this task, could you add a case testing \s, \S, \w, and \W to Tmain or Units?

PR #3035. Failed on Cygwin, MSYS2, and MacOS 10.15.
Interesting... Is is possible for them to use a different regex engine from gnu_regex/ in the ctags distribution?

[masatake]

If a platform has an implementation of regex library, ctags (build-system) may use it.
The code in gnu_regex/ directory is for the platform where the library is not available.

[hirooih]

If a platform has an implementation of regex library, ctags (build-system) may use it.
The code in gnu_regex/ directory is for the platform where the library is not available.

That makes sense and explains this situation.
Let me think some more.

[hirooih]

@masatake -san,

If a platform has an implementation of regex library, ctags (build-system) may use it.
The code in gnu_regex/ directory is for the platform where the library is not available.

Why don't we use gnu_regex always?

If ctags can use a same regex engine on all platforms, we can ensure the compatibility of optlib parsers among the platforms.
And regex engines on some platform has less functionalities than the GNU regex. \s and \w are very useful for optlib parsers as we see on c18057e.

I tired to use gnu_regex on my MacOS machine and confirmed it passed the new tests.

Here is my fix of `configure.ac*. I'm not familiar with Autoconf. There must be better fixes.

--- a/configure.ac
+++ b/configure.ac
@@ -563,27 +563,11 @@ dnl
 dnl The final result can be check with ./ctags --list-features.
 dnl
 dnl
-AC_CHECK_FUNCS(regcomp,[
-AC_MSG_CHECKING(if regcomp works)
-AC_RUN_IFELSE([AC_LANG_SOURCE([
-#include <sys/types.h>
-#include <regex.h>
-int main(void) {
-   regex_t patbuf;
-   return (regcomp (&patbuf, "/hello/", 0) != 0);
-}
-])],[regcomp_works=yes],[regcomp_works=no],[AC_DEFINE(CHECK_REGCOMP)])
-AC_MSG_RESULT($regcomp_works)
-if test no = "$regcomp_works"; then
-   AC_MSG_ERROR([regcomp() on this system is broken.])
-fi
-have_regcomp=yes
-],[
 dnl Using bundled regex implementation
 AC_LIBOBJ([regex])
 REGCOMP_CPPFLAGS="-I${srcdir}/gnu_regex -D__USE_GNU"
-AC_DEFINE(HAVE_REGCOMP)
-have_regcomp=no])
+AC_DEFINE(HAVE_REGCOMP,0,[use GNU regexp])
+have_regcomp=no
 AC_SUBST([REGCOMP_CPPFLAGS])
 AM_CONDITIONAL([HAVE_REGCOMP], [test "xyes" = "x$have_regcomp"])

And I need one more fix on Ubuntu system.
-D_USE_GNU is specified on the command line, but it is undefined in limits.h. I spent some time to solve this issue.

--- a/gnu_regex/regex.c
+++ b/gnu_regex/regex.c
@@ -57,6 +57,7 @@
    #undefs RE_DUP_MAX and sets it to the right value.  */
 #include <limits.h>

+#define __USE_GNU    // may be undefined by limits.h
 #include "regex.h"
 #include "regex_internal.h"

If you agree, I will add the above fixes to PR #3035. Or I will create a separate PR if you prefer.

[masatake]

I would like to keep gnu_regex/ as the fall-back implementation.

The implementation of gnu_regex/ is old. We have to update it to use widely.
I wonder where we should get the latest version. gnulib?

Fedora that I'm using daily, has newer glibc that may include newer gnu_regex.
I don't use gnu_regex/ in ctags source tree.

The gnu_regex/ in ctags source tree is patched by us.
When updating gnu_regex/ in ctags source tree, we must re-apply the patches.

$ git log --oneline gnu_regex
2ead636db gnu_regex: Suppress warnings
cb6188882 regex: Fix cast error on VC2015 x64
46204f785 Fix a lot of typos
035c7afca Updated to use regex code from glibc.
82268cee8 Updated to use regex code from glibc.
dcc4c8458 Fixed regex support for MinGW. Gnu regex module now included in all distributions.
738646227 Added GNU regex files to SVN control.

These are not so critical. However, if we have time, taking time for using pcre2 in ctags is fruitful.

[masatake]

See #3036.

[hirooih]

See #3036.

Great! I look forward to merging this fix.

---

The implementation of gnu_regex/ is old. We have to update it to use widely.
I wonder where we should get the latest version. gnulib?

Today I tried to import regex from glibc-2.33, the latest stable glibc.
I've confirmed that all of the fixed on ctags (diff between gnu_regex/* and reg*.[ch] in glibc-2.10.1) are already applied.
But I could not compile regex from 2.33 due to missing some include files, libc-config.h, intprops.h, and verify.h, and I gave-up.

For my records, here's what I've confirmed. (The exact same fixes, like typos in comment, are not listed.)
Note that the last one is different from ours. It might be a bug in ctags.

regcomp.c

--- gnu_regex-2.10.1/regcomp.c	2009-01-08 09:42:28.000000000 +0900
+++ gnu_regex/regcomp.c	2021-05-22 23:59:24.908479300 +0900
@@ -2527,7 +2527,7 @@
     old_tree = NULL;
 
   if (elem->token.type == SUBEXP)
-    postorder (elem, mark_opt_subexp, (void *) (long) elem->token.opr.idx);
+    postorder (elem, mark_opt_subexp, (void *) (intptr_t) elem->token.opr.idx);
 
   tree = create_tree (dfa, elem, NULL, (end == -1 ? OP_DUP_ASTERISK : OP_ALT));
   if (BE (tree == NULL, 0))

Fixed as follows;

    {
      uintptr_t subidx = elem->token.opr.idx;
      postorder (elem, mark_opt_subexp, (void *) subidx);
    }

@@ -3740,7 +3740,7 @@
 static reg_errcode_t
 mark_opt_subexp (void *extra, bin_tree_t *node)
 {
-  int idx = (int) (long) extra;
+  int idx = (int) (intptr_t) extra;
   if (node->token.type == SUBEXP && node->token.opr.idx == idx)
     node->token.opt_subexp = 1;

Fixed as follows;

  Idx idx = (uintptr_t) extra;

regex_internal.c

--- gnu_regex-2.10.1/regex_internal.c	2009-01-08 09:22:50.000000000 +0900
+++ gnu_regex/regex_internal.c	2020-09-04 13:16:03.791141600 +0900
@@ -1390,13 +1390,15 @@
 
 
 /* Add the token TOKEN to dfa->nodes, and return the index of the token.
-   Or return -1, if an error will be occured.  */
+   Or return -1, if an error will be occurred.  */
 
 static int
 internal_function
 re_dfa_add_node (re_dfa_t *dfa, re_token_t token)
 {
+#ifdef RE_ENABLE_I18N
   int type = token.type;
+#endif
   if (BE (dfa->nodes_len >= dfa->nodes_alloc, 0))
     {
       size_t new_nodes_alloc = dfa->nodes_alloc * 2;

The typo in comment is fixed.
The variable type is deleted. (token.type is used.)

regex_internal.h

--- gnu_regex-2.10.1/regex_internal.h	2009-01-08 09:23:00.000000000 +0900
+++ gnu_regex/regex_internal.h	2020-09-04 13:16:03.791141600 +0900
@@ -418,7 +418,11 @@
 #define re_string_skip_bytes(pstr,idx) ((pstr)->cur_idx += (idx))
 #define re_string_set_index(pstr,idx) ((pstr)->cur_idx = (idx))
 
-#include <alloca.h>
+#ifdef WIN32
+# include <malloc.h>
+#else
+# include <alloca.h>
+#endif
 
 #ifndef _LIBC
 # if HAVE_ALLOCA

This is fixed as follows;

#if defined _LIBC || HAVE_ALLOCA
# include <alloca.h>
#endif

#ifndef _LIBC
# if HAVE_ALLOCA
...
# else
/* alloca is implemented with malloc, so just use malloc.  */
#  define __libc_use_alloca(n) 0
#  undef alloca
#  define alloca(n) malloc (n)
# endif
#endif

regexec.c

--- gnu_regex-2.10.1/regexec.c	2009-01-08 09:47:05.000000000 +0900
+++ gnu_regex/regexec.c	2020-09-04 13:16:03.791141600 +0900
@@ -227,7 +227,9 @@
 {
   reg_errcode_t err;
   int start, length;
+#ifdef _LIBC
   re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
+#endif
 
   if (eflags & ~(REG_NOTBOL | REG_NOTEOL | REG_STARTEND))
     return REG_BADPAT;
@@ -418,7 +420,9 @@
   regmatch_t *pmatch;
   int nregs, rval;
   int eflags = 0;
+#ifdef _LIBC
   re_dfa_t *dfa = (re_dfa_t *) bufp->buffer;
+#endif
 
   /* Check for out-of-range.  */
   if (BE (start < 0 || start > length, 0))

Now dfa is used even when _LIBC is not defined (for lock_lock() and lock_unlock()).

@@ -468,7 +472,7 @@
 
   rval = 0;
 
-  /* I hope we needn't fill ther regs with -1's when no match was found.  */
+  /* I hope we need not to fill the regs with -1's when no match was found.  */
   if (result != REG_NOERROR)
     rval = -1;
   else if (regs != NULL)

"I hope we needn't fill their regs with -1's when no match was found."

@@ -2899,7 +2903,7 @@
 	      sizeof (re_dfastate_t *) * (path->alloc - old_alloc));
     }
 
-  str_idx = path->next_idx ?: top_str;
+  str_idx = path->next_idx ? 0 : top_str;
 
   /* Temporary modify MCTX.  */
   backup_state_log = mctx->state_log;

fixed as follows;

  str_idx = path->next_idx ? path->next_idx : top_str;

[masatake]

Thank you for taking your time for comparing the changes. What you are doing is important even if we introduce pcre2.

I think we should take a copy from gnulib, not from glibc.

https://git.savannah.gnu.org/cgit/gnulib.git/tree/lib/regex.h
https://git.savannah.gnu.org/cgit/gnulib.git/tree/lib
https://www.gnu.org/software/gnulib/
https://www.gnu.org/software/gnulib/manual/html_node/index.html

As far as reading the regex.h at gnulib repo, the license is not changed.

[k-takata]

This might be off-topic, but

/* alloca is implemented with malloc, so just use malloc.  */

alloca allocates memory from the stack and it will be automatically freed when a function returns.
Just replacing alloca with malloc causes memory leaks.

[hirooih]

@masatake -san,
I've been thinking gnulib is another name for glibc. I've just start reading the document of gnulib.

@k-tanaka san,
The implementation of regex in gnulib never use alloca().

Very interesting!
Thank you for your info.

[k-takata]

(You are mentioning the wrong person.)

[hirooih]

What you are doing is important even if we introduce pcre2.

I think we should take a copy from gnulib, not from glibc.

I had to learn about not only gnulib but also GNU Autotools to use gnulib,
Now I am ready to send a PR merging the latest regex engine from gnulib to ctags.

There are some concerns. I'd like to know if they are acceptable or not, before making a PR.

• The current Gnulib requires GNU Autoconf 2.64 (released in 2009). The current ctags requires 2.59 (released in 2003).
• The current gnu_regex directory has only 6 *.c and *.h files. If we import regex module from Gnulib, it also copy dependent files, total 73, and 52 M4 macro files.
  • See https://www.gnu.org/software/gnulib/MODULES.html#module=regex for details (dependent files, etc.). They may improve portability of ctags.
  • The directory name gnu_regex/ is not proper any more. I create a directory gnulib instead.

If these are acceptable. I will send a PR.