| // Copyright 2019 The Go Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style |
| // license that can be found in the LICENSE file. |
| |
| /* |
| The digraph command performs queries over unlabelled directed graphs |
| represented in text form. It is intended to integrate nicely with |
| typical UNIX command pipelines. |
| |
| Usage: |
| |
| your-application | digraph [command] |
| |
| The support commands are: |
| |
| nodes |
| the set of all nodes |
| degree |
| the in-degree and out-degree of each node |
| transpose |
| the reverse of the input edges |
| preds <node> ... |
| the set of immediate predecessors of the specified nodes |
| succs <node> ... |
| the set of immediate successors of the specified nodes |
| forward <node> ... |
| the set of nodes transitively reachable from the specified nodes |
| reverse <node> ... |
| the set of nodes that transitively reach the specified nodes |
| somepath <node> <node> |
| the list of nodes on some arbitrary path from the first node to the second |
| allpaths <node> <node> |
| the set of nodes on all paths from the first node to the second |
| sccs |
| all strongly connected components (one per line) |
| scc <node> |
| the set of nodes strongly connected to the specified one |
| focus <node> |
| the subgraph containing all directed paths that pass through the specified node |
| |
| Input format: |
| |
| Each line contains zero or more words. Words are separated by unquoted |
| whitespace; words may contain Go-style double-quoted portions, allowing spaces |
| and other characters to be expressed. |
| |
| Each word declares a node, and if there are more than one, an edge from the |
| first to each subsequent one. The graph is provided on the standard input. |
| |
| For instance, the following (acyclic) graph specifies a partial order among the |
| subtasks of getting dressed: |
| |
| $ cat clothes.txt |
| socks shoes |
| "boxer shorts" pants |
| pants belt shoes |
| shirt tie sweater |
| sweater jacket |
| hat |
| |
| The line "shirt tie sweater" indicates the two edges shirt -> tie and |
| shirt -> sweater, not shirt -> tie -> sweater. |
| |
| Example usage: |
| |
| Using digraph with existing Go tools: |
| |
| $ go mod graph | digraph nodes # Operate on the Go module graph. |
| $ go list -m all | digraph nodes # Operate on the Go package graph. |
| |
| Show the transitive closure of imports of the digraph tool itself: |
| |
| $ go list -f '{{.ImportPath}} {{join .Imports " "}}' ... | digraph forward golang.org/x/tools/cmd/digraph |
| |
| Show which clothes (see above) must be donned before a jacket: |
| |
| $ digraph reverse jacket |
| */ |
| package main // import "golang.org/x/tools/cmd/digraph" |
| |
| // TODO(adonovan): |
| // - support input files other than stdin |
| // - support alternative formats (AT&T GraphViz, CSV, etc), |
| // a comment syntax, etc. |
| // - allow queries to nest, like Blaze query language. |
| |
| import ( |
| "bufio" |
| "bytes" |
| "errors" |
| "flag" |
| "fmt" |
| "io" |
| "os" |
| "sort" |
| "strconv" |
| "strings" |
| "unicode" |
| "unicode/utf8" |
| ) |
| |
| func usage() { |
| fmt.Fprintf(os.Stderr, `Usage: your-application | digraph [command] |
| |
| The support commands are: |
| nodes |
| the set of all nodes |
| degree |
| the in-degree and out-degree of each node |
| transpose |
| the reverse of the input edges |
| preds <node> ... |
| the set of immediate predecessors of the specified nodes |
| succs <node> ... |
| the set of immediate successors of the specified nodes |
| forward <node> ... |
| the set of nodes transitively reachable from the specified nodes |
| reverse <node> ... |
| the set of nodes that transitively reach the specified nodes |
| somepath <node> <node> |
| the list of nodes on some arbitrary path from the first node to the second |
| allpaths <node> <node> |
| the set of nodes on all paths from the first node to the second |
| sccs |
| all non-trivial strongly connected components, one per line |
| (single-node components are only printed for nodes with self-loops) |
| scc <node> |
| the set of nodes nodes strongly connected to the specified one |
| focus <node> |
| the subgraph containing all directed paths that pass through the specified node |
| `) |
| os.Exit(2) |
| } |
| |
| func main() { |
| flag.Usage = usage |
| flag.Parse() |
| |
| args := flag.Args() |
| if len(args) == 0 { |
| usage() |
| } |
| |
| if err := digraph(args[0], args[1:]); err != nil { |
| fmt.Fprintf(os.Stderr, "digraph: %s\n", err) |
| os.Exit(1) |
| } |
| } |
| |
| type nodelist []string |
| |
| func (l nodelist) println(sep string) { |
| for i, node := range l { |
| if i > 0 { |
| fmt.Fprint(stdout, sep) |
| } |
| fmt.Fprint(stdout, node) |
| } |
| fmt.Fprintln(stdout) |
| } |
| |
| type nodeset map[string]bool |
| |
| func (s nodeset) sort() nodelist { |
| nodes := make(nodelist, len(s)) |
| var i int |
| for node := range s { |
| nodes[i] = node |
| i++ |
| } |
| sort.Strings(nodes) |
| return nodes |
| } |
| |
| func (s nodeset) addAll(x nodeset) { |
| for node := range x { |
| s[node] = true |
| } |
| } |
| |
| // A graph maps nodes to the non-nil set of their immediate successors. |
| type graph map[string]nodeset |
| |
| func (g graph) addNode(node string) nodeset { |
| edges := g[node] |
| if edges == nil { |
| edges = make(nodeset) |
| g[node] = edges |
| } |
| return edges |
| } |
| |
| func (g graph) addEdges(from string, to ...string) { |
| edges := g.addNode(from) |
| for _, to := range to { |
| g.addNode(to) |
| edges[to] = true |
| } |
| } |
| |
| func (g graph) reachableFrom(roots nodeset) nodeset { |
| seen := make(nodeset) |
| var visit func(node string) |
| visit = func(node string) { |
| if !seen[node] { |
| seen[node] = true |
| for e := range g[node] { |
| visit(e) |
| } |
| } |
| } |
| for root := range roots { |
| visit(root) |
| } |
| return seen |
| } |
| |
| func (g graph) transpose() graph { |
| rev := make(graph) |
| for node, edges := range g { |
| rev.addNode(node) |
| for succ := range edges { |
| rev.addEdges(succ, node) |
| } |
| } |
| return rev |
| } |
| |
| func (g graph) sccs() []nodeset { |
| // Kosaraju's algorithm---Tarjan is overkill here. |
| |
| // Forward pass. |
| S := make(nodelist, 0, len(g)) // postorder stack |
| seen := make(nodeset) |
| var visit func(node string) |
| visit = func(node string) { |
| if !seen[node] { |
| seen[node] = true |
| for e := range g[node] { |
| visit(e) |
| } |
| S = append(S, node) |
| } |
| } |
| for node := range g { |
| visit(node) |
| } |
| |
| // Reverse pass. |
| rev := g.transpose() |
| var scc nodeset |
| seen = make(nodeset) |
| var rvisit func(node string) |
| rvisit = func(node string) { |
| if !seen[node] { |
| seen[node] = true |
| scc[node] = true |
| for e := range rev[node] { |
| rvisit(e) |
| } |
| } |
| } |
| var sccs []nodeset |
| for len(S) > 0 { |
| top := S[len(S)-1] |
| S = S[:len(S)-1] // pop |
| if !seen[top] { |
| scc = make(nodeset) |
| rvisit(top) |
| if len(scc) == 1 && !g[top][top] { |
| continue |
| } |
| sccs = append(sccs, scc) |
| } |
| } |
| return sccs |
| } |
| |
| func (g graph) allpaths(from, to string) error { |
| // Mark all nodes to "to". |
| seen := make(nodeset) // value of seen[x] indicates whether x is on some path to "to" |
| var visit func(node string) bool |
| visit = func(node string) bool { |
| reachesTo, ok := seen[node] |
| if !ok { |
| reachesTo = node == to |
| seen[node] = reachesTo |
| for e := range g[node] { |
| if visit(e) { |
| reachesTo = true |
| } |
| } |
| if reachesTo && node != to { |
| seen[node] = true |
| } |
| } |
| return reachesTo |
| } |
| visit(from) |
| |
| // For each marked node, collect its marked successors. |
| var edges []string |
| for n := range seen { |
| for succ := range g[n] { |
| if seen[succ] { |
| edges = append(edges, n+" "+succ) |
| } |
| } |
| } |
| |
| // Sort (so that this method is deterministic) and print edges. |
| sort.Strings(edges) |
| for _, e := range edges { |
| fmt.Fprintln(stdout, e) |
| } |
| |
| return nil |
| } |
| |
| func (g graph) somepath(from, to string) error { |
| type edge struct{ from, to string } |
| seen := make(nodeset) |
| var dfs func(path []edge, from string) bool |
| dfs = func(path []edge, from string) bool { |
| if !seen[from] { |
| seen[from] = true |
| if from == to { |
| // fmt.Println(path, len(path), cap(path)) |
| // Print and unwind. |
| for _, e := range path { |
| fmt.Fprintln(stdout, e.from+" "+e.to) |
| } |
| return true |
| } |
| for e := range g[from] { |
| if dfs(append(path, edge{from: from, to: e}), e) { |
| return true |
| } |
| } |
| } |
| return false |
| } |
| maxEdgesInGraph := len(g) * (len(g) - 1) |
| if !dfs(make([]edge, 0, maxEdgesInGraph), from) { |
| return fmt.Errorf("no path from %q to %q", from, to) |
| } |
| return nil |
| } |
| |
| func parse(rd io.Reader) (graph, error) { |
| g := make(graph) |
| |
| var linenum int |
| // We avoid bufio.Scanner as it imposes a (configurable) limit |
| // on line length, whereas Reader.ReadString does not. |
| in := bufio.NewReader(rd) |
| for { |
| linenum++ |
| line, err := in.ReadString('\n') |
| eof := false |
| if err == io.EOF { |
| eof = true |
| } else if err != nil { |
| return nil, err |
| } |
| // Split into words, honoring double-quotes per Go spec. |
| words, err := split(line) |
| if err != nil { |
| return nil, fmt.Errorf("at line %d: %v", linenum, err) |
| } |
| if len(words) > 0 { |
| g.addEdges(words[0], words[1:]...) |
| } |
| if eof { |
| break |
| } |
| } |
| return g, nil |
| } |
| |
| // Overridable for redirection. |
| var stdin io.Reader = os.Stdin |
| var stdout io.Writer = os.Stdout |
| |
| func digraph(cmd string, args []string) error { |
| // Parse the input graph. |
| g, err := parse(stdin) |
| if err != nil { |
| return err |
| } |
| |
| // Parse the command line. |
| switch cmd { |
| case "nodes": |
| if len(args) != 0 { |
| return fmt.Errorf("usage: digraph nodes") |
| } |
| nodes := make(nodeset) |
| for node := range g { |
| nodes[node] = true |
| } |
| nodes.sort().println("\n") |
| |
| case "degree": |
| if len(args) != 0 { |
| return fmt.Errorf("usage: digraph degree") |
| } |
| nodes := make(nodeset) |
| for node := range g { |
| nodes[node] = true |
| } |
| rev := g.transpose() |
| for _, node := range nodes.sort() { |
| fmt.Fprintf(stdout, "%d\t%d\t%s\n", len(rev[node]), len(g[node]), node) |
| } |
| |
| case "transpose": |
| if len(args) != 0 { |
| return fmt.Errorf("usage: digraph transpose") |
| } |
| var revEdges []string |
| for node, succs := range g.transpose() { |
| for succ := range succs { |
| revEdges = append(revEdges, fmt.Sprintf("%s %s", node, succ)) |
| } |
| } |
| sort.Strings(revEdges) // make output deterministic |
| for _, e := range revEdges { |
| fmt.Fprintln(stdout, e) |
| } |
| |
| case "succs", "preds": |
| if len(args) == 0 { |
| return fmt.Errorf("usage: digraph %s <node> ... ", cmd) |
| } |
| g := g |
| if cmd == "preds" { |
| g = g.transpose() |
| } |
| result := make(nodeset) |
| for _, root := range args { |
| edges := g[root] |
| if edges == nil { |
| return fmt.Errorf("no such node %q", root) |
| } |
| result.addAll(edges) |
| } |
| result.sort().println("\n") |
| |
| case "forward", "reverse": |
| if len(args) == 0 { |
| return fmt.Errorf("usage: digraph %s <node> ... ", cmd) |
| } |
| roots := make(nodeset) |
| for _, root := range args { |
| if g[root] == nil { |
| return fmt.Errorf("no such node %q", root) |
| } |
| roots[root] = true |
| } |
| g := g |
| if cmd == "reverse" { |
| g = g.transpose() |
| } |
| g.reachableFrom(roots).sort().println("\n") |
| |
| case "somepath": |
| if len(args) != 2 { |
| return fmt.Errorf("usage: digraph somepath <from> <to>") |
| } |
| from, to := args[0], args[1] |
| if g[from] == nil { |
| return fmt.Errorf("no such 'from' node %q", from) |
| } |
| if g[to] == nil { |
| return fmt.Errorf("no such 'to' node %q", to) |
| } |
| if err := g.somepath(from, to); err != nil { |
| return err |
| } |
| |
| case "allpaths": |
| if len(args) != 2 { |
| return fmt.Errorf("usage: digraph allpaths <from> <to>") |
| } |
| from, to := args[0], args[1] |
| if g[from] == nil { |
| return fmt.Errorf("no such 'from' node %q", from) |
| } |
| if g[to] == nil { |
| return fmt.Errorf("no such 'to' node %q", to) |
| } |
| if err := g.allpaths(from, to); err != nil { |
| return err |
| } |
| |
| case "sccs": |
| if len(args) != 0 { |
| return fmt.Errorf("usage: digraph sccs") |
| } |
| buf := new(bytes.Buffer) |
| oldStdout := stdout |
| stdout = buf |
| for _, scc := range g.sccs() { |
| scc.sort().println(" ") |
| } |
| lines := strings.SplitAfter(buf.String(), "\n") |
| sort.Strings(lines) |
| stdout = oldStdout |
| io.WriteString(stdout, strings.Join(lines, "")) |
| |
| case "scc": |
| if len(args) != 1 { |
| return fmt.Errorf("usage: digraph scc <node>") |
| } |
| node := args[0] |
| if g[node] == nil { |
| return fmt.Errorf("no such node %q", node) |
| } |
| for _, scc := range g.sccs() { |
| if scc[node] { |
| scc.sort().println("\n") |
| break |
| } |
| } |
| |
| case "focus": |
| if len(args) != 1 { |
| return fmt.Errorf("usage: digraph focus <node>") |
| } |
| node := args[0] |
| if g[node] == nil { |
| return fmt.Errorf("no such node %q", node) |
| } |
| |
| edges := make(map[string]struct{}) |
| for from := range g.reachableFrom(nodeset{node: true}) { |
| for to := range g[from] { |
| edges[fmt.Sprintf("%s %s", from, to)] = struct{}{} |
| } |
| } |
| |
| gtrans := g.transpose() |
| for from := range gtrans.reachableFrom(nodeset{node: true}) { |
| for to := range gtrans[from] { |
| edges[fmt.Sprintf("%s %s", to, from)] = struct{}{} |
| } |
| } |
| |
| edgesSorted := make([]string, 0, len(edges)) |
| for e := range edges { |
| edgesSorted = append(edgesSorted, e) |
| } |
| sort.Strings(edgesSorted) |
| fmt.Fprintln(stdout, strings.Join(edgesSorted, "\n")) |
| |
| default: |
| return fmt.Errorf("no such command %q", cmd) |
| } |
| |
| return nil |
| } |
| |
| // -- Utilities -------------------------------------------------------- |
| |
| // split splits a line into words, which are generally separated by |
| // spaces, but Go-style double-quoted string literals are also supported. |
| // (This approximates the behaviour of the Bourne shell.) |
| // |
| // `one "two three"` -> ["one" "two three"] |
| // `a"\n"b` -> ["a\nb"] |
| func split(line string) ([]string, error) { |
| var ( |
| words []string |
| inWord bool |
| current bytes.Buffer |
| ) |
| |
| for len(line) > 0 { |
| r, size := utf8.DecodeRuneInString(line) |
| if unicode.IsSpace(r) { |
| if inWord { |
| words = append(words, current.String()) |
| current.Reset() |
| inWord = false |
| } |
| } else if r == '"' { |
| var ok bool |
| size, ok = quotedLength(line) |
| if !ok { |
| return nil, errors.New("invalid quotation") |
| } |
| s, err := strconv.Unquote(line[:size]) |
| if err != nil { |
| return nil, err |
| } |
| current.WriteString(s) |
| inWord = true |
| } else { |
| current.WriteRune(r) |
| inWord = true |
| } |
| line = line[size:] |
| } |
| if inWord { |
| words = append(words, current.String()) |
| } |
| return words, nil |
| } |
| |
| // quotedLength returns the length in bytes of the prefix of input that |
| // contain a possibly-valid double-quoted Go string literal. |
| // |
| // On success, n is at least two (""); input[:n] may be passed to |
| // strconv.Unquote to interpret its value, and input[n:] contains the |
| // rest of the input. |
| // |
| // On failure, quotedLength returns false, and the entire input can be |
| // passed to strconv.Unquote if an informative error message is desired. |
| // |
| // quotedLength does not and need not detect all errors, such as |
| // invalid hex or octal escape sequences, since it assumes |
| // strconv.Unquote will be applied to the prefix. It guarantees only |
| // that if there is a prefix of input containing a valid string literal, |
| // its length is returned. |
| // |
| // TODO(adonovan): move this into a strconv-like utility package. |
| func quotedLength(input string) (n int, ok bool) { |
| var offset int |
| |
| // next returns the rune at offset, or -1 on EOF. |
| // offset advances to just after that rune. |
| next := func() rune { |
| if offset < len(input) { |
| r, size := utf8.DecodeRuneInString(input[offset:]) |
| offset += size |
| return r |
| } |
| return -1 |
| } |
| |
| if next() != '"' { |
| return // error: not a quotation |
| } |
| |
| for { |
| r := next() |
| if r == '\n' || r < 0 { |
| return // error: string literal not terminated |
| } |
| if r == '"' { |
| return offset, true // success |
| } |
| if r == '\\' { |
| var skip int |
| switch next() { |
| case 'a', 'b', 'f', 'n', 'r', 't', 'v', '\\', '"': |
| skip = 0 |
| case '0', '1', '2', '3', '4', '5', '6', '7': |
| skip = 2 |
| case 'x': |
| skip = 2 |
| case 'u': |
| skip = 4 |
| case 'U': |
| skip = 8 |
| default: |
| return // error: invalid escape |
| } |
| |
| for i := 0; i < skip; i++ { |
| next() |
| } |
| } |
| } |
| } |