001/*
002 * Copyright (c) 1998, 2022, Oracle and/or its affiliates. All rights reserved.
003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
004 *
005 * This code is free software; you can redistribute it and/or modify it
006 * under the terms of the GNU General Public License version 2 only, as
007 * published by the Free Software Foundation.  Oracle designates this
008 * particular file as subject to the "Classpath" exception as provided
009 * by Oracle in the LICENSE file that accompanied this code.
010 *
011 * This code is distributed in the hope that it will be useful, but WITHOUT
012 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
013 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
014 * version 2 for more details (a copy is included in the LICENSE file that
015 * accompanied this code).
016 *
017 * You should have received a copy of the GNU General Public License version
018 * 2 along with this work; if not, write to the Free Software Foundation,
019 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
020 *
021 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
022 * or visit www.oracle.com if you need additional information or have any
023 * questions.
024 */
025
026package org.jdrupes.mdoclet.internal.doclets.toolkit.util;
027
028import java.util.ArrayList;
029import java.util.Collections;
030import java.util.Comparator;
031import java.util.EnumMap;
032import java.util.HashMap;
033import java.util.List;
034import java.util.Map;
035import java.util.Set;
036import java.util.SortedSet;
037import java.util.TreeSet;
038
039import javax.lang.model.element.Element;
040import javax.lang.model.element.TypeElement;
041import javax.lang.model.type.TypeMirror;
042
043import org.jdrupes.mdoclet.internal.doclets.toolkit.BaseConfiguration;
044import org.jdrupes.mdoclet.internal.doclets.toolkit.Messages;
045
046/**
047 * Class and interface hierarchies.
048 */
049public class ClassTree {
050
051    /**
052     * The kind of hierarchy.
053     * Currently, the kinds correspond to the kinds of declared types,
054     * although other partitions could be possible.
055     */
056    private enum HierarchyKind {
057        CLASSES, ENUM_CLASSES, RECORD_CLASSES, INTERFACES, ANNOTATION_INTERFACES
058    }
059
060    /**
061     * A "hierarchy" provides the subtypes of all the supertypes of a set of leaf elements,
062     * together with the root supertype(s).
063     */
064    public static class Hierarchy {
065        private final SortedSet<TypeElement> roots;
066        private final SubtypeMap subtypes;
067        private final Comparator<Element> comparator;
068
069        Hierarchy(Comparator<Element> comparator) {
070            this.comparator = comparator;
071            roots = new TreeSet<>(comparator);
072            subtypes = new SubtypeMap(comparator);
073        }
074
075        /**
076         * {@return the roots of the hierarchy}
077         * Each root is a class or interface with no superclass or superinterfaces.
078         * If the hierarchy just contains classes, the root will be {@code java.lang.Object}.
079         */
080        public SortedSet<TypeElement> roots() {
081            return roots;
082        }
083
084        /**
085         * {@return the immediate subtypes of the given type element, or an empty set if there are none}
086         * @param typeElement the type element
087         */
088        public SortedSet<TypeElement> subtypes(TypeElement typeElement) {
089            return subtypes.getOrDefault(typeElement,
090                Collections.emptySortedSet());
091        }
092
093        /**
094         * {@return the set of all subtypes of the given type element, or an empty set if there are none}
095         *
096         * The set of all subtypes is the transitive closure of the {@linkplain #subtypes(TypeElement) immediate subtypes}
097         * of the given type element.
098         *
099         * @param typeElement the type element
100         */
101        public SortedSet<TypeElement> allSubtypes(TypeElement typeElement) {
102            // new entries added to the collection are searched as well;
103            // this is really a work queue.
104            List<TypeElement> list = new ArrayList<>(subtypes(typeElement));
105            for (int i = 0; i < list.size(); i++) {
106                var subtypes = subtypes(list.get(i));
107                for (var subtype : subtypes) {
108                    if (!list.contains(subtype)) {
109                        list.add(subtype);
110                    }
111                }
112            }
113            SortedSet<TypeElement> out = new TreeSet<>(comparator);
114            out.addAll(list);
115            return out;
116        }
117    }
118
119    /**
120     * A map giving the subtypes for each of a collection of type elements.
121     * The subtypes may be subclasses or subinterfaces, depending on the context.
122     *
123     * The subtypes are recorded by calling {@link SubtypeMap#addSubtype(TypeElement, TypeElement) addSubtype}.
124     */
125    @SuppressWarnings("serial")
126    private static class SubtypeMap
127            extends HashMap<TypeElement, SortedSet<TypeElement>> {
128        private final Comparator<Element> comparator;
129
130        /**
131         * Creates a map to provide the subtypes of a type element,
132         * sorted according to a given comparator.
133         *
134         * An alternate implementation would be to store the subtypes unsorted,
135         * and to lazily sort them when needed, such as when generating documentation.
136         *
137         * @param comparator the comparator
138         */
139        SubtypeMap(Comparator<Element> comparator) {
140            this.comparator = comparator;
141        }
142
143        /**
144         * {@return the subtypes for a type element, or an empty set if there are none}
145         *
146         * @param typeElement the type element
147         */
148        SortedSet<TypeElement> getSubtypes(TypeElement typeElement) {
149            return computeIfAbsent(typeElement,
150                te -> new TreeSet<>(comparator));
151        }
152
153        /**
154         * Adds a subtype into the set of subtypes for a type element
155         *
156         * @param typeElement the type element
157         * @param subtype the subtype
158         * @return {@code true} if this set did not already contain the specified element
159         */
160        boolean addSubtype(TypeElement typeElement, TypeElement subtype) {
161            return getSubtypes(typeElement).add(subtype);
162        }
163    }
164
165    /**
166     * The collection of hierarchies, indexed by kind.
167     */
168    private final Map<HierarchyKind, Hierarchy> hierarchies;
169
170    /**
171    * Mapping for each interface with classes that implement it.
172    */
173    private final SubtypeMap implementingClasses;
174
175    private final BaseConfiguration configuration;
176    private final Utils utils;
177
178    /**
179     * Constructor. Build the tree for all the included type elements.
180     *
181     * @param configuration the configuration of the doclet
182     */
183    public ClassTree(BaseConfiguration configuration) {
184        this.configuration = configuration;
185        this.utils = configuration.utils;
186
187        Messages messages = configuration.getMessages();
188        messages.notice("doclet.Building_Tree");
189
190        Comparator<Element> comparator
191            = utils.comparators.makeClassUseComparator();
192
193        hierarchies = new EnumMap<>(HierarchyKind.class);
194        for (var hk : HierarchyKind.values()) {
195            hierarchies.put(hk, new Hierarchy(comparator));
196        }
197        implementingClasses = new SubtypeMap(comparator);
198
199        buildTree(configuration.getIncludedTypeElements());
200    }
201
202    /**
203     * Constructor. Build the tree for the given collection of classes.
204     *
205     * @param classesSet a set of classes
206     * @param configuration The current configuration of the doclet.
207     */
208    public ClassTree(SortedSet<TypeElement> classesSet,
209            BaseConfiguration configuration) {
210        this.configuration = configuration;
211        this.utils = configuration.utils;
212
213        Comparator<Element> comparator
214            = utils.comparators.makeClassUseComparator();
215
216        hierarchies = new EnumMap<>(HierarchyKind.class);
217        for (var hk : HierarchyKind.values()) {
218            hierarchies.put(hk, new Hierarchy(comparator));
219        }
220        implementingClasses = new SubtypeMap(comparator);
221
222        buildTree(classesSet);
223    }
224
225    /**
226     * Generate the hierarchies for the given type elements.
227     *
228     * @param typeElements the type elements
229     */
230    private void buildTree(Iterable<TypeElement> typeElements) {
231        for (TypeElement te : typeElements) {
232            // In the tree page (e.g overview-tree.html) do not include
233            // information of classes which are deprecated or are a part of a
234            // deprecated package.
235            if (configuration.getOptions().noDeprecated() &&
236                (utils.isDeprecated(te) ||
237                    utils.isDeprecated(utils.containingPackage(te)))) {
238                continue;
239            }
240
241            if (utils.hasHiddenTag(te)) {
242                continue;
243            }
244
245            if (utils.isEnum(te)) {
246                processType(te, hierarchies.get(HierarchyKind.ENUM_CLASSES));
247            } else if (utils.isRecord(te)) {
248                processType(te, hierarchies.get(HierarchyKind.RECORD_CLASSES));
249            } else if (utils.isClass(te)) {
250                processType(te, hierarchies.get(HierarchyKind.CLASSES));
251            } else if (utils.isPlainInterface(te)) {
252                processInterface(te);
253            } else if (utils.isAnnotationInterface(te)) {
254                processType(te,
255                    hierarchies.get(HierarchyKind.ANNOTATION_INTERFACES));
256            }
257        }
258    }
259
260    /**
261     * Adds details for a type element into a given hierarchy.
262     *
263     * The subtypes are updated for the transitive closure of all supertypes of this type element.
264     * If this type element has no superclass or superinterfaces, it is marked as a root.
265     *
266     * @param typeElement for which the hierarchy is to be generated
267     * @param hierarchy the hierarchy
268     */
269    private void processType(TypeElement typeElement, Hierarchy hierarchy) {
270        TypeElement superclass
271            = utils.getFirstVisibleSuperClassAsTypeElement(typeElement);
272        if (superclass != null) {
273            if (!hierarchy.subtypes.addSubtype(superclass, typeElement)) {
274                return;
275            } else {
276                processType(superclass, hierarchy);
277            }
278        } else {     // typeElement is java.lang.Object, add it once to the set
279            hierarchy.roots.add(typeElement);
280        }
281
282        Set<TypeMirror> interfaces = utils.getAllInterfaces(typeElement);
283        for (TypeMirror t : interfaces) {
284            implementingClasses.addSubtype(utils.asTypeElement(t), typeElement);
285        }
286    }
287
288    /**
289     * For the interface passed get the interfaces which it extends, and then
290     * put this interface in the subinterface set of those interfaces. Do it
291     * recursively. If an interface doesn't have superinterface just attach
292     * that interface in the set of all the baseInterfaces.
293     *
294     * @param typeElement Interface under consideration.
295     */
296    private void processInterface(TypeElement typeElement) {
297        Hierarchy interfacesHierarchy
298            = hierarchies.get(HierarchyKind.INTERFACES);
299        List<? extends TypeMirror> interfaces = typeElement.getInterfaces();
300        if (!interfaces.isEmpty()) {
301            for (TypeMirror t : interfaces) {
302                if (!interfacesHierarchy.subtypes
303                    .addSubtype(utils.asTypeElement(t), typeElement)) {
304                    return;
305                } else {
306                    processInterface(utils.asTypeElement(t));   // Recurse
307                }
308            }
309        } else {
310            // we need to add all the interfaces who do not have
311            // super-interfaces to the root set to traverse them
312            interfacesHierarchy.roots.add(typeElement);
313        }
314    }
315
316    /**
317     * Return the subclass set for the class passed.
318     *
319     * @param typeElement class whose subclass set is required.
320     */
321    public SortedSet<TypeElement> subClasses(TypeElement typeElement) {
322        return hierarchies.get(HierarchyKind.CLASSES).subtypes(typeElement);
323    }
324
325    /**
326     * Return the subinterface set for the interface passed.
327     *
328     * @param typeElement interface whose subinterface set is required.
329     */
330    public SortedSet<TypeElement> subInterfaces(TypeElement typeElement) {
331        return hierarchies.get(HierarchyKind.INTERFACES).subtypes(typeElement);
332    }
333
334    /**
335     * Return the set of classes which implement the interface passed.
336     *
337     * @param typeElement interface whose implementing-classes set is required.
338     */
339    public SortedSet<TypeElement> implementingClasses(TypeElement typeElement) {
340        SortedSet<TypeElement> result
341            = implementingClasses.getSubtypes(typeElement);
342        SortedSet<TypeElement> interfaces
343            = hierarchy(typeElement).allSubtypes(typeElement);
344
345        // If class x implements a subinterface of typeElement, then it follows
346        // that class x implements typeElement.
347        for (TypeElement te : interfaces) {
348            result.addAll(implementingClasses(te));
349        }
350        return result;
351    }
352
353    public Hierarchy hierarchy(TypeElement typeElement) {
354        HierarchyKind hk = switch (typeElement.getKind()) {
355        case CLASS -> HierarchyKind.CLASSES;
356        case ENUM -> HierarchyKind.ENUM_CLASSES;
357        case RECORD -> HierarchyKind.RECORD_CLASSES;
358        case INTERFACE -> HierarchyKind.INTERFACES;
359        case ANNOTATION_TYPE -> HierarchyKind.ANNOTATION_INTERFACES;
360        default -> throw new IllegalArgumentException(
361            typeElement.getKind().name() + " "
362                + typeElement.getQualifiedName());
363        };
364        return hierarchies.get(hk);
365    }
366
367    /**
368     * {@return the hierarchy for which the leaf nodes are plain classes}
369     */
370    public Hierarchy classes() {
371        return hierarchies.get(HierarchyKind.CLASSES);
372    }
373
374    /**
375     * {@return the hierarchy for which the leaf nodes are enum classes}
376     */
377    public Hierarchy enumClasses() {
378        return hierarchies.get(HierarchyKind.ENUM_CLASSES);
379    }
380
381    /**
382     * {@return the hierarchy for which the leaf nodes are record classes}
383     */
384    public Hierarchy recordClasses() {
385        return hierarchies.get(HierarchyKind.RECORD_CLASSES);
386    }
387
388    /**
389     * {@return the hierarchy for which the leaf nodes are plain interfaces}
390     */
391    public Hierarchy interfaces() {
392        return hierarchies.get(HierarchyKind.INTERFACES);
393    }
394
395    /**
396     * {@return the hierarchy for which the leaf nodes are annotation interfaces}
397     */
398    public Hierarchy annotationInterfaces() {
399        return hierarchies.get(HierarchyKind.ANNOTATION_INTERFACES);
400    }
401}