Skip to content

[vm/ffi] Array should expose an iterable #45508

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Open
dcharkes opened this issue Mar 29, 2021 · 19 comments
Open

[vm/ffi] Array should expose an iterable #45508

dcharkes opened this issue Mar 29, 2021 · 19 comments
Assignees
Labels
area-vm Use area-vm for VM related issues, including code coverage, and the AOT and JIT backends. contributions-welcome Contributions welcome to help resolve this (the resolution is expected to be clear from the issue) library-ffi

Comments

@dcharkes
Copy link
Contributor

dcharkes commented Mar 29, 2021

Pointers expose asTypedList which yields a TypedData which can be iterated over. Arrays do not.

We should either create an Array.asTypedList set of extensions, or provide another way to iterate over an Array's content. (Bonus: Arrays already carry a lenght, so .asTypedList() does not require a length argument.)

@timsneath thanks for reporting!

@dcharkes dcharkes added area-vm Use area-vm for VM related issues, including code coverage, and the AOT and JIT backends. library-ffi labels Mar 29, 2021
@dcharkes dcharkes changed the title [ffi] Array should expose an iterable [vm/ffi] Array should expose an iterable Jul 5, 2021
@Sunbreak
Copy link

Sunbreak commented Feb 7, 2022

Any plan?

@maks
Copy link

maks commented Feb 15, 2022

@dcharkes in the meantime is there any chance to document somewhere how to deal with ffi Arrays in structs. Maybe in the existing samples?

If it wasn't for my happening to find this comment (thank you @Sunbreak !!! 🙏🏻 ) I would have had no idea how to deal with getting a string out of a inline Array in a C struct I'm working with - the Dart docs for ffi Array are not really helpful at the moment.

@lrhn
Copy link
Member

lrhn commented Feb 15, 2022

