SequentialQueue class for serializing events using Callable

Description

"SequentialQueue is a streamlined class that encapsulates an Array of Callable objects, and provides specific methods for grabbing and running items in the array. While only the public functions are meant to be interacted with, `get_queue()` provides direct access to the internal array itself in case other modifications to the array are needed.\r\n\r\n[Disclaimer: Author self-rates his experience with gdscript\/game development as a beginner]\r\n\r\nThis utility class was created for a turn-based RPG combat system, where I wanted to collect a series of effects to occur in non-synchronous series, and run them at a later time, and was otherwise having trouble with signals and order of operations.\r\n\r\nFor instance, you might want to queue messages to display in a panel script:\r\n\r\n```\r\nvar message_queue : SequentialQueue = SequentialQueue.new()\r\n\r\nfunc _process(delta: float) -> void:\r\n\twhile queue_has_messages and not message_is_playing :\r\n\t\t_pop_message()\r\n\r\nfunc _pop_message() -> void :\r\n\tmessage_queue.call_next()\r\n\r\nfunc queue_message(source_message: String) -> void :\r\n\tmessage_queue.add_item(_display_message.bind(source_message))\r\n\tmessage_queued.emit()\r\n```\r\n\r\n(signals and logic variables omitted for brevity)\r\n\r\nIn this case, whenever `queue_message()` has been called, it adds `_display_message(source_message)` to the queue, and `_process()` will thus only pop it off when the conditions are satisfied.\r\n\r\nSimilar operations could be used to queue up animations of different objects to occur one after another."

Main code

class_name SequentialQueue extends Resource

var _queue : Array = []

func get_queue() -> Array :
	return _queue

func clear() -> void :
	_queue = []

func add_item(queue_item: Callable) -> void :
	_queue.push_back(queue_item)

func call_all() -> void :
	if _queue.is_empty() :
		print_debug(self, " was empty, returning without calling anything")
		return
	elif !_queue.is_empty() :
		await call_next()
	if !_queue.is_empty() :
		print_debug(self, " has more items, calling again recursively")
		await call_all()


func call_next() -> void :
	if _queue.is_empty() :
		print_debug("queue empty")
		return
	var queue_item = _queue.pop_front()
	await queue_item.call()

func erase_next() -> void :
	_queue.pop_front()
	
func is_empty() -> bool :
	if _queue.is_empty() : return true
	else : return false

func is_not_empty() -> bool :
	if _queue.is_empty() : return false
	else : return true

Comments

Report

"I'm a little verbose\/explicit as a beginner, so I'll blame that for the first question. :)\r\n\r\nSo, if I'm remembering correctly with the `call_all` method, is that if we set it up as a loop of the current contents of the array, I worry that the array can change on the fly outside of this method, and we won't call everything, or we'll go out of bounds? E.g. other concurrent routines can add\/subtract to the array while we're processing the current calls. Generally frowned upon. If adding, you won't exhaust the current contents. If we remove objects, we can go out of bounds. Even if we `await` the `call_all` from our main calling script, other things with access to the queue could also manipulate the queue. By only stepping through whatever the next item is, we can hopefully avoid that (and this is also why checking for an empty array happens first, even if we've just checked). This results in more `is_empty` checks but is there for runtime safety.\r\n\r\nYou could certainly try it that way instead, and maybe the solution is adding a separate non-recursive method that only queues up the current contents, as long as you're very careful about freezing the contents (maybe locking out the `erase_next` method while `call_all` is running?). Now that I'm thinking about it, `erase_next` ought to check for an empty array as well.\r\n\r\nPersonally, I am generally using this queue to store the same \"kind\" of routines, and the additions\/calls on it are coming from one script (e.g. my battle UI scene), only accessed locally, and I'll set up different queues for different kinds of routines (one for battle messages that display for a short period of time, one for animations I want to call one after another, handling player\/enemy turn order, etc.), so I'm avoiding the issues I'm bringing up here. I'm not sure what the effects of `call_all` being used in multiple places concurrently would be, which I *think* it will resolve OK, but there could be moments where something is popped by one iteration after `is_empty` is checked by the other?\r\n\r\nThanks for bringing up this concern, it's given me more to think about!"

"I was about to talk about the concurrency and reentrancy issues in my initial comment. In fact, concurrency is a concern if you intend to share the access of the `SequentialQueue` between threads. As long as you assume that it will not be the case, you're safe.\r\n\r\nHowever, reentrancy is another problem : What if one of the callable in your queue calls back the `call_all` function, or even add a new entry to the queue ? Using your recursive solution, one might think we're out of trouble. But recursivity, especially for list browsing, is usually not the best idea (old coders like me would yell \"_No !!! Stack Overflow Ahead !!!_\").\r\n\r\nSo, how ? Just iterate the array ?\r\n\tOne could be tempted to guard the access to the queue (that's concurrency protection), however, it will lead to a deadlock (the `callable` will be locked, which will lock the iteration itself ...). BUT, by using `try_lock` instead, you could just ignore the invocation (_i'm already calling everybody, move on !_). But this won't fix some upcoming issue (especially if your routine assume that everything has been called after a `call_all` invocation ... which lead to another concerns : code design. Why would a `callable` invoke `call_all` to begin with ?)\r\n\r\n(_Disclaimer : I've not looked at the Array implementation of Godot, especially the iteration_)\r\n\r\nNow, concerning calls to `add_item` while a `call_all` is occurring (and perhaps `call_next`, but it's very more unlikely).\r\nWith the use of a `Mutex` (or some weaker protection as a flag, but I won't recommend it), you could _route_ entries added using `add_item` to another queue (a lobby of some sort). When invoking the `call_next` or `call_all`, this lobby queue will be appended to `_queue` and emptied it to wait other entries. Thus, no issues. You could even make a loop in `call_all` that carry on while the lobby is not empty ! "

Description

Main code

Comments

Table of contents

Compatibility

Tags