text:
/*
 * Copyright (c) Meta Platforms, Inc. and affiliates.
 *
 * 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.
 */

#include <thrift/compiler/parse/parsing_driver.h>

#include <errno.h>
#include <stdlib.h>
#include <cmath>
#include <cstdarg>
#include <limits>
#include <memory>

#include <boost/filesystem.hpp>

/**
 * Note macro expansion because this is different between OSS and internal
 * build, sigh.
 */
#include THRIFTY_HH

namespace apache {
namespace thrift {
namespace compiler {

namespace {

class parsing_terminator : public std::runtime_error {
 public:
  parsing_terminator()
      : std::runtime_error(
            "Internal exception used to terminate the parsing process.") {}
};

// We don't use std::isspace since it's locale-dependent
bool is_white_space(char c) {
  return c == ' ' || c == '\t' || c == '\r' || c == '\n';
}

// If the given defintion defines a new scope for field ids.
bool is_field_scope(DefType type) {
  switch (type) {
    case DefType::Function:
    case DefType::Struct:
    case DefType::Union:
    case DefType::Exception:
      return true;
    default:
      return false;
  }
}

} // namespace

parsing_driver::parsing_driver(
    diagnostic_context& ctx, std::string path, parsing_params parse_params)
    : params(std::move(parse_params)),
      doctext(boost::none),
      doctext_lineno(0),
      mode(parsing_mode::INCLUDES),
      ctx_(ctx) {
  auto root_program = std::make_unique<t_program>(path);
  ctx_.start_program(program = root_program.get());
  program_bundle = std::make_unique<t_program_bundle>(std::move(root_program));

  scope_cache = program->scope();
}

/**
 * The default destructor needs to be explicitly defined in the .cc file since
 * it invokes the destructor of parse_ (of type unique_ptr<yy::parser>). It
 * cannot go in the header file since yy::parser is only forward-declared there.
 */
parsing_driver::~parsing_driver() = default;

std::unique_ptr<t_program_bundle> parsing_driver::parse() {
  std::unique_ptr<t_program_bundle> result{};
  try {
    scanner = std::make_unique<yy_scanner>();
  } catch (std::system_error const&) {
    return result;
  }

  parser_ = std::make_unique<yy::parser>(
      *this, scanner->get_scanner(), &yylval_, &yylloc_);

  try {
    parse_file();
    result = std::move(program_bundle);
  } catch (const parsing_terminator&) {
    // No need to do anything here. The purpose of the exception is simply to
    // end the parsing process by unwinding to here.
  }
  return result;
}

void parsing_driver::parse_file() {
  // Get scope file path
  const std::string& path = program->path();

  // Skip on already parsed files
  if (already_parsed_paths_.count(path)) {
    return;
  } else {
    already_parsed_paths_.insert(path);
  }

  try {
    scanner->start(path);
    scanner->set_lineno(1);
    reset_locations();
  } catch (std::runtime_error const& ex) {
    failure(ex.what());
  }

  // Create new scope and scan for includes
  verbose([&](auto& o) { o << "Scanning " << path << " for includes\n"; });
  mode = parsing_mode::INCLUDES;
  try {
    if (parser_->parse() != 0) {
      failure("Parser error during include pass.");
    }
  } catch (const std::string& x) {
    failure(x);
  }

  // Recursively parse all the include programs
  const auto& includes = program->get_included_programs();
  // Always enable allow_neg_field_keys when parsing included files.
  // This way if a thrift file has negative keys, --allow-neg-keys doesn't have
  // to be used by everyone that includes it.
  auto old_params = params;
  auto old_program = program;
  for (auto included_program : includes) {
    circular_deps_.insert(path);

    // Fail on circular dependencies
    if (circular_deps_.count(included_program->path())) {
      failure([&](auto& o) {
        o << "Circular dependency found: file `" << included_program->path()
          << "` is already parsed.";
      });
    }

    // This must be after the previous circular include check, since the emitted
    // error message above is supposed to reference the parent file name.
    params.allow_neg_field_keys = true;
    ctx_.start_program(program = included_program);
    parse_file();
    ctx_.end_program(program);

    size_t num_removed = circular_deps_.erase(path);
    (void)num_removed;
    assert(num_removed == 1);
  }
  params = old_params;
  program = old_program;

  // Parse the program file
  try {
    scanner->start(path);
    scanner->set_lineno(1);
    reset_locations();
  } catch (std::runtime_error const& ex) {
    failure(ex.what());
  }

  mode = parsing_mode::PROGRAM;
  verbose([&](auto& o) { o << "Parsing " << path << " for types\n"; });
  try {
    if (parser_->parse() != 0) {
      failure("Parser error during types pass.");
    }
  } catch (const std::string& x) {
    failure(x);
  }

  for (auto td : program->placeholder_typedefs()) {
    if (!td->resolve()) {
      failure(
          [&](auto& o) { o << "Type `" << td->name() << "` not defined."; });
    }
  }
}

[[noreturn]] void parsing_driver::end_parsing() {
  throw parsing_terminator{};
}

// TODO: This doesn't really need to be a member function. Move it somewhere
// else (e.g. `util.{h|cc}`) once everything gets consolidated into `parse/`.
std::string parsing_driver::directory_name(const std::string& filename) {
  boost::filesystem::path fullpath = filename;
  auto parent_path = fullpath.parent_path();
  auto result = parent_path.string();
  // No parent dir, just use the current directory
  if (result.empty()) {
    return ".";
  }
  return result;
}

std::string parsing_driver::find_include_file(const std::string& filename) {
  // Absolute path? Just try that
  boost::filesystem::path path{filename};
  if (path.has_root_directory()) {
    try {
      return boost::filesystem::canonical(path).string();
    } catch (const boost::filesystem::filesystem_error& e) {
      failure([&](auto& o) {
        o << "Could not find file: " << filename << ". Error: " << e.what();
      });
    }
  }

  // relative path, start searching
  // new search path with current dir global
  std::vector<std::string> sp = params.incl_searchpath;
  sp.insert(sp.begin(), directory_name(program->path()));
  // iterate through paths
  std::vector<std::string>::iterator it;
  for (it = sp.begin(); it != sp.end(); it++) {
    boost::filesystem::path sfilename = filename;
    if ((*it) != "." && (*it) != "") {
      sfilename = boost::filesystem::path(*(it)) / filename;
    }
    if (boost::filesystem::exists(sfilename)) {
      return sfilename.string();
    } else {
      debug([&](auto& o) { o << "Could not find: " << filename << "."; });
    }
  }
  // File was not found
  failure([&](auto& o) { o << "Could not find include file " << filename; });
}

void parsing_driver::validate_not_ambiguous_enum(const std::string& name) {
  if (scope_cache->is_ambiguous_enum_value(name)) {
    std::string possible_enums =
        scope_cache->get_fully_qualified_enum_value_names(name).c_str();
    std::string msg = "The ambiguous enum `" + name +
        "` is defined in more than one place. " +
        "Please refer to this enum using ENUM_NAME.ENUM_VALUE.";
    if (!possible_enums.empty()) {
      msg += (" Possible options: " + possible_enums);
    }
    warning(msg);
  }
}
void parsing_driver::clear_doctext() {
  if (doctext && mode == parsing_mode::PROGRAM) {
    warning_strict([&](auto& o) {
      o << "Uncaptured doctext at on line " << doctext_lineno << ".";
    });
  }

  doctext = boost::none;
}

t_doc parsing_driver::capture_doctext() {
  if (mode != parsing_mode::PROGRAM) {
    return boost::none;
  }
  return std::exchange(doctext, boost::none);
}

t_doc parsing_driver::clean_up_doctext(std::string docstring) {
  // Convert to C++ string, and remove Windows's carriage returns.
  docstring.erase(
      remove(docstring.begin(), docstring.end(), '\r'), docstring.end());

  // Separate into lines.
  std::vector<std::string> lines;
  std::string::size_type pos = std::string::npos;
  std::string::size_type last;
  while (true) {
    last = (pos == std::string::npos) ? 0 : pos + 1;
    pos = docstring.find('\n', last);
    if (pos == std::string::npos) {
      // First bit of cleaning.  If the last line is only whitespace, drop it.
      std::string::size_type nonwhite =
          docstring.find_first_not_of(" \t", last);
      if (nonwhite != std::string::npos) {
        lines.push_back(docstring.substr(last));
      }
      break;
    }
    lines.push_back(docstring.substr(last, pos - last));
  }

  // A very profound docstring.
  if (lines.empty()) {
    return boost::none;
  }

  // Clear leading whitespace from the first line.
  pos = lines.front().find_first_not_of(" \t");
  lines.front().erase(0, pos);

  // If every nonblank line after the first has the same number of spaces/tabs,
  // then a comment prefix, remove them.
  enum Prefix {
    None = 0,
    Star = 1, // length of '*'
    Slashes = 3, // length of '///'
  };
  Prefix found_prefix = None;
  std::string::size_type prefix_len = 0;
  std::vector<std::string>::iterator l_iter;

  // Start searching for prefixes from second line, since lexer already removed
  // initial prefix/suffix.
  for (l_iter = lines.begin() + 1; l_iter != lines.end(); ++l_iter) {
    if (l_iter->empty()) {
      continue;
    }

    pos = l_iter->find_first_not_of(" \t");
    if (found_prefix == None) {
      if (pos != std::string::npos) {
        if (l_iter->at(pos) == '*') {
          found_prefix = Star;
          prefix_len = pos;
        } else if (l_iter->compare(pos, 3, "///") == 0) {
          found_prefix = Slashes;
          prefix_len = pos;
        } else {
          found_prefix = None;
          break;
        }
      } else {
        // Whitespace-only line.  Truncate it.
        l_iter->clear();
      }
    } else if (
        l_iter->size() > pos && pos == prefix_len &&
        ((found_prefix == Star && l_iter->at(pos) == '*') ||
         (found_prefix == Slashes && l_iter->compare(pos, 3, "///") == 0))) {
      // Business as usual
    } else if (pos == std::string::npos) {
      // Whitespace-only line.  Let's truncate it for them.
      l_iter->clear();
    } else {
      // The pattern has been broken.
      found_prefix = None;
      break;
    }
  }

  // If our prefix survived, delete it from every line.
  if (found_prefix != None) {
    // Get the prefix too.
    prefix_len += found_prefix;
    for (l_iter = lines.begin() + 1; l_iter != lines.end(); ++l_iter) {
      l_iter->erase(0, prefix_len);
    }
  }

  // Now delete the minimum amount of leading whitespace from each line.
  prefix_len = std::string::npos;
  for (l_iter = lines.begin() + 1; l_iter != lines.end(); ++l_iter) {
    if (l_iter->empty()) {
      continue;
    }
    pos = l_iter->find_first_not_of(" \t");
    if (pos != std::string::npos &&
        (prefix_len == std::string::npos || pos < prefix_len)) {
      prefix_len = pos;
    }
  }

  // If our whitespace prefix survived, delete it from every line.
  if (prefix_len != std::string::npos) {
    for (l_iter = lines.begin() + 1; l_iter != lines.end(); ++l_iter) {
      l_iter->erase(0, prefix_len);
    }
  }

  // Remove trailing whitespace from every line.
  for (l_iter = lines.begin(); l_iter != lines.end(); ++l_iter) {
    pos = l_iter->find_last_not_of(" \t");
    if (pos != std::string::npos && pos != l_iter->length() - 1) {
      l_iter->erase(pos + 1);
    }
  }

  // If the first line is empty, remove it.
  // Don't do this earlier because a lot of steps skip the first line.
  if (lines.front().empty()) {
    lines.erase(lines.begin());
  }

  // Now rejoin the lines and copy them back into doctext.
  docstring.clear();
  for (l_iter = lines.begin(); l_iter != lines.end(); ++l_iter) {
    docstring += *l_iter;
    docstring += '\n';
  }

  return docstring;
}

bool parsing_driver::require_experimental_feature(const char* feature) {
  assert(feature != std::string("all"));
  if (params.allow_experimental_features.count("all") ||
      params.allow_experimental_features.count(feature)) {
    warning_strict([&](auto& o) {
      o << "'" << feature << "' is an experimental feature.";
    });
    return true;
  }
  failure(
      [&](auto& o) { o << "'" << feature << "' is an experimental feature."; });
  return false;
}

void parsing_driver::set_annotations(
    t_node* node, std::unique_ptr<t_annotations> annotations) {
  if (annotations != nullptr) {
    node->reset_annotations(annotations->strings);
  }
}

void parsing_driver::set_attributes(
    t_named* node,
    std::unique_ptr<t_def_attrs> attrs,
    std::unique_ptr<t_annotations> annotations) {
  if (attrs != nullptr) {
    if (attrs->doc) {
      node->set_doc(std::move(*attrs->doc));
    }
    if (attrs->struct_annotations != nullptr) {
      for (auto& an : *attrs->struct_annotations) {
        node->add_structured_annotation(std::move(an));
      }
    }
  }
  set_annotations(node, std::move(annotations));
}

source_range parsing_driver::get_source_range(const YYLTYPE& loc) {
  return source_range(
      *program, loc.begin.line, loc.begin.column, loc.end.line, loc.end.column);
}

void parsing_driver::reset_locations() {
  yylloc_.begin.line = 1;
  yylloc_.begin.column = 1;
  yylloc_.end.line = 1;
  yylloc_.end.column = 1;
  yylval_ = 0;
}

void parsing_driver::compute_location(
    YYLTYPE& yylloc, YYSTYPE& yylval, const char* text) {
  /* Only computing locations during second pass. */
  if (mode != parsing_mode::PROGRAM) {
    return;
  }

  int i = 0;

  // Updating current begin to previous end.
  yylloc.begin = yylloc.end;

  // Getting rid of useless whitespaces on begin position.
  for (; is_white_space(text[i]); i++) {
    yylval++;
    if (text[i] == '\n') {
      yylloc.begin.line++;
      yylloc.begin.column = 1;
      program->add_line_offset(yylval);
    } else {
      yylloc.begin.column++;
    }
  }

  // Avoid scanning whitespaces twice.
  yylloc.end = yylloc.begin;

  // Updating current end position.
  for (; text[i] != '\0'; i++) {
    yylval++;
    if (text[i] == '\n') {
      yylloc.end.line++;
      yylloc.end.column = 1;
      program->add_line_offset(yylval);
    } else {
      yylloc.end.column++;
    }
  }
}

std::unique_ptr<t_const> parsing_driver::new_struct_annotation(
    std::unique_ptr<t_const_value> const_struct) {
  auto ttype = const_struct->ttype().value(); // Copy the t_type_ref.
  auto result = std::make_unique<t_const>(
      program, std::move(ttype), "", std::move(const_struct));
  result->set_lineno(scanner->get_lineno());
  return result;
}

std::unique_ptr<t_throws> parsing_driver::new_throws(
    std::unique_ptr<t_field_list> exceptions) {
  assert(exceptions != nullptr);
  auto result = std::make_unique<t_throws>();
  append_fields(*result, std::move(*exceptions));
  return result;
}

void parsing_driver::append_fields(
    t_structured& tstruct, t_field_list&& fields) {
  for (auto& field : fields) {
    if (!tstruct.try_append_field(std::move(field))) {
      // Since we process root_program twice, we need to check parsing mode to
      // avoid double reporting
      if (mode == parsing_mode::PROGRAM ||
          program != program_bundle->root_program()) {
        ctx_.failure(*field, [&](auto& o) {
          o << "Field identifier " << field->get_key() << " for \""
            << field->get_name() << "\" has already been used.";
        });
      }
    }
  }
}

t_type_ref parsing_driver::new_type_ref(
    const t_type& type, std::unique_ptr<t_annotations> annotations) {
  if (annotations == nullptr) {
    return type;
  }

  // Make a copy of the node to hold the annotations.
  // TODO(afuller): Remove the need for copying the underlying type by making
  // t_type_ref annotatable directly.
  if (const auto* tbase_type = dynamic_cast<const t_base_type*>(&type)) {
    // base types can be copy constructed.
    auto node = std::make_unique<t_base_type>(*tbase_type);
    set_annotations(node.get(), std::move(annotations));
    t_type_ref result(*node);
    if (mode == parsing_mode::INCLUDES) {
      delete_at_the_end(node.release());
    } else {
      program->add_unnamed_type(std::move(node));
    }
    return result;
  }

  // Containers always use a new type, so should never show up here.
  assert(!type.is_container());
  // For all other types, we can just create a dummy typedef node with
  // the same name.
  // NOTE(afuller): This is not a safe assumption as it breaks all
  // dynamic casts and t_type::is_* calls.
  return *add_unnamed_typedef(
      std::make_unique<t_typedef>(
          const_cast<t_program*>(type.program()), type.get_name(), type),
      std::move(annotations));
}

t_type_ref parsing_driver::new_type_ref(
    std::unique_ptr<t_templated_type> node,
    std::unique_ptr<t_annotations> annotations) {
  assert(node != nullptr);
  const t_type* type = node.get();
  set_annotations(node.get(), std::move(annotations));
  if (mode == parsing_mode::INCLUDES) {
    delete_at_the_end(node.release());
  } else {
    program->add_type_instantiation(std::move(node));
  }
  return *type;
}

t_type_ref parsing_driver::new_type_ref(
    std::string name,
    std::unique_ptr<t_annotations> annotations,
    bool is_const) {
  if (mode == parsing_mode::INCLUDES) {
    // Ignore identifier-based type references in include mode
    return {};
  }

  // Try to resolve the type.
  const t_type* type = scope_cache->find_type(name);
  if (type == nullptr) {
    type = scope_cache->find_type(program->name() + "." + name);
  }
  if (type == nullptr) {
    // TODO(afuller): Remove this special case for const, which requires a
    // specific declaration order.
    if (is_const) {
      failure([&](auto& o) {
        o << "The type '" << name << "' is not defined yet. Types must be "
          << "defined before the usage in constant values.";
      });
    }
    // TODO(afuller): Why are interactions special? They should just be another
    // declared type.
    type = scope_cache->find_interaction(name);
    if (type == nullptr) {
      type = scope_cache->find_interaction(program->name() + "." + name);
    }
  }

  if (type != nullptr) {
    // We found the type!
    return new_type_ref(*type, std::move(annotations));
  }

  /*
   Either this type isn't yet declared, or it's never
   declared. Either way allow it and we'll figure it out
   during generation.
  */
  // NOTE(afuller): This assumes that, since the type was referenced by name, it
  // is safe to create a dummy typedef to use as a proxy for the original type.
  // However, this actually breaks dynamic casts and t_type::is_* calls.
  // TODO(afuller): Resolve *all* types in a second pass.
  return t_type_ref(*add_placeholder_typedef(
      std::make_unique<t_placeholder_typedef>(
          program, std::move(name), scope_cache),
      std::move(annotations)));
}

void parsing_driver::start_def(DefType type) {
  def_stack_.push({type, scanner->get_lineno()});
  if (is_field_scope(type)) {
    next_id_stack_.push(-1);
  }
}

void parsing_driver::finish_def(
    t_named* node,
    const YYLTYPE& loc,
    std::unique_ptr<t_def_attrs> attrs,
    std::unique_ptr<t_annotations> annotations) {
  node->set_lineno(def_stack_.top().lineno);
  set_attributes(node, std::move(attrs), std::move(annotations));
  node->set_src_range(get_source_range(loc));
  if (is_field_scope(def_stack_.top().type)) {
    next_id_stack_.pop();
  }
  def_stack_.pop();
}

void parsing_driver::finish_def(
    t_structured* node,
    const YYLTYPE& loc,
    std::unique_ptr<t_def_attrs> attrs,
    std::unique_ptr<t_field_list> fields,
    std::unique_ptr<t_annotations> annotations) {
  append_fields(*node, std::move(*fields));
  finish_def(node, loc, std::move(attrs), std::move(annotations));
}

void parsing_driver::finish_def(
    t_interface* node,
    const YYLTYPE& loc,
    std::unique_ptr<t_def_attrs> attrs,
    std::unique_ptr<t_function_list> functions,
    std::unique_ptr<t_annotations> annotations) {
  if (functions != nullptr) {
    node->set_functions(std::move(*functions));
  }
  finish_def(node, loc, std::move(attrs), std::move(annotations));
}

t_ref<t_const> parsing_driver::add_def(std::unique_ptr<t_const> node) {
  t_ref<t_const> result(node.get());
  if (should_add_node(node)) {
    scope_cache->add_constant(scoped_name(*node), node.get());
    program->add_const(std::move(node));
  }
  return result;
}
t_ref<t_interaction> parsing_driver::add_def(
    std::unique_ptr<t_interaction> node) {
  t_ref<t_interaction> result(node.get());
  if (should_add_node(node)) {
    scope_cache->add_interaction(scoped_name(*node), node.get());
    program->add_interaction(std::move(node));
  }
  return result;
}

t_ref<t_service> parsing_driver::add_def(std::unique_ptr<t_service> node) {
  t_ref<t_service> result(node.get());
  assert(!node->is_interaction());
  if (should_add_node(node)) {
    scope_cache->add_service(scoped_name(*node), node.get());
    program->add_service(std::move(node));
  }
  return result;
}

t_ref<t_typedef> parsing_driver::add_def(std::unique_ptr<t_typedef> node) {
  t_ref<t_typedef> result(node.get());
  if (should_add_type(node)) {
    program->add_typedef(std::move(node));
  }
  return result;
}

t_ref<t_struct> parsing_driver::add_def(std::unique_ptr<t_struct> node) {
  t_ref<t_struct> result(node.get());
  if (should_add_type(node)) {
    program->add_struct(std::move(node));
  }
  return result;
}

t_ref<t_union> parsing_driver::add_def(std::unique_ptr<t_union> node) {
  t_ref<t_union> result(node.get());
  if (should_add_type(node)) {
    program->add_struct(std::move(node));
  }
  return result;
}

t_ref<t_exception> parsing_driver::add_def(std::unique_ptr<t_exception> node) {
  t_ref<t_exception> result(node.get());
  if (should_add_type(node)) {
    program->add_xception(std::move(node));
  }
  return result;
}

t_ref<t_enum> parsing_driver::add_def(std::unique_ptr<t_enum> node) {
  t_ref<t_enum> result(node.get());

  if (should_add_type(node)) {
    // Register enum value names in scope.
    for (const auto& value : node->consts()) {
      // TODO(afuller): Remove ability to access unscoped enum values.
      scope_cache->add_constant(scoped_name(value), &value);
      scope_cache->add_constant(scoped_name(*node, value), &value);
    }
    program->add_enum(std::move(node));
  }
  return result;
}

void parsing_driver::add_include(std::string name) {
  if (mode != parsing_mode::INCLUDES) {
    return;
  }

  std::string path = find_include_file(name);
  assert(!path.empty()); // Should have throw an exception if not found.

  if (program_cache.find(path) == program_cache.end()) {
    auto included_program =
        program->add_include(path, name, scanner->get_lineno());
    program_cache[path] = included_program.get();
    program_bundle->add_program(std::move(included_program));
  } else {
    auto include = std::make_unique<t_include>(program_cache[path]);
    include->set_lineno(scanner->get_lineno());
    program->add_include(std::move(include));
  }
}

const t_type* parsing_driver::add_unnamed_typedef(
    std::unique_ptr<t_typedef> node,
    std::unique_ptr<t_annotations> annotations) {
  const t_type* result(node.get());
  set_annotations(node.get(), std::move(annotations));
  program->add_unnamed_typedef(std::move(node));
  return result;
}

const t_type* parsing_driver::add_placeholder_typedef(
    std::unique_ptr<t_placeholder_typedef> node,
    std::unique_ptr<t_annotations> annotations) {
  const t_type* result(node.get());
  set_annotations(node.get(), std::move(annotations));
  program->add_placeholder_typedef(std::move(node));
  return result;
}

t_field_id parsing_driver::to_field_id(int64_t int_const) {
  using limits = std::numeric_limits<t_field_id>;
  if (int_const < limits::min() || int_const > limits::max()) {
    // Not representable as a field id.
    failure([&](auto& o) {
      o << "Integer constant (" << int_const
        << ") outside the range of field ids ([" << limits::min() << ", "
        << limits::max() << "]).";
    });
  }
  return int_const;
}

t_field_id parsing_driver::allocate_field_id(const std::string& name) {
  assert(!next_id_stack_.empty());
  if (params.strict >= 192) {
    failure("Implicit field keys are deprecated and not allowed with -strict");
  }
  if (next_id_stack_.top() < t_field::min_id) {
    failure(
        "Cannot allocate an id for `" + name +
        "`. Automatic field ids are exhausted.");
  }
  return next_id_stack_.top()--;
}

void parsing_driver::reserve_field_id(t_field_id id) {
  assert(!next_id_stack_.empty());
  if (id < 0) {
    /*
     * Update next field id to be one less than the value.
     * The FieldList parsing will catch any duplicate id values.
     */
    next_id_stack_.top() = id - 1;
  }
}

uint64_t parsing_driver::parse_integer(const char* text, int offset, int base) {
  errno = 0;
  uint64_t val = strtoull(text + offset, nullptr, base);
  if (errno == ERANGE) {
    failure([&](auto& o) { o << "This integer is too big: " << text << "\n"; });
  }
  return val;
}

int64_t parsing_driver::to_int(uint64_t val, bool negative) {
  constexpr uint64_t i64max = std::numeric_limits<int64_t>::max();
  if (negative) {
    if (val > i64max + 1) { // Can store one more negative number.
      failure(
          [&](auto& o) { o << "This integer is too small: -" << val << "\n"; });
    }
    return -val;
  }
  if (val > i64max) {
    failure([&](auto& o) { o << "This integer is too big: " << val << "\n"; });
  }
  return val;
}

double parsing_driver::parse_double(const char* text) {
  errno = 0;
  double val = strtod(text, nullptr);
  if (errno == ERANGE) {
    if (val == 0) {
      failure([&](auto& o) {
        o << "This number is too infinitesimal: " << text << "\n";
      });
    } else if (val == HUGE_VAL) {
      failure(
          [&](auto& o) { o << "This number is too big: " << text << "\n"; });
    } else if (val == -HUGE_VAL) {
      failure(
          [&](auto& o) { o << "This number is too small: " << text << "\n"; });
    }
    // Allow subnormals.
  }
  return val;
}

void parsing_driver::parse_doctext(const char* text, int lineno) {
  if (mode != apache::thrift::compiler::parsing_mode::PROGRAM) {
    return;
  }

  // Deal with prefix/suffix.
  std::string str{text};
  if (str.compare(0, 3, "/**") == 0) {
    str = str.substr(3, str.length() - 3 - 2);
  } else if (str.compare(0, 3, "///") == 0) {
    str = str.substr(3, str.length() - 3);
  }

  clear_doctext();
  doctext = clean_up_doctext(str);
  doctext_lineno = lineno;
}

const t_service* parsing_driver::find_service(const std::string& name) {
  if (mode != parsing_mode::PROGRAM) {
    return nullptr;
  }
  if (auto* result = scope_cache->find_service(name)) {
    return result;
  }
  if (auto* result = scope_cache->find_service(scoped_name(name))) {
    return result;
  }
  failure([&](auto& o) {
    o << "Service \"" << name << "\" has not been defined.";
  });
}

const t_const* parsing_driver::find_const(const std::string& name) {
  validate_not_ambiguous_enum(name);
  if (const t_const* constant = scope_cache->find_constant(name)) {
    return constant;
  }
  if (const t_const* constant = scope_cache->find_constant(scoped_name(name))) {
    validate_not_ambiguous_enum(scoped_name(name));
    return constant;
  }
  return nullptr;
}

std::unique_ptr<t_const_value> parsing_driver::copy_const_value(
    const std::string& name) {
  if (const t_const* constant = find_const(name)) {
    // Copy const_value to perform isolated mutations
    auto result = constant->get_value()->clone();
    // We only want to clone the value, while discarding all real type
    // information.
    result->set_ttype(boost::none);
    result->set_is_enum(false);
    result->set_enum(nullptr);
    result->set_enum_value(nullptr);
    return result;
  }

  // TODO(afuller): Make this an error.
  if (mode == parsing_mode::PROGRAM) {
    warning(
        [&](auto& o) { o << "Constant strings should be quoted: " << name; });
  }
  return std::make_unique<t_const_value>(name);
}

} // namespace compiler
} // namespace thrift
} // namespace apache

