27.3.1 BitmapFile

Apart from the drawing commands supported through the type DrawCommand, the Fudget library also supports the Xlib library call XReadBitmapFile for reading images (bitmaps) from files:

data XRequest   = ... | ReadBitmapFile FilePath | ...
data XResponse  = ... | BitmapRead BitmapReturn | ...

data BitmapReturn = BitmapBad | BitmapReturn Size (Maybe Point) PixmapId

This means that we can easily create a data type that allows us to use images stored in files as graphical objects.

data BitmapFile = BitmapFile FilePath

instance Graphic BitmapFile where ...

As you can see in Figure 64, by using the type BitmapFile, a program that loads an image from a file and displays it is as just as simple as the "Hello, world!" program (see Section 9.1):

import Fudgets main = fudlogue (shellF "Hello" helloF) helloF = labelF (BitmapFile "hello.xbm")

Figure 64. The graphical version of the "Hello, world" program is just as simple as the textual version in Section 9.1.

27.3.2 FlexibleDrawing

The Fudget library provides the following type to create stretchable graphical objects:

data FlexibleDrawing = FlexD Size Bool Bool (Rect -> [DrawCommand])

instance Graphic FlexibleDrawing where ...

The first argument of the FlexD constructor indicates a nominal size, but the actual size is determined by the fudget layout system and depends on the context. The next two arguments indicate the stretchiness, that is, whether the size should be fixed horizontally and vertically, respectively.

The last argument is a function that should produce drawing commands that draw within the given rectangle. The argument is a rectangle rather than just a size to make flexible drawings more efficient to use as parts of structured graphical objects. Although the drawing function could draw completely different things for different rectangle position and sizes, changing the position is expected to have no other effect than a translation, that is,

f (Rect pos size) = moveDrawCommands (f (Rect origin size)) pos

where moveDrawCommands,

moveDrawCommands :: [DrawCommand] -> Point -> [DrawCommand]

moves (translates) drawing commands. Changing the size is expected make the function adjust the drawing to fill the available space, typically by stretching it.

As an example, here are flexible drawings for filled rectangles, horizontal lines and vertical lines:

filledRect, hFiller, vFiller :: Int -> FlexibleDrawing

filledRect = filler False False
hFiller = filler False True
vFiller = filler True False
filler fh fv d = FlexD (Point d d) fh fv (\r->[FillRectangle r])

A sample usage can be seen in Figure 66.

27.3.3 Fixed size drawings

Having defined the type FlexibleDrawing, we can easily define a function for creating graphical objects of a fixed size:

fixedD :: Size -> [DrawCommand] -> FlexibleDrawing
fixedD size dcmds = FlexD size True True drawit
  where drawit (Rect pos _) = moveDrawCommands dcmds pos

The arguments are a list of drawing commands to draw the desired shape and a size. The commands are expected to draw within a rectangle of the indicated size, with the origin as the upper left corner.(Footnote: Instead of leaving it to the user to indicate the size of the drawing, it would be possible to compute a bounding rectangle by inspecting the drawing commands, but doing it accurately in the general case is rather involved and would be less efficient.)

Notice that depending on how you define your FlexibleDrawing value, you may get very different operational behaviour. Using fixedD, you will get a value containing a reference to a list of drawing commands that will be retained in the heap and translated to the appropriate position (by moveDrawCommands) each time the drawing is used. For FlexibleDrawings created like filler above, the drawing commands may be recomputed and thrown away each time the drawing is used. So, although the result on the screen will be the same, how much recomputation that occurs and how much memory is used depends on details in how the program is written and what kind of lambda lifting the compiler does (whether it supports full laziness [Kar92]).

27.4.1 Manipulating drawings

Some functions to manipulate parts of drawings are shown in Figure 65. These can be used in the implementation of structure editors. Values of type DPath identify parts of drawings.

type DPath = [Int] up :: DPath -> DPath drawingPart :: Drawing a b -> DPath -> Drawing a b maybeDrawingPart :: Drawing a b -> DPath -> Maybe (Drawing a b) updatePart :: Drawing a b -> DPath -> (Drawing a b -> Drawing a b) -> Drawing a b mapLabelDrawing :: (a -> b) -> Drawing a c -> Drawing b c mapLeafDrawing :: (a -> b) -> Drawing c a -> Drawing c b drawingLabels :: Drawing a b -> [(DPath, a)] deletePart :: Drawing a b -> DPath -> Drawing a b ...

