DIRECTORY 
CD, CDBasics, CDCells, CDDirectory, CDInstances, CDPinObjects, CDProperties, CDRects, CDTexts, Core, CoreClasses, CoreCompose, CoreOps, CoreProperties, PWPins, RefTab, Rope, SEX, SymTab, PWObjects;

SEXImpl: CEDAR PROGRAM
IMPORTS CDBasics, CDCells, CDInstances, CDPinObjects, CDProperties, CDRects, CoreClasses, CoreCompose, CoreOps, CoreProperties, PWPins, RefTab, Rope, SEX
EXPORTS SEX
SHARES CDDirectory, CDRects, CDPinObjects = 
BEGIN OPEN SEX;
extractObjProcProp: PUBLIC ATOM _ $ExtractObjProcProp;
ExtractInst: PUBLIC ExtractInstProc = {
refProc: REF ExtractInstProc _ NARROW [CDProperties.GetPropFromInstance[inst, extractObjProcProp]];
IF refProc=NIL THEN refProc _ NARROW [CDProperties.GetPropFromObject[inst.ob, extractObjProcProp]];
IF refProc=NIL THEN refProc _ NARROW [CDProperties.GetProp[inst.ob.class, extractObjProcProp]];
[cellType, ] _ IF refProc#NIL THEN refProc^[inst, context] ELSE DefaultExtractInst[inst, context];
};
DefaultExtractInst: ExtractInstProc = {
};
ExtractCell: ExtractInstProc = {
cellPtr: CD.CellPtr _ NARROW[inst.ob.specificRef];
cdInsts, subCells: CD.InstanceList;
public, internal: Wire;
wires, publics, internals: LIST OF Wire;
data: CoreClasses.RecordCellType;
cdInsts _ cellPtr.contents;

[wires, subCells] _ ConnectivitySearch[cdInsts];
[internals, publics] _ MakeWires[wires, subCells, context];

FinishWires[wires, subCells, context, internals, publics];
internal _ CoreOps.CreateRecordWire[components: internals];
public _ CoreOps.CreateRecordWire[components: publics];
data _ NEW[CoreClasses.RecordCellTypeRec _ [
internal: internal,
instances: MakeInstances[subCells, context]]];
cellType _ NEW[Core.CellTypeRec _ [
name: cellPtr.name,
class: CoreClasses.recordCellClass,
public: public,
data: data]];
};
ConnectivitySearch: PROC [cdInsts: CD.InstanceList] RETURNS [wires: LIST OF Wire, subCells: CD.InstanceList _ NIL] = {
CreateListOfWiresProc: RefTab.EachPairAction = {
IF ISTYPE[val, Wire] THEN wires _ CONS[NARROW[val], wires];
quit _ FALSE;
};
connectTab: RefTab.Ref _ RefTab.Create[];	-- [key: CD.Instance, val: some instance connected to it]
FOR l: CD.InstanceList _ cdInsts, l.rest WHILE l#NIL DO
inst: CD.Instance _ l.first;
wire: Wire _ NEW[Core.WireRec];
IF ~IsCell[inst] THEN -- first, every wire or pin is its own root
[] _ RefTab.Store[connectTab, inst, wire];
SELECT TRUE FROM
IsPin[inst] => {
AddPinPropOnWire[wire, inst];
AddWireGeometryPropOnWire[wire, inst];
};
IsRectangle[inst] => {
AddWireGeometryPropOnWire[wire, inst];
};
IsCell[inst] => {		-- add the pins of the cell as geometry only
cell: CD.Instance _ inst;	-- to avoid name conflict
EachPin: PWPins.InstanceEnumerator = {
AddWireGeometryPropOnWire[wire, PWPins.TransformInstance[inst, cell.ob.size, cell.location, cell.orientation]];
};
[] _ PWPins.EnumerateEdgePins[cell.ob, EachPin];
subCells _ CONS[cell, subCells];
};
ENDCASE => ERROR;	-- what could inst be?
ENDLOOP;
FOR l1: CD.InstanceList _ cdInsts, l1.rest WHILE l1#NIL DO
inst1: CD.Instance _ l1.first;
FOR l2: CD.InstanceList _ l1.rest, l2.rest WHILE l2#NIL DO
inst2: CD.Instance _ l2.first;
IF Touch[inst1, inst2] THEN {
root1: CD.Instance _ Root[connectTab, inst1];
root2: CD.Instance _ Root[connectTab, inst2];
wire1: Wire _ RootWire[connectTab, inst1];
wire2: Wire _ RootWire[connectTab, inst2];
MergeWireInfo[wire1, wire2];
[] _ RefTab.Store[connectTab, root2, root1];	-- both now point to wire1
};
ENDLOOP;
ENDLOOP;

[] _ RefTab.Pairs[connectTab, CreateListOfWiresProc];
};
MakeWires: PROC [wires: LIST OF Wire, subCells: CD.InstanceList, context: Context] RETURNS [publics, internals: LIST OF Wire] = {
def, use: ROPE; outPins, inPins: CD.InstanceList;
FOR l: LIST OF Wire _ wires, l.rest WHILE l#NIL DO
wire: Wire _ l.first;
newWire: Wire;
[def, use, outPins, inPins] _ InfoOnWire[wire, context];
IF Rope.Equal[def, NIL] OR ~Rope.Equal[use, NIL] THEN RETURN;  -- for pass 2
IF ~Rope.Equal[def, NIL] AND ~Rope.Equal[use, NIL] THEN ERROR;   -- et alors? 
newWire _ CoreCompose.CreateWires[context, def];	-- hope it works for def=""
internals _ CONS[newWire, internals];
IF outPins#NIL THEN publics _ CONS[newWire, publics];
IF inPins#NIL THEN AttachWireAsActualOnEachInPin[newWire, inPins];
wire _ NIL;		-- somehow, I have to take it out for pass 2
ENDLOOP;
};
FinishWires: PROC [wires: LIST OF Wire, subCells: CD.InstanceList, context: Context, publics, internals: LIST OF Wire] = {
def, use: ROPE; outPins, inPins: CD.InstanceList;
FOR l: LIST OF Wire _ wires, l.rest WHILE l#NIL DO
wire: Wire _ l.first;
subWire: Wire;
[def, use, outPins, inPins] _ InfoOnWire[wire, context];
IF outPins=NIL AND inPins=NIL THEN ERROR;   
-- There is a use for sure
subWire _ FindSubWire[internals];	-- use CoreCompose
IF outPins#NIL THEN publics _ CONS[subWire, publics];
IF inPins#NIL THEN AttachWireAsActualOnEachInPin[subWire, inPins];
ENDLOOP;
};
MakeInstances: PROC [subCells: CD.InstanceList, context: Context] RETURNS [instances: CoreClasses.CellInstanceList] = {
FOR l: CD.InstanceList _ subCells, l.rest WHILE l#NIL DO
instances _ CONS[MakeInstance[l.first, context], instances];
ENDLOOP;
};
MakeInstance: PROC [cell: CD.Instance, context: Context] RETURNS [instance: CoreClasses.CellInstance]= {
};
AttachWireAsActualOnEachInPin: PROC [wire: Wire, inPins: CD.InstanceList] = {
};
FindSubWire: PROC [wires: LIST OF Wire] RETURNS [wire: Wire] = {
};
InfoOnWire: PROC [wire: Wire, context: Context] RETURNS [def, use: ROPE, outPins, inPins: CD.InstanceList] = {
outPins _ GetPinPropFromWire[wire];
};
MergeWireInfo: PROC [winner, looser: Wire] = {
AppendPinPropOnWire[winner, GetPinPropFromWire[looser]];
AppendWireGeometryPropOnWire[winner, GetWireGeometryPropFromWire[looser]];
};
Up: PROC [table: RefTab.Ref, ref: REF] RETURNS [up: REF _ NIL] = {
up _ RefTab.Fetch[table, ref].val};
RootWire: PROC [table: RefTab.Ref, inst: CD.Instance] RETURNS [wire: Wire] = {
wire _ NARROW[Up[table, Root[table, inst]]];
};
Root: PROC [table: RefTab.Ref, inst: CD.Instance] RETURNS [root: CD.Instance] = {
ref: REF _ inst;
up: REF _ Up[table, ref];
WHILE ~ISTYPE[up, Wire] DO ref _ up; up _ Up[table, ref]; ENDLOOP;
root _ NARROW[ref];
};
GetPinPropFromWire: PUBLIC PROC [wire: Wire] RETURNS [pins: LIST OF CD.Instance] = {
pins _ NARROW [CoreProperties.GetWireProp[wire, pinsProp]];
};
PutPinPropOnWire: PUBLIC PROC [wire: Wire, pins: LIST OF CD.Instance] = {
CoreProperties.PutWireProp[wire, pinsProp, pins];
};
AddPinPropOnWire: PUBLIC PROC [wire: Wire, pin: CD.Instance] = {
pins: LIST OF CD.Instance _ CONS [pin, NARROW [CoreProperties.GetWireProp[wire, pinsProp]]];
CoreProperties.PutWireProp[wire, pinsProp, pins];
};
AppendPinPropOnWire: PUBLIC PROC [wire: Wire, pins: LIST OF CD.Instance] = {
WHILE pins#NIL DO 
AddWireGeometryPropOnWire[wire, pins.first]; 
pins _ pins.rest;
ENDLOOP;
};