max_stars_repo_name: maalbash/fbthrift

max_issues_repo_name: maalbash/fbthrift

max_forks_repo_name: maalbash/fbthrift


text:
/*
patterndisp.cpp

Copyright (c) 2014, 2015, 2016 Terumasa Tadano

This file is distributed under the terms of the MIT license.
Please see the file 'LICENCE.txt' in the root directory
or http://opensource.org/licenses/mit-license.php for information.
*/

#include <iostream>
#include <iomanip>
#include "patterndisp.h"
#include "memory.h"
#include "error.h"
#include "system.h"
#include "fcs.h"
#include "cluster.h"
#include "symmetry.h"
#include "constants.h"
#include "mathfunctions.h"
#include "constraint.h"
#include <map>
#include <boost/bimap.hpp>

using namespace ALM_NS;

Displace::Displace()
{
    set_default_variables();
}

Displace::~Displace()
{
    deallocate_variables();
}

void Displace::gen_displacement_pattern(const Cluster *cluster,
                                        const Symmetry *symmetry,
                                        const Fcs *fcs,
                                        const Constraint *constraint,
                                        const System *system,
                                        const int verbosity)
{
    int order;
    const auto maxorder = cluster->get_maxorder();
    std::string preferred_basis;
    std::vector<int> group_tmp;
    ConstraintSparseForm *constsym;
    std::vector<std::vector<double>> const_tmp;

    std::vector<int> pairs;
    std::set<int> *include_set;
    std::set<DispAtomSet> *dispset;

    std::vector<size_t> *nequiv;
    std::vector<FcProperty> *fc_table, *fc_zeros;

    std::vector<ConstraintTypeFix> *const_fix_tmp;
    std::vector<ConstraintTypeRelate> *const_relate_tmp;
    boost::bimap<size_t, size_t> *index_bimap_tmp;
    const auto do_rref = true;

    if (verbosity > 0) {
        std::cout << " DISPLACEMENT PATTERN" << std::endl;
        std::cout << " ====================" << std::endl << std::endl;
    }

    // Decide preferred basis (Cartesian or Lattice)
    auto ncompat_cart = 0;
    auto ncompat_latt = 0;
    for (const auto &it : symmetry->get_SymmData()) {
        if (it.compatible_with_cartesian) ++ncompat_cart;
        if (it.compatible_with_lattice) ++ncompat_latt;
    }
    if (ncompat_cart >= ncompat_latt) {
        preferred_basis = "Cartesian";
    } else {
        preferred_basis = "Lattice";
    }

    // std::cout << "Preferred_basis = " << preferred_basis << std::endl;
    // std::cout << ncompat_cart << " " << ncompat_latt << std::endl;

    allocate(fc_table, maxorder);
    allocate(fc_zeros, maxorder);
    allocate(constsym, maxorder);
    allocate(nequiv, maxorder);
    allocate(const_fix_tmp, maxorder);
    allocate(const_relate_tmp, maxorder);
    allocate(index_bimap_tmp, maxorder);

    for (order = 0; order < maxorder; ++order) {

        fcs->generate_force_constant_table(order,
                                           system->get_supercell().number_of_atoms,
                                           cluster->get_cluster_list(order),
                                           symmetry, preferred_basis,
                                           fc_table[order], nequiv[order],
                                           fc_zeros[order], false);

        fcs->get_constraint_symmetry(system->get_supercell().number_of_atoms,
                                     symmetry,
                                     order,
                                     preferred_basis,
                                     fc_table[order],
                                     nequiv[order].size(),
                                     constraint->get_tolerance_constraint(),
                                     constsym[order], do_rref);

    }

    for (order = 0; order < maxorder; ++order) {
        const_fix_tmp[order].clear();
    }

    constraint->get_mapping_constraint(maxorder,
                                       nequiv,
                                       constsym,
                                       const_fix_tmp,
                                       const_relate_tmp,
                                       index_bimap_tmp);

    if (verbosity > 0) {
        for (order = 0; order < maxorder; ++order) {
            std::cout << "  Number of free" << std::setw(9)
                      << cluster->get_ordername(order) << " FCs : "
                      << index_bimap_tmp[order].size() << std::endl;
        }
        std::cout << std::endl;
    }

    deallocate(constsym);
    deallocate(const_fix_tmp);
    deallocate(const_relate_tmp);
    deallocate(fc_zeros);

    allocate(include_set, maxorder);

    for (order = 0; order < maxorder; ++order) {
        include_set[order].clear();

        for (const auto &it : index_bimap_tmp[order]) {
            include_set[order].insert(it.right);
        }
    }

    deallocate(index_bimap_tmp);

    if (verbosity > 0) {
        std::cout << "  Generating displacement patterns in ";
        std::cout << "Cartesian coordinate... ";
    }

    allocate(dispset, maxorder);

    for (order = 0; order < maxorder; ++order) {

        size_t m = 0;

        for (size_t i = 0; i < nequiv[order].size(); ++i) {

            if (include_set[order].find(i) != include_set[order].end()) {

                group_tmp.clear();

                // Store first order + 1 indexes as a necessary displacement pattern.
                // Here, duplicate entries will be removed.
                // For example, (iij) will be reduced to (ij).
                for (auto j = 0; j < order + 1; ++j) {
                    group_tmp.push_back(fc_table[order][m].elems[j]);
                }
                group_tmp.erase(std::unique(group_tmp.begin(), group_tmp.end()),
                                group_tmp.end());

                // Avoid equivalent entries using set.
                dispset[order].insert(DispAtomSet(group_tmp));

            }

            m += nequiv[order][i];
        }
    }
    deallocate(include_set);
    deallocate(nequiv);
    deallocate(fc_table);

    allocate(pattern_all, maxorder);
    // pattern_all is updated.
    generate_pattern_all(maxorder,
                         system->get_supercell().number_of_atoms,
                         system->get_supercell().lattice_vector,
                         symmetry,
                         dispset, preferred_basis);

    deallocate(dispset);

    if (verbosity > 0) {
        std::cout << " done!" << std::endl;
        std::cout << std::endl;

        for (order = 0; order < maxorder; ++order) {
            std::cout << "  Number of disp. patterns for " << std::setw(9)
                      << cluster->get_ordername(order) << " : "
                      << pattern_all[order].size() << std::endl;
        }
        std::cout << std::endl;
    }
}

