windows-nt-4.0/private/rpc/midlnew/doc/doc2.doc

THE TYPE GRAPH DRIVER
---------------------

	The Type graph driver is the interface to the type graph. It is
	a two-tiered interface (Level-1 and level-2). Level-1 provides
	mainly navigational functions. Level-2 provides the high level 
	interface.

	The above scheme is currently under discussion and can be taken as
	a starting point for further discussion and design.

	The two-tiered interface attempts to provide a black box - like 
	interface to the type graph , so that the type graph can be
	structurally altered without the rest of the application being
	affected. It interface is a set of macros that provide a 
	function-like flavor but have the advantage of compactness in
	code.

	Level-1 functions:
	------------------
	    Level-1 functions have intimate knowledge of the type graph, and
	    are intended to be used by the level-2 functions for the direct
	    type graph interface.

		1. TypeNode * GetChild( TypeNode *)
		2. TypeNode * GetSibling( TypeNode *)
		3. TypeNode * GetAttributeList( TypeNode *)
		4. ....
		
		5. STATUS_T SetChild( TypeNode *)
		6. STATUS_T SetSibling( TypeNode *)
		7. STATUS_T SetAttributeList( TypeNode *typenode, TypeNode * attrlist)
		8. .....
	
	Level-2 functions:
	------------------
	    Level-2 functions are intended to provide a certain level of 
	    abstraction on the type graph. These functions need to know
	    the general structure of the type graph too, but only at the
	    abstarct level. For example, it is known to Level-2 functions 
	    that a node has child pointers and sibling pointers but the
	    actual structure member names of the type graph need not be 
	    known to them. Level-2 functions interface to the external world.
	    Level-2 functions call Level-1 functions for accessing actual 
	    members of the type graph.

	    It is difficult to pin down the exact level-2 functions needed
	    since this interface is still under discussion. For each type
	    of higher-level type node (e.g function, structure tag, user
	    defined type etc) the level-2 functions will differ. For example
	    for a structure node (NODE_STRUCT), the sibling pointers are
	    other types defined at the same lexical scoping level, and child
	    pointers are pointers to the type-sub-graph corresponding to 
	    its members(i.e at a lower (or higher ?) lexical scoping.
	    For a member which has a base type, the sibling points to next
	    members of the structure, while the child points to the base
	    type sub-graph.

	    Assume we recognise the following structure:

		struct foo	{
		    short x;
		    long y;
		};

	    The type graph will have a node of type NODE_STRUCT with the
	    sibling pointing to the next structure , if any, at the same 
	    lexical level, while its child pointers will point to a
	    node of type NODE_FIELD (for x). The sibling pointer for x
	    will point to a node of type NODE_FIELD (for y). The sibling 
	    pointer of y will be NULL. The child pointer for the x node will
	    point to a type sub-graph for short, while that for y will point
	    to a type sub-graph for long.

	    Assume that for some semantic action, we need to find out the 
	    number of fields in this structure. The following program is a 
	    C fragment which represents a level-2 interface. Notice how the
	    Level-1 functions are called to traverse the type graph. Also
	    note that the level-2 functions know (but only in abstract form)
	    that the member fields are in a child type sub-graph.

	    int
	    MemberCount( TypeNode *pStruct )
		{
		TypeNode *	pMembers = GetChild(pStruct);
		int		cCount = 0;

		if(pMembers)
		    do
		      { 
		      cCount++;
		      } while(pMembers = GetSibling(pMembers));
		return cCount;
		}

	    Semantic actions in the parser can work on the notion of an 
	    abstract type graph, with the level-1 and level-2 routines
	    providing the translation to the type-graph structure.
	    
BUILDING THE TYPE GRAPH
-----------------------

	Building the type graph will be integrated into the semantic actions
	that take place on reduction of various productions in the parser.
	The type graph is built in a bottom up fashion, and exploits the
	suitablility of the parser stack to transmission of synthesised
	attributes.

	Assuming for the sake of explanation that the idl file consists of
	only structure definitions and base types. The productions that will
	recognise the syntax of the idl file will be:

	idl_file
		: base_type 					(1)
		  {
		  /***
		   *** Allocate an idl node. Attach the type sub-graph
		   *** returned by base_types
		   ***/
		  }
		| struct_type 					(2)
		  {
		  /***
		   *** Allocate an idl node. Attach the type sub-graph
		   *** returned by struct_types
		   ***/
		  }
		;
	struct_types
		: STRUCT ID '{' struct_members '} ID ';'	(3)
		  {
		  /***
		   *** A structure was just recognised. Allocate a
		   *** structure node. struct_members returns a 
		   *** type sub-graph too. Attach that type subgraph
		   *** to the child of the structure node
		   ***/
		  }
		;

	struct_members
		: struct members struct_member			(3a)
		  {
		  /***
		   *** Attach the type sub-graph returned by struct_member
		   *** to the type graph already existingnor structure
		   *** members
		   ***/
		  }
		| struct_member					(3b)
		  {
		  /***
		   *** The first structure member was recognised.
		   *** Any semantic action here ? Maybe initialisation
		   *** of some sort
		   ***/
		  }
		;

	struct_members
		: base_type 					(4)
		  {
		  /***
		   *** allocate a member node, since a structure
		   *** member has been recognised. Attach the 
		   *** type-subgraph returned by "base_types" to
		   *** the child node of member
		   ***/
		  }
		| struct_type 					(5)
		  {
		  /***
		   *** allocate a member node, since a structure
		   *** member has been recognised. Attach the 
		   *** type-subgraph returned by "struct_types" to
		   *** the child node of member
		   ***/
		  }
		;
	base_type
		: SHORT ID ';' 					(6)
		  {
		  /***
		   *** return a type subgraph for SHORT
		   ***/
		  }
		| ....
		;
	
	Let us attempt to recognise the following syntax:

	struct foo 
	    {
	    short foo_x;
	    struct bar 
	        {
	        short bar_x;
	        }foobar;
	    } myfoo;

	Without going into exact details of the parsing process, it 
	suffices to say that short foo_x is recognised by rule 6, 
	base_types returns a pointer to the type sub-grap for short.
	short foo_x gets reduced to a member by rule 3b. A member
	node is allocated, and the type sub-graph for short is attached
	as a child to the member node. Struct bar is recognised recursively
	and returns a type sub-graph for struct itself. Now another
	member node is allocated and the ype subgraph is attached as a
	child node for it. The second member is recognised by rule 3a and
	is attached as a sibling to the first member (foo_x). This process
	continues till struct foo is completely recognised. An idl node
	is allocated in rule 1 and the type graph gets attached to 
	it as a child. The entire process is hence building the type graph
	in a bottom-up manner.

	Special case:
	--------------
	1. Forward declaration of structures will result in a dummy structure
	   node allocated with child pointer as a null. The symbol table entry
	   will be marked as used-but-not-defined. When the structure does get
	   defined, it will be unmarked. At the end of the compilation pass,
	   any undefined structures will result in an error.

	2. Recursive declaration will be treated in the same manner.