GetWireGeometryPropFromWire: PUBLIC PROC [wire: Wire] RETURNS [geometry: LIST OF CD.Instance] = {
geometry _ NARROW [CoreProperties.GetWireProp[wire, wireGeometryProp]];
};
PutWireGeometryPropOnWire: PUBLIC PROC [wire: Wire, geometry: LIST OF CD.Instance] = {
CoreProperties.PutWireProp[wire, wireGeometryProp, geometry];
};
AddWireGeometryPropOnWire: PUBLIC PROC [wire: Wire, cdInstance: CD.Instance] = {
PutWireGeometryPropOnWire[wire, CONS [cdInstance, GetWireGeometryPropFromWire[wire]]];
};
AppendWireGeometryPropOnWire: PUBLIC PROC [wire: Wire, geometry: LIST OF CD.Instance] = {
WHILE geometry#NIL DO 
AddWireGeometryPropOnWire[wire, geometry.first]; 
geometry _ geometry.rest;
ENDLOOP;
};
IsRectangle: PROC [inst: CD.Instance] RETURNS [BOOL] = {
RETURN[inst.ob.class=CDRects.bareRectClass]};
IsPin: PROC [inst: CD.Instance] RETURNS [BOOL] = {
RETURN[inst.ob.class=CDPinObjects.pinObjectsClass]};
IsCell: PROC [inst: CD.Instance] RETURNS [BOOL] = {
RETURN[CDCells.IsCell[inst.ob]]};

