DOT graph → chatbot state machine

dot-graph-chat-bot.go

package main

/*
This program parses a DOT graph representing a chatbot's state machine.
It supports single-select, multiple-select, message-sends, and hooks into programs.
*/

import (
    "fmt"
    "gonum.org/v1/gonum/graph"
    "gonum.org/v1/gonum/graph/encoding"
    "gonum.org/v1/gonum/graph/encoding/dot"
    "gonum.org/v1/gonum/graph/multi"
    "math/rand"
    "time"
)

/*
The following blob is a conversation state machine encoded as a DOT-file.
The DOT format used is the predominant standard for graph description.
https://en.wikipedia.org/wiki/DOT_(graph_description_language)

There are even graphical tools which target it that we could use to build out conversations.

Here's an example online tool which parses and displays the graph this describes:
https://dreampuf.github.io/GraphvizOnline/#digraph%20%7B%0A%20%20%20%20start%20%5B%20type%3D%22START%22%20%5D%0A%20%20%20%20end%20%5B%20type%3D%22END%22%20%5D%0A%20%20%20%20start%20-%3E%20a%0A%20%20%20%20%20%20%20%20a%20%5B%20type%3D%22MSG%22%20text%3D%22Hey!%20You%20know%20how%20zodiac%20signs%20are%20pass%C3%A9%20and%20*soo*%20unscientific%3F%22%20%5D%0A%20%20%20%20%20%20%20%20a%20-%3E%20b%0A%20%20%20%20%20%20%20%20%20%20%20%20b%20%5B%20type%3D%22MSG%22%20text%3D%22We've%20worked%20out%20how%20to%20predict%20your%20future%20based%20on%20your%20favourite%20fruits!%22%20%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20b%20-%3E%20c%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20c%20%5B%20type%3D%22SSQ%22%20text%3D%22Do%20you%20want%20to%20know%20what%20the%20fruits%20you%20like%20say%20about%20you%3F%22%20%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20c%20-%3E%20i%20%5B%20type%3D%22OPT%22%20text%3D%22No.%20That's%20really%20dumb.%22%20%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20c%20-%3E%20d%20%5B%20type%3D%22OPT%22%20text%3D%22Yeah!%20I've%20always%20wondered!%22%20%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20d%20%5B%20type%3D%22MSQ%22%20text%3D%22Cool!%20Which%20of%20these%20do%20you%20like%3F%22%20%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20d%20-%3E%20f%20%5B%20type%3D%22OPT%22%20text%3D%22apples%22%20%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20d%20-%3E%20f%20%5B%20type%3D%22OPT%22%20text%3D%22banannas%22%20%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20d%20-%3E%20f%20%5B%20type%3D%22OPT%22%20text%3D%22coconuts%22%20%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20d%20-%3E%20f%20%5B%20type%3D%22OPT%22%20text%3D%22durians%20(Really!)%22%20%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20d%20-%3E%20f%20%5B%20type%3D%22OPT%22%20text%3D%22elderberries%22%20%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20d%20-%3E%20f%20%5B%20type%3D%22OPT%22%20text%3D%22figs%22%20%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%20%5B%20type%3D%22PRG%22%20uid%3D%22513DC7E6-4194-4515-BB47-9F4018ED4D68%22%20%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20f%20-%3E%20g%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20g%20%5B%20type%3D%22SSQ%22%20text%3D%22Does%20that%20sound%20about%20right%3F%22%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20g%20-%3E%20h%20%5B%20type%3D%22OPT%22%20text%3D%22Yeah!%20Wow.%20You%20read%20me%20like%20a%20tabloid%20magazine.%22%20%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20h%20%5B%20type%3D%22MSG%22%20text%3D%22I%20know%2C%20right!%20So%20dope.%22%20%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20h%20-%3E%20end%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20g%20-%3E%20i%20%5B%20type%3D%22OPT%22%20text%3D%22Not%20really.%22%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20i%20%5B%20type%3D%22MSG%22%20text%3D%22H8rs%20gonna%20hate.%22%20%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20i%20-%3E%20end%0A%7D
*/

