[C++][Compute] replace_substring_regex() creates invalid arrays => crash

[asfimport]

min

arr = pa.array(['A'] * 16)
arr2 = pa.compute.replace_substring_regex(arr, pattern="X", replacement="Y")
arr2.validate(full=True)

Expected results: a valid array
Actual results: pyarrow.lib.ArrowInvalid: Offset invariant failure: non-monotonic offset at slot 64: 0 < 63

So if you run arr.diff(arr2), you'll get something like:

terminate called after throwing an instance of 'std::length_error'
  what():  basic_string::_S_create
Aborted (core dumped)

This seems to happen if and only if the input array length is a multiple of 16. That leads to an ugly workaround:

def replace_substring_regex_workaround_12774(
    array: pa.Array,
    *,
    pattern: str,
    replacement: str
) -> pa.Array:
    if len(array) > 0 and len(array) % 16 == 0:
        chunked_array = pa.chunked_array([array.slice(0, 1), array.slice(1)], type=array.type)
        return pa.compute.replace_substring_regex(
            chunked_array,
            pattern=pattern,
            replacement=replacement
        ).combine_chunks()
    else:
        return pa.compute.replace_substring_regex(
            array,
            pattern=pattern,
            replacement=replacement
        )

Reporter: Adam Hooper / @adamhooper
Assignee: Niranda Perera / @nirandaperera

Related issues:

• [Python] compute.replace_substring_regex sometimes returns incorrect offsets, causing crashes/ub (supercedes)

PRs and other links:

• GitHub Pull Request #10320

_{Note: This issue was originally created as ARROW-12774. Please see the migration documentation for further details.}

[asfimport]

Antoine Pitrou / @pitrou:
@nirandaperera Perhaps you want to take a quick look at this.

[asfimport]

Niranda Perera / @nirandaperera:
@pitrou sure

[asfimport]

Eduardo Ponce / @edponce:
This error also occurs in replace_substring but not in other string transforms, including those that perform regex/match/split operations. It seems there is an offset miscalculation in the replace pipeline.

[asfimport]

Niranda Perera / @nirandaperera:
@pitrou I tried the following test cases in C++

// ARROW-12774
  ReplaceSubstringOptions options_regex3{"X", "Y"};
  this->CheckUnary("replace_substring_regex", R"(["AAAAAAAAAAAAAAAA"])", this->type(),
                   R"(["AAAAAAAAAAAAAAAA"])", &options_regex3);
  this->CheckUnary("replace_substring_regex", R"(["A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A"])", this->type(),
                   R"(["A","A","A","A","A","A","A","A","A","A","A","A","A","A","A","A"])", &options_regex3);

The 2nd case fails with the following error.

../src/arrow/compute/kernels/test_util.cc:52: Failure
Failed
'actual->ValidateFull()' failed with Invalid: Negative offsets in binary array
../src/arrow/compute/kernels/test_util.cc:90: Failure
Failed
replace_substring_regex(�) = � != A
../src/arrow/compute/kernels/test_util.cc:90: Failure
Failed
replace_substring_regex(\0) = \0 != A
../src/arrow/compute/kernels/test_util.cc:90: Failure
Failed
replace_substring_regex(\0) = \0 != A
../src/arrow/compute/kernels/test_util.cc:90: Failure
Failed
replace_substring_regex(\0) = \0 != A
../src/arrow/testing/gtest_util.cc:132: Failure
Failed@@ -0, +0 @@
-"A"
-"A"
-"A"
-"A"
+"�"
+"\0"
+"\0"
+"\0"
Expected:
  [
    "A",
    "A",
    "A",
    "A",
    "A"
  ]
Actual:
  [
    "�",
    "\0",
    "\0",
    "\0",
    "A"
  ]
../src/arrow/testing/gtest_util.cc:221: Failure
Failed
Got: 
  [
    [
      "�",
      "\0",
      "\0",
      "\0",
      "A"
    ],
    [
      "A",
      "A",
      "A",
      "A",
      "A",
      "A",
      "A",
      "A",
      "A",
      "A",
      "A"
    ]
  ]
Expected: 
  [
    [
      "A",
      "A",
      "A",
      "A",
      "A"
    ],
    [
      "A",
      "A",
      "A",
      "A",
      "A",
      "A",
      "A",
      "A",
      "A",
      "A",
      "A"
    ]
  ]

So, I believe the bug is confirmed. Let me see if I could figure out the reason behind this.

[asfimport]

Niranda Perera / @nirandaperera:
I think I found out the issue. The offset builder is reserved here [1]. So, when there are 16 string elements, only 16 slots are reserved. But it is "UnsafeAppend"ed for 17 times.

When buffers are resized, they are increased in multiples of 64b and 64bytes = 16 ints. So, that seems to be the reason why it is failing on multiples of 16.

@pitrou could you please check this PR [2]

[1] https://github.com/apache/arrow/blob/master/cpp/src/arrow/compute/kernels/scalar_string.cc#L1335

[2] #10320

[asfimport]

yibocai#1:
Issue resolved by pull request 10320
#10320