Hacker News Reader

Comment by Joker_vD | Hacker News Reader

Or you can replace the escape sequences right in the source text: it works since no escape sequence is shorter than the text it represents.

View on HN

The downside is that you lose the original and can't refer to it anymore. If (like OP) you are writing a compiler, you may need to spit out error messages, and will want to be able to say "line X, column Y", or even just print out the original line itself.

And no, you can't re-escape your unescaped text, as you can't do so losslessly in all cases. For some, the unescaped text might not obviously need re-escaping (e.g. the original text had a unicode escape for an emoji; you'll "forget" that after you unescape it).

Well, that's a trade-off, as most things in the parser design. You can go the way of the compilers of the yore and report only the line numbers. Or you can maintain column numbers only for a single line, everything in the previous lines will get only a line number. Or you can store the column numbers in the tokens which works better if you lexer emits them one at a time and the parser is fine with that.

Storing column numbers for every token just in case there might be an error likely weighs out the string allocation reduction. But for error messages it might suffice to output just the line number together with a snippet of the line at the error location. Most people probably don't care about the exact column number, though it might be bad for other tools.

> Storing column numbers for every token just in case there might be an error likely weighs out the string allocation reduction.

Only if you store all of the tokens before starting the parsing, which would arguably be the bigger fish to fry in terms of conserving memory.

But it actually slows down the lexer: by an insignificant amount if the lexer is the traditionally written one, or by quite a lot if it's one of those new-fangled ones that use SIMD-instructions speed up finding the token boundaries... but such lexers also benefit wrom the ability to re-use unneeded parts of the source input (like quotes or spaces) for storing auxillary data.

If you save the offset (and you are, if you use a borrowed string) you can retrieve the original source code by re-reading the input file on the fly. This is expensive (due to IO, but especially also since you need to re-lex and recompute all offsets up to the point of the error), but it only needs to happen in case a parse error is generated, so the cost is likely negligible.

I’ve done this in a parser where I wanted to avoid storing line and column numbers instead of a single byte offset, but still wanted to provide the more user-friendly line and column numbers in the error message.

If you still have access to the original source in the filesystem you could just re-read the snippet and recover the original escaped form. If your language offers only a single way to escape characters then you may even just re-escape the string when emitting the error (although most languages have some sort of codepoint escape sequence)

You can also be lazy about it -- store the quoted string with 1 escape as 3 separate (fixed-size) tokens/spans, and don't actually allocate or decode strings until you need to.

In an interpreter there may be many string constants that aren't used (e.g. docstrings in Python).

And probably in a compiler too, since you may import a ton of library code and only use 1 function.

Storing escapes as tokens also lets you point to them in warnings. I think most compilers warn about bad octal escapes like \777 these days.

You can, but see, the actual contents of the strings are really only used at the code-gen stage, where it's put verbatim in the .rodata section. Arguably, it could have been discarded by the dead-code elimination pass by that time but that's unlikely: most of the string constants do actually see use in the program.

Pushing that part of the lexer's task so late on the off-chance it probably won't be needed IMHO only makes sense if you're writing a parser for an IDE/LSP in which case you don't need to unescape the string at all.

If the string contents are only used at the code-gen stage, then I see that as an argument FOR being lazy.

On the other hand, the principle of validating your input up front suggests that you should at least recognize the escapes, if not store their decoded from.

That is, you can be lazy by only parsing \\ and \" to find the closing quote, and producing 1 token. But that's nearly the same thing as doing a full-decoding. The downsides are that it allows invalid input deeper into the compiler, and it doesn't alert the user to errors as quickly as possible.

most of the string constants do actually see use in the program

[citation needed] :) I don't see how that can possibly hold across languages (Go, Java, Swift, etc.), and I'm not even sure that's true for C/C++.

only makes sense if you're writing a parser for an IDE/LSP in which case you don't need to unescape the string at all.

Clang's front end is used both for LSP and for code gen, so that distinction doesn't apply in all cases. It seems like most projects want to reuse their front ends these days.

And again the LSP will want to warn about invalid escapes like \777 and \u{9999999}.

----

EDIT: Although I guess in C, emitting all the errors up front, and then storing the decoded form in place, is probably about the same cost. If there's no allocation, then I might treat eager decoding as "free".

I think the problem is that you lose info, and most languages have more structure in their string literals, e.g. Swift has \(var) interpolation, and IDEs in Rust want to do things with {} format! strings, etc.

I was wondering the same thing, you can probably mess a bit with the input if you can deal with the drawbacks (which seem mild, pre-processed input might be shorter and column numbers might be off).

What about \n, which decodes to 0x0ah - two bytes to one byte?

I can't think of any others like that, but newline in different OS's get represented in various different ways (like DOS's famous CRLF, which adds an 0x0dh to the recipe). Operating systems that use 0x0ah alone could very well be the only example.

Note that while in your compiler you don't really care about the representation that the OS expect in real files. It's ok for your intermediate, in-memory representation to be meaningless to the OS.

Also, maybe it's not a literal character for character replacement. Since lengths are probably changing, your pre-processed input might be shorter (or longer if you truly need to expand some escaped chars (and you have a program that just wants to break your compiler by abusing that escape sequence :P))

Yes, but some OS's use 0x0ah alone, which is half the bytes of \n representation. People from the 90's will easily remember navigating the ^M (which is the 0x0dh showing up) showing up at the end of every line in a DOS text file when viewing them under a Linux text editor.

This is a different problem around how to interpret new lines from a Windows file (\r\n) or maybe an old Mac version (\n\r to keep things incompatible I guess). If you are not happy with the OS's choice for new lines, you can pre-process that when reading the input as the very first stage. This is what I meant when I said that your compiler doesn't really care about the OS's semantics once the file is in memory, you only need to respect them if you are writing intermediate state to files (like some IR).

The article is talking about how to handle escaped characters in the source, like literal `\n` you can see on `let hi = "Hello\nWorld\nfrom my compiler!"` using your average text editor (0x5c+0x6e in ASCII), and how to build an efficient string type that mostly borrows views from the in-memory version of the source file (which could be a pre-processed version of the raw file if you hate odd line breaks).

FWIW the Classic Mac line ending is \r. \n\r was used by Acorn, apparently.

Before the UNIX had the bright idea to represent newlines as single LFs in disk files and then write a bunch of code in the kernel for the tty driver to convert LF to and from CRLF pairs (which is what ttys actually used), everybody else used CRLF pair to indicate a linebreak. That's why almost all network protocols use CRLF, and not because Microsoft invented the time machine and travelled into the seventies to hinder the UNIX adoption.

> everybody else used CRLF pair to indicate a linebreak

Almost everybody... https://en.wikipedia.org/wiki/Newline#Representation mentions a couple that apparently used LFCR.

Reread the suggestion, you’ve got it back to front:

> no escape sequence is shorter than the text it represents

The idea is that you unescape immediately, and if necessary shuffle the remainder back, leaving a blank space at the end, but able to reuse the initial allocation.

Also, I don’t even know of anything that actually turns a \n into {CARRIAGE RETURN, LINE FEED}; if you want that, you’ll need \r\n. (A very few situations are a bit fuzzy about it, e.g. \r and \n are a bit wonky in Vim’s :substitute, but that’s all I can think of).

Isn't the two byte escape sequence not shorter than the one byte newline?

I do inline replacement of escaped values all the time, because the sequence is always longer than the replacement.

And exponentially shorter with nested escapes.

Reply on news.ycombinator.com