pbx.c

Go to the documentation of this file.

/*
 * 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"
 
#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/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/hashtab.h"
#include "asterisk/module.h"
#include "asterisk/indications.h"
#include "asterisk/taskprocessor.h"
#include "asterisk/xmldoc.h"
#include "asterisk/astobj2.h"
#include "asterisk/stasis_channels.h"
#include "asterisk/dial.h"
#include "asterisk/vector.h"
#include "pbx_private.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
    <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>
    <manager name="ExtensionStateList" language="en_US">
        <synopsis>
            List the current known extension states.
        </synopsis>
        <syntax>
            <xi:include xpointer="xpointer(/docs/manager[@name='Login']/syntax/parameter[@name='ActionID'])" />
        </syntax>
        <description>
            <para>This will list out all known extension states in a
            sequence of <replaceable>ExtensionStatus</replaceable> events.
            When finished, a <replaceable>ExtensionStateListComplete</replaceable> event
            will be emitted.</para>
        </description>
        <see-also>
            <ref type="manager">ExtensionState</ref>
            <ref type="function">HINT</ref>
            <ref type="function">EXTENSION_STATE</ref>
        </see-also>
        <responses>
            <list-elements>
                <xi:include xpointer="xpointer(/docs/managerEvent[@name='ExtensionStatus'])" />
            </list-elements>
            <managerEvent name="ExtensionStateListComplete" language="en_US">
                <managerEventInstance class="EVENT_FLAG_COMMAND">
                    <synopsis>
                        Indicates the end of the list the current known extension states.
                    </synopsis>
                    <syntax>
                        <parameter name="EventList">
                            <para>Conveys the status of the event list.</para>
                        </parameter>
                        <parameter name="ListItems">
                            <para>Conveys the number of statuses reported.</para>
                        </parameter>
                    </syntax>
                </managerEventInstance>
            </managerEvent>
        </responses>
    </manager>
 ***/
 
#ifdef LOW_MEMORY
#define EXT_DATA_SIZE 256
#else
#define EXT_DATA_SIZE 8192
#endif
 
#define SWITCH_DATA_LENGTH 256
 
#define VAR_NORMAL      1
#define VAR_SOFTTRAN    2
#define VAR_HARDTRAN    3
 
struct ast_context;
struct ast_app;
 
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;            /*!< Clean Extension id */
    char *name;         /*!< Extension name (may include '-' eye candy) */
    int matchcid;           /*!< Match caller id ? */
    const char *cidmatch;       /*!< Caller id to match for this extension */
    const char *cidmatch_display;   /*!< Caller id to match (display version) */
    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 */
    const char *registrar_file;     /*!< File name used to register extension */
    int registrar_line;             /*!< Line number the extension was registered in text */
    struct ast_exten *next;     /*!< Extension with a greater ID */
    char stuff[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 {
    const char *name;
    const char *registrar;
 
    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_includes includes;     /*!< Include other contexts */
    struct ast_ignorepats ignorepats; /*!< Patterns for which to continue playing dialtone */
    struct ast_sws alts;              /*!< Alternative switches */
    int refcount;                     /*!< each module that would have created this context should inc/dec this as appropriate */
    int autohints;                    /*!< Whether autohints support is enabled or not */
 
    /*!
     * Buffer to hold the name & registrar character data.
     *
     * The context name *must* be stored first in this buffer.
     */
    char data[];
};
 
/*! \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. */
 
    AST_VECTOR(, char *) devices; /*!< Devices associated with the hint */
};
 
STASIS_MESSAGE_TYPE_DEFN_LOCAL(hint_change_message_type);
STASIS_MESSAGE_TYPE_DEFN_LOCAL(hint_remove_message_type);
 
#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];
};
 
/*! \brief Container for autohint contexts */
static struct ao2_container *autohints;
 
/*!
 * \brief Structure for dial plan autohints
 */
struct ast_autohint {
    /*! \brief Name of the registrar */
    char *registrar;
    /*! \brief Name of the context */
    char context[1];
};
 
/*!
 * \note Using the device for hash
 */
static int hintdevice_hash_cb(const void *obj, const int flags)
{
    const struct ast_hintdevice *ext;
    const char *key;
 
    switch (flags & OBJ_SEARCH_MASK) {
    case OBJ_SEARCH_KEY:
        key = obj;
        break;
    case OBJ_SEARCH_OBJECT:
        ext = obj;
        key = ext->hintdevice;
        break;
    default:
        ast_assert(0);
        return 0;
    }
 
    return ast_str_case_hash(key);
}
 
/*!
 * \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 *left = obj;
    struct ast_hintdevice *right = arg;
    const char *right_key = arg;
    int cmp;
 
    switch (flags & OBJ_SEARCH_MASK) {
    case OBJ_SEARCH_OBJECT:
        right_key = right->hintdevice;
        /* Fall through */
    case OBJ_SEARCH_KEY:
        cmp = strcasecmp(left->hintdevice, right_key);
        break;
    case OBJ_SEARCH_PARTIAL_KEY:
        /*
        * We could also use a partial key struct containing a length
        * so strlen() does not get called for every comparison instead.
        */
        cmp = strncmp(left->hintdevice, right_key, strlen(right_key));
        break;
    default:
        ast_assert(0);
        cmp = 0;
        break;
    }
    return cmp ? 0 : CMP_MATCH;
}
 
/*!
 * \note Using the context name for hash
 */
static int autohint_hash_cb(const void *obj, const int flags)
{
    const struct ast_autohint *autohint;
    const char *key;
 
    switch (flags & OBJ_SEARCH_MASK) {
    case OBJ_SEARCH_KEY:
        key = obj;
        break;
    case OBJ_SEARCH_OBJECT:
        autohint = obj;
        key = autohint->context;
        break;
    default:
        ast_assert(0);
        return 0;
    }
 
    return ast_str_case_hash(key);
}
 
static int autohint_cmp(void *obj, void *arg, int flags)
{
    struct ast_autohint *left = obj;
    struct ast_autohint *right = arg;
    const char *right_key = arg;
    int cmp;
 
    switch (flags & OBJ_SEARCH_MASK) {
    case OBJ_SEARCH_OBJECT:
        right_key = right->context;
        /* Fall through */
    case OBJ_SEARCH_KEY:
        cmp = strcasecmp(left->context, right_key);
        break;
    case OBJ_SEARCH_PARTIAL_KEY:
        /*
        * We could also use a partial key struct containing a length
        * so strlen() does not get called for every comparison instead.
        */
        cmp = strncmp(left->context, right_key, strlen(right_key));
        break;
    default:
        ast_assert(0);
        cmp = 0;
        break;
    }
    return cmp ? 0 : CMP_MATCH | CMP_STOP;
}
 
/*! \internal \brief \c ao2_callback function to remove hintdevices */
static int hintdevice_remove_cb(void *obj, void *arg, void *data, int flags)
{
    struct ast_hintdevice *candidate = obj;
    char *device = arg;
    struct ast_hint *hint = data;
 
    if (!strcasecmp(candidate->hintdevice, device)
        && candidate->hint == hint) {
        return CMP_MATCH;
    }
    return 0;
}
 
static int remove_hintdevice(struct ast_hint *hint)
{
    while (AST_VECTOR_SIZE(&hint->devices) > 0) {
        char *device = AST_VECTOR_GET(&hint->devices, 0);
 
        ao2_t_callback_data(hintdevices, OBJ_SEARCH_KEY | OBJ_UNLINK | OBJ_NODATA,
            hintdevice_remove_cb, device, hint, "Remove device from container");
        AST_VECTOR_REMOVE_UNORDERED(&hint->devices, 0);
        ast_free(device);
    }
 
    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.
 */
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 = ast_str_buffer(str);
 
    /* Spit on '&' and ',' to handle presence hints as well */
    while ((cur = strsep(&parse, "&,"))) {
        char *device_name;
 
        devicelength = strlen(cur);
        if (!devicelength) {
            continue;
        }
 
        device_name = ast_strdup(cur);
        if (!device_name) {
            return -1;
        }
 
        device = ao2_t_alloc(sizeof(*device) + devicelength, hintdevice_destroy,
            "allocating a hintdevice structure");
        if (!device) {
            ast_free(device_name);
            return -1;
        }
        strcpy(device->hintdevice, cur);
        ao2_ref(hint, +1);
        device->hint = hint;
        if (AST_VECTOR_APPEND(&hint->devices, device_name)) {
            ast_free(device_name);
            ao2_ref(device, -1);
            return -1;
        }
        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 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 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 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, const char *registrar_file, int registrar_line,
    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);
static unsigned int ext_strncpy(char *dst, const char *src, size_t dst_size, int nofluff);
 
/*!
 * \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? */
    /* not sure which side may be using ast_ext_matchcid_types, so check both */
    if (ac->matchcid == AST_EXT_MATCHCID_ANY || bc->matchcid == AST_EXT_MATCHCID_ANY) {
        return 0;
    }
    if (ac->matchcid == AST_EXT_MATCHCID_OFF && bc->matchcid == AST_EXT_MATCHCID_OFF) {
        return 0;
    }
    if (ac->matchcid != bc->matchcid) {
        return 1;
    }
    /* all other cases already disposed of, match now required on callerid string (cidmatch) */
    /* although ast_add_extension2_lockopt() enforces non-zero ptr, caller may not have */
    if (ast_strlen_zero(ac->cidmatch) && ast_strlen_zero(bc->cidmatch)) {
        return 0;
    }
    return strcmp(ac->cidmatch, bc->cidmatch);
}
 
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 == AST_EXT_MATCHCID_ON)
        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, ""));
}
 
static int autofallthrough = 1;
static int extenpatternmatchnew = 0;
static char *overrideswitch = NULL;
 
