Oberon || Library || Module Index || Search Engine || Definition || Module

Ulm's Oberon Library:
FragmentedStreams

NAME

FragmentedStreams - fragmented in-memory streams

SYNOPSIS

TYPE Stream = POINTER TO StreamRec;
TYPE StreamRec = RECORD (Streams.StreamRec) END;
TYPE Label = POINTER TO LabelRec;
TYPE LabelRec = RECORD (Disciplines.ObjectRec) END;



CONST cannotReadUnfixedObject = 0;
CONST cannotWriteUnfixedObject = 1;
CONST invalidPosition = 2;
CONST errors = 3;
TYPE ErrorCode = SHORTINT;
TYPE ErrorEvent = POINTER TO ErrorEventRec;
TYPE ErrorEventRec =
   RECORD
      (Events.EventRec)
      errorcode: ErrorCode;
   END;
VAR errormsg: ARRAY errors OF Events.Message;
VAR error: Events.EventType;



PROCEDURE Create(VAR s: Stream);
PROCEDURE Open(VAR s: Stream; base: Streams.Stream);



PROCEDURE CreateLabel(VAR label: Label);
PROCEDURE AttachLabel(s: Stream; label: Label);
PROCEDURE Attached(label: Label) : BOOLEAN;
PROCEDURE IncludeObject(s: Stream; object: Disciplines.Object;
                        minsize, maxsize: Streams.Count);
PROCEDURE Distance(label1, label2: Label;
                   VAR mindist, maxdist: Streams.Count);
PROCEDURE Difference(label1, label2: Label;
                     VAR mindiff, maxdiff: Streams.Count);
PROCEDURE ObjectDistance(object: Disciplines.Object; label: Label;
                         VAR mindist, maxdist: Streams.Count);
PROCEDURE ObjectDifference(object: Disciplines.Object; label: Label;
                           VAR mindiff, maxdiff: Streams.Count);
PROCEDURE GetSizeRange(object: Disciplines.Object;
                       VAR minsize, maxsize: Streams.Count);
PROCEDURE SizeFixed(object: Disciplines.Object) : BOOLEAN;
PROCEDURE ReduceObjectSizeRange(object: Disciplines.Object;
                                minsize, maxsize: Streams.Count);
PROCEDURE SetObjectSize(object: Disciplines.Object; size: Streams.Count);
PROCEDURE FixObject(object: Disciplines.Object);
PROCEDURE Length(s: Stream; VAR minlen, maxlen: Streams.Count);
PROCEDURE GetUnfixedObjects(s: Stream; VAR it: Iterators.Iterator);
PROCEDURE NumberOfUnfixedObjects(s: Stream) : INTEGER;
PROCEDURE GetObjectsWithUnknownSize(s: Stream; VAR it: Iterators.Iterator);
PROCEDURE NumberOfObjectsWithUnknownSize(s: Stream) : INTEGER;

DESCRIPTION

FragmentedStreams works like Texts but supports the inclusion of fragments whose size and contents is determined later. This is particularly useful in the context of machine code generation where the code size of relative jumps depends on the distance between jump instruction and destination address.

Principles of Operation

Create creates (like Texts.Open) an in-memory stream that is opened for reading and writing and supports seek operations. While normal stream writing operations may be used to insert byte sequences of fixed size, IncludeObject allows to include fragments of a not yet known size between minsize and maxsize bytes. Later, the size ranges of these objects may be reduced by ReduceObjectSizeRange or finally fixed by FixObject. Fragments of zero length are permitted.

While Create uses a stream of Texts internally, Open may be used to specify another base stream that must behave like a newly created stream of Texts. This means in particular that the base stream is not expected to fail on valid operations.

As long as a fragmented stream contains objects of unknown size, some differences in comparison to ordinary in-memory streams have to be considered:

Stream positions are not fixed until all included fragments of varying size are fixed. That means that a sequence of Streams.GetPos, Streams.Write, and Streams.SetPos using the position returned formerly by Streams.GetPos is not guaranteed to return to the former position if included objects have been fixed or reduced in their size range meanwhile. Labels may be used instead.
Included objects of unknown size behave like holes and cannot be read or written until they are fixed. Their size depends dynamically on the minimal size specified so far.

Labels

Labels allow to remember stream positions in a way that is not threatened by included fragments that change their size. CreateLabel creates a new label that is not yet attached to a stream position. Later, labels may be attached once but only once to the current position of a stream using AttachLabel. Attached allows to test whether AttachLabel has been invoked already for label.

Distances between labels and/or objects may be queried using Distance and ObjectDistance. Both return the minimal and maximal distance between two locations. Difference and ObjectDifference work similar but return negative values if the second object or label precedes the first.

Examining and Fixing Objects

Length returns the current minimal and maximal length of s. GetUnfixedObjects allows to iterate through all still unfixed objects passed formerly to IncludeObject. NumberOfUnfixedObjects returns the remaining number of unfixed objects.

