fidl-lsp/analysis/deps.go

// 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 analysis

import (
	"encoding/json"
	"errors"
	"fmt"
	"io/ioutil"

	"fidl-lsp/third_party/fidlgen"

	"fidl-lsp/state"
)

// CompiledLibraries represents a deserialized fidl_project.json.
// This is a file that declares all the FIDL libraries the language server
// should be aware of, and includes information on how to build them and find
// their compiled JSON IR.
type CompiledLibraries []CompiledLibrary

// CompiledLibrary represents the build information for a single FIDL library,
// including its name, its constituent files, its dependencies, and the absolute
// filepath to its compiled JSON IR.
type CompiledLibrary struct {
	Name  string
	Files []string
	Deps  []string
	JSON  string
}

// LoadFidlProject builds a CompiledLibraries out of a fidl_project.json file.
func LoadFidlProject(fidlProjectPath string) (CompiledLibraries, error) {
	data, err := ioutil.ReadFile(fidlProjectPath)
	if err != nil {
		return nil, fmt.Errorf("failed to read file: %s", err)
	}

	var libraries CompiledLibraries
	if err := json.Unmarshal(data, &libraries); err != nil {
		return nil, fmt.Errorf("failed to deserialize compiled libraries: %s", err)
	}
	return libraries, nil
}

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

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

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

// FindDeps analyzes the file at `path`, locates its dependencies, and returns
// the --files args for a fidlc invocation that will compile `file`'s library.
func (a *Analyzer) FindDeps(fs *state.FileSystem, path state.FileID) ([]string, error) {
	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 []fidlgen.LibraryName
	file, err := fs.File(path)
	if err != nil {
		return nil, fmt.Errorf("could not find file `%s`", path)
	}
	rootLibraryMatch, rootLibraryOk := state.ParseLibraryMatch(file)
	if !rootLibraryOk {
		return nil, fmt.Errorf("no library found for file %s", file)
	}
	stack = append(stack, fidlgen.LibraryName(rootLibraryMatch.Lib))
	rootImports := state.ParsePlatformImportsMatch(file)
	for _, m := range rootImports {
		stack = append(stack, fidlgen.LibraryName(m.Lib))
	}

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

		// Find the library's files and dependencies.
		var info libraryInfo
		// We don't call getLibraryWithFile here because these libraries are
		// found either by searching for regex patterns of library imports, or
		// by looking in a library's dependencies, which are only stored as bare
		// library names.
		if lib, ok := a.getLibrary(libName); ok {
			// Add the library's files to info.files
			for file := range lib.files {
				// Unless that file is a duplicate of one that is open
				if file == string(path) {
					continue
				}
				info.files = append(info.files, file)
			}
			// Add each of the library's dependencies to the stack
			for dep := range lib.deps {
				info.deps = append(info.deps, dep)
				stack = append(stack, dep)
			}
		} else {
			return nil, fmt.Errorf("could not find deps for library `%s`", libName)
		}

		if !info.empty() {
			result[libName] = info
		}
	}

	// `result` is now a libraryMap of the dependencies for the current file

	// Now do a topological sort on libraryMap (this will give us a list of
	// files in order of dependency for each library) and reverse order this
	// to get the correct list of --files args to return
	fileArgs, err := result.fidlcFileArgs()
	if err != nil {
		return nil, fmt.Errorf("error in getting fidlc --files args: %s", err)
	}
	return fileArgs, nil
}

// 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 {
			args = append(args, file)
		}
	}
	return args, 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() ([]fidlgen.LibraryName, error) {
	var sorted []fidlgen.LibraryName
	incoming := map[fidlgen.LibraryName]int{}
	for u := range m {
		incoming[u] = 0
	}
	for _, info := range m {
		for _, v := range info.deps {
			incoming[v]++
		}
	}
	var src []fidlgen.LibraryName
	for u, deg := range incoming {
		if deg == 0 {
			src = append(src, u)
		}
	}
	for len(src) != 0 {
		var u fidlgen.LibraryName
		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
}