| blob | 3e912ab92e803abc3e48215f1479b97a296256b1 |
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 #ifdef ERROR
48 #undef ERROR
49 #endif
50 #define ERROR(str) \
51 ctxt->error = XML_REGEXP_COMPILE_ERROR; \
52 xmlRegexpErrCompile(ctxt, str);
53 #define NEXT ctxt->cur++
54 #define CUR (*(ctxt->cur))
55 #define NXT(index) (ctxt->cur[index])
57 #define CUR_SCHAR(s, l) xmlStringCurrentChar(NULL, s, &l)
58 #define NEXTL(l) ctxt->cur += l;
60 /*
61 * Need PREV to check on a '-' within a Character Group. May only be used
62 * when it's guaranteed that cur is not at the beginning of ctxt->string!
63 */
64 #define PREV (ctxt->cur[-1])
66 /**
67 * TODO:
68 *
69 * macro to flag unimplemented blocks
70 */
71 #define TODO \
72 xmlGenericError(xmlGenericErrorContext, \
74 __FILE__, __LINE__);
76 /************************************************************************
77 * *
78 * Datatypes and structures *
79 * *
80 ************************************************************************/
82 /*
83 * Note: the order of the enums below is significant, do not shuffle
84 */
87 XML_REGEXP_CHARVAL,
88 XML_REGEXP_RANGES,
90 XML_REGEXP_STRING,
103 XML_REGEXP_LETTER_UPPERCASE,
104 XML_REGEXP_LETTER_LOWERCASE,
105 XML_REGEXP_LETTER_TITLECASE,
106 XML_REGEXP_LETTER_MODIFIER,
107 XML_REGEXP_LETTER_OTHERS,
108 XML_REGEXP_MARK,
109 XML_REGEXP_MARK_NONSPACING,
110 XML_REGEXP_MARK_SPACECOMBINING,
111 XML_REGEXP_MARK_ENCLOSING,
112 XML_REGEXP_NUMBER,
113 XML_REGEXP_NUMBER_DECIMAL,
114 XML_REGEXP_NUMBER_LETTER,
115 XML_REGEXP_NUMBER_OTHERS,
116 XML_REGEXP_PUNCT,
117 XML_REGEXP_PUNCT_CONNECTOR,
118 XML_REGEXP_PUNCT_DASH,
119 XML_REGEXP_PUNCT_OPEN,
120 XML_REGEXP_PUNCT_CLOSE,
121 XML_REGEXP_PUNCT_INITQUOTE,
122 XML_REGEXP_PUNCT_FINQUOTE,
123 XML_REGEXP_PUNCT_OTHERS,
124 XML_REGEXP_SEPAR,
125 XML_REGEXP_SEPAR_SPACE,
126 XML_REGEXP_SEPAR_LINE,
127 XML_REGEXP_SEPAR_PARA,
128 XML_REGEXP_SYMBOL,
129 XML_REGEXP_SYMBOL_MATH,
130 XML_REGEXP_SYMBOL_CURRENCY,
131 XML_REGEXP_SYMBOL_MODIFIER,
132 XML_REGEXP_SYMBOL_OTHERS,
133 XML_REGEXP_OTHER,
134 XML_REGEXP_OTHER_CONTROL,
135 XML_REGEXP_OTHER_FORMAT,
136 XML_REGEXP_OTHER_PRIVATE,
137 XML_REGEXP_OTHER_NA,
138 XML_REGEXP_BLOCK_NAME
143 XML_REGEXP_QUANT_ONCE,
144 XML_REGEXP_QUANT_OPT,
145 XML_REGEXP_QUANT_MULT,
146 XML_REGEXP_QUANT_PLUS,
147 XML_REGEXP_QUANT_ONCEONLY,
148 XML_REGEXP_QUANT_ALL,
149 XML_REGEXP_QUANT_RANGE
154 XML_REGEXP_FINAL_STATE,
155 XML_REGEXP_TRANS_STATE,
156 XML_REGEXP_SINK_STATE,
157 XML_REGEXP_UNREACH_STATE
162 XML_REGEXP_MARK_START,
163 XML_REGEXP_MARK_VISITED
171 xmlRegAtomType type;
175 };
185 xmlRegAtomType type;
186 xmlRegQuantType quant;
194 xmlRegStatePtr start;
195 xmlRegStatePtr start0;
196 xmlRegStatePtr stop;
201 };
209 };
215 xmlRegAtomPtr atom;
220 };
223 xmlRegStateType type;
224 xmlRegMarkedType mark;
225 xmlRegMarkedType markd;
226 xmlRegMarkedType reached;
231 /* knowing states ponting to us can speed things up */
235 };
240 #define AM_AUTOMATA_RNG 1
249 xmlRegStatePtr start;
250 xmlRegStatePtr end;
251 xmlRegStatePtr state;
253 xmlRegAtomPtr atom;
270 };
282 /*
283 * That's the compact form for determinists automatas
284 */
290 };
300 };
308 };
314 xmlRegExecCallbacks callback;
321 /*
322 * A stack of rollback states
323 */
328 /*
329 * The state of the automata if any
330 */
333 /*
334 * The input stack
335 */
343 /*
344 * error handling
345 */
351 };
353 #define REGEXP_ALL_COUNTER 0x123456
354 #define REGEXP_ALL_LAX_COUNTER 0x123457
366 /************************************************************************
367 * *
368 * Regexp memory error handler *
369 * *
370 ************************************************************************/
371 /**
372 * xmlRegexpErrMemory:
373 * @extra: extra information
374 *
375 * Handle an out of memory condition
376 */
377 static void
379 {
384 }
389 }
391 /**
392 * xmlRegexpErrCompile:
393 * @extra: extra information
394 *
395 * Handle a compilation failure
396 */
397 static void
399 {
407 }
412 }
414 /************************************************************************
415 * *
416 * Allocation/Deallocation *
417 * *
418 ************************************************************************/
421 /**
422 * xmlRegEpxFromParse:
423 * @ctxt: the parser context used to build it
424 *
425 * Allocate a new regexp and fill it with the result from the parser
426 *
427 * Returns the new regexp or NULL in case of error
428 */
429 static xmlRegexpPtr
431 xmlRegexpPtr ret;
437 }
450 }
466 /*
467 * Switch to a compact representation
468 * 1/ counting the effective number of states left
469 * 2/ counting the unique number of atoms, and check that
470 * they are all of the string type
471 * 3/ build a table state x atom for the transitions
472 */
479 }
483 nbstates++;
486 }
487 }
488 #ifdef DEBUG_COMPACTION
490 #endif
497 }
505 }
514 }
515 }
527 }
528 nbatoms++;
529 }
538 }
539 }
540 #ifdef DEBUG_COMPACTION
542 #endif
551 }
554 /*
555 * Allocate the transition table. The first entry for each
556 * state corresponds to the state type.
557 */
562 xmlRegStatePtr state;
563 xmlRegTransPtr trans;
586 }
587 }
589 /*
590 * if the same atom can generate transitions to 2 different
591 * states then it means the automata is not determinist and
592 * the compact form can't be used !
593 */
598 #ifdef DEBUG_COMPACTION
602 #endif
612 }
614 #if 0
617 #endif
623 }
624 }
625 }
627 #ifdef DEBUG_COMPACTION
628 /*
629 * Debug
630 */
634 }
636 }
638 #endif
639 /*
640 * Cleanup of the old data
641 */
646 }
653 }
664 }
665 not_determ:
674 }
676 /**
677 * xmlRegNewParserCtxt:
678 * @string: the string to parse
679 *
680 * Allocate a new regexp parser context
681 *
682 * Returns the new context or NULL in case of error
683 */
684 static xmlRegParserCtxtPtr
686 xmlRegParserCtxtPtr ret;
700 }
702 /**
703 * xmlRegNewRange:
704 * @ctxt: the regexp parser context
705 * @neg: is that negative
706 * @type: the type of range
707 * @start: the start codepoint
708 * @end: the end codepoint
709 *
710 * Allocate a new regexp range
711 *
712 * Returns the new range or NULL in case of error
713 */
714 static xmlRegRangePtr
717 xmlRegRangePtr ret;
723 }
729 }
731 /**
732 * xmlRegFreeRange:
733 * @range: the regexp range
734 *
735 * Free a regexp range
736 */
737 static void
745 }
747 /**
748 * xmlRegCopyRange:
749 * @range: the regexp range
750 *
751 * Copy a regexp range
752 *
753 * Returns the new copy or NULL in case of error.
754 */
755 static xmlRegRangePtr
757 xmlRegRangePtr ret;
772 }
773 }
775 }
777 /**
778 * xmlRegNewAtom:
779 * @ctxt: the regexp parser context
780 * @type: the type of atom
781 *
782 * Allocate a new atom
783 *
784 * Returns the new atom or NULL in case of error
785 */
786 static xmlRegAtomPtr
788 xmlRegAtomPtr ret;
794 }
801 }
803 /**
804 * xmlRegFreeAtom:
805 * @atom: the regexp atom
806 *
807 * Free a regexp atom
808 */
809 static void
827 }
829 /**
830 * xmlRegCopyAtom:
831 * @ctxt: the regexp parser context
832 * @atom: the oiginal atom
833 *
834 * Allocate a new regexp range
835 *
836 * Returns the new atom or NULL in case of error
837 */
838 static xmlRegAtomPtr
840 xmlRegAtomPtr ret;
846 }
860 }
866 }
867 }
870 error:
873 }
875 static xmlRegStatePtr
877 xmlRegStatePtr ret;
883 }
888 }
890 /**
891 * xmlRegFreeState:
892 * @state: the regexp state
893 *
894 * Free a regexp state
895 */
896 static void
906 }
908 /**
909 * xmlRegFreeParserCtxt:
910 * @ctxt: the regexp parser context
911 *
912 * Free a regexp parser context
913 */
914 static void
926 }
931 }
935 }
937 /************************************************************************
938 * *
939 * Display of Data structures *
940 * *
941 ************************************************************************/
943 static void
1052 }
1053 }
1055 static void
1074 }
1075 }
1076 static void
1083 }
1085 static void
1091 }
1111 }
1112 }
1114 static void
1120 }
1124 }
1128 else
1130 }
1133 }
1138 }
1142 }
1146 }
1148 static void
1156 }
1165 }
1166 }
1168 #ifdef DEBUG_REGEXP_GRAPH
1169 static void
1177 }
1188 }
1192 }
1201 }
1206 }
1207 }
1208 #endif
1210 /************************************************************************
1211 * *
1212 * Finite Automata structures manipulations *
1213 * *
1214 ************************************************************************/
1216 static void
1220 xmlRegRangePtr range;
1225 }
1229 }
1238 }
1248 }
1250 }
1257 }
1259 static int
1269 }
1279 }
1281 }
1285 }
1287 static int
1292 }
1301 }
1311 }
1313 }
1317 }
1319 static void
1330 }
1340 }
1342 }
1345 }
1347 static void
1357 }
1361 }
1362 /*
1363 * Other routines follow the philosophy 'When in doubt, add a transition'
1364 * so we check here whether such a transition is already present and, if
1365 * so, silently ignore this request.
1366 */
1374 #ifdef DEBUG_REGEXP_GRAPH
1377 #endif
1379 }
1380 }
1390 }
1400 }
1402 }
1403 #ifdef DEBUG_REGEXP_GRAPH
1415 #endif
1424 }
1426 static int
1437 }
1447 }
1449 }
1453 }
1455 /**
1456 * xmlFAGenerateAllTransition:
1457 * @ctxt: a regexp parser context
1458 * @from: the from state
1459 * @to: the target state or NULL for building a new one
1460 * @lax:
1461 *
1462 */
1463 static void
1471 }
1474 else
1476 }
1478 /**
1479 * xmlFAGenerateEpsilonTransition:
1480 * @ctxt: a regexp parser context
1481 * @from: the from state
1482 * @to: the target state or NULL for building a new one
1483 *
1484 */
1485 static void
1492 }
1494 }
1496 /**
1497 * xmlFAGenerateCountedEpsilonTransition:
1498 * @ctxt: a regexp parser context
1499 * @from: the from state
1500 * @to: the target state or NULL for building a new one
1501 * counter: the counter for that transition
1502 *
1503 */
1504 static void
1511 }
1513 }
1515 /**
1516 * xmlFAGenerateCountedTransition:
1517 * @ctxt: a regexp parser context
1518 * @from: the from state
1519 * @to: the target state or NULL for building a new one
1520 * counter: the counter for that transition
1521 *
1522 */
1523 static void
1530 }
1532 }
1534 /**
1535 * xmlFAGenerateTransitions:
1536 * @ctxt: a regexp parser context
1537 * @from: the from state
1538 * @to: the target state or NULL for building a new one
1539 * @atom: the atom generating the transition
1540 *
1541 * Returns 0 if success and -1 in case of error.
1542 */
1543 static int
1546 xmlRegStatePtr end;
1551 }
1553 /*
1554 * this is a subexpression handling one should not need to
1555 * create a new node except for XML_REGEXP_QUANT_RANGE.
1556 */
1559 }
1562 /*
1563 * Generate an epsilon transition to link to the target
1564 */
1566 #ifdef DV
1573 #endif
1574 }
1578 /*
1579 * transition done to the state after end of atom.
1580 * 1. set transition from atom start to new state
1581 * 2. set transition from atom end to this state.
1582 */
1589 }
1604 /*
1605 * create the final state now if needed
1606 */
1612 }
1614 /*
1615 * The principle here is to use counted transition
1616 * to avoid explosion in the number of states in the
1617 * graph. This is clearly more complex but should not
1618 * be exploitable at runtime.
1619 */
1621 xmlRegAtomPtr copy;
1622 /*
1623 * duplicate a transition based on atom to count next
1624 * occurences after 1. We cannot loop to atom->start
1625 * directly because we need an epsilon transition to
1626 * newstate.
1627 */
1628 /* ???? For some reason it seems we never reach that
1629 case, I suppose this got optimized out before when
1630 building the automata */
1645 /* count the number of times we see it again */
1648 /* allow a way out based on the count */
1651 /* and also allow a direct exit for 0 */
1653 newstate);
1655 /*
1656 * either we need the atom at least once or there
1657 * is an atom->start0 allowing to easilly plug the
1658 * epsilon transition.
1659 */
1663 /* count the number of times we see it again */
1666 /* allow a way out based on the count */
1669 /* and if needed allow a direct exit for 0 */
1672 newstate);
1674 }
1679 }
1682 }
1684 }
1687 /*
1688 * we can discard the atom and generate an epsilon transition instead
1689 */
1696 }
1697 }
1702 }
1709 }
1710 }
1714 /*
1715 * Do not pollute the target state by adding transitions from
1716 * it as it is likely to be the shared target of multiple branches.
1717 * So isolate with an epsilon transition.
1718 */
1719 xmlRegStatePtr tmp;
1726 }
1729 }
1732 }
1750 #if DV_test
1753 }
1754 #endif
1758 }
1760 }
1762 /**
1763 * xmlFAReduceEpsilonTransitions:
1764 * @ctxt: a regexp parser context
1765 * @fromnr: the from state
1766 * @tonr: the to state
1767 * @counter: should that transition be associated to a counted
1768 *
1769 */
1770 static void
1774 xmlRegStatePtr from;
1775 xmlRegStatePtr to;
1777 #ifdef DEBUG_REGEXP_GRAPH
1779 #endif
1792 #ifdef DEBUG_REGEXP_GRAPH
1794 #endif
1796 }
1801 /*
1802 * Don't remove counted transitions
1803 * Don't loop either
1804 */
1813 #ifdef DEBUG_REGEXP_GRAPH
1816 #endif
1824 counter);
1825 }
1826 }
1827 }
1838 }
1839 }
1840 }
1842 }
1844 /**
1845 * xmlFAEliminateSimpleEpsilonTransitions:
1846 * @ctxt: a regexp parser context
1847 *
1848 * Eliminating general epsilon transitions can get costly in the general
1849 * algorithm due to the large amount of generated new transitions and
1850 * associated comparisons. However for simple epsilon transition used just
1851 * to separate building blocks when generating the automata this can be
1852 * reduced to state elimination:
1853 * - if there exists an epsilon from X to Y
1854 * - if there is no other transition from X
1855 * then X and Y are semantically equivalent and X can be eliminated
1856 * If X is the start state then make Y the start state, else replace the
1857 * target of all transitions to X by transitions to Y.
1858 */
1859 static void
1872 /* is the only transition out a basic transition */
1881 #ifdef DEBUG_REGEXP_GRAPH
1884 #endif
1886 #ifdef DEBUG_REGEXP_GRAPH
1889 #endif
1894 #ifdef DEBUG_REGEXP_GRAPH
1897 #endif
1903 }
1904 }
1905 }
1908 /* eliminate the transition completely */
1913 }
1915 }
1916 }
1917 }
1918 /**
1919 * xmlFAEliminateEpsilonTransitions:
1920 * @ctxt: a regexp parser context
1921 *
1922 */
1923 static void
1926 xmlRegStatePtr state;
1931 /*
1932 * Eliminate simple epsilon transition and the associated unreachable
1933 * states.
1934 */
1939 #ifdef DEBUG_REGEXP_GRAPH
1941 #endif
1944 }
1945 }
1949 /*
1950 * Build the completed transitions bypassing the epsilons
1951 * Use a marking algorithm to avoid loops
1952 * Mark sink states too.
1953 * Process from the latests states backward to the start when
1954 * there is long cascading epsilon chains this minimize the
1955 * recursions and transition compares when adding the new ones
1956 */
1964 }
1970 #ifdef DEBUG_REGEXP_GRAPH
1973 #endif
1977 #ifdef DEBUG_REGEXP_GRAPH
1980 #endif
1987 #ifdef DEBUG_REGEXP_GRAPH
1991 #endif
1992 }
1993 }
1994 }
1995 }
1996 /*
1997 * Eliminate the epsilon transitions
1998 */
2010 }
2011 }
2012 }
2013 }
2015 /*
2016 * Use this pass to detect unreachable states too
2017 */
2022 }
2029 /*
2030 * Mark all states reachable from the current reachable state
2031 */
2043 }
2044 }
2045 }
2047 /*
2048 * find the next accessible state not explored
2049 */
2054 XML_REGEXP_MARK_START)) {
2057 }
2058 }
2059 }
2061 }
2065 #ifdef DEBUG_REGEXP_GRAPH
2067 #endif
2070 }
2071 }
2073 }
2075 static int
2087 /* put them in order */
2089 xmlRegRangePtr tmp;
2094 }
2107 else
2113 /*
2114 * just check all codepoints in the range for acceptance,
2115 * this is usually way cheaper since done only once at
2116 * compilation than testing over and over at runtime or
2117 * pushing too many states when evaluating.
2118 */
2132 }
2139 /*
2140 * comparing a block range with anything else is way
2141 * too costly, and maintining the table is like too much
2142 * memory too, so let's force the automata to save state
2143 * here.
2144 */
2146 }
2165 /* same thing to limit complexity */
2167 }
2170 /* range1->type < range2->type here */
2173 /* all disjoint except in the subgroups */
2227 /* safety net ! */
2229 }
2230 }
2231 }
2236 }
2238 /**
2239 * xmlFACompareAtomTypes:
2240 * @type1: an atom type
2241 * @type2: an atom type
2242 *
2243 * Compares two atoms type to check whether they intersect in some ways,
2244 * this is used by xmlFACompareAtoms only
2245 *
2246 * Returns 1 if they may intersect and 0 otherwise
2247 */
2248 static int
2267 /* simplify subsequent compares by making sure type1 < type2 */
2272 }
2275 /* can't be a letter, number, mark, pontuation, symbol */
2292 /* can't be a number, mark, separator, pontuation, symbol or other */
2311 /* can't be a mark, separator, pontuation, symbol or other */
2328 /* can't be a letter, mark, separator, pontuation, symbol or other */
2348 /* can't be a mark, separator, pontuation, symbol or other */
2364 /*
2365 * at that point we know both type 1 and type2 are from
2366 * character categories are ordered and are different,
2367 * it becomes simple because this is a partition
2368 */
2435 }
2437 }
2439 /**
2440 * xmlFAEqualAtoms:
2441 * @atom1: an atom
2442 * @atom2: an atom
2443 * @deep: if not set only compare string pointers
2444 *
2445 * Compares two atoms to check whether they are the same exactly
2446 * this is used to remove equivalent transitions
2447 *
2448 * Returns 1 if same and 0 otherwise
2449 */
2450 static int
2468 else
2476 /* too hard to do in the general case */
2480 }
2482 }
2484 /**
2485 * xmlFACompareAtoms:
2486 * @atom1: an atom
2487 * @atom2: an atom
2488 * @deep: if not set only compare string pointers
2489 *
2490 * Compares two atoms to check whether they intersect in some ways,
2491 * this is used by xmlFAComputesDeterminism and xmlFARecurseDeterminism only
2492 *
2493 * Returns 1 if yes and 0 otherwise
2494 */
2495 static int
2509 xmlRegAtomPtr tmp;
2513 }
2516 /* if they can't intersect at the type level break now */
2519 }
2524 else
2537 }
2544 /*
2545 * need to check that none of the ranges eventually matches
2546 */
2555 }
2556 }
2557 }
2559 }
2563 }
2564 done:
2567 }
2570 not_determinist:
2572 }
2574 /**
2575 * xmlFARecurseDeterminism:
2576 * @ctxt: a regexp parser context
2577 *
2578 * Check whether the associated regexp is determinist,
2579 * should be called after xmlFAEliminateEpsilonTransitions()
2580 *
2581 */
2582 static int
2588 xmlRegTransPtr t1;
2599 /*
2600 * don't recurse on transitions potentially added in the course of
2601 * the elimination.
2602 */
2606 /*
2607 * check transitions conflicting with the one looked at
2608 */
2618 /* t1->nd = 1; */
2619 }
2621 }
2626 /* mark the transition as non-deterministic */
2628 }
2629 }
2631 }
2633 /**
2634 * xmlFAComputesDeterminism:
2635 * @ctxt: a regexp parser context
2636 *
2637 * Check whether the associated regexp is determinist,
2638 * should be called after xmlFAEliminateEpsilonTransitions()
2639 *
2640 */
2641 static int
2644 xmlRegStatePtr state;
2650 #ifdef DEBUG_REGEXP_GRAPH
2653 #endif
2660 /*
2661 * First cleanup the automata removing cancelled transitions
2662 */
2671 /*
2672 * Determinism checks in case of counted or all transitions
2673 * will have to be handled separately
2674 */
2676 /* t1->nd = 1; */
2678 }
2687 /*
2688 * Here we use deep because we want to keep the
2689 * transitions which indicate a conflict
2690 */
2695 }
2696 }
2697 }
2698 }
2699 }
2701 /*
2702 * Check for all states that there aren't 2 transitions
2703 * with the same atom and a different target.
2704 */
2714 /*
2715 * Determinism checks in case of counted or all transitions
2716 * will have to be handled separately
2717 */
2720 }
2728 /*
2729 * But here we don't use deep because we want to
2730 * find transitions which indicate a conflict
2731 */
2734 /* mark the transitions as non-deterministic ones */
2738 }
2740 /*
2741 * do the closure in case of remaining specific
2742 * epsilon transitions like choices or all
2743 */
2746 /* don't shortcut the computation so all non deterministic
2747 transition get marked down
2748 if (ret == 0)
2749 return(0);
2750 */
2753 /* t2->nd = 1; */
2755 }
2756 }
2757 }
2758 /* don't shortcut the computation so all non deterministic
2759 transition get marked down
2760 if (ret == 0)
2761 break; */
2762 }
2764 /*
2765 * mark specifically the last non-deterministic transition
2766 * from a state since there is no need to set-up rollback
2767 * from it
2768 */
2771 }
2773 /* don't shortcut the computation so all non deterministic
2774 transition get marked down
2775 if (ret == 0)
2776 break; */
2777 }
2781 }
2783 /************************************************************************
2784 * *
2785 * Routines to check input against transition atoms *
2786 * *
2787 ************************************************************************/
2789 static int
2946 /* ret = xmlUCSIsCatCn(codepoint); */
2947 /* Seems it doesn't exist anymore in recent Unicode releases */
2953 }
2957 }
2959 static int
2962 xmlRegRangePtr range;
2990 else
2998 }
2999 }
3001 }
3058 }
3060 }
3062 /************************************************************************
3063 * *
3064 * Saving and restoring state of an execution context *
3065 * *
3066 ************************************************************************/
3068 #ifdef DEBUG_REGEXP_EXEC
3069 static void
3080 }
3082 }
3083 #endif
3085 static void
3087 #ifdef DEBUG_REGEXP_EXEC
3092 #endif
3093 #ifdef MAX_PUSH
3096 }
3098 #endif
3108 }
3122 }
3126 }
3138 }
3139 }
3142 }
3144 }
3146 static void
3150 #ifdef DEBUG_REGEXP_EXEC
3152 #endif
3154 }
3164 }
3168 }
3169 }
3171 #ifdef DEBUG_REGEXP_EXEC
3174 #endif
3175 }
3177 /************************************************************************
3178 * *
3179 * Verifier, running an input against a compiled regexp *
3180 * *
3181 ************************************************************************/
3183 static int
3185 xmlRegExecCtxt execval;
3208 }
3216 xmlRegTransPtr trans;
3217 xmlRegAtomPtr atom;
3219 /*
3220 * If end of input on non-terminal state, rollback, however we may
3221 * still have epsilon like transition for counted transitions
3222 * on counters, in that case don't break too early. Additionally,
3223 * if we are working on a range like "AB{0,2}", where B is not present,
3224 * we don't want to break.
3225 */
3228 /*
3229 * if there is a transition, we must check if
3230 * atom allows minOccurs of 0
3231 */
3238 }
3241 }
3253 xmlRegCounterPtr counter;
3258 }
3259 /*
3260 * A counted transition.
3261 */
3265 #ifdef DEBUG_REGEXP_EXEC
3268 #endif
3282 /*
3283 * this is a multiple input sequence
3284 * If there is a counter associated increment it now.
3285 * before potentially saving and rollback
3286 * do not increment if the counter is already over the
3287 * maximum limit in which case get to next transition
3288 */
3290 xmlRegCounterPtr counter;
3297 }
3302 #ifdef DEBUG_REGEXP_EXEC
3304 #endif
3306 }
3309 }
3312 /*
3313 * Try to progress as much as possible on the input
3314 */
3317 }
3319 /*
3320 * End of input: stop here
3321 */
3325 }
3330 /*
3331 * The transition is acceptable save it
3332 */
3338 }
3340 len);
3347 /*
3348 * If the last check failed but one transition was found
3349 * possible, rollback
3350 */
3355 }
3360 }
3361 #ifdef DEBUG_REGEXP_EXEC
3363 #endif
3365 }
3367 /*
3368 * we don't match on the codepoint, but minOccurs of 0
3369 * says that's ok. Setting len to 0 inhibits stepping
3370 * over the codepoint.
3371 */
3375 }
3377 /* another spot to match when minOccurs is 0 */
3381 }
3386 #ifdef DEBUG_REGEXP_EXEC
3390 else
3393 #endif
3395 }
3397 xmlRegCounterPtr counter;
3399 /* make sure we don't go over the counter maximum value */
3405 }
3409 #ifdef DEBUG_REGEXP_EXEC
3411 #endif
3413 }
3419 }
3420 #ifdef DEBUG_REGEXP_EXEC
3423 #endif
3425 }
3426 #ifdef DEBUG_REGEXP_EXEC
3428 #endif
3433 }
3438 }
3439 }
3441 rollback:
3442 /*
3443 * Failed to find a way out
3444 */
3446 #ifdef DEBUG_REGEXP_EXEC
3449 #endif
3451 }
3452 progress:
3454 }
3455 error:
3463 }
3465 }
3476 }
3478 }
3480 /************************************************************************
3481 * *
3482 * Progressive interface to the verifier one atom at a time *
3483 * *
3484 ************************************************************************/
3485 #ifdef DEBUG_ERR
3487 #endif
3489 /**
3490 * xmlRegNewExecCtxt:
3491 * @comp: a precompiled regular expression
3492 * @callback: a callback function used for handling progresses in the
3493 * automata matching phase
3494 * @data: the context data associated to the callback in this context
3495 *
3496 * Build a context used for progressive evaluation of a regexp.
3497 *
3498 * Returns the new context
3499 */
3500 xmlRegExecCtxtPtr
3502 xmlRegExecCtxtPtr exec;
3512 }
3529 /*
3530 * For error handling, exec->counts is allocated twice the size
3531 * the second half is used to store the data in case of rollback
3532 */
3539 }
3545 }
3553 }
3555 /**
3556 * xmlRegFreeExecCtxt:
3557 * @exec: a regular expression evaulation context
3558 *
3559 * Free the structures associated to a regular expression evaulation context.
3560 */
3561 void
3573 }
3575 }
3584 }
3586 }
3590 }
3592 static void
3595 #ifdef DEBUG_PUSH
3597 #endif
3606 }
3608 xmlRegInputTokenPtr tmp;
3617 }
3619 }
3625 }
3627 /**
3628 * xmlRegStrEqualWildcard:
3629 * @expStr: the string to be evaluated
3630 * @valStr: the validation string
3631 *
3632 * Checks if both strings are equal or have the same content. "*"
3633 * can be used as a wildcard in @valStr; "|" is used as a seperator of
3634 * substrings in both @expStr and @valStr.
3635 *
3636 * Returns 1 if the comparison is satisfied and the number of substrings
3637 * is equal, 0 otherwise.
3638 */
3640 static int
3646 /*
3647 * Eval if we have a wildcard for the current item.
3648 */
3650 /* if one of them starts with a wildcard make valStr be it */
3657 }
3662 valStr++;
3667 }
3668 expStr++;
3669 valStr++;
3673 else
3675 }
3677 /**
3678 * xmlRegCompactPushString:
3679 * @exec: a regexp execution context
3680 * @comp: the precompiled exec with a compact table
3681 * @value: a string token input
3682 * @data: data associated to the token to reuse in callbacks
3683 *
3684 * Push one input token in the execution context
3685 *
3686 * Returns: 1 if the regexp reached a final state, 0 if non-final, and
3687 * a negative value in case of error.
3688 */
3689 static int
3691 xmlRegexpPtr comp,
3701 /*
3702 * are we at a final state ?
3703 */
3705 XML_REGEXP_FINAL_STATE)
3708 }
3710 #ifdef DEBUG_PUSH
3712 #endif
3714 /*
3715 * Examine all outside transitions from current state
3716 */
3726 }
3727 #ifdef DEBUG_PUSH
3729 #endif
3731 XML_REGEXP_SINK_STATE)
3735 XML_REGEXP_FINAL_STATE)
3738 }
3739 }
3740 }
3741 /*
3742 * Failed to find an exit transition out from current state for the
3743 * current token
3744 */
3745 #ifdef DEBUG_PUSH
3747 #endif
3748 error:
3754 #ifdef DEBUG_ERR
3756 #endif
3758 }
3760 /**
3761 * xmlRegExecPushStringInternal:
3762 * @exec: a regexp execution context or NULL to indicate the end
3763 * @value: a string token input
3764 * @data: data associated to the token to reuse in callbacks
3765 * @compound: value was assembled from 2 strings
3766 *
3767 * Push one input token in the execution context
3768 *
3769 * Returns: 1 if the regexp reached a final state, 0 if non-final, and
3770 * a negative value in case of error.
3771 */
3772 static int
3775 xmlRegTransPtr trans;
3776 xmlRegAtomPtr atom;
3795 }
3797 #ifdef DEBUG_PUSH
3799 #endif
3800 /*
3801 * If we have an active rollback stack push the new value there
3802 * and get back to where we were left
3803 */
3808 #ifdef DEBUG_PUSH
3810 #endif
3811 }
3818 /*
3819 * End of input on non-terminal state, rollback, however we may
3820 * still have epsilon like transition for counted transitions
3821 * on counters, in that case don't break too early.
3822 */
3836 xmlRegTransPtr t;
3837 xmlRegCounterPtr counter;
3841 #ifdef DEBUG_PUSH
3843 #endif
3844 /*
3845 * Check all counted transitions from the current state
3846 */
3861 }
3868 }
3869 }
3870 }
3874 xmlRegTransPtr t;
3875 xmlRegCounterPtr counter;
3879 #ifdef DEBUG_PUSH
3881 #endif
3882 /*
3883 * Check all counted transitions from the current state
3884 */
3894 }
3895 }
3898 xmlRegCounterPtr counter;
3900 /*
3901 * A counted transition.
3902 */
3906 #ifdef DEBUG_PUSH
3909 #endif
3921 }
3923 xmlRegCounterPtr counter;
3930 }
3935 /*
3936 * this is a multiple input sequence
3937 */
3941 }
3943 }
3946 /*
3947 * Try to progress as much as possible on the input
3948 */
3951 }
3955 #ifdef DEBUG_PUSH
3957 #endif
3959 /*
3960 * End of input: stop here
3961 */
3965 }
3970 /*
3971 * The transition is acceptable save it
3972 */
3977 }
3981 }
3988 /*
3989 * If the last check failed but one transition was found
3990 * possible, rollback
3991 */
3996 }
3997 }
3998 }
4004 }
4008 }
4010 }
4012 #ifdef DEBUG_PUSH
4014 #endif
4016 }
4019 #ifdef DEBUG_REGEXP_EXEC
4022 #endif
4024 }
4025 #ifdef DEBUG_PUSH
4027 #endif
4030 XML_REGEXP_SINK_STATE)) {
4031 /*
4032 * entering a sink state, save the current state as error
4033 * state.
4034 */
4041 }
4050 #ifdef DEBUG_PUSH
4052 #endif
4056 #ifdef DEBUG_PUSH
4058 #endif
4059 }
4063 #ifdef DEBUG_PUSH
4065 #endif
4066 }
4067 }
4072 }
4073 }
4075 rollback:
4076 /*
4077 * if we didn't yet rollback on the current input
4078 * store the current state as the error state.
4079 */
4089 }
4091 /*
4092 * Failed to find a way out
4093 */
4099 #ifdef DEBUG_PUSH
4101 #endif
4102 }
4103 }
4105 progress:
4108 }
4111 }
4112 #ifdef DEBUG_ERR
4115 }
4116 #endif
4118 }
4120 /**
4121 * xmlRegExecPushString:
4122 * @exec: a regexp execution context or NULL to indicate the end
4123 * @value: a string token input
4124 * @data: data associated to the token to reuse in callbacks
4125 *
4126 * Push one input token in the execution context
4127 *
4128 * Returns: 1 if the regexp reached a final state, 0 if non-final, and
4129 * a negative value in case of error.
4130 */
4131 int
4135 }
4137 /**
4138 * xmlRegExecPushString2:
4139 * @exec: a regexp execution context or NULL to indicate the end
4140 * @value: the first string token input
4141 * @value2: the second string token input
4142 * @data: data associated to the token to reuse in callbacks
4143 *
4144 * Push one input token in the execution context
4145 *
4146 * Returns: 1 if the regexp reached a final state, 0 if non-final, and
4147 * a negative value in case of error.
4148 */
4149 int
4174 }
4177 }
4185 else
4191 }
4193 /**
4194 * xmlRegExecGetValues:
4195 * @exec: a regexp execution context
4196 * @err: error extraction or normal one
4197 * @nbval: pointer to the number of accepted values IN/OUT
4198 * @nbneg: return number of negative transitions
4199 * @values: pointer to the array of acceptable values
4200 * @terminal: return value if this was a terminal state
4201 *
4202 * Extract informations from the regexp execution, internal routine to
4203 * implement xmlRegExecNextValues() and xmlRegExecErrInfo()
4204 *
4205 * Returns: 0 in case of success or -1 in case of error.
4206 */
4207 static int
4222 xmlRegexpPtr comp;
4232 }
4235 XML_REGEXP_FINAL_STATE)
4237 else
4239 }
4244 XML_REGEXP_SINK_STATE)) {
4247 }
4248 }
4253 XML_REGEXP_SINK_STATE)) {
4256 }
4257 }
4260 xmlRegTransPtr trans;
4261 xmlRegAtomPtr atom;
4262 xmlRegStatePtr state;
4267 else
4269 }
4277 }
4280 transno++) {
4288 /* this should not be reached but ... */
4289 TODO;
4291 /* this should not be reached but ... */
4292 TODO;
4299 else
4306 else
4309 }
4313 XML_REGEXP_SINK_STATE)) {
4316 else
4319 }
4320 }
4321 }
4324 transno++) {
4340 XML_REGEXP_SINK_STATE)) {
4343 else
4346 }
4347 }
4348 }
4349 }
4351 }
4353 /**
4354 * xmlRegExecNextValues:
4355 * @exec: a regexp execution context
4356 * @nbval: pointer to the number of accepted values IN/OUT
4357 * @nbneg: return number of negative transitions
4358 * @values: pointer to the array of acceptable values
4359 * @terminal: return value if this was a terminal state
4360 *
4361 * Extract informations from the regexp execution,
4362 * the parameter @values must point to an array of @nbval string pointers
4363 * on return nbval will contain the number of possible strings in that
4364 * state and the @values array will be updated with them. The string values
4365 * returned will be freed with the @exec context and don't need to be
4366 * deallocated.
4367 *
4368 * Returns: 0 in case of success or -1 in case of error.
4369 */
4370 int
4374 }
4376 /**
4377 * xmlRegExecErrInfo:
4378 * @exec: a regexp execution context generating an error
4379 * @string: return value for the error string
4380 * @nbval: pointer to the number of accepted values IN/OUT
4381 * @nbneg: return number of negative transitions
4382 * @values: pointer to the array of acceptable values
4383 * @terminal: return value if this was a terminal state
4384 *
4385 * Extract error informations from the regexp execution, the parameter
4386 * @string will be updated with the value pushed and not accepted,
4387 * the parameter @values must point to an array of @nbval string pointers
4388 * on return nbval will contain the number of possible strings in that
4389 * state and the @values array will be updated with them. The string values
4390 * returned will be freed with the @exec context and don't need to be
4391 * deallocated.
4392 *
4393 * Returns: 0 in case of success or -1 in case of error.
4394 */
4395 int
4403 else
4405 }
4407 }
4409 #ifdef DEBUG_ERR
4417 }
4418 #endif
4420 #if 0
4421 static int
4423 xmlRegTransPtr trans;
4424 xmlRegAtomPtr atom;
4437 /*
4438 * End of input on non-terminal state, rollback, however we may
4439 * still have epsilon like transition for counted transitions
4440 * on counters, in that case don't break too early.
4441 */
4454 xmlRegCounterPtr counter;
4456 /*
4457 * A counted transition.
4458 */
4462 #ifdef DEBUG_REGEXP_EXEC
4465 #endif
4477 /*
4478 * this is a multiple input sequence
4479 */
4482 }
4485 /*
4486 * Try to progress as much as possible on the input
4487 */
4490 }
4492 /*
4493 * End of input: stop here
4494 */
4498 }
4503 /*
4504 * The transition is acceptable save it
4505 */
4511 }
4513 len);
4520 /*
4521 * If the last check failed but one transition was found
4522 * possible, rollback
4523 */
4528 }
4529 }
4530 }
4534 }
4535 /*
4536 * restart count for expressions like this ((abc){2})*
4537 */
4539 #ifdef DEBUG_REGEXP_EXEC
4541 #endif
4543 }
4545 #ifdef DEBUG_REGEXP_EXEC
4547 #endif
4549 }
4550 #ifdef DEBUG_REGEXP_EXEC
4552 #endif
4557 }
4562 }
4563 }
4565 rollback:
4566 /*
4567 * Failed to find a way out
4568 */
4571 }
4572 progress:
4574 }
4575 }
4576 #endif
4577 /************************************************************************
4578 * *
4579 * Parser for the Schemas Datatype Regular Expressions *
4580 * http://www.w3.org/TR/2001/REC-xmlschema-2-20010502/#regexs *
4581 * *
4582 ************************************************************************/
4584 /**
4585 * xmlFAIsChar:
4586 * @ctxt: a regexp parser context
4587 *
4588 * [10] Char ::= [^.\?*+()|#x5B#x5D]
4589 */
4590 static int
4602 }
4604 /**
4605 * xmlFAParseCharProp:
4606 * @ctxt: a regexp parser context
4607 *
4608 * [27] charProp ::= IsCategory | IsBlock
4609 * [28] IsCategory ::= Letters | Marks | Numbers | Punctuation |
4610 * Separators | Symbols | Others
4611 * [29] Letters ::= 'L' [ultmo]?
4612 * [30] Marks ::= 'M' [nce]?
4613 * [31] Numbers ::= 'N' [dlo]?
4614 * [32] Punctuation ::= 'P' [cdseifo]?
4615 * [33] Separators ::= 'Z' [slp]?
4616 * [34] Symbols ::= 'S' [mcko]?
4617 * [35] Others ::= 'C' [cfon]?
4618 * [36] IsBlock ::= 'Is' [a-zA-Z0-9#x2D]+
4619 */
4620 static void
4628 NEXT;
4631 NEXT;
4634 NEXT;
4637 NEXT;
4640 NEXT;
4643 NEXT;
4647 }
4649 NEXT;
4652 NEXT;
4653 /* nonspacing */
4656 NEXT;
4657 /* spacing combining */
4660 NEXT;
4661 /* enclosing */
4664 /* all marks */
4666 }
4668 NEXT;
4671 NEXT;
4672 /* digital */
4675 NEXT;
4676 /* letter */
4679 NEXT;
4680 /* other */
4683 /* all numbers */
4685 }
4687 NEXT;
4690 NEXT;
4691 /* connector */
4694 NEXT;
4695 /* dash */
4698 NEXT;
4699 /* open */
4702 NEXT;
4703 /* close */
4706 NEXT;
4707 /* initial quote */
4710 NEXT;
4711 /* final quote */
4714 NEXT;
4715 /* other */
4718 /* all punctuation */
4720 }
4722 NEXT;
4725 NEXT;
4726 /* space */
4729 NEXT;
4730 /* line */
4733 NEXT;
4734 /* paragraph */
4737 /* all separators */
4739 }
4741 NEXT;
4744 NEXT;
4746 /* math */
4748 NEXT;
4750 /* currency */
4752 NEXT;
4754 /* modifiers */
4756 NEXT;
4758 /* other */
4760 /* all symbols */
4762 }
4764 NEXT;
4767 NEXT;
4768 /* control */
4771 NEXT;
4772 /* format */
4775 NEXT;
4776 /* private use */
4779 NEXT;
4780 /* not assigned */
4783 /* all others */
4785 }
4788 NEXT;
4793 }
4794 NEXT;
4801 NEXT;
4807 NEXT;
4809 }
4810 }
4816 }
4824 }
4825 }
4827 /**
4828 * xmlFAParseCharClassEsc:
4829 * @ctxt: a regexp parser context
4830 *
4831 * [23] charClassEsc ::= ( SingleCharEsc | MultiCharEsc | catEsc | complEsc )
4832 * [24] SingleCharEsc ::= '\' [nrt\|.?*+(){}#x2D#x5B#x5D#x5E]
4833 * [25] catEsc ::= '\p{' charProp '}'
4834 * [26] complEsc ::= '\P{' charProp '}'
4835 * [37] MultiCharEsc ::= '.' | ('\' [sSiIcCdDwW])
4836 */
4837 static void
4847 }
4848 NEXT;
4850 }
4854 }
4855 NEXT;
4858 NEXT;
4862 }
4863 NEXT;
4868 }
4869 NEXT;
4871 NEXT;
4875 }
4876 NEXT;
4882 }
4883 NEXT;
4904 }
4905 }
4917 }
4920 }
4921 NEXT;
4958 }
4959 NEXT;
4965 }
4968 }
4969 }
4971 /**
4972 * xmlFAParseCharRange:
4973 * @ctxt: a regexp parser context
4974 *
4975 * [17] charRange ::= seRange | XmlCharRef | XmlCharIncDash
4976 * [18] seRange ::= charOrEsc '-' charOrEsc
4977 * [20] charOrEsc ::= XmlChar | SingleCharEsc
4978 * [21] XmlChar ::= [^\#x2D#x5B#x5D]
4979 * [22] XmlCharIncDash ::= [^\#x5B#x5D]
4980 */
4981 static void
4990 }
4994 NEXT;
5007 }
5015 }
5016 /*
5017 * Since we are "inside" a range, we can assume ctxt->cur is past
5018 * the start of ctxt->string, and PREV should be safe
5019 */
5023 }
5030 }
5031 NEXT;
5034 NEXT;
5047 }
5054 }
5056 /* TODO check that the values are acceptable character ranges for XML */
5062 }
5064 }
5066 /**
5067 * xmlFAParsePosCharGroup:
5068 * @ctxt: a regexp parser context
5069 *
5070 * [14] posCharGroup ::= ( charRange | charClassEsc )+
5071 */
5072 static void
5079 }
5082 }
5084 /**
5085 * xmlFAParseCharGroup:
5086 * @ctxt: a regexp parser context
5087 *
5088 * [13] charGroup ::= posCharGroup | negCharGroup | charClassSub
5089 * [15] negCharGroup ::= '^' posCharGroup
5090 * [16] charClassSub ::= ( posCharGroup | negCharGroup ) '-' charClassExpr
5091 * [12] charClassExpr ::= '[' charGroup ']'
5092 */
5093 static void
5100 NEXT;
5111 NEXT;
5115 }
5120 }
5121 }
5123 }
5125 /**
5126 * xmlFAParseCharClass:
5127 * @ctxt: a regexp parser context
5128 *
5129 * [11] charClass ::= charClassEsc | charClassExpr
5130 * [12] charClassExpr ::= '[' charGroup ']'
5131 */
5132 static void
5135 NEXT;
5141 NEXT;
5144 }
5147 }
5148 }
5150 /**
5151 * xmlFAParseQuantExact:
5152 * @ctxt: a regexp parser context
5153 *
5154 * [8] QuantExact ::= [0-9]+
5155 *
5156 * Returns 0 if success or -1 in case of error
5157 */
5158 static int
5166 NEXT;
5167 }
5170 }
5172 }
5174 /**
5175 * xmlFAParseQuantifier:
5176 * @ctxt: a regexp parser context
5177 *
5178 * [4] quantifier ::= [?*+] | ( '{' quantity '}' )
5179 * [5] quantity ::= quantRange | quantMin | QuantExact
5180 * [6] quantRange ::= QuantExact ',' QuantExact
5181 * [7] quantMin ::= QuantExact ','
5182 * [8] QuantExact ::= [0-9]+
5183 */
5184 static int
5197 }
5198 NEXT;
5200 }
5204 NEXT;
5209 NEXT;
5218 }
5219 }
5220 }
5222 NEXT;
5225 }
5232 }
5234 }
5236 }
5238 /**
5239 * xmlFAParseAtom:
5240 * @ctxt: a regexp parser context
5241 *
5242 * [9] atom ::= Char | charClass | ( '(' regExp ')' )
5243 */
5244 static int
5266 NEXT;
5267 /*
5268 * this extra Epsilon transition is needed if we count with 0 allowed
5269 * unfortunately this can't be known at that point
5270 */
5280 NEXT;
5283 }
5295 }
5297 }
5299 /**
5300 * xmlFAParsePiece:
5301 * @ctxt: a regexp parser context
5302 *
5303 * [3] piece ::= atom quantifier?
5304 */
5305 static int
5315 }
5318 }
5320 /**
5321 * xmlFAParseBranch:
5322 * @ctxt: a regexp parser context
5323 * @to: optional target to the end of the branch
5324 *
5325 * @to is used to optimize by removing duplicate path in automata
5326 * in expressions like (a|b)(c|d)
5327 *
5328 * [2] branch ::= piece*
5329 */
5330 static int
5332 xmlRegStatePtr previous;
5343 }
5352 }
5353 }
5355 }
5357 /**
5358 * xmlFAParseRegExp:
5359 * @ctxt: a regexp parser context
5360 * @top: is this the top-level expression ?
5361 *
5362 * [1] regExp ::= branch ( '|' branch )*
5363 */
5364 static void
5368 /* if not top start should have been generated by an epsilon trans */
5373 #ifdef DEBUG_REGEXP_GRAPH
5375 #endif
5377 }
5381 }
5384 NEXT;
5388 }
5392 }
5396 }
5397 }
5399 /************************************************************************
5400 * *
5401 * The basic API *
5402 * *
5403 ************************************************************************/
5405 /**
5406 * xmlRegexpPrint:
5407 * @output: the file for the output debug
5408 * @regexp: the compiled regexp
5409 *
5410 * Print the content of the compiled regular expression
5411 */
5412 void
5422 }
5429 }
5434 }
5439 }
5440 }
5442 /**
5443 * xmlRegexpCompile:
5444 * @regexp: a regular expression string
5445 *
5446 * Parses a regular expression conforming to XML Schemas Part 2 Datatype
5447 * Appendix F and builds an automata suitable for testing strings against
5448 * that regular expression
5449 *
5450 * Returns the compiled expression or NULL in case of error
5451 */
5452 xmlRegexpPtr
5454 xmlRegexpPtr ret;
5455 xmlRegParserCtxtPtr ctxt;
5461 /* initialize the parser */
5466 /* parse the expression building an automata */
5470 }
5474 }
5479 /* remove the Epsilon except for counted transitions */
5486 }
5490 }
5492 /**
5493 * xmlRegexpExec:
5494 * @comp: the compiled regular expression
5495 * @content: the value to check against the regular expression
5496 *
5497 * Check if the regular expression generates the value
5498 *
5499 * Returns 1 if it matches, 0 if not and a negative value in case of error
5500 */
5501 int
5506 }
5508 /**
5509 * xmlRegexpIsDeterminist:
5510 * @comp: the compiled regular expression
5511 *
5512 * Check if the regular expression is determinist
5513 *
5514 * Returns 1 if it yes, 0 if not and a negative value in case of error
5515 */
5516 int
5518 xmlAutomataPtr am;
5533 }
5546 }
5548 /**
5549 * xmlRegFreeRegexp:
5550 * @regexp: the regexp
5551 *
5552 * Free a regexp
5553 */
5554 void
5566 }
5571 }
5582 }
5585 }
5587 #ifdef LIBXML_AUTOMATA_ENABLED
5588 /************************************************************************
5589 * *
5590 * The Automata interface *
5591 * *
5592 ************************************************************************/
5594 /**
5595 * xmlNewAutomata:
5596 *
5597 * Create a new automata
5598 *
5599 * Returns the new object or NULL in case of failure
5600 */
5601 xmlAutomataPtr
5603 xmlAutomataPtr ctxt;
5609 /* initialize the parser */
5615 }
5621 }
5625 }
5627 /**
5628 * xmlFreeAutomata:
5629 * @am: an automata
5630 *
5631 * Free an automata
5632 */
5633 void
5638 }
5640 /**
5641 * xmlAutomataSetFlags:
5642 * @am: an automata
5643 * @flags: a set of internal flags
5644 *
5645 * Set some flags on the automata
5646 */
5647 void
5652 }
5654 /**
5655 * xmlAutomataGetInitState:
5656 * @am: an automata
5657 *
5658 * Initial state lookup
5659 *
5660 * Returns the initial state of the automata
5661 */
5662 xmlAutomataStatePtr
5667 }
5669 /**
5670 * xmlAutomataSetFinalState:
5671 * @am: an automata
5672 * @state: a state in this automata
5673 *
5674 * Makes that state a final state
5675 *
5676 * Returns 0 or -1 in case of error
5677 */
5678 int
5684 }
5686 /**
5687 * xmlAutomataNewTransition:
5688 * @am: an automata
5689 * @from: the starting point of the transition
5690 * @to: the target point of the transition or NULL
5691 * @token: the input string associated to that transition
5692 * @data: data passed to the callback function if the transition is activated
5693 *
5694 * If @to is NULL, this creates first a new target state in the automata
5695 * and then adds a transition from the @from state to the target state
5696 * activated by the value of @token
5697 *
5698 * Returns the target state or NULL in case of error
5699 */
5700 xmlAutomataStatePtr
5704 xmlRegAtomPtr atom;
5717 }
5721 }
5723 /**
5724 * xmlAutomataNewTransition2:
5725 * @am: an automata
5726 * @from: the starting point of the transition
5727 * @to: the target point of the transition or NULL
5728 * @token: the first input string associated to that transition
5729 * @token2: the second input string associated to that transition
5730 * @data: data passed to the callback function if the transition is activated
5731 *
5732 * If @to is NULL, this creates first a new target state in the automata
5733 * and then adds a transition from the @from state to the target state
5734 * activated by the value of @token
5735 *
5736 * Returns the target state or NULL in case of error
5737 */
5738 xmlAutomataStatePtr
5742 xmlRegAtomPtr atom;
5763 }
5770 }
5775 }
5779 }
5781 /**
5782 * xmlAutomataNewNegTrans:
5783 * @am: an automata
5784 * @from: the starting point of the transition
5785 * @to: the target point of the transition or NULL
5786 * @token: the first input string associated to that transition
5787 * @token2: the second input string associated to that transition
5788 * @data: data passed to the callback function if the transition is activated
5789 *
5790 * If @to is NULL, this creates first a new target state in the automata
5791 * and then adds a transition from the @from state to the target state
5792 * activated by any value except (@token,@token2)
5793 * Note that if @token2 is not NULL, then (X, NULL) won't match to follow
5794 # the semantic of XSD ##other
5795 *
5796 * Returns the target state or NULL in case of error
5797 */
5798 xmlAutomataStatePtr
5802 xmlRegAtomPtr atom;
5825 }
5832 }
5840 }
5845 }
5847 /**
5848 * xmlAutomataNewCountTrans2:
5849 * @am: an automata
5850 * @from: the starting point of the transition
5851 * @to: the target point of the transition or NULL
5852 * @token: the input string associated to that transition
5853 * @token2: the second input string associated to that transition
5854 * @min: the minimum successive occurences of token
5855 * @max: the maximum successive occurences of token
5856 * @data: data associated to the transition
5857 *
5858 * If @to is NULL, this creates first a new target state in the automata
5859 * and then adds a transition from the @from state to the target state
5860 * activated by a succession of input of value @token and @token2 and
5861 * whose number is between @min and @max
5862 *
5863 * Returns the target state or NULL in case of error
5864 */
5865 xmlAutomataStatePtr
5870 xmlRegAtomPtr atom;
5895 }
5902 }
5906 else
5910 /*
5911 * associate a counter to the transition.
5912 */
5917 /* xmlFAGenerateTransitions(am, from, to, atom); */
5921 }
5933 }
5935 /**
5936 * xmlAutomataNewCountTrans:
5937 * @am: an automata
5938 * @from: the starting point of the transition
5939 * @to: the target point of the transition or NULL
5940 * @token: the input string associated to that transition
5941 * @min: the minimum successive occurences of token
5942 * @max: the maximum successive occurences of token
5943 * @data: data associated to the transition
5944 *
5945 * If @to is NULL, this creates first a new target state in the automata
5946 * and then adds a transition from the @from state to the target state
5947 * activated by a succession of input of value @token and whose number
5948 * is between @min and @max
5949 *
5950 * Returns the target state or NULL in case of error
5951 */
5952 xmlAutomataStatePtr
5956 xmlRegAtomPtr atom;
5972 else
5976 /*
5977 * associate a counter to the transition.
5978 */
5983 /* xmlFAGenerateTransitions(am, from, to, atom); */
5987 }
5999 }
6001 /**
6002 * xmlAutomataNewOnceTrans2:
6003 * @am: an automata
6004 * @from: the starting point of the transition
6005 * @to: the target point of the transition or NULL
6006 * @token: the input string associated to that transition
6007 * @token2: the second input string associated to that transition
6008 * @min: the minimum successive occurences of token
6009 * @max: the maximum successive occurences of token
6010 * @data: data associated to the transition
6011 *
6012 * If @to is NULL, this creates first a new target state in the automata
6013 * and then adds a transition from the @from state to the target state
6014 * activated by a succession of input of value @token and @token2 and whose
6015 * number is between @min and @max, moreover that transition can only be
6016 * crossed once.
6017 *
6018 * Returns the target state or NULL in case of error
6019 */
6020 xmlAutomataStatePtr
6025 xmlRegAtomPtr atom;
6050 }
6057 }
6062 /*
6063 * associate a counter to the transition.
6064 */
6069 /* xmlFAGenerateTransitions(am, from, to, atom); */
6073 }
6078 }
6082 /**
6083 * xmlAutomataNewOnceTrans:
6084 * @am: an automata
6085 * @from: the starting point of the transition
6086 * @to: the target point of the transition or NULL
6087 * @token: the input string associated to that transition
6088 * @min: the minimum successive occurences of token
6089 * @max: the maximum successive occurences of token
6090 * @data: data associated to the transition
6091 *
6092 * If @to is NULL, this creates first a new target state in the automata
6093 * and then adds a transition from the @from state to the target state
6094 * activated by a succession of input of value @token and whose number
6095 * is between @min and @max, moreover that transition can only be crossed
6096 * once.
6097 *
6098 * Returns the target state or NULL in case of error
6099 */
6100 xmlAutomataStatePtr
6104 xmlRegAtomPtr atom;
6121 /*
6122 * associate a counter to the transition.
6123 */
6128 /* xmlFAGenerateTransitions(am, from, to, atom); */
6132 }
6137 }
6139 /**
6140 * xmlAutomataNewState:
6141 * @am: an automata
6142 *
6143 * Create a new disconnected state in the automata
6144 *
6145 * Returns the new state or NULL in case of error
6146 */
6147 xmlAutomataStatePtr
6149 xmlAutomataStatePtr to;
6156 }
6158 /**
6159 * xmlAutomataNewEpsilon:
6160 * @am: an automata
6161 * @from: the starting point of the transition
6162 * @to: the target point of the transition or NULL
6163 *
6164 * If @to is NULL, this creates first a new target state in the automata
6165 * and then adds an epsilon transition from the @from state to the
6166 * target state
6167 *
6168 * Returns the target state or NULL in case of error
6169 */
6170 xmlAutomataStatePtr
6172 xmlAutomataStatePtr to) {
6179 }
6181 /**
6182 * xmlAutomataNewAllTrans:
6183 * @am: an automata
6184 * @from: the starting point of the transition
6185 * @to: the target point of the transition or NULL
6186 * @lax: allow to transition if not all all transitions have been activated
6187 *
6188 * If @to is NULL, this creates first a new target state in the automata
6189 * and then adds a an ALL transition from the @from state to the
6190 * target state. That transition is an epsilon transition allowed only when
6191 * all transitions from the @from node have been activated.
6192 *
6193 * Returns the target state or NULL in case of error
6194 */
6195 xmlAutomataStatePtr
6204 }
6206 /**
6207 * xmlAutomataNewCounter:
6208 * @am: an automata
6209 * @min: the minimal value on the counter
6210 * @max: the maximal value on the counter
6211 *
6212 * Create a new counter
6213 *
6214 * Returns the counter number or -1 in case of error
6215 */
6216 int
6229 }
6231 /**
6232 * xmlAutomataNewCountedTrans:
6233 * @am: an automata
6234 * @from: the starting point of the transition
6235 * @to: the target point of the transition or NULL
6236 * @counter: the counter associated to that transition
6237 *
6238 * If @to is NULL, this creates first a new target state in the automata
6239 * and then adds an epsilon transition from the @from state to the target state
6240 * which will increment the counter provided
6241 *
6242 * Returns the target state or NULL in case of error
6243 */
6244 xmlAutomataStatePtr
6253 }
6255 /**
6256 * xmlAutomataNewCounterTrans:
6257 * @am: an automata
6258 * @from: the starting point of the transition
6259 * @to: the target point of the transition or NULL
6260 * @counter: the counter associated to that transition
6261 *
6262 * If @to is NULL, this creates first a new target state in the automata
6263 * and then adds an epsilon transition from the @from state to the target state
6264 * which will be allowed only if the counter is within the right range.
6265 *
6266 * Returns the target state or NULL in case of error
6267 */
6268 xmlAutomataStatePtr
6277 }
6279 /**
6280 * xmlAutomataCompile:
6281 * @am: an automata
6282 *
6283 * Compile the automata into a Reg Exp ready for being executed.
6284 * The automata should be free after this point.
6285 *
6286 * Returns the compiled regexp or NULL in case of error
6287 */
6288 xmlRegexpPtr
6290 xmlRegexpPtr ret;
6294 /* xmlFAComputesDeterminism(am); */
6298 }
6300 /**
6301 * xmlAutomataIsDeterminist:
6302 * @am: an automata
6303 *
6304 * Checks if an automata is determinist.
6305 *
6306 * Returns 1 if true, 0 if not, and -1 in case of error
6307 */
6308 int
6317 }
6320 #ifdef LIBXML_EXPR_ENABLED
6321 /************************************************************************
6322 * *
6323 * Formal Expression handling code *
6324 * *
6325 ************************************************************************/
6326 /************************************************************************
6327 * *
6328 * Expression handling context *
6329 * *
6330 ************************************************************************/
6333 xmlDictPtr dict;
6343 };
6345 /**
6346 * xmlExpNewCtxt:
6347 * @maxNodes: the maximum number of nodes
6348 * @dict: optional dictionnary to use internally
6349 *
6350 * Creates a new context for manipulating expressions
6351 *
6352 * Returns the context or NULL in case of error
6353 */
6354 xmlExpCtxtPtr
6356 xmlExpCtxtPtr ret;
6373 }
6381 }
6385 }
6387 }
6389 /**
6390 * xmlExpFreeCtxt:
6391 * @ctxt: an expression context
6392 *
6393 * Free an expression context
6394 */
6395 void
6403 }
6405 /************************************************************************
6406 * *
6407 * Structure associated to an expression node *
6408 * *
6409 ************************************************************************/
6410 #define MAX_NODES 10000
6412 /* #define DEBUG_DERIV */
6414 /*
6415 * TODO:
6416 * - Wildcards
6417 * - public API for creation
6418 *
6419 * Started
6420 * - regression testing
6421 *
6422 * Done
6423 * - split into module and test tool
6424 * - memleaks
6425 */
6431 #define IS_NILLABLE(node) ((node)->info & XML_EXP_NILABLE)
6439 xmlExpNodePtr exp_left;
6447 xmlExpNodePtr f_right;
6451 };
6453 #define exp_min field.count.f_min
6454 #define exp_max field.count.f_max
6455 /* #define exp_left field.children.f_left */
6456 #define exp_right field.children.f_right
6457 #define exp_str field.f_str
6462 };
6466 };
6469 /************************************************************************
6470 * *
6471 * The custom hash table for unicity and canonicalization *
6472 * of sub-expressions pointers *
6473 * *
6474 ************************************************************************/
6475 /*
6476 * xmlExpHashNameComputeKey:
6477 * Calculate the hash key for a token
6478 */
6479 static unsigned short
6488 }
6489 }
6491 }
6493 /*
6494 * xmlExpHashComputeKey:
6495 * Calculate the hash key for a compound expression
6496 */
6497 static unsigned short
6499 xmlExpNodePtr right) {
6523 }
6525 }
6528 static xmlExpNodePtr
6530 xmlExpNodePtr ret;
6543 }
6545 /**
6546 * xmlExpHashGetEntry:
6547 * @table: the hash table
6548 *
6549 * Get the unique entry from the hash table. The entry is created if
6550 * needed. @left and @right are consumed, i.e. their ref count will
6551 * be decremented by the operation.
6552 *
6553 * Returns the pointer or NULL in case of error
6554 */
6555 static xmlExpNodePtr
6560 xmlExpNodePtr entry;
6561 xmlExpNodePtr insert;
6566 /*
6567 * Check for duplicate and insertion location.
6568 */
6572 /* COUNT reduction rule 1 */
6573 /* a{1} -> a */
6577 }
6581 }
6582 }
6586 }
6589 else
6593 /* Forbid reduction rules */
6597 }
6601 }
6603 /* OR reduction rule 1 */
6604 /* a | a reduced to a */
6608 }
6609 /* OR canonicalization rule 1 */
6610 /* linearize (a | b) | c into a | (b | c) */
6615 }
6616 /* OR reduction rule 2 */
6617 /* a | (a | b) and b | (a | b) are reduced to a | b */
6623 }
6624 }
6625 /* OR canonicalization rule 2 */
6626 /* linearize (a | b) | c into a | (b | c) */
6628 xmlExpNodePtr tmp;
6630 /* OR canonicalization rule 2 */
6636 }
6646 }
6648 /* Ordering in the tree */
6649 /* C | (A | B) -> A | (B | C) */
6651 xmlExpNodePtr tmp;
6660 }
6661 /* Ordering in the tree */
6662 /* B | (A | C) -> A | (B | C) */
6664 xmlExpNodePtr tmp;
6673 }
6674 }
6675 /* we know both types are != XML_EXP_OR here */
6680 }
6683 /* Forbid reduction rules */
6687 }
6691 }
6692 /* Empty reduction rules */
6695 }
6698 }
6713 }
6720 }
6727 }
6728 }
6729 }
6730 }
6747 else
6760 else
6768 else
6770 }
6771 }
6780 }
6782 /**
6783 * xmlExpFree:
6784 * @ctxt: the expression context
6785 * @exp: the expression
6786 *
6787 * Dereference the expression
6788 */
6789 void
6797 /* Unlink it first from the hash table */
6802 xmlExpNodePtr tmp;
6809 }
6811 }
6812 }
6819 }
6822 }
6823 }
6825 /**
6826 * xmlExpRef:
6827 * @exp: the expression
6828 *
6829 * Increase the reference count of the expression
6830 */
6831 void
6835 }
6837 /**
6838 * xmlExpNewAtom:
6839 * @ctxt: the expression context
6840 * @name: the atom name
6841 * @len: the atom name length in byte (or -1);
6842 *
6843 * Get the atom associated to this name from that context
6844 *
6845 * Returns the node or NULL in case of error
6846 */
6847 xmlExpNodePtr
6855 }
6857 /**
6858 * xmlExpNewOr:
6859 * @ctxt: the expression context
6860 * @left: left expression
6861 * @right: right expression
6862 *
6863 * Get the atom associated to the choice @left | @right
6864 * Note that @left and @right are consumed in the operation, to keep
6865 * an handle on them use xmlExpRef() and use xmlExpFree() to release them,
6866 * this is true even in case of failure (unless ctxt == NULL).
6867 *
6868 * Returns the node or NULL in case of error
6869 */
6870 xmlExpNodePtr
6878 }
6880 }
6882 /**
6883 * xmlExpNewSeq:
6884 * @ctxt: the expression context
6885 * @left: left expression
6886 * @right: right expression
6887 *
6888 * Get the atom associated to the sequence @left , @right
6889 * Note that @left and @right are consumed in the operation, to keep
6890 * an handle on them use xmlExpRef() and use xmlExpFree() to release them,
6891 * this is true even in case of failure (unless ctxt == NULL).
6892 *
6893 * Returns the node or NULL in case of error
6894 */
6895 xmlExpNodePtr
6903 }
6905 }
6907 /**
6908 * xmlExpNewRange:
6909 * @ctxt: the expression context
6910 * @subset: the expression to be repeated
6911 * @min: the lower bound for the repetition
6912 * @max: the upper bound for the repetition, -1 means infinite
6913 *
6914 * Get the atom associated to the range (@subset){@min, @max}
6915 * Note that @subset is consumed in the operation, to keep
6916 * an handle on it use xmlExpRef() and use xmlExpFree() to release it,
6917 * this is true even in case of failure (unless ctxt == NULL).
6918 *
6919 * Returns the node or NULL in case of error
6920 */
6921 xmlExpNodePtr
6929 }
6932 }
6934 /************************************************************************
6935 * *
6936 * Public API for operations on expressions *
6937 * *
6938 ************************************************************************/
6940 static int
6944 tail:
6969 }
6971 }
6973 /**
6974 * xmlExpGetLanguage:
6975 * @ctxt: the expression context
6976 * @exp: the expression
6977 * @langList: where to store the tokens
6978 * @len: the allocated length of @list
6979 *
6980 * Find all the strings used in @exp and store them in @list
6981 *
6982 * Returns the number of unique strings found, -1 in case of errors and
6983 * -2 if there is more than @len strings
6984 */
6985 int
6991 }
6993 static int
6997 tail:
7024 }
7035 }
7037 }
7039 /**
7040 * xmlExpGetStart:
7041 * @ctxt: the expression context
7042 * @exp: the expression
7043 * @tokList: where to store the tokens
7044 * @len: the allocated length of @list
7045 *
7046 * Find all the strings that appears at the start of the languages
7047 * accepted by @exp and store them in @list. E.g. for (a, b) | c
7048 * it will return the list [a, c]
7049 *
7050 * Returns the number of unique strings found, -1 in case of errors and
7051 * -2 if there is more than @len strings
7052 */
7053 int
7059 }
7061 /**
7062 * xmlExpIsNillable:
7063 * @exp: the expression
7064 *
7065 * Finds if the expression is nillable, i.e. if it accepts the empty sequqnce
7066 *
7067 * Returns 1 if nillable, 0 if not and -1 in case of error
7068 */
7069 int
7074 }
7076 static xmlExpNodePtr
7078 {
7079 xmlExpNodePtr ret;
7088 #ifdef DEBUG_DERIV
7090 #endif
7093 #ifdef DEBUG_DERIV
7095 #endif
7096 /* TODO wildcards here */
7098 }
7101 xmlExpNodePtr tmp;
7103 #ifdef DEBUG_DERIV
7105 #endif
7109 }
7114 }
7118 }
7120 #ifdef DEBUG_DERIV
7122 #endif
7128 #ifdef DEBUG_DERIV
7130 #endif
7132 }
7134 #ifdef DEBUG_DERIV
7136 #endif
7140 }
7144 xmlExpNodePtr tmp;
7152 #ifdef DEBUG_DERIV
7154 #endif
7156 }
7161 else
7165 else
7171 #ifdef DEBUG_DERIV
7173 #endif
7175 }
7176 #ifdef DEBUG_DERIV
7178 #endif
7181 }
7182 }
7184 }
7186 /**
7187 * xmlExpStringDerive:
7188 * @ctxt: the expression context
7189 * @exp: the expression
7190 * @str: the string
7191 * @len: the string len in bytes if available
7192 *
7193 * Do one step of Brzozowski derivation of the expression @exp with
7194 * respect to the input string
7195 *
7196 * Returns the resulting expression or NULL in case of internal error
7197 */
7198 xmlExpNodePtr
7205 }
7206 /*
7207 * check the string is in the dictionnary, if yes use an interned
7208 * copy, otherwise we know it's not an acceptable input
7209 */
7213 }
7215 }
7217 static int
7226 }
7227 #if 0
7230 #endif
7232 }
7235 xmlExpNodePtr sub);
7236 /**
7237 * xmlExpDivide:
7238 * @ctxt: the expressions context
7239 * @exp: the englobing expression
7240 * @sub: the subexpression
7241 * @mult: the multiple expression
7242 * @remain: the remain from the derivation of the multiple
7243 *
7244 * Check if exp is a multiple of sub, i.e. if there is a finite number n
7245 * so that sub{n} subsume exp
7246 *
7247 * Returns the multiple value if successful, 0 if it is not a multiple
7248 * and -1 in case of internel error.
7249 */
7251 static int
7268 }
7272 }
7277 }
7281 else
7285 else
7287 #ifdef DEBUG_DERIV
7289 #endif
7291 }
7294 }
7295 #ifdef DEBUG_DERIV
7297 #endif
7299 }
7301 /**
7302 * xmlExpExpDeriveInt:
7303 * @ctxt: the expressions context
7304 * @exp: the englobing expression
7305 * @sub: the subexpression
7306 *
7307 * Try to do a step of Brzozowski derivation but at a higher level
7308 * the input being a subexpression.
7309 *
7310 * Returns the resulting expression or NULL in case of internal error
7311 */
7312 static xmlExpNodePtr
7318 /*
7319 * In case of equality and if the expression can only consume a finite
7320 * amount, then the derivation is empty
7321 */
7323 #ifdef DEBUG_DERIV
7325 #endif
7327 }
7328 /*
7329 * decompose sub sequence first
7330 */
7332 #ifdef DEBUG_DERIV
7334 #endif
7337 }
7339 #ifdef DEBUG_DERIV
7341 #endif
7350 }
7352 #ifdef DEBUG_DERIV
7354 #endif
7364 }
7366 }
7368 #ifdef DEBUG_DERIV
7370 #endif
7372 }
7377 #ifdef DEBUG_DERIV
7379 #endif
7382 #ifdef DEBUG_DERIV
7384 #endif
7388 /* TODO: handle wildcards */
7390 #ifdef DEBUG_DERIV
7392 #endif
7394 }
7395 #ifdef DEBUG_DERIV
7397 #endif
7399 }
7403 /* TODO: handle wildcards */
7405 #ifdef DEBUG_DERIV
7407 #endif
7409 }
7410 #ifdef DEBUG_DERIV
7412 #endif
7414 }
7415 #ifdef DEBUG_DERIV
7417 #endif
7420 /* try to get the sequence consumed only if possible */
7422 /* See if the sequence can be consumed directly */
7423 #ifdef DEBUG_DERIV
7425 #endif
7428 #ifdef DEBUG_DERIV
7430 #endif
7431 /*
7432 * TODO: assumption here that we are determinist
7433 * i.e. we won't get to a nillable exp left
7434 * subset which could be matched by the right
7435 * part too.
7436 * e.g.: (a | b)+,(a | c) and 'a+,a'
7437 */
7441 }
7442 #ifdef DEBUG_DERIV
7445 #endif
7446 }
7447 /* Try instead to decompose */
7451 #ifdef DEBUG_DERIV
7453 #endif
7458 #ifdef DEBUG_DERIV
7460 #endif
7463 else
7467 else
7481 }
7486 }
7487 }
7488 /* we made no progress on structured operations */
7491 #ifdef DEBUG_DERIV
7493 #endif
7501 }
7507 /*
7508 * Try to see if the loop is completely subsumed
7509 */
7516 #ifdef DEBUG_DERIV
7518 #endif
7522 #ifdef DEBUG_DERIV
7524 #endif
7526 }
7532 else
7535 #ifdef DEBUG_DERIV
7537 #endif
7540 }
7543 #ifdef DEBUG_DERIV
7545 #endif
7552 }
7555 #ifdef DEBUG_DERIV
7557 #endif
7560 }
7563 else
7566 }
7567 }
7569 /*
7570 * TODO: loop here to try to grow if working on finite
7571 * blocks.
7572 */
7573 #ifdef DEBUG_DERIV
7575 #endif
7581 #ifdef DEBUG_DERIV
7583 #endif
7587 #ifdef DEBUG_DERIV
7589 #endif
7592 }
7594 #ifdef DEBUG_DERIV
7596 #endif
7602 }
7605 #ifdef DEBUG_DERIV
7607 #endif
7614 }
7617 #ifdef DEBUG_DERIV
7619 #endif
7622 }
7625 else
7628 }
7629 }
7630 #ifdef DEBUG_DERIV
7632 #endif
7638 }
7642 }
7647 #ifdef DEBUG_DERIV
7649 #endif
7651 }
7654 else
7658 else
7661 #ifdef DEBUG_DERIV
7663 #endif
7672 }
7673 }
7675 #ifdef DEBUG_DERIV
7677 #endif
7681 else
7685 /*
7686 * here the structured derivation made no progress so
7687 * we use the default token based derivation to force one more step
7688 */
7696 }
7698 /*
7699 * collect all the strings accepted by the subexpression on input
7700 */
7709 }
7713 }
7720 }
7727 }
7736 }
7745 }
7746 }
7747 }
7750 }
7752 /**
7753 * xmlExpExpDerive:
7754 * @ctxt: the expressions context
7755 * @exp: the englobing expression
7756 * @sub: the subexpression
7757 *
7758 * Evaluates the expression resulting from @exp consuming a sub expression @sub
7759 * Based on algebraic derivation and sometimes direct Brzozowski derivation
7760 * it usually tatkes less than linear time and can handle expressions generating
7761 * infinite languages.
7762 *
7763 * Returns the resulting expression or NULL in case of internal error, the
7764 * result must be freed
7765 */
7766 xmlExpNodePtr
7771 /*
7772 * O(1) speedups
7773 */
7775 #ifdef DEBUG_DERIV
7777 #endif
7779 }
7781 #ifdef DEBUG_DERIV
7783 #endif
7785 }
7787 }
7789 /**
7790 * xmlExpSubsume:
7791 * @ctxt: the expressions context
7792 * @exp: the englobing expression
7793 * @sub: the subexpression
7794 *
7795 * Check whether @exp accepts all the languages accexpted by @sub
7796 * the input being a subexpression.
7797 *
7798 * Returns 1 if true 0 if false and -1 in case of failure.
7799 */
7800 int
7802 xmlExpNodePtr tmp;
7807 /*
7808 * TODO: speedup by checking the language of sub is a subset of the
7809 * language of exp
7810 */
7811 /*
7812 * O(1) speedups
7813 */
7815 #ifdef DEBUG_DERIV
7817 #endif
7819 }
7821 #ifdef DEBUG_DERIV
7823 #endif
7825 }
7827 #ifdef DEBUG_DERIV
7830 #endif
7840 }
7843 }
7845 /************************************************************************
7846 * *
7847 * Parsing expression *
7848 * *
7849 ************************************************************************/
7853 #undef CUR
7854 #define CUR (*ctxt->cur)
7855 #undef NEXT
7856 #define NEXT ctxt->cur++;
7857 #undef IS_BLANK
7859 #define SKIP_BLANKS while (IS_BLANK(*ctxt->cur)) ctxt->cur++;
7861 static int
7865 SKIP_BLANKS
7867 NEXT
7869 }
7874 NEXT
7875 }
7877 }
7879 static xmlExpNodePtr
7882 xmlExpNodePtr ret;
7885 SKIP_BLANKS
7888 NEXT
7890 SKIP_BLANKS
7895 }
7896 NEXT;
7897 SKIP_BLANKS
7899 }
7903 NEXT;
7910 SKIP_BLANKS
7911 parse_quantifier:
7915 NEXT
7920 }
7921 SKIP_BLANKS
7923 NEXT
7925 SKIP_BLANKS
7931 }
7932 NEXT
7935 SKIP_BLANKS
7937 NEXT
7940 SKIP_BLANKS
7942 NEXT
7945 SKIP_BLANKS
7947 NEXT
7950 SKIP_BLANKS
7951 }
7953 }
7956 static xmlExpNodePtr
7961 SKIP_BLANKS
7963 NEXT
7968 }
7972 }
7974 }
7976 static xmlExpNodePtr
7981 SKIP_BLANKS
7983 NEXT
7988 }
7992 }
7994 }
7996 /**
7997 * xmlExpParse:
7998 * @ctxt: the expressions context
7999 * @expr: the 0 terminated string
8000 *
8001 * Minimal parser for regexps, it understand the following constructs
8002 * - string terminals
8003 * - choice operator |
8004 * - sequence operator ,
8005 * - subexpressions (...)
8006 * - usual cardinality operators + * and ?
8007 * - finite sequences { min, max }
8008 * - infinite sequences { min, * }
8009 * There is minimal checkings made especially no checking on strings values
8010 *
8011 * Returns a new expression or NULL in case of failure
8012 */
8013 xmlExpNodePtr
8015 xmlExpNodePtr ret;
8021 SKIP_BLANKS
8025 }
8027 }
8029 static void
8031 xmlExpNodePtr c;
8049 else
8055 else
8062 else
8068 else
8077 else
8094 }
8098 }
8101 }
8104 }
8105 /**
8106 * xmlExpDump:
8107 * @buf: a buffer to receive the output
8108 * @expr: the compiled expression
8109 *
8110 * Serialize the expression as compiled to the buffer
8111 */
8112 void
8117 }
8119 /**
8120 * xmlExpMaxToken:
8121 * @expr: a compiled expression
8122 *
8123 * Indicate the maximum number of input a expression can accept
8124 *
8125 * Returns the maximum length or -1 in case of error
8126 */
8127 int
8132 }
8134 /**
8135 * xmlExpCtxtNbNodes:
8136 * @ctxt: an expression context
8137 *
8138 * Debugging facility provides the number of allocated nodes at a that point
8139 *
8140 * Returns the number of nodes in use or -1 in case of error
8141 */
8142 int
8147 }
8149 /**
8150 * xmlExpCtxtNbCons:
8151 * @ctxt: an expression context
8152 *
8153 * Debugging facility provides the number of allocated nodes over lifetime
8154 *
8155 * Returns the number of nodes ever allocated or -1 in case of error
8156 */
8157 int
8162 }
8165 #define bottom_xmlregexp