[asterisk/asterisk.git] / main / pbx.c

/*
 * Asterisk -- An open source telephony toolkit.
 *
 * Copyright (C) 1999 - 2008, Digium, Inc.
 *
 * Mark Spencer <markster@digium.com>
 *
 * See http://www.asterisk.org for more information about
 * the Asterisk project. Please do not directly contact
 * any of the maintainers of this project for assistance;
 * the project provides a web site, mailing lists and IRC
 * channels for your use.
 *
 * This program is free software, distributed under the terms of
 * the GNU General Public License Version 2. See the LICENSE file
 * at the top of the source tree.
 */

/*! \file
 *
 * \brief Core PBX routines.
 *
 * \author Mark Spencer <markster@digium.com>
 */

/*** MODULEINFO
        <support_level>core</support_level>
 ***/

#include "asterisk.h"

ASTERISK_FILE_VERSION(__FILE__, "$Revision$")

#include "asterisk/_private.h"
#include "asterisk/paths.h"     /* use ast_config_AST_SYSTEM_NAME */
#include <ctype.h>
#include <time.h>
#include <sys/time.h>
#if defined(HAVE_SYSINFO)
#include <sys/sysinfo.h>
#endif
#if defined(SOLARIS)
#include <sys/loadavg.h>
#endif

#include "asterisk/lock.h"
#include "asterisk/cli.h"
#include "asterisk/pbx.h"
#include "asterisk/channel.h"
#include "asterisk/file.h"
#include "asterisk/callerid.h"
#include "asterisk/cdr.h"
#include "asterisk/cel.h"
#include "asterisk/config.h"
#include "asterisk/term.h"
#include "asterisk/time.h"
#include "asterisk/manager.h"
#include "asterisk/ast_expr.h"
#include "asterisk/linkedlists.h"
#define SAY_STUBS       /* generate declarations and stubs for say methods */
#include "asterisk/say.h"
#include "asterisk/utils.h"
#include "asterisk/causes.h"
#include "asterisk/musiconhold.h"
#include "asterisk/app.h"
#include "asterisk/devicestate.h"
#include "asterisk/presencestate.h"
#include "asterisk/event.h"
#include "asterisk/hashtab.h"
#include "asterisk/module.h"
#include "asterisk/indications.h"
#include "asterisk/taskprocessor.h"
#include "asterisk/xmldoc.h"
#include "asterisk/astobj2.h"

/*!
 * \note I M P O R T A N T :
 *
 *              The speed of extension handling will likely be among the most important
 * aspects of this PBX.  The switching scheme as it exists right now isn't
 * terribly bad (it's O(N+M), where N is the # of extensions and M is the avg #
 * of priorities, but a constant search time here would be great ;-)
 *
 * A new algorithm to do searching based on a 'compiled' pattern tree is introduced
 * here, and shows a fairly flat (constant) search time, even for over
 * 10000 patterns.
 *
 * Also, using a hash table for context/priority name lookup can help prevent
 * the find_extension routines from absorbing exponential cpu cycles as the number
 * of contexts/priorities grow. I've previously tested find_extension with red-black trees,
 * which have O(log2(n)) speed. Right now, I'm using hash tables, which do
 * searches (ideally) in O(1) time. While these techniques do not yield much
 * speed in small dialplans, they are worth the trouble in large dialplans.
 *
 */

