PFSNamesImpl.mesa
Copyright Ó 1988, 1989, 1991 by Xerox Corporation. All rights reserved.
Carl Hauser, August 28, 1989 5:29:31 pm PDT
Bill Jackson (bj) May 31, 1989 11:21:34 pm PDT
Chauser, October 22, 1990 5:26 pm PDT
Willie-s, August 20, 1991 6:10 pm PDT
DIRECTORY
Basics USING [BoundsCheck],
PFS,
PFSNames,
Rope USING [CompareSubstrs, ROPE, Substr];
PFSNamesImpl: CEDAR PROGRAM
IMPORTS Basics, PFS, PFSNames, Rope
EXPORTS PFSNames
~ BEGIN OPEN PFSNames;
Representation
PATH: TYPE = REF PathObject;
PathObject: TYPE = PFSNames.PathObject;
PrivatePathObject: PUBLIC TYPE = PACKED RECORD [
comps: PRIVATE Components ¬ NIL,
comps[0] is most significant
IF pathKind = absolute, the first two components provide the protocol and server name.
Clients (and the implementation) must treat the comps^ as immutable, since it may be shared.
lastComp: Component ¬ [],
maybe we should provide extension parsing of this as well?
lastComp is not included in comps: the idea is to let the implementation share comps structures between Paths differing only in the last component.
absolute: BOOL ¬ FALSE,
absolute => path is absolute, i.e. begins with protocol, server, etc.
~absolute=> path is relative to some, as yet unspecified, working directory
As a wDir argument, ~absolute implies no working directory, since working directories must be absolute.
directory: BOOL ¬ FALSE,
directory=> name is syntactically that of a directory
~directory=> name is syntactically that of a file
unparsed: REF,
an unparsing hint; the various parsers may store something here to help them unparse fast.
parent: PATH ¬ NIL
another hint. If non-NIL, refers to a path object representing the parent directory for this object.
];
ComponentSequence: TYPE = RECORD [SEQUENCE count: [0..NAT.LAST) OF Component];
Components: TYPE = REF ComponentSequence;
Type Manipulation
NarrowPath: PUBLIC PROC [r: REF ANY] RETURNS [PATH] ~ {
RETURN [NARROW[r, PATH]];
};
IsPath: PUBLIC PROC [r: REF ANY] RETURNS [BOOL] ~ {
RETURN [ISTYPE[r, PATH]];
};
Parsing and Constructing Names
ConstructName: PUBLIC PROC [components: LIST OF Component, absolute, directory, reverse: BOOL ¬ FALSE, unparsed: REF ¬ NIL] RETURNS [name: PATH ¬ NIL] ~ {
A convenient way to construct names without parsing.
count: NAT ¬ 0;
name ¬ NEW [PathObject ¬ [NEW[PrivatePathObject ¬ []]]];
name.absolute ¬ absolute;
name.directory ¬ directory;
name.unparsed ¬ unparsed;
Count the components
FOR l: LIST OF Component ¬ components, l.rest WHILE l#NIL DO
count ¬ count+1;
ENDLOOP;
Allocate room in the sequence for all but the last
SELECT count FROM
0 => {
name.absolute ¬ name.directory ¬ absolute OR directory;
RETURN;
};
1 => NULL;
ENDCASE => name.comps ¬ NEW[ComponentSequence[count-1]];
Copy the components to the PATH
{
l: LIST OF Component ¬ components;
IF reverse THEN {
name.lastComp ¬ l.first;
l ¬ l.rest;
FOR i: NAT DECREASING IN [0..count-1) DO
name.comps[i] ¬ l.first;
l ¬ l.rest
ENDLOOP;
}
ELSE {
FOR i: NAT IN [0..count-1) DO
name.comps[i] ¬ l.first;
l ¬ l.rest
ENDLOOP;
name.lastComp ¬ l.first;
};
We don't want a 1-component name to inadvertantly look like a 0-component name.
IF name.lastComp.name.base=NIL THEN name.lastComp.name ¬ ["", 0, 0];
};
};
Operations Within the Algebra of Names
ExpandName: PUBLIC PROC [name: PATH, wDir: PATH ¬ NIL] RETURNS [PATH] ~ {
If name is not absolute then prepends wDir.
name ¬ LocalNonNIL[name];
wDir ¬ LocalNonNIL[wDir];
IF name.absolute OR NOT wDir.absolute THEN RETURN[name];
{
privateName: REF PrivatePathObject ¬ name­;
answer: PATH ¬ NEW[PathObject ¬ [NEW[PrivatePathObject ¬ privateName­]]];
answer.absolute ¬ TRUE;
[answer.comps, answer.lastComp] ¬ AdjoinComps[wDir, 0, Count[wDir], name, 0, Count[name]];
RETURN[answer];
};
};
ComponentCount: PUBLIC PROC [name: PATH] RETURNS [count: NAT] ~ {
IF name=NIL THEN RETURN[0];
count ¬ IF name.comps # NIL THEN name.comps.count+1
ELSE IF (name.lastComp.name.base#NIL) OR (name.lastComp.version.versionKind#none) -- OR
-- name.absolute OR
-- name.directory
THEN 1 ELSE 0;
};
emptyComps: Components ~ NEW[ComponentSequence[0]];
Compare: PUBLIC PROC [n1, n2: PATH, case: BOOL ¬ FALSE ] RETURNS [Comparison] ~ {
c: Comparison;
CompareBools: PROC [b1, b2: BOOL] RETURNS [Comparison] ~ {
SELECT TRUE FROM
~b1 AND b2 => RETURN[less];
b1 AND ~b2 => RETURN[greater];
ENDCASE => NULL;
RETURN[equal];
};
n1 ¬ LocalNonNIL[n1];
n2 ¬ LocalNonNIL[n2];
IF (c ¬ CompareBools[n1.absolute, n2.absolute]) # equal THEN RETURN[c];
{
comps1: Components ~ IF n1.comps # NIL THEN n1.comps ELSE emptyComps;
comps2: Components ~ IF n2.comps # NIL THEN n2.comps ELSE emptyComps;
c1: NAT ¬ comps1.count;
c2: NAT ¬ comps2.count;
FOR p: NAT IN [0..MIN[c1, c2]) DO
IF (c ¬ CompareComponents[comps1[p], comps2[p], case]) # equal THEN RETURN[c];
ENDLOOP;
SELECT TRUE FROM
c1 < c2 => {
IF (c ¬ CompareComponents[n1.lastComp, comps2[c1], case]) # equal
THEN RETURN[c] ELSE RETURN[less];
};
c1 > c2 => {
IF (c ¬ CompareComponents[comps1[c2], n2.lastComp, case]) # equal
THEN RETURN[c] ELSE RETURN[greater];
};
ENDCASE => NULL;
};
Assert (comps1.count=comps2.count)
IF (c ¬ CompareComponents[n1.lastComp, n2.lastComp, case]) # equal THEN RETURN[c];
RETURN[CompareBools[n1.directory, n2.directory]];
};
ShortName: PUBLIC PROC [name: PATH] RETURNS [shortName: Component] ~
{ RETURN[LocalNonNIL[name].lastComp] };
ShortNameRope: PUBLIC PROC [name: PATH] RETURNS [shortName: ROPE] ~
{ RETURN[InlineComponentRope[LocalNonNIL[name].lastComp]] };
InlineComponentRope: PROC [comp: Component] RETURNS [ROPE] ~ INLINE {
RETURN [Rope.Substr[comp.name.base, comp.name.start, comp.name.len]];
};
Cat: PUBLIC PROC [n1, n2: PATH] RETURNS [PATH] ~ {
seq: Components;
lastComp: Component;
absolute, directory: BOOL;
n1 ¬ LocalNonNIL[n1];
n2 ¬ LocalNonNIL[n2];
[seq, lastComp] ¬ AdjoinComps[p1~n1, p2~n2];
absolute ¬ n1.absolute OR (Count[n1]=0 AND n2.absolute);
directory ¬ n2.directory OR (Count[n2]=0 AND n1.directory);
RETURN[NEW[PathObject ¬ [NEW[PrivatePathObject ¬ [absolute~absolute, directory~directory, lastComp~lastComp, comps~seq, parent~IF Count[n2]=1 THEN EnsureDirectory[n1] ELSE NIL]]]]];
};
SubName: PUBLIC PROC [name: PATH, start: NAT ¬ 0, count: NAT ¬ NAT.LAST, absolute, directory: BOOL ¬ FALSE] RETURNS [PATH] ~ {
result: PATH ¬ NEW[PathObject ¬ [NEW[PrivatePathObject]]];
name ¬ LocalNonNIL[name];
count ¬ MIN[count, Count[name]-start];
result.absolute ¬ absolute;
result.directory ¬ directory;
SELECT count FROM
0 => {
result.directory ¬ result.absolute ¬ absolute OR directory;
RETURN[result];
};
1 => {
result.lastComp ¬ Fetch[name, start];
We don't want a 1-component name to inadvertantly look like a 0-component name.
IF result.lastComp.name.base=NIL THEN result.lastComp.name ¬ ["", 0, 0];
RETURN[result];
};
ENDCASE => result.comps ¬ NEW[ComponentSequence[count-1]];
FOR i: NAT IN [0..count-1) DO
result.comps[i] ¬ Fetch[name, start+i];
ENDLOOP;
result.lastComp ¬ Fetch[name, start+count-1];
RETURN[result];
};
Fetch: PUBLIC PROC [name: PATH, index: NAT] RETURNS [Component] ~ {
c: NAT;
name ¬ LocalNonNIL[name];
[] ¬ Basics.BoundsCheck[index, c¬Count[name]];
IF (c-1)=index THEN RETURN[name.lastComp] ELSE RETURN[name.comps[index]];
};
IsAPrefix: PUBLIC PROC [prefix, name: PATH] RETURNS [isa: BOOL, suffix: PATH] ~ {
prefix ¬ LocalNonNIL[prefix];
name ¬ LocalNonNIL[name];
{
pComps: NAT ¬ Count[prefix];
nComps: NAT ¬ Count[name];
IF pComps=0 AND ~prefix.absolute THEN {
a relative, empty name is a prefix of anything.
RETURN[TRUE, name];
};
IF (pComps >= nComps) OR (prefix.absolute#name.absolute) THEN {
prefix too long, or unmatched absoluteness.
some doubt about whether excluding equal lengths is useful.
RETURN[FALSE, NIL];
};
FOR i: NAT IN [0.. pComps-1) DO
IF NOT EqualComponents[name.comps[i], prefix.comps[i]] THEN RETURN[FALSE, NIL];
ENDLOOP;
IF (pComps>0) AND NOT EqualComponents[prefix.lastComp, name.comps[pComps-1]] THEN RETURN[FALSE, NIL];
Now compute the suffix
suffix ¬ NEW[PathObject ¬ [NEW[PrivatePathObject ¬ []]]];
[suffix.comps, suffix.lastComp] ¬ AdjoinComps[name, pComps, nComps-pComps, EmptyPath, 0,0];
suffix.absolute ¬ NOT prefix.directory;
suffix.directory ¬ name.directory;
RETURN[TRUE, suffix];
};
};
Count: PROC [name: PATH] RETURNS [count: NAT] ~ INLINE {
count ¬ ComponentCount[name];
};
Error: ERROR ~ CODE;
IsADirectory: PUBLIC PROC [name: PATH] RETURNS [BOOL] ~ {
name ¬ LocalNonNIL[name];
RETURN[name.directory]
};
EnsureDirectory: PUBLIC PROC [name: PATH] RETURNS [PATH] ~ {
name ¬ LocalNonNIL[name];
IF name.directory THEN RETURN[name];
{
answer: PATH ¬ CopyPath[name];
answer.directory ¬ TRUE;
answer.unparsed ¬ NIL;
RETURN[answer];
};
};
IsAbsolute: PUBLIC PROC [name: PATH] RETURNS [BOOL] ~ {
name ¬ LocalNonNIL[name];
RETURN[name.absolute]
};
EnsureAbsolute: PUBLIC PROC [name: PATH] RETURNS [PATH] ~ {
name ¬ LocalNonNIL[name];
IF name.absolute THEN RETURN[name];
{
answer: PATH ¬ CopyPath[name];
answer.absolute ¬ TRUE;
answer.unparsed ¬ NIL;
RETURN[answer];
};
};
StripVersionNumber: PUBLIC PROC [name: PATH] RETURNS [PATH] ~ {
returns name with [none[]] substituted for name.version.
name ¬ LocalNonNIL[name];
RETURN[NEW[PathObject ¬ [NEW[PrivatePathObject ¬ [name.comps, [name.lastComp.name, [none]], name.absolute, name.directory, NIL, name.parent]]]]];
};
SetVersionNumber: PUBLIC PROC [name: PATH, version: Version] RETURNS [PATH] ~ {
returns name with version substituted for name.version.
name ¬ LocalNonNIL[name];
RETURN[NEW[PathObject ¬ [NEW[PrivatePathObject ¬ [name.comps, [name.lastComp.name, version], name.absolute, name.directory, NIL, name.parent]]]]];
};
ReplaceShortName: PUBLIC PROC [name: PATH, newShortName: Component] RETURNS [PATH] ~ {
name ¬ LocalNonNIL[name];
RETURN[NEW[PathObject ¬ [NEW[PrivatePathObject ¬ [name.comps, newShortName, name.absolute, name.directory, NIL, name.parent]]]]];
};
ReplaceComponent: PUBLIC PROC [name: PATH, index: NAT, new: Component] RETURNS [PATH] ~ {
c: NAT;
name ¬ LocalNonNIL[name];
[] ¬ Basics.BoundsCheck[index, c¬Count[name]];
IF new.name.base=NIL THEN new.name.base ¬ ""; -- must not convert 1 component name to 0 component name;
IF (c-1)=index THEN RETURN[NEW[PathObject ¬ [NEW[PrivatePathObject ¬ [name.comps, new, name.absolute, name.directory, NIL, name.parent]]]]]
ELSE {
assert: name.comps#NIL
newPath: PATH ¬ NEW[PathObject ¬ [NEW[PrivatePathObject ¬ [NIL, name.lastComp, name.absolute, name.directory]]]];
newPath.comps ¬ NEW[ComponentSequence[name.comps.count]];
FOR i: NAT IN [0..name.comps.count) DO
newPath.comps[i] ¬ name.comps[i];
ENDLOOP;
newPath.comps[index] ¬ new;
RETURN[ newPath ];
};
};
InASubdirectory: PUBLIC PROC [parent: PATH, name: PATH] RETURNS [BOOL] ~ {
This implementation could be more efficient; it's not necessary to construct the suffix and Directory[suffix]
isa: BOOL;
suffix: PATH;
name ¬ LocalNonNIL[name];
parent ¬ LocalNonNIL[parent];
[isa, suffix] ¬ IsAPrefix[parent, name];
RETURN[isa AND Count[Directory[suffix]]#0];
};
FirstSubdirectory: PUBLIC PROC [parent: PATH, name: PATH] RETURNS [PATH] ~ {
If NOT InASubdirectory[parent, name] then returns NIL. Otherwise, returns the part of name up to and including the first subdirectory after the end of parent.
isa: BOOL;
suffix: PATH;
parent ¬ LocalNonNIL[parent];
name ¬ LocalNonNIL[name];
[isa, suffix] ¬ IsAPrefix[parent, name];
IF ~isa OR Count[Directory[suffix]]=0 THEN RETURN[NIL];
{
answer: PATH ¬ CopyPath[parent];
answer.unparsed ¬ NIL;
answer.parent ¬ NIL;
[answer.comps, answer.lastComp] ¬ AdjoinComps[name, 0, Count[parent]+1, EmptyPath, 0, 0];
RETURN[answer];
};
};
Directory: PUBLIC PROC [name: PATH] RETURNS [PATH] ~ {
Return the directory part of the name.
IF (name ¬ LocalNonNIL[name]).directory THEN RETURN[name];
RETURN[Parent[name]];
};
parentCalls: CARD ¬ 0;
parentsNotCached: CARD ¬ 0;
ParentCalls: PROC RETURNS [CARD] ~ { RETURN[parentCalls] };
ParentsNotCached: PROC RETURNS [CARD] ~ { RETURN[parentsNotCached] };
Parent: PUBLIC PROC [name: PATH] RETURNS [PATH] ~ {
If name is a directory, then returns the parent directory. If name is a file, then returns the containing directory. In either case, this means that Parent returns the directory which contains the object denoted by name.
nonNil: PATH ~ LocalNonNIL[name];
parentCalls ¬ parentCalls+1;
IF nonNil.parent#NIL THEN RETURN[nonNil.parent]
ELSE {
answer: PATH ¬ CopyPath[nonNil];
answer.unparsed ¬ NIL;
answer.parent ¬ NIL;
parentsNotCached ¬ parentsNotCached+1;
IF Count[answer]=0 AND ~answer.absolute THEN Error[];
[answer.comps, answer.lastComp] ¬ AdjoinComps[answer, 0, MAX[INTEGER[Count[answer]-1], 0], EmptyPath, 0, 0];
answer.directory ¬ TRUE;
IF name#NIL THEN name.parent ¬ answer;
RETURN[answer];
};
};
ConstructComponent: PUBLIC PROC [name: ComponentNamePart, version: Version ¬ [none]]
RETURNS [Component] ~
{ RETURN[ [name: name, version: version] ] };
VersionToRope: PUBLIC PROC [v: Version] RETURNS [ROPE] ~
{ RETURN[PFS.RopeFromPath[ConstructName[LIST[[name: [NIL, 0, 0] , version: v]], FALSE, FALSE]] ] };
Replace: PUBLIC PROC [base: PATH, start: INT ¬ 0, len: NAT ¬ NAT.LAST, with: PATH]
RETURNS [PATH] ~ {
bl: INT ~ base.ComponentCount[];
wl: INT ~ with.ComponentCount[];
len ¬ MIN[len, bl-start];
IF start=0 AND len=bl THEN RETURN [with];
IF len=0 AND wl=0 THEN RETURN [base];
{
cl: LIST OF Component ¬ NIL;
FOR i: INT IN [0..start) DO cl ¬ CONS[base.Fetch[i], cl] ENDLOOP;
FOR i: INT IN [0..wl) DO cl ¬ CONS[with.Fetch[i], cl] ENDLOOP;
FOR i: INT IN [start+len..bl) DO cl ¬ CONS[base.Fetch[i], cl] ENDLOOP;
RETURN [ConstructName[components: cl, absolute: base.IsAbsolute[], directory: base.IsADirectory, reverse: TRUE] ]
};
};
Map: PUBLIC PROC [name: PATH, componentProc: ComponentProc, separatorProc: SeparatorProc, ref: REF] ~ {
name ¬ LocalNonNIL[name];
{
c: NAT ¬ Count[name];
separatorProc[name.absolute, ref];
IF c=0 THEN RETURN;
FOR i: NAT IN [0..c-1) DO
componentProc[Fetch[name, i], ref];
separatorProc[TRUE, ref];
ENDLOOP;
componentProc[Fetch[name, c-1], ref];
separatorProc[name.directory, ref];
};
};
Operations on Components
CompareComponents: PUBLIC PROC [c1, c2: Component, case: BOOL] RETURNS [Comparison] ~ {
SELECT Rope.CompareSubstrs[
c1.name.base, c1.name.start, c1.name.len,
c2.name.base, c2.name.start, c2.name.len, case] FROM
less => RETURN[less];
greater => RETURN[greater];
ENDCASE => NULL;
RETURN[CompareVersions[c1.version, c2.version]];
};
Operations on Versions
CompareVersions: PUBLIC PROC [v1, v2: Version] RETURNS [Comparison] ~ {
IF v1.versionKind#v2.versionKind THEN RETURN[incomparable];
IF v1.versionKind#numeric THEN RETURN[equal];
SELECT TRUE FROM
v1.version<v2.version => RETURN[less];
v1.version>v2.version => RETURN[greater];
ENDCASE => RETURN[equal];
};
Unparsing Hint
GetUnparsingHint: PUBLIC PROC [p: PATH] RETURNS [REF] ~ {
RETURN [p.unparsed];
};
SetUnparsingHint: PUBLIC PROC [p: PATH, r: REF] RETURNS [prev: REF] ~ {
prev ¬ p.unparsed;
p.unparsed ¬ r;
};
Helpers
EmptyPath: PUBLIC PATH ~ NEW[PathObject ¬ [NEW[PrivatePathObject]]];
LocalNonNIL: PROC [p: PATH] RETURNS [PATH] ~ INLINE {
RETURN[IF p=NIL THEN EmptyPath ELSE p];
};
This is also in the interface, but this is better for use in the Impl because it doesn't indirect through the interface record to get to the EmptyPath.
CopyPath: PROC [path: PATH] RETURNS [PATH] ~ {
caller must ensure path is non-NIL;
privatePath: REF PrivatePathObject ~ path­;
RETURN[ NEW[PathObject ¬ [NEW[PrivatePathObject ¬ privatePath­]]] ];
};
AdjoinComps: PROC [
p1: PATH, s1: NAT ¬ 0, c1: NAT ¬ LAST[NAT],
p2: PATH ¬ NIL, s2: NAT ¬ 0, c2: NAT ¬ LAST[NAT] ]
RETURNS [seq: Components ¬ NIL, lastComp: Component ¬ [] ] ~ {
Combined Substring and Cat; avoids the allocations one would do to do them separately.
caller must assure that p1 and p2 are non-NIL
count1: NAT ¬ Count[p1];
count2: NAT ¬ Count[p2];
c1 ¬ MIN[c1, count1-s1];
c2 ¬ MIN[c2, count2-s2];
{
CopyComps: PROC [from: PATH, fromStart, count: NAT, to: Components, toStart: NAT] ~ {
j: NAT ¬ fromStart;
FOR i: NAT IN [toStart..MIN[toStart+count, to.count]) DO
to[i] ¬ Fetch[from, j];
j ¬ j+1;
ENDLOOP;
};
newCount: NAT ¬ c1+c2;
SELECT newCount FROM
0 => { RETURN };
1 => { NULL };
NAT.LAST => { ERROR }; -- maybe?
ENDCASE => seq ¬ NEW[ComponentSequence[newCount-1]];
assert: c2 > 0 OR c1 > 0
lastComp ¬ IF c2 > 0 THEN Fetch[p2, s2+c2-1] ELSE Fetch[p1, s1+c1-1];
IF seq = NIL THEN RETURN;
CopyComps[from: p1, fromStart: s1, count: c1, to: seq, toStart: 0];
CopyComps[from: p2, fromStart: s2, count: c2, to: seq, toStart: c1];
};
};
END.