// Protocol Buffers - Google's data interchange format
// Copyright 2008 Google Inc.  All rights reserved.
// https://developers.google.com/protocol-buffers/
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are
// met:
//
//     * Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
//     * Redistributions in binary form must reproduce the above
// copyright notice, this list of conditions and the following disclaimer
// in the documentation and/or other materials provided with the
// distribution.
//     * Neither the name of Google Inc. nor the names of its
// contributors may be used to endorse or promote products derived from
// this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

#include <google/protobuf/util/field_mask_util.h>

#include <google/protobuf/stubs/strutil.h>
#include <google/protobuf/stubs/map_util.h>

namespace google {
namespace protobuf {
namespace util {

using google::protobuf::FieldMask;

string FieldMaskUtil::ToString(const FieldMask& mask) {
  return Join(mask.paths(), ",");
}

void FieldMaskUtil::FromString(StringPiece str, FieldMask* out) {
  out->Clear();
  vector<string> paths = Split(str, ",");
  for (int i = 0; i < paths.size(); ++i) {
    if (paths[i].empty()) continue;
    out->add_paths(paths[i]);
  }
}

bool FieldMaskUtil::SnakeCaseToCamelCase(StringPiece input, string* output) {
  output->clear();
  bool after_underscore = false;
  for (int i = 0; i < input.size(); ++i) {
    if (input[i] >= 'A' && input[i] <= 'Z') {
      // The field name must not contain uppercase letters.
      return false;
    }
    if (after_underscore) {
      if (input[i] >= 'a' && input[i] <= 'z') {
        output->push_back(input[i] + 'A' - 'a');
        after_underscore = false;
      } else {
        // The character after a "_" must be a lowercase letter.
        return false;
      }
    } else if (input[i] == '_') {
      after_underscore = true;
    } else {
      output->push_back(input[i]);
    }
  }
  if (after_underscore) {
    // Trailing "_".
    return false;
  }
  return true;
}

bool FieldMaskUtil::CamelCaseToSnakeCase(StringPiece input, string* output) {
  output->clear();
  for (int i = 0; i < input.size(); ++i) {
    if (input[i] == '_') {
      // The field name must not contain "_"s.
      return false;
    }
    if (input[i] >= 'A' && input[i] <= 'Z') {
      output->push_back('_');
      output->push_back(input[i] + 'a' - 'A');
    } else {
      output->push_back(input[i]);
    }
  }
  return true;
}

bool FieldMaskUtil::ToJsonString(const FieldMask& mask, string* out) {
  out->clear();
  for (int i = 0; i < mask.paths_size(); ++i) {
    const string& path = mask.paths(i);
    string camelcase_path;
    if (!SnakeCaseToCamelCase(path, &camelcase_path)) {
      return false;
    }
    if (i > 0) {
      out->push_back(',');
    }
    out->append(camelcase_path);
  }
  return true;
}

bool FieldMaskUtil::FromJsonString(StringPiece str, FieldMask* out) {
  out->Clear();
  vector<string> paths = Split(str, ",");
  for (int i = 0; i < paths.size(); ++i) {
    if (paths[i].empty()) continue;
    string snakecase_path;
    if (!CamelCaseToSnakeCase(paths[i], &snakecase_path)) {
      return false;
    }
    out->add_paths(snakecase_path);
  }
  return true;
}

bool FieldMaskUtil::InternalIsValidPath(const Descriptor* descriptor,
                                        StringPiece path) {
  vector<string> parts = Split(path, ".");
  for (int i = 0; i < parts.size(); ++i) {
    const string& field_name = parts[i];
    if (descriptor == NULL) {
      return false;
    }
    const FieldDescriptor* field = descriptor->FindFieldByName(field_name);
    if (field == NULL) {
      return false;
    }
    if (!field->is_repeated() &&
        field->cpp_type() == FieldDescriptor::CPPTYPE_MESSAGE) {
      descriptor = field->message_type();
    } else {
      descriptor = NULL;
    }
  }
  return true;
}

void FieldMaskUtil::InternalGetFieldMaskForAllFields(
    const Descriptor* descriptor, FieldMask* out) {
  for (int i = 0; i < descriptor->field_count(); ++i) {
    out->add_paths(descriptor->field(i)->name());
  }
}

namespace {
// A FieldMaskTree represents a FieldMask in a tree structure. For example,
// given a FieldMask "foo.bar,foo.baz,bar.baz", the FieldMaskTree will be:
//
//   [root] -+- foo -+- bar
//           |       |
//           |       +- baz
//           |
//           +- bar --- baz
//
// In the tree, each leaf node represents a field path.
class FieldMaskTree {
 public:
  FieldMaskTree();
  ~FieldMaskTree();