Figure 65. Some functions for manipulating parts of drawings.

27.4.2 Mixing graphical objects of different types in one drawing

In a Drawing, all the leaves must have the same type. Although you could draw anything using only leaves of type FlexibleDrawing, it would be more convenient to be able to mix different types of leaves. For this purpose, the Fudget library provides the following type that makes use of existentially quantified types [LO92]:

data Gfx = (Graphic ?a) => G ?a

instance Graphic Gfx where ...  -- trivial

g :: Graphic a => Drawing lbl Gfx
g = AtomicD . G

In the definition of Gfx, ?a is an existentially quantified type variable. The context (Graphics ?a) => limits the domain of the variable to the types in the Graphic class. The result is that the constructor G can be applied to a value of any type in the Graphic class, yielding a value of type Gfx. When you later use pattern matching to extract the argument of G, you will not know what type it has, but you will know that the type is in the Graphic class, so you can apply the methods of that class on it. So, making Gfx an instance of the Graphic class becomes trivial. (The instance declaration is shown in Figure 71).

An example where strings and a FlexibleDrawing are mixed in a Drawing is shown in Figure 66.

placedD verticalP [SpacedD centerS (g "1"), g (hFiller 1), g "x+y"]

Figure 66. A sample drawing with leaves of different types.

The use of existential types gives us a way of packaging data with the methods that operate on it and abstract away from the concrete representation of the data. This is reminiscent of how data abstraction is achieved in object-oriented programming. (The reader is referred to [CW85] for a fuller discussion of the relation between existential types, data abstraction and object-oriented programming.)

27.4.3 Drawing attributes

Most of the Xlib drawing commands have an argument of type GC, a graphics context. This is a data structure containing the values of a number of parameters that affect the result of the drawing commands, but which would be tiresome to have to pass explicitly as arguments every time you draw something. Examples of such parameters, or attributes, are:

• foreground and background colors,
• which font to use for text,
• line width, line style (e.g., solid or dashed), fill style.

Most of these attributes are specified by numbers or elements of enumeration types, but colors and fonts are more troublesome. Colors can be specified using, e.g., color names or RGB values, but before a color can be used in a GC it must be converted to a pixel value. Depending on the visual type of the display, a pixel value can be, e.g., an 8-bit index into a 256 element colormap (for 8-bit PseudoColor displays) or RGB information packed into 16 or 24 bits (for 16-bit and 24-bit TrueColor displays, respectively).

Fonts can be specified by font names, but before they can be used, they have to be converted to font identifiers. Also, if you want to know how much space the text you draw will take up, you need obtain a data structure containing metric information on the font.

The data types provided by the Fudget library for specify drawing attributes are shown below. The types ColorSpec and FontSpec are described further in the next section.

data GCSpec
  =  SoftGC [GCAttributes ColorSpec FontSpec]
  |  HardGC GCtx

data ColorSpec -- see below
data FontSpec -- see below

data GCAttributes color font
  =  GCFunction GCFunction
  |  GCForeground color
  |  GCBackground color
  |  GCLineWidth Width
  |  GCLineStyle GCLineStyle
  |  GCFont font
  |  GCCapStyle GCCapStyle
  |  GCFillStyle GCFillStyle
  |  GCTile PixmapId
  |  GCStipple PixmapId
  ...

data GCtx = GC GCId FontStruct

data FontStruct -- abstract type for font metric info
data GCId -- An Xlib GC
type Width = Int

data GCFunction = GXclear | GXand | GXandReverse | GXcopy | ... | GXset 
data GCLineStyle = LineSolid | LineDoubleDash | LineOnOffDash
data GCCapStyle = CapNotLast | CapButt | CapRound | CapProjecting
data GCFillStyle = FillSolid | FillTiled | FillStippled | FillOpaqueStippled

