XNet regex pattern in .Net makes application freeze

Question

Processing time doubles as "Y" goes to the right. Can someone tell me why? How to solve this problem?

I have a lot of large identifier stored in the database that cannot be changed, so I can not limit the size too much.

using System; using System.IO; using System.Text; using System.Xml; using System.Xml.Schema; namespace TestRegex { class Program { static void Main(string[] args) { DateTime start = DateTime.Now; /****************************************** * ID to validate ******************************************/ //string id = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxx"; // Ok: Fast string id = "xxxxxxxxxxxxxxxxxxxxxYxxxxxxx"; // Invalid: Slow //string id = "xxxxxxxxxxxxxxxxxxxxxxYxxxxxx"; // Invalid: Slower //string id = "xxxxxxxxxxxxxxxxxxxxxxxYxxxxx"; // Invalid: Very slow //string id = "xxxxxxxxxxxxxxxxxxxxxxxxYxxxx"; // Invalid: Very very slow /****************************************** * XML to validate ******************************************/ XmlDocument doc = new XmlDocument(); doc.LoadXml("<root id='" + id + "'></root>"); /****************************************** * XSD validator ******************************************/ string xsl = @" <xs:schema xmlns:xs='http://www.w3.org/2001/XMLSchema' elementFormDefault='unqualified' attributeFormDefault='unqualified'> <xs:simpleType name='id'> <xs:restriction base='xs:string'> <xs:pattern value='^([a-z_]+[0-9]*)+' /> </xs:restriction> </xs:simpleType> <xs:element name='root'> <xs:complexType> <xs:attribute name='id' use='required' type='id' /> </xs:complexType> </xs:element> </xs:schema> "; /****************************************** * Adds XSD to XML and validates it ******************************************/ XmlTextReader reader = new XmlTextReader( new MemoryStream(ASCIIEncoding.Default.GetBytes(xsl))); XmlSchema schema = XmlSchema.Read(reader, new ValidationEventHandler(Validate)); doc.Schemas.Add(schema); doc.Validate(new ValidationEventHandler(Validate)); /****************************************** * Performance results ******************************************/ Console.WriteLine(id.Length + " = " + (DateTime.Now - start).TotalSeconds); Console.Read(); } private static void Validate(object o, ValidationEventArgs args) { if (args.Exception != null) { Console.WriteLine(args.Exception); } } } } 

Answer 1

Solved!

The regular expression ^([a-z_][a-z_0-9]*) has the same behavior, and it is very fast.

Answer 2

This is similar to the Catastrophic Rollback case.
Your regex seems too complicated. If I read it correctly, it takes lowercase letters and numbers when the first letter is not a number. You can rewrite it as:

 ^[a-z_]\w*