flang/lib/Evaluate/constant.cpp

   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 bool ConstantBounds::HasNonDefaultLowerBound() const {
  60   for (auto n : lbounds_) {
  61     if (n != 1) {
  62       return true;
  63     }
  64   }
  65   return false;
  66 }
  67
  68 ConstantSubscript 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
  83 std::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
  97 bool 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
 116 std::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
 135 bool HasNegativeExtent(const ConstantSubscripts &shape) {
 136   for (ConstantSubscript extent : shape) {
 137     if (extent < 0) {
 138       return true;
 139     }
 140   }
 141   return false;
 142 }
 143
 144 template <typename RESULT, typename ELEMENT>
 145 ConstantBase<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
 151 template <typename RESULT, typename ELEMENT>
 152 ConstantBase<RESULT, ELEMENT>::~ConstantBase() {}
 153
 154 template <typename RESULT, typename ELEMENT>
 155 bool ConstantBase<RESULT, ELEMENT>::operator==(const ConstantBase &that) const {
 156   return shape() == that.shape() && values_ == that.values_;
 157 }
 158
 159 template <typename RESULT, typename ELEMENT>
 160 auto 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
 177 template <typename RESULT, typename ELEMENT>
 178 std::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
 193 template <typename T>
 194 auto Constant<T>::At(const ConstantSubscripts &index) const -> Element {
 195   return Base::values_.at(Base::SubscriptsToOffset(index));
 196 }
 197
 198 template <typename T>
 199 auto Constant<T>::Reshape(ConstantSubscripts &&dims) const -> Constant {
 200   return {Base::Reshape(dims), std::move(dims)};
 201 }
 202
 203 template <typename T>
 204 std::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
 210 template <int KIND>
 211 Constant<Type<TypeCategory::Character, KIND>>::Constant(
 212     const Scalar<Result> &str)
 213     : values_{str}, length_{static_cast<ConstantSubscript>(values_.size())} {}
 214
 215 template <int KIND>
 216 Constant<Type<TypeCategory::Character, KIND>>::Constant(Scalar<Result> &&str)
 217     : values_{std::move(str)}, length_{static_cast<ConstantSubscript>(
 218                                    values_.size())} {}
 219
 220 template <int KIND>
 221 Constant<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
 241 template <int KIND>
 242 Constant<Type<TypeCategory::Character, KIND>>::~Constant() {}
 243
 244 template <int KIND>
 245 bool Constant<Type<TypeCategory::Character, KIND>>::empty() const {
 246   return size() == 0;
 247 }
 248
 249 template <int KIND>
 250 std::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
 260 template <int KIND>
 261 auto 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
 267 template <int KIND>
 268 auto 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
 289 template <int KIND>
 290 auto 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
 309 template <int KIND>
 310 std::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
 338 Constant<SomeDerived>::Constant(const StructureConstructor &x)
 339     : Base{x.values(), Result{x.derivedTypeSpec()}} {}
 340
 341 Constant<SomeDerived>::Constant(StructureConstructor &&x)
 342     : Base{std::move(x.values()), Result{x.derivedTypeSpec()}} {}
 343
 344 Constant<SomeDerived>::Constant(const semantics::DerivedTypeSpec &spec,
 345     std::vector<StructureConstructorValues> &&x, ConstantSubscripts &&s)
 346     : Base{std::move(x), std::move(s), Result{spec}} {}
 347
 348 static 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
 357 Constant<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
 361 std::optional<StructureConstructor>
 362 Constant<SomeDerived>::GetScalarValue() const {
 363   if (Rank() == 0) {
 364     return StructureConstructor{result().derivedTypeSpec(), values_.at(0)};
 365   } else {
 366     return std::nullopt;
 367   }
 368 }
 369
 370 StructureConstructor Constant<SomeDerived>::At(
 371     const ConstantSubscripts &index) const {
 372   return {result().derivedTypeSpec(), values_.at(SubscriptsToOffset(index))};
 373 }
 374
 375 bool 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
 381 auto Constant<SomeDerived>::Reshape(ConstantSubscripts &&dims) const
 382     -> Constant {
 383   return {result().derivedTypeSpec(), Base::Reshape(dims), std::move(dims)};
 384 }
 385
 386 std::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
 392 bool 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
 399 INSTANTIATE_CONSTANT_TEMPLATES
 400 } // namespace Fortran::evaluate