pbx: Create pbx_ignorepat.c for management of 'struct ast_ignorepat'.
[asterisk/asterisk.git] / main / pbx.c
1 /*
2  * Asterisk -- An open source telephony toolkit.
3  *
4  * Copyright (C) 1999 - 2008, Digium, Inc.
5  *
6  * Mark Spencer <markster@digium.com>
7  *
8  * See http://www.asterisk.org for more information about
9  * the Asterisk project. Please do not directly contact
10  * any of the maintainers of this project for assistance;
11  * the project provides a web site, mailing lists and IRC
12  * channels for your use.
13  *
14  * This program is free software, distributed under the terms of
15  * the GNU General Public License Version 2. See the LICENSE file
16  * at the top of the source tree.
17  */
18
19 /*! \file
20  *
21  * \brief Core PBX routines.
22  *
23  * \author Mark Spencer <markster@digium.com>
24  */
25
26 /*** MODULEINFO
27         <support_level>core</support_level>
28  ***/
29
30 #include "asterisk.h"
31
32 ASTERISK_REGISTER_FILE()
33
34 #include "asterisk/_private.h"
35 #include "asterisk/paths.h"     /* use ast_config_AST_SYSTEM_NAME */
36 #include <ctype.h>
37 #include <time.h>
38 #include <sys/time.h>
39 #if defined(HAVE_SYSINFO)
40 #include <sys/sysinfo.h>
41 #endif
42 #if defined(SOLARIS)
43 #include <sys/loadavg.h>
44 #endif
45
46 #include "asterisk/lock.h"
47 #include "asterisk/cli.h"
48 #include "asterisk/pbx.h"
49 #include "asterisk/channel.h"
50 #include "asterisk/file.h"
51 #include "asterisk/callerid.h"
52 #include "asterisk/cdr.h"
53 #include "asterisk/config.h"
54 #include "asterisk/term.h"
55 #include "asterisk/time.h"
56 #include "asterisk/manager.h"
57 #include "asterisk/ast_expr.h"
58 #include "asterisk/linkedlists.h"
59 #define SAY_STUBS       /* generate declarations and stubs for say methods */
60 #include "asterisk/say.h"
61 #include "asterisk/utils.h"
62 #include "asterisk/causes.h"
63 #include "asterisk/musiconhold.h"
64 #include "asterisk/app.h"
65 #include "asterisk/devicestate.h"
66 #include "asterisk/presencestate.h"
67 #include "asterisk/hashtab.h"
68 #include "asterisk/module.h"
69 #include "asterisk/indications.h"
70 #include "asterisk/taskprocessor.h"
71 #include "asterisk/xmldoc.h"
72 #include "asterisk/astobj2.h"
73 #include "asterisk/stasis_channels.h"
74 #include "asterisk/dial.h"
75 #include "asterisk/vector.h"
76 #include "pbx_private.h"
77
78 /*!
79  * \note I M P O R T A N T :
80  *
81  *              The speed of extension handling will likely be among the most important
82  * aspects of this PBX.  The switching scheme as it exists right now isn't
83  * terribly bad (it's O(N+M), where N is the # of extensions and M is the avg #
84  * of priorities, but a constant search time here would be great ;-)
85  *
86  * A new algorithm to do searching based on a 'compiled' pattern tree is introduced
87  * here, and shows a fairly flat (constant) search time, even for over
88  * 10000 patterns.
89  *
90  * Also, using a hash table for context/priority name lookup can help prevent
91  * the find_extension routines from absorbing exponential cpu cycles as the number
92  * of contexts/priorities grow. I've previously tested find_extension with red-black trees,
93  * which have O(log2(n)) speed. Right now, I'm using hash tables, which do
94  * searches (ideally) in O(1) time. While these techniques do not yield much
95  * speed in small dialplans, they are worth the trouble in large dialplans.
96  *
97  */
98
99 /*** DOCUMENTATION
100         <function name="EXCEPTION" language="en_US">
101                 <synopsis>
102                         Retrieve the details of the current dialplan exception.
103                 </synopsis>
104                 <syntax>
105                         <parameter name="field" required="true">
106                                 <para>The following fields are available for retrieval:</para>
107                                 <enumlist>
108                                         <enum name="reason">
109                                                 <para>INVALID, ERROR, RESPONSETIMEOUT, ABSOLUTETIMEOUT, or custom
110                                                 value set by the RaiseException() application</para>
111                                         </enum>
112                                         <enum name="context">
113                                                 <para>The context executing when the exception occurred.</para>
114                                         </enum>
115                                         <enum name="exten">
116                                                 <para>The extension executing when the exception occurred.</para>
117                                         </enum>
118                                         <enum name="priority">
119                                                 <para>The numeric priority executing when the exception occurred.</para>
120                                         </enum>
121                                 </enumlist>
122                         </parameter>
123                 </syntax>
124                 <description>
125                         <para>Retrieve the details (specified <replaceable>field</replaceable>) of the current dialplan exception.</para>
126                 </description>
127                 <see-also>
128                         <ref type="application">RaiseException</ref>
129                 </see-also>
130         </function>
131         <function name="TESTTIME" language="en_US">
132                 <synopsis>
133                         Sets a time to be used with the channel to test logical conditions.
134                 </synopsis>
135                 <syntax>
136                         <parameter name="date" required="true" argsep=" ">
137                                 <para>Date in ISO 8601 format</para>
138                         </parameter>
139                         <parameter name="time" required="true" argsep=" ">
140                                 <para>Time in HH:MM:SS format (24-hour time)</para>
141                         </parameter>
142                         <parameter name="zone" required="false">
143                                 <para>Timezone name</para>
144                         </parameter>
145                 </syntax>
146                 <description>
147                         <para>To test dialplan timing conditions at times other than the current time, use
148                         this function to set an alternate date and time.  For example, you may wish to evaluate
149                         whether a location will correctly identify to callers that the area is closed on Christmas
150                         Day, when Christmas would otherwise fall on a day when the office is normally open.</para>
151                 </description>
152                 <see-also>
153                         <ref type="application">GotoIfTime</ref>
154                 </see-also>
155         </function>
156         <manager name="ShowDialPlan" language="en_US">
157                 <synopsis>
158                         Show dialplan contexts and extensions
159                 </synopsis>
160                 <syntax>
161                         <xi:include xpointer="xpointer(/docs/manager[@name='Login']/syntax/parameter[@name='ActionID'])" />
162                         <parameter name="Extension">
163                                 <para>Show a specific extension.</para>
164                         </parameter>
165                         <parameter name="Context">
166                                 <para>Show a specific context.</para>
167                         </parameter>
168                 </syntax>
169                 <description>
170                         <para>Show dialplan contexts and extensions. Be aware that showing the full dialplan
171                         may take a lot of capacity.</para>
172                 </description>
173         </manager>
174         <manager name="ExtensionStateList" language="en_US">
175                 <synopsis>
176                         List the current known extension states.
177                 </synopsis>
178                 <syntax>
179                         <xi:include xpointer="xpointer(/docs/manager[@name='Login']/syntax/parameter[@name='ActionID'])" />
180                 </syntax>
181                 <description>
182                         <para>This will list out all known extension states in a
183                         sequence of <replaceable>ExtensionStatus</replaceable> events.
184                         When finished, a <replaceable>ExtensionStateListComplete</replaceable> event
185                         will be emitted.</para>
186                 </description>
187                 <see-also>
188                         <ref type="manager">ExtensionState</ref>
189                         <ref type="function">HINT</ref>
190                         <ref type="function">EXTENSION_STATE</ref>
191                 </see-also>
192                 <responses>
193                         <list-elements>
194                                 <xi:include xpointer="xpointer(/docs/managerEvent[@name='ExtensionStatus'])" />
195                         </list-elements>
196                         <managerEvent name="ExtensionStateListComplete" language="en_US">
197                                 <managerEventInstance class="EVENT_FLAG_COMMAND">
198                                         <synopsis>
199                                                 Indicates the end of the list the current known extension states.
200                                         </synopsis>
201                                         <syntax>
202                                                 <parameter name="EventList">
203                                                         <para>Conveys the status of the event list.</para>
204                                                 </parameter>
205                                                 <parameter name="ListItems">
206                                                         <para>Conveys the number of statuses reported.</para>
207                                                 </parameter>
208                                         </syntax>
209                                 </managerEventInstance>
210                         </managerEvent>
211                 </responses>
212         </manager>
213  ***/
214
215 #ifdef LOW_MEMORY
216 #define EXT_DATA_SIZE 256
217 #else
218 #define EXT_DATA_SIZE 8192
219 #endif
220
221 #define SWITCH_DATA_LENGTH 256
222
223 #define VAR_NORMAL              1
224 #define VAR_SOFTTRAN    2
225 #define VAR_HARDTRAN    3
226
227 struct ast_context;
228 struct ast_app;
229
230 AST_THREADSTORAGE(switch_data);
231 AST_THREADSTORAGE(extensionstate_buf);
232
233 /*!
234    \brief ast_exten: An extension
235         The dialplan is saved as a linked list with each context
236         having it's own linked list of extensions - one item per
237         priority.
238 */
239 struct ast_exten {
240         char *exten;                    /*!< Extension name */
241         int matchcid;                   /*!< Match caller id ? */
242         const char *cidmatch;           /*!< Caller id to match for this extension */
243         int priority;                   /*!< Priority */
244         const char *label;              /*!< Label */
245         struct ast_context *parent;     /*!< The context this extension belongs to  */
246         const char *app;                /*!< Application to execute */
247         struct ast_app *cached_app;     /*!< Cached location of application */
248         void *data;                     /*!< Data to use (arguments) */
249         void (*datad)(void *);          /*!< Data destructor */
250         struct ast_exten *peer;         /*!< Next higher priority with our extension */
251         struct ast_hashtab *peer_table;    /*!< Priorities list in hashtab form -- only on the head of the peer list */
252         struct ast_hashtab *peer_label_table; /*!< labeled priorities in the peers -- only on the head of the peer list */
253         const char *registrar;          /*!< Registrar */
254         struct ast_exten *next;         /*!< Extension with a greater ID */
255         char stuff[0];
256 };
257
258 /*! \brief ast_sw: Switch statement in extensions.conf */
259 struct ast_sw {
260         char *name;
261         const char *registrar;                  /*!< Registrar */
262         char *data;                             /*!< Data load */
263         int eval;
264         AST_LIST_ENTRY(ast_sw) list;
265         char stuff[0];
266 };
267
268 /*! \brief match_char: forms a syntax tree for quick matching of extension patterns */
269 struct match_char
270 {
271         int is_pattern; /* the pattern started with '_' */
272         int deleted;    /* if this is set, then... don't return it */
273         int specificity; /* simply the strlen of x, or 10 for X, 9 for Z, and 8 for N; and '.' and '!' will add 11 ? */
274         struct match_char *alt_char;
275         struct match_char *next_char;
276         struct ast_exten *exten; /* attached to last char of a pattern for exten */
277         char x[1];       /* the pattern itself-- matches a single char */
278 };
279
280 struct scoreboard  /* make sure all fields are 0 before calling new_find_extension */
281 {
282         int total_specificity;
283         int total_length;
284         char last_char;   /* set to ! or . if they are the end of the pattern */
285         int canmatch;     /* if the string to match was just too short */
286         struct match_char *node;
287         struct ast_exten *canmatch_exten;
288         struct ast_exten *exten;
289 };
290
291 /*! \brief ast_context: An extension context - must remain in sync with fake_context */
292 struct ast_context {
293         ast_rwlock_t lock;                      /*!< A lock to prevent multiple threads from clobbering the context */
294         struct ast_exten *root;                 /*!< The root of the list of extensions */
295         struct ast_hashtab *root_table;            /*!< For exact matches on the extensions in the pattern tree, and for traversals of the pattern_tree  */
296         struct match_char *pattern_tree;        /*!< A tree to speed up extension pattern matching */
297         struct ast_context *next;               /*!< Link them together */
298         struct ast_includes includes;           /*!< Include other contexts */
299         struct ast_ignorepats ignorepats;       /*!< Patterns for which to continue playing dialtone */
300         char *registrar;                        /*!< Registrar -- make sure you malloc this, as the registrar may have to survive module unloads */
301         int refcount;                   /*!< each module that would have created this context should inc/dec this as appropriate */
302         int autohints;                  /*!< Whether autohints support is enabled or not */
303         AST_LIST_HEAD_NOLOCK(, ast_sw) alts;    /*!< Alternative switches */
304         ast_mutex_t macrolock;                  /*!< A lock to implement "exclusive" macros - held whilst a call is executing in the macro */
305         char name[0];                           /*!< Name of the context */
306 };
307
308 /*! \brief ast_state_cb: An extension state notify register item */
309 struct ast_state_cb {
310         /*! Watcher ID returned when registered. */
311         int id;
312         /*! Arbitrary data passed for callbacks. */
313         void *data;
314         /*! Flag if this callback is an extended callback containing detailed device status */
315         int extended;
316         /*! Callback when state changes. */
317         ast_state_cb_type change_cb;
318         /*! Callback when destroyed so any resources given by the registerer can be freed. */
319         ast_state_cb_destroy_type destroy_cb;
320         /*! \note Only used by ast_merge_contexts_and_delete */
321         AST_LIST_ENTRY(ast_state_cb) entry;
322 };
323
324 /*!
325  * \brief Structure for dial plan hints
326  *
327  * \note Hints are pointers from an extension in the dialplan to
328  * one or more devices (tech/name)
329  *
330  * See \ref AstExtState
331  */
332 struct ast_hint {
333         /*!
334          * \brief Hint extension
335          *
336          * \note
337          * Will never be NULL while the hint is in the hints container.
338          */
339         struct ast_exten *exten;
340         struct ao2_container *callbacks; /*!< Device state callback container for this extension */
341
342         /*! Dev state variables */
343         int laststate;                  /*!< Last known device state */
344
345         /*! Presence state variables */
346         int last_presence_state;     /*!< Last known presence state */
347         char *last_presence_subtype; /*!< Last known presence subtype string */
348         char *last_presence_message; /*!< Last known presence message string */
349
350         char context_name[AST_MAX_CONTEXT];/*!< Context of destroyed hint extension. */
351         char exten_name[AST_MAX_EXTENSION];/*!< Extension of destroyed hint extension. */
352
353         AST_VECTOR(, char *) devices; /*!< Devices associated with the hint */
354 };
355
356 STASIS_MESSAGE_TYPE_DEFN_LOCAL(hint_change_message_type);
357
358 #define HINTDEVICE_DATA_LENGTH 16
359 AST_THREADSTORAGE(hintdevice_data);
360
361 /* --- Hash tables of various objects --------*/
362 #ifdef LOW_MEMORY
363 #define HASH_EXTENHINT_SIZE 17
364 #else
365 #define HASH_EXTENHINT_SIZE 563
366 #endif
367
368
369 /*! \brief Container for hint devices */
370 static struct ao2_container *hintdevices;
371
372 /*!
373  * \brief Structure for dial plan hint devices
374  * \note hintdevice is one device pointing to a hint.
375  */
376 struct ast_hintdevice {
377         /*!
378          * \brief Hint this hintdevice belongs to.
379          * \note Holds a reference to the hint object.
380          */
381         struct ast_hint *hint;
382         /*! Name of the hint device. */
383         char hintdevice[1];
384 };
385
386 /*! \brief Container for autohint contexts */
387 static struct ao2_container *autohints;
388
389 /*!
390  * \brief Structure for dial plan autohints
391  */
392 struct ast_autohint {
393         /*! \brief Name of the registrar */
394         char *registrar;
395         /*! \brief Name of the context */
396         char context[1];
397 };
398
399 /*!
400  * \note Using the device for hash
401  */
402 static int hintdevice_hash_cb(const void *obj, const int flags)
403 {
404         const struct ast_hintdevice *ext;
405         const char *key;
406
407         switch (flags & OBJ_SEARCH_MASK) {
408         case OBJ_SEARCH_KEY:
409                 key = obj;
410                 break;
411         case OBJ_SEARCH_OBJECT:
412                 ext = obj;
413                 key = ext->hintdevice;
414                 break;
415         default:
416                 ast_assert(0);
417                 return 0;
418         }
419
420         return ast_str_case_hash(key);
421 }
422
423 /*!
424  * \note Devices on hints are not unique so no CMP_STOP is returned
425  * Dont use ao2_find against hintdevices container cause there always
426  * could be more than one result.
427  */
428 static int hintdevice_cmp_multiple(void *obj, void *arg, int flags)
429 {
430         struct ast_hintdevice *left = obj;
431         struct ast_hintdevice *right = arg;
432         const char *right_key = arg;
433         int cmp;
434
435         switch (flags & OBJ_SEARCH_MASK) {
436         case OBJ_SEARCH_OBJECT:
437                 right_key = right->hintdevice;
438                 /* Fall through */
439         case OBJ_SEARCH_KEY:
440                 cmp = strcasecmp(left->hintdevice, right_key);
441                 break;
442         case OBJ_SEARCH_PARTIAL_KEY:
443                 /*
444                 * We could also use a partial key struct containing a length
445                 * so strlen() does not get called for every comparison instead.
446                 */
447                 cmp = strncmp(left->hintdevice, right_key, strlen(right_key));
448                 break;
449         default:
450                 ast_assert(0);
451                 cmp = 0;
452                 break;
453         }
454         return cmp ? 0 : CMP_MATCH;
455 }
456
457 /*!
458  * \note Using the context name for hash
459  */
460 static int autohint_hash_cb(const void *obj, const int flags)
461 {
462         const struct ast_autohint *autohint;
463         const char *key;
464
465         switch (flags & OBJ_SEARCH_MASK) {
466         case OBJ_SEARCH_KEY:
467                 key = obj;
468                 break;
469         case OBJ_SEARCH_OBJECT:
470                 autohint = obj;
471                 key = autohint->context;
472                 break;
473         default:
474                 ast_assert(0);
475                 return 0;
476         }
477
478         return ast_str_case_hash(key);
479 }
480
481 static int autohint_cmp(void *obj, void *arg, int flags)
482 {
483         struct ast_autohint *left = obj;
484         struct ast_autohint *right = arg;
485         const char *right_key = arg;
486         int cmp;
487
488         switch (flags & OBJ_SEARCH_MASK) {
489         case OBJ_SEARCH_OBJECT:
490                 right_key = right->context;
491                 /* Fall through */
492         case OBJ_SEARCH_KEY:
493                 cmp = strcasecmp(left->context, right_key);
494                 break;
495         case OBJ_SEARCH_PARTIAL_KEY:
496                 /*
497                 * We could also use a partial key struct containing a length
498                 * so strlen() does not get called for every comparison instead.
499                 */
500                 cmp = strncmp(left->context, right_key, strlen(right_key));
501                 break;
502         default:
503                 ast_assert(0);
504                 cmp = 0;
505                 break;
506         }
507         return cmp ? 0 : CMP_MATCH | CMP_STOP;
508 }
509
510 /*! \internal \brief \c ao2_callback function to remove hintdevices */
511 static int hintdevice_remove_cb(void *obj, void *arg, void *data, int flags)
512 {
513         struct ast_hintdevice *candidate = obj;
514         char *device = arg;
515         struct ast_hint *hint = data;
516
517         if (!strcasecmp(candidate->hintdevice, device)
518                 && candidate->hint == hint) {
519                 return CMP_MATCH;
520         }
521         return 0;
522 }
523
524 static int remove_hintdevice(struct ast_hint *hint)
525 {
526         while (AST_VECTOR_SIZE(&hint->devices) > 0) {
527                 char *device = AST_VECTOR_GET(&hint->devices, 0);
528
529                 ao2_t_callback_data(hintdevices, OBJ_SEARCH_KEY | OBJ_UNLINK | OBJ_NODATA,
530                         hintdevice_remove_cb, device, hint, "Remove device from container");
531                 AST_VECTOR_REMOVE_UNORDERED(&hint->devices, 0);
532                 ast_free(device);
533         }
534
535         return 0;
536 }
537
538 static char *parse_hint_device(struct ast_str *hint_args);
539 /*!
540  * \internal
541  * \brief Destroy the given hintdevice object.
542  *
543  * \param obj Hint device to destroy.
544  *
545  * \return Nothing
546  */
547 static void hintdevice_destroy(void *obj)
548 {
549         struct ast_hintdevice *doomed = obj;
550
551         if (doomed->hint) {
552                 ao2_ref(doomed->hint, -1);
553                 doomed->hint = NULL;
554         }
555 }
556
557 /*! \brief add hintdevice structure and link it into the container.
558  */
559 static int add_hintdevice(struct ast_hint *hint, const char *devicelist)
560 {
561         struct ast_str *str;
562         char *parse;
563         char *cur;
564         struct ast_hintdevice *device;
565         int devicelength;
566
567         if (!hint || !devicelist) {
568                 /* Trying to add garbage? Don't bother. */
569                 return 0;
570         }
571         if (!(str = ast_str_thread_get(&hintdevice_data, 16))) {
572                 return -1;
573         }
574         ast_str_set(&str, 0, "%s", devicelist);
575         parse = ast_str_buffer(str);
576
577         /* Spit on '&' and ',' to handle presence hints as well */
578         while ((cur = strsep(&parse, "&,"))) {
579                 char *device_name;
580
581                 devicelength = strlen(cur);
582                 if (!devicelength) {
583                         continue;
584                 }
585
586                 device_name = ast_strdup(cur);
587                 if (!device_name) {
588                         return -1;
589                 }
590
591                 device = ao2_t_alloc(sizeof(*device) + devicelength, hintdevice_destroy,
592                         "allocating a hintdevice structure");
593                 if (!device) {
594                         ast_free(device_name);
595                         return -1;
596                 }
597                 strcpy(device->hintdevice, cur);
598                 ao2_ref(hint, +1);
599                 device->hint = hint;
600                 if (AST_VECTOR_APPEND(&hint->devices, device_name)) {
601                         ast_free(device_name);
602                         ao2_ref(device, -1);
603                         return -1;
604                 }
605                 ao2_t_link(hintdevices, device, "Linking device into hintdevice container.");
606                 ao2_t_ref(device, -1, "hintdevice is linked so we can unref");
607         }
608
609         return 0;
610 }
611
612
613 static const struct cfextension_states {
614         int extension_state;
615         const char * const text;
616 } extension_states[] = {
617         { AST_EXTENSION_NOT_INUSE,                     "Idle" },
618         { AST_EXTENSION_INUSE,                         "InUse" },
619         { AST_EXTENSION_BUSY,                          "Busy" },
620         { AST_EXTENSION_UNAVAILABLE,                   "Unavailable" },
621         { AST_EXTENSION_RINGING,                       "Ringing" },
622         { AST_EXTENSION_INUSE | AST_EXTENSION_RINGING, "InUse&Ringing" },
623         { AST_EXTENSION_ONHOLD,                        "Hold" },
624         { AST_EXTENSION_INUSE | AST_EXTENSION_ONHOLD,  "InUse&Hold" }
625 };
626
627 struct pbx_exception {
628         AST_DECLARE_STRING_FIELDS(
629                 AST_STRING_FIELD(context);      /*!< Context associated with this exception */
630                 AST_STRING_FIELD(exten);        /*!< Exten associated with this exception */
631                 AST_STRING_FIELD(reason);               /*!< The exception reason */
632         );
633
634         int priority;                           /*!< Priority associated with this exception */
635 };
636
637 static int matchcid(const char *cidpattern, const char *callerid);
638 #ifdef NEED_DEBUG
639 static void log_match_char_tree(struct match_char *node, char *prefix); /* for use anywhere */
640 #endif
641 static void new_find_extension(const char *str, struct scoreboard *score,
642                 struct match_char *tree, int length, int spec, const char *callerid,
643                 const char *label, enum ext_match_t action);
644 static struct match_char *already_in_tree(struct match_char *current, char *pat, int is_pattern);
645 static struct match_char *add_exten_to_pattern_tree(struct ast_context *con,
646                 struct ast_exten *e1, int findonly);
647 static void create_match_char_tree(struct ast_context *con);
648 static struct ast_exten *get_canmatch_exten(struct match_char *node);
649 static void destroy_pattern_tree(struct match_char *pattern_tree);
650 static int hashtab_compare_extens(const void *ha_a, const void *ah_b);
651 static int hashtab_compare_exten_numbers(const void *ah_a, const void *ah_b);
652 static int hashtab_compare_exten_labels(const void *ah_a, const void *ah_b);
653 static unsigned int hashtab_hash_extens(const void *obj);
654 static unsigned int hashtab_hash_priority(const void *obj);
655 static unsigned int hashtab_hash_labels(const void *obj);
656 static void __ast_internal_context_destroy( struct ast_context *con);
657 static int ast_add_extension_nolock(const char *context, int replace, const char *extension,
658         int priority, const char *label, const char *callerid,
659         const char *application, void *data, void (*datad)(void *), const char *registrar);
660 static int ast_add_extension2_lockopt(struct ast_context *con,
661         int replace, const char *extension, int priority, const char *label, const char *callerid,
662         const char *application, void *data, void (*datad)(void *),
663         const char *registrar, int lock_context);
664 static struct ast_context *find_context_locked(const char *context);
665 static struct ast_context *find_context(const char *context);
666 static void get_device_state_causing_channels(struct ao2_container *c);
667
668 /*!
669  * \internal
670  * \brief Character array comparison function for qsort.
671  *
672  * \param a Left side object.
673  * \param b Right side object.
674  *
675  * \retval <0 if a < b
676  * \retval =0 if a = b
677  * \retval >0 if a > b
678  */
679 static int compare_char(const void *a, const void *b)
680 {
681         const unsigned char *ac = a;
682         const unsigned char *bc = b;
683
684         return *ac - *bc;
685 }
686
687 /* labels, contexts are case sensitive  priority numbers are ints */
688 int ast_hashtab_compare_contexts(const void *ah_a, const void *ah_b)
689 {
690         const struct ast_context *ac = ah_a;
691         const struct ast_context *bc = ah_b;
692         if (!ac || !bc) /* safety valve, but it might prevent a crash you'd rather have happen */
693                 return 1;
694         /* assume context names are registered in a string table! */
695         return strcmp(ac->name, bc->name);
696 }
697
698 static int hashtab_compare_extens(const void *ah_a, const void *ah_b)
699 {
700         const struct ast_exten *ac = ah_a;
701         const struct ast_exten *bc = ah_b;
702         int x = strcmp(ac->exten, bc->exten);
703         if (x) { /* if exten names are diff, then return */
704                 return x;
705         }
706
707         /* but if they are the same, do the cidmatch values match? */
708         /* not sure which side may be using ast_ext_matchcid_types, so check both */
709         if (ac->matchcid == AST_EXT_MATCHCID_ANY || bc->matchcid == AST_EXT_MATCHCID_ANY) {
710                 return 0;
711         }
712         if (ac->matchcid == AST_EXT_MATCHCID_OFF && bc->matchcid == AST_EXT_MATCHCID_OFF) {
713                 return 0;
714         }
715         if (ac->matchcid != bc->matchcid) {
716                 return 1;
717         }
718         /* all other cases already disposed of, match now required on callerid string (cidmatch) */
719         /* although ast_add_extension2_lockopt() enforces non-zero ptr, caller may not have */
720         if (ast_strlen_zero(ac->cidmatch) && ast_strlen_zero(bc->cidmatch)) {
721                 return 0;
722         }
723         return strcmp(ac->cidmatch, bc->cidmatch);
724 }
725
726 static int hashtab_compare_exten_numbers(const void *ah_a, const void *ah_b)
727 {
728         const struct ast_exten *ac = ah_a;
729         const struct ast_exten *bc = ah_b;
730         return ac->priority != bc->priority;
731 }
732
733 static int hashtab_compare_exten_labels(const void *ah_a, const void *ah_b)
734 {
735         const struct ast_exten *ac = ah_a;
736         const struct ast_exten *bc = ah_b;
737         return strcmp(S_OR(ac->label, ""), S_OR(bc->label, ""));
738 }
739
740 unsigned int ast_hashtab_hash_contexts(const void *obj)
741 {
742         const struct ast_context *ac = obj;
743         return ast_hashtab_hash_string(ac->name);
744 }
745
746 static unsigned int hashtab_hash_extens(const void *obj)
747 {
748         const struct ast_exten *ac = obj;
749         unsigned int x = ast_hashtab_hash_string(ac->exten);
750         unsigned int y = 0;
751         if (ac->matchcid == AST_EXT_MATCHCID_ON)
752                 y = ast_hashtab_hash_string(ac->cidmatch);
753         return x+y;
754 }
755
756 static unsigned int hashtab_hash_priority(const void *obj)
757 {
758         const struct ast_exten *ac = obj;
759         return ast_hashtab_hash_int(ac->priority);
760 }
761
762 static unsigned int hashtab_hash_labels(const void *obj)
763 {
764         const struct ast_exten *ac = obj;
765         return ast_hashtab_hash_string(S_OR(ac->label, ""));
766 }
767
768 static int autofallthrough = 1;
769 static int extenpatternmatchnew = 0;
770 static char *overrideswitch = NULL;
771
772 /*! \brief Subscription for device state change events */
773 static struct stasis_subscription *device_state_sub;
774 /*! \brief Subscription for presence state change events */
775 static struct stasis_subscription *presence_state_sub;
776
777 AST_MUTEX_DEFINE_STATIC(maxcalllock);
778 static int countcalls;
779 static int totalcalls;
780
781 static struct ast_context *contexts;
782 static struct ast_hashtab *contexts_table = NULL;
783
784 /*!
785  * \brief Lock for the ast_context list
786  * \note
787  * This lock MUST be recursive, or a deadlock on reload may result.  See
788  * https://issues.asterisk.org/view.php?id=17643
789  */
790 AST_MUTEX_DEFINE_STATIC(conlock);
791
792 /*!
793  * \brief Lock to hold off restructuring of hints by ast_merge_contexts_and_delete.
794  */
795 AST_MUTEX_DEFINE_STATIC(context_merge_lock);
796
797 static int stateid = 1;
798 /*!
799  * \note When holding this container's lock, do _not_ do
800  * anything that will cause conlock to be taken, unless you
801  * _already_ hold it.  The ast_merge_contexts_and_delete function
802  * will take the locks in conlock/hints order, so any other
803  * paths that require both locks must also take them in that
804  * order.
805  */
806 static struct ao2_container *hints;
807
808 static struct ao2_container *statecbs;
809
810 #ifdef CONTEXT_DEBUG
811
812 /* these routines are provided for doing run-time checks
813    on the extension structures, in case you are having
814    problems, this routine might help you localize where
815    the problem is occurring. It's kinda like a debug memory
816    allocator's arena checker... It'll eat up your cpu cycles!
817    but you'll see, if you call it in the right places,
818    right where your problems began...
819 */
820
821 /* you can break on the check_contexts_trouble()
822 routine in your debugger to stop at the moment
823 there's a problem */
824 void check_contexts_trouble(void);
825
826 void check_contexts_trouble(void)
827 {
828         int x = 1;
829         x = 2;
830 }
831
832 int check_contexts(char *, int);
833
834 int check_contexts(char *file, int line )
835 {
836         struct ast_hashtab_iter *t1;
837         struct ast_context *c1, *c2;
838         int found = 0;
839         struct ast_exten *e1, *e2, *e3;
840         struct ast_exten ex;
841
842         /* try to find inconsistencies */
843         /* is every context in the context table in the context list and vice-versa ? */
844
845         if (!contexts_table) {
846                 ast_log(LOG_NOTICE,"Called from: %s:%d: No contexts_table!\n", file, line);
847                 usleep(500000);
848         }
849
850         t1 = ast_hashtab_start_traversal(contexts_table);
851         while( (c1 = ast_hashtab_next(t1))) {
852                 for(c2=contexts;c2;c2=c2->next) {
853                         if (!strcmp(c1->name, c2->name)) {
854                                 found = 1;
855                                 break;
856                         }
857                 }
858                 if (!found) {
859                         ast_log(LOG_NOTICE,"Called from: %s:%d: Could not find the %s context in the linked list\n", file, line, c1->name);
860                         check_contexts_trouble();
861                 }
862         }
863         ast_hashtab_end_traversal(t1);
864         for(c2=contexts;c2;c2=c2->next) {
865                 c1 = find_context_locked(c2->name);
866                 if (!c1) {
867                         ast_log(LOG_NOTICE,"Called from: %s:%d: Could not find the %s context in the hashtab\n", file, line, c2->name);
868                         check_contexts_trouble();
869                 } else
870                         ast_unlock_contexts();
871         }
872
873         /* loop thru all contexts, and verify the exten structure compares to the
874            hashtab structure */
875         for(c2=contexts;c2;c2=c2->next) {
876                 c1 = find_context_locked(c2->name);
877                 if (c1) {
878                         ast_unlock_contexts();
879
880                         /* is every entry in the root list also in the root_table? */
881                         for(e1 = c1->root; e1; e1=e1->next)
882                         {
883                                 char dummy_name[1024];
884                                 ex.exten = dummy_name;
885                                 ex.matchcid = e1->matchcid;
886                                 ex.cidmatch = e1->cidmatch;
887                                 ast_copy_string(dummy_name, e1->exten, sizeof(dummy_name));
888                                 e2 = ast_hashtab_lookup(c1->root_table, &ex);
889                                 if (!e2) {
890                                         if (e1->matchcid == AST_EXT_MATCHCID_ON) {
891                                                 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 );
892                                         } else {
893                                                 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 );
894                                         }
895                                         check_contexts_trouble();
896                                 }
897                         }
898
899                         /* is every entry in the root_table also in the root list? */
900                         if (!c2->root_table) {
901                                 if (c2->root) {
902                                         ast_log(LOG_NOTICE,"Called from: %s:%d: No c2->root_table for context %s!\n", file, line, c2->name);
903                                         usleep(500000);
904                                 }
905                         } else {
906                                 t1 = ast_hashtab_start_traversal(c2->root_table);
907                                 while( (e2 = ast_hashtab_next(t1)) ) {
908                                         for(e1=c2->root;e1;e1=e1->next) {
909                                                 if (!strcmp(e1->exten, e2->exten)) {
910                                                         found = 1;
911                                                         break;
912                                                 }
913                                         }
914                                         if (!found) {
915                                                 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);
916                                                 check_contexts_trouble();
917                                         }
918
919                                 }
920                                 ast_hashtab_end_traversal(t1);
921                         }
922                 }
923                 /* is every priority reflected in the peer_table at the head of the list? */
924
925                 /* is every entry in the root list also in the root_table? */
926                 /* are the per-extension peer_tables in the right place? */
927
928                 for(e1 = c2->root; e1; e1 = e1->next) {
929
930                         for(e2=e1;e2;e2=e2->peer) {
931                                 ex.priority = e2->priority;
932                                 if (e2 != e1 && e2->peer_table) {
933                                         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 );
934                                         check_contexts_trouble();
935                                 }
936
937                                 if (e2 != e1 && e2->peer_label_table) {
938                                         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 );
939                                         check_contexts_trouble();
940                                 }
941
942                                 if (e2 == e1 && !e2->peer_table){
943                                         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 );
944                                         check_contexts_trouble();
945                                 }
946
947                                 if (e2 == e1 && !e2->peer_label_table) {
948                                         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 );
949                                         check_contexts_trouble();
950                                 }
951
952
953                                 e3 = ast_hashtab_lookup(e1->peer_table, &ex);
954                                 if (!e3) {
955                                         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 );
956                                         check_contexts_trouble();
957                                 }
958                         }
959
960                         if (!e1->peer_table){
961                                 ast_log(LOG_NOTICE,"Called from: %s:%d: No e1->peer_table!\n", file, line);
962                                 usleep(500000);
963                         }
964
965                         /* is every entry in the peer_table also in the peer list? */
966                         t1 = ast_hashtab_start_traversal(e1->peer_table);
967                         while( (e2 = ast_hashtab_next(t1)) ) {
968                                 for(e3=e1;e3;e3=e3->peer) {
969                                         if (e3->priority == e2->priority) {
970                                                 found = 1;
971                                                 break;
972                                         }
973                                 }
974                                 if (!found) {
975                                         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 );
976                                         check_contexts_trouble();
977                                 }
978                         }
979                         ast_hashtab_end_traversal(t1);
980                 }
981         }
982         return 0;
983 }
984 #endif
985
986 static void pbx_destroy(struct ast_pbx *p)
987 {
988         ast_free(p);
989 }
990
991 /* form a tree that fully describes all the patterns in a context's extensions
992  * in this tree, a "node" represents an individual character or character set
993  * meant to match the corresponding character in a dial string. The tree
994  * consists of a series of match_char structs linked in a chain
995  * via the alt_char pointers. More than one pattern can share the same parts of the
996  * tree as other extensions with the same pattern to that point.
997  * My first attempt to duplicate the finding of the 'best' pattern was flawed in that
998  * I misunderstood the general algorithm. I thought that the 'best' pattern
999  * was the one with lowest total score. This was not true. Thus, if you have
1000  * patterns "1XXXXX" and "X11111", you would be tempted to say that "X11111" is
1001  * the "best" match because it has fewer X's, and is therefore more specific,
1002  * but this is not how the old algorithm works. It sorts matching patterns
1003  * in a similar collating sequence as sorting alphabetic strings, from left to
1004  * right. Thus, "1XXXXX" comes before "X11111", and would be the "better" match,
1005  * because "1" is more specific than "X".
1006  * So, to accomodate this philosophy, I sort the tree branches along the alt_char
1007  * line so they are lowest to highest in specificity numbers. This way, as soon
1008  * as we encounter our first complete match, we automatically have the "best"
1009  * match and can stop the traversal immediately. Same for CANMATCH/MATCHMORE.
1010  * If anyone would like to resurrect the "wrong" pattern trie searching algorithm,
1011  * they are welcome to revert pbx to before 1 Apr 2008.
1012  * As an example, consider these 4 extensions:
1013  * (a) NXXNXXXXXX
1014  * (b) 307754XXXX
1015  * (c) fax
1016  * (d) NXXXXXXXXX
1017  *
1018  * In the above, between (a) and (d), (a) is a more specific pattern than (d), and would win over
1019  * most numbers. For all numbers beginning with 307754, (b) should always win.
1020  *
1021  * These pattern should form a (sorted) tree that looks like this:
1022  *   { "3" }  --next-->  { "0" }  --next--> { "7" } --next--> { "7" } --next--> { "5" } ... blah ... --> { "X" exten_match: (b) }
1023  *      |
1024  *      |alt
1025  *      |
1026  *   { "f" }  --next-->  { "a" }  --next--> { "x"  exten_match: (c) }
1027  *   { "N" }  --next-->  { "X" }  --next--> { "X" } --next--> { "N" } --next--> { "X" } ... blah ... --> { "X" exten_match: (a) }
1028  *      |                                                        |
1029  *      |                                                        |alt
1030  *      |alt                                                     |
1031  *      |                                                     { "X" } --next--> { "X" } ... blah ... --> { "X" exten_match: (d) }
1032  *      |
1033  *     NULL
1034  *
1035  *   In the above, I could easily turn "N" into "23456789", but I think that a quick "if( *z >= '2' && *z <= '9' )" might take
1036  *   fewer CPU cycles than a call to strchr("23456789",*z), where *z is the char to match...
1037  *
1038  *   traversal is pretty simple: one routine merely traverses the alt list, and for each matching char in the pattern,  it calls itself
1039  *   on the corresponding next pointer, incrementing also the pointer of the string to be matched, and passing the total specificity and length.
1040  *   We pass a pointer to a scoreboard down through, also.
1041  *   The scoreboard isn't as necessary to the revised algorithm, but I kept it as a handy way to return the matched extension.
1042  *   The first complete match ends the traversal, which should make this version of the pattern matcher faster
1043  *   the previous. The same goes for "CANMATCH" or "MATCHMORE"; the first such match ends the traversal. In both
1044  *   these cases, the reason we can stop immediately, is because the first pattern match found will be the "best"
1045  *   according to the sort criteria.
1046  *   Hope the limit on stack depth won't be a problem... this routine should
1047  *   be pretty lean as far a stack usage goes. Any non-match terminates the recursion down a branch.
1048  *
1049  *   In the above example, with the number "3077549999" as the pattern, the traversor could match extensions a, b and d.  All are
1050  *   of length 10; they have total specificities of  24580, 10246, and 25090, respectively, not that this matters
1051  *   at all. (b) wins purely because the first character "3" is much more specific (lower specificity) than "N". I have
1052  *   left the specificity totals in the code as an artifact; at some point, I will strip it out.
1053  *
1054  *   Just how much time this algorithm might save over a plain linear traversal over all possible patterns is unknown,
1055  *   because it's a function of how many extensions are stored in a context. With thousands of extensions, the speedup
1056  *   can be very noticeable. The new matching algorithm can run several hundreds of times faster, if not a thousand or
1057  *   more times faster in extreme cases.
1058  *
1059  *   MatchCID patterns are also supported, and stored in the tree just as the extension pattern is. Thus, you
1060  *   can have patterns in your CID field as well.
1061  *
1062  * */
1063
1064
1065 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)
1066 {
1067         /* if this extension is marked as deleted, then skip this -- if it never shows
1068            on the scoreboard, it will never be found, nor will halt the traversal. */
1069         if (deleted)
1070                 return;
1071         board->total_specificity = spec;
1072         board->total_length = length;
1073         board->exten = exten;
1074         board->last_char = last;
1075         board->node = node;
1076 #ifdef NEED_DEBUG_HERE
1077         ast_log(LOG_NOTICE,"Scoreboarding (LONGER) %s, len=%d, score=%d\n", exten->exten, length, spec);
1078 #endif
1079 }
1080
1081 #ifdef NEED_DEBUG
1082 static void log_match_char_tree(struct match_char *node, char *prefix)
1083 {
1084         char extenstr[40];
1085         struct ast_str *my_prefix = ast_str_alloca(1024);
1086
1087         extenstr[0] = '\0';
1088
1089         if (node && node->exten)
1090                 snprintf(extenstr, sizeof(extenstr), "(%p)", node->exten);
1091
1092         if (strlen(node->x) > 1) {
1093                 ast_debug(1, "%s[%s]:%c:%c:%d:%s%s%s\n", prefix, node->x, node->is_pattern ? 'Y':'N',
1094                         node->deleted? 'D':'-', node->specificity, node->exten? "EXTEN:":"",
1095                         node->exten ? node->exten->exten : "", extenstr);
1096         } else {
1097                 ast_debug(1, "%s%s:%c:%c:%d:%s%s%s\n", prefix, node->x, node->is_pattern ? 'Y':'N',
1098                         node->deleted? 'D':'-', node->specificity, node->exten? "EXTEN:":"",
1099                         node->exten ? node->exten->exten : "", extenstr);
1100         }
1101
1102         ast_str_set(&my_prefix, 0, "%s+       ", prefix);
1103
1104         if (node->next_char)
1105                 log_match_char_tree(node->next_char, ast_str_buffer(my_prefix));
1106
1107         if (node->alt_char)
1108                 log_match_char_tree(node->alt_char, prefix);
1109 }
1110 #endif
1111
1112 static void cli_match_char_tree(struct match_char *node, char *prefix, int fd)
1113 {
1114         char extenstr[40];
1115         struct ast_str *my_prefix = ast_str_alloca(1024);
1116
1117         extenstr[0] = '\0';
1118
1119         if (node->exten) {
1120                 snprintf(extenstr, sizeof(extenstr), "(%p)", node->exten);
1121         }
1122
1123         if (strlen(node->x) > 1) {
1124                 ast_cli(fd, "%s[%s]:%c:%c:%d:%s%s%s\n", prefix, node->x, node->is_pattern ? 'Y' : 'N',
1125                         node->deleted ? 'D' : '-', node->specificity, node->exten? "EXTEN:" : "",
1126                         node->exten ? node->exten->exten : "", extenstr);
1127         } else {
1128                 ast_cli(fd, "%s%s:%c:%c:%d:%s%s%s\n", prefix, node->x, node->is_pattern ? 'Y' : 'N',
1129                         node->deleted ? 'D' : '-', node->specificity, node->exten? "EXTEN:" : "",
1130                         node->exten ? node->exten->exten : "", extenstr);
1131         }
1132
1133         ast_str_set(&my_prefix, 0, "%s+       ", prefix);
1134
1135         if (node->next_char)
1136                 cli_match_char_tree(node->next_char, ast_str_buffer(my_prefix), fd);
1137
1138         if (node->alt_char)
1139                 cli_match_char_tree(node->alt_char, prefix, fd);
1140 }
1141
1142 static struct ast_exten *get_canmatch_exten(struct match_char *node)
1143 {
1144         /* find the exten at the end of the rope */
1145         struct match_char *node2 = node;
1146
1147         for (node2 = node; node2; node2 = node2->next_char) {
1148                 if (node2->exten) {
1149 #ifdef NEED_DEBUG_HERE
1150                         ast_log(LOG_NOTICE,"CanMatch_exten returns exten %s(%p)\n", node2->exten->exten, node2->exten);
1151 #endif
1152                         return node2->exten;
1153                 }
1154         }
1155 #ifdef NEED_DEBUG_HERE
1156         ast_log(LOG_NOTICE,"CanMatch_exten returns NULL, match_char=%s\n", node->x);
1157 #endif
1158         return 0;
1159 }
1160
1161 static struct ast_exten *trie_find_next_match(struct match_char *node)
1162 {
1163         struct match_char *m3;
1164         struct match_char *m4;
1165         struct ast_exten *e3;
1166
1167         if (node && node->x[0] == '.' && !node->x[1]) { /* dot and ! will ALWAYS be next match in a matchmore */
1168                 return node->exten;
1169         }
1170
1171         if (node && node->x[0] == '!' && !node->x[1]) {
1172                 return node->exten;
1173         }
1174
1175         if (!node || !node->next_char) {
1176                 return NULL;
1177         }
1178
1179         m3 = node->next_char;
1180
1181         if (m3->exten) {
1182                 return m3->exten;
1183         }
1184         for (m4 = m3->alt_char; m4; m4 = m4->alt_char) {
1185                 if (m4->exten) {
1186                         return m4->exten;
1187                 }
1188         }
1189         for (m4 = m3; m4; m4 = m4->alt_char) {
1190                 e3 = trie_find_next_match(m3);
1191                 if (e3) {
1192                         return e3;
1193                 }
1194         }
1195
1196         return NULL;
1197 }
1198
1199 #ifdef DEBUG_THIS
1200 static char *action2str(enum ext_match_t action)
1201 {
1202         switch (action) {
1203         case E_MATCH:
1204                 return "MATCH";
1205         case E_CANMATCH:
1206                 return "CANMATCH";
1207         case E_MATCHMORE:
1208                 return "MATCHMORE";
1209         case E_FINDLABEL:
1210                 return "FINDLABEL";
1211         case E_SPAWN:
1212                 return "SPAWN";
1213         default:
1214                 return "?ACTION?";
1215         }
1216 }
1217
1218 #endif
1219
1220 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)
1221 {
1222         struct match_char *p; /* note minimal stack storage requirements */
1223         struct ast_exten pattern = { .label = label };
1224 #ifdef DEBUG_THIS
1225         if (tree)
1226                 ast_log(LOG_NOTICE,"new_find_extension called with %s on (sub)tree %s action=%s\n", str, tree->x, action2str(action));
1227         else
1228                 ast_log(LOG_NOTICE,"new_find_extension called with %s on (sub)tree NULL action=%s\n", str, action2str(action));
1229 #endif
1230         for (p = tree; p; p = p->alt_char) {
1231                 if (p->is_pattern) {
1232                         if (p->x[0] == 'N') {
1233                                 if (p->x[1] == 0 && *str >= '2' && *str <= '9' ) {
1234 #define NEW_MATCHER_CHK_MATCH          \
1235                                         if (p->exten && !(*(str + 1))) { /* if a shorter pattern matches along the way, might as well report it */             \
1236                                                 if (action == E_MATCH || action == E_SPAWN || action == E_FINDLABEL) { /* if in CANMATCH/MATCHMORE, don't let matches get in the way */   \
1237                                                         update_scoreboard(score, length + 1, spec + p->specificity, p->exten, 0, callerid, p->deleted, p);                 \
1238                                                         if (!p->deleted) {                                                                                           \
1239                                                                 if (action == E_FINDLABEL) {                                                                             \
1240                                                                         if (ast_hashtab_lookup(score->exten->peer_label_table, &pattern)) {                                  \
1241                                                                                 ast_debug(4, "Found label in preferred extension\n");                                            \
1242                                                                                 return;                                                                                          \
1243                                                                         }                                                                                                    \
1244                                                                 } else {                                                                                                 \
1245                                                                         ast_debug(4, "returning an exact match-- first found-- %s\n", p->exten->exten);                       \
1246                                                                         return; /* the first match, by definition, will be the best, because of the sorted tree */           \
1247                                                                 }                                                                                                        \
1248                                                         }                                                                                                            \
1249                                                 }                                                                                                                \
1250                                         }
1251
1252 #define NEW_MATCHER_RECURSE                \
1253                                         if (p->next_char && (*(str + 1) || (p->next_char->x[0] == '/' && p->next_char->x[1] == 0)                 \
1254                                                        || p->next_char->x[0] == '!')) {                                          \
1255                                                 if (*(str + 1) || p->next_char->x[0] == '!') {                                                         \
1256                                                         new_find_extension(str + 1, score, p->next_char, length + 1, spec + p->specificity, callerid, label, action); \
1257                                                         if (score->exten)  {                                                                             \
1258                                                         ast_debug(4 ,"returning an exact match-- %s\n", score->exten->exten);                         \
1259                                                                 return; /* the first match is all we need */                                                 \
1260                                                         }                                                                                                                                                \
1261                                                 } else {                                                                                             \
1262                                                         new_find_extension("/", score, p->next_char, length + 1, spec + p->specificity, callerid, label, action);        \
1263                                                         if (score->exten || ((action == E_CANMATCH || action == E_MATCHMORE) && score->canmatch)) {      \
1264                                                         ast_debug(4,"returning a (can/more) match--- %s\n", score->exten ? score->exten->exten :     \
1265                                                "NULL");                                                                        \
1266                                                                 return; /* the first match is all we need */                                                 \
1267                                                         }                                                                                                                                                \
1268                                                 }                                                                                                    \
1269                                         } else if ((p->next_char || action == E_CANMATCH) && !*(str + 1)) {                                                                  \
1270                                                 score->canmatch = 1;                                                                                 \
1271                                                 score->canmatch_exten = get_canmatch_exten(p);                                                       \
1272                                                 if (action == E_CANMATCH || action == E_MATCHMORE) {                                                 \
1273                                                 ast_debug(4, "returning a canmatch/matchmore--- str=%s\n", str);                                  \
1274                                                         return;                                                                                          \
1275                                                 }                                                                                                                                                    \
1276                                         }
1277
1278                                         NEW_MATCHER_CHK_MATCH;
1279                                         NEW_MATCHER_RECURSE;
1280                                 }
1281                         } else if (p->x[0] == 'Z') {
1282                                 if (p->x[1] == 0 && *str >= '1' && *str <= '9' ) {
1283                                         NEW_MATCHER_CHK_MATCH;
1284                                         NEW_MATCHER_RECURSE;
1285                                 }
1286                         } else if (p->x[0] == 'X') {
1287                                 if (p->x[1] == 0 && *str >= '0' && *str <= '9' ) {
1288                                         NEW_MATCHER_CHK_MATCH;
1289                                         NEW_MATCHER_RECURSE;
1290                                 }
1291                         } else if (p->x[0] == '.' && p->x[1] == 0) {
1292                                 /* how many chars will the . match against? */
1293                                 int i = 0;
1294                                 const char *str2 = str;
1295                                 while (*str2 && *str2 != '/') {
1296                                         str2++;
1297                                         i++;
1298                                 }
1299                                 if (p->exten && *str2 != '/') {
1300                                         update_scoreboard(score, length + i, spec + (i * p->specificity), p->exten, '.', callerid, p->deleted, p);
1301                                         if (score->exten) {
1302                                                 ast_debug(4,"return because scoreboard has a match with '/'--- %s\n", score->exten->exten);
1303                                                 return; /* the first match is all we need */
1304                                         }
1305                                 }
1306                                 if (p->next_char && p->next_char->x[0] == '/' && p->next_char->x[1] == 0) {
1307                                         new_find_extension("/", score, p->next_char, length + i, spec+(p->specificity*i), callerid, label, action);
1308                                         if (score->exten || ((action == E_CANMATCH || action == E_MATCHMORE) && score->canmatch)) {
1309                                                 ast_debug(4, "return because scoreboard has exact match OR CANMATCH/MATCHMORE & canmatch set--- %s\n", score->exten ? score->exten->exten : "NULL");
1310                                                 return; /* the first match is all we need */
1311                                         }
1312                                 }
1313                         } else if (p->x[0] == '!' && p->x[1] == 0) {
1314                                 /* how many chars will the . match against? */
1315                                 int i = 1;
1316                                 const char *str2 = str;
1317                                 while (*str2 && *str2 != '/') {
1318                                         str2++;
1319                                         i++;
1320                                 }
1321                                 if (p->exten && *str2 != '/') {
1322                                         update_scoreboard(score, length + 1, spec + (p->specificity * i), p->exten, '!', callerid, p->deleted, p);
1323                                         if (score->exten) {
1324                                                 ast_debug(4, "return because scoreboard has a '!' match--- %s\n", score->exten->exten);
1325                                                 return; /* the first match is all we need */
1326                                         }
1327                                 }
1328                                 if (p->next_char && p->next_char->x[0] == '/' && p->next_char->x[1] == 0) {
1329                                         new_find_extension("/", score, p->next_char, length + i, spec + (p->specificity * i), callerid, label, action);
1330                                         if (score->exten || ((action == E_CANMATCH || action == E_MATCHMORE) && score->canmatch)) {
1331                                                 ast_debug(4, "return because scoreboard has exact match OR CANMATCH/MATCHMORE & canmatch set with '/' and '!'--- %s\n", score->exten ? score->exten->exten : "NULL");
1332                                                 return; /* the first match is all we need */
1333                                         }
1334                                 }
1335                         } else if (p->x[0] == '/' && p->x[1] == 0) {
1336                                 /* the pattern in the tree includes the cid match! */
1337                                 if (p->next_char && callerid && *callerid) {
1338                                         new_find_extension(callerid, score, p->next_char, length + 1, spec, callerid, label, action);
1339                                         if (score->exten || ((action == E_CANMATCH || action == E_MATCHMORE) && score->canmatch)) {
1340                                                 ast_debug(4, "return because scoreboard has exact match OR CANMATCH/MATCHMORE & canmatch set with '/'--- %s\n", score->exten ? score->exten->exten : "NULL");
1341                                                 return; /* the first match is all we need */
1342                                         }
1343                                 }
1344                         } else if (strchr(p->x, *str)) {
1345                                 ast_debug(4, "Nothing strange about this match\n");
1346                                 NEW_MATCHER_CHK_MATCH;
1347                                 NEW_MATCHER_RECURSE;
1348                         }
1349                 } else if (strchr(p->x, *str)) {
1350                         ast_debug(4, "Nothing strange about this match\n");
1351                         NEW_MATCHER_CHK_MATCH;
1352                         NEW_MATCHER_RECURSE;
1353                 }
1354         }
1355         ast_debug(4, "return at end of func\n");
1356 }
1357
1358 /* the algorithm for forming the extension pattern tree is also a bit simple; you
1359  * traverse all the extensions in a context, and for each char of the extension,
1360  * you see if it exists in the tree; if it doesn't, you add it at the appropriate
1361  * spot. What more can I say? At the end of each exten, you cap it off by adding the
1362  * address of the extension involved. Duplicate patterns will be complained about.
1363  *
1364  * Ideally, this would be done for each context after it is created and fully
1365  * filled. It could be done as a finishing step after extensions.conf or .ael is
1366  * loaded, or it could be done when the first search is encountered. It should only
1367  * have to be done once, until the next unload or reload.
1368  *
1369  * I guess forming this pattern tree would be analogous to compiling a regex. Except
1370  * that a regex only handles 1 pattern, really. This trie holds any number
1371  * of patterns. Well, really, it **could** be considered a single pattern,
1372  * where the "|" (or) operator is allowed, I guess, in a way, sort of...
1373  */
1374
1375 static struct match_char *already_in_tree(struct match_char *current, char *pat, int is_pattern)
1376 {
1377         struct match_char *t;
1378
1379         if (!current) {
1380                 return 0;
1381         }
1382
1383         for (t = current; t; t = t->alt_char) {
1384                 if (is_pattern == t->is_pattern && !strcmp(pat, t->x)) {/* uh, we may want to sort exploded [] contents to make matching easy */
1385                         return t;
1386                 }
1387         }
1388
1389         return 0;
1390 }
1391
1392 /* The first arg is the location of the tree ptr, or the
1393    address of the next_char ptr in the node, so we can mess
1394    with it, if we need to insert at the beginning of the list */
1395
1396 static void insert_in_next_chars_alt_char_list(struct match_char **parent_ptr, struct match_char *node)
1397 {
1398         struct match_char *curr, *lcurr;
1399
1400         /* insert node into the tree at "current", so the alt_char list from current is
1401            sorted in increasing value as you go to the leaves */
1402         if (!(*parent_ptr)) {
1403                 *parent_ptr = node;
1404                 return;
1405         }
1406
1407         if ((*parent_ptr)->specificity > node->specificity) {
1408                 /* insert at head */
1409                 node->alt_char = (*parent_ptr);
1410                 *parent_ptr = node;
1411                 return;
1412         }
1413
1414         lcurr = *parent_ptr;
1415         for (curr = (*parent_ptr)->alt_char; curr; curr = curr->alt_char) {
1416                 if (curr->specificity > node->specificity) {
1417                         node->alt_char = curr;
1418                         lcurr->alt_char = node;
1419                         break;
1420                 }
1421                 lcurr = curr;
1422         }
1423
1424         if (!curr) {
1425                 lcurr->alt_char = node;
1426         }
1427
1428 }
1429
1430 struct pattern_node {
1431         /*! Pattern node specificity */
1432         int specif;
1433         /*! Pattern node match characters. */
1434         char buf[256];
1435 };
1436
1437 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)
1438 {
1439         struct match_char *m;
1440
1441         if (!(m = ast_calloc(1, sizeof(*m) + strlen(pattern->buf)))) {
1442                 return NULL;
1443         }
1444
1445         /* strcpy is safe here since we know its size and have allocated
1446          * just enough space for when we allocated m
1447          */
1448         strcpy(m->x, pattern->buf);
1449
1450         /* the specificity scores are the same as used in the old
1451            pattern matcher. */
1452         m->is_pattern = is_pattern;
1453         if (pattern->specif == 1 && is_pattern && pattern->buf[0] == 'N') {
1454                 m->specificity = 0x0832;
1455         } else if (pattern->specif == 1 && is_pattern && pattern->buf[0] == 'Z') {
1456                 m->specificity = 0x0931;
1457         } else if (pattern->specif == 1 && is_pattern && pattern->buf[0] == 'X') {
1458                 m->specificity = 0x0a30;
1459         } else if (pattern->specif == 1 && is_pattern && pattern->buf[0] == '.') {
1460                 m->specificity = 0x18000;
1461         } else if (pattern->specif == 1 && is_pattern && pattern->buf[0] == '!') {
1462                 m->specificity = 0x28000;
1463         } else {
1464                 m->specificity = pattern->specif;
1465         }
1466
1467         if (!con->pattern_tree) {
1468                 insert_in_next_chars_alt_char_list(&con->pattern_tree, m);
1469         } else {
1470                 if (already) { /* switch to the new regime (traversing vs appending)*/
1471                         insert_in_next_chars_alt_char_list(nextcharptr, m);
1472                 } else {
1473                         insert_in_next_chars_alt_char_list(&current->next_char, m);
1474                 }
1475         }
1476
1477         return m;
1478 }
1479
1480 /*!
1481  * \internal
1482  * \brief Extract the next exten pattern node.
1483  *
1484  * \param node Pattern node to fill.
1485  * \param src Next source character to read.
1486  * \param pattern TRUE if the exten is a pattern.
1487  * \param extenbuf Original exten buffer to use in diagnostic messages.
1488  *
1489  * \retval Ptr to next extenbuf pos to read.
1490  */
1491 static const char *get_pattern_node(struct pattern_node *node, const char *src, int pattern, const char *extenbuf)
1492 {
1493 #define INC_DST_OVERFLOW_CHECK                                                  \
1494         do {                                                                                            \
1495                 if (dst - node->buf < sizeof(node->buf) - 1) {  \
1496                         ++dst;                                                                          \
1497                 } else {                                                                                \
1498                         overflow = 1;                                                           \
1499                 }                                                                                               \
1500         } while (0)
1501
1502         node->specif = 0;
1503         node->buf[0] = '\0';
1504         while (*src) {
1505                 if (*src == '[' && pattern) {
1506                         char *dst = node->buf;
1507                         const char *src_next;
1508                         int length;
1509                         int overflow = 0;
1510
1511                         /* get past the '[' */
1512                         ++src;
1513                         for (;;) {
1514                                 if (*src == '\\') {
1515                                         /* Escaped character. */
1516                                         ++src;
1517                                         if (*src == '[' || *src == '\\' || *src == '-' || *src == ']') {
1518                                                 *dst = *src++;
1519                                                 INC_DST_OVERFLOW_CHECK;
1520                                         }
1521                                 } else if (*src == '-') {
1522                                         unsigned char first;
1523                                         unsigned char last;
1524
1525                                         src_next = src;
1526                                         first = *(src_next - 1);
1527                                         last = *++src_next;
1528
1529                                         if (last == '\\') {
1530                                                 /* Escaped character. */
1531                                                 last = *++src_next;
1532                                         }
1533
1534                                         /* Possible char range. */
1535                                         if (node->buf[0] && last) {
1536                                                 /* Expand the char range. */
1537                                                 while (++first <= last) {
1538                                                         *dst = first;
1539                                                         INC_DST_OVERFLOW_CHECK;
1540                                                 }
1541                                                 src = src_next + 1;
1542                                         } else {
1543                                                 /*
1544                                                  * There was no left or right char for the range.
1545                                                  * It is just a '-'.
1546                                                  */
1547                                                 *dst = *src++;
1548                                                 INC_DST_OVERFLOW_CHECK;
1549                                         }
1550                                 } else if (*src == '\0') {
1551                                         ast_log(LOG_WARNING,
1552                                                 "A matching ']' was not found for '[' in exten pattern '%s'\n",
1553                                                 extenbuf);
1554                                         break;
1555                                 } else if (*src == ']') {
1556                                         ++src;
1557                                         break;
1558                                 } else {
1559                                         *dst = *src++;
1560                                         INC_DST_OVERFLOW_CHECK;
1561                                 }
1562                         }
1563                         /* null terminate the exploded range */
1564                         *dst = '\0';
1565
1566                         if (overflow) {
1567                                 ast_log(LOG_ERROR,
1568                                         "Expanded character set too large to deal with in exten pattern '%s'. Ignoring character set.\n",
1569                                         extenbuf);
1570                                 node->buf[0] = '\0';
1571                                 continue;
1572                         }
1573
1574                         /* Sort the characters in character set. */
1575                         length = strlen(node->buf);
1576                         if (!length) {
1577                                 ast_log(LOG_WARNING, "Empty character set in exten pattern '%s'. Ignoring.\n",
1578                                         extenbuf);
1579                                 node->buf[0] = '\0';
1580                                 continue;
1581                         }
1582                         qsort(node->buf, length, 1, compare_char);
1583
1584                         /* Remove duplicate characters from character set. */
1585                         dst = node->buf;
1586                         src_next = node->buf;
1587                         while (*src_next++) {
1588                                 if (*dst != *src_next) {
1589                                         *++dst = *src_next;
1590                                 }
1591                         }
1592
1593                         length = strlen(node->buf);
1594                         length <<= 8;
1595                         node->specif = length | (unsigned char) node->buf[0];
1596                         break;
1597                 } else if (*src == '-') {
1598                         /* Skip dashes in all extensions. */
1599                         ++src;
1600                 } else {
1601                         if (*src == '\\') {
1602                                 /*
1603                                  * XXX The escape character here does not remove any special
1604                                  * meaning to characters except the '[', '\\', and '-'
1605                                  * characters since they are special only in this function.
1606                                  */
1607                                 node->buf[0] = *++src;
1608                                 if (!node->buf[0]) {
1609                                         break;
1610                                 }
1611                         } else {
1612                                 node->buf[0] = *src;
1613                                 if (pattern) {
1614                                         /* make sure n,x,z patterns are canonicalized to N,X,Z */
1615                                         if (node->buf[0] == 'n') {
1616                                                 node->buf[0] = 'N';
1617                                         } else if (node->buf[0] == 'x') {
1618                                                 node->buf[0] = 'X';
1619                                         } else if (node->buf[0] == 'z') {
1620                                                 node->buf[0] = 'Z';
1621                                         }
1622                                 }
1623                         }
1624                         node->buf[1] = '\0';
1625                         node->specif = 1;
1626                         ++src;
1627                         break;
1628                 }
1629         }
1630         return src;
1631
1632 #undef INC_DST_OVERFLOW_CHECK
1633 }
1634
1635 static struct match_char *add_exten_to_pattern_tree(struct ast_context *con, struct ast_exten *e1, int findonly)
1636 {
1637         struct match_char *m1 = NULL;
1638         struct match_char *m2 = NULL;
1639         struct match_char **m0;
1640         const char *pos;
1641         int already;
1642         int pattern = 0;
1643         int idx_cur;
1644         int idx_next;
1645         char extenbuf[512];
1646         struct pattern_node pat_node[2];
1647
1648         if (e1->matchcid) {
1649                 if (sizeof(extenbuf) < strlen(e1->exten) + strlen(e1->cidmatch) + 2) {
1650                         ast_log(LOG_ERROR,
1651                                 "The pattern %s/%s is too big to deal with: it will be ignored! Disaster!\n",
1652                                 e1->exten, e1->cidmatch);
1653                         return NULL;
1654                 }
1655                 sprintf(extenbuf, "%s/%s", e1->exten, e1->cidmatch);/* Safe.  We just checked. */
1656         } else {
1657                 ast_copy_string(extenbuf, e1->exten, sizeof(extenbuf));
1658         }
1659
1660 #ifdef NEED_DEBUG
1661         ast_debug(1, "Adding exten %s to tree\n", extenbuf);
1662 #endif
1663         m1 = con->pattern_tree; /* each pattern starts over at the root of the pattern tree */
1664         m0 = &con->pattern_tree;
1665         already = 1;
1666
1667         pos = extenbuf;
1668         if (*pos == '_') {
1669                 pattern = 1;
1670                 ++pos;
1671         }
1672         idx_cur = 0;
1673         pos = get_pattern_node(&pat_node[idx_cur], pos, pattern, extenbuf);
1674         for (; pat_node[idx_cur].buf[0]; idx_cur = idx_next) {
1675                 idx_next = (idx_cur + 1) % ARRAY_LEN(pat_node);
1676                 pos = get_pattern_node(&pat_node[idx_next], pos, pattern, extenbuf);
1677
1678                 /* See about adding node to tree. */
1679                 m2 = NULL;
1680                 if (already && (m2 = already_in_tree(m1, pat_node[idx_cur].buf, pattern))
1681                         && m2->next_char) {
1682                         if (!pat_node[idx_next].buf[0]) {
1683                                 /*
1684                                  * This is the end of the pattern, but not the end of the tree.
1685                                  * Mark this node with the exten... a shorter pattern might win
1686                                  * if the longer one doesn't match.
1687                                  */
1688                                 if (findonly) {
1689                                         return m2;
1690                                 }
1691                                 if (m2->exten) {
1692                                         ast_log(LOG_WARNING, "Found duplicate exten. Had %s found %s\n",
1693                                                 m2->deleted ? "(deleted/invalid)" : m2->exten->exten, e1->exten);
1694                                 }
1695                                 m2->exten = e1;
1696                                 m2->deleted = 0;
1697                         }
1698                         m1 = m2->next_char; /* m1 points to the node to compare against */
1699                         m0 = &m2->next_char; /* m0 points to the ptr that points to m1 */
1700                 } else { /* not already OR not m2 OR nor m2->next_char */
1701                         if (m2) {
1702                                 if (findonly) {
1703                                         return m2;
1704                                 }
1705                                 m1 = m2; /* while m0 stays the same */
1706                         } else {
1707                                 if (findonly) {
1708                                         return m1;
1709                                 }
1710                                 m1 = add_pattern_node(con, m1, &pat_node[idx_cur], pattern, already, m0);
1711                                 if (!m1) { /* m1 is the node just added */
1712                                         return NULL;
1713                                 }
1714                                 m0 = &m1->next_char;
1715                         }
1716                         if (!pat_node[idx_next].buf[0]) {
1717                                 if (m2 && m2->exten) {
1718                                         ast_log(LOG_WARNING, "Found duplicate exten. Had %s found %s\n",
1719                                                 m2->deleted ? "(deleted/invalid)" : m2->exten->exten, e1->exten);
1720                                 }
1721                                 m1->deleted = 0;
1722                                 m1->exten = e1;
1723                         }
1724
1725                         /* The 'already' variable is a mini-optimization designed to make it so that we
1726                          * don't have to call already_in_tree when we know it will return false.
1727                          */
1728                         already = 0;
1729                 }
1730         }
1731         return m1;
1732 }
1733
1734 static void create_match_char_tree(struct ast_context *con)
1735 {
1736         struct ast_hashtab_iter *t1;
1737         struct ast_exten *e1;
1738 #ifdef NEED_DEBUG
1739         int biggest_bucket, resizes, numobjs, numbucks;
1740
1741         ast_debug(1, "Creating Extension Trie for context %s(%p)\n", con->name, con);
1742         ast_hashtab_get_stats(con->root_table, &biggest_bucket, &resizes, &numobjs, &numbucks);
1743         ast_debug(1, "This tree has %d objects in %d bucket lists, longest list=%d objects, and has resized %d times\n",
1744                         numobjs, numbucks, biggest_bucket, resizes);
1745 #endif
1746         t1 = ast_hashtab_start_traversal(con->root_table);
1747         while ((e1 = ast_hashtab_next(t1))) {
1748                 if (e1->exten) {
1749                         add_exten_to_pattern_tree(con, e1, 0);
1750                 } else {
1751                         ast_log(LOG_ERROR, "Attempt to create extension with no extension name.\n");
1752                 }
1753         }
1754         ast_hashtab_end_traversal(t1);
1755 }
1756
1757 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! */
1758 {
1759         /* destroy all the alternates */
1760         if (pattern_tree->alt_char) {
1761                 destroy_pattern_tree(pattern_tree->alt_char);
1762                 pattern_tree->alt_char = 0;
1763         }
1764         /* destroy all the nexts */
1765         if (pattern_tree->next_char) {
1766                 destroy_pattern_tree(pattern_tree->next_char);
1767                 pattern_tree->next_char = 0;
1768         }
1769         pattern_tree->exten = 0; /* never hurts to make sure there's no pointers laying around */
1770         ast_free(pattern_tree);
1771 }
1772
1773 /*!
1774  * \internal
1775  * \brief Get the length of the exten string.
1776  *
1777  * \param str Exten to get length.
1778  *
1779  * \retval strlen of exten.
1780  */
1781 static int ext_cmp_exten_strlen(const char *str)
1782 {
1783         int len;
1784
1785         len = 0;
1786         for (;;) {
1787                 /* Ignore '-' chars as eye candy fluff. */
1788                 while (*str == '-') {
1789                         ++str;
1790                 }
1791                 if (!*str) {
1792                         break;
1793                 }
1794                 ++str;
1795                 ++len;
1796         }
1797         return len;
1798 }
1799
1800 /*!
1801  * \internal
1802  * \brief Partial comparison of non-pattern extens.
1803  *
1804  * \param left Exten to compare.
1805  * \param right Exten to compare.  Also matches if this string ends first.
1806  *
1807  * \retval <0 if left < right
1808  * \retval =0 if left == right
1809  * \retval >0 if left > right
1810  */
1811 static int ext_cmp_exten_partial(const char *left, const char *right)
1812 {
1813         int cmp;
1814
1815         for (;;) {
1816                 /* Ignore '-' chars as eye candy fluff. */
1817                 while (*left == '-') {
1818                         ++left;
1819                 }
1820                 while (*right == '-') {
1821                         ++right;
1822                 }
1823
1824                 if (!*right) {
1825                         /*
1826                          * Right ended first for partial match or both ended at the same
1827                          * time for a match.
1828                          */
1829                         cmp = 0;
1830                         break;
1831                 }
1832
1833                 cmp = *left - *right;
1834                 if (cmp) {
1835                         break;
1836                 }
1837                 ++left;
1838                 ++right;
1839         }
1840         return cmp;
1841 }
1842
1843 /*!
1844  * \internal
1845  * \brief Comparison of non-pattern extens.
1846  *
1847  * \param left Exten to compare.
1848  * \param right Exten to compare.
1849  *
1850  * \retval <0 if left < right
1851  * \retval =0 if left == right
1852  * \retval >0 if left > right
1853  */
1854 static int ext_cmp_exten(const char *left, const char *right)
1855 {
1856         int cmp;
1857
1858         for (;;) {
1859                 /* Ignore '-' chars as eye candy fluff. */
1860                 while (*left == '-') {
1861                         ++left;
1862                 }
1863                 while (*right == '-') {
1864                         ++right;
1865                 }
1866
1867                 cmp = *left - *right;
1868                 if (cmp) {
1869                         break;
1870                 }
1871                 if (!*left) {
1872                         /*
1873                          * Get here only if both strings ended at the same time.  cmp
1874                          * would be non-zero if only one string ended.
1875                          */
1876                         break;
1877                 }
1878                 ++left;
1879                 ++right;
1880         }
1881         return cmp;
1882 }
1883
1884 /*
1885  * Special characters used in patterns:
1886  *      '_'     underscore is the leading character of a pattern.
1887  *              In other position it is treated as a regular char.
1888  *      '-' The '-' is a separator and ignored.  Why?  So patterns like NXX-XXX-XXXX work.
1889  *      .       one or more of any character. Only allowed at the end of
1890  *              a pattern.
1891  *      !       zero or more of anything. Also impacts the result of CANMATCH
1892  *              and MATCHMORE. Only allowed at the end of a pattern.
1893  *              In the core routine, ! causes a match with a return code of 2.
1894  *              In turn, depending on the search mode: (XXX check if it is implemented)
1895  *              - E_MATCH retuns 1 (does match)
1896  *              - E_MATCHMORE returns 0 (no match)
1897  *              - E_CANMATCH returns 1 (does match)
1898  *
1899  *      /       should not appear as it is considered the separator of the CID info.
1900  *              XXX at the moment we may stop on this char.
1901  *
1902  *      X Z N   match ranges 0-9, 1-9, 2-9 respectively.
1903  *      [       denotes the start of a set of character. Everything inside
1904  *              is considered literally. We can have ranges a-d and individual
1905  *              characters. A '[' and '-' can be considered literally if they
1906  *              are just before ']'.
1907  *              XXX currently there is no way to specify ']' in a range, nor \ is
1908  *              considered specially.
1909  *
1910  * When we compare a pattern with a specific extension, all characters in the extension
1911  * itself are considered literally.
1912  * XXX do we want to consider space as a separator as well ?
1913  * XXX do we want to consider the separators in non-patterns as well ?
1914  */
1915
1916 /*!
1917  * \brief helper functions to sort extension patterns in the desired way,
1918  * so that more specific patterns appear first.
1919  *
1920  * \details
1921  * The function compares individual characters (or sets of), returning
1922  * an int where bits 0-7 are the ASCII code of the first char in the set,
1923  * bits 8-15 are the number of characters in the set, and bits 16-20 are
1924  * for special cases.
1925  * This way more specific patterns (smaller character sets) appear first.
1926  * Wildcards have a special value, so that we can directly compare them to
1927  * sets by subtracting the two values. In particular:
1928  *  0x001xx     one character, character set starting with xx
1929  *  0x0yyxx     yy characters, character set starting with xx
1930  *  0x18000     '.' (one or more of anything)
1931  *  0x28000     '!' (zero or more of anything)
1932  *  0x30000     NUL (end of string)
1933  *  0x40000     error in set.
1934  * The pointer to the string is advanced according to needs.
1935  * NOTES:
1936  *  1. the empty set is ignored.
1937  *  2. given that a full set has always 0 as the first element,
1938  *     we could encode the special cases as 0xffXX where XX
1939  *     is 1, 2, 3, 4 as used above.
1940  */
1941 static int ext_cmp_pattern_pos(const char **p, unsigned char *bitwise)
1942 {
1943 #define BITS_PER        8       /* Number of bits per unit (byte). */
1944         unsigned char c;
1945         unsigned char cmin;
1946         int count;
1947         const char *end;
1948
1949         do {
1950                 /* Get character and advance. (Ignore '-' chars as eye candy fluff.) */
1951                 do {
1952                         c = *(*p)++;
1953                 } while (c == '-');
1954
1955                 /* always return unless we have a set of chars */
1956                 switch (c) {
1957                 default:
1958                         /* ordinary character */
1959                         bitwise[c / BITS_PER] = 1 << ((BITS_PER - 1) - (c % BITS_PER));
1960                         return 0x0100 | c;
1961
1962                 case 'n':
1963                 case 'N':
1964                         /* 2..9 */
1965                         bitwise[6] = 0x3f;
1966                         bitwise[7] = 0xc0;
1967                         return 0x0800 | '2';
1968
1969                 case 'x':
1970                 case 'X':
1971                         /* 0..9 */
1972                         bitwise[6] = 0xff;
1973                         bitwise[7] = 0xc0;
1974                         return 0x0A00 | '0';
1975
1976                 case 'z':
1977                 case 'Z':
1978                         /* 1..9 */
1979                         bitwise[6] = 0x7f;
1980                         bitwise[7] = 0xc0;
1981                         return 0x0900 | '1';
1982
1983                 case '.':
1984                         /* wildcard */
1985                         return 0x18000;
1986
1987                 case '!':
1988                         /* earlymatch */
1989                         return 0x28000; /* less specific than '.' */
1990
1991                 case '\0':
1992                         /* empty string */
1993                         *p = NULL;
1994                         return 0x30000;
1995
1996                 case '[':
1997                         /* char set */
1998                         break;
1999                 }
2000                 /* locate end of set */
2001                 end = strchr(*p, ']');
2002
2003                 if (!end) {
2004                         ast_log(LOG_WARNING, "Wrong usage of [] in the extension\n");
2005                         return 0x40000; /* XXX make this entry go last... */
2006                 }
2007
2008                 count = 0;
2009                 cmin = 0xFF;
2010                 for (; *p < end; ++*p) {
2011                         unsigned char c1;       /* first char in range */
2012                         unsigned char c2;       /* last char in range */
2013
2014                         c1 = (*p)[0];
2015                         if (*p + 2 < end && (*p)[1] == '-') { /* this is a range */
2016                                 c2 = (*p)[2];
2017                                 *p += 2;    /* skip a total of 3 chars */
2018                         } else {        /* individual character */
2019                                 c2 = c1;
2020                         }
2021                         if (c1 < cmin) {
2022                                 cmin = c1;
2023                         }
2024                         for (; c1 <= c2; ++c1) {
2025                                 unsigned char mask = 1 << ((BITS_PER - 1) - (c1 % BITS_PER));
2026
2027                                 /*
2028                                  * Note: If two character sets score the same, the one with the
2029                                  * lowest ASCII values will compare as coming first.  Must fill
2030                                  * in most significant bits for lower ASCII values to accomplish
2031                                  * the desired sort order.
2032                                  */
2033                                 if (!(bitwise[c1 / BITS_PER] & mask)) {
2034                                         /* Add the character to the set. */
2035                                         bitwise[c1 / BITS_PER] |= mask;
2036                                         count += 0x100;
2037                                 }
2038                         }
2039                 }
2040                 ++*p;
2041         } while (!count);/* While the char set was empty. */
2042         return count | cmin;
2043 }
2044
2045 /*!
2046  * \internal
2047  * \brief Comparison of exten patterns.
2048  *
2049  * \param left Pattern to compare.
2050  * \param right Pattern to compare.
2051  *
2052  * \retval <0 if left < right
2053  * \retval =0 if left == right
2054  * \retval >0 if left > right
2055  */
2056 static int ext_cmp_pattern(const char *left, const char *right)
2057 {
2058         int cmp;
2059         int left_pos;
2060         int right_pos;
2061
2062         for (;;) {
2063                 unsigned char left_bitwise[32] = { 0, };
2064                 unsigned char right_bitwise[32] = { 0, };
2065
2066                 left_pos = ext_cmp_pattern_pos(&left, left_bitwise);
2067                 right_pos = ext_cmp_pattern_pos(&right, right_bitwise);
2068                 cmp = left_pos - right_pos;
2069                 if (!cmp) {
2070                         /*
2071                          * Are the character sets different, even though they score the same?
2072                          *
2073                          * Note: Must swap left and right to get the sense of the
2074                          * comparison correct.  Otherwise, we would need to multiply by
2075                          * -1 instead.
2076                          */
2077                         cmp = memcmp(right_bitwise, left_bitwise, ARRAY_LEN(left_bitwise));
2078                 }
2079                 if (cmp) {
2080                         break;
2081                 }
2082                 if (!left) {
2083                         /*
2084                          * Get here only if both patterns ended at the same time.  cmp
2085                          * would be non-zero if only one pattern ended.
2086                          */
2087                         break;
2088                 }
2089         }
2090         return cmp;
2091 }
2092
2093 /*!
2094  * \internal
2095  * \brief Comparison of dialplan extens for sorting purposes.
2096  *
2097  * \param left Exten/pattern to compare.
2098  * \param right Exten/pattern to compare.
2099  *
2100  * \retval <0 if left < right
2101  * \retval =0 if left == right
2102  * \retval >0 if left > right
2103  */
2104 static int ext_cmp(const char *left, const char *right)
2105 {
2106         /* Make sure non-pattern extens come first. */
2107         if (left[0] != '_') {
2108                 if (right[0] == '_') {
2109                         return -1;
2110                 }
2111                 /* Compare two non-pattern extens. */
2112                 return ext_cmp_exten(left, right);
2113         }
2114         if (right[0] != '_') {
2115                 return 1;
2116         }
2117
2118         /*
2119          * OK, we need full pattern sorting routine.
2120          *
2121          * Skip past the underscores
2122          */
2123         return ext_cmp_pattern(left + 1, right + 1);
2124 }
2125
2126 int ast_extension_cmp(const char *a, const char *b)
2127 {
2128         int cmp;
2129
2130         cmp = ext_cmp(a, b);
2131         if (cmp < 0) {
2132                 return -1;
2133         }
2134         if (cmp > 0) {
2135                 return 1;
2136         }
2137         return 0;
2138 }
2139
2140 /*!
2141  * \internal
2142  * \brief used ast_extension_{match|close}
2143  * mode is as follows:
2144  *      E_MATCH         success only on exact match
2145  *      E_MATCHMORE     success only on partial match (i.e. leftover digits in pattern)
2146  *      E_CANMATCH      either of the above.
2147  * \retval 0 on no-match
2148  * \retval 1 on match
2149  * \retval 2 on early match.
2150  */
2151
2152 static int _extension_match_core(const char *pattern, const char *data, enum ext_match_t mode)
2153 {
2154         mode &= E_MATCH_MASK;   /* only consider the relevant bits */
2155
2156 #ifdef NEED_DEBUG_HERE
2157         ast_log(LOG_NOTICE,"match core: pat: '%s', dat: '%s', mode=%d\n", pattern, data, (int)mode);
2158 #endif
2159
2160         if (pattern[0] != '_') { /* not a pattern, try exact or partial match */
2161                 int lp = ext_cmp_exten_strlen(pattern);
2162                 int ld = ext_cmp_exten_strlen(data);
2163
2164                 if (lp < ld) {          /* pattern too short, cannot match */
2165 #ifdef NEED_DEBUG_HERE
2166                         ast_log(LOG_NOTICE,"return (0) - pattern too short, cannot match\n");
2167 #endif
2168                         return 0;
2169                 }
2170                 /* depending on the mode, accept full or partial match or both */
2171                 if (mode == E_MATCH) {
2172 #ifdef NEED_DEBUG_HERE
2173                         ast_log(LOG_NOTICE,"return (!ext_cmp_exten(%s,%s) when mode== E_MATCH)\n", pattern, data);
2174 #endif
2175                         return !ext_cmp_exten(pattern, data); /* 1 on match, 0 on fail */
2176                 }
2177                 if (ld == 0 || !ext_cmp_exten_partial(pattern, data)) { /* partial or full match */
2178 #ifdef NEED_DEBUG_HERE
2179                         ast_log(LOG_NOTICE,"return (mode(%d) == E_MATCHMORE ? lp(%d) > ld(%d) : 1)\n", mode, lp, ld);
2180 #endif
2181                         return (mode == E_MATCHMORE) ? lp > ld : 1; /* XXX should consider '!' and '/' ? */
2182                 } else {
2183 #ifdef NEED_DEBUG_HERE
2184                         ast_log(LOG_NOTICE,"return (0) when ld(%d) > 0 && pattern(%s) != data(%s)\n", ld, pattern, data);
2185 #endif
2186                         return 0;
2187                 }
2188         }
2189         if (mode == E_MATCH && data[0] == '_') {
2190                 /*
2191                  * XXX It is bad design that we don't know if we should be
2192                  * comparing data and pattern as patterns or comparing data if
2193                  * it conforms to pattern when the function is called.  First,
2194                  * assume they are both patterns.  If they don't match then try
2195                  * to see if data conforms to the given pattern.
2196                  *
2197                  * note: if this test is left out, then _x. will not match _x. !!!
2198                  */
2199 #ifdef NEED_DEBUG_HERE
2200                 ast_log(LOG_NOTICE, "Comparing as patterns first. pattern:%s data:%s\n", pattern, data);
2201 #endif
2202                 if (!ext_cmp_pattern(pattern + 1, data + 1)) {
2203 #ifdef NEED_DEBUG_HERE
2204                         ast_log(LOG_NOTICE,"return (1) - pattern matches pattern\n");
2205 #endif
2206                         return 1;
2207                 }
2208         }
2209
2210         ++pattern; /* skip leading _ */
2211         /*
2212          * XXX below we stop at '/' which is a separator for the CID info. However we should
2213          * not store '/' in the pattern at all. When we insure it, we can remove the checks.
2214          */
2215         for (;;) {
2216                 const char *end;
2217
2218                 /* Ignore '-' chars as eye candy fluff. */
2219                 while (*data == '-') {
2220                         ++data;
2221                 }
2222                 while (*pattern == '-') {
2223                         ++pattern;
2224                 }
2225                 if (!*data || !*pattern || *pattern == '/') {
2226                         break;
2227                 }
2228
2229                 switch (*pattern) {
2230                 case '[':       /* a range */
2231                         ++pattern;
2232                         end = strchr(pattern, ']'); /* XXX should deal with escapes ? */
2233                         if (!end) {
2234                                 ast_log(LOG_WARNING, "Wrong usage of [] in the extension\n");
2235                                 return 0;       /* unconditional failure */
2236                         }
2237                         if (pattern == end) {
2238                                 /* Ignore empty character sets. */
2239                                 ++pattern;
2240                                 continue;
2241                         }
2242                         for (; pattern < end; ++pattern) {
2243                                 if (pattern+2 < end && pattern[1] == '-') { /* this is a range */
2244                                         if (*data >= pattern[0] && *data <= pattern[2])
2245                                                 break;  /* match found */
2246                                         else {
2247                                                 pattern += 2; /* skip a total of 3 chars */
2248                                                 continue;
2249                                         }
2250                                 } else if (*data == pattern[0])
2251                                         break;  /* match found */
2252                         }
2253                         if (pattern >= end) {
2254 #ifdef NEED_DEBUG_HERE
2255                                 ast_log(LOG_NOTICE,"return (0) when pattern>=end\n");
2256 #endif
2257                                 return 0;
2258                         }
2259                         pattern = end;  /* skip and continue */
2260                         break;
2261                 case 'n':
2262                 case 'N':
2263                         if (*data < '2' || *data > '9') {
2264 #ifdef NEED_DEBUG_HERE
2265                                 ast_log(LOG_NOTICE,"return (0) N is not matched\n");
2266 #endif
2267                                 return 0;
2268                         }
2269                         break;
2270                 case 'x':
2271                 case 'X':
2272                         if (*data < '0' || *data > '9') {
2273 #ifdef NEED_DEBUG_HERE
2274                                 ast_log(LOG_NOTICE,"return (0) X is not matched\n");
2275 #endif
2276                                 return 0;
2277                         }
2278                         break;
2279                 case 'z':
2280                 case 'Z':
2281                         if (*data < '1' || *data > '9') {
2282 #ifdef NEED_DEBUG_HERE
2283                                 ast_log(LOG_NOTICE,"return (0) Z is not matched\n");
2284 #endif
2285                                 return 0;
2286                         }
2287                         break;
2288                 case '.':       /* Must match, even with more digits */
2289 #ifdef NEED_DEBUG_HERE
2290                         ast_log(LOG_NOTICE, "return (1) when '.' is matched\n");
2291 #endif
2292                         return 1;
2293                 case '!':       /* Early match */
2294 #ifdef NEED_DEBUG_HERE
2295                         ast_log(LOG_NOTICE, "return (2) when '!' is matched\n");
2296 #endif
2297                         return 2;
2298                 default:
2299                         if (*data != *pattern) {
2300 #ifdef NEED_DEBUG_HERE
2301                                 ast_log(LOG_NOTICE, "return (0) when *data(%c) != *pattern(%c)\n", *data, *pattern);
2302 #endif
2303                                 return 0;
2304                         }
2305                         break;
2306                 }
2307                 ++data;
2308                 ++pattern;
2309         }
2310         if (*data)                      /* data longer than pattern, no match */ {
2311 #ifdef NEED_DEBUG_HERE
2312                 ast_log(LOG_NOTICE, "return (0) when data longer than pattern\n");
2313 #endif
2314                 return 0;
2315         }
2316
2317         /*
2318          * match so far, but ran off the end of data.
2319          * Depending on what is next, determine match or not.
2320          */
2321         if (*pattern == '\0' || *pattern == '/') {      /* exact match */
2322 #ifdef NEED_DEBUG_HERE
2323                 ast_log(LOG_NOTICE, "at end, return (%d) in 'exact match'\n", (mode==E_MATCHMORE) ? 0 : 1);
2324 #endif
2325                 return (mode == E_MATCHMORE) ? 0 : 1;   /* this is a failure for E_MATCHMORE */
2326         } else if (*pattern == '!')     {               /* early match */
2327 #ifdef NEED_DEBUG_HERE
2328                 ast_log(LOG_NOTICE, "at end, return (2) when '!' is matched\n");
2329 #endif
2330                 return 2;
2331         } else {                                                /* partial match */
2332 #ifdef NEED_DEBUG_HERE
2333                 ast_log(LOG_NOTICE, "at end, return (%d) which deps on E_MATCH\n", (mode == E_MATCH) ? 0 : 1);
2334 #endif
2335                 return (mode == E_MATCH) ? 0 : 1;       /* this is a failure for E_MATCH */
2336         }
2337 }
2338
2339 /*
2340  * Wrapper around _extension_match_core() to do performance measurement
2341  * using the profiling code.
2342  */
2343 static int extension_match_core(const char *pattern, const char *data, enum ext_match_t mode)
2344 {
2345         int i;
2346         static int prof_id = -2;        /* marker for 'unallocated' id */
2347         if (prof_id == -2) {
2348                 prof_id = ast_add_profile("ext_match", 0);
2349         }
2350         ast_mark(prof_id, 1);
2351         i = _extension_match_core(ast_strlen_zero(pattern) ? "" : pattern, ast_strlen_zero(data) ? "" : data, mode);
2352         ast_mark(prof_id, 0);
2353         return i;
2354 }
2355
2356 int ast_extension_match(const char *pattern, const char *data)
2357 {
2358         return extension_match_core(pattern, data, E_MATCH);
2359 }
2360
2361 int ast_extension_close(const char *pattern, const char *data, int needmore)
2362 {
2363         if (needmore != E_MATCHMORE && needmore != E_CANMATCH)
2364                 ast_log(LOG_WARNING, "invalid argument %d\n", needmore);
2365         return extension_match_core(pattern, data, needmore);
2366 }
2367
2368 /* This structure must remain in sync with ast_context for proper hashtab matching */
2369 struct fake_context /* this struct is purely for matching in the hashtab */
2370 {
2371         ast_rwlock_t lock;
2372         struct ast_exten *root;
2373         struct ast_hashtab *root_table;
2374         struct match_char *pattern_tree;
2375         struct ast_context *next;
2376         struct ast_includes includes;
2377         struct ast_ignorepats ignorepats;
2378         const char *registrar;
2379         int refcount;
2380         int autohints;
2381         AST_LIST_HEAD_NOLOCK(, ast_sw) alts;
2382         ast_mutex_t macrolock;
2383         char name[256];
2384 };
2385
2386 struct ast_context *ast_context_find(const char *name)
2387 {
2388         struct ast_context *tmp;
2389         struct fake_context item;
2390
2391         if (!name) {
2392                 return NULL;
2393         }
2394         ast_rdlock_contexts();
2395         if (contexts_table) {
2396                 ast_copy_string(item.name, name, sizeof(item.name));
2397                 tmp = ast_hashtab_lookup(contexts_table, &item);
2398         } else {
2399                 tmp = NULL;
2400                 while ((tmp = ast_walk_contexts(tmp))) {
2401                         if (!strcasecmp(name, tmp->name)) {
2402                                 break;
2403                         }
2404                 }
2405         }
2406         ast_unlock_contexts();
2407         return tmp;
2408 }
2409
2410 #define STATUS_NO_CONTEXT       1
2411 #define STATUS_NO_EXTENSION     2
2412 #define STATUS_NO_PRIORITY      3
2413 #define STATUS_NO_LABEL         4
2414 #define STATUS_SUCCESS          5
2415
2416 static int matchcid(const char *cidpattern, const char *callerid)
2417 {
2418         /* If the Caller*ID pattern is empty, then we're matching NO Caller*ID, so
2419            failing to get a number should count as a match, otherwise not */
2420
2421         if (ast_strlen_zero(callerid)) {
2422                 return ast_strlen_zero(cidpattern) ? 1 : 0;
2423         }
2424
2425         return ast_extension_match(cidpattern, callerid);
2426 }
2427
2428 struct ast_exten *pbx_find_extension(struct ast_channel *chan,
2429         struct ast_context *bypass, struct pbx_find_info *q,
2430         const char *context, const char *exten, int priority,
2431         const char *label, const char *callerid, enum ext_match_t action)
2432 {
2433         int x, res;
2434         struct ast_context *tmp = NULL;
2435         struct ast_exten *e = NULL, *eroot = NULL;
2436         struct ast_sw *sw = NULL;
2437         struct ast_exten pattern = {NULL, };
2438         struct scoreboard score = {0, };
2439         struct ast_str *tmpdata = NULL;
2440         int idx;
2441
2442         pattern.label = label;
2443         pattern.priority = priority;
2444 #ifdef NEED_DEBUG_HERE
2445         ast_log(LOG_NOTICE, "Looking for cont/ext/prio/label/action = %s/%s/%d/%s/%d\n", context, exten, priority, label, (int) action);
2446 #endif
2447
2448         /* Initialize status if appropriate */
2449         if (q->stacklen == 0) {
2450                 q->status = STATUS_NO_CONTEXT;
2451                 q->swo = NULL;
2452                 q->data = NULL;
2453                 q->foundcontext = NULL;
2454         } else if (q->stacklen >= AST_PBX_MAX_STACK) {
2455                 ast_log(LOG_WARNING, "Maximum PBX stack exceeded\n");
2456                 return NULL;
2457         }
2458
2459         /* Check first to see if we've already been checked */
2460         for (x = 0; x < q->stacklen; x++) {
2461                 if (!strcasecmp(q->incstack[x], context))
2462                         return NULL;
2463         }
2464
2465         if (bypass) { /* bypass means we only look there */
2466                 tmp = bypass;
2467         } else {      /* look in contexts */
2468                 tmp = find_context(context);
2469                 if (!tmp) {
2470                         return NULL;
2471                 }
2472         }
2473
2474         if (q->status < STATUS_NO_EXTENSION)
2475                 q->status = STATUS_NO_EXTENSION;
2476
2477         /* Do a search for matching extension */
2478
2479         eroot = NULL;
2480         score.total_specificity = 0;
2481         score.exten = 0;
2482         score.total_length = 0;
2483         if (!tmp->pattern_tree && tmp->root_table) {
2484                 create_match_char_tree(tmp);
2485 #ifdef NEED_DEBUG
2486                 ast_debug(1, "Tree Created in context %s:\n", context);
2487                 log_match_char_tree(tmp->pattern_tree," ");
2488 #endif
2489         }
2490 #ifdef NEED_DEBUG
2491         ast_log(LOG_NOTICE, "The Trie we are searching in:\n");
2492         log_match_char_tree(tmp->pattern_tree, "::  ");
2493 #endif
2494
2495         do {
2496                 if (!ast_strlen_zero(overrideswitch)) {
2497                         char *osw = ast_strdupa(overrideswitch), *name;
2498                         struct ast_switch *asw;
2499                         ast_switch_f *aswf = NULL;
2500                         char *datap;
2501                         int eval = 0;
2502
2503                         name = strsep(&osw, "/");
2504                         asw = pbx_findswitch(name);
2505
2506                         if (!asw) {
2507                                 ast_log(LOG_WARNING, "No such switch '%s'\n", name);
2508                                 break;
2509                         }
2510
2511                         if (osw && strchr(osw, '$')) {
2512                                 eval = 1;
2513                         }
2514
2515                         if (eval && !(tmpdata = ast_str_thread_get(&switch_data, 512))) {
2516                                 ast_log(LOG_WARNING, "Can't evaluate overrideswitch?!\n");
2517                                 break;
2518                         } else if (eval) {
2519                                 /* Substitute variables now */
2520                                 pbx_substitute_variables_helper(chan, osw, ast_str_buffer(tmpdata), ast_str_size(tmpdata));
2521                                 datap = ast_str_buffer(tmpdata);
2522                         } else {
2523                                 datap = osw;
2524                         }
2525
2526                         /* equivalent of extension_match_core() at the switch level */
2527                         if (action == E_CANMATCH)
2528                                 aswf = asw->canmatch;
2529                         else if (action == E_MATCHMORE)
2530                                 aswf = asw->matchmore;
2531                         else /* action == E_MATCH */
2532                                 aswf = asw->exists;
2533                         if (!aswf) {
2534                                 res = 0;
2535                         } else {
2536                                 if (chan) {
2537                                         ast_autoservice_start(chan);
2538                                 }
2539                                 res = aswf(chan, context, exten, priority, callerid, datap);
2540                                 if (chan) {
2541                                         ast_autoservice_stop(chan);
2542                                 }
2543                         }
2544                         if (res) {      /* Got a match */
2545                                 q->swo = asw;
2546                                 q->data = datap;
2547                                 q->foundcontext = context;
2548                                 /* XXX keep status = STATUS_NO_CONTEXT ? */
2549                                 return NULL;
2550                         }
2551                 }
2552         } while (0);
2553
2554         if (extenpatternmatchnew) {
2555                 new_find_extension(exten, &score, tmp->pattern_tree, 0, 0, callerid, label, action);
2556                 eroot = score.exten;
2557
2558                 if (score.last_char == '!' && action == E_MATCHMORE) {
2559                         /* We match an extension ending in '!'.
2560                          * The decision in this case is final and is NULL (no match).
2561                          */
2562 #ifdef NEED_DEBUG_HERE
2563                         ast_log(LOG_NOTICE,"Returning MATCHMORE NULL with exclamation point.\n");
2564 #endif
2565                         return NULL;
2566                 }
2567
2568                 if (!eroot && (action == E_CANMATCH || action == E_MATCHMORE) && score.canmatch_exten) {
2569                         q->status = STATUS_SUCCESS;
2570 #ifdef NEED_DEBUG_HERE
2571                         ast_log(LOG_NOTICE,"Returning CANMATCH exten %s\n", score.canmatch_exten->exten);
2572 #endif
2573                         return score.canmatch_exten;
2574                 }
2575
2576                 if ((action == E_MATCHMORE || action == E_CANMATCH)  && eroot) {
2577                         if (score.node) {
2578                                 struct ast_exten *z = trie_find_next_match(score.node);
2579                                 if (z) {
2580 #ifdef NEED_DEBUG_HERE
2581                                         ast_log(LOG_NOTICE,"Returning CANMATCH/MATCHMORE next_match exten %s\n", z->exten);
2582 #endif
2583                                 } else {
2584                                         if (score.canmatch_exten) {
2585 #ifdef NEED_DEBUG_HERE
2586                                                 ast_log(LOG_NOTICE,"Returning CANMATCH/MATCHMORE canmatchmatch exten %s(%p)\n", score.canmatch_exten->exten, score.canmatch_exten);
2587 #endif
2588                                                 return score.canmatch_exten;
2589                                         } else {
2590 #ifdef NEED_DEBUG_HERE
2591                                                 ast_log(LOG_NOTICE,"Returning CANMATCH/MATCHMORE next_match exten NULL\n");
2592 #endif
2593                                         }
2594                                 }
2595                                 return z;
2596                         }
2597 #ifdef NEED_DEBUG_HERE
2598                         ast_log(LOG_NOTICE, "Returning CANMATCH/MATCHMORE NULL (no next_match)\n");
2599 #endif
2600                         return NULL;  /* according to the code, complete matches are null matches in MATCHMORE mode */
2601                 }
2602
2603                 if (eroot) {
2604                         /* found entry, now look for the right priority */
2605                         if (q->status < STATUS_NO_PRIORITY)
2606                                 q->status = STATUS_NO_PRIORITY;
2607                         e = NULL;
2608                         if (action == E_FINDLABEL && label ) {
2609                                 if (q->status < STATUS_NO_LABEL)
2610                                         q->status = STATUS_NO_LABEL;
2611                                 e = ast_hashtab_lookup(eroot->peer_label_table, &pattern);
2612                         } else {
2613                                 e = ast_hashtab_lookup(eroot->peer_table, &pattern);
2614                         }
2615                         if (e) {        /* found a valid match */
2616                                 q->status = STATUS_SUCCESS;
2617                                 q->foundcontext = context;
2618 #ifdef NEED_DEBUG_HERE
2619                                 ast_log(LOG_NOTICE,"Returning complete match of exten %s\n", e->exten);
2620 #endif
2621                                 return e;
2622                         }
2623                 }
2624         } else {   /* the old/current default exten pattern match algorithm */
2625
2626                 /* scan the list trying to match extension and CID */
2627                 eroot = NULL;
2628                 while ( (eroot = ast_walk_context_extensions(tmp, eroot)) ) {
2629                         int match = extension_match_core(eroot->exten, exten, action);
2630                         /* 0 on fail, 1 on match, 2 on earlymatch */
2631
2632                         if (!match || (eroot->matchcid && !matchcid(eroot->cidmatch, callerid)))
2633                                 continue;       /* keep trying */
2634                         if (match == 2 && action == E_MATCHMORE) {
2635                                 /* We match an extension ending in '!'.
2636                                  * The decision in this case is final and is NULL (no match).
2637                                  */
2638                                 return NULL;
2639                         }
2640                         /* found entry, now look for the right priority */
2641                         if (q->status < STATUS_NO_PRIORITY)
2642                                 q->status = STATUS_NO_PRIORITY;
2643                         e = NULL;
2644                         if (action == E_FINDLABEL && label ) {
2645                                 if (q->status < STATUS_NO_LABEL)
2646                                         q->status = STATUS_NO_LABEL;
2647                                 e = ast_hashtab_lookup(eroot->peer_label_table, &pattern);
2648                         } else {
2649                                 e = ast_hashtab_lookup(eroot->peer_table, &pattern);
2650                         }
2651                         if (e) {        /* found a valid match */
2652                                 q->status = STATUS_SUCCESS;
2653                                 q->foundcontext = context;
2654                                 return e;
2655                         }
2656                 }
2657         }
2658
2659         /* Check alternative switches */
2660         AST_LIST_TRAVERSE(&tmp->alts, sw, list) {
2661                 struct ast_switch *asw = pbx_findswitch(sw->name);
2662                 ast_switch_f *aswf = NULL;
2663                 char *datap;
2664
2665                 if (!asw) {
2666                         ast_log(LOG_WARNING, "No such switch '%s'\n", sw->name);
2667                         continue;
2668                 }
2669
2670                 /* Substitute variables now */
2671                 if (sw->eval) {
2672                         if (!(tmpdata = ast_str_thread_get(&switch_data, 512))) {
2673                                 ast_log(LOG_WARNING, "Can't evaluate switch?!\n");
2674                                 continue;
2675                         }
2676                         pbx_substitute_variables_helper(chan, sw->data, ast_str_buffer(tmpdata), ast_str_size(tmpdata));
2677                 }
2678
2679                 /* equivalent of extension_match_core() at the switch level */
2680                 if (action == E_CANMATCH)
2681                         aswf = asw->canmatch;
2682                 else if (action == E_MATCHMORE)
2683                         aswf = asw->matchmore;
2684                 else /* action == E_MATCH */
2685                         aswf = asw->exists;
2686                 datap = sw->eval ? ast_str_buffer(tmpdata) : sw->data;
2687                 if (!aswf)
2688                         res = 0;
2689                 else {
2690                         if (chan)
2691                                 ast_autoservice_start(chan);
2692                         res = aswf(chan, context, exten, priority, callerid, datap);
2693                         if (chan)
2694                                 ast_autoservice_stop(chan);
2695                 }
2696                 if (res) {      /* Got a match */
2697                         q->swo = asw;
2698                         q->data = datap;
2699                         q->foundcontext = context;
2700                         /* XXX keep status = STATUS_NO_CONTEXT ? */
2701                         return NULL;
2702                 }
2703         }
2704         q->incstack[q->stacklen++] = tmp->name; /* Setup the stack */
2705         /* Now try any includes we have in this context */
2706         for (idx = 0; idx < ast_context_includes_count(tmp); idx++) {
2707                 const struct ast_include *i = ast_context_includes_get(tmp, idx);
2708
2709                 if (include_valid(i)) {
2710                         if ((e = pbx_find_extension(chan, bypass, q, include_rname(i), exten, priority, label, callerid, action))) {
2711 #ifdef NEED_DEBUG_HERE
2712                                 ast_log(LOG_NOTICE,"Returning recursive match of %s\n", e->exten);
2713 #endif
2714                                 return e;
2715                         }
2716                         if (q->swo)
2717                                 return NULL;
2718                 }
2719         }
2720         return NULL;
2721 }
2722
2723 static void exception_store_free(void *data)
2724 {
2725         struct pbx_exception *exception = data;
2726         ast_string_field_free_memory(exception);
2727         ast_free(exception);
2728 }
2729
2730 static const struct ast_datastore_info exception_store_info = {
2731         .type = "EXCEPTION",
2732         .destroy = exception_store_free,
2733 };
2734
2735 /*!
2736  * \internal
2737  * \brief Set the PBX to execute the exception extension.
2738  *
2739  * \param chan Channel to raise the exception on.
2740  * \param reason Reason exception is raised.
2741  * \param priority Dialplan priority to set.
2742  *
2743  * \retval 0 on success.
2744  * \retval -1 on error.
2745  */
2746 int raise_exception(struct ast_channel *chan, const char *reason, int priority)
2747 {
2748         struct ast_datastore *ds = ast_channel_datastore_find(chan, &exception_store_info, NULL);
2749         struct pbx_exception *exception = NULL;
2750
2751         if (!ds) {
2752                 ds = ast_datastore_alloc(&exception_store_info, NULL);
2753                 if (!ds)
2754                         return -1;
2755                 if (!(exception = ast_calloc_with_stringfields(1, struct pbx_exception, 128))) {
2756                         ast_datastore_free(ds);
2757                         return -1;
2758                 }
2759                 ds->data = exception;
2760                 ast_channel_datastore_add(chan, ds);
2761         } else
2762                 exception = ds->data;
2763
2764         ast_string_field_set(exception, reason, reason);
2765         ast_string_field_set(exception, context, ast_channel_context(chan));
2766         ast_string_field_set(exception, exten, ast_channel_exten(chan));
2767         exception->priority = ast_channel_priority(chan);
2768         set_ext_pri(chan, "e", priority);
2769         return 0;
2770 }
2771
2772 static int acf_exception_read(struct ast_channel *chan, const char *name, char *data, char *buf, size_t buflen)
2773 {
2774         struct ast_datastore *ds = ast_channel_datastore_find(chan, &exception_store_info, NULL);
2775         struct pbx_exception *exception = NULL;
2776         if (!ds || !ds->data)
2777                 return -1;
2778         exception = ds->data;
2779         if (!strcasecmp(data, "REASON"))
2780                 ast_copy_string(buf, exception->reason, buflen);
2781         else if (!strcasecmp(data, "CONTEXT"))
2782                 ast_copy_string(buf, exception->context, buflen);
2783         else if (!strncasecmp(data, "EXTEN", 5))
2784                 ast_copy_string(buf, exception->exten, buflen);
2785         else if (!strcasecmp(data, "PRIORITY"))
2786                 snprintf(buf, buflen, "%d", exception->priority);
2787         else
2788                 return -1;
2789         return 0;
2790 }
2791
2792 static struct ast_custom_function exception_function = {
2793         .name = "EXCEPTION",
2794         .read = acf_exception_read,
2795 };
2796
2797 /*!
2798  * \brief The return value depends on the action:
2799  *
2800  * E_MATCH, E_CANMATCH, E_MATCHMORE require a real match,
2801  *      and return 0 on failure, -1 on match;
2802  * E_FINDLABEL maps the label to a priority, and returns
2803  *      the priority on success, ... XXX
2804  * E_SPAWN, spawn an application,
2805  *
2806  * \retval 0 on success.
2807  * \retval  -1 on failure.
2808  *
2809  * \note The channel is auto-serviced in this function, because doing an extension
2810  * match may block for a long time.  For example, if the lookup has to use a network
2811  * dialplan switch, such as DUNDi or IAX2, it may take a while.  However, the channel
2812  * auto-service code will queue up any important signalling frames to be processed
2813  * after this is done.
2814  */
2815 static int pbx_extension_helper(struct ast_channel *c, struct ast_context *con,
2816   const char *context, const char *exten, int priority,
2817   const char *label, const char *callerid, enum ext_match_t action, int *found, int combined_find_spawn)
2818 {
2819         struct ast_exten *e;
2820         struct ast_app *app;
2821         char *substitute = NULL;
2822         int res;
2823         struct pbx_find_info q = { .stacklen = 0 }; /* the rest is reset in pbx_find_extension */
2824         char passdata[EXT_DATA_SIZE];
2825         int matching_action = (action == E_MATCH || action == E_CANMATCH || action == E_MATCHMORE);
2826
2827         ast_rdlock_contexts();
2828         if (found)
2829                 *found = 0;
2830
2831         e = pbx_find_extension(c, con, &q, context, exten, priority, label, callerid, action);
2832         if (e) {
2833                 if (found)
2834                         *found = 1;
2835                 if (matching_action) {
2836                         ast_unlock_contexts();
2837                         return -1;      /* success, we found it */
2838                 } else if (action == E_FINDLABEL) { /* map the label to a priority */
2839                         res = e->priority;
2840                         ast_unlock_contexts();
2841                         return res;     /* the priority we were looking for */
2842                 } else {        /* spawn */
2843                         if (!e->cached_app)
2844                                 e->cached_app = pbx_findapp(e->app);
2845                         app = e->cached_app;
2846                         if (ast_strlen_zero(e->data)) {
2847                                 *passdata = '\0';
2848                         } else {
2849                                 const char *tmp;
2850                                 if ((!(tmp = strchr(e->data, '$'))) || (!strstr(tmp, "${") && !strstr(tmp, "$["))) {
2851                                         /* no variables to substitute, copy on through */
2852                                         ast_copy_string(passdata, e->data, sizeof(passdata));
2853                                 } else {
2854                                         /* save e->data on stack for later processing after lock released */
2855                                         substitute = ast_strdupa(e->data);
2856                                 }
2857                         }
2858                         ast_unlock_contexts();
2859                         if (!app) {
2860                                 ast_log(LOG_WARNING, "No application '%s' for extension (%s, %s, %d)\n", e->app, context, exten, priority);
2861                                 return -1;
2862                         }
2863                         if (ast_channel_context(c) != context)
2864                                 ast_channel_context_set(c, context);
2865                         if (ast_channel_exten(c) != exten)
2866                                 ast_channel_exten_set(c, exten);
2867                         ast_channel_priority_set(c, priority);
2868                         if (substitute) {
2869                                 pbx_substitute_variables_helper(c, substitute, passdata, sizeof(passdata)-1);
2870                         }
2871                         ast_debug(1, "Launching '%s'\n", app_name(app));
2872                         if (VERBOSITY_ATLEAST(3)) {
2873                                 ast_verb(3, "Executing [%s@%s:%d] " COLORIZE_FMT "(\"" COLORIZE_FMT "\", \"" COLORIZE_FMT "\") %s\n",
2874                                         exten, context, priority,
2875                                         COLORIZE(COLOR_BRCYAN, 0, app_name(app)),
2876                                         COLORIZE(COLOR_BRMAGENTA, 0, ast_channel_name(c)),
2877                                         COLORIZE(COLOR_BRMAGENTA, 0, passdata),
2878                                         "in new stack");
2879                         }
2880                         return pbx_exec(c, app, passdata);      /* 0 on success, -1 on failure */
2881                 }
2882         } else if (q.swo) {     /* not found here, but in another switch */
2883                 if (found)
2884                         *found = 1;
2885                 ast_unlock_contexts();
2886                 if (matching_action) {
2887                         return -1;
2888                 } else {
2889                         if (!q.swo->exec) {
2890                                 ast_log(LOG_WARNING, "No execution engine for switch %s\n", q.swo->name);
2891                                 res = -1;
2892                         }
2893                         return q.swo->exec(c, q.foundcontext ? q.foundcontext : context, exten, priority, callerid, q.data);
2894                 }
2895         } else {        /* not found anywhere, see what happened */
2896                 ast_unlock_contexts();
2897                 /* Using S_OR here because Solaris doesn't like NULL being passed to ast_log */
2898                 switch (q.status) {
2899                 case STATUS_NO_CONTEXT:
2900                         if (!matching_action && !combined_find_spawn)
2901                                 ast_log(LOG_NOTICE, "Cannot find extension context '%s'\n", S_OR(context, ""));
2902                         break;
2903                 case STATUS_NO_EXTENSION:
2904                         if (!matching_action && !combined_find_spawn)
2905                                 ast_log(LOG_NOTICE, "Cannot find extension '%s' in context '%s'\n", exten, S_OR(context, ""));
2906                         break;
2907                 case STATUS_NO_PRIORITY:
2908                         if (!matching_action && !combined_find_spawn)
2909                                 ast_log(LOG_NOTICE, "No such priority %d in extension '%s' in context '%s'\n", priority, exten, S_OR(context, ""));
2910                         break;
2911                 case STATUS_NO_LABEL:
2912                         if (context && !combined_find_spawn)
2913                                 ast_log(LOG_NOTICE, "No such label '%s' in extension '%s' in context '%s'\n", label, exten, S_OR(context, ""));
2914                         break;
2915                 default:
2916                         ast_debug(1, "Shouldn't happen!\n");
2917                 }
2918
2919                 return (matching_action) ? 0 : -1;
2920         }
2921 }
2922
2923 /*! \brief Find hint for given extension in context */
2924 static struct ast_exten *ast_hint_extension_nolock(struct ast_channel *c, const char *context, const char *exten)
2925 {
2926         struct pbx_find_info q = { .stacklen = 0 }; /* the rest is set in pbx_find_context */
2927         return pbx_find_extension(c, NULL, &q, context, exten, PRIORITY_HINT, NULL, "", E_MATCH);
2928 }
2929
2930 static struct ast_exten *ast_hint_extension(struct ast_channel *c, const char *context, const char *exten)
2931 {
2932         struct ast_exten *e;
2933         ast_rdlock_contexts();
2934         e = ast_hint_extension_nolock(c, context, exten);
2935         ast_unlock_contexts();
2936         return e;
2937 }
2938
2939 enum ast_extension_states ast_devstate_to_extenstate(enum ast_device_state devstate)
2940 {
2941         switch (devstate) {
2942         case AST_DEVICE_ONHOLD:
2943                 return AST_EXTENSION_ONHOLD;
2944         case AST_DEVICE_BUSY:
2945                 return AST_EXTENSION_BUSY;
2946         case AST_DEVICE_UNKNOWN:
2947                 return AST_EXTENSION_NOT_INUSE;
2948         case AST_DEVICE_UNAVAILABLE:
2949         case AST_DEVICE_INVALID:
2950                 return AST_EXTENSION_UNAVAILABLE;
2951         case AST_DEVICE_RINGINUSE:
2952                 return (AST_EXTENSION_INUSE | AST_EXTENSION_RINGING);
2953         case AST_DEVICE_RINGING:
2954                 return AST_EXTENSION_RINGING;
2955         case AST_DEVICE_INUSE:
2956                 return AST_EXTENSION_INUSE;
2957         case AST_DEVICE_NOT_INUSE:
2958                 return AST_EXTENSION_NOT_INUSE;
2959         case AST_DEVICE_TOTAL: /* not a device state, included for completeness */
2960                 break;
2961         }
2962
2963         return AST_EXTENSION_NOT_INUSE;
2964 }
2965
2966 /*!
2967  * \internal
2968  * \brief Parse out the presence portion of the hint string
2969  */
2970 static char *parse_hint_presence(struct ast_str *hint_args)
2971 {
2972         char *copy = ast_strdupa(ast_str_buffer(hint_args));
2973         char *tmp = "";
2974
2975         if ((tmp = strrchr(copy, ','))) {
2976                 *tmp = '\0';
2977                 tmp++;
2978         } else {
2979                 return NULL;
2980         }
2981         ast_str_set(&hint_args, 0, "%s", tmp);
2982         return ast_str_buffer(hint_args);
2983 }
2984
2985 /*!
2986  * \internal
2987  * \brief Parse out the device portion of the hint string
2988  */
2989 static char *parse_hint_device(struct ast_str *hint_args)
2990 {
2991         char *copy = ast_strdupa(ast_str_buffer(hint_args));
2992         char *tmp;
2993
2994         if ((tmp = strrchr(copy, ','))) {
2995                 *tmp = '\0';
2996         }
2997
2998         ast_str_set(&hint_args, 0, "%s", copy);
2999         return ast_str_buffer(hint_args);
3000 }
3001
3002 static void device_state_info_dt(void *obj)
3003 {
3004         struct ast_device_state_info *info = obj;
3005
3006         ao2_cleanup(info->causing_channel);
3007 }
3008
3009 static struct ao2_container *alloc_device_state_info(void)
3010 {
3011         return ao2_container_alloc_options(AO2_ALLOC_OPT_LOCK_NOLOCK, 1, NULL, NULL);
3012 }
3013
3014 static int ast_extension_state3(struct ast_str *hint_app, struct ao2_container *device_state_info)
3015 {
3016         char *cur;
3017         char *rest;
3018         struct ast_devstate_aggregate agg;
3019
3020         /* One or more devices separated with a & character */
3021         rest = parse_hint_device(hint_app);
3022
3023         ast_devstate_aggregate_init(&agg);
3024         while ((cur = strsep(&rest, "&"))) {
3025                 enum ast_device_state state = ast_device_state(cur);
3026
3027                 ast_devstate_aggregate_add(&agg, state);
3028                 if (device_state_info) {
3029                         struct ast_device_state_info *obj;
3030
3031                         obj = ao2_alloc_options(sizeof(*obj) + strlen(cur), device_state_info_dt, AO2_ALLOC_OPT_LOCK_NOLOCK);
3032                         /* if failed we cannot add this device */
3033                         if (obj) {
3034                                 obj->device_state = state;
3035                                 strcpy(obj->device_name, cur);
3036                                 ao2_link(device_state_info, obj);
3037                                 ao2_ref(obj, -1);
3038                         }
3039                 }
3040         }
3041
3042         return ast_devstate_to_extenstate(ast_devstate_aggregate_result(&agg));
3043 }
3044
3045 /*! \brief Check state of extension by using hints */
3046 static int ast_extension_state2(struct ast_exten *e, struct ao2_container *device_state_info)
3047 {
3048         struct ast_str *hint_app = ast_str_thread_get(&extensionstate_buf, 32);
3049
3050         if (!e || !hint_app) {
3051                 return -1;
3052         }
3053
3054         ast_str_set(&hint_app, 0, "%s", ast_get_extension_app(e));
3055         return ast_extension_state3(hint_app, device_state_info);
3056 }
3057
3058 /*! \brief Return extension_state as string */
3059 const char *ast_extension_state2str(int extension_state)
3060 {
3061         int i;
3062
3063         for (i = 0; (i < ARRAY_LEN(extension_states)); i++) {
3064                 if (extension_states[i].extension_state == extension_state)
3065                         return extension_states[i].text;
3066         }
3067         return "Unknown";
3068 }
3069
3070 /*!
3071  * \internal
3072  * \brief Check extension state for an extension by using hint
3073  */
3074 static int internal_extension_state_extended(struct ast_channel *c, const char *context, const char *exten,
3075         struct ao2_container *device_state_info)
3076 {
3077         struct ast_exten *e;
3078
3079         if (!(e = ast_hint_extension(c, context, exten))) {  /* Do we have a hint for this extension ? */
3080                 return -1;                   /* No hint, return -1 */
3081         }
3082
3083         if (e->exten[0] == '_') {
3084                 /* Create this hint on-the-fly */
3085                 ast_add_extension(e->parent->name, 0, exten, e->priority, e->label,
3086                         e->matchcid ? e->cidmatch : NULL, e->app, ast_strdup(e->data), ast_free_ptr,
3087                         e->registrar);
3088                 if (!(e = ast_hint_extension(c, context, exten))) {
3089                         /* Improbable, but not impossible */
3090                         return -1;
3091                 }
3092         }
3093
3094         return ast_extension_state2(e, device_state_info);  /* Check all devices in the hint */
3095 }
3096
3097 /*! \brief Check extension state for an extension by using hint */
3098 int ast_extension_state(struct ast_channel *c, const char *context, const char *exten)
3099 {
3100         return internal_extension_state_extended(c, context, exten, NULL);
3101 }
3102
3103 /*! \brief Check extended extension state for an extension by using hint */
3104 int ast_extension_state_extended(struct ast_channel *c, const char *context, const char *exten,
3105         struct ao2_container **device_state_info)
3106 {
3107         struct ao2_container *container = NULL;
3108         int ret;
3109
3110         if (device_state_info) {
3111                 container = alloc_device_state_info();
3112         }
3113
3114         ret = internal_extension_state_extended(c, context, exten, container);
3115         if (ret < 0 && container) {
3116                 ao2_ref(container, -1);
3117                 container = NULL;
3118         }
3119
3120         if (device_state_info) {
3121                 get_device_state_causing_channels(container);
3122                 *device_state_info = container;
3123         }
3124
3125         return ret;
3126 }
3127
3128 static int extension_presence_state_helper(struct ast_exten *e, char **subtype, char **message)
3129 {
3130         struct ast_str *hint_app = ast_str_thread_get(&extensionstate_buf, 32);
3131         char *presence_provider;
3132         const char *app;
3133
3134         if (!e || !hint_app) {
3135                 return -1;
3136         }
3137
3138         app = ast_get_extension_app(e);
3139         if (ast_strlen_zero(app)) {
3140                 return -1;
3141         }
3142
3143         ast_str_set(&hint_app, 0, "%s", app);
3144         presence_provider = parse_hint_presence(hint_app);
3145
3146         if (ast_strlen_zero(presence_provider)) {
3147                 /* No presence string in the hint */
3148                 return 0;
3149         }
3150
3151         return ast_presence_state(presence_provider, subtype, message);
3152 }
3153
3154 int ast_hint_presence_state(struct ast_channel *c, const char *context, const char *exten, char **subtype, char **message)
3155 {
3156         struct ast_exten *e;
3157
3158         if (!(e = ast_hint_extension(c, context, exten))) {  /* Do we have a hint for this extension ? */
3159                 return -1;                   /* No hint, return -1 */
3160         }
3161
3162         if (e->exten[0] == '_') {
3163                 /* Create this hint on-the-fly */
3164                 ast_add_extension(e->parent->name, 0, exten, e->priority, e->label,
3165                         e->matchcid ? e->cidmatch : NULL, e->app, ast_strdup(e->data), ast_free_ptr,
3166                         e->registrar);
3167                 if (!(e = ast_hint_extension(c, context, exten))) {
3168                         /* Improbable, but not impossible */
3169                         return -1;
3170                 }
3171         }
3172
3173         return extension_presence_state_helper(e, subtype, message);
3174 }
3175
3176 static int execute_state_callback(ast_state_cb_type cb,
3177         const char *context,
3178         const char *exten,
3179         void *data,
3180         enum ast_state_cb_update_reason reason,
3181         struct ast_hint *hint,
3182         struct ao2_container *device_state_info)
3183 {
3184         int res = 0;
3185         struct ast_state_cb_info info = { 0, };
3186
3187         info.reason = reason;
3188
3189         /* Copy over current hint data */
3190         if (hint) {
3191                 ao2_lock(hint);
3192                 info.exten_state = hint->laststate;
3193                 info.device_state_info = device_state_info;
3194                 info.presence_state = hint->last_presence_state;
3195                 if (!(ast_strlen_zero(hint->last_presence_subtype))) {
3196                         info.presence_subtype = ast_strdupa(hint->last_presence_subtype);
3197                 } else {
3198                         info.presence_subtype = "";
3199                 }
3200                 if (!(ast_strlen_zero(hint->last_presence_message))) {
3201                         info.presence_message = ast_strdupa(hint->last_presence_message);
3202                 } else {
3203                         info.presence_message = "";
3204                 }
3205                 ao2_unlock(hint);
3206         } else {
3207                 info.exten_state = AST_EXTENSION_REMOVED;
3208         }
3209
3210         res = cb(context, exten, &info, data);
3211
3212         return res;
3213 }
3214
3215 /*!
3216  * /internal
3217  * /brief Identify a channel for every device which is supposedly responsible for the device state.
3218  *
3219  * Especially when the device is ringing, the oldest ringing channel is chosen.
3220  * For all other cases the first encountered channel in the specific state is chosen.
3221  */
3222 static void get_device_state_causing_channels(struct ao2_container *c)
3223 {
3224         struct ao2_iterator iter;
3225         struct ast_device_state_info *info;
3226         struct ast_channel *chan;
3227
3228         if (!c || !ao2_container_count(c)) {
3229                 return;
3230         }
3231         iter = ao2_iterator_init(c, 0);
3232         for (; (info = ao2_iterator_next(&iter)); ao2_ref(info, -1)) {
3233                 enum ast_channel_state search_state = 0; /* prevent false uninit warning */
3234                 char match[AST_CHANNEL_NAME];
3235                 struct ast_channel_iterator *chan_iter;
3236                 struct timeval chantime = {0, }; /* prevent false uninit warning */
3237
3238                 switch (info->device_state) {
3239                 case AST_DEVICE_RINGING:
3240                 case AST_DEVICE_RINGINUSE:
3241                         /* find ringing channel */
3242                         search_state = AST_STATE_RINGING;
3243                         break;
3244                 case AST_DEVICE_BUSY:
3245                         /* find busy channel */
3246                         search_state = AST_STATE_BUSY;
3247                         break;
3248                 case AST_DEVICE_ONHOLD:
3249                 case AST_DEVICE_INUSE:
3250                         /* find up channel */
3251                         search_state = AST_STATE_UP;
3252                         break;
3253                 case AST_DEVICE_UNKNOWN:
3254                 case AST_DEVICE_NOT_INUSE:
3255                 case AST_DEVICE_INVALID:
3256                 case AST_DEVICE_UNAVAILABLE:
3257                 case AST_DEVICE_TOTAL /* not a state */:
3258                         /* no channels are of interest */
3259                         continue;
3260                 }
3261
3262                 /* iterate over all channels of the device */
3263                 snprintf(match, sizeof(match), "%s-", info->device_name);
3264                 chan_iter = ast_channel_iterator_by_name_new(match, strlen(match));
3265                 for (; (chan = ast_channel_iterator_next(chan_iter)); ast_channel_unref(chan)) {
3266                         ast_channel_lock(chan);
3267                         /* this channel's state doesn't match */
3268                         if (search_state != ast_channel_state(chan)) {
3269                                 ast_channel_unlock(chan);
3270                                 continue;
3271                         }
3272                         /* any non-ringing channel will fit */
3273                         if (search_state != AST_STATE_RINGING) {
3274                                 ast_channel_unlock(chan);
3275                                 info->causing_channel = chan; /* is kept ref'd! */
3276                                 break;
3277                         }
3278                         /* but we need the oldest ringing channel of the device to match with undirected pickup */
3279                         if (!info->causing_channel) {
3280                                 chantime = ast_channel_creationtime(chan);
3281                                 ast_channel_ref(chan); /* must ref it! */
3282                                 info->causing_channel = chan;
3283                         } else if (ast_tvcmp(ast_channel_creationtime(chan), chantime) < 0) {
3284                                 chantime = ast_channel_creationtime(chan);
3285                                 ast_channel_unref(info->causing_channel);
3286                                 ast_channel_ref(chan); /* must ref it! */
3287                                 info->causing_channel = chan;
3288                         }
3289                         ast_channel_unlock(chan);
3290                 }
3291                 ast_channel_iterator_destroy(chan_iter);
3292         }
3293         ao2_iterator_destroy(&iter);
3294 }
3295
3296 static void device_state_notify_callbacks(struct ast_hint *hint, struct ast_str **hint_app)
3297 {
3298         struct ao2_iterator cb_iter;
3299         struct ast_state_cb *state_cb;
3300         int state;
3301         int same_state;
3302         struct ao2_container *device_state_info;
3303         int first_extended_cb_call = 1;
3304         char context_name[AST_MAX_CONTEXT];
3305         char exten_name[AST_MAX_EXTENSION];
3306
3307         ao2_lock(hint);
3308         if (!hint->exten) {
3309                 /* The extension has already been destroyed */
3310                 ao2_unlock(hint);
3311                 return;
3312         }
3313
3314         /*
3315          * Save off strings in case the hint extension gets destroyed
3316          * while we are notifying the watchers.
3317          */
3318         ast_copy_string(context_name,
3319                         ast_get_context_name(ast_get_extension_context(hint->exten)),
3320                         sizeof(context_name));
3321         ast_copy_string(exten_name, ast_get_extension_name(hint->exten),
3322                         sizeof(exten_name));
3323         ast_str_set(hint_app, 0, "%s", ast_get_extension_app(hint->exten));
3324         ao2_unlock(hint);
3325
3326         /*
3327          * Get device state for this hint.
3328          *
3329          * NOTE: We cannot hold any locks while determining the hint
3330          * device state or notifying the watchers without causing a
3331          * deadlock.  (conlock, hints, and hint)
3332          */
3333
3334         /* Make a container so state3 can fill it if we wish.
3335          * If that failed we simply do not provide the extended state info.
3336          */
3337         device_state_info = alloc_device_state_info();
3338
3339         state = ast_extension_state3(*hint_app, device_state_info);
3340         same_state = state == hint->laststate;
3341         if (same_state && (~state & AST_EXTENSION_RINGING)) {
3342                 ao2_cleanup(device_state_info);
3343                 return;
3344         }
3345
3346         /* Device state changed since last check - notify the watchers. */
3347         hint->laststate = state;        /* record we saw the change */
3348
3349         /* For general callbacks */
3350         if (!same_state) {
3351                 cb_iter = ao2_iterator_init(statecbs, 0);
3352                 for (; (state_cb = ao2_iterator_next(&cb_iter)); ao2_ref(state_cb, -1)) {
3353                         execute_state_callback(state_cb->change_cb,
3354                                 context_name,
3355                                 exten_name,
3356                                 state_cb->data,
3357                                 AST_HINT_UPDATE_DEVICE,
3358                                 hint,
3359                                 NULL);
3360                 }
3361                 ao2_iterator_destroy(&cb_iter);
3362         }
3363
3364         /* For extension callbacks */
3365         /* extended callbacks are called when the state changed or when AST_STATE_RINGING is
3366          * included. Normal callbacks are only called when the state changed.
3367          */
3368         cb_iter = ao2_iterator_init(hint->callbacks, 0);
3369         for (; (state_cb = ao2_iterator_next(&cb_iter)); ao2_ref(state_cb, -1)) {
3370                 if (state_cb->extended && first_extended_cb_call) {
3371                         /* Fill detailed device_state_info now that we know it is used by extd. callback */
3372                         first_extended_cb_call = 0;
3373                         get_device_state_causing_channels(device_state_info);
3374                 }
3375                 if (state_cb->extended || !same_state) {
3376                         execute_state_callback(state_cb->change_cb,
3377                                 context_name,
3378                                 exten_name,
3379                                 state_cb->data,
3380                                 AST_HINT_UPDATE_DEVICE,
3381                                 hint,
3382                                 state_cb->extended ? device_state_info : NULL);
3383                 }
3384         }
3385         ao2_iterator_destroy(&cb_iter);
3386
3387         ao2_cleanup(device_state_info);
3388 }
3389
3390 static void presence_state_notify_callbacks(struct ast_hint *hint, struct ast_str **hint_app,
3391                                             struct ast_presence_state_message *presence_state)
3392 {
3393         struct ao2_iterator cb_iter;
3394         struct ast_state_cb *state_cb;
3395         char context_name[AST_MAX_CONTEXT];
3396         char exten_name[AST_MAX_EXTENSION];
3397
3398         ao2_lock(hint);
3399         if (!hint->exten) {
3400                 /* The extension has already been destroyed */
3401                 ao2_unlock(hint);
3402                 return;
3403         }
3404
3405         /*
3406          * Save off strings in case the hint extension gets destroyed
3407          * while we are notifying the watchers.
3408          */
3409         ast_copy_string(context_name,
3410                         ast_get_context_name(ast_get_extension_context(hint->exten)),
3411                         sizeof(context_name));
3412         ast_copy_string(exten_name, ast_get_extension_name(hint->exten),
3413                         sizeof(exten_name));
3414         ast_str_set(hint_app, 0, "%s", ast_get_extension_app(hint->exten));
3415         ao2_unlock(hint);
3416
3417         /* Check to see if update is necessary */
3418         if ((hint->last_presence_state == presence_state->state) &&
3419             ((hint->last_presence_subtype && presence_state->subtype &&
3420               !strcmp(hint->last_presence_subtype, presence_state->subtype)) ||
3421              (!hint->last_presence_subtype && !presence_state->subtype)) &&
3422             ((hint->last_presence_message && presence_state->message &&
3423               !strcmp(hint->last_presence_message, presence_state->message)) ||
3424              (!hint->last_presence_message && !presence_state->message))) {
3425                 /* this update is the same as the last, do nothing */
3426                 return;
3427         }
3428
3429         /* update new values */
3430         ast_free(hint->last_presence_subtype);
3431         ast_free(hint->last_presence_message);
3432         hint->last_presence_state = presence_state->state;
3433         hint->last_presence_subtype = presence_state->subtype ? ast_strdup(presence_state->subtype) : NULL;
3434         hint->last_presence_message = presence_state->message ? ast_strdup(presence_state->message) : NULL;
3435
3436         /* For general callbacks */
3437         cb_iter = ao2_iterator_init(statecbs, 0);
3438         for (; (state_cb = ao2_iterator_next(&cb_iter)); ao2_ref(state_cb, -1)) {
3439                 execute_state_callback(state_cb->change_cb,
3440                         context_name,
3441                         exten_name,
3442                         state_cb->data,
3443                         AST_HINT_UPDATE_PRESENCE,
3444                         hint,
3445                         NULL);
3446         }
3447         ao2_iterator_destroy(&cb_iter);
3448
3449         /* For extension callbacks */
3450         cb_iter = ao2_iterator_init(hint->callbacks, 0);
3451         for (; (state_cb = ao2_iterator_next(&cb_iter)); ao2_cleanup(state_cb)) {
3452                 execute_state_callback(state_cb->change_cb,
3453                         context_name,
3454                         exten_name,
3455                         state_cb->data,