Method of controlling the execution of object-oriented programs

Description Submit all comments and votes

TECHNICAL FIELD

This invention relates to computing.

BACKGROUND AND PROBLEM

A debugger is a tool that aids software development by giving a user control over and access to a running program. Debuggers typically run as self-contained processes, controlling the program under study--the so-called application process--through operating system primitives designed for that purpose. A simple application program typically consists of data, and functions that operate on those data. Data and functions are defined in a source file created by the programmer. Each datum is associated with a type that describes its internal structure and behaviors; for example, integers may be 16 bits long, and may be added, subtracted, multiplied, etc. A tool called a compiler or translator reads a source file and produces an object file. The compiler typically works in conjunction with other tools-assemblers, linkers, and optimizers-to accomplish this task, and such ancillary tools are usually invisible to the programmer.

The object file contains bits which can be loaded into computer memory and executed; these bits include both the data and the machine instructions generated from the original program. These bits, when loaded into memory, are called the program image. In most systems, there is a close mapping of program image onto what the user perceives as a user process. The object file also contains a table that maps some of the original source information, as variable and function names, onto addresses, offsets, sizes, and other pertinent properties of the program image. This so-called symbol table is usually not made part of the program image itself, but remains in the object file where other programs (like the debugger) can read and analyze it.

A debugger is used to examine the program image of a program in execution, and to control the execution of the program. Because the debugger has access to the symbol table, it allows the user to interact with the target process in terms of the names found in the source code. For example, if the user knows the name of a variable, they can ask the debugger to retrieve that variable's current contents from the program image or from storage dynamically allocated at run time by giving the variable's name. By going to the symbol table and looking up the variable's address and type, the debugger obtains the information it needs to satisfy the user request. An analogous scenario might allow the user to modify the value of a variable's contents on the fly. These are usually done while the target program is stopped.

Debuggers are most often used to intercept or monitor the thread of control through a running program. It is usually the case that one or the other of the debugger or the target program are active, but not both. If the target is running, the user can interact directly with it while the debugger lies dormant. If the debugger is running, the user has its attention and the application target is usually stopped; i.e., its program counter advances no further. When the debugger is running, it is said to be in control; when the debugger causes the target to begin (or resume) execution, it relinquishes control.

The debugger can arrange to regain control when the target program counter reaches some pre-specified address. The debugger can deposit a machine instruction at that address, designed to cause some trap or to cause an operating system service to be called when it is executed. By virtue of prior arrangements between the debugger and the operating system, two things happen when the target reaches one of these instructions: 1) execution of the target process is put aside (i.e., the target process is stopped); and 2) the debugger is notified of the event and gains control. The debugger is able to determine the location of the event by examining program image state information saved by the operating system. Such special instructions, or the locii of such instructions, are called breakpoints. The event of execution arriving at a breakpoint is called the firing of a breakpoint.

Breakpoints are usually set at the direction of a user, who may want to know if and when execution reaches a certain point in a program, and may further wish to examine state information after the breakpoint fires. The user specifies where to insert the breakpoint: it may be on entry to a function, or at a location corresponding to some line number in the source code. The symbol table can be used to map function names and line numbers onto program image addresses. Some debuggers allow additional types of breakpoints, e.g., on return from a function.

There is a direct mapping between the structure of the source, and the structure of the program image, when a simple procedural language such as C, FORTRAN, or Pascal is used. If there is a function f in the source, then there is code for f in the program image. Furthermore, both of these structurings map directly onto the abstractions a programmer deals with in creating and administering a program. For example, if a function appears in the source, it will appear in the program image as a likewise contiguous entity.

However, with object-oriented languages such as C++, it is useful to think of objects as associating themselves with different functions over the execution of the program. For example, a window variable may be used for a window based on one set of functions at the beginning of the program, and a different set of functions later on. These functions may correspond to, for example, different hardware windowing technologies that are connected to the system where the program is running. The major strength of object-oriented programming is in the way it combines inheritance with run-time operator identification using virtual functions. The specific identity of a virtual function when invoked by name is to be determined at run time as a function of the object with which it is associated. In debugging object-oriented programs, it would be desirable to allow a user to insert a breakpoint that will fire whenever a specified virtual function is invoked on a specified object. However, since the symbol table is generated as part of program compilation, it cannot include sufficient information to determine where to insert the breakpoint. Thus, known debuggers that rely on only symbol table information to determine breakpoint addresses are not able to insert breakpoints that fire under conditions involving a run time association of functions with objects.