const graphdot = `
digraph {
    start [ type="START" ]
    end [ type="END" ]
    start -> a
        a [ type="MSG" text="Hey! You know how zodiac signs are passé and *soo* unscientific?" ]
        a -> b
            b [ type="MSG" text="We've worked out how to predict your future based on your favourite fruits!" ]
            b -> c
                c [ type="SSQ" text="Do you want to know what the fruits you like say about you?" ]
                c -> i [ type="OPT" text="No. That's really dumb." ]
                c -> d [ type="OPT" text="Yeah! I've always wondered!" ]
                    d [ type="MSQ" text="Cool! Which of these do you like?" ]
                    d -> f [ type="OPT" text="apples" ]
                    d -> f [ type="OPT" text="banannas" ]
                    d -> f [ type="OPT" text="coconuts" ]
                    d -> f [ type="OPT" text="durians (Really!)" ]
                    d -> f [ type="OPT" text="elderberries" ]
                    d -> f [ type="OPT" text="figs" ]
                        f [ type="PRG" uid="513DC7E6-4194-4515-BB47-9F4018ED4D68" ]
                        f -> g
                            g [ type="SSQ" text="Does that sound about right?"]
                            g -> h [ type="OPT" text="Yeah! Wow. You read me like a tabloid magazine." ]
                                h [ type="MSG" text="I know, right! So dope." ]
                                h -> end
                            g -> i [ type="OPT" text="Not really."]
                                i [ type="MSG" text="H8rs gonna hate." ]
                                i -> end
}`


/*
This deserializes the graph from the string above and then kick off a 'random walk'
which simulates one possible conversation run across the graph.
*/

func main() {
    rand.Seed(time.Now().UnixNano())
    grph := newDotGraph()
    err := dot.UnmarshalMulti([]byte(graphdot), grph)
    if err != nil { panic("error: can't unmarshal graph") }

    // grab the node annotated with the type="START" attribute.
    var startNode *node
    for _, n := range graph.NodesOf(grph.Nodes()) {
        node := verifiedNode(asNode(n))
        if node.isStart {
            startNode = node
        }
    }
    grph.randomWalk(startNode)
}

/*
This random walk implementation shows some of the available `gonum` graph APIs.
(Jump to the end of the function to see the output from a sample run.)
*/

func (g *dotGraph) randomWalk(curr *node) {
    // We have a node. Nodes are states that trigger bot messages.
    // These are questions requiring response, messages requiring no response,
    // or programmatic hooks. (A program hook would allow you to do arbitrary
    // logic.)
    // Print the current node.
    curr.printInfo()

    // Let's grab all possible transitions and simulate a user trying to
    // interact with the bot while on the train... by picking randomly.

    // Grab all the nodes accessible from the current.
    nodes := graph.NodesOf(g.From(curr.ID()))

    // (We might be at the end of our state machine.)
    if len(nodes) == 0 {
        return
    }

    // Now grab the linking edges.
    // These edges contain the information to decide a transition.
    // That could be an empty/implicit transition or a set of options
    // for users to pick from.
    var edges []graph.Edge
    for _, node := range nodes {
        edges = append(edges, g.Edge(curr.ID(), node.ID()))
    }
    // Since multiple answers can transition from state A -> B there can be
    // multiple 'lines' across each A->B 'edge'.
    // Each is a potential option, so grab them all.
    var lines []*line
    for _, edge := range edges {
        // We grab the available lines and cast them to our internal
        // type which contains the DOT file data.
        ls := g.lines(edge)
        lines = append(lines, ls...)
    }

    // We now have all the available transitions from a node.

    // We could pre-parse the graph just like this to  verify that they're
    // legal state transition types based on their 'From' node.

    // At product run time we'd now either automatically transition if the
    // only edges available were empty/implicit or, if they're options
    // corresponding to a previously sent question we'd display them to the
    // user to pick from.

    // (Here, we'll just show the example user's response.)
    line := lines[rand.Intn(len(lines))]
    line.printInfo()

    // We cast the node to our internal type which contains DOT info.
    nextNode := verifiedNode(asNode(line.To()))

    // ...and we continue our simulation.
    g.randomWalk(nextNode)
}

