Faster read; faster lookup; more tests; error on new package inside existing package root

Previously adding (reading a file consisting of) n non-overlapping
packages took O(n^2) time.
Looking up a single package in a structure with n non-overlapping
packages took O(n) time.

Here this is changed so the timings are more like O(n) and O(1),
respectively.

(all of these should be taken with a grain of salt as not only the
number of packages influence the time, but also the length of the paths
which I completely ignore here).

Run like this:
```
$ for i in 1 10 100 1000 5000 10000 50000; do dart test/bench.dart $i;
done
```

(With no warmup, only run once etc --- there's lots of variations
between runs, but for this purpose it doesn't really matter.)

Before:
Read file with 1 packages in 18 ms, looked up all packages in 0 ms
Read file with 10 packages in 22 ms, looked up all packages in 0 ms
Read file with 100 packages in 28 ms, looked up all packages in 1 ms
Read file with 1000 packages in 78 ms, looked up all packages in 14 ms
Read file with 5000 packages in 442 ms, looked up all packages in 384 ms
Read file with 10000 packages in 2254 ms, looked up all packages in 1826 ms
Read file with 50000 packages in 67572 ms, looked up all packages in 84050 ms

After:
Read file with 1 packages in 24 ms, looked up all packages in 0 ms
Read file with 10 packages in 23 ms, looked up all packages in 0 ms
Read file with 100 packages in 25 ms, looked up all packages in 1 ms
Read file with 1000 packages in 60 ms, looked up all packages in 6 ms
Read file with 5000 packages in 127 ms, looked up all packages in 10 ms
Read file with 10000 packages in 187 ms, looked up all packages in 13 ms
Read file with 50000 packages in 525 ms, looked up all packages in 61 ms

Furthermore:
* Previously no error was given if a package was inside the package root
  of another package. Now an error is given and tests are added.
* Previously at least one test didn't work because of a json syntax
  error. This has been fixed.
diff --git a/lib/src/package_config_impl.dart b/lib/src/package_config_impl.dart
index 4167d35..c22622b 100644
--- a/lib/src/package_config_impl.dart
+++ b/lib/src/package_config_impl.dart
@@ -54,12 +54,12 @@
   static PackageTree _validatePackages(Iterable<Package> originalPackages,
       List<Package> packages, void Function(Object error) onError) {
     var packageNames = <String>{};
-    var tree = MutablePackageTree();
+    var tree = TrielikePackageTree();
     for (var originalPackage in packages) {
-      SimplePackage? package;
+      SimplePackage? newPackage;
       if (originalPackage is! SimplePackage) {
         // SimplePackage validates these properties.
-        package = SimplePackage.validate(
+        newPackage = SimplePackage.validate(
             originalPackage.name,
             originalPackage.root,
             originalPackage.packageUriRoot,
@@ -68,43 +68,58 @@
             originalPackage.relativeRoot, (error) {
           if (error is PackageConfigArgumentError) {
             onError(PackageConfigArgumentError(packages, 'packages',
-                'Package ${package!.name}: ${error.message}'));
+                'Package ${newPackage!.name}: ${error.message}'));
           } else {
             onError(error);
           }
         });
-        if (package == null) continue;
+        if (newPackage == null) continue;
       } else {
-        package = originalPackage;
+        newPackage = originalPackage;
       }
-      var name = package.name;
+      var name = newPackage.name;
       if (packageNames.contains(name)) {
         onError(PackageConfigArgumentError(
             name, 'packages', "Duplicate package name '$name'"));
         continue;
       }
       packageNames.add(name);
-      tree.add(0, package, (error) {
+      tree.add(newPackage, (error) {
         if (error is ConflictException) {
           // There is a conflict with an existing package.
           var existingPackage = error.existingPackage;
-          if (error.isRootConflict) {
-            onError(PackageConfigArgumentError(
-                originalPackages,
-                'packages',
-                'Packages ${package!.name} and ${existingPackage.name} '
-                    'have the same root directory: ${package.root}.\n'));
-          } else {
-            assert(error.isPackageRootConflict);
-            // Package is inside the package URI root of the existing package.
-            onError(PackageConfigArgumentError(
-                originalPackages,
-                'packages',
-                'Package ${package!.name} is inside the package URI root of '
-                    'package ${existingPackage.name}.\n'
-                    '${existingPackage.name} URI root: '
-                    '${existingPackage.packageUriRoot}\n'
-                    '${package.name} root: ${package.root}\n'));
+          switch (error.conflictType) {
+            case ConflictType.SameRoots:
+              onError(PackageConfigArgumentError(
+                  originalPackages,
+                  'packages',
+                  'Packages ${newPackage!.name} and ${existingPackage.name} '
+                      'have the same root directory: ${newPackage.root}.\n'));
+              break;
+            case ConflictType.Interleaving:
+              // The new package is inside the package URI root of the existing
+              // package.
+              onError(PackageConfigArgumentError(
+                  originalPackages,
+                  'packages',
+                  'Package ${newPackage!.name} is inside the root of '
+                      'package ${existingPackage.name}, and the package root '
+                      'of ${existingPackage.name} is inside the root of '
+                      '${newPackage.name}.\n'
+                      '${existingPackage.name} package root: '
+                      '${existingPackage.packageUriRoot}\n'
+                      '${newPackage.name} root: ${newPackage.root}\n'));
+              break;
+            case ConflictType.InsidePackageRoot:
+              onError(PackageConfigArgumentError(
+                  originalPackages,
+                  'packages',
+                  'Package ${newPackage!.name} is inside the package root of '
+                      'package ${existingPackage.name}.\n'
+                      '${existingPackage.name} package root: '
+                      '${existingPackage.packageUriRoot}\n'
+                      '${newPackage.name} root: ${newPackage.root}\n'));
+              break;
           }
         } else {
           // Any other error.
@@ -367,6 +382,11 @@
   SimplePackage? packageOf(Uri file);
 }
 
+class _TrielikePackageTreeHelper {
+  SimplePackage? package;
+  Map<String, _TrielikePackageTreeHelper> map = {};
+}
+
 /// Packages of a package configuration ordered by root path.
 ///
 /// A package has a root path and a package root path, where the latter
@@ -375,122 +395,120 @@
 /// A package is said to be inside another package if the root path URI of
 /// the latter is a prefix of the root path URI of the former.
 ///
-/// No two packages of a package may have the same root path, so this
-/// path prefix ordering defines a tree-like partial ordering on packages
-/// of a configuration.
-///
+/// No two packages of a package may have the same root path.
 /// The package root path of a package must not be inside another package's
 /// root path.
-/// Entire other packages are allowed inside a package's root or
-/// package root path.
-///
-/// The package tree contains an ordered mapping of unrelated packages
-/// (represented by their name) to their immediately nested packages' names.
-class MutablePackageTree implements PackageTree {
-  /// A list of packages that are not nested inside each other.
-  final List<SimplePackage> packages = [];
+/// Entire other packages are allowed inside a package's root.
+class TrielikePackageTree implements PackageTree {
+  final Map<String, _TrielikePackageTreeHelper> _map = {};
 
-  /// The tree of the immediately nested packages inside each package.
-  ///
-  /// Indexed by [Package.name].
-  /// If a package has no nested packages (which is most often the case),
-  /// there is no tree object associated with it.
-  Map<String, MutablePackageTree>? _packageChildren;
+  /// A list of all packages.
+  final List<SimplePackage> _packages = [];
 
   @override
   Iterable<Package> get allPackages sync* {
-    for (var package in packages) {
+    for (var package in _packages) {
       yield package;
     }
-    var children = _packageChildren;
-    if (children != null) {
-      for (var tree in children.values) {
-        yield* tree.allPackages;
-      }
-    }
   }
 
-  /// Tries to (add) `package` to the tree.
+  bool _checkConflict(_TrielikePackageTreeHelper currentMapHelper,
+      SimplePackage newPackage, void Function(Object error) onError) {
+    if (currentMapHelper.package != null) {
+      var existingPackage = currentMapHelper.package!;
+      // Trying to add package that is inside the existing package.
+      // 1) If it's an exact match it's not allowed (i.e. the roots can't be
+      //    the same).
+      if (newPackage.root.path.length == existingPackage.root.path.length) {
+        onError(ConflictException(
+            newPackage, existingPackage, ConflictType.SameRoots));
+        return true;
+      }
+      // 2) The existing package has a packageUriRoot thats inside the
+      //    root of the new package.
+      if (_beginsWith(0, newPackage.root.toString(),
+          existingPackage.packageUriRoot.toString())) {
+        onError(ConflictException(
+            newPackage, existingPackage, ConflictType.Interleaving));
+        return true;
+      }
+      // 3) The new package is inside the packageUriRoot of existing package.
+      if (_beginsWith(0, existingPackage.packageUriRoot.toString(),
+          newPackage.root.toString())) {
+        onError(ConflictException(
+            newPackage, existingPackage, ConflictType.InsidePackageRoot));
+        return true;
+      }
+    }
+    return false;
+  }
+
+  /// Tries to add `newPackage` to the tree.
   ///
   /// Reports a [ConflictException] if the added package conflicts with an
   /// existing package.
-  /// It conflicts if its root or package root is the same as another
-  /// package's root or package root, or is between the two.
+  /// It conflicts if its root or package root is the same as an existing
+  /// package's root or package root, is between the two, or if it's inside the
+  /// package root of an existing package.
   ///
-  /// If a conflict is detected between [package] and a previous package,
+  /// If a conflict is detected between [newPackage] and a previous package,
   /// then [onError] is called with a [ConflictException] object
-  /// and the [package] is not added to the tree.
+  /// and the [newPackage] is not added to the tree.
   ///
   /// The packages are added in order of their root path.
-  /// It is never necessary to insert a node between two existing levels.
-  void add(
-      int start, SimplePackage package, void Function(Object error) onError) {
-    var path = package.root.toString();
-    for (var treePackage in packages) {
-      // Check is package is inside treePackage.
-      var treePackagePath = treePackage.root.toString();
-      assert(treePackagePath.length > start);
-      assert(path.startsWith(treePackagePath.substring(0, start)));
-      if (_beginsWith(start, treePackagePath, path)) {
-        // Package *is* inside treePackage.
-        var treePackagePathLength = treePackagePath.length;
-        if (path.length == treePackagePathLength) {
-          // Has same root. Do not add package.
-          onError(ConflictException.root(package, treePackage));
-          return;
-        }
-        var treePackageUriRoot = treePackage.packageUriRoot.toString();
-        if (_beginsWith(treePackagePathLength, path, treePackageUriRoot)) {
-          // The treePackage's package root is inside package, which is inside
-          // the treePackage. This is not allowed.
-          onError(ConflictException.packageRoot(package, treePackage));
-          return;
-        }
-        _treeOf(treePackage).add(treePackagePathLength, package, onError);
-        return;
-      }
+  void add(SimplePackage newPackage, void Function(Object error) onError) {
+    var root = newPackage.root;
+    var currentMapHelper = _map[root.scheme] ??= _TrielikePackageTreeHelper();
+    if (_checkConflict(currentMapHelper, newPackage, onError)) return;
+    var segments = root.pathSegments;
+    for (var i = 0; i < segments.length - 1; i++) {
+      var path = segments[i];
+      currentMapHelper =
+          currentMapHelper.map[path] ??= _TrielikePackageTreeHelper();
+      if (_checkConflict(currentMapHelper, newPackage, onError)) return;
     }
-    packages.add(package);
+    currentMapHelper.package = newPackage;
+    _packages.add(newPackage);
+  }
+
+  bool _isMatch(String path, _TrielikePackageTreeHelper currentMapHelper,
+      List<SimplePackage> potential) {
+    if (currentMapHelper.package != null) {
+      var currentPackage = currentMapHelper.package!;
+      var currentPackageRootLength = currentPackage.root.toString().length;
+      if (path.length == currentPackageRootLength) return true;
+      var currentPackageUriRoot = currentPackage.packageUriRoot.toString();
+      // Is [file] is inside the package root of [currentPackage]?
+      if (currentPackageUriRoot.length == currentPackageRootLength ||
+          _beginsWith(currentPackageRootLength, currentPackageUriRoot, path)) {
+        return true;
+      }
+      potential.add(currentPackage);
+    }
+    return false;
   }
 
   @override
   SimplePackage? packageOf(Uri file) {
-    return findPackageOf(0, file.toString());
-  }
+    var currentMapHelper = _map[file.scheme];
+    if (currentMapHelper == null) return null;
+    var path = file.toString();
+    var potential = <SimplePackage>[];
+    if (_isMatch(path, currentMapHelper, potential)) {
+      return currentMapHelper.package;
+    }
+    var segments = file.pathSegments;
 
-  /// Finds package containing [path] in this tree.
-  ///
-  /// Returns `null` if no such package is found.
-  ///
-  /// Assumes the first [start] characters of path agrees with all
-  /// the packages at this level of the tree.
-  SimplePackage? findPackageOf(int start, String path) {
-    for (var childPackage in packages) {
-      var childPath = childPackage.root.toString();
-      if (_beginsWith(start, childPath, path)) {
-        // The [package] is inside [childPackage].
-        var childPathLength = childPath.length;
-        if (path.length == childPathLength) return childPackage;
-        var uriRoot = childPackage.packageUriRoot.toString();
-        // Is [package] is inside the URI root of [childPackage].
-        if (uriRoot.length == childPathLength ||
-            _beginsWith(childPathLength, uriRoot, path)) {
-          return childPackage;
-        }
-        return _packageChildren?[childPackage.name]
-                ?.findPackageOf(childPathLength, path) ??
-            childPackage;
+    for (var i = 0; i < segments.length - 1; i++) {
+      var segment = segments[i];
+      currentMapHelper = currentMapHelper!.map[segment];
+      if (currentMapHelper == null) break;
+      if (_isMatch(path, currentMapHelper, potential)) {
+        return currentMapHelper.package;
       }
     }
-    return null;
-  }
-
-  /// Returns the [PackageTree] of the children of [package].
-  ///
-  /// Ensures that the object is allocated if necessary.
-  MutablePackageTree _treeOf(SimplePackage package) {
-    var children = _packageChildren ??= {};
-    return children[package.name] ??= MutablePackageTree();
+    if (potential.isEmpty) return null;
+    return potential.last;
   }
 }
 
@@ -516,6 +534,8 @@
   return true;
 }
 
+enum ConflictType { SameRoots, Interleaving, InsidePackageRoot }
+
 /// Conflict between packages added to the same configuration.
 ///
 /// The [package] conflicts with [existingPackage] if it has
@@ -530,18 +550,10 @@
   final SimplePackage package;
 
   /// Whether the conflict is with the package URI root of [existingPackage].
-  final bool isPackageRootConflict;
+  final ConflictType conflictType;
 
   /// Creates a root conflict between [package] and [existingPackage].
-  ConflictException.root(this.package, this.existingPackage)
-      : isPackageRootConflict = false;
-
-  /// Creates a package root conflict between [package] and [existingPackage].
-  ConflictException.packageRoot(this.package, this.existingPackage)
-      : isPackageRootConflict = true;
-
-  /// WHether the conflict is with the root URI of [existingPackage].
-  bool get isRootConflict => !isPackageRootConflict;
+  ConflictException(this.package, this.existingPackage, this.conflictType);
 }
 
 /// Used for sorting packages by root path.
diff --git a/test/bench.dart b/test/bench.dart
new file mode 100644
index 0000000..7466431
--- /dev/null
+++ b/test/bench.dart
@@ -0,0 +1,71 @@
+// 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.
+
+import 'dart:convert';
+import 'dart:typed_data';
+
+import 'package:package_config/src/package_config_json.dart';
+
+void throwError(Object error) => throw error;
+
+void bench(final int size, final bool doPrint) {
+  var sb = StringBuffer();
+  sb.writeln('{');
+  sb.writeln('"configVersion": 2,');
+  sb.writeln('"packages": [');
+  for (var i = 0; i < size; i++) {
+    if (i != 0) {
+      sb.writeln(',');
+    }
+    sb.writeln('{');
+    sb.writeln('  "name": "p_$i",');
+    sb.writeln('  "rootUri": "file:///p_$i/",');
+    sb.writeln('  "packageUri": "lib/",');
+    sb.writeln('  "languageVersion": "2.5",');
+    sb.writeln('  "nonstandard": true');
+    sb.writeln('}');
+  }
+  sb.writeln('],');
+  sb.writeln('"generator": "pub",');
+  sb.writeln('"other": [42]');
+  sb.writeln('}');
+  var stopwatch = Stopwatch()..start();
+  var config = parsePackageConfigBytes(
+      // ignore: unnecessary_cast
+      utf8.encode(sb.toString()) as Uint8List,
+      Uri.parse('file:///tmp/.dart_tool/file.dart'),
+      throwError);
+  final int read = stopwatch.elapsedMilliseconds;
+
+  stopwatch.reset();
+  for (var i = 0; i < size; i++) {
+    if (config.packageOf(Uri.parse('file:///p_$i/lib/src/foo.dart'))!.name !=
+        'p_$i') {
+      throw "Unexpected result!";
+    }
+  }
+  final int lookup = stopwatch.elapsedMilliseconds;
+
+  if (doPrint) {
+    print('Read file with $size packages in $read ms, '
+        'looked up all packages in $lookup ms');
+  }
+}
+
+void main(List<String> args) {
+  if (args.length != 1 && args.length != 2) {
+    throw "Expects arguments: <size> <warmup iterations>?";
+  }
+  final size = int.parse(args[0]);
+  if (args.length > 1) {
+    final warmups = int.parse(args[1]);
+    print("Performing $warmups warmup iterations.");
+    for (var i = 0; i < warmups; i++) {
+      bench(10, false);
+    }
+  }
+
+  // Benchmark.
+  bench(size, true);
+}
diff --git a/test/parse_test.dart b/test/parse_test.dart
index d5c2e72..0a7770d 100644
--- a/test/parse_test.dart
+++ b/test/parse_test.dart
@@ -272,6 +272,36 @@
           Uri.parse('package:qux/diz'));
     });
 
+    test('nested packages 2', () {
+      var configBytes = utf8.encode(json.encode({
+        'configVersion': 2,
+        'packages': [
+          {'name': 'foo', 'rootUri': '/', 'packageUri': 'lib/'},
+          {'name': 'bar', 'rootUri': '/bar/', 'packageUri': 'lib/'},
+          {'name': 'baz', 'rootUri': '/bar/baz/', 'packageUri': 'lib/'},
+          {'name': 'qux', 'rootUri': '/qux/', 'packageUri': 'lib/'},
+        ]
+      }));
+      // ignore: unnecessary_cast
+      var config = parsePackageConfigBytes(configBytes as Uint8List,
+          Uri.parse('file:///tmp/.dart_tool/file.dart'), throwError);
+      expect(config.version, 2);
+      expect(
+          config.packageOf(Uri.parse('file:///lala/lala.dart'))!.name, 'foo');
+      expect(config.packageOf(Uri.parse('file:///bar/lala.dart'))!.name, 'bar');
+      expect(config.packageOf(Uri.parse('file:///bar/baz/lala.dart'))!.name,
+          'baz');
+      expect(config.packageOf(Uri.parse('file:///qux/lala.dart'))!.name, 'qux');
+      expect(config.toPackageUri(Uri.parse('file:///lib/diz')),
+          Uri.parse('package:foo/diz'));
+      expect(config.toPackageUri(Uri.parse('file:///bar/lib/diz')),
+          Uri.parse('package:bar/diz'));
+      expect(config.toPackageUri(Uri.parse('file:///bar/baz/lib/diz')),
+          Uri.parse('package:baz/diz'));
+      expect(config.toPackageUri(Uri.parse('file:///qux/lib/diz')),
+          Uri.parse('package:qux/diz'));
+    });
+
     group('invalid', () {
       void testThrows(String name, String source) {
         test(name, () {
@@ -283,6 +313,21 @@
         });
       }
 
+      void testThrowsContains(
+          String name, String source, String containsString) {
+        test(name, () {
+          dynamic exception;
+          try {
+            parsePackageConfigBytes(utf8.encode(source) as Uint8List,
+                Uri.parse('file:///tmp/.dart_tool/file.dart'), throwError);
+          } catch (e) {
+            exception = e;
+          }
+          if (exception == null) fail("Didn't get exception");
+          expect('$exception', contains(containsString));
+        });
+      }
+
       testThrows('comment', '# comment\n {$cfg,$pkgs}');
       testThrows('.packages file', 'foo:/foo\n');
       testThrows('no configVersion', '{$pkgs}');
@@ -375,19 +420,30 @@
       });
       testThrows('duplicate package name',
           '{$cfg,"packages":[{$name,$root},{$name,"rootUri":"/other/"}]}');
-      testThrows('same roots',
-          '{$cfg,"packages":[{$name,$root},{"name":"bar",$root}]}');
-      testThrows(
+      testThrowsContains(
           // The roots of foo and bar are the same.
           'same roots',
-          '{$cfg,"packages":[{$name,$root},{"name":"bar",$root}]}');
-      testThrows(
+          '{$cfg,"packages":[{$name,$root},{"name":"bar",$root}]}',
+          'the same root directory');
+      testThrowsContains(
+          // The roots of foo and bar are the same.
+          'same roots 2',
+          '{$cfg,"packages":[{$name,"rootUri":"/"},{"name":"bar","rootUri":"/"}]}',
+          'the same root directory');
+      testThrowsContains(
           // The root of bar is inside the root of foo,
           // but the package root of foo is inside the root of bar.
           'between root and lib',
           '{$cfg,"packages":['
               '{"name":"foo","rootUri":"/foo/","packageUri":"bar/lib/"},'
-              '{"name":"bar","rootUri":"/foo/bar/"},"packageUri":"baz/lib"]}');
+              '{"name":"bar","rootUri":"/foo/bar/","packageUri":"baz/lib"}]}',
+          'package root of foo is inside the root of bar');
+      testThrowsContains(
+          'root in lib',
+          '{$cfg,"packages":['
+              '{"name":"foo","rootUri":"/foo/","packageUri":"lib/"},'
+              '{"name":"bar","rootUri":"/foo/lib/bar/","packageUri":"lib"}]}',
+          'Package bar is inside the package root of package foo');
     });
   });