"; /-6ren">
gpt4 book ai didi

java - DiffMatchPatch 正则表达式容易出现灾难性回溯?

转载 作者:行者123 更新时间:2023-11-30 07:51:38 26 4
gpt4 key购买 nike

google DiffMatchPatch 的正则表达式是否为 (A*|B*|C*|D*)* 形式?

private static final String TAG_REGEX = "<(\"[^\"]*\"|'[^']*'|[^'\">])*>"; //in case the texts being compared contain XML or HTML tags

如果我理解正确,某些输入字符串应该会导致堆栈溢出,如此处所述 http://www.regular-expressions.info/catastrophic.html , Regex gone wild: java.util.regex.Pattern matcher goes into high CPU loop

有人可以提供会破坏这个正则表达式的示例吗?

最佳答案

正则表达式不会遇到灾难性的回溯,因为正则表达式是明确的。

但是,如果您使用 Oracle JVM 或 OpenJDK,那么当单引号或双引号字符串之外存在大量字符时,上述代码会出现 StackOverflowError,尤其是带有不带引号的属性的 HTML。

例如:

String input = "<a href=https://www.google.com/search?tbs=sbi:AMhZZisZE7GxcvzYV20Dr9-lbMIKPcIj1un1cusubzWm8vKUA4pt3wWZ_1T8F5DynP15tfGTUTz5nqFoQWqWtde44qYBjMwpISXp2yCcuxHNiOBQX96Ol_1Ipf1w-BNNwEteGZUxl6HX4niNUAvVJzMqyfs3p0CVyF9Vf5_1NnYssdzVEsCBpJDYE-g759Icjtlm8vZXWvq3RUGTLS7FOrkyTWQ1Ym9COR1jtJzAbLMhJT_1bMHM5i6SfUpspG7nW_10-XiHnNlW_10D7ApaO10mLaAFdRPm1qVjLBP0-R9Fz0wgeyEad28JXxKY8xBuAoOM5oW5SwLibZYFdMv_1OwgsHSjXZI6xcW7O7vgpcDUA-r5PjCFOm4mxBie2I0QylHAE4fqWELskrpg6MRCBo4lcS9mAceC4PPGWnBQi95s4Bg2qidUHOZ6FzXoGTFPSBJ6C65vVpijAS48qwUdT0LnyGyR4HgVoyXztnSVd18yHsNOMyhYp7SO3-jYYSZFOEoE8cVtEbBUlPEBLr6VsKEBf8pqCGHUS4T7dy5tlOIMXdT93r4MjilMOLhQq286l8oZhp9rNC1AxKuHvxQE4sh5kTzEs41LhF0sMm2PYPRB-vxTTD3RnPt47AZAkTsVJQAtgv-3_1optn69_1IDz0GHn0dRGR3Sd5Ekcx4SHb5XHGFBDJ-ejoCZ3IWzSo_1KMadJrWNOGojHkeX0lVkVeCa1N_111oUWxCqJ8ejUZfwMi1t7AgU7gdMmPC58oUlnNhwYqWxkOFN6YujVlFA7jDerSSIRL-TKdIrlc1egyiMYVZ-vSvpmKF2N7Qm4hcUEdwr9VD87Q27R2EfhsczHflOBZ7ensbnVYTzy6TgVJu8Wd5BortukJ860HfyexenbUNM9PtdwEDzfiNblJmUcahpgOPvfQlZjPZniLoGRO2KhMCrglu3yKD8ndRZu_1_1u_1ID_1xtsoJwCziNPTvaE5n2-bypPlY_1hFcMHB8d0dlOqF2D-YJoZu2qmNZzKYm0XkAgdX9rUEo6JtJdytvS5b46JQGvfGcvKFfWxeqbxc3rvE3uUcW1yK-4l5iz8dzQ42PoWxENXV5J0lAP2apcTgS068tKxaw8OSw5W1AWMLNY0WSeI7YeLD59xUlMXAyBSR25FtQBmV86taHP_1IxeNTwNF8pz20LLxmDT6CsG9LoXEEHGUPzr5rM2DMcgUw3_16_1Rp0zw_1h_1Ju-lgJ5bMP2KDxrSEKZ7neLdqPAfejMiAUV3_1miOk_1cOs8Gu0QKizmWt9yX7_14O9yrE1YQ6193rVnUqv7HIZ--WNzOxiVKOYaE_1Hy4gseyS0vh32oGlQBJslmk_1jXCi346Ffa-F2_1e6zfyjo-rMYw3d_14SYFZqXZL8dtIXJNQliBtsfn7dCInzkegkrhYRFcyLhppMWmZDurwMNhKQYbEZLC9lh8OabruxSTH1gkaDi0LlW0SpzJsXSwXSwgaRzFVTVNk2op4vPtVFs7NwD_187w2fDNJcIkkaIQ3cXQeQtzmhdvhLqhrudx9D7nAwdNwFM0gD2PVV2kUmc6YTJ6_1UQo2jS4ENycmXgg&btnG=Search%20by%20image&hl=en>";

问题原因分析于this answer of mine .

  1. 解决此问题的一种方法是使外部重复具有所有格:

    "<(\"[^\"]*\"|'[^']*'|[^'\">])*+>"
    ^^

    所有格量词是用循环实现的,所以不会出现StackOverflowError

  2. 解决此问题的另一种方法是在外部重复的单次迭代中尽可能多地匹配不带引号的字符 [^'\">]:

    "<(\"[^\"]*\"|'[^']*'|[^'\">]++)*>"
    ^^

    在这种情况下,所有格量词是强制的,否则正则表达式将出现灾难性的回溯。

关于java - DiffMatchPatch 正则表达式容易出现灾难性回溯?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33274953/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com