[PATCH] D72362: [clang-tidy] misc-no-recursion: a new check

[Roman Lebedev via Phabricator via cfe-commits]

This revision was automatically updated to reflect the committed changes.
Closed by commit rG49bffa5f8b79: [clang-tidy] misc-no-recursion: a new check 
(authored by lebedev.ri).

Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D72362/new/

https://reviews.llvm.org/D72362

Files:
  clang-tools-extra/clang-tidy/misc/CMakeLists.txt
  clang-tools-extra/clang-tidy/misc/MiscTidyModule.cpp
  clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp
  clang-tools-extra/clang-tidy/misc/NoRecursionCheck.h
  clang-tools-extra/docs/ReleaseNotes.rst
  clang-tools-extra/docs/clang-tidy/checks/list.rst
  clang-tools-extra/docs/clang-tidy/checks/misc-no-recursion.rst
  clang-tools-extra/test/clang-tidy/checkers/misc-no-recursion.cpp

Index: clang-tools-extra/test/clang-tidy/checkers/misc-no-recursion.cpp
===
--- /dev/null
+++ clang-tools-extra/test/clang-tidy/checkers/misc-no-recursion.cpp
@@ -0,0 +1,179 @@
+// RUN: %check_clang_tidy %s misc-no-recursion %t
+
+// We don't have the definition of this function,
+// so we can't tell anything about it..
+void external();
+
+// This function is obviously not recursive.
+void no_recursion() {
+}
+
+// Since we don't know what `external()` does,
+// we don't know if this is recursive or not.
+void maybe_no_recursion() {
+  external();
+}
+
+// Function calls itself - obviously a recursion.
+void endless_recursion() {
+  endless_recursion();
+}
+
+// CHECK-NOTES: :[[@LINE-4]]:6: warning: function 'endless_recursion' is within a recursive call chain [misc-no-recursion]
+// CHECK-NOTES: :[[@LINE-5]]:6: note: example recursive call chain, starting from function 'endless_recursion'
+// CHECK-NOTES: :[[@LINE-5]]:3: note: Frame #1: function 'endless_recursion' calls function 'endless_recursion' here:
+// CHECK-NOTES: :[[@LINE-6]]:3: note: ... which was the starting point of the recursive call chain; there may be other cycles
+
+bool external_oracle();
+bool another_external_oracle();
+
+// Function calls itself if some external function said so - recursion.
+void maybe_endless_recursion() {
+  if (external_oracle())
+maybe_endless_recursion();
+}
+
+// CHECK-NOTES: :[[@LINE-5]]:6: warning: function 'maybe_endless_recursion' is within a recursive call chain [misc-no-recursion]
+// CHECK-NOTES: :[[@LINE-6]]:6: note: example recursive call chain, starting from function 'maybe_endless_recursion'
+// CHECK-NOTES: :[[@LINE-5]]:5: note: Frame #1: function 'maybe_endless_recursion' calls function 'maybe_endless_recursion' here:
+// CHECK-NOTES: :[[@LINE-6]]:5: note: ... which was the starting point of the recursive call chain; there may be other cycles
+
+// Obviously-constrained recursion.
+void recursive_countdown(unsigned x) {
+  if (x == 0)
+return;
+  recursive_countdown(x - 1);
+}
+
+// CHECK-NOTES: :[[@LINE-6]]:6: warning: function 'recursive_countdown' is within a recursive call chain [misc-no-recursion]
+// CHECK-NOTES: :[[@LINE-7]]:6: note: example recursive call chain, starting from function 'recursive_countdown'
+// CHECK-NOTES: :[[@LINE-5]]:3: note: Frame #1: function 'recursive_countdown' calls function 'recursive_countdown' here:
+// CHECK-NOTES: :[[@LINE-6]]:3: note: ... which was the starting point of the recursive call chain; there may be other cycles
+
+void indirect_recursion();
+void conditionally_executed() {
+  if (external_oracle())
+indirect_recursion();
+}
+void indirect_recursion() {
+  if (external_oracle())
+conditionally_executed();
+}
+
+// CHECK-NOTES: :[[@LINE-10]]:6: warning: function 'indirect_recursion' is within a recursive call chain [misc-no-recursion]
+// CHECK-NOTES: :[[@LINE-10]]:6: warning: function 'conditionally_executed' is within a recursive call chain [misc-no-recursion]
+// CHECK-NOTES: :[[@LINE-12]]:6: note: example recursive call chain, starting from function 'indirect_recursion'
+// CHECK-NOTES: :[[@LINE-6]]:5: note: Frame #1: function 'indirect_recursion' calls function 'conditionally_executed' here:
+// CHECK-NOTES: :[[@LINE-11]]:5: note: Frame #2: function 'conditionally_executed' calls function 'indirect_recursion' here:
+// CHECK-NOTES: :[[@LINE-12]]:5: note: ... which was the starting point of the recursive call chain; there may be other cycles
+
+void taint();
+void maybe_selfrecursion_with_two_backedges() {
+  if (external_oracle())
+maybe_selfrecursion_with_two_backedges();
+  taint();
+  if (another_external_oracle())
+maybe_selfrecursion_with_two_backedges();
+}
+
+// CHECK-NOTES: :[[@LINE-8]]:6: warning: function 'maybe_selfrecursion_with_two_backedges' is within a recursive call chain [misc-no-recursion]
+// CHECK-NOTES: :[[@LINE-9]]:6: note: example recursive call chain, starting from function 'maybe_selfrecursion_with_two_backedges'
+// CHECK-NOTES: :[[@LINE-8]]:5: note: Frame #1: function 'maybe_selfrecursion_with_two_backedges' calls function 'maybe_selfrecursion_with_two_backedges' here:
+// 

[PATCH] D72362: [clang-tidy] misc-no-recursion: a new check

[Roman Lebedev via Phabricator via cfe-commits]

lebedev.ri updated this revision to Diff 244509.
lebedev.ri marked 8 inline comments as done.
lebedev.ri added a comment.

In D72362#1874690 , @aaron.ballman 
wrote:

> LGTM aside from some nits.


Thank you for the review!
Nits addressed.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D72362/new/

https://reviews.llvm.org/D72362

Files:
  clang-tools-extra/clang-tidy/misc/CMakeLists.txt
  clang-tools-extra/clang-tidy/misc/MiscTidyModule.cpp
  clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp
  clang-tools-extra/clang-tidy/misc/NoRecursionCheck.h
  clang-tools-extra/docs/ReleaseNotes.rst
  clang-tools-extra/docs/clang-tidy/checks/list.rst
  clang-tools-extra/docs/clang-tidy/checks/misc-no-recursion.rst
  clang-tools-extra/test/clang-tidy/checkers/misc-no-recursion.cpp

Index: clang-tools-extra/test/clang-tidy/checkers/misc-no-recursion.cpp
===
--- /dev/null
+++ clang-tools-extra/test/clang-tidy/checkers/misc-no-recursion.cpp
@@ -0,0 +1,179 @@
+// RUN: %check_clang_tidy %s misc-no-recursion %t
+
+// We don't have the definition of this function,
+// so we can't tell anything about it..
+void external();
+
+// This function is obviously not recursive.
+void no_recursion() {
+}
+
+// Since we don't know what `external()` does,
+// we don't know if this is recursive or not.
+void maybe_no_recursion() {
+  external();
+}
+
+// Function calls itself - obviously a recursion.
+void endless_recursion() {
+  endless_recursion();
+}
+
+// CHECK-NOTES: :[[@LINE-4]]:6: warning: function 'endless_recursion' is within a recursive call chain [misc-no-recursion]
+// CHECK-NOTES: :[[@LINE-5]]:6: note: example recursive call chain, starting from function 'endless_recursion'
+// CHECK-NOTES: :[[@LINE-5]]:3: note: Frame #1: function 'endless_recursion' calls function 'endless_recursion' here:
+// CHECK-NOTES: :[[@LINE-6]]:3: note: ... which was the starting point of the recursive call chain; there may be other cycles
+
+bool external_oracle();
+bool another_external_oracle();
+
+// Function calls itself if some external function said so - recursion.
+void maybe_endless_recursion() {
+  if (external_oracle())
+maybe_endless_recursion();
+}
+
+// CHECK-NOTES: :[[@LINE-5]]:6: warning: function 'maybe_endless_recursion' is within a recursive call chain [misc-no-recursion]
+// CHECK-NOTES: :[[@LINE-6]]:6: note: example recursive call chain, starting from function 'maybe_endless_recursion'
+// CHECK-NOTES: :[[@LINE-5]]:5: note: Frame #1: function 'maybe_endless_recursion' calls function 'maybe_endless_recursion' here:
+// CHECK-NOTES: :[[@LINE-6]]:5: note: ... which was the starting point of the recursive call chain; there may be other cycles
+
+// Obviously-constrained recursion.
+void recursive_countdown(unsigned x) {
+  if (x == 0)
+return;
+  recursive_countdown(x - 1);
+}
+
+// CHECK-NOTES: :[[@LINE-6]]:6: warning: function 'recursive_countdown' is within a recursive call chain [misc-no-recursion]
+// CHECK-NOTES: :[[@LINE-7]]:6: note: example recursive call chain, starting from function 'recursive_countdown'
+// CHECK-NOTES: :[[@LINE-5]]:3: note: Frame #1: function 'recursive_countdown' calls function 'recursive_countdown' here:
+// CHECK-NOTES: :[[@LINE-6]]:3: note: ... which was the starting point of the recursive call chain; there may be other cycles
+
+void indirect_recursion();
+void conditionally_executed() {
+  if (external_oracle())
+indirect_recursion();
+}
+void indirect_recursion() {
+  if (external_oracle())
+conditionally_executed();
+}
+
+// CHECK-NOTES: :[[@LINE-10]]:6: warning: function 'indirect_recursion' is within a recursive call chain [misc-no-recursion]
+// CHECK-NOTES: :[[@LINE-10]]:6: warning: function 'conditionally_executed' is within a recursive call chain [misc-no-recursion]
+// CHECK-NOTES: :[[@LINE-12]]:6: note: example recursive call chain, starting from function 'indirect_recursion'
+// CHECK-NOTES: :[[@LINE-6]]:5: note: Frame #1: function 'indirect_recursion' calls function 'conditionally_executed' here:
+// CHECK-NOTES: :[[@LINE-11]]:5: note: Frame #2: function 'conditionally_executed' calls function 'indirect_recursion' here:
+// CHECK-NOTES: :[[@LINE-12]]:5: note: ... which was the starting point of the recursive call chain; there may be other cycles
+
+void taint();
+void maybe_selfrecursion_with_two_backedges() {
+  if (external_oracle())
+maybe_selfrecursion_with_two_backedges();
+  taint();
+  if (another_external_oracle())
+maybe_selfrecursion_with_two_backedges();
+}
+
+// CHECK-NOTES: :[[@LINE-8]]:6: warning: function 'maybe_selfrecursion_with_two_backedges' is within a recursive call chain [misc-no-recursion]
+// CHECK-NOTES: :[[@LINE-9]]:6: note: example recursive call chain, starting from function 'maybe_selfrecursion_with_two_backedges'
+// CHECK-NOTES: :[[@LINE-8]]:5: note: Frame #1: function 

