Evgeniy Stepanov | bec2f0e | 2011-03-05 12:50:33 +0300 | [diff] [blame] | 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 "common_util.h" |
| 33 | #include "ts_util.h" |
| 34 | |
| 35 | #include "suppressions.h" |
| 36 | |
| 37 | // TODO(eugenis): convert checks to warning messages. |
| 38 | // TODO(eugenis): write tests for incorrect syntax. |
| 39 | |
| 40 | enum LocationType { |
| 41 | LT_STAR, // ... |
| 42 | LT_OBJ, // obj: |
| 43 | LT_FUN, // fun: |
| 44 | }; |
| 45 | |
| 46 | struct Location { |
| 47 | LocationType type; |
| 48 | string name; |
| 49 | }; |
| 50 | |
| 51 | struct StackTraceTemplate { |
| 52 | vector<Location> locations; |
| 53 | }; |
| 54 | |
| 55 | struct Suppression { |
| 56 | string name; |
| 57 | set<string> tools; |
| 58 | string warning_name; |
| 59 | // Extra information available for some suppression types. |
| 60 | // ex.: Memcheck:Param |
| 61 | string extra; |
| 62 | vector<StackTraceTemplate> templates; |
| 63 | }; |
| 64 | |
| 65 | class Parser { |
| 66 | public: |
| 67 | explicit Parser(const string &str) |
| 68 | : buffer_(str), next_(buffer_.c_str()), |
| 69 | end_(buffer_.c_str() + buffer_.size()), line_no_(0), error_(false) {} |
| 70 | |
| 71 | bool NextSuppression(Suppression* suppression); |
| 72 | bool GetError(); |
| 73 | string GetErrorString(); |
| 74 | int GetLineNo(); |
| 75 | |
| 76 | private: |
| 77 | bool Eof() { return next_ >= end_; } |
| 78 | string NextLine(); |
| 79 | string NextLineSkipComments(); |
| 80 | void PutBackSkipComments(string line); |
| 81 | bool ParseSuppressionToolsLine(Suppression* supp, string line); |
| 82 | bool IsExtraLine(string line); |
| 83 | bool ParseStackTraceLine(StackTraceTemplate* trace, string line); |
| 84 | bool NextStackTraceTemplate(StackTraceTemplate* trace, bool* last); |
| 85 | |
| 86 | void SetError(string desc); |
| 87 | |
| 88 | const string& buffer_; |
| 89 | const char* next_; |
| 90 | const char* end_; |
| 91 | stack<string> put_back_stack_; |
| 92 | |
| 93 | int line_no_; |
| 94 | bool error_; |
| 95 | string error_string_; |
| 96 | }; |
| 97 | |
| 98 | #define PARSER_CHECK(cond, desc) do {\ |
| 99 | if (!(cond)) {\ |
| 100 | SetError(desc);\ |
| 101 | return false;\ |
| 102 | }} while (0) |
| 103 | |
| 104 | void Parser::SetError(string desc) { |
| 105 | error_ = true; |
| 106 | error_string_ = desc; |
| 107 | } |
| 108 | |
| 109 | bool Parser::GetError() { |
| 110 | return error_; |
| 111 | } |
| 112 | |
| 113 | string Parser::GetErrorString() { |
| 114 | return error_string_; |
| 115 | } |
| 116 | |
| 117 | int Parser::GetLineNo() { |
| 118 | return line_no_; |
| 119 | } |
| 120 | |
| 121 | string Parser::NextLine() { |
| 122 | const char* first = next_; |
| 123 | while (!Eof() && *next_ != '\n') { |
| 124 | ++next_; |
| 125 | } |
| 126 | string line(first, next_ - first); |
| 127 | if (*next_ == '\n') { |
| 128 | ++next_; |
| 129 | } |
| 130 | ++line_no_; |
| 131 | return line; |
| 132 | } |
| 133 | |
| 134 | string Parser::NextLineSkipComments() { |
| 135 | string line; |
| 136 | if (!put_back_stack_.empty()) { |
| 137 | line = put_back_stack_.top(); |
| 138 | put_back_stack_.pop(); |
| 139 | return line; |
| 140 | } |
| 141 | while (!Eof()) { |
| 142 | line = NextLine(); |
| 143 | // Skip empty lines. |
| 144 | if (line.empty()) |
| 145 | continue; |
| 146 | // Skip comments. |
| 147 | if (line[0] == '#') |
| 148 | continue; |
| 149 | const char* p = line.c_str(); |
| 150 | const char* e = p + line.size(); |
| 151 | // Strip whitespace. |
| 152 | while (p < e && (*p == ' ' || *p == '\t')) |
| 153 | ++p; |
| 154 | if (p >= e) |
| 155 | continue; |
| 156 | const char* last = e - 1; |
| 157 | while (last > p && (*last == ' ' || *last == '\t')) |
| 158 | --last; |
| 159 | return string(p, last - p + 1); |
| 160 | } |
| 161 | return ""; |
| 162 | } |
| 163 | |
| 164 | void Parser::PutBackSkipComments(string line) { |
| 165 | put_back_stack_.push(line); |
| 166 | } |
| 167 | |
| 168 | bool Parser::ParseSuppressionToolsLine(Suppression* supp, string line) { |
| 169 | size_t idx = line.find(':'); |
| 170 | PARSER_CHECK(idx != string::npos, "expected ':' in tools line"); |
| 171 | string s1 = line.substr(0, idx); |
| 172 | string s2 = line.substr(idx + 1); |
| 173 | PARSER_CHECK(!s1.empty(), "expected non-empty tool(s) name"); |
| 174 | PARSER_CHECK(!s2.empty(), "expected non-empty warning name"); |
| 175 | size_t idx2; |
| 176 | while ((idx2 = s1.find(',')) != string::npos) { |
| 177 | supp->tools.insert(s1.substr(0, idx2)); |
| 178 | s1.erase(0, idx2 + 1); |
| 179 | } |
| 180 | supp->tools.insert(s1); |
| 181 | supp->warning_name = s2; |
| 182 | return true; |
| 183 | } |
| 184 | |
| 185 | bool Parser::ParseStackTraceLine(StackTraceTemplate* trace, string line) { |
| 186 | if (line == "...") { |
| 187 | Location location = {LT_STAR, ""}; |
| 188 | trace->locations.push_back(location); |
| 189 | return true; |
| 190 | } else { |
| 191 | size_t idx = line.find(':'); |
| 192 | PARSER_CHECK(idx != string::npos, "expected ':' in stack trace line"); |
| 193 | string s1 = line.substr(0, idx); |
| 194 | string s2 = line.substr(idx + 1); |
| 195 | if (s1 == "obj") { |
| 196 | Location location = {LT_OBJ, s2}; |
| 197 | trace->locations.push_back(location); |
| 198 | return true; |
| 199 | } else if (s1 == "fun") { |
| 200 | Location location = {LT_FUN, s2}; |
| 201 | trace->locations.push_back(location); |
| 202 | return true; |
| 203 | } else { |
| 204 | SetError("bad stack trace line"); |
| 205 | return false; |
| 206 | } |
| 207 | } |
| 208 | } |
| 209 | |
| 210 | // Checks if this line can not be parsed by Parser::NextStackTraceTemplate |
| 211 | // and, therefore, is an extra information for the suppression. |
| 212 | bool Parser::IsExtraLine(string line) { |
| 213 | if (line == "..." || line == "{" || line == "}") |
| 214 | return false; |
| 215 | if (line.size() < 4) |
| 216 | return true; |
| 217 | string prefix = line.substr(0, 4); |
| 218 | return !(prefix == "obj:" || prefix == "fun:"); |
| 219 | } |
| 220 | |
| 221 | bool Parser::NextStackTraceTemplate(StackTraceTemplate* trace, |
| 222 | bool* last_stack_trace) { |
| 223 | string line = NextLineSkipComments(); |
| 224 | if (line == "}") { // No more stack traces in multi-trace syntax |
| 225 | *last_stack_trace = true; |
| 226 | return false; |
| 227 | } |
| 228 | |
| 229 | if (line == "{") { // A multi-trace syntax |
| 230 | line = NextLineSkipComments(); |
| 231 | } else { |
| 232 | *last_stack_trace = true; |
| 233 | } |
| 234 | |
| 235 | while (true) { |
| 236 | if (!ParseStackTraceLine(trace, line)) |
| 237 | return false; |
| 238 | line = NextLineSkipComments(); |
| 239 | if (line == "}") |
| 240 | break; |
| 241 | } |
| 242 | return true; |
| 243 | } |
| 244 | |
| 245 | bool Parser::NextSuppression(Suppression* supp) { |
| 246 | string line; |
| 247 | line = NextLineSkipComments(); |
| 248 | if (line.empty()) |
| 249 | return false; |
| 250 | // Opening { |
| 251 | PARSER_CHECK(line == "{", "expected '{'"); |
| 252 | // Suppression name. |
| 253 | line = NextLineSkipComments(); |
| 254 | PARSER_CHECK(!line.empty(), "expected suppression name"); |
| 255 | supp->name = line; |
| 256 | // tool[,tool]:warning_name. |
| 257 | line = NextLineSkipComments(); |
| 258 | PARSER_CHECK(!line.empty(), "expected tool[, tool]:warning_name line"); |
| 259 | if (!ParseSuppressionToolsLine(supp, line)) |
| 260 | return false; |
| 261 | if (0) { // Not used currently. May still be needed later. |
| 262 | // A possible extra line. |
| 263 | line = NextLineSkipComments(); |
| 264 | if (IsExtraLine(line)) |
| 265 | supp->extra = line; |
| 266 | else |
| 267 | PutBackSkipComments(line); |
| 268 | } |
| 269 | // Everything else. |
| 270 | bool done = false; |
| 271 | while (!done) { |
| 272 | StackTraceTemplate trace; |
| 273 | if (NextStackTraceTemplate(&trace, &done)) |
| 274 | supp->templates.push_back(trace); |
| 275 | if (error_) |
| 276 | return false; |
| 277 | } |
| 278 | // TODO(eugenis): Do we need to check for empty traces? |
| 279 | return true; |
| 280 | } |
| 281 | |
| 282 | struct Suppressions::SuppressionsRep { |
| 283 | vector<Suppression> suppressions; |
| 284 | string error_string_; |
| 285 | int error_line_no_; |
| 286 | }; |
| 287 | |
| 288 | Suppressions::Suppressions() : rep_(new SuppressionsRep) {} |
| 289 | |
| 290 | Suppressions::~Suppressions() { |
| 291 | delete rep_; |
| 292 | } |
| 293 | |
| 294 | int Suppressions::ReadFromString(const string &str) { |
| 295 | int sizeBefore = rep_->suppressions.size(); |
| 296 | Parser parser(str); |
| 297 | Suppression supp; |
| 298 | while (parser.NextSuppression(&supp)) { |
| 299 | rep_->suppressions.push_back(supp); |
| 300 | } |
| 301 | if (parser.GetError()) { |
| 302 | rep_->error_string_ = parser.GetErrorString(); |
| 303 | rep_->error_line_no_ = parser.GetLineNo(); |
| 304 | return -1; |
| 305 | } |
| 306 | return rep_->suppressions.size() - sizeBefore; |
| 307 | } |
| 308 | |
| 309 | string Suppressions::GetErrorString() { |
| 310 | return rep_->error_string_; |
| 311 | } |
| 312 | |
| 313 | int Suppressions::GetErrorLineNo() { |
| 314 | return rep_->error_line_no_; |
| 315 | } |
| 316 | |
| 317 | struct MatcherContext { |
| 318 | MatcherContext( |
| 319 | const vector<string>& function_names_mangled_, |
| 320 | const vector<string>& function_names_demangled_, |
| 321 | const vector<string>& object_names_) : |
| 322 | function_names_mangled(function_names_mangled_), |
| 323 | function_names_demangled(function_names_demangled_), |
| 324 | object_names(object_names_), |
| 325 | tmpl(NULL) |
| 326 | {} |
| 327 | |
| 328 | const vector<string>& function_names_mangled; |
| 329 | const vector<string>& function_names_demangled; |
| 330 | const vector<string>& object_names; |
| 331 | StackTraceTemplate* tmpl; |
| 332 | }; |
| 333 | |
| 334 | static bool MatchStackTraceRecursive(MatcherContext ctx, int trace_index, |
| 335 | int tmpl_index) { |
| 336 | const int trace_size = ctx.function_names_mangled.size(); |
| 337 | const int tmpl_size = ctx.tmpl->locations.size(); |
| 338 | while (trace_index < trace_size && tmpl_index < tmpl_size) { |
| 339 | Location& location = ctx.tmpl->locations[tmpl_index]; |
| 340 | if (location.type == LT_STAR) { |
| 341 | ++tmpl_index; |
| 342 | while (trace_index < trace_size) { |
| 343 | if (MatchStackTraceRecursive(ctx, trace_index++, tmpl_index)) |
| 344 | return true; |
| 345 | } |
| 346 | return false; |
| 347 | } else { |
| 348 | bool match = false; |
| 349 | if (location.type == LT_OBJ) { |
| 350 | match = StringMatch(location.name, ctx.object_names[trace_index]); |
| 351 | } else { |
| 352 | CHECK(location.type == LT_FUN); |
| 353 | match = |
| 354 | StringMatch(location.name, ctx.function_names_mangled[trace_index]) || |
| 355 | StringMatch(location.name, ctx.function_names_demangled[trace_index]); |
| 356 | } |
| 357 | if (match) { |
| 358 | ++trace_index; |
| 359 | ++tmpl_index; |
| 360 | } else { |
| 361 | return false; |
| 362 | } |
| 363 | } |
| 364 | } |
| 365 | return tmpl_index == tmpl_size; |
| 366 | } |
| 367 | |
| 368 | bool Suppressions::StackTraceSuppressed(string tool_name, string warning_name, |
| 369 | const vector<string>& function_names_mangled, |
| 370 | const vector<string>& function_names_demangled, |
| 371 | const vector<string>& object_names, |
| 372 | string *name_of_suppression) { |
| 373 | MatcherContext ctx(function_names_mangled, function_names_demangled, |
| 374 | object_names); |
| 375 | for (vector<Suppression>::iterator it = rep_->suppressions.begin(); |
| 376 | it != rep_->suppressions.end(); ++it) { |
| 377 | if (it->warning_name != warning_name || |
| 378 | it->tools.find(tool_name) == it->tools.end()) |
| 379 | continue; |
| 380 | for (vector<StackTraceTemplate>::iterator it2 = it->templates.begin(); |
| 381 | it2 != it->templates.end(); ++it2) { |
| 382 | ctx.tmpl = &*it2; |
| 383 | bool result = MatchStackTraceRecursive(ctx, 0, 0); |
| 384 | if (result) { |
| 385 | *name_of_suppression = it->name; |
| 386 | return true; |
| 387 | } |
| 388 | } |
| 389 | } |
| 390 | return false; |
| 391 | } |