Method and system to handle context of interpretation in a document processing language

What is claimed as new and desired to be secured by Letters Patent of the United States is:

1. A computer implemented method for processing a hierarchically structured document, comprising the steps of:

creating a first data structure having a first set of information;

creating a first reference to the first data structure, said first reference to the first data structure being associated with a structure portion of a predetermined hierarchical level of the document;

creating, for said predetermined hierarchical level of the document when a content portion of said predetermined hierarchical level is processed, a second data structure which has a second reference thereto and copying the first set of information to a second set of information of the second data structure;

processing said content portion of said predetermined hierarchical level using the second reference to said second set of information;

determining if processing of content for said predetermined hierarchical level is finished;

processing a structure portion of a first subsequent hierarchical level, wherein said first subsequent hierarchical level is lower in the hierarchical structure of the document than the predetermined hierarchical level;

copying the first reference to a third reference associated with the structure portion of the first subsequent hierarchical level;

processing a structure portion of a second subsequent hierarchical level, wherein said second subsequent hierarchical level is lower in the hierarchical structure of the document than the first subsequent hierarchical level;

creating, for said second subsequent hierarchical level of the document when a content portion of said second subsequent hierarchical level is processed, a third data structure referenced by a fourth reference and copying the set of information referred to by the third reference to a third set of information of the third data structure;

processing said content portion of said second subsequent hierarchical level using said third set of information;

determining if processing of said content portion of said second subsequent hierarchical level is finished; and

copying the fourth reference to the third reference, when said processing of said content portion of said second subsequent hierarchical level is determined to be finished.

2. The method according to claim 1, further comprising the step of:

creating an entry in a stack for the predetermined hierarchical and the first subsequent hierarchical levels of the document, each entry in the stack including a reference to a set of references corresponding to structure of a corresponding hierarchical level and used during processing of the corresponding hierarchical level, and including a reference to a set of references corresponding to content of a corresponding hierarchical level and used during processing of a content portion of the corresponding hierarchical level.

3. A method according to claim 1, wherein said hierarchically structured document is a document which conforms to rules of a Standard Page Description Language.

4. A method according to claim 1, wherein:

said step of copying the fourth reference to the third reference copies a reference which is one of a reference to a state variable table and a reference to a dictionary which includes key-value pairs.

5. A computer implemented method for processing a hierarchically structured document, comprising the steps of:

creating a first data structure having a first set of information;

creating a first reference to the first data structure, said first reference to the first data structure being associated with a structure portion of a predetermined hierarchical level of the document;

creating, for said predetermined hierarchical level of the document when a content portion of said predetermined hierarchical level is processed, a second data structure having a second reference thereto and copying the first set of information to a second set of information of the second data structure;

processing a structure portion of a subsequent hierarchical level, wherein said subsequent hierarchical level is lower in the hierarchical structure of the document than the predetermined hierarchical level;

determining if processing of content for said predetermined hierarchical level is in process;

copying the second reference to a third reference associated with structure of the subsequent hierarchical level, when said processing of content for said predetermined hierarchical level is determined to be in process;

copying the first reference to the first data structure to the third reference associated with the structure of the subsequent hierarchical level, when said processing of content for said predetermined hierarchical level is determined not to be in process;

creating, for said subsequent hierarchical level of the document when a content portion of said subsequent hierarchical level is processed, a third data structure referenced by a fourth reference and copying the set of information referred to by the third reference to a third set of information of the third data structure; and

processing said content portion of said subsequent hierarchical level using said third set of information; and

continuing processing of said content portion of said predetermined hierarchical level after processing of said content portion of said subsequent hierarchical level is complete, using said second reference to said second data structure containing said second set of information, when said processing of content for said predetermined hierarchical level is determined to be in process.

6. A method according to claim 5, wherein said hierarchically structured document is a document which conforms to rules of a Standard Page Description Language.

7. An apparatus for processing a hierarchically structured document, comprising:

means for creating a first data structure having a first set of information;