/*** DOCUMENTATION
        <application name="Answer" language="en_US">
                <synopsis>
                        Answer a channel if ringing.
                </synopsis>
                <syntax>
                        <parameter name="delay">
                                <para>Asterisk will wait this number of milliseconds before returning to
                                the dialplan after answering the call.</para>
                        </parameter>
                        <parameter name="nocdr">
                                <para>Asterisk will send an answer signal to the calling phone, but will not
                                set the disposition or answer time in the CDR for this call.</para>
                        </parameter>
                </syntax>
                <description>
                        <para>If the call has not been answered, this application will
                        answer it. Otherwise, it has no effect on the call.</para>
                </description>
                <see-also>
                        <ref type="application">Hangup</ref>
                </see-also>
        </application>
        <application name="BackGround" language="en_US">
                <synopsis>
                        Play an audio file while waiting for digits of an extension to go to.
                </synopsis>
                <syntax>
                        <parameter name="filenames" required="true" argsep="&amp;">
                                <argument name="filename1" required="true" />
                                <argument name="filename2" multiple="true" />
                        </parameter>
                        <parameter name="options">
                                <optionlist>
                                        <option name="s">
                                                <para>Causes the playback of the message to be skipped
                                                if the channel is not in the <literal>up</literal> state (i.e. it
                                                hasn't been answered yet). If this happens, the
                                                application will return immediately.</para>
                                        </option>
                                        <option name="n">
                                                <para>Don't answer the channel before playing the files.</para>
                                        </option>
                                        <option name="m">
                                                <para>Only break if a digit hit matches a one digit
                                                extension in the destination context.</para>
                                        </option>
                                </optionlist>
                        </parameter>
                        <parameter name="langoverride">
                                <para>Explicitly specifies which language to attempt to use for the requested sound files.</para>
                        </parameter>
                        <parameter name="context">
                                <para>This is the dialplan context that this application will use when exiting
                                to a dialed extension.</para>
                        </parameter>
                </syntax>
                <description>
                        <para>This application will play the given list of files <emphasis>(do not put extension)</emphasis>
                        while waiting for an extension to be dialed by the calling channel. To continue waiting
                        for digits after this application has finished playing files, the <literal>WaitExten</literal>
                        application should be used.</para>
                        <para>If one of the requested sound files does not exist, call processing will be terminated.</para>
                        <para>This application sets the following channel variable upon completion:</para>
                        <variablelist>
                                <variable name="BACKGROUNDSTATUS">
                                        <para>The status of the background attempt as a text string.</para>
                                        <value name="SUCCESS" />
                                        <value name="FAILED" />
                                </variable>
                        </variablelist>
                </description>
                <see-also>
                        <ref type="application">ControlPlayback</ref>
                        <ref type="application">WaitExten</ref>
                        <ref type="application">BackgroundDetect</ref>
                        <ref type="function">TIMEOUT</ref>
                </see-also>
        </application>
        <application name="Busy" language="en_US">
                <synopsis>
                        Indicate the Busy condition.
                </synopsis>
                <syntax>
                        <parameter name="timeout">
                                <para>If specified, the calling channel will be hung up after the specified number of seconds.
                                Otherwise, this application will wait until the calling channel hangs up.</para>
                        </parameter>
                </syntax>
                <description>
                        <para>This application will indicate the busy condition to the calling channel.</para>
                </description>
                <see-also>
                        <ref type="application">Congestion</ref>
                        <ref type="application">Progress</ref>
                        <ref type="application">Playtones</ref>
                        <ref type="application">Hangup</ref>
                </see-also>
        </application>
        <application name="Congestion" language="en_US">
                <synopsis>
                        Indicate the Congestion condition.
                </synopsis>
                <syntax>
                        <parameter name="timeout">
                                <para>If specified, the calling channel will be hung up after the specified number of seconds.
                                Otherwise, this application will wait until the calling channel hangs up.</para>
                        </parameter>
                </syntax>
                <description>
                        <para>This application will indicate the congestion condition to the calling channel.</para>
                </description>
                <see-also>
                        <ref type="application">Busy</ref>
                        <ref type="application">Progress</ref>
                        <ref type="application">Playtones</ref>
                        <ref type="application">Hangup</ref>
                </see-also>
        </application>
        <application name="ExecIfTime" language="en_US">
                <synopsis>
                        Conditional application execution based on the current time.
                </synopsis>
                <syntax argsep="?">
                        <parameter name="day_condition" required="true">
                                <argument name="times" required="true" />
                                <argument name="weekdays" required="true" />
                                <argument name="mdays" required="true" />
                                <argument name="months" required="true" />
                                <argument name="timezone" required="false" />
                        </parameter>
                        <parameter name="appname" required="true" hasparams="optional">
                                <argument name="appargs" required="true" />
                        </parameter>
                </syntax>
                <description>
                        <para>This application will execute the specified dialplan application, with optional
                        arguments, if the current time matches the given time specification.</para>
                </description>
                <see-also>
                        <ref type="application">Exec</ref>
                        <ref type="application">ExecIf</ref>
                        <ref type="application">TryExec</ref>
                        <ref type="application">GotoIfTime</ref>
                </see-also>
        </application>
        <application name="Goto" language="en_US">
                <synopsis>
                        Jump to a particular priority, extension, or context.
                </synopsis>
                <syntax>
                        <parameter name="context" />
                        <parameter name="extensions" />
                        <parameter name="priority" required="true" />
                </syntax>
                <description>
                        <para>This application will set the current context, extension, and priority in the channel structure.
                        After it completes, the pbx engine will continue dialplan execution at the specified location.
                        If no specific <replaceable>extension</replaceable>, or <replaceable>extension</replaceable> and
                        <replaceable>context</replaceable>, are specified, then this application will
                        just set the specified <replaceable>priority</replaceable> of the current extension.</para>
                        <para>At least a <replaceable>priority</replaceable> is required as an argument, or the goto will
                        return a <literal>-1</literal>, and the channel and call will be terminated.</para>
                        <para>If the location that is put into the channel information is bogus, and asterisk cannot
                        find that location in the dialplan, then the execution engine will try to find and execute the code in
                        the <literal>i</literal> (invalid) extension in the current context. If that does not exist, it will try to execute the
                        <literal>h</literal> extension. If neither the <literal>h</literal> nor <literal>i</literal> extensions
                        have been defined, the channel is hung up, and the execution of instructions on the channel is terminated.
                        What this means is that, for example, you specify a context that does not exist, then
                        it will not be possible to find the <literal>h</literal> or <literal>i</literal> extensions,
                        and the call will terminate!</para>
                </description>
                <see-also>
                        <ref type="application">GotoIf</ref>
                        <ref type="application">GotoIfTime</ref>
                        <ref type="application">Gosub</ref>
                        <ref type="application">Macro</ref>
                </see-also>
        </application>
        <application name="GotoIf" language="en_US">
                <synopsis>
                        Conditional goto.
                </synopsis>
                <syntax argsep="?">
                        <parameter name="condition" required="true" />
                        <parameter name="destination" required="true" argsep=":">
                                <argument name="labeliftrue">
                                        <para>Continue at <replaceable>labeliftrue</replaceable> if the condition is true.
                                        Takes the form similar to Goto() of [[context,]extension,]priority.</para>
                                </argument>
                                <argument name="labeliffalse">
                                        <para>Continue at <replaceable>labeliffalse</replaceable> if the condition is false.
                                        Takes the form similar to Goto() of [[context,]extension,]priority.</para>
                                </argument>
                        </parameter>
                </syntax>
                <description>
                        <para>This application will set the current context, extension, and priority in the channel structure
                        based on the evaluation of the given condition. After this application completes, the
                        pbx engine will continue dialplan execution at the specified location in the dialplan.
                        The labels are specified with the same syntax as used within the Goto application.
                        If the label chosen by the condition is omitted, no jump is performed, and the execution passes to the
                        next instruction. If the target location is bogus, and does not exist, the execution engine will try
                        to find and execute the code in the <literal>i</literal> (invalid) extension in the current context.
                        If that does not exist, it will try to execute the <literal>h</literal> extension.
                        If neither the <literal>h</literal> nor <literal>i</literal> extensions have been defined,
                        the channel is hung up, and the execution of instructions on the channel is terminated.
                        Remember that this command can set the current context, and if the context specified
                        does not exist, then it will not be able to find any 'h' or 'i' extensions there, and
                        the channel and call will both be terminated!.</para>
                </description>
                <see-also>
                        <ref type="application">Goto</ref>
                        <ref type="application">GotoIfTime</ref>
                        <ref type="application">GosubIf</ref>
                        <ref type="application">MacroIf</ref>
                </see-also>
        </application>
        <application name="GotoIfTime" language="en_US">
                <synopsis>
                        Conditional Goto based on the current time.
                </synopsis>
                <syntax argsep="?">
                        <parameter name="condition" required="true">
                                <argument name="times" required="true" />
                                <argument name="weekdays" required="true" />
                                <argument name="mdays" required="true" />
                                <argument name="months" required="true" />
                                <argument name="timezone" required="false" />
                        </parameter>
                        <parameter name="destination" required="true" argsep=":">
                                <argument name="labeliftrue">
                                        <para>Continue at <replaceable>labeliftrue</replaceable> if the condition is true.
                                        Takes the form similar to Goto() of [[context,]extension,]priority.</para>
                                </argument>
                                <argument name="labeliffalse">
                                        <para>Continue at <replaceable>labeliffalse</replaceable> if the condition is false.
                                        Takes the form similar to Goto() of [[context,]extension,]priority.</para>
                                </argument>
                        </parameter>
                </syntax>
                <description>
                        <para>This application will set the context, extension, and priority in the channel structure
                        based on the evaluation of the given time specification. After this application completes,
                        the pbx engine will continue dialplan execution at the specified location in the dialplan.
                        If the current time is within the given time specification, the channel will continue at
                        <replaceable>labeliftrue</replaceable>. Otherwise the channel will continue at <replaceable>labeliffalse</replaceable>.
                        If the label chosen by the condition is omitted, no jump is performed, and execution passes to the next
                        instruction. If the target jump location is bogus, the same actions would be taken as for <literal>Goto</literal>.
                        Further information on the time specification can be found in examples
                        illustrating how to do time-based context includes in the dialplan.</para>
                </description>
                <see-also>
                        <ref type="application">GotoIf</ref>
                        <ref type="application">Goto</ref>
                        <ref type="function">IFTIME</ref>
                        <ref type="function">TESTTIME</ref>
                </see-also>
        </application>
        <application name="ImportVar" language="en_US">
                <synopsis>
                        Import a variable from a channel into a new variable.
                </synopsis>
                <syntax argsep="=">
                        <parameter name="newvar" required="true" />
                        <parameter name="vardata" required="true">
                                <argument name="channelname" required="true" />
                                <argument name="variable" required="true" />
                        </parameter>
                </syntax>
                <description>
                        <para>This application imports a <replaceable>variable</replaceable> from the specified
                        <replaceable>channel</replaceable> (as opposed to the current one) and stores it as a variable
                        (<replaceable>newvar</replaceable>) in the current channel (the channel that is calling this
                        application). Variables created by this application have the same inheritance properties as those
                        created with the <literal>Set</literal> application.</para>
                </description>
                <see-also>
                        <ref type="application">Set</ref>
                </see-also>
        </application>
        <application name="Hangup" language="en_US">
                <synopsis>
                        Hang up the calling channel.
                </synopsis>
                <syntax>
                        <parameter name="causecode">
                                <para>If a <replaceable>causecode</replaceable> is given the channel's
                                hangup cause will be set to the given value.</para>
                        </parameter>
                </syntax>
                <description>
                        <para>This application will hang up the calling channel.</para>
                </description>
                <see-also>
                        <ref type="application">Answer</ref>
                        <ref type="application">Busy</ref>
                        <ref type="application">Congestion</ref>
                </see-also>
        </application>
        <application name="Incomplete" language="en_US">
                <synopsis>
                        Returns AST_PBX_INCOMPLETE value.
                </synopsis>
                <syntax>
                        <parameter name="n">
                                <para>If specified, then Incomplete will not attempt to answer the channel first.</para>
                                <note><para>Most channel types need to be in Answer state in order to receive DTMF.</para></note>
                        </parameter>
                </syntax>
                <description>
                        <para>Signals the PBX routines that the previous matched extension is incomplete
                        and that further input should be allowed before matching can be considered
                        to be complete.  Can be used within a pattern match when certain criteria warrants
                        a longer match.</para>
                </description>
        </application>
        <application name="NoOp" language="en_US">
                <synopsis>
                        Do Nothing (No Operation).
                </synopsis>
                <syntax>
                        <parameter name="text">
                                <para>Any text provided can be viewed at the Asterisk CLI.</para>
                        </parameter>
                </syntax>
                <description>
                        <para>This application does nothing. However, it is useful for debugging purposes.</para>
                        <para>This method can be used to see the evaluations of variables or functions without having any effect.</para>
                </description>
                <see-also>
                        <ref type="application">Verbose</ref>
                        <ref type="application">Log</ref>
                </see-also>
        </application>
        <application name="Proceeding" language="en_US">
                <synopsis>
                        Indicate proceeding.
                </synopsis>
                <syntax />
                <description>
                        <para>This application will request that a proceeding message be provided to the calling channel.</para>
                </description>
        </application>
        <application name="Progress" language="en_US">
                <synopsis>
                        Indicate progress.
                </synopsis>
                <syntax />
                <description>
                        <para>This application will request that in-band progress information be provided to the calling channel.</para>
                </description>
                <see-also>
                        <ref type="application">Busy</ref>
                        <ref type="application">Congestion</ref>
                        <ref type="application">Ringing</ref>
                        <ref type="application">Playtones</ref>
                </see-also>
        </application>
        <application name="RaiseException" language="en_US">
                <synopsis>
                        Handle an exceptional condition.
                </synopsis>
                <syntax>
                        <parameter name="reason" required="true" />
                </syntax>
                <description>
                        <para>This application will jump to the <literal>e</literal> extension in the current context, setting the
                        dialplan function EXCEPTION(). If the <literal>e</literal> extension does not exist, the call will hangup.</para>
                </description>
                <see-also>
                        <ref type="function">Exception</ref>
                </see-also>
        </application>
        <application name="ResetCDR" language="en_US">
                <synopsis>
                        Resets the Call Data Record.
                </synopsis>
                <syntax>
                        <parameter name="options">
                                <optionlist>
                                        <option name="w">
                                                <para>Store the current CDR record before resetting it.</para>
                                        </option>
                                        <option name="a">
                                                <para>Store any stacked records.</para>
                                        </option>
                                        <option name="v">
                                                <para>Save CDR variables.</para>
                                        </option>
                                        <option name="e">
                                                <para>Enable CDR only (negate effects of NoCDR).</para>
                                        </option>
                                </optionlist>
                        </parameter>
                </syntax>
                <description>
                        <para>This application causes the Call Data Record to be reset.</para>
                </description>
                <see-also>
                        <ref type="application">ForkCDR</ref>
                        <ref type="application">NoCDR</ref>
                </see-also>
        </application>
        <application name="Ringing" language="en_US">
                <synopsis>
                        Indicate ringing tone.
                </synopsis>
                <syntax />
                <description>
                        <para>This application will request that the channel indicate a ringing tone to the user.</para>
                </description>
                <see-also>
                        <ref type="application">Busy</ref>
                        <ref type="application">Congestion</ref>
                        <ref type="application">Progress</ref>
                        <ref type="application">Playtones</ref>
                </see-also>
        </application>
        <application name="SayAlpha" language="en_US">
                <synopsis>
                        Say Alpha.
                </synopsis>
                <syntax>
                        <parameter name="string" required="true" />
                </syntax>
                <description>
                        <para>This application will play the sounds that correspond to the letters of the
                        given <replaceable>string</replaceable>.</para>
                </description>
                <see-also>
                        <ref type="application">SayDigits</ref>
                        <ref type="application">SayNumber</ref>
                        <ref type="application">SayPhonetic</ref>
                        <ref type="function">CHANNEL</ref>
                </see-also>
        </application>
        <application name="SayDigits" language="en_US">
                <synopsis>
                        Say Digits.
                </synopsis>
                <syntax>
                        <parameter name="digits" required="true" />
                </syntax>
                <description>
                        <para>This application will play the sounds that correspond to the digits of
                        the given number. This will use the language that is currently set for the channel.</para>
                </description>
                <see-also>
                        <ref type="application">SayAlpha</ref>
                        <ref type="application">SayNumber</ref>
                        <ref type="application">SayPhonetic</ref>
                        <ref type="function">CHANNEL</ref>
                </see-also>
        </application>
        <application name="SayNumber" language="en_US">
                <synopsis>
                        Say Number.
                </synopsis>
                <syntax>
                        <parameter name="digits" required="true" />
                        <parameter name="gender" />
                </syntax>
                <description>
                        <para>This application will play the sounds that correspond to the given <replaceable>digits</replaceable>.
                        Optionally, a <replaceable>gender</replaceable> may be specified. This will use the language that is currently
                        set for the channel. See the CHANNEL() function for more information on setting the language for the channel.</para>
                </description>
                <see-also>
                        <ref type="application">SayAlpha</ref>
                        <ref type="application">SayDigits</ref>
                        <ref type="application">SayPhonetic</ref>
                        <ref type="function">CHANNEL</ref>
                </see-also>
        </application>
        <application name="SayPhonetic" language="en_US">
                <synopsis>
                        Say Phonetic.
                </synopsis>
                <syntax>
                        <parameter name="string" required="true" />
                </syntax>
                <description>
                        <para>This application will play the sounds from the phonetic alphabet that correspond to the
                        letters in the given <replaceable>string</replaceable>.</para>
                </description>
                <see-also>
                        <ref type="application">SayAlpha</ref>
                        <ref type="application">SayDigits</ref>
                        <ref type="application">SayNumber</ref>
                </see-also>
        </application>
        <application name="Set" language="en_US">
                <synopsis>
                        Set channel variable or function value.
                </synopsis>
                <syntax argsep="=">
                        <parameter name="name" required="true" />
                        <parameter name="value" required="true" />
                </syntax>
                <description>
                        <para>This function can be used to set the value of channel variables or dialplan functions.
                        When setting variables, if the variable name is prefixed with <literal>_</literal>,
                        the variable will be inherited into channels created from the current channel.
                        If the variable name is prefixed with <literal>__</literal>, the variable will be
                        inherited into channels created from the current channel and all children channels.</para>
                        <note><para>If (and only if), in <filename>/etc/asterisk/asterisk.conf</filename>, you have
                        a <literal>[compat]</literal> category, and you have <literal>app_set = 1.4</literal> under that, then
                        the behavior of this app changes, and strips surrounding quotes from the right hand side as
                        it did previously in 1.4.
                        The advantages of not stripping out quoting, and not caring about the separator characters (comma and vertical bar)
                        were sufficient to make these changes in 1.6. Confusion about how many backslashes would be needed to properly
                        protect separators and quotes in various database access strings has been greatly
                        reduced by these changes.</para></note>
                </description>
                <see-also>
                        <ref type="application">MSet</ref>
                        <ref type="function">GLOBAL</ref>
                        <ref type="function">SET</ref>
                        <ref type="function">ENV</ref>
                </see-also>
        </application>
        <application name="MSet" language="en_US">
                <synopsis>
                        Set channel variable(s) or function value(s).
                </synopsis>
                <syntax>
                        <parameter name="set1" required="true" argsep="=">
                                <argument name="name1" required="true" />
                                <argument name="value1" required="true" />
                        </parameter>
                        <parameter name="set2" multiple="true" argsep="=">
                                <argument name="name2" required="true" />
                                <argument name="value2" required="true" />
                        </parameter>
                </syntax>
                <description>
                        <para>This function can be used to set the value of channel variables or dialplan functions.
                        When setting variables, if the variable name is prefixed with <literal>_</literal>,
                        the variable will be inherited into channels created from the current channel
                        If the variable name is prefixed with <literal>__</literal>, the variable will be
                        inherited into channels created from the current channel and all children channels.
                        MSet behaves in a similar fashion to the way Set worked in 1.2/1.4 and is thus
                        prone to doing things that you may not expect. For example, it strips surrounding
                        double-quotes from the right-hand side (value). If you need to put a separator
                        character (comma or vert-bar), you will need to escape them by inserting a backslash
                        before them. Avoid its use if possible.</para>
                </description>
                <see-also>
                        <ref type="application">Set</ref>
                </see-also>
        </application>
        <application name="SetAMAFlags" language="en_US">
                <synopsis>
                        Set the AMA Flags.
                </synopsis>
                <syntax>
                        <parameter name="flag" />
                </syntax>
                <description>
                        <para>This application will set the channel's AMA Flags for billing purposes.</para>
                </description>
                <see-also>
                        <ref type="function">CDR</ref>
                </see-also>
        </application>
        <application name="Wait" language="en_US">
                <synopsis>
                        Waits for some time.
                </synopsis>
                <syntax>
                        <parameter name="seconds" required="true">
                                <para>Can be passed with fractions of a second. For example, <literal>1.5</literal> will ask the
                                application to wait for 1.5 seconds.</para>
                        </parameter>
                </syntax>
                <description>
                        <para>This application waits for a specified number of <replaceable>seconds</replaceable>.</para>
                </description>
        </application>
        <application name="WaitExten" language="en_US">
                <synopsis>
                        Waits for an extension to be entered.
                </synopsis>
                <syntax>
                        <parameter name="seconds">
                                <para>Can be passed with fractions of a second. For example, <literal>1.5</literal> will ask the
                                application to wait for 1.5 seconds.</para>
                        </parameter>
                        <parameter name="options">
                                <optionlist>
                                        <option name="m">
                                                <para>Provide music on hold to the caller while waiting for an extension.</para>
                                                <argument name="x">
                                                        <para>Specify the class for music on hold. <emphasis>CHANNEL(musicclass) will
                                                        be used instead if set</emphasis></para>
                                                </argument>
                                        </option>
                                </optionlist>
                        </parameter>
                </syntax>
                <description>
                        <para>This application waits for the user to enter a new extension for a specified number
                        of <replaceable>seconds</replaceable>.</para>
                        <xi:include xpointer="xpointer(/docs/application[@name='Macro']/description/warning[2])" />
                </description>
                <see-also>
                        <ref type="application">Background</ref>
                        <ref type="function">TIMEOUT</ref>
                </see-also>
        </application>
        <function name="EXCEPTION" language="en_US">
                <synopsis>
                        Retrieve the details of the current dialplan exception.
                </synopsis>
                <syntax>
                        <parameter name="field" required="true">
                                <para>The following fields are available for retrieval:</para>
                                <enumlist>
                                        <enum name="reason">
                                                <para>INVALID, ERROR, RESPONSETIMEOUT, ABSOLUTETIMEOUT, or custom
                                                value set by the RaiseException() application</para>
                                        </enum>
                                        <enum name="context">
                                                <para>The context executing when the exception occurred.</para>
                                        </enum>
                                        <enum name="exten">
                                                <para>The extension executing when the exception occurred.</para>
                                        </enum>
                                        <enum name="priority">
                                                <para>The numeric priority executing when the exception occurred.</para>
                                        </enum>
                                </enumlist>
                        </parameter>
                </syntax>
                <description>
                        <para>Retrieve the details (specified <replaceable>field</replaceable>) of the current dialplan exception.</para>
                </description>
                <see-also>
                        <ref type="application">RaiseException</ref>
                </see-also>
        </function>
        <function name="TESTTIME" language="en_US">
                <synopsis>
                        Sets a time to be used with the channel to test logical conditions.
                </synopsis>
                <syntax>
                        <parameter name="date" required="true" argsep=" ">
                                <para>Date in ISO 8601 format</para>
                        </parameter>
                        <parameter name="time" required="true" argsep=" ">
                                <para>Time in HH:MM:SS format (24-hour time)</para>
                        </parameter>
                        <parameter name="zone" required="false">
                                <para>Timezone name</para>
                        </parameter>
                </syntax>
                <description>
                        <para>To test dialplan timing conditions at times other than the current time, use
                        this function to set an alternate date and time.  For example, you may wish to evaluate
                        whether a location will correctly identify to callers that the area is closed on Christmas
                        Day, when Christmas would otherwise fall on a day when the office is normally open.</para>
                </description>
                <see-also>
                        <ref type="application">GotoIfTime</ref>
                </see-also>
        </function>
        <manager name="ShowDialPlan" language="en_US">
                <synopsis>
                        Show dialplan contexts and extensions
                </synopsis>
                <syntax>
                        <xi:include xpointer="xpointer(/docs/manager[@name='Login']/syntax/parameter[@name='ActionID'])" />
                        <parameter name="Extension">
                                <para>Show a specific extension.</para>
                        </parameter>
                        <parameter name="Context">
                                <para>Show a specific context.</para>
                        </parameter>
                </syntax>
                <description>
                        <para>Show dialplan contexts and extensions. Be aware that showing the full dialplan
                        may take a lot of capacity.</para>
                </description>
        </manager>
 ***/

#ifdef LOW_MEMORY
#define EXT_DATA_SIZE 256
#else
#define EXT_DATA_SIZE 8192
#endif

#define SWITCH_DATA_LENGTH 256

#define VAR_BUF_SIZE 4096

#define VAR_NORMAL              1
#define VAR_SOFTTRAN    2
#define VAR_HARDTRAN    3

#define BACKGROUND_SKIP         (1 << 0)
#define BACKGROUND_NOANSWER     (1 << 1)
#define BACKGROUND_MATCHEXTEN   (1 << 2)
#define BACKGROUND_PLAYBACK     (1 << 3)

AST_APP_OPTIONS(background_opts, {
        AST_APP_OPTION('s', BACKGROUND_SKIP),
        AST_APP_OPTION('n', BACKGROUND_NOANSWER),
        AST_APP_OPTION('m', BACKGROUND_MATCHEXTEN),
        AST_APP_OPTION('p', BACKGROUND_PLAYBACK),
});

#define WAITEXTEN_MOH           (1 << 0)
#define WAITEXTEN_DIALTONE      (1 << 1)

AST_APP_OPTIONS(waitexten_opts, {
        AST_APP_OPTION_ARG('m', WAITEXTEN_MOH, 0),
        AST_APP_OPTION_ARG('d', WAITEXTEN_DIALTONE, 0),
});

struct ast_context;
struct ast_app;

static struct ast_taskprocessor *extension_state_tps;

AST_THREADSTORAGE(switch_data);
AST_THREADSTORAGE(extensionstate_buf);

