问题简述
说白了,Java根据指定分隔符分割字符串,忽略在引号（单引号和双引号）里面的分隔符; oom压测的时候,正则匹配"(?=(?:[^\"]*\"[^\"]*\")*[^\"]*$)(?=(?:[^']*'[^']*')*[^']*$)" 挂掉了,栈溢出了.
压测使用了200k的sql字符串,也就是200*1024Byte的字符串,单层时间复杂度就有2*10^5,不说时间的问题,正则匹配的迭代量太大,往往2*10^5中首次就可以匹配到上千个分隔符,上千1个再向后迭代,云云.
本地复现，debug一遍找到漏洞点
使用正则,200K的字符串扛不住；量小的话，运算时间也挺长的
/**
* 根据指定分隔符分割字符串---忽略在引号里面的分隔符
* @param str
* @param delimter
* @Deprecated Reason : 针对200K大小的sql任务,会存在OOM的问题
* @return
*/
public static String[] splitIgnoreQuota(String str, String delimter){
String splitPatternStr = delimter + "(?=(?:[^\"]*\"[^\"]*\")*[^\"]*$)(?=(?:[^']*'[^']*')*[^']*$)";
return str.split(splitPatternStr);
}
不使用正则, 完全通过使用单层for循环完全重写String的split方法, 废弃正则表达式, OOM的问题得到解决,秒出结果！
/**
* 使用非正则表达式的方法来实现 `根据指定分隔符分割字符串---忽略在引号里面的分隔符`
* @param str
* @param delimiter 分隔符
* @return
*/
public static String[] splitIgnoreQuotaNotUsingRegex(String str, String delimiter) {
// trim
str = str.trim();
// 遍历出成对的双引号的位置区间,排除转义的双引号
List<Pair<Integer, Integer>> doubleQuotas = getQuotaIndexPairs(str, '\"');
// 遍历出成对的单引号的位置区间,排除转义的单引号
List<Pair<Integer, Integer>> singleQuotas = getQuotaIndexPairs(str, '\'');
// 遍历出所有的delimiter的位置,排除掉在上述两个区间中的,排除掉转义的,按该delimiter位置拆分字符串
List<String> splitList = new ArrayList<>(128);
// index 表示目前搜索指针下标
// beforeIndex 表示目前已经成功匹配到的指针下标
int index = 0, beforeIndex = -1;
while ((index = str.indexOf(delimiter, Math.max(beforeIndex + 1, index))) != -1) {
// 排除转义
if (index == 0 || str.charAt(index - 1) != '\\') {
boolean flag = false;
// 排除双引号内的
for (Pair<Integer, Integer> p : doubleQuotas) {
if (p.getKey() <= index && p.getValue() >= index) {
flag = true;
break;
}
}
// 排除单引号内的
for (int i = 0; !flag && i < singleQuotas.size(); i++) {
Pair<Integer, Integer> p = singleQuotas.get(i);
if (p.getKey() <= index && p.getValue() >= index) {
flag = true;
break;
}
}
// flag = true, 表示该字符串在匹配的成对引号,跳过
if(flag){
index++;
continue;
}
// 这里的substring只取到分隔符的前一位,分隔符不加进来
splitList.add(str.substring(beforeIndex + 1, index));
beforeIndex = index;
} else {
index++;
}
}
// 收尾串
if (beforeIndex != str.length()) {
splitList.add(str.substring(beforeIndex + 1, str.length()));
}
return splitList.toArray(new String[0]);
}
/**
* 遍历出成对的双/单引号的位置区间,排除转义的双引号
* @param str
* @param quotaChar
* @return
*/
private static List<Pair<Integer, Integer>> getQuotaIndexPairs(String str, char quotaChar) {
List<Pair<Integer, Integer>> quotaPairs = new ArrayList<>(64);
List<Integer> posList = new ArrayList<>(128);
for (int idx = 0; idx < str.length(); idx++) {
if (str.charAt(idx) == quotaChar) {
if (idx == 0 || str.charAt(idx - 1) != '\\') {
posList.add(idx);
}
}
}
// 每两个装进Pair中,总数为奇数的话最后一个舍掉
for (int idx = 0; idx <= posList.size() - 2; idx += 2) {
quotaPairs.add(new Pair<>(posList.get(idx), posList.get(idx + 1)));
}
return quotaPairs;
}
样例输入 简单单测
@Test
public void test02() throws Exception {
String builder = "create table if not exists exam_ads_sales_all_d (\n" +
" stat_date string comment '统计日期'\n" +
" ,ord_quantity bigint comment '订单数量'\n" +
" ,ord_amount double comment '订单金额'\n" +
" ,pay_quantity bigint comment '付款数量'\n" +
" ,pay_amount double comment '付款金额'\n" +
" ,shop_cnt bigint comment '有交易的店铺数量'\n" +
")comment '测试;订单交易总表'\n" +
"PARTITIONED BY (ds string) lifecycle 7;select * from exam_ads_sales_all_d";
String[] splits = MyFormatter.splitIgnoreQuota(builder.toString(), ";");
System.out.println("================splitIgnoreQuota分割后行数： " + splits.length);
for (int i = 0; i < splits.length; i++) {
System.out.println(splits[i]+"\n");
}
String[] splits2 = DtStringUtil.splitIgnoreQuotaNotUsingRegex(builder.toString(), ";");
System.out.println("================splitIgnoreQuotaNotUsingRegex分割后行数： " + splits2.length);
for (int i = 0; i < splits2.length; i++) {
System.out.println(splits2[i]+"\n");
}
Assert.assertEquals(splits.length, splits2.length);
}
样例输出
================splitIgnoreQuotaNotUsingRegex分割后行数： 2
create table if not exists exam_ads_sales_all_d (
stat_date string comment '统计日期'
,ord_quantity bigint comment '订单数量'
,ord_amount double comment '订单金额'
,pay_quantity bigint comment '付款数量'
,pay_amount double comment '付款金额'
,shop_cnt bigint comment '有交易的店铺数量'
)comment '测试;订单交易总表'
PARTITIONED BY (ds string) lifecycle 7
select * from exam_ads_sales_all_d
- 为了后续的业务需求，算法中去掉了分隔符（有注释）；更多问题，欢迎指正！
- class Pair 引用自package org.apache.commons.math3.util; 自行添加maven依赖
码字不易啊~~
