git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: [PATCH] avoid exponential regex match for java and objc function names

From
Paolo Bonzini <paolo.bonzini@gmail.com>
Date
Jun 17, 2009, 16:04 UTC
Message-ID
<4A391429.4010706@gmail.com>
In-Reply-To
<9b18b3110906170900g778b3c8aie627fb45a4967eb2@mail.gmail.com>
Show 7 quoted lines
> Ah ok. Im not familiar with the finer points of the POSIX engine, but
> PCRE and Perl's engine, and most similar engines are not true regular
> expression engines and thus benefit *greatly* from atomic matching if
> it is available.
> 
> Like the difference between heat-death performance (or stack
> overflow), and running instantly.

You can almost always fix the regex to avoid this, by ensuring that whenever you have (...)+ (or *) a suffix of the subexpression cannot be a prefix of the subexpression too. This is what my patch did -- changing a bad regex to a nicely behaving one.

Paolo
Previous: demerphqNext: Junio C Hamano
Message 33 of 37 in “git diff looping?”
  1. John BitoJun 16, 2009
  2. Jeff EplerJun 16, 2009
  3. John BitoJun 16, 2009
  4. Jeff KingJun 16, 2009
  5. Jeff KingJun 16, 2009
  6. 1/2 Makefile: refactor regex compat supportJeff King, Jun 16, 2009
  7. Johannes SixtJun 16, 2009
  8. Jeff KingJun 16, 2009
  9. 1/2 Makefile: refactor regex compat supportJeff King, Jun 16, 2009
  10. 2/2 Makefile: use compat regex on SolarisJeff King, Jun 16, 2009
  11. Brandon CaseyJun 16, 2009
  12. Mike RalphsonJun 17, 2009
  13. Mike RalphsonJun 17, 2009
  14. 2/2 Makefile: use compat regex on SolarisJeff King, Jun 16, 2009
  15. John BitoJun 16, 2009
  16. Junio C HamanoJun 16, 2009
  17. Jeff KingJun 16, 2009
  18. Brandon CaseyJun 16, 2009
  19. John BitoJun 16, 2009
  20. Jeff KingJun 16, 2009
  21. Brandon CaseyJun 16, 2009
  22. Paolo BonziniJun 17, 2009
  23. Jeff KingJun 17, 2009
  24. Paolo BonziniJun 17, 2009
  25. Andreas EricssonJun 17, 2009
  26. Paolo BonziniJun 17, 2009
  27. Andreas EricssonJun 17, 2009
  28. Paolo BonziniJun 17, 2009
  29. avoid exponential regex match for java and objc function namesPaolo Bonzini, Jun 17, 2009
  30. demerphqJun 17, 2009
  31. Jeff KingJun 17, 2009
  32. demerphqJun 17, 2009
  33. Paolo BonziniJun 17, 2009
  34. Junio C HamanoJun 17, 2009
  35. Paolo BonziniJun 18, 2009
  36. John BitoJun 16, 2009
  37. Jeff KingJun 16, 2009

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.