flattype.h

// Copyright 2018-2019 Delft University of Technology
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
 
#pragma once
 
#include <algorithm>
#include <tuple>
#include <optional>
#include <utility>
#include <memory>
#include <vector>
#include <vector>
#include <string>
#include <sstream>
#include <iomanip>
#include <unordered_map>
 
#include "cerata/utils.h"
#include "cerata/logging.h"
 
namespace cerata {
 
class Type;
class Record;
class Stream;
class Node;
 
struct NamePart {
  NamePart() = default;
  explicit NamePart(std::string part, bool append_sep = true) : str(std::move(part)), sep(append_sep) {}
  std::string str = "";
  bool sep = false;
};
 
struct FlatType {
  FlatType() = default;
  FlatType(Type *t, std::vector<NamePart> prefix, const std::string &name, bool invert);
  Type *type_ = nullptr;
  int nesting_level_ = 0;
  std::vector<NamePart> name_parts_;
  bool reverse_ = false;
  [[nodiscard]] std::string name(const NamePart &root = NamePart(), const std::string &sep = "_") const;
};
 
bool operator<(const FlatType &a, const FlatType &b);
 
// Flattening functions for nested types:
 
void FlattenRecord(std::vector<FlatType> *list,
                   const Record *record,
                   const std::optional<FlatType> &parent,
                   bool invert);
 
void FlattenStream(std::vector<FlatType> *list,
                   const Stream *stream,
                   const std::optional<FlatType> &parent,
                   bool invert);
 
void Flatten(std::vector<FlatType> *list,
             Type *type,
             const std::optional<FlatType> &parent,
             const std::string &name,
             bool invert,
             bool sep = true);
 
std::vector<FlatType> Flatten(Type *type);
 
bool ContainsFlatType(const std::vector<FlatType> &flat_types_list, const Type *type);
 
int64_t IndexOfFlatType(const std::vector<FlatType> &flat_types_list, const Type *type);
 
std::string ToString(std::vector<FlatType> flat_type_list);
 
template<typename T>
class MappingMatrix {
 public:
  MappingMatrix(int64_t height, int64_t width) : height_(height), width_(width) {
    elements_ = std::vector<T>(height_ * width_, static_cast<T>(0));
  }
 
  static MappingMatrix Identity(int64_t dim) {
    MappingMatrix ret(dim, dim);
    for (int64_t i = 0; i < dim; i++) {
      ret(i, i) = 1;
    }
  }
 
  int64_t height() { return height_; }
  int64_t width() { return width_; }
 
  T &get(int64_t y, int64_t x) {
    if (y >= height_ || x >= width_) {
      CERATA_LOG(FATAL, "Indices exceed matrix dimensions.");
    }
    return elements_[width_ * y + x];
  }
 
  [[nodiscard]] const T &get(int64_t y, int64_t x) const {
    if (y >= height_ || x >= width_) {
      CERATA_LOG(FATAL, "Indices exceed matrix dimensions.");
    }
    return elements_[width_ * y + x];
  }
 
  T &operator()(int64_t y, int64_t x) {
    return get(y, x);
  }
 
  const T &operator()(int64_t y, int64_t x) const {
    return get(y, x);
  }
 
  [[nodiscard]] bool IsIdentity() const {
    if (width_ == height_) {
      for (size_t d = 0; d < width_; d++) {
        if (get(d, d) != 1) {
          return false;
        }
      }
    }
    return true;
  }
 
  [[nodiscard]] T MaxOfColumn(int64_t x) const {
    T max = 0;
    for (int64_t y = 0; y < height_; y++) {
      if (get(y, x) > max) {
        max = get(y, x);
      }
    }
    return max;
  }
 
  [[nodiscard]] T MaxOfRow(int64_t y) const {
    T max = 0;
    for (int64_t x = 0; x < width_; x++) {
      if (get(y, x) > max) {
        max = get(y, x);
      }
    }
    return max;
  }
 
  std::vector<std::pair<int64_t, T>> mapping_column(int64_t x) {
    std::vector<std::pair<int64_t, T>> ret;
    for (int64_t y = 0; y < height_; y++) {
      auto val = get(y, x);
      if (val > 0) {
        ret.emplace_back(y, val);
      }
    }
    std::sort(ret.begin(), ret.end(), [](const auto &x, const auto &y) -> bool {
      return x.second < y.second;
    });
    return ret;
  }
 
