# kdlquery

> A pure Python KDL 2.0 parser with a CSS3-like selector API.

## Overview

kdlquery provides five main capabilities:

1. **Two-tier lexer, `TreeBuilder` seam & lossless CST parser** (`kdlquery.parser`, `kdlquery.builder`) — Compiled regex token scanner (`KDLLexer.tokenize_raw()` / `tokenize()`) + recursive-descent parser driving a pluggable `TreeBuilder` protocol (`AstBuilder` for single-pass direct `KdlDocument` construction, `CstBuilder` for full lossless `CSTDocument`, and `_NullBuilder` for zero-allocation `/-` slashdash skipping) with deferred binary-searched line-starts position tables (`offset_to_position`). Conforms to the KDL 2.0 spec.
2. **Slotted mutable node tree** (`kdlquery.document`, `kdlquery.reader`) — `KdlDocument` and `KdlNode` (`@dataclass(slots=True)`) carry `parent` and `document` back-references wired in-flight. Containers (`nodes`, `args`, `properties`, `children`) are mutable (`list` / `dict`) to support programmatic tree building and editing, with automatic primitive-to-`KdlValue` coercion.
3. **Reader API** (`kdlquery.reader`) — Walk a raw KDL `str`, `KdlDocument`, or `CSTDocument` and transform it into arbitrary Python objects via the `Reader` abstract class. Includes `Walker`, `WalkContext`, `ReadDiagnostic`, `DiagnosticCollector`, `Severity`, and `parse_into()`. `DictReader` (`kdlquery.dict_reader`) produces nested dicts.
4. **Selector engine** (`kdlquery.selector`) — CSS3-like selectors for querying nodes by name, type annotation, properties, arguments, combinators, and pseudo-classes (`:has()` with multi-step descendant/child/sibling chains, `:nth-child(odd|even|An+B|-n+B)`, `:not()`, `:first-child`, `:last-child`, `:only-child`, `:empty`, `:root`). Supports signed numbers (`-5`, `-0.5`, `+5`) and KDL 2.0 keyword literals (`#true`, `#false`, `#null`, `#inf`, `#-inf`, `#nan`). Works on both `KdlDocument` (full tree) and `KdlNode` (children subtree only). Lexer → parser → matcher pipeline with LRU-cached selector parsing and type-annotation normalization. `MatchContext` Protocol decouples the matcher from the document.
5. **Regex-accelerated serializer** (`kdlquery.serializer`) — Emit KDL 2.0 text from any `KdlDocument` / `KdlNode` / `KdlValue` via their `to_kdl()` methods. Spec-compliant with compiled regex fast-paths: bare identifier detection (§3.10), quoted string escapes (`\\ \" \n \r \t \b \f \u{XXXX}`), multi-line dedent/reindent, `#true`/`#false`/`#null`/`#inf`/`#-inf`/`#nan` keyword literals, and type annotations.

## Quick start

```python
from kdlquery import parse

doc = parse('''
app "my-service" version="1.0.0" {
    server "primary" port=8080 tls=#true
    server "replica" port=8081 tls=#false
}
''')

doc.select("server[tls=#true]")    # → [server "primary"]
doc.select_one("app")              # → app node
doc.parent_of(doc.nodes[0].children[0])  # → app node

# Navigation directly on nodes
app = doc.nodes[0]
app.children[0].parent is app      # True
app.children[0].document is doc    # True
app.children[0].depth()            # 1
app.children[0].root is app        # True

# Parent queries
host = doc.select_one("host")
host.parents()                     # [server, app]
host.closest("server")             # server node
host.matches("host")               # True

# Node selectors — scoped to children subtree
app.select("server > host")        # → [host "localhost", host "127.0.0.1"]
app.select("*:root")               # → [] (no root concept in subtree)

# Mutation + serialization (primitives auto-wrapped into KdlValue)
from kdlquery import KdlNode
app.add_child(KdlNode.create("footer", args=[True], properties={"port": 8080}))
app.set_prop("migrated", True)
app.set_prop("port", 8080, type_annotation="(u16)")
app.add_arg("v2", type_annotation="(tag)")
doc.to_kdl()                       # → KDL 2.0 text with trailing newline
app.to_kdl(indent_str="\t")        # → custom indent
```

## Project structure

