Crafting an interpreter Part 3 - Parse Trees and Syntax Trees

/*	peg_tprint.h
	Created: 2005 Mai; Author: Martin.Holzherr@infobrain.com
	Copyright: This software is free of copyright's and is part of a work-in-progress
*/
/*  defines a print protocol for parse and syntax trees generated with the
	peg_tree module. 
	Tree printers should be derived from struct PrintNode.
	The 'PrintUCharNode' class covers a case where the Iterator 
	has type const unsigned char*
*/
#ifndef PEG_TPRINT_H_
#define PEG_TPRINT_H_

#include <map>
namespace peg_tprint{
using namespace peg_tree;
template<typename It >
struct PrintNode{
	virtual size_t  LenMaxLine	()=0;
	virtual bool	IsLeaf		(TNode<It>* p)=0;
	virtual bool	IsSkip		(TNode<It>* p){(p);return false;}
	virtual void	PrintNodeBeg(TNode<It>* p, bool bAlignVertical, 
								size_t& nOffsetLineBeg, size_t nLevel)=0;
	virtual void	PrintNodeEnd(TNode<It>* p, bool bAlignVertical, 
								 size_t& nOffsetLineBeg, size_t nLevel)=0;
	virtual size_t	LenNodeBeg	(TNode<It>* p)=0;
	virtual size_t	LenNodeEnd  (TNode<It>* p)=0;
	virtual void    PrintLeaf   (TNode<It>* p, size_t& nOffsetLineBeg, 
												bool bAlignVertical)=0;
	virtual size_t  LenLeaf		(TNode<It>* p)=0; 
	virtual size_t	LenDistNext	(TNode<It>* p, bool bAlignVertical,
									size_t& nOffsetLineBeg,int nLevel)=0;
	virtual void	PrintDistNext( TNode<It>* p, bool bAlignVertical,
									size_t& nOffsetLineBeg,int nLevel)=0;
};
struct PrintUCharNode : public PrintNode<const unsigned char*>{
	typedef const unsigned char* CUCharPtr;
	typedef std::pair<int,const char*> IdName;
	PrintUCharNode(std::ostream& os, size_t nMaxLineLen=60,
										IdName* pBeg=0,IdName* pEnd=0)
		:m_os(os),m_nMaxLineLen(nMaxLineLen),m_mapIdName(pBeg,pEnd)
	{
	}
	virtual size_t	LenMaxLine(){return m_nMaxLineLen;}
	virtual void	
		PrintNodeBeg(TNode<CUCharPtr>* p, bool bAlignVertical, 
								size_t& nOffsetLineBeg, size_t nLevel)
	{	
		(nLevel);
		PrintIdAsName(p);
		m_os << "<"; 
		if( bAlignVertical ){
			m_os << std::endl	<< std::string(nOffsetLineBeg+= 2,' ');
		}else{
			++nOffsetLineBeg;
		}
	}
	virtual void	
		PrintNodeEnd(TNode<CUCharPtr>* p, bool bAlignVertical, 
								size_t& nOffsetLineBeg, size_t nLevel)
	{
		(nLevel);(p);(nOffsetLineBeg);
		if( bAlignVertical ){
			m_os << std::endl	<<	std::string(nOffsetLineBeg-= 2,' ');
		}
		m_os << ">";
		if( !bAlignVertical ){
			++nOffsetLineBeg;
		}
	}
	virtual size_t	LenNodeBeg	(TNode<CUCharPtr>* p){return LenIdAsName(p)+1;}
	virtual size_t	LenNodeEnd  (TNode<CUCharPtr>* p){(p);return 1;}
	virtual void    PrintLeaf   (TNode<CUCharPtr>* p, 
								size_t& nOffsetLineBeg, bool bAlignVertical)
	{
		(nOffsetLineBeg);(bAlignVertical);
		int len= p->match.end - p->match.beg;
		m_os << "'";
		if( len > 0 ){
			m_os	<<	std::string((const char*)p->match.beg,len);
		}
		m_os << "'";
	}
	virtual size_t  LenLeaf(TNode<CUCharPtr>* p){
		return p->match.end - p->match.beg+2;
	}
	virtual bool	IsLeaf		(TNode<CUCharPtr>* p)
	{
		return p->child==0;
	}
	
