\chapter{Jungle上でのmatrixの実装}
\label{chap:poordirection}
前章では組織の中の許認可を管理するアプリケーションmaTrixについて説明を行った。
本章では、maTrixをJungle上にどのように実装するかを記述する。

\section{Jungle上でのmaTrixのデータ構造の表現}
maTrixは、前章でも説明したが、人物、役職、役割、といった情報を木構造で保持しており、それらのTreeはIDで参照しあっている。
人物Treeや役職Treeは、木構造のデータであるためそのままJungleに格納することができる。
実際に人物Treeを格納した際のデータの形を(図\ref{fig:PersonTree})に示した。(図\ref{fig:PersonTree})は前章で表示したPerson.xmlと対応している。
Tree間の参照は、TreeのデータはUniqueIdを保持しているため、Treeに対してIdで検索を行うことで表現した。


\begin{figure}[h]
\begin{center}
\includegraphics[height = 23cm , bb=150 0 1407 1603]{fig/JungleXmlTree.pdf}
\caption{Jungle上での人物Tree表現例}
\label{fig:PersonTree}
\end{center}
\end{figure}



\clearpage

JungleのTreeは、全てのversionのTreeでユニークなIdを保持しているため、Idを指定すれば、過去のTreeにアクセスすることが可能である。
それを利用し、Jungle上での過去の変更履歴を保持する構成情報モデルの表現は、構成情報モデルのversionと、各Treeのversionを保持し、関連付ける構成情報モデルTreeを作成し表現した。(図\ref{fig:configTree})。
\begin{figure}[h]
\begin{center}
\includegraphics[height = 8cm ,bb=0 0 530 347]{fig/configTree.pdf}
\caption{構成情報モデルTree表現例}
\label{fig:configTree}
\end{center}
\end{figure}



\begin{table}[h]
\caption{構成情報TreeのTreeNodeが保持しているAttribute}
\label{list:configTree}
\begin{center}
\begin{tabular}{|l|l|} \hline
version   & 構成情報モデルのversion　~ \\ \hline
person    & 構成情報モデルのversionに対応する人物Treeのversion ~\\ \hline
organization  & 構成情報モデルのversionに対応する組織Treeのversion ~ \\ \hline
role  & 構成情報モデルのversionに対応する役割Treeのversion  ~ \\ \hline
rde      & 構成情報モデルのversionに対応する役割記述要素Treeのversion ~\\ \hline
\end{tabular}
\end{center}
\end{table}


実際にどのようにJungle上で過去の構成情報モデルにアクセスするか、例題を用いて説明する。
構成情報モデルversion:3に対応する人物Treeにアクセスする手順を以下に示す。

\begin{enumerate}
\item 構成情報Treeからアクセスしたいversion情報を保持しているNodeを取得する(今回の例題ではversion3)
\item 取得したTreeNodeには、構成情報:version:3に対応した人物Treeなどのversionが記述されている(図\ref{fig:configTree})ので、人物Treeのverson(v:5)を取得する
\item ２で取得したversionの人物Treeにアクセスする。
\end{enumerate}
といった手順でJungleではmaTrixの構成情報モデルを表現する。
以下にJungle上での構成情報モデル表現例を図(\ref{fig:configTree2})を記す。

\begin{figure}[h]
\begin{center}
\includegraphics[height = 18cm ,bb=0 0 717 760]{fig/configModel.pdf}
\caption{構成情報モデルTree表現例2}
\label{fig:configTree2}
\end{center}
\end{figure}

\clearpage


\section{Jungle上の許認可}
Jungle上でmaTrixの許認可を行う際は、ポリシーファイルを読み込み、各Treeに対して検索関数を用いて、その結果から許認可を行う。

例えば、Aさんが、管理者しか閲覧出来ない資料を閲覧しようとした場合は

\begin{enumerate}
\item 人物Treeから、Aさんのデータを取得し、Aさんに割り振られている役割のIDを取得する。
\item 役割Treeから、1で取得した役割IDのデータを取得し、その役割IDに割り振られている役割記述要素IDを取得する
\item 役割記述要素Treeから、2で取得した役割記述要素IDのデータを取得し、役割記述要素名を取得する
\item 3で取得した役割記述要素名が、管理者かどうかを調べ、一致した場合はアクセスを許可し、一致しなかった場合はア
クセスを拒否する。
\end{enumerate}

といった流れになる。




\section{検索APIの実装}
Jungleは、データを格納するAPIは実装されていたが、データの検索を行うAPIの実装は行われていなかった。
しかし、Jungle上でmaTrixのデータ構造を表現、許認可を行うためには検索APIが必要であったため、実装を行った。



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

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}

find関数の処理の流れは、まず、Indexが登録されているかを調べる、Indexがある場合はIndexを使用し値を返す。Indexがない場合は、Treeを深さ優先で全探索する。(図\ref{fig:DepthFirstSearch})


\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を使用することで、更に限定的な探索が行えるようになった。

また、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のTreeMapを保持できる。
そのため、JungleのIndexと非常に相性が良い。
Indexは各JungleNodeがローカルにIndexを持つon the fly形式で実装する。(図\ref{fig:JungleIndex})

\begin{figure}[h]
\begin{center}
\includegraphics[height=5cm,bb=0 0 445 292]{fig/JungleIndes.pdf}
\caption{JungleのIndex}
\label{fig:JungleIndex}
\end{center}
\end{figure}


これまでのJungleのTreeの欠点として、親から子ノードを取得することは可能であったが、子ノードから親ノードを取得することは出来なかった。
そのため、Indexで取得できる値がNodeだけでは、Indexで検索を行って取得したNodeの編集が行えないため、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の型はTreeMap$<$String key,TreeMap$<$String value,List$<$TreeNode$>>>>$と定義できるようになった。

最初のTreeMap$<$String key,TreeMap$>$はIndexを格納するTreeMapである。
このTreeMapに対しkeyでgetを行うと、keyに対応するIndexが登録されている場合、Indexを取得でき、取得したIndexに対し
valueでgetを行うと、valueの値を持つNodeのListが返ってくる。

\section{親Nodeを返す特殊なIndex}
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}

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



\clearpage　

\section{過去のTreeに対するアクセス}
Jungle上でmaTrixの構成情報モデルの表現を行う際に、過去のTreeにアクセスする必要があるが、Jungleには、過去のTreeに対し、アクセスするAPIは実装されていなかったため、実装を行った。


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が見つからなかった場合は、エラーを返す。

\newpage

\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を作りそのNodeへ移動する。
その後、今いるNodeにAttributeの値を格納する。
charactorが呼ばれた時は、今いるNodeにテキストデータを格納する。
endElementが呼ばれたら、今いるNodeの親ノードに移動する。

以上の3つの関数を用いて、XMLのデータをTreeに格納していき、endDocumentが呼ばれた時に木のCommitを行っている。

\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で記述されたポリシーファイルのテストが行えるようになった。