feat(ext/node): embed std/node into the snapshot (#17724)

This commit moves "deno_std/node" in "ext/node" crate. The code is
transpiled and snapshotted during the build process.

During the first pass a minimal amount of work was done to create the
snapshot, a lot of code in "ext/node" depends on presence of "Deno"
global. This code will be gradually fixed in the follow up PRs to migrate
it to import relevant APIs from "internal:" modules.

Currently the code from snapshot is not used in any way, and all
Node/npm compatibility still uses code from 
"https://deno.land/std/node" (or from the location specified by 
"DENO_NODE_COMPAT_URL"). This will also be handled in a follow 
up PRs.

---------

Co-authored-by: crowlkats <crowlkats@toaxl.com>
Co-authored-by: Divy Srivastava <dj.srivastava23@gmail.com>
Co-authored-by: Yoshiya Hinosawa <stibium121@gmail.com>

1 files changed, 123 insertions, 0 deletions

diff --git a/ext/node/polyfills/internal/fixed_queue.ts b/ext/node/polyfills/internal/fixed_queue.ts
new file mode 100644
index 000000000..e6b8db70f
--- /dev/null
+++ b/ext/node/polyfills/internal/fixed_queue.ts
@@ -0,0 +1,123 @@
+// Copyright 2018-2023 the Deno authors. All rights reserved. MIT license.
+// Copyright Joyent, Inc. and other Node contributors.
+
+// Currently optimal queue size, tested on V8 6.0 - 6.6. Must be power of two.
+const kSize = 2048;
+const kMask = kSize - 1;
+
+// The FixedQueue is implemented as a singly-linked list of fixed-size
+// circular buffers. It looks something like this:
+//
+//  head                                                       tail
+//    |                                                          |
+//    v                                                          v
+// +-----------+ <-----\       +-----------+ <------\         +-----------+
+// |  [null]   |        \----- |   next    |         \------- |   next    |
+// +-----------+               +-----------+                  +-----------+
+// |   item    | <-- bottom    |   item    | <-- bottom       |  [empty]  |
+// |   item    |               |   item    |                  |  [empty]  |
+// |   item    |               |   item    |                  |  [empty]  |
+// |   item    |               |   item    |                  |  [empty]  |
+// |   item    |               |   item    |       bottom --> |   item    |
+// |   item    |               |   item    |                  |   item    |
+// |    ...    |               |    ...    |                  |    ...    |
+// |   item    |               |   item    |                  |   item    |
+// |   item    |               |   item    |                  |   item    |
+// |  [empty]  | <-- top       |   item    |                  |   item    |
+// |  [empty]  |               |   item    |                  |   item    |
+// |  [empty]  |               |  [empty]  | <-- top  top --> |  [empty]  |
+// +-----------+               +-----------+                  +-----------+
+//
+// Or, if there is only one circular buffer, it looks something
+// like either of these:
+//
+//  head   tail                                 head   tail
+//    |     |                                     |     |
+//    v     v                                     v     v
+// +-----------+                               +-----------+
+// |  [null]   |                               |  [null]   |
+// +-----------+                               +-----------+
+// |  [empty]  |                               |   item    |
+// |  [empty]  |                               |   item    |
+// |   item    | <-- bottom            top --> |  [empty]  |
+// |   item    |                               |  [empty]  |
+// |  [empty]  | <-- top            bottom --> |   item    |
+// |  [empty]  |                               |   item    |
+// +-----------+                               +-----------+
+//
+// Adding a value means moving `top` forward by one, removing means
+// moving `bottom` forward by one. After reaching the end, the queue
+// wraps around.
+//
+// When `top === bottom` the current queue is empty and when
+// `top + 1 === bottom` it's full. This wastes a single space of storage
+// but allows much quicker checks.
+
+class FixedCircularBuffer {
+  bottom: number;
+  top: number;
+  list: undefined | Array<unknown>;
+  next: FixedCircularBuffer | null;
+
+  constructor() {
+    this.bottom = 0;
+    this.top = 0;
+    this.list = new Array(kSize);
+    this.next = null;
+  }
+
+  isEmpty() {
+    return this.top === this.bottom;
+  }
+
+  isFull() {
+    return ((this.top + 1) & kMask) === this.bottom;
+  }
+
+  push(data: unknown) {
+    this.list![this.top] = data;
+    this.top = (this.top + 1) & kMask;
+  }
+
+  shift() {
+    const nextItem = this.list![this.bottom];
+    if (nextItem === undefined) {
+      return null;
+    }
+    this.list![this.bottom] = undefined;
+    this.bottom = (this.bottom + 1) & kMask;
+    return nextItem;
+  }
+}
+
+export class FixedQueue {
+  head: FixedCircularBuffer;
+  tail: FixedCircularBuffer;
+
+  constructor() {
+    this.head = this.tail = new FixedCircularBuffer();
+  }
+
+  isEmpty() {
+    return this.head.isEmpty();
+  }
+
+  push(data: unknown) {
+    if (this.head.isFull()) {
+      // Head is full: Creates a new queue, sets the old queue's `.next` to it,
+      // and sets it as the new main queue.
+      this.head = this.head.next = new FixedCircularBuffer();
+    }
+    this.head.push(data);
+  }
+
+  shift() {
+    const tail = this.tail;
+    const next = tail.shift();
+    if (tail.isEmpty() && tail.next !== null) {
+      // If there is another queue, it forms the new tail.
+      this.tail = tail.next;
+    }
+    return next;
+  }
+}