Warning: This file is not a C or C++ file. It does not have highlighting.

1//===-- include/flang/Evaluate/traverse.h -----------------------*- 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#ifndef FORTRAN_EVALUATE_TRAVERSE_H_
10#define FORTRAN_EVALUATE_TRAVERSE_H_
11
12// A utility for scanning all of the constituent objects in an Expr<>
13// expression representation using a collection of mutually recursive
14// functions to compose a function object.
15//
16// The class template Traverse<> below implements a function object that
17// can handle every type that can appear in or around an Expr<>.
18// Each of its overloads for operator() should be viewed as a *default*
19// handler; some of these must be overridden by the client to accomplish
20// its particular task.
21//
22// The client (Visitor) of Traverse<Visitor,Result> must define:
23// - a member function "Result Default();"
24// - a member function "Result Combine(Result &&, Result &&)"
25// - overrides for "Result operator()"
26//
27// Boilerplate classes also appear below to ease construction of visitors.
28// See CheckSpecificationExpr() in check-expression.cpp for an example client.
29//
30// How this works:
31// - The operator() overloads in Traverse<> invoke the visitor's Default() for
32// expression leaf nodes. They invoke the visitor's operator() for the
33// subtrees of interior nodes, and the visitor's Combine() to merge their
34// results together.
35// - Overloads of operator() in each visitor handle the cases of interest.
36//
37// The default handler for semantics::Symbol will descend into the associated
38// expression of an ASSOCIATE (or related) construct entity.
39
40#include "expression.h"
41#include "flang/Common/indirection.h"
42#include "flang/Semantics/symbol.h"
43#include "flang/Semantics/type.h"
44#include <set>
45#include <type_traits>
46
47namespace Fortran::evaluate {
48template <typename Visitor, typename Result,
49 bool TraverseAssocEntityDetails = true>
50class Traverse {
51public:
52 explicit Traverse(Visitor &v) : visitor_{v} {}
53
54 // Packaging
55 template <typename A, bool C>
56 Result operator()(const common::Indirection<A, C> &x) const {
57 return visitor_(x.value());
58 }
59 template <typename A>
60 Result operator()(const common::ForwardOwningPointer<A> &p) const {
61 return visitor_(p.get());
62 }
63 template <typename _> Result operator()(const SymbolRef x) const {
64 return visitor_(*x);
65 }
66 template <typename A> Result operator()(const std::unique_ptr<A> &x) const {
67 return visitor_(x.get());
68 }
69 template <typename A> Result operator()(const std::shared_ptr<A> &x) const {
70 return visitor_(x.get());
71 }
72 template <typename A> Result operator()(const A *x) const {
73 if (x) {
74 return visitor_(*x);
75 } else {
76 return visitor_.Default();
77 }
78 }
79 template <typename A> Result operator()(const std::optional<A> &x) const {
80 if (x) {
81 return visitor_(*x);
82 } else {
83 return visitor_.Default();
84 }
85 }
86 template <typename... As>
87 Result operator()(const std::variant<As...> &u) const {
88 return common::visit([=](const auto &y) { return visitor_(y); }, u);
89 }
90 template <typename A> Result operator()(const std::vector<A> &x) const {
91 return CombineContents(x);
92 }
93 template <typename A, typename B>
94 Result operator()(const std::pair<A, B> &x) const {
95 return Combine(x.first, x.second);
96 }
97
98 // Leaves
99 Result operator()(const BOZLiteralConstant &) const {
100 return visitor_.Default();
101 }
102 Result operator()(const NullPointer &) const { return visitor_.Default(); }
103 template <typename T> Result operator()(const Constant<T> &x) const {
104 if constexpr (T::category == TypeCategory::Derived) {
105 return visitor_.Combine(
106 visitor_(x.result().derivedTypeSpec()), CombineContents(x.values()));
107 } else {
108 return visitor_.Default();
109 }
110 }
111 Result operator()(const Symbol &symbol) const {
112 const Symbol &ultimate{symbol.GetUltimate()};
113 if constexpr (TraverseAssocEntityDetails) {
114 if (const auto *assoc{
115 ultimate.detailsIf<semantics::AssocEntityDetails>()}) {
116 return visitor_(assoc->expr());
117 }
118 }
119 return visitor_.Default();
120 }
121 Result operator()(const StaticDataObject &) const {
122 return visitor_.Default();
123 }
124 Result operator()(const ImpliedDoIndex &) const { return visitor_.Default(); }
125
126 // Variables
127 Result operator()(const BaseObject &x) const { return visitor_(x.u); }
128 Result operator()(const Component &x) const {
129 return Combine(x.base(), x.symbol());
130 }
131 Result operator()(const NamedEntity &x) const {
132 if (const Component * component{x.UnwrapComponent()}) {
133 return visitor_(*component);
134 } else {
135 return visitor_(DEREF(x.UnwrapSymbolRef()));
136 }
137 }
138 Result operator()(const TypeParamInquiry &x) const {
139 return visitor_(x.base());
140 }
141 Result operator()(const Triplet &x) const {
142 return Combine(x.lower(), x.upper(), x.stride());
143 }
144 Result operator()(const Subscript &x) const { return visitor_(x.u); }
145 Result operator()(const ArrayRef &x) const {
146 return Combine(x.base(), x.subscript());
147 }
148 Result operator()(const CoarrayRef &x) const {
149 return Combine(
150 x.base(), x.subscript(), x.cosubscript(), x.stat(), x.team());
151 }
152 Result operator()(const DataRef &x) const { return visitor_(x.u); }
153 Result operator()(const Substring &x) const {
154 return Combine(x.parent(), x.lower(), x.upper());
155 }
156 Result operator()(const ComplexPart &x) const {
157 return visitor_(x.complex());
158 }
159 template <typename T> Result operator()(const Designator<T> &x) const {
160 return visitor_(x.u);
161 }
162 template <typename T> Result operator()(const Variable<T> &x) const {
163 return visitor_(x.u);
164 }
165 Result operator()(const DescriptorInquiry &x) const {
166 return visitor_(x.base());
167 }
168
169 // Calls
170 Result operator()(const SpecificIntrinsic &) const {
171 return visitor_.Default();
172 }
173 Result operator()(const ProcedureDesignator &x) const {
174 if (const Component * component{x.GetComponent()}) {
175 return visitor_(*component);
176 } else if (const Symbol * symbol{x.GetSymbol()}) {
177 return visitor_(*symbol);
178 } else {
179 return visitor_(DEREF(x.GetSpecificIntrinsic()));
180 }
181 }
182 Result operator()(const ActualArgument &x) const {
183 if (const auto *symbol{x.GetAssumedTypeDummy()}) {
184 return visitor_(*symbol);
185 } else {
186 return visitor_(x.UnwrapExpr());
187 }
188 }
189 Result operator()(const ProcedureRef &x) const {
190 return Combine(x.proc(), x.arguments());
191 }
192 template <typename T> Result operator()(const FunctionRef<T> &x) const {
193 return visitor_(static_cast<const ProcedureRef &>(x));
194 }
195
196 // Other primaries
197 template <typename T>
198 Result operator()(const ArrayConstructorValue<T> &x) const {
199 return visitor_(x.u);
200 }
201 template <typename T>
202 Result operator()(const ArrayConstructorValues<T> &x) const {
203 return CombineContents(x);
204 }
205 template <typename T> Result operator()(const ImpliedDo<T> &x) const {
206 return Combine(x.lower(), x.upper(), x.stride(), x.values());
207 }
208 Result operator()(const semantics::ParamValue &x) const {
209 return visitor_(x.GetExplicit());
210 }
211 Result operator()(
212 const semantics::DerivedTypeSpec::ParameterMapType::value_type &x) const {
213 return visitor_(x.second);
214 }
215 Result operator()(
216 const semantics::DerivedTypeSpec::ParameterMapType &x) const {
217 return CombineContents(x);
218 }
219 Result operator()(const semantics::DerivedTypeSpec &x) const {
220 return Combine(x.typeSymbol(), x.parameters());
221 }
222 Result operator()(const StructureConstructorValues::value_type &x) const {
223 return visitor_(x.second);
224 }
225 Result operator()(const StructureConstructorValues &x) const {
226 return CombineContents(x);
227 }
228 Result operator()(const StructureConstructor &x) const {
229 return visitor_.Combine(visitor_(x.derivedTypeSpec()), CombineContents(x));
230 }
231
232 // Operations and wrappers
233 template <typename D, typename R, typename O>
234 Result operator()(const Operation<D, R, O> &op) const {
235 return visitor_(op.left());
236 }
237 template <typename D, typename R, typename LO, typename RO>
238 Result operator()(const Operation<D, R, LO, RO> &op) const {
239 return Combine(op.left(), op.right());
240 }
241 Result operator()(const Relational<SomeType> &x) const {
242 return visitor_(x.u);
243 }
244 template <typename T> Result operator()(const Expr<T> &x) const {
245 return visitor_(x.u);
246 }
247 Result operator()(const Assignment &x) const {
248 return Combine(x.lhs, x.rhs, x.u);
249 }
250 Result operator()(const Assignment::Intrinsic &) const {
251 return visitor_.Default();
252 }
253 Result operator()(const GenericExprWrapper &x) const { return visitor_(x.v); }
254 Result operator()(const GenericAssignmentWrapper &x) const {
255 return visitor_(x.v);
256 }
257
258private:
259 template <typename ITER> Result CombineRange(ITER iter, ITER end) const {
260 if (iter == end) {
261 return visitor_.Default();
262 } else {
263 Result result{visitor_(*iter)};
264 for (++iter; iter != end; ++iter) {
265 result = visitor_.Combine(std::move(result), visitor_(*iter));
266 }
267 return result;
268 }
269 }
270
271 template <typename A> Result CombineContents(const A &x) const {
272 return CombineRange(x.begin(), x.end());
273 }
274
275 template <typename A, typename... Bs>
276 Result Combine(const A &x, const Bs &...ys) const {
277 if constexpr (sizeof...(Bs) == 0) {
278 return visitor_(x);
279 } else {
280 return visitor_.Combine(visitor_(x), Combine(ys...));
281 }
282 }
283
284 Visitor &visitor_;
285};
286
287// For validity checks across an expression: if any operator() result is
288// false, so is the overall result.
289template <typename Visitor, bool DefaultValue,
290 bool TraverseAssocEntityDetails = true,
291 typename Base = Traverse<Visitor, bool, TraverseAssocEntityDetails>>
292struct AllTraverse : public Base {
293 explicit AllTraverse(Visitor &v) : Base{v} {}
294 using Base::operator();
295 static bool Default() { return DefaultValue; }
296 static bool Combine(bool x, bool y) { return x && y; }
297};
298
299// For searches over an expression: the first operator() result that
300// is truthful is the final result. Works for Booleans, pointers,
301// and std::optional<>.
302template <typename Visitor, typename Result = bool,
303 bool TraverseAssocEntityDetails = true,
304 typename Base = Traverse<Visitor, Result, TraverseAssocEntityDetails>>
305class AnyTraverse : public Base {
306public:
307 explicit AnyTraverse(Visitor &v) : Base{v} {}
308 using Base::operator();
309 Result Default() const { return default_; }
310 static Result Combine(Result &&x, Result &&y) {
311 if (x) {
312 return std::move(x);
313 } else {
314 return std::move(y);
315 }
316 }
317
318private:
319 Result default_{};
320};
321
322template <typename Visitor, typename Set,
323 bool TraverseAssocEntityDetails = true,
324 typename Base = Traverse<Visitor, Set, TraverseAssocEntityDetails>>
325struct SetTraverse : public Base {
326 explicit SetTraverse(Visitor &v) : Base{v} {}
327 using Base::operator();
328 static Set Default() { return {}; }
329 static Set Combine(Set &&x, Set &&y) {
330#if defined __GNUC__ && !defined __APPLE__ && !(CLANG_LIBRARIES)
331 x.merge(y);
332#else
333 // std::set::merge() not available (yet)
334 for (auto &value : y) {
335 x.insert(std::move(value));
336 }
337#endif
338 return std::move(x);
339 }
340};
341
342} // namespace Fortran::evaluate
343#endif
344

Warning: This file is not a C or C++ file. It does not have highlighting.

source code of flang/include/flang/Evaluate/traverse.h