Touch: PROC [inst1, inst2: CD.Instance] RETURNS [touch: BOOL _ FALSE] = {
IF IsRectangle[inst1] AND IsRectangle[inst2] THEN 
RETURN[TouchWires[InstToRect[inst1], InstToRect[inst2]]]
ELSE touch _ TouchListsRect[InstToRects[inst1], InstToRects[inst2]];
};
TouchWires: PROC [rect1, rect2: CD.Rect] RETURNS [BOOL _ FALSE] = {
IF ~CDBasics.Intersect[rect1, rect2] THEN RETURN[FALSE];
};
InstToRects: PROC [inst: CD.Instance] RETURNS [listRect: LIST OF CD.Rect _ NIL] = {
SELECT TRUE FROM
IsRectangle[inst] OR IsPin[inst] => listRect _ CONS[InstToRect[inst]];
IsCell[inst] => {	-- enumerate pins, turn into rects and CONS them
cell: CD.Instance _ inst;	-- to avoid name conflict
EachPin: PWPins.InstanceEnumerator = {
pinRect: CD.Rect _ InstToRect[PWPins.TransformInstance[inst, cell.ob.size, cell.location, cell.orientation]];
listRect _ CONS[pinRect, listRect];
};
[] _ PWPins.EnumerateEdgePins[cell.ob, EachPin];
listRect _ NIL};
ENDCASE => ERROR;
};
TouchListsRect: PROC [listRect1, listRect2: LIST OF CD.Rect] RETURNS [BOOL _ FALSE] = {
FOR l1: LIST OF CD.Rect _ listRect1, l1.rest WHILE l1#NIL DO
rect1: CD.Rect _ l1.first;
FOR l2: LIST OF CD.Rect _ listRect2, l2.rest WHILE l2#NIL DO
IF TouchRects[rect1, l2.first] THEN RETURN[TRUE];
ENDLOOP;
ENDLOOP;
};
TouchRects: PROC [rect1, rect2: CD.Rect] RETURNS [BOOL _ FALSE] = {
RETURN[CDBasics.Intersect[rect1, rect2]];
};
InstToRect: PROC [inst: CD.Instance] RETURNS [rect: CD.Rect] = {
rect _ CDInstances.InstRectI[inst]};

