path: root/js/stmd.js

// stmd.js - CommomMark in javascript
// Copyright (C) 2014 John MacFarlane
// License: BSD3.

// Basic usage:
//
// var stmd = require('stmd');
// var parser = new stmd.DocParser();
// var renderer = new stmd.HtmlRenderer();
// console.log(renderer.render(parser.parse('Hello *world*')));

(function(exports) {

// Some regexps used in inline parser:

var ESCAPABLE = '[!"#$%&\'()*+,./:;<=>?@[\\\\\\]^_`{|}~-]';
var ESCAPED_CHAR = '\\\\' + ESCAPABLE;
var IN_DOUBLE_QUOTES = '"(' + ESCAPED_CHAR + '|[^"\\x00])*"';
var IN_SINGLE_QUOTES = '\'(' + ESCAPED_CHAR + '|[^\'\\x00])*\'';
var IN_PARENS = '\\((' + ESCAPED_CHAR + '|[^)\\x00])*\\)';
var REG_CHAR = '[^\\\\()\\x00-\\x20]';
var IN_PARENS_NOSP = '\\((' + REG_CHAR + '|' + ESCAPED_CHAR + ')*\\)';
var TAGNAME = '[A-Za-z][A-Za-z0-9]*';
var BLOCKTAGNAME = '(?:article|header|aside|hgroup|iframe|blockquote|hr|body|li|map|button|object|canvas|ol|caption|output|col|p|colgroup|pre|dd|progress|div|section|dl|table|td|dt|tbody|embed|textarea|fieldset|tfoot|figcaption|th|figure|thead|footer|footer|tr|form|ul|h1|h2|h3|h4|h5|h6|video|script|style)';
var ATTRIBUTENAME = '[a-zA-Z_:][a-zA-Z0-9:._-]*';
var UNQUOTEDVALUE = "[^\"'=<>`\\x00-\\x20]+";
var SINGLEQUOTEDVALUE = "'[^']*'";
var DOUBLEQUOTEDVALUE = '"[^"]*"';
var ATTRIBUTEVALUE = "(?:" + UNQUOTEDVALUE + "|" + SINGLEQUOTEDVALUE + "|" + DOUBLEQUOTEDVALUE + ")";
var ATTRIBUTEVALUESPEC = "(?:" + "\\s*=" + "\\s*" + ATTRIBUTEVALUE + ")";
var ATTRIBUTE = "(?:" + "\\s+" + ATTRIBUTENAME + ATTRIBUTEVALUESPEC + "?)";
var OPENTAG = "<" + TAGNAME + ATTRIBUTE + "*" + "\\s*/?>";
var CLOSETAG = "</" + TAGNAME + "\\s*[>]";
var OPENBLOCKTAG = "<" + BLOCKTAGNAME + ATTRIBUTE + "*" + "\\s*/?>";
var CLOSEBLOCKTAG = "</" + BLOCKTAGNAME + "\\s*[>]";
var HTMLCOMMENT = "<!--([^-]+|[-][^-]+)*-->";
var PROCESSINGINSTRUCTION = "[<][?].*?[?][>]";
var DECLARATION = "<![A-Z]+" + "\\s+[^>]*>";
var CDATA = "<!\\[CDATA\\[([^\\]]+|\\][^\\]]|\\]\\][^>])*\\]\\]>";
var HTMLTAG = "(?:" + OPENTAG + "|" + CLOSETAG + "|" + HTMLCOMMENT + "|" +
           PROCESSINGINSTRUCTION + "|" + DECLARATION + "|" + CDATA + ")";
var HTMLBLOCKOPEN = "<(?:" + BLOCKTAGNAME + "[\\s/>]" + "|" +
    "/" + BLOCKTAGNAME + "[\\s>]" + "|" + "[?!])";

var reHtmlTag = new RegExp('^' + HTMLTAG, 'i');

var reHtmlBlockOpen = new RegExp('^' + HTMLBLOCKOPEN, 'i');

var reLinkTitle = new RegExp(
    '^(?:"(' + ESCAPED_CHAR + '|[^"\\x00])*"' +
    '|' +
    '\'(' + ESCAPED_CHAR + '|[^\'\\x00])*\'' +
    '|' +
    '\\((' + ESCAPED_CHAR + '|[^)\\x00])*\\))');

var reLinkDestinationBraces = new RegExp(
    '^(?:[<](?:[^<>\\n\\\\\\x00]' + '|' + ESCAPED_CHAR + '|' + '\\\\)*[>])');

var reLinkDestination = new RegExp(
    '^(?:' + REG_CHAR + '+|' + ESCAPED_CHAR + '|' + IN_PARENS_NOSP + ')*');

var reEscapable = new RegExp(ESCAPABLE);

var reAllEscapedChar = new RegExp('\\\\(' + ESCAPABLE + ')', 'g');

var reEscapedChar = new RegExp('^\\\\(' + ESCAPABLE + ')');

var reAllTab = /\t/g;

var reHrule = /^(?:(?:\* *){3,}|(?:_ *){3,}|(?:- *){3,}) *$/;

// Matches a character with a special meaning in markdown,
// or a string of non-special characters.  Note:  we match
// clumps of _ or * or `, because they need to be handled in groups.
var reMain = /^(?:[_*`\n]+|[\[\]\\!<&*_]|(?: *[^\n `\[\]\\!<&*_]+)+|[ \n]+)/m;

// UTILITY FUNCTIONS

// Replace backslash escapes with literal characters.
var unescape = function(s) {
  return s.replace(reAllEscapedChar, '$1');
};

// Returns true if string contains only space characters.
var isBlank = function(s) {
  return /^\s*$/.test(s);
};

// Normalize reference label: collapse internal whitespace
// to single space, remove leading/trailing whitespace, case fold.
var normalizeReference = function(s) {
  return s.trim()
          .replace(/\s+/,' ')
          .toUpperCase();
};

// Attempt to match a regex in string s at offset offset.
// Return index of match or null.
var matchAt = function(re, s, offset) {
  var res = s.slice(offset).match(re);
  if (res) {
    return offset + res.index;
  } else {
    return null;
  }
};

// Convert tabs to spaces on each line using a 4-space tab stop.
var detabLine = function(text) {
  if (text.indexOf('\t') == -1) {
    return text;
  } else {
    var lastStop = 0;
    return text.replace(reAllTab, function(match, offset) {
      var result = '    '.slice((offset - lastStop) % 4);
      lastStop = offset + 1;
      return result;
    });
  }
};

// INLINE PARSER

// These are methods of an InlineParser object, defined below.
// An InlineParser keeps track of a subject (a string to be
// parsed) and a position in that subject.

// If re matches at current position in the subject, advance
// position in subject and return the match; otherwise return null.
var match = function(re) {
  var match = re.exec(this.subject.slice(this.pos));
  if (match) {
    this.pos += match.index + match[0].length;
    return match[0];
  } else {
    return null;
  }
};

// Returns the character at the current subject position, or null if
// there are no more characters.
var peek = function() {
  return this.subject[this.pos] || null;
};

// Parse zero or more space characters, including at most one newline
var spnl = function() {
  this.match(/^ *(?:\n *)?/);
  return 1;
};

// All of the parsers below try to match something at the current position
// 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
// literal sequence of backticks.
var parseBackticks = function() {
  var startpos = this.pos;
  var ticks = this.match(/^`+/);
  if (!ticks) {
    return 0;
  }
  var afterOpenTicks = this.pos;
  var foundCode = false;
  var match;
  while (!foundCode && (match = this.match(/`+/m))) {
    if (match == ticks) {
      return { t: 'Code', c: this.subject.slice(afterOpenTicks,
                                   this.pos - ticks.length)
             .replace(/[ \n]+/g,' ')
             .trim() };
    }
  }
  // If we got here, we didn't match a closing backtick sequence.
  this.pos = afterOpenTicks;
  return { t: 'Str', c: ticks };
};

