\chapter{Jungleに新しく追加したAPI}
前章ではmaTrixのデータ構造と許認可について説明を行った後、Jungle上にどのように構築するか記述した。
本章では、Jungle上にmaTrixを構築するために新しく追加した機能について解説する。
\section{検索APIの実装}


JungleのTreeに対する検索は、java8の新機能であるlambda式を用いてfind関数を実装した。
lambda式を使用することで、匿名クラスを使う時より簡潔にコードを記述できるようになった。


\begin{itembox}[l]{find関数の定義}
\begin{verbatim}
 public Iterator<TreeNode> 
          find(final Query query, final String key, String searchValue);
\end{verbatim}
\end{itembox}

find関数は引数にQuery、String key、String valueの3つの引数を取り、条件に一致したNodeのIteratorを返す。
第一引数には、探索の条件を記述する関数boolean comdition(TreeNode)を定義したInterfaceQueryを。
第二、第三引数の、String key、String valueはIndexの取得を行うために使用する。

\begin{itembox}[l]{QueryInterfaceの定義}
\begin{verbatim}
public interface Query {
      boolean condition(TreeNode _node);
}
\end{verbatim}
\end{itembox}


以下に実際にlambda式を用いたfind関数の使用例と実際の処理の流れを記す。

\begin{itembox}[l]{JungleのQuery部分のソースコード}
\begin{verbatim} 
Iterator<TreeNode> pairPersonIterator = 
traverser.find((TreeNode node) -> {
  String element = node.getAttributes().getString("element");
  if (element == null)
    return false;
    if (element.equals("Person"))
      return true;
    return false;
}, "element", "Person");
\end{verbatim}
\end{itembox}

\begin{enumerate}
\item find関数の処理の流れは、まず、第2、第3引数のString key,String valueを用いて、これらの値に対応したIndexが登録されているかを調べる、Indexがある場合はIndexを使用し値を返す。Indexがない場合は、Treeから深さ優先でTreeNodeを取得していく。(図\ref{fig:DepthFirstSearch})
\item TreeNodeを取得したら、boolean Query.condition(TreeNode)を実行する。このconditionは実際にfindを使用する際にlambda式で記述する。 
\item conditionの中では、TreeNodeのAttributeに対してgetを行い探索対象のデータをTreeNodeが保持しているかを調べる
\item データを持っていた場合はTrueを、持っていなかった場合はFalseを返す
\item conditionの返り値が、Trueだった場合取得したTreeNodeを返す。Falseだった場合は次のTreeNodeを取得し、2に戻る。
\end{enumerate}

find関数は、上記の処理を探索が終わるまで繰り返す。
\begin{figure}[h]
\begin{center}
\includegraphics[height=5cm,bb=0 0 445 249]{fig/DepthFirstSearch.pdf}
\caption{findの検索順序}
\label{fig:DepthFirstSearch}
\end{center}
\end{figure}


検索APIは、他に特定のNode以下に対して検索を行うfindInSubTree(Query,node,key,value)も実装した。(図\ref{fig:FindInSubTree})

\begin{figure}[h]
\begin{center}
\includegraphics[height=5cm,bb=0 0 445 249]{fig/FindInSubTree.pdf}
\caption{FindInSubTreeの検索順序}
\label{fig:FindInSubTree}
\end{center}
\end{figure}

findInSubTreeを使用することで、更に限定的な探索が行えるようになった。この関数も基本的な処理の流れはfind関数と同じである。
また、maTrix上に実装されていた、構成情報からデータを取得するFunctionも全て実装して、実際のmaTrixと同じようにデータのアクセスを行えるようにした。


\section{Jungle上のIndexの設計}
Jungleの探索はTreeを全探索するので、探索の計算量はO(n)である。
そこで、Indexを使用することで効率よく探索を行えるようにする。
Jungleは過去のTreeを全て保持しているため、Treeのversion毎にIndexを持っていることが望ましい。
そこで、メモリの消費量を抑え、各versionのTreeにIndexをもたせる方法として、FunctionalJavaのTreeMapを使用したIndexの実装を提案する。

TreeMapは、KeyとValueのペアを用いて赤黒木を構築する。
赤黒木の長所として、ソート済み二分木の探索なので計算量がO(logN)であることがあげられる。

