Object Search and Traversal

Overview

The ROSE library provides a functions for applications to traverse, search, or otherwise locate objects in memory. Since a RoseDesign is the basic unit of I/O for STEP data, most of these services operate within the scope of a single design.

Some functions search for objects based upon particular criterion. Applications can take advantage of the EXPRESS usedin() function, objects organized by type, named objects, STEP entity identifiers from Part 21 files, ROSE universal object identifiers (OIDS), and objects marked as the root of a design. In addition, applications can use design cursors and special marking functions to simplify traversals. Each service is described in the following sections.

C++ is a strongly typed language, so pointer type casting is a major concern when working with objects returned by the traversal functions. Since traversal operations must handle all types of objects, most function return values are typed as RoseObject pointers. These very general pointers must often be cast to an appropriate type before using them.

Pointer Type Casting

C++ is a strongly typed language, and traversal functions often return values as general RoseObject pointers. You must cast the pointers to a more specific type before using them. Historically, C++ allows casts from a specific (subclass) to general (superclass), but not in the other direction. Before Run Time Type Information (RTTI) was common, the compiler could not check to verify that the cast is valid. The figure below shows the casting capabilities of C++.

The following code fragments show some C++ casts. If cartesian_point had a virtual base class (needed for multiple inheritance), the last cast would not be allowed by the compiler:

RoseDesign * d;
RoseObject * obj;

cartesian_point * pt = pnewIn(d) cartesian_point;
obj = pt;                     /* valid, automatic specific to general */
obj = (RoseObject *) pt;      /* valid, explicit specific to general*/

pt = obj;                     /* invalid, automatic general to specific */
pt = (cartesian_point *) obj; /* Disallowed if class has virtual base 
				 classes.  Otherwise allowed but validity 
				 unchecked by compiler. */

The ROSE_CAST() macro allows the full range of casting, even on classes with virtual base classes. It uses the ROSE type information to provide run-time type checking. The full range of casting is shown in the figure below.

The ROSE_CAST() macro takes the name of a type and a pointer value. It returns a pointer value of the appropriate type, with offsets adjusted accordingly to account for virtual base classes. The following example shows how to cast the results of a query down to a more specific type.

RoseCursor objects;
RoseObject * obj;

objects.traverse (design);
objects.domain (ROSE_DOMAIN (cartesian_point));

while ((obj=objects.next()) != 0) 
{
    cartesian_point * pt = ROSE_CAST (cartesian_point, obj);
    ... 
}

The RoseCursor::next() function returns a RoseObject pointer. Since we have told the cursor to only return cartesian points, we are confident that object is an instance of the more specific cartesian_point class. We use ROSE_CAST() to cast the pointer from RoseObject* to cartesian_point*.

If we tried to cast an object that was not a cartesian_point, the cast would return a null pointer and issue a warning. If we were not sure of the object type, we could check first using the RoseObject::isa() function.

Find Objects by Type

The RoseCursor class provides quick traversals over the contents of a design. It can return each object in the design or just objects of a specific type. It is time and space efficient because it traverses the data in place and does not need to creating an intermediate lists

The easiest way to use a RoseCursor is to create it on the stack so that the compiler can take care of allocating and deallocating the object. Next, use traverse() to tell the cursor what design to traverse.

By default, a cursor will returns all data objects, but you can select objects of a particular type using the domain() or exact() functions. The domain() function chooses all objects of a particular type plus all subtypes, while the exact() function chooses exactly one type with no subtypes.

Finally, you can iterate over the objects by calling the next() function. This function will return null when there are no more objects. The rewind(), previous(), and fastforward() functions are also available if you want to repeat the traversal or go through the list in reverse order.

The example below traverses all Point objects in a design. The next() function returns objects as a RoseObject pointer, and we use the ROSE_CAST() macro to cast the return value down to a more specific C++ type.

RoseCursor objects;
RoseObject * obj;

objects.traverse (design);
objects.domain (ROSE_DOMAIN (Point));

while ((obj=objects.next()) != 0) 
{
    Point * pt = ROSE_CAST (Point, obj);
    ... 
}

The code above returns instances of the Point type and subtypes, such as cartesian points. If we only want Point objects without any instances of subtypes, we can use RoseCursor::exact() instead of domain(), as shown below.

objects.traverse (design);
objects.exact (ROSE_DOMAIN (Point));
...

The cursor class contains other functions to select file header objects instead of data objects. If you need to cover several disconnected types in a single loop, you can use the RoseTypesCursor specialized cursor or provide a RoseCursor::type_filter() callback function to decide which types to return.

The RoseDesign class has the findObjects() function, which is a wrapper around RoseCursor that iterates over a design and fills an aggregate. Since this populates a list, it is not as space efficient as just using the cursor directly.

Find Object by An Identifier