// 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() {
  var subj = this.subject,
      pos  = this.pos;
  if (subj[pos] === '\\') {
    if (subj[pos + 1] === '\n') {
      this.pos = this.pos + 2;
      return { t: 'Hardbreak' };
    } else if (reEscapable.test(subj[pos + 1])) {
      this.pos = this.pos + 2;
      return { t: 'Str', c: subj[pos + 1] };
    } else {
      this.pos++;
      return {t: 'Str', c: '\\'};
    }
  } else {
    return null;
  }
};

// Attempt to parse an autolink (URL or email in pointy brackets).
var parseAutolink = function() {
  var m;
  var dest;
  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);
    return {t: 'Link',
            label: [{ t: 'Str', c: dest }],
            destination: 'mailto:' + dest };
  } 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);
    return { t: 'Link',
             label: [{ t: 'Str', c: dest }],
             destination: dest };
  } else {
    return null;
  }
};

// Attempt to parse a raw HTML tag.
var parseHtmlTag = function() {
  var m = this.match(reHtmlTag);
  if (m) {
    return { t: 'Html', c: m };
  } else {
    return null;
  }
};

// Scan a sequence of characters == c, and return information about
// the number of delimiters and whether they are positioned such that
// they can open and/or close emphasis or strong emphasis.  A utility
// function for strong/emph parsing.
var scanDelims = function(c) {
  var numdelims = 0;
  var first_close_delims = 0;
  var char_before, char_after;
  var startpos = this.pos;

  char_before = this.pos === 0 ? '\n' :
    this.subject[this.pos - 1];

  while (this.peek() === c) {
    numdelims++;
    this.pos++;
  }

  char_after = this.peek() || '\n';

  var can_open = numdelims > 0 && numdelims <= 3 && !(/\s/.test(char_after));
  var can_close = numdelims > 0 && numdelims <= 3 && !(/\s/.test(char_before));
  if (c === '_') {
    can_open = can_open && !((/[a-z0-9]/i).test(char_before));
    can_close = can_close && !((/[a-z0-9]/i).test(char_after));
  }
  this.pos = startpos;
  return { numdelims: numdelims,
           can_open: can_open,
           can_close: can_close };
};