void Displace::set_trim_dispsign_for_evenfunc(const bool trim_dispsign_for_evenfunc_in)
{
    trim_dispsign_for_evenfunc = trim_dispsign_for_evenfunc_in;
}

std::string Displace::get_disp_basis() const
{
    return disp_basis;
}

void Displace::set_disp_basis(const std::string disp_basis_in)
{
    disp_basis = disp_basis_in;
}

const std::vector<AtomWithDirection> &Displace::get_pattern_all(const int order) const
{
    return pattern_all[order];
}

void Displace::set_default_variables()
{
    trim_dispsign_for_evenfunc = true;
    disp_basis = "CART";
    pattern_all = nullptr;
}

void Displace::deallocate_variables()
{
    deallocate(pattern_all);
}

void Displace::generate_pattern_all(const int maxorder,
                                    const size_t nat,
                                    const double lavec[3][3],
                                    const Symmetry *symmetry,
                                    const std::set<DispAtomSet> *dispset_in,
                                    const std::string preferred_basis) const
{
    size_t i, j;
    int order;
    double disp_tmp[3];

    std::vector<int> atoms, vec_tmp, nums;
    std::vector<double> directions, directions_copy;
    std::vector<std::vector<int>> *sign_prod, sign_reduced;

    allocate(sign_prod, maxorder);

    for (order = 0; order < maxorder; ++order) {
        vec_tmp.clear();
        generate_signvecs(order + 1, sign_prod[order], vec_tmp);
    }

    for (order = 0; order < maxorder; ++order) {

        pattern_all[order].clear();

        for (auto it = dispset_in[order].begin(); it != dispset_in[order].end(); ++it) {

            atoms.clear();
            directions.clear();
            nums.clear();

            for (i = 0; i < (*it).atomset.size(); ++i) {

                auto atom_tmp = (*it).atomset[i] / 3;

                nums.push_back((*it).atomset[i]);
                atoms.push_back(atom_tmp);

                for (j = 0; j < 3; ++j) {
                    disp_tmp[j] = 0.0;
                }
                disp_tmp[(*it).atomset[i] % 3] = 1.0;

                for (j = 0; j < 3; ++j) directions.push_back(disp_tmp[j]);
            }

            const auto natom_disp = atoms.size();

            if (trim_dispsign_for_evenfunc) {
                find_unique_sign_pairs(natom_disp, nat, symmetry,
                                       sign_prod[natom_disp - 1],
                                       nums, sign_reduced, preferred_basis);
            } else {
                sign_reduced.clear();
                std::copy(sign_prod[natom_disp - 1].begin(),
                          sign_prod[natom_disp - 1].end(),
                          std::back_inserter(sign_reduced));
            }

            directions_copy.clear();
            std::copy(directions.begin(), directions.end(),
                      std::back_inserter(directions_copy));

            for (const auto &it2 : sign_reduced) {
                directions.clear();

                for (i = 0; i < it2.size(); ++i) {
                    const auto sign_double = static_cast<double>(it2[i]);

                    for (j = 0; j < 3; ++j) {
                        disp_tmp[j] = directions_copy[3 * i + j] * sign_double;
                    }
                    if (preferred_basis == "Lattice") {
                        rotvec(disp_tmp, disp_tmp, lavec);
                        double norm = 0.0;
                        for (j = 0; j < 3; ++j) norm += disp_tmp[j] * disp_tmp[j];
                        norm = std::sqrt(norm);
                        for (j = 0; j < 3; ++j) disp_tmp[j] /= norm;
                    }

                    for (j = 0; j < 3; ++j) {
                        directions.push_back(disp_tmp[j]);
                    }
                }
                pattern_all[order].emplace_back(atoms, directions);
            }
        }
    }

    deallocate(sign_prod);
}

