Skip to content

C#: Make CFG library shared #6513

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 2 commits into from
Aug 31, 2021
Merged

C#: Make CFG library shared #6513

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
2 commits
Select commit Hold shift + click to select a range
d405284
C#: Make CFG library shared
hvitved Aug 9, 2021
ab2bc38
C#: Use shared logic in `NodeGraph.ql` test
hvitved Aug 19, 2021
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
2 changes: 1 addition & 1 deletion csharp/ql/lib/semmle/code/csharp/Caching.qll
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -18,7 +18,7 @@ module Stages {

cached
private predicate forceCachingInSameStageRev() {
exists(SplitImpl si)
exists(Split s)
or
exists(SuccessorType st)
or
Expand Down
14 changes: 10 additions & 4 deletions csharp/ql/lib/semmle/code/csharp/controlflow/ControlFlowGraph.qll
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -183,7 +183,7 @@ module ControlFlow {
}

/** Gets a successor node of a given type, if any. */
Node getASuccessorByType(SuccessorType t) { result = getASuccessorByType(this, t) }
Node getASuccessorByType(SuccessorType t) { result = getASuccessor(this, t) }

/** Gets an immediate successor, if any. */
Node getASuccessor() { result = getASuccessorByType(_) }
Expand Down Expand Up @@ -255,9 +255,15 @@ module ControlFlow {

override Callable getEnclosingCallable() { result = this.getCallable() }

override Location getLocation() { result = getCallable().getLocation() }
private Assignable getAssignable() { this = TEntryNode(result) }

override Location getLocation() {
result in [this.getCallable().getLocation(), this.getAssignable().getLocation()]
}

override string toString() { result = "enter " + getCallable().toString() }
override string toString() {
result = "enter " + [this.getCallable().toString(), this.getAssignable().toString()]
}
}

/** A node for a callable exit point, annotated with the type of exit. */
Expand Down Expand Up @@ -314,7 +320,7 @@ module ControlFlow {
* different splits for the element.
*/
class ElementNode extends Node, TElementNode {
private Splitting::Splits splits;
private Splits splits;
private ControlFlowElement cfe;

ElementNode() { this = TElementNode(cfe, splits) }
Expand Down
244 changes: 16 additions & 228 deletions csharp/ql/lib/semmle/code/csharp/controlflow/internal/ControlFlowGraphImpl.qll
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -43,13 +43,22 @@
*/

import csharp
private import semmle.code.csharp.controlflow.ControlFlowGraph::ControlFlow
private import Completion
private import SuccessorType
private import SuccessorTypes
private import Splitting
private import semmle.code.csharp.ExprOrStmtParent
private import semmle.code.csharp.commons.Compilation
import ControlFlowGraphImplShared

/** An element that defines a new CFG scope. */
class CfgScope extends Element, @top_level_exprorstmt_parent {
CfgScope() {
this instanceof Callable
or
// For now, static initializer values have their own scope. Eventually, they
// should be treated like instance initializers.
this.(Assignable).(Modifiable).isStatic()
}
}

/**
* A compilation.
Expand All @@ -71,16 +80,11 @@ CompilationExt getCompilation(SourceFile f) {
result = TBuildless()
}

/** An element that defines a new CFG scope. */
class CfgScope extends Element, @top_level_exprorstmt_parent {
CfgScope() { not this instanceof Attribute }
}

module ControlFlowTree {
class Range_ = @callable or @control_flow_element;

class Range extends Element, Range_ {
Range() { this = getAChild*(any(CfgScope scope)) }
Range() { this = getAChild*(any(@top_level_exprorstmt_parent p | not p instanceof Attribute)) }
}

Element getAChild(Element p) {
Expand All @@ -93,61 +97,6 @@ module ControlFlowTree {
predicate idOf(Range_ x, int y) = equivalenceRelation(id/2)(x, y)
}

abstract private class ControlFlowTree extends ControlFlowTree::Range {
/**
* Holds if `first` is the first element executed within this control
* flow element.
*/
pragma[nomagic]
abstract predicate first(ControlFlowElement first);

/**
* Holds if `last` with completion `c` is a potential last element executed
* within this control flow element.
*/
pragma[nomagic]
abstract predicate last(ControlFlowElement last, Completion c);

/** Holds if abnormal execution of `child` should propagate upwards. */
abstract predicate propagatesAbnormal(ControlFlowElement child);

/**
* Holds if `succ` is a control flow successor for `pred`, given that `pred`
* finishes with completion `c`.
*/
pragma[nomagic]
abstract predicate succ(ControlFlowElement pred, ControlFlowElement succ, Completion c);
}

/**
* Holds if `first` is the first element executed within control flow
* element `cft`.
*/
predicate first(ControlFlowTree cft, ControlFlowElement first) { cft.first(first) }

/**
* Holds if `last` with completion `c` is a potential last element executed
* within control flow element `cft`.
*/
predicate last(ControlFlowTree cft, ControlFlowElement last, Completion c) {
cft.last(last, c)
or
exists(ControlFlowElement cfe |
cft.propagatesAbnormal(cfe) and
last(cfe, last, c) and
not c instanceof NormalCompletion
)
}

/**
* Holds if `succ` is a control flow successor for `pred`, given that `pred`
* finishes with completion `c`.
*/
pragma[nomagic]
predicate succ(ControlFlowElement pred, ControlFlowElement succ, Completion c) {
any(ControlFlowTree cft).succ(pred, succ, c)
}

/** Holds if `first` is first executed when entering `scope`. */
predicate scopeFirst(CfgScope scope, ControlFlowElement first) {
scope =
Expand All @@ -161,8 +110,7 @@ predicate scopeFirst(CfgScope scope, ControlFlowElement first) {
)
or
expr_parent_top_level_adjusted(any(Expr e | first(e, first)), _, scope) and
not scope instanceof Callable and
not scope instanceof InitializerSplitting::InitializedInstanceMember
not scope instanceof Callable
}

/** Holds if `scope` is exited when `last` finishes with completion `c`. */
Expand Down Expand Up @@ -204,53 +152,6 @@ private class ConstructorTree extends ControlFlowTree, Constructor {
}
}

/**
* A control flow element where the children are evaluated following a
* standard left-to-right evaluation. The actual evaluation order is
* determined by the predicate `getChildElement()`.
*/
abstract private class StandardElement extends ControlFlowTree {
/** Gets the `i`th child element, in order of evaluation, starting from 0. */
abstract ControlFlowElement getChildElement(int i);

/** Gets the first child element of this element. */
final ControlFlowElement getFirstChild() { result = this.getChildElement(0) }

/** Holds if this element has no children. */
final predicate isLeafElement() { not exists(this.getFirstChild()) }

/** Gets the last child element of this element. */
final ControlFlowTree getLastChild() {
exists(int last |
result = this.getChildElement(last) and
not exists(this.getChildElement(last + 1))
)
}

final override predicate propagatesAbnormal(ControlFlowElement child) {
child = this.getChildElement(_)
}

override predicate succ(ControlFlowElement pred, ControlFlowElement succ, Completion c) {
exists(int i |
last(this.getChildElement(i), pred, c) and
first(this.getChildElement(i + 1), succ) and
c instanceof NormalCompletion
)
}
}

abstract private class PreOrderTree extends ControlFlowTree {
final override predicate first(ControlFlowElement first) { first = this }
}

abstract private class PostOrderTree extends ControlFlowTree {
override predicate last(ControlFlowElement last, Completion c) {
last = this and
c.isValidFor(last)
}
}

abstract private class SwitchTree extends ControlFlowTree, Switch {
override predicate propagatesAbnormal(ControlFlowElement child) { child = this.getExpr() }

Expand Down Expand Up @@ -368,7 +269,7 @@ module Expressions {
)
}

private class StandardExpr extends StandardElement, PostOrderTree, Expr {
private class StandardExpr extends StandardPostOrderTree, Expr {
StandardExpr() {
// The following expressions need special treatment
not this instanceof LogicalNotExpr and
Expand Down Expand Up @@ -396,21 +297,6 @@ module Expressions {
}

final override ControlFlowElement getChildElement(int i) { result = getExprChild(this, i) }

final override predicate first(ControlFlowElement first) {
first(this.getFirstChild(), first)
or
not exists(this.getFirstChild()) and
first = this
}

final override predicate succ(ControlFlowElement pred, ControlFlowElement succ, Completion c) {
StandardElement.super.succ(pred, succ, c)
or
last(this.getLastChild(), pred, c) and
succ = this and
c instanceof NormalCompletion
}
}

/**
Expand Down Expand Up @@ -1095,7 +981,7 @@ private class PropertyPatternExprExprTree extends PostOrderTree, PropertyPattern
}

module Statements {
private class StandardStmt extends StandardElement, PreOrderTree, Stmt {
private class StandardStmt extends StandardPreOrderTree, Stmt {
StandardStmt() {
// The following statements need special treatment
not this instanceof IfStmt and
Expand Down Expand Up @@ -1140,22 +1026,6 @@ module Statements {
result =
rank[i + 1](ControlFlowElement cfe, int j | cfe = this.getChildElement0(j) | cfe order by j)
}

final override predicate last(ControlFlowElement last, Completion c) {
last(this.getLastChild(), last, c)
or
this.isLeafElement() and
last = this and
c.isValidFor(this)
}

final override predicate succ(ControlFlowElement pred, ControlFlowElement succ, Completion c) {
StandardElement.super.succ(pred, succ, c)
or
pred = this and
first(this.getFirstChild(), succ) and
c instanceof SimpleCompletion
}
}

private class IfStmtTree extends PreOrderTree, IfStmt {
Expand Down Expand Up @@ -1779,88 +1649,6 @@ module Statements {
}
}

cached
private module Cached {
private import semmle.code.csharp.Caching

private predicate isAbnormalExitType(SuccessorType t) {
t instanceof ExceptionSuccessor or t instanceof ExitSuccessor
}

/**
* Internal representation of control flow nodes in the control flow graph.
* The control flow graph is pruned for unreachable nodes.
*/
cached
newtype TNode =
TEntryNode(Callable c) {
Stages::ControlFlowStage::forceCachingInSameStage() and
succEntrySplits(c, _, _, _)
} or
TAnnotatedExitNode(Callable c, boolean normal) {
exists(Reachability::SameSplitsBlock b, SuccessorType t | b.isReachable(_) |
succExitSplits(b.getAnElement(), _, c, t) and
if isAbnormalExitType(t) then normal = false else normal = true
)
} or
TExitNode(Callable c) {
exists(Reachability::SameSplitsBlock b | b.isReachable(_) |
succExitSplits(b.getAnElement(), _, c, _)
)
} or
TElementNode(ControlFlowElement cfe, Splits splits) {
exists(Reachability::SameSplitsBlock b | b.isReachable(splits) | cfe = b.getAnElement())
}

/** Gets a successor node of a given flow type, if any. */
cached
Node getASuccessorByType(Node pred, SuccessorType t) {
// Callable entry node -> callable body
exists(ControlFlowElement succElement, Splits succSplits |
result = TElementNode(succElement, succSplits)
|
succEntrySplits(pred.(Nodes::EntryNode).getCallable(), succElement, succSplits, t)
)
or
exists(ControlFlowElement predElement, Splits predSplits |
pred = TElementNode(predElement, predSplits)
|
// Element node -> callable exit (annotated)
result =
any(Nodes::AnnotatedExitNode exit |
succExitSplits(predElement, predSplits, exit.getCallable(), t) and
if isAbnormalExitType(t) then not exit.isNormal() else exit.isNormal()
)
or
// Element node -> element node
exists(ControlFlowElement succElement, Splits succSplits, Completion c |
result = TElementNode(succElement, succSplits)
|
succSplits(predElement, predSplits, succElement, succSplits, c) and
t = c.getAMatchingSuccessorType()
)
)
or
// Callable exit (annotated) -> callable exit
pred.(Nodes::AnnotatedExitNode).getCallable() = result.(Nodes::ExitNode).getCallable() and
t instanceof SuccessorTypes::NormalSuccessor
}

/**
* Gets a first control flow element executed within `cfe`.
*/
cached
ControlFlowElement getAControlFlowEntryNode(ControlFlowElement cfe) { first(cfe, result) }

/**
* Gets a potential last control flow element executed within `cfe`.
*/
cached
ControlFlowElement getAControlFlowExitNode(ControlFlowElement cfe) { last(cfe, result, _) }
}

import Cached

/** A control flow element that is split into multiple control flow nodes. */
class SplitControlFlowElement extends ControlFlowElement {
SplitControlFlowElement() { strictcount(this.getAControlFlowNode()) > 1 }
Expand Down
Loading