/*
Here's the output of one run of the random walk.
    🤖 [start]
    🤖 [(a) bot-msg] Hey! You know how zodiac signs are passé and *soo* unscientific?
    🤖 [(b) bot-msg] We've worked out how to predict your future based on your favourite fruits!
    🤖 [(c) opt-sng] Do you want to know what the fruits you like say about you?
    🙋 "Yeah! I've always wondered!"
    🤖 [(d) opt-mlt] Cool! Which of these do you like?
    <elided for demo>
    🙋 "durians (Really!)"
    🤖 [(f) program]
    $ ./programs/513DC7E6-4194-4515-BB47-9F4018ED4D68
        'A gambler not only will lose what he has, but also will lose what he doesn’t have.'
    🤖 [(g) opt-sng] Does that sound about right?
    🙋 "Yeah! Wow. You read me like a tabloid magazine."
    🤖 [(h) bot-msg] I know, right! So dope.
    🤖 [end]
*/

/*
The implementation of the data structure parsing follows.
It's built on `gonum` which is a popular go graphing library.
This demo implementation takes some shortcuts — but not actually that many!
*/

type dotGraph struct {
    *multi.DirectedGraph
}

func newDotGraph() *dotGraph {
    return &dotGraph{
        DirectedGraph: multi.NewDirectedGraph(),
    }
}

/* node deserialization hooks */

func (g *dotGraph) NewNode() graph.Node {
    return &node{
        Node: g.DirectedGraph.NewNode()
    }
}

type NodeAttributeKey string
const (
    TYPE NodeAttributeKey = "type"
    TEXT NodeAttributeKey = "text"
    UID NodeAttributeKey = "uid"
)
type NodeType string
const START NodeType = "START"
type startNode struct {
    isStart bool
}
const END NodeType = "END"
type endNode struct {
    isEnd bool
}
const MESSAGE NodeType = "MSG"
type messageNode struct {
    isMessage bool
}
const SINGLE_SELECT_QUESTION NodeType = "SSQ"
type singleSelectQuestionNode struct {
    isSingleSelectQuestion bool
}
const MULTIPLE_SELECT_QUESTION NodeType = "MSQ"
type multipleSelectQuestionNode struct {
    isMultipleSelectQuestion bool
}
const PROGRAM NodeType = "PRG"
type programNode struct {
    isProgram bool
}
type commonNodeComponents struct {
    dotID string
    uid string
    text string
}
type mutexNodeComponents struct {
    startNode
    endNode
    messageNode
    singleSelectQuestionNode
    multipleSelectQuestionNode
    programNode
}
type node struct {
    graph.Node
    commonNodeComponents
    mutexNodeComponents
}

func (n *node) SetDOTID(id string) {
    n.dotID = id
}

func (n *node) SetAttribute(attr encoding.Attribute) error {
    switch NodeAttributeKey(attr.Key) {
    case TYPE:
        n.setType(attr.Value)
    case TEXT:
        n.text = attr.Value
    case UID:
        n.uid = attr.Value
    default:
        panic("dot-unmarshal: unknown attribute '#{attr.Key}'")
        return fmt.Errorf("dot-unmarshal: unknown attribute '#{attr.Key}'")
    }
    return nil
}

func (n *node) setType(val string) error {
    switch NodeType(val) {
    case START:
        n.isStart = true
    case END:
        n.isEnd = true
    case MESSAGE:
        n.isMessage = true
    case SINGLE_SELECT_QUESTION:
        n.isSingleSelectQuestion = true
    case MULTIPLE_SELECT_QUESTION:
        n.isMultipleSelectQuestion = true
    case PROGRAM:
        n.isProgram = true
    default:
        panic("dot-unmarshal: unknown node type '#{val}'")
        return fmt.Errorf("dot-unmarshal: unknown node type '#{val}'")
    }
    return nil
}

/* edge/line deserialization hooks */

func (g *dotGraph) NewLine(from graph.Node, to graph.Node) graph.Line {
    line := &line{
        Line: g.DirectedGraph.NewLine(asNode(from), asNode(to)),
    }
    line.isImplicit = true
    return line
}

type LineAttributeKey string
const (
    L_TYPE LineAttributeKey = "type"
    L_TEXT LineAttributeKey = "text"
)

type LineType string
const EOPTION LineType = "OPT"
type optionLine struct {
    isOption bool
    text string
}
type implicitLine struct {
    isImplicit bool
}
type commonLineComponents struct {}
type mutexLineComponents struct {
    optionLine
    implicitLine
}
type line struct {
    graph.Line
    commonLineComponents
    mutexLineComponents
}