/*! \brief Subscription for device state change events */
static struct stasis_subscription *device_state_sub;
/*! \brief Subscription for presence state change events */
static struct stasis_subscription *presence_state_sub;
 
AST_MUTEX_DEFINE_STATIC(maxcalllock);
static int countcalls;
static int totalcalls;
 
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 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_EXT_MATCHCID_ON) {
                        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_display);
                    } 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
 
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 traverser 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->name : "", 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->name : "", 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 const char *candidate_exten_advance(const char *str)
{
    str++;
    while (*str == '-') {
        str++;
    }
    return str;
}
 
#define MORE(s) (*candidate_exten_advance(s))
#define ADVANCE(s) candidate_exten_advance(s)
 
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 && !MORE(str)) { /* 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->name);                       \
                                    return; /* the first match, by definition, will be the best, because of the sorted tree */           \
                                }                                                                                                        \
                            }                                                                                                            \
                        }                                                                                                                \
                    }
 
#define NEW_MATCHER_RECURSE            \
                    if (p->next_char && (MORE(str) || (p->next_char->x[0] == '/' && p->next_char->x[1] == 0)                 \
                                               || p->next_char->x[0] == '!')) {                                          \
                        if (MORE(str) || p->next_char->x[0] == '!') {                                                         \
                            new_find_extension(ADVANCE(str), 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->name);                         \
                                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->name :      \
                                       "NULL");                                                                        \
                                return; /* the first match is all we need */                                                 \
                            }                                                                                                \
                        }                                                                                                    \
                    } else if ((p->next_char || action == E_CANMATCH) && !MORE(str)) {                                                                  \
                        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->name);
                        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->name : "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->name);
                        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->name : "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->name : "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");
}
 
#undef MORE
#undef ADVANCE
 
/* 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
}
 
#define MAX_EXTENBUF_SIZE 512
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[MAX_EXTENBUF_SIZE];
    volatile size_t required_space = strlen(e1->exten) + 1;
    struct pattern_node pat_node[2];
 
    if (e1->matchcid) {
        required_space += (strlen(e1->cidmatch) + 2 /* '/' + NULL */);
        if (required_space > MAX_EXTENBUF_SIZE) {
            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 {
        if (required_space > MAX_EXTENBUF_SIZE) {
            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;
        }
        ast_copy_string(extenbuf, e1->exten, required_space);
    }
 
#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->name, e1->name);
                }
                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->name, e1->name);
                }
                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 returns 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);
}
 
