Re: Bug 687560 "Invalid PDF if /BP pdfmarks withnon-unique /_objdef")

Dear Igor & other reviewers,

First, the good news: I managed to remove the "surgery", after figuring out a
way to store enough information for pdfmark_EP() to locate the "main" copy of 
the object with the given distill-time name (without adding extra data 
structures...).

Next, since nobody else posted an opinion on the subject, I'll try to
clarify my own opinion on the problems previously mentioned by 
mr. Igor Melichev; see below.

----- Original Message -----
From: "Igor V. Melichev" <[email protected]>
To: "SaGS" <[email protected]>; "gs-code-review"
<[email protected]>
Cc: "Miles Jones" <[email protected]>
Sent: Monday, 29 November 2004 10:00
Subject: Re: Bug 687560 "Invalid PDF if /BP pdfmarks withnon-unique
/_objdef") xefitra


> ...
> 2. ... Let the document file name is a.ps. To rise the problem run :
>
>     gs -sDEVICE=pdfwrite, sOutputFile=a.pdf a.ps a.ps
>
> Since the document is being processed twice in same session, the objdef
> with same name appears twice in same session.
> ...
> Another consequence of the example above is:
> an object definition MUST PRECEED any object usage,
> otherwise concatenating two correct documents
> with same object name and different values will give a
> wrong result
> ...
> 6. So now we get a strong consequence, ... without forward references.

Short answer:
In such a case the user IS EXPECTED (see pdfmark ref manual) to do something
like

    gs -sDEVICE=pdfwrite sOutputFile=a.pdf
       "-c [/NamespacePush pdfmark" -f 1st.ps "-c [/NamespacePop pdfmark"
       "-c [/NamespacePush pdfmark" -f 2nd.ps "-c [/NamespacePop pdfmark"

Details:
Indeed, simply concatenating or otherwise combining 2 PS files then 
converting to PDF may produce a different result than converting each 
file then combining the resulting PDFs. More precisely, forward {OBJRefs} 
encountered in 2nd file will be resolved either to the last definition 
of that object in the 1st file (in the former case), or to the 1st 
definition of that object in the 2dn file (in the latter case).

This is easily solved by enclosing each document with /NamespacePush and
/NamespacePop pdfmarks. In fact, when combining 2 independent PS files which
are expected to contain {OBJNAMES}, the user is expected to use these 2 
pdfmarks to isolate the files. This statement holds not only for 
concatenating PS files, but for including EPS files too.

As a consequence, we don't need to restrict forward references.

> ...
> 3. There are two ways to resolve the case (2) :
> 3.1. Perform a specal namespace cleanup before the second
> document is started;

This is the /NamespacePop's job.

> 3.2. Define a variable-like behavior for objdef.

OK.

> ...
> 4. The appriach (3.1) requires a change to the device interface,
> because now it doesn't pass a "start document" signal.
> Such kind of changes must not get bountiable status,
> since a resolution requires a high reliabiliry.
> I have no strong opinion, whether we need (3.1) or not,
> but I would vote for it, because the signal would be useful
> from a general point of view.

As mentioned above, for pdfwrite and distill-time names such a signal is
not needed. From a general point of view, I don't have a special preference.
I only want to point out that automatically providing such a cleanup may
create problems:
(4.a) As you may already know, it is possible to create PDFs with interactive
      form fields directly from PS, but this requires quite some overhead.
      It is reasonable to put all this common setup code and a "library" of
      button appearances (for check boxes, etc) in a separate file, then
      pass this file to GhostScript on the command line in front of the 
      main file. If the namespace is AUTOMATICALLY cleared between files, 
      this fails.
(4.b) What to about PS code specified directly on the command line (with "-c")?

> ...
> 6. ... It may be implemented as
> I suggested a week ago :
>
> 6.1. When a name is being defined at the first time,
> create the object, store it with the given name in the object directory
> (I mean the distill-time association of distill-time names with cos objects).

This is the PDF_NAMECOLLISION_NONE branch.

>
> 6.2. When an usage happens, the object exists and has a specific ID.
> Create a reference to it as usial by the object directory;

