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