158 lines
4.3 KiB
C++
158 lines
4.3 KiB
C++
/******************************************************************************/
|
|
/* ABSTRACT SYNTAX TREE *******************************************************/
|
|
/******************************************************************************/
|
|
|
|
#ifndef _H_EBCL_SYNTAXTREE
|
|
#define _H_EBCL_SYNTAXTREE
|
|
#include <ebcl/Types.hh>
|
|
#include <ebcl/Arrays.hh>
|
|
#include <ebcl/Algorithms.hh>
|
|
namespace ebcl {
|
|
|
|
|
|
/*= SYNTAX TREE ==============================================================*/
|
|
|
|
/*
|
|
* A syntax tree has typed nodes; each nodes may have 0, 1 or more children
|
|
* of various types. In addition, a node may carry additional data. The type
|
|
* of the data associated to a given node is not known.
|
|
*
|
|
* Nodes are accessed using integer indices. The tree's root node is always at
|
|
* index 0.
|
|
*/
|
|
template<
|
|
// Node type (should be an enum)
|
|
typename NodeType ,
|
|
// Location type
|
|
typename LocationType ,
|
|
// Data storage size
|
|
size_t InPlaceSize = sizeof( void* )
|
|
> class T_SyntaxTree
|
|
{
|
|
public:
|
|
using E_Node = NodeType;
|
|
using T_Location = LocationType;
|
|
using T_Self = T_SyntaxTree< NodeType , LocationType , InPlaceSize >;
|
|
|
|
static constexpr size_t StorageSize
|
|
= T_VariantExt< InPlaceSize >::StorageSize;
|
|
|
|
// A node, as seen from a visitor
|
|
struct T_Node
|
|
{
|
|
T_Self const& tree;
|
|
uint32_t node;
|
|
|
|
T_Node( ) = delete;
|
|
T_Node( T_Self const& tree , uint32_t node ) noexcept;
|
|
T_Node( T_Node const& other ) noexcept;
|
|
T_Node( T_Node&& other ) noexcept;
|
|
T_Node& operator =( T_Node const& other ) noexcept;
|
|
T_Node& operator =( T_Node&& other ) noexcept;
|
|
};
|
|
|
|
// Visitor type. "References" are actually values.
|
|
using T_Visitor = ::ebcl::T_Visitor< T_Node , T_Node >;
|
|
|
|
private:
|
|
// Internal storage for nodes
|
|
struct T_Node_
|
|
{
|
|
// Node type
|
|
E_Node type;
|
|
// Index of the parent node
|
|
uint32_t parent;
|
|
// Location of the node
|
|
T_Location location;
|
|
// Indices of the node's children
|
|
T_AutoArray< uint32_t , 8 > children;
|
|
// Extra data storage
|
|
T_VariantExt< StorageSize > data;
|
|
|
|
explicit T_Node_( E_Node type ,
|
|
uint32_t parent ) noexcept;
|
|
|
|
T_Node_( T_Node_ const& ) = delete;
|
|
T_Node_& operator =( T_Node_ const& ) = delete;
|
|
|
|
T_Node_( T_Node_&& other ) noexcept;
|
|
T_Node_& operator =( T_Node_&& other ) noexcept;
|
|
};
|
|
|
|
T_Array< T_Node_ > nodes_;
|
|
|
|
public:
|
|
M_TEMPLATE_POINTERS( T_SyntaxTree );
|
|
|
|
// Create the syntax tree, specifying the type of the root node
|
|
explicit T_SyntaxTree( E_Node rootType ) noexcept;
|
|
|
|
// Copy is disabled
|
|
T_SyntaxTree( T_Self const& ) = delete;
|
|
T_Self& operator =( T_Self const& other ) = delete;
|
|
|
|
// Move construction / assignment
|
|
T_SyntaxTree( T_Self&& other ) noexcept;
|
|
T_Self& operator =( T_Self&& other ) noexcept;
|
|
|
|
// Swapping
|
|
T_Self& swap( T_Self& other ) noexcept;
|
|
|
|
//----------------------------------------------------------------------
|
|
|
|
// Get the type of a node
|
|
E_Node typeOf( uint32_t node ) const noexcept;
|
|
|
|
// Returns the index of a node's parent. The root node will always
|
|
// return its own index.
|
|
uint32_t parentOf( uint32_t node ) const noexcept;
|
|
|
|
// Access the list of children for a node
|
|
T_AutoArray< uint32_t , 8 > const& childrenOf(
|
|
uint32_t node ) const noexcept;
|
|
|
|
// Check whether some node contains data
|
|
bool hasData( uint32_t node ) const noexcept;
|
|
|
|
// Access the data stored inside a node
|
|
template< typename D >
|
|
D const& dataOf( uint32_t node ) const;
|
|
|
|
// Access a node's location
|
|
T_Location const& locationOf( uint32_t node ) const noexcept;
|
|
|
|
//----------------------------------------------------------------------
|
|
|
|
// Add a new child, return its index
|
|
uint32_t addChild(
|
|
uint32_t parent ,
|
|
E_Node type ) noexcept;
|
|
|
|
// Add data to a node
|
|
template< typename D , typename ... Args >
|
|
D& newData( uint32_t node , Args&& ... args );
|
|
|
|
// Access the data stored inside a node
|
|
template< typename D >
|
|
D& dataOf( uint32_t node );
|
|
|
|
// Access a node's location
|
|
T_Location& locationOf( uint32_t node ) noexcept;
|
|
|
|
//----------------------------------------------------------------------
|
|
|
|
// Return a visitor suitable for this syntax tree
|
|
T_Visitor visitor( ) const noexcept;
|
|
|
|
// Return the root node in a format that can be fed to a visitor
|
|
T_Node root( ) const noexcept;
|
|
};
|
|
|
|
template< typename T , typename L , size_t S >
|
|
void swap( T_SyntaxTree< T , L , S >& lhs ,
|
|
T_SyntaxTree< T , L , S >& rhs ) noexcept;
|
|
|
|
|
|
}
|
|
#endif // _H_EBCL_SYNTAXTREE
|
|
#include <ebcl/inline/SyntaxTree.hh>
|