]> git.wincent.com - wikitext.git/blob - ext/parser.c
Call Data_Wrap_Struct on ary structs
[wikitext.git] / ext / parser.c
1 // Copyright 2007-2008 Wincent Colaiuta
2 // This program is free software: you can redistribute it and/or modify
3 // it under the terms of the GNU General Public License as published by
4 // the Free Software Foundation, either version 3 of the License, or
5 // (at your option) any later version.
6 //
7 // This program is distributed in the hope that it will be useful,
8 // but WITHOUT ANY WARRANTY; without even the implied warranty of
9 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10 // GNU General Public License for more details.
11 //
12 // You should have received a copy of the GNU General Public License
13 // along with this program.  If not, see <http://www.gnu.org/licenses/>.
14
15 #include "parser.h"
16 #include "ary.h"
17 #include "str.h"
18 #include "wikitext.h"
19 #include "wikitext_ragel.h"
20
21 #define IN(type) ary_includes(parser->scope, type)
22
23 // poor man's object orientation in C:
24 // instead of parsing around multiple parameters between functions in the parser
25 // we pack everything into a struct and pass around only a pointer to that
26 typedef struct
27 {
28     VALUE   output;                 // for accumulating output to be returned
29     VALUE   capture;                // for capturing substrings
30     VALUE   link_target;            // short term "memory" for parsing links
31     VALUE   link_text;              // short term "memory" for parsing links
32     VALUE   external_link_class;    // CSS class applied to external links
33     VALUE   img_prefix;             // path prepended when emitting img tags
34     ary_t   *scope;                 // stack for tracking scope
35     ary_t   *line;                  // stack for tracking scope as implied by current line
36     ary_t   *line_buffer;           // stack for tracking raw tokens (not scope) on current line
37     VALUE   pending_crlf;           // boolean (Qtrue or Qfalse)
38     VALUE   autolink;               // boolean (Qtrue or Qfalse)
39     VALUE   treat_slash_as_special; // boolean (Qtrue or Qfalse)
40     VALUE   space_to_underscore;    // boolean (Qtrue or Qfalse)
41     VALUE   special_link;           // boolean (Qtrue or Qfalse): is the current link_target a "special" link?
42     str_t   *line_ending;
43     int     base_indent;            // controlled by the :indent option to Wikitext::Parser#parse
44     int     current_indent;         // fluctuates according to currently nested structures
45     str_t   *tabulation;            // caching buffer for emitting indentation
46 } parser_t;
47
48 const char escaped_no_wiki_start[]      = "&lt;nowiki&gt;";
49 const char escaped_no_wiki_end[]        = "&lt;/nowiki&gt;";
50 const char literal_strong_em[]          = "'''''";
51 const char literal_strong[]             = "'''";
52 const char literal_em[]                 = "''";
53 const char escaped_em_start[]           = "&lt;em&gt;";
54 const char escaped_em_end[]             = "&lt;/em&gt;";
55 const char escaped_strong_start[]       = "&lt;strong&gt;";
56 const char escaped_strong_end[]         = "&lt;/strong&gt;";
57 const char escaped_tt_start[]           = "&lt;tt&gt;";
58 const char escaped_tt_end[]             = "&lt;/tt&gt;";
59 const char literal_h6[]                 = "======";
60 const char literal_h5[]                 = "=====";
61 const char literal_h4[]                 = "====";
62 const char literal_h3[]                 = "===";
63 const char literal_h2[]                 = "==";
64 const char literal_h1[]                 = "=";
65 const char pre_start[]                  = "<pre>";
66 const char pre_end[]                    = "</pre>";
67 const char escaped_pre_start[]          = "&lt;pre&gt;";
68 const char escaped_pre_end[]            = "&lt;/pre&gt;";
69 const char blockquote_start[]           = "<blockquote>";
70 const char blockquote_end[]             = "</blockquote>";
71 const char escaped_blockquote_start[]   = "&lt;blockquote&gt;";
72 const char escaped_blockquote_end[]     = "&lt;/blockquote&gt;";
73 const char strong_em_start[]            = "<strong><em>";
74 const char strong_start[]               = "<strong>";
75 const char strong_end[]                 = "</strong>";
76 const char em_start[]                   = "<em>";
77 const char em_end[]                     = "</em>";
78 const char tt_start[]                   = "<tt>";
79 const char tt_end[]                     = "</tt>";
80 const char ol_start[]                   = "<ol>";
81 const char ol_end[]                     = "</ol>";
82 const char ul_start[]                   = "<ul>";
83 const char ul_end[]                     = "</ul>";
84 const char li_start[]                   = "<li>";
85 const char li_end[]                     = "</li>";
86 const char h6_start[]                   = "<h6>";
87 const char h6_end[]                     = "</h6>";
88 const char h5_start[]                   = "<h5>";
89 const char h5_end[]                     = "</h5>";
90 const char h4_start[]                   = "<h4>";
91 const char h4_end[]                     = "</h4>";
92 const char h3_start[]                   = "<h3>";
93 const char h3_end[]                     = "</h3>";
94 const char h2_start[]                   = "<h2>";
95 const char h2_end[]                     = "</h2>";
96 const char h1_start[]                   = "<h1>";
97 const char h1_end[]                     = "</h1>";
98 const char p_start[]                    = "<p>";
99 const char p_end[]                      = "</p>";
100 const char space[]                      = " ";
101 const char a_start[]                    = "<a href=\"";
102 const char a_class[]                    = "\" class=\"";
103 const char a_start_close[]              = "\">";
104 const char a_end[]                      = "</a>";
105 const char link_start[]                 = "[[";
106 const char link_end[]                   = "]]";
107 const char separator[]                  = "|";
108 const char ext_link_start[]             = "[";
109 const char backtick[]                   = "`";
110 const char quote[]                      = "\"";
111 const char ampersand[]                  = "&";
112 const char quot_entity[]                = "&quot;";
113 const char amp_entity[]                 = "&amp;";
114 const char lt_entity[]                  = "&lt;";
115 const char gt_entity[]                  = "&gt;";
116 const char escaped_blockquote[]         = "&gt; ";
117 const char ext_link_end[]               = "]";
118 const char literal_img_start[]          = "{{";
119 const char img_start[]                  = "<img src=\"";
120 const char img_end[]                    = "\" />";
121 const char img_alt[]                    = "\" alt=\"";
122
123 // for testing and debugging only
124 VALUE Wikitext_parser_tokenize(VALUE self, VALUE string)
125 {
126     if (NIL_P(string))
127         return Qnil;
128     string = StringValue(string);
129     VALUE tokens = rb_ary_new();
130     char *p = RSTRING_PTR(string);
131     long len = RSTRING_LEN(string);
132     char *pe = p + len;
133     token_t token;
134     next_token(&token, NULL, p, pe);
135     rb_ary_push(tokens, _Wikitext_token(&token));
136     while (token.type != END_OF_FILE)
137     {
138         next_token(&token, &token, NULL, pe);
139         rb_ary_push(tokens, _Wikitext_token(&token));
140     }
141     return tokens;
142 }
143
144 // for benchmarking raw tokenization speed only
145 VALUE Wikitext_parser_benchmarking_tokenize(VALUE self, VALUE string)
146 {
147     if (NIL_P(string))
148         return Qnil;
149     string = StringValue(string);
150     char *p = RSTRING_PTR(string);
151     long len = RSTRING_LEN(string);
152     char *pe = p + len;
153     token_t token;
154     next_token(&token, NULL, p, pe);
155     while (token.type != END_OF_FILE)
156         next_token(&token, &token, NULL, pe);
157     return Qnil;
158 }
159
160 // we downcase "in place", overwriting the original contents of the buffer and returning the same string
161 inline VALUE _Wikitext_downcase(VALUE string)
162 {
163     char *ptr   = RSTRING_PTR(string);
164     long len    = RSTRING_LEN(string);
165     for (long i = 0; i < len; i++)
166     {
167         if (ptr[i] >= 'A' && ptr[i] <= 'Z')
168             ptr[i] += 32;
169     }
170     return string;
171 }
172
173 inline VALUE _Wikitext_hyperlink(VALUE link_prefix, VALUE link_target, VALUE link_text, VALUE link_class)
174 {
175     VALUE string = rb_str_new(a_start, sizeof(a_start) - 1);        // <a href="
176     if (!NIL_P(link_prefix))
177         rb_str_append(string, link_prefix);
178     rb_str_append(string, link_target);
179     if (link_class != Qnil)
180     {
181         rb_str_cat(string, a_class, sizeof(a_class) - 1);           // " class="
182         rb_str_append(string, link_class);
183     }
184     rb_str_cat(string, a_start_close, sizeof(a_start_close) - 1);   // ">
185     rb_str_append(string, link_text);
186     rb_str_cat(string, a_end, sizeof(a_end) - 1);
187     return string;
188 }
189
190 inline void _Wikitext_append_img(parser_t *parser, char *token_ptr, int token_len)
191 {
192     rb_str_cat(parser->output, img_start, sizeof(img_start) - 1);   // <img src="
193     if (!NIL_P(parser->img_prefix))
194         rb_str_append(parser->output, parser->img_prefix);
195     rb_str_cat(parser->output, token_ptr, token_len);
196     rb_str_cat(parser->output, img_alt, sizeof(img_alt) - 1);       // " alt="
197     rb_str_cat(parser->output, token_ptr, token_len);
198     rb_str_cat(parser->output, img_end, sizeof(img_end) - 1);       // " />
199 }
200
201 // will emit indentation only if we are about to emit any of:
202 //      <blockquote>, <p>, <ul>, <ol>, <li>, <h1> etc, <pre>
203 // each time we enter one of those spans must ++ the indentation level
204 inline void _Wikitext_indent(parser_t *parser)
205 {
206     int space_count = parser->current_indent + parser->base_indent;
207     if (space_count > 0)
208     {
209         char *old_end, *new_end;
210         if (!parser->tabulation)
211             parser->tabulation = str_new_size(space_count);
212         else if (parser->tabulation->len < space_count)
213             str_grow(parser->tabulation, space_count); // reallocates if necessary
214         old_end = parser->tabulation->ptr + parser->tabulation->len;
215         new_end = parser->tabulation->ptr + space_count;
216         while (old_end < new_end)
217             *old_end++ = ' ';
218         if (space_count > parser->tabulation->len)
219             parser->tabulation->len = space_count;
220         rb_str_cat(parser->output, parser->tabulation->ptr, space_count);
221     }
222     parser->current_indent += 2;
223 }
224
225 inline void _Wikitext_dedent(parser_t *parser, VALUE emit)
226 {
227     parser->current_indent -= 2;
228     if (emit != Qtrue)
229         return;
230     int space_count = parser->current_indent + parser->base_indent;
231     if (space_count > 0)
232         rb_str_cat(parser->output, parser->tabulation->ptr, space_count);
233 }
234
235 // Pops a single item off the parser's scope stack.
236 // A corresponding closing tag is written to the target string.
237 // The target string may be the main output buffer, or a substring capturing buffer if a link is being scanned.
238 void _Wikitext_pop_from_stack(parser_t *parser, VALUE target)
239 {
240     int top = ary_entry(parser->scope, -1);
241     if (NO_ITEM(top))
242         return;
243     if (NIL_P(target))
244         target = parser->output;
245     switch (top)
246     {
247         case PRE:
248         case PRE_START:
249             rb_str_cat(target, pre_end, sizeof(pre_end) - 1);
250             rb_str_cat(target, parser->line_ending->ptr, parser->line_ending->len);
251             _Wikitext_dedent(parser, Qfalse);
252             break;
253
254         case BLOCKQUOTE:
255         case BLOCKQUOTE_START:
256             _Wikitext_dedent(parser, Qtrue);
257             rb_str_cat(target, blockquote_end, sizeof(blockquote_end) - 1);
258             rb_str_cat(target, parser->line_ending->ptr, parser->line_ending->len);
259             break;
260
261         case NO_WIKI_START:
262             // not a real HTML tag; so nothing to pop
263             break;
264
265         case STRONG:
266         case STRONG_START:
267             rb_str_cat(target, strong_end, sizeof(strong_end) - 1);
268             break;
269
270         case EM:
271         case EM_START:
272             rb_str_cat(target, em_end, sizeof(em_end) - 1);
273             break;
274
275         case TT:
276         case TT_START:
277             rb_str_cat(target, tt_end, sizeof(tt_end) - 1);
278             break;
279
280         case OL:
281             _Wikitext_dedent(parser, Qtrue);
282             rb_str_cat(target, ol_end, sizeof(ol_end) - 1);
283             rb_str_cat(target, parser->line_ending->ptr, parser->line_ending->len);
284             break;
285
286         case UL:
287             _Wikitext_dedent(parser, Qtrue);
288             rb_str_cat(target, ul_end, sizeof(ul_end) - 1);
289             rb_str_cat(target, parser->line_ending->ptr, parser->line_ending->len);
290             break;
291
292         case NESTED_LIST:
293             // next token to pop will be a LI
294             // LI is an interesting token because sometimes we want it to behave like P (ie. do a non-emitting indent)
295             // and other times we want it to behave like BLOCKQUOTE (ie. when it has a nested list inside)
296             // hence this hack: we do an emitting dedent on behalf of the LI that we know must be coming
297             // and then when we pop the actual LI itself (below) we do the standard non-emitting indent
298             _Wikitext_dedent(parser, Qtrue);    // we really only want to emit the spaces
299             parser->current_indent += 2;        // we don't want to decrement the actual indent level, so put it back
300             break;
301
302         case LI:
303             rb_str_cat(target, li_end, sizeof(li_end) - 1);
304             rb_str_cat(target, parser->line_ending->ptr, parser->line_ending->len);
305             _Wikitext_dedent(parser, Qfalse);
306             break;
307
308         case H6_START:
309             rb_str_cat(target, h6_end, sizeof(h6_end) - 1);
310             rb_str_cat(target, parser->line_ending->ptr, parser->line_ending->len);
311             _Wikitext_dedent(parser, Qfalse);
312             break;
313
314         case H5_START:
315             rb_str_cat(target, h5_end, sizeof(h5_end) - 1);
316             rb_str_cat(target, parser->line_ending->ptr, parser->line_ending->len);
317             _Wikitext_dedent(parser, Qfalse);
318             break;
319
320         case H4_START:
321             rb_str_cat(target, h4_end, sizeof(h4_end) - 1);
322             rb_str_cat(target, parser->line_ending->ptr, parser->line_ending->len);
323             _Wikitext_dedent(parser, Qfalse);
324             break;
325
326         case H3_START:
327             rb_str_cat(target, h3_end, sizeof(h3_end) - 1);
328             rb_str_cat(target, parser->line_ending->ptr, parser->line_ending->len);
329             _Wikitext_dedent(parser, Qfalse);
330             break;
331
332         case H2_START:
333             rb_str_cat(target, h2_end, sizeof(h2_end) - 1);
334             rb_str_cat(target, parser->line_ending->ptr, parser->line_ending->len);
335             _Wikitext_dedent(parser, Qfalse);
336             break;
337
338         case H1_START:
339             rb_str_cat(target, h1_end, sizeof(h1_end) - 1);
340             rb_str_cat(target, parser->line_ending->ptr, parser->line_ending->len);
341             _Wikitext_dedent(parser, Qfalse);
342             break;
343
344         case LINK_START:
345             // not an HTML tag; so nothing to emit
346             break;
347
348         case EXT_LINK_START:
349             // not an HTML tag; so nothing to emit
350             break;
351
352         case SPACE:
353             // not an HTML tag (only used to separate an external link target from the link text); so nothing to emit
354             break;
355
356         case SEPARATOR:
357             // not an HTML tag (only used to separate an external link target from the link text); so nothing to emit
358             break;
359
360         case P:
361             rb_str_cat(target, p_end, sizeof(p_end) - 1);
362             rb_str_cat(target, parser->line_ending->ptr, parser->line_ending->len);
363             _Wikitext_dedent(parser, Qfalse);
364             break;
365
366         case END_OF_FILE:
367             // nothing to do
368             break;
369
370         default:
371             // should probably raise an exception here
372             break;
373     }
374     ary_pop(parser->scope);
375 }
376
377 // Pops items off the top of parser's scope stack, accumulating closing tags for them into the target string, until item is reached.
378 // If including is Qtrue then the item itself is also popped.
379 // The target string may be the main output buffer, or a substring capturing buffer when scanning links.
380 void _Wikitext_pop_from_stack_up_to(parser_t *parser, VALUE target, int item, VALUE including)
381 {
382     int continue_looping = 1;
383     do
384     {
385         int top = ary_entry(parser->scope, -1);
386         if (NO_ITEM(top))
387             return;
388         if (top == item)
389         {
390             if (including != Qtrue)
391                 return;
392             continue_looping = 0;
393         }
394         _Wikitext_pop_from_stack(parser, target);
395     } while (continue_looping);
396 }
397
398 inline void _Wikitext_start_para_if_necessary(parser_t *parser)
399 {
400     if (!NIL_P(parser->capture))    // we don't do anything if in capturing mode
401         return;
402
403     // if no block open yet, or top of stack is BLOCKQUOTE/BLOCKQUOTE_START (with nothing in it yet)
404     if (parser->scope->count == 0 ||
405         ary_entry(parser->scope, -1) == BLOCKQUOTE ||
406         ary_entry(parser->scope, -1) == BLOCKQUOTE_START)
407     {
408         _Wikitext_indent(parser);
409         rb_str_cat(parser->output, p_start, sizeof(p_start) - 1);
410         ary_push(parser->scope, P);
411         ary_push(parser->line, P);
412     }
413     else if (parser->pending_crlf == Qtrue)
414     {
415         if (IN(P))
416             // already in a paragraph block; convert pending CRLF into a space
417             rb_str_cat(parser->output, space, sizeof(space) - 1);
418         else if (IN(PRE))
419             // PRE blocks can have pending CRLF too (helps us avoid emitting the trailing newline)
420             rb_str_cat(parser->output, parser->line_ending->ptr, parser->line_ending->len);
421     }
422     parser->pending_crlf = Qfalse;
423 }
424
425 // Helper function that pops any excess elements off scope (pushing is already handled in the respective rules).
426 // For example, given input like:
427 //
428 //      > > foo
429 //      bar
430 //
431 // Upon seeing "bar", we want to pop two BLOCKQUOTE elements from the scope.
432 // The reverse case (shown below) is handled from inside the BLOCKQUOTE rule itself:
433 //
434 //      foo
435 //      > > bar
436 //
437 // Things are made slightly more complicated by the fact that there is one block-level tag that can be on the scope
438 // but not on the line scope:
439 //
440 //      <blockquote>foo
441 //      bar</blockquote>
442 //
443 // Here on seeing "bar" we have one item on the scope (BLOCKQUOTE_START) which we don't want to pop, but we have nothing
444 // on the line scope.
445 // Luckily, BLOCKQUOTE_START tokens can only appear at the start of the scope array, so we can check for them first before
446 // entering the for loop.
447 void inline _Wikitext_pop_excess_elements(parser_t *parser)
448 {
449     if (!NIL_P(parser->capture)) // we don't pop anything if in capturing mode
450         return;
451     for (int i = parser->scope->count - ary_count(parser->scope, BLOCKQUOTE_START), j = parser->line->count; i > j; i--)
452     {
453         // special case for last item on scope
454         if (i - j == 1)
455         {
456             // don't auto-pop P if it is only item on scope
457             if (ary_entry(parser->scope, -1) == P)
458             {
459                 // add P to the line scope to prevent us entering the loop at all next time around
460                 ary_push(parser->line, P);
461                 continue;
462             }
463         }
464         _Wikitext_pop_from_stack(parser, parser->output);
465     }
466 }
467
468 #define INVALID_ENCODING(msg)  do { if (dest_ptr) free(dest_ptr); rb_raise(eWikitextParserError, "invalid encoding: " msg); } while(0)
469
470 // convert a single UTF-8 codepoint to UTF-32
471 // expects an input buffer, src, containing a UTF-8 encoded character (which may be multi-byte)
472 // the end of the input buffer, end, is also passed in to allow the detection of invalidly truncated codepoints
473 // the number of bytes in the UTF-8 character (between 1 and 4) is returned by reference in width_out
474 // raises a RangeError if the supplied character is invalid UTF-8
475 // (in which case it also frees the block of memory indicated by dest_ptr if it is non-NULL)
476 inline uint32_t _Wikitext_utf8_to_utf32(char *src, char *end, long *width_out, void *dest_ptr)
477 {
478     uint32_t dest;
479     if ((unsigned char)src[0] <= 0x7f)                      // ASCII
480     {
481         dest = src[0];
482         *width_out = 1;
483     }
484     else if ((src[0] & 0xe0) == 0xc0)                       // byte starts with 110..... : this should be a two-byte sequence
485     {
486         if (src + 1 >= end)
487             INVALID_ENCODING("truncated byte sequence");    // no second byte
488         else if (((unsigned char)src[0] == 0xc0) || ((unsigned char)src[0] == 0xc1))
489             INVALID_ENCODING("overlong encoding");          // overlong encoding: lead byte of 110..... but code point <= 127
490         else if ((src[1] & 0xc0) != 0x80 )
491             INVALID_ENCODING("malformed byte sequence");    // should have second byte starting with 10......
492         dest = ((uint32_t)(src[0] & 0x1f)) << 6 | (src[1] & 0x3f);
493         *width_out = 2;
494     }
495     else if ((src[0] & 0xf0) == 0xe0)                       // byte starts with 1110.... : this should be a three-byte sequence
496     {
497         if (src + 2 >= end)
498             INVALID_ENCODING("truncated byte sequence");    // missing second or third byte
499         else if (((src[1] & 0xc0) != 0x80 ) || ((src[2] & 0xc0) != 0x80 ))
500             INVALID_ENCODING("malformed byte sequence");    // should have second and third bytes starting with 10......
501         dest = ((uint32_t)(src[0] & 0x0f)) << 12 | ((uint32_t)(src[1] & 0x3f)) << 6 | (src[2] & 0x3f);
502         *width_out = 3;
503     }
504     else if ((src[0] & 0xf8) == 0xf0)                       // bytes starts with 11110... : this should be a four-byte sequence
505     {
506         if (src + 3 >= end)
507             INVALID_ENCODING("truncated byte sequence");    // missing second, third, or fourth byte
508         else if ((unsigned char)src[0] >= 0xf5 && (unsigned char)src[0] <= 0xf7)
509             INVALID_ENCODING("overlong encoding");          // disallowed by RFC 3629 (codepoints above 0x10ffff)
510         else if (((src[1] & 0xc0) != 0x80 ) || ((src[2] & 0xc0) != 0x80 ) || ((src[3] & 0xc0) != 0x80 ))
511             INVALID_ENCODING("malformed byte sequence");    // should have second and third bytes starting with 10......
512         dest = ((uint32_t)(src[0] & 0x07)) << 18 | ((uint32_t)(src[1] & 0x3f)) << 12 | ((uint32_t)(src[1] & 0x3f)) << 6 | (src[2] & 0x3f);
513         *width_out = 4;
514     }
515     else                                                    // invalid input
516         INVALID_ENCODING("unexpected byte");
517     return dest;
518 }
519
520 inline VALUE _Wikitext_utf32_char_to_entity(uint32_t character)
521 {
522     // TODO: consider special casing some entities (ie. quot, amp, lt, gt etc)?
523     char hex_string[8]  = { '&', '#', 'x', 0, 0, 0, 0, ';' };
524     char scratch        = (character & 0xf000) >> 12;
525     hex_string[3]       = (scratch <= 9 ? scratch + 48 : scratch + 87);
526     scratch             = (character & 0x0f00) >> 8;
527     hex_string[4]       = (scratch <= 9 ? scratch + 48 : scratch + 87);
528     scratch             = (character & 0x00f0) >> 4;
529     hex_string[5]       = (scratch <= 9 ? scratch + 48 : scratch + 87);
530     scratch             = character & 0x000f;
531     hex_string[6]       = (scratch <= 9 ? scratch + 48 : scratch + 87);
532     return rb_str_new((const char *)hex_string, sizeof(hex_string));
533 }
534
535 inline VALUE _Wikitext_parser_trim_link_target(VALUE string)
536 {
537     string              = StringValue(string);
538     char    *src        = RSTRING_PTR(string);
539     char    *start      = src;                  // remember this so we can check if we're at the start
540     char    *left       = src;
541     char    *non_space  = src;                  // remember last non-space character output
542     long    len         = RSTRING_LEN(string);
543     char    *end        = src + len;
544     while (src < end)
545     {
546         if (*src == ' ')
547         {
548             if (src == left)
549                 *left++;
550         }
551         else
552             non_space = src;
553         src++;
554     }
555     if (left == start && non_space + 1 == end)
556         return string;
557     else
558         return rb_str_new(left, (non_space + 1) - left);
559 }
560
561 // - non-printable (non-ASCII) characters converted to numeric entities
562 // - QUOT and AMP characters converted to named entities
563 // - if rollback is Qtrue, there is no special treatment of spaces
564 // - if rollback is Qfalse, leading and trailing whitespace trimmed if trimmed
565 inline VALUE _Wikitext_parser_sanitize_link_target(parser_t *parser, VALUE rollback)
566 {
567     VALUE string        = StringValue(parser->link_target); // raises if string is nil or doesn't quack like a string
568     char    *src        = RSTRING_PTR(string);
569     char    *start      = src;                  // remember this so we can check if we're at the start
570     long    len         = RSTRING_LEN(string);
571     char    *end        = src + len;
572
573     // start with a destination buffer twice the size of the source, will realloc if necessary
574     // slop = (len / 8) * 8 (ie. one in every 8 characters can be converted into an entity, each entity requires 8 bytes)
575     // this efficiently handles the most common case (where the size of the buffer doesn't change much)
576     char    *dest       = ALLOC_N(char, len * 2);
577     char    *dest_ptr   = dest; // hang on to this so we can pass it to free() later
578     char    *non_space  = dest; // remember last non-space character output
579     while (src < end)
580     {
581         // need at most 8 characters (8 bytes) to display each character
582         if (dest + 8 > dest_ptr + len)                      // outgrowing buffer, must reallocate
583         {
584             char *old_dest      = dest;
585             char *old_dest_ptr  = dest_ptr;
586             len                 = len + (end - src) * 8;    // allocate enough for worst case
587             dest                = realloc(dest_ptr, len);   // will never have to realloc more than once
588             if (dest == NULL)
589             {
590                 // would have used reallocf, but this has to run on Linux too, not just Darwin
591                 free(dest_ptr);
592                 rb_raise(rb_eNoMemError, "failed to re-allocate temporary storage (memory allocation error)");
593             }
594             dest_ptr    = dest;
595             dest        = dest_ptr + (old_dest - old_dest_ptr);
596             non_space   = dest_ptr + (non_space - old_dest_ptr);
597         }
598
599         if (*src == '"')                 // QUOT
600         {
601             char quot_entity_literal[] = { '&', 'q', 'u', 'o', 't', ';' };  // no trailing NUL
602             memcpy(dest, quot_entity_literal, sizeof(quot_entity_literal));
603             dest += sizeof(quot_entity_literal);
604         }
605         else if (*src == '&')            // AMP
606         {
607             char amp_entity_literal[] = { '&', 'a', 'm', 'p', ';' };    // no trailing NUL
608             memcpy(dest, amp_entity_literal, sizeof(amp_entity_literal));
609             dest += sizeof(amp_entity_literal);
610         }
611         else if (*src == '<')           // LESS_THAN
612         {
613             free(dest_ptr);
614             rb_raise(rb_eRangeError, "invalid link text (\"<\" may not appear in link text)");
615         }
616         else if (*src == '>')           // GREATER_THAN
617         {
618             free(dest_ptr);
619             rb_raise(rb_eRangeError, "invalid link text (\">\" may not appear in link text)");
620         }
621         else if (*src == ' ' && src == start && rollback == Qfalse)
622             start++;                // we eat leading space
623         else if (*src >= 0x20 && *src <= 0x7e)    // printable ASCII
624         {
625             *dest = *src;
626             dest++;
627         }
628         else    // all others: must convert to entities
629         {
630             long        width;
631             VALUE       entity      = _Wikitext_utf32_char_to_entity(_Wikitext_utf8_to_utf32(src, end, &width, dest_ptr));
632             char        *entity_src = RSTRING_PTR(entity);
633             long        entity_len  = RSTRING_LEN(entity); // should always be 8 characters (8 bytes)
634             memcpy(dest, entity_src, entity_len);
635             dest        += entity_len;
636             src         += width;
637             non_space   = dest;
638             continue;
639         }
640         if (*src != ' ')
641             non_space = dest;
642         src++;
643     }
644
645     // trim trailing space if necessary
646     if (rollback == Qfalse && non_space > dest_ptr && dest != non_space)
647         len = non_space - dest_ptr;
648     else
649         len = dest - dest_ptr;
650     VALUE out = rb_str_new(dest_ptr, len);
651     free(dest_ptr);
652     return out;
653 }
654
655 VALUE Wikitext_parser_sanitize_link_target(VALUE self, VALUE string)
656 {
657     parser_t parser;
658     parser.link_target          = string;
659     return _Wikitext_parser_sanitize_link_target(&parser, Qfalse);
660 }
661
662 // encodes the input string according to RFCs 2396 and 2718
663 // leading and trailing whitespace trimmed
664 // note that the first character of the target link is not case-sensitive
665 // (this is a recommended application-level constraint; it is not imposed at this level)
666 // this is to allow links like:
667 //         ...the [[foo]] is...
668 // to be equivalent to:
669 //         thing. [[Foo]] was...
670 // this is also where we check treat_slash_as_special is true and act accordingly
671 // basically any link target matching /\A[a-z]+\/\d+\z/ is flagged as special
672 inline static void _Wikitext_parser_encode_link_target(parser_t *parser)
673 {
674     VALUE in                = StringValue(parser->link_target);
675     char        *input      = RSTRING_PTR(in);
676     char        *start      = input;            // remember this so we can check if we're at the start
677     long        len         = RSTRING_LEN(in);
678     if (!(len > 0))
679         return;
680     char        *end        = input + len;
681     static char hex[]       = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f' };
682
683     // this potential shortcut requires an (admittedly cheap) prescan, so only do it when treat_slash_as_special is true
684     parser->special_link = Qfalse;
685     if (parser->treat_slash_as_special == Qtrue)
686     {
687         char *c = input;                                    // \A
688         while (c < end && *c >= 'a' && *c <= 'z')           // [a-z]
689             c++;                                            // +
690         if (c > start && c < end && *c++ == '/')            // \/
691         {
692             while (c < end && *c >= '0' && *c <= '9')       // \d
693             {
694                 c++;                                        // +
695                 if (c == end)                               // \z
696                 {
697                     // matches /\A[a-z]+\/\d+\z/ so no transformation required
698                     parser->special_link = Qtrue;
699                     return;
700                 }
701             }
702         }
703     }
704
705     // to avoid most reallocations start with a destination buffer twice the size of the source
706     // this handles the most common case (where most chars are in the ASCII range and don't require more storage, but there are
707     // often quite a few spaces, which are encoded as "%20" and occupy 3 bytes)
708     // the worst case is where _every_ byte must be written out using 3 bytes
709     long        dest_len    = len * 2;
710     char        *dest       = ALLOC_N(char, dest_len);
711     char        *dest_ptr   = dest; // hang on to this so we can pass it to free() later
712     char        *non_space  = dest; // remember last non-space character output
713     for (; input < end; input++)
714     {
715         if ((dest + 3) > (dest_ptr + dest_len))     // worst case: a single character may grow to 3 characters once encoded
716         {
717             // outgrowing buffer, must reallocate
718             char *old_dest      = dest;
719             char *old_dest_ptr  = dest_ptr;
720             dest_len            += len;
721             dest                = realloc(dest_ptr, dest_len);
722             if (dest == NULL)
723             {
724                 // would have used reallocf, but this has to run on Linux too, not just Darwin
725                 free(dest_ptr);
726                 rb_raise(rb_eNoMemError, "failed to re-allocate temporary storage (memory allocation error)");
727             }
728             dest_ptr    = dest;
729             dest        = dest_ptr + (old_dest - old_dest_ptr);
730             non_space   = dest_ptr + (non_space - old_dest_ptr);
731         }
732
733         // pass through unreserved characters
734         if (((*input >= 'a') && (*input <= 'z')) ||
735             ((*input >= 'A') && (*input <= 'Z')) ||
736             ((*input >= '0') && (*input <= '9')) ||
737             (*input == '-') ||
738             (*input == '_') ||
739             (*input == '.') ||
740             (*input == '~'))
741         {
742             *dest++     = *input;
743             non_space   = dest;
744         }
745         else if (*input == ' ' && input == start)
746             start++;                    // we eat leading space
747         else if (*input == ' ' && parser->space_to_underscore == Qtrue)
748             *dest++     = '_';
749         else    // everything else gets URL-encoded
750         {
751             *dest++     = '%';
752             *dest++     = hex[(unsigned char)(*input) / 16];   // left
753             *dest++     = hex[(unsigned char)(*input) % 16];   // right
754             if (*input != ' ')
755                 non_space = dest;
756         }
757     }
758
759     // trim trailing space if necessary
760     if (non_space > dest_ptr && dest != non_space)
761         dest_len = non_space - dest_ptr;
762     else
763         dest_len = dest - dest_ptr;
764     parser->link_target = rb_str_new(dest_ptr, dest_len);
765     free(dest_ptr);
766 }
767
768 VALUE Wikitext_parser_encode_link_target(VALUE self, VALUE in)
769 {
770     parser_t parser;
771     parser.link_target              = in;
772     parser.treat_slash_as_special   = Qfalse;
773     parser.space_to_underscore      = Qfalse;
774     _Wikitext_parser_encode_link_target(&parser);
775     return parser.link_target;
776 }
777
778 // this method exposed for testing only
779 VALUE Wikitext_parser_encode_special_link_target(VALUE self, VALUE in)
780 {
781     parser_t parser;
782     parser.link_target              = in;
783     parser.treat_slash_as_special   = Qtrue;
784     parser.space_to_underscore      = Qfalse;
785     _Wikitext_parser_encode_link_target(&parser);
786     return parser.link_target;
787 }
788
789 // not sure whether these rollback functions should be inline: could refactor them into a single non-inlined function
790 inline void _Wikitext_rollback_failed_link(parser_t *parser)
791 {
792     if (!IN(LINK_START))
793         return; // nothing to do!
794     int scope_includes_separator = IN(SEPARATOR);
795     _Wikitext_pop_from_stack_up_to(parser, Qnil, LINK_START, Qtrue);
796     rb_str_cat(parser->output, link_start, sizeof(link_start) - 1);
797     if (!NIL_P(parser->link_target))
798     {
799         VALUE sanitized = _Wikitext_parser_sanitize_link_target(parser, Qtrue);
800         rb_str_append(parser->output, sanitized);
801         if (scope_includes_separator)
802         {
803             rb_str_cat(parser->output, separator, sizeof(separator) - 1);
804             if (!NIL_P(parser->link_text))
805                 rb_str_append(parser->output, parser->link_text);
806         }
807     }
808     parser->capture     = Qnil;
809     parser->link_target = Qnil;
810     parser->link_text   = Qnil;
811 }
812
813 inline void _Wikitext_rollback_failed_external_link(parser_t *parser)
814 {
815     if (!IN(EXT_LINK_START))
816         return; // nothing to do!
817     int scope_includes_space = IN(SPACE);
818     _Wikitext_pop_from_stack_up_to(parser, Qnil, EXT_LINK_START, Qtrue);
819     rb_str_cat(parser->output, ext_link_start, sizeof(ext_link_start) - 1);
820     if (!NIL_P(parser->link_target))
821     {
822         if (parser->autolink == Qtrue)
823             parser->link_target = _Wikitext_hyperlink(Qnil, parser->link_target, parser->link_target, parser->external_link_class);
824         rb_str_append(parser->output, parser->link_target);
825         if (scope_includes_space)
826         {
827             rb_str_cat(parser->output, space, sizeof(space) - 1);
828             if (!NIL_P(parser->link_text))
829                 rb_str_append(parser->output, parser->link_text);
830         }
831     }
832     parser->capture     = Qnil;
833     parser->link_target = Qnil;
834     parser->link_text   = Qnil;
835 }
836
837 VALUE Wikitext_parser_initialize(int argc, VALUE *argv, VALUE self)
838 {
839     // process arguments
840     VALUE options;
841     if (rb_scan_args(argc, argv, "01", &options) == 0) // 0 mandatory arguments, 1 optional argument
842         options = Qnil;
843
844     // defaults
845     VALUE autolink                  = Qtrue;
846     VALUE line_ending               = rb_str_new2("\n");
847     VALUE external_link_class       = rb_str_new2("external");
848     VALUE mailto_class              = rb_str_new2("mailto");
849     VALUE internal_link_prefix      = rb_str_new2("/wiki/");
850     VALUE img_prefix                = rb_str_new2("/images/");
851     VALUE space_to_underscore       = Qfalse;
852     VALUE treat_slash_as_special    = Qtrue;
853
854     // process options hash (override defaults)
855     if (!NIL_P(options) && TYPE(options) == T_HASH)
856     {
857 #define OVERRIDE_IF_SET(name)   rb_funcall(options, rb_intern("has_key?"), 1, ID2SYM(rb_intern(#name))) == Qtrue ? \
858                                 rb_hash_aref(options, ID2SYM(rb_intern(#name))) : name
859         autolink                = OVERRIDE_IF_SET(autolink);
860         line_ending             = OVERRIDE_IF_SET(line_ending);
861         external_link_class     = OVERRIDE_IF_SET(external_link_class);
862         mailto_class            = OVERRIDE_IF_SET(mailto_class);
863         internal_link_prefix    = OVERRIDE_IF_SET(internal_link_prefix);
864         img_prefix              = OVERRIDE_IF_SET(img_prefix);
865         space_to_underscore     = OVERRIDE_IF_SET(space_to_underscore);
866         treat_slash_as_special  = OVERRIDE_IF_SET(treat_slash_as_special);
867     }
868
869     // no need to call super here; rb_call_super()
870     rb_iv_set(self, "@autolink",                autolink);
871     rb_iv_set(self, "@line_ending",             line_ending);
872     rb_iv_set(self, "@external_link_class",     external_link_class);
873     rb_iv_set(self, "@mailto_class",            mailto_class);
874     rb_iv_set(self, "@internal_link_prefix",    internal_link_prefix);
875     rb_iv_set(self, "@img_prefix",              img_prefix);
876     rb_iv_set(self, "@space_to_underscore",     space_to_underscore);
877     rb_iv_set(self, "@treat_slash_as_special",  treat_slash_as_special);
878     return self;
879 }
880
881 VALUE Wikitext_parser_profiling_parse(VALUE self, VALUE string)
882 {
883     for (int i = 0; i < 100000; i++)
884         Wikitext_parser_parse(1, &string, self);
885 }
886
887 VALUE Wikitext_parser_parse(int argc, VALUE *argv, VALUE self)
888 {
889     // process arguments
890     VALUE string, options;
891     if (rb_scan_args(argc, argv, "11", &string, &options) == 1) // 1 mandatory argument, 1 optional argument
892         options = Qnil;
893     if (NIL_P(string))
894         return Qnil;
895     string = StringValue(string);
896
897     // process options hash
898     int base_indent = 0;
899     VALUE indent = Qnil;
900     if (!NIL_P(options) && TYPE(options) == T_HASH)
901     {
902         indent = rb_hash_aref(options, ID2SYM(rb_intern("indent")));
903         base_indent = NUM2INT(indent);
904         if (base_indent < 0)
905             base_indent = 0;
906     }
907
908     // set up scanner
909     char *p = RSTRING_PTR(string);
910     long len = RSTRING_LEN(string);
911     char *pe = p + len;
912
913     // access these once per parse
914     VALUE line_ending   = rb_iv_get(self, "@line_ending");
915     line_ending         = StringValue(line_ending);
916     VALUE link_class    = rb_iv_get(self, "@external_link_class");
917     link_class          = NIL_P(link_class) ? Qnil : StringValue(link_class);
918     VALUE mailto_class  = rb_iv_get(self, "@mailto_class");
919     mailto_class        = NIL_P(mailto_class) ? Qnil : StringValue(mailto_class);
920     VALUE prefix        = rb_iv_get(self, "@internal_link_prefix");
921
922     // set up parser struct to make passing parameters a little easier
923     // eventually this will encapsulate most or all of the variables above
924     parser_t _parser;
925     parser_t *parser                = &_parser;
926     parser->output                  = rb_str_new2("");
927     parser->capture                 = Qnil;
928     parser->link_target             = Qnil;
929     parser->link_text               = Qnil;
930     parser->external_link_class     = link_class;
931     parser->img_prefix              = rb_iv_get(self, "@img_prefix");
932     parser->scope                   = ary_new();
933     volatile VALUE scope_gc         = Data_Wrap_Struct(rb_cObject, 0, ary_free, parser->scope);
934     parser->line                    = ary_new();
935     volatile VALUE line_gc          = Data_Wrap_Struct(rb_cObject, 0, ary_free, parser->line);
936     parser->line_buffer             = ary_new();
937     volatile VALUE line_buffer_gc   = Data_Wrap_Struct(rb_cObject, 0, ary_free, parser->line_buffer);
938     parser->pending_crlf            = Qfalse;
939     parser->autolink                = rb_iv_get(self, "@autolink");
940     parser->treat_slash_as_special  = rb_iv_get(self, "@treat_slash_as_special");
941     parser->space_to_underscore     = rb_iv_get(self, "@space_to_underscore");
942     parser->special_link            = Qfalse;
943     parser->line_ending             = str_new_from_string(line_ending);
944     parser->base_indent             = base_indent;
945     parser->current_indent          = 0;
946     parser->tabulation              = NULL;
947
948     token_t _token;
949     _token.type = NO_TOKEN;
950     token_t *token = NULL;
951     do
952     {
953         // note that whenever we grab a token we push it into the line buffer
954         // this provides us with context-sensitive "memory" of what's been seen so far on this line
955 #define NEXT_TOKEN()    token = &_token, next_token(token, token, NULL, pe), ary_push(parser->line_buffer, token->type)
956
957         // check to see if we have a token hanging around from a previous iteration of this loop
958         if (token == NULL)
959         {
960             if (_token.type == NO_TOKEN)
961             {
962                 // first time here (haven't started scanning yet)
963                 token = &_token;
964                 next_token(token, NULL, p, pe);
965                 ary_push(parser->line_buffer, token->type);
966             }
967             else
968                 // already scanning
969                 NEXT_TOKEN();
970         }
971         int type = token->type;
972
973         // many restrictions depend on what is at the top of the stack
974         int top = ary_entry(parser->scope, -1);
975
976         // can't declare new variables inside a switch statement, so predeclare them here
977         long remove_strong          = -1;
978         long remove_em              = -1;
979
980         // general purpose counters and flags
981         long i                      = 0;
982         long j                      = 0;
983         long k                      = 0;
984
985         // The following giant switch statement contains cases for all the possible token types.
986         // In the most basic sense we are emitting the HTML that corresponds to each token,
987         // but some tokens require context information in order to decide what to output.
988         // For example, does the STRONG token (''') translate to <strong> or </strong>?
989         // So when looking at any given token we have three state-maintaining variables which gives us a notion of "where we are":
990         //
991         //  - the "scope" stack (indicates what HTML DOM structures we are currently nested inside, similar to a CSS selector)
992         //  - the line buffer (records tokens seen so far on the current line)
993         //  - the line "scope" stack (indicates what the scope should be based only on what is visible on the line so far)
994         //
995         // Although this is fairly complicated, there is one key simplifying factor:
996         // The translator continuously performs auto-correction, and this means that we always have a guarantee that the
997         // scope stack (up to the current token) is valid; our translator can take this as a given.
998         // Auto-correction basically consists of inserting missing tokens (preventing subsquent HTML from being messed up),
999         // or converting illegal (unexpected) tokens to their plain text equivalents (providing visual feedback to Wikitext author).
1000         switch (type)
1001         {
1002             case PRE:
1003                 if (IN(NO_WIKI_START) || IN(PRE_START))
1004                 {
1005                     rb_str_cat(parser->output, space, sizeof(space) - 1);
1006                     break;
1007                 }
1008                 else if (IN(BLOCKQUOTE_START))
1009                 {
1010                     // this kind of nesting not allowed (to avoid user confusion)
1011                     _Wikitext_pop_excess_elements(parser);
1012                     _Wikitext_start_para_if_necessary(parser);
1013                     i = NIL_P(parser->capture) ? parser->output : parser->capture;
1014                     rb_str_cat(i, space, sizeof(space) - 1);
1015                     break;
1016                 }
1017
1018                 // count number of BLOCKQUOTE tokens in line buffer and in scope stack
1019                 ary_push(parser->line, PRE);
1020                 i = ary_count(parser->line, BLOCKQUOTE);
1021                 j = ary_count(parser->scope, BLOCKQUOTE);
1022                 if (i < j)
1023                 {
1024                     // must pop (reduce nesting level)
1025                     for (i = j - i; i > 0; i--)
1026                         _Wikitext_pop_from_stack_up_to(parser, Qnil, BLOCKQUOTE, Qtrue);
1027                 }
1028
1029                 if (!IN(PRE))
1030                 {
1031                     parser->pending_crlf = Qfalse;
1032                     _Wikitext_pop_from_stack_up_to(parser, Qnil, BLOCKQUOTE, Qfalse);
1033                     _Wikitext_indent(parser);
1034                     rb_str_cat(parser->output, pre_start, sizeof(pre_start) - 1);
1035                     ary_push(parser->scope, PRE);
1036                 }
1037                 break;
1038
1039             case PRE_START:
1040                 if (IN(NO_WIKI_START) || IN(PRE) || IN(PRE_START))
1041                     rb_str_cat(parser->output, escaped_pre_start, sizeof(escaped_pre_start) - 1);
1042                 else if (IN(BLOCKQUOTE_START))
1043                 {
1044                     _Wikitext_rollback_failed_link(parser);             // if any
1045                     _Wikitext_rollback_failed_external_link(parser);    // if any
1046                     _Wikitext_pop_from_stack_up_to(parser, Qnil, BLOCKQUOTE_START, Qfalse);
1047                     _Wikitext_indent(parser);
1048                     rb_str_cat(parser->output, pre_start, sizeof(pre_start) - 1);
1049                     ary_push(parser->scope, PRE_START);
1050                     ary_push(parser->line, PRE_START);
1051                 }
1052                 else if (parser->scope->count == 0 || (IN(P) && !IN(BLOCKQUOTE)))
1053                 {
1054                     // would be nice to eliminate the repetition here but it's probably the clearest way
1055                     _Wikitext_rollback_failed_link(parser);             // if any
1056                     _Wikitext_rollback_failed_external_link(parser);    // if any
1057                     _Wikitext_pop_from_stack_up_to(parser, Qnil, P, Qtrue);
1058                     _Wikitext_indent(parser);
1059                     rb_str_cat(parser->output, pre_start, sizeof(pre_start) - 1);
1060                     ary_push(parser->scope, PRE_START);
1061                     ary_push(parser->line, PRE_START);
1062                 }
1063                 else
1064                 {
1065                     // everywhere else, PRE_START is illegal (in LI, BLOCKQUOTE, H1_START etc)
1066                     i = NIL_P(parser->capture) ? parser->output : parser->capture;
1067                     _Wikitext_pop_excess_elements(parser);
1068                     _Wikitext_start_para_if_necessary(parser);
1069                     rb_str_cat(i, escaped_pre_start, sizeof(escaped_pre_start) - 1);
1070                 }
1071                 break;
1072
1073             case PRE_END:
1074                 if (IN(NO_WIKI_START) || IN(PRE))
1075                     rb_str_cat(parser->output, escaped_pre_end, sizeof(escaped_pre_end) - 1);
1076                 else
1077                 {
1078                     if (IN(PRE_START))
1079                         _Wikitext_pop_from_stack_up_to(parser, parser->output, PRE_START, Qtrue);
1080                     else
1081                     {
1082                         i = NIL_P(parser->capture) ? parser->output : parser->capture;
1083                         _Wikitext_pop_excess_elements(parser);
1084                         _Wikitext_start_para_if_necessary(parser);
1085                         rb_str_cat(i, escaped_pre_end, sizeof(escaped_pre_end) - 1);
1086                     }
1087                 }
1088                 break;
1089
1090             case BLOCKQUOTE:
1091                 if (IN(NO_WIKI_START) || IN(PRE_START))
1092                     // no need to check for <pre>; can never appear inside it
1093                     rb_str_cat(parser->output, escaped_blockquote, TOKEN_LEN(token) + 3); // will either emit "&gt;" or "&gt; "
1094                 else if (IN(BLOCKQUOTE_START))
1095                 {
1096                     // this kind of nesting not allowed (to avoid user confusion)
1097                     _Wikitext_pop_excess_elements(parser);
1098                     _Wikitext_start_para_if_necessary(parser);
1099                     i = NIL_P(parser->capture) ? parser->output : parser->capture;
1100                     rb_str_cat(i, escaped_blockquote, TOKEN_LEN(token) + 3); // will either emit "&gt;" or "&gt; "
1101                     break;
1102                 }
1103                 else
1104                 {
1105                     ary_push(parser->line, BLOCKQUOTE);
1106
1107                     // count number of BLOCKQUOTE tokens in line buffer and in scope stack
1108                     i = ary_count(parser->line, BLOCKQUOTE);
1109                     j = ary_count(parser->scope, BLOCKQUOTE);
1110
1111                     // given that BLOCKQUOTE tokens can be nested, peek ahead and see if there are any more which might affect the decision to push or pop
1112                     while (NEXT_TOKEN(), (token->type == BLOCKQUOTE))
1113                     {
1114                         ary_push(parser->line, BLOCKQUOTE);
1115                         i++;
1116                     }
1117
1118                     // now decide whether to push, pop or do nothing
1119                     if (i > j)
1120                     {
1121                         // must push (increase nesting level)
1122                         _Wikitext_pop_from_stack_up_to(parser, Qnil, BLOCKQUOTE, Qfalse);
1123                         for (i = i - j; i > 0; i--)
1124                         {
1125                             _Wikitext_indent(parser);
1126                             rb_str_cat(parser->output, blockquote_start, sizeof(blockquote_start) - 1);
1127                             rb_str_cat(parser->output, parser->line_ending->ptr, parser->line_ending->len);
1128                             ary_push(parser->scope, BLOCKQUOTE);
1129                         }
1130                     }
1131                     else if (i < j)
1132                     {
1133                         // must pop (reduce nesting level)
1134                         for (i = j - i; i > 0; i--)
1135                             _Wikitext_pop_from_stack_up_to(parser, Qnil, BLOCKQUOTE, Qtrue);
1136                     }
1137
1138                     // jump to top of the loop to process token we scanned during lookahead
1139                     continue;
1140                 }
1141                 break;
1142
1143             case BLOCKQUOTE_START:
1144                 if (IN(NO_WIKI_START) || IN(PRE) || IN(PRE_START))
1145                     rb_str_cat(parser->output, escaped_blockquote_start, sizeof(escaped_blockquote_start) - 1);
1146                 else if (IN(BLOCKQUOTE_START))
1147                 {
1148                     // nesting is fine here
1149                     _Wikitext_rollback_failed_link(parser);             // if any
1150                     _Wikitext_rollback_failed_external_link(parser);    // if any
1151                     _Wikitext_pop_from_stack_up_to(parser, Qnil, BLOCKQUOTE_START, Qfalse);
1152                     _Wikitext_indent(parser);
1153                     rb_str_cat(parser->output, blockquote_start, sizeof(blockquote_start) - 1);
1154                     rb_str_cat(parser->output, parser->line_ending->ptr, parser->line_ending->len);
1155                     ary_push(parser->scope, BLOCKQUOTE_START);
1156                     ary_push(parser->line, BLOCKQUOTE_START);
1157                 }
1158                 else if (parser->scope->count == 0 || (IN(P) && !IN(BLOCKQUOTE)))
1159                 {
1160                     // would be nice to eliminate the repetition here but it's probably the clearest way
1161                     _Wikitext_rollback_failed_link(parser);             // if any
1162                     _Wikitext_rollback_failed_external_link(parser);    // if any
1163                     _Wikitext_pop_from_stack_up_to(parser, Qnil, P, Qtrue);
1164                     _Wikitext_indent(parser);
1165                     rb_str_cat(parser->output, blockquote_start, sizeof(blockquote_start) - 1);
1166                     rb_str_cat(parser->output, parser->line_ending->ptr, parser->line_ending->len);
1167                     ary_push(parser->scope, BLOCKQUOTE_START);
1168                     ary_push(parser->line, BLOCKQUOTE_START);
1169                 }
1170                 else
1171                 {
1172                     // everywhere else, BLOCKQUOTE_START is illegal (in LI, BLOCKQUOTE, H1_START etc)
1173                     i = NIL_P(parser->capture) ? parser->output : parser->capture;
1174                     _Wikitext_pop_excess_elements(parser);
1175                     _Wikitext_start_para_if_necessary(parser);
1176                     rb_str_cat(i, escaped_blockquote_start, sizeof(escaped_blockquote_start) - 1);
1177                 }
1178                 break;
1179
1180             case BLOCKQUOTE_END:
1181                 if (IN(NO_WIKI_START) || IN(PRE) || IN(PRE_START))
1182                     rb_str_cat(parser->output, escaped_blockquote_end, sizeof(escaped_blockquote_end) - 1);
1183                 else
1184                 {
1185                     if (IN(BLOCKQUOTE_START))
1186                         _Wikitext_pop_from_stack_up_to(parser, parser->output, BLOCKQUOTE_START, Qtrue);
1187                     else
1188                     {
1189                         i = NIL_P(parser->capture) ? parser->output : parser->capture;
1190                         _Wikitext_pop_excess_elements(parser);
1191                         _Wikitext_start_para_if_necessary(parser);
1192                         rb_str_cat(i, escaped_blockquote_end, sizeof(escaped_blockquote_end) - 1);
1193                     }
1194                 }
1195                 break;
1196
1197             case NO_WIKI_START:
1198                 if (IN(NO_WIKI_START) || IN(PRE) || IN(PRE_START))
1199                     rb_str_cat(parser->output, escaped_no_wiki_start, sizeof(escaped_no_wiki_start) - 1);
1200                 else
1201                 {
1202                     _Wikitext_pop_excess_elements(parser);
1203                     _Wikitext_start_para_if_necessary(parser);
1204                     ary_push(parser->scope, NO_WIKI_START);
1205                     ary_push(parser->line, NO_WIKI_START);
1206                 }
1207                 break;
1208
1209             case NO_WIKI_END:
1210                 if (IN(NO_WIKI_START))
1211                     // <nowiki> should always only ever be the last item in the stack, but use the helper routine just in case
1212                     _Wikitext_pop_from_stack_up_to(parser, Qnil, NO_WIKI_START, Qtrue);
1213                 else
1214                 {
1215                     _Wikitext_pop_excess_elements(parser);
1216                     _Wikitext_start_para_if_necessary(parser);
1217                     rb_str_cat(parser->output, escaped_no_wiki_end, sizeof(escaped_no_wiki_end) - 1);
1218                 }
1219                 break;
1220
1221             case STRONG_EM:
1222                 if (IN(NO_WIKI_START) || IN(PRE) || IN(PRE_START))
1223                 {
1224                     rb_str_cat(parser->output, literal_strong_em, sizeof(literal_strong_em) - 1);
1225                     break;
1226                 }
1227
1228                 i = NIL_P(parser->capture) ? parser->output : parser->capture;
1229                 _Wikitext_pop_excess_elements(parser);
1230
1231                 // if you've seen STRONG/STRONG_START or EM/EM_START, must close them in the reverse order that you saw them!
1232                 // otherwise, must open them
1233                 remove_strong  = -1;
1234                 remove_em      = -1;
1235                 j              = parser->scope->count;
1236                 for (j = j - 1; j >= 0; j--)
1237                 {
1238                     int val = ary_entry(parser->scope, j);
1239                     if (val == STRONG || val == STRONG_START)
1240                     {
1241                         rb_str_cat(i, strong_end, sizeof(strong_end) - 1);
1242                         remove_strong = j;
1243                     }
1244                     else if (val == EM || val == EM_START)
1245                     {
1246                         rb_str_cat(i, em_end, sizeof(em_end) - 1);
1247                         remove_em = j;
1248                     }
1249                 }
1250
1251                 if (remove_strong > remove_em)      // must remove strong first
1252                 {
1253                     ary_pop(parser->scope);
1254                     if (remove_em > -1)
1255                         ary_pop(parser->scope);
1256                     else    // there was no em to remove!, so consider this an opening em tag
1257                     {
1258                         rb_str_cat(i, em_start, sizeof(em_start) - 1);
1259                         ary_push(parser->scope, EM);
1260                         ary_push(parser->line, EM);
1261                     }
1262                 }
1263                 else if (remove_em > remove_strong) // must remove em first
1264                 {
1265                     ary_pop(parser->scope);
1266                     if (remove_strong > -1)
1267                         ary_pop(parser->scope);
1268                     else    // there was no strong to remove!, so consider this an opening strong tag
1269                     {
1270                         rb_str_cat(i, strong_start, sizeof(strong_start) - 1);
1271                         ary_push(parser->scope, STRONG);
1272                         ary_push(parser->line, STRONG);
1273                     }
1274                 }
1275                 else    // no strong or em to remove, so this must be a new opening of both
1276                 {
1277                     _Wikitext_start_para_if_necessary(parser);
1278                     rb_str_cat(i, strong_em_start, sizeof(strong_em_start) - 1);
1279                     ary_push(parser->scope, STRONG);
1280                     ary_push(parser->line, STRONG);
1281                     ary_push(parser->scope, EM);
1282                     ary_push(parser->line, EM);
1283                 }
1284                 break;
1285
1286             case STRONG:
1287                 if (IN(NO_WIKI_START) || IN(PRE) || IN(PRE_START))
1288                     rb_str_cat(parser->output, literal_strong, sizeof(literal_strong) - 1);
1289                 else
1290                 {
1291                     i = NIL_P(parser->capture) ? parser->output : parser->capture;
1292                     if (IN(STRONG_START))
1293                         // already in span started with <strong>, no choice but to emit this literally
1294                         rb_str_cat(parser->output, literal_strong, sizeof(literal_strong) - 1);
1295                     else if (IN(STRONG))
1296                         // STRONG already seen, this is a closing tag
1297                         _Wikitext_pop_from_stack_up_to(parser, i, STRONG, Qtrue);
1298                     else
1299                     {
1300                         // this is a new opening
1301                         _Wikitext_pop_excess_elements(parser);
1302                         _Wikitext_start_para_if_necessary(parser);
1303                         rb_str_cat(i, strong_start, sizeof(strong_start) - 1);
1304                         ary_push(parser->scope, STRONG);
1305                         ary_push(parser->line, STRONG);
1306                     }
1307                 }
1308                 break;
1309
1310             case STRONG_START:
1311                 if (IN(NO_WIKI_START) || IN(PRE) || IN(PRE_START))
1312                     rb_str_cat(parser->output, escaped_strong_start, sizeof(escaped_strong_start) - 1);
1313                 else
1314                 {
1315                     i = NIL_P(parser->capture) ? parser->output : parser->capture;
1316                     if (IN(STRONG_START) || IN(STRONG))
1317                         rb_str_cat(parser->output, escaped_strong_start, sizeof(escaped_strong_start) - 1);
1318                     else
1319                     {
1320                         _Wikitext_pop_excess_elements(parser);
1321                         _Wikitext_start_para_if_necessary(parser);
1322                         rb_str_cat(i, strong_start, sizeof(strong_start) - 1);
1323                         ary_push(parser->scope, STRONG_START);
1324                         ary_push(parser->line, STRONG_START);
1325                     }
1326                 }
1327                 break;
1328
1329             case STRONG_END:
1330                 if (IN(NO_WIKI_START) || IN(PRE) || IN(PRE_START))
1331                     rb_str_cat(parser->output, escaped_strong_end, sizeof(escaped_strong_end) - 1);
1332                 else
1333                 {
1334                     i = NIL_P(parser->capture) ? parser->output : parser->capture;
1335                     if (IN(STRONG_START))
1336                         _Wikitext_pop_from_stack_up_to(parser, i, STRONG_START, Qtrue);
1337                     else
1338                     {
1339                         // no STRONG_START in scope, so must interpret the STRONG_END without any special meaning
1340                         _Wikitext_pop_excess_elements(parser);
1341                         _Wikitext_start_para_if_necessary(parser);
1342                         rb_str_cat(i, escaped_strong_end, sizeof(escaped_strong_end) - 1);
1343                     }
1344                 }
1345                 break;
1346
1347             case EM:
1348                 if (IN(NO_WIKI_START) || IN(PRE) || IN(PRE_START))
1349                     rb_str_cat(parser->output, literal_em, sizeof(literal_em) - 1);
1350                 else
1351                 {
1352                     i = NIL_P(parser->capture) ? parser->output : parser->capture;
1353                     if (IN(EM_START))
1354                         // already in span started with <em>, no choice but to emit this literally
1355                         rb_str_cat(parser->output, literal_em, sizeof(literal_em) - 1);
1356                     else if (IN(EM))
1357                         // EM already seen, this is a closing tag
1358                         _Wikitext_pop_from_stack_up_to(parser, i, EM, Qtrue);
1359                     else
1360                     {
1361                         // this is a new opening
1362                         _Wikitext_pop_excess_elements(parser);
1363                         _Wikitext_start_para_if_necessary(parser);
1364                         rb_str_cat(i, em_start, sizeof(em_start) - 1);
1365                         ary_push(parser->scope, EM);
1366                         ary_push(parser->line, EM);
1367                     }
1368                 }
1369                 break;
1370
1371             case EM_START:
1372                 if (IN(NO_WIKI_START) || IN(PRE) || IN(PRE_START))
1373                     rb_str_cat(parser->output, escaped_em_start, sizeof(escaped_em_start) - 1);
1374                 else
1375                 {
1376                     i = NIL_P(parser->capture) ? parser->output : parser->capture;
1377                     if (IN(EM_START) || IN(EM))
1378                         rb_str_cat(i, escaped_em_start, sizeof(escaped_em_start) - 1);
1379                     else
1380                     {
1381                         _Wikitext_pop_excess_elements(parser);
1382                         _Wikitext_start_para_if_necessary(parser);
1383                         rb_str_cat(i, em_start, sizeof(em_start) - 1);
1384                         ary_push(parser->scope, EM_START);
1385                         ary_push(parser->line, EM_START);
1386                     }
1387                 }
1388                 break;
1389
1390             case EM_END:
1391                 if (IN(NO_WIKI_START) || IN(PRE) || IN(PRE_START))
1392                     rb_str_cat(parser->output, escaped_em_end, sizeof(escaped_em_end) - 1);
1393                 else
1394                 {
1395                     i = NIL_P(parser->capture) ? parser->output : parser->capture;
1396                     if (IN(EM_START))
1397                         _Wikitext_pop_from_stack_up_to(parser, i, EM_START, Qtrue);
1398                     else
1399                     {
1400                         // no EM_START in scope, so must interpret the TT_END without any special meaning
1401                         _Wikitext_pop_excess_elements(parser);
1402                         _Wikitext_start_para_if_necessary(parser);
1403                         rb_str_cat(i, escaped_em_end, sizeof(escaped_em_end) - 1);
1404                     }
1405                 }
1406                 break;
1407
1408             case TT:
1409                 if (IN(NO_WIKI_START) || IN(PRE) || IN(PRE_START))
1410                     rb_str_cat(parser->output, backtick, sizeof(backtick) - 1);
1411                 else
1412                 {
1413                     i = NIL_P(parser->capture) ? parser->output : parser->capture;
1414                     if (IN(TT_START))
1415                         // already in span started with <tt>, no choice but to emit this literally
1416                         rb_str_cat(parser->output, backtick, sizeof(backtick) - 1);
1417                     else if (IN(TT))
1418                         // TT (`) already seen, this is a closing tag
1419                         _Wikitext_pop_from_stack_up_to(parser, i, TT, Qtrue);
1420                     else
1421                     {
1422                         // this is a new opening
1423                         _Wikitext_pop_excess_elements(parser);
1424                         _Wikitext_start_para_if_necessary(parser);
1425                         rb_str_cat(i, tt_start, sizeof(tt_start) - 1);
1426                         ary_push(parser->scope, TT);
1427                         ary_push(parser->line, TT);
1428                     }
1429                 }
1430                 break;
1431
1432             case TT_START:
1433                 if (IN(NO_WIKI_START) || IN(PRE) || IN(PRE_START))
1434                     rb_str_cat(parser->output, escaped_tt_start, sizeof(escaped_tt_start) - 1);
1435                 else
1436                 {
1437                     i = NIL_P(parser->capture) ? parser->output : parser->capture;
1438                     if (IN(TT_START) || IN(TT))
1439                         rb_str_cat(i, escaped_tt_start, sizeof(escaped_tt_start) - 1);
1440                     else
1441                     {
1442                         _Wikitext_pop_excess_elements(parser);
1443                         _Wikitext_start_para_if_necessary(parser);
1444                         rb_str_cat(i, tt_start, sizeof(tt_start) - 1);
1445                         ary_push(parser->scope, TT_START);
1446                         ary_push(parser->line, TT_START);
1447                     }
1448                 }
1449                 break;
1450
1451             case TT_END:
1452                 if (IN(NO_WIKI_START) || IN(PRE) || IN(PRE_START))
1453                     rb_str_cat(parser->output, escaped_tt_end, sizeof(escaped_tt_end) - 1);
1454                 else
1455                 {
1456                     i = NIL_P(parser->capture) ? parser->output : parser->capture;
1457                     if (IN(TT_START))
1458                         _Wikitext_pop_from_stack_up_to(parser, i, TT_START, Qtrue);
1459                     else
1460                     {
1461                         // no TT_START in scope, so must interpret the TT_END without any special meaning
1462                         _Wikitext_pop_excess_elements(parser);
1463                         _Wikitext_start_para_if_necessary(parser);
1464                         rb_str_cat(i, escaped_tt_end, sizeof(escaped_tt_end) - 1);
1465                     }
1466                 }
1467                 break;
1468
1469             case OL:
1470             case UL:
1471                 if (IN(NO_WIKI_START) || IN(PRE_START))
1472                 {
1473                     // no need to check for PRE; can never appear inside it
1474                     rb_str_cat(parser->output, token->start, TOKEN_LEN(token));
1475                     break;
1476                 }
1477
1478                 // count number of tokens in line and scope stacks
1479                 int bq_count = ary_count(parser->scope, BLOCKQUOTE_START);
1480                 i = parser->line->count - ary_count(parser->line, BLOCKQUOTE_START);
1481                 j = parser->scope->count - bq_count;
1482                 k = i;
1483
1484                 // list tokens can be nested so look ahead for any more which might affect the decision to push or pop
1485                 for (;;)
1486                 {
1487                     type = token->type;
1488                     if (type == OL || type == UL)
1489                     {
1490                         token = NULL;
1491                         if (i - k >= 2)                             // already seen at least one OL or UL
1492                         {
1493                             ary_push(parser->line, NESTED_LIST);    // which means this is a nested list
1494                             i += 3;
1495                         }
1496                         else
1497                             i += 2;
1498                         ary_push(parser->line, type);
1499                         ary_push(parser->line, LI);
1500
1501                         // want to compare line with scope but can only do so if scope has enough items on it
1502                         if (j >= i)
1503                         {
1504                             if (ary_entry(parser->scope, i + bq_count - 2) == type && ary_entry(parser->scope, i + bq_count - 1) == LI)
1505                             {
1506                                 // line and scope match at this point: do nothing yet
1507                             }
1508                             else
1509                             {
1510                                 // item just pushed onto line does not match corresponding slot of scope!
1511                                 for (; j >= i - 2; j--)
1512                                     // must pop back before emitting
1513                                     _Wikitext_pop_from_stack(parser, Qnil);
1514
1515                                 // will emit UL or OL, then LI
1516                                 break;
1517                             }
1518                         }
1519                         else        // line stack size now exceeds scope stack size: must increase nesting level
1520                             break;  // will emit UL or OL, then LI
1521                     }
1522                     else
1523                     {
1524                         // not a OL or UL token!
1525                         if (j == i)
1526                             // must close existing LI and re-open new one
1527                             _Wikitext_pop_from_stack(parser, Qnil);
1528                         else if (j > i)
1529                         {
1530                             // item just pushed onto line does not match corresponding slot of scope!
1531                             for (; j >= i; j--)
1532                                 // must pop back before emitting
1533                                 _Wikitext_pop_from_stack(parser, Qnil);
1534                         }
1535                         break;
1536                     }
1537                     NEXT_TOKEN();
1538                 }
1539
1540                 // will emit
1541                 if (type == OL || type == UL)
1542                 {
1543                     // if LI is at the top of a stack this is the start of a nested list
1544                     if (j > 0 && ary_entry(parser->scope, -1) == LI)
1545                     {
1546                         // so we should precede it with a CRLF, and indicate that it's a nested list
1547                         rb_str_cat(parser->output, parser->line_ending->ptr, parser->line_ending->len);
1548                         ary_push(parser->scope, NESTED_LIST);
1549                     }
1550                     else
1551                     {
1552                         // this is a new list
1553                         if (IN(BLOCKQUOTE_START))
1554                             _Wikitext_pop_from_stack_up_to(parser, Qnil, BLOCKQUOTE_START, Qfalse);
1555                         else
1556                             _Wikitext_pop_from_stack_up_to(parser, Qnil, BLOCKQUOTE, Qfalse);
1557                     }
1558
1559                     // emit
1560                     _Wikitext_indent(parser);
1561                     if (type == OL)
1562                         rb_str_cat(parser->output, ol_start, sizeof(ol_start) - 1);
1563                     else if (type == UL)
1564                         rb_str_cat(parser->output, ul_start, sizeof(ul_start) - 1);
1565                     ary_push(parser->scope, type);
1566                     rb_str_cat(parser->output, parser->line_ending->ptr, parser->line_ending->len);
1567                 }
1568                 else if (type == SPACE)
1569                     // silently throw away the optional SPACE token after final list marker
1570                     token = NULL;
1571
1572                 _Wikitext_indent(parser);
1573                 rb_str_cat(parser->output, li_start, sizeof(li_start) - 1);
1574                 ary_push(parser->scope, LI);
1575
1576                 // any subsequent UL or OL tokens on this line are syntax errors and must be emitted literally
1577                 if (type == OL || type == UL)
1578                 {
1579                     k = 0;
1580                     while (k++, NEXT_TOKEN(), (type = token->type))
1581                     {
1582                         if (type == OL || type == UL)
1583                             rb_str_cat(parser->output, token->start, TOKEN_LEN(token));
1584                         else if (type == SPACE && k == 1)
1585                         {
1586                             // silently throw away the optional SPACE token after final list marker
1587                             token = NULL;
1588                             break;
1589                         }
1590                         else
1591                             break;
1592                     }
1593                 }
1594
1595                 // jump to top of the loop to process token we scanned during lookahead
1596                 continue;
1597
1598             case H6_START:
1599             case H5_START:
1600             case H4_START:
1601             case H3_START:
1602             case H2_START:
1603             case H1_START:
1604                 if (IN(NO_WIKI_START) || IN(PRE_START))
1605                 {
1606                     // no need to check for PRE; can never appear inside it
1607                     rb_str_cat(parser->output, token->start, TOKEN_LEN(token));
1608                     break;
1609                 }
1610
1611                 // pop up to but not including the last BLOCKQUOTE on the scope stack
1612                 if (IN(BLOCKQUOTE_START))
1613                     _Wikitext_pop_from_stack_up_to(parser, Qnil, BLOCKQUOTE_START, Qfalse);
1614                 else
1615                     _Wikitext_pop_from_stack_up_to(parser, Qnil, BLOCKQUOTE, Qfalse);
1616
1617                 // count number of BLOCKQUOTE tokens in line buffer and in scope stack
1618                 ary_push(parser->line, type);
1619                 i = ary_count(parser->line, BLOCKQUOTE);
1620                 j = ary_count(parser->scope, BLOCKQUOTE);
1621
1622                 // decide whether we need to pop off excess BLOCKQUOTE tokens (will never need to push; that is handled above in the BLOCKQUOTE case itself)
1623                 if (i < j)
1624                 {
1625                     // must pop (reduce nesting level)
1626                     for (i = j - i; i > 0; i--)
1627                         _Wikitext_pop_from_stack_up_to(parser, Qnil, BLOCKQUOTE, Qtrue);
1628                 }
1629
1630                 // discard any whitespace here (so that "== foo ==" will be translated to "<h2>foo</h2>" rather than "<h2> foo </h2")
1631                 while (NEXT_TOKEN(), (token->type == SPACE))
1632                     ; // discard
1633
1634                 ary_push(parser->scope, type);
1635                 _Wikitext_indent(parser);
1636
1637                 // rather than repeat all that code for each kind of heading, share it and use a conditional here
1638                 if (type == H6_START)
1639                     rb_str_cat(parser->output, h6_start, sizeof(h6_start) - 1);
1640                 else if (type == H5_START)
1641                     rb_str_cat(parser->output, h5_start, sizeof(h5_start) - 1);
1642                 else if (type == H4_START)
1643                     rb_str_cat(parser->output, h4_start, sizeof(h4_start) - 1);
1644                 else if (type == H3_START)
1645                     rb_str_cat(parser->output, h3_start, sizeof(h3_start) - 1);
1646                 else if (type == H2_START)
1647                     rb_str_cat(parser->output, h2_start, sizeof(h2_start) - 1);
1648                 else if (type == H1_START)
1649                     rb_str_cat(parser->output, h1_start, sizeof(h1_start) - 1);
1650
1651                 // jump to top of the loop to process token we scanned during lookahead
1652                 continue;
1653
1654             case H6_END:
1655                 if (IN(NO_WIKI_START) || IN(PRE) || IN(PRE_START))
1656                     rb_str_cat(parser->output, literal_h6, sizeof(literal_h6) - 1);
1657                 else
1658                 {
1659                     _Wikitext_rollback_failed_external_link(parser); // if any
1660                     if (!IN(H6_START))
1661                     {
1662                         // literal output only if not in h6 scope (we stay silent in that case)
1663                         _Wikitext_start_para_if_necessary(parser);
1664                         rb_str_cat(parser->output, literal_h6, sizeof(literal_h6) - 1);
1665                     }
1666                 }
1667                 break;
1668
1669             case H5_END:
1670                 if (IN(NO_WIKI_START) || IN(PRE) || IN(PRE_START))
1671                     rb_str_cat(parser->output, literal_h5, sizeof(literal_h5) - 1);
1672                 else
1673                 {
1674                     _Wikitext_rollback_failed_external_link(parser); // if any
1675                     if (!IN(H5_START))
1676                     {
1677                         // literal output only if not in h5 scope (we stay silent in that case)
1678                         _Wikitext_start_para_if_necessary(parser);
1679                         rb_str_cat(parser->output, literal_h5, sizeof(literal_h5) - 1);
1680                     }
1681                 }
1682                 break;
1683
1684             case H4_END:
1685                 if (IN(NO_WIKI_START) || IN(PRE) || IN(PRE_START))
1686                     rb_str_cat(parser->output, literal_h4, sizeof(literal_h4) - 1);
1687                 else
1688                 {
1689                     _Wikitext_rollback_failed_external_link(parser); // if any
1690                     if (!IN(H4_START))
1691                     {
1692                         // literal output only if not in h4 scope (we stay silent in that case)
1693                         _Wikitext_start_para_if_necessary(parser);
1694                         rb_str_cat(parser->output, literal_h4, sizeof(literal_h4) - 1);
1695                     }
1696                 }
1697                 break;
1698
1699             case H3_END:
1700                 if (IN(NO_WIKI_START) || IN(PRE) || IN(PRE_START))
1701                     rb_str_cat(parser->output, literal_h3, sizeof(literal_h3) - 1);
1702                 else
1703                 {
1704                     _Wikitext_rollback_failed_external_link(parser); // if any
1705                     if (!IN(H3_START))
1706                     {
1707                         // literal output only if not in h3 scope (we stay silent in that case)
1708                         _Wikitext_start_para_if_necessary(parser);
1709                         rb_str_cat(parser->output, literal_h3, sizeof(literal_h3) - 1);
1710                     }
1711                 }
1712                 break;
1713
1714             case H2_END:
1715                 if (IN(NO_WIKI_START) || IN(PRE) || IN(PRE_START))
1716                     rb_str_cat(parser->output, literal_h2, sizeof(literal_h2) - 1);
1717                 else
1718                 {
1719                     _Wikitext_rollback_failed_external_link(parser); // if any
1720                     if (!IN(H2_START))
1721                     {
1722                         // literal output only if not in h2 scope (we stay silent in that case)
1723                         _Wikitext_start_para_if_necessary(parser);
1724                         rb_str_cat(parser->output, literal_h2, sizeof(literal_h2) - 1);
1725                     }
1726                 }
1727                 break;
1728
1729             case H1_END:
1730                 if (IN(NO_WIKI_START) || IN(PRE) || IN(PRE_START))
1731                     rb_str_cat(parser->output, literal_h1, sizeof(literal_h1) - 1);
1732                 else
1733                 {
1734                     _Wikitext_rollback_failed_external_link(parser); // if any
1735                     if (!IN(H1_START))
1736                     {
1737                         // literal output only if not in h1 scope (we stay silent in that case)
1738                         _Wikitext_start_para_if_necessary(parser);
1739                         rb_str_cat(parser->output, literal_h1, sizeof(literal_h1) - 1);
1740                     }
1741                 }
1742                 break;
1743
1744             case MAIL:
1745                 if (IN(NO_WIKI_START) || IN(PRE) || IN(PRE_START))
1746                     rb_str_cat(parser->output, token->start, TOKEN_LEN(token));
1747                 else
1748                 {
1749                     // in plain scope, will turn into autolink (with appropriate, user-configurable CSS)
1750                     _Wikitext_pop_excess_elements(parser);
1751                     _Wikitext_start_para_if_necessary(parser);
1752                     i = TOKEN_TEXT(token);
1753                     if (parser->autolink == Qtrue)
1754                         i = _Wikitext_hyperlink(rb_str_new2("mailto:"), i, i, mailto_class);
1755                     rb_str_append(parser->output, i);
1756                 }
1757                 break;
1758
1759             case URI:
1760                 if (IN(NO_WIKI_START))
1761                     // user can temporarily suppress autolinking by using <nowiki></nowiki>
1762                     // note that unlike MediaWiki, we do allow autolinking inside PRE blocks
1763                     rb_str_cat(parser->output, token->start, TOKEN_LEN(token));
1764                 else if (IN(LINK_START))
1765                 {
1766                     // if the URI were allowed it would have been handled already in LINK_START
1767                     _Wikitext_rollback_failed_link(parser);
1768                     i = TOKEN_TEXT(token);
1769                     if (parser->autolink == Qtrue)
1770                         i = _Wikitext_hyperlink(Qnil, i, i, parser->external_link_class); // link target, link text
1771                     rb_str_append(parser->output, i);
1772                 }
1773                 else if (IN(EXT_LINK_START))
1774                 {
1775                     if (NIL_P(parser->link_target))
1776                     {
1777                         // this must be our link target: look ahead to make sure we see the space we're expecting to see
1778                         i = TOKEN_TEXT(token);
1779                         NEXT_TOKEN();
1780                         if (token->type == SPACE)
1781                         {
1782                             ary_push(parser->scope, SPACE);
1783                             parser->link_target = i;
1784                             parser->link_text   = rb_str_new2("");
1785                             parser->capture     = parser->link_text;
1786                             token               = NULL; // silently consume space
1787                         }
1788                         else
1789                         {
1790                             // didn't see the space! this must be an error
1791                             _Wikitext_pop_from_stack(parser, Qnil);
1792                             _Wikitext_pop_excess_elements(parser);
1793                             _Wikitext_start_para_if_necessary(parser);
1794                             rb_str_cat(parser->output, ext_link_start, sizeof(ext_link_start) - 1);
1795                             if (parser->autolink == Qtrue)
1796                                 i = _Wikitext_hyperlink(Qnil, i, i, parser->external_link_class); // link target, link text
1797                             rb_str_append(parser->output, i);
1798                         }
1799                     }
1800                     else
1801                     {
1802                         if (NIL_P(parser->link_text))
1803                             // this must be the first part of our link text
1804                             parser->link_text = TOKEN_TEXT(token);
1805                         else
1806                             // add to existing link text
1807                             rb_str_cat(parser->link_text, token->start, TOKEN_LEN(token));
1808                     }
1809                 }
1810                 else
1811                 {
1812                     // in plain scope, will turn into autolink (with appropriate, user-configurable CSS)
1813                     _Wikitext_pop_excess_elements(parser);
1814                     _Wikitext_start_para_if_necessary(parser);
1815                     i = TOKEN_TEXT(token);
1816                     if (parser->autolink == Qtrue)
1817                         i = _Wikitext_hyperlink(Qnil, i, i, parser->external_link_class); // link target, link text
1818                     rb_str_append(parser->output, i);
1819                 }
1820                 break;
1821
1822             // internal links (links to other wiki articles) look like this:
1823             //      [[another article]] (would point at, for example, "/wiki/another_article")
1824             //      [[the other article|the link text we'll use for it]]
1825             //      [[the other article | the link text we'll use for it]]
1826             // note that the forward slash is a reserved character which changes the meaning of an internal link;
1827             // this is a link that is external to the wiki but internal to the site as a whole:
1828             //      [[bug/12]] (a relative link to "/bug/12")
1829             // MediaWiki has strict requirements about what it will accept as a link target:
1830             //      all wikitext markup is disallowed:
1831             //          example [[foo ''bar'' baz]]
1832             //          renders [[foo <em>bar</em> baz]]        (ie. not a link)
1833             //          example [[foo <em>bar</em> baz]]
1834             //          renders [[foo <em>bar</em> baz]]        (ie. not a link)
1835             //          example [[foo <nowiki>''</nowiki> baz]]
1836             //          renders [[foo '' baz]]                  (ie. not a link)
1837             //          example [[foo <bar> baz]]
1838             //          renders [[foo &lt;bar&gt; baz]]         (ie. not a link)
1839             //      HTML entities and non-ASCII, however, make it through:
1840             //          example [[foo &euro;]]
1841             //          renders <a href="/wiki/Foo_%E2%82%AC">foo &euro;</a>
1842             //          example [[foo €]]
1843             //          renders <a href="/wiki/Foo_%E2%82%AC">foo €</a>
1844             // we'll impose similar restrictions here for the link target; allowed tokens will be:
1845             //      SPACE, PRINTABLE, DEFAULT, QUOT and AMP
1846             // everything else will be rejected
1847             case LINK_START:
1848                 i = NIL_P(parser->capture) ? parser->output : parser->capture;
1849                 if (IN(NO_WIKI_START) || IN(PRE) || IN(PRE_START))
1850                     rb_str_cat(i, link_start, sizeof(link_start) - 1);
1851                 else if (IN(EXT_LINK_START))
1852                     // already in external link scope! (and in fact, must be capturing link_text right now)
1853                     rb_str_cat(i, link_start, sizeof(link_start) - 1);
1854                 else if (IN(LINK_START))
1855                 {
1856                     // already in internal link scope! this is a syntax error
1857                     _Wikitext_rollback_failed_link(parser);
1858                     rb_str_cat(parser->output, link_start, sizeof(link_start) - 1);
1859                 }
1860                 else if (IN(SEPARATOR))
1861                 {
1862                     // scanning internal link text
1863                 }
1864                 else // not in internal link scope yet
1865                 {
1866                     // will either emit a link, or the rollback of a failed link, so start the para now
1867                     _Wikitext_pop_excess_elements(parser);
1868                     _Wikitext_start_para_if_necessary(parser);
1869                     ary_push(parser->scope, LINK_START);
1870
1871                     // look ahead and try to gobble up link target
1872                     while (NEXT_TOKEN(), (type = token->type))
1873                     {
1874                         if (type == SPACE       ||
1875                             type == PRINTABLE   ||
1876                             type == DEFAULT     ||
1877                             type == QUOT        ||
1878                             type == QUOT_ENTITY ||
1879                             type == AMP         ||
1880                             type == AMP_ENTITY  ||
1881                             type == IMG_START   ||
1882                             type == IMG_END     ||
1883                             type == LEFT_CURLY  ||
1884                             type == RIGHT_CURLY)
1885                         {
1886                             // accumulate these tokens into link_target
1887                             if (NIL_P(parser->link_target))
1888                             {
1889                                 parser->link_target = rb_str_new2("");
1890                                 parser->capture     = parser->link_target;
1891                             }
1892                             if (type == QUOT_ENTITY)
1893                                 // don't insert the entity, insert the literal quote
1894                                 rb_str_cat(parser->link_target, quote, sizeof(quote) - 1);
1895                             else if (type == AMP_ENTITY)
1896                                 // don't insert the entity, insert the literal ampersand
1897                                 rb_str_cat(parser->link_target, ampersand, sizeof(ampersand) - 1);
1898                             else
1899                                 rb_str_cat(parser->link_target, token->start, TOKEN_LEN(token));
1900                         }
1901                         else if (type == LINK_END)
1902                             break; // jump back to top of loop (will handle this in LINK_END case below)
1903                         else if (type == SEPARATOR)
1904                         {
1905                             ary_push(parser->scope, SEPARATOR);
1906                             parser->link_text   = rb_str_new2("");
1907                             parser->capture     = parser->link_text;
1908                             token               = NULL;
1909                             break;
1910                         }
1911                         else // unexpected token (syntax error)
1912                         {
1913                             _Wikitext_rollback_failed_link(parser);
1914                             break; // jump back to top of loop to handle unexpected token
1915                         }
1916                     }
1917
1918                     // jump to top of the loop to process token we scanned during lookahead (if any)
1919                     continue;
1920                 }
1921                 break;
1922
1923             case LINK_END:
1924                 i = NIL_P(parser->capture) ? parser->output : parser->capture;
1925                 if (IN(NO_WIKI_START) || IN(PRE) || IN(PRE_START))
1926                     rb_str_cat(i, link_end, sizeof(link_end) - 1);
1927                 else if (IN(EXT_LINK_START))
1928                     // already in external link scope! (and in fact, must be capturing link_text right now)
1929                     rb_str_cat(i, link_end, sizeof(link_end) - 1);
1930                 else if (IN(LINK_START))
1931                 {
1932                     // in internal link scope!
1933                     if (NIL_P(parser->link_text) || RSTRING_LEN(parser->link_text) == 0)
1934                         // use link target as link text
1935                         parser->link_text = _Wikitext_parser_sanitize_link_target(parser, Qfalse);
1936                     else
1937                         parser->link_text = _Wikitext_parser_trim_link_target(parser->link_text);
1938                     _Wikitext_parser_encode_link_target(parser);
1939                     _Wikitext_pop_from_stack_up_to(parser, i, LINK_START, Qtrue);
1940                     parser->capture     = Qnil;
1941                     if (parser->special_link)
1942                         i = _Wikitext_hyperlink(rb_str_new2("/"), parser->link_target, parser->link_text, Qnil);
1943                     else
1944                         i = _Wikitext_hyperlink(prefix, parser->link_target, parser->link_text, Qnil);
1945                     rb_str_append(parser->output, i);
1946                     parser->link_target = Qnil;
1947                     parser->link_text   = Qnil;
1948                 }
1949                 else // wasn't in internal link scope
1950                 {
1951                     _Wikitext_pop_excess_elements(parser);
1952                     _Wikitext_start_para_if_necessary(parser);
1953                     rb_str_cat(i, link_end, sizeof(link_end) - 1);
1954                 }
1955                 break;
1956
1957             // external links look like this:
1958             //      [http://google.com/ the link text]
1959             // strings in square brackets which don't match this syntax get passed through literally; eg:
1960             //      he was very angery [sic] about the turn of events
1961             case EXT_LINK_START:
1962                 i = NIL_P(parser->capture) ? parser->output : parser->capture;
1963                 if (IN(NO_WIKI_START) || IN(PRE) || IN(PRE_START))
1964                     rb_str_cat(i, ext_link_start, sizeof(ext_link_start) - 1);
1965                 else if (IN(EXT_LINK_START))
1966                     // already in external link scope! (and in fact, must be capturing link_text right now)
1967                     rb_str_cat(i, ext_link_start, sizeof(ext_link_start) - 1);
1968                 else if (IN(LINK_START))
1969                 {
1970                     // already in internal link scope!
1971                     i = rb_str_new(ext_link_start, sizeof(ext_link_start) - 1);
1972                     if (NIL_P(parser->link_target))
1973                         // this must be the first character of our link target
1974                         parser->link_target = i;
1975                     else if (IN(SPACE))
1976                     {
1977                         // link target has already been scanned
1978                         if (NIL_P(parser->link_text))
1979                             // this must be the first character of our link text
1980                             parser->link_text = i;
1981                         else
1982                             // add to existing link text
1983                             rb_str_append(parser->link_text, i);
1984                     }
1985                     else
1986                         // add to existing link target
1987                         rb_str_append(parser->link_target, i);
1988                 }
1989                 else // not in external link scope yet
1990                 {
1991                     // will either emit a link, or the rollback of a failed link, so start the para now
1992                     _Wikitext_pop_excess_elements(parser);
1993                     _Wikitext_start_para_if_necessary(parser);
1994
1995                     // look ahead: expect a URI
1996                     NEXT_TOKEN();
1997                     if (token->type == URI)
1998                         ary_push(parser->scope, EXT_LINK_START);    // so far so good, jump back to the top of the loop
1999                     else
2000                         // only get here if there was a syntax error (missing URI)
2001                         rb_str_cat(parser->output, ext_link_start, sizeof(ext_link_start) - 1);
2002                     continue; // jump back to top of loop to handle token (either URI or whatever it is)
2003                 }
2004                 break;
2005
2006             case EXT_LINK_END:
2007                 i = NIL_P(parser->capture) ? parser->output : parser->capture;
2008                 if (IN(NO_WIKI_START) || IN(PRE) || IN(PRE_START))
2009                     rb_str_cat(i, ext_link_end, sizeof(ext_link_end) - 1);
2010                 else if (IN(EXT_LINK_START))
2011                 {
2012                     if (NIL_P(parser->link_text))
2013                         // syntax error: external link with no link text
2014                         _Wikitext_rollback_failed_external_link(parser);
2015                     else
2016                     {
2017                         // success!
2018                         _Wikitext_pop_from_stack_up_to(parser, i, EXT_LINK_START, Qtrue);
2019                         parser->capture = Qnil;
2020                         i = _Wikitext_hyperlink(Qnil, parser->link_target, parser->link_text, parser->external_link_class);
2021                         rb_str_append(parser->output, i);
2022                     }
2023                     parser->link_target = Qnil;
2024                     parser->link_text   = Qnil;
2025                 }
2026                 else
2027                 {
2028                     _Wikitext_pop_excess_elements(parser);
2029                     _Wikitext_start_para_if_necessary(parser);
2030                     rb_str_cat(parser->output, ext_link_end, sizeof(ext_link_end) - 1);
2031                 }
2032                 break;
2033
2034             case SEPARATOR:
2035                 i = NIL_P(parser->capture) ? parser->output : parser->capture;
2036                 _Wikitext_pop_excess_elements(parser);
2037                 _Wikitext_start_para_if_necessary(parser);
2038                 rb_str_cat(i, separator, sizeof(separator) - 1);
2039                 break;
2040
2041             case SPACE:
2042                 i = NIL_P(parser->capture) ? parser->output : parser->capture;
2043                 if (IN(NO_WIKI_START) || IN(PRE) || IN(PRE_START))
2044                     rb_str_cat(i, token->start, TOKEN_LEN(token));
2045                 else
2046                 {
2047                     // peek ahead to see next token
2048                     char    *token_ptr  = token->start;
2049                     int     token_len   = TOKEN_LEN(token);
2050                     NEXT_TOKEN();
2051                     type = token->type;
2052                     if (((type == H6_END) && IN(H6_START)) ||
2053                         ((type == H5_END) && IN(H5_START)) ||
2054                         ((type == H4_END) && IN(H4_START)) ||
2055                         ((type == H3_END) && IN(H3_START)) ||
2056                         ((type == H2_END) && IN(H2_START)) ||
2057                         ((type == H1_END) && IN(H1_START)))
2058                     {
2059                         // will suppress emission of space (discard) if next token is a H6_END, H5_END etc and we are in the corresponding scope
2060                     }
2061                     else
2062                     {
2063                         // emit the space
2064                         _Wikitext_pop_excess_elements(parser);
2065                         _Wikitext_start_para_if_necessary(parser);
2066                         rb_str_cat(i, token_ptr, token_len);
2067                     }
2068
2069                     // jump to top of the loop to process token we scanned during lookahead
2070                     continue;
2071                 }
2072                 break;
2073
2074             case QUOT_ENTITY:
2075             case AMP_ENTITY:
2076             case NAMED_ENTITY:
2077             case DECIMAL_ENTITY:
2078                 // pass these through unaltered as they are case sensitive
2079                 i = NIL_P(parser->capture) ? parser->output : parser->capture;
2080                 _Wikitext_pop_excess_elements(parser);
2081                 _Wikitext_start_para_if_necessary(parser);
2082                 rb_str_cat(i, token->start, TOKEN_LEN(token));
2083                 break;
2084
2085             case HEX_ENTITY:
2086                 // normalize hex entities (downcase them)
2087                 i = NIL_P(parser->capture) ? parser->output : parser->capture;
2088                 _Wikitext_pop_excess_elements(parser);
2089                 _Wikitext_start_para_if_necessary(parser);
2090                 rb_str_append(i, _Wikitext_downcase(TOKEN_TEXT(token)));
2091                 break;
2092
2093             case QUOT:
2094                 i = NIL_P(parser->capture) ? parser->output : parser->capture;
2095                 _Wikitext_pop_excess_elements(parser);
2096                 _Wikitext_start_para_if_necessary(parser);
2097                 rb_str_cat(i, quot_entity, sizeof(quot_entity) - 1);
2098                 break;
2099
2100             case AMP:
2101                 i = NIL_P(parser->capture) ? parser->output : parser->capture;
2102                 _Wikitext_pop_excess_elements(parser);
2103                 _Wikitext_start_para_if_necessary(parser);
2104                 rb_str_cat(i, amp_entity, sizeof(amp_entity) - 1);
2105                 break;
2106
2107             case LESS:
2108                 i = NIL_P(parser->capture) ? parser->output : parser->capture;
2109                 _Wikitext_pop_excess_elements(parser);
2110                 _Wikitext_start_para_if_necessary(parser);
2111                 rb_str_cat(i, lt_entity, sizeof(lt_entity) - 1);
2112                 break;
2113
2114             case GREATER:
2115                 i = NIL_P(parser->capture) ? parser->output : parser->capture;
2116                 _Wikitext_pop_excess_elements(parser);
2117                 _Wikitext_start_para_if_necessary(parser);
2118                 rb_str_cat(i, gt_entity, sizeof(gt_entity) - 1);
2119                 break;
2120
2121             case IMG_START:
2122                 if (IN(NO_WIKI_START) || IN(PRE) || IN(PRE_START))
2123                     rb_str_cat(parser->output, token->start, TOKEN_LEN(token));
2124                 else if (!NIL_P(parser->capture))
2125                     rb_str_cat(parser->capture, token->start, TOKEN_LEN(token));
2126                 else
2127                 {
2128                     // not currently capturing: will be emitting something on success or failure, so get ready
2129                     _Wikitext_pop_excess_elements(parser);
2130                     _Wikitext_start_para_if_necessary(parser);
2131
2132                     // peek ahead to see next token
2133                     NEXT_TOKEN();
2134                     if (token->type != PRINTABLE)
2135                         // failure
2136                         rb_str_cat(parser->output, literal_img_start, sizeof(literal_img_start) - 1);
2137                     else
2138                     {
2139                         // remember the PRINTABLE
2140                         char    *token_ptr  = token->start;
2141                         int     token_len   = TOKEN_LEN(token);
2142
2143                         // peek ahead once more
2144                         NEXT_TOKEN();
2145                         if (token->type == IMG_END)
2146                         {
2147                             // success
2148                             _Wikitext_append_img(parser, token_ptr, token_len);
2149                             token = NULL;
2150                         }
2151                         else
2152                         {
2153                             // failure
2154                             rb_str_cat(parser->output, literal_img_start, sizeof(literal_img_start) - 1);
2155                             rb_str_cat(parser->output, token_ptr, token_len);
2156                         }
2157                     }
2158
2159                     // jump to top of the loop to process token we scanned during lookahead
2160                     continue;
2161                 }
2162                 break;
2163
2164             case CRLF:
2165                 parser->pending_crlf = Qfalse;
2166                 _Wikitext_rollback_failed_link(parser);             // if any
2167                 _Wikitext_rollback_failed_external_link(parser);    // if any
2168                 if (IN(NO_WIKI_START) || IN(PRE_START))
2169                 {
2170                     ary_clear(parser->line_buffer);
2171                     rb_str_cat(parser->output, parser->line_ending->ptr, parser->line_ending->len);
2172                     break;
2173                 }
2174                 else if (IN(PRE))
2175                 {
2176                     // beware when nothing or BLOCKQUOTE on line buffer (not line stack!) prior to CRLF, that must be end of PRE block
2177                     if (NO_ITEM(ary_entry(parser->line_buffer, -2)) || ary_entry(parser->line_buffer, -2) == BLOCKQUOTE)
2178                         // don't emit in this case
2179                         _Wikitext_pop_from_stack_up_to(parser, parser->output, PRE, Qtrue);
2180                     else
2181                     {
2182                         // peek ahead to see if this is definitely the end of the PRE block
2183                         NEXT_TOKEN();
2184                         type = token->type;
2185                         if (type != BLOCKQUOTE && type != PRE)
2186                         {
2187                             // this is definitely the end of the block, so don't emit
2188                             _Wikitext_pop_from_stack_up_to(parser, parser->output, PRE, Qtrue);
2189                         }
2190                         else
2191                             // potentially will emit
2192                             parser->pending_crlf = Qtrue;
2193
2194                         // delete the entire contents of the line scope stack and buffer
2195                         ary_clear(parser->line);
2196                         ary_clear(parser->line_buffer);
2197                         continue; // jump back to top of loop to handle token grabbed via lookahead
2198                     }
2199                 }
2200                 else
2201                 {
2202                     parser->pending_crlf = Qtrue;
2203
2204                     // count number of BLOCKQUOTE tokens in line buffer (can be zero) and pop back to that level
2205                     // as a side effect, this handles any open span-level elements and unclosed blocks
2206                     // (with special handling for P blocks and LI elements)
2207                     i = ary_count(parser->line, BLOCKQUOTE) + ary_count(parser->scope, BLOCKQUOTE_START);
2208                     for (j = parser->scope->count; j > i; j--)
2209                     {
2210                         if (parser->scope->count > 0 && ary_entry(parser->scope, -1) == LI)
2211                         {
2212                             parser->pending_crlf = Qfalse;
2213                             break;
2214                         }
2215
2216                         // special handling on last iteration through the loop if the top item on the scope is a P block
2217                         if ((j - i == 1) && ary_entry(parser->scope, -1) == P)
2218                         {
2219                             // if nothing or BLOCKQUOTE on line buffer (not line stack!) prior to CRLF, this must be a paragraph break
2220                             // (note that we have to make sure we're not inside a BLOCKQUOTE_START block
2221                             // because in those blocks BLOCKQUOTE tokens have no special meaning)
2222                             if (NO_ITEM(ary_entry(parser->line_buffer, -2)) ||
2223                                 (ary_entry(parser->line_buffer, -2) == BLOCKQUOTE && !IN(BLOCKQUOTE_START)))
2224                                 // paragraph break
2225                                 parser->pending_crlf = Qfalse;
2226                             else
2227                                 // not a paragraph break!
2228                                 continue;
2229                         }
2230                         _Wikitext_pop_from_stack(parser, Qnil);
2231                     }
2232                 }
2233
2234                 // delete the entire contents of the line scope stack and buffer
2235                 ary_clear(parser->line);
2236                 ary_clear(parser->line_buffer);
2237                 break;
2238
2239             case PRINTABLE:
2240             case IMG_END:
2241             case LEFT_CURLY:
2242             case RIGHT_CURLY:
2243                 i = NIL_P(parser->capture) ? parser->output : parser->capture;
2244                 _Wikitext_pop_excess_elements(parser);
2245                 _Wikitext_start_para_if_necessary(parser);
2246                 rb_str_cat(i, token->start, TOKEN_LEN(token));
2247                 break;
2248
2249             case DEFAULT:
2250                 i = NIL_P(parser->capture) ? parser->output : parser->capture;
2251                 _Wikitext_pop_excess_elements(parser);
2252                 _Wikitext_start_para_if_necessary(parser);
2253                 rb_str_append(i, _Wikitext_utf32_char_to_entity(token->code_point));    // convert to entity
2254                 break;
2255
2256             case END_OF_FILE:
2257                 // close any open scopes on hitting EOF
2258                 _Wikitext_rollback_failed_external_link(parser);    // if any
2259                 _Wikitext_rollback_failed_link(parser);             // if any
2260                 for (i = 0, j = parser->scope->count; i < j; i++)
2261                     _Wikitext_pop_from_stack(parser, Qnil);
2262                 goto return_output; // break not enough here (want to break out of outer while loop, not inner switch statement)
2263
2264             default:
2265                 break;
2266         }
2267
2268         // reset current token; forcing lexer to return another token at the top of the loop
2269         token = NULL;
2270     } while (1);
2271 return_output:
2272     // BUG: these will leak if we exit this function by raising an exception; need to investigate using Data_Wrap_Struct
2273     str_free(parser->line_ending);
2274     if (parser->tabulation)
2275         str_free(parser->tabulation);
2276     return parser->output;
2277 }