Fusion
Fusion copied to clipboard
dphfox
Deep equality checking
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.
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,
})
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.
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.
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!
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.
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.
Hmm, what if tables as State received a separate class, which has dedicated methods for handling the mutability and recalculations
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 })
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.
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).
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
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.
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
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.
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
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
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
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
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)
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.
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.
From my. conversations with others, there seems to be little appetite for this. Closing in favour of #291.