How C++ lower_bound caused a browser accessibility bug

In the last blog, I talked about the sneaky difference between lower_bound and upper_bound. And this blog is about how lower_bound caused a bug in Chromium.

Most people will never know this bug existed, and now that it has been merged and will land in your Chrome browser at some point, you probably will not notice the fix either. But there is a group in some corner of the world who will benefit from this fix.

This was a Chromium bug on macOS accessibility. When the macOS Accessibility API asked Chromium about the current line under a certain condition, Chromium was giving the wrong answer. This bug mostly involved these two APIs:

AXLineForIndex // maps a text index to a line number
AXRangeForLine // maps a line number to a text range

The first obvious step was to reproduce it with a small example:

<!DOCTYPE html>
<textarea id="textarea" rows="5" cols="15" wrap="off">
line zero
line one
line two</textarea
>

In this example, I clicked inside the second line, after line. The caret location was 14. I compared the behavior in Safari and Chromium, and this is what we got:

Value	Safari	Chromium
caret location	`14`	`14`
line number	`1`	`2`
line start location	`10`	`nil`
line length	`9`	`nil`

And it turned out we had two related issues:

AXLineForIndex(14) returned 2 instead of 1.
AXRangeForLine(...) returned nil instead of the current line range.

So, now that I knew the behavior, the next obvious step was to convert this into a test. We will anyway write a test after the fix, so why not start with it? Also, kind of like Test Driven Development :P

<!--
@SCRIPT:
  textarea.accessibilityParameterizedAttributeNames.has(AXLineForIndex)
  textarea.accessibilityParameterizedAttributeNames.has(AXRangeForLine)
  line:= textarea.AXLineForIndex(14)
  textarea.AXRangeForLine(line)
-->
<!DOCTYPE html>
<textarea id="textarea" rows="5" cols="15" wrap="off">
line zero
line one
line two</textarea
>

Notice in the test we use the same kind of textarea and ask Chromium for line and range:

AXLineForIndex(14)
AXRangeForLine(line)

Before the fix, the test returned:

line = 2
range = NULL

That makes sense. We had reduced the bug to two API calls and one failing expectation. From there we started digging deeper in chromium specifically where Chromium handles AXLineForIndex and AXRangeForLine for macOS. For the line number, Chromium already had line start positions. For this textarea, they were:

{0, 10, 19}

For caret index 14, the line we want is the one that starts at 10. But the old code was using lower_bound

auto iterator = std::lower_bound(lineStarts.begin(), lineStarts.end(), index);

And as we saw in the last blog, lower_bound returns the first value that is >= the value we are searching for. So for 14, this gives:

{0, 10, 19}
        ^
        19

That is not the line we wanted, and because the old code returned the iterator position, this became line: 2. Here, it seemed like we needed the > case rather than the >= case. So we are coming around to using upper_bound to find the next line start, and then step back to the current line:

auto iterator = std::upper_bound(lineStarts.begin(), lineStarts.end(), index);
return std::distance(lineStarts.begin(), iterator) - 1;

That gives line: 1, which is what Safari returned too. It also works for existing cases, not bad, huh!

This also explains why the bug only showed up when the caret was not at the beginning of a line. At index 10, lower_bound(10) returns 10, so it looked correct. At index 14, it jumps to 19. That fixed AXLineForIndex. But there was the second issue: AXRangeForLine. The old code only allowed line 0:

int lineIndex = [lineNumber intValue];
if (lineIndex != 0) {
  return nil;
}

return [NSValue valueWithRange:[self accessibilityRangeForLine:lineIndex]];

So asking for AXRangeForLine(1) could not return the range for line one. This was an easy fix: pass through the line number we received. accessibilityRangeForLine already expects it!

return [NSValue
    valueWithRange:[self accessibilityRangeForLine:[lineNumber intValue]]];

After both fixes, the same test returned:

line = 1
range = {loc: 10, len: 9}

That matched the Safari behavior we saw during reproduction. Amazing news!

But let's make our code more secure. We are using upper_bound so, let's handle invalid indexes like a negative index, or an index greater than or equal to the length of text. Chromium receives the index as a signed value, so the check happens before doing the line lookup:

if (index < 0 ||
    index >= static_cast<int>(_owner->GetValueForControl().size())) {
  return NSNotFound;
}

It feels pretty safe now! The accessibility data exposed to macOS was wrong. And the root cause was this tiny difference:

lower_bound: first >= value
upper_bound: first > value

And that pretty much sums up the bug.

I wrote this blog partly because landing a change in a browser used by millions of people felt worth documenting, but also because I hope it makes someone else feel a little less scared of working on big software.