libdm/regex/matcher.c

   1 /*
   2  * Copyright (C) 2001-2004 Sistina Software, Inc. All rights reserved.
   3  * Copyright (C) 2004-2012 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  14  */
  15
  16 #include "libdm/misc/dmlib.h"
  17 #include "parse_rx.h"
  18 #include "ttree.h"
  19 #include "assert.h"
  20
  21 struct dfa_state {
  22         struct dfa_state *next;
  23         int final;
  24         dm_bitset_t bits;
  25         struct dfa_state *lookup[256];
  26 };
  27
  28 struct dm_regex {               /* Instance variables for the lexer */
  29         struct dfa_state *start;
  30         unsigned num_nodes;
  31         unsigned num_charsets;
  32         int nodes_entered;
  33         struct rx_node **nodes;
  34         int charsets_entered;
  35         struct rx_node **charsets;
  36         struct dm_pool *scratch, *mem;
  37
  38         /* stuff for on the fly dfa calculation */
  39         dm_bitset_t charmap[256];
  40         dm_bitset_t dfa_copy;
  41         struct ttree *tt;
  42         dm_bitset_t bs;
  43         struct dfa_state *h, *t;
  44 };
  45
  46 static int _count_nodes(struct rx_node *rx)
  47 {
  48         int r = 1;
  49
  50         if (rx->left)
  51                 r += _count_nodes(rx->left);
  52
  53         if (rx->right)
  54                 r += _count_nodes(rx->right);
  55
  56         return r;
  57 }
  58
  59 static unsigned _count_charsets(struct rx_node *rx)
  60 {
  61         if (rx->type == CHARSET)
  62                 return 1;
  63
  64         return (rx->left ? _count_charsets(rx->left) : 0) +
  65                 (rx->right ? _count_charsets(rx->right) : 0);
  66 }
  67
  68 static void _enumerate_charsets_internal(struct rx_node *rx, unsigned *i)
  69 {
  70         if (rx->type == CHARSET)
  71                 rx->charset_index = (*i)++;
  72         else {
  73                 if (rx->left)
  74                         _enumerate_charsets_internal(rx->left, i);
  75                 if (rx->right)
  76                         _enumerate_charsets_internal(rx->right, i);
  77         }
  78 }
  79
  80 static void _enumerate_charsets(struct rx_node *rx)
  81 {
  82         unsigned i = 0;
  83         _enumerate_charsets_internal(rx, &i);
  84 }
  85
  86 static void _fill_table(struct dm_regex *m, struct rx_node *rx)
  87 {
  88         assert((rx->type != OR) || (rx->left && rx->right));
  89
  90         if (rx->left)
  91                 _fill_table(m, rx->left);
  92
  93         if (rx->right)
  94                 _fill_table(m, rx->right);
  95
  96         m->nodes[m->nodes_entered++] = rx;
  97         if (rx->type == CHARSET)
  98                 m->charsets[m->charsets_entered++] = rx;
  99 }
 100
 101 static int _create_bitsets(struct dm_regex *m)
 102 {
 103         unsigned i;
 104         struct rx_node *n;
 105
 106         for (i = 0; i < m->num_nodes; i++) {
 107                 n = m->nodes[i];
 108                 if (!(n->firstpos = dm_bitset_create(m->scratch, m->num_charsets)))
 109                         return_0;
 110                 if (!(n->lastpos = dm_bitset_create(m->scratch, m->num_charsets)))
 111                         return_0;
 112                 if (!(n->followpos = dm_bitset_create(m->scratch, m->num_charsets)))
 113                         return_0;
 114         }
 115
 116         return 1;
 117 }
 118
 119 static void _calc_functions(struct dm_regex *m)
 120 {
 121         unsigned i, j, final = 1;
 122         struct rx_node *rx, *c1, *c2;
 123
 124         for (i = 0; i < m->num_nodes; i++) {
 125                 rx = m->nodes[i];
 126                 c1 = rx->left;
 127                 c2 = rx->right;
 128
 129                 if (rx->type == CHARSET && dm_bit(rx->charset, TARGET_TRANS))
 130                         rx->final = final++;
 131
 132                 switch (rx->type) {
 133                 case CAT:
 134                         if (c1->nullable)
 135                                 dm_bit_union(rx->firstpos,
 136                                           c1->firstpos, c2->firstpos);
 137                         else
 138                                 dm_bit_copy(rx->firstpos, c1->firstpos);
 139
 140                         if (c2->nullable)
 141                                 dm_bit_union(rx->lastpos,
 142                                           c1->lastpos, c2->lastpos);
 143                         else
 144                                 dm_bit_copy(rx->lastpos, c2->lastpos);
 145
 146                         rx->nullable = c1->nullable && c2->nullable;
 147                         break;
 148
 149                 case PLUS:
 150                         dm_bit_copy(rx->firstpos, c1->firstpos);
 151                         dm_bit_copy(rx->lastpos, c1->lastpos);
 152                         rx->nullable = c1->nullable;
 153                         break;
 154
 155                 case OR:
 156                         dm_bit_union(rx->firstpos, c1->firstpos, c2->firstpos);
 157                         dm_bit_union(rx->lastpos, c1->lastpos, c2->lastpos);
 158                         rx->nullable = c1->nullable || c2->nullable;
 159                         break;
 160
 161                 case QUEST:
 162                 case STAR:
 163                         dm_bit_copy(rx->firstpos, c1->firstpos);
 164                         dm_bit_copy(rx->lastpos, c1->lastpos);
 165                         rx->nullable = 1;
 166                         break;
 167
 168                 case CHARSET:
 169                         dm_bit_set(rx->firstpos, rx->charset_index);
 170                         dm_bit_set(rx->lastpos, rx->charset_index);
 171                         rx->nullable = 0;
 172                         break;
 173
 174                 default:
 175                         log_error(INTERNAL_ERROR "Unknown calc node type");
 176                 }
 177
 178                 /*
 179                  * followpos has it's own switch
 180                  * because PLUS and STAR do the
 181                  * same thing.
 182                  */
 183                 switch (rx->type) {
 184                 case CAT:
 185                         for (j = 0; j < m->num_charsets; j++) {
 186                                 struct rx_node *n = m->charsets[j];
 187                                 if (dm_bit(c1->lastpos, j))
 188                                         dm_bit_union(n->followpos,
 189                                                      n->followpos, c2->firstpos);
 190                         }
 191                         break;
 192
 193                 case PLUS:
 194                 case STAR:
 195                         for (j = 0; j < m->num_charsets; j++) {
 196                                 struct rx_node *n = m->charsets[j];
 197                                 if (dm_bit(rx->lastpos, j))
 198                                         dm_bit_union(n->followpos,
 199                                                      n->followpos, rx->firstpos);
 200                         }
 201                         break;
 202                 }
 203         }
 204 }
 205
 206 static struct dfa_state *_create_dfa_state(struct dm_pool *mem)
 207 {
 208         return dm_pool_zalloc(mem, sizeof(struct dfa_state));
 209 }
 210
 211 static struct dfa_state *_create_state_queue(struct dm_pool *mem,
 212                                              struct dfa_state *dfa,
 213                                              dm_bitset_t bits)
 214 {
 215         if (!(dfa->bits = dm_bitset_create(mem, bits[0])))  /* first element is the size */
 216                 return_NULL;
 217
 218         dm_bit_copy(dfa->bits, bits);
 219         dfa->next = 0;
 220         dfa->final = -1;
 221
 222         return dfa;
 223 }
 224
 225 static int _calc_state(struct dm_regex *m, struct dfa_state *dfa, int a)
 226 {
 227         int set_bits = 0, i;
 228         dm_bitset_t dfa_bits = dfa->bits;
 229         dm_bit_and(m->dfa_copy, m->charmap[a], dfa_bits);
 230
 231         /* iterate through all the states in firstpos */
 232         for (i = dm_bit_get_first(m->dfa_copy); i >= 0; i = dm_bit_get_next(m->dfa_copy, i)) {
 233                 if (a == TARGET_TRANS)
 234                         dfa->final = m->charsets[i]->final;
 235
 236                 dm_bit_union(m->bs, m->bs, m->charsets[i]->followpos);
 237                 set_bits = 1;
 238         }
 239
 240         if (set_bits) {
 241                 struct dfa_state *tmp;
 242                 struct dfa_state *ldfa = ttree_lookup(m->tt, m->bs + 1);
 243                 if (!ldfa) {
 244                         /* push */
 245                         if (!(ldfa = _create_dfa_state(m->mem)))
 246                                 return_0;
 247
 248                         ttree_insert(m->tt, m->bs + 1, ldfa);
 249                         if (!(tmp = _create_state_queue(m->scratch, ldfa, m->bs)))
 250                                 return_0;
 251                         if (!m->h)
 252                                 m->h = m->t = tmp;
 253                         else {
 254                                 m->t->next = tmp;
 255                                 m->t = tmp;
 256                         }
 257                 }
 258
 259                 dfa->lookup[a] = ldfa;
 260                 dm_bit_clear_all(m->bs);
 261         }
 262
 263         return 1;
 264 }
 265
 266 static int _calc_states(struct dm_regex *m, struct rx_node *rx)
 267 {
 268         unsigned iwidth = (m->num_charsets / DM_BITS_PER_INT) + 1;
 269         struct dfa_state *dfa;
 270         struct rx_node *n;
 271         unsigned i;
 272         int a;
 273
 274         if (!(m->tt = ttree_create(m->scratch, iwidth)))
 275                 return_0;
 276
 277         if (!(m->bs = dm_bitset_create(m->scratch, m->num_charsets)))
 278                 return_0;
 279
 280         /* build some char maps */
 281         for (a = 0; a < 256; a++)
 282                 if (!(m->charmap[a] = dm_bitset_create(m->scratch, m->num_charsets)))
 283                         return_0;
 284
 285         for (i = 0; i < m->num_nodes; i++) {
 286                 n = m->nodes[i];
 287                         if (n->type == CHARSET) {
 288                         for (a = dm_bit_get_first(n->charset);
 289                              a >= 0; a = dm_bit_get_next(n->charset, a))
 290                                 dm_bit_set(m->charmap[a], n->charset_index);
 291                 }
 292         }
 293
 294         /* create first state */
 295         if (!(dfa = _create_dfa_state(m->mem)))
 296                 return_0;
 297
 298         m->start = dfa;
 299         ttree_insert(m->tt, rx->firstpos + 1, dfa);
 300
 301         /* prime the queue */
 302         if (!(m->h = m->t = _create_state_queue(m->scratch, dfa, rx->firstpos)))
 303                 return_0;
 304
 305         if (!(m->dfa_copy = dm_bitset_create(m->scratch, m->num_charsets)))
 306                 return_0;
 307
 308         return 1;
 309 }
 310
 311 /*
 312  * Forces all the dfa states to be calculated up front, ie. what
 313  * _calc_states() used to do before we switched to calculating on demand.
 314  */
 315 static int _force_states(struct dm_regex *m)
 316 {
 317         int a;
 318
 319         /* keep processing until there's nothing in the queue */
 320         struct dfa_state *s;
 321         while ((s = m->h)) {
 322                 /* pop state off front of the queue */
 323                 m->h = m->h->next;
 324
 325                 /* iterate through all the inputs for this state */
 326                 dm_bit_clear_all(m->bs);
 327                 for (a = 0; a < 256; a++)
 328                         if (!_calc_state(m, s, a))
 329                                 return_0;
 330         }
 331
 332         return 1;
 333 }
 334
 335 struct dm_regex *dm_regex_create(struct dm_pool *mem, const char * const *patterns,
 336                                  unsigned num_patterns)
 337 {
 338         char *all, *ptr;
 339         unsigned i;
 340         size_t len = 0;
 341         struct rx_node *rx;
 342         struct dm_regex *m;
 343         struct dm_pool *scratch = mem;
 344
 345         if (!(m = dm_pool_zalloc(mem, sizeof(*m))))
 346                 return_NULL;
 347
 348         /* join the regexps together, delimiting with zero */
 349         for (i = 0; i < num_patterns; i++)
 350                 len += strlen(patterns[i]) + 8;
 351
 352         ptr = all = dm_pool_alloc(scratch, len + 1);
 353
 354         if (!all)
 355                 goto_bad;
 356
 357         for (i = 0; i < num_patterns; i++) {
 358                 ptr += sprintf(ptr, "(.*(%s)%c)", patterns[i], TARGET_TRANS);
 359                 if (i < (num_patterns - 1))
 360                         *ptr++ = '|';
 361         }
 362
 363         /* parse this expression */
 364         if (!(rx = rx_parse_tok(scratch, all, ptr))) {
 365                 log_error("Couldn't parse regex");
 366                 goto bad;
 367         }
 368
 369         m->mem = mem;
 370         m->scratch = scratch;
 371         m->num_nodes = _count_nodes(rx);
 372         m->num_charsets = _count_charsets(rx);
 373         _enumerate_charsets(rx);
 374         if (!(m->nodes = dm_pool_alloc(scratch, sizeof(*m->nodes) * m->num_nodes)))
 375                 goto_bad;
 376
 377         if (!(m->charsets = dm_pool_alloc(scratch, sizeof(*m->charsets) * m->num_charsets)))
 378                 goto_bad;
 379
 380         _fill_table(m, rx);
 381
 382         if (!_create_bitsets(m))
 383                 goto_bad;
 384
 385         _calc_functions(m);
 386
 387         if (!_calc_states(m, rx))
 388                 goto_bad;
 389
 390         return m;
 391
 392       bad:
 393         dm_pool_free(mem, m);
 394
 395         return NULL;
 396 }
 397
 398 static struct dfa_state *_step_matcher(struct dm_regex *m, int c, struct dfa_state *cs, int *r)
 399 {
 400         struct dfa_state *ns;
 401
 402         if (!(ns = cs->lookup[(unsigned char) c])) {
 403                 if (!_calc_state(m, cs, (unsigned char) c))
 404                         return_NULL;
 405
 406                 if (!(ns = cs->lookup[(unsigned char) c]))
 407                         return NULL;
 408         }
 409
 410         // yuck, we have to special case the target trans
 411         if ((ns->final == -1) &&
 412             !_calc_state(m, ns, TARGET_TRANS))
 413                 return_NULL;
 414
 415         if (ns->final && (ns->final > *r))
 416                 *r = ns->final;
 417
 418         return ns;
 419 }
 420
 421 int dm_regex_match(struct dm_regex *regex, const char *s)
 422 {
 423         struct dfa_state *cs = regex->start;
 424         int r = 0;
 425
 426         dm_bit_clear_all(regex->bs);
 427         if (!(cs = _step_matcher(regex, HAT_CHAR, cs, &r)))
 428                 goto out;
 429
 430         for (; *s; s++)
 431                 if (!(cs = _step_matcher(regex, *s, cs, &r)))
 432                         goto out;
 433
 434         _step_matcher(regex, DOLLAR_CHAR, cs, &r);
 435
 436       out:
 437         /* subtract 1 to get back to zero index */
 438         return r - 1;
 439 }
 440
 441 /*
 442  * The next block of code concerns calculating a fingerprint for the dfa.
 443  *
 444  * We're not calculating a minimal dfa in _calculate_state (maybe a future
 445  * improvement).  As such it's possible that two non-isomorphic dfas
 446  * recognise the same language.  This can only really happen if you start
 447  * with equivalent, but different regexes (for example the simplifier in
 448  * parse_rx.c may have changed).
 449  *
 450  * The code is inefficient; repeatedly searching a singly linked list for
 451  * previously seen nodes.  Not worried since this is test code.
 452  */
 453 struct node_list {
 454         unsigned node_id;
 455         struct dfa_state *node;
 456         struct node_list *next;
 457 };
 458
 459 struct printer {
 460         struct dm_pool *mem;
 461         struct node_list *pending;
 462         struct node_list *processed;
 463         unsigned next_index;
 464 };
 465
 466 static uint32_t _randomise(uint32_t n)
 467 {
 468         /* 2^32 - 5 */
 469         uint32_t const prime = (~0) - 4;
 470         return n * prime;
 471 }
 472
 473 static int _seen(struct node_list *n, struct dfa_state *node, uint32_t *i)
 474 {
 475         while (n) {
 476                 if (n->node == node) {
 477                         *i = n->node_id;
 478                         return 1;
 479                 }
 480                 n = n->next;
 481         }
 482
 483         return 0;
 484 }
 485
 486 /*
 487  * Push node if it's not been seen before, returning a unique index.
 488  */
 489 static uint32_t _push_node(struct printer *p, struct dfa_state *node)
 490 {
 491         uint32_t i;
 492         struct node_list *n;
 493
 494         if (_seen(p->pending, node, &i) ||
 495             _seen(p->processed, node, &i))
 496                 return i;
 497
 498         if (!(n = dm_pool_alloc(p->mem, sizeof(*n))))
 499                 return_0;
 500
 501         n->node_id = ++p->next_index; /* start from 1, keep 0 as error code */
 502         n->node = node;
 503         n->next = p->pending;
 504         p->pending = n;
 505
 506         return n->node_id;
 507 }
 508
 509 /*
 510  * Pop the front node, and fill out it's previously assigned index.
 511  */
 512 static struct dfa_state *_pop_node(struct printer *p)
 513 {
 514         struct dfa_state *node = NULL;
 515         struct node_list *n;
 516
 517         if (p->pending) {
 518                 n = p->pending;
 519                 p->pending = n->next;
 520                 n->next = p->processed;
 521                 p->processed = n;
 522
 523                 node = n->node;
 524         }
 525
 526         return node;
 527 }
 528
 529 static uint32_t _combine(uint32_t n1, uint32_t n2)
 530 {
 531         return ((n1 << 8) | (n1 >> 24)) ^ _randomise(n2);
 532 }
 533
 534 static uint32_t _fingerprint(struct printer *p)
 535 {
 536         int c;
 537         uint32_t result = 0;
 538         struct dfa_state *node;
 539
 540         while ((node = _pop_node(p))) {
 541                 result = _combine(result, (node->final < 0) ? 0 : node->final);
 542                 for (c = 0; c < 256; c++)
 543                         result = _combine(result,
 544                                           _push_node(p, node->lookup[c]));
 545         }
 546
 547         return result;
 548 }
 549
 550 uint32_t dm_regex_fingerprint(struct dm_regex *regex)
 551 {
 552         struct printer p;
 553         uint32_t result = 0;
 554         struct dm_pool *mem = dm_pool_create("regex fingerprint", 1024);
 555
 556         if (!mem)
 557                 return_0;
 558
 559         if (!_force_states(regex))
 560                 goto_out;
 561
 562         p.mem = mem;
 563         p.pending = NULL;
 564         p.processed = NULL;
 565         p.next_index = 0;
 566
 567         if (!_push_node(&p, regex->start))
 568                 goto_out;
 569
 570         result = _fingerprint(&p);
 571 out:
 572         dm_pool_destroy(mem);
 573
 574         return result;
 575 }