1affc150dc44fab1911775a49636d0ce85333b634Zonr Chang//===- InputTree.h --------------------------------------------------------===// 25460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// 35460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// The MCLinker Project 45460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// 55460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// This file is distributed under the University of Illinois Open Source 65460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// License. See LICENSE.TXT for details. 75460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// 85460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao//===----------------------------------------------------------------------===// 922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao#ifndef MCLD_MC_INPUT_TREE_H 1022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao#define MCLD_MC_INPUT_TREE_H 115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#ifdef ENABLE_UNITTEST 125460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#include <gtest.h> 135460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#endif 145460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao#include <mcld/ADT/BinTree.h> 1622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao#include <mcld/ADT/TypeTraits.h> 1722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao#include <mcld/MC/MCLDInput.h> 1822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao#include <mcld/Support/Path.h> 195460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 205460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#include <string> 215460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 225460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liaonamespace mcld { 245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class template<typename Traits, typename Iterator> PolicyIterator<mcld::Input> 265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief PolicyIterator<mcld::Input> is a partially specific PolicyIterator 275460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 285460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<typename Traits, typename IteratorType> 295460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoclass PolicyIterator<mcld::Input, Traits, IteratorType> : public PolicyIteratorBase<Input, Traits, IteratorType> 305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef PolicyIterator<Input, Traits, IteratorType> Self; 335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef PolicyIteratorBase<Input, Traits, IteratorType> Base; 345460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef PolicyIterator<Input, typename Traits::nonconst_traits, IteratorType> iterator; 355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef PolicyIterator<Input, typename Traits::const_traits, IteratorType> const_iterator; 365460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 375460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 385460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao PolicyIterator() 395460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao : Base() {} 405460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 415460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao PolicyIterator(const iterator &X) 425460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao : Base(X.m_pNode) {} 435460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 445460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao explicit PolicyIterator(NodeBase* X) 455460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao : Base(X) {} 465460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 475460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao virtual ~PolicyIterator() {} 485460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 495460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao bool isGroup() const 5022add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao { return !Base::hasData() && !Base::isRoot(); } 515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 525460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao Self& operator++() { 535460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao IteratorType::advance(); 5422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao // skip the Group node 5522add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao while (isGroup()) 565460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao IteratorType::advance(); 575460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return *this; 585460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 595460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 605460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao Self operator++(int) { 615460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao Self tmp(*this); 625460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao IteratorType::advance(); 6322add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao // skip the Group node 6422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao while (isGroup()) 655460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao IteratorType::advance(); 665460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return tmp; 675460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 685460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 695460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 705460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao/** \class InputTree 715460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * \brief InputTree is the input tree to contains all inputs from the 725460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * command line. 735460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 745460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * InputTree, of course, is uncopyable. 755460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * 765460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao * @see Input 775460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao */ 785460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoclass InputTree : public BinaryTree<Input> 795460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 805460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaoprivate: 815460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef BinaryTree<Input> BinTreeTy; 825460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 835460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 845460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao enum Direction { 855460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao Inclusive = TreeIteratorBase::Leftward, 865460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao Positional = TreeIteratorBase::Rightward 875460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao }; 885460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 895460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef BinaryTree<Input>::iterator iterator; 905460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao typedef BinaryTree<Input>::const_iterator const_iterator; 915460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 925460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 93affc150dc44fab1911775a49636d0ce85333b634Zonr Chang /** \class Mover 94affc150dc44fab1911775a49636d0ce85333b634Zonr Chang * \brief Mover provides the interface for moving iterator forward. 95affc150dc44fab1911775a49636d0ce85333b634Zonr Chang * 96affc150dc44fab1911775a49636d0ce85333b634Zonr Chang * Mover is a function object (functor). @ref Mover::move moves 97affc150dc44fab1911775a49636d0ce85333b634Zonr Chang * iterator forward in certain direction. @ref Mover::connect 98affc150dc44fab1911775a49636d0ce85333b634Zonr Chang * connects two nodes of the given iterators togather. 99affc150dc44fab1911775a49636d0ce85333b634Zonr Chang */ 100affc150dc44fab1911775a49636d0ce85333b634Zonr Chang struct Mover { 101affc150dc44fab1911775a49636d0ce85333b634Zonr Chang virtual ~Mover() {} 10267e37f1be98c926645219cfb47fab9e90d8c725cShih-wei Liao virtual void connect(TreeIteratorBase& pFrom, const TreeIteratorBase& pTo) const = 0; 10367e37f1be98c926645219cfb47fab9e90d8c725cShih-wei Liao virtual void move(TreeIteratorBase& pNode) const = 0; 1045460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao }; 1055460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 106affc150dc44fab1911775a49636d0ce85333b634Zonr Chang /** \class Succeeder 107affc150dc44fab1911775a49636d0ce85333b634Zonr Chang * \brief class Succeeder moves the iterator afterward. 108affc150dc44fab1911775a49636d0ce85333b634Zonr Chang */ 109affc150dc44fab1911775a49636d0ce85333b634Zonr Chang struct Succeeder : public Mover { 11067e37f1be98c926645219cfb47fab9e90d8c725cShih-wei Liao virtual void connect(TreeIteratorBase& pFrom, const TreeIteratorBase& pTo) const { 1115460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao proxy::hook<Positional>(pFrom.m_pNode, pTo.m_pNode); 1125460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1135460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 11467e37f1be98c926645219cfb47fab9e90d8c725cShih-wei Liao virtual void move(TreeIteratorBase& pNode) const { 1155460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pNode.move<Positional>(); 1165460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1175460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao }; 1185460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 119affc150dc44fab1911775a49636d0ce85333b634Zonr Chang /** \class Includer 120affc150dc44fab1911775a49636d0ce85333b634Zonr Chang * \brief class Includer moves the iterator downward. 121affc150dc44fab1911775a49636d0ce85333b634Zonr Chang */ 122affc150dc44fab1911775a49636d0ce85333b634Zonr Chang struct Includer : public Mover { 12367e37f1be98c926645219cfb47fab9e90d8c725cShih-wei Liao virtual void connect(TreeIteratorBase& pFrom, const TreeIteratorBase& pTo) const { 1245460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao proxy::hook<Inclusive>(pFrom.m_pNode, pTo.m_pNode); 1255460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1265460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 12767e37f1be98c926645219cfb47fab9e90d8c725cShih-wei Liao virtual void move(TreeIteratorBase& pNode) const { 1285460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao pNode.move<Inclusive>(); 1295460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao } 1305460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao }; 1315460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1325460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 1335460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao static Succeeder Afterward; 1345460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao static Includer Downward; 1355460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1365460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaopublic: 1375460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1385460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao using BinTreeTy::merge; 1395460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1405460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao // ----- modify ----- // 1415460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao template<size_t DIRECT> 14267e37f1be98c926645219cfb47fab9e90d8c725cShih-wei Liao InputTree& enterGroup(TreeIteratorBase pRoot); 1435460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1445460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao template<size_t DIRECT> 14567e37f1be98c926645219cfb47fab9e90d8c725cShih-wei Liao InputTree& insert(TreeIteratorBase pRoot, 14622add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao Input& pInput); 1475460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 14822add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao InputTree& merge(TreeIteratorBase pRoot, 149affc150dc44fab1911775a49636d0ce85333b634Zonr Chang const Mover& pMover, 1505460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao InputTree& pTree); 1515460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 15267e37f1be98c926645219cfb47fab9e90d8c725cShih-wei Liao InputTree& insert(TreeIteratorBase pRoot, 153affc150dc44fab1911775a49636d0ce85333b634Zonr Chang const Mover& pMover, 15422add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao Input& pInput); 1555460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 15667e37f1be98c926645219cfb47fab9e90d8c725cShih-wei Liao InputTree& enterGroup(TreeIteratorBase pRoot, 157affc150dc44fab1911775a49636d0ce85333b634Zonr Chang const Mover& pMover); 1585460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1595460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao}; 1605460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1615460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaobool isGroup(const InputTree::iterator& pos); 1625460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaobool isGroup(const InputTree::const_iterator& pos); 1635460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaobool isGroup(const InputTree::dfs_iterator& pos); 1645460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaobool isGroup(const InputTree::const_dfs_iterator& pos); 1655460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaobool isGroup(const InputTree::bfs_iterator& pos); 1665460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaobool isGroup(const InputTree::const_bfs_iterator& pos); 1675460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1685460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} // namespace of mcld 1695460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1705460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao//===----------------------------------------------------------------------===// 1715460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao// template member functions 17222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao//===----------------------------------------------------------------------===// 1735460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<size_t DIRECT> 1745460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaomcld::InputTree& 17567e37f1be98c926645219cfb47fab9e90d8c725cShih-wei Liaomcld::InputTree::enterGroup(mcld::TreeIteratorBase pRoot) 1765460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 17722add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao BinTreeTy::node_type* node = createNode(); 178affc150dc44fab1911775a49636d0ce85333b634Zonr Chang if (pRoot.isRoot()) 179affc150dc44fab1911775a49636d0ce85333b634Zonr Chang proxy::hook<TreeIteratorBase::Leftward>(pRoot.m_pNode, 1805460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const_cast<const node_type*>(node)); 1815460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao else 182affc150dc44fab1911775a49636d0ce85333b634Zonr Chang proxy::hook<DIRECT>(pRoot.m_pNode, 1835460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const_cast<const node_type*>(node)); 1845460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return *this; 1855460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 1865460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 1875460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liaotemplate<size_t DIRECT> 18867e37f1be98c926645219cfb47fab9e90d8c725cShih-wei Liaomcld::InputTree& mcld::InputTree::insert(mcld::TreeIteratorBase pRoot, 18922add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao mcld::Input& pInput) 1905460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao{ 1915460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao BinTreeTy::node_type* node = createNode(); 19222add6ff3426df1a85089fe6a6e1597ee3b6f300Shih-wei Liao node->data = &pInput; 193affc150dc44fab1911775a49636d0ce85333b634Zonr Chang if (pRoot.isRoot()) 194affc150dc44fab1911775a49636d0ce85333b634Zonr Chang proxy::hook<TreeIteratorBase::Leftward>(pRoot.m_pNode, 1955460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const_cast<const node_type*>(node)); 1965460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao else 197affc150dc44fab1911775a49636d0ce85333b634Zonr Chang proxy::hook<DIRECT>(pRoot.m_pNode, 1985460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao const_cast<const node_type*>(node)); 1995460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao return *this; 2005460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao} 2015460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 2025460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao#endif 2035460a1f25d9ddecb5c70667267d66d51af177a99Shih-wei Liao 204