← Back to branch summary

~ubuntu-branches/ubuntu/maverick/libxml2/maverick

« back to all changes in this revision

Viewing changes to xmlregexp.c

  • Committer: Bazaar Package Importer
  • Author(s): Matthias Klose
  • Date: 2007-05-18 15:29:30 UTC
  • mfrom: (1.1.5 upstream)
  • Revision ID: james.westby@ubuntu.com-20070518152930-yo3h40tjup1cn5zj
Tags: 2.6.28.dfsg-1ubuntu1
* Merge with Debian; remaining changes:
  - debian/rules: create a udeb for debian-installer, correct libxml2-dev
    Depends to include zlib1g-dev.
  - Build a python-libxml2-dbg package.

Show diffs side-by-side

added added

removed removed

Lines of Context:
xmlregexp.c
54
54
#define CUR_SCHAR(s, l) xmlStringCurrentChar(NULL, s, &l)
55
55
#define NEXTL(l) ctxt->cur += l;
56
56
#define XML_REG_STRING_SEPARATOR '|'
 
57
/*
 
58
 * Need PREV to check on a '-' within a Character Group. May only be used
 
59
 * when it's guaranteed that cur is not at the beginning of ctxt->string!
 
60
 */
 
61
#define PREV (ctxt->cur[-1])
57
62
 
58
63
/**
59
64
 * TODO:
145
150
    XML_REGEXP_START_STATE = 1,
146
151
    XML_REGEXP_FINAL_STATE,
147
152
    XML_REGEXP_TRANS_STATE,
148
 
    XML_REGEXP_SINK_STATE
 
153
    XML_REGEXP_SINK_STATE,
 
154
    XML_REGEXP_UNREACH_STATE
149
155
} xmlRegStateType;
150
156
 
151
157
typedef enum {
1595
1601
            atom->quant = XML_REGEXP_QUANT_ONCE;
1596
1602
            xmlRegStateAddTrans(ctxt, to, atom, to, -1, -1);
1597
1603
            break;
 
1604
        case XML_REGEXP_QUANT_RANGE: 
 
1605
            if (atom->min == 0) {
 
1606
                xmlFAGenerateEpsilonTransition(ctxt, from, to);
 
1607
            }
 
1608
            break;
1598
1609
        default:
1599
1610
            break;
1600
1611
    }
1709
1720
            continue;
1710
1721
        if (state->nbTrans != 1)
1711
1722
            continue;
 
1723
        if (state->type == XML_REGEXP_UNREACH_STATE)
 
1724
            continue;
1712
1725
        /* is the only transition out a basic transition */
1713
1726
        if ((state->trans[0].atom == NULL) &&
1714
1727
            (state->trans[0].to >= 0) &&
1731
1744
                    tmp = ctxt->states[state->transTo[i]];
1732
1745
                    for (j = 0;j < tmp->nbTrans;j++) {
1733
1746
                        if (tmp->trans[j].to == statenr) {
1734
 
                            tmp->trans[j].to = newto;
1735
 
#ifdef DEBUG_REGEXP_GRAPH
1736
 
                            printf("Changed transition %d on %d to go to %d\n",
1737
 
                                   j, tmp->no, newto);
1738
 
#endif     
1739
 
                            xmlRegStateAddTransTo(ctxt, ctxt->states[newto],
1740
 
                                                  tmp->no);
1741
 
                        }
1742
 
                    }
1743
 
                }
1744
 
#if 0
1745
 
                for (i = 0;i < ctxt->nbStates;i++) {
1746
 
                    tmp = ctxt->states[i];
1747
 
                    for (j = 0;j < tmp->nbTrans;j++) {
1748
 
                        if (tmp->trans[j].to == statenr) {
1749
 
                            tmp->trans[j].to = newto;
1750
 
#ifdef DEBUG_REGEXP_GRAPH
1751
 
                            printf("Changed transition %d on %d to go to %d\n",
1752
 
                                   j, tmp->no, newto);
1753
 
#endif     
1754
 
                        }
1755
 
                    }
1756
 
                }
1757
 
#endif
 
1747
#ifdef DEBUG_REGEXP_GRAPH
 
1748
                            printf("Changed transition %d on %d to go to %d\n",
 
1749
                                   j, tmp->no, newto);
 
1750
#endif     
 
1751
                            tmp->trans[j].to = -1;
 
1752
                            xmlRegStateAddTrans(ctxt, tmp, tmp->trans[j].atom,
 
1753
                                                ctxt->states[newto],
 
1754
                                                tmp->trans[j].counter,
 
1755
                                                tmp->trans[j].count);
 
