InputTree.h revision 533eae20118036f425f27bf0536ef0ccbb090b65 
1//===- InputTree.h --------------------------------------------------------===//
2//
3//                     The MCLinker Project
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9#ifndef MCLD_INPUTTREE_H
10#define MCLD_INPUTTREE_H
11
12#include <mcld/ADT/BinTree.h>
13#include <mcld/ADT/TypeTraits.h>
14#include <mcld/MC/Input.h>
15#include <mcld/Support/Path.h>
16
17#include <string>
18
19
20namespace mcld {
21
22/** \class template<typename Traits, typename Iterator> PolicyIterator<mcld::Input>
23 *  \brief PolicyIterator<mcld::Input> is a partially specific PolicyIterator
24 */
25template<typename Traits, typename IteratorType>
26class PolicyIterator<mcld::Input, Traits, IteratorType> : public PolicyIteratorBase<Input, Traits, IteratorType>
27{
28public:
29  typedef PolicyIterator<Input, Traits, IteratorType> Self;
30  typedef PolicyIteratorBase<Input, Traits, IteratorType> Base;
31  typedef PolicyIterator<Input, typename Traits::nonconst_traits, IteratorType> iterator;
32  typedef PolicyIterator<Input, typename Traits::const_traits, IteratorType>    const_iterator;
33
34public:
35  PolicyIterator()
36    : Base() {}
37
38  PolicyIterator(const iterator &X)
39    : Base(X.m_pNode) {}
40
41  explicit PolicyIterator(NodeBase* X)
42    : Base(X) {}
43
44  virtual ~PolicyIterator() {}
45
46  bool isGroup() const
47  { return !Base::hasData() && !Base::isRoot(); }
48
49  Self& operator++() {
50    IteratorType::advance();
51    // skip the Group node
52    while (isGroup())
53      IteratorType::advance();
54    return *this;
55  }
56
57  Self operator++(int) {
58    Self tmp(*this);
59    IteratorType::advance();
60    // skip the Group node
61    while (isGroup())
62      IteratorType::advance();
63    return tmp;
64  }
65};
66
67template<>
68class BinaryTree<Input> : public BinaryTreeBase<Input>
69{
70public:
71  typedef size_t             size_type;
72  typedef ptrdiff_t          difference_type;
73  typedef Input              value_type;
74  typedef value_type*        pointer;
75  typedef value_type&        reference;
76  typedef const value_type*  const_pointer;
77  typedef const value_type&  const_reference;
78
79  typedef BinaryTree<Input>  Self;
80  typedef TreeIterator<value_type, NonConstTraits<value_type> > iterator;
81  typedef TreeIterator<value_type, ConstTraits<value_type> >    const_iterator;
82
83  typedef PolicyIterator<value_type, NonConstTraits<value_type>, DFSIterator> dfs_iterator;
84  typedef PolicyIterator<value_type, ConstTraits<value_type>, DFSIterator>    const_dfs_iterator;
85  typedef PolicyIterator<value_type, NonConstTraits<value_type>, BFSIterator> bfs_iterator;
86  typedef PolicyIterator<value_type, ConstTraits<value_type>, BFSIterator>    const_bfs_iterator;
87
88protected:
89  typedef Node<value_type> node_type;
90
91public:
92  // -----  constructors and destructor  ----- //
93  BinaryTree()
94  : BinaryTreeBase<Input>()
95  { }
96
97  ~BinaryTree() {
98  }
99
100  // -----  iterators  ----- //
101  bfs_iterator bfs_begin()
102  {
103     bfs_iterator it = bfs_iterator(BinaryTreeBase<Input>::m_Root.node.left);
104     if (it.isGroup())
105       ++it;
106     return it;
107  }
108
109  bfs_iterator bfs_end()
110  { return bfs_iterator(BinaryTreeBase<Input>::m_Root.node.right); }
111
112  const_bfs_iterator bfs_begin() const
113  {
114     const_bfs_iterator it =
115                    const_bfs_iterator(BinaryTreeBase<Input>::m_Root.node.left);
116     if (it.isGroup())
117       ++it;
118     return it;
119  }
120
121  const_bfs_iterator bfs_end() const
122  { return const_bfs_iterator(BinaryTreeBase<Input>::m_Root.node.right); }
123
124  dfs_iterator dfs_begin()
125  {
126    dfs_iterator it = dfs_iterator(BinaryTreeBase<Input>::m_Root.node.left);
127    if (it.isGroup())
128      ++it;
129    return it;
130  }
131
132  dfs_iterator dfs_end()
133  { return dfs_iterator(BinaryTreeBase<Input>::m_Root.node.right); }
134
135  const_dfs_iterator dfs_begin() const
136  {
137    const_dfs_iterator it =
138                    const_dfs_iterator(BinaryTreeBase<Input>::m_Root.node.left);
139    if (it.isGroup())
140      ++it;
141    return it;
142  }
143
144  const_dfs_iterator dfs_end() const
145  { return const_dfs_iterator(BinaryTreeBase<Input>::m_Root.node.right); }
146
147  iterator root()
148  { return iterator(&(BinaryTreeBase<Input>::m_Root.node)); }
149
150  const_iterator root() const
151  {
152    // FIXME: provide the iterater constructors for constant NodeBase instead of
153    // using const_cast
154    return const_iterator(
155                    const_cast<NodeBase*>(&BinaryTreeBase<Input>::m_Root.node));
156  }
157
158  iterator begin()
159  {
160    iterator it = iterator(BinaryTreeBase<Input>::m_Root.node.left);
161    return it;
162  }
163
164  iterator end()
165  { return iterator(BinaryTreeBase<Input>::m_Root.node.right); }
166
167  const_iterator begin() const
168  {
169    const_iterator it = const_iterator(BinaryTreeBase<Input>::m_Root.node.left);
170    return it;
171  }
172
173  const_iterator end() const
174  { return const_iterator(BinaryTreeBase<Input>::m_Root.node.right); }
175
176  // ----- modifiers  ----- //
177  /// join - create a leaf node and merge it in the tree.
178  //  This version of join determines the direction on compilation time.
179  //  @param DIRECT the direction of the connecting edge of the parent node.
180  //  @param position the parent node
181  //  @param value the value being pushed.
182  template<size_t DIRECT>
183  BinaryTree& join(TreeIteratorBase& pPosition, const Input& value) {
184    node_type *node = BinaryTreeBase<Input>::createNode();
185    node->data = const_cast<Input*>(&value);
186
187    if (pPosition.isRoot())
188      pPosition.hook<TreeIteratorBase::Leftward>(node);
189    else
190      pPosition.hook<DIRECT>(node);
191
192    return *this;
193  }
194
195  /// merge - merge the tree
196  //  @param DIRECT the direction of the connecting edge of the parent node.
197  //  @param position the parent node
198  //  @param the tree being joined.
199  //  @return the joined tree
200  template<size_t DIRECT>
201  BinaryTree& merge(TreeIteratorBase& pPosition, BinaryTree& pTree) {
202    if (this == &pTree)
203      return *this;
204
205    if (!pTree.empty()) {
206      pPosition.hook<DIRECT>(pTree.m_Root.node.left);
207      BinaryTreeBase<Input>::m_Root.summon(
208                                   pTree.BinaryTreeBase<Input>::m_Root);
209      BinaryTreeBase<Input>::m_Root.delegate(pTree.m_Root);
210      pTree.m_Root.node.left = pTree.m_Root.node.right = &pTree.m_Root.node;
211    }
212    return *this;
213  }
214};
215
216/** \class InputTree
217 *  \brief InputTree is the input tree to contains all inputs from the
218 *  command line.
219 *
220 *  InputTree, of course, is uncopyable.
221 *
222 *  @see Input
223 */
224class InputTree : public BinaryTree<Input>
225{
226private:
227  typedef BinaryTree<Input> BinTreeTy;
228
229public:
230  enum Direction {
231    Inclusive  = TreeIteratorBase::Leftward,
232    Positional = TreeIteratorBase::Rightward
233  };
234
235  typedef BinaryTree<Input>::iterator       iterator;
236  typedef BinaryTree<Input>::const_iterator const_iterator;
237
238public:
239  /** \class Mover
240   *  \brief Mover provides the interface for moving iterator forward.
241   *
242   *  Mover is a function object (functor). @ref Mover::move moves
243   *  iterator forward in certain direction. @ref Mover::connect
244   *  connects two nodes of the given iterators togather.
245   */
246  struct Mover {
247    virtual void connect(TreeIteratorBase& pFrom, NodeBase* pTo) const = 0;
248    virtual void move(TreeIteratorBase& pNode) const = 0;
249    virtual ~Mover() { }
250  };
251
252  /** \class Succeeder
253   *  \brief class Succeeder moves the iterator afterward.
254   */
255  struct Succeeder : public Mover {
256    void connect(TreeIteratorBase& pFrom, NodeBase* pTo) const {
257      pFrom.hook<Positional>(pTo);
258    }
259
260    void move(TreeIteratorBase& pNode) const {
261      pNode.move<Positional>();
262    }
263  };
264
265  /** \class Includer
266   *  \brief class Includer moves the iterator downward.
267   */
268  struct Includer : public Mover {
269    void connect(TreeIteratorBase& pFrom, NodeBase* pTo) const {
270      pFrom.hook<Inclusive>(pTo);
271    }
272
273    void move(TreeIteratorBase& pNode) const {
274      pNode.move<Inclusive>();
275    }
276  };
277
278public:
279  static Succeeder Afterward;
280  static Includer  Downward;
281
282public:
283
284  using BinTreeTy::merge;
285
286  // -----  modify  ----- //
287  template<size_t DIRECT>
288  InputTree& enterGroup(TreeIteratorBase pRoot);
289
290  template<size_t DIRECT>
291  InputTree& insert(TreeIteratorBase pRoot,
292                    Input& pInput);
293
294  InputTree& merge(TreeIteratorBase pRoot,
295                   const Mover& pMover,
296                   InputTree& pTree);
297
298  InputTree& insert(TreeIteratorBase pRoot,
299                    const Mover& pMover,
300                    Input& pInput);
301
302  InputTree& enterGroup(TreeIteratorBase pRoot,
303                        const Mover& pMover);
304
305};
306
307bool isGroup(const InputTree::iterator& pos);
308bool isGroup(const InputTree::const_iterator& pos);
309bool isGroup(const InputTree::dfs_iterator& pos);
310bool isGroup(const InputTree::const_dfs_iterator& pos);
311bool isGroup(const InputTree::bfs_iterator& pos);
312bool isGroup(const InputTree::const_bfs_iterator& pos);
313
314} // namespace of mcld
315
316//===----------------------------------------------------------------------===//
317// template member functions
318//===----------------------------------------------------------------------===//
319template<size_t DIRECT>
320mcld::InputTree&
321mcld::InputTree::enterGroup(mcld::TreeIteratorBase pRoot)
322{
323  BinTreeTy::node_type* node = createNode();
324
325  if (pRoot.isRoot())
326    pRoot.hook<TreeIteratorBase::Leftward>(node);
327  else
328    pRoot.hook<DIRECT>(node);
329
330  return *this;
331}
332
333template<size_t DIRECT>
334mcld::InputTree& mcld::InputTree::insert(mcld::TreeIteratorBase pRoot,
335	                                 mcld::Input& pInput)
336{
337  BinTreeTy::node_type* node = createNode();
338  node->data = &pInput;
339
340  if (pRoot.isRoot())
341    pRoot.hook<TreeIteratorBase::Leftward>(node);
342  else
343    pRoot.hook<DIRECT>(node);
344
345  return *this;
346}
347
348#endif
349
350