SOLUTION

This deficiency of the prior art is eliminated and a technical advance is achieved in accordance with the principles of the invention in an exemplary method used by a digital computer in controlling execution of an object-oriented program to effect a defined action, e.g., stopping the program, when a specified virtual function is invoked on a specified object during execution of the program. A breakpoint address is determined at run time, advantageously after the specified object is created in accordance with execution of the program. The breakpoint address determination is not based solely on symbol table, pre-execution, information, but in addition on information generated in conjunction with the creation of the specified object. The breakpoint is inserted while program execution is stopped at an intermediate program point after the specified object is created. After program execution is resumed and the specified virtual function is invoked in accordance with the program, the breakpoint fires. However, the defined action is performed only in response to determining that the firing occurred on the specified object.

In a method in accordance with the invention, execution of an object-oriented program is initiated and a specified object is created during execution of the program. After the specified object is created, a determination is made of the address of a function that is called when a specified virtual function is invoked on the specified object. A breakpoint is inserted at the determined function address.

Illustratively, the address determination can be made by obtaining the address and base type of the specified object. Using that information, a virtual function table is located for the specified object. The determined function address is obtained as an address from the virtual function table that maps, via a predefined address to function mapping, into the specified virtual function.

In a specific exemplary debugger embodiment for use with C++ programs, the symbol table generated as part of program compilation defines an address and a type for each program variable, where one of the program variables is a pointer to the specified object. The symbol table is used to determine the address and the type of the pointer variable. The contents of the determined pointer variable address are read to obtain the address of the specified object. Using the determined pointer variable type and the obtained object address, a virtual function table is located for the specified object. The virtual function table contains addresses for virtual functions. The determined function address is obtained as an address from the virtual function table, that maps, via a predefined address to function mapping, into the specified virtual function. A breakpoint is inserted at the determined function address and an entry is stored in a breakpoint table. The entry defines the determined function address and the obtained object address for the breakpoint. When firing of a breakpoint is detected after program execution is resumed, the address of the detected breakpoint and the address of the present object are ascertained. Only when the ascertained breakpoint address and present object address respectively correspond to the function address and object address of the entry in the breakpoint table, is the defined action performed. The method of processing breakpoints is also applicable to breakpoints on non-virtual functions.

A method, applicable to object-oriented programs which use parametric polymorphism, is used in controlling execution of a program to effect a defined action when a specified function is invoked with a specified argument. Execution of the program is initiated and an object is created. Thereafter, a determination is made of the address of a function that is called when the specified function is invoked with the specified argument and the specified argument is associated with the object. A breakpoint is inserted at the determined function address. After program execution is resumed and the specified function is invoked with the specified argument in accordance with the program, the breakpoint fires. However, the defined action is performed only in response to determining that the firing occurred on the object.

DRAWING DESCRIPTION

FIG. 1 is a diagram illustrating the elements of a computer system comprising a processor, memory, and disk;

FIG. 2 is a diagram illustrating elements stored in the memory of FIG. 1 that are used to implement the exemplary debugger embodiment sdb++ of the present invention;

FIG. 3 is a diagram showing the contents of a symbol table and program image stored in the disk of FIG. 1;

FIGS. 4-9 are diagrams illustrating a number of basic concepts of object-oriented programming;

FIG. 10 is a sequence diagram illustrating the operation of the exemplary debugger embodiment in inserting and processing breakpoints on nonvirtual functions; and

FIG. 11 is a sequence diagram illustrating the operation of the exemplary debugger embodiment in inserting and processing breakpoints on virtual functions.

Detailed Description

