1 /*
   2  * Copyright (c) 2012, 2016, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 package com.sun.hotspot.igv.data.serialization;
  26 
  27 import com.sun.hotspot.igv.data.*;
  28 import com.sun.hotspot.igv.data.Properties;
  29 import com.sun.hotspot.igv.data.services.GroupCallback;
  30 import java.io.EOFException;
  31 import java.io.IOException;
  32 import java.nio.ByteBuffer;
  33 import java.nio.channels.ReadableByteChannel;
  34 import java.nio.charset.Charset;
  35 import java.util.*;
  36 import java.util.regex.Matcher;
  37 import java.util.regex.Pattern;
  38 import javax.swing.SwingUtilities;
  39 import java.security.MessageDigest;
  40 import java.security.NoSuchAlgorithmException;
  41 
  42 public class BinaryParser implements GraphParser {
  43     private static final int BEGIN_GROUP = 0x00;
  44     private static final int BEGIN_GRAPH = 0x01;
  45     private static final int CLOSE_GROUP = 0x02;
  46 
  47     private static final int POOL_NEW = 0x00;
  48     private static final int POOL_STRING = 0x01;
  49     private static final int POOL_ENUM = 0x02;
  50     private static final int POOL_CLASS = 0x03;
  51     private static final int POOL_METHOD = 0x04;
  52     private static final int POOL_NULL = 0x05;
  53     private static final int POOL_NODE_CLASS = 0x06;
  54     private static final int POOL_FIELD = 0x07;
  55     private static final int POOL_SIGNATURE = 0x08;
  56 
  57     private static final int KLASS = 0x00;
  58     private static final int ENUM_KLASS = 0x01;
  59 
  60     private static final int PROPERTY_POOL = 0x00;
  61     private static final int PROPERTY_INT = 0x01;
  62     private static final int PROPERTY_LONG = 0x02;
  63     private static final int PROPERTY_DOUBLE = 0x03;
  64     private static final int PROPERTY_FLOAT = 0x04;
  65     private static final int PROPERTY_TRUE = 0x05;
  66     private static final int PROPERTY_FALSE = 0x06;
  67     private static final int PROPERTY_ARRAY = 0x07;
  68     private static final int PROPERTY_SUBGRAPH = 0x08;
  69 
  70     private static final String NO_BLOCK = "noBlock";
  71 
  72     private static final Charset utf8 = Charset.forName("UTF-8");
  73 
  74     private final GroupCallback callback;
  75     private final List<Object> constantPool;
  76     private final ByteBuffer buffer;
  77     private final ReadableByteChannel channel;
  78     private final GraphDocument rootDocument;
  79     private final Deque<Folder> folderStack;
  80     private final Deque<byte[]> hashStack;
  81     private final ParseMonitor monitor;
  82 
  83     private MessageDigest digest;
  84 
  85     private enum Length {
  86         S,
  87         M,
  88         L
  89     }
  90 
  91     private interface LengthToString {
  92         String toString(Length l);
  93     }
  94 
  95     private static abstract class Member implements LengthToString {
  96         public final Klass holder;
  97         public final int accessFlags;
  98         public final String name;
  99         public Member(Klass holder, String name, int accessFlags) {
 100             this.holder = holder;
 101             this.accessFlags = accessFlags;
 102             this.name = name;
 103         }
 104     }
 105 
 106     private static class Method extends Member {
 107         public final Signature signature;
 108         public final byte[] code;
 109         public Method(String name, Signature signature, byte[] code, Klass holder, int accessFlags) {
 110             super(holder, name, accessFlags);
 111             this.signature = signature;
 112             this.code = code;
 113         }
 114         @Override
 115         public String toString() {
 116             StringBuilder sb = new StringBuilder();
 117             sb.append(holder).append('.').append(name).append('(');
 118             for (int i = 0; i < signature.argTypes.length; i++) {
 119                 if (i > 0) {
 120                     sb.append(", ");
 121                 }
 122                 sb.append(signature.argTypes[i]);
 123             }
 124             sb.append(')');
 125             return sb.toString();
 126         }
 127         @Override
 128         public String toString(Length l) {
 129             switch(l) {
 130                 case M:
 131                     return holder.toString(Length.L) + "." + name;
 132                 case S:
 133                     return holder.toString(Length.S) + "." + name;
 134                 default:
 135                 case L:
 136                     return toString();
 137             }
 138         }
 139     }
 140 
 141     private static class Signature {
 142         public final String returnType;
 143         public final String[] argTypes;
 144         public Signature(String returnType, String[] argTypes) {
 145             this.returnType = returnType;
 146             this.argTypes = argTypes;
 147         }
 148     }
 149 
 150     private static class Field extends Member {
 151         public final String type;
 152         public Field(String type, Klass holder, String name, int accessFlags) {
 153             super(holder, name, accessFlags);
 154             this.type = type;
 155         }
 156         @Override
 157         public String toString() {
 158             return holder + "." + name;
 159         }
 160         @Override
 161         public String toString(Length l) {
 162             switch(l) {
 163                 case M:
 164                     return holder.toString(Length.L) + "." + name;
 165                 case S:
 166                     return holder.toString(Length.S) + "." + name;
 167                 default:
 168                 case L:
 169                     return toString();
 170             }
 171         }
 172     }
 173 
 174     private static class Klass implements LengthToString {
 175         public final String name;
 176         public final String simpleName;
 177         public Klass(String name) {
 178             this.name = name;
 179             String simple;
 180             try {
 181                 simple = name.substring(name.lastIndexOf('.') + 1);
 182             } catch (IndexOutOfBoundsException ioobe) {
 183                 simple = name;
 184             }
 185             this.simpleName = simple;
 186         }
 187         @Override
 188         public String toString() {
 189             return name;
 190         }
 191         @Override
 192         public String toString(Length l) {
 193             switch(l) {
 194                 case S:
 195                     return simpleName;
 196                 default:
 197                 case L:
 198                 case M:
 199                     return toString();
 200             }
 201         }
 202     }
 203 
 204     private static class EnumKlass extends Klass {
 205         public final String[] values;
 206         public EnumKlass(String name, String[] values) {
 207             super(name);
 208             this.values = values;
 209         }
 210     }
 211 
 212     private static class Port {
 213         public final boolean isList;
 214         public final String name;
 215         private Port(boolean isList, String name) {
 216             this.isList = isList;
 217             this.name = name;
 218         }
 219     }
 220 
 221     private static class TypedPort extends Port {
 222         public final EnumValue type;
 223         private TypedPort(boolean isList, String name, EnumValue type) {
 224             super(isList, name);
 225             this.type = type;
 226         }
 227     }
 228 
 229     private static class NodeClass {
 230         public final String className;
 231         public final String nameTemplate;
 232         public final List<TypedPort> inputs;
 233         public final List<Port> sux;
 234         private NodeClass(String className, String nameTemplate, List<TypedPort> inputs, List<Port> sux) {
 235             this.className = className;
 236             this.nameTemplate = nameTemplate;
 237             this.inputs = inputs;
 238             this.sux = sux;
 239         }
 240         @Override
 241         public String toString() {
 242             return className;
 243         }
 244     }
 245 
 246     private static class EnumValue implements LengthToString {
 247         public EnumKlass enumKlass;
 248         public int ordinal;
 249         public EnumValue(EnumKlass enumKlass, int ordinal) {
 250             this.enumKlass = enumKlass;
 251             this.ordinal = ordinal;
 252         }
 253         @Override
 254         public String toString() {
 255             return enumKlass.simpleName + "." + enumKlass.values[ordinal];
 256         }
 257         @Override
 258         public String toString(Length l) {
 259             switch(l) {
 260                 case S:
 261                     return enumKlass.values[ordinal];
 262                 default:
 263                 case M:
 264                 case L:
 265                     return toString();
 266             }
 267         }
 268     }
 269 
 270     public BinaryParser(ReadableByteChannel channel, ParseMonitor monitor, GraphDocument rootDocument, GroupCallback callback) {
 271         this.callback = callback;
 272         constantPool = new ArrayList<>();
 273         buffer = ByteBuffer.allocateDirect(256 * 1024);
 274         buffer.flip();
 275         this.channel = channel;
 276         this.rootDocument = rootDocument;
 277         folderStack = new LinkedList<>();
 278         hashStack = new LinkedList<>();
 279         this.monitor = monitor;
 280         try {
 281             this.digest = MessageDigest.getInstance("SHA-1");
 282         } catch (NoSuchAlgorithmException e) {
 283         }
 284     }
 285 
 286     private void fill() throws IOException {
 287         // All the data between lastPosition and position has been
 288         // used so add it to the digest.
 289         int position = buffer.position();
 290         buffer.position(lastPosition);
 291         byte[] remaining = new byte[position - buffer.position()];
 292         buffer.get(remaining);
 293         digest.update(remaining);
 294         assert position == buffer.position();
 295 
 296         buffer.compact();
 297         if (channel.read(buffer) < 0) {
 298             throw new EOFException();
 299         }
 300         buffer.flip();
 301         lastPosition = buffer.position();
 302     }
 303 
 304     private void ensureAvailable(int i) throws IOException {
 305         if (i > buffer.capacity()) {
 306             throw new IllegalArgumentException(String.format("Can not request %d bytes: buffer capacity is %d", i, buffer.capacity()));
 307         }
 308         while (buffer.remaining() < i) {
 309             fill();
 310         }
 311     }
 312 
 313     private int readByte() throws IOException {
 314         ensureAvailable(1);
 315         return ((int)buffer.get()) & 0xff;
 316     }
 317 
 318     private int readInt() throws IOException {
 319         ensureAvailable(4);
 320         return buffer.getInt();
 321     }
 322 
 323     private char readShort() throws IOException {
 324         ensureAvailable(2);
 325         return buffer.getChar();
 326     }
 327 
 328     private long readLong() throws IOException {
 329         ensureAvailable(8);
 330         return buffer.getLong();
 331     }
 332 
 333     private double readDouble() throws IOException {
 334         ensureAvailable(8);
 335         return buffer.getDouble();
 336     }
 337 
 338     private float readFloat() throws IOException {
 339         ensureAvailable(4);
 340         return buffer.getFloat();
 341     }
 342 
 343     private String readString() throws IOException {
 344         return new String(readBytes(), utf8).intern();
 345     }
 346 
 347     private byte[] readBytes() throws IOException {
 348         int len = readInt();
 349         if (len < 0) {
 350             return null;
 351         }
 352         byte[] b = new byte[len];
 353         int bytesRead = 0;
 354         while (bytesRead < b.length) {
 355             int toRead = Math.min(b.length - bytesRead, buffer.capacity());
 356             ensureAvailable(toRead);
 357             buffer.get(b, bytesRead, toRead);
 358             bytesRead += toRead;
 359         }
 360         return b;
 361     }
 362 
 363     private String readIntsToString() throws IOException {
 364         int len = readInt();
 365         if (len < 0) {
 366             return "null";
 367         }
 368         ensureAvailable(len * 4);
 369         StringBuilder sb = new StringBuilder().append('[');
 370         for (int i = 0; i < len; i++) {
 371             sb.append(buffer.getInt());
 372             if (i < len - 1) {
 373                 sb.append(", ");
 374             }
 375         }
 376         sb.append(']');
 377         return sb.toString().intern();
 378     }
 379 
 380     private String readDoublesToString() throws IOException {
 381         int len = readInt();
 382         if (len < 0) {
 383             return "null";
 384         }
 385         ensureAvailable(len * 8);
 386         StringBuilder sb = new StringBuilder().append('[');
 387         for (int i = 0; i < len; i++) {
 388             sb.append(buffer.getDouble());
 389             if (i < len - 1) {
 390                 sb.append(", ");
 391             }
 392         }
 393         sb.append(']');
 394         return sb.toString().intern();
 395     }
 396 
 397     private String readPoolObjectsToString() throws IOException {
 398         int len = readInt();
 399         if (len < 0) {
 400             return "null";
 401         }
 402         StringBuilder sb = new StringBuilder().append('[');
 403         for (int i = 0; i < len; i++) {
 404             sb.append(readPoolObject(Object.class));
 405             if (i < len - 1) {
 406                 sb.append(", ");
 407             }
 408         }
 409         sb.append(']');
 410         return sb.toString().intern();
 411     }
 412 
 413     private <T> T readPoolObject(Class<T> klass) throws IOException {
 414         int type = readByte();
 415         if (type == POOL_NULL) {
 416             return null;
 417         }
 418         if (type == POOL_NEW) {
 419             return (T) addPoolEntry(klass);
 420         }
 421         assert assertObjectType(klass, type);
 422         char index = readShort();
 423         if (index < 0 || index >= constantPool.size()) {
 424             throw new IOException("Invalid constant pool index : " + index);
 425         }
 426         Object obj = constantPool.get(index);
 427         return (T) obj;
 428     }
 429 
 430     private boolean assertObjectType(Class<?> klass, int type) {
 431         switch(type) {
 432             case POOL_CLASS:
 433                 return klass.isAssignableFrom(EnumKlass.class);
 434             case POOL_ENUM:
 435                 return klass.isAssignableFrom(EnumValue.class);
 436             case POOL_METHOD:
 437                 return klass.isAssignableFrom(Method.class);
 438             case POOL_STRING:
 439                 return klass.isAssignableFrom(String.class);
 440             case POOL_NODE_CLASS:
 441                 return klass.isAssignableFrom(NodeClass.class);
 442             case POOL_FIELD:
 443                 return klass.isAssignableFrom(Field.class);
 444             case POOL_SIGNATURE:
 445                 return klass.isAssignableFrom(Signature.class);
 446             case POOL_NULL:
 447                 return true;
 448             default:
 449                 return false;
 450         }
 451     }
 452 
 453     private Object addPoolEntry(Class<?> klass) throws IOException {
 454         char index = readShort();
 455         int type = readByte();
 456         assert assertObjectType(klass, type) : "Wrong object type : " + klass + " != " + type;
 457         Object obj;
 458         switch(type) {
 459             case POOL_CLASS: {
 460                 String name = readString();
 461                 int klasstype = readByte();
 462                 if (klasstype == ENUM_KLASS) {
 463                     int len = readInt();
 464                     String[] values = new String[len];
 465                     for (int i = 0; i < len; i++) {
 466                         values[i] = readPoolObject(String.class);
 467                     }
 468                     obj = new EnumKlass(name, values);
 469                 } else if (klasstype == KLASS) {
 470                     obj = new Klass(name);
 471                 } else {
 472                     throw new IOException("unknown klass type : " + klasstype);
 473                 }
 474                 break;
 475             }
 476             case POOL_ENUM: {
 477                 EnumKlass enumClass = readPoolObject(EnumKlass.class);
 478                 int ordinal = readInt();
 479                 obj = new EnumValue(enumClass, ordinal);
 480                 break;
 481             }
 482             case POOL_NODE_CLASS: {
 483                 String className = readString();
 484                 String nameTemplate = readString();
 485                 int inputCount = readShort();
 486                 List<TypedPort> inputs = new ArrayList<>(inputCount);
 487                 for (int i = 0; i < inputCount; i++) {
 488                     boolean isList = readByte() != 0;
 489                     String name = readPoolObject(String.class);
 490                     EnumValue inputType = readPoolObject(EnumValue.class);
 491                     inputs.add(new TypedPort(isList, name, inputType));
 492                 }
 493                 int suxCount = readShort();
 494                 List<Port> sux = new ArrayList<>(suxCount);
 495                 for (int i = 0; i < suxCount; i++) {
 496                     boolean isList = readByte() != 0;
 497                     String name = readPoolObject(String.class);
 498                     sux.add(new Port(isList, name));
 499                 }
 500                 obj = new NodeClass(className, nameTemplate, inputs, sux);
 501                 break;
 502             }
 503             case POOL_METHOD: {
 504                 Klass holder = readPoolObject(Klass.class);
 505                 String name = readPoolObject(String.class);
 506                 Signature sign = readPoolObject(Signature.class);
 507                 int flags = readInt();
 508                 byte[] code = readBytes();
 509                 obj = new Method(name, sign, code, holder, flags);
 510                 break;
 511             }
 512             case POOL_FIELD: {
 513                 Klass holder = readPoolObject(Klass.class);
 514                 String name = readPoolObject(String.class);
 515                 String fType = readPoolObject(String.class);
 516                 int flags = readInt();
 517                 obj = new Field(fType, holder, name, flags);
 518                 break;
 519             }
 520             case POOL_SIGNATURE: {
 521                 int argc = readShort();
 522                 String[] args = new String[argc];
 523                 for (int i = 0; i < argc; i++) {
 524                     args[i] = readPoolObject(String.class);
 525                 }
 526                 String returnType = readPoolObject(String.class);
 527                 obj = new Signature(returnType, args);
 528                 break;
 529             }
 530             case POOL_STRING: {
 531                 obj = readString();
 532                 break;
 533             }
 534             default:
 535                 throw new IOException("unknown pool type");
 536         }
 537         while (constantPool.size() <= index) {
 538             constantPool.add(null);
 539         }
 540         constantPool.set(index, obj);
 541         return obj;
 542     }
 543 
 544     private Object readPropertyObject() throws IOException {
 545         int type = readByte();
 546         switch (type) {
 547             case PROPERTY_INT:
 548                 return readInt();
 549             case PROPERTY_LONG:
 550                 return readLong();
 551             case PROPERTY_FLOAT:
 552                 return readFloat();
 553             case PROPERTY_DOUBLE:
 554                 return readDouble();
 555             case PROPERTY_TRUE:
 556                 return Boolean.TRUE;
 557             case PROPERTY_FALSE:
 558                 return Boolean.FALSE;
 559             case PROPERTY_POOL:
 560                 return readPoolObject(Object.class);
 561             case PROPERTY_ARRAY:
 562                 int subType = readByte();
 563                 switch(subType) {
 564                     case PROPERTY_INT:
 565                         return readIntsToString();
 566                     case PROPERTY_DOUBLE:
 567                         return readDoublesToString();
 568                     case PROPERTY_POOL:
 569                         return readPoolObjectsToString();
 570                     default:
 571                         throw new IOException("Unknown type");
 572                 }
 573             case PROPERTY_SUBGRAPH:
 574                 InputGraph graph = parseGraph("");
 575                 new Group(null).addElement(graph);
 576                 return graph;
 577             default:
 578                 throw new IOException("Unknown type");
 579         }
 580     }
 581 
 582     @Override
 583     public GraphDocument parse() throws IOException {
 584         folderStack.push(rootDocument);
 585         hashStack.push(null);
 586         if (monitor != null) {
 587             monitor.setState("Starting parsing");
 588         }
 589         try {
 590             while(true) {
 591                 parseRoot();
 592             }
 593         } catch (EOFException e) {
 594 
 595         }
 596         if (monitor != null) {
 597             monitor.setState("Finished parsing");
 598         }
 599         return rootDocument;
 600     }
 601 
 602     private void parseRoot() throws IOException {
 603         int type = readByte();
 604         switch(type) {
 605             case BEGIN_GRAPH: {
 606                 final Folder parent = folderStack.peek();
 607                 final InputGraph graph = parseGraph();
 608                 SwingUtilities.invokeLater(new Runnable(){
 609                     @Override
 610                     public void run() {
 611                         parent.addElement(graph);
 612                     }
 613                 });
 614                 break;
 615             }
 616             case BEGIN_GROUP: {
 617                 final Folder parent = folderStack.peek();
 618                 final Group group = parseGroup(parent);
 619                 if (callback == null || parent instanceof Group) {
 620                     SwingUtilities.invokeLater(new Runnable(){
 621                         @Override
 622                         public void run() {
 623                             parent.addElement(group);
 624                         }
 625                     });
 626                 }
 627                 folderStack.push(group);
 628                 hashStack.push(null);
 629                 if (callback != null && parent instanceof GraphDocument) {
 630                     callback.started(group);
 631                 }
 632                 break;
 633             }
 634             case CLOSE_GROUP: {
 635                 if (folderStack.isEmpty()) {
 636                     throw new IOException("Unbalanced groups");
 637                 }
 638                 folderStack.pop();
 639                 hashStack.pop();
 640                 break;
 641             }
 642             default:
 643                 throw new IOException("unknown root : " + type);
 644         }
 645     }
 646 
 647     private Group parseGroup(Folder parent) throws IOException {
 648         String name = readPoolObject(String.class);
 649         String shortName = readPoolObject(String.class);
 650         if (monitor != null) {
 651             monitor.setState(shortName);
 652         }
 653         Method method = readPoolObject(Method.class);
 654         int bci = readInt();
 655         Group group = new Group(parent);
 656         group.getProperties().setProperty("name", name);
 657         parseProperties(group.getProperties());
 658         if (method != null) {
 659             InputMethod inMethod = new InputMethod(group, method.name, shortName, bci);
 660             inMethod.setBytecodes("TODO");
 661             group.setMethod(inMethod);
 662         }
 663         return group;
 664     }
 665 
 666     int lastPosition = 0;
 667 
 668     private InputGraph parseGraph() throws IOException {
 669         if (monitor != null) {
 670             monitor.updateProgress();
 671         }
 672         String title = readPoolObject(String.class);
 673         digest.reset();
 674         lastPosition = buffer.position();
 675         InputGraph graph = parseGraph(title);
 676 
 677         int position = buffer.position();
 678         buffer.position(lastPosition);
 679         byte[] remaining = new byte[position - buffer.position()];
 680         buffer.get(remaining);
 681         digest.update(remaining);
 682         assert position == buffer.position();
 683         lastPosition = buffer.position();
 684 
 685         byte[] d = digest.digest();
 686         byte[] hash = hashStack.peek();
 687         if (hash != null && Arrays.equals(hash, d)) {
 688             graph.getProperties().setProperty("_isDuplicate", "true");
 689         } else {
 690             hashStack.pop();
 691             hashStack.push(d);
 692         }
 693         return graph;
 694     }
 695 
 696     private void parseProperties(Properties properties) throws IOException {
 697         int propCount = readShort();
 698         for (int j = 0; j < propCount; j++) {
 699             String key = readPoolObject(String.class);
 700             Object value = readPropertyObject();
 701             properties.setProperty(key, value != null ? value.toString() : "null");
 702         }
 703     }
 704 
 705     private InputGraph parseGraph(String title) throws IOException {
 706         InputGraph graph = new InputGraph(title);
 707         parseProperties(graph.getProperties());
 708         parseNodes(graph);
 709         parseBlocks(graph);
 710         graph.ensureNodesInBlocks();
 711         for (InputNode node : graph.getNodes()) {
 712             node.internProperties();
 713         }
 714         return graph;
 715     }
 716 
 717     private void parseBlocks(InputGraph graph) throws IOException {
 718         int blockCount = readInt();
 719         List<Edge> edges = new LinkedList<>();
 720         for (int i = 0; i < blockCount; i++) {
 721             int id = readInt();
 722             String name = id >= 0 ? Integer.toString(id) : NO_BLOCK;
 723             InputBlock block = graph.addBlock(name);
 724             int nodeCount = readInt();
 725             for (int j = 0; j < nodeCount; j++) {
 726                 int nodeId = readInt();
 727                 if (nodeId < 0) {
 728                     continue;
 729                 }
 730                 final Properties properties = graph.getNode(nodeId).getProperties();
 731                 final String oldBlock = properties.get("block");
 732                 if(oldBlock != null) {
 733                     properties.setProperty("block", oldBlock + ", " + name);
 734                 } else {
 735                     block.addNode(nodeId);
 736                     properties.setProperty("block", name);
 737                 }
 738             }
 739             int edgeCount = readInt();
 740             for (int j = 0; j < edgeCount; j++) {
 741                 int to = readInt();
 742                 edges.add(new Edge(id, to));
 743             }
 744         }
 745         for (Edge e : edges) {
 746             String fromName = e.from >= 0 ? Integer.toString(e.from) : NO_BLOCK;
 747             String toName = e.to >= 0 ? Integer.toString(e.to) : NO_BLOCK;
 748             graph.addBlockEdge(graph.getBlock(fromName), graph.getBlock(toName));
 749         }
 750     }
 751 
 752     private void parseNodes(InputGraph graph) throws IOException {
 753         int count = readInt();
 754         Map<String, Object> props = new HashMap<>();
 755         List<Edge> inputEdges = new ArrayList<>(count);
 756         List<Edge> succEdges = new ArrayList<>(count);
 757         for (int i = 0; i < count; i++) {
 758             int id = readInt();
 759             InputNode node = new InputNode(id);
 760             final Properties properties = node.getProperties();
 761             NodeClass nodeClass = readPoolObject(NodeClass.class);
 762             int preds = readByte();
 763             if (preds > 0) {
 764                 properties.setProperty("hasPredecessor", "true");
 765             }
 766             properties.setProperty("idx", Integer.toString(id));
 767             int propCount = readShort();
 768             for (int j = 0; j < propCount; j++) {
 769                 String key = readPoolObject(String.class);
 770                 if (key.equals("hasPredecessor") || key.equals("name") || key.equals("class") || key.equals("id") || key.equals("idx")) {
 771                     key = "!data." + key;
 772                 }
 773                 Object value = readPropertyObject();
 774                 if (value instanceof InputGraph) {
 775                     InputGraph subgraph = (InputGraph) value;
 776                     subgraph.getProperties().setProperty("name", node.getId() + ":" + key);
 777                     node.addSubgraph((InputGraph) value);
 778                 } else {
 779                     properties.setProperty(key, value != null ? value.toString() : "null");
 780                     props.put(key, value);
 781                 }
 782             }
 783             ArrayList<Edge> currentEdges = new ArrayList<>();
 784             int portNum = 0;
 785             for (TypedPort p : nodeClass.inputs) {
 786                 if (p.isList) {
 787                     int size = readShort();
 788                     for (int j = 0; j < size; j++) {
 789                         int in = readInt();
 790                         if (in >= 0) {
 791                             Edge e = new Edge(in, id, (char) (preds + portNum), p.name + "[" + j + "]", p.type.toString(Length.S), true);
 792                             currentEdges.add(e);
 793                             inputEdges.add(e);
 794                             portNum++;
 795                         }
 796                     }
 797                 } else {
 798                     int in = readInt();
 799                     if (in >= 0) {
 800                         Edge e = new Edge(in, id, (char) (preds + portNum), p.name, p.type.toString(Length.S), true);
 801                         currentEdges.add(e);
 802                         inputEdges.add(e);
 803                         portNum++;
 804                     }
 805                 }
 806 
 807             }
 808             portNum = 0;
 809             for (Port p : nodeClass.sux) {
 810                 if (p.isList) {
 811                     int size = readShort();
 812                     for (int j = 0; j < size; j++) {
 813                         int sux = readInt();
 814                         if (sux >= 0) {
 815                             Edge e = new Edge(id, sux, (char) portNum, p.name + "[" + j + "]", "Successor", false);
 816                             currentEdges.add(e);
 817                             succEdges.add(e);
 818                             portNum++;
 819                         }
 820                     }
 821                 } else {
 822                     int sux = readInt();
 823                     if (sux >= 0) {
 824                         Edge e = new Edge(id, sux, (char) portNum, p.name, "Successor", false);
 825                         currentEdges.add(e);
 826                         succEdges.add(e);
 827                         portNum++;
 828                     }
 829                 }
 830             }
 831             properties.setProperty("name", createName(currentEdges, props, nodeClass.nameTemplate));
 832             properties.setProperty("class", nodeClass.className);
 833             switch (nodeClass.className) {
 834                 case "BeginNode":
 835                     properties.setProperty("shortName", "B");
 836                     break;
 837                 case "EndNode":
 838                     properties.setProperty("shortName", "E");
 839                     break;
 840             }
 841             graph.addNode(node);
 842             props.clear();
 843         }
 844 
 845         Set<InputNode> nodesWithSuccessor = new HashSet<>();
 846 
 847         for (Edge e : succEdges) {
 848             assert !e.input;
 849             char fromIndex = e.num;
 850             nodesWithSuccessor.add(graph.getNode(e.from));
 851             char toIndex = 0;
 852             graph.addEdge(InputEdge.createImmutable(fromIndex, toIndex, e.from, e.to, e.label, e.type));
 853         }
 854         for (Edge e : inputEdges) {
 855             assert e.input;
 856             char fromIndex = (char) (nodesWithSuccessor.contains(graph.getNode(e.from)) ? 1 : 0);
 857             char toIndex = e.num;
 858             graph.addEdge(InputEdge.createImmutable(fromIndex, toIndex, e.from, e.to, e.label, e.type));
 859         }
 860     }
 861 
 862     static final Pattern templatePattern = Pattern.compile("\\{(p|i)#([a-zA-Z0-9$_]+)(/(l|m|s))?\\}");
 863 
 864     private String createName(List<Edge> edges, Map<String, Object> properties, String template) {
 865         Matcher m = templatePattern.matcher(template);
 866         StringBuffer sb = new StringBuffer();
 867         while (m.find()) {
 868             String name = m.group(2);
 869             String type = m.group(1);
 870             String result;
 871             switch (type) {
 872                 case "i":
 873                     StringBuilder inputString = new StringBuilder();
 874                     for(Edge edge : edges) {
 875                         if (edge.label.startsWith(name) && (name.length() == edge.label.length() || edge.label.charAt(name.length()) == '[')) {
 876                             if (inputString.length() > 0) {
 877                                 inputString.append(", ");
 878                             }
 879                             inputString.append(edge.from);
 880                         }
 881                     }
 882                     result = inputString.toString();
 883                     break;
 884                 case "p":
 885                     Object prop = properties.get(name);
 886                     String length = m.group(4);
 887                     if (prop == null) {
 888                         result = "?";
 889                     } else if (length != null && prop instanceof LengthToString) {
 890                         LengthToString lengthProp = (LengthToString) prop;
 891                         switch(length) {
 892                             default:
 893                             case "l":
 894                                 result = lengthProp.toString(Length.L);
 895                                 break;
 896                             case "m":
 897                                 result = lengthProp.toString(Length.M);
 898                                 break;
 899                             case "s":
 900                                 result = lengthProp.toString(Length.S);
 901                                 break;
 902                         }
 903                     } else {
 904                         result = prop.toString();
 905                     }
 906                     break;
 907                 default:
 908                     result = "#?#";
 909                     break;
 910             }
 911             result = result.replace("\\", "\\\\");
 912             result = result.replace("$", "\\$");
 913             m.appendReplacement(sb, result);
 914         }
 915         m.appendTail(sb);
 916         return sb.toString().intern();
 917     }
 918 
 919     private static class Edge {
 920         final int from;
 921         final int to;
 922         final char num;
 923         final String label;
 924         final String type;
 925         final boolean input;
 926         public Edge(int from, int to) {
 927             this(from, to, (char) 0, null, null, false);
 928         }
 929         public Edge(int from, int to, char num, String label, String type, boolean input) {
 930             this.from = from;
 931             this.to = to;
 932             this.label = label != null ? label.intern() : label;
 933             this.type = type != null ? type.intern() : type;
 934             this.num = num;
 935             this.input = input;
 936         }
 937     }
 938 }