generic/compiler/anontype.h

/*  ASCEND modelling environment
    Copyright (C) 2006 Carnegie Mellon University
    Copyright 1997, Carnegie Mellon University.

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2, or (at your option)
    any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program; if not, write to the Free Software
    Foundation, Inc., 59 Temple Place - Suite 330,
    Boston, MA 02111-1307, USA.
*//** @file
    'Anonymous type' classification functions.

    The idea of this module is to find and report groups of
    isomorphic instances (instances with the same Anonymous Type).
    We do not actually produce type definitions, or anything like them,
    but instead use various sorting techniques. Note that anonymous
    type is a dynamic quantity in the ascend language definition which
    allows deferred binding.
    This should be named something like isomorph.c, but half the compiler
    files start with i already.
    These functions are thread-safe, if the instance data
    structures are, as this module creates no global variables.
    At present, instance structures are not thread-safe unless the
    entire global simulations list is locked into one thread.

    Ultimately the user will be returned a gl_list of AnonType pointers,
    where each pointer knows how many occurrences of some identical AT
    there are and where those occurences are. This list will become
    invalid if any compiler actions anywhere in the simulation universe
    change any of the instances in such a way that any instance is
    MOVED (e.g. by realloc) or modified independently of all other
    instances in the same anonymous type group.

    The Instances are NOT left with a record of their anonymous type.
    Each AT has a unique index number, which is its position in the
    gl_list returned. There is no useful ordering of the gl_list returned.
    Each AT knows its formal family as a doubly linked list, and each
    AT has a counter, visited, that the user can do arbitrary things
    with. The doubly linked list is ordered in some way that is an
    artifact of the classification algorithm. The head and tail of
    the linked list are NULL.

    Special cases:

    -# Relations, logical relations, and when statements are always
       anonymous in the following sense:

       They are more like atomic types. Their true 'formal type',
       if you like, is the statement defining them since their
       basic DEFINITIONS are universal. If you accept this, then
       you can easily see also that the 'anonymous type' (the
       expanded token form) of a relation is entirely dependent
       on the anonymous type of the relation's context. This also
       holds for logical relations and when structures.

       So, in the collected 'anonymous types', there will be only as
       many AT's devoted to relations as there are formal definitions
       present in the system for relation (normally just 1).
       The AT for each formal relation definition present will have
       an instance list of all relations from that definition.

       To find cliques of relations, just look at cliques of models.
       If this handling of relations is insufficient, then the
       statement of the relation could be used in a secondary slot
       of the AT. To find exact relation groups requires a two pass
       algorithm.

    -# Arrays. ASCEND arrays just suck. The approach here is
       conservative; there may be fewer array cliques than we can
       compute with a single pass algorithm.

    -# Undefined constants. Constant reals/integers which are undefined
       are sorted as if they have DBL_MAX/LONG_MAX for a value. We are
       assuming there are no meaningful constants for modeling
       which take on the maximum value of the machine representation.

    Requires
    #include <stdio.h>
           #include "utilities/ascConfig.h"
           #include "general/list.h"
           #include "compiler/instance_enum.h"
    
*//*
    By Benjamin Andrew Allan
    Created August 30, 1997.
    Last in CVS: $Revision: 1.5 $ $Date: 1998/02/05 22:23:20 $ $Author: ballan $
*/

#ifndef ASC_ANONTYPE_H
#define ASC_ANONTYPE_H

/** addtogroup compiler Compiler
    @{
*/

/** For debugging set =1, for performance set = 0 */
#define ATDEBUG 0

/** abbreviated AT in comments */
struct AnonType {
   unsigned long index;           /**< index in the gllist of ATs
                                      0 -> not in list. -1 == freed. */
   struct gl_list_t *instances;   /**< list of this AT's instances */
   struct AnonType *prev, *next;  /**< other ATs related by
                                       all being the same formally. */
   int exactfamily;               /**< group id of anonymous types which are
                                       identical except for merged substructure. */
   int visited;                   /**< counter for arbitrary use. */
};

/**
 * The initial number of instances to expect for each AT.
 * Tuning this may be hard. E.g. relations and some atoms
 * will grow to a huge number, but many constant types will
 * only have 1-3 instances shared universally.
 * In a distillation MODEL there are ~400 anon types
 * and most of these fall in the constant types.
 */
#define INSTANCES_PER_AT 2

/**
 * Define the expected maximum number of anonymous types.
 * This should not be too low or the code will do memory
 * reallocation of gl_list, atl.
 */
#define ANONEXPECTED 200

/**
 * Define the size for the hash tables keyed by the
 * formal type name and secondarily keyed by type ptr.
 * The secondary key is required because mixed simulations
 * may be created by pathological users and we must not
 * get confused when classifying.
 * One such hash table is used while classifying an instance tree
 * into AT groups. The user never sees this table, however.
 * This size must be even power of 2 and shouldn't be messed with.
 */
#define ANONTABLESIZE 1024

/**
 * Return the nth element of anon type list n.
 * The return type is <code>AnonType*</code>.
 */
