GNOME Bugzilla – Bug 362989
xmlFAReduceEpsilonTransitions (in xmlregexp.c) in infinite loop (recursive call to itself)
Last modified: 2006-11-02 13:10:22 UTC
Please describe the problem: when validating an XML schema file using libxml2, the program gets into loop. Debugging shows that it's xmlFAReduceEpsilonTransitions calling itself recursively. It seems the bigger the schema file, the longer xmlFAReduceEpsilonTransitions takes to finish, and when the file size gets to some point, it never returns. So the recursive logic needs to be looked at. This happens in libxml2.6.26. The sympotom is different in libxml2.6.22, there I got out of memory error. I've managed to trim down the size of the schema file from 160K to 22K and the problem still happens. If I trim the file further, I don't see the problem. For example, I trimed down the file to 18K, then it worked, though it took long time to finish. Steps to reproduce: 1. source code snippet: xmlDocPtr doc; xmlSchemaPtr schema = NULL; xmlSchemaValidCtxtPtr validCtxtPtr; xmlSchemaParserCtxtPtr parserCtxtPtr; //schema handling parserCtxtPtr=xmlSchemaNewParserCtxt("./x.xsd"); if ( parserCtxtPtr==NULL ) { printf("Can't get schema.\n"); return 0; } xmlSchemaSetParserErrors(parserCtxtPtr, (xmlSchemaValidityErrorFunc)fprintf, (xmlSchemaValidityWarningFunc)fprintf, stderr); schema=xmlSchemaParse(parserCtxtPtr); if ( schema==NULL ) { printf("Can't get schema.\n"); xmlSchemaFreeParserCtxt(parserCtxtPtr); return 0; } else printf("schema loaded.\n"); Actual results: If you put the above source code in a main() and run it, you will see the program doesn't return -- infinite loop Expected results: You see the program stuck. Does this happen every time? Yes. Other information: Sorry I don't see a place to attach schema file, so here it is: <?xml version="1.0"?> <xs:schema xmlns:xs="http://www.w3.org/2001/XMLSchema" xmlns="http://www.cisco.com/test" targetNamespace="http://www.cisco.com/test" elementFormDefault="qualified"> <xs:element name="configure" type="configure_type"/> <xs:complexType name="configure_type"> <xs:sequence> <xs:group ref="optional_group" minOccurs="0" maxOccurs="1"/> <xs:element name="ip" type="ip_type" minOccurs="0"/> </xs:sequence> </xs:complexType> <xs:group name="optional_group"> <xs:sequence> <xs:element name="terminal" type="xs:string" minOccurs="0"/> </xs:sequence> </xs:group> <xs:complexType name="ip_type"> <xs:sequence> <xs:element name="access-list" type="access-list_type" minOccurs="0"/> </xs:sequence> </xs:complexType> <xs:complexType name="access-list_type"> <xs:sequence> <xs:element name="name" minOccurs="0" type="xs:string"/> <xs:group ref="block_group" minOccurs="0" maxOccurs="1"/> <xs:element name="remark" type="remark_type" minOccurs="0"/> <xs:element name="permitdeny" minOccurs="0"> <xs:simpleType> <xs:restriction base="xs:string"> <xs:enumeration value="permit"/> <xs:enumeration value="deny"/> </xs:restriction> </xs:simpleType> </xs:element> <xs:group ref="block_group_1" minOccurs="0" maxOccurs="1"/> <xs:group ref="block_group_2" minOccurs="0" maxOccurs="1"/> <xs:group ref="block_group_5" minOccurs="0" maxOccurs="1"/> <xs:group ref="block_group_8" minOccurs="0" maxOccurs="1"/> <xs:element name="proto_tcp" minOccurs="0"> <xs:simpleType> <xs:restriction base="xs:string"> <xs:enumeration value="tcp"/> </xs:restriction> </xs:simpleType> </xs:element> <xs:group ref="block_group_17" minOccurs="0" maxOccurs="1"/> <xs:group ref="optional_group_4" minOccurs="0" maxOccurs="1"/> <xs:group ref="block_group_26" minOccurs="0" maxOccurs="1"/> <xs:group ref="optional_group_5" minOccurs="0" maxOccurs="1"/> <xs:group ref="block_group_35" minOccurs="0" maxOccurs="1"/> <xs:element name="proto_udp" minOccurs="0"> <xs:simpleType> <xs:restriction base="xs:string"> <xs:enumeration value="udp"/> </xs:restriction> </xs:simpleType> </xs:element> <xs:group ref="block_group_44" minOccurs="0" maxOccurs="1"/> <xs:element name="proto_igmp" minOccurs="0"> <xs:simpleType> <xs:restriction base="xs:string"> <xs:enumeration value="igmp"/> </xs:restriction> </xs:simpleType> </xs:element> <xs:element name="proto_icmp" minOccurs="0"> <xs:simpleType> <xs:restriction base="xs:string"> <xs:enumeration value="icmp"/> </xs:restriction> </xs:simpleType> </xs:element> </xs:sequence> </xs:complexType> <xs:group name="block_group"> <xs:choice> <xs:group ref="optional_group_1" minOccurs="0" maxOccurs="1"/> <xs:element name="no" type="xs:string" minOccurs="0"/> </xs:choice> </xs:group> <xs:group name="optional_group_1"> <xs:sequence> <xs:element name="seqno" minOccurs="0" type="xs:unsignedInt"/> </xs:sequence> </xs:group> <xs:complexType name="remark_type"> <xs:sequence> <xs:element name="comment" minOccurs="0" type="xs:string"/> </xs:sequence> </xs:complexType> <xs:group name="block_group_1"> <xs:choice> <xs:element name="ip" type="xs:string" minOccurs="0"/> <xs:element name="proto" minOccurs="0"> <xs:simpleType> <xs:restriction base="xs:unsignedInt"> <xs:minInclusive value="0"/> <xs:maxInclusive value="255"/> </xs:restriction> </xs:simpleType> </xs:element> </xs:choice> </xs:group> <xs:group name="block_group_2"> <xs:choice> <xs:element name="src_any" minOccurs="0"> <xs:simpleType> <xs:restriction base="xs:string"> <xs:enumeration value="any"/> </xs:restriction> </xs:simpleType> </xs:element> <xs:group ref="block_group_3" minOccurs="0" maxOccurs="1"/> <xs:element name="src_prefix" minOccurs="0" type="xs:string"/> <xs:group ref="block_group_4" minOccurs="0" maxOccurs="1"/> </xs:choice> </xs:group> <xs:group name="block_group_3"> <xs:sequence> <xs:element name="src_addr" minOccurs="0" type="xs:string"/> <xs:element name="src_wild" minOccurs="0" type="xs:string"/> </xs:sequence> </xs:group> <xs:group name="block_group_4"> <xs:sequence> <xs:element name="host" type="host_type" minOccurs="0"/> </xs:sequence> </xs:group> <xs:complexType name="host_type"> <xs:sequence> <xs:element name="src_host" minOccurs="0" type="xs:string"/> </xs:sequence> </xs:complexType> <xs:group name="block_group_5"> <xs:choice> <xs:element name="dst_any" minOccurs="0"> <xs:simpleType> <xs:restriction base="xs:string"> <xs:enumeration value="any"/> </xs:restriction> </xs:simpleType> </xs:element> <xs:group ref="block_group_6" minOccurs="0" maxOccurs="1"/> <xs:element name="dst_prefix" minOccurs="0" type="xs:string"/> <xs:group ref="block_group_7" minOccurs="0" maxOccurs="1"/> </xs:choice> </xs:group> <xs:group name="block_group_6"> <xs:sequence> <xs:element name="dst_addr" minOccurs="0" type="xs:string"/> <xs:element name="dst_wild" minOccurs="0" type="xs:string"/> </xs:sequence> </xs:group> <xs:group name="block_group_7"> <xs:sequence> <xs:element name="host" type="host_type_1" minOccurs="0"/> </xs:sequence> </xs:group> <xs:complexType name="host_type_1"> <xs:sequence> <xs:element name="dst_host" minOccurs="0" type="xs:string"/> </xs:sequence> </xs:complexType> <xs:group name="block_group_8"> <xs:choice> <xs:group ref="block_group_9" minOccurs="0" maxOccurs="unbounded"/> <xs:group ref="block_group_12" minOccurs="0" maxOccurs="unbounded"/> </xs:choice> </xs:group> <xs:group name="block_group_9"> <xs:sequence> <xs:group ref="optional_group_2" minOccurs="0" maxOccurs="1"/> </xs:sequence> </xs:group> <xs:group name="optional_group_2"> <xs:choice> <xs:element name="fragments" type="xs:string" minOccurs="0"/> <xs:element name="log" type="xs:string" minOccurs="0"/> <xs:group ref="block_group_10" minOccurs="0" maxOccurs="1"/> </xs:choice> </xs:group> <xs:group name="block_group_10"> <xs:sequence> <xs:element name="dscp" type="dscp_type" minOccurs="0"/> </xs:sequence> </xs:group> <xs:complexType name="dscp_type"> <xs:sequence> <xs:group ref="block_group_11" minOccurs="0" maxOccurs="1"/> </xs:sequence> </xs:complexType> <xs:group name="block_group_11"> <xs:choice> <xs:element name="dscp_num" minOccurs="0"> <xs:simpleType> <xs:restriction base="xs:integer"> <xs:minInclusive value="0"/> <xs:maxInclusive value="63"/> </xs:restriction> </xs:simpleType> </xs:element> <xs:element name="dscp_str" minOccurs="0" type="xs:string"/> </xs:choice> </xs:group> <xs:group name="block_group_12"> <xs:sequence> <xs:group ref="optional_group_3" minOccurs="0" maxOccurs="1"/> </xs:sequence> </xs:group> <xs:group name="optional_group_3"> <xs:choice> <xs:element name="fragments" type="xs:string" minOccurs="0"/> <xs:element name="log" type="xs:string" minOccurs="0"/> <xs:group ref="block_group_15" minOccurs="0" maxOccurs="1"/> </xs:choice> </xs:group> <xs:group name="block_group_15"> <xs:sequence> <xs:element name="precedence" type="precedence_type" minOccurs="0"/> </xs:sequence> </xs:group> <xs:complexType name="precedence_type"> <xs:sequence> <xs:group ref="block_group_16" minOccurs="0" maxOccurs="1"/> </xs:sequence> </xs:complexType> <xs:group name="block_group_16"> <xs:choice> <xs:element name="prec_num" minOccurs="0"> <xs:simpleType> <xs:restriction base="xs:integer"> <xs:minInclusive value="0"/> <xs:maxInclusive value="7"/> </xs:restriction> </xs:simpleType> </xs:element> <xs:element name="prec_str" minOccurs="0"> <xs:simpleType> <xs:restriction base="xs:string"> <xs:enumeration value="routine"/> <xs:enumeration value="network"/> </xs:restriction> </xs:simpleType> </xs:element> </xs:choice> </xs:group> <xs:group name="block_group_17"> <xs:choice> <xs:element name="src_any" minOccurs="0"> <xs:simpleType> <xs:restriction base="xs:string"> <xs:enumeration value="any"/> </xs:restriction> </xs:simpleType> </xs:element> <xs:group ref="block_group_18" minOccurs="0" maxOccurs="1"/> <xs:element name="src_prefix" minOccurs="0" type="xs:string"/> <xs:group ref="block_group_19" minOccurs="0" maxOccurs="1"/> </xs:choice> </xs:group> <xs:group name="block_group_18"> <xs:sequence> <xs:element name="src_addr" minOccurs="0" type="xs:string"/> <xs:element name="src_wild" minOccurs="0" type="xs:string"/> </xs:sequence> </xs:group> <xs:group name="block_group_19"> <xs:sequence> <xs:element name="host" type="host_type_2" minOccurs="0"/> </xs:sequence> </xs:group> <xs:complexType name="host_type_2"> <xs:sequence> <xs:element name="src_host" minOccurs="0" type="xs:string"/> </xs:sequence> </xs:complexType> <xs:group name="optional_group_4"> <xs:sequence> <xs:group ref="block_group_20" minOccurs="0" maxOccurs="1"/> </xs:sequence> </xs:group> <xs:group name="block_group_20"> <xs:choice> <xs:group ref="block_group_21" minOccurs="0" maxOccurs="1"/> <xs:group ref="block_group_23" minOccurs="0" maxOccurs="1"/> </xs:choice> </xs:group> <xs:group name="block_group_21"> <xs:sequence> <xs:element name="src_port_op" minOccurs="0"> <xs:simpleType> <xs:restriction base="xs:string"> <xs:enumeration value="lt"/> <xs:enumeration value="gt"/> <xs:enumeration value="eq"/> <xs:enumeration value="neq"/> </xs:restriction> </xs:simpleType> </xs:element> <xs:group ref="block_group_22" minOccurs="0" maxOccurs="1"/> </xs:sequence> </xs:group> <xs:group name="block_group_22"> <xs:choice> <xs:element name="src_port1" minOccurs="0"> <xs:simpleType> <xs:restriction base="xs:integer"> <xs:minInclusive value="0"/> <xs:maxInclusive value="65535"/> </xs:restriction> </xs:simpleType> </xs:element> <xs:element name="src_port1_str" minOccurs="0" type="xs:string"/> </xs:choice> </xs:group> <xs:group name="block_group_23"> <xs:sequence> <xs:element name="src_port_range" minOccurs="0"> <xs:simpleType> <xs:restriction base="xs:string"> <xs:enumeration value="range"/> </xs:restriction> </xs:simpleType> </xs:element> <xs:group ref="block_group_24" minOccurs="0" maxOccurs="1"/> <xs:group ref="block_group_25" minOccurs="0" maxOccurs="1"/> </xs:sequence> </xs:group> <xs:group name="block_group_24"> <xs:choice> <xs:element name="src_port1" minOccurs="0"> <xs:simpleType> <xs:restriction base="xs:integer"> <xs:minInclusive value="0"/> <xs:maxInclusive value="65535"/> </xs:restriction> </xs:simpleType> </xs:element> <xs:element name="src_port1_str" minOccurs="0" type="xs:string"/> </xs:choice> </xs:group> <xs:group name="block_group_25"> <xs:choice> <xs:element name="src_port2" minOccurs="0"> <xs:simpleType> <xs:restriction base="xs:integer"> <xs:minInclusive value="0"/> <xs:maxInclusive value="65535"/> </xs:restriction> </xs:simpleType> </xs:element> <xs:element name="src_port2_str" minOccurs="0" type="xs:string"/> </xs:choice> </xs:group> <xs:group name="block_group_26"> <xs:choice> <xs:element name="dst_any" minOccurs="0"> <xs:simpleType> <xs:restriction base="xs:string"> <xs:enumeration value="any"/> </xs:restriction> </xs:simpleType> </xs:element> <xs:group ref="block_group_27" minOccurs="0" maxOccurs="1"/> <xs:element name="dst_prefix" minOccurs="0" type="xs:string"/> <xs:group ref="block_group_28" minOccurs="0" maxOccurs="1"/> </xs:choice> </xs:group> <xs:group name="block_group_27"> <xs:sequence> <xs:element name="dst_addr" minOccurs="0" type="xs:string"/> <xs:element name="dst_wild" minOccurs="0" type="xs:string"/> </xs:sequence> </xs:group> <xs:group name="block_group_28"> <xs:sequence> <xs:element name="host" type="host_type_3" minOccurs="0"/> </xs:sequence> </xs:group> <xs:complexType name="host_type_3"> <xs:sequence> <xs:element name="dst_host" minOccurs="0" type="xs:string"/> </xs:sequence> </xs:complexType> <xs:group name="optional_group_5"> <xs:sequence> <xs:group ref="block_group_29" minOccurs="0" maxOccurs="1"/> </xs:sequence> </xs:group> <xs:group name="block_group_29"> <xs:choice> <xs:group ref="block_group_30" minOccurs="0" maxOccurs="1"/> <xs:group ref="block_group_32" minOccurs="0" maxOccurs="1"/> </xs:choice> </xs:group> <xs:group name="block_group_30"> <xs:sequence> <xs:element name="dst_port_op" minOccurs="0"> <xs:simpleType> <xs:restriction base="xs:string"> <xs:enumeration value="lt"/> <xs:enumeration value="gt"/> <xs:enumeration value="eq"/> <xs:enumeration value="neq"/> </xs:restriction> </xs:simpleType> </xs:element> <xs:group ref="block_group_31" minOccurs="0" maxOccurs="1"/> </xs:sequence> </xs:group> <xs:group name="block_group_31"> <xs:choice> <xs:element name="dst_port1" minOccurs="0"> <xs:simpleType> <xs:restriction base="xs:integer"> <xs:minInclusive value="0"/> <xs:maxInclusive value="65535"/> </xs:restriction> </xs:simpleType> </xs:element> <xs:element name="dst_port1_str" minOccurs="0" type="xs:string"/> </xs:choice> </xs:group> <xs:group name="block_group_32"> <xs:sequence> <xs:element name="dst_port_range" minOccurs="0"> <xs:simpleType> <xs:restriction base="xs:string"> <xs:enumeration value="range"/> </xs:restriction> </xs:simpleType> </xs:element> <xs:group ref="block_group_33" minOccurs="0" maxOccurs="1"/> <xs:group ref="block_group_34" minOccurs="0" maxOccurs="1"/> </xs:sequence> </xs:group> <xs:group name="block_group_33"> <xs:choice> <xs:element name="dst_port1" minOccurs="0"> <xs:simpleType> <xs:restriction base="xs:integer"> <xs:minInclusive value="0"/> <xs:maxInclusive value="65535"/> </xs:restriction> </xs:simpleType> </xs:element> <xs:element name="dst_port1_str" minOccurs="0" type="xs:string"/> </xs:choice> </xs:group> <xs:group name="block_group_34"> <xs:choice> <xs:element name="dst_port2" minOccurs="0"> <xs:simpleType> <xs:restriction base="xs:integer"> <xs:minInclusive value="0"/> <xs:maxInclusive value="65535"/> </xs:restriction> </xs:simpleType> </xs:element> <xs:element name="dst_port2_str" minOccurs="0" type="xs:string"/> </xs:choice> </xs:group> <xs:group name="block_group_35"> <xs:choice> <xs:group ref="block_group_36" minOccurs="0" maxOccurs="unbounded"/> <xs:group ref="block_group_39" minOccurs="0" maxOccurs="unbounded"/> </xs:choice> </xs:group> <xs:group name="block_group_36"> <xs:sequence> <xs:group ref="optional_group_6" minOccurs="0" maxOccurs="1"/> </xs:sequence> </xs:group> <xs:group name="optional_group_6"> <xs:choice> <xs:element name="fragments" type="xs:string" minOccurs="0"/> <xs:element name="log" type="xs:string" minOccurs="0"/> <xs:element name="urg" type="xs:string" minOccurs="0"/> <xs:element name="ack" type="xs:string" minOccurs="0"/> <xs:element name="psh" type="xs:string" minOccurs="0"/> <xs:element name="rst" type="xs:string" minOccurs="0"/> <xs:element name="syn" type="xs:string" minOccurs="0"/> <xs:element name="fin" type="xs:string" minOccurs="0"/> <xs:element name="established" type="xs:string" minOccurs="0"/> <xs:group ref="block_group_37" minOccurs="0" maxOccurs="1"/> </xs:choice> </xs:group> <xs:group name="block_group_37"> <xs:sequence> <xs:element name="dscp" type="dscp_type_1" minOccurs="0"/> </xs:sequence> </xs:group> <xs:complexType name="dscp_type_1"> <xs:sequence> <xs:group ref="block_group_38" minOccurs="0" maxOccurs="1"/> </xs:sequence> </xs:complexType> <xs:group name="block_group_38"> <xs:choice> <xs:element name="dscp_num" minOccurs="0"> <xs:simpleType> <xs:restriction base="xs:integer"> <xs:minInclusive value="0"/> <xs:maxInclusive value="63"/> </xs:restriction> </xs:simpleType> </xs:element> <xs:element name="dscp_str" minOccurs="0" type="xs:string"/> </xs:choice> </xs:group> <xs:group name="block_group_39"> <xs:sequence> <xs:group ref="optional_group_7" minOccurs="0" maxOccurs="1"/> </xs:sequence> </xs:group> <xs:group name="optional_group_7"> <xs:choice> <xs:element name="fragments" type="xs:string" minOccurs="0"/> <xs:element name="log" type="xs:string" minOccurs="0"/> <xs:element name="urg" type="xs:string" minOccurs="0"/> <xs:element name="ack" type="xs:string" minOccurs="0"/> <xs:element name="psh" type="xs:string" minOccurs="0"/> <xs:element name="rst" type="xs:string" minOccurs="0"/> <xs:element name="syn" type="xs:string" minOccurs="0"/> <xs:element name="fin" type="xs:string" minOccurs="0"/> <xs:element name="established" type="xs:string" minOccurs="0"/> <xs:group ref="block_group_40" minOccurs="0" maxOccurs="1"/> <xs:group ref="block_group_42" minOccurs="0" maxOccurs="1"/> </xs:choice> </xs:group> <xs:group name="block_group_40"> <xs:sequence> <xs:element name="tos" type="tos_type_1" minOccurs="0"/> </xs:sequence> </xs:group> <xs:complexType name="tos_type_1"> <xs:sequence> <xs:group ref="block_group_41" minOccurs="0" maxOccurs="1"/> </xs:sequence> </xs:complexType> <xs:group name="block_group_41"> <xs:choice> <xs:element name="tos_num" minOccurs="0"> <xs:simpleType> <xs:restriction base="xs:integer"> <xs:minInclusive value="0"/> <xs:maxInclusive value="15"/> </xs:restriction> </xs:simpleType> </xs:element> <xs:element name="tos_str" minOccurs="0"> <xs:simpleType> <xs:restriction base="xs:string"> <xs:enumeration value="normal"/> <xs:enumeration value="min-monetary-cost"/> <xs:enumeration value="max-reliability"/> <xs:enumeration value="max-throughput"/> <xs:enumeration value="min-delay"/> </xs:restriction> </xs:simpleType> </xs:element> </xs:choice> </xs:group> <xs:group name="block_group_42"> <xs:sequence> <xs:element name="precedence" type="precedence_type_1" minOccurs="0"/> </xs:sequence> </xs:group> <xs:complexType name="precedence_type_1"> <xs:sequence> <xs:group ref="block_group_43" minOccurs="0" maxOccurs="1"/> </xs:sequence> </xs:complexType> <xs:group name="block_group_43"> <xs:choice> <xs:element name="prec_num" minOccurs="0"> <xs:simpleType> <xs:restriction base="xs:integer"> <xs:minInclusive value="0"/> <xs:maxInclusive value="7"/> </xs:restriction> </xs:simpleType> </xs:element> <xs:element name="prec_str" minOccurs="0"> <xs:simpleType> <xs:restriction base="xs:string"> <xs:enumeration value="routine"/> <xs:enumeration value="priority"/> <xs:enumeration value="immediate"/> <xs:enumeration value="flash"/> <xs:enumeration value="flash-override"/> <xs:enumeration value="critical"/> <xs:enumeration value="internet"/> <xs:enumeration value="network"/> </xs:restriction> </xs:simpleType> </xs:element> </xs:choice> </xs:group> <xs:group name="block_group_44"> <xs:choice> <xs:element name="src_any" minOccurs="0"> <xs:simpleType> <xs:restriction base="xs:string"> <xs:enumeration value="any"/> </xs:restriction> </xs:simpleType> </xs:element> <xs:group ref="block_group_45" minOccurs="0" maxOccurs="1"/> <xs:element name="src_prefix" minOccurs="0" type="xs:string"/> <xs:group ref="block_group_46" minOccurs="0" maxOccurs="1"/> </xs:choice> </xs:group> <xs:group name="block_group_45"> <xs:sequence> <xs:element name="src_addr" minOccurs="0" type="xs:string"/> <xs:element name="src_wild" minOccurs="0" type="xs:string"/> </xs:sequence> </xs:group> <xs:group name="block_group_46"> <xs:sequence> <xs:element name="host" type="host_type_4" minOccurs="0"/> </xs:sequence> </xs:group> <xs:complexType name="host_type_4"> <xs:sequence> <xs:element name="src_host" minOccurs="0" type="xs:string"/> </xs:sequence> </xs:complexType> </xs:schema>
Created attachment 74900 [details] the schema file to be validated. This is the schema file used to reproduce the bug. This file is a trim-down version of my original file which is too big.
I think this is fixed in CVS. The schemas is not deterministic, that doesn't really help: paphio:~/XML -> xmllint --timing --noout --schema 362989.xsd test.xml 362989.xsd:23: element complexType: Schemas parser error : complex type 'access-list_type': The content model is not determinist. WXS schema 362989.xsd failed to compile Compiling the schemas took 9 ms Parsing took 0 ms Freeing took 0 ms paphio:~/XML -> Daniel