Skip to content

Commit c110cbb

Browse files
kevmoosuryaKommana2662
authored andcommitted
Use int.oneBitCount in PersistentHashMap and scope 53-bit caps to JS (flutter#195005)
Replace the hand-rolled 32-bit SWAR `_bitCount` helper with Dart 3.13's `int.oneBitCount`, and narrow the `2^53` integer bounds in `SliverMultiBoxAdaptorElement` and `OverlayPortalController` from `kIsWeb` to `kIsWeb && !kIsWasm` (with `TODO`s to adopt `double.maxSafeInteger` / `double.minSafeInteger` on Dart 3.15). Fixes flutter#189716 ## Pre-launch Checklist - [x] I read the [Contributor Guide] and followed the process outlined there for submitting PRs. - [x] I read the [AI contribution guidelines] and understand my responsibilities, or I am not using AI tools. - [x] I read the [Tree Hygiene] wiki page, which explains my responsibilities. - [x] I read and followed the [Flutter Style Guide], including [Features we expect every widget to implement]. - [x] I signed the [CLA]. - [x] I listed at least one issue that this PR fixes in the description above. - [x] I updated/added relevant in-code documentation (doc comments with `///`). - [x] If this PR introduces a new feature or capability, I created and linked a website documentation issue or PR in [flutter/website] (or verified none is needed). - [x] I added new tests to check the change I am making, or this PR is [test-exempt]. - [x] I followed the [breaking change policy] and added [Data Driven Fixes] where supported. - [x] All existing and new tests are passing. <!-- Links --> [Contributor Guide]: https://github.com/flutter/flutter/blob/main/docs/contributing/Tree-hygiene.md#overview [AI contribution guidelines]: https://github.com/flutter/flutter/blob/main/CONTRIBUTING.ai.md [Tree Hygiene]: https://github.com/flutter/flutter/blob/main/docs/contributing/Tree-hygiene.md [test-exempt]: https://github.com/flutter/flutter/blob/main/docs/contributing/Tree-hygiene.md#tests [Flutter Style Guide]: https://github.com/flutter/flutter/blob/main/docs/contributing/Style-guide-for-Flutter-repo.md [Features we expect every widget to implement]: https://github.com/flutter/flutter/blob/main/docs/contributing/Style-guide-for-Flutter-repo.md#features-we-expect-every-widget-to-implement [CLA]: https://cla.developers.google.com/ [flutter/website]: https://github.com/flutter/website [breaking change policy]: https://github.com/flutter/flutter/blob/main/docs/contributing/Tree-hygiene.md#handling-breaking-changes [Data Driven Fixes]: https://github.com/flutter/flutter/blob/main/docs/contributing/Data-driven-Fixes.md
1 parent 4c51fff commit c110cbb

5 files changed

Lines changed: 77 additions & 21 deletions

File tree

‎packages/flutter/lib/src/foundation/persistent_hash_map.dart‎

Lines changed: 2 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -191,7 +191,7 @@ class _CompressedNode extends _TrieNode {
191191
);
192192
} else {
193193
// Adding new key/value mapping.
194-
final int occupiedCount = _bitCount(occupiedIndices);
194+
final int occupiedCount = occupiedIndices.oneBitCount;
195195
if (occupiedCount >= 16) {
196196
// Too many occupied: inflate compressed node into full node and
197197
// update descendant at the corresponding index.
@@ -271,7 +271,7 @@ class _CompressedNode extends _TrieNode {
271271
@pragma('vm:prefer-inline')
272272
@pragma('wasm:prefer-inline')
273273
int _compressedIndex(int bit) {
274-
return _bitCount(occupiedIndices & (bit - 1));
274+
return (occupiedIndices & (bit - 1)).oneBitCount;
275275
}
276276

277277
static _TrieNode _resolveCollision(
@@ -359,22 +359,6 @@ class _HashCollisionNode extends _TrieNode {
359359
}
360360
}
361361

362-
/// Returns number of bits set in a 32bit integer.
363-
///
364-
/// dart2js safe because we work with 32bit integers.
365-
@pragma('dart2js:tryInline')
366-
@pragma('vm:prefer-inline')
367-
@pragma('wasm:prefer-inline')
368-
int _bitCount(int n) {
369-
assert((n & 0xFFFFFFFF) == n);
370-
n = n - ((n >> 1) & 0x55555555);
371-
n = (n & 0x33333333) + ((n >>> 2) & 0x33333333);
372-
n = (n + (n >> 4)) & 0x0F0F0F0F;
373-
n = n + (n >> 8);
374-
n = n + (n >> 16);
375-
return n & 0x0000003F;
376-
}
377-
378362
/// Create a copy of the given array.
379363
///
380364
/// Caveat: do not replace with List.of or similar methods. They are

‎packages/flutter/lib/src/widgets/overlay.dart‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1704,7 +1704,8 @@ class OverlayPortalController {
17041704
int? _zOrderIndex;
17051705
final String? _debugLabel;
17061706

1707-
static int _wallTime = kIsWeb
1707+
// TODO(kevmoo): Use double.minSafeInteger - 1 when the minimum Dart SDK is 3.15, https://github.com/flutter/flutter/issues/195202.
1708+
static int _wallTime = kIsWeb && !kIsWasm
17081709
? -9007199254740992 // -2^53
17091710
: -1 << 63;
17101711

‎packages/flutter/lib/src/widgets/sliver.dart‎

Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1186,8 +1186,9 @@ class SliverMultiBoxAdaptorElement extends RenderObjectElement
11861186
var lo = 0;
11871187
var hi = 1;
11881188
final adaptorWidget = widget as SliverMultiBoxAdaptorWidget;
1189-
const int max = kIsWeb
1190-
? 9007199254740992 // max safe integer on JS (from 0 to this number x != x+1)
1189+
// TODO(kevmoo): Use double.maxSafeInteger + 1 when the minimum Dart SDK is 3.15, https://github.com/flutter/flutter/issues/195202.
1190+
const int max = kIsWeb && !kIsWasm
1191+
? 9007199254740992 // max safe integer on JS + 1 (2^53)
11911192
: ((1 << 63) - 1);
11921193
while (_build(hi - 1, adaptorWidget) != null) {
11931194
lo = hi - 1;

‎packages/flutter/test/foundation/persistent_hash_map_test.dart‎

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -77,4 +77,28 @@ void main() {
7777
}
7878
}
7979
});
80+
81+
test('PersistentHashMap - bit 31 and compressed bitmap popcount', () {
82+
// Place index 31 (1 << 31) first so occupiedIndices has bit 31 set during
83+
// every subsequent _CompressedNode.put call while below the 16-entry
84+
// _FullNode inflation threshold, then cross inflation with bit 31 occupied.
85+
const compressedIndices = <int>[31, 0, 1, 2, 5, 7, 11, 13, 15, 17, 19, 23, 25, 29, 30];
86+
var map = const PersistentHashMap<_MockKey, int>.empty();
87+
for (final index in compressedIndices) {
88+
map = map.put(_MockKey(hashCode: index, payload: 'k$index'), index * 10);
89+
}
90+
for (final index in compressedIndices) {
91+
expect(map[_MockKey(hashCode: index, payload: 'k$index')], equals(index * 10));
92+
}
93+
expect(map[const _MockKey(hashCode: 28, payload: 'missing')], isNull);
94+
95+
const inflationIndices = <int>[3, 4];
96+
for (final index in inflationIndices) {
97+
map = map.put(_MockKey(hashCode: index, payload: 'k$index'), index * 10);
98+
}
99+
for (final index in <int>[...compressedIndices, ...inflationIndices]) {
100+
expect(map[_MockKey(hashCode: index, payload: 'k$index')], equals(index * 10));
101+
}
102+
expect(map[const _MockKey(hashCode: 28, payload: 'missing')], isNull);
103+
});
80104
}

‎packages/flutter/test/widgets/sliver_list_test.dart‎

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2,6 +2,7 @@
22
// Use of this source code is governed by a BSD-style license that can be
33
// found in the LICENSE file.
44

5+
import 'package:flutter/foundation.dart';
56
import 'package:flutter/widgets.dart';
67
import 'package:flutter_test/flutter_test.dart';
78

@@ -381,6 +382,51 @@ void main() {
381382
expect(s1.index, 6);
382383
expect(s2.index, 7);
383384
});
385+
386+
testWidgets('SliverMultiBoxAdaptorElement.childCount scopes 53-bit cap to JS web', (
387+
WidgetTester tester,
388+
) async {
389+
const jsMaxSafeInteger = 9007199254740991; // 2^53 - 1
390+
const jsCap = 9007199254740992; // 2^53
391+
int? targetCount;
392+
393+
await tester.pumpWidget(
394+
Directionality(
395+
textDirection: TextDirection.ltr,
396+
child: CustomScrollView(
397+
slivers: <Widget>[
398+
SliverList.builder(
399+
itemBuilder: (BuildContext context, int index) {
400+
if (targetCount case final int count when index >= count) {
401+
return null;
402+
}
403+
return const SizedBox(height: 10);
404+
},
405+
),
406+
],
407+
),
408+
),
409+
);
410+
411+
final SliverMultiBoxAdaptorElement element = tester.element<SliverMultiBoxAdaptorElement>(
412+
find.byType(SliverList),
413+
);
414+
415+
targetCount = jsMaxSafeInteger;
416+
expect(element.childCount, jsMaxSafeInteger);
417+
418+
if (kIsWeb && !kIsWasm) {
419+
targetCount = jsCap;
420+
expect(() => element.childCount, throwsFlutterError);
421+
} else {
422+
targetCount = jsCap;
423+
expect(element.childCount, jsCap);
424+
425+
final int above53BitCount = int.parse('18014398509482021'); // 2^54 + 37
426+
targetCount = above53BitCount;
427+
expect(element.childCount, above53BitCount);
428+
}
429+
});
384430
}
385431

386432
Widget _buildSliverListRenderWidgetChild(List<String> items, ScrollController controller) {

0 commit comments

Comments
 (0)