OK. No change here rlative to existing GhostScript version.

>
> 6.3. When the object name appears in objdef at second time,
> create a new object, and replace the association in the object directory.
> The old object continues to exist.

You don't specify what is supposed to happen to {OBJRefs} that are already
resolved to the previous copy. If these are supposed to continue to refer
to the old copy, then what you define here is exactly what the patch
implements as PDF_NAMECOLLISION_BACKUP. If the object's CONTENTS gets
replaced (amd the old {OBJRefs} will actually display the new copy) then this
is exactly what the patch implements as PDF_NAMECOLLISION_REBUILD (with one
improvement: since the old copy is not needed, not being referenced anymore,
the patch does not preserve it).

Also note that in first case, what you describe here is very different from
what you defined as "variable-like behaviour" at point (3) in your message
dated Wed, 24 Nov 2004 08:15:10 +0300. That point (3) corresponds to my
PDF_NAMECOLLISION_REBUILD.

>
> 6.4. When another usage happens later, use the object directory
> to create the reference to the last object assotiated.
>
> 6.5. If an usage happens when no object associated in the object directory,
> signal error and discontinue the processing (since at this moment
> we don't know whether we'll start another document or not, we can't resolve
> whether this an error or a forward reference. A practical
> resolution for now is to emit error.

As stated above, we may safely assume it's a forward reference.

>
> 6.6. For future development inmplement a reserved function,
> which purges the object directory; It will be called after we
> implement the "start document" signal.

This is "[/NamespacePop pdfmark".

> ...
> 7. The approach (6) does not need any surgery or a fundamental change of
> pdfwrite invariants. In same time, patches suggested by SaGS,
> do change basic invariants, such as the resource lifetime and semantics.
> Therefore I would approve an implementation of (6), but I can't approve
> SaGS's patches (well, my opinion would be different if someone brings
> a practical example of a document with a non-unique objdef
> denerated by a popular PS writer, but as I already said, we did not
> recieve any).

