CheckNodeImpl.mesa
Copyright © 1985 by Xerox Corporation. All rights reserved.
written by Bill Paxton, April 1981
Bill Paxton, December 22, 1981 1:20 pm
Maxwell, January 5, 1983 12:49 pm
Russ Atkinson, March 7, 1985 3:17:23 am PST
Plass, March 14, 1985 12:30:28 pm PST
Doug Wyatt, March 3, 1985 5:45:05 pm PST
DIRECTORY
Basics,
CheckNode,
TextNode,
Rope,
TextLooks,
TextLooksSupport;
CheckNodeImpl:
CEDAR PROGRAM
IMPORTS TextLooks, TextLooksSupport, Rope, Basics
EXPORTS CheckNode
SHARES Rope, TextLooks =
BEGIN OPEN CheckNode;
Offset: TYPE = TextNode.Offset;
MaxLen: Offset = TextNode.MaxLen;
Failed: PUBLIC ERROR = CODE;
Check:
PUBLIC
PROC [node: TextNode.Ref] = {CheckTextNode[node]};
CheckTextNode:
PUBLIC
PROC [text: TextNode.RefTextNode] = {
size: Offset ← Rope.Size[text.rope];
CheckRope[text.rope];
CheckRuns[text.runs] };
CheckRope:
PUBLIC
PROC [rope: Rope.
ROPE] = {
size: Offset ← Rope.Size[rope];
CheckRopeOffset[rope, size, size, 0];
ClearRopeCache[] };
ropeCacheSize: NAT = 128; -- should be a power of 2
ropeCacheMax: NAT = (ropeCacheSize*2)/3; -- don't fill too full
ropeCacheCount: NAT; -- number of entries currently in use
RopeCache: TYPE = ARRAY [0..ropeCacheSize) OF Rope.ROPE;
ropeCache: REF RopeCache ← NEW[RopeCache ← ALL[NIL]];
ClearRopeCache:
PROC = {
ropeCacheCount ← 0;
FOR i: NAT IN [0..ropeCacheSize) DO ropeCache[i] ← NIL; ENDLOOP };
CheckRopeOffset:
PROC
[rope: Rope.ROPE, sizeMin, sizeMax: Offset, depth: NAT] = TRUSTED {
-- use explicit recursion instead of looping so if there is an error,
-- will be able to track it up the stack
initloc, loc: NAT;
found: BOOLEAN ← FALSE;
IF rope=
NIL
THEN
IF sizeMax=0 THEN RETURN ELSE ERROR Failed;
IF depth > 1000 THEN ERROR Failed;
loc ← initloc ←
(LOOPHOLE[Basics.LowHalf[LOOPHOLE[rope]],CARDINAL]/16) MOD ropeCacheSize;
DO
-- search cache
SELECT ropeCache[loc]
FROM
rope => { found ← TRUE; EXIT };
NIL => EXIT; -- this is an unused entry
ENDCASE;
SELECT (loc ← loc+1)
FROM
ropeCacheSize => IF (loc ← 0)=initloc THEN EXIT;
initloc => EXIT;
ENDCASE;
ENDLOOP;
IF ~found
THEN {
IF ropeCacheCount = ropeCacheMax
THEN {
loc ← initloc; ClearRopeCache[] };
ropeCache[loc] ← rope };
WITH x:rope
SELECT
FROM
text => {
SELECT
LONG[x.length]
FROM
< sizeMin => ERROR Failed;
> sizeMax => ERROR Failed;
ENDCASE };
node =>
WITH x:x
SELECT
FROM
substr => {
SELECT x.size
FROM
< sizeMin => ERROR Failed;
> sizeMax => ERROR Failed;
ENDCASE;
IF ~found THEN CheckRopeOffset[x.base, x.size+x.start, MaxLen, depth+1] };
concat => {
SELECT x.size
FROM
< sizeMin => ERROR Failed;
> sizeMax => ERROR Failed;
< x.pos => ERROR Failed;
ENDCASE;
IF ~found
THEN {
CheckRopeOffset[x.base,x.pos,x.pos,depth+1];
CheckRopeOffset[x.rest,x.size-x.pos,x.size-x.pos,depth+1] }};
replace => {
SELECT x.size
FROM
< sizeMin => ERROR Failed;
> sizeMax => ERROR Failed;
< x.newPos => ERROR Failed;
ENDCASE;
SELECT x.start
FROM
> x.newPos => ERROR Failed;
> x.oldPos => ERROR Failed;
ENDCASE;
IF ~found
THEN {
CheckRopeOffset[x.replace,x.newPos-x.start,x.newPos-x.start,depth+1];
CheckRopeOffset[x.base,x.size+x.oldPos-x.newPos,
x.size+x.oldPos-x.newPos,depth+1] }};
object => {
SELECT x.size
FROM
< sizeMin => ERROR Failed;
> sizeMax => ERROR Failed;
ENDCASE };
ENDCASE => ERROR Failed;
ENDCASE => ERROR Failed};
CheckRuns:
PUBLIC
PROC [runs: TextLooks.Runs] = {
size: Offset;
IF runs=NIL THEN RETURN;
size ← TextLooks.Size[runs];
CheckNodeRuns[runs,size,size,0];
ClearRunsCache[] };
runsCacheSize: NAT = 128; -- should be a power of 2
runsCacheMax: NAT = (runsCacheSize*2)/3; -- don't fill too full
runsCacheCount: NAT; -- number of entries currently in use
RunsCache: TYPE = ARRAY [0..runsCacheSize) OF TextLooks.Runs;
runsCache: REF RunsCache ← NEW[RunsCache ← ALL[NIL]];
ClearRunsCache:
PROC = {
runsCacheCount ← 0;
FOR i: NAT IN [0..runsCacheSize) DO runsCache[i] ← NIL; ENDLOOP };
CheckNodeRuns:
PROC [
runs: TextLooks.Runs,
sizeMin, sizeMax: Offset,
depth: NAT] = TRUSTED {
-- use explicit recursion instead of looping so if there is an error,
-- will be able to track it up the stack
initloc, loc: NAT;
found: BOOLEAN ← FALSE;
IF runs=
NIL
THEN
IF sizeMax=0 THEN RETURN ELSE ERROR Failed;
IF depth > 1000 THEN ERROR Failed;
loc ← initloc ←
(LOOPHOLE[Basics.LowHalf[LOOPHOLE[runs]],CARDINAL]/16) MOD runsCacheSize;
DO
-- search cache
SELECT runsCache[loc]
FROM
runs => { found ← TRUE; EXIT };
NIL => EXIT; -- this is an unused entry
ENDCASE;
SELECT (loc ← loc+1)
FROM
runsCacheSize => IF (loc ← 0)=initloc THEN EXIT;
initloc => EXIT;
ENDCASE;
ENDLOOP;
IF ~found
THEN {
IF runsCacheCount = runsCacheMax
THEN {
loc ← initloc; ClearRunsCache[] };
runsCache[loc] ← runs };
WITH x:runs SELECT FROM
base => {
SELECT TextLooksSupport.TbaseSize[@x]
FROM
< sizeMin => ERROR Failed;
> sizeMax => ERROR Failed;
ENDCASE;
IF ~found
THEN {
loc: Offset;
looks: TextLooks.Looks;
IF x.length=0 THEN ERROR Failed;
loc ← x[0].after; looks ← x[0].looks;
FOR i:
NAT
IN (0..x.length)
DO
IF x[i].after <= loc THEN ERROR Failed;
IF x[i].looks = looks THEN ERROR Failed;
loc ← x[i].after; looks ← x[i].looks;
ENDLOOP }};
node =>
WITH x:x
SELECT
FROM
substr => {
SELECT x.size
FROM
< sizeMin => ERROR Failed;
> sizeMax => ERROR Failed;
ENDCASE;
IF ~found THEN CheckNodeRuns[x.base,x.size+x.start,MaxLen,depth+1] };
concat => {
SELECT x.size
FROM
< sizeMin => ERROR Failed;
> sizeMax => ERROR Failed;
< x.pos => ERROR Failed;
ENDCASE;
IF ~found
THEN {
CheckNodeRuns[x.base,x.pos,x.pos,depth+1];
CheckNodeRuns[x.rest,x.size-x.pos,x.size-x.pos,depth+1] }};
replace => {
SELECT x.size
FROM
< sizeMin => ERROR Failed;
> sizeMax => ERROR Failed;
< x.newPos => ERROR Failed;
ENDCASE;
SELECT x.start
FROM
> x.newPos => ERROR Failed;
> x.oldPos => ERROR Failed;
ENDCASE;
IF ~found
THEN {
CheckNodeRuns[x.replace,x.newPos-x.start,x.newPos-x.start,depth+1];
CheckNodeRuns[x.base,x.size+x.oldPos-x.newPos,
x.size+x.oldPos-x.newPos,depth+1] }};
change => {
SELECT x.size
FROM
< sizeMin => ERROR Failed;
> sizeMax => ERROR Failed;
< x.start+x.len => ERROR Failed;
ENDCASE;
IF ~found THEN CheckNodeRuns[x.base,x.size,x.size,depth+1] };
ENDCASE => ERROR Failed;
ENDCASE => ERROR Failed};
***** Initialization
ClearRopeCache[];
ClearRunsCache[];
END.