/*!
   \brief ast_exten: An extension
        The dialplan is saved as a linked list with each context
        having it's own linked list of extensions - one item per
        priority.
*/
struct ast_exten {
        char *exten;                    /*!< Extension name */
        int matchcid;                   /*!< Match caller id ? */
        const char *cidmatch;           /*!< Caller id to match for this extension */
        int priority;                   /*!< Priority */
        const char *label;              /*!< Label */
        struct ast_context *parent;     /*!< The context this extension belongs to  */
        const char *app;                /*!< Application to execute */
        struct ast_app *cached_app;     /*!< Cached location of application */
        void *data;                     /*!< Data to use (arguments) */
        void (*datad)(void *);          /*!< Data destructor */
        struct ast_exten *peer;         /*!< Next higher priority with our extension */
        struct ast_hashtab *peer_table;    /*!< Priorities list in hashtab form -- only on the head of the peer list */
        struct ast_hashtab *peer_label_table; /*!< labeled priorities in the peers -- only on the head of the peer list */
        const char *registrar;          /*!< Registrar */
        struct ast_exten *next;         /*!< Extension with a greater ID */
        char stuff[0];
};

/*! \brief ast_include: include= support in extensions.conf */
struct ast_include {
        const char *name;
        const char *rname;                      /*!< Context to include */
        const char *registrar;                  /*!< Registrar */
        int hastime;                            /*!< If time construct exists */
        struct ast_timing timing;               /*!< time construct */
        struct ast_include *next;               /*!< Link them together */
        char stuff[0];
};

/*! \brief ast_sw: Switch statement in extensions.conf */
struct ast_sw {
        char *name;
        const char *registrar;                  /*!< Registrar */
        char *data;                             /*!< Data load */
        int eval;
        AST_LIST_ENTRY(ast_sw) list;
        char stuff[0];
};

/*! \brief ast_ignorepat: Ignore patterns in dial plan */
struct ast_ignorepat {
        const char *registrar;
        struct ast_ignorepat *next;
        const char pattern[0];
};

/*! \brief match_char: forms a syntax tree for quick matching of extension patterns */
struct match_char
{
        int is_pattern; /* the pattern started with '_' */
        int deleted;    /* if this is set, then... don't return it */
        int specificity; /* simply the strlen of x, or 10 for X, 9 for Z, and 8 for N; and '.' and '!' will add 11 ? */
        struct match_char *alt_char;
        struct match_char *next_char;
        struct ast_exten *exten; /* attached to last char of a pattern for exten */
        char x[1];       /* the pattern itself-- matches a single char */
};

struct scoreboard  /* make sure all fields are 0 before calling new_find_extension */
{
        int total_specificity;
        int total_length;
        char last_char;   /* set to ! or . if they are the end of the pattern */
        int canmatch;     /* if the string to match was just too short */
        struct match_char *node;
        struct ast_exten *canmatch_exten;
        struct ast_exten *exten;
};

/*! \brief ast_context: An extension context */
struct ast_context {
        ast_rwlock_t lock;                      /*!< A lock to prevent multiple threads from clobbering the context */
        struct ast_exten *root;                 /*!< The root of the list of extensions */
        struct ast_hashtab *root_table;            /*!< For exact matches on the extensions in the pattern tree, and for traversals of the pattern_tree  */
        struct match_char *pattern_tree;        /*!< A tree to speed up extension pattern matching */
        struct ast_context *next;               /*!< Link them together */
        struct ast_include *includes;           /*!< Include other contexts */
        struct ast_ignorepat *ignorepats;       /*!< Patterns for which to continue playing dialtone */
        char *registrar;                        /*!< Registrar -- make sure you malloc this, as the registrar may have to survive module unloads */
        int refcount;                   /*!< each module that would have created this context should inc/dec this as appropriate */
        AST_LIST_HEAD_NOLOCK(, ast_sw) alts;    /*!< Alternative switches */
        ast_mutex_t macrolock;                  /*!< A lock to implement "exclusive" macros - held whilst a call is executing in the macro */
        char name[0];                           /*!< Name of the context */
};

/*! \brief ast_app: A registered application */
struct ast_app {
        int (*execute)(struct ast_channel *chan, const char *data);
        AST_DECLARE_STRING_FIELDS(
                AST_STRING_FIELD(synopsis);     /*!< Synopsis text for 'show applications' */
                AST_STRING_FIELD(description);  /*!< Description (help text) for 'show application &lt;name&gt;' */
                AST_STRING_FIELD(syntax);       /*!< Syntax text for 'core show applications' */
                AST_STRING_FIELD(arguments);    /*!< Arguments description */
                AST_STRING_FIELD(seealso);      /*!< See also */
        );
#ifdef AST_XML_DOCS
        enum ast_doc_src docsrc;                /*!< Where the documentation come from. */
#endif
        AST_RWLIST_ENTRY(ast_app) list;         /*!< Next app in list */
        struct ast_module *module;              /*!< Module this app belongs to */
        char name[0];                           /*!< Name of the application */
};

/*! \brief ast_state_cb: An extension state notify register item */
struct ast_state_cb {
        /*! Watcher ID returned when registered. */
        int id;
        /*! Arbitrary data passed for callbacks. */
        void *data;
        /*! Flag if this callback is an extended callback containing detailed device status */
        int extended;
        /*! Callback when state changes. */
        ast_state_cb_type change_cb;
        /*! Callback when destroyed so any resources given by the registerer can be freed. */
        ast_state_cb_destroy_type destroy_cb;
        /*! \note Only used by ast_merge_contexts_and_delete */
        AST_LIST_ENTRY(ast_state_cb) entry;
};

/*!
 * \brief Structure for dial plan hints
 *
 * \note Hints are pointers from an extension in the dialplan to
 * one or more devices (tech/name)
 *
 * See \ref AstExtState
 */
struct ast_hint {
        /*!
         * \brief Hint extension
         *
         * \note
         * Will never be NULL while the hint is in the hints container.
         */
        struct ast_exten *exten;
        struct ao2_container *callbacks; /*!< Device state callback container for this extension */

        /*! Dev state variables */
        int laststate;                  /*!< Last known device state */

        /*! Presence state variables */
        int last_presence_state;     /*!< Last known presence state */
        char *last_presence_subtype; /*!< Last known presence subtype string */
        char *last_presence_message; /*!< Last known presence message string */

        char context_name[AST_MAX_CONTEXT];/*!< Context of destroyed hint extension. */
        char exten_name[AST_MAX_EXTENSION];/*!< Extension of destroyed hint extension. */
};


#define HINTDEVICE_DATA_LENGTH 16
AST_THREADSTORAGE(hintdevice_data);

/* --- Hash tables of various objects --------*/
#ifdef LOW_MEMORY
#define HASH_EXTENHINT_SIZE 17
#else
#define HASH_EXTENHINT_SIZE 563
#endif


/*! \brief Container for hint devices */
static struct ao2_container *hintdevices;

/*!
 * \brief Structure for dial plan hint devices
 * \note hintdevice is one device pointing to a hint.
 */
struct ast_hintdevice {
        /*!
         * \brief Hint this hintdevice belongs to.
         * \note Holds a reference to the hint object.
         */
        struct ast_hint *hint;
        /*! Name of the hint device. */
        char hintdevice[1];
};


/*!
 * \note Using the device for hash
 */
static int hintdevice_hash_cb(const void *obj, const int flags)
{
        const struct ast_hintdevice *ext = obj;

        return ast_str_case_hash(ext->hintdevice);
}
/*!
 * \note Devices on hints are not unique so no CMP_STOP is returned
 * Dont use ao2_find against hintdevices container cause there always
 * could be more than one result.
 */
static int hintdevice_cmp_multiple(void *obj, void *arg, int flags)
{
        struct ast_hintdevice *ext = obj, *ext2 = arg;

        return !strcasecmp(ext->hintdevice, ext2->hintdevice) ? CMP_MATCH  : 0;
}

/*
 * \details This is used with ao2_callback to remove old devices
 * when they are linked to the hint
*/
static int hintdevice_remove_cb(void *deviceobj, void *arg, int flags)
{
        struct ast_hintdevice *device = deviceobj;
        struct ast_hint *hint = arg;

        return (device->hint == hint) ? CMP_MATCH : 0;
}

static int remove_hintdevice(struct ast_hint *hint)
{
        /* iterate through all devices and remove the devices which are linked to this hint */
        ao2_t_callback(hintdevices, OBJ_NODATA | OBJ_MULTIPLE | OBJ_UNLINK,
                hintdevice_remove_cb, hint,
                "callback to remove all devices which are linked to a hint");
        return 0;
}

static char *parse_hint_device(struct ast_str *hint_args);
/*!
 * \internal
 * \brief Destroy the given hintdevice object.
 *
 * \param obj Hint device to destroy.
 *
 * \return Nothing
 */
static void hintdevice_destroy(void *obj)
{
        struct ast_hintdevice *doomed = obj;

        if (doomed->hint) {
                ao2_ref(doomed->hint, -1);
                doomed->hint = NULL;
        }
}

/*! \brief add hintdevice structure and link it into the container.
 */
static int add_hintdevice(struct ast_hint *hint, const char *devicelist)
{
        struct ast_str *str;
        char *parse;
        char *cur;
        struct ast_hintdevice *device;
        int devicelength;

        if (!hint || !devicelist) {
                /* Trying to add garbage? Don't bother. */
                return 0;
        }
        if (!(str = ast_str_thread_get(&hintdevice_data, 16))) {
                return -1;
        }
        ast_str_set(&str, 0, "%s", devicelist);
        parse = parse_hint_device(str);

        while ((cur = strsep(&parse, "&"))) {
                devicelength = strlen(cur);
                device = ao2_t_alloc(sizeof(*device) + devicelength, hintdevice_destroy,
                        "allocating a hintdevice structure");
                if (!device) {
                        return -1;
                }
                strcpy(device->hintdevice, cur);
                ao2_ref(hint, +1);
                device->hint = hint;
                ao2_t_link(hintdevices, device, "Linking device into hintdevice container.");
                ao2_t_ref(device, -1, "hintdevice is linked so we can unref");
        }

        return 0;
}


static const struct cfextension_states {
        int extension_state;
        const char * const text;
} extension_states[] = {
        { AST_EXTENSION_NOT_INUSE,                     "Idle" },
        { AST_EXTENSION_INUSE,                         "InUse" },
        { AST_EXTENSION_BUSY,                          "Busy" },
        { AST_EXTENSION_UNAVAILABLE,                   "Unavailable" },
        { AST_EXTENSION_RINGING,                       "Ringing" },
        { AST_EXTENSION_INUSE | AST_EXTENSION_RINGING, "InUse&Ringing" },
        { AST_EXTENSION_ONHOLD,                        "Hold" },
        { AST_EXTENSION_INUSE | AST_EXTENSION_ONHOLD,  "InUse&Hold" }
};

struct presencechange {
        char *provider;
        int state;
        char *subtype;
        char *message;
};

struct statechange {
        AST_LIST_ENTRY(statechange) entry;
        char dev[0];
};

struct pbx_exception {
        AST_DECLARE_STRING_FIELDS(
                AST_STRING_FIELD(context);      /*!< Context associated with this exception */
                AST_STRING_FIELD(exten);        /*!< Exten associated with this exception */
                AST_STRING_FIELD(reason);               /*!< The exception reason */
        );

        int priority;                           /*!< Priority associated with this exception */
};

static int pbx_builtin_answer(struct ast_channel *, const char *);
static int pbx_builtin_goto(struct ast_channel *, const char *);
static int pbx_builtin_hangup(struct ast_channel *, const char *);
static int pbx_builtin_background(struct ast_channel *, const char *);
static int pbx_builtin_wait(struct ast_channel *, const char *);
static int pbx_builtin_waitexten(struct ast_channel *, const char *);
static int pbx_builtin_incomplete(struct ast_channel *, const char *);
static int pbx_builtin_resetcdr(struct ast_channel *, const char *);
static int pbx_builtin_setamaflags(struct ast_channel *, const char *);
static int pbx_builtin_ringing(struct ast_channel *, const char *);
static int pbx_builtin_proceeding(struct ast_channel *, const char *);
static int pbx_builtin_progress(struct ast_channel *, const char *);
static int pbx_builtin_congestion(struct ast_channel *, const char *);
static int pbx_builtin_busy(struct ast_channel *, const char *);
static int pbx_builtin_noop(struct ast_channel *, const char *);
static int pbx_builtin_gotoif(struct ast_channel *, const char *);
static int pbx_builtin_gotoiftime(struct ast_channel *, const char *);
static int pbx_builtin_execiftime(struct ast_channel *, const char *);
static int pbx_builtin_saynumber(struct ast_channel *, const char *);
static int pbx_builtin_saydigits(struct ast_channel *, const char *);
static int pbx_builtin_saycharacters(struct ast_channel *, const char *);
static int pbx_builtin_sayphonetic(struct ast_channel *, const char *);
static int matchcid(const char *cidpattern, const char *callerid);
#ifdef NEED_DEBUG
static void log_match_char_tree(struct match_char *node, char *prefix); /* for use anywhere */
#endif
static int pbx_builtin_importvar(struct ast_channel *, const char *);
static void set_ext_pri(struct ast_channel *c, const char *exten, int pri);
static void new_find_extension(const char *str, struct scoreboard *score,
                struct match_char *tree, int length, int spec, const char *callerid,
                const char *label, enum ext_match_t action);
static struct match_char *already_in_tree(struct match_char *current, char *pat, int is_pattern);
static struct match_char *add_exten_to_pattern_tree(struct ast_context *con,
                struct ast_exten *e1, int findonly);
static void create_match_char_tree(struct ast_context *con);
static struct ast_exten *get_canmatch_exten(struct match_char *node);
static void destroy_pattern_tree(struct match_char *pattern_tree);
static int hashtab_compare_extens(const void *ha_a, const void *ah_b);
static int hashtab_compare_exten_numbers(const void *ah_a, const void *ah_b);
static int hashtab_compare_exten_labels(const void *ah_a, const void *ah_b);
static unsigned int hashtab_hash_extens(const void *obj);
static unsigned int hashtab_hash_priority(const void *obj);
static unsigned int hashtab_hash_labels(const void *obj);
static void __ast_internal_context_destroy( struct ast_context *con);
static int ast_add_extension_nolock(const char *context, int replace, const char *extension,
        int priority, const char *label, const char *callerid,
        const char *application, void *data, void (*datad)(void *), const char *registrar);
static int ast_add_extension2_lockopt(struct ast_context *con,
        int replace, const char *extension, int priority, const char *label, const char *callerid,
        const char *application, void *data, void (*datad)(void *),
        const char *registrar, int lock_context);
static struct ast_context *find_context_locked(const char *context);
static struct ast_context *find_context(const char *context);
static void get_device_state_causing_channels(struct ao2_container *c);

/*!
 * \internal
 * \brief Character array comparison function for qsort.
 *
 * \param a Left side object.
 * \param b Right side object.
 *
 * \retval <0 if a < b
 * \retval =0 if a = b
 * \retval >0 if a > b
 */
static int compare_char(const void *a, const void *b)
{
        const unsigned char *ac = a;
        const unsigned char *bc = b;

        return *ac - *bc;
}

