LoginSignup
162
158

More than 5 years have passed since last update.

@kawasima(Yoshitaka Kawashima)

プログラミングの学び方

Last updated at Posted at 2016-02-26

(学生や新入社員に「プログラミング、どうやって勉強したらよいのですか?」とよく聞かれるので書いてみました)

サッカーのことは詳しく知りませんが、モウリーニョのいうところの「サッカーを上達するにはサッカーの練習をしなければいけない」は、プログラミング学習者にも当てはまるところが大きくあると思います。

独学でプログラミングを学ぼうとすると、本を読んでExampleを動かしてみたり、チュートリアルを実践してみたりすることが多いかと思いますが、なかなか身につかず途中で挫折することがよくあります。また、それでいざ業務で使えるものを作ろうとしても、なかなか手が動かないなんてこともよくあります。

私がよくやるのは、自分が学ぼうとする言語/フレームワークとは、別のもので実装された機能を移植してみる、というものです。

などなど。

このやり方を薦めていらしゃる方もいます。

佐藤太一さんのデブサミ2016の資料

他の言語では盛り上がってるけど、得意な言語には無いものを再実装しよう

中島聡さんの「車輪の再発明」の価値

フレームワークを使うのもよいが，やみくもに使うのではなく，一度ソースコードを読みこなしたうえで，必要であればよりコンパクトなものを再実装するぐらいの気概で取り組むのがよいと私は思う。必要に応じて車輪の再発明はすべきだし，それによって学べることはたくさんある。

"車輪の再発明"は「何をテーマにプログラム書いたらいいか分からない」という勉強したい気持ちがあるが最初の一歩を踏み出せない人にとってとても有効だと思っています。

その過程で得られるものを実例をもとにご紹介します。

例: マルチパートの処理

Javaで新しいWebのフレームワークを作りたいと思ったわけですが、マルチパートの処理のところで手が止まりました。Spring MVCやClojure ringをみると、Commons Fileuploadに処理をディスパッチしています。が、役割を終えた感のあるCommonsには依存したくない気持ちがあり、自前で実装したいと思ったわけです。

そこで他の言語/フレームワークを見てみます。ここではCommons Fileupload以外で十分実績のありそうな、RubyのRackに注目し、そのMultipartの処理を参考にJavaで再実装することにしました。

Multipartについてザッと学ぶ

まず、実際にどういうリクエストをパースすればよいのか。テストデータが豊富にあるので、これを読みます。

--AaB03x
Content-Disposition: form-data; name="submit-name"

Larry
--AaB03x
Content-Disposition: form-data; name="submit-name-with-content"
Content-Type: text/plain

Berry
--AaB03x
Content-Disposition: form-data; name="files"; filename="file1.txt"
Content-Type: text/plain

contents
--AaB03x--

ふむふむ、--AaB03xを区切り文字として、ヘッダとボディが繰り返されるのだな、ということがわかります。

ここで、RFCも読みます。

Rackのソースを読み、Javaで書く

