lriggs commented on code in PR #55608:
URL: https://github.com/apache/arrow/pull/55608#discussion_r4605111079


##########
cpp/src/gandiva/expression_cache_key.h:
##########
@@ -19,17 +19,295 @@
 
 #include <stddef.h>
 
+#include <algorithm>
+#include <string>
 #include <thread>
+#include <type_traits>
+#include <unordered_map>
+#include <vector>
 
 #include "arrow/util/hash_util.h"
 #include "gandiva/arrow.h"
 #include "gandiva/configuration.h"
 #include "gandiva/expression.h"
+#include "gandiva/node.h"
 #include "gandiva/selection_vector.h"
 #include "gandiva/visibility.h"
 
 namespace gandiva {
 
+namespace internal {
+
+// Debug strings are ambiguous when literal values or field names contain 
expression
+// syntax. Encode the tree in a compact binary form that has one possible 
parse: every
+// node starts with a one byte tag, variable size tokens carry their length, 
and child
+// lists carry their count. Keys are process-local, so values are stored as 
raw bytes.
+//
+// Repeated types and names are written in full once per expression and as a 
short
+// reference after that. A reference points at the n-th definition in the same 
key, so
+// it stays unambiguous. Types are compared by their fingerprint, not by 
pointer, so two
+// separately built `decimal128(10, 2)` still give the same key.
+//
+// The return type of a node is written only when the node does not already 
fix it:
+// a field node has the type of its field, and boolean and IN nodes are always 
boolean.
+// This runs before validation, and a cache hit skips validation, so the key 
has to tell
+// apart every expression that validation could tell apart. Null nodes and 
types must
+// be safe.
+class ExpressionKeyVisitor : public NodeVisitor {
+ public:
+  std::string MakeKey(const Expression* expression, const char* kind) {
+    key_.clear();
+    type_by_pointer_.clear();
+    type_by_definition_.clear();
+    name_index_.clear();
+    has_like_ = false;
+
+    AppendBytes(&key_, kind);
+    if (!expression) {
+      key_ += kNullExpression;
+      return key_;
+    }
+    key_ += kExpression;
+    if (expression->result()) {
+      key_ += kResult;
+      AppendType(expression->result()->type());
+    } else {
+      key_ += kNullResult;
+    }
+    AppendNode(expression->root());
+    return key_;
+  }
+
+  bool has_like() const { return has_like_; }
+
+  Status Visit(const FieldNode& node) override {
+    key_ += kFieldNode;
+    AppendField(node.field());
+    return Status::OK();
+  }
+
+  Status Visit(const FunctionNode& node) override {
+    key_ += kFunctionNode;
+    AppendType(node.return_type());
+    AppendName(node.descriptor()->name());
+    has_like_ |= node.descriptor()->name() == "like";
+    AppendNodes(node.children());
+    return Status::OK();
+  }
+
+  Status Visit(const IfNode& node) override {
+    key_ += kIfNode;
+    AppendType(node.return_type());
+    AppendNode(node.condition());
+    AppendNode(node.then_node());
+    AppendNode(node.else_node());
+    return Status::OK();
+  }
+
+  Status Visit(const LiteralNode& node) override {
+    key_ += kLiteralNode;
+    AppendType(node.return_type());
+    key_ += node.is_null() ? kNullLiteral : kValueLiteral;
+    // The variant index fixes how many bytes follow, so values need no length.
+    key_ += static_cast<char>(node.holder().index());
+    std::visit([this](const auto& value) { AppendValue(&key_, value); }, 
node.holder());
+    return Status::OK();
+  }
+
+  Status Visit(const BooleanNode& node) override {
+    key_ += kBooleanNode;
+    key_ += static_cast<char>(node.expr_type());
+    AppendNodes(node.children());
+    return Status::OK();
+  }
+
+  Status Visit(const InExpressionNode<int32_t>& node) override {
+    return AppendIn(node, 'a');
+  }
+  Status Visit(const InExpressionNode<int64_t>& node) override {
+    return AppendIn(node, 'b');
+  }
+  Status Visit(const InExpressionNode<float>& node) override {
+    return AppendIn(node, 'c');
+  }
+  Status Visit(const InExpressionNode<double>& node) override {
+    return AppendIn(node, 'd');
+  }
+  Status Visit(const InExpressionNode<std::string>& node) override {
+    return AppendIn(node, 's');
+  }
+
+  Status Visit(const InExpressionNode<DecimalScalar128>& node) override {
+    key_ += kInNode;
+    key_ += 'D';
+    AppendVarint(&key_, static_cast<uint64_t>(node.get_precision()));
+    AppendVarint(&key_, static_cast<uint64_t>(node.get_scale()));
+    return AppendInValues(node);
+  }
+
+ private:
+  static constexpr char kNullExpression = 'X';
+  static constexpr char kExpression = 'E';
+  static constexpr char kResult = 'R';
+  static constexpr char kNullResult = 'r';
+  static constexpr char kNullNode = 'z';
+  static constexpr char kFieldNode = 'f';
+  static constexpr char kFunctionNode = 'c';
+  static constexpr char kIfNode = 'i';
+  static constexpr char kLiteralNode = 'l';
+  static constexpr char kBooleanNode = 'b';
+  static constexpr char kInNode = 'I';
+  static constexpr char kNullLiteral = 'n';
+  static constexpr char kValueLiteral = 'v';
+  static constexpr char kNullType = 'N';
+  static constexpr char kTypeDefinition = 'T';
+  static constexpr char kTypeReference = 't';
+  static constexpr char kNullField = 'Z';
+  static constexpr char kField = 'F';
+  static constexpr char kNullable = '1';
+  static constexpr char kNonNullable = '0';
+  static constexpr char kNameDefinition = 'M';
+  static constexpr char kNameReference = 'm';
+
+  static void AppendVarint(std::string* out, uint64_t value) {
+    while (value >= 0x80) {
+      out->push_back(static_cast<char>(value | 0x80));
+      value >>= 7;
+    }
+    out->push_back(static_cast<char>(value));
+  }
+
+  static void AppendBytes(std::string* out, const std::string& value) {
+    AppendVarint(out, value.size());
+    out->append(value);
+  }
+
+  template <typename T>
+  static void AppendValue(std::string* out, const T& value) {
+    static_assert(std::is_arithmetic_v<T>);
+    // Preserve exact numeric bytes, including float NaN payloads and signed 
zero,
+    // without decimal formatting or rounding.
+    out->append(reinterpret_cast<const char*>(&value), sizeof(value));
+  }
+
+  static void AppendValue(std::string* out, const std::string& value) {
+    AppendBytes(out, value);
+  }
+
+  static void AppendValue(std::string* out, const DecimalScalar128& value) {
+    AppendValue(out, value.value().high_bits());
+    AppendValue(out, value.value().low_bits());
+    AppendValue(out, value.precision());
+    AppendValue(out, value.scale());
+  }
+
+  void AppendType(const DataTypePtr& type) {

Review Comment:
   I dont feel strongly about this though. It just seems fairly complex and 
simplifying it seems good.



-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

To unsubscribe, e-mail: [email protected]

For queries about this service, please contact Infrastructure at:
[email protected]

Reply via email to