src/jdk.jlink/share/classes/jdk/tools/jlink/internal/ImageResourcesTree.java

/*
 * Copyright (c) 2014, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.  Oracle designates this
 * particular file as subject to the "Classpath" exception as provided
 * by Oracle in the LICENSE file that accompanied this code.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 */
package jdk.tools.jlink.internal;

import java.io.DataOutputStream;
import java.io.IOException;
import java.nio.ByteBuffer;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;

/**
 * A class to build a sorted tree of Resource paths as a tree of ImageLocation.
 *
 */
// XXX Public only due to the JImageTask / JImageTask code duplication
public final class ImageResourcesTree {
    public static boolean isTreeInfoResource(String path) {
        return path.startsWith("/packages") || path.startsWith("/modules");
    }

    /**
     * Path item tree node.
     */
    private static class Node {

        private final String name;
        private final Map<String, Node> children = new TreeMap<>();
        private final Node parent;
        private ImageLocationWriter loc;

        private Node(String name, Node parent) {
            this.name = name;
            this.parent = parent;

            if (parent != null) {
                parent.children.put(name, this);
            }
        }

        public String getPath() {
            if (parent == null) {
                return "/";
            }
            return buildPath(this);
        }

        public String getName() {
            return name;
        }

        public Node getChildren(String name) {
            Node item = children.get(name);
            return item;
        }

        private static String buildPath(Node item) {
            if (item == null) {
                return null;
            }
            String path = buildPath(item.parent);
            if (path == null) {
                return item.getName();
            } else {
                return path + "/" + item.getName();
            }
        }
    }

    private static final class ResourceNode extends Node {

        public ResourceNode(String name, Node parent) {
            super(name, parent);
        }
    }

    private static class PackageNode extends Node {
        /**
         * A reference to a package. Empty packages can be located inside one or
         * more modules. A package with classes exist in only one module.
         */
        final static class PackageReference {

            private final String name;
            private final boolean isEmpty;

            PackageReference(String name, boolean isEmpty) {
                Objects.requireNonNull(name);
                this.name = name;
                this.isEmpty = isEmpty;
            }

            @Override
            public String toString() {
                return name + "[empty:" + isEmpty + "]";
            }
        }

        private final Map<String, PackageReference> references = new TreeMap<>();

        PackageNode(String name, Node parent) {
            super(name, parent);
        }

        private void addReference(String name, boolean isEmpty) {
            PackageReference ref = references.get(name);
            if (ref == null) {
                references.put(name, new PackageReference(name, isEmpty));
            } else {
                if (ref.isEmpty) { // replace with new one incase non empty.
                    references.put(name, new PackageReference(name, isEmpty));
                }
            }
        }

        private void validate() {
            boolean exists = false;
            for (PackageReference ref : references.values()) {
                if (!ref.isEmpty) {
                    if (exists) {
                        throw new RuntimeException("Multiple modules to contain package "
                                + getName());
                    } else {
                        exists = true;
                    }
                }
            }
        }
    }

    /**
     * Tree of nodes.
     */
    private static final class Tree {

        private final Map<String, Node> directAccess = new HashMap<>();
        private final List<String> paths;
        private final Node root;
        private Node modules;
        private Node packages;

        private Tree(List<String> paths) {
            this.paths = paths;
            root = new Node("", null);
            buildTree();
        }

