HTTP/1.1 ヘッダのパラメータ付きトークンのデコーダ
RFC 7230 の Transfer-Encoding ヘッダのようなパラメータ付きトークンの並びをデコードします。 ただし、 RFC のままでは末尾のスペースが除去済みのものを扱うように規則が書いてあるので、 除去していなくても良いように規則を手直しすることにします。
⇒ RFC 7230 HTTP/1.1: Message Syntax and Routing
リンク先の Transfer-Encoding の生成規則を PEG 風に書き直します。 RFC の規則ではコンマの扱いがルーズで、 ヘッダ値の前後に余分なコンマがあっても良く、 コンマは WS を挟んで複数あっても良いことになっています。
Transfer_Encoding <- (',' (WS / ',')*)? transfer_coding
(',' (WS / ',')* transfer_coding)* (WS / ',')*
transfer_coding <- token WS* (';' WS* parameter WS*)*
parameter <- token WS* '=' WS* (token / quoted_string)
token <- [[:alnum:]!#$%&'*+\-.^_`|~]+
quoted_string <- '"' ([^"\\[:^graph:]] / WS / '\\' .)* '"'
WS <- [ \t]2015 年 9 月 14 日修正 アクション表と文字クラス表を使ってコードを書き直しました。
この規則を DFA に書き直して、 遷移表を作ります。 表の先頭カラムは、 1 ビット目が 1 のとき終了状態になれることを表しています。 状態 S1 を開始状態に選ぶと 1 個以上に、 状態 S12 を開始状態に選ぶとゼロ個以上のパラメータ付きトークンを認識します。
//@<パラメータ付きトークンの遷移表@>= static const int SHIFT[14][9] = { // \s , ; = " \\ T $ { 0, 0, 0, 0, 0, 0, 0, 0, 0}, { 0, 1, 1, 0, 0, 0, 0, 2, 0}, // S1: \s S1 | ',' S1 | T S2 { 0, 3, 12, 4, 0, 0, 0, 2, 13}, // S2: \s S3 | ',' S12 | ';' S4 | T S2 | $ S13 { 0, 3, 12, 4, 0, 0, 0, 0, 13}, // S3: \s S3 | ',' S12 | ';' S4 | $ S13 { 0, 4, 0, 0, 0, 0, 0, 5, 0}, // S4: \s S4 | T S5 { 0, 6, 0, 0, 7, 0, 0, 5, 0}, // S5: \s S6 | '=' S7 | T S5 { 0, 6, 0, 0, 7, 0, 0, 0, 0}, // S6: \s S6 | '=' S7 { 0, 7, 0, 0, 0, 10, 0, 8, 0}, // S7: \s S7 | '"' S10 | T S8 { 0, 11, 12, 4, 0, 0, 0, 8, 13}, // S8: \s S11 | ',' S12 | ';' S4 | T S8 | $ S13 { 0, 10, 10, 10, 10, 10, 10, 10, 0}, // S9: . S10 { 0, 10, 10, 10, 10, 11, 9, 10, 0}, // S10: '"' S11 / '\\' S9 / . S10 { 0, 11, 12, 4, 0, 0, 0, 0, 13}, // S11: \s S11 | ',' S12 | ';' S4 | $ S13 { 0, 12, 12, 0, 0, 0, 0, 2, 13}, // S12: \s S12 | ',' S12 | T S2 | $ S13 { 1, 0, 0, 0, 0, 0, 0, 0, 0}, // S13: MATCH };
遷移表の T は token を構成する文字クラスを表しています。 S1 と S2 の T による遷移は token に対応し、 S4 と S5 の T による遷移はパラメータ名に対応します。 S7 と S8 の T による遷移は token によるパラメータ値に対応します。 S9 と S10 はダブル・クォートに囲まれたパラメータ知に対応します。 これから、アクションを決めて、 アクション表を作ります。
//@<パラメータ付きトークンのアクション表@>= static const int ACTION[14][9] = { // \s , ; = " \\ T $ { 0, 0, 0, 0, 0, 0, 0, 0, 0}, { 0, 0, 0, 0, 0, 0, 0, 1, 0}, // S1: \s S1 | ',' S1 | T S2 { 0, 0, 5, 0, 0, 0, 0, 1, 5}, // S2: \s S3 | ',' S12 | ';' S4 | T S2 | $ S13 { 0, 0, 5, 0, 0, 0, 0, 0, 5}, // S3: \s S3 | ',' S12 | ';' S4 | $ S13 { 0, 0, 0, 0, 0, 0, 0, 2, 0}, // S4: \s S4 | T S5 { 0, 0, 0, 0, 0, 0, 0, 2, 0}, // S5: \s S6 | '=' S7 | T S5 { 0, 0, 0, 0, 0, 0, 0, 0, 0}, // S6: \s S6 | '=' S7 { 0, 0, 0, 0, 0, 0, 0, 3, 0}, // S7: \s S7 | '"' S10 | T S8 { 0, 4, 6, 4, 0, 0, 0, 3, 6}, // S8: \s S11 | ',' S12 | ';' S4 | T S8 | $ S13 { 0, 3, 3, 3, 3, 3, 3, 3, 0}, // S9: . S10 { 0, 3, 3, 3, 3, 4, 0, 3, 0}, // S10: '"' S11 / '\\' S9 / . S10 { 0, 0, 5, 0, 0, 0, 0, 0, 5}, // S11: \s S11 | ',' S12 | ';' S4 | $ S13 { 0, 0, 0, 0, 0, 0, 0, 1, 0}, // S12: \s S12 | ',' S12 | T S2 | $ S13 { 0, 0, 0, 0, 0, 0, 0, 0, 0}, // S13: MATCH };
文字コードから遷移表とアクション表で使う文字クラス番号に変換する表を作ります。
//@<パラメータ付きトークンの文字クラス表@>= static const int CCLS[128] = { // \t \n \r 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // ! " # $ % & ' ( ) * + , - . / 1, 7, 5, 7, 7, 7, 7, 7, 0, 0, 7, 7, 2, 7, 7, 0, // 0 1 2 3 4 5 6 7 8 9 : ; < = > ? 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 0, 3, 0, 4, 0, 0, // @ A B C D E F G H I J K L M N O 0, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, // P Q R S T U V W X Y Z [ \\ ] ^ _ 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 0, 6, 0, 7, 7, // ` a b c d e f g h i j k l m n o 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, // p q r s t u v w x y z { | } ~ 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 0, 7, 0, 7, 0, };
トークンとパラメータは header_item_type にまとめます。 これの parameter は文字列の交互リストにしています。 header_item_type を並べたものが header_item_list_type で、 デコーダはこれのメンバ関数にします。 decode メンバ関数は解釈したい文字列と、トークンが 1 個以上かゼロ個以上かを引数で指定できます。
#include <string> #include <vector> #include <cctype> struct header_item_type { std::string token; std::vector<std::string> parameter; bool equal_token (std::string const& x) const { return token == x; } void clear () { token.clear (); parameter.clear (); } }; struct header_item_list_type { std::vector<header_item_type> list; std::size_t find (std::string const& x) const; std::size_t size () const { return list.size (); } bool decode (std::string const& str, int const min = 1); }; bool header_item_list_type::decode (std::string const& str, int const min) { //@<パラメータ付きトークンの遷移表@> //@<パラメータ付きトークンのアクション表@> //@<パラメータ付きトークンの文字クラス表@> header_item_type item; std::string::const_iterator s = str.cbegin (); std::string::const_iterator const e = str.cend (); std::string name; std::string value; int next_state = 1 == min ? 1 : 12; for (; s <= e; ++s) { int ch = s == e ? '\0' : *s; int cls = s == e ? 8 : ch < 128 ? CCLS[ch] : 0; int prev_state = next_state; if ((9 == prev_state || 10 == prev_state) && 0 == cls) cls = 0x20 <= ch && ch < 0x7f ? 7 : 0; next_state = SHIFT[prev_state][cls]; if (! next_state) break; switch (ACTION[prev_state][cls]) { case 1: item.token.push_back (ch); break; case 2: name.push_back (std::tolower (ch)); break; case 3: value.push_back (ch); break; case 4: item.parameter.push_back (name); item.parameter.push_back (value); name.clear (); value.clear (); break; case 5: list.push_back (item); item.clear (); break; case 6: item.parameter.push_back (name); item.parameter.push_back (value); list.push_back (item); name.clear (); value.clear (); item.clear (); break; } } return (SHIFT[next_state][0] & 1) != 0; }