Line data Source code
1 : /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2 : /* This Source Code Form is subject to the terms of the Mozilla Public
3 : * License, v. 2.0. If a copy of the MPL was not distributed with this
4 : * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
5 :
6 : /*
7 :
8 : Implementations for the rule network classes.
9 :
10 : To Do.
11 :
12 : - Constrain() & Propagate() still feel like they are poorly named.
13 : - As do Instantiation and InstantiationSet.
14 : - Make InstantiationSet share and do copy-on-write.
15 : - Make things iterative, instead of recursive.
16 :
17 : */
18 :
19 : #include "nscore.h"
20 : #include "nsCOMPtr.h"
21 : #include "plhash.h"
22 :
23 : #include "mozilla/Logging.h"
24 :
25 : #include "nsString.h"
26 : #include "nsUnicharUtils.h"
27 : #include "nsXULContentUtils.h"
28 :
29 : #include "nsRuleNetwork.h"
30 : #include "nsXULTemplateResultSetRDF.h"
31 : #include "nsRDFConMemberTestNode.h"
32 : #include "nsRDFPropertyTestNode.h"
33 :
34 : using namespace mozilla;
35 : extern LazyLogModule gXULTemplateLog;
36 :
37 : //----------------------------------------------------------------------
38 : //
39 : // nsRuleNetwork
40 : //
41 :
42 : nsresult
43 0 : MemoryElementSet::Add(MemoryElement* aElement)
44 : {
45 0 : for (ConstIterator element = First(); element != Last(); ++element) {
46 0 : if (*element == *aElement) {
47 : // We've already got this element covered. Since Add()
48 : // assumes ownership, and we aren't going to need this,
49 : // just nuke it.
50 0 : delete aElement;
51 0 : return NS_OK;
52 : }
53 : }
54 :
55 0 : List* list = new List;
56 0 : list->mElement = aElement;
57 0 : list->mRefCnt = 1;
58 0 : list->mNext = mElements;
59 :
60 0 : mElements = list;
61 :
62 0 : return NS_OK;
63 : }
64 :
65 :
66 : //----------------------------------------------------------------------
67 :
68 : nsresult
69 0 : nsAssignmentSet::Add(const nsAssignment& aAssignment)
70 : {
71 0 : NS_PRECONDITION(! HasAssignmentFor(aAssignment.mVariable), "variable already bound");
72 :
73 : // XXXndeakin should this just silently fail?
74 0 : if (HasAssignmentFor(aAssignment.mVariable))
75 0 : return NS_ERROR_UNEXPECTED;
76 :
77 0 : List* list = new List(aAssignment);
78 0 : list->mRefCnt = 1;
79 0 : list->mNext = mAssignments;
80 :
81 0 : mAssignments = list;
82 :
83 0 : return NS_OK;
84 : }
85 :
86 : int32_t
87 0 : nsAssignmentSet::Count() const
88 : {
89 0 : int32_t count = 0;
90 0 : for (ConstIterator assignment = First(); assignment != Last(); ++assignment)
91 0 : ++count;
92 :
93 0 : return count;
94 : }
95 :
96 : bool
97 0 : nsAssignmentSet::HasAssignment(nsIAtom* aVariable, nsIRDFNode* aValue) const
98 : {
99 0 : for (ConstIterator assignment = First(); assignment != Last(); ++assignment) {
100 0 : if (assignment->mVariable == aVariable && assignment->mValue == aValue)
101 0 : return true;
102 : }
103 :
104 0 : return false;
105 : }
106 :
107 : bool
108 0 : nsAssignmentSet::HasAssignmentFor(nsIAtom* aVariable) const
109 : {
110 0 : for (ConstIterator assignment = First(); assignment != Last(); ++assignment) {
111 0 : if (assignment->mVariable == aVariable)
112 0 : return true;
113 : }
114 :
115 0 : return false;
116 : }
117 :
118 : bool
119 0 : nsAssignmentSet::GetAssignmentFor(nsIAtom* aVariable, nsIRDFNode** aValue) const
120 : {
121 0 : for (ConstIterator assignment = First(); assignment != Last(); ++assignment) {
122 0 : if (assignment->mVariable == aVariable) {
123 0 : *aValue = assignment->mValue;
124 0 : NS_IF_ADDREF(*aValue);
125 0 : return true;
126 : }
127 : }
128 :
129 0 : *aValue = nullptr;
130 0 : return false;
131 : }
132 :
133 : bool
134 0 : nsAssignmentSet::Equals(const nsAssignmentSet& aSet) const
135 : {
136 0 : if (aSet.mAssignments == mAssignments)
137 0 : return true;
138 :
139 : // If they have a different number of assignments, then they're different.
140 0 : if (Count() != aSet.Count())
141 0 : return false;
142 :
143 : // XXX O(n^2)! Ugh!
144 0 : nsCOMPtr<nsIRDFNode> value;
145 0 : for (ConstIterator assignment = First(); assignment != Last(); ++assignment) {
146 0 : if (! aSet.GetAssignmentFor(assignment->mVariable, getter_AddRefs(value)))
147 0 : return false;
148 :
149 0 : if (assignment->mValue != value)
150 0 : return false;
151 : }
152 :
153 0 : return true;
154 : }
155 :
156 : //----------------------------------------------------------------------
157 :
158 : PLHashNumber
159 0 : Instantiation::Hash(const void* aKey)
160 : {
161 0 : const Instantiation* inst = static_cast<const Instantiation*>(aKey);
162 :
163 0 : PLHashNumber result = 0;
164 :
165 0 : nsAssignmentSet::ConstIterator last = inst->mAssignments.Last();
166 0 : for (nsAssignmentSet::ConstIterator assignment = inst->mAssignments.First();
167 : assignment != last; ++assignment)
168 0 : result ^= assignment->Hash();
169 :
170 0 : return result;
171 : }
172 :
173 :
174 : int
175 0 : Instantiation::Compare(const void* aLeft, const void* aRight)
176 : {
177 0 : const Instantiation* left = static_cast<const Instantiation*>(aLeft);
178 0 : const Instantiation* right = static_cast<const Instantiation*>(aRight);
179 :
180 0 : return *left == *right;
181 : }
182 :
183 :
184 : //----------------------------------------------------------------------
185 : //
186 : // InstantiationSet
187 : //
188 :
189 0 : InstantiationSet::InstantiationSet()
190 : {
191 0 : mHead.mPrev = mHead.mNext = &mHead;
192 0 : MOZ_COUNT_CTOR(InstantiationSet);
193 0 : }
194 :
195 :
196 0 : InstantiationSet::InstantiationSet(const InstantiationSet& aInstantiationSet)
197 : {
198 0 : mHead.mPrev = mHead.mNext = &mHead;
199 :
200 : // XXX replace with copy-on-write foo
201 0 : ConstIterator last = aInstantiationSet.Last();
202 0 : for (ConstIterator inst = aInstantiationSet.First(); inst != last; ++inst)
203 0 : Append(*inst);
204 :
205 0 : MOZ_COUNT_CTOR(InstantiationSet);
206 0 : }
207 :
208 : InstantiationSet&
209 0 : InstantiationSet::operator=(const InstantiationSet& aInstantiationSet)
210 : {
211 : // XXX replace with copy-on-write foo
212 0 : Clear();
213 :
214 0 : ConstIterator last = aInstantiationSet.Last();
215 0 : for (ConstIterator inst = aInstantiationSet.First(); inst != last; ++inst)
216 0 : Append(*inst);
217 :
218 0 : return *this;
219 : }
220 :
221 :
222 : void
223 0 : InstantiationSet::Clear()
224 : {
225 0 : Iterator inst = First();
226 0 : while (inst != Last())
227 0 : Erase(inst++);
228 0 : }
229 :
230 :
231 : InstantiationSet::Iterator
232 0 : InstantiationSet::Insert(Iterator aIterator, const Instantiation& aInstantiation)
233 : {
234 0 : List* newelement = new List();
235 0 : if (newelement) {
236 0 : newelement->mInstantiation = aInstantiation;
237 :
238 0 : aIterator.mCurrent->mPrev->mNext = newelement;
239 :
240 0 : newelement->mNext = aIterator.mCurrent;
241 0 : newelement->mPrev = aIterator.mCurrent->mPrev;
242 :
243 0 : aIterator.mCurrent->mPrev = newelement;
244 : }
245 0 : return aIterator;
246 : }
247 :
248 : InstantiationSet::Iterator
249 0 : InstantiationSet::Erase(Iterator aIterator)
250 : {
251 0 : Iterator result = aIterator;
252 0 : ++result;
253 0 : aIterator.mCurrent->mNext->mPrev = aIterator.mCurrent->mPrev;
254 0 : aIterator.mCurrent->mPrev->mNext = aIterator.mCurrent->mNext;
255 0 : delete aIterator.mCurrent;
256 0 : return result;
257 : }
258 :
259 :
260 : bool
261 0 : InstantiationSet::HasAssignmentFor(nsIAtom* aVariable) const
262 : {
263 0 : return !Empty() ? First()->mAssignments.HasAssignmentFor(aVariable) : false;
264 : }
265 :
266 : //----------------------------------------------------------------------
267 : //
268 : // ReteNode
269 : //
270 : // The basic node in the network.
271 : //
272 :
273 : //----------------------------------------------------------------------
274 : //
275 : // TestNode
276 : //
277 : // to do:
278 : // - FilterInstantiations() is poorly named
279 : //
280 :
281 :
282 0 : TestNode::TestNode(TestNode* aParent)
283 0 : : mParent(aParent)
284 : {
285 0 : }
286 :
287 : nsresult
288 0 : TestNode::Propagate(InstantiationSet& aInstantiations,
289 : bool aIsUpdate, bool& aTakenInstantiations)
290 : {
291 0 : MOZ_LOG(gXULTemplateLog, LogLevel::Debug,
292 : ("TestNode[%p]: Propagate() begin", this));
293 :
294 0 : aTakenInstantiations = false;
295 :
296 0 : nsresult rv = FilterInstantiations(aInstantiations, nullptr);
297 0 : if (NS_FAILED(rv))
298 0 : return rv;
299 :
300 : // if there is more than one child, each will need to be supplied with the
301 : // original set of instantiations from this node, so create a copy in this
302 : // case. If there is only one child, optimize and just pass the
303 : // instantiations along to the child without copying
304 0 : bool shouldCopy = (mKids.Count() > 1);
305 :
306 : // See the header file for details about how instantiation ownership works.
307 0 : if (! aInstantiations.Empty()) {
308 0 : ReteNodeSet::Iterator last = mKids.Last();
309 0 : for (ReteNodeSet::Iterator kid = mKids.First(); kid != last; ++kid) {
310 0 : MOZ_LOG(gXULTemplateLog, LogLevel::Debug,
311 : ("TestNode[%p]: Propagate() passing to child %p", this, kid.operator->()));
312 :
313 : // create a copy of the instantiations
314 0 : if (shouldCopy) {
315 0 : bool owned = false;
316 : InstantiationSet* instantiations =
317 0 : new InstantiationSet(aInstantiations);
318 0 : rv = kid->Propagate(*instantiations, aIsUpdate, owned);
319 0 : if (!owned)
320 0 : delete instantiations;
321 0 : if (NS_FAILED(rv))
322 0 : return rv;
323 : }
324 : else {
325 0 : rv = kid->Propagate(aInstantiations, aIsUpdate, aTakenInstantiations);
326 0 : if (NS_FAILED(rv))
327 0 : return rv;
328 : }
329 : }
330 : }
331 :
332 0 : MOZ_LOG(gXULTemplateLog, LogLevel::Debug,
333 : ("TestNode[%p]: Propagate() end", this));
334 :
335 0 : return NS_OK;
336 : }
337 :
338 :
339 : nsresult
340 0 : TestNode::Constrain(InstantiationSet& aInstantiations)
341 : {
342 : nsresult rv;
343 :
344 0 : MOZ_LOG(gXULTemplateLog, LogLevel::Debug,
345 : ("TestNode[%p]: Constrain() begin", this));
346 :
347 : // if the cantHandleYet flag is set by FilterInstantiations,
348 : // there isn't enough information yet available to fill in.
349 : // For this, continue the constrain all the way to the top
350 : // and then call FilterInstantiations again afterwards. This
351 : // should fill in any missing information.
352 0 : bool cantHandleYet = false;
353 0 : rv = FilterInstantiations(aInstantiations, &cantHandleYet);
354 0 : if (NS_FAILED(rv)) return rv;
355 :
356 0 : if (mParent && (!aInstantiations.Empty() || cantHandleYet)) {
357 : // if we still have instantiations, or if the instantiations
358 : // could not be filled in yet, then ride 'em on up to the
359 : // parent to narrow them.
360 :
361 0 : MOZ_LOG(gXULTemplateLog, LogLevel::Debug,
362 : ("TestNode[%p]: Constrain() passing to parent %p", this, mParent));
363 :
364 0 : rv = mParent->Constrain(aInstantiations);
365 :
366 0 : if (NS_SUCCEEDED(rv) && cantHandleYet)
367 0 : rv = FilterInstantiations(aInstantiations, nullptr);
368 : }
369 : else {
370 0 : MOZ_LOG(gXULTemplateLog, LogLevel::Debug,
371 : ("TestNode[%p]: Constrain() failed", this));
372 :
373 0 : rv = NS_OK;
374 : }
375 :
376 0 : MOZ_LOG(gXULTemplateLog, LogLevel::Debug,
377 : ("TestNode[%p]: Constrain() end", this));
378 :
379 0 : return rv;
380 : }
381 :
382 :
383 : //----------------------------------------------------------------------
384 :
385 0 : ReteNodeSet::ReteNodeSet()
386 0 : : mNodes(nullptr), mCount(0), mCapacity(0)
387 : {
388 0 : }
389 :
390 0 : ReteNodeSet::~ReteNodeSet()
391 : {
392 0 : Clear();
393 0 : }
394 :
395 : nsresult
396 0 : ReteNodeSet::Add(ReteNode* aNode)
397 : {
398 0 : NS_PRECONDITION(aNode != nullptr, "null ptr");
399 0 : if (! aNode)
400 0 : return NS_ERROR_NULL_POINTER;
401 :
402 0 : if (mCount >= mCapacity) {
403 0 : int32_t capacity = mCapacity + 4;
404 0 : ReteNode** nodes = new ReteNode*[capacity];
405 0 : if (! nodes)
406 0 : return NS_ERROR_OUT_OF_MEMORY;
407 :
408 0 : for (int32_t i = mCount - 1; i >= 0; --i)
409 0 : nodes[i] = mNodes[i];
410 :
411 0 : delete[] mNodes;
412 :
413 0 : mNodes = nodes;
414 0 : mCapacity = capacity;
415 : }
416 :
417 0 : mNodes[mCount++] = aNode;
418 0 : return NS_OK;
419 : }
420 :
421 : nsresult
422 0 : ReteNodeSet::Clear()
423 : {
424 0 : delete[] mNodes;
425 0 : mNodes = nullptr;
426 0 : mCount = mCapacity = 0;
427 0 : return NS_OK;
428 : }
|
