dot.go

     1  // Copyright 2025 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package unify
     6  
     7  import (
     8  	"bytes"
     9  	"fmt"
    10  	"html"
    11  	"io"
    12  	"os"
    13  	"os/exec"
    14  	"strings"
    15  )
    16  
    17  const maxNodes = 30
    18  
    19  type dotEncoder struct {
    20  	w *bytes.Buffer
    21  
    22  	idGen    int // Node name generation
    23  	valLimit int // Limit the number of Values in a subgraph
    24  
    25  	idp identPrinter
    26  }
    27  
    28  func newDotEncoder() *dotEncoder {
    29  	return &dotEncoder{
    30  		w: new(bytes.Buffer),
    31  	}
    32  }
    33  
    34  func (enc *dotEncoder) clear() {
    35  	enc.w.Reset()
    36  	enc.idGen = 0
    37  }
    38  
    39  func (enc *dotEncoder) writeTo(w io.Writer) {
    40  	fmt.Fprintln(w, "digraph {")
    41  	// Use the "new" ranking algorithm, which lets us put nodes from different
    42  	// clusters in the same rank.
    43  	fmt.Fprintln(w, "newrank=true;")
    44  	fmt.Fprintln(w, "node [shape=box, ordering=out];")
    45  
    46  	w.Write(enc.w.Bytes())
    47  	fmt.Fprintln(w, "}")
    48  }
    49  
    50  func (enc *dotEncoder) writeSvg(w io.Writer) error {
    51  	cmd := exec.Command("dot", "-Tsvg")
    52  	in, err := cmd.StdinPipe()
    53  	if err != nil {
    54  		return err
    55  	}
    56  	var out bytes.Buffer
    57  	cmd.Stdout = &out
    58  	cmd.Stderr = os.Stderr
    59  	if err := cmd.Start(); err != nil {
    60  		return err
    61  	}
    62  	enc.writeTo(in)
    63  	in.Close()
    64  	if err := cmd.Wait(); err != nil {
    65  		return err
    66  	}
    67  	// Trim SVG header so the result can be embedded
    68  	//
    69  	// TODO: In Graphviz 10.0.1, we could use -Tsvg_inline.
    70  	svg := out.Bytes()
    71  	if i := bytes.Index(svg, []byte("<svg ")); i >= 0 {
    72  		svg = svg[i:]
    73  	}
    74  	_, err = w.Write(svg)
    75  	return err
    76  }
    77  
    78  func (enc *dotEncoder) newID(f string) string {
    79  	id := fmt.Sprintf(f, enc.idGen)
    80  	enc.idGen++
    81  	return id
    82  }
    83  
    84  func (enc *dotEncoder) node(label, sublabel string) string {
    85  	id := enc.newID("n%d")
    86  	l := html.EscapeString(label)
    87  	if sublabel != "" {
    88  		l += fmt.Sprintf("<BR ALIGN=\"CENTER\"/><FONT POINT-SIZE=\"10\">%s</FONT>", html.EscapeString(sublabel))
    89  	}
    90  	fmt.Fprintf(enc.w, "%s [label=<%s>];\n", id, l)
    91  	return id
    92  }
    93  
    94  func (enc *dotEncoder) edge(from, to string, label string, args ...any) {
    95  	l := fmt.Sprintf(label, args...)
    96  	fmt.Fprintf(enc.w, "%s -> %s [label=%q];\n", from, to, l)
    97  }
    98  
    99  func (enc *dotEncoder) valueSubgraph(v *Value) {
   100  	enc.valLimit = maxNodes
   101  	cID := enc.newID("cluster_%d")
   102  	fmt.Fprintf(enc.w, "subgraph %s {\n", cID)
   103  	fmt.Fprintf(enc.w, "style=invis;")
   104  	vID := enc.value(v)
   105  	fmt.Fprintf(enc.w, "}\n")
   106  	// We don't need the IDs right now.
   107  	_, _ = cID, vID
   108  }
   109  
   110  func (enc *dotEncoder) value(v *Value) string {
   111  	if enc.valLimit <= 0 {
   112  		id := enc.newID("n%d")
   113  		fmt.Fprintf(enc.w, "%s [label=\"...\", shape=triangle];\n", id)
   114  		return id
   115  	}
   116  	enc.valLimit--
   117  
   118  	switch vd := v.Domain.(type) {
   119  	default:
   120  		panic(fmt.Sprintf("unknown domain type %T", vd))
   121  
   122  	case nil:
   123  		return enc.node("_|_", "")
   124  
   125  	case Top:
   126  		return enc.node("_", "")
   127  
   128  		// TODO: Like in YAML, figure out if this is just a sum. In dot, we
   129  		// could say any unentangled variable is a sum, and if it has more than
   130  		// one reference just share the node.
   131  
   132  	// case Sum:
   133  	// 	node := enc.node("Sum", "")
   134  	// 	for i, elt := range vd.vs {
   135  	// 		enc.edge(node, enc.value(elt), "%d", i)
   136  	// 		if enc.valLimit <= 0 {
   137  	// 			break
   138  	// 		}
   139  	// 	}
   140  	// 	return node
   141  
   142  	case Def:
   143  		node := enc.node("Def", "")
   144  		for k, v := range vd.All() {
   145  			enc.edge(node, enc.value(v), "%s", k)
   146  			if enc.valLimit <= 0 {
   147  				break
   148  			}
   149  		}
   150  		return node
   151  
   152  	case Tuple:
   153  		if vd.repeat == nil {
   154  			label := "Tuple"
   155  			node := enc.node(label, "")
   156  			for i, elt := range vd.vs {
   157  				enc.edge(node, enc.value(elt), "%d", i)
   158  				if enc.valLimit <= 0 {
   159  					break
   160  				}
   161  			}
   162  			return node
   163  		} else {
   164  			// TODO
   165  			return enc.node("TODO: Repeat", "")
   166  		}
   167  
   168  	case String:
   169  		switch vd.kind {
   170  		case stringExact:
   171  			return enc.node(fmt.Sprintf("%q", vd.exact), "")
   172  		case stringRegex:
   173  			var parts []string
   174  			for _, re := range vd.re {
   175  				parts = append(parts, fmt.Sprintf("%q", re))
   176  			}
   177  			return enc.node(strings.Join(parts, "&"), "")
   178  		}
   179  		panic("bad String kind")
   180  
   181  	case Var:
   182  		return enc.node(fmt.Sprintf("Var %s", enc.idp.unique(vd.id)), "")
   183  	}
   184  }
   185  
   186  func (enc *dotEncoder) envSubgraph(e envSet) {
   187  	enc.valLimit = maxNodes
   188  	cID := enc.newID("cluster_%d")
   189  	fmt.Fprintf(enc.w, "subgraph %s {\n", cID)
   190  	fmt.Fprintf(enc.w, "style=invis;")
   191  	vID := enc.env(e.root)
   192  	fmt.Fprintf(enc.w, "}\n")
   193  	_, _ = cID, vID
   194  }
   195  
   196  func (enc *dotEncoder) env(e *envExpr) string {
   197  	switch e.kind {
   198  	default:
   199  		panic("bad kind")
   200  	case envZero:
   201  		return enc.node("0", "")
   202  	case envUnit:
   203  		return enc.node("1", "")
   204  	case envBinding:
   205  		node := enc.node(fmt.Sprintf("%q :", enc.idp.unique(e.id)), "")
   206  		enc.edge(node, enc.value(e.val), "")
   207  		return node
   208  	case envProduct:
   209  		node := enc.node("⨯", "")
   210  		for _, op := range e.operands {
   211  			enc.edge(node, enc.env(op), "")
   212  		}
   213  		return node
   214  	case envSum:
   215  		node := enc.node("+", "")
   216  		for _, op := range e.operands {
   217  			enc.edge(node, enc.env(op), "")
   218  		}
   219  		return node
   220  	}
   221  }
   222
View as plain text