From 63dcb3802c8139ff3b87b614cb275236cecea858 Mon Sep 17 00:00:00 2001 From: Nat Goodspeed Date: Thu, 7 Mar 2024 13:46:24 -0500 Subject: 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. --- indra/newview/scripts/lua/ErrorQueue.lua | 32 +++++----- indra/newview/scripts/lua/WaitQueue.lua | 20 +++++-- indra/newview/scripts/lua/qtest.lua | 100 ++++++++++++++++++++++++++++--- indra/newview/scripts/lua/util.lua | 72 ++++++++++++++++++++++ 4 files changed, 195 insertions(+), 29 deletions(-) create mode 100644 indra/newview/scripts/lua/util.lua (limited to 'indra/newview/scripts') 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 -- cgit v1.2.3