7 ms·

I've implemented a new HTTP/1.1 request and response parser by hand

79 points by fogus 17y ago

bumblebird 17y ago
By hand??? As opposed to what exactly? Isn't most code written by hand?
- ionfish 17y ago
  As opposed to using Ragel, as you'd have known if you'd read the link.
  - bumblebird 17y ago
    The title is "I've implemented a new HTTP/1.1 request and response parser by hand" My question was, how do you implement a new HTTP/1.1 request and response parser if it's not by hand. Isn't most code written using hands? I've written one too... big whoop. Meh anyway...
    - viraptor 17y ago
      Most parsers nowadays are generated via yacc and others. You write the structure, yacc generates the parser (and flex the lexer). It's something completely different if you write the parser yourself.
      - bumblebird 17y ago
        It was just a bit surprising to me. Parsing HTTP isn't exactly complex.
        ryah 17y ago
        clearly you're unfamiliar with http.
        bumblebird 17y ago
        I certainly am. It's a complete mystery to me. Is it like visual basic? The only PITA with HTTP is chunked encoding. Whoever thought that gem up should be shot. The rest is fairly trivial. Certainly parsing headers is. This implementation looks pretty silly. Having individual states for each of the characters in "HTTP" etc? WTF? edit: Instead of just downmodding me, why not explain exactly what part of parsing HTTP headers is non trivial?
        viraptor 17y ago
        The parser correctness is not trivial. The RFC2616 contains the complete grammar you need, so it's fairly simple to implement. OTOH, if you write a parser on your own, you're likely to miss stuff like section 4.2, which explains that header values can be multiline if they include LWS. The parser from this article will fail on (just looking at the source, I'm 99.5% sure of this): abc: def It also doesn't like tabs and will not support comma-separated header values. It's not rocket science to write a "good enough" http parser, but writing a fully compliant one is something completely different. There are also cool parts of the spec that you can read 10 times and come to different conclusions - for example what does the "\" CR LF section mean if it's inside a quoted string and does it finish the header value or not. Writing a "correct" parser is a LOT of fun... Keeping separate states for characters in HTTP saves you a couple of cycles probably, because you match as you go and can reject the message early and with the exact place that didn't match. It's a bit useless for a 4-letter string though.
viraptor 17y ago
For a couple of reasons this code doesn't look like a very reliable one... Almost identical cases don't reuse code (not even a define). There are also sections like "`if (usual[ch >> 5] & (1 << (ch & 0x1f))) break;`" without any comments. The code hardcodes the http methods for some reason so that the detection code spans ~130 lines (454..580). Looks like it will accept "HXXX/1.1" if strict checking is off. This double check is... interesting: if (!parser->FOR##_mark) return 0; \ assert(parser->FOR##_mark); \ Sure - speed++, but at what cost? Otherwise... cool code - I like the MARK / CALLBACK macros.
- jerf 17y ago
  "I can make it arbitrarily fast if I don't actually have to make it work": http://blogs.msdn.com/larryosterman/archive/2009/09/29/i-can-make-it-arbitrarily-fast-if-i-don-t-actually-have-to-make-it-work.aspx http://blogs.msdn.com/larryosterman/archive/2009/09/29/i-can...
  - nostrademons 17y ago
    I'm disappointed that the student who hardcoded the results was disqualified. You should get points for finding bugs in your professors' specification.
    - Confusion 17y ago
      The student missed the most important part of the spec: the intent. 99 Out of a 100 times, you aren't implementing a rigorous spec. The ability to understand what is requested is much more important than the ability to be a wise-ass.
      - viraptor 17y ago
        > 99 Out of a 100 times, you aren't implementing a rigorous spec. I'd argue that most programmers do, or are supposed to. Either because they are not the designers of the system they build and what they are expected to do is to "fill in the blanks and make it work", or because they implement something that operates with another system and should strictly adhere to the interface/protocol. The ones who have anything to say about the design are usually the system designers (duh), small project contributors (because there is no spec) and UI people (because they're designers). So yes - if your spec is "1. make it work on this input; 2. make it fast", then making it work in O(1) for this and only this input is basically the best thing you can do (unless you can make it faster for every input in less time of course). Spending time on generalising it is based on second-guessing the intent. I'd even go as far as saying that specs have absolutely no intent. You have an intent and describe it while writing the spec and you'd better formalise your intent precisely or you will end up with something you didn't request. If you want something on every input, you'd better write it down (when you give a task to someone else).
snorkel 17y ago
Clever use of ## in preprocessor directives. http://en.wikipedia.org/wiki/C_preprocessor http://en.wikipedia.org/wiki/C_preprocessor
rglullis 17y ago
I need to dig through my old computer and find my college lab assignments where we built a basic HTTP/1.1 server. For the request parser, we had to create a lex file for a grammar that include actions for all of the verbs, and also be robust to accept non-standard verbs, i.e, return a 400 code. I doubt that my yacc'd program would be only 124 bytes in size, but it would be interesting to get that old code and compare the results.
brianobush 17y ago
At my company we rolled our own too. The hard part was tracking down all the brain-dead servers that seemingly worked fine with browsers, but were off spec.
- jacobolus 17y ago
  Are there any good sets of HTTP compatibility tests which test deviations from the spec which show up in existing servers/browsers?
  - wmf 17y ago
    http://coad.measurement-factory.com/ http://coad.measurement-factory.com/ Warning: not free.
xal 17y ago
It has also been merged into node. This thing is starting to be a case study for optimized C network servers.
pquerna 17y ago
I thought it was a pretty cool implementation (zero memory alloc is pretty hard most of the time), though I was disappointed how HTTP methods were hard coded in, so adding a new HTTP method (like PROPFIND?) would be adding a ton of code, though I think you could make a few macros for doing HTTP methods and keep the rest of it.
- davisp 17y ago
  Hacked together an on_method callback last night for the Python bindings I'm writing: http://github.com/davisp/http-parser/commit/50e54f95fd4c2eac59d669ef5e9e0e8b61a0955d http://github.com/davisp/http-parser/commit/50e54f95fd4c2eac...

79 points by fogus 17y ago

bumblebird 17y ago

By hand??? As opposed to what exactly? Isn't most code written by hand?

ionfish 17y ago
As opposed to using Ragel, as you'd have known if you'd read the link.
- bumblebird 17y ago
  The title is "I've implemented a new HTTP/1.1 request and response parser by hand" My question was, how do you implement a new HTTP/1.1 request and response parser if it's not by hand. Isn't most code written using hands? I've written one too... big whoop. Meh anyway...
  - viraptor 17y ago
    Most parsers nowadays are generated via yacc and others. You write the structure, yacc generates the parser (and flex the lexer). It's something completely different if you write the parser yourself.
    - bumblebird 17y ago
      It was just a bit surprising to me. Parsing HTTP isn't exactly complex.
      - ryah 17y ago
        clearly you're unfamiliar with http.
        bumblebird 17y ago
        I certainly am. It's a complete mystery to me. Is it like visual basic? The only PITA with HTTP is chunked encoding. Whoever thought that gem up should be shot. The rest is fairly trivial. Certainly parsing headers is. This implementation looks pretty silly. Having individual states for each of the characters in "HTTP" etc? WTF? edit: Instead of just downmodding me, why not explain exactly what part of parsing HTTP headers is non trivial?
        viraptor 17y ago
        The parser correctness is not trivial. The RFC2616 contains the complete grammar you need, so it's fairly simple to implement. OTOH, if you write a parser on your own, you're likely to miss stuff like section 4.2, which explains that header values can be multiline if they include LWS. The parser from this article will fail on (just looking at the source, I'm 99.5% sure of this): abc: def It also doesn't like tabs and will not support comma-separated header values. It's not rocket science to write a "good enough" http parser, but writing a fully compliant one is something completely different. There are also cool parts of the spec that you can read 10 times and come to different conclusions - for example what does the "\" CR LF section mean if it's inside a quoted string and does it finish the header value or not. Writing a "correct" parser is a LOT of fun... Keeping separate states for characters in HTTP saves you a couple of cycles probably, because you match as you go and can reject the message early and with the exact place that didn't match. It's a bit useless for a 4-letter string though.

viraptor 17y ago

For a couple of reasons this code doesn't look like a very reliable one... Almost identical cases don't reuse code (not even a define). There are also sections like "`if (usual[ch >> 5] & (1 << (ch & 0x1f))) break;`" without any comments. The code hardcodes the http methods for some reason so that the detection code spans ~130 lines (454..580). Looks like it will accept "HXXX/1.1" if strict checking is off. This double check is... interesting: if (!parser->FOR##_mark) return 0; \ assert(parser->FOR##_mark); \ Sure - speed++, but at what cost? Otherwise... cool code - I like the MARK / CALLBACK macros.

jerf 17y ago
"I can make it arbitrarily fast if I don't actually have to make it work": http://blogs.msdn.com/larryosterman/archive/2009/09/29/i-can-make-it-arbitrarily-fast-if-i-don-t-actually-have-to-make-it-work.aspx http://blogs.msdn.com/larryosterman/archive/2009/09/29/i-can...
- nostrademons 17y ago
  I'm disappointed that the student who hardcoded the results was disqualified. You should get points for finding bugs in your professors' specification.
  - Confusion 17y ago
    The student missed the most important part of the spec: the intent. 99 Out of a 100 times, you aren't implementing a rigorous spec. The ability to understand what is requested is much more important than the ability to be a wise-ass.
    - viraptor 17y ago
      > 99 Out of a 100 times, you aren't implementing a rigorous spec. I'd argue that most programmers do, or are supposed to. Either because they are not the designers of the system they build and what they are expected to do is to "fill in the blanks and make it work", or because they implement something that operates with another system and should strictly adhere to the interface/protocol. The ones who have anything to say about the design are usually the system designers (duh), small project contributors (because there is no spec) and UI people (because they're designers). So yes - if your spec is "1. make it work on this input; 2. make it fast", then making it work in O(1) for this and only this input is basically the best thing you can do (unless you can make it faster for every input in less time of course). Spending time on generalising it is based on second-guessing the intent. I'd even go as far as saying that specs have absolutely no intent. You have an intent and describe it while writing the spec and you'd better formalise your intent precisely or you will end up with something you didn't request. If you want something on every input, you'd better write it down (when you give a task to someone else).

snorkel 17y ago

Clever use of ## in preprocessor directives. http://en.wikipedia.org/wiki/C_preprocessor http://en.wikipedia.org/wiki/C_preprocessor

rglullis 17y ago

I need to dig through my old computer and find my college lab assignments where we built a basic HTTP/1.1 server. For the request parser, we had to create a lex file for a grammar that include actions for all of the verbs, and also be robust to accept non-standard verbs, i.e, return a 400 code. I doubt that my yacc'd program would be only 124 bytes in size, but it would be interesting to get that old code and compare the results.

brianobush 17y ago

At my company we rolled our own too. The hard part was tracking down all the brain-dead servers that seemingly worked fine with browsers, but were off spec.

jacobolus 17y ago
Are there any good sets of HTTP compatibility tests which test deviations from the spec which show up in existing servers/browsers?
- wmf 17y ago
  http://coad.measurement-factory.com/ http://coad.measurement-factory.com/ Warning: not free.

xal 17y ago

It has also been merged into node. This thing is starting to be a case study for optimized C network servers.

pquerna 17y ago

I thought it was a pretty cool implementation (zero memory alloc is pretty hard most of the time), though I was disappointed how HTTP methods were hard coded in, so adding a new HTTP method (like PROPFIND?) would be adding a ton of code, though I think you could make a few macros for doing HTTP methods and keep the rest of it.

davisp 17y ago
Hacked together an on_method callback last night for the Python bindings I'm writing: http://github.com/davisp/http-parser/commit/50e54f95fd4c2eac59d669ef5e9e0e8b61a0955d http://github.com/davisp/http-parser/commit/50e54f95fd4c2eac...