[PATCH] D72362: [clang-tidy] misc-no-recursion: a new check

[Aaron Ballman via Phabricator via cfe-commits]

aaron.ballman accepted this revision.
aaron.ballman added a comment.
This revision is now accepted and ready to land.

LGTM aside from some nits.




Comment at: clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp:70
+
+template  class SmartSmallSetVector {
+public:

lebedev.ri wrote:
> aaron.ballman wrote:
> > Same complaint here about `Smart` -- should probably just be a 
> > `SmallSetVector`.
> There already is a `SmallSetVector`, and it does have different semantics,
> i've added a code comment explaining their differences, PTAL.
> 
> For now, i'd prefer to keep this as-is, but afterwards i suspect
> i might be able to "upstream" this into `SmallSetVector` itself,
> thus getting rid of `SmartSmallSetVector`.
> 
> Let me know if this makes sense?
Okay, that's reasonable enough. Can you add a FIXME suggesting that plan in the 
code?



Comment at: clang-tools-extra/docs/clang-tidy/checks/misc-no-recursion.rst:6
+
+Finds strongly connected functions (by analyzing call graph for SCC's
+that are loops), diagnoses each function in the cycle,

call graph -> the call graph

And you should probably spell out SCC.



Comment at: clang-tools-extra/docs/clang-tidy/checks/misc-no-recursion.rst:8
+that are loops), diagnoses each function in the cycle,
+and displays one example of possible call graph loop (recursion).
+

call graph -> a call graph



Comment at: clang-tools-extra/docs/clang-tidy/checks/misc-no-recursion.rst:8
+that are loops), diagnoses each function in the cycle,
+and displays one example of possible call graph loop (recursion).

lebedev.ri wrote:
> aaron.ballman wrote:
> > Eugene.Zelenko wrote:
> > > It'll be reasonable to add links to relevant coding guidelines.
> > Agreed.
> Is this better?
Looks great!



Comment at: clang-tools-extra/test/clang-tidy/checkers/misc-no-recursion.cpp:127
+}
+
+// CHECK-NOTES: :[[@LINE-14]]:13: warning: function 
'indirect_recursion_with_depth2' is part of call graph loop [misc-no-recursion]

lebedev.ri wrote:
> JonasToth wrote:
> > Does the check find recursion through function pointers? (Probably not? 
> > Should be noted as limitation).
> > 
> > Please add cases from lambdas. And cases where recursion happens in 
> > templates / only with one of multiple instantiations.
> This indeed gets blinded by function pointers, test added.
> 
> As for lambdas, i'm not sure what specifically you mean?
> The lambda itself can't be recursive i think?
> https://godbolt.org/z/GYLRnB
There are techniques to make lambdas recursive, but maybe we don't need to 
catch those (at least not initially). e.g., 
https://riptutorial.com/cplusplus/example/8508/recursive-lambdas


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D72362/new/

https://reviews.llvm.org/D72362



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D72362: [clang-tidy] misc-no-recursion: a new check

[Roman Lebedev via Phabricator via cfe-commits]

lebedev.ri added inline comments.



Comment at: clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp:28
+// 2. it is immutable, the way it was constructed it will stay.
+template  class ImmutableSmartSet {
+  ArrayRef Vector;

aaron.ballman wrote:
> "Smart" is not a descriptive term. This seems like it's an 
> `ImmutableSmallSet`?
I was really trying to convey the fact that it can either be in small-sized 
mode (linear search over vector),
or in set mode (constructed with a large size, search in set).
But then, SmallVector also can be in small-sized mode (stack allocation), and 
large-sized mode (heap).
So here i guess `ImmutableSmallSet` name should work..



Comment at: clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp:70
+
+template  class SmartSmallSetVector {
+public:

aaron.ballman wrote:
> Same complaint here about `Smart` -- should probably just be a 
> `SmallSetVector`.
There already is a `SmallSetVector`, and it does have different semantics,
i've added a code comment explaining their differences, PTAL.

For now, i'd prefer to keep this as-is, but afterwards i suspect
i might be able to "upstream" this into `SmallSetVector` itself,
thus getting rid of `SmartSmallSetVector`.

Let me know if this makes sense?



Comment at: clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp:203
+Decl *D = N->getDecl();
+diag(D->getLocation(), "function '%0' is part of call graph loop")
+<< cast(D)->getName();

aaron.ballman wrote:
> I think "call graph loop" is a bit much for a diagnostic -- how about `%0 is 
> within a recursive call chain` or something along those lines?
Sure, that should be fine too.



Comment at: clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp:204
+diag(D->getLocation(), "function '%0' is part of call graph loop")
+<< cast(D)->getName();
+  }

aaron.ballman wrote:
> Drop the call to `getName()` and remove the single quotes from the diagnostic 
> around `%0`, and just pass in the `NamedDecl` -- the diagnostics engine will 
> do the right thing (and it gives better names for strange things like 
> operators).
Nice!



Comment at: clang-tools-extra/docs/clang-tidy/checks/misc-no-recursion.rst:8
+that are loops), diagnoses each function in the cycle,
+and displays one example of possible call graph loop (recursion).

aaron.ballman wrote:
> Eugene.Zelenko wrote:
> > It'll be reasonable to add links to relevant coding guidelines.
> Agreed.
Is this better?



Comment at: clang-tools-extra/test/clang-tidy/checkers/misc-no-recursion.cpp:153
+// CHECK-NOTES: :[[@LINE-7]]:3: note: Frame #1: function 'boo' calls function 
'bar' here:
+// CHECK-NOTES: :[[@LINE-14]]:18: note: Frame #2: function 'bar' calls 
function 'boo' here:
+// CHECK-NOTES: :[[@LINE-15]]:18: note: ... which was the starting point of 
this call graph

NoQ wrote:
> lebedev.ri wrote:
> > lebedev.ri wrote:
> > > NoQ wrote:
> > > > Aha, yeah, the warning is present, i guess that part is correct, but 
> > > > look how your note `function 'bar' calls function 'boo' here:` doesn't 
> > > > really point into the body of 'bar'. In this case it still makes sense 
> > > > because it's easy to see that 'foo' is called from 'bar', but the chain 
> > > > of default arguments may be arbitrarily long (what if 'boo' has yet 
> > > > another default argument?). You might want to add a separate facility 
> > > > just to handle this edge case.
> > > To make this more readable, the diag is:
> > > ```
> > > /builddirs/llvm-project/build-Clang9-unknown/tools/clang/tools/extra/test/clang-tidy/checkers/Output/misc-no-recursion.cpp.tmp.cpp:138:5:
> > >  warning: function 'boo' is part of call graph loop [misc-no-recursion]
> > > int boo();
> > > ^
> > > /builddirs/llvm-project/build-Clang9-unknown/tools/clang/tools/extra/test/clang-tidy/checkers/Output/misc-no-recursion.cpp.tmp.cpp:140:6:
> > >  warning: function 'bar' is part of call graph loop [misc-no-recursion]
> > > void bar() {
> > >  ^
> > > /builddirs/llvm-project/build-Clang9-unknown/tools/clang/tools/extra/test/clang-tidy/checkers/Output/misc-no-recursion.cpp.tmp.cpp:138:5:
> > >  note: Example call graph loop, starting from function 'boo'
> > > int boo();
> > > ^
> > > /builddirs/llvm-project/build-Clang9-unknown/tools/clang/tools/extra/test/clang-tidy/checkers/Output/misc-no-recursion.cpp.tmp.cpp:145:3:
> > >  note: Frame #1: function 'boo' calls function 'bar' here:
> > >   bar();
> > >   ^
> > > /builddirs/llvm-project/build-Clang9-unknown/tools/clang/tools/extra/test/clang-tidy/checkers/Output/misc-no-recursion.cpp.tmp.cpp:139:18:
> > >  note: Frame #2: function 'bar' calls function 'boo' here:
> > > void foo(int x = boo()) {}
> > >  ^
> > > ```
> > > Am i looking at this wrong, or all the info is present?
> > Edit: right, `bar->foo` 

