INsNode.h
// INsNode.h
//
// Author David Barrett-Lennard
// (C)opyright Cedanet Pty Ltd 2008
@import "Object.h"
@import "SubString.h"
@import "MacroUtils.h"
/*
INsNode
-------
The interface INsNode is the basis for the namespace system and path searching. Unlike
Ceda1, in Ceda2 it is more usual for a parent node to be reponsible for naming its
children. This is important for performance. A node with many children can use a
hashmap, B+Tree or red black tree for efficient search. More importantly path look
up only needs to fetch objects along the path.
Note as well that only objects with children need to worry about how they should be
named. Since many nodes have no children at all this simplifies the implementation
for many objects.
An INsNode can easily forward the methods onto another object, thereby causing it to
"hijack" its children!
Unlike Ceda1, INsNode doesn't expect each node to store a pointer to the parent node.
Therefore it appears it isn't possible to bind a path using the namespace hiding rule,
because that depends on the ability to navigate up through the ancestry to perform searches
downwards from successively higher positions. The advantage is that INsNodes can form
DAGs rather than strict trees. Clearly this is very useful for symbolic links.
[from email to Dan and Jesse]
We make use of the scenegraph metaphor. We get our cake and eat it too as follows...
During the scenegraph traversal we use a stack of namespaces in thread local storage that
are pushed and popped by nodes that want to contribute to the namespace ancestry. Then
we implement the hiding rule simply by searching up through the linear stack of namespaces.
This is exactly how I was intending to implement ambient properties. I.e. for performance
an ambient property setter would push itself as a namespace of ambient properties, rather
than actually push all the ambient settings themselves. This obviously is much faster
and also allows the dependency graph to form.
Upshot : fast, efficient, less code to write, unifies ambient settings and namespace
system, allows for DAGs...
Do you remember the ideas on logical namespaces? I think our previous approach was
hampered by the tree constraint forcing a logical namespace to heap allocate INsNodes
at run time.
I'm wondering whether some "logical namespace controller" in ambient state is in general
able to get the first look in as far as determining how nodes are named and what are the
children of a given node. A controller is in fact a run time decorator that implements
INsNode and is able pass calls through to a delegate, and manipulate the results. The
decorator is reapplied all the way down through the namespace (at least while it remains
current in the sense of pushing and popping ambient state).
This encompasses the "super app" idea - as one browses data, the way it is displayed and
edited is dictated by a complex ambient controller (which may itself be assembled).
Proposal 30 May 2008
--------------------
It is inappropriate for INsNode to assume that it is easy to index the children. For example,
it makes it difficult to efficiently use a map<string, ptr<IObject> > to represent all the
children of a node.
Therefore the following interface is proposed
$interface+ INsNode : IObject
{
// Get the current number of child nodes
ssize_t GetNumNsChildren() const;
ptr<IForwardsIterator<NamedObject> > GetIterator() const;
// Get the child with the given name
// Returns one of
// NPR_OK
// NPR_NOT_FOUND
// NPR_AMBIGUOUS
ENavNamespaceResult FindChildNsNode(SubString name, ptr<IObject>& foundNode) const;
};
where we have used an abstract forwards iterator.
Namespace decorators
--------------------
Namespace decoration is an important concept. To promote code reuse mixins can be written that
decorate a base class implementation of INsNode.
Compile time mixins can be used to build run time decorators that are suitable for decorator
chains.
Ceda namespace system
---------------------
Concepts
* Namespaces don't define their own name. Instead namespaces define the names of their children.
* The namespaces form a tree not a DAG
* The underlying objects that generate the tree can link other objects, so in that sense it's like a DAG
* There are no pointers to parents
* During the recurse namespaces are pushed on a stack
* The namespace stack provides the mechanism for ambient properties
* The namespace tree is decoupled from persistence
Example a/
b/
c
d/
e
f
g
At e we have stack: a children = {b,d}
d children = {e,f,g}
Consider that 'a' has a large number of classifications, a number of which want to apply ambient state.
Rather than push all these, can we only push 'a', but 'a' represents a single point of access to all
these combined namespaces.
*/
/*
namespace YYY
{
$interface Iq
{
@for (T in [bool,int8,int16,int32,int64,uint8,uint16,uint32,uint64,char8,char16,string8,string16])
{
@def I = mToIdentifier(T)
void passbyval_@@I(T x);
void passbyptr_@@I(T* x);
void passbyref_@@I(T& x);
void passbycval_@@I(const T x);
void passbycptr_@@I(const T* x);
void passbycref_@@I(const T& x);
T retbyval_@@I();
}
};
}
*/
namespace ceda
{
///////////////////////////////////////////////////////////////////////////////////////////////////
// NamedObject
struct NamedObject
{
xstring name;
ptr<IObject> obj;
};
///////////////////////////////////////////////////////////////////////////////////////////////////
// ENavNamespaceResult
$enum+ ENavNamespaceResult
{
NPR_OK,
NPR_NOT_FOUND,
NPR_AMBIGUOUS,
NPR_SYNTAX_ERROR
};
///////////////////////////////////////////////////////////////////////////////////////////////////
// INsNode
$interface+ INsNode : IObject
{
// Used to indicate if this node has the ability to have child nodes. A return value of false
// indicates that the node will never have children. This is used by explorer windows to display
// the -/+ box
//bool CanHaveChildren() const;
// Get the current number of child nodes
ssize_t GetNumNsChildren() const;
// Get the name of the ith child
xstring GetChildNsNodeName(ssize_t i) const;
// Get the ith child
ptr<INsNode> GetChildNsNode(ssize_t i) const;
// Get the child with the given name
// Returns one of
// NPR_OK
// NPR_NOT_FOUND
// NPR_AMBIGUOUS
ENavNamespaceResult FindChildNsNode(SubString name, ptr<INsNode>& foundNode) const;
};
// Can form the basis for implementing the method FindChildNsNode() in terms of
// GetNumNsChildren(), GetChildNsNodeName() and GetChildNsNode() using a linear scan.
$function+ ENavNamespaceResult FindChildNsNodeWithLinearScan(ptr<const INsNode> parent, SubString name, ptr<INsNode>& child);
/*
startNode must not be null
If path is empty then returns NPR_OK and foundNode = startNode
The path must be of the form
name1/name2/..../namen
where each namei is a non-empty string. Otherwise returns NPR_SYNTAX_ERROR. Note that the
path must not begin or end with a '/'.
Returns one of
NPR_OK
NPR_NOT_FOUND
NPR_AMBIGUOUS
NPR_SYNTAX_ERROR
*/
$function+ ENavNamespaceResult BindPathDownwards(ptr<INsNode>& foundNode, ptr<INsNode> startNode, SubString path, xchar delimiter = '/');
@api void DumpNsTree(xostream& os, ptr<INsNode> node, int indentPerLevel = 4);
$mixin NoChildrenNsNodeMixin
{
ssize_t GetNumNsChildren() const
{
return 0;
}
xstring GetChildNsNodeName(ssize_t index) const
{
cxAssert(0);
return xstring();
}
ptr<INsNode> GetChildNsNode(ssize_t index)
{
cxAssert(0);
return nullptr;
}
ENavNamespaceResult FindChildNsNode(SubString name, ptr<INsNode>& foundNode) const
{
return NPR_NOT_FOUND;
}
};
//$mixin LinearScanNsNodeMixin
//{
// ENavNamespaceResult FindChildNsNode(SubString name, ptr<INsNode>& foundNode) const
// {
// return FindChildNsNodeWithLinearScan(this,name,child);
// }
//};
///////////////////////////////////////////////////////////////////////////////////////////////////
struct INsNodeVisitor
{
virtual void OnVisitNsNode(const xstring* path, ptr<INsNode> node) = 0;
// Override this function and return true to cancel namespace navigation before any further
// nodes are visited, for example when only the first match is required
//virtual bool StopVisiting() { return false; }
};
@api void VisitNamespace(ptr<INsNode> node, INsNodeVisitor& v, xstring* path = nullptr, xchar pathDelimiter = '/');
///////////////////////////////////////////////////////////////////////////////////////////////////
// ComposeNameSpacesMixin
/*
Implements the union of Head and Tail namespaces, giving them equal precedence.
*/
$mixin ComposeNameSpacesMixin
{
typedef typename BaseClass::Head Head;
typedef typename BaseClass::Tail Tail;
ssize_t GetNumNsChildren() const
{
return Head::GetNumNsChildren() + Tail::GetNumNsChildren();
}
// A composite iterator that iterates through one collection then the second collection
struct NsIterator
{
NsIterator(typename BaseClass::Head::NsIterator i1, typename BaseClass::Tail::NsIterator i2) : m_i1(i1), m_i2(i2)
{
}
explicit operator bool() const
{
return m_i1 || m_i2;
}
NamedObject operator*() const
{
return m_i1 ? *m_i1 : *m_i2;
}
NsIterator& operator++()
{
if (m_i1) ++m_i1;
else ++m_i2;
return *this;
}
typename BaseClass::Head::NsIterator m_i1;
typename BaseClass::Tail::NsIterator m_i2;
};
NsIterator GetNsIterator() const
{
return NsIterator( Head::GetNsIterator(), Tail::GetNsIterator() );
}
// There are different policies available here. Eg can give precedence to the head or to
// the tail, or we could given them equal precedence which increases the risk of ambiguity
// errors. The following code does the latter.
ENavNamespaceResult FindChildNsNode(SubString name, ptr<IObject>& foundNode) const
{
ptr<IObject> n1;
ENavNamespaceResult r1 = Head::FindChildNsNode(name,n1);
if (r1 == NPR_AMBIGUOUS) return r1;
ptr<IObject> n2;
ENavNamespaceResult r2 = Tail::FindChildNsNode(name,n2);
if (r2 == NPR_AMBIGUOUS)
{
return r2;
}
else if (r2 == NPR_OK)
{
if (r1 == NPR_OK) return NPR_AMBIGUOUS;
foundNode = n2;
return NPR_OK;
}
else
{
if (r1 == NPR_NOT_FOUND) return NPR_NOT_FOUND;
foundNode = n1;
return NPR_OK;
}
}
};
///////////////////////////////////////////////////////////////////////////////////////////////////
// AddChildToNamespaceMixin
// Decorate the base class namespace by adding child GetChild() with the name GetChildName()
$mixin AddChildToNamespaceMixin
{
ssize_t GetNumNsChildren() const
{
return BaseClass::GetNumNsChildren() + 1;
}
struct NsIterator
{
explicit operator bool() const
{
return !m_atend;
}
NamedObject operator*() const
{
cxAssert(!m_atend);
return m_i ? *m_i : BaseClass::GetChild();
}
NsIterator& operator++()
{
cxAssert(!m_atend);
if (m_i.AtEnd())
{
m_atend = true;
}
else
{
++m_i;
}
return *this;
}
typename BaseClass::NsIterator m_i;
bool m_atend;
};
NsIterator GetIterator() const
{
return NsIterator( BaseClass::GetIterator() );
}
// There are different policies available here. Eg can give precedence to the child or to
// the base, or we could given them equal precedence which increases the risk of ambiguity
// errors.
// The following gives precedence to the child.
ENavNamespaceResult FindChildNsNode(SubString name, ptr<IObject>& foundNode) const
{
if (name == BaseClass::GetChildName())
{
foundNode = BaseClass::GetChild();
return NPR_OK;
}
return BaseClass::FindChildNsNode(name,foundNode);
}
};
} // namespace ceda