// Row 148 (#1642, ruling sage-0507): the Markdown preview makes elements and text nodes only.
// The module is loaded into a bare context with a tiny document, so what it builds is a tree
// the tests can read: no markup is ever parsed on the way, which is the property under test.
import test from 'node:test';
import assert from 'node:assert/strict';
import { createHash } from 'node:crypto';
import { readFileSync } from 'node:fs';
import { createContext, runInContext, runInNewContext } from 'node:vm';
import { fileURLToPath } from 'node:url';
const FILE = fileURLToPath(new URL('../src/public/markdown-preview.js', import.meta.url));
const source = readFileSync(FILE, 'utf8');

class Node {
  constructor(tag) { this.tag = tag; this.children = []; this.attrs = {}; this.className = ''; this.text = null; }
  set textContent(v) { this.children = [new Text(String(v))]; }
  get textContent() { return this.children.map(c => c.textContent).join(''); }
  setAttribute(k, v) { this.attrs[k] = String(v); }
  appendChild(c) { this.children.push(c); return c; }
  get lastChild() { return this.children.at(-1); }
}
class Text { constructor(t) { this.tag = '#text'; this.data = t; } get textContent() { return this.data; } }
const doc = {
  createElement: tag => new Node(tag),
  createTextNode: t => new Text(String(t)),
  createDocumentFragment: () => new Node('#fragment'),
};
const { MosaicMarkdown } = (() => { const window = {}; runInNewContext(source, { window }); return window; })();
// `meter` receives {work, budget}: the render's look-ahead account, which the tests assert on instead of the clock.
const tree = (md, meter) => MosaicMarkdown.render(md, doc, meter);
// A compact view: <tag attr=..>children</tag>, text as itself.
const show = n => n.tag === '#text' ? n.data : `<${n.tag}${Object.entries(n.attrs).map(([k, v]) => ` ${k}=${v}`).join('')}>${n.children.map(show).join('')}</${n.tag}>`;
const html = md => tree(md).children.map(show).join('');
const find = (n, tag, out = []) => { if (n.tag === tag) out.push(n); for (const c of n.children ?? []) find(c, tag, out); return out; };

test('the preview source names none of the four string-to-markup sinks', () => {
  for (const sink of ['innerHTML', 'outerHTML', 'insertAdjacentHTML', 'document.write'])
    assert.equal(source.includes(sink), false, sink);
  assert.equal(/\beval\b|new Function|DOMParser|createContextualFragment|srcdoc/.test(source), false, 'no other way to parse markup or run text');
  assert.ok(source.includes('createElement') && source.includes('textContent'));
});

test('headings, paragraphs, emphasis and inline code render', () => {
  assert.equal(html('# One\n\n###### Six'), '<h1>One</h1><h6>Six</h6>');
  assert.equal(html('Setext\n===\n\nTwo\n---'), '<h1>Setext</h1><h2>Two</h2>');
  assert.equal(html('a **b** and *c* and _d_ and `e`\nnext'), '<p>a <strong>b</strong> and <em>c</em> and <em>d</em> and <code>e</code>\nnext</p>');
  assert.equal(html('snake_case_word and 2*3*4'), '<p>snake_case_word and 2<em>3</em>4</p>');
  assert.equal(html('``a ` b``'), '<p><code>a ` b</code></p>');
});

test('lists, block quotes and code blocks render', () => {
  assert.equal(html('- a\n- b **x**\n\n1. one\n2. two'), '<ul><li>a</li><li>b <strong>x</strong></li></ul><ol><li>one</li><li>two</li></ol>');
  assert.equal(html('3. three\n4. four'), '<ol start=3><li>three</li><li>four</li></ol>');
  assert.equal(html('- a\n  - nested\n- b'), '<ul><li>a<ul><li>nested</li></ul></li><li>b</li></ul>');
  assert.equal(html('> quoted\n> # head\n\nafter'), '<blockquote><p>quoted</p><h1>head</h1></blockquote><p>after</p>');
  assert.equal(html('```js\nconst a = "<b>";\n```\n'), '<pre><code>const a = "<b>";</code></pre>');
  assert.equal(html('~~~\nopen'), '<pre><code>open</code></pre>');
});

