Kata

Iterator is a mechanism that allows you to lazily traverse a data structure

The iterator shouldn't do any work unless explicitly requested, but your map (at least) starts processing the data immediately.

Thank you for the anwer. So if I well understand, when iterator_map() is called I just have to store the mapping function and mapping function's output size and I will perform the actual mapping only on the neeeded elements when iterator_next is called. Am I correct?

Thanx.

Yes.

No, not at all, it could be any size. However, giving your response I presume it should be sizeof (int).

No, not at all, it could be any size

With initial index being int, the only logical conclusion is that enumerate also generates int's. It could be long or long long in theory, but that'd make little sense since the iterator's capabilities would be limited by the function's interface.

Are you sure that's the message you're getting? The assertion is:

cr_assert_arr_eq(
  buffer,
  expected[i],
  sizeof(int) * 4,
  "Zip([1, 2, 3, 4], Zip(Zip([10, 20, 30, 40], [100, 200, 300, 400]), [1000, 2000, 3000, 4000]))[next_%d]: [%d, %d, %d, %d] should equal [%d, %d, %d, %d]",
  i,
  buffer[0], buffer[1], buffer[2], buffer[3],
  expected[i][0], expected[i][1], expected[i][2], expected[i][3]
);

and as you can see, it should use correct values for formatting.

Edit: it seems you're overwriting values on the stack.

How can I overwrite values in testcode?? Shouldn't that be impossible?

Shouldn't that be impossible?

What do you mean by saying "impossible"? Both the buffer and the expected values are stored on the stack - writing past the buffer bounds may easily affect the latter.

Would it not suffice for the output buffer to be large enough to contain the value produced by the iterator?

I'm not sure what you're talking about. If you mean that the description should state that "the values produced by the iterator being consumed fit in the buffer exactly", then it already says so, although with a different phrasing (saying that the buffer is "large enough" would imply the possiblity of it being bigger than required, and that'd be a lie). If you're suggesting that the buffer in the test code should be big enough to hold any value produced by any of the iterators in the whole consumption chain, then no - dealing with all this stuff correctly is the solver's responsibility.

I meant it should not matter if the caller happens to pass an output buffer larger than the expected output. Of course, the callee should not assume that the output buffer is any larger than necessary.

We know the size of the input to the MapFunction from the first argument to iterator_map, but how do we know the size of the output, other than from the third argument? My solution makes use of that third argument, but it would be interesting to see an implementation that does not use it at all (if it exists).

Okay, so it sseems there's this note in the comment of iterator.next: "// multiple values produced by "enumerate" or "zip" should be tightly-packed" so the question is indeed explained, but then instead of the issue i'd suggest putting this remark in some more prominent place, for example in a dedicated bullet point of "Special arguments" or the note about MemFunction and FilterFunction.

Gosh I cannot edit the label of the initial post to change it from issue to suggestion. Feel free to treat this one as just suggestion, or resolve it if you think it's completely invalid.

If I understand correctly, it is unsafe in C to reinterpret unaligned pointers (or something like that), right? Would it suffice to simply state that "MapFunction and FilterFunction assume the inputs pointers to be properly aligned, or they may fail otherwise"?

If I understand correctly, it is unsafe in C to reinterpret unaligned pointers (or something like that), right?

I'm not sure what you mean exactly, but it's kind of like that. A pointer can always be cast to void* and back, an object representation can always be memcpyed from anywhere to anywhere, but an object can't exist and be used normally without proper alignment.

Would it suffice to simply state that "MapFunction and FilterFunction assume the inputs pointers to be properly aligned, or they may fail otherwise"?

I guess so. It's hard to test it reliably because buffers can happen to be aligned accidentally. There are pointers in iterator_next too that are impossible to align with zipping and enumerating.

Added a note about this after the MapFunction and FilterFunction. If you have any other remarks/ideas, please share them.

What is "the proper alignment" in a context where some objects have to remain unaligned (results of zip and enumerate)? Is it the alignment of the first object, the LCM of subobject alignments or the maximum possible alignment? (None allows to access the second object directly, but some choices can give some usefull information for certain use cases.) What about the pointer in iterator_next? (It could be used for direct filtering.)

If I'm not mistaken, my solution uses pointers aligned according to the LCM of all the intermediate alignments, and it happens to work, although I'm not really sure. I didn't consider the objects' alignment when authoring this, and I'm wondering now if it would be better to rewrite all the functions to work with char * and read values using buffers instead of casting the pointer directly? If I understand correctly, this should resolve the problem entirely.

If I'm not mistaken, my solution uses pointers aligned according to the LCM of all the intermediate alignments

It looks like filter_iterator_next writes to unaligned char buffer[]...

and it happens to work

Alignment of non-vector types almost doesn't matter on x86, so anything will work at the low level as long as Clang doesn't apply any clever optimizations based on assumptions around alignment.

if it would be better to rewrite all the functions to work with char *

There isn't much difference between char* and void*, it doesn't matter.

read values using buffers instead of casting the pointer directly?

Yes, probably. The compiler knows anyway if unaligned access is possible on a given platform, so with optimizations memcpys will probably be just normal memory reads and writes whenever possible.

I've updated all the functions to read the data by memcpy'ing it, and changed the note in the description to explain how exactly MapFunction and FilterFunction work.

For some reason I was thinking that bool was an "alias" for some 4-byte type and there was no point in ever using it. Changed int to bool everywhere.

What about iterator_next?

Changed as well.

I've added an error message for this test, but the random tests will probably have to log X should equal Y because printing hundreds-of-elements-long arrays would not be useful, and idk if there's any other meaningful information that could be provided instead.

Rewrote the examples to make the next usage clear.