gettext-tools/libgrep/m-regex.c

   1 /* Pattern Matchers for Regular Expressions.
   2    Copyright (C) 1992, 1998, 2000, 2005-2006, 2010 Free Software Foundation, Inc.
   3
   4    This program is free software: you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation; either version 3 of the License, or
   7    (at your option) any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
  16
  17 #ifdef HAVE_CONFIG_H
  18 # include <config.h>
  19 #endif
  20
  21 /* Specification.  */
  22 #include "libgrep.h"
  23
  24 #include <ctype.h>
  25 #include <stdbool.h>
  26 #include <stdlib.h>
  27 #include <string.h>
  28 #include <regex.h>
  29
  30 #include "error.h"
  31 #include "exitfail.h"
  32 #include "xalloc.h"
  33
  34 #if defined (STDC_HEADERS) || (!defined (isascii) && !defined (HAVE_ISASCII))
  35 # define IN_CTYPE_DOMAIN(c) 1
  36 #else
  37 # define IN_CTYPE_DOMAIN(c) isascii(c)
  38 #endif
  39 #define ISALNUM(C) (IN_CTYPE_DOMAIN (C) && isalnum (C))
  40 #define IS_WORD_CONSTITUENT(C) (ISALNUM(C) || (C) == '_')
  41
  42 struct patterns
  43 {
  44   /* Regex compiled regexp. */
  45   struct re_pattern_buffer regexbuf;
  46   struct re_registers regs; /* This is here on account of a BRAIN-DEAD
  47                                Q@#%!# library interface in regex.c.  */
  48 };
  49
  50 struct compiled_regex {
  51   bool match_words;
  52   bool match_lines;
  53   char eolbyte;
  54
  55   /* The Regex compiled patterns.  */
  56   struct patterns *patterns;
  57   size_t pcount;
  58 };
  59
  60 static void *
  61 compile (const char *pattern, size_t pattern_size,
  62          bool match_icase, bool match_words, bool match_lines, char eolbyte,
  63          reg_syntax_t syntax)
  64 {
  65   struct compiled_regex *cregex;
  66
  67   cregex = XMALLOC (struct compiled_regex);
  68   memset (cregex, '\0', sizeof (struct compiled_regex));
  69   cregex->match_words = match_words;
  70   cregex->match_lines = match_lines;
  71   cregex->eolbyte = eolbyte;
  72   cregex->patterns = NULL;
  73   cregex->pcount = 0;
  74
  75   re_set_syntax (syntax);
  76
  77   /* For GNU regex compiler we have to pass the patterns separately to detect
  78      errors like "[\nallo\n]\n".  The patterns here are "[", "allo" and "]"
  79      GNU regex should have raised a syntax error.  The same for backref, where
  80      the backref should have been local to each pattern.  */
  81   {
  82     const char *sep;
  83     size_t total = pattern_size;
  84     const char *motif = pattern;
  85
  86     do
  87       {
  88         size_t len;
  89         const char *err;
  90
  91         sep = (const char *) memchr (motif, '\n', total);
  92         if (sep)
  93           {
  94             len = sep - motif;
  95             sep++;
  96             total -= (len + 1);
  97           }
  98         else
  99           {
 100             len = total;
 101             total = 0;
 102           }
 103
 104         cregex->patterns = xrealloc (cregex->patterns, (cregex->pcount + 1) * sizeof (struct patterns));
 105         memset (&cregex->patterns[cregex->pcount], '\0', sizeof (struct patterns));
 106
 107         if ((err = re_compile_pattern (motif, len,
 108                                        &cregex->patterns[cregex->pcount].regexbuf)) != NULL)
 109           error (exit_failure, 0, err);
 110         cregex->pcount++;
 111
 112         motif = sep;
 113       }
 114     while (sep && total != 0);
 115   }
 116
 117   return cregex;
 118 }
 119
 120 static void *
 121 Gcompile (const char *pattern, size_t pattern_size,
 122           bool match_icase, bool match_words, bool match_lines, char eolbyte)
 123 {
 124   return compile (pattern, pattern_size,
 125                   match_icase, match_words, match_lines, eolbyte,
 126                   RE_SYNTAX_GREP | RE_HAT_LISTS_NOT_NEWLINE);
 127 }
 128
 129 static void *
 130 Ecompile (const char *pattern, size_t pattern_size,
 131           bool match_icase, bool match_words, bool match_lines, char eolbyte)
 132 {
 133   return compile (pattern, pattern_size,
 134                   match_icase, match_words, match_lines, eolbyte,
 135                   RE_SYNTAX_POSIX_EGREP);
 136 }
 137
 138 static void *
 139 AWKcompile (const char *pattern, size_t pattern_size,
 140             bool match_icase, bool match_words, bool match_lines, char eolbyte)
 141 {
 142   return compile (pattern, pattern_size,
 143                   match_icase, match_words, match_lines, eolbyte,
 144                   RE_SYNTAX_AWK);
 145 }
 146
 147 static size_t
 148 EGexecute (const void *compiled_pattern,
 149            const char *buf, size_t buf_size,
 150            size_t *match_size, bool exact)
 151 {
 152   struct compiled_regex *cregex = (struct compiled_regex *) compiled_pattern;
 153   char eol = cregex->eolbyte;
 154   register const char *buflim = buf + buf_size;
 155   register const char *beg;
 156   register const char *end;
 157
 158   for (beg = buf; beg < buflim; beg = end)
 159     {
 160       size_t i;
 161
 162       end = (const char *) memchr (beg, eol, buflim - beg);
 163       if (end == NULL)
 164         end = buflim;
 165       /* Here, either end < buflim && *end == eol, or end == buflim.  */
 166
 167       for (i = 0; i < cregex->pcount; i++)
 168         {
 169           int start, len;
 170
 171           cregex->patterns[i].regexbuf.not_eol = 0;
 172           if (0 <= (start = re_search (&cregex->patterns[i].regexbuf, beg,
 173                                        end - beg, 0,
 174                                        end - beg, &cregex->patterns[i].regs)))
 175             {
 176               len = cregex->patterns[i].regs.end[0] - start;
 177               if (exact)
 178                 {
 179                   *match_size = len;
 180                   return start;
 181                 }
 182               if (cregex->match_lines)
 183                 {
 184                   if (len == end - beg) /* implies start == 0 */
 185                     goto success;
 186                 }
 187               else if (cregex->match_words)
 188                 {
 189                   /* If -w, check if the match aligns with word boundaries.
 190                      We do this iteratively because:
 191                      (a) the line may contain more than one occurence of the
 192                          pattern, and
 193                      (b) Several alternatives in the pattern might be valid at
 194                          a given point, and we may need to consider a shorter
 195                          one to find a word boundary.  */
 196                   while (start >= 0)
 197                     {
 198                       if ((start == 0 || !IS_WORD_CONSTITUENT ((unsigned char) beg[start - 1]))
 199                           && (start + len == end - beg
 200                               || !IS_WORD_CONSTITUENT ((unsigned char) beg[start + len])))
 201                         goto success;
 202                       if (len > 0)
 203                         {
 204                           /* Try a shorter length anchored at the same place. */
 205                           --len;
 206                           cregex->patterns[i].regexbuf.not_eol = 1;
 207                           len = re_match (&cregex->patterns[i].regexbuf, beg,
 208                                           start + len, start,
 209                                           &cregex->patterns[i].regs);
 210                         }
 211                       if (len <= 0)
 212                         {
 213                           /* Try looking further on. */
 214                           if (start == end - beg)
 215                             break;
 216                           ++start;
 217                           cregex->patterns[i].regexbuf.not_eol = 0;
 218                           start = re_search (&cregex->patterns[i].regexbuf, beg,
 219                                              end - beg,
 220                                              start, end - beg - start,
 221                                              &cregex->patterns[i].regs);
 222                           len = cregex->patterns[i].regs.end[0] - start;
 223                         }
 224                     }
 225                 }
 226               else
 227                 goto success;
 228             }
 229         }
 230
 231       if (end < buflim)
 232         end++;
 233     }
 234   return (size_t) -1;
 235
 236  success:
 237   *match_size = end - beg;
 238   return beg - buf;
 239 }
 240
 241 static void
 242 EGfree (void *compiled_pattern)
 243 {
 244   struct compiled_regex *cregex = (struct compiled_regex *) compiled_pattern;
 245
 246   free (cregex->patterns);
 247   free (cregex);
 248 }
 249
 250 /* POSIX Basic Regular Expressions */
 251 matcher_t matcher_grep =
 252   {
 253     Gcompile,
 254     EGexecute,
 255     EGfree
 256   };
 257
 258 /* POSIX Extended Regular Expressions */
 259 matcher_t matcher_egrep =
 260   {
 261     Ecompile,
 262     EGexecute,
 263     EGfree
 264   };
 265
 266 /* AWK Regular Expressions */
 267 matcher_t matcher_awk =
 268   {
 269     AWKcompile,
 270     EGexecute,
 271     EGfree
 272   };