// Copyright (c) 2021, the Dart project authors.  Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.

/// This tool builds a program with a deferred graph isomorphic to the provided
/// graph, or generates permutations of bits and the associated files to
/// generate complex deferred graphs.

/// For example, if 5 bits are permuted, we end up with files like:
///   lib1.dart
///   lib2.dart
///   lib3.dart
///   lib4.dart
///   lib5.dart
///   libB.dart
///   lib_000_01.dart
///   lib_000_10.dart
///   lib_001_00.dart
///   lib_010_00.dart
///   lib_100_00.dart
///   main.dart
///
/// Where
///   main.dart contains main().
///   libX.dart contains the actual deferred import of the file with the bit at
///     the X position starting from the left, ie lib1 imports lib_100_00, lib2
///     imports lib_010_00, etc.
///   libImport.dart is the 'top of the diamond' which contains all of the code.
///   lib_XXX_XX.dart invokes all of the functions in libImport which have a
///     1 bit at that position, ie lib_100_00 invokes all code in libImport with
///     a first bit of 1, f100_00, f110_00, etc.
///
/// Note: There are restrictions to what we can generate. Specifically, certain
/// OutputUnits can never be empty, namely we will always generate one file for
/// each entryLib, and because of our dependency on expect, we will always have
/// a file representing the intersection of all import entities. So, for example
/// with three bits, each of 100, 010, 001 and 111 must be present in the graph
/// file, but 110, 101, and 011 are optional.

import 'dart:io';
import 'dart:math';

typedef NameFunc = String Function(List<int>, int);

/// A simple constant pass through function for bit strings that don't need
/// special printing, ie stops.
String passThroughNameFunc(List<int> l, int i) => l[i].toString();

/// Generates all permutations of bits recursively.
void generatePermutedNames(
    Map<int, List<List<int>>> names, int maxBit, List<int> bits, int bit) {
  if (bit == maxBit) {
    for (int i = 0; i < bits.length; i++) {
      if (bits[i] == 1) {
        names.putIfAbsent(i, () => []);
        names[i].add(List.from(bits));
      }
    }
    return;
  }
  generatePermutedNames(names, maxBit, bits, bit + 1);
  bits[bit] = 1;
  generatePermutedNames(names, maxBit, bits, bit + 1);
  bits[bit] = 0;
}

/// A helper function to generate names from lists of strings of bits.
int namesFromGraphFileLines(
    List<String> lines, Map<int, List<List<int>>> names) {
  int maxBit = 0;
  for (var line in lines) {
    List<int> name = [];
    // Each line should have the same length.
    assert(maxBit == 0 || maxBit == line.length);
    maxBit = max(maxBit, line.length);
    for (int i = 0; i < line.length; i++) {
      var bit = line[i];
      if (bit == '1') {
        name.add(1);
        (names[i] ??= []).add(name);
      } else {
        name.add(0);
      }
    }
  }
  return maxBit;
}

/// Parses names from a graph file dumped from dart2js and returns the max bit.
int namesFromGraphFile(String graphFile, Map<int, List<List<int>>> names) {
  var lines = File(graphFile).readAsLinesSync();
  return namesFromGraphFileLines(lines, names);
}

class ImportData {
  String import;
  String entryPoint;

  ImportData(this.import, this.entryPoint);
}

class GraphIsomorphizer {
  /// The output directory, only relevant if files are written out.
  final String outDirectory;

  /// Various buffers for the files the GraphIsomorphizer generates.
  StringBuffer rootImportBuffer = StringBuffer();
  StringBuffer mainBuffer = StringBuffer();
  Map<String, StringBuffer> mixerLibBuffers = {};
  Map<String, StringBuffer> entryLibBuffers = {};

  /// A map of bit positions to lists of bit lists.
  final Map<int, List<List<int>>> names;

  /// We will permute bits up until the maximum bit.
  int maxBit = 0;

