スヌー君式の正しいHTML解析の作法

まえふり

HTML解析について、オープンソースのプロジェクトやネット上のドキュメントなどを見ててなんか言いたいことがあったので、ここに書く。半分はボヤキに近い。

ハナシの前提条件

ここでは「正しいこと」を書くのだけれど、世間一般で正しい事ではなく、あくまでも「スヌー君の流儀の中において正しいこと」である。なお、スヌー君に追従しても一円の特にもならないのだけれども、古いHTMLエディターで書かれた規格違反バリバリの文書や、世界レベルのポルノ中毒者の集う怪しい名門サイトの変なページでもソコソコ解析できるスクリプトが書けるというご利益はあるんだよ。

具体的な作法

シラブル分け

シラブル分けに通常の正規表現ライブラリを使用してはいけない。例えば、IMGタグにMIMEが埋め込まれていたら、タグ一つで数百メガバイトなんてこともありうる。汎用の正規表現エンジンの動作は細かすぎ、重すぎ、脆すぎる。

正しくは自前のNFAを使って行う。面識の有る無しを問わずにサナエトークンを取り出すんだよ木下さん。

この処理が終わってしまえば、この後の段階で汎用の正規表現ライブラリを使っても大丈夫になるはず。

パース

普通のパーサーを使うという事を考えてはいけない。「対象の構造は全体的に壊れている」という前提に立たないといけない。だから、XMLパーサーをベースにHTMLの解析プログラムを書こうなどという考えは現実の壁に当たって砕かれることになる。

正しくは、最初に全ての文書を読み込んで全てのタグのインデクスを作り、ファーストインラストアウトでペアを構成しうる要素の関連付けを行う。関連付けをしやすくデータ構造を工夫する。

そして、この索引を利用したイテレーターを作る。例えばこんな風に。

between('div', 'name', 'article') { |s, e| ... }
single('img', 'name', /^figure.*$/) { |n| ... }

こうやって、大丈夫そうな断片を引っ張り出して、必要に応じてそのブロック内に再びイテレーターを適用することによって入れ子構造を追跡する。

コード

作例として、スヌー君流のHTMLパーサーを掲載する。言語はRuby(2.3～3.4までは確認)、ライセンスはGPLv1。

