001/*
002 * Copyright 2006 - 2013
003 *     Stefan Balev     <stefan.balev@graphstream-project.org>
004 *     Julien Baudry    <julien.baudry@graphstream-project.org>
005 *     Antoine Dutot    <antoine.dutot@graphstream-project.org>
006 *     Yoann Pigné      <yoann.pigne@graphstream-project.org>
007 *     Guilhelm Savin   <guilhelm.savin@graphstream-project.org>
008 * 
009 * This file is part of GraphStream <http://graphstream-project.org>.
010 * 
011 * GraphStream is a library whose purpose is to handle static or dynamic
012 * graph, create them from scratch, file or any source and display them.
013 * 
014 * This program is free software distributed under the terms of two licenses, the
015 * CeCILL-C license that fits European law, and the GNU Lesser General Public
016 * License. You can  use, modify and/ or redistribute the software under the terms
017 * of the CeCILL-C license as circulated by CEA, CNRS and INRIA at the following
018 * URL <http://www.cecill.info> or under the terms of the GNU LGPL as published by
019 * the Free Software Foundation, either version 3 of the License, or (at your
020 * option) any later version.
021 * 
022 * This program is distributed in the hope that it will be useful, but WITHOUT ANY
023 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
024 * PARTICULAR PURPOSE.  See the GNU Lesser General Public License for more details.
025 * 
026 * You should have received a copy of the GNU Lesser General Public License
027 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
028 * 
029 * The fact that you are presently reading this means that you have had
030 * knowledge of the CeCILL-C and LGPL licenses and that you accept their terms.
031 */
032package org.graphstream.stream.file.dgs;
033
034import java.awt.Color;
035import java.io.IOException;
036import java.io.Reader;
037import java.util.HashMap;
038import java.util.LinkedList;
039
040import org.graphstream.graph.implementations.AbstractElement.AttributeChangeEvent;
041import org.graphstream.stream.SourceBase.ElementType;
042import org.graphstream.stream.file.FileSourceDGS;
043import org.graphstream.util.parser.ParseException;
044import org.graphstream.util.parser.Parser;
045
046// import org.graphstream.util.time.ISODateIO;
047
048public class DGSParser implements Parser {
049        static enum Token {
050                AN, CN, DN, AE, CE, DE, CG, ST, CL, TF, EOF
051        }
052
053        protected static final int BUFFER_SIZE = 4096;
054
055        public static final int ARRAY_OPEN = '{';
056        public static final int ARRAY_CLOSE = '}';
057
058        public static final int MAP_OPEN = '[';
059        public static final int MAP_CLOSE = ']';
060
061        Reader reader;
062        int line, column;
063        int bufferCapacity, bufferPosition;
064        char[] buffer;
065        int[] pushback;
066        int pushbackOffset;
067        FileSourceDGS dgs;
068        String sourceId;
069        Token lastDirective;
070
071        // ISODateIO dateIO;
072
073        public DGSParser(FileSourceDGS dgs, Reader reader) {
074                this.dgs = dgs;
075                this.reader = reader;
076                bufferCapacity = 0;
077                buffer = new char[BUFFER_SIZE];
078                pushback = new int[10];
079                pushbackOffset = -1;
080                this.sourceId = String.format("<DGS stream %x>", System.nanoTime());
081
082                // try {
083                // dateIO = new ISODateIO();
084                // } catch (Exception e) {
085                // e.printStackTrace();
086                // }
087        }
088
089        /*
090         * (non-Javadoc)
091         * 
092         * @see org.graphstream.util.parser.Parser#close()
093         */
094        public void close() throws IOException {
095                reader.close();
096        }
097
098        /*
099         * (non-Javadoc)
100         * 
101         * @see org.graphstream.util.parser.Parser#open()
102         */
103        public void open() throws IOException, ParseException {
104                header();
105        }
106
107        /*
108         * (non-Javadoc)
109         * 
110         * @see org.graphstream.util.parser.Parser#all()
111         */
112        public void all() throws IOException, ParseException {
113                header();
114
115                while (next())
116                        ;
117        }
118
119        protected int nextChar() throws IOException {
120                int c;
121
122                if (pushbackOffset >= 0)
123                        return pushback[pushbackOffset--];
124
125                if (bufferCapacity == 0 || bufferPosition >= bufferCapacity) {
126                        bufferCapacity = reader.read(buffer, 0, BUFFER_SIZE);
127                        bufferPosition = 0;
128                }
129
130                if (bufferCapacity <= 0)
131                        return -1;
132
133                c = buffer[bufferPosition++];
134
135                //
136                // Handle special EOL
137                // - LF
138                // - CR
139                // - CR+LF
140                //
141                if (c == '\r') {
142                        if (bufferPosition < bufferCapacity) {
143                                if (buffer[bufferPosition] == '\n')
144                                        bufferPosition++;
145                        } else {
146                                c = nextChar();
147
148                                if (c != '\n')
149                                        pushback(c);
150                        }
151
152                        c = '\n';
153                }
154
155                if (c == '\n') {
156                        line++;
157                        column = 0;
158                } else
159                        column++;
160
161                return c;
162        }
163
164        protected void pushback(int c) throws IOException {
165                if (c < 0)
166                        return;
167
168                if (pushbackOffset + 1 >= pushback.length)
169                        throw new IOException("pushback buffer overflow");
170
171                pushback[++pushbackOffset] = c;
172        }
173
174        protected void skipLine() throws IOException {
175                int c;
176
177                while ((c = nextChar()) != '\n' && c >= 0)
178                        ;
179        }
180
181        protected void skipWhitespaces() throws IOException {
182                int c;
183
184                while ((c = nextChar()) == ' ' || c == '\t')
185                        ;
186
187                pushback(c);
188        }
189
190        protected void header() throws IOException, ParseException {
191                int[] dgs = new int[6];
192
193                for (int i = 0; i < 6; i++)
194                        dgs[i] = nextChar();
195
196                if (dgs[0] != 'D' || dgs[1] != 'G' || dgs[2] != 'S')
197                        throw parseException(String.format(
198                                        "bad magic header, 'DGS' expected, got '%c%c%c'", dgs[0],
199                                        dgs[1], dgs[2]));
200
201                if (dgs[3] != '0' || dgs[4] != '0' || dgs[5] < '0' || dgs[5] > '5')
202                        throw parseException(String.format("bad version \"%c%c%c\"",
203                                        dgs[0], dgs[1], dgs[2]));
204
205                if (nextChar() != '\n')
206                        throw parseException("end-of-line is missing");
207
208                skipLine();
209        }
210
211        /*
212         * (non-Javadoc)
213         * 
214         * @see org.graphstream.util.parser.Parser#next()
215         */
216        public boolean next() throws IOException, ParseException {
217                int c;
218                String nodeId;
219                String edgeId, source, target;
220
221                lastDirective = directive();
222
223                switch (lastDirective) {
224                case AN:
225                        nodeId = id();
226                        dgs.sendNodeAdded(sourceId, nodeId);
227
228                        attributes(ElementType.NODE, nodeId);
229                        break;
230                case CN:
231                        nodeId = id();
232                        attributes(ElementType.NODE, nodeId);
233                        break;
234                case DN:
235                        nodeId = id();
236                        dgs.sendNodeRemoved(sourceId, nodeId);
237                        break;
238                case AE:
239                        edgeId = id();
240                        source = id();
241
242                        skipWhitespaces();
243                        c = nextChar();
244
245                        if (c != '<' && c != '>')
246                                pushback(c);
247
248                        target = id();
249
250                        switch (c) {
251                        case '>':
252                                dgs.sendEdgeAdded(sourceId, edgeId, source, target, true);
253                                break;
254                        case '<':
255                                dgs.sendEdgeAdded(sourceId, edgeId, target, source, true);
256                                break;
257                        default:
258                                dgs.sendEdgeAdded(sourceId, edgeId, source, target, false);
259                                break;
260                        }
261
262                        attributes(ElementType.EDGE, edgeId);
263                        break;
264                case CE:
265                        edgeId = id();
266                        attributes(ElementType.EDGE, edgeId);
267                        break;
268                case DE:
269                        edgeId = id();
270                        dgs.sendEdgeRemoved(sourceId, edgeId);
271                        break;
272                case CG:
273                        attributes(ElementType.GRAPH, null);
274                        break;
275                case ST:
276                        // TODO release 1.2 : read timestamp
277                        // Version for 1.2 :
278                        // --------------------------------
279                        // long step;
280                        // step = timestamp();
281                        // sendStepBegins(sourceId, ste);
282
283                        double step;
284
285                        step = Double.valueOf(id());
286                        dgs.sendStepBegins(sourceId, step);
287                        break;
288                case CL:
289                        dgs.sendGraphCleared(sourceId);
290                        break;
291                case TF:
292                        // TODO for release 1.2
293                        // String tf;
294                        // tf = string();
295
296                        // try {
297                        // dateIO.setFormat(tf);
298                        // } catch (Exception e) {
299                        // throw parseException("invalid time format \"%s\"", tf);
300                        // }
301
302                        break;
303                case EOF:
304                        return false;
305                }
306
307                skipWhitespaces();
308                c = nextChar();
309
310                if (c == '#') {
311                        skipLine();
312                        return true;
313                }
314
315                if (c < 0)
316                        return false;
317
318                if (c != '\n')
319                        throw parseException("eol expected, got '%c'", c);
320
321                return true;
322        }
323
324        public boolean nextStep() throws IOException, ParseException {
325                boolean r;
326                Token next;
327
328                do {
329                        r = next();
330                        next = directive();
331
332                        if (next != Token.EOF) {
333                                pushback(next.name().charAt(1));
334                                pushback(next.name().charAt(0));
335                        }
336                } while (next != Token.ST && next != Token.EOF);
337
338                return r;
339        }
340
341        protected void attributes(ElementType type, String id) throws IOException,
342                        ParseException {
343                int c;
344
345                skipWhitespaces();
346
347                while ((c = nextChar()) != '\n' && c != '#' && c >= 0) {
348                        pushback(c);
349                        attribute(type, id);
350                        skipWhitespaces();
351                }
352
353                pushback(c);
354        }
355
356        protected void attribute(ElementType type, String elementId)
357                        throws IOException, ParseException {
358                String key;
359                Object value = null;
360                int c;
361                AttributeChangeEvent ch = AttributeChangeEvent.CHANGE;
362
363                skipWhitespaces();
364                c = nextChar();
365
366                if (c == '+')
367                        ch = AttributeChangeEvent.ADD;
368                else if (c == '-')
369                        ch = AttributeChangeEvent.REMOVE;
370                else
371                        pushback(c);
372
373                key = id();
374
375                if (key == null)
376                        throw parseException("attribute key expected");
377
378                if (ch != AttributeChangeEvent.REMOVE) {
379
380                        skipWhitespaces();
381                        c = nextChar();
382
383                        if (c == '=' || c == ':') {
384                                skipWhitespaces();
385                                value = value(true);
386                        } else {
387                                value = Boolean.TRUE;
388                                pushback(c);
389                        }
390                }
391
392                dgs.sendAttributeChangedEvent(sourceId, elementId, type, key, ch, null,
393                                value);
394        }
395
396        protected Object value(boolean array) throws IOException, ParseException {
397                int c;
398                LinkedList<Object> l = null;
399                Object o;
400
401                do {
402                        skipWhitespaces();
403                        c = nextChar();
404                        pushback(c);
405
406                        switch (c) {
407                        case '\'':
408                        case '\"':
409                                o = string();
410                                break;
411                        case '#':
412                                o = color();
413                                break;
414                        case ARRAY_OPEN:
415                                //
416                                // Skip ARRAY_OPEN
417                                nextChar();
418                                //
419
420                                skipWhitespaces();
421                                o = value(true);
422                                skipWhitespaces();
423
424                                //
425                                // Check if next char is ARRAY_CLOSE
426                                if (nextChar() != ARRAY_CLOSE)
427                                        throw parseException("'%c' expected", ARRAY_CLOSE);
428                                //
429
430                                if (!o.getClass().isArray())
431                                        o = new Object[] { o };
432
433                                break;
434                        case MAP_OPEN:
435                                o = map();
436                                break;
437                        default: {
438                                String word = id();
439
440                                if (word == null)
441                                        throw parseException("missing value");
442
443                                if ((c >= '0' && c <= '9') || c == '-') {
444                                        try {
445                                                if (word.indexOf('.') > 0)
446                                                        o = Double.valueOf(word);
447                                                else {
448                                                        try {
449                                                                o = Integer.valueOf(word);
450                                                        } catch (NumberFormatException e) {
451                                                                o = Long.valueOf(word);
452                                                        }
453                                                }
454                                        } catch (NumberFormatException e) {
455                                                throw parseException("invalid number format '%s'", word);
456                                        }
457                                } else {
458                                        if (word.equalsIgnoreCase("true"))
459                                                o = Boolean.TRUE;
460                                        else if (word.equalsIgnoreCase("false"))
461                                                o = Boolean.FALSE;
462                                        else
463                                                o = word;
464                                }
465
466                                break;
467                        }
468                        }
469
470                        c = nextChar();
471
472                        if (l == null && array && c == ',') {
473                                l = new LinkedList<Object>();
474                                l.add(o);
475                        } else if (l != null)
476                                l.add(o);
477                } while (array && c == ',');
478
479                pushback(c);
480
481                if (l == null)
482                        return o;
483
484                return l.toArray();
485        }
486
487        protected Color color() throws IOException, ParseException {
488                int c;
489                int r, g, b, a;
490                StringBuilder hexa = new StringBuilder();
491
492                c = nextChar();
493
494                if (c != '#')
495                        throw parseException("'#' expected");
496
497                for (int i = 0; i < 6; i++) {
498                        c = nextChar();
499
500                        if ((c >= 0 && c <= '9') || (c >= 'a' && c <= 'f')
501                                        || (c >= 'A' && c <= 'F'))
502                                hexa.appendCodePoint(c);
503                        else
504                                throw parseException("hexadecimal value expected");
505                }
506
507                r = Integer.parseInt(hexa.substring(0, 2), 16);
508                g = Integer.parseInt(hexa.substring(2, 4), 16);
509                b = Integer.parseInt(hexa.substring(4, 6), 16);
510
511                c = nextChar();
512
513                if ((c >= '0' && c <= '9') || (c >= 'a' && c <= 'f')
514                                || (c >= 'A' && c <= 'F')) {
515                        hexa.appendCodePoint(c);
516
517                        c = nextChar();
518
519                        if ((c >= 0 && c <= '9') || (c >= 'a' && c <= 'f')
520                                        || (c >= 'A' && c <= 'F'))
521                                hexa.appendCodePoint(c);
522                        else
523                                throw parseException("hexadecimal value expected");
524
525                        a = Integer.parseInt(hexa.substring(6, 8), 16);
526                } else {
527                        a = 255;
528                        pushback(c);
529                }
530
531                return new Color(r, g, b, a);
532        }
533
534        protected Object array() throws IOException, ParseException {
535                int c;
536                LinkedList<Object> array = new LinkedList<Object>();
537
538                c = nextChar();
539
540                if (c != ARRAY_OPEN)
541                        throw parseException("'%c' expected", ARRAY_OPEN);
542
543                skipWhitespaces();
544                c = nextChar();
545
546                while (c != ARRAY_CLOSE) {
547                        pushback(c);
548                        array.add(value(false));
549
550                        skipWhitespaces();
551                        c = nextChar();
552
553                        if (c != ARRAY_CLOSE && c != ',')
554                                throw parseException("'%c' or ',' expected, got '%c'",
555                                                ARRAY_CLOSE, c);
556
557                        if (c == ',') {
558                                skipWhitespaces();
559                                c = nextChar();
560                        }
561                }
562
563                if (c != ARRAY_CLOSE)
564                        throw parseException("'%c' expected", ARRAY_CLOSE);
565
566                return array.toArray();
567        }
568
569        protected Object map() throws IOException, ParseException {
570                int c;
571                HashMap<String, Object> map = new HashMap<String, Object>();
572                String key;
573                Object value;
574
575                c = nextChar();
576
577                if (c != MAP_OPEN)
578                        throw parseException("'%c' expected", MAP_OPEN);
579
580                c = nextChar();
581
582                while (c != MAP_CLOSE) {
583                        pushback(c);
584                        key = id();
585
586                        if (key == null)
587                                throw parseException("id expected here, '%c'", c);
588
589                        skipWhitespaces();
590                        c = nextChar();
591
592                        if (c == '=' || c == ':') {
593                                skipWhitespaces();
594                                value = value(false);
595                        } else {
596                                value = Boolean.TRUE;
597                                pushback(c);
598                        }
599
600                        map.put(key, value);
601
602                        skipWhitespaces();
603                        c = nextChar();
604
605                        if (c != MAP_CLOSE && c != ',')
606                                throw parseException("'%c' or ',' expected, got '%c'",
607                                                MAP_CLOSE, c);
608
609                        if (c == ',') {
610                                skipWhitespaces();
611                                c = nextChar();
612                        }
613                }
614
615                if (c != MAP_CLOSE)
616                        throw parseException("'%c' expected", MAP_CLOSE);
617
618                return map;
619        }
620
621        protected Token directive() throws IOException, ParseException {
622                int c1, c2;
623
624                //
625                // Skip comment and empty lines
626                //
627                do {
628                        c1 = nextChar();
629
630                        if (c1 == '#')
631                                skipLine();
632
633                        if (c1 < 0)
634                                return Token.EOF;
635                } while (c1 == '#' || c1 == '\n');
636
637                c2 = nextChar();
638
639                if (c1 >= 'A' && c1 <= 'Z')
640                        c1 -= 'A' - 'a';
641
642                if (c2 >= 'A' && c2 <= 'Z')
643                        c2 -= 'A' - 'a';
644
645                switch (c1) {
646                case 'a':
647                        if (c2 == 'n')
648                                return Token.AN;
649                        else if (c2 == 'e')
650                                return Token.AE;
651
652                        break;
653                case 'c':
654                        switch (c2) {
655                        case 'n':
656                                return Token.CN;
657                        case 'e':
658                                return Token.CE;
659                        case 'g':
660                                return Token.CG;
661                        case 'l':
662                                return Token.CL;
663                        }
664
665                        break;
666                case 'd':
667                        if (c2 == 'n')
668                                return Token.DN;
669                        else if (c2 == 'e')
670                                return Token.DE;
671
672                        break;
673                case 's':
674                        if (c2 == 't')
675                                return Token.ST;
676
677                        break;
678                case 't':
679                        if (c1 == 'f')
680                                return Token.TF;
681
682                        break;
683                }
684
685                throw parseException("unknown directive '%c%c'", c1, c2);
686        }
687
688        protected String string() throws IOException, ParseException {
689                int c, s;
690                StringBuilder builder;
691                boolean slash;
692
693                slash = false;
694                builder = new StringBuilder();
695                c = nextChar();
696
697                if (c != '\"' && c != '\'')
698                        throw parseException("string expected");
699
700                s = c;
701
702                while ((c = nextChar()) != s || slash) {
703                        if (slash && c != s)
704                                builder.append("\\");
705
706                        slash = c == '\\';
707
708                        if (!slash) {
709                                if (!Character.isValidCodePoint(c))
710                                        throw parseException("invalid code-point 0x%X", c);
711
712                                builder.appendCodePoint(c);
713                        }
714                }
715
716                return builder.toString();
717        }
718
719        protected String id() throws IOException, ParseException {
720                int c;
721                StringBuilder builder = new StringBuilder();
722
723                skipWhitespaces();
724                c = nextChar();
725                pushback(c);
726
727                if (c == '\"' || c == '\'') {
728                        return string();
729                } else {
730                        boolean stop = false;
731
732                        while (!stop) {
733                                c = nextChar();
734
735                                switch (Character.getType(c)) {
736                                case Character.LOWERCASE_LETTER:
737                                case Character.UPPERCASE_LETTER:
738                                case Character.DECIMAL_DIGIT_NUMBER:
739                                        break;
740                                case Character.DASH_PUNCTUATION:
741                                        if (c != '-')
742                                                stop = true;
743
744                                        break;
745                                case Character.MATH_SYMBOL:
746                                        if (c != '+')
747                                                stop = true;
748
749                                        break;
750                                case Character.CONNECTOR_PUNCTUATION:
751                                        if (c != '_')
752                                                stop = true;
753
754                                        break;
755                                case Character.OTHER_PUNCTUATION:
756                                        if (c != '.')
757                                                stop = true;
758
759                                        break;
760                                default:
761                                        stop = true;
762                                        break;
763                                }
764
765                                if (!stop)
766                                        builder.appendCodePoint(c);
767                        }
768
769                        pushback(c);
770                }
771
772                if (builder.length() == 0)
773                        return null;
774
775                return builder.toString();
776        }
777
778        /*
779         * protected long timestamp() throws IOException, ParseException { int c;
780         * String time;
781         * 
782         * c = nextChar(); pushback(c);
783         * 
784         * switch (c) { case '"': case '\'': time = string(); break; default:
785         * StringBuilder builder = new StringBuilder();
786         * 
787         * while ((c = nextChar()) != '\n' && c != '"') builder.appendCodePoint(c);
788         * 
789         * pushback(c); time = builder.toString(); break; }
790         * 
791         * pushback(c); return dateIO.parse(time).getTimeInMillis(); }
792         */
793
794        protected ParseException parseException(String message, Object... args) {
795                return new ParseException(String.format(String.format(
796                                "parse error at (%d;%d) : %s", line, column, message), args));
797        }
798}