そしてRackの該当ソースを読みます。

    EOL = "\r\n"
    MULTIPART_BOUNDARY = "AaB03x"
    MULTIPART = %r|\Amultipart/.*boundary=\"?([^\";,]+)\"?|ni
    TOKEN = /[^\s()<>,;:\\"\/\[\]?=]+/
    CONDISP = /Content-Disposition:\s*#{TOKEN}\s*/i
    VALUE = /"(?:\\"|[^"])*"|#{TOKEN}/
    BROKEN_QUOTED = /^#{CONDISP}.*;\sfilename="(.*?)"(?:\s*$|\s*;\s*#{TOKEN}=)/i
    BROKEN_UNQUOTED = /^#{CONDISP}.*;\sfilename=(#{TOKEN})/i
    MULTIPART_CONTENT_TYPE = /Content-Type: (.*)#{EOL}/ni
    MULTIPART_CONTENT_DISPOSITION = /Content-Disposition:.*\s+name=(#{VALUE})/ni
    MULTIPART_CONTENT_ID = /Content-ID:\s*([^#{EOL}]*)/ni
    # Updated definitions from RFC 2231
    ATTRIBUTE_CHAR = %r{[^ \t\v\n\r)(><@,;:\\"/\[\]?='*%]}
    ATTRIBUTE = /#{ATTRIBUTE_CHAR}+/
    SECTION = /\*[0-9]+/
    REGULAR_PARAMETER_NAME = /#{ATTRIBUTE}#{SECTION}?/
    REGULAR_PARAMETER = /(#{REGULAR_PARAMETER_NAME})=(#{VALUE})/
    EXTENDED_OTHER_NAME = /#{ATTRIBUTE}\*[1-9][0-9]*\*/
    EXTENDED_OTHER_VALUE = /%[0-9a-fA-F]{2}|#{ATTRIBUTE_CHAR}/
    EXTENDED_OTHER_PARAMETER = /(#{EXTENDED_OTHER_NAME})=(#{EXTENDED_OTHER_VALUE}*)/
    EXTENDED_INITIAL_NAME = /#{ATTRIBUTE}(?:\*0)?\*/
    EXTENDED_INITIAL_VALUE = /[a-zA-Z0-9\-]*'[a-zA-Z0-9\-]*'#{EXTENDED_OTHER_VALUE}*/
    EXTENDED_INITIAL_PARAMETER = /(#{EXTENDED_INITIAL_NAME})=(#{EXTENDED_INITIAL_VALUE})/
    EXTENDED_PARAMETER = /#{EXTENDED_INITIAL_PARAMETER}|#{EXTENDED_OTHER_PARAMETER}/
    DISPPARM = /;\s*(?:#{REGULAR_PARAMETER}|#{EXTENDED_PARAMETER})\s*/
    RFC2183 = /^#{CONDISP}(#{DISPPARM})+$/i

大量の正規表現が定義されていますが、これはrfc2183で定められているBNFを実装したものに過ぎません。見比べながら概要を把握します。

Rackのマルチパートのパースは、以下のように状態を切り替えながら、ヘッダやフッタを処理していきます。このあたりはJavaでも同じように書けるので、そのまま移植していきます。

parser.rb
      def run_parser
        loop do
          case @state
          when :FAST_FORWARD
            break if handle_fast_forward == :want_read
          when :CONSUME_TOKEN
            break if handle_consume_token == :want_read
          when :MIME_HEAD
            break if handle_mime_head == :want_read
          when :MIME_BODY
            break if handle_mime_body == :want_read
          when :DONE
            break
          end
        end
      end

Javaで実装するとこんな感じ

    private void runParser() throws IOException {
        while (true) {
            switch (state) {
                case FAST_FORWARD:
                    if (handleFastForward()) return;
                    break;
                case CONSUME_TOKEN:
                    if (handleConsumeToken()) return;
                    break;
                case MIME_HEAD:
                    if (handleMimeHead()) return;
                    break;
                case MIME_BODY:
                    if (handleMimeBody()) return;
                    break;
                case DONE:
                    return;
            }
        }
    }

リクエストボディをストリームで読みながらパースするわけですが、Rackではバイト列でもStringで扱っています。

これは流石にJavaではそのまま実装しない方が良さそうなので、ByteBufferを使うことにします。ByteBufferガッツリ使ったことは無かったのですが、我々にはhishidamaメモがあるので安心です。

Javaバッファークラスメモ(Hishidama's Java Buffer Memo)。

そうすると、Rubyですっきり書けていた正規表現のマッチングによるマルチパートバウンダリーの探索は、バイト配列探索に書き直す必要が出てきます。

    def handle_mime_body
        if @buf =~ rx   # rx = /(?:#{EOL})?#{Regexp.quote(@boundary)}(#{EOL}|--)/n
          # Save the rest.
          if i = @buf.index(rx)
            @collector.on_mime_body @mime_index, @buf.slice!(0, i)
            @buf.slice!(0, 2) # Remove \r\n after the content
          end
          @state = :CONSUME_TOKEN
          @mime_index += 1
        else
          :want_read
        end
      end

バイト配列のから特定のバイト配列を探索するのはどうやるのが効率的なのでしょうか。
ググるとKnuth先生のKnuth-Morris-Pratt法が古典的で定石のようです。

こういう著名なアルゴリズムは、Wikipediaに擬似コードが載っているので、まず実装してみてデバッガなどで動きをみながら理解するのもよいかと思います。

疑問点をみつけて改善する

また、バウンダリーが見つからないときは、またストリームからデータを読み込むわけですが、そこの処理を書こうとすると、またつまずきます。

      def on_read content, eof
        handle_empty_content!(content, eof)
        @buf << content
        run_parser
      end

bufはString型ですが、バウンダリーが見つかるまでどんどんStringに加えていきます。このコードを見る限り、1GBのファイルをアップロードすると1GB分メモリに蓄えそうです(ホントに?)。さらに上で引用したhandle_mime_bodyを見ると毎回その大きなバッファに対してバウンダリーのマッチングを先頭から走らせるので、重そうです…(ホントに?) 1
今回のJavaの実装では、固定サイズのByteBufferを使っているので、バッファサイズを越えて読み込むことができません。そこで、ここのコードは、一度Tempfileに書き込んでバッファをクリアし、また読み込むことにします。

そうこうして、RackのマルチパートパーサがJavaで一通り動きます。

移植に際しては、元のロジックを完全に理解しようとしなくてもよいかと思います。まず書いてみて、次に示すようにテストも移植するので、そこで発生するエラーの修正で、必然的に中身の理解はすることになるからです。

テストケースを移植する

移植対象とするソフトウェアは、十分なテストケースがあるものの方が学びが多くなります。

% curl https://raw.githubusercontent.com/rack/rack/1.6.4/test/spec_multipart.rb | grep "should \"" | perl -pe 's/.*\"([^\"]*)\".*/$1/'
return nil if content type is not multipart
parse multipart content when content type present but filename is not
set US_ASCII encoding based on charset
set BINARY encoding on things without content type
set UTF8 encoding on names of things without content type
default text to UTF8
raise RangeError if the key space is exhausted
parse multipart form webkit style
reject insanely long boundaries
parse multipart upload with text file
preserve extension in the created tempfile
parse multipart upload with text file with no name field
parse multipart upload file using custom tempfile class
parse multipart upload with nested parameters
parse multipart upload with binary file
parse multipart upload with empty file
parse multipart upload with filename with semicolons
parse multipart upload with filename with invalid characters
not include file params if no file was selected
parse multipart/mixed
parse multipart/mixed
parse IE multipart upload and clean up filename
parse filename and modification param
parse filename with escaped quotes
parse filename with percent escaped quotes
parse filename with unescaped quotes
parse filename with escaped quotes and modification param
parse filename with unescaped percentage characters
parse filename with unescaped percentage characters that look like partial hex escapes
parse filename with unescaped percentage characters that look like partial hex escapes
not reach a multi-part limit
reach a multipart limit
return nil if no UploadedFiles were used
raise ArgumentError if params is not a Hash
parse multipart upload with no content-length header
parse very long unquoted multipart file names
support mixed case metadata

上記のとおり、結構なボリュームのケースがRackには備わっているので、これを移植するだけでもテストの書き方と、十分なテスト量を得ることができます。

得られたもの

そんなこんなで、移植が完成すると、新しいJavaのマルチパート実装だけでなく、

  • Rackのマルチパートの処理内容と、「これは?」というところの処理
  • ByteBufferの使い方
  • Knuth-Morris-Pratt アルゴリズム
  • マルチパートのテストケースパターン

などに関する知識も併せて獲得でき、学び多いプログラミングができます。

まとめ

プログラミングが上手くなるためには、できるだけ実践に近い形でプログラミングすること。そのためには車輪の再発明も良いのではないでしょうか。

  1. Rubyの詳しい人に見てもらったところ確かにそのとおりとのこと。Rack1.xではそんなことはなく、2系で書き直したときに入り込んだ問題ではないかと。気が向いたらIssue起票します。 ↩

162
158
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
162
158