1 /*
2  * JBoss, Home of Professional Open Source.
3  * Copyright 2014 Red Hat, Inc., and individual contributors
4  * as indicated by the @author tags.
5  *
6  * Licensed under the Apache License, Version 2.0 (the "License");
7  * you may not use this file except in compliance with the License.
8  * You may obtain a copy of the License at
9  *
10  *     http://www.apache.org/licenses/LICENSE-2.0
11  *
12  *  Unless required by applicable law or agreed to in writing, software
13  *  distributed under the License is distributed on an "AS IS" BASIS,
14  *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15  *  See the License for the specific language governing permissions and
16  *  limitations under the License.
17  */
18
19 package io.undertow.util;
20
21 import io.undertow.UndertowMessages;
22
23 import java.util.Comparator;
24 import java.util.HashMap;
25 import java.util.HashSet;
26 import java.util.Iterator;
27 import java.util.Map;
28 import java.util.Map.Entry;
29 import java.util.Set;
30 import java.util.TreeSet;
31
32 /**
33  * Utility class that provides fast path matching of path templates. Templates are stored in a map based on the stem of the template,
34  * and matches longest stem first.
35  * <p>
36  * TODO: we can probably do this faster using a trie type structure, but I think the current impl should perform ok most of the time
37  *
38  * @author Stuart Douglas
39  */
40 public class PathTemplateMatcher<T> {
41
42     /**
43      * Map of path template stem to the path templates that share the same base.
44      */
45     private Map<String, Set<PathTemplateHolder>> pathTemplateMap = new CopyOnWriteMap<>();
46
47     /**
48      * lengths of all registered paths
49      */
50     private volatile int[] lengths = {};
51
52     public PathMatchResult<T> match(final String path) {
53         String normalizedPath = "".equals(path) ? "/" : path;
54         final Map<String, String> params = new HashMap<>();
55         int length = normalizedPath.length();
56         final int[] lengths = this.lengths;
57         for (int i = 0; i < lengths.length; ++i) {
58             int pathLength = lengths[i];
59             if (pathLength == length) {
60                 Set<PathTemplateHolder> entry = pathTemplateMap.get(normalizedPath);
61                 if (entry != null) {
62                     PathMatchResult<T> res = handleStemMatch(entry, normalizedPath, params);
63                     if (res != null) {
64                         return res;
65                     }
66                 }
67             } else if (pathLength < length) {
68                 String part = normalizedPath.substring(0, pathLength);
69                 Set<PathTemplateHolder> entry = pathTemplateMap.get(part);
70                 if (entry != null) {
71                     PathMatchResult<T> res = handleStemMatch(entry, normalizedPath, params);
72                     if (res != null) {
73                         return res;
74                     }
75                 }
76             }
77         }
78         return null;
79     }
80
81     private PathMatchResult<T> handleStemMatch(Set<PathTemplateHolder> entry, final String path, final Map<String, String> params) {
82         for (PathTemplateHolder val : entry) {
83             if (val.template.matches(path, params)) {
84                 return new PathMatchResult<>(params, val.template.getTemplateString(), val.value);
85             } else {
86                 params.clear();
87             }
88         }
89         return null;
90     }
91
92
93     public synchronized PathTemplateMatcher<T> add(final PathTemplate template, final T value) {
94         Set<PathTemplateHolder> values = pathTemplateMap.get(trimBase(template));
95         Set<PathTemplateHolder> newValues;
96         if (values == null) {
97             newValues = new TreeSet<>();
98         } else {
99             newValues = new TreeSet<>(values);
100         }
101         PathTemplateHolder holder = new PathTemplateHolder(value, template);
102         if (newValues.contains(holder)) {
103             PathTemplate equivalent = null;
104             for (PathTemplateHolder item : newValues) {
105                 if (item.compareTo(holder) == 0) {
106                     equivalent = item.template;
107                     break;
108                 }
109             }
110             throw UndertowMessages.MESSAGES.matcherAlreadyContainsTemplate(template.getTemplateString(), equivalent.getTemplateString());
111         }
112         newValues.add(holder);
113         pathTemplateMap.put(trimBase(template), newValues);
114         buildLengths();
115         return this;
116     }
117
118     private String trimBase(PathTemplate template) {
119         String retval = template.getBase();
120
121         if (template.getBase().endsWith("/") && !template.getParameterNames().isEmpty()) {
122             return retval.substring(0, retval.length() - 1);
123         }
124         if (retval.endsWith("*")) {
125             return retval.substring(0, retval.length() - 1);
126         }
127         return retval;
128     }
129
130     private void buildLengths() {
131         final Set<Integer> lengths = new TreeSet<>(new Comparator<Integer>() {
132             @Override
133             public int compare(Integer o1, Integer o2) {
134                 return -o1.compareTo(o2);
135             }
136         });
137         for (String p : pathTemplateMap.keySet()) {
138             lengths.add(p.length());
139         }
140
141         int[] lengthArray = new int[lengths.size()];
142         int pos = 0;
143         for (int i : lengths) {
144             lengthArray[pos++] = i; //-1 because the base paths end with a /
145         }
146         this.lengths = lengthArray;
147     }
148
149     public synchronized PathTemplateMatcher<T> add(final String pathTemplate, final T value) {
150         final PathTemplate template = PathTemplate.create(pathTemplate);
151         return add(template, value);
152     }
153
154     public synchronized PathTemplateMatcher<T> addAll(PathTemplateMatcher<T> pathTemplateMatcher) {
155         for (Entry<String, Set<PathTemplateHolder>> entry : pathTemplateMatcher.getPathTemplateMap().entrySet()) {
156             for (PathTemplateHolder pathTemplateHolder : entry.getValue()) {
157                 add(pathTemplateHolder.template, pathTemplateHolder.value);
158             }
159         }
160         return this;
161     }
162
163     Map<String, Set<PathTemplateHolder>> getPathTemplateMap() {
164         return pathTemplateMap;
165     }
166
167     public Set<PathTemplate> getPathTemplates() {
168         Set<PathTemplate> templates = new HashSet<>();
169         for (Set<PathTemplateHolder> holders : pathTemplateMap.values()) {
170             for (PathTemplateHolder holder: holders) {
171                 templates.add(holder.template);
172             }
173         }
174         return templates;
175     }
176
177     public synchronized PathTemplateMatcher<T> remove(final String pathTemplate) {
178         final PathTemplate template = PathTemplate.create(pathTemplate);
179         return remove(template);
180     }
181
182     private synchronized PathTemplateMatcher<T> remove(PathTemplate template) {
183         Set<PathTemplateHolder> values = pathTemplateMap.get(trimBase(template));
184         Set<PathTemplateHolder> newValues;
185         if (values == null) {
186             return this;
187         } else {
188             newValues = new TreeSet<>(values);
189         }
190         Iterator<PathTemplateHolder> it = newValues.iterator();
191         while (it.hasNext()) {
192             PathTemplateHolder next = it.next();
193             if (next.template.getTemplateString().equals(template.getTemplateString())) {
194                 it.remove();
195                 break;
196             }
197         }
198         if (newValues.size() == 0) {
199             pathTemplateMap.remove(trimBase(template));
200         } else {
201             pathTemplateMap.put(trimBase(template), newValues);
202         }
203         buildLengths();
204         return this;
205     }
206
207
208     public synchronized T get(String template) {
209         PathTemplate pathTemplate = PathTemplate.create(template);
210         Set<PathTemplateHolder> values = pathTemplateMap.get(trimBase(pathTemplate));
211         if(values == null) {
212             return null;
213         }
214         for (PathTemplateHolder next : values) {
215             if (next.template.getTemplateString().equals(template)) {
216                 return next.value;
217             }
218         }
219         return null;
220     }
221
222     public static class PathMatchResult<T> extends PathTemplateMatch {
223         private final T value;
224
225         public PathMatchResult(Map<String, String> parameters, String matchedTemplate, T value) {
226             super(matchedTemplate, parameters);
227             this.value = value;
228         }
229
230         public T getValue() {
231             return value;
232         }
233     }
234
235     private final class PathTemplateHolder implements Comparable<PathTemplateHolder> {
236         final T value;
237         final PathTemplate template;
238
239         private PathTemplateHolder(T value, PathTemplate template) {
240             this.value = value;
241             this.template = template;
242         }
243
244         @Override
245         public boolean equals(Object o) {
246             if (this == o) return true;
247             if (o == null) return false;
248             if (!PathTemplateHolder.class.equals(o.getClass())) return false;
249
250             PathTemplateHolder that = (PathTemplateHolder) o;
251             return template.equals(that.template);
252         }
253
254         @Override
255         public int hashCode() {
256             return template.hashCode();
257         }
258
259         @Override
260         public int compareTo(PathTemplateHolder o) {
261             return template.compareTo(o.template);
262         }
263     }
264
265 }
266