

DIRECTORY
Basics USING [Comparison, UnsafeBlock];

Rope: CEDAR DEFINITIONS = BEGIN
ROPE: TYPE = REF RopeRep;

XROPE: TYPE = REF XRopeRep; -- a supertype of ROPE for larger character sets (see XRope)

Comparison: TYPE = Basics.Comparison;
UnsafeBlock: TYPE = Basics.UnsafeBlock;

NoRope: ERROR; 

Cat: PROC [r1, r2, r3: ROPE, r4, r5: ROPE м NIL] RETURNS [ROPE]; 

Concat: PROC [base, rest: ROPE] RETURNS [ROPE];

Compare: PROC [s1, s2: ROPE, case: BOOL м TRUE] RETURNS [Comparison]; 

Equal: PROC [s1, s2: ROPE, case: BOOL м TRUE] RETURNS [BOOL]; 

Fetch: PROC [base: ROPE, index: INT м 0] RETURNS [CHAR]; 

Index: PROC [s1: ROPE, pos1: INT м 0, s2: ROPE, case: BOOL м TRUE] RETURNS [INT];

Find: PROC [s1, s2: ROPE, pos1: INT м 0, case: BOOL м TRUE] RETURNS [INT]; 

FindBackward: PROC [s1, s2: ROPE, pos1: INT м MaxLen, case: BOOL м TRUE] RETURNS [INT];

IsEmpty: PROC [r: XROPE] RETURNS [BOOL];

Length: PROC [base: XROPE] RETURNS [INT];

Size: PROC [base: XROPE] RETURNS [INT];

Replace: PROC [base: ROPE, start: INT м 0, len: INT м MaxLen, with: ROPE м NIL] 
RETURNS [ROPE]; 

Substr: PROC [base: ROPE, start: INT м 0, len: INT м MaxLen] RETURNS [ROPE]; 

CompareSubstrs: PROC [
s1: ROPE, start1: INT м 0, len1: INT м MaxLen, 
s2: ROPE, start2: INT м 0, len2: INT м MaxLen, 
case: BOOL м TRUE] RETURNS [Comparison];

EqualSubstrs: PROC [
s1: ROPE, start1: INT м 0, len1: INT м MaxLen, 
s2: ROPE, start2: INT м 0, len2: INT м MaxLen, 
case: BOOL м TRUE] RETURNS [BOOL]; 

Literal: PROC [rope: ROPE] RETURNS [ROPE] ~ INLINE { RETURN[rope] };

Run: PROC [s1: ROPE, pos1: INT м 0, s2: ROPE, pos2: INT м 0, 
case: BOOL м TRUE, len: INT м MaxLen] RETURNS [INT]; 

IsPrefix: PROC [prefix: ROPE, subject: ROPE, case: BOOL м TRUE] RETURNS [BOOL];

Match: PROC [pattern, object: ROPE, case: BOOL м TRUE] RETURNS [BOOL]; 

SkipTo: PROC [s: ROPE, pos: INT м 0, skip: ROPE] RETURNS [INT]; 

SkipOver: PROC [s: ROPE, pos: INT м 0, skip: ROPE] RETURNS [INT]; 

Map: PROC [base: ROPE, start: INT м 0, len: INT м MaxLen, action: ActionType] 
RETURNS [BOOL]; 

Translate: PROC [base: ROPE, start: INT м 0, len: INT м MaxLen, 
translator: TranslatorType м NIL] RETURNS [new: ROPE]; 
Lower: TranslatorType;

Upper: TranslatorType;

Flatten: PROC [base: ROPE, start: INT м 0, len: INT м MaxLen] RETURNS [Text]; 

FromProc: PROC [len: INT, p: PROC RETURNS [CHAR], maxPiece: INT м MaxLen] 
RETURNS [ROPE];

FromChars: PROC [PROC [PROC [CHAR]]] RETURNS [ROPE];

FromRopes: PROC [PROC [PROC [ROPE]]] RETURNS [ROPE];

NewText: PROC [size: TextBound] RETURNS [Text];

FromRefText: PROC [s: REF READONLY TEXT, 
start: TextBound м 0, len: TextBound м TextBound.LAST] RETURNS [Text];