	virtual void	
		PrintDistNext(TNode<CUCharPtr>* p, bool bAlignVertical,
								size_t& nOffsetLineBeg,int nLevel)
	{
		(p);(nLevel);
		if(bAlignVertical){
			m_os << std::endl	<<	std::string(nOffsetLineBeg,' ');
		}else{
			m_os << " ";++nOffsetLineBeg;
		}
	}

	virtual size_t	
		LenDistNext		(TNode<CUCharPtr>* p,  bool bAlignVertical,
									size_t& nOffsetLineBeg,int nLevel)
	{
		(p);(bAlignVertical);(nOffsetLineBeg);(nLevel);
		return 1;
	}
	virtual size_t LenIdAsName(TNode<CUCharPtr>* p)
	{
		MapIdName::const_iterator it= m_mapIdName.find(p->id);
		if( it!=m_mapIdName.end() ){return strlen(it->second);}
		return 0;
	}
	virtual void PrintIdAsName(TNode<CUCharPtr>* p)
	{
		MapIdName::const_iterator it= m_mapIdName.find(p->id);
		if( it!=m_mapIdName.end() ){m_os << it->second;}
	}
	typedef std::map<int,const char*> MapIdName;
	MapIdName m_mapIdName;
	std::ostream&	m_os;
	size_t			m_nMaxLineLen;
private:
	PrintUCharNode& operator=(const PrintUCharNode&);
};
template<typename It>
size_t DetermineLineLength(TNode<It>* pParent,PrintNode<It>& rp,
									size_t nOffsetLineBeg,size_t nLevel)
{
	(nLevel);
	size_t nLen= rp.LenNodeBeg(pParent);
	for(TNode<It>* p= pParent->child ;p;p= p->next){
		if( rp.IsSkip(p) )continue;
		if( rp.IsLeaf(p) ){
			nLen+= rp.LenLeaf(p);
		}else{
			nLen+= DetermineLineLength(p,rp,nOffsetLineBeg,nLevel);
		}
		if( nLen+nOffsetLineBeg > rp.LenMaxLine() ){
			return nLen+nOffsetLineBeg;
		}
	}
	nLen+= rp.LenNodeEnd(p);
	return nLen;
}
template<typename It>
void PrintTree(TNode<It>* pParent,PrintNode<It>& rp,
							size_t& nOffsetLineBeg,size_t nLevel=0)
{
	if( rp.IsLeaf(pParent) ){
		rp.PrintLeaf(pParent,nOffsetLineBeg, false);
		return;
	}
	bool bAlignVertical= 
		DetermineLineLength(pParent,rp,nOffsetLineBeg,nLevel)>rp.LenMaxLine();
	rp.PrintNodeBeg(pParent,bAlignVertical,nOffsetLineBeg,nLevel);
	size_t nOffset= nOffsetLineBeg;
	for(TNode<It>* p= pParent->child ;p;p= p->next){
		if( rp.IsSkip(p) )continue;
		
		if( rp.IsLeaf(p) ){
			rp.PrintLeaf(p, nOffsetLineBeg, bAlignVertical);
		}else{
			PrintTree(p, rp, nOffsetLineBeg, nLevel+1);
		}
		if( bAlignVertical ){
			nOffsetLineBeg= nOffset;
		}
		while(p->next && rp.IsSkip(p->next)){
			p= p->next;
		}
		if(p->next ){
			rp.PrintDistNext(p,bAlignVertical, nOffsetLineBeg, nLevel);
		}
	}
	rp.PrintNodeEnd(pParent,bAlignVertical,nOffsetLineBeg,nLevel);
}
}
#endif