Bug 687560 "Invalid PDF if /BP pdfmarks with non-unique /_objdef"

Sorry, used a wrong e-mail address...

----- Original Message ----- 
From: SaGS 
To: Igor V. Melichev ; gs-code-review 
Sent: Thursday, 25 November 2004 00:21
Subject: Re: Bug 687560 "Invalid PDF if /BP pdfmarks with non-unique /_objdef"


Hello,
  The patch includes not 1, but 3 (well, 2 and a half) different interpretations of what "the same distill-time name" can mean. These are denoted in code by PDF_NAMECOLLISION_BACKUP, PDF_NAMECOLLISION_KEEPOLD, and PDF_NAMECOLLISION_REBUILD, the others being only necessary technicalities. Comment #6 on the bug report (http://bugs.ghostscript.com/show_bug.cgi?id=687560#c6), under "SOME DETAILS ABOUT THE NEW PATCH" gives details on these, but not in the terms you use in your message.

  First of all, I think an example will help. I attach 3 PDFs obtained using each of these interpretations from a sample attached to the bug report (comment #3 "An useful abuse..." http://bugs.ghostscript.com/show_bug.cgi?id=687560#c3); file names indicate which method was used for each PDF. The number displayed after "of" comes from a Form XObject named {TOTALPAGES} that is (re)created on each page with that page's number and is immediately displayed.

  My attempts to "translate" all of this into the terms you used in your message can be found later in this message.

  Before this, some clarifications and another way of viewing this problem.
The 3 uses of {OBJNAME} -------
  There are 3 different uses for the construct "{OBJNAME}":
  a.. When it appears as the value of the /_objdef key, it NAMES an object that is being created (does not generate, by itself, anything in the output PDF). Example pdfmarks: /OBJ, /BP. 
  b.. When it appears alone it (usually) is used to LOCATE an object FOR MODIFYING it (does not generate anything in the output PDF, but the pdfmark that located the object will modify it). Example pdfmarks: /PUT. 
  c.. When it appears as (part of) the value for any key except /_objdef, it generates a REFERENCE to a particular object (produces some output to the generated PDF, but does not touch the referenced object). This is what I meant by "{OBJRef}" in a preceding post.
  I find the distinction between 2nd and 3rd uses important. When there are multiple objects with same name, {OBJRefs} may be resolved to any of the copies, and there is not very important which one is chosen. But it is much more critical to which copy we add new content; without much care, content meant for one copy will be unexpectedly mixed with content for another one, and we may create incoherent objects.
A "global" view -------
  A parallel with a procedural programming language forces us to "think sequentially", which is not 100% suitable. The pdfmark reference explicitly allows to have {OBJRefs} to objects that are not defined yet, and "thinking sequentially" does not allow us to resolve these references. We could delay resolving the reference, but how long? Until the FIRST definition? Why not until the 2nd or LAST one?

  So, let's take if differently:
    1.. Create objects: temporarily don't pay attention to {OBJNAMES} and "delay" resolving {OBJRefs} during the interpretation of the PostScript code. 
    2.. What we get: at end-of-job we have a collection of objects, each having an attribute named "distill-time name". For some objects the value for this attribute is empty, for other it's not; we have multiple objects with same value for this attribute. We also have some {OBJRefs} that need to be resolved against these {OBJNAMES}. 
    3.. Sot out duplicate names: these can come from careless concatenation of 2 or more PS files, in which it's preferable to preserve all copies; but the "same name" can also be a hint that those objects are in fact the same, so we need to preserve a single copy.  In the last case, we must choose WHICH copy to preserve. PDF_NAMECOLLISION_BACKUP implements "preserve all"; PDF_NAMECOLLISION_KEEPOLD and PDF_NAMECOLLISION_REBUILD implement "preserve only one", but they differ in WHICH copy is preserved: FIRST respectively LAST copy in the order these copies are created. 
    4.. Resolve {OBJRefs}: obviously these have to be resolved to objects that were preserved after step 3. For names that are not duplicated, or if step 3 kept a single copy, there's no problem. PDF_NAMECOLLISION_REBUILD preserves multiple copies, so we must make, for each {OBJRef}, a choice. I chose to resolve each {OBJRef} to the MOST RECENT definition in execution order; "forward references" (= {OBJRef} with no preceding definition of that object) are resolved to the FIRST occurrence. 
    5.. Locating objects for modifications: points 1..4 above left aside the 2nd usage of "{OBJNAME}" described above. I consider the only choice here is the "dynamic scoping" described below, for point 2 in your message. Reason: this maximizes independence between objects, so that added contents does not unexpectedly end up into another copy.
----- Original Message ----- 
From: "Igor V. Melichev" <[email protected]>
To: "SaGS" <[email protected]>; "gs-code-review" <[email protected]>
Sent: Wednesday, 24 November 2004 07:15
Subject: Re: Bug 687560 "Invalid PDF if /BP pdfmarks with non-unique /_objdef"


> ...
> 1. An unscoped definition-like interpretation.
> An example is C language, global static definitions :
> 
>     struct mystruct1 a;
>     struct mystruct2 a;
> 
> The interpretation result is syntax error.
> ...

If the main goal of the patch were ONLY to avoid creating a damaged PDF, this would be the simplest approach. The patch does not implement this; it raises errors only when it really has no other choice.

> 2. A scoped definition-like interpretation.
> An example is C language, local definitions :
> 
>     struct mystruct1 a;
>     { struct mystruct2 a;
>        ......
>      }
> 
> The interpretation result is 2 objects with different life times.

This is what PDF_NAMECOLLISION_BACKUP implements. However, there are some differences compared to scoped definitions in a (traditional) language like C.

In C :
  a.. scopes are static, they result from the source code's structure; 
  b.. scopes may be nested and an old definition, from an outer level, "comes back to life" at the end of a nested scope.
PDF_NAMECOLLISION_BACKUP:
  a.. "scopes" are dynamic; the scope of a particular definition starts when (not WHERE!) appears an /_objdef for it and ends just before the next /_objdef with the same name (in EXECUTION order, not SOURCE CODE order) or at end-of-job; 
  b.. as a consequence, scopes are not nested and an old definition never "comes back to life".

> 
> 3. A variable-like interpretation.
> An example is C language, variables :
> 
>    int a, *b, *c;
> 
>     a = 1;
>     b = &a;
>     a = 2;
>     c = &a;
> 
> The interpretation result is a varying referent, same for b and c.

This is exactly what PDF_NAMECOLLISION_REBUILD and, with some strange difference, PDF_NAMECOLLISION_KEEPOLD do.
Correspondence between C and PS/PDF elements that come into discussion:
  a.. C identifier "a" => distill-time name "{A}" 
  b.. Values for variable "a" => PDF objects created using the distill-time name "{A}" 
  c.. "a = 1" => [/_objdef {A} ... marking operators 
  d.. "a = 2" => [/_objdef {A} ... other marking operators 
  e.. "b" and "c" are "{OBJRefs}" to PDF object "{A}" (they become "n 0 Refs" in the generated PDF) 
  f.. what gets written to the PDF: the final value of "a" for PDF_NAMECOLLISION_REBUILD and the first value of "a" for "PDF_NAMECOLLISION_KEEPOLD" (Why the first? Because Distiller 4 does this.)
> 
> 4. A pointer-like interpretation.
> An example is C++ language, pointers :
> 
>    int *a, *b;
> 
>     a =  new int;
>     b = a;
>     a = new int;
>     c = a;
> 
> The interpretation result is two different referents for b and c.

I don't quite see how C elements correspond to PDF elements in this case. It appears that each time an "{OBJRef}" (<=> "b" anc "c") appears, we make a copy of the object "{A}"'s (<=> "a") current value. I think the overall result is the same as for PDF_NAMECOLLISION_BACKUP explained above.

> 
> 5. An merge-like interpretation.
> An example may be taken from G.Tseytin's puplications about "associative nets"
> (let me know if you need an exact reference).
> 
>    let a be new NULL
>    let Nicolo be new child (father = new NULL, mother = "Tanya")
>    a += A.father
>    let Alex be new child (father = new NULL, mother = "Olga");
>    a += B.father
> 
> (note that here I used a different syntax than G.Tseytin;
> NULL is an object with no properties).
> The result is 2 children with same father, and we have no 
> information about the father besides he has the 2 children.
> 

I cannot make any comment on this, because it's an unknown territory for me. (Yes, I find this interesting and thank you in advance for a link, even if I don't think I'll study it for this patch.)

> So now we need to choose one of variants above.
> IMO (5) is out of our interest, because PS/PDF is not so advanced
> (at least there are no other places with a merge-like semantics).
> My old vote is either (1) or (4), but now I'm not sure whether we can
> ignore (2).
> 
> As to you vote, I still can't classify it for sure.
> Please clarify.
> 
> Igor.
>     

My first vote goes to PDF_NAMECOLLISION_REBUILD (3); reasons are explained in the initial bug report and in the companion bug 687561 "Smaller PDFs when using execform"(http://bugs.ghostscript.com/show_bug.cgi?id=687561).

I implemented PDF_NAMECOLLISION_BACKUP because:
  a.. If (ever happens that) an object (a particular "value") is already written to the output file, it cannot be replaced. This does not currently happen, but I don't know, for example, how pswrite2 will evolve. 
  b.. If, in the future, GS will keep all objects in temporary storage until end-of-job and, at that time, will be able to compare objects and remove duplicates (in order to get the ultimately small PDF file), this will be the implementation of choice. It' simple, robust, and immune to "lying" that objects are the same (the others take "same name implies same contents" for granted, but in this scenario GS would be capable to verify if this is true or not and keep exactly 1 copy for each distinct objects, not matter what name they have).

  Note: this last point also requires the ability to identify all "n 0 Refs" kept internally by pdfwrite, in order to replace the object numbers; also, renumbering objects. Off topic: I find the capability to renumber objects at end-of-job to be very usefull for optimizing pswrite2's output in terms of VM consumption during printing.
Finally, PDF_NAMECOLLISION_KEEPOLD is there, even if I find it to be a bad idea, only because (1) Distiller 4 does this and (2) I think it's needed to convince you that "like we do for ExtGState" is not a universal solution. The weakness of this method is explained in the bug report, comment #6 (http://bugs.ghostscript.com/show_bug.cgi?id=687560#c6, search for "weakness").


Sincerily yours,
mat Gh Savulescu

_______________________________________________
gs-code-review mailing list
[email protected]
http://www.ghostscript.com/mailman/listinfo/gs-code-review