summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorNat Goodspeed <nat@lindenlab.com>2024-03-07 13:46:24 -0500
committerNat Goodspeed <nat@lindenlab.com>2024-03-07 13:46:24 -0500
commit63dcb3802c8139ff3b87b614cb275236cecea858 (patch)
tree121c5dc7a84c3df3b8cbcdd052c5d5cdf50ddab6
parentc621fc39fc4ac25482fbc1090b8067c4187de176 (diff)
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.
-rw-r--r--indra/newview/scripts/lua/ErrorQueue.lua32
-rw-r--r--indra/newview/scripts/lua/WaitQueue.lua20
-rw-r--r--indra/newview/scripts/lua/qtest.lua100
-rw-r--r--indra/newview/scripts/lua/util.lua72
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