#define Asc_GetAnonType(atl,n) \
  ((struct AnonType *)gl_fetch((atl),(n)))

/**
 * Return the number of instances associated with the nth position
 * in anonymous type list n.  The return value is type
 * <code>unsigned long</code>.
 */
#define Asc_GetAnonCount(atl,n) \
  gl_length(Asc_GetAnonType((atl),(n))->instances)

/**
 * Returns the cth member of an anonymous type clique
 * represented by at.  The return value is type <code>Instance*</code>.
 * @param at  an AnonType*, such as returned by: at = Asc_GetAnonType(atl,n);
 * @param  c  index:  1 <= c <= Asc_GetAnonCount(atl,n)
 */
#define Asc_GetAnonTypeInstance(at,c) \
  (struct Instance *)gl_fetch((at)->instances,(c))

/**
 * Returns the first element of the instance list associated with the
 * AT given. Does not normally return unless there is such a creature.
 */
extern struct Instance *Asc_GetAnonPrototype(struct AnonType *at);

/**
 * Destroys the anonlist we returned from a call to classify.
 * Do not destroy this list any other way.
 */
ASC_DLLSPEC void Asc_DestroyAnonList(struct gl_list_t *atl);

/**
 * This function classifies an instance tree
 * and returns the list described above.
 * root may be at any place in an instance tree.
 * The list should be destroyed with Asc_DestroyAnonList.
 */
ASC_DLLSPEC struct gl_list_t *Asc_DeriveAnonList(struct Instance *root);

/**
 * Writes a list of anon type info in atl, mainly for debugging purposes,
 * to the file given. root is the instance that Asc_DeriveAnonList
 * was called with, for the proper writing of names.
 * If root is NULL, arbitrary names will be made up.
 * If mlists != 0 and merge info exists, merge info will be written
 * with the AT info.
 */
ASC_DLLSPEC void Asc_WriteAnonList(FILE *fp,
                              struct gl_list_t *atl,
                              struct Instance *root,
                              int mlists);

/* @} */

#endif  /* ASC_ANONTYPE_H */

