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