any interest in modifying code for binary search of tag names and for tag_in ?

[kevinhendricks]

Hi, I have modified gumbo-parser to expand the TagNames to include the full set of presentation elements in MathML and the full SVG tag list. (according to the latest spec). Given the size of the new tag list, a binary search is needed to quickly assign GumboTag enums.

But since we now can work with sorted lists of integers and complete sets of SVG and MathML tags we can easily use binary search on sorted integer lists to detect if a tag is a valid MathML tag (ie. part of the presentation subset) or a valid SVG tag.

With this capability in place we can convert all of the calls to tag_in in parser.c and its related cousins to properly handle any C pre-processor determined list of tags (no more varargs needed) and to use binary search to determine if a tag is in that list.

With this and the capability to quickly determine if something is a valid SVG or MathML element, you could easily modify the parser to properly prevent the confusion that comes when mislabling html tags as mathml or svg tags. which caused a number of issues.

I have completed part one of this where I modify src/tag.c, add src/tag.h, and update the gumbo.h tag enum or expand its contents to properly match the list in tag.c.

Before I go to the trouble of converting all of the varargs calls to tag_in and its relatives in parser.c to use pre-determined tag lists (pre-sorted), I was hoping someone would look at the part 1 patch and let me know if they are at all interested.

[kevinhendricks]

I am happy to e-mail the part-1 patch (using binary search and much larger recognized tag enum) to anyone who wants it for review as my own gumbo-parser fork on github has a number of other changes you will not want (working with xhtml parsing, error reporting, etc). Just let me know where to send it if anyone is interested.

[kevinhendricks]

Hi, I committed it to my fork so that the commit would show up and you could more easily decide if this is in any way the direction you would like to go.

https://github.com/kevinhendricks/gumbo-parser/commit/ae3b57af872a1eb9788f444a9f7de279f09e9b65

[kevinhendricks]

And here is what a parser modified to replace varargs calls with const int sorted lists for tag_in calls looks like. A similar approach can be used for the remaining use of varargs for the in_scope calls as well.

https://github.com/kevinhendricks/gumbo-parser/commit/4882c85ab0ba033d6559ee389e923b8c16732a21

That version has some of my changes for XHTML5 parsing but I would be happy to send a patch against a clean version from today's master if anyone is interested.

Kevin

[nostrademons]

I'm a little concerned about the impact of this on other language bindings, many of which provide enums for GumboTag that are defined in the scripting language. At the very least, the Python bindings would have to be updated. @craigbarnes, @rubys, @karlwestin, @rgrove, would changing the values of the GumboTag mess things up for the Lua, Ruby, Node bindings or for Sanitize? Any other bystanders have concerns? I do like the idea of the tag lists being more complete, but I don't want to make unnecessary work for the 10+ other language bindings, and I suspect that SVG/MathML parsing is a relatively niche use case compared to HTML and don't want to bloat the API for common usages.

I don't like the usage of numbered const int lists in the other patch. It's important that it be possible to follow along with the spec while reading the code, and this separates the declaration of the list from its usage. I would rather pass a bitset by value and construct it with some macro magic than have to jump between file locations to read every clause of the spec.

[rgrove]

It looks to me like Nokogumbo only relies on gumbo_normalized_tagname(), so I think it would be unaffected (and by extension Sanitize would be unaffected).

[kevinhendricks]

Understood about wanting to keep the lists right in the code. I did not think you could pass an initializer as an argument, so I decided to move them to the top of each routine to try to keep them as close as possible to their use point. I will try to see if there is any macro definition that would help in this case.

My use case is epub2 and epub3 so svg is common to expand cover images and mathml is required for the epub3 spec. I was able to fix your mismatched ns tag case where mathml is used in an html table using an extra if to check if that tag really was part of svg or mathml before making it part of those namespaces in handle_token. There are no mathml td or tr elements. So it is easy to detect.

So doing binary searches an a flat enum of tags is a viable solution. Our project Sigil will use that approach since we need xhtml parsing of non-void but self-closed tags as well and so must maintain our own version of gumbo anyway.

Thanks for looking at it.

Kevin

[kevinhendricks]

As it turns out you can pass an initializer list in an argument in C99 if you cast it properly.. In other words, you could do the following in an argument to a fuction that expects an int pointer in that position:

tag_in(token, (int []) { TAG1, TAG2, TAG3, TAG4 }, cnt);

and

nodetag_in(node, (int []) { TAG1, TAG2, TAG3, TAG4 }, cnt);

I will give that a try for our own version.

[kevinhendricks]

FWIW, here is the commit to putting back the now sorted taglists back where they belong oin the code using the C99 initializer as argument approach:

https://github.com/kevinhendricks/gumbo-parser/commit/ea248f03bcbf6ce272e8269198add05dda00a138

[nostrademons]

I've thought a bit more about this in context of some of the other upcoming patches that will likely go in before 1.0.

I do want to extend the tag list to include common SVG and MathML tags. It'll make the parser more complete and a bit easier to use for future projects that wish to use this. Plus, a couple new tags (notably and ) have been added to the W3C spec with special handling, and so we can't get away from adding more tags to the enum without sacrificing spec compatibility.

However, I want to honor backwards-compatibility promises and make migration as easy as possible. A quick survey of the language bindings that I know of showed that D, Lua, C#, and Python were dependent upon the enum list. Most of these copied source code in directly (often, their FFI is structured as a C parser that automatically extracts the language binding information from a C header file), so they won't immediately break, but I'd still like to minimize arbitrary migration work. So there are a couple restrictions on how new tags can go in:

1. They go at the end of the GumboTag enum. This means the integer values of enum constants in other languages won't suddenly change; worst-case, their GUMBO_TAG_UNKNOWN handling won't trigger when they expect it to. (Language/library bindings should consider unknown tags as >= GUMBO_TAG_UNKNOWN, to allow for future expansion.) This also means that binary search won't work, because we can't re-sort the enum as new tags are added. If we're particularly worried about performance we can use Ragel to build a finite state machine for matching tags; we already use this quite effectively for entity references, and it should be even faster than binary search.
2. I'm holding off on merging any patches with new tags until 0.10, so we can honor the semantic versioning promise in the README. Likely included in 0.10: next/prev fields, template tag, fixes, and possibly new tags. It's API additions only, no changes, so minor version increment only. I'd like to do a bugfix-only release (0.9.3) before then so people can get the benefits of correctness fixes without the risk of API changes.

@aroben's patch #286 is going in, so you probably don't want to do major surgery to any of the node_tag_in stuff until after the HTML_QN stuff goes in. It's not sufficient (in HTML5) to detect HTML vs. SVG vs. MathML in the tokenizer, because the same tag may be in a different namespace depending on where in the DOM it is. For example,