/**
 * @license
 * Copyright 2018 The Closure Library Authors. All Rights Reserved.
 *
 * 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.
 */

const {SourceError} = require('./sourceerror');
const path = require('path');

const {normalizePath} = require('./normalize');

/** @enum {string} */
const DependencyType = {
  /** A file containing goog.provide statements. */
  CLOSURE_PROVIDE: 'closure provide',
  /** A file containing a goog.module statement. */
  CLOSURE_MODULE: 'closure module',
  /** An ES6 module file. */
  ES6_MODULE: 'es6 module',
  /**
   * A JavaScript file that has no goog.provide/module and is not an ES6 module.
   */
  SCRIPT: 'script',
};


/**
 * A Dependency in the dependency graph (a vertex).
 */
class Dependency {
  /**
   * @param {!DependencyType} type
   * @param {string} filepath
   * @param {!Array<string>} closureSymbols
   * @param {!Array<!Import>} imports
   * @param {string=} language
   */
  constructor(type, filepath, closureSymbols, imports, language = 'es3') {
    /** @const */
    this.type = type;

    /**
     * Full path of this file on disc.
     * @const
     */
    this.path = path.resolve(filepath);

    /**
     * Array of Closure symbols this file provides.
     * @const
     */
    this.closureSymbols = closureSymbols;

    /**
     * Array of imports in this file.
     * @const
     */
    this.imports = imports;

    for (const i of this.imports) {
      i.from = this;
    }

    /**
     * The language level of this file; e.g. "es3", "es6", etc.
     * @const
     */
    this.language = language;
  }

  /**
   * Updates the path to Closure Library for this file. This is useful for
   * ParsedDependency, which cannot know the full path of a file on until it
   * knows the path to Closure Library, as the path in the goog.addDependency
   * call is relative from Closure Library.
   *
   * @param {string} path
   */
  setClosurePath(path) {}

  /**
   * @return {boolean}
   */
  isParsedFromDepsFile() { return false; }
}

let hasWarnedForAssignmentToPath = false;

/**
 * A dependency that was parsed from an goog.addDependnecy call.
 */
class ParsedDependency extends Dependency {
  /**
   * @param {!DependencyType} type
   * @param {string} closureRelativePath
   * @param {!Array<string>} closureSymbols
   * @param {!Array<!Import>} imports
   * @param {string=} language
   */
  constructor(
      type, closureRelativePath, closureSymbols, imports, language = 'es3') {
    super(type, /* filepath= */ '', closureSymbols, imports, language);
    /** @private @const {boolean} */
    this.hasCalledSuper_ = true;
    /** @private {string|undefined} */
    this.path_ = undefined;

    /**
     * Relative path from Closure Library to this file.
     * @const
     */
    this.closureRelativePath = closureRelativePath;
  }

  /** @return {string} */
  get path() {
    if (!this.path_) {
      throw new Error(
          'Must call setClosurePath in order to determine the ' +
          'actual path of this dependency.');
    }
    return this.path_;
  }

  /** @param {string} value */
  set path(value) {
    // Ignore, only here to satisfy super constructor.
    if (!hasWarnedForAssignmentToPath && this.hasCalledSuper_) {
      console.warn(
          'Assigning a path of a ParsedDependency instance was ignored. ' +
          'Use setClosurePath method instead.');
      hasWarnedForAssignmentToPath = true;
    }
  }

  /** @override */
  setClosurePath(closurePath) {
    this.path_ =
        normalizePath(path.resolve(closurePath, this.closureRelativePath));
  }

  /** @override */
  isParsedFromDepsFile() { return true; }
}


/**
 * Generic super class for all types of imports. This acts as an edge in the
 * dependency graph between two dependencies.
 *
 * @abstract
 */
class Import {
  /**
   * @param {string} symOrPath
   */
  constructor(symOrPath) {
    /**
     * Dependency this import is contained in.
     * @type {!Dependency}
     */
    this.from;
    /**
     * The Closure symbol or path that is required.
     * @const
     */
    this.symOrPath = symOrPath;
  }

  /**
   * Asserts that this import edge is valid.
   * @param {!Dependency} to
   * @abstract
   */
  validate(to) {}

  /**
   * @return {boolean}
   * @abstract
   */
  isGoogRequire() {}

  /**
   * @return {boolean}
   * @abstract
   */
  isEs6Import() {}
}

/** An import using goog.require. */
class GoogRequire extends Import {
  /** @override */
  validate(to) {
    for (const sym of to.closureSymbols) {
      if (sym === this.symOrPath) {
        return;
      }
    }

    throw new SourceError(
        `Invalid dependency edge: File ${to.path} does ` +
            `not provide symbol ${this.symOrPath}.`,
        this.from.path);
  }

  /** @override */
  isGoogRequire() {
    return true;
  }

  /** @override */
  isEs6Import() {
    return false;
  }
}

/** An ES6 import (or export from). */
class Es6Import extends Import {
  /** @override */
  toString() {
    return `import|export '${this.symOrPath}'`;
  }

  /** @override */
  validate(to) {
    if (to.type !== DependencyType.ES6_MODULE) {
      throw new SourceError(
          'Cannot import non-ES6 module: ' + to.path, this.from.path);
    }
  }

  /** @override */
  isGoogRequire() {
    return false;
  }

  /** @override */
  isEs6Import() {
    return true;
  }
}

/**
 * Interface for resolving module specifiers.
 * @interface
 */
class ModuleResolver {
  /**
   * @param {string} fromPath The path of the module that is doing the
   *     importing.
   * @param {string} importSpec The raw text of the import.
   * @return {string} The resolved path of the referenced module.
   */
  resolve(fromPath, importSpec) {}
}