means for creating a first reference to the first data structure, said first reference to the first data structure being associated with a structure portion of a predetermined hierarchical level of the document;

means for creating, for said predetermined hierarchical level of the document when a content portion of said predetermined hierarchical level is processed, a second data structure which has a second reference thereto and copying the first set of information to a second set of information of the second data structure;

means for processing said content portion of said predetermined hierarchical level using the second reference to said second set of information;

means for determining if processing of content for said predetermined hierarchical level is finished;

means for processing a structure portion of a first subsequent hierarchical level, wherein said first subsequent hierarchical level is lower in the hierarchical structure of the document than the predetermined hierarchical level;

means for copying the first reference to a third reference associated with the structure portion of the first subsequent hierarchical level;

means for processing a structure portion of a second subsequent hierarchical level, wherein said second subsequent hierarchical level is lower in the hierarchical structure of the document than the first subsequent hierarchical level;

means for creating, for said second subsequent hierarchical level of the document when a content portion of said second subsequent hierarchical level is processed, a third data structure referenced by a fourth reference and copying the set of information referred to by the third reference to a third set of information of the third data structure;

means for processing said content portion of said second subsequent hierarchical level using said third set of information;

means for determining if processing of said content portion of said second subsequent hierarchical level is finished; and

means for copying the fourth reference to the third reference, when said processing of said content portion of said second subsequent hierarchical level is determined to be finished.

8. The apparatus according to claim 7, further comprising:

means for creating an entry in a stack for the predetermined and the first subsequent hierarchical levels of the document, each entry in the stack including a reference to a set of references corresponding to structure of a corresponding hierarchical level and used during processing of the corresponding hierarchical level, and including a reference to a set of references corresponding to content of a corresponding hierarchical level and used during processing of a content portion of the corresponding hierarchical level.

9. The apparatus according to claim 7, wherein said hierarchically structured document is a document which conforms to rules of a Standard Page Description Language.

10. The apparatus according to claim 7, wherein:

said means for copying the fourth reference to the third reference copies a reference which is one of a reference to a state variable table and a reference to a dictionary which includes key-value pairs.

11. An apparatus for processing a hierarchically structured document, comprising:

means for creating a first data structure having a first set of information;

means for creating a first reference to the first data structure, said first reference to the first data structure being associated with a structure portion of a predetermined hierarchical level of the document;

means for creating, for said predetermined hierarchical level of the document when a content portion of said predetermined hierarchical level is processed, a second data structure having a second reference thereto and copying the first set of information to a second set of information of the second data structure;

means for processing a structure portion of a subsequent hierarchical level, wherein said subsequent hierarchical level is lower in the hierarchical structure of the document than the predetermined hierarchical level;

means for determining if processing of content for said predetermined hierarchical level is in process;

means for copying the second reference to a third reference associated with structure of the subsequent hierarchical level, when said processing of content for said predetermined hierarchical level is determined to be in process;

means for copying the first reference to the first data structure to the third reference associated with the structure of the subsequent hierarchical level, when said processing of content for said predetermined hierarchical level is determined not to be in process;

means for creating, for said subsequent hierarchical level of the document when a content portion of said subsequent hierarchical level is processed, a third data structure referenced by a fourth reference and copying the set of information referred to by the third reference to a third set of information of the third data structure;

means for processing said content portion of said subsequent hierarchical level using said third set of information; and

means for continuing processing of said content portion of said predetermined hierarchical level after processing of said content portion of said subsequent hierarchical level is complete, using said second reference to said second data structure containing said second set of information, when said processing of content for said predetermined hierarchical level is determined to be in process.

12. The apparatus according to claim 11, wherein said hierarchically structured document is a document which conforms to rules of a Standard Page Description Language.

Description Submit all comments and votes

BACKGROUND OF THE INVENTION

1. Field of the Invention