// Attempt to parse emphasis or strong emphasis.
var parseEmphasis = function() {
  var startpos = this.pos;
  var c ;
  var first_close = 0;
  var c = this.peek();
  if (!(c === '*' || c === '_')) {
    return null;
  }

  var numdelims;
  var delimpos;
  var inlines = [];

  // Get opening delimiters.
  res = this.scanDelims(c);
  numdelims = res.numdelims;

  if (numdelims === 0) {
    this.pos = startpos;
    return null;
  }

  if (numdelims >= 4 || !res.can_open) {
      this.pos += numdelims;
      return {t: 'Str', c: this.subject.slice(startpos, startpos + numdelims)};
  }

  this.pos += numdelims;

  var next_inline;
  var last_closer = null;

  var delims_to_match = numdelims;
  while (this.last_closer === null || this.last_closer >= this.pos) {
        res = this.scanDelims(c);
        numclosedelims = res.numdelims;
        if (res.can_close) {
            if (last_closer < this.pos) {
                last_closer = this.pos;
            }
            if (numclosedelims === 3 && delims_to_match === 3) {
                this.pos += 3;
                this.last_closer = null;
                return {t: 'Strong', c: [{t: 'Emph', c: inlines}]};
            } else if (numclosedelims >= 2 && delims_to_match >= 2) {
                delims_to_match -= 2;
                this.pos += 2;
                inlines = [{t: 'Strong', c: inlines}];
            } else if (numclosedelims >= 1 && delims_to_match >= 1) {
                delims_to_match -= 1;
                this.pos += 1;
                inlines = [{t: 'Emph', c: inlines}];
            }
            if (delims_to_match === 0) {
                this.last_closer = null;
                return inlines[0];
            }
        } else if (next_inline = this.parseInline()) {
            inlines.push(next_inline);
        } else {
            break;
        }
    }

    // didn't find closing delimiter
    this.pos = startpos + numdelims;
    if (last_closer === null) {
        this.last_closer = startpos;
    } else {
        this.last_closer = last_closer;
    }
    return {t: 'Str', c: this.subject.slice(startpos, startpos + numdelims)};
};

// Attempt to parse link title (sans quotes), returning the string
// or null if no match.
var parseLinkTitle = function() {
  var title = this.match(reLinkTitle);
  if (title) {
    // chop off quotes from title and unescape:
    return unescape(title.substr(1, title.length - 2));
  } else {
    return null;
  }
};

// Attempt to parse link destination, returning the string or
// null if no match.
var parseLinkDestination = function() {
  var res = this.match(reLinkDestinationBraces);
  if (res) {  // chop off surrounding <..>:
    return unescape(res.substr(1, res.length - 2));
  } else {
    res = this.match(reLinkDestination);
    if (res !== null) {
      return unescape(res);
    } else {
      return null;
    }
  }
};

// Attempt to parse a link label, returning number of characters parsed.
var parseLinkLabel = function() {
  if (this.peek() != '[') {
    return 0;
  }
  var startpos = this.pos;
  var nest_level = 0;
  if (this.label_nest_level > 0) {
    // If we've already checked to the end of this subject
    // for a label, even with a different starting [, we
    // know we won't find one here and we can just return.
    // This avoids lots of backtracking.
    // Note:  nest level 1 would be: [foo [bar]
    //        nest level 2 would be: [foo [bar [baz]
    this.label_nest_level--;
    return 0;
  }
  this.pos++;  // advance past [
  var c;
  while ((c = this.peek()) && (c != ']' || nest_level > 0)) {
    switch (c) {
      case '`':
        this.parseBackticks();
        break;
      case '<':
        this.parseAutolink() || this.parseHtmlTag() || this.parseString();
        break;
      case '[':  // nested []
        nest_level++;
        this.pos++;
        break;
      case ']':  // nested []
        nest_level--;
        this.pos++;
        break;
      case '\\':
        this.parseBackslash();
        break;
      default:
        this.parseString();
    }
  }
  if (c === ']') {
    this.label_nest_level = 0;
    this.pos++; // advance past ]
    return this.pos - startpos;
  } else {
    if (!c) {
      this.label_nest_level = nest_level;
    }
    this.pos = startpos;
    return 0;
  }
};

// Parse raw link label, including surrounding [], and return
// inline contents.  (Note:  this is not a method of InlineParser.)
var parseRawLabel = function(s) {
  // note:  parse without a refmap; we don't want links to resolve
  // in nested brackets!
  return new InlineParser().parse(s.substr(1, s.length - 2), {});
};