/** @implements {ModuleResolver} */
class PathModuleResolver {
  /** @override */
  resolve(fromPath, importSpec) {
    return path.resolve(path.dirname(fromPath), importSpec);
  }
}

class InvalidCycleError extends Error {
  /**
   * @param {!Array<!Dependency>} deps
   */
  constructor(deps) {
    super(
        'There exists at least one cycle with a Closure file, which is ' +
        'invalid. Files involved in cycle(s):' +
        deps.map(dep => dep.path).join(', '));
    this.deps = deps;
  }
}

/**
 * Dependency graph that provides validation along with a topological sorting
 * of dependencies given an entrypoint.
 *
 * A dependency graph is not validated by default, you must call validate() if
 * you wish to perform validation.
 */
class Graph {
  /**
   * @param {!Array<!Dependency>} dependencies
   * @param {!ModuleResolver=} moduleResolver
   */
  constructor(dependencies, moduleResolver = new PathModuleResolver()) {
    /** @const {!Map<string, !Dependency>} */
    this.depsBySymbol = new Map();
    /** @const {!Map<string, !Dependency>} */
    this.depsByPath = new Map();
    /** @const */
    this.moduleResolver = moduleResolver;

    for (const dep of dependencies) {
      if (this.depsByPath.has(dep.path)) {
        throw new Error('File registered twice? ' + dep.path);
      }
      this.depsByPath.set(dep.path, dep);
      // Keep both OS-dependent path and POSIX style path.
      this.depsByPath.set(normalizePath(dep.path), dep);
      for (const sym of dep.closureSymbols) {
        const previous = this.depsBySymbol.get(sym);
        if (previous) {
          throw new SourceError(
              `The symbol "${sym}" has already been defined at ` +
                  previous.path,
              dep.path);
        }
        this.depsBySymbol.set(sym, dep);
      }
    }
  }

  /**
   * Validates the dependency graph. Throws an error if the graph is invalid.
   *
   * This method uses Tarjan's algorithm to ensure Closure files are not part
   * of any cycle. Check it out:
   * https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
   */
  validate() {
    let index = 0;

    // Map that assigns each dependency an index in visit-order.
    const indexMap = new Map();
    // Stack of dependencies that are potentially part of the current strongly
    // connected component. If any dependency has a back pointer it is kept
    // on the stack. Thus after recursion anything left on the stack above the
    // current dependency is part of the SCC. If the dependency has no back
    // pointer the SCC is created from all dependencies on the stack until the
    // current dependency is popped off and added to the SCC.
    const depStack = new Set();

    const validate = (dep) => {
      const thisIndex = index++;
      indexMap.set(dep, thisIndex);
      let lowIndex = thisIndex;

      depStack.add(dep);

      // We might modify the imports when iterating (drop unrecognized ES6
      // imports), so iterate over a copy.
      for (const i of [...dep.imports]) {
        const to = this.resolve_(i);

        if (!to) {
          if (i.isGoogRequire()) {
            throw new SourceError(`Could not find "${i.symOrPath}".`, dep.path);
          } else {
            // Just drop unrecognized ES6 imports. Assume their entire branch is
            // non-Closure, like a built-in Node module.
            dep.imports.splice(dep.imports.indexOf(i), 1);
            console.warn(
                `Could not find "${i.symOrPath}".` +
                    'Assuming it (and its transitive dependencies) are ' +
                    'non-Closure managed.',
                dep.path);
            continue;
          }
        }

        i.validate(to);

        if (!indexMap.has(to)) {
          // "to" has not been visited, recurse.
          lowIndex = Math.min(lowIndex, validate(to));
        } else if (depStack.has(to)) {
          // "to" is on the stack and thus a part of the SCC.
          lowIndex = Math.min(lowIndex, indexMap.get(to));
        }
        // else visited but not on the stack, so it is not part of the SCC. It
        // is a common dependency of some other tree, but does not reach this
        // dependency and thus is not strongly connected.
      }

      if (lowIndex === thisIndex) {
        let anyClosure = false;
        const deps = [...depStack];
        const scc = [];
        for (let i = deps.length - 1; i > -1; i--) {
          scc.push(deps[i]);
          depStack.delete(deps[i]);
          anyClosure = anyClosure ||
              deps[i].type === DependencyType.CLOSURE_PROVIDE ||
              deps[i].type === DependencyType.CLOSURE_MODULE;
          if (deps[i] === dep) {
            break;
          }
        }
        if (anyClosure && scc.length > 1) {
          throw new InvalidCycleError(scc);
        }
      }

      return lowIndex;
    };

    for (const dep of this.depsByPath.values()) {
      if (!indexMap.has(dep)) {
        validate(dep);
      }
    }
  }

  /**
   * @param {!Import} i
   * @return {!Dependency}
   * @private
   */
  resolve_(i) {
    return i instanceof GoogRequire ?
        this.depsBySymbol.get(i.symOrPath) :
        this.depsByPath.get(
            this.moduleResolver.resolve(i.from.path, i.symOrPath));
  }

  /**
   * Provides a topological sorting of dependencies given the entrypoints.
   *
   * @param {...!Dependency} entrypoints
   * @return {!Array<!Dependency>}
   */
  order(...entrypoints) {
    const deps = [];
    const visited = new Set();

    const visit = (dep) => {
      if (visited.has(dep)) return;
      visited.add(dep);
      for (const i of dep.imports) {
        const next = this.resolve_(i);
        visit(next);
      }
      deps.push(dep);
    };

    for (const entrypoint of entrypoints) {
      visit(entrypoint);
    }

    return deps;
  }
}

module.exports = {
  DependencyType,
  Dependency,
  ParsedDependency,
  GoogRequire,
  Es6Import,
  Graph,
  ModuleResolver,
  PathModuleResolver,
  InvalidCycleError,
};
