backend/library.go - fidlbolt - Git at Google

 // Copyright 2020 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 (
 	"bytes"
 	"errors"
 	"fmt"
 	"io/ioutil"
 	"os"
 	"path/filepath"
 	"regexp"
 	"strings"
 	"sync"
 )

 // A library is a FIDL library represented by its name (as spelled in its
 // "library" declaration, not necessarily matching directory or file names).
 type library string

 // The zx library describes Zircon syscalls.
 const zxLibrary library = "zx"

 // A libraryMap stores information derived about a group of libraries.
 type libraryMap map[library]libraryInfo

 type libraryInfo struct {
 	// Directory containing the library.
 	dir string
 	// FIDL files that make up the library (relative to dir, or absolute).
 	files []string
 	// Direct dependencies (imported by "using" declarations in files).
 	deps []library
 }

 // A libraryCache is a thread-safe, append-only libraryMap.
 type libraryCache struct {
 	sync.RWMutex
 	libs libraryMap
 }

 func (c *libraryCache) get(lib library) (libraryInfo, bool) {
 	c.RLock()
 	defer c.RUnlock()
 	info, ok := c.libs[lib]
 	return info, ok
 }

 func (c *libraryCache) storeNew(libs libraryMap) {
 	// Avoid write contention by skipping the operation if all the libraries in
 	// libs are already in the cache.
 	if !c.hasNew(libs) {
 		return
 	}
 	c.Lock()
 	defer c.Unlock()
 	for lib, info := range libs {
 		if _, ok := c.libs[lib]; !ok {
 			c.libs[lib] = info
 		}
 	}
 }

 func (c *libraryCache) hasNew(libs libraryMap) bool {
 	c.RLock()
 	defer c.RUnlock()
 	for lib := range libs {
 		if _, ok := c.libs[lib]; !ok {
 			return true
 		}
 	}
 	return false
 }

 // libraryAnalyzer analyzes FIDL files to infer library dependencies. It caches
 // information to speed up future analyses.
 type libraryAnalyzer struct {
 	// Paths in which to search for FIDL library files. Given library foo.bar,
 	// the analyzer will check P/foo.bar and P/foo-bar for each path P in paths.
 	// If one of these exists, it reads all descendent .fidl files.
 	paths []string
 	// Global cache of library information.
 	cache libraryCache
 }

 func newLibraryAnalyzer(paths []string) *libraryAnalyzer {
 	return &libraryAnalyzer{
 		paths: paths,
 		cache: libraryCache{
 			libs: make(libraryMap),
 		},
 	}
 }

 const existingLibraryNotice = "" +
 	"NOTE: Your file will be compiled with the others in this library. " +
 	"If you don't want this behavior, choose a different library name."

 // analyze analyzes content, returning a libraryMap that includes content's
 // library together with all its transitive dependencies, and annotations on the
 // "library" and "using" declarations indicating their inferred location. It
 // assumes that filename is a FIDL file containing content. If any library
 // cannot be located in a.paths, it is silently ignored.
 func (a *libraryAnalyzer) analyze(filename, content string) (libraryMap, []Annotation) {
 	result := make(libraryMap)

 	// Start with a stack containing the root library (if it's a platform source
 	// library, meaning we can expect to find it in the tree) and its imports.
 	var stack []library
 	rootLibraryMatch, rootLibraryOk := parseLibraryMatch(content)
 	if rootLibraryOk && rootLibraryMatch.lib.isPlatform() {
 		stack = append(stack, rootLibraryMatch.lib)
 	}
 	rootImports := parsePlatformImportsMatch(content)
 	for _, m := range rootImports {
 		stack = append(stack, m.lib)
 	}

 	// Explore all dependencies via depth-first search.
 	for len(stack) != 0 {
 		// Pop a library and check if it needs processing.
 		var lib library
 		lib, stack = stack[len(stack)-1], stack[:len(stack)-1]
 		if _, ok := result[lib]; ok {
 			continue
 		}

 		// Check the analyzer's cache.
 		if info, ok := a.cache.get(lib); ok {
 			result[lib] = info
 			stack = append(stack, info.deps...)
 			continue
 		}

 		// Find the library's files and dependencies.
 		var info libraryInfo
 		for _, path := range a.paths {
 			for _, dir := range lib.possibleDirs() {
 				if !info.empty() {
 					break
 				}
 				info.dir = filepath.Join(path, dir)
 				// Keep track of already-seen imports to ensure that info.deps
 				// has no duplicates (there won't be duplicates in a valid FIDL
 				// file, but separate files might import the same library).
 				seen := map[library]struct{}{}
 				// Visit all .fidl files, including in subdirectories:
 				filepath.Walk(info.dir, func(file string, fi os.FileInfo, err error) error {
 					if err != nil || fi.IsDir() || filepath.Ext(file) != ".fidl" {
 						return err
 					}
 					rel, err := filepath.Rel(info.dir, file)
 					if err != nil {
 						return err
 					}
 					b, err := ioutil.ReadFile(file)
 					if err != nil {
 						return err
 					}
 					declaredLib, ok := parseLibrary(b)
 					if !ok || declaredLib != lib {
 						return nil
 					}
 					info.files = append(info.files, rel)
 					for _, dep := range parsePlatformImports(b) {
 						if _, ok := seen[dep]; ok {
 							continue
 						}
 						seen[dep] = struct{}{}
 						info.deps = append(info.deps, dep)
 						stack = append(stack, dep)
 					}
 					return nil
 				})
 			}
 		}
 		if !info.empty() {
 			result[lib] = info
 		}
 	}

 	// Cache reusable results first, before adding request-specific information.
 	a.cache.storeNew(result)

 	// The following handles two cases:
 	//   1. (More common) The user typed something like `library foo;`. This
 	//      is a new library outside the source tree, consisting of one file.
 	//   2. The user typed something like `library fuchsia.io;`. This behaves as
 	//      if they were adding a new file to the fuchsia.io library, alongside
 	//      the other ones in the source tree.
 	rootLib := rootLibraryMatch.lib
 	if !rootLibraryOk {
 		// The name doesn't really matter. We just need an entry in the map.
 		rootLib = "fidlbolt"
 	}
 	var anns []Annotation
 	rootInfo := libraryInfo{files: []string{filename}}
 	for _, m := range rootImports {
 		rootInfo.deps = append(rootInfo.deps, m.lib)
 		if info, ok := result[m.lib]; ok {
 			text := fmt.Sprintf("Found %s in %s", m.lib, info.userVisibleDir())
 			anns = append(anns, m.annotation(Info, text))
 		}
 	}
 	if info, ok := result[rootLib]; ok {
 		rootInfo = mergeInfo(rootInfo, info)
 		if rootLibraryOk {
 			text := fmt.Sprintf("Found %s in %s\n\n%s",
 				rootLib, info.userVisibleDir(), existingLibraryNotice)
 			anns = append(anns, rootLibraryMatch.annotation(Info, text))
 		}
 	}
 	result[rootLib] = rootInfo

 	return result, anns
 }

 // fidlcFileArgs returns a list of arguments to pass to fidlc to compile the
 // libraries in m. This is a fairly expensive operation. It returns an error if
 // there is an import cycle.
 func (m libraryMap) fidlcFileArgs() ([]string, error) {
 	sorted, err := m.topologicalSort()
 	if err != nil {
 		return nil, err
 	}

 	// Iterate in reverse order so that dependencies come before dependents.
 	var args []string
 	for i := len(sorted) - 1; i >= 0; i-- {
 		lib := sorted[i]
 		args = append(args, "--files")
 		info := m[lib]
 		for _, file := range info.files {
 			// When the user declares their file as belong to an existing
 			// library, their file will be an absolute path in a temp directory.
 			// Otherwise, all files are relative to info.dir.
 			if filepath.IsAbs(file) {
 				args = append(args, file)
 			} else {
 				args = append(args, filepath.Join(info.dir, file))
 			}
 		}
 	}
 	return args, nil
 }

 // dependencyGraph returns a map representing the the dependency graph of m.
 // Each key is a library name, and each value is another map whose keys are its
 // direct dependencies.
 func (m libraryMap) dependencyGraph() (map[string]interface{}, error) {
 	// Make sure there are no cycles, otherwise this will never terminate.
 	if _, err := m.topologicalSort(); err != nil {
 		return nil, err
 	}

 	sources := map[library]struct{}{}
 	for lib := range m {
 		sources[lib] = struct{}{}
 	}
 	for _, info := range m {
 		for _, dep := range info.deps {
 			delete(sources, dep)
 		}
 	}
 	var start []library
 	for lib := range sources {
 		start = append(start, lib)
 	}

 	var gen func(libs []library) map[string]interface{}
 	gen = func(libs []library) map[string]interface{} {
 		g := map[string]interface{}{}
 		for _, lib := range libs {
 			g[string(lib)] = gen(m[library(lib)].deps)
 		}
 		return g
 	}
 	return gen(start), nil
 }

 // topologicalSort runs topological sort on m, whose deps fields define a
 // directed graph in adjacency list form. In the resulting list, libraries only
 // depend on other libraries later in the list, not on earlier ones. Returns
 // an error if there is a cycle.
 func (m libraryMap) topologicalSort() ([]library, error) {
 	var sorted []library
 	incoming := map[library]int{}
 	for u := range m {
 		incoming[u] = 0
 	}
 	for _, info := range m {
 		for _, v := range info.deps {
 			incoming[v]++
 		}
 	}
 	var src []library
 	for u, deg := range incoming {
 		if deg == 0 {
 			src = append(src, u)
 		}
 	}
 	for len(src) != 0 {
 		var u library
 		u, src = src[len(src)-1], src[:len(src)-1]
 		sorted = append(sorted, u)
 		for _, v := range m[u].deps {
 			incoming[v]--
 			if incoming[v] == 0 {
 				src = append(src, v)
 			}
 		}
 	}
 	for _, deg := range incoming {
 		if deg != 0 {
 			return nil, errors.New("detected an import cycle")
 		}
 	}
 	return sorted, nil
 }

 // possibleDirs returns directory names that lib's files might be found in.
 func (lib library) possibleDirs() []string {
 	if lib == zxLibrary {
 		// The zx library is a special case: its .fidl files are in a
 		// directory named "vsdo" (fuchsia/zircon/vdso), not "zx".
 		return []string{"vdso"}
 	}
 	return []string{string(lib), strings.ReplaceAll(string(lib), ".", "-")}
 }

 // isPlatform returns true if lib adheres to the naming scheme for platform
 // source libraries (enforced by the FIDL linter).
 func (lib library) isPlatform() bool {
 	s := string(lib)
 	return strings.HasPrefix(s, "fidl.") ||
 		strings.HasPrefix(s, "fuchsia.") ||
 		strings.HasPrefix(s, "test.")
 }

 // empty returns true if i represents an empty library (has no files).
 func (i *libraryInfo) empty() bool {
 	return len(i.files) == 0
 }

 // userVisibleDir returns a representation of i.dir to show to the user.
 func (i *libraryInfo) userVisibleDir() string {
 	dir := filepath.ToSlash(i.dir)
 	if i := strings.Index(dir, "/fuchsia/"); i != -1 {
 		return dir[i+1:]
 	}
 	return dir
 }

 // mergeInfo returns a combination of the information in info and other. It
 // assumes that only one of them has dir set.
 func mergeInfo(info, other libraryInfo) libraryInfo {
 	if info.dir != "" && other.dir != "" {
 		panic("mergeInfo called with incompatible dirs")
 	}
 	if info.dir == "" {
 		info.dir = other.dir
 	}
 	info.files = append(info.files, other.files...)
 	deps := map[library]struct{}{}
 	for _, lib := range info.deps {
 		deps[lib] = struct{}{}
 	}
 	for _, lib := range other.deps {
 		if _, ok := deps[lib]; !ok {
 			info.deps = append(info.deps, lib)
 		}
 	}
 	return info
 }

 var (
 	// https://fuchsia.dev/fuchsia-src/development/languages/fidl/reference/language.md#identifiers
 	fidlIdentifierPattern = `[a-zA-Z](?:[a-zA-Z0-9_]*[a-zA-Z0-9])?`

 	// Although "library" can be used anywhere (e.g. as a type name), this regex
 	// is robust because the the library declaration must appear at the top of
 	// the file (only comments and whitespace can precede it).
 	libraryRegexp = regexp.MustCompile(`` +
 		`^(?:\s*//[^\n]*\n)*\s*` +
 		`library\s+(` +
 		fidlIdentifierPattern +
 		`(?:\.` + fidlIdentifierPattern + `)*` +
 		`)\s*;`)

 	// Although "using" can be used anywhere (e.g. as a type name), this regex
 	// is robust because it only matches imports of platform libraries (ones
 	// that start with fidl, fuchsia, or test) and the special library zx. The
 	// only problem is it can match commented imports, so we have to check for
 	// this after matching.
 	platformImportRegexp = regexp.MustCompile(`` +
 		`\busing\s+(` +
 		`zx|` +
 		`(?:fidl|fuchsia|test)` +
 		`(?:\.` + fidlIdentifierPattern + `)+` +
 		`)` +
 		`(?:\s+as\s+` + fidlIdentifierPattern + `)?` +
 		`\s*;`)
 )

 type libraryMatch struct {
 	lib          library
 	line, column int
 }

 func parseLibrary(fidl []byte) (library, bool) {
 	m := libraryRegexp.FindSubmatch(fidl)
 	if m == nil {
 		return "", false
 	}
 	return library(m[1]), true
 }

 func parseLibraryMatch(fidl string) (libraryMatch, bool) {
 	m := libraryRegexp.FindStringSubmatchIndex(fidl)
 	if m == nil {
 		return libraryMatch{}, false
 	}
 	return toLibraryMatch(fidl, m[2], m[3]), true
 }

 func parsePlatformImports(fidl []byte) []library {
 	var libs []library
 	for _, m := range platformImportRegexp.FindAllSubmatchIndex(fidl, -1) {
 		// Make sure the line isn't commented. Technically this breaks if the
 		// line contains a string const with "//" in it. This isn't a big deal
 		// because imports are supposed to come before all other declarations.
 		i := bytes.LastIndexByte(fidl[:m[2]], '\n')
 		if i == -1 || !bytes.Contains(fidl[i:m[2]], []byte("//")) {
 			libs = append(libs, library(fidl[m[2]:m[3]]))
 		}
 	}
 	return libs
 }

 func parsePlatformImportsMatch(fidl string) []libraryMatch {
 	var libs []libraryMatch
 	for _, m := range platformImportRegexp.FindAllStringSubmatchIndex(fidl, -1) {
 		// See the comment in parsePlatformImports.
 		i := strings.LastIndexByte(fidl[:m[2]], '\n')
 		if i == -1 || !strings.Contains(fidl[i:m[2]], "//") {
 			libs = append(libs, toLibraryMatch(fidl, m[2], m[3]))
 		}
 	}
 	return libs
 }

 func toLibraryMatch(fidl string, start, end int) libraryMatch {
 	return libraryMatch{
 		lib:    library(fidl[start:end]),
 		line:   strings.Count(fidl[:start], "\n") + 1,
 		column: start - strings.LastIndexByte(fidl[:start], '\n'),
 	}
 }

 func (m *libraryMatch) annotation(kind AnnotationKind, text string) Annotation {
 	return Annotation{
 		Line:   m.line,
 		Column: m.column,
 		Kind:   kind,
 		Text:   text,
 	}
 }
	// Copyright 2020 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 (
	"bytes"
	"errors"
	"fmt"
	"io/ioutil"
	"os"
	"path/filepath"
	"regexp"
	"strings"
	"sync"
	)

	// A library is a FIDL library represented by its name (as spelled in its
	// "library" declaration, not necessarily matching directory or file names).
	type library string

	// The zx library describes Zircon syscalls.
	const zxLibrary library = "zx"

	// A libraryMap stores information derived about a group of libraries.
	type libraryMap map[library]libraryInfo

	type libraryInfo struct {
	// Directory containing the library.
	dir string
	// FIDL files that make up the library (relative to dir, or absolute).
	files []string
	// Direct dependencies (imported by "using" declarations in files).
	deps []library
	}

	// A libraryCache is a thread-safe, append-only libraryMap.
	type libraryCache struct {
	sync.RWMutex
	libs libraryMap
	}

	func (c *libraryCache) get(lib library) (libraryInfo, bool) {
	c.RLock()
	defer c.RUnlock()
	info, ok := c.libs[lib]
	return info, ok
	}

	func (c *libraryCache) storeNew(libs libraryMap) {
	// Avoid write contention by skipping the operation if all the libraries in
	// libs are already in the cache.
	if !c.hasNew(libs) {
	return
	}
	c.Lock()
	defer c.Unlock()
	for lib, info := range libs {
	if _, ok := c.libs[lib]; !ok {
	c.libs[lib] = info
	}
	}
	}

	func (c *libraryCache) hasNew(libs libraryMap) bool {
	c.RLock()
	defer c.RUnlock()
	for lib := range libs {
	if _, ok := c.libs[lib]; !ok {
	return true
	}
	}
	return false
	}

	// libraryAnalyzer analyzes FIDL files to infer library dependencies. It caches
	// information to speed up future analyses.
	type libraryAnalyzer struct {
	// Paths in which to search for FIDL library files. Given library foo.bar,
	// the analyzer will check P/foo.bar and P/foo-bar for each path P in paths.
	// If one of these exists, it reads all descendent .fidl files.
	paths []string
	// Global cache of library information.
	cache libraryCache
	}

	func newLibraryAnalyzer(paths []string) *libraryAnalyzer {
	return &libraryAnalyzer{
	paths: paths,
	cache: libraryCache{
	libs: make(libraryMap),
	},
	}
	}

	const existingLibraryNotice = "" +
	"NOTE: Your file will be compiled with the others in this library. " +
	"If you don't want this behavior, choose a different library name."

	// analyze analyzes content, returning a libraryMap that includes content's
	// library together with all its transitive dependencies, and annotations on the
	// "library" and "using" declarations indicating their inferred location. It
	// assumes that filename is a FIDL file containing content. If any library
	// cannot be located in a.paths, it is silently ignored.
	func (a *libraryAnalyzer) analyze(filename, content string) (libraryMap, []Annotation) {
	result := make(libraryMap)

	// Start with a stack containing the root library (if it's a platform source
	// library, meaning we can expect to find it in the tree) and its imports.
	var stack []library
	rootLibraryMatch, rootLibraryOk := parseLibraryMatch(content)
	if rootLibraryOk && rootLibraryMatch.lib.isPlatform() {
	stack = append(stack, rootLibraryMatch.lib)
	}
	rootImports := parsePlatformImportsMatch(content)
	for _, m := range rootImports {
	stack = append(stack, m.lib)
	}

	// Explore all dependencies via depth-first search.
	for len(stack) != 0 {
	// Pop a library and check if it needs processing.
	var lib library
	lib, stack = stack[len(stack)-1], stack[:len(stack)-1]
	if _, ok := result[lib]; ok {
	continue
	}

	// Check the analyzer's cache.
	if info, ok := a.cache.get(lib); ok {
	result[lib] = info
	stack = append(stack, info.deps...)
	continue
	}

	// Find the library's files and dependencies.
	var info libraryInfo
	for _, path := range a.paths {
	for _, dir := range lib.possibleDirs() {
	if !info.empty() {
	break
	}
	info.dir = filepath.Join(path, dir)
	// Keep track of already-seen imports to ensure that info.deps
	// has no duplicates (there won't be duplicates in a valid FIDL
	// file, but separate files might import the same library).
	seen := map[library]struct{}{}
	// Visit all .fidl files, including in subdirectories:
	filepath.Walk(info.dir, func(file string, fi os.FileInfo, err error) error {
	if err != nil \|\| fi.IsDir() \|\| filepath.Ext(file) != ".fidl" {
	return err
	}
	rel, err := filepath.Rel(info.dir, file)
	if err != nil {
	return err
	}
	b, err := ioutil.ReadFile(file)
	if err != nil {
	return err
	}
	declaredLib, ok := parseLibrary(b)
	if !ok \|\| declaredLib != lib {
	return nil
	}
	info.files = append(info.files, rel)
	for _, dep := range parsePlatformImports(b) {
	if _, ok := seen[dep]; ok {
	continue
	}
	seen[dep] = struct{}{}
	info.deps = append(info.deps, dep)
	stack = append(stack, dep)
	}
	return nil
	})
	}
	}
	if !info.empty() {
	result[lib] = info
	}
	}

	// Cache reusable results first, before adding request-specific information.
	a.cache.storeNew(result)

	// The following handles two cases:
	// 1. (More common) The user typed something like `library foo;`. This
	// is a new library outside the source tree, consisting of one file.
	// 2. The user typed something like `library fuchsia.io;`. This behaves as
	// if they were adding a new file to the fuchsia.io library, alongside
	// the other ones in the source tree.
	rootLib := rootLibraryMatch.lib
	if !rootLibraryOk {
	// The name doesn't really matter. We just need an entry in the map.
	rootLib = "fidlbolt"
	}
	var anns []Annotation
	rootInfo := libraryInfo{files: []string{filename}}
	for _, m := range rootImports {
	rootInfo.deps = append(rootInfo.deps, m.lib)
	if info, ok := result[m.lib]; ok {
	text := fmt.Sprintf("Found %s in %s", m.lib, info.userVisibleDir())
	anns = append(anns, m.annotation(Info, text))
	}
	}
	if info, ok := result[rootLib]; ok {
	rootInfo = mergeInfo(rootInfo, info)
	if rootLibraryOk {
	text := fmt.Sprintf("Found %s in %s\n\n%s",
	rootLib, info.userVisibleDir(), existingLibraryNotice)
	anns = append(anns, rootLibraryMatch.annotation(Info, text))
	}
	}
	result[rootLib] = rootInfo

	return result, anns
	}

	// fidlcFileArgs returns a list of arguments to pass to fidlc to compile the
	// libraries in m. This is a fairly expensive operation. It returns an error if
	// there is an import cycle.
	func (m libraryMap) fidlcFileArgs() ([]string, error) {
	sorted, err := m.topologicalSort()
	if err != nil {
	return nil, err
	}

	// Iterate in reverse order so that dependencies come before dependents.
	var args []string
	for i := len(sorted) - 1; i >= 0; i-- {
	lib := sorted[i]
	args = append(args, "--files")
	info := m[lib]
	for _, file := range info.files {
	// When the user declares their file as belong to an existing
	// library, their file will be an absolute path in a temp directory.
	// Otherwise, all files are relative to info.dir.
	if filepath.IsAbs(file) {
	args = append(args, file)
	} else {
	args = append(args, filepath.Join(info.dir, file))
	}
	}
	}
	return args, nil
	}

	// dependencyGraph returns a map representing the the dependency graph of m.
	// Each key is a library name, and each value is another map whose keys are its
	// direct dependencies.
	func (m libraryMap) dependencyGraph() (map[string]interface{}, error) {
	// Make sure there are no cycles, otherwise this will never terminate.
	if _, err := m.topologicalSort(); err != nil {
	return nil, err
	}

	sources := map[library]struct{}{}
	for lib := range m {
	sources[lib] = struct{}{}
	}
	for _, info := range m {
	for _, dep := range info.deps {
	delete(sources, dep)
	}
	}
	var start []library
	for lib := range sources {
	start = append(start, lib)
	}

	var gen func(libs []library) map[string]interface{}
	gen = func(libs []library) map[string]interface{} {
	g := map[string]interface{}{}
	for _, lib := range libs {
	g[string(lib)] = gen(m[library(lib)].deps)
	}
	return g
	}
	return gen(start), nil
	}

	// topologicalSort runs topological sort on m, whose deps fields define a
	// directed graph in adjacency list form. In the resulting list, libraries only
	// depend on other libraries later in the list, not on earlier ones. Returns
	// an error if there is a cycle.
	func (m libraryMap) topologicalSort() ([]library, error) {
	var sorted []library
	incoming := map[library]int{}
	for u := range m {
	incoming[u] = 0
	}
	for _, info := range m {
	for _, v := range info.deps {
	incoming[v]++
	}
	}
	var src []library
	for u, deg := range incoming {
	if deg == 0 {
	src = append(src, u)
	}
	}
	for len(src) != 0 {
	var u library
	u, src = src[len(src)-1], src[:len(src)-1]
	sorted = append(sorted, u)
	for _, v := range m[u].deps {
	incoming[v]--
	if incoming[v] == 0 {
	src = append(src, v)
	}
	}
	}
	for _, deg := range incoming {
	if deg != 0 {
	return nil, errors.New("detected an import cycle")
	}
	}
	return sorted, nil
	}

	// possibleDirs returns directory names that lib's files might be found in.
	func (lib library) possibleDirs() []string {
	if lib == zxLibrary {
	// The zx library is a special case: its .fidl files are in a
	// directory named "vsdo" (fuchsia/zircon/vdso), not "zx".
	return []string{"vdso"}
	}
	return []string{string(lib), strings.ReplaceAll(string(lib), ".", "-")}
	}

	// isPlatform returns true if lib adheres to the naming scheme for platform
	// source libraries (enforced by the FIDL linter).
	func (lib library) isPlatform() bool {
	s := string(lib)
	return strings.HasPrefix(s, "fidl.") \|\|
	strings.HasPrefix(s, "fuchsia.") \|\|
	strings.HasPrefix(s, "test.")
	}

	// empty returns true if i represents an empty library (has no files).
	func (i *libraryInfo) empty() bool {
	return len(i.files) == 0
	}

	// userVisibleDir returns a representation of i.dir to show to the user.
	func (i *libraryInfo) userVisibleDir() string {
	dir := filepath.ToSlash(i.dir)
	if i := strings.Index(dir, "/fuchsia/"); i != -1 {
	return dir[i+1:]
	}
	return dir
	}

	// mergeInfo returns a combination of the information in info and other. It
	// assumes that only one of them has dir set.
	func mergeInfo(info, other libraryInfo) libraryInfo {
	if info.dir != "" && other.dir != "" {
	panic("mergeInfo called with incompatible dirs")
	}
	if info.dir == "" {
	info.dir = other.dir
	}
	info.files = append(info.files, other.files...)
	deps := map[library]struct{}{}
	for _, lib := range info.deps {
	deps[lib] = struct{}{}
	}
	for _, lib := range other.deps {
	if _, ok := deps[lib]; !ok {
	info.deps = append(info.deps, lib)
	}
	}
	return info
	}

	var (
	// https://fuchsia.dev/fuchsia-src/development/languages/fidl/reference/language.md#identifiers
	fidlIdentifierPattern = `[a-zA-Z](?:[a-zA-Z0-9_]*[a-zA-Z0-9])?`

	// Although "library" can be used anywhere (e.g. as a type name), this regex
	// is robust because the the library declaration must appear at the top of
	// the file (only comments and whitespace can precede it).
	libraryRegexp = regexp.MustCompile(`` +
	`^(?:\s//[^\n]\n)\s` +
	`library\s+(` +
	fidlIdentifierPattern +
	`(?:\.` + fidlIdentifierPattern + `)*` +
	`)\s*;`)

	// Although "using" can be used anywhere (e.g. as a type name), this regex
	// is robust because it only matches imports of platform libraries (ones
	// that start with fidl, fuchsia, or test) and the special library zx. The
	// only problem is it can match commented imports, so we have to check for
	// this after matching.
	platformImportRegexp = regexp.MustCompile(`` +
	`\busing\s+(` +
	`zx\|` +
	`(?:fidl\|fuchsia\|test)` +
	`(?:\.` + fidlIdentifierPattern + `)+` +
	`)` +
	`(?:\s+as\s+` + fidlIdentifierPattern + `)?` +
	`\s*;`)
	)

	type libraryMatch struct {
	lib library
	line, column int
	}

	func parseLibrary(fidl []byte) (library, bool) {
	m := libraryRegexp.FindSubmatch(fidl)
	if m == nil {
	return "", false
	}
	return library(m[1]), true
	}

	func parseLibraryMatch(fidl string) (libraryMatch, bool) {
	m := libraryRegexp.FindStringSubmatchIndex(fidl)
	if m == nil {
	return libraryMatch{}, false
	}
	return toLibraryMatch(fidl, m[2], m[3]), true
	}

	func parsePlatformImports(fidl []byte) []library {
	var libs []library
	for _, m := range platformImportRegexp.FindAllSubmatchIndex(fidl, -1) {
	// Make sure the line isn't commented. Technically this breaks if the
	// line contains a string const with "//" in it. This isn't a big deal
	// because imports are supposed to come before all other declarations.
	i := bytes.LastIndexByte(fidl[:m[2]], '\n')
	if i == -1 \|\| !bytes.Contains(fidl[i:m[2]], []byte("//")) {
	libs = append(libs, library(fidl[m[2]:m[3]]))
	}
	}
	return libs
	}

	func parsePlatformImportsMatch(fidl string) []libraryMatch {
	var libs []libraryMatch
	for _, m := range platformImportRegexp.FindAllStringSubmatchIndex(fidl, -1) {
	// See the comment in parsePlatformImports.
	i := strings.LastIndexByte(fidl[:m[2]], '\n')
	if i == -1 \|\| !strings.Contains(fidl[i:m[2]], "//") {
	libs = append(libs, toLibraryMatch(fidl, m[2], m[3]))
	}
	}
	return libs
	}

	func toLibraryMatch(fidl string, start, end int) libraryMatch {
	return libraryMatch{
	lib: library(fidl[start:end]),
	line: strings.Count(fidl[:start], "\n") + 1,
	column: start - strings.LastIndexByte(fidl[:start], '\n'),
	}
	}

	func (m *libraryMatch) annotation(kind AnnotationKind, text string) Annotation {
	return Annotation{
	Line: m.line,
	Column: m.column,
	Kind: kind,
	Text: text,
	}
	}