Rust and CSV parsing
blog.burntsushi.net
blog.burntsushi.net
It's pretty cool that Rust's dependency handling is so easy (thanks Cargo!) that even such a single-task library can come with a smaller, even more reusable library inside.
* csv-core doesn't require use of the standard library. (Notably, zero allocations.)
* No use of `unsafe` and it's very very fast.
:-)
The key is that the parser can start and stop at any point in time. So if you give it a fixed size stack allocation and it isn't big enough to hold the data, then `read_field` will return `OutputFull`.[1] At that point, it's up to the caller to figure out what to do. If caller literally cannot dynamically allocate memory at all, then the caller might choose to return an error. Otherwise, the caller might choose to allocate more space and then ask the CSV parser to pick back up where it left off.
With that said, while the `read_field` API is relatively simple, it's actually a bit slower than one would hope because it has to return to the caller every time a single field is read. So there's some overhead there. For that reason, there is also a `read_record` API, which is more complicated to use but is faster and preserves the zero-allocation property. It's faster because it reads an entire record at once.
The higher level `csv` library uses the read_record API[3], and it will expand its allocation when necessary.
The allocation bit isn't terribly important for performance, so long as you can amortize it (which is covered my blog post towards the end). The real trick to making it fast is the DFA. The DFA provides a way to do a very small constant amount of work per byte, which means that the configurability of the CSV parser has zero overhead because it's baked into the DFA. Compare that with the traditional NFA parser[4], and you can see how each state might need to step through multiple conditional checks.
[1] - https://docs.rs/csv-core/0.1.2/csv_core/enum.ReadFieldResult...
[2] - https://docs.rs/csv-core/0.1.2/csv_core/struct.Reader.html#m...
[3] - https://github.com/BurntSushi/rust-csv/blob/34e957e63bb92853...
[4] - https://github.com/BurntSushi/rust-csv/blob/master/csv-core/...
For writing and RFC 4180 compliance, see: https://docs.rs/csv-core/0.1.2/csv_core/struct.Writer.html#r... (The higher level `csv::Writer` will, by default, return an error when writing flexible records. Of course, that can be disabled.)
[1] - https://docs.rs/csv-core/0.1.2/csv_core/struct.Reader.html#r...
Or to put it differently:
"Be conservative in what you send {use RFC4180!}, be liberal in what you accept {parse broken ambiguous csv that was ignorant of RFC4180}." -- from the https://en.wikipedia.org/wiki/Robustness_principle
It also doesn't help that RFC4180 is dated 2005 which is trying to enforce a standard 20 to 30 years after csv files have been created adhoc in the wild without a formal specification.
A slight variation on this is important for security. Be liberal in what you accept, but define what "liberal" means. It's important to define what counts as a valid input. If you don't have a validation/recognizer verify that the input is acceptable, you are probably creating a "weird machine"[1] waiting to be exploited in ways you didn't expect.
I highly recommend Meredith and Sergey's talk[2][3] at 28c3, "The Science of Insecurity", where they explain this from a language-theoretic perspective.
[1] http://www.cs.dartmouth.edu/~sergey/wm/
[2] https://media.ccc.de/v/28c3-4763-en-the_science_of_insecurit...
[3] http://www.cs.dartmouth.edu/~sergey/langsec/insecurity-theor...
But even without getting crazy, simple line endings end up being a security issue. Some treat LF like CRLF. Or CRCR as a single line break. So you end up with a setup where your SIP or HTTP proxy will interpret a message one way, and your server interprets it differently. This lets you exploit things by sneaking in headers that your proxy would otherwise deny.
<line-ending> ::= "\r\n" | "\n"
> This lets you exploit things by sneaking in headers
In the talk at my previous [2][3], Serge specifically mentions Travis Goodspeed's packet-in-packet[4] exploit as an example of why you have to define what "liberal" means if you want to implement Postel's principle. (You should also limit input grammar's complexity to deterministic context-free, or the recognizer will be undecidable)
> in practice has made things a nightmare
That's what [2][3] is trying to fix. Stop using Turing Complete input languages, explicitly define your input grammar no matter what you're choosing to parse, and formally recognize all input against that grammar. The data either matches the defined grammar or it should be failed as invalid. Any allowances for sloppy input must be baked into that process.
[4] http://travisgoodspeed.blogspot.com/2011/09/remotely-exploit...
extern crate csv;
fn main() {
let mut rdr = csv::ReaderBuilder::new()
.has_headers(false)
.from_reader("abc,foo\"baz,xyz".as_bytes());
println!("{:?}", rdr.records().collect::<Result<Vec<_>, _>>().unwrap());
}
[StringRecord(["abc", "foo\"baz", "xyz"])]
>>> import csv
>>> list(csv.reader(['abc,foo"baz,xyz']))
[['abc', 'foo"baz', 'xyz']]
You've got it all backwards.
The people writing parsers are the ones who need a language specification to decide what to parse, what to ignore, and what to consider errors.
Meanwhile, writing CSV docs is just a for loop with a printf. That's it.
If an old 1970s mainframe is spitting out "broken" csv files that you need to parse, a new 2005 csv formal specification trying to impose some sanity to the landscape is irrelevant. That short RFC4180 tries to constrain what is "correct". It can't enumerate all the ways csv files are "incorrect".[1] The programmer has to look at the actual bad csv files he's trying to parse. As of today, Citi bank still exports broken csv for credit-card transactions. (Citi inserts extra CRLF in between quotes which breaks MS Excel csv import.) I don't need a formal spec telling me how it's broken. It's quite obvious by simply viewing it in Notepad.
>Meanwhile, writing CSV docs is just a for loop with a printf. That's it.
No. For example, if the field has a movie title with embedded quotes[2] or maybe a measurement using a one double quote for inches (e.g. [Sony 4k TV 65"])[3], using a naïve printf loop without generating extra escape characters will break many csv parsers that try to conform to RFC4180.
[1] although someone did try to enumerate bad csv files: https://donatstudios.com/Falsehoods-Programmers-Believe-Abou...
[2] example movie title [Precious: Based on the Novel "Push" by Sapphire] : https://en.wikipedia.org/wiki/Precious_(film)
[3] https://stackoverflow.com/questions/17808511/properly-escape...
...then that mainframe outputs data following a different document format, one that doesn't comply with the language defined by the standard.
If you need to parse a language, you target a language. You can't simply write a document in english and call it mandarin.
> No. For example, if the field has a movie title with embedded quotes[2]
...then you escape the quotes, and proceed to printf each field.
Is it that hard?
Yes, and so what? Stating RFC4180 as a retroactive fact isn't going to make the job get done.
Again, look at the date of RFC4180.[1] It is October 2005. There have been millions of csv files made for decades before that pseudo-standard even existed. (Yes, RFC4180 is not even a formal specification -- it is a pseudo-specification trying to codify the most prevalent and sane existing practices.)
The programmer still has to parse all the bad pre-2005 csv files so making the parsing dependent on RFC4180 is irrelevant.
Even today, the Citi bank cc transactions export to csv is _not_ RFC4180 compliant. So what? I still have to parse it.
Getting pedantic about noncompliant csv files not following RFC4180 is not productive for the task at hand. The programmer trying to parse them doesn't control the other entities that produce bad csv files.
>Is it that hard?
The conversation is not about difficulty. It is about where in the workflow a pseudo-standard like RFC4180 is most applicable: the writing of output not parsing of input.
I think this thread can be summarized simply as: "In theory, theory and practice are the same. In practice, they're completely different."
In theory, adhering to the CSV specification strictly is the Right Thing to Do. It's simple and makes it easy to confirm that the data you're parsing is correct.
But in practice, that all goes out the window. There are few things worse than running your CSV data through the standard parser and discovering that a smattering of fields contain stray quotes. And what do you get for that? The entire parser falls over and you can't do anything until you go in and fix the data. Or, if we're to believe other users in this thread, until someone goes and writes a specialty parser just for this task to fix the data.
In practice, CSV data is messy and therefore a strictly conforming parser tends to be incredibly annoying to use. IMHO, the authors of RFC 4180 failed to recognize this. As a result, most people just ignore it.
Exactly, and obviously it's in writing a parser.
Outputting CSV files is essentially a call to printf in a for loop. If a string needs escaping, the string is escaped. It's as simple as it gets.
It only gets complicated when you need to write a parser and handle stuff such as how to parse language violations.
No, you've got that wrong but I think I see the underlying issue. You believe that the suggested RFC4180 by is a formal language spec such that you have an exact BNF grammar. Therefore, parsing is a binary result: csv validity is either true or false.
This is why you believe RFC4180 is a guide to parsing. But this is wrong.
Unfortunately, the evolution of csv isn't like languages with official specs such as ISO C++ standard, or ECMAScript, or HTML.
> and handle stuff such as how to parse language violations.
...which renders RFC4180 useless for real-world parsing.
The supreme authority of usefully parsing csv is the actual csv file you have to deal with. That file supersedes anything RFC4180 says. Why? Because business people want the data in those broken and non-compliant csv files!
This is the opposite situation with parsing source code like C++ and Javascript: the broken source doesn't dictate the correct parsing, the language spec does.
With csv, the data itself (broken or not) is what drives the parsing. There is no "true/false compliant" parse. Instead, assume every csv row with incorrect commas and double quotes is parseable and write the parser to handle it no matter what RFC4180 says. An "error in csv" is not the same treatment as an "error in C/C++ source file".
Since programmers have to overrule RFC4180 to get useful data, the spec can't be obeyed for real-world parsing. The permissive-parsers are more useful than RFC4180-parsers that don't know how to handle broken csv.
This makes RFC4180 much more realistic to guide the output of csv. This is especially true if the programmer is aware of that pseudo-specification after October 2005.
This is why you have RFC4180's usefulness in the workflow backwards. An RFC4180-compliant-writer is much more useful than an RFC4180-compliant-reader. There are csv files that MS Excel can successfully import that a strict RFC4180-parser cannot handle.