それに加え、FunctionalJavaのTreeMapは、データの更新が行われた際に、一度作られたTreeに対して更新を行わず過去のTreeを再利用し、更新後のTreeMap新しく返すため、メモリの使用量を抑えつつ複数のversionでIndexを保持できる。

Indexの型を以下に記す。
\begin{itembox}[l]{Indexの型}
\begin{verbatim}
TreeMap<String key,TreeMap<String value,List<TreeNode>>>
\end{verbatim}
\label{interface}
\end{itembox}
最初のTreeMap$<$String key,TreeMap$>$はIndexを格納するTreeMapである。
このTreeMapに対しkeyでgetを行うと、keyに対応するIndexが登録されている場合、Indexを取得でき、取得したIndexに対し
valueでgetを行うと、valueの値を持つNodeのListが返ってくる。

\newpage
{\large ParentIndex}

TreeNodeでgetを行うと、親Nodeを返すParentIndexを実装した。
ParentIndexの型は、TreeMap$<$TreeNode,TreeNode$>$で定義されている。


\begin{figure}[h]
\begin{center}
\includegraphics[height=5cm,bb=0 0 426 277]{fig/ParentIndex.pdf}
\caption{ParentIndexExample}
\label{fig:ParentIndex}
\end{center}
\end{figure}

上記の図\ref{fig:ParentIndex}を用いたParentIndexの例を表\ref{list:ParentIndex}にまとめた。
\begin{table}[h]
\caption{ParentIndexの返り値}
\label{list:ParentIndex}
\begin{center}
\begin{tabular}{|l|l|} \hline
返ってくるNode & 渡すNode      ~ \\ \hline
Node2          & Node4、Node5  ~ \\ \hline
Node3          & Node6、Node7  ~ \\ \hline
Node1          & Node2、Node3  ~ \\ \hline
\end{tabular}
\end{center}
\end{table}

Jungleはノードの編集に、そのノードまでのNodePathを必要としたため、ParentIndexを実装するまでは、Indexの型を、TreeMap$<$String key, TreeMap$<$ String value , List$<$Pair$<$TreeNode,NodePath$>>>>$
と定義し、返り値をPair$<$TreeNode,NodePath$>$とし、TreeNodeとそのTreeNodeへのNodePathのペアにすることでNodeの編集を可能にしていた。
しかし、Treeの編集を行った際に、TreeNodeへのPathは常に変動する為、Index内のNodePathの更新コストが編集時のネックであった。
しかし、ParentIndexを実装することで、TreeNodeからNodePathを取得できるようになったため、IndexにNodePathを入れる必要がなくなり、Indexは今の型で定義できるようになった。
ParentIndexもIndexと同じようにFunctionalJavaのTreeMapを使用しているため、メモリの消費を抑えて、全てのversionのTreeで保持することが可能である。

以下にParentIndexを使用して、NodePathを取得する方法を示す。
\begin{enumerate}
\item ParentIndexを用いて親Nodeを取得する。
\item 親Nodeから子ノードのリストを取得する。
\item 子ノードのリストから、親Nodeをgetするのに使用したNodeがある位置のインデックスを取得する。
\item 3で取得したIndexをPathに追加する
\item rootNodeに辿り着くまで1 - 4を繰り返すと、対象NodeへのNodePathが取得できる。
\end{enumerate}



\section{過去のTreeに対するアクセス}
Jungle上でmaTrixの構成情報モデルの表現を行う際に、過去のTreeにアクセスする必要がある。
Jungleは、クラスChangeSet内にTreeのデータを保持している。
ChangeSetからは、今のrevisionIdと、１つ前のTreeのデータを取得できるため、再帰的に過去のTreeのデータを取得できる。
アクセスしたいTreeのrevisionIdを引数に取り、過去のTreeのデータの取得とrevisionIdの比較を繰り返すことで過去のTreeにアクセスする、getOldTree(long revisionId)を DefaultJungleTree内に実装した。


以下にgetOldTreeの実装部分のコードを示す。

