RopeReaderImpl.mesa
Copyright © 1985 by Xerox Corporation. All rights reserved.
written by Bill Paxton, January 1981
Bill Paxton, December 22, 1981 10:24 am
Maxwell, January 5, 1983 12:05 pm
Russ Atkinson, July 22, 1983 3:33 pm
Paul Rovner, August 10, 1983 4:21 pm
Doug Wyatt, May 23, 1984 11:37:49 am PDT
Michael Plass, February 18, 1985 9:06:37 am PST
DIRECTORY
Basics USING [CompareCard, CompareINT, Comparison],
PrincOpsUtils USING [ByteBlt],
RopeFile USING [AppendChars],
RefText USING [ObtainScratch, ReleaseScratch],
Rope USING [FetchType, InlineSize, MakeRope, MapType, NoRope, ROPE, Text],
RopeReader USING [Body, Chars, CharsArray, charsPerArray, Get, GetIndex, GetRope, MaxLen, Mode, Offset, ReadChar, Ref, SetIndex, SetPosition];
RopeReaderImpl: CEDAR MONITOR
IMPORTS Basics, PrincOpsUtils, RefText, Rope, RopeFile, RopeReader
EXPORTS RopeReader
= BEGIN OPEN RopeReader;
ROPE: TYPE = Rope.ROPE;
Text: TYPE = Rope.Text;
ReadOffEnd: PUBLIC ERROR = CODE;
ReadChar: PUBLIC PROC [reader: Ref, mode: Mode] RETURNS [char: CHAR] = {
rope: ROPE ~ reader.rope; -- the rope being read
size: INT ~ rope.InlineSize[]; -- size of the rope
index: INT ~ reader.index+reader.current; -- index of next char that Get would read
text: REF TEXT ~ reader.text; -- text buffer
length: NAT ← text.maxLength; -- number of chars to be read into buffer
forward: BOOL ~ SELECT mode FROM
get, peek => TRUE, backwards, peekbackwards => FALSE, ENDCASE => ERROR;
inBounds: BOOL ~ IF forward THEN index IN[0..size) ELSE index IN(0..size];
IF NOT inBounds THEN {
IF reader.charForEndOfRope THEN RETURN[reader.endChar]
ELSE ERROR ReadOffEnd;
};
IF forward THEN {
rem: INT ~ size-index;
IF rem<length THEN length ← rem;
reader.index ← index; reader.current ← 0;
}
ELSE {
IF index<length THEN length ← index;
reader.index ← index-length; reader.current ← length;
};
text.length ← 0;
[] ← RopeFile.AppendChars[buffer: text, rope: rope, start: reader.index, len: length];
IF text.length=length THEN {
i: NAT ~ reader.current;
SELECT mode FROM
get => { reader.current ← i+1; RETURN[text[i]] };
backwards => { RETURN[text[reader.current ← i-1]] };
peek => { RETURN[text[i]] };
peekbackwards => { RETURN[text[i-1]] };
ENDCASE => ERROR;
}
ELSE ERROR;
};
AppendToString: PUBLIC PROC[str: REF TEXT,
rope: ROPE, start: INT ← 0, len: INT ← LAST[INT]]
RETURNS [count: NAT ← 0] = {
Appends characters from the given rope onto the specified text. The move will stop at the end of the specified subrope OR the end of the rope OR the end of the text. It is the client's responsibility to determine whether enough characters have been moved. A BoundsFault will occur if start NOT IN [0..rope.Length[]].
count ← RopeFile.AppendChars[buffer: str, rope: rope, start: start, len: len];
};
AppendToChars: PUBLIC PROC[chars: REF CharsArray, offset: NAT ← 0,
rope: ROPE, start: INT ← 0, len: INT ← LAST[INT]]
RETURNS [count: NAT ← 0] = {
Appends characters from the given rope onto the specified buffer. The move will stop at the end of the specified subrope OR the end of the rope OR the end of the buffer. It is the client's responsibility to determine whether enough characters have been moved. A BoundsFault will occur if start NOT IN [0..rope.Length[]].
text: REF TEXT ← RefText.ObtainScratch[RopeReader.charsPerArray];
InRange: TYPE ~ [0..RopeReader.charsPerArray];
text.length ← 0;
count ← RopeFile.AppendChars[buffer: text, rope: rope, start: start, len: MIN[len, NAT[RopeReader.charsPerArray-offset]]];
TRUSTED {
count ← PrincOpsUtils.ByteBlt[
to: [blockPointer: LOOPHOLE[chars], startIndex: InRange[offset], stopIndexPlusOne: InRange[offset+count]],
from: [blockPointer: LOOPHOLE[text, LONG POINTER] + SIZE[TEXT[0]], startIndex: 0, stopIndexPlusOne: count]
];
};
RefText.ReleaseScratch[text];
};
GetString: PUBLIC PROC[reader: Ref, str: REF TEXT, length: NAT ← LAST[NAT]]
RETURNS [count: NAT] = {
index: INT ~ GetIndex[reader];
count ← RopeFile.AppendChars[buffer: str, rope: GetRope[reader], start: index, len: length];
SetIndex[reader, index+count];
};
BackwardsGetString: PUBLIC PROC[reader: Ref, str: REF TEXT, length: NAT ← LAST[NAT]]
RETURNS [count: NAT] = {
index: INT ~ GetIndex[reader];
rem: NAT ~ str.maxLength-str.length;
start: INT ← 0;
len: INT ← MIN[length, rem];
IF index<len THEN len ← index ELSE start ← index-len;
count ← RopeFile.AppendChars[buffer: str, rope: GetRope[reader], start: start, len: len];
SetIndex[reader, start];
};
GetChars: PUBLIC PROC[reader: Ref,
chars: REF CharsArray, length: NAT ← LAST[NAT], offset: NAT ← 0]
RETURNS [count: NAT] = {
index: INT ~ GetIndex[reader];
count ← AppendToChars[chars: chars, offset: offset,
rope: GetRope[reader], start: index, len: length];
SetIndex[reader, index+count];
};
BackwardsGetChars: PUBLIC PROC[reader: Ref,
chars: REF CharsArray, length: NAT ← LAST[NAT], offset: NAT ← 0]
RETURNS [count: NAT] = {
index: INT ~ GetIndex[reader];
rem: NAT ~ charsPerArray-offset;
start: INT ← 0;
len: INT ← MIN[length, rem];
IF index<len THEN len ← index ELSE start ← index-len;
count ← AppendToChars[chars: chars, offset: offset,
rope: GetRope[reader], start: start, len: len];
SetIndex[reader, start];
};
EqSubstrs: PUBLIC PROC [r1,r2: ROPE, start1,start2,len: Offset, rdr1,rdr2: Ref ← NIL]
RETURNS [eq: BOOLEAN] = {
-- uses readers rdr1 and rdr2 to read ropes r1 and r2 to test for equality
-- returns TRUE if r1 is same as len chars of r2 starting at start
free1, free2: BOOLEAN ← FALSE;
size1: Offset ← Rope.InlineSize[r1];
size2: Offset ← Rope.InlineSize[r2];
start1 ← MIN[start1,size1];
start2 ← MIN[start2,size2];
IF len=MaxLen THEN { IF (len ← size1-start1) # size2-start2 THEN RETURN [FALSE] }
ELSE IF start1+len > size1 THEN RETURN [FALSE]
ELSE IF start2+len > size2 THEN RETURN [FALSE];
IF rdr1 = NIL THEN { rdr1 ← GetRopeReader[]; free1 ← TRUE };
IF rdr2 = NIL THEN { rdr2 ← GetRopeReader[]; free2 ← TRUE };
SetPosition[rdr1,r1,start1];
SetPosition[rdr2,r2,start2];
eq ← TRUE;
WHILE len > 0 DO
num: NAT ← NAT.LAST; -- loop on NAT instead of INT
IF len<num THEN num ← len;
len ← len-num;
THROUGH [0..num) DO
IF Get[rdr1]#Get[rdr2] THEN { eq ← FALSE; GOTO Finis };
ENDLOOP;
REPEAT Finis => NULL;
ENDLOOP;
IF free1 THEN FreeRopeReader[rdr1];
IF free2 THEN FreeRopeReader[rdr2];
};
CompareSubstrs: PUBLIC PROC [
r1, r2: ROPE, start1, len1, start2, len2: Offset,
rdr1, rdr2: Ref ← NIL, case: BOOLEAN ← TRUE]
RETURNS [result: Basics.Comparison] = {
-- uses readers rdr1 and rdr2 to compare ropes r1 and r2
-- if ~case then all characters forced lowercase for comparison
size1: Offset ← Rope.InlineSize[r1];
size2: Offset ← Rope.InlineSize[r2];
rem, rem1, rem2: Offset;
free1, free2: BOOLEAN ← FALSE;
rem1 ← IF start1 > size1 THEN 0 ELSE size1-start1;
rem2 ← IF start2 > size2 THEN 0 ELSE size2-start2;
IF rdr1 = NIL THEN { rdr1 ← GetRopeReader[]; free1 ← TRUE };
IF rdr2 = NIL THEN { rdr2 ← GetRopeReader[]; free2 ← TRUE };
len1 ← MIN[len1,rem1]; len2 ← MIN[len2,rem2]; rem ← MIN[len1,len2];
SetPosition[rdr1,r1,start1];
SetPosition[rdr2,r2,start2];
result ← equal;
WHILE rem > 0 DO
num: NAT ← NAT.LAST;
IF rem<num THEN num ← rem;
rem ← rem-num;
THROUGH [0..num) DO
c1: CHARACTER ← Get[rdr1];
c2: CHARACTER ← Get[rdr2];
IF ~case THEN {
special crock by RRA, verified as generating good code (generates few jumps)
IF LOOPHOLE[c1-'A, CARDINAL] <= ('Z-'A) THEN
c1 ← LOOPHOLE[LOOPHOLE[c1, CARDINAL] + ('a-'A), CHAR];
IF LOOPHOLE[c2-'A, CARDINAL] <= ('Z-'A) THEN
c2 ← LOOPHOLE[LOOPHOLE[c2, CARDINAL] + ('a-'A), CHAR];
};
IF c1 # c2 THEN {
result ← Basics.CompareCard[LOOPHOLE[c1, CARDINAL], LOOPHOLE[c2, CARDINAL]];
GO TO Finis;
};
ENDLOOP;
REPEAT Finis => NULL;
ENDLOOP;
IF free1 THEN FreeRopeReader[rdr1];
IF free2 THEN FreeRopeReader[rdr2];
IF result # equal THEN RETURN;    -- if a character differerence, then return it
RETURN [Basics.CompareINT[len1, len2]]; -- if equal so far, the length determines
};
-- implementation of ropes using character arrays
CharsFetch: Rope.FetchType = {
PROC [data: REF, index: INT] RETURNS [CHAR]
WITH data SELECT FROM
x: Chars => RETURN[x[index]];
ENDCASE => ERROR Rope.NoRope;
};
CharsMap: Rope.MapType = {
PROC [base: REF, start, len: INT, action: ActionType] RETURNS [quit: BOOL ← FALSE]
WITH base SELECT FROM
x: Chars => {
k: NAT ~ start;
l: NAT ~ len;
FOR i: NAT IN[k..k+l) DO
IF action[x[i]] THEN RETURN [TRUE];
ENDLOOP;
};
ENDCASE => ERROR Rope.NoRope;
RETURN [FALSE]
};
CharsRope: PUBLIC PROC [chars: Chars] RETURNS [ROPE] = TRUSTED {
must LOOPHOLE to defeat READONLY
RETURN [Rope.MakeRope[LOOPHOLE[chars], charsPerArray, CharsFetch, CharsMap]];
};
-- ***** rope reader cache
defaultSize: NAT ← 200;
roperdr1, roperdr2, roperdr3: Ref ← NIL; -- shared rope readers
SetDefaultSize: PUBLIC ENTRY PROC[size: NAT] = {
defaultSize ← size;
roperdr1 ← roperdr2 ← roperdr3 ← NIL;
};
Create: PUBLIC PROC[size: NAT ← 0] RETURNS [Ref] = {
IF size=0 THEN size ← defaultSize;
RETURN[NEW[Body ← [text: NEW[TEXT[size]]]]]
};
GetRopeReader: PUBLIC ENTRY PROC RETURNS [reader: Ref] = {
IF roperdr3 # NIL THEN { reader ← roperdr3; roperdr3 ← NIL }
ELSE IF roperdr2 # NIL THEN { reader ← roperdr2; roperdr2 ← NIL }
ELSE IF roperdr1 # NIL THEN { reader ← roperdr1; roperdr1 ← NIL }
ELSE reader ← Create[];
};
FreeRopeReader: PUBLIC ENTRY PROC [reader: Ref] = {
SetPosition[reader, NIL];
IF reader.text.maxLength#defaultSize THEN RETURN;
reader.charForEndOfRope ← FALSE;
IF roperdr3 = reader OR roperdr2 = reader OR roperdr1 = reader THEN ERROR;
IF roperdr3 = NIL THEN roperdr3 ← reader
ELSE IF roperdr2 = NIL THEN roperdr2 ← reader
ELSE IF roperdr1 = NIL THEN roperdr1 ← reader;
};
END.