This invention relates generally to the computer control printing, displaying, or other presentation of documents which may have text, graphical components, and/or images. This invention is more particularly related to a method and system for processing the beginning and ending of pictures or pagesets in a document data stream, keeping track of the status of the presentation device referred to as the state of the virtual machine using a set of dictionaries, defined later, a context stack defining the search order of the dictionaries, a state variable table, a set of resources, and an operand stack.

2. Discussion of the Background

The development of laser printers in the early 1970s provided an opportunity for high quality, low cost printing of documents, which contained not only character text but also general graphical material. The primary method of controlling commands by the computer to the printer employed the so called "escape sequence" commands, similar to the type of commands used in the DIABLO.RTM. command sequence. These types of commands were distinguished from typical character data by preceding each command with a special byte, generally an escape character (ASCII 27). This methodology works acceptably with daisy wheel or dot matrix printers but is not well suited for printing documents that might have changing requirements. For example, as needs change and as technology improves, an upgrade of the presentation device is necessary. This type of upgrade in the past would have required removal of the program controller of conventional presentation devices. At a minimum, a new PROM containing instructions for the printer would be required. This is not a commercially acceptable way of handling temporary changes, as a new PROM would be installed for a few print jobs, and would then have to be replaced with the original PROM or another new PROM. This method of upgrade is wasteful and results in many failures of the presentation device controller.

As a response to the limitations inherent in the escape sequence commands, different types of "page description language" (PDL) were developed generally to control laser printers or other types of page printers. Backward compatibility of these laser printers was provided by way of an ability to accept escape sequence commands. Two current examples of page description language are the PostScript.RTM. system from Adobe Systems Incorporated and InterPress.RTM. from Xerox.RTM. Corporation. Several other proprietary PDLs are also known.

Some of the prior art page description languages provided various improvements to the standard escape sequences known previously, such as by providing tools and syntax for manipulation of objects, or by providing for the use of operand stacks or the like. Moreover, they are stack-oriented programming languages. These languages also allowed, in some cases, for dynamic changes in the printer's state, such as the ability to add fonts or graphical images to the resources that might be available to the printer. Some of these features are documented in such generally available reference works as Adobe System Incorporated's "PostScript Language Reference Manual" and the "PostScript Language Program Design," both by Addison-Wesley Publishing Company (1985 and 1988, respectively). Other PDLs are also described in various technical and reference books such as "InterPress, The Source Book" by Harrington et al. (Simon and Schuster, Inc., 1988)

A standardized page description language has been proposed and is being developed as an international standard by the International Organization for Standardization ("ISO"). The proposal, to which one of the present inventors is a contributor, is currently in draft form before a section of the ISO. The draft is known as ISO/IEC DIS 10180, labeled "Information Processing Text-Communication Standard Page Description Language" and is available through the American National Standards Institute("ANSI") in New York.

Many of the prior art types of page description languages suffer from various flaws. For example, one shortcoming of the PostScript.RTM. language is that a page description for a particular document can contain a new definition such as a resource definition (i.e. an additional font) or a new dictionary definition that can be used anywhere in the document. In other words, no structure is enforced in PostScript.RTM. and therefore, the entire content of the document must be processed to determine whether a particular printer has the resources necessary to print it. If this "preprocessing" is not performed, it is possible that the printing of a document may fail at any point during the printing process, even at the very end, due to the inability of the printer to comply with commands of the document page description.

Additional problems are associated with the prior art systems that employ PostScript.RTM.. For example, to print a given page of a document, it is generally necessary to read and process, before presenting a page, the entire PDL description of all the preceding pages of the document, in order to decide the state of the document page setup parameters (i.e., resource declarations, dictionary definitions or the like). In other words, a print controller program must read the entire PDL description of a document to consider the effect of every page setup command between the beginning of the document and the specified page. While this page setup scanning process is relatively straightforward, it does require a significant amount of processor time, which can be better used by the printer.

Additionally, there are no syntax or semantics defined in the PostScript.RTM. language to handle a structure, a prologue or a scope of a data declaration. There is a convention. This convention, however, does not need to be followed.

