Add tool to find directly recursive calls in toxcore.

We should avoid recursion, as it makes reasoning about stack growth
harder. This tool shows (currently) 4 (non-tail) recursive functions, at
least 2 of which are easy to fix.

4 files changed, 116 insertions, 3 deletions

diff --git a/.travis.yml b/.travis.yml
index 119228aa..ae7e7fa2 100644
--- a/.travis.yml
+++ b/.travis.yml
@@ -24,6 +24,7 @@ matrix:
             - libgtest-dev           # For unit tests.
             - libvpx-dev             # For toxav.
             - portaudio19-dev        # For av_test.
+            - pylint
       install:       .travis/$JOB install
       script:        .travis/$JOB script
       after_script:  .travis/upload-coverage
diff --git a/.travis/bazel-linux b/.travis/bazel-linux
index b157437d..5594ff8c 100755
--- a/.travis/bazel-linux
+++ b/.travis/bazel-linux
@@ -16,9 +16,10 @@ travis_install() {
 }
 
 travis_script() {
-  bazel test //c-toxcore:license_test
-  bazel test //c-toxcore:readme_test
-  bazel test //c-toxcore:yamllint_test
+  bazel test \
+    //c-toxcore:license_test \
+    //c-toxcore:readme_test \
+    //c-toxcore:yamllint_test
 
   # TODO(iphydf): Make tests have a chance to succeed.
   # Run the tests, but if they fail, at least we should be able to build.
diff --git a/.travis/cmake-linux b/.travis/cmake-linux
index fe5de10a..541eb014 100755
--- a/.travis/cmake-linux
+++ b/.travis/cmake-linux
@@ -53,8 +53,15 @@ travis_install() {
 }
 
 run_static_analysis() {
+  pylint -E other/analysis/check_recursion
+
   export CPPFLAGS="-isystem $CACHEDIR/include"
   export LDFLAGS="-L $CACHEDIR/lib"
+  cat toxav/*.c toxcore/*.c toxencryptsave/*.c \
+    | clang `pkg-config --cflags libsodium opus vpx` \
+        -Itoxav -Itoxcore -Itoxencryptsave -S -emit-llvm -xc - -o- \
+    | opt -analyze -print-callgraph 2>&1 \
+    | other/analysis/check_recursion
   other/analysis/run-clang
   other/analysis/run-clang-analyze
 }
diff --git a/other/analysis/check_recursion b/other/analysis/check_recursion
new file mode 100755
index 00000000..21063527
--- /dev/null
+++ b/other/analysis/check_recursion
@@ -0,0 +1,104 @@
+#!/usr/bin/env python
+"""
+Tool to check for recursive calls in toxcore C code.
+
+Usage: 
+
+cat toxav/*.c toxcore/*.c toxencryptsave/*.c \
+  | clang `pkg-config --cflags libsodium opus vpx` \
+      -Itoxav -Itoxcore -Itoxencryptsave -S -emit-llvm -xc - -o- \
+  | opt -analyze -print-callgraph 2>&1 \
+  | other/analysis/check_recursion
+"""
+
+from __future__ import print_function
+
+import collections
+import fileinput
+import re
+import sys
+import time
+
+def load_callgraph():
+    """
+    Parses the output from opt -print-callgraph from stdin or argv.
+
+    Returns graph as dict[str, list[str]] containing nodes with their outgoing
+    edges.
+    """
+    graph = collections.defaultdict(set)
+    cur = None
+    for line in fileinput.input():
+        found = re.search("Call graph node for function: '(.*)'", line)
+        if found:
+            cur = found.group(1)
+        if cur:
+            found = re.search("calls function '(.*)'", line)
+            if found:
+                graph[cur].add(found.group(1))
+
+    return {k: sorted(v) for k, v in graph.items()}
+
+def walk(visited, callgraph, cycles, stack, cur):
+    """
+    Detects cycles in the callgraph and adds them to the cycles parameter.
+    """
+    if cur in visited:
+        return
+    stack.append(cur)
+    for callee in callgraph.get(cur, ()):
+        try:
+            cycles.add(" -> ".join(stack[stack.index(callee):] + [callee]))
+        except ValueError:
+            walk(visited, callgraph, cycles, stack, callee)
+            visited.add(callee)
+    stack.pop()
+
+def get_time():
+    """
+    Return the current time in milliseconds.
+    """
+    return int(round(time.time() * 1000))
+
+def find_recursion(expected):
+    """
+    Main function: detects cycles and prints them.
+
+    Takes a set of expected cycles. If any of the expected cycles was not found,
+    or any unexpected cycle was found, the program exits with an error.
+    """
+    start = prev = get_time()
+    print("[+0000=0000] Generating callgraph")
+    callgraph = load_callgraph()
+
+    now = get_time()
+    print("[+%04d=%04d] Finding recursion" % (now - prev, now - start))
+    prev = now
+
+    cycles = set()
+    visited = set()
+    for func in sorted(callgraph.keys()):
+        walk(visited, callgraph, cycles, [], func)
+
+    now = get_time()
+    if cycles:
+        print("[+%04d=%04d] Recursion detected:" % (now - prev, now - start))
+        for cycle in sorted(cycles):
+            if cycle in expected:
+                print(" - " + cycle + " (expected)")
+                expected.remove(cycle)
+                cycles.remove(cycle)
+            else:
+                print(" - " + cycle)
+    else:
+        print("[+%04d=%04d] No recursion detected" % (now - prev, now - start))
+
+    if expected:
+        print("Expected recursion no longer present: " + str(list(expected)))
+    if expected or cycles:
+        sys.exit(1)
+
+find_recursion(expected={
+    "add_to_closest -> add_to_closest",
+    "add_to_list -> add_to_list",
+})