[PATCH] D72362: [clang-tidy] misc-no-recursion: a new check

[Roman Lebedev via Phabricator via cfe-commits]

lebedev.ri updated this revision to Diff 244354.
lebedev.ri marked 16 inline comments as done and an inline comment as not done.
lebedev.ri added a comment.

Ping.

@aaron.ballman thank you for taking a look!
Addressed review notes.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D72362/new/

https://reviews.llvm.org/D72362

Files:
  clang-tools-extra/clang-tidy/misc/CMakeLists.txt
  clang-tools-extra/clang-tidy/misc/MiscTidyModule.cpp
  clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp
  clang-tools-extra/clang-tidy/misc/NoRecursionCheck.h
  clang-tools-extra/docs/ReleaseNotes.rst
  clang-tools-extra/docs/clang-tidy/checks/list.rst
  clang-tools-extra/docs/clang-tidy/checks/misc-no-recursion.rst
  clang-tools-extra/test/clang-tidy/checkers/misc-no-recursion.cpp

Index: clang-tools-extra/test/clang-tidy/checkers/misc-no-recursion.cpp
===
--- /dev/null
+++ clang-tools-extra/test/clang-tidy/checkers/misc-no-recursion.cpp
@@ -0,0 +1,179 @@
+// RUN: %check_clang_tidy %s misc-no-recursion %t
+
+// We don't have the definition of this function,
+// so we can't tell anything about it..
+void external();
+
+// This function is obviously not recursive.
+void no_recursion() {
+}
+
+// Since we don't know what `external()` does,
+// we don't know if this is recursive or not.
+void maybe_no_recursion() {
+  external();
+}
+
+// Function calls itself - obviously a recursion.
+void endless_recursion() {
+  endless_recursion();
+}
+
+// CHECK-NOTES: :[[@LINE-4]]:6: warning: function 'endless_recursion' is within a recursive call chain [misc-no-recursion]
+// CHECK-NOTES: :[[@LINE-5]]:6: note: example recursive call chain, starting from function 'endless_recursion'
+// CHECK-NOTES: :[[@LINE-5]]:3: note: Frame #1: function 'endless_recursion' calls function 'endless_recursion' here:
+// CHECK-NOTES: :[[@LINE-6]]:3: note: ... which was the starting point of the recursive call chain; there may be other cycles
+
+bool external_oracle();
+bool another_external_oracle();
+
+// Function calls itself if some external function said so - recursion.
+void maybe_endless_recursion() {
+  if (external_oracle())
+maybe_endless_recursion();
+}
+
+// CHECK-NOTES: :[[@LINE-5]]:6: warning: function 'maybe_endless_recursion' is within a recursive call chain [misc-no-recursion]
+// CHECK-NOTES: :[[@LINE-6]]:6: note: example recursive call chain, starting from function 'maybe_endless_recursion'
+// CHECK-NOTES: :[[@LINE-5]]:5: note: Frame #1: function 'maybe_endless_recursion' calls function 'maybe_endless_recursion' here:
+// CHECK-NOTES: :[[@LINE-6]]:5: note: ... which was the starting point of the recursive call chain; there may be other cycles
+
+// Obviously-constrained recursion.
+void recursive_countdown(unsigned x) {
+  if (x == 0)
+return;
+  recursive_countdown(x - 1);
+}
+
+// CHECK-NOTES: :[[@LINE-6]]:6: warning: function 'recursive_countdown' is within a recursive call chain [misc-no-recursion]
+// CHECK-NOTES: :[[@LINE-7]]:6: note: example recursive call chain, starting from function 'recursive_countdown'
+// CHECK-NOTES: :[[@LINE-5]]:3: note: Frame #1: function 'recursive_countdown' calls function 'recursive_countdown' here:
+// CHECK-NOTES: :[[@LINE-6]]:3: note: ... which was the starting point of the recursive call chain; there may be other cycles
+
+void indirect_recursion();
+void conditionally_executed() {
+  if (external_oracle())
+indirect_recursion();
+}
+void indirect_recursion() {
+  if (external_oracle())
+conditionally_executed();
+}
+
+// CHECK-NOTES: :[[@LINE-10]]:6: warning: function 'indirect_recursion' is within a recursive call chain [misc-no-recursion]
+// CHECK-NOTES: :[[@LINE-10]]:6: warning: function 'conditionally_executed' is within a recursive call chain [misc-no-recursion]
+// CHECK-NOTES: :[[@LINE-12]]:6: note: example recursive call chain, starting from function 'indirect_recursion'
+// CHECK-NOTES: :[[@LINE-6]]:5: note: Frame #1: function 'indirect_recursion' calls function 'conditionally_executed' here:
+// CHECK-NOTES: :[[@LINE-11]]:5: note: Frame #2: function 'conditionally_executed' calls function 'indirect_recursion' here:
+// CHECK-NOTES: :[[@LINE-12]]:5: note: ... which was the starting point of the recursive call chain; there may be other cycles
+
+void taint();
+void maybe_selfrecursion_with_two_backedges() {
+  if (external_oracle())
+maybe_selfrecursion_with_two_backedges();
+  taint();
+  if (another_external_oracle())
+maybe_selfrecursion_with_two_backedges();
+}
+
+// CHECK-NOTES: :[[@LINE-8]]:6: warning: function 'maybe_selfrecursion_with_two_backedges' is within a recursive call chain [misc-no-recursion]
+// CHECK-NOTES: :[[@LINE-9]]:6: note: example recursive call chain, starting from function 'maybe_selfrecursion_with_two_backedges'
+// CHECK-NOTES: :[[@LINE-8]]:5: note: Frame #1: function 'maybe_selfrecursion_with_two_backedges' calls function 

[PATCH] D72362: [clang-tidy] misc-no-recursion: a new check

[Aaron Ballman via Phabricator via cfe-commits]

aaron.ballman added inline comments.



Comment at: clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp:28
+// 2. it is immutable, the way it was constructed it will stay.
+template  class ImmutableSmartSet {
+  ArrayRef Vector;

"Smart" is not a descriptive term. This seems like it's an `ImmutableSmallSet`?



Comment at: clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp:64
+  return llvm::find(Vector, V) == Vector.end() ? 0 : 1;
+} else {
+  return Set.count(V);

No `else` after `return`.



Comment at: clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp:70
+
+template  class SmartSmallSetVector {
+public:

Same complaint here about `Smart` -- should probably just be a `SmallSetVector`.



Comment at: clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp:203
+Decl *D = N->getDecl();
+diag(D->getLocation(), "function '%0' is part of call graph loop")
+<< cast(D)->getName();

I think "call graph loop" is a bit much for a diagnostic -- how about `%0 is 
within a recursive call chain` or something along those lines?



Comment at: clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp:204
+diag(D->getLocation(), "function '%0' is part of call graph loop")
+<< cast(D)->getName();
+  }

Drop the call to `getName()` and remove the single quotes from the diagnostic 
around `%0`, and just pass in the `NamedDecl` -- the diagnostics engine will do 
the right thing (and it gives better names for strange things like operators).



Comment at: clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp:230
+  diag(CycleEntryFn->getLocation(),
+   "Example call graph loop, starting from function '%0'",
+   DiagnosticIDs::Note)

Example -> example

I think "call graph group" might be a bit much for a diagnostic -- how about 
`example recursive call chain, starting from %0`



Comment at: clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp:232
+   DiagnosticIDs::Note)
+  << cast(CycleEntryFn)->getName();
+  for (int CurFrame = 1, NumFrames = CyclicCallStack.size();

Same here (and elsewhere, I'll stop commenting on them).



Comment at: clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp:249-250
+  diag(CyclicCallStack.back().CallExpr->getBeginLoc(),
+   "... which was the starting point of this call graph."
+   " This report is non-exhaustive, there may be other cycles.",
+   DiagnosticIDs::Note);

Diagnostic text should not be full sentences.

`... which was the starting point of the recursive call chain; there may be 
other cycles`



Comment at: clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp:259
+  CG.addToCallGraph(const_cast(TU));
+  // CG.viewGraph();
+

Remove commented out code.



Comment at: clang-tools-extra/docs/clang-tidy/checks/misc-no-recursion.rst:8
+that are loops), diagnoses each function in the cycle,
+and displays one example of possible call graph loop (recursion).

Eugene.Zelenko wrote:
> It'll be reasonable to add links to relevant coding guidelines.
Agreed.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D72362/new/

https://reviews.llvm.org/D72362



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D72362: [clang-tidy] misc-no-recursion: a new check

[Artem Dergachev via Phabricator via cfe-commits]

NoQ added inline comments.



Comment at: clang-tools-extra/test/clang-tidy/checkers/misc-no-recursion.cpp:153
+// CHECK-NOTES: :[[@LINE-7]]:3: note: Frame #1: function 'boo' calls function 
'bar' here:
+// CHECK-NOTES: :[[@LINE-14]]:18: note: Frame #2: function 'bar' calls 
function 'boo' here:
+// CHECK-NOTES: :[[@LINE-15]]:18: note: ... which was the starting point of 
this call graph

lebedev.ri wrote:
> lebedev.ri wrote:
> > NoQ wrote:
> > > Aha, yeah, the warning is present, i guess that part is correct, but look 
> > > how your note `function 'bar' calls function 'boo' here:` doesn't really 
> > > point into the body of 'bar'. In this case it still makes sense because 
> > > it's easy to see that 'foo' is called from 'bar', but the chain of 
> > > default arguments may be arbitrarily long (what if 'boo' has yet another 
> > > default argument?). You might want to add a separate facility just to 
> > > handle this edge case.
> > To make this more readable, the diag is:
> > ```
> > /builddirs/llvm-project/build-Clang9-unknown/tools/clang/tools/extra/test/clang-tidy/checkers/Output/misc-no-recursion.cpp.tmp.cpp:138:5:
> >  warning: function 'boo' is part of call graph loop [misc-no-recursion]
> > int boo();
> > ^
> > /builddirs/llvm-project/build-Clang9-unknown/tools/clang/tools/extra/test/clang-tidy/checkers/Output/misc-no-recursion.cpp.tmp.cpp:140:6:
> >  warning: function 'bar' is part of call graph loop [misc-no-recursion]
> > void bar() {
> >  ^
> > /builddirs/llvm-project/build-Clang9-unknown/tools/clang/tools/extra/test/clang-tidy/checkers/Output/misc-no-recursion.cpp.tmp.cpp:138:5:
> >  note: Example call graph loop, starting from function 'boo'
> > int boo();
> > ^
> > /builddirs/llvm-project/build-Clang9-unknown/tools/clang/tools/extra/test/clang-tidy/checkers/Output/misc-no-recursion.cpp.tmp.cpp:145:3:
> >  note: Frame #1: function 'boo' calls function 'bar' here:
> >   bar();
> >   ^
> > /builddirs/llvm-project/build-Clang9-unknown/tools/clang/tools/extra/test/clang-tidy/checkers/Output/misc-no-recursion.cpp.tmp.cpp:139:18:
> >  note: Frame #2: function 'bar' calls function 'boo' here:
> > void foo(int x = boo()) {}
> >  ^
> > ```
> > Am i looking at this wrong, or all the info is present?
> Edit: right, `bar->foo` edge is not shown there.
Yup. And, well, semantically it's kind of correct, because it's not `foo()` 
that calls `boo()`, but it's `bar()`'s responsiblity to call `boo()` directly 
before calling `foo()`. So it's more like a three-way relationship:
```
misc-no-recursion.cpp.tmp.cpp:139:18: note: Frame #1: function 'bar' calls 
function 'boo' here:
void foo(int x = boo()) {}
 ^
misc-no-recursion.cpp.tmp.cpp:141:7: note: ...in order to compute default 
argument for function 'foo' here:
  foo();
  ^
```
So i'd imagine `CallRecord`s potentially containing arbitrarily long chains of 
backreferences from a default argument initializer to the respective 
`CXXDefaultArgExpr` that we're currently visiting (which may in turn be part of 
another default argument initializer, given that those are arbitrary 
expressions).