  /// The 'top of the diamond' import file containing all code.
  final String rootImportFilename = 'libImport.dart';

  /// The main filename.
  final String mainFilename = 'main.dart';

  /// A bool to omit the comment block.
  final bool skipCopyright;

  GraphIsomorphizer(this.names, this.maxBit,
      {this.outDirectory: '.', this.skipCopyright: false});

  void noInlineDecorator(StringBuffer out) {
    out.write("@pragma('dart2js:noInline')\n");
  }

  void importExpect(StringBuffer out) {
    out.write('import "package:expect/expect.dart";\n\n');
  }

  /// Generates the header for a file.
  void generateHeader(StringBuffer out) {
    if (!skipCopyright) {
      out.write("""
// Copyright (c) 2021, the Dart project authors.  Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.

// This file was autogenerated by the pkg/compiler/tool/graph_isomorphizer.dart.

""");
    }
  }

  void generateRootImport(StringBuffer out) {
    generateHeader(out);
    importExpect(out);

    // We verify that each function in libImport is invoked only once from each
    // mixerLib and that only the correct functions are called, ie for lib_001,
    // only functions with XX1 are invoked.
    out.write('void v(Set<String> u, String name, int bit) {\n' +
        '  Expect.isTrue(u.add(name));\n' +
        "  Expect.equals(name[bit], '1');\n" +
        '}\n\n');

    Set<String> uniques = {};

    // Sort the names to ensure they are in a canonical order.
    var nameKeys = names.keys.toList();
    nameKeys.sort();
    for (var name in nameKeys) {
      var bitsList = names[name];
      for (var bits in bitsList) {
        var name = generateBitString(bits);
        if (uniques.add(name)) {
          noInlineDecorator(out);
          var stringBits = generateBitString(bits, withStops: false);
          out.write(
              "f$name(Set<String> u, int b) => v(u, '$stringBits', b);\n");
        }
      }
    }
  }

  /// Generates a mixerLib which will be loaded as a deferred library from an entryLib.
  void generateMixerLib(
      String name, StringBuffer out, String import, List<int> bits, int bit) {
    generateHeader(out);
    importExpect(out);
    out.write("import '$import';\n\n");
    noInlineDecorator(out);
    out.write('g$name() {\n'
        '  Set<String> uniques = {};\n\n'
        '  // f${generateCommentName(bits, bit)};\n');
    int count = 0;

    // Collect the names so we can sort them and put them in a canonical order.
    List<String> namesBits = [];
    names[bit].forEach((nameBits) {
      var nameString = generateBitString(nameBits);
      namesBits.add(nameString);
      count++;
    });

    namesBits.sort();
    for (var name in namesBits) {
      out.write('  f$name(uniques, $bit);\n');
    }

    // We expect 'count' unique strings added to be added to 'uniques'.
    out.write("  Expect.equals($count, uniques.length);\n"
        '}\n');
  }

  /// Generates a string of bits, with optional parameters to control how the
  /// bits print.
  String generateBitString(List<int> bits,
      {NameFunc f: passThroughNameFunc, bool withStops: true}) {
    int stop = 0;
    StringBuffer sb = StringBuffer();
    for (int i = 0; i < bits.length; i++) {
      if (stop++ % 3 == 0 && withStops) {
        sb.write('_');
      }
      sb.write(f(bits, i));
    }
    return sb.toString();
  }

  /// Generates a pretty bit string for use in comments.
  String generateCommentName(List<int> bits, int fixBit) {
    return generateBitString(bits,
        f: (List<int> bits, int bit) => bit == fixBit ? '1' : '*');
  }

  /// Generates an entryLib file.
  void generateEntryLib(StringBuffer out, String mainName, String funcName,
      String import, int bit) {
    generateHeader(out);
    var name = 'b$bit';
    out.write("import '$import' deferred as $name;\n\n"
        '$mainName async {\n'
        '  await $name.loadLibrary();\n'
        '  $name.g$funcName();\n'
        '}\n');
  }

