Gzilla widget set design proposal

[Raph Levien <raph acm org>]

Here's the design proposal for the gzilla widget set. I think overall it's
pretty good, although I'm sure it's going to need some tinkering before
it's finished. 

Raph


Preliminary design for Gzilla widget set

23 June 1997
Raph Levien <raph@acm.org>

   I've decided that Gzilla will contain its own widget set
specialized for the display of Web pages. The original design for
Gzilla was to use GTK widgets entirely for this purpose, but now it
seems clear that this approach is not adequate. Here are the problems
I see:

1. GTK widgets inherit the 32767 pixel size limitation from X11. Since
Web pages can easily exceed this limit, it's not feasible to use a GTK
widget to represent the Web page (although this is what gzilla
currently does).

For the next two, I'm assuming that tables will be constructed with a
table widget (analogous to gtk_table) , and that each entry in the
table will also be a widget. This approach seems like a really good
idea from a modularity standpoint.

2. For GTK child widgets to get mouse events, they need to have their
own X11 windows. Thus, a good sized table could make hundreds or
thousands of these, probably swamping the X server. (Judging from the
scrolledwindow test in testgtk.c, the overhead for window creation is
in the 10ms range).

3. GTK size negotiation doesn't support wrapped text. In other words,
there's no way for the height of the widget to depend on the width.

4. Performance. When dealing dynamically with large numbers of child
widgets, GTK containers currently _suck_. Basically, they redraw the
entire container every time anything changes. In fairness, these
containers could almost certainly be tuned for better performance.
However, two issues remain: gtk_object method dispatch overhead, and
visibility (if changes happen outside the visible area, then
repainting can be avoided altogether).

   Josh MacDonald's gtk_text widget deals with some of these issues,
but cannot be extended in modular fashion to handle things like
tables, and also cannot cleanly support GTK child widgets.

   Thus, I propose a new Gzilla widget set to function alongside the
GTK widget set. Gzilla widgets will be extremely specialized - they
will lack all features not required for Web page display (I have in
mind grabs, focus, keyboard accelerators, key events, selections, and
connectable signals, leaving only size negotiation, exposure, and
mouse events). If any of these features are desired, do it in a GTK
widget and embed it in a Gzilla widget that contains embedded GTK
widgets. Similarly, there will be a scrolledwindow that is both a GTK
widget and a container for Gzilla widgets. This widget will handle all
of the gorp that's required to get widgets larger than 32767 pixels to
scroll cleanly.


Architecture

   To avoid the overhead of gtk_object signals, and also to make
better use of the C type system, Gzilla widgets will use a simple
class and function pointer dispatch technique.

   Specifically, one of the fields of a Gzilla widget will be a
pointer to a klass struct (so named to avoid conflict with a C++
reserved word). The klass struct contains function pointers for each
of the methods. Usually, the klass structures will be set up
statically, one for each type of widget. A method is invoked as
follows:

widget->klass->method (object, args...);

   The cost is two dereferences and an indirect function call. There
will be macros to hide some of this syntax, i.e.

#define gzilla_widget_destroy(widget) widget->klass->destroy (widget);

(note: perhaps "methods" would be a slightly better name than
"klass"?)

   Widgets will contain the following fields:

struct _GzillaWidget {
  gint req_width_min;     /* the minimum comfortable width */
  gint req_width_max;     /* the maximum comfortable width */

   /* If the widget is not to be baseline aligned, it sets its
      req_height to the height, and req_ascent zero. Conversely, if it
      wants to be baseline aligned, it sets req_height and
      req_ascent. The descent is the height minus the ascent.
   */
   gint req_height;
   gint req_ascent;

   /* Allocation is similar to GTK.

      x, y coordinates are relative to the toplevel Gzilla widget.
   */
   GzillaRect allocation;

   /* Flags include:

      + alignment options (baseline, vertical, horizontal?)

      + information about what's currently displayed, one of:
        + valid data (no need for repaint)
        + previously valid data (can incrementally repaint)
        + window background (don't need to clear before drawing)
        + good data underneath (don't clear before drawing; for layers)
        + unknown (better clear and repaint)

      + widget needs resize

      + widget contains embedded GTK widget (used to prune propagation
        of gtk_foreach calls)

   */
   gint flags;

