Emacs：パターンマッチでスクレイピング

# はじめに

このエントリではスクレイピングに絡めて `pcase` を紹介します。

Emacs で大規模なクローリング & スクレイピングという話ではなく、調べものでちょっとした資料をまとめたり、マニュアル lookup 等のカスタムモードを作る時に `pcase` でスクレイピングすると楽しいなーという学びがあったのでおすそわけ。

`pcase` いいですよ。

# 必要なもの

- libxml2 をリンクした Emacs 24.x

# `pcase` 入門

リストを走査するとき、「字句どおりにマッチできたら楽なのに〜」って思いますよね。それ `pcase` で出来ます。

```
(pcase EXP &rest CASES)
```

`EXP` にマッチするパターンを `CASES` に書きます。`CASES` は `(UPATTERN CODE...)` のリストで、`UPATTERN` にマッチすると `CODE...` が評価されます。

まずは字句どおりにマッチするパターンを見てみます。

```el
(pcase '(keep "it" (simple) stupid)
  (`(keep "it" (simple) stupid)
   t))
;; ===> t
```

わーお！あまりにも自然すぎて便利さが伝わらないかも知れませんが、バッククォートで始まるパターンでは、アトム、文字列、コンスセルがそのままマッチします。

「マッチと同時に値を取り出せないの？」もちろん、できますとも。

```el
(pcase '(The Whole Earth Catalog)
  (`(The Whole Earth ,what)
   what))
;; ===> Catalog
```

バッククォートパターンの中で、カンマに続けてシンボルを置くと、その位置で捕捉された値（この場合は `Catalog`）がシンボルに束縛されます。

もう少し複雑なリストでもやってみます。

```el
(pcase '(p nil
           "paragraph"
           (a ((href . "foo.html")
               (rel . "bookmark"))
              "link text"))
  (`(p nil
       "paragraph"
       (a ((href . ,url)
           (rel . "bookmark"))
          ,text))
   (cons text url)))
