← Back to branch summary

~vcs-imports/gawk/master

« back to all changes in this revision

Viewing changes to regex_internal.c

  • Committer: Arnold D. Robbins
  • Date: 2010-07-16 11:47:02 UTC
  • Revision ID: git-v1:315bd501ca696bc3e3c938b4604d8dac7a6f512f
Tags: gawk-3.1.5
Move to gawk 3.1.5.

Show diffs side-by-side

added added

removed removed

Lines of Context:
regex_internal.c
15
15
 
16
16
   You should have received a copy of the GNU Lesser General Public
17
17
   License along with the GNU C Library; if not, write to the Free
18
 
   Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
19
 
   02111-1307 USA.  */
 
18
   Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
 
19
   02110-1301 USA.  */
20
20
 
21
21
static void re_string_construct_common (const char *str, int len,
22
22
                                        re_string_t *pstr,
26
26
static int re_string_skip_chars (re_string_t *pstr, int new_raw_idx,
27
27
                                 wint_t *last_wc) internal_function;
28
28
#endif /* RE_ENABLE_I18N */
29
 
static re_dfastate_t *create_newstate_common (re_dfa_t *dfa,
30
 
                                              const re_node_set *nodes,
31
 
                                              unsigned int hash) internal_function;
32
29
static reg_errcode_t register_state (re_dfa_t *dfa, re_dfastate_t *newstate,
33
30
                                     unsigned int hash) internal_function;
34
31
static re_dfastate_t *create_ci_newstate (re_dfa_t *dfa,
242
239
          for (i = 0; i < pstr->mb_cur_max && i < remain_len; ++i)
243
240
            {
244
241
              ch = pstr->raw_mbs [pstr->raw_mbs_idx + byte_idx + i];
245
 
              buf[i] = pstr->trans[ch];
 
242
              buf[i] = pstr->mbs[byte_idx + i] = pstr->trans[ch];
246
243
            }
247
244
          p = (const char *) buf;
248
245
        }
293
290
  byte_idx = pstr->valid_len;
294
291
  end_idx = (pstr->bufs_len > pstr->len) ? pstr->len : pstr->bufs_len;
295
292
 
296
 
#ifdef _LIBC
297
 
  /* The following optimization assumes that the wchar_t encoding is
298
 
     always ISO 10646.  */
 
293
  /* The following optimization assumes that ASCII characters can be
 
294
     mapped to wide characters with a simple cast.  */
299
295
  if (! pstr->map_notascii && pstr->trans == NULL && !pstr->offsets_needed)
300
296
    {
301
297
      while (byte_idx < end_idx)
309
305
              pstr->mbs[byte_idx]
310
306
                = toupper (pstr->raw_mbs[pstr->raw_mbs_idx + byte_idx]);
311
307
              /* The next step uses the assumption that wchar_t is encoded
312
 
                 with ISO 10646: all ASCII values can be converted like
313
 
                 this.  */
 
308
                 ASCII-safe: all ASCII values can be converted like this.  */
314
309
              pstr->wcs[byte_idx] = (wchar_t) pstr->mbs[byte_idx];
315
310
              ++byte_idx;
316
311
              continue;
329
324
                  int mbcdlen;
330
325
 
331
326
                  wcu = towupper (wc);
332
 
                  mbcdlen = wcrtomb (buf, wcu, &prev_st);
 
327
                  mbcdlen = wcrtomb ((char *)buf, wcu, &prev_st);
333
328
                  if (BE (mbclen == mbcdlen, 1))
334
329
                    memcpy (pstr->mbs + byte_idx, buf, mbclen);
335
330
                  else
368
363
      return REG_NOERROR;
369
364
    }
370
365
  else
371
 
#endif
372
366
    for (src_idx = pstr->valid_raw_len; byte_idx < end_idx;)
373
367
      {
374
368
        wchar_t wc;
375
369
        const char *p;
376
 
#ifdef _LIBC
377
 
offsets_needed:
378
 
#endif
 
370
 
 
371
      offsets_needed:
379
372
        remain_len = end_idx - byte_idx;
380
373
        prev_st = pstr->cur_state;
381
374
        if (BE (pstr->trans != NULL, 0))
400
393
                int mbcdlen;
401
394
 
402
395
                wcu = towupper (wc);
403
 
                mbcdlen = wcrtomb ((char *)buf, wcu, &prev_st);
 
396
                mbcdlen = wcrtomb ((char *) buf, wcu, &prev_st);
404
397
                if (BE (mbclen == mbcdlen, 1))
405
398
                  memcpy (pstr->mbs + byte_idx, buf, mbclen);
406
399
                else
581
574
     int idx, eflags;
582
575
{
583
576
  int offset = idx - pstr->raw_mbs_idx;
584
 
  if (offset < 0)
 
577
  if (BE (offset < 0, 0))
585
578
    {
586
579
      /* Reset buffer.  */
587
580
#ifdef RE_ENABLE_I18N
601
594
      offset = idx;
602
595
    }
603
596
 
604
 
  if (offset != 0)
 
597
  if (BE (offset != 0, 1))
605
598
    {
606
599
      /* Are the characters which are already checked remain?  */
607
 
      if (offset < pstr->valid_raw_len
 
600
      if (BE (offset < pstr->valid_raw_len, 1)
608
601
#ifdef RE_ENABLE_I18N
609
602
          /* Handling this would enlarge the code too much.
610
603
             Accept a slowdown in that case.  */
619
612
            memmove (pstr->wcs, pstr->wcs + offset,
620
613
                     (pstr->valid_len - offset) * sizeof (wint_t));
621
614
#endif /* RE_ENABLE_I18N */
622
 
          if (pstr->mbs_allocated)
 
615
          if (BE (pstr->mbs_allocated, 0))
623
616
            memmove (pstr->mbs, pstr->mbs + offset,
624
617
                     pstr->valid_len - offset);
625
618
          pstr->valid_len -= offset;
647
640
              int wcs_idx;
648
641
              wint_t wc = WEOF;
649
642
 
650
 
#ifdef _LIBC
651
643
              if (pstr->is_utf8)
652
644
                {
653
645
                  const unsigned char *raw, *p, *q, *end;
687
679
                        break;
688
680
                      }
689
681
                }
690
 
#endif
 
682
 
691
683
              if (wc == WEOF)
692
684
                pstr->valid_len = re_string_skip_chars (pstr, idx, &wc) - idx;
693
685
              if (BE (pstr->valid_len, 0))
717
709
                                      ? CONTEXT_NEWLINE : 0));
718
710
            }
719
711
        }
720
 
      if (!pstr->mbs_allocated)
 
712
      if (!BE (pstr->mbs_allocated, 0))
721
713
        pstr->mbs += offset;
722
714
    }
