Architecture

English | Português (Brasil)

ComplexityAnalysis.Analyzers is a standalone Roslyn analyzer package. The repository root is the product boundary: analyzer source lives under src/, tests under tests/, performance validation under performance/, and documentation under docs/.

The design favors conservative results, bounded analysis, deterministic behavior, and compatibility with compiler and IDE hosts.

Analysis pipeline

C# source
    |
    v
Roslyn syntax + SemanticModel
    |
    v
Executable-member analysis
    (supported C# executable constructs)
    |
    +-- analyzer configuration
    +-- input-size resolution
    +-- basic operations
    +-- loop bounds
    +-- known BCL/LINQ operations
    +-- safe source-method calls
    +-- direct-recursion extraction
    +-- recurrence solving
    +-- structural control-flow metrics
    +-- C# Halstead primitive and derived metrics
    |
    v
Complexity model
    |
    +-- atomic expressions
    +-- growth comparison
    +-- composition
    +-- Unknown
    |
    v
DiagnosticAnalyzer
    |
    +-- BIG0001 estimated complexity
    +-- BIG1001 linear lookup inside iteration
    +-- BIG1002 materialization inside iteration
    +-- BIG1003 ordering inside iteration
    +-- BIG1004 source call inside iteration
    +-- BIG1005 exponential recursive growth
    +-- BIG1006 configured threshold exceeded
    +-- BIG2001 cyclomatic threshold exceeded
    +-- BIG2002 maximum nesting threshold exceeded
    +-- BIG2003 method NLOC threshold exceeded
    +-- BIG2004 statement-count threshold exceeded
    +-- BIG2005 token-count threshold exceeded
    +-- BIG2006 parameter-count threshold exceeded
    +-- BIG2007 cognitive-complexity threshold exceeded
    `-- BIG9000 execution probe

Package boundary

The package is loaded by compiler and IDE hosts:

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

The analyzer project targets netstandard2.0 for host compatibility and is packed as an analyzer asset under:

analyzers/dotnet/cs/

It is not a runtime library. Consumer applications do not call analyzer classes, and Roslyn authoring dependencies are kept private rather than exposed transitively.

The repository build SDK is a separate concern. global.json selects SDK 10.0.401 for repository restore, build, tests, and pack, while supported compiler hosts are validated by installing the produced .nupkg into temporary consumer projects.

Project-Level Tooling Boundary

ComplexityAnalysis.Tool is a separate repository tool for project-level analysis:

.csproj / .slnx / .sln
        |
        v
ComplexityAnalysis.Tool
        |
        +-- project/source loading
        +-- aggregate report model
        +-- console and JSON writers
        +-- opt-in quality gates
        +-- normalized duplicate-code detection
        |
        v
shared analyzer metric calculators

The dependency direction is one-way: the CLI can reference ComplexityAnalysis.Analyzers to reuse metric implementations, but the analyzer project and produced NuGet package do not reference the CLI. Whole-project source loading, duplicate detection, filesystem traversal, report rendering, and quality-gate exit codes are therefore kept outside DiagnosticAnalyzer.Initialize and analyzer execution callbacks.

The CLI currently supports .csproj, .slnx, and .sln entry points without adding Microsoft.CodeAnalysis.Workspaces to the analyzer package. SARIF is a future report-writer extension over the aggregate report model rather than a dependency of analyzer internals.

Compatibility contracts

Contract	Current value
Repository build SDK	.NET SDK 10.0.401 from global.json.
Repository C# language version	12.0.
Analyzer target framework	netstandard2.0, preserved for compiler/IDE host compatibility.
Roslyn compiler API baseline	Microsoft.CodeAnalysis.CSharp 4.8.0, resolving Microsoft.CodeAnalysis.Common 4.8.0.
Analyzer authoring rules	Microsoft.CodeAnalysis.Analyzers 3.11.0.
Supported SDK host matrix	.NET 8, .NET 9, and .NET 10 consumer builds in CI.
Package analyzer path	analyzers/dotnet/cs/ComplexityAnalysis.Analyzers.dll.
Runtime package assets	No analyzer lib/ asset and no transitive Roslyn dependency group.

Compiling against newer Roslyn packages can introduce API references that older compiler or IDE hosts cannot load. Roslyn upgrades are therefore conservative: update proposals must keep Roslyn assets private, inspect the generated package, run the package/consumer contract tests, and validate every supported SDK host before merge.

Repository structure

The main product areas are:

src/ComplexityAnalysis.Analyzers/
    Analysis/
    Configuration/
    Diagnostics/
    Model/
    ComplexityAnalyzer.cs

src/ComplexityAnalysis.Tool/
    Cli/
    Duplicates/
    Project/
    Reporting/

tests/
performance/
docs/

The repository no longer depends on inherited implementation projects. The analyzer is developed and validated directly from the root solution.

Complexity model

The Roslyn-free model lives under:

src/ComplexityAnalysis.Analyzers/Model/

It represents complexity independently from C# syntax so mathematical behavior remains immutable, deterministic, and testable without compiler APIs.

The model supports:

• constant, polynomial/logarithmic, exponential, factorial, and Unknown forms;
• deterministic formatting, including fractional powers such as O(n^1.585);
• growth comparison for comparable expressions;
• conservative incomparability for independent variables;
• sequential, nested, and branch composition.

When the analyzer cannot prove a safe result, the model preserves Unknown rather than coercing the operation to a guessed complexity class.

Estimate guarantees and assumptions

A Big-O expression and the nature of its guarantee are separate model values:

Guarantee	Meaning	Required evidence
Worst-case upper bound	The expression bounds every supported execution under any listed non-probabilistic assumptions.	A known expression; assumptions are optional and must state conditional operation or runtime costs.
Expected	The expression is an expectation, not a bound for every execution.	A known expression and an explicit input or hash-distribution assumption.
Amortized	The expression applies across a sequence of operations and need not bound each individual operation.	A known expression and an explicit operation-sequence assumption.
Unknown	The available evidence does not prove a supported estimate.	The Unknown expression and no claimed assumptions.

The model rejects an expected estimate without a distribution assumption, an amortized estimate without an operation-sequence assumption, and any known guarantee paired with Unknown. Assumptions are immutable typed values so this contract is deterministic and testable without Roslyn.

For compatibility, ToBigONotation() and existing diagnostics continue to render the expression as before. The guarantee metadata qualifies that text; it does not turn an expected or amortized signal into a universal mathematical proof. For example, hash-table lookup is expected O(1) only under adequate hash distribution and constant-cost hashing/equality, while an unsupported operation remains Unknown rather than inheriting that estimate. Linear list lookups and O(n log n) sorting similarly record constant-cost equality or comparison as an explicit condition.

Structured analysis evidence

An opt-in internal analysis path can accompany a complexity result with a deterministic evidence trace. Each step records the operation category and origin, a source location relative to the current executable member, input dimensions, the qualified estimate and its assumptions, the composition rule, and a typed inconclusion reason when the step is Unknown. The initial vertical slice covers loop bounds, mapped BCL/LINQ invocations, and propagated calls to source methods.

Evidence collection is isolated from the normal diagnostic path, performs no I/O or telemetry, and never stores file paths. It is bounded to 8 levels and 64 steps by default, with hard maximums of 16 levels and 256 steps. Reaching either limit marks the trace as truncated without changing the calculated complexity. Stable ordering, relative locations, and per-analysis ownership keep snapshots deterministic under concurrent analysis. The trace is an internal analysis contract; existing diagnostic messages and public report formats remain unchanged.

Cyclomatic Complexity, Maximum Control-Flow Nesting Depth, and Cognitive Complexity are separate integer structural metrics. Halstead metrics are a separate source-token classification capability with primitive and derived values. These metrics are computed from executable-member syntax and are not combined with the Big-O complexity model or with each other.

Theoretical limits

The analyzer deliberately does not attempt to classify the asymptotic running time of every possible C# program. A total and exact classifier for arbitrary implementations would run into computability limits.

A direct reduction from the Halting Problem illustrates the boundary without relying on non-terminating input programs. Given an arbitrary machine M, construct a program P(n) that simulates M for at most n steps. If the simulation has not halted, P performs linear work; if it has halted, P performs quadratic work. P(n) always terminates because the simulation is bounded. If M never halts, P remains O(n). If M halts after some fixed number of steps, then for every sufficiently large n, P performs quadratic work and is O(n^2). An exact classifier able to distinguish those classes for arbitrary programs would therefore decide whether M halts.

Rice’s theorem is related to the broader computability context, but it is not the direct justification used here. In its classical form, Rice’s theorem concerns non-trivial extensional properties of the partial function computed by a program. Time complexity of a particular implementation is not extensional: two programs can compute the same function while having different asymptotic running times.

For that reason, this analyzer operates on explicitly supported program shapes and semantic evidence, with bounded interprocedural and recurrence analysis. When the available model cannot establish a safe result, Unknown is the intended result rather than a guessed complexity class.

Roslyn analysis

The main analysis layer lives under:

src/ComplexityAnalysis.Analyzers/Analysis/

Analysis starts from an internal executable-member abstraction and evaluates supported syntax and semantic facts. The analyzer normalizes ordinary methods, constructors, property/event accessors, operators, conversion operators, local functions, lambdas, anonymous methods, and supported expression-bodied forms into the same member pipeline when symbol identity, body ownership, and diagnostic location are available. Responsibilities include member/body extraction, input-size resolution, basic-operation classification, loop-bound analysis, known-operation mapping, source-call propagation, direct-recursion handling, and structural control-flow metrics such as Cyclomatic Complexity and Maximum Control-Flow Nesting Depth.

Representative components include:

• ExecutableMember for the analyzed member identity, body, display name, and diagnostic location;
• ExecutableMemberSyntax for executable-body boundaries that keep nested local functions, lambdas, and anonymous methods from inflating their lexical parent;
• MethodComplexityExtractor for method/body composition;
• MethodAnalysisContext for semantic and input-size context;
• InputSizeResolver for canonical dimensions such as n, m, k, p, and later variables;
• BasicOperationAnalyzer for proven basic work;
• LoopBoundAnalyzer for supported loop bounds;
• KnownOperationComplexityAnalyzer for supported BCL/LINQ costs.
• CyclomaticComplexityAnalyzer for structural path-complexity scoring that stays independent from Big-O.
• MaximumNestingDepthAnalyzer for maximum control-flow nesting depth scoring that stays independent from Big-O and Cyclomatic Complexity.
• CognitiveComplexityCalculator for the documented structural comprehension score that stays independent from Big-O, Cyclomatic Complexity, and Maximum Nesting Depth.
• HalsteadMetricsAnalyzer for C#-specific primitive counts and derived Halstead values that stay independent from Big-O and the public threshold diagnostics.

The analyzer does not require a whole-compilation or whole-solution call graph. Nested executable constructs are analyzed as their own roots. A parent member does not automatically traverse a local function, lambda, or anonymous method body unless that nested executable is reached through a supported call path.

Known BCL and LINQ operations

Known operations are resolved by Roslyn symbol identity, not text-only method names. This prevents a user-defined method named Contains, Where, or ToList from being treated as a framework operation accidentally.

Known-operation infrastructure lives under:

src/ComplexityAnalysis.Analyzers/Analysis/KnownOperations/

Deferred LINQ operations such as Where and OrderBy are not charged as full enumeration merely when created. Enumeration or sorting cost is applied when supported consumption is proven, such as through a terminal operation or foreach.

The bounded deferred-sequence analysis can follow a pipeline through an unchanged local initializer. It resolves locals and delegate targets by Roslyn symbol identity, rejects intervening writes, and replays the pipeline plan for each proven consumption. Delegate-body cost is propagated only from inline delegates, stable local delegates without mutable captured state, or safe source/local targets available in the same syntax tree; other targets make the consumed pipeline Unknown.

Unsupported or unresolved operations remain Unknown.

Collection mappings are keyed to the statically resolved declaring symbol. Concrete non-virtual List<T>, Dictionary<TKey,TValue>, and HashSet<T> operations can therefore carry documented guarantees and assumptions, while a same-name operation reached through ICollection<T>, IList<T>, ISet<T>, IDictionary<TKey,TValue>, or a read-only interface remains Unknown. The analyzer does not speculate about the runtime implementation behind interface dispatch.

Interprocedural source calls

Interprocedural analysis can include the cost of a supported source callee in the caller estimate. Callee results can be represented as templates relative to the callee parameters and then substituted using caller arguments.

Caller
  |
  v
Invocation resolution
  |
  +-- known BCL/LINQ operation
  |
  `-- supported source method
          |
      template/cache
          |
      argument substitution
          |
          v
Caller complexity

Traversal is demand-driven. A source method is analyzed only when reached from the current root, known-operation resolution does not apply, dispatch is safe, and the configured/internal analysis budget allows expansion.

Supported source dispatch includes static methods, private methods, ordinary non-virtual methods, sealed dispatch when the runtime target is proven, and direct local-function invocations. Unsafe virtual/interface dispatch, dynamic dispatch, delegates, reflection, external metadata-only methods, constructors, property access, event access, operators, conversions, lambdas, and anonymous methods as callees remain outside the supported interprocedural scope.

Cycles are detected conservatively. Direct recursion can be handled by the recurrence pipeline; mutual recursion is detected but not solved.

Direct recursion and recurrence solving

Recurrence analysis lives under:

src/ComplexityAnalysis.Analyzers/Analysis/Recursion/

The recursive pipeline separates detection, recurrence extraction, and solving. A supported recurrence requires semantic direct recursion, compatible base-case evidence, a provably reducing argument, and known local work.

Supported solver families include:

• summation/decrement recurrences;
• a bounded simple exponential subset;
• Master Theorem forms;
• a restricted, bounded Akra-Bazzi subset.

The implementation is deterministic and bounded. It does not perform general symbolic recurrence solving, general numerical integration, process execution, network access, MathNet/SymPy integration, or calls into external solver projects.

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

Configuration

Configuration is read through Roslyn AnalyzerConfigOptionsProvider; the analyzer does not parse .editorconfig files manually.

Public behavior options are:

• complexity_analyzers.interprocedural_analysis;
• complexity_analyzers.recursion_analysis;
• complexity_analyzers.max_call_depth;
• complexity_analyzers.max_methods_per_root;
• complexity_analyzers.maximum_complexity;
• complexity_analyzers.maximum_cyclomatic_complexity;
• complexity_analyzers.cyclomatic_complexity_mode;
• complexity_analyzers.maximum_nesting_depth;
• complexity_analyzers.maximum_method_nloc;
• complexity_analyzers.maximum_statement_count;
• complexity_analyzers.maximum_token_count;
• complexity_analyzers.maximum_parameters;
• complexity_analyzers.maximum_cognitive_complexity.

Tree-specific analyzer config values override global values for that syntax tree. Invalid values fall back to documented defaults rather than producing analyzer failures.

See Configuration for details.

Diagnostics

ComplexityAnalyzer exposes:

• BIG0001 for opt-in method complexity estimates;
• BIG1001 for supported linear lookups inside analyzable iteration;
• BIG1002 for supported materialization inside analyzable iteration;
• BIG1003 for supported consumed ordering inside analyzable iteration;
• BIG1004 for supported input-dependent source calls inside analyzable iteration;
• BIG1005 for supported direct recursion with solved exponential growth;
• BIG1006 for known comparable estimates above a configured threshold;
• BIG2001 for supported executable members above a configured Cyclomatic Complexity threshold;
• BIG2002 for supported executable members above a configured Maximum Control-Flow Nesting Depth threshold;
• BIG2003 for supported executable members above a configured NLOC threshold;
• BIG2004 for supported executable members above a configured statement-count threshold;
• BIG2005 for supported executable members above a configured token-count threshold;
• BIG2006 for supported executable members above a configured source-declared parameter threshold;
• BIG2007 for supported executable members above a configured Cognitive Complexity threshold;
• BIG9000 as an opt-in execution probe.

Generated-code analysis is disabled and concurrent analyzer execution is enabled. Halstead metrics are currently internal analysis capability only; no public Halstead diagnostic ID or configuration key is exposed because the project has not adopted a defensible maintainability threshold for a single derived Halstead metric.

See the Analyzer Catalog for rule-level behavior.

Performance and package validation

The analyzer is designed for compiler/IDE execution and keeps hot paths free of network access, process execution, telemetry, and mandatory whole-solution scans.

Performance validation uses deterministic synthetic workloads and structural invariants rather than narrow machine-specific timing thresholds. The compiler ReportAnalyzer=true path is used to verify analyzer execution reporting.

Performance budgets are part of the analyzer contract. Source-method traversal defaults to call depth 5 and 32 uncached source-method expansions per root, with public hard maximums of 16 and 128. Recurrence solving remains bounded by supported recurrence shapes and fixed numerical limits for the restricted Akra-Bazzi solver. At budget boundaries, the analyzer keeps affected results conservative, normally Unknown.

CI treats deterministic structural checks as hard gates: bounded traversal, cache ownership, cancellation behavior, generated-code exclusion, package layout, and consumer compatibility. Elapsed time and compiler analyzer timing are informational trend signals unless repeated evidence shows a material regression. The detailed regression policy and local commands are documented in performance/README.md.

Package contract validation ensures that ComplexityAnalysis.Analyzers.dll is packed under analyzers/dotnet/cs/, not lib/, and that authoring dependencies do not become consumer runtime dependencies.

CI also validates package consumption with .NET 8, .NET 9, and .NET 10 SDK hosts. Each compatibility job restores and builds a temporary consumer using the real .nupkg, enables BIG9000 as a package-load probe, enables BIG1006 on a known quadratic method, rejects analyzer load failures, and checks that the package contributes analyzer assets rather than compile/runtime assets.

Why no Workspaces dependency

Microsoft.CodeAnalysis.Workspaces is intentionally absent. The project does not implement a CodeFixProvider, solution loading, whole-project workspace analysis, or other IDE workspace features that require that dependency.