[Javapathfinder-svn] SF.net SVN: javapathfinder:[1814] branches/mango/Mango

[<fra...@us...>]

Revision: 1814
          http://javapathfinder.svn.sourceforge.net/javapathfinder/?rev=1814&view=rev
Author:   frankrimlinger
Date:     2009-08-08 23:28:10 +0000 (Sat, 08 Aug 2009)

Log Message:
-----------
The secondary hash idea still has the linear time in the number of rules matching problem, so decided on a filter tree instead.  This reduces the matching problem to about (2^number of wildcards)*(number of arguments+2) steps.  The filter design is

class RuleFilter{
	RuleFilter wildFilter
	HashMap<Object, RuleFilter > keyFilterMap
	HashSet<Rule> rules
}

Pattern encoding starts at the topFilter, using the lead ruleKey.  The variable length patterns bottom out immediately, everybody else then matches on argument length followed by the key for each individual argument, with wildcards matching on the wildFilter.  When the pattern bottoms out, it adds the corresponding rule to the rules member of the bottom filter.  When matching, each step will generally match on the wildFilter and a filter from the keyFilterMap, which is quite acceptable since number of wildcards <= number of arguments <4 with very few exceptions.  The rules from each bottom filter are then concatenated to form the rules forwarded to the unifier for unification.  This should dramatically decrease the load on the unifier.

With all this in place, hook up rule indexing update when rules are added/deleted, regardless of whether they are template, variable length, or "normal" rules.  These updates are no longer handled via the messaging system, but happen naturally as rules are created/deleted.  The details of template updating are elaborate and contained in the new "rule template" document.

The real reason for cleaning this up is to pave the way for new growth in the area of dynamic rule generation.  In particular, stable rules and composition rules should be generated dynamically.  Also, much could be done to ease the pain of translation rules.

Modified Paths:
--------------
    branches/mango/Mango/Mango/src/mango/core/sym/RuleVariable.java
    branches/mango/Mango/Mango/src/mango/worker/engine/hash/symbolHash/SymbolHashTyping.java
    branches/mango/Mango/Mango/src/mango/worker/engine/rule/Rule.java
    branches/mango/Mango/Mango/src/mango/worker/engine/rule/RuleGenerator.java
    branches/mango/Mango/Mango/src/mango/worker/engine/rule/TemplateRuleManager.java
    branches/mango/Mango/Mango/src/mango/worker/engine/sym/ClassNameSym.java
    branches/mango/Mango/Mango/src/mango/worker/engine/sym/ClinitWasCalledSym.java
    branches/mango/Mango/Mango/src/mango/worker/engine/sym/GenericMethodNameSym.java
    branches/mango/Mango/Mango/src/mango/worker/engine/sym/ImmutableSym.java
    branches/mango/Mango/Mango/src/mango/worker/engine/sym/InstructionNameSym.java
    branches/mango/Mango/Mango/src/mango/worker/engine/sym/InvocationNameSym.java
    branches/mango/Mango/Mango/src/mango/worker/engine/sym/Marker.java
    branches/mango/Mango/Mango/src/mango/worker/engine/sym/NullObject.java
    branches/mango/Mango/Mango/src/mango/worker/engine/sym/Other.java
    branches/mango/Mango/Mango/src/mango/worker/engine/sym/StringSym.java
    branches/mango/Mango/Mango/src/mango/worker/engine/sym/Sym.java
    branches/mango/Mango/Mango/src/mango/worker/utilities/Util.java
    branches/mango/Mango/javapathfinder-mango-bridge/mango/scanner/sym/InstructionSym.java

Added Paths:
-----------
    branches/mango/Mango/Mango/src/mango/worker/engine/rule/RuleFilter.java
    branches/mango/Mango/Mango/src/mango/worker/engine/rule/RuleFilterManager.java
    branches/mango/Mango/doc/rule template.txt

Removed Paths:
-------------
    branches/mango/Mango/Mango/src/mango/core/sym/PrimaryRuleGroup.java
    branches/mango/Mango/Mango/src/mango/worker/engine/rule/RuleCensus.java


This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.