Monday, March 4, 2024

マークアップテキストのパース、ネストしたブロッククオートに対処

前回（マークアップテキストのパース、ブロッククオート領域をハンドルする）のエントリーで BlockQuote 領域が入れ子（ネスト）になっていても再帰処理すれば対処できるだろう、などと書いていたので、それを試した。

つまり、このような BlockQuote 領域が二重になっているマークアップテキストに対処する。

xxx
yyy
> aaa
> bbb
> > ccc
> > ddd
> > eee
> fff
> ggg
hhh
iii

前回のコードをそのまま拡張できればよかったのだが、諸事情によりクラス名を少し変更します。

Node という名前で定義していたこのクラスを・・・

sealed class Node(open val lines: List<Line>){
    data class Just(override val lines: List<Line>): Node(lines)
    data class BlockQuote(override val lines: List<Line>): Node(lines)
}

TreeValue という名前に変更します。

sealed class TreeValue(open val lines: List<Line>){
    data class Just(override val lines: List<Line>): TreeValue(lines)
    data class BlockQuote(override val lines: List<Line>): TreeValue(lines)
    object Nothing: TreeValue(listOf())
}

そして TreeValue.Just, TreeValue.BlockQuote に加えて Nothing を追加しました。

さらにネストした部分を管理できるように Tree クラスを用意します。

sealed class Tree(open val value: TreeValue){
    data class Leaf(override val value: TreeValue): Tree(value)
    data class Node(override val value: TreeValue, val children: List<Tree>): Tree(value)
}

あとでわかったのですが、実際は Tree.Node は value を持つことはなかった。
sealed class Tree(open val value: TreeValue){
    data class Leaf(override val value: TreeValue): Tree(value)
    data class Node(override val value: TreeValue.Nothing, val children: List<Tree>): Tree(value)
    //data class Node(override val value: TreeValue, val children: List<Tree>): Tree(value)
}
さらに、 Tree.Node の value が常に TreeValue.Nothing なのだから、そもそもそれ自体を無くすことができる。つまり、Tree クラスの定義は次のようになる。（ただし、このように変更するとコードの修正範囲は先ほどの変更よりもずっと増える。）
sealed class Tree {
    data class Leaf(val value: TreeValue): Tree()
    data class Node(val children: List<Tree>): Tree()
}
詳細はこちらを参照のこと。

Node クラスを TreeValue に改名したので toNodeList 関数が toTreeValueList 関数に変わっています。処理内容は変わっていません。

val toTreeValueList: (List<Line>)->List<TreeValue> = { lineList->
    val removeLastOne: (List<TreeValue>)->List<TreeValue> = { treeValueList->
        if( treeValueList.isEmpty() ){ listOf() } else { 0.until(treeValueList.size-1).map{ treeValueList[it] } }
    }

    val initValue = listOf<TreeValue>()

    lineList.fold(initValue){ acc, line->
        if( acc.isEmpty() ){
            val newNode = when( line ){
                is Line.Just       -> TreeValue.Just(listOf(line))
                is Line.BlockQuote -> TreeValue.BlockQuote(listOf(line))
            }
            acc + listOf(newNode)
        } else {
            val lastOne: TreeValue = acc.last()
            when( lastOne ){
                is TreeValue.Nothing-> {
                    acc
                }

                is TreeValue.Just-> {
                    when(line){
                        is Line.Just -> {
                            // Just and Just
                            val newLastOne = TreeValue.Just(lastOne.lines + listOf(line))
                            removeLastOne(acc) + newLastOne
                        }
                        is Line.BlockQuote -> {
                            // Just and BlockQuote
                            val newLastOne = TreeValue.BlockQuote(listOf(line))
                            acc + listOf(newLastOne)
                        }
                    }
                }
    
                is TreeValue.BlockQuote-> {
                    when(line){
                        is Line.Just -> {
                            // BlockQuote and Just
                            val newLastOne = TreeValue.Just(listOf(line))
                            acc + listOf(newLastOne)
                        }
                        is Line.BlockQuote -> {
                            // BlockQuote and BlockQuote
                            val newLastOne = TreeValue.BlockQuote(lastOne.lines + listOf(line))
                            removeLastOne(acc) + newLastOne
                        }
                    }
                }
            }
        }
    }
}

