phanalist

E0044: Input-Dependent Runtime Growth

E0044 reports loops whose work grows faster than the configured runtime threshold as an input-sized collection grows. It is one of Phanalist’s resource-analysis rules (E0044-E0046), which model allocation, retention, and input cardinality separately from the bounded verification rules.

What it checks

• Nested loops over the same input-sized collection
• Loops that repeatedly perform linear work such as array_unshift(), array_merge(), in_array(), array_search(), preg_match(), or repeated array copying
• Linear work inside a loop that is already linear in the same size measure
• Loops whose bound is an unguarded input cardinality, reported together with E0046
• Calls to local functions or methods whose resource summary makes the enclosing loop superlinear

The analyzer represents loop bounds symbolically. It understands constants, count($items), strlen($input), strlen() of simple expressions, and array sizes derived from those values. A finding shows the estimated cost, such as O(count($items)^2), rather than an exact instruction count.

Model limits

E0044 is conservative and intentionally avoids unsupported exact measurements. It does not execute PHP, inspect runtime types, or infer complexity from timing. The following are not modeled precisely:

• Data-dependent loop bounds that are not constants, simple input sizes, or guarded size expressions
• Bounds produced by arbitrary helper functions without a collected resource summary
• Recursion; recursive calls are summarized conservatively and are not unrolled
• Work inside callbacks passed to array_map(), usort(), and similar higher-order functions
• while and do-while loops without a recognizable counter comparison; these are treated as unknown rather than guessed
• Combined for conditions are capped by the tightest known comparison, so $i < count($items) && $i < 100 is bounded at 100
• Destructive builtins that cannot be modeled from the available arguments
• Concurrency, database work, network I/O, and other external costs

A cap established by a comparison guard, such as if (count($items) > 1000), narrows the bound on that path. If the path is not provably capped, the rule keeps the size symbolic and may report conservatively.

Configuration

rules:
  E0044:
    runtime_threshold: quadratic
    heap_alloc_threshold: quadratic
    retained_element_bytes: 32
    report_input_cardinality: true
    include_cli_input: false
    max_findings_per_function: 20

runtime_threshold accepts linear, quadratic, cubic, or exponential. The default quadratic reports loops at O(n^2) and above. E0045 and E0046 share the same resource settings, but each rule reports only its own class.

This site is open source. Improve this page.