The description which follows is arranged in three parts: 1) a number of basic concepts of object-oriented programming are discussed to aid in understanding the description of the exemplary debugger embodiment sdb++ of the present invention, 2) several key definitions are provided, and 3) the specific methods of the exemplary debugger embodiment sdb++ in inserting and processing breakpoints on both virtual and non-virtual functions are described. The programming language used herein is C++, as described in the 1989 book of Stanley B. Lippman, "C++ Primer". C++ is based on the C language which is described, for example, in the 1983 book of Stephen G. Kochan, "Programming in C".

Basic Concepts

The approach described herein is suitable for programs, referred to as "processes" in some contexts, that run on a digital computer 100 (FIG. 1). The steps for carrying out the tasks to be done by computer 100 are kept as encoded instructions in a memory device 110; the contents of memory device 110 are examined by a processor 120 which interprets them to carry out actions using its own internal machinery, devices, and functions. The collection of steps controlling this process are commonly called a program. Data values (inputs, interim values, etc.) are also maintained in memory device 110; they can be deposited there by processor 120, or examined at will by processor 120.

A secondary memory device, disk 200, keeps programs until they are needed for execution, at which time they are brought into memory 110 where they can be directly accessed by processor 120. Disk 200 (FIG. 3) holds not only the bits that represent the program control steps, for example, executable program image PI, but also may hold a symbol table for each program, for example, table ST, that ties its bits back to the information that was in the original program typed in by a person. Symbol table ST is used--usually by other programs such as linkers or debuggers--to interpret variable or function names as addresses in the running program. The columns of symbol table ST are characterized as follows:

1. NAME: For variables, this is their name, either per se or with some simple encoding done by the compiler. For functions, it is a name in which the function signature has been encoded by the compiler. For types, particularly for structure definitions, it is the corresponding C type or structure name.

2. TYPE: This indicates the C language primitive type, or derived type, as appropriate, for the entity named in the NAME column.

3. CLASS: This is a basic designation of what the entry represents: a function, a structure, a structure member, a local variable, etc. The use of the term "class" here is unrelated to the use of the same word to describe a user-defined type.

4. ADDRESS: The address, or offset, as appropriate, of the symbol defined in this entry. For types, which in and of themselves take no storage, the size is given in this field.

5. LINK: A pointer to an associated "parent" entry in the symbol table. For example, all structure members "point" to their structure declaration entry.

Processor 120 selects which parts of memory device 110 it reads and writes using an address it gives to memory device 110 along with its request to read or write. Usually, the reading and interpretation of an encoded instruction at some address will cause processor 120 to fetch a subsequent instruction, either at the following address or some other address.

To learn about the behavior of a program, it is often instructive to monitor its progress during execution. This can be done by arranging for the program to stop at prearranged points in its sequence of steps, at which time memory data contents can be examined. Such points are called breakpoints. A succession of arrivals at such points gives the programmer a feel for the flow of the program, and the data contents tell of its progress and intermediate results.

A user application program 112 (FIG. 2) under study is controlled and observed by another program, debugger 111. Debugger 111 coexists in memory device 110 with application program 112. The debugger contains its own control logic DCL, i.e., sequences of instructions for controlling its behavior, as well as its own data. The data include a breakpoint table, BT, having an entry for each of the breakpoints that have been inserted in application program 112. Breakpoint table BT contains information that allows each breakpoint to be interpreted in a number of ways, depending on the context of the application program when the breakpoint is reached.

The present approach focuses on applications made up of objects, instances of abstract data types that can be thought of as self-contained modules that specialize in performing some task. The objects are not physically self-contained; their data are in one place, and the instructions (text) elsewhere. The program text for a group of like objects (objects of the same type) is shared across all such objects. It is useful to think of objects as associating themselves with different functions over the execution of a program. For example, a window variable may be used for a window based on one set of functions at the beginning of a program, and a different set of functions later on. These functions may correspond to, for example, different hardware windowing technologies that are connected to the system where the program is running. There is a loose association between the objects and their program text, which is determined at run time through tables in the application program image. Debugging such programs offers a special challenge, since information generated by the compiler and typically available to a debugger cannot reflect the run-time dynamics of all but the most trivial programs. The debugger needs to determine the association between objects and their operations at run time, and that is what is addressed by the approach described here.

