1 //===--- Forest.cpp - Parse forest ------------------------------*- C++-*-===// 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 #include "clang-pseudo/Forest.h" 10 #include "clang-pseudo/Token.h" 11 #include "llvm/ADT/ArrayRef.h" 12 #include "llvm/ADT/None.h" 13 #include "llvm/ADT/STLExtras.h" 14 #include "llvm/Support/FormatVariadic.h" 15 16 namespace clang { 17 namespace pseudo { 18 19 std::string ForestNode::dump(const Grammar &G) const { 20 switch (kind()) { 21 case Ambiguous: 22 return llvm::formatv("{0} := <ambiguous>", G.symbolName(symbol())); 23 case Terminal: 24 return llvm::formatv("{0} := tok[{1}]", G.symbolName(symbol()), 25 startTokenIndex()); 26 case Sequence: 27 return G.dumpRule(rule()); 28 case Opaque: 29 return llvm::formatv("{0} := <opaque>", G.symbolName(symbol())); 30 } 31 llvm_unreachable("Unhandled node kind!"); 32 } 33 34 std::string ForestNode::dumpRecursive(const Grammar &G, 35 bool Abbreviated) const { 36 using llvm::formatv; 37 Token::Index MaxToken = 0; 38 // Count visits of nodes so we can mark those seen multiple times. 39 llvm::DenseMap<const ForestNode *, /*VisitCount*/ unsigned> VisitCounts; 40 std::function<void(const ForestNode *)> CountVisits = 41 [&](const ForestNode *P) { 42 MaxToken = std::max(MaxToken, P->startTokenIndex()); 43 if (VisitCounts[P]++ > 0) 44 return; // Don't count children as multiply visited. 45 if (P->kind() == Ambiguous) 46 llvm::for_each(P->alternatives(), CountVisits); 47 else if (P->kind() == Sequence) 48 llvm::for_each(P->elements(), CountVisits); 49 }; 50 CountVisits(this); 51 52 unsigned IndexWidth = std::max(3, (int)std::to_string(MaxToken).size()); 53 // e.g. "[{0,4}, {1,4})" if MaxToken is 5742. 54 std::string RangeFormat = formatv("[{{0,{0}}, {{1,{0}}) ", IndexWidth); 55 56 // The box-drawing characters that should be added as a child is rendered. 57 struct LineDecoration { 58 std::string Prefix; // Prepended to every line. 59 llvm::StringRef First; // added to the child's line. 60 llvm::StringRef Subsequent; // added to descendants' lines. 61 }; 62 63 // We print a "#<id>" for nonterminal forest nodes that are being dumped 64 // multiple times. 65 llvm::DenseMap<const ForestNode *, size_t> ReferenceIds; 66 std::string Result; 67 constexpr Token::Index KEnd = std::numeric_limits<Token::Index>::max(); 68 std::function<void(const ForestNode *, Token::Index, llvm::Optional<SymbolID>, 69 LineDecoration &LineDec)> 70 Dump = [&](const ForestNode *P, Token::Index End, 71 llvm::Optional<SymbolID> ElidedParent, 72 LineDecoration LineDec) { 73 bool SharedNode = VisitCounts.find(P)->getSecond() > 1; 74 llvm::ArrayRef<const ForestNode *> Children; 75 auto EndOfElement = [&](size_t ChildIndex) { 76 return ChildIndex + 1 == Children.size() 77 ? End 78 : Children[ChildIndex + 1]->startTokenIndex(); 79 }; 80 if (P->kind() == Ambiguous) { 81 Children = P->alternatives(); 82 } else if (P->kind() == Sequence) { 83 Children = P->elements(); 84 if (Abbreviated) { 85 // Abbreviate chains of trivial sequence nodes. 86 // A := B, B := C, C := D, D := X Y Z 87 // becomes 88 // A~D := X Y Z 89 // 90 // We can't hide nodes that appear multiple times in the tree, 91 // because we need to call out their identity with IDs. 92 if (Children.size() == 1 && !SharedNode) { 93 assert(Children[0]->startTokenIndex() == P->startTokenIndex() && 94 EndOfElement(0) == End); 95 return Dump(Children[0], End, 96 /*ElidedParent=*/ElidedParent.value_or(P->symbol()), 97 LineDec); 98 } 99 } 100 } 101 102 if (End == KEnd) 103 Result += formatv(RangeFormat.c_str(), P->startTokenIndex(), "end"); 104 else 105 Result += formatv(RangeFormat.c_str(), P->startTokenIndex(), End); 106 Result += LineDec.Prefix; 107 Result += LineDec.First; 108 if (ElidedParent) { 109 Result += G.symbolName(*ElidedParent); 110 Result += "~"; 111 } 112 113 if (SharedNode && P->kind() != ForestNode::Terminal) { 114 auto It = ReferenceIds.try_emplace(P, ReferenceIds.size() + 1); 115 bool First = It.second; 116 unsigned ID = It.first->second; 117 118 // The first time, print as #1. Later, =#1. 119 if (First) { 120 Result += formatv("{0} #{1}", P->dump(G), ID); 121 } else { 122 Result += formatv("{0} =#{1}", G.symbolName(P->symbol()), ID); 123 Children = {}; // Don't walk the children again. 124 } 125 } else { 126 Result.append(P->dump(G)); 127 } 128 Result.push_back('\n'); 129 130 auto OldPrefixSize = LineDec.Prefix.size(); 131 LineDec.Prefix += LineDec.Subsequent; 132 for (size_t I = 0; I < Children.size(); ++I) { 133 if (I == Children.size() - 1) { 134 LineDec.First = "└─"; 135 LineDec.Subsequent = " "; 136 } else { 137 LineDec.First = "├─"; 138 LineDec.Subsequent = "│ "; 139 } 140 Dump(Children[I], P->kind() == Sequence ? EndOfElement(I) : End, 141 llvm::None, LineDec); 142 } 143 LineDec.Prefix.resize(OldPrefixSize); 144 }; 145 LineDecoration LineDec; 146 Dump(this, KEnd, llvm::None, LineDec); 147 return Result; 148 } 149 150 llvm::ArrayRef<ForestNode> 151 ForestArena::createTerminals(const TokenStream &Code) { 152 ForestNode *Terminals = Arena.Allocate<ForestNode>(Code.tokens().size()); 153 size_t Index = 0; 154 for (const auto &T : Code.tokens()) { 155 new (&Terminals[Index]) 156 ForestNode(ForestNode::Terminal, tokenSymbol(T.Kind), 157 /*Start=*/Index, /*TerminalData*/ 0); 158 ++Index; 159 } 160 NodeCount = Index; 161 return llvm::makeArrayRef(Terminals, Index); 162 } 163 164 } // namespace pseudo 165 } // namespace clang 166