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