1	/* ASCEND modelling environment
2	Copyright (C) 2006 Carnegie Mellon University
3	Copyright 1997, Carnegie Mellon University.
4
5	This program is free software; you can redistribute it and/or modify
6	it under the terms of the GNU General Public License as published by
7	the Free Software Foundation; either version 2, or (at your option)
8	any later version.
9
10	This program is distributed in the hope that it will be useful,
11	but WITHOUT ANY WARRANTY; without even the implied warranty of
12	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13	GNU General Public License for more details.
14
15	You should have received a copy of the GNU General Public License
16	along with this program; if not, write to the Free Software
17	Foundation, Inc., 59 Temple Place - Suite 330,
18	Boston, MA 02111-1307, USA.
19	//* @file
20	'Anonymous type' classification functions.
21
22	The idea of this module is to find and report groups of
23	isomorphic instances (instances with the same Anonymous Type).
24	We do not actually produce type definitions, or anything like them,
25	but instead use various sorting techniques. Note that anonymous
26	type is a dynamic quantity in the ascend language definition which
27	allows deferred binding.
28	This should be named something like isomorph.c, but half the compiler
29	files start with i already.
30	These functions are thread-safe, if the instance data
31	structures are, as this module creates no global variables.
32	At present, instance structures are not thread-safe unless the
33	entire global simulations list is locked into one thread.
34
35	Ultimately the user will be returned a gl_list of AnonType pointers,
36	where each pointer knows how many occurrences of some identical AT
37	there are and where those occurences are. This list will become
38	invalid if any compiler actions anywhere in the simulation universe
39	change any of the instances in such a way that any instance is
40	MOVED (e.g. by realloc) or modified independently of all other
41	instances in the same anonymous type group.
42
43	The Instances are NOT left with a record of their anonymous type.
44	Each AT has a unique index number, which is its position in the
45	gl_list returned. There is no useful ordering of the gl_list returned.
46	Each AT knows its formal family as a doubly linked list, and each
47	AT has a counter, visited, that the user can do arbitrary things
48	with. The doubly linked list is ordered in some way that is an
49	artifact of the classification algorithm. The head and tail of
50	the linked list are NULL.
51
52	Special cases:
53
54	-# Relations, logical relations, and when statements are always
55	anonymous in the following sense:
56
57	They are more like atomic types. Their true 'formal type',
58	if you like, is the statement defining them since their
59	basic DEFINITIONS are universal. If you accept this, then
60	you can easily see also that the 'anonymous type' (the
61	expanded token form) of a relation is entirely dependent
62	on the anonymous type of the relation's context. This also
63	holds for logical relations and when structures.
64
65	So, in the collected 'anonymous types', there will be only as
66	many AT's devoted to relations as there are formal definitions
67	present in the system for relation (normally just 1).
68	The AT for each formal relation definition present will have
69	an instance list of all relations from that definition.
70
71	To find cliques of relations, just look at cliques of models.
72	If this handling of relations is insufficient, then the
73	statement of the relation could be used in a secondary slot
74	of the AT. To find exact relation groups requires a two pass
75	algorithm.
76
77	-# Arrays. ASCEND arrays just suck. The approach here is
78	conservative; there may be fewer array cliques than we can
79	compute with a single pass algorithm.
80
81	-# Undefined constants. Constant reals/integers which are undefined
82	are sorted as if they have DBL_MAX/LONG_MAX for a value. We are
83	assuming there are no meaningful constants for modeling
84	which take on the maximum value of the machine representation.
85
86	Requires
87	#include <stdio.h>
88	#include "utilities/ascConfig.h"
89	#include "general/list.h"
90	#include "compiler/instance_enum.h"
91
92	//
93	By Benjamin Andrew Allan
94	Created August 30, 1997.
95	Last in CVS: $Revision: 1.5 $ $Date: 1998/02/05 22:23:20 $ $Author: ballan $
96	*/
97
98	#ifndef ASC_ANONTYPE_H
99	#define ASC_ANONTYPE_H
100
101	/** addtogroup compiler Compiler
102	@{
103	*/
104
105	/** For debugging set =1, for performance set = 0 */
106	#define ATDEBUG 0
107
108	/** abbreviated AT in comments */
109	struct AnonType {
110	unsigned long index; /**< index in the gllist of ATs
111	0 -> not in list. -1 == freed. */
112	struct gl_list_t instances; /< list of this AT's instances /
113	struct AnonType prev, next; /**< other ATs related by
114	all being the same formally. */
115	int exactfamily; /**< group id of anonymous types which are
116	identical except for merged substructure. */
117	int visited; /*< counter for arbitrary use. /
118	};
119
120	/**
121	* The initial number of instances to expect for each AT.
122	* Tuning this may be hard. E.g. relations and some atoms
123	* will grow to a huge number, but many constant types will
124	* only have 1-3 instances shared universally.
125	* In a distillation MODEL there are ~400 anon types
126	* and most of these fall in the constant types.
127	*/
128	#define INSTANCES_PER_AT 2
129
130	/**
131	* Define the expected maximum number of anonymous types.
132	* This should not be too low or the code will do memory
133	* reallocation of gl_list, atl.
134	*/
135	#define ANONEXPECTED 200
136
137	/**
138	* Define the size for the hash tables keyed by the
139	* formal type name and secondarily keyed by type ptr.
140	* The secondary key is required because mixed simulations
141	* may be created by pathological users and we must not
142	* get confused when classifying.
143	* One such hash table is used while classifying an instance tree
144	* into AT groups. The user never sees this table, however.
145	* This size must be even power of 2 and shouldn't be messed with.
146	*/
147	#define ANONTABLESIZE 1024
148
149	/**
150	* Return the nth element of anon type list n.
151	* The return type is <code>AnonType*</code>.
152	*/
153	#define Asc_GetAnonType(atl,n) \
154	((struct AnonType *)gl_fetch((atl),(n)))
155
156	/**
157	* Return the number of instances associated with the nth position
158	* in anonymous type list n. The return value is type
159	* <code>unsigned long</code>.
160	*/
161	#define Asc_GetAnonCount(atl,n) \
162	gl_length(Asc_GetAnonType((atl),(n))->instances)
163
164	/**
165	* Returns the cth member of an anonymous type clique
166	* represented by at. The return value is type <code>Instance*</code>.
167	* @param at an AnonType*, such as returned by: at = Asc_GetAnonType(atl,n);
168	* @param c index: 1 <= c <= Asc_GetAnonCount(atl,n)
169	*/
170	#define Asc_GetAnonTypeInstance(at,c) \
171	(struct Instance *)gl_fetch((at)->instances,(c))
172
173	/**
174	* Returns the first element of the instance list associated with the
175	* AT given. Does not normally return unless there is such a creature.
176	*/
177	extern struct Instance Asc_GetAnonPrototype(struct AnonType at);
178
179	/**
180	* Destroys the anonlist we returned from a call to classify.
181	* Do not destroy this list any other way.
182	*/
183	ASC_DLLSPEC void Asc_DestroyAnonList(struct gl_list_t *atl);
184
185	/**
186	* This function classifies an instance tree
187	* and returns the list described above.
188	* root may be at any place in an instance tree.
189	* The list should be destroyed with Asc_DestroyAnonList.
190	*/
191	ASC_DLLSPEC struct gl_list_t Asc_DeriveAnonList(struct Instance root);
192
193	/**
194	* Writes a list of anon type info in atl, mainly for debugging purposes,
195	* to the file given. root is the instance that Asc_DeriveAnonList
196	* was called with, for the proper writing of names.
197	* If root is NULL, arbitrary names will be made up.
198	* If mlists != 0 and merge info exists, merge info will be written
199	* with the AT info.
200	*/
201	ASC_DLLSPEC void Asc_WriteAnonList(FILE *fp,
202	struct gl_list_t *atl,
203	struct Instance *root,
204	int mlists);
205
206	/* @} */
207
208	#endif /* ASC_ANONTYPE_H */
209