// Released under MIT license

// Copyright (c) 2009-2010 Dominic Baggott

// Copyright (c) 2009-2010 Ash Berlin

// Copyright (c) 2011 Christoph Dorn <christoph@christophdorn.com> (http://www.christophdorn.com)



(function( expose ) {



/**

 *  class Markdown

 *

 *  Markdown processing in Javascript done right. We have very particular views

 *  on what constitutes 'right' which include:

 *

 *  - produces well-formed HTML (this means that em and strong nesting is

 *    important)

 *

 *  - has an intermediate representation to allow processing of parsed data (We

 *    in fact have two, both as [JsonML]: a markdown tree and an HTML tree).

 *

 *  - is easily extensible to add new dialects without having to rewrite the

 *    entire parsing mechanics

 *

 *  - has a good test suite

 *

 *  This implementation fulfills all of these (except that the test suite could

 *  do with expanding to automatically run all the fixtures from other Markdown

 *  implementations.)

 *

 *  ##### Intermediate Representation

 *

 *  *TODO* Talk about this :) Its JsonML, but document the node names we use.

 *

 *  [JsonML]: http://jsonml.org/ "JSON Markup Language"

 **/

var Markdown = expose.Markdown = function Markdown(dialect) {

  switch (typeof dialect) {

    case "undefined":

      this.dialect = Markdown.dialects.Gruber;

      break;

    case "object":

      this.dialect = dialect;

      break;

    default:

      if (dialect in Markdown.dialects) {

        this.dialect = Markdown.dialects[dialect];

      }

      else {

        throw new Error("Unknown Markdown dialect '" + String(dialect) + "'");

      }

      break;

  }

  this.em_state = [];

  this.strong_state = [];

  this.debug_indent = "";

};



/**

 *  parse( markdown, [dialect] ) -> JsonML

 *  - markdown (String): markdown string to parse

 *  - dialect (String | Dialect): the dialect to use, defaults to gruber

 *

 *  Parse `markdown` and return a markdown document as a Markdown.JsonML tree.

 **/

expose.parse = function( source, dialect ) {

  // dialect will default if undefined

  var md = new Markdown( dialect );

  return md.toTree( source );

};



/**

 *  toHTML( markdown, [dialect]  ) -> String

 *  toHTML( md_tree ) -> String

 *  - markdown (String): markdown string to parse

 *  - md_tree (Markdown.JsonML): parsed markdown tree

 *

 *  Take markdown (either as a string or as a JsonML tree) and run it through

 *  [[toHTMLTree]] then turn it into a well-formated HTML fragment.

 **/

expose.toHTML = function toHTML( source , dialect , options ) {

  var input = expose.toHTMLTree( source , dialect , options );



  return expose.renderJsonML( input );

};



/**

 *  toHTMLTree( markdown, [dialect] ) -> JsonML

 *  toHTMLTree( md_tree ) -> JsonML

 *  - markdown (String): markdown string to parse

 *  - dialect (String | Dialect): the dialect to use, defaults to gruber

 *  - md_tree (Markdown.JsonML): parsed markdown tree

 *

 *  Turn markdown into HTML, represented as a JsonML tree. If a string is given

 *  to this function, it is first parsed into a markdown tree by calling

 *  [[parse]].

 **/

expose.toHTMLTree = function toHTMLTree( input, dialect , options ) {

  // convert string input to an MD tree

  if ( typeof input ==="string" ) input = this.parse( input, dialect );



  // Now convert the MD tree to an HTML tree



  // remove references from the tree

  var attrs = extract_attr( input ),

      refs = {};



  if ( attrs && attrs.references ) {

    refs = attrs.references;

  }



  var html = convert_tree_to_html( input, refs , options );

  merge_text_nodes( html );

  return html;

};



// For Spidermonkey based engines

function mk_block_toSource() {

  return "Markdown.mk_block( " +

          uneval(this.toString()) +

          ", " +

          uneval(this.trailing) +

          ", " +

          uneval(this.lineNumber) +

          " )";

}



// node

function mk_block_inspect() {

  var util = require('util');

  return "Markdown.mk_block( " +

          util.inspect(this.toString()) +

          ", " +

          util.inspect(this.trailing) +

          ", " +

          util.inspect(this.lineNumber) +

          " )";



}



var mk_block = Markdown.mk_block = function(block, trail, line) {

  // Be helpful for default case in tests.

  if ( arguments.length == 1 ) trail = "\n\n";



  var s = new String(block);

  s.trailing = trail;

  // To make it clear its not just a string

  s.inspect = mk_block_inspect;

  s.toSource = mk_block_toSource;



  if (line != undefined)

    s.lineNumber = line;



  return s;

};



function count_lines( str ) {

  var n = 0, i = -1;

  while ( ( i = str.indexOf('\n', i+1) ) !== -1) n++;

  return n;

}



// Internal - split source into rough blocks

Markdown.prototype.split_blocks = function splitBlocks( input, startLine ) {

  // [\s\S] matches _anything_ (newline or space)

  var re = /([\s\S]+?)($|\n(?:\s*\n|$)+)/g,

      blocks = [],

      m;



  var line_no = 1;



  if ( ( m = /^(\s*\n)/.exec(input) ) != null ) {

    // skip (but count) leading blank lines

    line_no += count_lines( m[0] );

    re.lastIndex = m[0].length;

  }



  while ( ( m = re.exec(input) ) !== null ) {

    blocks.push( mk_block( m[1], m[2], line_no ) );

    line_no += count_lines( m[0] );

  }



  return blocks;

};



/**

 *  Markdown#processBlock( block, next ) -> undefined | [ JsonML, ... ]

 *  - block (String): the block to process

 *  - next (Array): the following blocks

 *

 * Process `block` and return an array of JsonML nodes representing `block`.

 *

 * It does this by asking each block level function in the dialect to process

 * the block until one can. Succesful handling is indicated by returning an

 * array (with zero or more JsonML nodes), failure by a false value.

 *

 * Blocks handlers are responsible for calling [[Markdown#processInline]]

 * themselves as appropriate.

 *

 * If the blocks were split incorrectly or adjacent blocks need collapsing you

 * can adjust `next` in place using shift/splice etc.

 *

 * If any of this default behaviour is not right for the dialect, you can

 * define a `__call__` method on the dialect that will get invoked to handle

 * the block processing.

 */

Markdown.prototype.processBlock = function processBlock( block, next ) {

  var cbs = this.dialect.block,

      ord = cbs.__order__;



  if ( "__call__" in cbs ) {

    return cbs.__call__.call(this, block, next);

  }



  for ( var i = 0; i < ord.length; i++ ) {

    //D:this.debug( "Testing", ord[i] );

    var res = cbs[ ord[i] ].call( this, block, next );

    if ( res ) {

      //D:this.debug("  matched");

      if ( !isArray(res) || ( res.length > 0 && !( isArray(res[0]) ) ) )

        this.debug(ord[i], "didn't return a proper array");

      //D:this.debug( "" );

      return res;

    }

  }



  // Uhoh! no match! Should we throw an error?

  return [];

};



Markdown.prototype.processInline = function processInline( block ) {

  return this.dialect.inline.__call__.call( this, String( block ) );

};



/**

 *  Markdown#toTree( source ) -> JsonML

 *  - source (String): markdown source to parse

 *

 *  Parse `source` into a JsonML tree representing the markdown document.

 **/

// custom_tree means set this.tree to `custom_tree` and restore old value on return

Markdown.prototype.toTree = function toTree( source, custom_root ) {

  var blocks = source instanceof Array ? source : this.split_blocks( source );



  // Make tree a member variable so its easier to mess with in extensions

  var old_tree = this.tree;

  try {

    this.tree = custom_root || this.tree || [ "markdown" ];



    blocks:

    while ( blocks.length ) {

      var b = this.processBlock( blocks.shift(), blocks );



      // Reference blocks and the like won't return any content

      if ( !b.length ) continue blocks;



      this.tree.push.apply( this.tree, b );

    }

    return this.tree;

  }

  finally {

    if ( custom_root ) {

      this.tree = old_tree;

    }

  }

};



// Noop by default

Markdown.prototype.debug = function () {

  var args = Array.prototype.slice.call( arguments);

  args.unshift(this.debug_indent);

  if (typeof print !== "undefined")

      print.apply( print, args );

  if (typeof console !== "undefined" && typeof console.log !== "undefined")

      console.log.apply( null, args );

}



Markdown.prototype.loop_re_over_block = function( re, block, cb ) {

  // Dont use /g regexps with this

  var m,

      b = block.valueOf();



  while ( b.length && (m = re.exec(b) ) != null) {

    b = b.substr( m[0].length );

    cb.call(this, m);

  }

  return b;

};



/**

 * Markdown.dialects

 *

 * Namespace of built-in dialects.

 **/

Markdown.dialects = {};



/**

 * Markdown.dialects.Gruber

 *

 * The default dialect that follows the rules set out by John Gruber's

 * markdown.pl as closely as possible. Well actually we follow the behaviour of

 * that script which in some places is not exactly what the syntax web page

 * says.

 **/

Markdown.dialects.Gruber = {

  block: {

    atxHeader: function atxHeader( block, next ) {

      var m = block.match( /^(#{1,6})\s*(.*?)\s*#*\s*(?:\n|$)/ );



      if ( !m ) return undefined;



      var header = [ "header", { level: m[ 1 ].length } ];

      Array.prototype.push.apply(header, this.processInline(m[ 2 ]));



      if ( m[0].length < block.length )

        next.unshift( mk_block( block.substr( m[0].length ), block.trailing, block.lineNumber + 2 ) );



      return [ header ];

    },



    setextHeader: function setextHeader( block, next ) {

      var m = block.match( /^(.*)\n([-=])\2\2+(?:\n|$)/ );



      if ( !m ) return undefined;



      var level = ( m[ 2 ] === "=" ) ? 1 : 2;

      var header = [ "header", { level : level }, m[ 1 ] ];



      if ( m[0].length < block.length )

        next.unshift( mk_block( block.substr( m[0].length ), block.trailing, block.lineNumber + 2 ) );



      return [ header ];

    },



    code: function code( block, next ) {

      // |    Foo

      // |bar

      // should be a code block followed by a paragraph. Fun

      //

      // There might also be adjacent code block to merge.



      var ret = [],

          re = /^(?: {0,3}\t| {4})(.*)\n?/,

          lines;



      // 4 spaces + content

      if ( !block.match( re ) ) return undefined;



      block_search:

      do {

        // Now pull out the rest of the lines

        var b = this.loop_re_over_block(

                  re, block.valueOf(), function( m ) { ret.push( m[1] ); } );



        if (b.length) {

          // Case alluded to in first comment. push it back on as a new block

          next.unshift( mk_block(b, block.trailing) );

          break block_search;

        }

        else if (next.length) {

          // Check the next block - it might be code too

          if ( !next[0].match( re ) ) break block_search;



          // Pull how how many blanks lines follow - minus two to account for .join

          ret.push ( block.trailing.replace(/[^\n]/g, '').substring(2) );



          block = next.shift();

        }

        else {

          break block_search;

        }

      } while (true);



      return [ [ "code_block", ret.join("\n") ] ];

    },



    horizRule: function horizRule( block, next ) {

      // this needs to find any hr in the block to handle abutting blocks

      var m = block.match( /^(?:([\s\S]*?)\n)?[ \t]*([-_*])(?:[ \t]*\2){2,}[ \t]*(?:\n([\s\S]*))?$/ );



      if ( !m ) {

        return undefined;

      }



      var jsonml = [ [ "hr" ] ];



      // if there's a leading abutting block, process it

      if ( m[ 1 ] ) {

        jsonml.unshift.apply( jsonml, this.processBlock( m[ 1 ], [] ) );

      }



      // if there's a trailing abutting block, stick it into next

      if ( m[ 3 ] ) {

        next.unshift( mk_block( m[ 3 ] ) );

      }



      return jsonml;

    },



    // There are two types of lists. Tight and loose. Tight lists have no whitespace

    // between the items (and result in text just in the <li>) and loose lists,

    // which have an empty line between list items, resulting in (one or more)

    // paragraphs inside the <li>.

    //

    // There are all sorts weird edge cases about the original markdown.pl's

    // handling of lists:

    //

    // * Nested lists are supposed to be indented by four chars per level. But

    //   if they aren't, you can get a nested list by indenting by less than

    //   four so long as the indent doesn't match an indent of an existing list

    //   item in the 'nest stack'.

    //

    // * The type of the list (bullet or number) is controlled just by the

    //    first item at the indent. Subsequent changes are ignored unless they

    //    are for nested lists

    //

    lists: (function( ) {

      // Use a closure to hide a few variables.

      var any_list = "[*+-]|\\d+\\.",

          bullet_list = /[*+-]/,

          number_list = /\d+\./,

          // Capture leading indent as it matters for determining nested lists.

          is_list_re = new RegExp( "^( {0,3})(" + any_list + ")[ \t]+" ),

          indent_re = "(?: {0,3}\\t| {4})";



      // TODO: Cache this regexp for certain depths.

      // Create a regexp suitable for matching an li for a given stack depth

      function regex_for_depth( depth ) {



        return new RegExp(

          // m[1] = indent, m[2] = list_type

          "(?:^(" + indent_re + "{0," + depth + "} {0,3})(" + any_list + ")\\s+)|" +

          // m[3] = cont

          "(^" + indent_re + "{0," + (depth-1) + "}[ ]{0,4})"

        );

      }

      function expand_tab( input ) {

        return input.replace( / {0,3}\t/g, "    " );

      }



      // Add inline content `inline` to `li`. inline comes from processInline

      // so is an array of content

      function add(li, loose, inline, nl) {

        if (loose) {

          li.push( [ "para" ].concat(inline) );

          return;

        }

        // Hmmm, should this be any block level element or just paras?

        var add_to = li[li.length -1] instanceof Array && li[li.length - 1][0] == "para"

                   ? li[li.length -1]

                   : li;



        // If there is already some content in this list, add the new line in

        if (nl && li.length > 1) inline.unshift(nl);



        for (var i=0; i < inline.length; i++) {

          var what = inline[i],

              is_str = typeof what == "string";

          if (is_str && add_to.length > 1 && typeof add_to[add_to.length-1] == "string" ) {

            add_to[ add_to.length-1 ] += what;

          }

          else {

            add_to.push( what );

          }

        }

      }



      // contained means have an indent greater than the current one. On

      // *every* line in the block

      function get_contained_blocks( depth, blocks ) {



        var re = new RegExp( "^(" + indent_re + "{" + depth + "}.*?\\n?)*$" ),

            replace = new RegExp("^" + indent_re + "{" + depth + "}", "gm"),

            ret = [];



        while ( blocks.length > 0 ) {

          if ( re.exec( blocks[0] ) ) {

            var b = blocks.shift(),

                // Now remove that indent

                x = b.replace( replace, "");



            ret.push( mk_block( x, b.trailing, b.lineNumber ) );

          }

          break;

        }

        return ret;

      }



      // passed to stack.forEach to turn list items up the stack into paras

      function paragraphify(s, i, stack) {

        var list = s.list;

        var last_li = list[list.length-1];



        if (last_li[1] instanceof Array && last_li[1][0] == "para") {

          return;

        }

        if (i+1 == stack.length) {

          // Last stack frame

          // Keep the same array, but replace the contents

          last_li.push( ["para"].concat( last_li.splice(1) ) );

        }

        else {

          var sublist = last_li.pop();

          last_li.push( ["para"].concat( last_li.splice(1) ), sublist );

        }

      }



      // The matcher function

      return function( block, next ) {

        var m = block.match( is_list_re );

        if ( !m ) return undefined;



        function make_list( m ) {

          var list = bullet_list.exec( m[2] )

                   ? ["bulletlist"]

                   : ["numberlist"];



          stack.push( { list: list, indent: m[1] } );

          return list;

        }





        var stack = [], // Stack of lists for nesting.

            list = make_list( m ),

            last_li,

            loose = false,

            ret = [ stack[0].list ],

            i;



        // Loop to search over block looking for inner block elements and loose lists

        loose_search:

        while( true ) {

          // Split into lines preserving new lines at end of line

          var lines = block.split( /(?=\n)/ );



          // We have to grab all lines for a li and call processInline on them

          // once as there are some inline things that can span lines.

          var li_accumulate = "";



          // Loop over the lines in this block looking for tight lists.

          tight_search:

          for (var line_no=0; line_no < lines.length; line_no++) {

            var nl = "",

                l = lines[line_no].replace(/^\n/, function(n) { nl = n; return ""; });



            // TODO: really should cache this

            var line_re = regex_for_depth( stack.length );



            m = l.match( line_re );

            //print( "line:", uneval(l), "\nline match:", uneval(m) );



            // We have a list item

            if ( m[1] !== undefined ) {

              // Process the previous list item, if any

              if ( li_accumulate.length ) {

                add( last_li, loose, this.processInline( li_accumulate ), nl );

                // Loose mode will have been dealt with. Reset it

                loose = false;

                li_accumulate = "";

              }



              m[1] = expand_tab( m[1] );

              var wanted_depth = Math.floor(m[1].length/4)+1;

              //print( "want:", wanted_depth, "stack:", stack.length);

              if ( wanted_depth > stack.length ) {

                // Deep enough for a nested list outright

                //print ( "new nested list" );

                list = make_list( m );

                last_li.push( list );

                last_li = list[1] = [ "listitem" ];

              }

              else {

                // We aren't deep enough to be strictly a new level. This is

                // where Md.pl goes nuts. If the indent matches a level in the

                // stack, put it there, else put it one deeper then the

                // wanted_depth deserves.

                var found = false;

                for (i = 0; i < stack.length; i++) {

                  if ( stack[ i ].indent != m[1] ) continue;

                  list = stack[ i ].list;

                  stack.splice( i+1 );

                  found = true;

                  break;

                }



                if (!found) {

                  //print("not found. l:", uneval(l));

                  wanted_depth++;

                  if (wanted_depth <= stack.length) {

                    stack.splice(wanted_depth);

                    //print("Desired depth now", wanted_depth, "stack:", stack.length);

                    list = stack[wanted_depth-1].list;

                    //print("list:", uneval(list) );

                  }

                  else {

                    //print ("made new stack for messy indent");

                    list = make_list(m);

                    last_li.push(list);

                  }

                }



                //print( uneval(list), "last", list === stack[stack.length-1].list );

                last_li = [ "listitem" ];

                list.push(last_li);

              } // end depth of shenegains

              nl = "";

            }



            // Add content

            if (l.length > m[0].length) {

              li_accumulate += nl + l.substr( m[0].length );

            }

          } // tight_search



          if ( li_accumulate.length ) {

            add( last_li, loose, this.processInline( li_accumulate ), nl );

            // Loose mode will have been dealt with. Reset it

            loose = false;

            li_accumulate = "";

          }



          // Look at the next block - we might have a loose list. Or an extra

          // paragraph for the current li

          var contained = get_contained_blocks( stack.length, next );



          // Deal with code blocks or properly nested lists

          if (contained.length > 0) {

            // Make sure all listitems up the stack are paragraphs

            forEach( stack, paragraphify, this);



            last_li.push.apply( last_li, this.toTree( contained, [] ) );

          }



          var next_block = next[0] && next[0].valueOf() || "";



          if ( next_block.match(is_list_re) || next_block.match( /^ / ) ) {

            block = next.shift();



            // Check for an HR following a list: features/lists/hr_abutting

            var hr = this.dialect.block.horizRule( block, next );



            if (hr) {

              ret.push.apply(ret, hr);

              break;

            }



            // Make sure all listitems up the stack are paragraphs

            forEach( stack, paragraphify, this);



            loose = true;

            continue loose_search;

          }

          break;

        } // loose_search



        return ret;

      };

    })(),



    blockquote: function blockquote( block, next ) {

      if ( !block.match( /^>/m ) )

        return undefined;



      var jsonml = [];



      // separate out the leading abutting block, if any

      if ( block[ 0 ] != ">" ) {

        var lines = block.split( /\n/ ),

            prev = [];



        // keep shifting lines until you find a crotchet

        while ( lines.length && lines[ 0 ][ 0 ] != ">" ) {

            prev.push( lines.shift() );

        }



        // reassemble!

        block = lines.join( "\n" );

        jsonml.push.apply( jsonml, this.processBlock( prev.join( "\n" ), [] ) );

      }



      // if the next block is also a blockquote merge it in

      while ( next.length && next[ 0 ][ 0 ] == ">" ) {

        var b = next.shift();

        block = new String(block + block.trailing + b);

        block.trailing = b.trailing;

      }



      // Strip off the leading "> " and re-process as a block.

      var input = block.replace( /^> ?/gm, '' ),

          old_tree = this.tree;

      jsonml.push( this.toTree( input, [ "blockquote" ] ) );



      return jsonml;

    },



    referenceDefn: function referenceDefn( block, next) {

      var re = /^\s*\[(.*?)\]:\s*(\S+)(?:\s+(?:(['"])(.*?)\3|\((.*?)\)))?\n?/;

      // interesting matches are [ , ref_id, url, , title, title ]



      if ( !block.match(re) )

        return undefined;



      // make an attribute node if it doesn't exist

      if ( !extract_attr( this.tree ) ) {

        this.tree.splice( 1, 0, {} );

      }



      var attrs = extract_attr( this.tree );



      // make a references hash if it doesn't exist

      if ( attrs.references === undefined ) {

        attrs.references = {};

      }



      var b = this.loop_re_over_block(re, block, function( m ) {



        if ( m[2] && m[2][0] == '<' && m[2][m[2].length-1] == '>' )

          m[2] = m[2].substring( 1, m[2].length - 1 );



        var ref = attrs.references[ m[1].toLowerCase() ] = {

          href: m[2]

        };



        if (m[4] !== undefined)

          ref.title = m[4];

        else if (m[5] !== undefined)

          ref.title = m[5];



      } );



      if (b.length)

        next.unshift( mk_block( b, block.trailing ) );



      return [];

    },



    para: function para( block, next ) {

      // everything's a para!

      return [ ["para"].concat( this.processInline( block ) ) ];

    }

  }

};



Markdown.dialects.Gruber.inline = {



    __oneElement__: function oneElement( text, patterns_or_re, previous_nodes ) {

      var m,

          res,

          lastIndex = 0;



      patterns_or_re = patterns_or_re || this.dialect.inline.__patterns__;

      var re = new RegExp( "([\\s\\S]*?)(" + (patterns_or_re.source || patterns_or_re) + ")" );



      m = re.exec( text );

      if (!m) {

        // Just boring text

        return [ text.length, text ];

      }

      else if ( m[1] ) {

        // Some un-interesting text matched. Return that first

        return [ m[1].length, m[1] ];

      }



      var res;

      if ( m[2] in this.dialect.inline ) {

        res = this.dialect.inline[ m[2] ].call(

                  this,

                  text.substr( m.index ), m, previous_nodes || [] );

      }

      // Default for now to make dev easier. just slurp special and output it.

      res = res || [ m[2].length, m[2] ];

      return res;

    },



    __call__: function inline( text, patterns ) {



      var out = [],

          res;



      function add(x) {

        //D:self.debug("  adding output", uneval(x));

        if (typeof x == "string" && typeof out[out.length-1] == "string")

          out[ out.length-1 ] += x;

        else

          out.push(x);

      }



      while ( text.length > 0 ) {

        res = this.dialect.inline.__oneElement__.call(this, text, patterns, out );

        text = text.substr( res.shift() );

        forEach(res, add )

      }



      return out;

    },



    // These characters are intersting elsewhere, so have rules for them so that

    // chunks of plain text blocks don't include them

    "]": function () {},

    "}": function () {},



    "\\": function escaped( text ) {

      // [ length of input processed, node/children to add... ]

      // Only esacape: \ ` * _ { } [ ] ( ) # * + - . !

      if ( text.match( /^\\[\\`\*_{}\[\]()#\+.!\-]/ ) )

        return [ 2, text[1] ];

      else

        // Not an esacpe

        return [ 1, "\\" ];

    },



    "![": function image( text ) {



      // Unlike images, alt text is plain text only. no other elements are

      // allowed in there



      // ![Alt text](/path/to/img.jpg "Optional title")

      //      1          2            3       4         <--- captures

      var m = text.match( /^!\[(.*?)\][ \t]*\([ \t]*(\S*)(?:[ \t]+(["'])(.*?)\3)?[ \t]*\)/ );



      if ( m ) {

        if ( m[2] && m[2][0] == '<' && m[2][m[2].length-1] == '>' )

          m[2] = m[2].substring( 1, m[2].length - 1 );



        m[2] = this.dialect.inline.__call__.call( this, m[2], /\\/ )[0];



        var attrs = { alt: m[1], href: m[2] || "" };

        if ( m[4] !== undefined)

          attrs.title = m[4];



        return [ m[0].length, [ "img", attrs ] ];

      }



      // ![Alt text][id]

      m = text.match( /^!\[(.*?)\][ \t]*\[(.*?)\]/ );



      if ( m ) {

        // We can't check if the reference is known here as it likely wont be

        // found till after. Check it in md tree->hmtl tree conversion

        return [ m[0].length, [ "img_ref", { alt: m[1], ref: m[2].toLowerCase(), original: m[0] } ] ];

      }



      // Just consume the '!['

      return [ 2, "![" ];

    },



    "[": function link( text ) {



      var orig = String(text);

      // Inline content is possible inside `link text`

      var res = Markdown.DialectHelpers.inline_until_char.call( this, text.substr(1), ']' );



      // No closing ']' found. Just consume the [

      if ( !res ) return [ 1, '[' ];



      var consumed = 1 + res[ 0 ],

          children = res[ 1 ],

          link,

          attrs;



      // At this point the first [...] has been parsed. See what follows to find

      // out which kind of link we are (reference or direct url)

      text = text.substr( consumed );



      // [link text](/path/to/img.jpg "Optional title")

      //                 1            2       3         <--- captures

      // This will capture up to the last paren in the block. We then pull

      // back based on if there a matching ones in the url

      //    ([here](/url/(test))

      // The parens have to be balanced

      var m = text.match( /^\s*\([ \t]*(\S+)(?:[ \t]+(["'])(.*?)\2)?[ \t]*\)/ );

      if ( m ) {

        var url = m[1];

        consumed += m[0].length;



        if ( url && url[0] == '<' && url[url.length-1] == '>' )

          url = url.substring( 1, url.length - 1 );



        // If there is a title we don't have to worry about parens in the url

        if ( !m[3] ) {

          var open_parens = 1; // One open that isn't in the capture

          for (var len = 0; len < url.length; len++) {

            switch ( url[len] ) {

            case '(':

              open_parens++;

              break;

            case ')':

              if ( --open_parens == 0) {

                consumed -= url.length - len;

                url = url.substring(0, len);

              }

              break;

            }

          }

        }



        // Process escapes only

        url = this.dialect.inline.__call__.call( this, url, /\\/ )[0];



        attrs = { href: url || "" };

        if ( m[3] !== undefined)

          attrs.title = m[3];



        link = [ "link", attrs ].concat( children );

        return [ consumed, link ];

      }



      // [Alt text][id]

      // [Alt text] [id]

      m = text.match( /^\s*\[(.*?)\]/ );



      if ( m ) {



        consumed += m[ 0 ].length;



        // [links][] uses links as its reference

        attrs = { ref: ( m[ 1 ] || String(children) ).toLowerCase(),  original: orig.substr( 0, consumed ) };



        link = [ "link_ref", attrs ].concat( children );



        // We can't check if the reference is known here as it likely wont be

        // found till after. Check it in md tree->hmtl tree conversion.

        // Store the original so that conversion can revert if the ref isn't found.

        return [ consumed, link ];

      }



      // [id]

      // Only if id is plain (no formatting.)

      if ( children.length == 1 && typeof children[0] == "string" ) {



        attrs = { ref: children[0].toLowerCase(),  original: orig.substr( 0, consumed ) };

        link = [ "link_ref", attrs, children[0] ];

        return [ consumed, link ];

      }



      // Just consume the '['

      return [ 1, "[" ];

    },





    "<": function autoLink( text ) {

      var m;



      if ( ( m = text.match( /^<(?:((https?|ftp|mailto):[^>]+)|(.*?@.*?\.[a-zA-Z]+))>/ ) ) != null ) {

        if ( m[3] ) {

          return [ m[0].length, [ "link", { href: "mailto:" + m[3] }, m[3] ] ];



        }

        else if ( m[2] == "mailto" ) {

          return [ m[0].length, [ "link", { href: m[1] }, m[1].substr("mailto:".length ) ] ];

        }

        else

          return [ m[0].length, [ "link", { href: m[1] }, m[1] ] ];

      }



      return [ 1, "<" ];

    },



    "`": function inlineCode( text ) {

      // Inline code block. as many backticks as you like to start it

      // Always skip over the opening ticks.

      var m = text.match( /(`+)(([\s\S]*?)\1)/ );



      if ( m && m[2] )

        return [ m[1].length + m[2].length, [ "inlinecode", m[3] ] ];

      else {

        // TODO: No matching end code found - warn!

        return [ 1, "`" ];

      }

    },



    "  \n": function lineBreak( text ) {

      return [ 3, [ "linebreak" ] ];

    }



};



// Meta Helper/generator method for em and strong handling

function strong_em( tag, md ) {



  var state_slot = tag + "_state",

      other_slot = tag == "strong" ? "em_state" : "strong_state";



  function CloseTag(len) {

    this.len_after = len;

    this.name = "close_" + md;

  }



  return function ( text, orig_match ) {



    if (this[state_slot][0] == md) {

      // Most recent em is of this type

      //D:this.debug("closing", md);

      this[state_slot].shift();



      // "Consume" everything to go back to the recrusion in the else-block below

      return[ text.length, new CloseTag(text.length-md.length) ];

    }

    else {

      // Store a clone of the em/strong states

      var other = this[other_slot].slice(),

          state = this[state_slot].slice();



      this[state_slot].unshift(md);



      //D:this.debug_indent += "  ";



      // Recurse

      var res = this.processInline( text.substr( md.length ) );

      //D:this.debug_indent = this.debug_indent.substr(2);



      var last = res[res.length - 1];



      //D:this.debug("processInline from", tag + ": ", uneval( res ) );



      var check = this[state_slot].shift();

      if (last instanceof CloseTag) {

        res.pop();

        // We matched! Huzzah.

        var consumed = text.length - last.len_after;

        return [ consumed, [ tag ].concat(res) ];

      }

      else {

        // Restore the state of the other kind. We might have mistakenly closed it.

        this[other_slot] = other;

        this[state_slot] = state;



        // We can't reuse the processed result as it could have wrong parsing contexts in it.

        return [ md.length, md ];

      }

    }

  }; // End returned function

}



Markdown.dialects.Gruber.inline["**"] = strong_em("strong", "**");

Markdown.dialects.Gruber.inline["__"] = strong_em("strong", "__");

Markdown.dialects.Gruber.inline["*"]  = strong_em("em", "*");

Markdown.dialects.Gruber.inline["_"]  = strong_em("em", "_");





// Build default order from insertion order.

Markdown.buildBlockOrder = function(d) {

  var ord = [];

  for ( var i in d ) {

    if ( i == "__order__" || i == "__call__" ) continue;

    ord.push( i );

  }

  d.__order__ = ord;

};



// Build patterns for inline matcher

Markdown.buildInlinePatterns = function(d) {

  var patterns = [];



  for ( var i in d ) {

    // __foo__ is reserved and not a pattern

    if ( i.match( /^__.*__$/) ) continue;

    var l = i.replace( /([\\.*+?|()\[\]{}])/g, "\\$1" )

             .replace( /\n/, "\\n" );

    patterns.push( i.length == 1 ? l : "(?:" + l + ")" );

  }



  patterns = patterns.join("|");

  d.__patterns__ = patterns;

  //print("patterns:", uneval( patterns ) );



  var fn = d.__call__;

  d.__call__ = function(text, pattern) {

    if (pattern != undefined) {

      return fn.call(this, text, pattern);

    }

    else

    {

      return fn.call(this, text, patterns);

    }

  };

};



Markdown.DialectHelpers = {};

Markdown.DialectHelpers.inline_until_char = function( text, want ) {

  var consumed = 0,

      nodes = [];



  while ( true ) {

    if ( text[ consumed ] == want ) {

      // Found the character we were looking for

      consumed++;

      return [ consumed, nodes ];

    }



    if ( consumed >= text.length ) {

      // No closing char found. Abort.

      return null;

    }



    var res = this.dialect.inline.__oneElement__.call(this, text.substr( consumed ) );

    consumed += res[ 0 ];

    // Add any returned nodes.

    nodes.push.apply( nodes, res.slice( 1 ) );

  }

}



// Helper function to make sub-classing a dialect easier

Markdown.subclassDialect = function( d ) {

  function Block() {}

  Block.prototype = d.block;

  function Inline() {}

  Inline.prototype = d.inline;



  return { block: new Block(), inline: new Inline() };

};



Markdown.buildBlockOrder ( Markdown.dialects.Gruber.block );

Markdown.buildInlinePatterns( Markdown.dialects.Gruber.inline );



Markdown.dialects.Maruku = Markdown.subclassDialect( Markdown.dialects.Gruber );



Markdown.dialects.Maruku.processMetaHash = function processMetaHash( meta_string ) {

  var meta = split_meta_hash( meta_string ),

      attr = {};



  for ( var i = 0; i < meta.length; ++i ) {

    // id: #foo

    if ( /^#/.test( meta[ i ] ) ) {

      attr.id = meta[ i ].substring( 1 );

    }

    // class: .foo

    else if ( /^\./.test( meta[ i ] ) ) {

      // if class already exists, append the new one

      if ( attr['class'] ) {

        attr['class'] = attr['class'] + meta[ i ].replace( /./, " " );

      }

      else {

        attr['class'] = meta[ i ].substring( 1 );

      }

    }

    // attribute: foo=bar

    else if ( /\=/.test( meta[ i ] ) ) {

      var s = meta[ i ].split( /\=/ );

      attr[ s[ 0 ] ] = s[ 1 ];

    }

  }



  return attr;

}



function split_meta_hash( meta_string ) {

  var meta = meta_string.split( "" ),

      parts = [ "" ],

      in_quotes = false;



  while ( meta.length ) {

    var letter = meta.shift();

    switch ( letter ) {

      case " " :

        // if we're in a quoted section, keep it

        if ( in_quotes ) {

          parts[ parts.length - 1 ] += letter;

        }

        // otherwise make a new part

        else {

          parts.push( "" );

        }

        break;

      case "'" :

      case '"' :

        // reverse the quotes and move straight on

        in_quotes = !in_quotes;

        break;

      case "\\" :

        // shift off the next letter to be used straight away.

        // it was escaped so we'll keep it whatever it is

        letter = meta.shift();

      default :

        parts[ parts.length - 1 ] += letter;

        break;

    }

  }



  return parts;

}



Markdown.dialects.Maruku.block.document_meta = function document_meta( block, next ) {

  // we're only interested in the first block

  if ( block.lineNumber > 1 ) return undefined;



  // document_meta blocks consist of one or more lines of `Key: Value\n`

  if ( ! block.match( /^(?:\w+:.*\n)*\w+:.*$/ ) ) return undefined;



  // make an attribute node if it doesn't exist

  if ( !extract_attr( this.tree ) ) {

    this.tree.splice( 1, 0, {} );

  }



  var pairs = block.split( /\n/ );

  for ( p in pairs ) {

    var m = pairs[ p ].match( /(\w+):\s*(.*)$/ ),

        key = m[ 1 ].toLowerCase(),

        value = m[ 2 ];



    this.tree[ 1 ][ key ] = value;

  }



  // document_meta produces no content!

  return [];

};



Markdown.dialects.Maruku.block.block_meta = function block_meta( block, next ) {

  // check if the last line of the block is an meta hash

  var m = block.match( /(^|\n) {0,3}\{:\s*((?:\\\}|[^\}])*)\s*\}$/ );

  if ( !m ) return undefined;



  // process the meta hash

  var attr = this.dialect.processMetaHash( m[ 2 ] );



  var hash;



  // if we matched ^ then we need to apply meta to the previous block

  if ( m[ 1 ] === "" ) {

    var node = this.tree[ this.tree.length - 1 ];

    hash = extract_attr( node );



    // if the node is a string (rather than JsonML), bail

    if ( typeof node === "string" ) return undefined;



    // create the attribute hash if it doesn't exist

    if ( !hash ) {

      hash = {};

      node.splice( 1, 0, hash );

    }



    // add the attributes in

    for ( a in attr ) {

      hash[ a ] = attr[ a ];

    }



    // return nothing so the meta hash is removed

    return [];

  }



  // pull the meta hash off the block and process what's left

  var b = block.replace( /\n.*$/, "" ),

      result = this.processBlock( b, [] );



  // get or make the attributes hash

  hash = extract_attr( result[ 0 ] );

  if ( !hash ) {

    hash = {};

    result[ 0 ].splice( 1, 0, hash );

  }



  // attach the attributes to the block

  for ( a in attr ) {

    hash[ a ] = attr[ a ];

  }



  return result;

};



Markdown.dialects.Maruku.block.definition_list = function definition_list( block, next ) {

  // one or more terms followed by one or more definitions, in a single block

  var tight = /^((?:[^\s:].*\n)+):\s+([\s\S]+)$/,

      list = [ "dl" ],

      i;



  // see if we're dealing with a tight or loose block

  if ( ( m = block.match( tight ) ) ) {

    // pull subsequent tight DL blocks out of `next`

    var blocks = [ block ];

    while ( next.length && tight.exec( next[ 0 ] ) ) {

      blocks.push( next.shift() );

    }



    for ( var b = 0; b < blocks.length; ++b ) {

      var m = blocks[ b ].match( tight ),

          terms = m[ 1 ].replace( /\n$/, "" ).split( /\n/ ),

          defns = m[ 2 ].split( /\n:\s+/ );



      // print( uneval( m ) );



      for ( i = 0; i < terms.length; ++i ) {

        list.push( [ "dt", terms[ i ] ] );

      }



      for ( i = 0; i < defns.length; ++i ) {

        // run inline processing over the definition

        list.push( [ "dd" ].concat( this.processInline( defns[ i ].replace( /(\n)\s+/, "$1" ) ) ) );

      }

    }

  }

  else {

    return undefined;

  }



  return [ list ];

};



Markdown.dialects.Maruku.inline[ "{:" ] = function inline_meta( text, matches, out ) {

  if ( !out.length ) {

    return [ 2, "{:" ];

  }



  // get the preceeding element

  var before = out[ out.length - 1 ];



  if ( typeof before === "string" ) {

    return [ 2, "{:" ];

  }



  // match a meta hash

  var m = text.match( /^\{:\s*((?:\\\}|[^\}])*)\s*\}/ );



  // no match, false alarm

  if ( !m ) {

    return [ 2, "{:" ];

  }



  // attach the attributes to the preceeding element

  var meta = this.dialect.processMetaHash( m[ 1 ] ),

      attr = extract_attr( before );



  if ( !attr ) {

    attr = {};

    before.splice( 1, 0, attr );

  }



  for ( var k in meta ) {

    attr[ k ] = meta[ k ];

  }



  // cut out the string and replace it with nothing

  return [ m[ 0 ].length, "" ];

};



Markdown.buildBlockOrder ( Markdown.dialects.Maruku.block );

Markdown.buildInlinePatterns( Markdown.dialects.Maruku.inline );



var isArray = Array.isArray || function(obj) {

  return Object.prototype.toString.call(obj) == '[object Array]';

};



var forEach;

// Don't mess with Array.prototype. Its not friendly

if ( Array.prototype.forEach ) {

  forEach = function( arr, cb, thisp ) {

    return arr.forEach( cb, thisp );

  };

}

else {

  forEach = function(arr, cb, thisp) {

    for (var i = 0; i < arr.length; i++) {

      cb.call(thisp || arr, arr[i], i, arr);

    }

  }

}



function extract_attr( jsonml ) {

  return isArray(jsonml)

      && jsonml.length > 1

      && typeof jsonml[ 1 ] === "object"

      && !( isArray(jsonml[ 1 ]) )

      ? jsonml[ 1 ]

      : undefined;

}







/**

 *  renderJsonML( jsonml[, options] ) -> String

 *  - jsonml (Array): JsonML array to render to XML

 *  - options (Object): options

 *

 *  Converts the given JsonML into well-formed XML.

 *

 *  The options currently understood are:

 *

 *  - root (Boolean): wether or not the root node should be included in the

 *    output, or just its children. The default `false` is to not include the

 *    root itself.

 */

expose.renderJsonML = function( jsonml, options ) {

  options = options || {};

  // include the root element in the rendered output?

  options.root = options.root || false;



  var content = [];



  if ( options.root ) {

    content.push( render_tree( jsonml ) );

  }

  else {

    jsonml.shift(); // get rid of the tag

    if ( jsonml.length && typeof jsonml[ 0 ] === "object" && !( jsonml[ 0 ] instanceof Array ) ) {

      jsonml.shift(); // get rid of the attributes

    }



    while ( jsonml.length ) {

      content.push( render_tree( jsonml.shift() ) );

    }

  }



  return content.join( "\n\n" );

};



function escapeHTML( text ) {

  return text.replace( /&/g, "&amp;" )

             .replace( /</g, "&lt;" )

             .replace( />/g, "&gt;" )

             .replace( /"/g, "&quot;" )

             .replace( /'/g, "&#39;" );

}



function render_tree( jsonml ) {

  // basic case

  if ( typeof jsonml === "string" ) {

    return escapeHTML( jsonml );

  }



  var tag = jsonml.shift(),

      attributes = {},

      content = [];



  if ( jsonml.length && typeof jsonml[ 0 ] === "object" && !( jsonml[ 0 ] instanceof Array ) ) {

    attributes = jsonml.shift();

  }



  while ( jsonml.length ) {

    content.push( arguments.callee( jsonml.shift() ) );

  }



  var tag_attrs = "";

  for ( var a in attributes ) {

    tag_attrs += " " + a + '="' + escapeHTML( attributes[ a ] ) + '"';

  }



  // be careful about adding whitespace here for inline elements

  if ( tag == "img" || tag == "br" || tag == "hr" ) {

    return "<"+ tag + tag_attrs + "/>";

  }

  else {

    return "<"+ tag + tag_attrs + ">" + content.join( "" ) + "</" + tag + ">";

  }

}



function convert_tree_to_html( tree, references, options ) {

  var i;

  options = options || {};



  // shallow clone

  var jsonml = tree.slice( 0 );



  if (typeof options.preprocessTreeNode === "function") {

      jsonml = options.preprocessTreeNode(jsonml, references);

  }



  // Clone attributes if they exist

  var attrs = extract_attr( jsonml );

  if ( attrs ) {

    jsonml[ 1 ] = {};

    for ( i in attrs ) {

      jsonml[ 1 ][ i ] = attrs[ i ];

    }

    attrs = jsonml[ 1 ];

  }



  // basic case

  if ( typeof jsonml === "string" ) {

    return jsonml;

  }



  // convert this node

  switch ( jsonml[ 0 ] ) {

    case "header":

      jsonml[ 0 ] = "h" + jsonml[ 1 ].level;

      delete jsonml[ 1 ].level;

      break;

    case "bulletlist":

      jsonml[ 0 ] = "ul";

      break;

    case "numberlist":

      jsonml[ 0 ] = "ol";

      break;

    case "listitem":

      jsonml[ 0 ] = "li";

      break;

    case "para":

      jsonml[ 0 ] = "p";

      break;

    case "markdown":

      jsonml[ 0 ] = "html";

      if ( attrs ) delete attrs.references;

      break;

    case "code_block":

      jsonml[ 0 ] = "pre";

      i = attrs ? 2 : 1;

      var code = [ "code" ];

      code.push.apply( code, jsonml.splice( i ) );

      jsonml[ i ] = code;

      break;

    case "inlinecode":

      jsonml[ 0 ] = "code";

      break;

    case "img":

      jsonml[ 1 ].src = jsonml[ 1 ].href;

      delete jsonml[ 1 ].href;

      break;

    case "linebreak":

      jsonml[ 0 ] = "br";

    break;

    case "link":

      jsonml[ 0 ] = "a";

      break;

    case "link_ref":

      jsonml[ 0 ] = "a";



      // grab this ref and clean up the attribute node

      var ref = references[ attrs.ref ];



      // if the reference exists, make the link

      if ( ref ) {

        delete attrs.ref;



        // add in the href and title, if present

        attrs.href = ref.href;

        if ( ref.title ) {

          attrs.title = ref.title;

        }



        // get rid of the unneeded original text

        delete attrs.original;

      }

      // the reference doesn't exist, so revert to plain text

      else {

        return attrs.original;

      }

      break;

    case "img_ref":

      jsonml[ 0 ] = "img";



      // grab this ref and clean up the attribute node

      var ref = references[ attrs.ref ];



      // if the reference exists, make the link

      if ( ref ) {

        delete attrs.ref;



        // add in the href and title, if present

        attrs.src = ref.href;

        if ( ref.title ) {

          attrs.title = ref.title;

        }



        // get rid of the unneeded original text

        delete attrs.original;

      }

      // the reference doesn't exist, so revert to plain text

      else {

        return attrs.original;

      }

      break;

  }



  // convert all the children

  i = 1;



  // deal with the attribute node, if it exists

  if ( attrs ) {

    // if there are keys, skip over it

    for ( var key in jsonml[ 1 ] ) {

      i = 2;

    }

    // if there aren't, remove it

    if ( i === 1 ) {

      jsonml.splice( i, 1 );

    }

  }



  for ( ; i < jsonml.length; ++i ) {

    jsonml[ i ] = arguments.callee( jsonml[ i ], references, options );

  }



  return jsonml;

}





// merges adjacent text nodes into a single node

function merge_text_nodes( jsonml ) {

  // skip the tag name and attribute hash

  var i = extract_attr( jsonml ) ? 2 : 1;



  while ( i < jsonml.length ) {

    // if it's a string check the next item too

    if ( typeof jsonml[ i ] === "string" ) {

      if ( i + 1 < jsonml.length && typeof jsonml[ i + 1 ] === "string" ) {

        // merge the second string into the first and remove it

        jsonml[ i ] += jsonml.splice( i + 1, 1 )[ 0 ];

      }

      else {

        ++i;

      }

    }

    // if it's not a string recurse

    else {

      arguments.callee( jsonml[ i ] );

      ++i;

    }

  }

}



} )( (function() {

  if ( typeof exports === "undefined" ) {

    window.markdown = {};

    return window.markdown;

  }

  else {

    return exports;

  }

} )() );