Consider exposing it as a (fixed-length) List, maybe List<X> get elements;.
(I'm assuming it has to be an extension getter, so the Dart type X can depend on the native array element type.)

@Sunbreak
Copy link

Here is the use case

https://github.com/woodemi/twaindsm.dart/blob/ecc1f3d242bbdca56e71ea75ce0f6d88fd165b42/lib/twaindsm.dart#L517-L518

@ffi.Packed(2)
class TW_IMAGEINFO extends ffi.Struct {
  @ffi.Array.multi([8])
  external ffi.Array<TW_INT16> BitsPerSample;
}

https://github.com/woodemi/twaindsm.dart/blob/ecc1f3d242bbdca56e71ea75ce0f6d88fd165b42/lib/structs.dart#L80-L84

extension TWImageInfo on TW_IMAGEINFO {
  Map<String, Object> toMap() => {
      'BitsPerSample': spreadBitsPerSample(),
    };

  Iterable<int> spreadBitsPerSample() sync* {
    for (var i = 0; i < 8; i++) {
      yield BitsPerSample[i];
    }
  }
}

With List<X> get elements it would be

extension TWImageInfo on TW_IMAGEINFO {
  Map<String, Object> toMap() => {
      'BitsPerSample': BitsPerSample.elements,
    };
}

@dcharkes dcharkes added the good first issue A good starting issue for contributors (issues with this label will appear in /contribute) label Dec 18, 2023
@shikharish
Copy link
Contributor

@dcharkes I would like to work on this issue. Please can you give me an overview about it?

@dcharkes
Copy link
Contributor Author

dcharkes commented Jan 24, 2024

Consider exposing it as a (fixed-length) List, maybe List<X> get elements;. (I'm assuming it has to be an extension getter, so the Dart type X can depend on the native array element type.)

@lrhn Do you suggest List<X> instead of Iterable<X> so that people can query the length and have O(1) random access?

Array's of ints and floats

I think for Array<Int8> (and the other int and floating types) asTypedList is more general, it implements list.

/// Bounds checking indexing methods on [Array]s of [Int8].
@Since('2.13')
extension Int8Array on Array<Int8> {
  external int operator [](int index);

  external void operator []=(int index, int value);

  /// Creates a typed list view backed by memory this Array is a view on.
  ///
  /// Uses the array dimensions for determining the list.
  @Since('3.4')
  external Int8List get elements;
}

@shikharish

  • sdk/lib/ffi/ffi.dart The API needs to be introduced here.
  • sdk/lib/_internal/vm/lib/ffi_patch.dart The implementations for ints and floats can be introduced here.
  • (and the code generation file that generates part of those files)
@patch
extension Int8Array on Array<Int8> {
  Int8List get elements {
    final length = _nestedDimensionsFlattened;
    if(_typedDataBase is Pointer) {
      return (_typedDataBase as Pointer).cast<Int8>().asTypedList(length);
    }
    assert(_typedDataBase is TypedData);
    return Int8List.sublistView(_typeDataBase as TypedData, 0, length);
  }
}

Make sure to write a bunch of tests which exercise things with different base offsets etc. I think you can currently only write tests which use Structs, because that's the only way to obtain Arrays currently.

Arrays of Structs, Unions, Arrays, and Pointers

For Array<MyStruct> we can't use TypedData. So we'd need to return a class that implements List<MyStruct> (and throws on modification).

The API would be somewhat similar:

/// Bounds checking indexing methods on [Array]s of [Struct].
@Since('2.13')
extension StructArray<T extends Struct> on Array<T> {
  /// This extension method must be invoked on a receiver of type `Pointer<T>`
  /// where `T` is a compile-time constant type.
  external T operator [](int index);
  
  /// Creates a typed list view backed by memory this Array is a view on.
  ///
  /// Uses the array dimensions for determining the list.
  @Since('3.4')
  external List<T> get elements;
}

The implementation would need to return object that implements the List interface, but we don't want to actually fabricate the list.

@patch
extension StructArray<T extends Struct> on Array<T> {
  @patch
  external List<T> get elements {
    return _StructArrayList<T>(this);
  }
}

class _StructArrayList<T extends Struct> with UnmodifiableListMixin {
  final Array<T> _array;

  @override
  T operator [](int index) => _array[index];

  // all the other methods that need to be implemented such as 
}

All of the implementation should be possible in the two files mentioned before.

This is a rough sketch of the implementation, I might have missed some details. 😄 Let me know if you can make it work or if you have more questions.

@lrhn
Copy link
Member

lrhn commented Jan 24, 2024

@lrhn Do you suggest List<X> instead of Iterable<X> so that people can query the length and have O(1) random access?

Yes. Because we can, and if we don't, we can expect users to do .toList() on the iterable all the time.
Which is exactly what we don't want.

@shikharish
Copy link
Contributor

@dcharkes Thank you for the detailed explanation. Will make a PR soon.

I had a question, which is a bit off-topic. Is there something like "array to pointer decay" in Dart? How are arrays passed as parameters?

@dcharkes
Copy link
Contributor Author

I had a question, which is a bit off-topic. Is there something like "array to pointer decay" in Dart? How are arrays passed as parameters?

Array's are currently not passable as parameters. The reason is that arrays can be backed by typed data in the Dart heap. We could consider allowing it for isLeaf: true FFI calls, I've filed #54739.

@shikharish
Copy link
Contributor

@dcharkes Can you please explain the implementation of Arrays of Struct, Unions, etc. a bit more? I understand that we cannot use TypedData.

The implementation would need to return object that implements the List interface, but we don't want to actually fabricate the list.

What does this mean?

@dcharkes
Copy link
Contributor Author

@dcharkes Can you please explain the implementation of Arrays of Struct, Unions, etc. a bit more? I understand that we cannot use TypedData.

The implementation would need to return object that implements the List interface, but we don't want to actually fabricate the list.

What does this mean?

We want to return an object that has the type List<MyStruct>. The object does not have to be a List. It can be a class _StructArrayList<T extends Struct> implements List<T>. Now if we create a class _StructArrayList that claims to implement the public API of List, it must implement all the methods of List. So this is exactly what we do, we implement all the methods of the List class inside _StructArrayList. So we use List as an interface type and return something that implements that interface.

The way that we implement all the methods is that we just forward them to Array. So we make _StructArrayList have a single field, and that field holds an Array.

Does that make sense?

@shikharish
Copy link
Contributor

@dcharkes Yes, got it. But why can't we just create a List object, fill it with the elements of the Array and return that List?

@dcharkes
Copy link
Contributor Author

@dcharkes Yes, got it. But why can't we just create a List object, fill it with the elements of the Array and return that List?

Imagine you have an array with length 1000000, you convert it to a list, and then access he 200th element and then let the list be garbage collected. This would take O(length-of-list) time. If you construct only a wrapper object, it would take O(1) time.

@shikharish
Copy link
Contributor

@dcharkes Why is there no BoolList?
image

@dcharkes
Copy link
Contributor Author

@dcharkes Why is there no BoolList?

@lrhn might know the answer to that.

@lrhn
Copy link
Member

lrhn commented Jan 31, 2024

JavaScript had no BoolArray.
Nothing deeper.

It's something one can easily write on top of any typed data list, but it's also not needed that often, and usually only as an internal implementation detail, so most people will just implement the functionality directly on top of a Uint8List. No reusable code needed.

@shikharish
Copy link
Contributor

BoolArray is defined in ffi.dart but there is no List implementation. Why would that be?

@dcharkes
Copy link
Contributor Author

If you want to support Array<Bool> to have a List<Bool> get elements, you can do it the same way as for Array<Struct> and forward the calls to a Uint8List (or just to Array<Bool> itself).

copybara-service bot pushed a commit that referenced this issue Feb 2, 2024
Refactor to avoid conflicts later with concurrent work on:
- #45508
- #44589

Change-Id: I7b7ea2e4ec29115da42b0c196a2952c3cd5d3fa6
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/349901
Commit-Queue: Martin Kustermann <[email protected]>
Auto-Submit: Daco Harkes <[email protected]>
Reviewed-by: Martin Kustermann <[email protected]>
@dcharkes dcharkes added contributions-welcome Contributions welcome to help resolve this (the resolution is expected to be clear from the issue) and removed good first issue A good starting issue for contributors (issues with this label will appear in /contribute) labels Aug 13, 2024
@goderbauer goderbauer self-assigned this Feb 21, 2025
copybara-service bot pushed a commit that referenced this issue Mar 20, 2025
For the arrays of the Int/Uint/Float/Double types this has been
implemented straight in the ffi_patch.dart file and `elements` returns a
typed-data list view on the original data backing the array.

The Bool and Pointer arrays return helper classes from their `elements`
getter. These helper classes implement the `List` interface utilizing
the `operator []` implementation of the underlying arrays. This is also
implemented directly in the ffi_patch.dart file.

The `elements` getter for array arrays is rewritten in the CFE
(use_sites.dart) to instantiate a helper class to which the size of a
single element of the array is passed (this information is not available
in ffi_patch.dart, hence the rewrite in the CFE). The helper class
implements the `List` interface and performs some pointer arithmetic
with the provided element size to implement its methods.

The `elements` getters for struct and union arrays are also rewritten in
the CFE to instantiate a helper class to which a constructor tearoff for
instantiating the underlying struct/union type is passed. The helper
class also implements the `List` interface and uses the provided
constructor tearoff to create instantiated structs/unions of the
elements in the list.

Last, but not least, the `elements` getter for abi-specific integer
arrays is also rewritten in the CFI to instantiate a helper class to
which a closure is provided to load abi specific integers from the
underlying array data structure.

TEST=tests/ffi/array_compound_elements_test.dart
TEST=tests/ffi/array_primitive_elements_generated_test.dart
CoreLibraryReviewExempt: Dart VM only.
Bug: #45508
Change-Id: I211a42174057c39632c6a363d4e8e6fa8e94e801
Cq-Include-Trybots: dart/try:vm-aot-android-release-arm64c-try,vm-aot-android-release-arm_x64-try,vm-aot-asan-linux-release-x64-try,vm-aot-linux-debug-x64-try,vm-aot-linux-debug-x64c-try,vm-aot-mac-release-arm64-try,vm-aot-mac-release-x64-try,vm-aot-msan-linux-release-x64-try,vm-aot-obfuscate-linux-release-x64-try,vm-aot-optimization-level-linux-release-x64-try,vm-aot-tsan-linux-release-x64-try,vm-aot-ubsan-linux-release-x64-try,vm-aot-win-debug-arm64-try,vm-aot-win-debug-x64-try,vm-aot-win-debug-x64c-try,vm-appjit-linux-debug-x64-try,vm-asan-linux-release-arm64-try,vm-asan-linux-release-x64-try,vm-checked-mac-release-arm64-try,vm-eager-optimization-linux-release-ia32-try,vm-eager-optimization-linux-release-x64-try,vm-ffi-android-debug-arm-try,vm-ffi-android-debug-arm64c-try,vm-ffi-mac-debug-simarm64_arm64-try,vm-ffi-qemu-linux-release-arm-try,vm-ffi-qemu-linux-release-riscv64-try,vm-fuchsia-release-arm64-try,vm-fuchsia-release-x64-try,vm-linux-debug-ia32-try,vm-linux-debug-x64-try,vm-linux-debug-x64c-try,vm-mac-debug-arm64-try,vm-mac-debug-x64-try,vm-msan-linux-release-arm64-try,vm-msan-linux-release-x64-try,vm-reload-linux-debug-x64-try,vm-reload-rollback-linux-debug-x64-try,vm-tsan-linux-release-arm64-try,vm-tsan-linux-release-x64-try,vm-ubsan-linux-release-arm64-try,vm-ubsan-linux-release-x64-try,vm-win-debug-arm64-try,vm-win-debug-x64-try,vm-win-debug-x64c-try,vm-win-release-ia32-try
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/414821
Commit-Queue: Daco Harkes <[email protected]>
Reviewed-by: Daco Harkes <[email protected]>
Reviewed-by: Alexander Markov <[email protected]>
Reviewed-by: Lasse Nielsen <[email protected]>
copybara-service bot pushed a commit that referenced this issue Mar 20, 2025
_BoolArrayList needs to extend FixedLengthListMixin instead of
UnmodifiableListMixin since it implements `operator []=`.

Also contains some other doc fixes that were brought up post-submit in
https://dart-review.googlesource.com/c/sdk/+/414821.

TEST=tests/ffi/array_primitive_elements_generated_test.dart

CoreLibraryReviewExempt: Dart VM only.
Bug: #45508
Change-Id: I7635152283aec51a4f38e06fdfc7da84e93e55ab
Cq-Include-Trybots: dart/try:vm-aot-android-release-arm64c-try,vm-aot-android-release-arm_x64-try,vm-aot-asan-linux-release-x64-try,vm-aot-linux-debug-x64-try,vm-aot-linux-debug-x64c-try,vm-aot-mac-release-arm64-try,vm-aot-mac-release-x64-try,vm-aot-msan-linux-release-x64-try,vm-aot-obfuscate-linux-release-x64-try,vm-aot-optimization-level-linux-release-x64-try,vm-aot-tsan-linux-release-x64-try,vm-aot-ubsan-linux-release-x64-try,vm-aot-win-debug-arm64-try,vm-aot-win-debug-x64-try,vm-aot-win-debug-x64c-try,vm-appjit-linux-debug-x64-try,vm-asan-linux-release-arm64-try,vm-asan-linux-release-x64-try,vm-checked-mac-release-arm64-try,vm-eager-optimization-linux-release-ia32-try,vm-eager-optimization-linux-release-x64-try,vm-ffi-android-debug-arm-try,vm-ffi-android-debug-arm64c-try,vm-ffi-mac-debug-simarm64_arm64-try,vm-ffi-qemu-linux-release-arm-try,vm-ffi-qemu-linux-release-riscv64-try,vm-fuchsia-release-arm64-try,vm-fuchsia-release-x64-try,vm-linux-debug-ia32-try,vm-linux-debug-x64-try,vm-linux-debug-x64c-try,vm-mac-debug-arm64-try,vm-mac-debug-x64-try,vm-msan-linux-release-arm64-try,vm-msan-linux-release-x64-try,vm-reload-linux-debug-x64-try,vm-reload-rollback-linux-debug-x64-try,vm-tsan-linux-release-arm64-try,vm-tsan-linux-release-x64-try,vm-ubsan-linux-release-arm64-try,vm-ubsan-linux-release-x64-try,vm-win-debug-arm64-try,vm-win-debug-x64-try,vm-win-debug-x64c-try,vm-win-release-ia32-try
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/417100
Reviewed-by: Daco Harkes <[email protected]>
Commit-Queue: Michael Goderbauer <[email protected]>
@mraleph
Copy link
Member

mraleph commented Mar 25, 2025

DBC to already landed commits:

  • Please make sure to add CHANGELOG entry
  • Please make sure to check generated code: for (var v in s.inlineArray.elements) should be fully inlined and specialized in both AOT and JIT. I assume we miss a number of prefer-inline annotations here and there for this to work.

copybara-service bot pushed a commit that referenced this issue Apr 22, 2025
Follow-up to https://dart-review.googlesource.com/c/sdk/+/414821

Bug: #45508
Change-Id: I46380486fb3758e2a99c829a33e3b75c96bfab52
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/423720
Reviewed-by: Daco Harkes <[email protected]>
Commit-Queue: Michael Goderbauer <[email protected]>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
area-vm Use area-vm for VM related issues, including code coverage, and the AOT and JIT backends. contributions-welcome Contributions welcome to help resolve this (the resolution is expected to be clear from the issue) library-ffi
Projects
None yet
Development

No branches or pull requests

7 participants