ToRefText: PROC [base: ROPE] RETURNS [REF TEXT];

FromChar: PROC [c: CHAR] RETURNS [Text];

MakeRope: PROC [base: REF, size: INT, fetch: FetchType, 
map: MapType м NIL, move: MoveType м NIL] RETURNS [ROPE]; 

MakeConstantRope: PROC [char: CHAR, length: INT] RETURNS [ROPE];
AppendChars: PROC [buffer: REF TEXT, rope: ROPE, start: INT м 0, len: INT м MaxLen] 
RETURNS [charsMoved: TextBound]; 

UnsafeMoveChars: UNSAFE PROC [block: UnsafeBlock, rope: ROPE, start: INT м 0] 
RETURNS [charsMoved: INT];

ContainingPiece: PROC [rope: ROPE, index: INT м 0]
RETURNS [base: ROPE, start: INT, len: INT]; 

Balance: PROC [base: ROPE, start: INT м 0, len: INT м MaxLen, flat: INT м FlatMax] 
RETURNS [ROPE]; 

VerifyStructure: PROC [s: ROPE] RETURNS [leaves, nodes, maxDepth: INT]; 

VerifyFailed: ERROR; 

FetchType: TYPE = PROC [data: REF, index: INT] RETURNS [CHAR]; 

MapType: TYPE = PROC [base: REF, start, len: INT, action: ActionType] 
RETURNS [quit: BOOL м FALSE]; 
MoveType: TYPE = UNSAFE PROC [block: UnsafeBlock, data: REF, start: INT] 
RETURNS [charsMoved: INT м 0];

ActionType: TYPE = PROC [c: CHAR] RETURNS [quit: BOOL м FALSE]; 
TranslatorType: TYPE = PROC [old: CHAR] RETURNS [CHAR];

StringBound: TYPE = CARD16;
TextBound: TYPE = NAT15;

UncheckedFlat: TYPE = POINTER TO UncheckedFlatRep;
UncheckedFlatRep: TYPE = MACHINE DEPENDENT RECORD [
len: StringBound,
max: StringBound,
chars: PACKED SEQUENCE COMPUTED StringBound OF CHAR
];

XRopeRep: PRIVATE TYPE = MACHINE DEPENDENT RECORD [
SELECT xtag: * FROM 
eightbit => [
length: NAT15, -- Only valid for text variant
v: SELECT tag: * FROM
text => [PACKED SEQUENCE max: NAT15 OF CHAR],
node => [
depth: [0..2**13) м 0,
cases: SELECT case: * FROM 
substr => [size: INT, base: ROPE, start: INT],
concat => [size: INT, base, rest: ROPE, pos: INT],
replace => [size: INT, base, replace: ROPE, start, oldPos, newPos: INT],
object => [size: INT, base: REF, fetch: FetchType, map: MapType, move: MoveType]
ENDCASE
],
ENDCASE
],
extended => [
size: INT[0..MaxLen),
ext: REF ExtendedRep
],
ENDCASE
];

MaxLen: INT = LAST[INT];
FlatMax: TextBound = 24;
Text: TYPE = REF TextRep; -- the small, flat variant handle
TextRep: TYPE = XRopeRep.eightbit.text; -- useful for creating new text variants
RopeRep: TYPE = XRopeRep.eightbit; -- the byte-oriented variety
ExtendedRep: TYPE; -- For extension to larger character sets - operations in another interface

END.
  "╛  
Rope.mesa
Copyright ╙ 1984, 1985, 1986, 1987, 1988, 1991, 1992 by Xerox Corporation.  All rights reserved.
created by Russ Atkinson
Beach, February 21, 1985 9:26:19 am PST
Russ Atkinson (RRA) July 13, 1987 9:50:50 pm PDT
Christian Jacobi, January 12, 1988 5:42:52 pm PST
Carl Hauser, February 10, 1988 3:00:08 pm PST
Willie-s, August 1, 1991 5:28 pm PDT
Michael Plass, February 21, 1992 4:30 pm PST
Doug Wyatt, November 22, 1991 4:26 pm PST
A ROPE is (nominally) an immutable object containing a sequence of characters indexed starting at 0 for Length characters.  The representation allows certain operations to be performed without copying all of the characters at the expense of adding additional nodes to the object.  The use of immutable ropes alleviates concerns about "ownership" of the storage, and allows sharing of ropes by concurrent processes.

