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