27 Content-Disposition: inline; filename=" 58 6b8f1433347557076140afb35ef4d9f036a658f9..e564e0af5c2f7b9732e89707655068e507579a89.patch 1ffe Last-Modified: Sat, 30 May 2026 20:52:23 GMT Expires: Tue, 27 May 2036 20:52:23 GMT From e564e0af5c2f7b9732e89707655068e507579a89 Mon Sep 17 00:00:00 2001 From: John MacFarlane 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/bench.js | 2 +- js/bin/commonmark | 2 +- js/lib/blocks.js | 127 +++++++------------- js/lib/html-renderer.js | 311 +++++++++++++++++++++++++++++------------------- js/lib/index.js | 1 + js/lib/inlines.js | 257 +++++++++++++++++++-------------------- js/lib/node.js | 195 ++++++++++++++++++++++++++++++ js/test.js | 2 +- 8 files changed, 555 insertions(+), 342 deletions(-) create mode 100644 js/lib/node.js diff --git a/js/bench.js b/js/bench.js index 77f5025..a5e0d91 100644 --- a/js/bench.js +++ b/js/bench.js @@ -17,7 +17,7 @@ suite.add('commonmark.js markdown->html', function() { "use strict"; var doc = new sm.DocParser().parse(contents); var renderer = new sm.HtmlRenderer(); - renderer.renderBlock(doc); + renderer.render(doc); }) .add('showdown.js markdown->html', function() { diff --git a/js/bin/commonmark b/js/bin/commonmark index 3c222f8..ac53e6e 100755 --- a/js/bin/commonmark +++ b/js/bin/commonmark @@ -14,7 +14,7 @@ var files = []; if (process.argv[2] === '--ast') { files = process.argv.slice(3); renderer = { render: function(x) { - return util.inspect(x, null, Infinity) + '\n'; + return util.inspect(x.toAST(), null, Infinity, true) + '\n'; } }; } else { files = process.argv.slice(2); diff --git a/js/lib/blocks.js b/js/lib/blocks.js index 786c099..cc2263a 100644 --- a/js/lib/blocks.js +++ b/js/lib/blocks.js @@ -1,3 +1,5 @@ +Node = require('./node'); + var C_GREATERTHAN = 62; var C_SPACE = 32; var C_OPEN_BRACKET = 91; @@ -48,19 +50,14 @@ var reHrule = /^(?:(?:\* *){3,}|(?:_ *){3,}|(?:- *){3,}) *$/; // These are methods of a DocParser object, defined below. var makeBlock = function(tag, start_line, start_column) { - return { t: tag, - open: true, - last_line_blank: false, - start_line: start_line, - start_column: start_column, - end_line: start_line, - children: [], - parent: null, - // string_content is formed by concatenating strings, in finalize: - string_content: "", - strings: [], - children: [] - }; + var b = new Node(tag); + b.pos.start = [start_line, start_column]; + b.pos.end = []; // assigned in finalization step + b.open = true; + b.last_line_blank = false; + b.string_content = ""; + b.strings = []; + return b; }; // Returns true if parent block can contain child block. @@ -81,14 +78,17 @@ var acceptsLines = function(block_type) { // Returns true if block ends with a blank line, descending if needed // into lists and sublists. var endsWithBlankLine = function(block) { - if (block.last_line_blank) { + while (block) { + if (block.last_line_blank) { return true; + } + if (block.t === 'List' || block.t === 'ListItem') { + block = block.lastChild; + } else { + break; + } } - if ((block.t === 'List' || block.t === 'ListItem') && block.children.length > 0) { - return endsWithBlankLine(block.children[block.children.length - 1]); - } else { - return false; - } + return false; }; // Break out of all containing lists, resetting the tip of the @@ -135,8 +135,7 @@ var addChild = function(tag, line_number, offset) { var column_number = offset + 1; // offset 0 = column 1 var newBlock = makeBlock(tag, line_number, column_number); - this.tip.children.push(newBlock); - newBlock.parent = this.tip; + this.tip.appendChild(newBlock); this.tip = newBlock; return newBlock; }; @@ -190,7 +189,6 @@ var listsMatch = function(list_data, item_data) { var incorporateLine = function(ln, line_number) { var all_matched = true; - var last_child; var first_nonspace; var offset = 0; var match; @@ -210,12 +208,11 @@ var incorporateLine = function(ln, line_number) { // For each containing block, try to parse the associated line start. // Bail out on failure: container will point to the last matching block. // Set all_matched to false if not all containers match. - while (container.children.length > 0) { - last_child = container.children[container.children.length - 1]; - if (!last_child.open) { + while (container.lastChild) { + if (!container.lastChild.open) { break; } - container = last_child; + container = container.lastChild; match = matchAt(/[^ ]/, ln, offset); if (match === -1) { @@ -472,8 +469,8 @@ var incorporateLine = function(ln, line_number) { container.t === 'Header' || container.t === 'FencedCode' || (container.t === 'ListItem' && - container.children.length === 0 && - container.start_line === line_number)); + !container.firstChild && + container.pos.start[0] === line_number)); var cont = container; while (cont.parent) { @@ -537,10 +534,10 @@ var finalize = function(block, line_number) { return 0; } block.open = false; - if (line_number > block.start_line) { - block.end_line = line_number - 1; + if (line_number > block.pos.start[0]) { + block.pos.end = [line_number - 1]; // TODO end column } else { - block.end_line = line_number; + block.pos.end = [line_number]; } switch (block.t) { @@ -584,30 +581,24 @@ var finalize = function(block, line_number) { case 'List': block.tight = true; // tight by default - var numitems = block.children.length; - var i = 0; - while (i < numitems) { - var item = block.children[i]; + var item = block.firstChild; + while (item) { // check for non-final list item ending with blank line: - var last_item = i === numitems - 1; - if (endsWithBlankLine(item) && !last_item) { + if (endsWithBlankLine(item) && item.next) { block.tight = false; break; } // recurse into children of list item, to see if there are // spaces between any of them: - var numsubitems = item.children.length; - var j = 0; - while (j < numsubitems) { - var subitem = item.children[j]; - var last_subitem = j === numsubitems - 1; - if (endsWithBlankLine(subitem) && !(last_item && last_subitem)) { + var subitem = item.firstChild; + while (subitem) { + if (endsWithBlankLine(subitem) && (item.next || subitem.next)) { block.tight = false; break; } - j++; + subitem = subitem.next; } - i++; + item = item.next; } break; @@ -621,45 +612,14 @@ var finalize = function(block, line_number) { // Walk through a block & children recursively, parsing string content // into inline content where appropriate. Returns new object. var processInlines = function(block) { - var newbl 1ff6 - newblock.t = block.t; - newblock.start_line = block.start_line; - newblock.start_column = block.start_column; - newblock.end_line = block.end_line; - - switch(block.t) { - case 'Paragraph': - newblock.children = - this.inlineParser.parse(block.string_content.trim(), this.refmap); - break; - case 'Header': - newblock.children = - this.inlineParser.parse(block.string_content.trim(), this.refmap); - newblock.level = block.level; - break; - case 'List': - newblock.list_data = block.list_data; - newblock.tight = block.tight; - break; - case 'CodeBlock': - newblock.string_content = block.string_content; - newblock.info = block.info; - break; - case 'HtmlBlock': - newblock.string_content = block.string_content; - break; - default: - break; - } - - if (block.children && !newblock.children) { - var newchildren = []; - for (var i = 0; i < block.children.length; i++) { - newchildren.push(this.processInlines(block.children[i])); + var node, event; + var walker = block.walker(); + while (event = walker.next()) { + node = event.node; + if (!event.entering && (node.t == 'Paragraph' || node.t == 'Header')) { + this.inlineParser.parse(node, this.refmap); } - newblock.children = newchildren; } - return newblock; }; // The main parsing function. Returns a parsed document AST. @@ -675,7 +635,8 @@ var parse = function(input) { while (this.tip) { this.finalize(this.tip, len - 1); } - return this.processInlines(this.doc); + this.processInlines(this.doc); + return this.doc; }; diff --git a/js/lib/html-renderer.js b/js/lib/html-renderer.js index f6efe32..e7953cf 100644 --- a/js/lib/html-renderer.js +++ b/js/lib/html-renderer.js @@ -1,6 +1,6 @@ -// Helper function to produce content in a pair of HTML tags. -var inTags = function(tag, attribs, contents, selfclosing) { - var result = '<' + tag; +// Helper function to produce an HTML tag. +var tag = function(name, attribs, selfclosing) { + var result = '<' + name; if (attribs) { var i = 0; var attrib; @@ -9,132 +9,207 @@ var inTags = function(tag, attribs, contents, selfclosing) { i++; } } - if (contents) { - result = result.concat('>', contents, ''); - } else if (selfclosing) { - result = result + ' />'; - } else { - result = result.concat('>'); - } - return result; -}; - -// Render an inline element as HTML. -var renderInline = function(inline) { - var attrs; - switch (inline.t) { - case 'Text': - return this.escape(inline.c); - case 'Softbreak': - return this.softbreak; - case 'Hardbreak': - return inTags('br', [], "", true) + '\n'; - case 'Emph': - return inTags('em', [], this.renderInlines(inline.children)); - case 'Strong': - return inTags('strong', [], this.renderInlines(inline.children)); - case 'Html': - return inline.c; - case 'Link': - attrs = [['href', this.escape(inline.destination, true)]]; - if (inline.title) { - attrs.push(['title', this.escape(inline.title, true)]); - } - return inTags('a', attrs, this.renderInlines(inline.children)); - case 'Image': - attrs = [['src', this.escape(inline.destination, true)], - ['alt', this.renderInlines(inline.children). - replace(/\<[^>]*alt="([^"]*)"[^>]*\>/g, '$1'). - replace(/\<[^>]*\>/g, '')]]; - if (inline.title) { - attrs.push(['title', this.escape(inline.title, true)]); - } - return inTags('img', attrs, "", true); - case 'Code': - return inTags('code', [], this.escape(inline.c)); - default: - console.log("Unknown inline type " + inline.t); - return ""; - } -}; + if (selfclosing) + result += ' /'; -// Render a list of inlines. -var renderInlines = function(inlines) { - var result = ''; - for (var i = 0; i < inlines.length; i++) { - result = result + this.renderInline(inlines[i]); - } + result += '>'; return result; }; -// Render a single block element. -var renderBlock = function(block, in_tight_list) { - var tag; - var attr; +var renderNodes = function(block) { + + var attrs; var info_words; - switch (block.t) { - case 'Document': - var whole_doc = this.renderBlocks(block.children); - return (whole_doc === '' ? '' : whole_doc + '\n'); - case 'Paragraph': - if (in_tight_list) { - return this.renderInlines(block.children); + var tagname; + var walker = block.walker(); + var event, node, entering; + var buffer = []; + var disableTags = 0; + var grandparent; + var out = function(s) { + if (disableTags > 0) { + buffer.push(s.replace(/\<[^>]*\>/g, '')); } else { - return inTags('p', [], this.renderInlines(block.children)); - } - break; - case 'BlockQuote': - var filling = this.renderBlocks(block.children); - return inTags('blockquote', [], filling === '' ? this.innersep : - this.innersep + filling + this.innersep); - case 'ListItem': - var contents = this.renderBlocks(block.children, in_tight_list); - if (/^[<]/.test(contents)) { - contents = '\n' + contents; + buffer.push(s); } - if (/[>]$/.test(contents)) { - contents = contents + '\n'; + } + var esc = this.escape; + var cr = function() { + if (buffer.length > 0 && buffer[buffer.length - 1] !== '\n') { + out('\n'); } - return inTags('li', [], contents, false).trim(); - case 'List': - tag = block.list_data.type === 'Bullet' ? 'ul' : 'ol'; - attr = (!block.list_data.start || block.list_data.start === 1) ? - [] : [['start', block.list_data.start.toString()]]; - return inTags(tag, attr, this.innersep + - this.renderBlocks(block.children, block.tight) + - this.innersep); - case 'Header': - tag = 'h' + block.level; - return inTags(tag, [], this.renderInlines(block.children)); - case 'CodeBlock': - info_words = block.info ? block.info.split(/ +/) : []; - attr = (info_words.length === 0 || info_words[0].length === 0) ? - [] : [['class', 'language-' + this.escape(info_words[0], true)]]; - return inTags('pre', [], - inTags('code', attr, this.escape(block.string_content))); - case 'HtmlBlock': - return block.string_content; - case 'ReferenceDef': - return ""; - case 'HorizontalRule': - return inTags('hr', [], "", true); - default: - console.log("Unknown block type " + block.t); - return ""; } -}; -// Render a list of block elements, separated by this.blocksep. -var renderBlocks = function(blocks, in_tight_list) { - var result = []; - for (var i = 0; i < blocks.length; i++) { - if (blocks[i].t !== 'ReferenceDef') { - result.push(this.renderBlock(blocks[i], in_tight_list)); + while (event = walker.next()) { + entering = event.entering; + node = event.node; + + switch (node.t) { + case 'Text': + out(esc(node.c)); + break; + + case 'Softbreak': + out(this.softbreak); + break; + + case 'Hardbreak': + out(tag('br', [], true)); + cr(); + break; + + case 'Emph': + out(tag(entering ? 'em' : '/em')); + break; + + case 'Strong': + out(tag(entering ? 'strong' : '/strong')); + break; + + case 'Emph': + out(tag(entering ? 'strong' : '/strong')); + break; + + case 'Html': + out(node.c); + break; + + case 'Link': + if (enteri 51 + attrs = [['href', esc(node.destination, true)]]; + 1fec + attrs.push(['title', esc(node.title, true)]); + } + out(tag('a', attrs)); + } else { + out(tag('/a')); + } + break; + + case 'Image': + if (entering) { + if (disableTags == 0) { + out(''); + } + disableTags += 1; + } else { + disableTags -= 1; + if (disableTags == 0) { + if (node.title) { + out(''); + } + } + break; + + case 'Code': + out(tag('code') + esc(node.c) + tag('/code')); + break; + + case 'Document': + break; + + case 'Paragraph': + grandparent = node.parent.parent; + if (grandparent !== null && + grandparent.t === 'List') { + if (grandparent.tight) + break; + } + if (entering) { + cr(); + out(tag('p')); + } else { + out(tag('/p')); + cr(); + } + break; + + case 'BlockQuote': + if (entering) { + cr(); + out(tag('blockquote')); + cr(); + } else { + cr(); + out(tag('/blockquote')); + cr(); + } + break; + + case 'ListItem': + if (entering) { + out(tag('li')); + } else { + out(tag('/li')); + cr(); + } + break; + + case 'List': + tagname = node.list_data.type === 'Bullet' ? 'ul' : 'ol'; + if (entering) { + attr = (!node.list_data.start || node.list_data.start === 1) ? + [] : [['start', node.list_data.start.toString()]]; + cr(); + out(tag(tagname, attr)); + cr(); + } else { + cr(); + out(tag('/' + tagname)); + cr(); + } + break; + + case 'Header': + tagname = 'h' + node.level; + if (entering) { + cr(); + out(tag(tagname)); + } else { + out(tag('/' + tagname)); + cr(); + } + break; + + case 'CodeBlock': + info_words = node.info ? node.info.split(/ +/) : []; + attr = (info_words.length === 0 || info_words[0].length === 0) + ? [] : [['class', 'language-' + esc(info_words[0], true)]]; + cr(); + out(tag('pre') + tag('code', attr)); + out(this.escape(node.string_content)); + out(tag('/code') + tag('/pre')); + cr(); + break; + + case 'HtmlBlock': + cr(); + out(node.string_content); + cr(); + break; + + case 'HorizontalRule': + cr(); + out(tag('hr', [], true)); + cr(); + break; + + + case 'ReferenceDef': + break; + + default: + console.log("Unknown node type " + node.t); } + } - return result.join(this.blocksep); + return buffer.join(''); }; + // The HtmlRenderer object. function HtmlRenderer(){ return { @@ -157,11 +232,7 @@ function HtmlRenderer(){ .replace(/["]/g, '"'); } }, - renderInline: renderInline, - renderInlines: renderInlines, - renderBlock: renderBlock, - renderBlocks: renderBlocks, - render: renderBlock + render: renderNodes }; } diff --git a/js/lib/index.js b/js/lib/index.js index 4e04532..b2388ce 100755 --- a/js/lib/index.js +++ b/js/lib/index.js @@ -17,6 +17,7 @@ var renderAST = function(tree) { return util.inspect(tree, {depth: null}); }; +module.exports.Node = require('./node'); module.exports.DocParser = require('./blocks'); module.exports.HtmlRenderer = require('./html-renderer'); module.exports.ASTRenderer = renderAST; diff --git a/js/lib/inlines.js b/js/lib/inlines.js index ef7a00f..23b2b1e 100644 --- a/js/lib/inlines.js +++ b/js/lib/inlines.js @@ -85,6 +85,12 @@ var normalizeReference = function(s) { .toUpperCase(); }; +var text = function(s) { + var node = new Node('Text'); + node.c = s; + return node; +} + // INLINE PARSER // These are methods of an InlineParser object, defined below. @@ -123,9 +129,9 @@ var spnl = function() { // in the subject. If they succeed in matching anything, they // return the inline matched, advancing the subject. -// Attempt to parse backticks, returning either a backtick code span or a +// Attempt to parse backticks, adding either a backtick code span or a // literal sequence of backticks. -var parseBackticks = function(inlines) { +var parseBackticks = function(block) { var ticks = this.match(/^`+/); if (!ticks) { return 0; @@ -133,37 +139,42 @@ var parseBackticks = function(inlines) { var afterOpenTicks = this.pos; var foundCode = false; var matched; + var node; while (!foundCode && (matched = this.match(/`+/m))) { if (matched === ticks) { - inlines.push({ t: 'Code', c: this.subject.slice(afterOpenTicks, - this.pos - ticks.length) - .replace(/[ \n]+/g, ' ') - .trim() }); + node = new Node('Code'); + node.c = this.subject.slice(afterOpenTicks, + this.pos - ticks.length) + .replace(/[ \n]+/g, ' ') + .trim(); + block.appendChild(node); return true; } } // If we got here, we didn't match a closing backtick sequence. this.pos = afterOpenTicks; - inlines.push({ t: 'Text', c: ticks }); + block.appendChild(text(ticks)); return true; }; // Parse a backslash-escaped special character, adding either the escaped // character, a hard line break (if the backslash is followed by a newline), -// or a literal backslash to the 'inlines' list. -var parseBackslash = function(inlines) { +// or a literal backslash to the block's children. +var parseBackslash = function(block) { var subj = this.subject, pos = this.pos; + var node; if (subj.charCodeAt(pos) === C_BACKSLASH) { if (subj.charAt(pos + 1) === '\n') { this.pos = this.pos + 2; - inlines.push({ t: 'Hardbreak' }); + node = new Node('Hardbreak'); + block.appendChild(node); } else if (reEscapable.test(subj.charAt(pos + 1))) { this.pos = this.pos + 2; - inlines.push({ t: 'Text', c: subj.charAt(pos + 1) }); + block.appendChild(text(subj.charAt(pos + 1))); } else { this.pos++; - inlines.push({t: 'Text', c: '\\'}); + block.appendChild(text('\\')); } return true; } else { @@ -172,22 +183,23 @@ var parseBackslash = function(inlines) { }; // Attempt to parse an autolink (URL or email in pointy brackets). -var parseAutolink = function(inlines) { +var parseAutolink = function(block) { var m; var dest; + var node; if ((m = this.match(/^<([a-zA-Z0-9.!#$%&'*+\/=?^_`{|}~-]+@[a-zA-Z0-9](?:[a-zA-Z0-9-]{0,61}[a-zA-Z0-9])?(?:\.[a-zA-Z0-9](?:[a-zA-Z0-9-]{0,61}[a-zA-Z0-9])?)*)>/))) { // email autolink dest = m.slice(1, -1); - inlines.push( - {t: 'Link', - children: [{ t: 'Text', c: dest }], - destination: 'mailto:' + encodeURI(unescape(dest)) }); + node = new Node('Link'); + node.destination = 'mailto:' + enc 1fe8 + node.appendChild(text(dest)); + block.appendChild(node); return true; } else if ((m = this.match(/^<(?:coap|doi|javascript|aaa|aaas|about|acap|cap|cid|crid|data|dav|dict|dns|file|ftp|geo|go|gopher|h323|http|https|iax|icap|im|imap|info|ipp|iris|iris.beep|iris.xpc|iris.xpcs|iris.lwz|ldap|mailto|mid|msrp|msrps|mtqp|mupdate|news|nfs|ni|nih|nntp|opaquelocktoken|pop|pres|rtsp|service|session|shttp|sieve|sip|sips|sms|snmp|soap.beep|soap.beeps|tag|tel|telnet|tftp|thismessage|tn3270|tip|tv|urn|vemmi|ws|wss|xcon|xcon-userid|xmlrpc.beep|xmlrpc.beeps|xmpp|z39.50r|z39.50s|adiumxtra|afp|afs|aim|apt|attachment|aw|beshare|bitcoin|bolo|callto|chrome|chrome-extension|com-eventbrite-attendee|content|cvs|dlna-playsingle|dlna-playcontainer|dtn|dvb|ed2k|facetime|feed|finger|fish|gg|git|gizmoproject|gtalk|hcp|icon|ipn|irc|irc6|ircs|itms|jar|jms|keyparc|lastfm|ldaps|magnet|maps|market|message|mms|ms-help|msnim|mumble|mvn|notes|oid|palm|paparazzi|platform|proxy|psyc|query|res|resource|rmi|rsync|rtmp|secondlife|sftp|sgn|skype|smb|soldat|spotify|ssh|steam|svn|teamspeak|things|udp|unreal|ut2004|ventrilo|view-source|webcal|wtai|wyciwyg|xfire|xri|ymsgr):[^<>\x00-\x20]*>/i))) { dest = m.slice(1, -1); - inlines.push({ -