```
kdlquery/
  __init__.py      — Public API: parse(), parse_into(), all major types (__all__)
  types.py         — Token, RawToken, TokenType, CSTDocument, CSTNode, CSTValue, CSTEntry, CSTArgEntry, CSTPropEntry, CSTTypeAnnotation, CSTIdentifier, Span, Position, KDLParseError, PARSE_ERROR_CODES
  builder.py       — TreeBuilder protocol, AstBuilder (direct KdlDocument), CstBuilder (lossless CSTDocument), _CstNodeFrame, _NullBuilder
  parser.py        — KDLLexer (tokenize_raw / tokenize), KDL2CSTParser, _Parser, offset_to_position, escape/multiline string decoding
  document.py      — KdlDocument (slots=True): from_cst(), select(), select_one(), parent_of(), depth_of(), index_of(), siblings_of(), iter_nodes(), mutation (add_node/insert_node/remove_node), to_kdl()
  reader.py        — KdlNode (mutable, slots=True, parent/document refs, mutators, create(), from_cst(), to_kdl()), KdlValue (frozen, slots=True, create()/keyword()/from_cst(), to_kdl()), _Keyword sentinel, Reader ABC, Walker, WalkContext, ReadDiagnostic, DiagnosticCollector, Severity, parse_into()
  serializer.py    — value_to_kdl(), node_to_kdl(), doc_to_kdl(): KDL 2.0 spec-compliant serialization with compiled regex fast-paths for bare-ident detection, string escaping, and multiline reindent
  dict_reader.py   — DictReader: KdlNode tree → list of nested dicts
  selector.py      — SelectorLexer, SelectorParser, SelectorMatcher, MatchContext Protocol, _SubtreeContext, _SingleNodeContext + slotted AST dataclasses
tests/
  test_kdl_parser.py
  test_tree_builder.py
  test_selector.py
  test_reader.py
  test_navigation.py
  test_write.py
  test_benchmark.py
```

## Dependencies

- Python 3.10+, zero external dependencies.
- Dev: pytest, mypy, ruff, pytest-cov.

## Public API surface

### Entry points

- `parse(source: str) -> KdlDocument` — Parse KDL 2.0 string directly into a queryable `KdlDocument` tree in a single pass via `KDLLexer.tokenize_raw()` and `AstBuilder` (skips intermediate CST node and unused span allocations).
- `parse_into(document: CSTDocument | KdlDocument | str, reader: Reader[T_node, R], *, strict: bool = False) -> tuple[R, list[ReadDiagnostic]]` — Walk a KDL source `str`, `KdlDocument`, or `CSTDocument` through a `Reader` (automatically wires `node.document` across the tree).

### Key types

- **KdlDocument** (`@dataclass(slots=True)`) — Owns the node tree (`nodes: list[KdlNode]`, `span: Span | None`). Factory: `from_cst(doc: CSTDocument) -> KdlDocument`. Queries & navigation: `select(selector)`, `select_one(selector)`, `parent_of(node)`, `depth_of(node)`, `index_of(node)`, `siblings_of(node)`, `iter_nodes()`. Mutation: `add_node(node)`, `insert_node(index, node)`, `remove_node(index) -> KdlNode`. Serialization: `to_kdl(indent_str="    ") -> str` (trailing newline; empty doc → `""`).
- **KdlNode** (`@dataclass(slots=True)`) — Mutable node with `name`, `type_annotation`, `args` (`list[KdlValue]`), `properties` (`dict[str, KdlValue]`), `children` (`list[KdlNode]`), `span`, `parent`. Methods:
  - Value access: `get_arg(i, default=None)`, `get_prop(k, default=None)`, `has_prop(k)`, `iter_args()`, `iter_props()`
  - Factories & Mutation: `create(name, *, args=None, properties=None, children=None, type_annotation=None) -> KdlNode` (`args` and `properties` accept `KdlValue` or raw Python primitives), `from_cst(node: CSTNode, parent=None) -> KdlNode`, `add_child(child)`, `insert_child(i, child)`, `remove_child(i) -> KdlNode` (clears `parent` and recursively clears `document` on the removed node and all descendants), `add_arg(value, *, type_annotation=None)`, `set_prop(k, value, *, type_annotation=None)` (accepts `KdlValue` or raw Python primitives), `remove_prop(k) -> KdlValue | None`
  - Selector queries: `select(selector)`, `select_one(selector)` — scoped to descendants, cannot access parent or root nodes.
  - Navigation (DOM-like): `root` (property), `document` (property), `depth()`, `index()`, `siblings()`, `iter_descendants()`, `parents()`, `matches(selector)`, `closest(selector)`
  - Serialization: `to_kdl(*, indent=0, indent_str="    ", force_children_block=False) -> str`
