code review 3355041: html: first cut at a parser.

html: first cut at a parser.

[nigeltao, 2010-12-02 06:18:39]

Hello golang-dev@googlegroups.com,

I'd like you to review this change.

[nigeltao, 2010-12-02 06:21:56]

R=gri

There are many, many TODOs before this parser is good enough for the tangled
mess that is all the world's HTML, but the general approach should be clear, and
it does pass the first three tests in the test suite.

[gri, 2010-12-02 22:11:35]

Looks pretty good.

Mostly questions, and a few suggestions.

http://codereview.appspot.com/3355041/diff/5001/src/pkg/html/doc.go
File src/pkg/html/doc.go (right):

http://codereview.appspot.com/3355041/diff/5001/src/pkg/html/doc.go#newcode72
src/pkg/html/doc.go:72: Parsing is done by calling Parse on an io.Reader, which
returns the root of the
should this be: "... by calling Parse with an io.Reader, ..." ? (_on_ an
io.Reader sounds to me like Parse is a method of io.Reader, but then again, I am
not a native English speaker).

http://codereview.appspot.com/3355041/diff/5001/src/pkg/html/parse.go
File src/pkg/html/parse.go (right):

http://codereview.appspot.com/3355041/diff/5001/src/pkg/html/parse.go#newcode16
src/pkg/html/parse.go:16: // ErrorNode means that an error occurred during
parsing.
These comments are redundant - the constant names are so clear. Better to just
have a small comment before the const.

http://codereview.appspot.com/3355041/diff/5001/src/pkg/html/parse.go#newcode30
src/pkg/html/parse.go:30: // contain a slice of Attributes. Data is unescaped,
so that it looks like
s/Data/Text Data/ ?

http://codereview.appspot.com/3355041/diff/5001/src/pkg/html/parse.go#newcode42
src/pkg/html/parse.go:42: type insertionMode func(*parser) insertionMode
I wonder if there's a better name for this function type. "transitionFunction",
"transition", ?

http://codereview.appspot.com/3355041/diff/5001/src/pkg/html/parse.go#newcode48
src/pkg/html/parse.go:48: t        *Tokenizer
Is field t accessed a lot? It deserves a longer name unless it's used everywhere
(maybe tstream, stream, ...). Your are not cheap with characters for the next
fields (token, and hasToken). It seems to me that it should only be accessed in
read().

http://codereview.appspot.com/3355041/diff/5001/src/pkg/html/parse.go#newcode49
src/pkg/html/parse.go:49: token    Token
I'd rather make this field shorter ("tok" comes to mind), it's used everywhere.

http://codereview.appspot.com/3355041/diff/5001/src/pkg/html/parse.go#newcode50
src/pkg/html/parse.go:50: hasToken bool
should explain hasToken

