backend/parser.go

// Copyright 2021 The Fuchsia Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

package main

import (
	"regexp"
	"strconv"
	"strings"

	"github.com/alecthomas/participle/v2"
	"github.com/alecthomas/participle/v2/lexer"
)

// This file is based on the official FIDL grammar:
// https://fuchsia.dev/fuchsia-src/reference/fidl/language/grammar
//
// It uses the participle parser library:
// https://github.com/alecthomas/participle
//
// A quick primer on participle:
//
// - It has separate lexing and parsing stages.
// - Lexer tokens are defined by regexes.
// - Productions are defined by structs with tags on each field.
// - The tags get concatenated (e.g. parens can be unbalanced within a tag).
// - Tags have the format `<exp1> <exp2> ... <expN>`.
// - Expression `"foo"` matches the literal "foo".
// - Expression `Foo` matches a Foo token.
// - Expression `@<exp>` captures <exp> into the field.
// - Expression `@@` recursively captures based on the field's type.
// - Tags for slice types can have multiple captures.
// - Boolean fields become true if a capture occurred.
// - Parentheses, `?`, `+`, `*`, `|` behave as expected.

var (
	fidlLexer = lexer.MustSimple([]lexer.Rule{
		{Name: "Whitespace", Pattern: `[ \n\r\t]`},
		{Name: "Comment", Pattern: `//[^\n]*`},
		{Name: "Punctuation", Pattern: "[.,;@=()]"},
		{Name: "Keyword", Pattern: `library|using|as`},
		{Name: "Bool", Pattern: `true|false`},
		{Name: "String", Pattern: `"(\\.|[^"\\])*"`},
		// This pattern matches the FIDL lexer, which defers more precise
		// numeric parsing to the flat AST stage.
		{Name: "Number", Pattern: `[0-9][0-9a-fA-FxX._\-]*`},
		// https://fuchsia.dev/fuchsia-src/reference/fidl/language/language?hl=en#identifiers
		{Name: "Identifier", Pattern: `[a-zA-Z]([a-zA-Z0-9_]*[a-zA-Z0-9])?`},
		// Define a fallback token so that the lexer never fails and we can
		// ignore the rest of the file (see the Rest field in fidlTopLevel).
		{Name: "Other", Pattern: `.*`},
	})

	fidlParser = participle.MustBuild(
		&fidlTopLevel{},
		participle.Lexer(fidlLexer),
		participle.Elide("Whitespace", "Comment"),
	)
)

type fidlTopLevel struct {
	Header fidlLibraryHeader `@@`
	Using  []fidlUsing       `@@*`
	// Ignore the rest of the file by matching 0+ tokens of any kind. Rather
	// than list every token type, we say ~"" (anything not equal to "").
	Rest bool `(@~"")*`
}

type fidlLibraryHeader struct {
	Attributes []fidlAttribute        `@@*`
	Library    fidlCompoundIdentifier `"library" @@ ";"`
}

type fidlUsing struct {
	Library fidlCompoundIdentifier `"using" @@`
	Alias   bool                   `("as" @Identifier)? ";"`
}

type fidlAttribute struct {
	Name bool               `"@" @Identifier`
	Args []fidlAttributeArg `("(" @@ ("," @@)* ")")?`
}

type fidlAttributeArg struct {
	Name  bool         `(@Identifier "=")?`
	Value fidlConstant `@@`
}

type fidlConstant struct {
	Identifier *fidlCompoundIdentifier `@@`
	Literal    bool                    `| @String | @Number | @Bool`
}

type fidlCompoundIdentifier struct {
	// Note: The field must be named "Pos" for participle to recognize it.
	Pos   lexer.Position
	Parts []string `@Identifier ("." @Identifier)*`
}

// Note: fields exported for cmp.Diff.
type parsedFidl struct {
	Decl  parsedLibrary
	Using []parsedLibrary
}

// Note: fields exported for cmp.Diff.
type parsedLibrary struct {
	Library      library
	Line, Column int
}

func parseFidl(input string) (parsedFidl, error) {
	var (
		top      fidlTopLevel
		parsed   parsedFidl
		filename = ""
	)
	err := fidlParser.ParseString(filename, input, &top)
	if err != nil {
		return parsed, err
	}
	parsed.Decl = toParsedLibrary(top.Header.Library)
	for _, using := range top.Using {
		parsed.Using = append(parsed.Using, toParsedLibrary(using.Library))
	}
	return parsed, nil
}

func toParsedLibrary(ident fidlCompoundIdentifier) parsedLibrary {
	return parsedLibrary{
		Library: library(strings.Join(ident.Parts, ".")),
		Line:    ident.Pos.Line,
		Column:  ident.Pos.Column,
	}
}

func (m *parsedLibrary) annotation(kind annotationKind, text string) annotation {
	return annotation{
		Line:   m.Line,
		Column: m.Column,
		Kind:   kind,
		Text:   text,
	}
}

var fidlAnnotationRegexp = regexp.MustCompile(`` +
	// Multi-line mode: ^ and $ match begin/end of line OR text.
	`(?m)` +
	`^/.*/fidlbolt\.fidl:(\d+):(\d+).*?` +
	`(` +
	string(Info) + `|` +
	string(Warning) + `|` +
	string(Error) + `)` +
	`:\s*(.*)$`)

// parseFidlAnnotations parses a list of annotations from error output. It
// assumes that the output refers to a file called "fidlbolt.fidl".
// TODO: Use fidlc --format=json instead of regex parsing.
func parseFidlAnnotations(output string) []annotation {
	matches := fidlAnnotationRegexp.FindAllStringSubmatch(output, -1)
	var anns []annotation
	for _, m := range matches {
		line, err := strconv.Atoi(m[1])
		if err != nil {
			continue
		}
		column, err := strconv.Atoi(m[2])
		if err != nil {
			continue
		}
		anns = append(anns, annotation{
			Line:   line,
			Column: column,
			Kind:   annotationKind(m[3]),
			Text:   m[4],
		})
	}
	return anns
}