- **KdlValue** (`@dataclass(frozen=True, slots=True)`) — Immutable typed value with `value`, `span`, `type_annotation`. Factories: `create(value, type_annotation=None)` (Python primitive → inferred KDL literal), `keyword(raw, type_annotation=None)` (raw passthrough wrapped in `_Keyword` sentinel), `from_cst(val: CSTValue) -> KdlValue`. Serialization: `to_kdl(*, indent=0, indent_str="    ") -> str`.
- **Reader[T_node, R]** — ABC with `on_node(node, ctx)`, `error_node(node, message, ctx)`, `finalize(nodes, diagnostics)`.
- **Walker[T_node]** — Tree walker with `walk()`, `walk_children()`, and `walk_document(document: CSTDocument | KdlDocument | str)`.
- **WalkContext[T_node]** (`@dataclass(slots=True)`) — Passed to `Reader.on_node`: attributes `node`, `parent`, `index`, `depth`; methods `walk_children() -> list[T_node]`, `error(message, *, span=None, hint="", code="", label=None, notes=None)`, `warning(message, *, span=None, hint="", code="", label=None, notes=None)`, `push(segment)`, `pop()`.
- **ReadDiagnostic**, **DiagnosticCollector**, **Severity** — Structured diagnostics (`Severity.ERROR`, `Severity.WARNING`) collected during `Reader` traversal.
- **DictReader** — Built-in reader producing `Node` TypedDicts.
- **SelectorError** — Raised on invalid selector syntax.

### Builder & CST types (low-level)

- `TreeBuilder[T_doc]` (Protocol), `AstBuilder` (produces `KdlDocument`), `CstBuilder` (produces `CSTDocument`)
- `KDL2CSTParser().parse(source) -> CSTDocument`
- `KDLLexer(source).tokenize_raw() -> list[RawToken]` (fast offset-only tokens) and `KDLLexer(source).tokenize() -> list[Token]` (tokens with full `Span`)
- `offset_to_position(offset: int, line_starts: list[int]) -> Position`
- `CSTDocument`, `CSTNode`, `CSTValue`, `CSTEntry`, `CSTArgEntry`, `CSTPropEntry`, `CSTTypeAnnotation`, `CSTIdentifier`, `Token`, `RawToken`, `TokenType`, `Span`, `Position`

## Selector syntax

```
# Node
name                    by bare identifier
"name" or 'name'        quoted node name (handles >, +, ~, ,, :, spaces)
\>name or a\>b          backslash-escaped identifier (CSS-style)
*                       any node
(type)                  by type annotation
("type") or (t\:ype)    quoted or escaped type annotation
(type)name              type annotation + name

# Property filters
[key]                   exists
["key"] or ['key']      quoted property key (handles ., :, >, spaces)
[key\.name]             backslash-escaped property key
["0"]                   property with string key "0" (distinguished from arg 0)
[key=val]               equals (strings, signed int/float like -5/-0.5/+5, #true, #false, #null, #inf, #-inf, #nan)
[key^=val]              starts with
[key$=val]              ends with
[key~=val]              contains
[(type)key]             property with type-annotated value
[("type")key=val]       type-annotated (quoted/escaped type) + value match

# Argument filters
[N]                     positional argument at index N exists (unquoted integer)
[N=val]                 positional argument at index N equals val (supports negative numbers & KDL 2.0 literals)
[N^=val]                starts with
[N$=val]                ends with
[N~=val]                contains
[(type)N]               positional argument with type annotation
[("type")N=val]         positional argument with quoted/escaped type annotation
[*=val]                 any positional argument equals val

# Combinators
A B                     descendant
A > B                   direct child
A + B                   adjacent sibling
A ~ B                   general sibling
A, B                    union (deduplicated)

# Pseudo-classes
:root
:first-child
:last-child
:nth-child(n)
:nth-child(odd)
:nth-child(even)
:nth-child(2n)
:nth-child(2n+1)
:nth-child(-n+3)
:only-child
:empty
:not(selector)
:has(selector)          descendant (supports multi-step chains like a > b, strictly bounded to subtree)
:has(> selector)        direct child (supports multi-step chains like > a > b)
:has(+ selector)        adjacent following sibling (supports multi-step chains)
:has(~ selector)        general following sibling (supports multi-step chains)
```

## Reader pattern

Subclass `Reader[T_node, R]` to transform the tree:

```python
class MyReader(Reader[dict, list[dict]]):
    def on_node(self, node: KdlNode, ctx: WalkContext[dict]) -> dict:
        children = ctx.walk_children()
        return {"name": node.name, "children": children}

    def error_node(self, node: KdlNode, message: str, ctx: WalkContext[dict]) -> dict:
        return {"name": node.name, "error": message}

    def finalize(self, nodes: list[dict], diagnostics: list[ReadDiagnostic]) -> list[dict]:
        return nodes
```

## Parse error codes

`KDLParseError` carries a stable machine-readable `code` (keyword-only, defaults to `""` for backward compatibility) and a human-readable `hint` looked up from a central table. Downstream tools should branch on `code`, not on `msg` text.

```python
from kdlquery import parse, KDLParseError, PARSE_ERROR_CODES

try:
    parse(r'foo re #"(\d+)"')          # missing trailing #
except KDLParseError as e:
    e.code   # "raw-string/unterminated"
    e.hint   # actionable, non-empty string
    e.msg    # "Unterminated raw string"
    e.line   # 1
    e.col    # 7
```

