Повторное совпадение занимает очень много времени.

Question

Я написал регулярное выражение, которое анализирует путь к файлу в разные группы (DRIVE, DIR, FILE, EXTENSION).

^((?<DRIVE>[a-zA-Z]):\\)*((?<DIR>[a-zA-Z0-9_]+(([a-zA-Z0-9_\s_\-\.]*[a-zA-Z0-9_]+)|([a-zA-Z0-9_]+)))\\)*(?<FILE>([a-zA-Z0-9_]+(([a-zA-Z0-9_\s_\-\.]*[a-zA-Z0-9_]+)|([a-zA-Z0-9_]+))\.(?<EXTENSION>[a-zA-Z0-9]{1,6})$)) 

Я сделал тест на C#. Когда путь, который я хочу проверить, правильный. Результат очень быстрый, и это то, чего я хотел ожидать.

string path = @"C:\Documents and Settings\jhr\My Documents\Visual Studio 2010\Projects\FileEncryptor\Dds.FileEncryptor\Dds.FileEncryptor.csproj"; 

=> OK

Но когда я пытаюсь проверить с пути, я знаю, что не будет соответствовать, как это:

string path = @"C:\Documents and Settings\jhr\My Documents\Visual Studio 2010\Projects\FileEncryptor\Dds.FileEncryptor\Dds.FileEncryptor?!??????"; 

=> BUG

Тест замораживается, когда я называю эту часть кода

Match match = s_fileRegex.Match(path); 

Когда я просматриваю свой Process Explorer, я вижу, что процесс QTAgent32.exe висит на 100% моего процессора. Что это значит ?

Answer 1

Проблема, с которой вы столкнулись, называется catastrophic backtracking и объясняется большим количеством способов, с помощью которых регулярное выражение может совпадать с началом строки, что дает медленную производительность из-за механизма регулярного выражения backtracking в .NET.

Я думаю, вы слишком часто используете * в своем регулярном выражении. * не означает «конкатенация» - это означает «0 или более раз». Например, не должно быть * здесь:

((?<DRIVE>[a-zA-Z]):\\)* 

Там должно быть не более одной спецификации привода. Здесь вы должны использовать ?, иначе квантификатор, если вы хотите, чтобы спецификация накопителя была обязательной. Точно так же существуют и другие места в вашем регулярном выражении, где квантификатор неверен.

Answer 2

Почему бы не просто использовать функции System.IO.Path?

• Привод: http://msdn.microsoft.com/en-us/library/system.io.path.getpathroot.aspx

• Каталог: http://msdn.microsoft.com/en-us/library/system.io.path.getdirectoryname.aspx минус, что получил за Драйв

• Имя файла: http://msdn.microsoft.com/en-us/library/system.io.path.getfilenamewithoutextension.aspx

• Расширение: http://msdn.microsoft.com/en-us/library/system.io.path.getextension.aspx

Answer 3

Я бы просто использовал классы FileInfo и Path для получения информации.

Если вы решите использовать регулярное выражение, , то обратите внимание, что регулярное выражение не соответствует всем законным именам файлов: в вашем регулярном выражении отсутствует целая куча легальных идентификаторов имени файла.

Answer 4

Mark Byers верен тем, что причиной проблемы является catastrophic backtracking, однако это последняя проблема, которая вызывает проблему, а не бит, соответствующий букве диска.

Например, в

(?<FILE> 
    ([a-zA-Z0-9_]+ 
    (
     ([a-zA-Z0-9_\s_\-\.]*[a-zA-Z0-9_]+) 
    | 
     ([a-zA-Z0-9_]+) 
    )\. 
    (?<EXTENSION>[a-zA-Z0-9]{1,6}) 
    $) 
) 

вы можете увидеть, что

([a-zA-Z0-9_\s_\-\.]*[a-zA-Z0-9_]+) 
| 
([a-zA-Z0-9_]+) 

может соответствовать той же строки в ряде различных способов, которые будут экспоненциально возрастать с длиной файла.

Когда случается, что часть расширения регулярного выражения не может совпадать, двигатель regex обращается назад и пытается выполнить другую перестановку для части имени файла, надеясь, что это позволит части расширения соответствовать, что, конечно, никогда не будет, но двигатель регулярных выражений не может понять это. RegexBuddy, когда вас попросят проверить регулярное выражение на указанном вами пути, прервите попытку матча после 1.000.000 итераций. Двигатель регулярных выражений C# будет работать до тех пор, пока он не исчерпает все перестановки, закрепив ваш процессор на 100% за это время.

Чтобы исправить это, как правило, необходимо избегать повторений повторяющихся элементов, чтобы избежать чередования, которые соответствуют тем же вещам, и, возможно, заключить части совпадения в atomic groups, которые не будут возвращены, если более поздняя часть регулярного выражения выходит из строя.

В вашем случае, однако, лучше использовать нужные инструменты для задания, и это функции управления трассировкой .NET.