(it's of course up to you whether you want to deal with this immediately or 
later, i'm just ranting, don't mind me)


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D72362/new/

https://reviews.llvm.org/D72362



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D72362: [clang-tidy] misc-no-recursion: a new check

[Roman Lebedev via Phabricator via cfe-commits]

lebedev.ri marked an inline comment as not done.
lebedev.ri added inline comments.



Comment at: clang-tools-extra/test/clang-tidy/checkers/misc-no-recursion.cpp:153
+// CHECK-NOTES: :[[@LINE-7]]:3: note: Frame #1: function 'boo' calls function 
'bar' here:
+// CHECK-NOTES: :[[@LINE-14]]:18: note: Frame #2: function 'bar' calls 
function 'boo' here:
+// CHECK-NOTES: :[[@LINE-15]]:18: note: ... which was the starting point of 
this call graph

lebedev.ri wrote:
> NoQ wrote:
> > Aha, yeah, the warning is present, i guess that part is correct, but look 
> > how your note `function 'bar' calls function 'boo' here:` doesn't really 
> > point into the body of 'bar'. In this case it still makes sense because 
> > it's easy to see that 'foo' is called from 'bar', but the chain of default 
> > arguments may be arbitrarily long (what if 'boo' has yet another default 
> > argument?). You might want to add a separate facility just to handle this 
> > edge case.
> To make this more readable, the diag is:
> ```
> /builddirs/llvm-project/build-Clang9-unknown/tools/clang/tools/extra/test/clang-tidy/checkers/Output/misc-no-recursion.cpp.tmp.cpp:138:5:
>  warning: function 'boo' is part of call graph loop [misc-no-recursion]
> int boo();
> ^
> /builddirs/llvm-project/build-Clang9-unknown/tools/clang/tools/extra/test/clang-tidy/checkers/Output/misc-no-recursion.cpp.tmp.cpp:140:6:
>  warning: function 'bar' is part of call graph loop [misc-no-recursion]
> void bar() {
>  ^
> /builddirs/llvm-project/build-Clang9-unknown/tools/clang/tools/extra/test/clang-tidy/checkers/Output/misc-no-recursion.cpp.tmp.cpp:138:5:
>  note: Example call graph loop, starting from function 'boo'
> int boo();
> ^
> /builddirs/llvm-project/build-Clang9-unknown/tools/clang/tools/extra/test/clang-tidy/checkers/Output/misc-no-recursion.cpp.tmp.cpp:145:3:
>  note: Frame #1: function 'boo' calls function 'bar' here:
>   bar();
>   ^
> /builddirs/llvm-project/build-Clang9-unknown/tools/clang/tools/extra/test/clang-tidy/checkers/Output/misc-no-recursion.cpp.tmp.cpp:139:18:
>  note: Frame #2: function 'bar' calls function 'boo' here:
> void foo(int x = boo()) {}
>  ^
> ```
> Am i looking at this wrong, or all the info is present?
Edit: right, `bar->foo` edge is not shown there.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D72362/new/

https://reviews.llvm.org/D72362



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D72362: [clang-tidy] misc-no-recursion: a new check

[Roman Lebedev via Phabricator via cfe-commits]

lebedev.ri added inline comments.



Comment at: clang-tools-extra/test/clang-tidy/checkers/misc-no-recursion.cpp:153
+// CHECK-NOTES: :[[@LINE-7]]:3: note: Frame #1: function 'boo' calls function 
'bar' here:
+// CHECK-NOTES: :[[@LINE-14]]:18: note: Frame #2: function 'bar' calls 
function 'boo' here:
+// CHECK-NOTES: :[[@LINE-15]]:18: note: ... which was the starting point of 
this call graph

NoQ wrote:
> Aha, yeah, the warning is present, i guess that part is correct, but look how 
> your note `function 'bar' calls function 'boo' here:` doesn't really point 
> into the body of 'bar'. In this case it still makes sense because it's easy 
> to see that 'foo' is called from 'bar', but the chain of default arguments 
> may be arbitrarily long (what if 'boo' has yet another default argument?). 
> You might want to add a separate facility just to handle this edge case.
To make this more readable, the diag is:
```
/builddirs/llvm-project/build-Clang9-unknown/tools/clang/tools/extra/test/clang-tidy/checkers/Output/misc-no-recursion.cpp.tmp.cpp:138:5:
 warning: function 'boo' is part of call graph loop [misc-no-recursion]
int boo();
^
/builddirs/llvm-project/build-Clang9-unknown/tools/clang/tools/extra/test/clang-tidy/checkers/Output/misc-no-recursion.cpp.tmp.cpp:140:6:
 warning: function 'bar' is part of call graph loop [misc-no-recursion]
void bar() {
 ^
/builddirs/llvm-project/build-Clang9-unknown/tools/clang/tools/extra/test/clang-tidy/checkers/Output/misc-no-recursion.cpp.tmp.cpp:138:5:
 note: Example call graph loop, starting from function 'boo'
int boo();
^
/builddirs/llvm-project/build-Clang9-unknown/tools/clang/tools/extra/test/clang-tidy/checkers/Output/misc-no-recursion.cpp.tmp.cpp:145:3:
 note: Frame #1: function 'boo' calls function 'bar' here:
  bar();
  ^
/builddirs/llvm-project/build-Clang9-unknown/tools/clang/tools/extra/test/clang-tidy/checkers/Output/misc-no-recursion.cpp.tmp.cpp:139:18:
 note: Frame #2: function 'bar' calls function 'boo' here:
void foo(int x = boo()) {}
 ^
```
Am i looking at this wrong, or all the info is present?


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D72362/new/

https://reviews.llvm.org/D72362



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D72362: [clang-tidy] misc-no-recursion: a new check

[Roman Lebedev via Phabricator via cfe-commits]

lebedev.ri updated this revision to Diff 242725.
lebedev.ri marked an inline comment as done.
lebedev.ri added a comment.

Fixup disclaimer printing, NFC.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D72362/new/

https://reviews.llvm.org/D72362

Files:
  clang-tools-extra/clang-tidy/misc/CMakeLists.txt
  clang-tools-extra/clang-tidy/misc/MiscTidyModule.cpp
  clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp
  clang-tools-extra/clang-tidy/misc/NoRecursionCheck.h
  clang-tools-extra/docs/ReleaseNotes.rst
  clang-tools-extra/docs/clang-tidy/checks/list.rst
  clang-tools-extra/docs/clang-tidy/checks/misc-no-recursion.rst
  clang-tools-extra/test/clang-tidy/checkers/misc-no-recursion.cpp

