Skip to content

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
end
  • 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: parse reads the text into a Graph value. An internal DSL in Nomi would be plain constructor calls on immutable values, which leaves nothing for the canonical cases to check.
  • A Graph is three maps: nodes by name, edges by their two node names in order (("a", "b") for b -- a, so an edge given twice either way round is one edge), and the graph’s own attributes. Attributes are a Map<String, Value>, written out: a typealias of a named type would only hide it.
  • An attribute’s Value is an enum of Number, Flag and Text, since the canonical attributes mix 1, true and "Testing Attrs". value_of tries them in order with one case over a tuple: quoted text, a whole number, true or false, then unquoted text (color=green).
  • parse keeps the lines that are not empty or comments and takes them apart with ["graph {", ..body, "}"] = lines else { ... }, so a text without both braces is InvalidGraph.
  • Each line between the braces is one statement, read by statement into a private Statement enum: graph attributes, a node, or a chain of edges. The words of its subject decide which: none, one, or a -- b -- ..., checked by edge_names as names at even positions and -- between them. Result.collect stops at the first bad line, and add folds 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 Error enum with an impl Display giving 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 subtests tables, the graphs and the errors, since they assert different things.