For a more complete explanation of ropes, see RopeDoc.tioga.

Implementation note: the bit pattern of the text variant is GUARANTEED to be consistent with the built-in Cedar type TEXT, although the types will not agree either at compile-time or runtime.  This means that one can Rope.Text or REF TEXT interchangeably provided that the runtime type is not examined, that the contents are not modified, and provided that the compiler can be fooled (via LOOPHOLE).  Since REF TEXT is bitwise compatible with Mesa LONG STRING for lengths < 32K characters, it is OK to pass flat ropes to procedures that expect LONG STRING, provided that those routines do not modify the contents.   For short STRING you are on your own (see ConvertUnsafe).
Part 1:  Basic operations and definitions
Stand-in for Basics.Comparison

Stand-in for Basics.UnsafeBlock
... is signalled if rope is invalid variant or some other invariant has broken.  This is a serious error, and indicates that either storage is corrupted, or the user has supplied a bad routine when making a rope, or some other nasty bug.

Note: BoundsFault = RuntimeError.BoundsFault; it is raised by many of the Rope operations.

There are no values of a len parameter that raise errors:  if len is too long it is shortened to indicate the rest of the rope, and if len < 0 the behavior will be as if len = 0.
... returns the concatenation of up to five ropes (limit based on eval stack depth).  BoundsFault occurs if the result would be longer than LAST[INT].
... is the two-rope (faster) version of Cat.  BoundsFault occurs if the result would be longer than LAST[INT].
... returns the lexicographic comparison of the two ropes based on CHAR collating sequence. 
case => case of characters is significant.
... tests contents equality of s1 and s2.  Faster than Compare.
case => case of characters is significant.
... fetches indexed character from given ropes.
BoundsFault occurs if index < 0 or index is >= Length[base].
... returns the smallest character position N such that N >= pos1 and Equal[Substr[s1, N, Length[s2]], s2, case].  If s2 does not occur in s1 at or after pos1, Length[s1] is returned. 
case => case of characters is significant.  BoundsFault occurs when pos1 < 0.
... is like Index, returning the smallest character position N such that N >= pos1 and Equal[Substr[s1, N, Length[s2]], s2, case], except that Find returns -1 if s2 is not found. 
case => case of characters is significant.  BoundsFault occurs when pos1 < 0.
... is like Find, except that it returns the largest character position N such that N <= pos1.
... is equivalent to Length[r] = 0.
... returns the # of characters in the given rope.
Size[base] = Length[base]
... returns rope with given range replaced by new.  BoundsFault occurs when start < 0 or start > Length[base] or the result would be longer than LAST[INT].
... returns a subrope of the base.  BoundsFault occurs if start < 0 or start > Length[base].
... returns Compare[Substr[s1, start1, len1], Substr[s2, start2, len2], case].
... returns Equal[Substr[s1, start1, len1], Substr[s2, start2, len2], case].
Part 2:  Extended operations and definitions
The identity function, useful to convey the desired type of a literal to the compiler in certain contexts, e.g. when the target type is a REF ANY.
... returns largest number of chars N <= len such that EqualSubstrs[s1,pos1,N, s2,pos2,N, case].
... returns Run[s1: prefix, s2: subject, case: case]=Length[prefix]; that is, returns TRUE iff prefix is a prefix of subject.
... returns TRUE iff object matches the pattern, where the pattern may contain * to indicate that 0 or more characters will match.  If case is true, then case matters. 
... returns the lowest position N in s such that s[N] is in the skip rope and N >= pos.  If pos > Length[s] or no such character occurs in s, then return Length[s].  BoundsFault occurs when pos < 0.
... returns the lowest position N in s such that s[N] is NOT in the skip rope and N >= pos.  If pos > Length[s] or no such character occurs in s, then return Length[s].  BoundsFault occurs when pos < 0.
... applies the action to the given range of characters in the rope.  Returns TRUE when some action returns TRUE.  BoundsFault occurs when start < 0 or start > Length[base].
... applies the translation to get a new rope.  If the resulting size > 0, then new does not share with the original rope!  If xtranslator = NIL, the identity translation is performed for extented characters.  If translator = NIL, the xtranslator is used for all characters.

