001/*
002 * Licensed to the Apache Software Foundation (ASF) under one
003 * or more contributor license agreements.  See the NOTICE file
004 * distributed with this work for additional information
005 * regarding copyright ownership.  The ASF licenses this file
006 * to you under the Apache License, Version 2.0 (the
007 * "License"); you may not use this file except in compliance
008 * with the License.  You may obtain a copy of the License at
009 *
010 *   http://www.apache.org/licenses/LICENSE-2.0
011 *
012 * Unless required by applicable law or agreed to in writing,
013 * software distributed under the License is distributed on an
014 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
015 * KIND, either express or implied.  See the License for the
016 * specific language governing permissions and limitations
017 * under the License.
018 */
019package org.eclipse.aether.internal.impl.filter.ruletree;
020
021import java.util.Arrays;
022import java.util.HashMap;
023import java.util.List;
024import java.util.concurrent.atomic.AtomicInteger;
025import java.util.stream.Stream;
026
027import static java.util.stream.Collectors.toList;
028
029/**
030 * Prefix tree for paths: if you step on a path prefix that exists, you are good to go.
031 * This class parses a text file that has a prefix on each line:
032 * <ul>
033 *     <li>ignored/formatting - each line starting with {@code '#'} (hash) or being empty/blank is ignored.</li>
034 *     <li>a path prefix  ie "/org/apache/maven".</li>
035 * </ul>
036 * By default, artifact is allowed if layout converted path of it has a matching prefix in this file.
037 *
038 * <p>
039 * Example prefix files:
040 * <ul>
041 *     <li><a href="https://repo.maven.apache.org/maven2/.meta/prefixes.txt">Maven Central</a></li>
042 *     <li><a href="https://repository.apache.org/content/repositories/releases/.meta/prefixes.txt">ASF Releases</a></li>
043 *     <li><a href="https://repo.eclipse.org/content/repositories/tycho/.meta/prefixes.txt">Eclipse Tycho</a></li>
044 * </ul>
045 */
046public class PrefixTree {
047    private static List<String> elementsOfPath(final String path) {
048        return Arrays.stream(path.split("/")).filter(e -> !e.isEmpty()).collect(toList());
049    }
050
051    private final String name;
052    private final HashMap<String, PrefixTree> children;
053    private final boolean leaf;
054
055    public PrefixTree(String name) {
056        this(name, false);
057    }
058
059    private PrefixTree(String name, boolean leaf) {
060        this.name = name;
061        this.children = new HashMap<>();
062        this.leaf = leaf;
063    }
064
065    public boolean isLeaf() {
066        return leaf;
067    }
068
069    public int loadNodes(Stream<String> linesStream) {
070        AtomicInteger counter = new AtomicInteger(0);
071        linesStream.forEach(line -> {
072            if (loadNode(line)) {
073                counter.incrementAndGet();
074            }
075        });
076        return counter.get();
077    }
078
079    /**
080     * Adds a line to the tree:
081     * <ul>
082     *     <li>it parses the URI-path-like element into list of segments {@link #elementsOfPath(String)}</li>
083     *     <li>cycles over the list, and marks last node added as {@code leaf=true}</li>
084     *     <li>if already on leaf node, processing stops (shorter path wins)</li>
085     * </ul>
086     */
087    public boolean loadNode(String line) {
088        if (!line.startsWith("#") && !line.trim().isEmpty()) {
089            final List<String> elements = elementsOfPath(line);
090            final int lastElementIdx = elements.size() - 1;
091            PrefixTree currentNode = this;
092            for (int i = 0; i <= lastElementIdx; i++) {
093                String element = elements.get(i);
094                boolean leaf = i == lastElementIdx;
095                PrefixTree siblingNode = currentNode.children.get(element);
096                if (leaf && siblingNode != null && !siblingNode.isLeaf()) {
097                    // shorter wins regardless of load order: we got /a/b/c, now /a/b arrives, drop the subtree
098                    siblingNode = new PrefixTree(element, true);
099                    currentNode.children.put(element, siblingNode);
100                }
101                if (siblingNode == null) {
102                    if (currentNode.isLeaf()) {
103                        break; // shorter wins: we got /a/b/c, but we already had /a/b
104                    } else {
105                        siblingNode = new PrefixTree(element, leaf);
106                        currentNode.children.put(element, siblingNode);
107                    }
108                }
109                currentNode = siblingNode;
110            }
111            return true;
112        }
113        return false;
114    }
115
116    public boolean acceptedPath(String path) {
117        final List<String> pathElements = elementsOfPath(path);
118        PrefixTree currentNode = this;
119        for (String pathElement : pathElements) {
120            currentNode = currentNode.children.get(pathElement);
121            if (currentNode == null || currentNode.isLeaf()) {
122                break;
123            }
124        }
125        // path is accepted if its elements lead to an existing node that is a leaf node
126        return currentNode != null && currentNode.isLeaf();
127    }
128}