| // 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" |
| |
| fidlcommon "fidl-lsp/third_party/common" |
| |
| "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 map[string]CompiledLibrary |
| |
| // CompiledLibrary represents the build information for a single FIDL library, |
| // including its constituent files, its dependencies, and the absolute filepath |
| // to its compiled JSON IR. |
| type CompiledLibrary struct { |
| 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[fidlcommon.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 []fidlcommon.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 []fidlcommon.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, fidlcommon.LibraryName(rootLibraryMatch.Lib)) |
| rootImports := state.ParsePlatformImportsMatch(file) |
| for _, m := range rootImports { |
| stack = append(stack, fidlcommon.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 fidlcommon.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 |
| if lib, ok := a.libs[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() ([]fidlcommon.LibraryName, error) { |
| var sorted []fidlcommon.LibraryName |
| incoming := map[fidlcommon.LibraryName]int{} |
| for u := range m { |
| incoming[u] = 0 |
| } |
| for _, info := range m { |
| for _, v := range info.deps { |
| incoming[v]++ |
| } |
| } |
| var src []fidlcommon.LibraryName |
| for u, deg := range incoming { |
| if deg == 0 { |
| src = append(src, u) |
| } |
| } |
| for len(src) != 0 { |
| var u fidlcommon.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 |
| } |