Merge of QAR-1383 event-system-7 into trunk.

svn merge -r 121797:121853 svn+ssh://svn.lindenlab.com/svn/linden/branches/merge-event-system-7

1 files changed, 779 insertions, 0 deletions

diff --git a/indra/llcommon/lldependencies.h b/indra/llcommon/lldependencies.h
new file mode 100644
index 0000000000..bd4bd7c96a
--- /dev/null
+++ b/indra/llcommon/lldependencies.h
@@ -0,0 +1,779 @@
+/**
+ * @file   lldependencies.h
+ * @author Nat Goodspeed
+ * @date   2008-09-17
+ * @brief  LLDependencies: a generic mechanism for expressing "b must follow a,
+ *         but precede c"
+ *
+ * $LicenseInfo:firstyear=2008&license=viewergpl$
+ * Copyright (c) 2008, Linden Research, Inc.
+ * $/LicenseInfo$
+ */
+
+#if ! defined(LL_LLDEPENDENCIES_H)
+#define LL_LLDEPENDENCIES_H
+
+#include <string>
+#include <vector>
+#include <set>
+#include <map>
+#include <stdexcept>
+#include <iosfwd>
+#include <boost/iterator/transform_iterator.hpp>
+#include <boost/iterator/indirect_iterator.hpp>
+#include <boost/range/iterator_range.hpp>
+#include <boost/function.hpp>
+#include <boost/bind.hpp>
+
+/*****************************************************************************
+*   Utilities
+*****************************************************************************/
+/**
+ * generic range transformer: given a range acceptable to Boost.Range (e.g. a
+ * standard container, an iterator pair, ...) and a unary function to apply to
+ * each element of the range, make a corresponding range that lazily applies
+ * that function to each element on dereferencing.
+ */
+template<typename FUNCTION, typename RANGE>
+inline
+boost::iterator_range<boost::transform_iterator<FUNCTION,
+                                                typename boost::range_const_iterator<RANGE>::type> >
+make_transform_range(const RANGE& range, FUNCTION function)
+{
+    // shorthand for the iterator type embedded in our return type
+    typedef boost::transform_iterator<FUNCTION, typename boost::range_const_iterator<RANGE>::type>
+        transform_iterator;
+    return boost::make_iterator_range(transform_iterator(boost::begin(range), function),
+                                      transform_iterator(boost::end(range),   function));
+}
+
+/// non-const version of make_transform_range()
+template<typename FUNCTION, typename RANGE>
+inline
+boost::iterator_range<boost::transform_iterator<FUNCTION,
+                                                typename boost::range_iterator<RANGE>::type> >
+make_transform_range(RANGE& range, FUNCTION function)
+{
+    // shorthand for the iterator type embedded in our return type
+    typedef boost::transform_iterator<FUNCTION, typename boost::range_iterator<RANGE>::type>
+        transform_iterator;
+    return boost::make_iterator_range(transform_iterator(boost::begin(range), function),
+                                      transform_iterator(boost::end(range),   function));
+}
+
+/**
+ * From any range compatible with Boost.Range, instantiate any class capable
+ * of accepting an iterator pair.
+ */
+template<class TYPE>
+struct instance_from_range: public TYPE
+{
+    template<typename RANGE>
+    instance_from_range(RANGE range):
+        TYPE(boost::begin(range), boost::end(range))
+    {}
+};
+
+/*****************************************************************************
+*   LLDependencies
+*****************************************************************************/
+/**
+ * LLDependencies components that should not be reinstantiated for each KEY,
+ * NODE specialization
+ */
+class LLDependenciesBase
+{
+public:
+    virtual ~LLDependenciesBase() {}
+
+    /**
+     * Exception thrown by sort() if there's a cycle
+     */
+    struct Cycle: public std::runtime_error
+    {
+        Cycle(const std::string& what): std::runtime_error(what) {}
+    };
+
+    /**
+     * Provide a short description of this LLDependencies instance on the
+     * specified output stream, assuming that its KEY type has an operator<<()
+     * that works with std::ostream.
+     *
+     * Pass @a full as @c false to omit any keys without dependency constraints.
+     */
+    virtual std::ostream& describe(std::ostream& out, bool full=true) const;
+
+    /// describe() to a string
+    virtual std::string describe(bool full=true) const;
+
+protected:
+    typedef std::vector< std::pair<int, int> > EdgeList;
+    typedef std::vector<int> VertexList;
+    VertexList topo_sort(int vertices, const EdgeList& edges) const;
+
+    /**
+     * refpair is specifically intended to capture a pair of references. This
+     * is better than std::pair<T1&, T2&> because some implementations of
+     * std::pair's ctor accept const references to the two types. If the
+     * types are themselves references, this results in an illegal reference-
+     * to-reference.
+     */
+    template<typename T1, typename T2>
+    struct refpair
+    {
+        refpair(T1 value1, T2 value2):
+            first(value1),
+            second(value2)
+        {}
+        T1 first;
+        T2 second;
+    };
+};
+
+/// describe() helper: for most types, report the type as usual
+template<typename T>
+inline
+std::ostream& LLDependencies_describe(std::ostream& out, const T& key)
+{
+    out << key;
+    return out;
+}
+
+/// specialize LLDependencies_describe() for std::string
+template<>
+inline
+std::ostream& LLDependencies_describe(std::ostream& out, const std::string& key)
+{
+    out << '"' << key << '"';
+    return out;
+}
+
+/**
+ * It's reasonable to use LLDependencies in a keys-only way, more or less like
+ * std::set. For that case, the default NODE type is an empty struct.
+ */
+struct LLDependenciesEmpty
+{
+    LLDependenciesEmpty() {}
+    /**
+     * Give it a constructor accepting void* so caller can pass placeholder
+     * values such as NULL or 0 rather than having to write
+     * LLDependenciesEmpty().
+     */
+    LLDependenciesEmpty(void*) {}    
+};
+
+/**
+ * This class manages abstract dependencies between node types of your
+ * choosing. As with a std::map, nodes are copied when add()ed, so the node
+ * type should be relatively lightweight; to manipulate dependencies between
+ * expensive objects, use a pointer type.
+ *
+ * For a given node, you may state the keys of nodes that must precede it
+ * and/or nodes that must follow it. The sort() method will produce an order
+ * that should work, or throw an exception if the constraints are impossible.
+ * We cache results to minimize the cost of repeated sort() calls.
+ */
+template<typename KEY = std::string,
+         typename NODE = LLDependenciesEmpty>
+class LLDependencies: public LLDependenciesBase
+{
+    typedef LLDependencies<KEY, NODE> self_type;
+
+    /**
+     * Internally, we bundle the client's NODE with its before/after keys.
+     */
+    struct DepNode
+    {
+        typedef std::set<KEY> dep_set;
+        DepNode(const NODE& node_, const dep_set& after_, const dep_set& before_):
+            node(node_),
+            after(after_),
+            before(before_)
+        {}
+        NODE node;
+        dep_set after, before;    
+    };
+    typedef std::map<KEY, DepNode> DepNodeMap;
+    typedef typename DepNodeMap::value_type DepNodeMapEntry;
+
+    /// We have various ways to get the dependencies for a given DepNode.
+    /// Rather than having to restate each one for 'after' and 'before'
+    /// separately, pass a dep_selector so we can apply each to either.
+    typedef boost::function<const typename DepNode::dep_set&(const DepNode&)> dep_selector;
+
+public:
+    LLDependencies() {}
+
+    typedef KEY key_type;
+    typedef NODE node_type;
+
+    /// param type used to express lists of other node keys -- note that such
+    /// lists can be initialized with boost::assign::list_of()
+    typedef std::vector<KEY> KeyList;
+
+    /**
+     * Add a new node. State its dependencies on other nodes (which may not
+     * yet have been added) by listing the keys of nodes this new one must
+     * follow, and separately the keys of nodes this new one must precede.
+     *
+     * The node you pass is @em copied into an internal data structure. If you
+     * want to modify the node value after add()ing it, capture the returned
+     * NODE& reference.
+     *
+     * @note
+     * Actual dependency analysis is deferred to the sort() method, so 
+     * you can add an arbitrary number of nodes without incurring analysis
+     * overhead for each. The flip side of this is that add()ing nodes that
+     * define a cycle leaves this object in a state in which sort() will
+     * always throw the Cycle exception.
+     *
+     * Two distinct use cases are anticipated:
+     * * The data used to load this object are completely known at compile
+     * time (e.g. LLEventPump listener names). A Cycle exception represents a
+     * bug which can be corrected by the coder. The program need neither catch
+     * Cycle nor attempt to salvage the state of this object.
+     * * The data are loaded at runtime, therefore the universe of
+     * dependencies cannot be known at compile time. The client code should
+     * catch Cycle.
+     * ** If a Cycle exception indicates fatally-flawed input data, this
+     * object can simply be discarded, possibly with the entire program run.
+     * ** If it is essential to restore this object to a working state, the
+     * simplest workaround is to remove() nodes in LIFO order.
+     * *** It may be useful to add functionality to this class to track the
+     * add() chronology, providing a pop() method to remove the most recently
+     * added node.
+     * *** It may further be useful to add a restore() method which would
+     * pop() until sort() no longer throws Cycle. This method would be
+     * expensive -- but it's not clear that client code could resolve the
+     * problem more cheaply.
+     */
+    NODE& add(const KEY& key, const NODE& node = NODE(),
+              const KeyList& after = KeyList(),
+              const KeyList& before = KeyList())
+    {
+        // Get the passed-in lists as sets for equality comparison
+        typename DepNode::dep_set
+            after_set(after.begin(), after.end()),
+            before_set(before.begin(), before.end());
+        // Try to insert the new node; if it already exists, find the old
+        // node instead.
+        std::pair<typename DepNodeMap::iterator, bool> inserted =
+            mNodes.insert(typename DepNodeMap::value_type(key,
+                                                          DepNode(node, after_set, before_set)));
+        if (! inserted.second)      // bool indicating success of insert()
+        {
+            // We already have a node by this name. Have its dependencies
+            // changed? If the existing node's dependencies are identical, the
+            // result will be unchanged, so we can leave the cache intact.
+            // Regardless of inserted.second, inserted.first is the iterator
+            // to the newly-inserted (or existing) map entry. Of course, that
+            // entry's second is the DepNode of interest.
+            if (inserted.first->second.after  != after_set ||
+                inserted.first->second.before != before_set)
+            {
+                // Dependencies have changed: clear the cached result.
+                mCache.clear();
+                // save the new dependencies
+                inserted.first->second.after  = after_set;
+                inserted.first->second.before = before_set;
+            }
+        }
+        else                        // this node is new
+        {
+            // This will change results.
+            mCache.clear();
+        }
+        return inserted.first->second.node;
+    }
+
+    /// the value of an iterator, showing both KEY and its NODE
+    typedef refpair<const KEY&, NODE&> value_type;
+    /// the value of a const_iterator
+    typedef refpair<const KEY&, const NODE&> const_value_type;
+
+private:
+    // Extract functors
+    static value_type value_extract(DepNodeMapEntry& entry)
+    {
+        return value_type(entry.first, entry.second.node);
+    }
+
+    static const_value_type const_value_extract(const DepNodeMapEntry& entry)
+    {
+        return const_value_type(entry.first, entry.second.node);
+    }
+
+    // All the iterator access methods return iterator ranges just to cut down
+    // on the friggin' boilerplate!!
+
+    /// generic mNodes range method
+    template<typename ITERATOR, typename FUNCTION>
+    boost::iterator_range<ITERATOR> generic_range(FUNCTION function)
+    {
+        return make_transform_range(mNodes, function);
+    }
+
+    /// generic mNodes const range method
+    template<typename ITERATOR, typename FUNCTION>
+    boost::iterator_range<ITERATOR> generic_range(FUNCTION function) const
+    {
+        return make_transform_range(mNodes, function);
+    }
+
+public:
+    /// iterator over value_type entries
+    typedef boost::transform_iterator<boost::function<value_type(DepNodeMapEntry&)>,
+                                      typename DepNodeMap::iterator> iterator;
+    /// range over value_type entries
+    typedef boost::iterator_range<iterator> range;
+
+    /// iterate over value_type <i>in @c KEY order</i> rather than dependency order
+    range get_range()
+    {
+        return generic_range<iterator>(value_extract);
+    }
+
+    /// iterator over const_value_type entries
+    typedef boost::transform_iterator<boost::function<const_value_type(const DepNodeMapEntry&)>,
+                                      typename DepNodeMap::const_iterator> const_iterator;
+    /// range over const_value_type entries
+    typedef boost::iterator_range<const_iterator> const_range;
+
+    /// iterate over const_value_type <i>in @c KEY order</i> rather than dependency order
+    const_range get_range() const
+    {
+        return generic_range<const_iterator>(const_value_extract);
+    }
+
+    /// iterator over stored NODEs
+    typedef boost::transform_iterator<boost::function<NODE&(DepNodeMapEntry&)>,
+                                      typename DepNodeMap::iterator> node_iterator;
+    /// range over stored NODEs
+    typedef boost::iterator_range<node_iterator> node_range;
+
+    /// iterate over NODE <i>in @c KEY order</i> rather than dependency order
+    node_range get_node_range()
+    {
+        // First take a DepNodeMapEntry and extract a reference to its
+        // DepNode, then from that extract a reference to its NODE.
+        return generic_range<node_iterator>(
+            boost::bind<NODE&>(&DepNode::node,
+                               boost::bind<DepNode&>(&DepNodeMapEntry::second, _1)));
+    }
+
+    /// const iterator over stored NODEs
+    typedef boost::transform_iterator<boost::function<const NODE&(const DepNodeMapEntry&)>,
+                                      typename DepNodeMap::const_iterator> const_node_iterator;
+    /// const range over stored NODEs
+    typedef boost::iterator_range<const_node_iterator> const_node_range;
+
+    /// iterate over const NODE <i>in @c KEY order</i> rather than dependency order
+    const_node_range get_node_range() const
+    {
+        // First take a DepNodeMapEntry and extract a reference to its
+        // DepNode, then from that extract a reference to its NODE.
+        return generic_range<const_node_iterator>(
+            boost::bind<const NODE&>(&DepNode::node,
+                                     boost::bind<const DepNode&>(&DepNodeMapEntry::second, _1)));
+    }
+
+    /// const iterator over stored KEYs
+    typedef boost::transform_iterator<boost::function<const KEY&(const DepNodeMapEntry&)>,
+                                      typename DepNodeMap::const_iterator> const_key_iterator;
+    /// const range over stored KEYs
+    typedef boost::iterator_range<const_key_iterator> const_key_range;
+    // We don't provide a non-const iterator over KEYs because they should be
+    // immutable, and in fact our underlying std::map won't give us non-const
+    // references.
+
+    /// iterate over const KEY <i>in @c KEY order</i> rather than dependency order
+    const_key_range get_key_range() const
+    {
+        // From a DepNodeMapEntry, extract a reference to its KEY.
+        return generic_range<const_key_iterator>(
+            boost::bind<const KEY&>(&DepNodeMapEntry::first, _1));
+    }
+
+    /**
+     * Find an existing NODE, or return NULL. We decided to avoid providing a
+     * method analogous to std::map::find(), for a couple of reasons:
+     *
+     * * For a find-by-key, getting back an iterator to the (key, value) pair
+     * is less than useful, since you already have the key in hand.
+     * * For a failed request, comparing to end() is problematic. First, we
+     * provide range accessors, so it's more code to get end(). Second, we
+     * provide a number of different ranges -- quick, to which one's end()
+     * should we compare the iterator returned by find()?
+     *
+     * The returned pointer is solely to allow expressing the not-found
+     * condition. LLDependencies still owns the found NODE.
+     */
+    const NODE* get(const KEY& key) const
+    {
+        typename DepNodeMap::const_iterator found = mNodes.find(key);
+        if (found != mNodes.end())
+        {
+            return &found->second.node;
+        }
+        return NULL;
+    }
+
+    /**
+     * non-const get()
+     */
+    NODE* get(const KEY& key)
+    {
+        // Use const implementation, then cast away const-ness of return
+        return const_cast<NODE*>(const_cast<const self_type*>(this)->get(key));
+    }
+
+    /**
+     * Remove a node with specified key. This operation is the major reason
+     * we rebuild the graph on the fly instead of storing it.
+     */
+    bool remove(const KEY& key)
+    {
+        typename DepNodeMap::iterator found = mNodes.find(key);
+        if (found != mNodes.end())
+        {
+            mNodes.erase(found);
+            return true;
+        }
+        return false;
+    }
+
+private:
+    /// cached list of iterators
+    typedef std::vector<iterator> iterator_list;
+    typedef typename iterator_list::iterator iterator_list_iterator;
+
+public:
+    /**
+     * The return type of the sort() method needs some explanation. Provide a
+     * public typedef to facilitate storing the result.
+     *
+     * * We will prepare mCache by looking up DepNodeMap iterators.
+     * * We want to return a range containing iterators that will walk mCache.
+     * * If we simply stored DepNodeMap iterators and returned
+     * (mCache.begin(), mCache.end()), dereferencing each iterator would
+     * obtain a DepNodeMap iterator.
+     * * We want the caller to loop over @c value_type: pair<KEY, NODE>.
+     * * This requires two transformations:
+     * ** mCache must contain @c LLDependencies::iterator so that
+     * dereferencing each entry will obtain an @c LLDependencies::value_type
+     * rather than a DepNodeMapEntry.
+     * ** We must wrap mCache's iterators in boost::indirect_iterator so that
+     * dereferencing one of our returned iterators will also dereference the
+     * iterator contained in mCache.
+     */
+    typedef boost::iterator_range<boost::indirect_iterator<iterator_list_iterator> > sorted_range;
+    /// for convenience in looping over a sorted_range
+    typedef typename sorted_range::iterator sorted_iterator;
+
+    /**
+     * Once we've loaded in the dependencies of interest, arrange them into an
+     * order that works -- or throw Cycle exception.
+     *
+     * Return an iterator range over (key, node) pairs that traverses them in
+     * the desired order.
+     */
+    sorted_range sort() const
+    {
+        // Changes to mNodes cause us to clear our cache, so empty mCache
+        // means it's invalid and should be recomputed. However, if mNodes is
+        // also empty, then an empty mCache represents a valid order, so don't
+        // bother sorting.
+        if (mCache.empty() && ! mNodes.empty())
+        {
+            // Construct a map of node keys to distinct vertex numbers -- even for
+            // nodes mentioned only in before/after constraints, that haven't yet
+            // been explicitly added. Rely on std::map rejecting a second attempt
+            // to insert the same key. Use the map's size() as the vertex number
+            // to get a distinct value for each successful insertion.
+            typedef std::map<KEY, int> VertexMap;
+            VertexMap vmap;
+            // Nest each of these loops because !@#$%? MSVC warns us that its
+            // former broken behavior has finally been fixed -- and our builds
+            // treat warnings as errors.
+            {
+                for (typename DepNodeMap::const_iterator nmi = mNodes.begin(), nmend = mNodes.end();
+                     nmi != nmend; ++nmi)
+                {
+                    vmap.insert(typename VertexMap::value_type(nmi->first, vmap.size()));
+                    for (typename DepNode::dep_set::const_iterator ai = nmi->second.after.begin(),
+                                                                   aend = nmi->second.after.end();
+                         ai != aend; ++ai)
+                    {
+                        vmap.insert(typename VertexMap::value_type(*ai, vmap.size()));
+                    }
+                    for (typename DepNode::dep_set::const_iterator bi = nmi->second.before.begin(),
+                                                                   bend = nmi->second.before.end();
+                         bi != bend; ++bi)
+                    {
+                        vmap.insert(typename VertexMap::value_type(*bi, vmap.size()));
+                    }
+                }
+            }
+            // Define the edges. For this we must traverse mNodes again, mapping
+            // all the known key dependencies to integer pairs.
+            EdgeList edges;
+            {
+                for (typename DepNodeMap::const_iterator nmi = mNodes.begin(), nmend = mNodes.end();
+                     nmi != nmend; ++nmi)
+                {
+                    int thisnode = vmap[nmi->first];
+                    // after dependencies: build edges from the named node to this one
+                    for (typename DepNode::dep_set::const_iterator ai = nmi->second.after.begin(),
+                                                                   aend = nmi->second.after.end();
+                         ai != aend; ++ai)
+                    {
+                        edges.push_back(EdgeList::value_type(vmap[*ai], thisnode));
+                    }
+                    // before dependencies: build edges from this node to the
+                    // named one
+                    for (typename DepNode::dep_set::const_iterator bi = nmi->second.before.begin(),
+                                                                   bend = nmi->second.before.end();
+                         bi != bend; ++bi)
+                    {
+                        edges.push_back(EdgeList::value_type(thisnode, vmap[*bi]));
+                    }
+                }
+            }
+            // Hide the gory details of our topological sort, since they shouldn't
+            // get reinstantiated for each distinct NODE type.
+            VertexList sorted(topo_sort(vmap.size(), edges));
+            // Build the reverse of vmap to look up the key for each vertex
+            // descriptor. vmap contains exactly one entry for each distinct key,
+            // and we're certain that the associated int values are distinct
+            // indexes. The fact that they're not in order is irrelevant.
+            KeyList vkeys(vmap.size());
+            for (typename VertexMap::const_iterator vmi = vmap.begin(), vmend = vmap.end();
+                 vmi != vmend; ++vmi)
+            {
+                vkeys[vmi->second] = vmi->first;
+            }
+            // Walk the sorted output list, building the result into mCache so
+            // we'll have it next time someone asks.
+            mCache.clear();
+            for (VertexList::const_iterator svi = sorted.begin(), svend = sorted.end();
+                 svi != svend; ++svi)
+            {
+                // We're certain that vkeys[*svi] exists. However, there might not
+                // yet be a corresponding entry in mNodes.
+                self_type* non_const_this(const_cast<self_type*>(this));
+                typename DepNodeMap::iterator found = non_const_this->mNodes.find(vkeys[*svi]);
+                if (found != non_const_this->mNodes.end())
+                {
+                    // Make an iterator of appropriate type.
+                    mCache.push_back(iterator(found, value_extract));
+                }
+            }
+        }
+        // Whether or not we've just recomputed mCache, it should now contain
+        // the results we want. Return a range of indirect_iterators over it
+        // so that dereferencing a returned iterator will dereference the
+        // iterator stored in mCache and directly reference the (key, node)
+        // pair.
+        boost::indirect_iterator<iterator_list_iterator>
+            begin(mCache.begin()),
+            end(mCache.end());
+        return sorted_range(begin, end);
+    }
+
+    /// Override base-class describe() with actual implementation
+    virtual std::ostream& describe(std::ostream& out, bool full=true) const
+    {
+        typename DepNodeMap::const_iterator dmi(mNodes.begin()), dmend(mNodes.end());
+        if (dmi != dmend)
+        {
+            std::string sep;
+            describe(out, sep, *dmi, full);
+            while (++dmi != dmend)
+            {
+                describe(out, sep, *dmi, full);
+            }
+        }
+        return out;
+    }
+
+    /// describe() helper: report a DepNodeEntry
+    static std::ostream& describe(std::ostream& out, std::string& sep,
+                                  const DepNodeMapEntry& entry, bool full)
+    {
+        // If we were asked for a full report, describe every node regardless
+        // of whether it has dependencies. If we were asked to suppress
+        // independent nodes, describe this one if either after or before is
+        // non-empty.
+        if (full || (! entry.second.after.empty()) || (! entry.second.before.empty()))
+        {
+            out << sep;
+            sep = "\n";
+            if (! entry.second.after.empty())
+            {
+                out << "after ";
+                describe(out, entry.second.after);
+                out << " -> ";
+            }
+            LLDependencies_describe(out, entry.first);
+            if (! entry.second.before.empty())
+            {
+                out << " -> before ";
+                describe(out, entry.second.before);
+            }
+        }
+        return out;
+    }
+
+    /// describe() helper: report a dep_set
+    static std::ostream& describe(std::ostream& out, const typename DepNode::dep_set& keys)
+    {
+        out << '(';
+        typename DepNode::dep_set::const_iterator ki(keys.begin()), kend(keys.end());
+        if (ki != kend)
+        {
+            LLDependencies_describe(out, *ki);
+            while (++ki != kend)
+            {
+                out << ", ";
+                LLDependencies_describe(out, *ki);
+            }
+        }
+        out << ')';
+        return out;
+    }
+
+    /// Iterator over the before/after KEYs on which a given NODE depends
+    typedef typename DepNode::dep_set::const_iterator dep_iterator;
+    /// range over the before/after KEYs on which a given NODE depends
+    typedef boost::iterator_range<dep_iterator> dep_range;
+
+    /// dependencies access from key
+    dep_range get_dep_range_from_key(const KEY& key, const dep_selector& selector) const
+    {
+        typename DepNodeMap::const_iterator found = mNodes.find(key);
+        if (found != mNodes.end())
+        {
+            return dep_range(selector(found->second));
+        }
+        // We want to return an empty range. On some platforms a default-
+        // constructed range (e.g. dep_range()) does NOT suffice! The client
+        // is likely to try to iterate from boost::begin(range) to
+        // boost::end(range); yet these iterators might not be valid. Instead
+        // return a range over a valid, empty container.
+        static const typename DepNode::dep_set empty_deps;
+        return dep_range(empty_deps.begin(), empty_deps.end());
+    }
+
+    /// dependencies access from any one of our key-order iterators
+    template<typename ITERATOR>
+    dep_range get_dep_range_from_xform(const ITERATOR& iterator, const dep_selector& selector) const
+    {
+        return dep_range(selector(iterator.base()->second));
+    }
+
+    /// dependencies access from sorted_iterator
+    dep_range get_dep_range_from_sorted(const sorted_iterator& sortiter,
+                                        const dep_selector& selector) const
+    {
+        // sorted_iterator is a boost::indirect_iterator wrapping an mCache
+        // iterator, which we can obtain by sortiter.base(). Deferencing that
+        // gets us an mCache entry, an 'iterator' -- one of our traversal
+        // iterators -- on which we can use get_dep_range_from_xform().
+        return get_dep_range_from_xform(*sortiter.base(), selector);
+    }
+
+    /**
+     * Get a range over the after KEYs stored for the passed KEY or iterator,
+     * in <i>arbitrary order.</i> If you pass a nonexistent KEY, returns empty
+     * range -- same as a KEY with no after KEYs. Detect existence of a KEY
+     * using get() instead.
+     */
+    template<typename KEY_OR_ITER>
+    dep_range get_after_range(const KEY_OR_ITER& key) const;
+
+    /**
+     * Get a range over the before KEYs stored for the passed KEY or iterator,
+     * in <i>arbitrary order.</i> If you pass a nonexistent KEY, returns empty
+     * range -- same as a KEY with no before KEYs. Detect existence of a KEY
+     * using get() instead.
+     */
+    template<typename KEY_OR_ITER>
+    dep_range get_before_range(const KEY_OR_ITER& key) const;
+
+private:
+    DepNodeMap mNodes;
+    mutable iterator_list mCache;
+};
+
+/**
+ * Functor to get a dep_range from a KEY or iterator -- generic case. If the
+ * passed value isn't one of our iterator specializations, assume it's
+ * convertible to the KEY type.
+ */
+template<typename KEY_ITER>
+struct LLDependencies_dep_range_from
+{
+    template<typename KEY, typename NODE, typename SELECTOR>
+    typename LLDependencies<KEY, NODE>::dep_range
+    operator()(const LLDependencies<KEY, NODE>& deps,
+               const KEY_ITER& key,
+               const SELECTOR& selector)
+    {
+        return deps.get_dep_range_from_key(key, selector);
+    }
+};
+
+/// Specialize LLDependencies_dep_range_from for our key-order iterators
+template<typename FUNCTION, typename ITERATOR>
+struct LLDependencies_dep_range_from< boost::transform_iterator<FUNCTION, ITERATOR> >
+{
+    template<typename KEY, typename NODE, typename SELECTOR>
+    typename LLDependencies<KEY, NODE>::dep_range
+    operator()(const LLDependencies<KEY, NODE>& deps,
+               const boost::transform_iterator<FUNCTION, ITERATOR>& iter,
+               const SELECTOR& selector)
+    {
+        return deps.get_dep_range_from_xform(iter, selector);
+    }
+};
+
+/// Specialize LLDependencies_dep_range_from for sorted_iterator
+template<typename BASEITER>
+struct LLDependencies_dep_range_from< boost::indirect_iterator<BASEITER> >
+{
+    template<typename KEY, typename NODE, typename SELECTOR>
+    typename LLDependencies<KEY, NODE>::dep_range
+    operator()(const LLDependencies<KEY, NODE>& deps,
+               const boost::indirect_iterator<BASEITER>& iter,
+               const SELECTOR& selector)
+    {
+        return deps.get_dep_range_from_sorted(iter, selector);
+    }
+};
+
+/// generic get_after_range() implementation
+template<typename KEY, typename NODE>
+template<typename KEY_OR_ITER>
+typename LLDependencies<KEY, NODE>::dep_range
+LLDependencies<KEY, NODE>::get_after_range(const KEY_OR_ITER& key_iter) const
+{
+    return LLDependencies_dep_range_from<KEY_OR_ITER>()(
+        *this,
+        key_iter,
+        boost::bind<const typename DepNode::dep_set&>(&DepNode::after, _1));
+}
+
+/// generic get_before_range() implementation
+template<typename KEY, typename NODE>
+template<typename KEY_OR_ITER>
+typename LLDependencies<KEY, NODE>::dep_range
+LLDependencies<KEY, NODE>::get_before_range(const KEY_OR_ITER& key_iter) const
+{
+    return LLDependencies_dep_range_from<KEY_OR_ITER>()(
+        *this,
+        key_iter,
+        boost::bind<const typename DepNode::dep_set&>(&DepNode::before, _1));
+}
+
+#endif /* ! defined(LL_LLDEPENDENCIES_H) */