Back to index

lightning-sunbird  0.9+nobinonly
nsRuleNetwork.cpp
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   Implementations for the rule network classes.
00042 
00043   To Do.
00044 
00045   - Constrain() & Propagate() still feel like they are poorly named.
00046   - As do Instantiation and InstantiationSet.
00047   - Make InstantiationSet share and do copy-on-write.
00048   - Make things iterative, instead of recursive.
00049 
00050  */
00051 
00052 #include "nscore.h"
00053 #include "nsCOMPtr.h"
00054 #include "nsCRT.h"
00055 #include "nsIComponentManager.h"
00056 #include "nsIContent.h"
00057 #include "nsRuleNetwork.h"
00058 #include "plhash.h"
00059 #include "nsReadableUtils.h"
00060 
00061 #include "prlog.h"
00062 #ifdef PR_LOGGING
00063 extern PRLogModuleInfo* gXULTemplateLog;
00064 #endif
00065 
00066 //----------------------------------------------------------------------
00067 //
00068 // nsRuleNetwork
00069 //
00070 
00071 static PLDHashNumber PR_CALLBACK
00072 HashEntry(PLDHashTable* aTable, const void* aKey)
00073 {
00074     return nsCRT::HashCode(NS_STATIC_CAST(const PRUnichar*, aKey));
00075 }
00076 
00077 static PRBool PR_CALLBACK
00078 MatchEntry(PLDHashTable* aTable, const PLDHashEntryHdr* aEntry, const void* aKey)
00079 {
00080     const nsRuleNetwork::SymtabEntry* entry =
00081         NS_REINTERPRET_CAST(const nsRuleNetwork::SymtabEntry*, aEntry);
00082 
00083     return 0 == nsCRT::strcmp(entry->mSymbol, NS_STATIC_CAST(const PRUnichar*, aKey));
00084 }
00085 
00086 static void PR_CALLBACK
00087 ClearEntry(PLDHashTable* aTable, PLDHashEntryHdr* aEntry)
00088 {
00089     nsRuleNetwork::SymtabEntry* entry =
00090         NS_REINTERPRET_CAST(nsRuleNetwork::SymtabEntry*, aEntry);
00091 
00092     nsCRT::free(entry->mSymbol);
00093     PL_DHashClearEntryStub(aTable, aEntry);
00094 }
00095 
00096 PLDHashTableOps nsRuleNetwork::gOps = {
00097     PL_DHashAllocTable,
00098     PL_DHashFreeTable,
00099     PL_DHashGetKeyStub,
00100     HashEntry,
00101     MatchEntry,
00102     PL_DHashMoveEntryStub,
00103     ClearEntry,
00104     PL_DHashFinalizeStub
00105 };
00106 
00107 void
00108 nsRuleNetwork::Init()
00109 {
00110     mNextVariable = 0;
00111     if (!PL_DHashTableInit(&mSymtab, &gOps, nsnull,
00112                            sizeof(SymtabEntry), PL_DHASH_MIN_SIZE))
00113         mSymtab.ops = nsnull;
00114 }
00115 
00116 void
00117 nsRuleNetwork::Finish()
00118 {
00119     if (mSymtab.ops)
00120         PL_DHashTableFinish(&mSymtab);
00121 
00122     // We "own" the nodes. So it's up to us to delete 'em
00123     for (ReteNodeSet::Iterator node = mNodes.First(); node != mNodes.Last(); ++node)
00124         delete *node;
00125 
00126     mNodes.Clear();
00127     mRoot.RemoveAllChildren();
00128 }
00129 
00130 
00131 //----------------------------------------------------------------------
00132 //
00133 // Value
00134 //
00135 
00136 #ifdef DEBUG
00137 
00142 nsISupports*
00143 value_to_isupports(const nsIID& aIID, const Value& aValue)
00144 {
00145     nsresult rv;
00146 
00147     // Need to const_cast aValue because QI() & Release() are not const
00148     nsISupports* isupports = NS_STATIC_CAST(nsISupports*, NS_CONST_CAST(Value&, aValue));
00149     if (isupports) {
00150         nsCOMPtr<nsISupports> dummy;
00151         rv = isupports->QueryInterface(aIID, getter_AddRefs(dummy));
00152         if (NS_FAILED(rv)) {
00153             NS_ERROR("value does not support expected interface");
00154         }
00155     }
00156     return isupports;
00157 }
00158 #endif
00159 
00160 Value::Value(const Value& aValue)
00161     : mType(aValue.mType)
00162 {
00163     MOZ_COUNT_CTOR(Value);
00164 
00165     switch (mType) {
00166     case eUndefined:
00167         break;
00168 
00169     case eISupports:
00170         mISupports = aValue.mISupports;
00171         NS_IF_ADDREF(mISupports);
00172         break;
00173 
00174     case eString:
00175         mString = nsCRT::strdup(aValue.mString);
00176         break;
00177 
00178     case eInteger:
00179         mInteger = aValue.mInteger;
00180         break;
00181     }
00182 }
00183 
00184 Value::Value(nsISupports* aISupports)
00185     : mType(eISupports)
00186 {
00187     MOZ_COUNT_CTOR(Value);
00188     mISupports = aISupports;
00189     NS_IF_ADDREF(mISupports);
00190 }
00191 
00192 Value::Value(const PRUnichar* aString)
00193     : mType(eString)
00194 {
00195     MOZ_COUNT_CTOR(Value);
00196     mString = nsCRT::strdup(aString);
00197 }
00198 
00199 Value::Value(PRInt32 aInteger)
00200     : mType(eInteger)
00201 {
00202     MOZ_COUNT_CTOR(Value);
00203     mInteger = aInteger;
00204 }
00205 
00206 Value&
00207 Value::operator=(const Value& aValue)
00208 {
00209     Clear();
00210 
00211     mType = aValue.mType;
00212 
00213     switch (mType) {
00214     case eUndefined:
00215         break;
00216 
00217     case eISupports:
00218         mISupports = aValue.mISupports;
00219         NS_IF_ADDREF(mISupports);
00220         break;
00221 
00222     case eString:
00223         mString = nsCRT::strdup(aValue.mString);
00224         break;
00225 
00226     case eInteger:
00227         mInteger = aValue.mInteger;
00228         break;
00229     }
00230 
00231     return *this;
00232 }
00233 
00234 Value&
00235 Value::operator=(nsISupports* aISupports)
00236 {
00237     Clear();
00238 
00239     mType = eISupports;
00240     mISupports = aISupports;
00241     NS_IF_ADDREF(mISupports);
00242 
00243     return *this;
00244 }
00245 
00246 Value&
00247 Value::operator=(const PRUnichar* aString)
00248 {
00249     Clear();
00250 
00251     mType = eString;
00252     mString = nsCRT::strdup(aString);
00253 
00254     return *this;
00255 }
00256 
00257 
00258 Value::~Value()
00259 {
00260     MOZ_COUNT_DTOR(Value);
00261     Clear();
00262 }
00263 
00264 
00265 void
00266 Value::Clear()
00267 {
00268     switch (mType) {
00269     case eInteger:
00270     case eUndefined:
00271         break;
00272 
00273     case eISupports:
00274         NS_IF_RELEASE(mISupports);
00275         break;
00276 
00277     case eString:
00278         nsCRT::free(mString);
00279         break;
00280 
00281     }
00282 }
00283 
00284 
00285 PRBool
00286 Value::Equals(const Value& aValue) const
00287 {
00288     if (mType == aValue.mType) {
00289         switch (mType) {
00290         case eUndefined:
00291             return PR_FALSE;
00292 
00293         case eISupports:
00294             return mISupports == aValue.mISupports;
00295 
00296         case eString:
00297             return nsCRT::strcmp(mString, aValue.mString) == 0;
00298 
00299         case eInteger:
00300             return mInteger == aValue.mInteger;
00301         }
00302     }
00303     return PR_FALSE;
00304 }
00305 
00306 PRBool
00307 Value::Equals(nsISupports* aISupports) const
00308 {
00309     return (mType == eISupports) && (mISupports == aISupports);
00310 }
00311 
00312 PRBool
00313 Value::Equals(const PRUnichar* aString) const
00314 {
00315     return (mType == eString) && (nsCRT::strcmp(aString, mString) == 0);
00316 }
00317 
00318 PRBool
00319 Value::Equals(PRInt32 aInteger) const
00320 {
00321     return (mType == eInteger) && (mInteger == aInteger);
00322 }
00323 
00324 
00325 PLHashNumber
00326 Value::Hash() const
00327 {
00328     PLHashNumber temp = 0;
00329 
00330     switch (mType) {
00331     case eUndefined:
00332         break;
00333 
00334     case eISupports:
00335         temp = PLHashNumber(NS_PTR_TO_INT32(mISupports)) >> 2; // strip alignment bits
00336         break;
00337 
00338     case eString:
00339         {
00340             PRUnichar* p = mString;
00341             PRUnichar c;
00342             while ((c = *p) != 0) {
00343                 temp = (temp >> 28) ^ (temp << 4) ^ c;
00344                 ++p;
00345             }
00346         }
00347         break;
00348 
00349     case eInteger:
00350         temp = mInteger;
00351         break;
00352     }
00353 
00354     return temp;
00355 }
00356 
00357 
00358 Value::operator nsISupports*() const
00359 {
00360     NS_ASSERTION(mType == eISupports, "not an nsISupports");
00361     return (mType == eISupports) ? mISupports : 0;
00362 }
00363 
00364 Value::operator const PRUnichar*() const
00365 {
00366     NS_ASSERTION(mType == eString, "not a string");
00367     return (mType == eString) ? mString : 0;
00368 }
00369 
00370 Value::operator PRInt32() const
00371 {
00372     NS_ASSERTION(mType == eInteger, "not an integer");
00373     return (mType == eInteger) ? mInteger : 0;
00374 }
00375 
00376 #ifdef DEBUG
00377 #include "nsIRDFResource.h"
00378 #include "nsIRDFLiteral.h"
00379 #include "nsString.h"
00380 #include "nsPrintfCString.h"
00381 
00382 void
00383 Value::ToCString(nsACString& aResult)
00384 {
00385     switch (mType) {
00386     case eUndefined:
00387         aResult = "[(undefined)]";
00388         break;
00389 
00390     case eISupports:
00391         do {
00392             nsCOMPtr<nsIRDFResource> res = do_QueryInterface(mISupports);
00393             if (res) {
00394                 aResult = "[nsIRDFResource ";
00395                 const char* s;
00396                 res->GetValueConst(&s);
00397                 aResult += s;
00398                 aResult += "]";
00399                 break;
00400             }
00401 
00402             nsCOMPtr<nsIRDFLiteral> lit = do_QueryInterface(mISupports);
00403             if (lit) {
00404                 aResult = "[nsIRDFLiteral \"";
00405                 const PRUnichar* s;
00406                 lit->GetValueConst(&s);
00407                 AppendUTF16toUTF8(s, aResult);
00408                 aResult += "\"]";
00409                 break;
00410             }
00411 
00412             aResult = "[nsISupports ";
00413             aResult += nsPrintfCString("%p", mISupports);
00414             aResult += "]";
00415         } while (0);
00416         break;
00417 
00418     case eString:
00419         aResult = "[string \"";
00420         AppendUTF16toUTF8(mString, aResult);
00421         aResult += "\"]";
00422         break;
00423 
00424     case eInteger:
00425         aResult = "[integer ";
00426         aResult += nsPrintfCString("%d", mInteger);
00427         aResult += "]";
00428         break;
00429     }
00430 }
00431 #endif
00432 
00433 
00434 //----------------------------------------------------------------------
00435 //
00436 // VariableSet
00437 //
00438 
00439 
00440 VariableSet::VariableSet()
00441     : mVariables(nsnull), mCount(0), mCapacity(0)
00442 {
00443 }
00444 
00445 VariableSet::~VariableSet()
00446 {
00447     delete[] mVariables;
00448 }
00449 
00450 nsresult
00451 VariableSet::Add(PRInt32 aVariable)
00452 {
00453     if (Contains(aVariable))
00454         return NS_OK;
00455 
00456     if (mCount >= mCapacity) {
00457         PRInt32 capacity = mCapacity + 4;
00458         PRInt32* variables = new PRInt32[capacity];
00459         if (! variables)
00460             return NS_ERROR_OUT_OF_MEMORY;
00461 
00462         for (PRInt32 i = mCount - 1; i >= 0; --i)
00463             variables[i] = mVariables[i];
00464 
00465         delete[] mVariables;
00466 
00467         mVariables = variables;
00468         mCapacity = capacity;
00469     }
00470 
00471     mVariables[mCount++] = aVariable;
00472     return NS_OK;
00473 }
00474 
00475 nsresult
00476 VariableSet::Remove(PRInt32 aVariable)
00477 {
00478     PRInt32 i = 0;
00479     while (i < mCount) {
00480         if (aVariable == mVariables[i])
00481             break;
00482 
00483         ++i;
00484     }
00485 
00486     if (i >= mCount)
00487         return NS_OK;
00488 
00489     --mCount;
00490 
00491     while (i < mCount) {
00492         mVariables[i] = mVariables[i + 1];
00493         ++i;
00494     }
00495         
00496     return NS_OK;
00497 }
00498 
00499 PRBool
00500 VariableSet::Contains(PRInt32 aVariable) const
00501 {
00502     for (PRInt32 i = mCount - 1; i >= 0; --i) {
00503         if (aVariable == mVariables[i])
00504             return PR_TRUE;
00505     }
00506 
00507     return PR_FALSE;
00508 }
00509 
00510 //----------------------------------------------------------------------=
00511 
00512 nsresult
00513 MemoryElementSet::Add(MemoryElement* aElement)
00514 {
00515     for (ConstIterator element = First(); element != Last(); ++element) {
00516         if (*element == *aElement) {
00517             // We've already got this element covered. Since Add()
00518             // assumes ownership, and we aren't going to need this,
00519             // just nuke it.
00520             delete aElement;
00521             return NS_OK;
00522         }
00523     }
00524 
00525     List* list = new List;
00526     if (! list)
00527         return NS_ERROR_OUT_OF_MEMORY;
00528 
00529     list->mElement = aElement;
00530     list->mRefCnt  = 1;
00531     list->mNext    = mElements;
00532 
00533     mElements = list;
00534 
00535     return NS_OK;
00536 }
00537 
00538 
00539 //----------------------------------------------------------------------
00540 
00541 nsresult
00542 nsAssignmentSet::Add(const nsAssignment& aAssignment)
00543 {
00544     NS_PRECONDITION(! HasAssignmentFor(aAssignment.mVariable), "variable already bound");
00545     if (HasAssignmentFor(aAssignment.mVariable))
00546         return NS_ERROR_UNEXPECTED;
00547 
00548     List* list = new List;
00549     if (! list)
00550         return NS_ERROR_OUT_OF_MEMORY;
00551 
00552     list->mAssignment = aAssignment;
00553     list->mRefCnt     = 1;
00554     list->mNext       = mAssignments;
00555 
00556     mAssignments = list;
00557 
00558     return NS_OK;
00559 }
00560 
00561 PRInt32
00562 nsAssignmentSet::Count() const
00563 {
00564     PRInt32 count = 0;
00565     for (ConstIterator assignment = First(); assignment != Last(); ++assignment)
00566         ++count;
00567 
00568     return count;
00569 }
00570 
00571 PRBool
00572 nsAssignmentSet::HasAssignment(PRInt32 aVariable, const Value& aValue) const
00573 {
00574     for (ConstIterator assignment = First(); assignment != Last(); ++assignment) {
00575         if (assignment->mVariable == aVariable && assignment->mValue == aValue)
00576             return PR_TRUE;
00577     }
00578 
00579     return PR_FALSE;
00580 }
00581 
00582 PRBool
00583 nsAssignmentSet::HasAssignmentFor(PRInt32 aVariable) const
00584 {
00585     for (ConstIterator assignment = First(); assignment != Last(); ++assignment) {
00586         if (assignment->mVariable == aVariable)
00587             return PR_TRUE;
00588     }
00589 
00590     return PR_FALSE;
00591 }
00592 
00593 PRBool
00594 nsAssignmentSet::GetAssignmentFor(PRInt32 aVariable, Value* aValue) const
00595 {
00596     for (ConstIterator assignment = First(); assignment != Last(); ++assignment) {
00597         if (assignment->mVariable == aVariable) {
00598             *aValue = assignment->mValue;
00599             return PR_TRUE;
00600         }
00601     }
00602 
00603     return PR_FALSE;
00604 }
00605 
00606 PRBool
00607 nsAssignmentSet::Equals(const nsAssignmentSet& aSet) const
00608 {
00609     if (aSet.mAssignments == mAssignments)
00610         return PR_TRUE;
00611 
00612     // If they have a different number of assignments, then they're different.
00613     if (Count() != aSet.Count())
00614         return PR_FALSE;
00615 
00616     // XXX O(n^2)! Ugh!
00617     for (ConstIterator assignment = First(); assignment != Last(); ++assignment) {
00618         Value value;
00619         if (! aSet.GetAssignmentFor(assignment->mVariable, &value))
00620             return PR_FALSE;
00621 
00622         if (assignment->mValue != value)
00623             return PR_FALSE;
00624     }
00625 
00626     return PR_TRUE;
00627 }
00628 
00629 //----------------------------------------------------------------------
00630 
00631 PLHashNumber
00632 Instantiation::Hash(const void* aKey)
00633 {
00634     const Instantiation* inst = NS_STATIC_CAST(const Instantiation*, aKey);
00635 
00636     PLHashNumber result = 0;
00637 
00638     nsAssignmentSet::ConstIterator last = inst->mAssignments.Last();
00639     for (nsAssignmentSet::ConstIterator assignment = inst->mAssignments.First(); assignment != last; ++assignment)
00640         result ^= assignment->Hash();
00641 
00642     return result;
00643 }
00644 
00645 
00646 PRIntn
00647 Instantiation::Compare(const void* aLeft, const void* aRight)
00648 {
00649     const Instantiation* left  = NS_STATIC_CAST(const Instantiation*, aLeft);
00650     const Instantiation* right = NS_STATIC_CAST(const Instantiation*, aRight);
00651 
00652     return *left == *right;
00653 }
00654 
00655 
00656 //----------------------------------------------------------------------
00657 //
00658 // InstantiationSet
00659 //
00660 
00661 InstantiationSet::InstantiationSet()
00662 {
00663     mHead.mPrev = mHead.mNext = &mHead;
00664     MOZ_COUNT_CTOR(InstantiationSet);
00665 }
00666 
00667 
00668 InstantiationSet::InstantiationSet(const InstantiationSet& aInstantiationSet)
00669 {
00670     mHead.mPrev = mHead.mNext = &mHead;
00671 
00672     // XXX replace with copy-on-write foo
00673     ConstIterator last = aInstantiationSet.Last();
00674     for (ConstIterator inst = aInstantiationSet.First(); inst != last; ++inst)
00675         Append(*inst);
00676 
00677     MOZ_COUNT_CTOR(InstantiationSet);
00678 }
00679 
00680 InstantiationSet&
00681 InstantiationSet::operator=(const InstantiationSet& aInstantiationSet)
00682 {
00683     // XXX replace with copy-on-write foo
00684     Clear();
00685 
00686     ConstIterator last = aInstantiationSet.Last();
00687     for (ConstIterator inst = aInstantiationSet.First(); inst != last; ++inst)
00688         Append(*inst);
00689 
00690     return *this;
00691 }
00692 
00693 
00694 void
00695 InstantiationSet::Clear()
00696 {
00697     Iterator inst = First();
00698     while (inst != Last())
00699         Erase(inst++);
00700 }
00701 
00702 
00703 InstantiationSet::Iterator
00704 InstantiationSet::Insert(Iterator aIterator, const Instantiation& aInstantiation)
00705 {
00706     List* newelement = new List();
00707     if (newelement) {
00708         newelement->mInstantiation = aInstantiation;
00709 
00710         aIterator.mCurrent->mPrev->mNext = newelement;
00711 
00712         newelement->mNext = aIterator.mCurrent;
00713         newelement->mPrev = aIterator.mCurrent->mPrev;
00714 
00715         aIterator.mCurrent->mPrev = newelement;
00716     }
00717     return aIterator;
00718 }
00719 
00720 InstantiationSet::Iterator
00721 InstantiationSet::Erase(Iterator aIterator)
00722 {
00723     Iterator result = aIterator;
00724     ++result;
00725     aIterator.mCurrent->mNext->mPrev = aIterator.mCurrent->mPrev;
00726     aIterator.mCurrent->mPrev->mNext = aIterator.mCurrent->mNext;
00727     delete aIterator.mCurrent;
00728     return result;
00729 }
00730 
00731 
00732 PRBool
00733 InstantiationSet::HasAssignmentFor(PRInt32 aVariable) const
00734 {
00735     return !Empty() ? First()->mAssignments.HasAssignmentFor(aVariable) : PR_FALSE;
00736 }
00737 
00738 //----------------------------------------------------------------------
00739 //
00740 // ReteNode
00741 //
00742 //   The basic node in the network.
00743 //
00744 
00745 
00746 
00747 //----------------------------------------------------------------------
00748 //
00749 // RootNode
00750 //
00751 
00752 nsresult
00753 RootNode::Propagate(const InstantiationSet& aInstantiations, void* aClosure)
00754 {
00755     PR_LOG(gXULTemplateLog, PR_LOG_DEBUG,
00756            ("RootNode[%p]: Propagate() begin", this));
00757 
00758     ReteNodeSet::Iterator last = mKids.Last();
00759     for (ReteNodeSet::Iterator kid = mKids.First(); kid != last; ++kid)
00760         kid->Propagate(aInstantiations, aClosure);
00761 
00762     PR_LOG(gXULTemplateLog, PR_LOG_DEBUG,
00763            ("RootNode[%p]: Propagate() end", this));
00764 
00765     return NS_OK;
00766 }
00767 
00768 nsresult
00769 RootNode::Constrain(InstantiationSet& aInstantiations, void* aClosure)
00770 {
00771     PR_LOG(gXULTemplateLog, PR_LOG_DEBUG,
00772            ("RootNode[%p]: Constrain()", this));
00773 
00774     return NS_OK;
00775 }
00776 
00777 
00778 nsresult
00779 RootNode::GetAncestorVariables(VariableSet& aVariables) const
00780 {
00781     return NS_OK;
00782 }
00783 
00784 
00785 PRBool
00786 RootNode::HasAncestor(const ReteNode* aNode) const
00787 {
00788     return aNode == this;
00789 }
00790 
00791 //----------------------------------------------------------------------
00792 //
00793 // JoinNode
00794 //
00795 //   A node that performs a join in the network.
00796 //
00797 
00798 JoinNode::JoinNode(InnerNode* aLeftParent,
00799                    PRInt32 aLeftVariable,
00800                    InnerNode* aRightParent,
00801                    PRInt32 aRightVariable,
00802                    Operator aOperator)
00803     : mLeftParent(aLeftParent),
00804       mLeftVariable(aLeftVariable),
00805       mRightParent(aRightParent),
00806       mRightVariable(aRightVariable),
00807       mOperator(aOperator)
00808 {
00809 }
00810 
00811 nsresult
00812 JoinNode::Propagate(const InstantiationSet& aInstantiations, void* aClosure)
00813 {
00814     // the add will have been propagated down from one of the parent
00815     // nodes: either the left or the right. Test the other node for
00816     // matches.
00817     nsresult rv;
00818 
00819     PRBool hasLeftAssignment = aInstantiations.HasAssignmentFor(mLeftVariable);
00820     PRBool hasRightAssignment = aInstantiations.HasAssignmentFor(mRightVariable);
00821 
00822     NS_ASSERTION(hasLeftAssignment ^ hasRightAssignment, "there isn't exactly one assignment specified");
00823     if (! (hasLeftAssignment ^ hasRightAssignment))
00824         return NS_ERROR_UNEXPECTED;
00825 
00826     InstantiationSet instantiations = aInstantiations;
00827     InnerNode* test = hasLeftAssignment ? mRightParent : mLeftParent;
00828 
00829     {
00830         // extend the assignments
00831         InstantiationSet::Iterator last = instantiations.Last();
00832         for (InstantiationSet::Iterator inst = instantiations.First(); inst != last; ++inst) {
00833             if (hasLeftAssignment) {
00834                 // the left is bound
00835                 Value leftValue;
00836                 inst->mAssignments.GetAssignmentFor(mLeftVariable, &leftValue);
00837                 rv = inst->AddAssignment(mRightVariable, leftValue);
00838             }
00839             else {
00840                 // the right is bound
00841                 Value rightValue;
00842                 inst->mAssignments.GetAssignmentFor(mRightVariable, &rightValue);
00843                 rv = inst->AddAssignment(mLeftVariable, rightValue);
00844             }
00845 
00846             if (NS_FAILED(rv)) return rv;
00847         }
00848     }
00849 
00850     if (! instantiations.Empty()) {
00851         // propagate consistency checking back up the tree
00852         rv = test->Constrain(instantiations, aClosure);
00853         if (NS_FAILED(rv)) return rv;
00854 
00855         ReteNodeSet::Iterator last = mKids.Last();
00856         for (ReteNodeSet::Iterator kid = mKids.First(); kid != last; ++kid)
00857             kid->Propagate(instantiations, aClosure);
00858     }
00859 
00860     return NS_OK;
00861 }
00862 
00863 
00864 nsresult
00865 JoinNode::GetNumBound(InnerNode* aAncestor, const InstantiationSet& aInstantiations, PRInt32* aBoundCount)
00866 {
00867     // Compute the number of variables for an ancestor that are bound
00868     // in the current instantiation set.
00869     nsresult rv;
00870 
00871     VariableSet vars;
00872     rv = aAncestor->GetAncestorVariables(vars);
00873     if (NS_FAILED(rv)) return rv;
00874 
00875     PRInt32 count = 0;
00876     for (PRInt32 i = vars.GetCount() - 1; i >= 0; --i) {
00877         if (aInstantiations.HasAssignmentFor(vars.GetVariableAt(i)))
00878             ++count;
00879     }
00880 
00881     *aBoundCount = count;
00882     return NS_OK;
00883 }
00884 
00885 
00886 nsresult
00887 JoinNode::Bind(InstantiationSet& aInstantiations, PRBool* aDidBind)
00888 {
00889     // Try to use the instantiation set to bind the unbound join
00890     // variable. If successful, aDidBind <= PR_TRUE.
00891     nsresult rv;
00892 
00893     PRBool hasLeftAssignment = aInstantiations.HasAssignmentFor(mLeftVariable);
00894     PRBool hasRightAssignment = aInstantiations.HasAssignmentFor(mRightVariable);
00895 
00896     NS_ASSERTION(! (hasLeftAssignment && hasRightAssignment), "there is more than one assignment specified");
00897     if (hasLeftAssignment && hasRightAssignment)
00898         return NS_ERROR_UNEXPECTED;
00899 
00900     if (hasLeftAssignment || hasRightAssignment) {
00901         InstantiationSet::Iterator last = aInstantiations.Last();
00902         for (InstantiationSet::Iterator inst = aInstantiations.First(); inst != last; ++inst) {
00903             if (hasLeftAssignment) {
00904                 // the left is bound
00905                 Value leftValue;
00906                 inst->mAssignments.GetAssignmentFor(mLeftVariable, &leftValue);
00907                 rv = inst->AddAssignment(mRightVariable, leftValue);
00908             }
00909             else {
00910                 // the right is bound
00911                 Value rightValue;
00912                 inst->mAssignments.GetAssignmentFor(mRightVariable, &rightValue);
00913                 rv = inst->AddAssignment(mLeftVariable, rightValue);
00914             }
00915 
00916             if (NS_FAILED(rv)) return rv;
00917         }
00918 
00919         *aDidBind = PR_TRUE;
00920     }
00921     else {
00922         *aDidBind = PR_FALSE;
00923     }
00924 
00925     return NS_OK;
00926 }
00927 
00928 nsresult
00929 JoinNode::Constrain(InstantiationSet& aInstantiations, void* aClosure)
00930 {
00931     if (aInstantiations.Empty())
00932         return NS_OK;
00933 
00934     nsresult rv;
00935     PRBool didBind;
00936 
00937     rv = Bind(aInstantiations, &didBind);
00938     if (NS_FAILED(rv)) return rv;
00939 
00940     PRInt32 numLeftBound;
00941     rv = GetNumBound(mLeftParent, aInstantiations, &numLeftBound);
00942     if (NS_FAILED(rv)) return rv;
00943 
00944     PRInt32 numRightBound;
00945     rv = GetNumBound(mRightParent, aInstantiations, &numRightBound);
00946     if (NS_FAILED(rv)) return rv;
00947 
00948     InnerNode *first, *last;
00949     if (numLeftBound > numRightBound) {
00950         first = mLeftParent;
00951         last = mRightParent;
00952     }
00953     else {
00954         first = mRightParent;
00955         last = mLeftParent;
00956     }
00957 
00958     rv = first->Constrain(aInstantiations, aClosure);
00959     if (NS_FAILED(rv)) return rv;
00960 
00961     if (! didBind) {
00962         rv = Bind(aInstantiations, &didBind);
00963         if (NS_FAILED(rv)) return rv;
00964 
00965         NS_ASSERTION(didBind, "uh oh, still no assignment");
00966     }
00967 
00968     rv = last->Constrain(aInstantiations, aClosure);
00969     if (NS_FAILED(rv)) return rv;
00970 
00971     if (! didBind) {
00972         // sort throught the full cross product
00973         NS_NOTYETIMPLEMENTED("write me");
00974     }
00975 
00976     return NS_OK;
00977 }
00978 
00979 
00980 nsresult
00981 JoinNode::GetAncestorVariables(VariableSet& aVariables) const
00982 {
00983     nsresult rv;
00984 
00985     rv = mLeftParent->GetAncestorVariables(aVariables);
00986     if (NS_FAILED(rv)) return rv;
00987 
00988     rv = mRightParent->GetAncestorVariables(aVariables);
00989     if (NS_FAILED(rv)) return rv;
00990 
00991     
00992     if (mLeftVariable) {
00993         rv = aVariables.Add(mLeftVariable);
00994         if (NS_FAILED(rv)) return rv;
00995     }
00996 
00997     if (mRightVariable) {
00998         rv = aVariables.Add(mRightVariable);
00999         if (NS_FAILED(rv)) return rv;
01000     }
01001 
01002     return NS_OK;
01003 }
01004 
01005 
01006 PRBool
01007 JoinNode::HasAncestor(const ReteNode* aNode) const
01008 {
01009     if (aNode == this) {
01010         return PR_TRUE;
01011     }
01012     else if (mLeftParent->HasAncestor(aNode) || mRightParent->HasAncestor(aNode)) {
01013         return PR_TRUE;
01014     }
01015     else {
01016         return PR_FALSE;
01017     }
01018 }
01019 
01020 //----------------------------------------------------------------------
01021 //
01022 // TestNode
01023 //
01024 //   to do:
01025 //     - FilterInstantiations() is poorly named
01026 //
01027 
01028 
01029 TestNode::TestNode(InnerNode* aParent)
01030     : mParent(aParent)
01031 {
01032 }
01033 
01034 
01035 nsresult
01036 TestNode::Propagate(const InstantiationSet& aInstantiations, void* aClosure)
01037 {
01038     nsresult rv;
01039 
01040     PR_LOG(gXULTemplateLog, PR_LOG_DEBUG,
01041            ("TestNode[%p]: Propagate() begin", this));
01042 
01043     InstantiationSet instantiations = aInstantiations;
01044     rv = FilterInstantiations(instantiations, aClosure);
01045     if (NS_FAILED(rv)) return rv;
01046 
01047     if (! instantiations.Empty()) {
01048         ReteNodeSet::Iterator last = mKids.Last();
01049         for (ReteNodeSet::Iterator kid = mKids.First(); kid != last; ++kid) {
01050             PR_LOG(gXULTemplateLog, PR_LOG_DEBUG,
01051                    ("TestNode[%p]: Propagate() passing to child %p", this, kid.operator->()));
01052 
01053             kid->Propagate(instantiations, aClosure);
01054         }
01055     }
01056 
01057     PR_LOG(gXULTemplateLog, PR_LOG_DEBUG,
01058            ("TestNode[%p]: Propagate() end", this));
01059 
01060     return NS_OK;
01061 }
01062 
01063 
01064 nsresult
01065 TestNode::Constrain(InstantiationSet& aInstantiations, void* aClosure)
01066 {
01067     nsresult rv;
01068 
01069     PR_LOG(gXULTemplateLog, PR_LOG_DEBUG,
01070            ("TestNode[%p]: Constrain() begin", this));
01071 
01072     rv = FilterInstantiations(aInstantiations, aClosure);
01073     if (NS_FAILED(rv)) return rv;
01074 
01075     if (! aInstantiations.Empty()) {
01076         // if we still have instantiations, then ride 'em on up to the
01077         // parent to narrow them.
01078 
01079         PR_LOG(gXULTemplateLog, PR_LOG_DEBUG,
01080                ("TestNode[%p]: Constrain() passing to parent %p", this, mParent));
01081 
01082         rv = mParent->Constrain(aInstantiations, aClosure);
01083     }
01084     else {
01085         PR_LOG(gXULTemplateLog, PR_LOG_DEBUG,
01086                ("TestNode[%p]: Constrain() failed", this));
01087 
01088         rv = NS_OK;
01089     }
01090 
01091     PR_LOG(gXULTemplateLog, PR_LOG_DEBUG,
01092            ("TestNode[%p]: Constrain() end", this));
01093 
01094     return rv;
01095 }
01096 
01097 
01098 nsresult
01099 TestNode::GetAncestorVariables(VariableSet& aVariables) const
01100 {
01101     return mParent->GetAncestorVariables(aVariables);
01102 }
01103 
01104 
01105 PRBool
01106 TestNode::HasAncestor(const ReteNode* aNode) const
01107 {
01108     return aNode == this ? PR_TRUE : mParent->HasAncestor(aNode);
01109 }
01110 
01111 
01112 //----------------------------------------------------------------------0
01113 
01114 ReteNodeSet::ReteNodeSet()
01115     : mNodes(nsnull), mCount(0), mCapacity(0)
01116 {
01117 }
01118 
01119 ReteNodeSet::~ReteNodeSet()
01120 {
01121     Clear();
01122 }
01123 
01124 nsresult
01125 ReteNodeSet::Add(ReteNode* aNode)
01126 {
01127     NS_PRECONDITION(aNode != nsnull, "null ptr");
01128     if (! aNode)
01129         return NS_ERROR_NULL_POINTER;
01130 
01131     if (mCount >= mCapacity) {
01132         PRInt32 capacity = mCapacity + 4;
01133         ReteNode** nodes = new ReteNode*[capacity];
01134         if (! nodes)
01135             return NS_ERROR_OUT_OF_MEMORY;
01136 
01137         for (PRInt32 i = mCount - 1; i >= 0; --i)
01138             nodes[i] = mNodes[i];
01139 
01140         delete[] mNodes;
01141 
01142         mNodes = nodes;
01143         mCapacity = capacity;
01144     }
01145 
01146     mNodes[mCount++] = aNode;
01147     return NS_OK;
01148 }
01149 
01150 nsresult
01151 ReteNodeSet::Clear()
01152 {
01153     delete[] mNodes;
01154     mNodes = nsnull;
01155     mCount = mCapacity = 0;
01156     return NS_OK;
01157 }