Use a more performant utf8 decoder algorithm. (#3204)

Fixes #3163

Co-authored-by: Kitson Kelly <me@kitsonkelly.com>
Co-authored-by: Qwerasd <qwerasd205@users.noreply.github.com>

2 files changed, 152 insertions, 113 deletions

diff --git a/cli/js/decode_utf8.ts b/cli/js/decode_utf8.ts
new file mode 100644
index 000000000..69d4c8633
--- /dev/null
+++ b/cli/js/decode_utf8.ts
@@ -0,0 +1,134 @@
+// Copyright 2018-2019 the Deno authors. All rights reserved. MIT license.
+// The following code is based off:
+// https://github.com/inexorabletash/text-encoding
+//
+// Copyright (c) 2008-2009 Bjoern Hoehrmann <bjoern@hoehrmann.de>
+//
+// Permission is hereby granted, free of charge, to any person obtaining a copy
+// of this software and associated documentation files (the "Software"), to deal
+// in the Software without restriction, including without limitation the rights
+// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+// copies of the Software, and to permit persons to whom the Software is
+// furnished to do so, subject to the following conditions:
+//
+// The above copyright notice and this permission notice shall be included in
+// all copies or substantial portions of the Software.
+//
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+// SOFTWARE.
+
+// `.apply` can actually take a typed array, though the type system doesn't
+// really support it, so we have to "hack" it a bit to get past some of the
+// strict type checks.
+declare global {
+  interface CallableFunction extends Function {
+    apply<T, R>(
+      this: (this: T, ...args: number[]) => R,
+      thisArg: T,
+      args: Uint16Array
+    ): R;
+  }
+}
+
+export function decodeUtf8(
+  input: Uint8Array,
+  fatal: boolean,
+  ignoreBOM: boolean
+): string {
+  let outString = "";
+
+  // Prepare a buffer so that we don't have to do a lot of string concats, which
+  // are very slow.
+  const outBufferLength: number = Math.min(1024, input.length);
+  const outBuffer = new Uint16Array(outBufferLength);
+  let outIndex = 0;
+
+  let state = 0;
+  let codepoint = 0;
+  let type: number;
+
+  let i =
+    ignoreBOM && input[0] === 0xef && input[1] === 0xbb && input[2] === 0xbf
+      ? 3
+      : 0;
+
+  for (; i < input.length; ++i) {
+    // Encoding error handling
+    if (state === 12 || (state !== 0 && (input[i] & 0xc0) !== 0x80)) {
+      if (fatal)
+        throw new TypeError(
+          `Decoder error. Invalid byte in sequence at position ${i} in data.`
+        );
+      outBuffer[outIndex++] = 0xfffd; // Replacement character
+      if (outIndex === outBufferLength) {
+        outString += String.fromCharCode.apply(null, outBuffer);
+        outIndex = 0;
+      }
+      state = 0;
+    }
+
+    // prettier-ignore
+    type = [
+       0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
+       0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
+       0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
+       0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
+       1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,  9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,
+       7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,  7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
+       8,8,2,2,2,2,2,2,2,2,2,2,2,2,2,2,  2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
+      10,3,3,3,3,3,3,3,3,3,3,3,3,4,3,3, 11,6,6,6,5,8,8,8,8,8,8,8,8,8,8,8
+    ][input[i]];
+    codepoint =
+      state !== 0
+        ? (input[i] & 0x3f) | (codepoint << 6)
+        : (0xff >> type) & input[i];
+    // prettier-ignore
+    state = [
+       0,12,24,36,60,96,84,12,12,12,48,72, 12,12,12,12,12,12,12,12,12,12,12,12,
+      12, 0,12,12,12,12,12, 0,12, 0,12,12, 12,24,12,12,12,12,12,24,12,24,12,12,
+      12,12,12,12,12,12,12,24,12,12,12,12, 12,24,12,12,12,12,12,12,12,24,12,12,
+      12,12,12,12,12,12,12,36,12,36,12,12, 12,36,12,12,12,12,12,36,12,36,12,12,
+      12,36,12,12,12,12,12,12,12,12,12,12
+    ][state + type];
+
+    if (state !== 0) continue;
+
+    // Add codepoint to buffer (as charcodes for utf-16), and flush buffer to
+    // string if needed.
+    if (codepoint > 0xffff) {
+      outBuffer[outIndex++] = 0xd7c0 + (codepoint >> 10);
+      if (outIndex === outBufferLength) {
+        outString += String.fromCharCode.apply(null, outBuffer);
+        outIndex = 0;
+      }
+      outBuffer[outIndex++] = 0xdc00 | (codepoint & 0x3ff);
+      if (outIndex === outBufferLength) {
+        outString += String.fromCharCode.apply(null, outBuffer);
+        outIndex = 0;
+      }
+    } else {
+      outBuffer[outIndex++] = codepoint;
+      if (outIndex === outBufferLength) {
+        outString += String.fromCharCode.apply(null, outBuffer);
+        outIndex = 0;
+      }
+    }
+  }
+
+  // Add a replacement character if we ended in the middle of a sequence or
+  // encountered an invalid code at the end.
+  if (state !== 0) {
+    if (fatal) throw new TypeError(`Decoder error. Unexpected end of data.`);
+    outBuffer[outIndex++] = 0xfffd; // Replacement character
+  }
+
+  // Final flush of buffer
+  outString += String.fromCharCode.apply(null, outBuffer.subarray(0, outIndex));
+
+  return outString;
+}
diff --git a/cli/js/text_encoding.ts b/cli/js/text_encoding.ts
index 8386ff8b0..fbae96109 100644
--- a/cli/js/text_encoding.ts
+++ b/cli/js/text_encoding.ts
@@ -24,6 +24,7 @@
 // OTHER DEALINGS IN THE SOFTWARE.
 
 import * as base64 from "./base64.ts";
+import { decodeUtf8 } from "./decode_utf8.ts";
 import * as domTypes from "./dom_types.ts";
 import { DenoError, ErrorKind } from "./errors.ts";
 
@@ -54,111 +55,6 @@ function stringToCodePoints(input: string): number[] {
   return u;
 }
 
-class UTF8Decoder implements Decoder {
-  private _codePoint = 0;
-  private _bytesSeen = 0;
-  private _bytesNeeded = 0;
-  private _fatal: boolean;
-  private _ignoreBOM: boolean;
-  private _lowerBoundary = 0x80;
-  private _upperBoundary = 0xbf;
-
-  constructor(options: DecoderOptions) {
-    this._fatal = options.fatal || false;
-    this._ignoreBOM = options.ignoreBOM || false;
-  }
-
-  handler(stream: Stream, byte: number): number | null {
-    if (byte === END_OF_STREAM && this._bytesNeeded !== 0) {
-      this._bytesNeeded = 0;
-      return decoderError(this._fatal);
-    }
-
-    if (byte === END_OF_STREAM) {
-      return FINISHED;
-    }
-
-    if (this._ignoreBOM) {
-      if (
-        (this._bytesSeen === 0 && byte !== 0xef) ||
-        (this._bytesSeen === 1 && byte !== 0xbb)
-      ) {
-        this._ignoreBOM = false;
-      }
-
-      if (this._bytesSeen === 2) {
-        this._ignoreBOM = false;
-        if (byte === 0xbf) {
-          //Ignore BOM
-          this._codePoint = 0;
-          this._bytesNeeded = 0;
-          this._bytesSeen = 0;
-          return CONTINUE;
-        }
-      }
-    }
-
-    if (this._bytesNeeded === 0) {
-      if (isASCIIByte(byte)) {
-        // Single byte code point
-        return byte;
-      } else if (inRange(byte, 0xc2, 0xdf)) {
-        // Two byte code point
-        this._bytesNeeded = 1;
-        this._codePoint = byte & 0x1f;
-      } else if (inRange(byte, 0xe0, 0xef)) {
-        // Three byte code point
-        if (byte === 0xe0) {
-          this._lowerBoundary = 0xa0;
-        } else if (byte === 0xed) {
-          this._upperBoundary = 0x9f;
-        }
-        this._bytesNeeded = 2;
-        this._codePoint = byte & 0xf;
-      } else if (inRange(byte, 0xf0, 0xf4)) {
-        if (byte === 0xf0) {
-          this._lowerBoundary = 0x90;
-        } else if (byte === 0xf4) {
-          this._upperBoundary = 0x8f;
-        }
-        this._bytesNeeded = 3;
-        this._codePoint = byte & 0x7;
-      } else {
-        return decoderError(this._fatal);
-      }
-      return CONTINUE;
-    }
-
-    if (!inRange(byte, this._lowerBoundary, this._upperBoundary)) {
-      // Byte out of range, so encoding error
-      this._codePoint = 0;
-      this._bytesNeeded = 0;
-      this._bytesSeen = 0;
-      stream.prepend(byte);
-      return decoderError(this._fatal);
-    }
-
-    this._lowerBoundary = 0x80;
-    this._upperBoundary = 0xbf;
-
-    this._codePoint = (this._codePoint << 6) | (byte & 0x3f);
-
-    this._bytesSeen++;
-
-    if (this._bytesSeen !== this._bytesNeeded) {
-      return CONTINUE;
-    }
-
-    const codePoint = this._codePoint;
-
-    this._codePoint = 0;
-    this._bytesNeeded = 0;
-    this._bytesSeen = 0;
-
-    return codePoint;
-  }
-}
-
 class UTF8Encoder implements Encoder {
   handler(codePoint: number): number | number[] {
     if (codePoint === END_OF_STREAM) {
@@ -323,17 +219,19 @@ for (const key of Object.keys(encodingMap)) {
 // A map of functions that return new instances of a decoder indexed by the
 // encoding type.
 const decoders = new Map<string, (options: DecoderOptions) => Decoder>();
-decoders.set(
-  "utf-8",
-  (options: DecoderOptions): UTF8Decoder => {
-    return new UTF8Decoder(options);
-  }
-);
 
 // Single byte decoders are an array of code point lookups
 const encodingIndexes = new Map<string, number[]>();
 // prettier-ignore
-encodingIndexes.set("windows-1252", [8364,129,8218,402,8222,8230,8224,8225,710,8240,352,8249,338,141,381,143,144,8216,8217,8220,8221,8226,8211,8212,732,8482,353,8250,339,157,382,376,160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,192,193,194,195,196,197,198,199,200,201,202,203,204,205,206,207,208,209,210,211,212,213,214,215,216,217,218,219,220,221,222,223,224,225,226,227,228,229,230,231,232,233,234,235,236,237,238,239,240,241,242,243,244,245,246,247,248,249,250,251,252,253,254,255]);
+encodingIndexes.set("windows-1252", [
+  8364,129,8218,402,8222,8230,8224,8225,710,8240,352,8249,338,141,381,143,144,
+  8216,8217,8220,8221,8226,8211,8212,732,8482,353,8250,339,157,382,376,160,161,
+  162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179,180,
+  181,182,183,184,185,186,187,188,189,190,191,192,193,194,195,196,197,198,199,
+  200,201,202,203,204,205,206,207,208,209,210,211,212,213,214,215,216,217,218,
+  219,220,221,222,223,224,225,226,227,228,229,230,231,232,233,234,235,236,237,
+  238,239,240,241,242,243,244,245,246,247,248,249,250,251,252,253,254,255
+]);
 for (const [key, index] of encodingIndexes) {
   decoders.set(
     key,
@@ -431,7 +329,7 @@ export class TextDecoder {
         `The encoding label provided ('${label}') is invalid.`
       );
     }
-    if (!decoders.has(encoding)) {
+    if (!decoders.has(encoding) && encoding !== "utf-8") {
       throw new TypeError(`Internal decoder ('${encoding}') not found.`);
     }
     this._encoding = encoding;
@@ -461,6 +359,12 @@ export class TextDecoder {
       bytes = new Uint8Array(0);
     }
 
+    // For performance reasons we utilise a highly optimised decoder instead of
+    // the general decoder.
+    if (this._encoding === "utf-8") {
+      return decodeUtf8(bytes, this.fatal, this.ignoreBOM);
+    }
+
     const decoder = decoders.get(this._encoding)!({
       fatal: this.fatal,
       ignoreBOM: this.ignoreBOM
@@ -485,6 +389,7 @@ export class TextDecoder {
 
     return codePointsToString(output);
   }
+
   get [Symbol.toStringTag](): string {
     return "TextDecoder";
   }