ComplexityAnalysis.Analyzers

English | Português (Brasil)

Documentation portal

The project's official bilingual documentation portal is planned for rodri-oliveira-dev.github.io/complexity-analyzers. Until the GitHub Pages deployment is confirmed, use the versioned documentation in this repository as the authoritative source.

The ecosystem has three independent integration surfaces:

• ComplexityAnalysis.Analyzers: Roslyn diagnostics during builds and IDE analysis.
• ComplexityAnalysis.Tool: a .NET CLI for reports, snapshots, comparison, duplicate detection, and opt-in quality gates.
• ComplexityAnalysis.Mcp: a local, read-only MCP server for compatible AI tools.

The portal source and local development instructions live in website/.

ComplexityAnalysis.Analyzers is a compile-time Roslyn analyzer for C# that estimates algorithmic complexity and reports diagnostics for costly patterns without adding runtime dependencies or instrumentation to consumer applications.

The analyzer is deliberately conservative: when complexity cannot be proven safely from the available syntax and semantic information, it returns Unknown instead of guessing.

This is intentionally not a general decision procedure for program complexity. No total algorithm can exactly classify the asymptotic running time of every arbitrary program: termination behavior can be encoded into a complexity-classification question through a reduction from the Halting Problem. The analyzer therefore operates on a documented, bounded subset of C# and preserves Unknown outside what it can safely establish. See Architecture for the detailed rationale.

Quick install

When consuming a published package version from NuGet.org:

dotnet add package ComplexityAnalysis.Analyzers

The package works as a compile-time analyzer. After installation, Roslyn loads it during builds and IDE analysis; application code does not call the analyzer and does not take a runtime dependency on it. For local package creation and repository-based consumption, see Getting Started.

Quick example

foreach (var item in items)
{
    if (otherItems.Contains(item))
    {
        // ...
    }
}

When otherItems is a linear-lookup collection such as List<T>, this can report:

BIG1001 - Linear lookup inside iteration

Want to see the analyzer in action? See the runnable sample. For the full rule and configuration reference, start with Getting Started and the Analyzer Catalog.

What it does

• Estimates Big-O complexity for supported C# methods using Roslyn syntax, symbols, and semantic information.
• Detects costly operations inside iteration, including linear lookups, collection materialization, and ordering.
• Understands a documented subset of BCL and LINQ operations by resolved symbol identity rather than method name alone.
• Performs bounded, demand-driven interprocedural analysis for safe source-method calls in the same compilation.
• Solves selected direct-recursion recurrence families, including decrement recurrences, simple exponential recursion, Master Theorem forms, and a restricted Akra-Bazzi subset.
• Measures structural Cyclomatic Complexity independently from Big-O, with standard and Modified McCabe switch accounting.
• Measures Maximum Control-Flow Nesting Depth independently from Big-O and Cyclomatic Complexity.
• Measures NLOC, statement count, and token count as independent executable-member size metrics.
• Measures source-declared Parameter Count independently from all complexity and size metrics.
• Measures Cognitive Complexity as an independent documented C# control-flow comprehension metric.
• Defines internal C# Halstead metrics for future reporting/tooling without emitting a public Halstead threshold diagnostic yet.
• Provides a separate project-level CLI for deterministic aggregate console/JSON reports, opt-in quality gates, and normalized duplicate-code detection outside analyzer hot paths.
• Supports configurable analysis budgets and a maximum-complexity threshold through .editorconfig/analyzer config.
• Runs as a normal Roslyn analyzer during builds and IDE analysis; consumer code does not call the analyzer at runtime.

Diagnostics

ID	Title	Category	Default severity	Enabled by default
BIG0001	Estimated algorithmic complexity	Complexity	Info	No
BIG1001	Linear lookup inside iteration	Complexity	Info	Yes
BIG1002	Materialization inside iteration	Complexity	Info	Yes
BIG1003	Ordering inside iteration	Complexity	Info	Yes
BIG1004	Input-dependent method call inside iteration	Complexity	Info	Yes
BIG1005	Exponential recursive growth	Complexity	Info	Yes
BIG1006	Method complexity exceeds configured threshold	Complexity	Info	Yes
BIG2001	Cyclomatic complexity exceeds configured threshold	Complexity	Info	Yes
BIG2002	Maximum nesting depth exceeds configured threshold	Complexity	Info	Yes
BIG2003	Method NLOC exceeds configured threshold	Complexity	Info	Yes
BIG2004	Statement count exceeds configured threshold	Complexity	Info	Yes
BIG2005	Token count exceeds configured threshold	Complexity	Info	Yes
BIG2006	Parameter count exceeds configured threshold	Complexity	Info	Yes
BIG2007	Cognitive complexity exceeds configured threshold	Complexity	Info	Yes
BIG9000	Analyzer execution probe	Infrastructure	Info	No