test('a link is made for http, https and relative targets, with rel and the target shown', () => {
  const links = find(tree('[a](https://example.com/x?y=1) [b](http://example.com) [c](docs/a.md) [d](#top) [e](../up.md) [f](/root)'), 'a');
  assert.deepEqual(links.map(a => a.attrs.href), ['https://example.com/x?y=1', 'http://example.com', 'docs/a.md', '#top', '../up.md', '/root']);
  for (const a of links) { assert.equal(a.attrs.rel, 'noopener noreferrer'); assert.equal(a.attrs.target, '_blank'); }
  assert.equal(html('[t](https://example.com)'), '<p><a href=https://example.com rel=noopener noreferrer target=_blank>t</a> <span>(https://example.com)</span></p>');
  assert.equal(find(tree('[t](https://example.com)'), 'span')[0].className, 'md-target');
  assert.equal(find(tree('[a *b* `c`](x.md)'), 'a')[0].children.map(show).join(''), 'a <em>b</em> <code>c</code>');
});

test('a link with any other scheme, or an evasion of the scheme, stays source text', () => {
  for (const target of ['javascript:alert(1)', 'JaVaScRiPt:alert(1)', 'data:text/html,<script>1</script>', 'vbscript:x', 'file:///etc/passwd', 'blob:x', 'ftp://x/y', 'mailto:a@b.c',
      'java\tscript:alert(1)', 'java\nscript:alert(1)', ' javascript:alert(1)', 'javascript&colon;alert(1)'.replace('&colon;', ':'), '\u0001javascript:x', '//evil.example/x', '\\\\evil\\x',
      '/\\evil.example', 'http:///x', 'https:', 'a' + String.fromCharCode(0x202e) + 'b', 'a' + String.fromCharCode(0x200b) + 'b']) {
    const md = `[click](<${target}>)`, t = tree(md);
    assert.deepEqual(find(t, 'a'), [], JSON.stringify(target));
    assert.equal(t.textContent, md, `${JSON.stringify(target)} stays as written`);
  }
  // The same without the angle brackets, for the targets that need none.
  for (const target of ['javascript:alert(1)', 'data:text/html;base64,AAAA', 'JAVASCRIPT:x']) {
    const t = tree(`[click](${target})`);
    assert.deepEqual(find(t, 'a'), []); assert.equal(t.textContent, `[click](${target})`);
  }
  assert.equal(MosaicMarkdown.linkTarget('javascript:x'), null);
  assert.equal(MosaicMarkdown.linkTarget('https://a.example/b'), 'https://a.example/b');
  assert.equal(MosaicMarkdown.linkTarget('a.md'), 'a.md');
});

test('an image shows alt text and URL, is never an img element and never loads', () => {
  const t = tree('![alt text](https://tracker.example/p.png) and ![x](javascript:alert(1))');
  assert.deepEqual(find(t, 'img'), []);
  assert.equal(t.textContent, '[image: alt text] https://tracker.example/p.png and [image: x] javascript:alert(1)');
  assert.deepEqual(find(t, 'a'), [], 'an image destination is never a link either');
});

test('raw HTML, entities and unsupported blocks show as source text, never as elements', () => {
  const samples = ['<script>alert(1)</script>', '<img src=x onerror=alert(1)>', '<a href="javascript:alert(1)">x</a>', '<iframe src="https://x"></iframe>',
    '<b>bold</b> text', '<!-- hidden -->', '<div onclick="x()">', '| a | b |\n|---|---|\n| 1 | 2 |', '&lt;script&gt;', '***', '<style>*{}</style>'];
  const allowed = new Set(['#fragment', 'p', 'ul', 'ol', 'li', 'em', 'strong', 'code', 'pre', 'a', 'span', 'blockquote', '#text', 'h1', 'h2', 'h3', 'h4', 'h5', 'h6']);
  for (const md of samples) {
    const t = tree(md), walk = n => { assert.ok(allowed.has(n.tag), `${md} made <${n.tag}>`); n.children?.forEach(walk); };
    walk(t);
    if (md !== '***') assert.equal(t.textContent.replace(/\s+/g, ' ').trim(), md.replace(/\s+/g, ' ').trim(), `${md} shows as written`);
  }
  assert.deepEqual(find(tree('<img src=x onerror=alert(1)>'), 'img'), []);
});

