feat(blog/nuldoc): change content format from DocBook to NulDoc

1 files changed, 559 insertions, 0 deletions

diff --git a/vhosts/blog/content/posts/2022-04-09/phperkaigi-2022-tokens.ndoc b/vhosts/blog/content/posts/2022-04-09/phperkaigi-2022-tokens.ndoc
new file mode 100644
index 00000000..c13b0c55
--- /dev/null
+++ b/vhosts/blog/content/posts/2022-04-09/phperkaigi-2022-tokens.ndoc
@@ -0,0 +1,559 @@
+---
+[article]
+title = "PHPerKaigi 2022 トークン問題の解説"
+description = "PHPerKaigi 2022 で私が作成した PHPer チャレンジ問題を解説する。"
+tags = [
+  "conference",
+  "php",
+  "phperkaigi",
+]
+
+[[article.revisions]]
+date = "2022-04-09"
+remark = "公開"
+
+[[article.revisions]]
+date = "2022-04-16"
+remark = "2問目、3問目の解説を追加、1問目に加筆"
+---
+<article>
+  <section id="intro">
+    <h>はじめに</h>
+    <p>
+      本日開始された <a href="https://phperkaigi.jp/2022/">PHPerKaigi 2022</a> の PHPer
+      チャレンジにおいて、弊社
+      <a href="https://www.dgcircus.com/">デジタルサーカス株式会社</a> の問題を
+      3問作成した。この記事では、これらの問題の解説をおこなう。
+    </p>
+    <p>
+      リポジトリはこちら: <a href="https://github.com/nsfisis/PHPerKaigi2022-tokens">https://github.com/nsfisis/PHPerKaigi2022-tokens</a>
+    </p>
+  </section>
+  <section id="q1-brainfuck">
+    <h>第1問 brainf_ck.php</h>
+    <p>
+      ソースコードはこちら。実行には PHP 8.1 以上が必要なので注意。
+    </p>
+    <codeblock language="php">
+      <![CDATA[
+      <?php
+
+      declare(strict_types=0O1);
+
+      namespace Dgcircus\PHPerKaigi\Y2022;
+
+      /**
+       * @todo
+       * Run this program to acquire a PHPer token.
+       */
+
+      https://creativecommons.org/publicdomain/zero/1.0/
+
+      \error_reporting(~+!'We are hiring!');
+
+      $z = fn($f) => (fn($x) => $f(fn(...$xs) => $x($x)(...$xs)))(fn($x) => $f(fn(...$xs) => $x($x)(...$xs)));
+      $id = \spl_object_id(...);
+      $put = fn($c) => \printf('%c', $c);
+      $mm = fn($p, $n) => new \ArrayObject(\array_fill(+!![], $n, $p));
+
+      $👉 = fn($m, $p, $b, $e, $mp, $pc) => [++$mp, ++$pc];
+      $👈 = fn($m, $p, $b, $e, $mp, $pc) => [--$mp, ++$pc];
+      $👍 = fn($m, $p, $b, $e, $mp, $pc) => [$mp, ++$pc, ++$m[$mp]];
+      $👎 = fn($m, $p, $b, $e, $mp, $pc) => [$mp, ++$pc, --$m[$mp]];
+      $📝 = fn($m, $p, $b, $e, $mp, $pc) => [$mp, ++$pc, $put($m[$mp])];
+      $🤡 = fn($m, $p, $b, $e, $mp, $pc) => match ($m[$mp]) {
+        +!![] => [$mp, $z(fn($loop) => fn($pc, $n) => match ($id($p[$pc])) {
+          $b => $loop(++$pc, ++$n),
+          $e => $n === +!![] ? ++$pc : $loop(++$pc, --$n),
+          default => $loop(++$pc, $n),
+        })($pc, -![])],
+        default => [$mp, ++$pc],
+      };
+      $🎪 = fn($m, $p, $b, $e, $mp, $pc) => match ($m[$mp]) {
+        +!![] => [$mp, ++$pc],
+        default => [$mp, $z(fn($loop) => fn($pc, $n) => match ($id($p[$pc])) {
+          $e => $loop(--$pc, ++$n),
+          $b => $n === +!![] ? $pc+![] : $loop(--$pc, --$n),
+          default => $loop(--$pc, $n),
+        })($pc, -![])],
+      };
+      $🐘 = fn($p) => $z(fn($loop) => fn($m, $p, $b, $e, $mp, $pc) =>
+        isset($p[$pc]) && $loop($m, $p, $b, $e, ...($p[$pc]($m, $p, $b, $e, $mp, $pc)))
+      )($mm(+!![], +(![].![])), $p, $id($🤡), $id($🎪), +!![], +!![]);
+
+      $🐘([
+        $👍, $👍, $👍, $👍, $👍, $👍, $👍, $👍, $👍, $👍,
+        $🤡,
+        $👉, $👍, $👍, $👍,
+        $👉, $👍, $👍, $👍, $👍, $👍,
+        $👉, $👍, $👍, $👍, $👍, $👍, $👍, $👍, $👍, $👍, $👍, $👍, $👍,
+        $👉, $👍, $👍, $👍, $👍, $👍, $👍, $👍, $👍, $👍, $👍,
+        $👈, $👈, $👈, $👈, $👎,
+        $🎪,
+        $👉, $👍, $👍, $👍, $👍, $👍, $📝,
+        $👎, $👎, $📝,
+        $👉, $👎, $👎, $👎, $📝,
+        $👉, $👎, $👎, $👎, $📝,
+        $👎, $👎, $📝,
+        $👎, $📝,
+        $👈, $📝,
+        $👉, $👉, $👎, $👎, $📝,
+        $👍, $👍, $👍, $👍, $👍, $👍, $👍, $📝,
+        $👈, $👎, $👎, $👎, $👎, $📝,
+        $👈, $📝,
+        $👉, $👍, $👍, $📝,
+        $👉, $👎, $📝,
+        $👈, $📝,
+      ]);
+      ]]>
+    </codeblock>
+    <p>
+      この問題は、単に適切なバージョンの PHP で動かせばトークンが得られる。
+    </p>
+    <section id="q1-brainfuck--commentary">
+      <h>解説</h>
+      <section id="q1-brainfuck--commentary--emoji">
+        <h>絵文字</h>
+        <p>
+          まず目につくのは大量の絵文字だろう。 PHP
+          は識別子に使用できる文字の範囲が広く、絵文字も使うことができる。
+        </p>
+      </section>
+      <section id="q1-brainfuck--commentary--brainfuck">
+        <h>プログラム全体</h>
+        <p>
+          Brainf*ck のインタプリタとプログラムになっている。 Brainf*ck
+          とは、難解プログラミング言語のひとつであり、ここで説明するよりも
+          Wikipedia の該当ページを読んだ方がよい。
+        </p>
+        <p>
+          <a href="https://ja.wikipedia.org/wiki/Brainfuck">https://ja.wikipedia.org/wiki/Brainfuck</a>
+        </p>
+        <p>
+          なお、brainf*ck プログラムを普通の書き方で書くと、次のようになる。
+        </p>
+        <codeblock>
+          <![CDATA[
+          + + + + + + + + + +
+          [
+            > + + +
+            > + + + + +
+            > + + + + + + + + + + + +
+            > + + + + + + + + + +
+            < < < < -
+          ]
+          > + + + + + .
+          - - .
+          > - - - .
+          > - - - .
+          - - .
+          - .
+          < .
+          > > - - .
+          + + + + + + + .
+          < - - - - .
+          < .
+          > + + .
+          > - .
+          < .
+          ]]>
+        </codeblock>
+        <p>
+          実行結果はこちら: <a href="https://ideone.com/22VWmb">https://ideone.com/22VWmb</a>
+        </p>
+        <p>
+          それぞれの絵文字で表された関数が、各命令に対応している。
+        </p>
+        <ul>
+          <li><code>$👉</code>: <code>&gt;</code></li>
+          <li><code>$👈</code>: <code>&lt;</code></li>
+          <li><code>$👍</code>: <code>+</code></li>
+          <li><code>$👎</code>: <code>-</code></li>
+          <li><code>$📝</code>: <code>.</code></li>
+          <li><code>$🤡</code>: <code>[</code></li>
+          <li><code>$🎪</code>: <code>]</code></li>
+        </ul>
+        <p>
+          <code>,</code> (入力) に対応する関数はない
+          (このプログラムでは使わないので用意していない)。
+        </p>
+        <p>
+          なお、<code>$🐘</code> はいわゆる main 関数であり、プログラムの実行部分である。
+        </p>
+      </section>
+      <section id="q1-brainfuck--commentary--emoji-selection">
+        <h>絵文字の選択</h>
+        <p>
+          おおよそ意味に合致するよう選んでいるが、<code>$🤡</code> と <code>$🎪</code>
+          は弊社デジタルサーカスにちなんでいる。 また、<code>$🐘</code> は PHP
+          のマスコットの象に由来する。
+        </p>
+      </section>
+      <section id="q1-brainfuck--commentary--strict-types">
+        <h>strict_types</h>
+        <p>
+          <code>declare</code> 文の <code>strict_types</code> に指定できるのは、<code>0</code> か <code>1</code>
+          の数値リテラルだが、 <code>0x0</code> や <code>0b1</code> のような値も受け付ける。 今回は、PHP
+          8.1 から追加された、<code>0O</code> または <code>0o</code> から始まる八進数リテラルを使った。
+        </p>
+      </section>
+      <section id="q1-brainfuck--commentary--url">
+        <h>URL</h>
+        <p>
+          ソースコードのライセンスを示したこの部分だが、
+        </p>
+        <codeblock language="php">
+          <![CDATA[
+          https://creativecommons.org/publicdomain/zero/1.0/
+          ]]>
+        </codeblock>
+        <p>
+          完全に合法な PHP のコードである。 <code>https:</code> 部分はラベル、<code>//</code>
+          以降は行コメントになっている。
+        </p>
+      </section>
+      <section id="q1-brainfuck--commentary--numbers">
+        <h>リテラルなしで数値を生成する</h>
+        <p>
+          ソースコード中に、ほとんど数値リテラルが書かれていないことにお気づきだろうか。
+          PHP では、型変換を利用することで任意の整数を作り出すことができる。
+        </p>
+        <codeblock language="php">
+          <![CDATA[
+          assert(0 === +!![]);
+          assert(1 === +![]);
+          assert(2 === ![]+![]);
+          assert(3 === ![]+![]+![]);
+          assert(10 === +(![].+!![]));
+          ]]>
+        </codeblock>
+        <p>
+          <code>[]</code> に <code>!</code> を適用すると <code>true</code> が返ってくる。それに <code>+</code>
+          を適用すると、<code>bool</code> から <code>int</code> ヘの型変換が走り、<code>1</code> が生成される。<code>10</code>
+          はさらにトリッキーだ。まず <code>1</code> と <code>0</code> を作り、<code>.</code> で文字列として結合する
+          (<code>'10'</code>)。これに <code>+</code> を適用すると、<code>string</code> から <code>int</code>
+          への型変換が走り、<code>10</code> が生まれる (コード量に頓着しないなら、<code>1</code> を 10
+          個足し合わせてももちろん 10 が作れる)。
+        </p>
+        <p>
+          また、<code>error_reporting</code> に指定しているのは <code>-1</code> である。 これは、<code>!</code>
+          によって文字列を <code>false</code> にし、<code>+</code> によって <code>false</code> を <code>0</code>
+          にし、さらにビット反転して <code>-1</code> にしている。
+        </p>
+      </section>
+      <section id="q1-brainfuck--commentary--conditionals">
+        <h><code>if</code> 文なしで条件分岐</h>
+        <p>
+          三項演算子ないし <code>match</code> 式を使うことで、<code>if</code>
+          を一切書かずに条件分岐ができる。 また、<code>&amp;&amp;</code> / <code>||</code> も使えることがある。
+          遅延評価が不要なケースでは、<code>[$t, $f][$cond]</code>
+          のような形で分岐することもできる。
+        </p>
+      </section>
+      <section id="q1-brainfuck--commentary--loops">
+        <h><code>while</code>、<code>for</code> 文なしでループ</h>
+        <p>
+          不動点コンビネータを使って無名再帰する
+          (詳しい説明は省略する。これらの単語で検索してほしい)。 ここでは、一般に
+          Z コンビネータとして知られるものを使った (<code>$z</code>)。
+        </p>
+        <p>
+          実際のところ、<code>$🤡</code> や <code>$🎪</code>、<code>$🐘</code> は、一度 Scheme (Lisp の一種)
+          で書いてから PHP に翻訳する形で記述した。
+        </p>
+        <p>
+          なお、PHP は末尾再帰の最適化をおこなわない (少なくとも今のところは)
+          ので、 あまりに長い brainf*ck
+          プログラムを書くとスタックオーバーフローする。
+        </p>
+      </section>
+    </section>
+  </section>
+  <section id="q2-riddle">
+    <h>第2問 riddle.php</h>
+    <p>
+      ソースコードはこちら。実行には PHP 8.0 以上が必要なので注意。
+    </p>
+    <codeblock language="php">
+      <![CDATA[
+      <?php
+
+      /*********************************************************
+      * This program displays a PHPer token.                  *
+      * Guess 'N'.                                            *
+      *                                                       *
+      * Hints:                                                *
+      * - N itself has no special meaning, e.g., 42, 8128,    *
+      *   it is selected at random.                           *
+      * - Each element of $token represents a single letter.  *
+      * - One letter consists of 5x5 cells.                   *
+      * - Remember, the output is a complete PHPer token.     *
+      *                                                       *
+      * License:                                              *
+      *   https://creativecommons.org/publicdomain/zero/1.0/  *
+      *********************************************************/
+      const N = 0 /* Change it to your answer. */;
+      assert(0 <= N && N <= 0b11111_11111_11111_11111_11111);
+
+      $token = [
+      0x14B499C,
+      0x0BE34CC, 0x01C9C69,
+      0x0ECA069, 0x01C2449, 0x0FDB166, 0x01C9C69,
+      0x01C1C66, 0x0FC1C47, 0x01C1C66,
+      0x10C5858, 0x1E4E3B8, 0x1A2F2F8,
+      ];
+      foreach ($token as $x) {
+      $x = $x ^ N;
+
+      $x = sprintf('%025b', $x);
+      $x = str_replace(search: ['0', '1'], replace: [' ', '#'], subject: $x);
+      $x = implode("\n", str_split($x, length: 5));
+      echo "{$x}\n\n";
+      }
+      ]]>
+    </codeblock>
+    <p>
+      さて、この問題はさきほどのように単純に実行しただけでは、謎のブロックが表示されるだけでトークンは得られない。
+      トークンを得るためには、ソースコードを読み、定数 <code>N</code>
+      を特定する必要がある。
+    </p>
+    <p>
+      ここでは、私の想定解を解説する。
+    </p>
+    <section id="q2-riddle--code-reading">
+      <h>読解</h>
+      <p>
+        まずはソースコードを読んでいく。
+      </p>
+      <codeblock language="php">
+        <![CDATA[
+        $token = [
+        // 略
+        ];
+        ]]>
+      </codeblock>
+      <p>
+        数値からなる <code>$token</code> があり、各要素をループしている。
+      </p>
+      <codeblock language="php">
+        <![CDATA[
+        $x = $x ^ N;
+        ]]>
+      </codeblock>
+      <p>
+        まずは排他的論理和 (xor) を取り、
+      </p>
+      <codeblock language="php">
+        <![CDATA[
+        $x = sprintf('%025b', $x);
+        ]]>
+      </codeblock>
+      <p>
+        二進数に変換して、
+      </p>
+      <codeblock language="php">
+        <![CDATA[
+        $x = str_replace(search: ['0', '1'], replace: [' ', '#'], subject: $x);
+        ]]>
+      </codeblock>
+      <p>
+        0 を空白に、1 を <code>#</code> にし、
+      </p>
+      <codeblock language="php">
+        <![CDATA[
+        $x = implode("\n", str_split($x, length: 5));
+        ]]>
+      </codeblock>
+      <p>
+        5文字ごとに区切ったあと、改行で結合している。
+      </p>
+    </section>
+    <section id="q2-riddle--hint">
+      <h>ヒント</h>
+      <p>
+        次に、ソースコードに書いてあるヒントを読んでいく。
+      </p>
+      <ul>
+        <li><code>N</code> それ自体は、42 や 8128 といったような特別な意味を持たず、ランダムに決められている</li>
+        <li><code>$token</code> の各要素は、1文字を表す</li>
+        <li>1文字は 5x5 のセルからなる</li>
+        <li>出力されるのは、完全な PHPer トークンである</li>
+      </ul>
+      <p>
+        ここで、PHPer トークンは必ず <code>#</code> 記号から始まることを思いだすと、
+        <code>$token</code> の最初の数字 <code>0x14B499C</code> は、変換の結果 <code>#</code>
+        になるのではないかと予想される (なお、このことは、リポジトリの README
+        ファイルに追加ヒントとして書かれている)。
+      </p>
+    </section>
+    <section id="q2-riddle--solve">
+      <h>解く</h>
+      <p>
+        ここまでわかれば、あと一歩で解ける。すなわち、<code>0x14B499C</code> が <code>#</code>
+        に変換されるような <code>N</code> を見つければよい。
+      </p>
+      <p>
+        <code>N</code> は高々
+      </p>
+      <codeblock language="php">
+        <![CDATA[
+        assert(0 <= N && N <= 0b11111_11111_11111_11111_11111);
+        ]]>
+      </codeblock>
+      <p>
+        なのでブルートフォースしてもよいが、ここではブルートフォースしない方法を紹介する。
+      </p>
+      <codeblock language="php">
+        <![CDATA[
+        <?php
+
+        $x = 0x14B499C;
+
+        $x = $x ^ N;
+
+        $x = sprintf('%025b', $x);
+        $x = str_replace(search: ['0', '1'], replace: [' ', '#'], subject: $x);
+        $x = implode("\n", str_split($x, length: 5));
+
+        assert($x ===
+        " # # \n" .
+        "#####\n" .
+        " # # \n" .
+        "#####\n" .
+        " # # ");
+        ]]>
+      </codeblock>
+      <p>
+        この一連の変換に対する逆変換を考えると、次のようになる。
+      </p>
+      <codeblock language="php">
+        <![CDATA[
+        <?php
+
+        $x =
+        " # # \n" .
+        "#####\n" .
+        " # # \n" .
+        "#####\n" .
+        " # # ";
+
+        $x = implode('', explode("\n", $x));
+        $x = str_replace(search: [' ', '#'], replace: ['0', '1'], subject: $x);
+        $x = bindec($x);
+
+        $n = $x ^ 0x14B499C;
+
+        echo "N = $n\n";
+        ]]>
+      </codeblock>
+      <p>
+        これを実行すると、<code>N</code> が得られる。
+      </p>
+    </section>
+  </section>
+  <section id="q3-toquine">
+    <h>第3問 toquine.php</h>
+    <p>
+      ソースコードはこちら。
+    </p>
+    <codeblock language="php">
+      <![CDATA[
+      <?php
+
+      // License: https://creativecommons.org/publicdomain/zero/1.0/
+      // This is a quine-like program to generate a PHPer token.
+      // Execute it like this: php toquine.php | php | php | php | ...
+
+      $s = <<<'Q'
+      <?cuc
+      // Yvprafr: uggcf://perngvirpbzzbaf.bet/choyvpqbznva/mreb/1.0/
+      // Guvf vf n dhvar-yvxr cebtenz gb trarengr n CUCre gbxra.
+      // Rkrphgr vg yvxr guvf: cuc gbdhvar.cuc | cuc | cuc | cuc | ...
+      %f$f = %f;
+      $f = fge_ebg13($f); $kf = [
+      %f,
+      ];
+      $g = ahyy.snyfr; sbe ($v = 0; $v <= vagqvi(__YVAR__-035,6); ++$v) vs (!vffrg($kf[$v])) oernx; ryfr
+      $g .= vzcybqr("\a", fge_fcyvg(fge_ercynpr(['0','1'], ['  ','##'], fcevags(pue(37) . '025o', $kf[$v])), 012)) . "\a\a";
+      $jf = neenl_znc(sa($j) => vzcybqr(', ', $j), neenl_puhax(neenl_znc(sa($k) => fcevags('0k' . pue(37) . '07K', $k), $kf), 10));
+      cevags($f, $g, fge_ebg13("<<<'Q'\a{$f}\aQ"), vzcybqr(",\a", $jf));
+      Q;
+      $s = str_rot13($s); $xs = [
+      0x0AFABEA, 0x1F294A7, 0x1F2109F, 0x1F294A7, 0x0002800, 0x1F2109F, 0x0117041, 0x1F294A7, 0x1FAD6B5, 0x1F295B7,
+      0x010FC21, 0x1FAD6B5, 0x1151151, 0x010FC21, 0x1F294A7, 0x1F295B7, 0x1FAD6B5, 0x1F294A7, 0x1F295B7, 0x1F8C63F,
+      0x1F8C631, 0x1FAD6B5, 0x17AD6BD, 0x17AD6BD, 0x1F8C63F, 0x1F295B7,
+      ];
+      $t = null.false; for ($i = 0; $i <= intdiv(__LINE__-035,6); ++$i) if (!isset($xs[$i])) break; else
+      $t .= implode("\n", str_split(str_replace(['0','1'], ['  ','##'], sprintf(chr(37) . '025b', $xs[$i])), 012)) . "\n\n";
+      $ws = array_map(fn($w) => implode(', ', $w), array_chunk(array_map(fn($x) => sprintf('0x' . chr(37) . '07X', $x), $xs), 10));
+      printf($s, $t, str_rot13("<<<'D'\n{$s}\nD"), implode(",\n", $ws));
+      ]]>
+    </codeblock>
+    <p>
+      コメントにもあるとおり、次のようにして実行すれば答えがでてくる。
+    </p>
+    <codeblock language="shell-session">
+      <![CDATA[
+      $ php toquine.php | php | php | php | ...
+      ]]>
+    </codeblock>
+    <p>
+      実際にはもう少しパイプで繋げなければならない。
+    </p>
+    <section id="q3-toquine--commentary">
+      <h>解説</h>
+      <section id="q3-toquine--commentary--quine">
+        <h>プログラム全体</h>
+        <p>
+          コメントにもあるとおり、これは quine (風) のプログラムになっている。
+          Quine
+          とは、自分のソースコードをそっくりそのまま出力するようなプログラムのことである。
+        </p>
+        <p>
+          このプログラムは、実行すると自身とほとんど同じプログラムを出力する。
+          異なるのはトークンになっている部分のみである。
+        </p>
+      </section>
+      <section id="q3-toquine--commentary--tokens">
+        <h>トークン</h>
+        <p>
+          <code>$xs</code> がトークンに対応している。変換のロジックは <code>riddle.php</code>
+          とほぼ同じなので省略する。
+        </p>
+      </section>
+      <section id="q3-toquine--commentary--states">
+        <h>状態保持</h>
+        <p>
+          トークンの何文字目まで出力したかを、ソースコードを変えずに (quine
+          なので) 覚えておく必要がある。
+          このプログラムでは、トークンが出力されるとソースコードがだんだんと長くなっていくのを利用して、<code>__LINE__</code>
+          から情報を取得している。
+        </p>
+      </section>
+      <section id="q3-toquine--commentary--rot-13">
+        <h>ROT 13</h>
+        <p>
+          Quine は、素朴に書くとプログラムの一部が 2回記述されてしまう。
+          これがあまり美しくないので、<code>toquine.php</code> では、ROT 13
+          変換を使って難読化した。
+        </p>
+        <p>
+          それにしてもなぜこんなものが標準ライブラリに……。
+        </p>
+      </section>
+    </section>
+  </section>
+  <section id="outro">
+    <h>おわりに</h>
+    <p>
+      解いていただいたみなさん、また、難易度調整につきあっていただいた社内のみなさん、ありがとうございました。
+    </p>
+    <p>
+      今回は直前に作りはじめたのもあり、3問だけかつ使い古されたネタばかりになってしまいましたが、
+      来年は 5問、より面白い問題を持っていきます。
+    </p>
+    <p>
+      実はもう作りはじめているので、どうか来年もありますように……。
+    </p>
+  </section>
+</article>