... changes chars to lower case
... changes chars to upper case
... returns a flat rope from the given range of characters.  BoundsFault occurs if the resulting length would be > LAST[TextBound].
... returns a new rope given a length and a proc to apply for each CHAR
... calls a generating proc which calls its argument proc once for each CHAR
... calls a generating proc which calls its argument proc once for each ROPE
it's best for the ropes to have approximately uniform size
... returns a new Rope.Text, contents uninitialized, Length[NewText[size]] = size
... makes a rope from a (substring of a) REF READONLY TEXT
causes copying, can raise BoundsFault for invalid start
... makes a REF TEXT from a rope
causes copying, can raise BoundsFault if the copied part can't fit
... makes a rope from a character
... returns a rope using user-supplied procedures and data.  Note that the user procedures MUST survive as long as the rope does!
result.Length[] = length.
result.Fetch[i] = char, for i in [0 .. length).

... appends characters to the end of a REF TEXT buffer, starting at start within the rope.  The move stops if there are no more characters from the rope OR len characters have been moved OR the buffer is full (buffer.length = buffer.maxLength); charsMoved is always the # of characters appended.  NOTE: the user is responsible for protecting buffer from concurrent modifications.
... moves characters to an UnsafeBlock, starting at start within the rope.  The move stops if there are no more characters from the rope OR block.count characters have been moved; charsMoved is always the # of characters moved.  This UNSAFE operation is mainly for the implementation of IO.RIS.  Most clients should use AppendChars.
... finds the largest piece containg the given index such that the result is either a text or an object variant.  (NIL, 0, 0) is returned if the index is NOT in the given rope.
... returns a balanced rope, possibly with much copying of components
flat' м MIN[MAX[flat,FlatMax], LAST[TextBound]]
len' м MIN[MAX[len,0], Size[base]-start]
start < 0 OR start > Size[base] => bounds fault 
the resulting maxDepth will be limited by 2+log2[len'/flat'] 
... traverses the structure of the given rope; return the number of leaves, nodes and the max depth of the rope extra checking is performed to verify invariants a leaf is a text or object variant a node is a non-NIL, non-leaf variant shared leaves and nodes are multiply counted.
occurs when VerifyStructure finds a bad egg
should not happen, of course    
Part 3:  Miscellaneous definitions
... is the type of fetch routine used to make a user rope.
... is the type of user routine used to map over a subrope; returns TRUE if some action returns TRUE.

... is the type of user routine used to move characters to an UnsafeBlock.  The move should stop if there are no more characters from the rope OR block.count characters have been moved; charsMoved is always the # of characters moved.  The data given is from the object variant.  This uses an UnsafeBlock in order to integrate well with IO.UnsafeGetBlock.
... is the type of routine applied when mapping; returns TRUE to quit from Map.

... is the type of routine supplied to Translate.
The bounds type for LONG STRING
The bounds type for REF TEXT
May be used by TRUSTED code for high-performance access to a Text variant.
No user-servicable parts inside; refer servicing to qualified personnel.
See RopeImpl for the official explanation of the RopeRep variants.
 Э╩Х  ХNewlineDelimiter
