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         bool SharedNode = VisitCounts.find(P)->getSecond() > 1;
67         llvm::ArrayRef<const ForestNode *> Children;
68         auto EndOfElement = [&](size_t ChildIndex) {
69           return ChildIndex + 1 == Children.size()
70                      ? End
71                      : Children[ChildIndex + 1]->startTokenIndex();
72         };
73         if (P->kind() == Ambiguous) {
74           Children = P->alternatives();
75         } else if (P->kind() == Sequence) {
76           Children = P->elements();
77           if (Abbreviated) {
78             // Abbreviate chains of trivial sequence nodes.
79             //    A := B, B := C, C := D, D := X Y Z
80             // becomes
81             //    A~D := X Y Z
82             //
83             // We can't hide nodes that appear multiple times in the tree,
84             // because we need to call out their identity with IDs.
85             if (Children.size() == 1 && !SharedNode) {
86               assert(Children[0]->startTokenIndex() == P->startTokenIndex() &&
87                      EndOfElement(0) == End);
88               return Dump(Children[0], End,
89                           /*ElidedParent=*/ElidedParent.value_or(P->symbol()),
90                           LineDec);
91             }
92           }
93         }
94 
95         if (End == KEnd)
96           Result += llvm::formatv("[{0,3}, end) ", P->startTokenIndex());
97         else
98           Result += llvm::formatv("[{0,3}, {1,3}) ", P->startTokenIndex(), End);
99         Result += LineDec.Prefix;
100         Result += LineDec.First;
101         if (ElidedParent) {
102           Result += G.symbolName(*ElidedParent);
103           Result += "~";
104         }
105 
106         if (SharedNode && P->kind() != ForestNode::Terminal) {
107           auto It = ReferenceIds.try_emplace(P, ReferenceIds.size() + 1);
108           bool First = It.second;
109           unsigned ID = It.first->second;
110 
111           // The first time, print as #1. Later, =#1.
112           if (First) {
113             Result += llvm::formatv("{0} #{1}", P->dump(G), ID);
114           } else {
115             Result += llvm::formatv("{0} =#{1}", G.symbolName(P->symbol()), ID);
116             Children = {}; // Don't walk the children again.
117           }
118         } else {
119           Result.append(P->dump(G));
120         }
121         Result.push_back('\n');
122 
123         auto OldPrefixSize = LineDec.Prefix.size();
124         LineDec.Prefix += LineDec.Subsequent;
125         for (size_t I = 0; I < Children.size(); ++I) {
126           if (I == Children.size() - 1) {
127             LineDec.First = "└─";
128             LineDec.Subsequent = "  ";
129           } else {
130             LineDec.First = "├─";
131             LineDec.Subsequent = "│ ";
132           }
133           Dump(Children[I], P->kind() == Sequence ? EndOfElement(I) : End,
134                llvm::None, LineDec);
135         }
136         LineDec.Prefix.resize(OldPrefixSize);
137       };
138   LineDecoration LineDec;
139   Dump(this, KEnd, llvm::None, LineDec);
140   return Result;
141 }
142 
143 llvm::ArrayRef<ForestNode>
144 ForestArena::createTerminals(const TokenStream &Code) {
145   ForestNode *Terminals = Arena.Allocate<ForestNode>(Code.tokens().size());
146   size_t Index = 0;
147   for (const auto &T : Code.tokens()) {
148     new (&Terminals[Index])
149         ForestNode(ForestNode::Terminal, tokenSymbol(T.Kind),
150                    /*Start=*/Index, /*TerminalData*/ 0);
151     ++Index;
152   }
153   NodeCount = Index;
154   return llvm::makeArrayRef(Terminals, Index);
155 }
156 
157 } // namespace pseudo
158 } // namespace clang
159