<html><head><meta http-equiv="Content-Type" content="text/html; charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><br class=""><div><br class=""><blockquote type="cite" class=""><div class="">On Jul 2, 2018, at 1:39 AM, Aleksei Sidorin <<a href="mailto:a.sidorin@samsung.com" class="">a.sidorin@samsung.com</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;">Hi George,<br class=""><br class="">Sorry for late response.<br class=""><br class="">16.06.2018 05:14, George Karpenkov via cfe-dev пишет:<br class=""></div><blockquote type="cite" cite="mid:62CB388B-E3BC-4E14-965E-FF1EDE9F39A7@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=""><br class=""><div class=""><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" class="" style="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;"><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 class="" 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;">Yes,<span class="Apple-converted-space"> </span></span><a class="moz-txt-link-freetext" href="https://xkcd.com/297/" moz-do-not-send="true" style="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);">https://xkcd.com/297/</a><span class="" 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;"><span class="Apple-converted-space"> </span>is what I was always thinking while writing new AST matchers. Time-honored tradition :)</span><br class="" 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;"><blockquote type="cite" cite="mid:8C34F101-FA8E-4D90-9B8F-E7A752BEB3E2@apple.com" class="" style="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;"><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 class="" 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;">Sure. If we need this stuff - the design details are subject for discussion and change.</span><br class="" 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;"><br class="" 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;"><blockquote type="cite" cite="mid:8C34F101-FA8E-4D90-9B8F-E7A752BEB3E2@apple.com" class="" style="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;"><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 class="" 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;">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 class="" 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;"><br class="" 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;"><blockquote type="cite" cite="mid:8C34F101-FA8E-4D90-9B8F-E7A752BEB3E2@apple.com" class="" style="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;"><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 class="" 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;">Yes, I know about some researches in this area, but thank you anyway!</span><br class="" 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;"><blockquote type="cite" cite="mid:8C34F101-FA8E-4D90-9B8F-E7A752BEB3E2@apple.com" class="" style="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;"><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 class="" 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;">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 class="" 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;"></div></blockquote><div class=""><br class=""></div><div class="">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><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="">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:</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=""><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="">1. Call to `chroot`.</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=""><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="">2. Do not call `chdir("/")`.</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=""><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="">3. Call anything but `chdir("/").</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=""><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="">Or do you mean something else?</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>The description is helpful.</div><div>I’ve meant that when designing a DSL for describing checkers we should think about the most convenient way to describe checkers:</div><div>and checks are normally described going forward (as you just did), not going backward.</div><div><br class=""></div><div>Overall, sounds very interesting, do you plan about posting a patch on Phabricator?</div><div><br class=""></div><div>What makes me really excited about this is that with such a DSL we could then load checkers from text files at runtime,</div><div>which would give our users a much easier way to write checkers.</div><br class=""><blockquote type="cite" class=""><div 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:62CB388B-E3BC-4E14-965E-FF1EDE9F39A7@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="">Also “explodedNode” is probably an unfortunate name, and “node” would be better.</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="">Naming is always a subject to 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=""><blockquote type="cite" cite="mid:62CB388B-E3BC-4E14-965E-FF1EDE9F39A7@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=""></div><div class="">I am also confused by the semantics of your list, since it mixes AST and “node” statements.</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="">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.</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:62CB388B-E3BC-4E14-965E-FF1EDE9F39A7@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="">Why is only the last matcher wrapped in “node”?</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="">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.</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:62CB388B-E3BC-4E14-965E-FF1EDE9F39A7@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=""><blockquote type="cite" class=""><div class=""><blockquote type="cite" cite="mid:8C34F101-FA8E-4D90-9B8F-E7A752BEB3E2@apple.com" class="" style="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;"><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 class="" 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;">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 class="" 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;"><br class="" 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;"><blockquote type="cite" cite="mid:8C34F101-FA8E-4D90-9B8F-E7A752BEB3E2@apple.com" class="" style="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;"><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 class="" 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;">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 class="" 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;"><br class="" 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;"><blockquote type="cite" cite="mid:8C34F101-FA8E-4D90-9B8F-E7A752BEB3E2@apple.com" class="" style="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;"><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 class="" 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;">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 class="" 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;"><br class="" 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;"><blockquote type="cite" cite="mid:8C34F101-FA8E-4D90-9B8F-E7A752BEB3E2@apple.com" class="" style="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;"><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 class="" 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;"><br class=""></p><br class="Apple-interchange-newline"></div></blockquote></div><br class=""><br class=""><fieldset class="mimeAttachmentHeader"></fieldset><br class=""><pre wrap="" class="">_______________________________________________
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 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><pre class="moz-signature" cols="72" style="caret-color: rgb(0, 0, 0); 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; word-spacing: 0px; -webkit-text-stroke-width: 0px; background-color: rgb(255, 255, 255); text-decoration: none;">--
Best regards,
Aleksei Sidorin,
SRR, Samsung Electronics
</pre><table id="bannersignimg" data-cui-lock="true" namo_lock="" style="caret-color: rgb(0, 0, 0); font-family: Helvetica; letter-spacing: normal; orphans: auto; text-indent: 0px; text-transform: none; 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=""><tbody class=""><tr class=""><td class=""><div class=""> <br class="webkit-block-placeholder"></div></td></tr></tbody></table><table id="confidentialsignimg" data-cui-lock="true" namo_lock="" style="caret-color: rgb(0, 0, 0); font-family: Helvetica; letter-spacing: normal; orphans: auto; text-indent: 0px; text-transform: none; 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=""><tbody class=""><tr class=""><td class=""><p class=""> <span id="cid:cafe_image_0@s-core.co.kr"><Mail Attachment.gif></span> </p></td></tr></tbody></table></div></blockquote></div><br class=""></body></html>