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.configuration.tree;
018
019import java.util.Collection;
020import java.util.LinkedList;
021import java.util.List;
022
023import org.apache.commons.lang.StringUtils;
024
025/**
026 * <p>
027 * A default implementation of the {@code ExpressionEngine} interface
028 * providing the &quot;native&quote; expression language for hierarchical
029 * configurations.
030 * </p>
031 * <p>
032 * This class implements a rather simple expression language for navigating
033 * through a hierarchy of configuration nodes. It supports the following
034 * operations:
035 * </p>
036 * <p>
037 * <ul>
038 * <li>Navigating from a node to one of its children using the child node
039 * delimiter, which is by the default a dot (&quot;.&quot;).</li>
040 * <li>Navigating from a node to one of its attributes using the attribute node
041 * delimiter, which by default follows the XPATH like syntax
042 * <code>[@&lt;attributeName&gt;]</code>.</li>
043 * <li>If there are multiple child or attribute nodes with the same name, a
044 * specific node can be selected using a numerical index. By default indices are
045 * written in parenthesis.</li>
046 * </ul>
047 * </p>
048 * <p>
049 * As an example consider the following XML document:
050 * </p>
051 *
052 * <pre>
053 *  &lt;database&gt;
054 *    &lt;tables&gt;
055 *      &lt;table type=&quot;system&quot;&gt;
056 *        &lt;name&gt;users&lt;/name&gt;
057 *        &lt;fields&gt;
058 *          &lt;field&gt;
059 *            &lt;name&gt;lid&lt;/name&gt;
060 *            &lt;type&gt;long&lt;/name&gt;
061 *          &lt;/field&gt;
062 *          &lt;field&gt;
063 *            &lt;name&gt;usrName&lt;/name&gt;
064 *            &lt;type&gt;java.lang.String&lt;/type&gt;
065 *          &lt;/field&gt;
066 *         ...
067 *        &lt;/fields&gt;
068 *      &lt;/table&gt;
069 *      &lt;table&gt;
070 *        &lt;name&gt;documents&lt;/name&gt;
071 *        &lt;fields&gt;
072 *          &lt;field&gt;
073 *            &lt;name&gt;docid&lt;/name&gt;
074 *            &lt;type&gt;long&lt;/type&gt;
075 *          &lt;/field&gt;
076 *          ...
077 *        &lt;/fields&gt;
078 *      &lt;/table&gt;
079 *      ...
080 *    &lt;/tables&gt;
081 *  &lt;/database&gt;
082 * </pre>
083 *
084 * </p>
085 * <p>
086 * If this document is parsed and stored in a hierarchical configuration object,
087 * for instance the key {@code tables.table(0).name} can be used to find
088 * out the name of the first table. In opposite {@code tables.table.name}
089 * would return a collection with the names of all available tables. Similarly
090 * the key {@code tables.table(1).fields.field.name} returns a collection
091 * with the names of all fields of the second table. If another index is added
092 * after the {@code field} element, a single field can be accessed:
093 * {@code tables.table(1).fields.field(0).name}. The key
094 * {@code tables.table(0)[@type]} would select the type attribute of the
095 * first table.
096 * </p>
097 * <p>
098 * This example works with the default values for delimiters and index markers.
099 * It is also possible to set custom values for these properties so that you can
100 * adapt a {@code DefaultExpressionEngine} to your personal needs.
101 * </p>
102 *
103 * @since 1.3
104 * @author <a
105 * href="http://commons.apache.org/configuration/team-list.html">Commons
106 * Configuration team</a>
107 * @version $Id: DefaultExpressionEngine.java 1301991 2012-03-17 20:18:02Z sebb $
108 */
109public class DefaultExpressionEngine implements ExpressionEngine
110{
111    /** Constant for the default property delimiter. */
112    public static final String DEFAULT_PROPERTY_DELIMITER = ".";
113
114    /** Constant for the default escaped property delimiter. */
115    public static final String DEFAULT_ESCAPED_DELIMITER = DEFAULT_PROPERTY_DELIMITER
116            + DEFAULT_PROPERTY_DELIMITER;
117
118    /** Constant for the default attribute start marker. */
119    public static final String DEFAULT_ATTRIBUTE_START = "[@";
120
121    /** Constant for the default attribute end marker. */
122    public static final String DEFAULT_ATTRIBUTE_END = "]";
123
124    /** Constant for the default index start marker. */
125    public static final String DEFAULT_INDEX_START = "(";
126
127    /** Constant for the default index end marker. */
128    public static final String DEFAULT_INDEX_END = ")";
129
130    /** Stores the property delimiter. */
131    private String propertyDelimiter = DEFAULT_PROPERTY_DELIMITER;
132
133    /** Stores the escaped property delimiter. */
134    private String escapedDelimiter = DEFAULT_ESCAPED_DELIMITER;
135
136    /** Stores the attribute start marker. */
137    private String attributeStart = DEFAULT_ATTRIBUTE_START;
138
139    /** Stores the attribute end marker. */
140    private String attributeEnd = DEFAULT_ATTRIBUTE_END;
141
142    /** Stores the index start marker. */
143    private String indexStart = DEFAULT_INDEX_START;
144
145    /** stores the index end marker. */
146    private String indexEnd = DEFAULT_INDEX_END;
147
148    /**
149     * Sets the attribute end marker.
150     *
151     * @return the attribute end marker
152     */
153    public String getAttributeEnd()
154    {
155        return attributeEnd;
156    }
157
158    /**
159     * Sets the attribute end marker.
160     *
161     * @param attributeEnd the attribute end marker; can be <b>null</b> if no
162     * end marker is needed
163     */
164    public void setAttributeEnd(String attributeEnd)
165    {
166        this.attributeEnd = attributeEnd;
167    }
168
169    /**
170     * Returns the attribute start marker.
171     *
172     * @return the attribute start marker
173     */
174    public String getAttributeStart()
175    {
176        return attributeStart;
177    }
178
179    /**
180     * Sets the attribute start marker. Attribute start and end marker are used
181     * together to detect attributes in a property key.
182     *
183     * @param attributeStart the attribute start marker
184     */
185    public void setAttributeStart(String attributeStart)
186    {
187        this.attributeStart = attributeStart;
188    }
189
190    /**
191     * Returns the escaped property delimiter string.
192     *
193     * @return the escaped property delimiter
194     */
195    public String getEscapedDelimiter()
196    {
197        return escapedDelimiter;
198    }
199
200    /**
201     * Sets the escaped property delimiter string. With this string a delimiter
202     * that belongs to the key of a property can be escaped. If for instance
203     * &quot;.&quot; is used as property delimiter, you can set the escaped
204     * delimiter to &quot;\.&quot; and can then escape the delimiter with a back
205     * slash.
206     *
207     * @param escapedDelimiter the escaped delimiter string
208     */
209    public void setEscapedDelimiter(String escapedDelimiter)
210    {
211        this.escapedDelimiter = escapedDelimiter;
212    }
213
214    /**
215     * Returns the index end marker.
216     *
217     * @return the index end marker
218     */
219    public String getIndexEnd()
220    {
221        return indexEnd;
222    }
223
224    /**
225     * Sets the index end marker.
226     *
227     * @param indexEnd the index end marker
228     */
229    public void setIndexEnd(String indexEnd)
230    {
231        this.indexEnd = indexEnd;
232    }
233
234    /**
235     * Returns the index start marker.
236     *
237     * @return the index start marker
238     */
239    public String getIndexStart()
240    {
241        return indexStart;
242    }
243
244    /**
245     * Sets the index start marker. Index start and end marker are used together
246     * to detect indices in a property key.
247     *
248     * @param indexStart the index start marker
249     */
250    public void setIndexStart(String indexStart)
251    {
252        this.indexStart = indexStart;
253    }
254
255    /**
256     * Returns the property delimiter.
257     *
258     * @return the property delimiter
259     */
260    public String getPropertyDelimiter()
261    {
262        return propertyDelimiter;
263    }
264
265    /**
266     * Sets the property delimiter. This string is used to split the parts of a
267     * property key.
268     *
269     * @param propertyDelimiter the property delimiter
270     */
271    public void setPropertyDelimiter(String propertyDelimiter)
272    {
273        this.propertyDelimiter = propertyDelimiter;
274    }
275
276    /**
277     * Evaluates the given key and returns all matching nodes. This method
278     * supports the syntax as described in the class comment.
279     *
280     * @param root the root node
281     * @param key the key
282     * @return a list with the matching nodes
283     */
284    public List<ConfigurationNode> query(ConfigurationNode root, String key)
285    {
286        List<ConfigurationNode> nodes = new LinkedList<ConfigurationNode>();
287        findNodesForKey(new DefaultConfigurationKey(this, key).iterator(),
288                root, nodes);
289        return nodes;
290    }
291
292    /**
293     * Determines the key of the passed in node. This implementation takes the
294     * given parent key, adds a property delimiter, and then adds the node's
295     * name. (For attribute nodes the attribute delimiters are used instead.)
296     * The name of the root node is a blanc string. Note that no indices will be
297     * returned.
298     *
299     * @param node the node whose key is to be determined
300     * @param parentKey the key of this node's parent
301     * @return the key for the given node
302     */
303    public String nodeKey(ConfigurationNode node, String parentKey)
304    {
305        if (parentKey == null)
306        {
307            // this is the root node
308            return StringUtils.EMPTY;
309        }
310
311        else
312        {
313            DefaultConfigurationKey key = new DefaultConfigurationKey(this,
314                    parentKey);
315            if (node.isAttribute())
316            {
317                key.appendAttribute(node.getName());
318            }
319            else
320            {
321                key.append(node.getName(), true);
322            }
323            return key.toString();
324        }
325    }
326
327    /**
328     * <p>
329     * Prepares Adding the property with the specified key.
330     * </p>
331     * <p>
332     * To be able to deal with the structure supported by hierarchical
333     * configuration implementations the passed in key is of importance,
334     * especially the indices it might contain. The following example should
335     * clarify this: Suppose the actual node structure looks like the
336     * following:
337     * </p>
338     * <p>
339     * <pre>
340     *  tables
341     *     +-- table
342     *             +-- name = user
343     *             +-- fields
344     *                     +-- field
345     *                             +-- name = uid
346     *                     +-- field
347     *                             +-- name = firstName
348     *                     ...
349     *     +-- table
350     *             +-- name = documents
351     *             +-- fields
352     *                    ...
353     * </pre>
354     * </p>
355     * <p>
356     * In this example a database structure is defined, e.g. all fields of the
357     * first table could be accessed using the key
358     * {@code tables.table(0).fields.field.name}. If now properties are
359     * to be added, it must be exactly specified at which position in the
360     * hierarchy the new property is to be inserted. So to add a new field name
361     * to a table it is not enough to say just
362     * </p>
363     * <p>
364     * <pre>
365     * config.addProperty(&quot;tables.table.fields.field.name&quot;, &quot;newField&quot;);
366     * </pre>
367     * </p>
368     * <p>
369     * The statement given above contains some ambiguity. For instance it is not
370     * clear, to which table the new field should be added. If this method finds
371     * such an ambiguity, it is resolved by following the last valid path. Here
372     * this would be the last table. The same is true for the {@code field};
373     * because there are multiple fields and no explicit index is provided, a
374     * new {@code name} property would be added to the last field - which
375     * is probably not what was desired.
376     * </p>
377     * <p>
378     * To make things clear explicit indices should be provided whenever
379     * possible. In the example above the exact table could be specified by
380     * providing an index for the {@code table} element as in
381     * {@code tables.table(1).fields}. By specifying an index it can
382     * also be expressed that at a given position in the configuration tree a
383     * new branch should be added. In the example above we did not want to add
384     * an additional {@code name} element to the last field of the table,
385     * but we want a complete new {@code field} element. This can be
386     * achieved by specifying an invalid index (like -1) after the element where
387     * a new branch should be created. Given this our example would run:
388     * </p>
389     * <p>
390     * <pre>
391     * config.addProperty(&quot;tables.table(1).fields.field(-1).name&quot;, &quot;newField&quot;);
392     * </pre>
393     * </p>
394     * <p>
395     * With this notation it is possible to add new branches everywhere. We
396     * could for instance create a new {@code table} element by
397     * specifying
398     * </p>
399     * <p>
400     * <pre>
401     * config.addProperty(&quot;tables.table(-1).fields.field.name&quot;, &quot;newField2&quot;);
402     * </pre>
403     * </p>
404     * <p>
405     * (Note that because after the {@code table} element a new branch is
406     * created indices in following elements are not relevant; the branch is new
407     * so there cannot be any ambiguities.)
408     * </p>
409     *
410     * @param root the root node of the nodes hierarchy
411     * @param key the key of the new property
412     * @return a data object with information needed for the add operation
413     */
414    public NodeAddData prepareAdd(ConfigurationNode root, String key)
415    {
416        DefaultConfigurationKey.KeyIterator it = new DefaultConfigurationKey(
417                this, key).iterator();
418        if (!it.hasNext())
419        {
420            throw new IllegalArgumentException(
421                    "Key for add operation must be defined!");
422        }
423
424        NodeAddData result = new NodeAddData();
425        result.setParent(findLastPathNode(it, root));
426
427        while (it.hasNext())
428        {
429            if (!it.isPropertyKey())
430            {
431                throw new IllegalArgumentException(
432                        "Invalid key for add operation: " + key
433                                + " (Attribute key in the middle.)");
434            }
435            result.addPathNode(it.currentKey());
436            it.next();
437        }
438
439        result.setNewNodeName(it.currentKey());
440        result.setAttribute(!it.isPropertyKey());
441        return result;
442    }
443
444    /**
445     * Recursive helper method for evaluating a key. This method processes all
446     * facets of a configuration key, traverses the tree of properties and
447     * fetches the the nodes of all matching properties.
448     *
449     * @param keyPart the configuration key iterator
450     * @param node the actual node
451     * @param nodes here the found nodes are stored
452     */
453    protected void findNodesForKey(DefaultConfigurationKey.KeyIterator keyPart,
454            ConfigurationNode node, Collection<ConfigurationNode> nodes)
455    {
456        if (!keyPart.hasNext())
457        {
458            nodes.add(node);
459        }
460
461        else
462        {
463            String key = keyPart.nextKey(false);
464            if (keyPart.isPropertyKey())
465            {
466                processSubNodes(keyPart, node.getChildren(key), nodes);
467            }
468            if (keyPart.isAttribute())
469            {
470                processSubNodes(keyPart, node.getAttributes(key), nodes);
471            }
472        }
473    }
474
475    /**
476     * Finds the last existing node for an add operation. This method traverses
477     * the configuration node tree along the specified key. The last existing
478     * node on this path is returned.
479     *
480     * @param keyIt the key iterator
481     * @param node the actual node
482     * @return the last existing node on the given path
483     */
484    protected ConfigurationNode findLastPathNode(
485            DefaultConfigurationKey.KeyIterator keyIt, ConfigurationNode node)
486    {
487        String keyPart = keyIt.nextKey(false);
488
489        if (keyIt.hasNext())
490        {
491            if (!keyIt.isPropertyKey())
492            {
493                // Attribute keys can only appear as last elements of the path
494                throw new IllegalArgumentException(
495                        "Invalid path for add operation: "
496                                + "Attribute key in the middle!");
497            }
498            int idx = keyIt.hasIndex() ? keyIt.getIndex() : node
499                    .getChildrenCount(keyPart) - 1;
500            if (idx < 0 || idx >= node.getChildrenCount(keyPart))
501            {
502                return node;
503            }
504            else
505            {
506                return findLastPathNode(keyIt, node.getChildren(keyPart).get(idx));
507            }
508        }
509
510        else
511        {
512            return node;
513        }
514    }
515
516    /**
517     * Called by {@code findNodesForKey()} to process the sub nodes of
518     * the current node depending on the type of the current key part (children,
519     * attributes, or both).
520     *
521     * @param keyPart the key part
522     * @param subNodes a list with the sub nodes to process
523     * @param nodes the target collection
524     */
525    private void processSubNodes(DefaultConfigurationKey.KeyIterator keyPart,
526            List<ConfigurationNode> subNodes, Collection<ConfigurationNode> nodes)
527    {
528        if (keyPart.hasIndex())
529        {
530            if (keyPart.getIndex() >= 0 && keyPart.getIndex() < subNodes.size())
531            {
532                findNodesForKey((DefaultConfigurationKey.KeyIterator) keyPart
533                        .clone(), subNodes.get(keyPart.getIndex()), nodes);
534            }
535        }
536        else
537        {
538            for (ConfigurationNode node : subNodes)
539            {
540                findNodesForKey((DefaultConfigurationKey.KeyIterator) keyPart
541                        .clone(), node, nodes);
542            }
543        }
544    }
545}