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 37 enum LocationType { 38 LT_STAR, // ... 39 LT_OBJ, // obj: 40 LT_FUN, // fun: 41 }; 42 43 struct Location { 44 LocationType type; 45 string name; 46 }; 47 48 struct StackTraceTemplate { 49 vector<Location> locations; 50 }; 51 52 struct 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 62 class 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 101 void Parser::SetError(string desc) { 102 error_ = true; 103 error_string_ = desc; 104 } 105 106 bool Parser::GetError() { 107 return error_; 108 } 109 110 string Parser::GetErrorString() { 111 return error_string_; 112 } 113 114 int Parser::GetLineNo() { 115 return line_no_; 116 } 117 118 string 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 131 string 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 161 void Parser::PutBackSkipComments(string line) { 162 put_back_stack_.push(line); 163 } 164 165 bool 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 182 bool 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. 254 bool 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 263 bool 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 287 bool 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 324 struct Suppressions::SuppressionsRep { 325 vector<Suppression> suppressions; 326 string error_string_; 327 int error_line_no_; 328 }; 329 330 Suppressions::Suppressions() : rep_(new SuppressionsRep) {} 331 332 Suppressions::~Suppressions() { 333 delete rep_; 334 } 335 336 int 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 351 string Suppressions::GetErrorString() { 352 return rep_->error_string_; 353 } 354 355 int Suppressions::GetErrorLineNo() { 356 return rep_->error_line_no_; 357 } 358 359 struct 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 376 static 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 410 bool 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