Don't use regular expressions in Loader. This is based on https://codereview.chromium.org/1325053002. It also avoids redundant parsing where possible. Closes dart-lang/yaml#12 R=rnystrom@google.com Review URL: https://codereview.chromium.org//1329763002 .
diff --git a/pkgs/yaml/CHANGELOG.md b/pkgs/yaml/CHANGELOG.md index 5dcd749..6359d97 100644 --- a/pkgs/yaml/CHANGELOG.md +++ b/pkgs/yaml/CHANGELOG.md
@@ -1,3 +1,7 @@ +## 2.1.4 + +* Substantially improve performance. + ## 2.1.3 * Add a hint that a colon might be missing when a mapping value is found in the
diff --git a/pkgs/yaml/lib/src/loader.dart b/pkgs/yaml/lib/src/loader.dart index 0792957..5336310 100644 --- a/pkgs/yaml/lib/src/loader.dart +++ b/pkgs/yaml/lib/src/loader.dart
@@ -4,6 +4,7 @@ library yaml.loader; +import 'package:charcode/ascii.dart'; import 'package:source_span/source_span.dart'; import 'equality.dart'; @@ -13,31 +14,6 @@ import 'yaml_exception.dart'; import 'yaml_node.dart'; -/// Matches YAML null. -final _nullRegExp = new RegExp(r"^(null|Null|NULL|~|)$"); - -/// Matches a YAML bool. -final _boolRegExp = new RegExp(r"^(?:(true|True|TRUE)|(false|False|FALSE))$"); - -/// Matches a YAML decimal integer like `+1234`. -final _decimalIntRegExp = new RegExp(r"^[-+]?[0-9]+$"); - -/// Matches a YAML octal integer like `0o123`. -final _octalIntRegExp = new RegExp(r"^0o([0-7]+)$"); - -/// Matches a YAML hexidecimal integer like `0x123abc`. -final _hexIntRegExp = new RegExp(r"^0x[0-9a-fA-F]+$"); - -/// Matches a YAML floating point number like `12.34+e56`. -final _floatRegExp = new RegExp( - r"^[-+]?(\.[0-9]+|[0-9]+(\.[0-9]*)?)([eE][-+]?[0-9]+)?$"); - -/// Matches YAML infinity. -final _infinityRegExp = new RegExp(r"^([+-]?)\.(inf|Inf|INF)$"); - -/// Matches YAML NaN. -final _nanRegExp = new RegExp(r"^\.(nan|NaN|NAN)$"); - /// A loader that reads [Event]s emitted by a [Parser] and emits /// [YamlDocument]s. /// @@ -133,15 +109,11 @@ YamlNode _loadScalar(ScalarEvent scalar) { var node; if (scalar.tag == "!") { - node = _parseString(scalar); + node = new YamlScalar.internal(scalar.value, scalar); } else if (scalar.tag != null) { node = _parseByTag(scalar); } else { - node = _parseNull(scalar); - if (node == null) node = _parseBool(scalar); - if (node == null) node = _parseInt(scalar); - if (node == null) node = _parseFloat(scalar); - if (node == null) node = _parseString(scalar); + node = _parseScalar(scalar); } _registerAnchor(scalar.anchor, node); @@ -197,82 +169,191 @@ /// Parses a scalar according to its tag name. YamlScalar _parseByTag(ScalarEvent scalar) { switch (scalar.tag) { - case "tag:yaml.org,2002:null": return _parseNull(scalar); - case "tag:yaml.org,2002:bool": return _parseBool(scalar); - case "tag:yaml.org,2002:int": return _parseInt(scalar); - case "tag:yaml.org,2002:float": return _parseFloat(scalar); - case "tag:yaml.org,2002:str": return _parseString(scalar); + case "tag:yaml.org,2002:null": + var result = _parseNull(scalar); + if (result != null) return result; + throw new YamlException("Invalid null scalar.", scalar.span); + case "tag:yaml.org,2002:bool": + var result = _parseBool(scalar); + if (result != null) return result; + throw new YamlException("Invalid bool scalar.", scalar.span); + case "tag:yaml.org,2002:int": + var result = _parseNumber(scalar, allowFloat: false); + if (result != null) return result; + throw new YamlException("Invalid int scalar.", scalar.span); + case "tag:yaml.org,2002:float": + var result = _parseNumber(scalar, allowInt: false); + if (result != null) return result; + throw new YamlException("Invalid float scalar.", scalar.span); + case "tag:yaml.org,2002:str": + return new YamlScalar.internal(scalar.value, scalar); + default: + throw new YamlException('Undefined tag: ${scalar.tag}.', scalar.span); } - throw new YamlException('Undefined tag: ${scalar.tag}.', scalar.span); } - /// Parses a null scalar. + /// Parses [scalar], which may be one of several types. + YamlScalar _parseScalar(ScalarEvent scalar) => + _tryParseScalar(scalar) ?? new YamlScalar.internal(scalar.value, scalar); + + /// Tries to parse [scalar]. + /// + /// If parsing fails, this returns `null`, indicating that the scalar should + /// be parsed as a string. + YamlScalar _tryParseScalar(ScalarEvent scalar) { + // Quickly check for the empty string, which means null. + var length = scalar.value.length; + if (length == 0) return new YamlScalar.internal(null, scalar); + + // Dispatch on the first character. + var firstChar = scalar.value.codeUnitAt(0); + switch (firstChar) { + case $dot: + case $plus: + case $minus: + return _parseNumber(scalar); + case $n: + case $N: + return length == 4 ? _parseNull(scalar) : null; + case $t: + case $T: + return length == 4 ? _parseBool(scalar) : null; + case $f: + case $F: + return length == 5 ? _parseBool(scalar) : null; + case $tilde: + return length == 1 ? new YamlScalar.internal(null, scalar) : null; + default: + if (firstChar >= $0 && firstChar <= $9) return _parseNumber(scalar); + return null; + } + } + + /// Parse a null scalar. + /// + /// Returns a Dart `null` if parsing fails. YamlScalar _parseNull(ScalarEvent scalar) { - // TODO(nweiz): add ScalarStyle and implicit metadata to the scalars. - if (_nullRegExp.hasMatch(scalar.value)) { - return new YamlScalar.internal(null, scalar.span, scalar.style); - } else { - return null; + switch (scalar.value) { + case "": + case "null": + case "Null": + case "NULL": + case "~": + return new YamlScalar.internal(null, scalar); + default: + return null; } } - /// Parses a boolean scalar. + /// Parse a boolean scalar. + /// + /// Returns `null` if parsing fails. YamlScalar _parseBool(ScalarEvent scalar) { - var match = _boolRegExp.firstMatch(scalar.value); - if (match == null) return null; - return new YamlScalar.internal( - match.group(1) != null, scalar.span, scalar.style); + switch (scalar.value) { + case "true": + case "True": + case "TRUE": + return new YamlScalar.internal(true, scalar); + case "false": + case "False": + case "FALSE": + return new YamlScalar.internal(false, scalar); + default: + return null; + } } - /// Parses an integer scalar. - YamlScalar _parseInt(ScalarEvent scalar) { - var match = _decimalIntRegExp.firstMatch(scalar.value); - if (match != null) { - return new YamlScalar.internal( - int.parse(match.group(0)), scalar.span, scalar.style); + /// Parses a numeric scalar. + /// + /// Returns `null` if parsing fails. + YamlNode _parseNumber(ScalarEvent scalar, {bool allowInt: true, + bool allowFloat: true}) { + var value = _parseNumberValue(scalar.value, + allowInt: allowInt, allowFloat: allowFloat); + return value == null ? null : new YamlScalar.internal(value, scalar); + } + + /// Parses the value of a number. + /// + /// Returns the number if it's parsed successfully, or `null` if it's not. + num _parseNumberValue(String contents, {bool allowInt: true, + bool allowFloat: true}) { + assert(allowInt || allowFloat); + + var firstChar = contents.codeUnitAt(0); + var length = contents.length; + + // Quick check for single digit integers. + if (allowInt && length == 1) { + var value = firstChar - $0; + return value >= 0 && value <= 9 ? value : null; } - match = _octalIntRegExp.firstMatch(scalar.value); - if (match != null) { - var n = int.parse(match.group(1), radix: 8); - return new YamlScalar.internal(n, scalar.span, scalar.style); + var secondChar = contents.codeUnitAt(1); + + // Hexadecimal or octal integers. + if (allowInt && firstChar == $0) { + // int.parse supports 0x natively. + if (secondChar == $x) return int.parse(contents, onError: (_) => null); + + if (secondChar == $o) { + var afterRadix = contents.substring(2); + return int.parse(afterRadix, radix: 8, onError: (_) => null); + } } - match = _hexIntRegExp.firstMatch(scalar.value); - if (match != null) { - return new YamlScalar.internal( - int.parse(match.group(0)), scalar.span, scalar.style); + // Int or float starting with a digit or a +/- sign. + if ((firstChar >= $0 && firstChar <= $9) || + ((firstChar == $plus || firstChar == $minus) && + secondChar >= $0 && secondChar <= $9)) { + // Try to parse an int or, failing that, a double. + var result = null; + if (allowInt) { + // Pass "radix: 10" explicitly to ensure that "-0x10", which is valid + // Dart but invalid YAML, doesn't get parsed. + result = int.parse(contents, radix: 10, onError: (_) => null); + } + + if (allowFloat) result ??= double.parse(contents, (_) => null); + return result; + } + + if (!allowFloat) return null; + + // Now the only possibility is to parse a float starting with a dot or a + // sign and a dot, or the signed/unsigned infinity values and not-a-numbers. + if ((firstChar == $dot && secondChar >= $0 && secondChar <= $9) || + (firstChar == $minus || firstChar == $plus) && secondChar == $dot) { + // Starting with a . and a number or a sign followed by a dot. + if (length == 5) { + switch (contents) { + case "+.inf": + case "+.Inf": + case "+.INF": + return double.INFINITY; + case "-.inf": + case "-.Inf": + case "-.INF": + return -double.INFINITY; + } + } + + return double.parse(contents, (_) => null); + } + + if (length == 4 && firstChar == $dot) { + switch (contents) { + case ".inf": + case ".Inf": + case ".INF": + return double.INFINITY; + case ".nan": + case ".NaN": + case ".NAN": + return double.NAN; + } } return null; } - - /// Parses a floating-point scalar. - YamlScalar _parseFloat(ScalarEvent scalar) { - var match = _floatRegExp.firstMatch(scalar.value); - if (match != null) { - // YAML allows floats of the form "0.", but Dart does not. Fix up those - // floats by removing the trailing dot. - var matchStr = match.group(0).replaceAll(new RegExp(r"\.$"), ""); - return new YamlScalar.internal( - double.parse(matchStr), scalar.span, scalar.style); - } - - match = _infinityRegExp.firstMatch(scalar.value); - if (match != null) { - var value = match.group(1) == "-" ? -double.INFINITY : double.INFINITY; - return new YamlScalar.internal(value, scalar.span, scalar.style); - } - - match = _nanRegExp.firstMatch(scalar.value); - if (match != null) { - return new YamlScalar.internal(double.NAN, scalar.span, scalar.style); - } - - return null; - } - - /// Parses a string scalar. - YamlScalar _parseString(ScalarEvent scalar) => - new YamlScalar.internal(scalar.value, scalar.span, scalar.style); }
diff --git a/pkgs/yaml/lib/src/yaml_node.dart b/pkgs/yaml/lib/src/yaml_node.dart index 027bc1b..d4961bb 100644 --- a/pkgs/yaml/lib/src/yaml_node.dart +++ b/pkgs/yaml/lib/src/yaml_node.dart
@@ -9,6 +9,7 @@ import 'package:collection/collection.dart'; import 'package:source_span/source_span.dart'; +import 'event.dart'; import 'null_span.dart'; import 'style.dart'; import 'yaml_node_wrapper.dart'; @@ -163,7 +164,14 @@ } /// Users of the library should not use this constructor. - YamlScalar.internal(this.value, SourceSpan span, this.style) { + YamlScalar.internal(this.value, ScalarEvent scalar) + : style = scalar.style { + _span = span; + } + + /// Users of the library should not use this constructor. + YamlScalar.internalWithSpan(this.value, SourceSpan span) + : style = ScalarStyle.ANY { _span = span; }
diff --git a/pkgs/yaml/lib/src/yaml_node_wrapper.dart b/pkgs/yaml/lib/src/yaml_node_wrapper.dart index be96ba4..d7146c4 100644 --- a/pkgs/yaml/lib/src/yaml_node_wrapper.dart +++ b/pkgs/yaml/lib/src/yaml_node_wrapper.dart
@@ -59,7 +59,7 @@ final SourceSpan _span; Iterable get keys => _dartMap.keys.map((key) => - new YamlScalar.internal(key, _span, ScalarStyle.ANY)); + new YamlScalar.internalWithSpan(key, _span)); _YamlMapNodes(this._dartMap, this._span); @@ -151,5 +151,5 @@ YamlNode _nodeForValue(value, SourceSpan span) { if (value is Map) return new YamlMapWrapper._(value, span); if (value is List) return new YamlListWrapper._(value, span); - return new YamlScalar.internal(value, span, ScalarStyle.ANY); + return new YamlScalar.internalWithSpan(value, span); }
diff --git a/pkgs/yaml/lib/yaml.dart b/pkgs/yaml/lib/yaml.dart index 9af329a..aa120ef 100644 --- a/pkgs/yaml/lib/yaml.dart +++ b/pkgs/yaml/lib/yaml.dart
@@ -53,7 +53,7 @@ var document = loader.load(); if (document == null) { return new YamlDocument.internal( - new YamlScalar.internal(null, loader.span, ScalarStyle.ANY), + new YamlScalar.internalWithSpan(null, loader.span), loader.span, null, const []); }
diff --git a/pkgs/yaml/pubspec.yaml b/pkgs/yaml/pubspec.yaml index 618f82b..f6a5b1e 100644 --- a/pkgs/yaml/pubspec.yaml +++ b/pkgs/yaml/pubspec.yaml
@@ -1,5 +1,5 @@ name: yaml -version: 2.1.4-dev +version: 2.1.4 author: "Dart Team <misc@dartlang.org>" homepage: https://github.com/dart-lang/yaml description: A parser for YAML. @@ -12,4 +12,4 @@ dev_dependencies: test: ">=0.12.0 <0.13.0" environment: - sdk: '>=1.8.0 <2.0.0' + sdk: '>=1.12.0 <2.0.0'