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 jdk.internal.jimage.ImageLocation;
28 import jdk.internal.jimage.ModuleReference;
29
30 import java.io.DataOutputStream;
31 import java.io.IOException;
32 import java.nio.ByteBuffer;
33 import java.util.ArrayList;
34 import java.util.Collections;
35 import java.util.Comparator;
36 import java.util.HashMap;
37 import java.util.HashSet;
38 import java.util.List;
39 import java.util.Map;
40 import java.util.Objects;
41 import java.util.Set;
42 import java.util.TreeMap;
43 import java.util.stream.Collectors;
44
45 /**
46 * A class to build a sorted tree of Resource paths as a tree of ImageLocation.
47 */
48 // XXX Public only due to the JImageTask / JImageTask code duplication
49 public final class ImageResourcesTree {
50 /**
51 * Path item tree node.
52 */
53 // Visible for testing only.
54 static class Node {
55
56 private final String name;
57 private final Map<String, Node> children = new TreeMap<>();
58 private final Node parent;
59 private ImageLocationWriter loc;
60
61 private Node(String name, Node parent) {
62 this.name = name;
63 this.parent = parent;
64
65 if (parent != null) {
66 parent.children.put(name, this);
67 }
68 }
69
70 private void setLocation(ImageLocationWriter loc) {
71 // This *can* be called more than once, but only with the same instance.
72 if (this.loc != null && loc != this.loc) {
73 throw new IllegalStateException("Cannot add different locations: " + name);
74 }
75 this.loc = Objects.requireNonNull(loc);
76 }
77
78 public String getPath() {
79 if (parent == null) {
80 return "/";
81 }
82 return buildPath(this);
83 }
84
85 public String getName() {
86 return name;
87 }
88
89 public Node getChildren(String name) {
90 Node item = children.get(name);
91 return item;
92 }
93
94 private static String buildPath(Node item) {
95 if (item == null) {
96 return null;
97 }
98 String path = buildPath(item.parent);
99 if (path == null) {
100 return item.getName();
101 } else {
102 return path + "/" + item.getName();
103 }
104 }
105 }
106
107 // Visible for testing only.
108 static final class ResourceNode extends Node {
109
110 public ResourceNode(String name, Node parent) {
111 super(name, parent);
112 }
113 }
114
115 /**
116 * A 2nd level package directory, {@code "/packages/<package-name>"}.
117 *
118 * <p>While package paths can exist within many modules, for each package
119 * there is at most one module in which that package has resources.
120 *
121 * <p>For example, the package path {@code java/util} exists in both the
122 * {@code java.base} and {@code java.logging} modules. This means both
123 * {@code "/packages/java.util/java.base"} and
124 * {@code "/packages/java.util/java.logging"} will exist, but only
125 * {@code "java.base"} entry will be marked as having content.
126 *
127 * <p>When processing module references in non-preview mode, entries marked
128 * as {@link ModuleReference#isPreviewOnly() preview-only} must be ignored.
129 *
130 * <p>If all references in a package are preview-only, then the entire
131 * package is marked as preview-only, and must be ignored.
132 */
133 // Visible for testing only.
134 static final class PackageNode extends Node {
135 private final List<ModuleReference> moduleReferences;
136
137 PackageNode(String name, List<ModuleReference> moduleReferences, Node parent) {
138 super(name, parent);
139 if (moduleReferences.isEmpty()) {
140 throw new IllegalStateException("Package must be associated with modules: " + name);
141 }
142 if (moduleReferences.stream().filter(ModuleReference::hasResources).count() > 1) {
143 throw new IllegalStateException("Multiple modules contain non-empty package: " + name);
144 }
145 this.moduleReferences = Collections.unmodifiableList(moduleReferences);
146 }
147
148 List<ModuleReference> getModuleReferences() {
149 return moduleReferences;
150 }
151 }
152
153 // Not serialized, and never stored in any field of any class that is.
154 @SuppressWarnings("serial")
155 private static final class InvalidTreeException extends Exception {
156 public InvalidTreeException(Node badNode) {
157 super("Resources tree, invalid data structure, skipping: " + badNode.getPath());
158 }
159 // Exception only used for program flow, not debugging.
160 @Override
161 public Throwable fillInStackTrace() {return this;}
162 }
163
164 /**
165 * Tree of nodes.
166 */
167 // Visible for testing only.
168 static final class Tree {
169 private static final String PREVIEW_PREFIX = "META-INF/preview/";
170
171 private final Map<String, Node> directAccess = new HashMap<>();
172 private final List<String> paths;
173 private final Node root;
174 private Node packagesRoot;
175
176 // Visible for testing only.
177 Tree(List<String> paths) {
178 this.paths = paths.stream().sorted(Comparator.reverseOrder()).toList();
179 // Root node is not added to the directAccess map.
180 root = new Node("", null);
181 buildTree();
182 }
183
184 private void buildTree() {
185 Node modulesRoot = new Node("modules", root);
186 directAccess.put(modulesRoot.getPath(), modulesRoot);
187 packagesRoot = new Node("packages", root);
188 directAccess.put(packagesRoot.getPath(), packagesRoot);
189
190 // Map of dot-separated package names to module references (those
191 // in which the package appear). References are merged after to
192 // ensure each module name appears only once, but temporarily a
193 // module may have several entries per package (e.g. with-content,
194 // without-content, normal, preview-only etc..).
195 Map<String, Set<ModuleReference>> packageToModules = new TreeMap<>();
196 for (String fullPath : paths) {
197 try {
198 processPath(fullPath, modulesRoot, packageToModules);
199 } catch (InvalidTreeException ex) {
200 // It has been observed some badly created jar file to contain
201 // invalid directory entry marked as not directory (see 8131762).
202 System.err.println(ex.getMessage());
203 }
204 }
205
206 // We've collected information for all "packages", including the root
207 // (empty) package and anything under "META-INF". However, these should
208 // not have entries in the "/packages" directory.
209 packageToModules.keySet().removeIf(p -> p.isEmpty() || p.equals("META-INF") || p.startsWith("META-INF."));
210 packageToModules.forEach((pkgName, modRefs) -> {
211 // Merge multiple refs for the same module.
212 List<ModuleReference> pkgModules = modRefs.stream()
213 .collect(Collectors.groupingBy(ModuleReference::name))
214 .values().stream()
215 .map(refs -> refs.stream().reduce(ModuleReference::merge).orElseThrow())
216 .sorted()
217 .toList();
218 PackageNode pkgNode = new PackageNode(pkgName, pkgModules, packagesRoot);
219 directAccess.put(pkgNode.getPath(), pkgNode);
220 });
221 }
222
223 private void processPath(
224 String fullPath,
225 Node modulesRoot,
226 Map<String, Set<ModuleReference>> packageToModules)
227 throws InvalidTreeException {
228 // Paths are untrusted, so be careful about checking expected format.
229 if (!fullPath.startsWith("/") || fullPath.endsWith("/") || fullPath.contains("//")) {
230 return;
231 }
232 int modEnd = fullPath.indexOf('/', 1);
233 // Ensure non-empty module name with non-empty suffix.
234 if (modEnd <= 1) {
235 return;
236 }
237 String modName = fullPath.substring(1, modEnd);
238 String pkgPath = fullPath.substring(modEnd + 1);
239
240 Node parentNode = getDirectoryNode(modName, modulesRoot);
241 boolean isPreviewPath = false;
242 if (pkgPath.startsWith(PREVIEW_PREFIX)) {
243 // For preview paths, process nodes relative to the preview directory.
244 pkgPath = pkgPath.substring(PREVIEW_PREFIX.length());
245 Node metaInf = getDirectoryNode("META-INF", parentNode);
246 parentNode = getDirectoryNode("preview", metaInf);
247 isPreviewPath = true;
248 }
249
250 int pathEnd = pkgPath.lastIndexOf('/');
251 // From invariants tested above, this must now be well-formed.
252 String fullPkgName = (pathEnd == -1) ? "" : pkgPath.substring(0, pathEnd).replace('/', '.');
253 String resourceName = pkgPath.substring(pathEnd + 1);
254 // Intermediate packages are marked "empty" (no resources). This might
255 // later be merged with a non-empty reference for the same package.
256 ModuleReference emptyRef = ModuleReference.forEmptyPackage(modName, isPreviewPath);
257
258 // Work down through empty packages to final resource.
259 for (int i = pkgEndIndex(fullPkgName, 0); i != -1; i = pkgEndIndex(fullPkgName, i)) {
260 // Due to invariants already checked, pkgName is non-empty.
261 String pkgName = fullPkgName.substring(0, i);
262 packageToModules.computeIfAbsent(pkgName, p -> new HashSet<>()).add(emptyRef);
263 String childNodeName = pkgName.substring(pkgName.lastIndexOf('.') + 1);
264 parentNode = getDirectoryNode(childNodeName, parentNode);
265 }
266 // Reached non-empty (leaf) package (could still be a duplicate).
267 Node resourceNode = parentNode.getChildren(resourceName);
268 if (resourceNode == null) {
269 ModuleReference resourceRef = ModuleReference.forPackage(modName, isPreviewPath);
270 packageToModules.computeIfAbsent(fullPkgName, p -> new HashSet<>()).add(resourceRef);
271 // Init adds new node to parent (don't add resources to directAccess).
272 new ResourceNode(resourceName, parentNode);
273 } else if (!(resourceNode instanceof ResourceNode)) {
274 throw new InvalidTreeException(resourceNode);
275 }
276 }
277
278 private Node getDirectoryNode(String name, Node parent) throws InvalidTreeException {
279 Node child = parent.getChildren(name);
280 if (child == null) {
281 // Adds child to parent during init.
282 child = new Node(name, parent);
283 directAccess.put(child.getPath(), child);
284 } else if (child instanceof ResourceNode) {
285 throw new InvalidTreeException(child);
286 }
287 return child;
288 }
289
290 // Helper to iterate package names up to, and including, the complete name.
291 private int pkgEndIndex(String s, int i) {
292 if (i >= 0 && i < s.length()) {
293 i = s.indexOf('.', i + 1);
294 return i != -1 ? i : s.length();
295 }
296 return -1;
297 }
298
299 private String toResourceName(Node node) {
300 if (!node.children.isEmpty()) {
301 throw new RuntimeException("Node is not a resource");
302 }
303 return removeRadical(node);
304 }
305
306 private 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 List<ModuleReference> refs = ((PackageNode) current).getModuleReferences();
343 // "/packages/<pkg name>" entries have 8-byte entries (flags+offset).
344 int size = refs.size() * 8;
345 writer.addLocation(current.getPath(), offset, 0, size, ImageLocation.getPackageFlags(refs));
346 offset += size;
347 } else {
348 int[] ret = new int[current.children.size()];
349 int i = 0;
350 for (java.util.Map.Entry<String, Node> entry : current.children.entrySet()) {
351 ret[i] = addLocations(entry.getValue());
352 i += 1;
353 }
354 if (current != tree.getRoot() && !(current instanceof ResourceNode)) {
355 int locFlags = ImageLocation.getFlags(current.getPath(), tree.directAccess::containsKey);
356 // Normal directory entries have 4-byte entries (offset only).
357 int size = ret.length * 4;
358 writer.addLocation(current.getPath(), offset, 0, size, locFlags);
359 offset += size;
360 }
361 }
362 return 0;
363 }
364
365 private List<byte[]> computeContent() {
366 // Map used to associate Tree item with locations offset.
367 Map<String, ImageLocationWriter> outLocations = new HashMap<>();
368 for (ImageLocationWriter wr : writer.getLocations()) {
369 outLocations.put(wr.getFullName(), wr);
370 }
371 // Attach location to node
372 for (Map.Entry<String, ImageLocationWriter> entry : outLocations.entrySet()) {
373 Node item = tree.getMap().get(entry.getKey());
374 if (item != null) {
375 item.setLocation(entry.getValue());
376 }
377 }
378 computeContent(tree.getRoot(), outLocations);
379 return content;
380 }
381
382 private int computeContent(Node current, Map<String, ImageLocationWriter> outLocations) {
383 if (current instanceof PackageNode) {
384 // "/packages/<pkg name>" entries have 8-byte entries (flags+offset).
385 List<ModuleReference> refs = ((PackageNode) current).getModuleReferences();
386 ByteBuffer byteBuffer = ByteBuffer.allocate(8 * refs.size());
387 byteBuffer.order(writer.getByteOrder());
388 ModuleReference.write(refs, byteBuffer.asIntBuffer(), writer::addString);
389 content.add(byteBuffer.array());
390 current.setLocation(outLocations.get(current.getPath()));
391 } else {
392 int[] ret = new int[current.children.size()];
393 int i = 0;
394 for (java.util.Map.Entry<String, Node> entry : current.children.entrySet()) {
395 ret[i] = computeContent(entry.getValue(), outLocations);
396 i += 1;
397 }
398 if (ret.length > 0) {
399 int size = ret.length * 4;
400 ByteBuffer buff = ByteBuffer.allocate(size);
401 buff.order(writer.getByteOrder());
402 for (int val : ret) {
403 buff.putInt(val);
404 }
405 byte[] arr = buff.array();
406 content.add(arr);
407 } else {
408 if (current instanceof ResourceNode) {
409 // A resource location, remove "/modules"
410 String s = tree.toResourceName(current);
411 current.setLocation(outLocations.get(s));
412 } else {
413 // empty "/packages" or empty "/modules" paths
414 current.setLocation(outLocations.get(current.getPath()));
415 }
416 }
417 if (current.loc == null && current != tree.getRoot()) {
418 System.err.println("Invalid path in metadata, skipping " + current.getPath());
419 }
420 }
421 return current.loc == null ? 0 : current.loc.getLocationOffset();
422 }
423 }
424
425 private final List<String> paths;
426 private final LocationsAdder adder;
427
428 public ImageResourcesTree(long offset, BasicImageWriter writer, List<String> paths) {
429 this.paths = new ArrayList<>();
430 this.paths.addAll(paths);
431 Collections.sort(this.paths);
432 Tree tree = new Tree(this.paths);
433 adder = new LocationsAdder(tree, offset, writer);
434 }
435
436 public void addContent(DataOutputStream out) throws IOException {
437 List<byte[]> content = adder.computeContent();
438 for (byte[] c : content) {
439 out.write(c, 0, c.length);
440 }
441 }
442 }