symfonic.memory.subtree

subtree

Descendant-sweep predicates: the erase direction of the scope hierarchy.

Deliberately a separate module from :mod:symfonic.memory.scope_isolation, because it answers the opposite question and is allowed the one construction that module forbids.

• Isolation (read). A query at path P sees a memory at path Q iff Q is a prefix of P — the query's own ancestors. Enforced by exact set membership over ancestor_prefix_paths(). A LIKE 'P%' there would let a query at acme read acmecorp's rows, which is the §5.b R2 CRITICAL class.
• Erasure (write). MemoryLifecyclePort.forget(scope) must reach a scope and its descendants, which no read on GraphBackend can enumerate. The v0 set is unbounded — a tenant may hold any number of sessions nobody listed — so the backend expresses it as a pattern.

The pattern is safe here, and it is safe for exactly one reason: the delimiter is appended before the wildcard. org\x1facme sweeps org\x1facme itself and everything under org\x1facme\x1f…; org\x1facmecorp does not begin with org\x1facme\x1f, so the false-prefix pair the isolation filter exists to refuse is refused here too. Drop the delimiter and this becomes the same leak with a delete on the end of it. Native v1 wire keys already end at a complete level with "/". In-memory native sweeps validate each stored key before comparing that boundary. SQL and Mongo native sweeps fail closed until those backends can validate canonical stored keys; a prefix or grammar regex cannot reject every malformed UTF-8 or forbidden NUL field. Native reads remain exact ancestor membership and exclude legacy rows.

Two hazards the naive spelling misses, and why the helpers exist rather than each backend writing its own predicate:

• Wildcard metacharacters in an id. LIKE reads _ as "any one character" and % as "any run", and an adopter id may legitimately contain both — a tenant acme_corp would otherwise sweep acmeXcorp. The SQL pattern is therefore escaped and the Mongo one goes through re.escape. ScopeLevel rejects the delimiter in an id, so the boundary cannot be forged; nothing rejects an underscore.
• Pre-v8.0 rows. A row written before scope_path existed dual-reads as the 1-level tenant root (design §6.b). Such a row is in the subtree of the tenant root and of nothing narrower, so the NULL branch is included only when the sweep is rooted at the tenant. A privacy deletion that skipped those rows would report success having erased nothing a legacy write produced.

is_in_subtree

is_in_subtree(stored_path: str | None, root_path: str) -> bool

Whether stored_path is root_path or lies beneath it.

The delimiter-terminated comparison, stated once. startswith(root_path) without it would call acmecorp a descendant of acme. Native v1 roots already terminate a complete level; malformed native roots refuse. Stored paths must be canonical storage keys; None is outside every subtree.

Source code in src/symfonic/memory/subtree.py

def is_in_subtree(stored_path: str | None, root_path: str) -> bool:
    """Whether ``stored_path`` is ``root_path`` or lies beneath it.

    The delimiter-terminated comparison, stated once. ``startswith(root_path)``
    without it would call ``acmecorp`` a descendant of ``acme``. Native v1
    roots already terminate a complete level; malformed native roots refuse.
    Stored paths must be canonical storage keys; None is outside every subtree.
    """
    prefix = subtree_prefix(root_path)
    if stored_path is None:
        return False
    if SCOPE_PATH_DELIMITER not in root_path:
        from symfonic.capabilities.memory.errors import MemoryContractError
        from symfonic.capabilities.memory.storage_key import StorageScopeKey

        try:
            StorageScopeKey.parse(stored_path)
        except MemoryContractError:
            return False
    return stored_path == root_path or stored_path.startswith(prefix)

mongo_subtree_filter

mongo_subtree_filter(scope: StorageScope, field: str = SCOPE_PATH_KEY) -> dict

Build the Mongo descendant-sweep filter for a scope_path field.

An anchored $regex over a re.escape-d literal, which is the Mongo spelling of the same delimiter-terminated prefix for v0. Native sweeps refuse explicitly until stored keys can be validated by the backend.

Source code in src/symfonic/memory/subtree.py

def mongo_subtree_filter(scope: StorageScope, field: str = SCOPE_PATH_KEY) -> dict:
    """Build the Mongo descendant-sweep filter for a scope_path field.

    An anchored ``$regex`` over a ``re.escape``-d literal, which is the Mongo
    spelling of the same delimiter-terminated prefix for v0. Native sweeps
    refuse explicitly until stored keys can be validated by the backend.
    """
    root = scope.scope_path
    if _is_native_scope(scope):
        from symfonic.capabilities.memory.errors import MemoryContractError

        subtree_prefix(root)
        raise MemoryContractError(
            "native database subtree sweep requires canonical backend validation"
        )
    pattern = "^" + re.escape(subtree_prefix(root))
    branches: list[dict] = [
        {field: root},
        {field: {"$regex": pattern}},
    ]
    if sweeps_legacy_rows(scope):
        branches += [{field: {"$exists": False}}, {field: None}]
    return {"$or": branches}

