| blob | feae87460ed5b58923b78c9dd76ed3deb98a4999 |
1 /*
2 * regexp.c: generic and extensible Regular Expression engine
3 *
4 * Basically designed with the purpose of compiling regexps for
5 * the variety of validation/shemas mechanisms now available in
6 * XML related specifications these include:
7 * - XML-1.0 DTD validation
8 * - XML Schemas structure part 1
9 * - XML Schemas Datatypes part 2 especially Appendix F
10 * - RELAX-NG/TREX i.e. the counter proposal
11 *
12 * See Copyright for the status of this software.
13 *
14 * Daniel Veillard <veillard@redhat.com>
15 */
17 #define IN_LIBXML
20 #ifdef LIBXML_REGEXP_ENABLED
22 /* #define DEBUG_ERR */
24 #include <stdio.h>
25 #include <string.h>
26 #ifdef HAVE_LIMITS_H
27 #include <limits.h>
28 #endif
30 #include <libxml/tree.h>
31 #include <libxml/parserInternals.h>
32 #include <libxml/xmlregexp.h>
33 #include <libxml/xmlautomata.h>
34 #include <libxml/xmlunicode.h>
36 #ifndef INT_MAX
38 #endif
40 /* #define DEBUG_REGEXP_GRAPH */
41 /* #define DEBUG_REGEXP_EXEC */
42 /* #define DEBUG_PUSH */
43 /* #define DEBUG_COMPACTION */
45 #define MAX_PUSH 10000000
47 #define ERROR(str) \
48 ctxt->error = XML_REGEXP_COMPILE_ERROR; \
49 xmlRegexpErrCompile(ctxt, str);
50 #define NEXT ctxt->cur++
51 #define CUR (*(ctxt->cur))
52 #define NXT(index) (ctxt->cur[index])
54 #define CUR_SCHAR(s, l) xmlStringCurrentChar(NULL, s, &l)
55 #define NEXTL(l) ctxt->cur += l;
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])
63 /**
64 * TODO:
65 *
66 * macro to flag unimplemented blocks
67 */
68 #define TODO \
69 xmlGenericError(xmlGenericErrorContext, \
71 __FILE__, __LINE__);
73 /************************************************************************
74 * *
75 * Datatypes and structures *
76 * *
77 ************************************************************************/
79 /*
80 * Note: the order of the enums below is significant, do not shuffle
81 */
84 XML_REGEXP_CHARVAL,
85 XML_REGEXP_RANGES,
87 XML_REGEXP_STRING,
100 XML_REGEXP_LETTER_UPPERCASE,
101 XML_REGEXP_LETTER_LOWERCASE,
102 XML_REGEXP_LETTER_TITLECASE,
103 XML_REGEXP_LETTER_MODIFIER,
104 XML_REGEXP_LETTER_OTHERS,
105 XML_REGEXP_MARK,
106 XML_REGEXP_MARK_NONSPACING,
107 XML_REGEXP_MARK_SPACECOMBINING,
108 XML_REGEXP_MARK_ENCLOSING,
109 XML_REGEXP_NUMBER,
110 XML_REGEXP_NUMBER_DECIMAL,
111 XML_REGEXP_NUMBER_LETTER,
112 XML_REGEXP_NUMBER_OTHERS,
113 XML_REGEXP_PUNCT,
114 XML_REGEXP_PUNCT_CONNECTOR,
115 XML_REGEXP_PUNCT_DASH,
116 XML_REGEXP_PUNCT_OPEN,
117 XML_REGEXP_PUNCT_CLOSE,
118 XML_REGEXP_PUNCT_INITQUOTE,
119 XML_REGEXP_PUNCT_FINQUOTE,
120 XML_REGEXP_PUNCT_OTHERS,
121 XML_REGEXP_SEPAR,
122 XML_REGEXP_SEPAR_SPACE,
123 XML_REGEXP_SEPAR_LINE,
124 XML_REGEXP_SEPAR_PARA,
125 XML_REGEXP_SYMBOL,
126 XML_REGEXP_SYMBOL_MATH,
127 XML_REGEXP_SYMBOL_CURRENCY,
128 XML_REGEXP_SYMBOL_MODIFIER,
129 XML_REGEXP_SYMBOL_OTHERS,
130 XML_REGEXP_OTHER,
131 XML_REGEXP_OTHER_CONTROL,
132 XML_REGEXP_OTHER_FORMAT,
133 XML_REGEXP_OTHER_PRIVATE,
134 XML_REGEXP_OTHER_NA,
135 XML_REGEXP_BLOCK_NAME
140 XML_REGEXP_QUANT_ONCE,
141 XML_REGEXP_QUANT_OPT,
142 XML_REGEXP_QUANT_MULT,
143 XML_REGEXP_QUANT_PLUS,
144 XML_REGEXP_QUANT_ONCEONLY,
145 XML_REGEXP_QUANT_ALL,
146 XML_REGEXP_QUANT_RANGE
151 XML_REGEXP_FINAL_STATE,
152 XML_REGEXP_TRANS_STATE,
153 XML_REGEXP_SINK_STATE,
154 XML_REGEXP_UNREACH_STATE
159 XML_REGEXP_MARK_START,
160 XML_REGEXP_MARK_VISITED
168 xmlRegAtomType type;
172 };
182 xmlRegAtomType type;
183 xmlRegQuantType quant;
191 xmlRegStatePtr start;
192 xmlRegStatePtr start0;
193 xmlRegStatePtr stop;
198 };
206 };
212 xmlRegAtomPtr atom;
217 };
220 xmlRegStateType type;
221 xmlRegMarkedType mark;
222 xmlRegMarkedType reached;
227 /* knowing states ponting to us can speed things up */
231 };
236 #define AM_AUTOMATA_RNG 1
245 xmlRegStatePtr start;
246 xmlRegStatePtr end;
247 xmlRegStatePtr state;
249 xmlRegAtomPtr atom;
266 };
278 /*
279 * That's the compact form for determinists automatas
280 */
286 };
296 };
304 };
310 xmlRegExecCallbacks callback;
317 /*
318 * A stack of rollback states
319 */
324 /*
325 * The state of the automata if any
326 */
329 /*
330 * The input stack
331 */
339 /*
340 * error handling
341 */
347 };
349 #define REGEXP_ALL_COUNTER 0x123456
350 #define REGEXP_ALL_LAX_COUNTER 0x123457
362 /************************************************************************
363 * *
364 * Regexp memory error handler *
365 * *
366 ************************************************************************/
367 /**
368 * xmlRegexpErrMemory:
369 * @extra: extra information
370 *
371 * Handle an out of memory condition
372 */
373 static void
375 {
380 }
385 }
387 /**
388 * xmlRegexpErrCompile:
389 * @extra: extra information
390 *
391 * Handle a compilation failure
392 */
393 static void
395 {
403 }
408 }
410 /************************************************************************
411 * *
412 * Allocation/Deallocation *
413 * *
414 ************************************************************************/
417 /**
418 * xmlRegEpxFromParse:
419 * @ctxt: the parser context used to build it
420 *
421 * Allocate a new regexp and fill it with the result from the parser
422 *
423 * Returns the new regexp or NULL in case of error
424 */
425 static xmlRegexpPtr
427 xmlRegexpPtr ret;
433 }
446 }
462 /*
463 * Switch to a compact representation
464 * 1/ counting the effective number of states left
465 * 2/ counting the unique number of atoms, and check that
466 * they are all of the string type
467 * 3/ build a table state x atom for the transitions
468 */
475 }
479 nbstates++;
482 }
483 }
484 #ifdef DEBUG_COMPACTION
486 #endif
493 }
501 }
510 }
511 }
523 }
524 nbatoms++;
525 }
534 }
535 }
536 #ifdef DEBUG_COMPACTION
538 #endif
547 }
550 /*
551 * Allocate the transition table. The first entry for each
552 * state corresponds to the state type.
553 */
558 xmlRegStatePtr state;
559 xmlRegTransPtr trans;
582 }
583 }
585 /*
586 * if the same atom can generate transitions to 2 different
587 * states then it means the automata is not determinist and
588 * the compact form can't be used !
589 */
594 #ifdef DEBUG_COMPACTION
598 #endif
608 }
610 #if 0
613 #endif
619 }
620 }
621 }
623 #ifdef DEBUG_COMPACTION
624 /*
625 * Debug
626 */
630 }
632 }
634 #endif
635 /*
636 * Cleanup of the old data
637 */
642 }
649 }
660 }
661 not_determ:
670 }
672 /**
673 * xmlRegNewParserCtxt:
674 * @string: the string to parse
675 *
676 * Allocate a new regexp parser context
677 *
678 * Returns the new context or NULL in case of error
679 */
680 static xmlRegParserCtxtPtr
682 xmlRegParserCtxtPtr ret;
696 }
698 /**
699 * xmlRegNewRange:
700 * @ctxt: the regexp parser context
701 * @neg: is that negative
702 * @type: the type of range
703 * @start: the start codepoint
704 * @end: the end codepoint
705 *
706 * Allocate a new regexp range
707 *
708 * Returns the new range or NULL in case of error
709 */
710 static xmlRegRangePtr
713 xmlRegRangePtr ret;
719 }
725 }
727 /**
728 * xmlRegFreeRange:
729 * @range: the regexp range
730 *
731 * Free a regexp range
732 */
733 static void
741 }
743 /**
744 * xmlRegCopyRange:
745 * @range: the regexp range
746 *
747 * Copy a regexp range
748 *
749 * Returns the new copy or NULL in case of error.
750 */
751 static xmlRegRangePtr
753 xmlRegRangePtr ret;
768 }
769 }
771 }
773 /**
774 * xmlRegNewAtom:
775 * @ctxt: the regexp parser context
776 * @type: the type of atom
777 *
778 * Allocate a new atom
779 *
780 * Returns the new atom or NULL in case of error
781 */
782 static xmlRegAtomPtr
784 xmlRegAtomPtr ret;
790 }
797 }
799 /**
800 * xmlRegFreeAtom:
801 * @atom: the regexp atom
802 *
803 * Free a regexp atom
804 */
805 static void
823 }
825 /**
826 * xmlRegCopyAtom:
827 * @ctxt: the regexp parser context
828 * @atom: the oiginal atom
829 *
830 * Allocate a new regexp range
831 *
832 * Returns the new atom or NULL in case of error
833 */
834 static xmlRegAtomPtr
836 xmlRegAtomPtr ret;
842 }
856 }
862 }
863 }
866 error:
869 }
871 static xmlRegStatePtr
873 xmlRegStatePtr ret;
879 }
884 }
886 /**
887 * xmlRegFreeState:
888 * @state: the regexp state
889 *
890 * Free a regexp state
891 */
892 static void
902 }
904 /**
905 * xmlRegFreeParserCtxt:
906 * @ctxt: the regexp parser context
907 *
908 * Free a regexp parser context
909 */
910 static void
922 }
927 }
931 }
933 /************************************************************************
934 * *
935 * Display of Data structures *
936 * *
937 ************************************************************************/
939 static void
1048 }
1049 }
1051 static void
1070 }
1071 }
1072 static void
1079 }
1081 static void
1087 }
1107 }
1108 }
1110 static void
1116 }
1120 }
1124 else
1126 }
1129 }
1134 }
1138 }
1142 }
1144 static void
1152 }
1161 }
1162 }
1164 #ifdef DEBUG_REGEXP_GRAPH
1165 static void
1173 }
1184 }
1188 }
1197 }
1202 }
1203 }
1204 #endif
1206 /************************************************************************
1207 * *
1208 * Finite Automata structures manipulations *
1209 * *
1210 ************************************************************************/
1212 static void
1216 xmlRegRangePtr range;
1221 }
1225 }
1234 }
1244 }
1246 }
1253 }
1255 static int
1265 }
1275 }
1277 }
1281 }
1283 static int
1288 }
1297 }
1307 }
1309 }
1313 }
1315 static void
1326 }
1336 }
1338 }
1341 }
1343 static void
1353 }
1357 }
1358 /*
1359 * Other routines follow the philosophy 'When in doubt, add a transition'
1360 * so we check here whether such a transition is already present and, if
1361 * so, silently ignore this request.
1362 */
1370 #ifdef DEBUG_REGEXP_GRAPH
1373 #endif
1375 }
1376 }
1386 }
1396 }
1398 }
1399 #ifdef DEBUG_REGEXP_GRAPH
1411 #endif
1420 }
1422 static int
1433 }
1443 }
1445 }
1449 }
1451 /**
1452 * xmlFAGenerateAllTransition:
1453 * @ctxt: a regexp parser context
1454 * @from: the from state
1455 * @to: the target state or NULL for building a new one
1456 * @lax:
1457 *
1458 */
1459 static void
1467 }
1470 else
1472 }
1474 /**
1475 * xmlFAGenerateEpsilonTransition:
1476 * @ctxt: a regexp parser context
1477 * @from: the from state
1478 * @to: the target state or NULL for building a new one
1479 *
1480 */
1481 static void
1488 }
1490 }
1492 /**
1493 * xmlFAGenerateCountedEpsilonTransition:
1494 * @ctxt: a regexp parser context
1495 * @from: the from state
1496 * @to: the target state or NULL for building a new one
1497 * counter: the counter for that transition
1498 *
1499 */
1500 static void
1507 }
1509 }
1511 /**
1512 * xmlFAGenerateCountedTransition:
1513 * @ctxt: a regexp parser context
1514 * @from: the from state
1515 * @to: the target state or NULL for building a new one
1516 * counter: the counter for that transition
1517 *
1518 */
1519 static void
1526 }
1528 }
1530 /**
1531 * xmlFAGenerateTransitions:
1532 * @ctxt: a regexp parser context
1533 * @from: the from state
1534 * @to: the target state or NULL for building a new one
1535 * @atom: the atom generating the transition
1536 *
1537 * Returns 0 if success and -1 in case of error.
1538 */
1539 static int
1542 xmlRegStatePtr end;
1547 }
1549 /*
1550 * this is a subexpression handling one should not need to
1551 * create a new node except for XML_REGEXP_QUANT_RANGE.
1552 */
1555 }
1558 /*
1559 * Generate an epsilon transition to link to the target
1560 */
1562 #ifdef DV
1569 #endif
1570 }
1574 /*
1575 * transition done to the state after end of atom.
1576 * 1. set transition from atom start to new state
1577 * 2. set transition from atom end to this state.
1578 */
1585 }
1600 /*
1601 * create the final state now if needed
1602 */
1608 }
1610 /*
1611 * The principle here is to use counted transition
1612 * to avoid explosion in the number of states in the
1613 * graph. This is clearly more complex but should not
1614 * be exploitable at runtime.
1615 */
1617 xmlRegAtomPtr copy;
1618 /*
1619 * duplicate a transition based on atom to count next
1620 * occurences after 1. We cannot loop to atom->start
1621 * directly because we need an epsilon transition to
1622 * newstate.
1623 */
1624 /* ???? For some reason it seems we never reach that
1625 case, I suppose this got optimized out before when
1626 building the automata */
1641 /* count the number of times we see it again */
1644 /* allow a way out based on the count */
1647 /* and also allow a direct exit for 0 */
1649 newstate);
1651 /*
1652 * either we need the atom at least once or there
1653 * is an atom->start0 allowing to easilly plug the
1654 * epsilon transition.
1655 */
1659 /* count the number of times we see it again */
1662 /* allow a way out based on the count */
1665 /* and if needed allow a direct exit for 0 */
1668 newstate);
1670 }
1675 }
1678 }
1680 }
1683 /*
1684 * we can discard the atom and generate an epsilon transition instead
1685 */
1692 }
1693 }
1698 }
1705 }
1706 }
1710 /*
1711 * Do not pollute the target state by adding transitions from
1712 * it as it is likely to be the shared target of multiple branches.
1713 * So isolate with an epsilon transition.
1714 */
1715 xmlRegStatePtr tmp;
1722 }
1725 }
1728 }
1746 #if DV_test
1749 }
1750 #endif
1754 }
1756 }
1758 /**
1759 * xmlFAReduceEpsilonTransitions:
1760 * @ctxt: a regexp parser context
1761 * @fromnr: the from state
1762 * @tonr: the to state
1763 * @counter: should that transition be associated to a counted
1764 *
1765 */
1766 static void
1770 xmlRegStatePtr from;
1771 xmlRegStatePtr to;
1773 #ifdef DEBUG_REGEXP_GRAPH
1775 #endif
1788 #ifdef DEBUG_REGEXP_GRAPH
1790 #endif
1792 }
1797 /*
1798 * Don't remove counted transitions
1799 * Don't loop either
1800 */
1809 #ifdef DEBUG_REGEXP_GRAPH
1812 #endif
1820 counter);
1821 }
1822 }
1823 }
1834 }
1835 }
1836 }
1838 }
1840 /**
1841 * xmlFAEliminateSimpleEpsilonTransitions:
1842 * @ctxt: a regexp parser context
1843 *
1844 * Eliminating general epsilon transitions can get costly in the general
1845 * algorithm due to the large amount of generated new transitions and
1846 * associated comparisons. However for simple epsilon transition used just
1847 * to separate building blocks when generating the automata this can be
1848 * reduced to state elimination:
1849 * - if there exists an epsilon from X to Y
1850 * - if there is no other transition from X
1851 * then X and Y are semantically equivalent and X can be eliminated
1852 * If X is the start state then make Y the start state, else replace the
1853 * target of all transitions to X by transitions to Y.
1854 */
1855 static void
1868 /* is the only transition out a basic transition */
1877 #ifdef DEBUG_REGEXP_GRAPH
1880 #endif
1882 #ifdef DEBUG_REGEXP_GRAPH
1885 #endif
1890 #ifdef DEBUG_REGEXP_GRAPH
1893 #endif
1899 }
1900 }
1901 }
1904 /* eliminate the transition completely */
1909 }
1911 }
1912 }
1913 }
1914 /**
1915 * xmlFAEliminateEpsilonTransitions:
1916 * @ctxt: a regexp parser context
1917 *
1918 */
1919 static void
1922 xmlRegStatePtr state;
1927 /*
1928 * Eliminate simple epsilon transition and the associated unreachable
1929 * states.
1930 */
1935 #ifdef DEBUG_REGEXP_GRAPH
1937 #endif
1940 }
1941 }
1945 /*
1946 * Build the completed transitions bypassing the epsilons
1947 * Use a marking algorithm to avoid loops
1948 * Mark sink states too.
1949 * Process from the latests states backward to the start when
1950 * there is long cascading epsilon chains this minimize the
1951 * recursions and transition compares when adding the new ones
1952 */
1960 }
1966 #ifdef DEBUG_REGEXP_GRAPH
1969 #endif
1973 #ifdef DEBUG_REGEXP_GRAPH
1976 #endif
1983 #ifdef DEBUG_REGEXP_GRAPH
1987 #endif
1988 }
1989 }
1990 }
1991 }
1992 /*
1993 * Eliminate the epsilon transitions
1994 */
2006 }
2007 }
2008 }
2009 }
2011 /*
2012 * Use this pass to detect unreachable states too
2013 */
2018 }
2025 /*
2026 * Mark all states reachable from the current reachable state
2027 */
2039 }
2040 }
2041 }
2043 /*
2044 * find the next accessible state not explored
2045 */
2050 XML_REGEXP_MARK_START)) {
2053 }
2054 }
2055 }
2057 }
2061 #ifdef DEBUG_REGEXP_GRAPH
2063 #endif
2066 }
2067 }
2069 }
2071 static int
2083 /* put them in order */
2085 xmlRegRangePtr tmp;
2090 }
2103 else
2109 /*
2110 * just check all codepoints in the range for acceptance,
2111 * this is usually way cheaper since done only once at
2112 * compilation than testing over and over at runtime or
2113 * pushing too many states when evaluating.
2114 */
2128 }
2135 /*
2136 * comparing a block range with anything else is way
2137 * too costly, and maintining the table is like too much
2138 * memory too, so let's force the automata to save state
2139 * here.
2140 */
2142 }
2161 /* same thing to limit complexity */
2163 }
2166 /* range1->type < range2->type here */
2169 /* all disjoint except in the subgroups */
2223 /* safety net ! */
2225 }
2226 }
2227 }
2232 }
2234 /**
2235 * xmlFACompareAtomTypes:
2236 * @type1: an atom type
2237 * @type2: an atom type
2238 *
2239 * Compares two atoms type to check whether they intersect in some ways,
2240 * this is used by xmlFACompareAtoms only
2241 *
2242 * Returns 1 if they may intersect and 0 otherwise
2243 */
2244 static int
2263 /* simplify subsequent compares by making sure type1 < type2 */
2268 }
2271 /* can't be a letter, number, mark, pontuation, symbol */
2288 /* can't be a number, mark, separator, pontuation, symbol or other */
2307 /* can't be a mark, separator, pontuation, symbol or other */
2324 /* can't be a letter, mark, separator, pontuation, symbol or other */
2344 /* can't be a mark, separator, pontuation, symbol or other */
2360 /*
2361 * at that point we know both type 1 and type2 are from
2362 * character categories are ordered and are different,
2363 * it becomes simple because this is a partition
2364 */
2431 }
2433 }
2435 /**
2436 * xmlFAEqualAtoms:
2437 * @atom1: an atom
2438 * @atom2: an atom
2439 * @deep: if not set only compare string pointers
2440 *
2441 * Compares two atoms to check whether they are the same exactly
2442 * this is used to remove equivalent transitions
2443 *
2444 * Returns 1 if same and 0 otherwise
2445 */
2446 static int
2464 else
2472 /* too hard to do in the general case */
2476 }
2478 }
2480 /**
2481 * xmlFACompareAtoms:
2482 * @atom1: an atom
2483 * @atom2: an atom
2484 * @deep: if not set only compare string pointers
2485 *
2486 * Compares two atoms to check whether they intersect in some ways,
2487 * this is used by xmlFAComputesDeterminism and xmlFARecurseDeterminism only
2488 *
2489 * Returns 1 if yes and 0 otherwise
2490 */
2491 static int
2505 xmlRegAtomPtr tmp;
2509 }
2512 /* if they can't intersect at the type level break now */
2515 }
2520 else
2533 }
2540 /*
2541 * need to check that none of the ranges eventually matches
2542 */
2551 }
2552 }
2553 }
2555 }
2559 }
2560 done:
2563 }
2566 not_determinist:
2568 }
2570 /**
2571 * xmlFARecurseDeterminism:
2572 * @ctxt: a regexp parser context
2573 *
2574 * Check whether the associated regexp is determinist,
2575 * should be called after xmlFAEliminateEpsilonTransitions()
2576 *
2577 */
2578 static int
2584 xmlRegTransPtr t1;
2593 /*
2594 * don't recurse on transitions potentially added in the course of
2595 * the elimination.
2596 */
2600 /*
2601 * check transitions conflicting with the one looked at
2602 */
2610 /* t1->nd = 1; */
2611 }
2613 }
2618 /* mark the transition as non-deterministic */
2620 }
2621 }
2623 }
2625 /**
2626 * xmlFAComputesDeterminism:
2627 * @ctxt: a regexp parser context
2628 *
2629 * Check whether the associated regexp is determinist,
2630 * should be called after xmlFAEliminateEpsilonTransitions()
2631 *
2632 */
2633 static int
2636 xmlRegStatePtr state;
2642 #ifdef DEBUG_REGEXP_GRAPH
2645 #endif
2652 /*
2653 * First cleanup the automata removing cancelled transitions
2654 */
2663 /*
2664 * Determinism checks in case of counted or all transitions
2665 * will have to be handled separately
2666 */
2668 /* t1->nd = 1; */
2670 }
2679 /*
2680 * Here we use deep because we want to keep the
2681 * transitions which indicate a conflict
2682 */
2687 }
2688 }
2689 }
2690 }
2691 }
2693 /*
2694 * Check for all states that there aren't 2 transitions
2695 * with the same atom and a different target.
2696 */
2706 /*
2707 * Determinism checks in case of counted or all transitions
2708 * will have to be handled separately
2709 */
2712 }
2720 /*
2721 * But here we don't use deep because we want to
2722 * find transitions which indicate a conflict
2723 */
2726 /* mark the transitions as non-deterministic ones */
2730 }
2732 /*
2733 * do the closure in case of remaining specific
2734 * epsilon transitions like choices or all
2735 */
2738 /* don't shortcut the computation so all non deterministic
2739 transition get marked down
2740 if (ret == 0)
2741 return(0);
2742 */
2745 /* t2->nd = 1; */
2747 }
2748 }
2749 }
2750 /* don't shortcut the computation so all non deterministic
2751 transition get marked down
2752 if (ret == 0)
2753 break; */
2754 }
2756 /*
2757 * mark specifically the last non-deterministic transition
2758 * from a state since there is no need to set-up rollback
2759 * from it
2760 */
2763 }
2765 /* don't shortcut the computation so all non deterministic
2766 transition get marked down
2767 if (ret == 0)
2768 break; */
2769 }
2773 }
2775 /************************************************************************
2776 * *
2777 * Routines to check input against transition atoms *
2778 * *
2779 ************************************************************************/
2781 static int
2938 /* ret = xmlUCSIsCatCn(codepoint); */
2939 /* Seems it doesn't exist anymore in recent Unicode releases */
2945 }
2949 }
2951 static int
2954 xmlRegRangePtr range;
2982 else
2990 }
2991 }
2993 }
3050 }
3052 }
3054 /************************************************************************
3055 * *
3056 * Saving and restoring state of an execution context *
3057 * *
3058 ************************************************************************/
3060 #ifdef DEBUG_REGEXP_EXEC
3061 static void
3072 }
3074 }
3075 #endif
3077 static void
3079 #ifdef DEBUG_REGEXP_EXEC
3084 #endif
3085 #ifdef MAX_PUSH
3088 }
3090 #endif
3100 }
3114 }
3118 }
3130 }
3131 }
3134 }
3136 }
3138 static void
3142 #ifdef DEBUG_REGEXP_EXEC
3144 #endif
3146 }
3156 }
3159 }
3161 #ifdef DEBUG_REGEXP_EXEC
3164 #endif
3165 }
3167 /************************************************************************
3168 * *
3169 * Verifier, running an input against a compiled regexp *
3170 * *
3171 ************************************************************************/
3173 static int
3175 xmlRegExecCtxt execval;
3198 }
3206 xmlRegTransPtr trans;
3207 xmlRegAtomPtr atom;
3209 /*
3210 * If end of input on non-terminal state, rollback, however we may
3211 * still have epsilon like transition for counted transitions
3212 * on counters, in that case don't break too early. Additionally,
3213 * if we are working on a range like "AB{0,2}", where B is not present,
3214 * we don't want to break.
3215 */
3218 /*
3219 * if there is a transition, we must check if
3220 * atom allows minOccurs of 0
3221 */
3228 }
3231 }
3243 xmlRegCounterPtr counter;
3248 }
3249 /*
3250 * A counted transition.
3251 */
3255 #ifdef DEBUG_REGEXP_EXEC
3258 #endif
3272 /*
3273 * this is a multiple input sequence
3274 * If there is a counter associated increment it now.
3275 * before potentially saving and rollback
3276 * do not increment if the counter is already over the
3277 * maximum limit in which case get to next transition
3278 */
3280 xmlRegCounterPtr counter;
3287 }
3292 #ifdef DEBUG_REGEXP_EXEC
3294 #endif
3296 }
3299 }
3302 /*
3303 * Try to progress as much as possible on the input
3304 */
3307 }
3309 /*
3310 * End of input: stop here
3311 */
3315 }
3320 /*
3321 * The transition is acceptable save it
3322 */
3328 }
3330 len);
3337 /*
3338 * If the last check failed but one transition was found
3339 * possible, rollback
3340 */
3345 }
3350 }
3351 #ifdef DEBUG_REGEXP_EXEC
3353 #endif
3355 }
3357 /*
3358 * we don't match on the codepoint, but minOccurs of 0
3359 * says that's ok. Setting len to 0 inhibits stepping
3360 * over the codepoint.
3361 */
3365 }
3367 /* another spot to match when minOccurs is 0 */
3371 }
3376 #ifdef DEBUG_REGEXP_EXEC
3380 else
3383 #endif
3385 }
3387 xmlRegCounterPtr counter;
3389 /* make sure we don't go over the counter maximum value */
3395 }
3399 #ifdef DEBUG_REGEXP_EXEC
3401 #endif
3403 }
3409 }
3410 #ifdef DEBUG_REGEXP_EXEC
3413 #endif
3415 }
3416 #ifdef DEBUG_REGEXP_EXEC
3418 #endif
3423 }
3428 }
3429 }
3431 rollback:
3432 /*
3433 * Failed to find a way out
3434 */
3436 #ifdef DEBUG_REGEXP_EXEC
3439 #endif
3441 }
3442 progress:
3444 }
3445 error:
3453 }
3455 }
3464 }
3466 }
3468 /************************************************************************
3469 * *
3470 * Progressive interface to the verifier one atom at a time *
3471 * *
3472 ************************************************************************/
3473 #ifdef DEBUG_ERR
3475 #endif
3477 /**
3478 * xmlRegNewExecCtxt:
3479 * @comp: a precompiled regular expression
3480 * @callback: a callback function used for handling progresses in the
3481 * automata matching phase
3482 * @data: the context data associated to the callback in this context
3483 *
3484 * Build a context used for progressive evaluation of a regexp.
3485 *
3486 * Returns the new context
3487 */
3488 xmlRegExecCtxtPtr
3490 xmlRegExecCtxtPtr exec;
3500 }
3517 /*
3518 * For error handling, exec->counts is allocated twice the size
3519 * the second half is used to store the data in case of rollback
3520 */
3527 }
3533 }
3541 }
3543 /**
3544 * xmlRegFreeExecCtxt:
3545 * @exec: a regular expression evaulation context
3546 *
3547 * Free the structures associated to a regular expression evaulation context.
3548 */
3549 void
3561 }
3563 }
3572 }
3574 }
3578 }
3580 static void
3583 #ifdef DEBUG_PUSH
3585 #endif
3594 }
3596 xmlRegInputTokenPtr tmp;
3605 }
3607 }
3613 }
3615 /**
3616 * xmlRegStrEqualWildcard:
3617 * @expStr: the string to be evaluated
3618 * @valStr: the validation string
3619 *
3620 * Checks if both strings are equal or have the same content. "*"
3621 * can be used as a wildcard in @valStr; "|" is used as a seperator of
3622 * substrings in both @expStr and @valStr.
3623 *
3624 * Returns 1 if the comparison is satisfied and the number of substrings
3625 * is equal, 0 otherwise.
3626 */
3628 static int
3634 /*
3635 * Eval if we have a wildcard for the current item.
3636 */
3638 /* if one of them starts with a wildcard make valStr be it */
3645 }
3650 valStr++;
3655 }
3656 expStr++;
3657 valStr++;
3661 else
3663 }
3665 /**
3666 * xmlRegCompactPushString:
3667 * @exec: a regexp execution context
3668 * @comp: the precompiled exec with a compact table
3669 * @value: a string token input
3670 * @data: data associated to the token to reuse in callbacks
3671 *
3672 * Push one input token in the execution context
3673 *
3674 * Returns: 1 if the regexp reached a final state, 0 if non-final, and
3675 * a negative value in case of error.
3676 */
3677 static int
3679 xmlRegexpPtr comp,
3689 /*
3690 * are we at a final state ?
3691 */
3693 XML_REGEXP_FINAL_STATE)
3696 }
3698 #ifdef DEBUG_PUSH
3700 #endif
3702 /*
3703 * Examine all outside transitions from current state
3704 */
3714 }
3715 #ifdef DEBUG_PUSH
3717 #endif
3719 XML_REGEXP_SINK_STATE)
3723 XML_REGEXP_FINAL_STATE)
3726 }
3727 }
3728 }
3729 /*
3730 * Failed to find an exit transition out from current state for the
3731 * current token
3732 */
3733 #ifdef DEBUG_PUSH
3735 #endif
3736 error:
3742 #ifdef DEBUG_ERR
3744 #endif
3746 }
3748 /**
3749 * xmlRegExecPushStringInternal:
3750 * @exec: a regexp execution context or NULL to indicate the end
3751 * @value: a string token input
3752 * @data: data associated to the token to reuse in callbacks
3753 * @compound: value was assembled from 2 strings
3754 *
3755 * Push one input token in the execution context
3756 *
3757 * Returns: 1 if the regexp reached a final state, 0 if non-final, and
3758 * a negative value in case of error.
3759 */
3760 static int
3763 xmlRegTransPtr trans;
3764 xmlRegAtomPtr atom;
3783 }
3785 #ifdef DEBUG_PUSH
3787 #endif
3788 /*
3789 * If we have an active rollback stack push the new value there
3790 * and get back to where we were left
3791 */
3796 #ifdef DEBUG_PUSH
3798 #endif
3799 }
3806 /*
3807 * End of input on non-terminal state, rollback, however we may
3808 * still have epsilon like transition for counted transitions
3809 * on counters, in that case don't break too early.
3810 */
3824 xmlRegTransPtr t;
3825 xmlRegCounterPtr counter;
3829 #ifdef DEBUG_PUSH
3831 #endif
3832 /*
3833 * Check all counted transitions from the current state
3834 */
3849 }
3856 }
3857 }
3858 }
3862 xmlRegTransPtr t;
3863 xmlRegCounterPtr counter;
3867 #ifdef DEBUG_PUSH
3869 #endif
3870 /*
3871 * Check all counted transitions from the current state
3872 */
3882 }
3883 }
3886 xmlRegCounterPtr counter;
3888 /*
3889 * A counted transition.
3890 */
3894 #ifdef DEBUG_PUSH
3897 #endif
3909 }
3911 xmlRegCounterPtr counter;
3918 }
3923 /*
3924 * this is a multiple input sequence
3925 */
3929 }
3931 }
3934 /*
3935 * Try to progress as much as possible on the input
3936 */
3939 }
3943 #ifdef DEBUG_PUSH
3945 #endif
3947 /*
3948 * End of input: stop here
3949 */
3953 }
3958 /*
3959 * The transition is acceptable save it
3960 */
3965 }
3969 }
3976 /*
3977 * If the last check failed but one transition was found
3978 * possible, rollback
3979 */
3984 }
3985 }
3986 }
3992 }
3996 }
3998 }
4000 #ifdef DEBUG_PUSH
4002 #endif
4004 }
4007 #ifdef DEBUG_REGEXP_EXEC
4010 #endif
4012 }
4013 #ifdef DEBUG_PUSH
4015 #endif
4018 XML_REGEXP_SINK_STATE)) {
4019 /*
4020 * entering a sink state, save the current state as error
4021 * state.
4022 */
4029 }
4038 #ifdef DEBUG_PUSH
4040 #endif
4044 #ifdef DEBUG_PUSH
4046 #endif
4047 }
4051 #ifdef DEBUG_PUSH
4053 #endif
4054 }
4055 }
4060 }
4061 }
4063 rollback:
4064 /*
4065 * if we didn't yet rollback on the current input
4066 * store the current state as the error state.
4067 */
4077 }
4079 /*
4080 * Failed to find a way out
4081 */
4087 #ifdef DEBUG_PUSH
4089 #endif
4090 }
4091 }
4093 progress:
4096 }
4099 }
4100 #ifdef DEBUG_ERR
4103 }
4104 #endif
4106 }
4108 /**
4109 * xmlRegExecPushString:
4110 * @exec: a regexp execution context or NULL to indicate the end
4111 * @value: a string token input
4112 * @data: data associated to the token to reuse in callbacks
4113 *
4114 * Push one input token in the execution context
4115 *
4116 * Returns: 1 if the regexp reached a final state, 0 if non-final, and
4117 * a negative value in case of error.
4118 */
4119 int
4123 }
4125 /**
4126 * xmlRegExecPushString2:
4127 * @exec: a regexp execution context or NULL to indicate the end
4128 * @value: the first string token input
4129 * @value2: the second string token input
4130 * @data: data associated to the token to reuse in callbacks
4131 *
4132 * Push one input token in the execution context
4133 *
4134 * Returns: 1 if the regexp reached a final state, 0 if non-final, and
4135 * a negative value in case of error.
4136 */
4137 int
4162 }
4165 }
4173 else
4179 }
4181 /**
4182 * xmlRegExecGetValues:
4183 * @exec: a regexp execution context
4184 * @err: error extraction or normal one
4185 * @nbval: pointer to the number of accepted values IN/OUT
4186 * @nbneg: return number of negative transitions
4187 * @values: pointer to the array of acceptable values
4188 * @terminal: return value if this was a terminal state
4189 *
4190 * Extract informations from the regexp execution, internal routine to
4191 * implement xmlRegExecNextValues() and xmlRegExecErrInfo()
4192 *
4193 * Returns: 0 in case of success or -1 in case of error.
4194 */
4195 static int
4210 xmlRegexpPtr comp;
4220 }
4223 XML_REGEXP_FINAL_STATE)
4225 else
4227 }
4232 XML_REGEXP_SINK_STATE)) {
4235 }
4236 }
4241 XML_REGEXP_SINK_STATE)) {
4244 }
4245 }
4248 xmlRegTransPtr trans;
4249 xmlRegAtomPtr atom;
4250 xmlRegStatePtr state;
4255 else
4257 }
4265 }
4268 transno++) {
4276 /* this should not be reached but ... */
4277 TODO;
4279 /* this should not be reached but ... */
4280 TODO;
4287 else
4294 else
4297 }
4301 XML_REGEXP_SINK_STATE)) {
4304 else
4307 }
4308 }
4309 }
4312 transno++) {
4328 XML_REGEXP_SINK_STATE)) {
4331 else
4334 }
4335 }
4336 }
4337 }
4339 }
4341 /**
4342 * xmlRegExecNextValues:
4343 * @exec: a regexp execution context
4344 * @nbval: pointer to the number of accepted values IN/OUT
4345 * @nbneg: return number of negative transitions
4346 * @values: pointer to the array of acceptable values
4347 * @terminal: return value if this was a terminal state
4348 *
4349 * Extract informations from the regexp execution,
4350 * the parameter @values must point to an array of @nbval string pointers
4351 * on return nbval will contain the number of possible strings in that
4352 * state and the @values array will be updated with them. The string values
4353 * returned will be freed with the @exec context and don't need to be
4354 * deallocated.
4355 *
4356 * Returns: 0 in case of success or -1 in case of error.
4357 */
4358 int
4362 }
4364 /**
4365 * xmlRegExecErrInfo:
4366 * @exec: a regexp execution context generating an error
4367 * @string: return value for the error string
4368 * @nbval: pointer to the number of accepted values IN/OUT
4369 * @nbneg: return number of negative transitions
4370 * @values: pointer to the array of acceptable values
4371 * @terminal: return value if this was a terminal state
4372 *
4373 * Extract error informations from the regexp execution, the parameter
4374 * @string will be updated with the value pushed and not accepted,
4375 * the parameter @values must point to an array of @nbval string pointers
4376 * on return nbval will contain the number of possible strings in that
4377 * state and the @values array will be updated with them. The string values
4378 * returned will be freed with the @exec context and don't need to be
4379 * deallocated.
4380 *
4381 * Returns: 0 in case of success or -1 in case of error.
4382 */
4383 int
4391 else
4393 }
4395 }
4397 #ifdef DEBUG_ERR
4405 }
4406 #endif
4408 #if 0
4409 static int
4411 xmlRegTransPtr trans;
4412 xmlRegAtomPtr atom;
4425 /*
4426 * End of input on non-terminal state, rollback, however we may
4427 * still have epsilon like transition for counted transitions
4428 * on counters, in that case don't break too early.
4429 */
4442 xmlRegCounterPtr counter;
4444 /*
4445 * A counted transition.
4446 */
4450 #ifdef DEBUG_REGEXP_EXEC
4453 #endif
4465 /*
4466 * this is a multiple input sequence
4467 */
4470 }
4473 /*
4474 * Try to progress as much as possible on the input
4475 */
4478 }
4480 /*
4481 * End of input: stop here
4482 */
4486 }
4491 /*
4492 * The transition is acceptable save it
4493 */
4499 }
4501 len);
4508 /*
4509 * If the last check failed but one transition was found
4510 * possible, rollback
4511 */
4516 }
4517 }
4518 }
4522 }
4523 /*
4524 * restart count for expressions like this ((abc){2})*
4525 */
4527 #ifdef DEBUG_REGEXP_EXEC
4529 #endif
4531 }
4533 #ifdef DEBUG_REGEXP_EXEC
4535 #endif
4537 }
4538 #ifdef DEBUG_REGEXP_EXEC
4540 #endif
4545 }
4550 }
4551 }
4553 rollback:
4554 /*
4555 * Failed to find a way out
4556 */
4559 }
4560 progress:
4562 }
4563 }
4564 #endif
4565 /************************************************************************
4566 * *
4567 * Parser for the Schemas Datatype Regular Expressions *
4568 * http://www.w3.org/TR/2001/REC-xmlschema-2-20010502/#regexs *
4569 * *
4570 ************************************************************************/
4572 /**
4573 * xmlFAIsChar:
4574 * @ctxt: a regexp parser context
4575 *
4576 * [10] Char ::= [^.\?*+()|#x5B#x5D]
4577 */
4578 static int
4590 }
4592 /**
4593 * xmlFAParseCharProp:
4594 * @ctxt: a regexp parser context
4595 *
4596 * [27] charProp ::= IsCategory | IsBlock
4597 * [28] IsCategory ::= Letters | Marks | Numbers | Punctuation |
4598 * Separators | Symbols | Others
4599 * [29] Letters ::= 'L' [ultmo]?
4600 * [30] Marks ::= 'M' [nce]?
4601 * [31] Numbers ::= 'N' [dlo]?
4602 * [32] Punctuation ::= 'P' [cdseifo]?
4603 * [33] Separators ::= 'Z' [slp]?
4604 * [34] Symbols ::= 'S' [mcko]?
4605 * [35] Others ::= 'C' [cfon]?
4606 * [36] IsBlock ::= 'Is' [a-zA-Z0-9#x2D]+
4607 */
4608 static void
4616 NEXT;
4619 NEXT;
4622 NEXT;
4625 NEXT;
4628 NEXT;
4631 NEXT;
4635 }
4637 NEXT;
4640 NEXT;
4641 /* nonspacing */
4644 NEXT;
4645 /* spacing combining */
4648 NEXT;
4649 /* enclosing */
4652 /* all marks */
4654 }
4656 NEXT;
4659 NEXT;
4660 /* digital */
4663 NEXT;
4664 /* letter */
4667 NEXT;
4668 /* other */
4671 /* all numbers */
4673 }
4675 NEXT;
4678 NEXT;
4679 /* connector */
4682 NEXT;
4683 /* dash */
4686 NEXT;
4687 /* open */
4690 NEXT;
4691 /* close */
4694 NEXT;
4695 /* initial quote */
4698 NEXT;
4699 /* final quote */
4702 NEXT;
4703 /* other */
4706 /* all punctuation */
4708 }
4710 NEXT;
4713 NEXT;
4714 /* space */
4717 NEXT;
4718 /* line */
4721 NEXT;
4722 /* paragraph */
4725 /* all separators */
4727 }
4729 NEXT;
4732 NEXT;
4734 /* math */
4736 NEXT;
4738 /* currency */
4740 NEXT;
4742 /* modifiers */
4744 NEXT;
4746 /* other */
4748 /* all symbols */
4750 }
4752 NEXT;
4755 NEXT;
4756 /* control */
4759 NEXT;
4760 /* format */
4763 NEXT;
4764 /* private use */
4767 NEXT;
4768 /* not assigned */
4771 /* all others */
4773 }
4776 NEXT;
4781 }
4782 NEXT;
4789 NEXT;
4795 NEXT;
4797 }
4798 }
4804 }
4812 }
4813 }
4815 /**
4816 * xmlFAParseCharClassEsc:
4817 * @ctxt: a regexp parser context
4818 *
4819 * [23] charClassEsc ::= ( SingleCharEsc | MultiCharEsc | catEsc | complEsc )
4820 * [24] SingleCharEsc ::= '\' [nrt\|.?*+(){}#x2D#x5B#x5D#x5E]
4821 * [25] catEsc ::= '\p{' charProp '}'
4822 * [26] complEsc ::= '\P{' charProp '}'
4823 * [37] MultiCharEsc ::= '.' | ('\' [sSiIcCdDwW])
4824 */
4825 static void
4835 }
4836 NEXT;
4838 }
4842 }
4843 NEXT;
4846 NEXT;
4850 }
4851 NEXT;
4856 }
4857 NEXT;
4859 NEXT;
4863 }
4864 NEXT;
4870 }
4871 NEXT;
4892 }
4893 }
4905 }
4908 }
4909 NEXT;
4946 }
4947 NEXT;
4953 }
4956 }
4957 }
4959 /**
4960 * xmlFAParseCharRange:
4961 * @ctxt: a regexp parser context
4962 *
4963 * [17] charRange ::= seRange | XmlCharRef | XmlCharIncDash
4964 * [18] seRange ::= charOrEsc '-' charOrEsc
4965 * [20] charOrEsc ::= XmlChar | SingleCharEsc
4966 * [21] XmlChar ::= [^\#x2D#x5B#x5D]
4967 * [22] XmlCharIncDash ::= [^\#x5B#x5D]
4968 */
4969 static void
4978 }
4982 NEXT;
4995 }
5003 }
5004 /*
5005 * Since we are "inside" a range, we can assume ctxt->cur is past
5006 * the start of ctxt->string, and PREV should be safe
5007 */
5011 }
5018 }
5019 NEXT;
5022 NEXT;
5035 }
5042 }
5044 /* TODO check that the values are acceptable character ranges for XML */
5050 }
5052 }
5054 /**
5055 * xmlFAParsePosCharGroup:
5056 * @ctxt: a regexp parser context
5057 *
5058 * [14] posCharGroup ::= ( charRange | charClassEsc )+
5059 */
5060 static void
5067 }
5070 }
5072 /**
5073 * xmlFAParseCharGroup:
5074 * @ctxt: a regexp parser context
5075 *
5076 * [13] charGroup ::= posCharGroup | negCharGroup | charClassSub
5077 * [15] negCharGroup ::= '^' posCharGroup
5078 * [16] charClassSub ::= ( posCharGroup | negCharGroup ) '-' charClassExpr
5079 * [12] charClassExpr ::= '[' charGroup ']'
5080 */
5081 static void
5088 NEXT;
5099 NEXT;
5103 }
5108 }
5109 }
5111 }
5113 /**
5114 * xmlFAParseCharClass:
5115 * @ctxt: a regexp parser context
5116 *
5117 * [11] charClass ::= charClassEsc | charClassExpr
5118 * [12] charClassExpr ::= '[' charGroup ']'
5119 */
5120 static void
5123 NEXT;
5129 NEXT;
5132 }
5135 }
5136 }
5138 /**
5139 * xmlFAParseQuantExact:
5140 * @ctxt: a regexp parser context
5141 *
5142 * [8] QuantExact ::= [0-9]+
5143 *
5144 * Returns 0 if success or -1 in case of error
5145 */
5146 static int
5154 NEXT;
5155 }
5158 }
5160 }
5162 /**
5163 * xmlFAParseQuantifier:
5164 * @ctxt: a regexp parser context
5165 *
5166 * [4] quantifier ::= [?*+] | ( '{' quantity '}' )
5167 * [5] quantity ::= quantRange | quantMin | QuantExact
5168 * [6] quantRange ::= QuantExact ',' QuantExact
5169 * [7] quantMin ::= QuantExact ','
5170 * [8] QuantExact ::= [0-9]+
5171 */
5172 static int
5185 }
5186 NEXT;
5188 }
5192 NEXT;
5197 NEXT;
5206 }
5207 }
5208 }
5210 NEXT;
5213 }
5220 }
5222 }
5224 }
5226 /**
5227 * xmlFAParseAtom:
5228 * @ctxt: a regexp parser context
5229 *
5230 * [9] atom ::= Char | charClass | ( '(' regExp ')' )
5231 */
5232 static int
5254 NEXT;
5255 /*
5256 * this extra Epsilon transition is needed if we count with 0 allowed
5257 * unfortunately this can't be known at that point
5258 */
5268 NEXT;
5271 }
5283 }
5285 }
5287 /**
5288 * xmlFAParsePiece:
5289 * @ctxt: a regexp parser context
5290 *
5291 * [3] piece ::= atom quantifier?
5292 */
5293 static int
5303 }
5306 }
5308 /**
5309 * xmlFAParseBranch:
5310 * @ctxt: a regexp parser context
5311 * @to: optional target to the end of the branch
5312 *
5313 * @to is used to optimize by removing duplicate path in automata
5314 * in expressions like (a|b)(c|d)
5315 *
5316 * [2] branch ::= piece*
5317 */
5318 static int
5320 xmlRegStatePtr previous;
5331 }
5340 }
5341 }
5343 }
5345 /**
5346 * xmlFAParseRegExp:
5347 * @ctxt: a regexp parser context
5348 * @top: is this the top-level expression ?
5349 *
5350 * [1] regExp ::= branch ( '|' branch )*
5351 */
5352 static void
5356 /* if not top start should have been generated by an epsilon trans */
5361 #ifdef DEBUG_REGEXP_GRAPH
5363 #endif
5365 }
5369 }
5372 NEXT;
5376 }
5380 }
5381 }
5383 /************************************************************************
5384 * *
5385 * The basic API *
5386 * *
5387 ************************************************************************/
5389 /**
5390 * xmlRegexpPrint:
5391 * @output: the file for the output debug
5392 * @regexp: the compiled regexp
5393 *
5394 * Print the content of the compiled regular expression
5395 */
5396 void
5406 }
5413 }
5418 }
5423 }
5424 }
5426 /**
5427 * xmlRegexpCompile:
5428 * @regexp: a regular expression string
5429 *
5430 * Parses a regular expression conforming to XML Schemas Part 2 Datatype
5431 * Appendix F and builds an automata suitable for testing strings against
5432 * that regular expression
5433 *
5434 * Returns the compiled expression or NULL in case of error
5435 */
5436 xmlRegexpPtr
5438 xmlRegexpPtr ret;
5439 xmlRegParserCtxtPtr ctxt;
5445 /* initialize the parser */
5450 /* parse the expression building an automata */
5454 }
5458 }
5463 /* remove the Epsilon except for counted transitions */
5470 }
5474 }
5476 /**
5477 * xmlRegexpExec:
5478 * @comp: the compiled regular expression
5479 * @content: the value to check against the regular expression
5480 *
5481 * Check if the regular expression generates the value
5482 *
5483 * Returns 1 if it matches, 0 if not and a negative value in case of error
5484 */
5485 int
5490 }
5492 /**
5493 * xmlRegexpIsDeterminist:
5494 * @comp: the compiled regular expression
5495 *
5496 * Check if the regular expression is determinist
5497 *
5498 * Returns 1 if it yes, 0 if not and a negative value in case of error
5499 */
5500 int
5502 xmlAutomataPtr am;
5517 }
5530 }
5532 /**
5533 * xmlRegFreeRegexp:
5534 * @regexp: the regexp
5535 *
5536 * Free a regexp
5537 */
5538 void
5550 }
5555 }
5566 }
5569 }
5571 #ifdef LIBXML_AUTOMATA_ENABLED
5572 /************************************************************************
5573 * *
5574 * The Automata interface *
5575 * *
5576 ************************************************************************/
5578 /**
5579 * xmlNewAutomata:
5580 *
5581 * Create a new automata
5582 *
5583 * Returns the new object or NULL in case of failure
5584 */
5585 xmlAutomataPtr
5587 xmlAutomataPtr ctxt;
5593 /* initialize the parser */
5599 }
5605 }
5609 }
5611 /**
5612 * xmlFreeAutomata:
5613 * @am: an automata
5614 *
5615 * Free an automata
5616 */
5617 void
5622 }
5624 /**
5625 * xmlAutomataSetFlags:
5626 * @am: an automata
5627 * @flags: a set of internal flags
5628 *
5629 * Set some flags on the automata
5630 */
5631 void
5636 }
5638 /**
5639 * xmlAutomataGetInitState:
5640 * @am: an automata
5641 *
5642 * Initial state lookup
5643 *
5644 * Returns the initial state of the automata
5645 */
5646 xmlAutomataStatePtr
5651 }
5653 /**
5654 * xmlAutomataSetFinalState:
5655 * @am: an automata
5656 * @state: a state in this automata
5657 *
5658 * Makes that state a final state
5659 *
5660 * Returns 0 or -1 in case of error
5661 */
5662 int
5668 }
5670 /**
5671 * xmlAutomataNewTransition:
5672 * @am: an automata
5673 * @from: the starting point of the transition
5674 * @to: the target point of the transition or NULL
5675 * @token: the input string associated to that transition
5676 * @data: data passed to the callback function if the transition is activated
5677 *
5678 * If @to is NULL, this creates first a new target state in the automata
5679 * and then adds a transition from the @from state to the target state
5680 * activated by the value of @token
5681 *
5682 * Returns the target state or NULL in case of error
5683 */
5684 xmlAutomataStatePtr
5688 xmlRegAtomPtr atom;
5703 }
5707 }
5709 /**
5710 * xmlAutomataNewTransition2:
5711 * @am: an automata
5712 * @from: the starting point of the transition
5713 * @to: the target point of the transition or NULL
5714 * @token: the first input string associated to that transition
5715 * @token2: the second input string associated to that transition
5716 * @data: data passed to the callback function if the transition is activated
5717 *
5718 * If @to is NULL, this creates first a new target state in the automata
5719 * and then adds a transition from the @from state to the target state
5720 * activated by the value of @token
5721 *
5722 * Returns the target state or NULL in case of error
5723 */
5724 xmlAutomataStatePtr
5728 xmlRegAtomPtr atom;
5749 }
5756 }
5761 }
5765 }
5767 /**
5768 * xmlAutomataNewNegTrans:
5769 * @am: an automata
5770 * @from: the starting point of the transition
5771 * @to: the target point of the transition or NULL
5772 * @token: the first input string associated to that transition
5773 * @token2: the second input string associated to that transition
5774 * @data: data passed to the callback function if the transition is activated
5775 *
5776 * If @to is NULL, this creates first a new target state in the automata
5777 * and then adds a transition from the @from state to the target state
5778 * activated by any value except (@token,@token2)
5779 * Note that if @token2 is not NULL, then (X, NULL) won't match to follow
5780 # the semantic of XSD ##other
5781 *
5782 * Returns the target state or NULL in case of error
5783 */
5784 xmlAutomataStatePtr
5788 xmlRegAtomPtr atom;
5811 }
5818 }
5826 }
5831 }
5833 /**
5834 * xmlAutomataNewCountTrans2:
5835 * @am: an automata
5836 * @from: the starting point of the transition
5837 * @to: the target point of the transition or NULL
5838 * @token: the input string associated to that transition
5839 * @token2: the second input string associated to that transition
5840 * @min: the minimum successive occurences of token
5841 * @max: the maximum successive occurences of token
5842 * @data: data associated to the transition
5843 *
5844 * If @to is NULL, this creates first a new target state in the automata
5845 * and then adds a transition from the @from state to the target state
5846 * activated by a succession of input of value @token and @token2 and
5847 * whose number is between @min and @max
5848 *
5849 * Returns the target state or NULL in case of error
5850 */
5851 xmlAutomataStatePtr
5856 xmlRegAtomPtr atom;
5881 }
5888 }
5892 else
5896 /*
5897 * associate a counter to the transition.
5898 */
5903 /* xmlFAGenerateTransitions(am, from, to, atom); */
5907 }
5919 }
5921 /**
5922 * xmlAutomataNewCountTrans:
5923 * @am: an automata
5924 * @from: the starting point of the transition
5925 * @to: the target point of the transition or NULL
5926 * @token: the input string associated to that transition
5927 * @min: the minimum successive occurences of token
5928 * @max: the maximum successive occurences of token
5929 * @data: data associated to the transition
5930 *
5931 * If @to is NULL, this creates first a new target state in the automata
5932 * and then adds a transition from the @from state to the target state
5933 * activated by a succession of input of value @token and whose number
5934 * is between @min and @max
5935 *
5936 * Returns the target state or NULL in case of error
5937 */
5938 xmlAutomataStatePtr
5942 xmlRegAtomPtr atom;
5958 else
5962 /*
5963 * associate a counter to the transition.
5964 */
5969 /* xmlFAGenerateTransitions(am, from, to, atom); */
5973 }
5985 }
5987 /**
5988 * xmlAutomataNewOnceTrans2:
5989 * @am: an automata
5990 * @from: the starting point of the transition
5991 * @to: the target point of the transition or NULL
5992 * @token: the input string associated to that transition
5993 * @token2: the second input string associated to that transition
5994 * @min: the minimum successive occurences of token
5995 * @max: the maximum successive occurences of token
5996 * @data: data associated to the transition
5997 *
5998 * If @to is NULL, this creates first a new target state in the automata
5999 * and then adds a transition from the @from state to the target state
6000 * activated by a succession of input of value @token and @token2 and whose
6001 * number is between @min and @max, moreover that transition can only be
6002 * crossed once.
6003 *
6004 * Returns the target state or NULL in case of error
6005 */
6006 xmlAutomataStatePtr
6011 xmlRegAtomPtr atom;
6036 }
6043 }
6048 /*
6049 * associate a counter to the transition.
6050 */
6055 /* xmlFAGenerateTransitions(am, from, to, atom); */
6059 }
6064 }
6068 /**
6069 * xmlAutomataNewOnceTrans:
6070 * @am: an automata
6071 * @from: the starting point of the transition
6072 * @to: the target point of the transition or NULL
6073 * @token: the input string associated to that transition
6074 * @min: the minimum successive occurences of token
6075 * @max: the maximum successive occurences of token
6076 * @data: data associated to the transition
6077 *
6078 * If @to is NULL, this creates first a new target state in the automata
6079 * and then adds a transition from the @from state to the target state
6080 * activated by a succession of input of value @token and whose number
6081 * is between @min and @max, moreover that transition can only be crossed
6082 * once.
6083 *
6084 * Returns the target state or NULL in case of error
6085 */
6086 xmlAutomataStatePtr
6090 xmlRegAtomPtr atom;
6107 /*
6108 * associate a counter to the transition.
6109 */
6114 /* xmlFAGenerateTransitions(am, from, to, atom); */
6118 }
6123 }
6125 /**
6126 * xmlAutomataNewState:
6127 * @am: an automata
6128 *
6129 * Create a new disconnected state in the automata
6130 *
6131 * Returns the new state or NULL in case of error
6132 */
6133 xmlAutomataStatePtr
6135 xmlAutomataStatePtr to;
6142 }
6144 /**
6145 * xmlAutomataNewEpsilon:
6146 * @am: an automata
6147 * @from: the starting point of the transition
6148 * @to: the target point of the transition or NULL
6149 *
6150 * If @to is NULL, this creates first a new target state in the automata
6151 * and then adds an epsilon transition from the @from state to the
6152 * target state
6153 *
6154 * Returns the target state or NULL in case of error
6155 */
6156 xmlAutomataStatePtr
6158 xmlAutomataStatePtr to) {
6165 }
6167 /**
6168 * xmlAutomataNewAllTrans:
6169 * @am: an automata
6170 * @from: the starting point of the transition
6171 * @to: the target point of the transition or NULL
6172 * @lax: allow to transition if not all all transitions have been activated
6173 *
6174 * If @to is NULL, this creates first a new target state in the automata
6175 * and then adds a an ALL transition from the @from state to the
6176 * target state. That transition is an epsilon transition allowed only when
6177 * all transitions from the @from node have been activated.
6178 *
6179 * Returns the target state or NULL in case of error
6180 */
6181 xmlAutomataStatePtr
6190 }
6192 /**
6193 * xmlAutomataNewCounter:
6194 * @am: an automata
6195 * @min: the minimal value on the counter
6196 * @max: the maximal value on the counter
6197 *
6198 * Create a new counter
6199 *
6200 * Returns the counter number or -1 in case of error
6201 */
6202 int
6215 }
6217 /**
6218 * xmlAutomataNewCountedTrans:
6219 * @am: an automata
6220 * @from: the starting point of the transition
6221 * @to: the target point of the transition or NULL
6222 * @counter: the counter associated to that transition
6223 *
6224 * If @to is NULL, this creates first a new target state in the automata
6225 * and then adds an epsilon transition from the @from state to the target state
6226 * which will increment the counter provided
6227 *
6228 * Returns the target state or NULL in case of error
6229 */
6230 xmlAutomataStatePtr
6239 }
6241 /**
6242 * xmlAutomataNewCounterTrans:
6243 * @am: an automata
6244 * @from: the starting point of the transition
6245 * @to: the target point of the transition or NULL
6246 * @counter: the counter associated to that transition
6247 *
6248 * If @to is NULL, this creates first a new target state in the automata
6249 * and then adds an epsilon transition from the @from state to the target state
6250 * which will be allowed only if the counter is within the right range.
6251 *
6252 * Returns the target state or NULL in case of error
6253 */
6254 xmlAutomataStatePtr
6263 }
6265 /**
6266 * xmlAutomataCompile:
6267 * @am: an automata
6268 *
6269 * Compile the automata into a Reg Exp ready for being executed.
6270 * The automata should be free after this point.
6271 *
6272 * Returns the compiled regexp or NULL in case of error
6273 */
6274 xmlRegexpPtr
6276 xmlRegexpPtr ret;
6280 /* xmlFAComputesDeterminism(am); */
6284 }
6286 /**
6287 * xmlAutomataIsDeterminist:
6288 * @am: an automata
6289 *
6290 * Checks if an automata is determinist.
6291 *
6292 * Returns 1 if true, 0 if not, and -1 in case of error
6293 */
6294 int
6303 }
6306 #ifdef LIBXML_EXPR_ENABLED
6307 /************************************************************************
6308 * *
6309 * Formal Expression handling code *
6310 * *
6311 ************************************************************************/
6312 /************************************************************************
6313 * *
6314 * Expression handling context *
6315 * *
6316 ************************************************************************/
6319 xmlDictPtr dict;
6329 };
6331 /**
6332 * xmlExpNewCtxt:
6333 * @maxNodes: the maximum number of nodes
6334 * @dict: optional dictionnary to use internally
6335 *
6336 * Creates a new context for manipulating expressions
6337 *
6338 * Returns the context or NULL in case of error
6339 */
6340 xmlExpCtxtPtr
6342 xmlExpCtxtPtr ret;
6359 }
6367 }
6371 }
6373 }
6375 /**
6376 * xmlExpFreeCtxt:
6377 * @ctxt: an expression context
6378 *
6379 * Free an expression context
6380 */
6381 void
6389 }
6391 /************************************************************************
6392 * *
6393 * Structure associated to an expression node *
6394 * *
6395 ************************************************************************/
6396 #define MAX_NODES 10000
6398 /* #define DEBUG_DERIV */
6400 /*
6401 * TODO:
6402 * - Wildcards
6403 * - public API for creation
6404 *
6405 * Started
6406 * - regression testing
6407 *
6408 * Done
6409 * - split into module and test tool
6410 * - memleaks
6411 */
6417 #define IS_NILLABLE(node) ((node)->info & XML_EXP_NILABLE)
6425 xmlExpNodePtr exp_left;
6433 xmlExpNodePtr f_right;
6437 };
6439 #define exp_min field.count.f_min
6440 #define exp_max field.count.f_max
6441 /* #define exp_left field.children.f_left */
6442 #define exp_right field.children.f_right
6443 #define exp_str field.f_str
6448 };
6452 };
6455 /************************************************************************
6456 * *
6457 * The custom hash table for unicity and canonicalization *
6458 * of sub-expressions pointers *
6459 * *
6460 ************************************************************************/
6461 /*
6462 * xmlExpHashNameComputeKey:
6463 * Calculate the hash key for a token
6464 */
6465 static unsigned short
6474 }
6475 }
6477 }
6479 /*
6480 * xmlExpHashComputeKey:
6481 * Calculate the hash key for a compound expression
6482 */
6483 static unsigned short
6485 xmlExpNodePtr right) {
6509 }
6511 }
6514 static xmlExpNodePtr
6516 xmlExpNodePtr ret;
6529 }
6531 /**
6532 * xmlExpHashGetEntry:
6533 * @table: the hash table
6534 *
6535 * Get the unique entry from the hash table. The entry is created if
6536 * needed. @left and @right are consumed, i.e. their ref count will
6537 * be decremented by the operation.
6538 *
6539 * Returns the pointer or NULL in case of error
6540 */
6541 static xmlExpNodePtr
6546 xmlExpNodePtr entry;
6547 xmlExpNodePtr insert;
6552 /*
6553 * Check for duplicate and insertion location.
6554 */
6558 /* COUNT reduction rule 1 */
6559 /* a{1} -> a */
6563 }
6567 }
6568 }
6572 }
6575 else
6579 /* Forbid reduction rules */
6583 }
6587 }
6589 /* OR reduction rule 1 */
6590 /* a | a reduced to a */
6594 }
6595 /* OR canonicalization rule 1 */
6596 /* linearize (a | b) | c into a | (b | c) */
6601 }
6602 /* OR reduction rule 2 */
6603 /* a | (a | b) and b | (a | b) are reduced to a | b */
6609 }
6610 }
6611 /* OR canonicalization rule 2 */
6612 /* linearize (a | b) | c into a | (b | c) */
6614 xmlExpNodePtr tmp;
6616 /* OR canonicalization rule 2 */
6622 }
6632 }
6634 /* Ordering in the tree */
6635 /* C | (A | B) -> A | (B | C) */
6637 xmlExpNodePtr tmp;
6646 }
6647 /* Ordering in the tree */
6648 /* B | (A | C) -> A | (B | C) */
6650 xmlExpNodePtr tmp;
6659 }
6660 }
6661 /* we know both types are != XML_EXP_OR here */
6666 }
6669 /* Forbid reduction rules */
6673 }
6677 }
6678 /* Empty reduction rules */
6681 }
6684 }
6699 }
6706 }
6713 }
6714 }
6715 }
6716 }
6733 else
6746 else
6754 else
6756 }
6757 }
6766 }
6768 /**
6769 * xmlExpFree:
6770 * @ctxt: the expression context
6771 * @exp: the expression
6772 *
6773 * Dereference the expression
6774 */
6775 void
6783 /* Unlink it first from the hash table */
6788 xmlExpNodePtr tmp;
6795 }
6797 }
6798 }
6805 }
6808 }
6809 }
6811 /**
6812 * xmlExpRef:
6813 * @exp: the expression
6814 *
6815 * Increase the reference count of the expression
6816 */
6817 void
6821 }
6823 /**
6824 * xmlExpNewAtom:
6825 * @ctxt: the expression context
6826 * @name: the atom name
6827 * @len: the atom name lenght in byte (or -1);
6828 *
6829 * Get the atom associated to this name from that context
6830 *
6831 * Returns the node or NULL in case of error
6832 */
6833 xmlExpNodePtr
6841 }
6843 /**
6844 * xmlExpNewOr:
6845 * @ctxt: the expression context
6846 * @left: left expression
6847 * @right: right expression
6848 *
6849 * Get the atom associated to the choice @left | @right
6850 * Note that @left and @right are consumed in the operation, to keep
6851 * an handle on them use xmlExpRef() and use xmlExpFree() to release them,
6852 * this is true even in case of failure (unless ctxt == NULL).
6853 *
6854 * Returns the node or NULL in case of error
6855 */
6856 xmlExpNodePtr
6864 }
6866 }
6868 /**
6869 * xmlExpNewSeq:
6870 * @ctxt: the expression context
6871 * @left: left expression
6872 * @right: right expression
6873 *
6874 * Get the atom associated to the sequence @left , @right
6875 * Note that @left and @right are consumed in the operation, to keep
6876 * an handle on them use xmlExpRef() and use xmlExpFree() to release them,
6877 * this is true even in case of failure (unless ctxt == NULL).
6878 *
6879 * Returns the node or NULL in case of error
6880 */
6881 xmlExpNodePtr
6889 }
6891 }
6893 /**
6894 * xmlExpNewRange:
6895 * @ctxt: the expression context
6896 * @subset: the expression to be repeated
6897 * @min: the lower bound for the repetition
6898 * @max: the upper bound for the repetition, -1 means infinite
6899 *
6900 * Get the atom associated to the range (@subset){@min, @max}
6901 * Note that @subset is consumed in the operation, to keep
6902 * an handle on it use xmlExpRef() and use xmlExpFree() to release it,
6903 * this is true even in case of failure (unless ctxt == NULL).
6904 *
6905 * Returns the node or NULL in case of error
6906 */
6907 xmlExpNodePtr
6915 }
6918 }
6920 /************************************************************************
6921 * *
6922 * Public API for operations on expressions *
6923 * *
6924 ************************************************************************/
6926 static int
6930 tail:
6955 }
6957 }
6959 /**
6960 * xmlExpGetLanguage:
6961 * @ctxt: the expression context
6962 * @exp: the expression
6963 * @langList: where to store the tokens
6964 * @len: the allocated lenght of @list
6965 *
6966 * Find all the strings used in @exp and store them in @list
6967 *
6968 * Returns the number of unique strings found, -1 in case of errors and
6969 * -2 if there is more than @len strings
6970 */
6971 int
6977 }
6979 static int
6983 tail:
7010 }
7021 }
7023 }
7025 /**
7026 * xmlExpGetStart:
7027 * @ctxt: the expression context
7028 * @exp: the expression
7029 * @tokList: where to store the tokens
7030 * @len: the allocated lenght of @list
7031 *
7032 * Find all the strings that appears at the start of the languages
7033 * accepted by @exp and store them in @list. E.g. for (a, b) | c
7034 * it will return the list [a, c]
7035 *
7036 * Returns the number of unique strings found, -1 in case of errors and
7037 * -2 if there is more than @len strings
7038 */
7039 int
7045 }
7047 /**
7048 * xmlExpIsNillable:
7049 * @exp: the expression
7050 *
7051 * Finds if the expression is nillable, i.e. if it accepts the empty sequqnce
7052 *
7053 * Returns 1 if nillable, 0 if not and -1 in case of error
7054 */
7055 int
7060 }
7062 static xmlExpNodePtr
7064 {
7065 xmlExpNodePtr ret;
7074 #ifdef DEBUG_DERIV
7076 #endif
7079 #ifdef DEBUG_DERIV
7081 #endif
7082 /* TODO wildcards here */
7084 }
7087 xmlExpNodePtr tmp;
7089 #ifdef DEBUG_DERIV
7091 #endif
7095 }
7100 }
7104 }
7106 #ifdef DEBUG_DERIV
7108 #endif
7114 #ifdef DEBUG_DERIV
7116 #endif
7118 }
7120 #ifdef DEBUG_DERIV
7122 #endif
7126 }
7130 xmlExpNodePtr tmp;
7138 #ifdef DEBUG_DERIV
7140 #endif
7142 }
7147 else
7151 else
7157 #ifdef DEBUG_DERIV
7159 #endif
7161 }
7162 #ifdef DEBUG_DERIV
7164 #endif
7167 }
7168 }
7170 }
7172 /**
7173 * xmlExpStringDerive:
7174 * @ctxt: the expression context
7175 * @exp: the expression
7176 * @str: the string
7177 * @len: the string len in bytes if available
7178 *
7179 * Do one step of Brzozowski derivation of the expression @exp with
7180 * respect to the input string
7181 *
7182 * Returns the resulting expression or NULL in case of internal error
7183 */
7184 xmlExpNodePtr
7191 }
7192 /*
7193 * check the string is in the dictionnary, if yes use an interned
7194 * copy, otherwise we know it's not an acceptable input
7195 */
7199 }
7201 }
7203 static int
7212 }
7213 #if 0
7216 #endif
7218 }
7221 xmlExpNodePtr sub);
7222 /**
7223 * xmlExpDivide:
7224 * @ctxt: the expressions context
7225 * @exp: the englobing expression
7226 * @sub: the subexpression
7227 * @mult: the multiple expression
7228 * @remain: the remain from the derivation of the multiple
7229 *
7230 * Check if exp is a multiple of sub, i.e. if there is a finite number n
7231 * so that sub{n} subsume exp
7232 *
7233 * Returns the multiple value if successful, 0 if it is not a multiple
7234 * and -1 in case of internel error.
7235 */
7237 static int
7254 }
7258 }
7263 }
7267 else
7271 else
7273 #ifdef DEBUG_DERIV
7275 #endif
7277 }
7280 }
7281 #ifdef DEBUG_DERIV
7283 #endif
7285 }
7287 /**
7288 * xmlExpExpDeriveInt:
7289 * @ctxt: the expressions context
7290 * @exp: the englobing expression
7291 * @sub: the subexpression
7292 *
7293 * Try to do a step of Brzozowski derivation but at a higher level
7294 * the input being a subexpression.
7295 *
7296 * Returns the resulting expression or NULL in case of internal error
7297 */
7298 static xmlExpNodePtr
7304 /*
7305 * In case of equality and if the expression can only consume a finite
7306 * amount, then the derivation is empty
7307 */
7309 #ifdef DEBUG_DERIV
7311 #endif
7313 }
7314 /*
7315 * decompose sub sequence first
7316 */
7318 #ifdef DEBUG_DERIV
7320 #endif
7323 }
7325 #ifdef DEBUG_DERIV
7327 #endif
7336 }
7338 #ifdef DEBUG_DERIV
7340 #endif
7350 }
7352 }
7354 #ifdef DEBUG_DERIV
7356 #endif
7358 }
7363 #ifdef DEBUG_DERIV
7365 #endif
7368 #ifdef DEBUG_DERIV
7370 #endif
7374 /* TODO: handle wildcards */
7376 #ifdef DEBUG_DERIV
7378 #endif
7380 }
7381 #ifdef DEBUG_DERIV
7383 #endif
7385 }
7389 /* TODO: handle wildcards */
7391 #ifdef DEBUG_DERIV
7393 #endif
7395 }
7396 #ifdef DEBUG_DERIV
7398 #endif
7400 }
7401 #ifdef DEBUG_DERIV
7403 #endif
7406 /* try to get the sequence consumed only if possible */
7408 /* See if the sequence can be consumed directly */
7409 #ifdef DEBUG_DERIV
7411 #endif
7414 #ifdef DEBUG_DERIV
7416 #endif
7417 /*
7418 * TODO: assumption here that we are determinist
7419 * i.e. we won't get to a nillable exp left
7420 * subset which could be matched by the right
7421 * part too.
7422 * e.g.: (a | b)+,(a | c) and 'a+,a'
7423 */
7427 }
7428 #ifdef DEBUG_DERIV
7431 #endif
7432 }
7433 /* Try instead to decompose */
7437 #ifdef DEBUG_DERIV
7439 #endif
7444 #ifdef DEBUG_DERIV
7446 #endif
7449 else
7453 else
7467 }
7472 }
7473 }
7474 /* we made no progress on structured operations */
7477 #ifdef DEBUG_DERIV
7479 #endif
7487 }
7493 /*
7494 * Try to see if the loop is completely subsumed
7495 */
7502 #ifdef DEBUG_DERIV
7504 #endif
7508 #ifdef DEBUG_DERIV
7510 #endif
7512 }
7518 else
7521 #ifdef DEBUG_DERIV
7523 #endif
7526 }
7529 #ifdef DEBUG_DERIV
7531 #endif
7538 }
7541 #ifdef DEBUG_DERIV
7543 #endif
7546 }
7549 else
7552 }
7553 }
7555 /*
7556 * TODO: loop here to try to grow if working on finite
7557 * blocks.
7558 */
7559 #ifdef DEBUG_DERIV
7561 #endif
7567 #ifdef DEBUG_DERIV
7569 #endif
7573 #ifdef DEBUG_DERIV
7575 #endif
7578 }
7580 #ifdef DEBUG_DERIV
7582 #endif
7588 }
7591 #ifdef DEBUG_DERIV
7593 #endif
7600 }
7603 #ifdef DEBUG_DERIV
7605 #endif
7608 }
7611 else
7614 }
7615 }
7616 #ifdef DEBUG_DERIV
7618 #endif
7624 }
7628 }
7633 #ifdef DEBUG_DERIV
7635 #endif
7637 }
7640 else
7644 else
7647 #ifdef DEBUG_DERIV
7649 #endif
7658 }
7659 }
7661 #ifdef DEBUG_DERIV
7663 #endif
7667 else
7671 /*
7672 * here the structured derivation made no progress so
7673 * we use the default token based derivation to force one more step
7674 */
7682 }
7684 /*
7685 * collect all the strings accepted by the subexpression on input
7686 */
7695 }
7699 }
7706 }
7713 }
7722 }
7731 }
7732 }
7733 }
7736 }
7738 /**
7739 * xmlExpExpDerive:
7740 * @ctxt: the expressions context
7741 * @exp: the englobing expression
7742 * @sub: the subexpression
7743 *
7744 * Evaluates the expression resulting from @exp consuming a sub expression @sub
7745 * Based on algebraic derivation and sometimes direct Brzozowski derivation
7746 * it usually tatkes less than linear time and can handle expressions generating
7747 * infinite languages.
7748 *
7749 * Returns the resulting expression or NULL in case of internal error, the
7750 * result must be freed
7751 */
7752 xmlExpNodePtr
7757 /*
7758 * O(1) speedups
7759 */
7761 #ifdef DEBUG_DERIV
7763 #endif
7765 }
7767 #ifdef DEBUG_DERIV
7769 #endif
7771 }
7773 }
7775 /**
7776 * xmlExpSubsume:
7777 * @ctxt: the expressions context
7778 * @exp: the englobing expression
7779 * @sub: the subexpression
7780 *
7781 * Check whether @exp accepts all the languages accexpted by @sub
7782 * the input being a subexpression.
7783 *
7784 * Returns 1 if true 0 if false and -1 in case of failure.
7785 */
7786 int
7788 xmlExpNodePtr tmp;
7793 /*
7794 * TODO: speedup by checking the language of sub is a subset of the
7795 * language of exp
7796 */
7797 /*
7798 * O(1) speedups
7799 */
7801 #ifdef DEBUG_DERIV
7803 #endif
7805 }
7807 #ifdef DEBUG_DERIV
7809 #endif
7811 }
7813 #ifdef DEBUG_DERIV
7816 #endif
7826 }
7829 }
7831 /************************************************************************
7832 * *
7833 * Parsing expression *
7834 * *
7835 ************************************************************************/
7839 #undef CUR
7840 #define CUR (*ctxt->cur)
7841 #undef NEXT
7842 #define NEXT ctxt->cur++;
7843 #undef IS_BLANK
7845 #define SKIP_BLANKS while (IS_BLANK(*ctxt->cur)) ctxt->cur++;
7847 static int
7851 SKIP_BLANKS
7853 NEXT
7855 }
7860 NEXT
7861 }
7863 }
7865 static xmlExpNodePtr
7868 xmlExpNodePtr ret;
7871 SKIP_BLANKS
7874 NEXT
7876 SKIP_BLANKS
7881 }
7882 NEXT;
7883 SKIP_BLANKS
7885 }
7889 NEXT;
7896 SKIP_BLANKS
7897 parse_quantifier:
7901 NEXT
7906 }
7907 SKIP_BLANKS
7909 NEXT
7911 SKIP_BLANKS
7917 }
7918 NEXT
7921 SKIP_BLANKS
7923 NEXT
7926 SKIP_BLANKS
7928 NEXT
7931 SKIP_BLANKS
7933 NEXT
7936 SKIP_BLANKS
7937 }
7939 }
7942 static xmlExpNodePtr
7947 SKIP_BLANKS
7949 NEXT
7954 }
7958 }
7960 }
7962 static xmlExpNodePtr
7967 SKIP_BLANKS
7969 NEXT
7974 }
7978 }
7980 }
7982 /**
7983 * xmlExpParse:
7984 * @ctxt: the expressions context
7985 * @expr: the 0 terminated string
7986 *
7987 * Minimal parser for regexps, it understand the following constructs
7988 * - string terminals
7989 * - choice operator |
7990 * - sequence operator ,
7991 * - subexpressions (...)
7992 * - usual cardinality operators + * and ?
7993 * - finite sequences { min, max }
7994 * - infinite sequences { min, * }
7995 * There is minimal checkings made especially no checking on strings values
7996 *
7997 * Returns a new expression or NULL in case of failure
7998 */
7999 xmlExpNodePtr
8001 xmlExpNodePtr ret;
8007 SKIP_BLANKS
8011 }
8013 }
8015 static void
8017 xmlExpNodePtr c;
8035 else
8041 else
8048 else
8054 else
8063 else
8080 }
8084 }
8087 }
8090 }
8091 /**
8092 * xmlExpDump:
8093 * @buf: a buffer to receive the output
8094 * @expr: the compiled expression
8095 *
8096 * Serialize the expression as compiled to the buffer
8097 */
8098 void
8103 }
8105 /**
8106 * xmlExpMaxToken:
8107 * @expr: a compiled expression
8108 *
8109 * Indicate the maximum number of input a expression can accept
8110 *
8111 * Returns the maximum length or -1 in case of error
8112 */
8113 int
8118 }
8120 /**
8121 * xmlExpCtxtNbNodes:
8122 * @ctxt: an expression context
8123 *
8124 * Debugging facility provides the number of allocated nodes at a that point
8125 *
8126 * Returns the number of nodes in use or -1 in case of error
8127 */
8128 int
8133 }
8135 /**
8136 * xmlExpCtxtNbCons:
8137 * @ctxt: an expression context
8138 *
8139 * Debugging facility provides the number of allocated nodes over lifetime
8140 *
8141 * Returns the number of nodes ever allocated or -1 in case of error
8142 */
8143 int
8148 }
8151 #define bottom_xmlregexp