Go to Qiita Advent Calendar 2024 Top
LoginSignup
2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

Minecraft CommandAdvent Calendar 2023

Day 14
@crafter1415

データパックで文字列結合

Last updated at Posted at 2023-12-14

この記事は Minecraft Command Advent Calendar 2023 14日目の記事です。

この記事の内容はすべて JavaEdition 1.20.2-1.20.4 (Datapack Verison 16-26) を基準に書かれており、その他のバージョンにおける動作確認等は一切行われていません。

TL;DR

本記事のデータパックはGitHubに公開されています。理論的な話を飛ばして手っ取り早く使いたい方、及びソースコードを見られれば十分な方は以下のリンクを確認してください。

前置き

この記事では23w31aで追加されたマクロ機能を利用した文字列結合について取り上げます。
マクロを用いない文字列結合も理論上可能ですが、今回は取り上げません。
というか旧verの文字列結合の知識が全くないので取り上げられません。誰か記事書いてくれ。

あと、ゴリゴリのJavaコードが少しだけ出てきます。
Javaを覚えろとまではいわないけど、何らかのプログラミング言語の知見はあった方が良いかも。

これ本当にコマンドの記事なの......?

関数マクロ

23w31aアップデートで追加された関数マクロは、コマンドをmcfunctionファイルに記述する際にコマンドの一部を変数にしておくことができ、関数を引数と共に呼び出した段階でコマンドを確定させられるといった機能です。例えば、

$particle dust $(r) $(g) $(b) 1 ~ ~ ~ 0.5 0.5 0.5 5 force @a

のようなマクロ関数を作成しておき、後から r, g, b のキーを持つストレージなどを引数として呼び出すことにより、色が動的に変化するパーティクルを作成することが出来ます。

(今回は文字列結合に関する解説のため軽い解説で済ませますが、より詳しい解説を確認したい方はこま氏による解説記事などを確認することをお勧めします。)

単純に繋げてみる

このマクロ関数ですが、複数の変数が空白なく連続していても何の問題もないため、

$data modify storage concat: result set value "$(first)$(second)"

のような関数を作成してしまえば、例えば {first:"foo",second:"bar"} のような中身を持つストレージを引数に実行した場合、

data modify storage concat: result set value "foobar"

の形になり、簡単に結合結果である {result:"foobar"} が得られます。

......あれ？
これが出来るんだったら、文字列結合もこの一行で終わるんじゃないの？

引用符とエスケープ記号

残念ながら上の実装だとうまくいかないケースが存在します。
例えば、前半文字列が "text": 、後半文字列が "Hello world!" だった場合、マクロ変数を代入した際に得られた文字列が

data modify storage concat: result set value ""text":"Hello world!""

となり、前半文字列の一文字目である " が文字列の終わりと解釈され、残りの文字列 text":"Hello world!"" が余分なものと解釈されてパースに失敗してしまいます1。

「じゃあ単一引用符で囲めばいいジャマイカ！」と思うかもしれませんが、単一引用符でも全く同じ問題が発生しうるので解決とはいきません。囲うための文字と同じ文字が文字列中のどこかに一つでも入っていたらパースに失敗しるので、例えば二重引用符と単一引用符の両方が入っていた場合どちらでもどうにもならないことになります。

また、エスケープ文字が存在した場合、

  • "(二重引用符で囲んでいた場合) '(単一引用符で囲んでいた場合) 及び \ と結合することで該当の文字をエスケープし、文字列中の一文字という扱いにする（エスケープは消滅する。）
  • それ以外の文字と結合し、不正なエスケープにより CommandSyntaxException を発生させる1。（マクロは実行されない。）

のいずれかを辿ることになるため、どのみち正しい結果が得られなくなってしまいます。
そのため、結合前にエスケープが必要な文字にエスケープを追加する作業が必要になります。

本編

そういう訳で文字列結合の前に文字列にエスケープを追加する処理が入るわけですが、マイクラコマンドはそこまで都合よくできていないので「この文字列のn文字目に"\\"を追加！ﾊﾟｼｨｯ!!」とは出来ません。出来たらそれで文字列結合して終わりです。
なので、

  • 全ての入力文字列をエスケープが必要な部分にエスケープが加えられる形に分割する
  • エスケープが必要な文字列の前にエスケープ文字列を結合する
  • 処理後の文字列を結合していく

という段階を踏んで処理することになります。

データパックで文字列分割

いつからこの記事が文字列結合の記事だと錯覚していた？

冗談はさておき、まず第一処理である「エスケープが加えられる形への分割」を取り上げます。
もちろん文字列を1文字ずつに分割しエスケープが必要な文字そのものにエスケープを結合することも可能ですが、結合の際に要素数が出来るだけ少ない方が好ましいため、どのように分割数を減らすかを考えます。

