text: #!/usr/bin/env node
  /**
   * @license
   * Copyright 2016 Google Inc.
   *
   * Licensed under the Apache License, Version 2.0 (the "License");
   * you may not use this file except in compliance with the License.
   * You may obtain a copy of the License at
   *
   *     http://www.apache.org/licenses/LICENSE-2.0
   *
   * Unless required by applicable law or agreed to in writing, software
   * distributed under the License is distributed on an "AS IS" BASIS,
   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   * See the License for the specific language governing permissions and
   * limitations under the License.
   */
  
  /**
   * @fileoverview
   *
   * A node script that generates externs automatically from the uncompiled
   * source of a Closure project.  Designed for Shaka Player, but may be usable
   * in other projects as well.  Does not depend on the Closure compiler itself.
   *
   * We were not able to get our externs generated by the Closure compiler.  There
   * were many issues with the Closure-generated externs, including the order of
   * the externs and the replacement of record types and enums with their
   * underlying types.
   *
   * This uses a node module called esprima to parse JavaScript, then explores the
   * abstract syntax tree from esprima.  It finds exported symbols and generates
   * an appropriate extern definition for it.
   *
   * The generated externs are then topologically sorted according to the
   * goog.provide and goog.require calls in the sources.  No sorting is done
   * within source files, and no sorting is done based on parameter types.
   * Circular deps between source files will not be resolved, and deps not
   * represented in goog.provide/goog.require will not be discovered.
   *
   * Arguments: --output <EXTERNS> <INPUT> [<INPUT> ...]
   */
  
  // Load required modules.
  let assert = require('assert');
  if (assert.strict) {
    // The "strict" mode was added in v9.9, use that if available.
    assert = assert.strict;
  }
  const esprima = require('esprima');
  const fs = require('fs');
  
  // The annotations we will consider "exporting" a symbol.
  const EXPORT_REGEX = /@(?:export|exportInterface|expose)\b/;
  
  
  /**
   * Topological sort of general objects using a DFS approach.
   * Will add a __mark field to each object as part of the sorting process.
   * @param {!Array.<T>} list
   * @param {function(T):!Array.<T>} getDeps
   * @return {!Array.<T>}
   * @template T
   * @see https://en.wikipedia.org/wiki/Topological_sorting#Depth-first_search
   */
  function topologicalSort(list, getDeps) {
    const sorted = [];
    const NOT_VISITED = 0;
    const MID_VISIT = 1;
    const COMPLETELY_VISITED = 2;
  
    // Mark all objects as not visited.
    for (const object of list) {
      object.__mark = NOT_VISITED;
    }
  
    // Visit each object.
    for (const object of list) {
      visit(object);
    }
  
    // Return the sorted list.
    return sorted;
  
    /**
     * @param {T} object
     * @template T
     */
    function visit(object) {
      if (object.__mark == MID_VISIT) {
        assert.fail('Dependency cycle detected!');
      } else if (object.__mark == NOT_VISITED) {
        object.__mark = MID_VISIT;
  
        // Visit all dependencies.
        for (const dep of getDeps(object)) {
          visit(dep);
        }
  
        object.__mark = COMPLETELY_VISITED;
  
        // Push this object onto the list.  All transitive dependencies have
        // already been added to the list.
        sorted.push(object);
      }
    }
  }
  
  /**
   * @param {ASTNode} node A node from the abstract syntax tree.
   * @return {boolean} true if this is a call node.
   */
  function isCallNode(node) {
    // Example node: {
    //   type: 'ExpressionStatement',
    //   expression: { type: 'CallExpression', callee: {...}, arguments: [...] },
    // }
    return node.type == 'ExpressionStatement' &&
           node.expression.type == 'CallExpression';
  }
  
  
  /**
   * Pretty-print a node via console.log.  Useful for debugging and development
   * to see what the AST looks like.
   * @param {ASTNode} node A node from the abstract syntax tree.
   */
  function dumpNode(node) {
    console.log(JSON.stringify(node, null, '  '));
  }
  
  
  /**
   * @param {ASTNode} node A node from the abstract syntax tree.
   * @return {boolean} true if this is a call to goog.provide.
   */
  function isProvideNode(node) {
    return isCallNode(node) &&
           getIdentifierString(node.expression.callee) == 'goog.provide';
  }
  
  
  /**
   * @param {ASTNode} node A node from the abstract syntax tree.
   * @return {boolean} true if this is a call to goog.require.
   */
  function isRequireNode(node) {
    return isCallNode(node) &&
           getIdentifierString(node.expression.callee) == 'goog.require';
  }
  
  
  /**
   * @param {ASTNode} node A node from the abstract syntax tree.
   * @return {boolean} true if this is an exported symbol or property.
   */
  function isExportNode(node) {
    const doc = getLeadingBlockComment(node);
    return doc && EXPORT_REGEX.test(doc);
  }
  
  
  /**
   * @param {ASTNode} node A node from the abstract syntax tree.
   * @return {string} A reconstructed leading comment block for the node.
   *   If there are multiple comments before this node, we will take the most
   *   recent block comment, as that is the one that would contain any applicable
   *   jsdoc/closure annotations for this symbol.
   */
  function getLeadingBlockComment(node) {
    // Example code: /** @summary blah */ /** @export */ foo.bar = ...;
    // Example node: {
    //   type: 'ExpressionStatement',
    //   expression: { ... },
    //   leadingComments: [
    //     { type: 'Block', value: '* @summary blah ' },
    //     { type: 'Block', value: '* @export ' },
    //   ],
    // }
    if (!node.leadingComments || !node.leadingComments.length) {
      return null;
    }
  
    // Ignore non-block comments, since those are not jsdoc/Closure comments.
    const blockComments = node.leadingComments.filter((comment) => {
      return comment.type == 'Block';
    });
    if (!blockComments.length) {
      return null;
    }
  
    // In case there are multiple (for example, a file-level comment that also
    // preceeds the node), take the most recent one, which is closest to the node.
    const mostRecentComment = blockComments[blockComments.length - 1];
  
    // Reconstruct the original block comment by adding back /* and */.
    return '/*' + mostRecentComment.value + '*/';
  }
  
  
  /**
   * @param {number} idx An argument index from the call node.
   * @param {ASTNode} node A node from the abstract syntax tree.
   * @return {string} The argument value as a string.
   */
  function getArgumentFromCallNode(idx, node) {
    // Example node: {
    //   type: 'ExpressionStatement',
    //   expression: { type: 'CallExpression', callee: {...}, arguments: [...] },
    // }
    assert(isCallNode(node));
    return node.expression.arguments[idx].value;
  }
  
  
  /**
   * @param {ASTNode} node An identifier or member node from the abstract syntax
   *   tree.
   * @return {string} The identifier as a string.
   */
  function getIdentifierString(node) {
    if (node.type == 'Identifier') {
      // Example code: foo
      // Example node: { type: 'Identifier', name: 'foo' }
      return node.name;
    }
  
    assert.equal(node.type, 'MemberExpression');
    // Example code: foo.bar.baz
    // Example node: {
    //   type: 'MemberExpression',
    //   object: {
    //     type: 'MemberExpression',
    //     object: { type: 'Identifier', name: 'foo' },
    //     property: { type: 'Identifier', name: 'bar' },
    //   },
    //   property: { type: 'Identifier', name: 'baz' },
    // }
    return getIdentifierString(node.object) + '.' +
        getIdentifierString(node.property);
  }
  
  
  /**
   * @param {ASTNode} node A function definition node from the abstract syntax
   *   tree.
   * @return {!Array.<string>} a list of the parameter names.
   */
  function getFunctionParameters(node) {
    assert(node.type == 'FunctionExpression' ||
           node.type == 'ArrowFunctionExpression');
    // Example code: function(x, y, z = null, ...varArgs) {...}
    // Example node: {
    //   params: [
    //     { type: 'Identifier', name: 'x' },
    //     { type: 'Identifier', name: 'y' },
    //     {
    //       type: 'AssignmentPattern',
    //       left: { type: 'Identifier', name: 'z' },
    //       right: { type: 'Literal', raw: 'null' },
    //     },
    //     {
    //       type: 'RestElement',
    //       argument: { type: 'Identifier', name: 'varArgs' },
    //     },
    //   ],
    //   body: {...},
    // }
    return node.params.map((param) => {
      if (param.type == 'Identifier') {
        return param.name;
      } else if (param.type == 'AssignmentPattern') {
        return param.left.name;
      } else {
        assert.equal(param.type, 'RestElement');
        return '...' + param.argument.name;
      }
    });
  }
  
  
  /**
   * Take the original block comment and prep it for the externs by removing
   * export annotations and blank lines.
   *
   * @param {string}
   * @return {string}
   */
  function removeExportAnnotationsFromComment(comment) {
    // Remove @export annotations.
    comment = comment.replace(EXPORT_REGEX, '');
  
    // Split into lines, remove empty comment lines, then recombine.
    comment = comment.split('\n')
        .filter((line) => !/^ *\*? *$/.test(line))
        .join('\n');
  
    return comment;
  }
  
  
  /**
   * Recursively find all expression statements in all block nodes.
   * @param {ASTNode} node
   * @return {!Array.<ASTNode>}
   */
  function getAllExpressionStatements(node) {
    assert(node.body && node.body.body);
    const expressionStatements = [];
    for (const childNode of node.body.body) {
      if (childNode.type == 'ExpressionStatement') {
        expressionStatements.push(childNode);
      } else if (childNode.body) {
        const childExpressions = getAllExpressionStatements(childNode);
        expressionStatements.push(...childExpressions);
      }
    }
    return expressionStatements;
  }
  
  
  /**
   * @param {!Set.<string>} names A set of the names of exported nodes.
   * @param {ASTNode} node An exported node from the abstract syntax tree.
   * @return {string} An extern string for this node.
   */
  function createExternFromExportNode(names, node) {
    assert.equal(node.type, 'ExpressionStatement', 'Unknown node type');
  
    let comment = getLeadingBlockComment(node);
    comment = removeExportAnnotationsFromComment(comment);
  
    let name;
    let assignment;
  
    switch (node.expression.type) {
      case 'AssignmentExpression':
        // Example code: /** @export */ foo.bar = function(...) { ... };
        // Example node.expression: {
        //   operator: '=',
        //   left: {
        //     type: 'MemberExpression',
        //     object: { type: 'Identifier', name: 'foo' },
        //     property: { type: 'Identifier', name: 'bar' },
        //   }, right: {
        //     type: 'FunctionExpression', params: [ ... ], body: {...}
        //   }
        // }
        name = getIdentifierString(node.expression.left);
        assignment = createExternAssignment(name, node.expression.right);
        break;
  
      case 'MemberExpression':
        // Example code: /** @export */ foo.bar;
        // Example node.expression: {
        //   object: { type: 'Identifier', name: 'foo' },
        //   property: { type: 'Identifier', name: 'bar' },
        // }
        name = getIdentifierString(node.expression);
        assignment = '';
        break;
  
      default:
        assert.fail('Unexpected expression type: ' + node.expression.type);
    }
  
    // Keep track of the names we've externed.
    names.add(name);
    // Generate the actual extern string.
    let externString = comment + '\n' + name + assignment + ';\n';
  
    // Find this.foo = bar in the constructor, and potentially generate externs
    // for that, too.
    if (node.expression.type == 'AssignmentExpression') {
      const rightSide = node.expression.right;
  
      if (rightSide.type == 'FunctionExpression' &&
          comment.includes('@constructor')) {
        externString += createExternsFromConstructor(name, rightSide);
      } else if (rightSide.type == 'ClassExpression') {
        const ctor = getClassConstructor(node.expression.right);
        if (ctor) {
          externString += createExternsFromConstructor(name, ctor);
        }
      }
    }
    return externString;
  }
  
  
  /**
   * @param {ASTNode} node A method node from the abstract syntax tree.
   * @return {string} The extern string for this method.
   */
  function createExternMethod(node) {
    // Example code: foo.bar = class {
    //   baz() { ... }
    // };
    // Example node: {
    //   leadingComments: [ ... ],
    //   static: false,
    //   key: Identifier,
    //   value: FunctionExpression,
    // }
    const id = getIdentifierString(node.key);
    let comment = getLeadingBlockComment(node);
    if (!comment) {
      if (id == 'constructor') {
        // ES6 constructors don't necessarily need comments; a comment along the
        // lines of "Creates a Foo object." doesn't really add anything.
        comment = '';
      } else {
        throw new Error('No leading block comment for: ' + id);
      }
    }
    comment = removeExportAnnotationsFromComment(comment);
  
    const params = getFunctionParameters(node.value);
  
    let methodString = (comment ? '  ' + comment + '\n' : '') + '  ';
    if (node.static) {
      methodString += 'static ';
    }
    methodString += id + '(' + params + ') {}';
    return methodString;
  }
  
  
  /**
   * Find the constructor of an ES6 class, if it exists.
   *
   * @param {ASTNode} className
   * @return {ASTNode}
   */
  function getClassConstructor(classNode) {
    // Example class node: {
    //   type: 'ClassExpression',
    //   body: {
    //     type: 'ClassBody',
    //     body: [ MethodDefinition, ... ],
    //   }
    // }
    //
    // Example method node: {
    //   type: 'MethodDefinition',
    //   key: { type: 'Identifier', name: 'constructor' },
    //   value: {
    //     type: 'FunctionExpression',
    //     params: [ [Identifier], [Identifier], [Identifier] ],
    //     body: { type: 'BlockStatement', body: [Array] },
    // }
  
    assert.equal(classNode.type, 'ClassExpression');
  
    for (const member of classNode.body.body) {
      if (member.type == 'MethodDefinition' && member.key.name == 'constructor') {
        return member.value;
      }
    }
  
    return null;
  }
  
  
  /**
   * @param {string} name The name of the thing we are assigning.
   * @param {ASTNode} node An assignment node from the abstract syntax tree.
   * @return {string} The assignment part of the extern string for this node.
   */
  function createExternAssignment(name, node) {
    switch (node.type) {
      case 'ClassExpression': {
        // Example code: foo.bar = class bar2 extends foo.baz { /* ... */ };
        // Example node: {
        //   id: { name: 'bar' },   // or null
        //   superClass: { type: 'MemberExpression', ... },  // or null
        //   body: { body: [ ... ] },
        // }
        let classString = ' = class ';
        if (node.id) {
          classString += getIdentifierString(node.id) + ' ';
        }
        if (node.superClass) {
          classString += 'extends ' + getIdentifierString(node.superClass) + ' ';
        }
        classString += '{\n';
        for (const member of node.body.body) {
          // Only look at exported members.  Constructors are exported implicitly
          // when the class is exported.
          const comment = getLeadingBlockComment(member);
          if (!EXPORT_REGEX.test(comment) && member.key.name != 'constructor') {
            continue;
          }
  
          assert.equal(
              member.type, 'MethodDefinition',
              'Unexpected exported member type in exported class!');
  
          classString += createExternMethod(member) + '\n';
        }
        classString += '}';
        return classString;
      }
  
      case 'ArrowFunctionExpression':
      case 'FunctionExpression': {
        // Example code: foo.square = function(x) { return x * x; };
        // Example node: { params: [ { type: 'Identifier', name: 'x' } ] }
        const params = getFunctionParameters(node);
        return ' = function(' + params.join(', ') + ') {}';
      }
  
      case 'ObjectExpression': {
        // Example code: foo.Bar = { 'ABC': 1, DEF: 2 };
        // Example node: {
        //   properties: [ {
        //     kind: 'init',
        //     key: { type: 'Literal', value: 'ABC' }
        //     value: { type: 'Literal', value: 1 }
        //   }, {
        //     kind: 'init',
        //     key: { type: 'Identifier', name: 'DEF' }
        //     value: { type: 'Literal', value: 2 }
        //   } ]
        // }
        const propertyStrings = node.properties.map((prop) => {
          assert.equal(prop.kind, 'init');
          assert(prop.key.type == 'Literal' || prop.key.type == 'Identifier');
          // Literal indicates a quoted name in the source, while Identifier is
          // an unquoted name.  In the case of Literal, key.raw gets us the
          // unquoted name, we end up with an unquoted name in both cases.
          const name = prop.key.type == 'Literal' ? prop.key.raw : prop.key.name;
          assert.equal(prop.value.type, 'Literal');
          return '  ' + name + ': ' + prop.value.raw;
        });
        return ' = {\n' + propertyStrings.join(',\n') + '\n}';
      }
  
      case 'Identifier':
        // Example code: /** @const {string} @export */ foo.version = VERSION;
        // Example extern: /** @const {string} */ foo.version;
        return '';
  
      case 'Literal':
        // Example code: /** @const {string} @export */ foo.version = 'v1.0.0';
        // Example extern: /** @const {string} */ foo.version;
        return '';
  
      default:
        assert.fail('Unexpected export type: ' + node.type);
        return '';  // Shouldn't be hit, but linter wants a return statement.
    }
  }
  
  
  /**
   * Look for exports in a constructor body.  If we don't do this, we may end up
   * with errors about classes not fully implementing their interfaces.  In
   * reality, the interface is implemented by assigning members on "this".
   *
   * @param {string} className
   * @param {ASTNode} constructorNode
   * @return {string}
   */
  function createExternsFromConstructor(className, constructorNode) {
    // Example code:
    //
    // /** @interface @exportInterface */
    // FooLike = function() {};
    //
    // /** @exportInterface @type {number} */
    // FooLike.prototype.bar;
    //
    // /** @export @implements {FooLike} */
    // class Foo {
    //   constructor() {
    //     /** @override @exportInterface */
    //     this.bar = 10;
    //   }
    // };
    //
    // Example externs:
    //
    // /**
    //  * Generated by createExternFromExportNode:
    //  * @implements {FooLike}
    //  */
    // class Foo {
    //   constructor() {}
    // }
    //
    // /**
    //  * Generated by createExternsFromConstructor:
    //  * @override
    //  */
    // Foo.prototype.bar;
  
    const expressionStatements = getAllExpressionStatements(constructorNode);
    let externString = '';
  
    for (const statement of expressionStatements) {
      const left = statement.expression.left;
      const right = statement.expression.right;
  
      // Skip anything that isn't an assignment to a member of "this".
      if (statement.expression.type != 'AssignmentExpression' ||
          left.type != 'MemberExpression' ||
          left.object.type != 'ThisExpression') {
        continue;
      }
  
      assert(left);
      assert(right);
  
      // Skip anything that isn't exported.
      let comment = getLeadingBlockComment(statement);
      if (!EXPORT_REGEX.test(comment)) {
        continue;
      }
  
      comment = removeExportAnnotationsFromComment(comment);
  
      assert.equal(left.property.type, 'Identifier');
      const name = className + '.prototype.' + left.property.name;
      externString += comment + '\n' + name + ';\n';
    }
  
    return externString;
  }
  
  
  /**
   * @param {!Set.<string>} names A set of the names of exported nodes.
   * @param {string} inputPath
   * @return {{
   *   path: string,
   *   provides: !Array.<string>,
   *   requires: !Array.<string>,
   *   externs: string,
   * }}
   */
  function generateExterns(names, inputPath) {
    // Load and parse the code, with comments attached to the nodes.
    const code = fs.readFileSync(inputPath, 'utf-8');
    const program = esprima.parse(code, {attachComment: true});
    assert.equal(program.type, 'Program');
  
    const body = program.body;
    const provides = program.body.filter(isProvideNode)
        .map((node) => getArgumentFromCallNode(0, node));
    const requires = program.body.filter(isRequireNode)
        .map((node) => getArgumentFromCallNode(0, node));
  
    const rawExterns = program.body.filter(isExportNode)
        .map((node) => createExternFromExportNode(names, node));
    const externs = rawExterns.join('');
  
    return {
      path: inputPath,
      provides: provides,
      requires: requires,
      externs: externs,
    };
  }
  
  
  /**
   * Generate externs from exported code.
   * Arguments: --output <EXTERNS> <INPUT> [<INPUT> ...]
   *
   * @param {!Array.<string>} args The args to this script, not counting node and
   *   the script name itself.
   */
  function main(args) {
    const inputPaths = [];
    let outputPath;
  
    for (let i = 0; i < args.length; ++i) {
      if (args[i] == '--output') {
        outputPath = args[i + 1];
        ++i;
      } else {
        inputPaths.push(args[i]);
      }
    }
    assert(outputPath, 'You must specify output file with --output <EXTERNS>');
    assert(inputPaths.length, 'You must specify at least one input file.');
  
    // Generate externs for all input paths.
    const names = new Set();
    const results = inputPaths.map((path) => generateExterns(names, path));
  
    // Sort them in dependency order.
    const sorted = topologicalSort(results, /* getDeps */ (object) => {
      return object.requires.map((id) => {
        const dep = results.find((x) => x.provides.includes(id));
        assert(dep, 'Cannot find dependency: ' + id);
        return dep;
      });
    });
  
    // Generate namespaces for all externs.  For example, if we extern
    // foo.bar.baz, foo and foo.bar will both need to be declared first.
    const namespaces = new Set();
    const namespaceDeclarations = [];
    for (const name of names) {
      // Add the full name "foo.bar.baz" and its prototype ahead of time.  We
      // should never generate these as namespaces.
      namespaces.add(name);
      namespaces.add(name + '.prototype');
  
      // For name "foo.bar.baz", iterate over partialName "foo" and "foo.bar".
      const pieces = name.split('.');
      for (let i = 1; i < pieces.length; ++i) {
        const partialName = pieces.slice(0, i).join('.');
        if (!namespaces.has(partialName)) {
          let declaration;
          if (i == 1) {
            declaration = '/** @namespace */\n';
            declaration += 'window.';
          } else {
            declaration = '/** @const */\n';
          }
          declaration += partialName + ' = {};\n';
          namespaceDeclarations.push(declaration);
          namespaces.add(partialName);
        }
      }
    }
  
    // Get externs.
    const externs = sorted.map((x) => x.externs).join('');
  
    // Output generated externs, with an appropriate header.
    fs.writeFileSync(outputPath,
        '/**\n' +
        ' * @fileoverview Generated externs.  DO NOT EDIT!\n' +
        ' * @externs\n' +
        ' * @suppress {duplicate} To prevent compiler errors with the\n' +
        ' *   namespace being declared both here and by goog.provide in the\n' +
        ' *   library.\n' +
        ' */\n\n' +
        namespaceDeclarations.join('') + '\n' + externs);
  }
  
  
  // Skip argv[0], which is the node binary, and argv[1], which is the script.
  main(process.argv.slice(2));
  