Method and apparatus for a type-safe framework for dynamically extensible objects5761511Abstract The present invention provides a system and process for making use of pre-existing data-structures which represent a computer program, in a way which has the advantages of shortening the time and cost required to create a new version of the computer program. The pre-existing data-structure is modified to produce a shadow data-structure which contains only shadows of those elements or nodes of the pre-existing data-structure required to perform the tasks of the new version of the computer program. The present invention includes processes to make the data-structure of the original program shadowable; processes to use data from the original program compilation process in compiling the new version of the program, including processes to create a shadow data-structure; and processes to use the new version of the computer program along with the shadow data-structure to create the desired execution. This new version of the computer program is typically a tool for checking or observing the original program's execution in some manner. Moreover, the system and processes disclosed provide mechanisms for a software manufacturer to create type-safe versions of a connected collection of objects which are dynamically extensible. Claims What is claimed is: Description BACKGROUND OF THE INVENTION
______________________________________
class Shadowable
public:
virtual Narrowable *create.sub.-- shadow (ShadowMap *map) =0;
};
______________________________________
Although all nodes to be shadowed must provide an implementation of create.sub.-- shadow, this method is never directly called by a client. In the preferred embodiment, the implementation is boiler-plate code that invokes the appropriate factory method on an appropriate subtype of the shadow map argument. This boiler-plate code can be mechanically generated by the program "autodefine". The map argument provides a context for the shadow, permitting different shadows of the same node to coexist. ShadowMap In the preferred embodiment, the object ShadowMap represents the shadow map. It has one public method, to look up a shadow node in the map, and to create one if not found. However, even this method is not normally called directly by clients. Instead, clients should call the shadow method on the target class instead, which provides more convenient and type-safe access to shadow nodes. There will normally be two levels of inheritance based on ShadowMap. The first extends the ShadowMap with a set of pure virtual methods that define the ability to shadow specific types of nodes; the second level provides the implementation of those pure virtual methods.
______________________________________
class ShadowMap
public:
Narrowable *lookup.sub.-- or.sub.-- create.sub.-- shadow(Shadowable
*orig);
// returns the shadow node for `orig`.
};
______________________________________
T'::shadow The most important method in the preferred embodiment is T'::shadow, since it is the primary way a client creates or accesses the shadow of a node. It is a static method on the desired type, T', of the shadow node. It takes two arguments: the node to be shadowed, of type T, and a shadow map. static T' *T'::shadow(T *t, ShadowMap *map); It returns the shadow of "t" according to "map." The argument passed as "map" should be an instance of a map capable of generating T' nodes from T nodes. This can be enforced by using an appropriate subtype of ShadowMap, as described below. Making a data structure shadowable The steps that must be taken to make a data structure shadowable in the preferred embodiment are now described. Referring now to FIG. 11, a task flow diagram 200 for the programmer of the original data structure is illustrated. In FIG. 11 the process begins with the programmer writing header files 204 to describe the objects that go to make up the data structure. These header files are augmented to add "create.sub.-- shadow" method to each type of shadowable object 206. The objects declared in the header files will inherit from the library class "Shadowable". Since the data structure is composed of objects, and objects have methods, the programmer then writes the code 208 for the methods of the objects in the data structure. In the preferred embodiment, some of the methods can be mechanically generated by running the header files through the program "autodefine" to create definitions and boiler plate functions and objects 210. The output of "autodefine" is C++ code that is combined with the written code from step 208. The programmer must also provide a special "ShadowMap" object for others who may wish to shadow the data structure. The "ShadowMap" class is also generated by "autodefine" in step 210 resulting in some header files that are combined with the header files from step 204 and all of these header files are collected together for later use by others 212. All of the header files and code files are then processed by a compiler 216 to generate object code. The output from the compiler 221 will be used by both the originating programmer and by others who may wish to create shadow data structures therefrom 218. In the preferred embodiment, some additional comments are of interest. To make a data structure shadowable, all the nodes to be shadowed in the data structure must inherit from a common root class, and this common root class must itself inherit from "Shadowable." The need for a common root class other than "Shadowable" is a requirement of the program "autodefine" which is used to automatically generate parts of the shadow machinery. All nodes to be shadowed must implement the abstract "create.sub.-- shadow" method inherited from "Shadowable." Narrowable *create.sub.-- shadow (ShadowMap *); These implementations of "create.sub.-- shadow" are typically declared as private methods on the nodes to be shadowed, to emphasize that they are not to be called directly by clients. (The method is declared public on "Shadowable.") The implementation is boiler-plate code that invokes the appropriate factory method on an appropriate subtype of the shadow map argument. This boiler-plate code can be mechanically generated by the utility "autodefine". One more thing must be done to make a data structure shadowable: an abstract subtype of "ShadowMap" must be provided that defines a special method for each node type, T, to be shadowed: Narrowable *shadowT(T*); These methods will be referred to in the boiler-plate implementations of "create.sub.-- shadow." Example Referring now to FIG. 12, a class structure for an example data structure 230 is shown. The data structure containing nodes of type A 238, B 234, C 240 and D 236. Suppose C 240 inherits from A 238 and D 236 inherits from both A 238, and B 234. Let us suppose that "Roman" 232 is the supertype for these four classes. Then we would expect to see the following patterns in the code:
______________________________________
class Roman: public virtual Shadowable
public:
// any generic methods on all Roman node types can be declared here
private:
Narrowable *create.sub.-- shadow (ShadowMap *);
};
class A: public virtual Roman
{
public:
// A methods. . .
private:
Narrowable *create.sub.-- shadow (ShadowMap *);
};
class B: public virtual Roman
{
public:
// B methods. . .
private:
Narrowable *create.sub.-- shadow (ShadowMap *);
};
class C: public virtual B
{
public:
// C methods. . .
private:
Narrowable *create.sub.-- shadow (ShadowMap *);
};
class D: public virtual A, public virtual B
{
public:
// D methods. . .
Narrowable *create.sub.-- shadow (ShadowMap *);
};
class Roman.sub.-- ShadowMap: public virtual ShadowMap
{
public:
virtual Narrowable *shadowRoman(Roman *);
virtual Narrowable *shadowA(A *);
virtual Narrowable *shadowB(B *);
virtual Narrowable *shadowC(C *);
virtual Narrowable *shadowD(D *);
};
______________________________________
Given the name of the root class, "Roman", the utility "autodefine" can mechanically generate the definition of the class "Roman.sub.-- ShadowMap" and default method bodies. The details of the default "shadow T" methods are described below. Those skilled in these arts will recognize that "virtual inheritance" is used in this example as a matter of style, and it may not be necessary in all situations. Making a specific shadow of a data structure For any data structure to be shadowed, it must be built with the conventions described above. To permit a specific shadow to be made, the major task is to provide an implementation of -the subtype of "ShadowMap" specific to the nodes in the data structure. The shadow map subtype contains a collection of methods of the form: Narrowable *shadowT(T*); These methods will be implicitly invoked as a result of a client calling T'::shadow (t, map); for the first time. (Subsequent calls will return the same result, which will have been saved in the shadow map.) Thus it is the task of the method to construct a T' object from the T*argument. This will typically involve shadowing the members of the T object and constructing a T' object from them. In addition to providing an implementation of a shadow map with factory methods that actually create the nodes of the shadow data structure, a shadow method must be declared on each of the classes for nodes in the shadow data structure. More accurately, it must be declared on those classes which can be generated as the result of shadowing a shadowable node. (See T'::shadow discussion above.) If the class being shadowed is T, and the corresponding shadow class is T', then the shadow method is declared as:
______________________________________
class T'
public:
static T' *shadow(T *t) TRoot.sub.-- ShadowMap *map);
};
______________________________________
In the preferred embodiment, the implementation of this method is boiler-plate, and can be generated by the utility "autodefine". It calls map->lookup.sub.-- or.sub.-- create.sub.-- shadow (t) and narrows the result to be of type T'*. "Narrows" here refers to a C++ technology which is described in Appendix A. Narrowing is also known as "down-casting" in the C++ community. Referring now to FIG. 13, the process followed by a subsequent programmer 250 to make a shadow data structure from some pre-existing shadowable data structure is depicted. The programmer writes header files 254 to describe the objects that go to make up the shadow data structure. These header files may reference the header files (204 in FIG. 11) supplied by the programmer of the original data structure. Since the shadow data structure is composed of objects, the programmer also writes code files 256 for the methods of these objects. These code files 256 will reference the header files supplied by the programmer of the original data structure (212 in FIG. 11). The code for the "shadow factory" methods are also written 258. The header files 254 are combined with the header files 214 (in both FIGS. 11 and 13) and passed through the utility "autodefine" 260 to generate the boilerplate code to produce the shadow data structure. The C++ code output by "autodefine" and the newly written code files 256 along with all of the header files are compiled together 262 and the outputted object code 263 is combined with the object code supplied 220 (in both FIGS. 11 and 13) and linked together to form a program 264. This program is then executed 266 in FIG. 13 and as shown in 270 in FIG. 14. Referring now to FIG. 14, during the program execution, a shadowable original data structure is created 274, a shadow data structure is created 276, and the shadowed data structure is executed 278. The subroutine to create the shadow data structure (276 in FIG. 14) is now described in more detail with reference to FIG. 15. In FIG. 15, the subroutine 290 when called 292 first creates a shadow map and associated shadow factory if it has not already done so 294. Then the subroutine 290 determines whether the original data structure node in question has been registered in the shadow map 296. If so 299 the subroutine returns the value registered (pointer) in the shadow map against the node in question 304, to the caller of the subroutine and exits 306. If however, the original data structure node in question has not been registered in the shadow map 298, then the "create.sub.-- shadow" method is called for the node, according to the node's type 300. This creates a shadow node and the result (pointer to the shadow node) is registered in the shadow map 302. This value then is returned to the caller of the subroutine 304 and the subroutine exits 306. The details of the "create.sub.-- shadow" method (300 in FIG. 15) is now described with reference to FIG. 16. In FIG. 16, when the "create.sub.-- shadow" method 310 is called 312, the implementation first determines the true type of the referenced node 314. A method is called on the shadow factory appropriate to the type of the referenced node object 316 to create a shadow node, and the newly created shadow node reference is returned to the caller 318 and the "create.sub.-- shadow" method exits 320. The details of the method for the shadow factory (316 in FIG. 16) are shown in FIG. 17. In FIG. 17, the shadow factory method 330, when called 332, checks the shadowable node to see if there are any child nodes of the specified node which must be shadowed 334. If so, the subroutine is run to create shadow nodes for the child nodes of the original data structure 336. In so doing this step determines whether a loop would be caused and records the arguments for later processing. Finally the shadow factory implementation creates the shadow node from shadowed children and from other non-shadowable information from the shadowable node 338 and exits 340. Example: Shadow methods and ways of generating shadow nodes Continuing the example above, involving classes A, B, C, and D, that inherit from "Roman", suppose we wish to make a shadow involving nodes Alpha, Beta, Gamma, and Delta, that have a common root node, "Greek". Then, picking "Alpha" as an example, its "shadow" method might be defined as:
______________________________________
class Alpha
public:
// other Alpha methods. . .
static Alpha *shadow(A *a, Roman.sub.-- ShadowMap *map);
};
______________________________________
Now a definition of a factory class is needed, such as "GreekFromRoman.sub.-- ShadowMap" that is an implementation of the class "Roman.sub.-- ShadowMap". Note that that class merely declared abstract (or default) "shadow T" methods for the various sub types of the root node, "Roman". It did not embody any knowledge of the types of the shadow nodes to be created; that knowledge will be embodied in the implementation of the methods of "GreekFromRoman.sub.-- ShadowMap". This is what the definition of the class "GreekFromRoman.sub.-- ShadowMap" might look like.
______________________________________
class GreekFromRoman.sub.-- ShadowMap:
public virtual Roman.sub.-- ShadowMap
public:
// Roman.sub.-- ShadowMap methods defined by this class:
Narrowable *shadowA(A *);
Narrowable *shadowB(B *);
Narrowable *shadowC(C *);
Narrowable *shadowD(D *);
};
______________________________________
If the shadow map being inherited has only pure virtual methods, then all of those methods will need to be implemented here. If there are any default implementations, then it may not be necessary to implement all of the methods here. Default factory methods for a shadow map are described below. There are several paradigms that can be used, and the examples that follow should be considered merely illustrative of the techniques that can be used. Which paradigm is appropriate in any particular situation will be a matter of personal taste and considerations of how to group the shadowing code: all together, or with the code for the nodes to be shadowed. Shadowing instance data within the factory method for a shadow node Suppose we wish to shadow an A object into an Alpha object, and that an A object has two members, of type B* and C* that are both to be shadowed into the Alpha object. Then, assuming suitable access functions and constructors, the factory method could be written in the following way:
______________________________________
Narrowable *GreekFromRoman.sub.-- ShadowMap:: shadowA (A *a)
Beta *beta = Beta::shadow(a->get.sub.-- b(), this);
Gamma *gamma = Gamma::shadow(a->get.sub.-- c(), this);
return new Alpha (beta, gamma);
};
______________________________________
The method shadows the child members of A, recursively invoking the shadow machinery for the children and calling a constructor on the result. Not all children need be shadowed if there is no need for them in the shadow node. Some members may not be shadowable: for example, basic types, enumerated values, strings and so on. These members can either be copied across to the shadow node directly, or a back pointer to the original node can be stored in the shadow, so that the shadow can get at these members by following the back pointer. The decision of which way to store them should be made by taking considerations of space and access time into account. Just as not all members of the original node may be shadowed, so not all members of the shadow node may be the result of shadowing members from the original node. Storing a back pointer is a very simple example. Alternatively, some members of the shadow node may be the result of computing and caching a complex expression involving one or more members of the original node. Shadowing instance data within a constructor for a shadow node Instead of shadowing the children in the factory method, the shadowing can be done in the constructor for the shadow node itself:
______________________________________
Narrowable *GreekFromRoman.sub.-- ShadowMap::shadowA(A *a)
return new Alpha (a, this);
};
Alpha::Alpha (A *a, Roman.sub.-- ShadowMap *map)
:beta(Beta::shadow(a->get.sub.-- b(), map)),
gamma(Gamma::shadow(a->get.sub.-- c(), map())
{};
______________________________________
Performing the shadowing in the constructor keeps the conversion code close to the rest of the code for Alpha, whereas performing the shadowing in the factory, groups all of the shadowing code (for all classes) together. Shadowing instance data within a static method of the shadow node Having the factory method call the constructor for the shadow node implies that the factory knows exactly what the shadow type really will be, as indicated by the calls of "new Alpha.(. . . )". Another solution is to use a static create method on the Alpha class. This keeps the factory code simple, without binding in knowledge of a concrete type.
______________________________________
Narrowable *GreekFromRoman.sub.-- ShadowMap::shadowA(A *a)
return Alpha::create(a, this);
};
Alpha *Alpha::create(A *a, Roman.sub.-- ShadowMap *map)
{
Beta *beta = Beta::shadow(a->get.sub.-- b(), map);
Gamma *gamma = Gamma::shadow(a->getc(), map);
return new Alpha (beta, gamma);
};
______________________________________
Example: Generating different types of shadow node There was an example above concerning a compiler parse tree node of type "PT.sub.-- BinaryExpr" that is to be shadowed into one of a number of different types, depending on the binary operation. Here is how that might be implemented, using a static create method in the shadow class.
______________________________________
CG.sub.-- Expr *CGBinaryExpr::create(PT.sub.-- BinaryExpr *be,
PT.sub.-- ShadowMap *map)
CG.sub.-- Expr *left = CGExpr::shadow(be->get.sub.-- get.sub.-- left(),
map);
CG.sub.-- Expr *right = CGExpr::shadow(be->get.sub.-- right(), map):
switch (be->get.sub.-- op()) {
case Op:: Add:
return new CG.sub.-- AddExpr(left, right);
case Op::Sub:
return new CG.sub.-- SubExpr(left, right);
case Op::Mult:
return new CG.sub.-- MultExpr(left, right);
case Op::Div:
return new CG.sub.-- DivExpr(left, right):
default:
should.sub.-- not.sub.-- happen();
}
};
______________________________________
Note that the body of this method could also be put into the factory method shadowPT.sub.-- BinaryExpr. The choice of where to locate the code is mostly one of style, although by making it a method on PT.sub.-- BinaryExpr, it is possible that a more sophisticated example would be able to make use of other methods defined in the class which might only be privately accessible. Lazy shadows for cyclic data The various examples of making shadows shown above also used the primitive operation "T'::shadow". As was noted in the explanation above, this will likely cause recursive calls on shadow for all the children of the node being shadowed. The corollary is that when shadowing a node, the transitive closure of all children of that node will also be shadowed. This will work provided the data structure is acyclic. If the data structure is cyclic, then the recursive processing scheme will not terminate, and will eventually run out of memory. "Lazy shadows" provide a way around these problems. They should be used if the data has (or might have) cycles; they can also be used if it is not necessary or desirable to shadow all of a data structure up front. If "T" is a type of node to be shadowed and "T'" is the type of the shadow node for T, then "LazyShadow<T', T>" is a template for a smart pointer that lazily evaluates "T'::shadow". The smart pointer is initialized with the two arguments for "T'::shadow:" a "T*" pointer and a "ShadowMap*". It can be assigned to a T' pointer, and can be transparently dereferenced as a T' pointer; both of these operations will cause the shadow to be evaluated. Consider the following code, written without using lazy shadows.
______________________________________
Narrowable *GreekFromRoman.sub.-- ShadowMap::shadowA(A *a)
return new Alpha(a, this);
}
class Alpha
{
public:
Alpha::Alpha(A *a, Roman.sub.-- ShadowMap *map);
void print();
private:
Beta *beta;
Gamma *gamma;
};
Alpha::Alpha(A *a, Roman.sub.-- ShadowMap *map)
: beta(beta::shadow(a->get.sub.-- b(), map)),
gamma(Gamma::shadow(a->get.sub.-- c(), map())
{}
void Alpha::print()
{
Beta *beta2 = beta;
gamma->print();
};
______________________________________
If for some reason it becomes necessary or desirable to use lazy shadows for the child nodes of class Alpha, here is how the code might change.
______________________________________
class Alpha
public:
Alpha::Alpha(A *a, Roman.sub.-- ShadowMap *map);
void print()
private
LazyShadow<Beta,B>beta; // was Beta *beta;
LazyShadow<Gamma,C>gamma; // was Gamma *gamma;
};
Alpha::Alpha(A *a, Roman.sub.-- ShadowMap *map)
:beta(a->get.sub.-- b(), map), // shadow call removed
gamma(a->get.sub.-- c(), map() // shadow call removed
{}
______________________________________
The method "GreekFromRoman.sub.-- ShadowMap::shadowA" remains unchanged. The implementation of "Alpha::print" also remains unchanged, because "beta" can be transparently converted to and used as a "Beta*" pointer, just as "gamma" can be converted to a "Gamma*" one. The first time "beta" is converted to a "Beta*" pointer, the call of "Beta::shadow(a->get.sub.-- b(), map)" will finally occur; however, subsequent uses of "beta" will bypass the call and will be almost as fast as using the evaluated pointer. Instantiating a shadow of a data structure(Or: What the end client actually needs to know.) Most of the apparatus needed to instantiate a shadow of a data structure in the preferred embodiment has been shown. Those skilled in these arts will recognize any number of alternative embodiments. However, in the preferred embodiment, additionally, to shadow a data structure a client needs the following: a root pointer to the data structure to be shadowed, or to a part of the data structure to be shadowed the shadow map subtype for the appropriate shadow type space The following is a typical code sequence used to instantiate a shadow:
______________________________________
A *a=. . .
// get pointer to data structure to be shadowed
Roman.sub.-- ShadowMap *map = new GreekFromRoman.sub.-- ShadowMap;
Alpha *alpha = Alpha::shadow(a, map);
//that's all there is to it
______________________________________
This works as follows: after getting a pointer to the node to be shadowed, the code creates an instance of the appropriate subtype of "ShadowMap", and then simply shadows the root pointer, using exactly the same method we have already seen when shadowing the child members of a node being shadowed. The result is that "alpha" is a root pointer to a shadow data structure as defined by the "GreekFromRoman.sub.-- ShadowMap" object. Once the node has been shadowed, it depends on the specification of "GreekFromRoman.sub.-- ShadowMap" as to when the map can be deleted. If the "alpha" shadow node has been fully evaluated, containing no internal lazy shadows and with no other implicit dependency on the map, then the map can indeed be deleted. However, a client may choose to keep the map available to shadow other nodes, in which case some or all of the saved entries in the map may speed up subsequent shadow operations. Additional Information for the Preferred Embodiment The above disclosure has given an overview of the entire mechanism, and details of what is needed both to make a data structure shadowable and to actually make a shadow. This section describes the glue code needed to make the various elements of code come together in the preferred embodiment. Following the execution of the two lines of example code from the previous page:
______________________________________
Roman.sub.-- ShadowMap *map= new GreekFromRoman.sub.-- ShadowMap;
Alpha *alpha = Alpha::shadow(a, map);
// that's all there is to it
______________________________________
Creating a shadow map The call of new "GreekFromRoman.sub.-- ShadowMap" constructs an instance of an implementation of a subtype of "ShadowMap" that can be used to generate a `greek` shadow of `roman` nodes. The call will automatically initialize a table in the ShadowMap base class that will be used to cache the results of calling the factory methods provided by the subtype. Creating a shadow node The shadow node is created by invoking the shadow method on the required type. This is a class-static method whose implementation is of the form:
______________________________________
T'*T'::shadow(T *x, TRoot.sub.-- ShadowMap *m)
return T'::narrow(m->lookup.sub.-- or.sub.-- create.sub.-- shadow(x))
;
}
______________________________________
The map is interrogated for the shadow of "x" by the call of "m->lookup.sub.-- or.sub.-- create.sub.-- shadow(x)". The result of "lookup.sub.-- or.sub.-- create.sub.-- shadow" is of type "Narrowable*", since the map cannot know the type that will actually be required. The result is therefore narrowed to the correct type by calling "T'::narrow". Assuming the shadow has been created correctly, this will give the required result. Otherwise, zero will be returned. Ignoring some minor complexity to deal with detecting cycles while creating shadows, the call of "lookup.sub.-- or.sub.-- create.sub.-- shadow" checks to see if a shadow node is already registered for the argument, and if not, it takes steps to create the shadow node. Somewhat simplified, the code looks like the following:
______________________________________
Narrowable *ShadowMap::lookup.sub.-- or.sub.-- create.sub.-- shadow(Shado
wable *sp)
Narrowable *np;
if(sp == 0)return 0;
if (|tbl->get.sub.-- shadow(sp, np)) {
np = sp->create.sub.-- shadow(this);
tbl->set.sub.-- shadow(sp, np);
}
return np;
}
______________________________________
The following notes are of interest in further explaining the above: tbl This represents the table that contains the results of earlier calls to lookup.sub.-- or.sub.-- create.sub.-- shadow. tbl->get.sub.-- shadow(sp, np) This looks up the shadow of "sp", sets "np" and returns TRUE if it is found, and otherwise leaves "np" alone and returns FALSE. tbl->set.sub.-- shadow(sp, np) This records "np" as the shadow of "sp". The major line that needs explaining is this one: np=sp->create.sub.-- shadow(this); This is the means by which the shadow mechanism correctly creates the appropriate type of shadow node, independently of the perceived type of the object. The client may have a "B*" pointer that in reality points to a "D" object. Nevertheless, the client may well invoke "Beta::shadow(b, map)" and will expect to receive a Beta object even though the real type of the object being shadowed is a D and the real type of the shadow node must be a Delta. "create.sub.-- shadow" is a virtual method of the node being shadowed. It is implemented for each type of object being shadowed, and looks like this:
______________________________________
Narrowable *D::create.sub.-- shadow(ShadowMap *map)
Roman.sub.-- ShadowMap *m = Roman.sub.-- ShadowMap::narrow(map);
return m->shadowD(this, map);
}
______________________________________
Note that the argument is only of type "ShadowMap*" and not of type "Roman.sub.-- ShadowMap*". This is a regrettable consequence of "create.sub.-- shadow" being inherited from "Shadowable", which only knows about "ShadowMap." When "sp->create.sub.-- shadow(this)" is invoked, the message will be received by the true type of the object, in its implementation of "create.sub.-- shadow." This knowledge of the true type is passed on to the map by invoking a method specific to the true type. This is the purpose of the call: m->shadowD(this) Since this is a call to shadow a "Roman" node (D), this is a method on the "Roman.sub.-- ShadowMap", which is the reason for the "narrow" call in the previous line of code. Note that map is not narrowed to the actual implementation type of the shadow map, since that is neither known nor necessary; it is merely narrowed to the type that defines the abstract methods to shadow the various types. Typically, the call of "m->shadowD(this)" will be implemented by a subtype of "Roman.sub.-- ShadowMap" that provides the knowledge of how to shadow a D node into the appropriate shadow type. In our running example, the call would be handled by "GreekFromRoman.sub.-- ShadowMap::shadowD", of which we have already seen the like. (See the discussion on the implementation of shadowA above.) The result of the shadow call on the map is of type "Narrowable*". The result is passed back to "ShadowMap::lookup.sub.-- or.sub.-- create.sub.-- shadow", which saves the value for future use, and returns it, still as a "Narrowable*", to the original call of shadow on the target type. This attempts to narrow to the appropriate type the value that has been passed back. If the narrow call succeeds, the client has the value that was wanted; if not, then zero is returned, which should be interpreted as meaning that either the item being shadowed was itself zero, or that the item cannot be shadowed to the requested type. If it is important to distinguish these cases, the client can easily check if the item being shadowed is zero or not. It is worth checking what happens in the face of inheritance and widened pointers. Assume the client has in his hand a B* pointer to a D object. As a B* pointer, it is to be expected that the shadow will be a Beta* pointer. Therefore, "Beta::shadow(b, map)" will be called. Assuming this is the first shadow call on "b", "ShadowMap::lookup.sub.-- or.sub.-- create.sub.-- shadow" will invoke "create.sub.-- shadow" on "b", which will be handled by the true type D, by way of the virtual function dispatch. This will call the factory to shadowD. Thus the shadow node will be created with the correct shadow type. The pointer to the shadow node (e.g. a Delta*) will be passed back as a "Narrowable*", and narrowed to Beta* in the code for "Beta::shadow". Thus the mapping between node type and shadow node type is maintained for both the true and perceived type of the objects involved. Who does what There are many different parts to the shadow system disclosed herein, with the code for the various parts being the responsibility of various different authors in the preferred embodiment. There are at least three authors involved: the author of the standard shadow code, the author of the data structure being shadowed and the author of the shadow data structure itself. In addition, some of the code can be mechanically generated by a special utility called autodefine which is described in Appendix B. Also described in Appendix A is additional explanatory information on the "Narrow" implementation used in the preferred embodiment. Referring to FIG. 19 a table describes the various components of the shadow system and identifies the responsibility for the various parts in the preferred embodiment. Default factory methods on a shadow map The disclosure of the preferred embodiment above described the actions necessary make a data structure shadowable, and introduced the need for a subtype of "ShadowMap" that declared a "shadowT" method for each class "T" in the data structure that needed to be shadowed. The disclosure above indicated that these methods could be pure virtual methods, and that the class could be automatically generated by "autodefine". The following illustrates how default methods on the "ShadowMap" subtype may be used to advantage. The examples so far have suggested that each type in the data structure has one or more corresponding types in the shadow data structure: examples of both 1-1 and 1-many mappings were illustrated. However, many-1 mappings (and even many--many mappings) are also possible. Consider the inheritance hierarchy 370 shown in FIG. 20. Nodes A 373, B 376, and C 378 inherit from "Roman" 372; and nodes C1 380, C2 382 and C3 384 inherit from C 378. For a particular shadow of a data structure built from these data types, it may be the case that we do not need to shadow all of the information in types C1 380, C2 and C3 384: it might be sufficient just to shadow the properties they have as C 378 objects. In order words, rather than shadowing C1 to Gamma1 C2 to Gamma2, and C3 to Gamma3, we wish to shadow all C nodes to Gamma nodes. Since we wish to shadow nodes of these types to Gamma nodes, it is appropriate to call "Gamma:: shadow (C*, Roman.sub.-- ShadowMap*)". Assuming this is the first shadow call on the C * argument, this will call through the virtual create.sub.-- shadow method, and that call will be received by the true type of the object: C1, C2 or C3. Whichever type receives the call will pass it on to the appropriate method on the factory: shadowC1, shadowC2 or shadowC3. If the methods on the "Roman.sub.-- ShadowMap" are all pure virtual methods, then they must all be separately implemented by the actual map used for the specific shadow. However, if the methods on "Roman.sub.-- ShadowMap" have a default implementation, then they do not need to be overridden in the actual map used. In this case, what is wanted is for shadowC1, shadowC2 and shadowC3 all to delegate to shadowC. This means that in the actual map to be used, only shadowC need be provided, and this can do what is necessary to shadow any C objects, whether they be C, C1, C2 or C3 objects. Based on this rationale, the following rule is implemented by autodefine in the present embodiment when generating the "TRoot.sub.-- ShadowMap" for a collection of types inheriting from TRoot. The default implementation for each shadowT method is to delegate to the immediate parent type, in the case of single inheritance, or to the leftmost immediate parent, in the case of multiple inheritance. ("Autodefine" in the preferred embodiment also has an option to make the methods on the "TRoot.sub.-- ShadowMap" class be pure virtual methods. It should also be noted that "autodefine", in the preferred embodiment, does not notice inherited template types.) The one exception is the shadowTRoot method, to which all methods will eventually delegate if not overridden, and this method will abort if invoked. It is up to the client to ensure that this abort does not get called: either by overriding it, or by ensuring that no instances of TRoot are allocated and that all subtypes of TRoot have overridden appropriate shadowT methods in the map. Shadows of shadows If some data structure is shadowed to yield a new data structure, there is no reason why that new data structure should not itself be shadowable. All that is required is that the base type of the nodes in the new data structure should inherit from Shadowable, and that the nodes should implement create.sub.-- shadow. A sequence of shadows could be used (for example) to represent the transformations involved in a compilation pipeline, going from syntax tree to machine code instructions. In this case, the job of fabricating the shadow nodes at each stage would probably be non-trivial, but there is no inherent reason why this could not be done. A variant of this is that a shadow might provide methods that, when invoked, cause a different data structure to be created, and this resultant data structure might itself be shadowable. Passing extra parameters to the shadow call When shadowing a node, it is sometimes useful to be able to pass additional information to the call that will fabricate the shadow node. This may be information needed globally by the whole shadow (such as a window handle or error stream) or it may be needed by a specific type and a specific shadow call. If this is necessary, such information can be stored as instance data of the actual implementation of the ShadowMap. This means that the information will be available in any call of shadowT that may subsequently be invoked. Information that is global to the shadowing process can be stored as instance data in the map when the map is constructed. Information that is needed on a per-node basis requires a little more care. The easy solution is to provide access methods on the factory that directly allow the extra instance data to be accessed and modified throughout the shadowing process. However, if this technique is used, there is a serious potential for an undetected programmer error. Consider the following scenario:
______________________________________
Inside some call of "Tx': : shadow Tx *X, TRoot.sub.-- ShadowMap *map)"
set instance data "d" on the map: "map->set.sub.-- data(d)"
call "Ty': :shadow(y, map)" to shadow some child "y"
______________________________________
The problem is that there is no inherent guarantee that the final call of "Ty'::shadow (y, map)" will see the data "d". If by some programmer error the shadow call has already been executed for the value y, then an entry will exist in the map and subsequent calls will return that value, and will not go through the factory method and pick up the data. In addition, it is clumsy for the client to have to call two methods: one to set the data and another to shadow the desired node. What is required is a slightly different mechanism that is easier to use and which provides better semantic guarantees. In the preferred embodiment, the solution is to provide methods on the map that set the instance data and shadow the node in one single operation. Since the reason for these methods is to have extra shadow-specific parameters, these are methods defined directly on the implementation of the shadow map, and are not inherited at all. For example, the lines above could be replaced by a method defined as follows:
______________________________________
class TRoot'.sub.-- from.sub.-- TRoot.sub.-- ShadowMap
public:
Ty' *create.sub.-- Ty.sub.-- shadow(Ty *y,Data *d);
// rest of class. . .
private:
Data *data.sub.-- for.sub.-- dreate.sub.-- Ty.sub.-- shadow;
};
______________________________________
The implementation of Ty' *create.sub.-- Ty.sub.-- shadow(Ty *y, Data *d) can set the instance variable "data.sub.-- for.sub.-- create.sub.-- Ty.sub.-- shadow" and must then cause a shadow to be created. Whilst it can do that by explicitly calling Ty'::shadow(y, map) there is another method on ShadowMap that is more suitable. Internally, "Ty'::shadow(y, map)" calls Ty'::narrow (map->lookup.sub.-- or.sub.-- create.sub.-- shadow (y)) and as we have seen, this returns the value stored in the map if it already exists. The alternative is to replace the call of "Ty'::shadow (y, map)" by the following y'=Ty'::narrow (map->create.sub.-- shadow (y)); The call of "map->lookup.sub.-- or.sub.-- create.sub.-- shadow(y)" has been replaced by a call to the sibling method "map->create.sub.-- shadow(y)", which still looks up y in the map, but this time to check that no value is already stored in there. It is a run-time error if a value is found. Assuming no entry is found, the code will then internally call y->create.sub.-- shadow (map) which, as before, will call back into one of the shadowT methods on the map. These all have access to the data d and can fabricate the shadow node correctly, based on the type of the node and the contextual information passed in from the client. The name "create.sub.-- Ty.sub.-- shadow" is the choice of the author of the shadow map implementation class, in this case "TRoot'.sub.-- from.sub.-- TRoot.sub.-- ShadowMap". It is specific to the implementation class and not inherited at all. It is suggested that it not be an overloaded name in case the implementation class is ever extended by implementation inheritance to shadow even more types. Although the present invention has been described with reference to particular operating systems, compilers, program code mechanisms, and object and object reference definitions, it will be appreciated by one skilled in the art that the present invention may be implemented in any one of a number of variations within a given operating environment, or in different operating system or object system environments. Similarly, particular computer client and server configurations or combinations illustrated are only representative of one of many such configurations of clients and servers and object and sub-object relationships which may use the present invention. Moreover, it will be understood that the figures are for illustration only and should not be taken as limitations on the invention. Some additional applications of the shadows techniques disclosed herein include the following: A compiler's ASG can be shadowed with a data structure that more closely matches the requirement of a code generator. (For example, additional methods may be added to nodes to translate the program fragment represented by the node to machine code.); A compiler's ASG can be shadowed with a data structure that provides browsing capabilities over the program; A compiler's ASG can be shadowed with a data structure that enables the ASG to be edited. The shadow nodes would contain some textual rendition of the nodes, the text could be edited, and then parsed back to an ASG; A compiler's ASG can be shadowed with a data structure that can be used as the input to an interpreter, to execute the program; The schematics for the design of an integrated circuit can be represented as a connected collection of typed objects. Such data structures could be made shadowable to permit an extensible collection of tools to manipulate the data structure. For example, such tools as various design rule checkers for different manufacturing processes could be used. As another example the data structure may be shadowed into the form of data structure representing the information needed for a particular foundry to manufacture the chip; Today, word processors manipulate complex structured documents. By making the document structure shadowable, various tools can be added to process the document, without building these tools into the one word processing program. Such tools might be style checkers, spelling checkers, cross-referencing programs, index construction, and converting to formats for other word processing programs. These possible uses of the Shadow technique are not intended to limit in any way the possible uses of the Shadow functions as disclosed herein, but merely represent some examples which those skilled in these arts will recognize as merely exemplary.
|
Same subclass Same class Consider this |
||||||||||