One problem with the well known InterPress.RTM. system from Xerox.RTM. is that its structure does not effectively handle dictionary definitions contained in an inputted data stream. Nor does InterPress.RTM. use the prologue structure in an expeditious manner. Also, the standard InterPress.RTM. encoding is only binary rather than clear text which a human can read.

SUMMARY OF THE INVENTION

Accordingly, one object of this invention is to provide a method and apparatus for the determination and efficient processing of hierarchical structure elements of a PDL document, such as the beginning and ending of pictures and/or pagesets in a document data stream so as to speed up the processing of document data streams.

It is another object of this invention to provide a method and apparatus which can keep track of the scope and status of material defined within the definition for each document data stream in an efficient manner.

It is a further object of this invention to provide an apparatus and methodology for selecting in an input data document stream a given page or picture for processing in an efficient manner without the requirement for processing all preceding pages in the document.

It is yet another object of the invention to create a current context of interpretation as the document is being processed which handles state variables and a "context stack" for keeping track of various dictionaries used for processing such as context dictionaries, content dictionaries, a user dictionary, and a system dictionary.

These and other objects are achieved according to the present invention by providing an efficient method of processing a page description language as defined in ISO/IEC DIS 10180, (hereinafter DIS 10180) for example. According to DIS 10180, as currently constituted, each document data stream is provided in a structure which is either a pageset or picture. The pageset and picture elements consist of an optional prologue which contains definitions and declatory commands and an optional body. A pageset body consists of zero or more pagesets or pictures while a picture body consists of zero or more pictures or tokensequences. The tokensequence which contains specific tokens or commands for defining specific images along with necessary operators contains "content" while other elements in the document are called "structure". The structure sets up the environment for content to generate the appropriate output images. The effects of a prologue within the hierarchical level of a picture or pageset is until the end of that picture or pageset. Therefore, the prologue of a picture in the hierarchical structure of a document does not influence those structures at the same or peer level or superior structures while influencing structures at a lower hierarchical level. This invention effectively handles this hierarchical tree structure along with the scope of the prologue by using a stack and various pointers.

A tree-linked hierarchical structure advantageously enables the processing of any portion of the document by directly addressing that portion of the document and those portions which are higher in the hierarchy without the necessity of processing any other items in different branches of the hierarchical tree. In other words, only structural definitions which occur in the hierarchical tree which are above a given portion of the document need be processed. This increases the efficiency of the processing of the document and also facilitates the determination of the type of resources which will be needed in the printing device or the display device prior to the commencement of the actual printing of the document. This increases the speed and efficiency by which various devices print or display the document.

Whenever a hierarchical level in a document is being processed, an entry is pushed into a picture/pageset stack corresponding to that hierarchical level. Each entry in the picture/pageset stack has a pointer to a prologue data structure and a pointer to a current context of interpretation (hereinafter called "CCI") data structure. The CCI data structure is used whenever content of a document is being processed. The entries in the CCI data structure can be modified when the structure of a document or file is being processed and can also be modified as content is being processed. However, content cannot directly modify the entries in the picture/pageset prologue data structure.

As a document is being processed, variables defining the state of the virtual machine which is performing the processing are defined in a state variable table. The state variables in a state variable table can be modified by the various processing commands.

A context stack is used to define the search order of four types of dictionaries used for processing the document. At the highest level in the context stack are context dictionary linked data structures which are used to define the search order of context and/or content dictionaries. The second level in the context stack pertains to the user dictionary. User dictionary link data structures are used to search the different entries at the different hierarchical levels of the user dictionary. Last, there is one system dictionary which is usually in the same location and the system dictionary is searched if the key being searched is for is not found in either of the context or user dictionaries.

BRIEF DESCRIPTION OF THE DRAWINGS

A more complete appreciation of the invention and many of the attendant advantages thereof will be readily obtained as the same becomes better understood by reference to the following detailed description when considered in connection with the accompanying drawings, wherein:

FIG. 1A and 1B are illustrations of sample documents and their hierarchical structural elements;

