"use strict";

const { PackageGraph } = require("@lerna/package-graph");

/**
 * @typedef {object} QueryGraphConfig
 * @property {'allDependencies'|'dependencies'} [graphType] "dependencies" excludes devDependencies from graph
 * @property {boolean} [rejectCycles] Whether or not to reject dependency cycles
 */

/**
 * A mutable PackageGraph used to query for next available packages.
 */
class QueryGraph {
  /**
   * @param {import("@lerna/package")[]} packages An array of Packages to build the graph out of
   * @param {QueryGraphConfig} [options]
   * @constructor
   */
  constructor(packages, { graphType = "allDependencies", rejectCycles } = {}) {
    // Create dependency graph
    this.graph = new PackageGraph(packages, graphType);

    // Evaluate cycles
    this.cycles = this.graph.collapseCycles(rejectCycles);
  }

  _getNextLeaf() {
    return Array.from(this.graph.values()).filter((node) => node.localDependencies.size === 0);
  }

  _getNextCycle() {
    const cycle = Array.from(this.cycles).find((cycleNode) => cycleNode.localDependencies.size === 0);

    if (!cycle) {
      return [];
    }

    this.cycles.delete(cycle);

    return cycle.flatten();
  }

  getAvailablePackages() {
    // Get the next leaf nodes
    const availablePackages = this._getNextLeaf();

    if (availablePackages.length > 0) {
      return availablePackages;
    }

    return this._getNextCycle();
  }

  markAsTaken(name) {
    this.graph.delete(name);
  }

  markAsDone(candidateNode) {
    this.graph.remove(candidateNode);

    for (const cycle of this.cycles) {
      cycle.unlink(candidateNode);
    }
  }
}

module.exports = QueryGraph;
module.exports.QueryGraph = QueryGraph;
module.exports.toposort = toposort;

/**
 * Sort the input list topologically.
 *
 * @param {import("@lerna/package")[]} packages An array of Packages to build the list out of
 * @param {QueryGraphConfig} [options]
 *
 * @returns {import("@lerna/package")[]} A list of Package instances in topological order
 */
function toposort(packages, options) {
  const graph = new QueryGraph(packages, options);
  const result = [];

  let batch = graph.getAvailablePackages();

  while (batch.length) {
    for (const node of batch) {
      // no need to take() in synchronous loop
      result.push(node.pkg);
      graph.markAsDone(node);
    }

    batch = graph.getAvailablePackages();
  }

  return result;
}

@@ -402,16 +402,731 @@
 Graph %7B%0A
+  /**%0A   * Sort a list of Packages topologically.%0A   *%0A   * @param %7Bimport(%22@lerna/package%22)%5B%5D%7D packages An array of Packages to build the list out of%0A   * @param %7BQueryGraphConfig%7D %5Boptions%5D%0A   *%0A   * @returns %7Bimport(%22@lerna/package%22)%5B%5D%7D A list of Package instances in topological order%0A   */%0A  static toposort(packages, options) %7B%0A    const graph = new QueryGraph(packages, options);%0A    const result = %5B%5D;%0A%0A    let batch = graph.getAvailablePackages();%0A%0A    while (batch.length) %7B%0A      for (const node of batch) %7B%0A        // no need to take() in synchronous loop%0A        result.push(node.pkg);%0A        graph.markAsDone(node);%0A      %7D%0A%0A      batch = graph.getAvailablePackages();%0A    %7D%0A%0A    return result;%0A  %7D%0A%0A
   /**%0A  
@@ -2429,683 +2429,25 @@
 t = 
-toposort;%0A%0A/**%0A * Sort the input list topologically.%0A *%0A * @param %7Bimport(%22@lerna/package%22)%5B%5D%7D packages An array of Packages to build the list out of%0A * @param %7BQueryGraphConfig%7D %5Boptions%5D%0A *%0A * @returns %7Bimport(%22@lerna/package%22)%5B%5D%7D A list of Package instances in topological order%0A */%0Afunction toposort(packages, options) %7B%0A  const graph = new QueryGraph(packages, options);%0A  const result = %5B%5D;%0A%0A  let batch = graph.getAvailablePackages();%0A%0A  while (batch.length) %7B%0A    for (const node of batch) %7B%0A      // no need to take() in synchronous loop%0A      result.push(node.pkg);%0A      graph.markAsDone(node);%0A    %7D%0A%0A    batch = graph.getAvailablePackages();%0A  %7D%0A%0A  return result;%0A%7D
+QueryGraph.toposort;
 %0A

Move toposort helper to static method, preserving named export