  void MergeFromFieldMask(const FieldMask& mask);
  void MergeToFieldMask(FieldMask* mask);

  // Add a field path into the tree. In a FieldMask, each field path matches
  // the specified field and also all its sub-fields. If the field path to
  // add is a sub-path of an existing field path in the tree (i.e., a leaf
  // node), it means the tree already matches the given path so nothing will
  // be added to the tree. If the path matches an existing non-leaf node in the
  // tree, that non-leaf node will be turned into a leaf node with all its
  // children removed because the path matches all the node's children.
  void AddPath(const string& path);

  // Calculate the intersection part of a field path with this tree and add
  // the intersection field path into out.
  void IntersectPath(const string& path, FieldMaskTree* out);

  // Merge all fields specified by this tree from one message to another.
  void MergeMessage(const Message& source,
                    const FieldMaskUtil::MergeOptions& options,
                    Message* destination) {
    // Do nothing if the tree is empty.
    if (root_.children.empty()) {
      return;
    }
    MergeMessage(&root_, source, options, destination);
  }

 private:
  struct Node {
    Node() {}

    ~Node() { ClearChildren(); }

    void ClearChildren() {
      for (map<string, Node*>::iterator it = children.begin();
           it != children.end(); ++it) {
        delete it->second;
      }
      children.clear();
    }

    map<string, Node*> children;

   private:
    GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(Node);
  };

  // Merge a sub-tree to mask. This method adds the field paths represented
  // by all leaf nodes descended from "node" to mask.
  void MergeToFieldMask(const string& prefix, const Node* node, FieldMask* out);

  // Merge all leaf nodes of a sub-tree to another tree.
  void MergeLeafNodesToTree(const string& prefix, const Node* node,
                            FieldMaskTree* out);

  // Merge all fields specified by a sub-tree from one message to another.
  void MergeMessage(const Node* node, const Message& source,
                    const FieldMaskUtil::MergeOptions& options,
                    Message* destination);

  Node root_;