BIG0001 is an opt-in informational diagnostic that reports a known method-complexity estimate at the method identifier.

BIG1005 reports supported direct recursive methods whose solved recurrence is exponential, such as Fibonacci-like recursion.

BIG1006 reports when complexity_analyzers.maximum_complexity is configured and a known, comparable estimate exceeds the configured threshold. Unknown and incomparable estimates are not reported.

BIG2001 reports when complexity_analyzers.maximum_cyclomatic_complexity is configured and a supported executable member's structural Cyclomatic Complexity exceeds that maximum. It is independent from Big-O and can use standard or Modified McCabe switch accounting.

BIG2002 reports when complexity_analyzers.maximum_nesting_depth is configured and a supported executable member's Maximum Control-Flow Nesting Depth exceeds that maximum. Straight-line code has depth 0; sibling branches do not accumulate; nested local functions, lambdas, and anonymous methods are analyzed independently.

BIG2003, BIG2004, and BIG2005 report when their matching method-size thresholds are configured and a supported executable member exceeds NLOC, statement-count, or token-count policy. These are size metrics, not Big-O or control-flow metrics.

BIG2006 reports when complexity_analyzers.maximum_parameters is configured and a supported executable member declares more source parameters than allowed. It counts declared parameters, including extension-method this receivers, but not type parameters, captured variables, implicit instance this, or implicit accessor value.

BIG2007 reports when complexity_analyzers.maximum_cognitive_complexity is configured and a supported executable member exceeds this project's documented C# Cognitive Complexity convention. Straight-line code has score 0; structural control-flow breaks and local nesting increase the score.

BIG9000 is an infrastructure probe used to prove that the analyzer package loaded and executed. It is not a performance recommendation.

See the Analyzer Catalog for rule details.

Analysis model

Known BCL and LINQ operations

Known operations are mapped by Roslyn symbol identity. Custom methods named Contains, Where, ToList, or similar are not treated as BCL/LINQ operations unless their resolved symbol belongs to the supported subset.

Implemented examples include:

• List<T>.Add, List<T>.Contains, List<T>.IndexOf, List<T>.Sort, List<T>.Count, and the List<T> indexer.
• Dictionary<TKey,TValue>.ContainsKey and Dictionary<TKey,TValue>.ContainsValue.
• HashSet<T>.Contains.
• Array and string Length.
• LINQ Any, All, Contains, Count, LongCount, ToList, ToArray, ToDictionary, ToHashSet, Sum, Min, Max, and Aggregate.
• Deferred LINQ operations including Where, Select, SelectMany, OrderBy, OrderByDescending, ThenBy, ThenByDescending, Distinct, and GroupBy.

Each known-operation estimate records whether its Big-O expression is a worst-case upper bound, expected cost, amortized cost, or Unknown, together with the assumptions required by that classification. In particular, Dictionary<TKey,TValue>.ContainsKey and HashSet<T>.Contains are modeled as expected O(1) only when hash codes are sufficiently distributed and hashing and equality have constant cost; they are not unconditional worst-case guarantees. Existing Big-O text remains unchanged for compatibility.

List<T>.Add is amortized O(1) across an append sequence under geometric capacity growth and constant-cost element assignment; one append that grows the backing storage can still take O(n). Calls resolved only through generic collection interfaces remain Unknown because interface contracts do not prove the runtime implementation or its complexity.

Deferred LINQ pipeline creation is not charged as a full enumeration. Direct chains and stable local pipelines retain their known cardinality and are charged when a supported terminal operation or foreach consumes them, including each proven re-enumeration. Predicate and selector cost is included only for inline delegates, stable local delegates, or safe source/local targets whose body is available; unresolved or reassigned delegate targets and delegates with mutable captured state remain Unknown when the pipeline is consumed.

Interprocedural analysis

When a caller invokes a supported source method declared in the same Roslyn Compilation, the analyzer can derive a caller-independent callee template and substitute the caller arguments into that template.

Supported source methods require safe dispatch, such as static methods, private methods, non-virtual methods, or sealed dispatch where the runtime target is proven. Known BCL/LINQ operations take precedence over source-method analysis.

Traversal is demand-driven and bounded. A callee is analyzed only when reached from the current root method. The analyzer does not pre-scan every syntax tree or construct a whole-compilation call graph.

Examples:

A -> B O(n)           => A O(n)
loop n -> B O(n)     => O(n^2)
loop n -> B O(m)     => O(n * m)
B(left) + B(right)   => O(n + m)
B(constant)          => O(1)
A -> B -> C O(log n) => O(log n)

Unsupported, unresolved, unsafe, budget-limited, cancelled, or cyclic calls remain Unknown.

Direct recursion and recurrence solving

The analyzer recognizes direct recursive calls by Roslyn symbol identity and requires compatible base-case evidence before solving a recurrence. Recursive calls in mutually exclusive branches are counted per path, so binary-search-style code remains O(log n) rather than being over-counted as linear.

Supported recurrence families include:

• decrement/summation forms such as T(n)=T(n-1)+1, T(n)=T(n-1)+n, and T(n)=T(n-1)+log n;
• simple exponential recursion such as 2T(n-1)+1 and Fibonacci-like T(n-1)+T(n-2)+1;
• Master Theorem forms such as T(n)=T(n/2)+1, 2T(n/2)+n, 2T(n/2)+n^2, and 3T(n/2)+n;
• a restricted, bounded Akra-Bazzi subset with scale-only recursive terms and polylogarithmic tolls, for example T(n)=T(n/3)+T(2n/3)+n.

Fractional polynomial powers are represented deterministically, so 3T(n/2)+n reports O(n^1.585).

Missing base cases, non-reducing arguments, unsupported recurrence shapes, unknown local work, numerical inconclusiveness, cancellation, and mutual recursion remain Unknown.

Build from source

Prerequisites:

• .NET SDK 10.0.401 or a compatible SDK selected by global.json.
• A shell capable of running dotnet commands.

From the repository root:

dotnet restore ComplexityAnalysis.Analyzers.slnx
dotnet build ComplexityAnalysis.Analyzers.slnx --configuration Release --no-restore
dotnet test ComplexityAnalysis.Analyzers.slnx --configuration Release --no-build
dotnet pack src/ComplexityAnalysis.Analyzers/ComplexityAnalysis.Analyzers.csproj --configuration Release --no-build -p:PackageVersion=0.0.0-local --output artifacts/local-packages

The repository also documents local package creation and consumption. If you are working before a stable NuGet.org package version is available, use the local package flow in Getting Started.

See Getting Started.

Project-level CLI

ComplexityAnalysis.Tool is a separately versioned .NET 10 tool for explicit project- and solution-level reports. After 1.0.0 is published, install it from NuGet.org:

dotnet tool install --global ComplexityAnalysis.Tool --version 1.0.0
complexity-analysis analyze MySolution.slnx
complexity-analysis analyze MyProject.csproj --format json
complexity-analysis analyze MyProject.csproj --format sarif
complexity-analysis analyze MyProject.csproj --max-cyclomatic-complexity 10

For a pinned local tool manifest:

dotnet new tool-manifest
dotnet tool install ComplexityAnalysis.Tool --version 1.0.0
dotnet tool restore
dotnet tool run complexity-analysis analyze MyProject.csproj

The CLI supports .csproj, .slnx, and .sln, console/JSON/SARIF reports, snapshots and regression comparison, opt-in quality gates, exclusions, and normalized duplicate detection. The Roslyn analyzer runs during compilation; the CLI runs only when invoked; the local MCP host is a separate read-only integration surface.

To test an unpublished package built from this source tree, use an explicit local source and local-only version:

dotnet pack src/ComplexityAnalysis.Tool/ComplexityAnalysis.Tool.csproj --configuration Release -p:Version=0.0.0-local -p:PackageVersion=0.0.0-local --output artifacts/local-packages
dotnet tool install ComplexityAnalysis.Tool --version 0.0.0-local --add-source artifacts/local-packages --tool-path artifacts/local-tools
artifacts/local-tools/complexity-analysis analyze samples/ComplexityAnalysis.Sample/ComplexityAnalysis.Sample.csproj

This local flow is not evidence of a NuGet.org release. The package is independent from ComplexityAnalysis.Analyzers; installing either package does not install the other or add a runtime dependency to analyzer consumers.

See Project-Level Tooling.

MCP server for agents

ComplexityAnalysis.Mcp exposes the CLI analysis contracts to local MCP clients over stdio. It is independently packaged as a .NET 10 tool and is not an autonomous agent. After 1.0.0 is published, install and start it with:

dotnet tool install --global ComplexityAnalysis.Mcp --version 1.0.0
complexity-mcp --root /absolute/path/to/project

Its three tools are read-only: analyze a project, query evidence for a stable member identity, and compare snapshots. Configure clients such as VS Code, Codex, or Claude Desktop with the installed command:

{
  "command": "complexity-mcp",
  "args": [
    "--root",
    "/absolute/path/to/project"
  ]
}

The host rejects paths outside that root, symbolic-link traversal, unsupported inputs, and workloads beyond its configured timeout, byte, and file limits. It does not expose shell, write, network, or arbitrary process operations. Full responses remain the default; an explicit summary mode reduces agent context. Every analyze_project response returns an analysisId for efficient exact evidence lookup.

See Local MCP Server and the MCP package README. Published versions are also discoverable as io.github.rodri-oliveira-dev/complexity-analysis in the Official MCP Registry, whose metadata points to the installable NuGet.org package.

Configuration

Analyzer behavior is configurable through Roslyn analyzer config. Diagnostic severities continue to use standard dotnet_diagnostic.<RULE_ID>.severity entries.

[*.cs]

complexity_analyzers.interprocedural_analysis = true
complexity_analyzers.recursion_analysis = true
complexity_analyzers.max_call_depth = 5
complexity_analyzers.max_methods_per_root = 32
complexity_analyzers.maximum_complexity = n_log_n
complexity_analyzers.maximum_cyclomatic_complexity = 10
complexity_analyzers.cyclomatic_complexity_mode = standard
complexity_analyzers.maximum_nesting_depth = 3
complexity_analyzers.maximum_method_nloc = 40
complexity_analyzers.maximum_statement_count = 25
complexity_analyzers.maximum_token_count = 300
complexity_analyzers.maximum_parameters = 5
complexity_analyzers.maximum_cognitive_complexity = 15

dotnet_diagnostic.BIG0001.severity = suggestion
dotnet_diagnostic.BIG1001.severity = warning
dotnet_diagnostic.BIG1002.severity = warning
dotnet_diagnostic.BIG1003.severity = warning
dotnet_diagnostic.BIG1004.severity = warning
dotnet_diagnostic.BIG1005.severity = warning
dotnet_diagnostic.BIG1006.severity = warning
dotnet_diagnostic.BIG2001.severity = warning
dotnet_diagnostic.BIG2002.severity = warning
dotnet_diagnostic.BIG2003.severity = warning
dotnet_diagnostic.BIG2004.severity = warning
dotnet_diagnostic.BIG2005.severity = warning
dotnet_diagnostic.BIG2006.severity = warning
dotnet_diagnostic.BIG2007.severity = warning
dotnet_diagnostic.BIG9000.severity = none

Defaults keep interprocedural and recursion analysis enabled, max_call_depth at 5, max_methods_per_root at 32, maximum_complexity at none, maximum_cyclomatic_complexity unset, cyclomatic_complexity_mode at standard, and all nesting/method-size/parameter/cognitive thresholds unset. Threshold reporting only applies to the configured metric.

See Configuration.

Performance and compatibility

The analyzer is designed to remain bounded and suitable for compiler/IDE execution: no network access, no analyzer hot-path filesystem I/O, no process launch, no telemetry, no mandatory whole-solution scan, bounded source-method traversal, bounded recurrence solving, concurrent execution, generated-code exclusion, and cancellation checks.

The repeatable performance harness is documented in performance/README.md. It validates structural behavior and compiler analyzer execution reporting with ReportAnalyzer=true; elapsed time is informational because hardware and CI runners vary.

CI validates local package consumption on .NET 8, .NET 9, and .NET 10 SDK hosts to catch analyzer loading and compatibility regressions.

Architecture

The package is a compile-time analyzer, not a runtime library:

application source
        |
        | compiled by
        v
Roslyn compiler / IDE host
        |
        | loads
        v
ComplexityAnalysis.Analyzers

The analyzer assembly is packed under:

analyzers/dotnet/cs/

See Architecture.

Documentation

• Changelog
• Getting Started
• Analyzer Catalog
• Architecture
• Configuration
• C# Halstead Metrics
• Project-Level Tooling
• Local MCP Server
• Runnable sample
• Release Quality Governance
• Documentação em português

Limitations

• Source-method analysis is limited to ordinary safe-dispatch methods in the same compilation.
• There is no whole-compilation or whole-solution call graph.
• Recurrence solving is limited to supported direct-recursion shapes with base-case evidence.
• Mutual recursion is detected but not solved.
• Akra-Bazzi support is a restricted/bounded subset, not the full theorem.
• General characteristic polynomials, general numerical integration, MathNet, SymPy, and inherited solver projects are not used.
• No CodeFixProvider is included.
• Microsoft.CodeAnalysis.Workspaces is not used.
• Unsupported or unproven behavior prefers Unknown over unsafe guesses.

License

MIT, matching the package license declaration.