Back to index

lightning-sunbird  0.9+nobinonly
nsRuleNetwork.h
Go to the documentation of this file.
00001 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
00002 /* ***** BEGIN LICENSE BLOCK *****
00003  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00004  *
00005  * The contents of this file are subject to the Mozilla Public License Version
00006  * 1.1 (the "License"); you may not use this file except in compliance with
00007  * the License. You may obtain a copy of the License at
00008  * http://www.mozilla.org/MPL/
00009  *
00010  * Software distributed under the License is distributed on an "AS IS" basis,
00011  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00012  * for the specific language governing rights and limitations under the
00013  * License.
00014  *
00015  * The Original Code is mozilla.org code.
00016  *
00017  * The Initial Developer of the Original Code is
00018  * Netscape Communications Corporation.
00019  * Portions created by the Initial Developer are Copyright (C) 2000
00020  * the Initial Developer. All Rights Reserved.
00021  *
00022  * Contributor(s):
00023  *   Chris Waterson <waterson@netscape.com>
00024  *
00025  * Alternatively, the contents of this file may be used under the terms of
00026  * either of the GNU General Public License Version 2 or later (the "GPL"),
00027  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00028  * in which case the provisions of the GPL or the LGPL are applicable instead
00029  * of those above. If you wish to allow use of your version of this file only
00030  * under the terms of either the GPL or the LGPL, and not to allow others to
00031  * use your version of this file under the terms of the MPL, indicate your
00032  * decision by deleting the provisions above and replace them with the notice
00033  * and other provisions required by the GPL or the LGPL. If you do not delete
00034  * the provisions above, a recipient may use your version of this file under
00035  * the terms of any one of the MPL, the GPL or the LGPL.
00036  *
00037  * ***** END LICENSE BLOCK ***** */
00038 
00039 /*
00040 
00041   A rule discrimination network implementation based on ideas from
00042   RETE and TREAT.
00043 
00044   RETE is described in Charles Forgy, "Rete: A Fast Algorithm for the
00045   Many Patterns/Many Objects Match Problem", Artificial Intelligence
00046   19(1): pp. 17-37, 1982.
00047 
00048   TREAT is described in Daniel P. Miranker, "TREAT: A Better Match
00049   Algorithm for AI Production System Matching", AAAI 1987: pp. 42-47.
00050 
00051   --
00052 
00053   TO DO:
00054 
00055   . nsAssignmentSet::List objects are allocated by the gallon. We
00056     should make it so that these are always allocated from a pool,
00057     maybe owned by the nsRuleNetwork?
00058 
00059  */
00060 
00061 #ifndef nsRuleNetwork_h__
00062 #define nsRuleNetwork_h__
00063 
00064 #include "nsCOMPtr.h"
00065 #include "nsIContent.h"
00066 #include "plhash.h"
00067 #include "pldhash.h"
00068 #include "nsCRT.h"
00069 
00070 class nsIRDFResource;
00071 class nsIRDFNode;
00072 
00073 //----------------------------------------------------------------------
00074 
00079 class Value {
00080 public:
00081     enum Type { eUndefined, eISupports, eString, eInteger };
00082 
00083 protected:
00084     Type mType;
00085 
00086     union {
00087         nsISupports* mISupports;
00088         PRUnichar*   mString;
00089         PRInt32      mInteger;
00090     };
00091 
00092     PRBool Equals(const Value& aValue) const;
00093     PRBool Equals(nsISupports* aISupports) const;
00094     PRBool Equals(const PRUnichar* aString) const;
00095     PRBool Equals(PRInt32 aInteger) const;
00096 
00097     void Clear();
00098 
00099 public:
00100     Value() : mType(eUndefined) {
00101         MOZ_COUNT_CTOR(Value); }
00102 
00103     Value(const Value& aValue);
00104     Value(nsISupports* aISupports);
00105     Value(const PRUnichar* aString);
00106     Value(PRInt32 aInteger);
00107 
00108     Value& operator=(const Value& aValue);
00109     Value& operator=(nsISupports* aISupports);
00110     Value& operator=(const PRUnichar* aString);
00111     Value& operator=(PRInt32 aInteger);
00112 
00113     ~Value();
00114 
00115     PRBool operator==(const Value& aValue) const { return Equals(aValue); }
00116     PRBool operator==(nsISupports* aISupports) const { return Equals(aISupports); }
00117     PRBool operator==(const PRUnichar* aString) const { return Equals(aString); }
00118     PRBool operator==(PRInt32 aInteger) const { return Equals(aInteger); }
00119 
00120     PRBool operator!=(const Value& aValue) const { return !Equals(aValue); }
00121     PRBool operator!=(nsISupports* aISupports) const { return !Equals(aISupports); }
00122     PRBool operator!=(const PRUnichar* aString) const { return !Equals(aString); }
00123     PRBool operator!=(PRInt32 aInteger) const { return !Equals(aInteger); }
00124 
00129     Type GetType() const { return mType; }
00130 
00137     operator nsISupports*() const;
00138 
00144     operator const PRUnichar*() const;
00145 
00151     operator PRInt32() const;
00152 
00153     PLHashNumber Hash() const;
00154 
00155 #ifdef DEBUG
00156     void ToCString(nsACString& aResult);
00157 #endif
00158 };
00159 
00160 #ifdef DEBUG
00161 nsISupports*
00162 value_to_isupports(const nsIID& aIID, const Value& aValue);
00163 
00164 #  define VALUE_TO_ISUPPORTS(type, v) \
00165         NS_STATIC_CAST(type*, value_to_isupports(NS_GET_IID(type), (v)))
00166 #else
00167 #  define VALUE_TO_ISUPPORTS(type, v) \
00168         NS_STATIC_CAST(type*, NS_STATIC_CAST(nsISupports*, (v)))
00169 #endif
00170 
00171 // Convenience wrappers for |Value::operator nsISupports*()|. In a
00172 // debug build, they expand to versions that will call QI() and verify
00173 // that the types are kosher. In an optimized build, they'll just cast
00174 // n' go. Rock on!
00175 #define VALUE_TO_IRDFRESOURCE(v) VALUE_TO_ISUPPORTS(nsIRDFResource, (v))
00176 #define VALUE_TO_IRDFNODE(v)     VALUE_TO_ISUPPORTS(nsIRDFNode, (v))
00177 #define VALUE_TO_ICONTENT(v)     VALUE_TO_ISUPPORTS(nsIContent, (v))
00178 
00179 //----------------------------------------------------------------------
00180 
00184 class VariableSet
00185 {
00186 public:
00187     VariableSet();
00188     ~VariableSet();
00189 
00195     nsresult Add(PRInt32 aVariable);
00196 
00202     nsresult Remove(PRInt32 aVariable);
00203 
00209     PRBool Contains(PRInt32 aVariable) const;
00210 
00215     PRInt32 GetCount() const { return mCount; }
00216 
00223     PRInt32 GetVariableAt(PRInt32 aIndex) const { return mVariables[aIndex]; }
00224 
00225 protected:
00226     PRInt32* mVariables;
00227     PRInt32 mCount;
00228     PRInt32 mCapacity;
00229 };
00230 
00231 //----------------------------------------------------------------------
00232 
00236 class MemoryElement {
00237 public:
00238     MemoryElement() {}
00239     virtual ~MemoryElement() {}
00240 
00241     virtual const char* Type() const = 0;
00242     virtual PLHashNumber Hash() const = 0;
00243     virtual PRBool Equals(const MemoryElement& aElement) const = 0;
00244     virtual MemoryElement* Clone(void* aPool) const = 0;
00245 
00246     PRBool operator==(const MemoryElement& aMemoryElement) const {
00247         return Equals(aMemoryElement);
00248     }
00249 
00250     PRBool operator!=(const MemoryElement& aMemoryElement) const {
00251         return !Equals(aMemoryElement);
00252     }
00253 };
00254 
00255 //----------------------------------------------------------------------
00256 
00260 class MemoryElementSet {
00261 public:
00262     class ConstIterator;
00263     friend class ConstIterator;
00264 
00265 protected:
00266     class List {
00267     public:
00268         List() { MOZ_COUNT_CTOR(MemoryElementSet::List); }
00269 
00270         ~List() {
00271             MOZ_COUNT_DTOR(MemoryElementSet::List);
00272             delete mElement;
00273             NS_IF_RELEASE(mNext); }
00274 
00275         PRInt32 AddRef() { return ++mRefCnt; }
00276 
00277         PRInt32 Release() {
00278             PRInt32 refcnt = --mRefCnt;
00279             if (refcnt == 0) delete this;
00280             return refcnt; }
00281 
00282         MemoryElement* mElement;
00283         PRInt32        mRefCnt;
00284         List*          mNext;
00285     };
00286 
00287     List* mElements;
00288 
00289 public:
00290     MemoryElementSet() : mElements(nsnull) {
00291         MOZ_COUNT_CTOR(MemoryElementSet); }
00292 
00293     MemoryElementSet(const MemoryElementSet& aSet) : mElements(aSet.mElements) {
00294         MOZ_COUNT_CTOR(MemoryElementSet);
00295         NS_IF_ADDREF(mElements); }
00296 
00297     MemoryElementSet& operator=(const MemoryElementSet& aSet) {
00298         NS_IF_RELEASE(mElements);
00299         mElements = aSet.mElements;
00300         NS_IF_ADDREF(mElements);
00301         return *this; }
00302         
00303     ~MemoryElementSet() {
00304         MOZ_COUNT_DTOR(MemoryElementSet);
00305         NS_IF_RELEASE(mElements); }
00306 
00307 public:
00308     class ConstIterator {
00309     public:
00310         ConstIterator(List* aElementList) : mCurrent(aElementList) {
00311             NS_IF_ADDREF(mCurrent); }
00312 
00313         ConstIterator(const ConstIterator& aConstIterator)
00314             : mCurrent(aConstIterator.mCurrent) {
00315             NS_IF_ADDREF(mCurrent); }
00316 
00317         ConstIterator& operator=(const ConstIterator& aConstIterator) {
00318             NS_IF_RELEASE(mCurrent);
00319             mCurrent = aConstIterator.mCurrent;
00320             NS_IF_ADDREF(mCurrent);
00321             return *this; }
00322 
00323         ~ConstIterator() { NS_IF_RELEASE(mCurrent); }
00324 
00325         ConstIterator& operator++() {
00326             List* next = mCurrent->mNext;
00327             NS_RELEASE(mCurrent);
00328             mCurrent = next;
00329             NS_IF_ADDREF(mCurrent);
00330             return *this; }
00331 
00332         ConstIterator operator++(int) {
00333             ConstIterator result(*this);
00334             List* next = mCurrent->mNext;
00335             NS_RELEASE(mCurrent);
00336             mCurrent = next;
00337             NS_IF_ADDREF(mCurrent);
00338             return result; }
00339 
00340         const MemoryElement& operator*() const {
00341             return *mCurrent->mElement; }
00342 
00343         const MemoryElement* operator->() const {
00344             return mCurrent->mElement; }
00345 
00346         PRBool operator==(const ConstIterator& aConstIterator) const {
00347             return mCurrent == aConstIterator.mCurrent; }
00348 
00349         PRBool operator!=(const ConstIterator& aConstIterator) const {
00350             return mCurrent != aConstIterator.mCurrent; }
00351 
00352     protected:
00353         List* mCurrent;
00354     };
00355 
00356     ConstIterator First() const { return ConstIterator(mElements); }
00357     ConstIterator Last() const { return ConstIterator(nsnull); }
00358 
00359     // N.B. that the set assumes ownership of the element
00360     nsresult Add(MemoryElement* aElement);
00361 };
00362 
00363 //----------------------------------------------------------------------
00364 
00368 class nsAssignment {
00369 public:
00370     PRInt32 mVariable;
00371     Value   mValue;
00372 
00373     nsAssignment() : mVariable(-1), mValue()
00374         { MOZ_COUNT_CTOR(nsAssignment); }
00375 
00376     nsAssignment(PRInt32 aVariable, const Value& aValue)
00377         : mVariable(aVariable),
00378           mValue(aValue)
00379         { MOZ_COUNT_CTOR(nsAssignment); }
00380 
00381     nsAssignment(const nsAssignment& aAssignment)
00382         : mVariable(aAssignment.mVariable),
00383           mValue(aAssignment.mValue)
00384         { MOZ_COUNT_CTOR(nsAssignment); }
00385 
00386     ~nsAssignment() { MOZ_COUNT_DTOR(nsAssignment); }
00387 
00388     nsAssignment& operator=(const nsAssignment& aAssignment) {
00389         mVariable = aAssignment.mVariable;
00390         mValue    = aAssignment.mValue;
00391         return *this; }
00392 
00393     PRBool operator==(const nsAssignment& aAssignment) const {
00394         return mVariable == aAssignment.mVariable && mValue == aAssignment.mValue; }
00395 
00396     PRBool operator!=(const nsAssignment& aAssignment) const {
00397         return mVariable != aAssignment.mVariable || mValue != aAssignment.mValue; }
00398 
00399     PLHashNumber Hash() const {
00400         // XXX I have no idea if this hashing function is good or not
00401         return (mValue.Hash() & 0xffff) | (mVariable << 16); }
00402 };
00403 
00404 
00405 //----------------------------------------------------------------------
00406 
00411 class nsAssignmentSet {
00412 public:
00413     class ConstIterator;
00414     friend class ConstIterator;
00415 
00416 protected:
00417     class List {
00418     public:
00419         List() { MOZ_COUNT_CTOR(nsAssignmentSet::List); }
00420 
00421         ~List() {
00422             MOZ_COUNT_DTOR(nsAssignmentSet::List);
00423             NS_IF_RELEASE(mNext); }
00424 
00425         PRInt32 AddRef() { return ++mRefCnt; }
00426 
00427         PRInt32 Release() {
00428             PRInt32 refcnt = --mRefCnt;
00429             if (refcnt == 0) delete this;
00430             return refcnt; }
00431 
00432         nsAssignment mAssignment;
00433         PRInt32 mRefCnt;
00434         List*   mNext;
00435     };
00436 
00437     List* mAssignments;
00438 
00439 public:
00440     nsAssignmentSet()
00441         : mAssignments(nsnull)
00442         { MOZ_COUNT_CTOR(nsAssignmentSet); }
00443 
00444     nsAssignmentSet(const nsAssignmentSet& aSet)
00445         : mAssignments(aSet.mAssignments) {
00446         MOZ_COUNT_CTOR(nsAssignmentSet);
00447         NS_IF_ADDREF(mAssignments); }
00448 
00449     nsAssignmentSet& operator=(const nsAssignmentSet& aSet) {
00450         NS_IF_RELEASE(mAssignments);
00451         mAssignments = aSet.mAssignments;
00452         NS_IF_ADDREF(mAssignments);
00453         return *this; }
00454 
00455     ~nsAssignmentSet() {
00456         MOZ_COUNT_DTOR(nsAssignmentSet);
00457         NS_IF_RELEASE(mAssignments); }
00458 
00459 public:
00460     class ConstIterator {
00461     public:
00462         ConstIterator(List* aAssignmentList) : mCurrent(aAssignmentList) {
00463             NS_IF_ADDREF(mCurrent); }
00464 
00465         ConstIterator(const ConstIterator& aConstIterator)
00466             : mCurrent(aConstIterator.mCurrent) {
00467             NS_IF_ADDREF(mCurrent); }
00468 
00469         ConstIterator& operator=(const ConstIterator& aConstIterator) {
00470             NS_IF_RELEASE(mCurrent);
00471             mCurrent = aConstIterator.mCurrent;
00472             NS_IF_ADDREF(mCurrent);
00473             return *this; }
00474 
00475         ~ConstIterator() { NS_IF_RELEASE(mCurrent); }
00476 
00477         ConstIterator& operator++() {
00478             List* next = mCurrent->mNext;
00479             NS_RELEASE(mCurrent);
00480             mCurrent = next;
00481             NS_IF_ADDREF(mCurrent);
00482             return *this; }
00483 
00484         ConstIterator operator++(int) {
00485             ConstIterator result(*this);
00486             List* next = mCurrent->mNext;
00487             NS_RELEASE(mCurrent);
00488             mCurrent = next;
00489             NS_IF_ADDREF(mCurrent);
00490             return result; }
00491 
00492         const nsAssignment& operator*() const {
00493             return mCurrent->mAssignment; }
00494 
00495         const nsAssignment* operator->() const {
00496             return &mCurrent->mAssignment; }
00497 
00498         PRBool operator==(const ConstIterator& aConstIterator) const {
00499             return mCurrent == aConstIterator.mCurrent; }
00500 
00501         PRBool operator!=(const ConstIterator& aConstIterator) const {
00502             return mCurrent != aConstIterator.mCurrent; }
00503 
00504     protected:
00505         List* mCurrent;
00506     };
00507 
00508     ConstIterator First() const { return ConstIterator(mAssignments); }
00509     ConstIterator Last() const { return ConstIterator(nsnull); }
00510 
00511 public:
00518     nsresult Add(const nsAssignment& aElement);
00519 
00527     PRBool HasAssignment(PRInt32 aVariable, const Value& aValue) const;
00528 
00534     PRBool HasAssignment(const nsAssignment& aAssignment) const {
00535         return HasAssignment(aAssignment.mVariable, aAssignment.mValue); }
00536 
00544     PRBool HasAssignmentFor(PRInt32 aVariable) const;
00545 
00554     PRBool GetAssignmentFor(PRInt32 aVariable, Value* aValue) const;
00555 
00560     PRInt32 Count() const;
00561 
00566     PRBool IsEmpty() const { return mAssignments == nsnull; }
00567 
00568     PRBool Equals(const nsAssignmentSet& aSet) const;
00569     PRBool operator==(const nsAssignmentSet& aSet) const { return Equals(aSet); }
00570     PRBool operator!=(const nsAssignmentSet& aSet) const { return !Equals(aSet); }
00571 };
00572 
00573 
00574 //----------------------------------------------------------------------
00575 
00584 class Instantiation
00585 {
00586 public:
00590     nsAssignmentSet  mAssignments;
00591 
00595     MemoryElementSet mSupport;
00596 
00597     Instantiation() { MOZ_COUNT_CTOR(Instantiation); }
00598 
00599     Instantiation(const Instantiation& aInstantiation)
00600         : mAssignments(aInstantiation.mAssignments),
00601           mSupport(aInstantiation.mSupport) {
00602         MOZ_COUNT_CTOR(Instantiation); }
00603 
00604     Instantiation& operator=(const Instantiation& aInstantiation) {
00605         mAssignments = aInstantiation.mAssignments;
00606         mSupport  = aInstantiation.mSupport;
00607         return *this; }
00608 
00609     ~Instantiation() { MOZ_COUNT_DTOR(Instantiation); }
00610 
00619     nsresult AddAssignment(PRInt32 aVariable, const Value& aValue) {
00620         mAssignments.Add(nsAssignment(aVariable, aValue));
00621         return NS_OK; }
00622 
00631     nsresult AddSupportingElement(MemoryElement* aMemoryElement) {
00632         mSupport.Add(aMemoryElement);
00633         return NS_OK; }
00634 
00635     PRBool Equals(const Instantiation& aInstantiation) const {
00636         return mAssignments == aInstantiation.mAssignments; }
00637 
00638     PRBool operator==(const Instantiation& aInstantiation) const {
00639         return Equals(aInstantiation); }
00640 
00641     PRBool operator!=(const Instantiation& aInstantiation) const {
00642         return !Equals(aInstantiation); }
00643 
00644     static PLHashNumber Hash(const void* aKey);
00645     static PRIntn Compare(const void* aLeft, const void* aRight);
00646 };
00647 
00648 
00649 //----------------------------------------------------------------------
00650 
00654 class InstantiationSet
00655 {
00656 public:
00657     InstantiationSet();
00658     InstantiationSet(const InstantiationSet& aInstantiationSet);
00659     InstantiationSet& operator=(const InstantiationSet& aInstantiationSet);
00660 
00661     ~InstantiationSet() {
00662         MOZ_COUNT_DTOR(InstantiationSet);
00663         Clear(); }
00664 
00665     class ConstIterator;
00666     friend class ConstIterator;
00667 
00668     class Iterator;
00669     friend class Iterator;
00670 
00671 protected:
00672     class List {
00673     public:
00674         Instantiation mInstantiation;
00675         List*         mNext;
00676         List*         mPrev;
00677 
00678         List() { MOZ_COUNT_CTOR(InstantiationSet::List); }
00679         ~List() { MOZ_COUNT_DTOR(InstantiationSet::List); }
00680     };
00681 
00682     List mHead;
00683 
00684 public:
00685     class ConstIterator {
00686     protected:
00687         friend class Iterator; // XXXwaterson so broken.
00688         List* mCurrent;
00689 
00690     public:
00691         ConstIterator(List* aList) : mCurrent(aList) {}
00692 
00693         ConstIterator(const ConstIterator& aConstIterator)
00694             : mCurrent(aConstIterator.mCurrent) {}
00695 
00696         ConstIterator& operator=(const ConstIterator& aConstIterator) {
00697             mCurrent = aConstIterator.mCurrent;
00698             return *this; }
00699 
00700         ConstIterator& operator++() {
00701             mCurrent = mCurrent->mNext;
00702             return *this; }
00703 
00704         ConstIterator operator++(int) {
00705             ConstIterator result(*this);
00706             mCurrent = mCurrent->mNext;
00707             return result; }
00708 
00709         ConstIterator& operator--() {
00710             mCurrent = mCurrent->mPrev;
00711             return *this; }
00712 
00713         ConstIterator operator--(int) {
00714             ConstIterator result(*this);
00715             mCurrent = mCurrent->mPrev;
00716             return result; }
00717 
00718         const Instantiation& operator*() const {
00719             return mCurrent->mInstantiation; }
00720 
00721         const Instantiation* operator->() const {
00722             return &mCurrent->mInstantiation; }
00723 
00724         PRBool operator==(const ConstIterator& aConstIterator) const {
00725             return mCurrent == aConstIterator.mCurrent; }
00726 
00727         PRBool operator!=(const ConstIterator& aConstIterator) const {
00728             return mCurrent != aConstIterator.mCurrent; }
00729     };
00730 
00731     ConstIterator First() const { return ConstIterator(mHead.mNext); }
00732     ConstIterator Last() const { return ConstIterator(NS_CONST_CAST(List*, &mHead)); }
00733 
00734     class Iterator : public ConstIterator {
00735     public:
00736         Iterator(List* aList) : ConstIterator(aList) {}
00737 
00738         Iterator& operator++() {
00739             mCurrent = mCurrent->mNext;
00740             return *this; }
00741 
00742         Iterator operator++(int) {
00743             Iterator result(*this);
00744             mCurrent = mCurrent->mNext;
00745             return result; }
00746 
00747         Iterator& operator--() {
00748             mCurrent = mCurrent->mPrev;
00749             return *this; }
00750 
00751         Iterator operator--(int) {
00752             Iterator result(*this);
00753             mCurrent = mCurrent->mPrev;
00754             return result; }
00755 
00756         Instantiation& operator*() const {
00757             return mCurrent->mInstantiation; }
00758 
00759         Instantiation* operator->() const {
00760             return &mCurrent->mInstantiation; }
00761 
00762         PRBool operator==(const ConstIterator& aConstIterator) const {
00763             return mCurrent == aConstIterator.mCurrent; }
00764 
00765         PRBool operator!=(const ConstIterator& aConstIterator) const {
00766             return mCurrent != aConstIterator.mCurrent; }
00767 
00768         friend class InstantiationSet;
00769     };
00770 
00771     Iterator First() { return Iterator(mHead.mNext); }
00772     Iterator Last() { return Iterator(&mHead); }
00773 
00774     PRBool Empty() const { return First() == Last(); }
00775 
00776     Iterator Append(const Instantiation& aInstantiation) {
00777         return Insert(Last(), aInstantiation); }
00778 
00779     Iterator Insert(Iterator aBefore, const Instantiation& aInstantiation);
00780 
00781     Iterator Erase(Iterator aElement);
00782 
00783     void Clear();
00784 
00785     PRBool HasAssignmentFor(PRInt32 aVariable) const;
00786 
00787 };
00788 
00789 //----------------------------------------------------------------------
00790 
00794 class ReteNode
00795 {
00796 public:
00797     ReteNode() {}
00798     virtual ~ReteNode() {}
00799 
00822     virtual nsresult Propagate(const InstantiationSet& aInstantiations, void* aClosure) = 0;
00823 };
00824 
00825 //----------------------------------------------------------------------
00826 
00830 class ReteNodeSet
00831 {
00832 public:
00833     ReteNodeSet();
00834     ~ReteNodeSet();
00835 
00836     nsresult Add(ReteNode* aNode);
00837     nsresult Clear();
00838 
00839     class Iterator;
00840 
00841     class ConstIterator {
00842     public:
00843         ConstIterator(ReteNode** aNode) : mCurrent(aNode) {}
00844 
00845         ConstIterator(const ConstIterator& aConstIterator)
00846             : mCurrent(aConstIterator.mCurrent) {}
00847 
00848         ConstIterator& operator=(const ConstIterator& aConstIterator) {
00849             mCurrent = aConstIterator.mCurrent;
00850             return *this; }
00851 
00852         ConstIterator& operator++() {
00853             ++mCurrent;
00854             return *this; }
00855 
00856         ConstIterator operator++(int) {
00857             ConstIterator result(*this);
00858             ++mCurrent;
00859             return result; }
00860 
00861         const ReteNode* operator*() const {
00862             return *mCurrent; }
00863 
00864         const ReteNode* operator->() const {
00865             return *mCurrent; }
00866 
00867         PRBool operator==(const ConstIterator& aConstIterator) const {
00868             return mCurrent == aConstIterator.mCurrent; }
00869 
00870         PRBool operator!=(const ConstIterator& aConstIterator) const {
00871             return mCurrent != aConstIterator.mCurrent; }
00872 
00873     protected:
00874         friend class Iterator; // XXXwaterson this is so wrong!
00875         ReteNode** mCurrent;
00876     };
00877 
00878     ConstIterator First() const { return ConstIterator(mNodes); }
00879     ConstIterator Last() const { return ConstIterator(mNodes + mCount); }
00880 
00881     class Iterator : public ConstIterator {
00882     public:
00883         Iterator(ReteNode** aNode) : ConstIterator(aNode) {}
00884 
00885         Iterator& operator++() {
00886             ++mCurrent;
00887             return *this; }
00888 
00889         Iterator operator++(int) {
00890             Iterator result(*this);
00891             ++mCurrent;
00892             return result; }
00893 
00894         ReteNode* operator*() const {
00895             return *mCurrent; }
00896 
00897         ReteNode* operator->() const {
00898             return *mCurrent; }
00899 
00900         PRBool operator==(const ConstIterator& aConstIterator) const {
00901             return mCurrent == aConstIterator.mCurrent; }
00902 
00903         PRBool operator!=(const ConstIterator& aConstIterator) const {
00904             return mCurrent != aConstIterator.mCurrent; }
00905     };
00906 
00907     Iterator First() { return Iterator(mNodes); }
00908     Iterator Last() { return Iterator(mNodes + mCount); }
00909 
00910 protected:
00911     ReteNode** mNodes;
00912     PRInt32 mCount;
00913     PRInt32 mCapacity;
00914 };
00915 
00916 //----------------------------------------------------------------------
00917 
00922 class InnerNode : public ReteNode
00923 {
00924 public:
00945     virtual nsresult Constrain(InstantiationSet& aInstantiations, void* aClosure) = 0;
00946 
00958     virtual nsresult GetAncestorVariables(VariableSet& aVariables) const = 0;
00959 
00966     virtual PRBool HasAncestor(const ReteNode* aNode) const = 0;
00967 
00973     nsresult AddChild(ReteNode* aNode) { return mKids.Add(aNode); }
00974 
00979     nsresult RemoveAllChildren() { return mKids.Clear(); }
00980 
00981 protected:
00982     ReteNodeSet mKids;
00983 };
00984 
00985 //----------------------------------------------------------------------
00986 
00990 class RootNode : public InnerNode
00991 {
00992 public:
00993     // "downward" propagations
00994     virtual nsresult Propagate(const InstantiationSet& aInstantiations, void* aClosure);
00995 
00996     // "upward" propagations
00997     virtual nsresult Constrain(InstantiationSet& aInstantiations, void* aClosure);
00998 
00999     virtual nsresult GetAncestorVariables(VariableSet& aVariables) const;
01000 
01001     virtual PRBool HasAncestor(const ReteNode* aNode) const;
01002 };
01003 
01004 //----------------------------------------------------------------------
01005 
01011 class JoinNode : public InnerNode
01012 {
01013 public:
01014     enum Operator { eEquality };
01015 
01016     JoinNode(InnerNode* aLeftParent,
01017              PRInt32 aLeftVariable,
01018              InnerNode* aRightParent,
01019              PRInt32 aRightVariable,
01020              Operator aOperator);
01021 
01022     // "downward" propagations
01023     virtual nsresult Propagate(const InstantiationSet& aInstantiations, void* aClosure);
01024 
01025     // "upward" propagations
01026     virtual nsresult Constrain(InstantiationSet& aInstantiations, void* aClosure);
01027 
01028     virtual nsresult GetAncestorVariables(VariableSet& aVariables) const;
01029 
01030     virtual PRBool HasAncestor(const ReteNode* aNode) const;
01031 
01032 protected:
01033     InnerNode* mLeftParent;
01034     PRInt32 mLeftVariable;
01035     InnerNode* mRightParent;
01036     PRInt32 mRightVariable;
01037     Operator mOperator;
01038 
01039     static nsresult GetNumBound(InnerNode* aAncestor, const InstantiationSet& aInstantiations, PRInt32* aBoundCount);
01040 
01041     nsresult Bind(InstantiationSet& aInstantiations, PRBool* aDidBind);
01042 };
01043 
01044 
01045 //----------------------------------------------------------------------
01046 
01056 class TestNode : public InnerNode
01057 {
01058 public:
01059     TestNode(InnerNode* aParent);
01060 
01065     InnerNode* GetParent() const { return mParent; }
01066 
01072     virtual nsresult Propagate(const InstantiationSet& aInstantiations, void* aClosure);
01073 
01079     virtual nsresult Constrain(InstantiationSet& aInstantiations, void* aClosure);
01080 
01093     virtual nsresult FilterInstantiations(InstantiationSet& aInstantiations, void* aClosure) const = 0; //XXX probably better named "ApplyConstraints" or "Discrminiate" or something
01094 
01095     virtual nsresult GetAncestorVariables(VariableSet& aVariables) const;
01096 
01097     virtual PRBool HasAncestor(const ReteNode* aNode) const;
01098 
01099 protected:
01100     InnerNode* mParent;
01101 };
01102 
01103 //----------------------------------------------------------------------
01104 
01105 class nsRuleNetwork
01106 {
01107 public:
01108     struct SymtabEntry {
01109         PLDHashEntryHdr mHdr;
01110         PRUnichar*      mSymbol;
01111         PRInt32         mVariable;
01112     };
01113     
01114     nsRuleNetwork() { Init(); }
01115     ~nsRuleNetwork() { Finish(); }
01116 
01122     void Clear() { Finish(); Init(); }
01123 
01132     nsresult AddNode(ReteNode* aNode) { return mNodes.Add(aNode); }
01133 
01138     RootNode* GetRoot() { return &mRoot; };
01139 
01143     PRInt32 CreateAnonymousVariable() { return ++mNextVariable; }
01144 
01148     void PutSymbol(const PRUnichar* aSymbol, PRInt32 aVariable) {
01149         if (!mSymtab.ops) return;
01150         NS_PRECONDITION(LookupSymbol(aSymbol) == 0, "symbol already defined");
01151 
01152         SymtabEntry* entry =
01153             NS_REINTERPRET_CAST(SymtabEntry*,
01154                                 PL_DHashTableOperate(&mSymtab,
01155                                                      aSymbol,
01156                                                      PL_DHASH_ADD));
01157 
01158         if (entry) {
01159             entry->mSymbol   = nsCRT::strdup(aSymbol);
01160             entry->mVariable = aVariable;
01161         } };
01162                                 
01166     PRInt32 LookupSymbol(const PRUnichar* aSymbol, PRBool aCreate = PR_FALSE) {
01167         if (!mSymtab.ops) return 0;
01168         SymtabEntry* entry =
01169             NS_REINTERPRET_CAST(SymtabEntry*,
01170                                 PL_DHashTableOperate(&mSymtab,
01171                                                      aSymbol,
01172                                                      PL_DHASH_LOOKUP));
01173 
01174         if (PL_DHASH_ENTRY_IS_BUSY(&entry->mHdr))
01175             return entry->mVariable;
01176 
01177         PRInt32 result = 0;
01178         if (aCreate) {
01179             result = CreateAnonymousVariable();
01180             PutSymbol(aSymbol, result);
01181         }
01182 
01183         return result; }
01184 
01185 protected:
01189     RootNode mRoot;
01190 
01194     ReteNodeSet mNodes;
01195 
01196     void Init();
01197     void Finish();
01198 
01202     PLDHashTable mSymtab;
01203 
01207     PRInt32 mNextVariable;
01208 
01209     static PLDHashTableOps gOps;
01210 };
01211 
01212 
01213 
01214 #endif // nsRuleNetwork_h__