/*
 * Licensed to the Apache Software Foundation (ASF) under one or more
 * contributor license agreements.  See the NOTICE file distributed with
 * this work for additional information regarding copyright ownership.
 * The ASF licenses this file to You under the Apache License, Version 2.0
 * (the "License"); you may not use this file except in compliance with
 * the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.commons.configuration.tree;

import java.util.Collection;
import java.util.LinkedList;
import java.util.List;

import org.apache.commons.lang.StringUtils;

 A default implementation of the ExpressionEngine interface providing the "native&quote; expression language for hierarchical configurations. 

This class implements a rather simple expression language for navigating
through a hierarchy of configuration nodes. It supports the following
operations:



Navigating from a node to one of its children using the child node
delimiter, which is by the default a dot (".").
Navigating from a node to one of its attributes using the attribute node
delimiter, which by default follows the XPATH like syntax
[@<attributeName>].
If there are multiple child or attribute nodes with the same name, a
specific node can be selected using a numerical index. By default indices are
written in parenthesis.



As an example consider the following XML document:

 <database>
   <tables>
     <table type="system">
       <name>users</name>
       <fields>
         <field>
           <name>lid</name>
           <type>long</name>
         </field>
         <field>
           <name>usrName</name>
           <type>java.lang.String</type>
         </field>
        ...
       </fields>
     </table>
     <table>
       <name>documents</name>
       <fields>
         <field>
           <name>docid</name>
           <type>long</type>
         </field>
         ...
       </fields>
     </table>
     ...
   </tables>
 </database>


 If this document is parsed and stored in a hierarchical configuration object, for instance the key tables.table(0).name can be used to find out the name of the first table. In opposite tables.table.name would return a collection with the names of all available tables. Similarly the key tables.table(1).fields.field.name returns a collection with the names of all fields of the second table. If another index is added after the field element, a single field can be accessed: tables.table(1).fields.field(0).name. The key tables.table(0)[@type] would select the type attribute of the first table. 
 This example works with the default values for delimiters and index markers. It is also possible to set custom values for these properties so that you can adapt a DefaultExpressionEngine to your personal needs. 
Author:
Commons
Configuration team
Since:
1.3
Version:
$Id: DefaultExpressionEngine.java 1301991 2012-03-17 20:18:02Z sebb $/**
 * <p>
 * A default implementation of the {@code ExpressionEngine} interface
 * providing the &quot;native&quote; expression language for hierarchical
 * configurations.
 * </p>
 * <p>
 * This class implements a rather simple expression language for navigating
 * through a hierarchy of configuration nodes. It supports the following
 * operations:
 * </p>
 * <p>
 * <ul>
 * <li>Navigating from a node to one of its children using the child node
 * delimiter, which is by the default a dot (&quot;.&quot;).</li>
 * <li>Navigating from a node to one of its attributes using the attribute node
 * delimiter, which by default follows the XPATH like syntax
 * <code>[@&lt;attributeName&gt;]</code>.</li>
 * <li>If there are multiple child or attribute nodes with the same name, a
 * specific node can be selected using a numerical index. By default indices are
 * written in parenthesis.</li>
 * </ul>
 * </p>
 * <p>
 * As an example consider the following XML document:
 * </p>
 *
 * <pre>
 *  &lt;database&gt;
 *    &lt;tables&gt;
 *      &lt;table type=&quot;system&quot;&gt;
 *        &lt;name&gt;users&lt;/name&gt;
 *        &lt;fields&gt;
 *          &lt;field&gt;
 *            &lt;name&gt;lid&lt;/name&gt;
 *            &lt;type&gt;long&lt;/name&gt;
 *          &lt;/field&gt;
 *          &lt;field&gt;
 *            &lt;name&gt;usrName&lt;/name&gt;
 *            &lt;type&gt;java.lang.String&lt;/type&gt;
 *          &lt;/field&gt;
 *         ...
 *        &lt;/fields&gt;
 *      &lt;/table&gt;
 *      &lt;table&gt;
 *        &lt;name&gt;documents&lt;/name&gt;
 *        &lt;fields&gt;
 *          &lt;field&gt;
 *            &lt;name&gt;docid&lt;/name&gt;
 *            &lt;type&gt;long&lt;/type&gt;
 *          &lt;/field&gt;
 *          ...
 *        &lt;/fields&gt;
 *      &lt;/table&gt;
 *      ...
 *    &lt;/tables&gt;
 *  &lt;/database&gt;
 * </pre>
 *
 * </p>
 * <p>
 * If this document is parsed and stored in a hierarchical configuration object,
 * for instance the key {@code tables.table(0).name} can be used to find
 * out the name of the first table. In opposite {@code tables.table.name}
 * would return a collection with the names of all available tables. Similarly
 * the key {@code tables.table(1).fields.field.name} returns a collection
 * with the names of all fields of the second table. If another index is added
 * after the {@code field} element, a single field can be accessed:
 * {@code tables.table(1).fields.field(0).name}. The key
 * {@code tables.table(0)[@type]} would select the type attribute of the
 * first table.
 * </p>
 * <p>
 * This example works with the default values for delimiters and index markers.
 * It is also possible to set custom values for these properties so that you can
 * adapt a {@code DefaultExpressionEngine} to your personal needs.
 * </p>
 *
 * @since 1.3
 * @author <a
 * href="http://commons.apache.org/configuration/team-list.html">Commons
 * Configuration team</a>
 * @version $Id: DefaultExpressionEngine.java 1301991 2012-03-17 20:18:02Z sebb $
 */
