Deep equality checking

[dphfox]

Currently, Fusion uses referential equality - essentially, just ==. However, this can lead to a lot of footguns, like this:

local array = {1, 2, 3, 4, 5}
local state = State(array)

table.insert(array, 6)
state:set(array) -- doesn't update, because the reference hasn't changed

local state = State({ message = "Hello" })

local computed = Computed(function()
    return state:get().message
end)

state:set({ message = "Hello" }) -- updates `computed` even though the message is identical, because the reference changed

Should Fusion also support deep equality checking? This would almost certainly have a performance impact, though I haven't prototyped and benchmarked anything yet.

[boatbomber]

As long as it is not the default behavior- I do not want my code to pay a performance penalty for this.

Perhaps the State() constructor could take in multiple arguments, the second being a dictionary of settings? (Dict so we can potentially add more settings in the future without being a breaking change)

local foo = State(stateArray, {
    DeepEquality = true,
})

[dphfox]

As long as it is not the default behavior- I do not want my code to pay a performance penalty for this.

Perhaps the State() constructor could take in multiple arguments, the second being a dictionary of settings? (Dict so we can potentially add more settings in the future without being a breaking change)

local foo = State(stateArray, {
    DeepEquality = true,
})

Perhaps - though I think we should benchmark what performance impact this would have before trying to work around the performance impact :p

Keep in mind this wouldn't affect everything - it'd only affect tables which are not referentially equal.

[Dionysusnu]

This should be enabled by default, with maybe an opt-out. It's so trivially easy to footgun with it disabled, as shown in the example. Fusion's simplicity is what makes it powerful. Having to think ages about specific internal workings to find a subtle state update bug does not line up with that simplicity.

[dphfox]

Thought I'd drop in to give a quick update on this.

It turns out there's a bit of ambiguity over what counts as 'deeply equal' - I was discussing this with one of my friends a while back, and it's actually a more complex and nuanced problem than it appears on the surface, specifically if you want to allow for cycles and table indices and other interesting things.

This 'pureEquals' function should in theory do what we want (thanks to AxisAngles for the help):

local function pair(pairings, a, b)
	pairings[a] = b
	pairings[b] = a
end

local function unpair(pairings, a, b)
	pairings[a] = nil
	pairings[b] = nil
end

local function pairable(pairings, a, b)
	return pairings[a] == nil or pairings[b] == nil or pairings[a] == b
end

local function next2(a, b, i, j)
	local nexti = next(a, i)
	local nextj = next(b, j)
	if i == nil and j == nil then
		if nexti == nil or nextj == nil then
			return nil, nil
		else
			return nexti, nextj
		end
	elseif nextj ~= nil then
		return i, nextj
	elseif nexti ~= nil then -- loop back to the beginning
		return nexti, next(b)
	else
		return nil, nil
	end
end


local function iCopy(a)
	local A = {}
	for i, v in next, a do
		A[i] = true
	end
	return A
end

local pureEquals
local pureEqualsTable

-- we can improve the efficiency substantially
function pureEqualsTable(pairings, unpairedA, unpairedB, a, b, i, j, func, ...)
	local nexti, nextj = next2(a, b, i, j)

	if nexti == nil or nextj == nil then
		if next(unpairedA) or next(unpairedB) then
			return false
		end
		-- passed the pairity check, now resume previous routine
		if not func then
			return true
		end
		return func(pairings, ...)
	end

	if unpairedA[nexti] and unpairedB[nextj] then
		--assume pairing
		unpairedA[nexti] = nil
		unpairedB[nextj] = nil

		local success = pureEquals(pairings,
			nexti, nextj,
			pureEquals, a[nexti], b[nextj],
			pureEqualsTable, unpairedA, unpairedB, a, b, nexti, nextj, -- should skip to the following i
			func, ...)

		--unpair cause we're done testing
		unpairedA[nexti] = true
		unpairedB[nextj] = true

		if success then
			return true
		end
	end

	--these were not pairable, so now we're going to continue on to the next potential i j pair
	return pureEqualsTable(pairings, unpairedA, unpairedB, a, b, nexti, nextj, func, ...)
end

function pureEquals(pairings, a, b, func, ...)
	-- if a and b are already paired, then yah, they're paired
	if pairings[a] == b then
		if not func then
			return true
		end
		return func(pairings, ...) -- resume
	elseif pairings[a] ~= nil or pairings[b] ~= nil then
		-- if a or b is already paired, then definite failure
		return false
	end

	local typeA = type(a)
	local typeB = type(b)
	if typeA ~= "table" or typeB ~= "table" then
		if a ~= b then
			return false
		end
		if not func then -- definite success
			return true
		end
		return func(pairings, ...) -- resume
	end

	-- at this point a and b are tables, and not paired to each other

	--presume pairity
	pair(pairings, a, b)

	-- now try to match each element in the table to each other element
	local success = pureEqualsTable(pairings,
		iCopy(a), iCopy(b), a, b, nil, nil,
		func, ...)

	-- undo everything
	unpair(pairings, a, b)
	return success
