Racket

KDL: a parser for the KDL Document Language🔗ℹ

jvivanco

package: kdl

A lexer, parser and abstract syntax tree for KDL v2.0.0, written in plain Racket using only the standard libraries: parser-tools/lex for the lexical structure, racket/match for the recursive-descent parser, and racket/contract to keep malformed trees from being built in the first place. Nothing is shelled out to an external tool.

Two levels of representation are available: a precise AST built from structs (The abstract syntax tree), and kexpr (Plain data: kexpr), plain hashes and lists in the spirit of jsexpr, for when a document is just configuration to be read.

The implementation passes all 338 cases of the official KDL conformance suite: each of the 243 valid documents parses to an AST equal to the one produced by its canonical form, and all 95 invalid documents are rejected.

1 Parsing🔗ℹ

procedure
(parse-kdl in) → kdl-document?
in : (or/c string? input-port?)

Parses a complete KDL document and returns its AST. Raises exn:fail:kdl if the input is not well-formed KDL.

Examples:

> (parse-kdl "server port=8080")
(kdl-document
(list
  (kdl-node
   #f
   "server"
   '()
   (list (kdl-property "port" (kdl-value #f 8080)))
   '())))
> (parse-kdl "a; b; c")
(kdl-document
(list
  (kdl-node #f "a" '() '() '())
  (kdl-node #f "b" '() '() '())
  (kdl-node #f "c" '() '() '())))

procedure
(parse-kdl-node in) → kdl-node?
in : (or/c string? input-port?)

Like parse-kdl, but for a document that holds exactly one node, which it returns directly. Raises exn:fail if the document has any other number of nodes. Convenient in tests and in code that already knows the shape of its input.

Example:

> (parse-kdl-node "package name=\"kdl\" version=\"0.2\"")
(kdl-node
#f
"package"
'()
(list
(kdl-property "name" (kdl-value #f "kdl"))
(kdl-property "version" (kdl-value #f "0.2")))
'())

2 The abstract syntax tree🔗ℹ

Every struct is #:transparent, so equal? compares trees by content and a test can spell out the expected tree literally.

struct
(struct kdl-document (nodes))
nodes : (listof kdl-node?)

A whole document: the sequence of its top-level nodes.

struct
(struct kdl-node (type name args props children))
  type : (or/c #f string?)
  name : string?
  args : (listof kdl-argument?)
  props : (listof kdl-property?)
  children : (listof kdl-node?)

A single node. type is its type annotation, or #f when it has none. args keeps the positional arguments in source order; props holds the properties, whose names are guaranteed to be unique (see Duplicate properties).

Examples:

> (define n (parse-kdl-node "(app)server \"web\" port=8080 { route \"/api\" }"))
> (kdl-node-type n)
"app"
> (kdl-node-name n)
"server"
> (kdl-node-arg-data n)
'("web")
> (map kdl-node-name (kdl-node-children n))
'("route")

struct
(struct kdl-argument (value))
value : kdl-value?

A positional argument.

struct
(struct kdl-property (name value))
name : string?
value : kdl-value?

A key=value property.

struct
(struct kdl-value (type datum))
type : (or/c #f string?)
datum : (or/c string? number? boolean? 'null)

A value, together with its type annotation if it carries one.

KDL’s #null becomes the symbol 'null rather than #f, so that it stays distinguishable from #false. #inf, #-inf and #nan become the corresponding Racket flonums.

Example:

> (kdl-node-args (parse-kdl-node "n (u8)255 #null #inf"))
(list
(kdl-argument (kdl-value "u8" 255))
(kdl-argument (kdl-value #f 'null))
(kdl-argument (kdl-value #f +inf.0)))

The contracts are enforced at the module boundary, so a tree that violates them is rejected where it is built rather than somewhere downstream:

Examples:

> (kdl-value #f (list 1 2))
kdl-value: contract violation
  expected: (or/c string? number? boolean? (quote null))
  given: '(1 2)
  in: the 2nd argument of
      (->
       (or/c #f string?)
       (or/c string? number? boolean? 'null)
       kdl-value?)
  contract from: <pkgs>/kdl/ast.rkt
  blaming: top-level
   (assuming the contract is correct)
  at: <pkgs>/kdl/ast.rkt:29:8
> (kdl-node #f 'not-a-string '() '() '())
kdl-node: contract violation
  expected: string?
  given: 'not-a-string
  in: the 2nd argument of
      (->
       (or/c #f string?)
       string?
       (listof kdl-argument*?)
       (and/c
        (listof kdl-property*?)
        distinct-prop-names?)
       (listof kdl-node*?)
       kdl-node?)
  contract from: <pkgs>/kdl/ast.rkt
  blaming: top-level
   (assuming the contract is correct)
  at: <pkgs>/kdl/ast.rkt:32:8

2.1 Accessors🔗ℹ

procedure
(kdl-node-ref node name [default]) → any/c
  node : kdl-node?
  name : string?
  default : any/c = #f

Looks a property up by name and returns its kdl-value, or default if the node has no such property.

Examples:

> (define n (parse-kdl-node "server port=8080 tls=#true"))
> (kdl-node-ref n "port")
(kdl-value #f 8080)
> (kdl-value-datum (kdl-node-ref n "tls"))
#t
> (kdl-node-ref n "missing" 'none)
'none

procedure
(kdl-node-arg-data node)
→ (listof (or/c string? number? boolean? 'null))
node : kdl-node?

The data carried by the node’s positional arguments, in order, with the type annotations dropped.

Example:

> (kdl-node-arg-data (parse-kdl-node "sizes 1 2.5 \"three\" #true"))
'(1 2.5 "three" #t)

3 Plain data: kexpr🔗ℹ

The AST is precise but verbose. When a document is just configuration to be read, kexpr is the flatter alternative: plain Racket data, the way a jsexpr is to JSON. There are no structs and no contracts to satisfy, only hashes and lists to walk with hash-ref and for.

A document is a list of nodes, and each node is a hash:

knode  = (hasheq 'name     symbol?
                 'type     symbol?      ; only when annotated
                 'args     (listof kvalue)
                 'props    (hasheq symbol? kvalue)
                 'children (listof knode))

kvalue = string? | number? | boolean? | 'null
       | (hasheq 'type symbol? 'value kvalue)

Names — of the node, of its properties, of a type annotation — are symbols, the way the keys of a jsexpr are; strings are left for data.

Note that a bare word and a quoted string are the same value in KDL: node foo, node "foo" and node #"foo"# all mean the same thing, and the canonical form of a document drops the quotes where they are not needed. So that distinction does not survive into a kexpr, and should not.

Example:

> (equal? (kdl->kexpr "n foo") (kdl->kexpr "n \"foo\""))
#t

The conversion loses nothing: KDL’s native types and its type annotations both survive a round trip.

procedure
(kdl->kexpr in) → (listof hash?)
in : (or/c string? input-port?)

Parses a document and returns it as a list of node hashes. Raises exn:fail:kdl on malformed input.

Every node carries all four of 'name, 'args, 'props and 'children, so they can be read without supplying a default; 'type appears only on annotated nodes.

A value that carries a type annotation is wrapped in a hash, which is the only place the annotation could go without losing it; a plain value is the datum itself.

Examples:

> (kdl->kexpr "server port=8080 tls=#true")
'(#hasheq((args . ())
          (children . ())
          (name . server)
          (props . #hasheq((port . 8080) (tls . #t)))))
> (kdl->kexpr "a; b")
'(#hasheq((args . ()) (children . ()) (name . a) (props . #hasheq()))
  #hasheq((args . ()) (children . ()) (name . b) (props . #hasheq())))
> (kdl->kexpr "n (u8)255")
'(#hasheq((args . (#hasheq((type . u8) (value . 255))))
          (children . ())
          (name . n)
          (props . #hasheq())))

procedure
(kexpr->kdl k) → string?
k : (or/c hash? (listof hash?))

Renders a kexpr back to KDL text. A single node hash is accepted in place of a one-node document, and a node may leave out the keys it does not need. Names may be given as strings as well as symbols: reading is strict, writing is lenient.

Strings are quoted only when they have to be — when they are not a legal bare identifier — and escapes are inserted where a literal character would be illegal. Properties are sorted by key, since a hash has no order of its own and the output should be reproducible.

Examples:

> (display (kexpr->kdl (hasheq 'name 'server
                               'props (hasheq 'port 8080))))
server port=8080
> (display (kexpr->kdl (hasheq 'name 'a
                               'children (list (hasheq 'name 'b)))))
a {
    b
}
> (display (kexpr->kdl (hasheq 'name 'n 'args (list "needs quoting"))))
n "needs quoting"

Raises exn:fail:kdl if a node has no 'name, or if a value has no KDL representation.

Examples:

> (kexpr->kdl (hasheq 'args '(1)))
kexpr->kdl: un nodo necesita 'name
> (kexpr->kdl (hasheq 'name 'n 'args (list (list 1 2))))
kexpr->kdl: valor no representable en KDL: (1 2)

The two are inverses, up to formatting:

Examples:

> (define doc "pkg name=\"kdl\" version=2 ok=#true { dep (u8)255 }")
> (display (kexpr->kdl (kdl->kexpr doc)))
pkg name=kdl ok=#true version=2 {
dep (u8)255
}
> (equal? (kdl->kexpr doc) (kdl->kexpr (kexpr->kdl (kdl->kexpr doc))))
#t

4 What is supported🔗ℹ

4.1 Values🔗ℹ

Bare identifiers, quoted strings, raw strings with any number of # delimiters, multi-line strings in both flavours, numbers in decimal, hex, octal and binary (with _ separators and exponents), and the keywords #true, #false, #null, #inf, #-inf and #nan.

Examples:

> (kdl-node-arg-data (parse-kdl-node "n 0xff 0o17 0b1010 1_000_000 -2.5e3"))
'(255 15 10 1000000 -2500.0)
> (kdl-node-arg-data (parse-kdl-node "n #\"a raw \\n string\"#"))
'("a raw \\n string")

Note that in KDL v2 the bare words true, false, null, inf, -inf and nan are reserved: they must be written with the leading #, and on their own they are an error rather than a string.

Example:

> (parse-kdl "enabled true")
kdl: `true` es palabra reservada; en KDL v2 se escribe
`#true` (línea 1, columna 9)

4.2 Multi-line strings🔗ℹ

The closing line of a multi-line string sets the whitespace prefix that is stripped from every other line; the opening and closing newlines are not part of the value, and a line that holds only whitespace always counts as empty. Inconsistent indentation is an error.

Example:

> (kdl-node-arg-data
(parse-kdl-node "text \"\"\"\n first\n indented\n\n last\n \"\"\""))
'("first\n indented\n\nlast")

4.3 Escapes🔗ℹ

\n, \r, \t, \\, \", \b, \f and \s (a space), plus \u{...} with one to six hexadecimal digits, validated to be a Unicode scalar value. A backslash followed by whitespace discards both the backslash and the whitespace.

Example:

> (kdl-node-arg-data (parse-kdl-node "n \"a\\tb\""))
'("a\tb")

4.4 Comments and slashdash🔗ℹ

// to the end of the line, /* */ which nests, and the slashdash /-, which is a semantic comment: whatever follows it is parsed like anything else — so it still has to be valid — and only then discarded. It applies to an argument, a property, a block of children, or a whole node.

Examples:

> (parse-kdl-node "flags /-dropped \"kept\" /-key=\"x\" real=\"y\"")
(kdl-node
#f
"flags"
(list (kdl-argument (kdl-value #f "kept")))
(list (kdl-property "real" (kdl-value #f "y")))
'())
> (map kdl-node-name (kdl-document-nodes (parse-kdl "a\n/-b 1 { deep; }\nc")))
'("a" "c")
> (parse-kdl "/-node { unclosed")
kdl: falta `}` para cerrar el bloque de hijos (línea 1,
columna 18)

4.5 Line continuations🔗ℹ

A \ at the end of a line lets a node carry on to the next one.

Example:

> (parse-kdl-node "limits \\\n  memory=512 \\\n  cpu=2")
(kdl-node
#f
"limits"
'()
(list
  (kdl-property "memory" (kdl-value #f 512))
  (kdl-property "cpu" (kdl-value #f 2)))
'())

4.6 Duplicate properties🔗ℹ

Properties are processed left to right and the rightmost occurrence of a key wins, keeping its position. Positional arguments preserve their order strictly.

Example:

> (kdl-node-props (parse-kdl-node "n x=1 y=2 x=3"))
(list (kdl-property "y" (kdl-value #f 2)) (kdl-property "x" (kdl-value #f 3)))

4.7 Disallowed literal code points🔗ℹ

The specification forbids a set of code points from appearing literally in a document: the C0 and C1 controls that are not whitespace, DELETE, the bidirectional direction-control characters, and the byte order mark anywhere but at the very start. Writing them as an escape is still fine.

Examples:

> (parse-kdl "node \"\u202A\"")
kdl: code point no permitido en un documento KDL: U+202A
(línea 1, columna 7)
> (kdl-node-arg-data (parse-kdl-node "node \"\\u{202A}\""))
'("\u202A")

5 Errors🔗ℹ

struct
(struct exn:fail:kdl exn:fail (line col))
line : (or/c #f exact-positive-integer?)
col : (or/c #f exact-nonnegative-integer?)

Raised for every lexical or syntactic error. Besides the message, it carries the line and column where the problem was found.

Examples:

> (parse-kdl "ok\nnode \"unterminated")
kdl: string sin cerrar (línea 2, columna 6)
> (with-handlers ([exn:fail:kdl? exn:fail:kdl-line])
(parse-kdl "ok\nnode \"unterminated"))
2

6 Modules🔗ℹ

(require kdl/ast)

package: kdl

The AST structs and their contracts.

(require kdl/lexer)

package: kdl

The lexer and exn:fail:kdl.

(require kdl/parser)

package: kdl

parse-kdl and parse-kdl-node.

(require kdl/kexpr)

package: kdl

kdl->kexpr and kexpr->kdl.

kdl re-exports all of them and is the module to require.

7 Tests🔗ℹ

raco test tests/

1	Parsing
2	The abstract syntax tree
3	Plain data: kexpr
4	What is supported
5	Errors
6	Modules
7	Tests