Trie is no longer DeepEqual after v1.5.5

[brackendawson]

Trie is no longer DeepEqual after v1.5.5

[seancfoley]

I've confirmed your test.

Here is my summary at this time: IPAddress types do not guarantee that reflect.DeepEqual will work. It uses golang equality and compares absolutely everything, including things that are irrelevant and should not be compared. That is why tries and addresses have Equal methods.

The fact that in v1.5.4 you get true for reflect.DeepEqual, that is not really reliable.

I am a little curious what is the difference here between v1.5.4 and v1.5.5 that changes the result of reflect.DeepEqual, so I might try to find out.

But really, I do not consider this a bug, because DeepEqual is not expected to work in general with the types in IPAddress. That is why the methods Equal (for tries, addresses and most other types) and DeepEqual (for associative tries) is provided.

[seancfoley]

This code shows you cannot use reflect.DeepEqual with version 1.5.4 tries either:

i := ipaddr.NewIPv4AddressTrie()
j := ipaddr.NewIPv4AddressTrie()
ai := ipaddr.NewIPAddressString("192.168.1.0/24").GetAddress().ToIPv4()
aj := ipaddr.NewIPAddressString("192.168.1.0/24").GetAddress().ToIPv4()
ak := ipaddr.NewIPAddressString("192.168.2.0/24").GetAddress().ToIPv4()
i.Add(ai)
j.Add(aj)
i.Equal(j)
i.Add(ak)
i.Remove(ak)
fmt.Println("reflect.DeepEqual", reflect.DeepEqual(i, j))
fmt.Println("Equal", i.Equal(j))

reflect.DeepEqual false
Equal true

reflect.DeepEqual can return false when two tries have the same trie data, or when two addresses have the same address data. This is not uncommon in go. reflect.DeepEqual should only be used with types when it is known that it provides the desired results.

With tries in this library, there is functionality to improve lookup performance, and functionality to detect when a trie has been changed while iterating through it, and the data fields required for those features are parsed by reflect.DeepEqual, possibly changing the results. With addresses, there are other circumstances when reflect.DeepEqual will not provide the answers one might anticipate.

However, an Equal method is provided for almost all types in this library, and has much better performance anyway. With associative tries you can also use the trie DeepEqual method.

With addresses, in addition to Equal, you can convert to and from the AddressKey (or IPAddressKey or other key types) for a given address, and each of the key types are compatible with reflect.DeepEqual. So, you can put those types in other data types that you wish to compare with reflect.DeepEqual.

If you wanted to embed a trie into some other data structure that you wanted to be compatible with reflect.DeepEqual (not something I would expect to happen often), then you could iterate the trie in order, for each trie address convert to an address key, and add the key to a slice of the same size as the trie, and use the slice in the data structure.

So, I do not consider this a bug, nor is there an intent to support reflect.DeepEqual with IPAddress tries or addresses.

[seancfoley]

I have taken a look at what caused this behaviour change. The behaviour was changed when I added a sync.Pool for root nodes for performance reasons to improve trie performance. I don't know if it is possible to make that work with reflect.DeepEqual - the generic types make the pool more difficult to share. Even if I could, there is also a changetracker type in there that might also cause reflect.DeepEqual to not work on occasion.