ParseSatellites: PROC [master: CD.Instance, context: Context] = {
ref: REF _ CDProperties.GetPropFromInstance[master, satellitesProp];
IF ref=NIL THEN RETURN;
FOR l: CD.InstanceList _ NARROW[ref], l.rest WHILE l#NIL DO
ENDLOOP;
};
[] _ CDProperties.RegisterProperty[extractObjProcProp, sexKey];

END.

SEXImpl.mesa
Copyright c 1985 by Xerox Corporation.  All rights reversed.
Louis Monier November 3, 1985 2:07:05 am PST

Properties
Extraction Procedures
-- Look for an extract proc on the instance, then the object, then the class

-- Pass 0: Produces a RefTab.Ref binding every instance to a wire, a list of wires, and a list of subCells; not clear we need the table anymore!
-- On the wire are found pins and all the geometry composing it

-- Pass 1: create internal wires, def or implicit, and put actuals as props on the internal pins of the subcells
-- Pass 2: treat the wires only used (parts of already defined wires)

-- Pass 3: now all wires exist, and all pins of internal cells are decorated with actuals
-- Create instances

-- Pass 0
-- Brute force! The table associates with each instance a ref: this ref is either another entry in the table (CD.Instance), or a Wire if this instance is a root

-- Take a look at all instances, create a wire and decorate it with pins and geometry

-- Now the O(n2) part
-- Now make a list of all wires

-- Pass 1
-- A wire is a set of rectangles and pins connected together; its name and structure can be defined (once) by a satellite of the form "def: foo", where "def" is reserved;
-- An undefined wire is atomic unnamed.
-- Create Internal

