1 /*
   2  * Copyright (c) 2014, 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 jdk.internal.jimage;
  26 
  27 import java.io.DataOutputStream;
  28 import java.io.IOException;
  29 import java.nio.ByteBuffer;
  30 import java.util.ArrayList;
  31 import java.util.Collections;
  32 import java.util.HashMap;
  33 import java.util.List;
  34 import java.util.Map;
  35 import java.util.Set;
  36 import java.util.TreeMap;
  37 import java.util.TreeSet;
  38 
  39 /**
  40  * A class to build a sorted tree of Resource paths as a tree of ImageLocation.
  41  *
  42  */
  43 // XXX Public only due to the JImageTask / JImageTask code duplication
  44 public final class ImageResourcesTree {
  45 
  46     private static final String MODULES = "modules";
  47     private static final String PACKAGES = "packages";
  48     public static final String MODULES_STRING = UTF8String.MODULES_STRING.toString();
  49     public static final String PACKAGES_STRING = UTF8String.PACKAGES_STRING.toString();
  50 
  51     public static boolean isTreeInfoResource(String path) {
  52         return path.startsWith(PACKAGES_STRING) || path.startsWith(MODULES_STRING);
  53     }
  54 
  55     /**
  56      * Path item tree node.
  57      */
  58     private static final class Node {
  59 
  60         private final String name;
  61         private final Map<String, Node> children = new TreeMap<>();
  62         private final Node parent;
  63         private ImageLocationWriter loc;
  64 
  65         private Node(String name, Node parent) {
  66             this.name = name;
  67             this.parent = parent;
  68 
  69             if (parent != null) {
  70                 parent.children.put(name, this);
  71             }
  72         }
  73 
  74         public String getPath() {
  75             if (parent == null) {
  76                 return "/";
  77             }
  78             return buildPath(this);
  79         }
  80 
  81         public String getName() {
  82             return name;
  83         }
  84 
  85         public Node getChildren(String name) {
  86             Node item = children.get(name);
  87             return item;
  88         }
  89 
  90         private static String buildPath(Node item) {
  91             if (item == null) {
  92                 return null;
  93             }
  94             String path = buildPath(item.parent);
  95             if (path == null) {
  96                 return item.getName();
  97             } else {
  98                 return path + "/" + item.getName();
  99             }
 100         }
 101     }
 102 
 103     /**
 104      * Tree of nodes.
 105      */
 106     private static final class Tree {
 107 
 108         private final Map<String, Node> directAccess = new HashMap<>();
 109         private final List<String> paths;
 110         private final Node root;
 111         private Node modules;
 112         private Node packages;
 113 
 114         private Tree(List<String> paths) {
 115             this.paths = paths;
 116             root = new Node("", null);
 117             buildTree();
 118         }
 119 
 120         private void buildTree() {
 121             modules = new Node(MODULES, root);
 122             directAccess.put(modules.getPath(), modules);
 123 
 124             Map<String, Set<String>> moduleToPackage = new TreeMap<>();
 125             Map<String, Set<String>> packageToModule = new TreeMap<>();
 126 
 127             for (String p : paths) {
 128                 if (!p.startsWith("/")) {
 129                     continue;
 130                 }
 131                 String[] split = p.split("/");
 132                 Node current = modules;
 133                 String module = null;
 134                 for (int i = 0; i < split.length; i++) {
 135                     String s = split[i];
 136                     if (!s.isEmpty()) {
 137                         if (module == null) {
 138                             module = s;
 139                         }
 140                         Node n = current.children.get(s);
 141                         if (n == null) {
 142                             n = new Node(s, current);
 143                             if (i == split.length - 1) { // Leaf
 144                                 String pkg = toPackageName(n.parent);
 145                                 if (pkg != null && !pkg.startsWith("META-INF")) {
 146                                     Set<String> pkgs = moduleToPackage.get(module);
 147                                     if (pkgs == null) {
 148                                         pkgs = new TreeSet<>();
 149                                         moduleToPackage.put(module, pkgs);
 150                                     }
 151                                     pkgs.add(pkg);
 152                                 }
 153                             } else { // put only sub trees, no leaf
 154                                 directAccess.put(n.getPath(), n);
 155                                 String pkg = toPackageName(n);
 156                                 if (pkg != null && !pkg.startsWith("META-INF")) {
 157                                     Set<String> mods = packageToModule.get(pkg);
 158                                     if (mods == null) {
 159                                         mods = new TreeSet<>();
 160                                         packageToModule.put(pkg, mods);
 161                                     }
 162                                     mods.add(module);
 163 
 164                                 }
 165                             }
 166                         }
 167                         current = n;
 168                     }
 169                 }
 170             }
 171             packages = new Node(PACKAGES, root);
 172             directAccess.put(packages.getPath(), packages);
 173             for (Map.Entry<String, Set<String>> entry : moduleToPackage.entrySet()) {
 174                 for (String pkg : entry.getValue()) {
 175                     Node pkgNode = new Node(pkg, packages);
 176                     directAccess.put(pkgNode.getPath(), pkgNode);
 177 
 178                     Node modNode = new Node(entry.getKey(), pkgNode);
 179                     directAccess.put(modNode.getPath(), modNode);
 180                 }
 181             }
 182             for (Map.Entry<String, Set<String>> entry : packageToModule.entrySet()) {
 183                 Node pkgNode = new Node(entry.getKey(), packages);
 184                 directAccess.put(pkgNode.getPath(), pkgNode);
 185                 for (String module : entry.getValue()) {
 186                     Node modNode = new Node(module, pkgNode);
 187                     directAccess.put(modNode.getPath(), modNode);
 188                 }
 189             }
 190         }
 191 
 192         public String toResourceName(Node node) {
 193             if (!node.children.isEmpty()) {
 194                 throw new RuntimeException("Node is not a resource");
 195             }
 196             return removeRadical(node);
 197         }
 198 
 199         public String getModule(Node node) {
 200             if (node.parent == null || node.getName().equals(MODULES) ||
 201                 node.getName().startsWith(PACKAGES)) {
 202                 return null;
 203             }
 204             String path = removeRadical(node);
 205             // "/xxx/...";
 206             path = path.substring(1);
 207             int i = path.indexOf("/");
 208             if (i == -1) {
 209                 return path;
 210             } else {
 211                 return path.substring(0, i);
 212             }
 213         }
 214 
 215         public String toPackageName(Node node) {
 216             if (node.parent == null) {
 217                 return null;
 218             }
 219             String path = removeRadical(node.getPath(), "/" + MODULES + "/");
 220             String module = getModule(node);
 221             if (path.equals(module)) {
 222                 return null;
 223             }
 224             String pkg = removeRadical(path, module + "/");
 225             return pkg.replaceAll("/", ".");
 226         }
 227 
 228         public String removeRadical(Node node) {
 229             String s = node.getPath();
 230             return removeRadical(node.getPath(), "/" + MODULES);
 231         }
 232 
 233         private String removeRadical(String path, String str) {
 234             return path.substring(str.length());
 235         }
 236 
 237         public Node getRoot() {
 238             return root;
 239         }
 240 
 241         public Map<String, Node> getMap() {
 242             return directAccess;
 243         }
 244 
 245         private boolean isPackageNode(Node node) {
 246             if (!node.children.isEmpty()) {
 247                 throw new RuntimeException("Node is not a package");
 248             }
 249             return node.getPath().startsWith("/" + PACKAGES);
 250         }
 251     }
 252 
 253     private static final class LocationsAdder {
 254 
 255         private long offset;
 256         private final List<byte[]> content = new ArrayList<>();
 257         private final BasicImageWriter writer;
 258         private final Tree tree;
 259 
 260         LocationsAdder(Tree tree, long offset, BasicImageWriter writer) {
 261             this.tree = tree;
 262             this.offset = offset;
 263             this.writer = writer;
 264             addLocations(tree.getRoot());
 265         }
 266 
 267         private int addLocations(Node current) {
 268             int[] ret = new int[current.children.size()];
 269             int i = 0;
 270             for (java.util.Map.Entry<String, Node> entry : current.children.entrySet()) {
 271                 ret[i] = addLocations(entry.getValue());
 272                 i += 1;
 273             }
 274             if (current != tree.getRoot() && (ret.length > 0 || tree.isPackageNode(current))) {
 275                 int size = ret.length * 4;
 276                 writer.addLocation(current.getPath(), offset, 0, size);
 277                 offset += size;
 278             }
 279             return 0;
 280         }
 281 
 282         private List<byte[]> computeContent() {
 283             // Map used to associate Tree item with locations offset.
 284             Map<String, ImageLocationWriter> outLocations = new HashMap<>();
 285             for (ImageLocationWriter wr : writer.getLocations()) {
 286                 outLocations.put(wr.getFullNameString(), wr);
 287             }
 288             // Attach location to node
 289             for (Map.Entry<String, ImageLocationWriter> entry : outLocations.entrySet()) {
 290                 Node item = tree.getMap().get(entry.getKey());
 291                 if (item != null) {
 292                     item.loc = entry.getValue();
 293                 }
 294             }
 295             computeContent(tree.getRoot(), outLocations);
 296             return content;
 297         }
 298 
 299         private int computeContent(Node current, Map<String, ImageLocationWriter> outLocations) {
 300             int[] ret = new int[current.children.size()];
 301             int i = 0;
 302             for (java.util.Map.Entry<String, Node> entry : current.children.entrySet()) {
 303                 ret[i] = computeContent(entry.getValue(), outLocations);
 304                 i += 1;
 305             }
 306             if (ret.length > 0) {
 307                 int size = ret.length * 4;
 308                 ByteBuffer buff = ByteBuffer.allocate(size);
 309                 buff.order(writer.getByteOrder());
 310                 for (int val : ret) {
 311                     buff.putInt(val);
 312                 }
 313                 byte[] arr = buff.array();
 314                 content.add(arr);
 315             } else {
 316                 if (tree.isPackageNode(current)) {
 317                     current.loc = outLocations.get(current.getPath());
 318                 } else {
 319                     String s = tree.toResourceName(current);
 320                     current.loc = outLocations.get(s);
 321                 }
 322             }
 323             return current == tree.getRoot() ? 0 : current.loc.getLocationOffset();
 324         }
 325     }
 326 
 327     private final List<String> paths;
 328     private final LocationsAdder adder;
 329 
 330     public ImageResourcesTree(long offset, BasicImageWriter writer, List<String> paths) {
 331         this.paths = new ArrayList<>();
 332         this.paths.addAll(paths);
 333         Collections.sort(this.paths);
 334         Tree tree = new Tree(this.paths);
 335         adder = new LocationsAdder(tree, offset, writer);
 336     }
 337 
 338     public void addContent(DataOutputStream out) throws IOException {
 339         List<byte[]> content = adder.computeContent();
 340         for (byte[] c : content) {
 341             out.write(c, 0, c.length);
 342         }
 343     }
 344 }