Breaking up (lines) is hard to do
Here’s a seemingly simple question: given a chunk of multi-line text, how do you split it and return an array whose members are the constituent lines of the text?
Hopefully, your first instinct is to reach for some sort of standard-library function, maybe something like the splitlines() method of Python’s str type. Because it turns out this “simple” question is actually pretty complex to answer! For example, quite some time ago I read a post by William Woodruff pointing out the surprising discovery that Python treats up to eleven different Unicode code points or code point sequences as indicating a line break.
At the time I meant to write about that, but a lot of other things started fighting for my time, and it’s only now that I’m finally digging it out of my drafts. Still, better late than never, so today let’s dig into some of the many ways there are to break a line of text and how they’ve been standardized and specified and ultimately wound up in the set Python uses.
In the beginning…
Once upon a time, there was ASCII. Of course there were other things before ASCII, and alongside ASCII, but for today’s discussion we really only need to go back to ASCII; if you want the full history of physical teletypes, how they evolved from typewriters and influenced character sets for computing and so on, I suggest Wikipedia. Here, I’m just going to gloss over and simplify a lot of that to focus on the topic at hand.
So. Once upon a time, there was ASCII. And it wound up being incredibly influential and important in computing, to an extent other early character sets couldn’t match. And because it was used on computers which used teletypes (basically electronic typewriters connected as input/output devices) as a user interface, it contained control characters for sending commands to the teletype. Such as a LINE FEED (byte value 0x0A) to advance the paper vertically to the next line, and a CARRIAGE RETURN (byte value 0x0D) to re-align the print head/carriage with the horizontal start point of the line.
These are often abbreviated LF and CR (or by their C-family escape sequences \n and \r, respectively), and you might think that since physically advancing a typewriter-style device to be ready to print the next line requires both operations, that would have just become the universal way everybody did new lines. Or at least the universal way everybody did them in English, or in the US, where ASCII dominated. Right?
Well, nothing is ever that simple. Physical teletypes apparently benefited from the two-character approach (as opposed to a single “new line” character) because it gave them time to physically move everything into the right position. But as virtual teletypes—“printing” to a television-like display instead of to paper—became more common, that was less of an issue. So there were multiple possible options for representing line breaks, and several of them showed up in historical systems. For example:
- CP/M used
CR LF. And so MS-DOS, which aimed for compatibility with it, usedCR LFtoo. And so Microsoft Windows, which wanted to be compatible with MS-DOS, also used it. - Meanwhile, Multics chose to use just
LFwith noCR, and Unix went along with that choice. - But Commodore and Apple and many others went yet another way and used plain
CR, with noLF.
This meant “plain text” was not easily portable between these various systems, since none of them could agree on how to represent a line break. Which led to one of my all-time favorite programming jokes, in the infamous “NOT the comp.text.sgml FAQ” document:
Q. What’s an RE?
A. RE is an acronym for Record End, which is sort of like a newline, only different. Goldfarb’s First Law of Text Processing states that:
“… if a text processing system has bugs, at least one of them will have to do with the handling of input line endings.”
[The Handbook, footnote p. 321]
The Record End concept was introduced to make sure that SGML parsers don’t violate Goldfarb’s First Law.
(for the uninitiated, Charles Goldfarb created SGML)
Anyway, over twenty years ago Python tried (in Python 2.3) to smooth this over by introducing “universal newline” mode for opening files, which accepts all three options: a plain \n (Unix), or a plain \r (classic Mac), or an \r\n sequence (DOS and Windows) will all be interpreted as line breaks.
But even in ASCII there there are other ways of breaking a line. For example, at byte value 0x0C ASCII includes the FORM FEED control character (FF, or \f). Which is not one of the traditional characters used by major operating systems as a “newline”, but nonetheless does cause a new line to occur: it moves to the next page (if necessary, by ejecting the current sheet of paper from the printer and feeding in a new one). And there’s also 0x0B, VERTICAL TAB (VT or \v): just as a “regular” tab (\t) causes a horizontal adjustment, a vertical tab causes a vertical one. So it, too, causes output to advance to another line (probably skipping several in the process).
And the C1 control characters added 0x85, the NEXT LINE character (typically abbreviated NEL), useful for translating back and forth between ASCII and IBM’s EBCDIC character set (which had “New Line” as a single character).
Then Unicode happened
Today we live in a Unicode world, and Unicode tries its hardest to catalog and standardize and describe how to work with all the world’s writing systems. Chapter 5, Section 8 of the Unicode Standard, “Newline Guidelines”, lists seven code points to recognize as causing new lines. Five of them we’ve seen already:
U+000A LINE FEED, from ASCIIU+000B LINE TABULATION, from ASCII’s vertical tabU+000C FORM FEED, from ASCIIU+000D CARRIAGE RETURN, from ASCIIU+0085 NEXT LINE, from the C1 control codes
The CR LF sequence is also recognized, on systems which use it.
But the other two code points are new and were created specifically for Unicode:
U+2028 LINE SEPARATOR(which Unicode likes to abbreviate asLS)U+2029 PARAGRAPH SEPARATOR(similarly abbreviated asPS)
The Unicode Standard explains that the traditional newline characters had started to become ambiguous, because of the rise of tools such as word-processing programs which automatically wrapped lines for display and so began using explicit “newline” characters to mean a paragraph break rather than a line break. So Unicode added two new code points whose purposes are explicit. And the standard says that “[I]n Unicode text, the PS and LS characters should be used wherever the desired function is unambiguous.”
This set of line-breaking code points originated in version 5.0 of Unicode, with Unicode Technical Report #13, which lists the seven “newline” code points and the CR LF sequence. This is also the set of code points and sequences defined for line boundaries in Unicode regular expressions, Unicode Technical Standard #18.
And expanding on Chapter 5 of the Standard, there’s Unicode Standard Annex #14, “Unicode Line Breaking Algorithm”. As the name implies, this document formally specifies the line-breaking algorithm for Unicode, including defining things like which characters offer an opportunity to break a line, whether the break is mandatory, and whether the break would come before or after the character in question. It does this in a typical Unicode way: by defining a set of named properties and specifying which characters have which properties.
Two ways about it
But there are still three “newline” characters supported by Python that we haven’t seen yet, and they come from a place that might be surprising: Unicode Standard Annex #9, the bidirectional algorithm. And it’s OK if you’re wondering what that has to do with newlines, because it’s not immediately obvious if you don’t already know about it.
Some written scripts, like the Latin script this blog post is written in, are written and read left-to-right: the start of a line of text is on the left-hand side, and the end is on the right-hand side. Other scripts, such as Arabic or Hebrew, do the opposite, and are right-to-left. And so Unicode, which again wants to cover all the world’s writing systems and let you use any or all of them, has to support both left-to-right and right-to-left horizontal text direction.
But more than that, it has to support switching direction within a single piece of text. You might have something that’s in, say, Arabic but quotes something in Spanish in the middle of a line; that would require a short section of left-to-right inside an otherwise right-to-left text. Or you might be writing something that uses boustrophedon, switching directions on each line. So Unicode includes direction-control characters like U+200E LEFT-TO-RIGHT MARK and U+200F RIGHT-TO-LEFT MARK to handle this. But it also needs to know the scope of a direction change, and that’s where the last “newline” characters come in: the Unicode bidirectional algorithm says that “[t]he effects of all of these formatting characters are limited to the current paragraph; thus, they are terminated by a paragraph separator”.
So Unicode characters have, among their properties, a “bidirectional class” which influences how they affect the bidirectional algorithm. And the characters which act as paragraph separators for purposes of ending the effects of an explicit directional marker all share a common value for this: bidirectional class B. The characters with that class include quite a few that we’ve already seen, along with three more characters:
U+001C INFORMATION SEPARATOR FOURU+001D INFORMATION SEPARATOR THREEU+001E INFORMATION SEPARATOR TWO
But these are better known by their original ASCII names: FILE SEPARATOR, GROUP SEPARATOR, and RECORD SEPARATOR. ASCII provided these to help represent data structures in memory and on storage media. Today it’s not as common to try to use control characters for this purpose, though they do have the virtue of being rare in actual text, unlike other common delimiters such as tab or comma.
End of the line
And now, after looking at multiple character sets and five Unicode technical documents, we can finally state clearly what’s going on in Python.
Python’s splitlines() treats ten different code points, and one multi-code-point sequence, as causing a line break. These are:
- The sequence
U+000D U+000A(CR LF). - The four code points which have line-breaking property
BK(Mandatory Break (Non-tailorable)):U+000B LINE TABULATION,U+000C FORM FEED,U+2028 LINE SEPARATOR, andU+2029 PARAGRAPH SEPARATOR. - The one code point which has line-breaking property
CR(Carriage Return (Non-tailorable)):U+000D CARRIAGE RETURN. - The one code point which has line-breaking property
LF(Line Feed (Non-tailorable)):U+000A LINE FEED. - The one code point which has line-breaking property
NL(Next Line (Non-tailorable)):U+0085 NEXT LINE. - The three code points which don’t have any of the above line-breaking properties, but do have bidirectional property
B:U+001C INFORMATION SEPARATOR FOUR,U+001D INFORMATION SEPARATOR THREE, andU+001E INFORMATION SEPARATOR TWO
Which is also exactly what’s stated by a comment in the CPython source code accompanying the list of individual code points that are considered to break lines, but hopefully now you have a better understanding of what that comment means and how this particular set was arrived at.