对Neko和原住民的特殊Regex失败

Question

所以我在haxeflixel中做一些清理工作，我需要验证一个csv映射，所以我使用regex来检查它是否正常(不用提到结束逗号，我知道这不是有效的csv，但我想允许它)，我认为我有一个很好的正则表达式，它在闪存上似乎很好，但是c++崩溃了，neko给了我这个错误:运行pcre_exec时出错.这是我的准则，很抱歉，但我不知道问题出在哪里.^(([ ]*-?[0-9]+[ ]*,?)+\r?\n?)+$，如果有人知道会发生什么，我会很感激的，谢谢，妮可

ps。在我检查csv的正则表达式中可能有错误，但我可以找出它们，这是一种令人愉快的感觉，我只想知道具体原因是什么：)

编辑:啊，我刚刚注意到不是所有的字符串都会发生这种情况，一旦我把范围缩小到什么字符串，我就会发布一个.至于我正在检查的内容，它基本上只是为了确保映射文件中没有奇怪的xml头或任何非整数值，基本上应该验证如下：

1,1,1,1

1,1,1,1

1,1,1,1

或者这个：

1,1,1,1

1,1,1,1

1,1,1,1

但不是：

xml blahh>

1，m,1,1

1,1，b,1

1,1,1,1

xml>

(是的，我知道这不是有效的xml；)

编辑:它变得更奇怪了:所以我试图确定是什么字符串使它崩溃，虽然这仍然不能解释一个正常的地图崩溃，但它确实很奇怪，并且有相同的结果：

所发生的情况是:这将导致.match()测试失败，但不会崩溃：

a

0,0,0,0,0,0,0,0,0,0,0,0,0,0,0

1,1,1,1,1,1,1,1,1,1,1,1,1,1,1

0,0,0,0,0,0,0,0,0,0,0,0,0,0,0

1,1,1,1,1,1,1,1,1,1,1,1,1,1,1

虽然这会使程序崩溃：

0,0,0,0,0,0,0,0,0,0,0,0,0,0,0

1,1,1,1,1,1,1,1,1,1,1,1,1,1,1

0,0,0,0,0,0,0,0,0,0,0,0,0,0,0

1,*a*,1,1,1,1,1,1,1,1,1,1,1,1,1

Answer 1

老实说，你写的是我见过的最糟糕的一次。实际上，它看起来是专门写的，尽可能的慢。我写它并不是为了冒犯您，而是为了表达您需要学习编写regexp (提示:编写自己的regexp引擎是一个很好的练习)。

至于你的问题，我想它只是内存不足(它是非常内存密集型的)。我不知道为什么它只发生在pcre目标上( neko和cpp目标都使用pcre)，但我想这是关于在pcre中运行的每个regexp的内存限制，或者是在其他目标中纠正这种错误编写的regexp的一些启发式方法。

我会建议一些类似于

~/^(( *-?[0-9]+ *,)* *-?[0-9]+ *,?\r?\n)*(( *-?[0-9]+ *,)* *-?[0-9]+ *,?\r?\n?)$/

在那里，"~/“和”last "/“是haxe regexp标记。

我并没有对它进行广泛的测试，只是对您的示例进行了一次测试，但是它应该可以完成这项工作(可能只是稍微做了一些调整)。

另外，作为提示，我建议您在运行任何regexp之前先将文件拆分成行，这样会降低内存使用量(或者只需要在内存中保存部分文本)并简化regexp。

我还要注意的是，由于您无论如何都需要解析csv (对于任何格式正确的输入(我猜这是数据中普遍存在的输入)，在实际解析时执行所有测试可能要快得多。

编辑：“为什么它会消耗这么多内存”的问题的答案

嗯，这不是一个简短的话题，这就是为什么我建议你写你自己的regexp引擎。实现方面有一些不同，但一般认为regexp引擎是这样工作的：

1. 解析您的正则表达式并构建一个所有可能状态的图表(状态基本上是一个符号值，并有许多指向其他符号的链接)。
2. 设置读指针和状态指针对的列表，当前状态列表，包括regexp初始状态和指向匹配字符串的第一个字母的指针。
3. 设置指向符号字符串的第一个符号的读指针。
4. 将状态点设置为regexp的初始状态
5. 从当前状态列表中取出一对，并将其存储为当前状态和当前读取指针。
6. 读取当前读取指针下的符号
7. 将其与当前状态有链接的状态中的符号匹配，并生成匹配状态的列表。
8. 如果该列表中有最后的regexp状态，则为12。
9. 对于此列表中的每个项，向当前状态列表中添加一对下一读指针(即current+1)和项。
10. 如果当前状态列表为空，则返回false，因为字符串与regexp不匹配
11. 到6
12. 在这里，在匹配regexp的最后状态下，返回true，字符串匹配regexp。

当然，regexp引擎之间也有一些区别，其中一些可以消除afaik的一些问题。当然，他们也有伪对称，分组，他们需要存储的位置regexp和组匹配，他们有展望和回顾和分组引用，这使得它更复杂(相当卑微)和强制使用更复杂的数据结构，但主要的想法是相同的。所以，我们在这里，你的问题可以从算法中清楚地看到。对于要匹配的内容，您的具体程度越低，引擎匹配状态图中不同路径的子字符串的机会就越大，内存和处理器时间就会以指数方式消耗。尝试在字符串aaaaaab、ab、aa、aaaaaaaaaa、

此外，值得注意的是，一些regexp引擎以一种稍微不同的方式来处理这种情况，但是总有一些方法可以使regexp非常慢。

另一件要注意的是，我可能对确切的记忆问题弄错了。在这种情况下，它也可能是处理器，在此之前，它可能是内存/处理器启动的引擎限制，而不是系统缺乏内存。