ReduceObjectSizeRange and SetObjectSize reduce or finally determine the size range of an object included formerly by IncludeObject. The call of ReduceObjectSizeRange with an interval of zero length is equivalent to SetObjectSize. Setting the size of an object to zero length is allowed. Reducing or finally setting the size of an object does not turn the fragment's status to fixed (even in case of zero length objects).

GetSizeRange returns the current size range of object. SizeFixed returns TRUE if the size range is of zero length.

GetObjectsWithUnknownSize allows to iterate through all objects whose size has not been fixed by know. NumberOfObjectsWithUnknownSize return the number of these objects.

FixObject sets the stream position to the current place of object where the representation of object is to be written immediately thereafter (if the object length is positive). Note that the size of object must have been defined earlier using ReduceObjectSizeRange (by giving a zero length interval) or SetObjectSize. Fixed objects must no longer be passed to any of the procedures above and they are no longer returned by GetUnfixedObjects.

Application

Generation of machine code with relative address references that need later to be fixed works in four phases:

Phase 1: Create a fragmented stream and write generated code to it. In case of instructions of beforehand unknown size objects have to be created and included that reference the destination address by a label.

Phase 2: Determine the size of all objects:

WHILE FragmentedStreams.NumberOfObjectsWithUnknownSize() > 0 DO
   FragmentedStreams.GetObjectsWithUnknownSize(s, it);
   anyObjectsChanged := FALSE;
   WHILE Iterators.Get(it, object) DO
      (* assumption: object.label is the label of the destination address *)
      FragmentedStreams.ObjectDistance(object, object.label,
         mindist, maxdist);
      IF (* mindist and maxdist define a range that finally
            resolves the size of object *) THEN
         size := (* final size *);
         FragmentedStreams.SetObjectSize(object, size);
         anyObjectsChanged := TRUE;
      ELSIF (* mindist and maxdist define a reduced range for object *) THEN
         minsize := (* new lower limit >= old lower limit *);
         maxsize := (* new upper limit <= old upper limit *);
         FragmentedStreams.ReduceObjectSizeRange(object, minsize, maxsize);
         anyObjectsChanged := TRUE;
      END;
   END;
   IF ~anyObjectsChanged THEN
      (* we have to pick one of the objects and to take the longest
         variant
      *)
      FragmentedStreams.GetObjectsWithUnknownSize(s, it);
      ok := Iterators.Get(it, object); ASSERT(ok);
      FragmentedStreams.ObjectDistance(object, object.label,
                                       mindist, maxdist);
      size := (* size in dependence of maxdist *);
      FragmentedStreams.SetObjectSize(object, size);
   END;
END;

Phase 3: Fix all objects:

FragmentedStreams.GetUnfixedObjects(s, it);
WHILE Iterators.Get(it, object) DO
   (* retrieve distance to destination if necessary *)
   FragmentedStreams.ObjectDistance(object, object.label,
      mindist, maxdist);
   ASSERT(mindist = maxdist);
   FragmentedStreams.GetSizeRange(object, minsize, maxsize);
   ASSERT(minsize = maxsize);
   size := minsize;
   FragmentedStreams.FixObject(object);
   (* write size bytes to s representing object *)
END;

Phase 4: Copy in-memory stream to output stream:
```
Streams.SetPos(s, 0); ok := Streams.Copy(s, out, -1);
```
Or, alternatively, convert it into a persistent text:
```
PersistentTexts.Create(ptext, s);
```
But note that in the latter case the close operation of s must be postponed until ptext is written using PersistentObjects.Write to its final storage.

DIAGNOSTICS

By default, error events for fragmented streams are being queued (see RelatedEvents). Beside error events generated by Streams and the underlying base stream, following error codes may be generated by FragmentedStreams:

cannotReadUnfixedObject: Unfixed objects cannot be read until FixObject is called for them.
cannotWriteUnfixedObject: Likewise, FragmentedStreams does not support write operations that would affect not unfixed objects.
invalidPosition: Negative stream positions or positions beyond the minimal length returned by Length are not supported.

A large number of preconditions is checked by assertions:

AttachLabel must not be called more than once for a label.
IncludeObject expects minsize and maxsize to be non-negative, and minsize to be less or equal to maxsize.
IncludeObject requires the current stream position to be at the end of the stream, i.e. objects can only be appended to a stream.
Distance and Difference require both labels to be attached to the same stream.
ObjectDistance and ObjectDifference expect fIlabel\fP to be attached to the stream object is included.
ReduceObjectSizeRange and FixObject require size specifications to be in between the former limits.

Some assertions check that the base stream does not fail on valid operations.

Read and write operations are clipped by unfixed objects. Operations like Streams.Read and Streams.Write return FALSE in these cases but s.count could be positive.

BUGS

Objects must not be included in more than one fragmented stream.

If the base stream does not permit holes (as Texts.Text does) fixed objects must be written entirely before attempting to perform other write operations. Violations may cause assertions to fail on later write operations.

Edited by: borchert, last change: 2004/04/23, revision: 1.7, converted to HTML: 2004/04/23