// Attempt to parse a link.  If successful, return the link.
var parseLink = function() {
  var startpos = this.pos;
  var reflabel;
  var n;
  var dest;
  var title;

  n = this.parseLinkLabel();
  if (n === 0) {
    return null;
  }
  var afterlabel = this.pos;
  var rawlabel = this.subject.substr(startpos, n);

  // if we got this far, we've parsed a label.
  // Try to parse an explicit link: [label](url "title")
  if (this.peek() == '(') {
    this.pos++;
    if (this.spnl() &&
        ((dest = this.parseLinkDestination()) !== null) &&
        this.spnl() &&
        // make sure there's a space before the title:
        (/^\s/.test(this.subject[this.pos - 1]) &&
         (title = this.parseLinkTitle() || '') || true) &&
        this.spnl() &&
        this.match(/^\)/)) {
        return { t: 'Link',
                 destination: dest,
                 title: title,
                 label: parseRawLabel(rawlabel) };
     } else {
        this.pos = startpos;
        return null;
     }
  }
  // If we're here, it wasn't an explicit link. Try to parse a reference link.
  // first, see if there's another label
  var savepos = this.pos;
  this.spnl();
  var beforelabel = this.pos;
  n = this.parseLinkLabel();
  if (n == 2) {
    // empty second label
    reflabel = rawlabel;
  } else if (n > 0) {
    reflabel = this.subject.slice(beforelabel, beforelabel + n);
  } else {
    this.pos = savepos;
    reflabel = rawlabel;
  }
  // lookup rawlabel in refmap
  var link = this.refmap[normalizeReference(reflabel)];
  if (link) {
    return {t: 'Link',
            destination: link.destination,
            title: link.title,
            label: parseRawLabel(rawlabel) };
  } else {
      this.pos = startpos;
      return null;
  }
  // Nothing worked, rewind:
  this.pos = startpos;
  return null;
};

// Attempt to parse an entity, return Entity object if successful.
var parseEntity = function() {
  var m;
  if ((m = this.match(/^&(?:#x[a-f0-9]{1,8}|#[0-9]{1,8}|[a-z][a-z0-9]{1,31});/i))) {
      return { t: 'Entity', c: m };
  } else {
      return  null;
  }
};

// Parse a run of ordinary characters, or a single character with
// a special meaning in markdown, as a plain string, adding to inlines.
var parseString = function() {
  var m;
  if (m = this.match(reMain)) {
    return { t: 'Str', c: m };
  } else {
    return null;
  }
};

// Parse a newline.  If it was preceded by two spaces, return a hard
// line break; otherwise a soft line break.
var parseNewline = function() {
  var m = this.match(/^ *\n/);
  if (m) {
      if (m.length > 2) {
          return { t: 'Hardbreak' };
      } else if (m.length > 0) {
          return { t: 'Softbreak' };
      }
  }
  return null;
};

// Attempt to parse an image.  If the opening '!' is not followed
// by a link, return a literal '!'.
var parseImage = function() {
  if (this.match(/^!/)) {
    var link = this.parseLink();
    if (link) {
      link.t = 'Image';
      return link;
    } else {
      return { t: 'Str', c: '!' };
    }
  } else {
      return null;
  }
};

// Attempt to parse a link reference, modifying refmap.
var parseReference = function(s, refmap) {
  this.subject = s;
  this.pos = 0;
  var rawlabel;
  var dest;
  var title;
  var matchChars;
  var startpos = this.pos;
  var match;

  // label:
  matchChars = this.parseLinkLabel();
  if (matchChars === 0) {
    return 0;
  } else {
    rawlabel = this.subject.substr(0, matchChars);
  }

  // colon:
  if (this.peek() === ':') {
    this.pos++;
  } else {
    this.pos = startpos;
    return 0;
  }

  //  link url
  this.spnl();

  dest = this.parseLinkDestination();
  if (dest === null || dest.length === 0) {
    this.pos = startpos;
    return 0;
  }

  var beforetitle = this.pos;
  this.spnl();
  title = this.parseLinkTitle();
  if (title === null) {
    title = '';
    // rewind before spaces
    this.pos = beforetitle;
  }

  // make sure we're at line end:
  if (this.match(/^ *(?:\n|$)/) === null) {
    this.pos = startpos;
    return 0;
  }

  var normlabel = normalizeReference(rawlabel);

  if (!refmap[normlabel]) {
    refmap[normlabel] = { destination: dest, title: title };
  }
  return this.pos - startpos;
};

// Parse the next inline element in subject, advancing subject position
// and returning the inline parsed.
var parseInline = function() {
  var startpos = this.pos;
  var memoized = this.memo[startpos];
  if (memoized) {
      this.pos = memoized.endpos;
      return memoized.inline;
  }
  var c = this.peek();
  if (!c) {
      return null;
  }
  var res;
  switch(c) {
  case '\n':
  case ' ':
    res = this.parseNewline();
    break;
  case '\\':
    res = this.parseBackslash();
    break;
  case '`':
    res = this.parseBackticks();
    break;
  case '*':
  case '_':
    res = this.parseEmphasis();
    break;
  case '[':
    res = this.parseLink();
    break;
  case '!':
    res = this.parseImage();
    break;
  case '<':
    res = this.parseAutolink() || this.parseHtmlTag();
    break;
  case '&':
    res = this.parseEntity();
    break;
  default:
    res = this.parseString();
    break;
  }
  if (res === null) {
    this.pos += 1;
    res = {t: 'Str', c: c};
  }
  if (res) {
    this.memo[startpos] = { inline: res,
                            endpos: this.pos };
  }
  return res;
};

// Parse s as a list of inlines, using refmap to resolve references.
var parseInlines = function(s, refmap) {
  this.subject = s;
  this.pos = 0;
  this.refmap = refmap || {};
  this.memo = {};
  this.last_closer = null;
  var inlines = [];
  var next_inline;
  while (next_inline = this.parseInline()) {
      inlines.push(next_inline);
  }
  return inlines;
};

// The InlineParser object.
function InlineParser(){
  return {
    subject: '',
    label_nest_level: 0, // used by parseLinkLabel method
    pos: 0,
    refmap: {},
    memo: {},
    last_closer: null,
    match: match,
    peek: peek,
    spnl: spnl,
    parseBackticks: parseBackticks,
    parseBackslash: parseBackslash,
    parseAutolink: parseAutolink,
    parseHtmlTag: parseHtmlTag,
    scanDelims: scanDelims,
    parseEmphasis: parseEmphasis,
    parseLinkTitle: parseLinkTitle,
    parseLinkDestination: parseLinkDestination,
    parseLinkLabel: parseLinkLabel,
    parseLink: parseLink,
    parseEntity: parseEntity,
    parseString: parseString,
    parseNewline: parseNewline,
    parseImage: parseImage,
    parseReference: parseReference,
    parseInline: parseInline,
    parse: parseInlines
  };
}

// DOC PARSER

// 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: [],
           inline_content: []
        };
};

// Returns true if parent block can contain child block.
var canContain = function(parent_type, child_type) {
  return ( parent_type == 'Document' ||
           parent_type == 'BlockQuote' ||
           parent_type == 'ListItem' ||
           (parent_type == 'List' && child_type == 'ListItem') );
};

// Returns true if block type can accept lines of text.
var acceptsLines = function(block_type) {
  return ( block_type == 'Paragraph' ||
           block_type == 'IndentedCode' ||
           block_type == 'FencedCode' );
};

// 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) {
    return true;
  }
  if ((block.t == 'List' || block.t == 'ListItem') && block.children.length > 0) {
    return endsWithBlankLine(block.children[block.children.length - 1]);
  } else {
    return false;
  }
};