/* labels, contexts are case sensitive  priority numbers are ints */
int ast_hashtab_compare_contexts(const void *ah_a, const void *ah_b)
{
        const struct ast_context *ac = ah_a;
        const struct ast_context *bc = ah_b;
        if (!ac || !bc) /* safety valve, but it might prevent a crash you'd rather have happen */
                return 1;
        /* assume context names are registered in a string table! */
        return strcmp(ac->name, bc->name);
}

static int hashtab_compare_extens(const void *ah_a, const void *ah_b)
{
        const struct ast_exten *ac = ah_a;
        const struct ast_exten *bc = ah_b;
        int x = strcmp(ac->exten, bc->exten);
        if (x) { /* if exten names are diff, then return */
                return x;
        }

        /* but if they are the same, do the cidmatch values match? */
        if (ac->matchcid && bc->matchcid) {
                return strcmp(ac->cidmatch,bc->cidmatch);
        } else if (!ac->matchcid && !bc->matchcid) {
                return 0; /* if there's no matchcid on either side, then this is a match */
        } else {
                return 1; /* if there's matchcid on one but not the other, they are different */
        }
}

static int hashtab_compare_exten_numbers(const void *ah_a, const void *ah_b)
{
        const struct ast_exten *ac = ah_a;
        const struct ast_exten *bc = ah_b;
        return ac->priority != bc->priority;
}

static int hashtab_compare_exten_labels(const void *ah_a, const void *ah_b)
{
        const struct ast_exten *ac = ah_a;
        const struct ast_exten *bc = ah_b;
        return strcmp(S_OR(ac->label, ""), S_OR(bc->label, ""));
}

unsigned int ast_hashtab_hash_contexts(const void *obj)
{
        const struct ast_context *ac = obj;
        return ast_hashtab_hash_string(ac->name);
}

static unsigned int hashtab_hash_extens(const void *obj)
{
        const struct ast_exten *ac = obj;
        unsigned int x = ast_hashtab_hash_string(ac->exten);
        unsigned int y = 0;
        if (ac->matchcid)
                y = ast_hashtab_hash_string(ac->cidmatch);
        return x+y;
}

static unsigned int hashtab_hash_priority(const void *obj)
{
        const struct ast_exten *ac = obj;
        return ast_hashtab_hash_int(ac->priority);
}

static unsigned int hashtab_hash_labels(const void *obj)
{
        const struct ast_exten *ac = obj;
        return ast_hashtab_hash_string(S_OR(ac->label, ""));
}


AST_RWLOCK_DEFINE_STATIC(globalslock);
static struct varshead globals = AST_LIST_HEAD_NOLOCK_INIT_VALUE;

static int autofallthrough = 1;
static int extenpatternmatchnew = 0;
static char *overrideswitch = NULL;

/*! \brief Subscription for device state change events */
static struct ast_event_sub *device_state_sub;
/*! \brief Subscription for presence state change events */
static struct ast_event_sub *presence_state_sub;

AST_MUTEX_DEFINE_STATIC(maxcalllock);
static int countcalls;
static int totalcalls;

static AST_RWLIST_HEAD_STATIC(acf_root, ast_custom_function);

/*! \brief Declaration of builtin applications */
static struct pbx_builtin {
        char name[AST_MAX_APP];
        int (*execute)(struct ast_channel *chan, const char *data);
} builtins[] =
{
        /* These applications are built into the PBX core and do not
           need separate modules */

        { "Answer",         pbx_builtin_answer },
        { "BackGround",     pbx_builtin_background },
        { "Busy",           pbx_builtin_busy },
        { "Congestion",     pbx_builtin_congestion },
        { "ExecIfTime",     pbx_builtin_execiftime },
        { "Goto",           pbx_builtin_goto },
        { "GotoIf",         pbx_builtin_gotoif },
        { "GotoIfTime",     pbx_builtin_gotoiftime },
        { "ImportVar",      pbx_builtin_importvar },
        { "Hangup",         pbx_builtin_hangup },
        { "Incomplete",     pbx_builtin_incomplete },
        { "NoOp",           pbx_builtin_noop },
        { "Proceeding",     pbx_builtin_proceeding },
        { "Progress",       pbx_builtin_progress },
        { "RaiseException", pbx_builtin_raise_exception },
        { "ResetCDR",       pbx_builtin_resetcdr },
        { "Ringing",        pbx_builtin_ringing },
        { "SayAlpha",       pbx_builtin_saycharacters },
        { "SayDigits",      pbx_builtin_saydigits },
        { "SayNumber",      pbx_builtin_saynumber },
        { "SayPhonetic",    pbx_builtin_sayphonetic },
        { "Set",            pbx_builtin_setvar },
        { "MSet",           pbx_builtin_setvar_multiple },
        { "SetAMAFlags",    pbx_builtin_setamaflags },
        { "Wait",           pbx_builtin_wait },
        { "WaitExten",      pbx_builtin_waitexten }
};

static struct ast_context *contexts;
static struct ast_hashtab *contexts_table = NULL;

/*!
 * \brief Lock for the ast_context list
 * \note
 * This lock MUST be recursive, or a deadlock on reload may result.  See
 * https://issues.asterisk.org/view.php?id=17643
 */
AST_MUTEX_DEFINE_STATIC(conlock);

/*!
 * \brief Lock to hold off restructuring of hints by ast_merge_contexts_and_delete.
 */
AST_MUTEX_DEFINE_STATIC(context_merge_lock);

static AST_RWLIST_HEAD_STATIC(apps, ast_app);

static AST_RWLIST_HEAD_STATIC(switches, ast_switch);

static int stateid = 1;
/*!
 * \note When holding this container's lock, do _not_ do
 * anything that will cause conlock to be taken, unless you
 * _already_ hold it.  The ast_merge_contexts_and_delete function
 * will take the locks in conlock/hints order, so any other
 * paths that require both locks must also take them in that
 * order.
 */
static struct ao2_container *hints;

static struct ao2_container *statecbs;

#ifdef CONTEXT_DEBUG

/* these routines are provided for doing run-time checks
   on the extension structures, in case you are having
   problems, this routine might help you localize where
   the problem is occurring. It's kinda like a debug memory
   allocator's arena checker... It'll eat up your cpu cycles!
   but you'll see, if you call it in the right places,
   right where your problems began...
*/

/* you can break on the check_contexts_trouble()
routine in your debugger to stop at the moment
there's a problem */
void check_contexts_trouble(void);

void check_contexts_trouble(void)
{
        int x = 1;
        x = 2;
}

int check_contexts(char *, int);

int check_contexts(char *file, int line )
{
        struct ast_hashtab_iter *t1;
        struct ast_context *c1, *c2;
        int found = 0;
        struct ast_exten *e1, *e2, *e3;
        struct ast_exten ex;

        /* try to find inconsistencies */
        /* is every context in the context table in the context list and vice-versa ? */

        if (!contexts_table) {
                ast_log(LOG_NOTICE,"Called from: %s:%d: No contexts_table!\n", file, line);
                usleep(500000);
        }

        t1 = ast_hashtab_start_traversal(contexts_table);
        while( (c1 = ast_hashtab_next(t1))) {
                for(c2=contexts;c2;c2=c2->next) {
                        if (!strcmp(c1->name, c2->name)) {
                                found = 1;
                                break;
                        }
                }
                if (!found) {
                        ast_log(LOG_NOTICE,"Called from: %s:%d: Could not find the %s context in the linked list\n", file, line, c1->name);
                        check_contexts_trouble();
                }
        }
        ast_hashtab_end_traversal(t1);
        for(c2=contexts;c2;c2=c2->next) {
                c1 = find_context_locked(c2->name);
                if (!c1) {
                        ast_log(LOG_NOTICE,"Called from: %s:%d: Could not find the %s context in the hashtab\n", file, line, c2->name);
                        check_contexts_trouble();
                } else
                        ast_unlock_contexts();
        }

        /* loop thru all contexts, and verify the exten structure compares to the
           hashtab structure */
        for(c2=contexts;c2;c2=c2->next) {
                c1 = find_context_locked(c2->name);
                if (c1) {
                        ast_unlock_contexts();

                        /* is every entry in the root list also in the root_table? */
                        for(e1 = c1->root; e1; e1=e1->next)
                        {
                                char dummy_name[1024];
                                ex.exten = dummy_name;
                                ex.matchcid = e1->matchcid;
                                ex.cidmatch = e1->cidmatch;
                                ast_copy_string(dummy_name, e1->exten, sizeof(dummy_name));
                                e2 = ast_hashtab_lookup(c1->root_table, &ex);
                                if (!e2) {
                                        if (e1->matchcid) {
                                                ast_log(LOG_NOTICE,"Called from: %s:%d: The %s context records the exten %s (CID match: %s) but it is not in its root_table\n", file, line, c2->name, dummy_name, e1->cidmatch );
                                        } else {
                                                ast_log(LOG_NOTICE,"Called from: %s:%d: The %s context records the exten %s but it is not in its root_table\n", file, line, c2->name, dummy_name );
                                        }
                                        check_contexts_trouble();
                                }
                        }

                        /* is every entry in the root_table also in the root list? */
                        if (!c2->root_table) {
                                if (c2->root) {
                                        ast_log(LOG_NOTICE,"Called from: %s:%d: No c2->root_table for context %s!\n", file, line, c2->name);
                                        usleep(500000);
                                }
                        } else {
                                t1 = ast_hashtab_start_traversal(c2->root_table);
                                while( (e2 = ast_hashtab_next(t1)) ) {
                                        for(e1=c2->root;e1;e1=e1->next) {
                                                if (!strcmp(e1->exten, e2->exten)) {
                                                        found = 1;
                                                        break;
                                                }
                                        }
                                        if (!found) {
                                                ast_log(LOG_NOTICE,"Called from: %s:%d: The %s context records the exten %s but it is not in its root_table\n", file, line, c2->name, e2->exten);
                                                check_contexts_trouble();
                                        }

                                }
                                ast_hashtab_end_traversal(t1);
                        }
                }
                /* is every priority reflected in the peer_table at the head of the list? */

                /* is every entry in the root list also in the root_table? */
                /* are the per-extension peer_tables in the right place? */

                for(e1 = c2->root; e1; e1 = e1->next) {

                        for(e2=e1;e2;e2=e2->peer) {
                                ex.priority = e2->priority;
                                if (e2 != e1 && e2->peer_table) {
                                        ast_log(LOG_NOTICE,"Called from: %s:%d: The %s context, %s exten, %d priority has a peer_table entry, and shouldn't!\n", file, line, c2->name, e1->exten, e2->priority );
                                        check_contexts_trouble();
                                }

                                if (e2 != e1 && e2->peer_label_table) {
                                        ast_log(LOG_NOTICE,"Called from: %s:%d: The %s context, %s exten, %d priority has a peer_label_table entry, and shouldn't!\n", file, line, c2->name, e1->exten, e2->priority );
                                        check_contexts_trouble();
                                }

                                if (e2 == e1 && !e2->peer_table){
                                        ast_log(LOG_NOTICE,"Called from: %s:%d: The %s context, %s exten, %d priority doesn't have a peer_table!\n", file, line, c2->name, e1->exten, e2->priority );
                                        check_contexts_trouble();
                                }

                                if (e2 == e1 && !e2->peer_label_table) {
                                        ast_log(LOG_NOTICE,"Called from: %s:%d: The %s context, %s exten, %d priority doesn't have a peer_label_table!\n", file, line, c2->name, e1->exten, e2->priority );
                                        check_contexts_trouble();
                                }


                                e3 = ast_hashtab_lookup(e1->peer_table, &ex);
                                if (!e3) {
                                        ast_log(LOG_NOTICE,"Called from: %s:%d: The %s context, %s exten, %d priority is not reflected in the peer_table\n", file, line, c2->name, e1->exten, e2->priority );
                                        check_contexts_trouble();
                                }
                        }

                        if (!e1->peer_table){
                                ast_log(LOG_NOTICE,"Called from: %s:%d: No e1->peer_table!\n", file, line);
                                usleep(500000);
                        }

                        /* is every entry in the peer_table also in the peer list? */
                        t1 = ast_hashtab_start_traversal(e1->peer_table);
                        while( (e2 = ast_hashtab_next(t1)) ) {
                                for(e3=e1;e3;e3=e3->peer) {
                                        if (e3->priority == e2->priority) {
                                                found = 1;
                                                break;
                                        }
                                }
                                if (!found) {
                                        ast_log(LOG_NOTICE,"Called from: %s:%d: The %s context, %s exten, %d priority is not reflected in the peer list\n", file, line, c2->name, e1->exten, e2->priority );
                                        check_contexts_trouble();
                                }
                        }
                        ast_hashtab_end_traversal(t1);
                }
        }
        return 0;
}
#endif

/*
   \note This function is special. It saves the stack so that no matter
   how many times it is called, it returns to the same place */
int pbx_exec(struct ast_channel *c,     /*!< Channel */
             struct ast_app *app,       /*!< Application */
             const char *data)          /*!< Data for execution */
{
        int res;
        struct ast_module_user *u = NULL;
        const char *saved_c_appl;
        const char *saved_c_data;

        if (ast_channel_cdr(c) && !ast_check_hangup(c))
                ast_cdr_setapp(ast_channel_cdr(c), app->name, data);

        /* save channel values */
        saved_c_appl= ast_channel_appl(c);
        saved_c_data= ast_channel_data(c);

        ast_channel_appl_set(c, app->name);
        ast_channel_data_set(c, data);
        ast_cel_report_event(c, AST_CEL_APP_START, NULL, NULL, NULL);

        if (app->module)
                u = __ast_module_user_add(app->module, c);
        res = app->execute(c, S_OR(data, ""));
        if (app->module && u)
                __ast_module_user_remove(app->module, u);
        ast_cel_report_event(c, AST_CEL_APP_END, NULL, NULL, NULL);
        /* restore channel values */
        ast_channel_appl_set(c, saved_c_appl);
        ast_channel_data_set(c, saved_c_data);
        return res;
}


/*! Go no deeper than this through includes (not counting loops) */
#define AST_PBX_MAX_STACK       128

/*! \brief Find application handle in linked list
 */
struct ast_app *pbx_findapp(const char *app)
{
        struct ast_app *tmp;

        AST_RWLIST_RDLOCK(&apps);
        AST_RWLIST_TRAVERSE(&apps, tmp, list) {
                if (!strcasecmp(tmp->name, app))
                        break;
        }
        AST_RWLIST_UNLOCK(&apps);

        return tmp;
}

static struct ast_switch *pbx_findswitch(const char *sw)
{
        struct ast_switch *asw;

        AST_RWLIST_RDLOCK(&switches);
        AST_RWLIST_TRAVERSE(&switches, asw, list) {
                if (!strcasecmp(asw->name, sw))
                        break;
        }
        AST_RWLIST_UNLOCK(&switches);

        return asw;
}

static inline int include_valid(struct ast_include *i)
{
        if (!i->hastime)
                return 1;

        return ast_check_timing(&(i->timing));
}