二重引用符で文字列を結合する際にエスケープが必要となるのは、

  • 二重引用符 "
  • エスケープ文字 \

の二種類の文字ですが、結合の前には「これらの文字とそれより前の文字列の間」に丁度いい数のエスケープをﾊﾟｼｨｯと入れることになるので、これらの文字と直前の文字の間で切ったような状態にすればいいわけです。

実装

実装においては「元文字列のイテレーション中に " \ の位置 $x$ を記録し、次に出現した際に元文字列の $x$ (これを含む) から $i$ (これを含まない) までの部分文字列を配列に追加する」という実装を取ります。
ただし、実際には配列の先頭から取り出す操作は負荷が大きいため、引数群を逆順に反復する前提で後ろから反復し、文字列の後ろの部分が前に来るようにしています。

移植元 (Java)
// ...
    @SuppressWarnings("unchecked")
    static List<String> split(String arg) {
        List<String> results = new ArrayList<>();
        int index = arg.length();
        int marker = index;
        while (0 < index) {
            int imm = index-1;
            String ch = arg.substring(imm, index);
            if (ch.equals("\"") || ch.equals("\\")) {
                results.add(arg.substring(imm, marker));
                marker=imm;
            }
            index=imm;
        }
        if (marker != 0)
            results.add(arg.substring(0, marker));
        return results;
    }
// ...

2023/12/13 追記

引数がエスケープが必要な文字で始まらなかった際、分割後の最初の要素を前の引数の最後の要素と結合することで引数の数 $N$ とエスケープが必要な文字の数 $M$ に対して分割後の要素数の最大値を $N+M+1$ から $M+1$ に減らすことが可能でした。

    static Map.Entry<List<String>, Boolean> split(List<String> args) {
        List<String> result = new ArrayList<>();
        boolean noEscLast = false;
        for (String target : args) {
            int index = target.length();
            int marker = index;
            while (0<index) {
                int imm = index-1;
                String ch = target.substring(imm, index);
                if (ch.equals("\\") || ch.equals("\"")) {
                    result.add(target.substring(imm, marker));
                    marker=imm;
                    if (noEscLast) {
                        // 直前の要素の先頭にエスケープがないので今の要素と結合できる
                        // 結果配列は前の要素が後ろに来るので結合時は後ろの要素を手前に持っていく
                        String first = result.remove(result.size()-1);
                        String second = result.remove(result.size()-1);
                        // secondは今さっき切ったばっかりの奴なのでエスケープが必要な文字で始まる
                        result.add(eval("\"\\"+second+first+"\""));
                        noEscLast = false;
                    }
                }
                index=imm;
            }
            if (marker != 0) {
                result.add(target.substring(0, marker));
                // 要素が残っている == 先頭の文字がエスケープが必要な文字じゃない
                if (noEscLast) {
                    String first = result.remove(result.size()-1);
                    String second = result.remove(result.size()-1);
                    // secondは前述の通りエスケープが必要な文字で始まらないのでエスケープ不要
                    // 因みにわざわざevalを入れなくても second+first と等価
                    result.add(eval("\""+second+first+"\""));
                }
                noEscLast = true;
            }
        }
        // 最後の要素にエスケープが必要か否かはエスケープを追加するときに使えるので一緒に返す
        return new AbstractMap.SimpleEntry<>(result, noEscLast);
    }

結合

少し順番は変わってしまいますが、先に結合について考えてみます。
結合については冒頭に出てきた関数

再利用
$data modify storage concat: result set value "$(first)$(second)"

を用いるので、基本的に二つの文字列を結合しまとめていくことになり、二分木に近い考え方をすることが可能となります。(二分木に関する説明はここでは省略させていただきます)

      foobar
     /      \
   foo      bar
  /   \    /   \
 f    oo  b    ar
     /  \     /  \
    o    o   a    r

ここで、

  • 葉は分割後の各要素
  • 葉以外のノードは子ノード二つを結合してできた要素
  • 根は最終的に完成した文字列

という定義を用いると、「ノードの深さ=その要素が評価される回数」が成り立ちます。

ただ、 $n$ 回評価される文字列に必要なエスケープの数 $a_n$ は

評価が一回の時 文字自体をエスケープする1個のみのため
　$a_1 = 1$
評価が二回以上の時 文字へのエスケープ1個と残り(n-1)回分のエスケープを評価後に残すための倍量のエスケープが必要なため
　$a_{n+1} = 2a_n + 1$
これを解いて
　$a_n = 2^n - 1$

