updated ChangeLog
[swftools.git] / lib / xml.c
1 /* xml.c
2    Lightweight and fast xml parser.
3
4    Part of the swftools package.
5    
6    Copyright (c) 2010 Matthias Kramm <kramm@quiss.org> 
7  
8    This program is free software; you can redistribute it and/or modify
9    it under the terms of the GNU General Public License as published by
10    the Free Software Foundation; either version 2 of the License, or
11    (at your option) any later version.
12
13    This program is distributed in the hope that it will be useful,
14    but WITHOUT ANY WARRANTY; without even the implied warranty of
15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16    GNU General Public License for more details.
17
18    You should have received a copy of the GNU General Public License
19    along with this program; if not, write to the Free Software
20    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
21
22 #include <stdio.h>
23 #include <stdlib.h>
24 #include <memory.h>
25 #include <assert.h>
26 #include "xml.h"
27
28 /*
29 group: 0=data 1=whitespace 2='"' 3='<' 4='>' 5='&' 6=';' 7='?' 8='/' 9='=' 10='!' 11=EOF
30 */
31
32 static int group[256] =
33 {
34 // 00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f
35 //                            \t \n       \r
36    13, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0,
37 // 10 11 12 13 14 15 16 17 18 19 1a 1b 1c 1d 1e 1f
38 //
39    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
40 // 20 21 22 23 24 25 26 27 28 29 2a 2b 2c 2d 2e 2f
41 //    !  "  #  $  %  &  '  (  )  *  +  ,  -  .  /
42    1,10, 2, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 8,
43 // 30 31 32 33 34 35 36 37 38 39 3a 3b 3c 3d 3e 3f
44 // 0  1  2  3  4  5  6  7  8  9  :  ;  <  =  >  ?
45    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 3, 9, 4, 7,
46 // 40 41 42 43 44 45 46 47 48 49 4a 4b 4c 4d 4e 4f
47 // @  A  B  C  D  E  F  G  H  I  J  K  L  M  N  O
48    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
49 // 50 51 52 53 54 55 56 57 58 59 5a 5b 5c 5d 5e 5f
50 // P  Q  R  S  T  U  V  W  X  Y  Z  [  \  ]  ^  _
51    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,11, 0,12, 0, 0,
52 // 60 61 62 63 64 65 66 67 68 69 6a 6b 6c 6d 6e 6f
53 // `  a  b  c  d  e  f  g  h  i  j  k  l  m  n  o
54    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
55 // 70 71 72 73 74 75 76 77 78 79 7a 7b 7c 7d 7e 7f
56 // p  q  r  s  t  u  v  w  x  y  z  {  |  }  ~
57    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
58 // 80 81 82 83 84 85 86 87 88 89 8a 8b 8c 8d 8e 8f
59 //
60    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
61 // 90 91 92 93 94 95 96 97 98 99 9a 9b 9c 9d 9e 9f
62 //
63    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
64 // a0 a1 a2 a3 a4 a5 a6 a7 a8 a9 aa ab ac ad ae af
65 //
66    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
67 // b0 b1 b2 b3 b4 b5 b6 b7 b8 b9 ba bb bc bd be bf
68 //
69    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
70 // c0 c1 c2 c3 c4 c5 c6 c7 c8 c9 ca cb cc cd ce cf
71 //
72    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
73 // d0 d1 d2 d3 d4 d5 d6 d7 d8 d9 da db dc dd de df
74 //
75    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
76 // e0 e1 e2 e3 e4 e5 e6 e7 e8 e9 ea eb ec ed ee ef
77 //
78    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
79 // f0 f1 f2 f3 f4 f5 f6 f7 f8 f9 fa fb fc fd fe ff
80 //
81    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
82 };
83
84 static const char*errors[]=
85 {
86   0,
87 #define E1 -0x41
88  /*E1*/"xml file must start with <?",
89 #define E2 -0x42
90  /*E2*/"<,; or & not allowed inside tags",
91 #define E3 -0x43
92  /*E3*/"syntax error",
93 #define E4 -0x44
94  /*E4*/"internal error",
95 #define E5 -0x45
96  /*E5*/"attribute definition without =\"",
97 };
98
99 static int new_state[][16]=
100 {        /*  dt ws  "  <  >  &  ;  ?  /  =  !  [  ]   - EOB*/
101  /*  0 */{   E1, 0,E1, 1,E1,E1,E1,E1,E1,E1,E3,E1,E1,-63}, // .<
102  /*  1 */{   E1,E1,E1,E1,E1,E1,E1, 9,E1,E1,E3,E1,E1,-63}, // <.?
103  /*  2 */{   -3, 2,E3,E2,E2,E2,E2,E2,12,E2,16,E2,E2,-63}, // <.
104  /*  3 */{   E3,E3,E3,E3,-1,E3,E3,E3,E3,E1,E3,E3,E3,-63}, // < /.>
105  /*  4 */{   E3,E3,E3,E3,-2,E3,E3,E3,E3,E1,E1,E3,E3,-63}, // < .>
106  /*  5 */{    5, 5, 5,-4, 5, 5, 5, 5, 5, 5, 5,E3,E3,-63}, // da.ta
107  /*  6 */{    6,-7,E3,E2,-6,E2,E2,E3,-9,E3,E3,E3,E3,-63}, // <na.me
108  /*  7 */{   -8, 7,E3,E2,-2,E2,E2, 7, 3,E3,E3,E3,E3,-63}, // <name .
109  /*  8 */{    8,-12,E3,E2,E3,E2,E2,E3,E3,-10,E3,E3,E3,-63}, // att.r
110  /*  9 */{    9, 7,E3,E3,E3,E3,E3,E3,E3,E3,E3,E3,E3,-63}, // <?x.ml
111  /* 10 */{   E5,10,-11,E5,E5,E5,E5,E5,E5,E5,E3,E3,E3,-63},// attr=."
112  /* 11 */{   11,11,-5 ,11,11,11,11,11,11,11,E3,E3,E3,-63},// attr="va.l
113  /* 12 */{  -13,12,E3,E3,E3,E3,E3,E3,E3,E3,E3,E3,E3,-63}, // </ . >
114  /* 13 */{  13,-14,E3,E3,-16,E3,E3,E3,E3,E3,E3,E3,E3,-63},// </ na.me>
115  /* 14 */{   E3,14,E3,E3,-15,E3,E3,E3,E3,E3,E3,E3,E3,-63},// </ name. >
116  /* 15 */{   E3,15,E3,E2,E3,E3,E3,E3,E3,10,E3,E3,E3,-63}, // attr .=
117  /* 16 */{   E3,E3,E3,E2,E3,E3,E3,E3,E3,E3,E3,17,E3,-63}, // <!.[CDATA[ ]]>
118  /* 17 */{   17,E3,E3,E3,E3,E3,E3,E3,E3,E3,E3,18,E3,-63}, // <![C.DATA[ ]]>
119  /* 18 */{   18,18,18,18,18,18,18,18,18,18,18,18,19,-63}, // <![CDATA[ . ]]>
120  /* 19 */{   18,18,18,18,-20,18,18,18,18,18,18,18,19,-63}, // <![CDATA[ ].]>
121  /* 20 */{0,0,0,0,0,0,0,0,0,0,0,-63},
122  /* 21 */{0,0,0,0,0,0,0,0,0,0,0,-63},
123  /* 22 */{0,0,0,0,0,0,0,0,0,0,0,-63},
124  /* 23 */{0,0,0,0,0,0,0,0,0,0,0,-63},
125  /* 24 */{0,0,0,0,0,0,0,0,0,0,0,-63},
126 };
127
128 typedef struct _tag_stack {
129     const char*name;
130     struct _tag_stack*prev;
131 } tag_stack_t;
132
133 typedef struct _stringstate {
134     char*current;
135     int len;
136     char*start;
137     char*result;
138 } stringstate_t;
139
140 static void stringstate_start(stringstate_t*s, char*buffer, int pos)
141 {
142     assert(!s->current);
143     s->start = &buffer[pos];
144     s->len = 0;
145     s->result = 0;
146 }
147 static void stringstate_save(stringstate_t*s, char*buffer, int pos)
148 {
149     if(!s->start) 
150         return;
151     int add = &buffer[pos] - s->start;
152     if(!s->current) {
153         assert(!s->len);
154         s->current = malloc(add+1);
155         memcpy(s->current, s->start, add);
156     } else {
157         s->current = realloc(s->current, s->len + add + 1);
158         memcpy(s->current+s->len, s->start, add);
159     }
160     s->len += add;
161     s->current[s->len] = 0;
162     s->start = buffer;
163 }
164 static void stringstate_finish(stringstate_t*s, char*buffer, int pos)
165 {
166     stringstate_save(s, buffer, pos);
167     s->result = s->current;
168     s->current = 0;
169     s->start = 0;
170 }
171 static void stringstate_clear(stringstate_t*s)
172 {
173     if(s->result) free(s->result);
174     if(s->current) free(s->current);
175     memset(s, 0, sizeof(stringstate_t));
176 }
177 static xmlattribute_t*attributes_reverse(xmlattribute_t*attr)
178 {
179     xmlattribute_t*prev = 0;
180     while(attr) {
181         xmlattribute_t*next = attr->next;
182         attr->next = prev;
183         prev = attr;
184         attr = next;
185     }
186     return prev;
187 }
188
189 static void attributes_free(xmlattribute_t*attributes)
190 {
191     while(attributes) {
192         xmlattribute_t*next = attributes->next;
193         free((void*)attributes->name);
194         free((void*)attributes->value);
195         free(attributes);
196         attributes = next;
197     }
198 }
199
200 int xml_parse(reader_t*reader, xmlconsumer_t*out)
201 {
202     char buffer[4097];
203     int old = 0, state = 0;
204     char first=1;
205     tag_stack_t*stack = 0;
206
207     stringstate_t tagname = {0,0,0,0};
208     stringstate_t attr_name = {0,0,0,0};
209     stringstate_t attr_value = {0,0,0,0};
210     stringstate_t data = {0,0,0,0};
211     xmlattribute_t*attributes = 0;
212
213     while(1) {
214         int num = reader->read(reader, buffer, 4096);
215         if(!num) break;
216         buffer[num]=0;
217         int pos = 0;
218         while(pos<num) {
219             /*printf("%c, state %d->%d\n", 
220                     buffer[pos], state, new_state[state][group[buffer[pos]]]);*/
221
222             /* inner loop */
223             do {
224                 state = new_state[old=state][group[(unsigned char)buffer[pos++]]];
225             } while(state>=0);
226
227             switch(state) {
228                 tag_stack_t*st;
229                 xmlattribute_t*a;
230                 case -63: // end of buffer
231                     if(pos!=num+1) {
232                         // we could backtrace, but the spec says this is indeed illegal
233                         fprintf(stderr, "error: xml contains \\0 chars\n");
234                         return 0;
235                     }
236                     // undo
237                     pos = num;
238                     state = old;
239                 break;
240                 case -1: // self closing tag
241                     attributes = attributes_reverse(attributes);
242                     out->start_tag(out, tagname.result, attributes);
243                     out->end_tag(out, tagname.result);
244                     stringstate_clear(&tagname);
245                     attributes_free(attributes);attributes = 0;
246                     stringstate_start(&data, buffer, pos);
247                     state = 5;
248                 break;
249                 case -6: // after <tagname, at >
250                     stringstate_finish(&tagname, buffer, pos-1);
251                 // fallthrough
252                 case -2: // <tag >.
253                     st = malloc(sizeof(tag_stack_t));
254                     st->name = tagname.result;
255                     st->prev = stack;
256                     stack = st;
257                     attributes = attributes_reverse(attributes);
258                     if(!first) out->start_tag(out, tagname.result, attributes);
259                     attributes_free(attributes);attributes = 0;
260                     stringstate_start(&data, buffer, pos);
261                     state = 5;
262                 break;
263                 case -3: case -13: // after <, start of tag name
264                     first=0;
265                     stringstate_start(&tagname, buffer, pos-1);
266                     state = state==-3?6:13;
267                 break;
268                 case -14: // after </, end of tag name, begin of white space
269                     stringstate_finish(&tagname, buffer, pos-1);
270                     state = 14;
271                     break;
272                 case -16: // after </, at >, end of tag name 
273                     stringstate_finish(&tagname, buffer, pos-1);
274                 // fallthrough
275                 case -15: // after </, at >
276                     out->end_tag(out, tagname.result);
277                     stringstate_clear(&tagname);
278                     stringstate_start(&data, buffer, pos);
279                     state = 5;
280                 break;
281                 case -4: // end of data
282                     stringstate_finish(&data, buffer, pos-1);
283                     if(!first) out->data(out, data.result, data.len);
284                     stringstate_clear(&data);
285                     state = 2;
286                 break;
287                 case -7: // after <, at whitespace, end of tag name
288                     stringstate_finish(&tagname, buffer, pos-1);
289                     state = 7;
290                 break;
291                 case -8: // inside tag, start of attribute name
292                     stringstate_start(&attr_name, buffer, pos-1);
293                     state = 8;
294                 break;
295                 case -9:
296                     stringstate_finish(&tagname, buffer, pos-1);
297                     state = 3;  
298                 break;
299                 case -12: // end of attribute name, at ws
300                     stringstate_finish(&attr_name, buffer, pos-1);
301                     state = 15;
302                 break;
303                 case -10: // end of attribute name, at =
304                     stringstate_finish(&attr_name, buffer, pos-1);
305                     state = 10;
306                 break;
307                 case -11: // start of attribute value
308                     stringstate_start(&attr_value, buffer, pos);
309                     state = 11;
310                 break;
311                 case -5: // end of attribute value
312                     stringstate_finish(&attr_value, buffer, pos-1);
313                     a = malloc(sizeof(xmlattribute_t));
314                     a->name = attr_name.result;attr_name.result=0;
315                     a->value = attr_value.result;attr_value.result=0;
316                     a->next = attributes;
317                     attributes = a;
318                     state = 7;
319                 break;
320                 case -20:
321                     state = 5;
322                 break;
323                 default:
324                     if(-state&0x40) {
325                         fprintf(stderr, "%s (state %d, char '%c')\n", errors[(-state)&0x3f], old, buffer[pos-1]);
326                         return 0;
327                     } else {
328                         fprintf(stderr, "internal error: no action %d\n", state);
329                     }
330                     return 0;
331                 break;
332             }
333         }
334         stringstate_save(&tagname, buffer, pos);
335         stringstate_save(&attr_name, buffer, pos);
336         stringstate_save(&attr_value, buffer, pos);
337         stringstate_save(&data, buffer, pos);
338     }
339
340     /* note: any of these except data *has* to be empty for a well formed xml */
341     stringstate_clear(&tagname);
342     stringstate_clear(&attr_name);
343     stringstate_clear(&attr_value);
344     stringstate_clear(&data);
345
346     while(stack) {
347         tag_stack_t*next = stack->prev;
348         free((void*)stack->name);
349         free(stack);
350         stack = next;
351     }
352     return 1;
353 }
354
355 #ifdef MAIN
356 void my_start_tag(xmlconsumer_t*c, char*name, xmlattribute_t*attr)
357 {
358     printf("<%s", name);
359     for(;attr;attr=attr->next) {
360         printf(" %s=\"%s\"", attr->name, attr->value);
361     }
362     printf(">");
363 }
364 void my_data(xmlconsumer_t*c, char*data, int len)
365 {
366     printf("%s", data);
367 }
368 void my_end_tag(xmlconsumer_t*c, char*name)
369 {
370     printf("</%s>", name);
371 }
372 int main()
373 {
374     xmlconsumer_t c = {my_start_tag, my_data, my_end_tag, 0};
375
376     reader_t r;
377     reader_init_filereader2(&r, "test.xml");
378     xml_parse(&r, &c);
379     r.dealloc(&r);
380     printf("\n");
381 }
382 #endif