`PARSE_ERROR_CODES` is a `frozenset[str]` of all category codes — useful for self-doc and exhaustiveness checks.

Codes are path-like, lowercase-kebab, and extensible. Adding a new category = one row in `_PARSE_ERROR_HINTS` (`kdlquery/types.py`) + one `code="..."` emit site in the parser.

| code | hint (summary) |
|------|----------------|
| `raw-string/unterminated` | KDL raw strings need a matching trailing `#` per leading `#` |
| `raw-string/newline` | single-line raw strings cannot span lines |
| `multiline-raw-string/no-leading-newline` | multiline raw body must start with `\n` after opening delimiter |
| `multiline-raw-string/decode` | multiline raw body violates KDL2 indent/escape rules |
| `quoted-string/unterminated` | quoted string missing closing `"` |
| `quoted-string/newline` | quoted strings cannot contain a literal newline |
| `quoted-string/decode` | invalid escape sequence in quoted string |
| `multiline-string/no-leading-newline` | multiline string body must start with `\n` after opening `"""` |
| `multiline-string/unterminated` | multiline string missing closing `"""` |
| `multiline-string/decode` | multiline string body violates KDL2 indent/escape rules |
| `block-comment/unterminated` | `/* ... */` missing closing `*/` |
| `unexpected-character` | character not valid in KDL2 at this position |
| `bom-outside-start` | U+FEFF only permitted as first code point |
| `surrogate-codepoint` | lone UTF-16 surrogates not allowed |
| `control-codepoint` | C0/C1 control chars (except tab/newline) not allowed |
| `direction-control-codepoint` | bidi control chars not allowed |
| `number/invalid-trailing` | number literal followed by identifier char without delimiter |
| `reserved-bare-identifier` | reserved identifier (`true`/`false`/`null`/`inf`/`nan`/`-inf`) not valid as bare ident |
| `children-block/unterminated` | `{ ... }` missing closing `}` |
| `node/multiple-children-blocks` | a node may have at most one children block |
| `expected-eol` | expected newline / semicolon / EOF after node |
| `expected-whitespace` | KDL2 requires whitespace between entries |
| `slashdash/no-children-block` | trailing `/` must be followed by a children block |
| `expected-identifier` | expected an identifier at this position |
| `expected-value` | expected a value (string/number/bool/null) at this position |
| `expected-token` | unexpected token — parser expected a specific token |

## Conventions
- All core data model, reader, builder, and selector AST classes (`KdlDocument`, `KdlNode`, `KdlValue`, `_Keyword`, `ReadDiagnostic`, `DiagnosticCollector`, `WalkContext`, `_CstNodeFrame`, and selector AST dataclasses) use `@dataclass(slots=True)` (no per-instance `__dict__`).
- `KdlValue` is frozen (immutable); constructed via `KdlValue.create()` or `KdlValue.keyword()`.
- `KdlNode` and `KdlDocument` are mutable. `args` and `children` are `list[KdlValue]` / `list[KdlNode]`; `properties` is `dict[str, KdlValue]`. `KdlDocument.nodes` is `list[KdlNode]`.
- `KdlNode.create()`, `add_arg()`, and `set_prop()` auto-wrap raw Python primitives (`str`, `int`, `float`, `bool`, `None`) into `KdlValue` while still accepting `KdlValue` instances directly; `add_arg()` and `set_prop()` also accept an optional `type_annotation` keyword argument.
- Mutators (`add_child`, `insert_child`, `add_node`, `insert_node`) wire `parent` and `_document` back-references on inserted subtrees automatically; `remove_child` clears `parent` and recursively clears `_document` on the removed node and all of its descendants.
- `parse_into` and `Walker.walk_document` accept `str | KdlDocument | CSTDocument` and wire `_document` back-references across the tree.
- `_EMPTY_SPAN` (sentinel) is the default span for synthetic nodes/values produced via `create()`/`KdlNode.create()` and for intermediate spans skipped by `_NullBuilder` / `AstBuilder`.
- Source spans (`Span(start=Position, end=Position)`) are preserved on every CST node and on `KdlDocument`, `KdlNode`, and `KdlValue` instances produced by `parse()`.
- Selector parsing and type annotation normalization are cached with `functools.lru_cache`, and `#nan` equality (`=`) uses `math.isnan`.
- KDL 2.0 spec features: slashdash comments, esclines, multiline strings, raw strings, type annotations, unicode whitespace.
- Serializer is spec-compliant and regex-accelerated, but not byte-identical round-trip: comments (`//`, `/* */`, `/-`), raw-string variants, hex/octal/binary number formats, BOM, and version markers are normalized away.

## License

MIT
