sqc 0.4.13

//! MEM11-C: Do not assume infinite heap space
//!
//! Memory is fundamentally limited. Programs that continuously allocate memory
//! without bounds can exhaust the heap, leading to undefined behavior and crashes.
//! This is particularly problematic in:
//! 1. Long-running servers that accumulate data
//! 2. Loops with user-controlled iteration counts
//! 3. Unbounded data structure growth (linked lists, trees, etc.)
//!
//! While static analysis cannot perfectly detect heap exhaustion (as it depends on
//! runtime environment), we can identify common anti-patterns like memory allocation
//! in loops without upper bound checks.
//!
//! ## Examples:
//!
//! **Non-compliant:**
//! ```c
//! do {
//!     fgets(new_name, MAX_LENGTH, stdin);
//!     if (strcmp(new_name, "quit") != 0) {
//!         namelist_t new_entry = malloc(sizeof(struct namelist_s)); // Unbounded allocation
//!         if (new_entry == NULL) { /* Handle error */ }
//!         // ... add to list ...
//!     }
//! } while (strcmp(new_name, "quit") != 0);
//! ```
//!
//! **Compliant:**
//! ```c
//! // Use database or file storage instead of accumulating in memory
//! // Or implement a maximum size limit:
//! int count = 0;
//! do {
//!     if (count >= MAX_ENTRIES) {
//!         /* Refuse to add more entries */
//!         break;
//!     }
//!     // ... allocate and add entry ...
//!     count++;
//! } while (...);
//! ```

use super::super::{CertRule, RuleViolation};
use crate::manifest::{RuleCategory, Severity};
use crate::utility::cert_c::ast_utils::get_node_text;
use tree_sitter::Node;

pub struct Mem11C;

impl CertRule for Mem11C {
    fn rule_id(&self) -> &'static str {
        "MEM11-C"
    }

    fn description(&self) -> &'static str {
        "Do not assume infinite heap space"
    }

    fn severity(&self) -> Severity {
        Severity::Low
    }

    fn category(&self) -> RuleCategory {
        RuleCategory::Rule
    }

    fn cert_id(&self) -> &'static str {
        "MEM11-C"
    }

    fn check(&self, node: &Node, source: &str) -> Vec<RuleViolation> {
        let mut violations = Vec::new();
        self.check_unbounded_allocations(node, source, &mut violations);
        violations
    }
}

impl Mem11C {
    fn check_unbounded_allocations(
        &self,
        node: &Node,
        source: &str,
        violations: &mut Vec<RuleViolation>,
    ) {
        // Look for loop statements
        match node.kind() {
            "while_statement" | "do_statement" | "for_statement"
                // Check if this loop contains memory allocations
                if self.contains_memory_allocation(node, source)
                    // Check if there's a bound check (like a counter)
                    && !self.has_bound_check(node, source) => {
                        violations.push(RuleViolation {
                            rule_id: self.rule_id().to_string(),
                            message: "Memory allocation in loop without upper bound check. \
                                     Unbounded memory allocation can exhaust heap space. \
                                     Consider using databases, file storage, or implementing \
                                     a maximum size limit for data structures."
                                .to_string(),
                            severity: self.severity(),
                            line: node.start_position().row + 1,
                            column: node.start_position().column + 1,
                            file_path: String::new(),
                            suggestion: Some(
                                "Add a counter to limit iterations or use persistent storage \
                                 (database/file) instead of accumulating unbounded data in memory"
                                    .to_string(),
                            ),
                            requires_manual_review: Some(true),
                        });
                    }
            _ => {}
        }

        // Recurse through children
        for i in 0..node.child_count() {
            if let Some(child) = node.child(i) {
                self.check_unbounded_allocations(&child, source, violations);
            }
        }
    }

    /// Check if a node contains memory allocation calls (malloc, calloc, realloc)
    fn contains_memory_allocation(&self, node: &Node, source: &str) -> bool {
        if node.kind() == "call_expression" {
            if let Some(function) = node.child_by_field_name("function") {
                let func_name = get_node_text(&function, source);
                if func_name == "malloc" || func_name == "calloc" || func_name == "realloc" {
                    return true;
                }
            }
        }

        // Recurse through children
        for i in 0..node.child_count() {
            if let Some(child) = node.child(i) {
                if self.contains_memory_allocation(&child, source) {
                    return true;
                }
            }
        }

        false
    }

    /// Check if there's a bound check in the loop (heuristic: look for counter variables)
    /// This is a simplified heuristic - we look for common patterns like:
    /// - Counter increment with comparison (count++; if (count >= MAX))
    /// - Loop counter with break based on limit
    /// - Loop condition checking against a limit
    fn has_bound_check(&self, node: &Node, source: &str) -> bool {
        // Look for specific patterns that indicate iteration bounds:
        // 1. Counter variable being incremented (count++, i++, etc.)
        // 2. Break statement with counter comparison
        // 3. Conditional with counter >= or > a limit

        if self.has_counter_with_limit(node, source) {
            return true;
        }

        false
    }

    /// Check if there's a counter variable being incremented with a limit check
    fn has_counter_with_limit(&self, node: &Node, source: &str) -> bool {
        let mut has_increment = false;
        let mut has_comparison = false;

        // Recursively search for increment and comparison patterns
        self.search_counter_patterns(node, source, &mut has_increment, &mut has_comparison);

        // Both increment and comparison must be present
        has_increment && has_comparison
    }

    fn search_counter_patterns(
        &self,
        node: &Node,
        source: &str,
        has_increment: &mut bool,
        has_comparison: &mut bool,
    ) {
        let node_text = get_node_text(node, source);

        // Check for increment patterns (count++, ++count, count += 1, i++, etc.)
        if node.kind() == "update_expression" {
            // count++, ++count
            *has_increment = true;
        } else if node.kind() == "assignment_expression" {
            // count += 1, count = count + 1
            if node_text.contains("+=") || node_text.contains("= ") && node_text.contains(" + 1") {
                *has_increment = true;
            }
        }

        // Check for comparison patterns in conditions
        if node.kind() == "binary_expression" {
            if let Some(operator) = node.child_by_field_name("operator") {
                let op = get_node_text(&operator, source);
                if op == ">=" || op == ">" || op == "<" || op == "<=" {
                    // Check if this is comparing a variable to something
                    // (not just any comparison, but one that looks like a limit)
                    if node_text.contains("count")
                        || node_text.contains("limit")
                        || (node_text.contains("MAX") && node_text.contains(">="))
                        || (node_text.contains("MAX") && node_text.contains(">"))
                    {
                        *has_comparison = true;
                    }
                }
            }
        }

        // Check for break statements with conditions
        if node.kind() == "if_statement" {
            if let Some(body) = node.child_by_field_name("consequence") {
                let body_text = get_node_text(&body, source);
                if body_text.contains("break") {
                    // This is a conditional break, check if condition has comparison
                    if let Some(condition) = node.child_by_field_name("condition") {
                        let cond_text = get_node_text(&condition, source);
                        if cond_text.contains(">=")
                            || cond_text.contains(">")
                            || cond_text.contains("MAX")
                            || cond_text.contains("limit")
                        {
                            *has_comparison = true;
                        }
                    }
                }
            }
        }

        // Recurse through children
        for i in 0..node.child_count() {
            if let Some(child) = node.child(i) {
                self.search_counter_patterns(&child, source, has_increment, has_comparison);
            }
        }
    }
}