public class DefaultExpressionEngine implements ExpressionEngine
{
    
Constant for the default property delimiter. /** Constant for the default property delimiter. */
    public static final String DEFAULT_PROPERTY_DELIMITER = ".";

    
Constant for the default escaped property delimiter. /** Constant for the default escaped property delimiter. */
    public static final String DEFAULT_ESCAPED_DELIMITER = DEFAULT_PROPERTY_DELIMITER
            + DEFAULT_PROPERTY_DELIMITER;

    
Constant for the default attribute start marker. /** Constant for the default attribute start marker. */
    public static final String DEFAULT_ATTRIBUTE_START = "[@";

    
Constant for the default attribute end marker. /** Constant for the default attribute end marker. */
    public static final String DEFAULT_ATTRIBUTE_END = "]";

    
Constant for the default index start marker. /** Constant for the default index start marker. */
    public static final String DEFAULT_INDEX_START = "(";

    
Constant for the default index end marker. /** Constant for the default index end marker. */
    public static final String DEFAULT_INDEX_END = ")";

    
Stores the property delimiter. /** Stores the property delimiter. */
    private String propertyDelimiter = DEFAULT_PROPERTY_DELIMITER;

    
Stores the escaped property delimiter. /** Stores the escaped property delimiter. */
    private String escapedDelimiter = DEFAULT_ESCAPED_DELIMITER;

    
Stores the attribute start marker. /** Stores the attribute start marker. */
    private String attributeStart = DEFAULT_ATTRIBUTE_START;

    
Stores the attribute end marker. /** Stores the attribute end marker. */
    private String attributeEnd = DEFAULT_ATTRIBUTE_END;

    
Stores the index start marker. /** Stores the index start marker. */
    private String indexStart = DEFAULT_INDEX_START;

    
stores the index end marker. /** stores the index end marker. */
    private String indexEnd = DEFAULT_INDEX_END;

    
Sets the attribute end marker.
Returns:
the attribute end marker/**
     * Sets the attribute end marker.
     *
     * @return the attribute end marker
     */
    public String getAttributeEnd()
    {
        return attributeEnd;
    }

    
Sets the attribute end marker.
Params:
attributeEnd – the attribute end marker; can be null if no
end marker is needed/**
     * Sets the attribute end marker.
     *
     * @param attributeEnd the attribute end marker; can be <b>null</b> if no
     * end marker is needed
     */
    public void setAttributeEnd(String attributeEnd)
    {
        this.attributeEnd = attributeEnd;
    }

    
Returns the attribute start marker.
Returns:
the attribute start marker/**
     * Returns the attribute start marker.
     *
     * @return the attribute start marker
     */
    public String getAttributeStart()
    {
        return attributeStart;
    }

    
Sets the attribute start marker. Attribute start and end marker are used
together to detect attributes in a property key.
Params:
attributeStart – the attribute start marker/**
     * Sets the attribute start marker. Attribute start and end marker are used
     * together to detect attributes in a property key.
     *
     * @param attributeStart the attribute start marker
     */
    public void setAttributeStart(String attributeStart)
    {
        this.attributeStart = attributeStart;
    }

    
Returns the escaped property delimiter string.
Returns:
the escaped property delimiter/**
     * Returns the escaped property delimiter string.
     *
     * @return the escaped property delimiter
     */
    public String getEscapedDelimiter()
    {
        return escapedDelimiter;
    }

    
Sets the escaped property delimiter string. With this string a delimiter
that belongs to the key of a property can be escaped. If for instance
"." is used as property delimiter, you can set the escaped
delimiter to "\." and can then escape the delimiter with a back
slash.
Params:
escapedDelimiter – the escaped delimiter string/**
     * Sets the escaped property delimiter string. With this string a delimiter
     * that belongs to the key of a property can be escaped. If for instance
     * &quot;.&quot; is used as property delimiter, you can set the escaped
     * delimiter to &quot;\.&quot; and can then escape the delimiter with a back
     * slash.
     *
     * @param escapedDelimiter the escaped delimiter string
     */
    public void setEscapedDelimiter(String escapedDelimiter)
    {
        this.escapedDelimiter = escapedDelimiter;
    }

    
Returns the index end marker.
Returns:
the index end marker/**
     * Returns the index end marker.
     *
     * @return the index end marker
     */
    public String getIndexEnd()
    {
        return indexEnd;
    }

    
Sets the index end marker.
Params:
indexEnd – the index end marker/**
     * Sets the index end marker.
     *
     * @param indexEnd the index end marker
     */
    public void setIndexEnd(String indexEnd)
    {
        this.indexEnd = indexEnd;
    }

    
Returns the index start marker.
Returns:
the index start marker/**
     * Returns the index start marker.
     *
     * @return the index start marker
     */
    public String getIndexStart()
    {
        return indexStart;
    }

    
Sets the index start marker. Index start and end marker are used together
to detect indices in a property key.
Params:
indexStart – the index start marker/**
     * Sets the index start marker. Index start and end marker are used together
     * to detect indices in a property key.
     *
     * @param indexStart the index start marker
     */
    public void setIndexStart(String indexStart)
    {
        this.indexStart = indexStart;
    }

    
Returns the property delimiter.
Returns:
the property delimiter/**
     * Returns the property delimiter.
     *
     * @return the property delimiter
     */
    public String getPropertyDelimiter()
    {
        return propertyDelimiter;
    }

    
Sets the property delimiter. This string is used to split the parts of a
property key.
Params:
propertyDelimiter – the property delimiter/**
     * Sets the property delimiter. This string is used to split the parts of a
     * property key.
     *
     * @param propertyDelimiter the property delimiter
     */
    public void setPropertyDelimiter(String propertyDelimiter)
    {
        this.propertyDelimiter = propertyDelimiter;
    }

    
Evaluates the given key and returns all matching nodes. This method
supports the syntax as described in the class comment.
Params:
root – the root node
key – the key
Returns:
a list with the matching nodes/**
     * Evaluates the given key and returns all matching nodes. This method
     * supports the syntax as described in the class comment.
     *
     * @param root the root node
     * @param key the key
     * @return a list with the matching nodes
     */
    public List<ConfigurationNode> query(ConfigurationNode root, String key)
    {
        List<ConfigurationNode> nodes = new LinkedList<ConfigurationNode>();
        findNodesForKey(new DefaultConfigurationKey(this, key).iterator(),
                root, nodes);
        return nodes;
    }

    
Determines the key of the passed in node. This implementation takes the
given parent key, adds a property delimiter, and then adds the node's
name. (For attribute nodes the attribute delimiters are used instead.)
The name of the root node is a blanc string. Note that no indices will be
returned.
Params:
node – the node whose key is to be determined
parentKey – the key of this node's parent
Returns:
the key for the given node/**
     * Determines the key of the passed in node. This implementation takes the
     * given parent key, adds a property delimiter, and then adds the node's
     * name. (For attribute nodes the attribute delimiters are used instead.)
     * The name of the root node is a blanc string. Note that no indices will be
     * returned.
     *
     * @param node the node whose key is to be determined
     * @param parentKey the key of this node's parent
     * @return the key for the given node
     */
    public String nodeKey(ConfigurationNode node, String parentKey)
    {
        if (parentKey == null)
        {
            // this is the root node
            return StringUtils.EMPTY;
        }

        else
        {
            DefaultConfigurationKey key = new DefaultConfigurationKey(this,
                    parentKey);
            if (node.isAttribute())
            {
                key.appendAttribute(node.getName());
            }
            else
            {
                key.append(node.getName(), true);
            }
            return key.toString();
        }
    }

    

Prepares Adding the property with the specified key.


To be able to deal with the structure supported by hierarchical
configuration implementations the passed in key is of importance,
especially the indices it might contain. The following example should
clarify this: Suppose the actual node structure looks like the
following:


