1// Copyright 2017 syzkaller project authors. All rights reserved.
2// Use of this source code is governed by Apache 2 LICENSE that can be found in the LICENSE file.
3
4package ast
5
6import (
7	"errors"
8	"fmt"
9	"io/ioutil"
10	"path/filepath"
11	"strconv"
12	"strings"
13)
14
15// Parse parses sys description into AST and returns top-level nodes.
16// If any errors are encountered, returns nil.
17func Parse(data []byte, filename string, errorHandler ErrorHandler) *Description {
18	p := &parser{s: newScanner(data, filename, errorHandler)}
19	prevNewLine, prevComment := false, false
20	var top []Node
21	for p.next(); p.tok != tokEOF; {
22		decl := p.parseTopRecover()
23		if decl == nil {
24			continue
25		}
26		// Add new lines around structs, remove duplicate new lines.
27		if _, ok := decl.(*NewLine); ok && prevNewLine {
28			continue
29		}
30		if str, ok := decl.(*Struct); ok && !prevNewLine && !prevComment {
31			top = append(top, &NewLine{Pos: str.Pos})
32		}
33		top = append(top, decl)
34		if str, ok := decl.(*Struct); ok {
35			decl = &NewLine{Pos: str.Pos}
36			top = append(top, decl)
37		}
38		_, prevNewLine = decl.(*NewLine)
39		_, prevComment = decl.(*Comment)
40	}
41	if prevNewLine {
42		top = top[:len(top)-1]
43	}
44	if !p.s.Ok() {
45		return nil
46	}
47	return &Description{top}
48}
49
50func ParseGlob(glob string, errorHandler ErrorHandler) *Description {
51	if errorHandler == nil {
52		errorHandler = LoggingHandler
53	}
54	files, err := filepath.Glob(glob)
55	if err != nil {
56		errorHandler(Pos{}, fmt.Sprintf("failed to find input files: %v", err))
57		return nil
58	}
59	if len(files) == 0 {
60		errorHandler(Pos{}, fmt.Sprintf("no files matched by glob %q", glob))
61		return nil
62	}
63	desc := &Description{}
64	for _, f := range files {
65		data, err := ioutil.ReadFile(f)
66		if err != nil {
67			errorHandler(Pos{}, fmt.Sprintf("failed to read input file: %v", err))
68			return nil
69		}
70		desc1 := Parse(data, filepath.Base(f), errorHandler)
71		if desc1 == nil {
72			desc = nil
73		}
74		if desc != nil {
75			desc.Nodes = append(desc.Nodes, desc1.Nodes...)
76		}
77	}
78	return desc
79}
80
81type parser struct {
82	s *scanner
83
84	// Current token:
85	tok token
86	lit string
87	pos Pos
88}
89
90// Skip parsing till the next NEWLINE, for error recovery.
91var errSkipLine = errors.New("")
92
93func (p *parser) parseTopRecover() Node {
94	defer func() {
95		switch err := recover(); err {
96		case nil:
97		case errSkipLine:
98			// Try to recover by consuming everything until next NEWLINE.
99			for p.tok != tokNewLine && p.tok != tokEOF {
100				p.next()
101			}
102			p.tryConsume(tokNewLine)
103		default:
104			panic(err)
105		}
106	}()
107	decl := p.parseTop()
108	if decl == nil {
109		panic("not reachable")
110	}
111	p.consume(tokNewLine)
112	return decl
113}
114
115func (p *parser) parseTop() Node {
116	switch p.tok {
117	case tokNewLine:
118		return &NewLine{Pos: p.pos}
119	case tokComment:
120		return p.parseComment()
121	case tokDefine:
122		return p.parseDefine()
123	case tokInclude:
124		return p.parseInclude()
125	case tokIncdir:
126		return p.parseIncdir()
127	case tokResource:
128		return p.parseResource()
129	case tokIdent:
130		name := p.parseIdent()
131		if name.Name == "type" {
132			return p.parseTypeDef()
133		}
134		switch p.tok {
135		case tokLParen:
136			return p.parseCall(name)
137		case tokLBrace, tokLBrack:
138			return p.parseStruct(name)
139		case tokEq:
140			return p.parseFlags(name)
141		default:
142			p.expect(tokLParen, tokLBrace, tokLBrack, tokEq)
143		}
144	case tokIllegal:
145		// Scanner has already producer an error for this one.
146		panic(errSkipLine)
147	default:
148		p.expect(tokComment, tokDefine, tokInclude, tokResource, tokIdent)
149	}
150	panic("not reachable")
151}
152
153func (p *parser) next() {
154	p.tok, p.lit, p.pos = p.s.Scan()
155}
156
157func (p *parser) consume(tok token) {
158	p.expect(tok)
159	p.next()
160}
161
162func (p *parser) tryConsume(tok token) bool {
163	if p.tok != tok {
164		return false
165	}
166	p.next()
167	return true
168}
169
170func (p *parser) expect(tokens ...token) {
171	for _, tok := range tokens {
172		if p.tok == tok {
173			return
174		}
175	}
176	var str []string
177	for _, tok := range tokens {
178		str = append(str, tok.String())
179	}
180	p.s.Error(p.pos, fmt.Sprintf("unexpected %v, expecting %v", p.tok, strings.Join(str, ", ")))
181	panic(errSkipLine)
182}
183
184func (p *parser) parseComment() *Comment {
185	c := &Comment{
186		Pos:  p.pos,
187		Text: p.lit,
188	}
189	p.consume(tokComment)
190	return c
191}
192
193func (p *parser) parseDefine() *Define {
194	pos0 := p.pos
195	p.consume(tokDefine)
196	name := p.parseIdent()
197	p.expect(tokInt, tokIdent, tokCExpr)
198	var val *Int
199	if p.tok == tokCExpr {
200		val = p.parseCExpr()
201	} else {
202		val = p.parseInt()
203	}
204	return &Define{
205		Pos:   pos0,
206		Name:  name,
207		Value: val,
208	}
209}
210
211func (p *parser) parseInclude() *Include {
212	pos0 := p.pos
213	p.consume(tokInclude)
214	return &Include{
215		Pos:  pos0,
216		File: p.parseString(),
217	}
218}
219
220func (p *parser) parseIncdir() *Incdir {
221	pos0 := p.pos
222	p.consume(tokIncdir)
223	return &Incdir{
224		Pos: pos0,
225		Dir: p.parseString(),
226	}
227}
228
229func (p *parser) parseResource() *Resource {
230	pos0 := p.pos
231	p.consume(tokResource)
232	name := p.parseIdent()
233	p.consume(tokLBrack)
234	base := p.parseType()
235	p.consume(tokRBrack)
236	var values []*Int
237	if p.tryConsume(tokColon) {
238		values = append(values, p.parseInt())
239		for p.tryConsume(tokComma) {
240			values = append(values, p.parseInt())
241		}
242	}
243	return &Resource{
244		Pos:    pos0,
245		Name:   name,
246		Base:   base,
247		Values: values,
248	}
249}
250
251func (p *parser) parseTypeDef() *TypeDef {
252	pos0 := p.pos
253	name := p.parseIdent()
254	var typ *Type
255	var str *Struct
256	var args []*Ident
257	p.expect(tokLBrack, tokIdent)
258	if p.tryConsume(tokLBrack) {
259		args = append(args, p.parseIdent())
260		for p.tryConsume(tokComma) {
261			args = append(args, p.parseIdent())
262		}
263		p.consume(tokRBrack)
264		if p.tok == tokLBrace || p.tok == tokLBrack {
265			emptyName := &Ident{
266				Pos:  pos0,
267				Name: "",
268			}
269			str = p.parseStruct(emptyName)
270		} else {
271			typ = p.parseType()
272		}
273	} else {
274		typ = p.parseType()
275	}
276	return &TypeDef{
277		Pos:    pos0,
278		Name:   name,
279		Args:   args,
280		Type:   typ,
281		Struct: str,
282	}
283}
284
285func (p *parser) parseCall(name *Ident) *Call {
286	c := &Call{
287		Pos:      name.Pos,
288		Name:     name,
289		CallName: callName(name.Name),
290	}
291	p.consume(tokLParen)
292	for p.tok != tokRParen {
293		c.Args = append(c.Args, p.parseField())
294		p.expect(tokComma, tokRParen)
295		p.tryConsume(tokComma)
296	}
297	p.consume(tokRParen)
298	if p.tok != tokNewLine {
299		c.Ret = p.parseType()
300	}
301	return c
302}
303
304func callName(s string) string {
305	pos := strings.IndexByte(s, '$')
306	if pos == -1 {
307		return s
308	}
309	return s[:pos]
310}
311
312func (p *parser) parseFlags(name *Ident) Node {
313	p.consume(tokEq)
314	switch p.tok {
315	case tokInt, tokIdent:
316		return p.parseIntFlags(name)
317	case tokString:
318		return p.parseStrFlags(name)
319	default:
320		p.expect(tokInt, tokIdent, tokString)
321		return nil
322	}
323}
324
325func (p *parser) parseIntFlags(name *Ident) *IntFlags {
326	values := []*Int{p.parseInt()}
327	for p.tryConsume(tokComma) {
328		values = append(values, p.parseInt())
329	}
330	return &IntFlags{
331		Pos:    name.Pos,
332		Name:   name,
333		Values: values,
334	}
335}
336
337func (p *parser) parseStrFlags(name *Ident) *StrFlags {
338	values := []*String{p.parseString()}
339	for p.tryConsume(tokComma) {
340		values = append(values, p.parseString())
341	}
342	return &StrFlags{
343		Pos:    name.Pos,
344		Name:   name,
345		Values: values,
346	}
347}
348
349func (p *parser) parseStruct(name *Ident) *Struct {
350	str := &Struct{
351		Pos:  name.Pos,
352		Name: name,
353	}
354	closing := tokRBrace
355	if p.tok == tokLBrack {
356		str.IsUnion = true
357		closing = tokRBrack
358	}
359	p.next()
360	p.consume(tokNewLine)
361	for {
362		newBlock := false
363		for p.tok == tokNewLine {
364			newBlock = true
365			p.next()
366		}
367		comments := p.parseCommentBlock()
368		if p.tryConsume(closing) {
369			str.Comments = comments
370			break
371		}
372		fld := p.parseField()
373		fld.NewBlock = newBlock
374		fld.Comments = comments
375		str.Fields = append(str.Fields, fld)
376		p.consume(tokNewLine)
377	}
378	if p.tryConsume(tokLBrack) {
379		str.Attrs = append(str.Attrs, p.parseType())
380		for p.tryConsume(tokComma) {
381			str.Attrs = append(str.Attrs, p.parseType())
382		}
383		p.consume(tokRBrack)
384	}
385	return str
386}
387
388func (p *parser) parseCommentBlock() []*Comment {
389	var comments []*Comment
390	for p.tok == tokComment {
391		comments = append(comments, p.parseComment())
392		p.consume(tokNewLine)
393		for p.tryConsume(tokNewLine) {
394		}
395	}
396	return comments
397}
398
399func (p *parser) parseField() *Field {
400	name := p.parseIdent()
401	return &Field{
402		Pos:  name.Pos,
403		Name: name,
404		Type: p.parseType(),
405	}
406}
407
408func (p *parser) parseType() *Type {
409	arg := &Type{
410		Pos: p.pos,
411	}
412	allowColon := false
413	switch p.tok {
414	case tokInt:
415		allowColon = true
416		arg.Value, arg.ValueFmt = p.parseIntValue()
417	case tokIdent:
418		allowColon = true
419		arg.Ident = p.lit
420	case tokString:
421		arg.String = p.lit
422		arg.HasString = true
423	default:
424		p.expect(tokInt, tokIdent, tokString)
425	}
426	p.next()
427	if allowColon && p.tryConsume(tokColon) {
428		arg.HasColon = true
429		arg.Pos2 = p.pos
430		switch p.tok {
431		case tokInt:
432			arg.Value2, arg.Value2Fmt = p.parseIntValue()
433		case tokIdent:
434			arg.Ident2 = p.lit
435		default:
436			p.expect(tokInt, tokIdent)
437		}
438		p.next()
439	}
440	arg.Args = p.parseTypeList()
441	return arg
442}
443
444func (p *parser) parseTypeList() []*Type {
445	var args []*Type
446	if p.tryConsume(tokLBrack) {
447		args = append(args, p.parseType())
448		for p.tryConsume(tokComma) {
449			args = append(args, p.parseType())
450		}
451		p.consume(tokRBrack)
452	}
453	return args
454}
455
456func (p *parser) parseIdent() *Ident {
457	p.expect(tokIdent)
458	ident := &Ident{
459		Pos:  p.pos,
460		Name: p.lit,
461	}
462	p.next()
463	return ident
464}
465
466func (p *parser) parseString() *String {
467	p.expect(tokString)
468	str := &String{
469		Pos:   p.pos,
470		Value: p.lit,
471	}
472	p.next()
473	return str
474}
475
476func (p *parser) parseInt() *Int {
477	i := &Int{
478		Pos: p.pos,
479	}
480	switch p.tok {
481	case tokInt:
482		i.Value, i.ValueFmt = p.parseIntValue()
483	case tokIdent:
484		i.Ident = p.lit
485	default:
486		p.expect(tokInt, tokIdent)
487	}
488	p.next()
489	return i
490}
491
492func (p *parser) parseIntValue() (uint64, IntFmt) {
493	if p.lit[0] == '\'' {
494		return uint64(p.lit[1]), IntFmtChar
495	}
496	if v, err := strconv.ParseUint(p.lit, 10, 64); err == nil {
497		return v, IntFmtDec
498	}
499	if v, err := strconv.ParseInt(p.lit, 10, 64); err == nil {
500		return uint64(v), IntFmtNeg
501	}
502	if len(p.lit) > 2 && p.lit[0] == '0' && p.lit[1] == 'x' {
503		if v, err := strconv.ParseUint(p.lit[2:], 16, 64); err == nil {
504			return v, IntFmtHex
505		}
506	}
507	panic(fmt.Sprintf("scanner returned bad integer %q", p.lit))
508}
509
510func (p *parser) parseCExpr() *Int {
511	i := &Int{
512		Pos:   p.pos,
513		CExpr: p.lit,
514	}
515	p.consume(tokCExpr)
516	return i
517}
518