forge_lint/sol/med/
tautology.rs

1use super::TypeBasedTautology;
2use crate::{
3    linter::{LateLintPass, LintContext},
4    sol::{Severity, SolLint, analysis::cast_type},
5};
6use alloy_primitives::U256;
7use solar::{
8    ast::{BinOpKind, LitKind, UnOpKind},
9    sema::{
10        Gcx,
11        hir::{ElementaryType, Expr, ExprKind, VariableId},
12        ty::TyKind,
13    },
14};
15use std::cmp::Ordering;
16
17declare_forge_lint!(
18    TYPE_BASED_TAUTOLOGY,
19    Severity::Med,
20    "type-based-tautology",
21    "condition is always true or false based on the variable's type"
22);
23
24impl<'gcx> LateLintPass<'gcx> for TypeBasedTautology {
25    fn check_expr(&mut self, ctx: &LintContext, gcx: Gcx<'gcx>, expr: &'gcx Expr<'gcx>) {
26        let ExprKind::Binary(left, op, right) = &expr.kind else { return };
27
28        // A pair of comparisons can cover the complete type range even when neither is
29        // tautological on its own, e.g. `x > 0 || x == 0` for `uint`.
30        let is_tautology = if op.kind == BinOpKind::Or {
31            matches!((comparison_of(gcx, left), comparison_of(gcx, right)),
32                (Some(l), Some(r)) if is_boundary_composition(&l, &r))
33        } else {
34            split_comparison(expr).is_some_and(|(operand, val, op)| {
35                elem_type_of(gcx, operand)
36                    .and_then(integer_bounds)
37                    .is_some_and(|range| is_tautology(range, val, op))
38            })
39        };
40        if is_tautology {
41            ctx.emit(&TYPE_BASED_TAUTOLOGY, expr.span);
42        }
43    }
44}
45
46/// A signed integer constant as `(is_negative, magnitude)`, matching how solar stores negated
47/// literals (`-128` is `Unary(Neg, Lit(128))`). Zero is always `(false, 0)`.
48type Const = (bool, U256);
49
50fn cmp(a: Const, b: Const) -> Ordering {
51    match (a.0, b.0) {
52        (true, false) => Ordering::Less,
53        (false, true) => Ordering::Greater,
54        (false, false) => a.1.cmp(&b.1),
55        (true, true) => b.1.cmp(&a.1),
56    }
57}
58
59#[derive(Clone, Copy, PartialEq, Eq)]
60struct Range {
61    lo: Const,
62    hi: Const,
63}
64
65fn integer_bounds(ty: ElementaryType) -> Option<Range> {
66    match ty {
67        ElementaryType::UInt(size) => {
68            let bits = size.bits();
69            let hi = if bits == 256 { U256::MAX } else { (U256::ONE << bits) - U256::ONE };
70            Some(Range { lo: (false, U256::ZERO), hi: (false, hi) })
71        }
72        ElementaryType::Int(size) => {
73            let half = U256::ONE << (size.bits() - 1);
74            Some(Range { lo: (true, half), hi: (false, half - U256::ONE) })
75        }
76        _ => None,
77    }
78}
79
80/// True if `x <op> val` has the same truth value for every `x` in `range`.
81fn is_tautology(range: Range, val: Const, op: BinOpKind) -> bool {
82    let (lo, hi) = (cmp(val, range.lo), cmp(val, range.hi));
83    match op {
84        BinOpKind::Gt | BinOpKind::Le => hi.is_ge() || lo.is_lt(),
85        BinOpKind::Ge | BinOpKind::Lt => lo.is_le() || hi.is_gt(),
86        BinOpKind::Eq | BinOpKind::Ne => hi.is_gt() || lo.is_lt(),
87        _ => false,
88    }
89}
90
91/// A relational/equality comparison between an operand and a constant, normalized to
92/// `operand <op> const` (the operator is flipped when the constant is on the left).
93fn split_comparison<'gcx>(expr: &'gcx Expr<'gcx>) -> Option<(&'gcx Expr<'gcx>, Const, BinOpKind)> {
94    let ExprKind::Binary(left, op, right) = &expr.peel_parens().kind else { return None };
95    let flipped = match op.kind {
96        BinOpKind::Lt => BinOpKind::Gt,
97        BinOpKind::Le => BinOpKind::Ge,
98        BinOpKind::Gt => BinOpKind::Lt,
99        BinOpKind::Ge => BinOpKind::Le,
100        BinOpKind::Eq | BinOpKind::Ne => op.kind,
101        _ => return None,
102    };
103    match lit_value_of(right) {
104        Some(val) => Some((left, val, op.kind)),
105        None => Some((right, lit_value_of(left)?, flipped)),
106    }
107}
108
109struct Comparison {
110    variable: VariableId,
111    cast_path: Vec<ElementaryType>,
112    range: Range,
113    op: BinOpKind,
114    val: Const,
115}
116
117/// A comparison of one resolved integer variable (possibly cast) against a constant.
118fn comparison_of<'gcx>(gcx: Gcx<'gcx>, expr: &'gcx Expr<'gcx>) -> Option<Comparison> {
119    let (operand, val, op) = split_comparison(expr)?;
120    let (variable, cast_path, range) = comparison_operand_of(gcx, operand)?;
121    Some(Comparison { variable, cast_path, range, op, val })
122}
123
124/// True when two comparisons over the same operand together cover its whole range.
125fn is_boundary_composition(l: &Comparison, r: &Comparison) -> bool {
126    if l.variable != r.variable || l.cast_path != r.cast_path || l.range != r.range {
127        return false;
128    }
129    let Range { lo, hi } = l.range;
130    let is = |c: &Comparison, op, val| c.op == op && c.val == val;
131    let at_lo = |c| is(c, BinOpKind::Eq, lo) || is(c, BinOpKind::Le, lo);
132    let at_hi = |c| is(c, BinOpKind::Eq, hi) || is(c, BinOpKind::Ge, hi);
133    [(l, r), (r, l)].into_iter().any(|(a, b)| {
134        (is(a, BinOpKind::Gt, lo) && (at_lo(b) || is(b, BinOpKind::Lt, hi)))
135            || (is(a, BinOpKind::Lt, hi) && at_hi(b))
136    })
137}
138
139/// The variable an operand compares, the casts applied to it and the range its values span.
140///
141/// A same-signed widening cast preserves the value, so it neither changes the range nor
142/// distinguishes the operand from the uncast expression; any other cast resets the range to the
143/// target type's and becomes part of the operand's identity.
144fn comparison_operand_of<'gcx>(
145    gcx: Gcx<'gcx>,
146    expr: &'gcx Expr<'gcx>,
147) -> Option<(VariableId, Vec<ElementaryType>, Range)> {
148    match &expr.peel_parens().kind {
149        ExprKind::Ident(_) => {
150            let variable = gcx.resolved_variable(expr)?;
151            let ty = elem_type_of(gcx, expr)?;
152            Some((variable, Vec::new(), integer_bounds(ty)?))
153        }
154        ExprKind::Call(callee, args, _) if args.len() == 1 => {
155            let ty = cast_type(callee)?;
156            let inner = args.exprs().next()?;
157            let (variable, mut cast_path, range) = comparison_operand_of(gcx, inner)?;
158            let source = elem_type_of(gcx, inner)?;
159            let widening = match (source, ty) {
160                (ElementaryType::UInt(from), ElementaryType::UInt(to))
161                | (ElementaryType::Int(from), ElementaryType::Int(to)) => from.bits() <= to.bits(),
162                _ => false,
163            };
164            if widening {
165                return Some((variable, cast_path, range));
166            }
167            cast_path.push(ty);
168            Some((variable, cast_path, integer_bounds(ty)?))
169        }
170        _ => None,
171    }
172}
173
174/// The elementary type selected by the type checker.
175fn elem_type_of(gcx: Gcx<'_>, expr: &Expr<'_>) -> Option<ElementaryType> {
176    match gcx.type_of_expr(expr.peel_parens().id)?.peel_refs().kind {
177        TyKind::Elementary(ty) => Some(ty),
178        _ => None,
179    }
180}
181
182/// A numeric literal or negated numeric literal.
183fn lit_value_of(expr: &Expr<'_>) -> Option<Const> {
184    let (neg, lit) = match &expr.peel_parens().kind {
185        ExprKind::Lit(lit) => (false, lit),
186        ExprKind::Unary(op, inner) if op.kind == UnOpKind::Neg => match &inner.peel_parens().kind {
187            ExprKind::Lit(lit) => (true, lit),
188            _ => return None,
189        },
190        _ => return None,
191    };
192    let LitKind::Number(n) = lit.kind else { return None };
193    Some((neg && !n.is_zero(), n))
194}
forge_lint/sol/med/tautology.rs

forge_lint/sol/med/
tautology.rs
