drools源码分析,rete源码分析,rete算法.doc

源码分析报告源码分析报告11.前言32.规则包格式33.规则编辑83.1AbstractRuleBase83.2ReteooRuleBase103.3ReteooBuilder103.4ReteooRuleBuilder113.5Rule133.6LogicTransformer（有待具体详细分析）133.7ReteooComponentBuilder(部分继承关系)153.8ObjectTypeNode233.9ObjectSinkPropagator263.10BuildUtils313.11NetWorkNode(部分继承关系)333.12Sink(部分继承关系)403.13Rete413.14FieldIndex414.运行时执行424.1ReteooRuleBase424.2AbstractRuleBase434.3ReteooStatefulSession444.4ReteooWorkingMemory444.5AbstractWorkingMemory/1484 row464.6ReteooFactHandleFactory524.7AbstractFactHandleFactory534.8PropagationContext534.9Rete / 678 row544.10ObjectTypeNode604.11ObjectSinkPropagator接口614.12AlphaNode/370 row664.13LeftInputAdapterNode674.14TupleSinkPropagator684.15JoinNode704.16RuleTerminalNode724.17BetaNode774.18BetaMemory774.19TupleMemory784.20ClassFieldExtractor784.21ReteTuple784.22BetaConstraints804.23VariableConstraint(Beta)834.24VariableRestriction834.25AbstractHashTable874.26PrimitiveLongMap874.27PrimitiveLongStack884.28TruthMaintenanceSystem884.29DefaultFactHandle884.30DefaultAgenda894.31AgendaItem904.32BinaryHeapQueueAgendaGroup914.33DefaultExecutorService924.34PackageCompilationData924.35PatternBuilder/0.1与初始事实有关924.36ObjectTypeNode/0.1与初始事实有关934.37DefaultKnowledgeHelper934.38ClassObjectType944.39ValueType944.40AlphaNodeFieldConstraint955.总结951. 前言RETE算法一般可以分为两个部分：规则编辑和运行时执行。规则编辑描述规则库中的规则如何生成一个有效的具有分辨力的网络即RETE网络；运行时执行描述工作区中加入事实后如何在RETE网络中传递到网络的根节点。本源码分析报告仅仅分析上述的两个部分，对规则包Package的构建不予分析，只是对规则包格式加以说明。2. 规则包格式应用场景以DEMO程序中修改的两条规则为例说明JAVA规则包的格式。（应用场景将在后续版本中修改）规则例子1：whenFeeList(userType = 01 )or FeeList(userType = 04 , callType = 32)and FeeList(userType = 03 , callType = 32)thenSystem.out.println(启动测试规则);规则例子2：when($feeList : FeeList(callStartTime 6)and FeeList(callEndTime 22)$basicfeePlan : BasicfeePlan()$longfeePlan : LongfeePlan();thenSystem.out.print(获得从忙时跨越到闲时的通话时长 : );System.out.print(忙时时长+$basicfeePlan.getBusyTime()+s + ； );System.out.println(闲时时长+$basicfeePlan.getIdleTime()+s);经过编译后，产生的 Package对象结构如下：其中rules为存放规则的HashMap，其中键为规则的名字，值为Rule对象：在进行 addPackage 并建立 Rete 网络阶段，我们重点关注 lhsRoot 属性，对于规则例子1 ，只有一个children其类型为GroupElement，其结构如下：默认情况下，所有 GroupElement.type 属性都是 AndType, 即此 GroupElement 内元素之间的逻辑关系为 AND继续细分顶层 GroupElement 结构如下：FeeList(userType = 01 ) 已经是一个独立的 Pattern , 而由于后面的两个模式有 AND 的逻辑关系，所以两个模式又都被归并到一个 GroupElement 中，而当前元素之间是 OR 的逻辑关系 type 为 OrType继续对后半部分 GroupElement 继续细分则结构如下：FeeList(userType = 04 , callType = 32)and FeeList(userType = 03 , callType = 32) 两个模式分别用两个 Pattern 保存，关系为逻辑 AND同理，对于规则例子2，lhsRoot含有3个孩子，其类型为Pattern，结构如下：对于规则例子2 中 Pattern 具体分析：($feeList : FeeList(callStartTime 6)and FeeList(callEndTime 22)$basicfeePlan : BasicfeePlan()$longfeePlan : LongfeePlan();Pattern(194) 包装模式 $feeList : FeeList(callStartTime 6)其中有两个约束 callStartTime 6 分别包装在 LiteralConstraint(224,226)中，只针对 callStartTime 22 分析其包装，主要是 restriction 属性描述了这个模式约束 ，结构如下：注意: 此处要重点分析模式中真正的约束条件是怎么包装的。 LiteralRestriction(269).extractor(267) 对于提取同一个类（FeeList）的某一个属性值(callStartTime)是共享的，从extractor(267).clazz 属性看出提取的那一个类 ，从extractor(267).fieldName 看出提取的类域名，而extractor(267).extractor(286)则针对 FeeList 中某一个属性(CallStartTime)值进行提取,在 extractor(286) 中可以看到要提取的 callStartTime 值是一个 int 类型； LiteralRestriction.evaluator 表示运算符（ 22)注意： 1. 后面会分析小括号归属于 GroupElement 中，并会打包，去掉冗余逻辑的过程，并把 OR 逻辑提取到最外层2. FeeList 类信息的共享，提取器的构造。Clazz(284)Pattern (187) 包装模式 $basicfeePlan : BasicfeePlan()由于模式中没有定义约束，所以 constraint 属性为 Collection$EmptyList(489)模式$longfeePlan : LongfeePlan() 同理，不再具体描述。分析 Drools 执行 addPackage(Package) 的具体过程：为了能够比较全面的分析整个过程，包括：节点共享，提取 OR 逻辑，使用 $Declaration 这些功能，编写了以下规则：此例子的 Package 包装形式在 (六) LogicTransformer 可见以下文档整个 addPackage 过程所产生的 Rete 网络也都以这个例子规则说明。/规则初始化化部分rule startTestno-loop true /执行一次后，是否能被再次激活 salience 100 /优先级别when / 此处特意写了 ( A and B ) and C 的逻辑冗余形式，主要是观察等价转化为 A and B and C 的过程( FeeList(userType = 01 , callType = 00 ) and $basic : BasicfeePlan(basicFeeTime 10) )and FeeList(userRoamArea = 1003)or FeeList(userType = 03 , roamType = 32)FeeList(roamType = 03)thenSystem.out.println(启动测试规则 . BasicFee is : + $basic.getBasicFee() );System.out.println(使用 function getAmoutTime 让 BasiceFee + 9 结果为 : + （9 + $basic.getBasicFee() );end代码中构造出的对象：FeeList 对象 = userType = “01” , callType = “00” , userRoamArea = 1003 , roamType = “03” BasicefeePlan 对象 = basicFeeTime = 0.0 3. 规则编辑3.1 AbstractRuleBase部分函数说明：1. addPackage( Package newpkg )1) 保持多线程资源同步 synchronized ( this.pkgs )2) 查看是否已经有了此包final Package pkg = (Package) this.pkgs.get( newPkg.getName() );3) 事件this.eventSupport.fireBeforePackageAdded( newPkg );4) 当 this.pkgs 中已经有此名称的 Package 时if ( pkg != null ) 要合并 mergePackage( pkg, newPkg );否则加入到 this.pkgs 中 this.pkgs.put( newPkg.getName(), newPkg );5) 取得全局变量 Map newGlobals = newPkg.getGlobals(); 并判断是否合理，加入到 this.globals 中6) 取得 Package 中的规则Rule rules = newPkg.getRules();依次对规则执行for ( int i = 0; i rules.length; +i ) addRule( newPkg, rulesi );7) 事件this.eventSupport.fireAfterPackageAdded( newPkg );2. addRule(Package , Rule)1) 事件this.eventSupport.fireBeforeRuleAdded( pkg,rule );2) 执行 addRule(rule)3) 事件this.eventSupport.fireAfterRuleAdded( pkg, rule );3. addRule(Rule) 一个抽象方法，具体实现在 ReteooRuleBase 类中3.2 ReteooRuleBaseorg.drools.reteoo;部分函数说明：1. addRule(Rule)this.reteooBuilder.addRule( rule ); 构建 Rete 网络的过程以 ReteooBuilder 类实例为入口开始3.3 ReteooBuilderorg.drools.reteoo;部分属性说明：rules:Map存放Rule与RuleTerminalNode之间的映射关系部分函数说明：1. addRule(Rule) 调用内部 ReteooRuleBuilder 属性的方法，开始真正的建立 Rete 网络的工作List terminals = this.ruleBuilder.addRule( rule, this.ruleBase, this.idGenerator );3.4 ReteooRuleBuilderorg.drools.reteoo.builder;部分函数说明：1. addRule(Rule , ReteooRuleBase , ReteooBuilder.IdGenerator)a. GroupElement subrules = rule.getTransformedLhs();getTransformedLhs() 方法具体见 (五)Rule 类如果规则 Rule 中包含 OR 逻辑，则把两个逻辑分别拆成两个不同的 GroupElement 中分别作为 subrulesi 和 subrulesj 来分别处理，同时如果规则中有冗余的括号，例如 (a AND b) AND c会把其优化为 a AND b AND c,因为括号中的元素以一个 GroupElement 整体出现，而后面我们会看到，一个 GroupElement 在 Rete 网络中对应一个 TerminalNode, 如果有冗余小括号则会出现逻辑错误, 而 OR 逻辑的两个分支分别对应一个 TerminalNode, 即只要有一个匹配到就可以执行规则。最后返回的subrules 数组包含了所有 AND 逻辑运行分支。经过打包去冗余小括号，并提取 OR 逻辑后，以我们的例子，得到的 subrules数组如下：b. for ( int i = 0; i subrules.length; i+ )依次将 subrules 中的各个GroupElement元素加入到 Rete网络中：i. 建立构造 Rete 网络时必须的上下文对象:BuildContext context = new BuildContext( rulebase,idGenerator );context 起到暂存,中间变量的作用，用于在构建 Rete 网络时中间保存父节点，构建父子关系,同时 context 也负责为新构建的 Rete 网络内节点分配 ID 号ii. 默认情况下，ruleBase.getConfiguration.Sequential 属性从外部文件读入值为 false, 所以接下来按照如下方式设置 context 属性/ 默认情况下执行此段 isSequential = false context.setTupleMemoryEnabled( true ); context.setObjectTypeNodeMemoryEnabled( true ); context.setTerminalNodeMemoryEnabled( true ); context.setAlphaNodeMemoryAllowed( true ); iii. TerminalNode node = this.addSubRule( context,subrulesi,rule ); 具体见本类此函数 函数整个过程将会把GroupElement 中的所有 Pattern（GroupElement.childeri）加入到 Rete 网络中并返回针对本条 GroupElement 的最后出口节点iv. nodes.add( node ); 返回（三)ReteooBuilder. addRule(Rule)2. addSubRule( BuildContext , GroupElement , Rule )a ReteooComponentBuilder builder = this.utils.getBuilderFor( subrule ); 首先根据元素类型获得对应的构造组件,subrule 是一个 GroupElement 所以 builder 类型为 GroupElementBuilder由于本次迭代中去除了Not，所以不需要初始事实的加入b builder.build( context,this.utils,subrule );具体见（七）ReteooComponentBuilder。GroupElementBuilder所有 GroupElement 加入 Rete 网络的工作都由专门的 GroupElementBuilder 实例来完成 返回 (四) ReteooRuleBuilder.addRule b.3c 加入TerminalNode 根据当前上下文新建一个终止节点terminal = new RuleTerminalNode ( context.getNextId(), context.getTupleSource(), rule, subrule, context );将终止节点加入当网络中terminal.attach();返回一个TerminalNode对象。3.5 Ruleorg.drools.rule;部分函数说明：1、 getTransformedLhs()return LogicTransformer.getInstance().transform( this.lhsRoot ); 具体分析见 (六) LogicTransformer类把 AND 运算都放到小括号中作为支路运算，最外层只有 OR 运算。产生一个 LogicTransformer(单体模式)对象执行3.6 LogicTransformer（有待具体详细分析）org.drools.rule;1、 transform(GroupElement and)a.先克隆一个副本GroupElement cloned = (GroupElement) and.clone();b.递归遍历整个 GroupElement 并去掉冗余：processTree( cloned );2、processTree(GroupElement ce) a.将表达式中的逻辑冗余去掉，主要是去掉冗余的小括号 ce.pack(); 具体看 GroupElement.pack() b.取出GroupElement 中的子元素并保存在数组中Object children = (Object) ce.getChildren().toArray(); c. for ( int i = 0; i children.length; i+ ) 对每一个childreni 依次递归遍历，遇到子元素也为 GroupElement 类型的就对其执行一次打包 pack()操作去掉冗余的小括号，并提出 OR 逻辑。提取 OR 逻辑的过程可以参看内嵌在 LogicTransformer 类中的 AndOrTransformation 类中的 transform 方法。由于过程复杂不在这里描述例如我们之前的例子：when / 此处特意写了 ( A and B ) and C 的逻辑冗余形式，主要是观察等价转化为 A and B and C 的过程( FeeList(userType = 01 , callType = 00 ) and $basic : BasicfeePlan(basicFeeTime 10) )and FeeList(userRoamArea = 1003)or FeeList(userType = 03 , roamType = 32)FeeList(roamType = 03)开始时的结构如下：FeeList(userType = 01 , callType = 00 ) Pattern (123)$basic : BasicfeePlan(basicFeeTime 10) Pattern (124)FeeList(userRoamArea = 1003) Pattern (95)FeeList(userType = 03 , roamType = 32) Pattern (81)FeeList(roamType = 03)Pattern (92)而去掉冗余小括号，提取 OR 逻辑到最外层，得到的逻辑等价结构如下：FeeList(userType = 01 , callType = 00 ) Pattern (123)$basic : BasicfeePlan(basicFeeTime 10) Pattern (124)FeeList(userRoamArea = 1003) Pattern (95)FeeList(userRoamArea = 1003 , roamType = 03 )Pattern(283)FeeList(userType = 03 , roamType = 32) Pattern (81)FeeList(userRoamArea = 1003 , roamType = 03)Pattern(292)其中 Pattern(283).constraints.restriction2(356 , 357) 属性与 Pattern(292).constraints.restriction2(328 , 322) 属性没有共享。经过打包后，得到的规则等价为：FeeList(userType = 01 , callType = 00 ) and $basic : BasicfeePlan(basicFeeTime 10)and FeeList(userRoamArea = 1003)and FeeList(userRoamArea = 1003 , roamType = 03 )or FeeList(userType = 03 , roamType = 32) and FeeList(userRoamArea = 1003 , roamType = 03)将原本嵌入在内的 OR 逻辑提出到最外层。(这种逻辑等价变化的过程值得细致研究。)返回 (四) ReteooRuleBuilder.addRule a.3.7 ReteooComponentBuilder(部分继承关系)3.7.1 GroupElementBuilderorg.drools.reteoo.builder;部分函数说明：Build(BuildContext context , BuildUtils utils, RuleCondtionElement rce)a. GroupElement ge = (GroupElement) rce; b. ReteooComponentBuilder builder = (ReteooComponentBuilder) this.geBuilders.get( ge.getType() );通过 getType() 方法得到 GroupElement.Type 为 AndType ，此时得到的 builder 类型为 AndBuilderc. builder.build( context,utils,rce );由于多个 Pattern 在 GroupElement 中是默认(And) 关系，则调用 AndBuilder.build()具体见抽象类 AndBuilder 返回（四）.addSubRule 2. c.3.7.2 AndBuilderorg.drools.reteoo.builder;部分函数说明：Build(BuildContext context , BuildUtils utils, RuleCondtionElement rce)a. GroupElement ge = (GroupElement) rce;b. for ( final Iterator it = ge.getChildren().iterator(); it.hasNext(); ) 把GroupElement.children 中所有Pattern 加入Rete网络i. RuleConditionElement child = (RuleConditionElement) it.next();取出一 child 例如: Pattern(137) ReteooComponentBuilder builder = utils.getBuilderFor( child );根据此 child 类型得到相应的构造器 builder.build( context,utils,child ); 此时，例子中的构造器都是 PatternBuilder 类型，见 PatternBuilder.build ii. 构造好一个 Pattern 后要根据情况构造 LeftInputAdapterNode 或 JoinNode情况1：对于第一个模式：FeeList(userType = 01 , callType = 00 )，此时context.ObjectSource 记录着刚刚把 Pattern 加入 Rete 网络时，最后一个约束（callType = 00）所绑定的 AlphaNode 。而下一个模式: $basic : BasicfeePlan(basicFeeTime 10)与其是 AND 逻辑而且之前，上下文context 中没有对 TupleSource 节点的记录。此时加入 LeftInputNode，可以认为建网络的第一阶段完成，开始进入第二阶段。/如果context记录的一个先前的objectTypeNode被绑定，并且当前的上下文中没有TupleSource则建立LeftInputNode。if ( context.getObjectSource() != null & context.getTupleSource() = null )/ adapt it to a Tuple source/ 此处新建一个 LeftInputAdapterNode 节点/ 具体见 LeftInputAdapter / 把LeftInputNode节点加入网络具体见 Utils.attachNodecontext.setTupleSource( (TupleSource) utils.attachNode( context, new LeftInputAdapterNode( context.getNextId(), context.getObjectSource(),context ) ) );此图为构造新的 LeftInputNode ,父节点为 AlphaNode,子节点集合 sink 为空类型/ 当第二阶段开始时，就把上下文 context 中的 objectSource 设为 null/ 开始分析下一个 Pattern , 上下文开始记录新的 AlphaNodecontext.setObjectSource( null );/此时的ObjectSource已经转换为LeftInputNode，需要清空/ 而上下文 context 记录下了上一个 Pattern 结束时的 LeftInputNode 情况2：/ 当第二个模式 ： $basic : BasicfeePlan(basicFeeTime 10)/ 也分析完毕后，此时上下文 context.ObjectSource 为/ （basicFeeTime 10） AlphaNode , context.TupleSource为/ 上一个 Pattern 完成后的 LeftInputNode./ 之后同属于一个 GroupElement 中的所有 Pattern ，他们都是 AND 逻辑关系/ 上下文都会以 JoinNode 链接两个 Pattern 。JoinNode 左父亲为上一个 Pattern 的结尾 JoinNode , 右父亲为本 Pattern 的最末约束 AlphaNode.直到循环结束if ( context.getObjectSource() != null & context.getTupleSource() != null )/ 在 Rete 网络中增加 JoinNode，用于链接两个 AND 逻辑的 Pattern/ 建立 JoinNode 具体见 JoinNode , 加入 Rete 网络具体见 Utils.attach/ 之后把上下文 context.TupleSource 设为此 JoinNodecontext.setTupleSource( (TupleSource) utils.attachNode( context,new JoinNode( context.getNextId(), context.getTupleSource(), context.getObjectSource(),betaConstraints,context ) ) ); 例如：执行完$basic : BasicfeePlan(basicFeeTime 10)后 JoinNode 如下： / 与情况1相同，把上下文 ObjectSource 刷新，保留 TupleSource 记录context.setBetaconstraints( null );context.setObjectSource( null );/end if/end for，步骤b结束 循环结束，返回 GroupElementBuilder.build3.7.3 PatternBuilderorg.drools.reteoo.builder;部分函数说明：1. Build(BuildContext context , BuildUtils utils, RuleCondtionElement rce) a. Pattern pattern = (Pattern) rce; b. this.attachPattern( context, utils, pattern ); 真正执行把 pattern 加入到网络中的操作 返回 AndBuilder.build .b22. attachPattern (BuildContext context, BuildUtils utils, Pattern pattern) a. final List alphaConstraints = new LinkedList();final List betaConstraints = new LinkedList();先构造出两个链表，用于区分 Pattern 中的 Constraint 属性属于哪一类，对我们的例子来书，上文可见，所有的Pattern . Constraint 属性都是LiteralConstraint 属于 ALPHA 类型的 Constraint b this.createConstraints( context,utils,pattern,alphaConstraints,betaConstraints );1. 检测相同的模式是否应该禁用（配置文件中设置）checkRemoveIdentities( context, pattern, betaConstraints );待深入2. 如果为申明约束Declaration则忽略3. 如果约束类型为Alpha约束，则加入alphaConstrains如果约束类型为Beta约束，如果需要的申明先前已经绑定BuildUtils.checkUnboundDeclarations则加入betaConstraints。 当前分析的所有 Constriants(LiteralConstraint) 都加入了 alphaConstrains 列表中,而betaConstraints 列表保持空此为加入例子中 Pattern(123) 时的链表c. if ( pattern.getSource() = null )attachAlphaNodes( context,utils,pattern,alphaConstraints );接下来就开始构建 AlphaNode , 在 AlphaNode 中描述的就是这些约束，要加入的约束已经绑定在链表中。注意 Pattern 中的约束是需要逻辑”与”匹配的，具体构建过程以及细节见下面的 attachAlphaNodes() 函数 else /待研究 context.setAlphaConstraints( alphaConstraints ); final int currentOffset = context.getCurrentPatternOffset(); PatternSource source = pattern.getSource(); ReteooComponentBuilder builder = utils.getBuilderFor( source ); builder.build( context, utils, source ); / restoring offset context.setCurrentPatternOffset( currentOffset ); d. context.incrementCurrentPatternOffset();/ last thing to do is increment the offset, since if the pattern has a source,/ offset must be overridden 返回 PatternBuilder.build .b3. attachAlphaNodes(BuildContext context,BuildUtils utils, Pattern pattern,List alphaConstraints)a boolean objectMemory = context.isObjectTypeNodeMemoryEnabled(); boolean alphaMemory = context.isAlphaMemoryAllowed();之前初始化设置 BuildContext 时已经把 ObjectTypeNodeMemory / AlphaMemory 功能打开，此处两个都是 true.b context.setObjectSource( (ObjectSource) utils.attachNode(context, new ObjectTypeNode(context.getNextId(), pattern.getObjectType()context)new ObjectTypeNode(context.getNextId(),pattern.getObjectType()，context)新建一个ObjectTypeNode节点，其父节点为网络的根节点Rete（objectSource属性标识），子节点为AlphaNode（当前为EmptyObjectSinkAdapter的一个实例，sink属性标识）此时开始构建 Rete 网络的第一层，即入口层：ObjcetTypeNode 节点,具体参见 (八)ObjectTypeNode 。该节点的作用是为了描述规则中各种模式所用到的类，并封装此信息。此时对于模式 Pattern(137) 而言具体如下：对于当前例子中分析的模式：FeeList(userType = 01 , callType = 00 ) Pattern (123)我们要取的类型是自定义的 FeeList ,所以getObjectType()返回的是描述 FeeList 类信息的ClassObjectType另外我们看到 context 对象的一个作用就是为构造的 Rete 网络上的节点分配 ID 号。此处的构造函数分析见 (八)ObjectTypeNode。 构造好 ObjectTypeNode 后将调用 utils.attachNode()判断之前在 Rete 网络中是否已经存在这个节点，这个过程具体见 (十)BuildUtils.attachNode当把 ObjectTypeNode 节点加入到 Rete 网络以后，则设置上下文的 ObjectSource 为此节点。这样就能够在加入下一个 AlphaNode 时构建其与这个 ObjectTypeNode 之间的父子关系。此时上下文context暂存，中间记录的功能就得以体现。图为上下文记录刚刚加入 Rete 网络的 ObjectSource 节点；注意 tupleSource 属性是用来记录LeftInputNode 或 JoinNode 等节点的，这在后面会介绍到。c for ( final Iterator it = alphaConstraints.iterator(); it.hasNext(); )把当前模式 Pattern 中的alphaConstraints约束依次绑定到 AlphaNode 中，并把此节点加入到 Rete 网络中。注意：此处只是对与alphaConstraints才生成AlphaNode并加入网络，而对于betaConstraints不生成AlphaNode，只是生成ObjectT