1//===- SectionMap.cpp -----------------------------------------------------===//
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#include <mcld/Object/SectionMap.h>
10#include <mcld/Script/Assignment.h>
11#include <mcld/Script/WildcardPattern.h>
12#include <mcld/Script/StringList.h>
13#include <mcld/Script/Operand.h>
14#include <mcld/Script/Operator.h>
15#include <mcld/Script/RpnExpr.h>
16#include <mcld/LD/LDSection.h>
17#include <mcld/LD/SectionData.h>
18#include <mcld/Fragment/NullFragment.h>
19#include <llvm/Support/Casting.h>
20#include <cassert>
21#include <cstring>
22#include <climits>
23#if !defined(MCLD_ON_WIN32)
24#include <fnmatch.h>
25#define fnmatch0(pattern,string) (fnmatch(pattern,string,0) == 0)
26#else
27#include <windows.h>
28#include <shlwapi.h>
29#define fnmatch0(pattern,string) (PathMatchSpec(string, pattern) == true)
30#endif
31
32using namespace mcld;
33//===----------------------------------------------------------------------===//
34// SectionMap::Input
35//===----------------------------------------------------------------------===//
36SectionMap::Input::Input(const std::string& pName,
37                         InputSectDesc::KeepPolicy pPolicy)
38  : m_Policy(pPolicy)
39{
40  m_Spec.m_pWildcardFile =
41    WildcardPattern::create("*", WildcardPattern::SORT_NONE);
42  m_Spec.m_pExcludeFiles = NULL;
43
44  StringList* sections = StringList::create();
45  sections->push_back(
46    WildcardPattern::create(pName, WildcardPattern::SORT_NONE));
47  m_Spec.m_pWildcardSections = sections;
48
49  m_pSection = LDSection::Create(pName, LDFileFormat::TEXT, 0, 0);
50  SectionData* sd = SectionData::Create(*m_pSection);
51  m_pSection->setSectionData(sd);
52  new NullFragment(sd);
53  new NullFragment(sd);
54}
55
56SectionMap::Input::Input(const InputSectDesc& pInputDesc)
57  : m_Policy(pInputDesc.policy())
58{
59  m_Spec.m_pWildcardFile = pInputDesc.spec().m_pWildcardFile;
60  m_Spec.m_pExcludeFiles = pInputDesc.spec().m_pExcludeFiles;
61  m_Spec.m_pWildcardSections = pInputDesc.spec().m_pWildcardSections;
62  m_pSection = LDSection::Create("", LDFileFormat::TEXT, 0, 0);
63  SectionData* sd = SectionData::Create(*m_pSection);
64  m_pSection->setSectionData(sd);
65  new NullFragment(sd);
66  new NullFragment(sd);
67}
68
69//===----------------------------------------------------------------------===//
70// SectionMap::Output
71//===----------------------------------------------------------------------===//
72SectionMap::Output::Output(const std::string& pName)
73  : m_Name(pName),
74    m_Order(UINT_MAX)
75{
76  m_Prolog.m_pVMA = NULL;
77  m_Prolog.m_Type = OutputSectDesc::LOAD;
78  m_Prolog.m_pLMA = NULL;
79  m_Prolog.m_pAlign = NULL;
80  m_Prolog.m_pSubAlign = NULL;
81  m_Prolog.m_Constraint = OutputSectDesc::NO_CONSTRAINT;
82
83  m_Epilog.m_pRegion = NULL;
84  m_Epilog.m_pLMARegion = NULL;
85  m_Epilog.m_pPhdrs = NULL;
86  m_Epilog.m_pFillExp = NULL;
87
88  m_pSection = LDSection::Create(pName, LDFileFormat::TEXT, 0, 0);
89  SectionData* sd = SectionData::Create(*m_pSection);
90  m_pSection->setSectionData(sd);
91
92  m_bIsDiscard = pName.compare("/DISCARD/") == 0;
93}
94
95SectionMap::Output::Output(const OutputSectDesc& pOutputDesc)
96  : m_Name(pOutputDesc.name()),
97    m_Prolog(pOutputDesc.prolog()),
98    m_Epilog(pOutputDesc.epilog()),
99    m_Order(UINT_MAX)
100{
101  m_pSection = LDSection::Create(m_Name, LDFileFormat::TEXT, 0, 0);
102  SectionData* sd = SectionData::Create(*m_pSection);
103  m_pSection->setSectionData(sd);
104
105  m_bIsDiscard = m_Name.compare("/DISCARD/") == 0;
106}
107
108bool SectionMap::Output::hasContent() const
109{
110  return m_pSection != NULL && m_pSection->size() != 0;
111}
112
113SectionMap::Output::const_dot_iterator
114SectionMap::Output::find_first_explicit_dot() const
115{
116  for (const_dot_iterator it = dot_begin(), ie = dot_end(); it != ie; ++it) {
117    if ((*it).type() == Assignment::DEFAULT)
118      return it;
119  }
120  return dot_end();
121}
122
123SectionMap::Output::dot_iterator SectionMap::Output::find_first_explicit_dot()
124{
125  for (dot_iterator it = dot_begin(), ie = dot_end(); it != ie; ++it) {
126    if ((*it).type() == Assignment::DEFAULT)
127      return it;
128  }
129  return dot_end();
130}
131
132SectionMap::Output::const_dot_iterator
133SectionMap::Output::find_last_explicit_dot() const
134{
135  typedef DotAssignments::const_reverse_iterator CONST_RIT;
136  for (CONST_RIT rit = dotAssignments().rbegin(), rie = dotAssignments().rend();
137    rit != rie; ++rit) {
138    if ((*rit).type() == Assignment::DEFAULT) {
139      return dot_begin() +
140             (dotAssignments().size() - (rit - dotAssignments().rbegin()) - 1);
141    }
142  }
143  return dot_end();
144}
145
146SectionMap::Output::dot_iterator SectionMap::Output::find_last_explicit_dot()
147{
148  typedef DotAssignments::reverse_iterator RIT;
149  for (RIT rit = dotAssignments().rbegin(), rie = dotAssignments().rend();
150    rit != rie; ++rit) {
151    if ((*rit).type() == Assignment::DEFAULT) {
152      return dot_begin() +
153             (dotAssignments().size() - (rit - dotAssignments().rbegin()) - 1);
154    }
155  }
156  return dot_end();
157}
158
159//===----------------------------------------------------------------------===//
160// SectionMap
161//===----------------------------------------------------------------------===//
162SectionMap::~SectionMap()
163{
164  iterator out, outBegin = begin(), outEnd = end();
165  for (out = outBegin; out != outEnd; ++out) {
166    if (*out != NULL) {
167      Output::iterator in, inBegin = (*out)->begin(), inEnd = (*out)->end();
168      for (in = inBegin; in != inEnd; ++in) {
169        if (*in != NULL)
170          delete *in;
171      }
172      delete *out;
173    }
174  }
175}
176
177SectionMap::const_mapping
178SectionMap::find(const std::string& pInputFile,
179                 const std::string& pInputSection) const
180{
181  const_iterator out, outBegin = begin(), outEnd = end();
182  for (out = outBegin; out != outEnd; ++out) {
183    Output::const_iterator in, inBegin = (*out)->begin(), inEnd = (*out)->end();
184    for (in = inBegin; in != inEnd; ++in) {
185      if (matched(**in, pInputFile, pInputSection))
186        return std::make_pair(*out, *in);
187    }
188  }
189  return std::make_pair((const Output*)NULL, (const Input*)NULL);
190}
191
192SectionMap::mapping SectionMap::find(const std::string& pInputFile,
193                                     const std::string& pInputSection)
194{
195  iterator out, outBegin = begin(), outEnd = end();
196  for (out = outBegin; out != outEnd; ++out) {
197    Output::iterator in, inBegin = (*out)->begin(), inEnd = (*out)->end();
198    for (in = inBegin; in != inEnd; ++in) {
199      if (matched(**in, pInputFile, pInputSection))
200        return std::make_pair(*out, *in);
201    }
202  }
203  return std::make_pair((Output*)NULL, (Input*)NULL);
204}
205
206SectionMap::const_iterator
207SectionMap::find(const std::string& pOutputSection) const
208{
209  const_iterator out, outBegin = begin(), outEnd = end();
210  for (out = outBegin; out != outEnd; ++out) {
211    if ((*out)->name().compare(pOutputSection) == 0)
212      return out;
213  }
214  return outEnd;
215}
216
217SectionMap::iterator
218SectionMap::find(const std::string& pOutputSection)
219{
220  iterator out, outBegin = begin(), outEnd = end();
221  for (out = outBegin; out != outEnd; ++out) {
222    if ((*out)->name().compare(pOutputSection) == 0)
223      return out;
224  }
225  return outEnd;
226}
227
228std::pair<SectionMap::mapping, bool>
229SectionMap::insert(const std::string& pInputSection,
230                   const std::string& pOutputSection,
231                   InputSectDesc::KeepPolicy pPolicy)
232{
233  iterator out, outBegin = begin(), outEnd = end();
234  for (out = outBegin; out != outEnd; ++out) {
235    if ((*out)->name().compare(pOutputSection) == 0)
236      break;
237  }
238  if (out != end()) {
239    Output::iterator in, inBegin = (*out)->begin(), inEnd = (*out)->end();
240    for (in = inBegin; in != inEnd; ++in) {
241      if ((*in)->getSection()->name().compare(pInputSection) == 0)
242        break;
243    }
244
245    if (in != (*out)->end()) {
246      return std::make_pair(std::make_pair(*out, *in), false);
247    } else {
248      Input* input = new Input(pInputSection, pPolicy);
249      (*out)->append(input);
250      return std::make_pair(std::make_pair(*out, input), true);
251    }
252  }
253
254  Output* output = new Output(pOutputSection);
255  m_OutputDescList.push_back(output);
256  Input* input = new Input(pInputSection, pPolicy);
257  output->append(input);
258
259  return std::make_pair(std::make_pair(output, input), true);
260}
261
262std::pair<SectionMap::mapping, bool>
263SectionMap::insert(const InputSectDesc& pInputDesc,
264                   const OutputSectDesc& pOutputDesc)
265{
266  iterator out, outBegin = begin(), outEnd = end();
267  for (out = outBegin; out != outEnd; ++out) {
268    if ((*out)->name().compare(pOutputDesc.name()) == 0 &&
269        (*out)->prolog() == pOutputDesc.prolog() &&
270        (*out)->epilog() == pOutputDesc.epilog())
271      break;
272  }
273
274  if (out != end()) {
275    Output::iterator in, inBegin = (*out)->begin(), inEnd = (*out)->end();
276    for (in = inBegin; in != inEnd; ++in) {
277      if ((*in)->policy() == pInputDesc.policy() &&
278          (*in)->spec() == pInputDesc.spec())
279        break;
280    }
281
282    if (in != (*out)->end()) {
283      return std::make_pair(std::make_pair(*out, *in), false);
284    } else {
285      Input* input = new Input(pInputDesc);
286      (*out)->append(input);
287      return std::make_pair(std::make_pair(*out, input), true);
288    }
289  }
290
291  Output* output = new Output(pOutputDesc);
292  m_OutputDescList.push_back(output);
293  Input* input = new Input(pInputDesc);
294  output->append(input);
295
296  return std::make_pair(std::make_pair(output, input), true);
297}
298
299SectionMap::iterator
300SectionMap::insert(iterator pPosition, LDSection* pSection)
301{
302  Output* output = new Output(pSection->name());
303  output->append(new Input(pSection->name(), InputSectDesc::NoKeep));
304  output->setSection(pSection);
305  return m_OutputDescList.insert(pPosition, output);
306}
307
308bool SectionMap::matched(const SectionMap::Input& pInput,
309                         const std::string& pInputFile,
310                         const std::string& pInputSection) const
311{
312  if (pInput.spec().hasFile() && !matched(pInput.spec().file(), pInputFile))
313      return false;
314
315  if (pInput.spec().hasExcludeFiles()) {
316    StringList::const_iterator file, fileEnd;
317    fileEnd = pInput.spec().excludeFiles().end();
318    for (file = pInput.spec().excludeFiles().begin(); file != fileEnd; ++file) {
319      if (matched(llvm::cast<WildcardPattern>(**file), pInputFile)) {
320        return false;
321      }
322    }
323  }
324
325  if (pInput.spec().hasSections()) {
326    StringList::const_iterator sect, sectEnd = pInput.spec().sections().end();
327    for (sect = pInput.spec().sections().begin(); sect != sectEnd; ++sect) {
328      if (matched(llvm::cast<WildcardPattern>(**sect), pInputSection)) {
329        return true;
330      }
331    }
332  }
333
334  return false;
335}
336
337bool SectionMap::matched(const WildcardPattern& pPattern,
338                         const std::string& pName) const
339{
340  if (pPattern.isPrefix()) {
341    llvm::StringRef name(pName);
342    return name.startswith(pPattern.prefix());
343  } else {
344    return fnmatch0(pPattern.name().c_str(), pName.c_str());
345  }
346}
347
348// fixupDotSymbols - ensure the dot symbols are valid
349void SectionMap::fixupDotSymbols()
350{
351  for (iterator it = begin() + 1, ie = end(); it != ie; ++it) {
352    // fixup the 1st explicit dot assignment if needed
353    if (!(*it)->dotAssignments().empty()) {
354      Output::dot_iterator dot = (*it)->find_first_explicit_dot();
355      if (dot != (*it)->dot_end() &&
356          (*dot).symbol().isDot() &&
357          (*dot).getRpnExpr().hasDot()) {
358        Assignment assign(Assignment::OUTPUT_SECTION,
359                          Assignment::DEFAULT,
360                          *SymOperand::create("."),
361                          *RpnExpr::buildHelperExpr(it - 1));
362        Output::dot_iterator ref = (*it)->dotAssignments().insert(dot, assign);
363        for (RpnExpr::iterator tok = (*dot).getRpnExpr().begin(),
364          tokEnd = (*dot).getRpnExpr().end();  tok != tokEnd; ++tok) {
365          if ((*tok)->kind() == ExprToken::OPERAND &&
366              llvm::cast<Operand>(*tok)->isDot())
367            *tok = &((*ref).symbol());
368        } // for each token in the RHS expr of the dot assignment
369      }
370    }
371
372    // fixup dot in output VMA if needed
373    if ((*it)->prolog().hasVMA() && (*it)->prolog().vma().hasDot()) {
374      Output::dot_iterator dot = (*it)->find_last_explicit_dot();
375      if (dot == (*it)->dot_end()) {
376        Assignment assign(Assignment::OUTPUT_SECTION,
377                          Assignment::DEFAULT,
378                          *SymOperand::create("."),
379                          *RpnExpr::buildHelperExpr(it - 1));
380        dot = (*it)->dotAssignments().insert(dot, assign);
381      }
382      for (RpnExpr::iterator tok = (*it)->prolog().vma().begin(),
383        tokEnd = (*it)->prolog().vma().end();  tok != tokEnd; ++tok) {
384        if ((*tok)->kind() == ExprToken::OPERAND &&
385            llvm::cast<Operand>(*tok)->isDot())
386          *tok = &((*dot).symbol());
387      } // for each token in the RHS expr of the dot assignment
388    }
389
390  } // for each output section
391}
392