<commit_before>
// Copyright 2020 Google LLC. 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 yaml = require('js-yaml');
const fs = require('fs');
const path = require('path');
const {printTable} = require('console-table-printer');

const DEPENDENCY_GRAPH =
    JSON.parse(fs.readFileSync('scripts/package_dependencies.json'));

// This is a reverse dependencies graph. Each entry in the graph lists the
// packages that depend on it.
const REVERSE_DEPENDENCY_GRAPH = transposeGraph(DEPENDENCY_GRAPH);

// Topologically sort the dependency tree and arrange
// steps in dependency order.
const DEPENDENCY_ORDER = topologicalSort(DEPENDENCY_GRAPH);

// Steps to exclude from cloudbuild files.
const EXCLUDE_STEPS = new Set(['build-deps', 'yarn-common']);

/**
 * Verify that an object is a valid graph.
 */
function verifyGraph(graph) {
  const nodes = new Set(Object.keys(graph));
  for (const [node, edges] of Object.entries(graph)) {
    for (const edge of edges) {
      if (!nodes.has(edge)) {
        throw new Error(
            `Graph edge ${edge} of node ${node} not found in the graph`);
      }
    }
  }
}

/**
 * Transpose a directed graph i.e. reverse the direction of the edges.
 */
function transposeGraph(graph) {
  verifyGraph(graph);
  const transposed = {};
  for (const [nodeName, connectedNodes] of Object.entries(graph)) {
    for (const connectedNode of connectedNodes) {
      if (!transposed[connectedNode]) {
        transposed[connectedNode] = new Set();
      }
      if (!transposed[nodeName]) {
        // Make sure the node itself ends up in the transposed graph.
        transposed[nodeName] = new Set();
      }
      transposed[connectedNode].add(nodeName);
    }
  }
  return transposed;
}

/**
 * Topologically sort a directed acyclic graph.
 *
 * Returns a list of graph nodes such that, by following edges,
 * you can only move forward in the list, not backward.
 */
function topologicalSort(graph) {
  // We can't use a standard sorting algorithm because
  // often, two packages won't have any dependency relationship
  // between each other, meaning they are incomparable.
  verifyGraph(graph);
  const sorted = [];

  while (sorted.length < Object.keys(graph).length) {
    // Find nodes not yet in 'sorted' that have edges
    // only to nodes already in 'sorted'
    const emptyNodes = Object.entries(graph)
                           .filter(([node, edges]) => {
                             if (sorted.includes(node)) {
                               return false;
                             }
                             for (const edge of edges) {
                               if (!sorted.includes(edge)) {
                                 return false;
                               }
                             }
                             return true;
                           })
                           .map(([node, edges]) => node);

    // If there are no such nodes, then the graph has a cycle.
    if (emptyNodes.length === 0) {
      throw new Error('Dependency graph has a cycle.');
    }

    for (node of emptyNodes) {
      sorted.push(node);
    }
  }
  return sorted;
}

/**
 * Find all subnodes in the subgraph generated by taking the transitive
 * closure at `node`.
 */
function findSubgraph(node, graph, subnodes = new Set()) {
  const directSubnodes = graph[node];
  if (directSubnodes) {
    for (const directSubnode of directSubnodes) {
      if (!subnodes.has(directSubnode)) {
        subnodes.add(directSubnode);
        findSubgraph(directSubnode, graph, subnodes);
      }
    }
  }

  return subnodes;
}

/**
 * Find the transitive closure of dependencies of the given packages.
 */
function findDeps(packages) {
  return new Set(
      [...packages]
          .map(packageName => findSubgraph(packageName, DEPENDENCY_GRAPH))
          .reduce((a, b) => [...a, ...b]));
}

/**
 * Find the reverse dependencies of the given packages, i.e. find the
 * set of packages that include at least one of the given packages in
 * their transitive closure of dependencies.
 */
function findReverseDeps(packages) {
  return new Set([
    ...packages
  ].map(packageName => findSubgraph(packageName, REVERSE_DEPENDENCY_GRAPH))
                     .reduce((a, b) => [...a, ...b]));
}

/**
 * Construct a cloudbuild.yml file that does the following:
 * 1. Builds all the dependencies of `packages`
 * 2. Builds and tests all the packages in `packages`
 * 3. Builds and tests all the reverse dependnecies of `packages`
 */
