001/* -*- mode: Java; c-basic-offset: 2; indent-tabs-mode: nil; coding: utf-8-unix -*-
002 *
003 * Copyright © 2022 microBean™.
004 *
005 * Licensed under the Apache License, Version 2.0 (the "License");
006 * you may not use this file except in compliance with the License.
007 * You may obtain a copy of the License at
008 *
009 *     http://www.apache.org/licenses/LICENSE-2.0
010 *
011 * Unless required by applicable law or agreed to in writing, software
012 * distributed under the License is distributed on an "AS IS" BASIS,
013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
014 * implied.  See the License for the specific language governing
015 * permissions and limitations under the License.
016 */
017package org.microbean.path;
018
019import java.lang.StackWalker.StackFrame;
020
021import java.lang.constant.ClassDesc;
022import java.lang.constant.Constable;
023import java.lang.constant.ConstantDesc;
024import java.lang.constant.DynamicConstantDesc;
025import java.lang.constant.MethodHandleDesc;
026import java.lang.constant.MethodTypeDesc;
027
028import java.lang.reflect.GenericArrayType;
029import java.lang.reflect.ParameterizedType;
030import java.lang.reflect.Type;
031
032import java.util.ArrayList;
033import java.util.Arrays;
034import java.util.Collection;
035import java.util.Collections;
036import java.util.Iterator;
037import java.util.List;
038import java.util.Map;
039import java.util.Objects;
040import java.util.Optional;
041import java.util.Set;
042import java.util.Spliterator;
043import java.util.TreeMap;
044import java.util.TreeSet;
045
046import java.util.function.BiFunction;
047import java.util.function.BiPredicate;
048
049import java.util.stream.Stream;
050
051import org.microbean.constant.Constables;
052
053import org.microbean.development.annotation.Experimental;
054
055import org.microbean.qualifier.Qualified;
056import org.microbean.qualifier.Qualifier;
057import org.microbean.qualifier.Qualifiers;
058
059import static java.lang.constant.ConstantDescs.BSM_INVOKE;
060import static java.lang.constant.ConstantDescs.CD_List;
061import static java.lang.constant.ConstantDescs.CD_Object;
062import static java.lang.constant.ConstantDescs.CD_String;
063import static java.lang.constant.ConstantDescs.CD_boolean;
064import static java.lang.constant.ConstantDescs.DEFAULT_NAME;
065import static java.lang.constant.ConstantDescs.FALSE;
066import static java.lang.constant.ConstantDescs.NULL;
067import static java.lang.constant.ConstantDescs.TRUE;
068
069import static java.lang.constant.DirectMethodHandleDesc.Kind.STATIC;
070
071import static org.microbean.path.ConstantDescs.CD_Path;
072import static org.microbean.path.ConstantDescs.CD_PathElement;
073
074import static org.microbean.qualifier.ConstantDescs.CD_Qualifiers;
075
076/**
077 * A {@linkplain Qualified qualified} sequence of {@linkplain
078 * Path.Element named and qualified elements} that "points to" an
079 * object and that can be used for many different purposes.
080 *
081 * <p>A {@link Path} can be used like a {@link javax.naming.Name
082 * javax.naming.Name}, or like a {@link java.nio.file.Path
083 * java.nio.file.Path}, or like a {@link java.net.URI java.net.URI}.
084 * It differs from these other objects in that it combines some of
085 * their concepts together.</p>
086 *
087 * @param <T> the type of the {@link Path}; most notably
088 * <strong>not necessarily</strong> the type of the thing the {@link
089 * Path} "points to"; more like an additional qualifier
090 *
091 * @author <a href="https://about.me/lairdnelson"
092 * target="_parent">Laird Nelson</a>
093 *
094 * @see Path.Element
095 */
096public final class Path<T> implements Iterable<Path.Element<?>>, Qualified<String, Object, T> {
097
098
099  /*
100   * Static fields.
101   */
102
103
104  private static final StackWalker stackWalker = StackWalker.getInstance();
105
106  private static final Path<?> ROOT = new Path<>();
107
108  private static final char PREFIX_SEPARATOR_CHAR = '.';
109
110  private static final String PREFIX_SEPARATOR = "" + PREFIX_SEPARATOR_CHAR;
111
112
113  /*
114   * Instance fields.
115   */
116
117
118  private final Qualifiers<String, Object> qualifiers;
119
120  private final List<Element<?>> elements;
121
122  private final boolean transliterated;
123
124
125  /*
126   * Constructors.
127   */
128
129
130  // For use by ROOT only.
131  @SuppressWarnings("unchecked")
132  private Path() {
133    this(Qualifiers.of(), List.of(), (Element<T>)Element.root(), true);
134  }
135
136  /**
137   * Creates a new {@link Path}.
138   *
139   * @param lastElement the {@linkplain #lastElement last element} of
140   * this {@link Path}; must not be {@code null}
141   *
142   * @exception NullPointerException if any parameter is {@code null}
143   *
144   * @see #Path(Qualifiers, List, Element)
145   */
146  public Path(final Element<? extends T> lastElement) {
147    this(Qualifiers.of(), List.of(), lastElement, false);
148  }
149
150  /**
151   * Creates a new {@link Path}.
152   *
153   * @param qualifiers the {@link Path}'s {@linkplain #qualifiers()
154   * qualifiers}; must not be {@code null}
155   *
156   * @param lastElement the {@linkplain #lastElement last element} of
157   * this {@link Path}; must not be {@code null}
158   *
159   * @exception NullPointerException if any parameter is {@code null}
160   *
161   * @see #Path(Qualifiers, List, Element)
162   */
163  public Path(final Qualifiers<? extends String, ?> qualifiers,
164              final Element<? extends T> lastElement) {
165    this(qualifiers, List.of(), lastElement, false);
166  }
167
168  /**
169   * Creates a new {@link Path}.
170   *
171   * @param qualifiers the {@link Path}'s {@linkplain #qualifiers()
172   * qualifiers}; must not be {@code null}
173   *
174   * @param elements the {@linkplain Element elements} of this {@link
175   * Path}; must not be {@code null}; may be {@linkplain
176   * List#isEmpty() empty}
177   *
178   * @param lastElement the {@linkplain #lastElement last element} of
179   * this {@link Path}; must not be {@code null}
180   *
181   * @exception NullPointerException if any parameter is {@code null}
182   */
183  public Path(final Qualifiers<? extends String, ?> qualifiers,
184              final List<? extends Element<?>> elements,
185              final Element<? extends T> lastElement) {
186    this(qualifiers, elements, lastElement, false);
187  }
188
189  @SuppressWarnings("unchecked")
190  // Also used by #describeConstable()
191  private Path(final Qualifiers<? extends String, ?> qualifiers,
192               final List<? extends Element<?>> elements,
193               final Element<? extends T> lastElement,
194               final boolean transliterated) {
195    super();
196    final int size = elements.size();
197    if (size > 0) {
198      Set<Qualifier<String, Object>> pathQualifiers = null;
199      final List<Element<?>> newList = new ArrayList<>(size + 1);
200      StringBuilder prefix = null;
201      for (int i = 0; i < size; i++) {
202        final Element<?> e = elements.get(i);
203        newList.add(e);
204        final Qualifiers<String, Object> eQualifiers = e.qualifiers();
205        if (!eQualifiers.isEmpty()) {
206          if (prefix == null) {
207            prefix = new StringBuilder();
208          }
209          if (pathQualifiers == null) {
210            pathQualifiers = new TreeSet<>();
211            for (final Qualifier<? extends String, ?> q : qualifiers) {
212              pathQualifiers.add((Qualifier<String, Object>)q);
213            }
214          }
215          prefix.append(e.name()).append(PREFIX_SEPARATOR_CHAR);
216          final String finalPrefix = prefix.toString();
217          for (final Qualifier<String, Object> q : eQualifiers.withPrefix(q -> finalPrefix + PREFIX_SEPARATOR + q.name())) {
218            pathQualifiers.add(q);
219          }
220        }
221      }
222      newList.add(lastElement);
223      this.elements = Collections.unmodifiableList(newList);
224      final Qualifiers<? extends String, ?> lastElementQualifiers = lastElement.qualifiers();
225      if (lastElementQualifiers.isEmpty()) {
226        if (pathQualifiers == null) {
227          this.qualifiers = (Qualifiers<String, Object>)qualifiers;
228        } else {
229          this.qualifiers = Qualifiers.of(pathQualifiers);
230        }
231      } else {
232        if (prefix == null) {
233          prefix = new StringBuilder();
234        }
235        if (pathQualifiers == null) {
236          pathQualifiers = new TreeSet<>();
237          for (final Qualifier<? extends String, ?> q : qualifiers) {
238            pathQualifiers.add((Qualifier<String, Object>)q);
239          }
240        }
241        final String finalPrefix = prefix.append(lastElement.name()).toString();
242        for (final Qualifier<String, Object> q : lastElement.qualifiers().withPrefix(q -> finalPrefix + PREFIX_SEPARATOR + q.name())) {
243          pathQualifiers.add(q);
244        }
245        this.qualifiers = Qualifiers.of(pathQualifiers);
246      }
247    } else {
248      this.elements = List.of(lastElement);
249      final Qualifiers<? extends String, ?> lastElementQualifiers = lastElement.qualifiers();
250      if (lastElementQualifiers.isEmpty()) {
251        this.qualifiers = (Qualifiers<String, Object>)qualifiers;
252      } else {
253        Set<Qualifier<String, Object>> pathQualifiers = new TreeSet<>();
254        for (final Qualifier<? extends String, ?> q : qualifiers) {
255          pathQualifiers.add((Qualifier<String, Object>)q);
256        }
257        for (final Qualifier<String, Object> q : lastElement.qualifiers().withPrefix(q -> lastElement.name() + PREFIX_SEPARATOR + q.name())) {
258          pathQualifiers.add(q);
259        }
260        this.qualifiers = Qualifiers.of(pathQualifiers);
261      }
262    }
263    this.transliterated = transliterated;
264  }
265
266
267  /*
268   * Instance methods.
269   */
270
271
272  /**
273   * Returns {@code true} if and only if this {@link Path} is the
274   * result of a call to {@link #transliterate(BiFunction)}.
275   *
276   * @return {@code true} if this {@link Path} is {@linkplain
277   * #transliterate(BiFunction) transliterated}; {@code false}
278   * otherwise
279   */
280  public final boolean transliterated() {
281    return this.transliterated;
282  }
283
284  /**
285   * <em>Transliterates</em> this {@link Path} into another,
286   * semantically equivalent {@link Path} by producing a {@link Path}
287   * that is otherwise equal to this {@link Path} but that will return
288   * {@code true} from its {@link #transliterated()} method.
289   *
290   * <p>Transliteration can be needed when a {@link Path} is defined
291   * by a Java class and used by an application containing that Java
292   * class&mdash;because another Java class may have used the same
293   * element names to refer to different things.</p>
294   *
295   * <p>If this {@link Path} {@linkplain #transliterated() is
296   * already transliterated} then it is returned.</p>
297   *
298   * <p>This method calls {@link #transliterate(BiFunction)} with
299   * {@code null} as its sole argument.</p>
300   *
301   * @return the transliterated {@link Path}, which may be this {@link
302   * Path}; never {@code null}
303   *
304   * @nullability This method never returns {@code null}.
305   *
306   * @idempotency This method is idempotent and deterministic.
307   *
308   * @threadsafety This method is safe for concurrent use by multiple
309   * threads.
310   *
311   * @see #transliterate(BiFunction)
312   *
313   * @see #transliterated()
314   */
315  public final Path<T> transliterate() {
316    return transliterate(null);
317  }
318
319  /**
320   * <em>Transliterates</em> this {@link Path} into another,
321   * semantically equivalent {@link Path} by applying the supplied
322   * {@link BiFunction}, and returns the transliterated {@link Path}.
323   *
324   * <p>The supplied {@link BiFunction} accepts a Java package name as
325   * its first argument, which will be the first package name
326   * {@linkplain StackWalker encountered in the current thread's
327   * stack} that identifies a caller whose package name is not equal
328   * to {@link Class#getPackageName() Path.class.getPackageName()}.
329   * Its second argument is a {@link Element Element} from this
330   * {@link Path}.  It must return a {@link Element} representing the
331   * transliteration of its second argument (which may be the second
332   * argument itself).</p>
333   *
334   * <p>Transliteration can be needed when a {@link Path} is defined
335   * by a Java class and used by an application containing that Java
336   * class&mdash;because another Java class may have used the same
337   * element names to refer to different things.</p>
338   *
339   * <p>If this {@link Path} {@linkplain #transliterated() is
340   * already transliterated} then it is returned.</p>
341   *
342   * @param f a {@link BiFunction} responsible for the
343   * transliteration, element by element; may be {@code null}
344   *
345   * @return the transliterated {@link Path}, which may be this {@link
346   * Path}; never {@code null}
347   *
348   * @nullability This method never returns {@code null}.
349   *
350   * @idempotency This method is idempotent and deterministic, but the
351   * supplied {@link BiFunction} may not be.
352   *
353   * @threadsafety This method is safe for concurrent use by multiple
354   * threads, but the supplied {@link BiFunction} may not be.
355   *
356   * @see #transliterated()
357   */
358  @Experimental
359  @SuppressWarnings("unchecked")
360  public final Path<T> transliterate(final BiFunction<? super String, ? super Element<?>, ? extends Element<?>> f) {
361    if (this.transliterated()) {
362      return this;
363    } else {
364      final int size = this.size();
365      final int lastIndex = size - 1;
366      if (f == null) {
367        return
368          new Path<T>(this.qualifiers(),
369                      this.elements.subList(0, lastIndex),
370                      (Element<? extends T>)this.elements.get(lastIndex),
371                      true);
372      } else {
373        final String userPackageName = stackWalker.walk(Path::findUserPackageName);
374        final List<Element<?>> newElements = new ArrayList<>(lastIndex);
375        for (int i = 0; i < lastIndex; i++) {
376          newElements.add(f.apply(userPackageName, this.elements.get(i)));
377        }
378        return
379          new Path<T>(this.qualifiers(),
380                      newElements,
381                      (Element<? extends T>)f.apply(userPackageName, this.elements.get(lastIndex)),
382                      true);
383      }
384    }
385  }
386
387  /**
388   * Returns an {@link Optional} containing a {@link ConstantDesc}
389   * representing this {@link Path}, or an {@linkplain
390   * Optional#isEmpty() empty <code>Optional</code>} if this {@link
391   * Path} cannot be represented as a {@link ConstantDesc}.
392   *
393   * <p>A {@link Path} instance may be represented by a {@link
394   * ConstantDesc} only when the return value of an invocation of the
395   * {@link Element#describeConstable()} method on its {@linkplain
396   * #lastElement() last element} returns a non-{@linkplain
397   * Optional#isEmpty() empty} {@link Optional}.</p>
398   *
399   * @return an {@link Optional} containing a {@link ConstantDesc}
400   * representing this {@link Path}; never {@code null}; possibly
401   * {@linkplain Optional#isEmpty() empty}
402   *
403   * @nullability This method never returns {@code null}.
404   *
405   * @idempotency This method is idempotent and deterministic.
406   *
407   * @threadsafety This method is safe for concurrent use by multiple
408   * threads.
409   *
410   * @see Element#describeConstable()
411   */
412  @Override // Constable
413  public final Optional<? extends ConstantDesc> describeConstable() {
414    if (this.isRoot()) {
415      return
416        Optional.of(DynamicConstantDesc.ofNamed(BSM_INVOKE,
417                                                DEFAULT_NAME,
418                                                CD_Path,
419                                                MethodHandleDesc.ofMethod(STATIC,
420                                                                          CD_Path,
421                                                                          "root",
422                                                                          MethodTypeDesc.of(CD_Path))));
423    } else {
424      final ConstantDesc qualifiers = this.qualifiers().describeConstable().orElse(null);
425      if (qualifiers != null) {
426        final ConstantDesc elements = Constables.describeConstable(this.elements.subList(0, this.size() - 1)).orElse(null);
427        if (elements != null) {
428          final ConstantDesc lastElement = this.elements.get(this.size() - 1).describeConstable().orElse(null);
429          if (lastElement != null) {
430            return
431              Optional.of(DynamicConstantDesc.ofNamed(BSM_INVOKE,
432                                                      DEFAULT_NAME,
433                                                      CD_Path,
434                                                      MethodHandleDesc.ofConstructor(CD_Path,
435                                                                                     CD_Qualifiers,
436                                                                                     CD_List,
437                                                                                     CD_PathElement,
438                                                                                     CD_boolean),
439                                                      qualifiers,
440                                                      elements,
441                                                      lastElement,
442                                                      this.transliterated ? TRUE : FALSE));
443          }
444        }
445      }
446    }
447    return Optional.empty();
448  }
449
450  /**
451   * Returns the {@link Qualifiers} that qualifies this {@link Path}.
452   *
453   * @return the {@link Qualifiers} that qualifies this {@link Path}
454   *
455   * @nullability This method never returns {@code null}.
456   *
457   * @idempotency This method is idempotent and deterministic.
458   *
459   * @threadsafety This method is safe for concurrent use by multiple
460   * threads.
461   */
462  @Override // Qualified<String, Object, T>
463  public final Qualifiers<String, Object> qualifiers() {
464    return this.qualifiers;
465  }
466
467  /**
468   * Returns the {@link Path.Element} found at the supplied zero-based
469   * index.
470   *
471   * @param index the index of the {@link Path.Element} to return;
472   * must be {@code 0} or greater and less than this {@link Path}'s
473   * {@linkplain #size() size}
474   *
475   * @return the {@link Path.Element} found at the supplied zero-based
476   * index
477   *
478   * @exception IndexOutOfBoundsException if {@code index} does not
479   * meet the requirements described above
480   *
481   * @nullability This method never returns {@code null}.
482   *
483   * @threadsafety This method is safe for concurrent use by multiple
484   * threads.
485   *
486   * @idempotency This method is idempotent and deterministic.
487   */
488  public final Element<?> get(final int index) {
489    return this.elements.get(index);
490  }
491
492  /**
493   * Returns an {@link Iterator} that iterates over the {@linkplain
494   * Element elements} of this {@link Path}, including the {@linkplain
495   * #lastElement() last element}.
496   *
497   * @return an {@link Iterator} that iterates over the {@linkplain
498   * Element elements} of this {@link Path}, including the {@linkplain
499   * #lastElement() last element}
500   *
501   * @nullability This method never returns {@code null}.
502   *
503   * @idempotency This method is idempotent and deterministic.
504   *
505   * @threadsafety This method is safe for concurrent use by multiple
506   * threads.
507   */
508  @Override // Iterable<Element<?>>
509  public final Iterator<Element<?>> iterator() {
510    return this.elements.iterator();
511  }
512
513  /**
514   * Returns a {@link Spliterator} for the {@linkplain Element
515   * elements} of this {@link Path}, including the {@linkplain
516   * #lastElement() last element}.
517   *
518   * @return a {@link Spliterator} for the {@linkplain Element
519   * elements} of this {@link Path}, including the {@linkplain
520   * #lastElement() last element}
521   *
522   * @nullability This method never returns {@code null}.
523   *
524   * @idempotency This method is idempotent and deterministic.
525   *
526   * @threadsafety This method is safe for concurrent use by multiple
527   * threads.
528   */
529  @Override // Iterable<Element<?>>
530  public final Spliterator<Element<?>> spliterator() {
531    return this.elements.spliterator();
532  }
533
534  /**
535   * Returns a {@link Stream} of this {@link Path}'s {@link Element}s.
536   *
537   * @return a possibly parallel {@link Stream} of this {@link Path}'s
538   * {@link Element}s
539   *
540   * @nullability This method never returns {@code null}.
541   *
542   * @idempotency This method is idempotent and deterministic.
543   *
544   * @threadsafety This method is safe for concurrent use by multiple
545   * threads.
546   */
547  public final Stream<Element<?>> stream() {
548    return this.elements.stream();
549  }
550
551  /**
552   * Returns a possibly parallel {@link Stream} of this {@link Path}'s
553   * {@link Element}s.
554   *
555   * @return a possibly parallel {@link Stream} of this {@link Path}'s
556   * {@link Element}s
557   *
558   * @nullability This method never returns {@code null}.
559   *
560   * @idempotency This method is idempotent and deterministic.
561   *
562   * @threadsafety This method is safe for concurrent use by multiple
563   * threads.
564   */
565  public final Stream<Element<?>> parallelStream() {
566    return this.elements.parallelStream();
567  }
568
569  /**
570   * Returns the number of {@link Element}s in this {@link Path},
571   * which is always greater than or equal to {@code 1}.
572   *
573   * @return the number of {@link Element}s in this {@link Path}
574   *
575   * @idempotency This method is idempotent and deterministic.
576   *
577   * @threadsafety This method is safe for concurrent use by multiple
578   * threads.
579   */
580  public final int size() {
581    return this.elements.size();
582  }
583
584  /**
585   * Returns the zero-based index identifying the position of the
586   * first occurrence of a {@link Path} {@linkplain #equals(Object)
587   * equal to} the supplied {@link Path} within this {@link Path}, or
588   * a negative value if the supplied {@link Path} does not occur
589   * within this {@link Path}.
590   *
591   * @param other the other {@link Path}; must not be {@code null}
592   *
593   * @return the zero-based index identifying the position of the
594   * first occurrence of a {@link Path} {@linkplain #equals(Object)
595   * equal to} supplied {@link Path} within this {@link Path}, or a
596   * negative value if the supplied {@link Path} does not occur within
597   * this {@link Path}
598   *
599   * @exception NullPointerException if {@code other} is {@code null}
600   *
601   * @idempotency This method is idempotent and deterministic.
602   *
603   * @threadsafety This method is safe for concurrent use by multiple
604   * threads.
605   */
606  public final int indexOf(final Path<?> other) {
607    return other == this ? 0 : Collections.indexOfSubList(this.elements, other.elements);
608  }
609
610  /**
611   * Returns the zero-based index identifying the position of the
612   * first occurrence of a {@link Path} {@linkplain #equals(Object)
613   * equal to} supplied {@link Path} within this {@link Path}, or a
614   * negative value if the supplied {@link Path} does not occur within
615   * this {@link Path}.
616   *
617   * <p>The supplied {@link BiPredicate} is used to test each {@link
618   * Element} of the supplied {@link Path} against {@link Element}s
619   * from this {@link Path}.  The first argument is a {@link Element}
620   * drawn from this {@link Path}.  The second argument is an {@link
621   * Element} drawn from the supplied {@link Path}.  The {@link
622   * BiPredicate} returns {@code true} if its arguments are deemed to
623   * match.  The supplied {@link BiPredicate}'s {@link
624   * BiPredicate#test(Object, Object)} method must be idempotent and
625   * deterministic.</p>
626   *
627   * @param path the other {@link Path}; must not be {@code null}
628   *
629   * @param p the {@link BiPredicate} used to {@linkplain
630   * BiPredicate#test(Object, Object) test} {@link Element}s; must not
631   * be {@code null}
632   *
633   * @return the zero-based index identifying the position of the
634   * first occurrence of a {@link Path} {@linkplain #equals(Object)
635   * equal to} supplied {@link Path} within this {@link Path}, or a
636   * negative value if the supplied {@link Path} does not occur within
637   * this {@link Path}
638   *
639   * @exception NullPointerException if either {@code path} or {@code
640   * p} is {@code null}
641   *
642   * @idempotency This method is idempotent and deterministic.
643   *
644   * @threadsafety This method is safe for concurrent use by multiple
645   * threads.
646   */
647  public final int indexOf(final Path<?> path, final BiPredicate<? super Element<?>, ? super Element<?>> p) {
648    final int pathSize = path.size();
649    final int sizeDiff = this.size() - pathSize;
650    OUTER_LOOP:
651    for (int i = 0; i <= sizeDiff; i++) {
652      for (int j = 0, k = i; j < pathSize; j++, k++) {
653        if (!p.test(this.elements.get(k), path.elements.get(j))) {
654          continue OUTER_LOOP;
655        }
656      }
657      return i;
658    }
659    return -1;
660  }
661
662  /**
663   * Returns {@code true} if this {@link Path} starts with a {@link
664   * Path} that is {@linkplain #equals(Object) equal to} the supplied
665   * {@link Path}.
666   *
667   * <p>This method returns {@code true} if and only if:</p>
668   *
669   * <ul>
670   *
671   * <li>{@code other} is identical to this {@link Path}, or</li>
672   *
673   * <li>An invocation of the {@link #indexOf(Path)} method with
674   * {@code other} as its sole argument returns {@code 0}</li>
675   *
676   * </ul>
677   *
678   * @param other the other {@link Path}; must not be {@code null}
679   *
680   * @return {@code true} if this {@link Path} starts with a {@link
681   * Path} that is {@linkplain #equals(Object) equal to} the supplied
682   * {@link Path}; {@code false} otherwise
683   *
684   * @exception NullPointerException if {@code other} is {@code null}
685   *
686   * @idempotency This method is idempotent and deterministic.
687   *
688   * @threadsafety This method is safe for concurrent use by multiple
689   * threads.
690   *
691   * @see #indexOf(Path)
692   */
693  public final boolean startsWith(final Path<?> other) {
694    return other == this || this.indexOf(other) == 0;
695  }
696
697  /**
698   * Returns the last {@link Element} in this {@link Path}.
699   *
700   * @return the last {@link Element} in this {@link Path}
701   *
702   * @nullability This method never returns {@code null}.
703   *
704   * @idempotency This method is idempotent and deterministic.
705   *
706   * @threadsafety This method is safe for concurrent use by multiple
707   * threads.
708   */
709  @SuppressWarnings("unchecked")
710  public final Element<T> lastElement() {
711    return (Element<T>)this.elements.get(this.size() - 1);
712  }
713
714  /**
715   * Returns the zero-based index identifying the position of the
716   * last occurrence of a {@link Path} {@linkplain #equals(Object)
717   * equal to} the supplied {@link Path} within this {@link Path}, or
718   * a negative value if the supplied {@link Path} does not occur
719   * within this {@link Path}.
720   *
721   * @param other the other {@link Path}; must not be {@code null}
722   *
723   * @return the zero-based index identifying the position of the
724   * last occurrence of a {@link Path} {@linkplain #equals(Object)
725   * equal to} supplied {@link Path} within this {@link Path}, or a
726   * negative value if the supplied {@link Path} does not occur within
727   * this {@link Path}
728   *
729   * @exception NullPointerException if {@code other} is {@code null}
730   *
731   * @idempotency This method is idempotent and deterministic.
732   *
733   * @threadsafety This method is safe for concurrent use by multiple
734   * threads.
735   */
736  public final int lastIndexOf(final Path<?> other) {
737    return other == this ? 0 : Collections.lastIndexOfSubList(this.elements, other.elements);
738  }
739
740  /**
741   * Returns the zero-based index identifying the position of the
742   * last occurrence of a {@link Path} {@linkplain #equals(Object)
743   * equal to} supplied {@link Path} within this {@link Path}, or a
744   * negative value if the supplied {@link Path} does not occur within
745   * this {@link Path}.
746   *
747   * <p>The supplied {@link BiPredicate} is used to test each {@link
748   * Element} of the supplied {@link Path} against {@link Element}s
749   * from this {@link Path}.  The first argument is a {@link Element}
750   * drawn from this {@link Path}.  The second argument is an {@link
751   * Element} drawn from the supplied {@link Path}.  The {@link
752   * BiPredicate} returns {@code true} if its arguments are deemed to
753   * match.  The supplied {@link BiPredicate}'s {@link
754   * BiPredicate#test(Object, Object)} method must be idempotent and
755   * deterministic.</p>
756   *
757   * @param path the other {@link Path}; must not be {@code null}
758   *
759   * @param p the {@link BiPredicate} used to {@linkplain
760   * BiPredicate#test(Object, Object) test} {@link Element}s; must not
761   * be {@code null}
762   *
763   * @return the zero-based index identifying the position of the
764   * last occurrence of a {@link Path} {@linkplain #equals(Object)
765   * equal to} supplied {@link Path} within this {@link Path}, or a
766   * negative value if the supplied {@link Path} does not occur within
767   * this {@link Path}
768   *
769   * @exception NullPointerException if either {@code path} or {@code
770   * p} is {@code null}
771   *
772   * @idempotency This method is idempotent and deterministic.
773   *
774   * @threadsafety This method is safe for concurrent use by multiple
775   * threads.
776   */
777  public final int lastIndexOf(final Path<?> path, final BiPredicate<? super Element<?>, ? super Element<?>> p) {
778    final int pathSize = path.size();
779    final int sizeDiff = this.size() - pathSize;
780    OUTER_LOOP:
781    for (int i = sizeDiff; i >= 0; i--) {
782      for (int j = 0, k = i; j < pathSize; j++, k++) {
783        if (!p.test(this.elements.get(k), path.elements.get(j))) {
784          continue OUTER_LOOP;
785        }
786      }
787      return i;
788    }
789    return -1;
790  }
791
792/**
793   * Returns {@code true} if this {@link Path} starts with a {@link
794   * Path} that is {@linkplain #equals(Object) equal to} the supplied
795   * {@link Path}.
796   *
797   * <p>The supplied {@link BiPredicate} is used to test each {@link
798   * Element} of the supplied {@link Path} against {@link Element}s
799   * from this {@link Path}.  The first argument is a {@link Element}
800   * drawn from this {@link Path}.  The second argument is a {@link
801   * Element} drawn from the supplied {@link Path}.  The {@link
802   * BiPredicate} returns {@code true} if its arguments are deemed to
803   * match.  The supplied {@link BiPredicate}'s {@link
804   * BiPredicate#test(Object, Object)} method must be idempotent and
805   * deterministic.</p>
806   *
807   * <p>This method returns {@code true} if and only if:</p>
808   *
809   * <ul>
810   *
811   * <li>{@code other} is identical to this {@link Path}, or</li>
812   *
813   * <li>An invocation of the {@link #indexOf(Path, BiPredicate)}
814   * method with {@code other} and {@code p} as its arguments returns
815   * {@code 0}</li>
816   *
817   * </ul>
818   *
819   * @param other the other {@link Path}; must not be {@code null}
820   *
821   * @param p the {@link BiPredicate} used to {@linkplain
822   * BiPredicate#test(Object, Object) test} {@link Element}s; must not
823   * be {@code null}
824   *
825   * @return {@code true} if this {@link Path} starts with a {@link
826   * Path} that is {@linkplain #equals(Object) equal to} the supplied
827   * {@link Path}; {@code false} otherwise
828   *
829   * @exception NullPointerException if {@code other} is {@code null}
830   *
831   * @idempotency This method is idempotent and deterministic.
832   *
833   * @threadsafety This method is safe for concurrent use by multiple
834   * threads.
835   *
836   * @see #indexOf(Path, BiPredicate)
837   */
838  public final boolean startsWith(final Path<?> other, final BiPredicate<? super Element<?>, ? super Element<?>> p) {
839    return other == this || this.indexOf(other, p) == 0;
840  }
841
842  /**
843   * Returns {@code true} if this {@link Path} ends with a {@link
844   * Path} that is {@linkplain #equals(Object) equal to} the supplied
845   * {@link Path}.
846   *
847   * <p>This method returns {@code true} if and only if:</p>
848   *
849   * <ul>
850   *
851   * <li>{@code other} is identical to this {@link Path}, or</li>
852   *
853   * <li>An invocation of the {@link #lastIndexOf(Path)} method with
854   * {@code other} as its sole argument returns {@code 0} or a
855   * positive {@code int}, and that number plus the supplied {@link
856   * Path}'s {@linkplain #size() size} is equal to this {@link Path}'s
857   * {@linkplain #size() size}</li>
858   *
859   * </ul>
860   *
861   * @param other the other {@link Path}; must not be {@code null}
862   *
863   * @return {@code true} if this {@link Path} ends with a {@link
864   * Path} that is {@linkplain #equals(Object) equal to} the supplied
865   * {@link Path}; {@code false} otherwise
866   *
867   * @exception NullPointerException if {@code other} is {@code null}
868   *
869   * @idempotency This method is idempotent and deterministic.
870   *
871   * @threadsafety This method is safe for concurrent use by multiple
872   * threads.
873   *
874   * @see #lastIndexOf(Path)
875   */
876  public final boolean endsWith(final Path<?> other) {
877    if (other == this) {
878      return true;
879    } else {
880      final int lastIndex = this.lastIndexOf(other);
881      return lastIndex >= 0 && lastIndex + other.size() == this.size();
882    }
883  }
884
885  /**
886   * Returns {@code true} if this {@link Path} ends with a {@link
887   * Path} that is {@linkplain #equals(Object) equal to} the supplied
888   * {@link Path}.
889   *
890   * <p>The supplied {@link BiPredicate} is used to test each {@link
891   * Element} of the supplied {@link Path} against {@link Element}s
892   * from this {@link Path}.  The first argument is a {@link Element}
893   * drawn from this {@link Path}.  The second argument is a {@link
894   * Element} drawn from the supplied {@link Path}.  The {@link
895   * BiPredicate} returns {@code true} if its arguments are deemed to
896   * match.  The supplied {@link BiPredicate}'s {@link
897   * BiPredicate#test(Object, Object)} method must be idempotent and
898   * deterministic.</p>
899   *
900   * <p>This method returns {@code true} if and only if:</p>
901   *
902   * <ul>
903   *
904   * <li>{@code other} is identical to this {@link Path}, or</li>
905   *
906   * <li>An invocation of the {@link #indexOf(Path, BiPredicate)}
907   * method with {@code other} and {@code p} as its arguments returns
908   * {@code 0} or a positive {@code int}, and if that number plus the
909   * supplied {@link Path}'s {@linkplain #size() size} is equal to
910   * this {@link Path}'s {@linkplain #size() size}</li>
911   *
912   * </ul>
913   *
914   * @param other the other {@link Path}; must not be {@code null}
915   *
916   * @param p the {@link BiPredicate} used to {@linkplain
917   * BiPredicate#test(Object, Object) test} {@link Element}s; must not
918   * be {@code null}
919   *
920   * @return {@code true} if this {@link Path} ends with a {@link
921   * Path} that is {@linkplain #equals(Object) equal to} the supplied
922   * {@link Path}; {@code false} otherwise
923   *
924   * @exception NullPointerException if {@code other} is {@code null}
925   *
926   * @idempotency This method is idempotent and deterministic.
927   *
928   * @threadsafety This method is safe for concurrent use by multiple
929   * threads.
930   *
931   * @see #lastIndexOf(Path, BiPredicate)
932   */
933  public final boolean endsWith(final Path<?> other, final BiPredicate<? super Element<?>, ? super Element<?>> p) {
934    if (other == this) {
935      return true;
936    } else {
937      final int lastIndex = this.lastIndexOf(other, p);
938      return lastIndex >= 0 && lastIndex + other.size() == this.size();
939    }
940  }
941
942  /**
943   * Calls the {@link Element#qualified()} method on the {@linkplain
944   * lastElement() last element in this <code>Path</code>} and returns
945   * the result.
946   *
947   * @return the result of invoking the {@link Element#qualified()}
948   * method on the {@linkplain lastElement() last element in this
949   * <code>Path</code>}
950   *
951   * @nullability This method may return {@code null}.
952   *
953   * @idempotency This method is idempotent and deterministic.
954   *
955   * @threadsafety This method is safe for concurrent use by multiple
956   * threads.
957   */
958  @Override // Qualified<String, Object, T>
959  public final T qualified() {
960    return this.lastElement().qualified();
961  }
962
963  /**
964   * Returns {@code true} if this {@link Path} is a <em>root
965   * path</em>, which is true when it has only one {@linkplain Element
966   * element} and that {@linkplain Element element} {@linkplain
967   * Element#isRoot() is root}.
968   *
969   * @return {@code true} if this {@link Path} is a <em>root
970   * path</em>; {@code false} otherwise
971   *
972   * @idempotency This method is idempotent and deterministic.
973   *
974   * @threadsafety This method is safe for concurrent use by multiple
975   * threads.
976   */
977  public final boolean isRoot() {
978    return this.size() == 1 && this.lastElement().isRoot();
979  }
980
981  /**
982   * Returns {@code true} if and only if this {@link Path} is
983   * <em>absolute</em>, which means that its first {@link Element} is
984   * a {@linkplain Element#isRoot() root} {@link Element}.
985   *
986   * @return {@code true} if and only if this {@link Path} is absolute
987   */
988  public final boolean absolute() {
989    return this.elements.get(0).isRoot();
990  }
991
992  /**
993   * Returns a hashcode for this {@link Path}.
994   *
995   * @return a hashcode for this {@link Path}
996   *
997   * @idempotency This method is idempotent and deterministic.
998   *
999   * @threadsafety This method is safe for concurrent use by multiple
1000   * threads.
1001   */
1002  @Override // Object
1003  public final int hashCode() {
1004    int hashCode = 17;
1005    Object value = this.qualifiers();
1006    int c = value == null ? 0 : value.hashCode();
1007    hashCode = 37 * hashCode + c;
1008    value = this.elements;
1009    c = value == null ? 0 : value.hashCode();
1010    hashCode = 37 * hashCode + c;
1011    c = this.transliterated ? 1 : 0;
1012    hashCode = 37 * hashCode + c;
1013    return hashCode;
1014  }
1015
1016  /**
1017   * Returns {@code true} if and only if the supplied {@link Object}
1018   * is equal to this {@link Path}.
1019   *
1020   * @param other the {@link Object} to test; may be {@code null} in
1021   * which case {@code false} will be returned
1022   *
1023   * @return {@code true} if and only if the supplied {@link Object}
1024   * is equal to this {@link Path}
1025   *
1026   * @idempotency This method is idempotent and deterministic.
1027   *
1028   * @threadsafety This method is safe for concurrent use by multiple
1029   * threads.
1030   */
1031  @Override // Object
1032  public final boolean equals(final Object other) {
1033    if (other == this) {
1034      return true;
1035    } else if (other != null && other.getClass() == this.getClass()) {
1036      final Path<?> her = (Path<?>)other;
1037      return
1038        Objects.equals(this.qualifiers(), her.qualifiers()) &&
1039        Objects.equals(this.elements, her.elements) &&
1040        this.transliterated == her.transliterated;
1041    } else {
1042      return false;
1043    }
1044  }
1045
1046  /**
1047   * Returns a <strong>new</strong> {@link Path} consisting of this
1048   * {@link Path}'s {@linkplain #qualifiers() qualifiers} and
1049   * {@linkplain Element elments} plus the supplied {@linkplain
1050   * Element element}.
1051   *
1052   * @param <U> the type of the new {@link Path}
1053   *
1054   * @param element the new {@link Path}'s {@linkplain #lastElement()
1055   * last element}; must not be {@code null}
1056   *
1057   * @return a <strong>new</strong> {@link Path} consisting of this
1058   * {@link Path}'s {@linkplain #qualifiers() qualifiers} and
1059   * {@linkplain Element elments} plus the supplied {@linkplain
1060   * Element element}
1061   *
1062   * @exception NullPointerException if {@code element} is {@code
1063   * null}
1064   *
1065   * @nullability This method never returns {@code null}.
1066   *
1067   * @idempotency This method is idempotent and deterministic.
1068   *
1069   * @threadsafety This method is safe for concurrent use by multiple
1070   * threads.
1071   */
1072  public final <U> Path<U> plus(final Element<? extends U> element) {
1073    return new Path<>(this.qualifiers(), this.elements, element);
1074  }
1075
1076  /**
1077   * Returns a <strong>new</strong> {@link Path} consisting of this
1078   * {@link Path}'s {@linkplain #qualifiers() qualifiers}, this {@link
1079   * Path}'s elements, the supplied {@code elements}, and the supplied
1080   * {@code lastElement}.
1081   *
1082   * @param <U> the type of the new {@link Path}
1083   *
1084   * @param elements additional {@linkplain Element elements}; must
1085   * not be {@code null}
1086   *
1087   * @param lastElement the new {@link Path}'s {@linkplain
1088   * #lastElement() last element}; must not be {@code null}
1089   *
1090   * @return a <strong>new</strong> {@link Path} consisting of this
1091   * {@link Path}'s {@linkplain #qualifiers() qualifiers}, this {@link
1092   * Path}'s elements, the supplied {@code elements}, and the supplied
1093   * {@code lastElement}
1094   *
1095   * @exception NullPointerException if {@code element} is {@code
1096   * null}
1097   *
1098   * @nullability This method never returns {@code null}.
1099   *
1100   * @idempotency This method is idempotent and deterministic.
1101   *
1102   * @threadsafety This method is safe for concurrent use by multiple
1103   * threads.
1104   */
1105  public final <U> Path<U> plus(final Collection<? extends Element<?>> elements,
1106                                final Element<? extends U> lastElement) {
1107    final List<Element<?>> newElements = new ArrayList<>(this.size() + elements.size());
1108    newElements.addAll(elements);
1109    return new Path<>(this.qualifiers(), newElements, lastElement);
1110  }
1111
1112  /**
1113   * Returns a <strong>new</strong> {@link Path} consisting of this
1114   * {@link Path}'s {@linkplain #qualifiers() qualifiers} combined
1115   * with a prefixed version of the supplied {@link Path}'s
1116   * {@linkplain #qualifiers() qualifiers}, this {@link Path}'s
1117   * elements, the supplied {@link Path}'s elements, and the supplied
1118   * {@link Path}'s {@linkplain #lastElement() last element}.
1119   *
1120   * <p>The new {@link Path}'s {@linkplain #qualifiers() qualifiers}
1121   * are those of this {@link Path} plus those of the supplied {@link
1122   * Path}, where each qualifier in the supplied {@link Path}'s
1123   * {@linkplain #qualifiers() qualifiers} has been prefixed with a
1124   * {@link String} formed from the {@linkplain Element#name() names}
1125   * of all the {@linkplain Element elements} in this {@link
1126   * Path}.</p>
1127   *
1128   * @param <U> the type of the new {@link Path}
1129   *
1130   * @param path the {@link Path} to logically append; must not be
1131   * {@code null}
1132   *
1133   * @return a <strong>new</strong> {@link Path} consisting of this
1134   * {@link Path}'s {@linkplain #qualifiers() qualifiers} combined
1135   * with a prefixed version of the supplied {@link Path}'s
1136   * {@linkplain #qualifiers() qualifiers}, this {@link Path}'s
1137   * elements, the supplied {@link Path}'s elements, and the supplied
1138   * {@link Path}'s {@linkplain #lastElement() last element}
1139   *
1140   * @exception NullPointerException if {@code path} is {@code null}
1141   *
1142   * @nullability This method never returns {@code null}.
1143   *
1144   * @idempotency This method is idempotent and deterministic.
1145   *
1146   * @threadsafety This method is safe for concurrent use by multiple
1147   * threads.
1148   */
1149  @SuppressWarnings("unchecked")
1150  public final <U> Path<U> plus(final Path<? extends U> path) {
1151    final int pathSize = path.size();
1152    final List<Element<?>> newElements = new ArrayList<>(this.size() + pathSize);
1153    newElements.addAll(this.elements);
1154    final int lastIndex = pathSize - 1;
1155    for (int i = 0; i < lastIndex; i++) {
1156      newElements.add(path.elements.get(i));
1157    }
1158    final String prefix = this.prefix();
1159    return
1160      new Path<>(path.qualifiers().withPrefix(k -> prefix + k),
1161                 newElements,
1162                 (Element<? extends U>)path.elements.get(lastIndex));
1163  }
1164
1165  private final String prefix() {
1166    final StringBuilder prefix = new StringBuilder();
1167    for (final Element<?> e : this) {
1168      prefix.append(e.name()).append(PREFIX_SEPARATOR_CHAR);
1169    }
1170    return prefix.toString();
1171  }
1172
1173  /**
1174   * Returns a non-{@code null} {@link String} representation of this
1175   * {@link Path}.
1176   *
1177   * <p>The format of the returned {@link String} is deliberately
1178   * undefined and may change between revisions of this class without
1179   * notice.</p>
1180   *
1181   * @return a non-{@code null} {@link String} representation of this
1182   * {@link Path}
1183   *
1184   * @nullability This method never returns {@code null}.
1185   *
1186   * @idempotency This method is idempotent and deterministic.
1187   *
1188   * @threadsafety This method is safe for concurrent use by multiple
1189   * threads.
1190   */
1191  @Override // Object
1192  public final String toString() {
1193    final StringBuilder sb = new StringBuilder();
1194    Iterator<Element<?>> i = this.iterator();
1195    while (i.hasNext()) {
1196      sb.append(i.next());
1197      if (i.hasNext()) {
1198        sb.append('/');
1199      }
1200    }
1201    sb.append(this.qualifiers());
1202    return sb.toString();
1203  }
1204
1205
1206  /*
1207   * Static methods.
1208   */
1209
1210
1211  /**
1212   * Returns a {@link Path} that {@linkplain #isRoot() is a <em>root
1213   * path</em>}.
1214   *
1215   * @return a {@link Path} that {@linkplain #isRoot() is a <em>root
1216   * path</em>}
1217   *
1218   * @nullability This method never returns {@code null}.
1219   *
1220   * @idempotency This method is idempotent and deterministic.
1221   *
1222   * @threadsafety This method is safe for concurrent use by multiple
1223   * threads.
1224   *
1225   * @see #isRoot()
1226   */
1227  public static final Path<?> root() {
1228    return ROOT;
1229  }
1230
1231  /**
1232   * Returns a (<strong>usually new</strong>) {@link Path} formed from
1233   * a {@link Element} formed from the supplied {@code qualified} and
1234   * an {@linkplain String#isEmpty() empty} {@linkplain Element#name()
1235   * name}.
1236   *
1237   * @param <T> the type of the {@link Path}
1238   *
1239   * @param qualified the {@linkplain Element#qualified() qualified
1240   * item} of what will be the last {@link Element}
1241   *
1242   * @return a {@link Path}
1243   *
1244   * @exception NullPointerException if {@code qualified} is {@code
1245   * null}
1246   *
1247   * @nullability This method never returns {@code null}.
1248   *
1249   * @idempotency This method is idempotent and deterministic.
1250   *
1251   * @threadsafety This method is safe for concurrent use by multiple
1252   * threads.
1253   *
1254   * @see #of(Object, List)
1255   */
1256  public static final <T> Path<T> of(final T qualified) {
1257    return Path.of(qualified, List.of());
1258  }
1259
1260  /**
1261   * Returns a (<strong>usually new</strong>) {@link Path} formed from
1262   * a {@link Element} formed from the supplied {@code qualified} and
1263   * the supplied name.
1264   *
1265   * @param <T> the type of the {@link Path}
1266   *
1267   * @param qualified the {@linkplain Element#qualified() qualified
1268   * item} of what will be the last {@link Element}
1269   *
1270   * @param name the {@linkplain Element#name() name} of what will be
1271   * the last {@link Element}
1272   *
1273   * @return a {@link Path}
1274   *
1275   * @exception NullPointerException if {@code name} is {@code null}
1276   *
1277   * @exception IllegalArgumentException if {@code qualified} is
1278   * {@code null} and name is {@code null} or an empty
1279   * <code>String</code>}
1280   *
1281   * @nullability This method never returns {@code null}.
1282   *
1283   * @idempotency This method is idempotent and deterministic.
1284   *
1285   * @threadsafety This method is safe for concurrent use by multiple
1286   * threads.
1287   *
1288   * @see #of(Object, List)
1289   */
1290  public static final <T> Path<T> of(final T qualified, final String name) {
1291    return Path.of(qualified, List.of(name));
1292  }
1293
1294  /**
1295   * Returns a (<strong>usually new</strong>) {@link Path} formed from
1296   * {@link Element}s formed from the supplied {@code qualified} and
1297   * the supplied array of {@linkplain Element#name() names}.
1298   *
1299   * @param <T> the type of the {@link Path}
1300   *
1301   * @param qualified the {@linkplain Element#qualified() qualified
1302   * item} of what will be the last {@link Element}
1303   *
1304   * @param names an array of {@linkplain Element#name() names} from
1305   * which {@link Element}s will be synthesized; must not be {@code
1306   * null}
1307   *
1308   * @return a {@link Path}
1309   *
1310   * @exception NullPointerException if {@code names} is {@code null}
1311   *
1312   * @exception IllegalArgumentException if {@code qualified} is
1313   * {@code null} and the last element of {@code names} {@linkplain
1314   * String#isEmpty() is an empty <code>String</code>}
1315   *
1316   * @nullability This method never returns {@code null}.
1317   *
1318   * @idempotency This method is idempotent and deterministic.
1319   *
1320   * @threadsafety This method is safe for concurrent use by multiple
1321   * threads.
1322   *
1323   * @see #of(Object, List)
1324   */
1325  public static final <T> Path<T> of(final T qualified, final String... names) {
1326    return Path.of(qualified, Arrays.asList(names));
1327  }
1328
1329  /**
1330   * Returns a (<strong>usually new</strong>) {@link Path} formed from
1331   * the supplied {@code lastElement}.
1332   *
1333   * @param <T> the type of the {@link Path}
1334   *
1335   * @param lastElement the last {@link Element}; must not be {@code
1336   * null}
1337   *
1338   * @return a {@link Path}
1339   *
1340   * @exception NullPointerException if {@code lastElement} is {@code
1341   * null}
1342   *
1343   * @nullability This method never returns {@code null}.
1344   *
1345   * @idempotency This method is idempotent and deterministic.
1346   *
1347   * @threadsafety This method is safe for concurrent use by multiple
1348   * threads.
1349   */
1350  public static final <T> Path<T> of(final Element<? extends T> lastElement) {
1351    return new Path<>(lastElement);
1352  }
1353
1354  /**
1355   * Returns a (<strong>usually new</strong>) {@link Path} formed from
1356   * {@link Element}s formed from the supplied {@code qualified} and
1357   * the supplied {@link List} of {@linkplain Element#name() names}.
1358   *
1359   * @param <T> the type of the {@link Path}
1360   *
1361   * @param qualified the {@linkplain Element#qualified() qualified
1362   * item} of what will be the last {@link Element}
1363   *
1364   * @param names a {@link List} of {@linkplain Element#name() names}
1365   * from which {@link Element}s will be synthesized; must not be
1366   * {@code null}
1367   *
1368   * @return a {@link Path}
1369   *
1370   * @exception NullPointerException if {@code names} is {@code null}
1371   *
1372   * @exception IllegalArgumentException if {@code qualified} is
1373   * {@code null} and the last element of {@code names} {@linkplain
1374   * String#isEmpty() is an empty <code>String</code>}
1375   *
1376   * @nullability This method never returns {@code null}.
1377   *
1378   * @idempotency This method is idempotent and deterministic.
1379   *
1380   * @threadsafety This method is safe for concurrent use by multiple
1381   * threads.
1382   *
1383   * @see Element#Element(Qualifiers, Object, String)
1384   */
1385  public static final <T> Path<T> of(final T qualified, final List<? extends String> names) {
1386    final int lastIndex = names.size() - 1;
1387    final List<Element<Object>> elements;
1388    switch (lastIndex) {
1389    case -1:
1390      return new Path<>(Qualifiers.of(), List.of(), Element.of(qualified, null));
1391    case 0:
1392      return new Path<>(Qualifiers.of(), List.of(), Element.of(qualified, names.get(0)));
1393    default:
1394      elements = new ArrayList<>(lastIndex);
1395      for (int i = 0; i < lastIndex; i++) {
1396        final String name = names.get(i);
1397        elements.add(Element.of(name));
1398      }
1399      return new Path<>(Qualifiers.of(), elements, Element.of(qualified, names.get(lastIndex)));
1400    }
1401  }
1402
1403  /**
1404   * Return a (<strong>usually new</strong>) {@link Path} formed from
1405   * the supplied arguments and returns it.
1406   *
1407   * @param <T> the type of the {@link Path}
1408   *
1409   * @param pathQualifiers the {@link Path}'s {@linkplain Qualifiers
1410   * qualifiers}; must not be {@code null}
1411   *
1412   * @param lastElement the {@linkplain #lastElement() last
1413   * <code>Element</code>} of the {@link Path}; must not be {@code
1414   * null}
1415   *
1416   * @return a (<strong>usually new</strong>) {@link Path}
1417   *
1418   * @exception NullPointerException if any argument is {@code null}
1419   *
1420   * @nullability This method never returns {@code null}.
1421   *
1422   * @idempotency This method is idempotent and deterministic.
1423   *
1424   * @threadsafety This method is safe for concurrent use by multiple
1425   * threads.
1426   *
1427   * @see #Path(Qualifiers, List, Element)
1428   */
1429  public static final <T> Path<T> of(final Qualifiers<? extends String, ?> pathQualifiers,
1430                                     final Element<? extends T> lastElement) {
1431    return new Path<>(pathQualifiers, lastElement);
1432  }
1433
1434  /**
1435   * Return a (<strong>usually new</strong>) {@link Path} formed from
1436   * the supplied arguments and returns it.
1437   *
1438   * @param <T> the type of the new {@link Path}
1439   *
1440   * @param pathQualifiers the {@link Path}'s {@linkplain Qualifiers qualifiers}; must
1441   * not be {@code null}
1442   *
1443   * @param elements the interior {@link Element}s of the {@link
1444   * Path}; must not be {@code null}
1445   *
1446   * @param lastElement the {@linkplain #lastElement() last
1447   * <code>Element</code>} of the {@link Path}; must not be {@code
1448   * null}
1449   *
1450   * @return a (<strong>usually new</strong>) {@link Path}
1451   *
1452   * @exception NullPointerException if any argument is {@code null}
1453   *
1454   * @nullability This method never returns {@code null}.
1455   *
1456   * @idempotency This method is idempotent and deterministic.
1457   *
1458   * @threadsafety This method is safe for concurrent use by multiple
1459   * threads.
1460   *
1461   * @see #Path(Qualifiers, List, Element)
1462   */
1463  public static final <T> Path<T> of(final Qualifiers<? extends String, ?> pathQualifiers,
1464                                     final List<? extends Element<?>> elements,
1465                                     final Element<? extends T> lastElement) {
1466    return new Path<>(pathQualifiers, elements, lastElement);
1467  }
1468
1469  private static final String findUserPackageName(final Stream<StackFrame> stream) {
1470    final String className = stream.sequential()
1471      .dropWhile(f -> f.getClassName().startsWith(Path.class.getPackageName()))
1472      .dropWhile(f -> f.getClassName().contains(".$Proxy")) // skip JDK proxies (and any other kind of proxies)
1473      .map(StackFrame::getClassName)
1474      .findFirst()
1475      .orElse(null);
1476    if (className == null) {
1477      return "";
1478    } else {
1479      final int lastIndex = className.lastIndexOf('.');
1480      if (lastIndex < 0) {
1481        return "";
1482      } else if (lastIndex == 0) {
1483        throw new AssertionError("className: " + className);
1484      } else {
1485        return className.substring(0, lastIndex);
1486      }
1487    }
1488  }
1489
1490
1491  /*
1492   * Inner and nested classes.
1493   */
1494
1495
1496  /**
1497   * An element normally {@linkplain Path#iterator() within} a {@link
1498   * Path}, consisting of a {@link #qualifiers() Qualifiers}, a
1499   * {@linkplain #name() name}, and an optional {@linkplain
1500   * #qualified() thing that it designates or points to}.
1501   *
1502   * @param <T> the type of this {@link Element}
1503   *
1504   * @author <a href="https://about.me/lairdnelson"
1505   * target="_parent">Laird Nelson</a>
1506   */
1507  public static final class Element<T> implements Qualified<String, Object, T> {
1508
1509
1510    /*
1511     * Static fields.
1512     */
1513
1514
1515    private static final Element<?> ROOT = new Element<>();
1516
1517
1518    /*
1519     * Instance fields.
1520     */
1521
1522
1523    private final Qualifiers<String, Object> qualifiers;
1524
1525    private final T qualified;
1526
1527    private final String name;
1528
1529
1530    /*
1531     * Constructors.
1532     */
1533
1534
1535    // For use by ROOT only.
1536    private Element() {
1537      super();
1538      this.qualifiers = Qualifiers.of();
1539      this.qualified = null;
1540      this.name = "";
1541    }
1542
1543    /**
1544     * Creates a new {@link Element}.
1545     *
1546     * @param name the name of this {@link Element}; must not be
1547     * {@code null} or {@linkplain String#isEmpty() empty}
1548     *
1549     * @exception NullPointerException if {@code name} is {@code null}
1550     *
1551     * @exception IllegalArgumentException if {@code name} {@linkplain
1552     * String#isEmpty() is empty}
1553     *
1554     * @see #Element(Qualifiers, Object, String)
1555     */
1556    public Element(final String name) {
1557      this(Qualifiers.of(), null, name);
1558    }
1559
1560    /**
1561     * Creates a new {@link Element}.
1562     *
1563     * @param qualified the thing this {@link Element} describes; may
1564     * be {@code null}
1565     *
1566     * @param name the name of this {@link Element}; may be {@code
1567     * null} only if {@code qualified} is not {@code null}
1568     *
1569     * @exception NullPointerException if {@code qualified} is {@code
1570     * null} and {@code name} is {@code null}
1571     *
1572     * @exception IllegalArgumentException if {@code qualified} is
1573     * {@code null} and {@code name} {@linkplain String#isEmpty() is
1574     * empty}
1575     *
1576     * @see #Element(Qualifiers, Object, String)
1577     */
1578    public Element(final T qualified, final String name) {
1579      this(Qualifiers.of(), qualified, name);
1580    }
1581
1582    /**
1583     * Creates a new {@link Element}.
1584     *
1585     * @param qualifiers the {@linkplain Qualifiers qualifiers}
1586     * qualifying this {@link Element}; may be {@code null} in which
1587     * case an {@linkplain Qualifiers#of() empty
1588     * <code>Qualifiers</code>} will be used instead
1589     *
1590     * @param name the name of this {@link Element}; may be {@code
1591     * null} only if {@code qualified} is not {@code null}
1592     *
1593     * @exception NullPointerException if {@code name} is {@code null}
1594     *
1595     * @exception IllegalArgumentException if {@code name} {@linkplain
1596     * String#isEmpty() is empty}
1597     *
1598     * @see #Element(Qualifiers, Object, String)
1599     */
1600    @SuppressWarnings("unchecked")
1601    public Element(final Qualifiers<? extends String, ?> qualifiers, final String name) {
1602      super();
1603      if (name == null) {
1604        throw new NullPointerException("name");
1605      } else if (name.isEmpty()) {
1606        throw new IllegalArgumentException("An empty name may not be paired with a null qualified");
1607      } else {
1608        this.name = name;
1609      }
1610      this.qualifiers = qualifiers == null || qualifiers.isEmpty() ? Qualifiers.of() : (Qualifiers<String, Object>)qualifiers;
1611      this.qualified = null;
1612    }
1613
1614    /**
1615     * Creates a new {@link Element}.
1616     *
1617     * @param qualifiers the {@linkplain Qualifiers qualifiers}
1618     * qualifying this {@link Element}; may be {@code null} in which
1619     * case an {@linkplain Qualifiers#of() empty
1620     * <code>Qualifiers</code>} will be used instead
1621     *
1622     * @param qualified the thing this {@link Element} describes; may
1623     * be {@code null}
1624     *
1625     * @param name the name of this {@link Element}; may be {@code
1626     * null} only if {@code qualified} is not {@code null}
1627     *
1628     * @exception NullPointerException if {@code qualified} is {@code
1629     * null} and {@code name} is {@code null}
1630     *
1631     * @exception IllegalArgumentException if {@code qualified} is
1632     * {@code null} and {@code name} {@linkplain String#isEmpty() is
1633     * empty}
1634     */
1635    @SuppressWarnings("unchecked")
1636    public Element(final Qualifiers<? extends String, ?> qualifiers, final T qualified, final String name) {
1637      super();
1638      if (qualified == null) {
1639        if (name == null) {
1640          throw new NullPointerException("name");
1641        } else if (name.isEmpty()) {
1642          throw new IllegalArgumentException("An empty name may not be paired with a null qualified");
1643        } else {
1644          this.name = name;
1645        }
1646      } else {
1647        this.name = name == null ? "" : name;
1648      }
1649      this.qualifiers = qualifiers == null || qualifiers.isEmpty() ? Qualifiers.of() : (Qualifiers<String, Object>)qualifiers;
1650      this.qualified = qualified;
1651    }
1652
1653
1654    /*
1655     * Instance methods.
1656     */
1657
1658
1659    /**
1660     * Returns an {@link Optional} containing a {@link ConstantDesc}
1661     * representing this {@link Element}.
1662     *
1663     * @return an {@link Optional} containing a {@link ConstantDesc}
1664     * representing this {@link Element}; never {@code null}; possibly
1665     * {@linkplain Optional#isEmpty() empty}
1666     *
1667     * @nullability This method never returns {@code null}.
1668     *
1669     * @idempotency This method is idempotent and deterministic.
1670     *
1671     * @threadsafety This method is safe for concurrent use by
1672     * multiple threads.
1673     */
1674    @Override // Constable
1675    public final Optional<? extends ConstantDesc> describeConstable() {
1676      if (this.isRoot()) {
1677        return
1678          Optional.of(DynamicConstantDesc.ofNamed(BSM_INVOKE,
1679                                                  DEFAULT_NAME,
1680                                                  CD_PathElement,
1681                                                  MethodHandleDesc.ofMethod(STATIC,
1682                                                                            CD_PathElement,
1683                                                                            "root",
1684                                                                            MethodTypeDesc.of(CD_PathElement))));
1685      } else {
1686        final ConstantDesc qualifiersDesc = this.qualifiers().describeConstable().orElse(null);
1687        if (qualifiersDesc != null) {
1688          final ConstantDesc qualifiedDesc;
1689          final Object qualified = this.qualified();
1690          if (qualified == null) {
1691            qualifiedDesc = NULL;
1692          } else if (qualified instanceof Constable cq) {
1693            qualifiedDesc = cq.describeConstable().orElse(null);
1694          } else if (qualified instanceof ConstantDesc cd) {
1695            qualifiedDesc = cd;
1696          } else {
1697            qualifiedDesc = null;
1698          }
1699          if (qualifiedDesc != null) {
1700            final String name = this.name();
1701            return
1702              Optional.of(DynamicConstantDesc.ofNamed(BSM_INVOKE,
1703                                                      name,
1704                                                      CD_PathElement,
1705                                                      MethodHandleDesc.ofConstructor(CD_PathElement,
1706                                                                                     CD_Qualifiers,
1707                                                                                     CD_Object,
1708                                                                                     CD_String),
1709                                                      qualifiersDesc,
1710                                                      qualifiedDesc,
1711                                                      name));
1712          }
1713        }
1714      }
1715      return Optional.empty();
1716    }
1717
1718    /**
1719     * Returns the {@link Qualifiers} that qualifies this {@link
1720     * Element}.
1721     *
1722     * @return the {@link Qualifiers} that qualifies this {@link
1723     * Element}
1724     *
1725     * @nullability This method never returns {@code null}.
1726     *
1727     * @idempotency This method is idempotent and deterministic.
1728     *
1729     * @threadsafety This method is safe for concurrent use by multiple
1730     * threads.
1731     */
1732    @Override // Qualified<String, Object, T>
1733    public final Qualifiers<String, Object> qualifiers() {
1734      return this.qualifiers;
1735    }
1736
1737    /**
1738     * Returns the thing that this {@link Element} describes (which
1739     * may be nothing).
1740     *
1741     * @return the thing that this {@link Element} describes, which
1742     * may be nothing, in which case {@code null} will be returned
1743     *
1744     * @nullability This method may return {@code null}.
1745     *
1746     * @idempotency This method is idempotent and deterministic.
1747     *
1748     * @threadsafety This method is safe for concurrent use by
1749     * multiple threads.
1750     */
1751    @Override // Qualified<String, Object, T>
1752    public final T qualified() {
1753      return this.qualified;
1754    }
1755
1756    /**
1757     * Returns the name of this {@link Element}.
1758     *
1759     * @return the name of this {@link Element}
1760     *
1761     * @nullability This method never returns {@code null}.
1762     *
1763     * @idempotency This method is idempotent and deterministic.
1764     *
1765     * @threadsafety This method is safe for concurrent use by
1766     * multiple threads.
1767     */
1768    public final String name() {
1769      return this.name;
1770    }
1771
1772    /**
1773     * Returns {@code true} if this {@link Element} is a <em>root
1774     * element</em>, which is true when the {@link #qualified()}
1775     * method returns {@code null} and the {@link #name()} method
1776     * returns an {@linkplain String#isEmpty() empty
1777     * <code>String</code>}.
1778     *
1779     * @return {@code true} if and only if this {@link Element} is a
1780     * <em>root element</em>
1781     *
1782     * @idempotency This method is idempotent and deterministic.
1783     *
1784     * @threadsafety This method is safe for concurrent use by
1785     * multiple threads.
1786     */
1787    public final boolean isRoot() {
1788      return this.qualified() == null && this.name().isEmpty();
1789    }
1790
1791    /**
1792     * Returns a {@link Element}, <strong>usually newly
1793     * created</strong>, whose {@linkplain #qualifiers() qualifiers}
1794     * have keys that are prefixed with the supplied {@code prefix}.
1795     *
1796     * @param prefix the prefix to apply; may be {@code null} or
1797     * {@linkplain String#isEmpty() empty} in which case {@code this}
1798     * will be returned
1799     *
1800     * @return a {@link Element}, <strong>usually newly
1801     * created</strong>, whose {@linkplain #qualifiers() qualifiers}
1802     * have keys that are prefixed with the supplied {@code prefix}
1803     *
1804     * @nullability This method never returns {@code null}.
1805     *
1806     * @idempotency This method is idempotent and deterministic.
1807     *
1808     * @threadsafety This method is safe for concurrent use by
1809     * multiple threads.
1810     */
1811    public final Element<T> withQualifiersPrefix(final String prefix) {
1812      if (prefix == null || prefix.isEmpty()) {
1813        return this;
1814      }
1815      return Element.of(this.qualifiers().withPrefix(k -> prefix + k),
1816                        this.qualified(),
1817                        this.name());
1818    }
1819
1820    /**
1821     * Returns a hashcode for this {@link Element}.
1822     *
1823     * @return a hashcode for this {@link Element}
1824     *
1825     * @idempotency This method is idempotent.
1826     *
1827     * @threadsafety This method is safe for concurrent use by
1828     * multiple threads.
1829     */
1830    @Override // Object
1831    public final int hashCode() {
1832      int hashCode = 17;
1833      Object value = this.qualified();
1834      int c = value == null ? 0 : value.hashCode();
1835      hashCode = 37 * hashCode + c;
1836      value = this.name();
1837      c = value == null ? 0 : value.hashCode();
1838      hashCode = 37 * hashCode + c;
1839      value = this.qualifiers();
1840      c = value == null ? 0 : value.hashCode();
1841      hashCode = 37 * hashCode + c;
1842      return hashCode;
1843    }
1844
1845    /**
1846     * Returns {@code true} if the supplied {@link Object} is equal to
1847     * this {@link Element}.
1848     *
1849     * @param other the {@link Object} to test; may be {@code null} in
1850     * which case {@code false} will be returned
1851     *
1852     * @return {@code true} if the supplied {@link Object} is equal to
1853     * this {@link Element}; {@code false} otherwise
1854     *
1855     * @idempotency This method is idempotent and deterministic.
1856     *
1857     * @threadsafety This method is safe for concurrent use by
1858     * multiple threads.
1859     */
1860    @Override // Object
1861    public final boolean equals(final Object other) {
1862      if (this == other) {
1863        return true;
1864      } else if (other != null && this.getClass() == other.getClass()) {
1865        final Element<?> her = (Element<?>)other;
1866        return
1867          Objects.equals(this.qualified(), her.qualified()) &&
1868          Objects.equals(this.name(), her.name()) &&
1869          Objects.equals(this.qualifiers(), her.qualifiers());
1870      } else {
1871        return false;
1872      }
1873    }
1874
1875    /**
1876     * Returns a non-{@code null} {@link String} representation of
1877     * this {@link Element}.
1878     *
1879     * <p>The format of the {@link String} that is returned is
1880     * deliberately unspecified and subject to change without notice
1881     * from version to version of this class.</p>
1882     *
1883     * @return a {@link String} representation of this {@link Element}
1884     *
1885     * @nullability This method never returns {@code null}
1886     *
1887     * @idempotency This method is idempotent and deterministic.
1888     *
1889     * @threadsafety This method is safe for concurrent use by
1890     * multiple threads.
1891     */
1892    @Override // Object
1893    public final String toString() {
1894      final StringBuilder sb = new StringBuilder();
1895      final T qualified = this.qualified();
1896      if (qualified != null) {
1897        // Handle the extremely common case that qualified is a Type.
1898        sb.append(qualified instanceof Type t ? t.getTypeName() : qualified).append(':');
1899      }
1900      sb.append(name);
1901      final Qualifiers<?, ?> q = this.qualifiers();
1902      if (!q.isEmpty()) {
1903        sb.append(q.toString());
1904      }
1905      return sb.toString();
1906    }
1907
1908
1909    /*
1910     * Static methods.
1911     */
1912
1913
1914    /**
1915     * Returns a {@link Element} that {@linkplain #isRoot() is a
1916     * <em>root element</em>}.
1917     *
1918     * @return a {@link Element} that {@linkplain #isRoot() is a
1919     * <em>root element</em>}
1920     *
1921     * @nullability This method never returns {@code null}.
1922     *
1923     * @idempotency This method is idempotent and deterministic.
1924     *
1925     * @threadsafety This method is safe for concurrent use by
1926     * multiple threads.
1927     */
1928    public static final Element<?> root() {
1929      return ROOT;
1930    }
1931
1932    /**
1933     * Returns a {@link Element} representing the supplied arguments.
1934     *
1935     * <p>The returned {@link Element} may be newly created or it may
1936     * be cached.  No assumption must be made about its identity.</p>
1937     *
1938     * @param <T> the type of this {@link Element}
1939     *
1940     * @param qualifiers the {@link Qualifiers} qualifying this {@link
1941     * Element}; may be {@code null} in which case an {@linkplain
1942     * Qualifiers#of() empty <code>Qualifiers</code>} will be used
1943     * instead
1944     *
1945     * @param qualified the thing this {@link Element} describes; may
1946     * be {@code null}
1947     *
1948     * @param name the name of this {@link Element}; may be {@code
1949     * null} only if {@code qualified} is not {@code null}
1950     *
1951     * @return a {@link Element} representing the supplied arguments
1952     *
1953     * @exception NullPointerException if {@code qualified} is {@code
1954     * null} and {@code name} is {@code null}
1955     *
1956     * @exception IllegalArgumentException if {@code qualified} is
1957     * {@code null} and {@code name} {@linkplain String#isEmpty() is
1958     * empty}
1959     *
1960     * @nullability This method never returns {@code null}.
1961     *
1962     * @idempotency This method is idempotent and deterministic.
1963     *
1964     * @threadsafety This method is safe for concurrent use by
1965     * multiple threads.
1966     */
1967    public static final <T> Element<T> of(final Qualifiers<? extends String, ?> qualifiers,
1968                                          final T qualified,
1969                                          final String name) {
1970      return new Element<>(qualifiers, qualified, name);
1971    }
1972
1973    /**
1974     * Returns a {@link Element} representing the supplied arguments.
1975     *
1976     * <p>The returned {@link Element} may be newly created or it may
1977     * be cached.  No assumption must be made about its identity.</p>
1978     *
1979     * @param <T> the type of this {@link Element}
1980     *
1981     * @param qualified the thing this {@link Element} describes; may
1982     * be {@code null}
1983     *
1984     * @param name the name of this {@link Element}; may be {@code
1985     * null} only if {@code qualified} is not {@code null}
1986     *
1987     * @return a {@link Element} representing the supplied arguments
1988     *
1989     * @exception NullPointerException if {@code qualified} is {@code
1990     * null} and {@code name} is {@code null}
1991     *
1992     * @exception IllegalArgumentException if {@code qualified} is
1993     * {@code null} and {@code name} {@linkplain String#isEmpty() is
1994     * empty}
1995     *
1996     * @nullability This method never returns {@code null}.
1997     *
1998     * @idempotency This method is idempotent and deterministic.
1999     *
2000     * @threadsafety This method is safe for concurrent use by
2001     * multiple threads.
2002     */
2003    public static final <T> Element<T> of(final T qualified, final String name) {
2004      return new Element<>(qualified, name);
2005    }
2006
2007    /**
2008     * Returns a {@link Element} representing the supplied arguments.
2009     *
2010     * <p>The returned {@link Element} may be newly created or it may
2011     * be cached.  No assumption must be made about its identity.</p>
2012     *
2013     * @param <T> the type of this {@link Element}
2014     *
2015     * @param name the name of this {@link Element}; may be {@code
2016     * null} only if {@code qualified} is not {@code null}
2017     *
2018     * @return a {@link Element} representing the supplied arguments
2019     *
2020     * @exception NullPointerException if {@code qualified} is {@code
2021     * null} and {@code name} is {@code null}
2022     *
2023     * @exception IllegalArgumentException if {@code qualified} is
2024     * {@code null} and {@code name} {@linkplain String#isEmpty() is
2025     * empty}
2026     *
2027     * @nullability This method never returns {@code null}.
2028     *
2029     * @idempotency This method is idempotent and deterministic.
2030     *
2031     * @threadsafety This method is safe for concurrent use by
2032     * multiple threads.
2033     */
2034    public static final <T> Element<T> of(final String name) {
2035      return new Element<>(name);
2036    }
2037
2038  }
2039
2040}