// Break out of all containing lists, resetting the tip of the
// document to the parent of the highest list, and finalizing
// all the lists.  (This is used to implement the "two blank lines
// break of of all lists" feature.)
var breakOutOfLists = function(block, line_number) {
  var b = block;
  var last_list = null;
  do {
    if (b.t === 'List') {
      last_list = b;
    }
    b = b.parent;
  } while (b);

  if (last_list) {
    while (block != last_list) {
      this.finalize(block, line_number);
      block = block.parent;
    }
    this.finalize(last_list, line_number);
    this.tip = last_list.parent;
  }
};

// Add a line to the block at the tip.  We assume the tip
// can accept lines -- that check should be done before calling this.
var addLine = function(ln, offset) {
  var s = ln.slice(offset);
  if (!(this.tip.open)) {
    throw({ msg: "Attempted to add line (" + ln + ") to closed container." });
  }
  this.tip.strings.push(s);
};

// Add block of type tag as a child of the tip.  If the tip can't
// accept children, close and finalize it and try its parent,
// and so on til we find a block that can accept children.
var addChild = function(tag, line_number, offset) {
  while (!canContain(this.tip.t, tag)) {
    this.finalize(this.tip, line_number);
  }

  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 = newBlock;
  return newBlock;
};

// Parse a list marker and return data on the marker (type,
// start, delimiter, bullet character, padding) or null.
var parseListMarker = function(ln, offset) {
  var rest = ln.slice(offset);
  var match;
  var spaces_after_marker;
  var data = {};
  if (rest.match(reHrule)) {
    return null;
  }
  if ((match = rest.match(/^[*+-]( +|$)/))) {
    spaces_after_marker = match[1].length;
    data.type = 'Bullet';
    data.bullet_char = match[0][0];

  } else if ((match = rest.match(/^(\d+)([.)])( +|$)/))) {
    spaces_after_marker = match[3].length;
    data.type = 'Ordered';
    data.start = parseInt(match[1]);
    data.delimiter = match[2];
  } else {
    return null;
  }
  var blank_item = match[0].length === rest.length;
  if (spaces_after_marker >= 5 ||
      spaces_after_marker < 1 ||
      blank_item) {
        data.padding = match[0].length - spaces_after_marker + 1;
  } else {
        data.padding = match[0].length;
  }
  return data;
};

// Returns true if the two list items are of the same type,
// with the same delimiter and bullet character.  This is used
// in agglomerating list items into lists.
var listsMatch = function(list_data, item_data) {
  return (list_data.type === item_data.type &&
          list_data.delimiter === item_data.delimiter &&
          list_data.bullet_char === item_data.bullet_char);
};

