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 (P->startTokenIndex() == End)
78               return;
79             for (size_t I = 0; I < Children.size(); ++I)
80               if (Children[I]->startTokenIndex() == P->startTokenIndex() &&
81                   EndOfElement(I) == End) {
82                 return Dump(
83                     Children[I], End,
84                     /*ElidedParent=*/ElidedParent.getValueOr(P->symbol()),
85                     LineDec);
86               }
87           }
88         }
89 
90         if (End == KEnd)
91           Result += llvm::formatv("[{0,3}, end) ", P->startTokenIndex());
92         else
93           Result += llvm::formatv("[{0,3}, {1,3}) ", P->startTokenIndex(), End);
94         Result += LineDec.Prefix;
95         Result += LineDec.First;
96         if (ElidedParent.hasValue()) {
97           Result += G.symbolName(*ElidedParent);
98           Result += "~";
99         }
100         Result.append(P->dump(G));
101 
102         if (VisitCounts.find(P)->getSecond() > 1 &&
103             P->kind() != ForestNode::Terminal) {
104           // The first time, print as #1. Later, =#1.
105           auto It = ReferenceIds.try_emplace(P, ReferenceIds.size() + 1);
106           Result +=
107               llvm::formatv(" {0}#{1}", It.second ? "" : "=", It.first->second);
108         }
109         Result.push_back('\n');
110 
111         auto OldPrefixSize = LineDec.Prefix.size();
112         LineDec.Prefix += LineDec.Subsequent;
113         for (size_t I = 0; I < Children.size(); ++I) {
114           if (I == Children.size() - 1) {
115             LineDec.First = "└─";
116             LineDec.Subsequent = "  ";
117           } else {
118             LineDec.First = "├─";
119             LineDec.Subsequent = "│ ";
120           }
121           Dump(Children[I], P->kind() == Sequence ? EndOfElement(I) : End,
122                llvm::None, LineDec);
123         }
124         LineDec.Prefix.resize(OldPrefixSize);
125       };
126   LineDecoration LineDec;
127   Dump(this, KEnd, llvm::None, LineDec);
128   return Result;
129 }
130 
131 llvm::ArrayRef<ForestNode>
132 ForestArena::createTerminals(const TokenStream &Code) {
133   ForestNode *Terminals = Arena.Allocate<ForestNode>(Code.tokens().size());
134   size_t Index = 0;
135   for (const auto &T : Code.tokens()) {
136     new (&Terminals[Index])
137         ForestNode(ForestNode::Terminal, tokenSymbol(T.Kind),
138                    /*Start=*/Index, /*TerminalData*/ 0);
139     ++Index;
140   }
141   NodeCount = Index;
142   return llvm::makeArrayRef(Terminals, Index);
143 }
144 
145 } // namespace pseudo
146 } // namespace clang
147