1/* Copyright (c) 2008-2010, Google Inc.
2 * All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions are
6 * met:
7 *
8 *     * Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 *     * Neither the name of Google Inc. nor the names of its
11 * contributors may be used to endorse or promote products derived from
12 * this software without specific prior written permission.
13 *
14 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
15 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
16 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
17 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
18 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
19 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
20 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
21 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
22 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
24 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 */
26
27// This file is part of ThreadSanitizer, a dynamic data race detector.
28// Author: Evgeniy Stepanov.
29
30// This file contains the parser for valgrind-compatible suppressions.
31
32#include "suppressions.h"
33
34// TODO(eugenis): convert checks to warning messages.
35// TODO(eugenis): write tests for incorrect syntax.
36
37enum LocationType {
38  LT_STAR,  // ...
39  LT_OBJ,  // obj:
40  LT_FUN,  // fun:
41};
42
43struct Location {
44  LocationType type;
45  string name;
46};
47
48struct StackTraceTemplate {
49  vector<Location> locations;
50};
51
52struct Suppression {
53  string name;
54  set<string> tools;
55  string warning_name;
56  // Extra information available for some suppression types.
57  // ex.: Memcheck:Param
58  string extra;
59  vector<StackTraceTemplate> templates;
60};
61
62class Parser {
63 public:
64  explicit Parser(const string &str)
65      : buffer_(str), next_(buffer_.c_str()),
66        end_(buffer_.c_str() + buffer_.size()), line_no_(0), error_(false) {}
67
68  bool NextSuppression(Suppression* suppression);
69  bool GetError();
70  string GetErrorString();
71  int GetLineNo();
72
73 private:
74  bool Eof() { return next_ >= end_; }
75  string NextLine();
76  string NextLineSkipComments();
77  void PutBackSkipComments(string line);
78  bool ParseSuppressionToolsLine(Suppression* supp, string line);
79  bool IsExtraLine(string line);
80  bool ParseStackTraceLine(StackTraceTemplate* trace, string line);
81  bool NextStackTraceTemplate(StackTraceTemplate* trace, bool* last);
82
83  void SetError(string desc);
84
85  const string& buffer_;
86  const char* next_;
87  const char* end_;
88  stack<string> put_back_stack_;
89
90  int line_no_;
91  bool error_;
92  string error_string_;
93};
94
95#define PARSER_CHECK(cond, desc) do {\
96    if (!(cond)) {\
97      SetError(desc);\
98      return false;\
99    }} while ((void)0, 0)
100
101void Parser::SetError(string desc) {
102  error_ = true;
103  error_string_ = desc;
104}
105
106bool Parser::GetError() {
107  return error_;
108}
109
110string Parser::GetErrorString() {
111  return error_string_;
112}
113
114int Parser::GetLineNo() {
115  return line_no_;
116}
117
118string Parser::NextLine() {
119  const char* first = next_;
120  while (!Eof() && *next_ != '\n') {
121    ++next_;
122  }
123  string line(first, next_ - first);
124  if (*next_ == '\n') {
125    ++next_;
126  }
127  ++line_no_;
128  return line;
129}
130
131string Parser::NextLineSkipComments() {
132  string line;
133  if (!put_back_stack_.empty()) {
134    line = put_back_stack_.top();
135    put_back_stack_.pop();
136    return line;
137  }
138  while (!Eof()) {
139    line = NextLine();
140    // Skip empty lines.
141    if (line.empty())
142      continue;
143    // Skip comments.
144    if (line[0] == '#')
145      continue;
146    const char* p = line.c_str();
147    const char* e = p + line.size();
148    // Strip whitespace.
149    while (p < e && (*p == ' ' || *p == '\t'))
150      ++p;
151    if (p >= e)
152      continue;
153    const char* last = e - 1;
154    while (last > p && (*last == ' ' || *last == '\t'))
155      --last;
156    return string(p, last - p + 1);
157  }
158  return "";
159}
160
161void Parser::PutBackSkipComments(string line) {
162  put_back_stack_.push(line);
163}
164
165bool Parser::ParseSuppressionToolsLine(Suppression* supp, string line) {
166  size_t idx = line.find(':');
167  PARSER_CHECK(idx != string::npos, "expected ':' in tools line");
168  string s1 = line.substr(0, idx);
169  string s2 = line.substr(idx + 1);
170  PARSER_CHECK(!s1.empty(), "expected non-empty tool(s) name");
171  PARSER_CHECK(!s2.empty(), "expected non-empty warning name");
172  size_t idx2;
173  while ((idx2 = s1.find(',')) != string::npos) {
174    supp->tools.insert(s1.substr(0, idx2));
175    s1.erase(0, idx2 + 1);
176  }
177  supp->tools.insert(s1);
178  supp->warning_name = s2;
179  return true;
180}
181
182bool Parser::ParseStackTraceLine(StackTraceTemplate* trace, string line) {
183  if (line == "...") {
184    Location location = {LT_STAR, ""};
185    trace->locations.push_back(location);
186    return true;
187  } else {
188    size_t idx = line.find(':');
189    PARSER_CHECK(idx != string::npos, "expected ':' in stack trace line");
190    string s1 = line.substr(0, idx);
191    string s2 = line.substr(idx + 1);
192    if (s1 == "obj") {
193      Location location = {LT_OBJ, s2};
194      trace->locations.push_back(location);
195      return true;
196    } else if (s1 == "fun") {
197      Location location = {LT_FUN, s2};
198      // A suppression frame can only have ( or ) if it comes from Objective-C,
199      // i.e. starts with +[ or -[ or =[
200      PARSER_CHECK(s2.find_first_of("()") == string::npos ||
201                   (s2[1] == '[' && strchr("+-=", s2[0]) != NULL),
202                   "'fun:' lines can't contain '()'");
203
204      // Check that we don't have template arguments in the suppression.
205      {
206        // Caveat: don't be confused by "operator>>" and similar...
207        size_t checked_till = 0;
208        // List of possible >>-like operators, sorted by the operation length.
209        const char *OP[] = {">>=", "<<=",
210                            ">>", "<<",
211                            ">=", "<=",
212                            "->", "->*",
213                            "<", ">"};
214        bool check_failed = false;
215        while (!check_failed && checked_till < s2.size()) {
216          size_t next = s2.find_first_of("<>", checked_till);
217          if (next == string::npos)
218            break;
219
220          if (next < 8) {
221            // operatorX won't fit
222            check_failed = true;
223            break;
224          }
225
226          for (size_t i = 0; i < TS_ARRAY_SIZE(OP); i++) {
227            size_t op_offset = ((string)OP[i]).find(s2[next]);
228            if (op_offset == string::npos)
229              continue;
230            if (next >= 8 + op_offset &&
231                "operator" == s2.substr(next- (8 + op_offset), 8) &&
232                OP[i] == s2.substr(next- op_offset, strlen(OP[i]))) {
233              checked_till = next + strlen(OP[i] + op_offset);
234              break;
235            }
236          }
237        }
238
239        PARSER_CHECK(!check_failed, "'fun:' lines can't contain '<' or '>' "
240                     "except for operators");
241      }
242
243      trace->locations.push_back(location);
244      return true;
245    } else {
246      SetError("bad stack trace line");
247      return false;
248    }
249  }
250}
251
252// Checks if this line can not be parsed by Parser::NextStackTraceTemplate
253// and, therefore, is an extra information for the suppression.
254bool Parser::IsExtraLine(string line) {
255  if (line == "..." || line == "{" || line == "}")
256    return false;
257  if (line.size() < 4)
258    return true;
259  string prefix = line.substr(0, 4);
260  return !(prefix == "obj:" || prefix == "fun:");
261}
262
263bool Parser::NextStackTraceTemplate(StackTraceTemplate* trace,
264    bool* last_stack_trace) {
265  string line = NextLineSkipComments();
266  if (line == "}") {  // No more stack traces in multi-trace syntax
267    *last_stack_trace = true;
268    return false;
269  }
270
271  if (line == "{") {  // A multi-trace syntax
272    line = NextLineSkipComments();
273  } else {
274    *last_stack_trace = true;
275  }
276
277  while (true) {
278    if (!ParseStackTraceLine(trace, line))
279      return false;
280    line = NextLineSkipComments();
281    if (line == "}")
282      break;
283  }
284  return true;
285}
286
287bool Parser::NextSuppression(Suppression* supp) {
288  string line;
289  line = NextLineSkipComments();
290  if (line.empty())
291    return false;
292  // Opening {
293  PARSER_CHECK(line == "{", "expected '{'");
294  // Suppression name.
295  line = NextLineSkipComments();
296  PARSER_CHECK(!line.empty(), "expected suppression name");
297  supp->name = line;
298  // tool[,tool]:warning_name.
299  line = NextLineSkipComments();
300  PARSER_CHECK(!line.empty(), "expected tool[, tool]:warning_name line");
301  if (!ParseSuppressionToolsLine(supp, line))
302    return false;
303  if (0) {  // Not used currently. May still be needed later.
304    // A possible extra line.
305    line = NextLineSkipComments();
306    if (IsExtraLine(line))
307      supp->extra = line;
308    else
309      PutBackSkipComments(line);
310  }
311  // Everything else.
312  bool done = false;
313  while (!done) {
314    StackTraceTemplate trace;
315    if (NextStackTraceTemplate(&trace, &done))
316      supp->templates.push_back(trace);
317    if (error_)
318      return false;
319  }
320  // TODO(eugenis): Do we need to check for empty traces?
321  return true;
322}
323
324struct Suppressions::SuppressionsRep {
325  vector<Suppression> suppressions;
326  string error_string_;
327  int error_line_no_;
328};
329
330Suppressions::Suppressions() : rep_(new SuppressionsRep) {}
331
332Suppressions::~Suppressions() {
333  delete rep_;
334}
335
336int Suppressions::ReadFromString(const string &str) {
337  int sizeBefore = rep_->suppressions.size();
338  Parser parser(str);
339  Suppression supp;
340  while (parser.NextSuppression(&supp)) {
341    rep_->suppressions.push_back(supp);
342  }
343  if (parser.GetError()) {
344    rep_->error_string_ = parser.GetErrorString();
345    rep_->error_line_no_ = parser.GetLineNo();
346    return -1;
347  }
348  return rep_->suppressions.size() - sizeBefore;
349}
350
351string Suppressions::GetErrorString() {
352  return rep_->error_string_;
353}
354
355int Suppressions::GetErrorLineNo() {
356  return rep_->error_line_no_;
357}
358
359struct MatcherContext {
360  MatcherContext(
361      const vector<string>& function_names_mangled_,
362      const vector<string>& function_names_demangled_,
363      const vector<string>& object_names_) :
364      function_names_mangled(function_names_mangled_),
365      function_names_demangled(function_names_demangled_),
366      object_names(object_names_),
367      tmpl(NULL)
368  {}
369
370  const vector<string>& function_names_mangled;
371  const vector<string>& function_names_demangled;
372  const vector<string>& object_names;
373  StackTraceTemplate* tmpl;
374};
375
376static bool MatchStackTraceRecursive(MatcherContext ctx, int trace_index,
377    int tmpl_index) {
378  const int trace_size = ctx.function_names_mangled.size();
379  const int tmpl_size = ctx.tmpl->locations.size();
380  while (trace_index < trace_size && tmpl_index < tmpl_size) {
381    Location& location = ctx.tmpl->locations[tmpl_index];
382    if (location.type == LT_STAR) {
383      ++tmpl_index;
384      while (trace_index < trace_size) {
385        if (MatchStackTraceRecursive(ctx, trace_index++, tmpl_index))
386          return true;
387      }
388      return false;
389    } else {
390      bool match = false;
391      if (location.type == LT_OBJ) {
392        match = StringMatch(location.name, ctx.object_names[trace_index]);
393      } else {
394        CHECK(location.type == LT_FUN);
395        match =
396          StringMatch(location.name, ctx.function_names_mangled[trace_index]) ||
397          StringMatch(location.name, ctx.function_names_demangled[trace_index]);
398      }
399      if (match) {
400        ++trace_index;
401        ++tmpl_index;
402      } else {
403        return false;
404      }
405    }
406  }
407  return tmpl_index == tmpl_size;
408}
409
410bool Suppressions::StackTraceSuppressed(string tool_name, string warning_name,
411    const vector<string>& function_names_mangled,
412    const vector<string>& function_names_demangled,
413    const vector<string>& object_names,
414    string *name_of_suppression) {
415  MatcherContext ctx(function_names_mangled, function_names_demangled,
416      object_names);
417  for (vector<Suppression>::iterator it = rep_->suppressions.begin();
418       it != rep_->suppressions.end(); ++it) {
419    if (it->warning_name != warning_name ||
420        it->tools.find(tool_name) == it->tools.end())
421      continue;
422    for (vector<StackTraceTemplate>::iterator it2 = it->templates.begin();
423         it2 != it->templates.end(); ++it2) {
424      ctx.tmpl = &*it2;
425      bool result = MatchStackTraceRecursive(ctx, 0, 0);
426      if (result) {
427        *name_of_suppression = it->name;
428        return true;
429      }
430    }
431  }
432  return false;
433}
434