+++ /dev/null
-// 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 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 strongly connected components (one per line)
- 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 // TODO(deklerk): change bool to struct to reduce memory footprint
-
-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)
- 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
- in := bufio.NewScanner(rd)
- for in.Scan() {
- linenum++
- // Split into words, honoring double-quotes per Go spec.
- words, err := split(in.Text())
- if err != nil {
- return nil, fmt.Errorf("at line %d: %v", linenum, err)
- }
- if len(words) > 0 {
- g.addEdges(words[0], words[1:]...)
- }
- }
- if err := in.Err(); err != nil {
- return nil, err
- }
- return g, nil
-}
-
-// Overridable for testing purposes.
-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")
- }
- for _, scc := range g.sccs() {
- scc.sort().println(" ")
- }
-
- 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()
- }
- }
- }
-}
projects / dotfiles / .git / blobdiff