In the programming paradigm described above, all functions and most data (local function variables being the exception) are thought of as having their structure reflected in the source. Data abstraction presents an alternative model that is more dynamic: the programmer thinks of their source code as a description of templates that are used to stamp out actual incarnations, at run time. The templates have the characteristics of programming language types, and are called abstract data types, or ADTs. An ADT contains a template describing what data fields will be in a variable of that type. It also contains (semantically) the definitions of functions tightly associated with that type. These functions can be thought of as implementing the operations on that type, and the functions themselves are called methods or member functions. Such a facility makes user-defined types possible.

The language provides facilities for creating variables of these types. More precisely, these incarnations that can be "stamped out" by the type are called objects, and this term is usually associated with the "variables" that come from ADTs. Another name for an ADT is a class, which is related to the use of such abstractions in object-oriented programming. The process of making an object from a class is called instantiation.

The user model of objects may be that each one contains its own data, and its own copy of the member functions, as specified in the object's class. To refer to a datum inside an object, or to name one of its functions, requires two names: one to specify the object, and another to specify the named member. Thus, if s1 and s2 are both Stacks, and if a Stack contains an integer named index, then s1.index and s2.index represent two distinct entities in memory. Similarly, the user may think of s1.pop() and s2.pop() as calling distinct functions.

In an analogous example, illustrated in FIG. 5, each Sunview Window and XWindow contains a variable field named color and a function named refresh. In this example, it is not sufficient to simply refer to color; to characterize the color, it is necessary to name the class that contains it; that gives its type, and therefore its size, behaviors, etc., as well as its offset from the beginning of an object that might contain it. To get the value of any particular color thus characterized, the address of the object containing it is specified; together with the information about its characteristics, which are specific in the context of a given class, a debugger can use this address to retrieve or set the particular variable of interest. The same is true for member functions like refresh, where it may be helpful to insert a breakpoint for use in debugging the program.

Thus, data abstraction makes invocation of the same name possible in different objects having a common type. But it also allows a user to define a field (operation or instance variable) of the same name on multiple distinct types. Consider two unrelated classes, Stack and Table, each of which has a field (also called a member) named index. The object s is of class Stack, and object t is of class Table. These fields may have different offsets, or even different types, and the debugger must be able to disambiguate between them, as described below.

It is important to point out that actual implementation may not reflect the model. For example, some object-oriented languages are implemented using preprocessors that generate low level language text (e.g., C) as object code. There must be a way to reasonably map the structure of abstraction onto the low-level code without violating the rules of the low-level language. For this reason, most names inside an ADT are mapped to names that reflect the abstraction containing them. (This particular measure is not necessary in the case of simple ADTs, but becomes important when ADTs are combined in inheritance, and disambiguation of names is necessary inside the new abstraction.) For example, the variable index may be called .sub.-- index.sub.-- 5Stack.sub.-- inside class Stack, and.sub.-- index.sub.-- 5Table.sub.-- inside class Table. The debugger must deal with this to give a feel of working in a truly object-oriented environment. An important part of the job of a debugger for object-oriented languages is to convert a user-supplied expression of the form aStack->index (where aStack is assumed to point to an instance object of class Stack) into the expression aStack->.sub.-- index.sub.-- 5Stack.sub.--. It does this by finding the type of aStack, and using the resulting type name to construct the name of the member. The functions for doing this are well known.

Related to multiple names in abstraction scopes is the issue of dealing with overloading, using the same name for different functions. Within any given class, there may be, for example, two functions named print as shown in Table 1.

TABLE 1 ______________________________________ class Foo { public: void print(int); void print(char*); }; ______________________________________

If the user expresses a desire to insert a breakpoint on Foo::print, there is obviously an ambiguity. One way to resolve this ambiguity is to force the user to type a complete signature for the function they want to choose; i.e., to type the complete function declaration, including its name and arguments. For functions with many or complicated arguments, this is tedious and error-prone. Another tact is to search the symbol table for all functions that match the basic pattern suggested by the userspecified name, and to let the user refine that search by selecting the proper one from a menu built by such a search. This is the approach taken in sdb++.

