Scippy

SCIP

Solving Constraint Integer Programs

xmlparse.c
Go to the documentation of this file.
1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
2 /* */
3 /* This file is part of the program and library */
4 /* SCIP --- Solving Constraint Integer Programs */
5 /* */
6 /* Copyright (C) 2002-2019 Konrad-Zuse-Zentrum */
7 /* fuer Informationstechnik Berlin */
8 /* */
9 /* SCIP is distributed under the terms of the ZIB Academic License. */
10 /* */
11 /* You should have received a copy of the ZIB Academic License */
12 /* along with SCIP; see the file COPYING. If not visit scip.zib.de. */
13 /* */
14 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
15 
16 /**@file xmldef.h
17  * @brief declarations for XML parsing
18  * @author Thorsten Koch
19  * @author Marc Pfetsch
20  *
21  * If SPEC_LIKE_SPACE_HANDLING is not defined, all LF,CR will be changed into spaces and from a
22  * sequence of spaces only one will be used.
23  *
24  * @todo Implement possibility to avoid the construction of parsing information for certain tags
25  * (and their children). For solution files this would avoid parsing the constraints section.
26  */
27 
28 /*---+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2*/
29 
30 #include <blockmemshell/memory.h>
31 
32 #include "xml.h"
33 #include "xmldef.h"
34 #include "scip/misc.h"
35 
36 
37 #include <sys/types.h>
38 #ifdef SCIP_WITH_ZLIB
39 #if defined(_WIN32) || defined(_WIN64)
40 #define R_OK _A_RDONLY
41 #define access _access
42 #include <io.h>
43 #else
44 #include <unistd.h>
45 #endif
46 #endif
47 #include <stdio.h>
48 #include <stdlib.h>
49 #include <assert.h>
50 #include <ctype.h>
51 #include <string.h>
52 
53 
54 #define NAME_EXT_SIZE 128
55 #define ATTR_EXT_SIZE 4096
56 #define DATA_EXT_SIZE 4096
57 #define LINE_BUF_SIZE 8192
58 
59 #define xmlError(a, b) xmlErrmsg(a, b, FALSE, __FILE__, __LINE__)
60 
61 
62 /* forward declarations */
63 typedef struct parse_stack_struct PSTACK;
64 typedef struct parse_pos_struct PPOS;
65 
66 /** state of the parser */
68 {
74 };
75 typedef enum parse_state_enum PSTATE;
76 
77 /** Stack as a (singly) linked list. The top element is the current node. */
79 {
82 };
83 
84 /** Store the current position in the file and the state of the parser. */
86 {
87  const char* filename;
89  char buf[LINE_BUF_SIZE];
90  int pos;
91  int lineno;
92  int nextsym;
93  int lastsym;
96 };
97 
98 
99 /** output error message with corresponding line and position */
100 static void xmlErrmsg(
101  PPOS* ppos,
102  const char* msg,
103  XML_Bool msg_only,
104  const char* file,
105  int line
106  )
107 {
108 #ifndef NDEBUG
109  int ret;
110  assert( ppos != NULL );
111 
112  if ( ! msg_only )
113  {
114  ret = fprintf(stderr, "%s(%d) Error in file %s line %d\n", file, line, ppos->filename, ppos->lineno);
115  assert(ret >= 0);
116 
117  ret = fprintf(stderr, "%s", ppos->buf);
118  assert(ret >= 0);
119 
120  if ( strchr(ppos->buf, '\n') == NULL )
121  {
122  int retc;
123 
124  retc = fputc('\n', stderr);
125  assert(retc != EOF);
126  }
127 
128  ret = fprintf(stderr, "%*s\n", ppos->pos, "^");
129  assert(ret >= 0);
130  }
131  ret = fprintf(stderr, "%s\n\n", msg);
132  assert(ret >= 0);
133 
134 #else
135 
136  if ( ! msg_only )
137  {
138  (void) fprintf(stderr, "%s(%d) Error in file %s line %d\n", file, line, ppos->filename, ppos->lineno);
139 
140  (void) fprintf(stderr, "%s", ppos->buf);
141 
142  if ( strchr(ppos->buf, '\n') == NULL )
143  {
144  (void) fputc('\n', stderr);
145  }
146 
147  (void) fprintf(stderr, "%*s\n", ppos->pos, "^");
148  }
149  (void) fprintf(stderr, "%s\n\n", msg);
150 #endif
151 }
152 
153 
154 /** Push new element on the parse stack.
155  *
156  * TRUE if it worked, FAILURE otherwise.
157  */
158 static
160  PPOS* ppos,
161  XML_NODE* node
162  )
163 {
164  PSTACK* p;
165 
166  assert(ppos != NULL);
167  assert(node != NULL);
168 
169  debugMessage("Pushing %s\n", node->name);
170 
172  assert(p != NULL);
173 
174  p->node = node;
175  p->next = ppos->top;
176  ppos->top = p;
177 
178  return TRUE;
179 }
180 
181 /** returns top element on stack (which has to be present) */
183  const PPOS* ppos
184  )
185 {
186  assert(ppos != NULL);
187  assert(ppos->top != NULL);
188 
189  return ppos->top->node;
190 }
191 
192 /** remove top element from stack and deletes it
193  *
194  * TRUE if ok, FALSE otherwise
195  */
196 static
198  PPOS* ppos /**< input stream position */
199  )
200 {
201  PSTACK* p;
202  XML_Bool result;
203 
204  assert(ppos != NULL);
205 
206  if ( ppos->top == NULL )
207  {
208  xmlError(ppos, "Stack underflow");
209  result = FALSE;
210  }
211  else
212  {
213  result = TRUE;
214  p = ppos->top;
215  ppos->top = p->next;
216 
217  debugMessage("Poping %s\n", p->node->name);
218  BMSfreeMemory(&p);
219  }
220  return result;
221 }
222 
223 /** remove complete stack */
224 static
226  PPOS* ppos
227  )
228 {
229  assert(ppos != NULL);
230 
231  while ( ppos->top != NULL )
232  (void) popPstack(ppos);
233 }
234 
235 /** Returns the next character from the input buffer and fills the buffer if it is empty (similar to fgetc()). */
236 static
237 int mygetc(
238  PPOS* ppos
239  )
240 {
241  assert(ppos != NULL);
242  assert(ppos->fp != NULL);
243  assert(ppos->pos < LINE_BUF_SIZE);
244 
245  if ( ppos->buf[ppos->pos] == '\0' )
246  {
247 #ifdef SCIP_DISABLED_CODE
248  /* the low level function gzread/fread used below seem to be faster */
249  if ( NULL == FGETS(ppos->buf, sizeof(ppos->buf), ppos->fp) )
250  return EOF;
251 #else
252  size_t len = (size_t) FREAD(ppos->buf, sizeof(ppos->buf) - 1, ppos->fp); /*lint !e571 !e747*/
253 
254  if( len == 0 || len > sizeof(ppos->buf) - 1 )
255  return EOF;
256 
257  ppos->buf[len] = '\0';
258 #endif
259  ppos->pos = 0;
260  }
261  return (unsigned char)ppos->buf[ppos->pos++];
262 }
263 
264 
265 #ifdef SPEC_LIKE_SPACE_HANDLING
266 /** Read input from fp_in.
267  *
268  * If there is a LF, CR, CR/LF, or LF/CR it returns exactly on LF. Also counts the number of
269  * characters.
270  */
271 static
272 int getsymbol(
273  PPOS* ppos
274  )
275 {
276  int c;
277 
278  assert(ppos != NULL);
279 
280  if ( ppos->nextsym == 0 )
281  c = mygetc(ppos);
282  else
283  {
284  c = ppos->nextsym;
285  ppos->nextsym = 0;
286  }
287  assert(ppos->nextsym == 0);
288 
289  if (((c == '\n') && (ppos->lastsym == '\r')) || ((c == '\r') && (ppos->lastsym == '\n')))
290  c = mygetc(ppos);
291 
292  ppos->lastsym = c;
293 
294  if ( c == '\r' )
295  c = '\n';
296 
297  if ( c == '\n' )
298  ++ppos->lineno;
299 
300  return c;
301 }
302 #else
303 /** Read input from fp_in (variant).
304  *
305  * Here we convert all LF or CR into SPACE and return maximally one SPACE after the other.
306  *
307  * @note This function counts lines differently. On systems that have only one '\\r' as line feed
308  * (MAC) it does not count correctly.
309  */
310 static
312  PPOS* ppos
313  )
314 {
315  int c;
316 
317  assert(ppos != NULL);
318 
319  do
320  {
321  if ( ppos->nextsym == 0 )
322  c = mygetc(ppos);
323  else
324  {
325  c = ppos->nextsym;
326  ppos->nextsym = 0;
327  }
328  assert(ppos->nextsym == 0);
329 
330  if ( c == '\n' )
331  ++ppos->lineno;
332 
333  if ((c == '\n') || (c == '\r'))
334  c = ' ';
335  } while((c == ' ') && (ppos->lastsym == c));
336 
337  ppos->lastsym = c;
338 
339  debugMessage("[%c]\n", c);
340 
341  return c;
342 }
343 #endif
344 
345 /** Reinserts a character into the input stream */
346 static
348  PPOS* ppos,
349  int c
350  )
351 {
352  assert(ppos != NULL);
353  assert(ppos->nextsym == 0);
354 
355  ppos->nextsym = c;
356 }
357 
358 /** Skip all spaces and return the next non-space character or EOF */
359 static
361  PPOS* ppos
362  )
363 {
364  int c;
365 
366  assert(ppos != NULL);
367 
368  do
369  {
370  c = getsymbol(ppos);
371  }
372  while(isspace(c));
373 
374  return c;
375 }
376 
377 /** Get name of a TAG or attribute from the input stream.
378  *
379  * Either it returns a pointer to allocated memory which contains the name or it returns NULL if
380  * there is some error.
381  */
382 static
383 char* getName(
384  PPOS* ppos
385  )
386 {
387  char* name = NULL;
388  size_t size = 0;
389  size_t len = 0;
390  int c;
391 
392  assert(ppos != NULL);
393 
394  c = getsymbol(ppos);
395 
396  if ( ! isalpha(c) && (c != '_') && (c != ':') )
397  {
398  xmlError(ppos, "Name starting with illegal charater");
399  return NULL;
400  }
401 
402  /* The following is wrong: Here almost all characters that we casted to unicode are feasible */
403  while ( isalnum(c) || (c == '_') || (c == ':') || (c == '.') || (c == '-') )
404  {
405  if ( len + 1 >= size )
406  {
407  size += NAME_EXT_SIZE;
408 
409  if ( name == NULL )
410  {
411  ALLOC_ABORT( BMSallocMemoryArray(&name, size) );
412  }
413  else
414  {
415  ALLOC_ABORT( BMSreallocMemoryArray(&name, size) );
416  }
417  }
418  assert(name != NULL);
419  assert(size > len);
420 
421  name[len++] = (char)c;
422 
423  c = getsymbol(ppos);
424  }
425  if ( c != EOF )
426  ungetsymbol(ppos, c);
427 
428  assert(name != NULL);
429 
430  if ( len == 0 )
431  {
432  BMSfreeMemoryArray(&name);
433  name = NULL;
434  }
435  else
436  name[len] = '\0';
437 
438  return name;
439 }
440 
441 /** Read the value of an attribute from the input stream.
442  *
443  * The value has to be between two " or ' (the other character is then valid as well). The function
444  * returns a pointer to allocated memory containing the value or it returns NULL in case of an
445  * error.
446  */
447 static
449  PPOS* ppos
450  )
451 {
452  char* attr = NULL;
453  int c;
454  int stop;
455  size_t len = 0;
456  size_t size = 0;
457 
458  assert(ppos != NULL);
459 
460  /* The following is not allowed according to the specification (the value has to be directly
461  * after the equation sign). */
462  c = skipSpace(ppos);
463 
464  if ( (c != '"') && (c != '\'') )
465  {
466  xmlError(ppos, "Atribute value does not start with \" or \'");
467  return NULL;
468  }
469  stop = c;
470 
471  for(;;)
472  {
473  if ( len == size )
474  {
475  size += ATTR_EXT_SIZE;
476 
477  if ( attr == NULL )
478  {
479  ALLOC_ABORT( BMSallocMemoryArray(&attr, size) );
480  }
481  else
482  {
483  ALLOC_ABORT( BMSreallocMemoryArray(&attr, size) );
484  }
485  }
486  assert(attr != NULL);
487  assert(size > len);
488 
489  c = getsymbol(ppos);
490 
491  if ( (c == stop) || (c == EOF) )
492  break;
493 
494  attr[len++] = (char)c;
495  }
496 
497  if ( c != EOF )
498  attr[len] = '\0';
499  else
500  {
501  BMSfreeMemoryArray(&attr);
502  attr = NULL;
503  }
504  return attr;
505 }
506 
507 /** Skip comment
508  *
509  * Return FALSE if an error occurs.
510  */
511 static
513  PPOS* ppos
514  )
515 {
516  XML_Bool result = TRUE;
517  int c;
518  int state = 0;
519 
520  assert(ppos != NULL);
521 
522  for(;;)
523  {
524  c = getsymbol(ppos);
525 
526  if ( c == EOF )
527  break;
528 
529  if ( (c == '>') && (state >= 2) )
530  break;
531 
532  state = (c == '-') ? state + 1 : 0;
533  }
534  if ( c == EOF )
535  {
536  xmlError(ppos, "Unexpected EOF in comment");
537  result = FALSE;
538  }
539  return result;
540 }
541 
542 /** Handles a CDATA section.
543  *
544  * Returns a pointer to allocated memory containing the data of this section or NULL in case of an
545  * error.
546  */
547 static
548 char* doCdata(
549  PPOS* ppos
550  )
551 {
552  char* data = NULL;
553  size_t size = 0;
554  size_t len = 0;
555  int state = 0;
556  int c;
557 
558  assert(ppos != NULL);
559 
560  for(;;)
561  {
562  c = getsymbol(ppos);
563 
564  if ( c == EOF )
565  break;
566 
567  if ( c == ']' )
568  state++;
569  else
570  if ( (c == '>') && (state >= 2) )
571  break;
572  else
573  state = 0;
574 
575  if ( len == size )
576  {
577  size += DATA_EXT_SIZE;
578 
579  if ( data == NULL )
580  {
581  ALLOC_ABORT( BMSallocMemoryArray(&data, size) );
582  }
583  else
584  {
585  ALLOC_ABORT( BMSreallocMemoryArray(&data, size) );
586  }
587  }
588  assert(data != NULL);
589  assert(size > len);
590 
591  data[len++] = (char)c;
592  }
593  assert(data != NULL);
594 
595  /*lint --e{527}*/
596  if ( c != EOF )
597  {
598  assert(len >= 2);
599  assert(data != NULL);
600 
601  data[len - 2] = '\0'; /*lint !e413*/
602  }
603  else
604  {
605  BMSfreeMemoryArray(&data);
606  data = NULL;
607  xmlError(ppos, "Unexpected EOF in CDATA");
608  }
609  return data;
610 }
611 
612 /** Handle processing instructions (skipping) */
613 static
614 void handlePi(
615  PPOS* ppos
616  )
617 {
618  int c;
619 
620  assert(ppos != NULL);
621  assert(ppos->state == XML_STATE_BEFORE);
622 
623  do
624  {
625  c = getsymbol(ppos);
626  }
627  while ( (c != EOF) && (c != '>') );
628 
629  if ( c != EOF )
630  ppos->state = XML_STATE_PCDATA;
631  else
632  {
633  xmlError(ppos, "Unexpected EOF in PI");
634  ppos->state = XML_STATE_ERROR;
635  }
636 }
637 
638 /** Handles declarations that start with a <!.
639  *
640  * This includes comments. Does currenlty not work very well, because of DTDs.
641  */
642 static
644  PPOS* ppos
645  )
646 {
647  enum XmlSection
648  {
649  IS_COMMENT,
650  IS_ATTLIST,
651  IS_DOCTYPE,
652  IS_ELEMENT,
653  IS_ENTITY,
654  IS_NOTATION,
655  IS_CDATA
656  };
657  typedef enum XmlSection XMLSECTION;
658 
659  static struct
660  {
661  const char* name;
662  XMLSECTION what;
663  } key[] =
664  {
665  { "--", IS_COMMENT },
666  { "ATTLIST", IS_ATTLIST },
667  { "DOCTYPE", IS_DOCTYPE },
668  { "ELEMENT", IS_ELEMENT },
669  { "ENTITY", IS_ENTITY },
670  { "NOTATION", IS_NOTATION },
671  { "[CDATA[", IS_CDATA }
672  };
673  XML_NODE* node;
674  char* data;
675  int c;
676  int k = 0;
677  int beg = 0;
678  int end;
679 
680  assert(ppos != NULL);
681  assert(ppos->state == XML_STATE_BEFORE);
682 
683  end = (int) (sizeof(key) / sizeof(key[0])) - 1;
684  do
685  {
686  c = getsymbol(ppos);
687 
688  for(; (beg <= end) && (c != key[beg].name[k]); beg++)
689  ;
690  for(; (end >= beg) && (c != key[end].name[k]); end--)
691  ;
692  k++;
693  } while(beg < end);
694 
695  if ( beg != end )
696  {
697  xmlError(ppos, "Unknown declaration");
698 
699  while ( (c != EOF) && (c != '>') )
700  c = getsymbol(ppos);
701  }
702  else
703  {
704  assert(beg == end);
705  assert(beg < (int)(sizeof(key) / sizeof(*key)));
706 
707  switch(key[beg].what)
708  {
709  case IS_COMMENT :
710  if ( ! doComment(ppos) )
711  ppos->state = XML_STATE_ERROR;
712  break;
713  case IS_CDATA :
714  if ( (data = doCdata(ppos)) == NULL )
715  ppos->state = XML_STATE_ERROR;
716  else
717  {
718  if ( NULL == (node = xmlNewNode("#CDATA", ppos->lineno)) )
719  {
720  xmlError(ppos, "Can't create new node");
721  ppos->state = XML_STATE_ERROR;
722  }
723  else
724  {
725  BMSduplicateMemoryArray(&node->data, data, strlen(data)+1);
726  BMSfreeMemoryArray(&data);
727  xmlAppendChild(topPstack(ppos), node);
728  }
729  }
730  break;
731  case IS_ATTLIST :
732  case IS_ELEMENT :
733  case IS_NOTATION :
734  case IS_ENTITY :
735  case IS_DOCTYPE :
736  break;
737  default :
738  abort();
739  }
740  }
741 }
742 
743 /** Handle end tag */
744 static
746  PPOS* ppos
747  )
748 {
749  char* name;
750  int c;
751 
752  assert(ppos != NULL);
753 
754  if ( (name = getName(ppos)) == NULL )
755  xmlError(ppos, "Missing name in endtag");
756  else
757  {
758  c = skipSpace(ppos);
759 
760  if ( c != '>' )
761  {
762  xmlError(ppos, "Missing '>' in endtag");
763  ppos->state = XML_STATE_ERROR;
764  }
765  else
766  {
767  if ( strcmp(name, topPstack(ppos)->name) )
768  {
769  xmlError(ppos, "Name of endtag does not match starttag");
770  ppos->state = XML_STATE_ERROR;
771  }
772  else
773  {
774  if ( popPstack(ppos) )
775  ppos->state = XML_STATE_PCDATA;
776  else
777  ppos->state = XML_STATE_ERROR;
778  }
779  }
780 
781  BMSfreeMemoryArray(&name);
782  }
783 }
784 
785 /** Handle start tag */
786 static
788  PPOS* ppos
789  )
790 {
791  XML_NODE* node;
792  char* name;
793 
794  assert(ppos != NULL);
795 
796  name = getName(ppos);
797  if ( name == NULL )
798  {
799  xmlError(ppos, "Missing name in tagstart");
800  ppos->state = XML_STATE_ERROR;
801  }
802  else
803  {
804  node = xmlNewNode(name, ppos->lineno);
805  if ( node == NULL )
806  {
807  xmlError(ppos, "Can't create new node");
808  ppos->state = XML_STATE_ERROR;
809  }
810  else
811  {
812  xmlAppendChild(topPstack(ppos), node);
813 
814  if ( pushPstack(ppos, node) )
815  ppos->state = XML_STATE_IN_TAG;
816  else
817  ppos->state = XML_STATE_ERROR;
818  }
819  BMSfreeMemoryArray(&name);
820  }
821 }
822 
823 /** Checks for next tag */
824 static
826  PPOS* ppos /**< input stream position */
827  )
828 {
829  int c;
830 
831  assert(ppos != NULL);
832  assert(ppos->state == XML_STATE_BEFORE);
833 
834  c = skipSpace(ppos);
835 
836  if ( c != '<' )
837  {
838  xmlError(ppos, "Expecting '<'");
839  ppos->state = XML_STATE_ERROR;
840  }
841  else
842  {
843  c = getsymbol(ppos);
844 
845  switch(c)
846  {
847  case EOF :
848  xmlError(ppos, "Unexpected EOF");
849  ppos->state = XML_STATE_ERROR;
850  break;
851  case '!' :
852  handleDecl(ppos);
853  break;
854  case '?' :
855  handlePi(ppos);
856  break;
857  case '/' :
858  handleEndtag(ppos);
859  break;
860  default :
861  ungetsymbol(ppos, c);
862  handleStarttag(ppos);
863  break;
864  }
865  }
866 }
867 
868 /** Process tag */
869 static
871  PPOS* ppos /**< input stream position */
872  )
873 {
874  XML_ATTR* attr;
875  int c;
876  XML_Bool empty = FALSE;
877  char* name;
878  char* value;
879 
880  assert(ppos != NULL);
881  assert(ppos->state == XML_STATE_IN_TAG);
882 
883  c = skipSpace(ppos);
884 
885  if ( (c == '/') || (c == '>') || (c == EOF) )
886  {
887  if ( c == '/' )
888  {
889  empty = TRUE;
890  c = getsymbol(ppos);
891  }
892 
893  if ( c == EOF )
894  {
895  xmlError(ppos, "Unexpected EOF while in a tag");
896  ppos->state = XML_STATE_ERROR;
897  }
898 
899  if ( c == '>' )
900  {
901  ppos->state = XML_STATE_PCDATA;
902 
903  if (empty && ! popPstack(ppos))
904  ppos->state = XML_STATE_ERROR;
905  }
906  else
907  {
908  xmlError(ppos, "Expected tag end marker '>'");
909  ppos->state = XML_STATE_ERROR;
910  }
911  }
912  else
913  {
914  ungetsymbol(ppos, c);
915 
916  name = getName(ppos);
917  if ( name == NULL )
918  {
919  xmlError(ppos, "No name for attribute");
920  ppos->state = XML_STATE_ERROR;
921  }
922  else
923  {
924  c = skipSpace(ppos);
925 
926  if ( (c != '=') || ((value = getAttrval(ppos)) == NULL) )
927  {
928  xmlError(ppos, "Missing attribute value");
929  ppos->state = XML_STATE_ERROR;
930  BMSfreeMemoryArray(&name);
931  }
932  else
933  {
934  attr = xmlNewAttr(name, value);
935  if ( attr == NULL )
936  {
937  xmlError(ppos, "Can't create new attribute");
938  ppos->state = XML_STATE_ERROR;
939  }
940  else
941  {
942  xmlAddAttr(topPstack(ppos), attr);
943  }
944  BMSfreeMemoryArray(&name);
945  BMSfreeMemoryArray(&value);
946  }
947  }
948  }
949 }
950 
951 /* Handles PCDATA */
952 static
954  PPOS* ppos /**< input stream position */
955  )
956 {
957  XML_NODE* node;
958  char* data = NULL;
959  size_t size = 0;
960  size_t len = 0;
961  int c;
962 
963  assert(ppos != NULL);
964  assert(ppos->state == XML_STATE_PCDATA);
965 
966 #ifndef SPEC_LIKE_SPACE_HANDLING
967  c = skipSpace(ppos);
968  if ( c != EOF )
969  ungetsymbol(ppos, c);
970 #endif
971  c = getsymbol(ppos);
972 
973  while ( (c != EOF) && (c != '<') )
974  {
975  if ( len + 1 >= size ) /* leave space for terminating '\0' */
976  {
977  size += DATA_EXT_SIZE;
978 
979  if ( data == NULL )
980  {
981  ALLOC_ABORT( BMSallocMemoryArray(&data, size) );
982  }
983  else
984  {
985  ALLOC_ABORT( BMSreallocMemoryArray(&data, size) );
986  }
987  }
988  assert(data != NULL);
989  assert(size > len + 1);
990 
991  data[len++] = (char)c;
992 
993  c = getsymbol(ppos);
994  }
995  if ( data == NULL )
996  {
997  if ( c == EOF )
998  ppos->state = XML_STATE_EOF;
999  else
1000  {
1001  assert(c == '<');
1002  ppos->state = XML_STATE_BEFORE;
1003  ungetsymbol(ppos, c);
1004  }
1005  }
1006  else
1007  {
1008  assert(len < size);
1009  data[len] = '\0';
1010 
1011  if ( c == EOF )
1012  ppos->state = XML_STATE_ERROR;
1013  else
1014  {
1015  ungetsymbol(ppos, c);
1016 
1017  node = xmlNewNode("#PCDATA", ppos->lineno);
1018  if ( node == NULL )
1019  {
1020  xmlError(ppos, "Can't create new node");
1021  ppos->state = XML_STATE_ERROR;
1022  }
1023  else
1024  {
1025  BMSduplicateMemoryArray(&node->data, data, strlen(data)+1);
1026  xmlAppendChild(topPstack(ppos), node);
1027  ppos->state = XML_STATE_BEFORE;
1028  }
1029  }
1030 
1031  BMSfreeMemoryArray(&data);
1032  }
1033 }
1034 
1035 /** Parse input stream */
1036 static
1038  PPOS* ppos /**< input stream position */
1039  )
1040 {
1041  XML_Bool ok = TRUE;
1042 
1043  while (ok)
1044  {
1045  debugMessage("state=%d\n", ppos->state);
1046 
1047  switch (ppos->state)
1048  {
1049  case XML_STATE_BEFORE :
1050  procBefore(ppos);
1051  break;
1052  case XML_STATE_IN_TAG :
1053  procInTag(ppos);
1054  break;
1055  case XML_STATE_PCDATA :
1056  procPcdata(ppos);
1057  break;
1058  case XML_STATE_EOF :
1059  ok = FALSE;
1060  break;
1061  case XML_STATE_ERROR :
1062  ok = FALSE;
1063  break;
1064  default :
1065  xmlError(ppos, "Internal Error, illegal state");
1066  ok = FALSE;
1067  }
1068  }
1069  return (ppos->state == XML_STATE_EOF);
1070 }
1071 
1072 /** Parse file */
1074  const char* filename /**< XML file name */
1075  )
1076 {
1077  PPOS ppos;
1078  XML_NODE* node = NULL;
1079  XML_ATTR* attr;
1080  XML_Bool result = FALSE;
1081  char* myfilename;
1082  size_t filenamelen;
1083 
1084  /* allocate space and copy filename (possibly modified below) in two steps in order to satisfy valgrind */
1085  assert( filename != NULL );
1086  filenamelen = strlen(filename);
1087  if ( BMSallocMemoryArray(&myfilename, filenamelen + 5) == NULL )
1088  return NULL;
1089  BMScopyMemoryArray(myfilename, filename, filenamelen + 1);
1090 
1091 #ifdef SCIP_WITH_ZLIB
1092  if ( access(filename, R_OK) != 0 )
1093  {
1094  strcat(myfilename, ".gz");
1095 
1096  /* If .gz also does not work, revert to the old name
1097  * to get a better error message.
1098  */
1099  if ( access(myfilename, R_OK) != 0 )
1100  (void)SCIPstrncpy(myfilename, filename, (int)filenamelen + 5);
1101  }
1102 #endif
1103  ppos.fp = FOPEN(myfilename, "r");
1104  if ( ppos.fp == NULL )
1105  perror(myfilename);
1106  else
1107  {
1108  ppos.filename = myfilename;
1109  ppos.buf[0] = '\0';
1110  ppos.pos = 0;
1111  ppos.lineno = 1;
1112  ppos.nextsym = 0;
1113  ppos.lastsym = 0;
1114  ppos.state = XML_STATE_BEFORE;
1115  ppos.top = NULL;
1116 
1117  node = xmlNewNode("#ROOT", ppos.lineno);
1118  if ( node == NULL )
1119  {
1120  xmlError(&ppos, "Can't create new node");
1121  }
1122  else
1123  {
1124  attr = xmlNewAttr("filename", myfilename);
1125  if ( attr == NULL )
1126  xmlError(&ppos, "Can't create new attribute");
1127  else
1128  {
1129  xmlAddAttr(node, attr);
1130 
1131  /* push root node on stack and start to process */
1132  if ( pushPstack(&ppos, node) )
1133  {
1134  result = xmlParse(&ppos);
1135 
1136  clearPstack(&ppos);
1137  }
1138  }
1139  }
1140 
1141  if ( ! result && (node != NULL) )
1142  {
1143  xmlErrmsg(&ppos, "Parsing error, processing stopped", TRUE, __FILE__, __LINE__);
1144  xmlFreeNode(node);
1145  node = NULL;
1146  }
1147  if ( FCLOSE(ppos.fp) )
1148  perror(myfilename);
1149  }
1150  BMSfreeMemoryArray(&myfilename);
1151 
1152  return node;
1153 }
1154 
1155 
1156 
1157 
1158 
1159 
1160 /*----------------------------------------------------------------------------------------------*/
1161 
1162 
1163 /** create new node */
1165  const char* name,
1166  int lineno
1167  )
1168 {
1169  XML_NODE* n = NULL;
1170 
1171  assert(name != NULL);
1172 
1173  if ( BMSallocMemory(&n) != NULL )
1174  {
1175  BMSclearMemory(n);
1176  BMSduplicateMemoryArray(&n->name, name, strlen(name)+1);
1177  n->lineno = lineno;
1178  }
1179  return n;
1180 }
1181 
1182 /** create new attribute */
1184  const char* name,
1185  const char* value
1186  )
1187 {
1188  XML_ATTR* a = NULL;
1189 
1190  assert(name != NULL);
1191  assert(value != NULL);
1192 
1193  if ( BMSallocMemory(&a) != NULL )
1194  {
1195  BMSclearMemory(a);
1196  BMSduplicateMemoryArray(&a->name, name, strlen(name)+1);
1197  BMSduplicateMemoryArray(&a->value, value, strlen(value)+1);
1198  }
1199  return a;
1200 }
1201 
1202 /** add attribute */
1204  XML_NODE* n,
1205  XML_ATTR* a
1206  )
1207 {
1208  assert(n != NULL);
1209  assert(a != NULL);
1210 
1211  a->next = n->attrlist;
1212  n->attrlist = a;
1213 }
1214 
1215 /** append child node */
1217  XML_NODE* parent,
1218  XML_NODE* child
1219  )
1220 {
1221  assert(parent != NULL);
1222  assert(child != NULL);
1223 
1224  child->parent = parent;
1225  child->prevsibl = parent->lastchild;
1226  child->nextsibl = NULL;
1227  parent->lastchild = child;
1228 
1229  if ( child->prevsibl != NULL )
1230  child->prevsibl->nextsibl = child;
1231 
1232  if ( parent->firstchild == NULL )
1233  parent->firstchild = child;
1234 }
1235 
1236 /** free attribute */
1237 static
1239  XML_ATTR* attr
1240  )
1241 {
1242  XML_ATTR* a;
1243 
1244  /* Note: use an iterative implementation instead of a recursive one; the latter is much slower for large instances
1245  * and might overflow the heap. */
1246  a = attr;
1247  while (a != NULL)
1248  {
1249  XML_ATTR* b;
1250  b = a->next;
1251 
1252  assert(a->name != NULL);
1253  assert(a->value != NULL);
1254 
1255  BMSfreeMemoryArray(&a->name);
1256  BMSfreeMemoryArray(&a->value);
1257  BMSfreeMemory(&a);
1258  a = b;
1259  }
1260 }
1261 
1262 /** free node */
1264  XML_NODE* node
1265  )
1266 {
1267  XML_NODE* n;
1268 
1269  if ( node == NULL )
1270  return;
1271 
1272  /* Free data from back to front (because free is faster this way). */
1273  /* Note: use an iterative implementation instead of a recursive one; the latter is much slower for large instances
1274  * and might overflow the heap. */
1275  n = node->lastchild;
1276  while ( n != NULL )
1277  {
1278  XML_NODE* m;
1279  m = n->prevsibl;
1280  xmlFreeNode(n);
1281  n = m;
1282  }
1283 
1284  xmlFreeAttr(node->attrlist);
1285 
1286  if ( node->data != NULL )
1287  {
1288  BMSfreeMemoryArray(&node->data);
1289  }
1290  assert(node->name != NULL);
1291 
1292  BMSfreeMemoryArray(&node->name);
1293  BMSfreeMemory(&node);
1294 }
1295 
1296 /** output node */
1298  const XML_NODE* root
1299  )
1300 {
1301  const XML_NODE* n;
1302  const XML_ATTR* a;
1303 
1304  assert(root != NULL);
1305 
1306  for (n = root; n != NULL; n = n->nextsibl)
1307  {
1308  infoMessage("Name: %s\n", n->name);
1309  infoMessage("Line: %d\n", n->lineno);
1310  infoMessage("Data: %s\n", (n->data != NULL) ? n->data : "***");
1311 
1312  for (a = n->attrlist; a != NULL; a = a->next)
1313  infoMessage("Attr: %s = [%s]\n", a->name, a->value);
1314 
1315  if ( n->firstchild != NULL )
1316  {
1317  infoMessage("->\n");
1318  xmlShowNode(n->firstchild);
1319  infoMessage("<-\n");
1320  }
1321  }
1322 }
1323 
1324 /** get attribute value */
1325 const char* xmlGetAttrval(
1326  const XML_NODE* node,
1327  const char* name
1328  )
1329 {
1330  XML_ATTR* a;
1331 
1332  assert(node != NULL);
1333  assert(name != NULL);
1334 
1335  for (a = node->attrlist; a != NULL; a = a->next)
1336  {
1337  if ( ! strcmp(name, a->name) )
1338  break;
1339  }
1340 
1341 #ifdef SCIP_DEBUG
1342  if (a == NULL)
1343  infoMessage("Error: Attribute %s in TAG <%s> not found\n", name, node->name);
1344 #endif
1345 
1346  return (a == NULL) ? NULL : a->value;
1347 }
1348 
1349 /** return first node */
1351  const XML_NODE* node,
1352  const char* name
1353  )
1354 {
1355  const XML_NODE* n;
1356 
1357  assert(node != NULL);
1358  assert(name != NULL);
1359 
1360  for (n = node; n != NULL; n = n->nextsibl)
1361  {
1362  if ( ! strcmp(name, n->name) )
1363  break;
1364  }
1365 
1366  return n;
1367 }
1368 
1369 /** return next node */
1371  const XML_NODE* node,
1372  const char* name
1373  )
1374 {
1375  assert(node != NULL);
1376  assert(name != NULL);
1377 
1378  return (node->nextsibl == NULL) ? NULL : xmlFirstNode(node->nextsibl, name);
1379 }
1380 
1381 /** find node */
1383  const XML_NODE* node,
1384  const char* name
1385  )
1386 {
1387  const XML_NODE* n;
1388  const XML_NODE* r;
1389 
1390  assert(node != NULL);
1391  assert(name != NULL);
1392 
1393  if ( ! strcmp(name, node->name) )
1394  return node;
1395 
1396  for (n = node->firstchild; n != NULL; n = n->nextsibl)
1397  {
1398  r = xmlFindNode(n, name);
1399  if ( r != NULL )
1400  return r;
1401  }
1402 
1403  return NULL;
1404 }
1405 
1406 /** find node with bound on the depth */
1408  const XML_NODE* node, /**< current node - use start node to begin */
1409  const char* name, /**< name of tag to search for */
1410  int depth, /**< current depth - start with 0 for root */
1411  int maxdepth /**< maximal depth */
1412  )
1413 {
1414  const XML_NODE* n;
1415  const XML_NODE* r;
1416 
1417  assert(node != NULL);
1418  assert(name != NULL);
1419 
1420  if ( ! strcmp(name, node->name) )
1421  return node;
1422 
1423  if ( depth < maxdepth )
1424  {
1425  for (n = node->firstchild; n != NULL; n = n->nextsibl)
1426  {
1427  r = xmlFindNodeMaxdepth(n, name, depth+1, maxdepth);
1428  if ( r != NULL )
1429  return r;
1430  }
1431  }
1432 
1433  return NULL;
1434 }
1435 
1436 /** return next sibling */
1438  const XML_NODE* node
1439  )
1440 {
1441  assert(node != NULL);
1442 
1443  return node->nextsibl;
1444 }
1445 
1446 /** return previous sibling */
1448  const XML_NODE* node
1449  )
1450 {
1451  assert(node != NULL);
1452 
1453  return node->prevsibl;
1454 }
1455 
1456 /** return first child */
1458  const XML_NODE* node
1459  )
1460 {
1461  assert(node != NULL);
1462 
1463  return node->firstchild;
1464 }
1465 
1466 /** return last child */
1468  const XML_NODE* node
1469  )
1470 {
1471  assert(node != NULL);
1472 
1473  return node->lastchild;
1474 }
1475 
1476 /** return name of node */
1477 const char* xmlGetName(
1478  const XML_NODE* node
1479  )
1480 {
1481  assert(node != NULL);
1482 
1483  return node->name;
1484 }
1485 
1486 /** get line number */
1488  const XML_NODE* node
1489  )
1490 {
1491  assert(node != NULL);
1492 
1493  return node->lineno;
1494 }
1495 
1496 /** get data */
1497 const char* xmlGetData(
1498  const XML_NODE* node
1499  )
1500 {
1501  assert(node != NULL);
1502 
1503  return node->data;
1504 }
1505 
1506 /** find PCDATA */
1507 const char* xmlFindPcdata(
1508  const XML_NODE* node,
1509  const char* name
1510  )
1511 {
1512  const XML_NODE* n;
1513 
1514  assert(node != NULL);
1515  assert(name != NULL);
1516 
1517  n = xmlFindNode(node, name);
1518  if ( n == NULL )
1519  return NULL;
1520 
1521  if ( ! strcmp(n->firstchild->name, "#PCDATA") )
1522  return n->firstchild->data;
1523 
1524  return NULL;
1525 }
#define XML_Bool
Definition: xmldef.h:33
#define NULL
Definition: def.h:253
#define LINE_BUF_SIZE
Definition: xmlparse.c:57
const XML_NODE * xmlFirstNode(const XML_NODE *node, const char *name)
Definition: xmlparse.c:1350
static void handleDecl(PPOS *ppos)
Definition: xmlparse.c:643
PSTACK * next
Definition: xmlparse.c:81
const char * xmlFindPcdata(const XML_NODE *node, const char *name)
Definition: xmlparse.c:1507
void xmlFreeNode(XML_NODE *node)
Definition: xmlparse.c:1263
#define FREAD(buf, len, fp)
Definition: xmldef.h:54
static int getsymbol(PPOS *ppos)
Definition: xmlparse.c:311
#define ALLOC_ABORT(x)
Definition: tclique_def.h:43
#define FCLOSE(fp)
Definition: xmldef.h:52
struct XML_ATTR_struct XML_ATTR
Definition: xml.h:32
static char * doCdata(PPOS *ppos)
Definition: xmlparse.c:548
static void xmlFreeAttr(XML_ATTR *attr)
Definition: xmlparse.c:1238
#define FALSE
Definition: def.h:73
XML_NODE * xmlNewNode(const char *name, int lineno)
Definition: xmlparse.c:1164
#define TRUE
Definition: def.h:72
const char * xmlGetName(const XML_NODE *node)
Definition: xmlparse.c:1477
#define BMSallocMemoryArray(ptr, num)
Definition: memory.h:113
#define DATA_EXT_SIZE
Definition: xmlparse.c:56
enum parse_state_enum PSTATE
Definition: xmlparse.c:75
#define ATTR_EXT_SIZE
Definition: xmlparse.c:55
XML_ATTR * xmlNewAttr(const char *name, const char *value)
Definition: xmlparse.c:1183
#define BMSfreeMemory(ptr)
Definition: memory.h:135
void xmlShowNode(const XML_NODE *root)
Definition: xmlparse.c:1297
static void procInTag(PPOS *ppos)
Definition: xmlparse.c:870
const char * xmlGetData(const XML_NODE *node)
Definition: xmlparse.c:1497
#define debugMessage
Definition: tclique_def.h:73
static void xmlErrmsg(PPOS *ppos, const char *msg, XML_Bool msg_only, const char *file, int line)
Definition: xmlparse.c:100
static void procPcdata(PPOS *ppos)
Definition: xmlparse.c:953
static int mygetc(PPOS *ppos)
Definition: xmlparse.c:237
PSTACK * top
Definition: xmlparse.c:95
static void ungetsymbol(PPOS *ppos, int c)
Definition: xmlparse.c:347
int SCIPstrncpy(char *t, const char *s, int size)
Definition: misc.c:10306
#define BMSfreeMemoryArray(ptr)
Definition: memory.h:137
parse_state_enum
Definition: xmlparse.c:67
static XML_Bool popPstack(PPOS *ppos)
Definition: xmlparse.c:197
struct XML_NODE_struct XML_NODE
Definition: xml.h:41
static XML_Bool doComment(PPOS *ppos)
Definition: xmlparse.c:512
#define ALLOC_FALSE(x)
Definition: tclique_def.h:55
internal miscellaneous methods
const XML_NODE * xmlFindNode(const XML_NODE *node, const char *name)
Definition: xmlparse.c:1382
const char * xmlGetAttrval(const XML_NODE *node, const char *name)
Definition: xmlparse.c:1325
Definition: grphload.c:88
const XML_NODE * xmlNextNode(const XML_NODE *node, const char *name)
Definition: xmlparse.c:1370
static XML_Bool xmlParse(PPOS *ppos)
Definition: xmlparse.c:1037
#define BMSduplicateMemoryArray(ptr, source, num)
Definition: memory.h:133
const XML_NODE * xmlFirstChild(const XML_NODE *node)
Definition: xmlparse.c:1457
XML_NODE * xmlProcess(const char *filename)
Definition: xmlparse.c:1073
static int skipSpace(PPOS *ppos)
Definition: xmlparse.c:360
static XML_NODE * topPstack(const PPOS *ppos)
Definition: xmlparse.c:182
static char * getAttrval(PPOS *ppos)
Definition: xmlparse.c:448
void xmlAddAttr(XML_NODE *n, XML_ATTR *a)
Definition: xmlparse.c:1203
#define FGETS(buf, len, fp)
Definition: xmldef.h:53
#define BMScopyMemoryArray(ptr, source, num)
Definition: memory.h:124
#define FOPEN(file, mode)
Definition: xmldef.h:51
#define infoMessage
Definition: tclique_def.h:79
#define FPTYPE
Definition: xmldef.h:55
#define xmlError(a, b)
Definition: xmlparse.c:59
#define BMSclearMemory(ptr)
Definition: memory.h:119
static char * getName(PPOS *ppos)
Definition: xmlparse.c:383
XML_NODE * node
Definition: xmlparse.c:80
SCIP_Real * r
Definition: circlepacking.c:50
SCIP_VAR ** b
Definition: circlepacking.c:56
const XML_NODE * xmlNextSibl(const XML_NODE *node)
Definition: xmlparse.c:1437
char buf[LINE_BUF_SIZE]
Definition: xmlparse.c:89
const char * filename
Definition: xmlparse.c:87
SCIP_VAR * a
Definition: circlepacking.c:57
static XML_Bool pushPstack(PPOS *ppos, XML_NODE *node)
Definition: xmlparse.c:159
#define BMSallocMemory(ptr)
Definition: memory.h:109
#define BMSreallocMemoryArray(ptr, num)
Definition: memory.h:117
declarations for XML parsing
#define NAME_EXT_SIZE
Definition: xmlparse.c:54
const XML_NODE * xmlPrevSibl(const XML_NODE *node)
Definition: xmlparse.c:1447
const XML_NODE * xmlLastChild(const XML_NODE *node)
Definition: xmlparse.c:1467
const XML_NODE * xmlFindNodeMaxdepth(const XML_NODE *node, const char *name, int depth, int maxdepth)
Definition: xmlparse.c:1407
static void handlePi(PPOS *ppos)
Definition: xmlparse.c:614
int xmlGetLine(const XML_NODE *node)
Definition: xmlparse.c:1487
void xmlAppendChild(XML_NODE *parent, XML_NODE *child)
Definition: xmlparse.c:1216
static void handleStarttag(PPOS *ppos)
Definition: xmlparse.c:787
PSTATE state
Definition: xmlparse.c:94
static void procBefore(PPOS *ppos)
Definition: xmlparse.c:825
static void handleEndtag(PPOS *ppos)
Definition: xmlparse.c:745
static void clearPstack(PPOS *ppos)
Definition: xmlparse.c:225
memory allocation routines
definitions for XML parsing