  /// Generates entry and mixer libs for the supplied names.
  List<ImportData> generateEntryAndMixerLibs() {
    // Generates each lib_XXX.dart and the associated entryLib file.
    List<ImportData> importData = [];
    for (int i = 1; i <= maxBit; i++) {
      // Generate the bit list representing this library. ie a list of all
      // 0s with a single 1 bit flipped.
      int oneBit = i - 1;
      List<int> bits = [];
      for (int j = 0; j < maxBit; j++) bits.add(j == oneBit ? 1 : 0);

      // Generate the mixerLib for this entryLib.
      var name = generateBitString(bits);
      var mixerLibBuffer = StringBuffer();
      var mixerLibName = "lib$name.dart";
      generateMixerLib(name, mixerLibBuffer, rootImportFilename, bits, oneBit);
      mixerLibBuffers[mixerLibName] = mixerLibBuffer;

      // Generate the entryLib for this mixerLib.
      var entryLibName = 'lib$i.dart';
      var entryFuncName = 'entryLib$i()';
      var entryLibBuffer = StringBuffer();
      generateEntryLib(entryLibBuffer, entryFuncName, name, mixerLibName, i);
      entryLibBuffers[entryLibName] = entryLibBuffer;

      // Stash the entry point in entryLib for later reference in the main file.
      importData.add(ImportData(entryLibName, entryFuncName));
    }
    return importData;
  }

  /// Generates the main file.
  void generateMain(StringBuffer out, List<ImportData> importData) {
    generateHeader(mainBuffer);
    for (var data in importData) {
      out.write("import '${data.import}';\n");
    }
    out.write('\n'
        'main() {\n');
    for (var data in importData) {
      out.write('  ${data.entryPoint};\n');
    }
    out.write('}\n');
  }

  /// Generates all files into buffers.
  void generateFiles() {
    generateRootImport(rootImportBuffer);
    var importData = generateEntryAndMixerLibs();
    generateMain(mainBuffer, importData);
  }

  /// Helper to dump contents to file.
  void writeToFile(String filename, StringBuffer contents) {
    var file = File(this.outDirectory + '/' + filename);
    file.createSync(recursive: true);
    var sink = file.openWrite();
    sink.write(contents);
    sink.close();
  }

  /// Writes all buffers to files.
  void writeFiles() {
    mixerLibBuffers.forEach(writeToFile);
    entryLibBuffers.forEach(writeToFile);
    writeToFile(rootImportFilename, rootImportBuffer);
    writeToFile(mainFilename, mainBuffer);
  }

  /// Generate and write files.
  void run() {
    generateFiles();
    writeFiles();
  }
}

/// Creates a GraphIsomorphizer based on the provided args.
GraphIsomorphizer createGraphIsomorphizer(List<String> args) {
  int maxBit = 0;
  String graphFile = '';
  String outDirectory = '.';

  for (var arg in args) {
    if (arg.startsWith('--max-bit')) {
      maxBit = int.parse(arg.substring('--max-bit='.length));
    }
    if (arg.startsWith('--graph-file')) {
      graphFile = arg.substring('--graph-file='.length);
    }
    if (arg.startsWith('--out-dir')) {
      outDirectory = arg.substring('--out-dir='.length);
    }
  }

  // If we don't have a graphFile, then we generate all permutations of bits up
  // to maxBit.
  Map<int, List<List<int>>> names = {};
  if (graphFile.isEmpty) {
    List<int> bits = List.filled(maxBit, 0);
    generatePermutedNames(names, maxBit, bits, 0);
  } else {
    maxBit = namesFromGraphFile(graphFile, names);
  }
  return GraphIsomorphizer(names, maxBit, outDirectory: outDirectory);
}

void main(List<String> args) {
  var graphIsomorphizer = createGraphIsomorphizer(args);
  graphIsomorphizer.run();
}