これから Tree を構築したいのですが、その前準備として (String)->List<TreeValue> する関数 fromTextToTreeValueList を定義しておきます。

val fromTextToTreeValueList: (String)->List<TreeValue> = { markupText->
    val lines: List<String> = toLines(markupText)
    val lineList: List<Line> = toLineList( lines )
    toTreeValueList( lineList )
}

Tree をビルド

それではこの fromTextToTreeValueList 関数を使って Tree をビルドする関数 buildTree を書きます。

再帰する関数なので fun を使って定義しています。シグニチャーがこれ (String)->List<Tree> になっていることに注意して実装します。

やっていることは List<TreeValue> を map して List<Tree> に変換しているだけです。ただし、TreeValue が BlockQuote だった場合に、さらにその中にネストして BlockQuote のマークアップが含まれている可能性があるので、その場合は、再帰的に bludTree を呼び出しているサブツリーを構築しているところがポイントです。

fun buildTree(markupText: String): List<Tree> {
    val br = System.getProperty("line.separator")

    val isBlockQuote: (String)->Boolean = { line->
        val m0 = "^>$".toRegex().find(line)
        val m1 = "^> ".toRegex().find(line)
        (m0!=null || m1!=null)
    }

    val treeValueList = fromTextToTreeValueList(markupText)
    val children: List<Tree> = treeValueList.mapNotNull { treeValue->
        when(treeValue){
            is TreeValue.Nothing-> {
                null
            }

            is TreeValue.Just -> {
                Tree.Leaf(treeValue)
            }

            is TreeValue.BlockQuote -> {
                val hasBlockQuote = (treeValue.lines.map { it.value } .filter { line: String-> isBlockQuote(line) }.size>0)
                if( !hasBlockQuote ){
                    Tree.Leaf(treeValue)
                } else {
                    val subMarkupText = treeValue.lines.map { it.value } .joinToString(br)
                    Tree.Node(TreeValue.Nothing, buildTree(subMarkupText))
                }
            }
        }
    }

    return children
}

この buildTree 関数を使うコードはこれです。

val markupText = """
xxx
yyy
> aaa
> bbb
> > ccc
> > ddd
> > eee
> fff
> ggg
hhh
iii
"""

val rootTreeValue = TreeValue.Nothing
val children = buildTree(markupText)
val rootTree = if( children.size>0 ){ Tree.Node(rootTreeValue, children) } else { Tree.Leaf(rootTreeValue) }

println(rootTree)

それでは実行してみます。

$ kotlin main.kts
Node(value=Main$TreeValue$Nothing@5b152082, children=[Leaf(value=Just(lines=[Just(value=), Just(value=xxx), Just(value=yyy)])), Node(value=Main$TreeValue$Nothing@5b152082, children=[Leaf(value=Just(lines=[Just(value=aaa), Just(value=bbb)])), Leaf(value=BlockQuote(lines=[BlockQuote(value=ccc), BlockQuote(value=ddd), BlockQuote(value=eee)])), Leaf(value=Just(lines=[Just(value=fff), Just(value=ggg)]))]), Leaf(value=Just(lines=[Just(value=hhh), Just(value=iii)]))])

構築した rootTree を println しただけでは、意図通り作動しているのかよくわからない。 showTree 関数を書きます。