class Htmltoken < Struct.new(:token, :map)
  @@s_txt = 0
  @@s_tag = 1
  @@s_rem = 2
  @@s_tagchk = 3
  @@s_quote = 4
  @@s_remchk1 = 5
  @@s_remchk2 = 6
  @@s_remend1 = 7
  @@s_remend2 = 8
  @@cache = Hash.new(nil)
  def initialize(s = '')
    load_string(s)
  end
  def load_string(s)
    reset
    s.split('').each { |c| fetch(c) }
    close
    return check
  end
  def reset
    self.token = []
    self.map = Hash.new(nil)
    @buff = ''
    @stt = @@s_txt
  end
  def isspace(c)
    case c
    when ' ', "\r", "\n", "\t"
      return true
    end
    return false
  end
  protected :isspace
  def tospace(c)
    return isspace(c) ? ' ' : c
  end
  protected :tospace
  def istag(i)
    return nil if self.token[i].size < 2
    return nil if self.token[i][0, 1] != '<'
    return nil if self.token[i][-1, 1] != '>'
    return nil if (self.token[i].size > 3) && (self.token[i][1, 1] == '!')
    return true
  end
  def iscomment(i)
    return nil if self.token[i].size < 7
    return nil if self.token[i][0, 4] != '<!--'
    return nil if self.token[i][-3, 3] != '-->'
    return true
  end
  def istext(i)
    return true if self.token[i].size < 2
    return nil if self.token[i][0, 1] == '<'
    return nil if self.token[i][-1, 1] == '>'
    return true
  end
  def tagmatch(pttn, val)
    if (pttn.class == Regexp) && (val.class == String) then
      return pttn =~ val if val.class == String
      return nil
    elsif (pttn.class == String) && (val.class == String) then
      return pttn.downcase == val.downcase if val.class == String
      return nil
    elsif pttn.class == TrueClass then
      return val.class == TrueClass
    end
    return nil
  end
  protected :tagmatch
  def fetch(c)
    case @stt
    when @@s_txt
      if c == '<' then
        self.token.push @buff if @buff.size > 0
        @buff = c
        @stt = @@s_tagchk
      else
        @buff = @buff + c
      end
    when @@s_tagchk
      c = tospace(c)
      @buff = @buff + c if c != ' '
      if c == '>' then
        self.token.push @buff
        @buff = ''
        @stt = @@s_txt
      elsif c == '!'
        @stt = @@s_remchk1
      else
        @buff = @buff.downcase
        @stt = @@s_tag
      end
    when @@s_tag
      c = tospace(c)
      if (c == ' ') && (@buff.size == 1) then
        # <直後の空白は無視
      elsif (c == ' ') && (@buff[-1, 1] == ' ') then
        # タグ内の連続した空白は一つの空白に
      elsif c == '>' then
        if @buff[-1, 1] == ' ' then # >直前の空白は削除
          @buff = @buff.slice(0, @buff.size - 1)
        end
        if (@buff.size > 2) \
         && (@buff[-1, 1] == '/') && (@buff[-1, 1] == ' ') then
          @buff = @buff.slice(0, @buff.size - 2) + '/' # />直前の空白カット
        end
        @buff = @buff + '>'
        # begin mapping
        ts = fetchtagname(@buff)
        if ts[0, 1] != '/' then # begin-tag
          if ts[-1, 1] == '/' # ended
            ks = ts.slice(0, ts.size - 1)
            self.map[ks] = [] if not self.map[ks]
            #self.map[ks].push [self.token.size, self.token.size]
            self.map[ks].push [self.token.size, nil]
          else
            self.map[ts] = [] if not self.map[ts]
            self.map[ts].push [self.token.size, nil]
          end
        else # end-tag
          ks = ts.slice(1, ts.size - 1)
          if self.map[ks] then
            (self.map[ks].size - 1).downto(0) { |i|
              if not self.map[ks][i][1] then
                self.map[ks][i][1] = self.token.size
                break
              end
            }
          else # pair unmatch
          end
        end
        # end mapping
        self.token.push @buff
        @buff = ''
        @stt = @@s_txt
      elsif c == '"' then
        @buff = @buff + c
        @stt = @@s_quote
      else
        @buff = @buff + c.downcase
      end
    when @@s_quote
      @buff = @buff + c
      @stt = @@s_tag if c == '"'
    when @@s_remchk1
      @buff = @buff + c
      if c == '-' then
        @stt = @@s_remchk2 
      else
        @buff = @buff.downcase
        @stt = @@s_tag
      end
    when @@s_remchk2
      @buff = @buff + c
      if c == '-' then
        @stt = @@s_rem
      else
        @buff = @buff.downcase
        @stt = @@s_tag
      end
    when @@s_rem
      @buff = @buff + c
      @stt = @@s_remend1 if c == '-'
    when @@s_remend1
      @buff = @buff + c
      if c == '-' then
        @stt = @@s_remend2
      else
        @stt = @@s_rem
      end
    when @@s_remend2
      @buff = @buff + c
      if c == '>' then
        self.token.push @buff
        @buff = ''
        @stt = @@s_txt
      else
        @stt = @@s_rem
      end
    end
    return @stt
  end
  def check
    return @stt == @@s_txt
  end
  def emss
    case @stt
    when @@s_tag, @@s_tagchk
      return "tag paren unmatched"
    when @@s_rem, @@s_remchk1, @@s_remchk2, @@s_remend1, @@s_remend2
      return "comment paren unmatched"
    when @@s_quote
      return "double quote unmatched"
    else
      return "success"
    end
  end
  def close
    self.token.push @buff
    @buff = ''
  end
  def fetchtagname(s)
    return nil if s.size < 2
    return nil if s[0, 1] != '<'
    return nil if s[-1, 1] != '>'
    d = s.slice(1, s.size - 2)
    d = d.slice(0, d.size - 1) if d[-1, 1] == '/'
    l = d.index(/ /)
    l = d.size if not l
    d = d.slice(0, l)
    d = d + '/' if s[-2, 1] == '/'
    return d
  end
  protected :fetchtagname
  def fetchattr(s)
    if n = s.index('=') then
      k = s[0, n]
      v = (((n + 1) < s.size) ? s.slice(n + 1, s.size - 1) : '')
      if (v.size >= 2) && (v[0, 1] == '"') && (v[-1, 1] == '"') then
        v = v[1, v.size - 2]
      end
      return [k, v]
    else 
      return [s, true]
    end
  end
  protected :fetchattr
  def fetchtag(s)
    return @@cache[s] if @@cache[s]
    if (s[0, 1] == '<') && (s[-1, 1] == '>') && (s[1, 1] != '!') then
      s = s.slice(1, s.size - 2)
      s = s.slice(0, s.size - 1) if s[-1, 1] == '/'
      buff = ''
      stt = 0
      cs = s.split('')
      vs = []
      0.upto(cs.size - 1) { |i|
        if stt == 0 then
          if cs[i] == '"'
            buff = buff + cs[i]
            stt = 1
          elsif cs[i] == ' '
            vs.push buff
            buff = ''
          elsif i == (cs.size - 1) then
            vs.push buff + cs[i]
            buff = ''
          else
            buff = buff + cs[i]
          end
        else
          if cs[i] == '"'
            buff = buff + cs[i]
            stt = 0
            vs.push buff if i == (cs.size - 1)
          elsif i == (cs.size - 1) then
            vs.push buff + cs[i] # tail lost
          else
            buff = buff + cs[i]
          end
        end
      }
      if vs.size > 0 then
        vs = vs.slice(1, vs.size - 1)
        0.upto(vs.size - 1) { |i|
          vs[i] = fetchattr(vs[i])
        }
      end
      @@cache[s] = vs
      return vs
    else
      return s
    end
  end
  protected :fetchtag
  def findattr(vs, key, val)
    0.upto(vs.size - 1) { |i|
      next if key && !tagmatch(key, vs[i][0])
      next if val && !tagmatch(val, vs[i][1])
      return true
    }
    return (key == nil) && (val == nil)
  end
  protected :findattr
  def checkrange(min, v, max)
    return nil if v && min && (v < min)
    return nil if v && max && (v > max)
    return true
  end
  protected :checkrange
  def scan(name = nil, key = nil, val = nil, min = nil, max = nil)
    if name.class == String then
      self.map[name].each { |pair|
        if key || val then
          next if !checkrange(min, pair[0], max)
          next if !checkrange(min, pair[1], max)
          if findattr(fetchtag(self.token[pair[0]]), key, val) then
            yield(pair[0], pair[1])
          end
        else
          next if !checkrange(min, pair[0], max)
          next if !checkrange(min, pair[1], max)
          yield(pair[0], pair[1])
        end
      } if self.map[name]
    else
      self.map.each { |tkey, pairs|
        next if name && !tagmatch(name, tkey)
        pairs.each { |pair|
          if key || val then
            next if !pair[0]
            next if !checkrange(min, pair[0], max)
            next if !checkrange(min, pair[1], max)
            if findattr(fetchtag(self.token[pair[0]]), key, val) then
              yield(pair[0], pair[1])
            end
          else
            yield(pair[0], pair[1])
          end
        }
      }
    end
  end
  def block(name = nil, key = nil, val = nil, min = nil, max = nil)
    if block_given? then
      scan(name, key, val, min, max) { |s, e|
        yield(s, e) if s && e && (s < e) 
      }
    else
      vs = []
      scan(name, key, val, min, max) { |s, e|
        vs.push self.token[s, e] if s && e && (s < e) 
      }
      return vs
    end
  end
  def between(name = nil, key = nil, val = nil, min = nil, max = nil)
    if block_given? then
      scan(name, key, val, min, max) { |s, e|
        yield(s + 1, e - 1) if s && e && ((e - s) > 1)
      }
    else
      vs = []
      scan(name, key, val, min, max) { |s, e|
        vs.push self.token[(s + 1), (e - 1)] if s && e && ((e - 1) > 1) 
      }
      return vs
    end
  end
  def single(name = nil, key = nil, val = nil, min = nil, max = nil)
    if block_given? then
      scan(name, key, val, min, max) { |s, e|
        yield(s) if s && !e
      }
    else
      vs = []
      scan(name, key, val, min, max) { |s, e|
        vs.push s if s && !e
      }
      return vs
    end
  end
  def broken(name = nil, key = nil, val = nil, min = nil, max = nil)
    if block_given? then
      scan(name, key, val, min, max) { |s, e|
        yield(s) if !s && e
      }
    else
      vs = []
      scan(name, key, val, min, max) { |s, e|
        vs.push e if !s && e
      }
      return vs
    end
  end
  def find(tag = nil, key = nil, val = nil, min = nil, max = nil)
    min = 0 if !min
    max = self.token.size - 1 if !max
    if block_given? then
      min.upto(max) { |j|
        next if not istag(j)
        vs = fetchtag(self.token[j])
        next if vs.class == String
        next if tag && !tagmatch(tag, fetchtagname(self.token[j]))
        if !key && !val then
          yield(j)
        elsif (key || val) then
          0.upto(vs.size - 1) { |i|
            next if key && !tagmatch(key, vs[i][0])
            next if val && !tagmatch(val, vs[i][1])
            yield(j)
            break
          }
        else
          0.upto(vs.size - 1) { |i|
            if  (!key || tagmatch(key, vs[i][0])) \
             && (!val || tagmatch(val, vs[i][1])) then
              yield(j)
              break
            end
          }
        end
      }
    else
      vs = []
      min.upto(max) { |j|
        next if not istag(j)
        vs = fetchtag(self.token[j])
        next if vs.class == String
        next if tag && !tagmatch(tag, fetchtagname(self.token[j]))
        if !key && !val then
          vs.push j
        elsif (key || val) then
          0.upto(vs.size - 1) { |i|
            next if key && !tagmatch(key, vs[i][0])
            next if val && !tagmatch(val, vs[i][1])
            vs.push j
            break
          }
        else
          0.upto(vs.size - 1) { |i|
            if  (!key || tagmatch(key, vs[i][0])) \
             && (!val || tagmatch(val, vs[i][1])) then
              vs.push j
              break
            end
          }
        end
      }
      return vs
    end
  end
  def withtag(i)
    name = fetchtagname(self.token[i])
    attr = Hash[*fetchtag(self.token[i]).flatten]
    yield(name, attr)
  end
  def edit(i)
    name = fetchtagname(self.token[i])
    attr = Hash[*fetchtag(self.token[i]).flatten]
    yield(name, attr)
    s = ''
    attr.each { |k, v|
      if v.class == String then
        s = s + sprintf(" %s=\"%s\"", k, v)
      elsif v.class == TrueClass
        s = s + sprintf(" %s", k)
      end
    }
    self.token[i] = "<#{name}#{s}>"
  end
  def textonly(s = 0, e = self.token.size - 1)
    if block_given? then
      s.upto(e) { |i| yield(i) if istext(i) }
    else
      vs = []
      s.upto(e) { |i| vs.push i if istext(i) }
      return vs
    end
  end
  def commentonly(s = 0, e = self.token.size - 1)
    if block_given? then
      s.upto(e) { |i| yield(i) if iscomment(i) }
    else
      vs = []
      s.upto(e) { |i| vs.push i if iscomment(i) }
      return vs
    end
  end
  def values(a) 
    return a.map { |i| self.token[i] }
  end
  def get_radio(mname)
    find('input', 'name', mname) { |i|
      withtag(i) { |name, attr|
        next if attr['type'] != 'radio'
        return attr['value'] if attr['checked']
      }
    }
    return nil
  end
  def set_radio(mname, setval, defval = nil)
    map = Hash.new(nil)
    find('input', 'name', mname) { |i|
      edit(i) { |name, attr|
        next if attr['type'] != 'radio'
        map[attr['value']] = i
        attr.delete('checked') 
      }
    }
    if x = map[setval] then
      edit(x) { |name, attr| attr['checked'] = true }
      return true
    elsif defval && map[defval] then
      edit(map[defval]) { |name, attr| attr['checked'] = true }
      return nil 
    else
      return nil
    end
  end
  def get_select(mname)
    between('select', 'name', mname) { |s, e|
      s.upto(e) { |i|
        if istag(i) then
          withtag(i) { |name, attr|
            if (name == 'option') then
              return attr['value'] if attr['selected']
            end
          }
        end
      }
    }
    return nil
  end
  def set_select(mname, selval, defval = nil)
    map = Hash.new(nil)
    between('select', 'name', mname) { |s, e|
      s.upto(e) { |i|
        if istag(i) then
          edit(i) { |name, attr|
            if (name == 'option') then
              map[attr['value']] = i
              attr.delete('selected')
            end
          }
        end
      }
    }
    if x = map[selval] then
      edit(x) { |name, attr| attr['selected'] = true }
      return true
    elsif defval && map[defval] then
      edit(map[defval]) { |name, attr| attr['selected'] = true }
      return nil
    else
      return nil
    end
  end
