5 ms·

Rust and CSV parsing

95 points by burntsushi 9y ago

userbinator 9y ago
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.
- burntsushi 9y ago
  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#rfc-4180 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#rfc-4180 https://docs.rs/csv-core/0.1.2/csv_core/struct.Reader.html#r... [2] - https://github.com/BurntSushi/rust-csv/issues/77 https://github.com/BurntSushi/rust-csv/issues/77
- jasode 9y ago
  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 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.
  - pdkl95 9y ago
    > 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/ http://www.cs.dartmouth.edu/~sergey/wm/ [2] https://media.ccc.de/v/28c3-4763-en-the_science_of_insecurity https://media.ccc.de/v/28c3-4763-en-the_science_of_insecurit... [3] http://www.cs.dartmouth.edu/~sergey/langsec/insecurity-theory-28c3.pdf http://www.cs.dartmouth.edu/~sergey/langsec/insecurity-theor...
    - MichaelGG 9y ago
      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.
      - pdkl95 9y ago
        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 <line-ending> ::= "\r\n" | "\n" to your input grammar, and properly recognize that the input matches that grammar before using any parsed values. It's an extension ("being liberal") to the official spec, but still strictly defined in the implemented parser. > 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-exploiting-phy-layer.html http://travisgoodspeed.blogspot.com/2011/09/remotely-exploit...
pornel 9y ago
> If you wanted to build your own csv-like library, you could build it on top of csv-core. 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.
- burntsushi 9y ago
  AND... * csv-core doesn't require use of the standard library. (Notably, zero allocations.) * No use of `unsafe` and it's very very fast. :-)
  - _ar7 9y ago
    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 https://github.com/AriaFallah/csv-parser
    - burntsushi 9y ago
      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#method.read_field 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.html 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#method.read_record https://docs.rs/csv-core/0.1.2/csv_core/struct.Reader.html#m... [3] - https://github.com/BurntSushi/rust-csv/blob/34e957e63bb92853ba32c314f613d948e8a3c012/src/reader.rs#L1554-L1588 https://github.com/BurntSushi/rust-csv/blob/34e957e63bb92853... [4] - https://github.com/BurntSushi/rust-csv/blob/master/csv-core/src/reader.rs#L928 https://github.com/BurntSushi/rust-csv/blob/master/csv-core/...
tankfeeder 9y ago
csv parsing on PicoLisp: https://bitbucket.org/mihailp/tankfeeder/src/5a91a025d78eacf68655b6dbec5c2dd346624146/csv.l?at=default&fileviewer=file-view-default https://bitbucket.org/mihailp/tankfeeder/src/5a91a025d78eacf...
chaosfox 9y ago
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

95 points by burntsushi 9y ago

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.

burntsushi 9y ago
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#rfc-4180 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#rfc-4180 https://docs.rs/csv-core/0.1.2/csv_core/struct.Reader.html#r... [2] - https://github.com/BurntSushi/rust-csv/issues/77 https://github.com/BurntSushi/rust-csv/issues/77
jasode 9y ago
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 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.
- pdkl95 9y ago
  > 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/ http://www.cs.dartmouth.edu/~sergey/wm/ [2] https://media.ccc.de/v/28c3-4763-en-the_science_of_insecurity https://media.ccc.de/v/28c3-4763-en-the_science_of_insecurit... [3] http://www.cs.dartmouth.edu/~sergey/langsec/insecurity-theory-28c3.pdf http://www.cs.dartmouth.edu/~sergey/langsec/insecurity-theor...
  - MichaelGG 9y ago
    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.
    - pdkl95 9y ago
      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 <line-ending> ::= "\r\n" | "\n" to your input grammar, and properly recognize that the input matches that grammar before using any parsed values. It's an extension ("being liberal") to the official spec, but still strictly defined in the implemented parser. > 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-exploiting-phy-layer.html http://travisgoodspeed.blogspot.com/2011/09/remotely-exploit...

pornel 9y ago

> If you wanted to build your own csv-like library, you could build it on top of csv-core. 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.

burntsushi 9y ago
AND... * csv-core doesn't require use of the standard library. (Notably, zero allocations.) * No use of `unsafe` and it's very very fast. :-)
- _ar7 9y ago
  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 https://github.com/AriaFallah/csv-parser
  - burntsushi 9y ago
    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#method.read_field 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.html 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#method.read_record https://docs.rs/csv-core/0.1.2/csv_core/struct.Reader.html#m... [3] - https://github.com/BurntSushi/rust-csv/blob/34e957e63bb92853ba32c314f613d948e8a3c012/src/reader.rs#L1554-L1588 https://github.com/BurntSushi/rust-csv/blob/34e957e63bb92853... [4] - https://github.com/BurntSushi/rust-csv/blob/master/csv-core/src/reader.rs#L928 https://github.com/BurntSushi/rust-csv/blob/master/csv-core/...

tankfeeder 9y ago

csv parsing on PicoLisp: https://bitbucket.org/mihailp/tankfeeder/src/5a91a025d78eacf68655b6dbec5c2dd346624146/csv.l?at=default&fileviewer=file-view-default https://bitbucket.org/mihailp/tankfeeder/src/5a91a025d78eacf...

chaosfox 9y ago

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