LCOV - code coverage report
Current view: top level - misc/kabi/lvm2.git/libdm/regex - parse_rx.c (source / functions) Hit Total Coverage
Test: unnamed Lines: 107 179 59.8 %
Date: 2010-04-13 Functions: 7 9 77.8 %
Branches: 49 104 47.1 %

           Branch data     Line data    Source code
       1                 :            : /*
       2                 :            :  * Copyright (C) 2001-2004 Sistina Software, Inc. All rights reserved.  
       3                 :            :  * Copyright (C) 2004-2007 Red Hat, Inc. All rights reserved.
       4                 :            :  *
       5                 :            :  * This file is part of the device-mapper userspace tools.
       6                 :            :  *
       7                 :            :  * This copyrighted material is made available to anyone wishing to use,
       8                 :            :  * modify, copy, or redistribute it subject to the terms and conditions
       9                 :            :  * of the GNU Lesser General Public License v.2.1.
      10                 :            :  *
      11                 :            :  * You should have received a copy of the GNU Lesser General Public License
      12                 :            :  * along with this program; if not, write to the Free Software Foundation,
      13                 :            :  * Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
      14                 :            :  */
      15                 :            : 
      16                 :            : #include "dmlib.h"
      17                 :            : #include "parse_rx.h"
      18                 :            : 
      19                 :            : struct parse_sp {               /* scratch pad for the parsing process */
      20                 :            :         struct dm_pool *mem;
      21                 :            :         int type;               /* token type, 0 indicates a charset */
      22                 :            :         dm_bitset_t charset;    /* The current charset */
      23                 :            :         const char *cursor;     /* where we are in the regex */
      24                 :            :         const char *rx_end;     /* 1pte for the expression being parsed */
      25                 :            : };
      26                 :            : 
      27                 :            : static struct rx_node *_or_term(struct parse_sp *ps);
      28                 :            : 
      29                 :          0 : static void _single_char(struct parse_sp *ps, unsigned int c, const char *ptr)
      30                 :            : {
      31                 :          0 :         ps->type = 0;
      32                 :          0 :         ps->cursor = ptr + 1;
      33                 :          0 :         dm_bit_clear_all(ps->charset);
      34                 :          0 :         dm_bit_set(ps->charset, c);
      35                 :          0 : }
      36                 :            : 
      37                 :            : /*
      38                 :            :  * Get the next token from the regular expression.
      39                 :            :  * Returns: 1 success, 0 end of input, -1 error.
      40                 :            :  */
      41                 :       5560 : static int _rx_get_token(struct parse_sp *ps)
      42                 :            : {
      43                 :       5560 :         int neg = 0, range = 0;
      44                 :       5560 :         char c, lc = 0;
      45                 :       5560 :         const char *ptr = ps->cursor;
      46         [ +  + ]:       5560 :         if (ptr == ps->rx_end) {     /* end of input ? */
      47                 :          3 :                 ps->type = -1;
      48                 :          3 :                 return 0;
      49                 :            :         }
      50                 :            : 
      51 [ +  +  -  -  + :       5557 :         switch (*ptr) {
                   -  + ]
      52                 :            :                 /* charsets and ncharsets */
      53                 :            :         case '[':
      54                 :          4 :                 ptr++;
      55         [ -  + ]:          4 :                 if (*ptr == '^') {
      56                 :          0 :                         dm_bit_set_all(ps->charset);
      57                 :            : 
      58                 :            :                         /* never transition on zero */
      59                 :          0 :                         dm_bit_clear(ps->charset, 0);
      60                 :          0 :                         neg = 1;
      61                 :          0 :                         ptr++;
      62                 :            : 
      63                 :            :                 } else
      64                 :          4 :                         dm_bit_clear_all(ps->charset);
      65                 :            : 
      66 [ +  - ][ +  + ]:         12 :                 while ((ptr < ps->rx_end) && (*ptr != ']')) {
      67         [ -  + ]:          8 :                         if (*ptr == '\\') {
      68                 :            :                                 /* an escaped character */
      69                 :          0 :                                 ptr++;
      70   [ #  #  #  # ]:          0 :                                 switch (*ptr) {
      71                 :            :                                 case 'n':
      72                 :          0 :                                         c = '\n';
      73                 :          0 :                                         break;
      74                 :            :                                 case 'r':
      75                 :          0 :                                         c = '\r';
      76                 :          0 :                                         break;
      77                 :            :                                 case 't':
      78                 :          0 :                                         c = '\t';
      79                 :          0 :                                         break;
      80                 :            :                                 default:
      81                 :          0 :                                         c = *ptr;
      82                 :            :                                 }
      83 [ +  + ][ +  - ]:         10 :                         } else if (*ptr == '-' && lc) {
      84                 :            :                                 /* we've got a range on our hands */
      85                 :          2 :                                 range = 1;
      86                 :          2 :                                 ptr++;
      87         [ -  + ]:          2 :                                 if (ptr == ps->rx_end) {
      88         [ #  # ]:          0 :                                         log_error("Incomplete range"
      89                 :            :                                                   "specification");
      90                 :          0 :                                         return -1;
      91                 :            :                                 }
      92                 :          2 :                                 c = *ptr;
      93                 :            :                         } else
      94                 :          6 :                                 c = *ptr;
      95                 :            : 
      96         [ +  + ]:          8 :                         if (range) {
      97                 :            :                                 /* add lc - c into the bitset */
      98         [ -  + ]:          2 :                                 if (lc > c) {
      99                 :          0 :                                         char tmp = c;
     100                 :          0 :                                         c = lc;
     101                 :          0 :                                         lc = tmp;
     102                 :            :                                 }
     103                 :            : 
     104         [ +  + ]:         12 :                                 for (; lc <= c; lc++) {
     105         [ -  + ]:         10 :                                         if (neg)
     106                 :          0 :                                                 dm_bit_clear(ps->charset, lc);
     107                 :            :                                         else
     108                 :         10 :                                                 dm_bit_set(ps->charset, lc);
     109                 :            :                                 }
     110                 :          2 :                                 range = 0;
     111                 :            :                         } else {
     112                 :            :                                 /* add c into the bitset */
     113         [ -  + ]:          6 :                                 if (neg)
     114                 :          0 :                                         dm_bit_clear(ps->charset, c);
     115                 :            :                                 else
     116                 :          6 :                                         dm_bit_set(ps->charset, c);
     117                 :            :                         }
     118                 :          8 :                         ptr++;
     119                 :          8 :                         lc = c;
     120                 :            :                 }
     121                 :            : 
     122         [ -  + ]:          4 :                 if (ptr >= ps->rx_end) {
     123                 :          0 :                         ps->type = -1;
     124                 :          0 :                         return -1;
     125                 :            :                 }
     126                 :            : 
     127                 :          4 :                 ps->type = 0;
     128                 :          4 :                 ps->cursor = ptr + 1;
     129                 :          4 :                 break;
     130                 :            : 
     131                 :            :                 /* These characters are special, we just return their ASCII
     132                 :            :                    codes as the type.  Sorted into ascending order to help the
     133                 :            :                    compiler */
     134                 :            :         case '(':
     135                 :            :         case ')':
     136                 :            :         case '*':
     137                 :            :         case '+':
     138                 :            :         case '?':
     139                 :            :         case '|':
     140                 :       1872 :                 ps->type = (int) *ptr;
     141                 :       1872 :                 ps->cursor = ptr + 1;
     142                 :       1872 :                 break;
     143                 :            : 
     144                 :            :         case '^':
     145                 :          0 :                 _single_char(ps, HAT_CHAR, ptr);
     146                 :          0 :                 break;
     147                 :            : 
     148                 :            :         case '$':
     149                 :          0 :                 _single_char(ps, DOLLAR_CHAR, ptr);
     150                 :          0 :                 break;
     151                 :            : 
     152                 :            :         case '.':
     153                 :            :                 /* The 'all but newline' character set */
     154                 :        315 :                 ps->type = 0;
     155                 :        315 :                 ps->cursor = ptr + 1;
     156                 :        315 :                 dm_bit_set_all(ps->charset);
     157                 :        315 :                 dm_bit_clear(ps->charset, (int) '\n');
     158                 :        315 :                 dm_bit_clear(ps->charset, (int) '\r');
     159                 :        315 :                 dm_bit_clear(ps->charset, 0);
     160                 :        315 :                 break;
     161                 :            : 
     162                 :            :         case '\\':
     163                 :            :                 /* escaped character */
     164                 :          0 :                 ptr++;
     165         [ #  # ]:          0 :                 if (ptr >= ps->rx_end) {
     166         [ #  # ]:          0 :                         log_error("Badly quoted character at end "
     167                 :            :                                   "of expression");
     168                 :          0 :                         ps->type = -1;
     169                 :          0 :                         return -1;
     170                 :            :                 }
     171                 :            : 
     172                 :          0 :                 ps->type = 0;
     173                 :          0 :                 ps->cursor = ptr + 1;
     174                 :          0 :                 dm_bit_clear_all(ps->charset);
     175   [ #  #  #  # ]:          0 :                 switch (*ptr) {
     176                 :            :                 case 'n':
     177                 :          0 :                         dm_bit_set(ps->charset, (int) '\n');
     178                 :          0 :                         break;
     179                 :            :                 case 'r':
     180                 :          0 :                         dm_bit_set(ps->charset, (int) '\r');
     181                 :          0 :                         break;
     182                 :            :                 case 't':
     183                 :          0 :                         dm_bit_set(ps->charset, (int) '\t');
     184                 :          0 :                         break;
     185                 :            :                 default:
     186                 :          0 :                         dm_bit_set(ps->charset, (int) *ptr);
     187                 :            :                 }
     188                 :          0 :                 break;
     189                 :            : 
     190                 :            :         default:
     191                 :            :                 /* add a single character to the bitset */
     192                 :       3366 :                 ps->type = 0;
     193                 :       3366 :                 ps->cursor = ptr + 1;
     194                 :       3366 :                 dm_bit_clear_all(ps->charset);
     195                 :       3366 :                 dm_bit_set(ps->charset, (int) *ptr);
     196                 :            :                 break;
     197                 :            :         }
     198                 :            : 
     199                 :       5560 :         return 1;
     200                 :            : }
     201                 :            : 
     202                 :       7682 : static struct rx_node *_node(struct dm_pool *mem, int type,
     203                 :            :                              struct rx_node *l, struct rx_node *r)
     204                 :            : {
     205                 :       7682 :         struct rx_node *n = dm_pool_zalloc(mem, sizeof(*n));
     206                 :            : 
     207         [ +  - ]:       7682 :         if (n) {
     208         [ -  + ]:       7682 :                 if (!(n->charset = dm_bitset_create(mem, 256))) {
     209                 :          0 :                         dm_pool_free(mem, n);
     210                 :          0 :                         return NULL;
     211                 :            :                 }
     212                 :            : 
     213                 :       7682 :                 n->type = type;
     214                 :       7682 :                 n->left = l;
     215                 :       7682 :                 n->right = r;
     216                 :            :         }
     217                 :            : 
     218                 :       7682 :         return n;
     219                 :            : }
     220                 :            : 
     221                 :       4936 : static struct rx_node *_term(struct parse_sp *ps)
     222                 :            : {
     223                 :            :         struct rx_node *n;
     224                 :            : 
     225      [ +  +  + ]:       4936 :         switch (ps->type) {
     226                 :            :         case 0:
     227         [ -  + ]:       3685 :                 if (!(n = _node(ps->mem, CHARSET, NULL, NULL))) {
     228         [ #  # ]:          0 :                         stack;
     229                 :          0 :                         return NULL;
     230                 :            :                 }
     231                 :            : 
     232                 :       3685 :                 dm_bit_copy(n->charset, ps->charset);
     233                 :       3685 :                 _rx_get_token(ps);      /* match charset */
     234                 :       3685 :                 break;
     235                 :            : 
     236                 :            :         case '(':
     237                 :        624 :                 _rx_get_token(ps);      /* match '(' */
     238                 :        624 :                 n = _or_term(ps);
     239         [ -  + ]:        624 :                 if (ps->type != ')') {
     240         [ #  # ]:          0 :                         log_error("missing ')' in regular expression");
     241                 :          0 :                         return 0;
     242                 :            :                 }
     243                 :        624 :                 _rx_get_token(ps);      /* match ')' */
     244                 :        624 :                 break;
     245                 :            : 
     246                 :            :         default:
     247                 :        627 :                 n = 0;
     248                 :            :         }
     249                 :            : 
     250                 :       4936 :         return n;
     251                 :            : }
     252                 :            : 
     253                 :       4936 : static struct rx_node *_closure_term(struct parse_sp *ps)
     254                 :            : {
     255                 :            :         struct rx_node *l, *n;
     256                 :            : 
     257         [ +  + ]:       4936 :         if (!(l = _term(ps)))
     258                 :        627 :                 return NULL;
     259                 :            : 
     260                 :            :         for (;;) {
     261   [ +  -  -  + ]:       4624 :                 switch (ps->type) {
     262                 :            :                 case '*':
     263                 :        315 :                         n = _node(ps->mem, STAR, l, NULL);
     264                 :        315 :                         break;
     265                 :            : 
     266                 :            :                 case '+':
     267                 :          0 :                         n = _node(ps->mem, PLUS, l, NULL);
     268                 :          0 :                         break;
     269                 :            : 
     270                 :            :                 case '?':
     271                 :          0 :                         n = _node(ps->mem, QUEST, l, NULL);
     272                 :          0 :                         break;
     273                 :            : 
     274                 :            :                 default:
     275                 :       4309 :                         return l;
     276                 :            :                 }
     277                 :            : 
     278         [ -  + ]:        315 :                 if (!n) {
     279         [ #  # ]:          0 :                         stack;
     280                 :          0 :                         return NULL;
     281                 :            :                 }
     282                 :            : 
     283                 :        315 :                 _rx_get_token(ps);
     284                 :        315 :                 l = n;
     285                 :       5251 :         }
     286                 :            : 
     287                 :            :         return n;
     288                 :            : }
     289                 :            : 
     290                 :       4936 : static struct rx_node *_cat_term(struct parse_sp *ps)
     291                 :            : {
     292                 :            :         struct rx_node *l, *r, *n;
     293                 :            : 
     294         [ +  + ]:       4936 :         if (!(l = _closure_term(ps)))
     295                 :        627 :                 return NULL;
     296                 :            : 
     297         [ +  + ]:       4309 :         if (ps->type == '|')
     298                 :        309 :                 return l;
     299                 :            : 
     300         [ +  + ]:       4000 :         if (!(r = _cat_term(ps)))
     301                 :        627 :                 return l;
     302                 :            : 
     303         [ -  + ]:       3373 :         if (!(n = _node(ps->mem, CAT, l, r)))
     304         [ #  # ]:          0 :                 stack;
     305                 :            : 
     306                 :       4936 :         return n;
     307                 :            : }
     308                 :            : 
     309                 :        936 : static struct rx_node *_or_term(struct parse_sp *ps)
     310                 :            : {
     311                 :            :         struct rx_node *l, *r, *n;
     312                 :            : 
     313         [ -  + ]:        936 :         if (!(l = _cat_term(ps)))
     314                 :          0 :                 return NULL;
     315                 :            : 
     316         [ +  + ]:        936 :         if (ps->type != '|')
     317                 :        627 :                 return l;
     318                 :            : 
     319                 :        309 :         _rx_get_token(ps);              /* match '|' */
     320                 :            : 
     321         [ -  + ]:        309 :         if (!(r = _or_term(ps))) {
     322         [ #  # ]:          0 :                 log_error("Badly formed 'or' expression");
     323                 :          0 :                 return NULL;
     324                 :            :         }
     325                 :            : 
     326         [ -  + ]:        309 :         if (!(n = _node(ps->mem, OR, l, r)))
     327         [ #  # ]:          0 :                 stack;
     328                 :            : 
     329                 :        936 :         return n;
     330                 :            : }
     331                 :            : 
     332                 :          3 : struct rx_node *rx_parse_tok(struct dm_pool *mem,
     333                 :            :                              const char *begin, const char *end)
     334                 :            : {
     335                 :            :         struct rx_node *r;
     336                 :          3 :         struct parse_sp *ps = dm_pool_zalloc(mem, sizeof(*ps));
     337                 :            : 
     338         [ -  + ]:          3 :         if (!ps) {
     339         [ #  # ]:          0 :                 stack;
     340                 :          0 :                 return NULL;
     341                 :            :         }
     342                 :            : 
     343                 :          3 :         ps->mem = mem;
     344                 :          3 :         ps->charset = dm_bitset_create(mem, 256);
     345                 :          3 :         ps->cursor = begin;
     346                 :          3 :         ps->rx_end = end;
     347                 :          3 :         _rx_get_token(ps);              /* load the first token */
     348                 :            : 
     349         [ -  + ]:          3 :         if (!(r = _or_term(ps))) {
     350         [ #  # ]:          0 :                 log_error("Parse error in regex");
     351                 :          0 :                 dm_pool_free(mem, ps);
     352                 :            :         }
     353                 :            : 
     354                 :          3 :         return r;
     355                 :            : }
     356                 :            : 
     357                 :          0 : struct rx_node *rx_parse_str(struct dm_pool *mem, const char *str)
     358                 :            : {
     359                 :          0 :         return rx_parse_tok(mem, str, str + strlen(str));
     360                 :            : }

Generated by: LCOV version 1.8