end

取説

パブリックメンバー
token
map

コンストラクタ
new(s = '')

文字列の読み込み
load_string(s)

内容を空にする
reset

トークンの種別
istag(i)
iscomment(i)
istext(i)

例:指定したページの最初の画像のURLを抽出する

  url = URI.parse(lnk)
  http = Net::HTTP.new(url.host, url.port)
  http.use_ssl = true if url.class == URI::HTTPS
  http.verify_mode = OpenSSL::SSL::VERIFY_NONE
  res = http.get(url)
  html = Htmltoken.new(res.body)
  html.single('img', 'id') { |s| 
    html.withtag(s) { |name, attr| puts "#{attr['src']}" }
  }

例:先頭のタグを一つ抽出する

  puts html.token[0] # 例えば"<html>"と表示される。

ペアになっているタグの探索
block(name = nil, key = nil, val = nil, min = nil, max = nil)
block(name = nil, key = nil, val = nil, min = nil, max = nil) {
 |startpos, endpos| ... }
between(name, key = nil, val = nil, min = nil, max = nil)
between(name, key = nil, val = nil, min = nil, max = nil) {
 |startpos, endndpos| ... }

blockは開始／終了タグを探す
betweenは開始／終了タグに挟まれた範囲を探す
min,maxは検索の範囲で、省略すれば文書全てを対象にする。
min,maxを指定すれば入れ子の処理ができる。
プロシジャーを与えていれば、開始位置と終了位置をパラメーターに実行する。

