wowlab_tidy/languages/rust/rules/performance/
missing_capacity.rs

1use ra_ap_syntax::{AstNode, ast, ast::HasName};
2
3use super::{super::support::type_name, support};
4use crate::{AstCtx, Example, Violation};
5
6#[rustfmt::skip]
7const EXAMPLES: &[Example] = &[
8    Example {
9        label: "Vec::new filled from xs.iter()",
10        code: "fn f(xs: &[u32]) { let mut out = Vec::new(); for x in xs.iter() { out.push(*x); } }",
11        pass: false,
12    },
13    Example {
14        label: "HashMap::new filled from &v",
15        code: "fn f(v: Vec<u32>) { let mut m = std::collections::HashMap::new(); for x in &v { m.insert(*x, 1); } }",
16        pass: false,
17    },
18    Example {
19        label: "String::new filled over a range",
20        code: "fn f(n: usize) { let mut s = String::new(); for _ in 0..n { s.push_str(\"x\"); } }",
21        pass: false,
22    },
23    Example {
24        label: "annotated Default::default() filled in sized loop",
25        code: "fn f(xs: &[u32]) { let mut out: Vec<u32> = Default::default(); for x in xs.iter() { out.push(*x); } }",
26        pass: false,
27    },
28    Example {
29        label: "push nested deeper in loop body",
30        code: "fn f(xs: &[u32]) { let mut out = Vec::new(); for x in xs.iter() { if *x > 0 { out.push(*x); } } }",
31        pass: false,
32    },
33    Example {
34        label: "with_capacity already used",
35        code: "fn f(xs: &[u32]) { let mut out = Vec::with_capacity(xs.len()); for x in xs.iter() { out.push(*x); } }",
36        pass: true,
37    },
38    Example {
39        label: "consecutive pushes belong to rust_vec_init_then_push, not this rule",
40        code: "fn f() { let mut v = Vec::new(); v.push(1); v.push(2); }",
41        pass: true,
42    },
43    Example {
44        label: "adapter chain has no knowable length",
45        code: "fn f(xs: &[u32]) { let mut out = Vec::new(); for x in xs.iter().filter(|x| **x > 0) { out.push(**x); } }",
46        pass: true,
47    },
48    Example {
49        label: "collect already sizes via size_hint",
50        code: "fn f(xs: &[u32]) -> Vec<u32> { xs.iter().map(|x| x + 1).collect() }",
51        pass: true,
52    },
53    Example {
54        label: "sized fill loop in test module",
55        code: "#[cfg(test)]\nmod tests {\n    fn t(xs: &[u32]) { let mut out = Vec::new(); for x in xs.iter() { out.push(*x); } }\n}",
56        pass: true,
57    },
58];
59
60crate::ast_rule!(
61    missing_capacity,
62    "Flag collections built with `new()`/`default()` then grown inside a loop over a sized source.",
63    "When the final size is knowable at construction, with_capacity or collect avoids repeated reallocation and copying.",
64);
65
66fn check_missing_capacity(ctx: &AstCtx<'_>) -> Vec<Violation> {
67    let mut violations = Vec::new();
68
69    for block in ctx.nodes::<ast::StmtList>() {
70        if ctx.is_in_test(&block) {
71            continue;
72        }
73
74        let entries: Vec<ra_ap_syntax::SyntaxNode> = block.syntax().children().collect();
75
76        for (index, entry) in entries.iter().enumerate() {
77            // #t(rust_clone_in_loop) SyntaxNode clone is reference-counted and O(1)
78            let Some(local) = ast::LetStmt::cast(entry.clone()) else {
79                continue;
80            };
81            let Some(name) = collection_binding(&local) else {
82                continue;
83            };
84
85            if grown_in_sized_loop(entries.iter().skip(index + 1), &name) {
86                violations.push(ctx.violation(&local, MSG));
87            }
88        }
89    }
90
91    violations
92}
93
94const SIZED_COLLECTIONS: &[&str] = &["HashMap", "HashSet", "String", "Vec"];
95const GROW_METHODS: &[&str] = &["insert", "push", "push_str"];
96
97const MSG: &str = "collection built without capacity then grown in a loop over a sized source — use with_capacity(...) or collect()";
98
99fn collection_binding(local: &ast::LetStmt) -> Option<String> {
100    let ast::Pat::IdentPat(pattern) = local.pat()? else {
101        return None;
102    };
103
104    pattern.mut_token()?;
105    let name = pattern.name()?.text().to_string();
106    let initializer = local.initializer()?;
107
108    is_empty_ctor(&initializer, local.ty().as_ref()).then_some(name)
109}
110
111fn is_empty_ctor(expr: &ast::Expr, annotated: Option<&ast::Type>) -> bool {
112    let ast::Expr::CallExpr(call) = expr else {
113        return false;
114    };
115
116    if !support::has_no_args(call) {
117        return false;
118    }
119
120    let Some(ast::Expr::PathExpr(function)) = call.expr() else {
121        return false;
122    };
123    let Some(path) = function.path() else {
124        return false;
125    };
126    let names = support::path_names(&path);
127    let Some(last) = names.last() else {
128        return false;
129    };
130
131    if last == "new" {
132        return names
133            .iter()
134            .rev()
135            .nth(1)
136            .is_some_and(|ty| SIZED_COLLECTIONS.contains(&ty.as_str()));
137    }
138
139    if last == "default" {
140        return annotated
141            .and_then(type_name)
142            .is_some_and(|name| SIZED_COLLECTIONS.contains(&name.as_str()));
143    }
144
145    false
146}
147
148fn sized_source(expr: &ast::Expr) -> bool {
149    match expr {
150        ast::Expr::RefExpr(_) | ast::Expr::RangeExpr(_) => true,
151        ast::Expr::MethodCallExpr(call) => support::method_name(call).as_deref() == Some("iter"),
152        _ => false,
153    }
154}
155
156fn grown_in_sized_loop<'a>(
157    rest: impl Iterator<Item = &'a ra_ap_syntax::SyntaxNode>,
158    name: &str,
159) -> bool {
160    for entry in rest {
161        // #t(rust_clone_in_loop) SyntaxNode clone is reference-counted and O(1)
162        let loop_expr = ast::ForExpr::cast(entry.clone()).or_else(|| {
163            // #t(rust_clone_in_loop) SyntaxNode clone is reference-counted and O(1)
164            ast::ExprStmt::cast(entry.clone()).and_then(|statement| match statement.expr()? {
165                ast::Expr::ForExpr(loop_expr) => Some(loop_expr),
166                _ => None,
167            })
168        });
169        let Some(loop_expr) = loop_expr else {
170            continue;
171        };
172
173        if !support::loop_source(&loop_expr).is_some_and(|source| sized_source(&source)) {
174            continue;
175        }
176
177        let Some(body) = support::loop_body(&loop_expr) else {
178            continue;
179        };
180
181        if body
182            .syntax()
183            .descendants()
184            .filter_map(ast::MethodCallExpr::cast)
185            .any(|call| grows_collection(&call, name))
186        {
187            return true;
188        }
189    }
190
191    false
192}
193
194fn grows_collection(call: &ast::MethodCallExpr, name: &str) -> bool {
195    if support::method_name(call).is_none_or(|method| !GROW_METHODS.contains(&method.as_str())) {
196        return false;
197    }
198
199    call.receiver()
200        .and_then(|receiver| support::path_expr_name(&receiver))
201        .is_some_and(|receiver| receiver == name)
202}
203
204crate::tidy_ast_test!(check_missing_capacity, {
205    crate::example_tests!(EXAMPLES, check_missing_capacity);
206});
wowlab_tidy/languages/rust/rules/performance/missing_capacity.rs

wowlab_tidy/languages/rust/rules/performance/
missing_capacity.rs
