tvm_ffi/extra/structural_eq_hash.rs
1/*
2 * Licensed to the Apache Software Foundation (ASF) under one
3 * or more contributor license agreements. See the NOTICE file
4 * distributed with this work for additional information
5 * regarding copyright ownership. The ASF licenses this file
6 * to you under the Apache License, Version 2.0 (the
7 * "License"); you may not use this file except in compliance
8 * with the License. You may obtain a copy of the License at
9 *
10 * http://www.apache.org/licenses/LICENSE-2.0
11 *
12 * Unless required by applicable law or agreed to in writing,
13 * software distributed under the License is distributed on an
14 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15 * KIND, either express or implied. See the License for the
16 * specific language governing permissions and limitations
17 * under the License.
18 */
19//! Structural equality and hashing of values.
20
21use crate::reflection::AccessPath;
22use crate::{AnyView, Array, Result};
23
24/// Options of structural equality and hashing.
25///
26/// See also [`structural_equal_with`], [`structural_hash_with`] and
27/// [`get_first_structural_mismatch_with`].
28#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
29pub struct StructuralOptions {
30 /// Whether free variables (variables without a definition site) can be
31 /// mapped to each other.
32 pub map_free_vars: bool,
33 /// Whether to skip the data content of tensors.
34 pub skip_tensor_content: bool,
35}
36
37/// Whether two values are structurally equal: they have the same structure
38/// and content, compared recursively through containers and reflected
39/// fields, not by identity.
40///
41/// Objects compare as their [`SEqHashKind`](crate::reflection::SEqHashKind) declares.
42///
43/// # Arguments
44///
45/// * `lhs` - The left value.
46/// * `rhs` - The right value.
47///
48/// # Returns
49///
50/// Whether the values are structurally equal.
51///
52/// # Errors
53///
54/// Returns an error if an object in either value does not support structural
55/// equality.
56///
57/// # Examples
58///
59/// ```standalone_crate
60/// use tvm_ffi::derive::ObjectRef;
61/// use tvm_ffi::{rs_object, structural_equal, Array, Object, ObjectArc};
62///
63/// #[rs_object(type_key = "my_ext.MyPair", final, s_eq_hash_kind = "TreeNode")]
64/// pub struct MyPairObj {
65/// base_: Object,
66/// pub first: i64,
67/// pub second: Array<i64>,
68/// }
69///
70/// #[derive(Clone, ObjectRef)]
71/// pub struct MyPair {
72/// data: ObjectArc<MyPairObj>,
73/// }
74///
75/// let pair = |second: Vec<i64>| {
76/// MyPair::from_object(MyPairObj::new(Object::new(), 1, Array::from_vec(second)))
77/// };
78/// assert!(structural_equal(&pair(vec![2, 3]), &pair(vec![2, 3]))?);
79/// assert!(!structural_equal(&pair(vec![2, 3]), &pair(vec![2, 4]))?);
80/// # Ok::<(), tvm_ffi::Error>(())
81/// ```
82pub fn structural_equal<'l, 'r>(
83 lhs: impl Into<AnyView<'l>>,
84 rhs: impl Into<AnyView<'r>>,
85) -> Result<bool> {
86 structural_equal_with(lhs, rhs, StructuralOptions::default())
87}
88
89/// As [`structural_equal`], with [`StructuralOptions`].
90pub fn structural_equal_with<'l, 'r>(
91 lhs: impl Into<AnyView<'l>>,
92 rhs: impl Into<AnyView<'r>>,
93 options: StructuralOptions,
94) -> Result<bool> {
95 let args = [
96 lhs.into(),
97 rhs.into(),
98 AnyView::from(&options.map_free_vars),
99 AnyView::from(&options.skip_tensor_content),
100 ];
101 crate::cached_global_func!("ffi.StructuralEqual")
102 .call_packed(&args)?
103 .try_into()
104}
105
106/// The structural hash of a value, consistent with [`structural_equal`]:
107/// structurally equal values have the same hash.
108///
109/// # Arguments
110///
111/// * `value` - The value to hash.
112///
113/// # Returns
114///
115/// The hash.
116///
117/// # Errors
118///
119/// Returns an error if an object in the value does not support structural
120/// hashing.
121///
122/// See also [`structural_equal`].
123pub fn structural_hash<'a>(value: impl Into<AnyView<'a>>) -> Result<u64> {
124 structural_hash_with(value, StructuralOptions::default())
125}
126
127/// As [`structural_hash`], with [`StructuralOptions`].
128pub fn structural_hash_with<'a>(
129 value: impl Into<AnyView<'a>>,
130 options: StructuralOptions,
131) -> Result<u64> {
132 let args = [
133 value.into(),
134 AnyView::from(&options.map_free_vars),
135 AnyView::from(&options.skip_tensor_content),
136 ];
137 let hash: i64 = crate::cached_global_func!("ffi.StructuralHash")
138 .call_packed(&args)?
139 .try_into()?;
140 // The hash crosses the ABI as an `i64` bit pattern.
141 Ok(hash as u64)
142}
143
144/// The first place where two values are not structurally equal, as the
145/// [`AccessPath`] of that place in each value.
146///
147/// # Arguments
148///
149/// * `lhs` - The left value.
150/// * `rhs` - The right value.
151///
152/// # Returns
153///
154/// `None` if the values are structurally equal, else the paths of the first
155/// mismatch in `lhs` and in `rhs`.
156///
157/// # Errors
158///
159/// Returns an error if an object in either value does not support structural
160/// equality.
161///
162/// See also [`structural_equal`].
163pub fn get_first_structural_mismatch<'l, 'r>(
164 lhs: impl Into<AnyView<'l>>,
165 rhs: impl Into<AnyView<'r>>,
166) -> Result<Option<(AccessPath, AccessPath)>> {
167 get_first_structural_mismatch_with(lhs, rhs, StructuralOptions::default())
168}
169
170/// As [`get_first_structural_mismatch`], with [`StructuralOptions`].
171pub fn get_first_structural_mismatch_with<'l, 'r>(
172 lhs: impl Into<AnyView<'l>>,
173 rhs: impl Into<AnyView<'r>>,
174 options: StructuralOptions,
175) -> Result<Option<(AccessPath, AccessPath)>> {
176 let args = [
177 lhs.into(),
178 rhs.into(),
179 AnyView::from(&options.map_free_vars),
180 AnyView::from(&options.skip_tensor_content),
181 ];
182 // The pair crosses the ABI as a two-item array.
183 let pair: Option<Array<AccessPath>> =
184 crate::cached_global_func!("ffi.GetFirstStructuralMismatch")
185 .call_packed(&args)?
186 .try_into()?;
187 Ok(pair.map(|pair| (pair[0].clone(), pair[1].clone())))
188}