--- a/paper/c4.tex	Fri Feb 19 01:16:37 2016 +0900
+++ b/paper/c4.tex	Fri Feb 19 03:14:25 2016 +0900
@@ -551,11 +551,17 @@
 次に正規表現木に状態を割り当てて、非決定性有限オートマトン(NFA)を生成する。
 正規表現木のノードに対して一定のルールに沿って状態を割り当てていく。
 
-\begin{itemize}
-\item 左子ノードが `*' でない `+' は新しい状態を作る
-\item `\textbar'ノードの場合、左右の子ノードの先頭の状態は同じ状態を割り振る。
-\item `*' があれば、次の状態は `*' に接続されている木の先頭の状態と同じ。次の状態が受理状態なら先頭の状態と受理状態の組み合わせになる。
-\end{itemize}
+% /**
+%     pass 1 : 正規表現に必要な状態を探して、それぞれに番号を割り振る
+%         前が * でない + は新しく状態を作る
+%         * があったら、次の状態はその時の先頭の状態か次の状態が終了状態ならば終了状態との組み合わせになる
+%         常に先頭の状態を返す
+%         最後が*ならば、それを持ち歩く
+%     pass 2: 
+%         割り当てられた状態に沿って charclass の行き先を書き換える
+%         書き換えた charclass を merge する
+%         前の部分に * がない + は新しい状態をつくるので、state を切り替えて生成する
+%  */
 
 \begin{lstlisting}[frame=lrbt,label=src:generateTransition,caption=正規表現木の状態割当,numbers=left]
 typedef struct tgValue {
@@ -622,7 +628,37 @@
     }
 }
 \end{lstlisting}
