[
https://issues.apache.org/jira/browse/THRIFT-6195?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=18112095#comment-18112095
]
Sylwester Lachiewicz commented on THRIFT-6195:
----------------------------------------------
Pull request: https://github.com/apache/thrift/pull/3806
> 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
> Priority: Major
> Time Spent: 10m
> Remaining Estimate: 0h
>
> 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)
