Skip to content

Commit 9b5b496

Browse files
smowtonsmowton
committed
Avoid quadratic switch case intermediate
1 parent d1e16ad commit 9b5b496

3 files changed

Lines changed: 64 additions & 37 deletions

File tree

‎java/ql/lib/semmle/code/java/ControlFlowGraph.qll‎

Lines changed: 1 addition & 28 deletions
Original file line numberDiff line numberDiff line change
@@ -82,6 +82,7 @@
8282
import java
8383
private import Completion
8484
private import controlflow.internal.Preconditions
85+
private import controlflow.internal.SwitchCases
8586

8687
/** A node in the expression-level control-flow graph. */
8788
class ControlFlowNode extends Top, @exprparent {
@@ -436,34 +437,6 @@ private module ControlFlowGraphImpl {
436437
)
437438
}
438439

439-
/**
440-
* Gets the `i`th `SwitchCase` defined on `switch`, if one exists.
441-
*/
442-
private SwitchCase getCase(StmtParent switch, int i) {
443-
result = switch.(SwitchExpr).getCase(i) or result = switch.(SwitchStmt).getCase(i)
444-
}
445-
446-
/**
447-
* Gets the `i`th `PatternCase` defined on `switch`, if one exists.
448-
*/
449-
private PatternCase getPatternCase(StmtParent switch, int i) {
450-
result =
451-
rank[i + 1](PatternCase pc, int caseIdx | pc = getCase(switch, caseIdx) | pc order by caseIdx)
452-
}
453-
454-
/**
455-
* Gets the PatternCase after pc, if one exists.
456-
*/
457-
private PatternCase getNextPatternCase(PatternCase pc) {
458-
exists(int idx, StmtParent switch |
459-
pc = getPatternCase(switch, idx) and result = getPatternCase(switch, idx + 1)
460-
)
461-
}
462-
463-
private int lastCaseIndex(StmtParent switch) {
464-
result = max(int i | any(SwitchCase c).isNthCaseOf(switch, i))
465-
}
466-
467440
// Join order engineering -- first determine the switch block and the case indices required, then retrieve them.
468441
bindingset[switch, i]
469442
pragma[inline_late]

‎java/ql/lib/semmle/code/java/controlflow/Guards.qll‎

Lines changed: 32 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -7,6 +7,7 @@ import java
77
private import semmle.code.java.controlflow.Dominance
88
private import semmle.code.java.controlflow.internal.GuardsLogic
99
private import semmle.code.java.controlflow.internal.Preconditions
10+
private import semmle.code.java.controlflow.internal.SwitchCases
1011

1112
/**
1213
* A basic block that terminates in a condition, splitting the subsequent control flow.
@@ -72,6 +73,35 @@ class ConditionBlock extends BasicBlock {
7273
}
7374
}
7475

76+
// Join order engineering -- first determine the switch block and the case indices required, then retrieve them.
77+
bindingset[switch, i]
78+
pragma[inline_late]
79+
private predicate isNthCaseOf(StmtParent switch, SwitchCase c, int i) { c.isNthCaseOf(switch, i) }
80+
81+
/**
82+
* Gets a switch case >= pred, up to but not including `pred`'s successor pattern case,
83+
* where `pred` is declared on `switch`.
84+
*/
85+
private SwitchCase getACaseUpToNextPattern(PatternCase pred, StmtParent switch) {
86+
// Note we do include `case null, default` (as well as plain old `default`) here.
87+
not result.(ConstCase).getValue(_) instanceof NullLiteral and
88+
exists(int maxCaseIndex |
89+
switch = pred.getParent() and
90+
if exists(getNextPatternCase(pred))
91+
then maxCaseIndex = getNextPatternCase(pred).getCaseIndex() - 1
92+
else maxCaseIndex = lastCaseIndex(switch)
93+
|
94+
isNthCaseOf(switch, result, [pred.getCaseIndex() .. maxCaseIndex])
95+
)
96+
}
97+
98+
/**
99+
* Gets the closest pattern case preceding `case`, including `case` itself, if any.
100+
*/
101+
private PatternCase getClosestPrecedingPatternCase(SwitchCase case) {
102+
case = getACaseUpToNextPattern(result, _)
103+
}
104+
75105
/**
76106
* A condition that can be evaluated to either true or false. This can either
77107
* be an `Expr` of boolean type that isn't a boolean literal, or a case of a
@@ -113,17 +143,10 @@ class Guard extends ExprParent {
113143
result = this.(Expr).getBasicBlock()
114144
or
115145
// Return the closest pattern case statement before this one, including this one.
116-
result =
117-
max(int i, PatternCase c |
118-
c = this.(SwitchCase).getSiblingCase(i) and i <= this.(SwitchCase).getCaseIndex()
119-
|
120-
c order by i
121-
).getBasicBlock()
146+
result = getClosestPrecedingPatternCase(this).getBasicBlock()
122147
or
123148
// Not a pattern case and no preceding pattern case -- return the top of the switch block.
124-
not exists(PatternCase c, int i |
125-
c = this.(SwitchCase).getSiblingCase(i) and i <= this.(SwitchCase).getCaseIndex()
126-
) and
149+
not exists(getClosestPrecedingPatternCase(this)) and
127150
result = this.(SwitchCase).getSelectorExpr().getBasicBlock()
128151
}
129152

‎java/ql/lib/semmle/code/java/controlflow/internal/SwitchCases.qll‎

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
/** Provides utility predicates relating to switch cases. */
2+
3+
import java
4+
5+
/**
6+
* Gets the `i`th `SwitchCase` defined on `switch`, if one exists.
7+
*/
8+
SwitchCase getCase(StmtParent switch, int i) {
9+
result = switch.(SwitchExpr).getCase(i) or result = switch.(SwitchStmt).getCase(i)
10+
}
11+
12+
/**
13+
* Gets the `i`th `PatternCase` defined on `switch`, if one exists.
14+
*/
15+
PatternCase getPatternCase(StmtParent switch, int i) {
16+
result =
17+
rank[i + 1](PatternCase pc, int caseIdx | pc = getCase(switch, caseIdx) | pc order by caseIdx)
18+
}
19+
20+
/**
21+
* Gets the PatternCase after pc, if one exists.
22+
*/
23+
PatternCase getNextPatternCase(PatternCase pc) {
24+
exists(int idx, StmtParent switch |
25+
pc = getPatternCase(switch, idx) and result = getPatternCase(switch, idx + 1)
26+
)
27+
}
28+
29+
int lastCaseIndex(StmtParent switch) {
30+
result = max(int i | any(SwitchCase c).isNthCaseOf(switch, i))
31+
}

0 commit comments

Comments
 (0)