Rust and CSV parsing(blog.burntsushi.net)
blog.burntsushi.net
Rust and CSV parsing
http://blog.burntsushi.net/csv/
23 comments
AND...
* csv-core doesn't require use of the standard library. (Notably, zero allocations.)
* No use of `unsafe` and it's very very fast.
:-)
* csv-core doesn't require use of the standard library. (Notably, zero allocations.)
* No use of `unsafe` and it's very very fast.
:-)
Could you elaborate on the zero allocation part? I made a CSV parser based on yours [0] before the 1.0.0-beta rewrite, and at the very least I have to allocate as much memory to hold a single field in the CSV (and then reuse that memory).
[0]: https://github.com/AriaFallah/csv-parser
[0]: https://github.com/AriaFallah/csv-parser
It's an iterator, so the parser will parse fields from the already-allocated raw CSV string and yield them to you as it reads them as slices borrowed from the string. It's up to you to store them in whatever structured format you want.
The `csv` crate uses allocation, but `csv-core` does not. I think it would help if you looked at the `read_field` API in `csv-core`: https://docs.rs/csv-core/0.1.2/csv_core/struct.Reader.html#m...
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/...
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/...
I've looked through all the docs and there is no mention of RFC4180 compliance? That's one of the things a lot of people looking for a CSV library would consider highly.
It's buried in the docs of csv-core[1], mostly because it's rarely useful in my experience. But it's a good question, so it probably should be featured more prominently. The implementation follows in the footsteps of Python's CSV parser, where it prefers a parse over returning an error. I'd like to add a strict mode[2], but I haven't perceived much demand for it.
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...
[2] - https://github.com/BurntSushi/rust-csv/issues/77
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...
[2] - https://github.com/BurntSushi/rust-csv/issues/77
RFC4180 is more helpful to generate correct CSV files. It's not as useful for parsing files since many (most?) csv writers will not have followed RFC4180 in the first place.
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.
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.
> Robustness_principle
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...
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...
Except that's not an interpretation of liberal anyone uses. That'd just be "by the spec". The robustness principle in practice has made things a nightmare. Consider SIP and HTTP. SIP explicitly encourages implementers to guess at the meaning of messages, and delights in how complicated their parsing rules are.
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.
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.
The point is it's important to define a new spec if you are being "liberal" in what you accept. For example, while RFC 4180 defines line endings as CRLF, it might be reasonable to "be liberal" and accept files with just LF if and only if you add a rule similar to
> 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...
<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...
I've saved myself a number of headaches by taking the opposite approach and being conservative in what I accept: I ignore the quoting rules. Comma or newline in the middle of your field? Malformed. Double-quote by itself in the middle of your field? Fine by me. Most of the weird stuff comes from Excel anyway, and I have a reader for Excel files that tolerates those things just fine. My users are happy with it because I've removed a source of ambiguity for them. My users are also highly technical, so I can get away with this sort of thing.
There's a certain amount of that in my CSV library as well, which is strongly influenced by Python's standard library `csv` behavior. Example:
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']]
> RFC4180 is more helpful to generate correct CSV files. It's not as useful for parsing files
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.
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.
>The people writing parsers are the ones who need a language specification to decide what to parse,
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...
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...
> If an old 1970s mainframe is spitting out "broken" csv files
...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?
...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?
>...then that mainframe outputs data following a different document format, one that doesn't comply with the language defined by the standard.
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.
[1] https://tools.ietf.org/html/rfc4180
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.
[1] https://tools.ietf.org/html/rfc4180
Agreed.
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.
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.
> The conversation is not about difficulty. It is about where in the workflow a pseudo-standard like RFC4180 is most applicable:
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.
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.
>Exactly, and obviously it's in writing a parser.
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.
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.
Make the parser RFC compliant. Use a separate tool for normalizing the broken cave files to RFC compliant.
don't forget to checkout xsv !
its the missing piece between standard unix tools and SQL, I love it.
https://github.com/BurntSushi/xsv
https://github.com/BurntSushi/xsv
csv parsing on PicoLisp:
https://bitbucket.org/mihailp/tankfeeder/src/5a91a025d78eacf...
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.