#moonrockz/diagrams-query

#Language version 1

query     := rule+
rule      := captured | '(' captured predicate+ ')'
captured  := node capture*
node      := '(' selector part* ')' | '[' captured+ ']'
part      := captured | field ':' captured | '!' field
selector  := qualified-kind | 'category.' category | '_'
capture   := '@' capture-name
predicate := '(' predicate-name capture string* ')'

• An identifier has ASCII letters, digits, _ and -, and starts with a letter or _. A qualified name is prefix.local; an unqualified name has no namespace. Capture names can also contain . after the first character.
• Strings use JSON escapes and keep Unicode values. ; starts a comment to the end of the line. Whitespace separates tokens.
• The namespace map of the compile call binds query prefixes to namespace URIs. Source-document prefixes have no effect. category is not a prefix.

#Native predicates

#Matching and order

#Unsupported features

///|
test "unsupported features fail with stable codes" {
  let schema = @query.Schema::new(
    id="example/tree",
    version=1,
    kinds=[@query.Name::new("", "box")],
    categories=["thing"],
    fields=[],
  )
  for case in [
    ("(box)*", "query/unsupported-quantifier"),
    ("(box . (box))", "query/unsupported-anchor"),
    ("((box) @b (#set! @b \"k\"))", "query/unsupported-directive"),
    ("((box) @b (#match? @b \"x\"))", "query/unsupported-regex"),
    ("(box \"+\")", "query/unsupported-anonymous-node"),
    ("((box) (box))", "query/unsupported-grouping"),
    ("((box) @b (#eq? @b \"x\"))", "query/unknown-predicate"),
  ] {
    let diagnostics = @query.compile(case.0, schema).unwrap_err()
    assert_eq(diagnostics[0].code, case.1)
    assert_true(diagnostics[0].span is Some(_))
  }
}

#Tree adapters and schemas

///|
struct Shelf {
  kinds : Array[String]
  children : Array[Array[Int]]
  names : Array[String?]
}

///|
let shelf_schema : @query.Schema = @query.Schema::new(
  id="example/shelf",
  version=1,
  kinds=[@query.Name::new("", "shelf"), @query.Name::new("", "book")],
  categories=["item"],
  fields=[@query.Name::new("", "holds")],
  reserved_namespaces=[""],
)

///|
impl @query.QueryTree for Shelf with schema(_self) {
  shelf_schema
}

///|
impl @query.QueryTree for Shelf with root(_self) {
  0
}

///|
impl @query.QueryTree for Shelf with node_count(self) {
  self.kinds.length()
}

///|
impl @query.QueryTree for Shelf with kind(self, node) {
  Some(@query.Name::new("", self.kinds[node]))
}

///|
impl @query.QueryTree for Shelf with category(_self, _node) {
  "item"
}

///|
impl @query.QueryTree for Shelf with children(self, node) {
  self.children[node][:]
}

///|
impl @query.QueryTree for Shelf with field(_self, node) {
  if node == 0 {
    None
  } else {
    Some(@query.Name::new("", "holds"))
  }
}

///|
impl @query.QueryTree for Shelf with attribute(self, node, name) {
  if name == @query.Name::new("", "name") {
    self.names[node].map(text => @query.ScalarValue::{ tag: "text", text })
  } else {
    None
  }
}

///|
impl @query.QueryTree for Shelf with text(_self, _node) {
  None
}

///|
impl @query.QueryTree for Shelf with extra(_self, _node, _name) {
  None
}

///|
impl @query.QueryTree for Shelf with location(_self, _node) {
  None
}

///|
impl @query.QueryTree for Shelf with path(_self, _node) {
  []
}

///|
impl @query.QueryTree for Shelf with depth(_self, node) {
  if node == 0 {
    0
  } else {
    1
  }
}

///|
test "text and typed queries give the same plan and matches" {
  let shelf = Shelf::{
    kinds: ["shelf", "book", "book"],
    children: [[1, 2], [], []],
    names: [None, Some("Dune"), Some("")],
  }
  let text = "((shelf holds: (book) @b) @s (#attr-eq? @b \"name\" \"Dune\"))"
  let form = @query.QueryForm::new([
    @query.Rule::new(
      @query.Pattern::node(
        Kind(@query.QName::new("shelf")),
        parts=[
          Field(
            @query.QName::new("holds"),
            @query.Pattern::node(Kind(@query.QName::new("book")), captures=["b"]),
          ),
        ],
        captures=["s"],
      ),
      predicates=[@query.Predicate::attr_eq("b", "name", "Dune")],
    ),
  ])
  let a = @query.compile(text, shelf_schema).unwrap()
  let b = @query.compile_form(form, shelf_schema).unwrap()
  assert_eq(a.normalized(), b.normalized())
  let result = a.collect(shelf)
  assert_eq(result, b.collect(shelf))
  assert_eq(result.matches.length(), 1)
  assert_eq(result.matches[0].captures.map(c => (c.name, c.node)).iter().to_array(), [
    ("b", 1),
    ("s", 0),
  ])
  // A missing name and an empty name are different.
  let empty = @query.compile("((book) @b (#attr-eq? @b \"name\" \"\"))", shelf_schema)
    .unwrap()
    .collect(shelf)
  assert_eq(empty.matches.map(m => m.captures[0].node).iter().to_array(), [2])
}

#Execution, projection and limits

///|
test "batches, cumulative limits and truthful terminal states" {
  let shelf = Shelf::{
    kinds: ["shelf", "book", "book", "book"],
    children: [[1, 2, 3], [], [], []],
    names: [None, Some("a"), None, Some("b")],
  }
  let plan = @query.compile("(book) @b", shelf_schema).unwrap()
  let projection = @query.Projection::new(shelf_schema, [Attribute("name")]).unwrap()
  let cursor = plan.execute(shelf, projection~)
  guard cursor.next_batch(2) is Rows(first) else { fail("no rows") }
  assert_eq(first.length(), 2)
  assert_eq(first[1].captures[0].values[0], Absent)
  guard cursor.next_batch(2) is Rows(second) else { fail("no rows") }
  assert_eq(second.length(), 1)
  assert_true(cursor.next_batch(2) is Complete)
  // A work bound reached after a batch is a failure, not completion.
  let bounded = plan.execute(shelf, limits=@query.ExecutionLimits::new(work=5))
  guard bounded.next_batch(1) is Rows(_) else { fail("no rows") }
  assert_true(bounded.next_batch(10) is Failed(Limit(Work)))
  assert_true(bounded.next_batch(10) is Failed(Limit(Work)))
}

#Guidance

• Compile a plan once and reuse it; each cursor has its own position and budgets.
• Prefer a narrow candidate root and exact kinds over wildcards for large trees. Set work and pending for untrusted queries.
• Request only the projection fields that you need; paths are materialized only when requested.
• Stop or close a cursor when you have enough rows. A stopped or failed cursor is never complete, and the rows it delivered are not the full result.
• Use the explicit graph operations of the domain library for references and reachability; tree queries do not follow them.