ペアになっていないタグの探索
single(name = nil, key = nil, val = nil, min = nil, max = nil)
single(name = nil, key = nil, val = nil, min = nil, max = nil) {
 |pos| ... }
broken(name = nil, key = nil, val = nil, min = nil, max = nil)
broken(name = nil, key = nil, val = nil, min = nil, max = nil) {
 |pos| ... }

singleはペアになる終了タグを持たない開始タグを探す
singleはペアになる開始タグを持たない終了タグを探す
min,maxは検索の範囲で、省略すれば文書全てを対象にする。

タグを検索
find(name = nil, key = nil, val = nil, min = nil, max = nil)
find(name = nil, key = nil, val = nil, min = nil, max = nil) {
 |pos| ... }

findはペアであるかどうかを問わずタグを検索する
min,maxは検索の範囲で、省略すれば文書全てを対象にする。

参照・編集
withtag(i) { |tagname, attr| ... }
edit(i) { |tagname, attr| ... }

タグを解釈してタグ名および{属性名=>属性値,...}の形式で
ブロックパラメータを与え、ブロックを実行する。
editはtagnameおよびattrに対する変更を保存しwithtagは無視する。

テキスト
textonly(s = 0, e = self.token.size - 1)
textonly(s = 0, e = self.token.size - 1) { |pos| ... }