void Displace::generate_signvecs(const int N,
                                 std::vector<std::vector<int>> &sign,
                                 std::vector<int> vec) const
{
    // returns the product of signs ('+','-')

    if (N == 0) {
        sign.push_back(vec);
        vec.clear();
    } else {
        std::vector<int> vec_tmp;

        vec_tmp.clear();
        std::copy(vec.begin(), vec.end(), std::back_inserter(vec_tmp));

        vec_tmp.push_back(1);
        generate_signvecs(N - 1, sign, vec_tmp);

        vec_tmp.clear();
        std::copy(vec.begin(), vec.end(), std::back_inserter(vec_tmp));
        vec_tmp.push_back(-1);
        generate_signvecs(N - 1, sign, vec_tmp);
    }
}

void Displace::find_unique_sign_pairs(const int natom_disp_in,
                                      const size_t nat,
                                      const Symmetry *symmetry,
                                      const std::vector<std::vector<int>> sign_in,
                                      const std::vector<int> &pair_in,
                                      std::vector<std::vector<int>> &sign_out,
                                      const std::string preferred_basis) const
{
    size_t isym, i;
    int j, k;
    int mapped_atom;
    int mapped_index;

    bool flag_avail;

    double disp_tmp;
    double **disp, **disp_sym;

    std::vector<int> symnum_vec;
    std::vector<int>::const_iterator loc;
    std::vector<int> atom_tmp, pair_tmp;
    std::vector<std::vector<int>> sign_found;
    std::vector<int> sign_tmp;
    std::vector<int> list_disp_atom;
    std::vector<IndexWithSign> index_for_sort;

    allocate(disp, nat, 3);
    allocate(disp_sym, nat, 3);

    sign_out.clear();
    symnum_vec.clear();
    list_disp_atom.clear();

    for (i = 0; i < pair_in.size(); ++i) {
        list_disp_atom.push_back(pair_in[i] / 3);
    }
    list_disp_atom.erase(std::unique(list_disp_atom.begin(), list_disp_atom.end()),
                         list_disp_atom.end());

    for (i = 0; i < nat; ++i) {
        for (j = 0; j < 3; ++j) {
            disp[i][j] = 0.0;
        }
    }

    for (i = 0; i < pair_in.size(); ++i) {
        disp[pair_in[i] / 3][pair_in[i] % 3] = 1.0;
    }

    const size_t natom_disp = static_cast<size_t>(natom_disp_in);

    // Find symmetry operations which can be used to
    // reduce the number of sign patterns (+, -) of displacements

    for (isym = 0; isym < symmetry->get_nsym(); ++isym) {

        flag_avail = true;
        pair_tmp.clear();

        for (i = 0; i < natom_disp; ++i) {
            if (!flag_avail) break;

            mapped_atom = symmetry->get_map_sym()[pair_in[i] / 3][isym];
            mapped_index = 3 * mapped_atom + pair_in[i] % 3;

            loc = std::find(pair_in.begin(), pair_in.end(), mapped_index);
            if (loc == pair_in.end()) {
                flag_avail = false;
            }

            pair_tmp.push_back(mapped_index);
        }

        if (!flag_avail) continue;

        // The symmetry may be useful only when the pair doesn't change
        // by the symmetry operation.
        std::sort(pair_tmp.begin(), pair_tmp.end());

        if (pair_tmp == pair_in) {

            pair_tmp.clear();

            for (i = 0; i < list_disp_atom.size(); ++i) {
                mapped_atom = symmetry->get_map_sym()[list_disp_atom[i]][isym];

                for (j = 0; j < 3; ++j) {
                    disp_sym[mapped_atom][j] = 0.0;

                    if (preferred_basis == "Cartesian") {
                        for (k = 0; k < 3; ++k) {
                            disp_sym[mapped_atom][j]
                                    += symmetry->get_SymmData()[isym].rotation_cart[j][k] * disp[list_disp_atom[i]][k];
                        }
                    } else if (preferred_basis == "Lattice") {
                        for (k = 0; k < 3; ++k) {
                            disp_sym[mapped_atom][j]
                                    += static_cast<double>(symmetry->get_SymmData()[isym].rotation[j][k])
                                       * disp[list_disp_atom[i]][k];
                        }
                    } else {
                        exit("find_unique_sign_pairs",
                             "Invalid basis. This cannot happen.");
                    }

                    disp_tmp = disp_sym[mapped_atom][j];
                    if (std::abs(disp_tmp) > eps) {
                        pair_tmp.push_back(3 * mapped_atom + j);
                    }
                }
            }

            std::sort(pair_tmp.begin(), pair_tmp.end());

            if (pair_tmp == pair_in) {
                symnum_vec.push_back(isym);
            }
        }
    }

    // Now find unique pairs of displacement directions

    sign_found.clear();

    for (const auto &it : sign_in) {

        // if the sign has already been found before, cycle the loop.
        // else, add the current sign pairs to the return variable.
        if (std::find(sign_found.begin(), sign_found.end(), it) != sign_found.end()) {
            continue;
        }
        sign_out.push_back(it);

        for (i = 0; i < nat; ++i) {
            for (j = 0; j < 3; ++j) {
                disp[i][j] = 0.0;
            }
        }

        for (i = 0; i < natom_disp; ++i) {
            disp[pair_in[i] / 3][pair_in[i] % 3] = static_cast<double>(it[i]);
        }

        for (isym = 0; isym < symnum_vec.size(); ++isym) {

            index_for_sort.clear();

            for (i = 0; i < list_disp_atom.size(); ++i) {
                mapped_atom = symmetry->get_map_sym()[list_disp_atom[i]][symnum_vec[isym]];

                for (j = 0; j < 3; ++j) {
                    disp_sym[mapped_atom][j] = 0.0;
                    if (preferred_basis == "Cartesian") {
                        for (k = 0; k < 3; ++k) {
                            disp_sym[mapped_atom][j]
                                    += symmetry->get_SymmData()[symnum_vec[isym]].rotation_cart[j][k]
                                       * disp[list_disp_atom[i]][k];
                        }
                    } else if (preferred_basis == "Lattice") {
                        for (k = 0; k < 3; ++k) {
                            disp_sym[mapped_atom][j]
                                    += static_cast<double>(symmetry->get_SymmData()[symnum_vec[isym]].rotation[j][k])
                                       * disp[list_disp_atom[i]][k];
                        }
                    } else {
                        exit("find_unique_sign_pairs",
                             "Invalid basis. This cannot happen.");
                    }

                    disp_tmp = disp_sym[mapped_atom][j];

                    if (std::abs(disp_tmp) > eps) {

                        if (disp_tmp < 0.0) {
                            index_for_sort.emplace_back(3 * mapped_atom + j, -1);
                        } else {
                            index_for_sort.emplace_back(3 * mapped_atom + j, 1);
                        }
                    }
                }

            }
            std::sort(index_for_sort.begin(), index_for_sort.end());

            sign_tmp.clear();

            for (i = 0; i < index_for_sort.size(); ++i) {
                sign_tmp.push_back(index_for_sort[i].sign);
            }

            if ((sign_tmp.size() == natom_disp) &&
                (std::find(sign_found.begin(), sign_found.end(), sign_tmp) == sign_found.end())) {
                sign_found.push_back(sign_tmp);
                std::sort(sign_found.begin(), sign_found.end());
            }
        }
    }

    deallocate(disp);
    deallocate(disp_sym);
}

