1 /*
2 * Copyright (c) 2014, 2025, 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.tools.jlink.internal;
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.Objects;
36 import java.util.Set;
37 import java.util.TreeMap;
38 import java.util.TreeSet;
39
40 /**
41 * A class to build a sorted tree of Resource paths as a tree of ImageLocation.
42 *
43 */
44 // XXX Public only due to the JImageTask / JImageTask code duplication
45 public final class ImageResourcesTree {
46 public static boolean isTreeInfoResource(String path) {
47 return path.startsWith("/packages") || path.startsWith("/modules");
48 }
49
50 /**
51 * Path item tree node.
52 */
53 private static class Node {
54
55 private final String name;
56 private final Map<String, Node> children = new TreeMap<>();
57 private final Node parent;
58 private ImageLocationWriter loc;
59
60 private Node(String name, Node parent) {
61 this.name = name;
62 this.parent = parent;
63
64 if (parent != null) {
65 parent.children.put(name, this);
66 }
67 }
68
69 public String getPath() {
70 if (parent == null) {
71 return "/";
72 }
73 return buildPath(this);
74 }
75
76 public String getName() {
77 return name;
78 }
79
80 public Node getChildren(String name) {
81 Node item = children.get(name);
82 return item;
83 }
84
85 private static String buildPath(Node item) {
86 if (item == null) {
87 return null;
88 }
89 String path = buildPath(item.parent);
90 if (path == null) {
91 return item.getName();
92 } else {
93 return path + "/" + item.getName();
94 }
95 }
96 }
97
98 private static final class ResourceNode extends Node {
99
100 public ResourceNode(String name, Node parent) {
101 super(name, parent);
102 }
103 }
104
105 private static class PackageNode extends Node {
106 /**
107 * A reference to a package. Empty packages can be located inside one or
108 * more modules. A package with classes exist in only one module.
109 */
110 static final class PackageReference {
111
112 private final String name;
113 private final boolean isEmpty;
114
115 PackageReference(String name, boolean isEmpty) {
116 this.name = Objects.requireNonNull(name);
117 this.isEmpty = isEmpty;
118 }
119
120 @Override
121 public String toString() {
122 return name + "[empty:" + isEmpty + "]";
123 }
124 }
125
126 private final Map<String, PackageReference> references = new TreeMap<>();
127
128 PackageNode(String name, Node parent) {
129 super(name, parent);
130 }
131
132 private void addReference(String name, boolean isEmpty) {
133 PackageReference ref = references.get(name);
134 if (ref == null || ref.isEmpty) {
135 references.put(name, new PackageReference(name, isEmpty));
136 }
137 }
138
139 private void validate() {
140 boolean exists = false;
141 for (PackageReference ref : references.values()) {
142 if (!ref.isEmpty) {
143 if (exists) {
144 throw new RuntimeException("Multiple modules to contain package "
145 + getName());
146 } else {
147 exists = true;
148 }
149 }
150 }
151 }
152 }
153
154 /**
155 * Tree of nodes.
156 */
157 private static final class Tree {
158
159 private final Map<String, Node> directAccess = new HashMap<>();
160 private final List<String> paths;
161 private final Node root;
162 private Node modules;
163 private Node packages;
164
165 private Tree(List<String> paths) {
166 this.paths = paths;
167 root = new Node("", null);
168 buildTree();
169 }
170
171 private void buildTree() {
172 modules = new Node("modules", root);
173 directAccess.put(modules.getPath(), modules);
174
175 Map<String, Set<String>> moduleToPackage = new TreeMap<>();
176 Map<String, Set<String>> packageToModule = new TreeMap<>();
177
178 for (String p : paths) {
179 if (!p.startsWith("/")) {
180 continue;
181 }
182 String[] split = p.split("/");
183 // minimum length is 3 items: /<mod>/<pkg>
184 if (split.length < 3) {
185 System.err.println("Resources tree, invalid data structure, "
186 + "skipping " + p);
187 continue;
188 }
189 Node current = modules;
190 String module = null;
191 for (int i = 0; i < split.length; i++) {
192 // When a non terminal node is marked as being a resource, something is wrong.
193 // It has been observed some badly created jar file to contain
194 // invalid directory entry marled as not directory (see 8131762)
195 if (current instanceof ResourceNode) {
196 System.err.println("Resources tree, invalid data structure, "
197 + "skipping " + p);
198 continue;
199 }
200 String s = split[i];
201 if (!s.isEmpty()) {
202 // First item, this is the module, simply add a new node to the
203 // tree.
204 if (module == null) {
205 module = s;
206 }
207 Node n = current.children.get(s);
208 if (n == null) {
209 if (i == split.length - 1) { // Leaf
210 n = new ResourceNode(s, current);
211 String pkg = toPackageName(n.parent);
212 //System.err.println("Adding a resource node. pkg " + pkg + ", name " + s);
213 if (pkg != null && !pkg.startsWith("META-INF")) {
214 Set<String> pkgs = moduleToPackage.get(module);
215 if (pkgs == null) {
216 pkgs = new TreeSet<>();
217 moduleToPackage.put(module, pkgs);
218 }
219 pkgs.add(pkg);
220 }
221 } else { // put only sub trees, no leaf
222 n = new Node(s, current);
223 directAccess.put(n.getPath(), n);
224 String pkg = toPackageName(n);
225 if (pkg != null && !pkg.startsWith("META-INF")) {
226 Set<String> mods = packageToModule.get(pkg);
227 if (mods == null) {
228 mods = new TreeSet<>();
229 packageToModule.put(pkg, mods);
230 }
231 mods.add(module);
232 }
233 }
234 }
235 current = n;
236 }
237 }
238 }
239 packages = new Node("packages", root);
240 directAccess.put(packages.getPath(), packages);
241 // The subset of package nodes that have some content.
242 // These packages exist only in a single module.
243 for (Map.Entry<String, Set<String>> entry : moduleToPackage.entrySet()) {
244 for (String pkg : entry.getValue()) {
245 PackageNode pkgNode = new PackageNode(pkg, packages);
246 pkgNode.addReference(entry.getKey(), false);
247 directAccess.put(pkgNode.getPath(), pkgNode);
248 }
249 }
250
251 // All packages
252 for (Map.Entry<String, Set<String>> entry : packageToModule.entrySet()) {
253 // Do we already have a package node?
254 PackageNode pkgNode = (PackageNode) packages.getChildren(entry.getKey());
255 if (pkgNode == null) {
256 pkgNode = new PackageNode(entry.getKey(), packages);
257 }
258 for (String module : entry.getValue()) {
259 pkgNode.addReference(module, true);
260 }
261 directAccess.put(pkgNode.getPath(), pkgNode);
262 }
263 // Validate that the packages are well formed.
264 for (Node n : packages.children.values()) {
265 ((PackageNode)n).validate();
266 }
267
268 }
269
270 public String toResourceName(Node node) {
271 if (!node.children.isEmpty()) {
272 throw new RuntimeException("Node is not a resource");
273 }
274 return removeRadical(node);
275 }
276
277 public String getModule(Node node) {
278 if (node.parent == null || node.getName().equals("modules")
279 || node.getName().startsWith("packages")) {
280 return null;
281 }
282 String path = removeRadical(node);
283 // "/xxx/...";
284 path = path.substring(1);
285 int i = path.indexOf("/");
286 if (i == -1) {
287 return path;
288 } else {
289 return path.substring(0, i);
290 }
291 }
292
293 public String toPackageName(Node node) {
294 if (node.parent == null) {
295 return null;
296 }
297 String path = removeRadical(node.getPath(), "/modules/");
298 String module = getModule(node);
299 if (path.equals(module)) {
300 return null;
301 }
302 String pkg = removeRadical(path, module + "/");
303 return pkg.replace('/', '.');
304 }
305
306 public String removeRadical(Node node) {
307 return removeRadical(node.getPath(), "/modules");
308 }
309
310 private String removeRadical(String path, String str) {
311 if (!(path.length() < str.length())) {
312 path = path.substring(str.length());
313 }
314 return path;
315 }
316
317 public Node getRoot() {
318 return root;
319 }
320
321 public Map<String, Node> getMap() {
322 return directAccess;
323 }
324 }
325
326 private static final class LocationsAdder {
327
328 private long offset;
329 private final List<byte[]> content = new ArrayList<>();
330 private final BasicImageWriter writer;
331 private final Tree tree;
332
333 LocationsAdder(Tree tree, long offset, BasicImageWriter writer) {
334 this.tree = tree;
335 this.offset = offset;
336 this.writer = writer;
337 addLocations(tree.getRoot());
338 }
339
340 private int addLocations(Node current) {
341 if (current instanceof PackageNode) {
342 PackageNode pkgNode = (PackageNode) current;
343 int size = pkgNode.references.size() * 8;
344 writer.addLocation(current.getPath(), offset, 0, size);
345 offset += size;
346 } else {
347 int[] ret = new int[current.children.size()];
348 int i = 0;
349 for (java.util.Map.Entry<String, Node> entry : current.children.entrySet()) {
350 ret[i] = addLocations(entry.getValue());
351 i += 1;
352 }
353 if (current != tree.getRoot() && !(current instanceof ResourceNode)) {
354 int size = ret.length * 4;
355 writer.addLocation(current.getPath(), offset, 0, size);
356 offset += size;
357 }
358 }
359 return 0;
360 }
361
362 private List<byte[]> computeContent() {
363 // Map used to associate Tree item with locations offset.
364 Map<String, ImageLocationWriter> outLocations = new HashMap<>();
365 for (ImageLocationWriter wr : writer.getLocations()) {
366 outLocations.put(wr.getFullName(), wr);
367 }
368 // Attach location to node
369 for (Map.Entry<String, ImageLocationWriter> entry : outLocations.entrySet()) {
370 Node item = tree.getMap().get(entry.getKey());
371 if (item != null) {
372 item.loc = entry.getValue();
373 }
374 }
375 computeContent(tree.getRoot(), outLocations);
376 return content;
377 }
378
379 private int computeContent(Node current, Map<String, ImageLocationWriter> outLocations) {
380 if (current instanceof PackageNode) {
381 // /packages/<pkg name>
382 PackageNode pkgNode = (PackageNode) current;
383 int size = pkgNode.references.size() * 8;
384 ByteBuffer buff = ByteBuffer.allocate(size);
385 buff.order(writer.getByteOrder());
386 for (PackageNode.PackageReference mod : pkgNode.references.values()) {
387 buff.putInt(mod.isEmpty ? 1 : 0);
388 buff.putInt(writer.addString(mod.name));
389 }
390 byte[] arr = buff.array();
391 content.add(arr);
392 current.loc = outLocations.get(current.getPath());
393 } else {
394 int[] ret = new int[current.children.size()];
395 int i = 0;
396 for (java.util.Map.Entry<String, Node> entry : current.children.entrySet()) {
397 ret[i] = computeContent(entry.getValue(), outLocations);
398 i += 1;
399 }
400 if (ret.length > 0) {
401 int size = ret.length * 4;
402 ByteBuffer buff = ByteBuffer.allocate(size);
403 buff.order(writer.getByteOrder());
404 for (int val : ret) {
405 buff.putInt(val);
406 }
407 byte[] arr = buff.array();
408 content.add(arr);
409 } else {
410 if (current instanceof ResourceNode) {
411 // A resource location, remove "/modules"
412 String s = tree.toResourceName(current);
413 current.loc = outLocations.get(s);
414 } else {
415 // empty "/packages" or empty "/modules" paths
416 current.loc = outLocations.get(current.getPath());
417 }
418 }
419 if (current.loc == null && current != tree.getRoot()) {
420 System.err.println("Invalid path in metadata, skipping " + current.getPath());
421 }
422 }
423 return current.loc == null ? 0 : current.loc.getLocationOffset();
424 }
425 }
426
427 private final List<String> paths;
428 private final LocationsAdder adder;
429
430 public ImageResourcesTree(long offset, BasicImageWriter writer, List<String> paths) {
431 this.paths = new ArrayList<>();
432 this.paths.addAll(paths);
433 Collections.sort(this.paths);
434 Tree tree = new Tree(this.paths);
435 adder = new LocationsAdder(tree, offset, writer);
436 }
437
438 public void addContent(DataOutputStream out) throws IOException {
439 List<byte[]> content = adder.computeContent();
440 for (byte[] c : content) {
441 out.write(c, 0, c.length);
442 }
443 }
444 }