Can the HTML5 parsing algorithm (https://html.spec.whatwg.org/multipage/parsing.html#parsing) be implemented in $O(n)$, or at worst $O(n\mathop{log}n)$, time, even for malicious input? It seems difficult; there appear to be places where a malicious document could force the user agent to perform $O(n)$ traversals $O(n)$ times. This is because the specification calls for the “list of active formatting elements” and the “stack of open elements” to be traversed in several places, and each of those can reach $O(n)$ size.

It appears that most of the queries could be done in $O(1)$ time by keeping a hash table from tag name to the list of unclosed elements with that tag name, along with using a multiset for the list of active formatting elements. However, the adoption agency algorithm presents a problem. It can only iterate 8 times, but each of those seems like it is $O(n)$. And I am not sure what kind of ferociously complicated data structure would work.

  • $\begingroup$ What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ – Raphael Jul 31 '17 at 5:07
  • 1
    $\begingroup$ "there appear to be places where a malicious document could force the user agent to perform O(n) traversals O(n) times" -- how so? $\endgroup$ – Raphael Jul 31 '17 at 5:07
  • 1
    $\begingroup$ That's a pretty complicated algorithm to be asking about. Have you done any analysis yourself? Is there any particular stage you are concerned about? Are there any stages that you have convinced yourself can be implemented efficiently? Can you elaborate on the specific aspects that you are concerned might require $O(n^2)$ time, and why? In your question, can we ignore Javascript execution (and ignore document.write), or do you also want to consider the time taken by and effects of Javascript? $\endgroup$ – D.W. Jul 31 '17 at 6:14
  • $\begingroup$ @D.W. I am not worried about Javascript. None of the applications that I am concerned about have it enabled. $\endgroup$ – Demi Jul 31 '17 at 13:39
  • $\begingroup$ I'm pretty sure the adoption agency algorithm is quadratic, and certainly all the implementations I've seen for it are quadratic. (At least, that's what I said in this related question on SO $\endgroup$ – rici Jul 31 '17 at 21:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.