Ontology Layer Defines:
  ObjectType: Project
  ObjectType: Dataset
  RelationType: Project --contains--> Dataset

ReBAC Permission Semantics:
  Project:proj1 --editor--> User:alice
  Project:proj1 --contains--> Dataset:ds1
  => User:alice has editor permission on Dataset:ds1 (via relationship inheritance)

// Relationship tuple definition
message RelationshipTuple {
  ObjectReference resource = 1;    // Resource object
  string relation = 2;            // Relation name
  SubjectReference subject = 3;    // Subject (user or userset)
}

message ObjectReference {
  string type = 1;     // Object type, e.g., "project", "dataset"
  string id = 2;       // Object ID
}

message SubjectReference {
  ObjectReference object = 1;      // Subject object
  string optional_relation = 2;    // Optional relation qualifier
}

(document:readme, viewer, project:alpha#member)

# Namespace configuration — similar to Zanzibar's namespace config
type_definitions:
  - type: "organization"
    relations:
      admin:
        description: "Organization administrator"
        directly_related_types:
          - type: "user"
      member:
        description: "Organization member"
        union:
          - directly_related: { type: "user" }
          - computed_relation: "admin"  # admin is also a member

  - type: "project"
    relations:
      parent_org:
        description: "Parent organization"
        directly_related_types:
          - type: "organization"
      admin:
        description: "Project administrator"
        union:
          - directly_related: { type: "user" }
          - tuple_to_userset:
              tupleset: "parent_org"
              computed_relation: "admin"  # org admin is also project admin
      editor:
        description: "Project editor"
        union:
          - directly_related: { type: "user" }
          - directly_related: { type: "team", relation: "member" }
          - computed_relation: "admin"  # admin is also editor
      viewer:
        description: "Project viewer"
        union:
          - directly_related: { type: "user" }
          - computed_relation: "editor"  # editor is also viewer

  - type: "dataset"
    relations:
      parent_project:
        description: "Parent project"
        directly_related_types:
          - type: "project"
      owner:
        description: "Dataset owner"
        directly_related: { type: "user" }
      editor:
        union:
          - directly_related: { type: "user" }
          - computed_relation: "owner"
          - tuple_to_userset:
              tupleset: "parent_project"
              computed_relation: "editor"
      viewer:
        union:
          - directly_related: { type: "user" }
          - computed_relation: "editor"
          - tuple_to_userset:
              tupleset: "parent_project"
              computed_relation: "viewer"

1. Direct Relation
   ┌─────────┐   viewer   ┌──────────┐
   │ User:bob │──────────>│ Doc:file1 │
   └─────────┘            └──────────┘

2. Computed Relation (Implied)
   Definition: viewer includes editor
   ┌───────────┐   editor   ┌──────────┐
   │ User:alice │──────────>│ Doc:file1 │
   └───────────┘            └──────────┘
   => alice automatically gains viewer permission

3. Tuple-to-Userset
   ┌──────────┐   parent   ┌──────────────┐
   │ Doc:file1 │──────────>│ Project:proj1 │
   └──────────┘            └──────────────┘
                                  │ editor
                                  ▼
                           ┌───────────┐
                           │ User:carol │
                           └───────────┘
   => carol inherits editor permission on file1 through proj1

┌─────────────────────────────────────────────────────────┐
│                  Tuple Store Layer                       │
├─────────────────────────────────────────────────────────┤
│                                                         │
│  ┌─────────────┐   ┌─────────────┐   ┌──────────────┐ │
│  │  Write Path  │   │  Read Path  │   │  Watch Path  │ │
│  │  (gRPC API)  │   │  (gRPC API) │   │ (Stream API) │ │
│  └──────┬──────┘   └──────┬──────┘   └──────┬───────┘ │
│         │                  │                  │         │
│  ┌──────▼──────────────────▼──────────────────▼───────┐ │
│  │              Changelog (WAL)                       │ │
│  │  - Zookie/Token per write for consistency          │ │
│  │  - Ordered sequence of tuple changes               │ │
│  └──────┬────────────────────────────────────────────┘ │
│         │                                               │
│  ┌──────▼────────────────────────────────────────────┐ │
│  │              Primary Store (PostgreSQL)            │ │
│  │  - relation_tuples table                          │ │
│  │  - Indexed: (resource_type, resource_id, relation)│ │
│  │  - Indexed: (subject_type, subject_id)            │ │
│  └───────────────────────────────────────────────────┘ │
│                                                         │
│  ┌───────────────────────────────────────────────────┐ │
│  │              Cache Layer (Redis)                   │ │
│  │  - Check result cache with Zookie invalidation    │ │
│  │  - Expand result cache                            │ │
│  └───────────────────────────────────────────────────┘ │
└─────────────────────────────────────────────────────────┘

-- Core relationship tuples table
CREATE TABLE relation_tuples (
    id              BIGSERIAL PRIMARY KEY,
    resource_type   VARCHAR(128) NOT NULL,
    resource_id     VARCHAR(256) NOT NULL,
    relation        VARCHAR(64)  NOT NULL,
    subject_type    VARCHAR(128) NOT NULL,
    subject_id      VARCHAR(256) NOT NULL,
    subject_relation VARCHAR(64),  -- NULL means direct user
    created_at      TIMESTAMP WITH TIME ZONE DEFAULT NOW(),
    deleted_at      TIMESTAMP WITH TIME ZONE,  -- Soft delete
    zookie          BIGINT NOT NULL,  -- Consistency token

    UNIQUE (resource_type, resource_id, relation,
            subject_type, subject_id, subject_relation)
);

-- High-frequency query indexes
CREATE INDEX idx_tuples_resource ON relation_tuples
    (resource_type, resource_id, relation)
    WHERE deleted_at IS NULL;

CREATE INDEX idx_tuples_subject ON relation_tuples
    (subject_type, subject_id)
    WHERE deleted_at IS NULL;

CREATE INDEX idx_tuples_zookie ON relation_tuples (zookie);

-- Changelog table (for Watch API and consistency)
CREATE TABLE changelog (
    zookie          BIGSERIAL PRIMARY KEY,
    operation       VARCHAR(16) NOT NULL,  -- TOUCH / DELETE
    resource_type   VARCHAR(128) NOT NULL,
    resource_id     VARCHAR(256) NOT NULL,
    relation        VARCHAR(64)  NOT NULL,
    subject_type    VARCHAR(128) NOT NULL,
    subject_id      VARCHAR(256) NOT NULL,
    subject_relation VARCHAR(64),
    timestamp       TIMESTAMP WITH TIME ZONE DEFAULT NOW()
);

Write Flow:
  1. Client writes tuple -> receives zookie Z1
  2. Subsequent Check requests carry zookie Z1
  3. Server ensures evaluation sees Z1 and all prior writes

Consistency Levels:
  - minimize_latency: Uses cache, may read stale data
  - at_least_as_fresh(zookie): At least as fresh as specified zookie
  - fully_consistent: Reads latest snapshot, slowest but safest

class ZookieManager:
    """Zookie consistency token manager"""

    def __init__(self, store: TupleStore):
        self._store = store
        self._current_zookie = AtomicCounter()

    def next_zookie(self) -> int:
        """Generate next globally incrementing zookie"""
        return self._current_zookie.increment()

    def snapshot_at(self, zookie: int) -> TupleSnapshot:
        """Get tuple snapshot at specified zookie"""
        return self._store.snapshot(zookie)

    def is_at_least_as_fresh(self, requested: int, current: int) -> bool:
        """Check if current snapshot satisfies freshness requirement"""
        return current >= requested

class ReBACheckEngine:
    """ReBAC permission check engine"""

    def __init__(self, store: TupleStore, type_system: TypeSystem):
        self._store = store
        self._type_system = type_system
        self._cache = CheckCache()

    async def check(
        self,
        resource: ObjectRef,
        permission: str,
        subject: SubjectRef,
        consistency: Consistency = Consistency.MINIMIZE_LATENCY,
    ) -> CheckResult:
        """
        Check if subject has the specified permission on resource.

        Algorithm:
        1. Get relation definition for the resource type
        2. Recursively expand based on derivation rules
        3. Search for subject reachability during expansion
        """
        cache_key = (resource, permission, subject)
        if cached := self._cache.get(cache_key, consistency):
            return cached

        type_def = self._type_system.get_type(resource.type)
        relation_def = type_def.get_relation(permission)

        result = await self._evaluate_rewrite(
            resource, relation_def.rewrite, subject,
            visited=set(), depth=0
        )

        self._cache.set(cache_key, result)
        return result

    async def _evaluate_rewrite(
        self,
        resource: ObjectRef,
        rewrite: RewriteRule,
        subject: SubjectRef,
        visited: set,
        depth: int,
    ) -> CheckResult:
        """Recursively evaluate rewrite rules"""
        if depth > MAX_DEPTH:
            raise MaxDepthExceededError()

        cycle_key = (resource, rewrite, subject)
        if cycle_key in visited:
            return CheckResult.DENIED  # Prevent cycles
        visited.add(cycle_key)

        match rewrite:
            case DirectRelation():
                return await self._check_direct(resource, rewrite.relation, subject)

            case ComputedRelation(relation=rel):
                # Permission implication: e.g., editor implies viewer
                rel_def = self._type_system.get_relation(resource.type, rel)
                return await self._evaluate_rewrite(
                    resource, rel_def.rewrite, subject, visited, depth + 1
                )

            case TupleToUserset(tupleset=ts, computed=comp):
                # Find all parent objects satisfying the tupleset relation
                parents = await self._store.query_tuples(
                    resource_type=resource.type,
                    resource_id=resource.id,
                    relation=ts,
                )
                for parent_tuple in parents:
                    parent_ref = ObjectRef(
                        type=parent_tuple.subject_type,
                        id=parent_tuple.subject_id
                    )
                    parent_type_def = self._type_system.get_type(parent_ref.type)
                    parent_rel_def = parent_type_def.get_relation(comp)
                    result = await self._evaluate_rewrite(
                        parent_ref, parent_rel_def.rewrite, subject,
                        visited, depth + 1
                    )
                    if result.allowed:
                        return result
                return CheckResult.DENIED

            case Union(children=children):
                # Any child rule allowing means allowed
                tasks = [
                    self._evaluate_rewrite(resource, child, subject, visited.copy(), depth + 1)
                    for child in children
                ]
                results = await asyncio.gather(*tasks)
                return CheckResult.ALLOWED if any(r.allowed for r in results) else CheckResult.DENIED

            case Intersection(children=children):
                # All child rules must allow
                tasks = [
                    self._evaluate_rewrite(resource, child, subject, visited.copy(), depth + 1)
                    for child in children
                ]
                results = await asyncio.gather(*tasks)
                return CheckResult.ALLOWED if all(r.allowed for r in results) else CheckResult.DENIED

            case Exclusion(base=base, subtract=sub):
                # base allows AND subtract does not allow
                base_result = await self._evaluate_rewrite(
                    resource, base, subject, visited.copy(), depth + 1
                )
                if not base_result.allowed:
                    return CheckResult.DENIED
                sub_result = await self._evaluate_rewrite(
                    resource, sub, subject, visited.copy(), depth + 1
                )
                return CheckResult.ALLOWED if not sub_result.allowed else CheckResult.DENIED

async def expand(
    self,
    resource: ObjectRef,
    relation: str,
) -> UsersetTree:
    """
    Expand the complete userset tree for a resource and relation.
    Returns a tree structure with leaf nodes being concrete users.
    """
    type_def = self._type_system.get_type(resource.type)
    rel_def = type_def.get_relation(relation)

    return await self._expand_rewrite(resource, rel_def.rewrite, visited=set())

async def _expand_rewrite(
    self,
    resource: ObjectRef,
    rewrite: RewriteRule,
    visited: set,
) -> UsersetTree:
    match rewrite:
        case DirectRelation():
            tuples = await self._store.query_tuples(
                resource_type=resource.type,
                resource_id=resource.id,
                relation=rewrite.relation,
            )
            leaf_users = []
            intermediate_nodes = []
            for t in tuples:
                if t.subject_relation:
                    child_tree = await self._expand_rewrite(
                        ObjectRef(t.subject_type, t.subject_id),
                        DirectRelation(t.subject_relation),
                        visited,
                    )
                    intermediate_nodes.append(child_tree)
                else:
                    leaf_users.append(SubjectRef(t.subject_type, t.subject_id))
            return UsersetTree(
                type="leaf" if not intermediate_nodes else "union",
                users=leaf_users,
                children=intermediate_nodes,
            )

        case Union(children=children):
            child_trees = []
            for child in children:
                tree = await self._expand_rewrite(resource, child, visited)
                child_trees.append(tree)
            return UsersetTree(type="union", children=child_trees)

class ParallelCheckOptimizer:
    """Parallel evaluation optimizer"""

    async def check_with_early_exit(
        self,
        resource: ObjectRef,
        union_rules: list[RewriteRule],
        subject: SubjectRef,
    ) -> CheckResult:
        """
        Use asyncio concurrency for Union rules,
        short-circuit exit on first ALLOWED result.
        """
        done_event = asyncio.Event()
        result_holder = {"result": CheckResult.DENIED}

        async def check_branch(rule: RewriteRule):
            r = await self._evaluate_rewrite(resource, rule, subject)
            if r.allowed:
                result_holder["result"] = CheckResult.ALLOWED
                done_event.set()

        tasks = [asyncio.create_task(check_branch(r)) for r in union_rules]

        wait_task = asyncio.create_task(done_event.wait())
        all_done = asyncio.gather(*tasks, return_exceptions=True)

        await asyncio.wait(
            [wait_task, all_done],
            return_when=asyncio.FIRST_COMPLETED,
        )

        for t in tasks:
            if not t.done():
                t.cancel()

        return result_holder["result"]

Organization: acme
    │ admin: [alice]
    │ member: [bob, charlie]
    │
    ├── Project: alpha
    │   │ parent_org: acme
    │   │ admin: [inherited from org:acme#admin -> alice]
    │   │ editor: [dave]
    │   │ viewer: [eve]
    │   │
    │   ├── Dataset: sales_2024
    │   │   parent_project: alpha
    │   │   owner: [frank]
    │   │   editor: [inherited from project:alpha#editor -> dave]
    │   │   viewer: [inherited from project:alpha#viewer -> eve]
    │   │
    │   └── Dataset: customer_info
    │       parent_project: alpha
    │       owner: [grace]
    │       editor: [inherited]
    │       viewer: [inherited]
    │
    └── Project: beta
        │ parent_org: acme
        │ admin: [inherited from org:acme#admin -> alice]
        │ editor: [heidi]

# Sensitive dataset: inherits project permissions but excludes contractors
type: "sensitive_dataset"
relations:
  parent_project:
    directly_related_types: [{ type: "project" }]
  blocked:
    directly_related_types: [{ type: "user" }]
  viewer:
    exclusion:
      base:
        tuple_to_userset:
          tupleset: "parent_project"
          computed_relation: "viewer"
      subtract:
        direct_relation: "blocked"

class ContextualTuple:
    """Context-aware relationship tuple"""

    resource: ObjectRef
    relation: str
    subject: SubjectRef
    condition: dict  # Condition expression

    def evaluate_condition(self, context: dict) -> bool:
        """Evaluate whether condition is satisfied"""
        for key, expected in self.condition.items():
            actual = context.get(key)
            if actual != expected:
                return False
        return True

# Example: editor permission only during business hours
contextual_tuple = ContextualTuple(
    resource=ObjectRef("project", "alpha"),
    relation="editor",
    subject=SubjectRef("user", "bob"),
    condition={"time_range": "business_hours", "network": "internal"},
)

Request Arrives
    │
    ▼
┌─────────────────────────────────┐
│ Layer 1: RBAC Coarse Filtering   │
│ - Check user role includes perm  │
│ - Fast reject on no role match   │
│ Result: ALLOW / DENY / CONTINUE  │
└──────────────┬──────────────────┘
               │ CONTINUE
               ▼
┌─────────────────────────────────┐
│ Layer 2: ABAC Attribute Eval     │
│ - Evaluate subject/resource/env  │
│ - Check data classification      │
│ Result: ALLOW / DENY / CONTINUE  │
└──────────────┬──────────────────┘
               │ CONTINUE
               ▼
┌─────────────────────────────────┐
│ Layer 3: ReBAC Graph Traversal   │
│ - Check direct and indirect rels │
│ - Handle inheritance, negation   │
│ Result: ALLOW / DENY             │
└─────────────────────────────────┘

class UnifiedPolicyEngine:
    """Unified policy engine: merges RBAC + ABAC + ReBAC"""

    async def authorize(self, request: AuthzRequest) -> AuthzDecision:
        # Phase 1: RBAC
        rbac_result = await self.rbac_engine.check(
            user=request.subject,
            permission=request.permission,
        )
        if rbac_result == Decision.EXPLICIT_DENY:
            return AuthzDecision.DENIED
        if rbac_result == Decision.EXPLICIT_ALLOW and not request.needs_fine_grained:
            return AuthzDecision.ALLOWED

        # Phase 2: ABAC
        abac_result = await self.abac_engine.evaluate(
            subject_attrs=request.subject_attributes,
            resource_attrs=request.resource_attributes,
            action=request.action,
            environment=request.environment,
        )
        if abac_result == Decision.EXPLICIT_DENY:
            return AuthzDecision.DENIED

        # Phase 3: ReBAC
        rebac_result = await self.rebac_engine.check(
            resource=request.resource,
            permission=request.permission,
            subject=request.subject_ref,
        )

        # Merge decisions
        return self._merge_decisions(rbac_result, abac_result, rebac_result)

    def _merge_decisions(self, rbac, abac, rebac) -> AuthzDecision:
        """
        Merge strategy:
        - Any EXPLICIT_DENY -> DENIED (deny takes precedence)
        - ReBAC ALLOW and ABAC no deny -> ALLOWED
        - RBAC ALLOW and ABAC ALLOW -> ALLOWED
        - Default -> DENIED (default deny)
        """
        if any(d == Decision.EXPLICIT_DENY for d in [rbac, abac, rebac]):
            return AuthzDecision.DENIED
        if rebac.allowed and abac != Decision.EXPLICIT_DENY:
            return AuthzDecision.ALLOWED
        if rbac == Decision.EXPLICIT_ALLOW and abac == Decision.EXPLICIT_ALLOW:
            return AuthzDecision.ALLOWED
        return AuthzDecision.DENIED

class ReBACheckCache:
    """Layered caching system"""

    def __init__(self):
        self.l1_local = LRUCache(max_size=10000)     # In-process cache
        self.l2_redis = RedisCache(ttl_seconds=300)   # Distributed cache

    def get(self, key: CheckCacheKey, consistency: Consistency) -> Optional[CheckResult]:
        if consistency == Consistency.FULLY_CONSISTENT:
            return None  # Skip cache

        if consistency == Consistency.AT_LEAST_AS_FRESH:
            cached = self.l1_local.get(key)
            if cached and cached.zookie >= consistency.min_zookie:
                return cached.result
            cached = self.l2_redis.get(key)
            if cached and cached.zookie >= consistency.min_zookie:
                self.l1_local.set(key, cached)
                return cached.result
            return None

        # minimize_latency: return cache directly
        if result := self.l1_local.get(key):
            return result.result
        if result := self.l2_redis.get(key):
            self.l1_local.set(key, result)
            return result.result
        return None

    def invalidate_for_resource(self, resource: ObjectRef):
        """Invalidate cache when resource relations change"""
        pattern = f"check:{resource.type}:{resource.id}:*"
        self.l1_local.invalidate_pattern(pattern)
        self.l2_redis.invalidate_pattern(pattern)

# Global configuration
MAX_TRAVERSAL_DEPTH = 15        # Maximum recursion depth
MAX_CONCURRENT_BRANCHES = 50    # Maximum concurrent branches
CHECK_TIMEOUT_MS = 500          # Single Check timeout

class DepthLimiter:
    """Depth limiter to prevent infinite recursion"""

    def __init__(self, max_depth: int = MAX_TRAVERSAL_DEPTH):
        self.max_depth = max_depth
        self._metrics = MetricsCollector()

    def check_depth(self, current_depth: int, context: str):
        if current_depth > self.max_depth:
            self._metrics.increment("rebac.depth_exceeded", tags={"context": context})
            raise MaxDepthExceededError(
                f"ReBAC traversal exceeded max depth {self.max_depth} at {context}"
            )

class BatchCheckOptimizer:
    """Batch permission check optimization"""

    async def batch_check(
        self,
        checks: list[CheckRequest],
    ) -> list[CheckResult]:
        """
        Batch check optimization strategies:
        1. Deduplication: same (resource, permission, subject) checked once
        2. Prefetching: bulk load related tuples into cache
        3. Shared traversal: reuse intermediate traversal results
        """
        # Deduplicate
        unique_checks = {c.cache_key: c for c in checks}

        # Prefetch tuples for all involved resources
        resources = {(c.resource.type, c.resource.id) for c in unique_checks.values()}
        await self._prefetch_tuples(resources)

        # Concurrent execution of deduplicated checks
        tasks = {
            key: asyncio.create_task(self.engine.check(c.resource, c.permission, c.subject))
            for key, c in unique_checks.items()
        }
        results = {key: await task for key, task in tasks.items()}

        # Map back to original request order
        return [results[c.cache_key] for c in checks]

    async def _prefetch_tuples(self, resources: set[tuple[str, str]]):
        """Batch prefetch tuples into cache"""
        tasks = [
            self._store.prefetch(resource_type=rt, resource_id=ri)
            for rt, ri in resources
        ]
        await asyncio.gather(*tasks)

service ReBAAuthorizationService {
    // Permission check
    rpc Check(CheckRequest) returns (CheckResponse);
    rpc BatchCheck(BatchCheckRequest) returns (BatchCheckResponse);

    // Relationship expansion
    rpc Expand(ExpandRequest) returns (ExpandResponse);

    // Relationship management
    rpc WriteTuples(WriteTuplesRequest) returns (WriteTuplesResponse);
    rpc DeleteTuples(DeleteTuplesRequest) returns (DeleteTuplesResponse);
    rpc ReadTuples(ReadTuplesRequest) returns (ReadTuplesResponse);

    // Change watching
    rpc Watch(WatchRequest) returns (stream WatchResponse);

    // Reverse queries: what resources can a user access
    rpc LookupResources(LookupResourcesRequest) returns (stream LookupResourcesResponse);
    rpc LookupSubjects(LookupSubjectsRequest) returns (stream LookupSubjectsResponse);
}

message CheckRequest {
    ObjectReference resource = 1;
    string permission = 2;
    SubjectReference subject = 3;
    Consistency consistency = 4;
    repeated RelationshipTuple contextual_tuples = 5;
}

message CheckResponse {
    bool allowed = 1;
    int64 checked_at_zookie = 2;
    DebugInfo debug = 3;  // Optional debug info
}

async def lookup_resources(
    self,
    resource_type: str,
    permission: str,
    subject: SubjectRef,
) -> AsyncIterator[ObjectRef]:
    """
    Find which resources of resource_type the subject has permission on.
    This is the reverse of Check, used to list accessible resources.
    """
    # Strategy 1: Forward traversal from subject
    direct_tuples = await self._store.query_by_subject(
        subject_type=subject.type,
        subject_id=subject.id,
    )

    seen = set()
    for tuple in direct_tuples:
        if tuple.resource_type == resource_type:
            if await self._relation_implies(
                resource_type, tuple.relation, permission
            ):
                if tuple.resource_id not in seen:
                    seen.add(tuple.resource_id)
                    yield ObjectRef(resource_type, tuple.resource_id)

    # Strategy 2: Consider indirect relations through intermediate objects
    for tuple in direct_tuples:
        children = await self._store.query_tuples(
            subject_type=tuple.resource_type,
            subject_id=tuple.resource_id,
        )
        for child in children:
            if child.resource_type == resource_type and child.resource_id not in seen:
                result = await self.check(
                    ObjectRef(child.resource_type, child.resource_id),
                    permission,
                    subject,
                )
                if result.allowed:
                    seen.add(child.resource_id)
                    yield ObjectRef(child.resource_type, child.resource_id)

class ReBAGraphVisualizer:
    """Relationship graph visualization tool for debugging permission inheritance"""

    async def visualize_permissions(
        self,
        resource: ObjectRef,
        max_depth: int = 5,
    ) -> str:
        """Generate Mermaid-format relationship graph"""
        lines = ["graph TD"]
        visited = set()

        async def traverse(obj: ObjectRef, depth: int):
            if depth > max_depth or obj in visited:
                return
            visited.add(obj)
            node_id = f"{obj.type}_{obj.id}"

            tuples = await self._store.query_tuples(
                resource_type=obj.type,
                resource_id=obj.id,
            )
            for t in tuples:
                subject_id = f"{t.subject_type}_{t.subject_id}"
                label = t.relation
                if t.subject_relation:
                    label += f" (via #{t.subject_relation})"
                lines.append(f"    {subject_id} -->|{label}| {node_id}")

                if t.subject_type != "user":
                    await traverse(
                        ObjectRef(t.subject_type, t.subject_id),
                        depth + 1,
                    )

        await traverse(resource, 0)
        return "\n".join(lines)

class PermissionExplainer:
    """Permission decision explainer"""

    async def explain(
        self,
        resource: ObjectRef,
        permission: str,
        subject: SubjectRef,
    ) -> ExplanationTree:
        """
        Explain why subject does/does not have permission on resource.
        Returns a complete decision tree with evaluation results at each step.
        """
        root = ExplanationNode(
            description=f"Check: {subject} -> {permission} -> {resource}",
        )

        result = await self._check_with_explanation(
            resource, permission, subject, root
        )

        root.result = result
        return ExplanationTree(root=root)

┌─────────────────────────────────────────────┐
│              Region A (Primary)             │
│  ┌────────────┐     ┌────────────────────┐  │
│  │ ReBAC API  │────>│ PostgreSQL Primary │  │
│  │ (gRPC)     │     │ (Write + Read)     │  │
│  └────────────┘     └────────────────────┘  │
│        │                     │               │
│        │              WAL Replication         │
│        │                     │               │
└────────│─────────────────────│───────────────┘
         │                     │
         │              ┌──────▼───────────────┐
         │              │   Region B (Replica)  │
         │              │  ┌────────────────┐  │
         │              │  │ PostgreSQL     │  │
         │              │  │ (Read Replica) │  │
         │              │  └────────────────┘  │
         │              │  ┌────────────────┐  │
         │              │  │ ReBAC API      │  │
         │              │  │ (Read-only)    │  │
         │              │  └────────────────┘  │
         │              └──────────────────────┘

REBAC_METRICS = {
    "rebac_check_total": Counter("Total check count"),
    "rebac_check_latency": Histogram("Check latency", buckets=[1, 5, 10, 50, 100, 500]),
    "rebac_check_allowed": Counter("Allowed count"),
    "rebac_check_denied": Counter("Denied count"),
    "rebac_traversal_depth": Histogram("Traversal depth", buckets=[1, 2, 3, 5, 8, 15]),
    "rebac_cache_hit_rate": Gauge("Cache hit rate"),
    "rebac_tuple_count": Gauge("Total tuple count"),
    "rebac_expand_latency": Histogram("Expand latency"),
    "rebac_batch_size": Histogram("Batch check size"),
}