模板
教程
環(huán)境
性能
功能
管理
Java正則表達式引發(fā)的思考
情況回放：
上周預發(fā)機器出了一個(gè)問(wèn)題，CPU不定時(shí)會(huì )近100%滿(mǎn)負載運行。重啟以后就會(huì )恢復，之后又會(huì )到達100%，而且不會(huì )自恢復。
首先想到的是程序出現了死循環(huán)，于是用jstack把棧打印出來(lái)，發(fā)現業(yè)務(wù)線(xiàn)程都停在了regex相關(guān)的代碼上，有死循環(huán)的樣子。
查看棧，發(fā)現一切都是由ClientFilter這個(gè)類(lèi)開(kāi)始，其使用了matcher.matches()方法。這樣一來(lái)，就很可能是由于輸入了不規范的正則導致的了。于是查看輸入日志，發(fā)現這么一個(gè)輸入：
也就是說(shuō)輸入的正則表達式為：******Deliver …，我們的代碼會(huì )將這種代碼規范成：.*.*.*.*.*.*.*Deliver。在java試了一下，試著(zhù)匹配
“sssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssssss”，果然會(huì )假死。
那么問(wèn)題是：為什么輸入這種正則會(huì )導致假死?
這里的原因是：java使用的是greedy模式來(lái)匹配 .*。為了讓分析簡(jiǎn)單，我們將輸入改成：.*.*.*.*D，正則需要匹配的字符串為：abcdefghijklmnopqrstuvwxyz0123456789，共36個(gè)字符。首先，我們將正則轉換成 ”有限自動(dòng)機(Finite-State Machine)“
那么greedy模式(可參看：java.util.regex.Pattern.Curly.match0(…)，另兩個(gè)是possessive與lazy，分別對應 + 與 ?)的意思就是：最大可能的匹配當前狀態(tài)(優(yōu)先匹配粗的路徑)，當不能匹配時(shí)再回溯配置下一個(gè)(虛線(xiàn)所示)，直到，回溯到cmin個(gè)匹配(對于 .* 這個(gè)cmin為0)。比如說(shuō)
.*D，如果想匹配 testDdev，那么Java首先將 .* 轉成 .{0, MAX}(這里的MAX應該是2億多，具體可以看代碼)，那么 .{0, MAX} 得到的匹配是(java會(huì )自動(dòng)在string后加上一個(gè)終止字符，這個(gè)字符只能java.util.regex.Pattern.LastNode匹配)：
testDev$
RED: 已匹配的部分
當到最后時(shí)，java會(huì )調用 next.match(matcher, i, seq)
testDev$
RED: 已匹配的部分
BLUE:回溯部分
顯然這里 D 不匹配，所以又需要回溯
testDev$
RED: 已匹配的部分
BLUE:回溯部分
顯然這里 e 也不匹配，所以還需要回溯，直到回溯到 D，才會(huì )正式進(jìn)入到下一個(gè)狀態(tài)：
testDev$
RED: {0 MAX} 配置的部分
BLUE:回溯部分
GREEN: D 配置的部分
testDdev
RED: 已匹配的部分
如下面的代碼所示(java.util.regex.Pattern.Curly.match0(…))：
看了上面的示例我想大家應該有點(diǎn)頭緒了?，F在我們回到 .*.*.*.*D 這里，其在java內經(jīng)過(guò)Pattern.compile之后是這個(gè)樣子：
type=0，表示使用的就是greedy方式。那么這里面有4個(gè)curly，我們用C1-4代表之。首先是C1滿(mǎn)匹配：
abcdefghijklmnopqrstuvwxyz0123456789$
我們省略前面幾步，看看回溯到5字符有什么特別
abcdefghijklmnopqrstuvwxyz0123456789$
這時(shí)候，C1釋放出了5個(gè)字符，那么這里就相當于 用 .*.*.*D 去配置6789$，那么老樣子C2會(huì )首先滿(mǎn)匹配
abcdefghijklmnopqrstuvwxyz0123456789$
然后next.match(matcher, i, seq)，不匹配，再next.match(matcher, i, seq)，‘D’也不匹配。只能回溯，我們看看回溯4個(gè)字符是什么樣子
abcdefghijklmnopqrstuvwxyz0123456789$
這時(shí)就相當于用 .*.*D 去匹配 789$ 了，又滿(mǎn)匹配，next又不匹配，再回溯，如下：
abcdefghijklmnopqrstuvwxyz0123456789$
就成了用 .*.*D 去match 89$，當 C2-4 都失敗后，C1才會(huì )再退一個(gè)字符，再進(jìn)行遞歸：
abcdefghijklmnopqrstuvwxyz0123456789$
我們到底需要多少步才能將這些數字match完?
可想而知，這里的數目有多么大。那么問(wèn)題來(lái)了，我們到底需要多少步才能將這些數字match完?OK，要解決這個(gè)問(wèn)題，關(guān)鍵是要弄清這個(gè)遞歸。
設字符長(cháng)度為n(加上終止符)，正則長(cháng)度為 m(這里是有效節點(diǎn)，如 .* 是一個(gè)節點(diǎn))。從上面的例子，我們能總結出遞歸的步驟為：
1、若m=1,返回 1;若m>1，步數 + n
2、回溯 i=1到n-1個(gè)字符，對于每個(gè)i 取 m=m-1, n=n-i 回1，并把所有的結果求合;
總的來(lái)說(shuō)，用數學(xué)公式表示的話(huà)，就是這個(gè)樣子：
這里我寫(xiě)了個(gè)簡(jiǎn)單的實(shí)現：
(注：這里的 depth 并不是遞歸深度，而是遞歸次數，當時(shí)搞錯了)
好了，現在我們來(lái)驗證一下我們的結果，通過(guò)看jdk源碼，我們知道，.* 在匹配時(shí)調用的是java/util/regex/Pattern$CharProperty.match 方法，而 D 調用的是java/util/regex/Pattern$BmpCharProperty.match 。由于我們不能更改源代碼，我們使用ASM
字節注入工具，分別在這兩個(gè)方法上埋點(diǎn)，部分代碼如下：
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://kjueaiud.com
