Java正則表達式引發的思考

　　情況回放：

　　上周預發機器出了一個問題，CPU不定時會近100%滿負載運行。重啟以后就會恢復，之后又會到達100%，而且不會自恢復。

　　首先想到的是程序出現了死循環，于是用jstack把棧打印出來，發現業務線程都停在了regex相關的代碼上，有死循環的樣子。

　　查看棧，發現一切都是由ClientFilter這個類開始，其使用了matcher.matches()方法。這樣一來，就很可能是由于輸入了不規范的正則導致的了。于是查看輸入日志，發現這么一個輸入：

　　也就是說輸入的正則表達式為：******Deliver …，我們的代碼會將這種代碼規范成：.*.*.*.*.*.*.*Deliver。在java試了一下，試著匹配

　　“sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss”，果然會假死。

　　那么問題是：為什么輸入這種正則會導致假死?

　　這里的原因是：java使用的是greedy模式來匹配 .*。為了讓分析簡單，我們將輸入改成：.*.*.*.*D，正則需要匹配的字符串為：abcdefghijklmnopqrstuvwxyz0123456789，共36個字符。首先，我們將正則轉換成 ”有限自動機(Finite-State Machine)“

　　那么greedy模式(可參看：java.util.regex.Pattern.Curly.match0(…)，另兩個是possessive與lazy，分別對應 + 與 ?)的意思就是：最大可能的匹配當前狀態(優先匹配粗的路徑)，當不能匹配時再回溯配置下一個(虛線所示)，直到，回溯到cmin個匹配(對于 .* 這個cmin為0)。比如說

　　.*D，如果想匹配 testDdev，那么Java首先將 .* 轉成 .{0, MAX}(這里的MAX應該是2億多，具體可以看代碼)，那么 .{0, MAX} 得到的匹配是(java會自動在string后加上一個終止字符，這個字符只能java.util.regex.Pattern.LastNode匹配)：

　　testDev$

　　RED: 已匹配的部分

　　當到最后時，java會調用 next.match(matcher, i, seq)

　　testDev$

　　RED: 已匹配的部分

　　BLUE:回溯部分

　　顯然這里 D 不匹配，所以又需要回溯

　　testDev$

　　RED: 已匹配的部分

　　BLUE:回溯部分

　　顯然這里 e 也不匹配，所以還需要回溯，直到回溯到 D，才會正式進入到下一個狀態：

　　testDev$

　　RED: {0 MAX} 配置的部分

　　BLUE:回溯部分

　　GREEN: D 配置的部分

　　testDdev

　　RED: 已匹配的部分

　　如下面的代碼所示(java.util.regex.Pattern.Curly.match0(…))：

　　看了上面的示例我想大家應該有點頭緒了?，F在我們回到 .*.*.*.*D 這里，其在java內經過Pattern.compile之后是這個樣子：

　　type=0，表示使用的就是greedy方式。那么這里面有4個curly，我們用C1-4代表之。首先是C1滿匹配：

　　abcdefghijklmnopqrstuvwxyz0123456789$

　　我們省略前面幾步，看看回溯到5字符有什么特別

　　abcdefghijklmnopqrstuvwxyz0123456789$

　　這時候，C1釋放出了5個字符，那么這里就相當于 用 .*.*.*D 去配置6789$，那么老樣子C2會首先滿匹配

　　abcdefghijklmnopqrstuvwxyz0123456789$

　　然后next.match(matcher, i, seq)，不匹配，再next.match(matcher, i, seq)，‘D’也不匹配。只能回溯，我們看看回溯4個字符是什么樣子

　　abcdefghijklmnopqrstuvwxyz0123456789$

　　這時就相當于用 .*.*D 去匹配 789$ 了，又滿匹配，next又不匹配，再回溯，如下：

　　abcdefghijklmnopqrstuvwxyz0123456789$

　　就成了用 .*.*D 去match 89$，當 C2-4 都失敗后，C1才會再退一個字符，再進行遞歸：

　　abcdefghijklmnopqrstuvwxyz0123456789$

　　我們到底需要多少步才能將這些數字match完?

　　可想而知，這里的數目有多么大。那么問題來了，我們到底需要多少步才能將這些數字match完?OK，要解決這個問題，關鍵是要弄清這個遞歸。

　　設字符長度為n(加上終止符)，正則長度為 m(這里是有效節點，如 .* 是一個節點)。從上面的例子，我們能總結出遞歸的步驟為：

　　1、若m=1,返回 1;若m>1，步數 + n

　　2、回溯 i=1到n-1個字符，對于每個i 取 m=m-1, n=n-i 回1，并把所有的結果求合;

　　總的來說，用數學公式表示的話，就是這個樣子：

　　這里我寫了個簡單的實現：

　　(注：這里的 depth 并不是遞歸深度，而是遞歸次數，當時搞錯了)

　　好了，現在我們來驗證一下我們的結果，通過看jdk源碼，我們知道，.* 在匹配時調用的是java/util/regex/Pattern$CharProperty.match 方法，而 D 調用的是java/util/regex/Pattern$BmpCharProperty.match 。由于我們不能更改源代碼，我們使用ASM

　　字節注入工具，分別在這兩個方法上埋點，部分代碼如下：

　　package com.alibaba.taobao.tinyprofiler;

　　import java.lang.instrument.ClassFileTransformer;

　　import java.lang.instrument.IllegalClassFormatException;

　　import java.security.ProtectionDomain;

　　import org.objectweb.asm.ClassAdapter;

原文轉自：http://www.kjueaiud.com