move html5lib code into dart svn repo

pkg/third_party/html5lib/lib/src/treebuilder.dart

+/** Internals to the tree builders. */
+library treebuilder;
+
+import 'dart:collection';
+import 'package:html5lib/dom.dart';
+import 'package:source_maps/span.dart' show FileSpan;
+import 'constants.dart';
+import 'list_proxy.dart';
+import 'token.dart';
+import 'utils.dart';
+
+// The scope markers are inserted when entering object elements,
+// marquees, table cells, and table captions, and are used to prevent formatting
+// from "leaking" into tables, object elements, and marquees.
+final Node Marker = null;
+
+// TODO(jmesserly): this should extend ListBase<Node>, but my simple attempt
+// didn't work.
+class ActiveFormattingElements extends ListProxy<Node> {
+  ActiveFormattingElements() : super();
+
+  // Override the "add" method.
+  // TODO(jmesserly): I'd rather not override this; can we do this in the
+  // calling code instead?
+  void add(Node node) {
+    int equalCount = 0;
+    if (node != Marker) {
+      for (Node element in reversed) {
+        if (element == Marker) {
+          break;
+        }
+        if (_nodesEqual(element, node)) {
+          equalCount += 1;
+        }
+        if (equalCount == 3) {
+          remove(element);
+          break;
+        }
+      }
+    }
+    super.add(node);
+  }
+}
+
+// TODO(jmesserly): this should exist in corelib...
+bool _mapEquals(Map a, Map b) {
+  if (a.length != b.length) return false;
+  if (a.length == 0) return true;
+
+  for (var keyA in a.keys) {
+    var valB = b[keyA];
+    if (valB == null && !b.containsKey(keyA)) {
+      return false;
+    }
+
+    if (a[keyA] != valB) {
+      return false;
+    }
+  }
+  return true;
+}
+
+
+bool _nodesEqual(Node node1, Node node2) {
+  return node1.nameTuple == node2.nameTuple &&
+      _mapEquals(node1.attributes, node2.attributes);
+}
+
+/** Basic treebuilder implementation. */
+class TreeBuilder {
+  final String defaultNamespace;
+
+  Document document;
+
+  final openElements = <Node>[];
+
+  final activeFormattingElements = new ActiveFormattingElements();
+
+  Node headPointer;
+
+  Node formPointer;
+
+  /**
+   * Switch the function used to insert an element from the
+   * normal one to the misnested table one and back again
+   */
+  bool insertFromTable;
+
+  TreeBuilder(bool namespaceHTMLElements)
+      : defaultNamespace = namespaceHTMLElements ? Namespaces.html : null {
+    reset();
+  }
+
+  void reset() {
+    openElements.clear();
+    activeFormattingElements.clear();
+
+    //XXX - rename these to headElement, formElement
+    headPointer = null;
+    formPointer = null;
+
+    insertFromTable = false;
+
+    document = new Document();
+  }
+
+  bool elementInScope(target, {String variant}) {
+    //If we pass a node in we match that. if we pass a string
+    //match any node with that name
+    bool exactNode = target is Node && target.nameTuple != null;
+
+    List listElements1 = scopingElements;
+    List listElements2 = const [];
+    bool invert = false;
+    if (variant != null) {
+      switch (variant) {
+        case "button":
+          listElements2 = const [const Pair(Namespaces.html, "button")];
+          break;
+        case "list":
+          listElements2 = const [const Pair(Namespaces.html, "ol"),
+                                 const Pair(Namespaces.html, "ul")];
+          break;
+        case "table":
+          listElements1 = const [const Pair(Namespaces.html, "html"),
+                                 const Pair(Namespaces.html, "table")];
+          break;
+        case "select":
+          listElements1 = const [const Pair(Namespaces.html, "optgroup"),
+                                 const Pair(Namespaces.html, "option")];
+          invert = true;
+          break;
+        default: assert(false); break;
+      }
+    }
+
+    for (Node node in openElements.reversed) {
+      if (node.tagName == target && !exactNode ||
+          node == target && exactNode) {
+        return true;
+      } else if (invert !=
+          (listElements1.contains(node.nameTuple) ||
+           listElements2.contains(node.nameTuple))) {
+        return false;
+      }
+    }
+
+    assert(false); // We should never reach this point
+  }
+
+  void reconstructActiveFormattingElements() {
+    // 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 (activeFormattingElements.length == 0) {
+      return;
+    }
+
+    // Step 2 and step 3: we start with the last element. So i is -1.
+    int i = activeFormattingElements.length - 1;
+    var entry = activeFormattingElements[i];
+    if (entry == Marker || openElements.contains(entry)) {
+      return;
+    }
+
+    // Step 6
+    while (entry != Marker && !openElements.contains(entry)) {
+      if (i == 0) {
+        //This will be reset to 0 below
+        i = -1;
+        break;
+      }
+      i -= 1;
+      // Step 5: let entry be one earlier in the list.
+      entry = activeFormattingElements[i];
+    }
+
+    while (true) {
+      // Step 7
+      i += 1;
+
+      // Step 8
+      entry = activeFormattingElements[i];
+
+      // TODO(jmesserly): optimize this. No need to create a token.
+      var cloneToken = new StartTagToken(
+          entry.tagName,
+          namespace: entry.namespace,
+          data: new LinkedHashMap.from(entry.attributes))
+          ..span = entry.sourceSpan;
+
+      // Step 9
+      var element = insertElement(cloneToken);
+
+      // Step 10
+      activeFormattingElements[i] = element;
+
+      // Step 11
+      if (element == activeFormattingElements.last) {
+        break;
+      }
+    }
+  }
+
+  void clearActiveFormattingElements() {
+    var entry = activeFormattingElements.removeLast();
+    while (activeFormattingElements.length > 0 && entry != Marker) {
+      entry = activeFormattingElements.removeLast();
+    }
+  }
+
+  /**
+   * Check if an element exists between the end of the active
+   * formatting elements and the last marker. If it does, return it, else
+   * return null.
+   */
+  Node elementInActiveFormattingElements(String name) {
+    for (Node item in activeFormattingElements.reversed) {
+      // Check for Marker first because if it's a Marker it doesn't have a
+      // name attribute.
+      if (item == Marker) {
+        break;
+      } else if (item.tagName == name) {
+        return item;
+      }
+    }
+    return null;
+  }
+
+  void insertRoot(Token token) {
+    var element = createElement(token);
+    openElements.add(element);
+    document.nodes.add(element);
+  }
+
+  void insertDoctype(DoctypeToken token) {
+    var doctype = new DocumentType(token.name, token.publicId, token.systemId)
+        ..sourceSpan = token.span;
+    document.nodes.add(doctype);
+  }
+
+  void insertComment(StringToken token, [Node parent]) {
+    if (parent == null) {
+      parent = openElements.last;
+    }
+    parent.nodes.add(new Comment(token.data)..sourceSpan = token.span);
+  }
+
+  /** Create an element but don't insert it anywhere */
+  Element createElement(StartTagToken token) {
+    var name = token.name;
+    var namespace = token.namespace;
+    if (namespace == null) namespace = defaultNamespace;
+    var element = new Element(name, namespace)
+        ..attributes = token.data
+        ..sourceSpan = token.span;
+    return element;
+  }
+
+  Element insertElement(StartTagToken token) {
+    if (insertFromTable) return insertElementTable(token);
+    return insertElementNormal(token);
+  }
+
+  Element insertElementNormal(StartTagToken token) {
+    var name = token.name;
+    var namespace = token.namespace;
+    if (namespace == null) namespace = defaultNamespace;
+    var element = new Element(name, namespace)
+        ..attributes = token.data
+        ..sourceSpan = token.span;
+    openElements.last.nodes.add(element);
+    openElements.add(element);
+    return element;
+  }
+
+  Element insertElementTable(token) {
+    /** Create an element and insert it into the tree */
+    var element = createElement(token);
+    if (!tableInsertModeElements.contains(openElements.last.tagName)) {
+      return insertElementNormal(token);
+    } else {
+      // We should be in the InTable mode. This means we want to do
+      // special magic element rearranging
+      var nodePos = getTableMisnestedNodePosition();
+      if (nodePos[1] == null) {
+        // TODO(jmesserly): I don't think this is reachable. If insertFromTable
+        // is true, there will be a <table> element open, and it always has a
+        // parent pointer.
+        nodePos[0].nodes.add(element);
+      } else {
+        nodePos[0].insertBefore(element, nodePos[1]);
+      }
+      openElements.add(element);
+    }
+    return element;
+  }
+
+  /** Insert text data. */
+  void insertText(String data, FileSpan span) {
+    var parent = openElements.last;
+
+    if (!insertFromTable || insertFromTable &&
+        !tableInsertModeElements.contains(openElements.last.tagName)) {
+      _insertText(parent, data, span);
+    } else {
+      // We should be in the InTable mode. This means we want to do
+      // special magic element rearranging
+      var nodePos = getTableMisnestedNodePosition();
+      _insertText(nodePos[0], data, span, nodePos[1]);
+    }
+  }
+
+  /**
+   * Insert [data] as text in the current node, positioned before the
+   * start of node [refNode] or to the end of the node's text.
+   */
+  static void _insertText(Node parent, String data, FileSpan span,
+      [Element refNode]) {
+    var nodes = parent.nodes;
+    if (refNode == null) {
+      if (nodes.length > 0 && nodes.last is Text) {
+        Text last = nodes.last;
+        last.value = '${last.value}$data';
+
+        if (span != null) {
+          last.sourceSpan = span.file.span(last.sourceSpan.start.offset,
+              span.end.offset);
+        }
+      } else {
+        nodes.add(new Text(data)..sourceSpan = span);
+      }
+    } else {
+      int index = nodes.indexOf(refNode);
+      if (index > 0 && nodes[index - 1] is Text) {
+        Text last = nodes[index - 1];
+        last.value = '${last.value}$data';
+      } else {
+        nodes.insert(index, new Text(data)..sourceSpan = span);
+      }
+    }
+  }
+
+  /**
+   * Get the foster parent element, and sibling to insert before
+   * (or null) when inserting a misnested table node
+   */
+  List<Node> getTableMisnestedNodePosition() {
+    // The foster parent element is the one which comes before the most
+    // recently opened table element
+    // XXX - this is really inelegant
+    Node lastTable = null;
+    Node fosterParent = null;
+    var insertBefore = null;
+    for (Node elm in openElements.reversed) {
+      if (elm.tagName == "table") {
+        lastTable = elm;
+        break;
+      }
+    }
+    if (lastTable != null) {
+      // XXX - we should really check that this parent is actually a
+      // node here
+      if (lastTable.parent != null) {
+        fosterParent = lastTable.parent;
+        insertBefore = lastTable;
+      } else {
+        fosterParent = openElements[openElements.indexOf(lastTable) - 1];
+      }
+    } else {
+      fosterParent = openElements[0];
+    }
+    return [fosterParent, insertBefore];
+  }
+
+  void generateImpliedEndTags([String exclude]) {
+    var name = openElements.last.tagName;
+    // XXX td, th and tr are not actually needed
+    if (name != exclude && const ["dd", "dt", "li", "option", "optgroup", "p",
+        "rp", "rt"].contains(name)) {
+      openElements.removeLast();
+      // XXX This is not entirely what the specification says. We should
+      // investigate it more closely.
+      generateImpliedEndTags(exclude);
+    }
+  }
+
+  /** Return the final tree. */
+  Document getDocument() => document;
+
+  /** Return the final fragment. */
+  DocumentFragment getFragment() {
+    //XXX assert innerHTML
+    var fragment = new DocumentFragment();
+    openElements[0].reparentChildren(fragment);
+    return fragment;
+  }
+}