-- Pass 2
-- Now using exisiting wires for making actuals
-- Recursive call to get the cellType of subcells
-- The val in the table; NIL if not found
-- The root, i.e. the last Up[Up[...[inst]...]] whose val is a wire
Operations for an easy management of properties
Geometrical Primitives
-- Special rule for two rectangles because crossing implies no contact
IF TouchOnlyOnCorner[rect1, rect2] THEN RETURN[TRUE];
-- The list of rectangles defining the contact points for this instance
-- This rule does not apply for the intersection of two wires
-- The rectangle corresponding to this instance
Satellites
-- Turn the satellites into properties and put them in the context
ParseSatellite[l.first, context];
TextToPropLit: PROC [sat: CD.Instance, context: Context] RETURNS [prop: CoreCompose.PropertyLiteral]= {
text: ROPE _ NARROW[sat.ob.specificRef, CDTexts.TextPtr].text;
prop _ NIL;
};
Initialization
CDProperties.PutProp[CDPinObjects.pinObjectsClass, extractObjProcProp, NEW [ExtractObjProc _ PinExtractObj]];
CDProperties.PutProp[CDCells.cellClass, extractObjProcProp, NEW [ExtractObjProc _ CellExtractObj]];
CDProperties.PutProp[PWObjects.abutXClass, extractObjProcProp, NEW [ExtractObjProc _ AbutExtractObj]];
CDProperties.PutProp[PWObjects.abutYClass, extractObjProcProp, NEW [ExtractObjProc _ AbutExtractObj]];
CDProperties.PutProp[PWObjects.indirectClass, extractObjProcProp, NEW [ExtractObjProc _ PWCoreOperatorExtractObj]];
CDProperties.PutProp[PWCore.gateWayClass, extractObjProcProp, NEW [ExtractObjProc _ PWCoreOperatorExtractObj]];
ส
>˜
codeš
œ™Kšœ
ฯm
œ1™<K™,—K™šฯk	œ
˜
Kšžœฌ
žœ˜ล
—K˜•StartOfExpansion[]šฯnœžœ
ž˜Kšžœ
ž˜™
Kšžœ
ž˜Kšžœ&˜,Kšžœ
žœ
žœ
˜—
head™
Kšœžœ
žœ˜6—™šŸœžœ˜'J™LJšœ	žœžœ>˜cJšœžœ
žœžœ?˜cJšœžœ
žœžœ;˜_Jš	œžœ	žœ
žœžœ#˜bK˜—šŸœ˜'K˜—šŸœ˜ Kšœ	žœžœ˜2Kšœžœ˜#Kš
œ˜Kšœžœ
žœ˜(Kš
œ!˜!K™Kš
œ˜K˜Kš
ฯc
™
K™?Kš
œ0˜0K™K™pKš
œ;˜;K˜K™EKš
œ:˜:Kš
œ;˜;Kš
œ7˜7K™K™YK™šœžœ"˜,Kš
œ˜Kš
œ.˜.—šœžœ˜#Kš
œ˜Kš
œ#˜#Kš
œ˜Kš
œ
˜
—K˜—K™š
ฯx	™	Kš qœ '™ 
šŸœžœžœžœ	žœ
žœžœžœ˜všŸœ˜0Kš
žœ
žœžœ	žœ
žœ˜;Kšœžœ
˜
Kš
œ˜—Jšœ) :˜cK™K™Uš	žœžœ žœžœ
ž˜7Kšœžœ˜Kšœ
žœ˜šžœžœ
 +˜AKš
