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 : A rule discrimination network implementation based on ideas from
9 : RETE and TREAT.
10 :
11 : RETE is described in Charles Forgy, "Rete: A Fast Algorithm for the
12 : Many Patterns/Many Objects Match Problem", Artificial Intelligence
13 : 19(1): pp. 17-37, 1982.
14 :
15 : TREAT is described in Daniel P. Miranker, "TREAT: A Better Match
16 : Algorithm for AI Production System Matching", AAAI 1987: pp. 42-47.
17 :
18 : --
19 :
20 : TO DO:
21 :
22 : . nsAssignmentSet::List objects are allocated by the gallon. We
23 : should make it so that these are always allocated from a pool,
24 : maybe owned by the nsRuleNetwork?
25 :
26 : */
27 :
28 : #ifndef nsRuleNetwork_h__
29 : #define nsRuleNetwork_h__
30 :
31 : #include "mozilla/Attributes.h"
32 : #include "nsCOMPtr.h"
33 : #include "nsCOMArray.h"
34 : #include "nsIAtom.h"
35 : #include "nsIDOMNode.h"
36 : #include "plhash.h"
37 : #include "PLDHashTable.h"
38 : #include "nsIRDFNode.h"
39 :
40 : class nsXULTemplateResultSetRDF;
41 :
42 : //----------------------------------------------------------------------
43 :
44 : /**
45 : * A memory element that supports an instantiation. A memory element holds a
46 : * set of nodes involved in an RDF test such as <member> or <triple> test. A
47 : * memory element is created when a specific test matches. The query processor
48 : * maintains a map between the memory elements and the results they eventually
49 : * matched. When an assertion is removed from the graph, this map is consulted
50 : * to determine which results will no longer match.
51 : */
52 : class MemoryElement {
53 : protected:
54 0 : MemoryElement() { MOZ_COUNT_CTOR(MemoryElement); }
55 :
56 : public:
57 0 : virtual ~MemoryElement() { MOZ_COUNT_DTOR(MemoryElement); }
58 :
59 : virtual const char* Type() const = 0;
60 : virtual PLHashNumber Hash() const = 0;
61 : virtual bool Equals(const MemoryElement& aElement) const = 0;
62 :
63 0 : bool operator==(const MemoryElement& aMemoryElement) const {
64 0 : return Equals(aMemoryElement);
65 : }
66 :
67 : bool operator!=(const MemoryElement& aMemoryElement) const {
68 : return !Equals(aMemoryElement);
69 : }
70 : };
71 :
72 : //----------------------------------------------------------------------
73 :
74 : /**
75 : * A collection of memory elements
76 : */
77 : class MemoryElementSet {
78 : public:
79 : class ConstIterator;
80 : friend class ConstIterator;
81 :
82 : protected:
83 : class List {
84 : public:
85 0 : List() { MOZ_COUNT_CTOR(MemoryElementSet::List); }
86 :
87 : protected:
88 0 : ~List() {
89 0 : MOZ_COUNT_DTOR(MemoryElementSet::List);
90 0 : delete mElement;
91 0 : NS_IF_RELEASE(mNext); }
92 :
93 : public:
94 0 : int32_t AddRef() { return ++mRefCnt; }
95 :
96 0 : int32_t Release() {
97 0 : int32_t refcnt = --mRefCnt;
98 0 : if (refcnt == 0) delete this;
99 0 : return refcnt; }
100 :
101 : MemoryElement* mElement;
102 : int32_t mRefCnt;
103 : List* mNext;
104 : };
105 :
106 : List* mElements;
107 :
108 : public:
109 0 : MemoryElementSet() : mElements(nullptr) {
110 0 : MOZ_COUNT_CTOR(MemoryElementSet); }
111 :
112 0 : MemoryElementSet(const MemoryElementSet& aSet) : mElements(aSet.mElements) {
113 0 : MOZ_COUNT_CTOR(MemoryElementSet);
114 0 : NS_IF_ADDREF(mElements); }
115 :
116 0 : MemoryElementSet& operator=(const MemoryElementSet& aSet) {
117 0 : NS_IF_RELEASE(mElements);
118 0 : mElements = aSet.mElements;
119 0 : NS_IF_ADDREF(mElements);
120 0 : return *this; }
121 :
122 0 : ~MemoryElementSet() {
123 0 : MOZ_COUNT_DTOR(MemoryElementSet);
124 0 : NS_IF_RELEASE(mElements); }
125 :
126 : public:
127 : class ConstIterator {
128 : public:
129 0 : explicit ConstIterator(List* aElementList) : mCurrent(aElementList) {
130 0 : NS_IF_ADDREF(mCurrent); }
131 :
132 : ConstIterator(const ConstIterator& aConstIterator)
133 : : mCurrent(aConstIterator.mCurrent) {
134 : NS_IF_ADDREF(mCurrent); }
135 :
136 : ConstIterator& operator=(const ConstIterator& aConstIterator) {
137 : NS_IF_RELEASE(mCurrent);
138 : mCurrent = aConstIterator.mCurrent;
139 : NS_IF_ADDREF(mCurrent);
140 : return *this; }
141 :
142 0 : ~ConstIterator() { NS_IF_RELEASE(mCurrent); }
143 :
144 0 : ConstIterator& operator++() {
145 0 : List* next = mCurrent->mNext;
146 0 : NS_RELEASE(mCurrent);
147 0 : mCurrent = next;
148 0 : NS_IF_ADDREF(mCurrent);
149 0 : return *this; }
150 :
151 : ConstIterator operator++(int) {
152 : ConstIterator result(*this);
153 : List* next = mCurrent->mNext;
154 : NS_RELEASE(mCurrent);
155 : mCurrent = next;
156 : NS_IF_ADDREF(mCurrent);
157 : return result; }
158 :
159 0 : const MemoryElement& operator*() const {
160 0 : return *mCurrent->mElement; }
161 :
162 0 : const MemoryElement* operator->() const {
163 0 : return mCurrent->mElement; }
164 :
165 : bool operator==(const ConstIterator& aConstIterator) const {
166 : return mCurrent == aConstIterator.mCurrent; }
167 :
168 0 : bool operator!=(const ConstIterator& aConstIterator) const {
169 0 : return mCurrent != aConstIterator.mCurrent; }
170 :
171 : protected:
172 : List* mCurrent;
173 : };
174 :
175 0 : ConstIterator First() const { return ConstIterator(mElements); }
176 0 : ConstIterator Last() const { return ConstIterator(nullptr); }
177 :
178 : // N.B. that the set assumes ownership of the element
179 : nsresult Add(MemoryElement* aElement);
180 : };
181 :
182 : //----------------------------------------------------------------------
183 :
184 : /**
185 : * An assignment of a value to a variable
186 : */
187 : class nsAssignment {
188 : public:
189 : const nsCOMPtr<nsIAtom> mVariable;
190 : nsCOMPtr<nsIRDFNode> mValue;
191 :
192 0 : nsAssignment(nsIAtom* aVariable, nsIRDFNode* aValue)
193 0 : : mVariable(aVariable),
194 0 : mValue(aValue)
195 0 : { MOZ_COUNT_CTOR(nsAssignment); }
196 :
197 0 : nsAssignment(const nsAssignment& aAssignment)
198 0 : : mVariable(aAssignment.mVariable),
199 0 : mValue(aAssignment.mValue)
200 0 : { MOZ_COUNT_CTOR(nsAssignment); }
201 :
202 0 : ~nsAssignment() { MOZ_COUNT_DTOR(nsAssignment); }
203 :
204 : bool operator==(const nsAssignment& aAssignment) const {
205 : return mVariable == aAssignment.mVariable && mValue == aAssignment.mValue; }
206 :
207 : bool operator!=(const nsAssignment& aAssignment) const {
208 : return mVariable != aAssignment.mVariable || mValue != aAssignment.mValue; }
209 :
210 0 : PLHashNumber Hash() const {
211 : // XXX I have no idea if this hashing function is good or not // XXX change this
212 0 : PLHashNumber temp = PLHashNumber(NS_PTR_TO_INT32(mValue.get())) >> 2; // strip alignment bits
213 0 : return (temp & 0xffff) | NS_PTR_TO_INT32(mVariable.get()); }
214 : };
215 :
216 :
217 : //----------------------------------------------------------------------
218 :
219 : /**
220 : * A collection of value-to-variable assignments that minimizes
221 : * copying by sharing subsets when possible.
222 : */
223 : class nsAssignmentSet {
224 : public:
225 : class ConstIterator;
226 : friend class ConstIterator;
227 :
228 : protected:
229 : class List {
230 : public:
231 0 : explicit List(const nsAssignment& aAssignment) : mAssignment(aAssignment) {
232 0 : MOZ_COUNT_CTOR(nsAssignmentSet::List); }
233 :
234 : protected:
235 0 : ~List() {
236 0 : MOZ_COUNT_DTOR(nsAssignmentSet::List);
237 0 : NS_IF_RELEASE(mNext); }
238 :
239 : public:
240 :
241 0 : int32_t AddRef() { return ++mRefCnt; }
242 :
243 0 : int32_t Release() {
244 0 : int32_t refcnt = --mRefCnt;
245 0 : if (refcnt == 0) delete this;
246 0 : return refcnt; }
247 :
248 : nsAssignment mAssignment;
249 : int32_t mRefCnt;
250 : List* mNext;
251 : };
252 :
253 : List* mAssignments;
254 :
255 : public:
256 0 : nsAssignmentSet()
257 0 : : mAssignments(nullptr)
258 0 : { MOZ_COUNT_CTOR(nsAssignmentSet); }
259 :
260 0 : nsAssignmentSet(const nsAssignmentSet& aSet)
261 0 : : mAssignments(aSet.mAssignments) {
262 0 : MOZ_COUNT_CTOR(nsAssignmentSet);
263 0 : NS_IF_ADDREF(mAssignments); }
264 :
265 0 : nsAssignmentSet& operator=(const nsAssignmentSet& aSet) {
266 0 : NS_IF_RELEASE(mAssignments);
267 0 : mAssignments = aSet.mAssignments;
268 0 : NS_IF_ADDREF(mAssignments);
269 0 : return *this; }
270 :
271 0 : ~nsAssignmentSet() {
272 0 : MOZ_COUNT_DTOR(nsAssignmentSet);
273 0 : NS_IF_RELEASE(mAssignments); }
274 :
275 : public:
276 : class ConstIterator {
277 : public:
278 0 : explicit ConstIterator(List* aAssignmentList) : mCurrent(aAssignmentList) {
279 0 : NS_IF_ADDREF(mCurrent); }
280 :
281 : ConstIterator(const ConstIterator& aConstIterator)
282 : : mCurrent(aConstIterator.mCurrent) {
283 : NS_IF_ADDREF(mCurrent); }
284 :
285 : ConstIterator& operator=(const ConstIterator& aConstIterator) {
286 : NS_IF_RELEASE(mCurrent);
287 : mCurrent = aConstIterator.mCurrent;
288 : NS_IF_ADDREF(mCurrent);
289 : return *this; }
290 :
291 0 : ~ConstIterator() { NS_IF_RELEASE(mCurrent); }
292 :
293 0 : ConstIterator& operator++() {
294 0 : List* next = mCurrent->mNext;
295 0 : NS_RELEASE(mCurrent);
296 0 : mCurrent = next;
297 0 : NS_IF_ADDREF(mCurrent);
298 0 : return *this; }
299 :
300 : ConstIterator operator++(int) {
301 : ConstIterator result(*this);
302 : List* next = mCurrent->mNext;
303 : NS_RELEASE(mCurrent);
304 : mCurrent = next;
305 : NS_IF_ADDREF(mCurrent);
306 : return result; }
307 :
308 : const nsAssignment& operator*() const {
309 : return mCurrent->mAssignment; }
310 :
311 0 : const nsAssignment* operator->() const {
312 0 : return &mCurrent->mAssignment; }
313 :
314 : bool operator==(const ConstIterator& aConstIterator) const {
315 : return mCurrent == aConstIterator.mCurrent; }
316 :
317 0 : bool operator!=(const ConstIterator& aConstIterator) const {
318 0 : return mCurrent != aConstIterator.mCurrent; }
319 :
320 : protected:
321 : List* mCurrent;
322 : };
323 :
324 0 : ConstIterator First() const { return ConstIterator(mAssignments); }
325 0 : ConstIterator Last() const { return ConstIterator(nullptr); }
326 :
327 : public:
328 : /**
329 : * Add an assignment to the set
330 : * @param aElement the assigment to add
331 : * @return NS_OK if all is well, NS_ERROR_OUT_OF_MEMORY if memory
332 : * could not be allocated for the addition.
333 : */
334 : nsresult Add(const nsAssignment& aElement);
335 :
336 : /**
337 : * Determine if the assignment set contains the specified variable
338 : * to value assignment.
339 : * @param aVariable the variable for which to lookup the binding
340 : * @param aValue the value to query
341 : * @return true if aVariable is bound to aValue; false otherwise.
342 : */
343 : bool HasAssignment(nsIAtom* aVariable, nsIRDFNode* aValue) const;
344 :
345 : /**
346 : * Determine if the assignment set contains the specified assignment
347 : * @param aAssignment the assignment to search for
348 : * @return true if the set contains the assignment, false otherwise.
349 : */
350 : bool HasAssignment(const nsAssignment& aAssignment) const {
351 : return HasAssignment(aAssignment.mVariable, aAssignment.mValue); }
352 :
353 : /**
354 : * Determine whether the assignment set has an assignment for the
355 : * specified variable.
356 : * @param aVariable the variable to query
357 : * @return true if the assignment set has an assignment for the variable,
358 : * false otherwise.
359 : */
360 : bool HasAssignmentFor(nsIAtom* aVariable) const;
361 :
362 : /**
363 : * Retrieve the assignment for the specified variable
364 : * @param aVariable the variable to query
365 : * @param aValue an out parameter that will receive the value assigned
366 : * to the variable, if any.
367 : * @return true if the variable has an assignment, false
368 : * if there was no assignment for the variable.
369 : */
370 : bool GetAssignmentFor(nsIAtom* aVariable, nsIRDFNode** aValue) const;
371 :
372 : /**
373 : * Count the number of assignments in the set
374 : * @return the number of assignments in the set
375 : */
376 : int32_t Count() const;
377 :
378 : /**
379 : * Determine if the set is empty
380 : * @return true if the assignment set is empty, false otherwise.
381 : */
382 : bool IsEmpty() const { return mAssignments == nullptr; }
383 :
384 : bool Equals(const nsAssignmentSet& aSet) const;
385 0 : bool operator==(const nsAssignmentSet& aSet) const { return Equals(aSet); }
386 : bool operator!=(const nsAssignmentSet& aSet) const { return !Equals(aSet); }
387 : };
388 :
389 :
390 : //----------------------------------------------------------------------
391 :
392 : /**
393 : * A collection of variable-to-value bindings, with the memory elements
394 : * that support those bindings. Essentially, an instantiation is the
395 : * collection of variables and values assigned to those variables for a single
396 : * result. For each RDF rule in the rule network, each instantiation is
397 : * examined and either extended with additional bindings specified by the RDF
398 : * rule, or removed if the rule doesn't apply (for instance if a node has no
399 : * children). When an instantiation gets to the last node of the rule network,
400 : * which is always an nsInstantiationNode, a result is created for it.
401 : *
402 : * An instantiation object is typically created by "extending" another
403 : * instantiation object. That is, using the copy constructor, and
404 : * adding bindings and support to the instantiation.
405 : */
406 : class Instantiation
407 : {
408 : public:
409 : /**
410 : * The variable-to-value bindings
411 : */
412 : nsAssignmentSet mAssignments;
413 :
414 : /**
415 : * The memory elements that support the bindings.
416 : */
417 : MemoryElementSet mSupport;
418 :
419 0 : Instantiation() { MOZ_COUNT_CTOR(Instantiation); }
420 :
421 0 : Instantiation(const Instantiation& aInstantiation)
422 0 : : mAssignments(aInstantiation.mAssignments),
423 0 : mSupport(aInstantiation.mSupport) {
424 0 : MOZ_COUNT_CTOR(Instantiation); }
425 :
426 0 : Instantiation& operator=(const Instantiation& aInstantiation) {
427 0 : mAssignments = aInstantiation.mAssignments;
428 0 : mSupport = aInstantiation.mSupport;
429 0 : return *this; }
430 :
431 0 : ~Instantiation() { MOZ_COUNT_DTOR(Instantiation); }
432 :
433 : /**
434 : * Add the specified variable-to-value assignment to the instantiation's
435 : * set of assignments.
436 : * @param aVariable the variable to which is being assigned
437 : * @param aValue the value that is being assigned
438 : * @return NS_OK if no errors, NS_ERROR_OUT_OF_MEMORY if there
439 : * is not enough memory to perform the operation
440 : */
441 0 : nsresult AddAssignment(nsIAtom* aVariable, nsIRDFNode* aValue) {
442 0 : mAssignments.Add(nsAssignment(aVariable, aValue));
443 0 : return NS_OK; }
444 :
445 : /**
446 : * Add a memory element to the set of memory elements that are
447 : * supporting the instantiation
448 : * @param aMemoryElement the memory element to add to the
449 : * instantiation's set of support
450 : * @return NS_OK if no errors occurred, NS_ERROR_OUT_OF_MEMORY
451 : * if there is not enough memory to perform the operation.
452 : */
453 0 : nsresult AddSupportingElement(MemoryElement* aMemoryElement) {
454 0 : mSupport.Add(aMemoryElement);
455 0 : return NS_OK; }
456 :
457 0 : bool Equals(const Instantiation& aInstantiation) const {
458 0 : return mAssignments == aInstantiation.mAssignments; }
459 :
460 0 : bool operator==(const Instantiation& aInstantiation) const {
461 0 : return Equals(aInstantiation); }
462 :
463 : bool operator!=(const Instantiation& aInstantiation) const {
464 : return !Equals(aInstantiation); }
465 :
466 : static PLHashNumber Hash(const void* aKey);
467 : static int Compare(const void* aLeft, const void* aRight);
468 : };
469 :
470 :
471 : //----------------------------------------------------------------------
472 :
473 : /**
474 : * A collection of intantiations
475 : */
476 : class InstantiationSet
477 : {
478 : public:
479 : InstantiationSet();
480 : InstantiationSet(const InstantiationSet& aInstantiationSet);
481 : InstantiationSet& operator=(const InstantiationSet& aInstantiationSet);
482 :
483 0 : ~InstantiationSet() {
484 0 : MOZ_COUNT_DTOR(InstantiationSet);
485 0 : Clear(); }
486 :
487 : class ConstIterator;
488 : friend class ConstIterator;
489 :
490 : class Iterator;
491 : friend class Iterator;
492 :
493 : friend class nsXULTemplateResultSetRDF; // so it can get to the List
494 :
495 : protected:
496 : class List {
497 : public:
498 : Instantiation mInstantiation;
499 : List* mNext;
500 : List* mPrev;
501 :
502 0 : List() { MOZ_COUNT_CTOR(InstantiationSet::List); }
503 0 : ~List() { MOZ_COUNT_DTOR(InstantiationSet::List); }
504 : };
505 :
506 : List mHead;
507 :
508 : public:
509 : class ConstIterator {
510 : protected:
511 : friend class Iterator; // XXXwaterson so broken.
512 : List* mCurrent;
513 :
514 : public:
515 0 : explicit ConstIterator(List* aList) : mCurrent(aList) {}
516 :
517 0 : ConstIterator(const ConstIterator& aConstIterator)
518 0 : : mCurrent(aConstIterator.mCurrent) {}
519 :
520 : ConstIterator& operator=(const ConstIterator& aConstIterator) {
521 : mCurrent = aConstIterator.mCurrent;
522 : return *this; }
523 :
524 0 : ConstIterator& operator++() {
525 0 : mCurrent = mCurrent->mNext;
526 0 : return *this; }
527 :
528 : ConstIterator operator++(int) {
529 : ConstIterator result(*this);
530 : mCurrent = mCurrent->mNext;
531 : return result; }
532 :
533 : ConstIterator& operator--() {
534 : mCurrent = mCurrent->mPrev;
535 : return *this; }
536 :
537 : ConstIterator operator--(int) {
538 : ConstIterator result(*this);
539 : mCurrent = mCurrent->mPrev;
540 : return result; }
541 :
542 0 : const Instantiation& operator*() const {
543 0 : return mCurrent->mInstantiation; }
544 :
545 0 : const Instantiation* operator->() const {
546 0 : return &mCurrent->mInstantiation; }
547 :
548 0 : bool operator==(const ConstIterator& aConstIterator) const {
549 0 : return mCurrent == aConstIterator.mCurrent; }
550 :
551 0 : bool operator!=(const ConstIterator& aConstIterator) const {
552 0 : return mCurrent != aConstIterator.mCurrent; }
553 : };
554 :
555 0 : ConstIterator First() const { return ConstIterator(mHead.mNext); }
556 0 : ConstIterator Last() const { return ConstIterator(const_cast<List*>(&mHead)); }
557 :
558 0 : class Iterator : public ConstIterator {
559 : public:
560 0 : explicit Iterator(List* aList) : ConstIterator(aList) {}
561 :
562 0 : Iterator& operator++() {
563 0 : mCurrent = mCurrent->mNext;
564 0 : return *this; }
565 :
566 0 : Iterator operator++(int) {
567 0 : Iterator result(*this);
568 0 : mCurrent = mCurrent->mNext;
569 0 : return result; }
570 :
571 : Iterator& operator--() {
572 : mCurrent = mCurrent->mPrev;
573 : return *this; }
574 :
575 0 : Iterator operator--(int) {
576 0 : Iterator result(*this);
577 0 : mCurrent = mCurrent->mPrev;
578 0 : return result; }
579 :
580 0 : Instantiation& operator*() const {
581 0 : return mCurrent->mInstantiation; }
582 :
583 0 : Instantiation* operator->() const {
584 0 : return &mCurrent->mInstantiation; }
585 :
586 : bool operator==(const ConstIterator& aConstIterator) const {
587 : return mCurrent == aConstIterator.mCurrent; }
588 :
589 0 : bool operator!=(const ConstIterator& aConstIterator) const {
590 0 : return mCurrent != aConstIterator.mCurrent; }
591 :
592 : friend class InstantiationSet;
593 : };
594 :
595 0 : Iterator First() { return Iterator(mHead.mNext); }
596 0 : Iterator Last() { return Iterator(&mHead); }
597 :
598 0 : bool Empty() const { return First() == Last(); }
599 :
600 0 : Iterator Append(const Instantiation& aInstantiation) {
601 0 : return Insert(Last(), aInstantiation); }
602 :
603 : Iterator Insert(Iterator aBefore, const Instantiation& aInstantiation);
604 :
605 : Iterator Erase(Iterator aElement);
606 :
607 : void Clear();
608 :
609 : bool HasAssignmentFor(nsIAtom* aVariable) const;
610 : };
611 :
612 : //----------------------------------------------------------------------
613 :
614 : /**
615 : * A abstract base class for all nodes in the rule network
616 : */
617 : class ReteNode
618 : {
619 : public:
620 0 : ReteNode() {}
621 0 : virtual ~ReteNode() {}
622 :
623 : /**
624 : * Propagate a set of instantiations "down" through the
625 : * network. Each instantiation is a partial set of
626 : * variable-to-value assignments, along with the memory elements
627 : * that support it.
628 : *
629 : * The node must evaluate each instantiation, and either 1)
630 : * extend it with additional assignments and memory-element
631 : * support, or 2) remove it from the set because it is
632 : * inconsistent with the constraints that this node applies.
633 : *
634 : * The node must then pass the resulting instantiation set along
635 : * to any of its children in the network. (In other words, the
636 : * node must recursively call Propagate() on its children. We
637 : * should fix this to make the algorithm interruptable.)
638 : *
639 : * See TestNode::Propagate for details about instantiation set ownership
640 : *
641 : * @param aInstantiations the set of instantiations to propagate
642 : * down through the network.
643 : * @param aIsUpdate true if updating, false for first generation
644 : * @param aTakenInstantiations true if the ownership over aInstantiations
645 : * has been taken from the caller. If false,
646 : * the caller owns it.
647 : * @return NS_OK if no errors occurred.
648 : */
649 : virtual nsresult Propagate(InstantiationSet& aInstantiations,
650 : bool aIsUpdate, bool& aTakenInstantiations) = 0;
651 : };
652 :
653 : //----------------------------------------------------------------------
654 :
655 : /**
656 : * A collection of nodes in the rule network
657 : */
658 : class ReteNodeSet
659 : {
660 : public:
661 : ReteNodeSet();
662 : ~ReteNodeSet();
663 :
664 : nsresult Add(ReteNode* aNode);
665 : nsresult Clear();
666 :
667 : class Iterator;
668 :
669 : class ConstIterator {
670 : public:
671 0 : explicit ConstIterator(ReteNode** aNode) : mCurrent(aNode) {}
672 :
673 0 : ConstIterator(const ConstIterator& aConstIterator)
674 0 : : mCurrent(aConstIterator.mCurrent) {}
675 :
676 : ConstIterator& operator=(const ConstIterator& aConstIterator) {
677 : mCurrent = aConstIterator.mCurrent;
678 : return *this; }
679 :
680 0 : ConstIterator& operator++() {
681 0 : ++mCurrent;
682 0 : return *this; }
683 :
684 : ConstIterator operator++(int) {
685 : ConstIterator result(*this);
686 : ++mCurrent;
687 : return result; }
688 :
689 0 : const ReteNode* operator*() const {
690 0 : return *mCurrent; }
691 :
692 : const ReteNode* operator->() const {
693 : return *mCurrent; }
694 :
695 : bool operator==(const ConstIterator& aConstIterator) const {
696 : return mCurrent == aConstIterator.mCurrent; }
697 :
698 0 : bool operator!=(const ConstIterator& aConstIterator) const {
699 0 : return mCurrent != aConstIterator.mCurrent; }
700 :
701 : protected:
702 : friend class Iterator; // XXXwaterson this is so wrong!
703 : ReteNode** mCurrent;
704 : };
705 :
706 : ConstIterator First() const { return ConstIterator(mNodes); }
707 : ConstIterator Last() const { return ConstIterator(mNodes + mCount); }
708 :
709 : class Iterator : public ConstIterator {
710 : public:
711 0 : explicit Iterator(ReteNode** aNode) : ConstIterator(aNode) {}
712 :
713 0 : Iterator& operator++() {
714 0 : ++mCurrent;
715 0 : return *this; }
716 :
717 : Iterator operator++(int) {
718 : Iterator result(*this);
719 : ++mCurrent;
720 : return result; }
721 :
722 0 : ReteNode* operator*() const {
723 0 : return *mCurrent; }
724 :
725 0 : ReteNode* operator->() const {
726 0 : return *mCurrent; }
727 :
728 : bool operator==(const ConstIterator& aConstIterator) const {
729 : return mCurrent == aConstIterator.mCurrent; }
730 :
731 0 : bool operator!=(const ConstIterator& aConstIterator) const {
732 0 : return mCurrent != aConstIterator.mCurrent; }
733 : };
734 :
735 0 : Iterator First() { return Iterator(mNodes); }
736 0 : Iterator Last() { return Iterator(mNodes + mCount); }
737 :
738 0 : int32_t Count() const { return mCount; }
739 :
740 : protected:
741 : ReteNode** mNodes;
742 : int32_t mCount;
743 : int32_t mCapacity;
744 : };
745 :
746 : //----------------------------------------------------------------------
747 :
748 : /**
749 : * A node that applies a test condition to a set of instantiations.
750 : *
751 : * This class provides implementations of Propagate() and Constrain()
752 : * in terms of one simple operation, FilterInstantiations(). A node
753 : * that is a "simple test node" in a rule network should derive from
754 : * this class, and need only implement FilterInstantiations().
755 : */
756 0 : class TestNode : public ReteNode
757 : {
758 : public:
759 : explicit TestNode(TestNode* aParent);
760 :
761 : /**
762 : * Retrieve the test node's parent
763 : * @return the test node's parent
764 : */
765 0 : TestNode* GetParent() const { return mParent; }
766 :
767 : /**
768 : * Calls FilterInstantiations() on the instantiation set, and if
769 : * the resulting set isn't empty, propagates the new set down to
770 : * each of the test node's children.
771 : *
772 : * Note that the caller of Propagate is responsible for deleting
773 : * aInstantiations if necessary as described below.
774 : *
775 : * Propagate may be called in update or non-update mode as indicated
776 : * by the aIsUpdate argument. Non-update mode is used when initially
777 : * generating results, whereas update mode is used when the datasource
778 : * changes and new results might be available.
779 : *
780 : * The last node in a chain of TestNodes is always an nsInstantiationNode.
781 : * In non-update mode, this nsInstantiationNode will cache the results
782 : * in the query using the SetCachedResults method. The query processor
783 : * takes these cached results and creates a nsXULTemplateResultSetRDF
784 : * which is the enumeration returned to the template builder. This
785 : * nsXULTemplateResultSetRDF owns the instantiations and they will be
786 : * deleted when the nsXULTemplateResultSetRDF goes away.
787 : *
788 : * In update mode, the nsInstantiationNode node will iterate over the
789 : * instantiations itself and callback to the builder to update any matches
790 : * and generated content. If no instantiations match, then the builder
791 : * will never be called.
792 : *
793 : * Thus, the difference between update and non-update modes is that in
794 : * update mode, the results and instantiations have been already handled
795 : * whereas in non-update mode they are expected to be returned in an
796 : * nsXULTemplateResultSetRDF for further processing by the builder.
797 : *
798 : * Regardless, aTakenInstantiations will be set to true if the
799 : * ownership over aInstantiations has been transferred to a result set.
800 : * If set to false, the caller is still responsible for aInstantiations.
801 : * aTakenInstantiations will be set properly even if an error occurs.
802 : */
803 : virtual nsresult Propagate(InstantiationSet& aInstantiations,
804 : bool aIsUpdate, bool& aTakenInstantiations) override;
805 :
806 : /**
807 : * This is called by a child node on its parent to allow the
808 : * parent's constraints to apply to the set of instantiations.
809 : *
810 : * A node must iterate through the set of instantiations, and for
811 : * each instantiation, either 1) extend the instantiation by
812 : * adding variable-to-value assignments and memory element support
813 : * for those assignments, or 2) remove the instantiation because
814 : * it is inconsistent.
815 : *
816 : * The node must then pass the resulting set of instantiations up
817 : * to its parent (by recursive call; we should make this iterative
818 : * & interruptable at some point.)
819 : *
820 : * @param aInstantiations the set of instantiations that must
821 : * be constrained
822 : * @return NS_OK if no errors occurred
823 : */
824 : virtual nsresult Constrain(InstantiationSet& aInstantiations);
825 :
826 : /**
827 : * Given a set of instantiations, filter out any that are
828 : * inconsistent with the test node's test, and append
829 : * variable-to-value assignments and memory element support for
830 : * those which do pass the test node's test.
831 : *
832 : * @param aInstantiations the set of instantiations to be
833 : * filtered
834 : * @param aCantHandleYet [out] true if the instantiations do not contain
835 : * enough information to constrain the data. May be null if this
836 : * isn't important to the caller.
837 : * @return NS_OK if no errors occurred.
838 : */
839 : virtual nsresult FilterInstantiations(InstantiationSet& aInstantiations,
840 : bool* aCantHandleYet) const = 0;
841 : //XXX probably better named "ApplyConstraints" or "Discrminiate" or something
842 :
843 : /**
844 : * Add another node as a child of this node.
845 : * @param aNode the node to add.
846 : * @return NS_OK if no errors occur.
847 : */
848 0 : nsresult AddChild(ReteNode* aNode) { return mKids.Add(aNode); }
849 :
850 : /**
851 : * Remove all the children of this node
852 : * @return NS_OK if no errors occur.
853 : */
854 : nsresult RemoveAllChildren() { return mKids.Clear(); }
855 :
856 : protected:
857 : TestNode* mParent;
858 : ReteNodeSet mKids;
859 : };
860 :
861 : #endif // nsRuleNetwork_h__
|