  std::vector<std::pair<int64_t, T>> mapping_row(int64_t y) {
    using pair = std::pair<int64_t, T>;
    std::vector<pair> ret;
    for (int64_t x = 0; x < width_; x++) {
      auto val = get(y, x);
      if (val > 0) {
        ret.emplace_back(x, val);
      }
    }
    std::sort(ret.begin(), ret.end(), [](const auto &x, const auto &y) -> bool {
      return x.second < y.second;
    });
    return ret;
  }
 
  MappingMatrix &SetNext(int64_t y, int64_t x) {
    get(y, x) = std::max(MaxOfColumn(x), MaxOfRow(y)) + 1;
    return *this;
  }
 
  [[nodiscard]] MappingMatrix Transpose() const {
    MappingMatrix ret(width_, height_);
    for (int64_t y = 0; y < height_; y++) {
      for (int64_t x = 0; x < width_; x++) {
        ret(x, y) = get(y, x);
      }
    }
    return ret;
  }
 
  [[nodiscard]] MappingMatrix Empty() const {
    MappingMatrix ret(height_, width_);
    return ret;
  }
 
  std::string ToString() {
    std::stringstream ret;
    for (int64_t y = 0; y < height_; y++) {
      for (int64_t x = 0; x < width_; x++) {
        ret << std::setw(3) << std::right << std::to_string(get(y, x)) << " ";
      }
      ret << "\n";
    }
    return ret.str();
  }
 
 private:
  std::vector<T> elements_;
  int64_t height_;
  int64_t width_;
};
 
struct MappingPair {
  using OptionalNode = std::optional<std::shared_ptr<Node>>;  
  using index = int64_t;  
  using offset = int64_t;  
  using IOF = std::tuple<index, offset, FlatType>;
  std::vector<IOF> a;
  std::vector<IOF> b;
  [[nodiscard]] int64_t num_a() const { return a.size(); }
  [[nodiscard]] int64_t num_b() const { return b.size(); }
  [[nodiscard]] index index_a(int64_t i) const { return std::get<0>(a[i]); }
  [[nodiscard]] index index_b(int64_t i) const { return std::get<0>(b[i]); }
  [[nodiscard]] offset offset_a(int64_t i) const { return std::get<1>(a[i]); }
  [[nodiscard]] offset offset_b(int64_t i) const { return std::get<1>(b[i]); }
  [[nodiscard]] FlatType flat_type_a(int64_t i) const { return std::get<2>(a[i]); }
  [[nodiscard]] FlatType flat_type_b(int64_t i) const { return std::get<2>(b[i]); }
 
  [[nodiscard]] std::shared_ptr<Node> width_a(const OptionalNode &no_width_increment = {}) const;
 
  [[nodiscard]] std::shared_ptr<Node> width_b(const OptionalNode &no_width_increment = {}) const;
 
  [[nodiscard]] std::string ToString() const;
};
 
class TypeMapper : public Named {
 public:
  TypeMapper(Type *a, Type *b);
  static std::shared_ptr<TypeMapper> Make(Type *a);
  static std::shared_ptr<TypeMapper> MakeImplicit(Type *a, Type *b);
  static std::shared_ptr<TypeMapper> Make(Type *a, Type *b);
  static std::shared_ptr<TypeMapper> Make(const std::shared_ptr<Type> &a, const std::shared_ptr<Type> &b);
 
  TypeMapper &Add(int64_t a, int64_t b);
  MappingMatrix<int64_t> map_matrix();
  void SetMappingMatrix(MappingMatrix<int64_t> map_matrix);
 
  std::vector<FlatType> flat_a() const;
  std::vector<FlatType> flat_b() const;
  Type *a() const { return a_; }
  Type *b() const { return b_; }
 
  bool CanConvert(const Type *a, const Type *b) const;
 
  std::shared_ptr<TypeMapper> Inverse() const;
 
  std::vector<MappingPair> GetUniqueMappingPairs();
 
  std::string ToString() const;
 
  std::unordered_map<std::string, std::string> meta;
 
 protected:
  std::vector<FlatType> fa_;
  std::vector<FlatType> fb_;
  Type *a_;
  Type *b_;
  MappingMatrix<int64_t> matrix_;
};
 
}  // namespace cerata