Sylwester Lachiewicz created THRIFT-6195:
--------------------------------------------
Summary: Go Equals is order-sensitive for set and entry-slice map
fields, so equal values compare unequal
Key: THRIFT-6195
URL: https://issues.apache.org/jira/browse/THRIFT-6195
Project: Thrift
Issue Type: Bug
Components: Go - Compiler
Affects Versions: 0.24.0
Reporter: Sylwester Lachiewicz
Thrift defines {{set}} and {{map}} as unordered collections. The Go binding
represents several of them as slices, and the generated {{Equals}} compares
slices position by position. Two values holding the same members in a
different order therefore compare unequal.
h2. Affected constructs
Three constructs share one behaviour, because they share one code path:
|| Thrift type || Go type || Introduced ||
| {{set<T>}} | {{[]T}} | long-standing |
| {{map<container, V>}} | {{[]thrift.MapEntry[K, V]}} | THRIFT-2063 |
| {{map<struct, V>}} with {{go:struct_key_entries}} | {{[]thrift.MapEntry[*K,
V]}} | THRIFT-6175 |
Measured on the current master compiler, comparing two values whose members
are identical but ordered differently:
|| Field type || Same order || Reordered ||
| {{set<Key>}} | true | false |
| {{map<list<string>, string>}} | true | false |
| {{map<Key, string>}} | true | false |
h2. Cause
{{generate_go_equals_container}} in
{{compiler/cpp/src/thrift/generate/t_go_generator.cc}} indexes both sides
positionally. The list and set branch at line 4314 shares one arm, and the
entry-slice branch does the same.
This is correct for {{list}}, which Thrift defines as ordered. It is wrong
for {{set}} and {{map}}, which it does not.
h2. Divergence from other bindings
Java compares these with {{HashSet}} and {{HashMap}} equality and Python with
{{set}} and {{dict}}, so both are order-insensitive without extra work. Go
cannot use a native map or set here, because a slice, a map, or a struct
containing either is not a valid Go map key. The slice representation is
forced by the language; the positional comparison is not.
h2. Impact
A round trip is stable, since the writer emits slice order and the reader
appends in wire order. The mismatch appears when two producers assemble the
same logical collection in different orders, for example a service whose own
iteration order shifts between restarts. A consumer comparing a newly
received message against the one it holds then sees a change that did not
happen, and reloads, invalidates a cache, or records a spurious audit diff.
h2. Proposed fix
Change {{generate_go_equals_container}} in
{{compiler/cpp/src/thrift/generate/t_go_generator.cc}}. First split the list
and set arm at line 4314: {{list}} is ordered, so its positional comparison is
already correct and must stay. Only {{set}} moves to the new logic, alongside
the entry-slice map branch.
Then compare in three tiers:
# Positional first. If it succeeds the values are equal, and this costs
exactly what the current code costs.
# If it fails and the element or key type can be a Go map key, index one side
and match against it. Linear.
# Otherwise match pairwise with a used-marker. Quadratic, and reached only by
unions, nested structs and container keys.
Tier 2 can reuse {{is_comparable_struct_key}}, added to the generator by
THRIFT-6175 for the write-side uniqueness check, extended to cover bare
scalars and enums so {{set<string>}} qualifies too.
Two details a naive implementation gets wrong. Both were found by running the
shape rather than reading it:
* *A used-marker is required.* Indexing one side by key and looking each
element up is not enough. With {{tgt}} holding {{\{a:1, a:1\}}} and {{src}}
holding {{\{a:1, b:2\}}}, the lengths match and both {{tgt}} entries find
the same {{src}} entry, so the comparison wrongly returns true. Marking each
matched index as consumed fixes it and stays linear.
* *nil elements need separate tracking*, since they cannot be dereferenced to
form a map key.
h2. Measured cost
A prototype of the emitted shape, 1000 entries, medians of five runs on an
Apple M1:
|| Strategy || ns/op || B/op ||
| Positional, current | 6089 | 0 |
| Index and match | 70900 | 37968 |
| Pairwise with used-marker | 441691 | 1024 |
| Tiered, equal and same order | 6515 | 0 |
| Tiered, equal but reordered | 62822 | 37968 |
Indexing is linear but its constant is large, so making it unconditional
would cost roughly twelve times the current comparison on the common path.
Trying positional first avoids that: values that are equal and in the same
order, which includes everything that has been through a round trip, keep the
current cost and allocate nothing. Only a reordering or a genuine difference
pays for the index.
h2. Compatibility
This changes observable behaviour. Code whose tests depend on positional
comparison of a set or an entry-slice map field would start seeing values
compare equal that previously did not. Nothing that is semantically correct
today should break, since the change only makes {{Equals}} agree with what
the Thrift type system already says these collections mean.
*This issue was created with AI assistance.*
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
