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:   Implementations for the rule network classes.
michael@0: 
michael@0:   To Do.
michael@0: 
michael@0:   - Constrain() & Propagate() still feel like they are poorly named.
michael@0:   - As do Instantiation and InstantiationSet.
michael@0:   - Make InstantiationSet share and do copy-on-write.
michael@0:   - Make things iterative, instead of recursive.
michael@0: 
michael@0:  */
michael@0: 
michael@0: #include "nscore.h"
michael@0: #include "nsCOMPtr.h"
michael@0: #include "plhash.h"
michael@0: 
michael@0: #include "prlog.h"
michael@0: #ifdef PR_LOGGING
michael@0: extern PRLogModuleInfo* gXULTemplateLog;
michael@0: 
michael@0: #include "nsString.h"
michael@0: #include "nsUnicharUtils.h"
michael@0: #include "nsXULContentUtils.h"
michael@0: 
michael@0: #endif
michael@0: 
michael@0: #include "nsRuleNetwork.h"
michael@0: #include "nsXULTemplateResultSetRDF.h"
michael@0: #include "nsRDFConMemberTestNode.h"
michael@0: #include "nsRDFPropertyTestNode.h"
michael@0: 
michael@0: using namespace mozilla;
michael@0: 
michael@0: //----------------------------------------------------------------------
michael@0: //
michael@0: // nsRuleNetwork
michael@0: //
michael@0: 
michael@0: nsresult
michael@0: MemoryElementSet::Add(MemoryElement* aElement)
michael@0: {
michael@0:     for (ConstIterator element = First(); element != Last(); ++element) {
michael@0:         if (*element == *aElement) {
michael@0:             // We've already got this element covered. Since Add()
michael@0:             // assumes ownership, and we aren't going to need this,
michael@0:             // just nuke it.
michael@0:             delete aElement;
michael@0:             return NS_OK;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     List* list = new List;
michael@0:     if (! list)
michael@0:         return NS_ERROR_OUT_OF_MEMORY;
michael@0: 
michael@0:     list->mElement = aElement;
michael@0:     list->mRefCnt  = 1;
michael@0:     list->mNext    = mElements;
michael@0: 
michael@0:     mElements = list;
michael@0: 
michael@0:     return NS_OK;
michael@0: }
michael@0: 
michael@0: 
michael@0: //----------------------------------------------------------------------
michael@0: 
michael@0: nsresult
michael@0: nsAssignmentSet::Add(const nsAssignment& aAssignment)
michael@0: {
michael@0:     NS_PRECONDITION(! HasAssignmentFor(aAssignment.mVariable), "variable already bound");
michael@0: 
michael@0:     // XXXndeakin should this just silently fail?
michael@0:     if (HasAssignmentFor(aAssignment.mVariable))
michael@0:         return NS_ERROR_UNEXPECTED;
michael@0: 
michael@0:     List* list = new List(aAssignment);
michael@0:     if (! list)
michael@0:         return NS_ERROR_OUT_OF_MEMORY;
michael@0: 
michael@0:     list->mRefCnt     = 1;
michael@0:     list->mNext       = mAssignments;
michael@0: 
michael@0:     mAssignments = list;
michael@0: 
michael@0:     return NS_OK;
michael@0: }
michael@0: 
michael@0: int32_t
michael@0: nsAssignmentSet::Count() const
michael@0: {
michael@0:     int32_t count = 0;
michael@0:     for (ConstIterator assignment = First(); assignment != Last(); ++assignment)
michael@0:         ++count;
michael@0: 
michael@0:     return count;
michael@0: }
michael@0: 
michael@0: bool
michael@0: nsAssignmentSet::HasAssignment(nsIAtom* aVariable, nsIRDFNode* aValue) const
michael@0: {
michael@0:     for (ConstIterator assignment = First(); assignment != Last(); ++assignment) {
michael@0:         if (assignment->mVariable == aVariable && assignment->mValue == aValue)
michael@0:             return true;
michael@0:     }
michael@0: 
michael@0:     return false;
michael@0: }
michael@0: 
michael@0: bool
michael@0: nsAssignmentSet::HasAssignmentFor(nsIAtom* aVariable) const
michael@0: {
michael@0:     for (ConstIterator assignment = First(); assignment != Last(); ++assignment) {
michael@0:         if (assignment->mVariable == aVariable)
michael@0:             return true;
michael@0:     }
michael@0: 
michael@0:     return false;
michael@0: }
michael@0: 
michael@0: bool
michael@0: nsAssignmentSet::GetAssignmentFor(nsIAtom* aVariable, nsIRDFNode** aValue) const
michael@0: {
michael@0:     for (ConstIterator assignment = First(); assignment != Last(); ++assignment) {
michael@0:         if (assignment->mVariable == aVariable) {
michael@0:             *aValue = assignment->mValue;
michael@0:             NS_IF_ADDREF(*aValue);
michael@0:             return true;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     *aValue = nullptr;
michael@0:     return false;
michael@0: }
michael@0: 
michael@0: bool
michael@0: nsAssignmentSet::Equals(const nsAssignmentSet& aSet) const
michael@0: {
michael@0:     if (aSet.mAssignments == mAssignments)
michael@0:         return true;
michael@0: 
michael@0:     // If they have a different number of assignments, then they're different.
michael@0:     if (Count() != aSet.Count())
michael@0:         return false;
michael@0: 
michael@0:     // XXX O(n^2)! Ugh!
michael@0:     nsCOMPtr<nsIRDFNode> value;
michael@0:     for (ConstIterator assignment = First(); assignment != Last(); ++assignment) {
michael@0:         if (! aSet.GetAssignmentFor(assignment->mVariable, getter_AddRefs(value)))
michael@0:             return false;
michael@0: 
michael@0:         if (assignment->mValue != value)
michael@0:             return false;
michael@0:     }
michael@0: 
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: //----------------------------------------------------------------------
michael@0: 
michael@0: PLHashNumber
michael@0: Instantiation::Hash(const void* aKey)
michael@0: {
michael@0:     const Instantiation* inst = static_cast<const Instantiation*>(aKey);
michael@0: 
michael@0:     PLHashNumber result = 0;
michael@0: 
michael@0:     nsAssignmentSet::ConstIterator last = inst->mAssignments.Last();
michael@0:     for (nsAssignmentSet::ConstIterator assignment = inst->mAssignments.First();
michael@0:          assignment != last; ++assignment)
michael@0:         result ^= assignment->Hash();
michael@0: 
michael@0:     return result;
michael@0: }
michael@0: 
michael@0: 
michael@0: int
michael@0: Instantiation::Compare(const void* aLeft, const void* aRight)
michael@0: {
michael@0:     const Instantiation* left  = static_cast<const Instantiation*>(aLeft);
michael@0:     const Instantiation* right = static_cast<const Instantiation*>(aRight);
michael@0: 
michael@0:     return *left == *right;
michael@0: }
michael@0: 
michael@0: 
michael@0: //----------------------------------------------------------------------
michael@0: //
michael@0: // InstantiationSet
michael@0: //
michael@0: 
michael@0: InstantiationSet::InstantiationSet()
michael@0: {
michael@0:     mHead.mPrev = mHead.mNext = &mHead;
michael@0:     MOZ_COUNT_CTOR(InstantiationSet);
michael@0: }
michael@0: 
michael@0: 
michael@0: InstantiationSet::InstantiationSet(const InstantiationSet& aInstantiationSet)
michael@0: {
michael@0:     mHead.mPrev = mHead.mNext = &mHead;
michael@0: 
michael@0:     // XXX replace with copy-on-write foo
michael@0:     ConstIterator last = aInstantiationSet.Last();
michael@0:     for (ConstIterator inst = aInstantiationSet.First(); inst != last; ++inst)
michael@0:         Append(*inst);
michael@0: 
michael@0:     MOZ_COUNT_CTOR(InstantiationSet);
michael@0: }
michael@0: 
michael@0: InstantiationSet&
michael@0: InstantiationSet::operator=(const InstantiationSet& aInstantiationSet)
michael@0: {
michael@0:     // XXX replace with copy-on-write foo
michael@0:     Clear();
michael@0: 
michael@0:     ConstIterator last = aInstantiationSet.Last();
michael@0:     for (ConstIterator inst = aInstantiationSet.First(); inst != last; ++inst)
michael@0:         Append(*inst);
michael@0: 
michael@0:     return *this;
michael@0: }
michael@0: 
michael@0: 
michael@0: void
michael@0: InstantiationSet::Clear()
michael@0: {
michael@0:     Iterator inst = First();
michael@0:     while (inst != Last())
michael@0:         Erase(inst++);
michael@0: }
michael@0: 
michael@0: 
michael@0: InstantiationSet::Iterator
michael@0: InstantiationSet::Insert(Iterator aIterator, const Instantiation& aInstantiation)
michael@0: {
michael@0:     List* newelement = new List();
michael@0:     if (newelement) {
michael@0:         newelement->mInstantiation = aInstantiation;
michael@0: 
michael@0:         aIterator.mCurrent->mPrev->mNext = newelement;
michael@0: 
michael@0:         newelement->mNext = aIterator.mCurrent;
michael@0:         newelement->mPrev = aIterator.mCurrent->mPrev;
michael@0: 
michael@0:         aIterator.mCurrent->mPrev = newelement;
michael@0:     }
michael@0:     return aIterator;
michael@0: }
michael@0: 
michael@0: InstantiationSet::Iterator
michael@0: InstantiationSet::Erase(Iterator aIterator)
michael@0: {
michael@0:     Iterator result = aIterator;
michael@0:     ++result;
michael@0:     aIterator.mCurrent->mNext->mPrev = aIterator.mCurrent->mPrev;
michael@0:     aIterator.mCurrent->mPrev->mNext = aIterator.mCurrent->mNext;
michael@0:     delete aIterator.mCurrent;
michael@0:     return result;
michael@0: }
michael@0: 
michael@0: 
michael@0: bool
michael@0: InstantiationSet::HasAssignmentFor(nsIAtom* aVariable) const
michael@0: {
michael@0:     return !Empty() ? First()->mAssignments.HasAssignmentFor(aVariable) : false;
michael@0: }
michael@0: 
michael@0: //----------------------------------------------------------------------
michael@0: //
michael@0: // ReteNode
michael@0: //
michael@0: //   The basic node in the network.
michael@0: //
michael@0: 
michael@0: //----------------------------------------------------------------------
michael@0: //
michael@0: // TestNode
michael@0: //
michael@0: //   to do:
michael@0: //     - FilterInstantiations() is poorly named
michael@0: //
michael@0: 
michael@0: 
michael@0: TestNode::TestNode(TestNode* aParent)
michael@0:     : mParent(aParent)
michael@0: {
michael@0: }
michael@0: 
michael@0: nsresult
michael@0: TestNode::Propagate(InstantiationSet& aInstantiations,
michael@0:                     bool aIsUpdate, bool& aTakenInstantiations)
michael@0: {
michael@0:     PR_LOG(gXULTemplateLog, PR_LOG_DEBUG,
michael@0:            ("TestNode[%p]: Propagate() begin", this));
michael@0: 
michael@0:     aTakenInstantiations = false;
michael@0: 
michael@0:     nsresult rv = FilterInstantiations(aInstantiations, nullptr);
michael@0:     if (NS_FAILED(rv))
michael@0:         return rv;
michael@0: 
michael@0:     // if there is more than one child, each will need to be supplied with the
michael@0:     // original set of instantiations from this node, so create a copy in this
michael@0:     // case. If there is only one child, optimize and just pass the
michael@0:     // instantiations along to the child without copying
michael@0:     bool shouldCopy = (mKids.Count() > 1);
michael@0: 
michael@0:     // See the header file for details about how instantiation ownership works.
michael@0:     if (! aInstantiations.Empty()) {
michael@0:         ReteNodeSet::Iterator last = mKids.Last();
michael@0:         for (ReteNodeSet::Iterator kid = mKids.First(); kid != last; ++kid) {
michael@0:             PR_LOG(gXULTemplateLog, PR_LOG_DEBUG,
michael@0:                    ("TestNode[%p]: Propagate() passing to child %p", this, kid.operator->()));
michael@0: 
michael@0:             // create a copy of the instantiations
michael@0:             if (shouldCopy) {
michael@0:                 bool owned = false;
michael@0:                 InstantiationSet* instantiations =
michael@0:                     new InstantiationSet(aInstantiations);
michael@0:                 if (!instantiations)
michael@0:                     return NS_ERROR_OUT_OF_MEMORY;
michael@0:                 rv = kid->Propagate(*instantiations, aIsUpdate, owned);
michael@0:                 if (!owned)
michael@0:                     delete instantiations;
michael@0:                 if (NS_FAILED(rv))
michael@0:                     return rv;
michael@0:             }
michael@0:             else {
michael@0:                 rv = kid->Propagate(aInstantiations, aIsUpdate, aTakenInstantiations);
michael@0:                 if (NS_FAILED(rv))
michael@0:                     return rv;
michael@0:             }
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     PR_LOG(gXULTemplateLog, PR_LOG_DEBUG,
michael@0:            ("TestNode[%p]: Propagate() end", this));
michael@0: 
michael@0:     return NS_OK;
michael@0: }
michael@0: 
michael@0: 
michael@0: nsresult
michael@0: TestNode::Constrain(InstantiationSet& aInstantiations)
michael@0: {
michael@0:     nsresult rv;
michael@0: 
michael@0:     PR_LOG(gXULTemplateLog, PR_LOG_DEBUG,
michael@0:            ("TestNode[%p]: Constrain() begin", this));
michael@0: 
michael@0:     // if the cantHandleYet flag is set by FilterInstantiations,
michael@0:     // there isn't enough information yet available to fill in.
michael@0:     // For this, continue the constrain all the way to the top
michael@0:     // and then call FilterInstantiations again afterwards. This
michael@0:     // should fill in any missing information.
michael@0:     bool cantHandleYet = false;
michael@0:     rv = FilterInstantiations(aInstantiations, &cantHandleYet);
michael@0:     if (NS_FAILED(rv)) return rv;
michael@0: 
michael@0:     if (mParent && (!aInstantiations.Empty() || cantHandleYet)) {
michael@0:         // if we still have instantiations, or if the instantiations
michael@0:         // could not be filled in yet, then ride 'em on up to the
michael@0:         // parent to narrow them.
michael@0: 
michael@0:         PR_LOG(gXULTemplateLog, PR_LOG_DEBUG,
michael@0:                ("TestNode[%p]: Constrain() passing to parent %p", this, mParent));
michael@0: 
michael@0:         rv = mParent->Constrain(aInstantiations);
michael@0: 
michael@0:         if (NS_SUCCEEDED(rv) && cantHandleYet)
michael@0:             rv = FilterInstantiations(aInstantiations, nullptr);
michael@0:     }
michael@0:     else {
michael@0:         PR_LOG(gXULTemplateLog, PR_LOG_DEBUG,
michael@0:                ("TestNode[%p]: Constrain() failed", this));
michael@0: 
michael@0:         rv = NS_OK;
michael@0:     }
michael@0: 
michael@0:     PR_LOG(gXULTemplateLog, PR_LOG_DEBUG,
michael@0:            ("TestNode[%p]: Constrain() end", this));
michael@0: 
michael@0:     return rv;
michael@0: }
michael@0: 
michael@0: 
michael@0: //----------------------------------------------------------------------
michael@0: 
michael@0: ReteNodeSet::ReteNodeSet()
michael@0:     : mNodes(nullptr), mCount(0), mCapacity(0)
michael@0: {
michael@0: }
michael@0: 
michael@0: ReteNodeSet::~ReteNodeSet()
michael@0: {
michael@0:     Clear();
michael@0: }
michael@0: 
michael@0: nsresult
michael@0: ReteNodeSet::Add(ReteNode* aNode)
michael@0: {
michael@0:     NS_PRECONDITION(aNode != nullptr, "null ptr");
michael@0:     if (! aNode)
michael@0:         return NS_ERROR_NULL_POINTER;
michael@0: 
michael@0:     if (mCount >= mCapacity) {
michael@0:         int32_t capacity = mCapacity + 4;
michael@0:         ReteNode** nodes = new ReteNode*[capacity];
michael@0:         if (! nodes)
michael@0:             return NS_ERROR_OUT_OF_MEMORY;
michael@0: 
michael@0:         for (int32_t i = mCount - 1; i >= 0; --i)
michael@0:             nodes[i] = mNodes[i];
michael@0: 
michael@0:         delete[] mNodes;
michael@0: 
michael@0:         mNodes = nodes;
michael@0:         mCapacity = capacity;
michael@0:     }
michael@0: 
michael@0:     mNodes[mCount++] = aNode;
michael@0:     return NS_OK;
michael@0: }
michael@0: 
michael@0: nsresult
michael@0: ReteNodeSet::Clear()
michael@0: {
michael@0:     delete[] mNodes;
michael@0:     mNodes = nullptr;
michael@0:     mCount = mCapacity = 0;
michael@0:     return NS_OK;
michael@0: }