utility/TreeStringSerializable.hpp - incubator-retired-quickstep - Git at Google

 /**
  * Licensed to the Apache Software Foundation (ASF) under one
  * or more contributor license agreements.  See the NOTICE file
  * distributed with this work for additional information
  * regarding copyright ownership.  The ASF licenses this file
  * to you 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.
  **/

 #ifndef QUICKSTEP_UTILITY_TREE_STRING_SERIALIZABLE_HPP_
 #define QUICKSTEP_UTILITY_TREE_STRING_SERIALIZABLE_HPP_

 #include <cstddef>
 #include <string>
 #include <vector>

 #include "utility/Macros.hpp"

 #include "glog/logging.h"

 namespace quickstep {

 /** \addtogroup Utility
  *  @{
  */

 /**
  * @brief Based class for a tree-structured type.
  *        It provides common logic in string serialization.
  *
  * @note This class is templated so that it may be used in both parser
  *       tree and optimizer trees. The parser tree uses unique_ptr to
  *       manage the ownership of fields, while the optimizer tree uses shared_ptr.
  *       TreeNodeType for a parser tree is a constant pointer, whereas it is
  *       a shared_ptr for an optimizer tree.
  */
 template<class TreeNodeType>
 class TreeStringSerializable {
  public:
   static const int kMaxLineWidth = 80;

   virtual ~TreeStringSerializable() {
   }

   /**
    * @return The node name in the tree-structured string.
    */
   virtual std::string getName() const = 0;

   /**
    * @return A tree-structured string representation.
    */
   std::string toString() const {
     return getNodeString(true /* is_root */,
                          true /* is_last */,
                          "" /* parent_prefix */,
                          "" /* node_name */);
   }

   /**
    * @return A short one-line string representation.
    */
   std::string getShortString() const {
     std::vector<std::string> inline_field_names;
     std::vector<std::string> inline_field_values;
     std::vector<std::string> non_container_child_field_names;
     std::vector<TreeNodeType> non_container_child_fields;
     std::vector<std::string> container_child_field_names;
     std::vector<std::vector<TreeNodeType>> container_child_fields;

     getFieldStringItems(&inline_field_names,
                         &inline_field_values,
                         &non_container_child_field_names,
                         &non_container_child_fields,
                         &container_child_field_names,
                         &container_child_fields);
     return getHeadString(true /* is_root */,
                          true /* is_last */,
                          "" /* prefix */,
                          "" /* node_name */,
                          inline_field_names,
                          inline_field_values,
                          false /* multi_line */);
   }

  protected:
   TreeStringSerializable() {
   }

   /**
    *
    * @brief Returns all the fields (the name and the value) that need to be shown in the output string. There are
    *        three types of fields:
    *        1) Inline fields are those that are not represented as tree nodes.
    *        2) Each non-container field corresponds to a tree node in the string representation. Each field corresponds
    *           to a single subtree.
    *        3) A container field contains a vector of non-container fields. They are all attached to a common child tree
    *           node.
    *
    * @param inline_field_names A list of inline field names.
    * @param inline_field_values A list of inline field string value representation.
    *            1:1 matching with inline_field_names.
    * @param non_container_child_field_names A list of names for non-container fields.
    * @param non_container_child_fields A list of non-container fields.
    * @param container_child_field_names A list of names for container fields.
    * @param container_child_fields A list of container fields.
    */
   virtual void getFieldStringItems(std::vector<std::string> *inline_field_names,
                                    std::vector<std::string> *inline_field_values,
                                    std::vector<std::string> *non_container_child_field_names,
                                    std::vector<TreeNodeType> *non_container_child_fields,
                                    std::vector<std::string> *container_child_field_names,
                                    std::vector<std::vector<TreeNodeType>> *container_child_fields) const = 0;

   /**
    * @brief Returns a tree-structured string representation.
    *
    * @param is_root Whether this node is a root.
    * @param is_last Whether this node is the last child node of its parent.
    * @param parent_prefix The prefix of the parent node.
    * @param node_name The name of this node in the parent node. This is different from getName() where the name is
    *            independent of the parent.
    * @return A tree-structured string representation.
    */
   std::string getNodeString(bool is_root,
                             bool is_last,
                             const std::string &parent_prefix,
                             const std::string &node_name) const {
     std::vector<std::string> inline_field_names;
     std::vector<std::string> inline_field_values;
     std::vector<std::string> non_container_child_field_names;
     std::vector<TreeNodeType> non_container_child_fields;
     std::vector<std::string> container_child_field_names;
     std::vector<std::vector<TreeNodeType>> container_child_fields;

     getFieldStringItems(&inline_field_names,
                         &inline_field_values,
                         &non_container_child_field_names,
                         &non_container_child_fields,
                         &container_child_field_names,
                         &container_child_fields);
     DCHECK_EQ(non_container_child_field_names.size(), non_container_child_fields.size());
     DCHECK_EQ(container_child_field_names.size(), container_child_field_names.size());
     DCHECK(!is_root || parent_prefix.empty());
     DCHECK(!is_root || is_last);

     std::string ret = getHeadString(is_root, is_last, parent_prefix, node_name, inline_field_names, inline_field_values,
                                     true /* multi_line */);
     ret.append("\n");

     std::string child_prefix;
     if (!is_root) {
       child_prefix = GetNewIndentedStringPrefix(is_last, parent_prefix);
     }

     // Append strings of non_container child fields.
     for (int i = 0; i < static_cast<int>(non_container_child_fields.size()) - 1; ++i) {
       ret.append(
           non_container_child_fields[i]->getNodeString(false /* is_root */,
                                                        false /* is_last */,
                                                        child_prefix,
                                                        non_container_child_field_names[i]));
     }

     if (!non_container_child_fields.empty()) {
       if (container_child_fields.empty()) {
         ret.append(
             non_container_child_fields.back()->getNodeString(false /* is_root */,
                                                              true /* is_last */,
                                                              child_prefix,
                                                              non_container_child_field_names.back()));
       } else {
         ret.append(
             non_container_child_fields.back()->getNodeString(false /* is_root */,
                                                              false /* is_last */,
                                                              child_prefix,
                                                              non_container_child_field_names.back()));
       }
     }

     // Append strings of container child fields.
     for (int i = 0; i < static_cast<int>(container_child_fields.size()) - 1; ++i) {
       ret.append(GetNodeListString(false /* is_last */,
                                    child_prefix,
                                    container_child_field_names[i],
                                    container_child_fields[i]));
     }

     if (!container_child_fields.empty()) {
       ret.append(
           GetNodeListString(true /* is_last */,
                             child_prefix,
                             container_child_field_names.back(),
                             container_child_fields.back()));
     }

     return ret;
   }

   /**
    * @brief Creates a tree node with a list of child tree nodes:
    *            +-NodeList
    *              +- Item1
    *              +- Item2
    *              +- Item3
    *
    * @param is_last Whether this is the last child node of the parent.
    * @param prefix The initial prefix of this node.
    * @param node_name The node name.
    * @param node_list The list of nodes.
    * @return A tree node string with a list of .
    */
   static std::string GetNodeListString(bool is_last,
                                        const std::string &prefix,
                                        const std::string &node_name,
                                        const std::vector<TreeNodeType> &node_list) {
     std::string ret;
     std::string item_prefix = prefix;
     if (!node_name.empty()) {
       ret = item_prefix;
       ret.append("+-").append(node_name).append("=").append("\n");
       // Indent the child fields only if the node name is not empty.
       item_prefix = GetNewIndentedStringPrefix(is_last, prefix);
     }

     if (node_list.empty()) {
       ret.append(item_prefix).append("+-[]\n");
       return ret;
     }

     for (int i = 0; i < static_cast<int>(node_list.size()) - 1; ++i) {
       // Do not provide the node name so that there will not be an extra indent.
       ret.append(node_list[i]->getNodeString(false /* is_root */,
                                              false /* is_last */,
                                              item_prefix,
                                              "" /* node_name */));
     }
     if (!node_name.empty()) {
       ret.append(node_list.back()->getNodeString(false /* is_root */,
                                                  true /* is_last */,
                                                  item_prefix,
                                                  "" /* node_name */));
     } else {
       ret.append(node_list.back()->getNodeString(false /* is_root */,
                                                  (node_name.empty() ? is_last : true),
                                                  item_prefix, "" /* node_name */));
     }
     return ret;
   }

   /**
    * @brief Returns the node head string with the form like NodeName[inline_field=value1,inline_field=value2].
    *
    * @param is_root Whether this node is the root.
    * @param is_last Whether this node is the last child of its parent.
    * @param parent_prefix The prefix of its parent node.
    * @param node_name The node name in the parent node.
    * @param field_names The names of inline fields.
    * @param field_values The string values of the inline fields.
    * @param multi_line Whether the returned string is allowed to have multiple lines.
    * @return The node head string.
    */
   std::string getHeadString(bool is_root,
                             bool is_last,
                             const std::string &parent_prefix,
                             const std::string &node_name,
                             const std::vector<std::string> &field_names,
                             const std::vector<std::string> &field_values,
                             bool multi_line) const {
     DCHECK_EQ(field_names.size(), field_values.size());
     std::string ret;

     const std::string name = getName();
     std::string prefix = GetNewIndentedStringPrefix(is_last, parent_prefix);
     std::string current_line = parent_prefix;
     if (!is_root) {
       current_line.append("+-");
     }

     if (!node_name.empty()) {
       current_line.append(node_name).append("=");
       if (current_line.size() + name.size() > kMaxLineWidth && multi_line) {
         ret.append(current_line).append("\n");
         current_line = prefix;
       }
     }

     current_line.append(name);

     if (!field_names.empty()) {
       // "[" and "]" are considered as inline fields
       // so that we can add newlines for them.
       AppendInlineString(prefix, "[" /* inline_field */, multi_line, &current_line, &ret);
       for (size_t i = 0; i < field_names.size(); ++i) {
         std::string inline_field = field_names[i];
         inline_field.append("=").append(field_values[i]);
         if (i < field_names.size() - 1) {
           inline_field.append(",");
         }
         AppendInlineString(prefix, inline_field, multi_line, &current_line, &ret);
       }
       AppendInlineString(prefix, "]" /* inline_field */, false /* multi_line */, &current_line, &ret);
     }

     if (!current_line.empty()) {
       ret.append(current_line);
     }

     return ret;
   }

   /**
    * @brief Appends an inline field to \p output if the length of the current line is greater than MAX_LINE_WIDTH.
    *        Otherwise updates \p current_line.
    */
   static void AppendInlineString(const std::string &prefix,
                                  const std::string &inline_field,
                                  bool multi_line,
                                  std::string *current_line,
                                  std::string *output) {
     if (current_line->size() + inline_field.size() > kMaxLineWidth && multi_line) {
       output->append(*current_line).append("\n");
       *current_line = prefix;
     }
     current_line->append(inline_field);
   }

   /**
    * @brief Returns a new prefix string indented by 2.
    *
    * @param is_last Whether this node is the last child of the parent.
    * @param prefix The current prefix.
    * @return A new prefix string indented by 2.
    */
   static std::string GetNewIndentedStringPrefix(bool is_last, const std::string &prefix) {
     std::string new_prefix(prefix);
     if (!is_last) {
       new_prefix.append("|").append(" ");
     } else {
       new_prefix.append(2, ' ');
     }
     return new_prefix;
   }

  private:
   DISALLOW_COPY_AND_ASSIGN(TreeStringSerializable);
 };

 /** @} */

 }  // namespace quickstep

 #endif /* QUICKSTEP_UTILITY_TREE_STRING_SERIALIZABLE_HPP_ */
	/**
	* Licensed to the Apache Software Foundation (ASF) under one
	* or more contributor license agreements. See the NOTICE file
	* distributed with this work for additional information
	* regarding copyright ownership. The ASF licenses this file
	* to you 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.
	**/

	#ifndef QUICKSTEP_UTILITY_TREE_STRING_SERIALIZABLE_HPP_
	#define QUICKSTEP_UTILITY_TREE_STRING_SERIALIZABLE_HPP_

	#include <cstddef>
	#include <string>
	#include <vector>

	#include "utility/Macros.hpp"

	#include "glog/logging.h"

	namespace quickstep {

	/** \addtogroup Utility
	* @{
	*/

	/**
	* @brief Based class for a tree-structured type.
	* It provides common logic in string serialization.
	*
	* @note This class is templated so that it may be used in both parser
	* tree and optimizer trees. The parser tree uses unique_ptr to
	* manage the ownership of fields, while the optimizer tree uses shared_ptr.
	* TreeNodeType for a parser tree is a constant pointer, whereas it is
	* a shared_ptr for an optimizer tree.
	*/
	template<class TreeNodeType>
	class TreeStringSerializable {
	public:
	static const int kMaxLineWidth = 80;

	virtual ~TreeStringSerializable() {
	}

	/**
	* @return The node name in the tree-structured string.
	*/
	virtual std::string getName() const = 0;

	/**
	* @return A tree-structured string representation.
	*/
	std::string toString() const {
	return getNodeString(true /* is_root */,
	true /* is_last */,
	"" /* parent_prefix */,
	"" /* node_name */);
	}

	/**
	* @return A short one-line string representation.
	*/
	std::string getShortString() const {
	std::vector<std::string> inline_field_names;
	std::vector<std::string> inline_field_values;
	std::vector<std::string> non_container_child_field_names;
	std::vector<TreeNodeType> non_container_child_fields;
	std::vector<std::string> container_child_field_names;
	std::vector<std::vector<TreeNodeType>> container_child_fields;

	getFieldStringItems(&inline_field_names,
	&inline_field_values,
	&non_container_child_field_names,
	&non_container_child_fields,
	&container_child_field_names,
	&container_child_fields);
	return getHeadString(true /* is_root */,
	true /* is_last */,
	"" /* prefix */,
	"" /* node_name */,
	inline_field_names,
	inline_field_values,
	false /* multi_line */);
	}

	protected:
	TreeStringSerializable() {
	}

	/**
	*
	* @brief Returns all the fields (the name and the value) that need to be shown in the output string. There are
	* three types of fields:
	* 1) Inline fields are those that are not represented as tree nodes.
	* 2) Each non-container field corresponds to a tree node in the string representation. Each field corresponds
	* to a single subtree.
	* 3) A container field contains a vector of non-container fields. They are all attached to a common child tree
	* node.
	*
	* @param inline_field_names A list of inline field names.
	* @param inline_field_values A list of inline field string value representation.
	* 1:1 matching with inline_field_names.
	* @param non_container_child_field_names A list of names for non-container fields.
	* @param non_container_child_fields A list of non-container fields.
	* @param container_child_field_names A list of names for container fields.
	* @param container_child_fields A list of container fields.
	*/
	virtual void getFieldStringItems(std::vector<std::string> *inline_field_names,
	std::vector<std::string> *inline_field_values,
	std::vector<std::string> *non_container_child_field_names,
	std::vector<TreeNodeType> *non_container_child_fields,
	std::vector<std::string> *container_child_field_names,
	std::vector<std::vector<TreeNodeType>> *container_child_fields) const = 0;

	/**
	* @brief Returns a tree-structured string representation.
	*
	* @param is_root Whether this node is a root.
	* @param is_last Whether this node is the last child node of its parent.
	* @param parent_prefix The prefix of the parent node.
	* @param node_name The name of this node in the parent node. This is different from getName() where the name is
	* independent of the parent.
	* @return A tree-structured string representation.
	*/
	std::string getNodeString(bool is_root,
	bool is_last,
	const std::string &parent_prefix,
	const std::string &node_name) const {
	std::vector<std::string> inline_field_names;
	std::vector<std::string> inline_field_values;
	std::vector<std::string> non_container_child_field_names;
	std::vector<TreeNodeType> non_container_child_fields;
	std::vector<std::string> container_child_field_names;
	std::vector<std::vector<TreeNodeType>> container_child_fields;

	getFieldStringItems(&inline_field_names,
	&inline_field_values,
	&non_container_child_field_names,
	&non_container_child_fields,
	&container_child_field_names,
	&container_child_fields);
	DCHECK_EQ(non_container_child_field_names.size(), non_container_child_fields.size());
	DCHECK_EQ(container_child_field_names.size(), container_child_field_names.size());
	DCHECK(!is_root \|\| parent_prefix.empty());
	DCHECK(!is_root \|\| is_last);

	std::string ret = getHeadString(is_root, is_last, parent_prefix, node_name, inline_field_names, inline_field_values,
	true /* multi_line */);
	ret.append("\n");

	std::string child_prefix;
	if (!is_root) {
	child_prefix = GetNewIndentedStringPrefix(is_last, parent_prefix);
	}

	// Append strings of non_container child fields.
	for (int i = 0; i < static_cast<int>(non_container_child_fields.size()) - 1; ++i) {
	ret.append(
	non_container_child_fields[i]->getNodeString(false /* is_root */,
	false /* is_last */,
	child_prefix,
	non_container_child_field_names[i]));
	}

	if (!non_container_child_fields.empty()) {
	if (container_child_fields.empty()) {
	ret.append(
	non_container_child_fields.back()->getNodeString(false /* is_root */,
	true /* is_last */,
	child_prefix,
	non_container_child_field_names.back()));
	} else {
	ret.append(
	non_container_child_fields.back()->getNodeString(false /* is_root */,
	false /* is_last */,
	child_prefix,
	non_container_child_field_names.back()));
	}
	}

	// Append strings of container child fields.
	for (int i = 0; i < static_cast<int>(container_child_fields.size()) - 1; ++i) {
	ret.append(GetNodeListString(false /* is_last */,
	child_prefix,
	container_child_field_names[i],
	container_child_fields[i]));
	}

	if (!container_child_fields.empty()) {
	ret.append(
	GetNodeListString(true /* is_last */,
	child_prefix,
	container_child_field_names.back(),
	container_child_fields.back()));
	}

	return ret;
	}

	/**
	* @brief Creates a tree node with a list of child tree nodes:
	* +-NodeList
	* +- Item1
	* +- Item2
	* +- Item3
	*
	* @param is_last Whether this is the last child node of the parent.
	* @param prefix The initial prefix of this node.
	* @param node_name The node name.
	* @param node_list The list of nodes.
	* @return A tree node string with a list of .
	*/
	static std::string GetNodeListString(bool is_last,
	const std::string &prefix,
	const std::string &node_name,
	const std::vector<TreeNodeType> &node_list) {
	std::string ret;
	std::string item_prefix = prefix;
	if (!node_name.empty()) {
	ret = item_prefix;
	ret.append("+-").append(node_name).append("=").append("\n");
	// Indent the child fields only if the node name is not empty.
	item_prefix = GetNewIndentedStringPrefix(is_last, prefix);
	}

	if (node_list.empty()) {
	ret.append(item_prefix).append("+-[]\n");
	return ret;
	}

	for (int i = 0; i < static_cast<int>(node_list.size()) - 1; ++i) {
	// Do not provide the node name so that there will not be an extra indent.
	ret.append(node_list[i]->getNodeString(false /* is_root */,
	false /* is_last */,
	item_prefix,
	"" /* node_name */));
	}
	if (!node_name.empty()) {
	ret.append(node_list.back()->getNodeString(false /* is_root */,
	true /* is_last */,
	item_prefix,
	"" /* node_name */));
	} else {
	ret.append(node_list.back()->getNodeString(false /* is_root */,
	(node_name.empty() ? is_last : true),
	item_prefix, "" /* node_name */));
	}
	return ret;
	}

	/**
	* @brief Returns the node head string with the form like NodeName[inline_field=value1,inline_field=value2].
	*
	* @param is_root Whether this node is the root.
	* @param is_last Whether this node is the last child of its parent.
	* @param parent_prefix The prefix of its parent node.
	* @param node_name The node name in the parent node.
	* @param field_names The names of inline fields.
	* @param field_values The string values of the inline fields.
	* @param multi_line Whether the returned string is allowed to have multiple lines.
	* @return The node head string.
	*/
	std::string getHeadString(bool is_root,
	bool is_last,
	const std::string &parent_prefix,
	const std::string &node_name,
	const std::vector<std::string> &field_names,
	const std::vector<std::string> &field_values,
	bool multi_line) const {
	DCHECK_EQ(field_names.size(), field_values.size());
	std::string ret;

	const std::string name = getName();
	std::string prefix = GetNewIndentedStringPrefix(is_last, parent_prefix);
	std::string current_line = parent_prefix;
	if (!is_root) {
	current_line.append("+-");
	}

	if (!node_name.empty()) {
	current_line.append(node_name).append("=");
	if (current_line.size() + name.size() > kMaxLineWidth && multi_line) {
	ret.append(current_line).append("\n");
	current_line = prefix;
	}
	}

	current_line.append(name);

	if (!field_names.empty()) {
	// "[" and "]" are considered as inline fields
	// so that we can add newlines for them.
	AppendInlineString(prefix, "[" /* inline_field */, multi_line, &current_line, &ret);
	for (size_t i = 0; i < field_names.size(); ++i) {
	std::string inline_field = field_names[i];
	inline_field.append("=").append(field_values[i]);
	if (i < field_names.size() - 1) {
	inline_field.append(",");
	}
	AppendInlineString(prefix, inline_field, multi_line, &current_line, &ret);
	}
	AppendInlineString(prefix, "]" /* inline_field /, false / multi_line */, &current_line, &ret);
	}

	if (!current_line.empty()) {
	ret.append(current_line);
	}

	return ret;
	}

	/**
	* @brief Appends an inline field to \p output if the length of the current line is greater than MAX_LINE_WIDTH.
	* Otherwise updates \p current_line.
	*/
	static void AppendInlineString(const std::string &prefix,
	const std::string &inline_field,
	bool multi_line,
	std::string *current_line,
	std::string *output) {
	if (current_line->size() + inline_field.size() > kMaxLineWidth && multi_line) {
	output->append(*current_line).append("\n");
	*current_line = prefix;
	}
	current_line->append(inline_field);
	}

	/**
	* @brief Returns a new prefix string indented by 2.
	*
	* @param is_last Whether this node is the last child of the parent.
	* @param prefix The current prefix.
	* @return A new prefix string indented by 2.
	*/
	static std::string GetNewIndentedStringPrefix(bool is_last, const std::string &prefix) {
	std::string new_prefix(prefix);
	if (!is_last) {
	new_prefix.append("\|").append(" ");
	} else {
	new_prefix.append(2, ' ');
	}
	return new_prefix;
	}

	private:
	DISALLOW_COPY_AND_ASSIGN(TreeStringSerializable);
	};

	/** @} */

	} // namespace quickstep

	#endif /* QUICKSTEP_UTILITY_TREE_STRING_SERIALIZABLE_HPP_ */