Skip to content

Commit dd6abdc

Browse files
MathiasVPMathiasVP
authored
QL: Merge pull request github#87 from github/mathiasvp/superfluous-exists
New query: Unnecessary 'exists'
2 parents fb491c3 + 1762b4f commit dd6abdc

4 files changed

Lines changed: 395 additions & 17 deletions

File tree

‎ql/src/codeql/GlobalValueNumbering.qll‎

Lines changed: 244 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,244 @@
1+
private import ql
2+
private import codeql_ql.ast.internal.Predicate
3+
private import codeql_ql.ast.internal.Type
4+
private import codeql_ql.ast.internal.Builtins
5+
6+
private newtype TValueNumber =
7+
TVariableValueNumber(VarDecl var) { variableAccessValueNumber(_, var) } or
8+
TFieldValueNumber(VarDecl var) { fieldAccessValueNumber(_, var) } or
9+
TThisValueNumber(Predicate pred) { thisAccessValueNumber(_, pred) } or
10+
TPredicateValueNumber(PredicateOrBuiltin pred, ValueNumberArgumentList args) {
11+
predicateCallValueNumber(_, pred, args)
12+
} or
13+
TClassPredicateValueNumber(PredicateOrBuiltin pred, ValueNumber base, ValueNumberArgumentList args) {
14+
classPredicateCallValueNumber(_, pred, base, args)
15+
} or
16+
TLiteralValueNumber(string value, Type t) { literalValueNumber(_, value, t) } or
17+
TBinaryOpValueNumber(FunctionSymbol symbol, ValueNumber leftOperand, ValueNumber rightOperand) {
18+
binaryOperandValueNumber(_, symbol, leftOperand, rightOperand)
19+
} or
20+
TUnaryOpValueNumber(FunctionSymbol symbol, ValueNumber operand) {
21+
unaryOperandValueNumber(_, symbol, operand)
22+
} or
23+
TInlineCastValueNumber(ValueNumber operand, Type t) { inlineCastValueNumber(_, operand, t) } or
24+
TDontCareValueNumber() or
25+
TRangeValueNumber(ValueNumber lower, ValueNumber high) { rangeValueNumber(_, lower, high) } or
26+
TSetValueNumber(ValueNumberElementList elements) { setValueNumber(_, elements) } or
27+
TUniqueValueNumber(Expr e) { uniqueValueNumber(e) }
28+
29+
private newtype ValueNumberArgumentList =
30+
MkArgsNil() or
31+
MkArgsCons(ValueNumber head, ValueNumberArgumentList tail) {
32+
argumentValueNumbers(_, _, head, tail)
33+
}
34+
35+
private newtype ValueNumberElementList =
36+
MkElementsNil() or
37+
MkElementsCons(ValueNumber head, ValueNumberElementList tail) {
38+
setValueNumbers(_, _, head, tail)
39+
}
40+
41+
private ValueNumberArgumentList argumentValueNumbers(Call call, int start) {
42+
start = call.getNumberOfArguments() and
43+
result = MkArgsNil()
44+
or
45+
exists(ValueNumber head, ValueNumberArgumentList tail |
46+
argumentValueNumbers(call, start, head, tail) and
47+
result = MkArgsCons(head, tail)
48+
)
49+
}
50+
51+
private predicate argumentValueNumbers(
52+
Call call, int start, ValueNumber head, ValueNumberArgumentList tail
53+
) {
54+
head = valueNumber(call.getArgument(start)) and
55+
tail = argumentValueNumbers(call, start + 1)
56+
}
57+
58+
private ValueNumberElementList setValueNumbers(Set set, int start) {
59+
start = set.getNumberOfElements() and
60+
result = MkElementsNil()
61+
or
62+
exists(ValueNumber head, ValueNumberElementList tail |
63+
setValueNumbers(set, start, head, tail) and
64+
result = MkElementsCons(head, tail)
65+
)
66+
}
67+
68+
private predicate setValueNumbers(Set set, int start, ValueNumber head, ValueNumberElementList tail) {
69+
head = valueNumber(set.getElement(start)) and
70+
tail = setValueNumbers(set, start + 1)
71+
}
72+
73+
/**
74+
* A value number. A value number represents a collection of expressions that compute to the same value
75+
* at runtime.
76+
*/
77+
class ValueNumber extends TValueNumber {
78+
string toString() { result = "GVN" }
79+
80+
/** Gets an expression that has this value number. */
81+
final Expr getAnExpr() { this = valueNumber(result) }
82+
}
83+
84+
private predicate uniqueValueNumber(Expr e) { not numberable(e) }
85+
86+
private predicate numberable(Expr e) {
87+
e instanceof VarAccess or
88+
e instanceof FieldAccess or
89+
e instanceof ThisAccess or
90+
e instanceof Call or
91+
e instanceof Literal or
92+
e instanceof BinOpExpr or
93+
e instanceof UnaryExpr or
94+
e instanceof InlineCast or
95+
e instanceof ExprAnnotation or
96+
e instanceof DontCare or
97+
e instanceof Range or
98+
e instanceof Set or
99+
e instanceof AsExpr
100+
}
101+
102+
private predicate variableAccessValueNumber(VarAccess access, VarDef var) {
103+
access.getDeclaration() = var
104+
}
105+
106+
private predicate fieldAccessValueNumber(FieldAccess access, VarDef var) {
107+
access.getDeclaration() = var
108+
}
109+
110+
private predicate thisAccessValueNumber(ThisAccess access, Predicate pred) {
111+
access.getEnclosingPredicate() = pred
112+
}
113+
114+
private predicate predicateCallValueNumber(
115+
Call call, PredicateOrBuiltin pred, ValueNumberArgumentList args
116+
) {
117+
call.getTarget() = pred and
118+
not exists(call.(MemberCall).getBase()) and
119+
args = argumentValueNumbers(call, 0)
120+
}
121+
122+
private predicate classPredicateCallValueNumber(
123+
MemberCall call, PredicateOrBuiltin pred, ValueNumber base, ValueNumberArgumentList args
124+
) {
125+
call.getTarget() = pred and
126+
valueNumber(call.getBase()) = base and
127+
args = argumentValueNumbers(call, 0)
128+
}
129+
130+
private predicate literalValueNumber(Literal lit, string value, Type t) {
131+
lit.(String).getValue() = value and
132+
t instanceof StringClass
133+
or
134+
lit.(Integer).getValue().toString() = value and
135+
t instanceof IntClass
136+
or
137+
lit.(Float).getValue().toString() = value and
138+
t instanceof FloatClass
139+
or
140+
lit.(Boolean).isFalse() and
141+
value = "false" and
142+
t instanceof BooleanClass
143+
or
144+
lit.(Boolean).isTrue() and
145+
value = "true" and
146+
t instanceof BooleanClass
147+
}
148+
149+
private predicate binaryOperandValueNumber(
150+
BinOpExpr e, FunctionSymbol symbol, ValueNumber leftOperand, ValueNumber rightOperand
151+
) {
152+
e.getOperator() = symbol and
153+
valueNumber(e.getLeftOperand()) = leftOperand and
154+
valueNumber(e.getRightOperand()) = rightOperand
155+
}
156+
157+
private predicate unaryOperandValueNumber(UnaryExpr e, FunctionSymbol symbol, ValueNumber operand) {
158+
e.getOperator() = symbol and
159+
valueNumber(e.getOperand()) = operand
160+
}
161+
162+
private predicate inlineCastValueNumber(InlineCast cast, ValueNumber operand, Type t) {
163+
valueNumber(cast.getBase()) = operand and
164+
cast.getTypeExpr().getResolvedType() = t
165+
}
166+
167+
private predicate rangeValueNumber(Range range, ValueNumber lower, ValueNumber high) {
168+
valueNumber(range.getLowEndpoint()) = lower and
169+
valueNumber(range.getHighEndpoint()) = high
170+
}
171+
172+
private predicate setValueNumber(Set set, ValueNumberElementList elements) {
173+
elements = setValueNumbers(set, 0)
174+
}
175+
176+
private TValueNumber nonUniqueValueNumber(Expr e) {
177+
exists(VarDecl var |
178+
variableAccessValueNumber(e, var) and
179+
result = TVariableValueNumber(var)
180+
)
181+
or
182+
exists(VarDecl var |
183+
fieldAccessValueNumber(e, var) and
184+
result = TFieldValueNumber(var)
185+
)
186+
or
187+
exists(Predicate pred |
188+
thisAccessValueNumber(e, pred) and
189+
result = TThisValueNumber(pred)
190+
)
191+
or
192+
exists(PredicateOrBuiltin pred, ValueNumberArgumentList args |
193+
predicateCallValueNumber(e, pred, args) and
194+
result = TPredicateValueNumber(pred, args)
195+
)
196+
or
197+
exists(PredicateOrBuiltin pred, ValueNumber base, ValueNumberArgumentList args |
198+
classPredicateCallValueNumber(e, pred, base, args) and
199+
result = TClassPredicateValueNumber(pred, base, args)
200+
)
201+
or
202+
exists(string value, Type t |
203+
literalValueNumber(e, value, t) and
204+
result = TLiteralValueNumber(value, t)
205+
)
206+
or
207+
exists(FunctionSymbol symbol, ValueNumber leftOperand, ValueNumber rightOperand |
208+
binaryOperandValueNumber(e, symbol, leftOperand, rightOperand) and
209+
result = TBinaryOpValueNumber(symbol, leftOperand, rightOperand)
210+
)
211+
or
212+
exists(FunctionSymbol symbol, ValueNumber operand |
213+
unaryOperandValueNumber(e, symbol, operand) and
214+
result = TUnaryOpValueNumber(symbol, operand)
215+
)
216+
or
217+
exists(ValueNumber operand, Type t |
218+
inlineCastValueNumber(e, operand, t) and
219+
result = TInlineCastValueNumber(operand, t)
220+
)
221+
or
222+
result = valueNumber([e.(ExprAnnotation).getExpression(), e.(AsExpr).getInnerExpr()])
223+
or
224+
e instanceof DontCare and result = TDontCareValueNumber()
225+
or
226+
exists(ValueNumber lower, ValueNumber high |
227+
rangeValueNumber(e, lower, high) and
228+
result = TRangeValueNumber(lower, high)
229+
)
230+
or
231+
exists(ValueNumberElementList elements |
232+
setValueNumber(e, elements) and
233+
result = TSetValueNumber(elements)
234+
)
235+
}
236+
237+
/** Gets the value number of an expression `e`. */
238+
cached
239+
TValueNumber valueNumber(Expr e) {
240+
result = nonUniqueValueNumber(e)
241+
or
242+
uniqueValueNumber(e) and
243+
result = TUniqueValueNumber(e)
244+
}

