Issue: STREAM-INFO (Version 4)

[dick@wheaties.ai.mit.edu (Richard C. Waters)]

----------
Issue:        STREAM-INFO
References:   FORMAT ~T (pp398-9) and ~<...~> (pp404-6), PPRINT (p383)
Category:     ADDITION
Edit history: 22-Jun-88, Version 1 by Pitman (2d model)
	      23-Jun-88, Version 2 by Waters (1d model, modified 2d model)
	      24-Jun-88, Version 3 by Pitman (minor reformatting)
	      24-Jun-88, Version 4 by Pitman (remove 2d model for submission)
              23-Sep-88, Version 5 by Waters (cleaned up in response to discussion)
Status:	      For Internal Discussion

Problem Description:

  Currently, there is no portable way to inquire about the line width of
  an output stream, the current position on a line, or the amount of
  space that the display of a string will take up.  This makes it
  essentially impossible to write a portable implementation of a pretty
  printer.

Proposal (STREAM-INFO: ONE-DIMENSIONAL-FUNCTIONS):

  Introduce four new functions.   
    These functions are carefully designed with an eye to the way they
  interact.  As a result, they can only be defined fully in terms of
  each other.  The presentation below first gives a very brief
  definition of each function and then gives detailed specifications of
  their relationships.

   LINE-WIDTH &optional (OUTPUT-STREAM *STANDARD-OUTPUT*)       [Function]

    Returns a non-negative integer representing the line width available
    when printing to OUTPUT-STREAM.  If the stream has no meaningful
    width (or the width cannot be computed) then NIL is returned.

   LINE-POSITION &optional (OUTPUT-STREAM *STANDARD-OUTPUT*)    [Function]

    Returns a non-negative integer representing the current horizontal
    position on the current output line, or NIL if the position cannot
    be computed.

   WRITE-SPACE WIDTH &optional (OUTPUT-STREAM *STANDARD-OUTPUT*) [function]

    Inserts blank space of length WIDTH into OUTPUT-STREAM.  WIDTH must
    be a non-negative integer.  WRITE-SPACE returns T if the operation
    is successful and NIL otherwise (e.g., if the operation is not
    supported by OUTPUT-STREAM).

   PRINTED-WIDTH STRING &optional (OUTPUT-STREAM *STANDARD-OUTPUT*)
		        &key (START 0) (END NIL)                [Function]  

    Returns an integer representing the horizontal width that would be
    required to display STRING if it were written at the current moment
    to OUTPUT-STREAM using (WRITE-STRING STRING OUTPUT-STREAM :start
    START :end END), or NIL if this width cannot be computed.  The width
    may be negative (e.g., if STRING contains backspace or newline
    characters.)
      PRINTED-WIDTH does not return any indication of the vertical
    distance required when printing STRING.  The START and END
    parameters delimit a substring of STRING in the usual manner.
    PRINTED-WIDTH never causes any change in the state of OUTPUT-STREAM.
      The width returned may well depend on the current state of
    OUTPUT-STREAM (e.g., the width of tabs depends on the line position
    and the width of characters depends on the font in use.)  In all
    respects the width is computed based on the current state of the
    stream.  However, the width returned always assumes that the total
    line width is infinite---i.e., does not reflect any wraparound or
    truncation which might occur.

  -The difficulties of a full specification:

    The functions above are intended to solve a specific current problem
    in CL.  To serve this purpose, they must have reasonably precise
    specifications.  However, there are several things which make it
    desirable to have specifications which allow for significant
    variability between implementations.  First, current implementations
    of CL differ greatly in the way IO is supported, and overly strict
    specifications might make things very difficult for certain
    implementations.  Second, CL places no limits on the kinds of
    idiosyncratic characters which can be supported by particular
    implementations.  Third, while many CL implementations only support
    the printing of characters in fixed width fonts, it is desirable to
    allow for output streams that support variable width fonts.
    Finally, it is desirable to leave room to move for the future.

  -Operations on standard characters where the line-width has not yet been exceeded.

    To deal with the problems above, a layered specification is
    provided.   The lowest level specification is given in terms of
    constraints between the four functions above.  In this lowest level
    specification, two key simplifying assumptions are made.  First, it
    is assumed that at the time the constraint applies, none of the
    previous operations on the stream S in question have caused output
    to go beyond the physical horizontal limits of the output device on
    the output lines relevant to the constraints.  I.e., it is assumed
    that truncation and or wraparound of the output has not occurred on
    these lines.  Second, it is assumed that all of the characters
    output to the stream on the output lines relevant to the constraints
    are standard characters as defined in CLTL pp 20-21.  The
    non-standard character #\newline may have been used to end one line
    and start the next.  (Note that standard characters are all simple
    characters such as A-Z.  Particularly, #\tab, #\backspace,
    #\newline, are NOT standard characters.)  It is further assumed that
    the strings (X and Y) referred to in the constraints consist solely
    of standard characters.

    Basic properties of LINE-POSITION:

    1- For all S, (not (minusp (line-position S)).
    2- For all S, (zerop (line-position (progn (terpri S) S))).
    3- For all S, If something is at line position N on one line and
       something else is at line position N on another line, then the
       two things are lined up vertically one under the other.
      
    Defining property of WRITE-SPACE

    4- For all N,S, let M = (+ (line-position S) N)
         if M <= (line-width S), then
            (= (line-position (progn (write-space N S) S)) M)

    Defining property of PRINTED-WIDTH

    5- For all X,S, let M = (+ (line-position S) (printed-width X))
         if 0 <= M <= (line-width S), then
            (= (line-position (progn (write-string X S) S)) M)

    Basic property of LINE-WIDTH

    6- For all N,S, let P = (line-position S)
        If (+ P N) <= (line-width S) then
           (write-space N S) is guaranteed to output space on the end of
           the current line without any truncation of wraparound occurring.
    7- For all X,S, let P = (line-position S)
        If 0 <= (+ P (printed-width X)) <= (line-width S) then
           (write-string X S) is guaranteed to output X on the end of
           the current line without any truncation of wraparound occurring.

    Additional properties of PRINTED-WIDTH

    8-  For all X,Y (= (printed-width (concatenate 'string X Y) S)
		       (+ (printed-width X S) (printed-width Y S)))
    9-  For all X,Z (= (printed-width X S)
		       (+ (printed-width X (write-string Z S))))

  -Support for varying width fonts.

    A key motivation behind the functions above is dealing with
    arbitrary kinds of output devices and output streams that support
    variable width fonts.  To provide for this, the properties above
    place no absolute constraints on the units used for the width
    values.  In fact, the units can vary from stream to stream.  The
    only thing that is required is that for a given stream, the units
    must be a constant throughout the life of the stream, and the four
    functions above must all operate in terms of the same units.  The
    units should be chosen to be small enough to represent the minimum
    possible difference in the length of two strings and large enough
    that it is possible to perform (write-space 1).  (I.e., a single
    pixel is a logical choice.)

    If an output stream only supports a single fixed width font, then
    the logical width unit to choose is the width of a single character.
    Given this choice, the following is a minimal implementation of the
    four functions that meets the requirements above.	

    LINE-WIDTH returns the maximum number of characters which can be
    printed on a single line.  LINE-POSITION returns the number of
    characters output since the last #\newline (or since the creation of
    the stream if no #\newlines have been output).  (WRITE-SPACE N S)
    outputs N #\space characters.  Finally, (PRINTED-LENGTH X S) =
    (length X).

  -Support for non-standard characters and situations where line width
    has been exceeded.

    In the main, the properties above can be supported even if the line
    width has been exceeded and even when non-standard charactres are
    involved.  However, characters such as #\tab and #\newline can make
    it impossible to support properties 7 and 8.  In addition, when the
    line width is exceeded, property 3 may not hold.  It is hoped that
    implementors will make a good faith effort to support the functions
    in the full range of situations which can be encountered in their CL
    implementations.  However, the simple implementation suggested above
    will probably provide at least 80% of the benefits intended.  As a
    result, it is important that people not allow the potential
    difficulties of a full implementation deter them from making a
    minimal implementation.

  -Support for derivative streams.  

    Intentionally, very little is said about what the width units should
    be or exactly what LINE-WIDTH should return.  The only key criterion
    is that LINE-WIDTH should return a result that is pessimistic enough
    to ensure proper printing.  However, it is useful to make some
    comments about these matters with regard to certain types of
    derivative streams.

    If a synonym stream, two way stream, or echo stream is created, it should
    have the same line-width and width unit as the base output stream.

    A string output stream should have a line-width of NIL and probably
    should be treated as supporting a fixed width font and having an
    output width unit so that each character has a printed-width of 1.

    If a broadcast stream is created, then LINE-LENGTH, LINE-POSITION,
    and PRINTED-WIDTH should be be supported by reflecting them through
    to the FIRST base stream.  (There is no guarantee that anything
    reasonable can be done with the streams as a set.  For example, one
    might support a varying length font while the others don't.)  An
    attempt should be made to send WRITE-SPACE requests to all of the
    base streams.  However, they may not come out right on other than
    the first base stream.

Test Case:

  Suppose that S is an output stream that supports a single fixed
  width font which can display 72 characters on a line and that the
  associated width unit is the width of one character.  Evaluating the
  following will produce the results shown.

  (line-width S) => 72
  (terpri S) => nil
  (output-position S) => 0
  (printed-width "testing: " S) => 9
  (write-string "testing: " S) => "testing: "
  (line-position S) => 9
  (write-string "foo" S) => "foo"
  (terpri S) => nil
  (write-space 9 S) => T
  (write-string "bar" S) => "bar"

  The output produced is
testing: foo
	 bar

Rationale:

  Pretty printing requires the function LINE-WIDTH to know how wide the
  output it produces can be.  Pretty printing requires LINE-POSITION to
  determine where on the line output is when pretty printing starts.
  Pretty printing requires PRINTED-WIDTH to determine how much space
  things will take in the output.  (If a variable width font is being
  used, this cannot be determined without a detailed knowledge of the
  font being used.)  (Properties 7 & 8 greatly reduce the number of
  times PRINTED-WIDTH has to be called.)  Pretty printing requires
  WRITE-SPACE to get proper indentations.  (If a variable width font is
  being used, indentations may be required that cannot be obtained by
  outputting spaces.)

Current Practice:

  Essentially every implementation of Common Lisp must support the
  minimal functionality above internally in order to support PPRINT and
  the FORMAT directives ~T and ~<...~>.  However, there is no documented
  interface to this functionality in CLTL.  As a result, while some
  implementations of Common Lisp make this functionality available to
  users, some do not.  Further, the implementations that do provide
  this functionality do so in a variety of incompatible ways.

Cost to Implementors:

  This proposal is written in such a way as to allow implementations
  which do not have the ability to compute difficult values to just
  return NIL.  Very little work is forced.  The idea is to offer
  implementors a common way to provide this useful information to
  portable programs where possible.

Cost to Users:

  None. This change is upward compatible.

Cost of Non-Adoption:

  Complex output programs such as pretty printers cannot be written portably.

Benefits:

  A wide range of programs can gain better control of the format of output.

Aesthetics:

  No significant aesthetic impact other than a slight increase in the
  number of functions defined.

Discussion:

  Dick Waters submitted a request for changes along the line of the
  horizontal aspects of these functions in a letter to X3J13 dated
  June 14, 1988.  Pitman and Waters wrote up the request formally.

  STREAM-INFO:ONE-DIMENSIONAL-FUNCTIONS is the minimum which is
  required to support pretty printing into a stream which
  displays output using a variable width font.

  We drafted an alternate proposal, STREAM-INFO:TWO-DIMENSIONAL-FUNCTIONS,
  which goes significantly beyond what is needed merely for pretty printing
  and provides primitives LINE-DIMENSIONS, LINE-POSITION,
  PRINTED-DIMENSIONS, and WRITE-SPACE but it is not included here.
  A key point of contention which would be likely to swamp the 2d proposal
  is the age old question of how to handle the issue of vertical distance
  (where is the origin, which way do you count, ...). If anyone would
  prefer to see larger problem 2d proposal, it could be circulated, but at
  the last minute Pitman got worried that even the 1d version was going to
  be controversial enough and decided to keep things focused on that.

  For his own needs, Waters is strongly interested in having either
  ONE-DIMENSIONAL-FUNCTIONS or TWO-DIMENSIONAL-FUNCTIONS proposal accepted,
  but does not care which. Pitman concurs.

  One variation of the 1d proposal might be useful to consider:
   PRINTED-WIDTH could return two additional values: the number of newlines
    that WRITE-STRING of the string would execute and the maximum X position
    encountered (which might differ from the first value if the number of
    newlines was non-zero).
  This feature wasn't necessary for Waters' minimalist proposal, but Pitman
  would be willing to write it in here if people thought it would be useful
  enough for other purposes.

  The 5th version was changed from the 4th by responding to suggestions
  about better names for the functions, including a discussion of how
  line-width should apply to various kinds of derivative streams, and
  most importantly, by including a much more precise specification for
  what the minimal capabilities of the functions should be.