   GzillaWidget *parent;

   /* Information about the enclosing gtk container. */
   GzillaContainerInfo *container;
};


struct _GzillaContainerInfo {
  /* The GTK widget that contains the toplevel Gzilla widget */
  GtkWidget *widget;

  /* x, y coordinates are relative to the toplevel Gzilla widget. */
  GzillaRect visibility;

  /* Add (x_offset, y_offset) to toplevel Gzilla coordinates to
     arrive at X11 window relative coordinates. */
  gint x_offset, y_offset;
};

   The following methods will be supported:

/* Determine the height of the widget given a width of width, and
   store in the req_height, req_ascent, and req_descent fields. */
void
alloc_width_req_height (GzillaWidget *widget, gint width);

/* Set the allocation rectangle in the widget, and propagate to child
   widgets if necessary. */
void
size_allocate (GzillaWidget *widget,
               GzillaRect *allocation);

/* Paint the expose rectangle. The x and y arguments contain the
   coordinates of the upper left corner of the widget with respect
   to the enclosing X11 window. This routine is also responsible for
   setting the flags to indicate that the window data is valid. */
void
paint (GzillaWidget *widget,
       gint x,
       gint y,
       GzillaRect *expose);

/* Handle a mouse event. The different events (button_press,
   button_release, and motion_notify) are combined to avoid code
   duplication in containers.

   Should we return a boolean to indicate whether the event was
   handled?   
   */
void
mouse_event (GzillaWidget *widget,
             GdkEventAny *event);

/* Do the callback once for every gtk widget inside the active
   rectangle. */ 
void
gtk_foreach (GzillaWidget *widget,
	     GtkCallback  callback,
	     gpointer     callback_data,
             GzillaRect   *active);


/* Destroy the widget, freeing all resources claimed by the widget. */
void
destroy (GzillaWidget *widget);

   In addition, two methods are supported only by containers (they
will never be called on child widgets):

/* Request that the widget be resized. */
void
request_resize (GzillaWidget *container,
                GzillaWidget *child);
/* include new widths as arguments, to support incremental updating? */

/* Request that the widget be repainted. */
void
request_repaint (GzillaWidget *container,
		 GzillaWidget *child);

   These requests will generally just set flags asking that the widget
get resized or repainted, then start a GTK idle process that calls
size_allocate to actually change the size. Thus, if a string of resize
requests comes in, the actual recalculation will only be done once.


Widget lifecycle

   The widget lifecycle is considerably simplified with respect to
GTK. In particular, the init, realize, and map methods are missing.
The width half of size_request is also missing.

   First, a *_new () call creates the widget, which is now in an
unmapped state (container is NULL). Additional calls can be used to
fill it with data, if necessary. At this point, the req_width_min and
req_width_max fields are valid. The widget is then either added to a
container or given to the scroller. Either way, a flag is set
indicating that the widget needs resize (setting the flag is the
responsibility of the container add). The request_resize request
propagates to the top of the widget hierarchy. If it's mapped, then
that starts an idle process which eventually starts the
process.

   The container add function loads the req_width_min and
req_width_max fields of the child widget, and updates its own
req_width_min and req_width_max accordingly. In most cases, this
recalculation can be done incrementally, without having to scan all
the child widgets. For example, a vbox container just sets its own
req_width_min to the child widget req_width_min if it's smaller, and
similarly for req_width_max.

   The idle process starts the next phase of size allocation with a
call to alloc_width_req_height on the toplevel widget. Now, the
toplevel widget knows how much width it is allocated, decides the
width of each of its child widgets, and propagates the
alloc_width_req_height down the tree.

   It then gathers the req_height information from each of its
