1 /****************************************************************************
2  * Copyright (C) 2009 by Matteo Franchin                                    *
3  *                                                                          *
4  * This file is part of Box.                                                *
5  *                                                                          *
6  *   Box is free software: you can redistribute it and/or modify it         *
7  *   under the terms of the GNU Lesser General Public License as published  *
8  *   by the Free Software Foundation, either version 3 of the License, or   *
9  *   (at your option) any later version.                                    *
10  *                                                                          *
11  *   Box is distributed in the hope that it will be useful,                 *
12  *   but WITHOUT ANY WARRANTY; without even the implied warranty of         *
13  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the          *
14  *   GNU Lesser General Public License for more details.                    *
15  *                                                                          *
16  *   You should have received a copy of the GNU Lesser General Public       *
17  *   License along with Box.  If not, see <http://www.gnu.org/licenses/>.   *
18  ****************************************************************************/
19 
20 /**
21  * @file ast.h
22  * @brief Abstract syntax tree related functionality.
23  *
24  * A nice description...
25  */
26 
27 #ifndef _AST_H
28 #  define _AST_H
29 
30 #  include <stdio.h>
31 #  include <stdlib.h>
32 
33 #  include <box/types.h>
34 #  include <box/srcpos.h>
35 
36 #  define AST_MAX_NUM_SUBNODES 4
37 
38 typedef struct __ASTNode ASTNode;
39 
40 /** Possible types of nodes in the AST */
41 typedef enum {
42   ASTNODETYPE_ERROR,
43   ASTNODETYPE_TYPENAME,
44   ASTNODETYPE_TYPETAG,
45   ASTNODETYPE_SUBTYPE,
46   ASTNODETYPE_INSTANCE,
47   ASTNODETYPE_BOX,
48   ASTNODETYPE_STATEMENT,
49   ASTNODETYPE_CONST,
50   ASTNODETYPE_STRING,
51   ASTNODETYPE_VAR,
52   ASTNODETYPE_IGNORE,
53   ASTNODETYPE_UNOP,
54   ASTNODETYPE_BINOP,
55   ASTNODETYPE_MEMBER,
56   ASTNODETYPE_STRUC,
57   ASTNODETYPE_ARRAYGET,
58   ASTNODETYPE_MEMBERGET,
59   ASTNODETYPE_RAISE,
60   ASTNODETYPE_SELFGET,
61   ASTNODETYPE_SUBTYPEBLD,
62   ASTNODETYPE_PROCDEF,
63   ASTNODETYPE_TYPEDEF,
64   ASTNODETYPE_STRUCTYPE,
65   ASTNODETYPE_MEMBERTYPE,
66   ASTNODETYPE_RAISETYPE,
67   ASTNODETYPE_SPECTYPE
68 
69 } ASTNodeType;
70 
71 /**Separator between statements */
72 typedef enum {ASTSEP_VOID, ASTSEP_PAUSE} ASTSep;
73 
74 /** Integer number which identifies the scope of a variable or a type */
75 typedef int ASTScope;
76 
77 /** Type of constants */
78 typedef enum {
79   ASTCONSTTYPE_CHAR,
80   ASTCONSTTYPE_INT,
81   ASTCONSTTYPE_REAL
82 } ASTConstType;
83 
84 /** Union large enough to contain a value of any constant type */
85 typedef union {
86   BoxChar c;
87   BoxInt  i;
88   BoxReal r;
89 } ASTConst;
90 
91 /** Unary operators */
92 typedef enum {
93   ASTUNOP_PLUS,
94   ASTUNOP_NEG,
95   ASTUNOP_LINC,
96   ASTUNOP_LDEC,
97   ASTUNOP_RINC,
98   ASTUNOP_RDEC,
99   ASTUNOP_NOT,
100   ASTUNOP_BNOT
101 } ASTUnOp;
102 
103 #define ASTUNOP__NUM_OPS (ASTUNOP_BNOT + 1)
104 
105 /** Binary operators */
106 typedef enum {
107   ASTBINOP_ADD=0,
108   ASTBINOP_SUB,
109   ASTBINOP_MUL,
110   ASTBINOP_DIV,
111   ASTBINOP_REM,
112   ASTBINOP_POW,
113   ASTBINOP_SHL,
114   ASTBINOP_SHR,
115   ASTBINOP_EQ,
116   ASTBINOP_NE,
117   ASTBINOP_LT,
118   ASTBINOP_LE,
119   ASTBINOP_GT,
120   ASTBINOP_GE,
121   ASTBINOP_BAND,
122   ASTBINOP_BXOR,
123   ASTBINOP_BOR,
124   ASTBINOP_LAND,
125   ASTBINOP_LOR,
126   ASTBINOP_ASSIGN,
127   ASTBINOP_APLUS,
128   ASTBINOP_AMINUS,
129   ASTBINOP_ATIMES,
130   ASTBINOP_AREM,
131   ASTBINOP_ADIV,
132   ASTBINOP_ASHL,
133   ASTBINOP_ASHR,
134   ASTBINOP_ABAND,
135   ASTBINOP_ABXOR,
136   ASTBINOP_ABOR
137 } ASTBinOp;
138 
139 #define ASTBINOP__NUM_OPS (ASTBINOP_ABOR + 1)
140 
141 /** Integer indicating the self level: 0 --> $, 1 --> $$, 2 --> $$$, etc. */
142 typedef BoxInt ASTSelfLevel;
143 
144 /* Each of the following structures corresponds to a possible node in the AST
145    and contains the characteristics attribute for that node type.
146  */
147 
148 /** Node for a type name */
149 typedef struct {
150   char    *name;
151   ASTNode *scope;
152 } ASTNodeTypeName;
153 
154 /** Node for a special type */
155 typedef struct {
156   BoxTypeId  type;
157 } ASTNodeTypeTag;
158 
159 /** Node for a subtype */
160 typedef struct {
161   char    *name;
162   ASTNode *parent;
163 } ASTNodeSubtype;
164 
165 /** Node for instantiation. E.g. in ``x = Type'' this node captures has
166  * ``Type'' as a child and indicates that a new instance of that type should
167  * be created.
168  */
169 typedef struct {
170   ASTNode    *type;
171 } ASTNodeInstance;
172 
173 /** Node for a Box: which is a list of statements */
174 typedef struct {
175   ASTNode    *parent;
176   ASTNode    *first_statement;
177   ASTNode    *last_statement;
178   BoxSrcName *file_names;     /**< Names of all the files involved */
179 } ASTNodeBox;
180 
181 /** Node for a statement */
182 typedef struct {
183   ASTNode *target;
184   ASTNode *next_statement;
185   ASTSep  sep;
186 } ASTNodeStatement;
187 
188 /** Node for a constant expression */
189 typedef struct {
190   ASTConstType type;
191   ASTConst     value;
192 } ASTNodeConst;
193 
194 /** Node for a string */
195 typedef struct {
196   char    *str;
197 } ASTNodeString;
198 
199 /** Node for a variable */
200 typedef struct {
201   char    *name;
202   ASTNode *scope;
203 } ASTNodeVar;
204 
205 /** Node for removal of ignore attribute */
206 typedef struct {
207   ASTNode *expr;
208   int     ignore;
209 } ASTNodeIgnore;
210 
211 /** Node for a unary operation */
212 typedef struct {
213   ASTUnOp  operation;
214   ASTNode  *expr;
215 } ASTNodeUnOp;
216 
217 /** Node for a binary operation */
218 typedef struct {
219   ASTBinOp operation;
220   ASTNode  *left;
221   ASTNode  *right;
222 } ASTNodeBinOp;
223 
224 /** Node for one structure member */
225 typedef struct {
226   char     *name;
227   ASTNode  *expr,
228            *next;
229 } ASTNodeMember;
230 
231 /** Node for a structure */
232 typedef struct {
233   ASTNode  *first_member;
234   ASTNode  *last_member;
235 } ASTNodeStruc;
236 
237 /** Node for an array */
238 typedef struct {
239   ASTNode  *array;
240   ASTNode  *index;
241 } ASTNodeArrayGet;
242 
243 /** Node for an array */
244 typedef struct {
245   ASTNode  *struc;
246   char     *member;
247 } ASTNodeMemberGet;
248 
249 /** Node for the raise operation */
250 typedef struct {
251   ASTNode  *expr;
252 } ASTNodeRaise;
253 
254 /** Node for subtype building */
255 typedef struct {
256   ASTNode  *parent;
257   char     *subtype;
258 } ASTNodeSubtypeBld;
259 
260 /** Node for $, $$, $$$, etc. */
261 typedef struct {
262   ASTSelfLevel
263            level;
264 } ASTNodeSelfGet;
265 
266 /** Node for procedure definition/declaration */
267 typedef struct {
268   ASTNode     *child_type,
269               *parent_type,
270               *c_name,
271               *implem;
272   BoxCombType combine;
273 } ASTNodeProcDef;
274 
275 /** Node for type definition */
276 typedef struct {
277   ASTNode  *name,
278            *src_type;
279 } ASTNodeTypeDef;
280 
281 /** Node for structure type definition */
282 typedef struct {
283   ASTNode  *first_member,
284            *last_member;
285 } ASTNodeStrucType;
286 
287 /** Node for member definition in structure types */
288 typedef struct {
289   char     *name;
290   ASTNode  *type,
291            *next;
292 } ASTNodeMemberType;
293 
294 /** Node for type raising */
295 typedef struct {
296   ASTNode  *type;
297 } ASTNodeRaiseType;
298 
299 /** Node for species type definition */
300 typedef struct {
301   ASTNode  *first_member,
302            *last_member;
303 } ASTNodeSpecType;
304 
305 /** Node finaliser (used only for few nodes) */
306 typedef void (*ASTNodeFinaliser)(ASTNode *node);
307 
308 /** Structure describing one node in the AST */
309 struct __ASTNode {
310   ASTNodeType         type;      /**< Node type */
311   ASTNodeFinaliser    finaliser; /**< Destructor for node */
312   BoxSrc              src;       /**< Position in the source*/
313   /* ^^^ this last entry doubles the size of ASTNode
314    *     (from 24 bytes to 48 on 32 bit machine)
315    *     We should use linear positions!
316    */
317   union {
318     ASTNodeTypeName   typenm;
319     ASTNodeTypeTag    typetag;
320     ASTNodeSubtype    subtype;
321     ASTNodeInstance   instance;
322     ASTNodeBox        box;
323     ASTNodeStatement  statement;
324     ASTNodeConst      constant;
325     ASTNodeString     string;
326     ASTNodeVar        var;
327     ASTNodeIgnore     ignore;
328     ASTNodeUnOp       un_op;
329     ASTNodeBinOp      bin_op;
330     ASTNodeMember     member;
331     ASTNodeStruc      struc;
332     ASTNodeArrayGet   array_get;
333     ASTNodeMemberGet  member_get;
334     ASTNodeRaise      raise;
335     ASTNodeSubtypeBld subtype_bld;
336     ASTNodeSelfGet    self_get;
337     ASTNodeProcDef    proc_def;
338     ASTNodeTypeDef    type_def;
339     ASTNodeStrucType  struc_type;
340     ASTNodeMemberType member_type;
341     ASTNodeRaiseType  raise_type;
342     ASTNodeSpecType   spec_type;
343   } attr;
344 };
345 
346 typedef ASTNode *ASTNodePtr;
347 
348 /** Used to define members of structure and species types */
349 typedef struct {
350   ASTNode *type; /**< Type of the member (NULL, if not present) */
351   char    *name; /**< Name of the member (NULL, if not present) */
352 } ASTTypeMemb;
353 
354 int ASTNode_Get_Subnodes(ASTNode *node,
355                          ASTNode **subnodes[AST_MAX_NUM_SUBNODES]);
356 
357 const char *ASTNodeType_To_Str(ASTNodeType t);
358 
359 /** Return the string representation of the unary operator passed as
360  * argument.
361  */
362 const char *ASTUnOp_To_String(ASTUnOp op);
363 
364 /** Return the string representation of the binary operator passed as
365  * argument.
366  */
367 const char *ASTBinOp_To_String(ASTBinOp op);
368 
369 /** Returns 1 if the given operator is a "right" unary operator,
370  * meaning that it returs its operand before modifying it.
371  */
372 int ASTUnOp_Is_Right(ASTUnOp op);
373 
374 ASTNode *ASTNode_New(ASTNodeType t);
375 void ASTNode_Destroy(ASTNode *node);
376 void ASTNode_Set_Error(ASTNode *node);
377 void ASTNode_Print(FILE *out, ASTNode *node);
378 
379 ASTNode *ASTNodeError_New(void);
380 ASTNode *ASTNodeTypeName_New(const char *name, size_t name_len);
381 ASTNode *ASTNodeTypeTag_New(BoxTypeId value);
382 ASTNode *ASTNodeSubtype_New(ASTNode *parent_type, const char *name);
383 ASTNode *ASTNodeStatement_New(ASTNode *target);
384 ASTNode *ASTNodeSep_New(ASTSep sep);
385 ASTNode *ASTNodeInstance_New(ASTNode *type);
386 ASTNode *ASTNodeBox_New(ASTNode *type, ASTNode *first_statement);
387 ASTNode *ASTNodeBox_Add_Statement(ASTNode *box, ASTNode *statement);
388 ASTNode *ASTNodeBox_Add_Sep(ASTNode *box, ASTSep sep);
389 ASTNode *ASTNodeBox_Set_Parent(ASTNode *box, ASTNode *parent);
390 ASTNode *ASTNodeConst_New(ASTConstType t, ASTConst c);
391 ASTNode *ASTNodeString_New(const char *str, size_t str_len);
392 ASTNode *ASTNodeString_Concat(ASTNode *str1, ASTNode *str2);
393 ASTNode *ASTNodeVar_New(const char *name, size_t name_len);
394 ASTNode *ASTNodeIgnore_New(ASTNode *expr, int do_ignore);
395 ASTNode *ASTNodeUnOp_New(ASTUnOp op, ASTNode *expr);
396 ASTNode *ASTNodeBinOp_New(ASTBinOp op, ASTNode *left, ASTNode *right);
397 ASTNode *ASTNodeMember_New(const char *name, ASTNode *expr);
398 ASTNode *ASTNodeStruc_New(const char *first_name, ASTNode *first_expr);
399 ASTNode *ASTNodeStruc_Add_Member(ASTNode *struc,
400                                  const char *this_name, ASTNode *this_expr);
401 ASTNode *ASTNodeArrayGet_New(ASTNode *array, ASTNode *index);
402 ASTNode *ASTNodeMemberGet_New(ASTNode *struc,
403                               const char *member, int member_len);
404 ASTNode *ASTNodeRaise_New(ASTNode *expr);
405 ASTNode *ASTNodeSubtype_Build(ASTNode *parent, const char *subtype);
406 ASTNode *ASTNodeSelfGet_New(BoxInt level);
407 ASTNode *ASTNodeProcDef_New(ASTNode *child_type, BoxCombType combine,
408                             ASTNode *parent_type);
409 ASTNode *ASTNodeProcDef_Set(ASTNode *proc_def, ASTNode *c_name,
410                             ASTNode *implem);
411 ASTNode *ASTNodeTypeDef_New(ASTNode *name, ASTNode *src_type);
412 ASTNode *ASTNodeStrucType_New(ASTTypeMemb *first_member);
413 ASTNode *ASTNodeStrucType_Add_Member(ASTNode *struc_type,
414                                      ASTTypeMemb *member);
415 ASTNode *ASTNodeSpecType_New(ASTNode *first_type, ASTNode *second_type);
416 ASTNode *ASTNodeSpecType_Add_Member(ASTNode *species, ASTNode *memb);
417 ASTNode *ASTNodeRaiseType_New(ASTNode *type);
418 
419 #endif /* _AST_H */
420