michael@0: /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
michael@0: /* This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: /*
michael@0: 
michael@0:   A rule discrimination network implementation based on ideas from
michael@0:   RETE and TREAT.
michael@0: 
michael@0:   RETE is described in Charles Forgy, "Rete: A Fast Algorithm for the
michael@0:   Many Patterns/Many Objects Match Problem", Artificial Intelligence
michael@0:   19(1): pp. 17-37, 1982.
michael@0: 
michael@0:   TREAT is described in Daniel P. Miranker, "TREAT: A Better Match
michael@0:   Algorithm for AI Production System Matching", AAAI 1987: pp. 42-47.
michael@0: 
michael@0:   --
michael@0: 
michael@0:   TO DO:
michael@0: 
michael@0:   . nsAssignmentSet::List objects are allocated by the gallon. We
michael@0:     should make it so that these are always allocated from a pool,
michael@0:     maybe owned by the nsRuleNetwork?
michael@0: 
michael@0:  */
michael@0: 
michael@0: #ifndef nsRuleNetwork_h__
michael@0: #define nsRuleNetwork_h__
michael@0: 
michael@0: #include "mozilla/Attributes.h"
michael@0: #include "nsCOMPtr.h"
michael@0: #include "nsCOMArray.h"
michael@0: #include "nsIAtom.h"
michael@0: #include "nsIDOMNode.h"
michael@0: #include "plhash.h"
michael@0: #include "pldhash.h"
michael@0: #include "nsIRDFNode.h"
michael@0: 
michael@0: class nsIRDFResource;
michael@0: class nsXULTemplateResultSetRDF;
michael@0: class nsXULTemplateQueryProcessorRDF;
michael@0: 
michael@0: //----------------------------------------------------------------------
michael@0: 
michael@0: /**
michael@0:  * A memory element that supports an instantiation. A memory element holds a
michael@0:  * set of nodes involved in an RDF test such as <member> or <triple> test. A
michael@0:  * memory element is created when a specific test matches. The query processor
michael@0:  * maintains a map between the memory elements and the results they eventually
michael@0:  * matched. When an assertion is removed from the graph, this map is consulted
michael@0:  * to determine which results will no longer match.
michael@0:  */
michael@0: class MemoryElement {
michael@0: protected:
michael@0:     MemoryElement() { MOZ_COUNT_CTOR(MemoryElement); }
michael@0: 
michael@0: public:
michael@0:     virtual ~MemoryElement() { MOZ_COUNT_DTOR(MemoryElement); }
michael@0: 
michael@0:     virtual const char* Type() const = 0;
michael@0:     virtual PLHashNumber Hash() const = 0;
michael@0:     virtual bool Equals(const MemoryElement& aElement) const = 0;
michael@0: 
michael@0:     bool operator==(const MemoryElement& aMemoryElement) const {
michael@0:         return Equals(aMemoryElement);
michael@0:     }
michael@0: 
michael@0:     bool operator!=(const MemoryElement& aMemoryElement) const {
michael@0:         return !Equals(aMemoryElement);
michael@0:     }
michael@0: };
michael@0: 
michael@0: //----------------------------------------------------------------------
michael@0: 
michael@0: /**
michael@0:  * A collection of memory elements
michael@0:  */
michael@0: class MemoryElementSet {
michael@0: public:
michael@0:     class ConstIterator;
michael@0:     friend class ConstIterator;
michael@0: 
michael@0: protected:
michael@0:     class List {
michael@0:     public:
michael@0:         List() { MOZ_COUNT_CTOR(MemoryElementSet::List); }
michael@0: 
michael@0:         ~List() {
michael@0:             MOZ_COUNT_DTOR(MemoryElementSet::List);
michael@0:             delete mElement;
michael@0:             NS_IF_RELEASE(mNext); }
michael@0: 
michael@0:         int32_t AddRef() { return ++mRefCnt; }
michael@0: 
michael@0:         int32_t Release() {
michael@0:             int32_t refcnt = --mRefCnt;
michael@0:             if (refcnt == 0) delete this;
michael@0:             return refcnt; }
michael@0: 
michael@0:         MemoryElement* mElement;
michael@0:         int32_t        mRefCnt;
michael@0:         List*          mNext;
michael@0:     };
michael@0: 
michael@0:     List* mElements;
michael@0: 
michael@0: public:
michael@0:     MemoryElementSet() : mElements(nullptr) {
michael@0:         MOZ_COUNT_CTOR(MemoryElementSet); }
michael@0: 
michael@0:     MemoryElementSet(const MemoryElementSet& aSet) : mElements(aSet.mElements) {
michael@0:         MOZ_COUNT_CTOR(MemoryElementSet);
michael@0:         NS_IF_ADDREF(mElements); }
michael@0: 
michael@0:     MemoryElementSet& operator=(const MemoryElementSet& aSet) {
michael@0:         NS_IF_RELEASE(mElements);
michael@0:         mElements = aSet.mElements;
michael@0:         NS_IF_ADDREF(mElements);
michael@0:         return *this; }
michael@0:         
michael@0:     ~MemoryElementSet() {
michael@0:         MOZ_COUNT_DTOR(MemoryElementSet);
michael@0:         NS_IF_RELEASE(mElements); }
michael@0: 
michael@0: public:
michael@0:     class ConstIterator {
michael@0:     public:
michael@0:         ConstIterator(List* aElementList) : mCurrent(aElementList) {
michael@0:             NS_IF_ADDREF(mCurrent); }
michael@0: 
michael@0:         ConstIterator(const ConstIterator& aConstIterator)
michael@0:             : mCurrent(aConstIterator.mCurrent) {
michael@0:             NS_IF_ADDREF(mCurrent); }
michael@0: 
michael@0:         ConstIterator& operator=(const ConstIterator& aConstIterator) {
michael@0:             NS_IF_RELEASE(mCurrent);
michael@0:             mCurrent = aConstIterator.mCurrent;
michael@0:             NS_IF_ADDREF(mCurrent);
michael@0:             return *this; }
michael@0: 
michael@0:         ~ConstIterator() { NS_IF_RELEASE(mCurrent); }
michael@0: 
michael@0:         ConstIterator& operator++() {
michael@0:             List* next = mCurrent->mNext;
michael@0:             NS_RELEASE(mCurrent);
michael@0:             mCurrent = next;
michael@0:             NS_IF_ADDREF(mCurrent);
michael@0:             return *this; }
michael@0: 
michael@0:         ConstIterator operator++(int) {
michael@0:             ConstIterator result(*this);
michael@0:             List* next = mCurrent->mNext;
michael@0:             NS_RELEASE(mCurrent);
michael@0:             mCurrent = next;
michael@0:             NS_IF_ADDREF(mCurrent);
michael@0:             return result; }
michael@0: 
michael@0:         const MemoryElement& operator*() const {
michael@0:             return *mCurrent->mElement; }
michael@0: 
michael@0:         const MemoryElement* operator->() const {
michael@0:             return mCurrent->mElement; }
michael@0: 
michael@0:         bool operator==(const ConstIterator& aConstIterator) const {
michael@0:             return mCurrent == aConstIterator.mCurrent; }
michael@0: 
michael@0:         bool operator!=(const ConstIterator& aConstIterator) const {
michael@0:             return mCurrent != aConstIterator.mCurrent; }
michael@0: 
michael@0:     protected:
michael@0:         List* mCurrent;
michael@0:     };
michael@0: 
michael@0:     ConstIterator First() const { return ConstIterator(mElements); }
michael@0:     ConstIterator Last() const { return ConstIterator(nullptr); }
michael@0: 
michael@0:     // N.B. that the set assumes ownership of the element
michael@0:     nsresult Add(MemoryElement* aElement);
michael@0: };
michael@0: 
michael@0: //----------------------------------------------------------------------
michael@0: 
michael@0: /**
michael@0:  * An assignment of a value to a variable
michael@0:  */
michael@0: class nsAssignment {
michael@0: public:
michael@0:     const nsCOMPtr<nsIAtom> mVariable;
michael@0:     nsCOMPtr<nsIRDFNode> mValue;
michael@0: 
michael@0:     nsAssignment(nsIAtom* aVariable, nsIRDFNode* aValue)
michael@0:         : mVariable(aVariable),
michael@0:           mValue(aValue)
michael@0:         { MOZ_COUNT_CTOR(nsAssignment); }
michael@0: 
michael@0:     nsAssignment(const nsAssignment& aAssignment)
michael@0:         : mVariable(aAssignment.mVariable),
michael@0:           mValue(aAssignment.mValue)
michael@0:         { MOZ_COUNT_CTOR(nsAssignment); }
michael@0: 
michael@0:     ~nsAssignment() { MOZ_COUNT_DTOR(nsAssignment); }
michael@0: 
michael@0:     bool operator==(const nsAssignment& aAssignment) const {
michael@0:         return mVariable == aAssignment.mVariable && mValue == aAssignment.mValue; }
michael@0: 
michael@0:     bool operator!=(const nsAssignment& aAssignment) const {
michael@0:         return mVariable != aAssignment.mVariable || mValue != aAssignment.mValue; }
michael@0: 
michael@0:     PLHashNumber Hash() const {
michael@0:         // XXX I have no idea if this hashing function is good or not // XXX change this
michael@0:         PLHashNumber temp = PLHashNumber(NS_PTR_TO_INT32(mValue.get())) >> 2; // strip alignment bits
michael@0:         return (temp & 0xffff) | NS_PTR_TO_INT32(mVariable.get()); }
michael@0: };
michael@0: 
michael@0: 
michael@0: //----------------------------------------------------------------------
michael@0: 
michael@0: /**
michael@0:  * A collection of value-to-variable assignments that minimizes
michael@0:  * copying by sharing subsets when possible.
michael@0:  */
michael@0: class nsAssignmentSet {
michael@0: public:
michael@0:     class ConstIterator;
michael@0:     friend class ConstIterator;
michael@0: 
michael@0: protected:
michael@0:     class List {
michael@0:     public:
michael@0:         List(const nsAssignment &aAssignment) : mAssignment(aAssignment) {
michael@0:             MOZ_COUNT_CTOR(nsAssignmentSet::List); }
michael@0: 
michael@0:         ~List() {
michael@0:             MOZ_COUNT_DTOR(nsAssignmentSet::List);
michael@0:             NS_IF_RELEASE(mNext); }
michael@0: 
michael@0:         int32_t AddRef() { return ++mRefCnt; }
michael@0: 
michael@0:         int32_t Release() {
michael@0:             int32_t refcnt = --mRefCnt;
michael@0:             if (refcnt == 0) delete this;
michael@0:             return refcnt; }
michael@0: 
michael@0:         nsAssignment mAssignment;
michael@0:         int32_t mRefCnt;
michael@0:         List*   mNext;
michael@0:     };
michael@0: 
michael@0:     List* mAssignments;
michael@0: 
michael@0: public:
michael@0:     nsAssignmentSet()
michael@0:         : mAssignments(nullptr)
michael@0:         { MOZ_COUNT_CTOR(nsAssignmentSet); }
michael@0: 
michael@0:     nsAssignmentSet(const nsAssignmentSet& aSet)
michael@0:         : mAssignments(aSet.mAssignments) {
michael@0:         MOZ_COUNT_CTOR(nsAssignmentSet);
michael@0:         NS_IF_ADDREF(mAssignments); }
michael@0: 
michael@0:     nsAssignmentSet& operator=(const nsAssignmentSet& aSet) {
michael@0:         NS_IF_RELEASE(mAssignments);
michael@0:         mAssignments = aSet.mAssignments;
michael@0:         NS_IF_ADDREF(mAssignments);
michael@0:         return *this; }
michael@0: 
michael@0:     ~nsAssignmentSet() {
michael@0:         MOZ_COUNT_DTOR(nsAssignmentSet);
michael@0:         NS_IF_RELEASE(mAssignments); }
michael@0: 
michael@0: public:
michael@0:     class ConstIterator {
michael@0:     public:
michael@0:         ConstIterator(List* aAssignmentList) : mCurrent(aAssignmentList) {
michael@0:             NS_IF_ADDREF(mCurrent); }
michael@0: 
michael@0:         ConstIterator(const ConstIterator& aConstIterator)
michael@0:             : mCurrent(aConstIterator.mCurrent) {
michael@0:             NS_IF_ADDREF(mCurrent); }
michael@0: 
michael@0:         ConstIterator& operator=(const ConstIterator& aConstIterator) {
michael@0:             NS_IF_RELEASE(mCurrent);
michael@0:             mCurrent = aConstIterator.mCurrent;
michael@0:             NS_IF_ADDREF(mCurrent);
michael@0:             return *this; }
michael@0: 
michael@0:         ~ConstIterator() { NS_IF_RELEASE(mCurrent); }
michael@0: 
michael@0:         ConstIterator& operator++() {
michael@0:             List* next = mCurrent->mNext;
michael@0:             NS_RELEASE(mCurrent);
michael@0:             mCurrent = next;
michael@0:             NS_IF_ADDREF(mCurrent);
michael@0:             return *this; }
michael@0: 
michael@0:         ConstIterator operator++(int) {
michael@0:             ConstIterator result(*this);
michael@0:             List* next = mCurrent->mNext;
michael@0:             NS_RELEASE(mCurrent);
michael@0:             mCurrent = next;
michael@0:             NS_IF_ADDREF(mCurrent);
michael@0:             return result; }
michael@0: 
michael@0:         const nsAssignment& operator*() const {
michael@0:             return mCurrent->mAssignment; }
michael@0: 
michael@0:         const nsAssignment* operator->() const {
michael@0:             return &mCurrent->mAssignment; }
michael@0: 
michael@0:         bool operator==(const ConstIterator& aConstIterator) const {
michael@0:             return mCurrent == aConstIterator.mCurrent; }
michael@0: 
michael@0:         bool operator!=(const ConstIterator& aConstIterator) const {
michael@0:             return mCurrent != aConstIterator.mCurrent; }
michael@0: 
michael@0:     protected:
michael@0:         List* mCurrent;
michael@0:     };
michael@0: 
michael@0:     ConstIterator First() const { return ConstIterator(mAssignments); }
michael@0:     ConstIterator Last() const { return ConstIterator(nullptr); }
michael@0: 
michael@0: public:
michael@0:     /**
michael@0:      * Add an assignment to the set
michael@0:      * @param aElement the assigment to add
michael@0:      * @return NS_OK if all is well, NS_ERROR_OUT_OF_MEMORY if memory
michael@0:      *   could not be allocated for the addition.
michael@0:      */
michael@0:     nsresult Add(const nsAssignment& aElement);
michael@0: 
michael@0:     /**
michael@0:      * Determine if the assignment set contains the specified variable
michael@0:      * to value assignment.
michael@0:      * @param aVariable the variable for which to lookup the binding
michael@0:      * @param aValue the value to query
michael@0:      * @return true if aVariable is bound to aValue; false otherwise.
michael@0:      */
michael@0:     bool HasAssignment(nsIAtom* aVariable, nsIRDFNode* aValue) const;
michael@0: 
michael@0:     /**
michael@0:      * Determine if the assignment set contains the specified assignment
michael@0:      * @param aAssignment the assignment to search for
michael@0:      * @return true if the set contains the assignment, false otherwise.
michael@0:      */
michael@0:     bool HasAssignment(const nsAssignment& aAssignment) const {
michael@0:         return HasAssignment(aAssignment.mVariable, aAssignment.mValue); }
michael@0: 
michael@0:     /**
michael@0:      * Determine whether the assignment set has an assignment for the
michael@0:      * specified variable.
michael@0:      * @param aVariable the variable to query
michael@0:      * @return true if the assignment set has an assignment for the variable,
michael@0:      *   false otherwise.
michael@0:      */
michael@0:     bool HasAssignmentFor(nsIAtom* aVariable) const;
michael@0: 
michael@0:     /**
michael@0:      * Retrieve the assignment for the specified variable
michael@0:      * @param aVariable the variable to query
michael@0:      * @param aValue an out parameter that will receive the value assigned
michael@0:      *   to the variable, if any.
michael@0:      * @return true if the variable has an assignment, false
michael@0:      *   if there was no assignment for the variable.
michael@0:      */
michael@0:     bool GetAssignmentFor(nsIAtom* aVariable, nsIRDFNode** aValue) const;
michael@0: 
michael@0:     /**
michael@0:      * Count the number of assignments in the set
michael@0:      * @return the number of assignments in the set
michael@0:      */
michael@0:     int32_t Count() const;
michael@0: 
michael@0:     /**
michael@0:      * Determine if the set is empty
michael@0:      * @return true if the assignment set is empty, false otherwise.
michael@0:      */
michael@0:     bool IsEmpty() const { return mAssignments == nullptr; }
michael@0: 
michael@0:     bool Equals(const nsAssignmentSet& aSet) const;
michael@0:     bool operator==(const nsAssignmentSet& aSet) const { return Equals(aSet); }
michael@0:     bool operator!=(const nsAssignmentSet& aSet) const { return !Equals(aSet); }
michael@0: };
michael@0: 
michael@0: 
michael@0: //----------------------------------------------------------------------
michael@0: 
michael@0: /**
michael@0:  * A collection of variable-to-value bindings, with the memory elements
michael@0:  * that support those bindings. Essentially, an instantiation is the
michael@0:  * collection of variables and values assigned to those variables for a single
michael@0:  * result. For each RDF rule in the rule network, each instantiation is
michael@0:  * examined and either extended with additional bindings specified by the RDF
michael@0:  * rule, or removed if the rule doesn't apply (for instance if a node has no
michael@0:  * children). When an instantiation gets to the last node of the rule network,
michael@0:  * which is always an nsInstantiationNode, a result is created for it.
michael@0:  *
michael@0:  * An instantiation object is typically created by "extending" another
michael@0:  * instantiation object. That is, using the copy constructor, and
michael@0:  * adding bindings and support to the instantiation.
michael@0:  */
michael@0: class Instantiation
michael@0: {
michael@0: public:
michael@0:     /**
michael@0:      * The variable-to-value bindings
michael@0:      */
michael@0:     nsAssignmentSet  mAssignments;
michael@0: 
michael@0:     /**
michael@0:      * The memory elements that support the bindings.
michael@0:      */
michael@0:     MemoryElementSet mSupport;
michael@0: 
michael@0:     Instantiation() { MOZ_COUNT_CTOR(Instantiation); }
michael@0: 
michael@0:     Instantiation(const Instantiation& aInstantiation)
michael@0:         : mAssignments(aInstantiation.mAssignments),
michael@0:           mSupport(aInstantiation.mSupport) {
michael@0:         MOZ_COUNT_CTOR(Instantiation); }
michael@0: 
michael@0:     Instantiation& operator=(const Instantiation& aInstantiation) {
michael@0:         mAssignments = aInstantiation.mAssignments;
michael@0:         mSupport  = aInstantiation.mSupport;
michael@0:         return *this; }
michael@0: 
michael@0:     ~Instantiation() { MOZ_COUNT_DTOR(Instantiation); }
michael@0: 
michael@0:     /**
michael@0:      * Add the specified variable-to-value assignment to the instantiation's
michael@0:      * set of assignments.
michael@0:      * @param aVariable the variable to which is being assigned
michael@0:      * @param aValue the value that is being assigned
michael@0:      * @return NS_OK if no errors, NS_ERROR_OUT_OF_MEMORY if there
michael@0:      *   is not enough memory to perform the operation
michael@0:      */
michael@0:     nsresult AddAssignment(nsIAtom* aVariable, nsIRDFNode* aValue) {
michael@0:         mAssignments.Add(nsAssignment(aVariable, aValue));
michael@0:         return NS_OK; }
michael@0: 
michael@0:     /**
michael@0:      * Add a memory element to the set of memory elements that are
michael@0:      * supporting the instantiation
michael@0:      * @param aMemoryElement the memory element to add to the
michael@0:      *   instantiation's set of support
michael@0:      * @return NS_OK if no errors occurred, NS_ERROR_OUT_OF_MEMORY
michael@0:      *   if there is not enough memory to perform the operation.
michael@0:      */
michael@0:     nsresult AddSupportingElement(MemoryElement* aMemoryElement) {
michael@0:         mSupport.Add(aMemoryElement);
michael@0:         return NS_OK; }
michael@0: 
michael@0:     bool Equals(const Instantiation& aInstantiation) const {
michael@0:         return mAssignments == aInstantiation.mAssignments; }
michael@0: 
michael@0:     bool operator==(const Instantiation& aInstantiation) const {
michael@0:         return Equals(aInstantiation); }
michael@0: 
michael@0:     bool operator!=(const Instantiation& aInstantiation) const {
michael@0:         return !Equals(aInstantiation); }
michael@0: 
michael@0:     static PLHashNumber Hash(const void* aKey);
michael@0:     static int Compare(const void* aLeft, const void* aRight);
michael@0: };
michael@0: 
michael@0: 
michael@0: //----------------------------------------------------------------------
michael@0: 
michael@0: /**
michael@0:  * A collection of intantiations
michael@0:  */
michael@0: class InstantiationSet
michael@0: {
michael@0: public:
michael@0:     InstantiationSet();
michael@0:     InstantiationSet(const InstantiationSet& aInstantiationSet);
michael@0:     InstantiationSet& operator=(const InstantiationSet& aInstantiationSet);
michael@0: 
michael@0:     ~InstantiationSet() {
michael@0:         MOZ_COUNT_DTOR(InstantiationSet);
michael@0:         Clear(); }
michael@0: 
michael@0:     class ConstIterator;
michael@0:     friend class ConstIterator;
michael@0: 
michael@0:     class Iterator;
michael@0:     friend class Iterator;
michael@0: 
michael@0:     friend class nsXULTemplateResultSetRDF; // so it can get to the List
michael@0: 
michael@0: protected:
michael@0:     class List {
michael@0:     public:
michael@0:         Instantiation mInstantiation;
michael@0:         List*         mNext;
michael@0:         List*         mPrev;
michael@0: 
michael@0:         List() { MOZ_COUNT_CTOR(InstantiationSet::List); }
michael@0:         ~List() { MOZ_COUNT_DTOR(InstantiationSet::List); }
michael@0:     };
michael@0: 
michael@0:     List mHead;
michael@0: 
michael@0: public:
michael@0:     class ConstIterator {
michael@0:     protected:
michael@0:         friend class Iterator; // XXXwaterson so broken.
michael@0:         List* mCurrent;
michael@0: 
michael@0:     public:
michael@0:         ConstIterator(List* aList) : mCurrent(aList) {}
michael@0: 
michael@0:         ConstIterator(const ConstIterator& aConstIterator)
michael@0:             : mCurrent(aConstIterator.mCurrent) {}
michael@0: 
michael@0:         ConstIterator& operator=(const ConstIterator& aConstIterator) {
michael@0:             mCurrent = aConstIterator.mCurrent;
michael@0:             return *this; }
michael@0: 
michael@0:         ConstIterator& operator++() {
michael@0:             mCurrent = mCurrent->mNext;
michael@0:             return *this; }
michael@0: 
michael@0:         ConstIterator operator++(int) {
michael@0:             ConstIterator result(*this);
michael@0:             mCurrent = mCurrent->mNext;
michael@0:             return result; }
michael@0: 
michael@0:         ConstIterator& operator--() {
michael@0:             mCurrent = mCurrent->mPrev;
michael@0:             return *this; }
michael@0: 
michael@0:         ConstIterator operator--(int) {
michael@0:             ConstIterator result(*this);
michael@0:             mCurrent = mCurrent->mPrev;
michael@0:             return result; }
michael@0: 
michael@0:         const Instantiation& operator*() const {
michael@0:             return mCurrent->mInstantiation; }
michael@0: 
michael@0:         const Instantiation* operator->() const {
michael@0:             return &mCurrent->mInstantiation; }
michael@0: 
michael@0:         bool operator==(const ConstIterator& aConstIterator) const {
michael@0:             return mCurrent == aConstIterator.mCurrent; }
michael@0: 
michael@0:         bool operator!=(const ConstIterator& aConstIterator) const {
michael@0:             return mCurrent != aConstIterator.mCurrent; }
michael@0:     };
michael@0: 
michael@0:     ConstIterator First() const { return ConstIterator(mHead.mNext); }
michael@0:     ConstIterator Last() const { return ConstIterator(const_cast<List*>(&mHead)); }
michael@0: 
michael@0:     class Iterator : public ConstIterator {
michael@0:     public:
michael@0:         Iterator(List* aList) : ConstIterator(aList) {}
michael@0: 
michael@0:         Iterator& operator++() {
michael@0:             mCurrent = mCurrent->mNext;
michael@0:             return *this; }
michael@0: 
michael@0:         Iterator operator++(int) {
michael@0:             Iterator result(*this);
michael@0:             mCurrent = mCurrent->mNext;
michael@0:             return result; }
michael@0: 
michael@0:         Iterator& operator--() {
michael@0:             mCurrent = mCurrent->mPrev;
michael@0:             return *this; }
michael@0: 
michael@0:         Iterator operator--(int) {
michael@0:             Iterator result(*this);
michael@0:             mCurrent = mCurrent->mPrev;
michael@0:             return result; }
michael@0: 
michael@0:         Instantiation& operator*() const {
michael@0:             return mCurrent->mInstantiation; }
michael@0: 
michael@0:         Instantiation* operator->() const {
michael@0:             return &mCurrent->mInstantiation; }
michael@0: 
michael@0:         bool operator==(const ConstIterator& aConstIterator) const {
michael@0:             return mCurrent == aConstIterator.mCurrent; }
michael@0: 
michael@0:         bool operator!=(const ConstIterator& aConstIterator) const {
michael@0:             return mCurrent != aConstIterator.mCurrent; }
michael@0: 
michael@0:         friend class InstantiationSet;
michael@0:     };
michael@0: 
michael@0:     Iterator First() { return Iterator(mHead.mNext); }
michael@0:     Iterator Last() { return Iterator(&mHead); }
michael@0: 
michael@0:     bool Empty() const { return First() == Last(); }
michael@0: 
michael@0:     Iterator Append(const Instantiation& aInstantiation) {
michael@0:         return Insert(Last(), aInstantiation); }
michael@0: 
michael@0:     Iterator Insert(Iterator aBefore, const Instantiation& aInstantiation);
michael@0: 
michael@0:     Iterator Erase(Iterator aElement);
michael@0: 
michael@0:     void Clear();
michael@0: 
michael@0:     bool HasAssignmentFor(nsIAtom* aVariable) const;
michael@0: };
michael@0: 
michael@0: //----------------------------------------------------------------------
michael@0: 
michael@0: /**
michael@0:  * A abstract base class for all nodes in the rule network
michael@0:  */
michael@0: class ReteNode
michael@0: {
michael@0: public:
michael@0:     ReteNode() {}
michael@0:     virtual ~ReteNode() {}
michael@0: 
michael@0:     /**
michael@0:      * Propagate a set of instantiations "down" through the
michael@0:      * network. Each instantiation is a partial set of
michael@0:      * variable-to-value assignments, along with the memory elements
michael@0:      * that support it.
michael@0:      *
michael@0:      * The node must evaluate each instantiation, and either 1)
michael@0:      * extend it with additional assignments and memory-element
michael@0:      * support, or 2) remove it from the set because it is
michael@0:      * inconsistent with the constraints that this node applies.
michael@0:      *
michael@0:      * The node must then pass the resulting instantiation set along
michael@0:      * to any of its children in the network. (In other words, the
michael@0:      * node must recursively call Propagate() on its children. We
michael@0:      * should fix this to make the algorithm interruptable.)
michael@0:      *
michael@0:      * See TestNode::Propagate for details about instantiation set ownership
michael@0:      *
michael@0:      * @param aInstantiations the set of instantiations to propagate
michael@0:      *   down through the network.
michael@0:      * @param aIsUpdate true if updating, false for first generation
michael@0:      * @param aTakenInstantiations true if the ownership over aInstantiations
michael@0:      *                             has been taken from the caller. If false,
michael@0:      *                             the caller owns it.
michael@0:      * @return NS_OK if no errors occurred.
michael@0:      */
michael@0:     virtual nsresult Propagate(InstantiationSet& aInstantiations,
michael@0:                                bool aIsUpdate, bool& aTakenInstantiations) = 0;
michael@0: };
michael@0: 
michael@0: //----------------------------------------------------------------------
michael@0: 
michael@0: /**
michael@0:  * A collection of nodes in the rule network
michael@0:  */
michael@0: class ReteNodeSet
michael@0: {
michael@0: public:
michael@0:     ReteNodeSet();
michael@0:     ~ReteNodeSet();
michael@0: 
michael@0:     nsresult Add(ReteNode* aNode);
michael@0:     nsresult Clear();
michael@0: 
michael@0:     class Iterator;
michael@0: 
michael@0:     class ConstIterator {
michael@0:     public:
michael@0:         ConstIterator(ReteNode** aNode) : mCurrent(aNode) {}
michael@0: 
michael@0:         ConstIterator(const ConstIterator& aConstIterator)
michael@0:             : mCurrent(aConstIterator.mCurrent) {}
michael@0: 
michael@0:         ConstIterator& operator=(const ConstIterator& aConstIterator) {
michael@0:             mCurrent = aConstIterator.mCurrent;
michael@0:             return *this; }
michael@0: 
michael@0:         ConstIterator& operator++() {
michael@0:             ++mCurrent;
michael@0:             return *this; }
michael@0: 
michael@0:         ConstIterator operator++(int) {
michael@0:             ConstIterator result(*this);
michael@0:             ++mCurrent;
michael@0:             return result; }
michael@0: 
michael@0:         const ReteNode* operator*() const {
michael@0:             return *mCurrent; }
michael@0: 
michael@0:         const ReteNode* operator->() const {
michael@0:             return *mCurrent; }
michael@0: 
michael@0:         bool operator==(const ConstIterator& aConstIterator) const {
michael@0:             return mCurrent == aConstIterator.mCurrent; }
michael@0: 
michael@0:         bool operator!=(const ConstIterator& aConstIterator) const {
michael@0:             return mCurrent != aConstIterator.mCurrent; }
michael@0: 
michael@0:     protected:
michael@0:         friend class Iterator; // XXXwaterson this is so wrong!
michael@0:         ReteNode** mCurrent;
michael@0:     };
michael@0: 
michael@0:     ConstIterator First() const { return ConstIterator(mNodes); }
michael@0:     ConstIterator Last() const { return ConstIterator(mNodes + mCount); }
michael@0: 
michael@0:     class Iterator : public ConstIterator {
michael@0:     public:
michael@0:         Iterator(ReteNode** aNode) : ConstIterator(aNode) {}
michael@0: 
michael@0:         Iterator& operator++() {
michael@0:             ++mCurrent;
michael@0:             return *this; }
michael@0: 
michael@0:         Iterator operator++(int) {
michael@0:             Iterator result(*this);
michael@0:             ++mCurrent;
michael@0:             return result; }
michael@0: 
michael@0:         ReteNode* operator*() const {
michael@0:             return *mCurrent; }
michael@0: 
michael@0:         ReteNode* operator->() const {
michael@0:             return *mCurrent; }
michael@0: 
michael@0:         bool operator==(const ConstIterator& aConstIterator) const {
michael@0:             return mCurrent == aConstIterator.mCurrent; }
michael@0: 
michael@0:         bool operator!=(const ConstIterator& aConstIterator) const {
michael@0:             return mCurrent != aConstIterator.mCurrent; }
michael@0:     };
michael@0: 
michael@0:     Iterator First() { return Iterator(mNodes); }
michael@0:     Iterator Last() { return Iterator(mNodes + mCount); }
michael@0: 
michael@0:     int32_t Count() const { return mCount; }
michael@0: 
michael@0: protected:
michael@0:     ReteNode** mNodes;
michael@0:     int32_t mCount;
michael@0:     int32_t mCapacity;
michael@0: };
michael@0: 
michael@0: //----------------------------------------------------------------------
michael@0: 
michael@0: /**
michael@0:  * A node that applies a test condition to a set of instantiations.
michael@0:  *
michael@0:  * This class provides implementations of Propagate() and Constrain()
michael@0:  * in terms of one simple operation, FilterInstantiations(). A node
michael@0:  * that is a "simple test node" in a rule network should derive from
michael@0:  * this class, and need only implement FilterInstantiations().
michael@0:  */
michael@0: class TestNode : public ReteNode
michael@0: {
michael@0: public:
michael@0:     TestNode(TestNode* aParent);
michael@0: 
michael@0:     /**
michael@0:      * Retrieve the test node's parent
michael@0:      * @return the test node's parent
michael@0:      */
michael@0:     TestNode* GetParent() const { return mParent; }
michael@0: 
michael@0:     /**
michael@0:      * Calls FilterInstantiations() on the instantiation set, and if
michael@0:      * the resulting set isn't empty, propagates the new set down to
michael@0:      * each of the test node's children.
michael@0:      *
michael@0:      * Note that the caller of Propagate is responsible for deleting
michael@0:      * aInstantiations if necessary as described below.
michael@0:      *
michael@0:      * Propagate may be called in update or non-update mode as indicated
michael@0:      * by the aIsUpdate argument. Non-update mode is used when initially
michael@0:      * generating results, whereas update mode is used when the datasource
michael@0:      * changes and new results might be available.
michael@0:      *
michael@0:      * The last node in a chain of TestNodes is always an nsInstantiationNode.
michael@0:      * In non-update mode, this nsInstantiationNode will cache the results
michael@0:      * in the query using the SetCachedResults method. The query processor
michael@0:      * takes these cached results and creates a nsXULTemplateResultSetRDF
michael@0:      * which is the enumeration returned to the template builder. This
michael@0:      * nsXULTemplateResultSetRDF owns the instantiations and they will be
michael@0:      * deleted when the nsXULTemplateResultSetRDF goes away.
michael@0:      *
michael@0:      * In update mode, the nsInstantiationNode node will iterate over the
michael@0:      * instantiations itself and callback to the builder to update any matches
michael@0:      * and generated content. If no instantiations match, then the builder
michael@0:      * will never be called.
michael@0:      *
michael@0:      * Thus, the difference between update and non-update modes is that in
michael@0:      * update mode, the results and instantiations have been already handled
michael@0:      * whereas in non-update mode they are expected to be returned in an
michael@0:      * nsXULTemplateResultSetRDF for further processing by the builder.
michael@0:      *
michael@0:      * Regardless, aTakenInstantiations will be set to true if the
michael@0:      * ownership over aInstantiations has been transferred to a result set.
michael@0:      * If set to false, the caller is still responsible for aInstantiations.
michael@0:      * aTakenInstantiations will be set properly even if an error occurs.
michael@0:      */
michael@0:     virtual nsresult Propagate(InstantiationSet& aInstantiations,
michael@0:                                bool aIsUpdate, bool& aTakenInstantiations) MOZ_OVERRIDE;
michael@0: 
michael@0:     /**
michael@0:      * This is called by a child node on its parent to allow the
michael@0:      * parent's constraints to apply to the set of instantiations.
michael@0:      *
michael@0:      * A node must iterate through the set of instantiations, and for
michael@0:      * each instantiation, either 1) extend the instantiation by
michael@0:      * adding variable-to-value assignments and memory element support
michael@0:      * for those assignments, or 2) remove the instantiation because
michael@0:      * it is inconsistent.
michael@0:      *
michael@0:      * The node must then pass the resulting set of instantiations up
michael@0:      * to its parent (by recursive call; we should make this iterative
michael@0:      * & interruptable at some point.)
michael@0:      * 
michael@0:      * @param aInstantiations the set of instantiations that must
michael@0:      *   be constrained
michael@0:      * @return NS_OK if no errors occurred
michael@0:      */
michael@0:     virtual nsresult Constrain(InstantiationSet& aInstantiations);
michael@0: 
michael@0:     /**
michael@0:      * Given a set of instantiations, filter out any that are
michael@0:      * inconsistent with the test node's test, and append
michael@0:      * variable-to-value assignments and memory element support for
michael@0:      * those which do pass the test node's test.
michael@0:      *
michael@0:      * @param aInstantiations the set of instantiations to be
michael@0:      *        filtered
michael@0:      * @param aCantHandleYet [out] true if the instantiations do not contain
michael@0:      *        enough information to constrain the data. May be null if this
michael@0:      *        isn't important to the caller.
michael@0:      * @return NS_OK if no errors occurred.
michael@0:      */
michael@0:     virtual nsresult FilterInstantiations(InstantiationSet& aInstantiations,
michael@0:                                           bool* aCantHandleYet) const = 0;
michael@0:     //XXX probably better named "ApplyConstraints" or "Discrminiate" or something
michael@0: 
michael@0:     /**
michael@0:      * Add another node as a child of this node.
michael@0:      * @param aNode the node to add.
michael@0:      * @return NS_OK if no errors occur.
michael@0:      */
michael@0:     nsresult AddChild(ReteNode* aNode) { return mKids.Add(aNode); }
michael@0: 
michael@0:     /**
michael@0:      * Remove all the children of this node
michael@0:      * @return NS_OK if no errors occur.
michael@0:      */
michael@0:     nsresult RemoveAllChildren() { return mKids.Clear(); }
michael@0: 
michael@0: protected:
michael@0:     TestNode* mParent;
michael@0:     ReteNodeSet mKids;
michael@0: };
michael@0: 
michael@0: #endif // nsRuleNetwork_h__