gemini-code-assist[bot] commented on code in PR #438: URL: https://github.com/apache/tvm-ffi/pull/438#discussion_r2780848777
########## src/ffi/extra/copy.cc: ########## @@ -0,0 +1,293 @@ +/* + * 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. + */ +/* + * \file src/ffi/extra/copy.cc + * + * \brief Reflection-based deep copy utilities. + */ +#include <tvm/ffi/any.h> +#include <tvm/ffi/container/array.h> +#include <tvm/ffi/container/map.h> +#include <tvm/ffi/container/shape.h> +#include <tvm/ffi/error.h> +#include <tvm/ffi/extra/copy.h> +#include <tvm/ffi/reflection/accessor.h> +#include <tvm/ffi/reflection/registry.h> + +#include <stack> +#include <unordered_map> +#include <unordered_set> +#include <vector> + +namespace tvm { +namespace ffi { + +/*! + * \brief Deep copier that recursively copies objects using shallow copy + field replacement. + * + * Algorithm: + * Phase 1: Walk the entire object graph (objects, arrays, maps) using an explicit + * stack, collecting all reachable nodes in topological order (post-order DFS). + * An unordered_set deduplicates nodes, preserving shared references. + * Phase 2: In two sub-passes: + * (a) Create shallow copies of all copyable objects first, so that + * back-references in cyclic object graphs resolve correctly. + * (b) Create deep-copied arrays/maps with resolved elements, and + * resolve fields of copyable objects with previously copied values. Review Comment:  The documentation for Phase 2 of the deep copy algorithm mentions two sub-passes, but the implementation in `CopyNodesInOrder` actually uses three distinct sub-passes. The comment within `CopyNodesInOrder` correctly describes these three passes. To improve clarity and consistency, the main class-level documentation should be updated to reflect the three-pass approach. ```suggestion * Phase 2: In three sub-passes: * (a) Create shallow copies of all copyable objects. This allows * back-references in cyclic graphs to be resolved correctly. * (b) Create deep copies of arrays and maps. Their elements are * resolved to their copied versions from sub-pass (a). * (c) Resolve fields of the shallow-copied objects from (a) to point * to their deep-copied versions from (a) and (b). ``` ########## src/ffi/extra/copy.cc: ########## @@ -0,0 +1,293 @@ +/* + * 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. + */ +/* + * \file src/ffi/extra/copy.cc + * + * \brief Reflection-based deep copy utilities. + */ +#include <tvm/ffi/any.h> +#include <tvm/ffi/container/array.h> +#include <tvm/ffi/container/map.h> +#include <tvm/ffi/container/shape.h> +#include <tvm/ffi/error.h> +#include <tvm/ffi/extra/copy.h> +#include <tvm/ffi/reflection/accessor.h> +#include <tvm/ffi/reflection/registry.h> + +#include <stack> +#include <unordered_map> +#include <unordered_set> +#include <vector> + +namespace tvm { +namespace ffi { + +/*! + * \brief Deep copier that recursively copies objects using shallow copy + field replacement. + * + * Algorithm: + * Phase 1: Walk the entire object graph (objects, arrays, maps) using an explicit + * stack, collecting all reachable nodes in topological order (post-order DFS). + * An unordered_set deduplicates nodes, preserving shared references. + * Phase 2: In two sub-passes: + * (a) Create shallow copies of all copyable objects first, so that + * back-references in cyclic object graphs resolve correctly. + * (b) Create deep-copied arrays/maps with resolved elements, and + * resolve fields of copyable objects with previously copied values. + * + * Primitive types, strings, bytes, and functions are immutable and returned as-is. + * Arrays and Maps are recursively copied (their elements are replaced with copies). + * Shared references (including shared containers) are preserved in the copy graph. + * Objects without enable_copy() are kept as shared references. + */ +class ObjectDeepCopier { + public: + static Any DeepCopy(const Any& root) { + ObjectDeepCopier copier; + // Phase 1: Collect all reachable nodes in topological order + copier.CollectNodes(root); + // Phase 2: Copy nodes in topological order + copier.CopyNodesInOrder(); + // Phase 3: Resolve the root value with copies + return copier.ResolveValue(root); + } + + private: + struct DFSFrame { + const Object* obj; + bool children_pushed; + }; + + // The type attribute column for looking up per-type shallow copy functions + static reflection::TypeAttrColumn& ShallowCopyColumn() { + static reflection::TypeAttrColumn column("__ffi_shallow_copy__"); + return column; + } + + // Map from original object pointer to its copy + std::unordered_map<const Object*, ObjectRef> copy_map_; + // Topological order of nodes to copy (post-order, leaves first) + std::vector<const Object*> topo_order_; + // Set of visited object pointers for deduplication + std::unordered_set<const Object*> visited_; + // Original Any values keyed by Object pointer (for typed container access) + std::unordered_map<const Object*, Any> originals_; + + /*! + * \brief Extract the Object pointer from an Any value. + * \return The Object pointer, or nullptr if the value is not an object/array/map. + */ + static const Object* AsObjectPtr(const Any& value) { + int32_t ti = value.type_index(); + if (ti == TypeIndex::kTVMFFIArray || ti == TypeIndex::kTVMFFIMap || + ti >= TypeIndex::kTVMFFIStaticObjectBegin) { + return details::AnyUnsafe::CopyFromAnyViewAfterCheck<const Object*>(value); + } + return nullptr; + } + + /*! + * \brief Phase 1: Walk the object graph iteratively, collecting all reachable nodes + * (objects, arrays, maps) in topological order (post-order DFS). + */ + void CollectNodes(const Any& root) { + const Object* root_obj = AsObjectPtr(root); + if (root_obj == nullptr) return; + originals_.emplace(root_obj, root); + + std::stack<DFSFrame> stack; + stack.push({root_obj, false}); + + while (!stack.empty()) { + DFSFrame& frame = stack.top(); + + if (frame.children_pushed) { + // All children processed, add this node in post-order + topo_order_.push_back(frame.obj); + stack.pop(); + continue; + } + + frame.children_pushed = true; + + // Dedup at process time (not push time) to ensure correct topological order + // when multiple parents share the same child node. + if (!visited_.insert(frame.obj).second) { + stack.pop(); + continue; + } + + int32_t ti = frame.obj->type_index(); + + if (ti == TypeIndex::kTVMFFIArray) { + // Push array elements as children + Array<Any> arr = + details::AnyUnsafe::CopyFromAnyViewAfterCheck<Array<Any>>(originals_[frame.obj]); + for (const Any& elem : arr) { + PushChild(elem, stack); + } + } else if (ti == TypeIndex::kTVMFFIMap) { + // Push map keys and values as children + Map<Any, Any> m = + details::AnyUnsafe::CopyFromAnyViewAfterCheck<Map<Any, Any>>(originals_[frame.obj]); + for (const auto& [k, v] : m) { + PushChild(k, stack); + PushChild(v, stack); + } + } else if (ShallowCopyColumn()[ti] != nullptr) { + // Copyable object - push field children + const TVMFFITypeInfo* type_info = TVMFFIGetTypeInfo(ti); + if (type_info->metadata != nullptr) { + reflection::ForEachFieldInfo(type_info, [&](const TVMFFIFieldInfo* field_info) { + int32_t sti = field_info->field_static_type_index; + if (sti >= TypeIndex::kTVMFFIStaticObjectBegin || sti == TypeIndex::kTVMFFIAny || + sti == TypeIndex::kTVMFFIArray || sti == TypeIndex::kTVMFFIMap) { + reflection::FieldGetter getter(field_info); + Any field_value = getter(frame.obj); + PushChild(field_value, stack); + } + }); + } + } else { + // No copy support - add to topo_order, skip children + topo_order_.push_back(frame.obj); + stack.pop(); + continue; + } + } + } + + /*! + * \brief Push a child node onto the DFS stack if not yet visited. + * + * Uses find() rather than insert() so that nodes still on the stack + * (pushed but not yet processed) can be pushed again from a different + * parent. The duplicate is processed first (LIFO) and the original + * frame is later skipped by the visited_ check in CollectNodes. + * This ensures correct topological order for shared dependencies. + */ Review Comment:  The comment for `PushChild` is a bit confusing as it seems to describe a different DFS strategy than what is implemented. The current implementation is a correct iterative post-order DFS where `visited_` tracks nodes whose expansion has started. The comment could be clarified to more accurately reflect the behavior of the code, which is to avoid pushing already-visited nodes onto the stack. ```c * rief Push a child node onto the DFS stack if it hasn't been visited. * * A node is considered "visited" once its processing begins in `CollectNodes` * (i.e., it is added to the `visited_` set). This check prevents adding * already-processed nodes to the stack, which is crucial for correctness * in graphs with shared dependencies and cycles. */ ``` -- 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] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