1756
                        }
 
1757
                    }
 
1758
                }
1758
1759
                if (state->type == XML_REGEXP_FINAL_STATE)
1759
1760
                    ctxt->states[newto]->type = XML_REGEXP_FINAL_STATE;
1760
1761
                /* eliminate the transition completely */
1761
1762
                state->nbTrans = 0;
1762
1763
 
 
1764
                state->type = XML_REGEXP_UNREACH_STATE;
1763
1765
 
1764
1766
            }
1765
1767
            
1779
1781
 
1780
1782
    if (ctxt->states == NULL) return;
1781
1783
 
 
1784
    /*
 
1785
     * Eliminate simple epsilon transition and the associated unreachable
 
1786
     * states.
 
1787
     */
1782
1788
    xmlFAEliminateSimpleEpsilonTransitions(ctxt);
 
1789
    for (statenr = 0;statenr < ctxt->nbStates;statenr++) {
 
1790
        state = ctxt->states[statenr];
 
1791
        if ((state != NULL) && (state->type == XML_REGEXP_UNREACH_STATE)) {
 
1792
#ifdef DEBUG_REGEXP_GRAPH
 
1793
            printf("Removed unreachable state %d\n", statenr);
 
1794
#endif
 
1795
            xmlRegFreeState(state);
 
1796
            ctxt->states[statenr] = NULL;
 
1797
        }
 
1798
    }
1783
1799
 
1784
1800
    has_epsilon = 0;
1785
1801
 
1786
1802
    /*
1787
 
     * build the completed transitions bypassing the epsilons
 
1803
     * Build the completed transitions bypassing the epsilons
1788
1804
     * Use a marking algorithm to avoid loops
1789
 
     * mark sink states too.
 
1805
     * Mark sink states too.
 
1806
     * Process from the latests states backward to the start when
 
1807
     * there is long cascading epsilon chains this minimize the
 
1808
     * recursions and transition compares when adding the new ones
1790
1809
     */
1791
 
    for (statenr = 0;statenr < ctxt->nbStates;statenr++) {
 
1810
    for (statenr = ctxt->nbStates - 1;statenr >= 0;statenr--) {
1792
1811
        state = ctxt->states[statenr];
1793
1812
        if (state == NULL)
1794
1813
            continue;
1812
1831
                    printf("Found epsilon trans %d from %d to %d\n",
1813
1832
                           transnr, statenr, newto);
1814
1833
#endif
 
1834
                    has_epsilon = 1;
 
1835
                    state->trans[transnr].to = -2;
1815
1836
                    state->mark = XML_REGEXP_MARK_START;
1816
 
                    has_epsilon = 1;
1817
1837
                    xmlFAReduceEpsilonTransitions(ctxt, statenr,
1818
1838
                                      newto, state->trans[transnr].counter);
1819
1839
                    state->mark = XML_REGEXP_MARK_NORMAL;
2424
2444
         * check transitions conflicting with the one looked at
2425
2445
         */
2426
2446
        if (t1->atom == NULL) {
2427
 
            if (t1->to == -1)
 
2447
            if (t1->to < 0)
2428
2448
                continue;
2429
2449
            res = xmlFARecurseDeterminism(ctxt, ctxt->states[t1->to],
2430
2450
                                           to, atom);
2875
2895
        int i;
2876
2896
        printf(": ");
2877
2897
        for (i = 0;(i < 3) && (i < exec->inputStackNr);i++)
2878
 
            printf("%s ", exec->inputStack[exec->inputStackNr - (i + 1)]);
 
2898
            printf("%s ", (const char *)
 
2899
                   exec->inputStack[exec->inputStackNr - (i + 1)].value);
2879
2900
    } else {
2880
2901
        printf(": %s", &(exec->inputString[exec->index]));
2881
2902
    }
4842
4863
        ERROR("Expecting a char range");
4843
4864
        return;
4844
4865
    }
 
4866
    /*
 
4867
     * Since we are "inside" a range, we can assume ctxt->cur is past
 
4868
     * the start of ctxt->string, and PREV should be safe
 
4869
     */
 
4870
    if ((start == '-') && (NXT(1) != ']') && (PREV != '[') && (PREV != '^')) {
 
4871
        NEXTL(len);
 
4872
        return;
 
4873
    }
4845
4874
    NEXTL(len);
4846
 
    if (start == '-') {
4847
 
        return;
4848
 
    }
4849
4875
    cur = CUR;
4850
4876
    if ((cur != '-') || (NXT(1) == ']')) {
4851
4877
        xmlRegAtomAddRange(ctxt, ctxt->atom, ctxt->neg,