static void pbx_destroy(struct ast_pbx *p)
{
        ast_free(p);
}

/* form a tree that fully describes all the patterns in a context's extensions
 * in this tree, a "node" represents an individual character or character set
 * meant to match the corresponding character in a dial string. The tree
 * consists of a series of match_char structs linked in a chain
 * via the alt_char pointers. More than one pattern can share the same parts of the
 * tree as other extensions with the same pattern to that point.
 * My first attempt to duplicate the finding of the 'best' pattern was flawed in that
 * I misunderstood the general algorithm. I thought that the 'best' pattern
 * was the one with lowest total score. This was not true. Thus, if you have
 * patterns "1XXXXX" and "X11111", you would be tempted to say that "X11111" is
 * the "best" match because it has fewer X's, and is therefore more specific,
 * but this is not how the old algorithm works. It sorts matching patterns
 * in a similar collating sequence as sorting alphabetic strings, from left to
 * right. Thus, "1XXXXX" comes before "X11111", and would be the "better" match,
 * because "1" is more specific than "X".
 * So, to accomodate this philosophy, I sort the tree branches along the alt_char
 * line so they are lowest to highest in specificity numbers. This way, as soon
 * as we encounter our first complete match, we automatically have the "best"
 * match and can stop the traversal immediately. Same for CANMATCH/MATCHMORE.
 * If anyone would like to resurrect the "wrong" pattern trie searching algorithm,
 * they are welcome to revert pbx to before 1 Apr 2008.
 * As an example, consider these 4 extensions:
 * (a) NXXNXXXXXX
 * (b) 307754XXXX
 * (c) fax
 * (d) NXXXXXXXXX
 *
 * In the above, between (a) and (d), (a) is a more specific pattern than (d), and would win over
 * most numbers. For all numbers beginning with 307754, (b) should always win.
 *
 * These pattern should form a (sorted) tree that looks like this:
 *   { "3" }  --next-->  { "0" }  --next--> { "7" } --next--> { "7" } --next--> { "5" } ... blah ... --> { "X" exten_match: (b) }
 *      |
 *      |alt
 *      |
 *   { "f" }  --next-->  { "a" }  --next--> { "x"  exten_match: (c) }
 *   { "N" }  --next-->  { "X" }  --next--> { "X" } --next--> { "N" } --next--> { "X" } ... blah ... --> { "X" exten_match: (a) }
 *      |                                                        |
 *      |                                                        |alt
 *      |alt                                                     |
 *      |                                                     { "X" } --next--> { "X" } ... blah ... --> { "X" exten_match: (d) }
 *      |
 *     NULL
 *
 *   In the above, I could easily turn "N" into "23456789", but I think that a quick "if( *z >= '2' && *z <= '9' )" might take
 *   fewer CPU cycles than a call to strchr("23456789",*z), where *z is the char to match...
 *
 *   traversal is pretty simple: one routine merely traverses the alt list, and for each matching char in the pattern,  it calls itself
 *   on the corresponding next pointer, incrementing also the pointer of the string to be matched, and passing the total specificity and length.
 *   We pass a pointer to a scoreboard down through, also.
 *   The scoreboard isn't as necessary to the revised algorithm, but I kept it as a handy way to return the matched extension.
 *   The first complete match ends the traversal, which should make this version of the pattern matcher faster
 *   the previous. The same goes for "CANMATCH" or "MATCHMORE"; the first such match ends the traversal. In both
 *   these cases, the reason we can stop immediately, is because the first pattern match found will be the "best"
 *   according to the sort criteria.
 *   Hope the limit on stack depth won't be a problem... this routine should
 *   be pretty lean as far a stack usage goes. Any non-match terminates the recursion down a branch.
 *
 *   In the above example, with the number "3077549999" as the pattern, the traversor could match extensions a, b and d.  All are
 *   of length 10; they have total specificities of  24580, 10246, and 25090, respectively, not that this matters
 *   at all. (b) wins purely because the first character "3" is much more specific (lower specificity) than "N". I have
 *   left the specificity totals in the code as an artifact; at some point, I will strip it out.
 *
 *   Just how much time this algorithm might save over a plain linear traversal over all possible patterns is unknown,
 *   because it's a function of how many extensions are stored in a context. With thousands of extensions, the speedup
 *   can be very noticeable. The new matching algorithm can run several hundreds of times faster, if not a thousand or
 *   more times faster in extreme cases.
 *
 *   MatchCID patterns are also supported, and stored in the tree just as the extension pattern is. Thus, you
 *   can have patterns in your CID field as well.
 *
 * */


static void update_scoreboard(struct scoreboard *board, int length, int spec, struct ast_exten *exten, char last, const char *callerid, int deleted, struct match_char *node)
{
        /* if this extension is marked as deleted, then skip this -- if it never shows
           on the scoreboard, it will never be found, nor will halt the traversal. */
        if (deleted)
                return;
        board->total_specificity = spec;
        board->total_length = length;
        board->exten = exten;
        board->last_char = last;
        board->node = node;
#ifdef NEED_DEBUG_HERE
        ast_log(LOG_NOTICE,"Scoreboarding (LONGER) %s, len=%d, score=%d\n", exten->exten, length, spec);
#endif
}

#ifdef NEED_DEBUG
static void log_match_char_tree(struct match_char *node, char *prefix)
{
        char extenstr[40];
        struct ast_str *my_prefix = ast_str_alloca(1024);

        extenstr[0] = '\0';

        if (node && node->exten)
                snprintf(extenstr, sizeof(extenstr), "(%p)", node->exten);

        if (strlen(node->x) > 1) {
                ast_debug(1, "%s[%s]:%c:%c:%d:%s%s%s\n", prefix, node->x, node->is_pattern ? 'Y':'N',
                        node->deleted? 'D':'-', node->specificity, node->exten? "EXTEN:":"",
                        node->exten ? node->exten->exten : "", extenstr);
        } else {
                ast_debug(1, "%s%s:%c:%c:%d:%s%s%s\n", prefix, node->x, node->is_pattern ? 'Y':'N',
                        node->deleted? 'D':'-', node->specificity, node->exten? "EXTEN:":"",
                        node->exten ? node->exten->exten : "", extenstr);
        }

        ast_str_set(&my_prefix, 0, "%s+       ", prefix);

        if (node->next_char)
                log_match_char_tree(node->next_char, ast_str_buffer(my_prefix));

        if (node->alt_char)
                log_match_char_tree(node->alt_char, prefix);
}
#endif

static void cli_match_char_tree(struct match_char *node, char *prefix, int fd)
{
        char extenstr[40];
        struct ast_str *my_prefix = ast_str_alloca(1024);

        extenstr[0] = '\0';

        if (node->exten) {
                snprintf(extenstr, sizeof(extenstr), "(%p)", node->exten);
        }

        if (strlen(node->x) > 1) {
                ast_cli(fd, "%s[%s]:%c:%c:%d:%s%s%s\n", prefix, node->x, node->is_pattern ? 'Y' : 'N',
                        node->deleted ? 'D' : '-', node->specificity, node->exten? "EXTEN:" : "",
                        node->exten ? node->exten->exten : "", extenstr);
        } else {
                ast_cli(fd, "%s%s:%c:%c:%d:%s%s%s\n", prefix, node->x, node->is_pattern ? 'Y' : 'N',
                        node->deleted ? 'D' : '-', node->specificity, node->exten? "EXTEN:" : "",
                        node->exten ? node->exten->exten : "", extenstr);
        }

        ast_str_set(&my_prefix, 0, "%s+       ", prefix);

        if (node->next_char)
                cli_match_char_tree(node->next_char, ast_str_buffer(my_prefix), fd);

        if (node->alt_char)
                cli_match_char_tree(node->alt_char, prefix, fd);
}

static struct ast_exten *get_canmatch_exten(struct match_char *node)
{
        /* find the exten at the end of the rope */
        struct match_char *node2 = node;

        for (node2 = node; node2; node2 = node2->next_char) {
                if (node2->exten) {
#ifdef NEED_DEBUG_HERE
                        ast_log(LOG_NOTICE,"CanMatch_exten returns exten %s(%p)\n", node2->exten->exten, node2->exten);
#endif
                        return node2->exten;
                }
        }
#ifdef NEED_DEBUG_HERE
        ast_log(LOG_NOTICE,"CanMatch_exten returns NULL, match_char=%s\n", node->x);
#endif
        return 0;
}

static struct ast_exten *trie_find_next_match(struct match_char *node)
{
        struct match_char *m3;
        struct match_char *m4;
        struct ast_exten *e3;

        if (node && node->x[0] == '.' && !node->x[1]) { /* dot and ! will ALWAYS be next match in a matchmore */
                return node->exten;
        }

        if (node && node->x[0] == '!' && !node->x[1]) {
                return node->exten;
        }

        if (!node || !node->next_char) {
                return NULL;
        }

        m3 = node->next_char;

        if (m3->exten) {
                return m3->exten;
        }
        for (m4 = m3->alt_char; m4; m4 = m4->alt_char) {
                if (m4->exten) {
                        return m4->exten;
                }
        }
        for (m4 = m3; m4; m4 = m4->alt_char) {
                e3 = trie_find_next_match(m3);
                if (e3) {
                        return e3;
                }
        }

        return NULL;
}

#ifdef DEBUG_THIS
static char *action2str(enum ext_match_t action)
{
        switch (action) {
        case E_MATCH:
                return "MATCH";
        case E_CANMATCH:
                return "CANMATCH";
        case E_MATCHMORE:
                return "MATCHMORE";
        case E_FINDLABEL:
                return "FINDLABEL";
        case E_SPAWN:
                return "SPAWN";
        default:
                return "?ACTION?";
        }
}

#endif

static void new_find_extension(const char *str, struct scoreboard *score, struct match_char *tree, int length, int spec, const char *callerid, const char *label, enum ext_match_t action)
{
        struct match_char *p; /* note minimal stack storage requirements */
        struct ast_exten pattern = { .label = label };
#ifdef DEBUG_THIS
        if (tree)
                ast_log(LOG_NOTICE,"new_find_extension called with %s on (sub)tree %s action=%s\n", str, tree->x, action2str(action));
        else
                ast_log(LOG_NOTICE,"new_find_extension called with %s on (sub)tree NULL action=%s\n", str, action2str(action));
#endif
        for (p = tree; p; p = p->alt_char) {
                if (p->is_pattern) {
                        if (p->x[0] == 'N') {
                                if (p->x[1] == 0 && *str >= '2' && *str <= '9' ) {
#define NEW_MATCHER_CHK_MATCH          \
                                        if (p->exten && !(*(str + 1))) { /* if a shorter pattern matches along the way, might as well report it */             \
                                                if (action == E_MATCH || action == E_SPAWN || action == E_FINDLABEL) { /* if in CANMATCH/MATCHMORE, don't let matches get in the way */   \
                                                        update_scoreboard(score, length + 1, spec + p->specificity, p->exten, 0, callerid, p->deleted, p);                 \
                                                        if (!p->deleted) {                                                                                           \
                                                                if (action == E_FINDLABEL) {                                                                             \
                                                                        if (ast_hashtab_lookup(score->exten->peer_label_table, &pattern)) {                                  \
                                                                                ast_debug(4, "Found label in preferred extension\n");                                            \
                                                                                return;                                                                                          \
                                                                        }                                                                                                    \
                                                                } else {                                                                                                 \
                                                                        ast_debug(4, "returning an exact match-- first found-- %s\n", p->exten->exten);                       \
                                                                        return; /* the first match, by definition, will be the best, because of the sorted tree */           \
                                                                }                                                                                                        \
                                                        }                                                                                                            \
                                                }                                                                                                                \
                                        }

#define NEW_MATCHER_RECURSE                \
                                        if (p->next_char && (*(str + 1) || (p->next_char->x[0] == '/' && p->next_char->x[1] == 0)                 \
                                                       || p->next_char->x[0] == '!')) {                                          \
                                                if (*(str + 1) || p->next_char->x[0] == '!') {                                                         \
                                                        new_find_extension(str + 1, score, p->next_char, length + 1, spec + p->specificity, callerid, label, action); \
                                                        if (score->exten)  {                                                                             \
                                                        ast_debug(4 ,"returning an exact match-- %s\n", score->exten->exten);                         \
                                                                return; /* the first match is all we need */                                                 \
                                                        }                                                                                                                                                \
                                                } else {                                                                                             \
                                                        new_find_extension("/", score, p->next_char, length + 1, spec + p->specificity, callerid, label, action);        \
                                                        if (score->exten || ((action == E_CANMATCH || action == E_MATCHMORE) && score->canmatch)) {      \
                                                        ast_debug(4,"returning a (can/more) match--- %s\n", score->exten ? score->exten->exten :     \
                                               "NULL");                                                                        \
                                                                return; /* the first match is all we need */                                                 \
                                                        }                                                                                                                                                \
                                                }                                                                                                    \
                                        } else if ((p->next_char || action == E_CANMATCH) && !*(str + 1)) {                                                                  \
                                                score->canmatch = 1;                                                                                 \
                                                score->canmatch_exten = get_canmatch_exten(p);                                                       \
                                                if (action == E_CANMATCH || action == E_MATCHMORE) {                                                 \
                                                ast_debug(4, "returning a canmatch/matchmore--- str=%s\n", str);                                  \
                                                        return;                                                                                          \
                                                }                                                                                                                                                    \
                                        }

                                        NEW_MATCHER_CHK_MATCH;
                                        NEW_MATCHER_RECURSE;
                                }
                        } else if (p->x[0] == 'Z') {
                                if (p->x[1] == 0 && *str >= '1' && *str <= '9' ) {
                                        NEW_MATCHER_CHK_MATCH;
                                        NEW_MATCHER_RECURSE;
                                }
                        } else if (p->x[0] == 'X') {
                                if (p->x[1] == 0 && *str >= '0' && *str <= '9' ) {
                                        NEW_MATCHER_CHK_MATCH;
                                        NEW_MATCHER_RECURSE;
                                }
                        } else if (p->x[0] == '.' && p->x[1] == 0) {
                                /* how many chars will the . match against? */
                                int i = 0;
                                const char *str2 = str;
                                while (*str2 && *str2 != '/') {
                                        str2++;
                                        i++;
                                }
                                if (p->exten && *str2 != '/') {
                                        update_scoreboard(score, length + i, spec + (i * p->specificity), p->exten, '.', callerid, p->deleted, p);
                                        if (score->exten) {
                                                ast_debug(4,"return because scoreboard has a match with '/'--- %s\n", score->exten->exten);
                                                return; /* the first match is all we need */
                                        }
                                }
                                if (p->next_char && p->next_char->x[0] == '/' && p->next_char->x[1] == 0) {
                                        new_find_extension("/", score, p->next_char, length + i, spec+(p->specificity*i), callerid, label, action);
                                        if (score->exten || ((action == E_CANMATCH || action == E_MATCHMORE) && score->canmatch)) {
                                                ast_debug(4, "return because scoreboard has exact match OR CANMATCH/MATCHMORE & canmatch set--- %s\n", score->exten ? score->exten->exten : "NULL");
                                                return; /* the first match is all we need */
                                        }
                                }
                        } else if (p->x[0] == '!' && p->x[1] == 0) {
                                /* how many chars will the . match against? */
                                int i = 1;
                                const char *str2 = str;
                                while (*str2 && *str2 != '/') {
                                        str2++;
                                        i++;
                                }
                                if (p->exten && *str2 != '/') {
                                        update_scoreboard(score, length + 1, spec + (p->specificity * i), p->exten, '!', callerid, p->deleted, p);
                                        if (score->exten) {
                                                ast_debug(4, "return because scoreboard has a '!' match--- %s\n", score->exten->exten);
                                                return; /* the first match is all we need */
                                        }
                                }
                                if (p->next_char && p->next_char->x[0] == '/' && p->next_char->x[1] == 0) {
                                        new_find_extension("/", score, p->next_char, length + i, spec + (p->specificity * i), callerid, label, action);
                                        if (score->exten || ((action == E_CANMATCH || action == E_MATCHMORE) && score->canmatch)) {
                                                ast_debug(4, "return because scoreboard has exact match OR CANMATCH/MATCHMORE & canmatch set with '/' and '!'--- %s\n", score->exten ? score->exten->exten : "NULL");
                                                return; /* the first match is all we need */
                                        }
                                }
                        } else if (p->x[0] == '/' && p->x[1] == 0) {
                                /* the pattern in the tree includes the cid match! */
                                if (p->next_char && callerid && *callerid) {
                                        new_find_extension(callerid, score, p->next_char, length + 1, spec, callerid, label, action);
                                        if (score->exten || ((action == E_CANMATCH || action == E_MATCHMORE) && score->canmatch)) {
                                                ast_debug(4, "return because scoreboard has exact match OR CANMATCH/MATCHMORE & canmatch set with '/'--- %s\n", score->exten ? score->exten->exten : "NULL");
                                                return; /* the first match is all we need */
                                        }
                                }
                        } else if (strchr(p->x, *str)) {
                                ast_debug(4, "Nothing strange about this match\n");
                                NEW_MATCHER_CHK_MATCH;
                                NEW_MATCHER_RECURSE;
                        }
                } else if (strchr(p->x, *str)) {
                        ast_debug(4, "Nothing strange about this match\n");
                        NEW_MATCHER_CHK_MATCH;
                        NEW_MATCHER_RECURSE;
                }
        }
        ast_debug(4, "return at end of func\n");
}

