--!strict
--!nolint LocalShadow

--[[
	Given a reactive object, updates all dependent reactive objects.
	Objects are only ever updated after all of their dependencies are updated,
	are only ever updated once, and won't be updated if their dependencies are
	unchanged.
]]

local Package = script.Parent.Parent
local Types = require(Package.Types)

type Descendant = (Types.Dependent & Types.Dependency) | Types.Dependent

-- Credit: https://blog.elttob.uk/2022/11/07/sets-efficient-topological-search.html
local function updateAll(
	root: Types.Dependency
)
	local counters: {[Descendant]: number} = {}
	local flags: {[Descendant]: boolean} = {}
	local queue: {Descendant} = {}
	local queueSize = 0
	local queuePos = 1

	for object in root.dependentSet do
		queueSize += 1
		queue[queueSize] = object
		flags[object] = true
	end

	-- Pass 1: counting up
	while queuePos <= queueSize do
		local next = queue[queuePos]
		local counter = counters[next]
		counters[next] = if counter == nil then 1 else counter + 1
		if (next :: any).dependentSet ~= nil then
			local next = next :: (Types.Dependent & Types.Dependency)
			for object in next.dependentSet do
				queueSize += 1
				queue[queueSize] = object
			end
		end
		queuePos += 1
	end

	-- Pass 2: counting down + processing
	queuePos = 1
	while queuePos <= queueSize do
		local next = queue[queuePos]
		local counter = counters[next] - 1
		counters[next] = counter
		if 
			counter == 0 
			and flags[next] 
			and next.scope ~= nil 
			and next:update() 
			and (next :: any).dependentSet ~= nil 
		then
			local next = next :: (Types.Dependent & Types.Dependency)
			for object in next.dependentSet do
				flags[object] = true
			end
		end
		queuePos += 1
	end
end

return updateAll