Skip to content

Commit 706ac16

Browse files
ColinYoungTaroColinYoungTaro
authored
feat: refactor AST-based reducer (#879)
* feat: refactor AST-based reducer + define different kinds of transformers separately, making the reducer extenable. + add options to enable AST Based Reducer * modify the code based on the feedback of the review * add expected value to test cases for AST-based reducer. * support removing columns, clauses for common table expressions * feat: add time-out and max-steps options for AST-based-reducer * feat: add support for simplifying double constant * feat: simplify double constants when using AST-based reducer * refactor: modify the structure of the code to make it appropriate * adjust the format of comments and code * change reduce-AST to reduce-ast
1 parent 48aadfd commit 706ac16

15 files changed

+1054
-488
lines changed

‎docs/testCaseReduction.md‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -12,9 +12,9 @@ The AST-based reducer can shorten a statement by applying AST level transformati
1212
The transformations are implemented by [JSQLParser](https://github.com/JSQLParser/JSqlParser), a RDBMS agnostic SQL statement parser that can translate SQL statements into a traversable hierarchy of Java classes. JSQLParser provides support for the SQL standard as well as major SQL dialects. The AST-based reducer works for any SQL dialects that can be parsed by this tool.
1313

1414
## Enable reducers
15-
Test-case reduction is disabled by default. The statement reducer can be enabled by passing `--use-reducer` when starting SQLancer. If you wish to further shorten each statements, you need to additionally pass the `--reduce-AST` parameter so that the AST-based reduction is applied.
15+
Test-case reduction is disabled by default. The statement reducer can be enabled by passing `--use-reducer` when starting SQLancer. If you wish to further shorten each statements, you need to additionally pass the `--reduce-ast` parameter so that the AST-based reduction is applied.
1616

17-
Note: if `--reduce-AST` is set, `--use-reducer` option must be enabled first.
17+
Note: if `--reduce-ast` is set, `--use-reducer` option must be enabled first.
1818

1919
There are also options to define timeout seconds and max steps of reduction for both statement reducer and AST-based reducer.
2020

‎src/sqlancer/ASTBasedReducer.java‎

Lines changed: 70 additions & 457 deletions
Large diffs are not rendered by default.

‎src/sqlancer/Main.java‎

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -444,6 +444,10 @@ public void run() throws Exception {
444444
} catch (IOException e) {
445445
throw new AssertionError(e);
446446
}
447+
448+
if (options.reduceAST() && !options.useReducer()) {
449+
throw new AssertionError("To reduce AST, use-reducer option must be enabled first");
450+
}
447451
if (reproducer != null && options.useReducer()) {
448452
System.out.println("EXPERIMENTAL: Trying to reduce queries using a simple reducer.");
449453
// System.out.println("Reduced query will be output to stdout but not logs.");
@@ -459,6 +463,12 @@ public void run() throws Exception {
459463

460464
Reducer<G> reducer = new StatementReducer<>(provider);
461465
reducer.reduce(state, reproducer, newGlobalState);
466+
467+
if (options.reduceAST()) {
468+
Reducer<G> astBasedReducer = new ASTBasedReducer<>(provider);
469+
astBasedReducer.reduce(state, reproducer, newGlobalState);
470+
}
471+
462472
throw new AssertionError("Found a potential bug");
463473
}
464474
}

‎src/sqlancer/MainOptions.java‎

Lines changed: 23 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -126,10 +126,19 @@ public class MainOptions {
126126
@Parameter(names = "--use-reducer", description = "EXPERIMENTAL Attempt to reduce queries using a simple reducer")
127127
private boolean useReducer = false; // NOPMD
128128

129+
@Parameter(names = "--reduce-ast", description = "EXPERIMENTAL perform AST reduction after statement reduction")
130+
private boolean reduceAST = false; // NOPMD
131+
129132
@Parameter(names = "--statement-reducer-max-steps", description = "EXPERIMENTAL Maximum steps the statement reducer will do")
130133
private long maxStatementReduceSteps = NO_REDUCE_LIMIT; // NOPMD
131134

132-
@Parameter(names = "--statement-reducer-max-time", description = "EXPERIMENTAL Maximum time duration (secs) the statement reducer will do")
135+
@Parameter(names = "--statement-reducer-max-time", description = "EXPERIMENTAL Maximum time duration (secs) the AST-based reducer will do")
136+
private long maxASTReduceTime = NO_REDUCE_LIMIT; // NOPMD
137+
138+
@Parameter(names = "--ast-reducer-max-steps", description = "EXPERIMENTAL Maximum steps the AST-based reducer will do")
139+
private long maxASTReduceSteps = NO_REDUCE_LIMIT; // NOPMD
140+
141+
@Parameter(names = "--ast-reducer-max-time", description = "EXPERIMENTAL Maximum time duration (secs) the statement reducer will do")
133142
private long maxStatementReduceTime = NO_REDUCE_LIMIT; // NOPMD
134143

135144
public int getMaxExpressionDepth() {
@@ -293,11 +302,24 @@ public boolean useReducer() {
293302
return useReducer;
294303
}
295304

305+
public boolean reduceAST() {
306+
return reduceAST;
307+
}
308+
296309
public long getMaxStatementReduceSteps() {
297310
return maxStatementReduceSteps;
298311
}
299312

300313
public long getMaxStatementReduceTime() {
301314
return maxStatementReduceTime;
302315
}
316+
317+
public long getMaxASTReduceSteps() {
318+
return maxASTReduceSteps;
319+
}
320+
321+
public long getMaxASTReduceTime() {
322+
return maxASTReduceTime;
323+
}
324+
303325
}

‎src/sqlancer/transformations/JSQLParserBasedTransformation.java‎

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
package sqlancer.transformations;
2+
3+
import net.sf.jsqlparser.parser.CCJSqlParserUtil;
4+
import net.sf.jsqlparser.statement.Statement;
5+
6+
/**
7+
* Transformations based on JSQLParser should be derived from this class.
8+
*/
9+
10+
public class JSQLParserBasedTransformation extends Transformation {
11+
12+
protected Statement statement;
13+
14+
public JSQLParserBasedTransformation(String desc) {
15+
super(desc);
16+
}
17+
18+
@Override
19+
protected void onStatementChanged() {
20+
if (statementChangedHandler != null) {
21+
statementChangedHandler.accept(this.statement.toString());
22+
}
23+
}
24+
25+
@Override
26+
public boolean init(String sql) {
27+
this.current = sql;
28+
try {
29+
statement = CCJSqlParserUtil.parse(current);
30+
} catch (Exception e) {
31+
return false;
32+
}
33+
return true;
34+
}
35+
36+
}

‎src/sqlancer/transformations/RemoveClausesOfSelect.java‎

Lines changed: 102 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,102 @@
1+
package sqlancer.transformations;
2+
3+
import java.util.List;
4+
5+
import net.sf.jsqlparser.expression.Expression;
6+
import net.sf.jsqlparser.statement.select.Distinct;
7+
import net.sf.jsqlparser.statement.select.GroupByElement;
8+
import net.sf.jsqlparser.statement.select.Limit;
9+
import net.sf.jsqlparser.statement.select.Offset;
10+
import net.sf.jsqlparser.statement.select.PlainSelect;
11+
import net.sf.jsqlparser.statement.select.Select;
12+
import net.sf.jsqlparser.statement.select.SubSelect;
13+
import net.sf.jsqlparser.statement.select.WithItem;
14+
import net.sf.jsqlparser.util.deparser.ExpressionDeParser;
15+
import net.sf.jsqlparser.util.deparser.SelectDeParser;
16+
17+
/**
18+
* remove clauses of a select, such as join, where, group by, distinct, offset, limit.
19+
*
20+
* e.g. select * from t where a = b offset 1 limit 1 -> select * from t;
21+
*/
22+
23+
public class RemoveClausesOfSelect extends JSQLParserBasedTransformation {
24+
private final SelectDeParser remover = new SelectDeParser() {
25+
@Override
26+
public void visit(PlainSelect plainSelect) {
27+
handleSelect(plainSelect);
28+
super.visit(plainSelect);
29+
}
30+
};
31+
32+
public RemoveClausesOfSelect() {
33+
super("remove clauses of select");
34+
}
35+
36+
@Override
37+
public boolean init(String original) {
38+
39+
boolean baseSuc = super.init(original);
40+
if (!baseSuc) {
41+
return false;
42+
}
43+
44+
this.remover.setExpressionVisitor(new ExpressionDeParser(remover, new StringBuilder()));
45+
return true;
46+
}
47+
48+
@Override
49+
public void apply() {
50+
super.apply();
51+
if (statement instanceof Select) {
52+
Select select = (Select) statement;
53+
select.getSelectBody().accept(remover);
54+
55+
List<WithItem> withItemsList = select.getWithItemsList();
56+
if (withItemsList == null) {
57+
return;
58+
}
59+
tryRemoveElms(select, withItemsList, Select::setWithItemsList);
60+
61+
for (WithItem withItem : withItemsList) {
62+
SubSelect subSelect = withItem.getSubSelect();
63+
if (subSelect == null) {
64+
return;
65+
}
66+
67+
if (subSelect.getSelectBody() != null) {
68+
subSelect.getSelectBody().accept(remover);
69+
}
70+
}
71+
}
72+
}
73+
74+
private void handleSelect(PlainSelect plainSelect) {
75+
76+
Expression where = plainSelect.getWhere();
77+
if (where != null) {
78+
tryRemove(plainSelect, where, PlainSelect::setWhere);
79+
}
80+
81+
GroupByElement groupByElement = plainSelect.getGroupBy();
82+
if (groupByElement != null) {
83+
tryRemove(plainSelect, groupByElement, PlainSelect::setGroupByElement);
84+
}
85+
86+
Distinct distinct = plainSelect.getDistinct();
87+
if (distinct != null) {
88+
tryRemove(plainSelect, distinct, PlainSelect::setDistinct);
89+
}
90+
91+
Offset offset = plainSelect.getOffset();
92+
if (offset != null) {
93+
tryRemove(plainSelect, offset, PlainSelect::setOffset);
94+
}
95+
96+
Limit limit = plainSelect.getLimit();
97+
if (offset != null) {
98+
tryRemove(plainSelect, limit, PlainSelect::setLimit);
99+
}
100+
}
101+
102+
}

‎src/sqlancer/transformations/RemoveColumnsOfSelect.java‎

Lines changed: 64 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,64 @@
1+
package sqlancer.transformations;
2+
3+
import java.util.List;
4+
5+
import net.sf.jsqlparser.statement.select.PlainSelect;
6+
import net.sf.jsqlparser.statement.select.Select;
7+
import net.sf.jsqlparser.statement.select.SubSelect;
8+
import net.sf.jsqlparser.statement.select.WithItem;
9+
import net.sf.jsqlparser.util.deparser.ExpressionDeParser;
10+
import net.sf.jsqlparser.util.deparser.SelectDeParser;
11+
12+
/**
13+
* remove columns of a select: e.g. select a, b, c from t -> select a from t.
14+
*/
15+
public class RemoveColumnsOfSelect extends JSQLParserBasedTransformation {
16+
17+
private final SelectDeParser remover = new SelectDeParser() {
18+
@Override
19+
public void visit(PlainSelect plainSelect) {
20+
tryRemoveElms(plainSelect, plainSelect.getSelectItems(), PlainSelect::setSelectItems);
21+
super.visit(plainSelect);
22+
}
23+
};
24+
25+
public RemoveColumnsOfSelect() {
26+
super("remove columns of a select");
27+
}
28+
29+
@Override
30+
public boolean init(String original) {
31+
32+
boolean baseSucc = super.init(original);
33+
if (!baseSucc) {
34+
return false;
35+
}
36+
this.remover.setExpressionVisitor(new ExpressionDeParser(remover, new StringBuilder()));
37+
return true;
38+
}
39+
40+
@Override
41+
public void apply() {
42+
super.apply();
43+
if (statement instanceof Select) {
44+
Select select = (Select) statement;
45+
select.getSelectBody().accept(remover);
46+
47+
List<WithItem> withItemsList = select.getWithItemsList();
48+
if (withItemsList == null) {
49+
return;
50+
}
51+
for (WithItem withItem : withItemsList) {
52+
SubSelect subSelect = withItem.getSubSelect();
53+
if (subSelect == null) {
54+
return;
55+
}
56+
57+
if (subSelect.getSelectBody() != null) {
58+
subSelect.getSelectBody().accept(remover);
59+
}
60+
}
61+
62+
}
63+
}
64+
}

‎src/sqlancer/transformations/RemoveElementsOfExpressionList.java‎

Lines changed: 87 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,87 @@
1+
package sqlancer.transformations;
2+
3+
import java.util.List;
4+
5+
import net.sf.jsqlparser.expression.Expression;
6+
import net.sf.jsqlparser.expression.operators.relational.ExpressionList;
7+
import net.sf.jsqlparser.statement.select.GroupByElement;
8+
import net.sf.jsqlparser.statement.select.Join;
9+
import net.sf.jsqlparser.statement.select.PlainSelect;
10+
import net.sf.jsqlparser.statement.select.Select;
11+
import net.sf.jsqlparser.util.deparser.ExpressionDeParser;
12+
import net.sf.jsqlparser.util.deparser.InsertDeParser;
13+
import net.sf.jsqlparser.util.deparser.SelectDeParser;
14+
15+
/**
16+
* remove elements of an expression list.
17+
*
18+
* NOTE: this only works for select statements and targets at ExpressionList type in JSQLParser, such as groupBy list
19+
*/
20+
public class RemoveElementsOfExpressionList extends JSQLParserBasedTransformation {
21+
private final ExpressionDeParser expressionHandler = new ExpressionDeParser();
22+
private final SelectDeParser simplifier = new SelectDeParser() {
23+
@Override
24+
public void visit(PlainSelect plainSelect) {
25+
handleSelect(plainSelect);
26+
super.visit(plainSelect);
27+
}
28+
29+
@Override
30+
public void visit(ExpressionList expressionList) {
31+
List<Expression> expressions = expressionList.getExpressions();
32+
tryRemoveElms(expressionList, expressions, ExpressionList::setExpressions);
33+
super.visit(expressionList);
34+
}
35+
};
36+
private final InsertDeParser insertDeParser = new InsertDeParser() {
37+
@Override
38+
public void visit(ExpressionList expressionList) {
39+
List<Expression> expressions = expressionList.getExpressions();
40+
tryRemoveElms(expressionList, expressions, ExpressionList::setExpressions);
41+
super.visit(expressionList);
42+
}
43+
};
44+
45+
public RemoveElementsOfExpressionList() {
46+
super("remove elements of expression lists");
47+
}
48+
49+
@Override
50+
public boolean init(String sql) {
51+
boolean baseSuc = super.init(sql);
52+
if (!baseSuc) {
53+
return false;
54+
}
55+
this.simplifier.setExpressionVisitor(expressionHandler);
56+
this.expressionHandler.setSelectVisitor(simplifier);
57+
58+
this.insertDeParser.setExpressionVisitor(expressionHandler);
59+
this.insertDeParser.setSelectVisitor(simplifier);
60+
return true;
61+
}
62+
63+
@Override
64+
public void apply() {
65+
super.apply();
66+
if (statement instanceof Select) {
67+
Select select = (Select) statement;
68+
select.getSelectBody().accept(simplifier);
69+
}
70+
}
71+
72+
private void handleSelect(PlainSelect plainSelect) {
73+
74+
GroupByElement groupByElement = plainSelect.getGroupBy();
75+
76+
if (groupByElement != null && groupByElement.getGroupByExpressionList() != null) {
77+
ExpressionList expressionList = groupByElement.getGroupByExpressionList();
78+
List<Expression> list = expressionList.getExpressions();
79+
tryRemoveElms(expressionList, list, ExpressionList::setExpressions);
80+
}
81+
82+
List<Join> expressionList = plainSelect.getJoins();
83+
if (expressionList != null) {
84+
tryRemoveElms(plainSelect, expressionList, PlainSelect::setJoins);
85+
}
86+
}
87+
}

0 commit comments

Comments
 (0)