def __init__(self, name):

"""Node representing an item in the tree.

self.name = name

self.parent = None

self.value = None

self.attributes = {}

self.childNodes = []

self._flags = []

def __unicode__(self):

attributesStr = " ".join(["%s=\"%s\""%(name, value)

for name, value in

self.attributes.items()])

if attributesStr:

return "<%s %s>"%(self.name,attributesStr)

else:

return "<%s>"%(self.name)

def __repr__(self):

return "<%s>" % (self.name)

def appendChild(self, node):

"""Insert node as a child of the current node

raise NotImplementedError

def insertText(self, data, insertBefore=None):

"""Insert data as text in the current node, positioned before the

raise NotImplementedError

def insertBefore(self, node, refNode):

"""Insert node as a child of the current node, before refNode in the

raise NotImplementedError

def removeChild(self, node):

"""Remove node from the children of the current node

raise NotImplementedError

def reparentChildren(self, newParent):

"""Move all the children of the current node to newParent.

#XXX - should this method be made more general?

for child in self.childNodes:

newParent.appendChild(child)

self.childNodes = []

def cloneNode(self):

"""Return a shallow copy of the current node i.e. a node with the same

raise NotImplementedError

def hasContent(self):

"""Return true if the node has children or text, false otherwise

"""Base treebuilder implementation

#Document class

documentClass = None

#The class to use for creating a node

elementClass = None

#The class to use for creating comments

commentClass = None

#The class to use for creating doctypes

doctypeClass = None

#Fragment class

fragmentClass = None

def __init__(self, namespaceHTMLElements):

if namespaceHTMLElements:

self.defaultNamespace = "http://www.w3.org/1999/xhtml"

else:

self.defaultNamespace = None

self.reset()

def reset(self):

self.openElements = []

self.activeFormattingElements = []

#XXX - rename these to headElement, formElement

self.headPointer = None

self.formPointer = None

self.insertFromTable = False

self.document = self.documentClass()

def elementInScope(self, target, tableVariant=False):

# Exit early when possible.

if self.openElements[-1].name == target:

return True

for node in reversed(self.openElements):

if node.name == target:

return True

elif node.name == "table":

return False

elif not tableVariant and node.name in scopingElements:

return False

elif node.name == "html":

return False

assert False # We should never reach this point

def reconstructActiveFormattingElements(self):

# Within this algorithm the order of steps described in the

# specification is not quite the same as the order of steps in the

# code. It should still do the same though.

# Step 1: stop the algorithm when there's nothing to do.

if not self.activeFormattingElements:

return

# Step 2 and step 3: we start with the last element. So i is -1.

i = -1

entry = self.activeFormattingElements[i]

if entry == Marker or entry in self.openElements:

return

# Step 6

while entry != Marker and entry not in self.openElements:

# Step 5: let entry be one earlier in the list.

i -= 1

try:

entry = self.activeFormattingElements[i]

except:

# Step 4: at this point we need to jump to step 8. By not doing

# i += 1 which is also done in step 7 we achieve that.

break

while True:

# Step 7

i += 1

# Step 8

clone = self.activeFormattingElements[i].cloneNode()

# Step 9

element = self.insertElement({"type":"StartTag",

"name":clone.name,

"namespace":clone.namespace,

"data":clone.attributes})

# Step 10

self.activeFormattingElements[i] = element

# Step 11

if element == self.activeFormattingElements[-1]:

break

def clearActiveFormattingElements(self):

entry = self.activeFormattingElements.pop()

while self.activeFormattingElements and entry != Marker:

entry = self.activeFormattingElements.pop()

def elementInActiveFormattingElements(self, name):

"""Check if an element exists between the end of the active

for item in self.activeFormattingElements[::-1]:

# Check for Marker first because if it's a Marker it doesn't have a

# name attribute.

if item == Marker:

break

elif item.name == name:

return item

return False

def insertRoot(self, token):

element = self.createElement(token)

self.openElements.append(element)

self.document.appendChild(element)

def insertDoctype(self, token):

name = token["name"]

publicId = token["publicId"]

systemId = token["systemId"]

doctype = self.doctypeClass(name, publicId, systemId)

self.document.appendChild(doctype)

def insertComment(self, token, parent=None):

if parent is None:

parent = self.openElements[-1]

parent.appendChild(self.commentClass(token["data"]))

def createElement(self, token):

"""Create an element but don't insert it anywhere"""

name = token["name"]

namespace = token.get("namespace", self.defaultNamespace)

element = self.elementClass(name, namespace)

element.attributes = token["data"]

return element

def _getInsertFromTable(self):

return self._insertFromTable

def _setInsertFromTable(self, value):

"""Switch the function used to insert an element from the

self._insertFromTable = value

if value:

self.insertElement = self.insertElementTable

else:

self.insertElement = self.insertElementNormal

insertFromTable = property(_getInsertFromTable, _setInsertFromTable)

def insertElementNormal(self, token):

name = token["name"]

namespace = token.get("namespace", self.defaultNamespace)

element = self.elementClass(name, namespace)

element.attributes = token["data"]

self.openElements[-1].appendChild(element)

self.openElements.append(element)

return element

def insertElementTable(self, token):

"""Create an element and insert it into the tree"""

element = self.createElement(token)

if self.openElements[-1].name not in tableInsertModeElements:

return self.insertElementNormal(token)

else:

#We should be in the InTable mode. This means we want to do

#special magic element rearranging

parent, insertBefore = self.getTableMisnestedNodePosition()

if insertBefore is None:

parent.appendChild(element)

else:

parent.insertBefore(element, insertBefore)

self.openElements.append(element)

return element

def insertText(self, data, parent=None):

"""Insert text data."""

if parent is None:

parent = self.openElements[-1]

if (not self.insertFromTable or (self.insertFromTable and

self.openElements[-1].name

not in tableInsertModeElements)):

parent.insertText(data)

else:

# We should be in the InTable mode. This means we want to do

# special magic element rearranging

parent, insertBefore = self.getTableMisnestedNodePosition()

parent.insertText(data, insertBefore)

def getTableMisnestedNodePosition(self):

"""Get the foster parent element, and sibling to insert before

# The foster parent element is the one which comes before the most

# recently opened table element

# XXX - this is really inelegant

lastTable=None

fosterParent = None

insertBefore = None

for elm in self.openElements[::-1]:

if elm.name == "table":

lastTable = elm

break

if lastTable:

# XXX - we should really check that this parent is actually a

# node here

if lastTable.parent:

fosterParent = lastTable.parent

insertBefore = lastTable

else:

fosterParent = self.openElements[

self.openElements.index(lastTable) - 1]

else:

fosterParent = self.openElements[0]

return fosterParent, insertBefore

def generateImpliedEndTags(self, exclude=None):

name = self.openElements[-1].name

# XXX td, th and tr are not actually needed

if (name in frozenset(("dd", "dt", "li", "p", "td", "th", "tr"))

and name != exclude):

self.openElements.pop()

# XXX This is not entirely what the specification says. We should

# investigate it more closely.

self.generateImpliedEndTags(exclude)

def getDocument(self):

"Return the final tree"

return self.document

def getFragment(self):

"Return the final fragment"

#assert self.innerHTML

fragment = self.fragmentClass()

self.openElements[0].reparentChildren(fragment)

return fragment

def testSerializer(self, node):

"""Serialize the subtree of node in the format required by unit tests