First, I found a way (haven't posted it yet) not to interfere with links
established by pdf_enter_substream(), so I expect the main objection will
dissapear.

Then, there's no change to invariants. The code either replaces/ modifies
CONTENTS/ELEMENTS of cos_object_t structures in a similar way /NI+image does,
or disposes of objects it knows FOR SURE won't be needed anymore.

> ...
> 8. There exists a disirable optimisation, which
> merges equal instances of  objects defined by consequtive objdefs.
> Particularly it would be useful if a document is being concatenated with itself.
> To implement this optimization I would use same technique,
> as pdfwrite uses for other resource types : write a new object to a stream,
> then compare the stream for equality with existing streams.
> If en equal one appears, replace the new object with the old one.
> This technique already works for most types of cos objects,
> and I woild approve it for XForm objects created by pdfmark.

Comparing by contents in order to remove duplicates works fine for unnamed
objects, but NOT for named ones. The reasons are not obvious at all, so I'll
try to give the details.

First reason is common to all named objects:

[8.a] A named object must be registered into pdev->local_named_objects & friends.
      That's the only place I found where distill-time names are asociated with
      cos_object_t objects, so if it's not registered there the association
      name <-> object is lost.

[8.b] An object registered into pdev->local_named_objects must be assigned an
      object number before the driver returns control to the the PS interpreter.
      In practice this means that it must get a number as soon as it is created.
      Reason: the very next operation could be a pdfmark that creates a reference
      to that object. {OBJRefs} are processed by gdevpdfr.c::pdf_replace_names()/
      pdfmark_next_object(), which do a text find-n-replace of "{OBJRef}" with
      "n 0 R"; if an object in pdev->local_named_objects does not have a number,
      we get "0 0 R" or "-1 0 R", which is invalid and cannot possibly be turned
      into something valid later (the association with the intended target is lost).

[8.c] A named object can be MODFIED at any time with a /PUT pdfmark. Note:
the
      pdfmark ref is not explicit enough about this, but it contains examples of
      things that are not clearly stated in the "reference" portion (for example
      dict-/PUT into streams created with /NI+image, to create alternate images).

[8.d] A consequence of [8.c] is that we can COMPARE named objects ONLY AT END OF JOB
      (or when they go out of scope because of a /NamespacePop pdfmark).

[8.e] Now, let's consider we create 2 objects {A} and {B} that we intend to compare
      for equality, and "collapse" them if equal:
          [{A} ... /OBJ pdfmark ... [{B} ... /OBJ pdfmark
      Let's assume we assigned number 10 to {A}. What number to assign to {B}?
      [8.b] requires it to be assigned a number as soon as it is created, but because
      of [8.d] we cannot know at that point if {B} == {A} or not. So, we have to
      assign a new number, let's say 20. During the job, we also have pdfmarks that
      REFER to these objects, and we end up with "10 0 R"/ "20 0 R" and/or
      "/R10 Do"/ "/R20 Do" all over the place, inside content streams and burried
      into the "value" part of key-value pairs.

[8.f] If, at end of job, we compare {A} and {B} and find these are equal, what can
      we do? Let's assume we intend to keep {A}, and dispose of {B}. This means:
      - the object number 20 (assigned to {B}) becomes unused, so it must be marked
        as such in the xref table; it's my impression GhostScript does not handle
        such a case. (This is the easy part...)
      - all "20 0 R" and "/R20 Do" (references already resolved to object {B}) have
        to be modified to point to object 10 ({A}). I find this to be a nearly
        impossible task, because there's no way to know for sure where these references
        are. (Well, content streams could be parsed...)
      If we cannot find those "20 0 R" and change them, we must include both {A} and
      {B} in the output file. Then, why bother to compare them?

2nd reason is specific to Form XObject & similar:

[8.g] All coordinates written by GhostScript into content streams correspond to the
      PostScript DEVICE space. Thus, if an identical sequence of marking operations is
      carried out with a different initial CTM, even if the Form XObjects are essentially
      the same they won't compare as equal: USER space coordinates are identical, but
      DEVICE space coordinates are not. (Distiller and Jaws PDF Creator record USER
      space coordinates.) pdfwrite gets device coordinates on it's interface;
      converting these back to user space coordinates does not solve the problem,
      because of rounding errors (if a single coordinate rounds differently then the
      whole stream object is different). I find that passing user space coordinates on
      the device interface would be a huge (and incompatible) change.

The big difference between named and unnamed objects is that UNnamed objects are
completely under driver's control. The driver decides when it won't modify an object
anymore and will start creating references to it, so can promptly do the comparison.

> But I would consider this optimization separately from the reported problem,

I find the "if same distill-time name then assume same contents" policy offers
an easy way out of the messy problems exposed above. Essentially, if someone asks
to create a reference to object {A} but creates 12 {A}s, then we have the liberty
to choose to which of those {A}s we will resolve the reference. By choosing the
SAME copy for all references, we can get rid of the other 11. This is why I see
this optimization tightly connected to the "same name" problem.

> ...
> 9.1. SaGS or somebody else will submit a patch for (6),
> I'll approve it, commit and Artifex shall pay the bounty.

This is the current patch with only PDF_NAMECOLLISON_REBUILD or
PDF_NAMECOLLISION_BACKUP (out of the 3 alternate implementations)
preserved, depending on how you interpret "references", and with the "surgery
on pdf_enter_substream() links" removed (I removed that "surgery" but haven't
posted this yet; waiting to clarify more basic things first).

> ...
> 9.2. Somebody submits a patch, which just signals error and stops.
> I would approve it as a temporary solution, since
> there is no claims from customers. But I'm not sure that
> the full bounty sum is good for such small patch.

More than this, I consider the "signal an error" would be a primitive and
far from usefull solution. Also, not conforming to what other "distillers"
do.

> ...
> 9.3. ... open an enhancement project with the
> "start document" implementation, assign a proper priority to it
> and put into the queue.

For the "same distill-time names" problem, the "start document signal" is
not really needed. If you consider this to be generally usefull, then 
that's something else....

> ...


Sincerely yours,
SaGS