static int ext_fluff_count(const char *exten)
{
    int fluff = 0;
 
    if (*exten != '_') {
        /* not a pattern, simple check. */
        while (*exten) {
            if (*exten == '-') {
                fluff++;
            }
            exten++;
        }
 
        return fluff;
    }
 
    /* do pattern check */
    while (*exten) {
        if (*exten == '-') {
            fluff++;
        } else if (*exten == '[') {
            /* skip set, dashes here matter. */
            exten = strchr(exten, ']');
 
            if (!exten) {
                /* we'll end up warning about this later, don't spam logs */
                return fluff;
            }
        }
        exten++;
    }
 
    return fluff;
}
 
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 *extension)
{
    return extension_match_core(pattern, extension, 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 ast_context *ast_context_find(const char *name)
{
    struct ast_context *tmp;
    struct ast_context item = {
        .name = name,
    };
 
    if (!name) {
        return NULL;
    }
    ast_rdlock_contexts();
    if (contexts_table) {
        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_exten pattern = {NULL, };
    struct scoreboard score = {0, };
    struct ast_str *tmpdata = NULL;
    int idx;
 
    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 (%d) exceeded. Too many includes?\n", AST_PBX_MAX_STACK);
        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 */
    for (idx = 0; idx < ast_context_switches_count(tmp); idx++) {
        const struct ast_sw *sw = ast_context_switches_get(tmp, idx);
        struct ast_switch *asw = pbx_findswitch(ast_get_switch_name(sw));
        ast_switch_f *aswf = NULL;
        const char *datap;
 
        if (!asw) {
            ast_log(LOG_WARNING, "No such switch '%s'\n", ast_get_switch_name(sw));
            continue;
        }
 
        /* Substitute variables now */
        if (ast_get_switch_eval(sw)) {
            if (!(tmpdata = ast_str_thread_get(&switch_data, 512))) {
                ast_log(LOG_WARNING, "Can't evaluate switch?!\n");
                continue;
            }
            pbx_substitute_variables_helper(chan, ast_get_switch_data(sw),
                ast_str_buffer(tmpdata), ast_str_size(tmpdata));
            datap = ast_str_buffer(tmpdata);
        } else {
            datap = ast_get_switch_data(sw);
        }
 
        /* 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;
        }
    }
    /* Technically we should be using tmp->name here, but if we used that we
     * would have to cast away the constness of the 'name' pointer and I do
     * not want to do that. */
    q->incstack[q->stacklen++] = tmp->data; /* Setup the stack */
    /* Now try any includes we have in this context */
    for (idx = 0; idx < ast_context_includes_count(tmp); idx++) {
        const struct ast_include *i = ast_context_includes_get(tmp, idx);
 
        if (include_valid(i)) {
            if ((e = pbx_find_extension(chan, bypass, q, include_rname(i), exten, priority, label, callerid, action))) {
#ifdef NEED_DEBUG_HERE
                ast_log(LOG_NOTICE,"Returning recursive match of %s\n", e->exten);
#endif
                return e;
            }
            if (q->swo)
                return NULL;
        }
    }
    return NULL;
}
 
static void exception_store_free(void *data)
{
    struct pbx_exception *exception = data;
    ast_string_field_free_memory(exception);
    ast_free(exception);
}
 
static const struct ast_datastore_info exception_store_info = {
    .type = "EXCEPTION",
    .destroy = exception_store_free,
};
 
/*!
 * \internal
 * \brief Set the PBX to execute the exception extension.
 *
 * \param chan Channel to raise the exception on.
 * \param reason Reason exception is raised.
 * \param priority Dialplan priority to set.
 *
 * \retval 0 on success.
 * \retval -1 on error.
 */
int raise_exception(struct ast_channel *chan, const char *reason, int priority)
{
    struct ast_datastore *ds = ast_channel_datastore_find(chan, &exception_store_info, NULL);
    struct pbx_exception *exception = NULL;
 
    if (!ds) {
        ds = ast_datastore_alloc(&exception_store_info, NULL);
        if (!ds)
            return -1;
        if (!(exception = ast_calloc_with_stringfields(1, struct pbx_exception, 128))) {
            ast_datastore_free(ds);
            return -1;
        }
        ds->data = exception;
        ast_channel_datastore_add(chan, ds);
    } else
        exception = ds->data;
 
    ast_string_field_set(exception, reason, reason);
    ast_string_field_set(exception, context, ast_channel_context(chan));
    ast_string_field_set(exception, exten, ast_channel_exten(chan));
    exception->priority = ast_channel_priority(chan);
    set_ext_pri(chan, "e", priority);
    return 0;
}
 
static int acf_exception_read(struct ast_channel *chan, const char *name, char *data, char *buf, size_t buflen)
{
    struct ast_datastore *ds = ast_channel_datastore_find(chan, &exception_store_info, NULL);
    struct pbx_exception *exception = NULL;
    if (!ds || !ds->data)
        return -1;
    exception = ds->data;
    if (!strcasecmp(data, "REASON"))
        ast_copy_string(buf, exception->reason, buflen);
    else if (!strcasecmp(data, "CONTEXT"))
        ast_copy_string(buf, exception->context, buflen);
    else if (!strncasecmp(data, "EXTEN", 5))
        ast_copy_string(buf, exception->exten, buflen);
    else if (!strcasecmp(data, "PRIORITY"))
        snprintf(buf, buflen, "%d", exception->priority);
    else
        return -1;
    return 0;
}
 
static struct ast_custom_function exception_function = {
    .name = "EXCEPTION",
    .read = acf_exception_read,
};
 
/*!
 * \brief The return value depends on the action:
 *
 * E_MATCH, E_CANMATCH, E_MATCHMORE require a real match,
 *  and return 0 on failure, -1 on match;
 * E_FINDLABEL maps the label to a priority, and returns
 *  the priority on success, ... XXX
 * E_SPAWN, spawn an application,
 *
 * \retval 0 on success.
 * \retval  -1 on failure.
 *
 * \note The channel is auto-serviced in this function, because doing an extension
 * match may block for a long time.  For example, if the lookup has to use a network
 * dialplan switch, such as DUNDi or IAX2, it may take a while.  However, the channel
 * auto-service code will queue up any important signalling frames to be processed
 * after this is done.
 */
static int pbx_extension_helper(struct ast_channel *c, struct ast_context *con,
  const char *context, const char *exten, int priority,
  const char *label, const char *callerid, enum ext_match_t action, int *found, int combined_find_spawn)
{
    struct ast_exten *e;
    struct ast_app *app;
    char *substitute = NULL;
    struct pbx_find_info q = { .stacklen = 0 }; /* the rest is reset in pbx_find_extension */
    char passdata[EXT_DATA_SIZE];
    int matching_action = (action == E_MATCH || action == E_CANMATCH || action == E_MATCHMORE);
 
    ast_rdlock_contexts();
 
    if (!context) {
        context = con->name;
    }
 
    if (found)
        *found = 0;
 
    e = pbx_find_extension(c, con, &q, context, exten, priority, label, callerid, action);
    if (e) {
        if (found)
            *found = 1;
        if (matching_action) {
            ast_unlock_contexts();
            return -1;  /* success, we found it */
        } else if (action == E_FINDLABEL) { /* map the label to a priority */
            int res = e->priority;
 
            ast_unlock_contexts();
 
            /* the priority we were looking for */
            return res;
        } else {    /* spawn */
            if (!e->cached_app)
                e->cached_app = pbx_findapp(e->app);
            app = e->cached_app;
            if (ast_strlen_zero(e->data)) {
                *passdata = '\0';
            } else {
                const char *tmp;
                if ((!(tmp = strchr(e->data, '$'))) || (!strstr(tmp, "${") && !strstr(tmp, "$["))) {
                    /* no variables to substitute, copy on through */
                    ast_copy_string(passdata, e->data, sizeof(passdata));
                } else {
                    /* save e->data on stack for later processing after lock released */
                    substitute = ast_strdupa(e->data);
                }
            }
            ast_unlock_contexts();
            if (!app) {
                ast_log(LOG_WARNING, "No application '%s' for extension (%s, %s, %d)\n", e->app, context, exten, priority);
                return -1;
            }
            if (ast_channel_context(c) != context)
                ast_channel_context_set(c, context);
            if (ast_channel_exten(c) != exten)
                ast_channel_exten_set(c, exten);
            ast_channel_priority_set(c, priority);
            if (substitute) {
                pbx_substitute_variables_helper(c, substitute, passdata, sizeof(passdata)-1);
            }
            ast_debug(1, "Launching '%s'\n", app_name(app));
            if (VERBOSITY_ATLEAST(3)) {
                ast_verb(3, "Executing [%s@%s:%d] " COLORIZE_FMT "(\"" COLORIZE_FMT "\", \"" COLORIZE_FMT "\") %s\n",
                    exten, context, priority,
                    COLORIZE(COLOR_BRCYAN, 0, app_name(app)),
                    COLORIZE(COLOR_BRMAGENTA, 0, ast_channel_name(c)),
                    COLORIZE(COLOR_BRMAGENTA, 0, passdata),
                    "in new stack");
            }
            return pbx_exec(c, app, passdata);  /* 0 on success, -1 on failure */
        }
    } else if (q.swo) { /* not found here, but in another switch */
        if (found)
            *found = 1;
        ast_unlock_contexts();
        if (matching_action) {
            return -1;
        } else {
            if (!q.swo->exec) {
                ast_log(LOG_WARNING, "No execution engine for switch %s\n", q.swo->name);
                return -1;
            }
            return q.swo->exec(c, q.foundcontext ? q.foundcontext : context, exten, priority, callerid, q.data);
        }
    } else {    /* not found anywhere, see what happened */
        ast_unlock_contexts();
        /* Using S_OR here because Solaris doesn't like NULL being passed to ast_log */
        switch (q.status) {
        case STATUS_NO_CONTEXT:
            if (!matching_action && !combined_find_spawn)
                ast_log(LOG_NOTICE, "Cannot find extension context '%s'\n", S_OR(context, ""));
            break;
        case STATUS_NO_EXTENSION:
            if (!matching_action && !combined_find_spawn)
                ast_log(LOG_NOTICE, "Cannot find extension '%s' in context '%s'\n", exten, S_OR(context, ""));
            break;
        case STATUS_NO_PRIORITY:
            if (!matching_action && !combined_find_spawn)
                ast_log(LOG_NOTICE, "No such priority %d in extension '%s' in context '%s'\n", priority, exten, S_OR(context, ""));
            break;
        case STATUS_NO_LABEL:
            if (context && !combined_find_spawn)
                ast_log(LOG_NOTICE, "No such label '%s' in extension '%s' in context '%s'\n", S_OR(label, ""), exten, S_OR(context, ""));
            break;
        default:
            ast_debug(1, "Shouldn't happen!\n");
        }
 
        return (matching_action) ? 0 : -1;
    }
}
 
/*! \brief Find hint for given extension in context */
static struct ast_exten *ast_hint_extension_nolock(struct ast_channel *c, const char *context, const char *exten)
{
    struct pbx_find_info q = { .stacklen = 0 }; /* the rest is set in pbx_find_context */
    return pbx_find_extension(c, NULL, &q, context, exten, PRIORITY_HINT, NULL, "", E_MATCH);
}
 
static struct ast_exten *ast_hint_extension(struct ast_channel *c, const char *context, const char *exten)
{
    struct ast_exten *e;
    ast_rdlock_contexts();
    e = ast_hint_extension_nolock(c, context, exten);
    ast_unlock_contexts();
    return e;
}
 
enum ast_extension_states ast_devstate_to_extenstate(enum ast_device_state devstate)
{
    switch (devstate) {
    case AST_DEVICE_ONHOLD:
        return AST_EXTENSION_ONHOLD;
    case AST_DEVICE_BUSY:
        return AST_EXTENSION_BUSY;
    case AST_DEVICE_UNKNOWN:
        return AST_EXTENSION_NOT_INUSE;
    case AST_DEVICE_UNAVAILABLE:
    case AST_DEVICE_INVALID:
        return AST_EXTENSION_UNAVAILABLE;
    case AST_DEVICE_RINGINUSE:
        return (AST_EXTENSION_INUSE | AST_EXTENSION_RINGING);
    case AST_DEVICE_RINGING:
        return AST_EXTENSION_RINGING;
    case AST_DEVICE_INUSE:
        return AST_EXTENSION_INUSE;
    case AST_DEVICE_NOT_INUSE:
        return AST_EXTENSION_NOT_INUSE;
    case AST_DEVICE_TOTAL: /* not a device state, included for completeness */
        break;
    }
 
    return AST_EXTENSION_NOT_INUSE;
}
 
/*!
 * \internal
 * \brief Parse out the presence portion of the hint string
 */
static char *parse_hint_presence(struct ast_str *hint_args)
{
    char *copy = ast_strdupa(ast_str_buffer(hint_args));
    char *tmp = "";
 
    if ((tmp = strrchr(copy, ','))) {
        *tmp = '\0';
        tmp++;
    } else {
        return NULL;
    }
    ast_str_set(&hint_args, 0, "%s", tmp);
    return ast_str_buffer(hint_args);
}
 
/*!
 * \internal
 * \brief Parse out the device portion of the hint string
 */
static char *parse_hint_device(struct ast_str *hint_args)
{
    char *copy = ast_strdupa(ast_str_buffer(hint_args));
    char *tmp;
 
    if ((tmp = strrchr(copy, ','))) {
        *tmp = '\0';
    }
 
    ast_str_set(&hint_args, 0, "%s", copy);
    return ast_str_buffer(hint_args);
}
 
static void device_state_info_dt(void *obj)
{
    struct ast_device_state_info *info = obj;
 
    ao2_cleanup(info->causing_channel);
}
 
static struct ao2_container *alloc_device_state_info(void)
{
    return ao2_container_alloc_list(AO2_ALLOC_OPT_LOCK_NOLOCK, 0, NULL, NULL);
}
 
static int ast_extension_state3(struct ast_str *hint_app, struct ao2_container *device_state_info)
{
    char *cur;
    char *rest;
    struct ast_devstate_aggregate agg;
 
    /* One or more devices separated with a & character */
    rest = parse_hint_device(hint_app);
 
    ast_devstate_aggregate_init(&agg);
    while ((cur = strsep(&rest, "&"))) {
        enum ast_device_state state = ast_device_state(cur);
 
        ast_devstate_aggregate_add(&agg, state);
        if (device_state_info) {
            struct ast_device_state_info *obj;
 
            obj = ao2_alloc_options(sizeof(*obj) + strlen(cur), device_state_info_dt, AO2_ALLOC_OPT_LOCK_NOLOCK);
            /* if failed we cannot add this device */
            if (obj) {
                obj->device_state = state;
                strcpy(obj->device_name, cur);
                ao2_link(device_state_info, obj);
                ao2_ref(obj, -1);
            }
        }
    }
 
    return ast_devstate_to_extenstate(ast_devstate_aggregate_result(&agg));
}
 
/*! \brief Check state of extension by using hints */
static int ast_extension_state2(struct ast_exten *e, struct ao2_container *device_state_info)
{
    struct ast_str *hint_app = ast_str_thread_get(&extensionstate_buf, 32);
 
    if (!e || !hint_app) {
        return -1;
    }
 
    ast_str_set(&hint_app, 0, "%s", ast_get_extension_app(e));
    return ast_extension_state3(hint_app, device_state_info);
}
 
/*! \brief Return extension_state as string */
const char *ast_extension_state2str(int extension_state)
{
    int i;
 
    for (i = 0; (i < ARRAY_LEN(extension_states)); i++) {
        if (extension_states[i].extension_state == extension_state)
            return extension_states[i].text;
    }
    return "Unknown";
}
 
/*!
 * \internal
 * \brief Check extension state for an extension by using hint
 */
static int internal_extension_state_extended(struct ast_channel *c, const char *context, const char *exten,
    struct ao2_container *device_state_info)
{
    struct ast_exten *e;
 
    if (!(e = ast_hint_extension(c, context, exten))) {  /* Do we have a hint for this extension ? */
        return -1;                   /* No hint, return -1 */
    }
 
    if (e->exten[0] == '_') {
        /* Create this hint on-the-fly, we explicitly lock hints here to ensure the
         * same locking order as if this were done through configuration file - that is
         * hints is locked first and then (if needed) contexts is locked
         */
        ao2_lock(hints);
        ast_add_extension(e->parent->name, 0, exten, e->priority, e->label,
            e->matchcid ? e->cidmatch : NULL, e->app, ast_strdup(e->data), ast_free_ptr,
            e->registrar);
        ao2_unlock(hints);
        if (!(e = ast_hint_extension(c, context, exten))) {
            /* Improbable, but not impossible */
            return -1;
        }
    }
 
    return ast_extension_state2(e, device_state_info);  /* Check all devices in the hint */
}
 
/*! \brief Check extension state for an extension by using hint */
int ast_extension_state(struct ast_channel *c, const char *context, const char *exten)
{
    return internal_extension_state_extended(c, context, exten, NULL);
}
 
/*! \brief Check extended extension state for an extension by using hint */
int ast_extension_state_extended(struct ast_channel *c, const char *context, const char *exten,
    struct ao2_container **device_state_info)
{
    struct ao2_container *container = NULL;
    int ret;
 
    if (device_state_info) {
        container = alloc_device_state_info();
    }
 
    ret = internal_extension_state_extended(c, context, exten, container);
    if (ret < 0 && container) {
        ao2_ref(container, -1);
        container = NULL;
    }
 
    if (device_state_info) {
        get_device_state_causing_channels(container);
        *device_state_info = container;
    }
 
    return ret;
}
 
static int extension_presence_state_helper(struct ast_exten *e, char **subtype, char **message)
{
    struct ast_str *hint_app = ast_str_thread_get(&extensionstate_buf, 32);
    char *presence_provider;
    const char *app;
 
    if (!e || !hint_app) {
        return -1;
    }
 
    app = ast_get_extension_app(e);
    if (ast_strlen_zero(app)) {
        return -1;
    }
 
    ast_str_set(&hint_app, 0, "%s", app);
    presence_provider = parse_hint_presence(hint_app);
 
    if (ast_strlen_zero(presence_provider)) {
        /* No presence string in the hint */
        return 0;
    }
 
    return ast_presence_state(presence_provider, subtype, message);
}
 
int ast_hint_presence_state(struct ast_channel *c, const char *context, const char *exten, char **subtype, char **message)
{
    struct ast_exten *e;
 
    if (!(e = ast_hint_extension(c, context, exten))) {  /* Do we have a hint for this extension ? */
        return -1;                   /* No hint, return -1 */
    }
 
    if (e->exten[0] == '_') {
        /* Create this hint on-the-fly */
        ao2_lock(hints);
        ast_add_extension(e->parent->name, 0, exten, e->priority, e->label,
            e->matchcid ? e->cidmatch : NULL, e->app, ast_strdup(e->data), ast_free_ptr,
            e->registrar);
        ao2_unlock(hints);
        if (!(e = ast_hint_extension(c, context, exten))) {
            /* Improbable, but not impossible */
            return -1;
        }
    }
 
    return extension_presence_state_helper(e, subtype, message);
}
 
static int execute_state_callback(ast_state_cb_type cb,
    const char *context,
    const char *exten,
    void *data,
    enum ast_state_cb_update_reason reason,
    struct ast_hint *hint,
    struct ao2_container *device_state_info)
{
    int res = 0;
    struct ast_state_cb_info info = { 0, };
 
    info.reason = reason;
 
    /* Copy over current hint data */
    if (hint) {
        ao2_lock(hint);
        info.exten_state = hint->laststate;
        info.device_state_info = device_state_info;
        info.presence_state = hint->last_presence_state;
        if (!(ast_strlen_zero(hint->last_presence_subtype))) {
            info.presence_subtype = ast_strdupa(hint->last_presence_subtype);
        } else {
            info.presence_subtype = "";
        }
        if (!(ast_strlen_zero(hint->last_presence_message))) {
            info.presence_message = ast_strdupa(hint->last_presence_message);
        } else {
            info.presence_message = "";
        }
        ao2_unlock(hint);
    } else {
        info.exten_state = AST_EXTENSION_REMOVED;
    }
 
    res = cb(context, exten, &info, data);
 
    return res;
}
 
/*!
 * \internal
 * \brief Identify a channel for every device which is supposedly responsible for the device state.
 *
 * Especially when the device is ringing, the oldest ringing channel is chosen.
 * For all other cases the first encountered channel in the specific state is chosen.
 */
static void get_device_state_causing_channels(struct ao2_container *c)
{
    struct ao2_iterator iter;
    struct ast_device_state_info *info;
    struct ast_channel *chan;
 
    if (!c || !ao2_container_count(c)) {
        return;
    }
    iter = ao2_iterator_init(c, 0);
    for (; (info = ao2_iterator_next(&iter)); ao2_ref(info, -1)) {
        enum ast_channel_state search_state = 0; /* prevent false uninit warning */
        char match[AST_CHANNEL_NAME];
        struct ast_channel_iterator *chan_iter;
        struct timeval chantime = {0, }; /* prevent false uninit warning */
 
        switch (info->device_state) {
        case AST_DEVICE_RINGING:
        case AST_DEVICE_RINGINUSE:
            /* find ringing channel */
            search_state = AST_STATE_RINGING;
            break;
        case AST_DEVICE_BUSY:
            /* find busy channel */
            search_state = AST_STATE_BUSY;
            break;
        case AST_DEVICE_ONHOLD:
        case AST_DEVICE_INUSE:
            /* find up channel */
            search_state = AST_STATE_UP;
            break;
        case AST_DEVICE_UNKNOWN:
        case AST_DEVICE_NOT_INUSE:
        case AST_DEVICE_INVALID:
        case AST_DEVICE_UNAVAILABLE:
        case AST_DEVICE_TOTAL /* not a state */:
            /* no channels are of interest */
            continue;
        }
 
        /* iterate over all channels of the device */
            snprintf(match, sizeof(match), "%s-", info->device_name);
        chan_iter = ast_channel_iterator_by_name_new(match, strlen(match));
        for (; (chan = ast_channel_iterator_next(chan_iter)); ast_channel_unref(chan)) {
            ast_channel_lock(chan);
            /* this channel's state doesn't match */
            if (search_state != ast_channel_state(chan)) {
                ast_channel_unlock(chan);
                continue;
            }
            /* any non-ringing channel will fit */
            if (search_state != AST_STATE_RINGING) {
                ast_channel_unlock(chan);
                info->causing_channel = chan; /* is kept ref'd! */
                break;
            }
            /* but we need the oldest ringing channel of the device to match with undirected pickup */
            if (!info->causing_channel) {
                chantime = ast_channel_creationtime(chan);
                ast_channel_ref(chan); /* must ref it! */
                info->causing_channel = chan;
            } else if (ast_tvcmp(ast_channel_creationtime(chan), chantime) < 0) {
                chantime = ast_channel_creationtime(chan);
                ast_channel_unref(info->causing_channel);
                ast_channel_ref(chan); /* must ref it! */
                info->causing_channel = chan;
            }
            ast_channel_unlock(chan);
        }
        ast_channel_iterator_destroy(chan_iter);
    }
    ao2_iterator_destroy(&iter);
}
 
static void device_state_notify_callbacks(struct ast_hint *hint, struct ast_str **hint_app)
{
    struct ao2_iterator cb_iter;
    struct ast_state_cb *state_cb;
    int state;
    int same_state;
    struct ao2_container *device_state_info;
    int first_extended_cb_call = 1;
    char context_name[AST_MAX_CONTEXT];
    char exten_name[AST_MAX_EXTENSION];
 
    ao2_lock(hint);
    if (!hint->exten) {
        /* The extension has already been destroyed */
        ao2_unlock(hint);
        return;
    }
 
    /*
     * Save off strings in case the hint extension gets destroyed
     * while we are notifying the watchers.
     */
    ast_copy_string(context_name,
            ast_get_context_name(ast_get_extension_context(hint->exten)),
            sizeof(context_name));
    ast_copy_string(exten_name, ast_get_extension_name(hint->exten),
            sizeof(exten_name));
    ast_str_set(hint_app, 0, "%s", ast_get_extension_app(hint->exten));
    ao2_unlock(hint);
 
    /*
     * Get device state for this hint.
     *
     * NOTE: We cannot hold any locks while determining the hint
     * device state or notifying the watchers without causing a
     * deadlock.  (conlock, hints, and hint)
     */
 
    /* Make a container so state3 can fill it if we wish.
     * If that failed we simply do not provide the extended state info.
     */
    device_state_info = alloc_device_state_info();
 
    state = ast_extension_state3(*hint_app, device_state_info);
    same_state = state == hint->laststate;
    if (same_state && (~state & AST_EXTENSION_RINGING)) {
        ao2_cleanup(device_state_info);
        return;
    }
 
    /* Device state changed since last check - notify the watchers. */
    hint->laststate = state;    /* record we saw the change */
 
    /* For general callbacks */
    if (!same_state) {
        cb_iter = ao2_iterator_init(statecbs, 0);
        for (; (state_cb = ao2_iterator_next(&cb_iter)); ao2_ref(state_cb, -1)) {
            execute_state_callback(state_cb->change_cb,
                context_name,
                exten_name,
                state_cb->data,
                AST_HINT_UPDATE_DEVICE,
                hint,
                NULL);
        }
        ao2_iterator_destroy(&cb_iter);
    }
 
    /* For extension callbacks */
    /* extended callbacks are called when the state changed or when AST_STATE_RINGING is
     * included. Normal callbacks are only called when the state changed.
     */
    cb_iter = ao2_iterator_init(hint->callbacks, 0);
    for (; (state_cb = ao2_iterator_next(&cb_iter)); ao2_ref(state_cb, -1)) {
        if (state_cb->extended && first_extended_cb_call) {
            /* Fill detailed device_state_info now that we know it is used by extd. callback */
            first_extended_cb_call = 0;
            get_device_state_causing_channels(device_state_info);
        }
        if (state_cb->extended || !same_state) {
            execute_state_callback(state_cb->change_cb,
                context_name,
                exten_name,
                state_cb->data,
                AST_HINT_UPDATE_DEVICE,
                hint,
                state_cb->extended ? device_state_info : NULL);
        }
    }
    ao2_iterator_destroy(&cb_iter);
 
    ao2_cleanup(device_state_info);
}
 
static void presence_state_notify_callbacks(struct ast_hint *hint, struct ast_str **hint_app,
                        struct ast_presence_state_message *presence_state)
{
    struct ao2_iterator cb_iter;
    struct ast_state_cb *state_cb;
    char context_name[AST_MAX_CONTEXT];
    char exten_name[AST_MAX_EXTENSION];
 
    ao2_lock(hint);
    if (!hint->exten) {
        /* The extension has already been destroyed */
        ao2_unlock(hint);
        return;
    }
 
    /*
     * Save off strings in case the hint extension gets destroyed
     * while we are notifying the watchers.
     */
    ast_copy_string(context_name,
            ast_get_context_name(ast_get_extension_context(hint->exten)),
            sizeof(context_name));
    ast_copy_string(exten_name, ast_get_extension_name(hint->exten),
            sizeof(exten_name));
    ast_str_set(hint_app, 0, "%s", ast_get_extension_app(hint->exten));
    ao2_unlock(hint);
 
    /* Check to see if update is necessary */
    if ((hint->last_presence_state == presence_state->state) &&
        ((hint->last_presence_subtype && presence_state->subtype &&
          !strcmp(hint->last_presence_subtype, presence_state->subtype)) ||
         (!hint->last_presence_subtype && !presence_state->subtype)) &&
        ((hint->last_presence_message && presence_state->message &&
          !strcmp(hint->last_presence_message, presence_state->message)) ||
         (!hint->last_presence_message && !presence_state->message))) {
        /* this update is the same as the last, do nothing */
        return;
    }
 
    /* update new values */
    ast_free(hint->last_presence_subtype);
    ast_free(hint->last_presence_message);
    hint->last_presence_state = presence_state->state;
    hint->last_presence_subtype = presence_state->subtype ? ast_strdup(presence_state->subtype) : NULL;
    hint->last_presence_message = presence_state->message ? ast_strdup(presence_state->message) : NULL;
 
    /* For general callbacks */
    cb_iter = ao2_iterator_init(statecbs, 0);
    for (; (state_cb = ao2_iterator_next(&cb_iter)); ao2_ref(state_cb, -1)) {
        execute_state_callback(state_cb->change_cb,
            context_name,
            exten_name,
            state_cb->data,
            AST_HINT_UPDATE_PRESENCE,
            hint,
            NULL);
    }
    ao2_iterator_destroy(&cb_iter);
 
    /* For extension callbacks */
    cb_iter = ao2_iterator_init(hint->callbacks, 0);
    for (; (state_cb = ao2_iterator_next(&cb_iter)); ao2_cleanup(state_cb)) {
        execute_state_callback(state_cb->change_cb,
            context_name,
            exten_name,
            state_cb->data,
            AST_HINT_UPDATE_PRESENCE,
            hint,
            NULL);
    }
    ao2_iterator_destroy(&cb_iter);
}
 
static int handle_hint_change_message_type(struct stasis_message *msg, enum ast_state_cb_update_reason reason)
{
    struct ast_hint *hint;
    struct ast_str *hint_app;
 
    if (hint_change_message_type() != stasis_message_type(msg)) {
        return 0;
    }
 
    if (!(hint_app = ast_str_create(1024))) {
        return -1;
    }
 
    hint = stasis_message_data(msg);
 
    switch (reason) {
    case AST_HINT_UPDATE_DEVICE:
        device_state_notify_callbacks(hint, &hint_app);
        break;
    case AST_HINT_UPDATE_PRESENCE:
        {
            char *presence_subtype = NULL;
            char *presence_message = NULL;
            int state;
 
            state = extension_presence_state_helper(
                hint->exten, &presence_subtype, &presence_message);
            {
                struct ast_presence_state_message presence_state = {
                    .state = state > 0 ? state : AST_PRESENCE_INVALID,
                    .subtype = presence_subtype,
                    .message = presence_message
                };
 
                presence_state_notify_callbacks(hint, &hint_app, &presence_state);
            }
 
            ast_free(presence_subtype);
            ast_free(presence_message);
        }
        break;
    }
 
    ast_free(hint_app);
    return 1;
}
 
static void device_state_cb(void *unused, struct stasis_subscription *sub, struct stasis_message *msg)
{
    struct ast_device_state_message *dev_state;
    struct ast_str *hint_app;
    struct ast_hintdevice *device;
    struct ast_hintdevice *cmpdevice;
    struct ao2_iterator *dev_iter;
    struct ao2_iterator auto_iter;
    struct ast_autohint *autohint;
    char *virtual_device;
    char *type;
    char *device_name;
 
    if (handle_hint_change_message_type(msg, AST_HINT_UPDATE_DEVICE)) {
        return;
    }
 
    if (hint_remove_message_type() == stasis_message_type(msg)) {
        /* The extension has already been destroyed */
        struct ast_state_cb *state_cb;
        struct ao2_iterator cb_iter;
        struct ast_hint *hint = stasis_message_data(msg);
 
        ao2_lock(hint);
        hint->laststate = AST_EXTENSION_DEACTIVATED;
        ao2_unlock(hint);
 
        cb_iter = ao2_iterator_init(hint->callbacks, 0);
        for (; (state_cb = ao2_iterator_next(&cb_iter)); ao2_ref(state_cb, -1)) {
            execute_state_callback(state_cb->change_cb,
                    hint->context_name,
                    hint->exten_name,
                    state_cb->data,
                    AST_HINT_UPDATE_DEVICE,
                    hint,
                    NULL);
        }
        ao2_iterator_destroy(&cb_iter);
        return;
    }
 
    if (ast_device_state_message_type() != stasis_message_type(msg)) {
        return;
    }
 
    dev_state = stasis_message_data(msg);
    if (dev_state->eid) {
        /* ignore non-aggregate states */
        return;
    }
 
    if (ao2_container_count(hintdevices) == 0 && ao2_container_count(autohints) == 0) {
        /* There are no hints monitoring devices. */
        return;
    }
 
    hint_app = ast_str_create(1024);
    if (!hint_app) {
        return;
    }
 
    cmpdevice = ast_alloca(sizeof(*cmpdevice) + strlen(dev_state->device));
    strcpy(cmpdevice->hintdevice, dev_state->device);
 
    ast_mutex_lock(&context_merge_lock);/* Hold off ast_merge_contexts_and_delete */
 
    /* Initially we find all hints for the device and notify them */
    dev_iter = ao2_t_callback(hintdevices,
        OBJ_SEARCH_OBJECT | OBJ_MULTIPLE,
        hintdevice_cmp_multiple,
        cmpdevice,
        "find devices in container");
    if (dev_iter) {
        for (; (device = ao2_iterator_next(dev_iter)); ao2_t_ref(device, -1, "Next device")) {
            if (device->hint) {
                device_state_notify_callbacks(device->hint, &hint_app);
            }
        }
        ao2_iterator_destroy(dev_iter);
    }
 
    /* Second stage we look for any autohint contexts and if the device is not already in the hints
     * we create it.
     */
    type = ast_strdupa(dev_state->device);
    if (ast_strlen_zero(type)) {
        goto end;
    }
 
    /* Determine if this is a virtual/custom device or a real device */
    virtual_device = strchr(type, ':');
    device_name = strchr(type, '/');
    if (virtual_device && (!device_name || (virtual_device < device_name))) {
        device_name = virtual_device;
    }
 
    /* Invalid device state name - not a virtual/custom device and not a real device */
    if (ast_strlen_zero(device_name)) {
        goto end;
    }
 
    *device_name++ = '\0';
 
    auto_iter = ao2_iterator_init(autohints, 0);
    for (; (autohint = ao2_iterator_next(&auto_iter)); ao2_t_ref(autohint, -1, "Next autohint")) {
        if (ast_get_hint(NULL, 0, NULL, 0, NULL, autohint->context, device_name)) {
            continue;
        }
 
        /* The device has no hint in the context referenced by this autohint so create one */
        ast_add_extension(autohint->context, 0, device_name,
            PRIORITY_HINT, NULL, NULL, dev_state->device,
            ast_strdup(dev_state->device), ast_free_ptr, autohint->registrar);
 
        /* Since this hint was just created there are no watchers, so we don't need to notify anyone */
    }
    ao2_iterator_destroy(&auto_iter);
 
end:
    ast_mutex_unlock(&context_merge_lock);
    ast_free(hint_app);
    return;
}
 
/*!
 * \internal
 * \brief Destroy the given state callback object.
 *
 * \param doomed State callback to destroy.
 */
static void destroy_state_cb(void *doomed)
{
    struct ast_state_cb *state_cb = doomed;
 
    if (state_cb->destroy_cb) {
        state_cb->destroy_cb(state_cb->id, state_cb->data);
    }
}
 
/*!
 * \internal
 * \brief Add watcher for extension states with destructor
 */
static int extension_state_add_destroy(const char *context, const char *exten,
    ast_state_cb_type change_cb, ast_state_cb_destroy_type destroy_cb, void *data, int extended)
{
    struct ast_hint *hint;
    struct ast_state_cb *state_cb;
    struct ast_exten *e;
    int id;
 
    /* If there's no context and extension:  add callback to statecbs list */
    if (!context && !exten) {
        /* Prevent multiple adds from adding the same change_cb at the same time. */
        ao2_lock(statecbs);
 
        /* Remove any existing change_cb. */
        ao2_find(statecbs, change_cb, OBJ_UNLINK | OBJ_NODATA);
 
        /* Now insert the change_cb */
        if (!(state_cb = ao2_alloc(sizeof(*state_cb), destroy_state_cb))) {
            ao2_unlock(statecbs);
            return -1;
        }
        state_cb->id = 0;
        state_cb->change_cb = change_cb;
        state_cb->destroy_cb = destroy_cb;
        state_cb->data = data;
        state_cb->extended = extended;
        ao2_link(statecbs, state_cb);
 
        ao2_ref(state_cb, -1);
        ao2_unlock(statecbs);
        return 0;
    }
 
    if (!context || !exten)
        return -1;
 
    /* This callback type is for only one hint, so get the hint */
    e = ast_hint_extension(NULL, context, exten);
    if (!e) {
        return -1;
    }
 
    /* If this is a pattern, dynamically create a new extension for this
     * particular match.  Note that this will only happen once for each
     * individual extension, because the pattern will no longer match first.
     */
    if (e->exten[0] == '_') {
        ao2_lock(hints);
        ast_add_extension(e->parent->name, 0, exten, e->priority, e->label,
            e->matchcid ? e->cidmatch : NULL, e->app, ast_strdup(e->data), ast_free_ptr,
            e->registrar);
        ao2_unlock(hints);
        e = ast_hint_extension(NULL, context, exten);
        if (!e || e->exten[0] == '_') {
            return -1;
        }
    }
 
    /* Find the hint in the hints container */
    ao2_lock(hints);/* Locked to hold off ast_merge_contexts_and_delete */
    hint = ao2_find(hints, e, 0);
    if (!hint) {
        ao2_unlock(hints);
        return -1;
    }
 
    /* Now insert the callback in the callback list  */
    if (!(state_cb = ao2_alloc(sizeof(*state_cb), destroy_state_cb))) {
        ao2_ref(hint, -1);
        ao2_unlock(hints);
        return -1;
    }
    do {
        id = stateid++;     /* Unique ID for this callback */
        /* Do not allow id to ever be -1 or 0. */
    } while (id == -1 || id == 0);
    state_cb->id = id;
    state_cb->change_cb = change_cb;    /* Pointer to callback routine */
    state_cb->destroy_cb = destroy_cb;
    state_cb->data = data;      /* Data for the callback */
    state_cb->extended = extended;
    ao2_link(hint->callbacks, state_cb);
 
    ao2_ref(state_cb, -1);
    ao2_ref(hint, -1);
    ao2_unlock(hints);
 
    return id;
}
 
int ast_extension_state_add_destroy(const char *context, const char *exten,
    ast_state_cb_type change_cb, ast_state_cb_destroy_type destroy_cb, void *data)
{
    return extension_state_add_destroy(context, exten, change_cb, destroy_cb, data, 0);
}
 
int ast_extension_state_add(const char *context, const char *exten,
    ast_state_cb_type change_cb, void *data)
{
    return extension_state_add_destroy(context, exten, change_cb, NULL, data, 0);
}
 
int ast_extension_state_add_destroy_extended(const char *context, const char *exten,
    ast_state_cb_type change_cb, ast_state_cb_destroy_type destroy_cb, void *data)
{
    return extension_state_add_destroy(context, exten, change_cb, destroy_cb, data, 1);
}
 
int ast_extension_state_add_extended(const char *context, const char *exten,
    ast_state_cb_type change_cb, void *data)
{
    return extension_state_add_destroy(context, exten, change_cb, NULL, data, 1);
}
 
/*! \brief Find Hint by callback id */
static int find_hint_by_cb_id(void *obj, void *arg, int flags)
{
    struct ast_state_cb *state_cb;
    const struct ast_hint *hint = obj;
    int *id = arg;
 
    if ((state_cb = ao2_find(hint->callbacks, id, 0))) {
        ao2_ref(state_cb, -1);
        return CMP_MATCH | CMP_STOP;
    }
 
    return 0;
}
 
int ast_extension_state_del(int id, ast_state_cb_type change_cb)
{
    struct ast_state_cb *p_cur;
    int ret = -1;
 
    if (!id) {  /* id == 0 is a callback without extension */
        if (!change_cb) {
            return ret;
        }
        p_cur = ao2_find(statecbs, change_cb, OBJ_UNLINK);
        if (p_cur) {
            ret = 0;
            ao2_ref(p_cur, -1);
        }
    } else { /* callback with extension, find the callback based on ID */
        struct ast_hint *hint;
 
        ao2_lock(hints);/* Locked to hold off ast_merge_contexts_and_delete */
        hint = ao2_callback(hints, 0, find_hint_by_cb_id, &id);
        if (hint) {
            p_cur = ao2_find(hint->callbacks, &id, OBJ_UNLINK);
            if (p_cur) {
                ret = 0;
                ao2_ref(p_cur, -1);
            }
            ao2_ref(hint, -1);
        }
        ao2_unlock(hints);
    }
 
    return ret;
}
 
static int hint_id_cmp(void *obj, void *arg, int flags)
{
    const struct ast_state_cb *cb = obj;
    int *id = arg;
 
    return (cb->id == *id) ? CMP_MATCH | CMP_STOP : 0;
}
 
/*!
 * \internal
 * \brief Destroy the given hint object.
 *
 * \param obj Hint to destroy.
 */
static void destroy_hint(void *obj)
{
    struct ast_hint *hint = obj;
    int i;
 
    ao2_cleanup(hint->callbacks);
 
    for (i = 0; i < AST_VECTOR_SIZE(&hint->devices); i++) {
        char *device = AST_VECTOR_GET(&hint->devices, i);
        ast_free(device);
    }
    AST_VECTOR_FREE(&hint->devices);
    ast_free(hint->last_presence_subtype);
    ast_free(hint->last_presence_message);
}
 
/*! \brief Publish a hint removed event  */
static int publish_hint_remove(struct ast_hint *hint)
{
    struct stasis_message *message;
 
    if (!hint_remove_message_type()) {
        return -1;
    }
 
    if (!(message = stasis_message_create(hint_remove_message_type(), hint))) {
        ao2_ref(hint, -1);
        return -1;
    }
 
    stasis_publish(ast_device_state_topic_all(), message);
 
    ao2_ref(message, -1);
 
    return 0;
}
 
/*! \brief Remove hint from extension */
static int ast_remove_hint(struct ast_exten *e)
{
    /* Cleanup the Notifys if hint is removed */
    struct ast_hint *hint;
 
    if (!e) {
        return -1;
    }
 
    hint = ao2_find(hints, e, OBJ_UNLINK);
    if (!hint) {
        return -1;
    }
 
    remove_hintdevice(hint);
 
    /*
     * The extension is being destroyed so we must save some
     * information to notify that the extension is deactivated.
     */
    ao2_lock(hint);
    ast_copy_string(hint->context_name,
        ast_get_context_name(ast_get_extension_context(hint->exten)),
        sizeof(hint->context_name));
    ast_copy_string(hint->exten_name, ast_get_extension_name(hint->exten),
        sizeof(hint->exten_name));
    hint->exten = NULL;
    ao2_unlock(hint);
 
    publish_hint_remove(hint);
 
    ao2_ref(hint, -1);
 
    return 0;
}
 
/*! \brief Add hint to hint list, check initial extension state */
static int ast_add_hint(struct ast_exten *e)
{
    struct ast_hint *hint_new;
    struct ast_hint *hint_found;
    char *message = NULL;
    char *subtype = NULL;
    int presence_state;
 
    if (!e) {
        return -1;
    }
 
    /*
     * We must create the hint we wish to add before determining if
     * it is already in the hints container to avoid possible
     * deadlock when getting the current extension state.
     */
    hint_new = ao2_alloc(sizeof(*hint_new), destroy_hint);
    if (!hint_new) {
        return -1;
    }
    AST_VECTOR_INIT(&hint_new->devices, 8);
 
    /* Initialize new hint. */
    hint_new->callbacks = ao2_container_alloc_list(AO2_ALLOC_OPT_LOCK_MUTEX, 0, NULL, hint_id_cmp);
    if (!hint_new->callbacks) {
        ao2_ref(hint_new, -1);
        return -1;
    }
    hint_new->exten = e;
    if (strstr(e->app, "${") && e->exten[0] == '_') {
        /* The hint is dynamic and hasn't been evaluated yet */
        hint_new->laststate = AST_DEVICE_INVALID;
        hint_new->last_presence_state = AST_PRESENCE_INVALID;
    } else {
        hint_new->laststate = ast_extension_state2(e, NULL);
        if ((presence_state = extension_presence_state_helper(e, &subtype, &message)) > 0) {
            hint_new->last_presence_state = presence_state;
            hint_new->last_presence_subtype = subtype;
            hint_new->last_presence_message = message;
        }
    }
 
    /* Prevent multiple add hints from adding the same hint at the same time. */
    ao2_lock(hints);
 
    /* Search if hint exists, do nothing */
    hint_found = ao2_find(hints, e, 0);
    if (hint_found) {
        ao2_ref(hint_found, -1);
        ao2_unlock(hints);
        ao2_ref(hint_new, -1);
        ast_debug(2, "HINTS: Not re-adding existing hint %s: %s\n",
            ast_get_extension_name(e), ast_get_extension_app(e));
        return -1;
    }
 
    /* Add new hint to the hints container */
    ast_debug(2, "HINTS: Adding hint %s: %s\n",
        ast_get_extension_name(e), ast_get_extension_app(e));
    ao2_link(hints, hint_new);
    if (add_hintdevice(hint_new, ast_get_extension_app(e))) {
        ast_log(LOG_WARNING, "Could not add devices for hint: %s@%s.\n",
            ast_get_extension_name(e),
            ast_get_context_name(ast_get_extension_context(e)));
    }
 
    /* if not dynamic */
    if (!(strstr(e->app, "${") && e->exten[0] == '_')) {
        struct ast_state_cb *state_cb;
        struct ao2_iterator cb_iter;
 
        /* For general callbacks */
        cb_iter = ao2_iterator_init(statecbs, 0);
        for (; (state_cb = ao2_iterator_next(&cb_iter)); ao2_ref(state_cb, -1)) {
            execute_state_callback(state_cb->change_cb,
                ast_get_context_name(ast_get_extension_context(e)),
                ast_get_extension_name(e),
                state_cb->data,
                AST_HINT_UPDATE_DEVICE,
                hint_new,
                NULL);
        }
        ao2_iterator_destroy(&cb_iter);
    }
    ao2_unlock(hints);
    ao2_ref(hint_new, -1);
 
    return 0;
}
 
/*! \brief Publish a hint changed event  */
static int publish_hint_change(struct ast_hint *hint, struct ast_exten *ne)
{
    struct stasis_message *message;
 
    if (!hint_change_message_type()) {
        return -1;
    }
 
    if (!(message = stasis_message_create(hint_change_message_type(), hint))) {
        ao2_ref(hint, -1);
        return -1;
    }
 
    stasis_publish(ast_device_state_topic_all(), message);
    stasis_publish(ast_presence_state_topic_all(), message);
 
    ao2_ref(message, -1);
 
    return 0;
}
 
/*! \brief Change hint for an extension */
static int ast_change_hint(struct ast_exten *oe, struct ast_exten *ne)
{
    struct ast_hint *hint;
 
    if (!oe || !ne) {
        return -1;
    }
 
    ao2_lock(hints);/* Locked to hold off others while we move the hint around. */
 
    /*
     * Unlink the hint from the hints container as the extension
     * name (which is the hash value) could change.
     */
    hint = ao2_find(hints, oe, OBJ_UNLINK);
    if (!hint) {
        ao2_unlock(hints);
        ast_mutex_unlock(&context_merge_lock);
        return -1;
    }
 
    remove_hintdevice(hint);
 
    /* Update the hint and put it back in the hints container. */
    ao2_lock(hint);
    hint->exten = ne;
 
    ao2_unlock(hint);
 
    ao2_link(hints, hint);
    if (add_hintdevice(hint, ast_get_extension_app(ne))) {
        ast_log(LOG_WARNING, "Could not add devices for hint: %s@%s.\n",
            ast_get_extension_name(ne),
            ast_get_context_name(ast_get_extension_context(ne)));
    }
    ao2_unlock(hints);
 
    publish_hint_change(hint, ne);
 
    ao2_ref(hint, -1);
 
    return 0;
}
 
/*! \brief Get hint for channel */
int ast_get_hint(char *hint, int hintsize, char *name, int namesize, struct ast_channel *c, const char *context, const char *exten)
{
    struct ast_exten *e = ast_hint_extension(c, context, exten);
 
    if (e) {
        if (hint)
            ast_copy_string(hint, ast_get_extension_app(e), hintsize);
        if (name) {
            const char *tmp = ast_get_extension_app_data(e);
            if (tmp)
                ast_copy_string(name, tmp, namesize);
        }
        return -1;
    }
    return 0;
}
 
/*! \brief Get hint for channel */
int ast_str_get_hint(struct ast_str **hint, ssize_t hintsize, struct ast_str **name, ssize_t namesize, struct ast_channel *c, const char *context, const char *exten)
{
    struct ast_exten *e = ast_hint_extension(c, context, exten);
 
    if (!e) {
        return 0;
    }
 
    if (hint) {
        ast_str_set(hint, hintsize, "%s", ast_get_extension_app(e));
    }
    if (name) {
        const char *tmp = ast_get_extension_app_data(e);
        if (tmp) {
            ast_str_set(name, namesize, "%s", tmp);
        }
    }
    return -1;
}
 
int ast_exists_extension(struct ast_channel *c, const char *context, const char *exten, int priority, const char *callerid)
{
    return pbx_extension_helper(c, NULL, context, exten, priority, NULL, callerid, E_MATCH, 0, 0);
}
 
int ast_findlabel_extension(struct ast_channel *c, const char *context, const char *exten, const char *label, const char *callerid)
{
    return pbx_extension_helper(c, NULL, context, exten, 0, label, callerid, E_FINDLABEL, 0, 0);
}
 
int ast_findlabel_extension2(struct ast_channel *c, struct ast_context *con, const char *exten, const char *label, const char *callerid)
{
    return pbx_extension_helper(c, con, NULL, exten, 0, label, callerid, E_FINDLABEL, 0, 0);
}
 
int ast_canmatch_extension(struct ast_channel *c, const char *context, const char *exten, int priority, const char *callerid)
{
    return pbx_extension_helper(c, NULL, context, exten, priority, NULL, callerid, E_CANMATCH, 0, 0);
}
 
int ast_matchmore_extension(struct ast_channel *c, const char *context, const char *exten, int priority, const char *callerid)
{
    return pbx_extension_helper(c, NULL, context, exten, priority, NULL, callerid, E_MATCHMORE, 0, 0);
}
 
int ast_spawn_extension(struct ast_channel *c, const char *context, const char *exten, int priority, const char *callerid, int *found, int combined_find_spawn)
{
    return pbx_extension_helper(c, NULL, context, exten, priority, NULL, callerid, E_SPAWN, found, combined_find_spawn);
}
 
void ast_pbx_h_exten_run(struct ast_channel *chan, const char *context)
{
    int autoloopflag;
    int found;
    int spawn_error;
 
    ast_channel_lock(chan);
 
    /*
     * Make sure that the channel is marked as hungup since we are
     * going to run the h exten on it.
     */
    ast_softhangup_nolock(chan, AST_SOFTHANGUP_HANGUP_EXEC);
 
    /* Set h exten location */
    if (context != ast_channel_context(chan)) {
        ast_channel_context_set(chan, context);
    }
    ast_channel_exten_set(chan, "h");
    ast_channel_priority_set(chan, 1);
 
    /* Save autoloop flag */
    autoloopflag = ast_test_flag(ast_channel_flags(chan), AST_FLAG_IN_AUTOLOOP);
    ast_set_flag(ast_channel_flags(chan), AST_FLAG_IN_AUTOLOOP);
    ast_channel_unlock(chan);
 
    for (;;) {
        spawn_error = ast_spawn_extension(chan, ast_channel_context(chan),
            ast_channel_exten(chan), ast_channel_priority(chan),
            S_COR(ast_channel_caller(chan)->id.number.valid,
                ast_channel_caller(chan)->id.number.str, NULL), &found, 1);
 
        ast_channel_lock(chan);
        if (spawn_error) {
            /* The code after the loop needs the channel locked. */
            break;
        }
        ast_channel_priority_set(chan, ast_channel_priority(chan) + 1);
        ast_channel_unlock(chan);
    }
    if (found && spawn_error) {
        /* Something bad happened, or a hangup has been requested. */
        ast_debug(1, "Spawn extension (%s,%s,%d) exited non-zero on '%s'\n",
            ast_channel_context(chan), ast_channel_exten(chan),
            ast_channel_priority(chan), ast_channel_name(chan));
        ast_verb(2, "Spawn extension (%s, %s, %d) exited non-zero on '%s'\n",
            ast_channel_context(chan), ast_channel_exten(chan),
            ast_channel_priority(chan), ast_channel_name(chan));
    }
 
    /* An "h" exten has been run, so indicate that one has been run. */
    ast_set_flag(ast_channel_flags(chan), AST_FLAG_BRIDGE_HANGUP_RUN);
 
    /* Restore autoloop flag */
    ast_set2_flag(ast_channel_flags(chan), autoloopflag, AST_FLAG_IN_AUTOLOOP);
    ast_channel_unlock(chan);
}
 
/*! helper function to set extension and priority */
void set_ext_pri(struct ast_channel *c, const char *exten, int pri)
{
    ast_channel_lock(c);
    ast_channel_exten_set(c, exten);
    ast_channel_priority_set(c, pri);
    ast_channel_unlock(c);
}
 
/*!
 * \brief collect digits from the channel into the buffer.
 * \param c, buf, buflen, pos
 * \param waittime is in milliseconds
 * \retval 0 on timeout or done.
 * \retval -1 on error.
*/
static int collect_digits(struct ast_channel *c, int waittime, char *buf, int buflen, int pos)
{
    int digit;
 
    buf[pos] = '\0';    /* make sure it is properly terminated */
    while (ast_matchmore_extension(c, ast_channel_context(c), buf, 1,
        S_COR(ast_channel_caller(c)->id.number.valid, ast_channel_caller(c)->id.number.str, NULL))) {
        /* As long as we're willing to wait, and as long as it's not defined,
           keep reading digits until we can't possibly get a right answer anymore.  */
        digit = ast_waitfordigit(c, waittime);
        if (ast_channel_softhangup_internal_flag(c) & AST_SOFTHANGUP_ASYNCGOTO) {
            ast_channel_clear_softhangup(c, AST_SOFTHANGUP_ASYNCGOTO);
        } else {
            if (!digit) /* No entry */
                break;
            if (digit < 0)  /* Error, maybe a  hangup */
                return -1;
            if (pos < buflen - 1) { /* XXX maybe error otherwise ? */
                buf[pos++] = digit;
                buf[pos] = '\0';
            }
            waittime = ast_channel_pbx(c)->dtimeoutms;
        }
    }
    return 0;
}
 
static enum ast_pbx_result __ast_pbx_run(struct ast_channel *c,
        struct ast_pbx_args *args)
{
    int found = 0;  /* set if we find at least one match */
    int res = 0;
    int autoloopflag;
    int error = 0;      /* set an error conditions */
    struct ast_pbx *pbx;
    ast_callid callid;
 
    /* A little initial setup here */
    if (ast_channel_pbx(c)) {
        ast_log(LOG_WARNING, "%s already has PBX structure??\n", ast_channel_name(c));
        /* XXX and now what ? */
        ast_free(ast_channel_pbx(c));
    }
    if (!(pbx = ast_calloc(1, sizeof(*pbx)))) {
        return AST_PBX_FAILED;
    }
 
    callid = ast_read_threadstorage_callid();
    /* If the thread isn't already associated with a callid, we should create that association. */
    if (!callid) {
        /* Associate new PBX thread with the channel call id if it is availble.
         * If not, create a new one instead.
         */
        callid = ast_channel_callid(c);
        if (!callid) {
            callid = ast_create_callid();
            if (callid) {
                ast_channel_lock(c);
                ast_channel_callid_set(c, callid);
                ast_channel_unlock(c);
            }
        }
        ast_callid_threadassoc_add(callid);
        callid = 0;
    }
 
    ast_channel_pbx_set(c, pbx);
    /* Set reasonable defaults */
    ast_channel_pbx(c)->rtimeoutms = 10000;
    ast_channel_pbx(c)->dtimeoutms = 5000;
 
    ast_channel_lock(c);
    autoloopflag = ast_test_flag(ast_channel_flags(c), AST_FLAG_IN_AUTOLOOP);   /* save value to restore at the end */
    ast_set_flag(ast_channel_flags(c), AST_FLAG_IN_AUTOLOOP);
    ast_channel_unlock(c);
 
    if (ast_strlen_zero(ast_channel_exten(c))) {
        /* If not successful fall back to 's' - but only if there is no given exten  */
        ast_verb(2, "Starting %s at %s,%s,%d failed so falling back to exten 's'\n", ast_channel_name(c), ast_channel_context(c), ast_channel_exten(c), ast_channel_priority(c));
        /* XXX the original code used the existing priority in the call to
         * ast_exists_extension(), and reset it to 1 afterwards.
         * I believe the correct thing is to set it to 1 immediately.
        */
        set_ext_pri(c, "s", 1);
    }
 
    for (;;) {
        char dst_exten[256];    /* buffer to accumulate digits */
        int pos = 0;        /* XXX should check bounds */
        int digit = 0;
        int invalid = 0;
        int timeout = 0;
 
        /* No digits pressed yet */
        dst_exten[pos] = '\0';
 
        /* loop on priorities in this context/exten */
        while (!(res = ast_spawn_extension(c, ast_channel_context(c), ast_channel_exten(c), ast_channel_priority(c),
            S_COR(ast_channel_caller(c)->id.number.valid, ast_channel_caller(c)->id.number.str, NULL),
            &found, 1))) {
 
            if (!ast_check_hangup(c)) {
                ast_channel_priority_set(c, ast_channel_priority(c) + 1);
                continue;
            }
 
            /* Check softhangup flags. */
            if (ast_channel_softhangup_internal_flag(c) & AST_SOFTHANGUP_ASYNCGOTO) {
                ast_channel_clear_softhangup(c, AST_SOFTHANGUP_ASYNCGOTO);
                continue;
            }
            if (ast_channel_softhangup_internal_flag(c) & AST_SOFTHANGUP_TIMEOUT) {
                if (ast_exists_extension(c, ast_channel_context(c), "T", 1,
                    S_COR(ast_channel_caller(c)->id.number.valid, ast_channel_caller(c)->id.number.str, NULL))) {
                    set_ext_pri(c, "T", 1);
                    /* If the AbsoluteTimeout is not reset to 0, we'll get an infinite loop */
                    memset(ast_channel_whentohangup(c), 0, sizeof(*ast_channel_whentohangup(c)));
                    ast_channel_clear_softhangup(c, AST_SOFTHANGUP_TIMEOUT);
                    continue;
                } else if (ast_exists_extension(c, ast_channel_context(c), "e", 1,
                    S_COR(ast_channel_caller(c)->id.number.valid, ast_channel_caller(c)->id.number.str, NULL))) {
                    raise_exception(c, "ABSOLUTETIMEOUT", 1);
                    /* If the AbsoluteTimeout is not reset to 0, we'll get an infinite loop */
                    memset(ast_channel_whentohangup(c), 0, sizeof(*ast_channel_whentohangup(c)));
                    ast_channel_clear_softhangup(c, AST_SOFTHANGUP_TIMEOUT);
                    continue;
                }
 
                /* Call timed out with no special extension to jump to. */
                error = 1;
                break;
            }
            ast_debug(1, "Extension %s, priority %d returned normally even though call was hung up\n",
                ast_channel_exten(c), ast_channel_priority(c));
            error = 1;
            break;
        } /* end while  - from here on we can use 'break' to go out */
        if (found && res) {
            /* Something bad happened, or a hangup has been requested. */
            if (strchr("0123456789ABCDEF*#", res)) {
                ast_debug(1, "Oooh, got something to jump out with ('%c')!\n", res);
                pos = 0;
                dst_exten[pos++] = digit = res;
                dst_exten[pos] = '\0';
            } else if (res == AST_PBX_INCOMPLETE) {
                ast_debug(1, "Spawn extension (%s,%s,%d) exited INCOMPLETE on '%s'\n", ast_channel_context(c), ast_channel_exten(c), ast_channel_priority(c), ast_channel_name(c));
                ast_verb(2, "Spawn extension (%s, %s, %d) exited INCOMPLETE on '%s'\n", ast_channel_context(c), ast_channel_exten(c), ast_channel_priority(c), ast_channel_name(c));
 
                /* Don't cycle on incomplete - this will happen if the only extension that matches is our "incomplete" extension */
                if (!ast_matchmore_extension(c, ast_channel_context(c), ast_channel_exten(c), 1,
                    S_COR(ast_channel_caller(c)->id.number.valid, ast_channel_caller(c)->id.number.str, NULL))) {
                    invalid = 1;
                } else {
                    ast_copy_string(dst_exten, ast_channel_exten(c), sizeof(dst_exten));
                    digit = 1;
                    pos = strlen(dst_exten);
                }
            } else {
                ast_debug(1, "Spawn extension (%s,%s,%d) exited non-zero on '%s'\n", ast_channel_context(c), ast_channel_exten(c), ast_channel_priority(c), ast_channel_name(c));
                ast_verb(2, "Spawn extension (%s, %s, %d) exited non-zero on '%s'\n", ast_channel_context(c), ast_channel_exten(c), ast_channel_priority(c), ast_channel_name(c));
 
                if ((res == AST_PBX_ERROR)
                    && ast_exists_extension(c, ast_channel_context(c), "e", 1,
                        S_COR(ast_channel_caller(c)->id.number.valid, ast_channel_caller(c)->id.number.str, NULL))) {
                    /* if we are already on the 'e' exten, don't jump to it again */
                    if (!strcmp(ast_channel_exten(c), "e")) {
                        ast_verb(2, "Spawn extension (%s, %s, %d) exited ERROR while already on 'e' exten on '%s'\n", ast_channel_context(c), ast_channel_exten(c), ast_channel_priority(c), ast_channel_name(c));
                        error = 1;
                    } else {
                        raise_exception(c, "ERROR", 1);
                        continue;
                    }
                }
 
                if (ast_channel_softhangup_internal_flag(c) & AST_SOFTHANGUP_ASYNCGOTO) {
                    ast_channel_clear_softhangup(c, AST_SOFTHANGUP_ASYNCGOTO);
                    continue;
                }
                if (ast_channel_softhangup_internal_flag(c) & AST_SOFTHANGUP_TIMEOUT) {
                    if (ast_exists_extension(c, ast_channel_context(c), "T", 1,
                        S_COR(ast_channel_caller(c)->id.number.valid, ast_channel_caller(c)->id.number.str, NULL))) {
                        set_ext_pri(c, "T", 1);
                        /* If the AbsoluteTimeout is not reset to 0, we'll get an infinite loop */
                        memset(ast_channel_whentohangup(c), 0, sizeof(*ast_channel_whentohangup(c)));
                        ast_channel_clear_softhangup(c, AST_SOFTHANGUP_TIMEOUT);
                        continue;
                    } else if (ast_exists_extension(c, ast_channel_context(c), "e", 1,
                        S_COR(ast_channel_caller(c)->id.number.valid, ast_channel_caller(c)->id.number.str, NULL))) {
                        raise_exception(c, "ABSOLUTETIMEOUT", 1);
                        /* If the AbsoluteTimeout is not reset to 0, we'll get an infinite loop */
                        memset(ast_channel_whentohangup(c), 0, sizeof(*ast_channel_whentohangup(c)));
                        ast_channel_clear_softhangup(c, AST_SOFTHANGUP_TIMEOUT);
                        continue;
                    }
                    /* Call timed out with no special extension to jump to. */
                }
                error = 1;
                break;
            }
        }
        if (error)
            break;
 
        /*!\note
         * We get here on a failure of some kind:  non-existing extension or
         * hangup.  We have options, here.  We can either catch the failure
         * and continue, or we can drop out entirely. */
 
        if (invalid
            || (ast_strlen_zero(dst_exten) &&
                !ast_exists_extension(c, ast_channel_context(c), ast_channel_exten(c), 1,
                S_COR(ast_channel_caller(c)->id.number.valid, ast_channel_caller(c)->id.number.str, NULL)))) {
            /*!\note
             * If there is no match at priority 1, it is not a valid extension anymore.
             * Try to continue at "i" (for invalid) or "e" (for exception) or exit if
             * neither exist.
             */
            if (ast_exists_extension(c, ast_channel_context(c), "i", 1,
                S_COR(ast_channel_caller(c)->id.number.valid, ast_channel_caller(c)->id.number.str, NULL))) {
                ast_verb(3, "Channel '%s' sent to invalid extension: context,exten,priority=%s,%s,%d\n",
                    ast_channel_name(c), ast_channel_context(c), ast_channel_exten(c), ast_channel_priority(c));
                pbx_builtin_setvar_helper(c, "INVALID_EXTEN", ast_channel_exten(c));
                set_ext_pri(c, "i", 1);
            } else if (ast_exists_extension(c, ast_channel_context(c), "e", 1,
                S_COR(ast_channel_caller(c)->id.number.valid, ast_channel_caller(c)->id.number.str, NULL))) {
                raise_exception(c, "INVALID", 1);
            } else {
                ast_log(LOG_WARNING, "Channel '%s' sent to invalid extension but no invalid handler: context,exten,priority=%s,%s,%d\n",
                    ast_channel_name(c), ast_channel_context(c), ast_channel_exten(c)