Is it possible to get all occurrences of \< in a string using regexec?

[Florian Weimer]

* Arkadiusz Drabczyk:

> On Mon, Feb 10, 2025 at 09:20:58AM +0100, Florian Weimer wrote:
>> * Arkadiusz Drabczyk:
>> 
>> > \< GNU extension matches the beginning of a word, for example when
>> > used with GNU sed:
>> >
>> > $ echo abc def xyz | sed 's,\<,*,g'
>> > *abc *def *xyz
>> >
>> > The problem is when that \< is used with regexec() on all substrings
>> > of a string incremented by 1 from the beginning until the end matches
>> > with rm_so and rm_eo set to 0 are always returned so effectively all
>> > characters in a word match. The behavior can be demonstrated with
>> > busybox sed that uses regexec() that way:
>> >
>> > $ echo abc def xyz | busybox sed 's,\<,*,g'
>> > *a*b*c *d*e*f *x*y*z
>> >
>> > The GNU sed example works because it uses gnulib regex. The difference
>> > is that gnulib implementation can operate on the same string and
>> > return the matches from the given offset but regexc() takes a new
>> > string and returns all matches form its beginning.
>> >
>> > Is it possible to use regexc() in a way that would make it possible to
>> > correctly match all occurrences of \< in a string?
>> 
>> Have you tried calling egexec with REG_NOTBOL?  It is documented as:
>> 
>> ‘REG_NOTBOL’
>> 
>>      Do not regard the beginning of the specified string as the
>>      beginning of a line; more generally, don't make any assumptions
>>      about what text might precede it.
>> 
>> Maybe it helps your use case as well?
>> 
>> Probably even better is REG_STARTEND (only documented in the manual
>> pages).  This avoids one source of quadratic run-time behavior.
>> 
>> Thanks,
>> Florian
>
> Thanks for the suggestion but it didn't help. Maybe it would be easier
> to explain what I want to achieve with the code example. I have:
>
> #include <stdio.h>
> #include <stdlib.h>
> #include <string.h>
> #include <regex.h>
>
> void find_matches(const char *pattern, const char *text) {
>   regex_t regex;
>   regmatch_t match[1];
>   size_t offset = 0;
>   size_t len = strlen(text);
>   int ret;
>
>   ret = regcomp(&regex, pattern, REG_EXTENDED | REG_NOTBOL);
>   if (ret) {
>     fprintf(stderr, "regcomp %d\n", ret);
>     return;
>   }
>
>   while (offset < len) {
>     ret = regexec(&regex, text + offset, 1, match, 0);
>
>     if (ret == REG_NOMATCH) {
>       break;
>     }
>
>     printf("match[0].rm_so == %d\n", match[0].rm_so);
>     printf("match[0].rm_eo == %d\n", match[0].rm_eo);
>
>     int start = offset + match[0].rm_so;
>     int end = offset + match[0].rm_eo;
>
>     printf("Match found at: %d to %d\n", start, end);
>
>     offset = start + 1;
>   }
>
>   regfree(&regex);
> }
>
> int main(void) {
>   const char *pattern = "\\<";
>   const char *text = "abc def xyz";
>
>   find_matches(pattern, text);
> }
>
> Output is:
>
> match[0].rm_so == 0
> match[0].rm_eo == 0
> Match found at: 0 to 0
> match[0].rm_so == 0
> match[0].rm_eo == 0
> Match found at: 1 to 1
> match[0].rm_so == 0
> match[0].rm_eo == 0
> Match found at: 2 to 2
> match[0].rm_so == 1
> match[0].rm_eo == 1
> Match found at: 4 to 4
> match[0].rm_so == 0
> match[0].rm_eo == 0
> Match found at: 5 to 5
> match[0].rm_so == 0
> match[0].rm_eo == 0
> Match found at: 6 to 6
> match[0].rm_so == 1
> match[0].rm_eo == 1
> Match found at: 8 to 8
> match[0].rm_so == 0
> match[0].rm_eo == 0
> Match found at: 9 to 9
> match[0].rm_so == 0
> match[0].rm_eo == 0
> Match found at: 10 to 10
>
> While using gnulib:
>
> #include <stdio.h>
> #include <stdlib.h>
> #include <string.h>
> #define __USE_GNU
> #include <regex.h>
> #include <sys/types.h>
>
> void find_matches(const char *pattern, const char *text) {
>   regex_t regex;
>   struct re_registers regs;
>   char fastmap[256];
>   int offset = 0;
>   size_t len = strlen(text);
>   int match_pos;
>
>   memset(&regex, 0, sizeof(regex));
>
>   regex.fastmap = fastmap;
>   regex.fastmap_accurate = 0;
>   regex.translate = NULL;
>   regex.buffer = NULL;
>   regex.allocated = 0;
>   regcomp(&regex, pattern, REG_EXTENDED);
>
>   memset(&regs, 0, sizeof(regs));
>
>   while (offset < len) {
>     match_pos = re_search(&regex, text, len, offset, len - offset, &regs);
>
>     if (match_pos < 0) {
>       break;
>     }
>
>     int start = match_pos;
>     int end = match_pos + (regs.end[0] - regs.start[0]);
>
>     printf("Match found at: %d to %d\n", match_pos, end);
>
>     offset = match_pos + 1;
>   }
>
>   free(regs.start);
>   free(regs.end);
>   regfree(&regex);
> }
>
> int main(void) {
>   const char *pattern = "\\<";
>   const char *text = "abc def xyz";
>
>   find_matches(pattern, text);
> }
>
> Output is:
>
> Match found at: 0 to 0
> Match found at: 4 to 4
> Match found at: 8 to 8

REG_STARTEND appears to work.  REG_NOTBOL does not seem to work.

This:

  size_t eo = strlen(text);
  while (offset < len) {
    match[0].rm_so = offset;
    match[0].rm_eo = eo;
    ret = regexec(&regex, text, 1, match, REG_STARTEND);

    if (ret == REG_NOMATCH) {
      break;
    }

    printf("match[0].rm_so == %d\n", match[0].rm_so);
    printf("match[0].rm_eo == %d\n", match[0].rm_eo);

    int start = match[0].rm_so;
    int end = match[0].rm_eo;

    printf("Match found at: %d to %d\n", start, end);

    offset = start + 1;
  }

Gives me with glibc:

match[0].rm_so == 0
match[0].rm_eo == 0
Match found at: 0 to 0
match[0].rm_so == 4
match[0].rm_eo == 4
Match found at: 4 to 4
match[0].rm_so == 8
match[0].rm_eo == 8
Match found at: 8 to 8

Is this what you had in mind?  We should perhaps add it as an example to
the manual.

Thanks,
Florian