1 //===-- lib/DebugInfo/Symbolize/MarkupFilter.cpp -------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 ///
9 /// \file
10 /// This file defines the implementation of a filter that replaces symbolizer
11 /// markup with human-readable expressions.
12 ///
13 /// See https://llvm.org/docs/SymbolizerMarkupFormat.html
14 ///
15 //===----------------------------------------------------------------------===//
16 
17 #include "llvm/DebugInfo/Symbolize/MarkupFilter.h"
18 
19 #include "llvm/ADT/None.h"
20 #include "llvm/ADT/STLExtras.h"
21 #include "llvm/ADT/StringExtras.h"
22 #include "llvm/ADT/StringSwitch.h"
23 #include "llvm/DebugInfo/DIContext.h"
24 #include "llvm/DebugInfo/Symbolize/Markup.h"
25 #include "llvm/DebugInfo/Symbolize/Symbolize.h"
26 #include "llvm/Debuginfod/Debuginfod.h"
27 #include "llvm/Demangle/Demangle.h"
28 #include "llvm/Object/ObjectFile.h"
29 #include "llvm/Support/Error.h"
30 #include "llvm/Support/Format.h"
31 #include "llvm/Support/FormatVariadic.h"
32 #include "llvm/Support/WithColor.h"
33 #include "llvm/Support/raw_ostream.h"
34 
35 using namespace llvm;
36 using namespace llvm::symbolize;
37 
38 MarkupFilter::MarkupFilter(raw_ostream &OS, LLVMSymbolizer &Symbolizer,
39                            Optional<bool> ColorsEnabled)
40     : OS(OS), Symbolizer(Symbolizer),
41       ColorsEnabled(
42           ColorsEnabled.value_or(WithColor::defaultAutoDetectFunction()(OS))) {}
43 
44 void MarkupFilter::filter(StringRef Line) {
45   this->Line = Line;
46   resetColor();
47 
48   Parser.parseLine(Line);
49   SmallVector<MarkupNode> DeferredNodes;
50   // See if the line is a contextual (i.e. contains a contextual element).
51   // In this case, anything after the contextual element is elided, or the whole
52   // line may be elided.
53   while (Optional<MarkupNode> Node = Parser.nextNode()) {
54     // If this was a contextual line, then summarily stop processing.
55     if (tryContextualElement(*Node, DeferredNodes))
56       return;
57     // This node may yet be part of an elided contextual line.
58     DeferredNodes.push_back(*Node);
59   }
60 
61   // This was not a contextual line, so nothing in it should be elided.
62   endAnyModuleInfoLine();
63   for (const MarkupNode &Node : DeferredNodes)
64     filterNode(Node);
65 }
66 
67 void MarkupFilter::finish() {
68   Parser.flush();
69   while (Optional<MarkupNode> Node = Parser.nextNode())
70     filterNode(*Node);
71   endAnyModuleInfoLine();
72   resetColor();
73   Modules.clear();
74   MMaps.clear();
75 }
76 
77 // See if the given node is a contextual element and handle it if so. This may
78 // either output or defer the element; in the former case, it will first emit
79 // any DeferredNodes.
80 //
81 // Returns true if the given element was a contextual element. In this case,
82 // DeferredNodes should be considered handled and should not be emitted. The
83 // rest of the containing line must also be ignored in case the element was
84 // deferred to a following line.
85 bool MarkupFilter::tryContextualElement(
86     const MarkupNode &Node, const SmallVector<MarkupNode> &DeferredNodes) {
87   if (tryMMap(Node, DeferredNodes))
88     return true;
89   if (tryReset(Node, DeferredNodes))
90     return true;
91   return tryModule(Node, DeferredNodes);
92 }
93 
94 bool MarkupFilter::tryMMap(const MarkupNode &Node,
95                            const SmallVector<MarkupNode> &DeferredNodes) {
96   if (Node.Tag != "mmap")
97     return false;
98   Optional<MMap> ParsedMMap = parseMMap(Node);
99   if (!ParsedMMap)
100     return true;
101 
102   if (const MMap *M = getOverlappingMMap(*ParsedMMap)) {
103     WithColor::error(errs())
104         << formatv("overlapping mmap: #{0:x} [{1:x}-{2:x}]\n", M->Mod->ID,
105                    M->Addr, M->Addr + M->Size - 1);
106     reportLocation(Node.Fields[0].begin());
107     return true;
108   }
109 
110   auto Res = MMaps.emplace(ParsedMMap->Addr, std::move(*ParsedMMap));
111   assert(Res.second && "Overlap check should ensure emplace succeeds.");
112   MMap &MMap = Res.first->second;
113 
114   if (!MIL || MIL->Mod != MMap.Mod) {
115     endAnyModuleInfoLine();
116     for (const MarkupNode &Node : DeferredNodes)
117       filterNode(Node);
118     beginModuleInfoLine(MMap.Mod);
119     OS << "; adds";
120   }
121   MIL->MMaps.push_back(&MMap);
122   return true;
123 }
124 
125 bool MarkupFilter::tryReset(const MarkupNode &Node,
126                             const SmallVector<MarkupNode> &DeferredNodes) {
127   if (Node.Tag != "reset")
128     return false;
129   if (!checkNumFields(Node, 0))
130     return true;
131 
132   if (!Modules.empty() || !MMaps.empty()) {
133     endAnyModuleInfoLine();
134     for (const MarkupNode &Node : DeferredNodes)
135       filterNode(Node);
136     highlight();
137     OS << "[[[reset]]]" << lineEnding();
138     restoreColor();
139 
140     Modules.clear();
141     MMaps.clear();
142   }
143   return true;
144 }
145 
146 bool MarkupFilter::tryModule(const MarkupNode &Node,
147                              const SmallVector<MarkupNode> &DeferredNodes) {
148   if (Node.Tag != "module")
149     return false;
150   Optional<Module> ParsedModule = parseModule(Node);
151   if (!ParsedModule)
152     return true;
153 
154   auto Res = Modules.try_emplace(
155       ParsedModule->ID, std::make_unique<Module>(std::move(*ParsedModule)));
156   if (!Res.second) {
157     WithColor::error(errs()) << "duplicate module ID\n";
158     reportLocation(Node.Fields[0].begin());
159     return true;
160   }
161   Module &Module = *Res.first->second;
162 
163   endAnyModuleInfoLine();
164   for (const MarkupNode &Node : DeferredNodes)
165     filterNode(Node);
166   beginModuleInfoLine(&Module);
167   OS << "; BuildID=";
168   printValue(toHex(Module.BuildID, /*LowerCase=*/true));
169   return true;
170 }
171 
172 void MarkupFilter::beginModuleInfoLine(const Module *M) {
173   highlight();
174   OS << "[[[ELF module";
175   printValue(formatv(" #{0:x} ", M->ID));
176   OS << '"';
177   printValue(M->Name);
178   OS << '"';
179   MIL = ModuleInfoLine{M};
180 }
181 
182 void MarkupFilter::endAnyModuleInfoLine() {
183   if (!MIL)
184     return;
185   llvm::stable_sort(MIL->MMaps, [](const MMap *A, const MMap *B) {
186     return A->Addr < B->Addr;
187   });
188   for (const MMap *M : MIL->MMaps) {
189     OS << (M == MIL->MMaps.front() ? ' ' : ',');
190     OS << '[';
191     printValue(formatv("{0:x}", M->Addr));
192     OS << '-';
193     printValue(formatv("{0:x}", M->Addr + M->Size - 1));
194     OS << "](";
195     printValue(M->Mode);
196     OS << ')';
197   }
198   OS << "]]]" << lineEnding();
199   restoreColor();
200   MIL.reset();
201 }
202 
203 // Handle a node that is known not to be a contextual element.
204 void MarkupFilter::filterNode(const MarkupNode &Node) {
205   if (!checkTag(Node))
206     return;
207   if (tryPresentation(Node))
208     return;
209   if (trySGR(Node))
210     return;
211 
212   OS << Node.Text;
213 }
214 
215 bool MarkupFilter::tryPresentation(const MarkupNode &Node) {
216   if (trySymbol(Node))
217     return true;
218   if (tryPC(Node))
219     return true;
220   if (tryBackTrace(Node))
221     return true;
222   return tryData(Node);
223 }
224 
225 bool MarkupFilter::trySymbol(const MarkupNode &Node) {
226   if (Node.Tag != "symbol")
227     return false;
228   if (!checkNumFields(Node, 1))
229     return true;
230 
231   highlight();
232   OS << llvm::demangle(Node.Fields.front().str());
233   restoreColor();
234   return true;
235 }
236 
237 bool MarkupFilter::tryPC(const MarkupNode &Node) {
238   if (Node.Tag != "pc")
239     return false;
240   if (!checkNumFieldsAtLeast(Node, 1))
241     return true;
242   if (!checkNumFieldsAtMost(Node, 2))
243     return true;
244 
245   Optional<uint64_t> Addr = parseAddr(Node.Fields[0]);
246   if (!Addr)
247     return true;
248 
249   // PC addresses that aren't part of a backtrace are assumed to be precise code
250   // locations.
251   PCType Type = PCType::PreciseCode;
252   if (Node.Fields.size() == 2) {
253     Optional<PCType> ParsedType = parsePCType(Node.Fields[1]);
254     if (!ParsedType)
255       return true;
256     Type = *ParsedType;
257   }
258   *Addr = adjustAddr(*Addr, Type);
259 
260   const MMap *MMap = getContainingMMap(*Addr);
261   if (!MMap) {
262     WithColor::error() << "no mmap covers address\n";
263     reportLocation(Node.Fields[0].begin());
264     printRawElement(Node);
265     return true;
266   }
267 
268   Expected<DILineInfo> LI = Symbolizer.symbolizeCode(
269       MMap->Mod->BuildID, {MMap->getModuleRelativeAddr(*Addr)});
270   if (!LI) {
271     WithColor::defaultErrorHandler(LI.takeError());
272     printRawElement(Node);
273     return true;
274   }
275   if (!*LI) {
276     printRawElement(Node);
277     return true;
278   }
279 
280   highlight();
281   printValue(LI->FunctionName);
282   OS << '[';
283   printValue(LI->FileName);
284   OS << ':';
285   printValue(Twine(LI->Line));
286   OS << ']';
287   restoreColor();
288   return true;
289 }
290 
291 bool MarkupFilter::tryBackTrace(const MarkupNode &Node) {
292   if (Node.Tag != "bt")
293     return false;
294   if (!checkNumFieldsAtLeast(Node, 2))
295     return true;
296   if (!checkNumFieldsAtMost(Node, 3))
297     return true;
298 
299   Optional<uint64_t> FrameNumber = parseFrameNumber(Node.Fields[0]);
300   if (!FrameNumber)
301     return true;
302 
303   Optional<uint64_t> Addr = parseAddr(Node.Fields[1]);
304   if (!Addr)
305     return true;
306 
307   // Backtrace addresses are assumed to be return addresses by default.
308   PCType Type = PCType::ReturnAddress;
309   if (Node.Fields.size() == 3) {
310     Optional<PCType> ParsedType = parsePCType(Node.Fields[2]);
311     if (!ParsedType)
312       return true;
313     Type = *ParsedType;
314   }
315   *Addr = adjustAddr(*Addr, Type);
316 
317   const MMap *MMap = getContainingMMap(*Addr);
318   if (!MMap) {
319     WithColor::error() << "no mmap covers address\n";
320     reportLocation(Node.Fields[0].begin());
321     printRawElement(Node);
322     return true;
323   }
324   uint64_t MRA = MMap->getModuleRelativeAddr(*Addr);
325 
326   Expected<DIInliningInfo> II =
327       Symbolizer.symbolizeInlinedCode(MMap->Mod->BuildID, {MRA});
328   if (!II) {
329     WithColor::defaultErrorHandler(II.takeError());
330     printRawElement(Node);
331     return true;
332   }
333 
334   highlight();
335   for (unsigned I = 0, E = II->getNumberOfFrames(); I != E; ++I) {
336     auto Header = formatv("{0, +6}", formatv("#{0}", FrameNumber)).sstr<16>();
337     // Don't highlight the # sign as a value.
338     size_t NumberIdx = Header.find("#") + 1;
339     OS << Header.substr(0, NumberIdx);
340     printValue(Header.substr(NumberIdx));
341     if (I == E - 1) {
342       OS << "   ";
343     } else {
344       OS << '.';
345       printValue(formatv("{0, -2}", I + 1));
346     }
347     printValue(formatv(" {0:x16} ", *Addr));
348 
349     DILineInfo LI = II->getFrame(I);
350     if (LI) {
351       printValue(LI.FunctionName);
352       OS << ' ';
353       printValue(LI.FileName);
354       OS << ':';
355       printValue(Twine(LI.Line));
356       OS << ':';
357       printValue(Twine(LI.Column));
358       OS << ' ';
359     }
360     OS << '(';
361     printValue(MMap->Mod->Name);
362     OS << "+";
363     printValue(formatv("{0:x}", MRA));
364     OS << ')';
365     if (I != E - 1)
366       OS << lineEnding();
367   }
368   restoreColor();
369   return true;
370 }
371 
372 bool MarkupFilter::tryData(const MarkupNode &Node) {
373   if (Node.Tag != "data")
374     return false;
375   if (!checkNumFields(Node, 1))
376     return true;
377   Optional<uint64_t> Addr = parseAddr(Node.Fields[0]);
378   if (!Addr)
379     return true;
380 
381   const MMap *MMap = getContainingMMap(*Addr);
382   if (!MMap) {
383     WithColor::error() << "no mmap covers address\n";
384     reportLocation(Node.Fields[0].begin());
385     printRawElement(Node);
386     return true;
387   }
388 
389   Expected<DIGlobal> Symbol = Symbolizer.symbolizeData(
390       MMap->Mod->BuildID, {MMap->getModuleRelativeAddr(*Addr)});
391   if (!Symbol) {
392     WithColor::defaultErrorHandler(Symbol.takeError());
393     printRawElement(Node);
394     return true;
395   }
396 
397   highlight();
398   OS << Symbol->Name;
399   restoreColor();
400   return true;
401 }
402 
403 bool MarkupFilter::trySGR(const MarkupNode &Node) {
404   if (Node.Text == "\033[0m") {
405     resetColor();
406     return true;
407   }
408   if (Node.Text == "\033[1m") {
409     Bold = true;
410     if (ColorsEnabled)
411       OS.changeColor(raw_ostream::Colors::SAVEDCOLOR, Bold);
412     return true;
413   }
414   auto SGRColor = StringSwitch<Optional<raw_ostream::Colors>>(Node.Text)
415                       .Case("\033[30m", raw_ostream::Colors::BLACK)
416                       .Case("\033[31m", raw_ostream::Colors::RED)
417                       .Case("\033[32m", raw_ostream::Colors::GREEN)
418                       .Case("\033[33m", raw_ostream::Colors::YELLOW)
419                       .Case("\033[34m", raw_ostream::Colors::BLUE)
420                       .Case("\033[35m", raw_ostream::Colors::MAGENTA)
421                       .Case("\033[36m", raw_ostream::Colors::CYAN)
422                       .Case("\033[37m", raw_ostream::Colors::WHITE)
423                       .Default(llvm::None);
424   if (SGRColor) {
425     Color = *SGRColor;
426     if (ColorsEnabled)
427       OS.changeColor(*Color);
428     return true;
429   }
430 
431   return false;
432 }
433 
434 // Begin highlighting text by picking a different color than the current color
435 // state.
436 void MarkupFilter::highlight() {
437   if (!ColorsEnabled)
438     return;
439   OS.changeColor(Color == raw_ostream::Colors::BLUE ? raw_ostream::Colors::CYAN
440                                                     : raw_ostream::Colors::BLUE,
441                  Bold);
442 }
443 
444 // Begin highlighting a field within a highlighted markup string.
445 void MarkupFilter::highlightValue() {
446   if (!ColorsEnabled)
447     return;
448   OS.changeColor(raw_ostream::Colors::GREEN, Bold);
449 }
450 
451 // Set the output stream's color to the current color and bold state of the SGR
452 // abstract machine.
453 void MarkupFilter::restoreColor() {
454   if (!ColorsEnabled)
455     return;
456   if (Color) {
457     OS.changeColor(*Color, Bold);
458   } else {
459     OS.resetColor();
460     if (Bold)
461       OS.changeColor(raw_ostream::Colors::SAVEDCOLOR, Bold);
462   }
463 }
464 
465 // Set the SGR and output stream's color and bold states back to the default.
466 void MarkupFilter::resetColor() {
467   if (!Color && !Bold)
468     return;
469   Color.reset();
470   Bold = false;
471   if (ColorsEnabled)
472     OS.resetColor();
473 }
474 
475 void MarkupFilter::printRawElement(const MarkupNode &Element) {
476   highlight();
477   OS << "[[[";
478   printValue(Element.Tag);
479   for (StringRef Field : Element.Fields) {
480     OS << ':';
481     printValue(Field);
482   }
483   OS << "]]]";
484   restoreColor();
485 }
486 
487 void MarkupFilter::printValue(Twine Value) {
488   highlightValue();
489   OS << Value;
490   highlight();
491 }
492 
493 // This macro helps reduce the amount of indirection done through Optional
494 // below, since the usual case upon returning a None Optional is to return None.
495 #define ASSIGN_OR_RETURN_NONE(TYPE, NAME, EXPR)                                \
496   auto NAME##Opt = (EXPR);                                                     \
497   if (!NAME##Opt)                                                              \
498     return None;                                                               \
499   TYPE NAME = std::move(*NAME##Opt)
500 
501 Optional<MarkupFilter::Module>
502 MarkupFilter::parseModule(const MarkupNode &Element) const {
503   if (!checkNumFieldsAtLeast(Element, 3))
504     return None;
505   ASSIGN_OR_RETURN_NONE(uint64_t, ID, parseModuleID(Element.Fields[0]));
506   StringRef Name = Element.Fields[1];
507   StringRef Type = Element.Fields[2];
508   if (Type != "elf") {
509     WithColor::error() << "unknown module type\n";
510     reportLocation(Type.begin());
511     return None;
512   }
513   if (!checkNumFields(Element, 4))
514     return None;
515   ASSIGN_OR_RETURN_NONE(SmallVector<uint8_t>, BuildID,
516                         parseBuildID(Element.Fields[3]));
517   return Module{ID, Name.str(), std::move(BuildID)};
518 }
519 
520 Optional<MarkupFilter::MMap>
521 MarkupFilter::parseMMap(const MarkupNode &Element) const {
522   if (!checkNumFieldsAtLeast(Element, 3))
523     return None;
524   ASSIGN_OR_RETURN_NONE(uint64_t, Addr, parseAddr(Element.Fields[0]));
525   ASSIGN_OR_RETURN_NONE(uint64_t, Size, parseSize(Element.Fields[1]));
526   StringRef Type = Element.Fields[2];
527   if (Type != "load") {
528     WithColor::error() << "unknown mmap type\n";
529     reportLocation(Type.begin());
530     return None;
531   }
532   if (!checkNumFields(Element, 6))
533     return None;
534   ASSIGN_OR_RETURN_NONE(uint64_t, ID, parseModuleID(Element.Fields[3]));
535   ASSIGN_OR_RETURN_NONE(std::string, Mode, parseMode(Element.Fields[4]));
536   auto It = Modules.find(ID);
537   if (It == Modules.end()) {
538     WithColor::error() << "unknown module ID\n";
539     reportLocation(Element.Fields[3].begin());
540     return None;
541   }
542   ASSIGN_OR_RETURN_NONE(uint64_t, ModuleRelativeAddr,
543                         parseAddr(Element.Fields[5]));
544   return MMap{Addr, Size, It->second.get(), std::move(Mode),
545               ModuleRelativeAddr};
546 }
547 
548 // Parse an address (%p in the spec).
549 Optional<uint64_t> MarkupFilter::parseAddr(StringRef Str) const {
550   if (Str.empty()) {
551     reportTypeError(Str, "address");
552     return None;
553   }
554   if (all_of(Str, [](char C) { return C == '0'; }))
555     return 0;
556   if (!Str.startswith("0x")) {
557     reportTypeError(Str, "address");
558     return None;
559   }
560   uint64_t Addr;
561   if (Str.drop_front(2).getAsInteger(16, Addr)) {
562     reportTypeError(Str, "address");
563     return None;
564   }
565   return Addr;
566 }
567 
568 // Parse a module ID (%i in the spec).
569 Optional<uint64_t> MarkupFilter::parseModuleID(StringRef Str) const {
570   uint64_t ID;
571   if (Str.getAsInteger(0, ID)) {
572     reportTypeError(Str, "module ID");
573     return None;
574   }
575   return ID;
576 }
577 
578 // Parse a size (%i in the spec).
579 Optional<uint64_t> MarkupFilter::parseSize(StringRef Str) const {
580   uint64_t ID;
581   if (Str.getAsInteger(0, ID)) {
582     reportTypeError(Str, "size");
583     return None;
584   }
585   return ID;
586 }
587 
588 // Parse a frame number (%i in the spec).
589 Optional<uint64_t> MarkupFilter::parseFrameNumber(StringRef Str) const {
590   uint64_t ID;
591   if (Str.getAsInteger(10, ID)) {
592     reportTypeError(Str, "frame number");
593     return None;
594   }
595   return ID;
596 }
597 
598 // Parse a build ID (%x in the spec).
599 Optional<SmallVector<uint8_t>> MarkupFilter::parseBuildID(StringRef Str) const {
600   std::string Bytes;
601   if (Str.empty() || Str.size() % 2 || !tryGetFromHex(Str, Bytes)) {
602     reportTypeError(Str, "build ID");
603     return None;
604   }
605   ArrayRef<uint8_t> BuildID(reinterpret_cast<const uint8_t *>(Bytes.data()),
606                             Bytes.size());
607   return SmallVector<uint8_t>(BuildID.begin(), BuildID.end());
608 }
609 
610 // Parses the mode string for an mmap element.
611 Optional<std::string> MarkupFilter::parseMode(StringRef Str) const {
612   if (Str.empty()) {
613     reportTypeError(Str, "mode");
614     return None;
615   }
616 
617   // Pop off each of r/R, w/W, and x/X from the front, in that order.
618   StringRef Remainder = Str;
619   if (!Remainder.empty() && tolower(Remainder.front()) == 'r')
620     Remainder = Remainder.drop_front();
621   if (!Remainder.empty() && tolower(Remainder.front()) == 'w')
622     Remainder = Remainder.drop_front();
623   if (!Remainder.empty() && tolower(Remainder.front()) == 'x')
624     Remainder = Remainder.drop_front();
625 
626   // If anything remains, then the string wasn't a mode.
627   if (!Remainder.empty()) {
628     reportTypeError(Str, "mode");
629     return None;
630   }
631 
632   // Normalize the mode.
633   return Str.lower();
634 }
635 
636 Optional<MarkupFilter::PCType> MarkupFilter::parsePCType(StringRef Str) const {
637   Optional<MarkupFilter::PCType> Type =
638       StringSwitch<Optional<MarkupFilter::PCType>>(Str)
639           .Case("ra", MarkupFilter::PCType::ReturnAddress)
640           .Case("pc", MarkupFilter::PCType::PreciseCode)
641           .Default(None);
642   if (!Type)
643     reportTypeError(Str, "PC type");
644   return Type;
645 }
646 
647 bool MarkupFilter::checkTag(const MarkupNode &Node) const {
648   if (any_of(Node.Tag, [](char C) { return C < 'a' || C > 'z'; })) {
649     WithColor::error(errs()) << "tags must be all lowercase characters\n";
650     reportLocation(Node.Tag.begin());
651     return false;
652   }
653   return true;
654 }
655 
656 bool MarkupFilter::checkNumFields(const MarkupNode &Element,
657                                   size_t Size) const {
658   if (Element.Fields.size() != Size) {
659     WithColor::error(errs()) << "expected " << Size << " field(s); found "
660                              << Element.Fields.size() << "\n";
661     reportLocation(Element.Tag.end());
662     return false;
663   }
664   return true;
665 }
666 
667 bool MarkupFilter::checkNumFieldsAtLeast(const MarkupNode &Element,
668                                          size_t Size) const {
669   if (Element.Fields.size() < Size) {
670     WithColor::error(errs())
671         << "expected at least " << Size << " field(s); found "
672         << Element.Fields.size() << "\n";
673     reportLocation(Element.Tag.end());
674     return false;
675   }
676   return true;
677 }
678 
679 bool MarkupFilter::checkNumFieldsAtMost(const MarkupNode &Element,
680                                         size_t Size) const {
681   if (Element.Fields.size() > Size) {
682     WithColor::error(errs())
683         << "expected at most " << Size << " field(s); found "
684         << Element.Fields.size() << "\n";
685     reportLocation(Element.Tag.end());
686     return false;
687   }
688   return true;
689 }
690 
691 void MarkupFilter::reportTypeError(StringRef Str, StringRef TypeName) const {
692   WithColor::error(errs()) << "expected " << TypeName << "; found '" << Str
693                            << "'\n";
694   reportLocation(Str.begin());
695 }
696 
697 // Prints two lines that point out the given location in the current Line using
698 // a caret. The iterator must be within the bounds of the most recent line
699 // passed to beginLine().
700 void MarkupFilter::reportLocation(StringRef::iterator Loc) const {
701   errs() << Line;
702   WithColor(errs().indent(Loc - Line.begin()), HighlightColor::String) << '^';
703   errs() << '\n';
704 }
705 
706 // Checks for an existing mmap that overlaps the given one and returns a
707 // pointer to one of them.
708 const MarkupFilter::MMap *
709 MarkupFilter::getOverlappingMMap(const MMap &Map) const {
710   // If the given map contains the start of another mmap, they overlap.
711   auto I = MMaps.upper_bound(Map.Addr);
712   if (I != MMaps.end() && Map.contains(I->second.Addr))
713     return &I->second;
714 
715   // If no element starts inside the given mmap, the only possible overlap would
716   // be if the preceding mmap contains the start point of the given mmap.
717   if (I != MMaps.begin()) {
718     --I;
719     if (I->second.contains(Map.Addr))
720       return &I->second;
721   }
722   return nullptr;
723 }
724 
725 // Returns the MMap that contains the given address or nullptr if none.
726 const MarkupFilter::MMap *MarkupFilter::getContainingMMap(uint64_t Addr) const {
727   // Find the first mmap starting >= Addr.
728   auto I = MMaps.lower_bound(Addr);
729   if (I != MMaps.end() && I->second.contains(Addr))
730     return &I->second;
731 
732   // The previous mmap is the last one starting < Addr.
733   if (I == MMaps.begin())
734     return nullptr;
735   --I;
736   return I->second.contains(Addr) ? &I->second : nullptr;
737 }
738 
739 uint64_t MarkupFilter::adjustAddr(uint64_t Addr, PCType Type) const {
740   // Decrementing return addresses by one moves them into the call instruction.
741   // The address doesn't have to be the start of the call instruction, just some
742   // byte on the inside. Subtracting one avoids needing detailed instruction
743   // length information here.
744   return Type == MarkupFilter::PCType::ReturnAddress ? Addr - 1 : Addr;
745 }
746 
747 StringRef MarkupFilter::lineEnding() const {
748   return Line.endswith("\r\n") ? "\r\n" : "\n";
749 }
750 
751 bool MarkupFilter::MMap::contains(uint64_t Addr) const {
752   return this->Addr <= Addr && Addr < this->Addr + Size;
753 }
754 
755 // Returns the module-relative address for a given virtual address.
756 uint64_t MarkupFilter::MMap::getModuleRelativeAddr(uint64_t Addr) const {
757   return Addr - this->Addr + ModuleRelativeAddr;
758 }
759