<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On 5 April 2017 at 11:05, Artem Dergachev via cfe-dev <span dir="ltr"><<a href="mailto:cfe-dev@lists.llvm.org" target="_blank">cfe-dev@lists.llvm.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">On second thought, maybe it's quite neat.<br>
<br>
I mean, like, a person who doesn't know anything about AST and about matchers and whatever, could probably do something like that<br>
<br>
$ cat < pattern.c<span class="gmail-"><br>
void bubblesort(int *array, int length) {<br>
for (int i = 0; i < length - 1; ++i)<br>
for (int j = 0; j < length - i - 1; ++j)<br>
if (array[j] > array[j + 1]) {<br>
int tmp = array[j];<br>
array[j] = array[j + 1];<br>
array[j + 1] = tmp;<br>
}<br>
}<br></span>
^D<br>
<br>
and then<br>
<br>
$ clang-finder --pattern pattern.c my_project.c<br>
<br>
and the tool would find all clones of the pattern in the project, by constructing the AST for the pattern and hashing it and looking for clones. The pattern would be in a different AST context, but i guess for the clone checker it shouldn't be a problem, so we wouldn't need to deal with ASTImporter for that.</blockquote><div><br></div><div>Pardon my ignorance, but will the clone checker match patterns that have different variable names (e.g. values instead of array and size instead of length)?</div><div><br></div><div>Also, is it possible to use patterns recursively? E.g. Say I want to detect naive swap and std::swap in the bubble sort:</div><div><br></div><div>swap1.c:</div><div> int tmp = array[j];<br> array[j] = array[j + 1];<br> array[j + 1] = tmp;<br></div><div>swap2.c:</div><div> std::swap(array[j], array[j + 1]);</div><div><br></div><div>pattern.c:</div><div>void bubblesort(int *array, int length) {<br> for (int i = 0; i < length - 1; ++i)<br> for (int j = 0; j < length - i - 1; ++j)<br> if (array[j] > array[j + 1]) {<br> SWAP(array, j)<br> }<br>}<br></div><div><br></div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div class="gmail-HOEnZb"><div class="gmail-h5"><br>
<br>
On 4/4/17 12:25 PM, Vassil Vassilev wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
On 04/04/17 10:59, Raphael Isemann wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
I feel the implementation of an algorithm in the STL and the<br>
equivalent implementation written by the user are usually so different<br>
in terms of syntax that the current clone detection won't work that<br>
well. If we had a constraint for estimating semantic equality, then it<br>
would be a different situation, but I don't expect an implementation<br>
of this anytime soon :).<br>
<br>
However, if we are satisfied with syntactic equality, then this can be<br>
done in a few minutes with the clone detector infrastructure with<br>
something like this pseudocode:<br>
<br>
detector.findClones(RecursiveT<wbr>ypeIIConstraint(),<br>
MinFunctionBodyCount(1), MinComplexity(20));<br>
<br>
This would detect code like this:<br>
<br>
void bubblesort(int *array, int length) {<br>
for (int i = 0; i < length - 1; ++i)<br>
for (int j = 0; j < length - i - 1; ++j)<br>
if (array[j] > array[j + 1]) {<br>
int tmp = array[j];<br>
array[j] = array[j + 1];<br>
array[j + 1] = tmp;<br>
}<br>
}<br>
<br>
int main() {<br>
for (int i = 0; i < length - 1; ++i) // expect-warning{You could<br>
call the function 'bubblesort' instead<br>
for (int j = 0; j < length - i - 1; ++j)<br>
if (array[j] > array[j + 1]) {<br>
int tmp = array[j];<br>
array[j] = array[j + 1];<br>
array[j + 1] = tmp;<br>
}<br>
}<br>
<br>
- Raphael<br>
</blockquote>
<br>
That being said, patches are welcome. The current infrastructure is friendly for implementing semantic clone detection constraints (clones type III). We'd be interested to help if necessary.<br>
<br>
-- Vassil<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
<br>
2017-04-04 10:35 GMT+02:00 Artem Dergachev <<a href="mailto:noqnoqneo@gmail.com" target="_blank">noqnoqneo@gmail.com</a>>:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
+CC CloneDetector guys.<br>
<br>
Hmm, the idea of making body-farms and then using CloneChecker to find<br>
clones of synthesized bodies in the actual code looks curious and funny,<br>
though i'm not immediately seeing how is it superior to ASTMatchers.<br>
<br>
<br>
<br>
On 4/1/17 1:49 PM, Kirill Bobyrev via cfe-dev wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
<br>
Hi Chris,<br>
<br>
To my knowledge, there isn't.<br>
<br>
I don't recall where I got the idea, but I gave it a try last summer<br>
trying to implement a clang-tidy check doing what you proposed. I didn't<br>
have enough time to complete it, though, and I only managed to detect one or<br>
two very simple patterns.<br>
<br>
After thinking about this idea for some time I found that clang-tidy might<br>
be a perfect place for that, not sure whether a separate tool would be<br>
beneficial. The task of detecting a specific pattern is very similar to what<br>
clang-tidy checks do in a wide range of tasks. Also, there'd be a separate<br>
heuristic set for each standard algorithm, which makes the partitioning into<br>
different checks (for each popular standard library algorithm) natural.<br>
<br>
In my opinion, such checks would be useful, I'd be interested in seeing a<br>
proof-of-concept of some sort.<br>
<br>
One more idea I have in mind: it might be interesting to try using<br>
CloneChecker (a check of Clang Static Analyzer) to detect similar patterns<br>
in a generic way, but I'm not sure how beneficial that would be in practice.<br>
Still, might worth a try.<br>
<br>
+CC Alex, he might have some thoughts about this.<br>
<br>
Kind regards,<br>
Kirill<br>
<br>
<br>
On 01/04/17 02:42, Christopher Di Bella via cfe-dev wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
Hey everyone,<br>
<br>
Just wondering if there's a clang tool that can analyse an algorithm to<br>
suggest where standard algorithms can be replace handwritten algos?<br>
E.g.<br>
<br>
int i = 0;<br>
for (; i < v.size(); ++i)<br>
if (v[i] == expected)<br>
break;<br>
if (i != v.size())<br>
some_function(v[i]);<br>
<br>
Can be rewritten to<br>
<br>
auto i = find(v.begin(), v.end(), expected);<br>
if (i != v.end())<br>
some_function(*i);<br>
<br>
or in C++17:<br>
<br>
if (auto i = find(v.begin(), v.end(), expected); i != v.end())<br>
some_function(*i);<br>
<br>
If not, how difficult a task is it to write such a tool? Is there<br>
anything that one should take into special consideration while writing this<br>
tool? Do you think it would have a lot of use-cases? (I do, based on my<br>
company's code base, and code I have seen while marking assignments).<br>
<br>
Cheers,<br>
<br>
Chris<br>
<br>
<br>
______________________________<wbr>_________________<br>
cfe-dev mailing list<br>
<a href="mailto:cfe-dev@lists.llvm.org" target="_blank">cfe-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/cfe-dev</a><br>
</blockquote>
<br>
<br>
<br>
______________________________<wbr>_________________<br>
cfe-dev mailing list<br>
<a href="mailto:cfe-dev@lists.llvm.org" target="_blank">cfe-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/cfe-dev</a><br>
</blockquote>
<br>
</blockquote></blockquote>
<br>
</blockquote>
<br>
______________________________<wbr>_________________<br>
cfe-dev mailing list<br>
<a href="mailto:cfe-dev@lists.llvm.org" target="_blank">cfe-dev@lists.llvm.org</a><br>
<a href="http://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-dev" rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/cfe-dev</a><br>
</div></div></blockquote></div><br></div></div>