test('markup inside code and inside link text stays text', () => {
  assert.equal(html('`<script>`'), '<p><code><script></code></p>');
  assert.equal(html('```\n<img src=x onerror=1>\n```'), '<pre><code><img src=x onerror=1></code></pre>');
  const a = find(tree('[<img src=x onerror=1>](x.md)'), 'a')[0];
  assert.equal(a.children.map(c => c.tag).join(), '#text');
  assert.equal(a.textContent, '<img src=x onerror=1>');
});

// A loose upper margin, not a derived maximum. The budget is checked when an opener starts, so one
// opener that starts just under it may still add its own scans: a link attempt can charge its label,
// the blanks around the destination, the destination and the title, each at most SPAN (2000)
// characters. 8 x SPAN is a round number above that sum. Only this upper side is loose: the lower
// bound below (`work >= budget`) is exact.
const OVERSHOOT = 8 * 2000;
test('hostile and pathological input stays within its look-ahead budget and under the nesting cap', () => {
  for (const md of ['['.repeat(5000), '*'.repeat(20000), '`'.repeat(20000), '> '.repeat(500) + 'x', '- '.repeat(500) + 'x', '[a](' + '('.repeat(5000), '*a '.repeat(5000), '_'.repeat(10000) + 'a', ('[x](' + 'y'.repeat(10) + ') ').repeat(3000), '![' .repeat(3000), '1. '.repeat(500) + 'x']) {
    const meter = {}, t = tree(md, meter);
    assert.ok(t.children.length >= 0);
    assert.ok(meter.work <= meter.budget + OVERSHOOT, `${md.slice(0, 12)}: ${meter.work} of ${meter.budget}`);
  }
  const depth = n => Math.max(0, ...(n.children ?? []).map(depth)) + 1;
  assert.ok(depth(tree('> '.repeat(500) + 'x')) < 60, 'block nesting is capped');
  assert.ok(depth(tree('*a '.repeat(200) + 'b' + ' a*'.repeat(200))) < 60, 'inline nesting is capped');
});

