DOT DSL
Read a small part of Graphviz’s DOT language into a graph of nodes, edges and attributes, refusing malformed graphs, edges and attributes.
Adapted from Exercism’s problem specification (MIT). Listed under Parsing & Validation.
// FILE: dot_dsl.nomi
//# Reads a small part of Graphviz's DOT language: an undirected `graph`
//# of nodes, edges and graph attributes, each of which may carry
//# attributes.
/// An attribute's value: a whole number, `true` or `false`, or text,
/// quoted or not.
pub enum Value
Number Int
Flag Bool
Text String
end
/// A graph: its nodes and edges, each with its attributes, and the graph's
/// own attributes. An edge is keyed by its two nodes in order, so `b -- a`
/// is the edge `("a", "b")`.
pub struct Graph
nodes: Map<String, Map<String, Value>>
edges: Map<(String, String), Map<String, Value>>
attrs: Map<String, Value>
end
/// Why a text is not a graph.
pub enum Error
InvalidGraph
InvalidEdge
InvalidAttribute
NodeNameNotAlphanumeric
end
impl Display for Error
fn to_string(error: Error) -> String
case error
.InvalidGraph -> "invalid graph"
.InvalidEdge -> "invalid edge"
.InvalidAttribute -> "invalid attribute"
.NodeNameNotAlphanumeric -> "node name must be alphanumeric"
end
end
end
/// One statement inside a graph's braces.
enum Statement
GraphAttributes Map<String, Value>
Node {name: String, attributes: Map<String, Value>}
Edges {names: List<String>, attributes: Map<String, Value>}
end
/// Reads `text`, a `graph { ... }` with one statement on each line between
/// the braces. A line that starts with `//` or `#` is a comment.
pub fn parse(text: String) -> Result<Graph, Error>
lines =
text
|> String.lines()
|> Iter.map(String.trim)
|> Iter.filter(fn line -> line != "" and not is_comment(line))
|> Iter.to_list()
["graph {", ..body, "}"] = lines else return Err(.InvalidGraph)
statements = body |> Iter.map(statement) |> Result.collect()?
empty: Graph = {nodes: {}, edges: {}, attrs: {}}
Ok(Iter.reduce(statements, empty, add))
end
fn is_comment(line: String) -> Bool
String.starts_with(line, "//") or String.starts_with(line, "#")
end
/// Reads one statement, `subject [name=value, ...];`, where the subject is
/// a node, a chain of edges `a -- b -- c`, or nothing for the graph's own
/// attributes.
fn statement(line: String) -> Result<Statement, Error>
Some(line) = String.strip_suffix(line, ";") else return Err(.InvalidGraph)
(subject, attributes) = case String.split(line, "[")
[subject] ->
(subject, {})
[subject, list] ->
Some(inner) = list |> String.trim() |> String.strip_suffix("]") else
return Err(.InvalidAttribute)
end
(subject, attributes_in(inner)?)
_ ->
return Err(.InvalidAttribute)
end
case String.words(subject)
[] ->
Ok(.GraphAttributes(attributes))
[name] ->
if not is_alphanumeric(name) then return Err(.NodeNameNotAlphanumeric)
Ok(.Node{name:, attributes:})
words ->
Ok(.Edges{names: edge_names(words)?, attributes:})
end
end
/// The attributes of `name=value, ...`, the text between a statement's
/// brackets.
fn attributes_in(list: String) -> Result<Map<String, Value>, Error>
list
|> String.split(",")
|> Iter.map(fn pair ->
case pair |> String.trim() |> String.split("=")
[name, value] when name != "" and value != "" -> Ok((name, value_of(value)))
_ -> Err(Error.InvalidAttribute)
end
end)
|> Result.collect()?
|> Iter.to_map()
|> Ok()
end
/// The value written `text`: quoted text, a whole number, `true` or
/// `false`, or else unquoted text.
fn value_of(text: String) -> Value
quoted = String.strip_prefix(text, "\"") |> Maybe.flat_map(&String.strip_suffix(&1, "\""))
case (quoted, String.to_int(text), text)
(Some(inner), _, _) -> .Text(inner)
(_, Some(number), _) -> .Number(number)
(_, _, "true") -> .Flag(True)
(_, _, "false") -> .Flag(False)
_ -> .Text(text)
end
end
/// The nodes of a chain of edges, `a -- b -- c`, written as words.
fn edge_names(words: List<String>) -> Result<List<String>, Error>
(names, links) =
words
|> Iter.with_index()
|> Iter.partition(&(&1.first % 2 == 0))
names = names |> Iter.map(.second) |> Iter.to_list()
valid = Iter.count(names) == Iter.count(links) + 1
and Iter.all_match(links, &(&1.second == "--"))
and Iter.all_match(names, is_alphanumeric)
if valid then Ok(names) else Err(.InvalidEdge)
end
fn is_alphanumeric(name: String) -> Bool
name
|> String.to_codepoints()
|> Iter.all_match(fn c -> Codepoint.is_letter(c) or Codepoint.is_digit(c))
end
/// `graph` with `statement`'s nodes, edges or attributes added. Attributes
/// given again for the same node, edge or graph replace those given before.
fn add(graph: Graph, statement: Statement) -> Graph
case statement
.GraphAttributes(attributes) ->
{..graph, attrs: Map.merge(.., attributes)}
.Node{name:, attributes:} ->
{..graph, nodes: with_attributes(.., name, attributes)}
.Edges{names:, attributes:} ->
nodes = Iter.reduce(names, graph.nodes, &with_attributes(&1, &2, {}))
edges =
names
|> Iter.windows(2)
|> Iter.reduce(graph.edges, fn edges, pair ->
[a, b] = Iter.sort(pair) else unreachable "a window of two holds two names"
with_attributes(edges, (a, b), attributes)
end)
{..graph, nodes:, edges:}
end
end
/// `entries` with `attributes` merged into those of `key`, which it gains
/// if it lacks it.
fn with_attributes<K>(
entries: Map<K, Map<String, Value>>,
key: K,
attributes: Map<String, Value>,
) -> Map<K, Map<String, Value>>
Map.update(entries, key, {}, &Map.merge(&1, attributes))
end
// FILE: dot_dsl_test.nomi
import
dot_dsl
dot_dsl.Graph
end
test "parse"
[
(
"empty graph",
"""
graph {
}
""",
Graph{nodes: {}, edges: {}, attrs: {}},
),
(
"graph with one node",
"""
graph {
a;
}
""",
{
nodes: {"a" => {}},
edges: {},
attrs: {},
},
),
(
"graph with one node with attribute",
"""
graph {
a [color=green];
}
""",
{
nodes: {"a" => {"color" => .Text("green")}},
edges: {},
attrs: {},
},
),
(
"graph with one edge",
"""
graph {
a -- b;
}
""",
{
nodes: {"a" => {}, "b" => {}},
edges: {("a", "b") => {}},
attrs: {},
},
),
(
"graph with one attribute",
"""
graph {
[foo=1];
}
""",
{nodes: {}, edges: {}, attrs: {"foo" => .Number(1)}},
),
(
"graph with comments",
"""
graph {
// a C-like comment
# a shell-like comment
[foo=1];
}
""",
{nodes: {}, edges: {}, attrs: {"foo" => .Number(1)}},
),
(
"graph with nodes, edges, and attributes",
"""
graph {
[foo=1];
[title="Testing Attrs"];
a [color=green];
b [label="Beta!"];
b -- c;
a -- b [color=blue];
[bar=true];
}
""",
{
nodes: {
"a" => {"color" => .Text("green")},
"b" => {"label" => .Text("Beta!")},
"c" => {},
},
edges: {("a", "b") => {"color" => .Text("blue")}, ("b", "c") => {}},
attrs: {
"foo" => .Number(1),
"title" => .Text("Testing Attrs"),
"bar" => .Flag(True),
},
},
),
(
"multiple edges on one line",
"""
graph {
a -- b -- c -- d [style=dotted];
}
""",
{
nodes: {"a" => {}, "b" => {}, "c" => {}, "d" => {}},
edges: {
("a", "b") => {"style" => .Text("dotted")},
("b", "c") => {"style" => .Text("dotted")},
("c", "d") => {"style" => .Text("dotted")},
},
attrs: {},
},
),
(
"only 1 edge between nodes",
"""
graph {
a -- b;
a -- b;
b -- a [color=blue];
}
""",
{
nodes: {"a" => {}, "b" => {}},
edges: {("a", "b") => {"color" => .Text("blue")}},
attrs: {},
},
),
]
|> subtests (description, text, expected), description
assert dot_dsl.parse(text) == Ok(expected)
end
end
test "parse errors"
[
(
"malformed input",
"""
graphical {
}
""",
"invalid graph",
),
(
"malformed edge",
"""
graph {
a --;
}
""",
"invalid edge",
),
(
"malformed edge 2",
"""
graph {
a b;
}
""",
"invalid edge",
),
("invalid edge type", "graph {\n a == b;\n} ", "invalid edge"),
(
"multiple edges missing a node",
"""
graph {
a -- b --;
}
""",
"invalid edge",
),
(
"multiple edges missing a connector",
"""
graph {
a -- b c;
}
""",
"invalid edge",
),
(
"empty attribute",
"""
graph {
a [];
}
""",
"invalid attribute",
),
(
"malformed attribute",
"""
graph {
a [name];
}
""",
"invalid attribute",
),
(
"empty attribute name",
"""
graph {
a [=value];
}
""",
"invalid attribute",
),
(
"non-alphanumeric node name",
"""
graph {
? [key=value];
}
""",
"node name must be alphanumeric",
),
]
|> subtests (description, text, expected), description
assert Err(error) = dot_dsl.parse(text)
assert "${error}" == expected
end
endok parse (9 cases)
ok parse errors (10 cases)
test result: ok. 19 passed, 0 failed
How it’s written
Section titled “How it’s written”- Adapted: the description asks for an internal DSL, graph-building code written in the host language. The canonical data instead parses DOT text, and this port does that:
parsereads the text into aGraphvalue. An internal DSL in Nomi would be plain constructor calls on immutable values, which leaves nothing for the canonical cases to check. - A
Graphis three maps: nodes by name, edges by their two node names in order (("a", "b")forb -- a, so an edge given twice either way round is one edge), and the graph’s own attributes. Attributes are aMap<String, Value>, written out: atypealiasof a named type would only hide it. - An attribute’s
Valueis an enum ofNumber,FlagandText, since the canonical attributes mix1,trueand"Testing Attrs".value_oftries them in order with onecaseover a tuple: quoted text, a whole number,trueorfalse, then unquoted text (color=green). parsekeeps the lines that are not empty or comments and takes them apart with["graph {", ..body, "}"] = lines else { ... }, so a text without both braces isInvalidGraph.- Each line between the braces is one statement, read by
statementinto a privateStatementenum: graph attributes, a node, or a chain of edges. The words of its subject decide which: none, one, ora -- b -- ..., checked byedge_namesas names at even positions and--between them.Result.collectstops at the first bad line, andaddfolds the statements into the graph. Attributes given again for the same node, edge or graph are merged, the later value winning. - The four canonical errors are an
Errorenum with animpl Displaygiving the canonical messages. The error cases assert the message,"${error}", so the table reads as the canonical data does. - The canonical inputs are lists of lines; each is a
"""string here. “invalid edge type” ends its last line with a space, which would be invisible at the end of a"""line, so it is an ordinary string with\n. - The cases are two
subteststables, the graphs and the errors, since they assert different things.