CheckNodeImpl.mesa; written by Bill Paxton, April 1981
edited by Bill Paxton, June 10, 1983 1:56 pm
edited by Maxwell, January 5, 1983 12:49 pm
edited by McGregor, February 8, 1983 11:32 am
Last Edited by: Lamming, February 24, 1983 9:10 am
DIRECTORY
CheckNode,
Inline,
Rope,
RopeEdit,
RopeInline,
TiogaLooks,
TiogaLooksOps,
TiogaLooksSupport,
TiogaNode,
TiogaNodeOps;
CheckNodeImpl:
CEDAR PROGRAM
IMPORTS TiogaLooksOps, TiogaLooksSupport, TiogaNodeOps, RopeEdit, Inline
EXPORTS CheckNode
SHARES Rope, TiogaLooks =
BEGIN OPEN CheckNode;
Offset: TYPE = TiogaNode.Offset;
MaxLen: Offset = TiogaNode.MaxLen;
Failed: PUBLIC ERROR = CODE;
Check:
PUBLIC
PROC [node: TiogaNode.Ref] =
TRUSTED {
IF TiogaNodeOps.IsText[node] THEN CheckTextNode[TiogaNodeOps.NarrowToTextNode[node]]};
CheckTextNode:
PUBLIC
PROC [text: TiogaNode.RefTextNode] = {
size: Offset ← RopeEdit.Size[text.rope];
CheckRope[text.rope];
CheckRuns[text.runs] };
CheckRope:
PUBLIC
PROC [rope: RopeEdit.
ROPE] = {
size: Offset ← RopeEdit.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 RopeEdit.ROPE;
ropeCache: RopeCache;
ClearRopeCache:
PROC = {
ropeCacheCount ← 0;
FOR i: NAT IN [0..ropeCacheSize) DO ropeCache[i] ← NIL; ENDLOOP };
CheckRopeOffset:
PROC [rope: RopeEdit.
ROPE, sizeMin, sizeMax: Offset, depth:
NAT] =
TRUSTED {
OPEN RopeInline;
-- 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[Inline.LowHalf[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: TiogaLooks.Runs] = {
size: Offset;
IF runs=NIL THEN RETURN;
size ← TiogaLooksOps.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 TiogaLooks.Runs;
runsCache: RunsCache;
ClearRunsCache:
PROC = {
runsCacheCount ← 0;
FOR i: NAT IN [0..runsCacheSize) DO runsCache[i] ← NIL; ENDLOOP };
CheckNodeRuns:
PROC [
runs: TiogaLooks.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[Inline.LowHalf[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 TiogaLooksSupport.TbaseSize[@x]
FROM
< sizeMin => ERROR Failed;
> sizeMax => ERROR Failed;
ENDCASE;
IF ~found
THEN {
loc: Offset;
looks: TiogaLooks.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};
ClearRopeCache[];
END.
Log
Modified to handle Tioga2 node structure February 24, 1983, by Lamming