Index: clang-tools-extra/test/clang-tidy/checkers/misc-no-recursion.cpp
===
--- /dev/null
+++ clang-tools-extra/test/clang-tidy/checkers/misc-no-recursion.cpp
@@ -0,0 +1,147 @@
+// RUN: %check_clang_tidy %s misc-no-recursion %t
+
+// We don't have the definition of this function,
+// so we can't tell anything about it..
+void external();
+
+// This function is obviously not recursive.
+void no_recursion() {
+}
+
+// Since we don't know what `external()` does,
+// we don't know if this is recursive or not.
+void maybe_no_recursion() {
+  external();
+}
+
+// Function calls itself - obviously a recursion.
+void endless_recursion() {
+  endless_recursion();
+}
+
+// CHECK-NOTES: :[[@LINE-4]]:6: warning: function 'endless_recursion' is part of call graph loop [misc-no-recursion]
+// CHECK-NOTES: :[[@LINE-5]]:6: note: Example call graph loop, starting from function 'endless_recursion'
+// CHECK-NOTES: :[[@LINE-5]]:3: note: Frame #1: function 'endless_recursion' calls function 'endless_recursion' here:
+// CHECK-NOTES: :[[@LINE-6]]:3: note: ... which was the starting point of this call graph. This report is non-exhaustive, there may be other cycles.
+
+bool external_oracle();
+bool another_external_oracle();
+
+// Function calls itself if some external function said so - recursion.
+void maybe_endless_recursion() {
+  if (external_oracle())
+maybe_endless_recursion();
+}
+
+// CHECK-NOTES: :[[@LINE-5]]:6: warning: function 'maybe_endless_recursion' is part of call graph loop [misc-no-recursion]
+// CHECK-NOTES: :[[@LINE-6]]:6: note: Example call graph loop, starting from function 'maybe_endless_recursion'
+// CHECK-NOTES: :[[@LINE-5]]:5: note: Frame #1: function 'maybe_endless_recursion' calls function 'maybe_endless_recursion' here:
+// CHECK-NOTES: :[[@LINE-6]]:5: note: ... which was the starting point of this call graph. This report is non-exhaustive, there may be other cycles.
+
+// Obviously-constrained recursion.
+void recursive_countdown(unsigned x) {
+  if (x == 0)
+return;
+  recursive_countdown(x - 1);
+}
+
+// CHECK-NOTES: :[[@LINE-6]]:6: warning: function 'recursive_countdown' is part of call graph loop [misc-no-recursion]
+// CHECK-NOTES: :[[@LINE-7]]:6: note: Example call graph loop, starting from function 'recursive_countdown'
+// CHECK-NOTES: :[[@LINE-5]]:3: note: Frame #1: function 'recursive_countdown' calls function 'recursive_countdown' here:
+// CHECK-NOTES: :[[@LINE-6]]:3: note: ... which was the starting point of this call graph. This report is non-exhaustive, there may be other cycles.
+
+void indirect_recursion();
+void conditionally_executed() {
+  if (external_oracle())
+indirect_recursion();
+}
+void indirect_recursion() {
+  if (external_oracle())
+conditionally_executed();
+}
+
+// CHECK-NOTES: :[[@LINE-10]]:6: warning: function 'indirect_recursion' is part of call graph loop [misc-no-recursion]
+// CHECK-NOTES: :[[@LINE-10]]:6: warning: function 'conditionally_executed' is part of call graph loop [misc-no-recursion]
+// CHECK-NOTES: :[[@LINE-12]]:6: note: Example call graph loop, starting from function 'indirect_recursion'
+// CHECK-NOTES: :[[@LINE-6]]:5: note: Frame #1: function 'indirect_recursion' calls function 'conditionally_executed' here:
+// CHECK-NOTES: :[[@LINE-11]]:5: note: Frame #2: function 'conditionally_executed' calls function 'indirect_recursion' here:
+// CHECK-NOTES: :[[@LINE-12]]:5: note: ... which was the starting point of this call graph. This report is non-exhaustive, there may be other cycles.
+
+void taint();
+void maybe_selfrecursion_with_two_backedges() {
+  if (external_oracle())
+maybe_selfrecursion_with_two_backedges();
+  taint();
+  if (another_external_oracle())
+maybe_selfrecursion_with_two_backedges();
+}
+
+// CHECK-NOTES: :[[@LINE-8]]:6: warning: function 'maybe_selfrecursion_with_two_backedges' is part of call graph loop [misc-no-recursion]
+// CHECK-NOTES: :[[@LINE-9]]:6: note: Example call graph loop, starting from function 'maybe_selfrecursion_with_two_backedges'
+// CHECK-NOTES: :[[@LINE-8]]:5: note: Frame #1: function 'maybe_selfrecursion_with_two_backedges' calls function 'maybe_selfrecursion_with_two_backedges' here:

[PATCH] D72362: [clang-tidy] misc-no-recursion: a new check

[Artem Dergachev via Phabricator via cfe-commits]

NoQ added inline comments.



Comment at: clang-tools-extra/test/clang-tidy/checkers/misc-no-recursion.cpp:153
+// CHECK-NOTES: :[[@LINE-7]]:3: note: Frame #1: function 'boo' calls function 
'bar' here:
+// CHECK-NOTES: :[[@LINE-14]]:18: note: Frame #2: function 'bar' calls 
function 'boo' here:
+// CHECK-NOTES: :[[@LINE-15]]:18: note: ... which was the starting point of 
this call graph

Aha, yeah, the warning is present, i guess that part is correct, but look how 
your note `function 'bar' calls function 'boo' here:` doesn't really point into 
the body of 'bar'. In this case it still makes sense because it's easy to see 
that 'foo' is called from 'bar', but the chain of default arguments may be 
arbitrarily long (what if 'boo' has yet another default argument?). You might 
want to add a separate facility just to handle this edge case.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D72362/new/

https://reviews.llvm.org/D72362



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D72362: [clang-tidy] misc-no-recursion: a new check

[Roman Lebedev via Phabricator via cfe-commits]

lebedev.ri added inline comments.