As an aside: I am always skeptical when I see a boolean flag to be used with a
read/unread mechanism. Would it be possible to always have the invariant that
token is the next token we are looking at, and that it may not be _consumed_ in
some cases (effectively when you'd do the unread)? In all cases it is consumed,
and read is called to get the token afterwards. So instead of doing an unread
(and somehow one needs to know that there are no 2 unreads following each other,
otherwise there's a bug), there's a consume().

http://codereview.appspot.com/3355041/diff/5001/src/pkg/html/parse.go#newcode55
src/pkg/html/parse.go:55: // doc is the resultant document.
Is this the root or the current sub-node? explain.

http://codereview.appspot.com/3355041/diff/5001/src/pkg/html/parse.go#newcode59
src/pkg/html/parse.go:59: // Element pointers (section 10.2.3.4).
Perhaps this could also be explained in more detail here.

http://codereview.appspot.com/3355041/diff/5001/src/pkg/html/parse.go#newcode62
src/pkg/html/parse.go:62: scripting, framesetOK bool
same here: use two separate lines and explain when they are true

http://codereview.appspot.com/3355041/diff/5001/src/pkg/html/parse.go#newcode65
src/pkg/html/parse.go:65: // pop pops from the stack of open elements.
It must only be called for non-empty stacks.

(or something along those lines)

http://codereview.appspot.com/3355041/diff/5001/src/pkg/html/parse.go#newcode81
src/pkg/html/parse.go:81: n := len(p.stack)
perhaps invert this, with common (?) case first:

if n := len(p.stack); n > 0 {
    return p.stack[n-1]
}
return p.doc

(up to you)

http://codereview.appspot.com/3355041/diff/5001/src/pkg/html/parse.go#newcode187
src/pkg/html/parse.go:187: p.unread()
how do I reason about unread? specifically, how can i be sure it's not been
called just before (and this one may cause a panic now)?

Is is because there is a token when I get into a insertionFunction and so I can
always unread one? If that is the case, wouldn't it better to reverse the
meaning, and have a "consume" when one has consumed a token? instead of an
unread?

http://codereview.appspot.com/3355041/diff/5001/src/pkg/html/parse.go#newcode429
src/pkg/html/parse.go:429: Type: DocumentNode,
perhaps just one line for this literal

http://codereview.appspot.com/3355041/diff/5001/src/pkg/html/token.go
File src/pkg/html/token.go (right):

http://codereview.appspot.com/3355041/diff/5001/src/pkg/html/token.go#newcode18
src/pkg/html/token.go:18: // ErrorToken means that an error occurred during
tokenization.
Is there a particular reason for the longer names? The shorter ones seem nice.

[nigeltao, 2010-12-03 04:04:24]

I've rewritten it to have an explicit read instead of an unread, driven by a
bool return value from calling the insertionMode transition function. Having the
transition function explictly call consume (or read) doesn't work so well since
it would have to handle the error (which may be EOF).

Consuming is the norm, and not doing so is the exception. Often the function
returns in return !foo, and it might be a little nicer to reverse the semantics
of the bool return, although I don't have a good variable name that means the
opposite of consumed. Let me think about it.

http://codereview.appspot.com/3355041/diff/5001/src/pkg/html/doc.go
File src/pkg/html/doc.go (right):

http://codereview.appspot.com/3355041/diff/5001/src/pkg/html/doc.go#newcode72
src/pkg/html/doc.go:72: Parsing is done by calling Parse on an io.Reader, which
returns the root of the
On 2010/12/02 22:11:35, gri wrote:
> should this be: "... by calling Parse with an io.Reader, ..." ? (_on_ an
> io.Reader sounds to me like Parse is a method of io.Reader, but then again, I
am
> not a native English speaker).

Done.

http://codereview.appspot.com/3355041/diff/5001/src/pkg/html/parse.go
File src/pkg/html/parse.go (right):

http://codereview.appspot.com/3355041/diff/5001/src/pkg/html/parse.go#newcode16
src/pkg/html/parse.go:16: // ErrorNode means that an error occurred during
parsing.
On 2010/12/02 22:11:35, gri wrote:
> These comments are redundant - the constant names are so clear. Better to just
> have a small comment before the const.

Done.

http://codereview.appspot.com/3355041/diff/5001/src/pkg/html/parse.go#newcode30
src/pkg/html/parse.go:30: // contain a slice of Attributes. Data is unescaped,
so that it looks like
On 2010/12/02 22:11:35, gri wrote:
> s/Data/Text Data/ ?

It's just Data, the same as a Token's Data field.

http://codereview.appspot.com/3355041/diff/5001/src/pkg/html/parse.go#newcode42
src/pkg/html/parse.go:42: type insertionMode func(*parser) insertionMode
On 2010/12/02 22:11:35, gri wrote:
> I wonder if there's a better name for this function type.
"transitionFunction",
> "transition", ?

The spec uses "insertion mode".

http://codereview.appspot.com/3355041/diff/5001/src/pkg/html/parse.go#newcode48
src/pkg/html/parse.go:48: t        *Tokenizer
On 2010/12/02 22:11:35, gri wrote:
> Is field t accessed a lot? It deserves a longer name unless it's used
everywhere
> (maybe tstream, stream, ...). Your are not cheap with characters for the next
> fields (token, and hasToken). It seems to me that it should only be accessed
in
> read().

Done.

http://codereview.appspot.com/3355041/diff/5001/src/pkg/html/parse.go#newcode49
src/pkg/html/parse.go:49: token    Token
On 2010/12/02 22:11:35, gri wrote:
> I'd rather make this field shorter ("tok" comes to mind), it's used
everywhere.

Done.

http://codereview.appspot.com/3355041/diff/5001/src/pkg/html/parse.go#newcode50
src/pkg/html/parse.go:50: hasToken bool
On 2010/12/02 22:11:35, gri wrote:
> should explain hasToken
> 
> As an aside: I am always skeptical when I see a boolean flag to be used with a
> read/unread mechanism. Would it be possible to always have the invariant that
> token is the next token we are looking at, and that it may not be _consumed_
in
> some cases (effectively when you'd do the unread)? In all cases it is
consumed,
> and read is called to get the token afterwards. So instead of doing an unread
> (and somehow one needs to know that there are no 2 unreads following each
other,
> otherwise there's a bug), there's a consume().

I've made insertionMode return a bool saying whether or not to consume.

http://codereview.appspot.com/3355041/diff/5001/src/pkg/html/parse.go#newcode55
src/pkg/html/parse.go:55: // doc is the resultant document.
On 2010/12/02 22:11:35, gri wrote:
> Is this the root or the current sub-node? explain.

It's the root node.

http://codereview.appspot.com/3355041/diff/5001/src/pkg/html/parse.go#newcode59
src/pkg/html/parse.go:59: // Element pointers (section 10.2.3.4).
On 2010/12/02 22:11:35, gri wrote:
> Perhaps this could also be explained in more detail here.

These extra state fields are written but not read anywhere yet. I'll add some
explanatory comments when I implement the part of the specification's algorithm
that refers to them.

http://codereview.appspot.com/3355041/diff/5001/src/pkg/html/parse.go#newcode65
src/pkg/html/parse.go:65: // pop pops from the stack of open elements.
On 2010/12/02 22:11:35, gri wrote:
> It must only be called for non-empty stacks.
> 
> (or something along those lines)

Done.

http://codereview.appspot.com/3355041/diff/5001/src/pkg/html/parse.go#newcode81
src/pkg/html/parse.go:81: n := len(p.stack)
On 2010/12/02 22:11:35, gri wrote:
> perhaps invert this, with common (?) case first:
> 
> if n := len(p.stack); n > 0 {
>     return p.stack[n-1]
> }
> return p.doc
> 
> (up to you)

Done.

http://codereview.appspot.com/3355041/diff/5001/src/pkg/html/token.go
File src/pkg/html/token.go (right):

http://codereview.appspot.com/3355041/diff/5001/src/pkg/html/token.go#newcode18
src/pkg/html/token.go:18: // ErrorToken means that an error occurred during
tokenization.
On 2010/12/02 22:11:35, gri wrote:
> Is there a particular reason for the longer names? The shorter ones seem nice.

It's because I'm introducing ErrorNode and TextNode as values of type NodeType.

[gri, 2010-12-04 00:13:41]

Some nitpicking.

Regarding the error handling: It's nice that there's only one place that needs
to worry about errors, but as it is now parsing will terminate right away of
there's an error. If it makes sense to continue in the presence of errors (e.g.
because one wants to analyze/index erroneous html), the current structure
doesn't work so well. An alternative approach would be to handle errors in
read() or consume() and have a error handler (a call back) that is invoked in
that case. Not sure that makes sense here, but I wanted to bring it up for
discussion. For instance, the go/parser uses that approach.

http://codereview.appspot.com/3355041/diff/15001/src/pkg/html/parse.go
File src/pkg/html/parse.go (right):

http://codereview.appspot.com/3355041/diff/15001/src/pkg/html/parse.go#newcode61
src/pkg/html/parse.go:61: // pop pops from the stack of open elements.
pop pops the top of the stack of open nodes.

(matches what you wrote for top())

http://codereview.appspot.com/3355041/diff/15001/src/pkg/html/parse.go#newcode70
src/pkg/html/parse.go:70: // push pushes onto the stack of open elements.
push pushes the node n onto the stack of open nodes.

http://codereview.appspot.com/3355041/diff/15001/src/pkg/html/parse.go#newcode75
src/pkg/html/parse.go:75: // top returns the top of the stack of open elements.
s/element/nodes/

http://codereview.appspot.com/3355041/diff/15001/src/pkg/html/parse.go#newcode84
src/pkg/html/parse.go:84: // addChild adds a child node n to the top element,
and pushes n
s/element/stack node/ (it may not be an element node)

http://codereview.appspot.com/3355041/diff/15001/src/pkg/html/parse.go#newcode94
src/pkg/html/parse.go:94: // addText adds text to the current node
addText adds a text node to the top stack node.

http://codereview.appspot.com/3355041/diff/15001/src/pkg/html/parse.go#newcod...
src/pkg/html/parse.go:115: // read reads the next token. This is usually from
the tokenizer, but it may
This comment is not quite right anymore (there's no unread).

http://codereview.appspot.com/3355041/diff/15001/src/pkg/html/parse.go#newcod...
src/pkg/html/parse.go:152: implied bool
perhaps this could be "consumed" (or "explicit" vs "implied") now? Then the
default also makes sense.

[nigeltao, 2010-12-05 22:58:25]

PTAL.

Regarding error handling, the spec defines "parse errors" but IIUC they only
terminate parsing in strict mode, which is only really used by conformance
checkers. Real world parsers just recover when encountering malformed HTML, and
the spec defines exactly how to recover. Real world HTML is nonconformant; that
horse has bolted and will never come back.

My parser doesn't do anything on "parse errors" except recover, and my tokenizer
only returns errors in placeholder TODO cases (such as implementing <!--
comments -->) or passing along those errors from its underlying io.Reader.

http://codereview.appspot.com/3355041/diff/15001/src/pkg/html/parse.go
File src/pkg/html/parse.go (right):

http://codereview.appspot.com/3355041/diff/15001/src/pkg/html/parse.go#newcode61
src/pkg/html/parse.go:61: // pop pops from the stack of open elements.
On 2010/12/04 00:13:41, gri wrote:
> pop pops the top of the stack of open nodes.
> 
> (matches what you wrote for top())

Done.

http://codereview.appspot.com/3355041/diff/15001/src/pkg/html/parse.go#newcode75
src/pkg/html/parse.go:75: // top returns the top of the stack of open elements.
On 2010/12/04 00:13:41, gri wrote:
> s/element/nodes/

stack is a []*Node, but consists only of element nodes, and not text nodes.

http://codereview.appspot.com/3355041/diff/15001/src/pkg/html/parse.go#newcod...
src/pkg/html/parse.go:115: // read reads the next token. This is usually from
the tokenizer, but it may
On 2010/12/04 00:13:41, gri wrote:
> This comment is not quite right anymore (there's no unread).

Done.

[gri, 2010-12-06 22:17:48]

LGTM

http://codereview.appspot.com/3355041/diff/26001/src/pkg/html/doc.go
File src/pkg/html/doc.go (right):

http://codereview.appspot.com/3355041/diff/26001/src/pkg/html/doc.go#newcode73
src/pkg/html/doc.go:73: the parse tree (the document element) as a *Node. Again,
it is the caller's
s/Again, it is/It is/

[nigeltao, 2010-12-07 01:02:48]

*** Submitted as http://code.google.com/p/go/source/detail?r=018e9434af09 ***

html: first cut at a parser.

R=gri
CC=golang-dev
http://codereview.appspot.com/3355041