より指数関数的に増えて行くため、深さ5程度では問題になりませんが要素があまりに深い位置にあるとOutOfMemoryErrorの原因となってしまいます。なので極端な例を挙げると、

   foobar
  /      \
 f      oobar
       /     \
      o     obar
           /    \
          o     bar
               /   \
              b    ar
                  /  \
                 a    r

のような偏った木構造ではなく、平衡二分木に近い形であることが望ましいです。

今回は実装面での難易度を考え、以下のような実装を考えます。

  1. 全ての要素を一度キューへ格納する
  2. キューが空になるまで先頭と二番目を取り出して結合し、別のキューへ移す
    • 残った要素が一つだった場合、取り出した要素をそのまま別のキューへ移す
  3. 別のキューに移した要素全てを最初のキューへ移す
  4. キューに二つ以上要素が残っていたら 2 に戻って繰り返し

この実装を取ったとき、例えば大きさ11の配列の結合は次のようになります2。

                   123456789ab
                  /           \
          12345678             9ab
         /        \           /   \
     1234          5678      9a    b
    /    \        /    \    /  \
  12      34    56      78  9   a
 /  \    /  \  /  \    /  \
1    2  3   4  5   6  7    8

これは厳密には平衡二分木ではありませんが、実装から考えると

  • 各ループですべての要素は0回3または1回評価される
  • 各ループで要素数は元の半分を切り上げた値3になる

ことから、各要素の評価回数は高々 $\left\lceil\ \log_2M\ \right\rceil$ 回になるので問題ないと言えるでしょう。

実装

ここでもListTagはスタック構造として用いているため、長さと反転の有無を保存しておき、反転していない場合(=最初の反復対象が最後の要素の場合)にサイズが奇数だったら最初の要素を送る処理を取ります。

移植元 (Java)
// ...
        List<String> concat = new ArrayList<>(Arrays.asList(args));
        List<String> buffer = new ArrayList<>();
        boolean reversed = false;
        int size = concat.size();
// ...
        while (1 < size) {
            if (!reversed & size%2==1)
                buffer.add(concat.remove(concat.size()-1));
            while (2 <= concat.size()) {
                String b = concat.remove(concat.size()-1);
                String a = concat.remove(concat.size()-1);
                // eval関数: 引数を文字列としてパースする
                buffer.add(eval("\""+(reversed ? b+a : a+b)+"\""));
            }
            if (concat.size() != 0)
                buffer.add(concat.remove(0));
            concat = buffer;
            buffer = new ArrayList<>();
            reversed = !reversed;
            size /= 2;
        }
// ...

エスケープの追加

まだ全然続くんじゃ。

エスケープの追加は

  • 必要になりそうなエスケープの生成
  • 各要素の評価回数の算出
  • 評価回数に応じたエスケープを追加

の三段階で構成されますが、このうちの「各要素の評価回数の算出」は結合アルゴリズムに依存するため、先に結合に関して考える必要がありました。
ひとまず結合についてはこのアルゴリズムで確定させ、配列インデックスから評価回数を算出する方法を考察していきます。

評価回数の算出

仮に要素数が2の累乗だった場合、上のアルゴリズムで結合するとちょうど完全二分木を形成するように結合されるため、要素数 $N$ のときすべての要素において評価回数 $\log_2N$ が成り立ちます。

再利用
                   123456789ab
                  /           \
          12345678             9ab
         /        \           /   \
     1234          5678      9a    b
    /    \        /    \    /  \
  12      34    56      78  9   a
 /  \    /  \  /  \    /  \
1    2  3   4  5   6  7    8

ここで先ほどの図をもう一度見てみると、根ノードの左側の部分木は完全二分木をなしていることが分かります。これが偶然の産物でないことを示せれば、評価回数の算出にうまい事使えそうです。

要素数が $N$ の時、結合時に要素が2つ以上残っていれば必ず最初と二番目の要素が取り出されるため、前方 $2^{\left\lfloor\log_2N\right\rfloor}$ 個の要素はそれらのみで完結し、完全二分木を形成します。
ここで残された後方 $N - 2^{\left\lfloor\log_2N\right\rfloor}$ 個の要素についてですが、

$\left(N - 2^{\left\lfloor\log_2N\right\rfloor}\right) - \left(2^{\left\lfloor\log_2N\right\rfloor}\right)$
$= N - 2 \cdot 2^{\left\lfloor\log_2N\right\rfloor}$
$= N - 2^{\left\lfloor\log_2N\right\rfloor+1}$
$\leq N - 2^{\log_2N}$
$= N - N \ = 0$
よって $N - 2^{\left\lfloor\log_2N\right\rfloor} \leq 2^{\left\lfloor\log_2N\right\rfloor}$