        private void buildTree() {
            modules = new Node("modules", root);
            directAccess.put(modules.getPath(), modules);

            Map<String, Set<String>> moduleToPackage = new TreeMap<>();
            Map<String, Set<String>> packageToModule = new TreeMap<>();

            for (String p : paths) {
                if (!p.startsWith("/")) {
                    continue;
                }
                String[] split = p.split("/");
                // minimum length is 3 items: /<mod>/<pkg>
                if (split.length < 3) {
                    System.err.println("Resources tree, invalid data structure, "
                            + "skipping " + p);
                    continue;
                }
                Node current = modules;
                String module = null;
                for (int i = 0; i < split.length; i++) {
                    // When a non terminal node is marked as being a resource, something is wrong.
                    // It has been observed some badly created jar file to contain
                    // invalid directory entry marled as not directory (see 8131762)
                    if (current instanceof ResourceNode) {
                        System.err.println("Resources tree, invalid data structure, "
                                + "skipping " + p);
                        continue;
                    }
                    String s = split[i];
                    if (!s.isEmpty()) {
                        // First item, this is the module, simply add a new node to the
                        // tree.
                        if (module == null) {
                            module = s;
                        }
                        Node n = current.children.get(s);
                        if (n == null) {
                            if (i == split.length - 1) { // Leaf
                                n = new ResourceNode(s, current);
                                String pkg = toPackageName(n.parent);
                                //System.err.println("Adding a resource node. pkg " + pkg + ", name " + s);
                                if (pkg != null && !pkg.startsWith("META-INF")) {
                                    Set<String> pkgs = moduleToPackage.get(module);
                                    if (pkgs == null) {
                                        pkgs = new TreeSet<>();
                                        moduleToPackage.put(module, pkgs);
                                    }
                                    pkgs.add(pkg);
                                }
                            } else { // put only sub trees, no leaf
                                n = new Node(s, current);
                                directAccess.put(n.getPath(), n);
                                String pkg = toPackageName(n);
                                if (pkg != null && !pkg.startsWith("META-INF")) {
                                    Set<String> mods = packageToModule.get(pkg);
                                    if (mods == null) {
                                        mods = new TreeSet<>();
                                        packageToModule.put(pkg, mods);
                                    }
                                    mods.add(module);
                                }
                            }
                        }
                        current = n;
                    }
                }
            }
            packages = new Node("packages", root);
            directAccess.put(packages.getPath(), packages);
            // The subset of package nodes that have some content.
            // These packages exist only in a single module.
            for (Map.Entry<String, Set<String>> entry : moduleToPackage.entrySet()) {
                for (String pkg : entry.getValue()) {
                    PackageNode pkgNode = new PackageNode(pkg, packages);
                    pkgNode.addReference(entry.getKey(), false);
                    directAccess.put(pkgNode.getPath(), pkgNode);
                }
            }

            // All packages
            for (Map.Entry<String, Set<String>> entry : packageToModule.entrySet()) {
                // Do we already have a package node?
                PackageNode pkgNode = (PackageNode) packages.getChildren(entry.getKey());
                if (pkgNode == null) {
                    pkgNode = new PackageNode(entry.getKey(), packages);
                }
                for (String module : entry.getValue()) {
                    pkgNode.addReference(module, true);
                }
                directAccess.put(pkgNode.getPath(), pkgNode);
            }
            // Validate that the packages are well formed.
            for (Node n : packages.children.values()) {
                PackageNode pkg = (PackageNode) n;
                pkg.validate();
            }

        }

        public String toResourceName(Node node) {
            if (!node.children.isEmpty()) {
                throw new RuntimeException("Node is not a resource");
            }
            return removeRadical(node);
        }

        public String getModule(Node node) {
            if (node.parent == null || node.getName().equals("modules")
                    || node.getName().startsWith("packages")) {
                return null;
            }
            String path = removeRadical(node);
            // "/xxx/...";
            path = path.substring(1);
            int i = path.indexOf("/");
            if (i == -1) {
                return path;
            } else {
                return path.substring(0, i);
            }
        }

        public String toPackageName(Node node) {
            if (node.parent == null) {
                return null;
            }
            String path = removeRadical(node.getPath(), "/modules/");
            String module = getModule(node);
            if (path.equals(module)) {
                return null;
            }
            String pkg = removeRadical(path, module + "/");
            return pkg.replaceAll("/", ".");
        }

        public String removeRadical(Node node) {
            return removeRadical(node.getPath(), "/modules");
        }

        private String removeRadical(String path, String str) {
            if (!(path.length() < str.length())) {
                path = path.substring(str.length());
            }
            return path;
        }

        public Node getRoot() {
            return root;
        }

        public Map<String, Node> getMap() {
            return directAccess;
        }
    }

    private static final class LocationsAdder {

