<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body text="#000000" bgcolor="#FFFFFF">
<div class="moz-cite-prefix">Hi George,<br>
<br>
Sorry for late response.<br>
<br>
16.06.2018 05:14, George Karpenkov via cfe-dev пишет:<br>
</div>
<blockquote type="cite"
cite="mid:62CB388B-E3BC-4E14-965E-FF1EDE9F39A7@apple.com">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<br class="">
<div><br class="">
<blockquote type="cite" class="">
<div class="">On May 22, 2018, at 4:37 PM, Alexey Sidorin <<a
href="mailto:alexey.v.sidorin@ya.ru" class=""
moz-do-not-send="true">alexey.v.sidorin@ya.ru</a>>
wrote:</div>
<br class="Apple-interchange-newline">
<div class="">
<div class="moz-cite-prefix" style="caret-color: rgb(0, 0,
0); font-family: Helvetica; font-size: 12px; font-style:
normal; font-variant-caps: normal; font-weight: normal;
letter-spacing: normal; text-align: start; text-indent:
0px; text-transform: none; white-space: normal;
word-spacing: 0px; -webkit-text-stroke-width: 0px;
background-color: rgb(255, 255, 255); text-decoration:
none;">22.05.2018 04:35, George Karpenkov пишет:<br
class="">
</div>
<blockquote type="cite"
cite="mid:8C34F101-FA8E-4D90-9B8F-E7A752BEB3E2@apple.com"
style="font-family: Helvetica; font-size: 12px;
font-style: normal; font-variant-caps: normal;
font-weight: normal; letter-spacing: normal; orphans:
auto; text-align: start; text-indent: 0px; text-transform:
none; white-space: normal; widows: auto; word-spacing:
0px; -webkit-text-size-adjust: auto;
-webkit-text-stroke-width: 0px; background-color: rgb(255,
255, 255); text-decoration: none;" class="">
<div class="">Hi Alexey,</div>
<div class=""><br class="">
</div>
<div class="">As classics say, "Any sufficiently
complicated C or Fortran program contains an ad-hoc,
informally-specified, bug-ridden, slow implementation of
half of Common Lisp.”</div>
</blockquote>
<span style="caret-color: rgb(0, 0, 0); font-family:
Helvetica; font-size: 12px; font-style: normal;
font-variant-caps: normal; font-weight: normal;
letter-spacing: normal; text-align: start; text-indent:
0px; text-transform: none; white-space: normal;
word-spacing: 0px; -webkit-text-stroke-width: 0px;
background-color: rgb(255, 255, 255); text-decoration:
none; float: none; display: inline !important;" class="">Yes,<span
class="Apple-converted-space"> </span></span><a
class="moz-txt-link-freetext" href="https://xkcd.com/297/"
style="font-family: Helvetica; font-size: 12px;
font-style: normal; font-variant-caps: normal;
font-weight: normal; letter-spacing: normal; orphans:
auto; text-align: start; text-indent: 0px; text-transform:
none; white-space: normal; widows: auto; word-spacing:
0px; -webkit-text-size-adjust: auto;
-webkit-text-stroke-width: 0px; background-color: rgb(255,
255, 255);" moz-do-not-send="true">https://xkcd.com/297/</a><span
style="caret-color: rgb(0, 0, 0); font-family: Helvetica;
font-size: 12px; font-style: normal; font-variant-caps:
normal; font-weight: normal; letter-spacing: normal;
text-align: start; text-indent: 0px; text-transform: none;
white-space: normal; word-spacing: 0px;
-webkit-text-stroke-width: 0px; background-color: rgb(255,
255, 255); text-decoration: none; float: none; display:
inline !important;" class=""><span
class="Apple-converted-space"> </span>is what I was
always thinking while writing new AST matchers.
Time-honored tradition :)</span><br style="caret-color:
rgb(0, 0, 0); font-family: Helvetica; font-size: 12px;
font-style: normal; font-variant-caps: normal;
font-weight: normal; letter-spacing: normal; text-align:
start; text-indent: 0px; text-transform: none;
white-space: normal; word-spacing: 0px;
-webkit-text-stroke-width: 0px; background-color: rgb(255,
255, 255); text-decoration: none;" class="">
<blockquote type="cite"
cite="mid:8C34F101-FA8E-4D90-9B8F-E7A752BEB3E2@apple.com"
style="font-family: Helvetica; font-size: 12px;
font-style: normal; font-variant-caps: normal;
font-weight: normal; letter-spacing: normal; orphans:
auto; text-align: start; text-indent: 0px; text-transform:
none; white-space: normal; widows: auto; word-spacing:
0px; -webkit-text-size-adjust: auto;
-webkit-text-stroke-width: 0px; background-color: rgb(255,
255, 255); text-decoration: none;" class="">
<div class=""><br class="">
</div>
<div class="">Jokes aside, I think the concept and what
you are doing is great,</div>
<div class="">and we could certainly benefit from
declarative matchers.</div>
<div class="">However, I think the actual implementation
and the set of matchers and predicates would require
quite a bit of bikeshedding.</div>
</blockquote>
<span style="caret-color: rgb(0, 0, 0); font-family:
Helvetica; font-size: 12px; font-style: normal;
font-variant-caps: normal; font-weight: normal;
letter-spacing: normal; text-align: start; text-indent:
0px; text-transform: none; white-space: normal;
word-spacing: 0px; -webkit-text-stroke-width: 0px;
background-color: rgb(255, 255, 255); text-decoration:
none; float: none; display: inline !important;" class="">Sure.
If we need this stuff - the design details are subject for
discussion and change.</span><br style="caret-color:
rgb(0, 0, 0); font-family: Helvetica; font-size: 12px;
font-style: normal; font-variant-caps: normal;
font-weight: normal; letter-spacing: normal; text-align:
start; text-indent: 0px; text-transform: none;
white-space: normal; word-spacing: 0px;
-webkit-text-stroke-width: 0px; background-color: rgb(255,
255, 255); text-decoration: none;" class="">
<br style="caret-color: rgb(0, 0, 0); font-family:
Helvetica; font-size: 12px; font-style: normal;
font-variant-caps: normal; font-weight: normal;
letter-spacing: normal; text-align: start; text-indent:
0px; text-transform: none; white-space: normal;
word-spacing: 0px; -webkit-text-stroke-width: 0px;
background-color: rgb(255, 255, 255); text-decoration:
none;" class="">
<blockquote type="cite"
cite="mid:8C34F101-FA8E-4D90-9B8F-E7A752BEB3E2@apple.com"
style="font-family: Helvetica; font-size: 12px;
font-style: normal; font-variant-caps: normal;
font-weight: normal; letter-spacing: normal; orphans:
auto; text-align: start; text-indent: 0px; text-transform:
none; white-space: normal; widows: auto; word-spacing:
0px; -webkit-text-size-adjust: auto;
-webkit-text-stroke-width: 0px; background-color: rgb(255,
255, 255); text-decoration: none;" class="">
<div class=""><br class="">
</div>
<div class="">Are you familiar with similar works in this
area?</div>
<div class="">E.g. Oracle has a Soufflé project doing a
similar task: <a href="http://souffle-lang.org/"
class="" moz-do-not-send="true">http://souffle-lang.org</a>.</div>
<div class="">They have found achieving high performance
very challenging, and IIRC they resort to generating C++
code from the declaratively described matcher.</div>
</blockquote>
<span style="caret-color: rgb(0, 0, 0); font-family:
Helvetica; font-size: 12px; font-style: normal;
font-variant-caps: normal; font-weight: normal;
letter-spacing: normal; text-align: start; text-indent:
0px; text-transform: none; white-space: normal;
word-spacing: 0px; -webkit-text-stroke-width: 0px;
background-color: rgb(255, 255, 255); text-decoration:
none; float: none; display: inline !important;" class="">My
goal was not to achieve extreme performance but not to
hurt analyzer's performance too much. Don't know how far I
am from this target, unfortunately.</span><br
style="caret-color: rgb(0, 0, 0); font-family: Helvetica;
font-size: 12px; font-style: normal; font-variant-caps:
normal; font-weight: normal; letter-spacing: normal;
text-align: start; text-indent: 0px; text-transform: none;
white-space: normal; word-spacing: 0px;
-webkit-text-stroke-width: 0px; background-color: rgb(255,
255, 255); text-decoration: none;" class="">
<br style="caret-color: rgb(0, 0, 0); font-family:
Helvetica; font-size: 12px; font-style: normal;
font-variant-caps: normal; font-weight: normal;
letter-spacing: normal; text-align: start; text-indent:
0px; text-transform: none; white-space: normal;
word-spacing: 0px; -webkit-text-stroke-width: 0px;
background-color: rgb(255, 255, 255); text-decoration:
none;" class="">
<blockquote type="cite"
cite="mid:8C34F101-FA8E-4D90-9B8F-E7A752BEB3E2@apple.com"
style="font-family: Helvetica; font-size: 12px;
font-style: normal; font-variant-caps: normal;
font-weight: normal; letter-spacing: normal; orphans:
auto; text-align: start; text-indent: 0px; text-transform:
none; white-space: normal; widows: auto; word-spacing:
0px; -webkit-text-size-adjust: auto;
-webkit-text-stroke-width: 0px; background-color: rgb(255,
255, 255); text-decoration: none;" class="">
<div class="">Maybe we would have to do the same in
tablegen spirit.</div>
<div class=""><br class="">
</div>
<div class="">I’m sure there are more such works in the
literature.</div>
</blockquote>
<span style="caret-color: rgb(0, 0, 0); font-family:
Helvetica; font-size: 12px; font-style: normal;
font-variant-caps: normal; font-weight: normal;
letter-spacing: normal; text-align: start; text-indent:
0px; text-transform: none; white-space: normal;
word-spacing: 0px; -webkit-text-stroke-width: 0px;
background-color: rgb(255, 255, 255); text-decoration:
none; float: none; display: inline !important;" class="">Yes,
I know about some researches in this area, but thank you
anyway!</span><br style="caret-color: rgb(0, 0, 0);
font-family: Helvetica; font-size: 12px; font-style:
normal; font-variant-caps: normal; font-weight: normal;
letter-spacing: normal; text-align: start; text-indent:
0px; text-transform: none; white-space: normal;
word-spacing: 0px; -webkit-text-stroke-width: 0px;
background-color: rgb(255, 255, 255); text-decoration:
none;" class="">
<blockquote type="cite"
cite="mid:8C34F101-FA8E-4D90-9B8F-E7A752BEB3E2@apple.com"
style="font-family: Helvetica; font-size: 12px;
font-style: normal; font-variant-caps: normal;
font-weight: normal; letter-spacing: normal; orphans:
auto; text-align: start; text-indent: 0px; text-transform:
none; white-space: normal; widows: auto; word-spacing:
0px; -webkit-text-size-adjust: auto;
-webkit-text-stroke-width: 0px; background-color: rgb(255,
255, 255); text-decoration: none;" class="">
<div class=""><br class="">
</div>
<div class="">
<div class="">
<blockquote type="cite" class="">
<div class="">On May 16, 2018, at 4:37 PM, Alexey
Sidorin via cfe-dev <<a
href="mailto:cfe-dev@lists.llvm.org" class=""
moz-do-not-send="true">cfe-dev@lists.llvm.org</a>>
wrote:</div>
<br class="Apple-interchange-newline">
<div class="">
<div class="">Hello everyone,<br class="">
<br class="">
I'd like to share some results of my
investigation targeted on improvement of Clang
Static Analyzer checker API. You can find some
previous conversation on this topic here:<span
class="Apple-converted-space"> </span><a
href="http://clang-developers.42468.n3.nabble.com/analyzer-RFC-Design-idea-separate-modelling-from-checking-td4059122.html"
class="" moz-do-not-send="true">http://clang-developers.42468.n3.nabble.com/analyzer-RFC-Design-idea-separate-modelling-from-checking-td4059122.html</a>.
In my investigation, I tried to solve a
particular problem of building a checker without
generating new nodes.<br class="">
</div>
</div>
</blockquote>
<div class=""><br class="">
</div>
<div class="">I agree that this is a worthy goal.</div>
<br class="">
<blockquote type="cite" class="">
<div class="">
<div class=""><br class="">
--------- Introduction and design goals
---------<br class="">
<br class="">
In brief, I tried to use matchers-like API to
make CSA checkers look like this:<br class="">
<br class="">
StatementMatcher NotChdir =<br class="">
<span class="Apple-converted-space"> </span>callExpr(unless(callee(functionDecl(hasName("::chdir")))));<br
class="">
Finder.addMatcher(<br class="">
<span class="Apple-converted-space"> </span>hasSequence(<br
class="">
<span class="Apple-converted-space"> </span>postStmt(hasStatement(<br
class="">
<span class="Apple-converted-space"> </span>callExpr(callee(functionDecl(hasName("::chroot")))))),<br
class="">
<span class="Apple-converted-space"> </span>unless(stmtPoint(hasStatement(callExpr(<br
class="">
<span class="Apple-converted-space"> </span>callee(functionDecl(hasName("::chdir"))),<br
class="">
<span class="Apple-converted-space"> </span>hasArgument(0,
hasValue(stringRegion(refersString("/")))))))),<br
class="">
<span class="Apple-converted-space"> </span>explodedNode(anyOf(postStmt(hasStatement(NotChdir)),<br
class="">
<span
class="Apple-converted-space"> </span>callEnter(hasCallExpr(NotChdir))))<br
class="">
<span class="Apple-converted-space"> </span>.bind("bug_node")),<br
class="">
<span class="Apple-converted-space"> </span>&Callback);<br
class="">
Finder.match(G);<br class="">
</div>
</div>
</blockquote>
<div class=""><br class="">
</div>
<div class="">Bikeshedding: I think it’s much better
for the sequence matcher to run from start to end,</div>
<div class="">since that’s how we think about the
execution of a program.</div>
</div>
</div>
</blockquote>
<span style="caret-color: rgb(0, 0, 0); font-family:
Helvetica; font-size: 12px; font-style: normal;
font-variant-caps: normal; font-weight: normal;
letter-spacing: normal; text-align: start; text-indent:
0px; text-transform: none; white-space: normal;
word-spacing: 0px; -webkit-text-stroke-width: 0px;
background-color: rgb(255, 255, 255); text-decoration:
none; float: none; display: inline !important;" class="">Not
sure that I understand completely what do you mean. The
nodes are written in the same sequence as they should be
on the path in ExplodedGraph.</span><br
style="caret-color: rgb(0, 0, 0); font-family: Helvetica;
font-size: 12px; font-style: normal; font-variant-caps:
normal; font-weight: normal; letter-spacing: normal;
text-align: start; text-indent: 0px; text-transform: none;
white-space: normal; word-spacing: 0px;
-webkit-text-stroke-width: 0px; background-color: rgb(255,
255, 255); text-decoration: none;" class="">
</div>
</blockquote>
<div><br class="">
</div>
<div>Yeah, but that doesn’t matter, right? We need to get a good
API for checker writers, and the events are generally
described in their progression as going forward.</div>
</div>
</blockquote>
Sorry, I still didn't get you. The events in the matcher are already
described in the order they should happen to report a bug:<br>
1. Call to `chroot`.<br>
2. Do not call `chdir("/")`.<br>
3. Call anything but `chdir("/").<br>
Or do you mean something else?<br>
<br>
<blockquote type="cite"
cite="mid:62CB388B-E3BC-4E14-965E-FF1EDE9F39A7@apple.com">
<div>
<div>Also “explodedNode” is probably an unfortunate name, and
“node” would be better.</div>
</div>
</blockquote>
Naming is always a subject to change.<br>
<blockquote type="cite"
cite="mid:62CB388B-E3BC-4E14-965E-FF1EDE9F39A7@apple.com">
<div>
<div><br class="">
</div>
<div>I am also confused by the semantics of your list, since it
mixes AST and “node” statements.</div>
</div>
</blockquote>
In this example, statement matchers are implicitly converted to
exploded node matchers and are applied only to ExplodedNodes that
have StmtPoint as their ProgramPoint. Initially, I was thinking it
is a good idea but soon discovered that I was wrong because it
causes a mess between all kinds of StmtPoint. This implicit
conversions is likely to be removed. There is also another implicit
conversion from ProgramPoint matcher to ExplodedNode matcher and I
found it to be much more useful.<br>
<blockquote type="cite"
cite="mid:62CB388B-E3BC-4E14-965E-FF1EDE9F39A7@apple.com">
<div>
<div>Why is only the last matcher wrapped in “node”?</div>
</div>
</blockquote>
All sub-matchers of `hasSequence()` are matchers on ExplodedNode,
but we need to emit a warning on the last node, so we need something
to bind against. The bound node is used to emit a warning on it.<br>
<br>
<blockquote type="cite"
cite="mid:62CB388B-E3BC-4E14-965E-FF1EDE9F39A7@apple.com">
<div><br class="">
<blockquote type="cite" class="">
<div class="">
<blockquote type="cite"
cite="mid:8C34F101-FA8E-4D90-9B8F-E7A752BEB3E2@apple.com"
style="font-family: Helvetica; font-size: 12px;
font-style: normal; font-variant-caps: normal;
font-weight: normal; letter-spacing: normal; orphans:
auto; text-align: start; text-indent: 0px; text-transform:
none; white-space: normal; widows: auto; word-spacing:
0px; -webkit-text-size-adjust: auto;
-webkit-text-stroke-width: 0px; background-color: rgb(255,
255, 255); text-decoration: none;" class="">
<div class="">
<div class=""><br class="">
<blockquote type="cite" class="">
<div class="">
<div class=""><br class="">
and I have managed to make some simple working
examples.<br class="">
<br class="">
The entire diff can be found here:<span
class="Apple-converted-space"> </span><a
href="https://github.com/a-sid/clang/commit/9a0b1d1d9b3cf41b551a663f041f54d5427aa72f"
class="" moz-do-not-send="true">https://github.com/a-sid/clang/commit/9a0b1d1d9b3cf41b551a663f041f54d5427aa72f</a><br
class="">
The code itself:<span
class="Apple-converted-space"> </span><a
href="https://github.com/a-sid/clang/tree/a4"
class="" moz-do-not-send="true">https://github.com/a-sid/clang/tree/a4</a><br
class="">
<br class="">
There are several reasons why I have tried this
approach.<br class="">
<br class="">
1. AST Matchers are already extensively used API
for AST checking. They are available both in
Clang-Tidy and CSA. And I wanted to use existing
functionality as much as possible. So, I decided
to extend an existing API to make its usage
seamless across different kinds of checks:
path-sensitive, AST-based and CFG-based.<br
class="">
<br class="">
2. AST matchers effectively help clients to
avoid a lot of checking of dyn_cast results.
This feature not only makes them more convenient
but also more safe because, in my experience,
forgetting a nullptr/None check is a pretty
common mistake for checker writers.<br class="">
<br class="">
3. Testing of AST matchers don't require writing
C++ code - it can be done interactively with
clang-query tool. And I believe that we need
similar functionality for CSA as well.<br
class="">
</div>
</div>
</blockquote>
<div class=""><br class="">
</div>
<div class="">Moreover, new matchers could be written
without modifying clang. I wonder if we should
support some kind of a plugin infrastructure which
support matchers</div>
<div class="">defined in a text file, e.g. something
along the lines of:</div>
<div class=""><br class="">
</div>
<div class="">clang -cc1 —analyze
-analyzer-checker=core,mymatcher
-analyzer-load-declarative-checker=mymatcher.txt</div>
</div>
</div>
</blockquote>
<span style="caret-color: rgb(0, 0, 0); font-family:
Helvetica; font-size: 12px; font-style: normal;
font-variant-caps: normal; font-weight: normal;
letter-spacing: normal; text-align: start; text-indent:
0px; text-transform: none; white-space: normal;
word-spacing: 0px; -webkit-text-stroke-width: 0px;
background-color: rgb(255, 255, 255); text-decoration:
none; float: none; display: inline !important;" class="">I
planned to reuse dynamic matchers infrastructure and
clang-query for this. clang-query is a command-line tool
but there shouldn't be too much difference where the
matcher string we parse comes from. The problem here is
that, AFAIR, using callbacks with dynamic matchers is
impossible. Still it is a very cool tool for quick matcher
prototyping.</span><br style="caret-color: rgb(0, 0, 0);
font-family: Helvetica; font-size: 12px; font-style:
normal; font-variant-caps: normal; font-weight: normal;
letter-spacing: normal; text-align: start; text-indent:
0px; text-transform: none; white-space: normal;
word-spacing: 0px; -webkit-text-stroke-width: 0px;
background-color: rgb(255, 255, 255); text-decoration:
none;" class="">
<br style="caret-color: rgb(0, 0, 0); font-family:
Helvetica; font-size: 12px; font-style: normal;
font-variant-caps: normal; font-weight: normal;
letter-spacing: normal; text-align: start; text-indent:
0px; text-transform: none; white-space: normal;
word-spacing: 0px; -webkit-text-stroke-width: 0px;
background-color: rgb(255, 255, 255); text-decoration:
none;" class="">
<blockquote type="cite"
cite="mid:8C34F101-FA8E-4D90-9B8F-E7A752BEB3E2@apple.com"
style="font-family: Helvetica; font-size: 12px;
font-style: normal; font-variant-caps: normal;
font-weight: normal; letter-spacing: normal; orphans:
auto; text-align: start; text-indent: 0px; text-transform:
none; white-space: normal; widows: auto; word-spacing:
0px; -webkit-text-size-adjust: auto;
-webkit-text-stroke-width: 0px; background-color: rgb(255,
255, 255); text-decoration: none;" class="">
<div class="">
<div class=""><br class="">
<blockquote type="cite" class="">
<div class="">
<div class=""><br class="">
I didn't want to replace existing checker API.
Instead, I tried to make new possibilities
usable independently or together with existing.<br
class="">
<br class="">
--------- Design and implementation ---------<br
class="">
<br class="">
The implementation consisted of a number of
steps.<br class="">
<br class="">
1. Allow matching nodes of path-sensitive graph
like usual AST nodes. To make this possible,
three actions were needed:<br class="">
1.1. ASTTypeTraits and DynTypedNode were
extended to support path-sensitive nodes:
ExplodedNode, ProgramState, SVal, SymExpr, etc.
The implementation with graph node support is
moved into a separate class (ASTGraphTypeTraits)
in ento namespace to resolve cyclic dependencies
(they are still exist, unfortunately, but are
header-only, so we can build the PoC).<br
class="">
1.2. Some additions to AST matchers were made
to add support for new kinds of nodes.<br
class="">
1.3. To make MatchFinder able to query specific
options not supported by pure AST, it was
augmented with "Contexts". A matcher that needs
to query the path-sensitive engine asks the
Finder for the required Context which provides
specific helper functions.<br class="">
<br class="">
As the result of this step, we are able to write
matchers like expr(hasArgument(0,
hasValue(stringRegion(refersString("/"))))).<br
class="">
<br class="">
2. Create an engine for graph exploration and
matching.<br class="">
<span class="Apple-converted-space"> </span>Unlike
normal AST matchers, hasSequence is a
path-sensitive matcher. It is launched against
ExplodedGraph. These matchers are handled by
GraphMatchFinder object. While searching a
graph, it collects matches. Each match contains
a pointer to the corresponding matcher and State
ID of this match. The way how matches are
translated from one state ID to another is
determined by matcher operators.<br class="">
<br class="">
<span class="Apple-converted-space"> </span>For
example, SequenceVariadicOperator, which is the
base of hasSequence() matcher, has "positive"
and "negative" sub-matches. Each positive
matcher has its corresponding State ID. In order
to advance to the next State ID, a node being
matched should match all "negative" matchers
before the next "positive" matchers and the next
"positive" matcher itself. Failure in matching
"negative" matcher discards the match.<br
class="">
<br class="">
<span class="Apple-converted-space"> </span>The
role of GraphMatchFinder is similar to
MatchFinder: it is only responsible for graph
exploration and keeping bound nodes and
matchers.<br class="">
<br class="">
3. Manage bound nodes.<br class="">
<span class="Apple-converted-space"> </span>While
matching a single graph node, BoundNodes from
AST MatchFinder are used. AST matchers for
path-sensitive nodes support bindings
out-of-the-box. However, the situation with
graph matching is a bit different. For graph
matching, we have another system of bound nodes.
Each graph node has a related map of bounds aka
GDMTy (yes, the name is not a coincidence).
GDMTy is a mapping from match ID to
BoundNodesMap which, in part, is effectively a
map from std::string to DynTypedNodes. This look
pretty much like how GDM is organized in
ExplodedGraph, just without one level of
indirection (it can be added, though).<br
class="">
<br class="">
<span class="Apple-converted-space"> </span>MatchFinder
contexts should allow support of their own
bindings. This is how equalsBoundNode() matcher
works for path-sensitive nodes: it just queries
all available contexts for the binding.<br
class="">
<br class="">
Finally, I have managed to make two checkers
work in this way: ChrootChecker (which is
present in the introduction) and
TestAfterDivZeroChecker. Both them can be found
in ChrootCheckerV2.cpp and
TestAfterDivZeroCheckerV2.cpp correspondingly.
They act like normal checkers: produce warnings
and use visitors. The main difference is that
they cannot generate sinks and use
checkEndAnalysis callback. The code of these
checkers can be found here:<br class="">
<br class="">
<a
href="https://github.com/a-sid/clang/blob/a4/lib/StaticAnalyzer/Checkers/ChrootCheckerV2.cpp"
class="" moz-do-not-send="true">https://github.com/a-sid/clang/blob/a4/lib/StaticAnalyzer/Checkers/ChrootCheckerV2.cpp</a><br
class="">
<a class="moz-txt-link-freetext"
href="https://github.com/a-sid/clang/blob/a4/lib/StaticAnalyzer/Checkers/TestAfterDivZeroCheckerV2.cpp"
moz-do-not-send="true">https://github.com/a-sid/clang/blob/a4/lib/StaticAnalyzer/Checkers/TestAfterDivZeroCheckerV2.cpp</a><br
class="">
<br class="">
<br class="">
-------- Some features --------<br class="">
<br class="">
1.The design of bindings has an interesting
consequence: it enables the dynamic
introspection of GDM which was pretty hard
before. (Hello alpha renaming?)<br class="">
2. Nothing prevents matchers to be used with
existing checker API for simplifying conditional
checking inside callbacks. The matchers are not
planned as the replacement for the current API,
but look like a nice complementary part.<br
class="">
3. Implicit conversion of
Matcher<ProgramPoint> to
Matcher<ExplodedNode> and
Matcher<SymExpr || MemRegion> to
Matcher<SVal> for writing shorter code.<br
class="">
<br class="">
-------- Not implemented/not checked yet
--------<br class="">
I tried to keep the PoC as minimal as possible.
As the result, some features are not implemented
yet, but I believe they can be added.<br
class="">
1. Usage of matchers inside checker callbacks<br
class="">
<span class="Apple-converted-space"> </span>This
is not exactly unimplemented, but is still
untested.<br class="">
2. Dynamic matchers (clang-query interface)<br
class="">
<span class="Apple-converted-space"> </span>In
addition to work for supporting dynamic nodes (I
don't know how many efforts it can take), we
need to enable matching against AST nodes, not
graph. But it doesn't look as a problem, we can
just make matchers polymorphic.<br class="">
3. Binding to successfully matched paths is not
implemented yet - only bindings to separate
nodes. I wonder if we need path bindings at all.<br
class="">
4. Some corner cases are still FIXMEs:
single-node sequences, for example.<br class="">
5. GDM is not based on immutable data structures
like it is done in CSA - it is just an STL map.
Its performance can be poor (full copy on every
new node), but I don't think that changing it to
use immutable structures is hard.<br class="">
6. Matching on-the-fly<br class="">
<span class="Apple-converted-space"> </span>GraphMatchFinder
should support on-the-fly matching during
ExplodedGraph building. For this support, we
should just call its advance() method each time
a new node is created. However, this possibility
wasn't checked yet.<br class="">
7. Matching CFG and CallGraph isn't implemented
because it was considered to be far out of
simple PoC.<br class="">
8. Only sequential matching is available now,
and I didn't try to implement other operators
yet. So, implementing a checker similar to
PthreadLock can be tricky or even impossible for
now.<br class="">
<br class="">
-------- Known and potential issues --------<br
class="">
From matchers' side:<br class="">
1. Some tests don't pass because they rely on
the checker ability to generate sink nodes. Our
matchers cannot do it by design so tests don't
pass.<br class="">
</div>
</div>
</blockquote>
<div class=""><br class="">
</div>
<div class="">Actually I would disagree with this one:
I think it would be better to support that, since
many errors are considered fatal.</div>
<div class="">(but that of course would require
running the checkers on a stream of events, rather
than on the already constructed graph)</div>
</div>
</div>
</blockquote>
<span style="caret-color: rgb(0, 0, 0); font-family:
Helvetica; font-size: 12px; font-style: normal;
font-variant-caps: normal; font-weight: normal;
letter-spacing: normal; text-align: start; text-indent:
0px; text-transform: none; white-space: normal;
word-spacing: 0px; -webkit-text-stroke-width: 0px;
background-color: rgb(255, 255, 255); text-decoration:
none; float: none; display: inline !important;" class="">As
I answered to Artem, this is technically possible (but
still undesirable, I think) because matchers fire their
given callbacks on match, and callbacks are much less
limited in their possibilities.</span><br
style="caret-color: rgb(0, 0, 0); font-family: Helvetica;
font-size: 12px; font-style: normal; font-variant-caps:
normal; font-weight: normal; letter-spacing: normal;
text-align: start; text-indent: 0px; text-transform: none;
white-space: normal; word-spacing: 0px;
-webkit-text-stroke-width: 0px; background-color: rgb(255,
255, 255); text-decoration: none;" class="">
<br style="caret-color: rgb(0, 0, 0); font-family:
Helvetica; font-size: 12px; font-style: normal;
font-variant-caps: normal; font-weight: normal;
letter-spacing: normal; text-align: start; text-indent:
0px; text-transform: none; white-space: normal;
word-spacing: 0px; -webkit-text-stroke-width: 0px;
background-color: rgb(255, 255, 255); text-decoration:
none;" class="">
<blockquote type="cite"
cite="mid:8C34F101-FA8E-4D90-9B8F-E7A752BEB3E2@apple.com"
style="font-family: Helvetica; font-size: 12px;
font-style: normal; font-variant-caps: normal;
font-weight: normal; letter-spacing: normal; orphans:
auto; text-align: start; text-indent: 0px; text-transform:
none; white-space: normal; widows: auto; word-spacing:
0px; -webkit-text-size-adjust: auto;
-webkit-text-stroke-width: 0px; background-color: rgb(255,
255, 255); text-decoration: none;" class="">
<div class="">
<div class=""><br class="">
<blockquote type="cite" class="">
<div class="">
<div class="">2. Representing checker bindings as
a map can be less effective than storing data in
structures. I didn't measure the overhead, so I
cannot give any numbers.<br class="">
3. Matchers are called on every node
independently of its type. This is not what
CheckerManager does. I wonder if this detail can
affect performance as well.<br class="">
</div>
</div>
</blockquote>
<div class=""><br class="">
</div>
<div class="">I would guess it would affect it hugely,
and getting the performance right would be the
biggest challenge for declarative matchers.</div>
</div>
</div>
</blockquote>
<span style="caret-color: rgb(0, 0, 0); font-family:
Helvetica; font-size: 12px; font-style: normal;
font-variant-caps: normal; font-weight: normal;
letter-spacing: normal; text-align: start; text-indent:
0px; text-transform: none; white-space: normal;
word-spacing: 0px; -webkit-text-stroke-width: 0px;
background-color: rgb(255, 255, 255); text-decoration:
none; float: none; display: inline !important;" class="">That's
sad. I'll try to measure the overhead but I'm not sure
I'll be able to do it soon.</span><br style="caret-color:
rgb(0, 0, 0); font-family: Helvetica; font-size: 12px;
font-style: normal; font-variant-caps: normal;
font-weight: normal; letter-spacing: normal; text-align:
start; text-indent: 0px; text-transform: none;
white-space: normal; word-spacing: 0px;
-webkit-text-stroke-width: 0px; background-color: rgb(255,
255, 255); text-decoration: none;" class="">
<br style="caret-color: rgb(0, 0, 0); font-family:
Helvetica; font-size: 12px; font-style: normal;
font-variant-caps: normal; font-weight: normal;
letter-spacing: normal; text-align: start; text-indent:
0px; text-transform: none; white-space: normal;
word-spacing: 0px; -webkit-text-stroke-width: 0px;
background-color: rgb(255, 255, 255); text-decoration:
none;" class="">
<blockquote type="cite"
cite="mid:8C34F101-FA8E-4D90-9B8F-E7A752BEB3E2@apple.com"
style="font-family: Helvetica; font-size: 12px;
font-style: normal; font-variant-caps: normal;
font-weight: normal; letter-spacing: normal; orphans:
auto; text-align: start; text-indent: 0px; text-transform:
none; white-space: normal; widows: auto; word-spacing:
0px; -webkit-text-size-adjust: auto;
-webkit-text-stroke-width: 0px; background-color: rgb(255,
255, 255); text-decoration: none;" class="">
<div class="">
<div class=""><br class="">
<blockquote type="cite" class="">
<div class="">
<div class="">4. Problems with cyclic
dependencies. clangStaticAnalyzer has a
dependency on clangASTMatchers, therefore,
clangASTMatchers cannot depend on
clangStaticAnalyzer. However, if we want
ASTMatchers to support static analyzer data
structures, there should be a backward
dependency. Now this dependency is header-only.<br
class="">
5. Code duplication. This is mostly fine for a
sandbox but needs to be reduced.<br class="">
<br class="">
From analyzer's side:<br class="">
1. Many events are not reflected in the final
ExplodedGraph. For example, checkers can receive
PointerEscape event, but the event itself will
not be recorded in the ExplodedGraph - only
changes made by checkers will. That's also true
for Stmt nodes: I noticed same issues with
PostCondition. This makes matching a bit harder.
Should we add some information into
ExplodedGraph?<br class="">
2. (Minor) Some static analyzer data structures
don't support traditional LLVM casting methods
(dyn_cast, isa) because they lack classof()
method. I have fixed this internally and will
put a patch on review soon.<br class="">
<br class="">
-------- Conclusion --------<br class="">
Finally, there is a graph matching engine
supporting basic functionality and two checkers
using it. I apologize for not starting the
discussion earlier, but I just wasn't sure that
the approach will work. Is anybody interested to
have this stuff in upstream (maybe, changed or
improved)? If yes, I'll be happy to contribute
this work patch-by-patch and continue its
improvement. If no - well, I had enough fun
playing with it.<br class="">
<br class="">
_______________________________________________<br
class="">
cfe-dev mailing list<br class="">
<a href="mailto:cfe-dev@lists.llvm.org" class=""
moz-do-not-send="true">cfe-dev@lists.llvm.org</a><br
class="">
<a class="moz-txt-link-freetext"
href="http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev"
moz-do-not-send="true">http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev</a><br
class="">
</div>
</div>
</blockquote>
</div>
<br class="">
</div>
</blockquote>
<p style="caret-color: rgb(0, 0, 0); font-family: Helvetica;
font-size: 12px; font-style: normal; font-variant-caps:
normal; font-weight: normal; letter-spacing: normal;
text-align: start; text-indent: 0px; text-transform: none;
white-space: normal; word-spacing: 0px;
-webkit-text-stroke-width: 0px; background-color: rgb(255,
255, 255); text-decoration: none;" class=""><br class="">
</p>
<br class="Apple-interchange-newline">
</div>
</blockquote>
</div>
<br class="">
<!--'"--><br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
cfe-dev mailing list
<a class="moz-txt-link-abbreviated" href="mailto:cfe-dev@lists.llvm.org">cfe-dev@lists.llvm.org</a>
<a class="moz-txt-link-freetext" href="http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev">http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev</a>
</pre>
</blockquote>
<p><br>
</p>
<pre class="moz-signature" cols="72">--
Best regards,
Aleksei Sidorin,
SRR, Samsung Electronics
</pre>
<table id=bannersignimg data-cui-lock="true" namo_lock><tr><td><p> </p>
</td></tr></table><table id=confidentialsignimg data-cui-lock="true" namo_lock><tr><td><p> <img style="border: 0px solid currentColor; border-image: none; width: 520px; height: 144px; display: inline-block;" unselectable="on" data-cui-image="true" src="cid:cafe_image_0@s-core.co.kr"> </p>
</td></tr></table></body>
</html>
<img src='http://ext.w1.samsung.net/mail/ext/v1/external/status/update?userid=a.sidorin&do=bWFpbElEPTIwMTgwNzAyMDgzOTMyZXVjYXMxcDI5MzM4YWU4MjhkMzc2ZGJmOTEwZTY3ZDJlMTI4OTJjYSZyZWNpcGllbnRBZGRyZXNzPWNmZS1kZXZAbGlzdHMubGx2bS5vcmc_' border=0 width=0 height=0 style='display:none'>