‎ql/src/codeql_ql/ast/Ast.qll‎

Lines changed: 37 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -816,6 +816,9 @@ class Call extends TCall, Expr, Formula {
816816
none() // overriden in sublcasses.
817817
}
818818

819+
/** Gets an argument of this call, if any. */
820+
final Expr getAnArgument() { result = getArgument(_) }
821+
819822
PredicateOrBuiltin getTarget() { resolveCall(this, result) }
820823

821824
override Type getType() { result = this.getTarget().getReturnType() }
@@ -1791,7 +1794,19 @@ class FunctionSymbol extends string {
17911794
/**
17921795
* A binary operation expression, such as `x + 3` or `y / 2`.
17931796
*/
1794-
class BinOpExpr extends TBinOpExpr, Expr { }
1797+
class BinOpExpr extends TBinOpExpr, Expr {
1798+
/** Gets the left operand of the binary expression. */
1799+
Expr getLeftOperand() { none() } // overriden in subclasses
1800+
1801+
/* Gets the right operand of the binary expression. */
1802+
Expr getRightOperand() { none() } // overriden in subclasses
1803+
1804+
/** Gets the operator of the binary expression. */
1805+
FunctionSymbol getOperator() { none() } // overriden in subclasses
1806+
1807+
/* Gets an operand of the binary expression. */
1808+
final Expr getAnOperand() { result = getLeftOperand() or result = getRightOperand() }
1809+
}
17951810

17961811
/**
17971812
* An addition or subtraction expression.
@@ -1802,17 +1817,11 @@ class AddSubExpr extends TAddSubExpr, BinOpExpr {
18021817

18031818
AddSubExpr() { this = TAddSubExpr(expr) and operator = expr.getChild().getValue() }
18041819

1805-
/** Gets the left operand of the binary expression. */
1806-
Expr getLeftOperand() { toGenerated(result) = expr.getLeft() }
1820+
override Expr getLeftOperand() { toGenerated(result) = expr.getLeft() }
18071821

1808-
/* Gets the right operand of the binary expression. */
1809-
Expr getRightOperand() { toGenerated(result) = expr.getRight() }
1822+
override Expr getRightOperand() { toGenerated(result) = expr.getRight() }
18101823

1811-
/* Gets an operand of the binary expression. */
1812-
Expr getAnOperand() { result = getLeftOperand() or result = getRightOperand() }
1813-
1814-
/** Gets the operator of the binary expression. */
1815-
FunctionSymbol getOperator() { result = operator }
1824+
override FunctionSymbol getOperator() { result = operator }
18161825

18171826
override PrimitiveType getType() {
18181827
// Both operands are the same type
@@ -1872,16 +1881,12 @@ class MulDivModExpr extends TMulDivModExpr, BinOpExpr {
18721881
MulDivModExpr() { this = TMulDivModExpr(expr) and operator = expr.getChild().getValue() }
18731882

18741883
/** Gets the left operand of the binary expression. */
1875-
Expr getLeftOperand() { toGenerated(result) = expr.getLeft() }
1884+
override Expr getLeftOperand() { toGenerated(result) = expr.getLeft() }
18761885

18771886
/** Gets the right operand of the binary expression. */
1878-
Expr getRightOperand() { toGenerated(result) = expr.getRight() }
1879-
1880-
/** Gets an operand of the binary expression. */
1881-
Expr getAnOperand() { result = getLeftOperand() or result = getRightOperand() }
1887+
override Expr getRightOperand() { toGenerated(result) = expr.getRight() }
18821888

1883-
/** Gets the operator of the binary expression. */
1884-
FunctionSymbol getOperator() { result = operator }
1889+
override FunctionSymbol getOperator() { result = operator }
18851890

18861891
override PrimitiveType getType() {
18871892
// Both operands are of the same type
@@ -1954,6 +1959,11 @@ class Range extends TRange, Expr {
19541959
*/
19551960
Expr getHighEndpoint() { toGenerated(result) = range.getUpper() }
19561961

1962+
/**
1963+
* Gets the lower and upper bounds of the range.
1964+
*/
1965+
Expr getAnEndpoint() { result = [getLowEndpoint(), getHighEndpoint()] }
1966+
19571967
override PrimitiveType getType() { result.getName() = "int" }
19581968

19591969
override string getAPrimaryQlClass() { result = "Range" }
@@ -1980,6 +1990,16 @@ class Set extends TSet, Expr {
19801990
*/
19811991
Expr getElement(int i) { toGenerated(result) = set.getChild(i) }
19821992

1993+
/**
1994+
* Gets an element in this set literal expression, if any.
1995+
*/
1996+
Expr getAnElement() { result = getElement(_) }
1997+
1998+
/**
1999+
* Gets the number of elements in this set literal expression.
2000+
*/
2001+
int getNumberOfElements() { result = count(getAnElement()) }
2002+
19832003
override Type getType() { result = this.getElement(0).getType() }
19842004

19852005
override string getAPrimaryQlClass() { result = "Set" }

‎ql/src/codeql_ql/ast/internal/Builtins.qll‎

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -65,3 +65,18 @@ string getArgType(string args, int i) { result = args.splitAt(",", i).trim() }
6565
class StringClass extends PrimitiveType {
6666
StringClass() { this.getName() = "string" }
6767
}
68+
69+
/** The primitive 'int' class. */
70+
class IntClass extends PrimitiveType {
71+
IntClass() { this.getName() = "int" }
72+
}
73+
74+
/** The primitive 'float' class. */
75+
class FloatClass extends PrimitiveType {
76+
FloatClass() { this.getName() = "float" }
77+
}
78+
79+
/** The primitive 'boolean' class. */
80+
class BooleanClass extends PrimitiveType {
81+
BooleanClass() { this.getName() = "boolean" }
82+
}

0 commit comments

Comments
 (0)