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 #ifndef PXR_USD_PCP_PRIM_INDEX_GRAPH_H 25 #define PXR_USD_PCP_PRIM_INDEX_GRAPH_H 26 27 #include "pxr/pxr.h" 28 #include "pxr/usd/pcp/iterator.h" 29 #include "pxr/usd/pcp/layerStack.h" 30 #include "pxr/usd/pcp/node.h" 31 #include "pxr/usd/pcp/mapExpression.h" 32 #include "pxr/usd/pcp/mapFunction.h" 33 #include "pxr/usd/pcp/types.h" 34 #include "pxr/usd/sdf/types.h" 35 36 #include "pxr/base/arch/attributes.h" 37 #include "pxr/base/tf/declarePtrs.h" 38 #include "pxr/base/tf/refBase.h" 39 #include "pxr/base/tf/weakBase.h" 40 41 #include <memory> 42 #include <utility> 43 #include <vector> 44 45 PXR_NAMESPACE_OPEN_SCOPE 46 47 class PcpArc; 48 class PcpLayerStackSite; 49 50 TF_DECLARE_WEAK_AND_REF_PTRS(PcpPrimIndex_Graph); 51 52 /// \class PcpPrimIndex_Graph 53 /// 54 /// Internal representation of the graph used to represent sources of 55 /// opinions in the prim index. 56 /// 57 class PcpPrimIndex_Graph 58 : public TfSimpleRefBase 59 , public TfWeakBase 60 { 61 public: 62 /// Creates a new graph with a root node for site \p rootSite. 63 static PcpPrimIndex_GraphRefPtr New(const PcpLayerStackSite& rootSite, 64 bool usd); 65 66 /// Creates a new graph that is a clone of \p rhs. 67 static PcpPrimIndex_GraphRefPtr New(const PcpPrimIndex_GraphPtr& rhs); 68 69 /// Returns true if this graph was created in USD mode. 70 bool IsUsd() const; 71 72 /// Get/set whether this prim index has an authored payload. 73 /// Note that it does not necessarily mean that the payload has been 74 /// loaded if this is set to true. 75 void SetHasPayloads(bool hasPayloads); 76 bool HasPayloads() const; 77 78 /// Get/set whether this prim index is instanceable. 79 void SetIsInstanceable(bool isInstanceable); 80 bool IsInstanceable() const; 81 82 /// Returns this graph's root node. This should always return a valid 83 /// node. 84 PcpNodeRef GetRootNode() const; 85 86 /// Returns the indexes of the nodes that encompass all direct child 87 /// nodes in the specified range as well as their descendants, in 88 /// strong-to-weak order. 89 /// 90 /// By default, this returns a range encompassing the entire graph. 91 std::pair<size_t, size_t> 92 GetNodeIndexesForRange(PcpRangeType rangeType = PcpRangeTypeAll) const; 93 94 /// Returns a node from the graph that uses the given site and can 95 /// contribute specs, if one exists. If multiple nodes in the graph 96 /// use the same site, the one that will be returned by this function 97 /// is undefined. 98 PcpNodeRef GetNodeUsingSite(const PcpLayerStackSite& site) const; 99 100 /// Appends the final element of \p childPath to each node's site path. 101 /// This takes the entire childPath as an optimization -- it's often the 102 /// case that the site paths are the parent path of childPath, in which case 103 /// we can just reuse childPath instead of reassembling a new matching path. 104 void AppendChildNameToAllSites(const SdfPath& childPath); 105 106 /// Inserts a new node with site \p site as a child of \p parentNode, 107 /// connected via \p arc. 108 /// Returns the newly-added child node. 109 /// If the new node would exceeed the graph capacity, an invalid 110 /// PcpNodeRef is returned. 111 PcpNodeRef InsertChildNode( 112 const PcpNodeRef& parentNode, 113 const PcpLayerStackSite& site, const PcpArc& arc, 114 PcpErrorBasePtr *error); 115 116 /// Inserts \p subgraph as a child of \p parentNode. The root node of 117 /// \p subgraph will be an immediate child of \p parentNode, connected via 118 /// \p arc. 119 /// Returns the root node of the newly-added subgraph. 120 /// If the new nodes would exceeed the graph capacity, an invalid 121 /// PcpNodeRef is returned. 122 PcpNodeRef InsertChildSubgraph( 123 const PcpNodeRef& parentNode, 124 const PcpPrimIndex_GraphPtr& subgraph, const PcpArc& arc, 125 PcpErrorBasePtr *error); 126 127 /// Finalizes the graph. This optimizes internal data structures and 128 /// should be called once the graph is fully generated. 129 void Finalize(); 130 131 /// Return true if the graph is in a finalized state. 132 bool IsFinalized() const; 133 134 /// Get the SdSite from compressed site \p site. GetSdSite(const Pcp_CompressedSdSite & site)135 SdfSite GetSdSite(const Pcp_CompressedSdSite& site) const 136 { 137 return SdfSite(_GetNode(site.nodeIndex). 138 layerStack->GetLayers()[site.layerIndex], 139 _nodeSitePaths[site.nodeIndex]); 140 } 141 142 /// Make an uncompressed site reference from compressed site \p site. GetSiteRef(const Pcp_CompressedSdSite & site)143 Pcp_SdSiteRef GetSiteRef(const Pcp_CompressedSdSite& site) const 144 { 145 return Pcp_SdSiteRef(_GetNode(site.nodeIndex). 146 layerStack->GetLayers()[site.layerIndex], 147 _nodeSitePaths[site.nodeIndex]); 148 } 149 150 /// Get a node from compressed site \p site. GetNode(const Pcp_CompressedSdSite & site)151 PcpNodeRef GetNode(const Pcp_CompressedSdSite& site) 152 { 153 TF_VERIFY(site.nodeIndex < _GetNumNodes()); 154 return PcpNodeRef(this, site.nodeIndex); 155 } 156 157 private: 158 // Forward declarations for internal data structures. 159 struct _Arc; 160 struct _ArcStrengthOrder; 161 struct _Node; 162 163 // Private constructors -- use New instead. 164 PcpPrimIndex_Graph(const PcpLayerStackSite& rootSite, bool usd); 165 PcpPrimIndex_Graph(const PcpPrimIndex_Graph& rhs); 166 167 size_t _CreateNode( 168 const PcpLayerStackSite& site, const PcpArc& arc); 169 size_t _CreateNodesForSubgraph( 170 const PcpPrimIndex_Graph& subgraph, const PcpArc& arc); 171 172 PcpNodeRef _InsertChildInStrengthOrder( 173 size_t parentNodeIdx, size_t childNodeIdx); 174 175 void _DetachSharedNodePool(); 176 177 // Iterates through the immediate children of the root node looking 178 // for the first node for which p(node) is true and the first subsequent 179 // node where p(node) is false. Returns the indexes of the resulting 180 // nodes. 181 template <class Predicate> 182 std::pair<size_t, size_t> _FindRootChildRange(const Predicate& p) const; 183 184 // Helper functions to compute a mapping between node indexes and 185 // the strength order of the corresponding node. 186 // 187 // Returns: 188 // True if the order of nodes in the node pool is the same as strength 189 // ordering, false otherwise. 190 // 191 // nodeIndexToStrengthOrder[i] => strength order of node at index i. 192 bool _ComputeStrengthOrderIndexMapping( 193 std::vector<size_t>* nodeIndexToStrengthOrder) const; 194 bool _ComputeStrengthOrderIndexMappingRecursively( 195 size_t nodeIdx, size_t* strengthIdx, 196 std::vector<size_t>* nodeIndexToStrengthOrder) const; 197 198 // Helper function to compute a node index mapping that erases nodes 199 // that have been marked for culling. 200 // 201 // Returns: 202 // True if any nodes marked for culling can be erased, false otherwise. 203 // culledNodeMapping[i] => index of node i after culled nodes are erased. 204 bool _ComputeEraseCulledNodeIndexMapping( 205 std::vector<size_t>* culledNodeMapping) const; 206 207 // Transforms the node pool by applying the given node index mapping. 208 // References to to other nodes in the pool are fixed up appropriately. 209 // 210 // \p nodeIndexMap is a vector of the same size as the node pool, where 211 // \p nodeIndexMap[i] => new position of node i. 212 // If \p nodeIndexMap[i] == _invalidNodeIndex, that node will be erased. 213 void _ApplyNodeIndexMapping(const std::vector<size_t>& nodeIndexMap); 214 215 private: 216 // PcpNodeRef is allowed to reach directly into the node pool to get/set 217 // data. 218 friend class PcpNodeRef; 219 friend class PcpNodeRef_ChildrenIterator; 220 friend class PcpNodeRef_ChildrenReverseIterator; 221 friend class PcpNodeRef_PrivateChildrenConstIterator; 222 friend class PcpNodeRef_PrivateChildrenConstReverseIterator; 223 224 // NOTE: These accessors assume the consumer will be changing the node 225 // and may cause shared node data to be copied locally. 226 _Node& _GetWriteableNode(size_t idx); 227 _Node& _GetWriteableNode(const PcpNodeRef& node); 228 _GetNumNodes()229 size_t _GetNumNodes() const 230 { 231 return _data->nodes.size(); 232 } 233 _GetNode(size_t idx)234 const _Node& _GetNode(size_t idx) const 235 { 236 TF_VERIFY(idx < _GetNumNodes()); 237 return _data->nodes[idx]; 238 } _GetNode(const PcpNodeRef & node)239 const _Node& _GetNode(const PcpNodeRef& node) const 240 { 241 return _GetNode(node._GetNodeIndex()); 242 } 243 244 private: 245 // Allow Pcp_Statistics access to internal data for diagnostics. 246 friend class Pcp_Statistics; 247 248 struct _Node { 249 static const size_t _nodeIndexSize = 15; 250 static const size_t _childrenSize = 10; 251 static const size_t _depthSize = 10; 252 // These types should be just large enough to hold the above sizes. 253 // This allows this structure to be packed into less space. 254 typedef unsigned short _NodeIndexType; 255 typedef unsigned short _ChildrenSizeType; 256 typedef unsigned short _DepthSizeType; 257 258 // Index used to represent an invalid node. 259 static const size_t _invalidNodeIndex = (1lu << _nodeIndexSize) - 1lu; 260 _Node_Node261 _Node() 262 /* The equivalent initializations to the memset(). 263 , permission(SdfPermissionPublic) 264 , hasSymmetry(false) 265 , inert(false) 266 , culled(false) 267 , permissionDenied(false) 268 , arcType(PcpArcTypeRoot) 269 , arcSiblingNumAtOrigin(0) 270 , arcNamespaceDepth(0) 271 , arcParentIndex(0) 272 , arcOriginIndex(0) 273 */ 274 { 275 memset(&smallInts, 0, sizeof(smallInts)); 276 smallInts.arcParentIndex = _invalidNodeIndex; 277 smallInts.arcOriginIndex = _invalidNodeIndex; 278 smallInts.firstChildIndex = _invalidNodeIndex; 279 smallInts.lastChildIndex = _invalidNodeIndex; 280 smallInts.prevSiblingIndex = _invalidNodeIndex; 281 smallInts.nextSiblingIndex = _invalidNodeIndex; 282 } 283 Swap_Node284 void Swap(_Node& rhs) 285 { 286 std::swap(layerStack, rhs.layerStack); 287 mapToRoot.Swap(rhs.mapToRoot); 288 mapToParent.Swap(rhs.mapToParent); 289 std::swap(smallInts, rhs.smallInts); 290 } 291 292 void SetArc(const PcpArc& arc); 293 294 // NOTE: We pack all info into _Node, including stuff that 295 // would reasonably encapsulate in other types like 296 // info about the arc to the parent, so we can lay 297 // out the data in memory as tightly as possible. 298 299 // The layer stack for this node. 300 PcpLayerStackRefPtr layerStack; 301 // Mapping function used to translate from this node directly 302 // to the root node. This is essentially the composition of the 303 // mapToParent for every arc between this node and the root. 304 PcpMapExpression mapToRoot; 305 // The value-mapping function used to map values from this arc's source 306 // node to its parent node. 307 PcpMapExpression mapToParent; 308 // Pack the non-byte sized integers into an unnamed structure. 309 // This allows us to initialize them all at once. g++ will, 310 // surprisingly, initialize each individually in the default 311 // copy constructor if they're direct members of _Node. 312 struct _SmallInts { 313 // The permissions for this node (whether specs on this node 314 // can be accessed from other nodes). 315 SdfPermission permission:2; 316 // Whether this node contributes symmetry information to 317 // composition. This implies that prims at this node's site 318 // or at any of its namespace ancestors contain symmetry 319 // information. 320 bool hasSymmetry:1; 321 // Whether this node is inert. This is set to true in cases 322 // where a node is needed to represent a structural dependency 323 // but no opinions are allowed to be added. 324 bool inert:1; 325 // Whether this node was culled. This implies that no opinions 326 // exist at this node and all child nodes. Because of this, 327 // prim indexing does not need to expand this node to look for 328 // other arcs. 329 bool culled:1; 330 // Whether this node is in violation of permission settings. 331 // This is set to true when: we arrive at this node from a 332 // node that was marked \c SdfPermissionPrivate, or we arrive 333 // at this node from another node that was denied permission. 334 bool permissionDenied:1; 335 // The type of the arc to the parent node. We only need 4 336 // bits but we use 5 to avoid signed/unsigned issues. 337 PcpArcType arcType:5; 338 // Index among sibling arcs at origin; lower is stronger 339 _ChildrenSizeType arcSiblingNumAtOrigin:_childrenSize; 340 // Absolute depth in namespace of node that introduced this 341 // node. Note that this does *not* count any variant 342 // selections. 343 _DepthSizeType arcNamespaceDepth:_depthSize; 344 345 // The following are padded to word size to avoid needing to 346 // bit shift for read/write access and having to access two 347 // words to read a value that straddles two machine words. 348 // Note that bitfield layout should be examined when any 349 // field is added, removed, or resized. 350 351 // The index of the parent (or target) node of this arc. 352 _NodeIndexType:0; 353 _NodeIndexType arcParentIndex:_nodeIndexSize; 354 // The index of the origin node of this arc. 355 _NodeIndexType:0; 356 _NodeIndexType arcOriginIndex:_nodeIndexSize; 357 358 // The indexes of the first/last child, previous/next sibling. 359 // The previous sibling index of a first child and the next 360 // sibling index of a last child are _invalidNodeIndex (i.e. 361 // they form a list, not a ring). 362 _NodeIndexType:0; 363 _NodeIndexType firstChildIndex:_nodeIndexSize; 364 _NodeIndexType:0; 365 _NodeIndexType lastChildIndex:_nodeIndexSize; 366 _NodeIndexType:0; 367 _NodeIndexType prevSiblingIndex:_nodeIndexSize; 368 _NodeIndexType:0; 369 _NodeIndexType nextSiblingIndex:_nodeIndexSize; 370 } 371 // Make this structure as small as possible. 372 #if defined(ARCH_COMPILER_GCC) || defined(ARCH_COMPILER_CLANG) 373 __attribute__((packed)) 374 #endif 375 ; 376 _SmallInts smallInts; 377 }; 378 379 typedef std::vector<_Node> _NodePool; 380 381 struct _SharedData { _SharedData_SharedData382 _SharedData(bool usd_) 383 : finalized(false) 384 , usd(usd_) 385 , hasPayloads(false) 386 , instanceable(false) 387 { } 388 389 // Pool of nodes for this graph. 390 _NodePool nodes; 391 392 // Whether this node pool has been finalized. 393 bool finalized:1; 394 // Whether this prim index is composed in USD mode. 395 bool usd:1; 396 // Whether this prim index has authored payloads. 397 bool hasPayloads:1; 398 // Whether this prim index is instanceable. 399 bool instanceable:1; 400 }; 401 402 // Container of graph data. PcpPrimIndex_Graph implements a 403 // copy-on-write scheme, so this data may be shared among multiple graph 404 // instances. 405 std::shared_ptr<_SharedData> _data; 406 407 // The following data is not included in the shared data object above 408 // because they will typically differ between graph instances. Including 409 // them in the shared data object would cause more graph instances to 410 // be created. 411 412 // Site paths for each node. Elements in this vector correspond to nodes 413 // in the shared node pool. Together, _data->nodes[i].layerStack and 414 // _nodeSitePaths[i] form a node's site. 415 std::vector<SdfPath> _nodeSitePaths; 416 417 // Flags indicating whether a particular node has any specs to contribute 418 // to the composed prim. Elements in this vector correspond to nodes in 419 // the shared node pool. 420 std::vector<bool> _nodeHasSpecs; 421 }; 422 423 PXR_NAMESPACE_CLOSE_SCOPE 424 425 #endif // PXR_USD_PCP_PRIM_INDEX_GRAPH_H 426