-ノードに状態を割り振りながら次の状態の遷移先を設定することによって、オートマトンによる状態遷移を表現することができる。
+
+ソースコード\ref{src:generateTransition}は、正規表現木を二度通すことによって状態割当と遷移先を設定するルーチンである。
+一度目は正規表現に必要な状態を探して、それぞれに状態を振っていく。
+\verb+generateTransition+ は \verb+TGValue+ を常に持ち歩いて状態を割り当てる。
+9-32行目は `+' ノードが来た時の処理である。
+tgv を tgvLeft にコピーしたのち左のノードに降りていく。
+もし tgvLeft に asterisk が含まれていたら、endState を`+'ノードの右ノードに割り振る。
+そして、左の asteriskの状態 を右の startState に割り振った後に右ノードに降りていく。
+右ノードに降りていった際にも asterisk があるかどうか確認し、その情報を左の asterisk にコピーし、左の tgv を返す。
+tgvLeft に asterisk が無ければ、新しい状態を生成して tgvRight と右ノードそれぞれに状態割り振る。
+その後、右ノードに降りていく。
+もし、tgvがendStateで、tgvRight が asterisk であれば、tgvの endState が受理状態を tgvRight.startState にコピーする。
+その後 tgvLeft を返す。
+
+34-37行目は `\textbar' ノードが来た時の処理である。
+`\textbar' の左ノードに下り、tgv1を生成する。
+tgv.endState を tgv1.endState にコピーしたのち、右ノードに下る際に tgv1 を食わせる。
+右ノードが下り終わったら tgv2 が返されるので、これを返す。
+
+39-44行目は `*' ノードが来た時の処理である。
+tgvAstah は startState と endState を同じ状態にする。
+左ノードに下って行く際、tgvAstah を食わせて、その結果を tgvAstah に代入する。
+tgvAstah の asterisk の状態を tgvAstah の startState にしたあとに tgvAstah を返す。
+
+46-59行目は文字もしくは文字クラスのノードが来た時の処理である。
+このとき、ノードに番号と状態を割り振る。
+
+二度目は割り当てられた状態に沿って文字クラスの行き先を書き換え、それを merge する。
+前の部分に * がない + は新しい状態をつくるので、state を切り替えて生成する。
+
+%書いててもわからんん・・・・
 
 ([a-zA-Z]\textbar ab*)*aa
 
@@ -660,7 +696,7 @@
 % \newpage
 
 1 入力に対して遷移先が複数存在している場合は、文字によって場合分けをする必要がある。
-図\ref{fig:nfaex} の
+図\ref{fig:nfa} の
 状態 4 は [a-z] が入力されると状態 4 に遷移し、b が入力されると状態 2 に遷移する。このとき、b が入力されると状態 2 か状態 4 のどちらかに遷移することになる。(図\ref{fig:nfa})
 
 \begin{figure}[htpb]
@@ -769,37 +805,68 @@
 \end{figure}
 
 \subsection{正規表現マッチャの並列処理の実装}
-正規表現から正規表現木を生成し、その木に対して状態を割り振りを行ない、Subset Construction による新しい状態の生成が終わったあとにマッチングを行う。
 
-% bit パターンの実装の話
-今回の実装では、状態それぞれを Bit Pattern で表現している。
-Bit Pattern で状態を持つことで、Subset Construction による状態の組み合わせも Bit Pattern の和を取ることで容易に表現できる。
-% state 構造 bitvector の話 配列を MaxState の分のコードの話
-それらの状態は StateArray と呼ばれる配列で格納されており、状態遷移が行われるたびに StateArray を見に行く。
-あらかじめ配列の大きさのメモリを確保する必要があるが、Subset Construction による新しい状態生成も考慮しなければならない。
-正規表現木に状態を割り振った時に最大の状態の Bit は分かっているので、その状態の Bit の 2 倍だけ配列を確保しておけば、Bit Pattern が全て 1 までの状態を表現することができる。
-
-StateArray を見れば、ある状態に対して入力をすると状態の遷移先をチェックすることができる。
-状態の遷移先は文字クラスごとの List 構造になっており、入力された文字をチェックしながらリストを辿って状態の遷移先を判断する。
-(図\ref{fig:statearray})
-
-\begin{figure}[htpb]
-  \begin{center}
-    \includegraphics[scale=0.2]{images/regex/statearray.pdf}
-  \end{center}
-  \caption{StateArray による状態遷移}
-  \label{fig:statearray}
-\end{figure}
+% % bit パターンの実装の話
+% 今回の実装では、状態それぞれを Bit Pattern で表現している。
+% Bit Pattern で状態を持つことで、Subset Construction による状態の組み合わせも Bit Pattern の和を取ることで容易に表現できる。
+% % state 構造 bitvector の話 配列を MaxState の分のコードの話
+% それらの状態は StateArray と呼ばれる配列で格納されており、状態遷移が行われるたびに StateArray を見に行く。
+% あらかじめ配列の大きさのメモリを確保する必要があるが、Subset Construction による新しい状態生成も考慮しなければならない。
+% 正規表現木に状態を割り振った時に最大の状態の Bit は分かっているので、その状態の Bit の 2 倍だけ配列を確保しておけば、Bit Pattern が全て 1 までの状態を表現することができる。
+% 
+% StateArray を見れば、ある状態に対して入力をすると状態の遷移先をチェックすることができる。
+% 状態の遷移先は文字クラスごとの List 構造になっており、入力された文字をチェックしながらリストを辿って状態の遷移先を判断する。
+% (図\ref{fig:statearray})
+% 
+% \begin{figure}[htpb]
+%   \begin{center}
+%     \includegraphics[scale=0.2]{images/regex/statearray.pdf}
+%   \end{center}
+%   \caption{StateArray による状態遷移}
+%   \label{fig:statearray}
+% \end{figure}
 
 % subset construction の速度 O(mlogn)
 
-\begin{lstlisting}[frame=lrbt,label=src:result,caption=ceriumGrep の TMmain,numbers=left]
+\begin{lstlisting}[frame=lrbt,label=src:ceriumTMmain,caption=ceriumGrep の TMmain,numbers=left]
+typedef struct transitionGenerator {
+    long totalStateCount;
+    long totalBasicState;
+    StateStackPtr stack;
+    StatePtr stateEnd;
+    StatePtr stateStart;   // start state without accept flag
+    StatePtr *stateArray;
+    StatePtr stateList;
+    StatePtr anyState;
+    tsValue (*stateSkip)(tsValue tsv);
+    tsValue (*stateMatch)(tsValue tsv);
+    tsValue (*stateNothing)(tsValue tsv);
+} TransitionGenerator, *TransitionGeneratorPtr;
+
+void
+ceriumCreateAnyState(TransitionGeneratorPtr tg) {
+    tg->stateSkip = stateSkip;
+    tg->stateMatch = stateMatch;
+    tg->stateNothing = stateNothing;
+    createAnyState(tg);
+    generateTState(tg->anyState,tg);
+    // generateTState for startState. It is used in stateMatch.
+    generateTState(tg->stateList,tg);
+    tg->stateStart = NEW(State);
+    *tg->stateStart = *tg->stateList;
+    tg->stateStart->accept = false; // Start state never accept
+    generateTState(tg->stateStart,tg);
+}
+
 int
 TMmain(TaskManager *manager, int argc, char *argv[])
 {
     char *filename = 0;
     Search s = grep(argc,argv,true);  // 正規表現木の生成、木の状態割り振りを行う
     FileMapReduce *fmp = new FileMapReduce(manager,TASK_EXEC,TASK_EXEC_DATA_PARALLEL,TASK_PRINT);
+
+    ceriumCreateAnyState(s.tg);
+
     filename = fmp->init(argc, argv);
     fmp->w->global = (void*)s.tg;
     if (filename < 0) {
@@ -812,7 +879,11 @@
 }
 \end{lstlisting}
 
-\begin{lstlisting}[frame=lrbt,label=src:task,caption=ceriumGrep のマッチング部分,numbers=left]
+ソースコード\ref{src:ceriumTMmain}は、ceriumGrep の Task 生成部分である。
+34行目で正規表現木の生成や状態割り振り、NFAの生成を行う。
+40行目に初期状態や受理状態、マッチした時の関数ポインタなど状態遷移に関する情報がまとまった \verb+TransitionGenerator+ を Task 側に渡す。
+
+\begin{lstlisting}[frame=lrbt,label=src:ceriumGreptask,caption=ceriumGrep Task,numbers=left]
 TSValue blockSearch(TSValue tsv,Buffer buff,int task_spawned) {
     tsv.current = tsv.tg->stateStart->tState;
     tsv.blk->result = NULL;
@@ -850,6 +921,9 @@
 }
 \end{lstlisting}
 
+ソースコード\ref{src:ceriumGreptask}は、並列実行でマッチングを行う Task である。
+文字列と正規表現のマッチングは 8 行目の \verb+tSearch+ で行われている。
+
 %tSearch の話
 \begin{lstlisting}[frame=lrbt,label=src:tSearch,caption=tSearch,numbers=left]
 TSValue tSearch(TSValue tsv) {
@@ -887,6 +961,8 @@
     return tsv;
 }
 \end{lstlisting}
+ソースコード\ref{src:tSearch}は、正規表現のマッチングを行う関数である。
+
 
 % Print の分割部分の話追加 最後
 分割されたファイルに対して正規表現によるマッチングを行う。

Binary file paper/master_paper.pdf has changed