Ц(cedarcode) styleЩ codeЪЬ	Щ	KЪЬ
╧eЬUЩ`KЪЬЩKЩ'KЩ0KЪЬ1Щ1KЩ-KЩ$KЩ,KЩ)KШ KЪЬ╧kЬШЩЮKЩ KЩ<KЩ KЪЬ<Ю
Ь/ЮЬmЮЬЮЬЧЮЬ
ЮЬЮЬ!ЮЬЮЬ%ЮЬ.ЮЬЮЬGЮЬ)ЩбЧKШ ЪЮ	Ш	KЪЬЮЬШ'ЧKШ KЪ╧nЬЮЬЮЬЮШheadЪЬ)Щ)ЪЮЬЮЬЮЬ	ШKШ ЧЪЮЬЮЬЮЬ╧c<ШXKШ ЧЪЬЮЬШ%KЪЬЩKЩ ЧЪЬЮЬШ'KЪЬЩЧKШ ЪЯЬЮЬШKЪЬэЩэЧKЩ KЪЬZЩZKЩ KЦ"cedar" styleЪЬ▓Щ▓KШ ЪЯЬЮЬЮЬ
ЮЬЮЬЮЬЮЬШAKЪЬМЮЬЮЬЩЦKШ ЧЪ
ЯЬЮЬЮЬЮЬЮЬШ/KЪЬdЮЬЮЬЩnKШ ЧЪЯЬЮЬ
ЮЬЮЬЮЬЮЬШFKЪЬCЮЬЩ\KЪЬ*Щ*KШ ЧЪЯЬЮЬ
ЮЬЮЬЮЬЮЬЮЬШ>KЪЬ?Щ?KЪЬ*Щ*KШ ЧЪЯЬЮЬЮЬ	ЮЬЮЬЮЬШ9KЪЬ/Щ/KЪЬ<Щ<KШ ЧЪЯЬЮЬЮЬЮЬ
ЮЬЮЬЮЬЮЬЮЬШQKЪЬ╕Щ╕KЪЬMЩMKШ ЧЪЯЬЮЬ
ЮЬЮЬЮЬЮЬЮЬЮЬШKKЪЬ│Щ│KЪЬMЩMKШ ЧЪЯЬЮЬ
ЮЬЮЬЮЬЮЬЮЬЮЬШWKЪЬ^Щ^KШ ЧЪ
ЯЬЮЬЮЬЮЬЮЬШ(KЩ#KШ ЧЪ
ЯЬЮЬЮЬЮЬЮЬШ)KЩ2KШ ЧЪ
ЯЬЮЬЮЬЮЬЮЬШ'KЪЬЩKШ ЧЪЯЬЮЬЮЬ	ЮЬЮЬЮЬЮЬЮЬЮЬШaKЪЬСЮЬЮЬЩЫKШ ЧЪЯЬЮЬЮЬ	ЮЬЮЬЮЬЮЬШMKЪЬ\Щ\KШ ЧЪЯЬЮЬЮЬ
ЮЬЮЬЮЬ
ЮЬЮЬЮЬЮЬЮЬШЯKЪЬNЩNKШ ЧЪЯЬЮЬЮЬ
ЮЬЮЬЮЬ
ЮЬЮЬЮЬЮЬЮЬЮЬШШKЪЬLЩLKШ ЧЧЪЬ,Щ,ЪЯЬЮЬЮЬЮЬЮЬЮЬЮЬ	ШDJЪЬКЮЬЮЬЩТKШ ЧЪЯЬЮЬЮЬЮЬ
ЮЬЮЬЮЬЮЬЮЬЮЬЮЬШsKЪЬ`Щ`KШ ЧЪЯЬЮЬ
ЮЬЮЬЮЬЮЬЮЬЮЬШOKЪЬVЮЬ#Щ}KШ ЧЪЯЬЮЬЮЬЮЬЮЬЮЬЮЬШGKЪЬЮЬШЩиKШ ЧЪЯЬЮЬЮЬЮЬЮЬЮЬЮЬШ@KЪЬ ЮЬЮЬЮЬwЩ╞KШ ЧЪЯЬЮЬЮЬЮЬЮЬЮЬЮЬШBKЪ	Ь ЮЬЮЬЮЬЮЬwЩ╩KШ ЧЪЯЬЮЬЮЬ	ЮЬЮЬ ЮЬЮЬШ_KЪЬNЮЬЮЬ=ЩнKШ ЧЪЯ	ЬЮЬЮЬ	ЮЬЮЬ)ЮЬЮЬЮЬШxKЪЬНЮЬRЮЬ-ЩТKЩ ЧЪЯЬШKЪЬЩKШ ЧЪЯЬШKЪЬЩKШ ЧЪЯЬЮЬЮЬ	ЮЬЮЬЮЬ	ШNKЪЬsЮЬЩГKШ ЧЪЯЬЮЬЮЬЮЬЮЬЮЬЮЬЮЬЮЬШZKЪЬCЮЩGKШ ЧЪЯ	ЬЮЬЮЬЮЬЮЬЮЬЮЬШ4KЪЬHЮЩLKШ ЧЪЯ	ЬЮЬЮЬЮЬЮЬЮЬЮЬШ4KЪЬHЮЩLKЩ:KШ ЧЪЯЬЮЬЮЬШ/KЪЬQЩQKШ ЧЪЯЬЮЬЮЬЮЬЮЬ4ЮЬЮЬШpKЪЬ)ЮЬЮЬЮЩ:KЪЬ7Щ7KШ ЧЪЯ	ЬЮЬЮЬЮЬЮЬЮЬШ0KЪЬЮЬЮЬЩ KЪЬBЩBKШ ЧЪЯЬЮЬЮЬЮЬШ(KЪЬ!Щ!KШ ЧЪЯЬЮЬЮЬЮЬ$ЮЬЮЬЮЬЮЬШsKЪЬБЩБKШ ЧЪЯЬЮЬЮЬ
ЮЬЮЬЮЬШ@KЩKЩ/KЩ ЧЪЯЬЮЬ
ЮЬЮЬЮЬ	ЮЬЮЬЮЬШvKЪЬ'ЮЬЮЬ╠Щ√KШ ЧЪЯЬЮЬЮЬЮЬ	ЮЬЮЬЮЬШiKЪЬъЮЬ/ЮЬЮЬ'Щ╠KШ ЧЪЯЬЮЬЮЬ	ЮЬЮЬЮЬ	ЮЬЮЬШ_KЪЬsЮЬ:Щ░KШ ЧЪЯЬЮЬЮЬ	ЮЬЮЬЮЬЮЬЮЬШdЪЬEЩEKЪЬЮЬЮЬЮЬЩ/KЪЬЮЬЮЬЩ(KЪЬ
ЮЬ$Щ0KЪЬ=Щ=ЧKШ ЧЪ
ЯЬЮЬЮЬЮЬЮЬШHKЪЬ╘ЮЬ@ЩЧKШ ЧЪЯЬЮЬШKЪЬ+Щ+KЪЬ Щ KШ ЧЧЪЬ"Щ"ЪЬЮЬЮЬЮЬ	ЮЬЮЬЮЬШ?KЪЬ:Щ:KШ ЧЪЬ	ЮЬЮЬЮЬЮЬЮЬЮЬЮЬШeKЪЬDЮЬЮЬЩeKЩ ЧЪЬ
ЮЬЮЬЮЬЮЬ	ЮЬЮЬЮЬШhKЪЬ╨ЮЬЩтKШ ЧЪЬЮЬЮЬЮЬЮЬЮЬЮЬШ@KЪЬ9ЮЬЩOKЩ ЧЪЬЮЬЮЬЮЬЮЬЮЬШ7KЪЬ1Щ1KШ ЧЪЬЮЬЮЬШKЪЬЮЬЮЩЧЪЬЮЬЮЬШKЪЬЮЬЮЩKШ ЧKЪЬЮЬЮЬЮЬШ2Ъ	ЬЮЬЮЬЮ	ЬЮЬШ3KЩJKЪЬHЩHKШKШKЪ
ЬЮЬЮЬЮЬЮЬЮШ3KШKШ ЧЪЬ
ЮЬЮЬЮЬЮ	ЬЮЬШ3KЩBЪЮЬ	ЮЬШЪЬШKЪЬЮЬаШ-ЪЬЮЬЮШKЪЬ	ЮЬЮЬЮЬЮЬЮЬШ-ЪЬ	Ш	KШЪЬЮЬ	ЮЬШKЪЬЮЬЮЬ	ЮЬШ.KЪЬЮЬЮЬЮЬШ2KЪЬЮЬЮЬЮЬШHKЪЬЮЬЮЬ1ШPKЪЮШЧKШЧKЪЮШЧKШЧЪЬШKЪЬЮЬШKЪЬЮЬШKЪЬШЧKЪЮШЧKШKШ ЧKЪЬЮЬЮЬЮЬШKЪЬШKЪЬЮЬЮЬ
а!Ш;KЪЬ	ЮЬа(ШPKЪЬ	ЮЬаШ?KЪЬЮЬаKШ^ЧKШ KЪЮЬШЧ ЕЧ    ╩  C  