Regex Performance Exercises

Test Apps

• input validation
• pattern search

Exercise 1

https://link.do/spa-greedy

Match HTML tags.

1. Add text inside/after the tag, see if step count changes; see debugger
2. Add another tag, see the result
3. Two solutions: limit repetition using lazy quantifier .*?, or limit scope [^>]
4. Try both, add text inside/after the tag, see step count changes

Hints:

• X* greedy quantifier
• X*? lazy quantifier
• [XYZ] character set, [^XYZ] negated character set

Exercise 2

https://link.do/spa-possessive

Match numbers with units ending with semicolon: 123cm; 32kg; 1m3;

1. Try to add digits to the number
2. Remove semicolon - see steps and backtracking in debugger
3. Replace greedy quantifier with the possessive one ++, see steps in debugger

Hints:

• \d digit
• \w word character (digit, letter, underscore)
• X++ possessive quantifier

Exercise 3

Optimize those two expressions:

1. Match Tea column in CSV text: https://link.do/spa-csv
2. (*) Find some CSS classes related to product: product-size, product-column, product-info and product ids that has digits 1,2,3. https://link.do/spa-css

Hints:

• ^ beginning of the line
• (?:...) non-capturing group
• X{6} repeat 6 times

Exercise 5 (*)

https://link.do/spa-operations

Arithmetic operations.

You have a regex matching simple arithmetic operations. Allowed: two numbers separated with plus or minus sign, ending with equals sign, e.g. 12+34= or 32121-23=

1. Enhance regex to allow 3 numbers and 2 signs (e.g. 12+322-1= ).
2. Enhance regex to allow any lenght of the operation (e.g. 12+322-1+223-2323+...=).
3. Remove equals sign from the test string, check steps in debugger.

References

• Mastering Regular Expressions, 3rd Edition, Jefferey Friedl, 2009
• Regex101 - online regex tester and debugger
• Test app - original thanks to Kamil Szubrycht
• OWASP on ReDoS
• Katafrakt: Regular expression how do they work?
• The true power of regular expressions
• FlashText algorithm vs regular epxressions for keyword matching )
• Jeff Atwood: Regex performance
• Mimicking atomic groups in JS regex
• RexEgg - Regex Tutorial, especially:
  • Explosive quantifiers
  • Mastering quantifiers
• regular-expressions.info:
  • Possesive quantifiers
  • Catastrophic backtracking
  • Regex engine internals
• Russ Cox regex series:
  • Regular Expression Matching Can Be Simple And Fast
  • Regular Expression Matching: the Virtual Machine Approach
  • Regular Expression Matching in the Wild
  • Regular Expression Matching with a Trigram Index
• Loggly:
  • Five invaluable techniques to improve regex performance
  • Regexes bad, better, best
• ReDoS cases
  • Sam Safron: Debugging 100% CPU usage in production Ruby on Rails systems
  • CloudFlare postmortem (2019)
  • StackOverflow postmortem (2016)