FIG. 2 is an illustration of the hierarchical structure of a document;

FIG. 3 is an illustration of the "grammar" of a picture, pageset, prologue, picture.sub.-- body and a pageset.sub.-- body;

FIG. 4 illustrates the structure of an exemplary two page SPDL document;

FIG. 5, is an illustration of a sample hardware embodiment which can employ the present invention;

FIG. 6 is an illustration of the virtual machine or processing model used to process SPDL documents;

FIG. 7 is an illustration of the picture/pageset stack and various hierarchical structure elements which push or pop entries onto the stack;

FIG. 8 is an illustration of the picture/pageset stack and the picture/pageset prologue data structure and CCI data structure pointed to by the entries in the picture/pageset stack;

FIG. 9 is an illustration of a state variable table;

FIGS. 10A and 10B illustrate a process performed at a "picture.sub.-- begin" command; FIG. 10A handles the manipulation of the picture/pageset stack and the picture/pageset prologue data structure and FIG. 10B handles the processing of the state variables;

FIG. 11 illustrates a process used to create a current context of interpretation data structure upon encountering a tokensequence structure element;

FIG. 12 illustrates a part of the system dictionary;

FIG. 13 is an illustration of the context stack;

FIG. 14 illustrates a context dictionary generator data structure;

FIG. 15 illustrates a context stack link data structure;

FIG. 16A-16C illustrate various states of the picture/pageset stack, CCI data structure, prologue data structure, context stack link data structure and context dictionaries during the processing of a document;

FIG. 17 illustrates the process used to push a context dictionary into a context stack link data structure when instructed by a tokensequence;

FIG. 18 illustrates various data structures after a dictionary has been pushed into the context stack link data structures;

FIG. 19 illustrates the process executed when a dictionary is popped out of a context stack link data structure by a tokensequence;

FIG. 20 illustrates the various stacks and data structures after pushing and popping of context stack link data structures have occurred;

FIG. 21 illustrates the user dictionary link data structure and a user dictionary;

FIG. 22 illustrates the process used to manipulate the user dictionary;

FIG. 23 is an example of a user dictionary containing one entry;

FIGS. 24A-24E illustrate the states of the picture/pageset stack, CCI data structure, prologue data structure, user dictionary links, and user dictionaries during various processing steps of a document;

FIG. 25 illustrates a process used when the end of a tokensequence element is encountered;

FIGS. 26A and 26B illustrate a process to save the necessary variables before a CCI data structure is deleted;

FIGS. 27A and 27B illustrate a process to delete unnecessary CCI data structures and data structure related to the CCI data structures; and

FIGS. 28A-28E illustrate data structures used during the processing of state variables.

DETAILED DESCRIPTION OF THE DRAWINGS

Referring now to the drawings, wherein like reference numerals designate identical or corresponding parts throughout the several views, and more particularly to FIGS. 1A and 1B thereof, there are illustrated two documents and their structural elements such as pictures and pagesets as defined in the Standard Page Description Language ("SPDL"). In SPDL, a document can be defined as a single picture or a single pageset. A pageset can consist of additional pagesets or pictures. A picture cannot be greater than one page and cannot cross from one page to another. FIG. 1A illustrates a document consisting of one pageset with four pages (the highest level of pictures). FIG. 1B illustrates a single page document containing text and two pictures. The document of FIG. 1B could be represented as either a pageset of one page or a picture as it is only one page.

FIG. 2 is an illustration of the hierarchical structure of an SPDL document. The document illustrated in FIG. 2 contains a pageset 10 as its highest hierarchical structural element. Pageset 10 consists of pageset 12 and picture 14. Pageset 12 further consists of the pictures 16, 18, and 20. To define hierarchical levels by way of example, pageset 12 is at a lower hierarchical level than pageset 10 but at a higher hierarchical than the pictures (pages) 16, 18, or 20. Each hierarchical element will usually consist of a lower level hierarchical element and/or one or more tokensequence elements. A tokensequence is a special type of structural element which contains content. Content is the substance of what is printed or displayed for a document. A tokensequence, for example, may describe a drawing, text or image. The representation of content such as a drawing, text, or image by way of tokensequences allows for a very rapid and efficient processing of a document for presentation, especially when only a portion of a document is to be presented because the tokensequences of pages which are not to be presented do not have to be processed. Pictures 14, 16, 18 and 20 each will probably have at least one tokensequence element.