sql_subtree_condition

sql_subtree_condition(scope: StorageScope, column: str, next_param_index: int) -> tuple[str, list[object]]

Build the SQL descendant-sweep predicate for a materialised column.

Returns (sql_fragment, params). V0 consumes two placeholders from next_param_index (asyncpg $N style): the exact root path, and the escaped complete-level subtree prefix followed by '%'. Explicit C collation keeps equality and LIKE byte-exact under nondeterministic column collations. Native sweeps refuse explicitly: SQL cannot prove stored-key canonicality from this prefix alone, and a no-op could look like erasure.

The IS NULL branch is appended, without a placeholder, only when :func:sweeps_legacy_rows holds — see the module docstring.

Source code in src/symfonic/memory/subtree.py

def sql_subtree_condition(
    scope: StorageScope,
    column: str,
    next_param_index: int,
) -> tuple[str, list[object]]:
    """Build the SQL descendant-sweep predicate for a materialised column.

    Returns ``(sql_fragment, params)``. V0 consumes two placeholders from
    ``next_param_index`` (asyncpg ``$N`` style): the exact root path, and
    the escaped complete-level subtree prefix followed by ``'%'``. Explicit C
    collation keeps equality and LIKE byte-exact under nondeterministic column
    collations. Native sweeps refuse explicitly: SQL cannot prove stored-key
    canonicality from this prefix alone, and a no-op could look like erasure.

    The ``IS NULL`` branch is appended, without a placeholder, only when
    :func:`sweeps_legacy_rows` holds — see the module docstring.
    """
    root = scope.scope_path
    if _is_native_scope(scope):
        from symfonic.capabilities.memory.errors import MemoryContractError

        subtree_prefix(root)
        raise MemoryContractError(
            "native database subtree sweep requires canonical backend validation"
        )
    root_idx = next_param_index
    pattern_idx = next_param_index + 1
    pattern = _escape_like(subtree_prefix(root)) + "%"
    fragment = (
        f"({column} COLLATE \"C\" = ${root_idx} "
        f"OR {column} COLLATE \"C\" LIKE ${pattern_idx} ESCAPE {_LIKE_ESCAPE_SQL}"
    )
    if sweeps_legacy_rows(scope):
        fragment += f" OR {column} IS NULL"
    return fragment + ")", [root, pattern]

subtree_prefix

subtree_prefix(root_path: str) -> str

Choose a complete boundary by wire grammar, never by an ID prefix.

Every valid v0 core path contains US, even at its root. A legacy kind may spell the native header, so testing that header alone would misclassify it. Otherwise require a canonical v1 key; malformed native roots fail closed. Callers must validate stored native keys before using this prefix.

Source code in src/symfonic/memory/subtree.py

def subtree_prefix(root_path: str) -> str:
    """Choose a complete boundary by wire grammar, never by an ID prefix.

    Every valid v0 core path contains US, even at its root. A legacy kind may
    spell the native header, so testing that header alone would misclassify it.
    Otherwise require a canonical v1 key; malformed native roots fail closed.
    Callers must validate stored native keys before using this prefix.
    """
    if SCOPE_PATH_DELIMITER in root_path:
        return root_path + SCOPE_PATH_DELIMITER
    from symfonic.capabilities.memory.storage_key import StorageScopeKey

    return StorageScopeKey.parse(root_path).subtree_prefix

sweeps_legacy_rows

sweeps_legacy_rows(scope: StorageScope) -> bool

Whether a sweep rooted at scope must also take pre-v8.0 rows.

True only at the 1-level tenant root, because that is the path a row with no stored scope_path dual-reads as. Every narrower sweep must leave them alone: they were tenant-global, and a session-scoped forget that deleted them would erase memories the session never owned.

Source code in src/symfonic/memory/subtree.py

def sweeps_legacy_rows(scope: StorageScope) -> bool:
    """Whether a sweep rooted at ``scope`` must also take pre-v8.0 rows.

    True only at the 1-level tenant root, because that is the path a row with
    no stored ``scope_path`` dual-reads as. Every narrower sweep must leave
    them alone: they were tenant-global, and a session-scoped forget that
    deleted them would erase memories the session never owned.
    """
    return (not _is_native_scope(scope)
            and scope.scope_path == legacy_scope_path(scope.tenant_id))