Another way that implementation may not directly reflect the model is in function sharing. Assume the programming language does not allow modification of its functions as a side-effect of execution. Then it is possible in most environments for all objects of a given class to share the same member function text--they are all identical. The only requirement is that such functions be re-entrant (so multiple objects can simultaneously have activation records open on a single given function). This in fact is done in most environments supporting data abstraction and object-oriented languages.

FIG. 4 illustrates abstractions from both the implementation and user perspective for a language such as C++ using a typically available compiler. From an implementation perspective, the application target program (or process) can be viewed as a collection of functions and data. In a procedural language, each source function is reflected in the program as a contiguous block of memory, and each datum likewise occupies some space in memory (except for local data on stack machines, which are allocated automatically on the fly as functions are entered). In an abstract data language, all objects of a given type (ADT) share their functions. So if a program is modeling terminal window abstractions using a class Window, all individual Window objects (variables) would share the same functions that implement the functions for clearing, drawing, moving, etc. All functions for class Keyboard would also be shared by all Keyboard objects, probably in a way that does not overlap anything of Window's. If there are two windows, window1 and window2, each of those will get its own data block in memory. Likewise, there may be an object for the console's Keyboard object; it would also get its own block of memory. These memory blocks contain the data prescribed by the data declarations in the the corresponding classes. The variables inside a class are called instance variables or just instances. The class can be thought of as a factory that creates a new instance every time a new object is declared or dynamically created.

However, the user view of these abstractions may differ from the implementation. They may view class Window as a template that manufactures a self-contained object, complete with space for its own instance variables, as well as a copy of the functions prescribed for that object in the class. This allows the user to think of each object as an intelligent agent that can be asked to perform some task. The object can be "personified" as a "specialist" that acts autonomously on the behalf of another object when asked to do so. The fact that functions are shared for objects of like class is invisible and in fact usually irrelevant at the user level. The commonality does become an issue in debugging two different objects of the same class at the same time: modifications to their shared text (e.g., to insert a breakpoint) will cause what is done in the name of one object to interfere with the others (i.e., by causing the specified breakpoint to happen for all of them).

Object-oriented programming offers a level of abstraction above that provided by ADTs: the ability to group classes themselves into yet more abstract classes. Furthermore, object orientation makes it possible to address objects of specific types in terms of the interface of any of the more highly abstract types which derive those objects' type. The example of FIG. 5 illustrates the utility of this property.

Assume that a class XWindow is used to implement the semantics for manipulating a window created using the X window system. It contains declarations of instance data that hold information pertinent to the details of maintaining windows: pixel depth, color, etc. The class also defines the functions to do what needs to be done to X windows: refresh, create, delete, and so forth.

There is a second class, Sunview Window, which is similar, but which serves to communicate with windows running in a different environment or perhaps on a different kind of terminal or work station. It, too, has its instance data-those pertinent to Sunview technology, in this case-and also has functions defined to carry out the details of refreshing, creating, and deleting Sunview windows; one may also be able to iconify them, and there is a function for that. Except for the latter function, it is noted that SunviewWindow exhibits behaviors, as defined by its member functions, that closely mimic those of XWindow. That is no surprise, since they are both windows. In fact, it is recognized that there is a more general abstraction called Window of which both XWindow and SunviewWindow are specializations. Window tells what all windows, in general, do.

In addition to that, it is noted that all windows have a position and a size, and that such parameters might be specified in a fashion independent of their implementation technology. These properties can be thought of as belonging to Window instead of to the particular specialized classes. They appear as instance data in the general Window class itself.

In fact, even some behaviors of all windows may be able to be completely specified in terms of the other behaviors, in a way that is technology-independent. For example, move might be implemented by redefining the value of Window's position instance variable to take on the value passed as an argument, after which the draw operation is invoked.

The classes XWindow and SunviewWindow are said to be derived from class Window. Everything that a Window has inside of it, they get. Whatever interface a Window has, XWindow and SunviewWindow must adhere to, though they can extend it. A class that derives some of its properties from another is called a derived class or subclass; a class that serves as a base for derivation by others below it is called a base class or superclass. The derivation relationship between these classes is specified in the programming language as given by the code in Table 2. (The code of Table 2 is not syntactically perfect C++, and should be regarded as pseudo-code).

