All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
primIndex_Graph.h
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 PCP_PRIM_INDEX_GRAPH_H
25 #define 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 
57 class PcpPrimIndex_Graph
58  : public TfSimpleRefBase
59  , public TfWeakBase
60 {
61 public:
63  static PcpPrimIndex_GraphRefPtr New(const PcpLayerStackSite& rootSite,
64  bool usd);
65 
67  static PcpPrimIndex_GraphRefPtr New(const PcpPrimIndex_GraphPtr& rhs);
68 
70  bool IsUsd() const;
71 
75  void SetHasPayloads(bool hasPayloads);
76  bool HasPayloads() const;
77 
79  void SetIsInstanceable(bool isInstanceable);
80  bool IsInstanceable() const;
81 
84  PcpNodeRef GetRootNode() const;
85 
91  std::pair<size_t, size_t>
92  GetNodeIndexesForRange(PcpRangeType rangeType = PcpRangeTypeAll) const;
93 
98  PcpNodeRef GetNodeUsingSite(const PcpLayerStackSite& site) const;
99 
104  void AppendChildNameToAllSites(const SdfPath& childPath);
105 
109  PcpNodeRef InsertChildNode(
110  const PcpNodeRef& parentNode,
111  const PcpLayerStackSite& site, const PcpArc& arc);
112 
117  PcpNodeRef InsertChildSubgraph(
118  const PcpNodeRef& parentNode,
119  const PcpPrimIndex_GraphPtr& subgraph, const PcpArc& arc);
120 
123  void Finalize();
124 
126  bool IsFinalized() const;
127 
129  SdfSite GetSdSite(const Pcp_CompressedSdSite& site) const
130  {
131  return SdfSite(_GetNode(site.nodeIndex).
132  layerStack->GetLayers()[site.layerIndex],
133  _nodeSitePaths[site.nodeIndex]);
134  }
135 
137  Pcp_SdSiteRef GetSiteRef(const Pcp_CompressedSdSite& site) const
138  {
139  return Pcp_SdSiteRef(_GetNode(site.nodeIndex).
140  layerStack->GetLayers()[site.layerIndex],
141  _nodeSitePaths[site.nodeIndex]);
142  }
143 
145  PcpNodeRef GetNode(const Pcp_CompressedSdSite& site)
146  {
147  TF_VERIFY(site.nodeIndex < _GetNumNodes());
148  return PcpNodeRef(this, site.nodeIndex);
149  }
150 
151 private:
152  // Forward declarations for internal data structures.
153  struct _Arc;
154  struct _ArcStrengthOrder;
155  struct _Node;
156 
157  // Private constructors -- use New instead.
158  PcpPrimIndex_Graph(const PcpLayerStackSite& rootSite, bool usd);
159  PcpPrimIndex_Graph(const PcpPrimIndex_Graph& rhs);
160 
161  size_t _CreateNode(
162  const PcpLayerStackSite& site, const PcpArc& arc);
163  size_t _CreateNodesForSubgraph(
164  const PcpPrimIndex_Graph& subgraph, const PcpArc& arc);
165 
166  PcpNodeRef _InsertChildInStrengthOrder(
167  size_t parentNodeIdx, size_t childNodeIdx);
168 
169  void _DetachSharedNodePool();
170 
171  // Iterates through the immediate children of the root node looking
172  // for the first node for which p(node) is true and the first subsequent
173  // node where p(node) is false. Returns the indexes of the resulting
174  // nodes.
175  template <class Predicate>
176  std::pair<size_t, size_t> _FindRootChildRange(const Predicate& p) const;
177 
178  // Helper functions to compute a mapping between node indexes and
179  // the strength order of the corresponding node.
180  //
181  // Returns:
182  // True if the order of nodes in the node pool is the same as strength
183  // ordering, false otherwise.
184  //
185  // nodeIndexToStrengthOrder[i] => strength order of node at index i.
186  bool _ComputeStrengthOrderIndexMapping(
187  std::vector<size_t>* nodeIndexToStrengthOrder) const;
188  bool _ComputeStrengthOrderIndexMappingRecursively(
189  size_t nodeIdx, size_t* strengthIdx,
190  std::vector<size_t>* nodeIndexToStrengthOrder) const;
191 
192  // Helper function to compute a node index mapping that erases nodes
193  // that have been marked for culling.
194  //
195  // Returns:
196  // True if any nodes marked for culling can be erased, false otherwise.
197  // culledNodeMapping[i] => index of node i after culled nodes are erased.
198  bool _ComputeEraseCulledNodeIndexMapping(
199  std::vector<size_t>* culledNodeMapping) const;
200 
201  // Transforms the node pool by applying the given node index mapping.
202  // References to to other nodes in the pool are fixed up appropriately.
203  //
204  // \p nodeIndexMap is a vector of the same size as the node pool, where
205  // \p nodeIndexMap[i] => new position of node i.
206  // If \p nodeIndexMap[i] == _invalidNodeIndex, that node will be erased.
207  void _ApplyNodeIndexMapping(const std::vector<size_t>& nodeIndexMap);
208 
209 private:
210  // PcpNodeRef is allowed to reach directly into the node pool to get/set
211  // data.
212  friend class PcpNodeRef;
213  friend class PcpNodeRef_ChildrenIterator;
214  friend class PcpNodeRef_ChildrenReverseIterator;
215  friend class PcpNodeRef_PrivateChildrenConstIterator;
216  friend class PcpNodeRef_PrivateChildrenConstReverseIterator;
217 
218  // NOTE: These accessors assume the consumer will be changing the node
219  // and may cause shared node data to be copied locally.
220  _Node& _GetWriteableNode(size_t idx);
221  _Node& _GetWriteableNode(const PcpNodeRef& node);
222 
223  size_t _GetNumNodes() const
224  {
225  return _data->nodes.size();
226  }
227 
228  const _Node& _GetNode(size_t idx) const
229  {
230  TF_VERIFY(idx < _GetNumNodes());
231  return _data->nodes[idx];
232  }
233  const _Node& _GetNode(const PcpNodeRef& node) const
234  {
235  return _GetNode(node._GetNodeIndex());
236  }
237 
238 private:
239  // Allow Pcp_Statistics access to internal data for diagnostics.
240  friend class Pcp_Statistics;
241 
242  struct _Node {
243  static const size_t _nodeIndexSize = 15;
244  static const size_t _childrenSize = 10;
245  static const size_t _depthSize = 10;
246  // These types should be just large enough to hold the above sizes.
247  // This allows this structure to be packed into less space.
248  typedef unsigned short _NodeIndexType;
249  typedef unsigned short _ChildrenSizeType;
250  typedef unsigned short _DepthSizeType;
251 
252  // Index used to represent an invalid node.
253  static const size_t _invalidNodeIndex = (1lu << _nodeIndexSize) - 1lu;
254 
255  _Node()
256  /* The equivalent initializations to the memset().
257  , permission(SdfPermissionPublic)
258  , hasSymmetry(false)
259  , inert(false)
260  , culled(false)
261  , permissionDenied(false)
262  , arcType(PcpArcTypeRoot)
263  , arcSiblingNumAtOrigin(0)
264  , arcNamespaceDepth(0)
265  , arcParentIndex(0)
266  , arcOriginIndex(0)
267  */
268  {
269  memset(&smallInts, 0, sizeof(smallInts));
270  smallInts.arcParentIndex = _invalidNodeIndex;
271  smallInts.arcOriginIndex = _invalidNodeIndex;
272  smallInts.firstChildIndex = _invalidNodeIndex;
273  smallInts.lastChildIndex = _invalidNodeIndex;
274  smallInts.prevSiblingIndex = _invalidNodeIndex;
275  smallInts.nextSiblingIndex = _invalidNodeIndex;
276  }
277 
278  void Swap(_Node& rhs)
279  {
280  std::swap(layerStack, rhs.layerStack);
281  mapToRoot.Swap(rhs.mapToRoot);
282  mapToParent.Swap(rhs.mapToParent);
283  std::swap(smallInts, rhs.smallInts);
284  }
285 
286  void SetArc(const PcpArc& arc);
287 
288  // NOTE: We pack all info into _Node, including stuff that
289  // would reasonably encapsulate in other types like
290  // info about the arc to the parent, so we can lay
291  // out the data in memory as tightly as possible.
292 
293  // The layer stack for this node.
294  PcpLayerStackRefPtr layerStack;
295  // Mapping function used to translate from this node directly
296  // to the root node. This is essentially the composition of the
297  // mapToParent for every arc between this node and the root.
298  PcpMapExpression mapToRoot;
299  // The value-mapping function used to map values from this arc's source
300  // node to its parent node.
301  PcpMapExpression mapToParent;
302  // Pack the non-byte sized integers into an unnamed structure.
303  // This allows us to initialize them all at once. g++ will,
304  // surprisingly, initialize each individually in the default
305  // copy constructor if they're direct members of _Node.
306  struct _SmallInts {
307  // The permissions for this node (whether specs on this node
308  // can be accessed from other nodes).
309  SdfPermission permission:2;
310  // Whether this node contributes symmetry information to
311  // composition. This implies that prims at this node's site
312  // or at any of its namespace ancestors contain symmetry
313  // information.
314  bool hasSymmetry:1;
315  // Whether this node is inert. This is set to true in cases
316  // where a node is needed to represent a structural dependency
317  // but no opinions are allowed to be added.
318  bool inert:1;
319  // Whether this node was culled. This implies that no opinions
320  // exist at this node and all child nodes. Because of this,
321  // prim indexing does not need to expand this node to look for
322  // other arcs.
323  bool culled:1;
324  // Whether this node is in violation of permission settings.
325  // This is set to true when: we arrive at this node from a
326  // node that was marked \c SdfPermissionPrivate, or we arrive
327  // at this node from another node that was denied permission.
328  bool permissionDenied:1;
329  // The type of the arc to the parent node. We only need 4
330  // bits but we use 5 to avoid signed/unsigned issues.
331  PcpArcType arcType:5;
332  // Index among sibling arcs at origin; lower is stronger
333  _ChildrenSizeType arcSiblingNumAtOrigin:_childrenSize;
334  // Absolute depth in namespace of node that introduced this
335  // node. Note that this does *not* count any variant
336  // selections.
337  _DepthSizeType arcNamespaceDepth:_depthSize;
338 
339  // The following are padded to word size to avoid needing to
340  // bit shift for read/write access and having to access two
341  // words to read a value that straddles two machine words.
342  // Note that bitfield layout should be examined when any
343  // field is added, removed, or resized.
344 
345  // The index of the parent (or target) node of this arc.
346  _NodeIndexType:0;
347  _NodeIndexType arcParentIndex:_nodeIndexSize;
348  // The index of the origin node of this arc.
349  _NodeIndexType:0;
350  _NodeIndexType arcOriginIndex:_nodeIndexSize;
351 
352  // The indexes of the first/last child, previous/next sibling.
353  // The previous sibling index of a first child and the next
354  // sibling index of a last child are _invalidNodeIndex (i.e.
355  // they form a list, not a ring).
356  _NodeIndexType:0;
357  _NodeIndexType firstChildIndex:_nodeIndexSize;
358  _NodeIndexType:0;
359  _NodeIndexType lastChildIndex:_nodeIndexSize;
360  _NodeIndexType:0;
361  _NodeIndexType prevSiblingIndex:_nodeIndexSize;
362  _NodeIndexType:0;
363  _NodeIndexType nextSiblingIndex:_nodeIndexSize;
364  }
365  // Make this structure as small as possible.
366 #if defined(ARCH_COMPILER_GCC) || defined(ARCH_COMPILER_CLANG)
367  __attribute__((packed))
368 #endif
369  ;
370  _SmallInts smallInts;
371  };
372 
373  typedef std::vector<_Node> _NodePool;
374 
375  struct _SharedData {
376  _SharedData(bool usd_)
377  : finalized(false)
378  , usd(usd_)
379  , hasPayloads(false)
380  , instanceable(false)
381  { }
382 
383  // Pool of nodes for this graph.
384  _NodePool nodes;
385 
386  // Whether this node pool has been finalized.
387  bool finalized:1;
388  // Whether this prim index is composed in USD mode.
389  bool usd:1;
390  // Whether this prim index has authored payloads.
391  bool hasPayloads:1;
392  // Whether this prim index is instanceable.
393  bool instanceable:1;
394  };
395 
396  // Container of graph data. PcpPrimIndex_Graph implements a
397  // copy-on-write scheme, so this data may be shared among multiple graph
398  // instances.
399  std::shared_ptr<_SharedData> _data;
400 
401  // The following data is not included in the shared data object above
402  // because they will typically differ between graph instances. Including
403  // them in the shared data object would cause more graph instances to
404  // be created.
405 
406  // Site paths for each node. Elements in this vector correspond to nodes
407  // in the shared node pool. Together, _data->nodes[i].layerStack and
408  // _nodeSitePaths[i] form a node's site.
409  std::vector<SdfPath> _nodeSitePaths;
410 
411  // Flags indicating whether a particular node has any specs to contribute
412  // to the composed prim. Elements in this vector correspond to nodes in
413  // the shared node pool.
414  std::vector<bool> _nodeHasSpecs;
415 };
416 
417 PXR_NAMESPACE_CLOSE_SCOPE
418 
419 #endif // PCP_PRIM_INDEX_GRAPH_H
Represents an arc connecting two nodes in the prim index.
Definition: arc.h:44
An expression that yields a PcpMapFunction value.
Definition: mapExpression.h:55
A site specifies a path in a layer stack of scene description.
Definition: site.h:117
PcpNode represents a node in an expression tree for compositing scene description.
Definition: node.h:65
#define TF_DECLARE_WEAK_AND_REF_PTRS(type)
Define standard weak, ref, and vector pointer types.
Definition: declarePtrs.h:89
An SdfSite is a simple representation of a location in a layer where opinions may possibly be found...
Definition: site.h:43
Enable a concrete base class for use with TfRefPtr that inhibits the &quot;unique changed&quot; facility of TfR...
Definition: refBase.h:132
void swap(UsdStageLoadRules &l, UsdStageLoadRules &r)
Swap the contents of rules l and r.
#define TF_VERIFY(cond, format,...)
Checks a condition and reports an error if it evaluates false.
Definition: diagnostic.h:289
PcpArcType
Describes the type of arc connecting two nodes in the prim index.
Definition: types.h:46
A path value used to locate objects in layers or scenegraphs.
Definition: path.h:287
SdfPermission
An enum that defines permission levels.
Definition: types.h:155
Enable a concrete base class for use with TfWeakPtr.
Definition: weakBase.h:142