timers: implement timers in javascript

4 files changed, 216 insertions, 92 deletions

diff --git a/js/deno.ts b/js/deno.ts
index 03f3d1a89..91f7ae1af 100644
--- a/js/deno.ts
+++ b/js/deno.ts
@@ -19,5 +19,4 @@ export { libdeno } from "./libdeno";
 export { arch, platform } from "./platform";
 export { trace } from "./trace";
 export { truncateSync, truncate } from "./truncate";
-export { setGlobalTimeout } from "./timers";
 export const args: string[] = [];
diff --git a/js/dispatch.ts b/js/dispatch.ts
index 9257be767..56d280ff9 100644
--- a/js/dispatch.ts
+++ b/js/dispatch.ts
@@ -9,19 +9,31 @@ import { maybePushTrace } from "./trace";
 let nextCmdId = 0;
 const promiseTable = new Map<number, util.Resolvable<fbs.Base>>();
 
+let fireTimers: () => void;
+
+export function setFireTimersCallback(fn: () => void) {
+  fireTimers = fn;
+}
+
 export function handleAsyncMsgFromRust(ui8: Uint8Array) {
-  const bb = new flatbuffers.ByteBuffer(ui8);
-  const base = fbs.Base.getRootAsBase(bb);
-  const cmdId = base.cmdId();
-  const promise = promiseTable.get(cmdId);
-  util.assert(promise != null, `Expecting promise in table. ${cmdId}`);
-  promiseTable.delete(cmdId);
-  const err = errors.maybeError(base);
-  if (err != null) {
-    promise!.reject(err);
-  } else {
-    promise!.resolve(base);
+  // If a the buffer is empty, recv() on the native side timed out and we
+  // did not receive a message.
+  if (ui8.length) {
+    const bb = new flatbuffers.ByteBuffer(ui8);
+    const base = fbs.Base.getRootAsBase(bb);
+    const cmdId = base.cmdId();
+    const promise = promiseTable.get(cmdId);
+    util.assert(promise != null, `Expecting promise in table. ${cmdId}`);
+    promiseTable.delete(cmdId);
+    const err = errors.maybeError(base);
+    if (err != null) {
+      promise!.reject(err);
+    } else {
+      promise!.resolve(base);
+    }
   }
+  // Fire timers that have become runnable.
+  fireTimers();
 }
 
 // @internal
diff --git a/js/timers.ts b/js/timers.ts
index 03badfd46..79aefb645 100644
--- a/js/timers.ts
+++ b/js/timers.ts
@@ -1,107 +1,225 @@
 // Copyright 2018 the Deno authors. All rights reserved. MIT license.
 import { assert } from "./util";
-import * as util from "./util";
 import * as fbs from "gen/msg_generated";
 import { flatbuffers } from "flatbuffers";
-import { sendSync, sendAsync } from "./dispatch";
+import { sendSync, setFireTimersCallback } from "./dispatch";
 
-let nextTimerId = 1;
-
-// tslint:disable-next-line:no-any
-export type TimerCallback = (...args: any[]) => void;
+// Tell the dispatcher which function it should call to fire timers that are
+// due. This is done using a callback because circular imports are disallowed.
+setFireTimersCallback(fireTimers);
 
 interface Timer {
   id: number;
-  cb: TimerCallback;
-  interval: boolean;
-  // tslint:disable-next-line:no-any
-  args: any[];
-  delay: number; // milliseconds
+  callback: () => void;
+  delay: number;
+  due: number;
+  repeat: boolean;
+  scheduled: boolean;
+}
+
+// We'll subtract EPOCH every time we retrieve the time with Date.now(). This
+// ensures that absolute time values stay below UINT32_MAX - 2, which is the
+// maximum object key that EcmaScript considers "numerical". After running for
+// about a month, this is no longer true, and Deno explodes.
+// TODO(piscisaureus): fix that ^.
+const EPOCH = Date.now();
+const APOCALYPS = 2 ** 32 - 2;
+
+let globalTimeoutDue: number | null = null;
+
+let nextTimerId = 1;
+const idMap = new Map<number, Timer>();
+const dueMap: { [due: number]: Timer[] } = Object.create(null);
+
+function getTime() {
+  // TODO: use a monotonic clock.
+  const now = Date.now() - EPOCH;
+  assert(now >= 0 && now < APOCALYPS);
+  return now;
 }
 
-export function setGlobalTimeout(timeout: number) {
+function setGlobalTimeout(due: number | null, now: number) {
+  // Since JS and Rust don't use the same clock, pass the time to rust as a
+  // relative time value. On the Rust side we'll turn that into an absolute
+  // value again.
+  // Note that a negative time-out value stops the global timer.
+  let timeout;
+  if (due === null) {
+    timeout = -1;
+  } else {
+    timeout = due - now;
+    assert(timeout >= 0);
+  }
+  // Send message to the backend.
   const builder = new flatbuffers.Builder();
   fbs.SetTimeout.startSetTimeout(builder);
   fbs.SetTimeout.addTimeout(builder, timeout);
   const msg = fbs.SetTimeout.endSetTimeout(builder);
   const res = sendSync(builder, fbs.Any.SetTimeout, msg);
   assert(res == null);
+  // Remember when when the global timer will fire.
+  globalTimeoutDue = due;
 }
 
-function startTimer(
-  id: number,
-  cb: TimerCallback,
-  delay: number,
-  interval: boolean,
-  // tslint:disable-next-line:no-any
-  args: any[]
-): void {
-  const timer: Timer = {
-    id,
-    interval,
-    delay,
-    args,
-    cb
-  };
-  util.log("timers.ts startTimer");
-
-  // Send TimerStart message
-  const builder = new flatbuffers.Builder();
-  fbs.TimerStart.startTimerStart(builder);
-  fbs.TimerStart.addId(builder, timer.id);
-  fbs.TimerStart.addDelay(builder, timer.delay);
-  const msg = fbs.TimerStart.endTimerStart(builder);
+function schedule(timer: Timer, now: number) {
+  assert(!timer.scheduled);
+  assert(now <= timer.due);
+  // Find or create the list of timers that will fire at point-in-time `due`.
+  let list = dueMap[timer.due];
+  if (list === undefined) {
+    list = dueMap[timer.due] = [];
+  }
+  // Append the newly scheduled timer to the list and mark it as scheduled.
+  list.push(timer);
+  timer.scheduled = true;
+  // If the new timer is scheduled to fire before any timer that existed before,
+  // update the global timeout to reflect this.
+  if (globalTimeoutDue === null || globalTimeoutDue > timer.due) {
+    setGlobalTimeout(timer.due, now);
+  }
+}
 
-  sendAsync(builder, fbs.Any.TimerStart, msg).then(
-    baseRes => {
-      assert(fbs.Any.TimerReady === baseRes!.msgType());
-      const msg = new fbs.TimerReady();
-      assert(baseRes!.msg(msg) != null);
-      assert(msg.id() === timer.id);
-      if (msg.canceled()) {
-        util.log("timer canceled message");
-      } else {
-        cb(...args);
-        if (interval) {
-          // TODO Faking setInterval with setTimeout.
-          // We need a new timer implementation, this is just a stopgap.
-          startTimer(id, cb, delay, true, args);
-        }
+function unschedule(timer: Timer) {
+  if (!timer.scheduled) {
+    return;
+  }
+  // Find the list of timers that will fire at point-in-time `due`.
+  const list = dueMap[timer.due];
+  if (list.length === 1) {
+    // Time timer is the only one in the list. Remove the entire list.
+    assert(list[0] === timer);
+    delete dueMap[timer.due];
+    // If the unscheduled timer was 'next up', find when the next timer that
+    // still exists is due, and update the global alarm accordingly.
+    if (timer.due === globalTimeoutDue) {
+      let nextTimerDue: number | null = null;
+      for (const key in dueMap) {
+        nextTimerDue = Number(key);
+        break;
       }
-    },
-    error => {
-      throw error;
+      setGlobalTimeout(nextTimerDue, getTime());
     }
-  );
+  } else {
+    // Multiple timers that are due at the same point in time.
+    // Remove this timer from the list.
+    const index = list.indexOf(timer);
+    assert(index > 0);
+    list.splice(index, 1);
+  }
 }
 
-export function setTimeout(
-  cb: TimerCallback,
+function fire(timer: Timer) {
+  // If the timer isn't found in the ID map, that means it has been cancelled
+  // between the timer firing and the promise callback (this function).
+  if (!idMap.has(timer.id)) {
+    return;
+  }
+  // Reschedule the timer if it is a repeating one, otherwise drop it.
+  if (!timer.repeat) {
+    // One-shot timer: remove the timer from this id-to-timer map.
+    idMap.delete(timer.id);
+  } else {
+    // Interval timer: compute when timer was supposed to fire next.
+    // However make sure to never schedule the next interval in the past.
+    const now = getTime();
+    timer.due = Math.max(now, timer.due + timer.delay);
+    schedule(timer, now);
+  }
+  // Call the user callback. Intermediate assignment is to avoid leaking `this`
+  // to it, while also keeping the stack trace neat when it shows up in there.
+  const callback = timer.callback;
+  callback();
+}
+
+function fireTimers() {
+  const now = getTime();
+  // Bail out if we're not expecting the global timer to fire (yet).
+  if (globalTimeoutDue === null || now < globalTimeoutDue) {
+    return;
+  }
+  // After firing the timers that are due now, this will hold the due time of
+  // the first timer that hasn't fired yet.
+  let nextTimerDue: number | null = null;
+  // Walk over the keys of the 'due' map. Since dueMap is actually a regular
+  // object and its keys are numerical and smaller than UINT32_MAX - 2,
+  // keys are iterated in ascending order.
+  for (const key in dueMap) {
+    // Convert the object key (a string) to a number.
+    const due = Number(key);
+    // Break out of the loop if the next timer isn't due to fire yet.
+    if (Number(due) > now) {
+      nextTimerDue = due;
+      break;
+    }
+    // Get the list of timers that have this due time, then drop it.
+    const list = dueMap[key];
+    delete dueMap[key];
+    // Fire all the timers in the list.
+    for (const timer of list) {
+      // With the list dropped, the timer is no longer scheduled.
+      timer.scheduled = false;
+      // Place the callback on the microtask queue.
+      Promise.resolve(timer).then(fire);
+    }
+  }
+  // Update the global alarm to go off when the first-up timer that hasn't fired
+  // yet is due.
+  setGlobalTimeout(nextTimerDue, now);
+}
+
+function setTimer<Args extends Array<unknown>>(
+  cb: (...args: Args) => void,
   delay: number,
-  // tslint:disable-next-line:no-any
-  ...args: any[]
+  args: Args,
+  repeat: boolean
 ): number {
-  const id = nextTimerId++;
-  startTimer(id, cb, delay, false, args);
-  return id;
+  // If any `args` were provided (which is uncommon), bind them to the callback.
+  const callback: () => void = args.length === 0 ? cb : cb.bind(null, ...args);
+  // In the browser, the delay value must be coercable to an integer between 0
+  // and INT32_MAX. Any other value will cause the timer to fire immediately.
+  // We emulate this behavior.
+  const now = getTime();
+  delay = Math.max(0, delay | 0);
+  // Create a new, unscheduled timer object.
+  const timer = {
+    id: nextTimerId++,
+    callback,
+    args,
+    delay,
+    due: now + delay,
+    repeat,
+    scheduled: false
+  };
+  // Register the timer's existence in the id-to-timer map.
+  idMap.set(timer.id, timer);
+  // Schedule the timer in the due table.
+  schedule(timer, now);
+  return timer.id;
 }
 
-export function setInterval(
-  cb: TimerCallback,
+export function setTimeout<Args extends Array<unknown>>(
+  cb: (...args: Args) => void,
   delay: number,
-  // tslint:disable-next-line:no-any
-  ...args: any[]
+  ...args: Args
 ): number {
-  const id = nextTimerId++;
-  startTimer(id, cb, delay, true, args);
-  return id;
+  return setTimer(cb, delay, args, false);
 }
 
-export function clearTimer(id: number) {
-  const builder = new flatbuffers.Builder();
-  fbs.TimerClear.startTimerClear(builder);
-  fbs.TimerClear.addId(builder, id);
-  const msg = fbs.TimerClear.endTimerClear(builder);
-  const res = sendSync(builder, fbs.Any.TimerClear, msg);
-  assert(res == null);
+export function setInterval<Args extends Array<unknown>>(
+  cb: (...args: Args) => void,
+  delay: number,
+  ...args: Args
+): number {
+  return setTimer(cb, delay, args, true);
+}
+
+export function clearTimer(id: number): void {
+  const timer = idMap.get(id);
+  if (timer === undefined) {
+    // Timer doesn't exist any more or never existed. This is not an error.
+    return;
+  }
+  // Unschedule the timer if it is currently scheduled, and forget about it.
+  unschedule(timer);
+  idMap.delete(timer.id);
 }
diff --git a/js/timers_test.ts b/js/timers_test.ts
index e5fe2d478..af172e976 100644
--- a/js/timers_test.ts
+++ b/js/timers_test.ts
@@ -1,5 +1,4 @@
 import { test, assertEqual } from "./test_util.ts";
-import { setGlobalTimeout } from "deno";
 
 function deferred() {
   let resolve;
@@ -96,7 +95,3 @@ test(async function intervalCancelInvalidSilentFail() {
   // Should silently fail (no panic)
   clearInterval(2147483647);
 });
-
-test(async function SetGlobalTimeoutSmoke() {
-  setGlobalTimeout(50);
-});