1//===- DefSymParser.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/Support/DefSymParser.h>
10#include <mcld/Support/MsgHandling.h>
11#include <mcld/LD/LDSymbol.h>
12
13using namespace llvm;
14using namespace mcld;
15
16DefSymParser::DefSymParser(const Module& pModule)
17  : m_Module(pModule) {
18}
19
20// passing a valid operator will return a number whose quantity relative
21// to other such obtained quantities will give the priority of the operator
22static inline int precedence(const char* x)
23{
24  switch (*x) {
25    case '-' :
26    case '+' : return 0;
27    case '/' :
28    case '*' : return 1;
29    default  : assert("Unsupported operator specified");
30  }
31  return 0;
32}
33
34bool DefSymParser::parse(StringRef pExpr, uint64_t& pSymVal)
35{
36  std::stack<const char*> operatorStack;
37  std::stack<unsigned long> operandStack;
38  unsigned long operand1 = 0,
39                operand2 = 0,
40                result = 0;
41  std::string token;
42  std::vector<std::string> postfixString;
43  std::vector<std::string>::iterator it;
44  llvm::StringRef::iterator si = pExpr.begin();
45
46  // Implement a modified Shunting Yard algorithm to form a RPN of the
47  // given expression
48  while (si != pExpr.end()) {
49    if (*si == '+' || *si == '-' || *si == '*' || *si == '/') {
50      if (token.empty() && (*si == '+' || *si == '-'))
51        // we have a case such as a++b or a+-b or a-+b
52        // pushing 0 when a token begins with a + or - operator
53        // solves unary operator problem
54        token = "0";
55      // An operator encountered means a token ended, push it to
56      // postfix string queue.
57      postfixString.push_back(token);
58      token.clear();
59
60      if (operatorStack.empty()) {
61        operatorStack.push(si);
62      }
63      else {
64        if (precedence(si) <= precedence(operatorStack.top())) {
65          // if the precedence of incoming operator is less or equal to
66          // top of stack, we clear stack till top is lower precedence
67          // or its empty
68          while (!operatorStack.empty()) {
69            if (precedence(si) <= precedence(operatorStack.top())) {
70            postfixString.push_back(std::string(operatorStack.top(),1));
71            operatorStack.pop();
72            }
73            else {
74              break;
75            }
76          }
77        }
78        operatorStack.push(si);
79      }
80      si++;
81      continue;
82    }
83    // keep reading the token when there is no operator encountered
84    token += *si;
85    si++;
86  }
87  postfixString.push_back(token);
88  // pop off any remaining operators from operator stack
89  while (!operatorStack.empty()) {
90    postfixString.push_back(std::string(operatorStack.top(),1));
91    operatorStack.pop();
92  }
93  //evaluate the postfix expression written above
94
95  for (it=postfixString.begin(); it != postfixString.end(); it++) {
96    switch (*((*it).c_str())) {
97      case '*':
98      case '-':
99      case '+':
100      case '/':
101        // when postfix string has an operator, pop first two operands from
102        // operand stack, use them in evaluate expression and push result
103        // back to stack
104        assert(!operandStack.empty() && "Invalid expression: extra operand");
105        operand2 = operandStack.top();
106        operandStack.pop();
107        operand1 = operandStack.top();
108        operandStack.pop();
109        if (*((*it).c_str()) == '*')
110          result = operand1 * operand2;
111        else if (*((*it).c_str()) == '/')
112          result = operand1 / operand2;
113        else if (*((*it).c_str()) == '-')
114          result = operand1 - operand2;
115        else
116          result = operand1 + operand2;
117        operandStack.push(result);
118        break;
119      default:
120        // if the string encountered in postfix queue is a string
121        // try converting it to integer.
122        llvm::StringRef stringOperand(*it);
123        if(stringOperand.getAsInteger(0,result)) {
124          // the integer conversion failed means the token is a symbol
125          // or its invalid if the NamePool has no such symbol;
126          const LDSymbol* symbol =
127                              m_Module.getNamePool().findSymbol(stringOperand);
128
129          if (!symbol)
130            fatal(diag::fail_sym_resolution)
131                  << __FILE__ << __LINE__
132                  << "mclinker@googlegroups.com" ;
133          result = symbol->value();
134        }
135        operandStack.push(result);
136    }
137  }
138  // once complete queue is processed, stack top is result
139  pSymVal = operandStack.top();
140  return true;
141}
142