ext: cpp

max_stars_repo_name: jochym/ALM

max_issues_repo_name: jochym/ALM

max_forks_repo_name: jochym/ALM


text:
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <iomanip>
#include "RBF.h"
#include "MLS.h"
#include "HermiteRBF.h"
#include "GeneralizedMLS.h"
#include <boost/mpl/list.hpp>
#include <boost/mpl/for_each.hpp>
#include <boost/mpl/int.hpp>
using namespace std;
using namespace kt84;
namespace mpl = boost::mpl;

// utility for interpolation algorithms |
//--------------------------------------+
template <template <int, int, class, int> class FuncT>
struct FuncUtil;
template <> struct FuncUtil<RBF> {
    static const char* getName() { return "RBF"; }
    template <class Func> static void add_constraint(Func& f, const typename Func::Point& p, const typename Func::Value& v, const typename Func::Gradient& g) { f.add_constraint(p, v); }
    template <class Func> static void preprocess(Func& f) { f.factorize_and_solve(); }
    template <class Func> static typename Func::Gradient gradient(const Func& f, const typename Func::Point& p) { return f.gradient(p); }
    template <class Func>
    static pair<double, double> getMaxError(const Func& f, double epsilon) {
        pair<double, double> result(0, 0);
        for (size_t i = 0; i < f.constraints.size(); ++i) {
            double error_v = (f(f.constraints[i].first) - f.constraints[i].second).norm();
            result.first = max<double>(result.first, error_v);
        }
        return result;
    }
};
template <> struct FuncUtil<MLS> {
    static const char* getName() { return "MLS"; }
    template <class Func> static void add_constraint(Func& f, const typename Func::Point& p, const typename Func::Value& v, const typename Func::Gradient& g) { f.add_constraint(p, v); }
    template <class Func> static void preprocess(Func& f) { }
    template <class Func> static typename Func::Gradient gradient(const Func& f, const typename Func::Point& p) { return typename Func::Gradient::Zero(); }
    template <class Func>
    static pair<double, double> getMaxError(const Func& f, double epsilon) {
        pair<double, double> result(0, 0);
        for (size_t i = 0; i < f.constraints.size(); ++i) {
            double error_v = (f(f.constraints[i].first) - f.constraints[i].second).norm();
            result.first = max<double>(result.first, error_v);
        }
        return result;
    }
};
template <> struct FuncUtil<HermiteRBF> {
    static const char* getName() { return "HRBF"; }
    template <class Func> static void add_constraint(Func& f, const typename Func::Point& p, const typename Func::Value& v, const typename Func::Gradient& g) { f.add_constraint(p, v, g); }
    template <class Func> static void preprocess(Func& f) { f.factorize_and_solve(); }
    template <class Func> static typename Func::Gradient gradient(const Func& f, const typename Func::Point& p) { return f.gradient(p); }
    template <class Func>
    static pair<double, double> getMaxError(const Func& f, double epsilon) {
        pair<double, double> result(0, 0);
        for (size_t i = 0; i < f.constraints.size(); ++i) {
            double error_v = (f(f.constraints[i].get<0>()) - f.constraints[i].get<1>()).norm();
            double error_g = (f.gradient_fd(f.constraints[i].get<0>(), epsilon) - f.constraints[i].get<2>()).norm();
            result.first  = max<double>(result.first , error_v);
            result.second = max<double>(result.second, error_g);
        }
        return result;
    }
};
template <> struct FuncUtil<GeneralizedMLS> {
    static const char* getName() { return "GMLS"; }
    template <class Func> static void add_constraint(Func& f, const typename Func::Point& p, const typename Func::Value& v, const typename Func::Gradient& g) { f.add_constraint(p, v, g); }
    template <class Func> static void preprocess(Func& f) { }
    template <class Func> static typename Func::Gradient gradient(const Func& f, const typename Func::Point& p) { return typename Func::Gradient::Zero(); }
    template <class Func>
    static pair<double, double> getMaxError(const Func& f, double epsilon) {
        pair<double, double> result(0, 0);
        for (size_t i = 0; i < f.constraints.size(); ++i) {
            double error_v = (f(f.constraints[i].get<0>()) - f.constraints[i].get<1>()).norm();
            double error_g = (f.gradient_fd(f.constraints[i].get<0>(), epsilon) - f.constraints[i].get<2>()).norm();
            result.first  = max<double>(result.first , error_v);
            result.second = max<double>(result.second, error_g);
        }
        return result;
    }
};