As shown in FIG. 3, a picture and pageset have a set "grammar". A picture is defined as having an optional prologue and an optional picturebody, and a pageset is defined as having an optional prologue and an optional pageset body. The optional prologue defines various parameters used by a processing system to process a document and contains elements such as an external declaration, informative declaration, resource definition, resource declaration, document production instruction declaration, context declaration, dictionary generation declaration or set-up procedure. All of these elements in the prologue are optional and, in fact, may be repeated in the sense that there may be multiple instances of the same item. Consequently, multiple levels of a prologue may be present and the handling of these multiple instances can be accomplished as set forth below.

FIG. 4 is a detailed illustration of the structure elements of a sample two page document. The document consists of one pageset 50 having a prologue 51 and a pagesetbody 60. As discussed with regard to FIG. 3, a prologue is an optional structural element which defines various parameters for the picture or pageset. The prologue 51 contains four subordinates; resource definition 52, dictionary generator 54, dictionary generator 56, and setup procedure 58, and corresponding tokensequences. The resource definition 52 is a structural element which indicates tokensequence 53 contains the content which defines resources used for presentation (e.g., the definition of a form used by a document).

The dictionary generator 54 indicates that tokensequence 55 defines a dictionary. Similarly, dictionary generator 56 indicates that tokensequence 57 defines a dictionary. A dictionary definition contains ordered pairs consisting of a key and a value. Whenever a key is encountered in content, the value from a dictionary corresponding to the key is substituted therefor. The value entry in a dictionary can be an integer number, a real number, procedure or any other type of value. Dictionaries created by dictionary generators are made read only and are created to be context dictionaries, as explained below.

The setup procedure 58 initializes various state variables which are used when processing content. Exemplary state variables are variables such as Current.sub.-- Color, Current.sub.-- Font and Current.sub.-- Position. The setup procedure is also used to alter the contents of the user dictionary, if desired. The user dictionary is a read/write dictionary which is searched after the context and content dictionaries are searched without encountering the searched key.

Pageset body 60 contains two pages having pictures 61 and 75. Picture 61 has its own prologue 62 which defines parameters only for the picture 61 and does not affect picture 75. Prologue 62 contains context declaration 63 and its dictionary identifier 64, dictionary generator 65 its tokensequence 66, setup procedure 67, and its tokensequence 68. The picturebody 69 of picture 61 contains tokensequences 70 and 74, and picture 71 having picturebody 72 and tokensequence 73. The second page of the document has picture 75 with picturebody 76 having tokensequence 77.

The context declaration 63 indicates a manipulation of context dictionaries which are defined in higher hierarchical levels of the structure. If a dictionary identifier such as dictionary identifier 64 follows a context declaration, the dictionary identifier will indicate how the search order of the context dictionaries are to be changed. If a dictionary identifier element does not follow the context declaration, any defined search order of the dictionaries will be eliminated, no context dictionaries will be searched for the particular hierarchical level, and the user dictionary and the system dictionary will be placed in the bottom of the context stack. The search order of the dictionaries is defined using context dictionary stack data structures, as will be explained in detail below.

It should be understood that FIG. 4 illustrates only an abstract description of the structure of an SPDL document and an actual SPDL document might use a different description.

Turning now to an exemplary hardware implementation of the present invention illustrated in FIG. 5, a system will generally have at least a CPU 102, memory generally in the form of ROM 106 and RAM 104, input/output means to receive the document data stream, and a means for displaying/printing a resultant output. The resultant output image may be produced by an image raster device which may be directly connected to the CPU or may ha