fun showTree(tree: Tree, depth: Int = 0): Unit {
    val br = System.getProperty("line.separator")

    val indent = 0.until(depth).map { "    " }.joinToString("")

    val text = tree.value.lines.map {
        "${indent}${it.value}"
    } .joinToString(br)


    when(tree){
        is Tree.Leaf -> {
            val name = when(tree.value){
                is TreeValue.Nothing -> "doc"
                is TreeValue.Just -> "just"
                is TreeValue.BlockQuote -> "blockquote"
            }

            println("${indent}--- <$name> ---")
            println(text)
            println("${indent}--- </$name>---")
        }
        is Tree.Node -> {
            val docOrBlockQuote = if( depth==0 ){ "doc" } else { "blockquote" }
            println("${indent}--- <$docOrBlockQuote> ---")

            println(text)
            tree.children.forEach { child->
                showTree( child ,depth+1 )
            }

            println("${indent}--- </$docOrBlockQuote>---")
        }
    }
}

println(rootTree) の代わりに showTree(rootTree) して実行します。

$ kotlin main.kts
--- <doc> ---

    --- <just> ---

    xxx
    yyy
    --- </just>---
    --- <blockquote> ---

        --- <just> ---
        aaa
        bbb
        --- </just>---
        --- <blockquote> ---
        ccc
        ddd
        eee
        --- </blockquote>---
        --- <just> ---
        fff
        ggg
        --- </just>---
    --- </blockquote>---
    --- <just> ---
    hhh
    iii

    --- </just>---
--- </doc>---

意図通り、ネストした BlockQuote ブロックまでふくめて木を構築できています。

まとめ

これで（スタックオーバーフローしなければ）何回ネストしても対処できます。おそらく、リストのマークアップなどもこれを応用すれば取り扱えるようになるのではないかと思う。

例によって最後にコード全体を掲載します。

//
// main.kts
//

val toLines: (String)->List<String> = { text->
    val regex = "\r?\n".toRegex()
    text.split(regex)
}

sealed class Line(open val value: String){
    data class Just(override val value: String): Line(value)
    data class BlockQuote(override val value: String): Line(value)
}

val toLineList: (List<String>)->List<Line> ={ lines->
    val isBlockQuote: (String)->Boolean = { line->
        val m0 = "^>$".toRegex().find(line)
        val m1 = "^> ".toRegex().find(line)
        (m0!=null || m1!=null)
    }

    val stripBlockQuoteMarkup: (String)-> String = { line->
        if( isBlockQuote(line) ){
            val m0 = "^>$".toRegex().find(line)
            if( m0!=null ){
                ""
            } else {
                val m1 = "^> (.*)".toRegex().find(line)
                if( m1!=null ){ m1.groupValues[1] } else { line }
            }
        } else {
            line
        }
    }

    lines.map { line->
        if( isBlockQuote(line) ){
            Line.BlockQuote( stripBlockQuoteMarkup(line) )
        } else {
            Line.Just(line)
        }
    }
}

sealed class TreeValue(open val lines: List<Line>){
    object Nothing: TreeValue(listOf())
    data class Just(override val lines: List<Line>): TreeValue(lines)
    data class BlockQuote(override val lines: List<Line>): TreeValue(lines)
}

sealed class Tree(open val value: TreeValue){
    data class Leaf(override val value: TreeValue): Tree(value)
    data class Node(override val value: TreeValue, val children: List<Tree>): Tree(value)
}