/* the algorithm for forming the extension pattern tree is also a bit simple; you
 * traverse all the extensions in a context, and for each char of the extension,
 * you see if it exists in the tree; if it doesn't, you add it at the appropriate
 * spot. What more can I say? At the end of each exten, you cap it off by adding the
 * address of the extension involved. Duplicate patterns will be complained about.
 *
 * Ideally, this would be done for each context after it is created and fully
 * filled. It could be done as a finishing step after extensions.conf or .ael is
 * loaded, or it could be done when the first search is encountered. It should only
 * have to be done once, until the next unload or reload.
 *
 * I guess forming this pattern tree would be analogous to compiling a regex. Except
 * that a regex only handles 1 pattern, really. This trie holds any number
 * of patterns. Well, really, it **could** be considered a single pattern,
 * where the "|" (or) operator is allowed, I guess, in a way, sort of...
 */

static struct match_char *already_in_tree(struct match_char *current, char *pat, int is_pattern)
{
        struct match_char *t;

        if (!current) {
                return 0;
        }

        for (t = current; t; t = t->alt_char) {
                if (is_pattern == t->is_pattern && !strcmp(pat, t->x)) {/* uh, we may want to sort exploded [] contents to make matching easy */
                        return t;
                }
        }

        return 0;
}

/* The first arg is the location of the tree ptr, or the
   address of the next_char ptr in the node, so we can mess
   with it, if we need to insert at the beginning of the list */

static void insert_in_next_chars_alt_char_list(struct match_char **parent_ptr, struct match_char *node)
{
        struct match_char *curr, *lcurr;

        /* insert node into the tree at "current", so the alt_char list from current is
           sorted in increasing value as you go to the leaves */
        if (!(*parent_ptr)) {
                *parent_ptr = node;
                return;
        }

        if ((*parent_ptr)->specificity > node->specificity) {
                /* insert at head */
                node->alt_char = (*parent_ptr);
                *parent_ptr = node;
                return;
        }

        lcurr = *parent_ptr;
        for (curr = (*parent_ptr)->alt_char; curr; curr = curr->alt_char) {
                if (curr->specificity > node->specificity) {
                        node->alt_char = curr;
                        lcurr->alt_char = node;
                        break;
                }
                lcurr = curr;
        }

        if (!curr) {
                lcurr->alt_char = node;
        }

}

struct pattern_node {
        /*! Pattern node specificity */
        int specif;
        /*! Pattern node match characters. */
        char buf[256];
};

static struct match_char *add_pattern_node(struct ast_context *con, struct match_char *current, const struct pattern_node *pattern, int is_pattern, int already, struct match_char **nextcharptr)
{
        struct match_char *m;

        if (!(m = ast_calloc(1, sizeof(*m) + strlen(pattern->buf)))) {
                return NULL;
        }

        /* strcpy is safe here since we know its size and have allocated
         * just enough space for when we allocated m
         */
        strcpy(m->x, pattern->buf);

        /* the specificity scores are the same as used in the old
           pattern matcher. */
        m->is_pattern = is_pattern;
        if (pattern->specif == 1 && is_pattern && pattern->buf[0] == 'N') {
                m->specificity = 0x0832;
        } else if (pattern->specif == 1 && is_pattern && pattern->buf[0] == 'Z') {
                m->specificity = 0x0931;
        } else if (pattern->specif == 1 && is_pattern && pattern->buf[0] == 'X') {
                m->specificity = 0x0a30;
        } else if (pattern->specif == 1 && is_pattern && pattern->buf[0] == '.') {
                m->specificity = 0x18000;
        } else if (pattern->specif == 1 && is_pattern && pattern->buf[0] == '!') {
                m->specificity = 0x28000;
        } else {
                m->specificity = pattern->specif;
        }

        if (!con->pattern_tree) {
                insert_in_next_chars_alt_char_list(&con->pattern_tree, m);
        } else {
                if (already) { /* switch to the new regime (traversing vs appending)*/
                        insert_in_next_chars_alt_char_list(nextcharptr, m);
                } else {
                        insert_in_next_chars_alt_char_list(&current->next_char, m);
                }
        }

        return m;
}

/*!
 * \internal
 * \brief Extract the next exten pattern node.
 *
 * \param node Pattern node to fill.
 * \param src Next source character to read.
 * \param pattern TRUE if the exten is a pattern.
 * \param extenbuf Original exten buffer to use in diagnostic messages.
 *
 * \retval Ptr to next extenbuf pos to read.
 */
static const char *get_pattern_node(struct pattern_node *node, const char *src, int pattern, const char *extenbuf)
{
#define INC_DST_OVERFLOW_CHECK                                                  \
        do {                                                                                            \
                if (dst - node->buf < sizeof(node->buf) - 1) {  \
                        ++dst;                                                                          \
                } else {                                                                                \
                        overflow = 1;                                                           \
                }                                                                                               \
        } while (0)

        node->specif = 0;
        node->buf[0] = '\0';
        while (*src) {
                if (*src == '[' && pattern) {
                        char *dst = node->buf;
                        const char *src_next;
                        int length;
                        int overflow = 0;

                        /* get past the '[' */
                        ++src;
                        for (;;) {
                                if (*src == '\\') {
                                        /* Escaped character. */
                                        ++src;
                                        if (*src == '[' || *src == '\\' || *src == '-' || *src == ']') {
                                                *dst = *src++;
                                                INC_DST_OVERFLOW_CHECK;
                                        }
                                } else if (*src == '-') {
                                        unsigned char first;
                                        unsigned char last;

                                        src_next = src;
                                        first = *(src_next - 1);
                                        last = *++src_next;

                                        if (last == '\\') {
                                                /* Escaped character. */
                                                last = *++src_next;
                                        }

                                        /* Possible char range. */
                                        if (node->buf[0] && last) {
                                                /* Expand the char range. */
                                                while (++first <= last) {
                                                        *dst = first;
                                                        INC_DST_OVERFLOW_CHECK;
                                                }
                                                src = src_next + 1;
                                        } else {
                                                /*
                                                 * There was no left or right char for the range.
                                                 * It is just a '-'.
                                                 */
                                                *dst = *src++;
                                                INC_DST_OVERFLOW_CHECK;
                                        }
                                } else if (*src == '\0') {
                                        ast_log(LOG_WARNING,
                                                "A matching ']' was not found for '[' in exten pattern '%s'\n",
                                                extenbuf);
                                        break;
                                } else if (*src == ']') {
                                        ++src;
                                        break;
                                } else {
                                        *dst = *src++;
                                        INC_DST_OVERFLOW_CHECK;
                                }
                        }
                        /* null terminate the exploded range */
                        *dst = '\0';

                        if (overflow) {
                                ast_log(LOG_ERROR,
                                        "Expanded character set too large to deal with in exten pattern '%s'. Ignoring character set.\n",
                                        extenbuf);
                                node->buf[0] = '\0';
                                continue;
                        }

                        /* Sort the characters in character set. */
                        length = strlen(node->buf);
                        if (!length) {
                                ast_log(LOG_WARNING, "Empty character set in exten pattern '%s'. Ignoring.\n",
                                        extenbuf);
                                node->buf[0] = '\0';
                                continue;
                        }
                        qsort(node->buf, length, 1, compare_char);

                        /* Remove duplicate characters from character set. */
                        dst = node->buf;
                        src_next = node->buf;
                        while (*src_next++) {
                                if (*dst != *src_next) {
                                        *++dst = *src_next;
                                }
                        }

                        length = strlen(node->buf);
                        length <<= 8;
                        node->specif = length | (unsigned char) node->buf[0];
                        break;
                } else if (*src == '-') {
                        /* Skip dashes in all extensions. */
                        ++src;
                } else {
                        if (*src == '\\') {
                                /*
                                 * XXX The escape character here does not remove any special
                                 * meaning to characters except the '[', '\\', and '-'
                                 * characters since they are special only in this function.
                                 */
                                node->buf[0] = *++src;
                                if (!node->buf[0]) {
                                        break;
                                }
                        } else {
                                node->buf[0] = *src;
                                if (pattern) {
                                        /* make sure n,x,z patterns are canonicalized to N,X,Z */
                                        if (node->buf[0] == 'n') {
                                                node->buf[0] = 'N';
                                        } else if (node->buf[0] == 'x') {
                                                node->buf[0] = 'X';
                                        } else if (node->buf[0] == 'z') {
                                                node->buf[0] = 'Z';
                                        }
                                }
                        }
                        node->buf[1] = '\0';
                        node->specif = 1;
                        ++src;
                        break;
                }
        }
        return src;

#undef INC_DST_OVERFLOW_CHECK
}

static struct match_char *add_exten_to_pattern_tree(struct ast_context *con, struct ast_exten *e1, int findonly)
{
        struct match_char *m1 = NULL;
        struct match_char *m2 = NULL;
        struct match_char **m0;
        const char *pos;
        int already;
        int pattern = 0;
        int idx_cur;
        int idx_next;
        char extenbuf[512];
        struct pattern_node pat_node[2];

        if (e1->matchcid) {
                if (sizeof(extenbuf) < strlen(e1->exten) + strlen(e1->cidmatch) + 2) {
                        ast_log(LOG_ERROR,
                                "The pattern %s/%s is too big to deal with: it will be ignored! Disaster!\n",
                                e1->exten, e1->cidmatch);
                        return NULL;
                }
                sprintf(extenbuf, "%s/%s", e1->exten, e1->cidmatch);/* Safe.  We just checked. */
        } else {
                ast_copy_string(extenbuf, e1->exten, sizeof(extenbuf));
        }

#ifdef NEED_DEBUG
        ast_debug(1, "Adding exten %s to tree\n", extenbuf);
#endif
        m1 = con->pattern_tree; /* each pattern starts over at the root of the pattern tree */
        m0 = &con->pattern_tree;
        already = 1;

        pos = extenbuf;
        if (*pos == '_') {
                pattern = 1;
                ++pos;
        }
        idx_cur = 0;
        pos = get_pattern_node(&pat_node[idx_cur], pos, pattern, extenbuf);
        for (; pat_node[idx_cur].buf[0]; idx_cur = idx_next) {
                idx_next = (idx_cur + 1) % ARRAY_LEN(pat_node);
                pos = get_pattern_node(&pat_node[idx_next], pos, pattern, extenbuf);

                /* See about adding node to tree. */
                m2 = NULL;
                if (already && (m2 = already_in_tree(m1, pat_node[idx_cur].buf, pattern))
                        && m2->next_char) {
                        if (!pat_node[idx_next].buf[0]) {
                                /*
                                 * This is the end of the pattern, but not the end of the tree.
                                 * Mark this node with the exten... a shorter pattern might win
                                 * if the longer one doesn't match.
                                 */
                                if (findonly) {
                                        return m2;
                                }
                                if (m2->exten) {
                                        ast_log(LOG_WARNING, "Found duplicate exten. Had %s found %s\n",
                                                m2->deleted ? "(deleted/invalid)" : m2->exten->exten, e1->exten);
                                }
                                m2->exten = e1;
                                m2->deleted = 0;
                        }
                        m1 = m2->next_char; /* m1 points to the node to compare against */
                        m0 = &m2->next_char; /* m0 points to the ptr that points to m1 */
                } else { /* not already OR not m2 OR nor m2->next_char */
                        if (m2) {
                                if (findonly) {
                                        return m2;
                                }
                                m1 = m2; /* while m0 stays the same */
                        } else {
                                if (findonly) {
                                        return m1;
                                }
                                m1 = add_pattern_node(con, m1, &pat_node[idx_cur], pattern, already, m0);
                                if (!m1) { /* m1 is the node just added */
                                        return NULL;
                                }
                                m0 = &m1->next_char;
                        }
                        if (!pat_node[idx_next].buf[0]) {
                                if (m2 && m2->exten) {
                                        ast_log(LOG_WARNING, "Found duplicate exten. Had %s found %s\n",
                                                m2->deleted ? "(deleted/invalid)" : m2->exten->exten, e1->exten);
                                }
                                m1->deleted = 0;
                                m1->exten = e1;
                        }

                        /* The 'already' variable is a mini-optimization designed to make it so that we
                         * don't have to call already_in_tree when we know it will return false.
                         */
                        already = 0;
                }
        }
        return m1;
}

