土制状态机在工作流引擎中的应用

/**
  * @author : ahuaxuan
  * @date 2009-10-27
  */

很早之前（应该是一年以前），ahuaxuan在用dfa实现文字过滤一文中使用确定有限自动机实现了词典的高速查询。其实在当时那段时间里，由于对状态机有了一定的研究，ahuaxuan也触类旁通的理解了工作流引擎的核心体制。于是当时就用python写了一个小巧的工作流引擎的示例，在这之前ahuaxuan没有看过任何工作流引擎的实现，该实现纯属思维的自我延伸。

现在我来说说我的实现。
状态机的本质是状态的迁移，即从A状态+某个动作===》B状态。到这里我们还要来看看这张图。

从这张图中我们可以看到，状态（大写字母）+动作（小写字母）可以到达新的状态。那么对于程序员来说，我们要做的就是将这种机制用程序表达出来。比如说我们最常想到的是什么？矩阵!

这很好理解，但是对于工作流引擎来说，由于状态的迁移涉及到:当前状态+动作+条件===》新状态。
所以用二维的矩阵无法表示出这种逻辑。那么我们可以将矩阵中的元素替换为条件数组。
这样，我们可以通过当前状态+动作得到一个条件数组，然后再遍历这个条件数组，条件数组中的元素即是条件和满足条件的下一个状态(虽然本质上是一个三维数组，但是在这里还是看成矩阵+数组元素比较符合逻辑)。



这里需要画一个图，一个矩阵，矩阵中的元素是一个条件数组

没错，这是一种方案，但是这里有一个问题，那就是每次做状态迁移的时候，我们必须知道某个状态在矩阵一维上的index,已经某个动作在矩阵二维上的index.有了这两个index我们才能得到条件数组。所以这里还有一个繁琐的转换操作操作。来看一段伪代码：

conditions = matrix[getStatusIndex[‘A’], getActionIndex[‘a’]]
For condiction in conditions:
       If condition match input:
              Return Condition.nextStatus

核心流程大概就是这样，当

那么除了矩阵这种数据结构，我们还有其他的数据结构可以用来表示: “当前状态+动作+条件===》新状态”吗。

当然有，那就是使用树结构。在了解了三维数组的实现之后，再来看树实现，应该和容易了，那就直接上图， 将上图的矩阵转换成树结构之后，我们可以得到如下的树结构。



那现在我们来审视一下现在的问题，打个比方，我们现在手里有两张牌，一张是状态A,一张是动作a，我们如何通过这两种牌来得到条件集合呢，最简单的方法是首先遍历第二层节点，找到A，然后再遍历A的子节点，找到a。通过两次for循环找到了条件集合，而条件集合中包含着下一个状态。

那么有没有更简单更快速的方式可以直接找到条件集合，而直接跳过两次遍历呢。有，ahuaxuan的想法是tree+hash.也就是通过A的hash值，我们可以直接找到tree上的A节点。然后再通过a的hash值，我们可以直接找到A的子中的a节点。得到a节点之后我们就可以条件集合。那么我们可以用什么样的数据结构来实现一个这样的模型呢。这里面有hash运算，那么我们首先选择HashMap来创建这么一颗树。

我们来看一下这个定义：

Map<String, Map<String, Map<String, List<Transition>>>> dfa。

那么我们如何根据A,和a来得到一个条件集合呢？

Dfa.get[“processName”].get[“A”].get[“a”]

通过这样的方式，我们就可以根据当前状态和当前的动作得到一个条件集合。然后遍历这个条件集合就是找到满足“输入“的条件，该条件会指向下一个状态。

我们来看一下代码实现：
首先我们来构造这么一个状态机：

private void constructDfa(List<WfProcess> processList) {
		for (WfProcess pro : processList) {
			Map<String, Map<String, List<Transition>>> pmap = new HashMap<String, Map<String,List<Transition>>>();
			dfa.put(pro.getName(), pmap);
			
			for (State sta : pro.getStates()) {
				Map<String, List<Transition>> smap = new HashMap<String, List<Transition>>();
				pmap.put(String.valueOf(sta.getName()), smap);
				
				for (Action action : sta.getActions()) {
					List<Transition> transitions = new ArrayList<Transition>();
					for (String transName : action.getTransNames()) {
						transitions.add(pro.getTransitions().get(transName));
					}
					
					smap.put(String.valueOf(action.getName()), transitions);
				}
				
			}
		}
	}

接着我们来看看如何根据这个状态机来做状态迁移：