func (e *line) ReversedEdge() graph.Edge {
    rev := e
    rev.Line = e.Line.ReversedLine()
    return rev
}

func (e *line) SetAttribute(attr encoding.Attribute) error {
    switch LineAttributeKey(attr.Key) {
    case L_TYPE:
        e.setType(attr.Value)
    case L_TEXT:
        e.text = attr.Value
    default:
        panic("dot-unmarshal: unknown attribute '#{attr.Key}'")
        return fmt.Errorf("dot-unmarshal: unknown attribute '#{attr.Key}'")
    }
    return nil
}

func (e *line) setType(val string) error {
    switch LineType(val) {
    case EOPTION:
        e.isImplicit = false
        e.isOption = true
    default:
        panic("dot-unmarshal: unknown node type '#{val}'")
        return fmt.Errorf("dot-unmarshal: unknown node type '#{val}'")
    }
    return nil
}

/*
Runtime data hooks to access data at runtime.
These only access pre-parsed data that's in the in-memory graph.
*/

func asNode(n graph.Node) *node {
    node, ok := n.(*node)
    if !ok { panic("error: can't use graph.Node as node") }
    return node
}

func verifiedNode(node *node) *node {
    components := 0
    switch {
    case node.isStart:
        components++
    case node.isEnd:
        components++
    case node.isMessage:
        components++
    case node.isSingleSelectQuestion:
        components++
    case node.isMultipleSelectQuestion:
        components++
    case node.isProgram:
        components++
    }
    if components != 1 {
        panic("error: illegally ambiguous node.")
    }
    return node
}

func (g *dotGraph)lines(e graph.Edge) []*line {
    if e == nil {
        panic("error: nil edge")
    }

    linesObj := g.Lines(e.From().ID(), e.To().ID())
    glines := graph.LinesOf(linesObj)
    var lines []*line
    for _, l := range glines {
        line, ok := l.(*line)
        if !ok { panic("error: can't use graph.Edge as line") }
        components := 0
        switch {
        case line.isOption:
            components++
        case line.isImplicit:
            components++
        }
        if components != 1 { panic("error: illegally ambiguous line") }
        lines = append(lines, line)
    }
    return lines
}

/* demo impl for PROGRAM triggering functionality */

func programs() map[string](func(string)string) {
    return map[string](func(string)string) {
        "513DC7E6-4194-4515-BB47-9F4018ED4D68": randomFortune,
    }
}

func programExec(id string, input string) string {
    return programs()[id](input)
}

func randomFortune(input string) string {
    fortuneCookies := []string {
        "A beautiful, smart, and loving person will be coming into your life.",
        "A dubious friend may be an enemy in camouflage.",
        "A faithful friend is a strong defense.",
        "A feather in the hand is better than a bird in the air.",
        "A fresh start will put you on your way.",
        "A friend asks only for your time not your money.",
        "A friend is a present you give yourself.",
        "A gambler not only will lose what he has, but also will lose what he doesn’t have.",
        "A golden egg of opportunity falls into your lap this month.",
        "A good friendship is often more important than a passionate romance.",
    }
    return fortuneCookies[rand.Intn(len(fortuneCookies))]
}

/* print funcs used in demo */

func (n *node) printInfo() {
    switch {
    case n.isStart:
        fmt.Println("🤖 [" + n.dotID + "]")
    case n.isEnd:
        fmt.Println("🤖 [" + n.dotID + "]")
    case n.isMessage:
        fmt.Println("🤖 [(" + n.dotID + ") bot-msg] " + n.text)
    case n.isSingleSelectQuestion:
        fmt.Println("🤖 [(" + n.dotID + ") opt-sng] " + n.text)
    case n.isMultipleSelectQuestion:
        fmt.Println("🤖 [(" + n.dotID + ") opt-mlt] " + n.text)
        fmt.Println("<elided for demo>")
    case n.isProgram:
        fmt.Println("🤖 [(" + n.dotID + ") program]")
        fmt.Println("$ ./programs/"+n.uid)
        fmt.Println("    '" + programExec(n.uid, "")+"'")
    }
}

func (e *line) printInfo() {
    switch {
    case e.isOption:
        fmt.Println("🙋 \"" + e.text + "\"")
    case e.isImplicit:
        break
    }
}