The ROSE library provides several indexing mechanisms for marking individual objects. Except as noted, these mechanisms are useful only while the objects are stored as ROSE working form files. STEP Part 21 files do not support this extra index information. The three main indices associate objects with names, universal object identifiers (OIDS), and STEP Part 21 entity identifiers.

STEP Part 21 Entity Identifier (#123)

The entity identifiers for objects that have been read in from a Part 21 physical file are available to an application program. The entity identifiers are the #number tags that are associated with each entity instance in a physical file. These identifiers are not meant to be persistent and may change each time the file is written.

You can search for these identifiers using the RoseDesign::findByEntityId() function. This builds an index for all of the IDs in the design. The entity identifiers are accessed through the RoseObject::entity_id() function.

Entity identifiers are only available for entities (RoseStructure subtypes) that are read from STEP physical files. This field will be zero for aggregates and selects read from physical files, as well as all objects read in from ROSE working form files. All entities are usually renumbered when written back out to disk.

STEP Part 21 Anchor / Object Name

Every RoseDesign object maintains an index of name/object pairs. Applications can use this name index to tag and locate specific objects. The name index is preserved as long as a design is written to ROSE working form files, but is lost when a design is written to a STEP Part 21 file. This mechanism is used extensively to find definitions within the ROSE compiled schema files.

An object can have many different names, but a name can be associated with only one object. The RoseDesign::addName() function associates an object with a name. Names can be removed with RoseDesign::removeName(). The name index is implemented as a dictionary of RoseObjects returned by RoseDesign::nameTable(). Refer to RoseDictionary for more on dictionaries.

Objects can be searched for with RoseDesign::findObject(). These functions return a RoseObject pointer, so an application must use the ROSE_CAST() macro to convert it to a more specific type.

RoseDesign * design;
cartesian_point * t;
. . .
design-> addName (top, t);
. . .
t = ROSE_CAST (cartesian_point,design-> findObject (top));

The RoseInterface::findObjectInWorkspace() function will search all designs in memory. If many designs have an object with the name, the function will return the first match. The order in which the designs are searched is not specified.

ROSE Unique Identifier (OID)

ROSE Object Identifiers (RoseOIDs) are 160 bit (20 byte) globally unique values used by the ROSE library for some cross-file references. Every data object can have a RoseOID, which can be retrieved with the RoseObject::oid() function. Because of the structure of these identifiers, we use a shorthand 32 bit representation for them while in main memory. This is the value that is passed to functions.

These identifiers are only preserved by ROSE working form files. When a STEP Part 21 file is read, the objects do not have a RoseOIDs until one is requested. Part 21 files must be entirely self contained, or must use a higher semantic mechanism for resolving object references.

RoseOIDs are used by ROSE internals. The RoseDesign::findObject() function can search for an object with a particular RoseOID. In addition, the RoseInterface::findObjectInWorkspace() function will search all designs in memory and return the first match. It is possible for two objects in different designs to have the same OID if they were copied from the same object. The order in which the designs are searched is not specified.

Mark Objects as Visited

Many algorithms need mark objects to detect multiple visits, prevent circular references, or indicate status. The ROSE library has functions to create markers and efficiently apply them to objects.

The rose_mark_begin() function initializes an object marker and returns a handle identifying a marker. You can use this handle to alternate between several marks, but for simple use that is strictly nested, you can omit the handle in the function calls and the most recent one will be used. The macro ROSE_MARK_CURRENT also refers to most recently opened mark.

When a new marker is started, no data objects will be marked. Call rose_mark_set() to add a mark, rose_is_marked() to test for a mark, and rose_mark_clear() to remove a previously placed mark. When the traversal is finished, call rose_mark_end() to release the mark.

The following example shows a simple traversal which takes a list that may contain duplicates. The code marks each object as it works to make sure that no object is processed twice.

ListOfRoseObject * objs;

rose_mark_begin();
for (unsigned i=0; i<objs->size(); i++)
{
    RoseObject * obj = objs->get(i);
    if (!rose_is_marked(obj))
    {
	rose_mark_set(obj);
	/* do other things */
    }
}
rose_mark_end();

The following example shows a traversal that uses multiple marks to categorize some objects.

unsigned i;
ListOfRoseObject * objs;

RoseMark red = rose_mark_begin();
RoseMark green = rose_mark_begin();
RoseMark blue = rose_mark_begin();

// Apply several different marks based on various conditions

for (i=0; i<objs->size(); i++)
{
    RoseObject * obj = objs->get(i);
    if (/* obj is red */)    rose_mark_set(obj, red);
    if (/* obj is green */)  rose_mark_set(obj, green);
    if (/* obj is blue */)   rose_mark_set(obj, blue);
}

// Do something based on what marks an object has
for (i=0; i<objs->size(); i++)
{
    RoseObject * obj = objs->get(i);
    if (rose_is_marked(obj, red) &&
        rose_is_marked(obj, green) &&
        rose_is_marked(obj, blue))
    {
	// object is marked by all three
    }
}

rose_mark_end(red);
rose_mark_end(green);
rose_mark_end(blue);

TheRoseCursor::nextUnmarked() and nextMarked() functions can also be used when marking objects during a traversal of a design. This may simplify your code slightly because it handles the test within the "next" function on the cursor. For example:

RoseCursor objs;
RoseObject * obj;
. . . 
rose_mark_begin();
while (obj = objs.nextUnmarked())
{
    rose_mark_set (obj);
    /* do other things */
}
rose_mark_end();

EXPRESS Usedin

The EXPRESS usedin() function is an important navigational mechanism. This function searches a data set for references to a particular object. Given an object and description of the attribute relation to look for, this function searches the data set for all instances that refer to the specified object through the given attribute relation. The structure of the STEP information models make this operation very valuable to an application programmer.

The primary design goal of a STEP APs is to document the structure of product information and relationships in a clear and unambiguous manner. Unfortunately, the clearest way to document a relationship is not always the way an application programmer would prefer for easy access.

An information modeler must capture existence and cardinality constraints of relationships. As an example, let us consider a one-to-many relationships, such as an assembly that has some parts. We would like to capture the knowledge that assemblies have associated simple parts, no two assemblies share parts, and no parts can exist without a assembly. One model for this is to have an assembly object refer to its part objects. The schema below shows this model.

ENTITY assembly;
    contents : SET [1:?] OF part;
END_ENTITY;

ENTITY part;
END_ENTITY;

Unfortunately, while this model matches the way we might wish to traverse the structure — from assembly to part — it does not completely model the constraints. We could construct stand-alone parts or parts that are owned by more than one assembly. Of course, we might argue that a disciplined user would not do this, but the goal of information modeling is to capture constraints within the model, not to rely on auxiliary knowledge. A better model would be:

ENTITY assembly;
END_ENTITY;

ENTITY part;
    owner : assembly;
END_ENTITY;

This is much better, since a part must have one and only one owner. Unfortunately, we have no direct navigation path from assembly to part. The EXPRESS usedin() function lets us perform a query to get that information:

ENTITY assembly;
DERIVE
    contents : SET [1:?] OF part := USEDIN (SELF, 'part.OWNER');
END_ENTITY;

ENTITY part;
    owner : assembly;
END_ENTITY;

And in fact, the usedin() function is similar to constructing an impromptu inverse attribute. The schema would be better written as:

ENTITY assembly;
INVERSE
    contents : SET [1:?] OF part FOR owner;
END_ENTITY;

ENTITY part;
    owner : assembly;
END_ENTITY;

This pattern appears throughout the STEP information models. Consequently, application programmers may need the usedin() function. This is available through RoseObject::usedin(). When called on an object, this function will search for references in the design that owns the object.

The usedin() function takes several arguments. The first is a RoseDomain data dictionary object which describes the type of object to search. If this is null, all entity instances (RoseStructure objects) within the design are searched. The second argument is a RoseAttribute object describing the attribute to examine. If this is null, all attributes of an object are examined. Finally, the function expects a RoseAggregate object to pass back the pointers to the matching objects. If this is null, a ListOfRoseObject is created by the function. You must free this object when it is no longer needed. The example below shows how one might use usedin() with the assembly schema.

unsigned i, sz;
ListOfpart contents; 

assembly *      aobj
RoseDomain *    search_domain;
RoseAttribute * search_att;

search_domain = ROSE_DOMAIN (part);
search_att = search_domain-> findTypeAttribute (owner);

aobj-> usedin (search_domain, search_att, &contents);
for (i=0, sz=contents.size(); i<sz; i++)
{
	  /* loop over the part objects */
}

Note the stack-based contents list in this example. Since we only need a temporary, non-persistent list, we keep the object on the stack, rather than creating it on the heap with new or pnew. This is a useful technique because the C++ compiler will allocate and deallocate the object when control flow enters and leaves the scope of the declaration. This is only useful for transient, non-persistent objects. Persistent objects must always be created on the heap with pnew.

An application can accumulate objects found by several different calls into a single list. If the aggregate passed to usedin() already has objects in it, the function will append the objects it finds to the aggregate.

Backpointers

The references in STEP Application Protocols often point is a direction that is inconvenient for application programmers to use. Thus, the ROSE library includes a feature to compute the back pointers to simplify object traversal.

Before using back pointers, you must call the rose_compute_backptrs() function, passing the RoseDesign for which you want the back pointers computed. This traverses all instances within the design and builds a list of backpointers on each instance. When you are finished, call rose_release_backptrs() to free the memory used to hold the back pointers.

Once the backpointers have been computed, you can retrieve them for any instance by calling rose_get_backptrs() on the object you need the back pointers to. This returns a RoseBackptrs object which can then be used to find all the references to the target object.

For example, you can use the following code to find all the instances that refer to the object obj.

RoseDesign *des = obj->design();
rose_compute_backptrs(des);
RoseBackptrs *bp = rose_get_backptrs(obj);
for (unsigned i=0; i<bp->size(); i++) {
  RoseObject * ref = bp->get(i);
  /* Ref points to obj -- go something with it here */
}

You can also use a RoseBackptrCursor to limit the scope of a search to a particular attribute. For example this can be used to efficiently compute inverse attributes.

RoseObject * product;
RoseAttribute * att = des->findDomain(product_definition_formation)
      ->findTypeAttribute(of_product);
RoseBackPtrCursor cur;
cur.traverse(product);
cur.attribute(att);
RoseObject *pdf;
while (pdf = cur.next()) {
  /* Do somethig with the product_definition_formation in pd */
}

Reference Counting

If you only need to know whether an object is referenced or not, a full set of backpointers is not necessary. The ROSE library can compute reference counts for objects in a more space efficient way than computing backpointer lists.

The procedure is similar to the backpointer functions described above. An application computes the reference counts for a design, then processes the objects using the counts, then finally releases the counts and cleans up the space.

Use rose_compute_refcount() to initializes the counts and rose_release_refcount() to clean up afterwards. Applications can then use rose_refcount() in the middle to test a particular object. The example below looks for unreferenced objects in a design. Note that this examines all types of objects: entities, selects, and aggregates.

RoseDesign * design;
RoseObject * obj;
RoseCusrsor objs;
rose_compute_refcount(design);
objs.traverse(design);
while (obj=objs.next()) {
    if (!rose_refcount(obj)) printf (Unreferenced obj!\n);
}
rose_release_refcount(design);

If you modify the objects after computing the reference counts, the counts are not automatically updated. However there are a number of functions that you can use to maintain the reference counts when adding or deleting objects.

The rose_refcount_inc() and rose_refcount_dec() functions increment or decrement the count of an individual object and return the new count value. If you want to set the reference count to a specific value, the rose_refcount_put() function can do so.

If you are deleting an object, you can decrement the reference counts of the objects referred to by its attributes using the rose_refcount_dec_atts() function. This only goes one level deep, but the rose_refcount_recursive_dec_atts() function continues to recursively decrement attributes of a sub-object if it becomes unreferenced.

Using this function, you could write a function to cleanly delete a tree of objects as shown below. Objects would only be deleted if they were not referenced elsewhere in the data.

ListOfRoseObject objs;
unsigned i, sz;

rose_refcount_recursive_dec_atts(obj, &objs);
for (i=0, sz=objs.size(); i<sz; i++) {
    rose_move_to_trash (objs[i]);
}
rose_move_to_trash (obj);

Design Sections

The objects within a RoseDesign are divided into design sections. Each design may have a section for the data objects, one for file header objects, and one for internal system objects. These sections correspond to the sections of a Part 21 physical file and are represented by instances of the RoseDesignSection class.

The RoseDesign::sections() function returns a linked list of RoseDesignSection objects belonging to the design. The list can be traversed using the RoseDesignSection::next() function.

When a design is written as a ROSE working form file all three types of sections are preserved. STEP physical files only preserve the header and data sections. The system section, which contains name table and other information is not preserved. The three types of sections are:

Data Section — Contains normal STEP data objects can be found. This corresponds to the DATA section of a Part 21 file. A design may have more than one data section when using multiple data section Part 21 files.
Header Section — This is where the Part 21 HEADER objects can be found. This can be accessed with the RoseDesign::header_section() function.
System Section — This contains objects specific to ROSE working form files, such as the ROSE name index, and associated database information. The system section is never written to a STEP Part 21 file, but it is written to ROSE working form files. This can be accessed with the RoseDesign::system_section() function.

Each design has a default section. Object created with pnew or pnewIn(RoseDesign*) will be placed in the default section. The default section is usually the first data section in the design, but it can be set to one of the others. This can be accessed with the RoseDesign::dflt_section() function. Objects can be created in a specific section using the pnewIn(RoseDesignSection*) operator.

RoseDesign * d;
Point * pt;

pt = pnew Point;         // in dflt section of current design
pt = pnewIn (d) Point;   // in dflt section of design 'd'
pt = pnewIn (d-> dflt_section()) Point;    // in default section
pt = pnewIn (d-> system_section()) Point;  // in system section

The RoseCursors understand and can take advantage of the design sections. The RoseCursor::traverse() function accepts individual sections as well as designs. To find the number of objects in a section, use the RoseDesignSection::size() function.

Objects can be moved between design sections using the rose_move_to_section() function. Moving an object to a null section makes it non-persistent, just like moving an object to a null design.