To include drawing attributes in a Drawing (defined above), you use the constructor AttribD applied to a GCSpec, which usually is the constructor SoftGC applied to a list of attributes containing high-level specifications of fonts and colors. However, before the drawing can be displayed, this high-level specification must be converted into a GC. In addition, to be able to automatically determine the size of text, the metric information for the specified font is required. The high-level drawing attributes are therefore converted into a value of type GCtx by fudgets that display drawings. This conversion may require calls to Xlib library functions like XLoadQueryFont, XAllocNamedColor and XCreateGC. For drawings that are to be displayed many times, making these calls every time can cause a noticeable performance degradation, so the library provides a way to create GCtx values in advance. These can then be included in drawings using GCSpecs with the constructor HardGC. The drawing can then be displayed without making any calls except for the necessary drawing commands. The reason for choosing the names SoftGC and HardGC is that the subdrawings of a node setting the drawing attributes using the SoftGC alternative, inherit the attributes not present in the GCAttributes list from the parent drawing, whereas with the HardGC alternative, all attributes are taken from the given GCtx.

27.4.4 Specifying fonts and colors

To allow fonts and colors to be specified conveniently in different ways, we have introduced the following types and classes:

class ColorGen a where ...
data ColorSpec -- an abstract type
colorSpec :: ColorGen a => a -> ColorSpec

class FontGen a where ...
data FontSpec -- an abstract type
fontSpec :: FontGen a => a -> FontSpec

The following types are instances of the ColorGen class and can be used to specify colors:

type ColorName = String -- color names, as used by Xlib

data RGB = RGB Int Int Int -- RGB values, as used by Xlib

data Pixel -- previously obtained pixel values

Values of the RGB type specifies the intensities of the primary colors red, green and blue, using 16-bit integers. RGB 0 0 0 is black, and RGB 65535 65535 65535 is white.

The following types are instances of the FontGen class and can be used to specify fonts:

type FontName = String -- font names as used by Xlib

data FontStruct -- a previously obtained FontStruct

The canonical way of including font and color specifications in a drawing is to do something like this:

blueHelloMsg =
   AttribD (SoftGC [GCForeground (colorSpec "blue"),
                    GCFont (fontSpec "-*-times-*-r-*-18-*")]),
           (g "Hello, world!")

As you can see, this is rather clumsy, so the Fudget library provides the following, more convenient functions:

bgD, fgD ::  ColorGen color =>
             color -> Drawing lbl leaf -> Drawing lbl leaf

fontD ::  FontGen font =>
          font -> Drawing lbl leaf -> Drawing lbl leaf

Using these, you can write the above example like this:

blueHelloMsg = fgD "blue" $ fontD "-*-times-*-r-*-18-*" $
               g "Hello, world!"

27.4.5 Allocating colors and fonts in advance

As mentioned above, you might for efficiency reasons want to allocate colors and fonts in advance, and include the resulting GCtx values in the drawings you construct. For this purpose, the Fudget library provides the following:

wCreateGCtx :: (FontGen b, ColorGen a) =>
               GCtx -> [GCAttributes a b] -> (GCtx -> F c d) -> F c d

rootGCtx :: GCtx

The function wCreateGCtx allows you to create GCtx values, by modifying a template GCtx. You can start from rootGCtx which contains the default settings for all attributes.

27.5.1 The capabilities of graphicsF

Since graphicsF is intended to satisfy all the needs for displaying graphics within the Fudget library, and also be the ground on which applications like syntax directed editors and web browsers can be built, it has been made fairly general. In addition to just displaying graphics, graphicsF

• can receive requests to change parts of a complex drawing. This allows you to create editors with efficient screen updates. If graphicsF only accepted complete drawings as input, either the entire window would have to be redrawn after each change, or expensive computations would be needed to calculate the difference between the new and the old drawing.
• can highlight part of a drawing in a fairly efficient way. This can be used to implement cursors in editors.
• supports receiving mouse and keyboard input. graphicsF indicates which part of a drawing a mouse click occurred in.
• can display a background image behind a drawing.
• can sound the terminal bell.
• can be told to make a certain part of a drawing visible when displaying a large drawing in a scrolling area.

The type of graphicsF is:

graphicsF :: (Graphic a) => F (GfxCommand a) GfxEvent

The definitions of the message types GfxCommand and GfxEvent are show in Figure 67. The constructor ChangeGfx creates messages that allow you to replace or modify the graphical object being displayed. The argument is a list of changes. Each change has the form

