parse.go

     1  // Copyright 2022 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 dag implements a language for expressing directed acyclic
     6  // graphs.
     7  //
     8  // The general syntax of a rule is:
     9  //
    10  //	a, b < c, d;
    11  //
    12  // which means c and d come after a and b in the partial order
    13  // (that is, there are edges from c and d to a and b),
    14  // but doesn't provide a relative order between a vs b or c vs d.
    15  //
    16  // The rules can chain together, as in:
    17  //
    18  //	e < f, g < h;
    19  //
    20  // which is equivalent to
    21  //
    22  //	e < f, g;
    23  //	f, g < h;
    24  //
    25  // Except for the special bottom element "NONE", each name
    26  // must appear exactly once on the right-hand side of any rule.
    27  // That rule serves as the definition of the allowed successor
    28  // for that name. The definition must appear before any uses
    29  // of the name on the left-hand side of a rule. (That is, the
    30  // rules themselves must be ordered according to the partial
    31  // order, for easier reading by people.)
    32  //
    33  // Negative assertions double-check the partial order:
    34  //
    35  //	i !< j
    36  //
    37  // means that it must NOT be the case that i < j.
    38  // Negative assertions may appear anywhere in the rules,
    39  // even before i and j have been defined.
    40  //
    41  // Comments begin with #.
    42  package dag
    43  
    44  import (
    45  	"fmt"
    46  	"sort"
    47  	"strings"
    48  )
    49  
    50  type Graph struct {
    51  	Nodes   []string
    52  	byLabel map[string]int
    53  	edges   map[string]map[string]bool
    54  }
    55  
    56  func newGraph() *Graph {
    57  	return &Graph{byLabel: map[string]int{}, edges: map[string]map[string]bool{}}
    58  }
    59  
    60  func (g *Graph) addNode(label string) bool {
    61  	if _, ok := g.byLabel[label]; ok {
    62  		return false
    63  	}
    64  	g.byLabel[label] = len(g.Nodes)
    65  	g.Nodes = append(g.Nodes, label)
    66  	g.edges[label] = map[string]bool{}
    67  	return true
    68  }
    69  
    70  func (g *Graph) AddEdge(from, to string) {
    71  	g.edges[from][to] = true
    72  }
    73  
    74  func (g *Graph) DelEdge(from, to string) {
    75  	delete(g.edges[from], to)
    76  }
    77  
    78  func (g *Graph) HasEdge(from, to string) bool {
    79  	return g.edges[from] != nil && g.edges[from][to]
    80  }
    81  
    82  func (g *Graph) Edges(from string) []string {
    83  	edges := make([]string, 0, 16)
    84  	for k := range g.edges[from] {
    85  		edges = append(edges, k)
    86  	}
    87  	sort.Slice(edges, func(i, j int) bool { return g.byLabel[edges[i]] < g.byLabel[edges[j]] })
    88  	return edges
    89  }
    90  
    91  // Parse parses the DAG language and returns the transitive closure of
    92  // the described graph. In the returned graph, there is an edge from "b"
    93  // to "a" if b < a (or a > b) in the partial order.
    94  func Parse(dag string) (*Graph, error) {
    95  	g := newGraph()
    96  	disallowed := []rule{}
    97  
    98  	rules, err := parseRules(dag)
    99  	if err != nil {
   100  		return nil, err
   101  	}
   102  
   103  	// TODO: Add line numbers to errors.
   104  	var errors []string
   105  	errorf := func(format string, a ...any) {
   106  		errors = append(errors, fmt.Sprintf(format, a...))
   107  	}
   108  	for _, r := range rules {
   109  		if r.op == "!<" {
   110  			disallowed = append(disallowed, r)
   111  			continue
   112  		}
   113  		for _, def := range r.def {
   114  			if def == "NONE" {
   115  				errorf("NONE cannot be a predecessor")
   116  				continue
   117  			}
   118  			if !g.addNode(def) {
   119  				errorf("multiple definitions for %s", def)
   120  			}
   121  			for _, less := range r.less {
   122  				if less == "NONE" {
   123  					continue
   124  				}
   125  				if _, ok := g.byLabel[less]; !ok {
   126  					errorf("use of %s before its definition", less)
   127  				} else {
   128  					g.AddEdge(def, less)
   129  				}
   130  			}
   131  		}
   132  	}
   133  
   134  	// Check for missing definition.
   135  	for _, tos := range g.edges {
   136  		for to := range tos {
   137  			if g.edges[to] == nil {
   138  				errorf("missing definition for %s", to)
   139  			}
   140  		}
   141  	}
   142  
   143  	// Complete transitive closure.
   144  	for _, k := range g.Nodes {
   145  		for _, i := range g.Nodes {
   146  			for _, j := range g.Nodes {
   147  				if i != k && k != j && g.HasEdge(i, k) && g.HasEdge(k, j) {
   148  					if i == j {
   149  						// Can only happen along with a "use of X before deps" error above,
   150  						// but this error is more specific - it makes clear that reordering the
   151  						// rules will not be enough to fix the problem.
   152  						errorf("graph cycle: %s < %s < %s", j, k, i)
   153  					}
   154  					g.AddEdge(i, j)
   155  				}
   156  			}
   157  		}
   158  	}
   159  
   160  	// Check negative assertions against completed allowed graph.
   161  	for _, bad := range disallowed {
   162  		for _, less := range bad.less {
   163  			for _, def := range bad.def {
   164  				if g.HasEdge(def, less) {
   165  					errorf("graph edge assertion failed: %s !< %s", less, def)
   166  				}
   167  			}
   168  		}
   169  	}
   170  
   171  	if len(errors) > 0 {
   172  		return nil, fmt.Errorf("%s", strings.Join(errors, "\n"))
   173  	}
   174  
   175  	return g, nil
   176  }
   177  
   178  // A rule is a line in the DAG language where "less < def" or "less !< def".
   179  type rule struct {
   180  	less []string
   181  	op   string // Either "<" or "!<"
   182  	def  []string
   183  }
   184  
   185  type syntaxError string
   186  
   187  func (e syntaxError) Error() string {
   188  	return string(e)
   189  }
   190  
   191  // parseRules parses the rules of a DAG.
   192  func parseRules(rules string) (out []rule, err error) {
   193  	defer func() {
   194  		e := recover()
   195  		switch e := e.(type) {
   196  		case nil:
   197  			return
   198  		case syntaxError:
   199  			err = e
   200  		default:
   201  			panic(e)
   202  		}
   203  	}()
   204  	p := &rulesParser{lineno: 1, text: rules}
   205  
   206  	var prev []string
   207  	var op string
   208  	for {
   209  		list, tok := p.nextList()
   210  		if tok == "" {
   211  			if prev == nil {
   212  				break
   213  			}
   214  			p.syntaxError("unexpected EOF")
   215  		}
   216  		if prev != nil {
   217  			out = append(out, rule{prev, op, list})
   218  		}
   219  		prev = list
   220  		if tok == ";" {
   221  			prev = nil
   222  			op = ""
   223  			continue
   224  		}
   225  		if tok != "<" && tok != "!<" {
   226  			p.syntaxError("missing <")
   227  		}
   228  		op = tok
   229  	}
   230  
   231  	return out, err
   232  }
   233  
   234  // A rulesParser parses the depsRules syntax described above.
   235  type rulesParser struct {
   236  	lineno   int
   237  	lastWord string
   238  	text     string
   239  }
   240  
   241  // syntaxError reports a parsing error.
   242  func (p *rulesParser) syntaxError(msg string) {
   243  	panic(syntaxError(fmt.Sprintf("parsing graph: line %d: syntax error: %s near %s", p.lineno, msg, p.lastWord)))
   244  }
   245  
   246  // nextList parses and returns a comma-separated list of names.
   247  func (p *rulesParser) nextList() (list []string, token string) {
   248  	for {
   249  		tok := p.nextToken()
   250  		switch tok {
   251  		case "":
   252  			if len(list) == 0 {
   253  				return nil, ""
   254  			}
   255  			fallthrough
   256  		case ",", "<", "!<", ";":
   257  			p.syntaxError("bad list syntax")
   258  		}
   259  		list = append(list, tok)
   260  
   261  		tok = p.nextToken()
   262  		if tok != "," {
   263  			return list, tok
   264  		}
   265  	}
   266  }
   267  
   268  // nextToken returns the next token in the deps rules,
   269  // one of ";" "," "<" "!<" or a name.
   270  func (p *rulesParser) nextToken() string {
   271  	for {
   272  		if p.text == "" {
   273  			return ""
   274  		}
   275  		switch p.text[0] {
   276  		case ';', ',', '<':
   277  			t := p.text[:1]
   278  			p.text = p.text[1:]
   279  			return t
   280  
   281  		case '!':
   282  			if len(p.text) < 2 || p.text[1] != '<' {
   283  				p.syntaxError("unexpected token !")
   284  			}
   285  			p.text = p.text[2:]
   286  			return "!<"
   287  
   288  		case '#':
   289  			i := strings.Index(p.text, "\n")
   290  			if i < 0 {
   291  				i = len(p.text)
   292  			}
   293  			p.text = p.text[i:]
   294  			continue
   295  
   296  		case '\n':
   297  			p.lineno++
   298  			fallthrough
   299  		case ' ', '\t':
   300  			p.text = p.text[1:]
   301  			continue
   302  
   303  		default:
   304  			i := strings.IndexAny(p.text, "!;,<#\n \t")
   305  			if i < 0 {
   306  				i = len(p.text)
   307  			}
   308  			t := p.text[:i]
   309  			p.text = p.text[i:]
   310  			p.lastWord = t
   311  			return t
   312  		}
   313  	}
   314  }
   315
View as plain text