Comment at: clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp:21
+
+inline bool operator==(const CallGraphNode::CallRecord ,
+   const CallGraphNode::CallRecord ) {

NoQ wrote:
> lebedev.ri wrote:
> > JonasToth wrote:
> > > That should be in the `CallGraph` code, adding a private operator 
> > > overload does not feel right.
> > I didn't want to put this into callgraph, because this
> > cements the fact that we do not care about sourceloc,
> > which may not be true for other users.
> > I can put it there, but if told so by it's code owners (@NoQ ?)
> Does this need to be `operator==`? It looks like `DenseMap` uses 
> `DenseMapInfo::isEqual` instead, maybe just call it "isEqual" to avoid 
> confusion?
Now that i store `Expr*` in `CallGraphNode::CallRecord`,
this comparison operator appears to be automatically provided,
which means we really should provide our own to avoid confusing behavior
as compared to the DenseMap behavior.
So i'd say yes.



Comment at: clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp:31
+
+// Specialize DenseMapInfo for clang::CallGraphNode::CallRecord.
+template <> struct DenseMapInfo {

NoQ wrote:
> lebedev.ri wrote:
> > JonasToth wrote:
> > > That stuff, too.
> > (same reasoning)
> So what exactly happens if you link together two different translation units 
> with different specializations of `DenseMapInfo` and start 
> passing such dense maps from one TU to the other?
> 
> (ODR violations are definitely not my specialty)
A good question, for another time.



Comment at: clang/lib/Analysis/CallGraph.cpp:103-106
   // Include the evaluation of the default argument.
   void VisitCXXDefaultArgExpr(CXXDefaultArgExpr *E) {
 Visit(E->getExpr());
   }

NoQ wrote:
> Note that if a function `void foo(int x = boo()) { ... }` is invoked as `void 
> bar() { foo(); foo(); }`, you'd get two different-in-every-way call records 
> from the same function `bar()` to the same function `boo()` with the same 
> source location (the location of call-expression `boo()` within the 
> `ParmVarDecl` for `x`). I'm legit curious if this is a problem for your 
> checker.
Test case added (is this how you'd imagine it to be a problem?).
I'm not sure what you mean by a problem, it is diagnosed at least.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D72362/new/

https://reviews.llvm.org/D72362



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D72362: [clang-tidy] misc-no-recursion: a new check

[Roman Lebedev via Phabricator via cfe-commits]

lebedev.ri updated this revision to Diff 242713.
lebedev.ri marked 11 inline comments as done.
lebedev.ri added a comment.

@NoQ Thank you for taking a look!

Rebased, addressed most of the review notes (some tests could be added), split 
callgraph changes into a separate review.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D72362/new/

https://reviews.llvm.org/D72362

Files:
  clang-tools-extra/clang-tidy/misc/CMakeLists.txt
  clang-tools-extra/clang-tidy/misc/MiscTidyModule.cpp
  clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp
  clang-tools-extra/clang-tidy/misc/NoRecursionCheck.h
  clang-tools-extra/docs/ReleaseNotes.rst
  clang-tools-extra/docs/clang-tidy/checks/list.rst
  clang-tools-extra/docs/clang-tidy/checks/misc-no-recursion.rst
  clang-tools-extra/test/clang-tidy/checkers/misc-no-recursion.cpp

Index: clang-tools-extra/test/clang-tidy/checkers/misc-no-recursion.cpp
===
--- /dev/null
+++ clang-tools-extra/test/clang-tidy/checkers/misc-no-recursion.cpp
@@ -0,0 +1,155 @@
+// RUN: %check_clang_tidy %s misc-no-recursion %t
+
+// We don't have the definition of this function,
+// so we can't tell anything about it..
+void external();
+
+// This function is obviously not recursive.
+void no_recursion() {
+}
+
+// Since we don't know what `external()` does,
+// we don't know if this is recursive or not.
+void maybe_no_recursion() {
+  external();
+}
+
+// Function calls itself - obviously a recursion.
+void endless_recursion() {
+  endless_recursion();
+}
+
+// CHECK-NOTES: :[[@LINE-4]]:6: warning: function 'endless_recursion' is part of call graph loop [misc-no-recursion]
+// CHECK-NOTES: :[[@LINE-5]]:6: note: Example call graph loop, starting from function 'endless_recursion'
+// CHECK-NOTES: :[[@LINE-5]]:3: note: Frame #1: function 'endless_recursion' calls function 'endless_recursion' here:
+// CHECK-NOTES: :[[@LINE-6]]:3: note: ... which was the starting point of this call graph
+// CHECK-NOTES: :[[@LINE-7]]:3: note: This report is non-exhaustive. There may be other cycles.
+
+bool external_oracle();
+bool another_external_oracle();
+
+// Function calls itself if some external function said so - recursion.
+void maybe_endless_recursion() {
+  if (external_oracle())
+maybe_endless_recursion();
+}
+
+// CHECK-NOTES: :[[@LINE-5]]:6: warning: function 'maybe_endless_recursion' is part of call graph loop [misc-no-recursion]
+// CHECK-NOTES: :[[@LINE-6]]:6: note: Example call graph loop, starting from function 'maybe_endless_recursion'
+// CHECK-NOTES: :[[@LINE-5]]:5: note: Frame #1: function 'maybe_endless_recursion' calls function 'maybe_endless_recursion' here:
+// CHECK-NOTES: :[[@LINE-6]]:5: note: ... which was the starting point of this call graph
+// CHECK-NOTES: :[[@LINE-7]]:5: note: This report is non-exhaustive. There may be other cycles.
+
+// Obviously-constrained recursion.
+void recursive_countdown(unsigned x) {
+  if (x == 0)
+return;
+  recursive_countdown(x - 1);
+}
+
+// CHECK-NOTES: :[[@LINE-6]]:6: warning: function 'recursive_countdown' is part of call graph loop [misc-no-recursion]
+// CHECK-NOTES: :[[@LINE-7]]:6: note: Example call graph loop, starting from function 'recursive_countdown'
+// CHECK-NOTES: :[[@LINE-5]]:3: note: Frame #1: function 'recursive_countdown' calls function 'recursive_countdown' here:
+// CHECK-NOTES: :[[@LINE-6]]:3: note: ... which was the starting point of this call graph
+// CHECK-NOTES: :[[@LINE-7]]:3: note: This report is non-exhaustive. There may be other cycles.
+
+void indirect_recursion();
+void conditionally_executed() {
+  if (external_oracle())
+indirect_recursion();
+}
+void indirect_recursion() {
+  if (external_oracle())
+conditionally_executed();
+}
+
+// CHECK-NOTES: :[[@LINE-10]]:6: warning: function 'indirect_recursion' is part of call graph loop [misc-no-recursion]
+// CHECK-NOTES: :[[@LINE-10]]:6: warning: function 'conditionally_executed' is part of call graph loop [misc-no-recursion]
+// CHECK-NOTES: :[[@LINE-12]]:6: note: Example call graph loop, starting from function 'indirect_recursion'
+// CHECK-NOTES: :[[@LINE-6]]:5: note: Frame #1: function 'indirect_recursion' calls function 'conditionally_executed' here:
+// CHECK-NOTES: :[[@LINE-11]]:5: note: Frame #2: function 'conditionally_executed' calls function 'indirect_recursion' here:
+// CHECK-NOTES: :[[@LINE-12]]:5: note: ... which was the starting point of this call graph
+// CHECK-NOTES: :[[@LINE-13]]:5: note: This report is non-exhaustive. There may be other cycles.
+
+void taint();
+void maybe_selfrecursion_with_two_backedges() {
+  if (external_oracle())
+maybe_selfrecursion_with_two_backedges();
+  taint();
+  if (another_external_oracle())
+maybe_selfrecursion_with_two_backedges();
+}
+
+// CHECK-NOTES: :[[@LINE-8]]:6: warning: function 'maybe_selfrecursion_with_two_backedges' is part of call graph loop [misc-no-recursion]
+// 

[PATCH] D72362: [clang-tidy] misc-no-recursion: a new check

[Artem Dergachev via Phabricator via cfe-commits]

NoQ added a comment.

`CallGraph` changes look nice, i don't see any immediate problems and it's a 
nice-to-have thing that other users may benefit from (the static analyzer 
wouldn't though, it's only interested in topological sorting order on the 
graph). I guess you could have as well stored a `CallExpr` with the 
`CallRecord`.

Note that there are certain problems with the call graph itself that are caused 
by how our very AST is structured. Hopefully they won't cause you too much 
trouble. I outlined some of them in the inline comments.




Comment at: clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp:21
+
+inline bool operator==(const CallGraphNode::CallRecord ,
+   const CallGraphNode::CallRecord ) {

lebedev.ri wrote:
> JonasToth wrote:
> > That should be in the `CallGraph` code, adding a private operator overload 
> > does not feel right.
> I didn't want to put this into callgraph, because this
> cements the fact that we do not care about sourceloc,
> which may not be true for other users.
> I can put it there, but if told so by it's code owners (@NoQ ?)
Does this need to be `operator==`? It looks like `DenseMap` uses 
`DenseMapInfo::isEqual` instead, maybe just call it "isEqual" to avoid 
confusion?



Comment at: clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp:31
+
+// Specialize DenseMapInfo for clang::CallGraphNode::CallRecord.
+template <> struct DenseMapInfo {

lebedev.ri wrote:
> JonasToth wrote:
> > That stuff, too.
> (same reasoning)
So what exactly happens if you link together two different translation units 
with different specializations of `DenseMapInfo` and start passing 
such dense maps from one TU to the other?

(ODR violations are definitely not my specialty)



Comment at: clang/lib/Analysis/CallGraph.cpp:96-101
   void VisitCXXConstructExpr(CXXConstructExpr *E) {
 CXXConstructorDecl *Ctor = E->getConstructor();
 if (FunctionDecl *Def = Ctor->getDefinition())
-  addCalledDecl(Def);
+  addCalledDecl(Def, Ctor->getBeginLoc());
 VisitChildren(E);
   }

Note that you're missing out on destructors. They aren't in the call graph 
because they aren't in the AST to begin with. Like, declarations are there of 
course, but expressions are mostly missing. A destructor may call another 
function that will in turn destroy an object of the same type (maybe even the 
same object), causing recursion.

(side note: we're missing out on destructors too)



Comment at: clang/lib/Analysis/CallGraph.cpp:103-106
   // Include the evaluation of the default argument.
   void VisitCXXDefaultArgExpr(CXXDefaultArgExpr *E) {
 Visit(E->getExpr());
   }

Note that if a function `void foo(int x = boo()) { ... }` is invoked as `void 
bar() { foo(); foo(); }`, you'd get two different-in-every-way call records 
from the same function `bar()` to the same function `boo()` with the same 
source location (the location of call-expression `boo()` within the 
`ParmVarDecl` for `x`). I'm legit curious if this is a problem for your checker.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D72362/new/

https://reviews.llvm.org/D72362



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D72362: [clang-tidy] misc-no-recursion: a new check

[Alexey Bader via Phabricator via cfe-commits]

bader added a comment.

@lebedev.ri, thanks for the suggestion. We will investigate this option when we 
ready to upload clang diagnostics patch.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D72362/new/

https://reviews.llvm.org/D72362



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D72362: [clang-tidy] misc-no-recursion: a new check

[Roman Lebedev via Phabricator via cfe-commits]

lebedev.ri added a comment.
Herald added a subscriber: Charusso.

In D72362#1819243 , @bader wrote:

> In D72362#1817682 , @lebedev.ri 
> wrote:
>
> > In D72362#1817599 , @bader wrote:
> >
> > > Does it make sense to implement such diagnostics in clang Sema, 
> > > considering that OpenCL does not allow recursion?
> > >  We implemented similar diagnostics for SYCL programming model and would 
> > > be like to upstream it to clang later 
> > > (https://github.com/intel/llvm/commit/4efe9fcf2dc6f6150b5b477b0f8320ea13a7f596).
> > >  Can we somehow leverage this work for the compiler?
> >
> >
> > Implementing it elsewhere will be more restrictive in the future - somehow 
> > i suspect
> >  it will be easier to make clang-tidy CTU-aware rather than clang sema.
> >
> > That being said, is SYCL inherently single-TU, does it not support
> >  linking multiple separately compiled object files together?
>
>
> SYCL doesn't require multi-TU support. AFAIK, ComputeCPP implementation is 
> signle-TU. +@Naghasan to confirm/clarify.
>  The open source implementation I referred to, does support linking 
> separately compiled object files, but still I think detecting single-TU 
> recursion in clang is very useful.
>  Is it possible to have both: intra-TU diagnostics in clang and inter-TU 
> diagnostics in clang-tidy tool? Share any infrastructure (e.g. recursion 
> detection)?


Feel free to post that as an RFC to cfe-dev. If the feedback is favorable, i 
suspect i can rework this code somehow.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D72362/new/

https://reviews.llvm.org/D72362



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D72362: [clang-tidy] misc-no-recursion: a new check

[Alexey Bader via Phabricator via cfe-commits]

bader added a subscriber: Naghasan.
bader added a comment.

In D72362#1817682 , @lebedev.ri wrote:

> In D72362#1817599 , @bader wrote:
>
> > Does it make sense to implement such diagnostics in clang Sema, considering 
> > that OpenCL does not allow recursion?
> >  We implemented similar diagnostics for SYCL programming model and would be 
> > like to upstream it to clang later 
> > (https://github.com/intel/llvm/commit/4efe9fcf2dc6f6150b5b477b0f8320ea13a7f596).
> >  Can we somehow leverage this work for the compiler?
>
>
> Implementing it elsewhere will be more restrictive in the future - somehow i 
> suspect
>  it will be easier to make clang-tidy CTU-aware rather than clang sema.
>
> That being said, is SYCL inherently single-TU, does it not support
>  linking multiple separately compiled object files together?


SYCL doesn't require multi-TU support. AFAIK, ComputeCPP implementation is 
signle-TU. +@Naghasan to confirm/clarify.
The open source implementation I referred to, does support linking separately 
compiled object files, but still I think detecting single-TU recursion in clang 
is very useful.
Is it possible to have both: intra-TU diagnostics in clang and inter-TU 
diagnostics in clang-tidy tool? Share any infrastructure (e.g. recursion 
detection)?


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D72362/new/

https://reviews.llvm.org/D72362



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D72362: [clang-tidy] misc-no-recursion: a new check

[Roman Lebedev via Phabricator via cfe-commits]

lebedev.ri marked 3 inline comments as done.
lebedev.ri added a comment.

In D72362#1817599 , @bader wrote:

> Does it make sense to implement such diagnostics in clang Sema, considering 
> that OpenCL does not allow recursion?
>  We implemented similar diagnostics for SYCL programming model and would be 
> like to upstream it to clang later 
> (https://github.com/intel/llvm/commit/4efe9fcf2dc6f6150b5b477b0f8320ea13a7f596).
>  Can we somehow leverage this work for the compiler?


Implementing it elsewhere will be more restrictive in the future - somehow i 
suspect
it will be easier to make clang-tidy CTU-aware rather than clang sema.

That being said, is SYCL inherently single-TU, does it not support
linking multiple separately compiled object files together?


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D72362/new/

https://reviews.llvm.org/D72362



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D72362: [clang-tidy] misc-no-recursion: a new check

[Alexey Bader via Phabricator via cfe-commits]

bader added a comment.

Does it make sense to implement such diagnostics in clang Sema, considering 
that OpenCL does not allow recursion?
We implemented similar diagnostics for SYCL programming model and would be like 
to upstream it to clang later 
(https://github.com/intel/llvm/commit/4efe9fcf2dc6f6150b5b477b0f8320ea13a7f596).
 Can we somehow leverage this work for the compiler?


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D72362/new/

https://reviews.llvm.org/D72362



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D72362: [clang-tidy] misc-no-recursion: a new check

[Roman Lebedev via Phabricator via cfe-commits]

lebedev.ri marked 8 inline comments as done.
lebedev.ri added a comment.

Thanks for taking a look.
Some deflective replies inline.




Comment at: clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp:21
+
+inline bool operator==(const CallGraphNode::CallRecord ,
+   const CallGraphNode::CallRecord ) {

JonasToth wrote:
> That should be in the `CallGraph` code, adding a private operator overload 
> does not feel right.
I didn't want to put this into callgraph, because this
cements the fact that we do not care about sourceloc,
which may not be true for other users.
I can put it there, but if told so by it's code owners (@NoQ ?)



Comment at: clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp:31
+
+// Specialize DenseMapInfo for clang::CallGraphNode::CallRecord.
+template <> struct DenseMapInfo {

JonasToth wrote:
> That stuff, too.
(same reasoning)



Comment at: clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp:67
+// 2. it is immutable, the way it was constructed it will stay.
+template  class ImmutableSmartSet {
+  ArrayRef Vector;

JonasToth wrote:
> Why `smart`?
Because if it's just named `ImmutableSet`, why should it not just be a `using 
ImmutableSet = DenseSet; const ImmutableSet ..`?
This denotes it's different behaviour when in small-size mode and in 
non-small-size mode.



Comment at: clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp:73
+
+  bool isSmall() const { return Set.empty(); }
+

JonasToth wrote:
> That method name looks confusing. `isEmpty()`? If not, why?
See how it's used, e.g. in `count()`, see `SmallSet` also.



Comment at: clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp:242
+Decl *D = N->getDecl();
+diag(D->getLocation(), "function '%0' is part of call graph loop")
+<< cast(D)->getName();

JonasToth wrote:
> That should be a `Note:`
I'm intentionally emitting it as a warning.

If i `// NOLINT` the main warning, does that not silence the related `Notes`?
I don't want `NOLINT`ing the "main" function to silence the report for the rest 
of the functions in SCC.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D72362/new/

https://reviews.llvm.org/D72362



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D72362: [clang-tidy] misc-no-recursion: a new check

[Jonas Toth via Phabricator via cfe-commits]

JonasToth added a comment.

So that is were the CTU question comes from? :)




Comment at: clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp:21
+
+inline bool operator==(const CallGraphNode::CallRecord ,
+   const CallGraphNode::CallRecord ) {

That should be in the `CallGraph` code, adding a private operator overload does 
not feel right.



Comment at: clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp:31
+
+// Specialize DenseMapInfo for clang::CallGraphNode::CallRecord.
+template <> struct DenseMapInfo {

That stuff, too.



Comment at: clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp:67
+// 2. it is immutable, the way it was constructed it will stay.
+template  class ImmutableSmartSet {
+  ArrayRef Vector;

Why `smart`?



Comment at: clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp:73
+
+  bool isSmall() const { return Set.empty(); }
+

That method name looks confusing. `isEmpty()`? If not, why?



Comment at: clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp:242
+Decl *D = N->getDecl();
+diag(D->getLocation(), "function '%0' is part of call graph loop")
+<< cast(D)->getName();

That should be a `Note:`



Comment at: clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp:287
+  diag(CyclicCallStack.back().Loc,
+   "... which was the starting point of this call graph",
+   DiagnosticIDs::Note);

Please merge these two notes into one.



Comment at: clang-tools-extra/clang-tidy/misc/NoRecursionCheck.h:28
+class NoRecursionCheck : public ClangTidyCheck {
+  void handleSCC(ArrayRef SCC);
+

nit: the `private` stuff is usually at the bottom in the other clang-tidy code. 
not sure if there is something in the coding standard though.



Comment at: clang-tools-extra/docs/ReleaseNotes.rst:149
+
+  Finds strongly connected functions (by analyzing call graph for SCC's
+  that are loops), diagnoses each function in the cycle,

The technical details should not be in the release notes. Just that it finds 
recursion and diagnoses it.



Comment at: clang-tools-extra/test/clang-tidy/checkers/misc-no-recursion.cpp:127
+}
+
+// CHECK-NOTES: :[[@LINE-14]]:13: warning: function 
'indirect_recursion_with_depth2' is part of call graph loop [misc-no-recursion]

Does the check find recursion through function pointers? (Probably not? Should 
be noted as limitation).

Please add cases from lambdas. And cases where recursion happens in templates / 
only with one of multiple instantiations.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D72362/new/

https://reviews.llvm.org/D72362



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D72362: [clang-tidy] misc-no-recursion: a new check

[Roman Lebedev via Phabricator via cfe-commits]

lebedev.ri updated this revision to Diff 236843.
lebedev.ri marked an inline comment as done.
lebedev.ri added a comment.

s/1/true/


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D72362/new/

https://reviews.llvm.org/D72362

Files:
  clang-tools-extra/clang-move/HelperDeclRefGraph.cpp
  clang-tools-extra/clang-tidy/misc/CMakeLists.txt
  clang-tools-extra/clang-tidy/misc/MiscTidyModule.cpp
  clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp
  clang-tools-extra/clang-tidy/misc/NoRecursionCheck.h
  clang-tools-extra/docs/ReleaseNotes.rst
  clang-tools-extra/docs/clang-tidy/checks/list.rst
  clang-tools-extra/docs/clang-tidy/checks/misc-no-recursion.rst
  clang-tools-extra/test/clang-tidy/checkers/misc-no-recursion.cpp
  clang/include/clang/Analysis/CallGraph.h
  clang/lib/Analysis/CallGraph.cpp

Index: clang/lib/Analysis/CallGraph.cpp
===
--- clang/lib/Analysis/CallGraph.cpp
+++ clang/lib/Analysis/CallGraph.cpp
@@ -66,16 +66,16 @@
 return nullptr;
   }
 
-  void addCalledDecl(Decl *D) {
+  void addCalledDecl(Decl *D, SourceLocation Loc) {
 if (G->includeInGraph(D)) {
   CallGraphNode *CalleeNode = G->getOrInsertNode(D);
-  CallerNode->addCallee(CalleeNode);
+  CallerNode->addCallee({CalleeNode, Loc});
 }
   }
 
   void VisitCallExpr(CallExpr *CE) {
 if (Decl *D = getDeclFromCall(CE))
-  addCalledDecl(D);
+  addCalledDecl(D, CE->getBeginLoc());
 VisitChildren(CE);
   }
 
@@ -89,14 +89,14 @@
 
   void VisitCXXNewExpr(CXXNewExpr *E) {
 if (FunctionDecl *FD = E->getOperatorNew())
-  addCalledDecl(FD);
+  addCalledDecl(FD, E->getBeginLoc());
 VisitChildren(E);
   }
 
   void VisitCXXConstructExpr(CXXConstructExpr *E) {
 CXXConstructorDecl *Ctor = E->getConstructor();
 if (FunctionDecl *Def = Ctor->getDefinition())
-  addCalledDecl(Def);
+  addCalledDecl(Def, Ctor->getBeginLoc());
 VisitChildren(E);
   }
 
@@ -122,7 +122,7 @@
   else
 D = IDecl->lookupPrivateClassMethod(Sel);
   if (D) {
-addCalledDecl(D);
+addCalledDecl(D, ME->getBeginLoc());
 NumObjCCallEdges++;
   }
 }
@@ -207,7 +207,7 @@
   Node = std::make_unique(F);
   // Make Root node a parent of all functions to make sure all are reachable.
   if (F)
-Root->addCallee(Node.get());
+Root->addCallee({Node.get(), SourceLocation()});
   return Node.get();
 }
 
@@ -230,8 +230,8 @@
 OS << " calls: ";
 for (CallGraphNode::const_iterator CI = N->begin(),
CE = N->end(); CI != CE; ++CI) {
-  assert(*CI != Root && "No one can call the root node.");
-  (*CI)->print(OS);
+  assert(CI->Callee != Root && "No one can call the root node.");
+  CI->Callee->print(OS);
   OS << " ";
 }
 OS << '\n';
Index: clang/include/clang/Analysis/CallGraph.h
===
--- clang/include/clang/Analysis/CallGraph.h
+++ clang/include/clang/Analysis/CallGraph.h
@@ -24,6 +24,7 @@
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallVector.h"
+#include "llvm/ADT/iterator_range.h"
 #include 
 
 namespace clang {
@@ -136,14 +137,23 @@
 private:
   /// Add the given declaration to the call graph.
   void addNodeForDecl(Decl *D, bool IsGlobal);
-
-  /// Allocate a new node in the graph.
-  CallGraphNode *allocateNewNode(Decl *);
 };
 
 class CallGraphNode {
 public:
-  using CallRecord = CallGraphNode *;
+  struct CallRecord {
+CallGraphNode *Callee;
+SourceLocation Loc;
+
+CallRecord() = default;
+
+CallRecord(CallGraphNode *Callee_, SourceLocation Loc_)
+: Callee(Callee_), Loc(Loc_) {}
+
+// The call destination is the only important data here,
+// allow to transparently unwrap into it.
+operator CallGraphNode *() const { return Callee; }
+  };
 
 private:
   /// The function/method declaration.
@@ -164,12 +174,18 @@
   const_iterator begin() const { return CalledFunctions.begin(); }
   const_iterator end() const { return CalledFunctions.end(); }
 
+  /// Iterator access to callees/children of the node.
+  llvm::iterator_range callees() {
+return llvm::make_range(begin(), end());
+  }
+  llvm::iterator_range callees() const {
+return llvm::make_range(begin(), end());
+  }
+
   bool empty() const { return CalledFunctions.empty(); }
   unsigned size() const { return CalledFunctions.size(); }
 
-  void addCallee(CallGraphNode *N) {
-CalledFunctions.push_back(N);
-  }
+  void addCallee(CallRecord Call) { CalledFunctions.push_back(Call); }
 
   Decl *getDecl() const { return FD; }
 
Index: clang-tools-extra/test/clang-tidy/checkers/misc-no-recursion.cpp
===
--- /dev/null
+++ clang-tools-extra/test/clang-tidy/checkers/misc-no-recursion.cpp
@@ -0,0 +1,136 @@
+// RUN: 

[PATCH] D72362: [clang-tidy] misc-no-recursion: a new check

[Roman Lebedev via Phabricator via cfe-commits]

lebedev.ri added a comment.

In D72362#1808825 , @Eugene.Zelenko 
wrote:

> It'll be reasonable to add CERT alias.


I'm not sure about that.
This diagnoses **any** potential recursion,
while CERT is much more specific than that.
(`Avoid cycles during initialization of static objects`)


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D72362/new/

https://reviews.llvm.org/D72362



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D72362: [clang-tidy] misc-no-recursion: a new check

[Eugene Zelenko via Phabricator via cfe-commits]

Eugene.Zelenko added a comment.

It'll be reasonable to add CERT alias.




Comment at: clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp:213
+  CallGraphNode::CallRecord *Node = 
+  while (1) {
+// Did we see this node before?

true



Comment at: clang-tools-extra/docs/clang-tidy/checks/misc-no-recursion.rst:8
+that are loops), diagnoses each function in the cycle,
+and displays one example of possible call graph loop (recursion).

It'll be reasonable to add links to relevant coding guidelines.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D72362/new/

https://reviews.llvm.org/D72362



___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D72362: [clang-tidy] misc-no-recursion: a new check

[Roman Lebedev via Phabricator via cfe-commits]

lebedev.ri created this revision.
lebedev.ri added reviewers: JonasToth, aaron.ballman, ffrankies, 
Eugene.Zelenko, erichkeane, NoQ.
lebedev.ri added a project: LLVM.
Herald added subscribers: xazax.hun, Anastasia, mgorny.
Herald added a project: clang.

Recursion is a powerful tool, but like any tool
without care it can be dangerous. For example,
if the recursion is unbounded, you will
eventually run out of stack and crash.

You can of course track the recursion depth
but if it is hardcoded, there can always be some
other environment when that depth is too large,
so said magic number would need to be env-dependent.
But then your program's behavior is suddenly more env-dependent.

Also, recursion, while it does not outright stop optimization,
recursive calls are less great than normal calls,
for example they hinder inlining.

Recursion is banned in some coding guidelines:

- SEI CERT DCL56-CPP. Avoid cycles during initialization of static objects
- JPL 2.4 Do not use direct or indirect recursion.
- I'd say it is frowned upon in LLVM, although not banned

And is plain unsupported in some cases:

- OpenCL 1.2, 6.9 Restrictions: i. Recursion is not supported.

So there's clearly a lot of reasons why one might want to
avoid recursion, and replace it with worklist handling.
It would be great to have a enforcement for it though.

This implements such a check.
Here we detect both direct and indirect recursive calls.

The algorithm is pretty straight-forward:

1. Build call-graph for the entire TU. For that, the existing 
`clang::CallGraph` is re-used, although it had to be modified to also track the 
location of the call.
2. Then, the hard problem: how do we detect recursion? Since we have a graph, 
let's just do the sane thing, and look for Strongly Connected Function 
Declarations - widely known as `SCC`. For that LLVM provides 
`llvm::scc_iterator`, which is internally an Tarjan's DFS algorithm, and is 
used throught LLVM, so this should be as performant as possible.
3. Now that we've got SCC's, we discard those that don't contain loops. Note 
that there may be more than one loop in SCC!
4. For each loopy SCC, we call out each function, and print a single example 
call graph that shows recursion -- it didn't seem worthwhile enumerating every 
possible loop in SCC, although i suppose it could be implemented.
  - To come up with that call graph cycle example, we start at first SCC node, 
see which callee of the node is within SCC (and is thus known to be in cycle), 
and recurse into it until we hit the callee that is already in call stack.


Repository:
  rG LLVM Github Monorepo

https://reviews.llvm.org/D72362

Files:
  clang-tools-extra/clang-move/HelperDeclRefGraph.cpp
  clang-tools-extra/clang-tidy/misc/CMakeLists.txt
  clang-tools-extra/clang-tidy/misc/MiscTidyModule.cpp
  clang-tools-extra/clang-tidy/misc/NoRecursionCheck.cpp
  clang-tools-extra/clang-tidy/misc/NoRecursionCheck.h
  clang-tools-extra/docs/ReleaseNotes.rst
  clang-tools-extra/docs/clang-tidy/checks/list.rst
  clang-tools-extra/docs/clang-tidy/checks/misc-no-recursion.rst
  clang-tools-extra/test/clang-tidy/checkers/misc-no-recursion.cpp
  clang/include/clang/Analysis/CallGraph.h
  clang/lib/Analysis/CallGraph.cpp

Index: clang/lib/Analysis/CallGraph.cpp
===
--- clang/lib/Analysis/CallGraph.cpp
+++ clang/lib/Analysis/CallGraph.cpp
@@ -66,16 +66,16 @@
 return nullptr;
   }
 
-  void addCalledDecl(Decl *D) {
+  void addCalledDecl(Decl *D, SourceLocation Loc) {
 if (G->includeInGraph(D)) {
   CallGraphNode *CalleeNode = G->getOrInsertNode(D);
-  CallerNode->addCallee(CalleeNode);
+  CallerNode->addCallee({CalleeNode, Loc});
 }
   }
 
   void VisitCallExpr(CallExpr *CE) {
 if (Decl *D = getDeclFromCall(CE))
-  addCalledDecl(D);
+  addCalledDecl(D, CE->getBeginLoc());
 VisitChildren(CE);
   }
 
@@ -89,14 +89,14 @@
 
   void VisitCXXNewExpr(CXXNewExpr *E) {
 if (FunctionDecl *FD = E->getOperatorNew())
-  addCalledDecl(FD);
+  addCalledDecl(FD, E->getBeginLoc());
 VisitChildren(E);
   }
 
   void VisitCXXConstructExpr(CXXConstructExpr *E) {
 CXXConstructorDecl *Ctor = E->getConstructor();
 if (FunctionDecl *Def = Ctor->getDefinition())
-  addCalledDecl(Def);
+  addCalledDecl(Def, Ctor->getBeginLoc());
 VisitChildren(E);
   }
 
@@ -122,7 +122,7 @@
   else
 D = IDecl->lookupPrivateClassMethod(Sel);
   if (D) {
-addCalledDecl(D);
+addCalledDecl(D, ME->getBeginLoc());
 NumObjCCallEdges++;
   }
 }
@@ -207,7 +207,7 @@
   Node = std::make_unique(F);
   // Make Root node a parent of all functions to make sure all are reachable.
   if (F)
-Root->addCallee(Node.get());
+Root->addCallee({Node.get(), SourceLocation()});
   return Node.get();
 }
 
@@ -230,8 +230,8 @@
 OS << " calls: ";
 for (CallGraphNode::const_iterator CI = N->begin(),