static void create_match_char_tree(struct ast_context *con)
{
        struct ast_hashtab_iter *t1;
        struct ast_exten *e1;
#ifdef NEED_DEBUG
        int biggest_bucket, resizes, numobjs, numbucks;

        ast_debug(1, "Creating Extension Trie for context %s(%p)\n", con->name, con);
        ast_hashtab_get_stats(con->root_table, &biggest_bucket, &resizes, &numobjs, &numbucks);
        ast_debug(1, "This tree has %d objects in %d bucket lists, longest list=%d objects, and has resized %d times\n",
                        numobjs, numbucks, biggest_bucket, resizes);
#endif
        t1 = ast_hashtab_start_traversal(con->root_table);
        while ((e1 = ast_hashtab_next(t1))) {
                if (e1->exten) {
                        add_exten_to_pattern_tree(con, e1, 0);
                } else {
                        ast_log(LOG_ERROR, "Attempt to create extension with no extension name.\n");
                }
        }
        ast_hashtab_end_traversal(t1);
}

static void destroy_pattern_tree(struct match_char *pattern_tree) /* pattern tree is a simple binary tree, sort of, so the proper way to destroy it is... recursively! */
{
        /* destroy all the alternates */
        if (pattern_tree->alt_char) {
                destroy_pattern_tree(pattern_tree->alt_char);
                pattern_tree->alt_char = 0;
        }
        /* destroy all the nexts */
        if (pattern_tree->next_char) {
                destroy_pattern_tree(pattern_tree->next_char);
                pattern_tree->next_char = 0;
        }
        pattern_tree->exten = 0; /* never hurts to make sure there's no pointers laying around */
        ast_free(pattern_tree);
}

/*!
 * \internal
 * \brief Get the length of the exten string.
 *
 * \param str Exten to get length.
 *
 * \retval strlen of exten.
 */
static int ext_cmp_exten_strlen(const char *str)
{
        int len;

        len = 0;
        for (;;) {
                /* Ignore '-' chars as eye candy fluff. */
                while (*str == '-') {
                        ++str;
                }
                if (!*str) {
                        break;
                }
                ++str;
                ++len;
        }
        return len;
}

/*!
 * \internal
 * \brief Partial comparison of non-pattern extens.
 *
 * \param left Exten to compare.
 * \param right Exten to compare.  Also matches if this string ends first.
 *
 * \retval <0 if left < right
 * \retval =0 if left == right
 * \retval >0 if left > right
 */
static int ext_cmp_exten_partial(const char *left, const char *right)
{
        int cmp;

        for (;;) {
                /* Ignore '-' chars as eye candy fluff. */
                while (*left == '-') {
                        ++left;
                }
                while (*right == '-') {
                        ++right;
                }

                if (!*right) {
                        /*
                         * Right ended first for partial match or both ended at the same
                         * time for a match.
                         */
                        cmp = 0;
                        break;
                }

                cmp = *left - *right;
                if (cmp) {
                        break;
                }
                ++left;
                ++right;
        }
        return cmp;
}

/*!
 * \internal
 * \brief Comparison of non-pattern extens.
 *
 * \param left Exten to compare.
 * \param right Exten to compare.
 *
 * \retval <0 if left < right
 * \retval =0 if left == right
 * \retval >0 if left > right
 */
static int ext_cmp_exten(const char *left, const char *right)
{
        int cmp;

        for (;;) {
                /* Ignore '-' chars as eye candy fluff. */
                while (*left == '-') {
                        ++left;
                }
                while (*right == '-') {
                        ++right;
                }

                cmp = *left - *right;
                if (cmp) {
                        break;
                }
                if (!*left) {
                        /*
                         * Get here only if both strings ended at the same time.  cmp
                         * would be non-zero if only one string ended.
                         */
                        break;
                }
                ++left;
                ++right;
        }
        return cmp;
}

/*
 * Special characters used in patterns:
 *      '_'     underscore is the leading character of a pattern.
 *              In other position it is treated as a regular char.
 *      '-' The '-' is a separator and ignored.  Why?  So patterns like NXX-XXX-XXXX work.
 *      .       one or more of any character. Only allowed at the end of
 *              a pattern.
 *      !       zero or more of anything. Also impacts the result of CANMATCH
 *              and MATCHMORE. Only allowed at the end of a pattern.
 *              In the core routine, ! causes a match with a return code of 2.
 *              In turn, depending on the search mode: (XXX check if it is implemented)
 *              - E_MATCH retuns 1 (does match)
 *              - E_MATCHMORE returns 0 (no match)
 *              - E_CANMATCH returns 1 (does match)
 *
 *      /       should not appear as it is considered the separator of the CID info.
 *              XXX at the moment we may stop on this char.
 *
 *      X Z N   match ranges 0-9, 1-9, 2-9 respectively.
 *      [       denotes the start of a set of character. Everything inside
 *              is considered literally. We can have ranges a-d and individual
 *              characters. A '[' and '-' can be considered literally if they
 *              are just before ']'.
 *              XXX currently there is no way to specify ']' in a range, nor \ is
 *              considered specially.
 *
 * When we compare a pattern with a specific extension, all characters in the extension
 * itself are considered literally.
 * XXX do we want to consider space as a separator as well ?
 * XXX do we want to consider the separators in non-patterns as well ?
 */

/*!
 * \brief helper functions to sort extension patterns in the desired way,
 * so that more specific patterns appear first.
 *
 * \details
 * The function compares individual characters (or sets of), returning
 * an int where bits 0-7 are the ASCII code of the first char in the set,
 * bits 8-15 are the number of characters in the set, and bits 16-20 are
 * for special cases.
 * This way more specific patterns (smaller character sets) appear first.
 * Wildcards have a special value, so that we can directly compare them to
 * sets by subtracting the two values. In particular:
 *  0x001xx     one character, character set starting with xx
 *  0x0yyxx     yy characters, character set starting with xx
 *  0x18000     '.' (one or more of anything)
 *  0x28000     '!' (zero or more of anything)
 *  0x30000     NUL (end of string)
 *  0x40000     error in set.
 * The pointer to the string is advanced according to needs.
 * NOTES:
 *  1. the empty set is ignored.
 *  2. given that a full set has always 0 as the first element,
 *     we could encode the special cases as 0xffXX where XX
 *     is 1, 2, 3, 4 as used above.
 */
static int ext_cmp_pattern_pos(const char **p, unsigned char *bitwise)
{
#define BITS_PER        8       /* Number of bits per unit (byte). */
        unsigned char c;
        unsigned char cmin;
        int count;
        const char *end;

        do {
                /* Get character and advance. (Ignore '-' chars as eye candy fluff.) */
                do {
                        c = *(*p)++;
                } while (c == '-');

                /* always return unless we have a set of chars */
                switch (c) {
                default:
                        /* ordinary character */
                        bitwise[c / BITS_PER] = 1 << ((BITS_PER - 1) - (c % BITS_PER));
                        return 0x0100 | c;

                case 'n':
                case 'N':
                        /* 2..9 */
                        bitwise[6] = 0x3f;
                        bitwise[7] = 0xc0;
                        return 0x0800 | '2';

                case 'x':
                case 'X':
                        /* 0..9 */
                        bitwise[6] = 0xff;
                        bitwise[7] = 0xc0;
                        return 0x0A00 | '0';

                case 'z':
                case 'Z':
                        /* 1..9 */
                        bitwise[6] = 0x7f;
                        bitwise[7] = 0xc0;
                        return 0x0900 | '1';

                case '.':
                        /* wildcard */
                        return 0x18000;

                case '!':
                        /* earlymatch */
                        return 0x28000; /* less specific than '.' */

                case '\0':
                        /* empty string */
                        *p = NULL;
                        return 0x30000;

                case '[':
                        /* char set */
                        break;
                }
                /* locate end of set */
                end = strchr(*p, ']');

                if (!end) {
                        ast_log(LOG_WARNING, "Wrong usage of [] in the extension\n");
                        return 0x40000; /* XXX make this entry go last... */
                }

                count = 0;
                cmin = 0xFF;
                for (; *p < end; ++*p) {
                        unsigned char c1;       /* first char in range */
                        unsigned char c2;       /* last char in range */

                        c1 = (*p)[0];
                        if (*p + 2 < end && (*p)[1] == '-') { /* this is a range */
                                c2 = (*p)[2];
                                *p += 2;    /* skip a total of 3 chars */
                        } else {        /* individual character */
                                c2 = c1;
                        }
                        if (c1 < cmin) {
                                cmin = c1;
                        }
                        for (; c1 <= c2; ++c1) {
                                unsigned char mask = 1 << ((BITS_PER - 1) - (c1 % BITS_PER));

                                /*
                                 * Note: If two character sets score the same, the one with the
                                 * lowest ASCII values will compare as coming first.  Must fill
                                 * in most significant bits for lower ASCII values to accomplish
                                 * the desired sort order.
                                 */
                                if (!(bitwise[c1 / BITS_PER] & mask)) {
                                        /* Add the character to the set. */
                                        bitwise[c1 / BITS_PER] |= mask;
                                        count += 0x100;
                                }
                        }
                }
                ++*p;
        } while (!count);/* While the char set was empty. */
        return count | cmin;
}

/*!
 * \internal
 * \brief Comparison of exten patterns.
 *
 * \param left Pattern to compare.
 * \param right Pattern to compare.
 *
 * \retval <0 if left < right
 * \retval =0 if left == right
 * \retval >0 if left > right
 */
static int ext_cmp_pattern(const char *left, const char *right)
{
        int cmp;
        int left_pos;
        int right_pos;

        for (;;) {
                unsigned char left_bitwise[32] = { 0, };
                unsigned char right_bitwise[32] = { 0, };

                left_pos = ext_cmp_pattern_pos(&left, left_bitwise);
                right_pos = ext_cmp_pattern_pos(&right, right_bitwise);
                cmp = left_pos - right_pos;
                if (!cmp) {
                        /*
                         * Are the character sets different, even though they score the same?
                         *
                         * Note: Must swap left and right to get the sense of the
                         * comparison correct.  Otherwise, we would need to multiply by
                         * -1 instead.
                         */
                        cmp = memcmp(right_bitwise, left_bitwise, ARRAY_LEN(left_bitwise));
                }
                if (cmp) {
                        break;
                }
                if (!left) {
                        /*
                         * Get here only if both patterns ended at the same time.  cmp
                         * would be non-zero if only one pattern ended.
                         */
                        break;
                }
        }
        return cmp;
}

/*!
 * \internal
 * \brief Comparison of dialplan extens for sorting purposes.
 *
 * \param left Exten/pattern to compare.
 * \param right Exten/pattern to compare.
 *
 * \retval <0 if left < right
 * \retval =0 if left == right
 * \retval >0 if left > right
 */
static int ext_cmp(const char *left, const char *right)
{
        /* Make sure non-pattern extens come first. */
        if (left[0] != '_') {
                if (right[0] == '_') {
                        return -1;
                }
                /* Compare two non-pattern extens. */
                return ext_cmp_exten(left, right);
        }
        if (right[0] != '_') {
                return 1;
        }

        /*
         * OK, we need full pattern sorting routine.
         *
         * Skip past the underscores
         */
        return ext_cmp_pattern(left + 1, right + 1);
}

int ast_extension_cmp(const char *a, const char *b)
{
        int cmp;

        cmp = ext_cmp(a, b);
        if (cmp < 0) {
                return -1;
        }
        if (cmp > 0) {
                return 1;
        }
        return 0;
}

/*!
 * \internal
 * \brief used ast_extension_{match|close}
 * mode is as follows:
 *      E_MATCH         success only on exact match
 *      E_MATCHMORE     success only on partial match (i.e. leftover digits in pattern)
 *      E_CANMATCH      either of the above.
 * \retval 0 on no-match
 * \retval 1 on match
 * \retval 2 on early match.
 */

static int _extension_match_core(const char *pattern, const char *data, enum ext_match_t mode)
{
        mode &= E_MATCH_MASK;   /* only consider the relevant bits */

#ifdef NEED_DEBUG_HERE
        ast_log(LOG_NOTICE,"match core: pat: '%s', dat: '%s', mode=%d\n", pattern, data, (int)mode);
#endif

        if (pattern[0] != '_') { /* not a pattern, try exact or partial match */
                int lp = ext_cmp_exten_strlen(pattern);
                int ld = ext_cmp_exten_strlen(data);

                if (lp < ld) {          /* pattern too short, cannot match */
#ifdef NEED_DEBUG_HERE
                        ast_log(LOG_NOTICE,"return (0) - pattern too short, cannot match\n");
#endif
                        return 0;
                }
                /* depending on the mode, accept full or partial match or both */
                if (mode == E_MATCH) {
#ifdef NEED_DEBUG_HERE
                        ast_log(LOG_NOTICE,"return (!ext_cmp_exten(%s,%s) when mode== E_MATCH)\n", pattern, data);
#endif
                        return !ext_cmp_exten(pattern, data); /* 1 on match, 0 on fail */
                }
                if (ld == 0 || !ext_cmp_exten_partial(pattern, data)) { /* partial or full match */
#ifdef NEED_DEBUG_HERE
                        ast_log(LOG_NOTICE,"return (mode(%d) == E_MATCHMORE ? lp(%d) > ld(%d) : 1)\n", mode, lp, ld);
#endif
                        return (mode == E_MATCHMORE) ? lp > ld : 1; /* XXX should consider '!' and '/' ? */
                } else {
#ifdef NEED_DEBUG_HERE
                        ast_log(LOG_NOTICE,"return (0) when ld(%d) > 0 && pattern(%s) != data(%s)\n", ld, pattern, data);
#endif
                        return 0;
                }
        }
        if (mode == E_MATCH && data[0] == '_') {
                /*
                 * XXX It is bad design that we don't know if we should be
                 * comparing data and pattern as patterns or comparing data if
                 * it conforms to pattern when the function is called.  First,
                 * assume they are both patterns.  If they don't match then try
                 * to see if data conforms to the given pattern.
                 *
                 * note: if this test is left out, then _x. will not match _x. !!!
                 */
#ifdef NEED_DEBUG_HERE
                ast_log(LOG_NOTICE, "Comparing as patterns first. pattern:%s data:%s\n", pattern, data);
#endif
                if (!ext_cmp_pattern(pattern + 1, data + 1)) {
#ifdef NEED_DEBUG_HERE
                        ast_log(LOG_NOTICE,"return (1) - pattern matches pattern\n");
#endif
                        return 1;
                }
        }

        ++pattern; /* skip leading _ */
        /*
         * XXX below we stop at '/' which is a separator for the CID info. However we should
         * not store '/' in the pattern at all. When we insure it, we can remove the checks.
         */
        for (;;) {
                const char *end;

                /* Ignore '-' chars as eye candy fluff. */
                while (*data == '-') {
                        ++data;
                }
                while (*pattern == '-') {
                        ++pattern;
                }
                if (!*data || !*pattern || *pattern == '/') {
                        break;
                }

                switch (*pattern) {
                case '[':       /* a range */
                        ++pattern;
                        end = strchr(pattern, ']'); /* XXX should deal with escapes ? */
                        if (!end) {
                                ast_log(LOG_WARNING, "Wrong usage of [] in the extension\n");
                                return 0;       /* unconditional failure */
                        }
                        if (pattern == end) {
                                /* Ignore empty character sets. */
                                ++pattern;
                                continue;
                        }
                        for (; pattern < end; ++pattern) {
                                if (pattern+2 < end && pattern[1] == '-') { /* this is a range */
                                        if (*data >= pattern[0] && *data <= pattern[2])
                                                break;  /* match found */
                                        else {
                                                pattern += 2; /* skip a total of 3 chars */
                                                continue;
                                        }
                                } else if (*data == pattern[0])
                                        break;  /* match found */
                        }
                        if (pattern >= end) {
#ifdef NEED_DEBUG_HERE
                                ast_log(LOG_NOTICE,"return (0) when pattern>=end\n");
#endif
                                return 0;
                        }
                        pattern = end;  /* skip and continue */
                        break;
                case 'n':
                case 'N':
                        if (*data < '2' || *data > '9') {
#ifdef NEED_DEBUG_HERE
                                ast_log(LOG_NOTICE,"return (0) N is not matched\n");
#endif
                                return 0;
                        }
                        break;
                case 'x':
                case 'X':
                        if (*data < '0' || *data > '9') {
#ifdef NEED_DEBUG_HERE
                                ast_log(LOG_NOTICE,"return (0) X is not matched\n");
#endif
                                return 0;
                        }
                        break;
                case 'z':
                case 'Z':
                        if (*data < '1' || *data > '9') {
#ifdef NEED_DEBUG_HERE
                                ast_log(LOG_NOTICE,"return (0) Z is not matched\n");
#endif
                                return 0;
                        }
                        break;
                case '.':       /* Must match, even with more digits */
#ifdef NEED_DEBUG_HERE
                        ast_log(LOG_NOTICE, "return (1) when '.' is matched\n");
#endif
                        return 1;
                case '!':       /* Early match */
#ifdef NEED_DEBUG_HERE
                        ast_log(LOG_NOTICE, "return (2) when '!' is matched\n");
#endif
                        return 2;
                default:
                        if (*data != *pattern) {
#ifdef NEED_DEBUG_HERE
                                ast_log(LOG_NOTICE, "return (0) when *data(%c) != *pattern(%c)\n", *data, *pattern);
#endif
                                return 0;
                        }
                        break;
                }
                ++data;
                ++pattern;
        }
        if (*data)                      /* data longer than pattern, no match */ {
#ifdef NEED_DEBUG_HERE
                ast_log(LOG_NOTICE, "return (0) when data longer than pattern\n");
#endif
                return 0;
        }

        /*
         * match so far, but ran off the end of data.
         * Depending on what is next, determine match or not.
         */
        if (*pattern == '\0' || *pattern == '/') {      /* exact match */
#ifdef NEED_DEBUG_HERE
                ast_log(LOG_NOTICE, "at end, return (%d) in 'exact match'\n", (mode==E_MATCHMORE) ? 0 : 1);
#endif
                return (mode == E_MATCHMORE) ? 0 : 1;   /* this is a failure for E_MATCHMORE */
        } else if (*pattern == '!')     {               /* early match */
#ifdef NEED_DEBUG_HERE
                ast_log(LOG_NOTICE, "at end, return (2) when '!' is matched\n");
#endif
                return 2;
        } else {                                                /* partial match */
#ifdef NEED_DEBUG_HERE
                ast_log(LOG_NOTICE, "at end, return (%d) which deps on E_MATCH\n", (mode == E_MATCH) ? 0 : 1);
#endif
                return (mode == E_MATCH) ? 0 : 1;       /* this is a failure for E_MATCH */
        }
}

