1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/content/xul/templates/src/nsRuleNetwork.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,439 @@
1.4 +/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
1.5 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.6 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.7 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.8 +
1.9 +/*
1.10 +
1.11 + Implementations for the rule network classes.
1.12 +
1.13 + To Do.
1.14 +
1.15 + - Constrain() & Propagate() still feel like they are poorly named.
1.16 + - As do Instantiation and InstantiationSet.
1.17 + - Make InstantiationSet share and do copy-on-write.
1.18 + - Make things iterative, instead of recursive.
1.19 +
1.20 + */
1.21 +
1.22 +#include "nscore.h"
1.23 +#include "nsCOMPtr.h"
1.24 +#include "plhash.h"
1.25 +
1.26 +#include "prlog.h"
1.27 +#ifdef PR_LOGGING
1.28 +extern PRLogModuleInfo* gXULTemplateLog;
1.29 +
1.30 +#include "nsString.h"
1.31 +#include "nsUnicharUtils.h"
1.32 +#include "nsXULContentUtils.h"
1.33 +
1.34 +#endif
1.35 +
1.36 +#include "nsRuleNetwork.h"
1.37 +#include "nsXULTemplateResultSetRDF.h"
1.38 +#include "nsRDFConMemberTestNode.h"
1.39 +#include "nsRDFPropertyTestNode.h"
1.40 +
1.41 +using namespace mozilla;
1.42 +
1.43 +//----------------------------------------------------------------------
1.44 +//
1.45 +// nsRuleNetwork
1.46 +//
1.47 +
1.48 +nsresult
1.49 +MemoryElementSet::Add(MemoryElement* aElement)
1.50 +{
1.51 + for (ConstIterator element = First(); element != Last(); ++element) {
1.52 + if (*element == *aElement) {
1.53 + // We've already got this element covered. Since Add()
1.54 + // assumes ownership, and we aren't going to need this,
1.55 + // just nuke it.
1.56 + delete aElement;
1.57 + return NS_OK;
1.58 + }
1.59 + }
1.60 +
1.61 + List* list = new List;
1.62 + if (! list)
1.63 + return NS_ERROR_OUT_OF_MEMORY;
1.64 +
1.65 + list->mElement = aElement;
1.66 + list->mRefCnt = 1;
1.67 + list->mNext = mElements;
1.68 +
1.69 + mElements = list;
1.70 +
1.71 + return NS_OK;
1.72 +}
1.73 +
1.74 +
1.75 +//----------------------------------------------------------------------
1.76 +
1.77 +nsresult
1.78 +nsAssignmentSet::Add(const nsAssignment& aAssignment)
1.79 +{
1.80 + NS_PRECONDITION(! HasAssignmentFor(aAssignment.mVariable), "variable already bound");
1.81 +
1.82 + // XXXndeakin should this just silently fail?
1.83 + if (HasAssignmentFor(aAssignment.mVariable))
1.84 + return NS_ERROR_UNEXPECTED;
1.85 +
1.86 + List* list = new List(aAssignment);
1.87 + if (! list)
1.88 + return NS_ERROR_OUT_OF_MEMORY;
1.89 +
1.90 + list->mRefCnt = 1;
1.91 + list->mNext = mAssignments;
1.92 +
1.93 + mAssignments = list;
1.94 +
1.95 + return NS_OK;
1.96 +}
1.97 +
1.98 +int32_t
1.99 +nsAssignmentSet::Count() const
1.100 +{
1.101 + int32_t count = 0;
1.102 + for (ConstIterator assignment = First(); assignment != Last(); ++assignment)
1.103 + ++count;
1.104 +
1.105 + return count;
1.106 +}
1.107 +
1.108 +bool
1.109 +nsAssignmentSet::HasAssignment(nsIAtom* aVariable, nsIRDFNode* aValue) const
1.110 +{
1.111 + for (ConstIterator assignment = First(); assignment != Last(); ++assignment) {
1.112 + if (assignment->mVariable == aVariable && assignment->mValue == aValue)
1.113 + return true;
1.114 + }
1.115 +
1.116 + return false;
1.117 +}
1.118 +
1.119 +bool
1.120 +nsAssignmentSet::HasAssignmentFor(nsIAtom* aVariable) const
1.121 +{
1.122 + for (ConstIterator assignment = First(); assignment != Last(); ++assignment) {
1.123 + if (assignment->mVariable == aVariable)
1.124 + return true;
1.125 + }
1.126 +
1.127 + return false;
1.128 +}
1.129 +
1.130 +bool
1.131 +nsAssignmentSet::GetAssignmentFor(nsIAtom* aVariable, nsIRDFNode** aValue) const
1.132 +{
1.133 + for (ConstIterator assignment = First(); assignment != Last(); ++assignment) {
1.134 + if (assignment->mVariable == aVariable) {
1.135 + *aValue = assignment->mValue;
1.136 + NS_IF_ADDREF(*aValue);
1.137 + return true;
1.138 + }
1.139 + }
1.140 +
1.141 + *aValue = nullptr;
1.142 + return false;
1.143 +}
1.144 +
1.145 +bool
1.146 +nsAssignmentSet::Equals(const nsAssignmentSet& aSet) const
1.147 +{
1.148 + if (aSet.mAssignments == mAssignments)
1.149 + return true;
1.150 +
1.151 + // If they have a different number of assignments, then they're different.
1.152 + if (Count() != aSet.Count())
1.153 + return false;
1.154 +
1.155 + // XXX O(n^2)! Ugh!
1.156 + nsCOMPtr<nsIRDFNode> value;
1.157 + for (ConstIterator assignment = First(); assignment != Last(); ++assignment) {
1.158 + if (! aSet.GetAssignmentFor(assignment->mVariable, getter_AddRefs(value)))
1.159 + return false;
1.160 +
1.161 + if (assignment->mValue != value)
1.162 + return false;
1.163 + }
1.164 +
1.165 + return true;
1.166 +}
1.167 +
1.168 +//----------------------------------------------------------------------
1.169 +
1.170 +PLHashNumber
1.171 +Instantiation::Hash(const void* aKey)
1.172 +{
1.173 + const Instantiation* inst = static_cast<const Instantiation*>(aKey);
1.174 +
1.175 + PLHashNumber result = 0;
1.176 +
1.177 + nsAssignmentSet::ConstIterator last = inst->mAssignments.Last();
1.178 + for (nsAssignmentSet::ConstIterator assignment = inst->mAssignments.First();
1.179 + assignment != last; ++assignment)
1.180 + result ^= assignment->Hash();
1.181 +
1.182 + return result;
1.183 +}
1.184 +
1.185 +
1.186 +int
1.187 +Instantiation::Compare(const void* aLeft, const void* aRight)
1.188 +{
1.189 + const Instantiation* left = static_cast<const Instantiation*>(aLeft);
1.190 + const Instantiation* right = static_cast<const Instantiation*>(aRight);
1.191 +
1.192 + return *left == *right;
1.193 +}
1.194 +
1.195 +
1.196 +//----------------------------------------------------------------------
1.197 +//
1.198 +// InstantiationSet
1.199 +//
1.200 +
1.201 +InstantiationSet::InstantiationSet()
1.202 +{
1.203 + mHead.mPrev = mHead.mNext = &mHead;
1.204 + MOZ_COUNT_CTOR(InstantiationSet);
1.205 +}
1.206 +
1.207 +
1.208 +InstantiationSet::InstantiationSet(const InstantiationSet& aInstantiationSet)
1.209 +{
1.210 + mHead.mPrev = mHead.mNext = &mHead;
1.211 +
1.212 + // XXX replace with copy-on-write foo
1.213 + ConstIterator last = aInstantiationSet.Last();
1.214 + for (ConstIterator inst = aInstantiationSet.First(); inst != last; ++inst)
1.215 + Append(*inst);
1.216 +
1.217 + MOZ_COUNT_CTOR(InstantiationSet);
1.218 +}
1.219 +
1.220 +InstantiationSet&
1.221 +InstantiationSet::operator=(const InstantiationSet& aInstantiationSet)
1.222 +{
1.223 + // XXX replace with copy-on-write foo
1.224 + Clear();
1.225 +
1.226 + ConstIterator last = aInstantiationSet.Last();
1.227 + for (ConstIterator inst = aInstantiationSet.First(); inst != last; ++inst)
1.228 + Append(*inst);
1.229 +
1.230 + return *this;
1.231 +}
1.232 +
1.233 +
1.234 +void
1.235 +InstantiationSet::Clear()
1.236 +{
1.237 + Iterator inst = First();
1.238 + while (inst != Last())
1.239 + Erase(inst++);
1.240 +}
1.241 +
1.242 +
1.243 +InstantiationSet::Iterator
1.244 +InstantiationSet::Insert(Iterator aIterator, const Instantiation& aInstantiation)
1.245 +{
1.246 + List* newelement = new List();
1.247 + if (newelement) {
1.248 + newelement->mInstantiation = aInstantiation;
1.249 +
1.250 + aIterator.mCurrent->mPrev->mNext = newelement;
1.251 +
1.252 + newelement->mNext = aIterator.mCurrent;
1.253 + newelement->mPrev = aIterator.mCurrent->mPrev;
1.254 +
1.255 + aIterator.mCurrent->mPrev = newelement;
1.256 + }
1.257 + return aIterator;
1.258 +}
1.259 +
1.260 +InstantiationSet::Iterator
1.261 +InstantiationSet::Erase(Iterator aIterator)
1.262 +{
1.263 + Iterator result = aIterator;
1.264 + ++result;
1.265 + aIterator.mCurrent->mNext->mPrev = aIterator.mCurrent->mPrev;
1.266 + aIterator.mCurrent->mPrev->mNext = aIterator.mCurrent->mNext;
1.267 + delete aIterator.mCurrent;
1.268 + return result;
1.269 +}
1.270 +
1.271 +
1.272 +bool
1.273 +InstantiationSet::HasAssignmentFor(nsIAtom* aVariable) const
1.274 +{
1.275 + return !Empty() ? First()->mAssignments.HasAssignmentFor(aVariable) : false;
1.276 +}
1.277 +
1.278 +//----------------------------------------------------------------------
1.279 +//
1.280 +// ReteNode
1.281 +//
1.282 +// The basic node in the network.
1.283 +//
1.284 +
1.285 +//----------------------------------------------------------------------
1.286 +//
1.287 +// TestNode
1.288 +//
1.289 +// to do:
1.290 +// - FilterInstantiations() is poorly named
1.291 +//
1.292 +
1.293 +
1.294 +TestNode::TestNode(TestNode* aParent)
1.295 + : mParent(aParent)
1.296 +{
1.297 +}
1.298 +
1.299 +nsresult
1.300 +TestNode::Propagate(InstantiationSet& aInstantiations,
1.301 + bool aIsUpdate, bool& aTakenInstantiations)
1.302 +{
1.303 + PR_LOG(gXULTemplateLog, PR_LOG_DEBUG,
1.304 + ("TestNode[%p]: Propagate() begin", this));
1.305 +
1.306 + aTakenInstantiations = false;
1.307 +
1.308 + nsresult rv = FilterInstantiations(aInstantiations, nullptr);
1.309 + if (NS_FAILED(rv))
1.310 + return rv;
1.311 +
1.312 + // if there is more than one child, each will need to be supplied with the
1.313 + // original set of instantiations from this node, so create a copy in this
1.314 + // case. If there is only one child, optimize and just pass the
1.315 + // instantiations along to the child without copying
1.316 + bool shouldCopy = (mKids.Count() > 1);
1.317 +
1.318 + // See the header file for details about how instantiation ownership works.
1.319 + if (! aInstantiations.Empty()) {
1.320 + ReteNodeSet::Iterator last = mKids.Last();
1.321 + for (ReteNodeSet::Iterator kid = mKids.First(); kid != last; ++kid) {
1.322 + PR_LOG(gXULTemplateLog, PR_LOG_DEBUG,
1.323 + ("TestNode[%p]: Propagate() passing to child %p", this, kid.operator->()));
1.324 +
1.325 + // create a copy of the instantiations
1.326 + if (shouldCopy) {
1.327 + bool owned = false;
1.328 + InstantiationSet* instantiations =
1.329 + new InstantiationSet(aInstantiations);
1.330 + if (!instantiations)
1.331 + return NS_ERROR_OUT_OF_MEMORY;
1.332 + rv = kid->Propagate(*instantiations, aIsUpdate, owned);
1.333 + if (!owned)
1.334 + delete instantiations;
1.335 + if (NS_FAILED(rv))
1.336 + return rv;
1.337 + }
1.338 + else {
1.339 + rv = kid->Propagate(aInstantiations, aIsUpdate, aTakenInstantiations);
1.340 + if (NS_FAILED(rv))
1.341 + return rv;
1.342 + }
1.343 + }
1.344 + }
1.345 +
1.346 + PR_LOG(gXULTemplateLog, PR_LOG_DEBUG,
1.347 + ("TestNode[%p]: Propagate() end", this));
1.348 +
1.349 + return NS_OK;
1.350 +}
1.351 +
1.352 +
1.353 +nsresult
1.354 +TestNode::Constrain(InstantiationSet& aInstantiations)
1.355 +{
1.356 + nsresult rv;
1.357 +
1.358 + PR_LOG(gXULTemplateLog, PR_LOG_DEBUG,
1.359 + ("TestNode[%p]: Constrain() begin", this));
1.360 +
1.361 + // if the cantHandleYet flag is set by FilterInstantiations,
1.362 + // there isn't enough information yet available to fill in.
1.363 + // For this, continue the constrain all the way to the top
1.364 + // and then call FilterInstantiations again afterwards. This
1.365 + // should fill in any missing information.
1.366 + bool cantHandleYet = false;
1.367 + rv = FilterInstantiations(aInstantiations, &cantHandleYet);
1.368 + if (NS_FAILED(rv)) return rv;
1.369 +
1.370 + if (mParent && (!aInstantiations.Empty() || cantHandleYet)) {
1.371 + // if we still have instantiations, or if the instantiations
1.372 + // could not be filled in yet, then ride 'em on up to the
1.373 + // parent to narrow them.
1.374 +
1.375 + PR_LOG(gXULTemplateLog, PR_LOG_DEBUG,
1.376 + ("TestNode[%p]: Constrain() passing to parent %p", this, mParent));
1.377 +
1.378 + rv = mParent->Constrain(aInstantiations);
1.379 +
1.380 + if (NS_SUCCEEDED(rv) && cantHandleYet)
1.381 + rv = FilterInstantiations(aInstantiations, nullptr);
1.382 + }
1.383 + else {
1.384 + PR_LOG(gXULTemplateLog, PR_LOG_DEBUG,
1.385 + ("TestNode[%p]: Constrain() failed", this));
1.386 +
1.387 + rv = NS_OK;
1.388 + }
1.389 +
1.390 + PR_LOG(gXULTemplateLog, PR_LOG_DEBUG,
1.391 + ("TestNode[%p]: Constrain() end", this));
1.392 +
1.393 + return rv;
1.394 +}
1.395 +
1.396 +
1.397 +//----------------------------------------------------------------------
1.398 +
1.399 +ReteNodeSet::ReteNodeSet()
1.400 + : mNodes(nullptr), mCount(0), mCapacity(0)
1.401 +{
1.402 +}
1.403 +
1.404 +ReteNodeSet::~ReteNodeSet()
1.405 +{
1.406 + Clear();
1.407 +}
1.408 +
1.409 +nsresult
1.410 +ReteNodeSet::Add(ReteNode* aNode)
1.411 +{
1.412 + NS_PRECONDITION(aNode != nullptr, "null ptr");
1.413 + if (! aNode)
1.414 + return NS_ERROR_NULL_POINTER;
1.415 +
1.416 + if (mCount >= mCapacity) {
1.417 + int32_t capacity = mCapacity + 4;
1.418 + ReteNode** nodes = new ReteNode*[capacity];
1.419 + if (! nodes)
1.420 + return NS_ERROR_OUT_OF_MEMORY;
1.421 +
1.422 + for (int32_t i = mCount - 1; i >= 0; --i)
1.423 + nodes[i] = mNodes[i];
1.424 +
1.425 + delete[] mNodes;
1.426 +
1.427 + mNodes = nodes;
1.428 + mCapacity = capacity;
1.429 + }
1.430 +
1.431 + mNodes[mCount++] = aNode;
1.432 + return NS_OK;
1.433 +}
1.434 +
1.435 +nsresult
1.436 +ReteNodeSet::Clear()
1.437 +{
1.438 + delete[] mNodes;
1.439 + mNodes = nullptr;
1.440 + mCount = mCapacity = 0;
1.441 + return NS_OK;
1.442 +}
