1//===-- lib/Evaluate/constant.cpp -----------------------------------------===//
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 "flang/Evaluate/constant.h"
10#include "flang/Evaluate/expression.h"
11#include "flang/Evaluate/shape.h"
12#include "flang/Evaluate/type.h"
13#include <string>
14
15namespace Fortran::evaluate {
16
17ConstantBounds::ConstantBounds(const ConstantSubscripts &shape)
18 : shape_(shape), lbounds_(shape_.size(), 1) {}
19
20ConstantBounds::ConstantBounds(ConstantSubscripts &&shape)
21 : shape_(std::move(shape)), lbounds_(shape_.size(), 1) {}
22
23ConstantBounds::~ConstantBounds() = default;
24
25void ConstantBounds::set_lbounds(ConstantSubscripts &&lb) {
26 CHECK(lb.size() == shape_.size());
27 lbounds_ = std::move(lb);
28 for (std::size_t j{0}; j < shape_.size(); ++j) {
29 if (shape_[j] == 0) {
30 lbounds_[j] = 1;
31 }
32 }
33}
34
35ConstantSubscripts ConstantBounds::ComputeUbounds(
36 std::optional<int> dim) const {
37 if (dim) {
38 CHECK(*dim < Rank());
39 return {lbounds_[*dim] + (shape_[*dim] - 1)};
40 } else {
41 ConstantSubscripts ubounds(Rank());
42 for (int i{0}; i < Rank(); ++i) {
43 ubounds[i] = lbounds_[i] + (shape_[i] - 1);
44 }
45 return ubounds;
46 }
47}
48
49void ConstantBounds::SetLowerBoundsToOne() {
50 for (auto &n : lbounds_) {
51 n = 1;
52 }
53}
54
55Constant<SubscriptInteger> ConstantBounds::SHAPE() const {
56 return AsConstantShape(shape_);
57}
58
59bool ConstantBounds::HasNonDefaultLowerBound() const {
60 for (auto n : lbounds_) {
61 if (n != 1) {
62 return true;
63 }
64 }
65 return false;
66}
67
68ConstantSubscript ConstantBounds::SubscriptsToOffset(
69 const ConstantSubscripts &index) const {
70 CHECK(GetRank(index) == GetRank(shape_));
71 ConstantSubscript stride{1}, offset{0};
72 int dim{0};
73 for (auto j : index) {
74 auto lb{lbounds_[dim]};
75 auto extent{shape_[dim++]};
76 CHECK(j >= lb && j - lb < extent);
77 offset += stride * (j - lb);
78 stride *= extent;
79 }
80 return offset;
81}
82
83std::optional<uint64_t> TotalElementCount(const ConstantSubscripts &shape) {
84 uint64_t size{1};
85 for (auto dim : shape) {
86 CHECK(dim >= 0);
87 uint64_t osize{size};
88 size = osize * dim;
89 if (size > std::numeric_limits<decltype(dim)>::max() ||
90 (dim != 0 && size / dim != osize)) {
91 return std::nullopt;
92 }
93 }
94 return static_cast<uint64_t>(GetSize(shape));
95}
96
97bool ConstantBounds::IncrementSubscripts(
98 ConstantSubscripts &indices, const std::vector<int> *dimOrder) const {
99 int rank{GetRank(shape_)};
100 CHECK(GetRank(indices) == rank);
101 CHECK(!dimOrder || static_cast<int>(dimOrder->size()) == rank);
102 for (int j{0}; j < rank; ++j) {
103 ConstantSubscript k{dimOrder ? (*dimOrder)[j] : j};
104 auto lb{lbounds_[k]};
105 CHECK(indices[k] >= lb);
106 if (++indices[k] - lb < shape_[k]) {
107 return true;
108 } else {
109 CHECK(indices[k] - lb == std::max<ConstantSubscript>(shape_[k], 1));
110 indices[k] = lb;
111 }
112 }
113 return false; // all done
114}
115
116std::optional<std::vector<int>> ValidateDimensionOrder(
117 int rank, const std::vector<int> &order) {
118 std::vector<int> dimOrder(rank);
119 if (static_cast<int>(order.size()) == rank) {
120 std::bitset<common::maxRank> seenDimensions;
121 for (int j{0}; j < rank; ++j) {
122 int dim{order[j]};
123 if (dim < 1 || dim > rank || seenDimensions.test(dim - 1)) {
124 return std::nullopt;
125 }
126 dimOrder[j] = dim - 1;
127 seenDimensions.set(dim - 1);
128 }
129 return dimOrder;
130 } else {
131 return std::nullopt;
132 }
133}
134
135bool HasNegativeExtent(const ConstantSubscripts &shape) {
136 for (ConstantSubscript extent : shape) {
137 if (extent < 0) {
138 return true;
139 }
140 }
141 return false;
142}
143
144template <typename RESULT, typename ELEMENT>
145ConstantBase<RESULT, ELEMENT>::ConstantBase(
146 std::vector<Element> &&x, ConstantSubscripts &&sh, Result res)
147 : ConstantBounds(std::move(sh)), result_{res}, values_(std::move(x)) {
148 CHECK(TotalElementCount(shape()) && size() == *TotalElementCount(shape()));
149}
150
151template <typename RESULT, typename ELEMENT>
152ConstantBase<RESULT, ELEMENT>::~ConstantBase() {}
153
154template <typename RESULT, typename ELEMENT>
155bool ConstantBase<RESULT, ELEMENT>::operator==(const ConstantBase &that) const {
156 return shape() == that.shape() && values_ == that.values_;
157}
158
159template <typename RESULT, typename ELEMENT>
160auto ConstantBase<RESULT, ELEMENT>::Reshape(
161 const ConstantSubscripts &dims) const -> std::vector<Element> {
162 std::optional<uint64_t> optN{TotalElementCount(dims)};
163 CHECK_MSG(optN, "Overflow in TotalElementCount");
164 uint64_t n{*optN};
165 CHECK(!empty() || n == 0);
166 std::vector<Element> elements;
167 auto iter{values().cbegin()};
168 while (n-- > 0) {
169 elements.push_back(*iter);
170 if (++iter == values().cend()) {
171 iter = values().cbegin();
172 }
173 }
174 return elements;
175}
176
177template <typename RESULT, typename ELEMENT>
178std::size_t ConstantBase<RESULT, ELEMENT>::CopyFrom(
179 const ConstantBase<RESULT, ELEMENT> &source, std::size_t count,
180 ConstantSubscripts &resultSubscripts, const std::vector<int> *dimOrder) {
181 std::size_t copied{0};
182 ConstantSubscripts sourceSubscripts{source.lbounds()};
183 while (copied < count) {
184 values_.at(SubscriptsToOffset(resultSubscripts)) =
185 source.values_.at(source.SubscriptsToOffset(sourceSubscripts));
186 copied++;
187 source.IncrementSubscripts(sourceSubscripts);
188 IncrementSubscripts(resultSubscripts, dimOrder);
189 }
190 return copied;
191}
192
193template <typename T>
194auto Constant<T>::At(const ConstantSubscripts &index) const -> Element {
195 return Base::values_.at(Base::SubscriptsToOffset(index));
196}
197
198template <typename T>
199auto Constant<T>::Reshape(ConstantSubscripts &&dims) const -> Constant {
200 return {Base::Reshape(dims), std::move(dims)};
201}
202
203template <typename T>
204std::size_t Constant<T>::CopyFrom(const Constant<T> &source, std::size_t count,
205 ConstantSubscripts &resultSubscripts, const std::vector<int> *dimOrder) {
206 return Base::CopyFrom(source, count, resultSubscripts, dimOrder);
207}
208
209// Constant<Type<TypeCategory::Character, KIND> specializations
210template <int KIND>
211Constant<Type<TypeCategory::Character, KIND>>::Constant(
212 const Scalar<Result> &str)
213 : values_{str}, length_{static_cast<ConstantSubscript>(values_.size())} {}
214
215template <int KIND>
216Constant<Type<TypeCategory::Character, KIND>>::Constant(Scalar<Result> &&str)
217 : values_{std::move(str)}, length_{static_cast<ConstantSubscript>(
218 values_.size())} {}
219
220template <int KIND>
221Constant<Type<TypeCategory::Character, KIND>>::Constant(ConstantSubscript len,
222 std::vector<Scalar<Result>> &&strings, ConstantSubscripts &&sh)
223 : ConstantBounds(std::move(sh)), length_{len} {
224 CHECK(TotalElementCount(shape()) &&
225 strings.size() == *TotalElementCount(shape()));
226 values_.assign(strings.size() * length_,
227 static_cast<typename Scalar<Result>::value_type>(' '));
228 ConstantSubscript at{0};
229 for (const auto &str : strings) {
230 auto strLen{static_cast<ConstantSubscript>(str.size())};
231 if (strLen > length_) {
232 values_.replace(at, length_, str.substr(0, length_));
233 } else {
234 values_.replace(at, strLen, str);
235 }
236 at += length_;
237 }
238 CHECK(at == static_cast<ConstantSubscript>(values_.size()));
239}
240
241template <int KIND>
242Constant<Type<TypeCategory::Character, KIND>>::~Constant() {}
243
244template <int KIND>
245bool Constant<Type<TypeCategory::Character, KIND>>::empty() const {
246 return size() == 0;
247}
248
249template <int KIND>
250std::size_t Constant<Type<TypeCategory::Character, KIND>>::size() const {
251 if (length_ == 0) {
252 std::optional<uint64_t> n{TotalElementCount(shape())};
253 CHECK(n);
254 return *n;
255 } else {
256 return static_cast<ConstantSubscript>(values_.size()) / length_;
257 }
258}
259
260template <int KIND>
261auto Constant<Type<TypeCategory::Character, KIND>>::At(
262 const ConstantSubscripts &index) const -> Scalar<Result> {
263 auto offset{SubscriptsToOffset(index)};
264 return values_.substr(offset * length_, length_);
265}
266
267template <int KIND>
268auto Constant<Type<TypeCategory::Character, KIND>>::Substring(
269 ConstantSubscript lo, ConstantSubscript hi) const
270 -> std::optional<Constant> {
271 std::vector<Element> elements;
272 ConstantSubscript n{GetSize(shape())};
273 ConstantSubscript newLength{0};
274 if (lo > hi) { // zero-length results
275 while (n-- > 0) {
276 elements.emplace_back(); // ""
277 }
278 } else if (lo < 1 || hi > length_) {
279 return std::nullopt;
280 } else {
281 newLength = hi - lo + 1;
282 for (ConstantSubscripts at{lbounds()}; n-- > 0; IncrementSubscripts(at)) {
283 elements.emplace_back(At(at).substr(lo - 1, newLength));
284 }
285 }
286 return Constant{newLength, std::move(elements), ConstantSubscripts{shape()}};
287}
288
289template <int KIND>
290auto Constant<Type<TypeCategory::Character, KIND>>::Reshape(
291 ConstantSubscripts &&dims) const -> Constant<Result> {
292 std::optional<uint64_t> optN{TotalElementCount(dims)};
293 CHECK(optN);
294 uint64_t n{*optN};
295 CHECK(!empty() || n == 0);
296 std::vector<Element> elements;
297 ConstantSubscript at{0},
298 limit{static_cast<ConstantSubscript>(values_.size())};
299 while (n-- > 0) {
300 elements.push_back(values_.substr(at, length_));
301 at += length_;
302 if (at == limit) { // subtle: at > limit somehow? substr() will catch it
303 at = 0;
304 }
305 }
306 return {length_, std::move(elements), std::move(dims)};
307}
308
309template <int KIND>
310std::size_t Constant<Type<TypeCategory::Character, KIND>>::CopyFrom(
311 const Constant<Type<TypeCategory::Character, KIND>> &source,
312 std::size_t count, ConstantSubscripts &resultSubscripts,
313 const std::vector<int> *dimOrder) {
314 CHECK(length_ == source.length_);
315 if (length_ == 0) {
316 // It's possible that the array of strings consists of all empty strings.
317 // If so, constant folding will result in a string that's completely empty
318 // and the length_ will be zero, and there's nothing to do.
319 return count;
320 } else {
321 std::size_t copied{0};
322 std::size_t elementBytes{length_ * sizeof(decltype(values_[0]))};
323 ConstantSubscripts sourceSubscripts{source.lbounds()};
324 while (copied < count) {
325 auto *dest{&values_.at(SubscriptsToOffset(resultSubscripts) * length_)};
326 const auto *src{&source.values_.at(
327 source.SubscriptsToOffset(sourceSubscripts) * length_)};
328 std::memcpy(dest, src, elementBytes);
329 copied++;
330 source.IncrementSubscripts(sourceSubscripts);
331 IncrementSubscripts(resultSubscripts, dimOrder);
332 }
333 return copied;
334 }
335}
336
337// Constant<SomeDerived> specialization
338Constant<SomeDerived>::Constant(const StructureConstructor &x)
339 : Base{x.values(), Result{x.derivedTypeSpec()}} {}
340
341Constant<SomeDerived>::Constant(StructureConstructor &&x)
342 : Base{std::move(x.values()), Result{x.derivedTypeSpec()}} {}
343
344Constant<SomeDerived>::Constant(const semantics::DerivedTypeSpec &spec,
345 std::vector<StructureConstructorValues> &&x, ConstantSubscripts &&s)
346 : Base{std::move(x), std::move(s), Result{spec}} {}
347
348static std::vector<StructureConstructorValues> AcquireValues(
349 std::vector<StructureConstructor> &&x) {
350 std::vector<StructureConstructorValues> result;
351 for (auto &&structure : std::move(x)) {
352 result.emplace_back(std::move(structure.values()));
353 }
354 return result;
355}
356
357Constant<SomeDerived>::Constant(const semantics::DerivedTypeSpec &spec,
358 std::vector<StructureConstructor> &&x, ConstantSubscripts &&shape)
359 : Base{AcquireValues(std::move(x)), std::move(shape), Result{spec}} {}
360
361std::optional<StructureConstructor>
362Constant<SomeDerived>::GetScalarValue() const {
363 if (Rank() == 0) {
364 return StructureConstructor{result().derivedTypeSpec(), values_.at(0)};
365 } else {
366 return std::nullopt;
367 }
368}
369
370StructureConstructor Constant<SomeDerived>::At(
371 const ConstantSubscripts &index) const {
372 return {result().derivedTypeSpec(), values_.at(SubscriptsToOffset(index))};
373}
374
375bool Constant<SomeDerived>::operator==(
376 const Constant<SomeDerived> &that) const {
377 return result().derivedTypeSpec() == that.result().derivedTypeSpec() &&
378 shape() == that.shape() && values_ == that.values_;
379}
380
381auto Constant<SomeDerived>::Reshape(ConstantSubscripts &&dims) const
382 -> Constant {
383 return {result().derivedTypeSpec(), Base::Reshape(dims), std::move(dims)};
384}
385
386std::size_t Constant<SomeDerived>::CopyFrom(const Constant<SomeDerived> &source,
387 std::size_t count, ConstantSubscripts &resultSubscripts,
388 const std::vector<int> *dimOrder) {
389 return Base::CopyFrom(source, count, resultSubscripts, dimOrder);
390}
391
392bool ComponentCompare::operator()(SymbolRef x, SymbolRef y) const {
393 return semantics::SymbolSourcePositionCompare{}(x, y);
394}
395
396#ifdef _MSC_VER // disable bogus warning about missing definitions
397#pragma warning(disable : 4661)
398#endif
399INSTANTIATE_CONSTANT_TEMPLATES
400} // namespace Fortran::evaluate
401

source code of flang/lib/Evaluate/constant.cpp