// utility for RBF kernels |
//-------------------------+
template <class RBFKernel_Core>
struct KernelUtil;
template <> struct KernelUtil<RBFKernel_Gaussian      > { static const char* getName() { return "Gauss"; } static RBFKernel_Gaussian      ::Param getParam() { return RBFKernel_Gaussian      ::Param(10); } };
template <> struct KernelUtil<RBFKernel_SquaredInverse> { static const char* getName() { return "SqInv"; } static RBFKernel_SquaredInverse::Param getParam() { return RBFKernel_SquaredInverse::Param(20); } };
template <> struct KernelUtil<RBFKernel_Wendland      > { static const char* getName() { return "Wendl"; } static RBFKernel_Wendland      ::Param getParam() { return RBFKernel_Wendland      ::Param(1.5); } };
template <> struct KernelUtil<RBFKernel_Cubed         > { static const char* getName() { return "Cubed"; } static RBFKernel_Cubed         ::Param getParam() { return RBFKernel_Cubed         ::Param()   ; } };
template <> struct KernelUtil<RBFKernel_Identity      > { static const char* getName() { return "Ident"; } static RBFKernel_Identity      ::Param getParam() { return RBFKernel_Identity      ::Param()   ; } };
template <> struct KernelUtil<RBFKernel_SquaredLog    > { static const char* getName() { return "SqLog"; } static RBFKernel_SquaredLog    ::Param getParam() { return RBFKernel_SquaredLog    ::Param()   ; } };

// test functions |
//----------------+
template <int Dim, template <int, int, class, int> class FuncT>
struct Tester;