コメント
commentonly(s = 0, e = self.token.size - 1)
commentonly(s = 0, e = self.token.size - 1) { |pos| ... }

ラジオボタン
get_radio(mname)
set_radio(mname, setval, defval = nil)

get_radioは
inputタグのradioボタンに関して、
指定された名前のradioボタンの一覧からcheckedに
なっているタグを検索し、設定されているvalueを返す。

set_radioは
inputタグのradioボタンに関して、
指定された名前のradioボタンの一覧から
valueがsetvalと等しければそのタグにcheckedを付け、
そうでなければcheckedを外す。
defvalを指定した場合でかつcheckedを付けるべき項目
が見つからない場合、setvalではなくdefvalで探す。
(選択肢に「その他」があるような場合を想定している)

セレクタ
get_select(mname)
set_select(mname, selval, defval = nil)

get_selectは
指定された名前のselectタグに連なるoptionタグに関して、
一覧からselectedになっているoptionタグを検索し、
設定されているvalueを返す。

set_selectは
指定された名前のselectタグに連なるoptionタグに関して、
valueがsetvalと等しければそのタグにselectedを付け、
そうでなければselectedを外す。
defvalを指定した場合でかつselectedを付けるべき項目
が見つからない場合、setvalではなくdefvalで探す。
(選択肢に「その他」があるような場合を想定している)