| // 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. |
| |
| // TODO(joshualitt): This is a good start for a fuzzer. There is still work to |
| // do: |
| // * Emit some classes as const and some not |
| // * Randomize what we emit as we walk the graph so it is more sparse. |
| |
| import 'dart:io'; |
| import 'dart:math'; |
| import 'package:dart_style/dart_style.dart' show DartFormatter; |
| |
| 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; |
| |
| /// A map of bit positions to lists of class names. |
| final Map<int, List<String>> classNames = {}; |
| final Map<int, List<String>> mixerClassNames = {}; |
| |
| /// A map of bit positions to lists of mixin names. |
| final Map<int, List<String>> mixinNames = {}; |
| |
| /// A map of bit positions to lists of class names used only as types. |
| final Map<int, List<String>> typeNames = {}; |
| final Map<int, List<String>> mixerTypeNames = {}; |
| final Map<int, List<String>> closureNames = {}; |
| |
| /// 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'); |
| } |
| |
| void newline(StringBuffer out) { |
| out.write('\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. |
| """); |
| } |
| } |
| |
| /// Generates the root import, where classes, types, mixins, and closures |
| /// live. |
| 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'); |
| |
| // Sort the names to ensure they are in a canonical order. |
| var nameKeys = names.keys.toList(); |
| nameKeys.sort(); |
| |
| // Generate the 'base' classes, mixins, and types which will be combined to |
| // generate hierarchies. Also generate a const instance per class and a closure |
| // to invoke. |
| Set<String> uniques = {}; |
| for (var bitPosition in nameKeys) { |
| var bitsList = names[bitPosition]; |
| for (var bits in bitsList) { |
| var name = generateBitString(bits); |
| if (!uniques.add(name)) continue; |
| String className = 'C$name'; |
| String mixinName = 'M$name'; |
| String typeName = 'T$name'; |
| (classNames[bitPosition] ??= []).add(className); |
| (mixinNames[bitPosition] ??= []).add(mixinName); |
| (typeNames[bitPosition] ??= []).add(typeName); |
| (mixerClassNames[bitPosition] ??= []).add(className); |
| (mixerTypeNames[bitPosition] ??= []).add(typeName); |
| out.write('class $className { const $className(); }\n'); |
| out.write('class $mixinName {}\n'); |
| out.write('class $typeName {}\n'); |
| out.write('const $className i$className = const $className();\n'); |
| out.write('closure$className(foo) => ($className unused) '); |
| out.write('=> i$className.toString() == foo.toString();\n'); |
| } |
| } |
| |
| // Generate combined classes and types, as well as const instances and |
| // closures. |
| newline(out); |
| uniques = {}; |
| for (var bitPosition in nameKeys) { |
| var bitsList = names[bitPosition]; |
| for (var bits in bitsList) { |
| var name = generateBitString(bits); |
| var bitCount = bits.reduce((a, b) => a + b); |
| var baseName = 'C$name'; |
| if (!uniques.add(baseName)) continue; |
| if (bitCount > 1) { |
| List<String> classes = []; |
| List<String> mixins = []; |
| List<String> types = []; |
| for (int i = 0; i < bits.length; i++) { |
| if (bits[i] == 1) { |
| classes.addAll(classNames[i]); |
| mixins.addAll(mixinNames[i]); |
| types.addAll(typeNames[i]); |
| } |
| } |
| String mixinString = mixins.join(', '); |
| int count = 1; |
| assert(classes.length == types.length); |
| for (int i = 0; i < classes.length; i++) { |
| var cls = classes[i]; |
| var type = types[i]; |
| List<String> classImpls = []; |
| List<String> typeImpls = []; |
| if (i > 0) { |
| classImpls.addAll(classes.sublist(0, i)); |
| typeImpls.addAll(types.sublist(0, i)); |
| } |
| if (i < classes.length - 1) { |
| classImpls.addAll(classes.sublist(i + 1)); |
| typeImpls.addAll(types.sublist(i + 1)); |
| } |
| var classImplementsString = classImpls.join(', '); |
| String className = '${baseName}_class_${count}'; |
| out.write('class $className extends $cls with $mixinString '); |
| out.write( |
| 'implements $classImplementsString { const $className(); }\n'); |
| out.write('const $className i$className = const $className();\n'); |
| out.write('closure$className(foo) => ($className unused) '); |
| out.write('=> i$className.toString() == foo.toString();\n'); |
| |
| var typeImplementsString = typeImpls.join(', '); |
| String typeName = 'T${name}_type__${count}'; |
| out.write('class $typeName extends $type with $mixinString '); |
| out.write('implements $typeImplementsString {}\n'); |
| for (int i = 0; i < bits.length; i++) { |
| if (bits[i] == 1) { |
| mixerClassNames[i].add(className); |
| mixerTypeNames[i].add(typeName); |
| } |
| } |
| count++; |
| } |
| } |
| } |
| } |
| |
| // Generate functions. |
| newline(out); |
| uniques = {}; |
| 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"); |
| |
| // create type test. |
| noInlineDecorator(out); |
| out.write('typeTest(dynamic t) {\n'); |
| for (var type in mixerTypeNames[bit]) { |
| out.write(' if (t is $type) { return true; }\n'); |
| } |
| out.write(' return false;\n'); |
| out.write('}\n\n'); |
| |
| noInlineDecorator(out); |
| out.write('g$name() {\n'); |
| out.write(' // C${generateCommentName(bits, bit)};\n'); |
| |
| // Construct new instances of each class and pass them to the typeTest |
| for (var cls in mixerClassNames[bit]) { |
| out.write(' Expect.isFalse(typeTest($cls()));\n'); |
| } |
| newline(out); |
| |
| // Invoke the test closure for each class. |
| for (var cls in mixerClassNames[bit]) { |
| out.write(' Expect.isTrue(closure$cls($cls())($cls()));\n'); |
| } |
| newline(out); |
| |
| // Verify the runtimeTypes of the closures haven't been mangled. |
| for (var cls in mixerClassNames[bit]) { |
| out.write(' Expect.equals(closure$cls($cls()).runtimeType.toString(), '); |
| out.write("'($cls) => bool');\n"); |
| } |
| newline(out); |
| |
| // Collect the names so we can sort them and put them in a canonical order. |
| int count = 0; |
| List<String> namesBits = []; |
| names[bit].forEach((nameBits) { |
| var nameString = generateBitString(nameBits); |
| namesBits.add(nameString); |
| count++; |
| }); |
| |
| out.write(' Set<String> uniques = {};\n\n' |
| ' // f${generateCommentName(bits, bit)};\n'); |
| |
| 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(DartFormatter().format(contents.toString())); |
| 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(); |
| } |