œ*˜*—šžœ
žœ
ž˜š
œ˜Kš
œ˜Kš
œ&˜&K˜—š
œ˜Kš
œ&˜&Kš
œ˜—šœ ,˜?J–4 -- [inst: CD.Instance] RETURNS [quit: BOOL _ FALSE]šœžœ ˜3šฯbœ˜&Jš
œo˜oJ˜—Jš
œ0˜0Jšœžœ˜ Kš
œ˜—Kšžœžœ ˜(—Kšžœ
˜—K™Kšœฯu
œ™š	žœžœ!žœžœ
ž˜:Kšœžœ˜š	žœžœ!žœžœ
ž˜:Kšœžœ˜šžœžœ˜Kšœžœ$˜-Kšœžœ$˜-Kš
œ*˜*Kš
œ*˜*Kš
œ˜Kšœ- ˜GK˜—Kšžœ
˜—Kšžœ
˜—K˜K™Kš
œ5˜5K˜——K™šกœ
™	K™ช
K™'šŸ	œžœ	žœ
žœžœ!žœžœ
žœ
˜
Kšœ
žœ
ž
œžœ˜1šžœžœ
žœžœžœ
ž˜2Kš
œ˜K˜Kš
œ8˜8Kš
žœžœžœžœžœ
žœ 
˜LKš
žœžœžœžœžœ
žœ 
˜NK™Kšœ1 ˜LKšœžœ˜%Kšžœ	žœ
žœžœ˜5Kšžœžœ
žœ0˜BKšœžœ ,˜9Kšžœ
˜—K˜——K™šกœ
™	K™/šŸœžœ	žœ
žœžœ5žœ
žœ
˜zKšœ
žœ
ž
œžœ˜1šžœžœ
žœžœžœ
ž˜2Kš
œ˜K˜Kš
œ8˜8Kšžœ	žœ
žœžœ
žœ
žœ˜,Jš
 ˜Kšœ" ˜4Kšžœ	žœ
žœžœ˜5Kšžœžœ
žœ0˜BKšžœ
˜—K˜——K™1šŸ
œžœžœ!žœ.˜wš	žœžœ!žœžœ
ž˜8Kšœžœ,˜<Kšžœ
˜—K˜—šŸœžœžœžœ(˜hK˜—šŸœžœžœ˜MK˜—š
Ÿœžœ	žœ
žœžœ˜@K˜—š
Ÿ
œžœ žœžœžœ˜nKš
œ#˜#K˜—šŸ
œžœ˜.Kš
œ8˜8Kš
œJ˜JK˜—K™)šŸœžœžœžœžœžœ˜BKš
œ#˜#—šŸœžœžœžœ˜NKšœžœ˜,K˜—Jš
œC™Cš
Ÿœžœžœžœžœ˜QJšœžœ˜Jšœžœ˜Kš
žœžœžœ	ž
œžœ
˜BJšœžœ˜J˜——™/šŸœžœ
žœžœžœ
žœ
žœ˜TJšœžœ.˜;J˜—šŸœžœ
žœžœ
žœ
žœ˜IJš
œ1˜1J˜—šŸœžœ
žœžœ˜@Jšœžœ
žœ
žœžœžœ/˜\Jš
œ1˜1J˜—šŸœžœ
žœžœ
žœ
žœ˜Lšžœžœ
žœ
˜Jš
œ-˜-Jš
œ˜Jšžœ
˜—J˜—J˜šŸœžœ
žœžœžœ
žœ
žœ˜aJšœžœ6˜GJ˜—šŸœžœ
žœžœ
žœ
žœ˜VJš
œ=˜=J˜—šŸœžœ
žœžœ˜PJšœ žœ2˜VJ˜—šŸœžœ
žœžœ
žœ
žœ˜Yšžœ
žœ
žœ
˜Jš
œ1˜1Jš
œ˜Jšžœ
˜—J˜——™š
Ÿœžœžœžœžœ˜8Kšžœ'˜-—š
Ÿœžœžœžœžœ˜2Kšžœ.˜4—š
Ÿœžœžœžœžœ˜3Kšžœ˜!—K˜šŸœžœžœžœ	žœžœ˜Išžœžœžœ
˜2Kšžœ2˜8—Kšžœ@˜DK˜—K™FšŸ
œžœžœžœžœžœ˜CKšžœ#žœ
žœ
žœ˜8Kšžœ!žœ
žœ
žœ™5K˜—K™GšŸœžœžœžœžœ
žœ
žœžœ˜Sšžœ
žœ
ž˜Kšœžœžœ˜Fšœ 0˜BJ–4 -- [inst: CD.Instance] RETURNS [quit: BOOL _ FALSE]šœžœ ˜3šขœ˜&Jšœ	žœb˜mJšœžœ˜#J˜—Jš
œ0˜0Kšœžœ˜—Kšžœžœ
˜—Kš
œ˜—šŸœžœžœ
žœ
žœžœžœžœ˜Wš
žœžœ
žœ
žœžœžœ
ž˜<Kšœžœ˜š
žœžœ
žœ
žœžœžœ
ž˜<Kšžœžœ
žœ
žœ˜1Kšžœ
˜—Kšžœ
˜—K˜—K™=šŸ
œžœžœžœžœžœ˜CJšžœ#˜)K˜—K™/š
Ÿ
œžœžœžœžœ
˜@Kš
œ$˜$K˜——™
K™BšŸœžœ
žœ ˜AKšœžœ<˜DKšžœžœ
žœ
žœ
˜šžœžœžœžœžœ
ž˜;Kš
œ!™!Kšžœ
˜—K˜—šŸ
œžœžœžœ'™gKšœžœžœ+™>Kšœžœ
™Kš
œ™——š
œ™Kš
œ?˜?KšœGžœ#™mKšœ<žœ$™cKšœ?žœ$™fKšœ?žœ$™fKšœBžœ.™sKšœ>žœ.™oK˜Kšžœ
˜K˜——…—%R=ฎ