summaryrefslogtreecommitdiff
path: root/other/analysis/check_recursion
blob: 210635276c081c50d4d5f9dd382b74dd48f37819 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
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",
})