Finish WaitQueue, ErrorQueue; add util.count(), join(); extend qtest.

For WaitQueue, nail down the mechanism for declaring a subclass and for
calling a base-class method from a subclass override. Break out new
_wake_waiters() method from Enqueue(): we need to do the same from close(), in
case there are waiting consumers. Also, in Lua, 0 is not false.

Instead of bundling a normal/error flag with every queued value, make
ErrorQueue overload its _closed attribute. Once you call ErrorQueue:Error(),
every subsequent Dequeue() call by any consumer will re-raise the same error.

util.count() literally counts entries in a table, since #t is documented to be
unreliable. (If you create a list with 5 entries and delete the middle one, #t
might return 2 or it might return 5, but it won't return 4.)

util.join() fixes a curious omission from Luau's string library: like Python's
str.join(), it concatenates all the strings from a list with an optional
separator. We assume that incrementally building a list of strings and then
doing a single allocation for the desired result string is cheaper than
reallocating each of a sequence of partial concatenated results.

Add qtest test that posts individual items to a WaitQueue, waking waiting
consumers to retrieve the next available result. Add test proving that calling
ErrorQueue:Error() propagates the error to all consumers.

4 files changed, 195 insertions, 29 deletions

diff --git a/indra/newview/scripts/lua/ErrorQueue.lua b/indra/newview/scripts/lua/ErrorQueue.lua
index e6279f8411..db7022661e 100644
--- a/indra/newview/scripts/lua/ErrorQueue.lua
+++ b/indra/newview/scripts/lua/ErrorQueue.lua
@@ -1,32 +1,30 @@
 -- ErrorQueue isa WaitQueue with the added feature that a producer can push an
--- error through the queue. When that error is dequeued, the consumer will
--- throw that error.
+-- error through the queue. Once that error is dequeued, every consumer will
+-- raise that error.
 
 local WaitQueue = require('WaitQueue')
 
 ErrorQueue = WaitQueue:new()
 
-function ErrorQueue:Enqueue(value)
-    -- normal value, not error
-    WaitQueue:Enqueue({ false, value })
-end
-
 function ErrorQueue:Error(message)
-    -- flag this entry as an error message
-    WaitQueue:Enqueue({ true, message })
+    -- Setting Error() is a marker, like closing the queue. Once we reach the
+    -- error, every subsequent Dequeue() call will raise the same error.
+    self._closed = message
+    self:_wake_waiters()
 end
 
 function ErrorQueue:Dequeue()
-    local errflag, value = table.unpack(WaitQueue:Dequeue())
-    if errflag == nil then
-        -- queue has been closed, tell caller
-        return nil
+    local value = WaitQueue.Dequeue(self)
+    if value ~= nil then
+        -- queue not yet closed, show caller
+        return value
     end
-    if errflag then
-        -- 'value' is a message pushed by Error()
-        error(value)
+    if self._closed == true then
+        -- WaitQueue:close() sets true: queue has only been closed, tell caller
+        return nil
     end
-    return value
+    -- self._closed is a message set by Error()
+    error(self._closed)
 end
 
 return ErrorQueue
diff --git a/indra/newview/scripts/lua/WaitQueue.lua b/indra/newview/scripts/lua/WaitQueue.lua
index 05d2056085..6a64c3dd67 100644
--- a/indra/newview/scripts/lua/WaitQueue.lua
+++ b/indra/newview/scripts/lua/WaitQueue.lua
@@ -7,8 +7,10 @@ local Queue = require('Queue')
 WaitQueue = Queue:new()
 
 function WaitQueue:new()
-    local obj = setmetatable(Queue:new(), self)
+    local obj = Queue:new()
+    setmetatable(obj, self)
     self.__index = self
+
     obj._waiters = {}
     obj._closed = false
     return obj
@@ -18,7 +20,14 @@ function WaitQueue:Enqueue(value)
     if self._closed then
         error("can't Enqueue() on closed Queue")
     end
-    Queue:Enqueue(value)
+    -- can't simply call Queue:Enqueue(value)! That calls the method on the
+    -- Queue class definition, instead of calling Queue:Enqueue() on self.
+    -- Hand-expand the Queue:Enqueue() syntactic sugar.
+    Queue.Enqueue(self, value)
+    self:_wake_waiters()
+end
+
+function WaitQueue:_wake_waiters()
     -- WaitQueue is designed to support multi-producer, multi-consumer use
     -- cases. With multiple consumers, if more than one is trying to
     -- Dequeue() from an empty WaitQueue, we'll have multiple waiters.
@@ -27,7 +36,7 @@ function WaitQueue:Enqueue(value)
     -- callers. But since resuming that caller might entail either Enqueue()
     -- or Dequeue() calls, recheck every time around to see if we must resume
     -- another waiting coroutine.
-    while not self:IsEmpty() and #self._waiters do
+    while not self:IsEmpty() and #self._waiters > 0 do
         -- pop the oldest waiting coroutine instead of the most recent, for
         -- more-or-less round robin fairness
         local waiter = table.remove(self._waiters, 1)
@@ -58,11 +67,14 @@ function WaitQueue:Dequeue()
         coroutine.yield()
     end
     -- here we're sure this queue isn't empty
-    return Queue:Dequeue()
+    return Queue.Dequeue(self)
 end
 
 function WaitQueue:close()
     self._closed = true
+    -- close() is like Enqueueing an end marker. If there are waiting
+    -- consumers, give them a chance to see we're closed.
+    self:_wake_waiters()
 end
 
 return WaitQueue
diff --git a/indra/newview/scripts/lua/qtest.lua b/indra/newview/scripts/lua/qtest.lua
index 16a54be0d1..12e425b7b2 100644
--- a/indra/newview/scripts/lua/qtest.lua
+++ b/indra/newview/scripts/lua/qtest.lua
@@ -3,7 +3,11 @@
 Queue = require('Queue')
 WaitQueue = require('WaitQueue')
 ErrorQueue = require('ErrorQueue')
+util = require('util')
 
+inspect = require('inspect')
+
+-- ------------------ Queue variables are instance-specific ------------------
 q1 = Queue:new()
 q2 = Queue:new()
 
@@ -15,33 +19,113 @@ assert(q1:Dequeue() == 17)
 assert(q1:Dequeue() == nil)
 assert(q2:Dequeue() == nil)
 
+-- ----------------------------- test WaitQueue ------------------------------
 q1 = WaitQueue:new()
-
-inspect = require('inspect')
-print(inspect(q1))
-
 q2 = WaitQueue:new()
 result = {}
-
 values = { 1, 1, 2, 3, 5, 8, 13, 21 }
+
 for i, value in pairs(values) do
     q1:Enqueue(value)
 end
+-- close() while not empty tests that queue drains before reporting done
+q1:close()
 
+-- ensure that WaitQueue instance variables are in fact independent
+assert(q2:IsEmpty())
+
+-- consumer() coroutine to pull from the passed q until closed
 function consumer(desc, q)
-    print('consumer(', desc, ') start')
+    print(string.format('consumer(%s) start', desc))
     local value = q:Dequeue()
     while value ~= nil do
+        print(string.format('consumer(%s) got %q', desc, value))
         table.insert(result, value)
         value = q:Dequeue()
     end
-    print('consumer(', desc, ') done')
+    print(string.format('consumer(%s) done', desc))
 end
 
+-- run two consumers
 coa = coroutine.create(consumer)
 cob = coroutine.create(consumer)
+-- Since consumer() doesn't yield while it can still retrieve values,
+-- consumer(a) will dequeue all values from q1 and return when done.
 coroutine.resume(coa, 'a', q1)
+-- consumer(b) will wake up to find the queue empty and closed.
 coroutine.resume(cob, 'b', q1)
+coroutine.close(coa)
+coroutine.close(cob)
+
+print('values:', inspect(values))
+print('result:', inspect(result))
+
+assert(util.equal(values, result))
+
+-- try incrementally enqueueing values
+q3 = WaitQueue:new()
+result = {}
+values = { 'This', 'is', 'a', 'test', 'script' }
+
+coros = {}
+for _, name in {'a', 'b'} do
+    local coro = coroutine.create(consumer)
+    table.insert(coros, coro)
+    -- Resuming both coroutines should leave them both waiting for a queue item.
+    coroutine.resume(coro, name, q3)
+end
+
+for _, s in pairs(values) do
+    print(string.format('Enqueue(%q)', s))
+    q3:Enqueue(s)
+end
+q3:close()
+
+function joinall(coros)
+    local running
+    local errors = 0
+    repeat
+        running = false
+        for i, coro in pairs(coros) do
+            if coroutine.status(coro) == 'suspended' then
+                running = true
+                local ok, message = coroutine.resume(coro)
+                if not ok then
+                    print('*** ' .. message)
+                    errors += 1
+                end
+                if coroutine.status(coro) == 'dead' then
+                    coros[i] = nil
+                end
+            end
+        end
+    until not running
+    return errors
+end
+
+joinall(coros)
+
+print(string.format('%q', util.join(result, ' ')))
+assert(util.equal(values, result))
+
+-- ----------------------------- test ErrorQueue -----------------------------
+q4 = ErrorQueue:new()
+result = {}
+values = { 'This', 'is', 'a', 'test', 'script' }
+
+coros = {}
+for _, name in {'a', 'b'} do
+    local coro = coroutine.create(consumer)
+    table.insert(coros, coro)
+    -- Resuming both coroutines should leave them both waiting for a queue item.
+    coroutine.resume(coro, name, q4)
+end
+
+for i = 1, 4 do
+    print(string.format('Enqueue(%q)', values[i]))
+    q4:Enqueue(values[i])
+end
+q4:Error('something went wrong')
 
-assert(result == values)
+assert(joinall(coros) == 2)
 
diff --git a/indra/newview/scripts/lua/util.lua b/indra/newview/scripts/lua/util.lua
new file mode 100644
index 0000000000..bb8d492d12
--- /dev/null
+++ b/indra/newview/scripts/lua/util.lua
@@ -0,0 +1,72 @@
+-- utility functions, in alpha order
+
+local util = {}
+
+-- cheap test whether table t is empty
+function util.empty(t)
+    for _ in pairs(t) do
+        return false
+    end
+    return true
+end
+
+-- reliable count of the number of entries in table t
+-- (since #t is unreliable)
+function util.count(t)
+    local count = 0
+    for _ in pairs(t) do
+        count += 1
+    end
+    return count
+end
+
+-- recursive table equality
+function util.equal(t1, t2)
+    if not (type(t1) == 'table' and type(t2) == 'table') then
+        return t1 == t2
+    end
+    -- both t1 and t2 are tables: get modifiable copy of t2
+    local temp = table.clone(t2)
+    for k, v in pairs(t1) do
+        -- if any key in t1 doesn't have same value in t2, not equal
+        if not util.equal(v, temp[k]) then
+            return false
+        end
+        -- temp[k] == t1[k], delete temp[k]
+        temp[k] = nil
+    end
+    -- All keys in t1 have equal values in t2; t2 == t1 if there are no extra keys in t2
+    return util.empty(temp)
+end
+
+-- Concatentate the strings in the passed list, return the composite string.
+-- For iterative string building, the theory is that building a list with
+-- table.insert() and then using join() to allocate the full-size result
+-- string once should be more efficient than reallocating an intermediate
+-- string for every partial concatenation.
+function util.join(list, sep)
+    -- This succinct implementation assumes that string.format() precomputes
+    -- the required size of its output buffer before populating it. We don't
+    -- know that. Moreover, this implementation predates our sep argument.
+--  return string.format(string.rep('%s', #list), table.unpack(list))
+
+    -- this implementation makes it explicit
+    local sep = sep or ''
+    local size = if util.empty(list) then 0 else -#sep
+    for _, s in pairs(list) do
+        size += #sep + #s
+    end
+    local result = buffer.create(size)
+    size = 0
+    for i, s in pairs(list) do
+        if i > 1 then
+            buffer.writestring(result, size, sep)
+            size += #sep
+        end
+        buffer.writestring(result, size, s)
+        size += #s
+    end
+    return buffer.tostring(result)
+end
+
+return util