end

return function(a, b)
	return pureEquals({}, a, b)
end

...but, as I'm sure you've noticed, that is a lot of engineering. I did write a substantially shorter function which solves a subset of the problem reasonably well, but which isn't a 'true' deep equals:

local function deepEquals_impl(a, b, seen)
	if a == b then
		return true
	elseif type(a) ~= "table" or type(b) ~= "table" then
		return false
	end

	-- we know `a` and `b` are tables which are not referentially equal
	-- time to do a deep check

	if seen[a] == nil then
		seen[a] = {}
	end

	if seen[b] == nil then
		seen[b] = {}
	end

	-- if we've seen `a` and `b` before, don't descend into them, because it's a
	-- cycle
	if seen[a][b] then
		return true
	end

	seen[a][b] = true
	seen[b][a] = true

	for key, valueA in pairs(a) do
		local valueB = b[key]
		if not deepEquals_impl(valueA, valueB, seen) then
			return false
		end
	end

	for key, valueB in pairs(b) do
		local valueA = a[key]
		if not deepEquals_impl(valueA, valueB, seen) then
			return false
		end
	end

	return true
end

local function deepEquals(a, b)
	return deepEquals_impl(a, b, {})
end

return deepEquals

I'm not sure whether to go with this or not - I'm currently still playing around with various ideas. I might end up taking table state in Fusion in a different direction entirely.

tl;dr tables are hard!

[Dionysusnu]

I've thought of a different solution. Most of the footguns are from mutating tables. Should Fusion go the Rodux way of making data immutable? This is easy now with table.freeze.

[dphfox]

That's also what I'm considering right now - we would be breaking the mental model of state objects as variables a bit, but perhaps that's a net positive.

[Dionysusnu]

Hmm, what if tables as State received a separate class, which has dedicated methods for handling the mutability and recalculations

[Zyrakia]

How about something like this for dictionaries, not sure about arrays, but for dictionaries this could work. Not sure if this is actually a viable solution, but I thought I'd bring it up. This function basically turns a table into a table of values recursively, and includes a set function which can be used to update part of the table.

function TableValue(initialTable)
	local tableValue = {}

	for k, v in pairs(initialTable) do
		if (typeof(v) == "table") then
			-- Need to implement a check to make sure it's not an array
			tableValue[k] = TableValue(v)
		else
			tableValue[k] = Value(v)
		end
	end

	tableValue.set = function(partial, force)
		for key, value in pairs(partial) do
			local holder = tableValue[key]
                        if holder == nil then
                                continue
                        end

			if (xtypeof(holder) == 'State') then
				holder:set(value, force)
			else 
				holder.set(value, force)
			end
		end
	end

	return tableValue
end

local myTable = TableValue({ a = 5, b = { c = 5 } })

print("initial a:", myTable.a:get())
Observer(myTable.a):onChange(function()
	print("a changed to:", myTable.a:get())
end)

