-- 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.