/*
 * Wrapper around _extension_match_core() to do performance measurement
 * using the profiling code.
 */
static int extension_match_core(const char *pattern, const char *data, enum ext_match_t mode)
{
        int i;
        static int prof_id = -2;        /* marker for 'unallocated' id */
        if (prof_id == -2) {
                prof_id = ast_add_profile("ext_match", 0);
        }
        ast_mark(prof_id, 1);
        i = _extension_match_core(ast_strlen_zero(pattern) ? "" : pattern, ast_strlen_zero(data) ? "" : data, mode);
        ast_mark(prof_id, 0);
        return i;
}

int ast_extension_match(const char *pattern, const char *data)
{
        return extension_match_core(pattern, data, E_MATCH);
}

int ast_extension_close(const char *pattern, const char *data, int needmore)
{
        if (needmore != E_MATCHMORE && needmore != E_CANMATCH)
                ast_log(LOG_WARNING, "invalid argument %d\n", needmore);
        return extension_match_core(pattern, data, needmore);
}

struct fake_context /* this struct is purely for matching in the hashtab */
{
        ast_rwlock_t lock;
        struct ast_exten *root;
        struct ast_hashtab *root_table;
        struct match_char *pattern_tree;
        struct ast_context *next;
        struct ast_include *includes;
        struct ast_ignorepat *ignorepats;
        const char *registrar;
        int refcount;
        AST_LIST_HEAD_NOLOCK(, ast_sw) alts;
        ast_mutex_t macrolock;
        char name[256];
};

struct ast_context *ast_context_find(const char *name)
{
        struct ast_context *tmp;
        struct fake_context item;

        if (!name) {
                return NULL;
        }
        ast_rdlock_contexts();
        if (contexts_table) {
                ast_copy_string(item.name, name, sizeof(item.name));
                tmp = ast_hashtab_lookup(contexts_table, &item);
        } else {
                tmp = NULL;
                while ((tmp = ast_walk_contexts(tmp))) {
                        if (!strcasecmp(name, tmp->name)) {
                                break;
                        }
                }
        }
        ast_unlock_contexts();
        return tmp;
}

#define STATUS_NO_CONTEXT       1
#define STATUS_NO_EXTENSION     2
#define STATUS_NO_PRIORITY      3
#define STATUS_NO_LABEL         4
#define STATUS_SUCCESS          5

static int matchcid(const char *cidpattern, const char *callerid)
{
        /* If the Caller*ID pattern is empty, then we're matching NO Caller*ID, so
           failing to get a number should count as a match, otherwise not */

        if (ast_strlen_zero(callerid)) {
                return ast_strlen_zero(cidpattern) ? 1 : 0;
        }

        return ast_extension_match(cidpattern, callerid);
}

struct ast_exten *pbx_find_extension(struct ast_channel *chan,
        struct ast_context *bypass, struct pbx_find_info *q,
        const char *context, const char *exten, int priority,
        const char *label, const char *callerid, enum ext_match_t action)
{
        int x, res;
        struct ast_context *tmp = NULL;
        struct ast_exten *e = NULL, *eroot = NULL;
        struct ast_include *i = NULL;
        struct ast_sw *sw = NULL;
        struct ast_exten pattern = {NULL, };
        struct scoreboard score = {0, };
        struct ast_str *tmpdata = NULL;

        pattern.label = label;
        pattern.priority = priority;
#ifdef NEED_DEBUG_HERE
        ast_log(LOG_NOTICE, "Looking for cont/ext/prio/label/action = %s/%s/%d/%s/%d\n", context, exten, priority, label, (int) action);
#endif

        /* Initialize status if appropriate */
        if (q->stacklen == 0) {
                q->status = STATUS_NO_CONTEXT;
                q->swo = NULL;
                q->data = NULL;
                q->foundcontext = NULL;
        } else if (q->stacklen >= AST_PBX_MAX_STACK) {
                ast_log(LOG_WARNING, "Maximum PBX stack exceeded\n");
                return NULL;
        }

        /* Check first to see if we've already been checked */
        for (x = 0; x < q->stacklen; x++) {
                if (!strcasecmp(q->incstack[x], context))
                        return NULL;
        }

        if (bypass) { /* bypass means we only look there */
                tmp = bypass;
        } else {      /* look in contexts */
                tmp = find_context(context);
                if (!tmp) {
                        return NULL;
                }
        }

        if (q->status < STATUS_NO_EXTENSION)
                q->status = STATUS_NO_EXTENSION;

        /* Do a search for matching extension */

        eroot = NULL;
        score.total_specificity = 0;
        score.exten = 0;
        score.total_length = 0;
        if (!tmp->pattern_tree && tmp->root_table) {
                create_match_char_tree(tmp);
#ifdef NEED_DEBUG
                ast_debug(1, "Tree Created in context %s:\n", context);
                log_match_char_tree(tmp->pattern_tree," ");
#endif
        }
#ifdef NEED_DEBUG
        ast_log(LOG_NOTICE, "The Trie we are searching in:\n");
        log_match_char_tree(tmp->pattern_tree, "::  ");
#endif

        do {
                if (!ast_strlen_zero(overrideswitch)) {
                        char *osw = ast_strdupa(overrideswitch), *name;
                        struct ast_switch *asw;
                        ast_switch_f *aswf = NULL;
                        char *datap;
                        int eval = 0;

                        name = strsep(&osw, "/");
                        asw = pbx_findswitch(name);

                        if (!asw) {
                                ast_log(LOG_WARNING, "No such switch '%s'\n", name);
                                break;
                        }

                        if (osw && strchr(osw, '$')) {
                                eval = 1;
                        }

                        if (eval && !(tmpdata = ast_str_thread_get(&switch_data, 512))) {
                                ast_log(LOG_WARNING, "Can't evaluate overrideswitch?!\n");
                                break;
                        } else if (eval) {
                                /* Substitute variables now */
                                pbx_substitute_variables_helper(chan, osw, ast_str_buffer(tmpdata), ast_str_size(tmpdata));
                                datap = ast_str_buffer(tmpdata);
                        } else {
                                datap = osw;
                        }

                        /* equivalent of extension_match_core() at the switch level */
                        if (action == E_CANMATCH)
                                aswf = asw->canmatch;
                        else if (action == E_MATCHMORE)
                                aswf = asw->matchmore;
                        else /* action == E_MATCH */
                                aswf = asw->exists;
                        if (!aswf) {
                                res = 0;
                        } else {
                                if (chan) {
                                        ast_autoservice_start(chan);
                                }
                                res = aswf(chan, context, exten, priority, callerid, datap);
                                if (chan) {
                                        ast_autoservice_stop(chan);
                                }
                        }
                        if (res) {      /* Got a match */
                                q->swo = asw;
                                q->data = datap;
                                q->foundcontext = context;
                                /* XXX keep status = STATUS_NO_CONTEXT ? */
                                return NULL;
                        }
                }
        } while (0);

        if (extenpatternmatchnew) {
                new_find_extension(exten, &score, tmp->pattern_tree, 0, 0, callerid, label, action);
                eroot = score.exten;

                if (score.last_char == '!' && action == E_MATCHMORE) {
                        /* We match an extension ending in '!'.
                         * The decision in this case is final and is NULL (no match).
                         */
#ifdef NEED_DEBUG_HERE
                        ast_log(LOG_NOTICE,"Returning MATCHMORE NULL with exclamation point.\n");
#endif
                        return NULL;
                }

                if (!eroot && (action == E_CANMATCH || action == E_MATCHMORE) && score.canmatch_exten) {
                        q->status = STATUS_SUCCESS;
#ifdef NEED_DEBUG_HERE
                        ast_log(LOG_NOTICE,"Returning CANMATCH exten %s\n", score.canmatch_exten->exten);
#endif
                        return score.canmatch_exten;
                }

                if ((action == E_MATCHMORE || action == E_CANMATCH)  && eroot) {
                        if (score.node) {
                                struct ast_exten *z = trie_find_next_match(score.node);
                                if (z) {
#ifdef NEED_DEBUG_HERE
                                        ast_log(LOG_NOTICE,"Returning CANMATCH/MATCHMORE next_match exten %s\n", z->exten);
#endif
                                } else {
                                        if (score.canmatch_exten) {
#ifdef NEED_DEBUG_HERE
                                                ast_log(LOG_NOTICE,"Returning CANMATCH/MATCHMORE canmatchmatch exten %s(%p)\n", score.canmatch_exten->exten, score.canmatch_exten);
#endif
                                                return score.canmatch_exten;
                                        } else {
#ifdef NEED_DEBUG_HERE
                                                ast_log(LOG_NOTICE,"Returning CANMATCH/MATCHMORE next_match exten NULL\n");
#endif
                                        }
                                }
                                return z;
                        }
#ifdef NEED_DEBUG_HERE
                        ast_log(LOG_NOTICE, "Returning CANMATCH/MATCHMORE NULL (no next_match)\n");
#endif
                        return NULL;  /* according to the code, complete matches are null matches in MATCHMORE mode */
                }

                if (eroot) {
                        /* found entry, now look for the right priority */
                        if (q->status < STATUS_NO_PRIORITY)
                                q->status = STATUS_NO_PRIORITY;
                        e = NULL;
                        if (action == E_FINDLABEL && label ) {
                                if (q->status < STATUS_NO_LABEL)
                                        q->status = STATUS_NO_LABEL;
                                e = ast_hashtab_lookup(eroot->peer_label_table, &pattern);
                        } else {
                                e = ast_hashtab_lookup(eroot->peer_table, &pattern);
                        }
                        if (e) {        /* found a valid match */
                                q->status = STATUS_SUCCESS;
                                q->foundcontext = context;
#ifdef NEED_DEBUG_HERE
                                ast_log(LOG_NOTICE,"Returning complete match of exten %s\n", e->exten);
#endif
                                return e;
                        }
                }
        } else {   /* the old/current default exten pattern match algorithm */

                /* scan the list trying to match extension and CID */
                eroot = NULL;
                while ( (eroot = ast_walk_context_extensions(tmp, eroot)) ) {
                        int match = extension_match_core(eroot->exten, exten, action);
                        /* 0 on fail, 1 on match, 2 on earlymatch */

                        if (!match || (eroot->matchcid && !matchcid(eroot->cidmatch, callerid)))
                                continue;       /* keep trying */
                        if (match == 2 && action == E_MATCHMORE) {
                                /* We match an extension ending in '!'.
                                 * The decision in this case is final and is NULL (no match).
                                 */
                                return NULL;
                        }
                        /* found entry, now look for the right priority */
                        if (q->status < STATUS_NO_PRIORITY)
                                q->status = STATUS_NO_PRIORITY;
                        e = NULL;
                        if (action == E_FINDLABEL && label ) {
                                if (q->status < STATUS_NO_LABEL)
                                        q->status = STATUS_NO_LABEL;
                                e = ast_hashtab_lookup(eroot->peer_label_table, &pattern);
                        } else {
                                e = ast_hashtab_lookup(eroot->peer_table, &pattern);
                        }
                        if (e) {        /* found a valid match */
                                q->status = STATUS_SUCCESS;
                                q->foundcontext = context;
                                return e;
                        }
                }
        }

        /* Check alternative switches */
        AST_LIST_TRAVERSE(&tmp->alts, sw, list) {
                struct ast_switch *asw = pbx_findswitch(sw->name);
                ast_switch_f *aswf = NULL;
                char *datap;

                if (!asw) {
                        ast_log(LOG_WARNING, "No such switch '%s'\n", sw->name);
                        continue;
                }

                /* Substitute variables now */
                if (sw->eval) {
                        if (!(tmpdata = ast_str_thread_get(&switch_data, 512))) {
                                ast_log(LOG_WARNING, "Can't evaluate switch?!\n");
                              &nb