wowlab_tidy/languages/rust/rules/complexity/
recursive_fn.rs

1use ra_ap_syntax::{
2    AstNode,
3    ast::{self, HasName},
4};
5
6use super::support;
7use crate::{AstCtx, Example, Violation};
8
9#[rustfmt::skip]
10const EXAMPLES: &[Example] = &[
11    Example {
12        label: "direct recursion (bare call)",
13        code: "fn factorial(n: u64) -> u64 { if n <= 1 { 1 } else { n * factorial(n - 1) } }",
14        pass: false,
15    },
16    Example {
17        label: "Self:: recursion",
18        code: "struct S;\nimpl S { fn go(&self) { Self::go(self); } }",
19        pass: false,
20    },
21    Example {
22        label: "no recursion",
23        code: "fn add(a: u64, b: u64) -> u64 { a + b }",
24        pass: true,
25    },
26    Example {
27        label: "recursion in test module",
28        code: "#[cfg(test)]\nmod tests {\n    fn factorial(n: u64) -> u64 { if n <= 1 { 1 } else { n * factorial(n - 1) } }\n}",
29        pass: true,
30    },
31    Example {
32        label: "calling different function",
33        code: "fn foo() { bar(); }\nfn bar() {}",
34        pass: true,
35    },
36    Example {
37        label: "constructor calling other type constructors",
38        code: "struct S { v: Vec<u8> }\nimpl S { fn new() -> Self { Self { v: Vec::new() } } }",
39        pass: true,
40    },
41    Example {
42        label: "Default impl calling other defaults",
43        code: "struct S { v: Vec<u8> }\nimpl Default for S { fn default() -> Self { Self { v: Vec::default() } } }",
44        pass: true,
45    },
46    Example {
47        label: "qualified trait delegation",
48        code: "struct S; trait T { fn go(); } impl T for S { fn go() { <u8 as T>::go(); } }",
49        pass: true,
50    },
51];
52
53crate::ast_rule!(
54    recursive_fn,
55    "Flag direct self-recursion (stack overflow risk, especially in WASM).",
56    "Direct recursion risks stack overflow, especially in WASM with its fixed 1MB stack. Use iteration or trampolining.",
57    High,
58);
59
60// #t(fn: rust_alloc_in_loop) diagnostics own function names and messages after a confirmed recursive call
61fn check_recursive_fn(ctx: &AstCtx<'_>) -> Vec<Violation> {
62    let mut violations = Vec::new();
63
64    for function in ctx
65        .nodes::<ast::Fn>()
66        .filter(|function| !ctx.is_in_test(function))
67    {
68        let Some(name) = function.name() else {
69            continue;
70        };
71        let function_name = name.text().to_string();
72        let impl_type = function
73            .syntax()
74            .ancestors()
75            .skip(1)
76            .find_map(ast::Impl::cast)
77            .and_then(|item_impl| item_impl.self_ty())
78            .and_then(|ty| support::self_type_name(&ty));
79
80        for call in function
81            .syntax()
82            .descendants()
83            .filter_map(ast::CallExpr::cast)
84        {
85            if enclosing_function(&call).as_ref() != Some(&function) {
86                continue;
87            }
88
89            let Some(path) = call.expr().and_then(|callee| match callee {
90                ast::Expr::PathExpr(path) => path.path(),
91                _ => None,
92            }) else {
93                continue;
94            };
95
96            if is_self_call(&path, &function_name, impl_type.as_deref()) {
97                let message = format!(
98                    "direct self-recursion in `{function_name}` — risk of stack overflow (especially in WASM)"
99                );
100
101                if let Some(location) = path.segment().and_then(|segment| segment.name_ref()) {
102                    violations.push(ctx.violation(&location, message));
103                } else {
104                    violations.push(ctx.violation(&call, message));
105                }
106            }
107        }
108    }
109
110    violations
111}
112
113fn enclosing_function<N>(node: &N) -> Option<ast::Fn>
114where
115    N: AstNode,
116{
117    node.syntax().ancestors().skip(1).find_map(ast::Fn::cast)
118}
119
120fn is_self_call(path: &ast::Path, fn_name: &str, impl_type: Option<&str>) -> bool {
121    if path
122        .syntax()
123        .descendants()
124        .any(|node| ast::TypeAnchor::cast(node).is_some())
125    {
126        return false;
127    }
128
129    let Some(called) = path.segment().and_then(|segment| segment.name_ref()) else {
130        return false;
131    };
132
133    if called.text() != fn_name {
134        return false;
135    }
136
137    let Some(qualifier) = path.qualifier() else {
138        return true;
139    };
140
141    if qualifier.qualifier().is_some() {
142        return false;
143    }
144
145    qualifier
146        .segment()
147        .and_then(|segment| segment.name_ref())
148        .is_some_and(|name| name.text() == "Self" || impl_type.is_some_and(|ty| name.text() == ty))
149}
150
151crate::tidy_ast_test!(check_recursive_fn, {
152    crate::example_tests!(EXAMPLES, check_recursive_fn);
153});
wowlab_tidy/languages/rust/rules/complexity/recursive_fn.rs

wowlab_tidy/languages/rust/rules/complexity/
recursive_fn.rs
