From e564e0af5c2f7b9732e89707655068e507579a89 Mon Sep 17 00:00:00 2001
From: John MacFarlane <fiddlosopher@gmail.com>
Date: Thu, 8 Jan 2015 10:21:30 -0800
Subject: Use linked list instead of arrays for AST.

Use the same doubly linked node structure that cmark uses.
The primary advantages of this change are (a) simplified code,
especially in the renderers, and (b) elimination of the need for
recursion, so we can render deeply-nested structures without a
stack overflow.

A node walker has also been added, for easy AST traversal.

* Added js/lib/node.js for nodes. Includes a node walker.
* All modules updated to use node structures.
* Regularized position information into pos property.
* Performance is slightly worse than before, but only marginally,
  and no doubt there are more optimizations that can be done.
---
 js/lib/node.js | 195 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 195 insertions(+)
 create mode 100644 js/lib/node.js

(limited to 'js/lib/node.js')

diff --git a/js/lib/node.js b/js/lib/node.js
new file mode 100644
index 0000000..f96d65c
--- /dev/null
+++ b/js/lib/node.js
@@ -0,0 +1,195 @@
+util = require('util');
+
+function isContainer(node) {
+  var t = node.t;
+  return (t == 'Document' ||
+          t == 'BlockQuote' ||
+          t == 'List' ||
+          t == 'ListItem' ||
+          t == 'Paragraph' ||
+          t == 'Header' ||
+          t == 'Emph' ||
+          t == 'Strong' ||
+          t == 'Link' ||
+          t == 'Image');
+}
+
+function NodeWalker(root) {
+  this.current = root;
+  this.root = root;
+  this.entering = true;
+}
+
+NodeWalker.prototype.resumeAt = function(node, entering) {
+  this.current = node;
+  this.entering = (entering === true);
+};
+
+NodeWalker.prototype.next = function(){
+  var cur = this.current;
+  var entering = this.entering;
+
+  if (!cur)
+    return null;
+
+  var container = isContainer(cur);
+
+  if (entering && container) {
+    if (cur.firstChild) {
+      this.current = cur.firstChild;
+      this.entering = true;
+    } else {
+      // stay on node but exit
+      this.entering = false;
+    }
+
+  } else if (!entering && cur == this.root) {
+    // don't move past root
+    this.current = null;
+
+  } else if (cur.next) {
+    this.current = cur.next;
+    this.entering = true;
+
+  } else {
+    this.current = cur.parent;
+    this.entering = false;
+  }
+
+  return {entering: entering, node: cur};
+};
+
+function Node(nodeType) {
+  this.t = nodeType;
+  this.parent = null;
+  this.firstChild = null;
+  this.lastChild = null;
+  this.prev = null;
+  this.next = null;
+  this.pos = {};
+}
+
+Node.prototype.isContainer = function() {
+  return isContainer(this);
+};
+
+Node.prototype.appendChild = function(child) {
+  child.unlink();
+  child.parent = this;
+  if (this.lastChild) {
+    this.lastChild.next = child;
+    child.prev = this.lastChild;
+    this.lastChild = child;
+  } else {
+    this.firstChild = child;
+    this.lastChild = child;
+  }
+};
+
+Node.prototype.prependChild = function(child) {
+  child.unlink();
+  child.parent = this;
+  if (this.firstChild) {
+    this.firstChild.prev = child;
+    child.next = this.firstChild;
+    this.firstChild = child;
+  } else {
+    this.firstChild = child;
+    this.lastChild = child;
+  }
+};
+
+Node.prototype.unlink = function() {
+  if (this.prev) {
+    this.prev.next = this.next;
+  } else if (this.parent) {
+    this.parent.firstChild = this.next;
+  }
+  if (this.next) {
+    this.next.prev = this.prev;
+  } else if (this.parent) {
+    this.parent.lastChild = this.prev;
+  }
+  this.parent = null;
+  this.next = null;
+  this.prev = null;
+};
+
+Node.prototype.insertAfter = function(sibling) {
+  sibling.unlink();
+  sibling.next = this.next;
+  if (sibling.next) {
+      sibling.next.prev = sibling;
+  }
+  sibling.prev = this;
+  this.next = sibling;
+  sibling.parent = this.parent;
+  if (!sibling.next) {
+    sibling.parent.lastChild = sibling;
+  }
+};
+
+Node.prototype.insertBefore = function(sibling) {
+  sibling.unlink();
+  sibling.prev = this.prev;
+  if (sibling.prev) {
+    sibling.prev.next = sibling;
+  }
+  sibling.next = this;
+  this.prev = sibling;
+  sibling.parent = this.parent;
+  if (!sibling.prev) {
+    sibling.parent.firstChild = sibling;
+  }
+};
+
+Node.prototype.walker = function() {
+  var walker = new NodeWalker(this);
+  return walker;
+};
+
+Node.prototype.toAST = function() {
+  var children;
+  var cur;
+  var result = { t: this.t };
+
+  var propsToShow = ['t', 'c', 'list_data', 'string_content',
+                     'pos', 'start_column', 'end_column',
+                     'tight', 'info'];
+
+  for (var i = 0; i < propsToShow.length; i++) {
+      var prop = propsToShow[i];
+      if (this[prop] !== undefined) {
+          result[prop] = this[prop];
+      }
+  }
+
+  if (isContainer(this)) {
+    children = [];
+    if (this.firstChild) {
+      cur = this.firstChild;
+      while (cur) {
+        // TODO avoid recursion here...
+        children.push(cur.toAST());
+        cur = cur.next;
+      }
+      result.children = children;
+    }
+  }
+  return result;
+
+};
+
+module.exports = Node;
+
+
+/* Example of use of walker:
+
+ var walker = w.walker();
+ var event;
+
+ while (event = walker.next()) {
+   console.log(event.entering, event.node.t);
+ }
+
+*/
-- 
cgit v1.2.3