Adding support for overlapping ranges to RangeMap.

src/processor/basic_source_line_resolver.cc

 // Copyright (c) 2010 Google Inc.
 // All rights reserved.
 //
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 // notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
@@ skipping 128 matching lines @@
         LogParseError("ParseStackInfo failed", line_number, &num_errors);
       }
     } else if (strncmp(buffer, "FUNC ", 5) == 0) {
       cur_func.reset(ParseFunction(buffer));
       if (!cur_func.get()) {
         LogParseError("ParseFunction failed", line_number, &num_errors);
       } else {
         // StoreRange will fail if the function has an invalid address or size.
         // We'll silently ignore this, the function and any corresponding lines
         // will be destroyed when cur_func is released.
-        functions_.StoreRange(cur_func->address, cur_func->size, cur_func);
+        functions_.StoreRange(cur_func->address, 0 /* delta */, cur_func->size,
+                              cur_func);
       }
     } else if (strncmp(buffer, "PUBLIC ", 7) == 0) {
       // Clear cur_func: public symbols don't contain line number information.
       cur_func.reset();
 
       if (!ParsePublicSymbol(buffer)) {
         LogParseError("ParsePublicSymbol failed", line_number, &num_errors);
       }
     } else if (strncmp(buffer, "MODULE ", 7) == 0) {
       // Ignore these.  They're not of any use to BasicSourceLineResolver,
       // which is fed modules by a SymbolSupplier.  These lines are present to
       // aid other tools in properly placing symbol files so that they can
       // be accessed by a SymbolSupplier.
       //
       // MODULE <guid> <age> <filename>
     } else if (strncmp(buffer, "INFO ", 5) == 0) {
       // Ignore these as well, they're similarly just for housekeeping.
       //
       // INFO CODE_ID <code id> <filename>
     } else {
       if (!cur_func.get()) {
         LogParseError("Found source line data without a function",
                        line_number, &num_errors);
       } else {
         Line *line = ParseLine(buffer);
         if (!line) {
           LogParseError("ParseLine failed", line_number, &num_errors);
         } else {
-          cur_func->lines.StoreRange(line->address, line->size,
+          cur_func->lines.StoreRange(line->address, 0 /* delta */, line->size,
                                      linked_ptr<Line>(line));
         }
       }
     }
     if (num_errors > kMaxErrorsBeforeBailing) {
       break;
     }
     buffer = strtok_r(NULL, "\r\n", &save_ptr);
   }
   is_corrupt_ = num_errors > 0;
   return true;
 }
 
 void BasicSourceLineResolver::Module::LookupAddress(StackFrame *frame) const {
   MemAddr address = frame->instruction - frame->module->base_address();
 
   // First, look for a FUNC record that covers address. Use
   // RetrieveNearestRange instead of RetrieveRange so that, if there
   // is no such function, we can use the next function to bound the
   // extent of the PUBLIC symbol we find, below. This does mean we
   // need to check that address indeed falls within the function we
   // find; do the range comparison in an overflow-friendly way.
   linked_ptr<Function> func;
   linked_ptr<PublicSymbol> public_symbol;
   MemAddr function_base;
   MemAddr function_size;
   MemAddr public_address;
-  if (functions_.RetrieveNearestRange(address, &func,
-                                      &function_base, &function_size) &&
+  if (functions_.RetrieveNearestRange(address, &func, &function_base,
+                                      NULL /* delta */, &function_size) &&
       address >= function_base && address - function_base < function_size) {
     frame->function_name = func->name;
     frame->function_base = frame->module->base_address() + function_base;
 
     linked_ptr<Line> line;
     MemAddr line_base;
-    if (func->lines.RetrieveRange(address, &line, &line_base, NULL)) {
+    if (func->lines.RetrieveRange(address, &line, &line_base, NULL, NULL)) {
       FileMap::const_iterator it = files_.find(line->source_file_id);
       if (it != files_.end()) {
         frame->source_file_name = files_.find(line->source_file_id)->second;
       }
       frame->source_line = line->line;
       frame->source_line_base = frame->module->base_address() + line_base;
     }
   } else if (public_symbols_.Retrieve(address,
                                       &public_symbol, &public_address) &&
              (!func.get() || public_address > function_base)) {
@@ skipping 24 matching lines @@
 
   // Even without a relevant STACK line, many functions contain
   // information about how much space their parameters consume on the
   // stack. Use RetrieveNearestRange instead of RetrieveRange, so that
   // we can use the function to bound the extent of the PUBLIC symbol,
   // below. However, this does mean we need to check that ADDRESS
   // falls within the retrieved function's range; do the range
   // comparison in an overflow-friendly way.
   linked_ptr<Function> function;
   MemAddr function_base, function_size;
-  if (functions_.RetrieveNearestRange(address, &function,
-                                      &function_base, &function_size) &&
+  if (functions_.RetrieveNearestRange(address, &function, &function_base,
+                                      NULL /* delta */, &function_size) &&
       address >= function_base && address - function_base < function_size) {
     result->parameter_size = function->parameter_size;
     result->valid |= WindowsFrameInfo::VALID_PARAMETER_SIZE;
     return result.release();
   }
 
   // PUBLIC symbols might have a parameter size. Use the function we
   // found above to limit the range the public symbol covers.
   linked_ptr<PublicSymbol> public_symbol;
   MemAddr public_address;
   if (public_symbols_.Retrieve(address, &public_symbol, &public_address) &&
       (!function.get() || public_address > function_base)) {
     result->parameter_size = public_symbol->parameter_size;
   }
 
   return NULL;
 }
 
 CFIFrameInfo *BasicSourceLineResolver::Module::FindCFIFrameInfo(
     const StackFrame *frame) const {
   MemAddr address = frame->instruction - frame->module->base_address();
   MemAddr initial_base, initial_size;
   string initial_rules;
 
   // Find the initial rule whose range covers this address. That
   // provides an initial set of register recovery rules. Then, walk
   // forward from the initial rule's starting address to frame's
   // instruction address, applying delta rules.
-  if (!cfi_initial_rules_.RetrieveRange(address, &initial_rules,
-                                        &initial_base, &initial_size)) {
+  if (!cfi_initial_rules_.RetrieveRange(address, &initial_rules, &initial_base,
+                                        NULL /* delta */, &initial_size)) {
     return NULL;
   }
 
   // Create a frame info structure, and populate it with the rules from
   // the STACK CFI INIT record.
   scoped_ptr<CFIFrameInfo> rules(new CFIFrameInfo());
   if (!ParseCFIRuleSet(initial_rules, rules.get()))
     return NULL;
 
   // Find the first delta rule that falls within the initial rule's range.
@@ skipping 141 matching lines @@
     if (!address_field) return false;
 
     char *size_field = strtok_r(NULL, " \r\n", &cursor);
     if (!size_field) return false;
 
     char *initial_rules = strtok_r(NULL, "\r\n", &cursor);
     if (!initial_rules) return false;
 
     MemAddr address = strtoul(address_field, NULL, 16);
     MemAddr size    = strtoul(size_field,    NULL, 16);
-    cfi_initial_rules_.StoreRange(address, size, initial_rules);
+    cfi_initial_rules_.StoreRange(address, 0 /* delta */, size, initial_rules);
     return true;
   }
 
   // This record has the form "STACK <address> <rules...>".
   char *address_field = init_or_address;
   char *delta_rules = strtok_r(NULL, "\r\n", &cursor);
   if (!delta_rules) return false;
   MemAddr address = strtoul(address_field, NULL, 16);
   cfi_delta_rules_[address] = delta_rules;
   return true;
@@ skipping 125 matching lines @@
   if (!IsValidAfterNumber(after_number) ||
       *address == std::numeric_limits<unsigned long long>::max()) {
     return false;
   }
   *stack_param_size = strtol(tokens[1], &after_number, 16);
   if (!IsValidAfterNumber(after_number) ||
       *stack_param_size == std::numeric_limits<long>::max() ||
       *stack_param_size < 0) {
     return false;
   }
-  *name = tokens[2]; 
+  *name = tokens[2];
 
   return true;
 }
 
 // static
 bool SymbolParseHelper::IsValidAfterNumber(char *after_number) {
   if (after_number != NULL && strchr(kWhitespace, *after_number) != NULL) {
     return true;
   }
   return false;
 }
 
 }  // namespace google_breakpad