 tables
    +-- table
            +-- name = user
            +-- fields
                    +-- field
                            +-- name = uid
                    +-- field
                            +-- name = firstName
                    ...
    +-- table
            +-- name = documents
            +-- fields
                   ...


 In this example a database structure is defined, e.g. all fields of the first table could be accessed using the key tables.table(0).fields.field.name. If now properties are to be added, it must be exactly specified at which 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 to say just 

config.addProperty("tables.table.fields.field.name", "newField");


 The statement given above contains some ambiguity. For instance it is not clear, to which table the new field should be added. If this method finds such an ambiguity, it is resolved by following the last valid path. Here this would be the last table. The same is true for the field; because there are multiple fields and no explicit index is provided, a new name property would be added to the last field - which is probably not what was desired. 
 To make things clear explicit indices should be provided whenever possible. In the example above the exact table could be specified by providing an index for the table element as in tables.table(1).fields. By specifying an index it can also be expressed that at a given position in the configuration tree a new branch should be added. In the example above we did not want to add an additional name element to the last field of the table, but we want a complete new field element. This can be achieved by specifying an invalid index (like -1) after the element where a new branch should be created. Given this our example would run: 

config.addProperty("tables.table(1).fields.field(-1).name", "newField");


 With this notation it is possible to add new branches everywhere. We could for instance create a new table element by specifying 

config.addProperty("tables.table(-1).fields.field.name", "newField2");


