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