// Analyze a line of text and update the document appropriately.
// We parse markdown text by calling this on each line of input,
// then finalizing the document.
var incorporateLine = function(ln, line_number) {

  var all_matched = true;
  var last_child;
  var first_nonspace;
  var offset = 0;
  var match;
  var data;
  var blank;
  var indent;
  var last_matched_container;
  var i;
  var CODE_INDENT = 4;

  var container = this.doc;
  var oldtip = this.tip;

  // Convert tabs to spaces:
  ln = detabLine(ln);

  // 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) {
      break;
    }
    container = last_child;

    match = matchAt(/[^ ]/, ln, offset);
    if (match === null) {
      first_nonspace = ln.length;
      blank = true;
    } else {
      first_nonspace = match;
      blank = false;
    }
    indent = first_nonspace - offset;

    switch (container.t) {
      case 'BlockQuote':
        var matched = indent <= 3 && ln[first_nonspace] === '>';
        if (matched) {
          offset = first_nonspace + 1;
          if (ln[offset] === ' ') {
            offset++;
          }
        } else {
          all_matched = false;
        }
        break;

      case 'ListItem':
        if (indent >= container.list_data.marker_offset +
                      container.list_data.padding) {
          offset += container.list_data.marker_offset +
                    container.list_data.padding;
        } else if (blank) {
          offset = first_nonspace;
        } else {
          all_matched = false;
        }
        break;

      case 'IndentedCode':
        if (indent >= CODE_INDENT) {
          offset += CODE_INDENT;
        } else if (blank) {
          offset = first_nonspace;
        } else {
          all_matched = false;
        }
        break;

      case 'ATXHeader':
      case 'SetextHeader':
      case 'HorizontalRule':
        // a header can never container > 1 line, so fail to match:
        all_matched = false;
        break;

      case 'FencedCode':
        // skip optional spaces of fence offset
        i = container.fence_offset;
        while (i > 0 && ln[offset] === ' ') {
          offset++;
          i--;
        }
        break;

      case 'HtmlBlock':
        if (blank) {
          all_matched = false;
        }
        break;

      case 'Paragraph':
        if (blank) {
          container.last_line_blank = true;
          all_matched = false;
        }
        break;

      default:
    }

    if (!all_matched) {
      container = container.parent; // back up to last matching block
      break;
    }
  }

  last_matched_container = container;

  // This function is used to finalize and close any unmatched
  // blocks.  We aren't ready to do this now, because we might
  // have a lazy paragraph continuation, in which case we don't
  // want to close unmatched blocks.  So we store this closure for
  // use later, when we have more information.
  var closeUnmatchedBlocks = function(mythis) {
    // finalize any blocks not matched
    while (!already_done && oldtip != last_matched_container) {
      mythis.finalize(oldtip, line_number);
      oldtip = oldtip.parent;
    }
    var already_done = true;
  };

  // Check to see if we've hit 2nd blank line; if so break out of list:
  if (blank && container.last_line_blank) {
    this.breakOutOfLists(container, line_number);
  }

  // Unless last matched container is a code block, try new container starts,
  // adding children to the last matched container:
  while (container.t != 'FencedCode' &&
         container.t != 'IndentedCode' &&
         container.t != 'HtmlBlock' &&
         // this is a little performance optimization:
         matchAt(/^[ #`~*+_=<>0-9-]/,ln,offset) !== null) {

    match = matchAt(/[^ ]/, ln, offset);
    if (match === null) {
      first_nonspace = ln.length;
      blank = true;
    } else {
      first_nonspace = match;
      blank = false;
    }
    indent = first_nonspace - offset;

    if (indent >= CODE_INDENT) {
      // indented code
      if (this.tip.t != 'Paragraph' && !blank) {
        offset += CODE_INDENT;
        closeUnmatchedBlocks(this);
        container = this.addChild('IndentedCode', line_number, offset);
      } else { // indent > 4 in a lazy paragraph continuation
        break;
      }

    } else if (ln[first_nonspace] === '>') {
      // blockquote
      offset = first_nonspace + 1;
      // optional following space
      if (ln[offset] === ' ') {
        offset++;
      }
      closeUnmatchedBlocks(this);
      container = this.addChild('BlockQuote', line_number, offset);

    } else if ((match = ln.slice(first_nonspace).match(/^#{1,6}(?: +|$)/))) {
      // ATX header
      offset = first_nonspace + match[0].length;
      closeUnmatchedBlocks(this);
      container = this.addChild('ATXHeader', line_number, first_nonspace);
      container.level = match[0].trim().length; // number of #s
      // remove trailing ###s:
      container.strings =
            [ln.slice(offset).replace(/(?:(\\#) *#*| *#+) *$/,'$1')];
      break;

    } else if ((match = ln.slice(first_nonspace).match(/^`{3,}(?!.*`)|^~{3,}(?!.*~)/))) {
      // fenced code block
      var fence_length = match[0].length;
      closeUnmatchedBlocks(this);
      container = this.addChild('FencedCode', line_number, first_nonspace);
      container.fence_length = fence_length;
      container.fence_char = match[0][0];
      container.fence_offset = first_nonspace - offset;
      offset = first_nonspace + fence_length;
      break;

    } else if (matchAt(reHtmlBlockOpen, ln, first_nonspace) !== null) {
      // html block
      closeUnmatchedBlocks(this);
      container = this.addChild('HtmlBlock', line_number, first_nonspace);
      // note, we don't adjust offset because the tag is part of the text
      break;

    } else if (container.t == 'Paragraph' &&
               container.strings.length === 1 &&
               ((match = ln.slice(first_nonspace).match(/^(?:=+|-+) *$/)))) {
      // setext header line
      closeUnmatchedBlocks(this);
      container.t = 'SetextHeader'; // convert Paragraph to SetextHeader
      container.level = match[0][0] === '=' ? 1 : 2;
      offset = ln.length;

    } else if (matchAt(reHrule, ln, first_nonspace) !== null) {
      // hrule
      closeUnmatchedBlocks(this);
      container = this.addChild('HorizontalRule', line_number, first_nonspace);
      offset = ln.length - 1;
      break;

    } else if ((data = parseListMarker(ln, first_nonspace))) {
      // list item
      closeUnmatchedBlocks(this);
      data.marker_offset = indent;
      offset = first_nonspace + data.padding;

      // add the list if needed
      if (container.t !== 'List' ||
          !(listsMatch(container.list_data, data))) {
           container = this.addChild('List', line_number, first_nonspace);
           container.list_data = data;
      }

      // add the list item
      container = this.addChild('ListItem', line_number, first_nonspace);
      container.list_data = data;

    } else {
      break;

    }

    if (acceptsLines(container.t)) {
      // if it's a line container, it can't contain other containers
      break;
    }
  }

  // What remains at the offset is a text line.  Add the text to the
  // appropriate container.

  match = matchAt(/[^ ]/, ln, offset);
  if (match === null) {
    first_nonspace = ln.length;
    blank = true;
  } else {
    first_nonspace = match;
    blank = false;
  }
  indent = first_nonspace - offset;

  // First check for a lazy paragraph continuation:
  if (this.tip !== last_matched_container &&
      !blank &&
      this.tip.t == 'Paragraph' &&
      this.tip.strings.length > 0) {
     // lazy paragraph continuation

    this.last_line_blank = false;
    this.addLine(ln, offset);

  } else { // not a lazy continuation

    // finalize any blocks not matched
    closeUnmatchedBlocks(this);

    // Block quote lines are never blank as they start with >
    // and we don't count blanks in fenced code for purposes of tight/loose
    // lists or breaking out of lists.  We also don't set last_line_blank
    // on an empty list item.
    container.last_line_blank = blank &&
      !(container.t == 'BlockQuote' ||
        container.t == 'FencedCode' ||
        (container.t == 'ListItem' &&
         container.children.length === 0 &&
         container.start_line == line_number));

    var cont = container;
    while (cont.parent) {
      cont.parent.last_line_blank = false;
      cont = cont.parent;
    }

    switch (container.t) {
    case 'IndentedCode':
    case 'HtmlBlock':
      this.addLine(ln, offset);
      break;

    case 'FencedCode':
      // check for closing code fence:
      match = (indent <= 3 &&
               ln[first_nonspace] == container.fence_char &&
               ln.slice(first_nonspace).match(/^(?:`{3,}|~{3,})(?= *$)/));
      if (match && match[0].length >= container.fence_length) {
        // don't add closing fence to container; instead, close it:
        this.finalize(container, line_number);
      } else {
        this.addLine(ln, offset);
      }
      break;

    case 'ATXHeader':
    case 'SetextHeader':
    case 'HorizontalRule':
      // nothing to do; we already added the contents.
      break;

    default:
      if (acceptsLines(container.t)) {
        this.addLine(ln, first_nonspace);
      } else if (blank) {
        // do nothing
      } else if (container.t != 'HorizontalRule' &&
                 container.t != 'SetextHeader') {
        // create paragraph container for line
        container = this.addChild('Paragraph', line_number, first_nonspace);
        this.addLine(ln, first_nonspace);
      } else {
        console.log("Line " + line_number.toString() +
                     " with container type " + container.t +
                     " did not match any condition.");

      }
    }
  }
};

// Finalize a block.  Close it and do any necessary postprocessing,
// e.g. creating string_content from strings, setting the 'tight'
// or 'loose' status of a list, and parsing the beginnings
// of paragraphs for reference definitions.  Reset the tip to the
// parent of the closed block.
var finalize = function(block, line_number) {
  var pos;
  // don't do anything if the block is already closed
  if (!block.open) {
    return 0;
  }
  block.open = false;
  if (line_number > block.start_line) {
    block.end_line = line_number - 1;
  } else {
    block.end_line = line_number;
  }

  switch (block.t) {
  case 'Paragraph':
    block.string_content = block.strings.join('\n').replace(/^  */m,'');

    // try parsing the beginning as link reference definitions:
    while (block.string_content[0] === '[' &&
           (pos = this.inlineParser.parseReference(block.string_content,
                                                   this.refmap))) {
      block.string_content = block.string_content.slice(pos);
      if (isBlank(block.string_content)) {
        block.t = 'ReferenceDef';
        break;
      }
    }
    break;

  case 'ATXHeader':
  case 'SetextHeader':
  case 'HtmlBlock':
    block.string_content = block.strings.join('\n');
    break;

  case 'IndentedCode':
    block.string_content = block.strings.join('\n').replace(/(\n *)*$/,'\n');
    break;

  case 'FencedCode':
    // first line becomes info string
    block.info = unescape(block.strings[0].trim());
    if (block.strings.length == 1) {
      block.string_content = '';
    } else {
      block.string_content = block.strings.slice(1).join('\n') + '\n';
    }
    break;

  case 'List':
    block.tight = true; // tight by default

    var numitems = block.children.length;
    var i = 0;
    while (i < numitems) {
      var item = block.children[i];
      // check for non-final list item ending with blank line:
      var last_item = i == numitems - 1;
      if (endsWithBlankLine(item) && !last_item) {
        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)) {
          block.tight = false;
          break;
        }
        j++;
      }
      i++;
    }
    break;

  default:
    break;
  }

  this.tip = block.parent || this.top;
};

// Walk through a block & children recursively, parsing string content
// into inline content where appropriate.
var processInlines = function(block) {
  switch(block.t) {
    case 'Paragraph':
    case 'SetextHeader':
    case 'ATXHeader':
      block.inline_content =
        this.inlineParser.parse(block.string_content.trim(), this.refmap);
      block.string_content = "";
      break;
    default:
      break;
  }

  if (block.children) {
    for (var i = 0; i < block.children.length; i++) {
      this.processInlines(block.children[i]);
    }
  }

};

// The main parsing function.  Returns a parsed document AST.
var parse = function(input) {
  this.doc = makeBlock('Document', 1, 1);
  this.tip = this.doc;
  this.refmap = {};
  var lines = input.replace(/\n$/,'').split(/\r\n|\n|\r/);
  var len = lines.length;
  for (var i = 0; i < len; i++) {
    this.incorporateLine(lines[i], i+1);
  }
  while (this.tip) {
    this.finalize(this.tip, len - 1);
  }
  this.processInlines(this.doc);
  return this.doc;
};


// The DocParser object.
function DocParser(){
  return {
    doc: makeBlock('Document', 1, 1),
    tip: this.doc,
    refmap: {},
    inlineParser: new InlineParser(),
    breakOutOfLists: breakOutOfLists,
    addLine: addLine,
    addChild: addChild,
    incorporateLine: incorporateLine,
    finalize: finalize,
    processInlines: processInlines,
    parse: parse
  };
}

// HTML RENDERER

// Helper function to produce content in a pair of HTML tags.
var inTags = function(tag, attribs, contents, selfclosing) {
  var result = '<' + tag;
  if (attribs) {
    var i = 0;
    var attrib;
    while ((attrib = attribs[i]) !== undefined) {
      result = result.concat(' ', attrib[0], '="', attrib[1], '"');
      i++;
    }
  }
  if (contents) {
    result = result.concat('>', contents, '</', tag, '>');
  } else if (selfclosing) {
    result = result + ' />';
  } else {
    result = result.concat('></', tag, '>');
  }
  return result;
};

// Render an inline element as HTML.
var renderInline = function(inline) {
  var attrs;
  switch (inline.t) {
    case 'Str':
      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.c));
    case 'Strong':
      return inTags('strong', [], this.renderInlines(inline.c));
    case 'Html':
      return inline.c;
    case 'Entity':
      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.label));
    case 'Image':
      attrs = [['src', this.escape(inline.destination, true)],
                   ['alt', this.escape(this.renderInlines(inline.label))]];
      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("Uknown inline type " + inline.t);
      return "";
  }
};

// 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]);
  }
  return result;
};

// Render a single block element.
var renderBlock = function(block, in_tight_list) {
  var tag;
  var attr;
  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.inline_content);
      } else {
        return inTags('p', [], this.renderInlines(block.inline_content));
      }
      break;
    case 'BlockQuote':
      var filling = this.renderBlocks(block.children);
      return inTags('blockquote', [], filling === '' ? this.innersep :
          this.innersep + this.renderBlocks(block.children) + this.innersep);
    case 'ListItem':
      return inTags('li', [], this.renderBlocks(block.children, in_tight_list).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 'ATXHeader':
    case 'SetextHeader':
      tag = 'h' + block.level;
      return inTags(tag, [], this.renderInlines(block.inline_content));
    case 'IndentedCode':
      return inTags('pre', [],
              inTags('code', [], this.escape(block.string_content)));
    case 'FencedCode':
      info_words = 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("Uknown 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));
    }
  }
  return result.join(this.blocksep);
};

// The HtmlRenderer object.
function HtmlRenderer(){
  return {
    // default options:
    blocksep: '\n',  // space between blocks
    innersep: '\n',  // space between block container tag and contents
    softbreak: '\n', // by default, soft breaks are rendered as newlines in HTML
                     // set to "<br />" to make them hard breaks
                     // set to " " if you want to ignore line wrapping in source
    escape: function(s, preserve_entities) {
      if (preserve_entities) {
      return s.replace(/[&](?![#](x[a-f0-9]{1,8}|[0-9]{1,8});|[a-z][a-z0-9]{1,31};)/gi,'&amp;')
              .replace(/[<]/g,'&lt;')
              .replace(/[>]/g,'&gt;')
              .replace(/["]/g,'&quot;');
      } else {
      return s.replace(/[&]/g,'&amp;')
              .replace(/[<]/g,'&lt;')
              .replace(/[>]/g,'&gt;')
              .replace(/["]/g,'&quot;');
      }
    },
    renderInline: renderInline,
    renderInlines: renderInlines,
    renderBlock: renderBlock,
    renderBlocks: renderBlocks,
    render: renderBlock
  };
}

exports.DocParser = DocParser;
exports.HtmlRenderer = HtmlRenderer;

})(typeof exports === 'undefined' ? this.stmd = {} : exports);