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