summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--.travis.yml1
-rwxr-xr-x.travis/bazel-linux7
-rwxr-xr-x.travis/cmake-linux7
-rwxr-xr-xother/analysis/check_recursion104
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:
24 - libgtest-dev # For unit tests. 24 - libgtest-dev # For unit tests.
25 - libvpx-dev # For toxav. 25 - libvpx-dev # For toxav.
26 - portaudio19-dev # For av_test. 26 - portaudio19-dev # For av_test.
27 - pylint
27 install: .travis/$JOB install 28 install: .travis/$JOB install
28 script: .travis/$JOB script 29 script: .travis/$JOB script
29 after_script: .travis/upload-coverage 30 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() {
16} 16}
17 17
18travis_script() { 18travis_script() {
19 bazel test //c-toxcore:license_test 19 bazel test \
20 bazel test //c-toxcore:readme_test 20 //c-toxcore:license_test \
21 bazel test //c-toxcore:yamllint_test 21 //c-toxcore:readme_test \
22 //c-toxcore:yamllint_test
22 23
23 # TODO(iphydf): Make tests have a chance to succeed. 24 # TODO(iphydf): Make tests have a chance to succeed.
24 # Run the tests, but if they fail, at least we should be able to build. 25 # 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() {
53} 53}
54 54
55run_static_analysis() { 55run_static_analysis() {
56 pylint -E other/analysis/check_recursion
57
56 export CPPFLAGS="-isystem $CACHEDIR/include" 58 export CPPFLAGS="-isystem $CACHEDIR/include"
57 export LDFLAGS="-L $CACHEDIR/lib" 59 export LDFLAGS="-L $CACHEDIR/lib"
60 cat toxav/*.c toxcore/*.c toxencryptsave/*.c \
61 | clang `pkg-config --cflags libsodium opus vpx` \
62 -Itoxav -Itoxcore -Itoxencryptsave -S -emit-llvm -xc - -o- \
63 | opt -analyze -print-callgraph 2>&1 \
64 | other/analysis/check_recursion
58 other/analysis/run-clang 65 other/analysis/run-clang
59 other/analysis/run-clang-analyze 66 other/analysis/run-clang-analyze
60} 67}
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 @@
1#!/usr/bin/env python
2"""
3Tool to check for recursive calls in toxcore C code.
4
5Usage:
6
7cat toxav/*.c toxcore/*.c toxencryptsave/*.c \
8 | clang `pkg-config --cflags libsodium opus vpx` \
9 -Itoxav -Itoxcore -Itoxencryptsave -S -emit-llvm -xc - -o- \
10 | opt -analyze -print-callgraph 2>&1 \
11 | other/analysis/check_recursion
12"""
13
14from __future__ import print_function
15
16import collections
17import fileinput
18import re
19import sys
20import time
21
22def load_callgraph():
23 """
24 Parses the output from opt -print-callgraph from stdin or argv.
25
26 Returns graph as dict[str, list[str]] containing nodes with their outgoing
27 edges.
28 """
29 graph = collections.defaultdict(set)
30 cur = None
31 for line in fileinput.input():
32 found = re.search("Call graph node for function: '(.*)'", line)
33 if found:
34 cur = found.group(1)
35 if cur:
36 found = re.search("calls function '(.*)'", line)
37 if found:
38 graph[cur].add(found.group(1))
39
40 return {k: sorted(v) for k, v in graph.items()}
41
42def walk(visited, callgraph, cycles, stack, cur):
43 """
44 Detects cycles in the callgraph and adds them to the cycles parameter.
45 """
46 if cur in visited:
47 return
48 stack.append(cur)
49 for callee in callgraph.get(cur, ()):
50 try:
51 cycles.add(" -> ".join(stack[stack.index(callee):] + [callee]))
52 except ValueError:
53 walk(visited, callgraph, cycles, stack, callee)
54 visited.add(callee)
55 stack.pop()
56
57def get_time():
58 """
59 Return the current time in milliseconds.
60 """
61 return int(round(time.time() * 1000))
62
63def find_recursion(expected):
64 """
65 Main function: detects cycles and prints them.
66
67 Takes a set of expected cycles. If any of the expected cycles was not found,
68 or any unexpected cycle was found, the program exits with an error.
69 """
70 start = prev = get_time()
71 print("[+0000=0000] Generating callgraph")
72 callgraph = load_callgraph()
73
74 now = get_time()
75 print("[+%04d=%04d] Finding recursion" % (now - prev, now - start))
76 prev = now
77
78 cycles = set()
79 visited = set()
80 for func in sorted(callgraph.keys()):
81 walk(visited, callgraph, cycles, [], func)
82
83 now = get_time()
84 if cycles:
85 print("[+%04d=%04d] Recursion detected:" % (now - prev, now - start))
86 for cycle in sorted(cycles):
87 if cycle in expected:
88 print(" - " + cycle + " (expected)")
89 expected.remove(cycle)
90 cycles.remove(cycle)
91 else:
92 print(" - " + cycle)
93 else:
94 print("[+%04d=%04d] No recursion detected" % (now - prev, now - start))
95
96 if expected:
97 print("Expected recursion no longer present: " + str(list(expected)))
98 if expected or cycles:
99 sys.exit(1)
100
101find_recursion(expected={
102 "add_to_closest -> add_to_closest",
103 "add_to_list -> add_to_list",
104})