Google Open-Sources Gumbo: C Library for Parsing HTML5

https://github.com/google/gumbo-parser#gumbo---a-pure-c-html5-parser

by bryanh • 13 years ago

262 59 13 years ago

bryanh2• 13 years ago

I would be quite interested in Gumbo as the backend to the awesome pure Python but otherwise rather-slow https://github.com/html5lib/html5lib-python, which actually has great whitelisting/cleaning facilities but is easily an order of magnitude slower than lxml's more limited clean_html.

PyPy JIT and html5lib is about 8x faster as it is cpython.

voltagex_• 13 years ago

From a quick glance, it looks like you'd need to make Gumbo a backend for lxml. Is that even possible?

bryanh2• 13 years ago

https://github.com/html5lib/html5lib-python/issues/105 seems to imply that such a thing is possible. I am unsure about the requirement for lxml. I was under the impression that lxml is an optional walker, the default is the slower pure python walker.

nostrademons10• 13 years ago

Gumbo's Python wrapper should be a drop-in replacement for html5lib. Just replace

     import html5lib

with

     from gumbo import html5lib

The tree generated from gumbo.html5lib.HTMLParser should be API-compatible with the one generated by html5lib.HTMLParser. (Possibly modulo some minor features...html5lib's maintainer has filed a bug about implementing treewalkers in the html5lib adaptor.)

I'm not sure offhand what the speed would be - I'd imagine the Gumbo backend would be significantly faster than html5lib by virtue of being written in C, but speed was not a design goal, and so I suspect it's currently significantly slower than lxml. What Gumbo gives you over lxml is HTML5 compatibility - lxml does an HTML4-approximate parse.

gsnedders3• 13 years ago

Well, differences off hand compared with html5lib:

- Byte strings (opposed to Unicode ones) have encoding sniffed and parsed according to that in html5lib whereas they're all handled as UTF-8 in Gumbo.

- There's a namespaceHTMLElements option in html5lib which avoids putting HTML elements in the HTML namespace, useful for some legacy HTML processing tools.

- html5lib can read directly from a file object, which might in extreme cases be a useful memory saving (though the parse tree will likely use 100x the amount of memory anyway), but perhaps is more useful when dealing with network streams (it doesn't block waiting for all the data before starting to parse).

- html5lib supports fragment parsing, as is used by innerHTML.

Otherwise, given it takes a normal html5lib tree builder, it should support almost everything else (the tree walkers, albeit with indirection from Gumbo's own representation of the tree, and related stuff like the serialiser).

Compared with libxml2, it provides what is likely a better tested parse algorithm (ultimately, libxml2's is just a few bits of error handling of the non-fatal type in the libxml2 parser with a few bits of variant behaviour. I know the experience of HubHub's author was it had a fair few bad bugs like infinite loops and the like, as well as radically different behaviour to any browser and what most web authors expect to get.

Speed wise, quickly trying to appears to be a few times quicker than html5lib under PyPy and an order of magnitude quicker under CPython. This will likely differ with the input given.

Smerity• 13 years ago

They already provide adapters for standard Python HTML parsing libraries[1], specifically html5lib and BeautifulSoup. This is how they suggest it be used with Python[2].

[1] https://github.com/google/gumbo-parser/tree/master/python/gu...

[2] https://github.com/google/gumbo-parser#python-usage

sanxiyn• 13 years ago

How does this compare to Hubbub, another C library for parsing HTML5?

http://www.netsurf-browser.org/projects/hubbub/

nostrademons10• 13 years ago

From a cursory glance at the Hubbub source:

1. Hubbub provides a SAX-style (callback-based) API, while Gumbo gives you a DOM-style (tree-based) struct directly. Hubbub is likely faster in this regard, Gumbo is easier to use out-of-the-box.

2. Gumbo is better tested. It's unclear whether Hubbub's 90% test coverage is "90% of the code is tested" or "90% of the tests pass", but Gumbo has 100% code coverage, 100% of html5lib tests pass (as of 0.95; the html5lib maintainer has pointed out that additional tests were added to trunk recently that don't pass), and it's run without crashing on ~4.5B documents from Google's index.

3. Gumbo has better support for source locations and going between original text and parse tree.

4. Hubbub has character encoding detection, Gumbo doesn't.

eliasmacpherson4• 13 years ago

Have you seen this before? http://vtd-xml.sourceforge.net/faq.html#How_do_I_get_started...

It's an xml parser that is neither DOM nor SAX. I haven't seen much mention of it before, except as a recommendation for Java devs. There's a C version too. It makes bold claims about performance.

"Comparing with DOM, VTD-XML is significantly faster (up to 10x), more memory-efficient (up to 5x).

Comparing with SAX/PULL, VTD-XML is not only faster, but also is capable of random-access, therefore is easier to use."

Basically by building a DOM style model in SAX fashion.

thejosh• 13 years ago

A good thing about developing tools at Google is the access to test data with their index.

The line:

  Tested on over 2.5 billion pages from Google's index.

That's quite awesome, and would cover quite a few edge cases.

tlb• 13 years ago

Indeed, although anyone can also get 3.8 billion pages from CommonCrawl.

http://commoncrawl.org/a-look-inside-common-crawls-210tb-201...

mikkelewis• 13 years ago

Although not anyone can crawl 2+ billion pages AND fix all the crazy edge cases without going insane :)

faddotio2• 13 years ago

And anyone can pay for the EC2 instances to test all 3.8B pages!

frik• 13 years ago

Are there plans to add bindings for PHP? Would be awesome.

nostrademons10• 13 years ago

I don't have plans to. It's an open-source library, though, so there's nothing stopping an enterprising programmer familiar with PHP extensions to add some herself. That's what Gumbo was designed for: to serve as a building block for other tools.

Goranek• 13 years ago

any chance to open source DOM too? Thug made a solid DOM with pyV8 but still not 100% compatible as far as i know.

soulclap• 13 years ago

Hopefully someone will get busy on that. Great project!

pokoleo• 13 years ago

I think the big move here is that they didn't publish it to their own http://code.google.com site.

plg• 13 years ago

This is interesting isn't it. To their credit, perhaps, they posted it to the place where it will get the most exposure.

tvon• 13 years ago

They post quite a bit to GitHub: https://github.com/google/

xedarius• 13 years ago

Nice to see they've written the parser from scratch rather than some BISON and FLEX construct that generates impenetrable code.

idlewan• 13 years ago

Just like with any generated code, you are not supposed to read the code bison and flex generate (except maybe if you are a flex/bison developer). 'Impenetrable' is neither an advantage nor a disadvantage of generated code.

Do you often read the output of some library macros that the C pre-compiler generates?

munificent• 13 years ago

Do you often read the output of some library macros that the C pre-compiler generates?

I do when they have bugs in them. :(

ksec• 13 years ago

Um... Incoming Naive Questions.

Why do we need yet another HTML5 Parser? What's wrong with Webkit? What's wrong with the new Gecko2 HTML5 parser?

And what license is it?

felixge• 13 years ago

License is Apache 2: https://github.com/google/gumbo-parser/blob/master/COPYING

venomsnake• 13 years ago

Because WebKit and Gecko are not only parsers for starters. They are much more complex layout engines. Which is a whole other can of worms.

mjn• 13 years ago

The new Gecko parser is based on a Java->C++ translation from this standalone parser: http://about.validator.nu/htmlparser/

jgraham• 13 years ago

A standalone parser written in C is a great asset. Pretty much any language worth mentioning has C bindings, so they are now just a bindings implementation away from having a reasonably fast (the fact that performance was a non-goal notwithstanding), standards compliant HTML parser. This is an improvement over the status-quo where most languages have bindings to lxml which is fast but has made-up error handling and a tendency to deal poorly with quite a lot of content, and some languages have slow, native implementations of the HTML standard parsing algorithm (I wrote much of Python's html5lib so I am aware both that it is slow and that it is non-trivial to speed up).

Compared to Gecko and WebKit, this gives you just the parser, which is significantly simpler than the whole engine and all you want for many applications.

cliveowen• 13 years ago

I'm very excited because even though is useless for me is an enough small project to actually learn something of C programming...and from Google no less.

clarry• 13 years ago

Coming from Google doesn't mean it's good code to learn from. Be careful not to pick up bad (and potentially disasterous, security-wise) habits like not checking for arithmetic overflows in functions such as enlarge_vector_if_full (vector.c) or maybe_resize_string_buffer (string_buffer.c) -- or not checking the return value from malloc.

nostrademons10• 13 years ago

You could file bugs for these rather than posting them in a comment thread that will likely be soon forgotten.

jbrooksuk2• 13 years ago

Node.js bindings would be awesome, especially for writing a headless website parser.

I just forked Gumbo and gave it a shot, but my limited experience of v8 didn't get me very far. I was able to create and build a basic plugin, but returning the scope with a Gumbo object was beyond my limited capabilities.

I think as a little side project I may continue to work on this.

joshguthrie• 13 years ago

Nice idea, give the repo an I'll give it a push =)

jbrooksuk2• 13 years ago

Currently it's just a straight fork - https://github.com/jbrooksuk/gumbo-parser

I'm giving it another crack now.

You can see my first attempt at https://github.com/jbrooksuk/gumbo-parser/commit/d64f78b125f... - unfortunately it's not quite there. I can't figure out how to send back the struct created by Gumbo.

swah• 13 years ago

Can you comment on why this is C and not C++? (Although some examples are in C++)

desas• 13 years ago

It's very easy to re-use C code in most other languages.

wtetzner• 13 years ago

Sure, but why not write in C++ and just expose a C interface?

johnbellone• 13 years ago

If you are writing this as a library you're most likely going to end up having to write a C wrapper for most language bindings. In the end it may just be easier to write the whole library in C and then write the specific binding for Python, Ruby, etc.

nostrademons10• 13 years ago

https://news.ycombinator.com/item?id=6213558

avian• 13 years ago

I'm curious as to what was the motivation behind this project at Google. It seems to me that the only benefit of writing something like this in pure C would be performance gains over existing parsers, but it specifically says in the README that parsing performance was not one of the goals.

jasonwocky• 13 years ago

Most languages can be extended by C code without too much fuss. If the C is written in a platform-independent manner (which should be possible for this library), it's pretty much write-once, run-anywhere. Even if optimal performance wasn't a goal, it's still nice to have a single portable, performant html5 parser that's been tested against billions of pages.

nostrademons10• 13 years ago

It actually arose out of a templating language project within Google, which was written in C++. We evaluated the existing C/C++ parsers (which at the time were Webkit, the auto-generated port of validator.nu, and another Google-internal parser - we didn't learn about Hubbub until later), and found that the effort needed to integrate with our project, and the number of dependencies they would bring into the serving system, precluded us from using them easily. Hixie suggested "Just write your own! It shouldn't be too hard, the algorithm is all specified in the HTML spec" (har, har, famous last words), and Gumbo was born out of naivete and youthful optimism. :-)

There were a bunch of reasons for the choice of C over C++:

1. At the time, we were doing a bunch of stuff with LLVM in the templating language. I'd previously been responsible for trying to integrate LLVM with C++ generated code, and it is painful, mostly because of name mangling and vtable dispatch. Providing a C API sidesteps this entirely, as LLVM can call into C code and use C structs no problem, and once the API is in C there's little reason to make the internals be in C++.

2. We wanted to provide tooling for this templating language, and the easiest way to write tooling is in Python or some other scripting language. It's easier to provide Python etc. bindings with a C API than a C++ API.

3. We'd intended from the start to open-source this. One of the team members had significant open-source experience, and he pointed out that within the open-source community, there are a number of people who basically refuse to use C++ and will instantly disqualify a C++ library. So regardless of whether these people are right, to reach the maximum number of people and prospective projects it should be in C.

edwinyzh• 13 years ago

Great! As a developer of a live html code editor, I've got my excellent html parser (in Delphi) already, but still have to bookmark this one for future reference

Lasher• 13 years ago

Is this what Google actually uses to parse HTML5 pages? Seems like there might be some SEO value in studying it if so. Not for any "black hat" purposes, more to understand what they can and can't easily get to.

carsonreinke• 13 years ago

Is it me or do the comments in the source seem sparse?

Google Open-Sources Gumbo: C Library for Parsing HTML5

Related Stories