-- This will never update a, so the observer will not fire
myTable.set({ b = { c = 10 })

-- This will update a, but will never update b, or b.c
myTable.set({ a = 0.5 })

[dphfox]

That's certainly a possibility, but it's worth noting there that your solution doesn't work if the table contains a set key.
It would be better to externalise the behaviour of setting these table values:

local function makeValues(x)
    if typeof(x) ~= "table" then
        return Value(x)
    else
        local tbl = {}
        for key, value in pairs(x) do
            tbl[key] = makeValues(value)
        end
        return tbl
    end
end

local function syncValues(destination, source)
    if xtypeof(destination) == "State" and destination.kind == "Value" then
        destination:set(source)
    elseif typeof(destination) == "table" then
        for key, sub in pairs(destination) do
            syncValues(sub, source[key])
        end
    else
        error("Expected a Value object or structure of Value objects")
    end
end

local structure = makeValues({
    foo = 2,
    bar = {
        baz = 5,
        frob = 7
    }
})

print(structure.foo:get()) --> 2

syncValues(structure, {
    foo = 6,
    bar = {
        baz = 2,
        frob = 1
    }
})

print(structure.foo:get()) --> 6

At that point, this looks like a procedural implementation of state stores - which is certainly another avenue we could pursue. I think this is a very interesting angle to approach from, decomposing values storing tables into tables storing values.

[Zyrakia]

I enjoy this because it removes the need for deep equality checking since all the values are just boiled into small Value objects which can do their own inexpensive referential check only when needed, and it also let's you connect to the change of a single value without an extra computed. Not sure if this would ever be the end all solution for most people, but I definitely run into situations where this is incredibly useful (theme/settings/data tables).

[dphfox]

For sure - I think this is a much preferable solution where its applicable.

[jcphlux]

So just ran into this issue. There might be a simple "maybe hacky" way to solve this.
using HttpService do a JSONEncode of the 2 values in the isSimilar function. Maybe add a few quick checks before the encoding.
Note: I am not sure of the cost of this.

local function isSimilar(a: any, b: any): boolean
	if typeof(a) == "table" then
		if a == nil and b == nil then
			return true
		elseif typeof(b) ~= "table" or (a == nil and b ~= nil) or (a ~= nil and b == nil) or #a ~= #b then
			return false
		end

		return HttpService:JSONEncode(a) == HttpService:JSONEncode(b)
	else
		return a == b
	end
end

[krypt102]

Doesn't seem like a bad solution, we could do a benchmark with JSONEncode

[jcphlux]

Also, this would not work 100% for a mixed table but from reading the API doc Roblox while allows it does not like mixed tables.

[boatbomber]

This solution will not work. You can't JSONEncode Roblox datatypes, meaning that using this would make Fusion unable to have states hold tables with Vector3, Color3, Instances, etc

[jcphlux]

Might not be perfect but currently if you have a table in a state it always updates the state even if you pass it the same value.

[jcphlux]

This solution will not work. You can't JSONEncode Roblox datatypes, meaning that using this would make Fusion unable to have states hold tables with Vector3, Color3, Instances, etc

It would be nice if they documented this in there API docs under JSONEncode and JSONDecode

[krypt102]

Oh yeah forgot about that edge case, bit annoying unfortunately.

[jcphlux]

ok update to check if RB datatypes are in the encode and fallback to og table handling.

local function isSimilar(a: any, b: any): boolean
	if typeof(a) == "table" then
		if a == nil and b == nil then
			return true
		elseif typeof(b) ~= "table" or (a == nil and b ~= nil) or (a ~= nil and b == nil) or #a ~= #b then
			return false
		end
		local jsonA, jsonB = HttpService:JSONEncode(a), HttpService:JSONEncode(b)
		if jsonA == jsonB and (jsonA:match(":null") or jsonB:match(":null")) then
			-- fallback to og return
			return false
		end
		return jsonA == jsonB
	else
		return a == b
	end
end

[jcphlux]

Non hacky way of handling.

local function _subset(a: table, b: table): boolean
	if a == nil and b == nil then
		return true
	elseif (a == nil and b ~= nil) or (a ~= nil and b == nil) or #a ~= #b then
		return false
	end
	for key, value in a do
		if typeof(value) == "table" then
			if not isSimilar(b[key], value) then
				return false
			end
		else
			if b[key] ~= value then
				return false
			end
		end
	end
	return true
end

local function isSimilar(a: any, b: any): boolean
	if typeof(a) == "table" then
		if typeof(b) ~= "table" then
			return false
		end
		return _subset(a, b) and _subset(b, a)
	else
		return a == b
	end
end

[jcphlux]

This is version would check State Objects in the tables or if for some reason the state object value was a state object.

local class = {}
class.__index = class

function class.tblIsSimilar(a: table, b: table): boolean
	if #a ~= #b then
		return false
	end
	for key, value in a do
		if not class.isSimilar(b[key], value) then
			return false
		end
	end
	return true
end

function class.isSimilar(a: any, b: any): boolean
	if a == nil and b == nil then
		return true
	elseif typeof(a) ~= typeof(b) then
		return false
	elseif a.type == "State" and b.type == "State" then
		return class.isSimilar(a:get(), b:get())
	elseif typeof(a) == "table" and typeof(b) == "table" then
		return class.tblIsSimilar(a, b) and class.tblIsSimilar(b, a)
	else
		return a == b
	end
end

return class.isSimilar

[jcphlux]

if you are good with this last version I can do a pull request.

[krypt102]

I wouldn't create a PR just yet only because this issue is marked as status: needs design. PR's are generally meant for approved features (a mistake I made twice so just helpin out :D)

[jcphlux]

I wouldn't create a PR just yet only because this issue is marked as status: needs design. PR's are generally meant for approved features (a mistake I made twice so just helpin out :D)

no worries. Even if what I wrote just helps some with the design choices I am glad to help.

[ala89]

The correct way to solve this problem should be to let the user pass its own equality function (on both Values and Computeds). A framework should not be the one deciding how to perform equality checks. I have a draft of this already.

[dphfox]

From my. conversations with others, there seems to be little appetite for this. Closing in favour of #291.