rust-lang/rust-clippy

New Lint: No recursion without tail calls

Open

#1678 opened on Apr 15, 2017

View on GitHub
 (7 comments) (0 reactions) (0 assignees)Rust (10,406 stars) (1,391 forks)batch import
A-lintL-perfT-middlegood first issue

Description

Based on this HIC++ guideline.

The stack explodes much faster using recursion than a huge BFS work queue would explode the heap. Therefore, if clippy detects some direct or indirect recursion that does not benefit from tail call optimisation, clippy should issue a warning along with a short description about why this is potentially bad and a short hint on how to transform recursive algorithms to iterative ones (e.g. using a work queue and BFS). And maybe a tl;dr about what tail calls are and how to make the algorithm tail recursive.

Contributor guide

Tech stack
rust
Domain
developer experienceperformance
Issue type
feature
DifficultyEstimated implementation difficulty for a new contributor, from 1 for very small changes to 5 for expert-level work.
4
Estimated timeA rough time range for an experienced contributor to investigate, implement, test, and prepare a pull request.
3-5 days
Activity statusHow available the issue appears right now: fresh, active, stale, blocked, or waiting on maintainer input.
stale
ClarityHow clearly the issue explains the expected change, acceptance criteria, and next step.
clear
Prerequisites
Rust programming knowledgeTail call optimization conceptClippy lint API
Newbie friendlinessA 1-100 score estimating how approachable this issue is for first-time contributors.
35
Research direction
Review existing Clippy lint implementations in clippy lints/src/ for patterns. Study Rust's MIR to understand recursion detection. Explore tail call optimization criteria and how to determine if a recursive call is in tail position. Consider indirect recursion via function pointers. Test with examples from the HIC++ guideline linked in the issue. Discuss approach in issue comments before implementing.