From ea8fb54c124b03812c02231ee0363da41fa58f8b Mon Sep 17 00:00:00 2001
From: Nathaniel Wesley Filardo <nwf@cs.jhu.edu>
Date: Sat, 29 Jul 2017 15:32:45 -0400
Subject: [PATCH] tq bugfixes (and API change)

- not all lapsed time should be credited to the head node
- needs to reset the time base (_tst) in all cases
- always return the object for cancellation
- defend against time going backwards (just in case)

While here, rework to simplify, simplify API, and add comments
---
 tq/tq.lua | 58 ++++++++++++++++++++++++++++++++++++-------------------
 1 file changed, 38 insertions(+), 20 deletions(-)

diff --git a/tq/tq.lua b/tq/tq.lua
index c9ef8ba..55c5e35 100644
--- a/tq/tq.lua
+++ b/tq/tq.lua
@@ -1,15 +1,15 @@
 -- DEPENDS: tmr [only by default]
-local fire, doarm
-function fire(self)
-  local cbt = {}
+local function fire(self)
   local entryt = self:now()
-  local lapsed = (entryt - self._tst)/1000
+  local lapsed = (entryt > self._tst) and (entryt - self._tst)/1000 or 0
   if #self._q > 0 and lapsed < self._q[1].t then
     -- premature fire?  adjust and rearm
     self._q[1].t = self._q[1].t - lapsed
-    doarm(self, self._q[1].t)
+    self._tst = entryt
+    self:arm(self._q[1].t, entryt)
     return
   end
+  local cbt = {}
   while #self._q > 0 and self._q[1].t <= lapsed do
     -- collect events in the past into cbt
     local cbs = table.remove(self._q,1)
@@ -19,28 +19,44 @@ function fire(self)
   if #self._q > 0 then
     -- leftover events: credit excess lapsed time and rearm
     self._q[1].t = self._q[1].t - lapsed
-    doarm(self, self._q[1].t)
+    self._tst = entryt
+    self:arm(self._q[1].t, entryt)
   end
   -- run all collected callbacks, having adjusted queue
   local k, cbs, v
   for k,cbs in ipairs(cbt) do for k,v in ipairs(cbs) do v() end end
 end
-function doarm(self,when) self:arm(function() fire(self) end, when); self._tst = self:now() end
 local function queue(self,when,what,...)
-  if #self._q > 0 then
-    local lapsed = (self:now() - self._tst)/1000
-    self._q[1].t = self._q[1].t - lapsed
-  end
-  local ix = 0; local tleft = when
-  while (ix < #self._q) do
-    if (tleft < self._q[ix+1].t) then break end
+  local entryt = self:now()
+  local lapsed = (entryt > self._tst) and (entryt - self._tst)/1000 or 0
+  self._tst = entryt
+   -- scan upwards for insertion position
+  local ix = 0
+  local tleft = when
+  while ix < #self._q do
+    local qi = self._q[ix+1]
+    -- credit lapsed time, if any
+    if     (lapsed > qi.t) then lapsed = lapsed - qi.t ; qi.t = 0 -- entirely covers
+    elseif (lapsed > 0   ) then qi.t = qi.t - lapsed ; lapsed = 0 -- partially covers
+    end
+    -- see if this bucket extends far enough in time
+    -- (now that we have subtracted any lapsed time)
+    if (tleft < qi.t) then break end
     ix = ix + 1; tleft = tleft - self._q[ix].t
   end
+  -- invariant: lapsed == 0
+  -- create queue element
   local warg = {...}; local nwarg = select('#',...)
-  local wfn = function () return what(unpack(warg,1,nwarg)) end
-  if ix == 0 then doarm(self,when)
-  elseif tleft == 0 then table.insert(self._q[ix],wfn); return
+  local wfn = function () what(unpack(warg,1,nwarg)) end
+  if ix == 0 then
+    -- we're going at the head of the queue, so set the new firing time
+    self:arm(when, entryt)
+  elseif tleft == 0 then
+    -- we're going in an existing bucket that isn't the first
+    table.insert(self._q[ix],wfn)
+    return wfn
   end
+  -- create a new bucket
   table.insert(self._q,ix+1,{["t"] = tleft, [1] = wfn})
   if ix+1 < #self._q then
     self._q[ix+2].t = self._q[ix+2].t - tleft
@@ -53,9 +69,11 @@ local function dequeue(self,what)
     if w == what then table.remove(v,k) end
   end end
 end
-local function defl_arm(self,fn,t) tmr.alarm(self.tmr, t, tmr.ALARM_SINGLE, fn) end
-local function defl_now(_) return tmr.now() end
+local function defl_arm(self,t)
+  tmr.alarm(self.tmr, t, tmr.ALARM_SINGLE, function() self:fire() end)
+end
 return function(tmrix) return {
   _q = {}, _tst = 0,
-  ["arm"] = defl_arm, ["now"] = defl_now, ["tmr"] = tmrix, ["queue"] = queue, ["dequeue"] = dequeue
+  ["fire"] = fire, ["arm"] = defl_arm, ["now"] = tmr and tmr.now,
+  ["tmr"] = tmrix, ["queue"] = queue, ["dequeue"] = dequeue
 } end
-- 
2.50.1