1 //
2 // Copyright 2016 Pixar
3 //
4 // Licensed under the Apache License, Version 2.0 (the "Apache License")
5 // with the following modification; you may not use this file except in
6 // compliance with the Apache License and the following modification to it:
7 // Section 6. Trademarks. is deleted and replaced with:
8 //
9 // 6. Trademarks. This License does not grant permission to use the trade
10 // names, trademarks, service marks, or product names of the Licensor
11 // and its affiliates, except as required to comply with Section 4(c) of
12 // the License and to reproduce the content of the NOTICE file.
13 //
14 // You may obtain a copy of the Apache License at
15 //
16 // http://www.apache.org/licenses/LICENSE-2.0
17 //
18 // Unless required by applicable law or agreed to in writing, software
19 // distributed under the Apache License with the above modification is
20 // distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
21 // KIND, either express or implied. See the Apache License for the specific
22 // language governing permissions and limitations under the Apache License.
23 //
24
25 #include "pxr/pxr.h"
26 #include "pxr/usd/pcp/mapExpression.h"
27 #include "pxr/usd/pcp/mapFunction.h"
28 #include "pxr/usd/pcp/layerStack.h"
29
30 #include "pxr/base/trace/trace.h"
31
32 #include <tbb/concurrent_hash_map.h>
33
34 PXR_NAMESPACE_OPEN_SCOPE
35
36 struct Pcp_VariableImpl;
37
38 // Add a mapping from </> to </> if the function does not already have one.
39 static PcpMapFunction
_AddRootIdentity(const PcpMapFunction & value)40 _AddRootIdentity(const PcpMapFunction &value)
41 {
42 if (value.HasRootIdentity()) {
43 // This function already maps </> to </>; use it as-is.
44 return value;
45 }
46 // Re-create the function with an added root identity mapping.
47 PcpMapFunction::PathMap sourceToTargetMap = value.GetSourceToTargetMap();
48 SdfPath const &absRoot = SdfPath::AbsoluteRootPath();
49 sourceToTargetMap[absRoot] = absRoot;
50 return PcpMapFunction::Create(sourceToTargetMap, value.GetTimeOffset());
51 }
52
53 ////////////////////////////////////////////////////////////////////////
54
PcpMapExpression()55 PcpMapExpression::PcpMapExpression()
56 {
57 }
58
59 bool
IsNull() const60 PcpMapExpression::IsNull() const
61 {
62 return !_node;
63 }
64
65 void
Swap(PcpMapExpression & other)66 PcpMapExpression::Swap(PcpMapExpression &other)
67 {
68 _node.swap(other._node);
69 }
70
71 const PcpMapExpression::Value &
Evaluate() const72 PcpMapExpression::Evaluate() const
73 {
74 static PcpMapExpression::Value defaultValue;
75 return _node ? _node->EvaluateAndCache() : defaultValue;
76 }
77
78 PcpMapExpression
Identity()79 PcpMapExpression::Identity()
80 {
81 static const PcpMapExpression val = Constant(PcpMapFunction::Identity());
82 return val;
83 }
84
85 PcpMapExpression
Constant(const Value & value)86 PcpMapExpression::Constant( const Value & value )
87 {
88 return PcpMapExpression( _Node::New(_OpConstant, _NodeRefPtr(),
89 _NodeRefPtr(), value) );
90 }
91
92 PcpMapExpression
Compose(const PcpMapExpression & f) const93 PcpMapExpression::Compose(const PcpMapExpression &f) const
94 {
95 // Fast path short-circuits for identities
96 if (IsConstantIdentity()) {
97 return f;
98 }
99 if (f.IsConstantIdentity()) {
100 return *this;
101 }
102 if (_node->key.op == _OpConstant && f._node->key.op == _OpConstant) {
103 // Apply constant folding
104 return Constant( Evaluate().Compose( f.Evaluate() ) );
105 }
106 return PcpMapExpression( _Node::New(_OpCompose, _node, f._node) );
107 }
108
109 PcpMapExpression
Inverse() const110 PcpMapExpression::Inverse() const
111 {
112 // Fast path short-circuits for identities
113 if (IsConstantIdentity()) {
114 return *this;
115 }
116 if (_node->key.op == _OpConstant) {
117 // Apply constant folding
118 return Constant( Evaluate().GetInverse() );
119 }
120 return PcpMapExpression( _Node::New(_OpInverse, _node) );
121 }
122
123 PcpMapExpression
AddRootIdentity() const124 PcpMapExpression::AddRootIdentity() const
125 {
126 // Fast path short-circuits for identities
127 if (IsConstantIdentity()) {
128 return *this;
129 }
130 if (_node->key.op == _OpConstant) {
131 // Apply constant folding
132 return Constant( _AddRootIdentity(Evaluate()) );
133 }
134 if (_node->expressionTreeAlwaysHasIdentity) {
135 return PcpMapExpression(_node);
136 }
137
138 return PcpMapExpression( _Node::New(_OpAddRootIdentity, _node) );
139 }
140
141 ////////////////////////////////////////////////////////////////////////
142 // Variable implementation
143
~Variable()144 PcpMapExpression::Variable::~Variable()
145 {
146 // Do nothing
147 }
148
149 // Private implementation for Variable.
150 struct Pcp_VariableImpl final : PcpMapExpression::Variable
151 {
~Pcp_VariableImplPcp_VariableImpl152 ~Pcp_VariableImpl() override {}
153
Pcp_VariableImplPcp_VariableImpl154 explicit Pcp_VariableImpl(PcpMapExpression::_NodeRefPtr &&node)
155 : _node(std::move(node)) {}
156
GetValuePcp_VariableImpl157 const PcpMapExpression::Value & GetValue() const override {
158 return _node->GetValueForVariable();
159 }
160
SetValuePcp_VariableImpl161 void SetValue(PcpMapExpression::Value && value) override {
162 _node->SetValueForVariable(std::move(value));
163 }
164
GetExpressionPcp_VariableImpl165 PcpMapExpression GetExpression() const override {
166 return PcpMapExpression(_node);
167 }
168
169 const PcpMapExpression::_NodeRefPtr _node;
170 };
171
172 PcpMapExpression::VariableUniquePtr
NewVariable(Value && initialValue)173 PcpMapExpression::NewVariable(Value && initialValue)
174 {
175 Pcp_VariableImpl *var = new Pcp_VariableImpl( _Node::New(_OpVariable) );
176
177 var->SetValue(std::move(initialValue));
178
179 return VariableUniquePtr(var);
180 }
181
182 ////////////////////////////////////////////////////////////////////////
183 // Node
184
185 namespace {
186
187 template <class Key>
188 struct _KeyHashEq
189 {
equal__anonf53d73f00111::_KeyHashEq190 inline bool equal(const Key &l, const Key &r) const { return l == r; }
hash__anonf53d73f00111::_KeyHashEq191 inline size_t hash(const Key &k) const { return k.GetHash(); }
192 };
193
194 } // anon
195
196 struct PcpMapExpression::_Node::_NodeMap
197 {
198 typedef PcpMapExpression::_Node::Key Key;
199 typedef tbb::concurrent_hash_map<
200 Key, PcpMapExpression::_Node *, _KeyHashEq<Key> > MapType;
201 typedef MapType::accessor accessor;
202 MapType map;
203 };
204
205 TfStaticData<PcpMapExpression::_Node::_NodeMap>
206 PcpMapExpression::_Node::_nodeRegistry;
207
208 bool
_ExpressionTreeAlwaysHasIdentity(const Key & key)209 PcpMapExpression::_Node::_ExpressionTreeAlwaysHasIdentity(const Key& key)
210 {
211 switch (key.op) {
212 case _OpAddRootIdentity:
213 return true;
214
215 case _OpVariable:
216 return false;
217
218 case _OpConstant:
219 {
220 // Check if this maps </> back to </> -- in which case this
221 // has a root identity mapping.
222 return key.valueForConstant.HasRootIdentity();
223 }
224
225 case _OpCompose:
226 // Composing two map expressions may cause the identity
227 // mapping to be removed; consider the case where we compose
228 // {</>:</>, </A>:</B>} and {</B>:</C>}. The expected result
229 // is {</A>:</C>}.
230 //
231 // In this case, the expression tree will only have an identity
232 // mapping if *both* subtrees being composed have an identity.
233 return (key.arg1 && key.arg1->expressionTreeAlwaysHasIdentity &&
234 key.arg2 && key.arg2->expressionTreeAlwaysHasIdentity);
235
236 default:
237 // For any other operation, if either of the subtrees has an
238 // identity mapping, so does this tree.
239 return (key.arg1 && key.arg1->expressionTreeAlwaysHasIdentity) ||
240 (key.arg2 && key.arg2->expressionTreeAlwaysHasIdentity);
241 }
242 }
243
244 PcpMapExpression::_NodeRefPtr
New(_Op op_,const _NodeRefPtr & arg1_,const _NodeRefPtr & arg2_,const Value & valueForConstant_)245 PcpMapExpression::_Node::New( _Op op_,
246 const _NodeRefPtr & arg1_,
247 const _NodeRefPtr & arg2_,
248 const Value & valueForConstant_ )
249 {
250 TfAutoMallocTag2 tag("Pcp", "PcpMapExpresion");
251 const Key key(op_, arg1_, arg2_, valueForConstant_);
252
253 if (key.op != _OpVariable) {
254 // Check for existing instance to re-use
255 _NodeMap::accessor accessor;
256 if (_nodeRegistry->map.insert(accessor, key) ||
257 accessor->second->_refCount.fetch_and_increment() == 0) {
258 // Either there was no node in the table, or there was but it had
259 // begun dying (another client dropped its refcount to 0). We have
260 // to create a new node in the table. When the client that is
261 // killing the other node it looks for itself in the table, it will
262 // either not find itself or will find a different node and so won't
263 // remove it.
264 _NodeRefPtr newNode(new _Node(key));
265 accessor->second = newNode.get();
266 return newNode;
267 }
268 return _NodeRefPtr(accessor->second, /*add_ref =*/ false);
269 }
270 return _NodeRefPtr(new _Node(key));
271 }
272
_Node(const Key & key_)273 PcpMapExpression::_Node::_Node( const Key & key_ )
274 : key(key_)
275 , expressionTreeAlwaysHasIdentity(_ExpressionTreeAlwaysHasIdentity(key))
276 {
277 _hasCachedValue = false;
278 _refCount = 0;
279 if (key.arg1) {
280 tbb::spin_mutex::scoped_lock lock(key.arg1->_mutex);
281 key.arg1->_dependentExpressions.insert(this);
282 }
283 if (key.arg2) {
284 tbb::spin_mutex::scoped_lock lock(key.arg2->_mutex);
285 key.arg2->_dependentExpressions.insert(this);
286 }
287 }
288
~_Node()289 PcpMapExpression::_Node::~_Node()
290 {
291 if (key.arg1) {
292 tbb::spin_mutex::scoped_lock lock(key.arg1->_mutex);
293 key.arg1->_dependentExpressions.erase(this);
294 }
295 if (key.arg2) {
296 tbb::spin_mutex::scoped_lock lock(key.arg2->_mutex);
297 key.arg2->_dependentExpressions.erase(this);
298 }
299
300 if (key.op != _OpVariable) {
301 // Remove from node map if present.
302 _NodeMap::accessor accessor;
303 if (_nodeRegistry->map.find(accessor, key) &&
304 accessor->second == this) {
305 _nodeRegistry->map.erase(accessor);
306 }
307 }
308 }
309
310 const PcpMapExpression::Value &
EvaluateAndCache() const311 PcpMapExpression::_Node::EvaluateAndCache() const
312 {
313 if (_hasCachedValue) {
314 return _cachedValue;
315 }
316
317 TRACE_SCOPE("PcpMapExpression::_Node::EvaluateAndCache - cache miss");
318 Value val = _EvaluateUncached();
319 tbb::spin_mutex::scoped_lock lock(_mutex);
320 if (!_hasCachedValue) {
321 _cachedValue = val;
322 _hasCachedValue = true;
323 }
324 return _cachedValue;
325 }
326
327 PcpMapExpression::Value
_EvaluateUncached() const328 PcpMapExpression::_Node::_EvaluateUncached() const
329 {
330 switch(key.op) {
331 case _OpConstant:
332 return key.valueForConstant;
333 case _OpVariable:
334 return _valueForVariable;
335 case _OpInverse:
336 return key.arg1->EvaluateAndCache().GetInverse();
337 case _OpCompose:
338 return key.arg1->EvaluateAndCache()
339 .Compose(key.arg2->EvaluateAndCache());
340 case _OpAddRootIdentity:
341 return _AddRootIdentity(key.arg1->EvaluateAndCache());
342 default:
343 TF_VERIFY(false, "unhandled case");
344 return PcpMapFunction();
345 }
346 }
347
348 void
_Invalidate()349 PcpMapExpression::_Node::_Invalidate()
350 {
351 // Caller must hold a lock on _mutex.
352 if (_hasCachedValue) {
353 _hasCachedValue = false;
354 _cachedValue = Value();
355 for (auto dep: _dependentExpressions) {
356 tbb::spin_mutex::scoped_lock lock(dep->_mutex);
357 dep->_Invalidate();
358 }
359 } else {
360 // This node is already invalid so dependent nodes are already invalid.
361 }
362 }
363
364 void
SetValueForVariable(Value && value)365 PcpMapExpression::_Node::SetValueForVariable(Value && value)
366 {
367 if (key.op != _OpVariable) {
368 TF_CODING_ERROR("Cannot set value for non-variable");
369 return;
370 }
371 tbb::spin_mutex::scoped_lock lock(_mutex);
372 if (_valueForVariable != value) {
373 _valueForVariable = std::move(value);
374 _Invalidate();
375 }
376 }
377
378 inline size_t
GetHash() const379 PcpMapExpression::_Node::Key::GetHash() const
380 {
381 size_t hash = op;
382 boost::hash_combine(hash, boost::get_pointer(arg1));
383 boost::hash_combine(hash, boost::get_pointer(arg2));
384 boost::hash_combine(hash, valueForConstant);
385 return hash;
386 }
387
388 bool
operator ==(const Key & key) const389 PcpMapExpression::_Node::Key::operator==(const Key &key) const
390 {
391 return op == key.op
392 && arg1 == key.arg1
393 && arg2 == key.arg2
394 && valueForConstant == key.valueForConstant;
395 }
396
397 void
intrusive_ptr_add_ref(PcpMapExpression::_Node * p)398 intrusive_ptr_add_ref(PcpMapExpression::_Node* p)
399 {
400 ++p->_refCount;
401 }
402
403 void
intrusive_ptr_release(PcpMapExpression::_Node * p)404 intrusive_ptr_release(PcpMapExpression::_Node* p)
405 {
406 if (p->_refCount.fetch_and_decrement() == 1)
407 delete p;
408 }
409
410 PXR_NAMESPACE_CLOSE_SCOPE
411