How hard is it to check for whitespace?

When looking through a piece of source code recently, I stumbled across this method from Guava – a popular Java library from Google.

As you might've guessed from the name, this method checks whether a given character is a whitespace character. Yet the code looks a lot more complex than a simple c == ' ' check. This made me curious and sent me down a small rabbit hole trying to understand where all this complexity was coming from. If you're curious how this code works too, this article is for you.

What is whitespace, anyway?

The first thing one needs when inspecting a function that checks whether a character is whitespace is to define what whitespace actually is. While the SPACE (U+0020) is probably the best-known whitespace character, it's not the only one. If you've been writing code for a while, you can probably name a few more – the non-breaking space NO-BREAK SPACE (U+00A0), a tab CHARACTER TABULATION (U+0009), a newline LINE FEED (U+000A).

Well, there are more. Unicode defines a White_Space property that gives us a list of 25 characters. Here they are – meticulously copied , ,,, , ,…, , , , , , , , , , , , , ,
,
, , ,　.

Each of these characters has a different purpose. FIGURE SPACE (U+2007), for example, has the same width as a digit in a table, while THIN SPACE (U+2009) and HAIR SPACE (U+200A) provide progressively smaller gaps. NO-BREAK SPACE (U+00A0) has the width of an ordinary space, but keeps the surrounding text together when wrapping a line.

It's not always easy to tell whether a character is in the whitespace set from the name or by looking at the glyph either. For instance, ZERO WIDTH SPACE (U+200B) isn't a whitespace character at all. Despite the name, it's a format character that can indicate a word or line break opportunity without adding a visible gap.

There are also some less obvious members of the set too. OGHAM SPACE MARK (U+1680) can actually be rendered as a visible horizontal line. In Ogham fonts with a stemline, the space continues that line between letters (e.g. ᚛ᚆᚓᚂᚂᚑ ᚒᚑᚏᚂᚇ᚜), while in stemless fonts, it's blank. So even the assumption that whitespace must look empty isn't always true.

Different runtimes, different rules

Having a single definition of whitespace is only useful if everyone can agree on it. But even within a single runtime, some libraries might disagree on what whitespace is.

Consider the NO-BREAK SPACE (U+00A0) I mentioned above. It's included in Unicode's White_Space property, but Java explicitly excludes it, along with two other non-breaking spaces. The javadoc usefully highlights that the method checks for whitespace according to Java, rather than according to the Unicode property we had a look at before.

Character.isWhitespace(' ');      // true
Character.isWhitespace('\u00A0'); // false

But what about other runtimes? Looking at two more popular ones, Python and JavaScript, we can see that there isn't a single authoritative list of characters everyone agrees on. Python, for example, has a convenient str.isspace() method. And unlike Java, it considers U+00A0 a whitespace character.

So possibly Python just follows Unicode's White_Space property? Not quite.

"\u00A0".isspace()  # True
"\u0085".isspace()  # True
"\u001C".isspace()  # True
"\uFEFF".isspace()  # False

The interesting one here is FILE SEPARATOR (U+001C). It's an ASCII control character originally intended to separate pieces of information, and it isn't included in Unicode's White_Space property. So Python recognises 29 whitespace characters, rather than Unicode's 25.

JavaScript takes yet another approach. It doesn't have an equivalent of the Character.isWhitespace() method, but we can use the \s character class in a regular expression:

/\s/.test("\u00A0");  // true
/\s/.test("\u0085");  // false
/\s/.test("\uFEFF");  // true

The odd one out above is NEXT LINE (U+0085). Unicode explicitly includes it in White_Space, and Python accepts it too, but JavaScript doesn't. Instead, JavaScript recognises ZERO WIDTH NO-BREAK SPACE (U+FEFF), which Unicode doesn't include in the set.

I haven't looked through any other runtimes, but something tells me the inconsistencies won't stop at these three.

Nothing is set in stone

What adds more complexity is that Unicode is not frozen in time, and is constantly evolving. And this affects the definition of whitespace. For example, Unicode 6.3 had reclassified MONGOLIAN VOWEL SEPARATOR (U+180E) from a space separator to a format character, removing its White_Space property. The Unicode whitespace set had changed from 26 characters to 25 as a result. For runtimes and libraries that strive for backwards compatibility, these changes can be a pretty significant challenge as you'd want the standard library of a language to be as stable as it can be.

Checking for whitespace fast

Let's say we've finally agreed on the set of characters we want to check – the current set of Unicode whitespace characters. A naive way to implement this would be to go through the list of characters and check whether any of them matches. While this would work, it's definitely not the most efficient approach.

So what Guava's implementation that we saw at the beginning of the article did was implement a perfect hash function – a hash function that guarantees no hash collisions for the characters in the known set.

static final String TABLE = "\u2002...";

@Override
public boolean matches(char c) {
    int slot = (1682554634 * c) >>> 27;
    return TABLE.charAt(slot) == c;
}

Above, TABLE is a string of 32 characters – effectively a hash table mapping each index (the key) to a character (the value). It contains all 25 Unicode whitespace characters, with some duplicates filling the remaining positions.

The most interesting part here is calculating the index. The multiplication 1682554634 * c produces a 32-bit integer, and >>> 27 shifts it 27 bits to the right, isolating the five most significant bits – a number in the [0, 32) range which can be used to look up the table. Of course, there are more possible characters than table entries, that's why the final == c check is needed to check that the character we found is the one we were looking up.

You can click on the characters below to see how the table is populated.

int value =

32

*

1682554634

= -1992826560

10001

001001101111110000101000000

17

0·

1·

2·

3·

4·

5·

6·

7·

8·

9·

10·

11·

12·

13·

14·

15·

16·

170020

18·

19·

20·

21·

22·

23·

24·

25·

26·

27·

28·

29·

30·

31·

The magic 1682554634 number does look magical, and it's unclear to me how it was chosen (please do share if you know the answer). But it's not the only possible multiplier, and you can find all suitable options by running a simple brute-force search.

static final char[] ALL_CHARS = (
        "\u2002\u3000\r\u0085"
        + "\u200A\u2005\u2000"
        + "\u2029\u000B\u2008"
        + "\u2003\u205F\u1680"
        + "\u0009\u0020\u2006"
        + "\u2001\u202F\u00A0"
        + "\u000C\u2009\u2004"
        + "\u2028\n\u2007"
).toCharArray();

public static void main(String[] a) {
    var slots = new BitSet(32);
    outer:
    for (int mul = 1; mul != 0; mul++) {
        slots.clear();
        for (char c : ALL_CHARS) {
            int index = (mul * c) >>> 27;
            if (slots.get(index)) {
                continue outer;
            }
            slots.set(index);
        }
        System.out.println(mul);
    }
}

Interestingly, anyone willing to dive deeper can trace how Guava arrived at this implementation by looking through the git history. It transitioned from a simpler matcher to a mod-79 version which has an interesting observation about the Unicode character set but had a downside of involving a division operation, then followed by a perfect hash function.

And if you're interested in other applications for perfect hashing – somewhat serendipitously just as I was writing this article, Daniel Lemire published a blog on the same topic where he gives an example of using perfect hashing for checking HTTP methods.

Conclusion

When I first saw the whitespace-checking code in Guava, it sparked my curiosity, and as a result I learned a few things about Unicode and saw an interesting application of a perfect hash function – something you don't see used that often in the wild.

I hope you've learned something interesting from this article too. And if you find something that sparks your curiosity, please do write a blog post and share it. I do feel that these write-ups are becoming increasingly rare in the AI-first world, where there's rarely a reason to peek under the hood of a function as simple as isWhitespace.