001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  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 implied.
014 * See the License for the specific language governing permissions and
015 * limitations under the License.
016 */
017package org.apache.commons.configuration2.tree;
018
019import java.util.Collection;
020import java.util.LinkedList;
021import java.util.List;
022
023import org.apache.commons.lang3.StringUtils;
024
025/**
026 * <p>
027 * A default implementation of the {@code ExpressionEngine} interface providing the &quot;native&quot; expression
028 * language for hierarchical configurations.
029 * </p>
030 * <p>
031 * This class implements a rather simple expression language for navigating through a hierarchy of configuration nodes.
032 * It supports the following operations:
033 * </p>
034 * <ul>
035 * <li>Navigating from a node to one of its children using the child node delimiter, which is by the default a dot
036 * (&quot;.&quot;).</li>
037 * <li>Navigating from a node to one of its attributes using the attribute node delimiter, which by default follows the
038 * XPATH like syntax {@code [@&lt;attributeName&gt;]}.</li>
039 * <li>If there are multiple child or attribute nodes with the same name, a specific node can be selected using a
040 * numerical index. By default indices are written in parenthesis.</li>
041 * </ul>
042 * <p>
043 * As an example consider the following XML document:
044 * </p>
045 *
046 * <pre>
047 *  &lt;database&gt;
048 *    &lt;tables&gt;
049 *      &lt;table type=&quot;system&quot;&gt;
050 *        &lt;name&gt;users&lt;/name&gt;
051 *        &lt;fields&gt;
052 *          &lt;field&gt;
053 *            &lt;name&gt;lid&lt;/name&gt;
054 *            &lt;type&gt;long&lt;/name&gt;
055 *          &lt;/field&gt;
056 *          &lt;field&gt;
057 *            &lt;name&gt;usrName&lt;/name&gt;
058 *            &lt;type&gt;java.lang.String&lt;/type&gt;
059 *          &lt;/field&gt;
060 *         ...
061 *        &lt;/fields&gt;
062 *      &lt;/table&gt;
063 *      &lt;table&gt;
064 *        &lt;name&gt;documents&lt;/name&gt;
065 *        &lt;fields&gt;
066 *          &lt;field&gt;
067 *            &lt;name&gt;docid&lt;/name&gt;
068 *            &lt;type&gt;long&lt;/type&gt;
069 *          &lt;/field&gt;
070 *          ...
071 *        &lt;/fields&gt;
072 *      &lt;/table&gt;
073 *      ...
074 *    &lt;/tables&gt;
075 *  &lt;/database&gt;
076 * </pre>
077 *
078 * <p>
079 * If this document is parsed and stored in a hierarchical configuration object, for instance the key
080 * {@code tables.table(0).name} can be used to find out the name of the first table. In opposite
081 * {@code tables.table.name} would return a collection with the names of all available tables. Similarly the key
082 * {@code tables.table(1).fields.field.name} returns a collection with the names of all fields of the second table. If
083 * another index is added after the {@code field} element, a single field can be accessed:
084 * {@code tables.table(1).fields.field(0).name}. The key {@code tables.table(0)[@type]} would select the type attribute
085 * of the first table.
086 * </p>
087 * <p>
088 * This example works with the default values for delimiters and index markers. It is also possible to set custom values
089 * for these properties so that you can adapt a {@code DefaultExpressionEngine} to your personal needs.
090 * </p>
091 * <p>
092 * The concrete symbols used by an instance are determined by a {@link DefaultExpressionEngineSymbols} object passed to
093 * the constructor. By providing a custom symbols object the syntax for querying properties in a hierarchical
094 * configuration can be altered.
095 * </p>
096 * <p>
097 * Instances of this class are thread-safe and can be shared between multiple hierarchical configuration objects.
098 * </p>
099 *
100 * @since 1.3
101 */
102public class DefaultExpressionEngine implements ExpressionEngine {
103    /**
104     * A default instance of this class that is used as expression engine for hierarchical configurations per default.
105     */
106    public static final DefaultExpressionEngine INSTANCE = new DefaultExpressionEngine(DefaultExpressionEngineSymbols.DEFAULT_SYMBOLS);
107
108    /** The symbols used by this instance. */
109    private final DefaultExpressionEngineSymbols symbols;
110
111    /** The matcher for node names. */
112    private final NodeMatcher<String> nameMatcher;
113
114    /**
115     * Creates a new instance of {@code DefaultExpressionEngine} and initializes its symbols.
116     *
117     * @param syms the object with the symbols (must not be <b>null</b>)
118     * @throws IllegalArgumentException if the symbols are <b>null</b>
119     */
120    public DefaultExpressionEngine(final DefaultExpressionEngineSymbols syms) {
121        this(syms, null);
122    }
123
124    /**
125     * Creates a new instance of {@code DefaultExpressionEngine} and initializes its symbols and the matcher for comparing
126     * node names. The passed in matcher is always used when the names of nodes have to be matched against parts of
127     * configuration keys.
128     *
129     * @param syms the object with the symbols (must not be <b>null</b>)
130     * @param nodeNameMatcher the matcher for node names; can be <b>null</b>, then a default matcher is used
131     * @throws IllegalArgumentException if the symbols are <b>null</b>
132     */
133    public DefaultExpressionEngine(final DefaultExpressionEngineSymbols syms, final NodeMatcher<String> nodeNameMatcher) {
134        if (syms == null) {
135            throw new IllegalArgumentException("Symbols must not be null!");
136        }
137
138        symbols = syms;
139        nameMatcher = nodeNameMatcher != null ? nodeNameMatcher : NodeNameMatchers.EQUALS;
140    }
141
142    /**
143     * Gets the {@code DefaultExpressionEngineSymbols} object associated with this instance.
144     *
145     * @return the {@code DefaultExpressionEngineSymbols} used by this engine
146     * @since 2.0
147     */
148    public DefaultExpressionEngineSymbols getSymbols() {
149        return symbols;
150    }
151
152    /**
153     * {@inheritDoc} This method supports the syntax as described in the class comment.
154     */
155    @Override
156    public <T> List<QueryResult<T>> query(final T root, final String key, final NodeHandler<T> handler) {
157        final List<QueryResult<T>> results = new LinkedList<>();
158        findNodesForKey(new DefaultConfigurationKey(this, key).iterator(), root, results, handler);
159        return results;
160    }
161
162    /**
163     * {@inheritDoc} This implementation takes the given parent key, adds a property delimiter, and then adds the node's
164     * name. The name of the root node is a blank string. Note that no indices are returned.
165     */
166    @Override
167    public <T> String nodeKey(final T node, final String parentKey, final NodeHandler<T> handler) {
168        if (parentKey == null) {
169            // this is the root node
170            return StringUtils.EMPTY;
171        }
172        final DefaultConfigurationKey key = new DefaultConfigurationKey(this, parentKey);
173        key.append(handler.nodeName(node), true);
174        return key.toString();
175    }
176
177    @Override
178    public String attributeKey(final String parentKey, final String attributeName) {
179        final DefaultConfigurationKey key = new DefaultConfigurationKey(this, parentKey);
180        key.appendAttribute(attributeName);
181        return key.toString();
182    }
183
184    /**
185     * {@inheritDoc} This implementation works similar to {@code nodeKey()}; however, each key returned by this method has
186     * an index (except for the root node). The parent key is prepended to the name of the current node in any case and
187     * without further checks. If it is <b>null</b>, only the name of the current node with its index is returned.
188     */
189    @Override
190    public <T> String canonicalKey(final T node, final String parentKey, final NodeHandler<T> handler) {
191        final String nodeName = handler.nodeName(node);
192        final T parent = handler.getParent(node);
193        final DefaultConfigurationKey key = new DefaultConfigurationKey(this, parentKey);
194        key.append(StringUtils.defaultString(nodeName));
195
196        if (parent != null) {
197            // this is not the root key
198            key.appendIndex(determineIndex(node, parent, nodeName, handler));
199        }
200        return key.toString();
201    }
202
203    /**
204     * <p>
205     * Prepares Adding the property with the specified key.
206     * </p>
207     * <p>
208     * To be able to deal with the structure supported by hierarchical configuration implementations the passed in key is of
209     * importance, especially the indices it might contain. The following example should clarify this: Suppose the current
210     * node structure looks like the following:
211     * </p>
212     *
213     * <pre>
214     *  tables
215     *     +-- table
216     *             +-- name = user
217     *             +-- fields
218     *                     +-- field
219     *                             +-- name = uid
220     *                     +-- field
221     *                             +-- name = firstName
222     *                     ...
223     *     +-- table
224     *             +-- name = documents
225     *             +-- fields
226     *                    ...
227     * </pre>
228     * <p>
229     * In this example a database structure is defined, e.g. all fields of the first table could be accessed using the key
230     * {@code tables.table(0).fields.field.name}. If now properties are to be added, it must be exactly specified at which
231     * position in the hierarchy the new property is to be inserted. So to add a new field name to a table it is not enough
232     * to say just
233     * </p>
234     *
235     * <pre>
236     * config.addProperty(&quot;tables.table.fields.field.name&quot;, &quot;newField&quot;);
237     * </pre>
238     * <p>
239     * The statement given above contains some ambiguity. For instance it is not clear, to which table the new field should
240     * be added. If this method finds such an ambiguity, it is resolved by following the last valid path. Here this would be
241     * the last table. The same is true for the {@code field}; because there are multiple fields and no explicit index is
242     * provided, a new {@code name} property would be added to the last field - which is probably not what was desired.
243     * </p>
244     * <p>
245     * To make things clear explicit indices should be provided whenever possible. In the example above the exact table
246     * could be specified by providing an index for the {@code table} element as in {@code tables.table(1).fields}. By
247     * specifying an index it can also be expressed that at a given position in the configuration tree a new branch should
248     * be added. In the example above we did not want to add an additional {@code name} element to the last field of the
249     * table, but we want a complete new {@code field} element. This can be achieved by specifying an invalid index (like
250     * -1) after the element where a new branch should be created. Given this our example would run:
251     * </p>
252     *
253     * <pre>
254     * config.addProperty(&quot;tables.table(1).fields.field(-1).name&quot;, &quot;newField&quot;);
255     * </pre>
256     * <p>
257     * With this notation it is possible to add new branches everywhere. We could for instance create a new {@code table}
258     * element by specifying
259     * </p>
260     *
261     * <pre>
262     * config.addProperty(&quot;tables.table(-1).fields.field.name&quot;, &quot;newField2&quot;);
263     * </pre>
264     * <p>
265     * (Note that because after the {@code table} element a new branch is created indices in following elements are not
266     * relevant; the branch is new so there cannot be any ambiguities.)
267     * </p>
268     *
269     * @param <T> the type of the nodes to be dealt with
270     * @param root the root node of the nodes hierarchy
271     * @param key the key of the new property
272     * @param handler the node handler
273     * @return a data object with information needed for the add operation
274     */
275    @Override
276    public <T> NodeAddData<T> prepareAdd(final T root, final String key, final NodeHandler<T> handler) {
277        final DefaultConfigurationKey.KeyIterator it = new DefaultConfigurationKey(this, key).iterator();
278        if (!it.hasNext()) {
279            throw new IllegalArgumentException("Key for add operation must be defined!");
280        }
281
282        final T parent = findLastPathNode(it, root, handler);
283        final List<String> pathNodes = new LinkedList<>();
284
285        while (it.hasNext()) {
286            if (!it.isPropertyKey()) {
287                throw new IllegalArgumentException("Invalid key for add operation: " + key + " (Attribute key in the middle.)");
288            }
289            pathNodes.add(it.currentKey());
290            it.next();
291        }
292
293        return new NodeAddData<>(parent, it.currentKey(), !it.isPropertyKey(), pathNodes);
294    }
295
296    /**
297     * Recursive helper method for evaluating a key. This method processes all facets of a configuration key, traverses the
298     * tree of properties and fetches the results of all matching properties.
299     *
300     * @param <T> the type of nodes to be dealt with
301     * @param keyPart the configuration key iterator
302     * @param node the current node
303     * @param results here the found results are stored
304     * @param handler the node handler
305     */
306    protected <T> void findNodesForKey(final DefaultConfigurationKey.KeyIterator keyPart, final T node, final Collection<QueryResult<T>> results,
307        final NodeHandler<T> handler) {
308        if (!keyPart.hasNext()) {
309            results.add(QueryResult.createNodeResult(node));
310        } else {
311            final String key = keyPart.nextKey(false);
312            if (keyPart.isPropertyKey()) {
313                processSubNodes(keyPart, findChildNodesByName(handler, node, key), results, handler);
314            }
315            if (keyPart.isAttribute() && !keyPart.hasNext() && handler.getAttributeValue(node, key) != null) {
316                results.add(QueryResult.createAttributeResult(node, key));
317            }
318        }
319    }
320
321    /**
322     * Finds the last existing node for an add operation. This method traverses the node tree along the specified key. The
323     * last existing node on this path is returned.
324     *
325     * @param <T> the type of the nodes to be dealt with
326     * @param keyIt the key iterator
327     * @param node the current node
328     * @param handler the node handler
329     * @return the last existing node on the given path
330     */
331    protected <T> T findLastPathNode(final DefaultConfigurationKey.KeyIterator keyIt, final T node, final NodeHandler<T> handler) {
332        final String keyPart = keyIt.nextKey(false);
333
334        if (keyIt.hasNext()) {
335            if (!keyIt.isPropertyKey()) {
336                // Attribute keys can only appear as last elements of the path
337                throw new IllegalArgumentException("Invalid path for add operation: " + "Attribute key in the middle!");
338            }
339            final int idx = keyIt.hasIndex() ? keyIt.getIndex() : handler.getMatchingChildrenCount(node, nameMatcher, keyPart) - 1;
340            if (idx < 0 || idx >= handler.getMatchingChildrenCount(node, nameMatcher, keyPart)) {
341                return node;
342            }
343            return findLastPathNode(keyIt, findChildNodesByName(handler, node, keyPart).get(idx), handler);
344        }
345        return node;
346    }
347
348    /**
349     * Called by {@code findNodesForKey()} to process the sub nodes of the current node depending on the type of the current
350     * key part (children, attributes, or both).
351     *
352     * @param <T> the type of the nodes to be dealt with
353     * @param keyPart the key part
354     * @param subNodes a list with the sub nodes to process
355     * @param nodes the target collection
356     * @param handler the node handler
357     */
358    private <T> void processSubNodes(final DefaultConfigurationKey.KeyIterator keyPart, final List<T> subNodes, final Collection<QueryResult<T>> nodes,
359        final NodeHandler<T> handler) {
360        if (keyPart.hasIndex()) {
361            if (keyPart.getIndex() >= 0 && keyPart.getIndex() < subNodes.size()) {
362                findNodesForKey((DefaultConfigurationKey.KeyIterator) keyPart.clone(), subNodes.get(keyPart.getIndex()), nodes, handler);
363            }
364        } else {
365            subNodes.forEach(node -> findNodesForKey((DefaultConfigurationKey.KeyIterator) keyPart.clone(), node, nodes, handler));
366        }
367    }
368
369    /**
370     * Determines the index of the given node based on its parent node.
371     *
372     * @param node the current node
373     * @param parent the parent node
374     * @param nodeName the name of the current node
375     * @param handler the node handler
376     * @param <T> the type of the nodes to be dealt with
377     * @return the index of this node
378     */
379    private <T> int determineIndex(final T node, final T parent, final String nodeName, final NodeHandler<T> handler) {
380        return findChildNodesByName(handler, parent, nodeName).indexOf(node);
381    }
382
383    /**
384     * Returns a list with all child nodes of the given parent node which match the specified node name. The match is done
385     * using the current node name matcher.
386     *
387     * @param handler the {@code NodeHandler}
388     * @param parent the parent node
389     * @param nodeName the name of the current node
390     * @param <T> the type of the nodes to be dealt with
391     * @return a list with all matching child nodes
392     */
393    private <T> List<T> findChildNodesByName(final NodeHandler<T> handler, final T parent, final String nodeName) {
394        return handler.getMatchingChildren(parent, nameMatcher, nodeName);
395    }
396}