Statifier.HierarchyCache (statifier v1.9.0)

Pre-computed hierarchy information for O(1) runtime lookups.

This module provides caching for expensive hierarchy operations that are frequently called during state machine execution. By pre-computing hierarchy relationships during document validation, we can achieve significant performance improvements for complex documents with deep state hierarchies.

Performance Benefits

descendant_of?/3: O(depth) → O(1)
get_ancestor_path/2: O(depth) → O(1)
compute_lcca/3: O(depth₁ + depth₂) → O(1)
get_parallel_ancestors/2: O(depth) → O(1)

Memory Trade-offs

Cache size is approximately O(n²) for LCCA matrix and O(n) for other caches, where n is the number of states. Typical memory overhead is 1.5-2x the original document size, with 5-15x performance improvements for hierarchy operations.

Usage

The cache is built automatically during document validation and used transparently by StateHierarchy functions. Manual cache building is also supported:

cache = HierarchyCache.build(document)
cached_document = %{document | hierarchy_cache: cache}

Summary

Types

t()

Pre-computed hierarchy cache containing all hierarchy relationships.

Functions

build(document)

Build complete hierarchy cache for a document.

get_stats(cache)

Get cache statistics and performance information.

validate_cache(cache, document)

Validate cache consistency against document structure.

Types

t()

@type t() :: %Statifier.HierarchyCache{
  ancestor_paths: %{required(String.t()) => [String.t()]},
  build_time: non_neg_integer() | nil,
  descendant_sets: %{required(String.t()) => MapSet.t(String.t())},
  lcca_matrix: %{
    required(String.t() | {String.t(), String.t()}) => String.t() | nil
  },
  memory_usage: non_neg_integer(),
  parallel_ancestors: %{required(String.t()) => [String.t()]},
  parallel_regions: %{
    required(String.t()) => %{required(String.t()) => [String.t()]}
  },
  state_count: non_neg_integer()
}

Pre-computed hierarchy cache containing all hierarchy relationships.

Functions

build(document)

@spec build(Statifier.Document.t()) :: t()

Build complete hierarchy cache for a document.

Performs comprehensive analysis of document hierarchy to pre-compute all relationships needed for O(1) runtime lookups.

Performance Characteristics

Time complexity: O(n²) for LCCA matrix, O(n log n) typical
Space complexity: O(n²) worst case for LCCA matrix
Build time: Typically 10-20% of total validation time

Example

iex> cache = HierarchyCache.build(document)
iex> cache.state_count
15
iex> Map.has_key?(cache.ancestor_paths, "leaf1")
true

get_stats(cache)

@spec get_stats(t()) :: %{
  state_count: non_neg_integer(),
  build_time_ms: float(),
  memory_usage_kb: float(),
  lcca_entries: non_neg_integer(),
  parallel_regions: non_neg_integer()
}

Get cache statistics and performance information.

Returns detailed information about cache size, memory usage, and build time for monitoring and optimization.

Example

iex> HierarchyCache.get_stats(cache)
%{
  state_count: 15,
  build_time_ms: 2.5,
  memory_usage_kb: 12.3,
  cache_ratio: 1.8
}

validate_cache(cache, document)

@spec validate_cache(t(), Statifier.Document.t()) :: :ok | {:error, [String.t()]}

Validate cache consistency against document structure.

Verifies that cached data matches actual document hierarchy. Used for debugging and integrity checking.

Example

iex> HierarchyCache.validate_cache(cache, document)
:ok