function generateCloudbuild(packages, print = true) {
  // Make sure all packages are declared in package_dependencies.json.
  const allPackages = new Set(Object.keys(DEPENDENCY_GRAPH));
  for (const packageName of packages) {
    if (!allPackages.has(packageName)) {
      throw new Error(
          `Package ${packageName} was not declared in ` +
          'package_dependencies.json');
    }
  }

  const deps = findDeps(packages);<commit_msg>Add initial values for reduce in generate_cloudbuild (#4250)<commit_after>
// Copyright 2020 Google LLC. 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 yaml = require('js-yaml');
const fs = require('fs');
const path = require('path');
const {printTable} = require('console-table-printer');

const DEPENDENCY_GRAPH =
    JSON.parse(fs.readFileSync('scripts/package_dependencies.json'));

// This is a reverse dependencies graph. Each entry in the graph lists the
// packages that depend on it.
const REVERSE_DEPENDENCY_GRAPH = transposeGraph(DEPENDENCY_GRAPH);

// Topologically sort the dependency tree and arrange
// steps in dependency order.
const DEPENDENCY_ORDER = topologicalSort(DEPENDENCY_GRAPH);

// Steps to exclude from cloudbuild files.
const EXCLUDE_STEPS = new Set(['build-deps', 'yarn-common']);

/**
 * Verify that an object is a valid graph.
 */
function verifyGraph(graph) {
  const nodes = new Set(Object.keys(graph));
  for (const [node, edges] of Object.entries(graph)) {
    for (const edge of edges) {
      if (!nodes.has(edge)) {
        throw new Error(
            `Graph edge ${edge} of node ${node} not found in the graph`);
      }
    }
  }
}

/**
 * Transpose a directed graph i.e. reverse the direction of the edges.
 */
function transposeGraph(graph) {
  verifyGraph(graph);
  const transposed = {};
  for (const [nodeName, connectedNodes] of Object.entries(graph)) {
    for (const connectedNode of connectedNodes) {
      if (!transposed[connectedNode]) {
        transposed[connectedNode] = new Set();
      }
      if (!transposed[nodeName]) {
        // Make sure the node itself ends up in the transposed graph.
        transposed[nodeName] = new Set();
      }
      transposed[connectedNode].add(nodeName);
    }
  }
  return transposed;
}

/**
 * Topologically sort a directed acyclic graph.
 *
 * Returns a list of graph nodes such that, by following edges,
 * you can only move forward in the list, not backward.
 */
function topologicalSort(graph) {
  // We can't use a standard sorting algorithm because
  // often, two packages won't have any dependency relationship
  // between each other, meaning they are incomparable.
  verifyGraph(graph);
  const sorted = [];

  while (sorted.length < Object.keys(graph).length) {
    // Find nodes not yet in 'sorted' that have edges
    // only to nodes already in 'sorted'
    const emptyNodes = Object.entries(graph)
                           .filter(([node, edges]) => {
                             if (sorted.includes(node)) {
                               return false;
                             }
                             for (const edge of edges) {
                               if (!sorted.includes(edge)) {
                                 return false;
                               }
                             }
                             return true;
                           })
                           .map(([node, edges]) => node);

    // If there are no such nodes, then the graph has a cycle.
    if (emptyNodes.length === 0) {
      throw new Error('Dependency graph has a cycle.');
    }

    for (node of emptyNodes) {
      sorted.push(node);
    }
  }
  return sorted;
}

/**
 * Find all subnodes in the subgraph generated by taking the transitive
 * closure at `node`.
 */
function findSubgraph(node, graph, subnodes = new Set()) {
  const directSubnodes = graph[node];
  if (directSubnodes) {
    for (const directSubnode of directSubnodes) {
      if (!subnodes.has(directSubnode)) {
        subnodes.add(directSubnode);
        findSubgraph(directSubnode, graph, subnodes);
      }
    }
  }

  return subnodes;
}

/**
 * Find the transitive closure of dependencies of the given packages.
 */
function findDeps(packages) {
  return new Set(
      [...packages]
          .map(packageName => findSubgraph(packageName, DEPENDENCY_GRAPH))
          .reduce((a, b) => [...a, ...b], []));
}

/**
 * Find the reverse dependencies of the given packages, i.e. find the
 * set of packages that include at least one of the given packages in
 * their transitive closure of dependencies.
 */
function findReverseDeps(packages) {
  return new Set([
    ...packages
  ].map(packageName => findSubgraph(packageName, REVERSE_DEPENDENCY_GRAPH))
                     .reduce((a, b) => [...a, ...b], []));
}

/**
 * Construct a cloudbuild.yml file that does the following:
 * 1. Builds all the dependencies of `packages`
 * 2. Builds and tests all the packages in `packages`
 * 3. Builds and tests all the reverse dependnecies of `packages`
 */
function generateCloudbuild(packages, print = true) {
  // Make sure all packages are declared in package_dependencies.json.
  const allPackages = new Set(Object.keys(DEPENDENCY_GRAPH));
  for (const packageName of packages) {
    if (!allPackages.has(packageName)) {
      throw new Error(
          `Package ${packageName} was not declared in ` +
          'package_dependencies.json');
    }
  }

  const deps = findDeps(packages);
{'fraction_non_alphanumeric': 0.12011447992129505, 'fraction_numerical': 0.0025042482783293085, 'mean_word_length': 2.5793854033290655, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 15, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6515381', 'n_tokens_mistral': 3081, 'n_tokens_neox': 3016, 'n_words': 1080}