;; ===> ("link text" . "foo.html")
```

結構深い位置にある要素も、パターンマッチを使うと簡単に抜き出せることがわかります。便利ですねー。

パターンは記述した順に評価され、マッチしたパターンより後は評価されません。

```el
(pcase '(a b c)
  (`(a b c)
   'first)
  (`(a b c)
   'second)
  (`(a b c)
   'third))
;; ===> first
```

どのパターンにもマッチしない場合には `nil` が返されます。

```el
(pcase '(a b c)
  (`(x y z)
   t))
;; ===> nil
```

何にでもマッチするフォールバックパターンには `,_` が使えます。

```el
(pcase '(a b c)
  (`(a ,_ ,_)
   t))
;; ===> t
```

リストにマッチするパターンがどういったものか、これでおおよそ理解できたかと思います。でも、これだけでは不十分ですね。条件分岐や、込み入った変数束縛もできないと。

他にはどんなパターンを書けるのか、`pcase` のドキュメントで確認してみます。

```
pcase is an autoloaded Lisp macro in `pcase.el'.

(pcase EXP &rest CASES)

Perform ML-style pattern matching on EXP.
CASES is a list of elements of the form (UPATTERN CODE...).

UPatterns can take the following forms:
  _             matches anything.
  SELFQUOTING   matches itself.  This includes keywords, numbers, and strings.
  SYMBOL        matches anything and binds it to SYMBOL.
  (or UPAT...)  matches if any of the patterns matches.
  (and UPAT...) matches if all the patterns match.
  `QPAT         matches if the QPattern QPAT matches.
  (pred PRED)   matches if PRED applied to the object returns non-nil.
  (guard BOOLEXP)       matches if BOOLEXP evaluates to non-nil.
  (let UPAT EXP)        matches if EXP matches UPAT.
If a SYMBOL is used twice in the same pattern (i.e. the pattern is
"non-linear"), then the second occurrence is turned into an `eq'uality test.

QPatterns can take the following forms:
  (QPAT1 . QPAT2)       matches if QPAT1 matches the car and QPAT2 the cdr.
  ,UPAT                 matches if the UPattern UPAT matches.
  STRING                matches if the object is `equal' to STRING.
  ATOM                  matches if the object is `eq' to ATOM.
QPatterns for vectors are not implemented yet.

PRED can take the form
  FUNCTION           in which case it gets called with one argument.
  (FUN ARG1 .. ARGN) in which case it gets called with an N+1'th argument
                        which is the value being matched.
A PRED of the form FUNCTION is equivalent to one of the form (FUNCTION).
PRED patterns can refer to variables bound earlier in the pattern.
E.g. you can match pairs where the cdr is larger than the car with a pattern
like `(,a . ,(pred (< a))) or, with more checks:
`(,(and a (pred numberp)) . ,(and (pred numberp) (pred (< a))))
```

どうやら、`UPatterns` と `QPatterns` の二種類のパターンがあるようです。以下、少し詳しく見ていきますが、上記内容を噛み砕いているだけなので、不要なら読み飛ばしてください。

## `UPatterns`

`UPatterns` には何にでもマッチする `_`、即値、シンボル（変数束縛）、組み込み関数、そしてバッククォートで始まる `QPattern` を記述できます。

### フォールバックパターン

何にでもマッチするパターンには `_` を使います。

```el
(pcase '(a b c)
  (`(x y z) 'xyz)
  (`(1 2 3) '123)
  (_ 'fallback))
;; ===> fallback
```

### 即値

即値として許されるのは、数値、文字列、キーワードだけです。

```el
(pcase 1225
  (0 nil)
  (1225 t))
;; ===> t

(pcase "happy"
  ("Christmas" nil)
  ("happy" t))
;; ===> t

(pcase :white
  (:Christmas nil)
  (:white t))
;; ===> t
```

### 変数束縛

裸のシンボルは、捕捉した値を束縛します。

```el
(pcase 'qiita
  (var1 var1)
  (var2 var2))
;; ===> qiita
```

変数束縛は常に `non-nil` を返します。よって上記は `var1` が評価されます。

### 組み込み関数

`(pred FUNC)` は叙述関数で、`FUNC` の引数として捕捉した値（ここでは `'atom`）を適用して評価します。

```el
(pcase 'atom
  ((pred numberp)
   'number)
  ((pred stringp)
   'string)
  ((pred symbolp)
   'symbol))
;; ===> symbol
```

`(and UPAT...)` は `UPAT` が全て `non-nil` ならマッチとみなします。

```el
(pcase 1224
  ((and (pred (< 1201))
        (pred (> 1231)))
   t))
;; ===> t
```

`pred` の引数を `(FUNC ARG1 .. ARGN)` のように括弧でくくると、複数引数の関数も呼び出せるようになります。捕捉した値（ここでは `1224`）が最後の引数として適用されるのは同じです。

`(or UPAT...)` は `UPAT` のいずれかが `non-nil` ならマッチとみなします。

```el
(pcase "qiita"
  ((or (pred symbolp)
       (pred stringp))
   t))
;; ===> t
```

残りの `(guard ...)` と `(let ...)` については、おいおい見ていくことにします。

### `QPatterns`

`QPatterns` には字句どおりマッチするアトム、文字列、コンスセルの他、カンマに続けて `UPattern` を記述できます。ところで、`UPatterns` にも、バッククォートで始まる `QPattern` を書くことができました。

ということはつまり、両者は相互再帰的に記述可能ということです。

```el
(pcase '(ul nil
            (li ((class . "menu"))
                (button ((class . "bookmark"))
                        "button text")))
  (`(ul ,_
        (li ((class . "menu"))
            ,(or `(a ,(pred (member '(rel . "bookmark")))
                     ,text)
                 `(button ((class . "bookmark"))
                          ,text))))
   text))
;; ===> "button text"
```

最初のほうで見た、バッククォート中のフォールバックパターン `,_` や変数束縛 `,url` なども、結局のところ、`QPattern` から `UPattern` への一時的なスイッチにすぎなかったわけです。

# 補足：捕捉とマッチについて

何度か捕捉という言葉が出てきていますが、このエントリでは次の意味で使っています。

- 捕捉：パターンに適用するオブジェクトを式から取り出すこと
- マッチ：捕捉したオブジェクトをパターンに適用すること

例として、以下の式を順を追って見ていきます。

```el
(pcase '(a (b c) "string")
  (`(a ,(pred listp) ,text)
   text))
;; ===> "string"
```

1. `EXP` から `'(a (b c) "string")` を捕捉する（以降、`object` と呼ぶ）
2. 最初のパターンを取り出す（以降、`pattern` と呼ぶ）
3. `object` から `a` を捕捉し、`pattern` の `a` と比較 → マッチ成功
4. `object` から `(b c)` を捕捉し、`pattern` の `,(pred listp)` に適用 → マッチ成功
5. `object` から `"string"` を捕捉し `pattern` の `,text` に適用 → 束縛 & マッチ成功
6. `object` が `pattern` 全体にマッチしたので、`text` を評価 → `"string"`

捕捉したからといって、常にマッチに成功するわけではありません。念の為。

# スクレイピング用のテンプレート

続いて後半です。スクレイピングの実装に入ります。

まずは、最低限の処理だけ実装したテンプレートです。

```el
(defun your-retrieve-function (url func buffer-name)
  (let ((callback
         `(lambda (status)
            (when status
              (error "%S" status))
            (let ((dom (mm-with-part (mm-dissect-buffer 'no-strict-mime)
                         (libxml-parse-html-region (point-min)
                                                   (point-max))))
                  (buffer (get-buffer-create ,buffer-name))
                  (standard-output (get-buffer ,buffer-name)))
              (with-current-buffer buffer
                (erase-buffer)
                (prin1 (,func dom))
                (message "`%s' done" ',func))))))
    (url-retrieve url callback)))
```

`url-retrieve` は非同期なのですぐに制御を戻します。コールバック関数 `callback` は、一時バッファに応答結果（HTTPヘッダー込み）が展開された状態で呼び出されます。

この内容を `mm-dissect-buffer` で解析し、`mm-with-part` で HTML を抜き出し、`libxml-parse-html-region` で DOM に変換します。`func` 引数はスクレイピング用の関数で、この戻り値を `buffer-name` バッファに挿入します。とりあえずのテンプレートなので、カスタマイズはお好きなように。

次は `func` に渡す DOM の中身を調べてみます。

# DOM の構造

`libxml-parse-html-region` が返すリスト形式は `(TAG ATTR-ALIST CHILDREN)` です。例えば、以下のような HTML があった場合

```html
<div class="article">
  <h1>title</h1>
  <p>paragraph
    <a href="foo.html" class="bar">link text</a>
    <!-- comment -->
    some text
    
    end of paragraph
    <br/>
  </p>
</div>
```

次のリストが返されます。

```el
(html nil
      (body nil
            (div
             ((class . "article"))
             "\n  "
             (h1 nil "title")
             "\n  "
             (p nil "paragraph\n    "
                (a
                 ((href . "foo.html")
                  (class . "bar"))
                 "link text")
                "\n    "
                (comment nil " comment ")
                "\n    some text\n    \n    end of paragraph\n  ")
                (br nil))
             "\n")))
```

`html` や `body` など、最低限必要な要素は自動的に補われてます。また、`ATTR-ALIST` がない場合でも明示的に `nil` が置かれます。`CHILDREN` 部は長さ 0 以上のリストで、その要素はアトムかリストです。

HTML が普通にリスト化されてますね。

ところで、見るからに邪魔なのが `"\n  "` などの文字列。パターンマッチさせることを考えると、あらかじめ除去しておきたいところ。

# DOM のサニタイズ

さて、どうやってゴミを除去したものか。

ゴミと思しき文字列は空白や改行ですが、これはゴミ以外の文字列にも出現します。なので、ゴミにマッチしない正規表現を書いてみます。

```el
(string-match-p "[[:graph:]]" "\n  ")
;; ===> nil
(string-match-p "[[:graph:]]" "\n    some text\n    \n    end of paragraph\n  ")
;; ===> 5
```

オーケー。これを反転させればゴミを識別できます。あとはリスト走査を付け加えれば、サニタイズ関数の出来上がり。

```el
(defun your-sanitize-function (dom &optional result)
  (push (nreverse
         (cl-reduce (lambda (acc object)
                      (cond
                       ((and (stringp object)
                             (not (string-match-p "[[:graph:]]" object)))
                        acc)
                       ((or (atom object)
                            (consp (car object)))
                        (cons object acc))
                       (t
                        (your-sanitize-function object acc))))
                    dom :initial-value nil))
        result))
```

`cl-reduce` で `dom` を走査し、リスト要素を調べていきます。

ゴミを見つけた場合には、それまでの結果を蓄えたリストである `acc` を返します。アトムか連想リストなら、要素をそのまま `cons` します。残りはリストなので再帰します。

要素はリストの先頭に追加していくので、最後に `nreverse` で元の並びに戻します。

これを先ほどのテンプレートと組み合わせると次の通り。

```el
(your-retrieve-function "http://your.url"
                        (lambda (dom)
                          (your-extract-function
                           (your-sanitize-function dom)))
                        "your buffer")
```

よーやく形が見えてきました。あとは `your-extract-function` を実装するだけ。

# 実践：パターンマッチ

長らくお待たせしました。いよいよパターンマッチで抜き出します。`cl-reduce` を使うとこんな感じ。

```el
(defun your-extract-function (dom &optional result)
  (nreverse
   (cl-reduce (lambda (acc object)
                (pcase object
                  ;; マッチさせたいパターンを最初に書く
                  ;; 例）とにかくリンクを抜き出す場合
                  ;; (`(a ,_ ,_)
                  ;;  (cons object acc))
                  ((or (pred atom)
                       (guard (consp (car object))))
                   acc)
                  (_
                   (your-extract-function object acc))))
              dom :initial-value result)))
```

サニタイズ関数と似ていますが、パターンにマッチしたものだけを `cons` していくので、結果は平坦なリストになります。

`((or ...` の部分は、サニタイズ関数にもあったアトムと連想リストの判定です。このパターンにマッチしたということは即ち不要な要素（再帰も不要）なので、`cons` せずに `acc` を返します。

`(guard BOOLEXP)` は `BOOLEXP` を評価します。`(pred FUNC)` とは異なり、捕捉した値は引数に適用されません。冗長ですが、汎用的とも言えます。

最後に、フォールバックパターンで再帰します。あとは好きなようにいじってテストしていけば、感じが掴めるはず。

## 例1：テーブルからリンクを抜き出す

テーブル形式の一覧からリンクを抜き出したいとします。抜き出したい部分はこんな感じです（ちなみに、ネタは [Go のパッケージ一覧](https://golang.org/pkg/)）。

```html
<tr>
  <td class="pkg-name" style="padding-left: 20px;">
    <a href="archive/tar/">tar</a>
  </td>
  <td class="pkg-synopsis">
    Package tar implements access to tar archives.
  </td>
</tr>
```

ところでよく見ると、次のように `"pkg-synopsis"` が空っぽのものもチラホラあります。

```html
<tr>
  <td class="pkg-name" style="padding-left: 0px;">
    <a href="archive/">archive</a>
  </td>
  <td class="pkg-synopsis">

  </td>
</tr>
```

これはディレクトリ用のリンクであり、パッケージそのものではないので、無視することにします。また、テーブルに含まれていないリンクもいくつか発見しましたが、これらも当然、対象外となります。

よって仕様としては『テーブルに含まれていて、かつ、"pkg-synopsis" が空っぽじゃないリンクを抜き出す』になります。言葉で書くと簡単ですが、いざ実装しようと思うといかにも面倒臭そうですね。。。

でも `pcase` を使えばご覧の通り。仕様と実装の隔たりを、ほとんどゼロと言えるくらいにまで縮めることができます。

```el
(pcase object
  (`(tr ,_
        (td ,_
            (a ((href . ,href)) ,text))
        (td ((class . "pkg-synopsis"))
            ,(pred stringp)))
   (cons (cons text href) acc))
  ...
```

若干補足すると、サニタイズ済みなので `,(pred stringp)` の部分は `,_` でも良いのですが、『文字列が置かれていること』という意図を強調するために `pred` を使っています。このへんは好みですね。

## 例2：可変パターン

固定のパターンにマッチさせるのは確かに簡単です。でも可変の場合はどうか？

基本的には、コンスセルとしてマッチさせることになります。

```el
(pcase '(1 2 3)
  (`(,_ . ,rest)
   rest))
;; ===> (2 3)
```

同様に、`CHILDREN` 部だけ束縛したいケースは `(a b c) == (a . (b . c))` なので、

```el
(pcase '(p nil
           "paragraph"
           (br nil)
           (a ((href . "abc")) "text"))
  (`(p . (,_ . ,children))
   children))
;; ===> ("paragraph" (br nil) (a ((href . "abc")) "text"))
```

ですね。

類似した例で、属性リストが可変だったり、パターンの出現位置を事前に固定できない場合もあります。そんな時でも、

```el
(pcase '(a ((href . "foo.html")
            (rel . "bookmark"))
           "link text")
  (`(a ,(pred (member '(rel . "bookmark")))
       ,text)
   text))
;; ===> "link text"
```

と堅牢に書くことができます。

## 例3：一時変数

もしパターンの中で込み入った変数束縛が必要なら `let` が使えます。`let` は常に `non-nil` と評価されます（`nil` を束縛した場合でも）。

```el
(pcase '(a ((href . "foo.html")
            (rel . "bookmark"))
           "link text")
  (`(a ,(and attr
             (pred (member '(rel . "bookmark")))
             (let href (cdr (assq 'href attr))))
       ,text)
   (cons text href)))
;; ===> ("link text" . "foo.html")
```

この例では、`(rel . "bookmark")` が現れるリンクの `href` を抜き出しています。老婆心ながら、`(and attr...` の `attr` は変数束縛です。その値は、この位置で捕捉した連想リストになります。

## 例4：否定

`pcase` のドキュメントには記述がありませんが、Emacs 24.5 に付属の `pcase` では組み込みの `(not OBJECT)` として扱われるようです。

```el
(pcase 'abc
  ((not stringp)
   'not-string)
  ((not atom)
   'not-atom)
  (_
   'unknown))
;; ===> unknown

(pcase 'abc
  ((not (pred stringp))
   'not-string)
  ((not (pred atom))
   'not-atom)
  (_
   'unknown))
;; ===> not-string
```

## 番外編：init.el で使う

[elisp初心者がelispを触るとdolistを使いたがる](http://qiita.com/j8takagi/items/50afc3a5f2fdc0f1c0a0) を見てたらどうにもムズムズしてしまったので、`pcase` を使って書いてみました。

```el
(let ((mode-specific-keybind-list
       '(("text-mode" text-mode-hook text-mode-map
          (("C-M-i" dabbrev-expand)))
         ("tex-mode" latex-mode-hook latex-mode-map
          (("<M-return>" latex-insert-item)
           ("C-c p p" exopen-buffer-pdffile)
           ("C-c p d" exopen-buffer-dvifile)
           ("C-c C-c" comment-region)))
         ("lisp-mode" emacs-lisp-mode-hook lisp-mode-shared-map
          (("<M-return>" completion-at-point)))
         ("mediawiki" mediawiki-mode-hook mediawiki-mode-map
          (("C-x C-s" save-buffer))))))
  (dolist (config mode-specific-keybind-list)
    (pcase config
      (`(,lib ,hook ,map
              ,keybind-list)
       (let ((func-init-keybind
              (intern (format "my-init-%s-keybind" map))))
         (with-eval-after-load lib
           (fset func-init-keybind
                 `(lambda ()
                    (dolist (keybind ',keybind-list)
                      (pcase keybind
                        (`(,key ,(and (pred functionp)
                                      func))
                         (define-key ,map (kbd key) func))
                        (`(,_ ,func)
                         (message "Warning: in setting %s, function `%s' is not defined."
                                  ',map func))))))
           `(add-hook ',hook ',func-init-keybind)))))))
```

こんな書き方もあるんだなーということで参考にしてもらえれば。

# おわり

長々とお付き合いいただき、ありがとうございました。

`pcase` だけに絞ったエントリのほうが良かったかもと思いつつ、つい欲張ってモリモリ書いてしまいました。わかりずらいところなどあれば加筆しますので、ご指摘下さい。スクレイピングに限らずいろんなところで活用できそうな `pcase` の楽しさ・便利さを少しでも共有できたらなと。

たぶん来年は「それ、`pcase` で書けるよ」という、かわいがりエントリが盛大に流行る予定なので、今から準備しておくときっといいことあります（嘘です）。

それでは皆様、良いお年を！