 (Note that because after the table element a new branch is created indices in following elements are not relevant; the branch is new so there cannot be any ambiguities.) 
Params:
root – the root node of the nodes hierarchy
key – the key of the new property
Returns:
a data object with information needed for the add operation/**
     * <p>
     * Prepares Adding the property with the specified key.
     * </p>
     * <p>
     * To be able to deal with the structure supported by hierarchical
     * configuration implementations the passed in key is of importance,
     * especially the indices it might contain. The following example should
     * clarify this: Suppose the actual node structure looks like the
     * following:
     * </p>
     * <p>
     * <pre>
     *  tables
     *     +-- table
     *             +-- name = user
     *             +-- fields
     *                     +-- field
     *                             +-- name = uid
     *                     +-- field
     *                             +-- name = firstName
     *                     ...
     *     +-- table
     *             +-- name = documents
     *             +-- fields
     *                    ...
     * </pre>
     * </p>
     * <p>
     * In this example a database structure is defined, e.g. all fields of the
     * first table could be accessed using the key
     * {@code tables.table(0).fields.field.name}. If now properties are
     * to be added, it must be exactly specified at which 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 to say just
     * </p>
     * <p>
     * <pre>
     * config.addProperty(&quot;tables.table.fields.field.name&quot;, &quot;newField&quot;);
     * </pre>
     * </p>
     * <p>
     * The statement given above contains some ambiguity. For instance it is not
     * clear, to which table the new field should be added. If this method finds
     * such an ambiguity, it is resolved by following the last valid path. Here
     * this would be the last table. The same is true for the {@code field};
     * because there are multiple fields and no explicit index is provided, a
     * new {@code name} property would be added to the last field - which
     * is probably not what was desired.
     * </p>
     * <p>
     * To make things clear explicit indices should be provided whenever
     * possible. In the example above the exact table could be specified by
     * providing an index for the {@code table} element as in
     * {@code tables.table(1).fields}. By specifying an index it can
     * also be expressed that at a given position in the configuration tree a
     * new branch should be added. In the example above we did not want to add
     * an additional {@code name} element to the last field of the table,
     * but we want a complete new {@code field} element. This can be
     * achieved by specifying an invalid index (like -1) after the element where
     * a new branch should be created. Given this our example would run:
     * </p>
     * <p>
     * <pre>
     * config.addProperty(&quot;tables.table(1).fields.field(-1).name&quot;, &quot;newField&quot;);
     * </pre>
     * </p>
     * <p>
     * With this notation it is possible to add new branches everywhere. We
     * could for instance create a new {@code table} element by
     * specifying
     * </p>
     * <p>
     * <pre>
     * config.addProperty(&quot;tables.table(-1).fields.field.name&quot;, &quot;newField2&quot;);
     * </pre>
     * </p>
     * <p>
     * (Note that because after the {@code table} element a new branch is
     * created indices in following elements are not relevant; the branch is new
     * so there cannot be any ambiguities.)
     * </p>
     *
     * @param root the root node of the nodes hierarchy
     * @param key the key of the new property
     * @return a data object with information needed for the add operation
     */
    public NodeAddData prepareAdd(ConfigurationNode root, String key)
    {
        DefaultConfigurationKey.KeyIterator it = new DefaultConfigurationKey(
                this, key).iterator();
        if (!it.hasNext())
        {
            throw new IllegalArgumentException(
                    "Key for add operation must be defined!");
        }

        NodeAddData result = new NodeAddData();
        result.setParent(findLastPathNode(it, root));

        while (it.hasNext())
        {
            if (!it.isPropertyKey())
            {
                throw new IllegalArgumentException(
                        "Invalid key for add operation: " + key
                                + " (Attribute key in the middle.)");
            }
            result.addPathNode(it.currentKey());
            it.next();
        }

        result.setNewNodeName(it.currentKey());
        result.setAttribute(!it.isPropertyKey());
        return result;
    }

    
Recursive helper method for evaluating a key. This method processes all
facets of a configuration key, traverses the tree of properties and
fetches the the nodes of all matching properties.
Params:
keyPart – the configuration key iterator
node – the actual node
nodes – here the found nodes are stored/**
     * Recursive helper method for evaluating a key. This method processes all
     * facets of a configuration key, traverses the tree of properties and
     * fetches the the nodes of all matching properties.
     *
     * @param keyPart the configuration key iterator
     * @param node the actual node
     * @param nodes here the found nodes are stored
     */
    protected void findNodesForKey(DefaultConfigurationKey.KeyIterator keyPart,
            ConfigurationNode node, Collection<ConfigurationNode> nodes)
    {
        if (!keyPart.hasNext())
        {
            nodes.add(node);
        }

        else
        {
            String key = keyPart.nextKey(false);
            if (keyPart.isPropertyKey())
            {
                processSubNodes(keyPart, node.getChildren(key), nodes);
            }
            if (keyPart.isAttribute())
            {
                processSubNodes(keyPart, node.getAttributes(key), nodes);
            }
        }
    }

    
Finds the last existing node for an add operation. This method traverses
the configuration node tree along the specified key. The last existing
node on this path is returned.
Params:
keyIt – the key iterator
node – the actual node
Returns:
the last existing node on the given path/**
     * Finds the last existing node for an add operation. This method traverses
     * the configuration node tree along the specified key. The last existing
     * node on this path is returned.
     *
     * @param keyIt the key iterator
     * @param node the actual node
     * @return the last existing node on the given path
     */
    protected ConfigurationNode findLastPathNode(
            DefaultConfigurationKey.KeyIterator keyIt, ConfigurationNode node)
    {
        String keyPart = keyIt.nextKey(false);

        if (keyIt.hasNext())
        {
            if (!keyIt.isPropertyKey())
            {
                // Attribute keys can only appear as last elements of the path
                throw new IllegalArgumentException(
                        "Invalid path for add operation: "
                                + "Attribute key in the middle!");
            }
            int idx = keyIt.hasIndex() ? keyIt.getIndex() : node
                    .getChildrenCount(keyPart) - 1;
            if (idx < 0 || idx >= node.getChildrenCount(keyPart))
            {
                return node;
            }
            else
            {
                return findLastPathNode(keyIt, node.getChildren(keyPart).get(idx));
            }
        }

        else
        {
            return node;
        }
    }

    
Called by findNodesForKey() to process the sub nodes of the current node depending on the type of the current key part (children, attributes, or both). 
Params:
keyPart – the key part
subNodes – a list with the sub nodes to process
nodes – the target collection/**
     * Called by {@code findNodesForKey()} to process the sub nodes of
     * the current node depending on the type of the current key part (children,
     * attributes, or both).
     *
     * @param keyPart the key part
     * @param subNodes a list with the sub nodes to process
     * @param nodes the target collection
     */
    private void processSubNodes(DefaultConfigurationKey.KeyIterator keyPart,
            List<ConfigurationNode> subNodes, Collection<ConfigurationNode> nodes)
    {
        if (keyPart.hasIndex())
        {
            if (keyPart.getIndex() >= 0 && keyPart.getIndex() < subNodes.size())
            {
                findNodesForKey((DefaultConfigurationKey.KeyIterator) keyPart
                        .clone(), subNodes.get(keyPart.getIndex()), nodes);
            }
        }
        else
        {
            for (ConfigurationNode node : subNodes)
            {
                findNodesForKey((DefaultConfigurationKey.KeyIterator) keyPart
                        .clone(), node, nodes);
            }
        }
    }
}