より、後方の要素数は前方以下であることが分かるので、後方の要素をそれ単体で結合した場合結合にかかるループの回数は前方と同じかそれ以下となるため、前方と後方の結合は一番最後であることが分かり、根ノードの左側部分木は完全二分木であることが示されました。

これを用いると、要素数 $N$ の時の $i$ 番目の要素の評価回数 $f(N, i)$ は、以下のように分岐し細分化することが可能です。

  • $i \leq 2^{\left\lfloor\log_2N\right\rfloor}$ のとき
    • 前方の完全二分木の結合後、最後に後方要素との結合1回を行うため $\left\lfloor\log_2N\right\rfloor + 1$
      条件より要素数が2の累乗でないため
      $= \left\lceil\ \log_2N\ \right\rceil$
  • $2^{\left\lfloor\log_2N\right\rfloor} < i$ のとき
    • 後方が独立していることから後方 $N - 2^{\left\lfloor\log_2N\right\rfloor}$ 個のうち $i - 2^{\left\lfloor\log_2N\right\rfloor}$ 個目の要素の評価回数に最後の結合分の1回を足したものになるため
      結合回数 $f(N - 2^{\left\lfloor\log_2N\right\rfloor}, i - 2^{\left\lfloor\log_2N\right\rfloor}) + 1$

後はこれに沿って再帰する実装を書けば終わりです。

サンプルコード
Ans(n, i) {
  int f = ceil(log(2, n))
  int g = pow(2, f)
  if (n==g) return f
  if (i < g/2) return f
  else return Ans(n-g/2, i-g/2)+1
}

エスケープの生成・追加

ここまで来てしまえば後は単純です。

エスケープの生成に関しては、エスケープの個数の式

$a_1 = 1$
$a_{n+1} = 2a_n + 1$

が既に存在するため、これを漸化式のまま使えばエスケープが生成できます。
ただし、実装時の注意として、$n$個のエスケープ文字を残すためにその倍量のエスケープ文字を書く必要があるため、評価後に$2n$個のエスケープを残すためには結果的に$4n$個のエスケープが必要になります。
追加に関しても同様に、結合時の評価でエスケープが半分消えてしまうため倍量+1個のエスケープが必要となることに注意が必要です。

実装
concat:concat/escgen/add.macro
execute store result storage concat: escgen.arg int 0.9999999999 run data get storage concat: escgen.arg
$data modify storage concat: escgen.result append value "\\$(last)$(last)$(last)$(last)"
data modify storage concat: escgen.last set from storage concat: escgen.result[-1]
#tellraw @a {"storage":"concat:","nbt":"{}","color":"yellow"}
execute unless data storage concat: escgen{arg:0} run function concat:concat/escgen/add.macro with storage concat: escgen
concat:concat/slow/escape.macro
$data modify storage concat: target set value "$(token)$(token)\$(target)"

余談

冒頭にも記載しましたが、今回書いたデータパックはGitHubに公開されています。

test関数

今回のデータパックですが、substr logpow evalcnt など関数が小分けにされており、速度重視というより読みやすさ重視な構造になっていることがわかると思われます。
このような実装を取った理由として、「作成した関数を似た構造にしておくことにより、マクロ機能で一括ユニットテストを実行できるようにできる」というものが存在します。
本来のユニットテストの在り方とはやや異なるかもしれませんが、「マクロの活用法の一つ」として参考にしてみてください。

謝辞とか

先駆者

今回データパックを作成するにあたって、先駆者である @intsuc 氏のデータパック(下記)及び丁寧な解説ポストを参考にさせていただきました。時間があればぜひこちらもご確認ください。

IMP-Doc

今回のデータパックを書くにあたって、TheSkyBlessingのコーディング規則を非常に大きく参考にさせていただきました。
本記事中に登場するmcfunctionファイルにはIMP-Docは記載しておりませんが、GitHubに置かれているデータパックは殆どのファイルにIMP-Docによるドキュメンテーションが存在します。実際の関数の流れを確認したい場合は、ぜひそちらを有効活用ください。
また、本企画 Minecraft Command Advent Calender 2023 にもちぇん氏 @ChenCMD によるIMP-Docに関する記事があるため、そちらも是非追ってご確認ください。

その他

Pon氏デタパとメイン・サブ記事の査読アリガトナス！！

EOF

皆様も良きコマンドライフを！

  1. Brigadier 1.0.18により検証。
    https://github.com/Mojang/brigadier ↩ ↩2

  2. 結合の様子は図の通りだが、キューの中身としては1回目 [12, 34, 56, 78, 9a, b] 、二回目 [1234, 5678, 9ab] 、三回目 [12345678, 9ab] となる。 ↩

  3. 要素数が奇数の場合末端の要素は評価されないことが原因。 ↩ ↩2

2
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?