Refactor MFM

Co-authored-by: syuilo syuilotan@yahoo.co.jp

12 files changed, 199 insertions, 203 deletions

diff --git a/src/client/app/common/scripts/note-mixin.ts b/src/client/app/common/scripts/note-mixin.ts
index 36b8ca32c1..dea36cd2a5 100644
--- a/src/client/app/common/scripts/note-mixin.ts
+++ b/src/client/app/common/scripts/note-mixin.ts
@@ -80,8 +80,8 @@ export default (opts: Opts = {}) => ({
 				const ast = parse(this.appearNote.text);
 				// TODO: 再帰的にURL要素がないか調べる
 				return unique(ast
-					.filter(t => ((t.name == 'url' || t.name == 'link') && t.props.url && !t.props.silent))
-					.map(t => t.props.url));
+					.filter(t => ((t.node.type == 'url' || t.node.type == 'link') && t.node.props.url && !t.node.props.silent))
+					.map(t => t.node.props.url));
 			} else {
 				return null;
 			}
diff --git a/src/client/app/common/views/components/messaging-room.message.vue b/src/client/app/common/views/components/messaging-room.message.vue
index fa77fa7af1..872dc2d89e 100644
--- a/src/client/app/common/views/components/messaging-room.message.vue
+++ b/src/client/app/common/views/components/messaging-room.message.vue
@@ -52,8 +52,8 @@ export default Vue.extend({
 			if (this.message.text) {
 				const ast = parse(this.message.text);
 				return unique(ast
-					.filter(t => ((t.name == 'url' || t.name == 'link') && t.props.url && !t.silent))
-					.map(t => t.props.url));
+					.filter(t => ((t.node.type == 'url' || t.node.type == 'link') && t.node.props.url && !t.node.props.silent))
+					.map(t => t.node.props.url));
 			} else {
 				return null;
 			}
diff --git a/src/client/app/common/views/components/mfm.ts b/src/client/app/common/views/components/mfm.ts
index 399e8e884b..69ae7638a5 100644
--- a/src/client/app/common/views/components/mfm.ts
+++ b/src/client/app/common/views/components/mfm.ts
@@ -1,6 +1,6 @@
 import Vue, { VNode } from 'vue';
 import { length } from 'stringz';
-import { Node } from '../../../../../mfm/parser';
+import { MfmForest } from '../../../../../mfm/parser';
 import parse from '../../../../../mfm/parse';
 import MkUrl from './url.vue';
 import MkMention from './mention.vue';
@@ -9,16 +9,11 @@ import MkFormula from './formula.vue';
 import MkGoogle from './google.vue';
 import syntaxHighlight from '../../../../../mfm/syntax-highlight';
 import { host } from '../../../config';
+import { preorderF, countNodesF } from '../../../../../prelude/tree';
 
-function getTextCount(tokens: Node[]): number {
-	const rootCount = sum(tokens.filter(x => x.name === 'text').map(x => length(x.props.text)));
-	const childrenCount = sum(tokens.filter(x => x.children).map(x => getTextCount(x.children)));
-	return rootCount + childrenCount;
-}
-
-function getChildrenCount(tokens: Node[]): number {
-	const countTree = tokens.filter(x => x.children).map(x => getChildrenCount(x.children));
-	return countTree.length + sum(countTree);
+function sumTextsLength(ts: MfmForest): number {
+	const textNodes = preorderF(ts).filter(n => n.type === 'text');
+	return sum(textNodes.map(x => length(x.props.text)));
 }
 
 export default Vue.component('misskey-flavored-markdown', {
@@ -27,10 +22,6 @@ export default Vue.component('misskey-flavored-markdown', {
 			type: String,
 			required: true
 		},
-		ast: {
-			type: [],
-			required: false
-		},
 		shouldBreak: {
 			type: Boolean,
 			default: true
@@ -55,17 +46,15 @@ export default Vue.component('misskey-flavored-markdown', {
 	render(createElement) {
 		if (this.text == null || this.text == '') return;
 
-		const ast = this.ast == null ?
-			parse(this.text, this.plainText) : // Parse text to ast
-			this.ast as Node[];
+		const ast = parse(this.text, this.plainText);
 
 		let bigCount = 0;
 		let motionCount = 0;
 
-		const genEl = (ast: Node[]) => concat(ast.map((token): VNode[] => {
-			switch (token.name) {
+		const genEl = (ast: MfmForest) => concat(ast.map((token): VNode[] => {
+			switch (token.node.type) {
 				case 'text': {
-					const text = token.props.text.replace(/(\r\n|\n|\r)/g, '\n');
+					const text = token.node.props.text.replace(/(\r\n|\n|\r)/g, '\n');
 
 					if (this.shouldBreak) {
 						const x = text.split('\n')
@@ -95,7 +84,7 @@ export default Vue.component('misskey-flavored-markdown', {
 
 				case 'big': {
 					bigCount++;
-					const isLong = getTextCount(token.children) > 10 || getChildrenCount(token.children) > 5;
+					const isLong = sumTextsLength(token.children) > 10 || countNodesF(token.children) > 5;
 					const isMany = bigCount > 3;
 					return (createElement as any)('strong', {
 						attrs: {
@@ -122,7 +111,7 @@ export default Vue.component('misskey-flavored-markdown', {
 
 				case 'motion': {
 					motionCount++;
-					const isLong = getTextCount(token.children) > 10 || getChildrenCount(token.children) > 5;
+					const isLong = sumTextsLength(token.children) > 10 || countNodesF(token.children) > 5;
 					const isMany = motionCount > 3;
 					return (createElement as any)('span', {
 						attrs: {
@@ -139,7 +128,7 @@ export default Vue.component('misskey-flavored-markdown', {
 					return [createElement(MkUrl, {
 						key: Math.random(),
 						props: {
-							url: token.props.url,
+							url: token.node.props.url,
 							target: '_blank',
 							style: 'color:var(--mfmLink);'
 						}
@@ -150,9 +139,9 @@ export default Vue.component('misskey-flavored-markdown', {
 					return [createElement('a', {
 						attrs: {
 							class: 'link',
-							href: token.props.url,
+							href: token.node.props.url,
 							target: '_blank',
-							title: token.props.url,
+							title: token.node.props.url,
 							style: 'color:var(--mfmLink);'
 						}
 					}, genEl(token.children))];
@@ -162,8 +151,8 @@ export default Vue.component('misskey-flavored-markdown', {
 					return [createElement(MkMention, {
 						key: Math.random(),
 						props: {
-							host: (token.props.host == null && this.author && this.author.host != null ? this.author.host : token.props.host) || host,
-							username: token.props.username
+							host: (token.node.props.host == null && this.author && this.author.host != null ? this.author.host : token.node.props.host) || host,
+							username: token.node.props.username
 						}
 					})];
 				}
@@ -172,10 +161,10 @@ export default Vue.component('misskey-flavored-markdown', {
 					return [createElement('router-link', {
 						key: Math.random(),
 						attrs: {
-							to: `/tags/${encodeURIComponent(token.props.hashtag)}`,
+							to: `/tags/${encodeURIComponent(token.node.props.hashtag)}`,
 							style: 'color:var(--mfmHashtag);'
 						}
-					}, `#${token.props.hashtag}`)];
+					}, `#${token.node.props.hashtag}`)];
 				}
 
 				case 'blockCode': {
@@ -184,7 +173,7 @@ export default Vue.component('misskey-flavored-markdown', {
 					}, [
 						createElement('code', {
 							domProps: {
-								innerHTML: syntaxHighlight(token.props.code)
+								innerHTML: syntaxHighlight(token.node.props.code)
 							}
 						})
 					])];
@@ -193,7 +182,7 @@ export default Vue.component('misskey-flavored-markdown', {
 				case 'inlineCode': {
 					return [createElement('code', {
 						domProps: {
-							innerHTML: syntaxHighlight(token.props.code)
+							innerHTML: syntaxHighlight(token.node.props.code)
 						}
 					})];
 				}
@@ -227,8 +216,8 @@ export default Vue.component('misskey-flavored-markdown', {
 					return [createElement('mk-emoji', {
 						key: Math.random(),
 						attrs: {
-							emoji: token.props.emoji,
-							name: token.props.name
+							emoji: token.node.props.emoji,
+							name: token.node.props.name
 						},
 						props: {
 							customEmojis: this.customEmojis || customEmojis,
@@ -242,7 +231,7 @@ export default Vue.component('misskey-flavored-markdown', {
 					return [createElement(MkFormula, {
 						key: Math.random(),
 						props: {
-							formula: token.props.formula
+							formula: token.node.props.formula
 						}
 					})];
 				}
@@ -252,13 +241,13 @@ export default Vue.component('misskey-flavored-markdown', {
 					return [createElement(MkGoogle, {
 						key: Math.random(),
 						props: {
-							q: token.props.query
+							q: token.node.props.query
 						}
 					})];
 				}
 
 				default: {
-					console.log('unknown ast type:', token.name);
+					console.log('unknown ast type:', token.node.type);
 
 					return [];
 				}
diff --git a/src/mfm/html.ts b/src/mfm/html.ts
index 8712add054..6af2833858 100644
--- a/src/mfm/html.ts
+++ b/src/mfm/html.ts
@@ -2,10 +2,10 @@ const jsdom = require('jsdom');
 const { JSDOM } = jsdom;
 import config from '../config';
 import { INote } from '../models/note';
-import { Node } from './parser';
 import { intersperse } from '../prelude/array';
+import { MfmForest, MfmTree } from './parser';
 
-export default (tokens: Node[], mentionedRemoteUsers: INote['mentionedRemoteUsers'] = []) => {
+export default (tokens: MfmForest, mentionedRemoteUsers: INote['mentionedRemoteUsers'] = []) => {
 	if (tokens == null) {
 		return null;
 	}
@@ -14,11 +14,11 @@ export default (tokens: Node[], mentionedRemoteUsers: INote['mentionedRemoteUser
 
 	const doc = window.document;
 
-	function appendChildren(children: Node[], targetElement: any): void {
-		for (const child of children.map(n => handlers[n.name](n))) targetElement.appendChild(child);
+	function appendChildren(children: MfmForest, targetElement: any): void {
+		for (const child of children.map(t => handlers[t.node.type](t))) targetElement.appendChild(child);
 	}
 
-	const handlers: { [key: string]: (token: Node) => any } = {
+	const handlers: { [key: string]: (token: MfmTree) => any } = {
 		bold(token) {
 			const el = doc.createElement('b');
 			appendChildren(token.children, el);
@@ -58,7 +58,7 @@ export default (tokens: Node[], mentionedRemoteUsers: INote['mentionedRemoteUser
 		blockCode(token) {
 			const pre = doc.createElement('pre');
 			const inner = doc.createElement('code');
-			inner.innerHTML = token.props.code;
+			inner.innerHTML = token.node.props.code;
 			pre.appendChild(inner);
 			return pre;
 		},
@@ -70,39 +70,39 @@ export default (tokens: Node[], mentionedRemoteUsers: INote['mentionedRemoteUser
 		},
 
 		emoji(token) {
-			return doc.createTextNode(token.props.emoji ? token.props.emoji : `:${token.props.name}:`);
+			return doc.createTextNode(token.node.props.emoji ? token.node.props.emoji : `:${token.node.props.name}:`);
 		},
 
 		hashtag(token) {
 			const a = doc.createElement('a');
-			a.href = `${config.url}/tags/${token.props.hashtag}`;
-			a.textContent = `#${token.props.hashtag}`;
+			a.href = `${config.url}/tags/${token.node.props.hashtag}`;
+			a.textContent = `#${token.node.props.hashtag}`;
 			a.setAttribute('rel', 'tag');
 			return a;
 		},
 
 		inlineCode(token) {
 			const el = doc.createElement('code');
-			el.textContent = token.props.code;
+			el.textContent = token.node.props.code;
 			return el;
 		},
 
 		math(token) {
 			const el = doc.createElement('code');
-			el.textContent = token.props.formula;
+			el.textContent = token.node.props.formula;
 			return el;
 		},
 
 		link(token) {
 			const a = doc.createElement('a');
-			a.href = token.props.url;
+			a.href = token.node.props.url;
 			appendChildren(token.children, a);
 			return a;
 		},
 
 		mention(token) {
 			const a = doc.createElement('a');
-			const { username, host, acct } = token.props;
+			const { username, host, acct } = token.node.props;
 			switch (host) {
 				case 'github.com':
 					a.href = `https://github.com/${username}`;
@@ -133,7 +133,7 @@ export default (tokens: Node[], mentionedRemoteUsers: INote['mentionedRemoteUser
 
 		text(token) {
 			const el = doc.createElement('span');
-			const nodes = (token.props.text as string).split('\n').map(x => doc.createTextNode(x));
+			const nodes = (token.node.props.text as string).split('\n').map(x => doc.createTextNode(x));
 
 			for (const x of intersperse('br', nodes)) {
 				el.appendChild(x === 'br' ? doc.createElement('br') : x);
@@ -144,15 +144,15 @@ export default (tokens: Node[], mentionedRemoteUsers: INote['mentionedRemoteUser
 
 		url(token) {
 			const a = doc.createElement('a');
-			a.href = token.props.url;
-			a.textContent = token.props.url;
+			a.href = token.node.props.url;
+			a.textContent = token.node.props.url;
 			return a;
 		},
 
 		search(token) {
 			const a = doc.createElement('a');
-			a.href = `https://www.google.com/?#q=${token.props.query}`;
-			a.textContent = token.props.content;
+			a.href = `https://www.google.com/?#q=${token.node.props.query}`;
+			a.textContent = token.node.props.content;
 			return a;
 		}
 	};
diff --git a/src/mfm/parse.ts b/src/mfm/parse.ts
index 58e126be3e..21e4ca651f 100644
--- a/src/mfm/parse.ts
+++ b/src/mfm/parse.ts
@@ -1,40 +1,36 @@
-import parser, { Node, plainParser } from './parser';
+import parser, { plainParser, MfmForest, MfmTree } from './parser';
 import * as A from '../prelude/array';
 import * as S from '../prelude/string';
+import { createTree, createLeaf } from '../prelude/tree';
 
-export default (source: string, plainText = false): Node[] => {
-	if (source == null || source == '') {
-		return null;
-	}
-
-	let nodes: Node[] = plainText ? plainParser.root.tryParse(source) : parser.root.tryParse(source);
+function concatTextTrees(ts: MfmForest): MfmTree {
+	return createLeaf({ type: 'text', props: { text: S.concat(ts.map(x => x.node.props.text)) } });
+}
 
-	const combineText = (es: Node[]): Node =>
-		({ name: 'text', props: { text: S.concat(es.map(e => e.props.text)) } });
+function concatIfTextTrees(ts: MfmForest): MfmForest {
+	return ts[0].node.type === 'text' ? [concatTextTrees(ts)] : ts;
+}
 
-	const concatText = (nodes: Node[]): Node[] =>
-		A.concat(A.groupOn(x => x.name, nodes).map(es =>
-			es[0].name === 'text' ? [combineText(es)] : es
-		));
+function concatConsecutiveTextTrees(ts: MfmForest): MfmForest {
+	const us = A.concat(A.groupOn(t => t.node.type, ts).map(concatIfTextTrees));
+	return us.map(t => createTree(t.node, concatConsecutiveTextTrees(t.children)));
+}
 
-	const concatTextRecursive = (es: Node[]): void => {
-		for (const x of es.filter(x => x.children)) {
-			x.children = concatText(x.children);
-			concatTextRecursive(x.children);
-		}
-	};
+function isEmptyTextTree(t: MfmTree): boolean {
+	return t.node.type == 'text' && t.node.props.text === '';
+}
 
-	nodes = concatText(nodes);
-	concatTextRecursive(nodes);
+function removeEmptyTextNodes(ts: MfmForest): MfmForest {
+	return ts
+		.filter(t => !isEmptyTextTree(t))
+		.map(t => createTree(t.node, removeEmptyTextNodes(t.children)));
+}
 
-	const removeEmptyTextNodes = (nodes: Node[]) => {
-		for (const n of nodes.filter(n => n.children)) {
-			n.children = removeEmptyTextNodes(n.children);
-		}
-		return nodes.filter(n => !(n.name == 'text' && n.props.text == ''));
-	};
-
-	nodes = removeEmptyTextNodes(nodes);
+export default (source: string, plainText = false): MfmForest => {
+	if (source == null || source == '') {
+		return null;
+	}
 
-	return nodes;
+	const raw = plainText ? plainParser.root.tryParse(source) : parser.root.tryParse(source) as MfmForest;
+	return removeEmptyTextNodes(concatConsecutiveTextTrees(raw));
 };
diff --git a/src/mfm/parser.ts b/src/mfm/parser.ts
index 56c49ba3fa..885b7e01cd 100644
--- a/src/mfm/parser.ts
+++ b/src/mfm/parser.ts
@@ -2,41 +2,44 @@ import * as P from 'parsimmon';
 import parseAcct from '../misc/acct/parse';
 import { toUnicode } from 'punycode';
 import { takeWhile } from '../prelude/array';
+import { Tree } from '../prelude/tree';
+import * as T from '../prelude/tree';
 
 const emojiRegex = /((?:\ud83d[\udc68\udc69])(?:\ud83c[\udffb-\udfff])?\u200d(?:\u2695\ufe0f|\u2696\ufe0f|\u2708\ufe0f|\ud83c[\udf3e\udf73\udf93\udfa4\udfa8\udfeb\udfed]|\ud83d[\udcbb\udcbc\udd27\udd2c\ude80\ude92]|\ud83e[\uddb0-\uddb3])|(?:\ud83c[\udfcb\udfcc]|\ud83d[\udd74\udd75]|\u26f9)((?:\ud83c[\udffb-\udfff]|\ufe0f)\u200d[\u2640\u2642]\ufe0f)|(?:\ud83c[\udfc3\udfc4\udfca]|\ud83d[\udc6e\udc71\udc73\udc77\udc81\udc82\udc86\udc87\ude45-\ude47\ude4b\ude4d\ude4e\udea3\udeb4-\udeb6]|\ud83e[\udd26\udd35\udd37-\udd39\udd3d\udd3e\uddb8\uddb9\uddd6-\udddd])(?:\ud83c[\udffb-\udfff])?\u200d[\u2640\u2642]\ufe0f|(?:\ud83d\udc68\u200d\u2764\ufe0f\u200d\ud83d\udc8b\u200d\ud83d\udc68|\ud83d\udc68\u200d\ud83d\udc68\u200d\ud83d\udc66\u200d\ud83d\udc66|\ud83d\udc68\u200d\ud83d\udc68\u200d\ud83d\udc67\u200d\ud83d[\udc66\udc67]|\ud83d\udc68\u200d\ud83d\udc69\u200d\ud83d\udc66\u200d\ud83d\udc66|\ud83d\udc68\u200d\ud83d\udc69\u200d\ud83d\udc67\u200d\ud83d[\udc66\udc67]|\ud83d\udc69\u200d\u2764\ufe0f\u200d\ud83d\udc8b\u200d\ud83d[\udc68\udc69]|\ud83d\udc69\u200d\ud83d\udc69\u200d\ud83d\udc66\u200d\ud83d\udc66|\ud83d\udc69\u200d\ud83d\udc69\u200d\ud83d\udc67\u200d\ud83d[\udc66\udc67]|\ud83d\udc68\u200d\u2764\ufe0f\u200d\ud83d\udc68|\ud83d\udc68\u200d\ud83d\udc66\u200d\ud83d\udc66|\ud83d\udc68\u200d\ud83d\udc67\u200d\ud83d[\udc66\udc67]|\ud83d\udc68\u200d\ud83d\udc68\u200d\ud83d[\udc66\udc67]|\ud83d\udc68\u200d\ud83d\udc69\u200d\ud83d[\udc66\udc67]|\ud83d\udc69\u200d\u2764\ufe0f\u200d\ud83d[\udc68\udc69]|\ud83d\udc69\u200d\ud83d\udc66\u200d\ud83d\udc66|\ud83d\udc69\u200d\ud83d\udc67\u200d\ud83d[\udc66\udc67]|\ud83d\udc69\u200d\ud83d\udc69\u200d\ud83d[\udc66\udc67]|\ud83c\udff3\ufe0f\u200d\ud83c\udf08|\ud83c\udff4\u200d\u2620\ufe0f|\ud83d\udc41\u200d\ud83d\udde8|\ud83d\udc68\u200d\ud83d[\udc66\udc67]|\ud83d\udc69\u200d\ud83d[\udc66\udc67]|\ud83d\udc6f\u200d\u2640\ufe0f|\ud83d\udc6f\u200d\u2642\ufe0f|\ud83e\udd3c\u200d\u2640\ufe0f|\ud83e\udd3c\u200d\u2642\ufe0f|\ud83e\uddde\u200d\u2640\ufe0f|\ud83e\uddde\u200d\u2642\ufe0f|\ud83e\udddf\u200d\u2640\ufe0f|\ud83e\udddf\u200d\u2642\ufe0f)|[\u0023\u002a\u0030-\u0039]\ufe0f?\u20e3|(?:[\u00a9\u00ae\u2122\u265f]\ufe0f)|(?:\ud83c[\udc04\udd70\udd71\udd7e\udd7f\ude02\ude1a\ude2f\ude37\udf21\udf24-\udf2c\udf36\udf7d\udf96\udf97\udf99-\udf9b\udf9e\udf9f\udfcd\udfce\udfd4-\udfdf\udff3\udff5\udff7]|\ud83d[\udc3f\udc41\udcfd\udd49\udd4a\udd6f\udd70\udd73\udd76-\udd79\udd87\udd8a-\udd8d\udda5\udda8\uddb1\uddb2\uddbc\uddc2-\uddc4\uddd1-\uddd3\udddc-\uddde\udde1\udde3\udde8\uddef\uddf3\uddfa\udecb\udecd-\udecf\udee0-\udee5\udee9\udef0\udef3]|[\u203c\u2049\u2139\u2194-\u2199\u21a9\u21aa\u231a\u231b\u2328\u23cf\u23ed-\u23ef\u23f1\u23f2\u23f8-\u23fa\u24c2\u25aa\u25ab\u25b6\u25c0\u25fb-\u25fe\u2600-\u2604\u260e\u2611\u2614\u2615\u2618\u2620\u2622\u2623\u2626\u262a\u262e\u262f\u2638-\u263a\u2640\u2642\u2648-\u2653\u2660\u2663\u2665\u2666\u2668\u267b\u267f\u2692-\u2697\u2699\u269b\u269c\u26a0\u26a1\u26aa\u26ab\u26b0\u26b1\u26bd\u26be\u26c4\u26c5\u26c8\u26cf\u26d1\u26d3\u26d4\u26e9\u26ea\u26f0-\u26f5\u26f8\u26fa\u26fd\u2702\u2708\u2709\u270f\u2712\u2714\u2716\u271d\u2721\u2733\u2734\u2744\u2747\u2757\u2763\u2764\u27a1\u2934\u2935\u2b05-\u2b07\u2b1b\u2b1c\u2b50\u2b55\u3030\u303d\u3297\u3299])(?:\ufe0f|(?!\ufe0e))|(?:(?:\ud83c[\udfcb\udfcc]|\ud83d[\udd74\udd75\udd90]|[\u261d\u26f7\u26f9\u270c\u270d])(?:\ufe0f|(?!\ufe0e))|(?:\ud83c[\udf85\udfc2-\udfc4\udfc7\udfca]|\ud83d[\udc42\udc43\udc46-\udc50\udc66-\udc69\udc6e\udc70-\udc78\udc7c\udc81-\udc83\udc85-\udc87\udcaa\udd7a\udd95\udd96\ude45-\ude47\ude4b-\ude4f\udea3\udeb4-\udeb6\udec0\udecc]|\ud83e[\udd18-\udd1c\udd1e\udd1f\udd26\udd30-\udd39\udd3d\udd3e\uddb5\uddb6\uddb8\uddb9\uddd1-\udddd]|[\u270a\u270b]))(?:\ud83c[\udffb-\udfff])?|(?:\ud83c\udff4\udb40\udc67\udb40\udc62\udb40\udc65\udb40\udc6e\udb40\udc67\udb40\udc7f|\ud83c\udff4\udb40\udc67\udb40\udc62\udb40\udc73\udb40\udc63\udb40\udc74\udb40\udc7f|\ud83c\udff4\udb40\udc67\udb40\udc62\udb40\udc77\udb40\udc6c\udb40\udc73\udb40\udc7f|\ud83c\udde6\ud83c[\udde8-\uddec\uddee\uddf1\uddf2\uddf4\uddf6-\uddfa\uddfc\uddfd\uddff]|\ud83c\udde7\ud83c[\udde6\udde7\udde9-\uddef\uddf1-\uddf4\uddf6-\uddf9\uddfb\uddfc\uddfe\uddff]|\ud83c\udde8\ud83c[\udde6\udde8\udde9\uddeb-\uddee\uddf0-\uddf5\uddf7\uddfa-\uddff]|\ud83c\udde9\ud83c[\uddea\uddec\uddef\uddf0\uddf2\uddf4\uddff]|\ud83c\uddea\ud83c[\udde6\udde8\uddea\uddec\udded\uddf7-\uddfa]|\ud83c\uddeb\ud83c[\uddee-\uddf0\uddf2\uddf4\uddf7]|\ud83c\uddec\ud83c[\udde6\udde7\udde9-\uddee\uddf1-\uddf3\uddf5-\uddfa\uddfc\uddfe]|\ud83c\udded\ud83c[\uddf0\uddf2\uddf3\uddf7\uddf9\uddfa]|\ud83c\uddee\ud83c[\udde8-\uddea\uddf1-\uddf4\uddf6-\uddf9]|\ud83c\uddef\ud83c[\uddea\uddf2\uddf4\uddf5]|\ud83c\uddf0\ud83c[\uddea\uddec-\uddee\uddf2\uddf3\uddf5\uddf7\uddfc\uddfe\uddff]|\ud83c\uddf1\ud83c[\udde6-\udde8\uddee\uddf0\uddf7-\uddfb\uddfe]|\ud83c\uddf2\ud83c[\udde6\udde8-\udded\uddf0-\uddff]|\ud83c\uddf3\ud83c[\udde6\udde8\uddea-\uddec\uddee\uddf1\uddf4\uddf5\uddf7\uddfa\uddff]|\ud83c\uddf4\ud83c\uddf2|\ud83c\uddf5\ud83c[\udde6\uddea-\udded\uddf0-\uddf3\uddf7-\uddf9\uddfc\uddfe]|\ud83c\uddf6\ud83c\udde6|\ud83c\uddf7\ud83c[\uddea\uddf4\uddf8\uddfa\uddfc]|\ud83c\uddf8\ud83c[\udde6-\uddea\uddec-\uddf4\uddf7-\uddf9\uddfb\uddfd-\uddff]|\ud83c\uddf9\ud83c[\udde6\udde8\udde9\uddeb-\udded\uddef-\uddf4\uddf7\uddf9\uddfb\uddfc\uddff]|\ud83c\uddfa\ud83c[\udde6\uddec\uddf2\uddf3\uddf8\uddfe\uddff]|\ud83c\uddfb\ud83c[\udde6\udde8\uddea\uddec\uddee\uddf3\uddfa]|\ud83c\uddfc\ud83c[\uddeb\uddf8]|\ud83c\uddfd\ud83c\uddf0|\ud83c\uddfe\ud83c[\uddea\uddf9]|\ud83c\uddff\ud83c[\udde6\uddf2\uddfc]|\ud83c[\udccf\udd8e\udd91-\udd9a\udde6-\uddff\ude01\ude32-\ude36\ude38-\ude3a\ude50\ude51\udf00-\udf20\udf2d-\udf35\udf37-\udf7c\udf7e-\udf84\udf86-\udf93\udfa0-\udfc1\udfc5\udfc6\udfc8\udfc9\udfcf-\udfd3\udfe0-\udff0\udff4\udff8-\udfff]|\ud83d[\udc00-\udc3e\udc40\udc44\udc45\udc51-\udc65\udc6a-\udc6d\udc6f\udc79-\udc7b\udc7d-\udc80\udc84\udc88-\udca9\udcab-\udcfc\udcff-\udd3d\udd4b-\udd4e\udd50-\udd67\udda4\uddfb-\ude44\ude48-\ude4a\ude80-\udea2\udea4-\udeb3\udeb7-\udebf\udec1-\udec5\uded0-\uded2\udeeb\udeec\udef4-\udef9]|\ud83e[\udd10-\udd17\udd1d\udd20-\udd25\udd27-\udd2f\udd3a\udd3c\udd40-\udd45\udd47-\udd70\udd73-\udd76\udd7a\udd7c-\udda2\uddb4\uddb7\uddc0-\uddc2\uddd0\uddde-\uddff]|[\u23e9-\u23ec\u23f0\u23f3\u267e\u26ce\u2705\u2728\u274c\u274e\u2753-\u2755\u2795-\u2797\u27b0\u27bf\ue50a])|\ufe0f)/;
 
-export type Node = {
-	name: string,
-	children?: Node[],
-	props?: any;
-};
+type Node<T, P> = { type: T, props: P };
 
-export interface IMentionNode extends Node {
-	props: {
-		canonical: string;
-		username: string;
-		host: string;
-		acct: string;
-	};
-}
+export type MentionNode = Node<'mention', {
+	canonical: string,
+	username: string,
+	host: string,
+	acct: string
+}>;
 
-function _makeNode(name: string, children?: Node[], props?: any): Node {
-	return children ? {
-		name,
-		children,
-		props
-	} : {
-		name,
-		props
-	};
-}
+export type HashtagNode = Node<'hashtag', {
+	hashtag: string
+}>;
+
+export type EmojiNode = Node<'emoji', {
+	name: string
+}>;
+
+export type MfmNode =
+	MentionNode |
+	HashtagNode |
+	EmojiNode |
+	Node<string, any>;
+
+export type MfmTree = Tree<MfmNode>;
+
+export type MfmForest = MfmTree[];
 
-function makeNode(name: string, props?: any): Node {
-	return _makeNode(name, null, props);
+export function createLeaf(type: string, props: any): MfmTree {
+	return T.createLeaf({ type, props });
 }
 
-function makeNodeWithChildren(name: string, children: Node[], props?: any): Node {
-	return _makeNode(name, children, props);
+export function createTree(type: string, children: MfmForest, props: any): MfmTree {
+	return T.createTree({ type, props }, children);
 }
 
 function getTrailingPosition(x: string): number {
@@ -79,17 +82,17 @@ export const plainParser = P.createLanguage({
 		r.text
 	).atLeast(1),
 
-	text: () => P.any.map(x => makeNode('text', { text: x })),
+	text: () => P.any.map(x => createLeaf('text', { text: x })),
 
 	//#region Emoji
 	emoji: r =>
 		P.alt(
 			P.regexp(/:([a-z0-9_+-]+):/i, 1)
-			.map(x => makeNode('emoji', {
+			.map(x => createLeaf('emoji', {
 				name: x
 			})),
 			P.regexp(emojiRegex)
-			.map(x => makeNode('emoji', {
+			.map(x => createLeaf('emoji', {
 				emoji: x
 			})),
 		),
@@ -119,12 +122,12 @@ const mfm = P.createLanguage({
 		r.text
 	).atLeast(1),
 
-	text: () => P.any.map(x => makeNode('text', { text: x })),
+	text: () => P.any.map(x => createLeaf('text', { text: x })),
 
 	//#region Big
 	big: r =>
 		P.regexp(/^\*\*\*([\s\S]+?)\*\*\*/, 1)
-		.map(x => makeNodeWithChildren('big', P.alt(
+		.map(x => createTree('big', P.alt(
 			r.strike,
 			r.italic,
 			r.mention,
@@ -132,13 +135,13 @@ const mfm = P.createLanguage({
 			r.emoji,
 			r.math,
 			r.text
-		).atLeast(1).tryParse(x))),
+		).atLeast(1).tryParse(x), {})),
 	//#endregion
 
 	//#region Small
 	small: r =>
 		P.regexp(/<small>([\s\S]+?)<\/small>/, 1)
-		.map(x => makeNodeWithChildren('small', P.alt(
+		.map(x => createTree('small', P.alt(
 			r.strike,
 			r.italic,
 			r.mention,
@@ -146,7 +149,7 @@ const mfm = P.createLanguage({
 			r.emoji,
 			r.math,
 			r.text
-		).atLeast(1).tryParse(x))),
+		).atLeast(1).tryParse(x), {})),
 	//#endregion
 
 	//#region Block code
@@ -156,7 +159,7 @@ const mfm = P.createLanguage({
 				const text = input.substr(i);
 				const match = text.match(/^```(.+?)?\n([\s\S]+?)\n```(\n|$)/i);
 				if (!match) return P.makeFailure(i, 'not a blockCode');
-				return P.makeSuccess(i + match[0].length, makeNode('blockCode', { code: match[2], lang: match[1] ? match[1].trim() : null }));
+				return P.makeSuccess(i + match[0].length, createLeaf('blockCode', { code: match[2], lang: match[1] ? match[1].trim() : null }));
 			})
 		),
 	//#endregion
@@ -164,7 +167,7 @@ const mfm = P.createLanguage({
 	//#region Bold
 	bold: r =>
 		P.regexp(/\*\*([\s\S]+?)\*\*/, 1)
-		.map(x => makeNodeWithChildren('bold', P.alt(
+		.map(x => createTree('bold', P.alt(
 			r.strike,
 			r.italic,
 			r.mention,
@@ -173,13 +176,13 @@ const mfm = P.createLanguage({
 			r.link,
 			r.emoji,
 			r.text
-		).atLeast(1).tryParse(x))),
+		).atLeast(1).tryParse(x), {})),
 	//#endregion
 
 	//#region Center
 	center: r =>
 		P.regexp(/<center>([\s\S]+?)<\/center>/, 1)
-		.map(x => makeNodeWithChildren('center', P.alt(
+		.map(x => createTree('center', P.alt(
 			r.big,
 			r.small,
 			r.bold,
@@ -193,18 +196,18 @@ const mfm = P.createLanguage({
 			r.url,
 			r.link,
 			r.text
-		).atLeast(1).tryParse(x))),
+		).atLeast(1).tryParse(x), {})),
 	//#endregion
 
 	//#region Emoji
 	emoji: r =>
 		P.alt(
 			P.regexp(/:([a-z0-9_+-]+):/i, 1)
-			.map(x => makeNode('emoji', {
+			.map(x => createLeaf('emoji', {
 				name: x
 			})),
 			P.regexp(emojiRegex)
-			.map(x => makeNode('emoji', {
+			.map(x => createLeaf('emoji', {
 				emoji: x
 			})),
 		),
@@ -221,20 +224,20 @@ const mfm = P.createLanguage({
 			if (hashtag.match(/^[0-9]+$/)) return P.makeFailure(i, 'not a hashtag');
 			if (input[i - 1] != null && input[i - 1].match(/[a-z0-9]/i)) return P.makeFailure(i, 'not a hashtag');
 			if (hashtag.length > 50) return P.makeFailure(i, 'not a hashtag');
-			return P.makeSuccess(i + ('#' + hashtag).length, makeNode('hashtag', { hashtag: hashtag }));
+			return P.makeSuccess(i + ('#' + hashtag).length, createLeaf('hashtag', { hashtag: hashtag }));
 		}),
 	//#endregion
 
 	//#region Inline code
 	inlineCode: r =>
 		P.regexp(/`([^´\n]+?)`/, 1)
-		.map(x => makeNode('inlineCode', { code: x })),
+		.map(x => createLeaf('inlineCode', { code: x })),
 	//#endregion
 
 	//#region Italic
 	italic: r =>
 		P.regexp(/<i>([\s\S]+?)<\/i>/, 1)
-		.map(x => makeNodeWithChildren('italic', P.alt(
+		.map(x => createTree('italic', P.alt(
 			r.bold,
 			r.strike,
 			r.mention,
@@ -243,7 +246,7 @@ const mfm = P.createLanguage({
 			r.link,
 			r.emoji,
 			r.text
-		).atLeast(1).tryParse(x))),
+		).atLeast(1).tryParse(x), {})),
 	//#endregion
 
 	//#region Link
@@ -258,7 +261,7 @@ const mfm = P.createLanguage({
 			P.string(')'),
 		)
 		.map((x: any) => {
-			return makeNodeWithChildren('link', P.alt(
+			return createTree('link', P.alt(
 				r.big,
 				r.small,
 				r.bold,
@@ -269,7 +272,7 @@ const mfm = P.createLanguage({
 				r.text
 			).atLeast(1).tryParse(x.text), {
 				silent: x.silent,
-				url: x.url.props.url
+				url: x.url.node.props.url
 			});
 		}),
 	//#endregion
@@ -277,7 +280,7 @@ const mfm = P.createLanguage({
 	//#region Math
 	math: r =>
 		P.regexp(/\\\((.+?)\\\)/, 1)
-		.map(x => makeNode('math', { formula: x })),
+		.map(x => createLeaf('math', { formula: x })),
 	//#endregion
 
 	//#region Mention
@@ -292,7 +295,7 @@ const mfm = P.createLanguage({
 		.map(x => {
 			const { username, host } = parseAcct(x.substr(1));
 			const canonical = host != null ? `@${username}@${toUnicode(host)}` : x;
-			return makeNode('mention', {
+			return createLeaf('mention', {
 				canonical, username, host, acct: x
 			});
 		}),
@@ -301,7 +304,7 @@ const mfm = P.createLanguage({
 	//#region Motion
 	motion: r =>
 		P.alt(P.regexp(/\(\(\(([\s\S]+?)\)\)\)/, 1), P.regexp(/<motion>(.+?)<\/motion>/, 1))
-		.map(x => makeNodeWithChildren('motion', P.alt(
+		.map(x => createTree('motion', P.alt(
 			r.bold,
 			r.small,
 			r.strike,
@@ -313,7 +316,7 @@ const mfm = P.createLanguage({
 			r.link,
 			r.math,
 			r.text
-		).atLeast(1).tryParse(x))),
+		).atLeast(1).tryParse(x), {})),
 	//#endregion
 
 	//#region Quote
@@ -325,7 +328,7 @@ const mfm = P.createLanguage({
 			const qInner = quote.join('\n').replace(/^>/gm, '').replace(/^ /gm, '');
 			if (qInner == '') return P.makeFailure(i, 'not a quote');
 			const contents = r.root.tryParse(qInner);
-			return P.makeSuccess(i + quote.join('\n').length + 1, makeNodeWithChildren('quote', contents));
+			return P.makeSuccess(i + quote.join('\n').length + 1, createTree('quote', contents, {}));
 		})),
 	//#endregion
 
@@ -335,14 +338,14 @@ const mfm = P.createLanguage({
 			const text = input.substr(i);
 			const match = text.match(/^(.+?)( |　)(検索|\[検索\]|Search|\[Search\])(\n|$)/i);
 			if (!match) return P.makeFailure(i, 'not a search');
-			return P.makeSuccess(i + match[0].length, makeNode('search', { query: match[1], content: match[0].trim() }));
+			return P.makeSuccess(i + match[0].length, createLeaf('search', { query: match[1], content: match[0].trim() }));
 		})),
 	//#endregion
 
 	//#region Strike
 	strike: r =>
 		P.regexp(/~~(.+?)~~/, 1)
-		.map(x => makeNodeWithChildren('strike', P.alt(
+		.map(x => createTree('strike', P.alt(
 			r.bold,
 			r.italic,
 			r.mention,
@@ -351,7 +354,7 @@ const mfm = P.createLanguage({
 			r.link,
 			r.emoji,
 			r.text
-		).atLeast(1).tryParse(x))),
+		).atLeast(1).tryParse(x), {})),
 	//#endregion
 
 	//#region Title
@@ -376,7 +379,7 @@ const mfm = P.createLanguage({
 				r.inlineCode,
 				r.text
 			).atLeast(1).tryParse(q);
-			return P.makeSuccess(i + match[0].length, makeNodeWithChildren('title', contents));
+			return P.makeSuccess(i + match[0].length, createTree('title', contents, {}));
 		})),
 	//#endregion
 
@@ -392,7 +395,7 @@ const mfm = P.createLanguage({
 			if (url.endsWith(',')) url = url.substr(0, url.lastIndexOf(','));
 			return P.makeSuccess(i + url.length, url);
 		})
-		.map(x => makeNode('url', { url: x })),
+		.map(x => createLeaf('url', { url: x })),
 	//#endregion
 });
 
diff --git a/src/misc/extract-emojis.ts b/src/misc/extract-emojis.ts
new file mode 100644
index 0000000000..a7b949f4f7
--- /dev/null
+++ b/src/misc/extract-emojis.ts
@@ -0,0 +1,9 @@
+import { EmojiNode, MfmForest } from '../mfm/parser';
+import { preorderF } from '../prelude/tree';
+import { unique } from '../prelude/array';
+
+export default function(mfmForest: MfmForest): string[] {
+	const emojiNodes = preorderF(mfmForest).filter(x => x.type === 'emoji') as EmojiNode[];
+	const emojis = emojiNodes.filter(x => x.props.name && x.props.name.length <= 100).map(x => x.props.name);
+	return unique(emojis);
+}
diff --git a/src/misc/extract-hashtags.ts b/src/misc/extract-hashtags.ts
new file mode 100644
index 0000000000..43eaa45909
--- /dev/null
+++ b/src/misc/extract-hashtags.ts
@@ -0,0 +1,9 @@
+import { HashtagNode, MfmForest } from '../mfm/parser';
+import { preorderF } from '../prelude/tree';
+import { unique } from '../prelude/array';
+
+export default function(mfmForest: MfmForest): string[] {
+	const hashtagNodes = preorderF(mfmForest).filter(x => x.type === 'hashtag') as HashtagNode[];
+	const hashtags = hashtagNodes.map(x => x.props.hashtag);
+	return unique(hashtags);
+}
diff --git a/src/misc/extract-mentions.ts b/src/misc/extract-mentions.ts
index 1d844211c0..a53a25ffc4 100644
--- a/src/misc/extract-mentions.ts
+++ b/src/misc/extract-mentions.ts
@@ -1,19 +1,10 @@
-import parse from '../mfm/parse';
-import { Node, IMentionNode } from '../mfm/parser';
+// test is located in test/extract-mentions
 
-export default function(tokens: ReturnType<typeof parse>): IMentionNode['props'][] {
-	const mentions: IMentionNode['props'][] = [];
+import { MentionNode, MfmForest } from '../mfm/parser';
+import { preorderF } from '../prelude/tree';
 
-	const extract = (tokens: Node[]) => {
-		for (const x of tokens.filter(x => x.name === 'mention')) {
-			mentions.push(x.props);
-		}
-		for (const x of tokens.filter(x => x.children)) {
-			extract(x.children);
-		}
-	};
-
-	extract(tokens);
-
-	return mentions;
+export default function(mfmForest: MfmForest): MentionNode['props'][] {
+	// TODO: 重複を削除
+	const mentionNodes = preorderF(mfmForest).filter(x => x.type === 'mention') as MentionNode[];
+	return mentionNodes.map(x => x.props);
 }
diff --git a/src/prelude/tree.ts b/src/prelude/tree.ts
new file mode 100644
index 0000000000..519234a0b0
--- /dev/null
+++ b/src/prelude/tree.ts
@@ -0,0 +1,36 @@
+import { concat, sum } from './array';
+
+export type Tree<T> = {
+	node: T,
+	children: Forest<T>;
+};
+
+export type Forest<T> = Tree<T>[];
+
+export function createLeaf<T>(node: T): Tree<T> {
+	return { node, children: [] };
+}
+
+export function createTree<T>(node: T, children: Forest<T>): Tree<T> {
+	return { node, children };
+}
+
+export function hasChildren<T>(t: Tree<T>): boolean {
+	return t.children.length !== 0;
+}
+
+export function preorder<T>(t: Tree<T>): T[] {
+	return [t.node, ...preorderF(t.children)];
+}
+
+export function preorderF<T>(ts: Forest<T>): T[] {
+	return concat(ts.map(preorder));
+}
+
+export function countNodes<T>(t: Tree<T>): number {
+	return preorder(t).length;
+}
+
+export function countNodesF<T>(ts: Forest<T>): number {
+	return sum(ts.map(countNodes));
+}
diff --git a/src/server/api/endpoints/i/update.ts b/src/server/api/endpoints/i/update.ts
index fbf1dc32e1..7bdd52883c 100644
--- a/src/server/api/endpoints/i/update.ts
+++ b/src/server/api/endpoints/i/update.ts
@@ -7,7 +7,7 @@ import { publishToFollowers } from '../../../../services/i/update';
 import define from '../../define';
 import getDriveFileUrl from '../../../../misc/get-drive-file-url';
 import parse from '../../../../mfm/parse';
-import { extractEmojis } from '../../../../services/note/create';
+import extractEmojis from '../../../../misc/extract-emojis';
 const langmap = require('langmap');
 
 export const meta = {
diff --git a/src/services/note/create.ts b/src/services/note/create.ts
index 55d5eed146..248c2372f0 100644
--- a/src/services/note/create.ts
+++ b/src/services/note/create.ts
@@ -24,12 +24,13 @@ import isQuote from '../../misc/is-quote';
 import notesChart from '../../chart/notes';
 import perUserNotesChart from '../../chart/per-user-notes';
 
-import { erase, unique } from '../../prelude/array';
+import { erase } from '../../prelude/array';
 import insertNoteUnread from './unread';
 import registerInstance from '../register-instance';
 import Instance from '../../models/instance';
-import { Node } from '../../mfm/parser';
 import extractMentions from '../../misc/extract-mentions';
+import extractEmojis from '../../misc/extract-emojis';
+import extractHashtags from '../../misc/extract-hashtags';
 
 type NotificationType = 'reply' | 'renote' | 'quote' | 'mention';
 
@@ -466,44 +467,6 @@ async function insertNote(user: IUser, data: Option, tags: string[], emojis: str
 	}
 }
 
-function extractHashtags(tokens: ReturnType<typeof parse>): string[] {
-	const hashtags: string[] = [];
-
-	const extract = (tokens: Node[]) => {
-		for (const x of tokens.filter(x => x.name === 'hashtag')) {
-			hashtags.push(x.props.hashtag);
-		}
-		for (const x of tokens.filter(x => x.children)) {
-			extract(x.children);
-		}
-	};
-
-	// Extract hashtags
-	extract(tokens);
-
-	return unique(hashtags);
-}
-
-export function extractEmojis(tokens: ReturnType<typeof parse>): string[] {
-	const emojis: string[] = [];
-
-	const extract = (tokens: Node[]) => {
-		for (const x of tokens.filter(x => x.name === 'emoji')) {
-			if (x.props.name && x.props.name.length <= 100) {
-				emojis.push(x.props.name);
-			}
-		}
-		for (const x of tokens.filter(x => x.children)) {
-			extract(x.children);
-		}
-	};
-
-	// Extract emojis
-	extract(tokens);
-
-	return unique(emojis);
-}
-
 function index(note: INote) {
 	if (note.text == null || config.elasticsearch == null) return;