(path,(hilite,opt_repl))

where path selects which part of the object should be changed, hilite switches on or off highlighting and opt_repl is an optional replacement for the selected part.

graphicsF is actually a simplification of graphicsGroupF,

graphicsGroupF :: (Graphic gfx) => 
                  (F a b) -> F (Either (GfxCommand gfx) a) 
                               (Either GfxEvent b)

which like groupF, discussed in Section 22.1.2, can contain subfudgets. The fudget activeGraphicsF (discussed in Section 32.3) for displaying drawing with active parts (for example forms in a web browser) is built on top of graphicsGroupF.

There are also customisable versions of these fudgets, allowing you to change parameters like the event mask, border width and resizing policy.

data GfxCommand gfx = ChangeGfx [(DPath,(Bool,Maybe gfx))] | ChangeGfxBg ColorSpec | ChangeGfxBgPixmap PixmapId Bool -- True = free pixmap | ShowGfx DPath (Maybe Alignment,Maybe Alignment) -- makes the selected part visible | BellGfx Int -- sound the bell | GetGfxPlaces [DPath] -- ask for rectangles of listed paths data GfxEvent = GfxButtonEvent { gfxState :: ModState, gfxType :: Pressed, gfxButton:: Button, gfxPaths :: [(DPath,(Point,Rect))] } | GfxMotionEvent { gfxState :: ModState, gfxPaths :: [(DPath,(Point,Rect))] } | GfxKeyEvent { gfxState::ModState, gfxKeySym::KeySym, gfxKeyLookup::KeyLookup } | GfxPlaces [Rect] -- response to GetGfxPlaces | GfxResized Size

Figure 67. The message types used by graphicsF.

27.5.2 Implementation of graphicsF

The fudget graphicsGroupF is implemented using groupF:

graphicsGroupF subfudgets = groupF graphicsK subfudgets

graphicsK = ...

The behaviour of the fudget is thus implemented in the fudget kernel graphicsK. Here is roughly what graphicsK does in the course of displaying a graphical object.

• A graphical object is received on the high-level input.
• The sizes of the parts of the graphical object are determined and the required resources (fonts, colors, GCs) are allocated. This part requires calls to Xlib, which are made by graphicsK through the appropriate low-level messages. The result is a value of type MeasuredGraphics (Figure 68), containing leaves of known sizes (i.e., with known LayoutRequests), GCtxs and placers/spacers.

  data MeasuredGraphics = LeafM LayoutRequest GCtx (Rect->[DrawCommand]) | SpacedM Spacer MeasuredGraphics | PlacedM Placer MeasuredGraphics | ComposedM [MeasuredGraphics]

  Figure 68. The type MeasuredGraphics.

  The conversion from an arbitrary graphical object to a value of type MeasuredGraphics is done using the methods of the Graphic class. These are shown in Figure 69. Sample instance declarations are shown last in this section.

  class Graphic a where measureGraphicK :: a -> GCtx -> Cont (K i o) MeasuredGraphics measureGraphicListK :: [a] -> GCtx -> Cont (K i o) MeasuredGraphics -- Default method for lists: measureGraphicListK xs gctx cont = ... -- converts xs one element at a time and applies ComposedM -- to the resulting list.

  Figure 69. The methods of the Graphic class.

• The layout is computed, generating a value of type CompiledGraphics (Figure 70), containing bounding rectangles and drawing commands for all the parts. This step is taken by a pure function:

  compileMG ::  MeasuredGraphics 
            ->  (CompiledGraphics, LayoutRequest)

  data CompiledGraphics = CGraphics Rect Cursor [XCommand] [CompiledGraphics] -- The only XCommand used is -- Draw MyWindow some_GC some_DrawCommand type Cursor = Bool

  Figure 70. The type CompiledGraphics.