723
715
  pstr->raw_mbs_idx = idx;
739
731
    }
740
732
  else
741
733
#endif /* RE_ENABLE_I18N */
 
734
  if (BE (pstr->mbs_allocated, 0))
742
735
    {
743
736
      if (pstr->icase)
744
737
        build_upper_buffer (pstr);
745
738
      else if (pstr->trans != NULL)
746
739
        re_string_translate_buffer (pstr);
747
 
      else
748
 
        pstr->valid_len = pstr->len;
749
740
    }
 
741
  else
 
742
    pstr->valid_len = pstr->len;
 
743
 
750
744
  pstr->cur_idx = 0;
751
 
 
752
745
  return REG_NOERROR;
753
746
}
754
747
 
846
839
     int idx, eflags;
847
840
{
848
841
  int c;
849
 
  if (idx < 0 || idx == input->len)
850
 
    {
851
 
      if (idx < 0)
852
 
        /* In this case, we use the value stored in input->tip_context,
853
 
           since we can't know the character in input->mbs[-1] here.  */
854
 
        return input->tip_context;
855
 
      else /* (idx == input->len) */
856
 
        return ((eflags & REG_NOTEOL) ? CONTEXT_ENDBUF
857
 
                : CONTEXT_NEWLINE | CONTEXT_ENDBUF);
858
 
    }
 
842
  if (BE (idx < 0, 0))
 
843
    /* In this case, we use the value stored in input->tip_context,
 
844
       since we can't know the character in input->mbs[-1] here.  */
 
845
    return input->tip_context;
 
846
  if (BE (idx == input->len, 0))
 
847
    return ((eflags & REG_NOTEOL) ? CONTEXT_ENDBUF
 
848
            : CONTEXT_NEWLINE | CONTEXT_ENDBUF);
859
849
#ifdef RE_ENABLE_I18N
860
850
  if (input->mb_cur_max > 1)
861
851
    {
894
884
     re_node_set *set;
895
885
     int size;
896
886
{
 
887
  /*
 
888
   * ADR: valgrind says size can be 0, which then doesn't
 
889
   * free the block of size 0.  Harumph. This seems
 
890
   * to work ok, though.
 
891
   */
 
892
  if (size == 0)
 
893
    {
 
894
       memset(set, 0, sizeof(*set));
 
895
       return REG_NOERROR;
 
896
    }
897
897
  set->alloc = size;
898
898
  set->nelem = 0;
899
899
  set->elems = re_malloc (int, size);
1258
1258
  return 1;
1259
1259
}
1260
1260
 
 
1261
/* Insert the new element ELEM to the re_node_set* SET.
 
1262
   SET should not already have any element greater than or equal to ELEM.
 
1263
   Return -1 if an error is occured, return 1 otherwise.  */
 
1264
 
 
1265
static int
 
1266
re_node_set_insert_last (set, elem)
 
1267
     re_node_set *set;
 
1268
     int elem;
 
1269
{
 
1270
  /* Realloc if we need.  */
 
1271
  if (set->alloc == set->nelem)
 
1272
    {
 
1273
      int *new_array;
 
1274
      set->alloc = (set->alloc + 1) * 2;
 
1275
      new_array = re_realloc (set->elems, int, set->alloc);
 
1276
      if (BE (new_array == NULL, 0))
 
1277
        return -1;
 
1278
      set->elems = new_array;
 
1279
    }
 
1280
 
 
1281
  /* Insert the new element.  */
 
1282
  set->elems[set->nelem++] = elem;
 
1283
  return 1;
 
1284
}
 
1285
 
1261
1286
/* Compare two node sets SET1 and SET2.
1262
1287
   return 1 if SET1 and SET2 are equivalent, return 0 otherwise.  */
1263
1288
 
1281
1306
     const re_node_set *set;
1282
1307
     int elem;
1283
1308
{
1284
 
  int idx, right, mid;
 
1309
  unsigned int idx, right, mid;
1285
1310
  if (set->nelem <= 0)
1286
1311
    return 0;
1287
1312
 
1316
1341
   Or return -1, if an error will be occured.  */
1317
1342
 
1318
1343
static int
1319
 
re_dfa_add_node (dfa, token, mode)
 
1344
re_dfa_add_node (dfa, token)
1320
1345
     re_dfa_t *dfa;
1321
1346
     re_token_t token;
1322
 
     int mode;
1323
1347
{
1324
1348
  if (BE (dfa->nodes_len >= dfa->nodes_alloc, 0))
1325
1349
    {
1326
1350
      int new_nodes_alloc = dfa->nodes_alloc * 2;
 
1351
      int *new_nexts, *new_indices;
 
1352
      re_node_set *new_edests, *new_eclosures;
 
1353
 
1327
1354
      re_token_t *new_array = re_realloc (dfa->nodes, re_token_t,
1328
1355
                                          new_nodes_alloc);
1329
1356
      if (BE (new_array == NULL, 0))
1330
1357
        return -1;
1331
1358
      dfa->nodes = new_array;
1332
 
      if (mode)
1333
 
        {
1334
 
          int *new_nexts, *new_indices;
1335
 
          re_node_set *new_edests, *new_eclosures, *new_inveclosures;
1336
 
 
1337
 
          new_nexts = re_realloc (dfa->nexts, int, new_nodes_alloc);
1338
 
          new_indices = re_realloc (dfa->org_indices, int, new_nodes_alloc);
1339
 
          new_edests = re_realloc (dfa->edests, re_node_set, new_nodes_alloc);
1340
 
          new_eclosures = re_realloc (dfa->eclosures, re_node_set,
1341
 
                                      new_nodes_alloc);
1342
 
          new_inveclosures = re_realloc (dfa->inveclosures, re_node_set,
1343
 
                                         new_nodes_alloc);
1344
 
          if (BE (new_nexts == NULL || new_indices == NULL
1345
 
                  || new_edests == NULL || new_eclosures == NULL
1346
 
                  || new_inveclosures == NULL, 0))
1347
 
            return -1;
1348
 
          dfa->nexts = new_nexts;
1349
 
          dfa->org_indices = new_indices;
1350
 
          dfa->edests = new_edests;
1351
 
          dfa->eclosures = new_eclosures;
1352
 
          dfa->inveclosures = new_inveclosures;
1353
 
        }
 
1359
      new_nexts = re_realloc (dfa->nexts, int, new_nodes_alloc);
 
1360
      new_indices = re_realloc (dfa->org_indices, int, new_nodes_alloc);
 
1361
      new_edests = re_realloc (dfa->edests, re_node_set, new_nodes_alloc);
 
1362
      new_eclosures = re_realloc (dfa->eclosures, re_node_set, new_nodes_alloc);
 
1363
      if (BE (new_nexts == NULL || new_indices == NULL
 
1364
              || new_edests == NULL || new_eclosures == NULL, 0))
 
1365
        return -1;
 
1366
      dfa->nexts = new_nexts;
 
1367
      dfa->org_indices = new_indices;
 
1368
      dfa->edests = new_edests;
 
1369
      dfa->eclosures = new_eclosures;
1354
1370
      dfa->nodes_alloc = new_nodes_alloc;
1355
1371
    }
1356
1372
  dfa->nodes[dfa->nodes_len] = token;
1357
 
  dfa->nodes[dfa->nodes_len].opt_subexp = 0;
1358
 
  dfa->nodes[dfa->nodes_len].duplicated = 0;
1359
1373
  dfa->nodes[dfa->nodes_len].constraint = 0;
 
1374
#ifdef RE_ENABLE_I18N
 
1375
  dfa->nodes[dfa->nodes_len].accept_mb =
 
1376
    (token.type == OP_PERIOD && dfa->mb_cur_max > 1) || token.type == COMPLEX_BRACKET;
 
1377
#endif
 
1378
  dfa->nexts[dfa->nodes_len] = -1;
 
1379
  re_node_set_init_empty (dfa->edests + dfa->nodes_len);
 
1380
  re_node_set_init_empty (dfa->eclosures + dfa->nodes_len);
1360
1381
  return dfa->nodes_len++;
1361
1382
}
1362
1383
 
1467
1488
    }
1468
1489
}
1469
1490
 
1470
 
/* Allocate memory for DFA state and initialize common properties.
1471
 
   Return the new state if succeeded, otherwise return NULL.  */
1472
 
 
1473
 
static re_dfastate_t *
1474
 
create_newstate_common (dfa, nodes, hash)
1475
 
     re_dfa_t *dfa;
1476
 
     const re_node_set *nodes;
1477
 
     unsigned int hash;
1478
 
{
1479
 
  re_dfastate_t *newstate;
1480
 
  reg_errcode_t err;
1481
 
  newstate = (re_dfastate_t *) calloc (sizeof (re_dfastate_t), 1);
1482
 
  if (BE (newstate == NULL, 0))
1483
 
    return NULL;
1484
 
  err = re_node_set_init_copy (&newstate->nodes, nodes);
1485
 
  if (BE (err != REG_NOERROR, 0))
1486
 
    {
1487
 
      re_free (newstate);
1488
 
      return NULL;
1489
 
    }
1490
 
  newstate->trtable = NULL;
1491
 
  newstate->hash = hash;
1492
 
  return newstate;
1493
 
}
1494
 
 
1495
 
/* Store the new state NEWSTATE whose hash value is HASH in appropriate
1496
 
   position.  Return value indicate the error code if failed.  */
 
1491
/* Finish initialization of the new state NEWSTATE, and using its hash value
 
1492
   HASH put in the appropriate bucket of DFA's state table.  Return value
 
1493
   indicates the error code if failed.  */
1497
1494
 
1498
1495
static reg_errcode_t
1499
1496
register_state (dfa, newstate, hash)
1502
1499
     unsigned int hash;
1503
1500
{
1504
1501
  struct re_state_table_entry *spot;
 
1502
  reg_errcode_t err;
 
1503
  int i;
 
1504
 
 
1505
  newstate->hash = hash;
 
1506
  err = re_node_set_alloc (&newstate->non_eps_nodes, newstate->nodes.nelem);
 
1507
  if (BE (err != REG_NOERROR, 0))
 
1508
    return REG_ESPACE;
 
1509
  for (i = 0; i < newstate->nodes.nelem; i++)
 
1510
    {
 
1511
      int elem = newstate->nodes.elems[i];
 
1512
      if (!IS_EPSILON_NODE (dfa->nodes[elem].type))
 
1513
        re_node_set_insert_last (&newstate->non_eps_nodes, elem);
 
1514
    }
 
1515
 
1505
1516
  spot = dfa->state_table + (hash & dfa->state_hash_mask);
1506
 
 
1507
1517
  if (BE (spot->alloc <= spot->num, 0))
1508
1518
    {
1509
1519
      int new_alloc = 2 * spot->num + 2;
1530
1540
  int i;
1531
1541
  reg_errcode_t err;
1532
1542
  re_dfastate_t *newstate;
1533
 
  newstate = create_newstate_common (dfa, nodes, hash);
 
1543
 
 
1544
  newstate = (re_dfastate_t *) calloc (sizeof (re_dfastate_t), 1);
1534
1545
  if (BE (newstate == NULL, 0))
1535
1546
    return NULL;
 
1547
  err = re_node_set_init_copy (&newstate->nodes, nodes);
 
1548
  if (BE (err != REG_NOERROR, 0))
 
1549
    {
 
1550
      re_free (newstate);
 
1551
      return NULL;
 
1552
    }
 
1553
 
1536
1554
  newstate->entrance_nodes = &newstate->nodes;
1537
 
 
1538
1555
  for (i = 0 ; i < nodes->nelem ; i++)
1539
1556
    {
1540
1557
      re_token_t *node = dfa->nodes + nodes->elems[i];
1541
1558
      re_token_type_t type = node->type;
1542
1559
      if (type == CHARACTER && !node->constraint)
1543
1560
        continue;
 
1561
#ifdef RE_ENABLE_I18N
 
1562
      newstate->accept_mb |= node->accept_mb;
 
1563
#endif /* RE_ENABLE_I18N */
1544
1564
 
1545
1565
      /* If the state has the halt node, the state is a halt state.  */
1546
 
      else if (type == END_OF_RE)
 
1566
      if (type == END_OF_RE)
1547
1567
        newstate->halt = 1;
1548
 
#ifdef RE_ENABLE_I18N
1549
 
      else if (type == COMPLEX_BRACKET
1550
 
               || type == OP_UTF8_PERIOD
1551
 
               || (type == OP_PERIOD && dfa->mb_cur_max > 1))
1552
 
        newstate->accept_mb = 1;
1553
 
#endif /* RE_ENABLE_I18N */
1554
1568
      else if (type == OP_BACK_REF)
1555
1569
        newstate->has_backref = 1;
1556
1570
      else if (type == ANCHOR || node->constraint)
1578
1592
  reg_errcode_t err;
1579
1593
  re_dfastate_t *newstate;
1580
1594
 
1581
 
  newstate = create_newstate_common (dfa, nodes, hash);
 
1595
  newstate = (re_dfastate_t *) calloc (sizeof (re_dfastate_t), 1);
1582
1596
  if (BE (newstate == NULL, 0))
1583
1597
    return NULL;
 
1598
  err = re_node_set_init_copy (&newstate->nodes, nodes);
 
1599
  if (BE (err != REG_NOERROR, 0))
 
1600
    {
 
1601
      re_free (newstate);
 
1602
      return NULL;
 
1603
    }
 
1604
 
1584
1605
  newstate->context = context;
1585
1606
  newstate->entrance_nodes = &newstate->nodes;
1586
1607
 
1594
1615
 
1595
1616
      if (type == CHARACTER && !constraint)
1596
1617
        continue;
 
1618
#ifdef RE_ENABLE_I18N
 
1619
      newstate->accept_mb |= node->accept_mb;
 
1620
#endif /* RE_ENABLE_I18N */
 
1621
 
1597
1622
      /* If the state has the halt node, the state is a halt state.  */
1598
 
      else if (type == END_OF_RE)
 
1623
      if (type == END_OF_RE)
1599
1624
        newstate->halt = 1;
1600
 
#ifdef RE_ENABLE_I18N
1601
 
      else if (type == COMPLEX_BRACKET
1602
 
               || type == OP_UTF8_PERIOD
1603
 
               || (type == OP_PERIOD && dfa->mb_cur_max > 1))
1604
 
        newstate->accept_mb = 1;
1605
 
#endif /* RE_ENABLE_I18N */
1606
1625
      else if (type == OP_BACK_REF)
1607
1626
        newstate->has_backref = 1;
1608
1627
      else if (type == ANCHOR)
1643
1662
free_state (state)
1644
1663
     re_dfastate_t *state;
1645
1664
{
 
1665
  re_node_set_free (&state->non_eps_nodes);
 
1666
  re_node_set_free (&state->inveclosure);
1646
1667
  if (state->entrance_nodes != &state->nodes)
1647
1668
    {
1648
1669
      re_node_set_free (state->entrance_nodes);
1649
1670
      re_free (state->entrance_nodes);
1650
1671
    }
1651
1672
  re_node_set_free (&state->nodes);
 
1673
  re_free (state->word_trtable);
1652
1674
  re_free (state->trtable);
1653
1675
  re_free (state);
1654
1676
}