  GOOGLE_DISALLOW_EVIL_CONSTRUCTORS(FieldMaskTree);
};

FieldMaskTree::FieldMaskTree() {}

FieldMaskTree::~FieldMaskTree() {}

void FieldMaskTree::MergeFromFieldMask(const FieldMask& mask) {
  for (int i = 0; i < mask.paths_size(); ++i) {
    AddPath(mask.paths(i));
  }
}

void FieldMaskTree::MergeToFieldMask(FieldMask* mask) {
  MergeToFieldMask("", &root_, mask);
}

void FieldMaskTree::MergeToFieldMask(const string& prefix, const Node* node,
                                     FieldMask* out) {
  if (node->children.empty()) {
    if (prefix.empty()) {
      // This is the root node.
      return;
    }
    out->add_paths(prefix);
    return;
  }
  for (map<string, Node*>::const_iterator it = node->children.begin();
       it != node->children.end(); ++it) {
    string current_path = prefix.empty() ? it->first : prefix + "." + it->first;
    MergeToFieldMask(current_path, it->second, out);
  }
}

void FieldMaskTree::AddPath(const string& path) {
  vector<string> parts = Split(path, ".");
  if (parts.empty()) {
    return;
  }
  bool new_branch = false;
  Node* node = &root_;
  for (int i = 0; i < parts.size(); ++i) {
    if (!new_branch && node != &root_ && node->children.empty()) {
      // Path matches an existing leaf node. This means the path is already
      // coverred by this tree (for example, adding "foo.bar.baz" to a tree
      // which already contains "foo.bar").
      return;
    }
    const string& node_name = parts[i];
    Node*& child = node->children[node_name];
    if (child == NULL) {
      new_branch = true;
      child = new Node();
    }
    node = child;
  }
  if (!node->children.empty()) {
    node->ClearChildren();
  }
}

void FieldMaskTree::IntersectPath(const string& path, FieldMaskTree* out) {
  vector<string> parts = Split(path, ".");
  if (parts.empty()) {
    return;
  }
  const Node* node = &root_;
  for (int i = 0; i < parts.size(); ++i) {
    if (node->children.empty()) {
      if (node != &root_) {
        out->AddPath(path);
      }
      return;
    }
    const string& node_name = parts[i];
    const Node* result = FindPtrOrNull(node->children, node_name);
    if (result == NULL) {
      // No intersection found.
      return;
    }
    node = result;
  }
  // Now we found a matching node with the given path. Add all leaf nodes
  // to out.
  MergeLeafNodesToTree(path, node, out);
}

void FieldMaskTree::MergeLeafNodesToTree(const string& prefix, const Node* node,
                                         FieldMaskTree* out) {
  if (node->children.empty()) {
    out->AddPath(prefix);
  }
  for (map<string, Node*>::const_iterator it = node->children.begin();
       it != node->children.end(); ++it) {
    string current_path = prefix.empty() ? it->first : prefix + "." + it->first;
    MergeLeafNodesToTree(current_path, it->second, out);
  }
}

void FieldMaskTree::MergeMessage(const Node* node, const Message& source,
                                 const FieldMaskUtil::MergeOptions& options,
                                 Message* destination) {
  GOOGLE_DCHECK(!node->children.empty());
  const Reflection* source_reflection = source.GetReflection();
  const Reflection* destination_reflection = destination->GetReflection();
  const Descriptor* descriptor = source.GetDescriptor();
  for (map<string, Node*>::const_iterator it = node->children.begin();
       it != node->children.end(); ++it) {
    const string& field_name = it->first;
    const Node* child = it->second;
    const FieldDescriptor* field = descriptor->FindFieldByName(field_name);
    if (field == NULL) {
      GOOGLE_LOG(ERROR) << "Cannot find field \"" << field_name << "\" in message "
                 << descriptor->full_name();
      continue;
    }
    if (!child->children.empty()) {
      // Sub-paths are only allowed for singular message fields.
      if (field->is_repeated() ||
          field->cpp_type() != FieldDescriptor::CPPTYPE_MESSAGE) {
        GOOGLE_LOG(ERROR) << "Field \"" << field_name << "\" in message "
                   << descriptor->full_name()
                   << " is not a singular message field and cannot "
                   << "have sub-fields.";
        continue;
      }
      MergeMessage(child, source_reflection->GetMessage(source, field), options,
                   destination_reflection->MutableMessage(destination, field));
      continue;
    }
    if (!field->is_repeated()) {
      switch (field->cpp_type()) {
#define COPY_VALUE(TYPE, Name)                                            \
  case FieldDescriptor::CPPTYPE_##TYPE: {                                 \
    destination_reflection->Set##Name(                                    \
        destination, field, source_reflection->Get##Name(source, field)); \
    break;                                                                \
  }
        COPY_VALUE(BOOL, Bool)
        COPY_VALUE(INT32, Int32)
        COPY_VALUE(INT64, Int64)
        COPY_VALUE(UINT32, UInt32)
        COPY_VALUE(UINT64, UInt64)
        COPY_VALUE(FLOAT, Float)
        COPY_VALUE(DOUBLE, Double)
        COPY_VALUE(ENUM, Enum)
        COPY_VALUE(STRING, String)
#undef COPY_VALUE
        case FieldDescriptor::CPPTYPE_MESSAGE: {
          if (options.replace_message_fields()) {
            destination_reflection->ClearField(destination, field);
          }
          if (source_reflection->HasField(source, field)) {
            destination_reflection->MutableMessage(destination, field)
                ->MergeFrom(source_reflection->GetMessage(source, field));
          }
          break;
        }
      }
    } else {
      if (options.replace_repeated_fields()) {
        destination_reflection->ClearField(destination, field);
      }
      switch (field->cpp_type()) {
#define COPY_REPEATED_VALUE(TYPE, Name)                            \
  case FieldDescriptor::CPPTYPE_##TYPE: {                          \
    int size = source_reflection->FieldSize(source, field);        \
    for (int i = 0; i < size; ++i) {                               \
      destination_reflection->Add##Name(                           \
          destination, field,                                      \
          source_reflection->GetRepeated##Name(source, field, i)); \
    }                                                              \
    break;                                                         \
  }
        COPY_REPEATED_VALUE(BOOL, Bool)
        COPY_REPEATED_VALUE(INT32, Int32)
        COPY_REPEATED_VALUE(INT64, Int64)
        COPY_REPEATED_VALUE(UINT32, UInt32)
        COPY_REPEATED_VALUE(UINT64, UInt64)
        COPY_REPEATED_VALUE(FLOAT, Float)
        COPY_REPEATED_VALUE(DOUBLE, Double)
        COPY_REPEATED_VALUE(ENUM, Enum)
        COPY_REPEATED_VALUE(STRING, String)
#undef COPY_REPEATED_VALUE
        case FieldDescriptor::CPPTYPE_MESSAGE: {
          int size = source_reflection->FieldSize(source, field);
          for (int i = 0; i < size; ++i) {
            destination_reflection->AddMessage(destination, field)
                ->MergeFrom(
                    source_reflection->GetRepeatedMessage(source, field, i));
          }
          break;
        }
      }
    }
  }
}

}  // namespace

void FieldMaskUtil::ToCanonicalForm(const FieldMask& mask, FieldMask* out) {
  FieldMaskTree tree;
  tree.MergeFromFieldMask(mask);
  out->Clear();
  tree.MergeToFieldMask(out);
}

void FieldMaskUtil::Union(const FieldMask& mask1, const FieldMask& mask2,
                          FieldMask* out) {
  FieldMaskTree tree;
  tree.MergeFromFieldMask(mask1);
  tree.MergeFromFieldMask(mask2);
  out->Clear();
  tree.MergeToFieldMask(out);
}

void FieldMaskUtil::Intersect(const FieldMask& mask1, const FieldMask& mask2,
                              FieldMask* out) {
  FieldMaskTree tree, intersection;
  tree.MergeFromFieldMask(mask1);
  for (int i = 0; i < mask2.paths_size(); ++i) {
    tree.IntersectPath(mask2.paths(i), &intersection);
  }
  out->Clear();
  intersection.MergeToFieldMask(out);
}

bool FieldMaskUtil::IsPathInFieldMask(StringPiece path, const FieldMask& mask) {
  for (int i = 0; i < mask.paths_size(); ++i) {
    const string& mask_path = mask.paths(i);
    if (path == mask_path) {
      return true;
    } else if (mask_path.length() < path.length()) {
      // Also check whether mask.paths(i) is a prefix of path.
      if (path.substr(0, mask_path.length() + 1).compare(mask_path + ".") ==
          0) {
        return true;
      }
    }
  }
  return false;
}

void FieldMaskUtil::MergeMessageTo(const Message& source, const FieldMask& mask,
                                   const MergeOptions& options,
                                   Message* destination) {
  GOOGLE_CHECK(source.GetDescriptor() == destination->GetDescriptor());
  // Build a FieldMaskTree and walk through the tree to merge all specified
  // fields.
  FieldMaskTree tree;
  tree.MergeFromFieldMask(mask);
  tree.MergeMessage(source, options, destination);
}

}  // namespace util
}  // namespace protobuf
}  // namespace google