test('trailing blanks and closing hashes are cut by a walk from the end, not a regex that retries inside a blank run', () => {
  // A regex such as /[ \t]+$/ retries from every blank of a long run: 256 KiB of blanks took 30 s. The
  // suite does not read the clock, so it checks two other things: the walk gives the same text as the
  // regexes it replaced for every string of up to six characters over four, and neither regex form is in
  // the source (a pin, not a proof of speed).
  assert.equal(/\[ \\t\]\+(\)#\+)?\$/.test(source), false, 'no end-anchored blank-run regex');
  const alphabet = [' ', '\t', '#', 'a'];
  let level = [''];
  for (let n = 0; n <= 6; n++) {
    for (const s of level) {
      const heading = tree(`# ${s}`).children[0];
      assert.equal(heading.tag, 'h1', JSON.stringify(s));
      assert.equal(heading.textContent, s.replace(/^[ \t]+/, '').trim().replace(/(^|[ \t]+)#+$/, '').trim(), `heading ${JSON.stringify(s)}`);
      assert.equal(tree(`x${s}\nz`).textContent, `x${s}`.replace(/[ \t]+$/, '') + '\nz', `paragraph ${JSON.stringify(s)}`);
    }
    level = level.flatMap(s => alphabet.map(c => s + c));
  }
});

// Round 2 (B1): one scan for a closer must not look past SPAN. Timing cannot tell the bounded scan from
// the unbounded one (about 100 ms against 70 ms at 256 KiB), so this counts: the module is loaded into
// its own context whose indexOf records the most characters any one call could have to search.
// Unbounded, that is the rest of the text (about 256 KiB); bounded, it is at most SPAN + 1.
test('a link opener with no closer searches at most SPAN characters ahead', () => {
  const ctx = createContext({ window: {} });
  runInContext(`globalThis.widest = 0; const indexOf = String.prototype.indexOf;
    String.prototype.indexOf = function (needle, from) { widest = Math.max(widest, this.length - (from | 0)); return indexOf.call(this, needle, from); };`, ctx);
  runInContext(source, ctx);
  const render = md => ctx.window.MosaicMarkdown.render(md, doc);
  const SIZE = 256 * 1024;
  for (const unit of ['[a](<', '[a](x (', '[a](x "', '![a](<']) {
    ctx.widest = 0;
    render(unit.repeat(Math.ceil(SIZE / unit.length)));
    assert.ok(ctx.widest <= 2001, `${JSON.stringify(unit)}: one search covered ${ctx.widest} characters`);
  }
  // The control: a closer inside SPAN still makes the link, so the bound is not a refusal to look.
  assert.equal(find(tree('[a](<b.md>)'), 'a')[0].attrs.href, 'b.md');
  assert.equal(find(tree('[a](b.md "t")'), 'a')[0].attrs.href, 'b.md');
});

// Round 2 (sage-0568): SPAN bounds one scan, not a render. n openers with no closer cost n x SPAN, which
// was about 2 s per render at 256 KiB and 8 s at 1 MiB. The module now keeps one account per render and
// the tests read it through the optional third argument; nothing here looks at the clock. The limits
// below are the test's own numbers, so a budget that is raised or never enforced fails here too.
const SIZE = 256 * 1024;
const PER_CHAR = 32, FLOOR = 1 << 20;
// Code spans whose opener sizes cycle 1..70: the next run of the same size is 2625 characters away,
// past SPAN, so every opener searches its whole reach and finds no closer.
const SIZES = Array.from({ length: 70 }, (_, k) => '`'.repeat(k + 1) + 'a ').join('');
const HOSTILE = [
  ['_a ', 'underscore opener'], ['*a ', 'star opener'], ['**a ', 'double star opener'], ['[', 'bracket'], ['[a](', 'destination'],
  ['[a](((', 'nested destination'], ['[a](<', 'angle destination'], ['[a](x (', 'paren title'], ['![a](<', 'image angle destination'],
  [SIZES, 'code span sizes'],
];
const budgetOf = length => Math.max(FLOOR, PER_CHAR * length);
test('the look-ahead work of one render is a fixed multiple of the text, whatever the opener', () => {
  for (const [unit, name] of HOSTILE) {
    const md = unit.repeat(Math.ceil(SIZE / unit.length)).slice(0, SIZE), meter = {};
    tree(md, meter);
    assert.equal(meter.budget, budgetOf(md.length), `${name}: the budget is ${PER_CHAR} per character`);
    assert.ok(meter.work <= meter.budget + OVERSHOOT, `${name}: ${meter.work} of ${meter.budget} for ${md.length} characters`);
    assert.ok(meter.work >= meter.budget, `${name}: the input should have spent the budget (${meter.work} of ${meter.budget})`);
  }
  // A short text has the floor, not a share of its own length.
  const small = {};
  tree('x'.repeat(10), small);
  assert.equal(small.budget, FLOOR); assert.equal(small.work, 0);
});

test('past the budget an opener is source text, through the path all other text takes', () => {
  const head = '_a '.repeat(4000); // 12 KB, far more look-ahead than the 1 Mi floor allows
  const tail = '<script>alert(1)</script> "><img src=x onerror=alert(1)> [x](https://ok.example) *em* `code` ![i](https://ok.example/p.png)';
  // The same tail, alone, is made into a link, emphasis and code: only the budget keeps it as text.
  const alone = tree(tail);
  assert.equal(find(alone, 'a').length, 1); assert.equal(find(alone, 'em').length, 1); assert.equal(find(alone, 'code').length, 1);
  const meter = {}, t = tree(head + tail, meter);
  assert.ok(meter.work >= meter.budget, 'the head spent the budget before the tail');
  const allowed = new Set(['#fragment', 'p', '#text']);
  const walk = n => { assert.ok(allowed.has(n.tag), `made <${n.tag}>`); n.children?.forEach(walk); };
  walk(t);
  for (const tag of ['a', 'em', 'strong', 'code', 'img', 'script', 'span']) assert.deepEqual(find(t, tag), [], tag);
  assert.equal(t.textContent, head + tail, 'every character is still shown, as written');
});

// The budget must not touch a normal document. This one is built, not stored: headings with closing
// marks and trailing blanks, a setext heading, emphasis, links of each kind, images, nested lists, a
// block quote, a fenced block, raw HTML, stray openers and a few long paragraphs. Its rendering is
// pinned by the SHA-256 of the compact view, taken from the round 1 preview (no budget), so any
// difference in what a normal file shows fails here. To take the pin again, render sampleDocument()
// with a preview that has no budget and hash show() of the fragment's children.
function sampleDocument() {
  const T = '`', out = [];
  const words = n => Array.from({ length: n }, (_, i) => `word${(i * 7) % 31}`).join(' ');
  for (let n = 0, size = 0; size < 200 * 1024; n++) {
    const block = [
      `## Section ${n} ##   `, '',
      `A paragraph with **strong ${n}**, *emphasis*, _under_, ${T}code ${n}${T} and a [link](https://example.com/p/${n}?q=1 "title") plus [local](docs/page-${n}.md) and ![pic](https://example.com/i/${n}.png).`,
      `Second line with snake_case_name, 2*3*4, a stray [bracket and a lone ${T} tick, <b>html</b> and &amp; text.   `, '',
      `- item ${n} with **bold**`, '  - nested [x](<a b.md>) item', `- last ${T}code${T}`, '',
      '3. third', '4. fourth *four*', '',
      `> quoted ${n} *text*`, '> more', '',
      `${T}${T}${T}js`, `const a = "<b>"; // ${n}`, `${T}${T}${T}`, '',
      `Setext ${n}`, '===', '',
      '[bad](javascript:alert(1)) and [ok](#top) and [empty]()', '', '---', '',
      ...(n % 5 === 0 ? [`[A long paragraph ${n}: ${words(500)} *closed* and _also_ and ${T}code${T}, then an open * star and an open [ bracket.`, ''] : []),
    ];
    out.push(...block);
    size += block.reduce((sum, line) => sum + line.length + 1, 0);
  }
  return out.join('\n');
}
test('a normal 200 KiB document renders exactly as it did without a budget, and spends little of it', () => {
  const md = sampleDocument(), meter = {};
  assert.ok(md.length >= 200 * 1024 && md.length < 260 * 1024, `${md.length} characters`);
  const t = tree(md, meter);
  const sections = (md.match(/^## Section /gm) ?? []).length;
  assert.ok(sections > 50, `${sections} sections`);
  assert.ok(find(t, 'a').length >= 2 * sections && find(t, 'em').length >= 3 * sections && find(t, 'code').length >= 2 * sections && find(t, 'pre').length === sections, 'the sample exercises each element');
  assert.equal(meter.budget, budgetOf(md.length));
  assert.ok(meter.work * 2 < meter.budget, `a normal document used ${meter.work} of ${meter.budget}`);
  const digest = createHash('sha256').update(t.children.map(show).join('')).digest('hex');
  assert.equal(digest, '5df9165a60cdd36d511fee74b2a25854e58ef4eade30f1acfd55f3c518cee249', 'the rendering matches the round 1 preview');
});

// Round 3 (B1, sage-0604): `.` stops at U+2028 and U+2029, and the split on "\n" leaves both inside a
// line. Without the `s` flag on FENCE, ATX and ITEM, `$` then failed behind a long run and the engine
// retried the run from every offset: 2.2 s for a 64 KiB line, none of it visible to the meter. The clock
// cannot be used for that, so these are semantic: without the flag the line is not a heading, an item
// or a fence at all, it falls through to a paragraph, and these assertions fail on that.
const SEPARATORS = [['U+2028', String.fromCharCode(0x2028)], ['U+2029', String.fromCharCode(0x2029)]];
test('a line separator inside a heading, a list item or a fence line does not end the marker line', () => {
  for (const [name, sep] of SEPARATORS) {
    assert.equal(html(`# a${sep}b`), `<h1>a${sep}b</h1>`, `heading with ${name}`);
    assert.equal(html(`- a${sep}b`), `<ul><li>a${sep}b</li></ul>`, `bullet with ${name}`);
    assert.equal(html(`1. a${sep}b`), `<ol><li>a${sep}b</li></ol>`, `numbered item with ${name}`);
    for (const fence of ['```', '~~~'])
      assert.equal(html(`${fence}a${sep}b\ncode\n${fence}`), '<pre><code>code</code></pre>', `${fence} info string with ${name}`);
    // The shapes that were slow: the marker, a long run, then the separator. Short here; the run's length
    // does not matter to the result, only that the separator follows it.
    assert.equal(find(tree(`# ${' '.repeat(50)}${sep}b`), 'h1').length, 1, `heading, blank run, ${name}`);
    assert.equal(find(tree(`- ${' '.repeat(50)}${sep}b`), 'li').length, 1, `item, blank run, ${name}`);
    const run = '`'.repeat(50), pre = find(tree(`${run}${sep}x\ncode\n${run}`), 'pre');
    assert.equal(pre.length, 1, `fence, backtick run, ${name}`);
    assert.equal(pre[0].textContent, 'code', `fence body, ${name}`);
  }
});

// A thematic break is told from a list item by a walk, not the regex it replaced. That regex,
// /^ {0,3}([-*_])(?:[ \t]*\1){2,}[ \t]*$/, threw RangeError ("Maximum call stack size exceeded") on one
// line of about 2 MiB of marks (4 MiB when spaced). The preview has no rule element: a break line is
// source text in a paragraph, and its only effect is that it does not open a list.
const OLD_RULE = /^ {0,3}([-*_])(?:[ \t]*\1){2,}[ \t]*$/;
const listIn = md => { const t = tree(md); return find(t, 'ul').length + find(t, 'ol').length > 0; };
test('a thematic-break line is a paragraph, every other marker line opens a list', () => {
  for (const line of ['* * *', '- - -', '***', '---', '___', '_ _ _', ' * * *', '   - - -', '*  *  *', '* * * * *', '- - -   ', '*\t*\t*', '-\t-\t-', '- - - -'])
    assert.equal(listIn(line), false, JSON.stringify(line));
  for (const line of ['- -', '* *', '- - x', '* a * *', '- * -', '* - *', '- _ -', '-  -', '*\t*', '- - -x'])
    assert.equal(listIn(line), true, JSON.stringify(line));
  assert.equal(html('* * *'), '<p>* * *</p>');
  assert.equal(html('- a\n- - -\n- b'), '<ul><li>a\n- - -</li><li>b</li></ul>', 'a break line inside a list item is text, the next marker line is the next item');
});
test('every short line over space, tab, - * _ and a letter is a break exactly when the old regex said so', () => {
  const alphabet = [' ', '\t', '-', '*', '_', 'a'];
  let checked = 0, rules = 0;
  const walk = (prefix, left) => {
    if (prefix) {
      const seen = prefix.replace(/^[ \t]+/, w => w.replace(/\t/g, '    '));
      // Only a line that would otherwise open a list can show the difference.
      const wouldBeItem = /^ {0,3}[-*+]([ \t]|$)/.test(seen);
      if (wouldBeItem) { checked++; if (OLD_RULE.test(seen)) rules++; assert.equal(listIn(prefix), !OLD_RULE.test(seen), JSON.stringify(prefix)); }
    }
    if (left) for (const c of alphabet) walk(prefix + c, left - 1);
  };
  walk('', 6);
  assert.ok(checked > 5000 && rules > 100, `${checked} lines checked, ${rules} of them breaks`);
});
test('one line of marks does not throw, at 4 MiB, whatever the mark or the spacing', () => {
  const MIB4 = 4 * 1024 * 1024;
  for (const unit of ['-', '- ', '*', '* ', '_', '_ ', '-\t', ' -', '  *  '])
    for (const lead of ['', '   ']) {
      const line = lead + unit.repeat(Math.ceil(MIB4 / unit.length));
      let tree_;
      assert.doesNotThrow(() => { tree_ = tree(line); }, JSON.stringify(unit));
      assert.equal(find(tree_, 'ul').length, 0, `${JSON.stringify(unit)} is a break, not a list`);
      assert.equal(find(tree_, 'p').length, 1, JSON.stringify(unit));
    }
  // Not a break, same size: a list item whose text is the long run, and the same with one stray letter.
  assert.doesNotThrow(() => tree('- ' + 'a '.repeat(MIB4 / 2)));
  assert.doesNotThrow(() => tree('-'.repeat(MIB4) + 'a'));
});

test('CRLF and tabs are read like LF and spaces; empty input renders nothing', () => {
  assert.equal(html('# a\r\n\r\ntext\r\nmore'), '<h1>a</h1><p>text\nmore</p>');
  assert.equal(tree('').children.length, 0);
  assert.equal(tree('\n\n  \n').children.length, 0);
});