val toTreeValueList: (List<Line>)->List<TreeValue> = { lineList->
    val removeLastOne: (List<TreeValue>)->List<TreeValue> = { treeValueList->
        if( treeValueList.isEmpty() ){ listOf() } else { 0.until(treeValueList.size-1).map{ treeValueList[it] } }
    }

    val initValue = listOf<TreeValue>()

    lineList.fold(initValue){ acc, line->
        if( acc.isEmpty() ){
            val newNode = when( line ){
                is Line.Just       -> TreeValue.Just(listOf(line))
                is Line.BlockQuote -> TreeValue.BlockQuote(listOf(line))
            }
            acc + listOf(newNode)
        } else {
            val lastOne: TreeValue = acc.last()
            when( lastOne ){
                is TreeValue.Nothing-> {
                    acc
                }

                is TreeValue.Just-> {
                    when(line){
                        is Line.Just -> {
                            // Just and Just
                            val newLastOne = TreeValue.Just(lastOne.lines + listOf(line))
                            removeLastOne(acc) + newLastOne
                        }
                        is Line.BlockQuote -> {
                            // Just and BlockQuote
                            val newLastOne = TreeValue.BlockQuote(listOf(line))
                            acc + listOf(newLastOne)
                        }
                    }
                }
    
                is TreeValue.BlockQuote-> {
                    when(line){
                        is Line.Just -> {
                            // BlockQuote and Just
                            val newLastOne = TreeValue.Just(listOf(line))
                            acc + listOf(newLastOne)
                        }
                        is Line.BlockQuote -> {
                            // BlockQuote and BlockQuote
                            val newLastOne = TreeValue.BlockQuote(lastOne.lines + listOf(line))
                            removeLastOne(acc) + newLastOne
                        }
                    }
                }
            }
        }
    }
}

val fromTextToTreeValueList: (String)->List<TreeValue> = { markupText->
    val lines: List<String> = toLines(markupText)
    val lineList: List<Line> = toLineList( lines )
    toTreeValueList( lineList )
}

fun buildTree(markupText: String): List<Tree> {
    val br = System.getProperty("line.separator")

    val isBlockQuote: (String)->Boolean = { line->
        val m0 = "^>$".toRegex().find(line)
        val m1 = "^> ".toRegex().find(line)
        (m0!=null || m1!=null)
    }

    val treeValueList = fromTextToTreeValueList(markupText)
    val children: List<Tree> = treeValueList.mapNotNull { treeValue->
        when(treeValue){
            is TreeValue.Nothing-> {
                null
            }

            is TreeValue.Just -> {
                Tree.Leaf(treeValue)
            }

            is TreeValue.BlockQuote -> {
                val hasBlockQuote = (treeValue.lines.map { it.value } .filter { line: String-> isBlockQuote(line) }.size>0)
                if( !hasBlockQuote ){
                    Tree.Leaf(treeValue)
                } else {
                    val subMarkupText = treeValue.lines.map { it.value } .joinToString(br)
                    Tree.Node(TreeValue.Nothing, buildTree(subMarkupText))
                }
            }
        }
    }

    return children
}

fun showTree(tree: Tree, depth: Int = 0): Unit {
    val br = System.getProperty("line.separator")

    val indent = 0.until(depth).map { "    " }.joinToString("")

    val text = tree.value.lines.map {
        "${indent}${it.value}"
    } .joinToString(br)


    when(tree){
        is Tree.Leaf -> {
            val name = when(tree.value){
                is TreeValue.Nothing -> "doc"
                is TreeValue.Just -> "just"
                is TreeValue.BlockQuote -> "blockquote"
            }

            println("${indent}--- <$name> ---")
            println(text)
            println("${indent}--- </$name>---")
        }
        is Tree.Node -> {
            val docOrBlockQuote = if( depth==0 ){ "doc" } else { "blockquote" }
            println("${indent}--- <$docOrBlockQuote> ---")

            println(text)
            tree.children.forEach { child->
                showTree( child ,depth+1 )
            }

            println("${indent}--- </$docOrBlockQuote>---")
        }
    }
}


val markupText = """
xxx
yyy
> aaa
> bbb
> > ccc
> > ddd
> > eee
> fff
> ggg
hhh
iii
"""

val rootTreeValue = TreeValue.Nothing
val children = buildTree(markupText)
val rootTree = if( children.size>0 ){ Tree.Node(rootTreeValue, children) } else { Tree.Leaf(rootTreeValue) }

//println(rootTree)

showTree(rootTree)

以上です。

Liked some of this entry? Buy me a coffee, please.