// 1D test
template <template <int, int, class, int> class FuncT>
struct Tester<1, FuncT> {
    template <class RBFKernel_Core, int DegreePolynomial>
    static void go(const typename RBFKernel_Core::Param& param) {
        typedef FuncT<1, 1, RBFKernel_Core, DegreePolynomial> Func;
        typedef Func::Point Point;
        typedef Func::Value Value;
        typedef Func::Gradient Gradient;

        Func f;
        f.kernel.param() = param;

        ifstream fin("input1d.txt");
        if (!fin)
            throw exception("input1d.txt not found!");
        while (!fin.eof()) {
            Point p;
            Value v;
            Gradient g;

            fin >> p[0] >> v[0] >> g[0];
            if (!fin.eof())
                FuncUtil<FuncT>::add_constraint(f, p, v, g);
        }

        FuncUtil<FuncT>::preprocess(f);

        stringstream fname;
        fname << "test1d_" << FuncUtil<FuncT>::getName() << "_" << KernelUtil<RBFKernel_Core>::getName() << "_p" << DegreePolynomial << ".txt";
        ofstream fout(fname.str().c_str());
        // report error first
        pair<double, double> maxError = FuncUtil<FuncT>::getMaxError(f, 0.00001);
        fout << "# max error (value, gradient): (" << maxError.first << ", " << maxError.second << ")" << endl << endl;
        // plot data
        const int N = 100;
        for (double i = 0; i <= N; ++i) {
            Func::Point point = Func::Point::Constant(i / N);
            Func::Value value = f(point);
            Func::Gradient gradient = FuncUtil<FuncT>::gradient(f, point);
            Func::Gradient gradient_fd = f.gradient_fd(point, 0.00001);
            fout
                << setw(12) << point[0] << " "
                << setw(12) << value[0] << " "
                << setw(12) << gradient[0] << " "
                << setw(12) << gradient_fd[0] << " "
                << endl;
        }
    }
    // generate gnuplot commands |
    //---------------------------+
    template <class RBFKernel_Core>
    static void genCmd(int DegreePolynomial) {
        stringstream fname;
        const char* funcName = FuncUtil<FuncT>::getName();
        const char* kernelName = KernelUtil<RBFKernel_Core>::getName();
        fname << "cmd1d_" << funcName << "_" << kernelName << ".txt";
        ofstream fout(fname.str().c_str());
        fout << "plot\\" << endl;
        for (int i = 0; i <= DegreePolynomial; ++i) {
            fout << "    \"test1d_" << funcName << "_" << kernelName << "_p" << i << ".txt\" w linespoints";
            if (i < DegreePolynomial)
                fout << ",\\";
            fout << endl;
        }
        fout << "pause -1" << endl;
        fout.close();
        fname.str("");
        fname << "cmd1d_" << funcName << "_" << kernelName << "_g.txt";
        fout.open(fname.str().c_str());
        fout << "plot\\" << endl;
        for (int i = 0; i <= DegreePolynomial; ++i) {
            fout << "    \"test1d_" << funcName << "_" << kernelName << "_p" << i << ".txt\" u 1:4 w linespoints";
            if (i < DegreePolynomial)
                fout << ",\\";
            fout << endl;
        }
        fout << "pause -1" << endl;
    }
};

// 2D test
template <template <int, int, class, int> class FuncT>
struct Tester<2, FuncT> {
    template <class RBFKernel_Core, int DegreePolynomial>
    static void go(const typename RBFKernel_Core::Param& param) {
        typedef FuncT<2, 1, RBFKernel_Core, DegreePolynomial> Func;
        typedef Func::Point Point;
        typedef Func::Value Value;
        typedef Func::Gradient Gradient;

        Func f;
        f.kernel.param() = param;

        ifstream fin("input2d.txt");
        if (!fin)
            throw exception("input2d.txt not found!");
        while (!fin.eof()) {
            Point p;
            Value v;
            Gradient g;

            fin >> p[0] >> p[1] >> v[0] >> g[0] >> g[1];
            if (!fin.eof())
                FuncUtil<FuncT>::add_constraint(f, p, v, g);
        }

        FuncUtil<FuncT>::preprocess(f);

        stringstream fname;
        fname << "test2d_" << FuncUtil<FuncT>::getName() << "_" << KernelUtil<RBFKernel_Core>::getName() << "_p" << DegreePolynomial << ".txt";
        ofstream fout(fname.str().c_str());
        // report error first
        pair<double, double> maxError = FuncUtil<FuncT>::getMaxError(f, 0.00001);
        fout << "# max error (value, gradient): (" << maxError.first << ", " << maxError.second << ")" << endl << endl;
        // plot data
        const int N = 32;
        for (double j = 0; j <= N; ++j) {
            for (double i = 0; i <= N; ++i) {
                Func::Point point = Func::Point(i / N, j / N);
                Func::Value value = f(point);
                Func::Gradient gradient = FuncUtil<FuncT>::gradient(f, point);
                Func::Gradient gradient_fd = f.gradient_fd(point, 0.00001);
                fout
                    << setw(12) << point[0] << " "
                    << setw(12) << point[1] << " "
                    << setw(12) << value[0] << " "
                    << setw(12) << gradient[0] << " "
                    << setw(12) << gradient[1] << " "
                    << setw(12) << gradient_fd[0] << " "
                    << setw(12) << gradient_fd[1] << " "
                    << endl;
            }
            fout << endl;
        }
    }
    // generate gnuplot commands |
    //---------------------------+
    template <class RBFKernel_Core>
    static void genCmd(int DegreePolynomial) {
        const char* funcName = FuncUtil<FuncT>::getName();
        const char* kernelName = KernelUtil<RBFKernel_Core>::getName();
        for (int i = 0; i <= DegreePolynomial; ++i) {
            // value
            stringstream fname;
            fname << "cmd2d_" << funcName << "_" << kernelName << "_p" << i << ".txt";
            ofstream fout(fname.str().c_str());
            fout << "set pm3d; unset surface; set pm3d hidden3d 100;set view 60, 320\n";
            fout << "splot \"test2d_" << funcName << "_" << kernelName << "_p" << i << ".txt\" u 1:2:3\n";
            fout << "pause -1\n";
            fout.close();
            // gradient
            fname.str("");
            fname << "cmd2d_" << funcName << "_" << kernelName << "_p" << i << "_g.txt";
            fout.open(fname.str().c_str());
            fout << "set pm3d; unset surface; set pm3d hidden3d 100;set view 60, 320;\n";
            fout << "splot \"test2d_" << funcName << "_" << kernelName << "_p" << i << "_g.txt\" u 1:2:6\n";
            fout << "pause -1\n";
        }
    }
};

// list of valid kernels for each algorithm |
//------------------------------------------+
template <template <int, int, class, int> class FuncT>
struct KernelList;
template <> struct KernelList<RBF> {
    typedef mpl::list<
        RBFKernel_Gaussian      ,
        RBFKernel_SquaredInverse,
        RBFKernel_Wendland      ,
        RBFKernel_Cubed         ,
        RBFKernel_Identity      ,
        RBFKernel_SquaredLog
    > Value;
};
template <> struct KernelList<HermiteRBF> {
    typedef mpl::list<
        RBFKernel_Gaussian      ,
        RBFKernel_SquaredInverse,
        RBFKernel_Cubed
    > Value;
};
template <> struct KernelList<MLS> {
    typedef mpl::list<
        RBFKernel_Gaussian      ,
        RBFKernel_SquaredInverse,
        RBFKernel_Wendland
    > Value;
};
template <> struct KernelList<GeneralizedMLS> {
    typedef mpl::list<
        RBFKernel_Gaussian      ,
        RBFKernel_SquaredInverse,
        RBFKernel_Wendland
    > Value;
};

// utility for looping over parameters |
//-------------------------------------+
template <template <int, int, class, int> class FuncT>
struct TestLooper {
    static void go() {
        typedef mpl::list<
            mpl::int_<1>,
            mpl::int_<2>
        > DimList;
        mpl::for_each<DimList>(LoopDim());
    }
    struct LoopDim {
        template <class IntDim>
        void operator()(const IntDim&) const {
            mpl::for_each<KernelList<FuncT>::Value>(LoopKernel<IntDim::value>());
        }
        template <int Dim>
        struct LoopKernel {
            template <class RBFKernel>
            void operator()(const RBFKernel&) const {
                typedef mpl::list<
                    mpl::int_<0>,
                    mpl::int_<1>,
                    mpl::int_<2>
                > DegreeList;
                mpl::for_each<DegreeList>(LoopDegree<RBFKernel>());
                Tester<Dim, FuncT>::genCmd<RBFKernel>(2);
            }
            template <class RBFKernel>
            struct LoopDegree {
                template <class IntDegree>
                void operator()(const IntDegree&) const {
                    Tester<Dim, FuncT>::go<RBFKernel, IntDegree::value>(KernelUtil<RBFKernel>::getParam());
                }
            };
        };
    };
};

int main() {
    TestLooper<RBF           >::go();       // list of templates cannot be handled by Boost.MPL
    TestLooper<MLS           >::go();
    TestLooper<HermiteRBF    >::go();
    TestLooper<GeneralizedMLS>::go();
}

max_stars_repo_name: Pentacode-IAFA/Quad-Remeshing

max_issues_repo_name: Pentacode-IAFA/Quad-Remeshing

max_forks_repo_name: Pentacode-IAFA/Quad-Remeshing


