nsRuleNetwork.cpp 11 KB

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