        private long offset;
        private final List<byte[]> content = new ArrayList<>();
        private final BasicImageWriter writer;
        private final Tree tree;

        LocationsAdder(Tree tree, long offset, BasicImageWriter writer) {
            this.tree = tree;
            this.offset = offset;
            this.writer = writer;
            addLocations(tree.getRoot());
        }

        private int addLocations(Node current) {
            if (current instanceof PackageNode) {
                PackageNode pkgNode = (PackageNode) current;
                int size = pkgNode.references.size() * 8;
                writer.addLocation(current.getPath(), offset, 0, size);
                offset += size;
            } else {
                int[] ret = new int[current.children.size()];
                int i = 0;
                for (java.util.Map.Entry<String, Node> entry : current.children.entrySet()) {
                    ret[i] = addLocations(entry.getValue());
                    i += 1;
                }
                if (current != tree.getRoot() && !(current instanceof ResourceNode)) {
                    int size = ret.length * 4;
                    writer.addLocation(current.getPath(), offset, 0, size);
                    offset += size;
                }
            }
            return 0;
        }

        private List<byte[]> computeContent() {
            // Map used to associate Tree item with locations offset.
            Map<String, ImageLocationWriter> outLocations = new HashMap<>();
            for (ImageLocationWriter wr : writer.getLocations()) {
                outLocations.put(wr.getFullName(), wr);
            }
            // Attach location to node
            for (Map.Entry<String, ImageLocationWriter> entry : outLocations.entrySet()) {
                Node item = tree.getMap().get(entry.getKey());
                if (item != null) {
                    item.loc = entry.getValue();
                }
            }
            computeContent(tree.getRoot(), outLocations);
            return content;
        }

        private int computeContent(Node current, Map<String, ImageLocationWriter> outLocations) {
            if (current instanceof PackageNode) {
                // /packages/<pkg name>
                PackageNode pkgNode = (PackageNode) current;
                int size = pkgNode.references.size() * 8;
                ByteBuffer buff = ByteBuffer.allocate(size);
                buff.order(writer.getByteOrder());
                for (PackageNode.PackageReference mod : pkgNode.references.values()) {
                    buff.putInt(mod.isEmpty ? 1 : 0);
                    buff.putInt(writer.addString(mod.name));
                }
                byte[] arr = buff.array();
                content.add(arr);
                current.loc = outLocations.get(current.getPath());
            } else {
                int[] ret = new int[current.children.size()];
                int i = 0;
                for (java.util.Map.Entry<String, Node> entry : current.children.entrySet()) {
                    ret[i] = computeContent(entry.getValue(), outLocations);
                    i += 1;
                }
                if (ret.length > 0) {
                    int size = ret.length * 4;
                    ByteBuffer buff = ByteBuffer.allocate(size);
                    buff.order(writer.getByteOrder());
                    for (int val : ret) {
                        buff.putInt(val);
                    }
                    byte[] arr = buff.array();
                    content.add(arr);
                } else {
                    if (current instanceof ResourceNode) {
                        // A resource location, remove "/modules"
                        String s = tree.toResourceName(current);
                        current.loc = outLocations.get(s);
                    } else {
                        // empty "/packages" or empty "/modules" paths
                        current.loc = outLocations.get(current.getPath());
                    }
                }
                if (current.loc == null && current != tree.getRoot()) {
                    System.err.println("Invalid path in metadata, skipping " + current.getPath());
                }
            }
            return current.loc == null ? 0 : current.loc.getLocationOffset();
        }
    }

    private final List<String> paths;
    private final LocationsAdder adder;

    public ImageResourcesTree(long offset, BasicImageWriter writer, List<String> paths) {
        this.paths = new ArrayList<>();
        this.paths.addAll(paths);
        Collections.sort(this.paths);
        Tree tree = new Tree(this.paths);
        adder = new LocationsAdder(tree, offset, writer);
    }

    public void addContent(DataOutputStream out) throws IOException {
        List<byte[]> content = adder.computeContent();
        for (byte[] c : content) {
            out.write(c, 0, c.length);
        }
    }
}