text:
//
// Copyright 2010 Scott McMurray.
// Distributed under the Boost Software License, Version 1.0.
// (See accompanying file LICENSE_1_0.txt or copy at
//  http://www.boost.org/LICENSE_1_0.txt)
//

#ifndef BOOST_HASH_STREAM_PREPROCESSOR_HPP
#define BOOST_HASH_STREAM_PREPROCESSOR_HPP

#include <boost/array.hpp>
#include <boost/hash/pack.hpp>
#include <boost/integer.hpp>
#include <boost/static_assert.hpp>
#include <boost/utility/enable_if.hpp>

#include <iterator>

namespace boost {
namespace hashes {

//
// This will do the usual Merkle-Damgård-style strengthening, padding with
// a 1 bit, then 0 bits as needed, then, if requested, the length.
//
template <typename endian,
          unsigned value_bits_,
          unsigned length_bits_,
          typename block_hash_T>
class stream_preprocessor {
  private:
    typedef block_hash_T block_hash_type;

    static unsigned const word_bits = block_hash_type::word_bits;
    typedef typename block_hash_type::word_type word_type;

    static unsigned const block_bits = block_hash_type::block_bits;
    static unsigned const block_words = block_hash_type::block_words;
    typedef typename block_hash_type::block_type block_type;
  public:
    typedef typename block_hash_type::digest_type digest_type;

    static unsigned const value_bits = value_bits_;
    typedef typename uint_t<value_bits>::least value_type;
    BOOST_STATIC_ASSERT(word_bits % value_bits == 0);
    static unsigned const block_values = block_bits/value_bits;
    typedef array<value_type, block_values> value_array_type;

  private:

    static unsigned const length_bits = length_bits_;
    // FIXME: do something more intelligent than capping at 64
    static unsigned const length_type_bits =
        length_bits < word_bits ?
            word_bits :
        length_bits > 64 ?
            64 :
            length_bits;
    typedef typename uint_t<length_type_bits>::least length_type;
    static unsigned const length_words = length_bits/word_bits;
    BOOST_STATIC_ASSERT(!length_bits || length_bits % word_bits == 0);
    BOOST_STATIC_ASSERT(block_bits % value_bits == 0);

    BOOST_STATIC_ASSERT(!length_bits || value_bits <= length_bits);

  private:
    void
    process_block() {
        // Convert the input into words
        block_type block;
        pack<endian, value_bits, word_bits>(value_array, block);

        // Process the block
        block_hash.update(block);

        // Reset seen if we don't need to track the length
        if (!length_bits) seen = 0;
    }
    template <typename Dummy>
    typename enable_if_c<length_bits && sizeof(Dummy)>::type
    append_length(length_type length) {
        // Convert the input into words
        block_type block;
        pack<endian, value_bits, word_bits>(value_array, block);

        // Append length
        array<length_type, 1> length_array = {{length}};
        array<word_type, length_words> length_words_array;
        pack<endian, length_bits, word_bits>(length_array, length_words_array);
        for (unsigned i = length_words; i; --i) {
            block[block_words - i] = length_words_array[length_words - i];
        }

        // Process the last block
        block_hash.update(block);
    }
    template <typename Dummy>
    typename disable_if_c<length_bits && sizeof(Dummy)>::type
    append_length(length_type) {
        // No appending requested, so nothing to do
    }
  public:
    stream_preprocessor &
    update_one(value_type value) {
        unsigned i = seen % block_bits;
        unsigned j = i / value_bits;
        value_array[j] = value;
        seen += value_bits;
        if (i == block_bits - value_bits) {
            // Process the completed block
            process_block();
        }
        return *this;
    }
    template <typename IterT>
    stream_preprocessor &
    update_n(IterT p, size_t n) {
#ifndef BOOST_HASH_NO_OPTIMIZATION
        for ( ; n && (seen % block_bits); --n, ++p) {
            update_one(*p);
        }
        for ( ; n >= block_values; n -= block_values, p += block_values) {
            // Convert the input into words
            block_type block;
            pack_n<endian, value_bits, word_bits>(p, block_values,
                                                  &block[0], block_words);

            // Process the block
            block_hash.update(block);
            seen += block_bits;

            // Reset seen if we don't need to track the length
            if (!length_bits) seen = 0;
        }
#endif
        for ( ; n; --n, ++p) {
            update_one(*p);
        }
        return *this;
    }
    template <typename IterT>
    stream_preprocessor &
    update(IterT b, IterT e, std::random_access_iterator_tag) {
        return update_n(b, e-b);
    }
    template <typename IterT, typename Category>
    stream_preprocessor &
    update(IterT b, IterT e, Category) {
        while (b != e) update_one(*b++);
        return *this;
    }
    template <typename IterT>
    stream_preprocessor &
    update(IterT b, IterT e) {
        typedef typename std::iterator_traits<IterT>::iterator_category cat;
        return update(b, e, cat());
    }
    template <typename ContainerT>
    stream_preprocessor &
    update(ContainerT const &c) {
        return update_n(c.data(), c.size());
    }
    digest_type
    end_message() {
        length_type length = seen;

        // Add a 1 bit
#ifdef BOOST_HASH_NO_OPTIMIZATION
        array<bool, value_bits> padding_bits = {{1}};
        array<value_type, 1> padding_values;
        pack<endian, 1, value_bits>(padding_bits, padding_values);
        update_one(padding_values[0]);
#else
        value_type pad = 0;
        detail::imploder_step<endian, 1, value_bits, 0>::step(1, pad);
        update_one(pad);
#endif

        // Pad with 0 bits
        while ((seen + length_bits) % block_bits != 0) {
            update_one(value_type());
        }

        // Append length
        append_length<int>(length);

        // Reset for next message
        seen = 0;

        // Calculate digest and reset block_hash
        return block_hash.end_message();
    }
    digest_type digest() const {
        return stream_preprocessor(*this).end_message();
    }

  public:
    stream_preprocessor() : value_array(), block_hash(), seen() {}
    void
    reset() {
        seen = 0;
        block_hash.reset();
    }

  private:
    value_array_type value_array;
    block_hash_type block_hash;
    length_type seen;
};

} // namespace hashes
} // namespace boost

#endif // BOOST_HASH_STREAM_PREPROCESSOR_HPP

ext: hpp

max_stars_repo_name: dillonl/boost-cmake

max_issues_repo_name: dillonl/boost-cmake

max_forks_repo_name: dillonl/boost-cmake


text:
//=======================================================================
// Copyright 2007 Aaron Windsor
//
// Distributed under the Boost Software License, Version 1.0. (See
// accompanying file LICENSE_1_0.txt or copy at
// http://www.boost.org/LICENSE_1_0.txt)
//=======================================================================
#include <iostream>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/properties.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/property_map.hpp>
#include <boost/ref.hpp>
#include <vector>

#include <boost/graph/planar_canonical_ordering.hpp>
#include <boost/graph/boyer_myrvold_planar_test.hpp>

using namespace boost;

int main(int argc, char** argv)
{

  typedef adjacency_list
    < vecS,
      vecS,
      undirectedS,
      property<vertex_index_t, int>,
      property<edge_index_t, int>
    >
    graph;

  // Create a maximal planar graph on 6 vertices
  graph g(6);

  add_edge(0,1,g);
  add_edge(1,2,g);
  add_edge(2,3,g);
  add_edge(3,4,g);
  add_edge(4,5,g);
  add_edge(5,0,g);

  add_edge(0,2,g);
  add_edge(0,3,g);
  add_edge(0,4,g);

  add_edge(1,3,g);
  add_edge(1,4,g);
  add_edge(1,5,g);

  // Initialize the interior edge index
  property_map<graph, edge_index_t>::type e_index = get(edge_index, g);
  graph_traits<graph>::edges_size_type edge_count = 0;
  graph_traits<graph>::edge_iterator ei, ei_end;
  for(tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
    put(e_index, *ei, edge_count++);

  // Test for planarity - we know it is planar, we just want to
  // compute the planar embedding as a side-effect
  typedef std::vector< graph_traits<graph>::edge_descriptor > vec_t;
  std::vector<vec_t> embedding(num_vertices(g));
  if (boyer_myrvold_planarity_test(boyer_myrvold_params::graph = g,
                                   boyer_myrvold_params::embedding =
                                       &embedding[0]
                                   )
      )
    std::cout << "Input graph is planar" << std::endl;
  else
    std::cout << "Input graph is not planar" << std::endl;

  typedef std::vector<graph_traits<graph>::vertex_descriptor>
    ordering_storage_t;

  ordering_storage_t ordering;
  planar_canonical_ordering(g, &embedding[0], std::back_inserter(ordering));

  ordering_storage_t::iterator oi, oi_end;
  oi_end = ordering.end();
  std::cout << "The planar canonical ordering is: ";
  for(oi = ordering.begin(); oi != oi_end; ++oi)
    std::cout << *oi << " ";
  std::cout << std::endl;

  return 0;
}