• When Expose events are received, the drawing commands of the parts whose bounding rectangles intersect with the damaged rectangles can efficiently be extracted and output. Notice that the drawing commands are kept in the form of XCommands in the CompiledGraphicss. This means that they can be output as they are. No temporary data structures need to be created when responding to an Expose event. This fact, in combination with the use of bounding rectangles allows Expose events to be handled very efficiently. This is noticeable in applications like WWWBrowser and Alfa.
• When a part of the drawing is replaced by a new drawing, the new drawing is converted into a MeasuredGraphics and inserted in the old MeasuredGraphics at the appropriate place. (Paths are preserved when a Drawing is converted into a MeasuredGraphics.) A new CompiledGraphics is then computed from the new MeasuredGraphics. Guided by the paths of the changes and the differences between the bounding rectangles of the corresponding parts in the old and new CompiledGraphics, only those parts that have actually changed, or have moved because of the changes, are redrawn.

A shortcoming of current implementation of graphicsF is that it does not handle overlapping parts properly, not because overlapping parts would be too difficult to handle in the current solution, but simply because it has not been important in the applications where graphicsF has been used so far. This means that a drawing with overlapping parts can look different after part of it has been redrawn in response to an Expose event.

Finally, some sample instance declarations for the Graphic class are shown in Figure 71.

instance Graphic Gfx where measureGraphicK (G x) = measureGraphicK x instance Graphic FlexibleDrawing where measureGraphicK (FlexD s fh fv drawf) gctx k = k (LeafM (plainLayout s fh fv) gctx drawf) -- plainLayout is defined in Section 27.6.2. instance Graphic Char where measureGraphicK c = measureString [c] measureGraphicListK = measureString instance Graphic a => Graphic [a] where measureGraphicK = measureGraphicListK instance Graphic Int where -- and similarly for other basic types measureGraphicK i = measureString (show i) measureString s gctx@(GC gc fs) k = let r@(Rect _ size) = string_rect fs s d = font_descent fs a = font_ascent fs p1 = Point 0 a -- left end of base line reference point p2 = Point (xcoord size) a -- right end of base line ref point drawit (Rect p (Point _ h)) = [DrawString (p+(Point 0 (h-d))) s] in k (LeafM (refpLayout size True True [p1,p2]) gctx drawit) -- refpLayout is defined in Section 27.6.2.

Figure 71. Some sample instances for the Graphic class.

27.5.3 Efficiency issues in the implementation of graphicsF

As mentioned above, when part of a drawing is replaced, graphicsF recomputes the layout of the complete drawing. None of the old layout computations are utilised in this step. This may put an upper limit on how big objects can be handled with reasonable response times in a structure editor. A better solution would be to reuse layout information for parts that are not affected by a change. This is done in the ordinary fudget layout system (see Chapter 23).

Large drawings consist of many DrawCommands. Outputting these one at a time in low-level messages turned out to entail a considerable overhead. For example, redrawing the window after a page scroll in the editor Alfa (Chapter 33) in a typical situation could take 1 second. In an attempt to improve this, we added a new constructor to the XCommand type:

data XCommand = ...  | XDoCommands [XCommands] ...

It allows many commands to be passed in one low-level message, thus allowing all the DrawCommands needed to redraw a window to be passed in one message from graphicsF to the top level of the fudget hierarchy. The message passing overhead thus becomes negligible. Also, caches and other filters (see Chapter 24) that previously had to examine every DrawCommand now only examine one XDoCommands message (they do not look inside). This reduced the above mentioned redrawing time from 1 second to about 0.1 second, which makes a big difference from the user's point of view.

27.6.1 Reference points

To implement alignP, the layout requests (see Chapter 23) were extended to contain, in addition to the nominal size and the stretchiness, a list of reference points:

data LayoutRequest
  = Layout {  minsize :: Size,
              fixedh, fixedv :: Bool,
              refpoints :: [Point] }

The use of these appear in the Graphic instance for strings (see the function measureString in Figure 71).

alignP places the argument boxes so that the last reference point in one box coincides with the first reference point in the next box. This gives us base line alignment when composing text.

Unlike most other placers, alignP does not stretch the argument boxes. In fact, we have not included a mechanism for specifying how reference points are affected by stretching, so you may get odd layout if a box containing reference points is first stretched by one placer and then aligned with another box containing reference points by alignP.

We have also found use for some spacers that manipulate reference points:

refMiddleS, refEdgesS, noRefsS :: Spacer

moveRefsS :: Point -> Spacer