\begin{itembox}[l]{getOldTreeの実装部分}
\begin{verbatim}
@Override
public Either<Error, JungleTree> getOldTree(long revision) {
  TreeContext tc = repository.get();
  ChangeSet cs = tc.getChangeSet();

  for (; cs.revision() != revision;) {
    cs = cs.prev();
    if (cs == null)
      return DefaultEither.newA(GetOldTreeError.OLD_TREE_NOT_FOUND);
  }

  TreeNode root = cs.getRoot();

  TreeContext oldTc = new DefaultTreeContext(root, cs);
  String oldTreeUuid = uuid + revision;
  JungleTree oldTree = 
      new DefaultJungleTree(oldTc, oldTreeUuid, writer, treeEditor);
  return DefaultEither.newB(oldTree);
}
\end{verbatim}
\end{itembox}

for文の中で、過去のTreeの取得と、revisionの比較を繰り返している。
revisionが一致した場合は、そのversionのTreeを返し、アクセスしたいrevisionを持つTreeが見つからなかった場合は、エラーを返す。

\section{JungleXMLReader}
maTrixからXML形式で書き出されたデータをJungleに格納するためのAPIとして、XMLReaderを実装した。
JungleXMLReaderの実装にはsax(Simple API for XML)を用いた。

saxは、XMLのタグやテキストデータを読んだ際にイベントを発生させながら、構文解析を行う。
プログラマは、ContentHandlerという特殊なイベントリスナをsaxのparserに登録すると、発生するイベントを取得できる。
イベントには、読み込んだタグの名前やテキストデータが含まれている。


\begin{table}[h]
\caption{saxの主要なイベント一覧}
\label{list:TreeNode}
\begin{center}
\begin{tabular}{|l|l|} \hline
イベント名 & 呼び出されるタイミング \\ \hline
startDocument & XMLのParseが始まる時 ~\\ \hline
endDocument &  XMLのParseが終わった時~\\ \hline
startElement & 要素を読み込んだ時 ~\\ \hline
endElement & 要素が閉じられた時 ~\\ \hline
Charactor & テキストが読み込まれた時 ~\\ \hline
\end{tabular}
\end{center}
\end{table}

saxでは、org.xml.sax.helpers.DefaultHandlerという形で、ContentHandlerのデフォルト機能が提供されているため、プロ
グラマはこれを継承することで必要なイベント処理のみをoverrideして記述できるようになっている。

XMLReaderで使用しているReadXmlHandlerは、startElement、charactor、endElement、endDocument、の4つのイベントを使用しており、XMLを読み込む際に、Treeを構築しながらParseを行う。

startElementが呼ばれた時は、今いる地点の下に新しくNodeを作り、Attributeの値を格納する。
charactorが呼ばれた時は、今いるNodeにテキストデータを格納する。
endElementが呼ばれたら、今いるNodeの親ノードに移動する。

以上の3つの関数を用いて、XMLのデータをTreeに格納していき、endDocumentが呼ばれた時に木のCommitを行っている。
データの格納は、Jungle上でのmaTrixのデータ構造の表現で述べたように、多少Jungleに適合した形に書き換えてから行う。
\section{XACMLInterpreter}
XMLReaderと同じようsaxにを用いて実装している。
XACMLInterpreterは、引数に、使用するpolicyFile名、どのResourceにアクセスするか、どんな処理を行うか、許認可を求める人のUserID等を与える。

XAMLInterpreterでHandlerが使用しているイベントは、XMLReaderと同じで、startElement、charactor、endElement、endDocumentの4つを使用している。

startElementでは、主に評価関数や、評価関数の引数等を取得する。
また評価関数が入れ子になっていることがあるため、functionStackとattributeStackを用いて評価関数と引数を関連付けて
いる。図(\ref{fig:functionStack})の例だと、function3を実行した後、function3の返り値と、function2の引数の２つを使ってfunction2を実行する。
\begin{figure}[h]
\begin{center}
\includegraphics[height=5cm,bb=0 0 426 299]{fig/xacmlStack.pdf}
\caption{XACMLInterpreterで用いられているstack}
\label{fig:functionStack}
\end{center}
\end{figure}

charactorでは、評価関数の引数を取得し、AttributeStackにpushする
endElementでは。主に評価関数の実行を行う。
endDocumentでは、これまでに実行した評価関数等の結果から今回の許認可を判断する。

XACMLInterpreterを用いることでJungle単体でXACMLで記述されたポリシーファイルのテストが行えるようになった。