children an calculates the height of the overall widget (for the vbox
widget, it's just the sum). It then returns to the toplevel container.

   The toplevel container then calls size_allocate on the toplevel
widget, which again propagates it to its children, almost entirely
analogous to GTK. Note that the width in the allocation can be
completely different than that in the alloc_width_req_height call
(perhaps the name of the latter should be changed). For example, in a
scrolling widget, the alloc_width_req_height is the width of the
window minus padding for the scrollbars, while the size_allocate width
is the maximum of that width and the req_width_min of the child.

   Finally, the toplevel container calls paint on the toplevel widget,
which again propagates it to its children. The window is now painted
and quiesces.

   When a widget needs to change size, it calls request_resize on its
container. In general, that just sets a bit and (if the bit was not
already set) propagates the request_resize to the top of the
hierarchy, where it's handled by an idle process associated with the
top container.

   When a widget's data changes, it has two choices. First, it can
call request_repaint on its container, which will propagate the "needs
repaint" bit to the top of the hierarchy for handling by an idle
process, much like the resize request. This is especially useful if
the changes might be bursty - they may get clumped together, saving
repaint time. The second choice is to just repaint the data. However,
if the widget is in need of resize, it should always defer the
repainting.


Widgets

   Initially, I envision that there would be exactly four Gzilla
widgets and one GTK widget that served as a Gzilla container. These
would be the page, bullet, GTK embedder, and table widgets, and
the scroller. The page widget would be very similar to the existing
gtk_page widget in gzilla 0.0.9. The bullet widget is trivial - it
just draws nice bullets. The GTK embedder would take care of embedding
a GTK widget in the Gzilla framework. The table widget would be quite
analogous to the GTK's table widget, but would be much smarter in
laying out wrapped text. It would also support HTML specific features
such as visible borders, size hints, and background colors for the
table entries.

   Finally, the scroller would be responsible for embedding the Gzilla
widget back into GTK. In functionality, it's basically the same as
GTK's scrolled_window widget, but it has to do a lot more to handle
the new size negotiation, especially with widgets greater than 32767
pixels. Implementation of this module will be fairly gorpy, which is
one of the main reasons why I'm proposing splitting the page display
into Gzilla widgets rather than doing a monolithic page widget with
wrapped text, tables, and embedded widgets. Ideally, the scroller can
be reused for other GTK programs that require scrolled windows that
may exceed 32767 pixels.


Scrolling architecture

   There are several possible ways to implement scrolling. Gzilla
0.0.9 currently defines a fixed size 32767 pixel window, and uses a
gdk_window_move_resize call (which in turn calls XMoveResizeWindow) to
move the window around inside the viewport. This has a lot of
advantages - child windows move around with the main one, and the X
server is responsible for generating expose events for the regions
that scroll into view. It's pretty nice, but limited to 32767 pixels.

   A different approach is taken by GTK's text widget. gtk_text has a
window that's the size of the viewport, and uses the scroll position
as an offset for drawing into the window. It uses a gdk_draw_pixmap
call (which in turn calls XCopyArea) to scroll the window contents.
This is also a pretty good approach, and is what I'd use if I didn't
have to worry about embedded widgets.

   However, in GTK, each widget that can accept keyboard and mouse
input must have its own X Window. Thus, in addition to scrolling the
contents of the page with XCopyArea, it would also be necessary to
move each of the child windows separately. The problem is that,
because the child windows can't be moved at the same time as the page
contents, they will uncover and then re-obscure actual page data. This
will generate expose events, so there will be flashing in the wake of
child widgets when the window is scrolled. Even without the flashing,
there would be a lag between the page and the child widgets, which
would not be aesthetically pleasing.

   Thus, for Gzilla I plan to use a hybrid approach. For all pages
smaller than 32767 pixels, it will behave exactly as Gzilla 0.0.9. For
larger pages, whenever the scrolling nears the edge of the 32767 pixel
window, the whole contents of the window get shifted by about 20000
pixels, and the page gets completely redrawn. Any child widgets that
jumped off the edge of the window become unmapped, and any that come
inside the new window's coordinates become mapped. Those that stay on
the window simply get moved with a size_allocate method invocation,
which turns into a gtk_window_move_resize call. The gtk_foreach method
will be used to dispatch the appropriate GTK method calls to the
embedded GTK widgets.

   Thus, the entire window will flash very infrequently, and only on
large pages. I consider this an acceptable compromise.


Tables

   The details of the table widget should help to motivate the design
of the size negotiation mechanism. In this section, I present a very
simplified table widget (no rowspan or colspan, no size hints) and
describe how the size negotiation could get implemented.

   Whenever table entries are added, the table widget incrementally
updates its req_width_min and req_width_max fields. The req_width
(either min or max) is the sum of the req widths of all columns, and
the req width of each column is the maximum of the req_width of its
entries.

   The next phase of size negotiation is the alloc_width_req_height
call. Here's where the core of the actual table layout happens -
deciding the width to allocate to each column. Expressed formally,
it's a matter of finding x_set such that:

           __
           \
 x_total = /  max (req_width_min (i), min (req_width_max (i), x_set))
           --
      i = 1..n_cols


   where req_width_{min,max} (i) is the minimum (or maximum)
requisition width for column i, and x_total is the total width given
in the alloc_width_req_height method invocation.

   There are a few ways to solve this. The bisection method will have
good performance and is really easy to code, so that's what I think
I'll use, even though there are no doubt fancier algorithms. The
bisection method will also scale up nicely when rowspans and such are
added.

   Once x_set is found, then the width of each column is just max
(req_width_min (i), min (req_width_max (i), x_set)). If you don't
understand the math, don't worry. It basically says that it tries to
make the columns all even width, to fill up the total space given, but
respects the minimum and maximum widths of each entry.

   Note: the equation above doesn't have a solution when x_total is
greater than the sum of the req_width_max for all columns. In that
case, you can do basically the same thing but ignoring the
req_width_max'es altogether.

   Once the column widths are determined, the table widget call
alloc_width_req_height on each of its children. The total height is
the sum of the heights of all of the columns, each of which is the
maximum of the heights of the entries within the column. Again, this
becomes slightly more complex in the face of colspans.

   When the _actual_ width is allocated, in the size_alloc call, the
table widths may be calculated again. However, in most cases the width
given will be the same as in the alloc_width_req_height call.

   Painting is pretty straightforward - just dispatching the paint
event to the children. One quirk is when table entries have
backgrounds. In that case, the table widget draws a filled rectangle
with the background color and set's the child widget's flags
indicating what's underneath to "good data underneath" before invoking
the paint method of the child.


Embedded GTK widgets

   When adding new GTK widgets, it is imperative to avoid repainting
the entire page. Yet, all GTK containers implement their add or pack
methods by adding the child widget to the data structure, then calling
gtk_container_check_resize on the container, which almost always does
result in a repaint of the entire container.

   The Gzilla widget that embeds GTK widgets will simply avoid calling
gtk_container_check_resize when adding new widgets. Instead, it will
directly invoke the GTK methods needed to get the child widget
displayed. Essentially, this sequence is size_request, size_allocate,
realize, and map. If the new widget is outside the visibility
rectangle, it may even be possible to defer the realize and map calls
until it actually does become visible.

   I'm not really sure what the hell happens when the child widget
requests a size change. I think the right answer may be as simple as
providing a need_resize method that invokes request_resize on the GTK
widget's Gzilla container, then returns FALSE indicating that no more
work is needed from GTK.

   I've just looked through the resize code in GTK, and must confess
that I'm lost. Some of it is clear to me, but it seems to me that the
topmost test in gtk_container_check_resize (i.e. the return value from
the gtk_container_needs_resize call) must always be true, otherwise
the child widget may not get redrawn. Actually, from testing I know
that bugs exist in which the child widget doesn't get redrawn
(especially when the topmost container is a viewport), so maybe the
code is flat out wrong. It looks like some careful hacking is needed.


Baseline alignment

   I should say a little about baseline alignment. Putting multiple
widgets on a line with baseline alignment (and perhaps also with other
text) is calculated the same way as a table with two rows. The first
row represents the ascent, and the second row represents the descent.
If a widget is not to be baseline aligned, then it's basically the
same as a colspan of two.