The spacer refMiddleS replaces the reference points of a box with two reference points placed on the middle of the left and right edges. refEdgesS takes the first and last reference points and moves them horizontally to the left and right edges, respectively. noRefsS removes the reference points from a box. moveRefsS displaces the reference points of a box by a given vector.

The placers and spacers we have presented do not make use of more than two reference points, so it perhaps seems more appropriate to have a pair (instead of a list) of reference points in the layout requests. One can also consider more elaborate use of reference points, for example, different placers might use different sets of reference points. To take a concrete example, when putting equations together horizontally in a comma separated list, you probably want to do base line alignment, but when placing equations in a vertical list, you may want them to appear with the = symbols on the same vertical line. Also, you may want the layout system to choose between horizontal and vertical placement depending on the available space, so the equations must contain reference points for both possibilities, and the placers must be able to choose between them.

27.6.2 Line breaking

The fudget layout system computes the layout in two steps: first a bottom-up pass collects the layout requests from the leaf boxes, giving the required size of the top-level window as a result. Based on this size, the exact placement of each box is computed in a top-down pass. The actual size of each box depends on the requested sizes of all boxes. The actual sizes can also be changed if the user resizes the shell window.

To display text with automatic line breaking, we would like the requested height to depend on the actual width. The line breaking should be redone when the width of the window is changed.

In the original fudget layout system, there was no way for a fudget to ask for a size where the requested height depends on the available width. A fudget could still achieve this behaviour: whenever notified of a size change, it could output a new request with the same width as in the notification but with a new height. Care of course had be taken to avoid generating infinite sequences of notifications and requests and other unpleasant effects. This solution was used in an early version of the web browser described in Chapter 32.

As part of the work on support for structured graphics, we developed a better solution to the line breaking problem. We extended the layout requests with a function that answers the question ``if you can be this wide, how tall do you want to be?''. For symmetry, there is also a function that allows the requested width to depend on the actual height (otherwise flipP would not work). The two functions are called wAdj and hAdj, respectively.

data LayoutRequest
  = Layout {  minsize :: Size,
              fixedh, fixedv :: Bool,
              refpoints :: [Point],
              wAdj, hAdj :: Int -> Size}

The placers now combine such functions in addition to combining nominal sizes and stretchiness. Although the old behaviour can be achieved by using constant wAdj/hAdj functions, the layout requests still contain the usual nominal size. This saves us from having to rewrite all placers and spacers. Also, the usual nominal size is still used rather than the wAdj/ hAdj functions on the top level in normal shell windows, while the wAdj function is used in vScrollF (see Section 10.7) , where the width is constrained but the height can vary freely. (Not surprisingly, hAdj is used in hScrollF.)

Changing the data type LayoutRequest meant that all occurrences of the constructor Layout in the Fudget library had to be adjusted. The functions plainLayout and refpLayout were introduced to simplify these adjustments:

plainLayout s fh fv = refpLayout s fh fv []
refpLayout s fh fv rps = Layout s fh fv (const s) (const s) rps

27.6.3 Conditional spacers and placers

Occasionally, we have found use for combinators that try alternative layouts and pick the best one according to some condition. We have implemented an ad hoc choice of such combinators:

ifSizeP  :: (Size->Size->Bool) -> Placer -> Placer -> Placer
ifSizeS  :: (Size->Size->Bool) -> Spacer -> Spacer -> Spacer

stretchCaseS :: ((Bool,Bool)->Spacer) -> Spacer

alignFixedS :: Alignment -> Alignment -> Spacer

The first two allow you to choose between two placers/spacers depending on the size of the resulting box, i.e., if placer₁ and placer₂ yield boxes of size₁ and size₂, respectively, then ifSizeP p placer1 placer2 uses placer₁ if p size1 size2 is True, and placer₂ otherwise. ifSizeS works analogously for spacers.

stretchCaseS allows you to write spacers that depend on the horizontal and vertical stretchiness of the argument box. alignFixedS is an application of stretchCaseS. It can be used to allow stretchable graphical objects to be stretched while objects of fixed size are aligned. As an example, when buttonF was generalised from displaying strings to arbitrary graphics, we switched from unconditionally centering the label with centerS to conditionally centering it with alignFixedS aCenter aCenter. This means that text labels will be centered as before, while graphical labels may be stretched.