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   // Count visits of nodes so we can mark those seen multiple times.
37   llvm::DenseMap<const ForestNode *, /*VisitCount*/ unsigned> VisitCounts;
38   std::function<void(const ForestNode *)> CountVisits =
39       [&](const ForestNode *P) {
40         if (VisitCounts[P]++ > 0)
41           return; // Don't count children as multiply visited.
42         if (P->kind() == Ambiguous)
43           llvm::for_each(P->alternatives(), CountVisits);
44         else if (P->kind() == Sequence)
45           llvm::for_each(P->elements(), CountVisits);
46       };
47   CountVisits(this);
48 
49   // The box-drawing characters that should be added as a child is rendered.
50   struct LineDecoration {
51     std::string Prefix;         // Prepended to every line.
52     llvm::StringRef First;      // added to the child's line.
53     llvm::StringRef Subsequent; // added to descendants' lines.
54   };
55 
56   // We print a "#<id>" for nonterminal forest nodes that are being dumped
57   // multiple times.
58   llvm::DenseMap<const ForestNode *, size_t> ReferenceIds;
59   std::string Result;
60   constexpr Token::Index KEnd = std::numeric_limits<Token::Index>::max();
61   std::function<void(const ForestNode *, Token::Index, llvm::Optional<SymbolID>,
62                      LineDecoration &LineDec)>
63       Dump = [&](const ForestNode *P, Token::Index End,
64                  llvm::Optional<SymbolID> ElidedParent,
65                  LineDecoration LineDec) {
66         llvm::ArrayRef<const ForestNode *> Children;
67         auto EndOfElement = [&](size_t ChildIndex) {
68           return ChildIndex + 1 == Children.size()
69                      ? End
70                      : Children[ChildIndex + 1]->startTokenIndex();
71         };
72         if (P->kind() == Ambiguous) {
73           Children = P->alternatives();
74         } else if (P->kind() == Sequence) {
75           Children = P->elements();
76           if (Abbreviated) {
77             if (Children.size() == 1) {
78               assert(Children[0]->startTokenIndex() == P->startTokenIndex() &&
79                      EndOfElement(0) == End);
80               return Dump(Children[0], End,
81                           /*ElidedParent=*/ElidedParent.getValueOr(P->symbol()),
82                           LineDec);
83             }
84           }
85         }
86 
87         if (End == KEnd)
88           Result += llvm::formatv("[{0,3}, end) ", P->startTokenIndex());
89         else
90           Result += llvm::formatv("[{0,3}, {1,3}) ", P->startTokenIndex(), End);
91         Result += LineDec.Prefix;
92         Result += LineDec.First;
93         if (ElidedParent.hasValue()) {
94           Result += G.symbolName(*ElidedParent);
95           Result += "~";
96         }
97         Result.append(P->dump(G));
98 
99         if (VisitCounts.find(P)->getSecond() > 1 &&
100             P->kind() != ForestNode::Terminal) {
101           // The first time, print as #1. Later, =#1.
102           auto It = ReferenceIds.try_emplace(P, ReferenceIds.size() + 1);
103           Result +=
104               llvm::formatv(" {0}#{1}", It.second ? "" : "=", It.first->second);
105         }
106         Result.push_back('\n');
107 
108         auto OldPrefixSize = LineDec.Prefix.size();
109         LineDec.Prefix += LineDec.Subsequent;
110         for (size_t I = 0; I < Children.size(); ++I) {
111           if (I == Children.size() - 1) {
112             LineDec.First = "└─";
113             LineDec.Subsequent = "  ";
114           } else {
115             LineDec.First = "├─";
116             LineDec.Subsequent = "│ ";
117           }
118           Dump(Children[I], P->kind() == Sequence ? EndOfElement(I) : End,
119                llvm::None, LineDec);
120         }
121         LineDec.Prefix.resize(OldPrefixSize);
122       };
123   LineDecoration LineDec;
124   Dump(this, KEnd, llvm::None, LineDec);
125   return Result;
126 }
127 
128 llvm::ArrayRef<ForestNode>
129 ForestArena::createTerminals(const TokenStream &Code) {
130   ForestNode *Terminals = Arena.Allocate<ForestNode>(Code.tokens().size());
131   size_t Index = 0;
132   for (const auto &T : Code.tokens()) {
133     new (&Terminals[Index])
134         ForestNode(ForestNode::Terminal, tokenSymbol(T.Kind),
135                    /*Start=*/Index, /*TerminalData*/ 0);
136     ++Index;
137   }
138   NodeCount = Index;
139   return llvm::makeArrayRef(Terminals, Index);
140 }
141 
142 } // namespace pseudo
143 } // namespace clang
144