public String getNextState(String processName, String stateId, String actionId, Map<String, String> conditions) {
		
		List<Transition> transitions = dfa.get(processName).get(String.valueOf(stateId)).get(String.valueOf(actionId));
		
		for (Transition trans : transitions) {
			if (match(trans.getConditions(), conditions)) {
				return trans.getToState();
			}
		}
		
		StringBuilder sb = new StringBuilder();
		sb.append("There is no state for process : ").append(processName);
		sb.append(", stateId : ").append(stateId);
		sb.append(", actionId : ").append(actionId);
		sb.append(", conditions : ").append(conditions);
		
		throw new WorkFlowStateException(sb.toString());
	}

通过这种tree + hash的方式，我们可以很容易的进行状态的迁移，不需要那么多for循环。但是for循环确实有这样的实现。

今天早上下载了osworkflow的代码，稍微看了一下AbstractWorkflow的doAction方法。
发现osworkflow就是通过循环来实现状态的迁移的，比如说上图中树结构的状态可以用以下伪代码：

For state in states:
	If state.name == inputStateName:
		For action in state.actions:
			If action.name == inputActionName:
					for transition in action.transitions:
	…………………………………………………………………

通过这种方式，用户传入inputStateName和inputActionName, osworkflow得到了一组transition,并根据条件选择某个transition, 这样也实现了状态的转移。

从这里面可以看出，osworkflow是利用广度优先的原则，先找到符合条件的state,然后再找到符合条件的action，以此类推。

说到这里，通过这种状态机实现工作流引擎的方式基本的完全的，较为清晰的呈现在我们眼前了。

未完待续

评论

2 楼 ahuaxuan 2009-11-02  

把动作和条件合并在一起的做法不太流行


动作是一个操作，条件是对业务数据的一个抽象。
比如动作是一个类的方法，而条件是方法的参数决定的，这样更合理一些

1 楼 melin 2009-11-02  

打算写一个小的工作流引擎：
定义的流程定义为：

<processdefine name="TestFlow" version="1.1.1" description="">
	<Activitys>
		<Activity id="start" type="start" name="开始" description="">
			<SplitMode>XOR</SplitMode>
		</Activity>
		<Activity id="A01" type="manual" name="申请" description="">
			<SplitMode>XOR</SplitMode>
			<JoinMode>XOR</JoinMode>
			<participantType>organization</participantType>
			<participantList>
				<participant id="910150" name="俞文琦" type="person"/>
				<participant id="910115" name="李强" type="person"/>	
			</participantList>
		</Activity>
		<Activity id="A02" type="manual" name="审核" description="">
			<SplitMode>XOR</SplitMode>
			<JoinMode>XOR</JoinMode>
			<participantType>process-starter</participantType>
		</Activity>
		<Activity id="end" type="finish" name="结束" description="">
			<JoinMode>XOR</JoinMode>
		</Activity>
	</Activitys>
	
	<Transitions>
		<Transition id="" from="start" to="A01" name="">
			<IsDefault>true</IsDefault>
		</Transition>
		<Transition id="" from="A01" to="A02" name="">
			<IsDefault>true</IsDefault>	
		</Transition>
		<Transition id="" from="A02" to="end" name="">
			<IsDefault>false</IsDefault>
			<Expression>optId==1</Expression>
		</Transition>
	</Transitions>
</processdefine>

查找当前环节的后续环节为：

public Transition[] getNextTransitions(String aid) {
		Transition[] arr = null;
		List<Transition> list = new ArrayList<Transition>();
		Iterator<Transition> it = this.transitions.iterator();
		while (it.hasNext()) {
			Transition trans = it.next();
			if (trans.getFrom().equals(aid))
				list.add(trans);
		}
		arr = new Transition[list.size()];
		for (int i = 0; i < arr.length; ++i) {
			arr[i] = ((Transition) list.get(i));
		}
		return arr;
	}

查找满足条件的transition

public static List<String> getPossilbeListNormal(WFProcessInstance pi,
			Activity actDef, Transition[] transarr) {
		List<String> possibleList = new ArrayList<String>(4);

		if (actDef.getSplitMode().equals("AND")) {
			for (int i = 0; i < transarr.length; ++i) {
				possibleList.add(transarr[i].getTo());
			}
		} else {
			Transition[] oktrans;
			int i;
			if (actDef.getSplitMode().equals("XOR")) {
				oktrans = getXORModeNextTrans(transarr, pi.getRelDataMap());

				Transition tran = findMostOKByPrority(oktrans);

				possibleList.add(tran.getTo());
			} else if (actDef.getSplitMode().equals(DefineConst.SPLIT_MODE_OR)) {
				oktrans = getORModeNextTrans(transarr, pi.getRelDataMap());

				if (oktrans.length == 0) {
					return possibleList;
				}

				for (i = 0; i < oktrans.length; ++i) {
					possibleList.add(oktrans[i].getTo());
				}

			}

		}

		return possibleList;
	}