Off-by-one error in Strings.peel

[reuster986]

The inner for loops in the following code should iterate over 0..#(len-1), not 0..#len:

https://github.com/mhmerrill/arkouda/blob/5c4d04a15ca6fb150223a789bc43a70e393ac34c/src/SegmentedArray.chpl#L619-L630

Background: the peel function splits strings into left and right portions based on a delimiter. After the logic of finding the split point is all complete, this code copies the bytes of the left and right portions into their respective destination arrays. The leftLengths and rightLengths arrays are supplying the full lengths of the destination buffers, including the null byte, i.e. one greater than the actual length of the substring to be copied. Thus, when the code copies #len bytes from the source buffer, it is grabbing an extra byte from the source string and overwriting the destination's null terminator with it. This results in strings that are not null-terminated and misbehave in weird and hard-to-find ways.

As part of this issue, we should consider adding validation on the ak.Strings class that checks for null terminators, and/or a CI test that checks for null-terminators after a peel operation. I am hopeful that resolving this issue will also address the sporadic CI failures for peel/stick and allow us to move this from experimental to fully supported functionality.

[ronawho]

I am hopeful that resolving this issue will also address the sporadic CI failures for peel/stick and allow us to move this from experimental to fully supported functionality.

Note that if you want to make it fully supported, switching from unorderedCopy to aggregators is probably important.

[reuster986]

@ronawho good point. If fixing this error gets the function working correctly, then we have a baseline from which to move towards aggregators. I think it could be done along the lines of how we did it in Segstring.this() with index arrays, where we sacrificed some memory to make a fully local byte index array for use with an aggregator.

Also, we will need to make a benchmark :)

[mhmerrill]

@reuster986 did we already address this? @glitch contact @reuster986 just in case he already solved this...

[glitch]

I touched based with @reuster986 and this is still an outstanding issue, I'm going to take a swing at it.

[glitch]

I'm walking through the code and trying to understand what's happening. One thing that keeps eluding me is why we expect a null termination character on both sides of the entry?

I believe we have a large sequence of bytes representing the strings and they are originally delimited by a null character, so i.e.

[key1:val1\x00key2:val2\x00key3:val3\x00]  # Question 1: do we expect a null char at the end of the entire strings.bytes array?

Given this is the Strings.bytes, the corresponding offsets should point to the beginning of each string as an offset from the start of the array, so we should have a Strings.offsets array that is [0, 10, 20], so far so good.

If the delimiter is a :, then the first entry should be [key1:val1\x00] the code finds the split point of the delimiter and we should end up with the left bytes of key1 and right bytes of val1\x00 so we should only have to scrub the single null byte right?

I made the suggested changes and tested it against a new unit test and it passes, so obviously one of my assumptions is wrong, but I'm not sure which one.

Any pointers?

[hokiegeek2]

@glitch I believe we expect a null char on both sides if it's a space-delimited string, but not (to the best of my knowledge) if there's another delimiter like ":"

[reuster986]

@glitch your description of the data format for the input Strings.bytes array is correct, but let's look at the expected output format for the left and right Strings.bytes:

[key1\x00key2\x00key3\x00]       # left Strings.bytes
[val1\x00val2\x00val3\x00]       # right Strings.bytes

Note that the output is two arrays of null-terminated strings, so we are creating a null terminator for the left part where there was none before.

For your example, the code should find the position of the : and then figure out 1) how many bytes to allocate for the output and 2) how many bytes to copy over. The bug in the current code is that it treats these two numbers as the same, although they are actually different. In the first entry, the code should determine that the left part requires 5 bytes of space in the output array (including the null terminator), but only 4 bytes should be copied over (the characters key1). Similarly, the right part also requires 5 bytes of space but only 4 bytes should be copied (val1).

What the original (buggy) code was doing was saying "the left part requires 5 bytes of space, so allocate 5 bytes for it and copy 5 bytes". This resulted in output like

[key1:key2:key3:]

I.e. the left-part strings are not null-terminated anymore and don't conform to the standard for arkouda Strings arrays. That was messing up some logic elsewhere in the code.

The suggested changes made it so that 5 bytes got allocated but only 4 bytes got copied. Because Chapel arrays get initialized to zero, that 5th byte is guaranteed to be null, as we want.

[glitch]

Thanks @reuster986 that was super helpful. I was able to add in some extra debug and play around a bit with the #(len) vs #(len-1) to see the difference. I'm spending some time looking into how Python handles null terminated strings and whether the server even sends it back as such to see if I can update/add a new client side unit test for it. Thanks again!

EDIT: As an aside, I can attach directly to the string bytes object for one of the sides of peel, i.e.

a, b = mystring.peel(":")
a.register("a")
abytes = ak.pdarray.attach("a.bytes")

but we don't support a str/datastr or repr/datarepr on uint8 dtypes. Adding that support would make it easier for debugging etc. but it may not be a good idea as users really shouldn't be messing with the guts of stuff.

[glitch]

Ah, I figured out a reasonable way to look at what is in the bytes section from the client side of things:

import pandas as pd
import arkouda as ak
ak.connect("localhost", 5555)

series = pd.Series(["k1:v1", "k2:v2", "k3:v3"])
pda = ak.from_series(series, "string")
a, b = pda.peel(":")
a.register("a")
abytes = ak.pdarray.attach("a.bytes")
x = abytes.to_ndarray()

>>> print(a)  # Will print the strings object
['k1', 'k2', 'k3']
>>> print(x)  # Will print out the bytes in decimal representation
[107  49   0 107  50   0 107  51   0]


# Similarly the original strings bytes (using same register/attach/to_ndarray() technique) is
print(orig_bytes.to_ndarray())
[107  49  58 118  49   0 107  50  58 118  50   0 107  51  58 118  51   0]

(Sorry, I'm really just documenting my learning process)