libdm/regex/matcher.c

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