-- DependenciesImpl.mesa
-- last edit July 13, 1984 1:18:59 pm PDT Sturgis
DIRECTORY
Dependencies USING[DependencySet, DependencySetBody, Action, ActionBody, DataItem, DataItemBody, ListCell, ListCellBody];
DependenciesImpl: PROGRAM EXPORTS Dependencies =
BEGIN OPEN Dependencies;
freeListCells: ListCell ← NIL;
debugging: BOOLEAN ← FALSE;
CreateDependencySet: PUBLIC PROCEDURE RETURNS[DependencySet] =
{RETURN[NEW[DependencySetBody ← [FALSE, NIL, NIL, FALSE, NIL, NIL]]]};
DefineAction: PUBLIC PROCEDURE[inSet: DependencySet, act: PROC[Action, REF ANY], actInfo: REF ANY] RETURNS[Action] =
BEGIN
action: Action ← NEW[ActionBody ← [
act: act,
info: actInfo,
dirty: FALSE,
dependentData: NIL,
firstDataList: NIL,
set: inSet,
sorting: FALSE,
sorted: FALSE,
isSource: FALSE,
prevUnsorted: NIL,
nextUnsorted: inSet.unSortedList,
prevSorted: NIL,
nextSorted: NIL]];
IF inSet.unSortedList # NIL THEN inSet.unSortedList.prevUnsorted ← action;
inSet.unSortedList ← action;
inSet.changed ← TRUE;
Verify[inSet];
RETURN[action];
END;
DefineDataItem: PUBLIC PROCEDURE[inSet: DependencySet] RETURNS[DataItem] =
BEGIN
dataItem: DataItem ← NEW[DataItemBody ← [
dirty: FALSE,
set: inSet,
nextItem: inSet.dataItems,
prevItem: NIL,
nextDirtyItem: NIL,
prevDirtyItem: NIL,
dependentActions: NIL,
firstActionList: NIL
]];
IF inSet.dataItems # NIL THEN inSet.dataItems.prevItem ← dataItem;
inSet.dataItems ← dataItem;
inSet.changed ← TRUE;
Verify[inSet];
RETURN[dataItem];
END;
NoteThatDataItemIsReadByAction: PUBLIC PROCEDURE[dataItem: DataItem, action: Action] =
BEGIN
cell: ListCell;
IF dataItem = NIL OR action = NIL THEN RETURN;
IF dataItem.set # action.set THEN MisMatchedDependencySets;
IF freeListCells # NIL THEN
{cell ← freeListCells; freeListCells ← cell.nextOnList}
ELSE cell ← NEW[ListCellBody];
cell↑ ← [
action: action,
dataItem: dataItem,
prevOnList: NIL,
nextOnList: dataItem.dependentActions,
prevList: NIL,
nextList: action.firstDataList
];
IF dataItem.dependentActions # NIL THEN dataItem.dependentActions.prevOnList ← cell;
dataItem.dependentActions ← cell;
IF action.firstDataList # NIL THEN action.firstDataList.prevList ← cell;
action.firstDataList ← cell;
dataItem.set.changed ← TRUE;
END;
NoteThatActionModifiesDataItem: PUBLIC PROCEDURE[action: Action, dataItem: DataItem] =
BEGIN
cell: ListCell;
IF dataItem = NIL OR action = NIL THEN RETURN;
IF dataItem.set # action.set THEN MisMatchedDependencySets;
IF freeListCells # NIL THEN
{cell ← freeListCells; freeListCells ← cell.nextOnList}
ELSE cell ← NEW[ListCellBody];
cell↑ ← [
action: action,
dataItem: dataItem,
prevOnList: NIL,
nextOnList: action.dependentData,
prevList: NIL,
nextList: dataItem.firstActionList
];
IF action.dependentData # NIL THEN action.dependentData.prevOnList ← cell;
action.dependentData ← cell;
IF dataItem.firstActionList # NIL THEN dataItem.firstActionList.prevList ← cell;
dataItem.firstActionList ← cell;
action.set.changed ← TRUE;
Verify[action.set];
END;
DeactivateAction: PUBLIC PROCEDURE[action: Action] =
BEGIN
set: DependencySet;
nextCell: ListCell ← NIL;
IF action = NIL THEN RETURN;
set ← action.set;
-- remove the action from the set lists
IF set.sortedList = action THEN set.sortedList ← action.nextSorted;
IF action.prevSorted # NIL THEN action.prevSorted.nextSorted ← action.nextSorted;
IF action.nextSorted # NIL THEN action.nextSorted.prevSorted ← action.prevSorted;
IF (set.unSortedList = action) # (action.prevUnsorted = NIL) THEN ERROR;
IF set.unSortedList = action THEN set.unSortedList ← action.nextUnsorted;
IF action.prevUnsorted # NIL THEN action.prevUnsorted.nextUnsorted ← action.nextUnsorted;
IF action.nextUnsorted # NIL THEN action.nextUnsorted.prevUnsorted ← action.prevUnsorted;
-- now remove the action from all dependent lists hanging off of data items
FOR cell: ListCell ← action.firstDataList, nextCell WHILE cell # NIL DO
nextCell ← cell.nextList;
IF cell.prevOnList = NIL THEN cell.dataItem.dependentActions ← cell.nextOnList;
RemoveCell[cell];
ENDLOOP;
-- now erase the list of dependent data items
FOR cell: ListCell ← action.dependentData, nextCell WHILE cell # NIL DO
nextCell ← cell.nextOnList;
IF cell.prevList = NIL THEN cell.dataItem.firstActionList ← cell.nextList;
RemoveCell[cell];
ENDLOOP;
action↑ ← [
act: NIL,
info: NIL,
dirty: FALSE,
dependentData: NIL,
firstDataList: NIL,
set: NIL,
sorting: FALSE,
sorted: FALSE,
isSource: FALSE,
prevUnsorted: NIL,
nextUnsorted: NIL,
prevSorted: NIL,
nextSorted: NIL];
set.changed ← TRUE;
Verify[set];
END;
DeactivateDataItem: PUBLIC PROCEDURE[dataItem: DataItem] =
BEGIN
set: DependencySet;
nextCell: ListCell ← NIL;
IF dataItem = NIL THEN RETURN;
set ← dataItem.set;
-- remove the data item from the set lists
IF set.dataItems = dataItem THEN set.dataItems ← dataItem.nextItem;
IF dataItem.prevItem # NIL THEN dataItem.prevItem.nextItem ← dataItem.nextItem;
IF dataItem.nextItem # NIL THEN dataItem.nextItem.prevItem ← dataItem.prevItem;
IF set.dirtyDataItems = dataItem THEN set.dirtyDataItems ← dataItem.nextDirtyItem;
IF dataItem.prevDirtyItem # NIL THEN dataItem.prevDirtyItem.nextDirtyItem ← dataItem.nextDirtyItem;
IF dataItem.nextDirtyItem # NIL THEN dataItem.nextDirtyItem.prevDirtyItem ← dataItem.prevDirtyItem;
-- now remove the data item from all dependent lists hanging off of actions
FOR cell: ListCell ← dataItem.firstActionList, nextCell WHILE cell # NIL DO
nextCell ← cell.nextList;
IF cell.prevOnList = NIL THEN cell.action.dependentData ← cell.nextOnList;
RemoveCell[cell];
ENDLOOP;
-- now erase the list of dependent actions
FOR cell: ListCell ← dataItem.dependentActions, nextCell WHILE cell # NIL DO
nextCell ← cell.nextOnList;
IF cell.prevList = NIL THEN cell.action.firstDataList ← cell.nextList;
RemoveCell[cell];
ENDLOOP;
dataItem↑ ←
[
dirty: FALSE,
set: NIL,
nextItem: NIL,
prevItem: NIL,
nextDirtyItem: NIL,
prevDirtyItem: NIL,
dependentActions: NIL,
firstActionList: NIL];
set.changed ← TRUE;
Verify[set];
END;
SortDependencySet: PUBLIC PROCEDURE[set: DependencySet] =
BEGIN
IF NOT set.changed THEN RETURN;
set.sortedList ← NIL;
FOR action: Action ← set.unSortedList, action.nextUnsorted WHILE action # NIL DO
action.isSource ← TRUE; -- tentative
action.sorting ← action.sorted ← FALSE;
ENDLOOP;
FOR action: Action ← set.unSortedList, action.nextUnsorted WHILE action # NIL DO
MarkNotSource: PROC[act: Action] = {act.isSource ← FALSE};
EnumerateActionDependencies[action, MarkNotSource];
ENDLOOP;
FOR action: Action ← set.unSortedList, action.nextUnsorted WHILE action # NIL DO
IF action.isSource THEN SortOneUnsortedActionAndDependencies[action];
ENDLOOP;
FOR action: Action ← set.unSortedList, action.nextUnsorted WHILE action # NIL DO
IF NOT action.sorted THEN ERROR LoopInDependencyGraph;
ENDLOOP;
FOR dItem: DataItem ← set.dataItems, dItem.nextItem WHILE dItem # NIL DO
IF dItem.firstActionList # NIL AND dItem.firstActionList.nextList # NIL THEN
ERROR MultipleAssignmentToOneDataItem[];
ENDLOOP;
set.changed ← FALSE;
END;
MarkDataItemDirty: PUBLIC PROCEDURE[dataItem: DataItem] =
BEGIN
IF dataItem = NIL THEN RETURN;
IF NOT dataItem.dirty THEN
BEGIN
dataItem.dirty ← TRUE;
dataItem.nextDirtyItem ← dataItem.set.dirtyDataItems;
dataItem.set.dirtyDataItems ← dataItem;
END;
END;
MarkActionDirty: PUBLIC PROCEDURE[action: Action] =
BEGIN
IF action = NIL THEN RETURN;
action.dirty ← TRUE;
action.set.dirtyActionsExist ← TRUE;
END;
DataItemIsSource: PUBLIC PROCEDURE[dataItem: DataItem] RETURNS[--yes-- BOOLEAN] =
BEGIN
RETURN[dataItem.firstActionList = NIL];
END;
PerformDirtyActions: PUBLIC PROCEDURE[set: DependencySet] =
BEGIN
nextDataItem: DataItem;
IF set.dirtyDataItems = NIL AND NOT set.dirtyActionsExist THEN RETURN;
IF set.changed THEN SortDependencySet[set];
-- first process the dirty data items
FOR dataItem: DataItem ← set.dirtyDataItems, nextDataItem WHILE dataItem # NIL DO
nextDataItem ← dataItem.nextDirtyItem;
dataItem.nextDirtyItem ← NIL;
dataItem.dirty ← FALSE;
FOR actionCell: ListCell ← dataItem.dependentActions, actionCell.nextOnList WHILE actionCell # NIL DO
actionCell.action.dirty ← TRUE;
ENDLOOP;
ENDLOOP;
set.dirtyDataItems ← NIL;
-- now process the dirty actions, and subsequent dirty actions
FOR action: Action ← set.sortedList, action.nextSorted WHILE action # NIL DO
IF action.dirty THEN
BEGIN
MarkAsDirty: PROC[act: Action] = {act.dirty ← TRUE};
action.act[action, action.info];
EnumerateActionDependencies[action, MarkAsDirty];
action.dirty ← FALSE;
END;
ENDLOOP;
set.dirtyActionsExist ← FALSE;
END;
MisMatchedDependencySets: PUBLIC ERROR = CODE;
LoopInDependencyGraph: PUBLIC ERROR = CODE;
MultipleAssignmentToOneDataItem: PUBLIC ERROR = CODE;
GetActionInfo: PUBLIC PROCEDURE[action: Action] RETURNS[DependencySet, PROC[Action, REF ANY], REF ANY] =
BEGIN
RETURN[action.set, action.act, action.info];
END;
Verify: PUBLIC PROCEDURE[dSet: DependencySet] =
BEGIN
prevDataItem: DataItem ← NIL;
prevAction: Action ← NIL;
IF NOT debugging THEN RETURN;
-- scan each data item and see if its lists are ok
FOR dataItem: DataItem ← dSet.dataItems, dataItem.nextItem WHILE dataItem # NIL DO
IF dataItem.prevItem # prevDataItem THEN ERROR;
CheckList[dataItem.dependentActions];
CheckListChain[dataItem.firstActionList];
prevDataItem ← dataItem;
ENDLOOP;
-- scan each action and see if some of its chains are ok
FOR action: Action ← dSet.unSortedList, action.nextUnsorted WHILE action # NIL DO
IF action.prevUnsorted # prevAction THEN ERROR;
CheckList[action.dependentData];
CheckListChain[action.firstDataList];
prevAction ← action;
ENDLOOP;
END;
-- local procedures
RemoveCell: PROCEDURE[cell: ListCell] =
BEGIN
IF cell.prevOnList # NIL THEN cell.prevOnList.nextOnList ← cell.nextOnList;
IF cell.nextOnList # NIL THEN cell.nextOnList.prevOnList ← cell.prevOnList;
IF cell.prevList # NIL THEN cell.prevList.nextList ← cell.nextList;
IF cell.nextList # NIL THEN cell.nextList.prevList ← cell.prevList;
cell↑ ← [
action: NIL,
dataItem: NIL,
prevOnList: NIL,
nextOnList: freeListCells,
prevList: NIL,
nextList: NIL];
freeListCells ← cell;
END;
SortOneUnsortedActionAndDependencies: PROCEDURE[action: Action] =
BEGIN
IF action.sorting THEN LoopInDependencyGraph;
IF NOT action.sorted THEN
BEGIN
action.sorting ← TRUE;
EnumerateActionDependencies[action, SortOneUnsortedActionAndDependencies];
action.nextSorted ← action.set.sortedList;
action.set.sortedList ← action;
action.sorting ← FALSE;
action.sorted ← TRUE;
END;
END;
EnumerateActionDependencies: PROCEDURE[action: Action, p: PROC[Action]] =
BEGIN
FOR dataCell: ListCell ← action.dependentData, dataCell.nextOnList WHILE dataCell # NIL DO
FOR actionCell: ListCell ← dataCell.dataItem.dependentActions, actionCell.nextOnList WHILE actionCell # NIL DO
p[actionCell.action];
ENDLOOP;
ENDLOOP;
END;
CheckList: PROCEDURE[cell: ListCell] =
BEGIN
prev: ListCell ← NIL;
nSeen: CARDINAL ← 0;
FOR cell ← cell, cell.nextOnList WHILE cell # NIL DO
IF cell.prevOnList # prev THEN ERROR;
IF cell.action = NIL THEN ERROR;
IF cell.dataItem = NIL THEN ERROR;
prev ← cell;
nSeen ← nSeen + 1;
IF nSeen = 0 THEN ERROR;
ENDLOOP;
END;
CheckListChain: PROCEDURE[cell: ListCell] =
BEGIN
prev: ListCell ← NIL;
nSeen: CARDINAL ← 0;
FOR cell ← cell, cell.nextList WHILE cell # NIL DO
IF cell.prevList # prev THEN ERROR;
IF cell.action = NIL THEN ERROR;
IF cell.dataItem = NIL THEN ERROR;
prev ← cell;
nSeen ← nSeen + 1;
IF nSeen = 0 THEN ERROR;
ENDLOOP;
END;
END..
-- 14-Feb-82 15:09:52: Sturgis, started DependenciesImpl.mesa
-- 14-Feb-82 17:07:26: compiles
-- 16-Feb-82 17:25:02: re-wrote to match the redesigned interface (that involves explicit recognition of data Items) (about 2 to 3 hours)
-- RTE: 19-Feb-82 12:26:11: define data item did not set certain fields, and the compiler defaulted them to NIL!!!, rather than generating an error.
-- RTE: 19-Feb-82 13:51:33: PerformDirtyDataActions had wrong sign on the test for the existince of dirty data items.
-- change: 4-Mar-82 17:23:26: add GetactionInfo for debugging
-- change: 5-Mar-82 11:55:47: add Verify
-- RTE: 5-Mar-82 12:04:56: creating an action did not properly insert it on the unSOrtedlist. similar for creating a dataitem.
-- RTE: 5-Mar-82 12:22:24: when deactivating items, and removing cells on assorted lists, forgot to handle the case of chaning through the first cell on a list, the pointer in the controlling object must be nilled.
-- RTE: 5-Mar-82 12:36:16: prev error got half of the cases, but there are two back pointers that can be nil, not one.
-- RTE: 5-Mar-82 13:01:27: add verify calls to many structure change actions.
-- RTE: 5-Mar-82 13:25:07: when deleting an action, forgot to nil out its back pointer if it was head of unsorted list, due to an editing error when creating the code by copy.
-- Change: 9-Mar-82 16:09:44: add a cehck to see taht all actions are sorted after a sort. Looking for a mysterious bug wherein rows do not recompute when a column is deleted.
-- RTE: 9-Mar-82 16:23:20: adding the above check led to a loop. Seems that I had not been marking the actions unsorted before starting the sort, so ol actions did not end up sorted. while adding the check code I also set the actions unserted. This led to the observation that I wasnt nilling the set.sorted list before starting the sort, so the last sorted action ended up pointing to the first old (and unsroted) action.
-- RTE: 11-Mar-82 17:31:26: the deactivate code worked incorrectly when removing a cell from the first of a list, it set the pointer in the action or data item hoding the list to NIL, rather than to the next cell in the appropriate list.
-- change: 12-Mar-82 10:40:48: add MarkActionDirty, and DataItemIsSource
-- RTE: 12-Mar-82 12:49:10: got the sign wrong on DataItemIsSOurce.
-- RTE: August 2, 1982 4:04 pm: allow Deactivate routines to accept NIL items.
-- change: August 2, 1982 4:16 pm: notice any changes to the set, and if set is marked changed when PerformDirtyActions is called, first sort the set. Also, modify sort procedure to return if no changes have been made.
-- RTE: August 8, 1982 3:34 pm: generate LoopInDependencyGraph as expected, rather than simply ERROR, when finding such a loop.
-- August 8, 1982 3:59 pm: add catch for multiple assignment to one data item.
-- change: October 6, 1982 3:05 pm: add a global flag to turn the verifier on and off. Nominally off.
-- change: November 13, 1982 3:28 pm: tighten up verify to check for nil entries in cells.
-- RTE: November 13, 1982 3:49 pm: When deactivating a data item, it remained on the dirtyDataItems chain (no back pointer to remove it with). Moreover, we left its dependentActions list pointing into the FreeCells chain, because the cells on its dependentAction list had been "freed", and we did not nil the corresponding pointer in the DataItem.
-- March 2, 1983 9:18 am: make sure deactivation routines nil out all pointers.
-- Change: July 13, 1984 1:18:17 pm PDT: after placing many nil tests in client code, I have finally decided to put the NIL tests in the mark dirty routines and not dependence routines.