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