1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/sourcepawn/compiler/scstate.c Sun Mar 30 07:00:22 2008 +0000
1.3 @@ -0,0 +1,375 @@
1.4 +/* Pawn compiler
1.5 + *
1.6 + * Machine and state maintenance.
1.7 + *
1.8 + * Three lists are maintained here:
1.9 + * - A list of automatons (state machines): these hold a name, a unique id
1.10 + * (in the "index" field) and the memory address of a cell that holds the
1.11 + * current state of the automaton (in the "value" field).
1.12 + * - A list of states for each automaton: a name, an automaton id (in the
1.13 + * "index" field) and a unique id for the state (unique in the automaton;
1.14 + * states belonging to different automatons may have the same id).
1.15 + * - A list of state combinations. Each function may belong to a set of states.
1.16 + * This list assigns a unique id to the combination of the automaton and all
1.17 + * states.
1.18 + *
1.19 + * For a function/variable that has states, there is a fourth list, which is
1.20 + * attached to the "symbol" structure. This list contains the code label (in
1.21 + * the "name" field, only for functions), the id of the state combinations (the
1.22 + * state list id; it is stored in the "index" field) and the code address at
1.23 + * which the function starts. The latter is currently unused.
1.24 + *
1.25 + * At the start of the compiled code, a set of stub functions is generated.
1.26 + * Each stub function looks up the value of the "state selector" value for the
1.27 + * automaton, and goes with a "switch" instruction to the start address of the
1.28 + * function. This happens in SC4.C.
1.29 + *
1.30 + *
1.31 + * Copyright (c) ITB CompuPhase, 2005-2006
1.32 + *
1.33 + * This software is provided "as-is", without any express or implied warranty.
1.34 + * In no event will the authors be held liable for any damages arising from
1.35 + * the use of this software.
1.36 + *
1.37 + * Permission is granted to anyone to use this software for any purpose,
1.38 + * including commercial applications, and to alter it and redistribute it
1.39 + * freely, subject to the following restrictions:
1.40 + *
1.41 + * 1. The origin of this software must not be misrepresented; you must not
1.42 + * claim that you wrote the original software. If you use this software in
1.43 + * a product, an acknowledgment in the product documentation would be
1.44 + * appreciated but is not required.
1.45 + * 2. Altered source versions must be plainly marked as such, and must not be
1.46 + * misrepresented as being the original software.
1.47 + * 3. This notice may not be removed or altered from any source distribution.
1.48 + *
1.49 + * Version: $Id$
1.50 + */
1.51 +#include <assert.h>
1.52 +#include <limits.h>
1.53 +#include <stdio.h>
1.54 +#include <stdlib.h>
1.55 +#include <string.h>
1.56 +#include "sc.h"
1.57 +#if defined LINUX || defined __FreeBSD__ || defined __OpenBSD__
1.58 + #include <sclinux.h>
1.59 +#endif
1.60 +
1.61 +#if defined FORTIFY
1.62 + #include <alloc/fortify.h>
1.63 +#endif
1.64 +
1.65 +typedef struct s_statelist {
1.66 + struct s_statelist *next;
1.67 + int *states; /* list of states in this combination */
1.68 + int numstates; /* number of items in the above list */
1.69 + int fsa; /* automaton id */
1.70 + int listid; /* unique id for this combination list */
1.71 +} statelist;
1.72 +
1.73 +static statelist statelist_tab = { NULL, NULL, 0, 0, 0}; /* state combinations table */
1.74 +
1.75 +
1.76 +static constvalue *find_automaton(const char *name,int *last)
1.77 +{
1.78 + constvalue *ptr;
1.79 +
1.80 + assert(last!=NULL);
1.81 + *last=0;
1.82 + ptr=sc_automaton_tab.next;
1.83 + while (ptr!=NULL) {
1.84 + if (strcmp(name,ptr->name)==0)
1.85 + return ptr;
1.86 + if (ptr->index>*last)
1.87 + *last=ptr->index;
1.88 + ptr=ptr->next;
1.89 + } /* while */
1.90 + return NULL;
1.91 +}
1.92 +
1.93 +SC_FUNC constvalue *automaton_add(const char *name)
1.94 +{
1.95 + constvalue *ptr;
1.96 + int last;
1.97 +
1.98 + assert(strlen(name)<sizeof(ptr->name));
1.99 + ptr=find_automaton(name,&last);
1.100 + if (ptr==NULL) {
1.101 + assert(last+1 <= SHRT_MAX);
1.102 + ptr=append_constval(&sc_automaton_tab,name,(cell)0,(short)(last+1));
1.103 + } /* if */
1.104 + return ptr;
1.105 +}
1.106 +
1.107 +SC_FUNC constvalue *automaton_find(const char *name)
1.108 +{
1.109 + int last;
1.110 + return find_automaton(name,&last);
1.111 +}
1.112 +
1.113 +SC_FUNC constvalue *automaton_findid(int id)
1.114 +{
1.115 + constvalue *ptr;
1.116 + for (ptr=sc_automaton_tab.next; ptr!=NULL && ptr->index!=id; ptr=ptr->next)
1.117 + /* nothing */;
1.118 + return ptr;
1.119 +}
1.120 +
1.121 +
1.122 +static constvalue *find_state(const char *name,int fsa,int *last)
1.123 +{
1.124 + constvalue *ptr;
1.125 +
1.126 + assert(last!=NULL);
1.127 + *last=0;
1.128 + ptr=sc_state_tab.next;
1.129 + while (ptr!=NULL) {
1.130 + if (ptr->index==fsa) {
1.131 + if (strcmp(name,ptr->name)==0)
1.132 + return ptr;
1.133 + if ((int)ptr->value>*last)
1.134 + *last=(int)ptr->value;
1.135 + } /* if */
1.136 + ptr=ptr->next;
1.137 + } /* while */
1.138 + return NULL;
1.139 +}
1.140 +
1.141 +SC_FUNC constvalue *state_add(const char *name,int fsa)
1.142 +{
1.143 + constvalue *ptr;
1.144 + int last;
1.145 +
1.146 + assert(strlen(name)<sizeof(ptr->name));
1.147 + ptr=find_state(name,fsa,&last);
1.148 + if (ptr==NULL) {
1.149 + assert(fsa <= SHRT_MAX);
1.150 + ptr=append_constval(&sc_state_tab,name,(cell)(last+1),(short)fsa);
1.151 + } /* if */
1.152 + return ptr;
1.153 +}
1.154 +
1.155 +SC_FUNC constvalue *state_find(const char *name,int fsa_id)
1.156 +{
1.157 + int last; /* dummy */
1.158 + return find_state(name,fsa_id,&last);
1.159 +}
1.160 +
1.161 +SC_FUNC constvalue *state_findid(int id)
1.162 +{
1.163 + constvalue *ptr;
1.164 + for (ptr=sc_state_tab.next; ptr!=NULL && ptr->value!=id; ptr=ptr->next)
1.165 + /* nothing */;
1.166 + return ptr;
1.167 +}
1.168 +
1.169 +SC_FUNC void state_buildlist(int **list,int *listsize,int *count,int stateid)
1.170 +{
1.171 + int idx;
1.172 +
1.173 + assert(list!=NULL);
1.174 + assert(listsize!=NULL);
1.175 + assert(*listsize>=0);
1.176 + assert(count!=NULL);
1.177 + assert(*count>=0);
1.178 + assert(*count<=*listsize);
1.179 +
1.180 + if (*count==*listsize) {
1.181 + /* To avoid constantly calling malloc(), the list is grown by 4 states at
1.182 + * a time.
1.183 + */
1.184 + *listsize+=4;
1.185 + *list=(int*)realloc(*list,*listsize*sizeof(int));
1.186 + if (*list==NULL)
1.187 + error(103); /* insufficient memory */
1.188 + } /* if */
1.189 +
1.190 + /* find the insertion point (the list has to stay sorted) */
1.191 + for (idx=0; idx<*count && *list[idx]<stateid; idx++)
1.192 + /* nothing */;
1.193 + if (idx<*count)
1.194 + memmove(&(*list)[idx+1],&(*list)[idx],(int)((*count-idx+1)*sizeof(int)));
1.195 + (*list)[idx]=stateid;
1.196 + *count+=1;
1.197 +}
1.198 +
1.199 +static statelist *state_findlist(int *list,int count,int fsa,int *last)
1.200 +{
1.201 + statelist *ptr;
1.202 + int i;
1.203 +
1.204 + assert(count>0);
1.205 + assert(last!=NULL);
1.206 + *last=0;
1.207 + ptr=statelist_tab.next;
1.208 + while (ptr!=NULL) {
1.209 + if (ptr->listid>*last)
1.210 + *last=ptr->listid;
1.211 + if (ptr->fsa==fsa && ptr->numstates==count) {
1.212 + /* compare all states */
1.213 + for (i=0; i<count && ptr->states[i]==list[i]; i++)
1.214 + /* nothing */;
1.215 + if (i==count)
1.216 + return ptr;
1.217 + } /* if */
1.218 + ptr=ptr->next;
1.219 + } /* while */
1.220 + return NULL;
1.221 +}
1.222 +
1.223 +static statelist *state_getlist_ptr(int listid)
1.224 +{
1.225 + statelist *ptr;
1.226 +
1.227 + assert(listid>0);
1.228 + for (ptr=statelist_tab.next; ptr!=NULL && ptr->listid!=listid; ptr=ptr->next)
1.229 + /* nothing */;
1.230 + return ptr;
1.231 +}
1.232 +
1.233 +SC_FUNC int state_addlist(int *list,int count,int fsa)
1.234 +{
1.235 + statelist *ptr;
1.236 + int last;
1.237 +
1.238 + assert(list!=NULL);
1.239 + assert(count>0);
1.240 + ptr=state_findlist(list,count,fsa,&last);
1.241 + if (ptr==NULL) {
1.242 + if ((ptr=(statelist*)malloc(sizeof(statelist)))==NULL)
1.243 + error(103); /* insufficient memory */
1.244 + if ((ptr->states=(int*)malloc(count*sizeof(int)))==NULL) {
1.245 + free(ptr);
1.246 + error(103); /* insufficient memory */
1.247 + } /* if */
1.248 + memcpy(ptr->states,list,count*sizeof(int));
1.249 + ptr->numstates=count;
1.250 + ptr->fsa=fsa;
1.251 + ptr->listid=last+1;
1.252 + ptr->next=statelist_tab.next;
1.253 + statelist_tab.next=ptr;
1.254 + } /* if */
1.255 + assert(ptr!=NULL);
1.256 + return ptr->listid;
1.257 +}
1.258 +
1.259 +SC_FUNC void state_deletetable(void)
1.260 +{
1.261 + statelist *ptr;
1.262 +
1.263 + while (statelist_tab.next!=NULL) {
1.264 + ptr=statelist_tab.next;
1.265 + /* unlink first */
1.266 + statelist_tab.next=ptr->next;
1.267 + /* then delete */
1.268 + assert(ptr->states!=NULL);
1.269 + free(ptr->states);
1.270 + free(ptr);
1.271 + } /* while */
1.272 +}
1.273 +
1.274 +SC_FUNC int state_getfsa(int listid)
1.275 +{
1.276 + statelist *ptr;
1.277 +
1.278 + assert(listid>=0);
1.279 + if (listid==0)
1.280 + return -1;
1.281 +
1.282 + ptr=state_getlist_ptr(listid);
1.283 + return (ptr!=NULL) ? ptr->fsa : -1; /* fsa 0 exists */
1.284 +}
1.285 +
1.286 +SC_FUNC int state_count(int listid)
1.287 +{
1.288 + statelist *ptr=state_getlist_ptr(listid);
1.289 + if (ptr==NULL)
1.290 + return 0; /* unknown list, no states in it */
1.291 + return ptr->numstates;
1.292 +}
1.293 +
1.294 +SC_FUNC int state_inlist(int listid,int state)
1.295 +{
1.296 + statelist *ptr;
1.297 + int i;
1.298 +
1.299 + ptr=state_getlist_ptr(listid);
1.300 + if (ptr==NULL)
1.301 + return FALSE; /* unknown list, state not in it */
1.302 + for (i=0; i<ptr->numstates; i++)
1.303 + if (ptr->states[i]==state)
1.304 + return TRUE;
1.305 + return FALSE;
1.306 +}
1.307 +
1.308 +SC_FUNC int state_listitem(int listid,int index)
1.309 +{
1.310 + statelist *ptr;
1.311 +
1.312 + ptr=state_getlist_ptr(listid);
1.313 + assert(ptr!=NULL);
1.314 + assert(index>=0 && index<ptr->numstates);
1.315 + return ptr->states[index];
1.316 +}
1.317 +
1.318 +static int checkconflict(statelist *psrc,statelist *ptgt)
1.319 +{
1.320 + int s,t;
1.321 +
1.322 + assert(psrc!=NULL);
1.323 + assert(ptgt!=NULL);
1.324 + for (s=0; s<psrc->numstates; s++)
1.325 + for (t=0; t<ptgt->numstates; t++)
1.326 + if (psrc->states[s]==ptgt->states[t])
1.327 + return 1; /* state conflict */
1.328 + return 0;
1.329 +}
1.330 +
1.331 +/* This function searches whether one of the states in the list of statelist id's
1.332 + * of a symbol exists in any other statelist id's of the same function; it also
1.333 + * verifies that all definitions of the symbol are in the same automaton.
1.334 + */
1.335 +SC_FUNC void state_conflict(symbol *root)
1.336 +{
1.337 + statelist *psrc,*ptgt;
1.338 + constvalue *srcptr,*tgtptr;
1.339 + symbol *sym;
1.340 +
1.341 + assert(root!=NULL);
1.342 + for (sym=root->next; sym!=NULL; sym=sym->next) {
1.343 + if (sym->parent!=NULL || sym->ident!=iFUNCTN)
1.344 + continue; /* hierarchical data type or no function */
1.345 + if (sym->states==NULL)
1.346 + continue; /* this function has no states */
1.347 + for (srcptr=sym->states->next; srcptr!=NULL; srcptr=srcptr->next) {
1.348 + if (srcptr->index==-1)
1.349 + continue; /* state list id -1 is a special case */
1.350 + psrc=state_getlist_ptr(srcptr->index);
1.351 + assert(psrc!=NULL);
1.352 + for (tgtptr=srcptr->next; tgtptr!=NULL; tgtptr=tgtptr->next) {
1.353 + if (tgtptr->index==-1)
1.354 + continue; /* state list id -1 is a special case */
1.355 + ptgt=state_getlist_ptr(tgtptr->index);
1.356 + assert(ptgt!=NULL);
1.357 + if (psrc->fsa!=ptgt->fsa && strcmp(sym->name,uENTRYFUNC)!=0)
1.358 + error(83,sym->name); /* this function is part of another machine */
1.359 + if (checkconflict(psrc,ptgt))
1.360 + error(84,sym->name); /* state conflict */
1.361 + } /* for (tgtptr) */
1.362 + } /* for (srcptr) */
1.363 + } /* for (sym) */
1.364 +}
1.365 +
1.366 +/* check whether the two state lists (whose ids are passed in) share any
1.367 + * states
1.368 + */
1.369 +SC_FUNC int state_conflict_id(int listid1,int listid2)
1.370 +{
1.371 + statelist *psrc,*ptgt;
1.372 +
1.373 + psrc=state_getlist_ptr(listid1);
1.374 + assert(psrc!=NULL);
1.375 + ptgt=state_getlist_ptr(listid2);
1.376 + assert(ptgt!=NULL);
1.377 + return checkconflict(psrc,ptgt);
1.378 +}
