Add m-esr52 at 52.6.0

1 files changed, 1964 insertions, 0 deletions

diff --git a/rdf/base/nsInMemoryDataSource.cpp b/rdf/base/nsInMemoryDataSource.cpp
new file mode 100644
index 000000000..9bdd6b4fb
--- /dev/null
+++ b/rdf/base/nsInMemoryDataSource.cpp
@@ -0,0 +1,1964 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*-
+ *
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/.
+ *
+ *
+ * This Original Code has been modified by IBM Corporation.
+ * Modifications made by IBM described herein are
+ * Copyright (c) International Business Machines
+ * Corporation, 2000
+ *
+ * Modifications to Mozilla code or documentation
+ * identified per MPL Section 3.3
+ *
+ * Date         Modified by     Description of modification
+ * 03/27/2000   IBM Corp.       Added PR_CALLBACK for Optlink
+ *                               use in OS2
+ */
+
+/*
+
+  Implementation for an in-memory RDF data store.
+
+  TO DO
+
+  1) Instrument this code to gather space and time performance
+     characteristics.
+
+  2) Optimize lookups for datasources which have a small number
+     of properties + fanning out to a large number of targets.
+
+  3) Complete implementation of thread-safety; specifically, make
+     assertions be reference counted objects (so that a cursor can
+     still refer to an assertion that gets removed from the graph).
+
+ */
+
+#include "nsAgg.h"
+#include "nsCOMPtr.h"
+#include "nscore.h"
+#include "nsArrayEnumerator.h"
+#include "nsIOutputStream.h"
+#include "nsIRDFDataSource.h"
+#include "nsIRDFLiteral.h"
+#include "nsIRDFNode.h"
+#include "nsIRDFObserver.h"
+#include "nsIRDFInMemoryDataSource.h"
+#include "nsIRDFPropagatableDataSource.h"
+#include "nsIRDFPurgeableDataSource.h"
+#include "nsIRDFService.h"
+#include "nsIServiceManager.h"
+#include "nsCOMArray.h"
+#include "nsEnumeratorUtils.h"
+#include "nsTArray.h"
+#include "nsCRT.h"
+#include "nsRDFCID.h"
+#include "nsRDFBaseDataSources.h"
+#include "nsString.h"
+#include "nsReadableUtils.h"
+#include "nsXPIDLString.h"
+#include "rdfutil.h"
+#include "PLDHashTable.h"
+#include "plstr.h"
+#include "mozilla/Logging.h"
+#include "rdf.h"
+
+#include "rdfIDataSource.h"
+#include "rdfITripleVisitor.h"
+
+using mozilla::LogLevel;
+
+// This struct is used as the slot value in the forward and reverse
+// arcs hash tables.
+//
+// Assertion objects are reference counted, because each Assertion's
+// ownership is shared between the datasource and any enumerators that
+// are currently iterating over the datasource.
+//
+class Assertion
+{
+public:
+    Assertion(nsIRDFResource* aSource,      // normal assertion
+              nsIRDFResource* aProperty,
+              nsIRDFNode* aTarget,
+              bool aTruthValue);
+    explicit Assertion(nsIRDFResource* aSource);     // PLDHashTable assertion variant
+
+private:
+    ~Assertion();
+
+public:
+    void AddRef() {
+        if (mRefCnt == UINT16_MAX) {
+            NS_WARNING("refcount overflow, leaking Assertion");
+            return;
+        }
+        ++mRefCnt;
+    }
+
+    void Release() {
+        if (mRefCnt == UINT16_MAX) {
+            NS_WARNING("refcount overflow, leaking Assertion");
+            return;
+        }
+        if (--mRefCnt == 0)
+            delete this;
+    }
+
+    // For nsIRDFPurgeableDataSource
+    inline  void    Mark()      { u.as.mMarked = true; }
+    inline  bool    IsMarked()  { return u.as.mMarked; }
+    inline  void    Unmark()    { u.as.mMarked = false; }
+
+    // public for now, because I'm too lazy to go thru and clean this up.
+
+    // These are shared between hash/as (see the union below)
+    nsIRDFResource*         mSource;
+    Assertion*              mNext;
+
+    union
+    {
+        struct hash
+        {
+            PLDHashTable*  mPropertyHash;
+        } hash;
+        struct as
+        {
+            nsIRDFResource* mProperty;
+            nsIRDFNode*     mTarget;
+            Assertion*      mInvNext;
+            // make sure bool are final elements
+            bool            mTruthValue;
+            bool            mMarked;
+        } as;
+    } u;
+
+    // also shared between hash/as (see the union above)
+    // but placed after union definition to ensure that
+    // all 32-bit entries are long aligned
+    uint16_t                    mRefCnt;
+    bool                        mHashEntry;
+};
+
+
+struct Entry : PLDHashEntryHdr {
+    nsIRDFNode*     mNode;
+    Assertion*      mAssertions;
+};
+
+
+Assertion::Assertion(nsIRDFResource* aSource)
+    : mSource(aSource),
+      mNext(nullptr),
+      mRefCnt(0),
+      mHashEntry(true)
+{
+    MOZ_COUNT_CTOR(Assertion);
+
+    NS_ADDREF(mSource);
+
+    u.hash.mPropertyHash =
+        new PLDHashTable(PLDHashTable::StubOps(), sizeof(Entry));
+}
+
+Assertion::Assertion(nsIRDFResource* aSource,
+                     nsIRDFResource* aProperty,
+                     nsIRDFNode* aTarget,
+                     bool aTruthValue)
+    : mSource(aSource),
+      mNext(nullptr),
+      mRefCnt(0),
+      mHashEntry(false)
+{
+    MOZ_COUNT_CTOR(Assertion);
+
+    u.as.mProperty = aProperty;
+    u.as.mTarget = aTarget;
+
+    NS_ADDREF(mSource);
+    NS_ADDREF(u.as.mProperty);
+    NS_ADDREF(u.as.mTarget);
+
+    u.as.mInvNext = nullptr;
+    u.as.mTruthValue = aTruthValue;
+    u.as.mMarked = false;
+}
+
+Assertion::~Assertion()
+{
+    if (mHashEntry && u.hash.mPropertyHash) {
+        for (auto i = u.hash.mPropertyHash->Iter(); !i.Done(); i.Next()) {
+            auto entry = static_cast<Entry*>(i.Get());
+            Assertion* as = entry->mAssertions;
+            while (as) {
+                Assertion* doomed = as;
+                as = as->mNext;
+
+                // Unlink, and release the datasource's reference.
+                doomed->mNext = doomed->u.as.mInvNext = nullptr;
+                doomed->Release();
+            }
+        }
+        delete u.hash.mPropertyHash;
+        u.hash.mPropertyHash = nullptr;
+    }
+
+    MOZ_COUNT_DTOR(Assertion);
+#ifdef DEBUG_REFS
+    --gInstanceCount;
+    fprintf(stdout, "%d - RDF: Assertion\n", gInstanceCount);
+#endif
+
+    NS_RELEASE(mSource);
+    if (!mHashEntry)
+    {
+        NS_RELEASE(u.as.mProperty);
+        NS_RELEASE(u.as.mTarget);
+    }
+}
+
+////////////////////////////////////////////////////////////////////////
+// InMemoryDataSource
+class InMemoryArcsEnumeratorImpl;
+class InMemoryAssertionEnumeratorImpl;
+class InMemoryResourceEnumeratorImpl;
+
+class InMemoryDataSource : public nsIRDFDataSource,
+                           public nsIRDFInMemoryDataSource,
+                           public nsIRDFPropagatableDataSource,
+                           public nsIRDFPurgeableDataSource,
+                           public rdfIDataSource
+{
+protected:
+    // These hash tables are keyed on pointers to nsIRDFResource
+    // objects (the nsIRDFService ensures that there is only ever one
+    // nsIRDFResource object per unique URI). The value of an entry is
+    // an Assertion struct, which is a linked list of (subject
+    // predicate object) triples.
+    PLDHashTable mForwardArcs;
+    PLDHashTable mReverseArcs;
+
+    nsCOMArray<nsIRDFObserver> mObservers;  
+    uint32_t                   mNumObservers;
+
+    // VisitFoo needs to block writes, [Un]Assert only allowed
+    // during mReadCount == 0
+    uint32_t mReadCount;
+
+    friend class InMemoryArcsEnumeratorImpl;
+    friend class InMemoryAssertionEnumeratorImpl;
+    friend class InMemoryResourceEnumeratorImpl; // b/c it needs to enumerate mForwardArcs
+
+    // Thread-safe writer implementation methods.
+    nsresult
+    LockedAssert(nsIRDFResource* source, 
+                 nsIRDFResource* property, 
+                 nsIRDFNode* target,
+                 bool tv);
+
+    nsresult
+    LockedUnassert(nsIRDFResource* source,
+                   nsIRDFResource* property,
+                   nsIRDFNode* target);
+
+    explicit InMemoryDataSource(nsISupports* aOuter);
+    virtual ~InMemoryDataSource();
+
+    friend nsresult
+    NS_NewRDFInMemoryDataSource(nsISupports* aOuter, const nsIID& aIID, void** aResult);
+
+public:
+    NS_DECL_CYCLE_COLLECTING_AGGREGATED
+    NS_DECL_AGGREGATED_CYCLE_COLLECTION_CLASS(InMemoryDataSource)
+
+    // nsIRDFDataSource methods
+    NS_DECL_NSIRDFDATASOURCE
+
+    // nsIRDFInMemoryDataSource methods
+    NS_DECL_NSIRDFINMEMORYDATASOURCE
+
+    // nsIRDFPropagatableDataSource methods
+    NS_DECL_NSIRDFPROPAGATABLEDATASOURCE
+
+    // nsIRDFPurgeableDataSource methods
+    NS_DECL_NSIRDFPURGEABLEDATASOURCE
+
+    // rdfIDataSource methods
+    NS_DECL_RDFIDATASOURCE
+
+protected:
+    struct SweepInfo {
+        Assertion* mUnassertList;
+        PLDHashTable* mReverseArcs;
+    };
+
+    static void
+    SweepForwardArcsEntries(PLDHashTable* aTable, SweepInfo* aArg);
+
+public:
+    // Implementation methods
+    Assertion*
+    GetForwardArcs(nsIRDFResource* u) {
+        PLDHashEntryHdr* hdr = mForwardArcs.Search(u);
+        return hdr ? static_cast<Entry*>(hdr)->mAssertions : nullptr;
+    }
+
+    Assertion*
+    GetReverseArcs(nsIRDFNode* v) {
+        PLDHashEntryHdr* hdr = mReverseArcs.Search(v);
+        return hdr ? static_cast<Entry*>(hdr)->mAssertions : nullptr;
+    }
+
+    void
+    SetForwardArcs(nsIRDFResource* u, Assertion* as) {
+        if (as) {
+            auto entry =
+                static_cast<Entry*>(mForwardArcs.Add(u, mozilla::fallible));
+            if (entry) {
+                entry->mNode = u;
+                entry->mAssertions = as;
+            }
+        }
+        else {
+            mForwardArcs.Remove(u);
+        }
+    }
+
+    void
+    SetReverseArcs(nsIRDFNode* v, Assertion* as) {
+        if (as) {
+            auto entry =
+                static_cast<Entry*>(mReverseArcs.Add(v, mozilla::fallible));
+            if (entry) {
+                entry->mNode = v;
+                entry->mAssertions = as;
+            }
+        }
+        else {
+            mReverseArcs.Remove(v);
+        }
+    }
+
+    void
+    LogOperation(const char* aOperation,
+                 nsIRDFResource* asource,
+                 nsIRDFResource* aProperty,
+                 nsIRDFNode* aTarget,
+                 bool aTruthValue = true);
+
+    bool    mPropagateChanges;
+
+private:
+    static mozilla::LazyLogModule gLog;
+};
+
+mozilla::LazyLogModule InMemoryDataSource::gLog("InMemoryDataSource");
+
+//----------------------------------------------------------------------
+//
+// InMemoryAssertionEnumeratorImpl
+//
+
+/**
+ * InMemoryAssertionEnumeratorImpl
+ */
+class InMemoryAssertionEnumeratorImpl : public nsISimpleEnumerator
+{
+private:
+    InMemoryDataSource* mDataSource;
+    nsIRDFResource* mSource;
+    nsIRDFResource* mProperty;
+    nsIRDFNode*     mTarget;
+    nsIRDFNode*     mValue;
+    bool            mTruthValue;
+    Assertion*      mNextAssertion;
+
+    virtual ~InMemoryAssertionEnumeratorImpl();
+
+public:
+    InMemoryAssertionEnumeratorImpl(InMemoryDataSource* aDataSource,
+                                    nsIRDFResource* aSource,
+                                    nsIRDFResource* aProperty,
+                                    nsIRDFNode* aTarget,
+                                    bool aTruthValue);
+
+    // nsISupports interface
+    NS_DECL_ISUPPORTS
+
+    // nsISimpleEnumerator interface
+    NS_DECL_NSISIMPLEENUMERATOR
+};
+
+////////////////////////////////////////////////////////////////////////
+
+
+InMemoryAssertionEnumeratorImpl::InMemoryAssertionEnumeratorImpl(
+                 InMemoryDataSource* aDataSource,
+                 nsIRDFResource* aSource,
+                 nsIRDFResource* aProperty,
+                 nsIRDFNode* aTarget,
+                 bool aTruthValue)
+    : mDataSource(aDataSource),
+      mSource(aSource),
+      mProperty(aProperty),
+      mTarget(aTarget),
+      mValue(nullptr),
+      mTruthValue(aTruthValue),
+      mNextAssertion(nullptr)
+{
+    NS_ADDREF(mDataSource);
+    NS_IF_ADDREF(mSource);
+    NS_ADDREF(mProperty);
+    NS_IF_ADDREF(mTarget);
+
+    if (mSource) {
+        mNextAssertion = mDataSource->GetForwardArcs(mSource);
+
+        if (mNextAssertion && mNextAssertion->mHashEntry) {
+            // its our magical HASH_ENTRY forward hash for assertions
+            PLDHashEntryHdr* hdr =
+                mNextAssertion->u.hash.mPropertyHash->Search(aProperty);
+            mNextAssertion =
+                hdr ? static_cast<Entry*>(hdr)->mAssertions : nullptr;
+        }
+    }
+    else {
+        mNextAssertion = mDataSource->GetReverseArcs(mTarget);
+    }
+
+    // Add an owning reference from the enumerator
+    if (mNextAssertion)
+        mNextAssertion->AddRef();
+}
+
+InMemoryAssertionEnumeratorImpl::~InMemoryAssertionEnumeratorImpl()
+{
+#ifdef DEBUG_REFS
+    --gInstanceCount;
+    fprintf(stdout, "%d - RDF: InMemoryAssertionEnumeratorImpl\n", gInstanceCount);
+#endif
+
+    if (mNextAssertion)
+        mNextAssertion->Release();
+
+    NS_IF_RELEASE(mDataSource);
+    NS_IF_RELEASE(mSource);
+    NS_IF_RELEASE(mProperty);
+    NS_IF_RELEASE(mTarget);
+    NS_IF_RELEASE(mValue);
+}
+
+NS_IMPL_ADDREF(InMemoryAssertionEnumeratorImpl)
+NS_IMPL_RELEASE(InMemoryAssertionEnumeratorImpl)
+NS_IMPL_QUERY_INTERFACE(InMemoryAssertionEnumeratorImpl, nsISimpleEnumerator)
+
+NS_IMETHODIMP
+InMemoryAssertionEnumeratorImpl::HasMoreElements(bool* aResult)
+{
+    if (mValue) {
+        *aResult = true;
+        return NS_OK;
+    }
+
+    while (mNextAssertion) {
+        bool foundIt = false;
+        if ((mProperty == mNextAssertion->u.as.mProperty) &&
+            (mTruthValue == mNextAssertion->u.as.mTruthValue)) {
+            if (mSource) {
+                mValue = mNextAssertion->u.as.mTarget;
+                NS_ADDREF(mValue);
+            }
+            else {
+                mValue = mNextAssertion->mSource;
+                NS_ADDREF(mValue);
+            }
+            foundIt = true;
+        }
+
+        // Remember the last assertion we were holding on to
+        Assertion* as = mNextAssertion;
+
+        // iterate
+        mNextAssertion = (mSource) ? mNextAssertion->mNext : mNextAssertion->u.as.mInvNext;
+
+        // grab an owning reference from the enumerator to the next assertion
+        if (mNextAssertion)
+            mNextAssertion->AddRef();
+
+        // ...and release the reference from the enumerator to the old one.
+        as->Release();
+
+        if (foundIt) {
+            *aResult = true;
+            return NS_OK;
+        }
+    }
+
+    *aResult = false;
+    return NS_OK;
+}
+
+
+NS_IMETHODIMP
+InMemoryAssertionEnumeratorImpl::GetNext(nsISupports** aResult)
+{
+    nsresult rv;
+
+    bool hasMore;
+    rv = HasMoreElements(&hasMore);
+    if (NS_FAILED(rv)) return rv;
+
+    if (! hasMore)
+        return NS_ERROR_UNEXPECTED;
+
+    // Don't AddRef: we "transfer" ownership to the caller
+    *aResult = mValue;
+    mValue = nullptr;
+
+    return NS_OK;
+}
+
+////////////////////////////////////////////////////////////////////////
+//
+
+/**
+ * This class is a little bit bizarre in that it implements both the
+ * <tt>nsIRDFArcsOutCursor</tt> and <tt>nsIRDFArcsInCursor</tt> interfaces.
+ * Because the structure of the in-memory graph is pretty flexible, it's
+ * fairly easy to parameterize this class. The only funky thing to watch
+ * out for is the multiple inheritance clashes.
+ */
+
+class InMemoryArcsEnumeratorImpl : public nsISimpleEnumerator
+{
+private:
+    InMemoryDataSource* mDataSource;
+    nsIRDFResource*     mSource;
+    nsIRDFNode*         mTarget;
+    AutoTArray<nsCOMPtr<nsIRDFResource>, 8> mAlreadyReturned;
+    nsIRDFResource*     mCurrent;
+    Assertion*          mAssertion;
+    nsCOMArray<nsIRDFNode>* mHashArcs;
+
+    virtual ~InMemoryArcsEnumeratorImpl();
+
+public:
+    InMemoryArcsEnumeratorImpl(InMemoryDataSource* aDataSource,
+                               nsIRDFResource* aSource,
+                               nsIRDFNode* aTarget);
+
+    // nsISupports interface
+    NS_DECL_ISUPPORTS
+
+    // nsISimpleEnumerator interface
+    NS_DECL_NSISIMPLEENUMERATOR
+};
+
+
+InMemoryArcsEnumeratorImpl::InMemoryArcsEnumeratorImpl(InMemoryDataSource* aDataSource,
+                                                       nsIRDFResource* aSource,
+                                                       nsIRDFNode* aTarget)
+    : mDataSource(aDataSource),
+      mSource(aSource),
+      mTarget(aTarget),
+      mCurrent(nullptr),
+      mHashArcs(nullptr)
+{
+    NS_ADDREF(mDataSource);
+    NS_IF_ADDREF(mSource);
+    NS_IF_ADDREF(mTarget);
+
+    if (mSource) {
+        // cast okay because it's a closed system
+        mAssertion = mDataSource->GetForwardArcs(mSource);
+
+        if (mAssertion && mAssertion->mHashEntry) {
+            // its our magical HASH_ENTRY forward hash for assertions
+            mHashArcs = new nsCOMArray<nsIRDFNode>();
+            for (auto i = mAssertion->u.hash.mPropertyHash->Iter();
+                 !i.Done();
+                 i.Next()) {
+                auto entry = static_cast<Entry*>(i.Get());
+                mHashArcs->AppendElement(entry->mNode);
+            }
+            mAssertion = nullptr;
+        }
+    }
+    else {
+        mAssertion = mDataSource->GetReverseArcs(mTarget);
+    }
+}
+
+InMemoryArcsEnumeratorImpl::~InMemoryArcsEnumeratorImpl()
+{
+#ifdef DEBUG_REFS
+    --gInstanceCount;
+    fprintf(stdout, "%d - RDF: InMemoryArcsEnumeratorImpl\n", gInstanceCount);
+#endif
+
+    NS_RELEASE(mDataSource);
+    NS_IF_RELEASE(mSource);
+    NS_IF_RELEASE(mTarget);
+    NS_IF_RELEASE(mCurrent);
+    delete mHashArcs;
+}
+
+NS_IMPL_ADDREF(InMemoryArcsEnumeratorImpl)
+NS_IMPL_RELEASE(InMemoryArcsEnumeratorImpl)
+NS_IMPL_QUERY_INTERFACE(InMemoryArcsEnumeratorImpl, nsISimpleEnumerator)
+
+NS_IMETHODIMP
+InMemoryArcsEnumeratorImpl::HasMoreElements(bool* aResult)
+{
+    NS_PRECONDITION(aResult != nullptr, "null ptr");
+    if (! aResult)
+        return NS_ERROR_NULL_POINTER;
+
+    if (mCurrent) {
+        *aResult = true;
+        return NS_OK;
+    }
+
+    if (mHashArcs) {
+        if (!mHashArcs->IsEmpty()) {
+            const uint32_t last = mHashArcs->Length() - 1;
+            nsCOMPtr<nsIRDFResource> tmp(do_QueryInterface(mHashArcs->ObjectAt(last)));
+            tmp.forget(&mCurrent);
+            mHashArcs->RemoveElementAt(last);
+            *aResult = true;
+            return NS_OK;
+        }
+    }
+    else
+        while (mAssertion) {
+            nsIRDFResource* next = mAssertion->u.as.mProperty;
+
+            // "next" is the property arc we are tentatively going to return
+            // in a subsequent GetNext() call.  It is important to do two
+            // things, however, before that can happen:
+            //   1) Make sure it's not an arc we've already returned.
+            //   2) Make sure that |mAssertion| is not left pointing to
+            //      another assertion that has the same property as this one.
+            // The first is a practical concern; the second a defense against
+            // an obscure crash and other erratic behavior.  To ensure the
+            // second condition, skip down the chain until we find the next 
+            // assertion with a property that doesn't match the current one.
+            // (All these assertions would be skipped via mAlreadyReturned
+            // checks anyways; this is even a bit faster.)
+
+            do {
+                mAssertion = (mSource ? mAssertion->mNext :
+                        mAssertion->u.as.mInvNext);
+            }
+            while (mAssertion && (next == mAssertion->u.as.mProperty));
+
+            bool alreadyReturned = false;
+            for (int32_t i = mAlreadyReturned.Length() - 1; i >= 0; --i) {
+                if (mAlreadyReturned[i] == next) {
+                    alreadyReturned = true;
+                    break;
+                }
+            }
+
+            if (! alreadyReturned) {
+                mCurrent = next;
+                NS_ADDREF(mCurrent);
+                *aResult = true;
+                return NS_OK;
+            }
+        }
+
+    *aResult = false;
+    return NS_OK;
+}
+
+
+NS_IMETHODIMP
+InMemoryArcsEnumeratorImpl::GetNext(nsISupports** aResult)
+{
+    nsresult rv;
+
+    bool hasMore;
+    rv = HasMoreElements(&hasMore);
+    if (NS_FAILED(rv)) return rv;
+
+    if (! hasMore)
+        return NS_ERROR_UNEXPECTED;
+
+    // Add this to the set of things we've already returned so that we
+    // can ensure uniqueness
+    mAlreadyReturned.AppendElement(mCurrent);
+
+    // Don't AddRef: we "transfer" ownership to the caller
+    *aResult = mCurrent;
+    mCurrent = nullptr;
+
+    return NS_OK;
+}
+
+
+////////////////////////////////////////////////////////////////////////
+// InMemoryDataSource
+
+nsresult
+NS_NewRDFInMemoryDataSource(nsISupports* aOuter, const nsIID& aIID, void** aResult)
+{
+    NS_PRECONDITION(aResult != nullptr, "null ptr");
+    if (! aResult)
+        return NS_ERROR_NULL_POINTER;
+    *aResult = nullptr;
+
+    if (aOuter && !aIID.Equals(NS_GET_IID(nsISupports))) {
+        NS_ERROR("aggregation requires nsISupports");
+        return NS_ERROR_ILLEGAL_VALUE;
+    }
+
+    InMemoryDataSource* datasource = new InMemoryDataSource(aOuter);
+    NS_ADDREF(datasource);
+
+    datasource->fAggregated.AddRef();
+    nsresult rv = datasource->AggregatedQueryInterface(aIID, aResult); // This'll AddRef()
+    datasource->fAggregated.Release();
+
+    NS_RELEASE(datasource);
+    return rv;
+}
+
+
+InMemoryDataSource::InMemoryDataSource(nsISupports* aOuter)
+    : mForwardArcs(PLDHashTable::StubOps(), sizeof(Entry))
+    , mReverseArcs(PLDHashTable::StubOps(), sizeof(Entry))
+    , mNumObservers(0)
+    , mReadCount(0)
+{
+    NS_INIT_AGGREGATED(aOuter);
+
+    mPropagateChanges = true;
+    MOZ_COUNT_CTOR(InMemoryDataSource);
+}
+
+
+InMemoryDataSource::~InMemoryDataSource()
+{
+#ifdef DEBUG_REFS
+    --gInstanceCount;
+    fprintf(stdout, "%d - RDF: InMemoryDataSource\n", gInstanceCount);
+#endif
+
+    if (mForwardArcs.EntryCount() > 0) {
+        // This'll release all of the Assertion objects that are
+        // associated with this data source. We only need to do this
+        // for the forward arcs, because the reverse arcs table
+        // indexes the exact same set of resources.
+        for (auto iter = mForwardArcs.Iter(); !iter.Done(); iter.Next()) {
+            auto entry = static_cast<Entry*>(iter.Get());
+            Assertion* as = entry->mAssertions;
+            while (as) {
+                Assertion* doomed = as;
+                as = as->mNext;
+
+                // Unlink, and release the datasource's reference.
+                doomed->mNext = doomed->u.as.mInvNext = nullptr;
+                doomed->Release();
+            }
+        }
+    }
+
+    MOZ_LOG(gLog, LogLevel::Debug,
+           ("InMemoryDataSource(%p): destroyed.", this));
+
+    MOZ_COUNT_DTOR(InMemoryDataSource);
+}
+
+
+////////////////////////////////////////////////////////////////////////
+
+NS_IMPL_CYCLE_COLLECTION_CLASS(InMemoryDataSource)
+
+NS_IMPL_CYCLE_COLLECTION_UNLINK_BEGIN(InMemoryDataSource)
+    NS_IMPL_CYCLE_COLLECTION_UNLINK(mObservers)
+NS_IMPL_CYCLE_COLLECTION_UNLINK_END
+NS_IMPL_CYCLE_COLLECTION_TRAVERSE_BEGIN_AGGREGATED(InMemoryDataSource)
+    NS_IMPL_CYCLE_COLLECTION_TRAVERSE(mObservers)
+NS_IMPL_CYCLE_COLLECTION_TRAVERSE_END
+
+NS_IMPL_CYCLE_COLLECTING_AGGREGATED(InMemoryDataSource)
+NS_INTERFACE_MAP_BEGIN_AGGREGATED(InMemoryDataSource)
+    NS_INTERFACE_MAP_ENTRIES_CYCLE_COLLECTION_AGGREGATED(InMemoryDataSource)
+    NS_INTERFACE_MAP_ENTRY(nsIRDFDataSource)
+    NS_INTERFACE_MAP_ENTRY(nsIRDFInMemoryDataSource)
+    NS_INTERFACE_MAP_ENTRY(nsIRDFPropagatableDataSource)
+    NS_INTERFACE_MAP_ENTRY(nsIRDFPurgeableDataSource)
+    NS_INTERFACE_MAP_ENTRY(rdfIDataSource)
+NS_INTERFACE_MAP_END
+
+////////////////////////////////////////////////////////////////////////
+
+
+void
+InMemoryDataSource::LogOperation(const char* aOperation,
+                                 nsIRDFResource* aSource,
+                                 nsIRDFResource* aProperty,
+                                 nsIRDFNode* aTarget,
+                                 bool aTruthValue)
+{
+    if (! MOZ_LOG_TEST(gLog, LogLevel::Debug))
+        return;
+
+    nsXPIDLCString uri;
+    aSource->GetValue(getter_Copies(uri));
+    PR_LogPrint
+           ("InMemoryDataSource(%p): %s", this, aOperation);
+
+    PR_LogPrint
+           ("  [(%p)%s]--", aSource, (const char*) uri);
+
+    aProperty->GetValue(getter_Copies(uri));
+
+    char tv = (aTruthValue ? '-' : '!');
+    PR_LogPrint
+           ("  --%c[(%p)%s]--", tv, aProperty, (const char*) uri);
+
+    nsCOMPtr<nsIRDFResource> resource;
+    nsCOMPtr<nsIRDFLiteral> literal;
+
+    if ((resource = do_QueryInterface(aTarget)) != nullptr) {
+        resource->GetValue(getter_Copies(uri));
+        PR_LogPrint
+           ("  -->[(%p)%s]", aTarget, (const char*) uri);
+    }
+    else if ((literal = do_QueryInterface(aTarget)) != nullptr) {
+        nsXPIDLString value;
+        literal->GetValue(getter_Copies(value));
+        nsAutoString valueStr(value);
+        char* valueCStr = ToNewCString(valueStr);
+
+        PR_LogPrint
+           ("  -->(\"%s\")\n", valueCStr);
+
+        free(valueCStr);
+    }
+    else {
+        PR_LogPrint
+           ("  -->(unknown-type)\n");
+    }
+}
+
+
+NS_IMETHODIMP
+InMemoryDataSource::GetURI(char* *uri)
+{
+    NS_PRECONDITION(uri != nullptr, "null ptr");
+    if (! uri)
+        return NS_ERROR_NULL_POINTER;
+
+    *uri = nullptr;
+    return NS_OK;
+}
+
+NS_IMETHODIMP
+InMemoryDataSource::GetSource(nsIRDFResource* property,
+                              nsIRDFNode* target,
+                              bool tv,
+                              nsIRDFResource** source)
+{
+    NS_PRECONDITION(source != nullptr, "null ptr");
+    if (! source)
+        return NS_ERROR_NULL_POINTER;
+
+    NS_PRECONDITION(property != nullptr, "null ptr");
+    if (! property)
+        return NS_ERROR_NULL_POINTER;
+
+    NS_PRECONDITION(target != nullptr, "null ptr");
+    if (! target)
+        return NS_ERROR_NULL_POINTER;
+
+    for (Assertion* as = GetReverseArcs(target); as; as = as->u.as.mInvNext) {
+        if ((property == as->u.as.mProperty) && (tv == as->u.as.mTruthValue)) {
+            *source = as->mSource;
+            NS_ADDREF(*source);
+            return NS_OK;
+        }
+    }
+    *source = nullptr;
+    return NS_RDF_NO_VALUE;
+}
+
+NS_IMETHODIMP
+InMemoryDataSource::GetTarget(nsIRDFResource* source,
+                              nsIRDFResource* property,
+                              bool tv,
+                              nsIRDFNode** target)
+{
+    NS_PRECONDITION(source != nullptr, "null ptr");
+    if (! source)
+        return NS_ERROR_NULL_POINTER;
+
+    NS_PRECONDITION(property != nullptr, "null ptr");
+    if (! property)
+        return NS_ERROR_NULL_POINTER;
+
+    NS_PRECONDITION(target != nullptr, "null ptr");
+    if (! target)
+        return NS_ERROR_NULL_POINTER;
+
+    Assertion *as = GetForwardArcs(source);
+    if (as && as->mHashEntry) {
+        PLDHashEntryHdr* hdr = as->u.hash.mPropertyHash->Search(property);
+        Assertion* val = hdr ? static_cast<Entry*>(hdr)->mAssertions : nullptr;
+        while (val) {
+            if (tv == val->u.as.mTruthValue) {
+                *target = val->u.as.mTarget;
+                NS_IF_ADDREF(*target);
+                return NS_OK;
+            }
+            val = val->mNext;
+        }
+    }
+    else
+    for (; as != nullptr; as = as->mNext) {
+        if ((property == as->u.as.mProperty) && (tv == (as->u.as.mTruthValue))) {
+            *target = as->u.as.mTarget;
+            NS_ADDREF(*target);
+            return NS_OK;
+        }
+    }
+
+    // If we get here, then there was no target with for the specified
+    // property & truth value.
+    *target = nullptr;
+    return NS_RDF_NO_VALUE;
+}
+
+NS_IMETHODIMP
+InMemoryDataSource::HasAssertion(nsIRDFResource* source,
+                                 nsIRDFResource* property,
+                                 nsIRDFNode* target,
+                                 bool tv,
+                                 bool* hasAssertion)
+{
+    if (! source)
+        return NS_ERROR_NULL_POINTER;
+
+    if (! property)
+        return NS_ERROR_NULL_POINTER;
+
+    if (! target)
+        return NS_ERROR_NULL_POINTER;
+
+    Assertion *as = GetForwardArcs(source);
+    if (as && as->mHashEntry) {
+        PLDHashEntryHdr* hdr = as->u.hash.mPropertyHash->Search(property);
+        Assertion* val = hdr ? static_cast<Entry*>(hdr)->mAssertions : nullptr;
+        while (val) {
+            if ((val->u.as.mTarget == target) && (tv == (val->u.as.mTruthValue))) {
+                *hasAssertion = true;
+                return NS_OK;
+            }
+            val = val->mNext;
+        }
+    }
+    else
+    for (; as != nullptr; as = as->mNext) {
+        // check target first as its most unique
+        if (target != as->u.as.mTarget)
+            continue;
+
+        if (property != as->u.as.mProperty)
+            continue;
+
+        if (tv != (as->u.as.mTruthValue))
+            continue;
+
+        // found it!
+        *hasAssertion = true;
+        return NS_OK;
+    }
+
+    // If we get here, we couldn't find the assertion
+    *hasAssertion = false;
+    return NS_OK;
+}
+
+NS_IMETHODIMP
+InMemoryDataSource::GetSources(nsIRDFResource* aProperty,
+                               nsIRDFNode* aTarget,
+                               bool aTruthValue,
+                               nsISimpleEnumerator** aResult)
+{
+    NS_PRECONDITION(aProperty != nullptr, "null ptr");
+    if (! aProperty)
+        return NS_ERROR_NULL_POINTER;
+
+    NS_PRECONDITION(aTarget != nullptr, "null ptr");
+    if (! aTarget)
+        return NS_ERROR_NULL_POINTER;
+
+    NS_PRECONDITION(aResult != nullptr, "null ptr");
+    if (! aResult)
+        return NS_ERROR_NULL_POINTER;
+
+    InMemoryAssertionEnumeratorImpl* result =
+        new InMemoryAssertionEnumeratorImpl(this, nullptr, aProperty,
+                                            aTarget, aTruthValue);
+
+    if (! result)
+        return NS_ERROR_OUT_OF_MEMORY;
+
+    NS_ADDREF(result);
+    *aResult = result;
+
+    return NS_OK;
+}
+
+NS_IMETHODIMP
+InMemoryDataSource::GetTargets(nsIRDFResource* aSource,
+                               nsIRDFResource* aProperty,
+                               bool aTruthValue,
+                               nsISimpleEnumerator** aResult)
+{
+    NS_PRECONDITION(aSource != nullptr, "null ptr");
+    if (! aSource)
+        return NS_ERROR_NULL_POINTER;
+
+    NS_PRECONDITION(aProperty != nullptr, "null ptr");
+    if (! aProperty)
+        return NS_ERROR_NULL_POINTER;
+
+    NS_PRECONDITION(aResult != nullptr, "null ptr");
+    if (! aResult)
+        return NS_ERROR_NULL_POINTER;
+
+    InMemoryAssertionEnumeratorImpl* result =
+        new InMemoryAssertionEnumeratorImpl(this, aSource, aProperty,
+                                            nullptr, aTruthValue);
+
+    if (! result)
+        return NS_ERROR_OUT_OF_MEMORY;
+
+    NS_ADDREF(result);
+    *aResult = result;
+
+    return NS_OK;
+}
+
+
+nsresult
+InMemoryDataSource::LockedAssert(nsIRDFResource* aSource,
+                                 nsIRDFResource* aProperty,
+                                 nsIRDFNode* aTarget,
+                                 bool aTruthValue)
+{
+    LogOperation("ASSERT", aSource, aProperty, aTarget, aTruthValue);
+
+    Assertion* next = GetForwardArcs(aSource);
+    Assertion* prev = next;
+    Assertion* as = nullptr;
+
+    bool    haveHash = (next) ? next->mHashEntry : false;
+    if (haveHash) {
+        PLDHashEntryHdr* hdr = next->u.hash.mPropertyHash->Search(aProperty);
+        Assertion* val = hdr ? static_cast<Entry*>(hdr)->mAssertions : nullptr;
+        while (val) {
+            if (val->u.as.mTarget == aTarget) {
+                // Wow, we already had the assertion. Make sure that the
+                // truth values are correct and bail.
+                val->u.as.mTruthValue = aTruthValue;
+                return NS_OK;
+            }
+            val = val->mNext;
+        }
+    }
+    else
+    {
+        while (next) {
+            // check target first as its most unique
+            if (aTarget == next->u.as.mTarget) {
+                if (aProperty == next->u.as.mProperty) {
+                    // Wow, we already had the assertion. Make sure that the
+                    // truth values are correct and bail.
+                    next->u.as.mTruthValue = aTruthValue;
+                    return NS_OK;
+                }
+            }
+
+            prev = next;
+            next = next->mNext;
+        }
+    }
+
+    as = new Assertion(aSource, aProperty, aTarget, aTruthValue);
+    if (! as)
+        return NS_ERROR_OUT_OF_MEMORY;
+
+    // Add the datasource's owning reference.
+    as->AddRef();
+
+    if (haveHash)
+    {
+        PLDHashEntryHdr* hdr = next->u.hash.mPropertyHash->Search(aProperty);
+        Assertion *asRef =
+            hdr ? static_cast<Entry*>(hdr)->mAssertions : nullptr;
+        if (asRef)
+        {
+            as->mNext = asRef->mNext;
+            asRef->mNext = as;
+        }
+        else
+        {
+            hdr = next->u.hash.mPropertyHash->Add(aProperty, mozilla::fallible);
+            if (hdr)
+            {
+                Entry* entry = static_cast<Entry*>(hdr);
+                entry->mNode = aProperty;
+                entry->mAssertions = as;
+            }
+        }
+    }
+    else
+    {
+        // Link it in to the "forward arcs" table
+        if (!prev) {
+            SetForwardArcs(aSource, as);
+        } else {
+            prev->mNext = as;
+        }
+    }
+
+    // Link it in to the "reverse arcs" table
+
+    next = GetReverseArcs(aTarget);
+    as->u.as.mInvNext = next;
+    next = as;
+    SetReverseArcs(aTarget, next);
+
+    return NS_OK;
+}
+
+NS_IMETHODIMP
+InMemoryDataSource::Assert(nsIRDFResource* aSource,
+                           nsIRDFResource* aProperty, 
+                           nsIRDFNode* aTarget,
+                           bool aTruthValue) 
+{
+    NS_PRECONDITION(aSource != nullptr, "null ptr");
+    if (! aSource)
+        return NS_ERROR_NULL_POINTER;
+
+    NS_PRECONDITION(aProperty != nullptr, "null ptr");
+    if (! aProperty)
+        return NS_ERROR_NULL_POINTER;
+
+    NS_PRECONDITION(aTarget != nullptr, "null ptr");
+    if (! aTarget)
+        return NS_ERROR_NULL_POINTER;
+
+    if (mReadCount) {
+        NS_WARNING("Writing to InMemoryDataSource during read\n");
+        return NS_RDF_ASSERTION_REJECTED;
+    }
+
+    nsresult rv;
+    rv = LockedAssert(aSource, aProperty, aTarget, aTruthValue);
+    if (NS_FAILED(rv)) return rv;
+
+    // notify observers
+    for (int32_t i = (int32_t)mNumObservers - 1; mPropagateChanges && i >= 0; --i) {
+        nsIRDFObserver* obs = mObservers[i];
+
+        // XXX this should never happen, but it does, and we can't figure out why.
+        NS_ASSERTION(obs, "observer array corrupted!");
+        if (! obs)
+          continue;
+
+        obs->OnAssert(this, aSource, aProperty, aTarget);
+        // XXX ignore return value?
+    }
+
+    return NS_RDF_ASSERTION_ACCEPTED;
+}
+
+
+nsresult
+InMemoryDataSource::LockedUnassert(nsIRDFResource* aSource,
+                                   nsIRDFResource* aProperty,
+                                   nsIRDFNode* aTarget)
+{
+    LogOperation("UNASSERT", aSource, aProperty, aTarget);
+
+    Assertion* next = GetForwardArcs(aSource);
+    Assertion* prev = next;
+    Assertion* root = next;
+    Assertion* as = nullptr;
+
+    bool    haveHash = (next) ? next->mHashEntry : false;
+    if (haveHash) {
+        PLDHashEntryHdr* hdr = next->u.hash.mPropertyHash->Search(aProperty);
+        prev = next = hdr ? static_cast<Entry*>(hdr)->mAssertions : nullptr;
+        bool first = true;
+        while (next) {
+            if (aTarget == next->u.as.mTarget) {
+                break;
+            }
+            first = false;
+            prev = next;
+            next = next->mNext;
+        }
+        // We don't even have the assertion, so just bail.
+        if (!next)
+            return NS_OK;
+
+        as = next;
+
+        if (first) {
+            root->u.hash.mPropertyHash->RawRemove(hdr);
+
+            if (next && next->mNext) {
+                PLDHashEntryHdr* hdr =
+                    root->u.hash.mPropertyHash->Add(aProperty,
+                                                    mozilla::fallible);
+                if (hdr) {
+                    Entry* entry = static_cast<Entry*>(hdr);
+                    entry->mNode = aProperty;
+                    entry->mAssertions = next->mNext;
+                }
+            }
+            else {
+                // If this second-level hash empties out, clean it up.
+                if (!root->u.hash.mPropertyHash->EntryCount()) {
+                    root->Release();
+                    SetForwardArcs(aSource, nullptr);
+                }
+            }
+        }
+        else {
+            prev->mNext = next->mNext;
+        }
+    }
+    else
+    {
+        while (next) {
+            // check target first as its most unique
+            if (aTarget == next->u.as.mTarget) {
+                if (aProperty == next->u.as.mProperty) {
+                    if (prev == next) {
+                        SetForwardArcs(aSource, next->mNext);
+                    } else {
+                        prev->mNext = next->mNext;
+                    }
+                    as = next;
+                    break;
+                }
+            }
+
+            prev = next;
+            next = next->mNext;
+        }
+    }
+    // We don't even have the assertion, so just bail.
+    if (!as)
+        return NS_OK;
+
+#ifdef DEBUG
+    bool foundReverseArc = false;
+#endif
+
+    next = prev = GetReverseArcs(aTarget);
+    while (next) {
+        if (next == as) {
+            if (prev == next) {
+                SetReverseArcs(aTarget, next->u.as.mInvNext);
+            } else {
+                prev->u.as.mInvNext = next->u.as.mInvNext;
+            }
+#ifdef DEBUG
+            foundReverseArc = true;
+#endif
+            break;
+        }
+        prev = next;
+        next = next->u.as.mInvNext;
+    }
+
+#ifdef DEBUG
+    NS_ASSERTION(foundReverseArc, "in-memory db corrupted: unable to find reverse arc");
+#endif
+
+    // Unlink, and release the datasource's reference
+    as->mNext = as->u.as.mInvNext = nullptr;
+    as->Release();
+
+    return NS_OK;
+}
+
+NS_IMETHODIMP
+InMemoryDataSource::Unassert(nsIRDFResource* aSource,
+                             nsIRDFResource* aProperty,
+                             nsIRDFNode* aTarget)
+{
+    NS_PRECONDITION(aSource != nullptr, "null ptr");
+    if (! aSource)
+        return NS_ERROR_NULL_POINTER;
+
+    NS_PRECONDITION(aProperty != nullptr, "null ptr");
+    if (! aProperty)
+        return NS_ERROR_NULL_POINTER;
+
+    NS_PRECONDITION(aTarget != nullptr, "null ptr");
+    if (! aTarget)
+        return NS_ERROR_NULL_POINTER;
+
+    if (mReadCount) {
+        NS_WARNING("Writing to InMemoryDataSource during read\n");
+        return NS_RDF_ASSERTION_REJECTED;
+    }
+
+    nsresult rv;
+
+    rv = LockedUnassert(aSource, aProperty, aTarget);
+    if (NS_FAILED(rv)) return rv;
+
+    // Notify the world
+    for (int32_t i = int32_t(mNumObservers) - 1; mPropagateChanges && i >= 0; --i) {
+        nsIRDFObserver* obs = mObservers[i];
+
+        // XXX this should never happen, but it does, and we can't figure out why.
+        NS_ASSERTION(obs, "observer array corrupted!");
+        if (! obs)
+          continue;
+
+        obs->OnUnassert(this, aSource, aProperty, aTarget);
+        // XXX ignore return value?
+    }
+
+    return NS_RDF_ASSERTION_ACCEPTED;
+}
+
+
+NS_IMETHODIMP
+InMemoryDataSource::Change(nsIRDFResource* aSource,
+                           nsIRDFResource* aProperty,
+                           nsIRDFNode* aOldTarget,
+                           nsIRDFNode* aNewTarget)
+{
+    NS_PRECONDITION(aSource != nullptr, "null ptr");
+    if (! aSource)
+        return NS_ERROR_NULL_POINTER;
+
+    NS_PRECONDITION(aProperty != nullptr, "null ptr");
+    if (! aProperty)
+        return NS_ERROR_NULL_POINTER;
+
+    NS_PRECONDITION(aOldTarget != nullptr, "null ptr");
+    if (! aOldTarget)
+        return NS_ERROR_NULL_POINTER;
+
+    NS_PRECONDITION(aNewTarget != nullptr, "null ptr");
+    if (! aNewTarget)
+        return NS_ERROR_NULL_POINTER;
+
+    if (mReadCount) {
+        NS_WARNING("Writing to InMemoryDataSource during read\n");
+        return NS_RDF_ASSERTION_REJECTED;
+    }
+
+    nsresult rv;
+
+    // XXX We can implement LockedChange() if we decide that this
+    // is a performance bottleneck.
+
+    rv = LockedUnassert(aSource, aProperty, aOldTarget);
+    if (NS_FAILED(rv)) return rv;
+
+    rv = LockedAssert(aSource, aProperty, aNewTarget, true);
+    if (NS_FAILED(rv)) return rv;
+
+    // Notify the world
+    for (int32_t i = int32_t(mNumObservers) - 1; mPropagateChanges && i >= 0; --i) {
+        nsIRDFObserver* obs = mObservers[i];
+
+        // XXX this should never happen, but it does, and we can't figure out why.
+        NS_ASSERTION(obs, "observer array corrupted!");
+        if (! obs)
+          continue;
+
+        obs->OnChange(this, aSource, aProperty, aOldTarget, aNewTarget);
+        // XXX ignore return value?
+    }
+
+    return NS_RDF_ASSERTION_ACCEPTED;
+}
+
+
+NS_IMETHODIMP
+InMemoryDataSource::Move(nsIRDFResource* aOldSource,
+                         nsIRDFResource* aNewSource,
+                         nsIRDFResource* aProperty,
+                         nsIRDFNode* aTarget)
+{
+    NS_PRECONDITION(aOldSource != nullptr, "null ptr");
+    if (! aOldSource)
+        return NS_ERROR_NULL_POINTER;
+
+    NS_PRECONDITION(aNewSource != nullptr, "null ptr");
+    if (! aNewSource)
+        return NS_ERROR_NULL_POINTER;
+
+    NS_PRECONDITION(aProperty != nullptr, "null ptr");
+    if (! aProperty)
+        return NS_ERROR_NULL_POINTER;
+
+    NS_PRECONDITION(aTarget != nullptr, "null ptr");
+    if (! aTarget)
+        return NS_ERROR_NULL_POINTER;
+
+    if (mReadCount) {
+        NS_WARNING("Writing to InMemoryDataSource during read\n");
+        return NS_RDF_ASSERTION_REJECTED;
+    }
+
+    nsresult rv;
+
+    // XXX We can implement LockedMove() if we decide that this
+    // is a performance bottleneck.
+
+    rv = LockedUnassert(aOldSource, aProperty, aTarget);
+    if (NS_FAILED(rv)) return rv;
+
+    rv = LockedAssert(aNewSource, aProperty, aTarget, true);
+    if (NS_FAILED(rv)) return rv;
+
+    // Notify the world
+    for (int32_t i = int32_t(mNumObservers) - 1; mPropagateChanges && i >= 0; --i) {
+        nsIRDFObserver* obs = mObservers[i];
+
+        // XXX this should never happen, but it does, and we can't figure out why.
+        NS_ASSERTION(obs, "observer array corrupted!");
+        if (! obs)
+          continue;
+
+        obs->OnMove(this, aOldSource, aNewSource, aProperty, aTarget);
+        // XXX ignore return value?
+    }
+
+    return NS_RDF_ASSERTION_ACCEPTED;
+}
+
+
+NS_IMETHODIMP
+InMemoryDataSource::AddObserver(nsIRDFObserver* aObserver)
+{
+    NS_PRECONDITION(aObserver != nullptr, "null ptr");
+    if (! aObserver)
+        return NS_ERROR_NULL_POINTER;
+
+    mObservers.AppendObject(aObserver);
+    mNumObservers = mObservers.Count();
+
+    return NS_OK;
+}
+
+NS_IMETHODIMP
+InMemoryDataSource::RemoveObserver(nsIRDFObserver* aObserver)
+{
+    NS_PRECONDITION(aObserver != nullptr, "null ptr");
+    if (! aObserver)
+        return NS_ERROR_NULL_POINTER;
+
+    mObservers.RemoveObject(aObserver);
+    // note: use Count() instead of just decrementing
+    // in case aObserver wasn't in list, for example
+    mNumObservers = mObservers.Count();
+
+    return NS_OK;
+}
+
+NS_IMETHODIMP 
+InMemoryDataSource::HasArcIn(nsIRDFNode *aNode, nsIRDFResource *aArc, bool *result)
+{
+    Assertion* ass = GetReverseArcs(aNode);
+    while (ass) {
+        nsIRDFResource* elbow = ass->u.as.mProperty;
+        if (elbow == aArc) {
+            *result = true;
+            return NS_OK;
+        }
+        ass = ass->u.as.mInvNext;
+    }
+    *result = false;
+    return NS_OK;
+}
+
+NS_IMETHODIMP
+InMemoryDataSource::HasArcOut(nsIRDFResource *aSource, nsIRDFResource *aArc, bool *result)
+{
+    Assertion* ass = GetForwardArcs(aSource);
+    if (ass && ass->mHashEntry) {
+        PLDHashEntryHdr* hdr = ass->u.hash.mPropertyHash->Search(aArc);
+        Assertion* val = hdr ? static_cast<Entry*>(hdr)->mAssertions : nullptr;
+        if (val) {
+            *result = true;
+            return NS_OK;
+        }
+        ass = ass->mNext;
+    }
+    while (ass) {
+        nsIRDFResource* elbow = ass->u.as.mProperty;
+        if (elbow == aArc) {
+            *result = true;
+            return NS_OK;
+        }
+        ass = ass->mNext;
+    }
+    *result = false;
+    return NS_OK;
+}
+
+NS_IMETHODIMP
+InMemoryDataSource::ArcLabelsIn(nsIRDFNode* aTarget, nsISimpleEnumerator** aResult)
+{
+    NS_PRECONDITION(aTarget != nullptr, "null ptr");
+    if (! aTarget)
+        return NS_ERROR_NULL_POINTER;
+
+    InMemoryArcsEnumeratorImpl* result =
+        new InMemoryArcsEnumeratorImpl(this, nullptr, aTarget);
+
+    if (! result)
+        return NS_ERROR_OUT_OF_MEMORY;
+
+    NS_ADDREF(result);
+    *aResult = result;
+
+    return NS_OK;
+}
+
+NS_IMETHODIMP
+InMemoryDataSource::ArcLabelsOut(nsIRDFResource* aSource, nsISimpleEnumerator** aResult)
+{
+    NS_PRECONDITION(aSource != nullptr, "null ptr");
+    if (! aSource)
+        return NS_ERROR_NULL_POINTER;
+
+    InMemoryArcsEnumeratorImpl* result =
+        new InMemoryArcsEnumeratorImpl(this, aSource, nullptr);
+
+    if (! result)
+        return NS_ERROR_OUT_OF_MEMORY;
+
+    NS_ADDREF(result);
+    *aResult = result;
+
+    return NS_OK;
+}
+
+
+NS_IMETHODIMP
+InMemoryDataSource::GetAllResources(nsISimpleEnumerator** aResult)
+{
+    nsCOMArray<nsIRDFNode> nodes;
+    nodes.SetCapacity(mForwardArcs.EntryCount());
+
+    // Get all of our entries into an nsCOMArray
+    for (auto iter = mForwardArcs.Iter(); !iter.Done(); iter.Next()) {
+        auto entry = static_cast<Entry*>(iter.Get());
+        nodes.AppendObject(entry->mNode);
+    }
+    return NS_NewArrayEnumerator(aResult, nodes);
+}
+
+NS_IMETHODIMP
+InMemoryDataSource::GetAllCmds(nsIRDFResource* source,
+                               nsISimpleEnumerator/*<nsIRDFResource>*/** commands)
+{
+    return(NS_NewEmptyEnumerator(commands));
+}
+
+NS_IMETHODIMP
+InMemoryDataSource::IsCommandEnabled(nsISupports* aSources,
+                                     nsIRDFResource*   aCommand,
+                                     nsISupports* aArguments,
+                                     bool* aResult)
+{
+    return NS_ERROR_NOT_IMPLEMENTED;
+}
+
+NS_IMETHODIMP
+InMemoryDataSource::DoCommand(nsISupports* aSources,
+                              nsIRDFResource*   aCommand,
+                              nsISupports* aArguments)
+{
+    return NS_ERROR_NOT_IMPLEMENTED;
+}
+
+NS_IMETHODIMP
+InMemoryDataSource::BeginUpdateBatch()
+{
+    for (int32_t i = int32_t(mNumObservers) - 1; mPropagateChanges && i >= 0; --i) {
+        nsIRDFObserver* obs = mObservers[i];
+        obs->OnBeginUpdateBatch(this);
+    }
+    return NS_OK;
+}
+
+NS_IMETHODIMP
+InMemoryDataSource::EndUpdateBatch()
+{
+    for (int32_t i = int32_t(mNumObservers) - 1; mPropagateChanges && i >= 0; --i) {
+        nsIRDFObserver* obs = mObservers[i];
+        obs->OnEndUpdateBatch(this);
+    }
+    return NS_OK;
+}
+
+
+
+////////////////////////////////////////////////////////////////////////
+// nsIRDFInMemoryDataSource methods
+
+NS_IMETHODIMP
+InMemoryDataSource::EnsureFastContainment(nsIRDFResource* aSource)
+{
+    Assertion *as = GetForwardArcs(aSource);
+    bool    haveHash = (as) ? as->mHashEntry : false;
+
+    // if its already a hash, then nothing to do
+    if (haveHash)   return(NS_OK);
+
+    // convert aSource in forward hash into a hash
+    Assertion *hashAssertion = new Assertion(aSource);
+    NS_ASSERTION(hashAssertion, "unable to create Assertion");
+    if (!hashAssertion) return(NS_ERROR_OUT_OF_MEMORY);
+
+    // Add the datasource's owning reference.
+    hashAssertion->AddRef();
+
+    Assertion *first = GetForwardArcs(aSource);
+    SetForwardArcs(aSource, hashAssertion);
+
+    // mutate references of existing forward assertions into this hash
+    PLDHashTable *table = hashAssertion->u.hash.mPropertyHash;
+    Assertion *nextRef;
+    while(first) {
+        nextRef = first->mNext;
+        nsIRDFResource *prop = first->u.as.mProperty;
+
+        PLDHashEntryHdr* hdr = table->Search(prop);
+        Assertion* val = hdr ? static_cast<Entry*>(hdr)->mAssertions : nullptr;
+        if (val) {
+            first->mNext = val->mNext;
+            val->mNext = first;
+        }
+        else {
+            PLDHashEntryHdr* hdr = table->Add(prop, mozilla::fallible);
+            if (hdr) {
+                Entry* entry = static_cast<Entry*>(hdr);
+                entry->mNode = prop;
+                entry->mAssertions = first;
+                first->mNext = nullptr;
+            }
+        }
+        first = nextRef;
+    }
+    return(NS_OK);
+}
+
+
+////////////////////////////////////////////////////////////////////////
+// nsIRDFPropagatableDataSource methods
+NS_IMETHODIMP
+InMemoryDataSource::GetPropagateChanges(bool* aPropagateChanges)
+{
+    *aPropagateChanges = mPropagateChanges;
+    return NS_OK;
+}
+
+NS_IMETHODIMP
+InMemoryDataSource::SetPropagateChanges(bool aPropagateChanges)
+{
+    mPropagateChanges = aPropagateChanges;
+    return NS_OK;
+}
+
+
+////////////////////////////////////////////////////////////////////////
+// nsIRDFPurgeableDataSource methods
+
+NS_IMETHODIMP
+InMemoryDataSource::Mark(nsIRDFResource* aSource,
+                         nsIRDFResource* aProperty,
+                         nsIRDFNode* aTarget,
+                         bool aTruthValue,
+                         bool* aDidMark)
+{
+    NS_PRECONDITION(aSource != nullptr, "null ptr");
+    if (! aSource)
+        return NS_ERROR_NULL_POINTER;
+
+    NS_PRECONDITION(aProperty != nullptr, "null ptr");
+    if (! aProperty)
+        return NS_ERROR_NULL_POINTER;
+
+    NS_PRECONDITION(aTarget != nullptr, "null ptr");
+    if (! aTarget)
+        return NS_ERROR_NULL_POINTER;
+
+    Assertion *as = GetForwardArcs(aSource);
+    if (as && as->mHashEntry) {
+        PLDHashEntryHdr* hdr = as->u.hash.mPropertyHash->Search(aProperty);
+        Assertion* val = hdr ? static_cast<Entry*>(hdr)->mAssertions : nullptr;
+        while (val) {
+            if ((val->u.as.mTarget == aTarget) &&
+                (aTruthValue == (val->u.as.mTruthValue))) {
+
+                // found it! so mark it.
+                as->Mark();
+                *aDidMark = true;
+
+                LogOperation("MARK", aSource, aProperty, aTarget, aTruthValue);
+
+                return NS_OK;
+            }
+            val = val->mNext;
+        }
+    }
+    else for (; as != nullptr; as = as->mNext) {
+        // check target first as its most unique
+        if (aTarget != as->u.as.mTarget)
+            continue;
+
+        if (aProperty != as->u.as.mProperty)
+            continue;
+
+        if (aTruthValue != (as->u.as.mTruthValue))
+            continue;
+
+        // found it! so mark it.
+        as->Mark();
+        *aDidMark = true;
+
+        LogOperation("MARK", aSource, aProperty, aTarget, aTruthValue);
+
+        return NS_OK;
+    }
+
+    // If we get here, we couldn't find the assertion
+    *aDidMark = false;
+    return NS_OK;
+}
+
+NS_IMETHODIMP
+InMemoryDataSource::Sweep()
+{
+    SweepInfo info = { nullptr, &mReverseArcs };
+
+    // Remove all the assertions, but don't notify anyone.
+    SweepForwardArcsEntries(&mForwardArcs, &info);
+
+    // Now do the notification.
+    Assertion* as = info.mUnassertList;
+    while (as) {
+        LogOperation("SWEEP", as->mSource, as->u.as.mProperty, as->u.as.mTarget, as->u.as.mTruthValue);
+        if (!(as->mHashEntry))
+        {
+            for (int32_t i = int32_t(mNumObservers) - 1; mPropagateChanges && i >= 0; --i) {
+                nsIRDFObserver* obs = mObservers[i];
+                // XXXbz other loops over mObservers null-check |obs| here!
+                obs->OnUnassert(this, as->mSource, as->u.as.mProperty, as->u.as.mTarget);
+                // XXX ignore return value?
+            }
+        }
+
+        Assertion* doomed = as;
+        as = as->mNext;
+
+        // Unlink, and release the datasource's reference
+        doomed->mNext = doomed->u.as.mInvNext = nullptr;
+        doomed->Release();
+    }
+
+    return NS_OK;
+}
+
+
+void
+InMemoryDataSource::SweepForwardArcsEntries(PLDHashTable* aTable,
+                                            SweepInfo* aInfo)
+{
+    for (auto iter = aTable->Iter(); !iter.Done(); iter.Next()) {
+        auto entry = static_cast<Entry*>(iter.Get());
+
+        Assertion* as = entry->mAssertions;
+        if (as && (as->mHashEntry)) {
+            // Stuff in sub-hashes must be swept recursively (max depth: 1)
+            SweepForwardArcsEntries(as->u.hash.mPropertyHash, aInfo);
+
+            // If the sub-hash is now empty, clean it up.
+            if (!as->u.hash.mPropertyHash->EntryCount()) {
+                as->Release();
+                iter.Remove();
+            }
+            continue;
+        }
+
+        Assertion* prev = nullptr;
+        while (as) {
+            if (as->IsMarked()) {
+                prev = as;
+                as->Unmark();
+                as = as->mNext;
+            }
+            else {
+                // remove from the list of assertions in the datasource
+                Assertion* next = as->mNext;
+                if (prev) {
+                    prev->mNext = next;
+                }
+                else {
+                    // it's the first one. update the hashtable entry.
+                    entry->mAssertions = next;
+                }
+
+                // remove from the reverse arcs
+                PLDHashEntryHdr* hdr =
+                    aInfo->mReverseArcs->Search(as->u.as.mTarget);
+                NS_ASSERTION(hdr, "no assertion in reverse arcs");
+
+                Entry* rentry = static_cast<Entry*>(hdr);
+                Assertion* ras = rentry->mAssertions;
+                Assertion* rprev = nullptr;
+                while (ras) {
+                    if (ras == as) {
+                        if (rprev) {
+                            rprev->u.as.mInvNext = ras->u.as.mInvNext;
+                        }
+                        else {
+                            // it's the first one. update the hashtable entry.
+                            rentry->mAssertions = ras->u.as.mInvNext;
+                        }
+                        as->u.as.mInvNext = nullptr; // for my sanity.
+                        break;
+                    }
+                    rprev = ras;
+                    ras = ras->u.as.mInvNext;
+                }
+
+                // Wow, it was the _only_ one. Unhash it.
+                if (! rentry->mAssertions) {
+                    aInfo->mReverseArcs->RawRemove(hdr);
+                }
+
+                // add to the list of assertions to unassert
+                as->mNext = aInfo->mUnassertList;
+                aInfo->mUnassertList = as;
+
+                // Advance to the next assertion
+                as = next;
+            }
+        }
+
+        // if no more assertions exist for this resource, then unhash it.
+        if (! entry->mAssertions) {
+            iter.Remove();
+        }
+    }
+}
+
+////////////////////////////////////////////////////////////////////////
+// rdfIDataSource methods
+
+NS_IMETHODIMP
+InMemoryDataSource::VisitAllSubjects(rdfITripleVisitor *aVisitor)
+{
+    // Lock datasource against writes
+    ++mReadCount;
+
+    // Enumerate all of our entries.
+    nsresult rv = NS_OK;
+    for (auto iter = mForwardArcs.Iter(); !iter.Done(); iter.Next()) {
+        auto entry = static_cast<Entry*>(iter.Get());
+        nsresult rv2;
+        nsCOMPtr<nsIRDFNode> subject = do_QueryInterface(entry->mNode, &rv2);
+        if (NS_FAILED(rv2)) {
+            NS_WARNING("QI to nsIRDFNode failed");
+            continue;
+        }
+        rv = aVisitor->Visit(subject, nullptr, nullptr, true);
+        if (NS_FAILED(rv) || rv == NS_RDF_STOP_VISIT) {
+            break;
+        }
+    }
+
+    // Unlock datasource
+    --mReadCount;
+
+    return rv;
+}
+
+NS_IMETHODIMP
+InMemoryDataSource::VisitAllTriples(rdfITripleVisitor *aVisitor)
+{
+    // Lock datasource against writes
+    ++mReadCount;
+
+    // Enumerate all of our entries.
+    nsresult rv = NS_OK;
+    for (auto iter = mForwardArcs.Iter(); !iter.Done(); iter.Next()) {
+        auto entry = static_cast<Entry*>(iter.Get());
+
+        nsresult rv2;
+        nsCOMPtr<nsIRDFNode> subject = do_QueryInterface(entry->mNode, &rv2);
+        if (NS_FAILED(rv2)) {
+            NS_WARNING("QI to nsIRDFNode failed");
+
+        } else if (entry->mAssertions->mHashEntry) {
+            for (auto iter = entry->mAssertions->u.hash.mPropertyHash->Iter();
+                 !iter.Done();
+                 iter.Next()) {
+                auto entry = static_cast<Entry*>(iter.Get());
+                Assertion* assertion = entry->mAssertions;
+                while (assertion) {
+                    NS_ASSERTION(!assertion->mHashEntry, "shouldn't have to hashes");
+                    rv = aVisitor->Visit(subject, assertion->u.as.mProperty,
+                                                  assertion->u.as.mTarget,
+                                                  assertion->u.as.mTruthValue);
+                    if (NS_FAILED(rv)) {
+                        goto end;
+                    }
+                    if (rv == NS_RDF_STOP_VISIT) {
+                        goto inner_end;
+                    }
+                    assertion = assertion->mNext;
+                }
+            }
+
+        } else {
+            Assertion* assertion = entry->mAssertions;
+            while (assertion) {
+                NS_ASSERTION(!assertion->mHashEntry, "shouldn't have to hashes");
+                rv = aVisitor->Visit(subject, assertion->u.as.mProperty,
+                                              assertion->u.as.mTarget,
+                                              assertion->u.as.mTruthValue);
+                if (NS_FAILED(rv) || rv == NS_RDF_STOP_VISIT) {
+                    goto end;
+                }
+                assertion = assertion->mNext;
+            }
+        }
+
+      inner_end:
+        (void) 0;
+    }
+
+  end:
+    // Unlock datasource
+    --mReadCount;
+
+    return rv;
+} 
+
+////////////////////////////////////////////////////////////////////////
+