TABLE 2 ______________________________________ class Window { public: virtual void move( ); virtual void refresh( ); virtual void create( ); virtual void delete( ); private: Position position; Size size; }; class XWindow: public Window { public: void refresh( ); void create( ); void delete( ); private: XGCvalues gcontext; Depth pixdepth; XColor Color; }; class SunviewWindow: public Window { public: void refresh( ); void create( ); void delete( ); private: Attr.sub.-- avlis attributes; Pixrect winPixrect; int color; }; ______________________________________

A window of a specific type can often be treated as though it were of the more general Window type. For example, a variable declared to point to a Window might be initialized to point to a newly created XWindow. This is not a type problem; because XWindow is a subtype of Window, the assignment is legal, for much the same reason that assignment of an 8-bit integer into a 16-bit integer is legal in most languages. FIG. 6 illustrates some Window pointers being set up just in this fashion, to point to windows of specific types. The code is given in Table 3.

TABLE 3 ______________________________________ Window *window1 = new SunviewWindow; Window *window2 = new XWindow; ______________________________________

Now assume there is a function zurbitz (Table 4) which is designed to operate on any kind of window. It takes a window, and prints "hello world" in it.

TABLE 4 ______________________________________ void zurbitz(Window *aGenericWindow) { aGenericWindow->draw("hello world"); ______________________________________

It is legal to invoke the calls of Table 5.

TABLE 5 ______________________________________ zurbitz(window1); zurbitz(window2); ______________________________________

In the first case, zurbitz will determine at run time that it has to invoke SunviewWindow's draw function, though it has no compile-time basis for making that decision. In the second case, a similar run-time decision is made, ending up inside XWindow's draw. There needs to be information inside each object that gives zurbitz enough information about its type for that or any analogous function to make a decision about what to do. In addition, there have to be data structures and conventions known by the compiler to make it possible to get to the right operation at run time.

This "lookup" of type information only is done in C++ for virtual functions. This implements a degree of polymorphism, called inclusion polymorphism, in object-oriented languages, and is the keystone to object orientation. A virtual function of Window is one that Window asserts as not being its own; i.e., as being defined in the derived class. If a function is virtual, then the determination of which function to call is made on the basis of the type of the object, the type which was used to create it. This type is somewhat independent of the type declaration of the variable that names the object. (The variable is typically declared as a pointer to a superclass of the object's class). In C++, if the function is not virtual, then the determination of which function to call is made at compile time based on the type of the pointer or variable being used to invoke the function, instead of the type of what is actually pointed or referred to.

When the compiler analyzes the template specified by a user for some class, it may add some housekeeping information of its own to manage the run-time operator lookup described above. This information maps directly onto the class or type of the object, and can be found in all objects that are being used in an objectoriented fashion (i.e., those that are from classes having virtual functions).

The most important piece of information put into an object is a pointer called the virtual function pointer. This pointer references a table; the table comes from a class, and contains the addresses of that class's functions. The table is generated automatically by the compiler, as is the insertion of the pointer in the object. The initialization of the pointer's contents are also arranged by the compiler to take place properly when a new object of a given class comes into being. Note that all objects of like class will have the same contents in their pointer field.

Another key point is that all classes in a derivation hierarchy will specify that this function table pointer be at the same offset from the beginning of the class. The offset can be set as being "just beyond" the data of the base-most class. (Actually, it will come "just beyond" the data of that class highest in the derivation hierarchy, all of whose superclasses contain no virtual functions, and the pointer is positioned subject to other byte alignment constraints imposed by the computer's architecture.) Instance data from classes farther down the inheritance tree will be appended to the instance following the pointer; note that additional levels of derivation do not affect the offset of the pointer. That means that if a base class pointer points to an object of any class in that derivation tree, the function table pointer can be found given the address of the object. For objects of different classes in a hierarchy, the value of this pointer will be different, and that is how the operator invocation mechanism determines how to call the right function at run time.

Within a derivation hierarchy, all functions of the same signature have the same virtual function pointer table index assigned to them. By signature, what is meant is basically the func