Guess the location of fidl-format

This change introduces two ways that the FIDL extension tries to find
fidl-format. Both of these techniques involve finding the root of the
Fuchsia repo by looking for the .fx-build-dir file.

* Try to walk up the directory hierarchy of each of the workspace
directories, checking if any contains .fx-build-dir.
* Try to find .fx-build-dir in all of the current workspace directories.

In each case, the extension uses the location in this file to construct
a likely path where fidl-format might exist.

Change-Id: Id8bbfce3801c0a96012b71c31216c5f308494316
diff --git a/vscode-language-fidl/package-lock.json b/vscode-language-fidl/package-lock.json
index 9d4e628..c3f5842 100644
--- a/vscode-language-fidl/package-lock.json
+++ b/vscode-language-fidl/package-lock.json
@@ -22,12 +22,6 @@
 			"integrity": "sha512-1MxY/ooNO67EQv7Jlv9v/lG1Cll26Uqo4mY00dNPE6TZ62sTJ39WTlEOWbLwn7elRpmqT6hX3fUaBhFeFcQeuA==",
 			"dev": true
 		},
-		"@types/tmp": {
-			"version": "0.1.0",
-			"resolved": "https://registry.npmjs.org/@types/tmp/-/tmp-0.1.0.tgz",
-			"integrity": "sha512-6IwZ9HzWbCq6XoQWhxLpDjuADodH/MKXRUIDFudvgjcVdjFknvmR+DNsoUeer4XPrEnrZs04Jj+kfV9pFsrhmA==",
-			"dev": true
-		},
 		},
 		"@types/vscode": {
 			"version": "1.41.0",
diff --git a/vscode-language-fidl/src/formatter.ts b/vscode-language-fidl/src/formatter.ts
index 78c9f93..1f4e421 100644
--- a/vscode-language-fidl/src/formatter.ts
+++ b/vscode-language-fidl/src/formatter.ts
@@ -2,7 +2,12 @@
 
 import * as vscode from 'vscode';
 import { spawnSync } from 'child_process';
-import * as fs from 'fs';
+import {
+    guessFidlFormatToolPath,
+    getFidlFormatToolPathFromPreferences,
+    FormatToolError,
+    FormatToolErrorCause
+} from './tool_finder';
 
 const notDefined = "FIDL format tool not specified. Please set the path to fidl-format in Settings.";
 const notExecutable = "FIDL format tool doesn't exist or can't be run. Please verify the path to fidl-format in Settings.";
@@ -10,40 +15,6 @@
 
 const editSettingLabel = "Edit setting";
 
-enum FormatToolErrorCause {
-    ToolNotSpecified, ToolNotExecutable, FormatterError
-}
-
-class FormatToolError extends Error {
-    cause: FormatToolErrorCause;
-    formatterMessage: string | undefined;
-
-    constructor(cause: FormatToolErrorCause) {
-        super();
-        this.cause = cause;
-    }
-}
-
-/**
- * Checks whether the path to fidl-format has been filled out. If the default
- * value of an empty string is found, an error is shown as a notification.
- */
-function getFidlFormatToolPath(): string {
-    const formatTool: string | undefined | null = vscode.workspace.getConfiguration('fidl').get('formatTool');
-    if (!formatTool) {
-        throw new FormatToolError(FormatToolErrorCause.ToolNotSpecified);
-    }
-
-    try {
-        // Throws if tool is not present or not executable.
-        fs.accessSync(formatTool, fs.constants.X_OK);
-    } catch (e) {
-        throw new FormatToolError(FormatToolErrorCause.ToolNotExecutable);
-    }
-
-    return formatTool as string;
-}
-
 async function showError(e: FormatToolError) {
     let message;
     let showEdit = false;
@@ -82,9 +53,7 @@
 
 /**
  * A formatting edit provider that runs fidl-format over the code in the
- * current FIDL file. This happens indirectly by the use of a temporary file to
- * work around fidl-format's limitation of not accepting FIDL code via standard
- * input.
+ * current FIDL file.
  *
  * Objects of this class will check for the presence of the fidl-format path in
  * settings when instantiated and on every formatting request. If the path is
@@ -93,25 +62,49 @@
  * try to format a FIDL file.
  */
 export default class FidlFormattingEditProvider implements vscode.DocumentFormattingEditProvider {
+    /**
+     * The cached path to the autodetected fidl-format tool. This is set once
+     * for the session if the user hasn't explicitly set a path in preferences.
+     */
+    cachedGuessedFidlFormatToolPath: string | null = null;
     constructor() {
-        try {
-            getFidlFormatToolPath();
-        } catch (e) {
-            showError(e);
+        if (getFidlFormatToolPathFromPreferences()) {
+            // The fidl-format tool path is specified in preferences, so no
+            // caching is needed.
+            return;
         }
+
+        guessFidlFormatToolPath().then(
+            (p) => this.cachedGuessedFidlFormatToolPath = p,
+            (e: FormatToolError) => showError(e));
+
     }
 
-    provideDocumentFormattingEdits(document: vscode.TextDocument): vscode.TextEdit[] {
+    async provideDocumentFormattingEdits(document: vscode.TextDocument): Promise<vscode.TextEdit[]> {
+        const fromPrefs = getFidlFormatToolPathFromPreferences();
         let formatTool: string;
-        try {
-            formatTool = getFidlFormatToolPath();
-        } catch (e) {
-            showError(e);
-            return [];
+
+        if (fromPrefs) {
+            // If the user has set a fidl-format path, that takes precedence.
+            formatTool = fromPrefs;
+            // Remove any cached (i.e. autodetected) tool.
+            this.cachedGuessedFidlFormatToolPath = null;
+        } else if (this.cachedGuessedFidlFormatToolPath) {
+            // If there is a cached fidl-format path, use that for this
+            // session.
+            formatTool = this.cachedGuessedFidlFormatToolPath;
+        } else {
+            // Find the fidl-format tool.
+            try {
+                formatTool = await guessFidlFormatToolPath();
+            } catch (e) {
+                showError(e);
+                return [];
+            }
         }
 
         // FIDL files are assumed to always be UTF-8.
-        const format = spawnSync(formatTool, ["-"], { encoding: 'utf8', input: document.getText() });
+        const format = spawnSync(formatTool, [], { encoding: 'utf8', input: document.getText() });
         if (format.status) {
             // fidl-format exited with an error.
             const e = new FormatToolError(FormatToolErrorCause.FormatterError);
diff --git a/vscode-language-fidl/src/tool_finder.ts b/vscode-language-fidl/src/tool_finder.ts
new file mode 100644
index 0000000..ef1cb49
--- /dev/null
+++ b/vscode-language-fidl/src/tool_finder.ts
@@ -0,0 +1,212 @@
+import * as vscode from 'vscode';
+import * as path from 'path';
+import * as fs from 'fs';
+
+export enum FormatToolErrorCause {
+    ToolNotSpecified, ToolNotExecutable, FormatterError
+}
+
+export class FormatToolError extends Error {
+    cause: FormatToolErrorCause;
+    formatterMessage: string | undefined;
+
+    constructor(cause: FormatToolErrorCause) {
+        super();
+        this.cause = cause;
+    }
+}
+
+/**
+ * Finds the Zircon build output directory given a Fuchsia repository root.
+ *
+ * This function derives the correct filesystem path, but it doesn't check to
+ * ensure that the path exists. Callers are responsible for ensuring that the
+ * resulting path exists and has the expected contents.
+ *
+ * @param fuchsiaRoot the filesystem path to the root of the Fuchsia
+ * repository.
+ * @returns the filesystem path to the root of the Zircon build output
+ * directory.
+ */
+function deriveZirconOutPath(fuchsiaRoot: string): string | null {
+    const buildOutputPointer = path.join(fuchsiaRoot, '.fx-build-dir');
+    let outputRoot
+    try {
+        outputRoot = fs.readFileSync(buildOutputPointer, { encoding: 'utf8' }).trim();
+    } catch (err) {
+        // TODO: proper error handling
+        return null;
+    }
+    return path.join(fuchsiaRoot, outputRoot + '.zircon');
+}
+
+/**
+ * Finds the fidl-format tool given a Zircon output repository root.
+ *
+ * This function derives the correct filesystem path, but it doesn't check to
+ * ensure that the path exists. Callers are responsible for ensuring that the
+ * resulting path exists and has the expected contents.
+ *
+ * @param zirconRoot the filesystem path to the root of the Fuchsia
+ * repository.
+ * @returns the filesystem path to the fidl-format tool.
+ */
+function deriveFidlFormatPath(zirconRoot: string): string | null {
+    return path.join(zirconRoot, 'tools', 'fidl-format');
+}
+
+/**
+ * Attempts to find the fidl-format tool in the current directory, returning
+ * the path to the tool if it's present and executable by the current user.
+ *
+ * @param folderPath The path to the folder to search in.
+ * @returns The path to the fidl-format tool in folderPath or null if the tool can't be found or isn't executable.
+ */
+function findFidlFormatInFolder(folderPath: string): string | null {
+    const zirconRoot = deriveZirconOutPath(folderPath);
+    if (!zirconRoot) {
+        return null;
+    }
+
+    const toolPath = deriveFidlFormatPath(zirconRoot);
+    if (!toolPath) {
+        return null;
+    }
+
+    try {
+        fs.accessSync(toolPath, fs.constants.X_OK);
+    } catch (err) {
+        return null;
+    }
+
+    return toolPath;
+}
+
+/**
+ * Attempts to find the fidl-format tool by asking VS Code to find the root of
+ * the Fuchsia repository.
+ *
+ * @returns the absolute path to fidl-format or null if it couldn't be found.
+ */
+async function guessFidlFormatPathFromWorkspace(): Promise<string | null> {
+    const uris = await vscode.workspace.findFiles('.fx-build-dir', null, 1);
+    if (uris.length < 1) {
+        return null;
+    }
+
+    for (const uri of uris) {
+        if (uri.scheme !== 'file') {
+            // If the repository isn't local, fidl-format won't be runnable
+            // even if present.
+            continue;
+        }
+
+        const basePath = path.dirname(uri.fsPath);
+        const toolPath = findFidlFormatInFolder(basePath);
+        if (toolPath == null) {
+            continue;
+        }
+
+        return toolPath;
+    }
+
+    return null;
+}
+
+/**
+ * Attempts to find the fidl-format tool by traversing the directory tree up
+ * from the root of each workspace folder toward the root of the filesystem.
+ *
+ * @returns the absolute path to fidl-format or null if it couldn't be found.
+ */
+function guessFidlFormatPathFromAncestors(): string | null {
+    const folders = vscode.workspace.workspaceFolders;
+    if (!folders) {
+        return null;
+    }
+
+    for (const folder of folders) {
+        if (folder.uri.scheme !== 'file') {
+            // If the repository isn't local, fidl-format won't be runnable
+            // even if present.
+            continue;
+        }
+
+        let folderPath;
+
+        // Traverse through parent repositories until the direct child of the
+        // root directory.
+        for (folderPath = folder.uri.fsPath;
+            path.dirname(folderPath) != folderPath;
+            folderPath = path.dirname(folderPath)) {
+
+            const toolPath = findFidlFormatInFolder(folderPath);
+            if (toolPath) {
+                return toolPath;
+            }
+        }
+
+        // Also check the root directory.
+        const toolPath = findFidlFormatInFolder(folderPath);
+        if (toolPath) {
+            return toolPath;
+        }
+    }
+
+    return null;
+}
+
+/**
+ * Gets the fidl-format tool path as configured in VS Code preferences.
+ *
+ * @returns the path to fidl-format as configured by the user, or `null` if the
+ * tool isn't set.
+ */
+export function getFidlFormatToolPathFromPreferences(): string | null {
+    let formatTool: string | undefined | null
+        = vscode.workspace.getConfiguration('fidl').get('formatTool');
+
+    try {
+        fs.accessSync(toolPath, fs.constants.X_OK);
+    } catch (err) {
+        throw new FormatToolError(FormatToolErrorCause.ToolNotExecutable);
+    }
+
+    if (formatTool) {
+        return formatTool;
+    } else {
+        return null;
+    }
+}
+
+/**
+ * Checks whether the path to fidl-format has been filled out. If the default
+ * value of an empty string is found, an error is shown as a notification.
+ */
+export async function guessFidlFormatToolPath(): Promise<string> {
+    let formatTool: string | undefined | null
+        = getFidlFormatToolPathFromPreferences();
+
+    // Guessing by ancestor is faster than searching a large workspace for the
+    // Fuchsia root, so we try this approach first.
+    if (!formatTool) {
+        formatTool = guessFidlFormatPathFromAncestors();
+    }
+
+    if (!formatTool) {
+        formatTool = await guessFidlFormatPathFromWorkspace();
+    }
+
+    if (!formatTool) {
+        throw new FormatToolError(FormatToolErrorCause.ToolNotSpecified);
+    }
+
+    try {
+        // Throws if tool is not present or not executable.
+        fs.accessSync(formatTool, fs.constants.X_OK);
+    } catch (err) {
+        throw new FormatToolError(FormatToolErrorCause.ToolNotExecutable);
+    }
+
+    return formatTool;
+}